440 views

Skip to first unread message

Jul 27, 2022, 2:32:06 AM7/27/22

to pqc-co...@nist.gov, pqc-...@list.nist.gov

NIST's round-3 report claims a better FO proof picture for Kyber than

it does for NTRU. This is wrong---exactly the opposite of what the

literature says on this topic.

Here's what the report says about FO proofs for Kyber:

The security proofs hold tightly in the ROM [169, 170] and

non-tightly in the QROM. Yet under various other natural assumptions,

KYBER may also achieve a tight security reduction in the QROM [184].

Here's what the report says about FO proofs for NTRU:

The NTRU KEMs have tight CCA-security reductions to the underlying

PKEs in the ROM, and non-tight security reductions in the QROM.

Making some additional non-standard assumptions, one of the QROM

security proofs can be made tight.

This portrays NTRU as having a worse security-proof picture than Kyber:

NTRU needs "non-standard assumptions" for a tight QROM proof, whereas

Kyber "may" have a tight QROM proof under "natural" assumptions.

In fact, the situation for years has been that the literature has better

FO proofs---better tradeoffs between tightness and the strength of the

PKE assumption---for deterministic PKEs than for randomized PKEs:

* ROM, deterministic PKE: https://eprint.iacr.org/2018/526 Theorem

14.3 obtains IND-CCA2 very tightly from the standard minimal PKE

security assumption, OW-CPA. (The techniques are older, but this

paper is designed to support proof verification and identifies

errors in some previously claimed theorems.)

* ROM, randomized PKE: https://eprint.iacr.org/2017/604 has a proof

that's (almost as) tight, but assumes that the PKE is IND-CPA.

IND-CPA is still standard, but it's stronger and more complicated

than OW-CPA, and has received less attention from cryptanalysts.

