Black-Box Circular-Secure Encryption beyond Affine Functions

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

 ∈ ℕ, 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

λ

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-

d

polynomials, we show that the resulting schemes are also secure with respect to

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.

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

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.