idnits 2.17.1 draft-rfced-info-kubo-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-27) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == The page length should not exceed 58 lines per page, but there was 11 longer pages, the longest (page 2) being 64 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 13 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There is 1 instance of too long lines in the document, the longest one being 3 characters in excess of 72. ** There are 293 instances of lines with control characters in the document. == There are 50 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 643 has weird spacing: '...re G is a (m,...' == Unrecognized Status in 'Category: Informational ', assuming Proposed Standard (Expected one of 'Standards Track', 'Full Standard', 'Draft Standard', 'Proposed Standard', 'Best Current Practice', 'Informational', 'Experimental', 'Informational', 'Historic'.) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (June 1998) is 9448 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '1' on line 70 looks like a reference -- Missing reference section? '2' on line 71 looks like a reference -- Missing reference section? '3' on line 71 looks like a reference -- Missing reference section? '4' on line 550 looks like a reference -- Missing reference section? '5' on line 553 looks like a reference -- Missing reference section? '6' on line 557 looks like a reference Summary: 9 errors (**), 0 flaws (~~), 5 warnings (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 INTERNET DRAFT EXPIRES JAN 1999 INTERNET DRAFT 2 Network Working Group T. Nishioka and T. Kubo 3 INTERNET DRAFT Info. and Comm. Biz. Div. 4 Category: Informational ADVANCE Co., Ltd. 6 June 1998 8 The ID-based Key Management System (IDKMS) 9 11 Status of This Memo 13 This document is an Internet-Draft. Internet-Drafts are working 14 documents of the Internet Engineering Task Force (IETF), its 15 areas, and its working groups. Note that other groups may also 16 distribute working documents as Internet-Drafts. 18 Internet-Drafts are draft documents valid for a maximum of six 19 months and may be updated, replaced, or obsoleted by other 20 documents at any time. It is inappropriate to use Internet- 21 Drafts as reference material or to cite them other than as 22 "work in progress." 24 To view the entire list of current Internet-Drafts, please check 25 the "1id-abstracts.txt" listing contained in the Internet-Drafts 26 Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net 27 (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au 28 (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu 29 (US West Coast). 31 Distribution of this document is unlimited. 33 Abstract 35 This informational document describes some cryptographic protocols on an 36 ID-based system called Key Predistribution System (KPS). 38 Table of Contents 40 1. Introduction and preliminary remarks............................2 41 2. Setup...........................................................3 42 2.1. PAGS Setup...............................................3 43 2.2. User Setup...............................................3 44 3. Cryptographic Protocols.........................................4 45 3.1. Confidential Communication...............................4 46 3.2. Entity Authentication....................................5 47 3.3. Mutual Authentication....................................6 48 3.4. Message Authentication...................................8 49 3.5. Digital Signature........................................9 50 3.6. Key Recovery............................................10 51 4. Security Considerations and One Implementation of KPS..........12 52 Acknowledgment....................................................14 53 References........................................................14 54 Authors' Address..................................................14 56 1. Introduction and preliminary remarks 58 Cryptography is one of the fundamental tools to make the Internet a 59 more secure network. 61 It guards the Internet against various malicious attacks like 62 eavesdropping, masquerading, falsifying, and so on. Although 63 cryptography has powerful abilities in this area, it has also an 64 Achilles' heel in key management. If key management were insecure, 65 any system using cryptography would be totally defenseless, no 66 matter how strong the cryptography is. The construction of a public 67 -key infrastructure is one important point of the key management. 69 In this memo we propose a different type of key management, which is 70 based on an ID-based cryptography[1] called Key Predistribution 71 System (KPS)[2,3]. 73 The simplest KPS consists of one center and unspecified entities 74 (users). It is assumed that each unspecified entity has his own 75 broad-sense "name" represented by an ID, which may be something 76 like, for example, a mail-address in the internet. The center called 77 "KPS center" generates a center-algorithm represented by G. The 78 center-algorithm G is confidential and nobody except the KPS center 79 must know its content. 81 The algorithm G outputs a secret algorithm if an ID is input into G. 82 The secret algorithm is confidentially and securely distributed to 83 an entity having the corresponding ID. The secret algorithm has the 84 capability to generate a common key. If the owner inputs an ID into 85 his secret algorithm, the secret algorithm outputs a common key 86 between the owner and the entity having the corresponding ID. 87 Therefore any common key has already been pre-distributed to an 88 entity when the entity received his own secret algorithm. 90 Using the above KPS, we introduce some interesting cryptographic 91 protocols on the internet. The following protocols are mainly 92 discussed on the application layer. 94 It is expected that the reader is familiar with the basics of 95 cryptography and linear algebra. 97 Due to the ASCII representation of this memo, the following style is 98 chosen for mathematical purposes: 100 - a^{b} means the exponentiation of a to the power of b, which is 101 always used within a modulo context. 103 - a^[b] means a with an upper index of b. 105 - a_[b] means a with a lower index or subscription of b. 107 - a_[b,c] means a with lower indices or subscription of b and c. 109 - a=b means equality or congruency within a modulo context. 111 - E_{k}(M) means encryption of message M by key k. 113 - D_{k}(C) means decryption of cipher C by key k. 115 2. Setup 117 2.1. PAGS Set up 119 "Private Algorithm Generation System (PAGS)" represents both the KPS 120 center and its center-algorithm: G( , ) for the internet. 122 PAGS first generates the center-algorithm, G and stores it secretly. 124 2.2. User Set up 126 An entity A applies for his own private ID to PAGS, where a private 127 ID represents the secret-algorithm for the internet. 129 1. The entity A proposes his own "public ID": ID_[A] to PAGS, 130 where public ID means usual the ID for the internet in 131 contrast to the private ID. 133 2. Receiving A's application and his public ID, PAGS 134 authenticates A and the correctness of ID_[A]. 136 3. If the application has no problem, PAGS generates the 137 private ID: X_[A] using the center-algorithm G; 139 X_[A]( )= G(ID_[A], )=G( ,ID_[A]). 141 where G having two inputs is symmetric mapping the two 142 inputs. If the application has a problem, PAGS notifies the 143 applicant of the result and does not generate the 144 corresponding private ID. 146 4. PAGS confidentially distributes the private ID, X_[A] to the 147 entity A through a more secure channel than the internet. 149 5. Receiving the private ID, the entity A stores the private 150 ID: X_[A] secretly. 152 The entity A is able to share each different common key with any 153 other entity B non-interactively using his own private ID, X_[A]. 154 The entity A inputs B's public ID: ID_[B] into X_[A] and then A gets 155 the common key: k_[AB]; 157 k_[AB] = X_[A](ID_[B]) = G(ID_[A],ID_[B]). 159 Independently and in the same way, the entity B can generate the 160 common key with his private ID: X_[B]; 162 k_[BA] = X_[B](ID_[A]) = G(ID_[B],ID_[A]), 163 = G(ID_[A],ID_[B]), 164 = k_[AB]. 166 3. Cryptographic Protocols 168 Some interesting cryptographic protocols are presented in this 169 section. They are based on some powerful features of KPS. 171 3.1. Confidential Communication 173 We deal with confidential communication by common-key cryptography. 174 It is critical to think about how to distribute a session key: k to 175 a correct receiver B, where the session key is cryptographic and 176 used to encrypt the main message: M. The ciphertext C is given by, 178 E_{k}(M). 180 We exhibit the key sharing between a sender A and a receiver B and 181 the confidential communication protocol in the following; 183 3.1.1. Sender side 185 3.1.1.1. Common key generation 187 The sender A generates a common key using his private 188 ID and B's public ID; 190 k_[AB] = X_[A](ID_[B]). 192 3.1.1.2. Session key generation 194 The sender A generates a session key: k, using some 195 appropriate random generator. 197 3.1.1.3. Message encryption 199 Message M is encrypted with the session key into 200 ciphertext C; 202 C = E_{k}(M). 204 3.1.1.4. Session key encryption 206 The session key is encrypted with the common key; 208 E_{k_[AB]}(k). 210 3.1.1.5. Sending ciphertext 212 The sender A sends the following data; 214 ID_[A]aE_{k_[AB]}(k)aC, 216 to the receiver B where the symbol "a"means 217 concatenation. 219 Note: The sender's public ID, ID_[A] needs not to be 220 sent explicitly if the receiver recovers ID_[A] from 221 other protocols. 223 3.1.2. Receiver side 225 3.1.2.1. Extraction of public ID 227 Receiving the ciphered data, the receiver B extracts 228 the sender's public ID: 230 ID_[A], 232 from them. 234 3.1.2.2. Common key generation 236 The sender B generates a common key using his private 237 ID and A's public ID; 239 k_[AB] = X_[B](ID_[A]). 241 3.1.2.3. Session key decryption 243 The session key is decrypted with the common key; 245 k = D_{k_[AB]}(E_{k_[AB]}(k)). 247 3.1.2.4. Message decryption 249 The Message is decrypted with the session key; 251 M = D_{k}(C). 253 3.2. Entity Authentication 255 Owing to KPS, any two entities share each own common key non 256 -interactively. Using such a feature, a challenger C can 257 authenticate a responder V. We introduce an authentication protocol 258 in the following. It is assumed that the challenger C and the 259 responder V have already known each public ID: ID_[C], ID_[V]. 261 3.2.1. Challenger side 263 3.2.1.1. Challenge word generation 265 The challenger C generates a challenge word: R. It is 266 preferred that the word R is a one-time word and 267 usually generated from a random number generator. 269 3.2.1.2. Sending the challenge word 271 The challenger C sends the word R to the responder V. 273 3.2.2. Responder side 275 3.2.2.1. Common key generation 277 The responder V generates a common key: k_[CV] with the 278 challenger C using V's private ID: X_[V] and C's public 279 ID; 281 k_[CV] = X_[V](ID_[C]). 283 3.2.2.2. Challenge word encryption 285 Receiving the challenge word R, the responder V 286 encrypts R with the common key; 288 R' = E_{k_[CV]}(R). 290 3.2.2.3. Challenge response 292 The responder V returns the response R' back to the 293 challenger C. 295 3.2.3. Challenger side 297 3.2.3.1. Common key generation 299 The challenger C generates a common key: k_[CV] using 300 V's private ID: X_[C] and V's public ID; 302 k_[CV] = X_[C](ID_[V]). 304 3.2.3.2. Response decryption 306 Receiving the response, the challenger C decrypts the 307 response with the common key; 309 R'' = D_{k_[CV]}(R'). 311 3.2.3.3 Comparison 313 The challenger C compares R'' with R. If R'' = R, the 314 authentication is acknowledged. Otherwise the 315 authentication is denied. 317 3.3. Mutual Authentication 319 We can do mutual authentication using the entity authentication 320 protocol in duplicate. It is, however, possible to save 321 communicational cost by dealing with the duplicate protocols as a 322 whole. We exhibit such a protocol in this section. We assume that an 323 entity A with ID_[A] and an entity B with ID_[B] mutually 324 authenticate and that both entities have already known each public 325 ID. 327 3.3.1. Entity A side 329 3.3.1.1. Common key generation 331 The entity A generates a common key: k_[AB]; 332 k_[AB] = X_[A](ID_[B]). 334 3.3.1.2. Challenge word generation 336 The entity A generates a challenge word: R_[A]. It is 337 preferred that R_[A] is a random number. 339 3.3.1.3. Sending the challenge word 341 The entity A sends the word R_[A] to the entity B. 343 3.3.2. Entity B side 345 3.3.2.1. Common key generation 347 The entity B generates a common key: k_[AB]; 349 k_[AB] = X_[B](ID_[A]). 351 3.3.2.2. Challenge word encryption 353 Receiving the word R_[A], the entity B encrypts R_[A] 354 with the common key k_[AB]; 356 R'_[A] = E_{k_[AB]}(R_[A]). 358 3.3.2.3. Challenge word generation 360 The entity B also generates a challenge word: R_[B]. It 361 is preferred that R_[B] is a random number. 363 3.3.2.4. Sending the challenge and response word 365 The entity B sends the word R'_[A] and R_[B] to the 366 entity A; 368 R'_[A]aR_[B]. 370 3.3.3. Entity A side 372 3.3.3.1. Response decryption 374 Receiving the response R'_[A], the entity A decrypts it 375 with the common key; 377 R''_[A] = D_{k_[AB]}(R'_[A]). 379 3.3.3.2. Comparison 381 The entity A compares R''_[A] with R_[A]. 382 If R''_[A]=R_[A], the authentication of A to B is 383 acknowledged. Otherwise the authentication is a denied. 385 3.3.3.3. Challenge word encryption 387 The entity A encrypts the challenge word R_[B] with the 388 common key; 390 R'_[B] = E_{k_[AB]}(R_[B]). 392 3.3.3.4 Sending the response word 394 The entity A sends the word R'_[B] to the entity B. 396 3.3.4. Entity B side 398 3.3.4.1. Response decryption 400 Receiving the response R'_[B], the entity B decrypts it 401 with the common key; 403 R''_[B] = D_{k_[AB]}(R'_[B]). 405 3.3.4.2. Comparison 407 The entity B compares R''_[B] with R_[B]. 408 If R''_[B]=R_[B], authentication of B to A is 409 acknowledged. Otherwise the authentication is a denied. 411 3.4. Message Authentication 413 It is possible for a receiver to authenticate a message using key 414 sharing based on KPS. Message authentication in this memo means that 415 a receiver can confirm that a message is not falsified and that the 416 identification of its sender is correct. We introduce a message 417 authentication protocol in the following. It is assumed that a 418 sender A sends a message M to a receiver B and that the sender A has 419 already known the receiver B's public ID: ID_[B]. One of remarkable 420 features of our protocol is the fact that it is not interactive. 422 3.4.1. Sender side 424 3.4.1.1. Common key generation 426 The sender A generates a common key: k_[AB] from his 427 private ID and the receiver's public ID in the 428 following, 430 k_[AB] = X_[A](ID_[B]). 432 3.4.1.2. Message hashing 434 The sender A hashes a message M and the result is 436 H(M), 438 where H is a predefined hash function. 440 3.4.1.3. MAC generation 442 Message authentication code (MAC) is generated from the 443 hash value and the common key; 445 MAC = E_{k_[AB]}(H(M)). 447 3.4.1.4. Message with MAC sending 449 The sender A sends his own public ID, the message and 450 the corresponding MAC: 452 ID_[A]aMaMAC, 454 to the receiver B. 456 3.4.2. Receiver side 458 3.4.2.1. Common key generation 460 Receiving the message with MAC, the receiver B extracts 461 the sender's public ID: ID_[A] from it. Then he 462 generates the common key from the public ID and his own 463 private ID; 465 k_[AB] = X_[B](ID_[A]). 467 3.4.2.2. Message hashing 469 The receiver B separates the message: M' itself from 470 the message with MAC and then hashes the M'; 472 H(M') 474 3.4.2.3. MAC decryption 476 The receiver B decrypts the MAC with the common key; 478 H(M)' = D_{k_[AB]}(MAC). 480 3.4.2.4. Comparison 482 The receiver B compares the hashed message H(M') with 483 the decrypted MAC H(M)'. If H(M')=H(M)', the 484 authentication is acknowledged. Otherwise the 485 authentication is denied. 487 3.5. Digital Signature 489 In KPS, all related common keys have been already pre-distributed 490 into each private ID. This feature enables us to construct some 491 digital signature schemes. We introduce a digital signature scheme 492 based on KPS using a one-way homomorphism in this section. The 493 following signature scheme is an ID-based signature scheme and has 494 no public key. Any entities with their own private ID can, however, 495 authenticate any signature non-interactively. We assume that a 496 signer A with ID_[A] signs a message M and a verifier B 497 authenticates the message M of the signer A. 499 3.5.1. Signer side 501 3.5.1.1. Signing 503 The signer A signs the message M with his own private 504 ID using a keyed one-way homomorphism: F; 506 Sign_[M,A]( ) = F_{M}(X_[A]( )) 508 where the algebraic structure of X_[A] is succeeded 509 into Sign_[M,A] by the homomorphism. However, the 510 private ID itself cannot be derived from the signature 511 by one-wayness of F. 513 3.5.1.2. Message sending or opening 515 The signer A opens or sends the message, his public ID 516 and the signature: 518 ID_[A]aMaSign_[M,A], 520 to the verifier B. 522 3.5.2. Verifier side 524 3.5.2.1. Authenticator_1 generation 526 Receiving the message and the signer's public ID, the 527 verifier B generates an authenticator_1: Auth_1, using 528 his own private ID X_[B]; 530 Auth_1 = F_{M}(X_[B](ID_[A])), 531 = F_{M}(k_[AB]). 533 3.5.2.2. Authenticator_2 generation 535 The verifier B generates an authenticator_2: Auth_2, 536 from the signature itself and his public ID ID_[B]; 538 Auth_2 = Sign_[M,A](ID_[B]), 539 = F_{M}(X_[A](ID_[B])), 540 = F_{M}(k_[AB]). 542 3.5.2.3. Comparison 544 The verifier B compares Auth_1 with Auth_2. If 545 Auth_1=Auth_2, the authentication is acknowledged. 546 Otherwise the authentication is denied. 548 3.6. Key Recovery 550 Strictly speaking, key recovery[4] may not be protocol. 551 Nevertheless, it is a topic which cannot be neglected in the key 552 management system. In this section, we introduce a key recovery 553 scheme based on KPS[5]. 555 Although many Key Recovery Systems have been 556 proposed recently, our KPS is particularly strong in the areas of 557 Key Recovery System (KRS) with Data Recovery Field (DRF)[6]. 559 In our scheme, PAGS further plays a role of Key Recovery Agent (KRA) 560 and DRF is given by the encrypted session key itself: 562 E_{k_[AB]}(k), 564 in 3.1. (Confidential Communication). 566 We then exhibit a key recovery protocol between Data Recovery Agency 567 (DRA) and PAGS(KRA). It is assumed that the DRA has already got the 568 ciphertext including the encrypted session key: 570 ID_[A]aE_{k_[AB]}(k)aC, 572 between the entity A and B in 3.1. (Confidential Communication) and 573 the DRA knows also receiver's public ID, ID_B. 575 3.6.1. DRA side 577 3.6.1.1. DRF extraction 579 DRA extracts the encrypted session key as DRF from the 580 ciphertext to be recovered; 582 DRF = E_{k_[AB]}(k). 584 3.6.1.2. Key Recovery Application 586 DRA sends an application for the key recovery with the 587 sender's public ID, the receiver's public ID and the 588 DRF to PAGS; 590 ID_[A]aID_[B]aDRF. 591 3.6.2. PAGS side 593 3.6.2.1. Key Recovery Authentication 595 PAGS authenticates the application. If it is 596 acceptable, PAGS takes the next step. Otherwise PAGS 597 notifies DRA of the result. 599 3.6.2.2. Common key generation 601 PAGS generates the common key from the center-algorithm 602 using the two public IDs; 604 k_[AB] = G(ID_[A],ID_[B]). 606 3.6.2.3. Session key recovery 608 PAGS decrypts the DRF with the common key; 610 k = D_{k_[AB]}(DRF). 612 3.6.2.4. Session key return back 614 PAGS returns the session key k back to DRA. 616 3.6.3. DRA side 618 3.6.3.1. Message recovery 620 Receiving the session key k, DRA decrypts the 621 ciphertext with it; 623 M = D_{k}(C). 625 4. Security Considerations and One Implementation of KPS 627 The security of the above proposed protocols mainly depends on the 628 security of KPS, though the security of cryptographic encryption 629 algorithm, hash function, and random generator is also not 630 negligible. There have been, however, many implementations proposed 631 on KPS and the security of KPS depends on its implementation. We 632 then recommend linear scheme KPS as the implementation of KPS. This 633 KPS is based on information-theoretic security and has prominent 634 simplicity and efficiency. We then briefly introduce a linear scheme 635 KPS; 637 1. Center-algorithm 639 The center-algorithm is represented by 641 G_[i,j], 643 where G is a (m,m) 2nd rank symmetric covariant tensor 644 and its component is a random number belonging to GF(q) 645 where q is a prime number. 647 2. Effective ID 649 ID, for example ID_[A], is transferred to 650 "effective ID": x_[A]^[i]; 652 x_[A]^[i] = f^[i](ID_[A]), 654 where f is a pre-defined one-way function. The 655 effective ID is a contra-variant vector and its 656 component also belongs to GF(q). 658 3. Secret algorithm 660 The secret algorithm is generated from the center 661 algorithm and the corresponding ID, for example, the 662 entity A's secret-algorithm is given by, 664 X_[A,i] = G_[i,j]f^[j](ID_[A]) mod q, 665 = G_[i,j]x_[A]^[j] mod q, 667 where Einstein's contraction is done on the overlapping 668 index j. The secret-algorithm is then a covariant 669 vector and its component also belongs to GF(q). 671 4. Common key 673 Any common key is generated from secret-algorithm and 674 ID, for example, the generation of the common key 675 between A and B is as follows; 677 k_[AB] = X_[A,i]f^[i](ID_[B]) mod q (A side), 678 = X_[B,j]f^[j](ID_[A]) mod q (B side), 679 = G_[i,j]x_[A]^[j]x_[B]^[i] mod q. 681 In this way, the main calculation of the linear scheme KPS is 682 simple. Moreover, an attacker needs at least m different secret 683 algorithms to break the system completely. Such features suggest 684 that the linear scheme KPS is a pragmatic one. We, however, 685 recommend that each secret algorithm is stored in each tamper 686 resistant module like an IC card. 688 As one example of one-way homomorphism used in the digital 689 signature, a homomorphism based on discrete log problem is proposed; 691 1. Signature 693 Signature is given by, 695 Sig_[M,A,i] = h^{X_[A,i]} mod p, 697 where p is a large prime which satisfies 699 q|p-1, 701 and h is a specific value determined with the message M 702 and the signer's ID_[A]: 704 h = h(M, ID_[A]), 706 where the order of the cyclic group generated by h on 707 modulo p must be sufficient large. 709 2. Authenticator_2 711 Authenticator_1 is easily calculated in this 712 implementation. Authentictor_2 is calculated in the 713 following way; 715 Auth_2= prod_[i=1]^[i=m] 716 Sig_[M,A,i]^{f^[i](ID_[B])}mod p, 718 = prod_[i=1]^[i=m] 719 Sig_[M,A,i]^{x_[B]^[i]} mod p. 721 where "prod" means that the following terms are 722 multiplied from i=1 to i=m. 724 The security of the signature scheme depends on both computational 725 complex and information-theoretic security. 727 Acknowledgements 729 One of the authors thanks to Prof. Imai and Imailab members for 730 useful advises on some topics. 732 References 734 1. A. Shamir, "Identity-Based Cryptosystems and Signature Schemes," 735 Advances in Cryptology: Proc. of CRYPTO'84, Springer LNCS 196, 736 pp.47-53, 1985 738 2. T. Matsumoto and H. Imai, "On the KEY PREDISTRIBUTION SYSTEM: 739 A Practical Solution to the Key Distribution Problem," Advances 740 in Cryptology: Proc. of CRYPTO'87, Springer LNCS 293, pp.185-193, 741 1987. 743 3. T. Matsumoto and H. Imai, "Applying the key predistribution 744 systems to electronic mails and signatures," Proc. of SITA'87, 745 pp.101-106, 1987. 747 4. D. E. Denning and D. K. Branstad, "A Taxonomy for Key Recovery 748 Encryption System,"(URL:http://www.cosc.georgetown.edu/~denning 749 /crypto/taxonom.html),May 11, 1997. 751 D. E. Denning and D. K. Branstad, "A Taxonomy for Key Escrow 752 Encryption System," Communication of the ACM, Vol.39, No,3, 753 pp.34-40, March 1996. 755 5. T. Kubo, "Key Pre-distribution System as a Key Recovery system," 756 Proc. of PKS'97, April 1997. 758 6. T. Nishioka, K. Matsuura, Y. Zheng, and H. Imai, "A Proposal for 759 Authenticated Key Recovery System," Proc. JW-ISC'97,pp.189-196, 760 October 1997 762 Authors' Address 764 Tsuyoshi Nishioka, Ph.D. 765 IT Laboratory 767 Taka Kubo, Ph.D. 768 Information & Communication Business Division 770 ADVANCE Co., Ltd. 771 5-7, Nihonbashi-Kobunacho 772 Chuo-ku, Tokyo 103-8354 Japan 774 Phone: ++81 3 3667 6148 775 Fax: ++81 3 3664 4387 776 E-mail: nishioka@advance.co.jp, kubo@advance.co.jp 777 WWW: http://www.advance.co.jp 779 INTERNET DRAFT EXPIRES JAN 1999 INTERNET DRAFT