I'm new to blind signatures, trying to understand security notions of it: blindness and one-more unforgeability.

I found out that in the security game for blindness property, the adversary $\mathcal{A}$ interacts with two users (each with messages $m_0$ and $m_1$). Without knowing who signed first, $\mathcal{A}$ gets a list of signatures in order $\{\sigma(m_b),\sigma(m_{1-b})\}$. Then $\mathcal{A}$ would try to guess which of them came first. That is, to guess a bit $b'$. So $\mathcal{A}$ succeeds if $b'=b$.

My question is: why do we need to interact with two users (or twice)? Can't we just give $\mathcal{A}$ a signature of randomly selected message ($m_0$ or $m_1$)? In that case, $\mathcal{A}$ would try to guess which of those two messages were signed.

Can anyone give me the reason why do we need two interactions in the security game?

Thanks in advance.


1 Answer 1


A blind signature scheme is an interactive protocol between a signer $\mathsf{S}$ (holding a secret key $sk$) and a user $\mathsf{U}$ (holding a public key $pk$ and a message $m$) with the goal that $\mathsf{U}$ obtains a signature $\sigma$ on $m$.

Depending on the construction at hand, the number of moves needed to complete the interactive protocol may vary. This, in turn, may have an impact on the way the security game is played. In the case of a round-optimal blind signature scheme the protocol would look like this: $$ \begin{array}{lcl} \hline \text{Signer } \mathsf{S}(sk) & & \text{User } \mathsf{U}(pk,m) \\ \hline & & c\gets\mathsf{U}_1(pk,m) \\ & \stackrel{c}{\longleftarrow} & \\ s\gets\mathsf{S}(sk,c) & \\ & \stackrel{s}{\longrightarrow} & \\ & & \sigma\gets\mathsf{U}_2(pk,c,s,m) \\ & & \text{Output } \sigma \\ \hline \end{array} $$ Whereas the protocol for a three-move blind signature scheme would look like this: $$ \begin{array}{lcl} \hline \text{Signer } \mathsf{S}(sk) & & \text{User } \mathsf{U}(pk,m) \\ \hline R\gets\mathsf{S}_1(sk) & \\ & \stackrel{R}{\longrightarrow} & \\ & & c\gets\mathsf{U}_1(pk,m) \\ & \stackrel{c}{\longleftarrow} & \\ s\gets\mathsf{S}_2(sk,c) & \\ & \stackrel{s}{\longrightarrow} & \\ & & \sigma\gets\mathsf{U}_2(pk,c,s,m) \\ & & \text{Output } \sigma \\ \hline \end{array} $$ Here, $\mathsf{U}$ and $\mathsf{S}$ are split into $\mathsf{U}_i$s and $\mathsf{S}_i$s, respectively (it is not vital what $R$, $c$, and $s$ represent). Whilst, the blindness game would proceed the same way for both schemes, the one-more unforgeability game would proceed somewhat differently in each case.

Informally, blindness ensures that a signer $\mathsf{S}$ issuing signatures on two messages $(m_0,m_1)$ of its own choice to a user $\mathsf{U}$, can not tell in what order it issued them. More specifically, $\mathsf{S}$ is given both resulting signatures $\sigma_0,\sigma_1$, and can keep the transcript of both interactions with $\mathsf{U}$. In the blindness game, the game takes on the role of the honest user and the adversary $\mathcal{A}$ takes on the role of a malicious signer and is thus given both the secret and public key.

First, the game samples a fresh key pair $(sk,pk)$. Next, the game samples a random bit $b$ which determines the order in which the adversarially chosen messages are signed. $\mathcal{A}$ is given access to three oracles $\texttt{Init}$, $\texttt{Usr}_1$ and $\texttt{Usr}_2$. By convention, $\mathcal{A}$ first has to query the $\texttt{Init}$ oracle. Then, $\mathcal{A}$ may open at most two sessions by calling the $\texttt{Usr}_1$ oracle twice. For each of these two sessions, $\mathcal{A}$ obtains corresponding transcripts $T_1=(c_1,s_1)$ and $T_2=(c_2,s_2)$. The game uses $m_b$ and $m_{1-b}$ to generate the transcripts $T_1$ and $T_2$, respectively. If $\mathcal{A}$ completes both sessions honestly with the game, it obtains signatures $\sigma_b$ and $\sigma_{1-b}$ on messages $m_b$ and $m_{1-b}$. Note that $\mathcal{A}$ obtains $\sigma_b$ and $\sigma_{1-b}$ by calling $\texttt{Usr}_2$ twice. More precisely, the first call to $\texttt{Usr}_2$ closes the first session and the second call closes the second session. Once both session are closed, the game checks if $\mathcal{A}$ acted honestly in both of them and if so, returns the signatures $(\sigma_b,\sigma_{1-b})$. If instead $\mathcal{A}$ has behaved dishonestly and, as a result $\sigma_b=\bot$ or $\sigma_{1-b}=\bot$ at the time of closing the second session, $\texttt{Usr}_2$ returns $(\bot,\bot)$. At the end of the experiment, $\mathcal{A}$ has to guess the bit $b$. We define the advantage of adversary $\mathcal{A}$ in the game as $\mathsf{Adv}(\mathcal{A}):=|\Pr[\mathsf{Game}^{\mathcal{A}}\Rightarrow1]-\frac{1}{2}|$.

References. Hauck E., Kiltz E., Loss J., Nguyen N.K. (2020) Lattice-Based Blind Signatures, Revisited. In: Micciancio D., Ristenpart T. (eds) Advances in Cryptology – CRYPTO 2020. CRYPTO 2020. Lecture Notes in Computer Science, vol 12171. Springer, Cham. https://doi.org/10.1007/978-3-030-56880-1_18


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.