Small public key size or small signature size, which is preferred?

Question

Suppose two signature schemes provides the same level of security. The sum of the sizes of a public key and a signature, i.e., sizeof(sig) + sizeof(pk), are equal in the two schemes. One of the schemes has smaller public key size, and the other has smaller signature size. Then which scheme is preferred in practice? If it depends, then in what scenarios we prefer smaller public keys, in what scenarios we prefer smaller signatures?

Here is a more specific example. Supppose we want to use a multi-party signature scheme. We have two choices, both providing $256$-bit security: 1. A scheme where a group of $N$ users has a shared public key of size $512$ bits and produces signatures of size $512N$ bits; 2. A scheme where a group of $N$ users has a shared public key of size $512N$ bits and produces signatures of size $512$ bits. We don't have a both-optimal scheme and have to make a trade-off.

Answer 1

One of the schemes has smaller public key size, and the other has smaller signature size. Then which scheme is preferred in practice?

It depends (obviously); in some cases, it doesn't matter; in other cases, smaller signatures are better; in some obscure situations, smaller public keys can be better.

The cases where it doesn't matter is where the public key and the signature always appear together (for example, within a certificate); in that case, both your examples would take up $513N$ bits, and so both are equally costly (in terms of space, and you don't give any other way to differentiate the two schemes).

The cases where smaller signatures is better is when the constraint is total bandwidth, and people can cache the large public key (and so it doesn't need to be transmitted). In your example, if each device can store the $512N$ bit public key, then all they need to transfer is the 512 bit signatures, and things are considerably cheaper.

The case where smaller public keys are better? Well, consider the case where the devices are constrained to the point that they don't have the space to store a $512N$ bit public key; in addition, the signature verification logic is able to process the signature in sections [1], so that it doesn't need to store the entire thing at once. In that case, transmitting $512N$ bit signatures actually works better; the total bandwidth is significantly larger, however in this case, that's not the constraint we're optimizing for; instead, we're optimizing for the capabilities that our constrained devices have.

---

[1]: And, in case you're wondering, yes, such signature systems do exist - hash based signatures is one example.

Answer 2

As poncho mentions, this is of course application dependent. For one of the "most obvious" applications (TLS 1.3), Bas Westerbaan at Cloudflare has a nice blog post. Of course you should read the whole thing for more details, but the takeaway from the blog post is

A timely adoption of PQ signatures on the web would be great. Our evidence so far suggests that this will be easiest, if six signatures and two public keys would fit in 9kB.

This is to say that for TLS1.3, the "natural metric" is 6 sizeof(sig) + 2 sizeof(pk), which suggests that (for TLS) signature size is more important than public key size.