Are ring signatures possible with elliptic curves? If so how. The original paper by Rivest, Shamir, Tauman seems to require an invertible trapdoor function. But I've only seen algorithms for secret agreement (ECDH for example) with elliptic curves. That doesn't seem to be adequate to complete the ring - don't you need invertibility?

  • $\begingroup$ If you need "only" an invertible trapdoor function, this is very well possible in EC. Otherwise ECDSA and ECIES wouldn't be possible (I guess). $\endgroup$
    – SEJPM
    May 25 '15 at 19:32
  • 1
    $\begingroup$ If you feel "TL;DR" about my above comment: Solving $Q=[d]P$ (for d) is one-way trapdoor if you don't know d. $\endgroup$
    – SEJPM
    May 25 '15 at 19:33
  • $\begingroup$ It's entirely possible that I'm being phenomenally dense here, but that doesn't quite seem to be the same thing as invertible to me. I need to be able to find x for an arbitrary y where $y = f(x)$. And I need doing so to be difficult for anyone who doesn't know the scalar key. That might be implicit in ECDSA but I'm not sure I can see where. $\endgroup$
    – geoff_h
    May 25 '15 at 19:44
  • $\begingroup$ So you mean you need to be able to find $x$ from $y$ ($y=f(x)$), without being able to choose $x$, so no instance of discrete-logarithm approach can be used? In this case I'd highly doubt EC provides such a function, as it's mainly used for discrete-logarithm-based stuff. $\endgroup$
    – SEJPM
    May 25 '15 at 19:46
  • 1
    $\begingroup$ What research have you done? There are various constructions in the DL setting that can be used with elliptic curves. One early and generic approach: citeseerx.ist.psu.edu/viewdoc/summary?doi= $\endgroup$
    – DrLecter
    May 25 '15 at 19:52

As suggested, here is a hopefully entry-level precis of the paper linked in the comment above.

A Discrete Logarithm based asymmetric key system lacks a true trapdoor function - you can't compute a pre-image for an arbitrary image. Instead, a Schnorr signature relies on a slightly weaker condition. A generalized Schnorr signature can be considered to have two parts:

  • a function $O_{K}(i, s)$ taking public key, $K$, an input $i$ and a signature $s$. In ECC, the main component of $O_K(i,s)$ is a bit representation of $s\cdot G+i\cdot K$, where $G$ is the canonical generator for the ECC group and $x\cdot h$ is multiplication of the curve point $h$ by the scalar $x$. Other data may be appended to this bit representation, such as the message to be signed and the list of candidate keys in the ring signature. Generally, it must contain enough information to precisely specify the claim the signature is intended to prove, so that the signature can't be replayed in any other context.
  • a hash function $H(o, m)$ which takes $o$, any output of $O$, and $m$, the message to be authenticated.

$O$ has the additional property that, knowing the secret key corresponding to $K$, it is possible to construct arbitrarily many $o'$ where it is possible to find $s$ for any given $i$ s.t. $o' = O(i, s)$. i.e. there are specific outputs where we can solve for the signature given any input. Call this a preimageable output.

In a standard Schnorr signature we...

  • construct such a preimageable output $o'$ and pass to $H$
  • take $i = H(o', m)$ and solve for $s$.
  • Our signature is $(i, s)$

We verify by checking $i = H( O_{K}(i, s), m )$, i.e. that the input to $O$ is equal to the output of $H$.

Assuming we know the secret key for $K_{1}$ in a set of $K_{1 ... n}$ public keys, we can construct a ring signature as follows:

  • Construct $o'_{1}$, a preimageable output of $O_{K_{1}}$
  • Calculate $i_{1} = H(o'_{1}, m)$
  • Calculate each $i_{j+1} = H( O_{K_{j}}(i_{j}, s_{j}), m )$ for a randomly chosen $s_{j}$
  • Finally, with $i_{1} = i_{n+1}$ solve $o' = O_{K_{1}}(i_{1}, s_{1})$ for $s_{1}$

The ring signature is the sequence of $(i_{j}, s_{j})$ and is verified by checking that for a chosen $i_{j}$ a round-trip of the ring gives the starting value.

The actual construction is a little more complex. The hash includes the complete set of public keys, for example. But this should give the idea of how it works.


Yes, for example Monero use Ring Signature with Ed25519, if it can help to understand the building blocks this is a cheatsheet I have made to contrib to Monero documentation: https://github.com/baro77/RingsCS


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.