TDP over bit strings ⇒ Ring signatures with fixed-ring unforgeability (Rivest–Shamir–Tauman)
Statement
Let each user’s public key describe a trapdoor permutation over bit strings of a common domain , with the trapdoor as secret key. For a trapdoor permutation on , as with RSA, RST01 obtain such a as for when , with the identity on the remaining points, a negligible fraction of when is super-polynomial in (RSA ⇒ TDP over bit strings) — RST01. Let be a cipher on and a hash function giving . A ring signature on with respect to is such that the values satisfy
The signer picks and every with at random, solves this equation for , and inverts with its trapdoor. The scheme is unconditionally signer-ambiguous, and with modeled as an ideal cipher and as a random oracle it is a ring signature with fixed-ring unforgeability: every efficient forger with non-negligible advantage yields an efficient algorithm that inverts one of the at a uniform point with non-negligible probability — RST01.
Notes
- Verifying costs one cipher call and one evaluation of per ring member; signing costs the same, except that the signer inverts instead of evaluating it — RST01.
- The random oracle is needed: if for , a signature on verifies unchanged on — standard.
- The construction paradigm is secure in the random-oracle model alone, without an ideal cipher — BSS02.