Home

Linear Diophantine equations

Equations of the form $\sum_i a_i x_i = 0$ where the $x_i$’s are integer unknowns are called linear Diophantine equations. Their integer solutions can be computed using greatest common denominator (GCD) tricks. In this post, we go over a few basic types of such equations and their integer solutions.

Read more

Aggregatable Subvector Commitments for Stateless Cryptocurrencies from Lagrange Polynomials

tl;dr: We build a vector commitment (VC) scheme from KZG commitments to Lagrange polynomials that has (1) constant-sized, aggregatable proofs, which can all be precomputed in $O(n\log{n})$ time, and (2) linear public parameters, which can be derived from any “powers-of-tau” CRS in $O(n\log{n})$ time. Importantly, the auxiliary information needed...

Read more

Basics of Polynomials for Cryptography

A polynomial $\phi$ of degree $d$ is a vector of $d+1$ coefficients: \begin{align} \phi &= [\phi_0, \phi_1, \phi_2, \dots, \phi_d] \end{align} For example, $\phi = [1, 10, 9]$ is a degree 2 polynomial. Also, $\phi’ = [1, 10, 9, 0, 0, 0]$ is also a degree 2 polynomial, since the zero coefficients at the end do not count. But $\phi’’ = [...

Read more

Towards Scalable Verifiable Secret Sharing and Distributed Key Generation

tl;dr: We “authenticate” a polynomial multipoint evaluation using Kate-Zaverucha-Goldberg (KZG) commitments. This gives a new way to precompute $n$ proofs on a degree $t$ polynomial in $\Theta(n\log{t})$ time, rather than $\Theta(nt)$. The key trade-off is that our proofs are logarithmic-sized, rather than constant-sized. Nonetheless, we use ou...

Read more