628 views

Skip to first unread message

Jan 19, 2022, 2:12:35â€¯PM1/19/22

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

Within the general risks of structured lattices, there are specific

cryptanalytic reasons for concern regarding the security impact of

Kyber's leap to higher-rank modules over smaller rings: for example,

kyber768 relying on rank-3 modules over a ring of dimension only 256.

It's entirely possible that this structure is exploitable. For example,

compared to the original NTRU system using the 719th cyclotomic field,

kyber768 could end up _much weaker_, as a direct result of Kyber's

module structure.

There's advertising to the contrary, trying to make people believe that

the extra risks of Kyber have been proven not to exist. This advertising

is fundamentally flawed. The proofs _do not_ say what they're portrayed

as saying. There's no hope of fixing this.

Let's go carefully through the details.

1. Special field structures

\Q[X]/(X^1024+1), the 2048th cyclotomic field, has a big pile of

nontrivial subfields: three subfields of half degree, three subfields of

quarter degree, etc.

For example, one subfield is \Q[X^4]/(X^1024+1), which is isomorphic to

\Q[X]/(X^256+1). In this message I'll apply such isomorphisms implicitly

and talk about \Q[X]/(X^256+1) as a subfield of \Q[X]/(X^1024+1).

Such a big pile of subfields is unusual _even among cyclotomic fields_.

There are far fewer subfields in, e.g., the Nth cyclotomic field where N

and (N-1)/2 are prime, exactly the fields recommended in the original

NTRU paper for implementation reasons.

2. Security risks of special field structures

Do unnecessary subfields damage security? From a cryptanalytic

perspective, there are clear reasons to worry that the answer is yes.

There's a vast literature on number-theoretic computations exploiting

subfields. Subfields speed up discrete-log computations. They speed up

class-group computations, unit-group computations, etc. Known S-unit

attacks already exploit subfields in a variety of ways; see, e.g.,

https://cr.yp.to/papers.html#multiquad, https://arxiv.org/abs/2002.12332,

and https://cr.yp.to/talks.html#2021.08.20.

The notion that S-unit attacks are living in a separate world from

lattice-based cryptography was already disproven by the unit attacks

breaking the cyclotomic case of Gentry's original STOC 2009 FHE system,

the original multilinear-map system, etc. Subsequent S-unit attacks are

coming closer and closer to lattice KEMs in NISTPQC, and have already

broken through an amazing series of claimed attack "barriers" reviewed

in Section 1.2 of https://ntruprime.cr.yp.to/latticerisks-20211031.pdf.

What's most important here is that there's no proof, not even a hope of

proving, that extra subfields are safe. I'll return to this below.

3. The modules-are-less-structured argument

There has been endless advertisement of rank-{2,3,4} MLWE systems as

supposedly reducing security risks compared to RLWE systems. Let's look

at what this difference means mathematically.

For concreteness, let's say

* a,e are secret vectors of length 1024 with small entries,

* G is a linear transformation of such vectors, and

* the public key is aG+e.

One of the basic attack goals is to find a,e given G,aG+e.

This description leaves many options for the set of transformations G.

For example, is it any 1024x1024 matrix? Or a matrix with a particular

structure? The choice of this set could have a big impact on security.

Let's compare three choices. I'll describe each choice as a \Q-algebra,

which means a ring R (not necessarily commutative) equipped with a ring

morphism from \Q to R. Here \Q is the field of rational numbers. I'll

abbreviate \Q-algebra as simply "algebra".

Each of these algebras acts as a set of linear transformations on the

module \Q^1024. I'll skip reviewing the standard mechanisms to extract

important "integral" subrings (e.g., extracting \Z[X]/(X^1024+1) from

\Q[X]/(X^1024+1)) and to reduce modulo q, giving linear transformations

on \Z^1024 and on (\Z/q)^1024.

Here are the three choices of algebras:

* "The LWE choice": \Q^(1024x1024), the algebra of 1024x1024 matrices

over \Q, with each matrix viewed as a linear transformation on the

module \Q^1024 in the usual way. There are 1048576 degrees of

freedom in a matrix.

* "The MLWE choice": (\Q[X]/(X^256+1))^(4x4), the algebra of 4x4

matrices with entries in the ring \Q[X]/(X^256+1). Each of these

matrices is viewed as a (\Q[X]/(X^256+1))-linear transformation,

and hence \Q-linear transformation, on the module

(\Q[X]/(X^256+1))^4, which is isomorphic to \Q^1024 as a \Q-module.

There are only 4096 degrees of freedom here. This is a small,

highly structured subalgebra of the first algebra.

* "The RLWE choice": \Q[X]/(X^1024+1), with each element viewed as

the linear transformation that multiplies by that element.

There are only 1024 degrees of freedom here. This is an even

smaller, even more highly structured subalgebra.

It's easy to prove that the third algebra is a subalgebra of the second,

and that solving various problems for transformations of the second type

implies solving various problems for transformations of the third type.

Sounds like switching from RLWE to MLWE is provably eliminating extra

structure and reducing risks, right?

NIST's official round-2 report cites this proof as part of its reason

for rejecting NewHope in favor of Kyber. Half of the NewHope text in

that report is discussing this proof. The report categorically describes

"RLWE schemes" (not just NewHope) as "the most structured", "MLWE" as

"intermediately structured", and "plain LWE" as the "least structured".

4. The fundamental flaw in the argument

The provable relationship between \Q[X]/(X^1024+1) and

(\Q[X]/(X^256+1))^(4x4) relies on the fact that \Q[X]/(X^256+1) is a

subfield of \Q[X]/(X^1024+1).

Having \Q[X]/(X^256+1) as a subfield is a _special structure_ of

\Q[X]/(X^1024+1). For example, the proof does not work---and there is no

hope of making it work---as a comparison to the following field:

