Embedding Inner Products

\gdef\p#1{\left({#1}\right)} \gdef\ceil#1{\left\lceil{#1}\right\rceil} \gdef\norm#1{\left|{#1}\right|} \gdef\setn#1{\mathcal{#1}} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\F{\mathbb{F}} \gdef\Z{\mathbb{Z}} \gdef\vd{𝛅} \gdef\i{\mathrm{i}} \gdef\j{\mathrm{j}} \gdef\om{\mathrm{\omega}}

In cryptographic protocols it's useful to compute inner products over small fields \F_p while using a large extension field \F_{p^d}. The naive approach of embedding \F_p into \F_{p^d} directly incurs a d overhead in memory and d^2 overhead in multiplications. In this article I present an approach based on bilinear embeddings that is simple, has no memory overhead, and only a d overhead in multiplications.

Inner Product Commitment Schemes

Recent commitment schemes such as WHIR (AC+24) and Ligerito (NA25) are not just multivariate polynomial commitment schemes, but something more general: inner product commitment schemes. Let's quickly define these:

Definition 1. An Inner Product Commitment Scheme has \mathsf{commit}, \mathsf{open} and \mathsf{verify} algorithms.

  • The \mathsf{commit} algorithm takes a vector \vec v \in \F_q^n and outputs a commitment C to \vec v.
  • The \mathsf{open} algorithm takes a commitment C, a vector \vec w \in \F_q^n and a value y \in \F_q and outputs a proof \pi that the inner product \vec v \cdot \vec w = \sum_{i \in [0,n)} v_i \cdot w_i equals y.
  • The \mathsf{verify} algorithm takes C, \vec w, y, \pi and outputs true if the proof is valid and false otherwise.

Observe that this generalizes over polynomial commitment schemes: Take \vec v to be coefficients in some basis and \vec w to be evaluations of the basis polynomials at a certain point. This works regardless of the basis so this includes Lagrange, monomial and multivariate bases.

Aside: Verifier Succinctness

In the definition above, the verifier needs to process a vector \vec w of size n. This is not ideal, as we would like the verifier's work to be sub-linear in n. Both WHIR and Ligerito only require the verifier to compute a single value from \vec w:

\widetilde{w} = \sum_{i \in [0,n)} \mathrm{eq}_i(\vec x) \cdot w_i

for some \vec x \in \F_q^k. Here k \geq \log_2 n and \mathrm{eq}_i(\vec x) is the multi-linear basis polynomial that is 1 at i and 0 at all other indices, with indices interpreted as corners on the \{0,1\}^k hypercube.

In the general case, this requires O(n) work, but for many useful structures of \vec w this can be computed more efficiently. Classifying these efficient structures is a topic for a future post. For now I'll just note that they include monomial and multi-linear polynomial basis evaluation, so an inner product commitment scheme with this succinctness property is also a succinct polynomial commitment scheme.

Small Fields and Bilinear Embeddings

For technical reasons, we want to use WHIR over a large field, i.e. \norm{\F_q} > 2^{128}. However, many applications require inner products over a small field, e.g. \F_p for p a 31-bit prime. Typically this is solved by using a field extension \F_{p^d} with d large enough that \norm{\F_{p^d}} > 2^{128}.

One can then take the natural embedding of \F_p^n into \F_{p^d}^n by mapping each element of \F_p to its representation in \F_{p^d}. Applying this to both vectors, the inner product can be computed in \F_{p^d}. The downside of this approach is that the vectors grow in size by a factor d in memory, and the computation by a factor d^2. To reduce this overhead, several solutions have been proposed, notably Ring-Switching (DP24) as used in Binius. Here I'll present a different, simpler approach that generalizes over a clever embedding discovered by Bryan Gillespie for inner products in multi-party computation (BG+24 eq. 2).

Inner products are an example of a bilinear map, and the general embedding of bilinear maps in finite algebras looks like this:

Definition 2. Given a bilinear map f:𝔽^n Γ— 𝔽^m β†’ 𝔽^k and a finite 𝔽-algebra K, an embedding or packing of f in K is a triplet of linear maps (\mat A, \mat B, \mat C) such that for all \vec x ∈ 𝔽^n, \vec y ∈ 𝔽^m we have

