Perfect anonymity of presentations

[mmaker]

A desirable property for blind schemes is unlinkability. Unlinkability, roughly speaking, says that it should not be possible to link issuance with redemption of a credential.

Consider the (canonical) scenario where the user wants to sign a random message $m$ (a "token"), that is kept hidden at issuance time and revealed upon presentation. In the current setup, the server will have at disposal (from issuance):

• $C$, the first message at issuance time, and $(A, e, s'')$, the server response (5.3 blind spec)
• the presentation material $(\bar A, D, \bar B , \pi)$ and the message (3.7.1 sig spec) satisfying

  \begin{aligned}
  \bar A &= r_1r_2 A  \\ 
  D &= r_2 (G_0 + mG_1 + sG_2) \\ 
  \bar B &= -e \bar A + r_1 D \end{aligned}

A (very strong) attacker can check if the issuance message is linked to the presentation material via the following. Let $B = C + s''G_2 = G_0 + mG_1 + sG_2$ (The first equality can be computed without knowing the message, the second one requires to know $s'$ which seems to be the case in the current spec but can be removed) and compute

\begin{aligned}
\rho_1 = \log_D(\bar B - e \bar A) \\
\rho_2 = \log_B(D) \\
\textbf{check } \rho_1\rho_2 A = \bar A
\end{aligned}

A legacy alternative

It is possible to avoid this problem extracting from the BBS+ paper the presentation/show proof, that I'm rewriting here with minor changes for clarity

A' = A + rH \qquad
E' = eG + r'H

and letting

\pi = \text{PoK}\left\{
(m, e, s, r, r', u, u'): \begin{array}{c}
[xA]_T - [G_0]_T = m[G_1]_T + s[G_2]_T - e A' \\
0G = uG  + u'H  - rE' \\
E' = eG + r'H
\end{array}
\right\}

where $u = er, u' = rr'$ Intuitively, here one is sending two elements, each with its own blinding factor, and so for any presentation material $(A', E', \pi)$ and any issuance message $(A, e, s'')$ there are uniformly distributed blinding factors $r, r'$ that can relate the two.

The proof is obviously larger, but not too much. For a full disclosure of attributes, while the first one has size $3g + 4s$ ($g$ is the size of a group element, $s$, a scalar), this one has $2g + 6s$ size, which for 256-bit curves is only 32 more bytes.

[BasileiosKal]

Hey Michele! Thank you very much for that issue!

$\rho_1 = \log_D(\bar B - e \bar A)$

Sorry! Just to make sure I don't miss something, I assume you mean $\rho_1 = \log_D(\bar B + e \bar A)$ here?

Let me know if the following makes sense. Note that I'm focusing on the non blind case here. If I haven't missed anything, the same results could apply in the blind case as well.

Lets consider a BBS+ signature $\sigma = (A, e)$ as a signature over the point $B$, so that $(x + e) \cdot A= B$, where $x$ the Issuer's secret key (note that $B$ is the commitment to the messages).

Lets assume that we have a proof presentation $(\bar{A}, D, \bar{B}, \pi)$ generated using the signature $(A, e)$. Note that $\bar{B} = x \cdot \bar{A}$

Lets consider another signature $\sigma' = (A', e')$ over the point $B'$, where $\sigma \neq \sigma'$. If $\sigma'$ is valid, it means that,

(x + e') \cdot A'= B' \qquad \text{(*)}

Following the steps outlined in the original post, using $(\sigma', B')$ as the input, we will get $\rho_1$ and $\rho_2$ so that $D = \rho_2 \cdot B'$ and

\bar{B} + e' \cdot \bar{A} = (x + e') \cdot \bar{A} = \rho_1 \cdot D = \rho_1 \rho_2 \cdot B'

Substituting $B'$ from (*) we get that

(x + e') \cdot \bar{A}= (x + e') \cdot \rho_1 \rho_2 \cdot A'

Meaning that (assuming $x + e' \neq 0$),

\bar{A} = \rho_1 \rho_2 \cdot A'

This seems to suggest that the equation the adversary checks always holds? assuming any valid signature as input?

[mmaker]

Hey, thanks for the speedy answer here.

for the first question: you're right!

For the rest of the message, you're also right, thanks for clarifying this! Indeed it looks like all signatures appear the same but, differently from the original BBS+ protocol, it seems that a "simulator" for anonymity can't just present a message without having a valid signature to show. I don't think this is a problem at all, so I'm closing this issue for now.