NDLI: Magic Functions: In Memoriam: Bernard M. Dwork 1923--1998

Content Provider	ACM Digital Library
Author	Dwork, Cynthia Naor, Moni Reingold, Omer Stockmeyer, Larry
Copyright Year	2003
Abstract	We prove that three apparently unrelated fundamental problems in distributed computing, cryptography, and complexity theory, are essentially the same problem. These three problems and brief descriptions of them follow. (1) The selective decommitment problem. An adversary is given commitments to a collection of messages, and the adversary can ask for some subset of the commitments to be opened. The question is whether seeing the decommitments to these open plaintexts allows the adversary to learn something unexpected about the plaintexts that are unopened. (2) The power of 3-round weak zero-knowledge arguments. The question is what can be proved in (a possibly weakened form of) zero-knowledge in a 3-round argument. In particular, is there a language outside of BPP that has a 3-round public-coin weak zero-knowledge argument? (3) The Fiat-Shamir methodology. This is a method for converting a 3-round public-coin argument (viewed as an identification scheme) to a 1-round signature scheme. The method requires what we call a "magic function" that the signer applies to the first-round message of the argument to obtain a second-round message (queries from the verifier). An open question here is whether every 3-round public-coin argument for a language outside of BPP has a magic function.It follows easily from definitions that if a 3-round public-coin argument system is zero-knowledge in the standard (fairly strong) sense, then it has no magic function. We define a weakening of zero-knowledge such that zero-knowledge ⇒ no-magic-function still holds. For this weakened form of zero-knowledge, we give a partial converse: informally, if a 3-round public-coin argument system is not weakly zero-knowledge, then some form of magic is possible for this argument system. We obtain our definition of weak zero-knowledge by a sequence of weakenings of the standard definition, forming a hierarchy. Intermediate forms of zero-knowledge in this hierarchy are reasonable ones, and they may be useful in applications. Finally, we relate the selective decommitment problem to public-coin proof systems and arguments at an intermediate level of the hierarchy, and obtain several positive security results for selective decommitment.
Starting Page	852
Ending Page	921
Page Count	70
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/950620.950623
Journal	Journal of the ACM (JACM)
Volume Number	50
Issue Number	6
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2003-11-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Digital signature Fiat-Shamir methodology Interactive argument Interactive proof system Magic function Selective decommitment Zero knowledge
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

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

Magic functions (2000).

The theory of cryptography conference- tcc 2013 — on the (in)security of the fiat-shamir paradigm, revisited.

On the (in)security of fischlin’s paradigm.

Some remarks on signature schemes based on the zero-knowledge technique.

An improved parallel interactive Feige-Fiat-Shamir identification scheme with almost zero soundness error and complete zero-knowledge

On the length of hash-values for digital signature schemes.

On the (In)security of the Fiat-Shamir Paradigm (2003)

On the (In)security of the Fiat-Shamir Paradigm

On Protocol Divertibility (1998)

Magic Functions: In Memoriam: Bernard M. Dwork 1923--1998

Similar Documents

Magic functions (2000).

The theory of cryptography conference- tcc 2013 — on the (in)security of the fiat-shamir paradigm, revisited.

On the (in)security of fischlin’s paradigm.

Some remarks on signature schemes based on the zero-knowledge technique.

An improved parallel interactive Feige-Fiat-Shamir identification scheme with almost zero soundness error and complete zero-knowledge

On the length of hash-values for digital signature schemes.

On the (In)security of the Fiat-Shamir Paradigm (2003)

On the (In)security of the Fiat-Shamir Paradigm

On Protocol Divertibility (1998)

Magic Functions: In Memoriam: Bernard M. Dwork 1923--1998