# Implementing OLE using WE-KZG

This document describes the implementation of Oblivious Linear Evaluation (OLE) using Extractable Witness Encryption for KZG Commitments (WE-KZG).

## Oblivious Linear Evaluation (OLE)

OLE is a cryptographic protocol that enables two parties to collaboratively compute a linear function without revealing their private inputs. In OLE:

- **Sender's inputs**: coefficients $a$ and $b$
- **Receiver's input**: value $x$
- **Receiver obtains**: $y = a \cdot x + b$

The sender learns nothing about $x$, and the receiver learns nothing about $a$ or $b$.

## Extractable Witness Encryption for KZG Commitments (WE-KZG)

WE-KZG is a cryptographic scheme that allows us to encrypt a message towards a commitment, point, and evaluation of a polynomial, which can be decrypted using a valid opening.

It can be thought of as an alternative to using a public-private key pair, where:

- **Public Key**: Commitment
- **Private Key**: Polynomial

A key consideration when using this scheme is that encryption requires knowledge of a point and its evaluation on the polynomial, which may not be readily available without knowing the polynomial itself. However, it is useful when the evaluations are limited or known in advance—for instance, if the polynomial represents a selection or position, such as an array of boolean values.

For a more detailed explanation, refer to [this blog post](https://www.leku.blog/kzg-we/).

## Residue Number System (RNS)

RNS is a method of representing integers using their remainders after division by a set of pairwise co-prime moduli $(m_1, m_2, \dots, m_n)$. Each integer $X$ is uniquely represented by its residues:

$$
x_i = X \bmod m_i, \quad \text{for } i = 1, 2, \dots, n
$$

This approach reduces the possible combinations needed to generate every number within the desired range, as each coefficient $x_i$ is constrained by its modulus $m_i$.

## OLE Using WE-KZG and RNS

We aim to implement Oblivious Linear Evaluation using Extractable Witness Encryption for KZG Commitments and the Residue Number System. In this protocol:

- **Sender**: Holds inputs $a$ and $b$.
- **Receiver**: Holds input $x$.
- **Goal**: The Receiver obtains $y = a \cdot x + b$ without revealing $x$ to the Sender, and without learning $a$ or $b$ beyond $y$. The Sender learns nothing about $x$ or $y$.

## Steps of the Implementation

### 1. **Receiver Encodes Input Using RNS**

The Receiver selects an integer $x$ within a predefined range and represents it using RNS with pairwise co-prime moduli.

**Example Chosen Moduli -> $RNS(7|5|3)$**

- $m_1 = 7$
- $m_2 = 5$
- $m_3 = 3$

**Maximum Representable Value:**

$$
M = m_1 \times m_2 \times m_3 = 7 \times 5 \times 3 = 105
$$

**Compute Residues:**

For each modulus $m_i$:

$$
x_i = x \bmod m_i
$$

### 2. **Receiver Constructs Selection Polynomials and Commits**

For each residue $x_i$, the Receiver constructs a **selection polynomial** $P_i(t)$ such that:

- $P_i(x_i) = 1$
- $P_i(t) = 0$ for all $t \in \{0, 1, \dots, m_i - 1\}$ and $t \ne x_i$

These polynomials will be zero at all points (from 0 to $m_i - 1$) except at $x_i$, where they evaluate to one.

**Commitments:**

- For modulus $m_i$, the Receiver computes the KZG commitment $\text{com}_{i}$ to the polynomial $P_i(t)$.
- The commitments $\text{com}_{1}, \text{com}_{2}, \text{com}_{3}$ are sent to the Sender.

### 3. **Sender Encrypts Evaluations Using WE-KZG**

The Sender wants to enable the Receiver to obtain $y = a \cdot x + b$ without learning $x$ and ensuring that only the Receiver can decrypt $y$.

**For Each Modulus $m_i$:**

1. **Compute Evaluations for All Possible Residues:**

For each possible residue $t \in \{0, 1, \dots, m_i - 1\}$:

$$
y_{i,t} = (a \cdot t + b) \bmod m_i
$$

In our $RNS(7|5|3)$ example, we'll have to calculate $n = 7 + 5 + 3 = 15$ different evaluations since we don't know $x$.

2. **Encrypt Evaluations Using WE-KZG:**

- For each $t$, the Sender creates an encryption $E_{i,t}$ of $y_{i,t}$ using WE-KZG -> $Enc(com, \alpha, \beta, msg)$.
- $E_{i,t}$ = $Enc(com_i, t, 1, y_{i,t})$
- The encryption targets the Receiver's commitment $\text{com}_{i}$, the point $t$, and the value $y_{i,t}$.
- The WE-KZG scheme ensures that only the encryption corresponding to $t = x_i$ can be decrypted by the Receiver.

### 4. **Receiver Decrypts the Relevant Evaluation**

The Receiver uses the selection polynomial $P_i(t)$ and the opening at $x_i$ to decrypt the correct encrypted value.

**For Each Modulus $m_i$:**

- Calculate opening proof $\pi = open(P_i(t), x_i)$
- Decrypt $E_{i,x_i}$ to obtain $y_i = (a \cdot x_i + b) \bmod m_i$.
- Cannot decrypt other $E_{i,t}$ values, ensuring that no additional information is learned.

### 5. **Receiver Reconstructs Final Result Using CRT**

Having obtained $y_i$ for each modulus $m_i$, the Receiver reconstructs $y = a \cdot x + b$ modulo $M$ using the Chinese Remainder Theorem (CRT).

**Compute $y$:**

Solve the system of congruences:

$$
y \equiv y_i \mod m_i \quad \text{for } i = 1, 2, 3
$$

By applying CRT, the Receiver obtains the unique $y$ modulo $M$.