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.