Paper TLDR Project

This project serves as intermediate indices to my memory of paper reading and notes.

It also serves as a humble mimic to Oded’s choices.

[Seen 2023/11 for Nova line of work for Folding Scheme]

Spartan: Efficient and general-purpose zkSNARKs without trusted setup
  • To bridge R1CS with sum-check protocol, Setty et al. encoded R1CS with low-degree extension (LDE) into multi-linear polynomials.
  • The Spartan NIZK version requires the verifier to evaluate encoded R1CS polynomials over random points, thus they applied polynomial commitments to make the prover to compute the evaluation point for verifier.
  • R1CS matrices are sparse, i.e., the matrix can be $\mathbb{F}^{m \times m}$ with $n = O(m)$ non-zero entries. They showed a gradual transform in prover complexity:
    • An $O(m^2)$ solution would be directly committing against LDE multi-linear polynomial of matrix $\mathbb{F}^{m \times m}$.
    • An $O(n \log n)$ “strawman” solution would be to LDE against tuples of matrix coordinates ($\mathbb{F}^\mu$ where $\mu = 2s$, $s = \log m$) and non-zero entry $\mathbb{F}$.
      • In total requires $O(n \log n)$ variables, where the extra $\log n$ comes from $\mathbb{F}^\mu$ of coordinates.
    • Finally, an $O(n)$ solution would be compressing sparse matrix $\mathbb{F}^{m \times m}$ into $n$-length list of tuples of (row, col, val), then use offline memory checking technique in Spice to construct an $O(n)$ sized, $O(\log n)$ depth circuit.
      • Offline memory checking performs time stamp order construction for non-zero entries in matrices, the trick is init + write = read + audit.
      • The public coin multiset hash function helps checking the equality of sets of (coordinate, value, time-stamp) tuple.

The hardest part to comprehend (for me) is the memory checking circuit for $\tilde{M}(\pmb{r_x},\pmb{r_y})$ on Section 7 for SPARK compiler that converts a poly commitment into one that handles sparse multi-linear poly commitment.

Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
  • The motivation is that: vanilla R1CS relation does not allow for merging 2 statement-witness pairs into one, and naive construction of IVC is far from practical to be used.
  • The previous R1CS relation is $(A, B, C \in \mathbb{F}^{m \times m}, \pmb{z} \in \mathbb{F}^m)$ where $\pmb{z} = 1 \parallel \pmb{z} \parallel {w} \in \mathbb{F}^m$, such that $(A \pmb{z}) \circ (B \pmb{z}) = C\pmb{z}$.
  • To make the relation foldable, we should introduce relaxation terms $u \in \mathbb{F}$ and $\pmb{e} \in \mathbb{F}^m$, such that $(A \cdot (\pmb{z}_1 + r \pmb{z}_2)) \circ (B \cdot (\pmb{z}_1 + r \pmb{z}_2)) = u \cdot C \cdot (\pmb{z}_1 + r \pmb{z}_2) + \pmb{e}$.
    • Additionally, we want to commit to the R1CS witness $\pmb{w}, \pmb{e}$ with an additive homomorphic commitment as $\text{com}_w$ and $\text{com}_e$.
  • To make use of folding scheme, or non-interactive folding scheme (NIFS) in IVC, we want to let the circuit to fold 2 R1CS statement into 1:
    • R1CS statement contains inputs and outputs, the contradiction is that we can no longer make R1CS statement constant as each step goes.
    • To make the R1CS statement size being a constant, they use hash of inputs as R1CS statement.
    • Such hash can be vied as a “constant sized computation binding” to the inputs we want to use at each step.
  • Series connection of folding components into an IVC, while at each step a NIFS prover will keep track of the relaxation terms and IVC proof, which is the R1CS witness.
  • To compress the IVC proof size, which is the same as R1CS statement-witness pair size, they applied Spartan to generate a proof of knowledge of IVC proof, which compresses the concrete proof size.

The trickiest part is the hash of R1CS statements in folding scheme as R1CS statement, which ensures the statement size being constant.

TODO: SuperNova: Proving universal machine executions without universal circuits

TODO: HyperNova: Recursive arguments for customizable constraint systems

TODO: LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems

[Seen 2023/11 for PlonK line of work]

see notes here

TODO: Efficient Zero-Knowledge Argument for Correctness of a Shuffle

