Score:3

What short signature standard?

ng flag

In some applications like QR-codes, saving 25 bytes out of 100 makes a difference in usability.

What choice is there for a signature scheme with (most important criteria first)

  1. As small as possible signature size (for a signature with appendix) or as small as possible added size (measured at 40-byte arbitrary message for a signature scheme with message recovery, but I'd prefer avoiding these), at conjectured 128-bit security level (effort to break comparable to AES-128 key search) discounting Cryptographically Relevant Quantum Computers.
  2. Standardized or vetted by ISO, IEC, ETSI, ANSI, ECRYPT, NIST, ANSSI, BSI, SECG, CFRG, some national standard or body, unamit…, or even an active IETF RFC or a reasonable consensus of crypto experts.
  3. Not or no longer patent-encumbered.
  4. Not overly resource-intensive for verification (perhaps use DSA-3072-256 as the limit).

So far I see:

Notably absent is short Schnorr signature (on Elliptic Curve or Schnorr group), which would be about 48-byte, but AFAIK fails [2]. Perhaps it was not standardized because it has slightly worrying security characteristics:

  • The best brute force attack on the hash alone (e.g. with ASICs as in bitcoin mining) obtains with probability $1/n$ a signed message of practical content at cost $2^{128}/n$ hashes and one merely known message/signature pair, versus cost $\sqrt n$ times higher and one signature query with chosen message for 64-byte competitors.
  • The private-key holder can generate pairs of messages with different and practical content but the same signature using about $2^{66}$ hashes.

¹ I think people got cold feet after the Extented Tower Number Field Sieve incited to revise down earlier security estimates of pairing-friendly curves formerly thought secure, and change some deployed schemes. The subject has grown so complex I'm unable to follow, but from what appears to be a one-page summary of the latest estimates around, for 128-bit security, BLS12-381 at best has not much margin and BN254 seems at risk, in at least some applications (I don't know for BLS signature).

Gilles 'SO- stop being evil' avatar
cn flag
“the private-key holder can generate pairs of messages with different and practical content but the same signature” There are many applications where this isn't a problem. After all we commonly use MAC and AEAD schemes where the secret key holder can create collisions with negligible cost. Authenticity doesn't guarantee integrity in general.
fgrieu avatar
ng flag
@Gilles 'SO- stop being evil' : agreed, none of the two slightly worrying security characteristics I cite for short (EC-)Schnorr are showstoppers. In particular they do not break (s)EUF-CMA. I was citing these as perhaps reasons short (EC-)Schnorr is not standardized, when EC-Schnorr is. [update: I clarified that in the question]
kr flag
I don't know about standardization attempts, but at the risk of sounding a bit reckless, I wouldn't discount BLS signatures on BN254 for this type of applications. Signature size is only 32 bytes, speed is significantly better than BLS12-381, and exTNFS notwithstanding, I wouldn't be surprised if one could make a case that it's a similar security level to the AES once all attack costs are properly accounted for (incl. memory accesses, say).
fgrieu avatar
ng flag
@Mehdi Tibouchi : are you saying the exTNFS-related reasons BN254 has been demoted in favor of BLS12-381 in some applications [see new note ¹ in the question for links] do not harm it down below AES-128 level in general, or that they do not in BLS signature in particular? In either case, I wonder why no Barreto-Naehrig curve is considered in the [draft RFC](https://tools.ietf.org/pdf/draft-irtf-cfrg-bls-signature-04.pdf) for BLS signature. I admit that the rationale for choice of pairing-friendly curves flies high above my head, and scares me!
kr flag
@fgrieu If one can compute discrete logs, one can directly recover the secret key in the BLS signature scheme, so there's nothing special about that setting that makes it especially resilient against exTNFS. The issue is more about what "128 bits of security" actually means. The paper you mention in your note estimates the cost of breaking BN254 with STNFS at around 2^105 or so. However, this means 2^105 computation steps, each of which is *vastly* more costly than one evaluation of AES. The attack also requires massive amounts of memory and communication between compute nodes. So I feel…
kr flag
…fairly confident claiming that 105 bits of TNFS security is higher than 128 bits of AES security, for a reasonable assessment of those two costs.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.