量子计算机的发展,对传统公钥密码体制(如RSA、ElGamal等)构成了极大的威胁.为此,具有“抗量子计算”性质的公钥密码受到了广泛关注,目前提出的抗Shor量子算法攻击的公钥密码,主要有基于格问题的NTRU算法、基于Hash函数的签名算法、基于纠错码的公钥密码体制以及多变量二次多项式(简称MQ)公钥密码体制等类型.近几年,MQ公钥密码引起了密码界的极大兴趣,它是抗量子计算公钥密码学领域最为活跃的研究分支,其安全性是基于有限域上多变量二次方程组的难解性问题.除了具有抗量子计算的性质外,它的最大优点是实现效率高,不需要密码协处理器,非常适合智能卡等计算资源有限的嵌入式设备.例如,2003年被欧洲NESSIE工程选定的SFLASH就是专门为其特殊应用而设计的一种快速签名算法.不幸的是,2007年Dubois等人利用差分攻击成功破译了SFLASH签名算法.目前,绝大多数MQ公钥密码算法已被成功破译,这些有效攻击方法的出现,使人们对MQ公钥密码体制的安全性产生了质疑.同时,传统MQ公钥密码只能用于签名,不具备安全的加密功能,人们希望能构造出既能签名又能加密的MQ公钥密码体制.其次,近年来的研究结果表明,目前使用最广泛的Hash函数如MD5和SHA系列等已不安全,新型Hah函数的设计已刻不容缓.美国国家标准和技术研究所在2005年10月和2006年8月举办了两次研讨会,评估了这些Hash函数的使用状况,决定公开征集新一代Hash函数标准SHA-3.目前共有14个候选算法进入第二轮评选,预计这一计划将在2012年完成.鉴于上述背景,本文对MQ公钥密码进行了深入研究,我们借鉴Merkle树签名算法和纠错公钥密码算法的设计思想,并结合传统MQ公钥密码结构特征,通过引入Hash认证技术,提出了扩展MQ公钥密码系统.其基本思想是对传统MQ密码的算法空间进行拓展.我们通过构造基于Hash函数的Tame变换,将传统MQ密码的公钥映射拓展隐藏到更大算法空间中得到新的公钥映射,增加了内部扰动变量,但却并未改变原公钥映射的可逆性质.从攻击者的角度,由于无法从新公钥中成功分解出原来的公钥映射,因此必须在拓展空间中求解更大规模的不定非线性方程组,这相当于对传统MQ公钥方案使用了“减模式”方法,提升了原算法的安全性.因此,可由此构造安全的MQ公钥加密方案,使MQ类公钥密码系统具有安全的加密功能.此外,扩展MQ公钥密码系统中引入了Hash认证技术,攻击者伪造签名时,伪造的签名不仅要满足传统公钥方程、还要通过Hash函数认证,双重安全性保护极大地提升了传统MQ公钥签名算法的安全性.其次,我们对扩展MQ密码系统进行了探索性的简化改进,将底层MQ公钥密码算法替换成线性变换,构造了一种新型轻量级数字签名方案.该算法在效率方面优于目前所有的数字签名算法.另外,本文还将传统MQ公钥体制与纠错密码理论结合起来、构造了一种安全的扩展MQ加密方案,同时给出一个80比特安全性的实用加密方案,并进行安全性及效能分析.本文在深入研究MQ公钥密码算法的同时,还对MQ问题在Hash函数领域中的应用作了深入的研究.我们根据理论分析和大量实验数据阐述了利用MQ问题构造Hash函数的可行性.并结合HAIFA迭代框架,提出了一种新型Hash函数.新Hash算法与目前广泛使用的Hash算法相比具有下列优点：安全性基于一个公认的数学难题,且在MQ难解性问题的假设前提下,可达到理想Hash函数的安全性强度;输出Hash值长度可变；设计自动化,用户可根据实际需求构造满足其特定要求的Hash函数.此外,由于新算法具有良好的随机性,还可将其作为一种伪随机数生成器.归结起来讲,本文的主要结论有如下几个方面：1.提出了扩展MQ公钥密码方案的概念.分别给出扩展MQ加密和签名方案的构造方法,深入分析了这些方案的安全性,并做了详细的性能评估和方案的参数优化推荐.2.对扩展MQ签名方案进行了的简化改进,构造了一种新型轻量级数字签名方案.实验表明,该算法在效率方面优于目前所有的数字签名算法.3.将传统MQ公钥体制与纠错密码理论结合起来、构造了一种安全的扩展MQ加密方案,同时给出一个80比特安全性的实用加密方案,并进行安全性及效能分析.4.利用扩展MQ问题(即有限域上次数大于2次的非线性方程组的求解问题)的难解性,构造了一种新型的多变量Hash函数,并给出了加速实现算法和存储空间优化算法.同时还详细分析了新Hash算法的安全性,通过大量的实验数据阐述了利用MQ问题构造Hash函数的可行性.