PlonK: Permutations over Lagrange-bases for Oecumenical Non-Interactive arguments of Knowledge
  • A permutation argument checks if a polynomial is permutation of another polynomial by $f(\sigma(x)) = g(x)$.
    • The instantiation of permutation argument in Plonk is product argument, which constructs $z(x)$ progressing over $g^0 … g^n$.
    • Each step of $z(x)$ multiplies a step over $f(x) + \beta x + \gamma$, with a division over $g(x) + \beta \cdot \sigma(x) + \gamma$.
    • The goal is to check when finishing the progression, $z(x)$ should have all terms canceled, which means $z(g^n) = 1$.
    • $\gamma$ is necessary as a randomized shift for multiset equality, while $\beta$ is necessary for prover holding on to the same permutation $\sigma$, which yields a permutation argument.
  • Another perspective of constraint system is that, view computation circuit as $n$ gates and $m$ wires, then the wire values attached to gates as input/output should be equal.
    • This yields the motivation of introducing the copy constraints, which is established by permutation argument.
  • A trick to combine multiple zeroity check is to apply random linear combination over multiple zerotiy terms with exponents of random $\alpha \in \mathbb{F}$.
    • The same trick applies to Spartan in sumcheck on multiple terms.
  • KZG polynomial commitment allows up to polynomial degree up to $n$ by CRS, linearization allows one to open against polynomial as products of sub-polynomials of degree lower than $n$.
    • Give verifier evaluation points of a subset of sub-polynomials, and swap the evaluations against these sub-polynomials in the original polynomial, we get the linearization polynomial.
    • KZG commitments are additive homomorphic, while evaluations sent over are over $\mathbb{F}$, then the verifier can construct the commitment for linearization polynomial, and finish the open check.
PlookUp: A simplified polynomial protocol for lookup tables
  • A similar trick of permutation argument application, while we want to check all the elements in multiset $F = f_1 … f_n$ appeared in vector table $T = t_1 … t_d$.
  • We only need to check the multiset equality, so we no need of $\beta \in \mathbb{F}$ in plonk.
  • To check $F \subseteq T$, we merge these two multisets and sort them, yielding a multiset $S’$.
    • Supposing $F \subseteq T$, then all $F$ elements with same value as $T$ can appear later than $T$’s element.
    • We convert $S’$ into $S$ by $s_i + \beta s_{i+1}$, the motivation is to help with multiset subset checking.
    • The progression over $S’$ from first and $n^{th}$ should be equal to progression over $f_i (1 + \beta)$ ($f_i$ is identical with earlier $t_i$) and $t_i + \beta t_{i+1}$.
PlonKup: Reconciling PlonK with plookup
  • Combining the upper 2 works into a Plonk with look up table supported.
  • To combine a line of 2 input 1 output table entry into $\mathbb{F}$, see Spartan multiset hash function, that $t = t_1 + \gamma \cdot t_2 + \gamma^2 \cdot t_3$ for random $\gamma \in \mathbb{F}$.
  • Additional to constraint system is that $q_{k_i} (w_i + \gamma \cdot w_{n + i} + \gamma^2 \cdot w_{2n + i} - t_i) = 0$ for all $i \in [n]$, which checks intermediate witnesses match table results.
HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates
  • This paper gave off a good vibe from Spartan, with 2 contributions:
    • Formalization of sumcheck based PIOP toolkits to build up plonk-alike SNARK without FFT involving.
    • Compression of multilinear polynomial commitment size with the help of Commit-and-Prove SNARK, which is similar to Spartan’s Spark compiler in some sense.
  • This paper helped me realizing the essence of Plonk, that is multiset hash function with multiset product argument:
    • Recall the multiset hash function in Spartan, with $h_\gamma(\alpha_1, \alpha_2, \alpha_3) = \alpha_1 + \gamma \alpha_2 + \gamma^2 \alpha_3$ and $H_\beta(\pmb{\alpha}) = \prod (\alpha_i - \beta)$.
    • The constraints in Plonk can be viewed as an entry of 2 elements of index and witness value merged with $h_\gamma$ above, and the final multiset should hold a multiset hash from $H_\beta$.
    • Given a permutation that permutes over same value, the permutation way of constructing multiset hash should lead to same multiset hash with a vanilla way of constructing multiset hash.
    • We can check above with a product check argument, that the grand product of divisions leads to 1 as a result.
  • I personally like the way they organize the PIOPs in section 3, which is very well organized and can be easily read.
    • We saw the sumcheck for high individual degree polynomials in Spartan before, but the prover complexity is $O(2^\mu d^2)$ rather than $O(2^\mu d \log^2 d)$ in implementation – this should not be a big issue when $d$ is low, just asymptotically different.
    • 3 queries per round (0, 1, $r$) in multilinear sumcheck can be merged into 1, with the help of last round’s claim of sum and multilinear polynomial dividing over $X (1-X)$.
    • They use Spartan’s zero-over-subcube check trick extensively, with a random challenge $\pmb{r} \in \mathbb{F}^\mu$ and check $\sum\limits_{\pmb{x} \in {(0, 1)}^\mu} f(\pmb{x}) \cdot \text{eq}(\pmb{x}, \pmb{r}) = 0$.
    • Product check takes advantage from Quark, which checks product over $\mu$ bits by carefully arrange evaluations ($2^\mu$) and sub-products ($2^\mu - 1$) over $\mu + 1$ bits.
      • We check the encoding over $\mu + 1$ bits by seeing if it satisfies $v(1, \pmb{x}) = v(\pmb{x}, 0) \cdot v(\pmb{x}, 1)$ over $\mu$ bits of $\pmb{x}$.
      • The rest should follow from a standard sumcheck.
    • Permutation PIOP with small soundness error views $\sigma$ as permutation, using inverse permutation $\sigma^{-1}$, we avoided exploding the degree in sumcheck round polynomial.
      • The first $n$ rounds can be done in $O(\mu 2^\mu)$ complexity, with each round $O(2^\mu)$, by $O(2^{\mu - i})$ on $\text{eq}$ and $O(2^i)$ on multilinear minus term (zeroity terms).
      • The last $n$ rounds can be done in $O(2^\mu \cdot \mu \log^2 \mu)$, for $\sigma^{-1}$ is applied in $\text{eq}$ incurring degree to be $O(\mu)$, and operation done by sumcheck over high degree polynomial.
    • Lookup PIOP deploys a degree-2 multivariate “generator” polynomial, but it gets linearized by computing $f$ twice rather than computing $f(g(\pmb{x}))$ directly.
      • The rest should follow from plookup and multiset check PIOP, for “shift-by-1” table and values over $\mu+1$ bits.
    • Batch opening for multilinear polynomials gets to optimized complexity with $O(k 2^\mu)$ for $k$ batch size.
      • This is achieved by rewriting $f(\pmb{x}) = \sum\limits_{\pmb{z} \in {(0, 1)}^\mu} f(\pmb{z}) \cdot \text{eq}(\pmb{z}, \pmb{x})$ in its multilinear form (a variant of Spartan’s trick).
      • All these subchecks can be combined together by Spartan’s zero-on-subcube checks, checking zeroity over sum of $\mu + \log k$ bits.
      • A specific case when all the opening points are over subcube is that, we can precompute the $\text{eq}$ terms in Spartan trick, and the prover complexity optimized to $O(2^\mu)$.
  • Linear time multilinear polynomial commitment scheme from Orion has concretely large proof size, due to full MT implementation.
    • Similar to Spartan, to compress both the proof size and verifier cost, they build an outer SNARK to prove the verification of original proof goes through.
    • To decrease the circuit complexity of MT verification, they uses multilinear KZG as part of the commitment for lower SNARK circuit complexity.
    • For random access of proximity test query location, they construct lookup table for querying.
    • The consistency check in witness with public IO can be removed from circuit from Commit-and-Prove SNARK.

TODO: Succinct Arguments over Towers of Binary Fields

[Seen 2023/12 for efficient polynomial commitment line of work]

TODO: Doubly-efficient zkSNARKs without trusted setup (Hyrax)

Ligero: Lightweight Sublinear Arguments Without a Trusted Setup (interleaving code proximity test from tensor-code IOPP)
  • The contributions of this paper are two folds as follows:
    • They introduced an interleaved linear code proximity test.
      • Given a interleaved linear code $U^\ast$ with large min distance from $L^m$ by $d(U^\ast,L^m) > e$, an element $\pmb{w}^\ast \in L^\ast$ preserves $d(\pmb{w}^\ast, L) > e$ with high probability.
      • Brakedown, Orion, and BCG20 papers follow from the proximity test over interleaved linear code, which plays a role in tensor code based polynomial commitment.
    • This work provides a viewpoint that connects MPC with argument system, that each column of an interleaved linear code can be viewed as a party’s view in MPC.
      • If the linear code is RS-code, then the secret sharing is Shamir secret sharing.
  • We start by Lemma 4.2/4.3 version, where $e < \dfrac{d}{4}$, that: if $d(U^\ast,L^m)>e$, let $L^\ast = \text{rowspan}(U^\ast)$, then $\Pr\limits_{\pmb{w}^\ast \overset{R}{\gets} L^\ast}[d(\pmb{w}^\ast,L) \le e] \le \dfrac{e + 1}{|\mathbb{F}|}$.
    • The main trick is to write $\pmb{w}^\ast$ into the affine form by $\alpha \cdot U^\ast_i + \pmb{x}$, then we argue for a given $\pmb{x}$, at most one $\alpha$ s.t. $j \in \Delta(U_i,L)$, but $d(\pmb{w}^\ast,L) \le e$ and $j \notin \Delta(\pmb{w}^\ast,L)$.
    • Or the span of these $\pmb{w}^\ast \in L^\ast$ would contradict with $j \in \Delta(U_i,L)$, for $U_i$ itself is in the span. (The subtlety here is the unique decoding radius, that $2e < d/2$)
  • An improved analysis by by Roth and Zemor gives $e < \dfrac{d}{3}$, that: if $d(U^\ast,L^m)>e$, then $\Pr\limits_{\pmb{w}^\ast \overset{R}{\gets} L^\ast}[d(\pmb{w}^\ast,L) \le e] \le \dfrac{e + 1}{|\mathbb{F}|}$.
    • The improvement on bound $e$ is due to escaping the previous constraint from unique decoding radius.
    • This result derive from a lemma, that says if $d(U^\ast,L^m)>e$, then $\exists \pmb{w}^\ast \in L^\ast$ that $d(\pmb{w}^\ast,L)$.
    • The lemma is achieved by proof of contradiction, that assuming all elements in $L^\ast$ are at most $e$-far from $L$, then the bases $U_i^\ast$ are all $e$-close to $L$.
    • Assuming one vector is $\pmb{v}_0^\ast$ maximize the distance, then there exists another basis $U_i^\ast$ holding other error entries that $\Delta(U_i^\ast,L)\setminus \Delta(\pmb{v}^\ast_0,L) \neq \varnothing$.
    • Then by the affine form $\alpha \cdot U_i^\ast + \pmb{v}_0^\ast \in L^\ast$, and by the unique closest codeword in $L$, that lead to a larger distance to $L$, which contradict to $\pmb{v}_0^\ast$ maximizing the distance.
  • Based on the interleaved code proximity test, they developed a way to test if an interleaved codeword contain message satisfying linear/quadratic constraints.
    • The trick of consistency test and evaluation test is by encoding a row of RS code into a polynomial, and using random linear combination to combine all rows into one.
    • To ZKify this, we pad a line of random codeword, and thus randomize the response polynomial from prover, which makes it simulatable.
RedShift: Transparent SNARKs from List Polynomial Commitments (univariate PCS from FRI)
  • This paper introduced a way to construct polynomial commitment from FRI.
    • Specifically, they proposed a construction for List Polynomial Commitment (LPC) from FRI.
    • By taking advantage of randomness, they can “patch” the LPC such that it commits to the actual polynomial uniquely, with minor soundness error.
  • The motivation behind LPC is that, distinguishing a sufficient close function from a valid codeword in RS code leads to large parameters.
    • This involves a concept called list decoding, that $L_\delta(f)$ denotes a list of valid codewords in RS code that are at most $\delta$-far from $f$.
    • Supposing the $\delta$ is sufficient small (smaller than unique decoding radius $\delta_0$), then $L_\delta(f)$ contain only 1 codeword.
    • that is the function constrained over RS field $D \subseteq \mathbb{F}$.
    • Instead, we can try to commit to a list of polynomials that are in $L_\delta(f)$, and complying to an additional list of point-evaluation pairs.
  • However, the LPC above doesn’t give uniqueness in normal polynomial commitment.
    • The rough idea is to take advantage of randomness sampling, picking points to patch the LPC point-evaluation pairs that $f$ must comply to.
    • The application of a $\mu$-dimensional $\varepsilon$-distinguisher happens in the “offline” stage.
    • It appends $\mu$ pairs of random point-evaluation of $f$ to the list of point-evaluation pairs for LPC.
    • The PPT distinguisher patches all points that all other $g \in L_\delta(f)$ that are not agreeing with $f$, to be evaluated by $f$.
    • Soundness error follows from Schwartz-Zippel, that for a $g \in L_\delta(f)$ that is not $f$, we have $\Pr\limits_{x \in \mathbb{F}}\left[f(x) = g(x)\right] \le \dfrac{d}{|\mathbb{F}|}$.
    • By union bound over $|L_\delta(f) -1|$ other polynomials and iterating over $\mu$ points, $\varepsilon \le \left(\dfrac{d}{|\mathbb{F}|} \cdot (|L_\delta| - 1)\right)^\mu$.
  • Finally, double-column ACM format is anti-human, definitely hate it.

