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

Mihir Bellare; Hannah Davis; Felix Günther

Paper 2020/241

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

Mihir Bellare, Hannah Davis, and Felix Günther

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.

Metadata

Available format(s): PDF
Publication info: A minor revision of an IACR publication in EUROCRYPT 2020
Keywords: Post-Quantum Cryptography NIST Key Encapsulation Public-Key Encryption Random Oracles Domain Separation Indifferentiability Composition
Contact author(s): mihir @ eng ucsd edu
h3davis @ eng ucsd edu
mail @ felixguenther info
History: 2020-02-25: received
Short URL: https://ia.cr/2020/241
License: CC BY

BibTeX

@misc{cryptoeprint:2020/241,
      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},
      url = {https://eprint.iacr.org/2020/241}
}