Factoring and Pairings are not Necessary for iO: Circular-Secure LWE Suffices
Factoring and Pairings are not Necessary for iO: Circular-Secure LWE Suffices
复制标题
DOI：
10.4230/lipics.icalp.2022.28
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Zvika Brakerski;Nico Döttling;Sanjam Garg;Giulio Malavolta
中科院分区：
文献类型：
--
作者：
Zvika Brakerski;Nico Döttling;Sanjam Garg;Giulio Malavolta
。我们仅在基于错误学习（LWE）问题的加密方案的循环安全属性下构建不可区分性混淆（ iO ）。之前使用循环安全假设来构造（非分级）全同态加密（FHE），但我们的假设更强并且需要循环随机性泄漏弹性。与之前的工作相比，这个假设可以被推测为后量子安全；产生第一个可证明安全的 iO 结构，它（似乎）是后量子安全的。我们的工作遵循 Gay 和 Pass [STOC 2021] 最近工作的高级概要，他们展示了一种从 Brakerski、Dòottling、Garg 和 Malavolta [EUROCRYPT 2020] 基于同态加密的 iO 方法中删除启发式步骤的方法。因此，他们获得了在自然同态加密方案的循环安全假设下被证明是安全的构造——具体来说，他们分别使用基于 LWE 和 DCR 的同态加密方案。在这项工作中，我们展示了如何消除 DCR 假设并保留仅基于 LWE 循环安全性的方案。在此过程中，我们放松了 Gay-Pass 蓝图中的一些要求，从而获得了一个在宽松的假设下安全的方案。具体来说，我们不要求存在密钥循环时的安全性，而只要求存在密钥随机性循环时的安全性。我们工作的另一个贡献是指出了许多 iO 候选者（包括所有现有可证明的后量子候选者）使用的构建模块之一的问题。也就是说，从 Lin、Pass、Seth 和 Telang 的指数效率 iO (XiO) 的转变中 [PKC 2016]。我们展示了为什么它们的转换本质上无法实现预期目标，然后通过展示浅层 XiO（即混淆器是深度限制的）确实使用 LWE 转换为 iO 来纠正这种情况。
. We construct indistinguishability obfuscation ( iO ) solely under circular-security properties of encryption schemes based on the Learning with Errors (LWE) problem. Circular-security assumptions were used before to construct (non-leveled) fully-homomorphic encryption (FHE), but our assumption is stronger and requires circular randomness-leakage-resilience. In contrast with prior works, this assumption can be conjectured to be post-quantum secure; yielding the first provably secure iO construction that is (plausibly) post-quantum secure. Our work follows the high-level outline of the recent work of Gay and Pass [STOC 2021], who showed a way to remove the heuristic step from the homomorphic-encryption based iO approach of Brakerski, D¨ottling, Garg, and Malavolta [EUROCRYPT 2020]. They thus obtain a construction proved secure under circular security assumption of natural homomorphic encryption schemes — specifically, they use homomorphic encryption schemes based on LWE and DCR, respectively. In this work we show how to remove the DCR assumption and remain with a scheme based on the circular security of LWE alone. Along the way we relax some of the requirements in the Gay-Pass blueprint and thus obtain a scheme that is secure under a relaxed assumption. Specifically, we do not require security in the presence of a key-cycle, but rather only in the presence of a key-randomness cycle. An additional contribution of our work is to point out a problem in one of the building blocks used by many iO candidates, including all existing provable post-quantum candidates. Namely, in the transformation from exponentially-efficient iO (XiO) from Lin, Pass, Seth and Telang [PKC 2016]. We show why their transformation inherently falls short of achieving the desired goal, and then rectify this situation by showing that shallow XiO (i.e. one where the obfuscator is depth-bounded) does translate to iO using LWE.