The idea of an Identity-based Encryption (IBE) Scheme was proposed by Shamir in 1984 as an alternative to public-key encryption, to eliminate the need for Public-Key Infrastructure (PKI) and expensive certification of public-keys. Informally, an Identity-based Encryption Scheme allows the use of an arbitrary string as the public-key. For instance, if Bob wants to send Alice encrypted e-mail, he does not need to know Alice's public-key (assuming Alice is smart enough to use Identity-based Encryption) -- he just needs to know Alice's email address, which he knows anyway. Even though the idea of an Identity-based encryption scheme has been around for more than two decades, we did not know how to construct an IBE scheme until the work of Boneh et al.[3,2].

Identity-based Encryption is a very powerful cryptographic object. In this work, we seek to determine how IBE can be used to construct various strong cryptographic primitives. We are also interested in the complexity of constructing an IBE scheme from general assumptions -- that is, starting from a better-understood assumption, such as the existence of a semantically-secure encryption scheme.

Progress

• We define a new notion of security for encryption schemes -- strong non-malleability. Intuitively, this says that an adversary, given a ciphertext, cannot change it into the ciphertext of a related message {\em under a possibly different public-key}. This is a strengthening of the standard notion of non-malleability of encryption schemes, and is potentially useful in some real-world situations. We construct efficient strongly non-malleable encryption schemes starting from the Identity-based Encryption scheme of Waters [4].
• We construct Non-Interactive Zero Knowledge proofs for all languages in NP, assuming the existence of an Identity-Based Encryption scheme, provided that it is easy to prove the validity of a ciphertext in Non-Interactive ZK (This is possible for all known IBE schemes). NIZK protocols (for all NP languages) are known under the assumption that there exist trapdoor permutations. Our result gives a new way of constructing NIZK schemes under an incomparable assumption.

Future Work

We believe that Identity-based Encryption is a powerful new cryptographic object, and could potentially be used as a tool to construct strong cryptographic primitives. As a sample, the work of [CHK] shows that Identity-based Encryption can be used to construct very efficient CCA-secure encryption schemes.

References

[1] Ran Canetti, Shai Halevi and Jonathan Katz, Chosen-ciphertext security from Identity-based Encryption, EUROCRYPT 2004.

[2] Dan Boneh and Xavier Boyen, Secure Identity-Based Encryption Without Random Oracles, CRYPTO 2004.

[3] Dan Boneh and Matthew Franklin, Identity-based Encryption from the Weil Pairing, SIAM Journal of Computing, Vol. 32, No. 3, 2003.

[4] Brent Waters, Efficient Identity-Based Encryption Without Random Oracles, EUROCRYPT 2005.