4
$\begingroup$

Conventionally, sigma protocols are defined as being a three-move protocol (1. commit, 2. challenge, 3. response). Reading papers like "Bulletproofs" (Bunz, Bootle, Boneh et al., 2018), it feels like the authors avoid to call their protocols "sigma protocols", although their protocols are always repeats of either 1, 2 and 3 or only 2 and 3; i.e., the verifier only issues (field element) challenges and the prover repeats a response and commit.

Is there a technical reason that the term "sigma protocol" cannot be generalised to multi-move protocols?

Improve this question
$\endgroup$
1
  • $\begingroup$ (I added zero-knowledge-proofs as tag, since there is no proof-of-knowledge tag...) $\endgroup$
    – Ruben De Smet
    May 2, 2019 at 14:06

1 Answer 1

Reset to default
3
$\begingroup$

There is no technical reason while it couldn't - but the term $\Sigma$-protocol was specifically invented to mean three-round public-coin honest-verifier zero-knowledge proof system. Note that the very choice of the greek letter $\Sigma$ was made because it (kind of) picturally represents the interaction pattern in a three-move protocol (arguably, one could also kind of see a four move protocol in it :p).

Note that interaction is a big deal in cryptography: more rounds introduce more latency, and this is very often the main efficiency bottleneck in protocols (think of a protocol between London and Sao Paulo: a 30-round protocol would take 3 seconds counting solely the latency, and is doomed to take at least one full second unless the parties can send messages faster than light - this means that 1 second is here a strict physical efficiency lower bound, unlike communication and computation which we can always improve with more bandwidth or more processors). Hence it makes sense to distinguish, through a specific name, protocols which enjoy the very desirable feature of having only three rounds (which is the minimum we can hope for in the plain model, at least if we want honest-verifier zero-knowledge - of course, in the common reference string model or in the ROM, we can have non-interactive proofs, which are also a big deal in crypto).

For many-round generalizations of $\Sigma$-protocol, I'd recommend calling them by their natural name, public-coin HVZK proofs. Note that the form "commitment - challenge - response" is characteristic of public-coin proofs in general, not only of $\Sigma$-protocols.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Nice answer! Now, in practice, it seems to me that those pc-hvzk-proof protocols (including $\Sigma$-protocols) are basically always used though a Fiat Shamir transformation, such that we don't require the physical communication any more. Of course, this brings us into ROM, but it makes interaction less of a big deal. $\endgroup$
    – Ruben De Smet
    May 3, 2019 at 7:49
  • 1
    $\begingroup$ That might indeed be what happens most of the time in practice, yes - but the terminology comes from long before these proofs systems started to get used in practice :) $\endgroup$
    – Geoffroy Couteau
    May 3, 2019 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.