Greyhound is a post-quantum, no trusted-setup and efficient polynomial commitment scheme.
Its security is based on the Module-SIS assumption:
Stated in other words, given a random matrix $A$ of size $n \cdot m$ and with coefficients in $R_q := \mathbb Z_q[X]/(X^d +1)$, it is hard to find a vector z shorter than $\beta$ such that $Az = 0$.
We can use the euclidean norm or the infinity norm for example.
The scheme takes 2 public parameters composed of 2 matrix $A \in R_q^{n \times m}$ and $B \in R_q^{n \times n\delta r}$ where $m$ is the number of rows the commitmed matrix will have and $r$ is the number of collumn the commited matrix will have. These two matrix $A$ and $B$ are generated randomly before the start of the protocol.
The matrix $D \in R_q^{n \times \delta r}$ is used to batch several prover internal proofs in order to keep the final proof succinct.
The LaBRADOR commitment scheme:
To commit a matrix $S \in R_q^{mr}$, we first represent $S$ as $r$ column vectors $s_i \in R_q^m : i \in \{1,\dots, r\}$. Then the commitment strategie is divided into two parts, the calculation of the inner commitment and the outter commitment. The actual commitment of the PCS is the outter commitment while the verification of its derivation and the material required for this is part of the proof.
The inner commitment is a vector composed of $t_i = As_i : i \in \{1;\dots,r\}$. Each $t_i$ is still in $R_q^n$ or stated differently, each $t_i$ is a polynomial of degree $n-1$ with coefficients in $\mathbb Z_q = \mathbb Z / q\mathbb Z$.
The outter commitment is the value $u = B \begin{bmatrix} \hat{t_1}\\ \vdots\\ \hat{t_r} \end{bmatrix}$such that $\hat{t_i}$ can be seen as the bit decomposition of $t_i$ (it’s equal to $G^{-1}t_i$ where $G_n = I_n \otimes [1, 2, \dots, 2^{\delta}]$ .
To understand the Greyhound protocol :
Let’s take the example of DA to really understand the polynomial commitment. Originally we have data. First we need to represent this data as $\mathbb Z_q$ elements, i.e. as finite field elements (for example $q = 2^{31}-1$ and data represented by 31-bit elements). For the example let’s say that data is of 1 MiB and $q=2^{31}-1$. For coherence with the following, we will take $N = m \cdot r \cdot d = 327680$.
Once we have our 327680 degree polynomial $f$ representing the data, it’s split into elements of $R_q$ that are degree less than $d$ polynomials. The paper says they often take $d=64$ and want to explore reduction costs with $d=1024$. So let’s assume $d=64$ for now. It means that we would split $f$ into 5120 $f_i$ polynomials in $\mathbb Z_q[X]/(X^{64}-1)$ taking the coefficient in the same order. So the first 64 coefficients of $f$ form the polynomial $f_0$ then the 64 next form the polynomial $f_1$ each of degree 63.