NDLI: Zero-Knowledge against Quantum Attacks

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Watrous, John
Copyright Year	2009
Abstract	This paper proves that several interactive proof systems are zero-knowledge against general quantum attacks. This includes the well-known GoldreichMicaliWigderson classical zero-knowledge protocols for graph isomorphism and graph 3-coloring (assuming the existence of quantum computationally concealing commitment schemes in the second case). Also included is a quantum interactive proof system for a complete problem for the complexity class of problems having honest verifier quantum statistical zero-knowledge proofs, which therefore establishes that honest verifier and general quantum statistical zero-knowledge are equal: $\mathrm{QSZK}= \mathrm{QSZK}_{\mathrm{HV}}$. Previously no nontrivial interactive proof systems were known to be zero-knowledge against quantum attacks, except in restricted settings such as the honest verifier and common reference string models. This paper therefore establishes for the first time that true zero-knowledge is indeed possible in the presence of quantum information and computation.
Starting Page	25
Ending Page	58
Page Count	34
File Format	PDF
ISSN	00975397
DOI	10.1137/060670997
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	1 (Special Issue On The Thirty-Eighth Annual ACM Symposium On Theory Of Computing (STOC 2006))
Volume Number	39
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2009-05-28
Access Restriction	Subscribed
Subject Keyword	Modes of computation Quantum computation quantum cryptography interactive proof systems zero-knowledge
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Zero-knowledge against quantum attacks

The Knowledge Complexity of Interactive Proof Systems

On the Composition of Zero-Knowledge Proof Systems

Minimum-Knowledge Interactive Proofs for Decision Problems

Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete

Memorizable interactive proof and zero-knowledge proof systems

Witness indistinguishability and witness hiding against quantum attacks

2-round zero knowledge and proof auditors

Sharp: Short Relaxed Range Proofs

Zero-Knowledge against Quantum Attacks

Similar Documents

Zero-knowledge against quantum attacks

The Knowledge Complexity of Interactive Proof Systems

On the Composition of Zero-Knowledge Proof Systems

Minimum-Knowledge Interactive Proofs for Decision Problems

Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete

Memorizable interactive proof and zero-knowledge proof systems

Witness indistinguishability and witness hiding against quantum attacks

2-round zero knowledge and proof auditors

Sharp: Short Relaxed Range Proofs

Zero-Knowledge against Quantum Attacks