Ring signature

In cryptography, a ring signature is a type of digital signature that can be performed by any member of a set of users that each have keys. Therefore, a message signed with a ring signature is endorsed by someone in a particular set of people. One of the security properties of a ring signature is that it should be computationally infeasible to determine which of the set's members' keys was used to produce the signature. Ring signatures are similar to group signatures but differ in two key ways: first, there is no way to revoke the anonymity of an individual signature; and second, any set of users can be used as a signing set without additional setup. Ring signatures were invented by Ron Rivest, Adi Shamir, and Yael Tauman Kalai, and introduced at ASIACRYPT in 2001. The name, ring signature, comes from the ring like structure of the signature algorithm.

Suppose that a set of entities each have public/private key pairs, (P1, S1), (P2, S2), , (Pn, Sn). Party i can compute a ring signature σ on a message m, on input (m, Si, P1, , Pn). Anyone can check the validity of a ring signature given σ, m, and the public keys involved, P1, , Pn. If a ring signature is properly computed, it should pass the check. On the other hand, it should be hard for anyone to create a valid ring signature on any message for any set without knowing any of the private keys for that set.

Most of the proposed algorithms have asymptotic output size ; i. e., the size of the resulting signature increases linearly with the size of input (number of public keys). That means that such schemes are impracticable for real use cases with sufficiently large (for example, an e voting with millions of participants). But for some application with relatively small median input size such estimate may be acceptable. CryptoNote implements ring signature scheme by Fujisaki and Suzuki as well as with constant size.

The original paper describes an RSA based ring signature scheme, as well as one based on Rabin signatures. They define a keyed "combining function" which takes a key , an initialization value , and a list of arbitrary values is defined as , where is a trap door function (i. e. an RSA public key in the case of RSA based ring signatures). The function is called the ring equation, and is defined below. The equation is based on a symmetric encryption function :

It outputs a single value which is forced to be equal to The equation
can be solved as long as at least one , and by extension , can be freely chosen. Under the assumptions of RSA, this implies knowledge of at least one of the inverses of the trap door functions (i. e. a private key), since .

Signature verification involves three steps. Apply the public key trap door on all : Calculate the symmetric key Verify that the ring equation holds .

Monero and several other cryptocurrencies use this technology.