Home

We have already examined the Ring-LWE problem in a previous post, so now let’s consider some practical examples of what we can build using it. In my opinion, 1 is one of the most interesting and fundamental works. In this post, I briefly go through this paper, leaving some comments collected from different materials. We know that the Ring-LWE...

It is assumed that the reader is already familiar with the basics of Bitcoin, Bitcoin script, cryptography, and atomic swaps, and knows the difference between an image and a preimage. This article aims to give a precise but understandable description of how Lightning Network payments are performed under the hood, which may be useful for new Ligh...

Let’s define the following list of configurations for each attack: GOAL — the goal of an attack; ATK — a type or a certain attack name; PROP — additional property for an attack (if needed). We say that a cryptosystem is $v(\lambda)$-GOAL-ATK-PROP secure if, for any PPT adversary $\mathcal{A}$, the following holds: \[\texttt{Adv}_\math...

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

The Learning With Errors (LWE) problems have received a lot of attention mostly because of their application to 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 First, let’s observe classic LWE, where we fix an error distribution $...

Following 1 and some modern notation, 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)$ of degree $n$. It has a basis $\mathcal{B} = {x^i}\big|_{0}^{n-1}$. It also has the following properties: $GF(2^n)$ is a field with characteristic $2$...