%0 Journal Article
%T Public Key Cryptography Based on Average-Case Complexity<br>基于平均复杂性的公钥密码研究
%A 赵一鸣
%A 鲍振东
%J 计算机科学
%D 2000
%I 
%X 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.
%K Average-case complexity
%K Lattices
%K Public key cryptosystem<br>公钥密码
%K 平均复杂性
%K 密码学
%K 离散对数
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=AB0EB125F1AB8FA4&yid=9806D0D4EAA9BED3&vid=DB817633AA4F79B9&iid=94C357A881DFC066&sid=BC12EA701C895178&eid=C5154311167311FE&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=9