大型计算能力的提升和密码分析学的进步,特别是量子计算理论的成熟和量子计算机的发展,给很多基于大整数分解和离散对数等传统数学问题的密码算法的安全性,带来了巨大的威胁和挑战。Shor算法、Simon算法、Grover算法等量子算法的提出标志着现代密码学步入了后量子时代,即人们开始研究能够抵御量子计算机和量子算法攻击的密码学,这些抗量子计算攻击的密码又叫后量子密码。目前,能够做到抗量子计算攻击的后量子密码学主要有如下几类:基于格的密码学、基于编码的密码学、基于哈希的密码学、基于多变量方程的密码学以及基于同源的密码学等。其中基于格和基于编码的密码学是目前最被看好的研究方向,因为这两类算法底层的数学困难问题具有悠久的研究历史和公认的量子困难性,同时基于其设计的密码方案还具有较好的计算效率和并行性,因此基于格和基于编码的密码学成为了目前最主流,也是最有前途的研究热点之一。本论文主要集中于后量子密码领域里基于编码的密码学的研究。旨在研究基于编码的数学困难问题的计算困难性,给出更好的攻击算法及其复杂度分析,给出编码上不同计算困难问题之间的安全归约,并基于这些困难假设构造可证明安全的密码学原语、密码学协议和密码学方案等。具体来说,我们的研究对象包括著名的带噪声奇偶性学习问题 LPN（Learning Parity with Noise）及其变种问题如 Sparse LPN（Sparsely Learning Parity with Noise）和LSPN（Learning Sparse Parities with Noise）;除此之外,我们还研究了 LPN问题的对偶问题,即二元最短向量问题bSVP（binary Shortest Vector Problem）及其非齐次版本的IbSVP（Inhomogeneous bSVP）问题的困难性。最后我们基于这些编码上的计算困难假设构造了承诺和∑-协议等密码学方案,并设计了基于编码的高效的零知识证明协议。通过给出安全归约和安全证明,将密码算法和协议的安全性建立在底层编码问题的计算困难性之上,从而达到密码算法和密码协议的可证明安全性。我们的研究成果分为两个方面,首先介绍基于编码的数学问题的困难性研究成果:1.Sparse LPN问题及其困难性研究。影响编码密码学发展的最大瓶颈在于生成矩阵需要大量的随机数,进一步也导致了巨大的存储和通信开销。我们研究了稀疏矩阵LPN问题,即Sparse LPN问题的困难性。Sparse LPN问题的公共矩阵不是均匀随机的,而是由一些稀疏的向量组成的。更具体地说,矩阵的每一个元素都来自伯努利分布。我们证明了在相同噪声率下,只要标准LPN问题是困难的,那么Sparse LPN问题也是困难的。否则将会得到令人惊讶的突破性结果,即在任何噪声率下,可以基于标准的LPN假设构造IND-CPA安全的公钥加密（PKE）方案和不经意传输（OT）协议,并且不需要求助于亚指数安全的LPN困难假设或者基于低噪声率LPN困难假设。此外,通过借助密钥公开的伪随机函数（PRF）,我们还给出了 Sparse LPN问题实例的启发式生成方法。上述所有的证明技巧均来自双赢论断（Win-Win Argument）技术。2.LSPN问题及其困难性研究。我们研究了稀疏密钥LPN问题,即LSPN问题的困难性,给出了求解LSPN问题的优化算法及其在不同参数下的复杂度分析。并且借助于D（?）ttling的样本放大技术（Sample Amplification）,由较少的样本生成更多计算意义上不可区分的新样本,用以求解LSPN问题。具体地,（1）当密钥的汉明重量k=nu（0＜u＜1）,噪声率η＜1/2时,我们的算法能够以常数大小的概率解决（n,k,η）-LSPN问题,该算法所需要的时间和空间复杂度为（n（1-u+o（1））k）/（1/2-η）2。当u＞0.2的时候,我们的算法比目前G.Valiant所提出的最优的算法还要好,其算法的时间复杂度为poly（1/1-2η）·n0.8k;对于u＞0.5的时候,我们越过了n0.5k这个障碍,这是Grigorescu等人所给出的低噪声LSPN问题最优求解算法所没有达到的。另一个优于Grigorescu等人工作的地方在于我们摆脱了n在指数上对于噪声率参数η的依赖。（2）对于任意常数1/2＜c1＜1,k=o（ηn/logn）以及η≤n-c1/4,我们的算法能够以常数大小的概率解决（n,k,η）-LSPN问题,该算法所需要的时间和空间复杂度为n2（1-c1+o（1））k。尤其是当噪声率η≤n-0.75,同时密钥重量k较小的时候（如k=log n）,我们的算法比Grigorescu等人的算法要更好。值得注意的是,Alekhnovich指出高级的密码学应用如公钥加密方案和不经意传输协议,都可以基于噪声率为η ≤n-0.5的低噪声LPN假设来构造。（3）最后我们给出了如何利用较少样本来获取更多样本的双赢的结果。如果存在一个算法能够以Ω（1）的概率,在时间复杂度和样本复杂度都是nO（k）的情况下解决（n,k,η）-LSPN问题,其中密钥的汉明重量为k=o（n1-c）,噪声率为η=n1-2c/3且常数c满足1/2 ≤c＜1。那么下列至少有一项成立,即-要么存在一个算法能够在较低的噪声率μ=n-c/3的情况下,以Ω（1）的成功概率在2n个样本的复杂度下解决（n,k,μ）-LSPN 问题;-要么存在一个算法能够以n-O（k）/poly（n）的概率解决（n,k’,μ）-LSPN问题,其密钥的汉明重量为一个较大的参数k’=n1-c,该算法的时间复杂度为poly（n）.nO（k）而空间复杂度仅为n个样本。3.bSVP问题及其困难性研究。我们研究了 LPN问题的对偶问题,即bSVP问题在平均意义和最坏意义情况下的困难性,bSVP问题可以看作是格上SIS问题在二元线性码上的特例。受到Yu和Zhang给出的二元线性码平滑（Code Smoothing）技术的启发,我们给出了第一个bSVP问题最坏意义情况下困难性到平均意义情况下困难性的归约。通过当前最先进的信息集合译码（ISD）算法来求解最坏意义的bSVP问题,我们得到其算法复杂度为2Ω（n）。因为目前我们并不知道任何能够对ISD算法进行优化和加速的其他算法,于是我们得到了 bSVP问题在最坏意义下依然具有指数级的困难性。我们的第二个研究内容集中于编码密码学在零知识证明领域的应用,构造了基于LSPN和bSVP困难假设的零知识证明协议:1.基于LSPN问题的零知识证明方案设计。我们基于LSPN问题构造了统计意义上绑定的承诺方案,并给出了 LSPN问题稀疏密钥知识的零知识证明、承诺方案有效打开知识的零知识证明,以及底层承诺消息之间满足任意关系的零知识证明。2.基于bSVP问题的零知识证明方案设计。我们基于bSVP问题构造了计算意义上绑定和隐藏的承诺方案,并给出了 bSVP问题密钥知识的零知识证明、承诺方案有效打开知识的零知识证明,以及底层承诺消息之间满足任意关系的零知识证明。3.bSVP问题在零知识证明里的高级密码学方案设计。我们给出了bSVP问题在零知识证明领域更高级的密码学应用,包括身份认证协议,以及利用Fiat-Shamir通用转换将其转化为基于编码的数字签名方案;我们还介绍了基于bSVP问题的多中之一证明（One-out-of-Many Proof）、集合成员证明（Set Membership Proof）和范围证明（Range Proof）;最后,我们给出了基于LPN问题的公钥加密方案的明文知识证明（Proof of Plaintext Knowledge,PoPK）和明文相等知识证明。