Welcome to the resource topic for 2009/485
Title:
Black-Box Circular-Secure Encryption Beyond Affine Functions
Authors: Zvika Brakerski, Shafi Goldwasser, 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.
ePrint: https://eprint.iacr.org/2009/485
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .