**Black-Box Circular-Secure Encryption Beyond Affine Functions**

*Zvika Brakerski and 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.

**Category / Keywords: **public-key cryptography / public-key cryptography, circular secure encryption, decision Diffie Hellman, Learning with Errors

**Date: **received 1 Oct 2009, last revised 9 Mar 2011

**Contact author: **zvika brakerski at weizmann ac il

**Available format(s): **PDF | BibTeX Citation

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

**Version: **20110309:223137 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]