[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
Network Working Group                         T. Nishioka and T. Kubo
INTERNET DRAFT                                Info. and Comm. Biz. Div.
Category: Informational                       ADVANCE Co., Ltd.

                                                              June 1998

                The ID-based Key Management System (IDKMS)

Status of This Memo

This document is an Internet-Draft.  Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its
areas, and its working groups.  Note that other groups may also
distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other
documents at any time.  It is inappropriate to use Internet-
Drafts as reference material or to cite them other than as
"work in progress."

To view the entire list of current Internet-Drafts, please check
the "1id-abstracts.txt" listing contained in the Internet-Drafts
Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net
(Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au
(Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu
(US West Coast).

Distribution of this document is unlimited.


   This informational document describes some cryptographic protocols on an
   ID-based system called Key Predistribution System (KPS).

Table of Contents

   1. Introduction and preliminary remarks............................2
   2. Setup...........................................................3
        2.1. PAGS Setup...............................................3
        2.2. User Setup...............................................3
   3. Cryptographic Protocols.........................................4
        3.1. Confidential Communication...............................4
        3.2. Entity Authentication....................................5
        3.3. Mutual Authentication....................................6
        3.4. Message Authentication...................................8
        3.5. Digital Signature........................................9
        3.6. Key Recovery............................................10
   4. Security Considerations and One Implementation of KPS..........12
   Authors' Address..................................................14

Nishioka & Kubo                 Informational                  [Page 1]

                The ID-based Key Management System (IDKMS)    July 1998

1. Introduction and preliminary remarks

   Cryptography is one of the fundamental tools to make the Internet a
   more secure network.

   It guards the Internet against various malicious attacks like
   eavesdropping, masquerading, falsifying, and so on. Although
   cryptography has powerful abilities in this area, it has also an
   Achilles' heel in key management. If key management were insecure,
   any system using cryptography would be totally defenseless, no
   matter how strong the cryptography is. The construction of a public
   -key infrastructure is one important point of the key management.

   In this memo we propose a different type of key management, which is
   based on an ID-based cryptography[1] called Key Predistribution
   System (KPS)[2,3].

   The simplest KPS consists of one center and unspecified entities
   (users). It is assumed that each unspecified entity has his own
   broad-sense "name" represented by an ID, which may be something
   like, for example, a mail-address in the internet. The center called
   "KPS center" generates a center-algorithm represented by G. The
   center-algorithm G is confidential and nobody except the KPS center
   must know its content.

   The algorithm G outputs a secret algorithm if an ID is input into G.
   The secret algorithm is confidentially and securely distributed to
   an entity having the corresponding ID. The secret algorithm has the
   capability to generate a common key. If the owner inputs an ID into
   his secret algorithm, the secret algorithm outputs a common key
   between the owner and the entity having the corresponding ID.
   Therefore any common key has already been pre-distributed to an
   entity when the entity received his own secret algorithm.

   Using the above KPS, we introduce some interesting cryptographic
   protocols on the internet. The following protocols are mainly
   discussed on the application layer.

   It is expected that the reader is familiar with the basics of
   cryptography and linear algebra.

   Due to the ASCII representation of this memo, the following style is
   chosen for mathematical purposes:

   - a^{b} means the exponentiation of a to the power of b, which is
     always used within a modulo context.

   - a^[b] means a with an upper index of b.

   - a_[b] means a with a lower index or subscription of b.

   - a_[b,c] means a with lower indices or subscription of b and c.

   - a=b means equality or congruency within a modulo context.

   - E_{k}(M) means encryption of message M by key k.

   - D_{k}(C) means decryption of cipher C by key k.

Nishioka & Kubo                 Informational                  [Page 2]

                The ID-based Key Management System (IDKMS)    July 1998

2. Setup

2.1. PAGS Set up

   "Private Algorithm Generation System (PAGS)" represents both the KPS
   center and its center-algorithm: G( , ) for the internet.

   PAGS first generates the center-algorithm, G and stores it secretly.

2.2. User Set up

   An entity A applies for his own private ID to PAGS, where a private
   ID represents the secret-algorithm for the internet.

        1. The entity A proposes his own "public ID": ID_[A] to PAGS,
           where public ID means usual the ID for the internet in
           contrast to the private ID.

        2. Receiving A's application and his public ID, PAGS
           authenticates A and the correctness of ID_[A].

        3. If the application has no problem, PAGS generates the
           private ID: X_[A] using the center-algorithm G;

                X_[A]( )= G(ID_[A], )=G( ,ID_[A]).

           where G having two inputs is symmetric mapping the two
           inputs. If the application has a problem, PAGS notifies the
           applicant of the result and does not generate the
           corresponding private ID.

        4. PAGS confidentially distributes the private ID, X_[A] to the
           entity A through a more secure channel than the internet.

        5. Receiving the private ID, the entity A stores the private
           ID: X_[A] secretly.

   The entity A is able to share each different common key with any
   other entity B non-interactively using his own private ID, X_[A].
   The entity A inputs B's public ID: ID_[B] into X_[A] and then A gets
   the common key: k_[AB];

        k_[AB] = X_[A](ID_[B]) = G(ID_[A],ID_[B]).

   Independently and in the same way, the entity B can generate the
   common key with his private ID: X_[B];

                k_[BA] = X_[B](ID_[A]) = G(ID_[B],ID_[A]),
                                       = G(ID_[A],ID_[B]),
                                       = k_[AB].

Nishioka & Kubo                 Informational                  [Page 3]

                The ID-based Key Management System (IDKMS)    July 1998

3. Cryptographic Protocols

   Some interesting cryptographic protocols are presented in this
   section. They are based on some powerful features of KPS.

3.1. Confidential Communication

   We deal with confidential communication by common-key cryptography.
   It is critical to think about how to distribute a session key: k to
   a correct receiver B, where the session key is cryptographic and
   used to encrypt the main message: M. The ciphertext C is given by,


   We exhibit the key sharing between a sender A and a receiver B and
   the confidential communication protocol in the following;

   3.1.1. Sender side Common key generation

                The sender A generates a common key using his private
                ID and B's public ID;

                        k_[AB] = X_[A](ID_[B]). Session key generation

                The sender A generates a session key: k, using some
                appropriate random generator. Message encryption

                Message M is encrypted with the session key into
                ciphertext C;

                        C = E_{k}(M). Session key encryption

                The session key is encrypted with the common key;

                        E_{k_[AB]}(k). Sending ciphertext

                The sender A sends the following data;


                to the receiver B where the symbol "a"means

                Note: The sender's public ID, ID_[A] needs not to be
                sent explicitly if the receiver recovers ID_[A] from
                other protocols.

Nishioka & Kubo                 Informational                  [Page 4]

                The ID-based Key Management System (IDKMS)    July 1998

   3.1.2. Receiver side Extraction of public ID

                Receiving the ciphered data, the receiver B extracts
                the sender's public ID:


                from them. Common key generation

                The sender B generates a common key using his private
                ID and A's public ID;

                        k_[AB] = X_[B](ID_[A]). Session key decryption

                The session key is decrypted with the common key;

                        k = D_{k_[AB]}(E_{k_[AB]}(k)). Message decryption

                The Message is decrypted with the session key;

                        M = D_{k}(C).

3.2. Entity Authentication

   Owing to KPS, any two entities share each own common key non
   -interactively. Using such a feature, a challenger C can
   authenticate a responder V. We introduce an authentication protocol
   in the following. It is assumed that the challenger C and the
   responder V have already known each public ID: ID_[C], ID_[V].

   3.2.1. Challenger side Challenge word generation

                The challenger C generates a challenge word: R. It is
                preferred that the word R is a one-time word and
                usually generated from a random number generator. Sending the challenge word

                The challenger C sends the word R to the responder V.

Nishioka & Kubo                 Informational                  [Page 5]

                The ID-based Key Management System (IDKMS)    July 1998

   3.2.2. Responder side Common key generation

                The responder V generates a common key: k_[CV] with the
                challenger C using V's private ID: X_[V] and C's public

                        k_[CV] = X_[V](ID_[C]). Challenge word encryption

                Receiving the challenge word R, the responder V
                encrypts R with the common key;

                        R' = E_{k_[CV]}(R). Challenge response

                The responder V returns the response R' back to the
                challenger C.

   3.2.3. Challenger side Common key generation

                The challenger C generates a common key: k_[CV] using
                V's private ID: X_[C] and V's public ID;

                        k_[CV] = X_[C](ID_[V]). Response decryption

                Receiving the response, the challenger C decrypts the
                response with the common key;

                        R'' = D_{k_[CV]}(R'). Comparison

                The challenger C compares R'' with R. If R'' = R, the
                authentication is acknowledged. Otherwise the
                authentication is denied.

3.3. Mutual Authentication

   We can do mutual authentication using the entity authentication
   protocol in duplicate. It is, however, possible to save
   communicational cost by dealing with the duplicate protocols as a
   whole. We exhibit such a protocol in this section. We assume that an
   entity A with ID_[A] and an entity B with ID_[B] mutually
   authenticate and that both entities have already known each public

Nishioka & Kubo                 Informational                  [Page 6]

                The ID-based Key Management System (IDKMS)    July 1998

   3.3.1. Entity A side Common key generation

                The entity A generates a common key: k_[AB];
                        k_[AB] = X_[A](ID_[B]). Challenge word generation

                The entity A generates a challenge word: R_[A]. It is
                preferred that R_[A] is a random number. Sending the challenge word

                The entity A sends the word R_[A] to the entity B.

   3.3.2. Entity B side Common key generation

                The entity B generates a common key: k_[AB];

                        k_[AB] = X_[B](ID_[A]). Challenge word encryption

                Receiving the word R_[A], the entity B encrypts R_[A]
                with the common key k_[AB];

                        R'_[A] = E_{k_[AB]}(R_[A]). Challenge word generation

                The entity B also generates a challenge word: R_[B]. It
                is preferred that R_[B] is a random number. Sending the challenge and response word

                The entity B sends the word R'_[A] and R_[B] to the
                entity A;


   3.3.3. Entity A side Response decryption

                Receiving the response R'_[A], the entity A decrypts it
                with the common key;

                        R''_[A] = D_{k_[AB]}(R'_[A]). Comparison

                The entity A compares R''_[A] with R_[A].
                If R''_[A]=R_[A], the authentication of A to B is
                acknowledged. Otherwise the authentication is a denied.

Nishioka & Kubo                 Informational                  [Page 7]

                The ID-based Key Management System (IDKMS)    July 1998
 Challenge word encryption

                The entity A encrypts the challenge word R_[B] with the
                common key;

                        R'_[B] = E_{k_[AB]}(R_[B]). Sending the response word

                The entity A sends the word R'_[B] to the entity B.

   3.3.4. Entity B side Response decryption

                Receiving the response R'_[B], the entity B decrypts it
                with the common key;

                        R''_[B] = D_{k_[AB]}(R'_[B]). Comparison

                The entity B compares R''_[B] with R_[B].
                If R''_[B]=R_[B], authentication of B to A is
                acknowledged. Otherwise the authentication is a denied.

3.4. Message Authentication

   It is possible for a receiver to authenticate a message using key
   sharing based on KPS. Message authentication in this memo means that
   a receiver can confirm that a message is not falsified and that the
   identification of its sender is correct. We introduce a message
   authentication protocol in the following. It is assumed that a
   sender A sends a message M to a receiver B and that the sender A has
   already known the receiver B's public ID: ID_[B]. One of remarkable
   features of our protocol is the fact that it is not interactive.

   3.4.1. Sender side Common key generation

                The sender A generates a common key: k_[AB] from his
                private ID and the receiver's public ID in the

                        k_[AB] = X_[A](ID_[B]). Message hashing

                The sender A hashes a message M and the result is


                where H is a predefined hash function.

Nishioka & Kubo                 Informational                  [Page 8]

                The ID-based Key Management System (IDKMS)    July 1998
 MAC generation

                Message authentication code (MAC) is generated from the
                hash value and the common key;

                        MAC = E_{k_[AB]}(H(M)). Message with MAC sending

                The sender A sends his own public ID, the message and
                the corresponding MAC:


                to the receiver B.

   3.4.2. Receiver side Common key generation

                Receiving the message with MAC, the receiver B extracts
                the sender's public ID: ID_[A] from it. Then he
                generates the common key from the public ID and his own
                private ID;

                        k_[AB] = X_[B](ID_[A]). Message hashing

                The receiver B separates the message: M' itself from
                the message with MAC and then hashes the M';

                        H(M') MAC decryption

                The receiver B decrypts the MAC with the common key;

                        H(M)' = D_{k_[AB]}(MAC). Comparison

                The receiver B compares the hashed message H(M') with
                the decrypted MAC H(M)'. If H(M')=H(M)', the
                authentication is acknowledged. Otherwise the
                authentication is denied.

3.5. Digital Signature

   In KPS, all related common keys have been already pre-distributed
   into each private ID. This feature enables us to construct some
   digital signature schemes. We introduce a digital signature scheme
   based on KPS using a one-way homomorphism in this section. The
   following signature scheme is an ID-based signature scheme and has
   no public key. Any entities with their own private ID can, however,
   authenticate any signature non-interactively. We assume that a
   signer A with ID_[A] signs a message M and a verifier B
   authenticates the message M of the signer A.

Nishioka & Kubo                 Informational                  [Page 9]

                The ID-based Key Management System (IDKMS)    July 1998

   3.5.1. Signer side Signing

                The signer A signs the message M with his own private
                ID using a keyed one-way homomorphism: F;

                        Sign_[M,A]( ) = F_{M}(X_[A]( ))

                where the algebraic structure of X_[A] is succeeded
                into Sign_[M,A] by the homomorphism. However, the
                private ID itself cannot be derived from the signature
                by one-wayness of F. Message sending or opening

                The signer A opens or sends the message, his public ID
                and the signature:


                to the verifier B.

   3.5.2. Verifier side Authenticator_1 generation

                Receiving the message and the signer's public ID, the
                verifier B generates an authenticator_1: Auth_1, using
                his own private ID X_[B];

                        Auth_1 = F_{M}(X_[B](ID_[A])),
                               = F_{M}(k_[AB]). Authenticator_2 generation

                The verifier B generates an authenticator_2: Auth_2,
                from the signature itself and his public ID ID_[B];

                        Auth_2 = Sign_[M,A](ID_[B]),
                               = F_{M}(X_[A](ID_[B])),
                               = F_{M}(k_[AB]). Comparison

                The verifier B compares Auth_1 with Auth_2. If
                Auth_1=Auth_2, the authentication is acknowledged.
                Otherwise the authentication is denied.

3.6. Key Recovery

   Strictly speaking, key recovery[4] may not be protocol.
   Nevertheless, it is a topic which cannot be neglected in the key
   management system. In this section, we introduce a key recovery
   scheme based on KPS[5].

Nishioka & Kubo                 Informational                 [Page 10]

                The ID-based Key Management System (IDKMS)    July 1998

   Although many Key Recovery Systems have been
   proposed recently, our KPS is particularly strong in the areas of
   Key Recovery System (KRS) with Data Recovery Field (DRF)[6].

   In our scheme, PAGS further plays a role of Key Recovery Agent (KRA)
   and DRF is given by the encrypted session key itself:


   in 3.1. (Confidential Communication).

   We then exhibit a key recovery protocol between Data Recovery Agency
   (DRA) and PAGS(KRA). It is assumed that the DRA has already got the
   ciphertext including the encrypted session key:


   between the entity A and B in 3.1. (Confidential Communication) and
   the DRA knows also receiver's public ID, ID_B.

   3.6.1. DRA side  DRF extraction

                DRA extracts the encrypted session key as DRF from the
                ciphertext to be recovered;

                        DRF = E_{k_[AB]}(k). Key Recovery Application

                DRA sends an application for the key recovery with the
                sender's public ID, the receiver's public ID and the
                DRF to PAGS;

   3.6.2. PAGS side Key Recovery Authentication

                PAGS authenticates the application. If it is
                acceptable, PAGS takes the next step. Otherwise PAGS
                notifies DRA of the result. Common key generation

                PAGS generates the common key from the center-algorithm
                using the two public IDs;

                        k_[AB] = G(ID_[A],ID_[B]). Session key recovery

                PAGS decrypts the DRF with the common key;

                        k = D_{k_[AB]}(DRF).

Nishioka & Kubo                 Informational                 [Page 11]

                The ID-based Key Management System (IDKMS)    July 1998
 Session key return back

                PAGS returns the session key k back to DRA.

   3.6.3. DRA side Message recovery

                Receiving the session key k, DRA decrypts the
                ciphertext with it;

                        M = D_{k}(C).

4. Security Considerations and One Implementation of KPS

   The security of the above proposed protocols mainly depends on the
   security of KPS, though the security of cryptographic encryption
   algorithm, hash function, and random generator is also not
   negligible. There have been, however, many implementations proposed
   on KPS and the security of KPS depends on its implementation. We
   then recommend linear scheme KPS as the implementation of KPS. This
   KPS is based on information-theoretic security and has prominent
   simplicity and efficiency. We then briefly introduce a linear scheme

        1. Center-algorithm

                The center-algorithm is represented by


                where G is  a (m,m) 2nd rank symmetric covariant tensor
                and its component is a random number belonging to GF(q)
                where q is a prime number.

        2. Effective ID

                ID, for example ID_[A], is transferred to
                "effective ID": x_[A]^[i];

                        x_[A]^[i] = f^[i](ID_[A]),

                where f is a pre-defined one-way function. The
                effective ID is a contra-variant vector and its
                component also belongs to GF(q).

        3. Secret algorithm

                The secret algorithm is generated from the center
                algorithm and the corresponding ID, for example, the
                entity A's secret-algorithm is given by,

                        X_[A,i] = G_[i,j]f^[j](ID_[A]) mod q,
                                = G_[i,j]x_[A]^[j]     mod q,

                where Einstein's contraction is done on the overlapping
                index j. The secret-algorithm is then a covariant
                vector and its component also belongs to GF(q).

Nishioka & Kubo                 Informational                 [Page 12]

                The ID-based Key Management System (IDKMS)    July 1998

        4. Common key

                Any common key is generated from secret-algorithm and
                ID, for example, the generation of the common key
                between A and B is as follows;

                        k_[AB] = X_[A,i]f^[i](ID_[B]) mod q (A side),
                               = X_[B,j]f^[j](ID_[A]) mod q (B side),
                               = G_[i,j]x_[A]^[j]x_[B]^[i] mod q.

   In this way, the main calculation of the linear scheme KPS is
   simple. Moreover, an attacker needs at least m different secret
   algorithms to break the system completely. Such features suggest
   that the linear scheme KPS is a pragmatic one. We, however,
   recommend that each secret algorithm is stored in each tamper
   resistant module like an IC card.

   As one example of one-way homomorphism used in the digital
   signature, a homomorphism based on discrete log problem is proposed;

        1. Signature

                Signature is given by,

                        Sig_[M,A,i] = h^{X_[A,i]} mod p,

                where p is a large prime which satisfies


                and h is a specific value determined with the message M
                and the signer's ID_[A]:

                        h = h(M, ID_[A]),

                where the order of the cyclic group generated by h on
                modulo p must be sufficient large.

        2. Authenticator_2

                Authenticator_1 is easily calculated in this
                implementation. Authentictor_2 is calculated in the
                following way;

                        Auth_2= prod_[i=1]^[i=m]
                                    Sig_[M,A,i]^{f^[i](ID_[B])}mod p,

                              = prod_[i=1]^[i=m]
                                    Sig_[M,A,i]^{x_[B]^[i]} mod p.

                where "prod" means that the following terms are
                multiplied from i=1 to i=m.

   The security of the signature scheme depends on both computational
   complex and information-theoretic security.

Nishioka & Kubo                 Informational                 [Page 13]

                The ID-based Key Management System (IDKMS)    July 1998


   One of the authors thanks to Prof. Imai and Imailab members for
   useful advises on some topics.


   1. A. Shamir, "Identity-Based Cryptosystems and Signature Schemes,"
      Advances in Cryptology: Proc. of CRYPTO'84, Springer LNCS 196,
      pp.47-53, 1985

   2. T. Matsumoto and H. Imai, "On the KEY PREDISTRIBUTION SYSTEM:
      A Practical Solution to the Key Distribution Problem," Advances
      in Cryptology: Proc. of CRYPTO'87, Springer LNCS 293, pp.185-193,

   3. T. Matsumoto and H. Imai, "Applying the key predistribution
      systems to electronic mails and signatures," Proc. of SITA'87,
      pp.101-106, 1987.

   4. D. E. Denning and D. K. Branstad, "A Taxonomy for Key Recovery
      Encryption System,"(URL:http://www.cosc.georgetown.edu/~denning
      /crypto/taxonom.html),May 11, 1997.

      D. E. Denning and D. K. Branstad, "A Taxonomy for Key Escrow
      Encryption System," Communication of the ACM, Vol.39, No,3,
      pp.34-40, March 1996.

   5. T. Kubo, "Key Pre-distribution System as a Key Recovery system,"
      Proc. of PKS'97, April 1997.

   6. T. Nishioka, K. Matsuura, Y. Zheng, and H. Imai, "A Proposal for
      Authenticated Key Recovery System," Proc. JW-ISC'97,pp.189-196,
      October 1997

Authors' Address

        Tsuyoshi Nishioka, Ph.D.
        IT Laboratory

        Taka Kubo, Ph.D.
        Information & Communication Business Division

        ADVANCE Co., Ltd.
        5-7, Nihonbashi-Kobunacho
        Chuo-ku, Tokyo 103-8354 Japan

        Phone:  ++81 3 3667 6148
        Fax:    ++81 3 3664 4387
        E-mail: nishioka@advance.co.jp, kubo@advance.co.jp
        WWW:    http://www.advance.co.jp