2
$\begingroup$

Context

After reading that for all post-quantum public key cryptography era of short keys and signatures is gone, I wonder how it would be possible to reduce cryptographic overhead of data transfer. For example, the Rainbow-1 public key size is 157,800 bytes?!

Even Dillitium2 public keys are 1320 with signatures of 2420.

The GEMMS128 public key is over 352 KB!

Key sizes and signatures sizes are from https://blog.cloudflare.com/sizing-up-post-quantum-signatures (post is from 2021)

Questions

  1. is it a reliable thing to map a SHA512 of Rainbow-1 or GEMMS128 public key to such key, to prevent transfer of such huge keys with every message or file transferred?
  2. Or if transferred thing will be the random 16 byte stuff with signature done with these algorithms, is it ok to used such construct (key_random_id||signature_of_id_by_key as key for public keys lookup table-service?
Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ BTW: both Rainbow and GeMSS have been broken. Of course, your question is equally applicable to say, a UOV-based system (which would have similarly huge public keys)... $\endgroup$
    – poncho
    Commented Jun 5 at 20:11
  • $\begingroup$ Nice catch! THat post I was refering to is from 2021, I will patch the question a bit. $\endgroup$
    – Kote Isaev
    Commented Jun 6 at 19:48

2 Answers 2

Reset to default
3
$\begingroup$
  1. is it a reliable thing to map a SHA512 of Rainbow-1 or GEMMS128 public key to such key, to prevent transfer of such huge keys with every message or file transferred?

Well, the verifier would need to get the entire public key in order to verify - the hash of that public key would not be sufficient.

On the other hand, if the verifier can use that hash to look-up the public key somehow (either to say "I have 3 preinstalled public keys that I trust; this hash will allow me to pick out which one it is"; or "I can use this hash to download the public key from a public server"), that can work.

In fact, one common suggestion to address these huge public keys is, in fact, to send a "URL+Hash" in place of the public key - the URL would identify where to download the public key from, and the hash would allow you to verify that what you downloaded was correct (and that it wasn't modified on the public server) [1].

  1. Or if transferred thing will be the random 16 byte stuff with signature done with these algorithms, is it ok to used such construct (key_random_id||signature_of_id_by_key as key for public keys lookup table-service?

By 'signature_of_id_by_key', do you mean that the signer signs the key_random_id, and sends that?

Well, I'm not so certain about that. I believe that (depending on the signature algorithm involved) it may be possible to modify the public key so that, for a specific message (key_random_id), the signature is unmodified, and so someone who can modify things on the table-service could replace the public key with something else.

What could they do with that (other than general mischief)? I'm not sure, however by using a collision-resistant hash of the public key, we know that would not be an issue.

[1]: We're sending this URL+Hash where we would normally send the public key. This transmission of the public key must be protected somehow by the protocol (otherwise we can't trust the public key), and this same protection would extend to the 'URL+Hash' (and hence we don't have to worry about someone replacing the hash with the hash of their own public key).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Well, using pair of random_key_id||signature_of_by_key is more relevant to peer-to-peer networking. In more centralized context the random_key_id actually can be not so random and just that unique part of url to key in public keys repository. Thanks for your answer. $\endgroup$
    – Kote Isaev
    Commented Jun 6 at 20:01
2
$\begingroup$

It's worth mentioning that certain schemes are known to have smaller public keys. In particular, isogeny-based crypto typically can achieve public keys $\leq 100$ bytes, and not all of it was broken by the recent (devestating) attacks. See for example this for a modern scheme.

That being said, the trade-off with isogenies (ignoring even the devastating attacks for the moment) is that they are slow. For example, for the linked paper, on a Intel Xeon Gold 6338, signing takes anywhere between 80ms and 470ms, depending on the choice of parameters. The paper also contains cycle counts (Tables 3 and 4). It seems that, even using various optimized CPU instructions (I imagine AVX-type, but didn't check), signing takes 16 million - 94 million cycles. This is compared with dilithium, for which the slowest algorithm (at the highest security level) takes under 3 million cycles. This is not a comparison on a single hardware platform, but still indicates a significant slowdown when using isogenies.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It seems that even with using reference instead of public key, not too much options left for PQ world for compact signatures. Sounds like network devices and OS vendors will have to adapt to allow larger MTU, like 15K instead of today common 1500 bytes. $\endgroup$
    – Kote Isaev
    Commented Jun 7 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.