Can we get KEMs from signatures (vice versa) in PQC?

✍️ Written on 2022-01-27 in 694 words.
Part of cs IT-security pqcrypto

Motivation

Yesterday, someone at rustgraz asked me whether we can get a digital signature scheme from a KEM by swapping public and private key, just like in the RSA case? Why not? What a good question.

PKE and digital signatures in RSA

Let us look at the description of RSA on Wikipedia:

  1. Choose two distinct prime numbers p and q.

  2. Compute n = pq.

  3. Compute λ(n), where λ is Carmichael’s totient function. Since n = pq, λ(n) = lcm(λ(p), λ(q)), and since p and q are prime, λ(p) = φ(p) = p − 1, and likewise λ(q) = q − 1. Hence λ(n) = lcm(p − 1, q − 1).

  4. Choose an integer e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1; that is, e and λ(n) are coprime.

  5. Determine d as d ≡ e−1 (mod λ(n)); that is, d is the modular multiplicative inverse of e modulo λ(n).

  6. Compute c ≡ me (mod n) for message m to encrypt.

  7. Compute cd ≡ m (mod n) for ciphertext c to decrypt.

Here, (n, e) is the public key and (n, d) is the private key. Now, in order to turn this public key encryption scheme (PKE) into a digital signature scheme, we can just swap the keys.

  1. Compute s ≡ md (mod n) for message m to sign.

  2. Compute se ≡ m (mod n) to verify the signature.

What about PQC?

The equivalent of PKE and digital signatures in post-quantum cryptography is called KEM (Key Encapsulation Mechanism) and digital signatures. One issue is that KEMs (unlike PKEs) do not encrypt a message. Let us take a look at the KEM finalists in the PQC Standardization Effort:

  1. Classic McEliece

  2. CRYSTALS-KYBER

  3. NTRU

  4. SABER

None of these contribute a scheme, where we can easily retrieve an equivalent digital signature scheme. Why? One answer is that three schemes introduce a certain error (NTRU is an exception). They are based on the idea, that computations happen with some error and a non-linear step in the decryption called decryption limits the error. We have seen that RSA computes the message m in the decryption accurately (mathematically speaking, linearly and even homomorphic). But for the three, this is not true. Honestly, I cannot see directly that this prevents the design of a digital signature scheme, but it seems difficult. You need to bound the error somehow and swapping keys means the error must not only be bound for the private key but also the public key. This seems a difficult task. For NTRU, I do not have an equivalent argument. But there is another reason, why swapping public key / private key won’t work: structural differences.

KEMs store different information in the two keys. Often the public key stores information what the underlying mathematical object looks like, e.g. lattice points. However, the public key does not store lattice points but the error introduced. As a result, we cannot swap keys, because the resulting computations would generate semantic garbage. In the case of RSA, public key and private keys have been finite field elements which can be used interchangably.

Conclusion

So, can one generate a digital signature scheme from a key encapsulation mechanism in PQC? No, because …

  1. KEMs do not encrypt a message, but negotiate a shared key. The protocol does not fit (PKE versus KEM).

  2. The proposed PQC KEMs have non-linear operations which makes such a design (at least) difficult.

  3. Unlike RSA, public and private keys are structurally different values.