Zero knowledge and circuit minimization

被引：20

作者：

Allender, Eric ^{[1
]}

Das, Bireswar ^{[2
]}

机构：

[1] Rutgers State Univ, Dept Comp Sci, Piscataway, NJ 08854 USA

[2] IIT Gandhinagar, Ahmadabad, Gujarat, India

来源：

INFORMATION AND COMPUTATION | 2017年 / 256卷

关键词：

Graph Isomorphism; Minimum Circuit Size Problem; NP-intermediate problem; Statistical Zero Knowledge; PROOF SYSTEMS; COMPLEXITY; LANGUAGES; NP;

D O I：

10.1016/j.ic.2017.04.004

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that every problem in the complexity class SZK(Statistical Zero Knowledge) is efficiently reducible to the Minimum Circuit Size Problem (MCSP). In particular Graph Isomorphism lies in RPMCSP. DThis is the first theorem relating the computational power of Graph Isomorphism and MCSP, despite the long history these problems share, as candidate NP-intermediate problems. (C) 2017 Elsevier Inc. All rights reserved.

引用

页码：2 / 8

页数：7

共 30 条

[1] STATISTICAL ZERO-KNOWLEDGE LANGUAGES CAN BE RECOGNIZED IN 2 ROUNDS
AIELLO, W
HASTAD, J
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1991, 42 (03) : 327 - 345
[2] Power from random strings
Allender, E
Buhrman, H
Koucky, M
Van Melkebeek, D
Ronneburger, D
[J]. SIAM JOURNAL ON COMPUTING, 2006, 35 (06) : 1467 - 1493
[3] [Anonymous], 2003, Computational discrete mathematics: combinatorics and graph theory with Mathematica, DOI DOI 10.1017/CBO9781139164849
[4] [Anonymous], 1997, STOC 1997, DOI DOI 10.1145/258533.258590
[5] Arora S, 2009, COMPUTATIONAL COMPLEXITY: A MODERN APPROACH, P1, DOI 10.1017/CBO9780511804090
[6] SZK proofs for black-box group problems
Arvind, V.
Das, Bireswar
[J]. THEORY OF COMPUTING SYSTEMS, 2008, 43 (02) : 100 - 117
[7] Arvind V., 2005, B EUR ASS THEOR COMP, V86
[8] Babai Laszlo, 2016, ACM S THEOR COMP STO
[9] Trading help for interaction in statistical zero-knowledge proofs
Ben-Or, M
Gutfreund, D
[J]. JOURNAL OF CRYPTOLOGY, 2003, 16 (02) : 95 - 116
[10] Ben-Or Michael, 1990, ADV CRYPTOLOGY CRYPT, V88, P37

← 1 2 3 →