Black-Box Circular-Secure Encryption Beyond Affine Functions

Zvika Brakerski; Shafi Goldwasser; Yael Kalai

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 $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).

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: public-key cryptography circular secure encryption decision Diffie Hellman Learning 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: 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},
      note = {\url{https://eprint.iacr.org/2009/485}},
      url = {https://eprint.iacr.org/2009/485}
}