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
Agrawal, M
Allender, E
Rudich, S
[J]. 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
BLUM, M
MICALI, S
[J]. SIAM JOURNAL ON COMPUTING, 1984, 13 (04) : 850 - 864
[7] NEW DIRECTIONS IN CRYPTOGRAPHY
DIFFIE, W
HELLMAN, ME
[J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 1976, 22 (06) : 644 - 654
[8] A PUBLIC KEY CRYPTOSYSTEM AND A SIGNATURE SCHEME BASED ON DISCRETE LOGARITHMS
ELGAMAL, T
[J]. 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

← 1 2 3 →