## RSA Accumulators

An RSA accumulator is an authenticated set built from cryptographic assumptions in hidden-order groups such as $\mathbb{Z}_N^*$. RSA accumulators enable a prover, who stores the full set, to convince any verifier, who only stores a succinct digest of the set, of various set relations such as (non)membership, subset or disjointness. For example, ...

## Catalano-Fiore Vector Commitments

A vector commitment (VC) scheme allows a prover with access to a vector $\mathbf{v} = [ v_1, \dots, v_n ]$ to convince any verifier that position $i$ in $\mathbf{v}$ stores $v_i$ for any index $i\in[n]$. Importantly, verifers only store a succinct digest of the vector (e.g., a 32-byte hash) rather than the full vector $\mathbf{v}$.

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.