* "Another RLWE choice": \Q[X]/(X^1013-X-1), with each element viewed

as the linear transformation that multiplies by that element.

Or, if one wants to precisely match dimensions, the following field:

* "Yet another RLWE choice": \Q[X]/(X^1024-X-1), again viewed as

linear transformations in the usual way.

The third algebra above isn't actually "the" RLWE choice: there are

_many_ choices of fields in each dimension, and the proof requires

restricting attention to a narrow, structured subset of these choices.

This means that enabling the proof required _imposing structure_ on the

starting field. From the perspective of the algorithm designer, this

structure is an attack tool!

The full S-unit lattice for a nontrivial S isn't hard to calculate for

the field \Q[X]/(X^256+1), thanks to the smallness and special structure

of this field. It's not that this has been publicly extended yet to a

break of problems for (\Q[X]/(X^256+1))^(4x4), but it's really not hard

to imagine that severe weaknesses of a ring also create weaknesses of

4x4 matrices over that ring.

Even people who have trouble seeing how such algorithms might work can't

deny the logical _possibility_ that the smallness and special structure

of \Q[X]/(X^256+1) will turn into a devastating attack against problems

for (\Q[X]/(X^256+1))^(4x4), making kyber1024 feasible to break.

The proof then says that, logically, there must also be a weakness for

\Q[X]/(X^1024+1). But this _doesn't_ logically imply weaknesses in most

other algebras. There's no reason to exclude the possibility of other

algebras being stronger: for example, \Q[X]/(X^1013-X-1) being stronger.

In this scenario, the proof is simply relating one weak problem to

another weak problem. What's terrifying is that _this is being used as

an argument to use a weak problem instead of a stronger problem_. People

are casually introducing a small structured ring into a cryptosystem and

blindly advertising the use of modules over this ring as risk reduction,

even though in this scenario it _damages_ security.

Are we supposed to worry about structured matrices and _not_ worry about

structured rings? This makes no sense. A direct comparison of the

algebras being used, the basic algebraic structure of the set of G used

for public keys aG+e, immediately shows that the move to modules

requires structure that otherwise would _not_ have to be there.

If the comparison is merely to NewHope, then the field \Q[X]/(X^256+1)

was present from the outset as a subfield. In this case, sure, insisting

on modules doesn't require adding any structure to the field. (There are

other problems with NIST's NewHope comparison; see below.) But this is a

_very_ special case.

Instead of acknowledging the special field structure enabling this

proof, NIST glibly generalizes, categorically describing "RLWE" as "more

structured" than "MLWE". That categorical statement is simply wrong!

For example, (\Q[X]/(X^256+1))^(4x4) has a subalgebra \Q[X]/(X^256+1)

with many special properties drawing the cryptanalyst's attention:

* The subalgebra is much bigger than \Q, but much smaller than the

full algebra.

* The subalgebra is in the "center" of the full algebra, meaning

that it commutes with every choice of G.

* The subalgebra is a cyclotomic field.

* This field has a tower of smaller subfields having the same

properties, such as \Q[X]/(X^128+1), plus further subfields.

This structure is not present in \Q[X]/(X^1013-X-1), a field whose only

subfields are itself and \Q.

People are being misled into believing that the proof says that the

entire class of RLWE problems of degree around n is broken if rank-4

MLWE problems of degree around n/4 are broken. No, that's _not_ what the

proof says. One needs to narrow attention to some _highly structured_

RLWE problems to make the proof work. Adding this structure to enable

the proof also adds dangers that the proof doesn't address.

5. Small fields in pre-quantum DH

Think back to the old days when people used a 1024-bit prime field

inside your favorite discrete-log system, let's say DH. (Not so old,

actually.)

Imagine someone saying "You should move to this matrix version of DH

using 4x4 matrices over \F_{2^256}. For similar cost in the following

metrics, this allows many more matrices, and the following 4x4 matrix

problems are provably secure if some \F_{2^1024} problems are secure."

Um, yes, okay, there are more matrices, and it's not crazy to _hope_ for

the non-commutativity to add security compared to \F_{2^1024}. But if

(1) the subfields of \F_{2^1024} are a security disaster (this turns

out to be the case) and

(2) non-commutativity isn't enough to rescue the system (it turns

out to provide _no_ security benefit; see 1997 Menezes--Wu)

then the new system is a security disaster while, as far as we know, the

old one isn't.

So the proof is relating one weak problem to another weak problem.

Meanwhile it's misleading people into switching away from a strong

problem, even though the proof actually says _nothing_ about the strong

problem---the same way that the MLWE-vs.-RLWE proof says _nothing_ about

RLWE using fields outside a specially structured class.

This DH example illustrates the structural dangers inherent in (1)

constructing systems "with the objective of being able to give security

reductions for them" and (2) using this as a risk-assessment mechanism,

judging systems as less risky if they have more "security proofs". What

the proofs actually say about security is limited, and the limitations

have to be carefully taken into account.

6. Modules as a danger separate from cyclotomics

In the above matrix example, \F_{2^256} has a tower of subfields that

are unnecessary for DH, the same way that \Z[X]/(X^256+1) has many

subfields that are unnecessary for lattice-based cryptography, along

with further unnecessary structure such as being cyclotomic.

What happens if one removes this structure? Consider 4x4 matrices over

the prime field \F_p, where p is a 256-bit prime. "Provable security"

then highlights a relationship between these matrices and a 1024-bit

finite field \F_{p^4}.

Is it correct to say that the matrices are less structured than 1024-bit

fields? No, of course not. The proof is only for _extremely special_

1024-bit fields, the ones that have 256-bit prime subfields.

If this subfield structure opens up vulnerabilities (variants of NFS

that exploit subfields are an active research area today), and if these

are also vulnerabilities of the matrix system (which, again, turns out

to be the case; see 1997 Menezes--Wu), then moving from a 1024-bit prime

