Anonymity of KEMs in the QROM

[x k]

Dear PQC forum,

I would like to introduce my paper "Anonymity of NIST PQC Round-3 KEMs"
https://eprint.iacr.org/2021/1323. This paper investigates anonymity and
robustness of NIST PQC Round-3 KEMs __in the QROM__, following Grubbs,
Maram, and Paterson (3rd NIST PQC Std. Conf.,
https://eprint.iacr.org/2021/708).

# Anonymity and robustness in the QROM

The following table summarizes the properties of KEM and the hybrid PKE
in the QROM: indistinguishability, strong pseudorandomness, anonymity,
collision-freeness, and robustness of KEM and anonymity and robustness
of the hybrid PKE under chosen-ciphertext attacks:

====================
ClassicM: Y Y Y N N Y N
Kyber   : ? ? ? ? N ? ? (Grubbs et al.)
NTRU    : Y Y Y Y N Y Y
Saber   : ? ? ? ? N ? ? (Grubbs et al.)

BIKE    : Y Y Y Y N Y Y
FrodoKEM: Y Y Y Y N Y Y (Grubbs et al.)
HQC-1/3 : Y Y Y Y Y Y Y
HQC-5   : Y N N Y Y N Y
sntrupr : ? ? ? ? N ? ?
ntrulpr : Y Y Y Y N Y Y
SIKE    : Y Y Y Y N Y Y
====================
where HQC-1/3 = HQC-128 and HQC-192 and HQC-5 = HQC-256.


# IND-CCA security in the QROM

Grubbs, Maram, and Paterson pointed out that Kyber and Saber have a gap
in the IND-CCA security proof in the QROM because of 'pre-key' and
'nested random oracles'. Their encapsulation algorithms chooses a
message m, computes (khat,r) = G(m,hash(pk)), and then computes K =
H(khat,hash(c)). Their bespoke proof can be applied to FrodoKEM, whose
the encapsulation algorithm computes (khat,r) = G(m,hash(pk)) and K =
H(khat,c), where the length of m and r is equivalent.

I additionally found that Streamlined NTRU Prime (sntrupr) has an
obstacle to apply the existing IND-CCA security proof in the QROM.
In their case, K = H1(H3(m),(c0,c1)) and key-confirmation hash is c1 =
H2(H3(m),H4(pk)).

The QROM IND-CCA security proof for Kyber, Saber, and Streamlined NTRU
Prime without modifying the schemes is an important open problem, while
they will have the ROM IND-CCA security proof without modifying the
schemes.

Bernstein suggested to use of the `domain extension' of quantum random
oracles in [C:Zhandry19], which shows quantum indifferentiability. This
will be a good tool to avoid those obstacles.


Best regards,
Keita Xagawa

[D. J. Bernstein]

To say a bit more about the indifferentiability perspective: The point
of the results in, e.g.,

https://cs.nyu.edu/~dodis/ps/merkle.pdf Lemma 3.2
https://hal.inria.fr/file/index/docid/765883/filename/main.pdf

is that a ROM proof of any protocol using H(x,y) for fixed-length x,y
implies a ROM proof of the same protocol using H_2(H_1(x),y); and

https://eprint.iacr.org/2018/276 Theorem 4

says something analogous for QROM. The results are tight when H_1 has
reasonably long output. (If H_1 is modeled as collision-free then
H_2(H_1(x),y) is a perfect simulation of H(x,y), although formalizing
this is harder than doing ROM proofs.)

Some submissions have stated "theorems" that they never proved, and in
particular https://eprint.iacr.org/2021/708 observed that a Kyber
"theorem" had glossed over the gap between H(x,y) and H_2(H_1(x),y). I
don't see how this observation justifies the proposal to change Kyber:

* This would mean yet another version of Kyber to review: new spec,
new software.

* The change would be making at best a very small difference in proof
tightness for Kyber.

* Meanwhile Kyber needs FO derandomization, which has big looseness
problems. See https://cr.yp.to/papers.html#footloose.

The real problems with these "theorems" are procedural:

* The mechanisms by which security proofs _sometimes_ stop security
problems are almost entirely disabled when submissions claim
"theorems" without doing the work of writing down a proof.

* Even when theorems are proven, they control only a small corner of
lattice security risks, while users are being intimidated into
believing otherwise. See https://cr.yp.to/papers.html#latticeproofs
for a survey of the remaining security risks, and see Section 8 of
https://eprint.iacr.org/2004/152 for the intimidation process.

Finally, I don't see anything in https://eprint.iacr.org/2021/708 or the
new paper https://eprint.iacr.org/2021/1323 indicating an issue for NTRU
Prime. The chart in the new paper seems to say that sntrup is missing
IND-CCA2 provability, but that chart doesn't account for known
indifferentiability results. Regarding the procedural issues, the
theorems presented in the submission have always been subjected to
requirements of (1) being carefully checked and (2) not making the
available security proofs sound bigger than they actually are. The
ongoing process of carefully checking what _can_ be proven about
security is being carried out in separate papers, such as
https://cr.yp.to/papers.html#tightkem, which found counterexamples to
some previously claimed "theorems".

---Dan