基于平均复杂性的公钥密码研究

1 引言在近代密码学特别是公钥密码系统的研究中,密码系统的安全性都是基于难解的可计算问题的,如大数分解问题、计算有限域的离散对数问题、平方剩余问题以及椭圆曲线的对数问题等。必须指出的是,关于平均复杂性的研究因远比最坏情况下的复杂性研究要难得多,所以目前密码系统的安全性都是建立在最坏情

Public Key Cryptography Based on Average-Case Complexity

In this survey we review the most recent result,from which we can construct a cryptosystem whose security is based on average-case complexity. Using lattice rounding technique,we analyze the hardness of computing the most significant bits of key and the entire secret. And we can construct a public key cryptosystem that is secure unless the problem which found the shortest nonzero vector in a lattice L can be solved in polynomial time. Based on the relation between the worst-case complexity and the average-case one ,we introduce the problem finding large cliques in random graphs. Assuming the hardness of finding large cliques in random graphs,we can state that when a clique of sufficiently large size is randomly inserted into a random graph G,yielding graph G' ,finding any large clique in G' is still hard. The result can be constructed a new one-way function.