Welcome to the resource topic for 2016/110
Title:
Three’s Compromised Too: Circular Insecurity for Any Cycle Length from (Ring-)LWE
Authors: Navid Alamati, Chris Peikert
Abstract:Informally, a public-key encryption scheme is \emph{k-circular secure} if a cycle of~k encrypted secret keys (\pkcenc_{\pk_{1}}(\sk_{2}), \pkcenc_{\pk_{2}}(\sk_{3}), \ldots, \pkcenc_{\pk_{k}}(\sk_{1})) is indistinguishable from encryptions of zeros. Circular security has applications in a wide variety of settings, ranging from security of symbolic protocols to fully homomorphic encryption. A fundamental question is whether standard security notions like IND-CPA/CCA imply k-circular security. For the case k=2, several works over the past years have constructed counterexamples—i.e., schemes that are CPA or even CCA secure but not 2-circular secure—under a variety of well-studied assumptions (SXDH, decision linear, and LWE). However, for k > 2 the only known counterexamples are based on strong general-purpose obfuscation assumptions. In this work we construct k-circular security counterexamples for any k \geq 2 based on (ring-)LWE. Specifically: \begin{itemize} \item for any constant k=O(1), we construct a counterexample based on n-dimensional (plain) LWE for \poly(n) approximation factors; \item for any k=\poly(\lambda), we construct one based on degree-n ring-LWE for at most subexponential \exp(n^{\varepsilon}) factors. \end{itemize} Moreover, both schemes are k'-circular insecure for 2 \leq k' \leq k. Notably, our ring-LWE construction does not immediately translate to an LWE-based one, because matrix multiplication is not commutative. To overcome this, we introduce a new ``tensored’’ variant of LWE which provides the desired commutativity, and which we prove is actually equivalent to plain LWE.
ePrint: https://eprint.iacr.org/2016/110
Talk: https://www.youtube.com/watch?v=jpjUbBLSGeQ
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 .