Home Edition #2

Proposal: Σ-protocols Discussion notes

Moderator: Eran Tromer
Presenters: Michele Orrù

Authors:

  • Michele Orrù
  • Stephan Krenn

To be presented on 2021-04-19.

Resources:

Real-time notes

Note taker: Sean Coughlin & Eran Tromer & Stephan Krenn
PP

There are several security concerns that are subtly represented in the implementation of sigma protocols (such as hashing the statement with the randomness as the script when using fiat-shamir for non-interactivity).

-Prime fields
-Non-Interactivity
-Composition

Daira shared: https://eprint.iacr.org/2017/540.pdf
Mary shared: https://eprint.iacr.org/2012/704.pdf
to explain that sigma protocols compiled with Fiat-shamir are simulation sound

May be worth focusing on a certain amount of groups / ECs. To chose, we could do

  • prime-order groups
  • prime-order gorup abstractions
  • pairing-friendly groups

Safely deriving the challenge is challenging. Actual attacks known on real-world implementations. ProposeD:
H(T,Y,gen,curve,ds) with proper separators to avoid length-extension attacks and "chop off at 256bits" (draft-irtf-cfrg-hash-to-curve, STROBE but it's heavyweight)

Challenge-Response

Response: Short (c,s) and Batchable (T,s)

Existing implementations

(Reviewed in the paper)
Please let authors know about missing frameworks/implementations

Limitations

Long/complex statements might be a better fit for, e.g., SNARKs than for Σ-protocols. Should discuss application scope.
ZK-property still holds in PQ setting, if hash output is sufficiently long. Formally, soundness is maintained also if DLOG is broken (statement becomes meaningless, though)

Discussion / Questions

Post-Quantum
Assuming hashing algorithms are valid then this scheme should be compatible for 20+ years.

Daira: Considered using a Σ-protocol proof of DL equality in Zcash. Did not because there was no standard.

Daira: a motivation is faster proving than a SNARK with untrusted setup

If the number of witnesses is small, Sigma-protocols are more efficient than SNARKs. In the standard, estimate the size of the Sigma protocol depending on statement to prove/number of witnesses, and compare this with other approaches (SNARKs)

Mary: putting the Σ verifier inside a circuit introduces new concerns, e.g., choice of hash function. This would allow opportunity/need for more formalization of existing alrgoritms to compare across schemes, i.e. Poseidon Hash (H R: which is already deployed in Loopring).

Carla: threshold cryptography is a possible application

Thomas: Why is there a domain separator AND the full instance of the problem? Isn't that redundant? –> Idea of domain separator was to also define the context (e.g., passport vs xxxx).
Daira: Use a domain name string, that should make it unique

George: I am wary of mandating a particular hash for something as general as this. It seems like in practice people will want to use a hash that already makes sense for the rest of their system. (+1 by Antonie, H R, Kevaundray)
Michele: maybe one hash function in the SNARK context and one outside?
Daira: that might be too specific in SNARK context, standardizing on one may be an issue in the case of discovered errors in the algorithm and in the inability of one standard to represent the already existing diverse use-cases and implementations.
George: Don't over-specialize and over-specify, as certain systems might already use, e.g., SHA2
Daira: just recommend specific hash functions, but do not mandate

Peאטודי: It's not an easy problem to make interfaces work for efficiency inside and outside circuits (we're trying to solve this in ark-sponge), but IMO that's the more secure and flexible way

AntoineR: Is the plan of this standardisation to meet some security target or to be interoperable to use sigma protocols across many contexts? If the goal is the latter, it seems like we should be simply focusing on data encoding and defining domain/codomains of the functions

Michele: possible further topics to be discussed:

  • Constraint system format and R1CS compatibility: Σ-protocols are stable and easy to deploy. What would be nice is an interface that could be used as an interface between Σ-protocols and other proof systems. There are already other initiatives. Is R1CS the right format? Which other formats could/should be used?

Daira: parallel implementation example would allow for easier comparison and standardization.

  • Shared proof computation: how to distribute the computation of a proof across different parties that have parts of the witness? e.g., frost

  • Designated verifier proofs: [lack of time for discussion]

  • Interactive protocols: [lack of time for discussion]

Chelsea says: Note that we have a standardization draft for FROST within the CFRG already (as a note to the sigma protocol working group)

This is an early example of a less restrictive requirements allowing for optimization in certain cases.

What should be the scope? Highlighting the pitfalls, formalize next steps and describe specific schemes including test vectors, etc.?

Didactically:

  • Many SNARKs (e.g., Bulletproofs), especially without trusted setups, are somehow generalizations of Σ-protocols. Thus having Σ-protocols standardized might make it much easier for future proposals.
  • Seek for harmonization across different approaches.

Proposed standards-oriented action

  • Separate document from the community document
  • Document could start from the current proposal, need to discuss how it needs to be extended
  • could be referred in the community reference document
  • Create a working group and a Telegram channel
  • Schedule a meeting in a few weeks to fix scope and follow-up on the discussions above
  • We should coordinate with other efforts (e.g. PrivacyPass) to prevent duplication of work
Select a repo