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