**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.

**Category / Keywords: **public-key cryptography / circular (in)security, (ring-)LWE

**Original Publication**** (with minor differences): **IACR-CRYPTO-2016

**Date: **received 9 Feb 2016, last revised 3 Jun 2016

**Contact author: **cpeikert at alum mit edu

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

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

**Version: **20160603:192001 (All versions of this report)

**Short URL: **ia.cr/2016/110

[ Cryptology ePrint archive ]