On The Impossibility of Providing Strong Anonymity in Blockchains via Linkable Ring Signatures

Abstract

Anonymity is a necessary property for a ring signature scheme and also its variant such as linkable ring signature and traceable ring signature schemes, which are especially useful in blockchains. Intuitively, those variants were designed for detecting or seeking the dishonest signatory, however, at the cost of reducing the anonymity of a traditional ring signature. As a result, while various constructions of strongly anonymous ring signatures were well-known, a linkable ring signature scheme with the same property was an open problem for a long time.
In this work, we launched a so-called denying attack to show the gap between an arbitrary ring signature and linkable ring signature transparently, which further confirmed the widely believed impossibility in building a linkable ring signature with both strong anonymity and strong linkability.
For a concrete instance, we also applied this attack to the scheme in IEEE TKDE, which to the best of our knowledge is the unique linkable ring signature both with strong anonymity and strong linkability so far.
The concrete attack is easily launched in blockchain so that it shows the impossibility of providing strong anonymity via linkable ring signature for blockchain applications, since strong likability is indispensable.