December 1, 2024: updated to make corrections as shown. The proposed alternative definition of special soundness has not been changed, but its wording has been clarified.
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.
as done by Boneh and Shoup in Theorem 19.1 of their online textbook,
which we reference in Section 3.5.2.2.1 of the book chapter.
In those cases the two transcripts are created by rewinding the
prover to its initial state with the same random tape
to its state after sending the commitment message, 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
with the same commitment
but different challenges, in cases where not only the commitment
but also the blinding factor used by the prover to generate the commitment
is the same.
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 the prover of a special sound protocol is rewound
with the same random tapeto its state after sending the commitment message, 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 itwith the same random tapeto its state after sending the commitment message 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 rewoundwith the same random tapeto its state after sending the commitment message, both resulting transcripts will have used 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.