NDLI: On Basing ZK ≠ BPP on the Hardness of PAC Learning

Content Provider	IEEE Xplore Digital Library
Author	Xiao, D.
Copyright Year	2009
Abstract	Learning is a central task in computer science, and there are various formalisms for capturing the notion. One important model studied in computational learning theory is the PAC model of Valiant (CACM 1984). On the other hand, in cryptography the notion of "learning nothing'' is often modelled by the simulation paradigm: in an interactive protocol, a party learns nothing if it can produce a transcript of the protocol by itself that is indistinguishable from what it gets by interacting with other parties. The most famous example of this paradigm is zero knowledge proofs, introduced by Goldwasser, Micali, and Rackoff (SICOMP 1989). Applebaum et al. (FOCS 2008) observed that a theorem of Ostrovsky and Wigderson (ISTCS 1993) combined with the transformation of one-way functions to pseudo-random functions (Hastad et al. SICOMP 1999, Goldreich et al. J. ACM 1986) implies that if there exist non-trivial languages with zero-knowledge arguments, then no efficient algorithm can PAC learn polynomial-size circuits. They also prove a weak reverse implication, that if a certain non-standard learning task is hard, then zero knowledge is non-trivial. This motivates the question we explore here: can one prove that hardness of PAC learning is equivalent to non-triviality of zero-knowledge? We show that this statement cannot be proven via the following techniques: 1. Relativizing techniques: there exists an oracle relative to which learning polynomial-size circuits is hard and yet the class of languages with zero knowledge arguments is trivial. 2. Semi-black-box techniques: if there is a black-box construction of a zero-knowledge argument for an NP-complete language (possibly with a non-black-box security reduction) based on hardness of PAC learning, then NP has statistical zero knowledge proofs, namely NP is contained in SZK. Under the standard conjecture that NP is not contained in SZK, our results imply that most standard techniques do not suffice to prove the equivalence between the non-triviality of zero knowledge and the hardness of PAC learning. Our results hold even when considering non-uniform hardness of PAC learning with membership queries. In addition, our technique relies on a new kind of separating oracle that may be of independent interest.
Starting Page	304
Ending Page	315
File Size	404539
Page Count	12
File Format	PDF
ISBN	9780769537177
ISSN	10930159
DOI	10.1109/CCC.2009.11
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-07-15
Publisher Place	France
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Circuits Computational modeling Cryptography Polynomials Computer science Cryptographic protocols Computational complexity Security relativizing PAC learning zero knowledge complexity cryptography black-box
Content Type	Text
Resource Type	Article

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

On basing ZK ̸= BPP on the hardness of pac learning (2009)

A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP

Constant-Round Concurrent Zero Knowledge from P-Certificates

Subquadratic zero-knowledge

Parallel repetition of zero-knowledge proofs and the possibility of basing cryptography on NP-hardness

How to go beyond the black-box simulation barrier

Concurrent Non-Malleable Zero Knowledge

Statistical Zero-Knowledge Arguments for NP from Any One-Way Function

An unconditional study of computational zero knowledge (2006).

On Basing ZK ≠ BPP on the Hardness of PAC Learning

Similar Documents

On basing ZK ̸= BPP on the hardness of pac learning (2009)

A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP

Constant-Round Concurrent Zero Knowledge from P-Certificates

Subquadratic zero-knowledge

Parallel repetition of zero-knowledge proofs and the possibility of basing cryptography on NP-hardness

How to go beyond the black-box simulation barrier

Concurrent Non-Malleable Zero Knowledge

Statistical Zero-Knowledge Arguments for NP from Any One-Way Function

An unconditional study of computational zero knowledge (2006).

On Basing ZK ≠ BPP on the Hardness of PAC Learning