Added eccPublicKey to the final hashing step of the ECC-KEMs

[fluppe2]

I didn't alter the security considerations, only put eccPublicKey into the hash. Shall we also elaborate on this in the security considerations?

[ahuelsing]

Setup: We have two KEMs which we assume to be multi-user secure. We combine their outputs using a KEM-combiner k = H(k1, c1, k2, c2), c = (c1, c2).

Question 1: Do we have to add pk1 and pk2 to H to preserve multi-user security?

Answer: No. To break security the adversary has to distinguish a set of challenge keys k_u from random (one per user / pk). For each of these k it holds that if the adversary never makes a query H(k1_u, c1_u, k2_u, c2_u) they have a zero advantage over guessing [the result of the query is k_u if it was not random and something different from k_u if it was random -- without querying a random oracle H at a position x an adversary cannot make any statement about H(x)].

The only multi-user advantage that the adversary could gain therefore consists of queries to H that are meaningful for two different users u1 != u2 and their associated public keys. This is only the case if (c1_u1, c2_u1) = (c1_u2, c2_u2) as the ciphertext values decide for which challenge the query is meaningful. I.e., we need a ciphertext collision between challenges. We will argue that this is sufficiently unlikely.

Note, that up to decryption errors, encapsulation is an injective function (otherwise you could not decapsulate). That means that the actual image of the (partial) encapsulation function in the ciphertext space C is at least as large as the space of shared secrets K which in turn has to have sufficient size such that the min-entropy of the challenge k is linear in the security parameter (in practice it will be 256bit and therefore |K| >= 2^256). Now, even if (worst case ever) two users have the same public key, the probability that the challenge ciphertexts are identical is at most 2^-min_entropy (this makes the assumption that the randomness used in the generation of the two challenges is uncorrelated; if it is not independent this is not guaranteed). Hence, the probability that any two users have the same challenge ciphertext is |U^2| 2^-min_entropy.

In consequence, the ciphertexts already work sufficiently well as domain-separator.

Question 2: Can adding pk1 and pk2 to H add multi-user security if the KEMs themselve are not multi-user secure (beyond the trivial non-tight bound)?

Answer: Unlikely, we were unable to construct a counter-example in a short time period, but previous works were only able to show that using a key-ID to domain-separate all hashes preserves multi-user security (see, e.g. https://eprint.iacr.org/2021/1351.pdf).

In consequence, it seems as if it does not make sense to add the pk.

[wussler]

@ahuelsing so if I understood correctly, you mean that:

• We should add the eccPublicKey to the hash (as done in this PR)
• We can remove the PK from the KEM combiner (in another PR)

[ahuelsing]

Exactly (although I did not find a proof that guarantees that adding the eccPK to the hash does give you multi-user security, there are several papers that conjecture it does)