Ring signature

<h2 id="definition">Definition</h2>

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.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

<h2 id="applications-and-modifications">Applications and modifications</h2>

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 <a href="/facts/White_House/CJQc7dKF">White House</a> 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. Here the sender and the recipient of a message form a group for the ring signature, then the signature is valid to the recipient, but 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.
There were various works, introducing new features and based on different assumptions:

Threshold ring signatures
<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> Unlike standard "t-out-of-n" <a href="/facts/Threshold_cryptosystem/4KKvNxW8">threshold signature</a>, where t of n users should collaborate to sign a message, this variant of a ring signature requires t users to cooperate in the ring signing <a href="/facts/Cryptographic_protocol/0WuyTkFo">protocol</a>. Namely, t parties S1, ..., St ∈ {P1, ..., Pn} can compute a (t, n)-ring signature, σ, on a message, m, on input (m, S1, ..., St, P1, ..., Pn).
Linkable ring signatures
<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> The property of linkability allows one to determine whether any two signatures have been produced by the same member (under the same private key). The identity of the signer is nevertheless preserved. One of the possible applications can be an offline <a href="/facts/E-cash/ycholMaA">e-cash system</a>.
Traceable ring signature
<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> In addition to the previous scheme the public key of the signer is revealed (if they issue more than one signatures under the same private key). An <a href="/facts/E-voting/jsI9Ngwr">e-voting system</a> can be implemented using this protocol.
<h2 id="efficiency">Efficiency</h2>
Most of the proposed algorithms have <a href="/facts/Big_O_notation/weFFjSWg">asymptotic</a> output size 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
; 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 
 
 
 
 n
 
 
 {\displaystyle n}
 
 (for example, an e-voting with millions of participants). But for some application with relatively small <a href="/facts/Median/YwXGWTyr">median</a> input size such estimate may be acceptable. <a href="/facts/CryptoNote/tK691ht0">CryptoNote</a> implements 
 
 
 
 O
 (
 n
 )
 
 
 {\displaystyle O(n)}
 
 ring signature scheme by Fujisaki and Suzuki<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> in p2p payments to achieve sender's untraceability.
More efficient algorithms have appeared recently. There are schemes with the sublinear size of the signature,<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> as well as with constant size.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="implementation">Implementation</h2>
<h3>Original scheme</h3>
The original paper describes an <a href="/facts/Rivest_Shamir_Adleman/XTzyfHuq">RSA</a> based ring signature scheme, as well as one based on <a href="/facts/Rabin_cryptosystem/Q7MRkmdo">Rabin signatures</a>. They define a <a href="/facts/Key_(cryptography)/5W5PAmT4">keyed</a> "combining function" 
 
 
 
 
 C
 
 k
 ,
 v
 
 
 (
 
 y
 
 1
 
 
 ,
 
 y
 
 2
 
 
 ,
 …
 ,
 
 y
 
 n
 
 
 )
 
 
 {\displaystyle C_{k,v}(y_{1},y_{2},\dots ,y_{n})}
 
 which takes a key 
 
 
 
 k
 
 
 {\displaystyle k}
 
, an initialization value 
 
 
 
 v
 
 
 {\displaystyle v}
 
, and a list of arbitrary values 
 
 
 
 
 y
 
 1
 
 
 ,
 …
 
 y
 
 n
 
 
 
 
 {\displaystyle y_{1},\dots y_{n}}
 
. 
 
 
 
 
 y
 
 i
 
 
 
 
 {\displaystyle y_{i}}
 
 is defined as 
 
 
 
 
 g
 
 i
 
 
 (
 
 x
 
 i
 
 
 )
 
 
 {\displaystyle g_{i}(x_{i})}
 
, where 
 
 
 
 
 g
 
 i
 
 
 
 
 {\displaystyle g_{i}}
 
 is a trap-door function (i.e. an RSA public key in the case of RSA based ring signatures).
The function 
 
 
 
 
 C
 
 k
 ,
 v
 
 
 (
 
 y
 
 1
 
 
 ,
 
 y
 
 2
 
 
 ,
 …
 ,
 
 y
 
 n
 
 
 )
 
 
 {\displaystyle C_{k,v}(y_{1},y_{2},\dots ,y_{n})}
 
 is called the ring equation, and is defined below. The equation is based on a <a href="/facts/Symmetric-key_algorithm/5zfe0b76">symmetric encryption function</a> 
 
 
 
 
 E
 
 k
 
 
 
 
 {\displaystyle E_{k}}
 
:

C
          
            k
            ,
            v
          
        
        (
        
          y
          
            1
          
        
        ,
        
          y
          
            2
          
        
        ,
        …
        ,
        
          y
          
            n
          
        
        )
        =
        
          E
          
            k
          
        
        (
        
          y
          
            n
          
        
        ⊕
        
          E
          
            k
          
        
        (
        
          y
          
            n
            −
            1
          
        
        ⊕
        
          E
          
            k
          
        
        (
        ⋯
        ⊕
        
          E
          
            k
          
        
        (
        
          y
          
            1
          
        
        ⊕
        v
        )
        …
        )
        )
        )
      
    
    {\displaystyle C_{k,v}(y_{1},y_{2},\dots ,y_{n})=E_{k}(y_{n}\oplus E_{k}(y_{n-1}\oplus E_{k}(\dots \oplus E_{k}(y_{1}\oplus v)\dots )))}

It outputs a single value 
 
 
 
 z
 
 
 {\displaystyle z}
 
 which is forced to be equal to 
 
 
 
 v
 
 
 {\displaystyle v}
 
. The equation 
 
 
 
 v
 =
 
 C
 
 k
 ,
 v
 
 
 (
 
 y
 
 1
 
 
 ,
 
 y
 
 2
 
 
 ,
 …
 ,
 
 y
 
 n
 
 
 )
 
 
 {\displaystyle v=C_{k,v}(y_{1},y_{2},\dots ,y_{n})}

can be solved as long as at least one 
 
 
 
 
 y
 
 i
 
 
 
 
 {\displaystyle y_{i}}
 
, and by extension 
 
 
 
 
 x
 
 i
 
 
 
 
 {\displaystyle x_{i}}
 
, can be freely chosen. Under the assumptions of RSA, this implies knowledge of at least one of the inverses of the trap door functions 
 
 
 
 
 g
 
 i
 
 
 −
 1
 
 
 
 
 {\displaystyle g_{i}^{-1}}
 
 (i.e. a private key), since 
 
 
 
 
 g
 
 i
 
 
 −
 1
 
 
 (
 
 y
 
 i
 
 
 )
 =
 
 x
 
 i
 
 
 
 
 {\displaystyle g_{i}^{-1}(y_{i})=x_{i}}
 
.

<h4>Signature generation</h4>
Generating a ring signature involves six steps. The plaintext is signified by 
 
 
 
 m
 
 
 {\displaystyle m}
 
, the ring's public keys by 
 
 
 
 
 P
 
 1
 
 
 ,
 
 P
 
 2
 
 
 ,
 …
 ,
 
 P
 
 n
 
 
 
 
 {\displaystyle P_{1},P_{2},\dots ,P_{n}}
 
.

<ol><li>Calculate the key 
 
 
 
 k
 =
 
 
 H
 
 
 (
 m
 )
 
 
 {\displaystyle k={\mathcal {H}}(m)}
 
, using a <a href="/facts/Cryptographic_hash_function/cuxkgbST">cryptographic hash function</a>. This step assumes a <a href="/facts/Random_oracle/wK7MhxDq">random oracle</a> for 
 
 
 
 
 
 H
 
 
 
 
 {\displaystyle {\mathcal {H}}}
 
, since 
 
 
 
 k
 
 
 {\displaystyle k}
 
 will be used as key for 
 
 
 
 
 E
 
 k
 
 
 
 
 {\displaystyle E_{k}}
 
.</li>
<li>Pick a random glue value 
 
 
 
 v
 
 
 {\displaystyle v}
 
.</li>
<li>Pick random 
 
 
 
 
 x
 
 i
 
 
 
 
 {\displaystyle x_{i}}
 
 for all ring members but yourself (
 
 
 
 
 x
 
 s
 
 
 
 
 {\displaystyle x_{s}}
 
 will be calculated using the signer's private key), and calculate corresponding 
 
 
 
 
 y
 
 i
 
 
 =
 
 g
 
 i
 
 
 (
 
 x
 
 i
 
 
 )
 
 
 {\displaystyle y_{i}=g_{i}(x_{i})}
 
.</li>
<li>Solve the ring equation for 
 
 
 
 
 y
 
 s
 
 
 
 
 {\displaystyle y_{s}}
 
</li>
<li>Calculate 
 
 
 
 
 x
 
 s
 
 
 
 
 {\displaystyle x_{s}}
 
 using the signer's private key: 
 
 
 
 
 x
 
 s
 
 
 =
 
 g
 
 s
 
 
 −
 1
 
 
 (
 
 y
 
 s
 
 
 )
 
 
 {\displaystyle x_{s}=g_{s}^{-1}(y_{s})}
 
</li>
<li>The ring signature now is the 
 
 
 
 (
 2
 n
 +
 1
 )
 
 
 {\displaystyle (2n+1)}
 
-tuple 
 
 
 
 (
 
 P
 
 1
 
 
 ,
 
 P
 
 2
 
 
 ,
 …
 ,
 
 P
 
 n
 
 
 ;
 v
 ;
 
 x
 
 1
 
 
 ,
 
 x
 
 2
 
 
 ,
 …
 ,
 
 x
 
 n
 
 
 )
 
 
 {\displaystyle (P_{1},P_{2},\dots ,P_{n};v;x_{1},x_{2},\dots ,x_{n})}
 
</li></ol>
<h4>Signature verification</h4>
Signature verification involves three steps.

<ol><li>Apply the public key trap door on all 
 
 
 
 
 x
 
 i
 
 
 
 
 {\displaystyle x_{i}}
 
: 
 
 
 
 
 y
 
 i
 
 
 =
 
 g
 
 i
 
 
 (
 
 x
 
 i
 
 
 )
 
 
 {\displaystyle y_{i}=g_{i}(x_{i})}
 
.</li>
<li>Calculate the symmetric key 
 
 
 
 k
 =
 
 
 H
 
 
 (
 m
 )
 
 
 {\displaystyle k={\mathcal {H}}(m)}
 
.</li>
<li>Verify that the ring equation holds 
 
 
 
 
 C
 
 k
 ,
 v
 
 
 (
 
 y
 
 1
 
 
 ,
 
 y
 
 2
 
 
 ,
 …
 ,
 
 y
 
 n
 
 
 )
 =
 v
 
 
 {\displaystyle C_{k,v}(y_{1},y_{2},\dots ,y_{n})=v}
 
.</li></ol>
<h4>Python implementation</h4>
Here is a <a href="/facts/Python_(language)/YbuGqofa">Python</a> implementation of the original paper using <a href="/facts/Rivest_Shamir_Adleman/XTzyfHuq">RSA</a>. Requires 3rd-party module PyCryptodome.

import os
import hashlib
import random
import Crypto.PublicKey.RSA

import functools

class Ring:
    """RSA implementation."""

def __init__(self, k, L: int = 1024) -> None:
 self.k = k
 self.l = L
 self.n = len(k)
 self.q = 1 << (L - 1)

def sign_message(self, m: str, z: int):
        self._permut(m)
        s = [None] * self.n
        u = random.randint(0, self.q)
        c = v = self._E(u)

first_range = list(range(z + 1, self.n))
        second_range = list(range(z))
        whole_range = first_range + second_range

for i in whole_range:
            s[i] = random.randint(0, self.q)
            e = self._g(s[i], self.k[i].e, self.k[i].n)
            v = self._E(v ^ e)
            if (i + 1) % self.n == 0:
                c = v

s[z] = self._g(v ^ u, self.k[z].d, self.k[z].n)
        return [c] + s

def verify_message(self, m: str, X) -> bool:
        self._permut(m)

def _f(i):
            return self._g(X[i + 1], self.k[i].e, self.k[i].n)

y = map(_f, range(len(X) - 1))
        y = list(y)

def _g(x, i):
            return self._E(x ^ y[i])

r = functools.reduce(_g, range(self.n), X[0])
        return r == X[0]

def _permut(self, m):
        msg = m.encode("utf-8")
        self.p = int(hashlib.sha1(msg).hexdigest(), 16)

def _E(self, x):
        msg = f"{x}{self.p}".encode("utf-8")
        return int(hashlib.sha1(msg).hexdigest(), 16)

def _g(self, x, e, n):
 q, r = divmod(x, n)
 if ((q + 1) * n) <= ((1 << self.l) - 1):
 result = q * n + pow(r, e, n)
 else:
 result = x
 return result

To sign and verify 2 messages in a ring of 4 users:

size = 4
msg1, msg2 = "hello", "world!"

def _rn(_):
    return Crypto.PublicKey.RSA.generate(1024, os.urandom)

key = map(_rn, range(size))
key = list(key)

r = Ring(key)

for i in range(size):
    signature_1 = r.sign_message(msg1, i)
    signature_2 = r.sign_message(msg2, i)
    assert r.verify_message(msg1, signature_1) and r.verify_message(msg2, signature_2) and not r.verify_message(msg1, signature_2)

<h2 id="cryptocurrencies">Cryptocurrencies</h2>
<a href="/facts/Monero/KAQXR18X">Monero</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> and several other <a href="/facts/Cryptocurrency/Rg6JAS8y">cryptocurrencies</a> use this technology.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Witness-indistinguishable_proof/zu40pChJ">Witness-indistinguishable proofs</a></li></ul>

This article incorporates <a href="https://www.getmonero.org/resources/moneropedia/ringsignatures.html">text</a> available under the CC BY-SA 4.0 license.

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Rivest, Ronald L.; Shamir, Adi; Tauman, Yael (2001). "How to Leak a Secret". Advances in Cryptology — ASIACRYPT 2001. Lecture Notes in Computer Science. Vol. 2248. pp. 552–565. doi:10.1007/3-540-45682-1_32. ISBN 978-3-540-42987-6. <a href="978-3-540-42987-6" target="_blank">978-3-540-42987-6</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Debnath, Ashmita; Singaravelu, Pradheepkumar; Verma, Shekhar (19 December 2012). "Efficient spatial privacy preserving scheme for sensor network". Central European Journal of Engineering. 3 (1): 1–10. doi:10.2478/s13531-012-0048-7. S2CID 137248994. <a href="https://doi.org/10.2478%2Fs13531-012-0048-7" target="_blank">https://doi.org/10.2478%2Fs13531-012-0048-7</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">E. Bresson; J. Stern; M. Szyd lo (2002). "Threshold Ring Signatures and Applications to Ad-hoc Groups" (PDF). Advances in Cryptology — CRYPTO 2002. Lecture Notes in Computer Science. Vol. 2442. pp. 465–480. doi:10.1007/3-540-45708-9_30. ISBN 978-3-540-44050-5. <a href="978-3-540-44050-5" target="_blank">978-3-540-44050-5</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Liu, Joseph K.; Wong, Duncan S. (2005). "Linkable Ring Signatures: Security Models and New Schemes". Computational Science and Its Applications – ICCSA 2005. Lecture Notes in Computer Science. Vol. 2. pp. 614–623. doi:10.1007/11424826_65. ISBN 978-3-540-25861-2. {{cite book}}: |journal= ignored (help) <a href="978-3-540-25861-2" target="_blank">978-3-540-25861-2</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Fujisaki, Eiichiro; Suzuki, Koutarou (2007). "Traceable Ring Signature". Public Key Cryptography: 181–200. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Fujisaki, Eiichiro; Suzuki, Koutarou (2007). "Traceable Ring Signature". Public Key Cryptography: 181–200. <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Fujisaki, Eiichiro (2011). "Sub-linear size traceable ring signatures without random oracles". IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 95 (1): 393–415. Bibcode:2012IEITF..95..151F. doi:10.1587/transfun.E95.A.151. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Au, Man Ho; Liu, Joseph K.; Susilo, Willy; Yuen, Tsz Hon (2006). "Constant-Size ID-Based Linkable and Revocable-iff-Linked Ring Signature". Progress in Cryptology - INDOCRYPT 2006. Lecture Notes in Computer Science. Vol. 4329. pp. 364–378. doi:10.1007/11941378_26. ISBN 978-3-540-49767-7. <a href="978-3-540-49767-7" target="_blank">978-3-540-49767-7</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">"Evaluation of Bulletproof Implementation" (PDF). Quarkslab. <a href="https://ostif.org/wp-content/uploads/2018/10/OSTIF-QuarksLab-Monero-Bulletproofs-Final2.pdf" target="_blank">https://ostif.org/wp-content/uploads/2018/10/OSTIF-QuarksLab-Monero-Bulletproofs-Final2.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
</ol>

Ring signature open-in-new

Ring signature