Dual Packing

WHIR, and Ligerito are ({\mathbb{E}},{\mathbb{E}})-IPCS for |{\mathbb{E}}| \geq \sim 2^{\lambda} where \lambda is the security parameter and indeed reduce to \mathbf{e} = \operatorname{eq}_{\mathbf{γ}} for some \mathbf{γ}. If the query happens to be an MLE evaluation, i.e. \mathbf{q} = \operatorname{eq}_{\mathbf{δ}} for some delta \mathbf{δ}, then the reduced claim \langle\mathbf{e},\mathbf{q}\rangle = \langle\operatorname{eq}_{\mathbf{γ}},\operatorname{eq}_{\mathbf{δ}}\rangle can be efficiently evaluated and the schemes are a succinct polynomial commitment scheme.

We are interested in committing to a subfield {\mathbb{F}} \subset {\mathbb{E}} and opening in with a query in \mathbb{F} or in \mathbb{E}, so what we want instead is a ({\mathbb{F}},{\mathbb{F}})- or ({\mathbb{F}},{\mathbb{E}})-IPCS. We can trivially construct those using the subfield embedding, but this has an overhead equal to the extension degree \lbrack{\mathbb{E}}:{\mathbb{F}}\rbrack. On approach to mitigate this overhead is to adapt the commitment scheme to the sparcity. Here instead we will focus on approaches that mitigate the overhead without modifying the ({\mathbb{E}},{\mathbb{E}})-IPCS. The canonical approach is ring-switch as presented in DP24 §3 and BRW26 §B. Here instead we develop it along a different route, inspired by the inner product optimization in BGKSW14 eq. 2 which was adapted to inner product commitments in a previous post. We will show that under very general assumptions, the constructions must all share the same structure. Furthermore, this structure preserves succinctness of matrix branching programs.

(𝔽,𝔽)-IPCS embedding

We will start with the simpler case where witness, query and value all lie in \mathbb{F}. Let \mathbb{E} be a degree d-extension of \mathbb{F} and \mathbf{w},\mathbf{q} \in {\mathbb{F}}^{nd}. Then we seek a triple of maps W,Q:{\mathbb{F}}^{dn} \rightarrow {\mathbb{E}}^{n},H:{\mathbb{E}} \rightarrow {\mathbb{F}} that satisfy:

\langle\mathbf{w},\mathbf{q}\rangle_{\mathbb{F}} = H\left( \langle W(\mathbf{w}),Q(\mathbf{q})\rangle_{\mathbb{E}} \right).

First we assume that W and Q act blockwise over groups of d elements, i.e.

W\left( \left( \mathbf{w}_{1},\mathbf{w}_{2},\ldots,\mathbf{w}_{n} \right) \right) = \left( W_{d}\left( \mathbf{w}_{1} \right),W_{d}\left( \mathbf{w}_{2} \right),\ldots,W_{d}\left( \mathbf{w}_{n} \right) \right)

where W_{d}:{\mathbb{F}}^{d} \rightarrow {\mathbb{E}} and similarly for Q. We first study n = 1 and assume that H is \mathbb{F}-linear. The resulting embeddings extend blockwise to arbitrary n, as shown below.

The n = 1 case extends naturally to n > 1 by doing blockwise packing, i.e. we embed using W' = I_{n} \otimes W and Q' = I_{n} \otimes Q and keep the same H. We could consider using non-uniform block packings as long as they are dual under the same H, or even mixing coordinates across different blocks, but this does not seem useful in practice and we will ignore it. Going forward, we use W and Q also for their blockwise extensions when the meaning is clear.

Under these assumptions (uniform blockwise packing and H \mathbb{F}-linear), we have characterized the possible constructions. We can choose any non-zero output map H and witness basis \left( \beta_{1},\ldots,\beta_{d} \right) and the query basis follows as the dual under H. The dual basis can be computed by forming the Gram matrix G_{ij} ≔ H\left( \beta_{i}\beta_{j} \right), inverting it in {\mathbb{F}}^{d \times d}, and computing {\mathbf{β}}^{\land} = G^{- 1}{\mathbf{β}}.

Coordinate projection

To construct a concrete dual packing, represent \mathbb{E} as {\mathbb{F}}\lbrack X\rbrack/\left( f(X) \right) for some monic degree d polynomial f irreducible over \mathbb{F}. We assume f is chosen for implementation efficiency: it is sparse with mostly low order terms.

Further we represent members of \mathbb{E} in the monomial basis \left( 1,X,X^{2},\ldots,X^{d - 1} \right). We can then represent W and Q by invertible matrices in {\mathbb{F}}^{d \times d} and H by a vector in {\mathbb{F}}^{d}. For implementation efficiency we seek an embedding with sparse W and Q. It turns out taking the most efficient choices for H and W also gives efficient Q:

Take W = I_{d} and H = (1,0,\ldots,0) selecting the X^{0} coordinate. Then the dual-basis embedding Q is given by

Q_{ij} = \begin{cases} 1 & i = j = 0 \\ - f_{i + j}/f_{0} & {i,j \geq 1\mathrm{\text{ and }}i + j \leq d} \\ 0 & \mathrm{\text{otherwise}}. \end{cases}

In particular, Q is a bordered upper anti-triangular Hankel matrix. For d = 5 it looks like

Q = \frac{1}{f_{0}}\begin{pmatrix} f_{0} & 0 & 0 & 0 & 0 \\ 0 & - f_{2} & - f_{3} & - f_{4} & - 1 \\ 0 & - f_{3} & - f_{4} & - 1 & 0 \\ 0 & - f_{4} & - 1 & 0 & 0 \\ 0 & - 1 & 0 & 0 & 0 \end{pmatrix}.

Notably f_{1} does not appear and for k > 1 the f_{k} coefficient appears k - 1 times. This perfectly matches the usual implementation preference for sparse reduction polynomials with mostly low-order terms.

When doing inner product openings, the 1/f_{0} factor can be moved out of the inner product if it is non-trivial. For the 127-bit field {\mathbb{F}}_{2}\lbrack X\rbrack/\left( X^{127} + X + 1 \right) the Q map is simply a reversal of the i > 0 coordinates. For the GHASH field {\mathbb{F}}_{2}\lbrack X\rbrack/\left( X^{128} + X^{7} + X^{2} + X + 1 \right) the map additionally needs seven XOR corrections.

Succinctness

Certain \mathbf{q} allow succinct evaluation of \widetilde{q}({\mathbf{γ}}) ≔ \langle\operatorname{eq}_{\mathbf{γ}},\mathbf{q}\rangle_{\mathbb{F}}, but this doesn’t immediately mean that the packed query Q(\mathbf{q}) can be succinctly evaluated as \langle\operatorname{eq}_{{\mathbf{γ}}'},Q(\mathbf{q})\rangle_{\mathbb{E}}. We will show that for a large class of succinct \mathbf{q} this is the case. First we define what succinctness means:

A vector \mathbf{q} \in {\mathbb{F}}^{n} for n = 2^{k} is called succinct if it admits a tensor decomposition

\begin{bmatrix} m_{10} \\ m_{11} \end{bmatrix} \otimes \begin{bmatrix} m_{20} \\ m_{21} \end{bmatrix} \otimes \cdots \otimes \begin{bmatrix} m_{k0} \\ m_{k1} \end{bmatrix}

where typically m_{ij} \in {\mathbb{F}}. The multilinear extension of \mathbf{q}, viewed as a function on \left\{ 0,1 \right\}^{k}, then becomes

\widetilde{q}(\mathbf{r}) = \prod_{i \in \lbrack k\rbrack}\left( \left( 1 - r_{i} \right)m_{i0} + r_{i}m_{i1} \right).

which can be evaluated in O(k) field operations.

More generally, the coefficients m_{ij} need not themselves be field elements. It suffices that they belong to an associative \mathbb{F}-algebra in which every complete product m_{1b_{1}}m_{2b_{1}}\cdots m_{kb_{k}} evaluates to an element of \mathbb{F}. Consequently, every vector entry and every value of the multilinear extension remains an element of \mathbb{F}. As the m_{ij} no longer need to be commutative we must therefore also fix a permutation of the variables \mathbf{r}.

Since every finite-dimensional associative algebra admits a matrix representation, we may, without loss of generality, assume that the objects m_{ij} are matrices. In fact, it suffices to take m_{ij} \in {\mathbb{F}}^{w_{i} \times w_{i + 1}} with boundary dimensions w_{1} = w_{k + 1} = 1. We call \max w_{i} the width of the representation, which is known as a matrix branching program.

The canonical example of a succinct vector is the multilinear evaluation vector \operatorname{eq}_{\mathbf{r}} itself, obtained by taking m_{i0} = 1 - r_{i} and m_{i1} = r_{i}. Another classical example is the geometric progression \left( 1,x,x^{2},\ldots \right) obtained by taking m_{i0} = 1 and m_{i1} = x^{2^{i}}. An illustrative non-scalar example is the counting vector (0,1,2,\ldots) represented by

\begin{aligned} m_{1b} & = \begin{bmatrix} 2 & b \end{bmatrix} & m_{ib} & = \begin{bmatrix} 2 & b \\ 0 & 1 \end{bmatrix} & m_{kb} & = \begin{bmatrix} b \\ 1 \end{bmatrix}. \end{aligned}

Preservation of Succinctness

An important property of dual packing is that it preserves succinctness if the block size aligns with the tensor decomposition:

(𝔽,𝔼)-IPCS embedding

Assume now that we wish to open a base-field witness \mathbf{w} \in {\mathbb{F}}^{nd} with an extension-field query \mathbf{q} \in {\mathbb{E}}^{nd}, to proof the claim \langle\mathbf{w},\mathbf{q}\rangle_{\mathbb{E}} = h for some h \in {\mathbb{E}}. We present a one-round batching protocol analogous to the one in DP24 and BRW26.

Batching protocol

Given a dual packing (W,Q,H) and an arbitrary basis \left( \beta_{1},\ldots,\beta_{d} \right) for {\mathbb{E}}/{\mathbb{F}}, we reduce the extension-field claim by decomposing into basis coordinates and batching the resulting claims with a random linear combination.

Preservation of succinctness

The opening claim reduces to \langle\operatorname{eq}_{\mathbf{γ}},\mathbf{q}'\rangle_{\mathbb{E}} and a natural question is if \mathbf{q}' is succinct if \mathbf{q} is. We will show that if \mathbf{q} has max width w then \mathbf{q}' has max width dw.

While the width increases by a factor d, the interior matrices have coefficients in \mathbb{F}. Using dense matrix evaluation and schoolbook extension arithmetic, the online evaluation costs only a factor d more base-field operations, rather than d^{2}.

For MLE queries, this matches the performance of DP24 and BRW26, which also have proof size d^{2} and require d evaluations of \widetilde{\mathbf{q}}.

References