Post-quantum zero knowledge in constant rounds

Nir Bitansky; Omri Shmueli

doi:10.1145/3357713.3384324

Post-quantum zero knowledge in constant rounds

Nir Bitansky, Omri Shmueli

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We construct a constant-round zero-knowledge classical argument for NP secure against quantum attacks. We assume the existence of Quantum Fully-Homomorphic Encryption and other standard primitives, known based on the Learning with Errors Assumption for quantum algorithms. As a corollary, we also obtain a constant-round zero-knowledge quantum argument for QMA. At the heart of our protocol is a new no-cloning non-black-box simulation technique.

Original language	English (US)
Title of host publication	STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
Editors	Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
Publisher	Association for Computing Machinery
Pages	269-279
Number of pages	11
ISBN (Electronic)	9781450369794
DOIs	https://doi.org/10.1145/3357713.3384324
State	Published - Jun 8 2020
Event	52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, United States Duration: Jun 22 2020 → Jun 26 2020

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0737-8017

Conference

Conference	52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020
Country/Territory	United States
City	Chicago
Period	6/22/20 → 6/26/20

Keywords

Non-black-box simulation
Post-quantum cryptography
Zero-knowledge

ASJC Scopus subject areas

Software

Access to Document

10.1145/3357713.3384324

Cite this

Bitansky, N., & Shmueli, O. (2020). Post-quantum zero knowledge in constant rounds. In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, & J. Chuzhoy (Eds.), STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (pp. 269-279). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3357713.3384324

Post-quantum zero knowledge in constant rounds. / Bitansky, Nir; Shmueli, Omri.
STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. ed. / Konstantin Makarychev; Yury Makarychev; Madhur Tulsiani; Gautam Kamath; Julia Chuzhoy. Association for Computing Machinery, 2020. p. 269-279 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bitansky, N & Shmueli, O 2020, Post-quantum zero knowledge in constant rounds. in K Makarychev, Y Makarychev, M Tulsiani, G Kamath & J Chuzhoy (eds), STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 269-279, 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, United States, 6/22/20. https://doi.org/10.1145/3357713.3384324

Bitansky N, Shmueli O. Post-quantum zero knowledge in constant rounds. In Makarychev K, Makarychev Y, Tulsiani M, Kamath G, Chuzhoy J, editors, STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. 2020. p. 269-279. (Proceedings of the Annual ACM Symposium on Theory of Computing). doi: 10.1145/3357713.3384324

Bitansky, Nir ; Shmueli, Omri. / Post-quantum zero knowledge in constant rounds. STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. editor / Konstantin Makarychev ; Yury Makarychev ; Madhur Tulsiani ; Gautam Kamath ; Julia Chuzhoy. Association for Computing Machinery, 2020. pp. 269-279 (Proceedings of the Annual ACM Symposium on Theory of Computing).

@inproceedings{a42315cffc7744ef9f08ba81f43350ce,

title = "Post-quantum zero knowledge in constant rounds",

abstract = "We construct a constant-round zero-knowledge classical argument for NP secure against quantum attacks. We assume the existence of Quantum Fully-Homomorphic Encryption and other standard primitives, known based on the Learning with Errors Assumption for quantum algorithms. As a corollary, we also obtain a constant-round zero-knowledge quantum argument for QMA. At the heart of our protocol is a new no-cloning non-black-box simulation technique.",

keywords = "Non-black-box simulation, Post-quantum cryptography, Zero-knowledge",

author = "Nir Bitansky and Omri Shmueli",

note = "Publisher Copyright: {\textcopyright} 2020 ACM.; 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 ; Conference date: 22-06-2020 Through 26-06-2020",

year = "2020",

month = jun,

day = "8",

doi = "10.1145/3357713.3384324",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "269--279",

editor = "Konstantin Makarychev and Yury Makarychev and Madhur Tulsiani and Gautam Kamath and Julia Chuzhoy",

booktitle = "STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing",

}

TY - GEN

T1 - Post-quantum zero knowledge in constant rounds

AU - Bitansky, Nir

AU - Shmueli, Omri

PY - 2020/6/8

Y1 - 2020/6/8

N2 - We construct a constant-round zero-knowledge classical argument for NP secure against quantum attacks. We assume the existence of Quantum Fully-Homomorphic Encryption and other standard primitives, known based on the Learning with Errors Assumption for quantum algorithms. As a corollary, we also obtain a constant-round zero-knowledge quantum argument for QMA. At the heart of our protocol is a new no-cloning non-black-box simulation technique.

AB - We construct a constant-round zero-knowledge classical argument for NP secure against quantum attacks. We assume the existence of Quantum Fully-Homomorphic Encryption and other standard primitives, known based on the Learning with Errors Assumption for quantum algorithms. As a corollary, we also obtain a constant-round zero-knowledge quantum argument for QMA. At the heart of our protocol is a new no-cloning non-black-box simulation technique.

KW - Non-black-box simulation

KW - Post-quantum cryptography

KW - Zero-knowledge

UR - http://www.scopus.com/inward/record.url?scp=85086767819&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85086767819&partnerID=8YFLogxK

U2 - 10.1145/3357713.3384324

DO - 10.1145/3357713.3384324

M3 - Conference contribution

AN - SCOPUS:85086767819

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 269

EP - 279

BT - STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Makarychev, Konstantin

A2 - Makarychev, Yury

A2 - Tulsiani, Madhur

A2 - Kamath, Gautam

A2 - Chuzhoy, Julia

PB - Association for Computing Machinery

T2 - 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020

Y2 - 22 June 2020 through 26 June 2020

ER -

Post-quantum zero knowledge in constant rounds

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this