Almost Tight Security in Lattices with Polynomial Moduli - PRF, IBE, All-but-many LTF, and More
Almost Tight Security in Lattices with Polynomial Moduli - PRF, IBE, All-but-many LTF, and More
复制标题
DOI：
10.1007/978-3-030-45374-9_22
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Qiqi Lai;Feng-Hao Liu;Zhedong Wang
中科院分区：
文献类型：
--
作者：
Qiqi Lai;Feng-Hao Liu;Zhedong Wang
实现严格的安全性是密码学的一项基本任务。虽然此任务最重要的目的之一是提高构造的整体效率（通过允许更小的安全参数），但许多当前基于格的实例化并没有完全实现该目标。特别是，在所有先前的（几乎）严格方案的工作中，超多项式模数似乎是必要的，这些方案允许对手进行查询，例如 PRF、IBE 和签名。由于超多项式模量会影响噪声模量比，从而增加参数，这可能会抵消更严格分析带来的优势（效率）。为了确定格中严格安全性/分析的全部能力，有必要确定超多项式模量限制是否是固有的。在这项工作中，我们消除了许多重要原语的超多项式模数限制 - PRF、IBE、所有但许多有损陷门函数和签名。关键在于对 Boyen 和 Li (Asiacrypt 16) 框架的改进，以及从 LWE 到 LWR 的几乎严格缩减，这改进了 Alwen 等人 (Eurocrypt 13)、Bogdanov 等人 (TCC 16) 和 Bai 等人 (Asiacrypt 15) 的先前工作。通过结合这两项进展，我们能够在 LWE 下用多项式模量导出这些几乎紧密的方案。
Achieving tight security is a fundamental task in cryptography. While one of the most important purposes of this task is to improve the overall efficiency of a construction (by allowing smaller security parameters), many current lattice-based instantiations do not completely achieve the goal. Particularly, a super-polynomial modulus seems to be necessary in all prior work for (almost) tight schemes that allow the adversary to conduct queries, such as PRF, IBE, and Signatures. As the super-polynomial modulus would affect the noise-to-modulus ratio and thus increase the parameters, this might cancel out the advantages (in efficiency) brought from the tighter analysis. To determine the full power of tight security/analysis in lattices, it is necessary to determine whether the super-polynomial modulus restriction is inherent. In this work, we remove the super-polynomial modulus restriction for many important primitives—PRF, IBE, all-but-many Lossy Trapdoor Functions, and Signatures. The crux relies on an improvement over the framework of Boyen and Li (Asiacrypt 16), and an almost tight reduction from LWE to LWR, which improves prior work by Alwen et al.(Eurocrypt 13), Bogdanov et al.(TCC 16), and Bai et al.(Asiacrypt 15). By combining these two advances, we are able to derive these almost tight schemes under LWE with a polynomial modulus.