Preliminaries

This page is a description of the cryptographic components we use as building blocks to design the protocol.

Polynomial commitment:

A polynomial commitment is a useful cryptographic tool, used to commit to a polynomial. Intuitively, the commitment will bind and hide the content of it, namely, the polynomial. Furthermore, the prover has the ability to give an evaluation point of the polynomial and the proof of its correctness, without leaking other information of the polynomial.

Formally, a polynomial commitment consists of three algorithms:

• Commit$(\phi(.))$: the algorithm outputs a commitment $R$ of the polynomial $(\phi(.))$.

• Prove$(\phi, \vec{x},R)$: given an evaluation point $\phi(\vec{x})$, the algorithm outputs a tuple$<\vec{x}, \phi(\vec{x}), \pi_{\vec{x}}>$ , where $\pi_{\vec{x}}$ is the proof.

• VerifyEval$(\vec{x}, \phi(\vec{x}), \pi_{\vec{x}}, R)$: given $(\vec{x}, \phi(\vec{x}), \pi_{\vec{x}}, R)$ the algorithm checks if $\phi(\vec{x})$ is the correct evaluation. The algorithm outputs accept or reject.

Linear code:

A linear error-correcting code with message length $k$ and codeword length $n$ is a linear subspace $C ∈ F^n$, such that there exists an injective mapping from message to codeword $E_C : F^k → C$, which is called the encoder of the code.

• Any linear combination of codewords is also a codeword.

• The rate of the code is defined as $\frac{k}{n}$ .

• The distance between two codewords $u, v$ is the hamming distance denoted as $∆(u, v)$.

• The minimum distance is $d = min_{u,v} ∆(u, v)$.

Such a code is denoted as $[n, k, d]$ linear code, and we also refer to $\frac{d}{n}$ as the relative distance of the code.

Tensor code:

Let $C$ be a $[n, k, d]$ linear code, the tensor code $C^{⊗2}$ of dimension 2 is the linear code in $F^{n^2}$ with message length $k^2$ , codeword length $n^2$ , and distance $nd$. We can view the codeword as a $n × n$ matrix. We define the encoding function below:

1. A message of length $k×k$ is parsed as a $k×k$ matrix. Each row of the matrix is encoded using $E_C$ , resulting in a codeword $C_1$ of size $k × n$.

2. Each column of $C_1$ is then encoded again using $E_C$ . The result $C_2$ of size $n × n$ is the codeword of the tensor code.