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

Public Key Cryptography Based on Average-Case Complexity

作　　者：赵一鸣[1] 鲍振东[1] 

机构地区：[1]复旦大学计算机系,上海200433

出　　处：《计算机科学》2000年第5期22-25,共4页Computer Science

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

关 键 词：公钥密码 平均复杂性 密码学 离散对数 

分 类 号：TN918.2[电子电信—通信与信息系统]