# BBS+ SPK

***Warning*:** can allow for correlation if *A* is leaked, making the proof not fully zero knowledge, [see updated version](https://hackmd.io/@Vasileios/H190hWAg5).

### Definitions

$P_1, P_2$: standard generator points of curves $\mathbb{G}_1$ and $\mathbb{G}_2$ respectively
$L$: the number of signed messages
$\mathcal{D}, \mathcal{R}$: indices of disclosed and undisclosed messages, such that $\mathcal{D} \cup \mathcal{R} = (1,L)$
$H_i$: a predetermined, randomly generated point in $\mathbb{G_1}$ called the message generator, associated with message index $i$
$x$: the private key of the issuer
$W$: the public key of the issuer in $\mathbb{G}_2$, defined as $P_2x$

### SpkGen

$r_1, \tilde{e}, \tilde{r}_2, \{\tilde{m}_i\}_{i \in \mathcal{R}} \xleftarrow{\small{＄}} \mathbb{Z}_p^*$
$r_2 = -r_1^{-1}$
$A' = Ar_1$
$\bar{A} \gets A'(-e)$
$D = (P_1 + \sum_{i=1}^L{H_im_i})r_1$
$C_1 = A'\tilde{e}$
$C_2 = D\tilde{r}_2 + \sum_{i \in \mathcal{R}}{H_im_i}$
$c = H(W \| \{m_i\}_{i \in \mathcal{D}} \| A' \| \bar{A} \| D \| C_1 \| C_2 \| ...)$
$\hat{e} = \tilde{e} + ec$
$\hat{r}_2 = \tilde{r}_2 + r_2c$
for $i \in \mathcal{R}$, $\hat{m}_i = \tilde{m}_i + m_ic$
send $(A', \bar{A}, D, \hat{e}, \hat{r}_2, \{\hat{m}_i\}, c)$

### SpkVerify

check $A' \neq 1$
$C_1 = \bar{A}c + A'\hat{e}$
$C_2 = (P_1 + \sum_{i \in \mathcal{D}}{H_im_i})c + D\hat{r}_2 + \sum_{i \in \mathcal{R}}{H_i\hat{m}_i}$
$c_v = H(W \| \{m_i\}_{i \in \mathcal{D}} \| A' \| \bar{A} \| D \| C_1 \| C_2 \| ...)$
check $c = c_v$
check $e(\bar{A} + D, P_2) = e(A', W)$

## Analysis

The signature proof of knowledge takes the following form:

$$\pi \in SPK\{(\{m_i\}_{i \in \mathcal{R}},e,r_2):\\
-\bar{A} = A'e \land
-P_1 - \sum_{i \in \mathcal{D}}H_{i}m_{i} = Dr_2 + \sum_{i \in \mathcal{R}}H_{i}m_i\}$$

**Completeness:** If $A \neq 1$ then we have $A' \neq 1$. $\pi_1$ and $\pi_2$ trivially follow from the construction of $\bar{A}$ and $D$. For the pairing check, we have $\ \ \ e(\bar{A} + D, P_2)\\\ \ = e(A'(-e) + A'(e + x), P_2)\\\ \ = e(A'x, P_2)\\\ \ = e(A', W).$

**Soundness:** By the soundness of proof $\pi$, we can extract $(\{m_i\}_{i \in \mathcal{R}}, e, r_2)$ such that:
$$\bar{A} = A'(-e)\\D = (P_1 + \sum_{i \in \mathcal{D}}{H_im_i} + \sum_{i \in \mathcal{R}}{H_im_i})(-r_2^{-1})$$

From $e(\bar{A} + D, P_2) = e(A', W)$ we have $\bar{A} + D = A'x$, giving:
$$A'(-e) + D = A'x\\A' = D(e + x)^{-1}$$

Substituting $D(-r_2) = P_1 + \sum_{i=1}^L{H_im_i}$ from $\pi_2$, we see that an extractor can compute $A'(-r_2)$ to obtain a valid signature over the messages $\{m_i\}_{i=1}^L$.

**Zero Knowledge:** A proof of knowledge of a signature on messages $\{m_i\}_{i=1}^L$ can be simulated using the pair $(\bar{g}, \bar{g}x) \in \mathbb{G}_1^2$ which must be published by the issuer. Take a random $p \xleftarrow{\small{＄}} \mathbb{Z}_p^*$ and $D \xleftarrow{\small{＄}} \mathbb{G}_1^*$, and set $A' = \bar{g}p$ and $\bar{A} = (\bar{g}x)p - D$. Note that $(A', D)$ are uniform in $\mathbb{G}_1^*$ and $\bar{A} + D = A'x$ as in a real proof. Use the simulator of $\pi$ to construct the simulated proof.