f(\vec x, \vec y) = \mat C \p{\mat A \vec x β‹…_K \mat B \vec y }

where \mat A: 𝔽^n β†’ K, \mat B: 𝔽^m β†’ K and \mat C: K β†’ 𝔽^k, and β‹…_K denotes multiplication in K.

Note that K is isomorphic to 𝔽^l for some l and given a representation of K the \mat A, \mat B, \mat C are represented by matrices.

Lemma 3. If f is symmetric (i.e. f(x,y) = f(y,x) for all x, y) and (\mat A, \mat B, \mat C) is an embedding, then so is (\mat B, \mat A, \mat C).

This lemma is useful as we will have \mat A the identity and this allows us to choose to apply \mat B to either the committed vector or the weights vector.

Results for Inner Products

The main result we'll derive here is

Lemma 4. \F_q inner products can be embedded in \F_{q^d} for d = 2^n \cdot 3^m with \mat A = \mat I, \mat B a sparse matrix and \mat C the projection on the first coordinate.

The restriction on the extension degree is likely not necessary in practice but it is hard to prove. Furthermore,

Let's focus on embedding \F_q^d inner products in \F_{q^d}. Larger vectors can be handled by zero padding to the next largest multiple of d and doing a k=\ceil{\frac{n}{d}}-sized inner product in \F_{q^d}^k.

Lemma 5. Given a field \F_{q^d} over \F_q represented by \F_q [X]/(X^d - m_1 β‹… X - m_0), there exists an embedding of the \F_q^d inner product in \F_{q^d} with \mat A the identity \mat I, \mat C the projection on the first coefficient (1, 0, \dots, 0), and \mat B the monomial matrix

\begin{bmatrix} 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 0 & \cdots & 0 & m_0^{-1} \\ 0 & 0 & 0 & \cdots & m_0^{-1} & 0 \\ \vdots & \vdots &\vdots & \ddots & \vdots & \vdots \\ 0 & 0 & m_0^{-1} & \cdots & 0 & 0\\ 0 & m_0^{-1} & 0 & \cdots & 0 & 0 \end{bmatrix}\text{.}

Proof: The embedding of vectors (a_0, a_1, \dots, a_{d-1}) and (b_0, b_1, \dots, b_{d-1}) results in

\begin{align*} a & = a_0 + a_1 \cdot X + \cdots + a_{d-1} \cdot X^{d-1} \\ b & = b_0 + m_0^{-1} \cdot \p{ b_{d-1} \cdot X + \cdots + b_1 \cdot X^{d-1}} \\ \end{align*}

The product aβ‹…b has powers up to X^{2β‹…(d-1)}. Note that in the quotient we have X^d = m_0 + m_1 β‹… X. Of the unreduced product, only X^0 and X^d contribute to the constant term of the reduced result. To see this, consider a term X^{d + k} with k ∈ [1, d-2]:

X^{d + k} = (m_0 + m_1 β‹… X) β‹… X^k = m_0β‹…X^k + m_1β‹…X^{k+1}

since k >0 and k+1 < d this does not contribute to X^0. Thus the constant term is given by

a_0 \cdot b_0 + m_0 \cdot \p{a_1 \cdot m_0^{-1} \cdot b_1 + \cdots + a_{d-1} \cdot m_0^{-1} \cdot b_{d-1}}

which is the inner product as required.

Note that the \mat B matrix is a monomial matrix over \F_q, i.e. a generalized permutation matrix that allows for non-zero entries other than 1. These can be applied in at most n multiplications.

Example 6. Complex Numbers. The field \mathbb{C} is \mathbb{R}[X]/(X^2 + 1). Here m_1 = 0 and m_0 = -1. The embedding matrix \mat B is thus

\mat B = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}\text{.}

The map \mat B happens to correspond to complex conjugation. The inner product of two real vectors (a_0, a_1) and (b_0, b_1) can thus be computed as the real part of

(a_0 + a_1 \i) \cdot \overline{(b_0 + b_1 \i)} = (a_0 b_0 + a_1 b_1) + (a_1 b_0 - a_0 b_1) \i \text{.}

