# zk-SAM: Signed Accumulator Membership

The zk-SAM procedure consists of a signature proof of knowledge combined with a pairing-based accumulator membership proof. It allows the prover to demonstrate knowledge of a value $n$ that is contained in an unrevealed, but signed accumulator. This acts as a basis of a scalable, anonymous credential revocation system.

The signature is a short group signature based on BBS+. It covers selectively-revealed associated messages in addition to the accumulator value, and is verifiable against the issuer's public signing key in combination with a public accumulation key.

The pairing-based accumulator design follows Ngu05[^Ngu05]. In brief, a witness for a member value $n$ in an accumulator $V$ is defined by $W = V(n + z)^{-1}$ where $z$ is the private revocation key of the issuer.

See [Non-Revocation Token](https://hackmd.io/kj223D1ZQN29WiusmnPFMA?view) for implementation details.

Notation:

- $P_1$, $P_2$: standard generators of the target pairing-friendly elliptic curve groups $G_1$ and $G_2$
- $\mathit{I2OSP(n,c)}$: Encode an integer value as a series of $c$ octets, as defined by RFC-8017[^RFC8017]
- $\mathit{H2I}(...)$: Hash a series of octets to produce an element in $\mathbb{Z_\mathit{p}^*}$ (TODO: add reference and parameters)
- $\mathit{H2C}(...)$: Hash a series of octets to produce a value on the curve $G_1$ according to hash-to-curve RFC draft 11[^hash-to-curve]

## SetupGenerators

Inputs:

- $l$: the message generator count
- $P_2{k} \in G_2$: public signing key
- $P_2{z} \in G_2$: public accumulation key

Procedure:

- Set $H_i \gets \mathit{H2C}(P_2{k} \parallel \mathit{I2OSP}(0, 1) \parallel P_2{z} \parallel \mathit{I2OSP}(i, 4))$
- Output $H_1 ... H_l$

## Sign

Inputs:

- $H_i \in G_1$: message generators
- $m_i \in \mathbb{Z_\mathit{p}}$: message values
- $V \in G_1$: accumulator value
- $k \in \mathbb{Z_\mathit{p}}$: private signing key

Procedure:

- Set $B \gets P_1 + V + \sum_{i=1}^l{H_{i}m_i}$
- Set $e \gets \mathit{H2I}(V \parallel m_1 \parallel ... \parallel m_l)$
- Set $A \gets B(e + k)^{-1}$
- Output $A, e$

## PrepareSPK

Inputs:

- $H_i \in G_1$: message generators
- $m_i \in \mathbb{Z_\mathit{p}}$: message values
- $n \in \mathbb{Z_\mathit{p}}$: member value
- $V \in G_1$: accumulator value
- $W \in G_1$: witness value for $n$ in accumulator $V$
- $A \in G_1$: signature value
- $e \in \mathbb{Z_\mathit{p}}$: signature nonce
- $\mathcal{D} \subset [1,l]$: the set of revealed messages indices

Procedure:

- Choose $r_1 \xleftarrow{\small{＄}} \mathbb{Z_\mathit{p}^*}$ and set $r_2 \gets r_1^{-1}$
- Set $B \gets P_1 + V + \sum_{i=1}^l{H_{i}m_i}$
- Set $A' \gets Ar_1$
- Set $\bar{A} \gets Br_1 - A'e$ ($= A'k$)
- Set $W' \gets Wr_1$
- Set $\bar{W} \gets Vr_1 - W'n$ ($= W'z$)
- Set $E \gets Br_1 - W'n$
- Choose $\tilde{e}, \{\tilde{m_i}\}_{i \notin \mathcal{D}}, \tilde{n}, \tilde{r_2} \xleftarrow{\small{＄}} \mathbb{Z_\mathit{p}^*}$
- Output $A', \bar{A}, W', \bar{W}, E, \tilde{e}, \{\tilde{m_i}\}, \tilde{n}, \tilde{r_2}$

## GenChallenge

Inputs:

- $\mathcal{D} \subset [1,l]$: the set of revealed messages indices

Procedure:

