opaque-lattice/docs/LEAP_ANALYSIS.md

# From Split-Blinding to LEAP: Achieving True Unlinkability

## 1. The Fingerprint Attack on Split-Blinding

### 1.1 The Split-Blinding Protocol

In our split-blinding construction, the client sends two ring elements:

```
C   = A·(s + r) + (e + eᵣ)     [blinded password encoding]
Cᵣ  = A·r + eᵣ                 [blinding component]
```

Where:
- `s, e` are deterministically derived from the password
- `r, eᵣ` are fresh random per session
- `A` is the public parameter
- All operations are in the ring `Rq = Zq[X]/(Xⁿ + 1)`

### 1.2 The Fatal Flaw

A malicious server computes:

```
C - Cᵣ = A·(s + r) + (e + eᵣ) - A·r - eᵣ
       = A·s + e
```

**This value is deterministic from the password alone!**

The server can store `(session_id, A·s + e)` and link all sessions from the same user
by checking if `C - Cᵣ` matches any previously seen fingerprint.

### 1.3 The Fundamental Tension

| Property | Requirement | Conflict |
|----------|-------------|----------|
| **Determinism** | Output must be same for same password | Something must be fixed per password |
| **Unlinkability** | Server cannot correlate sessions | Nothing can be fixed per password |

These appear contradictory. The key insight: **the server must not be able to extract any deterministic function**.

---

## 2. Why OT-Based OPRFs Work

### 2.1 Bit-by-Bit Oblivious Transfer

In OT-based Ring-LPR (Shan et al. 2025):

```
For each bit bᵢ of the password encoding:
  1. Server prepares: (V₀ᵢ, V₁ᵢ) = evaluations for bit=0 and bit=1
  2. Client selects: Vᵢ = V_{bᵢ}ᵢ via 1-of-2 OT
  3. Server learns nothing about bᵢ
```

The selection is hidden by OT security. Server evaluates **both** options but cannot determine which the client chose.

### 2.2 Why It's Slow

256 bits × 2 evaluations × OT overhead = **~86ms**

The OT protocol requires multiple rounds and exponentiations per bit.

---

## 3. The LEAP Solution: Vector-OLE

### 3.1 VOLE Correlation

Vector Oblivious Linear Evaluation (VOLE) provides correlations of the form:

```
Sender holds:    (Δ, b)
Receiver holds:  (a, c)
Correlation:     c = a·Δ + b
```

Where the receiver knows `a` (the input) and `c` (the output), but NOT `Δ` (the key).
The sender knows `Δ` and `b`, but NOT `a` or `c`.

### 3.2 VOLE-Based OPRF

The LEAP construction uses VOLE to achieve oblivious evaluation:

```
Setup:
  - Server key: k ∈ Rq (small)
  - Public: A ∈ Rq

Protocol:
  1. Client and Server run VOLE with:
     - Receiver (Client) input: s (password-derived)
     - Sender (Server) input: k (secret key)
     
  2. VOLE outputs:
     - Client receives: y = k·s + Δ (masked evaluation)
     - Server receives: random shares (learns nothing about s)
     
  3. Client unblinds using their share of Δ
```

### 3.3 Why Fingerprinting Fails

Unlike split-blinding where client sends `(C, Cᵣ)`:
- In VOLE, the "blinding" is **jointly computed**
- Server contributes to the randomness but cannot recover `A·s + e`
- The protocol transcript is computationally indistinguishable from random

---

## 4. The Spring PRF with LWR

### 4.1 Learning With Rounding (LWR)

Instead of using reconciliation helpers (which leak information), Spring uses LWR:

```
PRF_k(x) = ⌊A·k·x⌋_p   (rounded to modulus p < q)
```

The rounding **absorbs** the error locally:
- No helper bits needed from server
- Client can compute the rounding independently
- Error is "hidden" in the rounded-away bits

### 4.2 Spring PRF Construction

```
Spring_k(x):
  1. Expand x to ring element: s = H(x)
  2. Compute: v = A·k·s mod q
  3. Round: y = ⌊v·p/q⌋ mod p
  4. Output: H'(y)
```

### 4.3 Error Budget

For LWR with parameters (n, q, p):
- Rounding error: ≤ q/(2p)
- LWE error contribution: ≤ n·β²
- Security requires: n·β² < q/(2p)

With n=256, q=65537, p=256, β=3:
- Error bound: 256·9 = 2304
- Rounding threshold: 65537/512 ≈ 128

**Problem**: 2304 > 128. Need larger q or smaller p.

With q=65537, p=16:
- Rounding threshold: 65537/32 ≈ 2048
- Still marginal. Need careful parameter selection.

---

## 5. Our Implementation: LEAP-Style VOLE OPRF

### 5.1 Simplified VOLE for Ring-LWE

We implement a simplified VOLE using Ring-LWE:

```rust
struct VoleCorrelation {
    delta: RingElement,      // Server's key contribution
    b: RingElement,          // Server's randomness
    a: RingElement,          // Client's input (derived from password)
    c: RingElement,          // Client's output: c = a·Δ + b
}
```

### 5.2 The Protocol

```
Round 1 (Client → Server): Commitment
  - Client computes: com = H(r) where r is fresh randomness
  - Client sends: com
  
Round 2 (Server → Client): Challenge
  - Server generates: ρ (random challenge)
  - Server sends: ρ
  
Round 3 (Client → Server): Masked Input
  - Client computes: C = A·(s + H(r||ρ)) + e'
  - Client sends: C
  
Round 4 (Server → Client): Evaluation
  - Server computes: V = k·C
  - Server sends: V (no helper needed with LWR)
  
Client Finalization:
  - Client computes: W = (s + H(r||ρ))·B
  - Client rounds: y = ⌊W·p/q⌋
  - Output: H(y)
```

### 5.3 Security Analysis

**Unlinkability**: 
- Server sees `C = A·(s + H(r||ρ)) + e'`
- Cannot compute `C - ?` to get fingerprint because:
  - `r` is committed before `ρ` is known
  - `H(r||ρ)` is unpredictable without knowing `r`
  - Client doesn't send the "unblinding key"

**Determinism**:
- Final output depends only on `k·A·s` (deterministic)
- The `H(r||ρ)` terms cancel in the LWR computation
- Same password → same PRF output

---

## 6. Comparison

| Property | Split-Blinding | OT-Based | **VOLE-LEAP** |
|----------|---------------|----------|---------------|
| Speed | ~0.1ms | ~86ms | **~0.75ms** |
| Rounds | 1 | 256 OT | **2-4** |
| Unlinkability | ❌ Fingerprint | ✅ OT hiding | **✅ VOLE hiding** |
| Error Handling | Reconciliation | Per-bit | **LWR rounding** |
| Communication | ~2KB | ~100KB | **~4KB** |

---

## 7. Open Questions

1. **Parameter Selection**: Exact (n, q, p, β) for 128-bit security with LWR
2. **VOLE Efficiency**: Optimal silent VOLE instantiation for Ring-LWE
3. **Constant-Time**: Ensuring all operations are timing-safe
4. **Threshold**: Extending to t-of-n threshold OPRF

---

## References

1. Heimberger et al., "LEAP: A Fast, Lattice-based OPRF", Eurocrypt 2025
2. Banerjee et al., "Spring PRF from Rounded Ring Products", 2024
3. Shan et al., "Ring-LPR OPRF", 2025
4. Boyle et al., "Efficient Pseudorandom Correlation Generators", Crypto 2019