Lemma 5 requires an irreducible polynomial of the form X^d - m_1 β‹… X - m_0 over \F_q. Such polynomials are typically easy to find. It is however hard to prove that they exist. By construction they always exist for d=2 and by the Hansen–Mullen theorem (HM92 conj. B, later proven) we know they exist for d=3, but beyond that it is hard to prove. Instead, to get to larger fields we can use towers of extensions.

Lemma 7. (Towers) Given a \F_q^m inner product embedding in \F_{q^m} given by (\mat A_m, \mat B_m, \mat C_m) and an \F_{q^m}^n inner product embedding in \F_{q^{m \cdot n}} given by (\mat A_n, \mat B_n, \mat C_n), we can construct an \F_q^{m \cdot n} inner product embedding in \F_{q^{m \cdot n}} as

(\mat A_n' \cdot (\mat I_n \otimes \mat A_m), \mat B_n' \cdot (\mat I_n \otimes \mat B_m), \mat C_m \cdot \mat C_n')

where \mat A_n', \mat B_n', \mat C_n' are \mat A_n, \mat B_n, \mat C_n represented with coefficients in \F_q, \mat I_n is the n \times n identity matrix and \otimes denotes the Kronecker product.

Proof: Given vectors \vec x, \vec y ∈ \F_q^{m \cdot n} we can interpret them as \vec x = (\vec x_0, \vec x_1, \dots, \vec x_{n-1}) and \vec y = (\vec y_0, \vec y_1, \dots, \vec y_{n-1}) with \vec x_i, \vec y_i ∈ \F_q^m. Using the first embedding we turn this into an \F_{q^m}^n inner product

\sum_{i \in [0,n)} \vec x_i \cdot \vec y_i = \sum_{i \in [0,n)} \mat C_m \p{\mat A_m \vec x_i β‹…_{\F_{q^m}} \mat B_m \vec y_i} = \mat C_m \p{\sum_{i \in [0,n)} \mat A_m \vec x_i β‹…_{\F_{q^m}} \mat B_m \vec y_i}\text{.}

This \F_{q^m}^n inner product is over two vectors

\begin{align*} \vec{\widetilde x} &= (\mat A_m \vec x_0, \mat A_m \vec x_1, \dots, \mat A_m \vec x_{n-1}) = (\mat I_n \otimes \mat A_m) \vec x \\ \vec{\widetilde y} &= (\mat B_m \vec y_0, \mat B_m \vec y_1, \dots, \mat B_m \vec y_{n-1}) = (\mat I_n \otimes \mat B_m) \vec y \text{.} \end{align*}

Applying the second embedding we get

\begin{align*} C_n \p{\mat A_n \vec{\widetilde x} β‹…_{\F_{q^{m \cdot n}}} \mat B_n \vec{\widetilde y}} &= C_n \p{\mat A_n' \cdot (\mat I_n \otimes \mat A_m) \vec x β‹…_{\F_{q^{m \cdot n}}} \mat B_n' \cdot (\mat I_n \otimes \mat B_m) \vec y} \text{.} \end{align*}

where we used the mixed-product property of the Kronecker product. Finally, we need to apply \mat C_m to get back to \F_q, and this gets us the desired result.

Observe that the Kronecker product of identity matrices is an identity matrix, the Kronecker product of monomial matrices is a monomial matrix and the product of the first-coordinate projections is a first-coordinate projection. This proofs Lemma 4 by induction, starting from the base cases d=2 and d=3 from Lemma 5 and applying Lemma 7 repeatedly.

While \mat B_n is monomial this does not guarantee that \mat B_n' is monomial. In practice we can and want to find values of m_0 that make this the case, and if we do then monomiality is preserved in towering.

Example 8. Mersenne 31. Take p = 2^{31} - 1 and a tower of extensions over \F_p as:

\begin{align*} \F_{p^2} &= \F_p [\i]/(\i^2 + 1) \\ \F_{p^6} &= \F_{p^2} [\j]/(\j^3 - 5) \end{align*}

then inner products can be embedded in \F_{p^6} with \mat B =

\begin{pmatrix} 1 & \phantom{-}0 & 0 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 & 0 & 0 \\ 0 & \phantom{-}0 & 0 & 0 & \phantom{-}5^{-1} & 0 \\ 0 & \phantom{-}0 & 0 & 0 & 0 & -5^{-1} \\ 0 & \phantom{-}0 & \phantom{-}5^{-1} & 0 & 0 & 0 \\ 0 & \phantom{-}0 & 0 & -5^{-1} & 0 & 0 \\ \end{pmatrix}\text{.}

The method presented here prescribes a particular representation of the field \F_{q^d}, but one can use any representation and make the appropriate change of basis to (\mat A, \mat B, \mat C) matrices. This won't necessarily preserve their sparsity, but it will still be an embedding. Fortunately, the prescribed representation is already very efficient and typical of what one would choose in practice.

Overhead

The embedding is perfect in the sense that no memory is wasted. The overhead to apply \mat B is also minimal, as it is a monomial matrix. The main overhead is in the field multiplications.

Directly evaluating the inner product would take n multiplications in \F_q. Using the embedding in \F_{q^d}, we need k = \ceil{\frac{n}{d}} multiplications in \F_{q^d}. Each multiplication in \F_{q^d} takes d^2 multiplications in \F_q using schoolbook multiplication. Thus the overhead is

\frac{d^2 \cdot k}{n} \leq \frac{d^2 \cdot (n/d + 1)}{n} = d + \frac{d^2}{n} \text{.}

For the expected case of n \gg d the number of multiplications increases roughly by the extension degree d.

Open questions

References

Sage Implementation

Here is a Sage implementation of the \mat A, \mat B embeddings described above:

def embed(x, extension_field, kind):
    # Check vector
    if not isinstance(x, FreeModuleElement):
        raise TypeError("x is not a vector")
    if x.base_ring() is extension_field:
        return x
    if x.base_ring() is not extension_field.base_ring():
        if extension_field.degree() > 1:
            # Tower: Recursively embed in base field first.
            x = embed(x, extension_field.base_ring(), kind)
        else:
            raise ValueError("x is not a vector over the base field")

    # Check extension
    X = extension_field.gen()
    m = extension_field.modulus()
    d = m.degree()
    if m[d] != 1 or list(m.dict().keys()) not in [[0, 1, d], [0, d]]:
        raise ValueError("extension not of form X^d - m_1 X - m_0")

    # Compute embedding coefficients
    if kind == 'A':
        c = [X^i for i in range(d)]
    elif kind == 'B':
        a = 1/(-m[0])
        c = [X^0] + [a * X^(d - i) for i in range(1, d)]
    else:
        raise ArgumentError("kind must be 'A' or 'B'")

    # Compute embedded vector (implicitly zero-pads)
    r = vector(extension_field, [0] * ((len(x) + d - 1) // d) )
    for i in range(len(x)):
        r[i // d] += c[i % d] * x[i]
    return r

And here's a test for various extension of M31:

F = GF(2^31 - 1)
R = PolynomialRing(F, 'X')
X = R.gen()

# Plain extensions over F
F2.<i> = F.extension(X^2 + 1)
F3 = F.extension(X^3 - 5, 'X')
F4 = F.extension(X^4 - X - 1, 'X')
F5 = F.extension(X^5 - 5 * X - 1, 'X')
F6 = F.extension(X^6 - 5, 'X')
F8 = F.extension(X^8 - 16 * X - 1, 'X')

# Towered extensions over F2
R2 = PolynomialRing(F2, 'X')
X = R2.gen()
F22 = F2.extension(X^2 - X - 2 * i, 'X')
F23 = F2.extension(X^3 - 5, 'X')

for n in range(100):
    for _ in range(100):
        # Generate random vectors of length n
        x = VectorSpace(F, n).random_element()
        y = VectorSpace(F, n).random_element()
        expected = x * y

        for FE in [F, F2, F3, F4, F5, F6, F8, F22, F23]:
            assert FE.is_field()

            # Embed in FE and compute FE dot product
            xe = embed(x, FE, 'A')
            ye = embed(y, FE, 'B')
            result = xe * ye

            # (Recursively) extract constant coefficient
            while result.parent() != F:
                result = result[0]

            # Check against base field dot product
            assert result == expected

Remco Bloemen
Math & Engineering
https://2Ο€.com