Paper 2009/485
BlackBox CircularSecure Encryption Beyond Affine Functions
Zvika Brakerski, Shafi Goldwasser, and Yael Kalai
Abstract
We show how to achieve publickey 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 publickey 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 keydependent message (KDM) secure w.r.t.\ degree$d$ polynomials. We also show that for any constants $c,e$, there exists a publickey 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 publickey schemes can be based either on the standard decision DiffieHellman (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)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 publickey cryptographycircular secure encryptiondecision Diffie HellmanLearning with Errors
 Contact author(s)
 zvika brakerski @ weizmann ac il
 History
 20110309: revised
 20091005: 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 = {BlackBox CircularSecure 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} }