As indicated in an earlier Q / A, KEM's do not necessarily directly encrypt a pre-generated random value. However, it is clear that some KEM's do actually do this, with RSA-KEM being an obvious example.

Is there a name for the property of a KEM that it relies on both the public key value as well as a generated random value by the party that performs the encapsulation?

A possible disadvantage of such a scheme is that the shared secret will only rely on the randomness generated by one of the parties, even though the exchanged ciphertext of course relies on both - assuming that the required key pair is ephemeral.

Do the CRYSTALS-KYBER scheme (standardized by NIST PQC challenge) and ECIES-KEM depend on random values of both parties?

Assume that the public key can be considered ephemeral and that the key pair was generated using a random number generator.

Is there any standardized or recommended for the shared secret to depend on random values provided by both parties? I presume that for e.g. RSA-KEM you could provide a random value that is used within the Info or Salt input of a KDF that is part of a particular KEM scheme?

  • 2
    $\begingroup$ Regarding your first question. So far I have seen these KEMs referred to as "contributory". E.g., McEliece is not contributory (unless I misread the spec). Correct me if I am wrong but I feel the reason why it is not really discussed (but I agree it should be given more attention) is that in an ephemeral key exchange if you assume one party has bad RNG then the attacker can bruteforce its private key and it does not matter if the shared secret is generated from randomness of both parties. Of course, in different (more subtle) scenarios/threat models it can be useful. $\endgroup$
    – honzaik
    Commented Sep 4, 2023 at 12:39
  • 2
    $\begingroup$ Kyber is contributory - explicitly mentioned in csrc.nist.gov/csrc/media/Presentations/2022/… (deliberate use of hash over public key within the KEM). $\endgroup$
    – honzaik
    Commented Sep 4, 2023 at 12:41
  • 1
    $\begingroup$ Thanks for the comments, very informative! I don't get the argument of the "weak RNG used to produce the private key" in case just one key pair is used, as that would currently not be the party that produces the random during encapsulation. And I guess that in most transport mode security that would be the server side anyway, so the servers that are creating the key pair are probably more capable of generating random values. Interesting issue for key agreement based KEM's though. $\endgroup$
    – Maarten Bodewes
    Commented Sep 4, 2023 at 12:59
  • $\begingroup$ Oh you are right, my apologies, I was looking at it from the incorrect "Diffie-Hellman point of view". $\endgroup$
    – honzaik
    Commented Sep 4, 2023 at 13:20
  • $\begingroup$ "Is there any standardized or recommended for the shared secret to depend on random values provided by both parties?" This is how ECDHE in TLS works. Both the client and server generate a random private key, and so both contribute randomness to the shared secret. The server then discards its ephemeral private key, so that if the long-term server private key is leaked, it cannot be used to decrypt logged traffic. $\endgroup$
    – knaccc
    Commented Sep 4, 2023 at 15:36


Your Answer

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