Circular and leakage resilient public-key encryption under subgroup indistinguishability (or: Quadratic residuosity strikes back)
Author(s)
Brakerski, Zvika; Goldwasser, Shafi![Thumbnail](/bitstream/handle/1721.1/73957/Goldwasser-Circular%20and%20leakage.pdf.jpg?sequence=4&isAllowed=y)
DownloadGoldwasser-Circular and leakage.pdf (380.5Kb)
OPEN_ACCESS_POLICY
Open Access Policy
Creative Commons Attribution-Noncommercial-Share Alike
Terms of use
Metadata
Show full item recordAbstract
The main results of this work are new public-key encryption schemes that, under the quadratic residuosity (QR) assumption (or Paillier’s decisional composite residuosity (DCR) assumption), achieve key-dependent message security as well as high resilience to secret key leakage and high resilience to the presence of auxiliary input information.
In particular, under what we call the subgroup indistinguishability assumption, of which the QR and DCR are special cases, we can construct a scheme that has:
• Key-dependent message (circular) security. Achieves security even when encrypting affine functions of its own secret key (in fact, w.r.t. affine “key-cycles” of predefined length). Our scheme also meets the requirements for extending key-dependent message security to broader classes of functions beyond affine functions using previous techniques of Brakerski et al. or Barak et al.
• Leakage resiliency. Remains secure even if any adversarial low-entropy (efficiently computable) function of the secret key is given to the adversary. A proper selection of parameters allows for a “leakage rate” of (1 − o(1)) of the length of the secret key.
• Auxiliary-input security. Remains secure even if any sufficiently hard to invert (efficiently computable) function of the secret key is given to the adversary.
Our scheme is the first to achieve key-dependent security and auxiliary-input security based on the DCR and QR assumptions. Previous schemes that achieved these properties relied either on the DDH or LWE assumptions. The proposed scheme is also the first to achieve leakage resiliency for leakage rate (1 − o(1)) of the secret key length, under the QR assumption. We note that leakage resilient schemes under the DCR and the QR assumptions, for the restricted case of composite modulus product of safe primes, were implied by the work of Naor and Segev, using hash proof systems. However, under the QR assumption, known constructions of hash proof systems only yield a leakage rate of o(1) of the secret key length.
Description
30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings
Date issued
2010-08Department
Massachusetts Institute of Technology. Department of Electrical Engineering and Computer ScienceJournal
Advances in Cryptology – CRYPTO 2010
Publisher
Springer Berlin / Heidelberg
Citation
Brakerski, Zvika, and Shafi Goldwasser. “Circular and Leakage Resilient Public-Key Encryption Under Subgroup Indistinguishability.” Advances in Cryptology – CRYPTO 2010. Ed. Tal Rabin. LNCS Vol. 6223. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. 1–20.
Version: Author's final manuscript
ISBN
978-3-642-14622-0
ISSN
0302-9743
1611-3349