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?
-
https://csrc.nist.gov/projects/post-quantum-cryptography/round-1-submissions – Dec 26 '17 at 19:22
-
4You 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! – Squeamish Ossifrage Dec 26 '17 at 19:43
-
SIDH can be used with the same key size as regular DH. – forest Aug 19 '18 at 03:09
-
1@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. – Ella Rose Feb 06 '19 at 21:57
-
@forest: also, Melab asked for a signature scheme; SIDH (and SIKE) does encryption... – poncho Feb 06 '19 at 22:07
-
@EllaRose Looking into it more, with SIDH compression, you can get a 128-bit security level with 2640-bit public keys which is actually better than standard Diffie-Hellman which requires closer to 3072-bit public keys, according to https://eprint.iacr.org/2016/963. So I stand by my SIDH vs DH key size claim. – forest Feb 08 '19 at 06:40
-
1Ok, 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. – Ella Rose Feb 08 '19 at 16:15
-
@EllaRose It answers if there are any with smaller key sizes than the examples he was aware of, and answers in the negative that there are any only 10 times larger than the desired security level or as small as classical ECC. But you're right, my answer was assuming key exchange. I'll edit it shortly to include signature algorithms. – forest Feb 13 '19 at 08:32
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.
- 15,253
- 2
- 48
- 103
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.
- 2,585
- 1
- 10
- 32
- 11