Ring signatures and their applications

From CryptoWiki
Jump to: navigation, search

Ring signature - digital signature which allows a member of some group (named ring) to sign some message in an anonymous way, which means that no one (except actual signer) knows which member signed the message.

Contents

Security challenge

Unlike group signature schemes, ring signature scheme have no managers (since rings are geometric regions with uniform periphery and no center [RST01]). In a ring signature scheme there are no prearranged groups of users, there are no procedures for setting, changing, or deleting groups, there is no way to distribute specialized keys, and there is no way to revoke the anonymity of the actual signer (unless he decides to expose himself). Only assumption is that each member is already associated with the public key of some standard signature scheme such as RSA. To produce a ring signature, the actual signer declares an arbitrary set of possible signers that includes himself, and computes the signature entirely by himself using only his secret key and the others’ public keys. (Figure 1).

RingSign1.png
Figure 1 - Ring signature scheme with As member as actual signer

So ring signature scheme may be useful if it is necessary to provide signer's anonimity and his independence of other members, and thus ensure the integrity and authenticity of signed message.

Theoretical issues

Definitions

Define ring as a group of possible signers and the actual signer. Signer (or actual signer) is a member who wants to sign some message using ring signature. Each possible signer (denote X) is associated with its public key PKx and corresponding private key SKx. There is no special requirements for each member's individual digital signature scheme, but in [RST01] is an example of building ring signature scheme based on trapdoor one-way function (for example, RSA). Ring signature is defined with two procedures:

  • RingSign(M, PK1, PK2,...,PKr, s, SKs) - procedure of computing ring signature Q, which takes message M, public keys of ring members and signer's private key SKs as arguments;
  • RingVerify(M, Q) - procedure of verifying the ring signature Q, which takes message M and ring signature Q as arguments; returns 1 if signature is correct and 0 otherwise.

Requirements

A ring signature scheme is set-up free: The signer does not need the knowledge, consent, or assistance of the other ring members to put them in the ring - all he needs is knowledge of their regular public keys. Different members can use different independent public key signature schemes, with different key and signature sizes. Verification must satisfy the usual soundness and completeness conditions, but in addition we want the signatures to be signer-ambiguous in the sense that the verifier should be unable to determine the identity of the actual signer in a ring of size r with probability greater than 1/r.

Cryptographic issues

Suppose that member As wants to sign message M using ring signature with r members A1, ..., Ar.

Trapdoor one-way function

Each member Ai has its own public key PKi = (ni, ei) which define trapdoor one-way function: RingSign2.png. It is supposed that only Ai member can efficiently compute RingSign3.png, because only he knows private key SKi.

In work [RST01] proposed the use of an extended trapdoor one-way function for each function fi. Function takes b-bit value m as input, for which numbers qi and ri defined as: RingSign5.png, RingSign6.png. Extended trapdoor one-way function gi is defined as:

RingSign4.png

It is obvious that there will be own extended trapdoor one-way function for each member. But one can compute inverse value of function gi only with knowledge of private key SKi.

Symmetric encryption

Let E be symmetric cryptoalgorithm for strings with length b bit. Let Ek be reversible cryptographic transformation which uses the key k.

Hash function

Let h be collision-resistant hash function which converts its input into a string used as a key for Ek and its reverse transformation.

Combining function

Define combining function as follows: RingSign7.png, where k is symmetric encryption key, v is random b-bit value used as initializing vector, yi are input b-bit values. It is required [RST01] that combining function should satisfy the following properties:

  • For any input value with other fixed values combining function is one-to-one mapping of non-fixed input value to the output;
  • Any unknown input value can be effectively found with certain others and a certain output value;
  • It is impossible to find the input values for a known output value and the known parameters k и v.

Combining function supposed in work [RST01] is follows:

RingSign8.png.

If we suppose that RingSign9.png, combining function can be represented as follows:

RingSign10.png
Figure 2 - Supposed combining function

This function can be used for computing and verifying ring signature.

Signature generation

Having message m, own private key SKs and a sequence of ring members public keys, signer As creates ring signature as follows:

  • Computes key k:RingSign11.png
  • Chooses v randomly
  • Chooses random values xi except value which corresponds to own id s and computes values RingSign15.png
  • Finds ys during equation solution RingSign12.png
  • Finds xs knowing value of SKs:RingSign13.png
  • Provides a ring signature as RingSign14.png

Проверка подписи

Having ring signature of m' (and message m too) and a sequence of ring members public keys, verifier can verify ring signature as follows:

  • ДFor each xi computes RingSign15.png
  • Computes k as follows:RingSign11.png
  • Checks correctness of equation RingSign12.png for values yi
  • If equation is correct then signature is considered as correct, otherwise it is considered incorrect

Ring signature applications

Cryptocurrency

Ring signature is used in some cryptocurrencies (based on CryptoNote protocol) for Sender hiding. In such systems, a disposable addresses are used as destination address. Ring signature confirms the right to use one of the possible addresses in the chain, but without some knowledge of exact address.Signed transactions refer to the number of other transactions in the block chain. From the observer's point of view, such a transaction is likely to be used as an input to any of the transactions to which it refers. The greater the number of links to previous transactions included in the ring signature, the greater the uncertainty, and the greater the size of the signature.

Anonymous information sources

Ring signature can be used [AJR05] in the following case: a clerk willing to disclose certain information, while signing on behalf of several of its officials. Thus, the other person will be able to rely on this information and be sure that the source is really official. Thus he will remain anonymous.

The proof of the right of access to a resource

Ring signature can allow [AJR05] take evidence that a member of the user group has access to some resources at the same time without disclosing the identity of the user.

E-mail

Ring signature with ring size of 2 can be used in e-mail [AJR05] to ensure that one user could send a signed message to another, but at the same time another user is not able to subsequently prove who the sender is.

Glossary

Bibliography

Go to bibliography of "Ring signature and its applications".

R. Rezvukhin, 2016