One of the things that I have come to like about elliptic curve cryptography is that the key only needs to be twice as long as the desired security level. That's a very small expansion (I also like it aesthetically). The sizes for the public key and private key are also the same. Unfortunately, ECC is not secure against quantum algorithms and quantum computers capable of breaking uses of elliptic curves seem to be coming up within a decade or two. What is more is that many post-quantum cryptosystems—the ones I am familiar with, at least—have idiotically huge keys and signatures. The best key sizes seem to be achieved by lattice-based cryptosystems and one variant of code-based cryptography. Are there any candidates with smaller key and signature sizes? Any as small 10 times larger than the desired security level? Any as small as ECC ones?
-
$\begingroup$ csrc.nist.gov/projects/post-quantum-cryptography/… $\endgroup$– user10653Dec 26, 2017 at 19:22
-
4$\begingroup$ You can browse through the NIST pqcrypto submissions, but it's pretty clear that it's too early to say which ones with small keys/signatures/ciphertext overheads/agreement costs are going to stand to scrutiny! $\endgroup$– Squeamish OssifrageDec 26, 2017 at 19:43
-
$\begingroup$ SIDH can be used with the same key size as regular DH. $\endgroup$– forest ♦Aug 19, 2018 at 3:09
-
1$\begingroup$ @forest The SIDH spec (page 28) says generating a shared secret of 256-bits requires a 6608 bit private key and 5808-bit public key (converted from bytes to bits, the paper lists sizes in bytes). These are significantly larger than the values used in either ECDH or even finite field DH. $\endgroup$– Ella RoseFeb 6, 2019 at 21:57
-
1$\begingroup$ Ok, that's technically true as a counter to exactly what I said. But Melab asked about ECC or designs that come within 10x the same size. And there is no way SIDH will come close to ECDH key sizes, and 2640-bit public keys are more than 10x the size of 128 bits. So I stand by my claim that your claim was inaccurate as far as the question here is concerned. This is all kind of irrelevant anyways, since as poncho pointed out the question was asked about signatures, and SIDH is not a signature scheme. $\endgroup$– Ella RoseFeb 8, 2019 at 16:15
2 Answers
It appears that SIDH, or Supersingular Isogeny Diffie-Hellman, is the post-quantum candidate with the smallest key size. When using compression, public key size can be reduced to 330 bytes (2640 bits) to achieve the 128-bit security level. For classical Diffie-Hellman, this value is often quoted at 3072 bits. From the above-linked paper describing the attractiveness of the small public key size of SIDH:
Not only are high-security SIDH public keys smaller than their lattice- and code-based counterparts, they are even smaller than some of the traditional (i.e., finite field) Diffie-Hellman public keys.
The SIDH-based public key encryption and key encapsulation scheme submitted to the NIST post-quantum cryptography process is called SIKE, for Supersingular Isogeny Key Encapsulation, and specifies parameters called SIKEp503 to obtain a 378-byte (3024-bit) public key for the 128-bit security target. However, note that SIKE has been badly broken.
With candidates it must be SIKE, but with non-candidates there is another option: CSIDH. CSIDH with security level $128$ bits has a key length of 64B only two times as large as ECC. It is also about $10$ times slower than SIKE.
