4
$\begingroup$

Signing

  • 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)$

Verifying

  • $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

Improve this question
$\endgroup$
2
  • $\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, 2014 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, 2014 at 21:52

1 Answer 1

Reset to default
7
$\begingroup$

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
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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