Encryption Schemes from Bilinear Maps

Author: Eu-Jin Goh.


Encryption schemes are designed to provide data confidentiality and are a fundamental cryptographic primitive with many applications in higher-level protocols. Groups with a bilinear map allow us to build public key encryption schemes with new properties that are otherwise difficult to obtain using groups without a bilinear map. We support our thesis by presenting two encryption schemes based on bilinear groups; the first is a partial solution to the open problem on doubly homomorphic encryption proposed by Rivest et al. in 1978, and the second is the most efficient hierarchical identity based encryption scheme to date.

Our main result deals with homomorphic encryption. Using bilinear groups, we developed a homomorphic encryption scheme based on the subgroup decision complexity assumption; this encryption scheme is additively homomorphic and also possesses an additional limited (single) multiplicative homomorphism. Even with such limitations, our encryption scheme allows us to evaluate on encrypted inputs useful formulas such as polynomials of total degree at most two and dot products. Our encryption scheme also lends itself naturally to a secure function evaluation protocol for computing 2-DNFs, which can be used to improve private information retrieval protocols.

Our second result deals with hierarchical identity based encryption (HIBE), a generalization of identity based encryption. In previous constructions for HIBE, the length of ciphertexts, as well as the time needed for decryption, grows linearly with the depth of the hierarchy. Our HIBE system has ciphertext size, as well as decryption cost, that is independent of the hierarchy depth. The principal applications for HIBE are forward secure encryption and public key broadcast encryption. Using our HIBE system instead of existing HIBE systems in these two applications results in substantial reductions in the ciphertext size of both these applications.

Stanford University Computer Science Ph.D. Thesis 2007.
BibTex: bib

Full Paper:

Ph.D. Thesis Defense, May 2007

Related Papers: