09/07/05

The most popular system in use today is the public-key encryption.  However, it appears that this system will soon be replaced by identity-based encryption (IBE).   

The current public-key encryption system relies on long, randomly generated keys which must be linked to identities using digitally signed documents called certificates.  Managing the certificates, and the multiple transmissions of the certificates required to encrypt a message, has made the system very cumbersome.  Because of this, in 1984 Adi Shamir, one of the developers of the Rivest-Shamir-Adleman (RSA) Algorithm, proposed a public key encryption system in which the public key can be an arbitrary string.  He believed that this new idea of IBE would simplify certificate management by eliminating the need for certificates and Certification Authorities required under the current public-key systems.  Because his idea was so revolutionary, it was not until 2000 that Dr. Dan Boneh of Stanford and Dr. Matt Franklin of UC-Davis figured out the mathematics used in their Boneh-Franklin IBE Algorithm, the first secure and practical IBE system.

IBE uses well-known identifiers, such as e-mail addresses, as public keys.  This eliminates the need for the certificates and Certification Authorities mentioned above.  Below is an example taken from Voltage’s website which shows the difference between an RSA and IBE public key:

The following is a RSA public key. A certificate is required to bind this key to an identity (i.e. to state that this key    belongs to bob@b.com).

     Public exponent:

     0x10001

     Modulus:
     135066410865995223349603216278805969938881475605667027524485143851526510604859

     533833940287150571909441798207282164471551373680419703964191743046496589274256

     239341020864383202110372958725762358509643110564073501508187510676594629205563

      685529475213500852879416377328533906109750544334999811150056977236890927563                   

             In contrast, this is an IBE public key. No certificate is required because the key is the identity.

                 Name = bob@b.com

             IBE is based on a function called a "bilinear map" which has the following property:

     Pair( a • X, b • Y ) = Pair( b • X, a • Y )

The IBE algorithm is composed of four steps: setup, encrypt, key generation, and decrypt.

     During setup, a server picks an elliptic curve and uses a random number generator to select a secret s and a point P on the curve.  Point P and the product of s and P are then distributed to the users on the server.

     To encrypt a message, the sender enters in the receiving e-mail address and picks a random r.  The system then uses this to calculate a key k based on the following function:

     k = Pair( r • user ID , s • P)

     The encrypted message is then sent along with k and the product of r and P.

     To receive a personal key, the receiver must connect to the server.  The server identifies the user, calculates the product of s and their user ID, and returns this value to the receiver as their personal key.

     To decrypt the message the receiver can calculate k though the following function:

     k = Pair( s • user ID , r • P )

     Since the value of k calculated by the end user has the same value as the k used by the sender, the receiver can use k to unlock the encrypted message. 

     In addition to being streamlined, IBE also offers additional benefits.  Since the encrypted message can only be opened by the recipient, the message is very secure.  The system also relies on both the master key, known only to the server, and the private key, known only to the user.  Since all of the information is not stored in one location, it is much more difficult to steal or crack the keys.  The IBE process is largely hidden from the user and seems very intuitive.  Because of this, it can reduce costs to train users on the more complicated certificate-based systems.  IBE also gives organizations flexibility to manage their keys.  If someone leaves the organization, their key will immediately and automatically become void if their user ID is erased from the system.  This eliminates the separate step of erasing the users’ key from the server and eliminates the need to archive previous keys.

      While public-key encryption is the current de facto standard used by most organizations, its days appear to be numbered.  Because of the many advantages associated with identity-based encryption, it is largely considered to be the future of cryptology.