## BBS SPK with Commitment

Prove that the value behind a commitment is also included in a BBS Signature.

## SPK
Given $r_1, r_2, r \xleftarrow{\small{＄}} \mathbb{Z}_p^*$

Set the following

$r_3 \gets r_1 ^{-1}$
$s' \gets r_2 * r_3$
$A' \gets A * r_1$
$\bar{A} \gets A' * (-e) + B * r_1$
$B \gets P_1 + \sum_{i \gets 1}^{L}H_i * m_i$
$D \gets B * r_1 + H_0 * r_2$

Chose 2 generator points $g_r, g_m$ and calculate a commitment of $m_1$

$C = g_r ^ r g_m ^ {m_1}$

We assume that $m_1$ is not revealed. Let $R$ be the index of disclosed messages ($1 \not\in R$). Calculate a proof $\pi$ such that

$$\pi \in SPK\{(m_1, \{m_i\}_{i\not\in R \cup \{1\}}, e, r_2, r_3, s', ), \\
\bar{A}/D = A' ^ {-e}h_0^{r_2} \land g_1 \prod_{i \in R}h_i ^ {m_i} = D^{r_3}h_0^{-s'} h_{1}^{m_1} \prod_{i \not\in R \cup \{1\}} h_i ^ {-m_i} \land\\ C = g_r ^{r} g_m ^ {m_1}\}$$

## Pseudo code

### Proof Generation
$r_1, r_2, r, \tilde{r}, \tilde{e}, \tilde{r}_2, \tilde{r}_3, \tilde{s}, \{\tilde{m}_{i\not\in R}\} \xleftarrow{\small{＄}} \mathbb{Z}_p^*$

$B \gets g_1h_0^{s}\prod_{i = 1} ^ L h_i^{m_i}$

$r_3 = r_1^{-1}$

$A' \gets A ^ {r_1}$
$\bar{A} \gets A'^{-e} B ^ {r_1}$
$D \gets B ^ {r_1} h_0 ^ {r_2}$
$C \gets g_r ^ r g_m ^ {m_1}$

$C_1 \gets A'^{\tilde{e}} h_0 ^ {\tilde{r}_2}$
$C_2 \gets D ^ {-\tilde{r}_3} h_0 ^ \tilde{s} \prod_{i \not\in R}{h_i ^ {\tilde{m}_i}}$
$C_3 \gets g_r ^ \tilde{r}g_m ^ {\tilde{m}_1}$

$c = H(PK \| \{m_i\}_{i \in \mathcal{D}} \| A' \| \bar{A} \| D \| C \| C_1 \| C_2 \| C_3 \| ...)$

$\hat{e} = \tilde{e} + e * c$
$\hat{r} = \tilde{r} + r * c$
$\hat{r}_2 = \tilde{r}_2 + r_2 * c$
$\hat{r}_3 = \tilde{r}_3 + r_3 * c$

$s' = s + r_2 * r_3 + s$
$\hat{s} = \tilde{s} + c * r_2 * r_3$

for $i \not\in R \cup \{1\}$, $\hat{m}_i = \tilde{m}_i + m_ic$

return $proof = (A', \bar{A}, D, C, c, \hat{e}, \hat{r}_2, \hat{r}_3, \hat{s}, \hat{r}, \{\hat{m}\}_{i \not\in R \cup \{1\}} )$

### Proof Verify

$(A', \bar{A}, D, C, c, \hat{e}, \hat{r}_2, \hat{r}_3, \hat{s}, \hat{r}, \{\hat{m}\}_{i \not\in R \cup \{1\}} ) \gets proof$

$C_1 \gets (\bar{A} / D) ^ c A' ^ \hat{e} h_0 ^ {\hat{r}_2}$

$T \gets g_1 \prod_{i \in R} h_i^{m_i}$

$C_2 = T ^ c D ^ {-\hat{r}_3} h_0 ^ {\hat{s}} h_1 ^{\hat{m}_1} \prod_{i \not\in R \cup \{1\}}{h_i ^ {\hat{m}_i}}$

$C_3 = C ^ {-c} g_r ^ {\hat{r}} g_m ^ {\hat{m}_1}$

$c_v = H(PK \| \{m_i\}_{i \in \mathcal{D}} \| A' \| \bar{A} \| D \| C \| C_1 \| C_2 \| C_3 \|...)$

check $c = c_v$
check $e(\bar{A}, P_2) = e(A', W)$