SQZ Talk | 第2期—郁昱教授专题报告“带噪声的奇偶性学习及其密码学应用”

郁昱教授 专题报告

       带噪声的奇偶性学习(Learning Parity with Noise，简称LPN)问题是一个自90年代初以来在学习理论、编码理论和基于编码的密码学领域得到深入研究的计算难题。LPN问题可以看作是带噪声学习(Learning With Errors，简称LWE)问题在模数是2时的一个特例。尽管它的形式简单，但标准的LPN假设似乎并没有超越Minicrypt。

       构造公钥密码算法。2016年前如何基于常噪声、标准LPN问题设计公钥密码算法是密码学界一直关注的公开问题。在这次演讲中，郁昱教授展示了带有亚指数求逆困难的辅助输入方法，基于多项式对数熵源和子空间采样技术，构造了具有亚指数困难性的常噪声、标准LPN问题，在此基础上构造了CCA安全的公钥密码算法，解决了这一公开问题。

       构造抗碰撞哈希函数。2017年Applebaum等人提出了二元最短向量(binary Shortest Vector Problem，简称bSVP)问题，该问题是格上小整数解(Short Integer Solution，简称SIS)问题在二元线性码上的特例。通过SIS问题实现抗碰撞哈希函数是一个已经得到解决的研究，如何从LPN问题，特别是在更高安全性的标准假设下，设计抗碰撞哈希函数是一个公开问题。郁昱教授提出了一种解决方案，首先给出了LPN问题到bSVP问题的归约，刻画了bSVP问题的困难性，然后分别基于亚指数困难的标准和低噪声LPN假设构造了抗碰撞哈希函数。

       时间和空间折衷的 BKW 算法框架。BKW算法是第一个解决LPN问题的亚指数算法，但是需要的运行时间和存储空间是不理想的。郁昱教授提出了更加现实的时间和空间折衷的 BKW 算法框架，该框架不依赖任何启发式假设，可以结合Grover量子算法，或者Dissection技术进一步优化时间复杂度。