Internal review of Theory

November 14, 2021 → November 26, 2021
@Nicola, @Friedel Ziegelmayer
Aayush Rajasekaran

What is this Audit About:

We are going through the entire SnapDeals protocol together in order to have a final validation of the theory behind it. The team includes people who directly worked on SnapDeals as well as researchers who did not directly work on it in the past but have extensive expertise in analyzing cryptographic protocols and their security: in this way we aim to minimize potential biases.

Relevant link that describes the entire process+plans we have:

SnapDeals Theory Audit
SnapDeals Theory Audit

What is in Scope for this line of work:

A deep dive into the SnapDeals protocol in order to check all the technical details of it, including Security. In details:

Double check the encoding function and agree we are fine with it
Go over all the assumptions and validate them together
Why Assumption 1 is broken
Which concrete attack we can put in place
Why we are convinced the assumptions we are using
We are fine with considering the flipping adversary as specified in the protocol description
We will investigate how resampling affects Kolmogorov bounds
Analyze the security proofs of SnapDeals
Two bytes for one bit (probabilistic)
Kolmogorov bound-based (information theoretic)
Review bucketing analysis and take a final decision on it
Agree on the calculation about the additional spacegap
Agree we are overall taking a quite conservative approach, and that we are fine with it
Agree on number of different hashes used in the protocol (512 or 1024?)
1024 have to communicate it
Produce a list of important items to be checked during the next implementation audit
Challenge generation (using Poseidon inside the circuit)