---
title: NIZKP, PVPKE, PVSS, NIDKG, NITSS
description: In-depth look at proof systems for Schnorr-based threshold signature
theme: gaia
size: 16:9
_class: lead
class: invert
paginate: true
backgroundColor: #000000
marp: true
math: katex
header: IOTA Foundation
---


# NIZKP, PVPKE, PVSS, NIDKG, NITSS #

2021-12-14

---

## Agenda: Part #1 ##

### Recap ###

- [Provable security: ROM, Canetti-Krawczyk](#4)
- [Network: sync vs async, consensus, broadcast](#5)
- [Commitment: Pedersen, ElGamal](#6)
- [ZKP: Goldwasser/Goldreich Micali ... Lindell](#14)
- [Preimage proofs: Schnorr & Maurer, Fiat & Shamir](#23)
- [Bulletproofs: Bunz & Bootle & Boneh, IPA, range proofs](#29)
- [PVPKE: Lifted & Twisted ElGamal](#46)

---

## Agenda: Part #2 ##

### Main construction ###

- [Rationale](#59)
- [PVSS: Shamir & Feldman & proofs, Groth](#67)
- [NIDKG: Groth](#82)
- [NITSS: Schnorr](#92)
- [Future work](#100)
- [Final notes](#101)

---

## TODO: Provable security ##

### ROM ###

### AGM ###

### Forking lemma ###

### Canetti-Krawczyk ###

### Theorem proof tricks ###

---

## TODO: Network ##

- async vs partially sync vs sync
- broadcast, consensus
- BFT

---

## Commitment ##

- [Notation](#7)
- [Use cases](#8)
- [Properties](#10)
- [Examples](#12)

---

### Commitment: Notation ###

$$Commitment = commit(Message,Randomization)$$

$C$ *binds* to $M$ and *hides* it

$M$ can be:

- *target* message (amount of tokens, age), or
- *helper* message (randomization, one-time key)

---

### Commitment: Use cases 1/ ###

$$C = commit(M,R)$$

#### Public knowledge ####

1. use $C$
2. **reveal** $M$, $R$
3. verify $C$, $M$, $R$

---

### Commitment: Use cases 2/2 ###

$$C = commit(M,R)$$

#### Zero knowledge ####

1. use $C$
2. $\pi$ = **prove** $C$, $M$, $R$
3. verify $C$, $\pi$

---

### Commitment: Properties 1/ ###

$$C = commit(M,R)$$

#### Binding ####

Prover can't forge $M'$, ie. $commit$ is collision resistant:

- **perfect**: $commit$ is *bijection* (for each $C$ there's unique $M$)
- **computational**: it's computationally *hard* to find collision
$commit(M',R') = commit(M,R)$

---

### Commitment: Properties 2/2 ###

$$C = commit(M,R)$$

#### Hiding ####

Verifier can't know $M$, ie. $commit$ is one-way:

- **perfect**: it's *impossible* to invert $commit$ (multiple preimages)
- **computational**: it's computationally *hard* to invert
$M = commit^{-1}(C)$

---

### Commitment: Examples 1/ ###

#### Pedersen ####

Setup: $\{(G, H \in \mathbb{G}; d \in \mathbb{Z}): H = d G\}$~-- CRS, $d$ is unknown

$$\texttt{Pedersen}_{G,H}(x,r) = x G + r H$$

- **computationally** binding:
$x' G + r' H = x G + r H$ => $H = (x - x')/(r' - r) G$
- **perfectly** hiding: $\forall C,x \exists! r: r H = C - x G$

---

### Commitment: Examples 2/2 ###

#### ElGamal ####

Setup: $\{(G, H \in \mathbb{G}; d \in \mathbb{Z}): H = d G\}$~-- CRS, $d$ is unknown

$$\texttt{ElGamal}_{G,H}(x,r) = x G + r H, r G$$

- **perfectly** binding: $\forall C=(A,B) \exists! x: x G = A - \texttt{DL}_G(B) H$
- **computationally** hiding: to get a unique $x$ from $A$ we need to get a unique $r H$ from $B = r G$, hence either $\texttt{DL}_G(H)$ or $\texttt{DL}_G(B)$ is known

---

## ZKP ##

- [Notation](#15)
- [Properties](#16)
- [Proofs vs Arguments](#20)
- [Interactive vs Non-interactive](#22)

---

## ZKP: Notation ##

$$\texttt{ZKP}\{(Instance; Witness): Statement\}$$

Proof of knowledge:

- $Setup$: CRS, public parameters
- $Witness$: hidden value
- $Instance$: public value, commitment to $Witness$
- $Statement$: relation between $Witness$ and $Instance$, property of $Witness$
- $Proof$: proof of $Statement$ about $Witness$ and $Instance$

---

### ZKP: Properties 1/ ###

#### Correctness ####

$$\texttt{Yes} = \texttt{HV}.Verify(I, \texttt{HP}.Prove(I,W))$$

*$\texttt{HP}$ -- honest prover
*$\texttt{HV}$ -- honest verifier

---

### ZKP: Properties 2/ ###

#### Soundness (UF) ####

$$\texttt{Yes} = \texttt{HV}.Verify(I, P.Prove(I))\implies P\; knows\; W,$$

ie. use $P$ to *extract witness* $W$ or to solve hard problem.

- **computational**: adversary $P$ is computationally bounded
- **perfect**: $P$ is *unbounded* (solves hard problem) but still *knows* $W$:
$\nexists W': \texttt{Yes} = \texttt{HV}.Verify(I, P.Prove(I,W'))$

---

### ZKP: Properties 3/ ###

#### Zero-knowledge 1/ ####

$$\texttt{Yes} = V.Verify(I, \texttt{HP}.Prove(I, W)) \implies V\; doesn't\;know\; W,$$

ie. there's *simulator* generating *valid* transcripts.
Compare simulated and honest transcript distributions, ZK is:

- **computational**: transcripts are *computationally indistinguishable*
- **statistical**: transcripts are *statistically close*
- **perfect**: transcripts *match*

---

### ZKP: Properties 4/4 ###

#### Zero-knowledge 2/2 ####

$$\texttt{Yes} = V.Verify(I, \texttt{HP}.Prove(I, W)) \implies $$
$$malicious\; V\; doesn't\;know\; W$$

ZK is hard to prove for *any* verifier as simulator doesn't know distribution of verifier's challenges. Hence

- **special honest-verifier** ZK: ZK with *semi-honest* adversary $V$

---

### ZKP: Proofs vs Arguments 1/ ###

| | Proof | Argument |
|:---------------------|:--------------|:--------------|
| soundness | perfect | computational |
| commitment binding | perfect | computational |
| commitment (example) | ElGamal | Pedersen |
| adversary (forger) | unbounded | comp. bounded |
| quantum-proof | yes | no |
| ZK (roughly) | computational | perfect |

---

### ZKP: Proofs vs Arguments 2/2 ###

1. Adversary commits to amount A of tokens,
2. solves for amount A' with the same commitment in 10 years with quantum computer,
3. forges argument of knowledge and claims A' instead of A tokens.

| Property | Forgery affects | Severity |
|:------------------------|:---------------------|:-------------------|
| Perfect soundness | one party | :fire: |
| Zero-knowledge | one or many parties | :fire::fire: |
| Computational soundness | whole system | :fire::fire::fire: |

---

### ZKP: Interactive vs Non-interactive ###

Prover and Verifier run *interactive protocol* to construct a proof.
The proof can only convince this *one* Verifier.

- Protocol is *public coin* if Verifier's challenges are random and independent.
- Public coin can be converted to *non-interactive* proof system via *Fiat-Shamir transform* -- choose challenges pseudo-randomly based on current transcript.
- Non-interactive proof can be verified by *anyone*.

IZKP with SHVZK property can be converted to NIZKP with ZK property in ROM.

---

## Preimage NIZKP ##

- [Notation](#24)
- [Schnorr's identity protocol](#25)
- [Maurer's generalized proof](#26)
- [Schnorr's signature scheme](#27)
- [Aggregation](#28)

---

## Preimage NIZKP: Notation ##

$$\texttt{Preimage}\{(X \in \mathbb{G}; x \in \mathbb{F}): X = [x]\}$$

- $Setup$:
$\mathbb{F}$, $\mathbb{G}$ -- groups,
$[.]: \mathbb{F} \to \mathbb{G}$ -- *one-way* homomorphism: $[x+y] = [x]+[y]$
- $Witness$: $x \in \mathbb{F}$
- $Instance$: $X \in \mathbb{G}$
- $Statement$: Prover knows $x$ such that $X = [x]$

---

### Preimage: Schnorr's identity protocol ###

$$\texttt{SchnorrId}\{(PK \in EC(\mathbb{F}_p); sk \in \mathbb{Z}_q): PK = sk\; G\}$$

Interactive $\Sigma$-protocol (public coin):

| $P(PK,sk)$ computes | $P$ <=> $V$ | $V(PK)$ computes |
|:--------------------|:-----------:|:-----------------|
| $r \overset{\$}{\gets} \mathbb{Z}_q, R = r\; G$ | commitment $R$ | |
| | challenge $c$ | $c \overset{\$}{\gets} \mathbb{Z}_q$ |
| $s = r + c\cdot sk$ | response $s$ | $s\; G \overset{?}{=} R + c\cdot PK$ |

---

### Preimage: Maurer's generalized proof ###

$$\texttt{Preimage}\{(X \in \mathbb{G}; x \in \mathbb{F}): X = [x]\}$$

Interactive $\Sigma$-protocol (public coin):

| $P(X,x)$ computes | $P$ <=> $V$ | $V(X)$ computes |
|:------------------|:-----------:|:----------------|
| $r \overset{\$}{\gets} \mathbb{F}, R = [r]$ | commitment $R$ | |
| | challenge $c$ | $c \overset{\$}{\gets} \mathbb{Z}$ |
| $s = r + c\cdot x$ | response $s$ | $[s] \overset{?}{=} R + c \cdot X$ |

---

### Preimage: Schnorr's signature scheme ###

$$\texttt{Signature}\{(X \in \mathbb{F}; m \in 2^*, x \in \mathbb{G}): X = [x], m\}$$

$\Sigma$-protocol is public coin. Use Fiat-Shamir to construct NIZKP.

| Prove | | Verify |
|:--------------------------|---|:-----------------------|
| $r \overset{\$}{\gets} \mathbb{F}$, $R = [r]$ || $(s, R, m) = Proof$ |
| $c = h(X, R, m)$ | | $c = h(X, R, m)$ |
| $s = r + c x$ | | $S = R + c X$ |
| $\texttt{Proof} = (s, R, m)$ | | $[s] \overset{?}{=} S$ |

---

### Preimage: Aggregation ###

$$\texttt{Preimage}\{(X \in \mathbb{G}^n; x \in \mathbb{F}^n): \wedge_{i=1}^n X_i = [x_i]\}$$

1. $r \overset{\$}{\gets} \mathbb{F}$, $R = [r]$
2. $s(z) = r + \sum_{i=1}^n z^i x_i \in \mathbb{F}[z]$
$[s(z)] = [r] + \sum_{i=1}^n z^i [x_i]\in \mathbb{G}[z]$
$S(z) = R + \sum_{i=1}^n z^i X_i\in \mathbb{G}[z]$
3. $c = h(X, R)$
4. $\texttt{Proof} = (s(c),R) \in \mathbb{F} \times \mathbb{G}$
5. verify $[s(c)] \overset{?}{=} S(c)$

---

## Bulletproofs ##

- [Outline](#30)
- [Inner-Product Argument](#31)
- [Range proof](#35)
- [R1CS](#45)

---

## Bulletproofs: Outline ##

- Argument of knowledge (computational soundness)
- Succinct -- proof size $O(log(n))$
- Slow -- verify time $O(n)$
- Based on Innter-product argument (IPA)

Applications:

- Range proofs
- R1CS

---

### Bulletproofs: Inner-product argument 1/ ###

$$\texttt{IPA}\{(\overline{G},\overline{H},P,c; \overline{a},\overline{b}): P = \langle \overline{a}, \overline{G} \rangle + \langle \overline{b}, \overline{H} \rangle \wedge c = \langle \overline{a}, \overline{b} \rangle \}$$

$\overline{a} \in \mathbb{Z}_q, \overline{x} \in \mathbb{X}: \langle \overline{a}, \overline{x} \rangle = \sum_{i=0}^{n-1} a_i x_i \in \mathbb{X}$ -- inner product

Equivalent form:

$$\texttt{IPA}'\{(\overline{G},\overline{H},P,U; \overline{a},\overline{b}): P = \langle \overline{a}, \overline{G} \rangle + \langle \overline{b}, \overline{H} \rangle + \langle \overline{a}, \overline{b} \rangle U \}$$

Inductive proof.

1. $n=1$: proof is $(a,b) \in \mathbb{F}^2$

---

### Bulletproofs: Inner-product argument 2/ ###

$$\texttt{IPA'}\{(\overline{G},\overline{H},P,U; \overline{a},\overline{b}): P = \langle \overline{a}, \overline{G} \rangle + \langle \overline{b}, \overline{H} \rangle + \langle \overline{a}, \overline{b} \rangle U \}$$

2. $n=2m$: use Laurent polynomials

- $\overline{a}'(x) = x \overline{a}_L + x^{-1} \overline{a}_R,\; \overline{b}'(x) = x^{-1} \overline{b}_L + x \overline{b}_R$
- $\overline{G}'(x) = x^{-1} \overline{G}_L + x \overline{G}_R,\; \overline{H}'(x) = x \overline{H}_L + x^{-1} \overline{H}_R$
- $P'(x) = \langle \overline{a}',\overline{G}' \rangle + \langle \overline{b}',\overline{H}' \rangle + \langle \overline{a}',\overline{b}' \rangle U$
- $L = \langle \overline{a}_L,\overline{G}_R \rangle + \langle \overline{b}_R,\overline{H}_L \rangle + \langle \overline{a}_L,\overline{b}_R \rangle U$
- $R = \langle \overline{a}_R,\overline{G}_L \rangle + \langle \overline{b}_L,\overline{H}_R \rangle + \langle \overline{a}_R,\overline{b}_L \rangle U$

---

### Bulletproofs: Inner-product argument 3/ ###

$$\texttt{IPA'}\{(\overline{G},\overline{H},P,U; \overline{a},\overline{b}): P = \langle \overline{a}, \overline{G} \rangle + \langle \overline{b}, \overline{H} \rangle + \langle \overline{a}, \overline{b} \rangle U \}$$

1. $P'$ satisfies equation: $P'(x) = x^2 L + P + x^{-2} R$
2. Prover sends $L$ and $R$ (as part of proof) to Verifier
3. Verifier choses $x$ (and evaluates $\overline{G}'$, $\overline{H}'$, $P'$)
4. Prover evaluates $\overline{G}'$, $\overline{H}'$, $\overline{a}'$, $\overline{b}'$, $P'$ at $x$
5. Inductive step: Prover proves $\texttt{IPA'}\{(\overline{G}',\overline{H}',P',U; \overline{a}',\overline{b}'): P' = \langle \overline{a}', \overline{G}' \rangle + \langle \overline{b}', \overline{H}' \rangle + \langle \overline{a}', \overline{b}' \rangle U \}$

---

### Bulletproofs: Inner-product argument 4/4 ###

#### IPA Properties ####

- **Succinct** (short): $2 log_2(n)$ group elements
- **Slow**: generation and verification $\approx 6n$ group operations
- **Argument** of knowledge: computational soundness
- **No zero-knowledge**: can extract information

---

### Bulletproofs: Range proof 1/ ###

$$\texttt{RangeProof}\{(G,H,V,n;v,r): V = vG + rH \wedge v\in[0 .. 2^n)\}$$

$v\in[0 .. 2^n) \Leftrightarrow \exists \overline{a}, \overline{b} \in \mathbb{Z}_q^n$:

$$\langle \overline{a}, 2^n \rangle = v,\quad \overline{b} = \overline{a} - 1^n,\quad \overline{a} \circ \overline{b} = 0^n$$

Why not: $\langle \overline{a}, 2^n \rangle = v,\; \overline{a} \circ (\overline{a} - 1^n) = 0^n$:interrobang:

\*$c^n = (c^i)_{i=0}^{n-1} \in \mathbb{Z}_q^n$
\*$\overline{a} \circ \overline{b} = (a_i b_i)_{i=0}^{n-1} \in \mathbb{Z}_q^n$ -- Hadamard product
\*$c \cdot \overline{a} = (c a_i)_{i=0}^{n-1} \in \mathbb{Z}_q^n$ -- dot product $\quad\quad\quad\quad$ See [PVSS](#74)

---

### Bulletproofs: Range proof 2/ ###

$$\texttt{RangeProof}\{(G,H,V,n;v,r): V = vG + rH \wedge v\in[0 .. 2^n)\}$$

$$\langle \overline{a}, 2^n \rangle = v,\; \overline{b} = \overline{a} - 1^n,\; \overline{a} \circ \overline{b} = 0^n \Leftrightarrow$$
$$\langle \overline{a}, 2^n \rangle = v,\; \langle \overline{a} - 1^n - \overline{b}, y^n \rangle = 0,\;
\langle \overline{a}, \overline{b} \circ y^n \rangle = 0 \Leftrightarrow$$
$$z^2 \cdot \langle \overline{a}, 2^n \rangle + z \cdot \langle \overline{a} - 1^n - \overline{b}, y^n \rangle +
\langle \overline{a}, \overline{b} \circ y^n \rangle = z^2 v \Leftrightarrow$$
$$\langle \overline{a} - z \cdot 1^n, y^n \circ (\overline{b} + z \cdot 1^n) + z^2 \cdot 2^n \rangle = z^2 v + \delta(y,z)$$

---

### Bulletproofs: Range proof 3/ ###

$$\langle \overline{a} - z \cdot 1^n, y^n \circ (\overline{b} + z \cdot 1^n) + z^2 \cdot 2^n \rangle = z^2 v + \delta(y,z)$$

Verifier choses $y, z \in \mathbb{Z}_q$. Can't use IPA right now: no ZK. Add blindings $\overline{c}, \overline{d} \in \mathbb{Z}_q^n$!

$l(x) = (\overline{a} - z \cdot 1^n) + \overline{c} x \in \mathbb{Z}_q^n[x]$
$r(x) = y^n \circ (\overline{b} + z \cdot 1^n + \overline{d} x) + z^2 \cdot 2^n \in \mathbb{Z}_q^n[x]$
$t(x) = \langle l(x),r(x) \rangle = x^2 t_2 + x t_1 + t_0 \in \mathbb{Z}_q[x]$
$t_0 = z^2 v + \delta(y,z)$

---

### Bulletproofs: Range proof 4/ ###

$$t(x) = \langle l(x),r(x) \rangle = x^2 t_2 + x t_1 + t_0 \in \mathbb{Z}_q[x]$$

1. Prover commits to $\overline{c}, \overline{d}, t_1, t_2$
2. Verifier choses challenges $y, z, x$
3. Prover uses IPA to prove $t(x) = \langle l(x),r(x) \rangle$
4. Verifier verifies IPA
5. Verifier verifies commitments

$\texttt{RangeProof}$ is public coin hence can be made non-interactive.

---

### Bulletproofs: Range proof 5/ ###

#### Transcript ####

| Randomization | Commitment | Challenge |
|:--------------|:-----------|:----------|
| $\alpha \overset{\$}{\gets} \mathbb{Z}_q$ | $A = \alpha H + \langle \overline{a}, \overline{G} \rangle + \langle \overline{b}, \overline{H} \rangle$ | |
| $\overline{c}, \overline{d} \overset{\$}{\gets} \mathbb{Z}_q^n$, $\rho \overset{\$}{\gets} \mathbb{Z}_q$ | $S = \rho H + \langle \overline{c}, \overline{G} \rangle + \langle \overline{d}, \overline{H} \rangle$ | $y, z \overset{\$}{\gets} \mathbb{Z}_q^*$ |
| $\tau_i \overset{\$}{\gets} \mathbb{Z}_q$, $i=1,2$ | $T_i = t_i G + \tau_i H$, $i=1,2$ | $x \overset{\$}{\gets} \mathbb{Z}_q^*$ |

See [ElGamal commitment in PVSS](#74), [sharing proof in PVSS](#76)

---

### Bulletproofs: Range proof 6/ ###

#### Proof ####

1. $\mu = \alpha + x \rho \in \mathbb{Z}_q$
2. $\overline{l} = l(x), \overline{r} = r(x) \in \mathbb{Z}_q^n$
3. $\hat t = t(x) = \langle \overline{l}, \overline{r} \rangle \in \mathbb{Z}_q$
4. $\tau_x = x^2 \tau_2 + x \tau_1 + z^2 r \in \mathbb{Z}_q$ -- $r$ here is from witness

---

### Bulletproofs: Range proof 7/ ###

#### Verify ####

1. $\overline{H}' = \langle y^{-n}, \overline{H} \rangle$, $P = A + x S - z G + (z^2 \cdot 2^n + z \cdot y^n) \overline{H}'$
2. $P \overset{?}{=} \mu H + \langle \overline{l}, \overline{G} \rangle + \langle \overline{r}, \overline{H} \rangle$ -- $\overline{l}$, $\overline{r}$, correct?
3. $\hat t G + \tau_x H \overset{?}{=} z^2 V + x^2 T_2 + x T_1 + \delta(y,z) G$ -- $\hat t \overset{?}{=} t(x)$?
4. $\hat t \overset{?}{=} \langle \overline{l}, \overline{r} \rangle$ -- $\hat t$ correct? via IPA

See [ElGamal commitment in PVSS](#74), [sharing proof in PVSS](#76)

---

### Bulletproofs: Range proof 8/ ###

#### Aggregation 1/ ####

$$\texttt{RangeProof}\{(G,H,V_j,n;v_j,r_j): V_j = v_jG + r_jH \wedge v_j\in[0 .. 2^n)\}$$

1. Use longer vectors: $\overline{a}, \overline{b} \in \mathbb{Z}_q^{n \textcolor{red}{m}}$
2. Adjust polynomial: $r(x) = y^n \circ (\overline{b} + z \cdot 1^n + \overline{d} x) + \textcolor{red}{\sum_{j=1}^m z^{j+1} \cdot (0^{(j-1)n} \| 2^n \| 0^{(m-j)n})} \in \mathbb{Z}_q^{nm}[x]$
3. Aggregate randomness: $\tau_x = x^2 \tau_2 + x \tau_1 + \textcolor{red}{\sum_{j=1}^m z^{1+j} r_j} \in \mathbb{Z}_q$

---

### Bulletproofs: Range proof 9/ ###

#### Aggregation 2/2 ####

4. Update: $\color{red} \delta(y,z)$,
5. Update commitment: $P = A + x S - z G + (z \cdot y^{n\textcolor{red}{m}}) \overline{H}' + \textcolor{red}{\sum_{j=1}^m (z^{j+1} \cdot (0^{(j-1)n} \| 2^n \| 0^{(m-j)n}))} \overline{H}'$
6. Verify: $\hat t G + \tau_x H \overset{?}{=} z^2 \textcolor{red}{\langle z^m, \overline{V} \rangle} + x^2 T_2 + x T_1 + \textcolor{red}{\delta(y,z)} G$

[Aggregation in PVSS](#77)

---

### Bulletproofs: Range proof 10/10 ###

#### Batch verification ####

1. Combine equations $O \overset{?}{=} P_i$, $i=1..n$ into one: $O \overset{?}{=} \sum z^i P_i$
2. Verifier choses $z = h(\|_i P_i)$
3. Use multiscalar multiplication

[Batch verification in PVSS](#78)

---

### Bulletproofs: R1CS ###

---

## PVPKE ##

- [Lifted ElGamal](#47)
- [Decryptability and Chunking proofs](#49)
- [Lifted ElGamal issues](#51)
- [Lifted Twisted ElGamal](#54)
- [DL-bruteforce](#55)

---

### PVPKE: Lifted ElGamal 1/ ###

Let $\overline{X} = \overline{x} G$ be Receivers' public keys, then:

$$\overline{C}, R = \texttt{Enc}_{\overline{X}}(\overline{s},r) = \overline{s} \cdot H + r \cdot \overline{X}, r G$$
$$s_j = Dec_{x_j}(C_j,R) = \texttt{DL}_H(C_j - x_j R)$$

Only works for small $s_j \in [0..2^b)$.

Aggregate decryption: $\sum_i s_j^{(i)} = Dec_{x_j}(\sum_i C_j^{(i)},R^{(i)})$?

---

### PVPKE: Lifted ElGamal 2/2 ###

#### Chunking ####

Let's split $s_j = \sum_{l=0}^{m-1} 2^{bl} s_{j,l}$ into chunks $s_{j,l} \in [0..2^b)$.

$$\overline{C}_l, R_l = \texttt{Enc}_{\overline{X}}(\overline{s}_l,r_l) = \overline{s}_l \cdot H + r_l \cdot \overline{X}, r_l G$$
$$s_{j,l} = Dec_{x_j}(C_{j,l},R_l) = \texttt{DL}_H(C_{j,l} - x_j R_l)$$

- $b=16$: $m=16$ chunks
- $b=32$: $m=8$ chunks
- $b=64$: impractical

---

### PVPKE: Lifted ElGamal proofs 1/ ###

#### Decryptability proof ####

Proof that Receiver **can decrypt** $s H = C - x R$:

$$\texttt{Decryptability}\{(C,R; s,r): C, R = \texttt{Enc}_X(s,r)\}$$

- use $\texttt{Preimage}$ proof with $\texttt{Enc}_X(s,r)$ as one-way map
- *formally* means that Dealer knows $s, r$
- *semantically* means Receiver's public key $X$ was used to encrypt
- aggregate final proof to account for $n$ Receivers and $m$ chunks

---

### PVPKE: Lifted ElGamal proofs 2/2 ###

#### Chunking proof ####

Proof that Receiver **can bruteforce** DLog: $s = \texttt{DL}_H(s H)$:

$$\texttt{Chunking}\{(C; s,r): C = s H + r X \wedge s \in [0..2^b)\}$$

- use $\texttt{RangeProof}$ proof with $C$ as Pedersen commitment
- formally *also* proves knowledge of $s, r$
- is it safe to use public key $X$ and $H$ as CRS in Pedersen commitment? (if not, use lifted *twisted* ElGamal instead)

---

### PVPKE: Lifted ElGamal issues 1/ ###

#### Issue #1: Proof duplication ####

Problem: $\texttt{Decryptability}$ and $\texttt{Chunking}$ duplicate proof of knowledge of $s$ and $r$.

Source: One uses ElGamal commitment, the other uses Pedersen.

Solution: Extend $\texttt{RangeProof}$ to accept ElGamal commitments.

---

### PVPKE: Lifted ElGamal issues 2/ ###

#### Issue #2: Heterogenous range proof aggregation ####

Problem: $\texttt{RangeProof}$ implementation can't aggregate range proofs with the different CRS' in Pedersen commitments.

Source: ElGamal uses Receiver's public key as second base point.

Solution #1: Switch to twisted ElGamal.

Solution #2: Extend aggregation to heterogenous Pedersen commitments.

---

### PVPKE: Lifted ElGamal issues 3/3 ###

#### Issue #3: Public key in CRS ####

Problem: Public key does not strictly conform requirements to CRS, might cause troubles in security proofs.

Source: ElGamal uses Receiver's public key as second base point.

Solution #1: Switch to twisted ElGamal.

Solution #2: Research and revisit security proofs. Avoid rogue keys with additional checks during Setup. Use $H$ point for scalars while public keys are base $G$ point.

---

### PVPKE: Lifted Twisted ElGamal ###

Let $\overline{X} = \overline{x} G$ be Receivers' public keys, then:

$$\overline{C}, \overline{R} = \texttt{Enc}_{\overline{X}}(\overline{s},\overline{r}) = \overline{s} \cdot H + \overline{r} \cdot G, \overline{r} \circ \overline{X}$$
$$s_j = Dec_{x_j}(C_j,R_j) = \texttt{DL}_H(C_j - x_j^{-1} R_j)$$

- :white_check_mark: $\texttt{RangeProof}$ aggregation-friendly
- :white_check_mark: Pedersen commitment-friendly, no CRS questions
- :x: can't reuse randomizations, roughly double cipher text size

---

### PVPKE: DL-bruteforce 1/ ###

| Algorithm | Memory | Runtime |
|:------------------------------|:-------------|:-------------|
| Baby-step giant-step | $O(\sqrt n)$ | $O(\sqrt n)$ |
| Pollard's rho/lambda/kangaroo | $O(1)$ | $O(\sqrt n)$ |
| **Precomp table\*\*** | $O(n^*)$ | $O(1)$ |

\*$n = 2^b$, where $b$ is chunk size in bits
\*\*$b=16$, impractical with $b=32$

---

### PVPKE: DL-bruteforce 2/ ###

#### Precomputation ####

1. $\texttt{DL}_k[i_k] = \empty$ for $k=1,2$, $i_k \in [0..2^w)$
2. for $x \in [0..2^b)$ for $k=1,2$:
3. $\;\;X = x G \in EC(\mathbb{F}_p)$
4. $\;\;i_k = hash_k(X) \in [0..2^w)$
5. $\;\;\texttt{DL}_k[i_k] = \texttt{DL}_k[i_k] \cup x$

\*$hash_k$ extracts $w$ bits from $X$ encoding

---

### PVPKE: DL-bruteforce 3/ ###

#### Algorithm ####

Input: $X \in EC(\mathbb{F}_p)$
Output: $x \in [0..2^b)$ or $\bot$
Steps:

1. $i_k = hash_k(X) \in [0..2^w)$ for $k=1,2$
2. $dlogs = \cap_{k=1}^2 \texttt{DL}_k[i_k]$
3. if $|dlogs| \neq 1$, return $\bot$, else $\{x\} = dlogs$
4. if $x G = X$, return $x$, else return $\bot$

---

### PVPKE: DL-bruteforce 4/4 ###

#### Analysis ####

- $w$ must be chosen so that there's a unique value in $\cap_{k=1}^2 \texttt{DL}_k[i_k]$
- For $X$, $\texttt{DL}_G(X) \in [0..2^b)$ algorithm returns correct value.
- For $X$, $\texttt{DL}_G(X) \notin [0..2^b)$ algorithm returns $\bot$.

#### Complexity ####

Memory: $2*b*2^w*max_{i_k}|\texttt{DL}_k[i_k]|$ bits
For $b=16$, $w=16$, $max_{i_k} |\texttt{DL}_k[i_k]| = 8$, memory 2Mb.

---

## Rationale ##

- [Platform](#60)
- [Interactivity](#61)
- [Networking](#62)
- [Encryption](#63)
- [Proofs](#64)
- [DKG](#65)
- [TSS](#66)

---

## Rationale: Platform ##

| Pairings / BLS | DL / Schnorr |
|:------------------|:----------------|
| more powerful | powerful enough |
| slow | reasonably fast |
| no Layer 1 compat | Layer 1 compat |

---

## Rationale: Interactivity ##

| Interactive | Non-Interactive |
|:-------------------|:-------------------|
| less computation | more computation |
| more networking | less networking |
| complex adversary | broadcast |

---

## Rationale: Networking ##

Consensus, broadcast, async
AVSS, ADKG

---

## Rationale: Encryption ##

| Lifted ElGamal | Twisted ElGamal | Symmetric / Other |
|:----------------------|:--------------------|:----------------------|
| Preimage/Bulletproofs | longer ciphertexts | complex/slow proofs |

---

## Rationale: Proofs ##

Bulletproofs, Preimage

---

## Rationale: DKG ##

NIDKG vs ADKG

---

## Rationale: TSS ##

Robust vs non-robust
random vs deterministic
precomp, FROST, Stinson-Strobl

---

## PVSS ##

- [Shamir's secret sharing with Feldman's verification](#68)
- [Non-interactive](#70)
- [Publicly verifiable](#71)
- [Succinct proofs: aggregation & fusion](#73)
- [Construction](#79)

---

### PVSS: Shamir's secret sharing 1/ ###

| Computation | Description |
|:-------------------------------------|:---------------------------|
| $f(x) = \sum_{k=0}^{t-1} x^k f_k$ | Dealer's random polynomial |
| $s = f_0 = f(0)$ | Dealer's secret |
| $F_k = f_k H$ | commitment to $f(x)$ |
| $F_0$ | Dealer's public key |
| $F(x) = \sum_{k=0}^{t-1} x^k F_k$ | commitment polynomial |

---

### PVSS: Shamir's secret sharing 2/2 ###

| Computation | Description |
|:-------------------------------------|:---------------------------|
| $s_j = f(j)$ | $j$-th share |
| $s_j H \overset{?}{=} F(j)$ | Feldman's verification |
| $l_j^J(x) = \prod_{i\in J,i\neq j} \frac{x - i}{i - j}$ | Lagrange polynomial |
| $\hat f(x) = \sum_{j\in J} l_j^J(x) s_j$ | polynomial interpolation |
| $\hat s = \hat f(0)$ | secret recovery |

---

### PVSS: Non-interactive ###

Just encrypt $s_j$ share with $j$-th Receiver's public key $X_j$:

$$C_{j,l},R_l = s_{j,l} H + r_l X_j, r_l G$$

Attach [decryptability](#49) and [chunking](#50) proofs:

$$\texttt{Decryptability}\{(C_{j,l},R_l,X_j; s_{j,l},r_l): C_{j,l}, R_l = \texttt{Enc}_{X_j}(s_{j,l},r_l)\}$$
$$\texttt{Chunking}\{(C_{j,l},X_j; s_{j,l},r_l): C_{j,l} = s_{j,l} H + r_l X_j \wedge s_{j,l} \in [0..2^b)\}$$

---

### PVSS: Publicly verifiable 1/ ###

Proof that encrypted share is correct, ie. $s_j H = F(j)$:

$$\texttt{Sharing}\{(F_k,C_{j,l},R_l,X_j; r_l): \\
\sum_l 2^{bl} C_{j,l} - F(j) = \sum_l 2^{bl} r_l X_j \wedge R_l = r_l G\}$$

- $\texttt{Preimage}$ PoK with $g_{X_j}(r_l) = (\sum_l 2^{bl} r_l X_j, r_l G)$ as OW map
- *formally* means knowledge of $r$ and equality of discrete logs
- *semantically* means image of encrypted value is $F(j)$
- :interrobang: $r = \sum_l 2^{bl} r_l$, but we already have PoK of $r_l$ :interrobang:

---

### PVSS: Publicly verifiable 2/2 ###

#### Jens Groth's approach ####

$$\texttt{Sharing'}\{(F_k,C_{j,l},R_l,X_j; s_j, r): \\
\sum_l 2^{bl} C_{j,l} = s_j H + r X_j \wedge F(j) = s_j H \wedge \sum_l 2^{bl} R_l = r G\}$$

- $\texttt{Preimage}$ PoK with $g_{X_j}(s_j, r) = (s_j H + r X_j, s_j H, r G)$ as one-way map
- *formally* means knowledge of $s_j$ and $r$
- :exclamation: don't need knowledge of $s_j$ here, only that $s_j H = F(j)$ :exclamation:

---

### PVSS: Succinct proofs 1/ ###

Idea: aggregate & fuse $\texttt{Decryptability}$, $\texttt{Chunking}$ and $\texttt{Sharing}$ proofs into one:

$$\texttt{PVSS}\{(F_k,C_{j,l},R_l,X_j; s_{j,l},r_l):
\\ C_{j,l}, R_l = \texttt{Enc}_{X_j}(s_{j,l},r_l) \wedge
\\ s_{j,l} \in [0..2^b) \wedge
\\ \sum_l 2^{bl} C_{j,l} - F(j) = \sum_l 2^{bl} r_l X_j \}$$

\*$\texttt{Enc}_{X_j}(s,r) = \texttt{ElGamal.commit}(s,r)$

---

### PVSS: Succinct proofs 2/ ###

#### ElGamal commitment in range proof ####

1. Add ElGamal commitment to [instance and statement](#35):
$\texttt{RP}\{(V,\textcolor{red}{R},n;v,r): V = vG + rH \wedge \textcolor{red}{R = rG} \wedge v\in[0 .. 2^n)\}$
2. Use ElGamal to [commit to $\tau_i$](#39):
$T_i = t_i G + \tau_i H$, $\color{red} P_i = \tau_i G$, $i=1,2$
3. Add verification [equation](#41):
$\textcolor{green}{\tau_x} = x^2 \tau_2 + x \tau_1 + z^2 \textcolor{green}{r} \in \mathbb{Z}_q$
$\hat t G + \textcolor{green}{\tau_x} H \overset{?}{=} z^2 \textcolor{green}{V} + \ldots$, $\color{red} \tau_x G \overset{?}{=} x^2 P_2 + x P_1 + z^2 R$

---

### PVSS: Succinct proofs 3/ ###

#### Fused preimage & range proofs 1/ ####

Recall [$\texttt{Sharing}$ proof](#71) with one-way map:
$g_H: \mathbb{Z}_q^m \to \mathbb{G} \times \mathbb{G}^m, g_H(r_l) = (\sum_l 2^{bl} r_l H, r_l G)$

1. $\tau_l \overset{\$}{\gets} \mathbb{Z}_q^m$, $(S_j,P_{j,l}) = g_{X_j}(\tau_l)$,
2. $z_l = h(S_j,P_{j,l},C_{j,l},R_l)$, 3. $\tau_{x,l} = \tau_l + z_l r_l$

$\sum_l 2^{bl} \tau_{x,l} X_j \overset{?}{=} S_j + z_l (\sum_l 2^{bl} C_{j,l} - F(j))$
$\tau_{x,l} G \overset{?}{=} P_{j,l} + z_l R_l$

---

### PVSS: Succinct proofs 4/ ###

#### Fused preimage & range proofs 2/2 ####

1. Add correct sharing condition to [statement](#74):
$\texttt{RP}\{(\textcolor{red}{F_k,X_j,C_{j,l}},R_l,n;v_l,r_l): \textcolor{red}{C_{j,l}} = v_l G + r_l \textcolor{red}{X_j} \wedge U_l = r_l G \wedge \textcolor{red}{\sum_l 2^{bl} (C_{j,l} - r_l X_j) = F(j)} \wedge v_l\in[0 .. 2^n)\}$
2. [Commit](#39) to $\sum_l 2^{bl} \tau_{i,l}$:
$\color{red} S_{i,j} = \sum_l 2^{bl} \tau_{i,l} X_j$, $i=1,2$
3. Add verification [equation](#41):
$\textcolor{green}{\tau_{x,l}} = x^2 \tau_{2,l} + x \tau_{1,l} + z^2 \textcolor{green}{r_l} \in \mathbb{Z}_q$
$\color{red} \sum_l 2^{bl} \tau_{x,l} X_j \overset{?}{=} x^2 S_{2,j} + x S_{1,j} + z^2 (\sum_l 2^{bl} C_{j,l} - F(j))$

---

### PVSS: Succinct proofs 5/ ###

#### Heterogenous fused range proof aggregation ####

See [Bulletproofs](#42)

:x: Can't use heterogenous ElGamal commitments in [aggregated range proofs](#43):
$\textcolor{red}{\tau_x} = x^2 \tau_2 + x \tau_1 + \textcolor{red}{\sum_{j=1}^m z^{1+j} r_j} \in \mathbb{Z}_q$
$\textcolor{red}{T_{i,j}} = t_i G + \tau_i \textcolor{red}{X_j}$, $i=1,2$
$\hat t G + \textcolor{red}{\tau_x X_j}? \overset{?}{=} z^2 \langle z^m, \textcolor{red}{\overline{V}} \rangle + x^2 \textcolor{red}{T_2} + x \textcolor{red}{T_1} + \delta(y,z) G$

Use [twisted ElGamal](#54)

---

### PVSS: Succinct proofs 6/6 ###

#### Heterogenous fused range proof batch verification ####

See [Bulletproofs](#44), use same technique.

---

### PVSS: Construction 1/ ###

#### Share 1/ ####

| Computation | Description |
|:------------------------------------------|:----------------------------|
| 1. $f_k \overset{\$}{\gets} \mathbb{Z}_q$ | generate random polynomial |
| 2. $F_k = f_k H$ | commitments to $f_k$ |
| 3. $s_j = f(j)$ | $j$-th share |
| 4. $s_j = \sum_l 2^{bl} s_{j,l}$ | split share into chunks |

---

### PVSS: Construction 2/ ###

#### Share 2/2 ####

| Computation | Description |
|:------------------------------------------|:----------------------------|
| 5. $r_l \overset{\$}{\gets} \mathbb{Z}_q$ | generate randomizations |
| 6. $R_l = r_l G$ | ephemeral public keys |
| 7. $C_{j,l} = s_{j,l} H + r_l X_j$ | encrypt chunks |
| 8. $\pi = \texttt{PVSS}.Prove()$ | generate aggregated proof |
| 9. return $F_k,R_l,C_{j,l},\pi$ | sign & publish everything |

---

### PVSS: Construction 3/3 ###

#### Recover ####

| Computation | Description |
|:------------------------------------------|:----------------------------|
| 1. input $j$ | receiver's index |
| 2. parse $F_k,R_l,C_{j,l},\pi$ | receive everything |
| 3. $\texttt{PVSS}.Verify(\pi)$ | verify signature and proofs |
| 4. $s_{j,l} = \texttt{DL}_H(C_{j,l} - x_j R_l)$ | decrypt chunks |
| 5. return $s_j = \sum_l 2^{bl} s_{j,l}$ | recover secret share |

---

## NIDKG ##

- [Setup](#83)
- [Round #1](#84)
- [Round #2](#85)
- [Notes](#87)
- [Security](#88)

---

### NIDKG: Setup ###

- $n$ -- number of parties
- $t$ -- threshold number
- $i \in \{1..n\}$ -- party's index
- $Q_j$ for $j=1..n$ -- parties' public keys

---

### NIDKG: Round #1 ###

| Computation | Description |
|:------------------------------------------|:----------------------------|
| 1. $M_i \gets \texttt{PVSS}.Share()$ | run PVSS.Share as Dealer |
| 2. broadcast $M_i$ | send |

---

### NIDKG: Round #2 1/ ###

| Computation | Description |
|:-----------------------------------------------------|:-----------------------------|
| 1. receive $M^{(j)}$ for $j=1..n$, $j \neq i$ | receive Dealers' messages |
| 2. $s^{(j)} \gets \texttt{PVSS}.Recover(i, M^{(j)})$ | recover as Receiver $i$ |
| 3. $J = \{j: s^{(j)} \neq \bot\}$ | valid* contributors |
| 4. $F_k = \sum_{j \in J} M^{(j)}.F_k$, for $k$ | combined commitments |

\*all parties $P_i$ must agree on the set $J$ and commitments $M^{(j)}.F_0$

---

### NIDKG: Round #2 2/2 ###

| Computation | Description |
|:---------------------------------------------|:-----------------------------|
| 5. $s_i = \sum_{j \in J} s^{(j)}$ | combined secret share |
| 6. $T_j = \sum_k j^k F_k$ for $j=1..n$ | combined partial public keys |
| 7. $T = F_0$ | combined public key |
| 8. $s_i H \overset{?}{=} T_i$ | must not fail |
| 9. return $s_i$, $T$, $T_j$ for $j=1..n$ | share, PK, partial PKs |

---

### NIDKG: Notes ###

1. parties **must agree** on $V = \{(j,F_j): j \in J, F_j = M^{(j)}.F_0\}$
- either have weak broadcast and run consensus for $V$
- or run reliable broadcast to guarantee agreement on $V$
2. attach sid / timestamp to avoid session hijack

---

### NIDKG: Security 1/ ###

#### Adversary ####

- acts as malicious and semi-honest party
- can corrupt up to $t-1$ parties
- can block up to $n-t$ parties
- can run multiple sessions

---

### NIDKG: Security 2/ ###

#### Properties ####

1. soundness:
adversary can't skew distribution of secret / shares
2. computational ZK:
adversary can't have knowledge of secret / shares
3. robustness -- depends on agreement / broadcast protocol:
adversary can't stall / DoS protocol

---

### NIDKG: Security 3/ ###

#### Adversary's Game ####

TODO: ROM, eCK model, games

Game #1:

- (t-1)A vs 1P: A wants to forge
- A can't know, can't skew

Game #2:

- (min(n-t,t-1))A vs tP: A wants to DoS
- A can't DoS, can't skew, can't know

---

### NIDKG: Security 4/4 ###

#### Adversary's Advantage ####

TODO: Theorem, rewind, forking lemma, universal composability

---

## NITSS ##

- [Setup](#93)
- [KeyGen](#94)
- [Sign](#95)
- [Issues](#98)
- [Security](#99)

---

### NITSS: Setup ###

NIDKG.Setup:

- $n$ -- number of parties
- $t$ -- threshold number
- $i \in \{1..n\}$ -- party's index
- $Q_j$ for $j=1..n$ -- parties' public keys

---

### NITSS: KeyGen Rounds #1 & #2 ###

| Computation | Description |
|:---------------------------------------------|:-----------------------------|
| 1. $s_i, T, T_j \gets \texttt{NIDKG}()$ | run NIDKG protocol |
| 2. $sid = h(T_j)$ | session id |
| 3. store $s_i$, $T_j$, $sid$ | store secret / session info |
| 4. publish $T$ | announce public key |

---

### NITSS: Sign 1/ ###

#### Input ####

- $M$ -- TBS message
- $s_i$, $T$, $sid$, $T_j$ -- output from KeyGen

#### Output ####

- $p,K$ -- signature of $M$ with respect to public key $T$ or $\bot$

---

### NITSS: Sign 2/ ###

#### Rounds #1 & #2 -- signers ####

| Computation | Description |
|:---------------------------------------------|:-------------------------------|
| 1. $k_i, K \gets \texttt{NIDKG}(M)$ | run NIDKG protocol for msg $M$ |
| 2. $p_i = k_i + h(K,T,M) s_i$ | partial signature |
| 3. broadcast $p_i$ | publish partial signature |

---

### NITSS: Sign 3/3 ###

#### Round #3 -- aggregator ####

| Computation | Description |
|:---------------------------------------------|:-------------------------------|
| 1. receive $p_j$ | fetch partial signatures |
| 2. $p_j G \overset{?}{=} K_j + h(K,T,M) Q_j$ | verify partial signatures |
| 3. $J = \{j: p_j - valid\}$ | subset of valid signers |
| 4. if $\|J\| < t$ return $\bot$ | epic fail |
| 5. $p = \sum_{j \in J} l_j^{J}(0) p_j$ | interpolate final signature |
| 6. publish $(p,K)$ | publish signature |

---

### NITSS: Issue #1: Base points ###

Issue: Parties' public keys $Q_j = d_j G$ use base point $G$.
NITSS public key $T = \sum_j F_0^{(j)} = \sum_j f_0^{(j)} H$ uses base point $H$.
Points $G$, $H$ make up CRS and $\texttt{DL}_G(H)$ must be unknown.

Source: ElGamal encryption and CRS security claims

Solution #1: use twisted ElGamal to allow $G$ in both positions. :white_check_mark:
Solution #2: use non-standard $H$ base point for $Q_j$, requires tweaks to sign/verify algorithms, breaks compatibility. :x: (ugly)
Solution #3: use $H=G$ with ElGamal anyway and claim it's secure as ElGamal is **perfectly** binding. :x: (incompatible with aggregation)

---

### NITSS: Security ###

Adversary
Games
Security: UF, robustness

---

## Future work ##

1. Bulletproofs, TODOs
2. resharing, forward security
3. issues
4. provable security
5. implementation
6. integration

---

## Final notes ##

---

## Thank you ##