field to the matrix system has damaged security. So how can one portray

the proof as saying that moving to matrices is reducing risks?

What one sees here is that simply imposing the matrix structure, working

with 4x4 matrices over a field with 1/4 as many bits, is creating a new

security risk, a risk that is _not_ addressed by the "security proof".

Similar comments apply to lattice systems. Cyclotomics are particularly

worrisome, but _even outside the cyclotomic context_ it's entirely

possible that moving to modules---for example, a rank-4 module over a

quarter-dimension ring---damages security. There's certainly no proof to

the contrary.

Consider, as concrete examples, the following \Q-algebras:

(1) \Q[X]/(X^1024-X-1).

(2) \Q[X]/(X^1024-X^4-1).

(3) (\Q[X]/(X^256-X-1))^(4x4).

(4) \Q[X]^(1024x1024).

Here the argument for modules says that #1 is a small, structured piece

of #4, which is worrisome, and that #2 is a small, structured piece of

#4, which is worrisome, and that #3 is an intermediate case between #2

and #4, making it less worrisome.

But #2 and #3 both have special structure that doesn't exist in #1!

This isn't as extreme as the tower of cyclotomics mentioned above, but

again there's an intermediate algebra with special properties catching

the cryptanalyst's eye as a potential springboard for attacks: both

algebras contain \Q[X]/(X^256-X-1), which is much bigger than \Q, much

smaller than the full algebra, and in the center of the full algebra.

The presence of this special intermediate field could expose #2 and #3

to attacks that don't apply to #1, a field whose only proper subfield is

\Q.

Advocating a leap from #1 to #3, and trying to justify this by pointing

to a proof relating #2 to #3, is indefensibly exaggerating what the

proof says, and ignoring the security risk of introducing extra

subfields---again, something that has a long history of being exploited.

To summarize, what the advertising wants people to believe is that the

Kyber matrices are provably at least as strong as commutative rings

(acting on vectors of similar dimension). What the proof actually says

is, at best, that the Kyber matrices are at least as strong as some

_very special_ commutative rings, the rings used in NewHope. The proof

does _not_ say that the Kyber matrices are at least as strong as _other_

commutative rings. Closing this gap is hopeless.

7. Credits and subsequent discussions

The fundamental flaw in the module advertising was already pinpointed in

Section 5.5 of https://ntruprime.cr.yp.to/latticerisks-20211031.pdf (in

less detail than the explanation I've given above). I cited that paper

in my first message in the small-rounding thread:

Theorems that might give a "modules are guaranteed safe" impression have

limitations rendering them logically inapplicable to NISTPQC. See, e.g.,

Section 5.5 of https://ntruprime.cr.yp.to/latticerisks-20211031.pdf.

A followup a few days later, the message I'm responding to, repeats

essentially the same advertising---hiding the flaw inside a false

hypothesis.

[ context omitted by the message I'm replying to: ]

> > Let's try an example: the experiments reported in Section 4.2 of

> > https://www.ntru.org/f/hps98.pdf (the first paper Dr. Peikert cited).

> > These are attacking scaled-down versions of the original NTRU system.

[ context included in the message I'm replying to: ]

> > Why exactly is it supposed to be okay to count these experiments towards

> > "enough cryptanalysis" of systems that move to rank-3 modules over a

> > ring of only 1/3 dimension (e.g., kyber768),

> Because there are simple reductions that allow one to decrease the

> degree of the ring, while increasing the module rank.

> If R=Z[X]/(X^1024+1)

[ ... ]

> So if NTRU is over the ring R

This is the false hypothesis mentioned above.

The question was explicitly about the experiments in Section 4.2 of the

original NTRU paper. Those experiments used X^N-1 for various N; why

would they have detected security failures of X^N+1 with N being a power

of 2? Maybe failures of X^N+1 would show up for X^2N-1, but the

experiments didn't use any power-of-2 exponents. In short, no, this

isn't over the ring R; it isn't over _any_ power-of-2 ring.

The same hypothesis is, of course, also false for various NISTPQC KEMs,

such as sntrup1013.

Again, the (partial) proof that kyber1024 >= newhope1024 relies on the

fact that \Q[X]/(X^1024+1) has a much smaller subfield \Q[X]/(X^256+1).

What happens if the smallness and special structure of \Q[X]/(X^256+1)

turn out to be a security problem for _both_ kyber1024 and newhope1024,

a problem not shared by most fields---maybe even most cyclotomics?

Perhaps someone has in mind a _heuristic_ saying that if power-of-2

cyclotomics have a security problem then the problem will also show up

for many other cyclotomics. This essentially assumes away any potential

difference between power-of-2 cyclotomics and random cyclotomics. Maybe

this is a valid heuristic, but how well has it been tested?

Compare this to Dr. Peikert's message at the start of the small-rounding

thread: "The existing analyses essentially 'assume away' any potential

difference between deterministic rounding errors and random ones. Maybe

this is a valid heuristic, but how well has it been tested?"

If we're supposed to worry about the possibility that rounding loses

security, and the possibility that structure in matrices loses security,

shouldn't we worry about the possibility that power-of-2 cyclotomic

structure loses security, even compared to most cyclotomics? Where are

all the papers redoing every NTRU attack experiment for the power-of-2

case? Where are the objections to a lack of Kyber-specific experiments?

These possibilities are analogous in that none of these features have

been _proven_ secure. This is what I've been emphasizing in the last few

paragraphs---but it's also a _very_ low bar. Every lattice KEM has a

combinatorial explosion of features (obviously far beyond the number of

attack papers); only a narrow corner is proven secure; so it's trivial

to take any submission and selectively highlight a proof gap for that

submission. If this were done systematically then people would realize

how content-free it is. Instead it's against a backdrop of many other

proofs being indefensibly exaggerated, such as the MLWE-vs.-RLWE proof.

Correcting the exaggerations and studying how little the proofs actually

say makes clear that risk management has to be driven instead by the

literature designing and analyzing _algorithms_. What's truly concerning

about subfields, cyclotomics, etc. isn't the minimal point that they

haven't been proven safe. What's truly concerning is that these

structures have already been exploited for many years to speed up a wide

range of number-theoretic computations---often quite dramatically, as

illustrated by the quantum polynomial-time break of Gentry's original

STOC 2009 FHE system for cyclotomics (under minor assumptions), and the

non-quantum quasi-polynomial-time break of an analogous system using

multiquadratics (which aren't cyclotomic but have many subfields).

I understand that the magnitude of the danger isn't obvious to everyone.

But the idea that the danger has been _proven_ not to exist is absurd.

There's a specific fiction that leaping to rank-{2,3,4} modules, while

dropping the field degree correspondingly, has been proven to not lose

security; let's get that corrected for the record.

> what is your "concern" with the above?

First of all, for a mathematician, _any_ proof exaggeration is

unacceptable.

NIST wrote "In a technical sense, the security of NewHope is never

better than that of KYBER", pointing to a proof. But simply reading what

the proof says and comparing it to the NewHope-vs.-Kyber example shows

many reasons that, no, the proof _doesn't_ say that Kyber is at least as

strong as NewHope. (See generally my email dated 25 Jul 2020 10:36:57

+0200.) NIST didn't even bother to systematically _list_ those reasons,

never mind presenting an evaluation of the corresponding security risks.

This is horrifying.

The specific exaggeration that I'm emphasizing in this message doesn't

matter for NewHope in particular: as noted above, NewHope already had

\Q[X]/(X^256+1) present as a subfield. However, as part of the same

official report, NIST stated a much broader categorical preference for

"low-rank MLWE schemes over RLWE schemes"---evidently blind to the fact

that this leap requires inserting extra structure that could damage

security, structure that a pure RLWE system doesn't need. The proof does

_not_ provide any reason to think that (\Q[X]/(X^256+1))^(4x4) is as

safe as \Q[X]/(X^1013-X-1).

In short, readers are being led to believe that inserting the small

field \Q[X]/(X^256+1) into a system design is guaranteed safe---but the

argument presented for this starts by hypothesizing that \Q[X]/(X^256+1)

was already present as a subfield! This makes no sense.

> Is it:

> 1. It's possible that Module-LWE over random A'' is easy (so

> Kyber-1024 is easy), but Module-LWE over a structured A'' (i.e. the

> one you get from transforming A-->A'') is hard?

I have a clarification question regarding two general words here, "easy"

vs. "hard": are these supposed to refer to some _big_ gap in security?

Kyber's security margin seems to keep dropping and seems very small

(possibly nonexistent), so a small improvement in attacks could mean

that Kyber doesn't reach its claimed security level.

The rest of the specific text here seems like a pointless distraction

from the elephant in the room, the fact that the proof at hand compares

MLWE using \Q[X]/(X^256+1) to an _extremely restricted_ type of RLWE

system, one where \Q[X]/(X^256+1) is already present as a subfield.

> 2. That this reduction works only for dimensions that are a power of

> 2, so we can't say anything about Kyber-768 which has a 3x3 matrix A

> (i.e. maybe it's as hard as Kyber with a 2x2 matrix over the same

> ring).

In the absence of further information, one has to guess that the 3x3

case is stronger than the 2x2 case. But this is a weak statement given

that the 2x2 case is already on the bleeding edge against known attacks

and that the 3x3 case claims a _much_ higher security level.

Why resort to some weak 3-to-2 relation instead of talking about how

Kyber relates to some degree-768 extension of \Q[X]/(X^256+1), such as

\Q[X,Y]/(X^256+1,Y^3-Y-X)? Could this be because presenting such an

extension helps the reader realize that the 256*3 -> 768 proof is

restricted to a narrow, specially structured set of degree-768 fields?

> Both of these "objections", however, are counter to a lot of the

> theory that underlies lattice cryptography. (1) contradicts that

> random matrices A are the hard instances and (2) contradicts that

> increasing the dimension makes the lattice problem harder.

This text also seems like a distraction from the elephant.

> So if you're going to state hypotheses that go against established

> theory, you need to have some evidence. Otherwise, one can state anything

> that can't be proved or disproved -- (e.g. do you have concrete proof

> contradicting the Qanon and the covid vaccine conspiracies? No? Then I

> guess you should consider them to be as valid as their negations.)

This level of rhetoric regarding the nature of evidence is in a message

that starts from an outright false assumption regarding the stated

context and ignores an earlier reference to a paper explaining the gap?

Hmmm.

> The difference between saying (1) LWE is hard, but LWR with small

> rounding could be easy and (2) NTRU is hard, but Module-LWE could be

> easy is that (1) does not contradict any of the underlying theory or

> understanding upon which lattice crypto is built, whereas (2) would

> mean that the core of the established theory is wrong.

Please clarify.

What's covered by "the underlying theory or understanding upon which

lattice crypto is built"? Is this excluding, e.g., the original LLL

paper, the original BKZ paper, the original NTRU paper, and many more

years of design and analysis of algorithms? If this excludes papers on,

e.g., class-group computations, then what's the rationale for excluding

those, and how does this avoid making the argument circular?

How precisely would weaknesses triggered by the smallness and special

structure of \Q[X]/(X^256+1) contradict "the established theory"?

It's disturbing to see a message that's so driven by "security proofs"

that it makes a hypothesis that's false regarding the explicit context

and often false for NISTPQC---simply _assuming_ that one is starting

with particular field structures, because this is what has to be done to

make the proof work---and then tries to lead the reader to believe that

the existing "theory and understanding" guarantee the safety of modules,

evidently with no need to even _look_ at what's known about algorithms

exploiting those field structures.

---Dan

cryptanalytic reasons for concern regarding the security impact of

Kyber's leap to higher-rank modules over smaller rings: for example,

kyber768 relying on rank-3 modules over a ring of dimension only 256.

It's entirely possible that this structure is exploitable. For example,

compared to the original NTRU system using the 719th cyclotomic field,

kyber768 could end up _much weaker_, as a direct result of Kyber's

module structure.

There's advertising to the contrary, trying to make people believe that

the extra risks of Kyber have been proven not to exist. This advertising

is fundamentally flawed. The proofs _do not_ say what they're portrayed

as saying. There's no hope of fixing this.

Let's go carefully through the details.

1. Special field structures

\Q[X]/(X^1024+1), the 2048th cyclotomic field, has a big pile of

nontrivial subfields: three subfields of half degree, three subfields of

quarter degree, etc.

For example, one subfield is \Q[X^4]/(X^1024+1), which is isomorphic to

\Q[X]/(X^256+1). In this message I'll apply such isomorphisms implicitly

and talk about \Q[X]/(X^256+1) as a subfield of \Q[X]/(X^1024+1).

Such a big pile of subfields is unusual _even among cyclotomic fields_.

There are far fewer subfields in, e.g., the Nth cyclotomic field where N

and (N-1)/2 are prime, exactly the fields recommended in the original

NTRU paper for implementation reasons.

2. Security risks of special field structures

Do unnecessary subfields damage security? From a cryptanalytic

perspective, there are clear reasons to worry that the answer is yes.

There's a vast literature on number-theoretic computations exploiting

subfields. Subfields speed up discrete-log computations. They speed up

class-group computations, unit-group computations, etc. Known S-unit

attacks already exploit subfields in a variety of ways; see, e.g.,

https://cr.yp.to/papers.html#multiquad, https://arxiv.org/abs/2002.12332,

and https://cr.yp.to/talks.html#2021.08.20.

The notion that S-unit attacks are living in a separate world from

lattice-based cryptography was already disproven by the unit attacks

breaking the cyclotomic case of Gentry's original STOC 2009 FHE system,

the original multilinear-map system, etc. Subsequent S-unit attacks are

coming closer and closer to lattice KEMs in NISTPQC, and have already

broken through an amazing series of claimed attack "barriers" reviewed

in Section 1.2 of https://ntruprime.cr.yp.to/latticerisks-20211031.pdf.

What's most important here is that there's no proof, not even a hope of

proving, that extra subfields are safe. I'll return to this below.

3. The modules-are-less-structured argument

There has been endless advertisement of rank-{2,3,4} MLWE systems as

supposedly reducing security risks compared to RLWE systems. Let's look

at what this difference means mathematically.

For concreteness, let's say

* a,e are secret vectors of length 1024 with small entries,

* G is a linear transformation of such vectors, and

* the public key is aG+e.

One of the basic attack goals is to find a,e given G,aG+e.

This description leaves many options for the set of transformations G.

For example, is it any 1024x1024 matrix? Or a matrix with a particular

structure? The choice of this set could have a big impact on security.

Let's compare three choices. I'll describe each choice as a \Q-algebra,

which means a ring R (not necessarily commutative) equipped with a ring

morphism from \Q to R. Here \Q is the field of rational numbers. I'll

abbreviate \Q-algebra as simply "algebra".

Each of these algebras acts as a set of linear transformations on the

module \Q^1024. I'll skip reviewing the standard mechanisms to extract

important "integral" subrings (e.g., extracting \Z[X]/(X^1024+1) from

\Q[X]/(X^1024+1)) and to reduce modulo q, giving linear transformations

on \Z^1024 and on (\Z/q)^1024.

Here are the three choices of algebras:

* "The LWE choice": \Q^(1024x1024), the algebra of 1024x1024 matrices

over \Q, with each matrix viewed as a linear transformation on the

module \Q^1024 in the usual way. There are 1048576 degrees of

freedom in a matrix.

* "The MLWE choice": (\Q[X]/(X^256+1))^(4x4), the algebra of 4x4

matrices with entries in the ring \Q[X]/(X^256+1). Each of these

matrices is viewed as a (\Q[X]/(X^256+1))-linear transformation,

and hence \Q-linear transformation, on the module

(\Q[X]/(X^256+1))^4, which is isomorphic to \Q^1024 as a \Q-module.

There are only 4096 degrees of freedom here. This is a small,

highly structured subalgebra of the first algebra.

* "The RLWE choice": \Q[X]/(X^1024+1), with each element viewed as

the linear transformation that multiplies by that element.

There are only 1024 degrees of freedom here. This is an even

smaller, even more highly structured subalgebra.

It's easy to prove that the third algebra is a subalgebra of the second,

and that solving various problems for transformations of the second type

implies solving various problems for transformations of the third type.

Sounds like switching from RLWE to MLWE is provably eliminating extra

structure and reducing risks, right?

NIST's official round-2 report cites this proof as part of its reason

for rejecting NewHope in favor of Kyber. Half of the NewHope text in

that report is discussing this proof. The report categorically describes

"RLWE schemes" (not just NewHope) as "the most structured", "MLWE" as

"intermediately structured", and "plain LWE" as the "least structured".

4. The fundamental flaw in the argument

The provable relationship between \Q[X]/(X^1024+1) and

(\Q[X]/(X^256+1))^(4x4) relies on the fact that \Q[X]/(X^256+1) is a

subfield of \Q[X]/(X^1024+1).

Having \Q[X]/(X^256+1) as a subfield is a _special structure_ of

\Q[X]/(X^1024+1). For example, the proof does not work---and there is no

hope of making it work---as a comparison to the following field:

* "Another RLWE choice": \Q[X]/(X^1013-X-1), with each element viewed

as the linear transformation that multiplies by that element.

Or, if one wants to precisely match dimensions, the following field:

* "Yet another RLWE choice": \Q[X]/(X^1024-X-1), again viewed as

linear transformations in the usual way.

The third algebra above isn't actually "the" RLWE choice: there are

_many_ choices of fields in each dimension, and the proof requires

restricting attention to a narrow, structured subset of these choices.

This means that enabling the proof required _imposing structure_ on the

starting field. From the perspective of the algorithm designer, this

structure is an attack tool!

The full S-unit lattice for a nontrivial S isn't hard to calculate for

the field \Q[X]/(X^256+1), thanks to the smallness and special structure

of this field. It's not that this has been publicly extended yet to a

break of problems for (\Q[X]/(X^256+1))^(4x4), but it's really not hard

to imagine that severe weaknesses of a ring also create weaknesses of

4x4 matrices over that ring.

Even people who have trouble seeing how such algorithms might work can't

deny the logical _possibility_ that the smallness and special structure

of \Q[X]/(X^256+1) will turn into a devastating attack against problems

for (\Q[X]/(X^256+1))^(4x4), making kyber1024 feasible to break.

The proof then says that, logically, there must also be a weakness for

\Q[X]/(X^1024+1). But this _doesn't_ logically imply weaknesses in most

other algebras. There's no reason to exclude the possibility of other

algebras being stronger: for example, \Q[X]/(X^1013-X-1) being stronger.

In this scenario, the proof is simply relating one weak problem to

another weak problem. What's terrifying is that _this is being used as

an argument to use a weak problem instead of a stronger problem_. People

are casually introducing a small structured ring into a cryptosystem and

blindly advertising the use of modules over this ring as risk reduction,

even though in this scenario it _damages_ security.

Are we supposed to worry about structured matrices and _not_ worry about

structured rings? This makes no sense. A direct comparison of the

algebras being used, the basic algebraic structure of the set of G used

for public keys aG+e, immediately shows that the move to modules

requires structure that otherwise would _not_ have to be there.

If the comparison is merely to NewHope, then the field \Q[X]/(X^256+1)

was present from the outset as a subfield. In this case, sure, insisting

on modules doesn't require adding any structure to the field. (There are

other problems with NIST's NewHope comparison; see below.) But this is a

_very_ special case.

Instead of acknowledging the special field structure enabling this

proof, NIST glibly generalizes, categorically describing "RLWE" as "more

structured" than "MLWE". That categorical statement is simply wrong!

For example, (\Q[X]/(X^256+1))^(4x4) has a subalgebra \Q[X]/(X^256+1)

with many special properties drawing the cryptanalyst's attention:

* The subalgebra is much bigger than \Q, but much smaller than the

full algebra.

* The subalgebra is in the "center" of the full algebra, meaning

that it commutes with every choice of G.

* The subalgebra is a cyclotomic field.

* This field has a tower of smaller subfields having the same

properties, such as \Q[X]/(X^128+1), plus further subfields.

This structure is not present in \Q[X]/(X^1013-X-1), a field whose only

subfields are itself and \Q.

People are being misled into believing that the proof says that the

entire class of RLWE problems of degree around n is broken if rank-4

MLWE problems of degree around n/4 are broken. No, that's _not_ what the

proof says. One needs to narrow attention to some _highly structured_

RLWE problems to make the proof work. Adding this structure to enable

the proof also adds dangers that the proof doesn't address.

5. Small fields in pre-quantum DH

Think back to the old days when people used a 1024-bit prime field

inside your favorite discrete-log system, let's say DH. (Not so old,

actually.)

