International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Mihir Bellare , University of California San Diego
Hannah Davis , University of California San Diego
Felix Günther , ETH Zürich
Download:
DOI: 10.1007/978-3-030-45724-2_1 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: 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.
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30253,
  title={Separate Your Domains: NIST PQC KEMs, Oracle Cloning and Read-Only Indifferentiability},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={Random oracle model;domain separation;key encapsulation mechanism;NIST post-quantum cryptography},
  volume={12105},
  doi={10.1007/978-3-030-45724-2_1},
  author={Mihir Bellare and Hannah Davis and Felix Günther},
  year=2020
}