changed a year ago
Linked with GitHub

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[1]. 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 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[2]
  • \(\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[3]

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[4] 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)\).

  1. Lan Nguyen. Accumulators from Bilinear Pairings and Applications in CT-RSA 2005: Topics in Cryptology. ↩︎

  2. Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch. RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2 November 2016. ↩︎

  3. Hashing to Elliptic Curves draft-irtf-cfrg-hash-to-curve-11 ↩︎

  4. Jan Camenisch, Manu Drijvers, and Anja Lehmann. Anonymous Attestation Using the Strong Diffie Hellman Assumption Revisited last revised Jan 2017. ↩︎

Select a repo