基于大整数因子分级和离散对数的传统公钥密码体制运算速度比较慢,这限制了它们的应用范围。随着量子计算的发展,基于新型困难问题密码算法设计的重要性被提升到了一个前所未有的高度。基于格困难问题的快速公钥算法是新型密码设计的一个重要方向,本文对此进行了研究,取得了如下成果:(1)给出了一条NTRU加密算法参数选择规则:要求NTRU的三个参数n,p,q满足分圆多项式在GF(p)和GF(q)上不可分解。此时,对于环R = Z[x]/(x~n - 1)的任意一个多项式,只要满足f(1) = 0,f在模p和模q意义下的逆一定存在。这不仅保证了密钥生成的效率,而且避免了弱密钥的产生。(2)当NTRU的公钥h与x~n -1的在环R = Z[x]/(x~n -1)上的最大公因式gcd(h,x~n -1)的次数不为零时,构造了一种类似于循环码译码的方法结合格基规约算法破解用h加密产生的密文。进一步的,若gcd(h,x~n - 1)的次数为k,攻击者只需用格基规约算法求解(n - k)维格中的SVP问题即可得到明文。(3)对三轮OAEP明文填充方案进行了分析,指出当攻击者可以获得填充方案中的随机串时,三轮OAEP并不能让RSA,ELGamal等加密算法达到适应性选择密文攻击下的语义安全性。对三轮OAEP进行了改进,使其在填充算法中随机串泄露的情况下仍然可以让加密算法达到适应性选择密文攻击下的语义安全性,并在随机预言机模型下证明了这个结论。(4)为NTRU加密算法设计了一个明文填充方案。在加密算法选择适当参数保证合法加密不会发生解密失败的条件下,该填充方案能使NTRU达到适应性选择密文攻击下的语义安全性。与现有的NTRU明文填充方案NAEP相比,我们的填充算法更简洁更便于实现。(5)提出了一种改进的NTRU加密算法。改进算法解密时能精确消除加密过程中所用的工作密钥,避免了像NTRU那样公钥所对应的CS格中任意足够短的向量都可以用来解密的情况。只有原密钥向量可以用来解密使得格基规约技术不能直接攻击改进算法,这是以计算量和密钥长度的增加为代价的。为改进算法设计了一种明文填充方案,并在随机预言机模型下证明了填充方案在适应性选择密文攻击下的语义安全性。