In the paper "Hybrid Key Encapsulation Mechanisms and Authenticated Key Exchange" by Bindel et al., I looked at the IND-CCA security experiment (figure 3).

In the first line of the game, we have $H \leftarrow \mathcal{H}_{\mathcal{K}}$

However, I cannot find the definition of $\mathcal{H}_{\mathcal{K}}$ in the paper. I know that $\mathcal{K}$ represents a key encapsulation mechanism (KEM).

Is this standard notation? I assume that it has something to do with a hash function, as the experiment is done in the random oracle model. Has anybody seen this notation?

  • $\begingroup$ I believe that $\mathcal{H}_{\mathcal{K}}$ is capturing the idea of Universal Hash functions(wisdom.weizmann.ac.il/~naor/PAPERS/uowhf.pdf); as we can read from the cited paper DK05. $\endgroup$ Nov 28, 2023 at 18:07
  • $\begingroup$ @CryptoLearner, it's very unlikely to be related to universal hashes. Looking at the paper in the question, this is about security of schemes in the random oracle model. A UHF can't be used for such constructions, especially when one assumes the attacker can query the hash. For many UHFs, collision resistance may not be guaranteed once a few input-output pairs are known. As I explain in the answer, this notation is introduced in another paper that the current paper builds upon. $\endgroup$ Nov 28, 2023 at 23:09
  • $\begingroup$ @MarcIlunga, I'm not entirely sure about that, even though the authors mention 'Universal Hash' 3 times in the OP paper. However, I'm quite sure that the notation is associated with the concept of 'Family of Hash Functions,' which would be more common than the term you used, 'set of functions'. $\endgroup$ Nov 29, 2023 at 2:50
  • $\begingroup$ @CryptoLearner, the context in which UHF are mentioned in the paper is that of building blogs for key combiners for KEMs. They have nothing to do with the security game/definition of KEM. Look carefully at the paper and the reference I linked to see where the notation in the question is introduced. Besides that, a family of functions is a set of functions. Those terms are used interchangeably in the literature and have the same mathematical meaning. Sometimes, "space of functions" is also used. $\endgroup$ Nov 29, 2023 at 10:08

1 Answer 1


In the first line of the game, we have $H \leftarrow \mathcal{H}_{\mathcal{K}}$

Note that the notation is actually: $H {\leftarrow\mathrel{\mkern-2.0mu}\tiny{\\\$}} \mathcal{H}_{\mathcal{K}}$ (note the "$\tiny\\\$$").

The meaning of the notation is that $H$ is a function sampled at random from the set of functions $\mathcal{H}_{\mathcal{K}}$. This set is the set of functions defined for the KEM. This is a way to formalize that we are working in the random oracle model.

You are right that the notation is introduced without context. I guess that they adopted the notation of one of their references and forgot to introduce it. The notation is used in the paper Transitioning to a Quantum-Resistant Public Key Infrastructure. It is also consistent with the explanation given above.


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.