Introduction

Welcome to this book dedicated to Zero-Knowledge Proofs(ZK) and their applications in modern cryptography. Zero-Knowledge Proofs are magical, inspiring, passionate, and, more importantly, breathtaking. This book will compile documentation and specifications on ZK algorithms, aiming to provide researchers, developers, and cryptography enthusiasts with in-depth insights and guidance.

As this is a work in progress, we are continually learning and evolving our understanding of the subject. If you find any errors or areas for improvement, please feel free to provide feedback.

Please note that this book is a work in progress, and not necessarily to reflecting the latest developments in the ZK field.

Terminology

This document establishes a consistent terminology and notation for the concepts commonly used in the context of zero-knowledge proofs (ZKPs). It aims to make the presentation clear and concise, particularly for readers with a background in cryptography or mathematics. The following conventions will be used throughout the book:

Fields and Curves

1. Finite Fields:

• ${\mathbb{F}}_p$: Denotes a general finite field of prime order $p$.

2. Elliptic Curves:

• ${\mathbb{F}}_r$: Scalar field
• ${\mathbb{F}}_q$: Base field

Algebra

In zero-knowledge proofs, algebra plays a crucial role as it provides the foundational framework for constructing complex mathematical structures and algorithms. These structures ensure the security and privacy of information, allowing verifiers to confirm the truth of a statement without revealing specific details. We will provide an introductory overview of groups, rings, fields, Number Theoretic Transform (NTT), and Multi-Scalar Multiplication (MSM).

Groups

• Introduction
• Groups And Abelian Groups
  • Basic Definitions
  • Example of Groups
• Cyclic groups

Introduction

This document provides a simple introduction to group theory and its key role in cryptography. Group theory is essential for building many cryptographic systems, including encryption, digital signatures, and zero-knowledge proofs (ZKPs). These mathematical structures ensure that operations like encryption and authentication are secure and reliable.

We’ll start by defining groups, abelian groups, and cyclic groups, which are the backbone of many cryptographic algorithms. For example, the security of RSA encryption relies on group properties, and protocols like ECDSA use elliptic curves, which are based on group theory. Cyclic groups are crucial for creating secure ZKP systems like the Schnorr protocol, which is widely used for authentication.

Throughout the article, we’ll highlight how these abstract mathematical concepts directly contribute to secure communication in cryptography.

Groups And Abelian Groups

In cryptography, group theory plays a fundamental role, especially in modern public-key cryptography and protocol design. A group is an algebraic structure consisting of a set of elements and a binary operation that satisfies closure, associativity, identity element, and invertibility. Below are some key applications of group theory in cryptography:

• Underpins many widely used signature schemes, such as RSA and ECDSA.
• Many ZKP protocols use group operations, particularly cyclic groups, to construct secure proof systems. For instance, the Schnorr protocol is a zero-knowledge proof system based on cyclic groups and the discrete logarithm problem, widely used for authentication and privacy-preserving systems.

Let's begin with a definition and then some examples.

Basic Definitions

Binary operation: Let $\mathbb{G}$ be a set. A binary operation is a map of sets: $$\circ :\mathbb{G}\times \mathbb{G}\to \mathbb{G}.$$ For ease of notation we write $\circ (a,b)=a\circ b$, for all $a,b$ in $\mathbb{G}$. Any binary operation on $\mathbb{G}$ gives a way of combining elements. If $\mathbb{G}=\mathbb{Z}$(the set of integers $\mathbb{Z}$, so denoted because the German word for numbers is Zahlen) then $+$ and $\times$ are natural examples of binary operations.

Group: A group is a set $\mathbb{G}$, together with a binary operation $\circ$, such that the following hold:

• (Associativity):The operation is associative;that is, $(a\circ b)\circ c=a\circ (b\circ c)$ for all $a,b,c$ in $\mathbb{G}$.
• (Existence of identity): There is an element $e$ (called the identity) in $\mathbb{G}$ such that $a\circ e=e\circ a=a$ for all $a$ in $\mathbb{G}$.
• (Existence of inverses): For each element $a$ in $\mathbb{G}$, there is an element $b$ in $\mathbb{G}$(called an inverse of $a$ and denoted by $a^{-1}$) such that $a\circ b=b\circ a=e$.

Abelian group: If the operation is $commutative$, that is the $group$ has the property that $a\circ b=b\circ a$ for every pair of elements a and b, we say the group is $Abelian$.

Example of Groups

