I am asking for help in finding a signature algorithm with the following property:

  1. Given a message m and a private key prikey, the result of signing m with prikey is unique (which is stricter than deterministic). In another word, there is only one signature (or finding another one using prikey is securely hard) that can pass the verification by the public key of prikey.
  2. High space efficiency of storing private key and signature.

ECDSA's space efficiency is satisfying, but the signature is not unique; RSA has uniqueness, but is there any alternative with better space efficiency?

  • $\begingroup$ ECDSA signatures can be made to enjoy the uniqueness property you require. See crypto.stackexchange.com/questions/851/… $\endgroup$ – Barack Obama Sep 17 '14 at 20:51
  • 1
    $\begingroup$ @BarackObama Deterministic is not unique. $\endgroup$ – updogliu Sep 17 '14 at 21:17
  • 1
    $\begingroup$ I think BLS is (or can be made) unique. Its signatures have half the size of ECDSA signatures. $\endgroup$ – CodesInChaos Sep 18 '14 at 9:18

Yes! There are verifiably pseudorandom functions or VRFs made out of elliptic curves including EC-VRF, related to ECDSA, and VXEdDSA, related to EdDSA. In addition to getting a unique output for each message, the output is a pseudorandom function of the message, and you get a proof of uniqueness.

More references on VRFs.

|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.