LWE with Side Information: Attacks and Concrete Security Estimation
LWE with Side Information: Attacks and Concrete Security Estimation
复制标题
DOI：
10.1007/978-3-030-56880-1_12
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Dana Dachman-Soled;L. Ducas;Huijing Gong;Mélissa Rossi
中科院分区：
文献类型：
--
作者：
Dana Dachman-Soled;L. Ducas;Huijing Gong;Mélissa Rossi
我们提出了一个基于格的方案的密码分析框架，当关于秘密和/或错误的“提示”形式的边信息可用时。我们的框架推广了所谓的原始格约简攻击，并允许在运行最终的格约简步骤之前渐进地整合提示。我们集成线索的技术包括稀疏格子、投影到超平面和与超平面相交、和/或改变秘密向量的分布。我们的主要贡献是提出了一个工具箱和一种方法来将这些提示整合到格化简攻击中，并利用边信息来预测这些格攻击的性能。虽然我们最初是为边信道信息设计的，但我们的框架也可以用于其他情况：利用解密失败，或者仅仅利用某些方案(LAC，Round5，NTRU)施加的约束。我们实现了一个Sage 9.0工具包，在计算可行的情况下实际安装具有提示的此类攻击，并在更大的实例上预测它们的性能。我们提供了几个端到端的应用实例，例如Bos等人对Frodo的单一跟踪攻击的改进。(SAC 2018)。特别是，我们的工作可以估计安全损失，即使给出很少的辅助信息，导致侧通道攻击的测量/计算平滑权衡。
We propose a framework for cryptanalysis of lattice-based schemes, when side information—in the form of “hints”—about the secret and/or error is available. Our framework generalizes the so-called primal lattice reduction attack, and allows the progressive integration of hints before running a final lattice reduction step. Our techniques for integrating hints include sparsifying the lattice, projecting onto and intersecting with hyperplanes, and/or altering the distribution of the secret vector. Our main contribution is to propose a toolbox and a methodology to integrate such hints into lattice reduction attacks and to predict the performance of those lattice attacks with side information.While initially designed for side-channel information, our framework can also be used in other cases: exploiting decryption failures, or simply exploiting constraints imposed by certain schemes (LAC, Round5, NTRU).We implement a Sage 9.0 toolkit to actually mount such attacks with hints when computationally feasible, and to predict their performances on larger instances. We provide several end-to-end application examples, such as an improvement of a single trace attack on Frodo by Bos et al. (SAC 2018). In particular, our work can estimates security loss even given very little side information, leading to a smooth measurement/computation trade-off for side-channel attacks.