• The integers $\mathbb{Z}=\{...,-1,0,1,2,...\}$ form a group under the operation of addition. The binary operation on two integers $m,n$ in $\mathbb{Z}$ is just their sum. Since the integers under addition already have a well-established notation, we will use the operator $+$ instead of $\circ$; that is, we shallwrite $m+n$ instead of $m\circ n$.The identity is 0, and the inverse of $n$ in $\mathbb{Z}$ is written as $-n$ instead of $n^{-1}$.
• The integers mod $n$ form a group under additon modulo $n$.Consider ${\mathbb{Z}}_5$, consisting of the equivalence classes of the integers 0, 1, 2, 3, and 4. We define the group operation on ${\mathbb{Z}}_5$ by modular addition. We write the binary operation on the group additively; that is, we write $m+n$. The element 0 is the identity of the group and each element in ${\mathbb{Z}}_5$ has an inverse. For instance, $3+2=2+3=0$.
• Not every set with a binary operation is a group. For example, if we let modular multiplication be the binary operation on ${\mathbb{Z}}_n$, then ${\mathbb{Z}}_n$ fails to be a group. The element 1 acts as a group identity since $1\cdot k=k\cdot 1=k$ for all $k$ in ${\mathbb{Z}}_n$.Even if we consider the set ${\mathbb{Z}}_n\backslash \{0\}=\{1,2,3,...,n-1\}$, we still may not have a group. For instance, let 2 in ${\mathbb{Z}}_6$.Than 2 has no multiplicative inverse since$$\begin{gathered} 0\cdot 2=0 \\ 1\cdot 2=2 \\ 2\cdot 2=4 \\ 3\cdot 2=6 \\ 4\cdot 2=8 \\ 5\cdot 2=10 \end{gathered}$$

Cyclic groups

A group $\mathbb{G}$ is called cyclic if there exists an element $g\in \mathbb{G}$ such that every element $a\in \mathbb{G}$ can be written as $g^n$ (for some integer $n$).In other words:$\mathbb{G}=g^n:n\in \mathbb{Z}$ where $g^n$ means applying the group operation to $g$ $n$ times. In this case $g$ is a $generator$ of $\mathbb{G}$.

Rings

• Definitions
  • Rings
  • unity or identity
  • commutative rings
  • division rings
• Examples

A $group$ is a set equipped with only one binary operation.But many sets are naturally endowed with two binary operations: addition and multiplication, and are denoted as usual by "+" and $\cdot$, respectively. Examples that quickly come to mind are the integers, the integers modulo n, the real numbers, matrices, and polynomials. When considering these sets as groups, we simply used addition and ignored multiplication. In many instances, however, one wishes to take into account both addition and multiplication. One abstract concept that does this is the concept of a $ring$.

Definitions

Rings

By a $ring$ we mean a set $\mathbb{A}$ with operations called addition and multiplication which satisfy the following axioms:

• $\mathbb{A}$ with additon alone is an abelian group.
• Multiplication is associative. That is, for all a,b, and c in $\mathbb{A}$, $$(a\cdot b)\cdot c=a\cdot (b\cdot c)$$
• Multiplication is distributive over addition. That is, for all a,b, and c in $\mathbb{A}$, $$a\cdot (b+c)=a\cdot b+a\cdot c$$ and $$(b+c)\cdot a=b\cdot a+c\cdot a$$

Since $\mathbb{A}$ with addition alone is an abelian group, there is in $\mathbb{A}$ a neutral element for addition: it is called the $zero$ element and is written 0. Also, every element has an additive inverse called its $negative$; the negative of $a$ is denoted by $-a$. Subtraction is defined by $$a-b=a+(-b)$$

unity or identity

If there is an element $1\in \mathbb{A}$ such that $1\ne 0$ and $1\cdot a=a\cdot 1=a$ for each element $a\in \mathbb{A}$, we say that $\mathbb{A}$ is a ring with $unity$ or $identity$.

commutative rings

A ring $\mathbb{A}$ for which $a\cdot b=b\cdot a$ for all a, b in $\mathbb{A}$ is called a $commutativering$.

division rings

A $divisionring$ is a ring $\mathbb{A}$, with an identity, in which every nonzero element in $\mathbb{A}$ is a $unit$; that is, for ech $a\in \mathbb{A}$ with $a\ne 0$,there exists a unique element $a^{-1}$ such $a^{-1}\cdot a=a\cdot a^{-1}=1$.

Examples

The easiest examples of $rings$ are the traditional number systems. The set $\mathbb{Z}$ of the integers, with conventional additon and addition and multiplication, is a ring called the $ringoftheintegers$. We designate this ring simply with the letter $\mathbb{Z}$. Similarly, $\mathbb{Q}$ is the ring of the rational numbers, $\mathbb{R}$ is the ring of the real numbers; and $\mathbb{C}$ is the ring of the complex numbers. In each case, the operations are conventional addition and multiplication.

We must remember, that the elements of a ring are not necessarily numbers(for example, there are rings of polynomials/rings of functions, rings of switching circuits, and so on);and therefore "addition" does not necessarily refer to the conventional addition of numbers, nor does multiplications necessarily refer to the conventional operation of multiplying numbers. In fact, $+$ and $\cdot$ are nothing more than symbols denoting the two operations of a $ring$ .

