Lookup arguments

\gdef\vec#1{\bm{#1}} \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\set#1{\mathcal{#1}} \gdef\mset#1{\mathrm{#1}} \gdef\g{\mathrm{g}} \gdef\F{\mathbb{F}} \gdef\S{\mathcal S} \gdef\X{\mathcal X} \gdef\Z{\mathrm{Z}} \gdef\βˆ€{\mathop{\huge βˆ€}\limits}

Zero polynomials

Given a multiset \mset A over 𝔽 define the zero polynomial \Z_{\mset A} ∈ 𝔽[X] as

\Z_{\mset A}(X) = \prod_{a ∈ \mset A} \p{X - a}

Alternatively using the base set \set A βŠ† 𝔽 and multiplicities m_A: 𝔽 β†’ β„• we can collect factors

\Z_{\mset A}(X) = \prod_{a ∈ 𝔽} \p{X - a}^{m_A(a)}

To guarantee uniqueness we require m_A(a) < p where p is the characteristic of 𝔽.

The logarithmic derivative of \Z_{\mset A} has the curious property that all zeros turn into pole,s perserving multiplicities:

\frac{\Z_{\mset A}'(X)}{\Z_{\mset A}(X)} = \sum_{a ∈ \mset A} \frac{1}{X - a} = \sum_{a ∈ \set A} \frac{m_A(a)}{X - a}

Aurora lemma

Let H βŠ† 𝔽 be a multiplicative subgroup of size n, then for f ∈ 𝔽_{<n}[X]

\sum_{x ∈ H} f(x) = n β‹… f(0)

This follows from the non-zero elements of H being n-th roots of unity, that sum to zero for n>1.

\sum_{x ∈ H} x^k = \begin{cases} n & k = 0 \mod \p{n - 1} \\ 0 & \text{otherwise} \end{cases}

FK lemma

Cached Quotients

Cached quotiens (EFG22) builds on a series of prior protocols H22, ZBK+22, PAK22, GK22, ZGK+22. We want to proof that some f ∈ \F[X] evaluates to values in a certain set \S on a domain \X, i.e.

\βˆ€_{x \in \X}\quad f(x) \in \S

In H22 it is shown that this holds if and only if there exists m_s ∈ \F such that

\sum_{x ∈ \X} \frac{1}{X + f(x)} = \sum_{s ∈ \S} \frac{m_s}{X + s}

This follows from the uniqueness of the fractional decomposition and the observation that the values of f on \X should differ only in multiplicities form \S, where the multiplicity can also be zero.

This rational identity can be checked by evaluating in a random x ∈ 𝔽. Computing polynomial commitments to either side is not a problem as they both only have |\set X| non-zero terms. The challenge is to show that the commitment to the right hand side is computed correctly.

A(X) β‹… \p{T(X) + x} - m(X) = Q_A(X) β‹… \Z_{\set Y}(X)

where T(X) evaluates to \set S on the domain \set Y.

Setup

Given elliptic curve pairing \mathrm{e}:𝔾_1 Γ— 𝔾_2 β†’ 𝔾_T with generators \g_1 ∈ 𝔾_1, \g_2 ∈ 𝔾_2, \g_T ∈ 𝔾_T.

$$

$$

logUp

Lasso lookups

For fixed sparse matrix \mathrm M and committed vectors \vec v and \vec a show:

\mathrm M β‹… \vec v = \vec a

References

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