Paper 2009/485

Black-Box Circular-Secure Encryption Beyond Affine Functions

Zvika Brakerski, Shafi Goldwasser, and Yael Kalai

Abstract

We show how to achieve public-key encryption schemes that can securely encrypt nonlinear functions of their own secret key. Specifically, we show that for any constant dN, there exists a public-key encryption scheme that can securely encrypt any function f of its own secret key, assuming f can be expressed as a polynomial of total degree~d. Such a scheme is said to be key-dependent message (KDM) secure w.r.t.\ degree-d polynomials. We also show that for any constants c,e, there exists a public-key encryption scheme that is KDM secure w.r.t.\ all Turing machines with description size clogλ and running time λe, where λ is the security parameter. The security of such public-key schemes can be based either on the standard decision Diffie-Hellman (DDH) assumption or on the learning with errors (LWE) assumption (with certain parameters settings). In the case of functions that can be expressed as degree- polynomials, we show that the resulting schemes are also secure with respect to \emph{key cycles} of any length. Specifically, for any polynomial number of key pairs, our schemes can securely encrypt a degree- polynomial whose variables are the collection of coordinates of all secret keys. Prior to this work, it was not known how to achieve this for nonlinear functions. Our key idea is a general transformation that amplifies KDM security. The transformation takes an encryption scheme that is KDM secure w.r.t.\ \emph{some} functions even when the secret keys are weak (i.e.\ chosen from an arbitrary distribution with entropy~), and outputs a scheme that is KDM secure w.r.t.\ a \emph{richer} class of functions. The resulting scheme may no longer be secure with weak keys. Thus, in some sense, this transformation converts security with weak keys into amplified KDM security.

Note: Editorial changes (no change in technical contents).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
public-key cryptographycircular secure encryptiondecision Diffie HellmanLearning with Errors
Contact author(s)
zvika brakerski @ weizmann ac il
History
2011-03-09: revised
2009-10-05: received
See all versions
Short URL
https://ia.cr/2009/485
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/485,
      author = {Zvika Brakerski and Shafi Goldwasser and Yael Kalai},
      title = {Black-Box Circular-Secure Encryption Beyond Affine Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/485},
      year = {2009},
      url = {https://eprint.iacr.org/2009/485}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.