I have read that in cases where there is a limit on the amount of data sent over the network, one idea is to sent only $t$ bits of data rather than sending all the bits. For example, in the Schnorr scheme this can be employed.

My question is, whether this can be specified by sending the $t$ bits along with the other information?

  • 1
    $\begingroup$ If you want shorter signatures you should consider BLS $\endgroup$ Jan 29 '14 at 11:58
  • $\begingroup$ @CodesInChaos Is it possible to send only a part of signature? Like 16 bits? $\endgroup$
    – user5507
    Jan 31 '14 at 2:43
  • $\begingroup$ There are short MACs (but even they need 64 bits for a decent level of securiy), but even BLS signatures need 2x the security level. One can use proof-of-work to shave of a 20 bits or so. $\endgroup$ Jan 31 '14 at 8:35
  • $\begingroup$ In general, truncating a signature makes verification harder. For most signature schemes around, one fraction of signature verification has its cost next to doubled for each bit removed, because the verification essentially checks all possible values of the bits removed. If verification was just as easy, the truncation would already be part of the signature definition. Thus truncating signature is not often practiced. $\endgroup$
    – fgrieu
    Sep 15 '20 at 8:23

In general, this depends entirely on the signature scheme in question; usually however, the answer is that truncation is generally not possible.

For very short signatures, depending on your risk appetite for other kinds of somewhat novel public-key cryptography, you may find success with pairing-based BLS signatures or multivariate cryptography (GeMSS comes to mind).

For Schnorr signatures in particular, you generally either send:

  • the result of applying the group operation with the nonce $r$, $x = \alpha^r$ (or $[r]G$ in the elliptic curve case) and the scalar $y$, or
  • the tuple of the hash value $e=h(\overline{x}, m)$ and the scalar $y$.

EdDSA, a relative of Schnorr signatures, sends $([r]G, y)$ and thus doesn't lend itself to shortening unless you change your implementation to send $(e, y)$ instead.

If you send $(e, y)$, you can essentially truncate $e$ to an arbitrary extent in your scheme, but the security of the scheme also sinks by that much. Schnorr's original paper proposed using a $t$-bit hash for a $2t$-bit group order. The academic community still isn't sure whether this is a good idea, however, see e. g. Jeremiah Blocki and Seunghoon Lee. On the Multi-User Security of Short Schnorr Signatures, 2019 and Daniel R. L. Brown. Short Schnorr signatures require a hash function with more than just random-prefix resistance, 2015 and their references.


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.