Sigma protocols
Sigma protocols are protocols for Alice to prove something to Bob (that she knows some secret). They have the following general form: Alice knows a secret; Alice and Bob both share some common information. Then:
- Alice sends a value to Bob, known as a commitment.
- Bob picks a challenge uniformly at random and sends it to Alice.
- Alice computes a response and sends it to Bob.
- Bob checks the response and accepts or rejects Alice's claim.
In cryptography, the properties we expect a Sigma protocol to support are:
Correctness If everyone does what they are supposed to, then Bob accepts.
Soundness If Alice lies, then Bob can tell (she can't trick him into accepting something false)
Zero-knoweldge If Alice tells the truth, Bob can't learn what her secret input was.
A more formal treatment
Having provided a rough overview, we now provide a more formal treatment, based on David's PhD thesis "Zero-Knowledge Proofs in Theory and Practice".
Defining a Sigma Protocol
Let $k$ be a field. We're interested in linear functions $f: W \to X$ from one $k$- vector space to another, where Alice and Bob both know some public $x \in X$ and Alice also knows a secret preimage $w \in W$ such that $f(w) = x$. Alice wants to prove to Bob that she knows a preimage of $x$.
Quite a lot of cryptography is done over elliptic curves nowadays. An elliptic curve is a group of points of the form $P = (x,y)$ and a special point "at infinity" that is an honorary member of the curve. These points satisfy some equations and most importantly, one can add two points on the curve to get another and this addition makes the curve into a group. One often starts with a large prime $p$, works over the base field $k = \mathbb F_p$ and considers points $P$ in $E_p = E \cap \mathbb F_p \times \mathbb F_p$.
Many elliptic curve protocols start out by generating keypairs using point multiplication: everyone agrees on a common, public base point $P$. Then one can pick a secret key $x \in \mathbb F_p$ and compute the related public key $Y = x \cdot P$. If Alice wants to register her public key somewhere, it is good for security if the registrar asks her to prove that she knows the associated secret key, or else she could register someone else's key as her own. But of course Alice should not reveal her secret key to the registrar. She could, for example, use a Sigma protocol to prove that she knows the secret key that she claims to know, without revealing it.
If one takes $W = \mathbb F_p$ as a $k$-vector space and $X = E_p$ then point multiplication for a fixed base point, specifically $f: W \to X, w \mapsto w \cdot P$ is a linear function. The same can be said for "matrix product" functions. Suppose that Alice has a secret key $x$ and a public key $Y = x \cdot P$, and someone sends her an ElGamal ciphertext $(C,D)$ for her key. She wants to decrypt this and prove that she has decrypted it correctly, one way to do this is to compute a decryption share $S = x \cdot C$. The decryption is then $D-S$ which anyone can compute from $(C,D)$ and $S$. So Alice want to show that she knows an $x$ meeting the two equations $Y = x \cdot P$ and $S = x \cdot C$, so we set $W = k, X = E_p \times E_p$ and $f(x) = (x \cdot P, x \cdot C)$ which is a linear function $f: W \to X$.
The Sigma protocol for $f: W \to X$ is the following construction. Alice knows $(x, w) \in X \times W$ with $f(w) = x$ and Bob knows $x$. 1. Alice picks $r \in W$ at random, sets $A = f(r)$ and sends $A$ to Bob. This is the commitment (Alice is committing to $r$). 2. Bob picks $c \in k$ at random and sends it to Alice. This is the challenge. 3. Alice computes the response $s = r + c \cdot w$ in $W$ (the product is scalar multiplication in $W$) and sends $s$ to Bob. 4. Bob accepts if $f(s) = A + c \cdot x$ in $X$.
Let's look at the three security properties for Sigma protocols in more detail:
Correctness
In just about any protocol (cryptographic or otherwise), correctness means that if everyone follows the protocol then it does what it should. In the context of Sigma protocols, this means that if Alice and Bob do as told then Bob accepts; this is true because $f$ is linear.
Soundness
Soundness means that Alice cannot prove a false statement. This trips up a lot of people because the first protocol they see is Schnorr's protocol for proving that $y = x \cdot P$, so Alice is proving that such an $x$ exists. But that is obvious! (Alice is also proving that she knows $x$, which is more interesting but that's another property.) But let's look at the other example, Alice proving that $S$ is a correct decryption share for $C$ under public key $Y$. Here, Alice is proving that an $x$ exists such that $Y = x \cdot P$ and $S = x \cdot C$ which is not true for all tuples $(P, C, Y, S)$. What's actually going on is that the image of $f$ is a one-dimensional subspace of the two-dimensional $k$- vector space $X$. In our formalism, soundness means that Bob does not accept (except with perhaps negligible probability) unless $x$ is in the image of $f$ (that is, a preimage $w$ exists such that $x = f(w)$).
Sigma protocols are sound. Actually, they are even more than that, they have a property called special soundness. Informally, consider the point in time when Alice has just sent her commitment $A$ to Bob. For which values of $c$ can Alice possibly find a $r$ that Bob will accept? If there is at most one such value then Alice gets Bob to accept overall with probability at most $1/|k|$. Usually, $|k|$ is exponentially large (it's the prime $p$ that we started with) so $1/|k|$ is negligibly small. Special soundness says that if Alice can conveince Bob even for only two out of $|k|$ possible challenges, then a preimage $w$ must exist. Suppose that on challenge $c$ Alice would reply $s$ and on challenge $c' \neq c$ Alice would reply $s'$, and Bob would accept both of these. Then set $d = (c-c')^{-1}$ which we can do as $k$ is a field and $c \neq c'$, and a bit of linear algebra shows that $w = d \cdot (s-s')$ where the product is again $W$-scalar multiplication satisfies the equation $x = f(w)$.
Zero-Knowledge
Bob is happy because the protocol is sound. Alice still needs to know that Bob can't learn $w$ from the Sigma protocol. Actually, Alice probably wants even more than that: after running the protocol with Bob, Bob should not be able to prove to Charlie that he knows Alice's secret $w$ either. Zero-knowledge says even more than that, Bob does not learn anything from the protocol except that Alice knows $w$ (and therefore, that $w$ exists and $x$ is in the image of $f$).
The proof that Sigma protocols are zero-knowledge ... does not exist! Contrary to what one might guess after learning about Sigma protocols in the textbook chapter on zero-knowledge, Sigma protocols in general are not zero-knowledge, which beginning students of cryptography would do well to remember for their exams. (They meet a weaker requirement called honest-verifier zero-knowledge.)
Discussing Sigma protocols in the context of zero-knowledge isn't completely arbitrary though: one can make them zero-knowlege in several ways, the most practical of which is making them non-interactive. But that's next week's topic...
No comments:
Post a Comment