- Prover: compute
$$\displaylines{C_1 \gets A'\tilde{e} + W'\tilde{n}\\
C_2 \gets (E - \bar{W})\tilde{r_2} - \sum_{i \notin \mathcal{D}}{H_i\tilde{m_i}}}$$
- Verifier: using the prover's challenge value $c$, compute
$$\displaylines{C_1 \gets A'\hat{e} + W'\hat{n} + (\bar{A} - E)c\\
C_2 \gets (E - \bar{W})\hat{r_2} - \sum_{i \notin \mathcal{D}}{H_{i}\hat{m_i}} + (P_1 + \sum_{i \in \mathcal{D}}H_{i}m_i)c}$$
- Output $A' \parallel \bar{A} \parallel W' \parallel \bar{W} \parallel E \parallel C_1 \parallel C_2$ as the input to the challenge hash function

## CompleteSPK

Inputs:

- $e \in \mathbb{Z_\mathit{p}}$: signature nonce
- $\{m_i\}_{i \notin \mathcal{D}}$: unrevealed message values
- $n \in \mathbb{Z_\mathit{p}}$: member value
- $r_2 \in \mathbb{Z_\mathit{p}}$: blinding factor
- $\tilde{e}, \{\tilde{m_i}\}, \tilde{n}, \tilde{r_2} \in \mathbb{Z_\mathit{p}}$
- $c \in \mathbb{Z_\mathit{p}}$: challenge value

Procedure:

- Set $\hat{e} = \tilde{e} + ce$
- Set $\hat{m_i} = \tilde{m_i} - cm_i$
- Set $\hat{n} = \tilde{n} - cn$
- Set $\hat{r_2} = \tilde{r_2} - cr_2$
- Output $\hat{e}, \{\hat{m_i}\}, \hat{n}, \hat{r_2}$

## VerifySPK

_In addition to verifying the Fiat-Shamir challenge value._

Inputs:

- $P_{2}k \in G_2$: public signing key
- $P_{2}z \in G_2$: public accumulation key
- $A', \bar{A}, W', \bar{W} \in G_1$

Procedure:

- If $A' = 0$ or $W' = 0$ return INVALID
- If $e(A', P_{2}k) \ne e(\bar{A}, P_2)$ return INVALID
- If $e(W', P_{2}z) \ne e(\bar{W}, P_2)$ return INVALID
- Return VALID

Explanation:

The prover demonstrates (adapted from CDL16[^CDL16] 4.5):
$$\displaylines{\pi \in SPK\lbrace(e,\{m_i\}_{i \notin \mathcal{D}},n,r2):\\
\bar{A} - E = W'n - A'e \land\\
P_1 + \sum_{i \in \mathcal{D}}H_{i}m_{i} = (E - \bar{W})r_2 - \sum_{i \notin \mathcal{D}}H_{i}m_i\rbrace}$$

- From $\pi_1$, $\bar{A} = W'n - A'e + E$. Given $e(A', P_{2}k) = e(\bar{A}, P_2)$, substitute $\bar{A} = A'k$ to show $A'(e + k) = W'n + E$.
- From $\pi_2$, $E = \bar{W} + (P_1 + \sum_{i=1}^l{H_{i}m_i})r_2^{-1}$, and so $A'(e + k) = W'n + \bar{W} + (P_1 + \sum_{i=1}^l{H_{i}m_i})r_2^{-1}$.
- Given $e(W', P_{2}z) = e(\bar{W}, P_2)$, substitute $\bar{W} = W'z$ to show $A'r_2(e + k) = P_1 + W'r_2(n + z) + \sum_{i=1}^l{H_{i}m_i}$.
- Thus, $(A'r_2, e)$ is a valid signature, and $W'r_2$ represents a valid membership witness for member value $n$ in the signed accumulator $V = W'r_2(n + z)$.

[^CDL16]: Jan Camenisch, Manu Drijvers, and Anja Lehmann. [Anonymous Attestation Using the Strong Diffie Hellman Assumption Revisited](https://eprint.iacr.org/2016/663) last revised Jan 2017.
[^RFC8017]: Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch. [RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2](https://www.rfc-editor.org/info/rfc8017) November 2016.
[^hash-to-curve]: [Hashing to Elliptic Curves](https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11) draft-irtf-cfrg-hash-to-curve-11
[^Ngu05]: Lan Nguyen. [Accumulators from Bilinear Pairings and Applications](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.4846&rep=rep1&type=pdf#page=286) in CT-RSA 2005: Topics in Cryptology.