随着量子计算理论的发展和量子计算机制造工艺的不断进步,量子算法的研究已不仅局限于理论模型,其日益成为未来可实现甚至推广应用的科学技术。类似于现行的经典计算机模型,量子计算机可以进行高速数学与逻辑运算,还可以存储与处理数据信息。随着量子计算模型在其他相关领域的应用,我们发现,在已有的研究中,大部分广泛应用的经典密码学的应用在量子计算机下是不安全的,换句话说,这些应用是可以找到时间复杂度为多项式的量子算法解决的。在这个大背景下,虽然量子计算机大规模运算和推广还未实现,但是密码学界已经开始设计新的抗量子计算机攻击的密码学体系—-后量子密码学了。这些后量子密码学大致可以分为以下几类:基于哈希数字签名协议(Hash-based Digital Signature Schemes),基于编码的密码体系(Code-based Cryptography),基于格问题的密码学体系(Lattice-based Cryptography)和基于多变量困难问题的密码学体系(Multivariate Public key Cryptography)。本文主要讨论与研究基于编码的密码体系的一个分支,基于LPN(Learning Parity with Noise)困难性的密码体系,并且对稀疏LPN问题(Sparsely LPN)的健壮性进行研究,并给出了几个简单的应用。在机器学习理论和密码学理论领域中,LPN问题(Learning Parity with Noise)一直是一个大热点。本文主要探讨其在密码学领域的应用与研究,LPN问题在量子计算机模型下是安全的,即没有时间复杂度为多项式的量子算法可以以多项式分之一的成功概率来攻击LPN问题,所以引起了密码学界的关注。并且,许多基于LPN问题的密码学体系在后量子密码学的安全方案中以高效著称。在密码学界,密码学家不仅仅是研究LPN问题的密码学应用,而且还深入研究不同变种的LPN问题在量子计算模型和经典计算模型下的困难性。Applebaum B,Barak B,Wigderson(STOC 2010)提出了一种建立在某种变种LPN问题的公钥加密方案,该变种LPN问题是公共随机矩阵每一行独立随机地从全部汉明重量为3的向量集合中抽取的LPN问题。而且对于这个变种LPN问题的困难性给出了一个不是很严格的探讨,即用所有已知的针对LPN问题的攻击都是对该变种LPN问题是无效的,即不能够在多项式时间内恢复密钥或者被加密的数据。本文证明了广义的该种变种LPN问题,公共随机矩阵的每个元素都是独立随机地服从低期望的伯努利分布的LPN问题,是困难的。证明步骤主要是通过双赢(win-win)方法来对两个假设建立联系,即至少一个假设为真(证明排除了两个假设都为假的情况)。两个假设如下:1.稀疏LPN问题是困难的;2.一套新的黑盒构造,可以在标准LPN问题上建立公钥加密(public-key encryption,PKE)和不经意传送(oblivious transfer,OT)。而且通过密码学家们的大量研究和不懈努力,第二个假设很难实现,并且第二个假设为真远远比第一个假设为真更具有创新性和突破性。所以本文相信第一个假设为真,即稀疏LPN是困难的。本文最主要的价值在于通过双赢方法建立了两个假设之间存在着一个联系,即两个假设不可能同时为假。