Paper 2016/110

Three's Compromised Too: Circular Insecurity for Any Cycle Length from (Ring-)LWE

Navid Alamati and 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.

Note: Updated with comparison to concurrent work [KW16].

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2016
Keywords
circular (in)security(ring-)LWE
Contact author(s)
cpeikert @ alum mit edu
History
2016-06-03: revised
2016-02-10: received
See all versions
Short URL
https://ia.cr/2016/110
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/110,
      author = {Navid Alamati and Chris Peikert},
      title = {Three's Compromised Too: Circular Insecurity for Any Cycle Length from (Ring-)LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2016/110},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/110}},
      url = {https://eprint.iacr.org/2016/110}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.