Contents

1. Basic Concepts

• Evaluation: Given a function $f$ and an input $x$, compute the function value $y$.
• Verification: Given a function $f$, an input $x$, and a function value $y$, verify whether $y = f(x)$.

Example 1:

Evaluation: Given a multiplicative group of order $n$ and an element $g$, find its inverse $y$.

Evaluation Method:

$$y = g^{-1} = g^{-1}g^{n} = g^{n - 1}$$

Computing $g^{n - 1}$ requires calculating $g^{2},g^{4},\ldots,g^{2^{i}}$ using exponentiation, needing at least $\log n$ multiplications.

Verification: Given a multiplicative group of order $n$ and an element $g$, verify that $y$ is its inverse.

Verification Method: Check if $g \cdot y = 1$, which requires only a single multiplication.

Hence, evaluation is at least $\log n$ times more complex than verification.

Example 2:

Evaluation: Given a cyclic elliptic curve group of order $n$ with generator $G$, and a public key $X$, find the private key $x$.

Evaluation Method: A brute-force search requires $2^{n}$ operations, with each step involving at least $\log x$ point doublings.

Verification: Given a cyclic elliptic curve group of order $n$ with generator $G$, and a public key $X$, verify that its private key is $x$.

Verification Method: Check if $xG = X$, which requires only $\log x$ point doublings.

Hence, evaluation is $2^{n}$ times more complex than verification.

Thus, verification generally has a much lower computational complexity than evaluation.

Similarly, in bilinear pairings, verifying whether a pairing equation holds, such as $e(A,B) = e(C,D)$, does not involve computing the individual pairing values but instead follows a verification approach to reduce computational cost.

2. Using Residue Verification Instead of Final Exponentiation

Two elements $x,y \in F$ are equivalent if and only if there exists some $c \in F^{*}$ such that $xc^{r} = y$:

$$y^{\frac{q^{k} - 1}{r}} = \left( x^{cr} \right)^{\frac{q^{k} - 1}{r}} = x^{\frac{q^{k} - 1}{r}}c^{q^{k} - 1} = x^{\frac{q^{k} - 1}{r}}.$$

Thus, by providing $c$ as an auxiliary input, we can directly verify $xc^{r} = y$ to reduce complexity.

Theorem 1: The product of pairings is equal to 1 if and only if the Miller loop product is an $r$-th residue:

$$\prod_{i}^{}e\left( P_{i},Q_{i} \right) = 1 \Leftrightarrow \exists c \in F_{q^{k}}^{*}:\prod_{i}^{}f_{r,Q}\left( P_{i} \right) = c^{r}.$$

Proof: Let $x = \prod_{i}^{}f_{r,Q}\left( P_{i} \right)$.

Completeness (If Direction):
Suppose

$$1 = \prod_{i}^{}e\left( P_{i},Q_{i} \right) = \left( \prod_{i}^{}e\left( P_{i},Q_{i} \right) \right)^{h} = x^{h}.$$

Since $r^{2} \nmid p^{k} - 1$ and $r \cdot h = q^{k} - 1$, we have $\gcd(r,h) = 1$ and $h' = h^{-1} \mod r$

Because $x^{hh'} = 1^{h'} = 1$ and $hh' = 1 + rs$, we obtain $x^{hh'} = x^{1 + rs} = 1$ 

Therefore, $c = x^{-s}$, implying $x = c^{r}$.

Soundness (Only If Direction):

Suppose $\prod_{i}^{}f_{r,Q}\left( P_{i} \right) = c^{r}$. Raising both sides to the power of $h$, we get $\prod_{i}^{}e\left( P_{i},Q_{i} \right) = c^{rh} = 1$.

By providing $c$ as an auxiliary input, we can replace final exponentiation with $r$-residue verification, reducing computational complexity.

Theorem 2: The Product of Pairings Equals 1 If and Only If the Miller Loop Product is a $\lambda/d$-th Residue

$$\prod_{i}^{}e\left( P_{i},Q_{i} \right) = 1 \Leftrightarrow \exists c \in F_{q^{k}}^{*}:\prod_{i}^{}f_{r,Q}\left( P_{i} \right) = c^{\lambda/d}.$$

