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$
    – user10653
    Dec 26 '17 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$ Dec 26 '17 at 19:43
  • $\begingroup$ SIDH can be used with the same key size as regular DH. $\endgroup$
    – forest
    Aug 19 '18 at 3:09
  • $\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 Rose
    Feb 6 '19 at 21:57
  • $\begingroup$ @forest: also, Melab asked for a signature scheme; SIDH (and SIKE) does encryption... $\endgroup$
    – poncho
    Feb 6 '19 at 22:07

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.


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.