TY - GEN

T1 - Post-quantum zero knowledge in constant rounds

AU - Bitansky, Nir

AU - Shmueli, Omri

N1 - Publisher Copyright:
© 2020 ACM.

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 -