for instance, $\mathcal{F}(\mathbb{R})$ represents the set of all the functions from $\mathbb{R}$ to $\mathbb{R}$;that is, the set fo all real-valued functions of a real variable:if $f$ and $g$ are any two functions from $\mathbb{R}$ to $\mathbb{R}$,their sum $f+g$ and their $productf\cdot g$ are defined as follows: $$[f+g](x)=f(x)+g(x)\text{for every real number x}$$ and $$[f\cdot g](x)=f(x)\cdot g(x)\text{for every real number x}$$ $\mathcal{F}(\mathbb{R})$ with these operations for adding and multiplying functions is a ring called $ringofrealfunctions$.It is written simply as $\mathcal{F}(\mathbb{R})$.

The rings $\mathbb{Z},\mathbb{Q},\mathbb{R},\mathbb{C}$ and $\mathcal{F}(\mathbb{R})$ are all $infiniterings$, that is, rings with infinitely many elements. There are also $finiterings$: rings with a finite number of elements.As an important example, consider the group ${\mathbb{Z}}_n$,and define an operation of multiplication on ${\mathbb{Z}}_n$ by allowing the product $a\cdot b$ to be the remainder of the usual product of integers $a$ and $b$ after division by $n$(For example, in ${\mathbb{Z}}_5$， $2\cdot 4=3,3\cdot 3=4$, and $4\cdot 3=2$.)This operation is called $multiplicationmodulon$. ${\mathbb{Z}}_n$ with addition and multiplication modulo $n$ is a ring.

Fields

• Definition Field
• Example
• Finite Fields and Their Efficient Implementations

In many applications, a particular kind of integral domain called a $field$ is necessary.

Definition Field

Field.A commutative division ring is called a $field$. That is, a set $\mathbb{A}$ with operations called addition "+" and multiplication "$\cdot$" which satisfy the following axioms:

• $(\mathbb{A},+)$ is an abelian group.
• $(\mathbb{A}\backslash \{0\},\cdot )$ is an abelian group.
• Multiplication is distributive over addition.

Example

• $\mathbb{Q},\mathbb{R},\mathbb{C}$ are all fields;
• if $p$ is a prime number, $Z_p$ is a field, usually denote this field by ${\mathbb{F}}_p$;
  • ${\mathbb{F}}_p$ is a $finitefield$. The elements of ${\mathbb{F}}_p$ are the set of natural numbers $\{0,1,2,3,4,...,p-1\}$. The $order$ of the set is $p$. That is, the number of elements in this set is $p$.
  • The identity for addition "+" is 0
  • The identity for multiplication "$\cdot$" is 1
  • Add$(x,y)$ = $(x+y)(\mathrm{mod}p)$
  • Sub$(x,y)$ = $(x-y)(\mathrm{mod}p)$
  • Mul$(x,y)$ = $(x\cdot y)(\mathrm{mod}p)$
  • Div$(x,y)$ = $(x\cdot y^{-1})=(x\cdot y^{p-2})(\mathrm{mod}p)$
• 2 is a prime nummber, so ${\mathbb{F}}_2$ is a field whose elements are $\{0,1\}$.
  • $0+0=0$
  • $0+1=1+0=1$
  • $1+1=0$
  • $0\ast 0=0$
  • $0\ast 1=1\ast 0=0$
  • $1\ast 1=1$
  • You'll find that addition is equivalent to XOR, and multiplication is equivalent to AND.
• 7 is a prime number, so there is a field whose elements are $\{0,1,2,3,4,5,6\}$.
  • $\frac{1}{2}=1\cdot 2^{7-2}(\mathrm{mod}7)=2^5(\mathrm{mod}7)=32(\mathrm{mod}7)=4$
• let q = 21888242871839275222246405745257275088696311157297823662689037894645226208583, q is a prime number, so there is a field whose elements are $\{0,1,2,...,21888242871839275222246405745257275088696311157297823662689037894645226208582\}$.

Finite Fields and Their Efficient Implementations

The efficient implementation of finite fields can be referenced at: http://cacr.uwaterloo.ca/hac/about/chap14.pdf.

Number Theoretic Transform

Number Theoretic Transform(NTT) is an efficient algorithm for polynomial multiplication, akin to the Fast Fourier Transform (FFT). It operates in finite fields, making it particularly valuable in cryptography and coding theory, where it enables rapid computations on large numbers and polynomials. For the purposes of this document, polynomials are assumed to be defined over finite fields by default.

Polynomial Multiplication

Let's consider two polynomials: $A(x)=x^2+3x+2$        $B(x)=2x^2+1$
The product $C(x)=A(x)\cdot B(x)$ can be expressed as:
$C(x)=(x^2+3x+2)(2x^2+1)$
By expanding, we find: $C(x)=x^2(2x^2+1)+3x(2x^2+1)+2(2x^2+1)$
$C(x)=2x^4+x^2+6x^3+3x+4x^2+2$
$C(x)=2x^4+6x^3+5x^2+3x+2$

