## Extractable Witness Encryption for KZG Commitments --- ## Brief Story ----  ## $+$  ----  ----  ----  --- ## Witness Encryption ---- ### Encryption  ---- ### Public Key Encryption  ---- ## Witness Encryption  ---- ## Witness Encryption  ---- ## NP Problem - If there is a witness, it can be verified by a deterministic algorithm in polynomial time. ---- ## NP Relation $$ \mathcal{R} = \{ (x, w) \mid M_r(x, w) = 1 \} $$ - $x$ -- Statement - $w$ -- Witness - $M_r(x, w)$ -- Check algorithm ---- ### Language $$ \mathcal{L} = \{ x \mid \exists w \text{ such that } (x, w) \in \mathcal{R} \} $$ ---- #### Correctness $$ (x, w) \in \mathcal{R} $$  ---- #### Security $x \notin \mathcal{L}$  $c_0 \approx_c c_1$ ---- - If no witness exists, then $c$ should reveal nothing about $m$ - Without a valid solution, decryption should not be possible - Hard problems: determining $x \in \mathcal{L}$ is computationally infeasible without a witness. ---- ### Witness Encryption for Specific Relations - Witness Encryption schemes for arbitrary NP relations **exist** but are not efficient. - We will look at Witness Encryptions for KZG commitments. --- #### KZG Polynomial Commitment Scheme  ---- ### WE for KZG  ---- ### Language  $$ \pi:=\left[\frac{f(\tau)-\beta}{\tau-\alpha}\right]_1 $$ --- ### Key Encapsulation Mechanism  ---- #### Extractable Witness KEM for KZG $$ \small \begin{aligned} &e\left(\operatorname{com}-[\beta]_1,[1]_2\right) = e\left(\pi,[\tau]_2-[\alpha]_2\right) \end{aligned} $$ $$ \small \textbf{Encap}^{\text{H}}(\text{ck}, (\text{com}, \alpha, \beta)) \begin{cases} r \leftarrow \mathbb{F}_p \\ s := e\left(r \cdot \left(\text{com} - [\beta]_1\right), [1]_2\right) \\ \text{ct} := r \cdot \left([\tau]_2 - [\alpha]_2\right) \\ \text{k} := \text{H}(s) \\ \text{return } (\text{ct}, \text{k}) \end{cases} $$ $$ \small \textbf{Decap}^{\text{H}}(\text{ck}, \pi, \text{ct}) \begin{cases} s := e(\pi, \text{ct}) \\ \text{k} := \text{H}(s) \\ \text{return } \text{k} \end{cases} $$ ---- ### Extractable WE for KZG Commitments $$ \small \operatorname{Enc}((\text{com}, \alpha, \beta), m) \begin{cases} \left(\mathrm{ct}_1, \mathrm{k}\right) \leftarrow \textbf{Encap}^{\text{H}}((\text{com}, \alpha, \beta)) \\ \mathrm{ct}_2 \leftarrow \mathrm{Enc}^{\text{sym}}(\mathrm{k}, m) \\ \text{return } \left(\mathrm{ct}_1, \mathrm{ct}_2\right) \end{cases} $$ $$ \small \operatorname{Dec}\left(\pi, \left(\mathrm{ct}_1, \mathrm{ct}_2\right)\right) \begin{cases} \mathrm{k} := \textbf{Decap}^{\text{H}}\left( \pi, \mathrm{ct}_1\right) \\ m := \operatorname{Dec}^{\text{sym}}\left(\mathrm{k}, \mathrm{ct}_2\right) \\ \text{return } m \end{cases} $$ --- ## Keaki :deciduous_tree: ---- - Rust implementation :crab: - Simple layout: - `kzg` Module - `setup`, `open`, `commit`, `verify`, `open_fk` - `kem` Module - `encapsulate`, `decapsulate` - `we` Module - `encrypt`, `decrypt` - `vec` Module - `we` wrapper to work with vectors ---- ### Vector $$ \mathbf{v} = [v_1, v_2, \dots, v_n] $$ - We can think of each value as the evaluation of a polynomial at the $n$-th root of unity. - This allows us to perform $iFFT$ to convert it into the coefficients representation. ----  --- ## Oblivious Transfer - Cryptographic two-party protocol between a **sender** and a **receiver** - Allows the receiving party to decrypt **one** of the sending party’s messages - The sender does not learn the choice of the receiver - The receiver does not learn the non selected inputs ---- ## 1-out-of-2 Oblivious Transfer  ---- ## Laconic Oblivious Transfer  ----  ----  ----  --- :pray: