2
$\begingroup$

NISTs Post Quantum Standardization process selected Kyber as the KEM scheme.

I'm a bit confused over why NIST would standardize for a 'scheme' and not just a 'cipher'. Does Crystals-Dilithium use a different cipher from Crystal-Kyber? I guess previously I was used to just referring to RSA or ECC as ciphers, instead of schemes, and we could use RSA for both signing and Key exchange. Why the distinction now?

I can understand that the requirements around KEM and Signing are different in terms of performance and key generation etc, but I'm not sure if that's a direct result from the 'scheme' or the underlying cipher itself.

Could you take something like Falcon or SPHINCS+ and turn them into KEMs?

$\endgroup$
3
  • 2
    $\begingroup$ "Could you take something like [...] SPHINCS+ and turn them into KEMs?" That would be a major breakthrough that would need to circumvent established impossibility results. $\endgroup$
    – Maeher
    Commented Apr 24 at 9:17
  • 1
    $\begingroup$ I think you are asking why NIST did not call for candidates for Encryption and Hash Algorithms. Well, AES-256 is already Post Quantum secure and may even AES-128. Actually, any classically secure block cipher with 256 bits of key is secure. This table lists the requirements so you can see why they are secure $\endgroup$
    – kelalaka
    Commented Apr 24 at 10:35
  • $\begingroup$ RSA and ECDH are prone to Shor's shortest-period finding algorithms. So we need new mechanisms to securely key exchange/establish/encapsulate. $\endgroup$
    – kelalaka
    Commented Apr 24 at 10:37

1 Answer 1

4
$\begingroup$

I'm not sure what you mean by “scheme” and “cipher”: the exact definition of what is considered different schemes or different cipher can vary. But whatever your definition is, not all schemes are ciphers. A cipher is an encryption/decryption scheme, or part of one. A signature scheme is not a cipher. Ciphers and signatures have different interfaces: different inputs, different outputs, different security requirements.

“RSA” and “ECC” are not schemes or ciphers. They are building blocks from which it is possible to build various kinds of cryptographic schemes including asymmetric encryption, signature and key establishment. They each correspond to a hardness assumption, i.e. a computation problem which is believed to be infeasible for parameters of some agreed-upon size. For RSA, the assumed hardness is for the RSA problem, which is an instance of the general problem of factoring an integer. For ECC, the assumed hardness is that of the Diffie-Hellman problem on chosen groups that are elliptic curves, which is an instance of the general problem of calculating discrete logarithms. Just because a cryptographic scheme uses RSA and ECC as a building block doesn't mean that it's secure: there are plenty of ways to get it wrong, such as “textbook RSA” (encrypting a message by just encoding it as an integer $m$ and calculating $m^e \bmod n$).

NIST does not endorse “RSA” or “ECC” as generic components from which you can build anything you like. For example, the Digital Signature Standard (FIPS 186) endorses four families of signature schemes: RSASSA-PKCS1-v1.5 (based on the RSA problem), RSASSA-PSS (also based on the RSA problem), ECDSA (based on the discrete logarithm problem on certain kinds of elliptic curves) and EdDSA (based on the discrete logarithm problem on one of two elliptic curves). FIPS 186 does not define any encryption scheme, since that's not its job.


we could use RSA for both signing and Key exchange

There are signature schemes based on RSA, as well as asymmetric encryption schemes based on RSA. They use RSA in different ways: the inputs are constructed differently and the outputs are used differently.

RSA is not usually used for a key exchange, where both sides of a communication channel contribute to the material for a shared secret key (Diffie-Hellman, including ECDH, is pretty much the only key exchange scheme out there.). RSA is sometimes used for key encapsulation (where one side chooses a session key and sends it to the other side — this is very easy to build on top of asymmetric encryption).

All common classic asymmetric schemes have two parts: a “mathy” part which is typically written with mathematical notation, and a “programmy” part which is about manipulating bit-strings. For RSA, the mathy part of signature schemes and asymmetric encryption schemes is mostly the same. This is a specificity of RSA: for example, with ECC, ECDSA (signature) and ECDH (key exchange) have very different mathy parts. Even with RSA, the programmy parts are completely different for signature and for encryption.

the requirements around KEM and Signing are different in terms of performance and key generation etc

Actually, it's quite the opposite. For example, all common RSA schemes can use any valid RSA key, so the generation process is the same for an RSA signing key and an RSA decryption key. It is possible (but not recommended due to key management and robustness issues) to use the same RSA key pair for signature/verification and decryption/encryption. Likewise, ECDH and ECDSA have the same valid keys. The performance of RSA-based algorithms is dominated by the mathy part, so RSA signature and decryption have the same performance, and RSA verification and encryption have the same performance. With ECDH vs ECDSA, the mathy parts are different, so their performance is less directly related, but still usually heavily correlated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.