TODO: Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof

TODO: Linear-Time Arguments with Sublinear Verification from Tensor Codes

Brakedown: Linear-time and field-agnostic SNARKs for R1CS (multilinear PCS from tensor-code IOPP)
  • On Brakedown, the main contributions are two folds:
    • They proved the extractability of coding based multilinear polynomial commitments, without the need of efficient decoding, this has something to do with extractor.
    • On the top of removing the need of efficient decoding, they constructed an efficient linear code with linear-time encoding from expander code.
  • The polynomial commitment scheme from BCG20 is holding the form of $g(\pmb{r}) = \langle \pmb{q}_1 \otimes \pmb{q}_2, \pmb{u}\rangle$, where $\pmb{u}$ is the Lagrange basis for $g$ over $(0, 1)^n$.
  • As for the efficient extractor without need of efficient decoder part:
    • We should start with the definition of extractor, that extractor should be ignorant of the odds of prover convincing verifier.
    • The first construction of the extractor needs to know the probability $\varepsilon$ that the prover convinces the verifier, for it needs $\varepsilon$ to estimate its runtime.
    • The second extractor construction builds on the top of the first one, that “guesses” the $\varepsilon$.
      • The extractor runs regardless what $\varepsilon$ is, in case $\varepsilon$ is not inverse poly time with $m$ and $\lambda$, and extractor won’t be in expected poly time.
      • The guessing trick is from Hazay, Lindell, and Goldreich.
    • The resulting expected runtime of second extractor turns out to be in expected poly time, given that it aborts on $2^m$ steps.
  • The claim 1 and lemma 1 for testing phase are a bit hard to comprehend; while using Ligero’s lemma 4.2 and 4.4, things are straightforward.
  • There are a lot to learn in coding theory and extractor runtime subtly (EPT) proof, I need to be better at it.
  • The linear code description in Brakedown is a bit hard to comprehend, so we defer this to the following writeup on expander code.

TODO: Brakedown’s expander code (supplementary file for Brakedown Section 4 construction)

TODO: Gemini: Elastic SNARKs for Diverse Environments (provides a way to convert univariate PCS to a multilinear PCS)

TODO: Orion: Zero Knowledge Proof with Linear Prover Time (from tensor-code IOPP)

