Rivest's ring signatures with hashes instead of symmetric encryption

While studying ring signatures, I obviously stumbled on the Wikipedia article about ring signatures. It includes a piece of Python code to demonstrate "How to leak a secret" ring signatures.

Remarkably, they do not use a symmetric encryption function ($E_k$, as in "How to leak a secret"), but a hash function ($\mathcal{H}$). Indeed, the encryption function does not need to be invertible, if we close the ring of the signature at the very last (take $v^\prime$ random, $m$ is the hashed plaintext):

\begin{align*} \mathcal{H'}(x) &= \mathcal{H}(x\mathbin\Vert m)\\ v&=\mathcal{H'}(y_{r} \oplus \mathcal{H'}(y_{r-1} \oplus \mathcal{H'}(\ldots\oplus \mathcal{H'}(v'))))\quad r-s\enspace\text{times}\\ h&=\mathcal{H'}(y_{s-1} \oplus \mathcal{H'}(y_{s-2} \oplus \mathcal{H'}(\ldots\oplus \mathcal{H'}(y_1 \oplus v)))) \end{align*}

now notice that $$v'=y_s \oplus h \quad\Leftrightarrow\quad y_s=v'\oplus h\\ x_s=g_s^{-1}(y_s)$$

which "closes" the ring.

What are the security implications here? I can't seem to find literature describing this substitution.

• Why would it? It looks to me like this can work. – Ruben De Smet Oct 31 '17 at 10:18
• I see . My bad. – Occams_Trimmer Oct 31 '17 at 10:41

There are two immediate implications.

Now, does it break in practical terms? Not obviously, but our confidence in the security of the ring signature scheme cannot be understood entirely by studying the security of the underlying ordinary signature scheme—there may be an attack against the ring signature scheme even if the underlying ordinary signature scheme is secure, so there are more targets for cryptanalysis, meaning you can't save work by focusing on one primitive.

The two implications are for two different security properties:

1. Anonymity of the signer.

The Rivest–Shamir–Tauman scheme guarantees the anonymity of the signer even against an adversary of unbounded computational capacity without even relying on $h$ to be a random oracle. The proof of this depends on the invertibility of everything involved so that there's a pigeon in every hole and exactly one pigeon to each hole: for every $k$ and $v$, there are exactly $(2^b)^{r - 1}$ possible values of $(y_1, y_2, \dots, y_r)$ satisfying the ring signature equation, all equiprobable if the $x_i$ are drawn uniformly at random.

If you replace the PRP $E_k$ by a PRF $H_k$, then this proof no longer holes: the distribution on solutions may be nonuniform. Is it so nonuniform you could unmask the dirty traitor and prosecute them under the Espionage Act and pillory them on Fox News? Maybe, maybe not (although you could doubtless find someone else to pillory on Fox News, such as a nonbinary vulture just trying to use the bathroom, and ratings would go up just the same).

2. Reduction of security of ring signatures to security of underlying ordinary signatures against forgery.

The proof demonstrates how to build an algorithm to forge ordinary signatures given an algorithm to forge ring signatures. The algorithm again relies on the reversibility of the encryption function, but it's got more details than I can fit in this feathery head today, so I can't say whether you could adapt the reduction (maybe with a wider tightness gap) to work with the hashing version.

Of course, as you may have observed, $2^b$ must be larger than all the moduli, and there aren't all that many 2048-bit block ciphers lying around. (1024-bit, yes: Threefish. But you also don't want to rely on RSA-1024.) So in practical terms, you don't want to use this scheme anyway! Fortunately, there is a pretty substantial literature on ring signature schemes in the past fifteen years since the RST paper came out. I leave it as an exercise for the reader to study newer developments in ring signatures.

I couldn't find the origin of the exact implementation given in the Python code, but the earliest paper I could find that uses hashes instead of encryption, and "closes the ring" is "1-out-of-n Signatures from a Variety of Keys" by Abe, Ohkubo and Suzuki. It's a technique that's become relatively common, since it's easier to apply to elliptic curve based schemes than the original symmetric cipher approach.

There doesn't look to be anything obviously wrong with the implementation given. It seems like it should work, if $g_i$ is RSA encryption, $g_s^{-1}$ is RSA decryption, and $y_i = g_i(x_i)$ for all $i$ except $s$. However you would be better off using a well-studied implementation.