Paper 2015/741

On Generic Constructions of Circularly-Secure, Leakage-Resilient Public-Key Encryption Schemes

Mohammad Hajiabadi, Bruce M. Kapron, and Venkatesh Srinivasan


Abstract. We propose generic constructions of public-key encryption schemes, satisfying key- dependent message (KDM) security for projections and different forms of key-leakage resilience, from CPA-secure private key encryption schemes with two main abstract properties: (1) additive homomorphism with respect to both messages and randomness, and (2) reproducibility, providing a means for reusing encryption randomness across independent secret keys. More precisely, our construction transforms a private-key scheme with the stated properties (and one more mild condition) into a public-key one, providing: - n-KDM-projection security, an extension of circular security, where the adversary may also ask for encryptions of negated secret key bits; – a (1-o(1)) resilience rate in the bounded-memory leakage model of Akavia et al. (TCC 2009); and – Auxiliary-input security against subexponentially-hard functions. We introduce homomorphic weak pseudorandom functions, a homomorphic version of the weak PRFs proposed by Naor and Reingold (FOCS ’95) and use them to realize our base encryption scheme. We obtain homomorphic weak PRFs under assumptions including subgroup indistinguishability (implied, in particular, by QR and DCR) and homomorphic hash-proof systems (HHPS). As corollaries of our results, we obtain (1) a projection-secure encryption scheme (as well as a scheme with a (1-o(1)) resilience rate) based solely on the HHPS assumption, and (2) a unifying approach explaining the results of Boneh et al (CRYPTO ’08) and Brakerski and Goldwasser (CRYPTO ’10). Finally, by observing that Applebaum’s KDM amplification method (EUROCRYPT ’11) preserves both types of leakage resilience, we obtain schemes providing at the same time high leakage resilience and KDM security against any fixed polynomial-sized circuit family.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2016
KDM Securitycircular securityleakage resilience
Contact author(s)
mhaji @ uvic ca
2016-02-23: last of 2 revisions
2015-07-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mohammad Hajiabadi and Bruce M.  Kapron and Venkatesh Srinivasan},
      title = {On Generic Constructions of Circularly-Secure, Leakage-Resilient Public-Key Encryption Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2015/741},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.