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.[1] The name, ring signature, comes from the ring-like structure of the signature algorithm.

Definition

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.[2]

Applications and modifications

Behaviour of the Rivest, Shamir, Tauman ring signature scheme

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 House 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
[3] Unlike standard "t-out-of-n" threshold signature, where t of n users should collaborate to decrypt a message, this variant of a ring signature requires t users to cooperate in the signing protocol. Namely, t parties (i1, i2, ..., it) can compute a (t, n)-ring signature, σ, on a message, m, on input (m, Si1, Si2, ..., Sit, P1, ..., Pn).
Linkable ring signatures
[4] 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 e-cash system.
Traceable ring signature
[5] 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 e-voting system can be implemented using this protocol.

Efficiency

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[5] in p2p payments to achieve sender's untraceability.

More efficient algorithms have appeared recently. There are schemes with the sublinear size of the signature,[6] as well as with constant size.[7]

Implementation

Original scheme

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 . It outputs a single value . The equation is solvable for any single input, but it is infeasible to solve for if the adversary cannot invert any of the (here RSA-based) trap-door functions . The function is called the ring equation, and is defined below. The equation is based on a symmetric encryption function :

In the ring signature scheme, the output is the same as the input. This function is trivially invertible given parameters.

Signature generation

Generating a ring signature involves six steps. The plaintext is signified by , the ring's public keys by .

  1. Calculate the key , using a cryptographic hash function. This step assumes a random oracle for , since will be used as key for .
  2. Pick a random glue value .
  3. Pick random for all ring members but yourself ( will be calculated using the signer's private key), and calculate corresponding .
  4. Solve the ring equation for
  5. Calculate using the signer's private key:
  6. The ring signature now is the -tuple

Signature verification

Signature verification involves three steps.

  1. Apply the public key trap door on all : .
  2. Calculate the symmetric key .
  3. Verify that the ring equation holds .

Python implementation

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)

Cryptocurrencies

The CryptoNote technology uses ring signatures.[8] It was first implemented by Bytecoin.

ShadowCash

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]

Monero

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]

References

  1. How to leak a secret, Ron Rivest, Adi Shamir, and Yael Tauman Kalai, ASIACRYPT 2001. Volume 2248 of Lecture Notes in Computer Science, pages 552–565.
  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.
  3. E. Bresson; J. Stern; M. Szyd lo (2002). "Threshold ring signatures and applications to ad-hocgroups" (PDF). Advances in Cryptology: Crypto 2002. Lecture Notes in Computer Science. 2442: 465–480. doi:10.1007/3-540-45708-9_30. ISBN 978-3-540-44050-5.
  4. Liu, Joseph K.; Wong, Duncan S. (2005). Linkable ring signatures: Security models and new schemes. ICCSA. Lecture Notes in Computer Science. 2. pp. 614–623. doi:10.1007/11424826_65. ISBN 978-3-540-25861-2.
  5. Fujisaki, Eiichiro; Suzuki, Koutarou (2007). "Traceable Ring Signature". Public Key Cryptography: 181–200.
  6. Fujisaki, Eiichiro (2011). "Sub-linear size traceable ring signatures without random oracles". CTRSA. 95 (1): 393–415. Bibcode:2012IEITF..95..151F. doi:10.1587/transfun.E95.A.151.
  7. Au, Man Ho; Liu, Joseph K.; Susilo, Willy; Yuen, Tsz Hon (2006). Constant-Size ID-Based Linkable and Revocable-iff-Linked Ring Signature. Lecture Notes in Computer Science. 4329. pp. 364–378. doi:10.1007/11941378_26. ISBN 978-3-540-49767-7.
  8. CryptoNote Technology - Untraceable payments
  9. Shadow - Zero-knowledge Anonymous Distributed Electronic Cash via Traceable Ring Signatures
  10. Broken Crypto in Shadowcash Archived 2016-09-27 at the Wayback Machine
  11. https://blog.shadowproject.io/2016/03/07/development-update-march-phoenix/
  12. "A low-level explanation of the mechanics of Monero vs Bitcoin in plain English".
  13. Bunz, Benedikt (November 1, 2017). "Bulletproofs: Short Proofs for Confidential Transactions and More". iarc.org. Retrieved February 14, 2019.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.