4
$\begingroup$

In Schnorr's digital signature protocol (https://en.wikipedia.org/wiki/Schnorr_signature), the signing process (as described in wikipedia) requires the generation of a random bit $r$. I am wondering how necessary it is for this bit to in fact be randomly generated. For example, what if I generate my ith $r$ as $Q(i)$ for some degree $k$ polynomial $Q$. Would the signing protocol still be secure?

$\endgroup$
1
4
$\begingroup$

Note that the signature is $(s,e)$ where $s=k-xe$. If you can learn $k$ since it is predictable, then you can learn the secret signing key by computing $x = (s-k)/e$. Note that even without a concrete attack, the proof of security completely breaks down if the value $k$ is not chosen randomly.

Having said this, it is possible to change the scheme to be deterministic by including a random key $K$ for a PRF as part of the secret key and then generating the randomness needed to sign $M$ by computing $PRF_K(M)$. This actually is a good idea especially for DSA/ECDSA since repeating randomness there is a disaster The proof that this is good in general is not difficult (a reduction to the PRF).

$\endgroup$
4
  • $\begingroup$ Just a thought: what about PRF over $M$ and a random value in case the user doesn't want repeating signatures? $\endgroup$
    – Maarten Bodewes
    Jan 4 '16 at 21:37
  • $\begingroup$ I would do something different for that: PRF over M XORed with a random value. This says that it will be random if at least one is random. $\endgroup$ Jan 4 '16 at 21:50
  • $\begingroup$ @MaartenBodewes Adam Langley patched OpenSSL to work like that since deterministic signatures would have been a breaking change. $\endgroup$ Jan 4 '16 at 22:39
  • $\begingroup$ @MaartenBodewes Sounds good. The whole idea of this transformation is that it doesn't change anything about the interface of the signature scheme, but doesn't rely on having good randomness. $\endgroup$ Jan 5 '16 at 7:10
2
$\begingroup$

In all digital signature methods, random numbers must be unpredictable.If you use of polynomials or such methods, one can find your polynomial with interpolation or another numerical analysis methods and then use it for any attack.

$\endgroup$

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.