BaseFold: Efficient Field-Agnostic Polynomial Commitment Schemes from Foldable Codes (multilinear PCS from Foldable Code IOPP)
  • The paper has following three contributions:
    • A new foldable linear code family that has a generation matrix efficiently and randomly sampled, and with high probability that the encoding has high min distance.
    • A generalization FRI IOPP for the foldable linear code, that applies to a broad class of codes (can be instantiated with RS code).
    • A construction of multilinear PC based on interleaving BaseFold and sumcheck protocol.
  • The foldable linear code derive from a family of random foldable distribution, that has high min distance with high probability.
    • The key idea behind the construction follows:
      • Starting from a MDS generation matrix for a MDS code, a natural question to ask is about how to encode a doubled length message more efficiently.
      • A construction is that, write $\pmb{m} = \pmb{m}_l \parallel \pmb{m}_r$, the codeword for next level would be $\text{Enc}_{i + 1}(\pmb{m}) = \text{Enc}_i(\pmb{m}_l) + \pmb{t}_1 \circ \text{Enc}_i (\pmb{m}_r) \parallel \text{Enc}_i(\pmb{m}_l) + \pmb{t}_2 \circ \text{Enc}_i (\pmb{m}_r)$.
      • The random foldable distribution additionally requires $\pmb{t}_1 \in (\mathbb{F}^\ast)^{n_i}$, and $\pmb{t}_1 + \pmb{t}_2 = 0$.
    • The construction above requires that, the minimum relative distance over $n$ layers of encoding should preserve to be sufficient.
    • Applying $\pmb{t}_1$ and $\pmb{t}_2$ against $\text{Enc}_i(\pmb{m}_r)$ for $\text{Enc}_{i + 1}(\pmb{m})$ will lead to additional zeros in Hamming Weight.
    • The key lemma here is to introduce rank-nullity theorem to bound the kernel size of the matrix formed by columns of the generator matrix, which help with lowering the parameters in Hamming Weight.
    • The additional zeros introduced in new level of encoding caused larger and larger min distance, that is $\Delta_{C_i} \ge \Delta_{C_j}$ for $i \le j$.
  • The IOPP for foldable linear code gives a similar vibe of FRI.
    • The main idea of the foldable linear code IOPP is somewhat going in the opposite direction of foldable linear code:
      • That is to unapply the $\pmb{t}_l$ and $\pmb{t}_r$ on left and right side of $\text{Enc}_{i + 1}(\pmb{m})$, and fold $\text{Enc}_i(\pmb{m}_l)$ and $\text{Enc}_i(\pmb{m}_r)$ with $\alpha$.
    • The main idea should derive from Ben-Sasson et al.’s paper in CCC 2018: “Worst-case to average case reductions for the distance to a code”.
  • The polynomial commitment scheme is a combination of BaseFold IOPP and sumcheck protocol.
    • The tricky part is: BaseFold IOPP only rule out an encoding far from $C_d$ will not have a distance close to $C_i$ in folding process.
    • But it won’t rule out the case that the prover shift from the folding of previous message to the encoding of another message.
    • The soundness proof focus on the bad case above, i.e., swapping over to another encoded message, instead of folding of the previous one.
    • This is done by proof of contradiction, that $\Delta_{C_k} \le \Delta_{C_d}$ contradicts to $\Delta_{C_i} \ge \Delta_{C_k}$ for any $i \le k$, which is by foldable code construction.
    • The knowledge soundness requires one to construct an EPT extractor: Gaussian elimination over $2^d$ samples of MLE bases over $\mathbb{F}^{2^d}$ against function’s coefficient form.
    • The extractor is somewhat looking like Brakedown’s, but the difference lies in the predicate forking lemma for sampling the linearly independent MLE bases.
  • The whole paper is a bit mathematical heavy, which is good for me to practice my paper reading and proving skills.

TODO: Vortex: A List Polynomial Commitment and its Application to Arguments of Knowledge

[Seen 2023/11 for Reed-Solomon Proximity Test line of work]

TODO: Fast Reed-Solomon Interactive Oracle Proofs of Proximity

TODO: Worst-Case to Average Case Reductions for the Distance to a Code (BaseFold construction derive from this paper)

TODO: DEEP-FRI: Sampling Outside the Box Improves Soundness

TODO: Proximity Gaps for Reed-Solomon Codes

TODO: Lattice (List) Decoding Near Minkowski’s Inequality

TODO: Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes

[MPC and distributed ZK related works]

TODO: Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs

TODO: Efficient Fully Secure Computation via Distributed Zero-Knowledge Proofs

Experimenting with Collaborative zk-SNARKs: Zero-Knowledge Proofs for Distributed Secrets
  • This paper specialized in introducing MPC techniques into developed SNARK schemes, and implementing relevant components for the collaborative version.
  • The main technique here is bringing linear secret sharing over elliptic curve, that avoids using MPC to lift group elements over the curve.
  • The definition of collaborative SNARK on knowledge soundness does not guarantee extraction of each sub-prover.
    • But rather, when all the prover pool information together, they can determine witnesses.
  • The definition of zero-knowledgeness in collaborative SNARK is also a bit different.
    • For a single prover, it has to be valid witness, or an honest prover cannot generate proof.
    • For collaborative proofs, each prover holds a share of witness, and eventually the reconstruction of witness is valid or not.
    • Thus the simulator need to know the validity of the witness itself.
  • To bring KZG commitment into collaborative scenario, the key is lemma 4.
    • The goal is to prove an MPC scheme replacing a sub-circuit for linear function with local computation over secret sharing is secure.