In a programming context, we can represent polynomials as follows:
$A(x)=2+3x+x^2\to A=[2,3,1]$
$B(x)=1+2x^2\to B=[1,0,2]$
$C(x)=2+3x+5x^2+6x^3+2x^4\to C=[2,3,5,6,2]$
$C[k]$ = coefficient of $k^{th}$ degree term of polynomial $C(x)$

$A(x)=a_0+a_{1}x+a_2{x}^2+...+a_d{x}^d$
$B(x)=b_0+b_{1}x+b_2{x}^2+...+b_d{x}^d$
$C(x)=c_0+c_{1}x+c_2{x}^2+...+c_{2d}{x}^{2d}$
Using the distributive property, the runtime for multiplying two polynomials of degree $d$ is $O(d^2)$.However, is there a more efficient method?

Polynomial Representation

Coefficient Representation

$P(x)=p_0+p_{1}x\to [p_0,p_1]$
To illustrate this representation visually,we can use an interactive graph where the coefficients can be adjusted:

Value Representation

$P(x)=p_0+p_{1}x\to [(x_0,P(x_0)),(x_1,P(x_1))]$ A polynomial can also be uniquely defined by its values at some specific points. For example, two points define a unique line:

• For points$(-2,0)$ and $(2,2)$, we have $P(x)=1+0.5s$.
• For points$(3,0)$ and $(-1,4)$, we have $P(x)=3-x$.

Three points define a quadratic polynomial:

• $\{(-3,1),(-1,-1),(1,3)\}\to P(x)=\frac{3}{4}{x}^2+2x+\frac{1}{4}$
• $\{(-1,0),(0,1),(1,0),(2,1)\}\to P(x)=\frac{2}{3}{x}^3-x^2-\frac{2}{3}x+1$

More generally,$(d+1)$ points uniquely define a polynomial of degree $d$: $$\{(x_0,P(x_0)),(x_1,P(x_1)),...,(x_d,P(x_d))\}$$ $$P(x)=p_0+p_{1}x+p_2{x}^2+...+p_d{x}^d$$ $$\begin{gathered} P(x_0)=p_0+p_1{x}_0+p_2{x}_0^2+...+p_d{x}_0^d \\ P(x_1)=p_0+p_1{x}_1+p_2{x}_1^2+...+p_d{x}_1^d \\ ⋮ \\ P(x_d)=p_0+p_1{x}_d+p_2{x}_d^2+...+p_d{x}_d^d \end{gathered}$$ That is: $$\begin{array}{c}\left[\begin{array}{c}P(x_0)\\ P(x_1)\\ ⋮\\ P(x_d)\end{array}\right]=\underset{M}{\underbrace{\left[\begin{array}{ccccc}1& x_0& x_0^2& \cdots & x_0^d\\ 1& x_1& x_1^2& \cdots & x_1^d\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& x_d& x_d^2& \cdots & x_d^d\end{array}\right]}}\left[\begin{array}{c}{p}_0\\ p_1\\ ⋮\\ p_d\end{array}\right]\end{array}$$ $M$ is invertible for unique $x_0,x_1,...,x_d$ $\Rightarrow$ Unique $p_0,p_1,...,p_d$ exists $\Rightarrow$ Unique polynomial $P(x)$ exists.

Punchline: Two Unique Trpresentations for Polynomials $$P(x)=p_0+p_{1}x+p_2{x}^2+...+p_d{x}^d$$ $$1.\underset{\text{Coefficient Representation}}{\underbrace{[p_0,p_1,...,p_d]}}$$ $$2.\underset{\text{Value Representation}}{\underbrace{(x_0,P(x_0),(x_1,P(x_1)),...,(x_d,P(x_d)))}}$$

Value Representation Advantages

$\underset{[(-2,1),(-1,0),(0,1),(1,4),(2,9)]}{A(x)=x^2+2x+1}\underset{[(-2,9),(-1,4),(0,1),(1,0),(2,1)]}{B(x)=x^2-2x+1}\underset{Degree4\to 5points}{\underbrace{C(x)=A(x)\cdot B(x)}}$
and $\begin{array}{r}[(-2,1),(-1,0),(0,1),(1,4),(2,9)]\\ \times [(-2,9),(-1,4),(0,1),(1,0),(2,1)]\\ [(-2,9),(-1,0),(0,1),(1,0),(2,9)]\end{array}$
$\Rightarrow$ $\underset{[(-2,9),(-1,0),(0,1),(1,0),(2,9)]}{C(x)=A(x)\cdot B(x)}$ $\Rightarrow$ $\underset{[(-2,9),(-1,0),(0,1),(1,0),(2,9)]}{C(x)=x^4-2x^2+1}$

In value representation, multiplication can be performed in linear time $O(d)$ rather than quadratic $O(d^2)$. This is especially advantageous when working with large polynomials.

Polynomial Multiplication Flowchart

Polynomial Evaluation

Evaluation from Coefficients to Values

