• Let $y = g^x$, which is your public/private keypair.
  • Let $r = g^v$, for random $v$
  • Let $c = H(M)$
  • Let $z = (v + cx) \bmod q$
  • The signature is the pair $(r,z)$


  • $g^z = ry^c \bmod p$

We further assume that the signer takes care not to sign the same message twice (that's his job in my application), and that the resulting malleability is not an issue. Is this scheme secure in the Random Oracle model?

If so, we can get trivially fast non-interactive multisignature aggregation. https://crypto.stackexchange.com/questions/19291/need-fast-bulk-signature-verification-followed-by-fast-non-interactive-multisig

  • $\begingroup$ In your modified version, how is $r_v$ used? What prevents a forger from just outputting $e = H(M)$ and $s$ being something arbitrary? $\endgroup$ – poncho Sep 23 '14 at 21:44
  • $\begingroup$ Yeah, I guess the wikipedia scheme doesn't work. I've modified the algorithm. Good point and thanks! $\endgroup$ – Jag the Reducer Sep 23 '14 at 21:52

This scheme is insecure, as anyone with the public key can generate a forgery of an arbitrary message.

To do this, the forger would take the message $M$, the public key $y$, pick an arbitrary $z$, and compute $r = y^{-H(M)} g^{z} \bmod p$ and output $(r,z)$

| improve this answer | |

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.