EOS: Efficient Private Delegation of zkSNARK Provers
  • This paper achieved private delegation of SNARK with efficient throughput, and malicious security at the same time.
  • The differences from OB22 are:
    • EOS uses honest delegator to minimize preprocessing cost, avoiding the cost of generating correlated randomness with PKE.
    • EOS introduces a notion of PIOP consistency check, that allows delegator to check the consistency of polynomial computation, which minimizes malicious security.
    • However, EOS requires the delegator to be also involved in the proof generation computation, while OB22 just delegates, and walks away.
zkSaaS: Zero-Knowledge SNARKs as a Service
  • An essence of secret sharing based MPC shown in this paper is the use of randomness:
    • It comes in as jointly generated random secret sharings, reconstructed and applied to target, and remvoed by deducting these random sharings.
  • This paper’s main contribution is the use of packed secret sharing:
    • The rewritten sub-protocols gives lower memory and communication, and performs “SIMD-alike” computation over secret of vector form.
    • The workload of servers involved in computation (not the large server in the center of star topology) is reduced due to packed secret sharing.
  • The nature of FFT leads to an $O(\log m)$ round naive MPC, but the paper provides a 2 round computation from packed secret sharing:
    • By arranging the vector packed in the secret, a party can last from $\log m$ to $\log \ell$ round by locally perform linear combination.
    • Once $\log \ell$ round in FFT is reached, the parties add masked randomness to sharings, and send over all computation to a server with large memory,
    • The large server taking over FFT take over the rest of the computation, and send out shaings once its computation is done.
    • The small server perform only $O(m / \ell \cdot (\log m - \log \ell))$ operations and $O(m / \ell)$ memory, due to SIMD operation from packed SS.
    • The large server additionally need $O(m \log \ell)$ operations for FFT, $O(m \log n)$ operations for secret sharing over $n$ parties, and $O(m)$ memory.

[Sumcheck Protocols]

TODO: Doubly Efficient Interactive Proofs for General Arithmetic Circuits with Linear Prover Time

[Argument System in general]

TODO: How to Construct Constant-Round Zero-Knowledge Proof Systems for NP

TODO: Succinct Non-Interactive Arguments via Linear Interactive Proofs

TODO: A Uniform Min-Max Theorem with Applications in Cryptography

TODO: Delegating Computation: Interactive Proofs for Muggles

TODO: Separating SNARGs from All Falsifiable Assumptions

TODO: Fiat-Shamir: From practice to Theory, Part I: Fiat-Shamir From Simpler Assumptions

TODO: Fiat-Shamir: From Practice to Theory, Part II: NIZK and Correlation Intractability from Circular-Secure FHE

TODO: Transparent SNARKs from DARK Compilers

TODO: Does Fiat-Shamir Require a Cryptographic Hash Function?

TODO: Fiat-Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW is not Zero-Knowledge)

TODO: Non-Interactive Batch Arguments for NP from Standard Assumptions

TODO: SNARGs for P from LWE

TODO: Algebraic Reductions of Knowledge

TODO: Batch Arguments for NP and More from Standard Bilinear Group Assumptions

TODO: Lower Bound on SNARGs in the Random Oracle Model

TODO: PPAD is as Hard as LWE and Iterated Squaring

TODO: Non-Interactive Zero-Knowledge from Non-Interactive Batch Arguments

[Fiat-Shamir with Abort Signature line of work]

TODO: Lattice Signatures Without Trapdoors

TODO: More Efficient Commitments from Structured Lattice Assumptions (BDLOP commitment)

