### Circular and Leakage Resilient Public-Key Encryption Under Subgroup Indistinguishability (or: Quadratic Residuosity Strikes Back)

Zvika Brakerski and Shafi Goldwasser

##### 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-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 [BGK, ePrint09] or [BHHI, Eurocrypt10]. * 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-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 [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.

Note: Editorial changes (results are unchanged).

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
zvika brakerski @ weizmann ac il
History
2010-11-16: revised
See all versions
Short URL
https://ia.cr/2010/226

CC BY

BibTeX

@misc{cryptoeprint:2010/226,
author = {Zvika Brakerski and Shafi Goldwasser},
title = {Circular and Leakage Resilient Public-Key Encryption Under Subgroup Indistinguishability (or: Quadratic Residuosity Strikes Back)},
howpublished = {Cryptology ePrint Archive, Paper 2010/226},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/226}},
url = {https://eprint.iacr.org/2010/226}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.