4
$\begingroup$

I'm failing to fully understand the reasoning in 19.2.3 of Boneh and Shoup's A Graduate Course in Applied Cryptography. That constructs short («optimized»/original) Schnorr signature from «regular» (modern) Schnorr signature.

I get the construction, and that it's described by

The transformation $(u_t,\alpha_z)\mapsto(H(m,u_t),\alpha_z)$ maps a regular Schnorr signature on $m$ to an optimized Schnorr signature, while the transformation $(H(m,u_t),\alpha_z)\mapsto(u_t,\alpha_z)$ maps an optimized Schnorr signature to a regular Schnorr signature.

Thanks to helpful comments, I now fully understand the mappings, and can now answer my original question: why

It follows that forging an optimized Schnorr signature is equivalent to forging a regular Schnorr signature.

Update: But I lack understanding of why

It will be sufficient to work with 128-bit challenges.

My thinking is that the proof of the regular Schnorr signature models the hash as a random oracle, but we can't model something with a 128-bit output as a random oracle and claim 128-bit security. Also, I'm worried the reduction to the Discrete Logarithm Problem could become one to a different DLP with some 128-bit limitation. And that could be an issue: for example, the problem of finding $x$ given $(g,y)$ with $y=g^x$ becomes tractable¹ when we limit $x$ to 128-bit, or to $x=a\,x'+b$ with 128-bit $x'$ and given $(a,b)$.

Update 2: Pondering that comment, the crux seems to be that a verifier in Schnorr's identification/Σ-protocol needs only a $t$-bit challenge for error probability $2^{-t}$. But that's still foggy for me.

¹ by Baby-Step/Giant-Step in principle, or Pollard's Rho in practice

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Using the observability property of random oracles, you can extract the regular signature from an algorithm forging an optimized signature. So that should give you the missing direction, should it not? $\endgroup$
    – Maeher
    May 18 at 20:53
  • $\begingroup$ @Maeher: ah, your remark helps. I now see how we turn a forgery for one into a forgery for the other in both directions, assuming the same hash function is used (an assumption I somewhat had missed despite "It will be sufficient to work with 128-bit challenges" in my ref; that explains the size reduction). It's still not clear to me if we can (and how) turn a forgery-making algorithm for one system into a forgery-making alg for the other, since these algs have different inputs, but at least I made some progress. $\endgroup$
    – fgrieu ♦
    May 18 at 21:33
  • 1
    $\begingroup$ Actually, what I said is true but not even necessary. Given a forged optimized signature $(c, \alpha_z)$, you can simply compute the corresponding regular signature as $(g^{\alpha_z}u^{-c},\alpha_z)$. So given an algorithm that can forge one type of signature you can also forge the other type of signature. I don't think I understand your confusion. $\endgroup$
    – Maeher
    May 18 at 22:25
  • $\begingroup$ @Maher: I think I now get it; made that an answer and modified the question. Thanks! $\endgroup$
    – fgrieu ♦
    May 18 at 22:51
  • 1
    $\begingroup$ On the update: the discrete logarithm in question is not subject to any 128-bit limitation; it applies to the public/secret keypair, which is an unrestricted dlog problem. Any prover that can successfully answer two different “challenges” (hash outputs) on its same “initial commitment” must know the secret key (the discrete log of the public key). This is formalized by an extractor, which can easily compute the secret key from the two challenges and answers. Since a prover that doesn’t know the dlog can answer at most one challenge, it suffices to pick the challenge from a big enough space. $\endgroup$
    – Chris Peikert
    May 20 at 12:33
1
$\begingroup$

@Maher's comments guided me to understanding.

To prove security of short Schnorr signature from security of «regular» Schnorr signature with the same hash $H$, we hypothesizes a PPT algorithm $\mathcal A$ that breaks short Schnorr signature, and use it to build algorithm $\mathcal A'$ that breaks regular Schnorr signature, as follows.

$\mathcal A'$ does as $\mathcal A$, except:

  • Whenever $\mathcal A$ requests a signature: $\mathcal A'$ requests a signature for the same message $m$ from the regular Schnorr signature oracle, gets a regular signature $(u_t,\alpha_z)$, turns it into a short signature $(H(m,u_t),\alpha_z)$ by applying $u_t\mapsto H(u_t,m)$ to the first component of the signature, and uses that for whatever $\mathcal A$ does.
  • When and if $\mathcal A$ outputs a forgery: $\mathcal A'$ turns that short signature forgery into a regular signature forgery by applying $c\mapsto g^{\alpha_z}\,u^{-c}$ to the first component of the forgery, using only knowledge of public key $u$ and the group parameters.

Algorithm $\mathcal A'$ remains PPT, and breaks regular Schnorr signature with the same probability as $\mathcal A$; only extra cost are more queries to the random oracle performing the hash, and the final computation for the forgery.

What Boneh and Shoup's 19.2.3 leaves unclear to me is how it's justified

It will be sufficient to work with 128-bit challenges.

that is why $H$ with output much narrower that the group order will do in regular Schnorr signature.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I am going by memory here, but does this help?: the Sigma-protocol for dlog underlying Schnorr’s signature has special soundness, so it suffices to choose the challenge uniformly from a big enough set (since a malicious prover can answer only one possible challenge without knowing the discrete log). Something like the set of 128-bit strings should be enough. $\endgroup$
    – Chris Peikert
    May 19 at 3:15

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.