To evaluate a polynomial $P(x)=p_0+p_{1}x+p_2{x}^2+...+p_d{x}^d$ at $n\ge d+1$ points,we can compute as follows: $$\begin{array}{c}(1,P(1))\\ (2,P(2))\\ ⋮\\ (n,P(n))\end{array}\Rightarrow \underset{O(nd)⟺O(d^2)}{\underbrace{\begin{array}{c}(1,p_0+p_1\cdot 1+p_2\cdot 1^2+\cdots +p_d\cdot 1^d)\\ (2,p_0+p_1\cdot 2+p_2\cdot 2^2+\cdots +p_d\cdot 2^d)\\ ⋮\\ (n,p_0+p_1\cdot n+p_2\cdot n^2+\cdots +p_d\cdot n^d)\end{array}}}$$ Howerer, this operation can have a complexity of $O(nd)$, which could lead to $O(d^2)$.

More Efficient Strategies

For example, when evaluatiing $P(x)=x^2$ at 8 points, we can select symmetric points such as
$$\begin{gathered} (1,1)(-1,1) \\ (2,4)(-2,4) \\ (3,9)(-3,9) \\ (4,16)(-4,16) \end{gathered}$$.
We have $P(-x)=P(x)$.

For $P(x)=x^3$ we can select:
$$\begin{gathered} (1,1)(-1,-1) \\ (2,8)(-2,-8) \\ (3,27)(-3,-27) \\ (4,64)(-4,-64) \end{gathered}$$
We have $P(-x)=-P(x)$.

So we only need 4 points!

• $$P(x)=3x^5+2x^4+x^3+7x^2+5x+1$$ $$Evaluateatnpoints\pm x_1,\pm x_2,\dots ,\pm x_{\frac{n}{2}}$$ $$P(x)=(2x^4+7x^2+1)+(3x^5+x^3+5x)=\underset{P_e(x^2)}{\underbrace{(2x^4+7x^2+1)}}+x\underset{P_o(x^2)}{\underbrace{(3x^4+x^2+5)}}$$ $$P(x)=P_e(x^2)+x{P}_o(x^2)$$ $$\begin{array}{l}P(x_i)=P_e(x_i^2)+x_i{P}_o(x_i^2)\\ P(-x_i)=P_e(x_i^2)-x_i{P}_o(x_i^2)\end{array}\}\text{Lot of overlap!}$$ $$P_e(x^2)=2x^2+7x+1P_o(x^2)=3x^2+x+5$$ $$P_e(x^2)\text{ and }{P}_o(x^2)\text{ have degree 2!}$$

• $$P(x)=p_0+p_{1}x+p_2{x}^2+\cdots +p_{n-1}{x}^{n-1}$$ $$\text{Evaluate at }n\text{ points }\pm x_1,\pm x_2,\dots ,\pm x_{\frac{n}{2}}$$ $$P(x)=P_e(x^2)+x{P}_o(x^2)$$ $$\begin{array}{l}P(x_i)=P_e(x_i^2)+x_i{P}_o(x_i^2)\\ P(-x_i)=P_e(x_i^2)-x_i{P}_o(x_i^2)\end{array}\}\text{Lot of overlap!}$$ $$P_e(x^2)\text{ and }{P}_o(x^2)\text{ have degree }\frac{n}{2}!$$

$$\underset{\text{Same process on simpler problem}}{\underbrace{\text{Evaluate }{P}_e(x^2)\text{ and }{P}_o(x^2)\text{ each at }{x}_1^2,x_2^2,\dots ,x_{\frac{n}{2}}^2(\frac{n}{2}\text{ points})}}$$

