Home

This post is based on the lectures by Daniele Micciancio: Introduction to lattices Let’s put parameters $m,n,q \in \mathbb{Z}$ which we describe later. Then, let’s put a uniformly random matrix $A \in \mathbb{Z}_q^{n\times m}$. Next, we put a function $f_A(\mathbf{x})\colon\, \mathbb{Z}_q^m \rightarrow \mathbb{Z}_q^n$ as follows: \[f_A(\mathb...

The Learning With Error (LWE) problems have received a lot of attention mostly because of the application to the PQ cryptography. Here we give the definitions of standard LWE and the generalized Ring-LWE which has become more popular due to cheaper operations. Standard LWE Firstly, let’s observe classic LWE where we fix an error distribution $...

Following 1 and some modern notations, I aim to describe a formal definition of a $3$-step interactive $\Sigma$-protocol with formal proofs, to help young engineers prove their $\Sigma$-protocols security. So: For an NP relation $\mathcal{R}$ a $\Sigma$-protocol is a $3$-step protocol between the Prover and the Verifier consisting of three a...

The purpose of a memory checking protocol is to allow a verifier to audit a large, untrusted memory transcript using only a small proof. The prover logs every read and write operation, generating a proof that guarantees both the correctness of the final memory state and the consistency of all operations. While most popular zkVMs use fairly stand...

The $GF(2^n)$ field First of all, let’s examine what a $GF(2^n)$ field is: it is a finite field with $2^n$ elements that is built as a field extension of $GF(2)$ using some polynomial $P(x)$ with degree $n$. It has basis $\mathcal{B} = {x^i}\big|_{0}^{n-1}$. It also has the following properties: $GF(2^n)$ is a field with characteristic $2$...

The Bulletproofs protocol when appeared made some kind of revolution in ZK world, especially in anonymous transactions where range proofs are the most complicated and important part to validate correct transfer. Today, may protocols rely on Bulletproofs of Bulletproofs+ (more advanced version) to enable range-proofs. Additionally, Bulletproofs p...

File download: Dark White Here I’m not going to describe the general definition of zk-SNARK or any related terms. Instead, I’ll try to help reader to understand the underling math of one of the first popular and novel zk-SNARK protocols called a Pinocchio protocol appeared in 2013. Special thanks to Anton Levochko and ZK-DL lectur...

Commitment Vortex has much in common with Ligero (frankly speaking, it has been built using Ligero idea). So, imagine we have a list of polynomials $f_0,\dots,f_{k-1}$. We want to commit them and evaluate at the same point at the same time. We describe each polynomial as vector $a_i$ where \[f_i(x) = \sum_{j=0}^{n-1} x^j\cdot a_{i,j}\] For si...