Imagine someone saying "You should move to this matrix version of DH

using 4x4 matrices over \F_{2^256}. For similar cost in the following

metrics, this allows many more matrices, and the following 4x4 matrix

problems are provably secure if some \F_{2^1024} problems are secure."

Um, yes, okay, there are more matrices, and it's not crazy to _hope_ for

the non-commutativity to add security compared to \F_{2^1024}. But if

(1) the subfields of \F_{2^1024} are a security disaster (this turns

out to be the case) and

(2) non-commutativity isn't enough to rescue the system (it turns

out to provide _no_ security benefit; see 1997 Menezes--Wu)

then the new system is a security disaster while, as far as we know, the

old one isn't.

So the proof is relating one weak problem to another weak problem.

Meanwhile it's misleading people into switching away from a strong

problem, even though the proof actually says _nothing_ about the strong

problem---the same way that the MLWE-vs.-RLWE proof says _nothing_ about

RLWE using fields outside a specially structured class.

This DH example illustrates the structural dangers inherent in (1)

constructing systems "with the objective of being able to give security

reductions for them" and (2) using this as a risk-assessment mechanism,

judging systems as less risky if they have more "security proofs". What

the proofs actually say about security is limited, and the limitations

have to be carefully taken into account.

6. Modules as a danger separate from cyclotomics

