Home Edition #2
Moderator: Eran Tromer
Presenters: Michele Orrù
Authors:
To be presented on 2021-04-19.
Resources:
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
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)
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:
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:
or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing