Some New Consequences of the Hypothesis That P Has Fixed Polynomial-Size Circuits

被引：3

作者：

Ding, Ning ^{[1
,2
]}

机构：

[1] Shanghai Jiao Tong Univ, Dept Comp Sci & Engn, Shanghai 200030, Peoples R China

[2] NTT Secure Platform Labs, Tokyo, Japan

来源：

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2015) | 2015年 / 9076卷

关键词：

LOWER BOUNDS;

D O I：

10.1007/978-3-319-17142-5_8

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present some new consequences of the hypothesis that P can be computed by fixed polynomial-size circuits since [Lipton SCTC 94]. For instance, we show that the hypothesis implies that some small circuit family and BPP machines cannot be fooled by any complexity-theoretic pseudorandom generator G : {0, 1}(Theta(log n)) to {0, 1}(n), which means the known derandomization argument of BPP = P no longer works. It also implies the existence of 2-round public-coin zero-knowledge proofs for NP.

引用

页码：75 / 86

页数：12

共 20 条

[1] Lower bounds for non-black-box zero knowledge [J].

Barak, B ;

Lindell, Y ;

Vadhan, S .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2006, 72 (02) :321-391

[2] Nonrelativizing separations [J].

Buhrman, H ;

Fortnow, L ;

Thierauf, T .

THIRTEENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY - PROCEEDINGS, 1998, :8-12

[3] Zaps and their applications [J].

Dwork, C ;

Naor, M .

41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2000, :283-293

[4] Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits (Extended Abstract) [J].

Garg, Sanjam ;

Gentry, Craig ;

Halevi, Shai ;

Raykova, Mariana ;

Sahai, Amit ;

Waters, Brent .

2013 IEEE 54TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2013, :40-49

[5] How to construct constant-round zero-knowledge proof systems for NP [J].

Goldreich, O ;

Kahan, A .

JOURNAL OF CRYPTOLOGY, 1996, 9 (03) :167-189

[6]

GOLDREICH O, 1994, J CRYPTOL, V7, P1, DOI 10.1007/BF00195207

[7] THE KNOWLEDGE COMPLEXITY OF INTERACTIVE PROOF SYSTEMS [J].

GOLDWASSER, S ;

MICALI, S ;

RACKOFF, C .

SIAM JOURNAL ON COMPUTING, 1989, 18 (01) :186-208

[8] A pseudorandom generator from any one-way function [J].

Hästad, J ;

Impagliazzo, R ;

Levin, LA ;

Luby, M .

SIAM JOURNAL ON COMPUTING, 1999, 28 (04) :1364-1396

[9]

Impagliazzo R., 1997, STOC 1997, P220, DOI DOI 10.1145/258533.258590

[10]

Iwama K, 2002, LECT NOTES COMPUT SC, V2420, P353

← 1 2 →