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 $({\text{pkcenc}}_{{\text{pk}}_1}({\text{sk}}_2),{\text{pkcenc}}_{{\text{pk}}_2}({\text{sk}}_3),\dots ,{\text{pkcenc}}_{{\text{pk}}_k}({\text{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 $$-circular security. For the case $$, several works over the past years have constructed counterexamples---i.e., schemes that are CPA or even CCA secure but not $$-circular secure---under a variety of well-studied assumptions (SXDH, decision linear, and LWE). However, for $$ the only known counterexamples are based on strong general-purpose obfuscation assumptions. In this work we construct $$-circular security counterexamples for any $$ based on (ring-)LWE. Specifically: \begin{itemize} \item for any constant $$, we construct a counterexample based on $$-dimensional (plain) LWE for $$ approximation factors; \item for any $$, we construct one based on degree-$$ ring-LWE for at most subexponential $$ factors. \end{itemize} Moreover, both schemes are $$-circular insecure for $$. 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].