But that is one major problem. $$\text{Points }[\pm x_1,\pm x_2,\dots ,\pm x_{fracn2}]are\pm paired.$$ $$\text{Points }[x_1^2,x_2^2,\dots ,x_{\frac{n}{2}}^2]\text{ are not }\pm \text{ paired.}$$ $$\text{Recursion breaks!}$$ $$\text{Is it possible to make }[x_1^2,x_2^2,\dots ,x_{\frac{n}{2}}^2\pm \text{ paired?}$$ We can choose the roots of unity in the finite field.

Which Evaluation Points to Use?

To evaluation $P(x)=p_0+p_{1}x+p_2{x}^2+\cdots +p_d{x}^d$, we need at least $n\ge (d+1)$ points, ideally $n=2^k$ for $k\in \mathbb{Z}$. The points chosen should be the $n^{th}$ roots of unity:

$$\text{Evaluate }P(x)\text{ at }[1,{\omega }^1,{\omega }^2,\dots ,{\omega }^{n-1}]$$ whers $\omega$ is a root of $z^n=1$.

NTT Implementation

def FFT(P):
    # P- [p0,p1,...,p_{n-1}] coeff representation
    n=len(P) # n is a power of 2
    if n==1:
        return P
    w = get_root_of_unity(n)
    P_e,P_o = [P[0],P[2],...,P[n-2]],[P[1],P[3],...,P[n-1]]
    y_e,y_o = FFT(P_e), FFT(P_o)
    y = [0]*n
    for j in range(n/2):
        y[j] = y_e[j]+w^j*y_o[j]
        y[j+n/2] = y_e[j]-w^j*y_o[j]
    return y

Interpolation and Inverse NTT

Alternative Perspective on Evaluation/NTT

$$P(x)=p_0+p_{1}x+p_2{x}^2+\cdots +p_{n-1}{x}^{n-1}$$ $$\begin{array}{c}\left[\begin{array}{c}P(x_0)\\ P(x_1)\\ ⋮\\ P(x_{n-1})\end{array}\right]=\left[\begin{array}{ccccc}1& x_0& x_0^2& \cdots & x_0^{n-1}\\ 1& x_1& x_1^2& \cdots & x_1^{n-1}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& x_{n-1}& x_{n-1}^2& \cdots & x_{n-1}^{n-1}\end{array}\right]\left[\begin{array}{c}{p}_0\\ p_1\\ ⋮\\ p_{n-1}\end{array}\right]\end{array}$$
$$x_k={\omega }^k\text{ where }\omega \text{ is a root of unity in the finite field}$$ That is $$\begin{array}{c}\left[\begin{array}{c}P(x_0)\\ P(x_1)\\ ⋮\\ P(x_{n-1})\end{array}\right]=\underset{\text{Discrete Fourier Transform (DFT) matrix}}{\underbrace{\left[\begin{array}{ccccc}1& 1& 1^2& \cdots & 1^{n-1}\\ 1& \omega & {\omega }^2& \cdots & {\omega }^{n-1}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\omega }^{n-1}& {\omega }^{2(n-1)}& \cdots & {\omega }^{(n-1)(n-1)}\end{array}\right]}}\left[\begin{array}{c}{p}_0\\ p_1\\ ⋮\\ p_{n-1}\end{array}\right]\end{array}$$

Interpolation involves inversing the DFT matrix

$$P(x)=p_0+p_{1}x+p_2{x}^2+\cdots +p_{n-1}{x}^{n-1}$$ $$\begin{array}{c}\begin{array}{c}\left[\begin{array}{c}{p}_0\\ p_1\\ ⋮\\ p_{n-1}\end{array}\right]={\left[\begin{array}{ccccc}1& 1& 1^2& \cdots & 1^{n-1}\\ 1& \omega & {\omega }^2& \cdots & {\omega }^{n-1}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\omega }^{n-1}& {\omega }^{2(n-1)}& \cdots & {\omega }^{(n-1)(n-1)}\end{array}\right]}^{-1}\left[\begin{array}{c}P(x_0)\\ P(x_1)\\ ⋮\\ P(x_{n-1})\end{array}\right]\end{array}\\ \Downarrow \\ \begin{array}{c}\left[\begin{array}{c}{p}_0\\ p_1\\ ⋮\\ p_{n-1}\end{array}\right]=\frac{1}{n}\left[\begin{array}{ccccc}1& 1& 1^2& \cdots & 1^{n-1}\\ 1& {\omega }^{-1}& {\omega }^{-2}& \cdots & {\omega }^{-(n-1)}\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\omega }^{-(n-1)}& {\omega }^{-2(n-1)}& \cdots & {\omega }^{-(n-1)(n-1)}\end{array}\right]\left[\begin{array}{c}P(x_0)\\ P(x_1)\\ ⋮\\ P(x_{n-1})\end{array}\right]\end{array}\end{array}$$
The inverse matrix and original matrix look quite similar! Every $\omega$ in original matrix is now $\frac{1}{n}{\omega }^{-1}$

$$INTT(<values>)⟺NTT(<values>)\text{ wit }{\omega }^{\prime }=\frac{1}{n}{\omega }^{-1}$$

So the implementation of inverse NTT as follows:

def IFFT(P):
    # P- [p0,p1,...,p_{n-1}] coeff representation
    n=len(P) # n is a power of 2
    if n==1:
        return P
    w = 1/n*(get_root_of_unity(n)^{-1})
    P_e,P_o = [P[0],P[2],...,P[n-2]],[P[1],P[3],...,P[n-1]]
    y_e,y_o = FFT(P_e), FFT(P_o)
    y = [0]*n
    for j in range(n/2):
        y[j] = y_e[j]+w^j*y_o[j]
        y[j+n/2] = y_e[j]-w^j*y_o[j]
    return y

Multi-Scalar Multiplication

• Bucket method

The Multi-Scalar Multiplication(MSM) problem involves calculating the sum of multiple elliptic curve points, represented ad:
$$P=\sum _{i=1}^n{k}_i{G}_i$$ Here, $k_i$ are scalars(integers modulo a prime), $G_i=(x_i,y_i)$ are elliptic curve points. $k_i{G}_i$ indicates that $G_i$ is added to itself $k_i$ times.
Given that about 75% of the time spent producing a zk-SNARK proof is dedicated to $MSM$, optimizing this operation is essential for enhancing overall performance.