In the above matrix example, \F_{2^256} has a tower of subfields that

are unnecessary for DH, the same way that \Z[X]/(X^256+1) has many

subfields that are unnecessary for lattice-based cryptography, along

with further unnecessary structure such as being cyclotomic.

What happens if one removes this structure? Consider 4x4 matrices over

the prime field \F_p, where p is a 256-bit prime. "Provable security"

then highlights a relationship between these matrices and a 1024-bit

finite field \F_{p^4}.

Is it correct to say that the matrices are less structured than 1024-bit

fields? No, of course not. The proof is only for _extremely special_

1024-bit fields, the ones that have 256-bit prime subfields.

If this subfield structure opens up vulnerabilities (variants of NFS

that exploit subfields are an active research area today), and if these

are also vulnerabilities of the matrix system (which, again, turns out

to be the case; see 1997 Menezes--Wu), then moving from a 1024-bit prime

field to the matrix system has damaged security. So how can one portray

the proof as saying that moving to matrices is reducing risks?

What one sees here is that simply imposing the matrix structure, working

with 4x4 matrices over a field with 1/4 as many bits, is creating a new

security risk, a risk that is _not_ addressed by the "security proof".

Similar comments apply to lattice systems. Cyclotomics are particularly

worrisome, but _even outside the cyclotomic context_ it's entirely

