Interactive Coding for Interactive Proofs

被引：2

作者：

Bishop, Allison ^{[1
]}

Dodis, Yevgeniy ^{[2
]}

机构：

[1] Columbia Univ, New York, NY USA

[2] NYU, New York, NY USA

来源：

THEORY OF CRYPTOGRAPHY, TCC 2016-A, PT II | 2016年 / 9563卷

关键词：

CONSTRUCTIONS;

D O I：

10.1007/978-3-662-49099-0_13

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider interactive proof systems over adversarial communication channels. We show that the seminal result that IP = PSPACE still holds when the communication channel is malicious, allowing even a constant fraction of the communication to be arbitrarily corrupted.

引用

页码：352 / 366

页数：15

共 25 条

[1]

Agrawal S., 2013, ADAPTIVE PROTO UNPUB

[2] SIMPLE CONSTRUCTIONS OF ALMOST K-WISE INDEPENDENT RANDOM-VARIABLES [J].

ALON, N ;

GOLDREICH, O ;

HASTAD, J ;

PERALTA, R .

RANDOM STRUCTURES & ALGORITHMS, 1992, 3 (03) :289-304

[3]

[Anonymous], 1986, P 18 S THEOR COMP, DOI DOI 10.1145/12130.12137

[4]

Bellare M., 1993, Computational Complexity, V3, P319, DOI 10.1007/BF01275487

[5] Efficient Interactive Coding Against Adversarial Noise [J].

Brakerski, Zvika ;

Kalai, Yael Tauman .

2012 IEEE 53RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2012, :160-166

[6]

Braverman M, 2011, ACM S THEORY COMPUT, P159

[7]

Braverman Mark, 2012, Innovations in Theoretical Computer Science Conference ITCS, P161, DOI 10.1145/2090236.20902502

[8]

Braverman Mark, 2014, FOCS

[9]

Chung K.-M., 2013, FOCS

[10]

Chung KM, 2010, LECT NOTES COMPUT SC, V5978, P19, DOI 10.1007/978-3-642-11799-2_2

← 1 2 3 →