Why do the signature and ciphertext size increase in post-quantum schemes? And is there any table or comparison as to how much this increase happens for each scheme type (lattice, multivariate, code-based, etc.)

  • $\begingroup$ I'm really not sure at all about what I'm going to say, but I've heard about the so-called Grover's quantum algorithm, which can improve the efficiency of classical algorithms, and therefore improve classical attacks. This is a good forum to read about it: pqcrypto.org/pqc-forum/20161028-152555.txt $\endgroup$ – Daniel Jan 5 '17 at 21:41
  • $\begingroup$ Increase compared to what? The message? Asymmetric schemes? I guess the best we can do is list signature and ciphertext sizes for specific strengths and a minimum amount of message size, say 256 bits for encryption and 512 bits for signature generation (enough for most hybrid systems). $\endgroup$ – Maarten Bodewes Jan 5 '17 at 22:40
  • $\begingroup$ @SolidSnake That's why we can just increase the key size for symmetric cryptosystems. But, for public key crypto, Shor's algorithm breaks them in polynomial time, so people design new alternatives, but they usually have large signature size. $\endgroup$ – typos Jan 5 '17 at 23:20
  • $\begingroup$ I know about that, what I do not know (like Maarten) is what are you comparing the sizes with? MPKC cryptosystems do not have that large ciphertext sizes in general $\endgroup$ – Daniel Jan 5 '17 at 23:27

If quantum computers are built, then the discrete log and factoring problems will be broken. This means that all schemes based on factoring (e.g., RSA) or discrete log (e.g., ECIES, ECDSA) are broken. In addition, due to Grover's algorithm it is possible to find a symmetric key in time that is square root of the key space. Thus, for $2^{128}$ security, you need 256-bit keys. This means that we need to upgrade to AES-256. Finally, using a trick with Grover's algorithm, it is possible to find collisions in a hash function in time $O(2^{n/3})$ where $n$ is the length of the output. Thus, we need an output of 384 bits at the minimum.

As a result of the above, we are still able to do symmetric crypto and collision resistant hash functions (to the best of our knowledge), but our asymmetric crypto breaks. The factoring and discrete log based systems must therefore be replaced. Currently, the candidates that exist are mainly based on lattices and coding (but there are some others as well). All of these require larger keys and larger ciphertexts, irrespective of quantum computers, simply by the nature of the problems. For signatures there are also schemes based on hash functions, but these also have long signatures. We don't have any proof that these need to be much longer, and it's not because we are just taking longer keys; rather, it's due to the techniques that we currently have for constructing asymmetric schemes that are post-quantum secure.

  • $\begingroup$ “it is possible to find collisions in a hash function in time $$O(n^{1/3})$$, where is the length of the output” – are you sure it is possible in sublinear time? If it is, I wonder how… But I believe there is a mistake. $\endgroup$ – v6ak Jan 7 '17 at 6:56
  • $\begingroup$ Sorry, I meant where $n$ is the size of the output space. So, for length $n$ output, it is time $2^{n/3}$. Thanks. $\endgroup$ – Yehuda Lindell Jan 7 '17 at 23:11

What you say isn't entirely correct. In some post-quantum schemes, the signature or ciphertext is actually smaller than the equivalent-but-classical security level analogue in ECC. See for example the MQ encryption scheme ZHFE (link) or the code-based signature scheme CFS (link). However, in these cases the public key is invariably huge. In other cases we have the opposite: e.g. in the hash-based signature scheme SPHINCS (link), the public key is nice and small, but the signatures are huge. Lattice-based schemes tend to produce public keys of roughly the same size as the ciphertext or signature, but both are noticeably larger than their ECC counterparts. So there is a question there, but it should be rephrased to something like "why is $|\mathsf{pk}| + |\mathsf{s}|$ or $|\mathsf{pk}| + |\mathsf{c}|$ always so large in post-quantum crypto, but not in classical crypto?"

The way all public key schemes work is by relying on hard computational problems with a very definite algebraic structure.* This structure is necessary to guarantee a link between the public and private keys, i.e., only the holder of the private key that matches the public key should be able to decrypt or sign messages. This stands in stark contrast to symmetric crypto, where security relies on breaking -not retaining- algebraic structure and no such link is necessary because there is no distinction between public and private keys. Public key schemes are the subject to more functional constraints than symmetric schemes and as a result there are fewer strategies for their construction. Of those strategies we know to work, only schemes based on number theory and elliptic curves are known to be broken by Shor's quantum algorithm. The others are consequently considered part of post-quantum cryptography. So maybe the best phrasing of your question is something like "why are schemes that are broken by Shor's algorithm, also the schemes with the smallest $|\mathsf{pk}| + |\mathsf{c}|$ and $|\mathsf{pk}| + |\mathsf{s}|$?"

This question has a straightforward answer: both number theory and elliptic curves, or commutative group theory in general, enable a very succinct encoding of computational hardness while retaining a lot of algebraic structure. Unfortunately, this copious algebraic structure comes back to bite you in the ass because it is precisely what allows Shor's algorithm to work.

The good news is that, like Yehuda says, there is no proof that hard algebraic problems that resist attacks on quantum computers cannot have a succinct encoding. So conceivably, it may be possible to design short public key and short signature/ciphertext post-quantum schemes. We just don't know of any that accomplish this.

In terms of a comparison of existing schemes, take a look at eBATS (link), a website that compares operational cost as well as key and message size of various pre- and post-quantum schemes.

*: The exception to this rule is the branch of hash-based signatures. But their notable lack of algebraic structure is also what causes the inherent statefulness (i.e. you have to keep track of all previous signatures to be secure) and what kills the possibility for public key encryption based on hash functions.

  • $\begingroup$ "The exception to this rule is the branch of hash-based signatures. But their notable lack of algebraic structure is also what causes the inherent statefulness" The SPHINCS is stateless. $\endgroup$ – Calmarius Oct 27 '19 at 19:12

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.