Blind signature

A blind signature scheme is a signature scheme whose signing algorithm is an interactive protocol between a signer holding the secret key and a user holding a message: the user obtains a signature on the message, while the signer learns nothing about the message or the resulting signature — Cha82.

Syntax

A blind signature scheme is a tuple $(\mathsf{KeyGen},S,U,\mathsf{Vrfy})$, following the two-party protocol syntax:

• $\mathsf{KeyGen}(1^{\lambda })\to (\mathsf{sk},\mathsf{pk})$, a randomized algorithm sampling a key pair,
• $S$ (the signer, on input $\mathsf{sk}$) and $U$ (the user, on input $\mathsf{pk}$ and a message $m\in \mathcal{M}$) are interactive algorithms with $⟨S(\mathsf{sk}),U(\mathsf{pk},m)⟩\to (\perp ,\sigma )$, where $\sigma$ is a signature or $\perp$,
• $\mathsf{Vrfy}(\mathsf{pk},m,\sigma )\to b$, a deterministic algorithm outputting a bit $b\in \{0,1\}$.

Properties

Correctness

The scheme is perfectly correct if for all $m\in \mathcal{M}$, $\mathrm{Pr}\left[\mathsf{Vrfy}(\mathsf{pk},m,\sigma )=1\right]=1$, where $(\mathsf{sk},\mathsf{pk})\leftarrow \mathsf{KeyGen}(1^{\lambda })$ and $(\perp ,\sigma )\leftarrow ⟨S(\mathsf{sk}),U(\mathsf{pk},m)⟩$.

One-more unforgeability

The adversary plays the user in signer sessions that it may interleave arbitrarily; after completing $\ell$ of them it must not output valid signatures on $\ell +1$ distinct messages — PS00.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{omuf}}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\sk, \pk) \gets \KeyGen(1^\secpar)$ ; $\ell \gets 0$
\State $((m_1, \sigma_1), \ldots, (m_k, \sigma_k)) \gets \calA^{\calO_{S}}(1^\secpar, \pk)$
\Return $\big[k > \ell \land m_1, \ldots, m_k \text{ distinct} \land \forall_{i \in [k]}~\Vrfy(\pk, m_i, \sigma_i) = 1\big]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{S}(j, M)$}
\begin{algorithmic}
\If{session $j$ is new}
\State start a signer $S_j(\sk)$ with fresh coins
\EndIf
\State feed $M$ to $S_j$; let $M'$ be its next message
\If{$S_j$ has sent its last message}
\State $\ell \gets \ell + 1$
\EndIf
\Return $M'$
\end{algorithmic}
\end{algorithm}

The scheme is one-more unforgeable if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\Pi ,\mathcal{A}}^{\text{omuf}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\Pi ,\mathcal{A}}^{\text{omuf}}(\lambda )=1\right]$$

is negligible. Strong one-more unforgeability asks only that the $k$ pairs $(m_i,{\sigma }_i)$ be distinct — standard.

Blindness

The adversary plays the signer, with a public key of its choice, in two sessions with honest users on messages $m_0,m_1$ it chooses, the first session on $m_b$ and the second on $m_{1-b}$ for a hidden bit $b$; it then gets both signatures and must guess $b$ — standard.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{blind}}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\pk, m_0, m_1, \stA) \gets \calA(1^\secpar)$ ; $b \getsr \bits$
\State Run $\langle \calA(\stA), U(\pk, m_b) \rangle$ and $\langle \calA(\stA), U(\pk, m_{1-b}) \rangle$, scheduled by $\calA$
\Comment{the first session yields $\sigma_b$, the second $\sigma_{1-b}$}
\If{$\sigma_0 = \bot$ or $\sigma_1 = \bot$}
\State $(\sigma_0, \sigma_1) \gets (\bot, \bot)$
\EndIf
\State $b' \gets \calA(\stA, \sigma_0, \sigma_1)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

The scheme is blind if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\Pi ,\mathcal{A}}^{\text{blind}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\Pi ,\mathcal{A}}^{\text{blind}}(\lambda )=1\right]-1\right|$$

is negligible.

Variations

Blind Schnorr signatures

The key pair is a Schnorr key pair $(x,X=g^x)$ in a group of prime order $p$, and a signature is an ordinary Schnorr signature. The signer sends $R=g^r$ for $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$. The user samples $\alpha ,\beta \stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$, sets $R^{\prime }=R{g}^{\alpha }{X}^{\beta }$ and $c^{\prime }=H(R^{\prime }\Vert m)$, and sends $c=c^{\prime }+\beta \mathrm{mod}p$. The signer replies $s=r+cx\mathrm{mod}p$; the user checks $g^s=R{X}^c$ and outputs $\sigma =(R^{\prime },s+\alpha )$, which satisfies $g^{s+\alpha }=R^{\prime }{X}^{c^{\prime }}$ — Sch01, FPS20. Every valid signature is consistent with every signer session under exactly one choice of $(\alpha ,\beta )$, so the scheme is perfectly blind — standard. As an object, blind Schnorr signatures denote the scheme with one-more unforgeability against polynomially many concurrent sessions.

Blind Schnorr signatures are not one-more unforgeable: an adversary that opens $\ell >\log p$ concurrent sessions forges $\ell +1$ signatures in polynomial time, by solving the ROS problem — BLLOR21.

Blind Okamoto-Schnorr signatures

The blind version of the Fiat–Shamir transform of the Okamoto identification protocol, with public key $X=g_1^{x_1}{g}_2^{x_2}$. The signer sends $A=g_1^{r_1}{g}_2^{r_2}$. The user samples ${\alpha }_1,{\alpha }_2,\beta \stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$, sets $A^{\prime }=A{g}_1^{{\alpha }_1}{g}_2^{{\alpha }_2}{X}^{\beta }$ and $c^{\prime }=H(A^{\prime }\Vert m)$, and sends $c=c^{\prime }+\beta \mathrm{mod}p$. The signer replies $z_j=r_j+c{x}_j\mathrm{mod}p$, and the user outputs $(A^{\prime },z_1+{\alpha }_1,z_2+{\alpha }_2)$, which satisfies $g_1^{z_1+{\alpha }_1}{g}_2^{z_2+{\alpha }_2}=A^{\prime }{X}^{c^{\prime }}$ — PS00. As an object, blind Okamoto–Schnorr signatures denote the scheme with one-more unforgeability against a number of signer sessions logarithmic in $\lambda$, which may run in parallel.

Other results

• A transformation of blind Okamoto–Schnorr signatures gives a scheme secure against polynomially many sequential signer interactions — Poi98.
• Chaum’s RSA blind signature is one-more unforgeable in the random-oracle model under the one-more RSA-inversion assumption — BNPS03.

Participates in

Produces Blind signature

• OMDL + ROS ⇒ Blind Schnorr signatures (via Blind Schnorr signatures)
• DLOG ⇒ Blind Okamoto–Schnorr signatures (via Blind Okamoto-Schnorr signatures)