Short Invertible Elements in Partially Splitting Cyclotomic Rings
  • First of all, think geometrically, prove algebraically.
  • Suppose we have a ring represented in CRT form. We write modulus $p = \prod p_i^{e_i}$, short elements $v$ with each entry being between $(-p_i, p_i) \setminus {0}$ are invertible.
    • Their CRT form won’t contain 0, thus they are invertible.
    • Their CRT form is a vector of same value $v$.
    • If the $\ell_\infty$-norm bound of the CRT form is beyond $p_i$, the challenge space $C$ will contain invertible elements, where 0 exists in their CRT form.
  • Suppose we have a $m^{th}$ cyclotomic polynomial $\Phi_m(x) \equiv \prod\limits_{i = 1}^{\varphi(m)}(x - r_i) \mod p$, with $r_i$ being $m^{th}$ primitive root of unities over $\mathbb{Z}_p^\ast$.
    • Then $\Phi_m(x) \equiv \Phi_{\delta(m)}(x^{m / \delta(m)}) \mod p$, with $\delta(m) = \prod\limits_{\text{prime}~p_i | m} p_i$.
    • More generally we have $\Phi_m(x) \equiv \Phi_{z}(x^{m / z}) \mod p$ for $z = \prod p_i^{f_i}$ with $1 \le f_i \le e_i$, because of $\varphi(m) = m / \delta(m) \cdot \varphi(\delta(m)) = m / z \cdot \varphi(z)$.
  • Now, let $\Phi_m(x) \equiv \prod\limits_{i = 1}^{d}f_i(x) \mod p$, also let $\Lambda$ be a set for $\pmb{z} \in R = \mathbb{Z}^{\varphi(m)} / \Phi_m(x)$ that $\pmb{z} \equiv \pmb{0} \mod (\Phi_m(x), p)$. Note that $\Lambda$ forms an ideal lattice in $R$.
    • A polynomial in $R_p$ that is invertible, then its modulo $f_i$ over $p$ should always be non zero.
    • We write $\lambda_1(\Lambda)$ as the Euclidean length of the shortest non-zero vector in $\Lambda$.
    • We have $\det(\Lambda) = | \mathbb{Z}^{\varphi(m)} / \Lambda | = p^{\varphi(m) / d}$, and we can use it to retrieve $\lambda_1(\Lambda)$ upper bounded by $\dfrac{\sqrt{\varphi(m)}}{s_1(m)} \cdot \det(\Lambda)^{1/ \varphi(m)}$.
    • Supposing $\pmb{y} \in R$ has $\pmb{y} \equiv \pmb{0} \mod (\Phi_m(x), p)$ and $\lVert \pmb{y} \rVert_2 < \lambda_1(\Lambda)$, then contradict with shortest vector in ideal lattice. (Not long enough to round back)
  • In short, given an ideal lattice $\Lambda$ in $R$, if $\forall \pmb{c} \in C$ are shorter than any shortest vector in it, then they are always invertible.

[Lattices in general]

TODO: FHE Circuit Privacy Almost For Free

TODO: Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices

TODO: Streaming Authenticated Data Structures

TODO: Chipmunk: Better Synchronized Multi-Signatures from Lattices

[Homomorphic Signatures and Commitments line of work]

TODO: Leveled Fully Homomorphic Signatures from Standard Lattices

TODO: Succinct Vector, Polynomial, and Functional Commitments from Lattices

[Leakage Resilient Secret Sharing line of work]

TODO: On the Local Leakage Resilience of Linear Secret Sharing Scheme

TODO: Constructing Locally Leakage-resilient Linear Secret-sharing Schemes

[Combinatorics Papers]

An Alternative Proof of The Schwartz-Zippel Lemma

A degree $d$ polynomial in $n$ variables cuts out a hypersurface $S$ in $\mathbb{F}^n$. There are at most $d$ intersection points between a hypersurface $S$ and an independent line (i.e., the intersection is not the whole line).

This explains separating out homogeneous $g$ of total degree $d$ from $f$: we need $g$ for constructing hypersurface $S$ in $\mathbb{F}^n$.

If one can find a direction that is everywhere independent of the hypersurface $S$, one can foliate $\mathbb{F}^n$ by parallel lines in that direction and count intersections within each line.

Question: Why we want to foliate $\mathbb{F}^n$?

Recall that, we want to upper bound the number of $\pmb{\alpha}$’s such that $f(\pmb{\alpha}) = 0$ over $\mathbb{F}^n$, namely, $|S|$ (points over $S$) over $\mathbb{F}^n$.

The foliation is parameterized by the direction’s orthogonal complement, which is isomorphic to $\mathbb{F}^{n-1}$, so the total points in $\mathbb{F}^n$ can be described by $\mathbb{F}^{n-1}$ lines, and we count intersection points between lines and hyperplane $S$ within each line.

The total number of lines is $|\mathbb{F}|^{n-1}$, while on each line either at most $d$ points or all $p$ points over the line (we eliminated this case by independence), thus the total number of hypersurface points across all of $\mathbb{F}^n$ is at most $d \cdot |\mathbb{F}|^{n-1}$.

TODO: Multilinear Schwartz-Zippel mod N with Applications to Succinct Arguments