Customized and zero-knowledge identification protocols
This section considers protocols specifically designed to achieve identification, which use asymmetric techniques but do not rely on digital signatures or public-key encryption, and which avoid use of block ciphers, sequence numbers, and timestamps. They are similar in some regards to the challenge-response protocols of §10.3, but are based on the ideas of interactive proof systems and zero-knowledge proofs (see §10.4.1), employing random numbers not only as challenges, but also as commitments to prevent cheating.
Overview of zero-knowledge concepts
A disadvantage of simple password protocols is that when a claimant A (called a prover in the context of zero-knowledge protocols) gives the verifier В her password, В can thereafter impersonate A. Challenge-response protocols improve on this: A responds to B’s challenge to demonstrate knowledge of A’s secret in a tune-variant manner, providing information not directly reusable by B. This might nonetheless reveal some partial information about the claimant’s secret; an adversarial verifier might also be able to strategically select challenges to obtain responses providing such information (see chosen-text attacks, §10.5).
Zero-knowledge (ZK) protocols are designed to address these concerns, by allowing a prover to demonstrate knowledge of a secret while revealing no information whatsoever (beyond what the verifier was able to deduce prior to the protocol run) of use to the verifier in conveying this demonstration of knowledge to others. The point is that only a single bit of information need be conveyed - namely, that the prover actually does know the secret.
More generally, a zero-knowledge protocol allows a proof of the truth of an assertion, while conveying no information whatsoever (this notion can be quantified in a rigorous sense) about the assertion itself other than its actual truth. In this sense, a zero-knowledge proof is similar to an answer obtained from a (trusted) oracle.
(i) Interactive proof systems and zero-knowledge protocols
The ZK protocols to be discussed are instances of interactive proof systems, wherein a prover and verifier exchange multiple messages (challenges and responses), typically dependent on random numbers (ideally: the outcomes of fair coin tosses) which they may keep secret. The prover’s objective is to convince (prove to) the verifier the truth of an assertion, e.g., claimed knowledge of a secret. The verifier either accepts or rejects the proof. The traditional mathematical notion of a proof, however, is altered to an interactive game wherein proofs are probabilistic rather than absolute; a proof in this context need be correct only with bounded probability, albeit possibly arbitrarily close to 1. For this reason, an interactive proof is sometimes called a proof by protocol.
Interactive proofs used for identification may be formulated as proofs of knowledge. A possesses some secret s, and attempts to convince В it has knowledge of s by correctly responding to queries (involving publicly known inputs and agreed upon functions) which require knowledge of s to answer. Note that proving knowledge of s differs from proving that such s exists - for example, proving knowledge of the prime factors of n differs from provmg that n is composite.
An interactive proof is said to be a proof of knowledge if it has both the properties of completeness and soundness. Completeness may be viewed as the customary requirement that a protocol functions properly given honest participants.
- 10.18 Definition (completeness property) An interactive proof (protocol) is complete if, given an honest prover and an honest verifier, the protocol succeeds with overwhelming probability (i.e., the verifier accepts the prover’s claim). The definition of overwhelming depends on the application, but generally implies that the probability of failure is not of practical significance.
- 10.19 Definition (soundness property0 An interactive proof (protocol) is sound if there exists an expected polynomial-time algorithm M with the following property: if a dishonest prover (impersonating A) can with non-negligible probability successfully execute the protocol with B, then M can be used to extract from this prover knowledge (essentially equivalent to A’s secret) which with overwhelming probability allows successful subsequent protocol executions.
An alternate explanation of the condition in Definition 10.19 is as follows: the prover’s secret s together with public data satisfies some polynomial-time predicate, and another solution of this predicate (possibly the same) can be extracted, allowing successful execution of subsequent protocol instances.
Since any party capable of impersonating A must know the equivalent of , Ts secret knowledge (M can be used to extract it from this party in polynomial time), soundness guarantees that the protocol does indeed provide a proof of knowledge - knowledge equivalent to that being queried is required to succeed. Soundness thus prevents a dishonest prover from convincing an honest verifier (but does does not by itself guarantee that acquiring the prover’s secret is difficult; see Remark 10.23). A standard method to establish the soundness of a particular protocol is to assume the existence of a dishonest prover capable of successfully executing the protocol, and show how this allows one to compute the real prover’s secret.
While an interactive proof of knowledge (or protocol based thereon) must be sound to be of cryptographic use, the main property of zero-knowledge protocols is the zero- knowledge aspect itself. For what follows, define a transcript (or view) to be the collection of messages resulting from protocol execution.
10.20 Definition (zero-knowledge property) A protocol which is a proof of knowledge has the zero-knowledge property> if it is simulatable in the following sense: there exists an expected polynomial-time algorithm (simulator) which can produce, upon input of the assertion(s) to be proven but without interacting with the real prover, transcripts indistinguishable from those resulting from interaction with the real prover.
The zero-knowledge property implies that a prover executing the protocol (even when interacting with a malicious verifier) does not release any information (about its secret knowledge, other than that the particular assertion itself is true) not otherwise computable in polynomial time from public information alone. Tlius, participation does not increase the chances of subsequent impersonation.
- 10.21 Remark (simulated ZK protocols and protocol obscn'ers) Consider an observer C who witnesses a zero-knowledge interactive proof (ZKIP) involving a prover A convincing a verifier В (В Ф C) of some knowledge A has. The “proof” to В does not provide any guarantees to C. (Indeed, A and В might have a prior agreement, conspiring against C, on the challenges to be issued.) Similarly, a recorded ZKIP conveys no guarantees upon playback. This is fundamental to the idea of the zero-knowledge property and the condition that proofs be simulatable by a verifier alone. Interactive proofs convey knowledge only to (interactive) verifiers able to select their own random challenges.
- 10.22 Definition (computational vs. perfect zero-knowledge) A protocol is computationally zero-knowledge if an observer restricted to probabilistic polynomial-tune tests cannot distinguish real from simulated transcripts. For perfect zero-knowledge, the probability distributions of the transcripts must be identical. By convention, when not further qualified, zero-knowledge means computational zero-knowledge.
In the case of computational zero-knowledge, real and simulated transcripts are said to be polynomials indistinguishable (indistinguishable using polynomial-time algorithms). Any information extracted by a verifier through interaction with a prover provides no advantage to the verifier within polynomial time.
- 10.23 Remark (,ZK property' and soundness vs. security') The zero-knowledge property (Definition 10.20) does not guarantee that a protocol is secure (i.e., that the probability of it being easily defeated is negligible). Similarly, the soundness property (Definition 10.19) does not guarantee that a protocol is secure. Neither property has much value unless the underlying problem faced by an adversary is computationally hard.
- (ii) Comments on zero-knowledge vs. other asymmetric protocols
The following observations may be made regarding zero-knowledge (ZK) techniques, as compared with other public-key (PK) techniques.
1. no degradation with usage: protocols proven to have the ZK property do not suffer degradation of security with repeated use, and resist chosen-text attacks. This is perhaps the most appealing practical feature of ZK techniques.
A ZK technique which is not provably secure may or may not be viewed as more desirable than a PK technique which is provably secure (e.g., as difficult as factoring).
- 2. encryption avoided: many ZK techniques avoid use of explicit encryption algorithms. This may offer political advantages (e.g., with respect to export controls).
- 3. efficiency: while some ZK-based techniques are extremely efficient (see §10.4.5), protocols which formally have the zero-knowledge property typically have higher communications and/or computational overheads than PK protocols which do not. The computational efficiency of the more practical ZK-based schemes arises from then nature as interactive proofs, rather than their zero-knowledge aspect.
- 4. unproven assumptions: many ZK protocols (“proofs of knowledge”) themselves rely on the same unproven assumptions as PK techniques (e.g., the intractability of factoring or quadratic residuosity).
- 5. ZK-based vs. ZK: although supported by prudent underlying principles, many techniques based on zero-knowledge concepts fall short of formally being zero-knowledge and/or formally sound in practice, due to parameter selection for reasons of efficiency, or for other technical reasons (cf. Notes 10.33 and 10.38). In fact, many such concepts are asymptotic, and do not apply directly to practical protocols (Remark 10.34).
- (iii) Example of zero-knowledge proof: Fiat-Shamir identification protocol
The general idea of a zero-knowledge (ZK) proof is illustrated by the basic version of the Fiat-Shamir protocol. The basic version is presented here for historical and illustrative purposes (Protocol 10.24). In practice, one would use a more efficient variation, such as Protocol 10.26, with multiple “questions” per iteration rather than as here, where В poses only a single one-bit challenge per iteration.
The objective is for A to identify itself by proving knowledge of a secret s (associated with A through authentic public data) to any verifier B, without revealing any information about s not known or computable by В prior to execution of the protocol (see Note 10.25). The security relies on the difficulty of extracting square roots modulo large composite integers n of unknown factorization, which is equivalent to that of factoring n (Fact 3.46).
10.24 Protocol Fiat-Shamir identification protocol (basic version)
SUMMARY: A proves knowledge of s to В in t executions of a 3-pass protocol.
- 1. One-time setup.
- (a) A trusted center T selects and publishes an RS А-like modulus n = pq but keeps primes p and q secret.
- (b) Each claimant A selects a secret .s coprime to n, 1 < s < n - 1, computes v = s2 mod n, and registers v with T as its public key.6
- 2. Protocol messages. Each of t rounds has three messages with form as follows.
technically, T should verify the condition gcd(s, n) = 1 or equivalently gcdty, n) = 1, for this to be a sound proof of knowledge; and В should stop with failure if gcd(у, n) Ф 1, where у is A’s response in the third message. But either condition failing would allow the factorization of n, violatmg the assumption that n cannot be factored.
- 3. Protocol actions. The following steps are iterated t times (sequentially and independently). В accepts the proof if all t rounds succeed.
- (a) A chooses a random (commitment) r, 1 < r < n — 1, and sends (the witness) x = r2 mod n to B.
- (b) В randomly selects a (challenge) bit e = 0 or e = 1, and sends e to A.
- (c) A computes and sends to В (the response) y, either у = r (if e = 0) or у = rs mod 7i (if e = 1).
- (d) В rejects the proof if у = 0. and otherwise accepts upon verifying y2 = x ■ ve
- (mod n). (Depending on e, y2 = x or y2 = xv mod ri, since v = s2 mod n. Note that checking for у = 0 precludes the case r = 0.)
Protocol 10.24 may be explained and informally justified as follows. The challenge (or exam) e requires that A be capable of answering two questions, one of which demonstrates her knowledge of the secret s, and the other an easy question (for honest provers) to prevent cheating. An adversary impersonating A might try to cheat by selecting any r and setting x = r2/v, then answering the challenge e = 1 with a “correct” answer у = r; but would be unable to answer the exam e = 0 which requires knowing a square root of x mod n. A prover A knowing s can answer both questions, but otherwise can at best answer one of the two questions, and so has probability only 1/2 of escaping detection. To decrease the probability of cheating arbitrarily to an acceptably small value of 2-f (e.g., t = 20 or t = 40), the protocol is iterated t times, with В accepting A’s identity only if all t questions (over t rounds) are successfully answered.
10.25 Note (secret information revealed by A) The response у = r is independent of .4’s secret s, while the response у = rs mod n also provides no information about s because the random r is unknown to B. Information pairs (x, y) extracted from A could equally well be simulated by a verifier В alone by choosing у randomly, then defining x = y2 or y2/v mod n. While this is not the method by which A would construct such pairs, such pairs (x, y) have a probability distribution which is indistinguishable from those A would produce; this establishes the zero-knowledge property. Despite the ability to simulate proofs, В is unable to impersonate A because В cannot predict the real-time challenges.
As a minor technical point, however, the protocol does reveal a bit of information: the answer у = rs provides supporting evidence that v is indeed a square modulo n, and the soundness of the protocol allows one to conclude, after t successful iterations, that this is indeed the case.
(iv) General structure of zero-knowledge protocols
Protocol 10.24 illustrates the general structure of a large class of three-move zero-knowledge protocols:
The prover claiming to be A selects a random element from a pre-defined set as its secret commitment (providing hidden randomization or “private coin tosses”), and from this computes an associated (public) witness. This provides initial randomness for variation from other protocol runs, and essentially defines a set of questions all of which the prover claims to be able to answer, thereby a priori constraining her forthcoming response. By protocol design, only the legitimate party A, with knowledge of A’s secret, is truly capable of answering all the questions, and the answer to any one of these provides no information about
A’s long-term secret. B’s subsequent challenge selects one of these questions. A provides its response, which В checks for correctness. The protocol is iterated, if necessary, to improve the bound limiting the probability of successful cheating.
Zero-knowledge interactive protocols thus combine the ideas of cut-and-choose protocols (this terminology results from the standard method by which two children share a piece of cake: one cuts, the other chooses) and challenge-response protocols. A responds to at most one challenge (question) for a given witness, and should not reuse any witness; in many protocols, security (possibly of long-term keying material) may be compromised if either of these conditions is violated.