Circular and leakage resilient public-key encryption under subgroup indistinguishability (or: Quadratic residuosity strikes back)
30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Berlin / Heidelberg
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73957 https://orcid.org/0000-0003-4728-1535 |
| _version_ | 1811069972876623872 |
|---|---|
| author | Brakerski, Zvika Goldwasser, Shafi |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Brakerski, Zvika Goldwasser, Shafi |
| author_sort | Brakerski, Zvika |
| collection | MIT |
| description | 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings |
| first_indexed | 2024-09-23T08:19:49Z |
| format | Article |
| id | mit-1721.1/73957 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:19:49Z |
| publishDate | 2012 |
| publisher | Springer Berlin / Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/739572022-09-23T12:20:17Z Circular and leakage resilient public-key encryption under subgroup indistinguishability (or: Quadratic residuosity strikes back) Brakerski, Zvika Goldwasser, Shafi Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Goldwasser, Shafi 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings 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. Microsoft Research 2012-10-15T14:33:12Z 2012-10-15T14:33:12Z 2010-08 2010-08 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-14622-0 0302-9743 1611-3349 http://hdl.handle.net/1721.1/73957 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. https://orcid.org/0000-0003-4728-1535 en_US http://dx.doi.org/10.1007/978-3-642-14623-7_1 Advances in Cryptology – CRYPTO 2010 Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Berlin / Heidelberg Other University Web Domain |
| spellingShingle | Brakerski, Zvika Goldwasser, Shafi Circular and leakage resilient public-key encryption under subgroup indistinguishability (or: Quadratic residuosity strikes back) |
| title | Circular and leakage resilient public-key encryption under subgroup indistinguishability (or: Quadratic residuosity strikes back) |
| title_full | Circular and leakage resilient public-key encryption under subgroup indistinguishability (or: Quadratic residuosity strikes back) |
| title_fullStr | Circular and leakage resilient public-key encryption under subgroup indistinguishability (or: Quadratic residuosity strikes back) |
| title_full_unstemmed | Circular and leakage resilient public-key encryption under subgroup indistinguishability (or: Quadratic residuosity strikes back) |
| title_short | Circular and leakage resilient public-key encryption under subgroup indistinguishability (or: Quadratic residuosity strikes back) |
| title_sort | circular and leakage resilient public key encryption under subgroup indistinguishability or quadratic residuosity strikes back |
| url | http://hdl.handle.net/1721.1/73957 https://orcid.org/0000-0003-4728-1535 |
| work_keys_str_mv | AT brakerskizvika circularandleakageresilientpublickeyencryptionundersubgroupindistinguishabilityorquadraticresiduositystrikesback AT goldwassershafi circularandleakageresilientpublickeyencryptionundersubgroupindistinguishabilityorquadraticresiduositystrikesback |