CryptoDB
Circular and Leakage Resilient Public-Key Encryption Under Subgroup Indistinguishability (or: Quadratic Residuosity Strikes Back)
| Authors: | |
|---|---|
| Download: | |
| Abstract: | 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 {\it subgroup indistinguishability assumption}, of which the QR and DCR are special cases, we can construct a scheme that has: * Key-dependant 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-dependant message security to broader classes of functions beyond affine functions using the techniques of [BGK, ePrint09] or [BHHI, ePrint09]. * 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 \emph{hard to invert} (efficiently computable) function of the secret-key is given to the adversary. Our scheme is the first to achieve key-dependant 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 [NS, Crypto09], 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. |
BibTeX
@misc{eprint-2010-23127,
title={Circular and Leakage Resilient Public-Key Encryption Under Subgroup Indistinguishability (or: Quadratic Residuosity Strikes Back)},
booktitle={IACR Eprint archive},
keywords={public-key cryptography /},
url={http://eprint.iacr.org/2010/226},
note={ zvika.brakerski@weizmann.ac.il 14721 received 22 Apr 2010},
author={Zvika Brakerski and Shafi Goldwasser},
year=2010
}