I am co-authoring a book on the Foundations of Cryptographic Authentication with Sukhi Chuhan and Veronica Wojnas, where Chapter 3 is concerned with traditional credentials (as opposed to verifiable credentials or the mDL). Section 3.5 has an extensive treatment of zero knowledge, and in section 3.5.6 we use BBS signatures as an example of anonymous credentials. The chapter is still work in progress: the definition of special soundness proposed here is discussed in Section 3.5.6 but has not been retrofitted yet into sections 3.5.1-5.
As we were studying in detail the BBS paper we saw that the Sigma protocol defined in the paper for proving knowledge of a BBS signature is not special sound, contrary to what the paper claims. Then we thought of a modification to the definition of special soundness, proposed here, that would make it special sound. The proposed definition is more widely applicable than the current one, while still implying proof of knowledge.
The modified definition uses what we call “the blinding factor of a Sigma protocol”, a new concept that may also be useful for other purposes, such as formally specifying Fiat-Shamir transforms and proving their security. In the rest of this post I give the definition of this new concept, then I explain how there are several errors in the BBS paper before proposing and motivating the modified definition.
Blinding factor of a Sigma protocol
A Sigma protocol is a 3-move public-coin interactive proof system where the three messages are called the commitment, the challenge, and the response. Why is the first message called “the commitment”?
In cryptography, the term “commitment” refers to a commitment scheme, which often involves three elements: a committed value typically secret, a random value called the blinding factor of the commitment, and the published commitment. These three elements can be discerned in a Sigma protocol: the committed value corresponds to the witness, which is often a secret, such as the private key of an identification scheme or the secret signature in a presentation of an anonymous credentials; the blinding factor of the commitment corresponds to the random values generated by the prover before sending the commitment message; and the published commitment corresponds to the commitment message.
So, perhaps a Sigma protocol can be viewed as a kind of commitment scheme. But whether it is viewed as a commitment scheme or not, we propose to define the blinding factor of a Sigma protocol as the coin tosses that the prover makes before sending the commitment.
Errors in the BBS paper
The following errors in the BBS paper must be identified in preparation for motivating the proposed definition of special soundness:
- As seen in Fig. 3 of the BBS paper, a BBS signature is generated by computing C from the message and the generators of 𝔾1, generating a random scalar e, and computing A = C1/(x+e). The signature is then (A,e). In section 3.1, the paper says: “There is an unlikely event that the inversion to compute 1/(x + e) during signature issuance fails because x + e = 0—for ease of syntax, we use the convention that 1/0 = 0”.
It is hard to see how any syntactic consideration could justify letting 1/0 be 0 in the computation of a signature. But even if we overlook this deviation from mathematical practice and arbitrarily replace 1/(x+e) with 0 while computing the signature, the result of the computation is (C0,e), which is equal to (1𝔾1,e), a vacuous “signature” that is unrelated the message, and hence cannot be a signature on the message.
In the subsection “Solutions to problems left unsolved by the paper” of section 3.5.6 of the book chapter, we suggest a simple way of avoiding the corner case x + e = 0: Since e is selected at random by the signer from a probability distribution, the signer can exclude -x from the distribution by trying again as needed if the random scalar generator returns -x as the value of e.
- In the section “Special soundness” on page 24, the use of the letters “s” and “t” is swapped in the names of the variables “s1“, “s2“, “si” vs. “t1“, “t2” and “ti“, and inconsistent with the use of those letters in the variables “s” and “t” of the protocol definition.
- The proof of special soundness has two cases: r ≠ 0 and r = 0. The proof is correct in the case r ≠ 0, except for the above-mentioned error that swaps the letters s and t. But the case r = 0 is not correct. In that case, the paper derives x = -e from the two accepting transcripts, then says “and this gives us a signature”. But the purported signature that x = -e gives is the vacuous signature (1𝔾1,e) computed by letting 1/0 be 0 that we encountered in error 1.
Thus, the Sigma protocol for proving knowledge of a BBS signature is NOT special sound with the current definition of special soundness.
There are also two errors in the BBS paper that are not directly related to special soundness but make the paper confusing. The definitions of I and J in the section on partial disclosure have typographical errors. In the definition of I, m should be m’; that error also occurs in Appendix A, but not in Appendix B. In the definition of J, [n] should be [l]; that error occurs in both appendices.
Motivation for the proposed modification of the definition of special soundness
Error 5 above is related to the corner case r = 0 in the proof of special soundness, which leads to x = -e. But in that corner case, x = -e not only does not give us a signature as claimed, it gives us instead the value of x, which is the signing key! In the case r = 0, the two accepting transcripts yield the private key of the credential issuer.
The case r = 0 is weird, so let’s look at it more closely.
The case occurs when the two accepting transcripts have the same value of the first component, s, of the response even though they have different commitments. This is something that should not happen in cases that matter. Cases that matter are those where special soundness is used to argue that the protocol is a proof of knowledge, as we do in the subsection “Special soundness and proof of knowledge” of Section 3.5.2.1 of the book chapter, or to prove that the protocol is secure by reduction to a cryptographic assumption, as we do for the Schnorr identification scheme in Section 3.5.2.2.1.
In those cases the two transcripts are created by rewinding the prover to its initial state with the same random tape, and therefore they have the same blinding factor. At least in the case of BBS, but perhaps also in the case of other anonymous credentials, if the blinding factors of two accepting transcripts are the same while the challenges are different, then both components of the response are different, as seen for BBS by looking at the protocol description at the top of page 24 of the paper. The blinding factor of the protocol comprises the random variables r, α and β, and the response (s,t) is computed from the blinding factor, the signature, and the commitment c, as s = α + r · c, t = β – e · c. If α and r are the same in two transcripts but c is different, then s = α + r · c is different. And if β is the same in two transcripts where e is also the same as a component of the signature but c is different, then t = β – e · c is different.
This suggests that what matters in special soundness is not whether two transcripts have the same commitment, but whether they have the same blinding factor.
Proposed modification of the definition of special soundness
As defined in more detail in Section 3.5.2.1 of the book chapter, the current definition of special soundness is as follows: a Sigma protocol is special sound if it is possible to efficiently extract a witness from two accepting transcripts with the same commitment but different challenges. In Section 3.5.6.2.1 we are now proposing to change “same commitment” to “same blinding factor”, and to say that a Sigma protocol is special sound if an efficient extractor can compute the witness from two accepting transcripts with the same blinding factor but different challenges.
Properties of the proposed definition
- The proposed definition is more widely applicable than the original definition. It is at least as widely applicable because two transcripts that have the same blinding factor have the same commitment, since the blinding factor includes all the coin tosses made by the prover before the commitment; and it is strictly more widely applicable since, as we have seen, the BBS protocol is special sound under the proposed definition but not under the original definition.
- A protocol that is special sound according to the proposed definition is a proof of knowledge protocol. Being a proof of knowledge protocol is often equated with being special sound. With such definition, being special sound under the proposed definition would of course not imply being a PoK protocol, since the proposed definition is strictly more widely applicable than the original one. But equating special soundness with PoK is justified by the fact that, if a special sound protocol is rewound with the same random tape, then the witness can be extracted from the resulting pair of transcripts. If we take that justification as the definition of being a PoK protocol, i.e. if we say that a protocol is a PoK protocol if rewinding it with the same random tape yields the witness, then a protocol that is special sound according to the new definition of special soundness meets the PoK definition, because if it is rewound with the same random tape, both resulting transcripts will have the same blinding factor and, by the new definition of special soundness, there will exist an efficient extractor that can compute the witness from those two transcripts.