格的归约理论和它在密码学中的应用

Lattice Rounding Technique and Its Cryptographic Applications

介绍和讨论了格理论在公钥密码体制中的应用。利用格的归约技术可以分析研究计算部分密钥位与整个密钥位的计算复杂性。在均匀模式下,计算基于公钥系统的Okamoto协议的2 log log p密钥位与计算整个密钥的难度是相同的。用格的理论建立了一个公钥密码系统,且该系统是安全的,除非能够在多项式时间内从n维格L中找到最短的非零向量。

This paper introduces and discusses of lattice rounding technique and its cryptographic applications. Using lattice rounding technique, it analyzes the hardness of computing the most significant bits of key and the entire secret. In a non - uniform model computing the 21oglogp bits of the secret key in Okamoto' s scheme is as hard as computing the entire key. And we can construct a public key cryptosystem, which is secure unless the problem that found the shortest nonzero vector in a lattice L can be solved in polynomial time.