(See generally Section 6 of https://eprint.iacr.org/2019/691.)

* QROM, deterministic PKE: https://eprint.iacr.org/2019/590 obtains

IND-CCA2 tightly from OW-CPA. I'm assuming here that sqrt(epsilon)

is allowed as tight, unlike a number-of-queries loss factor.

* QROM, randomized PKE: All tight proofs in the literature make

non-standard assumptions, such as the "disjoint simulatability"

assumption from the paper [184] that NIST cites. This is stronger

than standard assumptions; declaring that it's "natural" doesn't

make cryptanalysis magically appear, and doesn't tell us whether

the security levels are as high as desired.

The Kyber PKE (like other GAM/LPR variants) is randomized, so it

definitely can't use the better proofs. The NTRU PKE is deterministic

(since round 2), so presumably the better proofs apply. Someone should

check the details of this application, but the risk of an error here

doesn't justify NIST making claims that are out of whack with the

applicable literature.

NIST's report thus needs an erratum to say that, oops, the report said

that NTRU needs a "non-standard assumption" for a tight QROM proof and

didn't say this about Kyber, whereas in fact the literature indicates

that Kyber needs a non-standard assumption for a tight QROM proof while

NTRU doesn't.

If NIST _isn't_ allowing sqrt(epsilon) as "tight", then the report needs

to clarify the "tight" dividing line. An erratum is still required for

the misinformation that Kyber has a better FO proof picture than NTRU:

in fact, Kyber has a worse FO proof picture than NTRU.

This is important because this Kyber proof gap could be hiding a big

security loss. See https://eprint.iacr.org/2021/912 for examples where

FO IND-CCA2 security is far below OW-CPA security of the underlying PKE.

This is exactly the "derandomization" risk described in Sections 3.8 and

5.8 of https://ntruprime.cr.yp.to/latticerisks-20211031.pdf, which was

filed before NIST's deadline for round-3 input and which, unfortunately,

NIST doesn't seem to have read. But simply reading through the previous

FO proofs is sufficient to see that NIST's report gets this security

comparison backwards.

---D. J. Bernstein

P.S. This is unrelated to the objections that have been raised to the

handling of hashing in Kyber's FO security proofs. Qualitatively, those

objections are identifying an error in the proofs, which of course is

worrisome in a security analysis that NIST's report calls "thorough".

However, the idea that someone is going to find a collision in these

hash functions is very far down any reasonable list of post-quantum

security risks; and plugging in known indifferentiability results closes

the proof gap at the expense of a quantitatively minor loss of

tightness. Derandomization is a much bigger issue.

P.P.S. Kyber has had a new version in every round, and presumably one

should wait to see the next version before filing comments on it, so I'm

filing this is a round-3 comment. However, unless there's a radical

change in Kyber, I would expect the same comment to continue to apply.

P.P.P.S. This comment is of course also regarding NTRU, which NIST's

report says NIST could still select. The underlying issues are also

applicable to the split between deterministic PKEs and randomized PKEs

in other submissions, although unfortunately NIST's report is structured

in a way that obfuscates such comparisons.

it does for NTRU. This is wrong---exactly the opposite of what the

literature says on this topic.

Here's what the report says about FO proofs for Kyber:

The security proofs hold tightly in the ROM [169, 170] and

non-tightly in the QROM. Yet under various other natural assumptions,

KYBER may also achieve a tight security reduction in the QROM [184].

Here's what the report says about FO proofs for NTRU:

The NTRU KEMs have tight CCA-security reductions to the underlying

PKEs in the ROM, and non-tight security reductions in the QROM.

Making some additional non-standard assumptions, one of the QROM

security proofs can be made tight.

This portrays NTRU as having a worse security-proof picture than Kyber:

NTRU needs "non-standard assumptions" for a tight QROM proof, whereas

Kyber "may" have a tight QROM proof under "natural" assumptions.

In fact, the situation for years has been that the literature has better

FO proofs---better tradeoffs between tightness and the strength of the

PKE assumption---for deterministic PKEs than for randomized PKEs:

* ROM, deterministic PKE: https://eprint.iacr.org/2018/526 Theorem

14.3 obtains IND-CCA2 very tightly from the standard minimal PKE

security assumption, OW-CPA. (The techniques are older, but this

paper is designed to support proof verification and identifies

errors in some previously claimed theorems.)

* ROM, randomized PKE: https://eprint.iacr.org/2017/604 has a proof

that's (almost as) tight, but assumes that the PKE is IND-CPA.

IND-CPA is still standard, but it's stronger and more complicated

than OW-CPA, and has received less attention from cryptanalysts.

(See generally Section 6 of https://eprint.iacr.org/2019/691.)

* QROM, deterministic PKE: https://eprint.iacr.org/2019/590 obtains

IND-CCA2 tightly from OW-CPA. I'm assuming here that sqrt(epsilon)

is allowed as tight, unlike a number-of-queries loss factor.

* QROM, randomized PKE: All tight proofs in the literature make

non-standard assumptions, such as the "disjoint simulatability"

assumption from the paper [184] that NIST cites. This is stronger

than standard assumptions; declaring that it's "natural" doesn't

make cryptanalysis magically appear, and doesn't tell us whether

the security levels are as high as desired.

The Kyber PKE (like other GAM/LPR variants) is randomized, so it

definitely can't use the better proofs. The NTRU PKE is deterministic

(since round 2), so presumably the better proofs apply. Someone should

check the details of this application, but the risk of an error here

doesn't justify NIST making claims that are out of whack with the

applicable literature.

NIST's report thus needs an erratum to say that, oops, the report said

that NTRU needs a "non-standard assumption" for a tight QROM proof and

didn't say this about Kyber, whereas in fact the literature indicates

that Kyber needs a non-standard assumption for a tight QROM proof while

NTRU doesn't.

If NIST _isn't_ allowing sqrt(epsilon) as "tight", then the report needs

to clarify the "tight" dividing line. An erratum is still required for

the misinformation that Kyber has a better FO proof picture than NTRU:

in fact, Kyber has a worse FO proof picture than NTRU.

This is important because this Kyber proof gap could be hiding a big

security loss. See https://eprint.iacr.org/2021/912 for examples where

FO IND-CCA2 security is far below OW-CPA security of the underlying PKE.

This is exactly the "derandomization" risk described in Sections 3.8 and

5.8 of https://ntruprime.cr.yp.to/latticerisks-20211031.pdf, which was

filed before NIST's deadline for round-3 input and which, unfortunately,

NIST doesn't seem to have read. But simply reading through the previous

FO proofs is sufficient to see that NIST's report gets this security

comparison backwards.

---D. J. Bernstein

P.S. This is unrelated to the objections that have been raised to the

handling of hashing in Kyber's FO security proofs. Qualitatively, those

objections are identifying an error in the proofs, which of course is

worrisome in a security analysis that NIST's report calls "thorough".

However, the idea that someone is going to find a collision in these

hash functions is very far down any reasonable list of post-quantum

security risks; and plugging in known indifferentiability results closes

the proof gap at the expense of a quantitatively minor loss of

tightness. Derandomization is a much bigger issue.

P.P.S. Kyber has had a new version in every round, and presumably one

should wait to see the next version before filing comments on it, so I'm

filing this is a round-3 comment. However, unless there's a radical

change in Kyber, I would expect the same comment to continue to apply.

P.P.P.S. This comment is of course also regarding NTRU, which NIST's

report says NIST could still select. The underlying issues are also

applicable to the split between deterministic PKEs and randomized PKEs

in other submissions, although unfortunately NIST's report is structured

in a way that obfuscates such comparisons.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu