Preventing Zeroizing Attacks on GGH15
Preventing Zeroizing Attacks on GGH15
复制标题
防止对 GGH15 的归零攻击
DOI：
10.1145/3318041.3355462
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Mark Zhandry
中科院分区：
文献类型：
--
作者：
James Bartusek;Jiaxin Guan;Fermi Ma;Mark Zhandry
GGH 15多线性映射已经成为许多尖端加密提案的基础。不幸的是，许多建立在GGH 15上的方案已经被所谓的“零化攻击”明确地破坏了，这种攻击利用了诚实的零测试查询的泄漏。零化攻击可能发生的确切环境仍不清楚。最值得注意的是，目前GGH 15中的不可否认性混淆（iO）候选者都没有任何针对零化攻击的正式安全保证。在这项工作中，我们证明了所有已知的零化攻击GGH 15隐式构造零测试的结果和编码的明文元素之间的代数关系。然后，我们提出了一个“GGH 15归零模型”作为一个新的通用框架，大大概括了已知的攻击。我们的第二个贡献是描述一个新的GGH 15变体，我们正式分析我们的GGH 15归零模型。然后，我们使用我们的多线性映射构建了一个新的iO候选，我们在GGH 15零化模型中证明了它的安全性。这意味着抵制所有已知的零化策略。该证明依赖于Garg等人的分支程序不可零性（BPUA）假设[TCC 16-B]（这是针对P/poly的NC安全中的PRF所暗示的）和Miles等人的复杂性理论p有界加速假设[ePrint 14]（指数时间假设的加强）。
The GGH15 multilinear maps have served as the foundation for a number of cutting-edge cryptographic proposals. Unfortunately, many schemes built on GGH15 have been explicitly broken by so-called “zeroizing attacks,” which exploit leakage from honest zero-test queries. The precise settings in which zeroizing attacks are possible have remained unclear. Most notably, none of the current indistinguishability obfuscation (iO) candidates from GGH15 have any formal security guarantees against zeroizing attacks. In this work, we demonstrate that all known zeroizing attacks on GGH15 implicitly construct algebraic relations between the results of zero-testing and the encoded plaintext elements. We then propose a “GGH15 zeroizing model” as a new general framework which greatly generalizes known attacks. Our second contribution is to describe a new GGH15 variant, which we formally analyze in our GGH15 zeroizing model. We then construct a new iO candidate using our multilinear map, which we prove secure in the GGH15 zeroizing model. This implies resistance to all known zeroizing strategies. The proof relies on the Branching Program Un-Annihilatability (BPUA) Assumption of Garg et al. [TCC 16-B] (which is implied by PRFs in NC secure against P/poly) and the complexity-theoretic p-Bounded Speedup Hypothesis of Miles et al. [ePrint 14] (a strengthening of the Exponential Time Hypothesis).