Pseudo-random generators and structure of complete degrees

被引：21
作者：
Agrawal, M [1 ]
机构：
[1] Indian Inst Technol, Dept CSE, Kanpur 208016, Uttar Pradesh, India
来源：
17TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS | 2002年
关键词：
D O I：
10.1109/CCC.2002.1004349
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
It is shown that if there exist sets in E that require 2(Omega(n))-sized circuits then sets that are hard for class P, and above, under 1-1 reductions are also hard under 1-1, size-increasing reductions. Under the assumption of the hardness of solving RSA or Discrete Log problem, it is shown that sets that are hard for class NP, and above, under many-one reductions are also hard under (non-uniform) 1-1, and size-increasing reductions.
引用
收藏
页码：139 / 147
页数：9
相关论文
共 21 条
[1]   Reductions in circuit complexity: An isomorphism theorem and a gap theorem [J].
Agrawal, M ;
Allender, E ;
Rudich, S .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1998, 57 (02) :127-143
[2]  
AGRAWAL M, 2001, P 21 FST TCS
[3]  
[Anonymous], 1982, 23 ANN S FDN COMPUTE, DOI DOI 10.1109/SFCS.1982.45
[4]  
Berman L., 1977, SIAM Journal on Computing, V6, P305, DOI 10.1137/0206023
[5]  
BERMAN L, 1977, THESIS CORNELL U
[6]   HOW TO GENERATE CRYPTOGRAPHICALLY STRONG SEQUENCES OF PSEUDO-RANDOM BITS [J].
BLUM, M ;
MICALI, S .
SIAM JOURNAL ON COMPUTING, 1984, 13 (04) :850-864
[7]   NEW DIRECTIONS IN CRYPTOGRAPHY [J].
DIFFIE, W ;
HELLMAN, ME .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1976, 22 (06) :644-654
[8]   A PUBLIC KEY CRYPTOSYSTEM AND A SIGNATURE SCHEME BASED ON DISCRETE LOGARITHMS [J].
ELGAMAL, T .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1985, 31 (04) :469-472
[9]  
GANESAN K, 1989, LECT NOTES COMPUT SC, V349, P240
[10]  
Goldreich O., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P25, DOI 10.1145/73007.73010
123