Ring signature

A ring signature scheme lets a user sign on behalf of any set of public keys, a ring, that contains its own: the signature verifies under the ring and hides which of its members produced it, with no group manager, setup or cooperation from the other members — RST01.

Syntax

A ring signature scheme is a tuple of efficient algorithms with respect to message space , where a ring is a list of public keys — BKM06:

  • , a randomized algorithm, run by each user independently,
  • , a randomized algorithm that outputs a signature on with respect to a ring containing the public key of ,
  • , a deterministic algorithm outputting a bit .

Properties

Correctness

A ring signature scheme is -correct if for all , all key pairs output by with , all and ,

over the randomness of . When , is perfectly correct.

Anonymity against full key exposure

honest users generate keys with coins . The adversary has a signing oracle for every honest user on rings of its choice, which may contain public keys it made up. It names two honest users , a message and a ring containing both of their keys, and receives a signature on with respect to by user together with every user’s coins , so that it holds every secret key, those of and included; it must guess — BKM06.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{anon}}_{\Pi,\calA}(\secpar, n)$}
\begin{algorithmic}
\For{$i \in [n]$}
\State $\omega_i \getsr \bits^*$; $(\pk_i, \sk_i) \gets \KeyGen(1^\secpar; \omega_i)$
\EndFor
\State $S \gets (\pk_1, \ldots, \pk_n)$; $b \getsr \bits$
\State $(i_0, i_1, m^*, R^*, \stA) \gets \calA^{\calO_{\Sign}}(1^\secpar, S)$
\Comment{$i_0 \ne i_1$ and $\pk_{i_0}, \pk_{i_1} \in R^*$}
\State $\sigma^* \gets \Sign(\sk_{i_b}, m^*, R^*)$
\State $b' \gets \calA^{\calO_{\Sign}}(\stA, \sigma^*, \omega_1, \ldots, \omega_n)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\Sign}(i, m, R)$}
\begin{algorithmic}
\If{$\pk_i \notin R$}
\Return $\bot$
\EndIf
\Return $\Sign(\sk_i, m, R)$
\end{algorithmic}
\end{algorithm}

A ring signature scheme is anonymous against full key exposure if for every polynomial and all efficient ,

is negligible.

Unforgeability with respect to insider corruption

The adversary has a signing oracle for every honest user on rings of its choice and may corrupt honest users adaptively, learning their key-generation coins. It wins with a valid signature on a message with respect to a ring of uncorrupted honest users, provided it never asked for a signature on with respect to — BKM06. A ring containing a corrupted or adversarial key admits signatures by its owner, and a signing query returns a valid signature, which is why both are excluded.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{uf}}_{\Pi,\calA}(\secpar, n)$}
\begin{algorithmic}
\For{$i \in [n]$}
\State $\omega_i \getsr \bits^*$; $(\pk_i, \sk_i) \gets \KeyGen(1^\secpar; \omega_i)$
\EndFor
\State $S \gets (\pk_1, \ldots, \pk_n)$; $C \gets \{\}$; $\calQ \gets \{\}$
\State $(m^*, R^*, \sigma^*) \gets \calA^{\calO_{\Sign}, \calO_{\mathrm{Corr}}}(1^\secpar, S)$
\If{$R^* \not\subseteq \{\pk_i : i \in [n] \setminus C\}$ or $(m^*, R^*) \in \calQ$}
\Comment{$R^*$ holds only uncorrupted honest keys; $(m^*, R^*)$ never queried}
\Return $0$
\EndIf
\Return $[\Vrfy(R^*, m^*, \sigma^*)]$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\Sign}(i, m, R)$}
\begin{algorithmic}
\If{$\pk_i \notin R$}
\Return $\bot$
\EndIf
\State $\calQ \gets \calQ \cup \{(m, R)\}$
\Return $\Sign(\sk_i, m, R)$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\mathrm{Corr}}(i)$}
\begin{algorithmic}
\State $C \gets C \cup \{i\}$
\Return $\omega_i$
\end{algorithmic}
\end{algorithm}

A ring signature scheme is unforgeable with respect to insider corruption if for every polynomial and all efficient ,

is negligible.

These are the strongest anonymity and unforgeability notions of BKM06, who prove them strictly stronger than the notions used before. As an object, ring signatures denote correct schemes, with negligible , that are anonymous against full key exposure and unforgeable with respect to insider corruption.

Variations

Weaker unforgeability

Chosen-subring unforgeability

The unforgeability game without the corruption oracle, in which every ring, in a signing query or in the forgery, consists of honest users’ keys — BKM06.

Fixed-ring unforgeability

The unforgeability game without the corruption oracle, in which every ring, in a signing query or in the forgery, is the list of all honest keys, and the forgery must be on a message never submitted for signing — BKM06. As an object, ring signatures with fixed-ring unforgeability denote correct schemes, with negligible , that are anonymous against full key exposure and unforgeable against fixed-ring attacks.

Linkable ring signatures

A linkable ring signature scheme has a further public algorithm that decides whether two signatures with respect to the same ring were produced by the same member, while still hiding which member it is — LWW04.

Other results

  • Trapdoor permutations over bit strings give ring signatures with fixed-ring unforgeability when a symmetric cipher is modeled as an ideal cipher and a hash function as a random oracle; signer ambiguity is unconditional, and each ring member costs one evaluation of a permutation and one cipher call (TDP over bit strings ⇒ Ring signatures with fixed-ring unforgeability) — RST01. The construction paradigm is secure in the random-oracle model, without an ideal cipher — BSS02.
  • Without random oracles and without setup, ring signatures that are anonymous against full key exposure and unforgeable with respect to insider corruption exist under generic assumptions, among them a semantically secure PKE scheme, a signature scheme and a zap for — BKM06.
  • For rings of two users, a more efficient scheme without random oracles, based on Waters signatures, is unforgeable against chosen-subring attacks and unconditionally anonymous against full key exposure — BKM06.

Participates in

Builds on Ring signature

Produces Ring signature