TY - GEN
T1 - On generic constructions of circularly-secure, leakage-resilient public-key encryption schemes
AU - Hajiabadi, Mohammad
AU - Kapron, Bruce M.
AU - Srinivasan, Venkatesh
N1 - Funding Information:
Work of the first two authors supported in part by an NSERC Discovery Grant, “Foundational studies in privacy and security”, and the Simons Institute for the Theory of Computing program “Real analysis in computer science”. Work of the second author was partly completed while a Visiting Member of the School of Mathematics at the Institute for Advanced Study. Part of this work was done while the third author was a Senior Visiting Research Fellow at the Centre for Quantum Technologies, NUS, Singapore.
Publisher Copyright:
© International Association for Cryptologic Research 2016.
PY - 2016
Y1 - 2016
N2 - 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) a form of (additive) homomorphism with respect to both plaintexts 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:–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 in turn obtain homomorphic weak PRFs from homomorphic hash-proof systems (HHPS). We also show how the base encryption scheme may be realized using subgroup indistinguishability (implied, in particular, by quadratic residuosity (QR) and decisional composite residuosity (DCR)). As corollaries of our results, we obtain (1) the first multiple-key projection-secure bit-encryption scheme (as well as the first 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.
AB - 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) a form of (additive) homomorphism with respect to both plaintexts 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:–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 in turn obtain homomorphic weak PRFs from homomorphic hash-proof systems (HHPS). We also show how the base encryption scheme may be realized using subgroup indistinguishability (implied, in particular, by quadratic residuosity (QR) and decisional composite residuosity (DCR)). As corollaries of our results, we obtain (1) the first multiple-key projection-secure bit-encryption scheme (as well as the first 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.
UR - http://www.scopus.com/inward/record.url?scp=84959187227&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84959187227&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-49387-8_6
DO - 10.1007/978-3-662-49387-8_6
M3 - Conference contribution
AN - SCOPUS:84959187227
SN - 9783662493861
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 129
EP - 158
BT - Public-Key Cryptography – PKC 2016 - 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings
A2 - Cheng, Chen-Mou
A2 - Chung, Kai-Min
A2 - Yang, Bo-Yin
A2 - Persiano, Giuseppe
PB - Springer Verlag
T2 - 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, PKC 2016
Y2 - 6 March 2016 through 9 March 2016
ER -