在任意整数环和域上LPN问题的困难性及其在PCG应用

       LPN问题已在密码学中得到广泛应用，最近被用于设计PCG类相关随机数生成协议，进而被应用在安全多方计算、零知识证明和私有集合交集等密码协议中。郁昱团队系统研究了PCG应用中LPN问题的困难性，获得了以下三方面的研究成果：

       LPN问题的困难性是PCG类不经意传输协议及其算术变形的安全基石，已被应用在安全多方计算、零知识证明和私有集合交集等密码协议中，具有样本数大、噪音率低、采用精确或正则噪音分布等特点，但PCG类协议中LPN问题研究较少，系统全面的安全性分析还是空白。

       郁昱团队从理论归约和实际安全性两个角度对PCG类协议中LPN问题困难性系统全面给出了三方面的分析成果。一方面，大部分实际高效的PCG类协议均采用正则噪音分布的LPN问题；提出了新型的精确噪音分布到正则噪音分布LPN问题的安全归约，将安全损失从指数级降低至亚指数级。二方面，模2方幂剩余类环上LPN问题是设计相应环上PCG类协议的安全基石；给出了剩余类环上LPN问题的一个实际有效攻击，降低LPN问题一半的噪音率，有效降低LPN问题安全性约40比特，使得多个后续工作改变了噪音的选取方式；此外，从渐进意义下给出了环上LPN问题与二元域上LPN问题之间等价性安全归约，建立了环上LPN问题判定版本与计算版本的等价性安全归约。三方面，之前所有PCG类协议均根据ACM CCS 2018研究工作给出的LPN问题安全性评估公式选取LPN参数，但他们的评估公式不够准确；针对PCG类协议中LPN问题的实际安全性，研制了LPN问题安全性自动化评估脚本，整合了最先进的 Pooled Gauss、SD、ISD和代数攻击，其中该评估脚本已被多个后续工作采用。