Magic Functions

In this paper we show that three apparently unrelated problems are in fact very closely related. We sketch these problems at a high level. The selective decommitment problem first arose in a slightly different form, selective decryption, in the context of Byzantine agreement, no later than 1985. Instead of seeing encryptions of plaintexts the adversary is given commitments to the plaintexts. This problem is poorly understood even in strong-receiver commitments, which leak no information about the plaintext values information-theoretically. The second problem is in complexity theory: what can be proved in (a possibly weakened form of) zero-knowledge in a 3-round argument (interactive proof in which the prover is polynomial-time bounded)? The Fiat-Shamir Methodology is cryptographic, and addresses a methodology suggested by Fiat and Shamir (1987) to construct a (non-interactive) signature scheme from any 3-round (not necessarily zero-knowledge) public-coin identification scheme.

Authors

• Cynthia Dwork
• Moni Naor
• Omer Reingold
• Larry J. Stockmeyer

Keywords

• Cryptography
• Postal services
• Computer science
• Mathematics
• Switches
• Microwave integrated circuits
• Security
• Complexity theory
• Polynomials
• Roads
• Deterministic
• Decoding
• Interesting Question
• Results In Cases
• Data Privacy
• Plaintext
• Analogous Results
• Secret Key
• Public Key
• Security Parameter
• Hard Core
• Random String
• Hardness Results
• Random Oracle
• Signature Scheme
• Probabilistic Polynomial Time
• Zero-knowledge Proof
• Type Of Security