Bucket method

We can break down the Multi-Scalar Multiplication problem into smaller sums and reduce the number of operations by applying the windowing technique. Before we compute $k_i{G}_i$,it's important to note that each scalar $k_i$ can be represented in binary. This representation allows us to express $k_i{G}_i$ in a more efficient manner.

For each $k_i$, we can segment its binary representation into windows of size $c$:
$$k_i=k_{i,0}+k_{i,1}{2}^c+k_{i,2}{2}^{2c}+\cdots +k_{i,m-1}{2}^{c(m-1)}.$$ Using this approach, we can express the scalar multiplication $k_i{G}_i$ as:
$$k_i{G}_i=k_{i,0}{G}_i+k_{i,1}{G}_i+k_{i,2}{G}_i+\cdots +k_{i,m-1}{2}^{c(m-1)}{G}_i.$$
This allows us to rewrite the MSM problem as:
$$P=\sum _{i=1}^n{k}_i{G}_i=\sum _{i=1}^n\sum _{j=0}^{m-1}{k}_{i,j}{2}^{cj}{G}_i$$
By changing the order of summation, we have:
$$P=\sum _{j=0}^{m-1}{2}^{cj}(\sum _{i=1}^n{k}_{i,j}{G}_i)$$

weher we first break the scalars into windows and then aggregate the points in each window. Now we can focus on efficiently calculating each $B_j:$
$$B_j=\sum _{i=1}^n{k}_{i,j}{G}_i=\sum _{\lambda =0}^{2^c-1}\lambda \sum _{u(\lambda )}{G}_u$$
with the inner summation over $u(\lambda )$ considering only points with the coefficient $\lambda$. This leads us to organize points into the corresponding lambda buckets（if $c=3$):
$$B_j=\sum _{\lambda =1}^{2^c-1}\lambda S_{j,\lambda }=S_{j,1}+2S_{j,2}+3S_{j,3}+4S_{j,4}+5S_{j,5}+6S_{j,6}+7S_{j,7}.$$
We can compute this with minimal point additions using partial sums:
$T_{j,1}=S_{j,7},T_{j,2}=T_{j,1}+S_{j,6},T_{j,3}=T_{j,2}+S_{j,5},T_{j,4}=T_{j,3}+S_{j,4},T_{j,5}=T_{j,4}+S_{j,3},T_{j,6}=T_{j,5}+S_{j,2},T_{j,7}=T_{j,6}+S_{j,1}.$
Each of these operations involves just one elliptic point addition. We can obtain the final result by summing these partial sums:
$$B_j=\sum _k{T}_{j,k}.$$

Elliptic Curve And It's Applications

• Introduction
• What is Elliptic Curve
  • The Group Law
• Elliptic Curve's Applications
  • What is discrete logarithm problem
  • ECDSA
  • Diffie-Hellman Key Exchange
  • Schnorr protocol
• Short Weierstrass curves and their representations for fast computations

Introduction

Elliptic curves are a fascinating area of mathematics with profound implications in number theory and cryptography. They provide a rich structure that can be utilized in various applications, particularly in secure communication protocols. In this article, we will explore the fundamental properties of elliptic curves, their group law, and how these mathematical concepts form the basis for several cryptographic algorithms. By understanding elliptic curves, we can gain insight into the underlying principles that ensure the security and efficiency of modern cryptographic systems.

What is Elliptic Curve

An elliptic curve is the graph of an short Weierstrass equation
$$y^2=x^3+Ax+B$$
where $A$ and $B$ are constants. Below is an example of such a curve.

The Group Law

