As the title says. My reference point for the "pseudorandom ciphertext" concept is this paper by Möller, which introduces a public-key encryption algorithm with this property. I want to know the analogue for cryptographic signatures; forgive me if this is discoverable somehow via Google, since it is quite hard to get the search engine to understand that "pseudorandom signature" doesn't refer to the random value used in many signature algorithms.

  • $\begingroup$ Every signature algorithm (and most cryptography on general) contains deterministic algorithms with some inputs, and sometimes when you want pseudorandomness you add a single use random value (IV, nonce). Standard ECDSA uses a secret random value unique per signature (repetitions breaks the security). EdDSA is deterministic and do not use such random inputs. There's no inherent need for pseudorandom signatures, it's just a simpler construct compared to the hashing method EdDSA uses. $\endgroup$
    – Natanael
    Jul 21, 2019 at 13:09
  • $\begingroup$ Depends a bit on what you mean by that. Maybe this is what you're looking for? ia.cr/2011/673 $\endgroup$
    – Maeher
    Jul 21, 2019 at 15:31
  • $\begingroup$ @Maeher That seems right. Another thing that appears to be what I'm thinking of, and for practical purposes seems to be the same, is "verifiable random functions". $\endgroup$
    – Ryan Reich
    Jul 21, 2019 at 19:45

1 Answer 1


A valid signature $\sigma$ satisfies the very special property that $\textsf{Ver}(vk,m,\sigma)=1$, whereas a random value $\tilde \sigma$ will surely not satisfy this property. So a signature simply cannot be indistinguishable from random if $vk$ and $m$ are known. And if you consider $vk$ or $m$ to be secret, then you are leaving the standard realm of signatures. The paper mentioned above by Maeher does exactly this.


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.