Which post-quantum public key and signature system includes the most compact reusable keypairs? E.g. a private key which produces practically unlimited signatures without losing the security provided initially like RSA as opposed to something like hash-based Merkle tree driven signatures with a limited number of uses?
14
-
$\begingroup$ Modern hash-based signature schemes are practically unlimited. However, they were never contenders for most compact signatures or public keys. $\endgroup$– Squeamish OssifrageCommented Dec 18, 2017 at 2:18
-
$\begingroup$ What are some of them? $\endgroup$– CoryGCommented Dec 18, 2017 at 3:04
-
$\begingroup$ sphincs.cr.yp.to $\endgroup$– Squeamish OssifrageCommented Dec 18, 2017 at 3:06
-
1$\begingroup$ I do believe I warned you up front that they were never contenders for most compact signatures. $\endgroup$– Squeamish OssifrageCommented Dec 18, 2017 at 3:50
-
1$\begingroup$ What do you want a post-quantum signature scheme for? Quantum cryptanalysis is still a long way off, and public verification keys can usually be given short expiration times so that it doesn't matter if a quantum computer can forge them years from now. But it does matter if a quantum computer can retroactively decrypt messages that were exchanged years ago, so that's where most of the pqcrypto work has been focused. (P.S. I assure you I don't mention things just because they're the first Google hit! SPHINCS is actually useful, unlike Lamport one-time signatures.) $\endgroup$– Squeamish OssifrageCommented Dec 18, 2017 at 3:58
|
Show 9 more comments
1 Answer
$\begingroup$
$\endgroup$
4
First of all, you have to say bye to the assumption that you get something like RSA or even ECDSA. Sizes for post-quantum candidates are larger than for classical schemes. Period. There exist schemes with small public keys or signatures but never both. The point is that you can often shift information around between public key and signature but the sum remains the same or gets even worse.
Generally, you got three areas that you can pick from: Hash-based, lattice-based, or multi-variate signatures. Code-based and isogeny-based do not really have practical proposals, yet. Each of these areas has its advantages and disadvantages.
Hash-based gives you the most reliable security guarantees, small public keys and moderate size signatures. For small, fast signatures you require to maintain a state (XMSS / LM-HSS), for stateless schemes (SPHINCS, SPHINCS+, Gravity-SPHINCS) signatures get to the order of 10th of kilobytes.
Lattice-based crypto currently provides you with the best sizes. If the current parameters turn out to be secure you can get away with 2.5 kilobyte signatures and 1.5 kilobyte public keys (Dilithium). However, the cryptanalysis of lattice problems is still on the move. It would not be totally surprising if someone finds an algorithm that is an order of magnitude faster than current attacks (this does not mean that the schemes would be broken but that parameters would have to be adjusted).
Finally, for MQ or multivariate signatures you got two choices: You can go with schemes like UOV or Rainbow (careful: patents) which offer extremely short signatures but somewhat large public keys (I do not know exact numbers as all I found are numbers for classical attacks and 80bit security...). If you further add cyclic structure to the keys, public key sizes go down. However, these constructions are heuristic and we only know that they were not yet broken with known attacks. Especially, their security is not only linked to the MQ-problem but also to far less understood problems like IP and MinRank. Alternatively, you can go with something like MQDSS which has a security reduction from MQ. However, then you are at slightly larger sizes than SPHINCS.
-
$\begingroup$ Is there a fundamental reason why post-quantum crypto needs large signatures and/or public keys? $\endgroup$– DemiCommented Dec 21, 2018 at 0:31
-
$\begingroup$ In general because it uses problems that are closely related to NP-Complete problems which have a huge description size. As the problem instance has to be described either in the public key or in the signature, at least one of them has to be large. However, it is not clear that this is the only way to build post-quantum crypto. Hash-based are an exception for example (with big signatures for other reasons...) but that is why PQ-signatures are currently large $\endgroup$– mephistoCommented Dec 26, 2018 at 10:25
-
$\begingroup$
First of all, you have to say bye to the assumption that you get something like RSA or even ECDSA.Is that guaranteed to always be the case? $\endgroup$– MelabCommented Aug 17, 2023 at 17:45 -
$\begingroup$ I am not aware of a proof that this always has to be the case. However, overcoming the issue requires new ideas that are significantly different from how we build signatures today for the previously mentioned reasons. This is also reflected by the new submissions to NISTs onramp. All unbroken proposals have large signatures or keys for the above reasons. $\endgroup$– mephistoCommented Aug 24, 2023 at 16:31