Paper 2020/241

Separate Your Domains: NIST PQC KEMs, Oracle Cloning and Read-Only Indifferentiability

Mihir Bellare, Hannah Davis, and Felix Günther


It is convenient and common for schemes in the random oracle model to assume access to multiple random oracles (ROs), leaving to implementations the task (we call it oracle cloning) of constructing them from a single RO. The first part of the paper is a case study of oracle cloning in KEM submissions to the NIST Post-Quantum Cryptography standardization process. We give key-recovery attacks on some submissions arising from mistakes in oracle cloning, and find other submissions using oracle cloning methods whose validity is unclear. Motivated by this, the second part of the paper gives a theoretical treatment of oracle cloning. We give a definition of what is an "oracle cloning method" and what it means for such a method to "work," in a framework we call read-only indifferentiability, a simple variant of classical indifferentiability that yields security not only for usage in single-stage games but also in multi-stage ones. We formalize domain separation, and specify and study many oracle cloning methods, including common domain-separating ones, giving some general results to justify (prove read-only indifferentiability of) certain classes of methods. We are not only able to validate the oracle cloning methods used in many of the unbroken NIST PQC KEMs, but also able to specify and validate oracle cloning methods that may be useful beyond that.

Available format(s)
Publication info
A minor revision of an IACR publication in EUROCRYPT 2020
Post-Quantum CryptographyNISTKey EncapsulationPublic-Key EncryptionRandom OraclesDomain SeparationIndifferentiabilityComposition
Contact author(s)
mihir @ eng ucsd edu
h3davis @ eng ucsd edu
mail @ felixguenther info
2020-02-25: received
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and Hannah Davis and Felix Günther},
      title = {Separate Your Domains: NIST PQC KEMs, Oracle Cloning and Read-Only Indifferentiability},
      howpublished = {Cryptology ePrint Archive, Paper 2020/241},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.