Standardizing Sigma Protocols?

Hello there,

(sorry for crossposting this message; it was initially shared with the commit-and-prove working group, but nobody can access it outside the group.)

Following the discussions during «Commit-and-Prove Zero-Knowledge Proof Systems» from Matteo Campanelli and «Zero-Knowledge Proofs for Constructing Protocols» from Jan Camenish, I’d like to open a thread to see what’s the general feeling for standardizing sigma protocols.
Concretely, I’m thinking about the formalization of Camenisch-Stadler and [Boneh-Schoup, Chap. 19].
I am aware that there are more involved sigma protocols that have better asymptotics in particular scenarios (e.g. for instance [GK14]); but it’d rather stay with these simpler ones for now.

Sigma protocols are simple, mature and pretty powerful; I think they deserve a place in this general standardization effort for proving in zk knowledge of a dlog, one-of-many dlogs, discrete log equality, that a triple is a DDH tuple, proving knowledge of multiple dlogs simultaneously, and more generally (simple) relations on committed values.

What’s your feeling on this? Perhaps we can use the hearts to test the general vibe?

As a first step, I’m listing the current use-cases and implementations, in the hope that they will help better understand the context and scoping the proposal.

Use-cases

Implementations


A lot of works were blatantly stolen from the already-made comparisons of Lueks, Kulynych, Fasquelle,Le Bail-Collet,Troncoso. So… yeah, thanks!
11 Likes

Are there any miss-use resistance techniques that one could extract at the sigma protocol level?

I fully agree with this.

This is definitely a great point, and something that can go “unnoticed” if the effort / community was to focus only on the generic version of ZK.

I would personally like to see such a standard being formed. Maybe we should point people to this post and get their view on this. If we get enough support maybe we can start an ad-hoc working group, as we did with the primitives working group. Let’s get support (people who are willing to put time into this) of at least 10/15 people and then we can create the working group?

@retq would you like to lead this?

Sure ! let me get back to you with a list of people.

Do you think we should reach out with an email to the IRTF CFRG so see what they think about it and if they want to chime in, given that they’re also standardizing some specific sigma protocols?

1 Like

I think it could be great to have their input!
Can you elaborate a bit on what specifically is being standardized as sigma protocol in the VOPRF and Privacy Pass working groups? We definitely do not want to step over / replicate their work.

Could we define the sigma protocol in a generic way so it includes those drafts but can encompass a different concrete protocol?

I saw you texted on the Telegram group - thanks!

Hi Michael & Daniel, I am interested at least in the initial discussions to see whether there is something I can uniquely help with.

1 Like

Hello sigma standardisers!

In the hope of raising the spirits and the morale here, I would like to notify you that we are planning to submit a proposal for the next Zkproof workshop.
The idea, for now, is to submit a small ~10-15 page document containing:

Standard Schnorr proof, equipped with and/or composition, focusing on prime order groups over elliptic-curves, either compact (challenge+response) or batchable (commitment+response). API, selection of curves, and hash functions that should be considered for the task.

Now, the use-cases and implementations that I listed above will be pretty-much our guide. Therefore, if you know some more, please let us know! We’re also looking for:

  • Input from the industry: if people are using sigma protocols within the industry, we would love to hear about your use-case. Even if we already listed you above, we need to understand how you’re putting them into practice, and we have specific questions for you.
  • Reviews: it would be awesome if some of you could find the time to read the document, and report potential issues, bugs, or additions that would help us improve the proposal document. Even a correction handwritten on the top of a pdf would be gold!
    I think there’s a lot of design choices that need care and attention for this standard. I’m talking about silly issues like how many bits of the hash are needed for the challenge, or whether to return a transcript using the challenge (so without point verification) or the commitment (so with batching), which unfortunately have a big impact. Hence, really, please let us know what you think!

I’m also tagging @mmaller and @markulf, which expressed interest over the Telegram chat (thank you!) and might be interested.

Peace,

Michele.

1 Like