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 Discussion forum: Show discussion | Start new discussion