Ring signature
Encyclopedia
In cryptography
, a ring signature is a type of digital signature
that can be performed by any member of a group of users that each have keys
. Therefore, a message signed with a ring signature is endorsed by someone in a particular group of people. One of the security properties of a ring signature is that it should be difficult to determine which of the group members' keys was used to produce the signature. Ring signatures are similar to group signature
s but differ in two key ways: first, there is no way to revoke the anonymity of an individual signature, and second, any group of users can be used as a group without additional setup.
Ring signatures were invented by Ron Rivest
, Adi Shamir
, and Yael Tauman, and introduced at ASIACRYPT
in 2001. The name "ring signature" comes from the ring-like structure of the signature algorithm
.
official", without revealing which official signed the message. Ring signatures are right for this application because the anonymity of a ring signature cannot be revoked, and because the group for a ring signature can be improvised.
Another application, also described in the original paper, is for deniable signatures. A ring signature where the group is the sender and the recipient of a message will only seem to be a signature of the sender to the recipient: anyone else will be unsure whether the recipient or the sender was the actual signer. Thus, such a signature is convincing, but cannot be transferred beyond its intended recipient.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, a ring signature is a type of digital signature
Digital signature
A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit...
that can be performed by any member of a group of users that each have keys
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
. Therefore, a message signed with a ring signature is endorsed by someone in a particular group of people. One of the security properties of a ring signature is that it should be difficult to determine which of the group members' keys was used to produce the signature. Ring signatures are similar to group signature
Group signature
A Group signature scheme is a method for allowing a member of a group to anonymously sign a message on behalf of the group. The concept was first introduced by David Chaum and Eugene van Heyst in 1991...
s but differ in two key ways: first, there is no way to revoke the anonymity of an individual signature, and second, any group of users can be used as a group without additional setup.
Ring signatures were invented by Ron Rivest
Ron Rivest
Ronald Linn Rivest is a cryptographer. He is the Andrew and Erna Viterbi Professor of Computer Science at MIT's Department of Electrical Engineering and Computer Science and a member of MIT's Computer Science and Artificial Intelligence Laboratory...
, Adi Shamir
Adi Shamir
Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
, and Yael Tauman, and introduced at ASIACRYPT
Asiacrypt
Asiacrypt is an important international conference for cryptography research. The full name of the conference is currently International Conference on the Theory and Application of Cryptology and Information Security, though this has varied over time...
in 2001. The name "ring signature" comes from the ring-like structure of the signature algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
.
Definition
Suppose that a group of entities each have public/private key pairs, (PK1, SK1), (PK2, SK2), ... ,(PKn, SKn). Party i can compute a ring signature σ on a message m, on input (m, SKi, PK1, ... , PKn). Anyone can check the validity of a ring signature given σ, m, and the public keys involved, PK1, ... , PKn. 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 group without knowing any of the secret keys for that group.Applications
In the original paper, Rivest, Shamir, and Tauman described ring signatures as a way to leak a secret. For instance, a ring signature could be used to provide an anonymous signature from "a high-ranking White HouseWhite House
The White House is the official residence and principal workplace of the president of the United States. Located at 1600 Pennsylvania Avenue NW in Washington, D.C., the house was designed by Irish-born James Hoban, and built between 1792 and 1800 of white-painted Aquia sandstone in the Neoclassical...
official", without revealing which official signed the message. Ring signatures are right for this application because the anonymity of a ring signature cannot be revoked, and because the group for a ring signature can be improvised.
Another application, also described in the original paper, is for deniable signatures. A ring signature where the group is the sender and the recipient of a message will only seem to be a signature of the sender to the recipient: anyone else will be unsure whether the recipient or the sender was the actual signer. Thus, such a signature is convincing, but cannot be transferred beyond its intended recipient.