Paper 2009/485

Black-Box Circular-Secure Encryption Beyond Affine Functions

Zvika Brakerski, Shafi Goldwasser, and Yael Kalai


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 $d\in\mathbb{N}$, 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 $c\log \lambda$ and running time $\lambda^e$, where $\lambda$ 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-$d$ polynomials, we show that the resulting schemes are also secure with respect to \emph{key cycles} of any length. Specifically, for any polynomial number $n$ of key pairs, our schemes can securely encrypt a degree-$d$ polynomial whose variables are the collection of coordinates of all $n$ 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~$k$), 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).

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


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.