Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Three’s Compromised Too: Circular Insecurity for Any Cycle Length from (Ring-)LWE
verfasst von : Navid Alamati, Chris Peikert
Erschienen in: Advances in Cryptology – CRYPTO 2016
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
A public-key encryption scheme is k-circular secure if a cycle of k encrypted secret keys \((\mathsf {Enc} _{pk_{1}}(sk_{2}), \mathsf {Enc} _{pk_{2}}(sk_{3}), \ldots , \mathsf {Enc} _{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 \ge 2\) based on (ring-)LWE. Specifically:
-
for any constant \(k=O(1)\), we construct a counterexample based on n-dimensional (plain) LWE for \(\mathrm{poly}(n)\) approximation factors;
-
for any \(k=\mathrm{poly}(\lambda )\), we construct one based on degree-n ring-LWE for at most subexponential \(\exp (n^{\varepsilon })\) factors.
Moreover, both schemes are \(k'\)-circular insecure for \(2 \le k' \le 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.