possible that moving to modules---for example, a rank-4 module over a

quarter-dimension ring---damages security. There's certainly no proof to

the contrary.

Consider, as concrete examples, the following \Q-algebras:

(1) \Q[X]/(X^1024-X-1).

(2) \Q[X]/(X^1024-X^4-1).

(3) (\Q[X]/(X^256-X-1))^(4x4).

(4) \Q[X]^(1024x1024).

Here the argument for modules says that #1 is a small, structured piece

of #4, which is worrisome, and that #2 is a small, structured piece of

#4, which is worrisome, and that #3 is an intermediate case between #2

and #4, making it less worrisome.

But #2 and #3 both have special structure that doesn't exist in #1!

This isn't as extreme as the tower of cyclotomics mentioned above, but

again there's an intermediate algebra with special properties catching

the cryptanalyst's eye as a potential springboard for attacks: both

algebras contain \Q[X]/(X^256-X-1), which is much bigger than \Q, much

smaller than the full algebra, and in the center of the full algebra.

The presence of this special intermediate field could expose #2 and #3

to attacks that don't apply to #1, a field whose only proper subfield is

\Q.

Advocating a leap from #1 to #3, and trying to justify this by pointing

to a proof relating #2 to #3, is indefensibly exaggerating what the

proof says, and ignoring the security risk of introducing extra

subfields---again, something that has a long history of being exploited.

To summarize, what the advertising wants people to believe is that the

Kyber matrices are provably at least as strong as commutative rings

(acting on vectors of similar dimension). What the proof actually says

is, at best, that the Kyber matrices are at least as strong as some

_very special_ commutative rings, the rings used in NewHope. The proof

does _not_ say that the Kyber matrices are at least as strong as _other_

commutative rings. Closing this gap is hopeless.

7. Credits and subsequent discussions

The fundamental flaw in the module advertising was already pinpointed in

Section 5.5 of https://ntruprime.cr.yp.to/latticerisks-20211031.pdf (in

less detail than the explanation I've given above). I cited that paper

in my first message in the small-rounding thread:

Theorems that might give a "modules are guaranteed safe" impression have

limitations rendering them logically inapplicable to NISTPQC. See, e.g.,

Section 5.5 of https://ntruprime.cr.yp.to/latticerisks-20211031.pdf.

A followup a few days later, the message I'm responding to, repeats

essentially the same advertising---hiding the flaw inside a false

hypothesis.