Proof: If $\prod_{i}^{}e\left( Q_{i},P_{i} \right) = 1$, then according to Theorem 1, we have $\prod_{i}^{}f_{r,Q}\left( P_{i} \right) = c^{r}$, implying $ord(c) \mid r$.

By definition, $\frac{m}{d} \nmid h$ and $\frac{m}{d}$ is not divisible by any divisor of $h$, leading to $\gcd\left( \frac{m}{d},ord(c) \right) = 1$.

Thus, there exists an integer $m'$ such that:

$$\frac{m}{d} \cdot m' = 1 \mod ord(c)$$

This means that for some $c$, we obtain:

$$\left( c^{m'} \right)^{(m/d)} = c$$

Thus, the Miller Loop can always be reduced to a $\lambda/d$-th residue.

Conversely, raising both sides to the power of $h$, we get:

$$\prod_{i}^{}f_{r,Q_{i}}\left( P_{i} \right)^{h} = \left( c^{\frac{m}{d}} \right)^{rh} = 1 = \prod_{i = 0}^{n}e\left( Q_{i},P_{i} \right)$$

Therefore, by providing an auxiliary input $c$, we can replace the final exponentiation with $\lambda/d$-th residue verification, significantly reducing computational complexity.

Lemma 1 Suppose $a$ and $u$ satisfy $a^{r} = u$. If $\prod_{i = 0}^{n}e\left( Q_{i},P_{i} \right) \neq 1$, then there does not exist $c \in F_{q}^{*}$ such that:

$$\prod_{i = 0}^{n}f_{r},Q_{i}\left( P_{i} \right) \cdot u = c^{r}$$

Proof: When $\prod_{i = 0}^{n}e\left( Q_{i},P_{i} \right) \neq 1$, we have:

$$\prod_{i = 0}^{n}f_{r},Q_{i}\left( P_{i} \right) = w^{i} \cdot s^{r}$$

where $s \in F_{q}^{*}$, $i \neq 0$, and $w$ is an $r$-th root of unity in $F_{q}^{*}$.

Conversely, if there exists $c \in F_{q}^{*}$ such that:

$$w^{i} \cdot s^{r} \cdot u = c^{r}$$

then:

$$w^{i} = \left( \frac{c}{s \cdot a} \right)^{r}$$

By the definition of $r$-th roots of unity, we know:

$$\left( w^{i} \right)^{r} = 1$$

which implies:

$$\left( \frac{c}{s \cdot a} \right)^{r} = 1$$

Thus, the order of $\frac{c}{s \cdot a}$ is $r^{2}$, contradicting the assumption that $r^{2} \nmid q^{k} - 1$.

Lemma 2: Let $b$ be a non-$d$-th residue. Then, there exists an $a$ such that: - $a$ is a non-$d$-th residue but an $r$-th residue. - $a \cdot b$ is a $d$-th residue.

Proof: Let $h = d^{s} \cdot f$, where $d \nmid f$. Choose $a$ such that $ord(a) = d^{s}$.

Since $r$ is a prime and $\gcd\left( d^{s},r \right) = 1$, it follows that $a$ is an $r$-th residue.

To prove that $a$ is a non-$d$-th residue, assume the contrary:

If there exists $b$ such that $b^{d} = a$, then given that $ord(a) = d^{s}$, this would imply:

$$ord(b) = d^{s + 1}$$

which contradicts $d^{s + 1} \nmid h$, implying $d^{s + 1} \nmid q^{k} + 1$.

Since $b$ is a non-$d$-th residue, we have:

$$b^{\left( q^{k} - 1 \right)/d} = w^{i}$$

for some $i \neq 0$ and $\left( w^{i} \right)^{d} = 1$. Moreover, $a$ is also a non-$d$-th residue, meaning all $a^{i}$ (for $i \in \lbrack 1,d - 1\rbrack$) are non-$d$-th residue.

By evaluating $\left( a^{i} \right)^{\left( q^{k} - 1 \right)/d}$, which forms a permutation over $i \in \lbrack 1,d - 1\rbrack$, there exists some $j$ such that:

$$\left( a^{j} \right)^{\left( q^{k} - 1 \right)/d} = w^{-i}$$

making $a^{j}$ a $d$-th residue.

Theorem 3: The Product of Pairings Equals 1 If and Only If the Miller Loop Output is a $d^{i}$-th Root of Unity and $\lambda$-th Residue Verification Holds

$$\prod_{i}^{}e\left( P_{i},Q_{i} \right) = 1 \Leftrightarrow \exists c,u \in F_{q^{k}}^{*}:\prod_{i}^{}f_{r,Q}\left( P_{i} \right) = c^{\lambda}u \land u^{d^{i}} = 1$$

Proof: We need to prove that there exists $x$ if and only if there exist $c,u$ such that:

$$x^{r} = c^{d}u,\quad u^{d^{i}} = 1$$

Given that $\gcd(d,rm) = 1$, there exists:

$$v = u^{(rm)^{-1} \mod d^{i}}$$

such that:

$$v^{rm} = u$$

Let $m' = m^{-1} \mod \left( q^{k} - 1 \right)$. Rewriting the equation:

$$x^{rm'} = \left( c^{d}v \right)^{rmm'}$$

Let $y = x^{m'}$, then $x = y^{m}$.

We need to show that $y$ exists if and only if there exist $c,v$ such that:

$$y = c^{d}v,\quad v^{d^{i}} = 1$$

• If $c,v$ exist, then $y$ exists.
• $y$ can be computed using the Tonelli-Shanks algorithm.
• Given $x$, we compute $c$ and $v$ from $x^{m'}$, then set $u = v^{rm}$.

Conversely, given $c,u$, we set:

$$x = \left( c^{d}u^{(rm)^{-1} \mod d^{i}} \right)^{m}$$

Thus, the theorem holds.

3. Verifying Line Coefficients Instead of Computing Lines

Instead of computing the line equation from points $T$ and $Q$, we provide the line coefficients $(\lambda,\mu)$ and verify that the line $y = \lambda x + \mu$ passes through $T$ and $Q$. This enables efficient computation of the line value at $P$.

Tangent Line Verification and Evaluation:

Given a point $T = \left( x_{1},y_{1} \right) \in E\left( F_{q^{k}} \right)$, evaluate its tangent line at $P \in E\left( F_{q} \right)$ using line coefficients $(\lambda,\mu)$.

1. Verify that $(\lambda,\mu)$ defines the tangent line passing through $T$:
   Verify $y_{1} - \lambda x_{1} = 0$ and $2\lambda y_{1} = 3x_{1}^{2}$.
2. Compute $\lambda^{2}$.
3. Compute $x_{3} = \lambda^{2} - 2x_{1}$, $y_{3} = - \mu - \lambda x_{3}$.
4. Compute ${line}_{T,Q}(P) = 1 + \lambda x'_{P} - y'_{P}\mu\omega^{3}$.

Intersection Line Verification and Evaluation:

Given points $T = \left( x_{1},y_{1} \right),Q = \left( x_{2},y_{2} \right) \in E\left( F_{q^{k}} \right)$, evaluate their intersection line at $P \in E\left( F_{q} \right)$ using coefficients $(\lambda,\mu)$.

1. Verify that $(\lambda,\mu)$ defines the line passing through $T$ and $Q$:
   Verify $y_{1} - \lambda x_{1} - \mu = 0$ and $y_{2} + \lambda x_{2} - \mu = 0$.
2. Compute $\lambda^{2}$.
3. Compute $x_{3} = \lambda^{2} - x_{1} - x_{2}$, $y_{3} = - \mu - \lambda x_{3}$.
4. Compute ${line}_{T,Q}(P) = 1 + \lambda x'_{P} - y'_{P}\mu\omega^{3}$.

Thus, by providing the coefficients $(\lambda,\mu)$, we can verify that the line passes through $T$ and $Q$ without computing it from them, reducing complexity.

4. Algorithm Overview

Define a line determined by $(\lambda,\mu) \in F_{q}^{2/k}$ with the following functions:

• line.is_tangent(T): Verifies if the line is the tangent at $T$.
• line.is_line(T, Q): Verifies if the line passes through $T$ and $Q$.
• line.evaluate(P): Evaluates the line at $P$.
• line.double(T): Performs point doubling, returning $2T$.
• line.add(T, Q): Performs point addition, returning $T + Q$.

The final algorithm of Miller Loop is optimized as follows:

from BitVM2: Bridging Bitcoin to Second Layers