二次剩余在密码方案构造和密码协议设计中扮演着重要角色。众所周知,Goldwasser和Micali里程碑式的工作首次给出了密文不可分辨性与语义安全的形式化定义,继而开启了密码学可证明安全领域研究的新篇章。他们基于二次剩余构造了第一个概率加密方案。然而,这个方案具有较大的密文扩张率,所以降低了它的实际应用价值。如何改进Goldwasser-Micali密码系统是一项古老而又富有挑战的课题。除了在构造同态加密上的应用,二次剩余还可以用来构造伪随机数发生器、零知识证明、数字签名等方案与协议。基于身份的密码学（IBC）被认为是公钥密码学的演化。它把用户的身份信息当做公钥,从而省去了数字证书的使用。目前,绝大多数的IBC方案都是基于双线性配对构造的。然而计算一个双线性配对并不是高效的,而且这些方案的安全性普遍依赖于未经考验的复杂性假设或者难题。Cocks基于二次剩余构造了首个不需要配对的基于身份的加密（IBE）方案。虽然这个方案具有较快的加解密算法,但是它在带宽和空间利用方面并不是很高效,而且它也不是匿名的。这些缺陷使得Cocks的IBE方案受到比较少的关注。数论是最古老的数学分支之一。Gauss、Eisenstein、Kummer和Dedekind等人对代数数论的建立和研究做出了重大贡献。我们已经看到二次剩余在密码学领域中大放异彩。如何将更多的数论应用到密码学是一项具有重要的理论和实际意义的课题。本文从上述背景和问题出发,完成了以下三个方面的工作:1.基于幂剩余符号的高效同态密码系统:在这部分工作中,我们回顾了幂剩余符号并给出了它在密码学中的一些应用。具体地讲,我们证明了计算一类幂剩余符号与求解某个离散对数难题相关,从而利用这个结论给出了Goldwasser-Micali密码系统的一个很自然的推广。与Joye和Libert在EU-ROCRYPT 2013会议上提出的推广方案相比,我们的方案在带宽、空间利用以及解密效率方面都要更高效一些。我们同时推广了Goldwasser-Micali密码系统所依赖的复杂性假设,并且在推广的假设下证明了我们的方案是IND-CPA安全的。我们还展示了如何利用上述结论去构造有损陷门函数与循环安全和弹性泄露的公钥加密方案,并且这些构造同样具有高效的解密效率和带宽和空间的使用效率。2.基于二次剩余的具有快速加密算法的匿名IBE方案:在这部分工作中,我们给出了Cocks的IBE方案的两个变种。第一个变种有更高效的加密算法,其中最耗时的部分仅需要几个模乘法运算。第二个变种在合适的复杂性假设下匿名化了第一个变种,但是它的解密效率要比第一个变种的解密效率低两倍左右。两个变种的密文扩张率都比Cocks方案的密文扩张率大两倍。为了减轻第二个变种因较大的密文扩张率带来的不利影响,我们考虑利用文献[1]提出的变换将它转化成一个带关键字检索的公钥加密方案。3.基于高次剩余的IBE方案上的推广Galbraith测试:在PKC 2019会议上,Clear和Mc Goldrick首次提出了模一个多项式大小的素数e是加法同态的群同态IBE方案。同时,他们证明了如果判定某个特殊的多变量多项式系统是否可解是困难的,那么该方案在e>2的情形下是匿名的。在这部分工作中,我们回顾了Cocks方案的匿名性上的经典Galbraith测试。我们引入了Fq[x]上的一般互反律来推广Galbraith测试,并对Clear-Mc Goldrick方案的匿名性给出了一个有效的攻击方法,从而加深了人们对Galbraith测试的理解。我们相信推广的Galbraith测试在构造基于高次剩余的匿名IBE方案中扮演了重要的角色。