[ context omitted by the message I'm replying to: ]

> > Let's try an example: the experiments reported in Section 4.2 of

> > https://www.ntru.org/f/hps98.pdf (the first paper Dr. Peikert cited).

> > These are attacking scaled-down versions of the original NTRU system.

[ context included in the message I'm replying to: ]

> > Why exactly is it supposed to be okay to count these experiments towards

> > "enough cryptanalysis" of systems that move to rank-3 modules over a

> > ring of only 1/3 dimension (e.g., kyber768),

> Because there are simple reductions that allow one to decrease the

> degree of the ring, while increasing the module rank.

> If R=Z[X]/(X^1024+1)

[ ... ]

> So if NTRU is over the ring R

This is the false hypothesis mentioned above.

The question was explicitly about the experiments in Section 4.2 of the

original NTRU paper. Those experiments used X^N-1 for various N; why

would they have detected security failures of X^N+1 with N being a power

of 2? Maybe failures of X^N+1 would show up for X^2N-1, but the

experiments didn't use any power-of-2 exponents. In short, no, this

isn't over the ring R; it isn't over _any_ power-of-2 ring.

The same hypothesis is, of course, also false for various NISTPQC KEMs,

such as sntrup1013.

Again, the (partial) proof that kyber1024 >= newhope1024 relies on the

fact that \Q[X]/(X^1024+1) has a much smaller subfield \Q[X]/(X^256+1).

What happens if the smallness and special structure of \Q[X]/(X^256+1)

turn out to be a security problem for _both_ kyber1024 and newhope1024,

a problem not shared by most fields---maybe even most cyclotomics?

Perhaps someone has in mind a _heuristic_ saying that if power-of-2

cyclotomics have a security problem then the problem will also show up

for many other cyclotomics. This essentially assumes away any potential

difference between power-of-2 cyclotomics and random cyclotomics. Maybe

this is a valid heuristic, but how well has it been tested?

Compare this to Dr. Peikert's message at the start of the small-rounding

thread: "The existing analyses essentially 'assume away' any potential

difference between deterministic rounding errors and random ones. Maybe

this is a valid heuristic, but how well has it been tested?"

If we're supposed to worry about the possibility that rounding loses

security, and the possibility that structure in matrices loses security,

shouldn't we worry about the possibility that power-of-2 cyclotomic

structure loses security, even compared to most cyclotomics? Where are

all the papers redoing every NTRU attack experiment for the power-of-2

case? Where are the objections to a lack of Kyber-specific experiments?

These possibilities are analogous in that none of these features have

been _proven_ secure. This is what I've been emphasizing in the last few

paragraphs---but it's also a _very_ low bar. Every lattice KEM has a

combinatorial explosion of features (obviously far beyond the number of

attack papers); only a narrow corner is proven secure; so it's trivial

to take any submission and selectively highlight a proof gap for that

submission. If this were done systematically then people would realize

how content-free it is. Instead it's against a backdrop of many other

proofs being indefensibly exaggerated, such as the MLWE-vs.-RLWE proof.

Correcting the exaggerations and studying how little the proofs actually

say makes clear that risk management has to be driven instead by the

literature designing and analyzing _algorithms_. What's truly concerning

about subfields, cyclotomics, etc. isn't the minimal point that they

haven't been proven safe. What's truly concerning is that these

structures have already been exploited for many years to speed up a wide

range of number-theoretic computations---often quite dramatically, as

illustrated by the quantum polynomial-time break of Gentry's original

STOC 2009 FHE system for cyclotomics (under minor assumptions), and the

non-quantum quasi-polynomial-time break of an analogous system using

multiquadratics (which aren't cyclotomic but have many subfields).

I understand that the magnitude of the danger isn't obvious to everyone.

But the idea that the danger has been _proven_ not to exist is absurd.

There's a specific fiction that leaping to rank-{2,3,4} modules, while

dropping the field degree correspondingly, has been proven to not lose

security; let's get that corrected for the record.

> what is your "concern" with the above?

First of all, for a mathematician, _any_ proof exaggeration is

unacceptable.

NIST wrote "In a technical sense, the security of NewHope is never

better than that of KYBER", pointing to a proof. But simply reading what

the proof says and comparing it to the NewHope-vs.-Kyber example shows

many reasons that, no, the proof _doesn't_ say that Kyber is at least as

strong as NewHope. (See generally my email dated 25 Jul 2020 10:36:57

+0200.) NIST didn't even bother to systematically _list_ those reasons,

never mind presenting an evaluation of the corresponding security risks.

This is horrifying.

The specific exaggeration that I'm emphasizing in this message doesn't

matter for NewHope in particular: as noted above, NewHope already had

\Q[X]/(X^256+1) present as a subfield. However, as part of the same

official report, NIST stated a much broader categorical preference for

"low-rank MLWE schemes over RLWE schemes"---evidently blind to the fact

that this leap requires inserting extra structure that could damage

security, structure that a pure RLWE system doesn't need. The proof does

_not_ provide any reason to think that (\Q[X]/(X^256+1))^(4x4) is as

safe as \Q[X]/(X^1013-X-1).

In short, readers are being led to believe that inserting the small

field \Q[X]/(X^256+1) into a system design is guaranteed safe---but the

argument presented for this starts by hypothesizing that \Q[X]/(X^256+1)

was already present as a subfield! This makes no sense.

> Is it:

> 1. It's possible that Module-LWE over random A'' is easy (so

> Kyber-1024 is easy), but Module-LWE over a structured A'' (i.e. the

> one you get from transforming A-->A'') is hard?

I have a clarification question regarding two general words here, "easy"

vs. "hard": are these supposed to refer to some _big_ gap in security?

Kyber's security margin seems to keep dropping and seems very small

(possibly nonexistent), so a small improvement in attacks could mean

that Kyber doesn't reach its claimed security level.

The rest of the specific text here seems like a pointless distraction

from the elephant in the room, the fact that the proof at hand compares

MLWE using \Q[X]/(X^256+1) to an _extremely restricted_ type of RLWE

system, one where \Q[X]/(X^256+1) is already present as a subfield.

> 2. That this reduction works only for dimensions that are a power of

> 2, so we can't say anything about Kyber-768 which has a 3x3 matrix A

> (i.e. maybe it's as hard as Kyber with a 2x2 matrix over the same

> ring).

In the absence of further information, one has to guess that the 3x3

case is stronger than the 2x2 case. But this is a weak statement given

that the 2x2 case is already on the bleeding edge against known attacks

and that the 3x3 case claims a _much_ higher security level.

Why resort to some weak 3-to-2 relation instead of talking about how

Kyber relates to some degree-768 extension of \Q[X]/(X^256+1), such as

\Q[X,Y]/(X^256+1,Y^3-Y-X)? Could this be because presenting such an

extension helps the reader realize that the 256*3 -> 768 proof is

restricted to a narrow, specially structured set of degree-768 fields?

> Both of these "objections", however, are counter to a lot of the

> theory that underlies lattice cryptography. (1) contradicts that

> random matrices A are the hard instances and (2) contradicts that

> increasing the dimension makes the lattice problem harder.

This text also seems like a distraction from the elephant.

> So if you're going to state hypotheses that go against established

> theory, you need to have some evidence. Otherwise, one can state anything

> that can't be proved or disproved -- (e.g. do you have concrete proof

> contradicting the Qanon and the covid vaccine conspiracies? No? Then I

> guess you should consider them to be as valid as their negations.)

This level of rhetoric regarding the nature of evidence is in a message

that starts from an outright false assumption regarding the stated

context and ignores an earlier reference to a paper explaining the gap?

Hmmm.

> The difference between saying (1) LWE is hard, but LWR with small

> rounding could be easy and (2) NTRU is hard, but Module-LWE could be

> easy is that (1) does not contradict any of the underlying theory or

> understanding upon which lattice crypto is built, whereas (2) would

> mean that the core of the established theory is wrong.

Please clarify.

What's covered by "the underlying theory or understanding upon which

lattice crypto is built"? Is this excluding, e.g., the original LLL

paper, the original BKZ paper, the original NTRU paper, and many more

years of design and analysis of algorithms? If this excludes papers on,

e.g., class-group computations, then what's the rationale for excluding

those, and how does this avoid making the argument circular?

How precisely would weaknesses triggered by the smallness and special

structure of \Q[X]/(X^256+1) contradict "the established theory"?

It's disturbing to see a message that's so driven by "security proofs"

that it makes a hypothesis that's false regarding the explicit context

and often false for NISTPQC---simply _assuming_ that one is starting

with particular field structures, because this is what has to be done to

make the proof work---and then tries to lead the reader to believe that

the existing "theory and understanding" guarantee the safety of modules,

evidently with no need to even _look_ at what's known about algorithms

exploiting those field structures.

---Dan

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu