Ring signature

The original paper describes an RSA based ring signature scheme, as well as one based on Rabin signatures. They define a keyed "combining function" ${\displaystyle C_{k,v}(y_{1},y_{2},\dots ,y_{n})}$ which takes a key ${\displaystyle k}$, an initialization value ${\displaystyle v}$, and a list of arbitrary values ${\displaystyle y_{1},\dots y_{n}}$. It outputs a single value ${\displaystyle z}$. The equation ${\displaystyle C_{k,v}(y_{1},y_{2},\dots ,y_{n})}$ is solvable for any single input, but it is infeasible to solve ${\displaystyle C_{k,v}(g_{1}(x_{1}),g_{2}(x_{2}),\dots ,g_{n}(x_{n}))}$ for ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$ if the adversary cannot invert any of the (here RSA-based) trap-door functions ${\displaystyle g_{1},g_{2},\dots ,g_{n}}$. The function ${\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 symmetric encryption function ${\displaystyle E_{k}}$:

${\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 )))=v}$

In the ring signature scheme, the output ${\displaystyle v}$ is the same as the input. This function is trivially invertible given ${\displaystyle n-1}$ parameters.

Generating a ring signature involves six steps. The plaintext is signified by ${\displaystyle m}$, the ring's public keys by ${\displaystyle P_{1},P_{2},\dots ,P_{n}}$.

1. Calculate the key ${\displaystyle k={\mathcal {H}}(m)}$, using a cryptographic hash function. This step assumes a random oracle for ${\displaystyle {\mathcal {H}}}$, since ${\displaystyle k}$ will be used as key for ${\displaystyle E_{k}}$.
2. Pick a random glue value ${\displaystyle v}$.
3. Pick random ${\displaystyle x_{i}}$ for all ring members but yourself (${\displaystyle x_{s}}$ will be calculated using the signer's private key), and calculate corresponding ${\displaystyle y_{i}=g_{i}(x_{i})}$.
4. Solve the ring equation for ${\displaystyle y_{s}}$
5. Calculate ${\displaystyle x_{s}}$ using the signer's private key: ${\displaystyle x_{s}=g_{s}^{-1}(y_{s})}$
6. The ring signature now is the ${\displaystyle (2n+1)}$-tuple ${\displaystyle (P_{1},P_{2},\dots ,P_{n};v;x_{1},x_{2},\dots ,x_{n})}$

Signature verification involves three steps.

1. Apply the public key trap door on all ${\displaystyle x_{i}}$: ${\displaystyle y_{i}=g_{i}(x_{i})}$.
2. Calculate the symmetric key ${\displaystyle k={\mathcal {H}}(m)}$.
3. Verify that the ring equation holds ${\displaystyle C_{k,v}(y_{1},y_{2},\dots ,y_{n})=v}$.

Here is a Python implementation of the original paper using RSA.

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

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(self, m: str, z: int):
        """Sign a message."""
        self._permut(m)
        s = [None] * self.n
        u = random.randint(0, self.q)
        c = v = self._E(u)
        for i in range(z + 1, self.n) + range(z):
            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(self, m: str, X) -> bool:
        """Verify a message."""
        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))
        def _g(x, i):
            return self._E(x ^ y[i])
        r = reduce(_g, range(self.n), X[0])
        return r == X[0]

    def _permut(self, m):
        self.p = int(hashlib.sha1("%s" % m).hexdigest(), 16)

    def _E(self, x):
        msg = "%s%s" % (x, self.p)
        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))
r = Ring(key)
for i in range(size):
    s1 = r.sign(msg1, i)
    s2 = r.sign(msg2, i)
    assert r.verify(msg1, s1) and r.verify(msg2, s2) and not r.verify(msg1, s2)

The cryptocurrency ShadowCash uses traceable ring signature to anonymize the sender of a transaction.[9] However, these were originally implemented incorrectly, resulting in a partial de-anonymization of ShadowCash from their first implementation until February 2016 by Monero Research Labs researcher, Shen Noether.[10] Luckily only 20% of all the one-time keys in the system were affected by this bug, sender anonymity was compromised but receiver anonymity remained intact. A patch was submitted in a timely fashion to resolve the bug.[11]

Between January 10, 2017 and October 18, 2018, Monero used Ring Confidential Transaction technology to obfuscate transaction amounts on the blockchain. This allowed only the sender and recipient of the funds to know the true quantity being sent.[12] The currency has since switched to Bulletproofs.[13]