# BBS+ SPK Modification
## Slight modification of the [original proposal](https://hackmd.io/8t8o56mvTL6p-VZyayLnTA?view) from [Andrew Whitehead](https://github.com/andrewwhitehead)
### 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} = (0,L)$, $\mathcal{D} \cap \mathcal{R} = \emptyset$ and $0 \in \mathcal{R}$
$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, r_2, \tilde{e}, \tilde{r}_1, \tilde{r}_3, \{\tilde{m}_i\}_{i \in \mathcal{R}} \xleftarrow{\small{＄}} \mathbb{Z}_p^*$
$A' \gets Ar_1 r_2$
$D \gets (P_1 + \sum_{i=1}^L{H_im_i})r_2$
$\bar{A} \gets A'(-e) + Dr_1 ( = A' x)$
$r_3 = -r_2^{-1}$
$C_1 \gets A'\tilde{e} + D\tilde{r}_1$
$C_2 \gets D\tilde{r}_3 + \sum_{i \in \mathcal{R}}{H_i\tilde{m}_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}_1 = \tilde{r}_1 - r_1c$
$\hat{r}_3 = \tilde{r}_3 + r_3c$
for $i \in \mathcal{R}$, $\hat{m}_i = \tilde{m}_i + m_ic$
send $(A', \bar{A}, D, \hat{e}, \hat{r}_1, \hat{r}_3, \{\hat{m}_i\}, c)$

### SpkVerify

check $A' \neq 1$
$C_1 = \bar{A}c + A'\hat{e} + D\hat{r}_1$
$C_2 = (P_1 + \sum_{i \in \mathcal{D}}{H_im_i})c + D\hat{r}_3 + \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}, 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_1, r_3):\\
\bar{A} = A'(-e) + Dr_1 \land
P_1 + \sum_{i \in \mathcal{D}}H_{i}m_{i} = -Dr_3 - \sum_{i \in \mathcal{R}}H_{i}m_i\}$$

**Completeness:** Completeness trivially holds if $A \neq 1$ since $\bar{A} = A'x$. To prove that, $\bar{A} = A'x$ note that $A' = Dr_1(e+x)^{-1}$ and so we have,

$\bar{A} = A'(-e) + Dr_1 = D(r_1)(-e)(e+x)^{-1} + D(r_1) = D(r_1)(x)(e+x)^{-1} = A'x$

From that the pairing equality also follows trivially.

**Soundness:** Using the extractor of $\pi$, we can get $(\{m_i\}_{i \in \mathcal{R}}, e, r_1, r_3)$ such that:
$$\bar{A} = A'(-e) + Dr_1\\D(-r_3) = P_1 + \sum_{i \in \mathcal{D}}{H_im_i} + \sum_{i \in \mathcal{R}}{H_im_i}$$

From $e(\bar{A}, P_2) = e(A', W)$ we have $\bar{A} = A'x$ and from the first equation of $\pi$ we get:
$$A'(-e) + Dr_1 = A'x \Rightarrow A'(e+x) = Dr_1$$

From the second equation of $\pi$ we get $D = (P_1 + \sum_{i=0}^L{H_im_i})(-r_3^{-1})$ and substituting in the above we get,
$$A'(e+x) = (P_1 + \sum_{i=0}^L{H_im_i})(-r_3^{-1}r_1)$$

we can see that if $r_3, r_1 \neq 0$ (they should if $A' \neq 1$) an extractor can compute $A'(-r_3 r_1^{-1})$ to obtain a valid signature over the messages $\{m_i\}_{i=0}^L$.

**Zero Knowledge:** A proof of knowledge of a signature on messages $\{m_i\}_{i=0}^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$. Note that $(A', \bar{A}, D)$ are uniform in $\mathbb{G}_1^*$ and $\bar{A} = A'x$ as in a real proof. Use the simulator of $\pi$ to construct the simulated proof.