Cryptology ePrint Archive: Report 2020/241

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

Mihir Bellare and 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.

Category / Keywords: Post-Quantum Cryptography, NIST, Key Encapsulation, Public-Key Encryption, Random Oracles, Domain Separation, Indifferentiability, Composition

Original Publication (with minor differences): IACR-EUROCRYPT-2020

Date: received 22 Feb 2020, last revised 23 Feb 2020

Contact author: mihir at eng ucsd edu, h3davis at eng ucsd edu, mail at felixguenther info

Available format(s): PDF | BibTeX Citation

Version: 20200225:203331 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]