SaTC: CORE: Small: Lattices, number theory, and distribution questions in cryptography

现代密码学面临着一个严重的问题，即量子计算机总有一天会打破我们目前使用的大多数密码系统。 这将对互联网安全和隐私造成灾难性后果。 因此，开发和理解新类型的潜在抗量子密码系统非常重要。 基于欧几里德格的数学概念的密码系统是目前后量子密码学的主要候选者。 该提案研究了这些系统的数学基础以及可能的攻击。具体而言，PI和合作者将研究与LLL格基约简算法（攻击基于格的密码系统的基本工具之一）行为相关的分布问题（例如有偏输出）。 估计基于格的密码系统的安全性需要了解LLL算法及其变体的实际平均情况性能，因此对这种分析感兴趣。 PI和合作者还计划从解析数论和自守形式中开发机器来研究随机晶格的最小基的大小，这对于理解平均情况下的密钥大小也很重要。 最后，PI和合作者将系统地研究椭圆曲线密码系统实现的各种实际方面，例如时间或其他侧信道信息中的异常偏差。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Modern cryptography faces the serious concern that quantum computers will one day break most of our presently-used cryptosystems. This would have catastrophic consequences to internet security and privacy. As a result, it is very important to develop and understand newer types of potentially quantum-resistant cryptosystems. Cryptosystems based on the mathematical notion of Euclidean lattices are presently the leading candidates for post-quantum cryptography. The proposal studies the mathematical underpinnings of these systems, as well as possible attacks on them.Specifically, the PI and collaborators will study distribution questions (such as biased outputs) related to the behavior of the LLL lattice basis reduction algorithm, one of the basic tools for attacking lattice-based cryptosystems. Estimating the security of lattice-based cryptosystems requires understanding the actual, average-case performance of the LLL algorithm and its variants, hence the interest in such an analysis. The PI and collaborators also plan to develop machinery from analytic number theory and automorphic forms to study the size of the smallest basis of a random lattice, which is also important for understanding average-case key sizes. Finally, the PI and collaborators will systematically study various practical aspects of implementations of elliptic curve cryptosystems, such as unusual biases in timings or other side-channel information.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.