• Adding Points on an Elliptic Curve
  Start with two points
  $$P_1=(x_1,y_1),P_2=(x_2,y_2)$$
  on an elliptic curve $E$ given by the equation $y^2=x^3+Ax+B$. Define a new point $P_3$ as follows. Draw the line $L$ through $P_1$ and $P_2$. We'll see below that $L$ intersects $E$ in a third point $P_3^{\prime }$. Reflect $P_3^{\prime }$ across the $x-$axis (i.e., change the sign of the $y$-coordinate) to obtain $P_3$. We define
  $$P_1+P_2=P_3$$
  Examples below will show that shis is not the same as adding coordinates of the points. It might be better to denote this operation by $P_1+P_2$, but we opt for the simpler notation since we will never be adding points by adding coordinates.
  Assume first that $P_1\ne P_2$ and that neither point is $\infty$. Draw the line $L$ through $P_1$ and $P_2$. Its slope is
  $$m=\frac{y_2-y_1}{x_2-x_1}.$$
  If $x_1=x_2$, then $L$ is vertical. We'll treat this case later, so let's assume that $x_1\ne x_2$. The equation of $L$ is then
  $$y=m(x-x_1)+y_1.$$
  To find the intersection with $E$, substitute to get
  $$(m(x-x_1)+y_1{)}^2=x^3+Ax+B.$$
  This can be rearranged to the form
  $$0=x^3-m^2{x}^2+\dots .$$
  The three roots of this cubic correspond to the three points of intersection of $L$ with $E$. Generally, solving a cubic is not easy, but in the present case we already know two of the roots, namely $x_1$ and $x_2$, since $P_1$ and $P_2$ are points on both $L$ and $E$. Therefore, we could factor the cubic to obtain the third value of x. But there is an easier way. If we have a cubic polynomial $x^3+a{x}^2+bx+c$ with roots $r,s,t$, then
  $$x^3+a{x}^2+bx+c=(x-r)(x-s)(x-t)=x^3-(r+s+t)x^2+\dots .$$ Therefore,
  $$r+s+t=-a.$$
  If we know two roots $r,s$, then we can recover the third as $t=-a-r-s$.
  In our case, we obtain
  $$x=m^2-x_1-x_2$$
  and
  $$y=m(x-x_1)+y_1.$$
  Now, reflect across the $x-$axis to obtain the point $P_3=x_3,y_3$:
  $$x_3=m^2-x_1-x_2,y_3=m(x_1-x_3)-y_1.$$
  In the case that $x_1=x_2$ but $y_1\ne y_2$, the line through $P_1$ and $P_2$ is a vertical line, which therefore intersects E in $\infty$. REflecting $\infty$ across the $x-$axis yields the same point $\infty$(this is why we put $\infty$ at both the top and the bottom of the $y-$axis).Therefore, in this case $P_1+P_2=\infty$.
  Now consider the case where $P_1=P_2=(x_1,y_1).$ When two points on a curve are very close to each other, the line through them approximates a tangent line. Therefore, when the two points coincide, we take the line $L$ through them to be the tangent line. Implicit differentiation allows us to find the slope $m$ of $L$:
  $$2y\frac{dy}{dx}=3x^2+A,\text{ so }m=\frac{dy}{dx}=\frac{3x_1^2+A}{2y_1}.$$
  If $y_1=0$ then the line is vertical and we set $P_1+P_2=\infty$, as before. Therefore, assume that $y_1\ne 0$. The equation of $L$ is
  $$y=m(x-x_1)+y_1,$$
  as before. We obtain the cubic equation
  $$0=x^3-m^2{x}^2+\dots .$$ This time, we know only one root, namely $x_1$, but it is a double root since $L$ is tangent to $E$ at $P_1$. Therefore, proceeding as before, we obtain
  $$x_3=m^2-2x_1,y_3=m(x_1-x_3)-y_1.$$
  Finally, suppose $P_2=\infty$. The line through $P_1$ and $\infty$ is a vertical line that intersects $E$ in the point $P_1^{\prime }$ that is the reflection of $P_1$ across the $x-$axis. When we reflect $P_1^{\prime }$ across the $x-$axis to get $P_3=P_1+P_2$, we are back at $P_1$. Therefore
  $$P_1+\infty =P_1$$
  for all points $P_1$ on $E$. Of course, we extend this to include $\infty +\infty =\infty$.
  Let's summarize the above discussion:

Let $E$ be an elliptic curve defined by $y^2=x^3+Ax+B$. let $P_1=(x_1,y_1)$ and $P_2=(x_2,y_2)$ be points on $E$ with $P_1,P_2\ne \infty$. Define $P_1+P_2=P_3=(x_3,y_3)$ as follows:

• If $x_1\ne x_2$, then $x_3=m^2-x_1-x_2,y_3=m(x_1-x_3)-y_1,$ where $m=\frac{y_2-y_1}{x_2-x_1}$.
• If $x_1=x_2$ but $y_1\ne y_2$, then $P_1+P_2=\infty$.
• If $P_1=P_2$ and $y_1\ne 0$, then $x_3=m^2-2x_1,y_3=m(x_1-x_3)-y_1$, where $m=\frac{3x_1^2+A}{2y_1}$.
• If $P_1=P_2$ and $y_1=0$, then $P_1+P_2=\infty$.
  Moreover, define
  $$P+\infty =P$$
  for all points $P$ on $E$.

The addition of points on an elliptic curve $E$ satisfies the following properties:

• (Commutativity) $P_1+P_2=P_2+P_1$ for all $P_1,P_2$ on $E$.
• (existence of identity) $P+\infty =P$ for all points $P$ on $E$.
• (existence of inverses) Given $P$ on $E$, there exists $P^{\prime }$ on $E$ with $P+P^{\prime }=\infty$. This point $P^{\prime }$ will usually be denoted $-P$.
• (associativity) $(P_1+P_2)+P_3=P_1+(P_2+P_3)$ for all $P_1,P_2,P_3$ on $E$. In other words, the points on $E$ form an additive abelian group with $\infty$ as the identity element.