Soliloquy

[D. J. Bernstein]

At PKC 2010, Smart and Vercauteren introduced an ideal-lattice-based
fully homomorphic encryption scheme. They said that one-wayness and key
recovery of this scheme were "related to well studied problems in number
theory". See https://eprint.iacr.org/2009/571.

GCHQ announced a few months ago that in 2007 it had (quietly) designed
an ideal-lattice-based post-quantum encryption scheme, but that between
2010 and 2013 it had developed a fast key-recovery attack. For links see
https://www.schneier.com/blog/archives/2014/12/quantum_attack_.html.

Now here's the scary part: There don't seem to be any relevant
differences between the GCHQ scheme ("Soliloquy") and the SV scheme! In
both cases the public key is an ideal lattice that was secretly built to
have a short generator, and the key-recovery problem is to find a short
generator. SV seem to say this is hard; GCHQ seems to say this is easy.

One could imagine that "post-quantum" is the explanation: these schemes
are secure against pre-quantum attacks but broken by quantum computers.
I've seen more and more claims that lattice-based cryptography is secure
against quantum computers, so a quantum attack against a lattice-based
scheme is clearly big news. However, it seems to me that the damage is
even worse: there's an idea here that drastically weakens the schemes
even _without_ quantum computers.

Let's dive into the algorithms. Everybody starts the same way, namely
evaluating and optimizing the complexity of the computational number
theorist's standard approach to find generators of principal ideals.

First stage: Compute the class group, the unit group, and _some_
generator, expressed as a product of powers of small field elements. (In
a nutshell: try to factor many field elements as products of powers of
various ideals, namely small prime ideals and the input ideal; and then
solve this system of equations.)

Smart and Vercauteren quote a cost estimate that's more than exponential
in the field degree. What they write is literally an upper bound, not a
lower bound, but they seem to think that the computation actually scales
as poorly as the upper bound suggests.

My blog post http://blog.cr.yp.to/20140213-ideal.html says that this is
all wrong: the computation, optimized sensibly, should be heavily
subexponential in the field degree. There was already serious
optimization work and complexity analysis, notably from Biasse (see
http://www.lix.polytechnique.fr/~biasse/), and I don't think anyone
believes the SV view at this point.

As for quantum computers: SV claim that these problems are "relatively
easy" on quantum computers, quoting Hallgren's 2005 paper. This is an
overstatement of that paper---the paper was quantum poly-time for fixed
degree but ran into serious obstacles as the degree grows.

New work gets around all of those obstacles. Specifically, a paper from
Eisenträger, Hallgren, Kitaev, and Song computes the unit group in
quantum poly-time for variable degree, and a followup paper from Biasse
and Song does the same for the class group and a generator. (Apparently
GCHQ came up with some similar ideas here, but kept the ideas secret.)

Second stage: Reduce _some_ generator to a _short_ generator.

Smart and Vercauteren say, correctly, that the generator found in the
first stage won't be short. They don't even cite reduction methods, let
alone quantify the difficulty of the reduction.

The standard method (presumably Dirichlet?) is to solve CVP in the unit
lattice. Of course, this isn't easy as the dimension grows: we all know
that the best CVP algorithms take exponential time. There's interesting
recent news from Laarhoven regarding the exponent, but this still looks
like a much more serious problem than, e.g., the class-group
precomputation, or the computation of _some_ generator.

My blog post has something new at this point, namely reducing the
dimension of the lattice by first solving the same problem in subfields.
I think that the practical consequences of this are worth exploring, and
that it's slightly subexponential in some cases. I recommended removing
this structure by switching to, e.g., x^p-x-1 fields ("NTRU Prime").

What GCHQ says at this point is much more dramatic: namely, that for
them this step isn't a problem at all!

When I first looked at the GCHQ slides, I found a "simplifying
assumption" that "we can recover" a short generator from "_any_
generator". I dismissed this as silly: skipping over the slow step of
the computation and focusing on optimizing the fast step. I'm indebted
to Regev for pointing out to me a few weeks ago (at the DIMACS Workshop
on the Mathematics of Post-Quantum Cryptography) that GCHQ actually
_has_ a plausible method to quickly reduce any generator to a short
generator---assuming that the field is cyclotomic.

This suggests the following scorecard for the short-generator problem:

* Cyclotomic, post-quantum: Breakable in polynomial time.
* Cyclotomic, pre-quantum: Breakable in subexponential time.
* Safe fields, post-quantum: No change---exponential time.
* Safe fields, pre-quantum: No change---exponential time.

So how does the cyclotomic-field generator-reduction method work?

Remember that CVP is very easy to solve for typical vectors (Babai) if
you've precomputed a very good basis for the lattice. The point here is
that for cyclotomics you can simply _write down_ a very good basis.

To see where this basis comes from, let's start with exactly the
structure used in many "security proofs" in this area, namely the (many)
automorphisms of cyclotomic fields. If z is an nth root of unity, and k
is coprime to n, then there's an automorphism of \Q(z) mapping z to z^k.

Applying this automorphism to z-1 produces z^k-1, which is divisible by
z-1 in \Z[z]. Applying the inverse automorphism (i.e., viewing z as a
power of z^k) shows that z-1 is divisible by z^k-1 in \Z[z]. Hence the
ratio (z^k-1)/(z-1) is a unit in \Z[z].

Now here's the recipe: Write down these units for each k coprime to n
with 1<k<n/2, and take logs. At this point it's reasonable to hope that
you have a very good basis for the unit lattice.

I'm skipping over some minor obstacles here:

* Maybe there are units of \Z[z] that aren't what number theorists
call "cyclotomic units"---units that are products of powers of z,
1-z, 1-z^2, 1-z^3, etc.

If the logs of cyclotomic units have index j in the logs of all
units then there's chance 1/j of a "random" generator being the
desired generator times a cyclotomic unit. Computing the class
group has the side effect of showing how big j is, and everybody
believes (from existing computations) that j is always very small.

* Maybe the logs of (z^k-1)/(z-1) don't generate the lattice of logs
of all cyclotomic units.

This problem doesn't exist when n is a power of a prime (the usual
situation in lattice-based cryptography), and for the general case
one can replace (z^k-1)/(z-1) with slightly more complicated
formulas. See, e.g., Chapter 8 of Washington's Introduction to
Cyclotomic Fields.

It's also important to quantify the angles between these easily
constructed units, but my impression from Regev is that GCHQ tried this
(at least for the values of n that they cared about) and found that the
basis was always very good.

---Dan

[Chris Peikert]

(An HTML version of this message can be found at

http://www.cc.gatech.edu/~cpeikert/soliloquy.html )

Dan Bernstein recently wrote about a neat new attack by

Campbell-Groves-Shepherd of GCHQ on their homegrown Soliloquy

public-key cryptosystem.  The attack also turns out to apply equally

well to the Smart-Vercauteren fully homomorphic encryption scheme from

PKC'10, and the Garg-Gentry-Halevi multilinear map candidate from

Eurocrypt'13.  These proposals belong to an exciting and rapidly

growing body of work on lattice-based cryptography.  What further

distinguishes these three systems is the particular way they rely on

(principal) ideal lattices in certain algebraic rings.  For

simplicity, this note mostly refers to Soliloquy, but everything I

write applies equally well to all three systems.

The GCHQ attack is a *quantum* algorithm that breaks Soliloquy in

polynomial time (under some standard number-theoretic heuristics).

Alternatively, the quantum part of the attack can be made non-quantum,

yielding a subexponential running time of about 2^(n^1/3), where n is

the dimension of the ideal lattices.  For more background, see the

paper at

http://docbox.etsi.org/Workshop/2014/201410_CRYPTO/S07_Systems_and_Attacks/S07_Groves_Annex.pdf

, Dan's summary at

https://groups.google.com/forum/#!topic/cryptanalytic-algorithms/GdVfp5Kbdb8

, and Dan's earlier blog post on similar topics at

http://blog.cr.yp.to/20140213-ideal.html .

In this note I'd like to shed some more light on the implications of

the GCHQ attack for ideal/lattice-based cryptography more broadly, and

what lessons we might take away from it.  It's helpful to read the

above links first, but not necessary.  (By way of background, I have

been working almost exclusively on ideal/lattice-based cryptography

since 2005.  I thank Dan Shepherd, Oded Regev, Leo Ducas, and Craig

Gentry for many discussions that influenced this note.)

My main points are as follows:

1.  "Lattice-based" cryptosystems are not based on "lattices" per se,

    but rather on certain *computational problems* on lattices.  There

    are many kinds of lattice problems, not all of which appear to be

    equally hard -- therefore, not all lattice-based cryptosystems

    offer the same qualitative level of security.  For ideal lattices,

    the choice of *problem* matters at least as much as the choice of

    *ring*.

2.  Soliloquy is *not* representative of modern ideal/lattice-based

    cryptography.  In contrast to the vast majority of works in the

    area, Soliloquy does not come with any meaningful security

    proofs/reductions.  Moreover, it relies on a more specialized --

    and hence potentially easier to break -- lattice problem.

3.  The GCHQ attack works because Soliloquy unexpectedly turns out to

    rely on "weak ideals" that can be broken more efficiently than

    general ideals.  There is a direct link between the lack of

    security reduction and this unforeseen reliance on weak ideals.

4.  The GCHQ attack *does not* affect the vast majority of

    ideal-lattice-based cryptosystems.  In particular, it does not

    work against any system that has a "worst-case" security proof via

    the Ring-LWE or Ring-SIS problems.

5.  This state of affairs underscores the importance of worst-case

    security proofs in ideal/lattice-based cryptography.  Among other

    advantages, such proofs ensure that a cryptosystem does not have

    any unexpected reliance on "weak" instances.

Before diving into the details, let's warm up with something more

familiar.

=== AN ANALOGY: FACTORING VERSUS RSA ===

In number-theoretic cryptography, not all problems are thought to be

equally hard (or easy).  For example, consider the integer

factorization problem and the related RSA problem.  We know that if

factoring were to turn out to be easy, then the RSA problem would also

be easy: factoring the public modulus gives all the information needed

to break RSA.  However, it's unknown whether the reverse implication

holds -- it might be the case that the RSA problem is easy (or merely

"somewhat hard"), while integer factorization remains hard.  In this

sense, we know that RSA is "no harder, and possibly easier" than

factoring.  So all else being equal, if cryptosystems X and Y have

security based respectively on the factoring and RSA problems, we

should prefer system X for its stronger security guarantee.  (Of

course, it is commonly believed that RSA and factorization are both

about equally hard.  But this is still just a conjecture; we don't

really know one way or the other.)

Now, the story is not quite so simple as this, because cryptography

inherently deals with *average-case* problems, where instances are

generated at random.  For example, a cryptosystem might generate a

random integer N=p*q, where p and q are random primes that are nearly

equal.  This would be very unwise, because such numbers N turn out to

be very easy to factor!  (Hint: p and q are both very close to the

square root of N.)  There are many clever algorithms that can quickly

factor numbers having various other special forms.  We call such

numbers "weak composites," because they are easy to factor -- despite

the belief that factoring integers is hard in general.

Obviously, any cryptosystem that relies on the hardness of factoring

must avoid generating weak composites.  But here is an inconvenient

truth: we don't know all the ways in which a composite might be weak

-- so we certainly can't test for them all!  Instead, it is typical to

simply *conjecture* that a random composite generated in a certain way

has an extremely small chance of being weak.  But we don't really have

any compelling evidence for this belief -- it might turn out to be

easier to factor such random composites than it is to factor arbitrary

composites.  Indeed, many proposed cryptosystems over the years have

turned out to be insecure exactly because of this reason.

To sum up so far:

1. Not all (factoring-related) problems are equally hard.

2. The "average case" for a problem may be easier than the "worst

   case."

=== LATTICE PROBLEMS ===

Now back to lattice-based cryptography.  Saying that a cryptosystem is

"lattice-based" is helpful as a first-order categorization, but not

all such systems are created equal, because they involve different

kinds of lattice problems.  Some commonly used problems in lattice

crypto, arranged in non-increasing order of hardness, include the

following (the meanings of the acronyms aren't important):

    SIVP: Given a lattice, find a full-rank set of lattice vectors

    where the longest such vector is nearly as short as possible.

    BDD: Given a lattice and a target point that is promised to be

    "rather close" to some lattice vector v, find v.

    Ideal-SVP/BDD: same as above, but specialized to *ideal* lattices

    in a certain ring R.  Ideal lattices have additional geometric

    symmetries arising from the algebraic properties of the ring.

    (Due to the ideal structure, SIVP is equivalent to finding just

    one non-zero lattice vector whose length is nearly as short as

    possible.  This is why we use the name SVP instead.)

    Principal-SVP: same as Ideal-SVP, but specialized to *principal*

    ideal lattices in a certain ring R.  A principal ideal is of the

    form g*R for some element g in R, called a "generator," although

    the attacker is not given g itself.  (For commonly used rings,

    principal ideals are an extremely small fraction of all ideals.)

Given the choice between, say, SIVP and the more specialized (and

hence potentially easier) Ideal-SVP or even Principal-SVP, why would

anyone opt to design a cryptosystem using the latter problems?  There

are a few common reasons.  One is efficiency: the additional structure

of ideals allows for much smaller keys and much faster operations --

roughly linear versus quadratic.  So if Ideal-SVP happens to be about

as hard as SIVP, it offers a much better security/efficiency tradeoff.

Another reason is functionality: to obtain a certain desirable

feature, a cryptographer might need to use lattices or rings that have

a particular structure.  Yet another reason might be technical or

conceptual simplicity (this was a stated goal of both

Smart-Vercauteren and Soliloquy).

=== (WORST-CASE) SECURITY PROOFS IN LATTICE CRYPTOGRAPHY ===

The vast majority of modern lattice-based cryptosystems -- by my

estimate, at least 90% of papers appearing in top venues in the past

10 years -- are **provably based on** the SIVP/BDD problems, or their

Ideal-SVP/BDD variants.  Here the phrase "provably based on" means the

following very strong guarantee:

   There is a mathematical proof that the *only* way to break the

   cryptosystem (within some formal attack model) on its random

   instances is by being able to solve the underlying lattice problem

   in the *worst case*.

Such a proof is given by a "worst-case reduction:" a transformation

that converts any successful attack on the cryptosystem into a

comparably efficient algorithm that solves *any* instance of the

underlying problem.  The worst-case reductions for most cryptosystems

are obtained in two parts.  First, one gives a reduction that bases

the cryptosystem's security on one of a few natural average-case

problems, called (Ring-)SIS and (Ring-)LWE.  Then, one simply invokes

prior worst-case reductions that have based (Ring-)SIS/LWE on

(Ideal-)SIVP/BDD.

A worst-case reduction for a cryptosystem is a very powerful thing.

It means that to evaluate the cryptosystem's security, it is enough to

focus one's attention on the underlying worst-case problem, which is

typically much simpler and more mathematically natural than the

cryptosystem itself.  As long as *some* instances of the underlying

problem are actually hard, we are assured that the cryptosystem is

secure -- in particular, it does not have any "unexpected" design

flaws, such as a reliance on weak random instances.  Moreover, many

different kinds of cryptosystems can be based on the same few

underlying problems, which lets us reuse previous cryptanalytic effort

(rather than starting from scratch for every new cryptosystem).

Of course, having a reduction does not say anything about whether the

underlying problem is actually hard!  Just as it's possible that RSA

is actually easy while factoring remains hard, it might be the case

that, say, Ideal-SVP is easy (in some or all rings) while SIVP remains

hard in general.  Fortunately, many experts have attempted to solve

the Ideal-SVP/BDD problem, including in highly "structured" rings like

cyclotomics, and even using the power of quantum algorithms.  Yet

nobody has been able to come up with any algorithm for Ideal-SVP/BDD

that significantly outperforms those for the more general SIVP/BDD

problems.  This state of affairs could change overnight if someone

just discovers a clever new idea, but the same can be said for all

problems used in cryptography -- it's an inherently risky business,

and we make the best bets we can.

(An aside: from a practical point of view, having a security reduction

is just the beginning.  One needs to determine whether the formal

attack model is realistic for the application, choose parameters for a

desired concrete level of security, implement everything correctly,

etc. etc.  But here, as in Dan's posts, I am only concerned with

purely mathematical attacks and their asymptotic behavior.)

=== A FEW WORDS ON CYCLOTOMICS ===

Problems on ideal lattices are always phrased in terms of a particular

choice of ring, and *cyclotomic rings* are very common choices.  Dan

argues in his posts that cyclotomics are not safe, because they have a

lot of structure: many subrings, many automorphisms, etc.  One might

worry that all this structure will someday lead to good attacks on

Ideal-SVP or other important problems in cyclotomic rings.  It is a

fair concern, but at this point it is all just speculation.  Although

cyclotomics have a lot of structure, nobody has yet found a way to

exploit it in attacking Ideal-SVP/BDD (and hence Ring-LWE as well).

One could even argue that the popularity of cyclotomics makes them

*more* secure, because they have received most of the cryptanalytic

effort so far -- and there's still nothing to show for it!  I don't

find any of this too convincing one way or the other.  Unfortunately,

we just don't have very meaningful ways of comparing ideal-lattice

problems across entirely different kinds of rings (it's a great

research question!).  So to claim that one kind of ring is safer than

another simply because it has "less structure" is premature;

"structure" has no precise definition, and structure that doesn't help

the attacker causes no harm.

Dan's post also suggests that the GCHQ attack on Soliloquy is somehow

innately related to the structure of cyclotomics.  As we'll see, the

attack probably doesn't have much to do with cyclotomics per se;

they're just the kind of rings Soliloquy happened to be defined over.

What's much more important than the kind of ring is the *particular

ideal-lattice problem* that the attack solves.  As we'll see next,

this problem is quite a bit different from what Ring-LWE and most

ideal/lattice crypto are based upon.

=== SOLILOQUY AND THE GCHQ ATTACK ===

In Soliloquy, a secret key is chosen as a random short ring element g,

and the corresponding public key is the principal ideal lattice g*R

generated by g.  Knowing any sufficiently short vector of the lattice

(not necessarily g itself) allows one to decrypt, so solving the

Principal-SVP problem would clearly break these schemes.  Note already

that Principal-SVP is a more specialized -- and hence potentially

easier -- problem than Ideal-SVP (the problem that Ring-LWE is

provably based upon).  But what's even more important to realize is

that there might be alternative attacks on Soliloquy that do *not*

involve solving Principal-SVP at all!  Unlike the cryptosystems

described above, Soliloquy does not come with any proof that breaking

it is *at least as hard as* Principal-SVP (or any other problem) -- we

can only say that breaking them is *no harder than* Principal-SVP.

Indeed, the GCHQ attack manages to break Soliloquy without solving

Principal-SVP in general.  The attack exploits the fact that the

random ideals generated by Soliloquy are "weak" in a previously

unnoticed way -- they have additional structure that make them much

easier to attack.  Going back to the analogy with factoring, Soliloquy

ideals are like composites N=p*q where p and q are nearly equal.

The main lever behind the GCHQ attack is the fact that the public

ideal is implicitly guaranteed to have a *short* generator g.  This

fact is so important that it's worth defining a specialized problem to

capture it:

    SG-Principal-SVP: same as Principal-SVP, but specialized to

    principal ideals that are promised to have a short generator g.

    (Such ideals are a very small fraction of all principal ideals.)

The GCHQ attack demonstrates that SG-Principal-SVP is not so hard.

Specifically, it can be solved in polynomial time quantumly, and in

subexponential time classically, in certain cyclotomic rings (and

possibly other rings).  This is much better than the best known

attacks against Principal-SVP in general.  In essence, **the mere

guarantee of a short generator** makes an ideal "weak."

At a technical level, the fact that the public ideal has a short

generator g means that, given an arbitrary generator h of the ideal,

it is very easy to recover not just a short vector, but g itself!

This works using the classical technique of decoding the "log-unit"

lattice using a known good basis.  The Soliloquy paper omits

essentially all the details here, which is why all the experts I've

talked to about it were initially quite skeptical (more on this

below).  But with some help from the authors, we have verified that

the attack does indeed work both asymptotically and in practice, even

in very large dimensions, using a natural and well-known basis for the

log-unit lattice.  (A paper with Ronald Cramer, Leo Ducas, Oded Regev

is coming soon.)

=== DISCUSSION ===

Although Dan's description of the attack is given in terms of

cyclotomic rings and their automorphisms, these objects are not really

so essential to the attack.  All one needs to break SG-Principal-SVP

in a given ring is a reasonably good basis of the ring's log-unit

lattice, and it's reasonable to expect that such bases exist and can

be found for many classes of rings.  The weakness here is not so much

due to the structure of cyclotomics, but rather to the extra structure

of principal ideals that have short generators.

The techniques used in this attack on SG-Principal-SVP already fail to

work on the more general Principal-SVP problem -- the "SG" promise

seems essential.  For an arbitrary principal ideal, the attack may

find a (nearly) shortest generator.  But for the vast majority of

principal ideals, even the shortest generator is an invalid solution

to Principal-SVP, because it is *much* longer than the shortest

lattice vector, by a factor of 2^sqrt{n} or so.

While it is obvious that Soliloquy ideals have short generators, for

years the *importance* of this fact went unnoticed by Dan, me, and

nearly every other expert in the area.  This is all the more striking,

because the central technique of decoding the log-unit lattice is very

well known, and several of us had independently considered (and

eventually abandoned) the idea as a potential attack on Principal-SVP!

We simply hadn't realized that the added guarantee of a short

generator would transform the technique from useless to devastatingly

effective.

My point is this: prior to the GCHQ attack, one might have believed

that Soliloquy is "based on" the Principal-SVP problem.  But there was

no proof to justify this belief -- no worst-case reduction.  So unlike

for cryptosystems that have such reductions, we can only say that

Soliloquy is "related to" or "relies on" Principal-SVP -- we don't

have a lower bound on security, only an upper bound.  Indeed, now we

know that Soliloquy isn't based on Principal-SVP at all, but instead

relies on a specialized variant that appears much easier.  And this

too is still just an upper bound; Soliloquy may yet turn out to be

even easier to break for other reasons.

=== CONCLUSIONS ===

What does all this mean for ideal/lattice cryptography as a whole?

Should we be skeptical about how secure it is secure against quantum

attacks, or even non-quantum attacks?  Healthy skepticism is always

warranted (especially in cryptography), but based on these new

developments, I don't believe our level of skepticism should rise much

from where it was before.

My first conclusion is that the SG-Principal-SVP problem should now be

viewed with great suspicion, in essentially any ring -- not just

cyclotomics.  Fortunately, SG-Principal-SVP is a very specialized

problem that is irrelevant to the vast majority of lattice-based

cryptosystems, including those based on Ring-LWE, and hence on

Ideal-SVP/BDD.

My second conclusion is that for an ideal-lattice-based cryptosystem,

the particular choice of lattice *problem* can matter at least as much

as (if not more than) the choice of *ring*.  Rings themselves are not

"easy/weak" or "hard/strong" -- problems and their instances are.  The

GCHQ attack shows that specializing a problem too much, or relying on

random instances whose distribution we don't really understand, can

introduce unexpected weaknesses.

My final conclusion is that worst-case security reductions are really

important in lattice cryptography, where there is so much rope to hang

oneself with (i.e., flexibility in generating random instances).  In

return for the discipline they impose, worst-case reductions give a

hard-and-fast guarantee that the cryptosystem is at least as hard to

break as the *hardest* instances of some underlying problem.  This

gives a true lower bound on security, and prevents the kind of

unexpected weaknesses that have so often been exposed in schemes that

lack such reductions.

[D. J. Bernstein]

Chris Peikert writes:
> All one needs to break SG-Principal-SVP in a given ring is a reasonably
> good basis of the ring's log-unit lattice, and it's reasonable to
> expect that such bases exist and can be found for many classes of rings.

Of course the lattice _has_ a good basis, but why should a good basis be
easy to find? Here are the approaches that we've seen:

* For arbitrary number fields: find enough smooth relations to
compute _some_ basis for the unit group (subexponential time, or
quantum polynomial time); and then apply generic SIVP techniques
(exponential time).

* For number fields with many subfields: maybe faster as explained in
my blog (translated from generators to units), possibly slightly
subexponential time in extreme cases.

* For cyclotomics: simply _write down_ a good basis (polynomial
time), as GCHQ suggested.

Presumably this picture will be further refined and clarified, but I'm
surprised that you'd expect the whole thing to collapse down to an easy
problem. Are lattices arising from number fields more suspicious than
"random" lattices? Do you have in mind a fast algorithm to find many
short lattice vectors in the general case?

Such an algorithm would, I think, be a solid step towards breaking much
larger parts of ideal-lattice cryptography. For example, I think that
short nonzero vectors in NTRU lattices for a degree-n field can be
viewed as short generators of principal-ideal lattices for a degree-2n
field, implying that degree-n NTRU would be broken by a solution to the
short-generator problem for the degree-2n field.

---Dan

[Christopher J Peikert]

Chris Peikert writes:
> All one needs to break SG-Principal-SVP in a given ring is a reasonably
> good basis of the ring's log-unit lattice, and it's reasonable to
> expect that such bases exist and can be found for many classes of rings.

Of course the lattice _has_ a good basis, but why should a good basis be
easy to find?

I am very glad you asked this question; my note was already far too long to explain this in any depth.

Let me first be clear about the context here: in almost all schemes involving ideal lattices (including the alternative proposal from your blog post), the ring itself is fixed for the entire world to use.  Then, individual instances -- ideals, Ring-LWE samples, or whatever -- are chosen as keys.  (One could imagine also randomly choosing a ring as part of the key, but this is very uncommon and would probably not be desirable for other reasons.)

Therefore, the proper way to think about computing a good basis for the log-unit lattice is as a "preprocessing" problem.  That is, the adversary knows the ring in advance of the instances/keys it may want to break, and can expend some effort to compute a good basis (or whatever else it may find useful).  Then, it can use the results of the preprocessing to attack all keys that ever have been or will be generated.

For this reason, to be conservative we should treat the preprocessing step as computationally "free" for the attacker, not caring about how much it actually costs.  I am not claiming that it really *is* free -- only that it is safer to treat it as if it could be free, because it's a fixed one-time cost that is amortized over all keys in the world.  We should only count the adversary's "online" effort to break keys/instances after completing the preprocessing.  By doing the accounting this way, assuming the online effort really is large, we remain safe even if someone expends a huge one-time effort on the ring itself -- or worse, comes up with a really fast way of doing it.

Indeed, for power-of-two cyclotomics the preprocessing really is free, because we can obtain a basis that happens to be good just by looking it up in a book, or working it out with pen and paper.  We should not be surprised if the same can be done for other reasonable-looking number fields, such as the ones you proposed using in your blog post.

This is why my first stated conclusion was that the SG-Principal-SVP problem is highly suspicious, no matter the ring -- because with preprocessing, the online cost of solving it is essentially zero.

Presumably this picture will be further refined and clarified, but I'm
surprised that you'd expect the whole thing to collapse down to an easy
problem. Are lattices arising from number fields more suspicious than
"random" lattices? Do you have in mind a fast algorithm to find many
short lattice vectors in the general case?

By "lattices arising from number fields" I assume you still mean log-unit lattices.  At the risk of repeating myself: for evaluating security, I don't much care whether computing a good basis for the log-unit lattice in a given number field is cheap or expensive -- I'll just be safe and assume that the adversary can do it cheaply.  (Nevertheless, it is a nice algorithmic question.  I just wouldn't rely on it for any security.)

If by "lattices arising from number fields" you mean individual ideal lattices, then I care very much about how hard these are -- because they are the foundation for the Ring-LWE problem!  While ideal lattices obviously have much more structure than "random" lattices, nobody has yet been able to exploit that fact for solving Ideal-SVP in the worst case, despite quite serious attempts by some great minds (and mine as well).

 

Such an algorithm would, I think, be a solid step towards breaking much
larger parts of ideal-lattice cryptography. For example, I think that
short nonzero vectors in NTRU lattices for a degree-n field can be
viewed as short generators of principal-ideal lattices for a degree-2n
field, implying that degree-n NTRU would be broken by a solution to the
short-generator problem for the degree-2n field.

I would be very interested to know if this is really true.  I think people have attempted such a connection in the past, but to my knowledge it has never worked out.  NTRU lattices have a "quasi-cyclic" structure, in which the two halves of the 2n coordinates "rotate" in concert -- I don't know whether this can be encoded as a principal ideal in a degree-2n number field.

However, suppose it did work out, and NTRU -- which does not have any security reduction, worst-case or otherwise -- does indeed fall to an attack on the SG-Principal-SVP problem.  Then this would be another piece of evidence in favor of having worst-case security reductions from harder problems like Ideal-SVP.

Chris

[Christopher J Peikert]

A correction/clarification:

 

This is why my first stated conclusion was that the SG-Principal-SVP problem is highly suspicious, no matter the ring -- because with preprocessing, the online cost of solving it is essentially zero.

The online cost is zero for quantum.  For non-quantum, it is at most subexponential.

[Vadim Lyubashevsky]

Such an algorithm would, I think, be a solid step towards breaking much
larger parts of ideal-lattice cryptography. For example, I think that
short nonzero vectors in NTRU lattices for a degree-n field can be
viewed as short generators of principal-ideal lattices for a degree-2n
field, implying that degree-n NTRU would be broken by a solution to the
short-generator problem for the degree-2n field.

I would be very interested to know if this is really true.  I think people have attempted such a connection in the past, but to my knowledge it has never worked out.  NTRU lattices have a "quasi-cyclic" structure, in which the two halves of the 2n coordinates "rotate" in concert -- I don't know whether this can be encoded as a principal ideal in a degree-2n number field.

However, suppose it did work out, and NTRU -- which does not have any security reduction, worst-case or otherwise -- does indeed fall to an attack on the SG-Principal-SVP problem.  Then this would be another piece of evidence in favor of having worst-case security reductions from harder problems like Ideal-SVP.

The existence of a map that Dan mentions would be quite scary for all of ideal lattice crypto -- proofs or not.  As Chris said, NTRU lattices have a quasi-cyclic structure where the two halves of the 2n coordinates "rotate in concert".  But analogously, Ring-LWE lattices have a quasi-cyclic structure where the three thirds of the 3n coordinates "rotate in concert", and the elements are basically just as short as in NTRU lattices.  So presumably, if one could transform an NTRU lattice into a principal ideal lattice of dimension 2n, one could possibly do the same thing with a Ring-LWE lattice into dimension 3n.  This is of course not a proof and there could be some weird reason that it works for NTRU and not for Ring-LWE, but it would be kind of surprising (and very enlightening). 

So to me, it's this quasi-cyclic structure of the lattices underlying both NTRU and Ring-LWE that seems to be the source of the hardness. In this respect, I don't see a separation between NTRU and Ring-LWE.  It may also be the case that these average case problems (NTRU and Ring-LWE) are actually harder than the worst-case problem from which we gave reductions for Ring-LWE and Ring-SIS.  Let me ask a more general version of Dan's question as to whether maps from NTRU lattices to principal ideals exist.  Suppose you have an oracle that finds short vectors in *all* ideals of the ring of integers of Q[x]/f(x), can it help to solve the NTRU or the Ring-LWE problem over some ring Z_q[x]/g(x) for a cyclotomic g(x) (or perhaps even for a non-cyclotomic, but still irreducible, g(x) with a weird connection to f(x) as a starting point)?  

-Vadim

 

Chris

[Christopher J Peikert]

Such an algorithm would, I think, be a solid step towards breaking much
larger parts of ideal-lattice cryptography. For example, I think that
short nonzero vectors in NTRU lattices for a degree-n field can be
viewed as short generators of principal-ideal lattices for a degree-2n
field, implying that degree-n NTRU would be broken by a solution to the
short-generator problem for the degree-2n field.

I would be very interested to know if this is really true.  I think people have attempted such a connection in the past, but to my knowledge it has never worked out.  NTRU lattices have a "quasi-cyclic" structure, in which the two halves of the 2n coordinates "rotate" in concert -- I don't know whether this can be encoded as a principal ideal in a degree-2n number field.

However, suppose it did work out, and NTRU -- which does not have any security reduction, worst-case or otherwise -- does indeed fall to an attack on the SG-Principal-SVP problem.  Then this would be another piece of evidence in favor of having worst-case security reductions from harder problems like Ideal-SVP.

The existence of a map that Dan mentions would be quite scary for all of ideal lattice crypto -- proofs or not.  As Chris said, NTRU lattices have a quasi-cyclic structure where the two halves of the 2n coordinates "rotate in concert".  But analogously, Ring-LWE lattices have a quasi-cyclic structure where the three thirds of the 3n coordinates "rotate in concert", and the elements are basically just as short as in NTRU lattices.  So presumably, if one could transform an NTRU lattice into a principal ideal lattice of dimension 2n, one could possibly do the same thing with a Ring-LWE lattice into dimension 3n.  This is of course not a proof and there could be some weird reason that it works for NTRU and not for Ring-LWE, but it would be kind of surprising (and very enlightening).

That's a good point -- NTRU is closer to Ring-LWE than it is to Soliloquy.

In addition to the quasi-cyclic structure, there is yet another obstruction to expressing an NTRU or Ring-LWE lattice as an ideal with a short generator: the "mod-q" structure.  It's too much to hope that the short 2n-dim vector in an NTRU lattice generates the lattice as an ideal, because this doesn't account for the mod-q arithmetic.

In conclusion, NTRU and Ring-LWE lattices do not appear to be principal ideals, or even ideals at all, but merely R_q-modules.  I agree with Vadim that this appears to be a significant source of the apparent hardness of these problems.  I also agree that NTRU and Ring-LWE could even be concretely *harder* than Ideal-SVP in the same ring; the reductions give a lower bound, and based on current cryptanalysis this bound doesn't appear to be very tight.

Chris

[D. J. Bernstein]

Christopher J Peikert writes:
> I am not claiming that it really *is* free -- only that it is safer to
> treat it as if it could be free, because it's a fixed one-time cost
> that is amortized over all keys in the world.

Underestimating the attack cost isn't necessarily "safer". Consider the
problem faced by a user who wants to choose the strongest system that he
can, subject to performance constraints: maybe X is stronger than Y, but
your underestimate of the security of X is _below_ your underestimate of
the security of Y, misleading the user into choosing Y.

For a more detailed discussion of this problem, including an example of
how the "safer" approach produces significantly _less_ secure parameter
choices for DSA, see Appendix B.1.2 ("The more-conservative-is-better
fallacy") in http://cr.yp.to/papers.html#nonuniform.

It's of course true that the attacker will amortize precomputations
across keys when possible. Even better, in many situations there are
_batch_ algorithms that handle many keys more efficiently than handling
each key separately. But the attacker does have to pay the startup cost,
not just the incremental cost per key. The startup cost is often huge
and is poorly predicted by the incremental cost, so it's important for
us to analyze the whole algorithm and understand the total cost.

As another example, Section 3 of http://cr.yp.to/papers.html#nonuniform
says how to break NIST P-256 in 2^85 operations, after a precomputation
that uses 2^170 operations. Saying that we should measure this as 2^85
rather than 2^170, since the 2^170 is "a fixed one-time cost that is
amortized over all keys in the world", is obviously a mistake; see
Appendix B.1.1 ("The amortization-eliminates-precomputation fallacy")
for further discussion.

There is, furthermore, an obvious analogy between multiple keys and
multiple messages. You could just as easily have written

* "your public key is fixed for the entire world to use" and

* "the adversary knows the key in advance of the messages it wants to
break" and

* "the adversary can use the results of the preprocessing to attack
all messages that ever have been or will be generated" and

* "to be conservative we should treat the preprocessing step as

computationally 'free' for the attacker, not caring about how much it

actually costs" and

* "it is safer to treat it as if it could be free, because it's a fixed
one-time cost that is amortized over all messages sent to you" and

* "we should only count the adversary's 'online' effort to break
messages after completing the preprocessing".

Of course it is again true that the attacker will amortize effort over
many messages if possible; again there are interesting precomputations
and interesting batch algorithms. But focusing on the incremental
per-message cost is obviously ignoring even more effects than focusing
on the incremental per-key cost.

For typical cryptographic systems, in typical attack models, the
incremental per-message cost is negligible, since the attacker can
precompute your secret key "for free". Does this mean that we should
tell users to throw away systems with any keys that last longer than a
single message---even if performance constraints then force them to move
to, say, a 2^32 security level? The incremental-per-message-cost metric
would say that this is an improvement, even though for actual security
this would obviously be an unmitigated disaster. This is a more extreme
illustration of the fact that underestimating the attack cost isn't
necessarily "safer".

Bottom line: There's no substitute for proper algorithm analysis. Waving
away parts of the cost as "precomputation", "overhead", etc. can be a
simplification but runs the risk of being a serious oversimplification,
omitting costs that are in fact dominant.

---Dan

P.S. Side note regarding terminology for batch algorithms that produce
early output: "Decrypting one out of many" and "decoding one out of
many" can be written "DOOM". This acronym is due to Nicolas Sendrier.

[Christopher J Peikert]

I'm puzzled that you only want to discuss the detailed cost of attacking Soliloquy/SG-Principal-SVP, when it has already been shown to be very weak in *at least* those rings that have easily analyzable units, thanks to the SG promise.  That hardly inspires confidence.

The whole point of my original note is that lattice crypto should be (and fortunately, is) based on other problems like Ideal-SVP that:

(a) *provably* offer at least as much security as SG-Principal-SVP -- no matter what attacks may eventually be found (because SG-Principal-SVP is a strict specialization of Ideal-SVP), and

(b) offer *significantly more* security against currently known attacks.

These points hold in any reasonable model of precomputation/amortization.  And for (b), we get even larger security gaps (and even polynomial-time attacks!) by assuming cheaper precomputation and/or quantum and/or rings with easily analyzable units.

If you don't dispute these claims, then SG-Principal-SVP is at best irrelevant, and at worst dangerous.  If you do dispute them, then you should say so, and explain why.

Bottom lines: (1) There *is* a substitute for algorithm analysis, namely, when there is a tight reduction from one problem to another -- such as when one is a strict specialization of the other.  (2) Where we don't have tight reductions, current algorithm analysis strongly favors Ideal-SVP/Ring-LWE over SG-Principal-SVP/Soliloquy.

Just for the record, I will respond to this point:

Christopher J Peikert writes:
> I am not claiming that it really *is* free -- only that it is safer to
> treat it as if it could be free, because it's a fixed one-time cost
> that is amortized over all keys in the world.

Underestimating the attack cost isn't necessarily "safer". Consider the
problem faced by a user who wants to choose the strongest system that he
can, subject to performance constraints: maybe X is stronger than Y, but
your underestimate of the security of X is _below_ your underestimate of
the security of Y, misleading the user into choosing Y.

That's all fine in general, but here we are comparing:

(X) Ideal-SVP in a ring (which is a *lower* bound on Ring-LWE-based systems), and

(Y) SG-Principal-SVP in the same ring (which is an *upper* bound on Soliloquy-style systems).

Because Y is a strict specialization of X, there is no possibility of mis-estimating their relative security -- X always comes out on top.

If you want to compare X versus Y in different rings, you can try -- but as I wrote, we don't yet have very good tools to do so.  About all we can do is compare the best known algorithms for the two problems.  Here again X comes out on top.

[D. J. Bernstein]

Christopher J Peikert writes:
> NTRU lattices have a "quasi-cyclic" structure, in which the two halves
> of the 2n coordinates "rotate" in concert -- I don't know whether this
> can be encoded as a principal ideal in a degree-2n number field.

Define K as \Q[x]/\Phi_N(x), where as usual \Phi_N is the Nth cyclotomic
polynomial. Then K is a degree-n number field for n = \phi(N), where as
usual phi(N) = deg \Phi_N. For example, if N is in {2,4,8,...} then
n = N/2 and \Phi_N(x) = x^n + 1.

Define R as \Z[x]/\Phi_N(x). Then R is the ring of integers of K.

Define L as K[y]/(y^2-r), where r is a non-square in R. Then L is a
degree-2n number field.

Define S as R[y]/(y^2-r). S isn't necessarily the ring of integers of L,
but it's close enough that everything I'll say about ideals of S can
easily be adapted to ideals of the ring of integers. (Moving from S to
the ring of integers is what algebraic geometers call "resolution of
singularities"; this has a well-understood effect on class groups etc.)

As an R-module, S is freely generated by 1 and y; multiplication by y
replaces 1 with y and replaces y with r. As a \Z-module, R is generated
by 1,x,...,x^{N-1}, so S is generated by

1,x,...,x^{N-1},
y,yx,...,yx^{N-1},

with multiplication by x rotating these two lists of generators in
concert; also, R is freely generated by 1,x,...,x^{n-1}, so S is freely
generated by

1,x,...,x^{n-1},
y,yx,...,yx^{n-1},

with multiplication by x again rotating except for the usual reduction
of x^n modulo Phi_N. The same "quasi-cyclic" action of x also applies to
ideals of S.

For comparison: In NTRU, the secret key consists of two short elements
f,g of R, where 3g and 1+3f are both invertible in R/q; here q is a
standard integer. The public key h in R is a minimal representative of
3g/(1+3f) modulo q. Define the "NTRU lattice" L as the set of (u,v) in
R^2 such that v is congruent to uh modulo q, i.e., as the R-submodule

(1,h)R + (0,q)R

of R^2. The NTRU key-recovery problem is the problem of finding the
short nonzero vector (1+3f,3g) of L, given h.

Assume that r is congruent to h^2 modulo q (i.e., r-h^2 is in qR), and
define I as the R-submodule (y+h)R + qR of S. Then I is an ideal of S,
since

y(y+h) = yh + r = (y+h)h + r-h^2 and
yq = (y+h)q - hq

are both in I. Furthermore, I is the preimage of L under the standard
R-module map from S to R^2 that maps 1 to (0,1) and maps y to (1,0).
This ideal I has a short nonzero vector (1+3f)y + 3g, and the NTRU
key-recovery problem is exactly the problem of finding this vector.

This _almost_ demonstrates a perfect match to what my blog post called
the "prototypical ideal-lattice problem" (apparently this is what you
now call "SG-Principal-SVP"; it's basically Smart--Vercauteren "SPIP",
although they aren't careful to emphasize as part of the problem that g
exists):

Someone has a secret short nonzero element g of a ring R, and tells
us a basis for the principal ideal gR. Our task is to find g. The
ring R is public, the ring of integers of a standard degree-n number
field.

To see the match, replace g with (1+3f)y + 3g, replace R with S, and
replace n with 2n. Someone has a secret short nonzero element (1+3f)y+3g
of S, and tells us a basis for the ideal I; our task is to find this
element; the ring S is (aside from minor obstructions) the ring of
integers of a degree-2n number field (which isn't standard, but that's
okay as long as we account properly for field precomputations). We also
know that the ideal I contains the short element (1+3f)y+3g. The only
remaining question is whether I _equals_ ((1+3f)y+3g)S.

If r is chosen to be small, let's say the minimal representative of h^2
modulo q (assuming that's not a square), then the norm (3g)^2-r(1+3f)^2
is a small multiple of q (since f and g are short). This means that
there can't be much gap between ((1+3f)y+3g)S and I: the ratio is some
small ideal J, and replacing I by IJ will give us exactly the desired
ideal ((1+3f)y+3g)S. At this point there's a quantitative question of
what exactly "small" means and how many choices for J there are; I'd
resort to computer experiments to get a handle on this.

For most number fields, class groups are very small---it's typical for
_all_ ideals to be principal. Cyclotomics aren't typical: their many
symmetries are well known to create larger class groups. For the same
reason, I'd expect S to have a rather large class group. This should
_help_ the search for J: once we've computed the class group, the class
of I, and the classes of all small prime ideals, we don't have to waste
time enumerating J for which IJ isn't principal, since the condition "IJ
is principal" linearly constrains the exponents in J's factorization.

> I think people have attempted such a connection in the past, but to my
> knowledge it has never worked out. 

You keep making vague claims that people have tried attacking various
problems. Could you please get in the habit of providing evidence to
back up these claims? Anyone interested in working on better algorithms
will want to see the details of _what_ has been tried before, what the
methods _did_ succeed in doing, and what the methods did _not_ succeed
in doing. If this documentation doesn't exist then it's much more likely
that there haven't been any serious efforts.

---Dan

[Christopher J Peikert]

On Sat, Feb 21, 2015 at 12:54 PM, D. J. Bernstein <d...@cr.yp.to> wrote:

Christopher J Peikert writes:
> NTRU lattices have a "quasi-cyclic" structure, in which the two halves
> of the 2n coordinates "rotate" in concert -- I don't know whether this
> can be encoded as a principal ideal in a degree-2n number field.

Define K as \Q[x]/\Phi_N(x), where as usual \Phi_N is the Nth cyclotomic

polynomial. Define R as \Z[x]/\Phi_N(x). Then R is the ring of integers of K.

Define L as K[y]/(y^2-r), where r is a non-square in R. Then L is a
degree-2n number field. Define S as R[y]/(y^2-r).

OK, in short you are defining the NTRU lattice as an ideal in some quadratic extension S of R, where the choice of S **depends on the public key**.  That doesn't match up with any of the systems and attacks considered so far (the ring has always been known in advance of the public key), but let's see where it leads.

I see two significant problems with the basic setup of this approach (details follow):

1. We can't preprocess S before seeing the public key, and we have little idea what the units of S look like ahead of time.  Recall that for the attack to convert an arbitrary generator to a short one, it needs to compute a basis that is good for solving BDD on the log-unit lattice of S.  Because the element r defining S is random, we're back to generic exponential-time algorithms for this computation alone.  (Moreover, it's not even clear that a suitably good basis exists!)  This seems to already kill the approach in its crib -- in the sense that its performance will be worse than other known attacks -- but let's say it doesn't.

2. This choice of S completely distorts the *geometry* of the problem, i.e., the kind of "shortness" required of the generator by the GCHQ attack.  This is because the polynomial defining S/R is y^2-r, and one must instantiate r=r(x) to be quite large (having coefficients of size roughly q) relative to the vectors in the NTRU lattice.  It follows that the S-element corresponding to the NTRU secret key is **not at all short** in the sense required by the attack.

(Point 2 is related to the fact that cryptosystems need to use rings whose defining polynomials have coefficients much smaller than q.)

 

For comparison: In NTRU, the secret key consists of two short elements
f,g of R, where 3g and 1+3f are both invertible in R/q; here q is a
standard integer. The public key h in R is a minimal representative of
3g/(1+3f) modulo q. Define the "NTRU lattice" L as the set of (u,v) in

R^2 such that v is congruent to uh modulo q.

Assume that r is congruent to h^2 modulo q (i.e., r-h^2 is in qR), and

define I as the R-submodule (y+h)R + qR of S. Then I is an ideal of S.

This is all fine.

 

This ideal I has a short nonzero vector (1+3f)y + 3g, and the NTRU
key-recovery problem is exactly the problem of finding this vector.

This is mistaken.  It's not right to consider z = (1+3f)y + 3g as "short" in S, because y is not really short: y^2 = r has big coefficients, of magnitude roughly q.

You've implicitly assumed that any element having small coefficients wrt the R-basis {1,y} of S is "short."  But the choice of R-basis is R-bitrary (sorry), and a priori has no geometric meaning -- for example, we could have used the basis {1, y-10^6} instead, which makes the coefficient of 1 much larger, but it doesn't change anything in the underlying geometry.

Geometrically, what matters to the attack on SG-Principal-SVP is the canonical (Minkowski) embedding of the generator z into C^2n.  Specifically, we need all the complex embeddings of z to have roughly the same magnitude, up to small multiplicative factors.  (Without this, we don't have a BDD instance on the log-unit lattice.)  But z is not at all short in this sense!

This can be seen already in the case of a real quadratic extension of the rationals (the 1st cyclotomic), when r is even slightly large.  For, say, r=37, the ratio

|6 + sqrt{37}| / |6 - sqrt{37}| ~= 146 is huge!

 

> I think people have attempted such a connection in the past, but to my
> knowledge it has never worked out. 

You keep making vague claims that people have tried attacking various
problems. Could you please get in the habit of providing evidence to
back up these claims? Anyone interested in working on better algorithms
will want to see the details of _what_ has been tried before, what the
methods _did_ succeed in doing, and what the methods did _not_ succeed
in doing. If this documentation doesn't exist then it's much more likely
that there haven't been any serious efforts.

Across math and science, serious attempts that fail to solve problems are rarely written up in any detail or made public (for one thing, conferences and journals tend not to publish them).  They tend to be shared informally, if at all.  Maybe it shouldn't be this way, but it is this way.  The point is that lack of documentation is in no way evidence for lack of serious efforts.

As one anecdote, during a big fraction of the time we spent on what became the Ring-SIS and Ring-LWE papers, we were actually trying hard to break Ideal-SVP (using all the usual suspects: subfields, the log-unit lattice, etc.)  We even thought we succeeded a few times.  But it turned out that we could only manage to reduce Ideal-SVP to those other problems.

Chris

[D. J. Bernstein]

Christopher J Peikert writes:
> Across math and science, serious attempts that fail to solve problems
> are rarely written up in any detail or made public (for one thing,
> conferences and journals tend not to publish them).

My experience is that pretty much every useful algorithmic idea starts
out solving _some_ problems. The successes---and limitations---are
documented in papers, and technical reports, and software, and blog
entries, and the occasional mailing-list discussion. :-)

> OK, in short you are defining the NTRU lattice as an ideal in some quadratic
> extension S of R, where the choice of S **depends on the public key**.  That
> doesn't match up with any of the systems and attacks considered so far (the
> ring has always been known in advance of the public key)

There's no mismatch as long as people are careful to keep track of the
time required for ring-specific computation. For example, my blog post
does this. The bigger picture is that keeping track of precomputation
cost is an important and standard part of cryptanalysis, for reasons
that I explained in an earlier message.

> We can't preprocess S before seeing the public key, and we have
> little idea what the units of S look like ahead of time.

Why are you now commenting on the hardness of the short-generator
problem? Weren't you, a moment ago, dismissing the short-generator
problem as being irrelevant to lattice-based cryptography?

What I'm saying is that there's a plausible way to break NTRU _if_ one
has a solution to the short-generator problem. There are some steps that
need quantification and that might turn out to be bottlenecks; further
adapting the ideas to Ring-LWE would take more work and could run into
even larger obstacles; but one can't be so cavalier regarding the
importance of the short-generator problem.

As for the hardness of the problem, I agree that the GCHQ idea doesn't
instantly solve the whole problem, but my blog post explains a concrete
strategy to exploit subfields to make unit CVP easier.

> This choice of S completely distorts the *geometry* of the problem

No: your preconceived notion of "short" simply isn't relevant here. What
ultimately matters is that the log of the generator is close enough to 0
to be found efficiently by the unit CVP attack. You might think that a
factor of sqrt(q) is quite noticeable for an ideal that has q as an
element, but such elements don't even show up in the CVP stage: this
stage sees only _generators_ of the ideal, and those are much more
widely spaced. Even better, since the GCHQ idea immediately takes care
of the cyclotomic subfield, the approach in my blog post ends up
focusing on a much sparser sublattice.

---Dan

[Christopher J Peikert]

On Saturday, February 21, 2015, D. J. Bernstein <d...@cr.yp.to> wrote:

Christopher J Peikert writes:
> Across math and science, serious attempts that fail to solve problems
> are rarely written up in any detail or made public (for one thing,
> conferences and journals tend not to publish them).

My experience is that pretty much every useful algorithmic idea starts
out solving _some_ problems.

What can I say, our experiences differ. I have come away completely empty-handed from dozens of attempts to solve problems, many of them concerning these very topics.  I'm assuming it's similar for most other researchers.

> We can't preprocess S before seeing the public key, and we have
> little idea what the units of S look like ahead of time.

Why are you now commenting on the hardness of the short-generator
problem? Weren't you, a moment ago, dismissing the short-generator
problem as being irrelevant to lattice-based cryptography?

Sheesh, I'm commenting on SG-PIP (aka SPIP) because you're proposing it as a way of solving NTRU!  Except that you're not using the SG-PIP as defined and used in every prior work under discussion, including your own blog post*.

In SG-PIP as previously defined, there is one fixed ring (for a given dimension), and **only the ideal** is the input/instance.  In your new problem, the ring is chosen at random from a huge family, and **the ring is also part of the input**.  There is such a big qualitative difference between these problems, and the algorithms used to solve them, that they cannot reasonably be called by the same name.

[* From your post, emphasis added: "Someone has a secret short nonzero element g of a ring R, and tells us a basis for the principal ideal gR. Our task is to find g. The ring R is public, the ring of integers of a standard degree-n number field." ]

To avoid this ambiguity, suppose we call the new problem RR-SG-PIP for "random ring," with the understanding that one needs to parameterize it by a family of rings and a distribution over them for each dimension (just like SG-PIP is parameterized by a sequence of rings, at most one per dimension).

With this important distinction made, I stand by my claim that SG-PIP is suspicious and should/can be avoided in lattice-based cryptography, for the reasons I have already given.

 

one can't be so cavalier regarding the
importance of the short-generator problem.

Not if you redefine the problem, I can't!

What I'm saying is that there's a plausible way to break NTRU _if_ one

has a solution to ...

...a certain RR-SG-PIP problem.

But you've given no reason to expect the log of the generator (corresponding to the NTRU secret key) to lie in a particular unique-decoding region of the log-unit lattice.  I have given a simple example where the log-generator is far from zero.  Without more details about how to resolve this central issue, I would not say the approach rises to the level of "plausible."

Moreover, I'd say that a reduction from NTRU to RR-SG-PIP is not very interesting if the latter is harder to solve than NTRU itself.  Even if everything else works, finding a good enough basis of the log-unit lattice of these random rings -- if one even exists -- looks a lot harder than NTRU, and takes exponential time by current algorithms (even allowing for free preprocessing).

As for the hardness of the problem, I agree that the GCHQ idea doesn't
instantly solve the whole problem, but my blog post explains a concrete
strategy to exploit subfields to make unit CVP easier.

Ok, there is a strategy -- does it actually work?  Are you saying that one can solve CVP on the log-unit lattice for a given one of these random rings in subexp time, or at least faster than we know how to break NTRU?  What exactly is the claim here?

More generally, what is the status of the ideas in the blog post?  On the one hand you write that they are preliminary and that many important details ---- -- including whether the ideas work at all! -- need fleshing out; on the other hand you often invoke the post as if its claims are reliable.  The post has been up for more than a year; will it ever move out of limbo?

 

> This choice of S completely distorts the *geometry* of the problem

No: your preconceived notion of "short" simply isn't relevant here. What
ultimately matters is that the log of the generator is close enough to 0
to be found efficiently by the unit CVP attack.

I agree that only generators "show up" in this part of the attack, and that the existence of other short vectors is not relevant one way or the other.

However, my "preconceived" notion of shortness is exactly what it's supposed to be -- I wrote that all embeddings of the generator must have nearly the same magnitudes, up to small multiplicative factors, which is equivalent to the condition given above.  And I gave a concrete example, using small parameters, where the log of the generator is very far from zero.  What do you make of it?

Chris

[D. J. Bernstein]

Christopher J Peikert writes:
> More generally, what is the status of the ideas in the blog post?

The blog post describes a strategy to solve short-generator problems via
optimized computations in algebraic number theory. The first stage,
finding _some_ generator, was already considered by Smart and
Vercauteren, but they claimed worse than exponential time while the post
claims subexponential. For the second stage, reducing the generator, the
post articulates a new idea to exploit subfields; in extreme cases this
reduces the lattice dimension to slightly sublinear. The post is careful
to say which parts are settled and which parts need more study.

Since then I've seen at least three interesting directions of work:

* For cyclotomic fields, the second stage is easy: the GCHQ idea
obviously supersedes my subfield approach. However, the earlier
stages (like NFS for integer factorization) are quite expensive,
and it's important to understand their performance. Furthermore,
the second stage remains the asymptotic bottleneck for most fields,
such as the x^p-x-1 fields recommended in my blog post.

* For quantum computers, the first stage is easy. In particular, for
quantum computers, the whole problem is easy for cyclotomic fields.
But we also want to understand pre-quantum security---it's not as
if Shor's algorithm ended research into the cost of factorization.

* Various people have been working on quantifying the effectiveness
of various subroutines, and I've encouraged these people to speak
up as soon as they have something to report.

I'd also encourage new researchers to introduce themselves here, say
what they're thinking of working on, and ask what has been done already,
so that we can all avoid accidental duplication of effort.

> In SG-PIP as previously defined, there is one fixed ring (for a given
> dimension), and **only the ideal** is the input/instance. In your new
> problem, the ring is chosen at random from a huge family, and **the
> ring is also part of the input**.

Over here in CryptanalysisLand(tm), it's completely standard to keep
track of the costs of precomputation---in this case, the amount of
precomputation that has to be done to process the ring. After all,
_somebody_ has to do the computation!

Theoreticians very frequently screw this up---making definitions that
_ignore_ the cost of precomputation, and then using cryptanalysis as a
justification for conjecturing difficulty under those definitions, even
though the cryptanalysis actually _included_ the cost of precomputation.
http://cr.yp.to/papers.html#nonuniform gives several detailed examples
of this phenomenon, and (assuming standard heuristics) disproves several
security conjectures in the literature; the underlying definitions don't
accurately model actual security.

I fully understand your point that a subroutine analysis _ignoring_
ring-specific precomputation wouldn't be useful if the subroutine is
applied to a ring that varies. But this point is irrelevant to my blog
post: my analysis _does_ account for ring-specific precomputation, so
this reduction from NTRU (very briefly mentioned near the end of the
post) is free to vary the choice of ring.

Of course, by analyzing the precomputation separately, I was also
answering the question of how long the main computation would take after
the precomputation was done---but if precomputation is unrealistically
viewed as _free_ then the best algorithm changes; for example, one would
then be free to take practically forever finding an excellent basis for
the unit lattice, whereas in reality the best CVP approach obviously
isn't so extreme. (The story is different when excessive ring structure
simply gives us an excellent basis, as exploited by GCHQ.)

While I'm correcting your errors regarding my blog post, I should also
note that the short-generator problem has been the main focus of my work
on lattice-based cryptography, and is featured prominently in my blog
post. So I'd appreciate it if you'd refrain from claiming, e.g., that I
didn't "notice" the importance of a short generator.

> There is such a big qualitative difference between these problems, and
> the algorithms used to solve them, that they cannot reasonably be
> called by the same name.

Coppersmith's "factorization factory" does size-specific precomputation
but we still call it a "factorization" algorithm. Yes, there's a change
in input order (first read the size, then precompute, then clone the VM,
then read N) but this hardly justifies switching from "factorization" to
a new name; instead we use composable concepts such as "precomputation".
The goal of the algorithm is the same; there's just a change in metric.

> I gave a concrete example, using small parameters, where the log
> of the generator is very far from zero.  What do you make of it?

Since you ask: It's not "very far from zero"; it's tiny. The phenomenon
you're trying to illustrate is well known to be a narrow corner case,
disappearing as the degree goes up; given the GCHQ observation I
wouldn't expect even the slightest trouble for any small extension of a
big cyclotomic field. More fundamentally, it seems to me that you're
getting caught up in minor theoretical obstacles to particular proof
strategies, while the question at hand is what the actual algorithm
performance is, and I don't see your analysis technique as shedding any
light on this.

---Dan

[Thomas Wunderer]

Hello,

 

Dan wrote:

„I'd also encourage new researchers to introduce themselves here, say what they're thinking of working on, and ask what has been done already, so that we can all avoid accidental duplication of effort.“

 

I would like to take this opportunity to introduce myself. My name is Thomas Wunderer and I am a new PhD student here at Technische Universität Darmstadt working on lattice-based cryptography. Because of my background in algebraic number theory, at the moment my main interest lies in ideal lattices.

 

This is an incomplete list of interesting research topics I have gathered so far:

1.         1. Finding some generator of a principal ideal.

2.         2. Given some generator of a principal ideal, find a short generator.

3.         3. Is there a connection between short(est) generators and short(est) vectors?

4.         4. Given a (shortest) generator of a principal ideal lattice, is SVP/CVP easy/easier to solve?

5.         5. Apply the obtained results to specific schemes.

6.         6. How to deal with the mod q structure?

7.         7. Anything non-trivial about non-principal ideal lattices.

8.         8. Expanding on the “dimension-halvening technique” for principal ideal lattices using the Gentry-Szydlo algorithm (described here https://eprint.iacr.org/2012/610.pdf)

9.         9. Identifying more weak instances (see Dan’s other topic in the group).

 

As I am just starting out, choosing first topics to begin with seems not too easy. So if you have any advice, I would be happy if you let me know.  If you have any additions to the list, feel free to extend it. Also, if you have done or are aware of any work in these (or similar) areas, please share your knowledge.

 

I will now ask some specific questions related to some of the above topics. The questions are motivated by quotes from this discussion, but I encourage everyone, not just the author of the quotes, to answer.

 

Ad 1.:

Dan wrote:

“My blog post http://blog.cr.yp.to/20140213-ideal.html says that this is

all wrong: the computation, optimized sensibly, should be heavily

subexponential in the field degree.”

 

Has there been some progress (in special cases)? In my understanding, finding a generator of a principal ideal is still considered a very difficult task in algebraic number theory. I hope to talk more with Jean-François Biasse at the Mathematics of Lattices Workshop (http://icerm.brown.edu/topical_workshops/tw15-7-mlc/) about this topic.

 

 

Ad 2.:

Dan wrote:

“Of course the [log unit] lattice _has_ a good basis, but why should a good basis be
easy to find? Here are the approaches that we've seen: […] For cyclotomics: simply _write down_ a good basis (polynomial time), as GCHQ suggested.”

 

Does this work this easy for all cyclotomics or just special cases (e.g. power-of-two)? If I remember it correctly, the GCHQ paper makes some assumptions, and I am not sure in which cases they are actually satisfied.

 

 

Ad 3. and 4.:

Chris wrote:

“SG-Principal-SVP: same as Principal-SVP, but specialized to principal ideals that are promised to have a short generator g. (Such ideals are a very small fraction of all principal ideals.)”

And

“But for the vast majority of principal ideals, even the shortest generator is an invalid solution to Principal-SVP, because it is *much* longer than the shortest lattice vector, by a factor of 2^sqrt{n} or so.”

 

I agree to consider the case where one is promised a short generator as a separate case. But how do you draw the conclusion that such principal ideals are a very small fraction? In particular, where does the factor 2^sqrt(n) come from? I remember that I have heard statements like “typical generators are short” as well as statements similar to yours, but no evidence to support either claim. Did you (or somebody else) collect some empirical data about the relation between short(est) vectors and short(est) generators? I recently read a PhD thesis that wants to connect short generators and short vectors (http://repository.lib.ncsu.edu/ir/bitstream/1840.16/10072/1/etd.pdf). Although the results are not too convincing, he seems to believe that there is a connection between short(est) vectors and short(est) generators. The author first shows that in dimension 1 and 2, shortest vectors are always generators (not relevant for crypto). Then he presents empirical tests in higher dimensions showing that with high probability (at least 95 %) the “short” vector output by LLL given the rotation basis of a generator is a generator of the same ideal. He then suggests that therefore short(est) vectors in a principal ideal might be generators. This is the part I was referring to as “not too convincing”. It might be that this is a special property of LLL when given a rotation basis, this could be true for the “somewhat short” vector output by LLL but false for shortest vectors, and so on. By the way, the author points these problems out himself, so he is not to be blamed.

 

 

Ad 5.:

Dan mentioned the idea of applying the attack to NTRU. I will not go into this right now, but leave this for a future post. Maybe there are more interesting ideas to rewrite shortest vector problems as short generator problems.

 

 

Ad 6.:

Chris wrote:

“In conclusion, NTRU and Ring-LWE lattices do not appear to be principal ideals, or even ideals at all, but merely R_q-modules”

This is a valid point I wondered about before. How do you overcome this obstacle? Are there any ideas?

 

 

- Thomas

[D. J. Bernstein]

Thomas Wunderer writes:
> Does this work this easy for all cyclotomics or just special cases (e.g.
> power-of-two)? If I remember it correctly, the GCHQ paper makes some
> assumptions, and I am not sure in which cases they are actually satisfied.

There are standard formulas that, for every cyclotomic field K =
\Q(\zeta_n), produce a basis B of a group C of units that's conjectured
to be of small index in O_K^*. It seems that Log B is always a very good
basis for the lattice Log C, making CVP very easy for Log C; this is
what the Soliloquy paper relies on.

The paper makes an extra assumption that C = O_K^*. This is often the
case, and it forces Log C to be Log O_K^*, but it isn't actually
necessary: all we need is for Log C to have small index j in Log O_K^*.

Remember that the goal is to find a short vector g, given the ideal I =
gO_K. In subexponential time (or quantum poly time) we find _some_
generator h of I, and then h/g must be in O_K^*. If h/g is "random" then
Log(h/g) has a significant chance 1/j of being in Log C, and then the
easy CVP computation for Log C will find Log g given Log h. If Log(h/g)
isn't in Log C, simply continue the computation to find more "random"
generators of I, and keep trying CVP for each of those generators.
(Alternatively, reduce the newly found elements of O_K^* modulo C,
obtaining a very good basis for a better approximation to O_K^*.)

Regarding the conjecture: See, e.g., Washington, Introduction to
Cyclotomic Fields, Second Edition, page 147, Theorem 8.3, which

* displays explicit formulas for a set B (from Ramachandra) of real
cyclotomic units inside K^+ (typo: \zeta_p should be \zeta_n), with
#B = phi(n)/2 - 1;

* states that B is multiplicatively independent; and

* gives an explicit formula for the index of the group generated by B
and -1 inside O_{K^+}^*. One factor in the formula is h_n^+, the
class number of K^+; the other factors are all visibly small.

The index of O_{K^+}^* inside O_K^* is small (especially after logs) by
Theorem 4.12, so the only way for the group generated by B to have large
index is for h_n^+ to be large---but standard conjectures say that h_n^+
is small. More explicitly:

* On pages 421 through 423 you'll find a table that, for each prime
p below 10000, shows a number that's believed to be h_p^+ (or skips
p in the usual case that this number is 1). The largest number is
130473.

* On page 421 you'll also find various conjectures regarding h_n^+
for non-primes n: for example, h_n^+ = 1 for all n <= 200 except
h_136^+ = 2, h_145^+ = 2, h_163^+ = 4, h_183^+ = 4, h_191^+ = 11.

* Weber's conjecture states that h_n^+ = 1 when n is a power of 2.

What the Soliloquy paper said at this point was "We assume that the
cyclotomic units have index 1 in the entire group of units ... which is
almost certainly true for the specific instance of Soliloquy that had
been proposed." The paper goes on to say that a "simple" basis is known
and that CVP is easy since the target (Log g) is small compared to the
"determinant of this lattice". Note that the paper is being sloppy here:
do the authors think that CVP difficulty depends only on the size of the
target vector and not on the quality of the known basis? The argument
would be completely invalid if the "simple" known basis were a _bad_
basis for the lattice. Fortunately for the attacker, it seems that this
basis is always very good.

---Dan

[Christopher J Peikert]

I agree with all that Dan has written here, but just want to make one very important distinction: the attack does not rely on solving CVP in the log-unit lattice, but rather the more specialized BDD (bounded-distance decoding) problem.

In CVP, the target point is *arbitrary*, and we want to find some lattice vector that is (nearly) closest to it.

In BDD, the target point is guaranteed to be "very close" to some lattice vector (much closer than it is to all others), and we want to find *that* vector.

Even using a very good lattice basis, efficient CVP algorithms will not always find *the* closest lattice vector to the target.  In the context of the attack -- or more generally, when trying to find a short general of an *arbitrary* principal ideal (with no shortness promise) -- such an outcome will be essentially useless.  This is why the attack does not solve the Principal-SVP problem.

What makes the attack work is that the existence of a short generator means that we have a BDD instance -- it implies that the target is quite close to the log-unit lattice.  A good basis is enough to solve BDD efficiently.

Chris

--
You received this message because you are subscribed to the Google Groups "Cryptanalytic algorithms" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cryptanalytic-algo...@googlegroups.com.
To post to this group, send email to cryptanalyti...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cryptanalytic-algorithms/20150305165237.8911.qmail%40cr.yp.to.
For more options, visit https://groups.google.com/d/optout.

[Christopher J Peikert]

In reply to my original post on what the Soliloquy attack means for lattice crypto more broadly, Dan Bernstein wrote:

Such an algorithm would, I think, be a solid step towards breaking much

larger parts of ideal-lattice cryptography.  For example, I think that

short nonzero vectors in NTRU lattices for a degree-n field can be

viewed as short generators of principal-ideal lattices for a degree-2n

field, implying that degree-n NTRU would be broken by a solution to the

short-generator problem for the degree-2n field.

I replied:

> NTRU lattices have a "quasi-cyclic" structure, in which the two halves
> of the 2n coordinates "rotate" in concert -- I don't know whether this
> can be encoded as a principal ideal in a degree-2n number field.

Dan responded with an interesting possible way of doing this, by embedding into a quadratic extension of the original ring (where the extension depends on the public key).  The idea is that the NTRU lattice corresponds to an ideal in this extension, and that solving the "short generator problem of a principal ideal" problem (SG-PIP) on a related ideal would yield the NTRU secret key.

This note describes why the proposed attack is inherently (much) slower than brute-force key enumeration.  In short, this is because the attack involves a (slower than necessary) enumeration that by itself is already sufficient to recover the secret key -- no SG-PIP needed.

As a corollary of the analysis, we'll also see that the attack does not represent the NTRU lattice as a principal ideal in any meaningful way.  In short, this is because the ideal corresponding to the NTRU lattice, and the principal ideal under consideration, are not related in any way we can compute efficiently.

There turns out to be a simple alternative description of the attack, which just involves an easy relation on the NTRU keys (no quadratic extension rings, ideals, etc.). With this perspective, we'll see why the framework of the attack is subsumed by other more natural relations/enumerations, including brute-force key search.

(The end of this post contains Sage code for the supporting experiments.)

 

Define K as \Q[x]/\Phi_N(x), where as usual \Phi_N is the Nth cyclotomic
polynomial. Then K is a degree-n number field for n = \phi(N), where as
usual phi(N) = deg \Phi_N. For example, if N is in {2,4,8,...} then
n = N/2 and \Phi_N(x) = x^n + 1.

Define R as \Z[x]/\Phi_N(x). Then R is the ring of integers of K.

Define L as K[y]/(y^2-r), where r is a non-square in R. Then L is a
degree-2n number field.

Define S as R[y]/(y^2-r). S isn't necessarily the ring of integers of L,
but it's close enough that everything I'll say about ideals of S can
easily be adapted to ideals of the ring of integers.

The connection to NTRU: let f,g in R be "short" elements comprising the NTRU secret key, and let h=f^-1 * g mod qR be the public key, where q is a public small integer.  For concreteness, think of the coefficients of f and g as being uniform from some small interval of constant size.  (Dan's post uses 1+3f and 3g, but that has no effect on anything here, so we'll keep the notation simple.)

To define the extension L, we take r in R to be congruent to h^2 in R/qR and "as small as possible," e.g., the minimal representative.  (This is usually a non-square in R.)

Define the "NTRU lattice" L as the set of (u,v) in
R^2 such that v is congruent to uh modulo q, i.e., as the R-submodule

   (1,h)R + (0,q)R

of R^2. The NTRU key-recovery problem is the problem of finding the

short nonzero vector (f,g) of L, given h.

Assume that r is congruent to h^2 modulo q (i.e., r-h^2 is in qR), and
define I as the R-submodule (y+h)R + qR of S. Then I is an ideal of S,
since

   y(y+h) = yh + r = (y+h)h + r-h^2 and
   yq = (y+h)q - hq

are both in I. Furthermore, I is the preimage of L under the standard
R-module map from S to R^2 that maps 1 to (0,1) and maps y to (1,0).

This ideal I has a short nonzero vector f*y + g, and the NTRU

key-recovery problem is exactly the problem of finding this vector.

So far, so good.

 

We know that the ideal I contains the short element f*y+g. The only
remaining question is whether I _equals_ (f*y+g)S.

This is indeed the key question.

 

If r is chosen to be small, let's say the minimal representative of h^2

modulo q (assuming that's not a square), then the norm g^2-r*f^2

is a small multiple of q (since f and g are short). This means that

there can't be much gap between (f*y + g)S and I: the ratio is some

small ideal J, and replacing I by IJ will give us exactly the desired

ideal (f*y + g)S. At this point there's a quantitative question of

what exactly "small" means and how many choices for J there are; I'd
resort to computer experiments to get a handle on this.

This is where the trouble begins.

Just to be sure everything is explicit, here's my understanding of the proposal:

* There is a (known) ideal I = (y+h)R + qR corresponding to the NTRU lattice for public key h.

* There is an (unknown) principal ideal I' = (f*y + g)S, whose generator (f*y+g) we hope is short enough to find using an SG-PIP algorithm for S.  (Whether or not this is actually true will turn out not to matter; the main problem lies elsewhere.)  We know I divides I', because f*y+g is in I.

* The integral ideal J = I' * I^-1 is unknown, but we hope it has "small-ish" absolute norm.  More on this in a moment.

* The attack is therefore: given I, try all candidate ideals J in S of small enough absolute norm.  Solve SG-PIP on each I*J, until we recover a generator (f*y+g) corresponding to the NTRU secret key -- which comes from the correct choice of J.  (There is an idea below to cut down on the number of candidate J using the class group, but it doesn't seem to work; see below.)

If I have all this right, then here is the main trouble:

The ideal J has huge norm, and there are far too many candidates to enumerate.

Experiments show that the norm of J is on the order of n^n (or a bit larger), where n is the dimension of the cyclotomic ring R.

The number of ideals of norm <= N is roughly C_L*N, where C_L is the residue of \zeta_L at s=1 (see http://math.stackexchange.com/questions/92426/how-many-elements-in-a-number-field-of-a-given-norm ).  We can use the class number formula to get C_L, but that requires knowing the discriminant and regulator of L, which are expensive to compute even in moderate dimensions.

Fortunately, there is a simpler explanation for what is really going on here, which avoids all these complications (including the quadratic extension itself).  We'll give it right after this brief

~~~~~ INTERLUDE ~~~~~

For most number fields, class groups are very small---it's typical for
_all_ ideals to be principal. Cyclotomics aren't typical: their many
symmetries are well known to create larger class groups. For the same
reason, I'd expect S to have a rather large class group.

From the experiments I ran, this doesn't appear to be the case.  In dozens of random runs, the class number of S was always either 1 or 2.  (Unfortunately, it's expensive to compute, so I could only do it in small dimensions <= 20.  But it's enough to see that there's no reason for optimism in this direction.)

~~~~~ END INTERLUDE ~~~~~

Back to the main questions: why does J = I' * I^-1 have huge absolute norm (roughly n^n), and how many candidate J do we need to enumerate?  How does this compare with other attacks?

To answer these questions, let's work in R (not S) via the relative norm N(.).  As noted above, we have

   N(I') = g^2 - r*f^2 = w*qR

for some "small-ish" w in R.  This w is approximately f^2, because r has coefficients of magnitude roughly q.  Alternatively, the coefficients of w have magnitudes roughly n.

Typically, N(I) = qR (recall that I = (y+h)R + qR).  So

   N(J) = N(I') * N(I)^-1 = wR.

This has absolute norm about n^n (or more) for typical distributions of f and g.  The number of principal ideals in R of norm <= n^n is roughly n^n, give or take an o(n) in the exponent.

Now, when we enumerate candidate ideals J in S, we're also implicitly enumerating their relative norms N(J) in R.  So the attack is really just enumerating ~n^n candidates for w -- and using an expensive SG-PIP oracle to confirm the right one.

This is obviously very costly.  Here are some strictly better alternatives:

* Good: don't use SG-PIP to confirm the correct w.  Recalling that g^2 - r * f^2 = q*w, for a candidate w just reduce q*w modulo r and test if the result is short (it'll be g^2).  This test is possible because r is rather long, so we have a good enough basis for qR.

* Better: search for v = (g - r' * f)/q, where r' in R denotes the minimal representative of h.  This unknown v has coefficients of magnitude ~ sqrt{n}, yielding a square-root runtime improvement of roughly n^(n/2).

* Even better: just search for f itself!  There are only c^n possibilities, and it's trivial to test when you've got the right one: check that h*f mod q is short (it'll be g).

Chris

====== SAGE CODE ======

m=16;  # which cyclotomic to use

K.<x> = CyclotomicField(m);

R.<y> = K[];      # introduce y as a variable

q=257;            # the NTRU modulus

# generate secret key; tune the coeff bound as desired

f = K.random_element(4, integral_coefficients=True);

g = K.random_element(4, integral_coefficients=True);

Rq.<xq> = K.quotient_ring(K.ideal([q]));              # quotient ring R/qR

fq = Rq.retract(f); gq = Rq.retract(g); hq = fq^-1*gq; h = lift(hq);  # compute h, r in R

r = lift(hq*hq);

w = (g^2 - r*f^2)/q;

v = (g - h*f)/q;               # "better" alternative for faster enumeration

L.<y> = K.extension(y^2 - r);                         # define extension field

# L.class_number(proof=False);                        # class number; pretty slow

# norms of interest:

# only efficient up to m=16

# J = (f*y+g)/L.ideal([h+y,q]);

# J.relative_norm();

# J.absolute_norm();

# efficient up to m=64 or more

# w.absolute_norm()

# v.absolute_norm()

[D. J. Bernstein]

Christopher J Peikert writes:
> From the experiments I ran, this doesn't appear to be the case.  In dozens of
> random runs, the class number of S was always either 1 or 2.  (Unfortunately,
> it's expensive to compute, so I could only do it in small dimensions <= 20. 
> But it's enough to see that there's no reason for optimism in this direction.)

You're deceiving yourself with small examples. There's an extensive
literature showing that, as I said before, the many symmetries of
cyclotomic fields create larger class groups. This isn't visible in
small examples (e.g., \Q[x]/(x^2+1), \Q[x]/(x^4+1), \Q[x]/(x^8+1), and
\Q[x]/(x^16+1) all have class number 1) but it becomes a huge effect for
cryptographic sizes.

Here's an illustrative example: The class group of \Q[x]/(x^256+1) is a
cyclic group of order

6262503984490932358745721482528922841978219389975605329,

which is slightly larger than 2^182. The easy part of this is that the
class group is _at least_ this large. The hard part (proven under GRH
recently by John C. Miller: see http://arxiv.org/pdf/1405.1094.pdf) is
that it isn't even _larger_ than this.

If we know the classes of (say) ideals I,P1,P2,...,P10, and we want to
search through a range of 2^182 possibilities for a principal ideal of
the form I P1^e1 P2^e2 ... P10^e10 with small (e1,e2,...,e10), then we
can immediately restrict attention to a linear subspace that typically
includes just 1 possibility. It's conceivable that the classes will
conspire against the search, but the main heuristic used in class-group
computations is that small primes rarely engage in such conspiracies.

As the number of primes increases, this search turns into a subset-sum
problem, eventually a hard problem. However, ideals that aren't very
large have a significant chance of being smooth---and an even better
chance of being semi-smooth, which is adequate, since we can afford a
medium-size combinatorial search for a few larger primes.

> This w is approximately f^2, because r has coefficients of magnitude
> roughly q.  Alternatively, the coefficients of w have magnitudes roughly n.

There's a different mistake here: you obviously aren't even _trying_ to
find optimal attack parameters.

As in NFS polynomial selection, instead of merely searching through
integral r, let's search fractions r/s. If you don't like denominators
then you can easily clear them, converting y = sqrt(r/s) into sy =
sqrt(rs), converting the fractional ideal (y+h)R + qR into the ideal
(sy+sh)R + sqR, and converting the target (1+3f)y + 3g into the target
(1+3f)sy + 3sg, which has relative norm s^2(3g)^2 - rs(1+3f)^2, forced
to be a multiple of sq; note that sq is public.

The requirement r/s = h^2 mod q is a linear constraint on the pair
(r,s). We can't expect lattice-basis reduction to find (r,s) as short as
((3g)^2,(1+3f)^2) in a feasible amount of time, but we can expect it to
find (r,s) much shorter than the original (h^2 mod q,1), and this will
considerably reduce the ratios (s(3g)^2-r(1+3f)^2)/q. Of course, there's
no substitute for a serious quantitative study of how small these norms
can actually be pushed.

> The ideal J has huge norm, and there are far too many candidates to
> enumerate.

This statement pulls together both mistakes. First, your evaluation of
the norm of J is corrupted by your lackadaisical parameter search.
Second, you have a completely wrong idea of the size of the class group,
so you think that the goal is to pin J down to one possibility, when in
fact the goal for x^256+1 is to pin J down to 2^182 possibilities.

These bogus extrapolations and missed optimizations are nice examples of
how cryptosystem designers have the wrong incentives to carry out attack
analyses---they don't really _want_ good attacks to exist. Of course,
attack designers can be too optimistic the other way, but attack
optimism encourages serious implementation and optimization efforts
showing what works and what doesn't, so there's a natural path towards
resolving any errors. Security optimism usually ends up _discouraging_
these efforts, promoting a much longer lifetime for errors.

> Here are some strictly better alternatives:

Strictly better except for the slowdown factor 2^182. Your "better
alternatives" don't even try to exploit the huge class group.

I'm also not sure what you think you mean by "no SG-PIP needed" and
"don't use SG-PIP to confirm the correct w". The simplest case is that
(1+3f)y+3g generates the ideal (y+h)R+qR; in this case, how precisely do
you leap from knowing w=1 to finding this short generator? Being able to
find short generators of principal ideals is exactly the right tool.

---Dan

[Christopher J Peikert]

There were two main points to my previous note.  The first concerns the runtime of the proposed attack:

The number of candidates for the unknown ideal J = I' * I^-1 of S is far too large -- much larger than the exponential number c^n of possible secret keys.

There is abundant theoretical and experimental evidence (even in high dimension) that the absolute norm of J is roughly n^n.  So we're interested in the number of ideals of norm <= n^n in a particular ideal class (because J*I is principal).  My note punted on this analysis -- apart from some experiments in low dimensions -- and instead went straight to the alternative view of the attack (more on this below).

So for the record, let's do the analysis, taking advantage of the large class group.  The takeaway is that this doesn't help much, because the group order is ~n^(n/4) but we're dealing with norms ~n^n.  More precisely, we'll show that (39n)^(n/4) is a very crude lower bound on the number of candidates for J.  An immediate corollary is that the attack doesn't represent the NTRU lattice as a principal ideal in any meaningful way.

To start, we'll first bound the number of ideals of norm <= N in a particular ideal class of the cyclotomic field K itself.  For the values of N under consideration, the number of such ideals is roughly C_K*N, where

    C_K ~ (2pi)^(n/2) * Reg_K / |D_K|^(1/2)

and Reg_K, D_K are respectively the regulator and discriminant of K (see http://math.stackexchange.com/questions/92426/how-many-elements-in-a-number-field-of-a-given-norm ).

The |D_K|^(1/2) term is exactly n^(n/2).  The Reg_K term is roughly n^(n/4).  So the number of ideals is roughly N * (4 pi^2 / n)^(n/4).

Now consider the quadratic extension L of K, where J really lives.  Reg_L and D_L seem hard to analyze and compute, but we can still get a very crude bound that suffices to prove the point.  It's enough to count *principal* ideals in S of norm <= n^n, because ideals are distributed roughly uniformly across the ideal classes (see the above reference).  Now, any principal ideal aR of norm <= n^(n/2) yields a principal ideal aS of norm <= n^n.  By the above, there are roughly (4 pi^2 n)^(n/4) ~ (39n)^(n/4) such ideals aR.

= = = = = = = =

The above shows that the attack is not competitive, but it doesn't really explain *why*.  In particular, the role of the quadratic extension S is somewhat mysterious.  To clarify the situation, here is my second claim:

It's not just an unlucky happenstance that the number of candidates for J is too large; it's essentially inherent to the setup of the attack.  This is because we can alternatively view the attack as a (highly suboptimal) enumeration to solve an easy relation on the NTRU key -- without resorting to extension rings, SG-PIP, etc.

To be clear: this alternative viewpoint *absolutely does* exploit the large class group of the cyclotomic ring R, because it considers only *principal* ideals of bounded norm (see item 1 below).  So your criticism on these grounds (it's "strictly better except for the slowdown factor 2^182") is just incorrect.  One subtlety, however, is that the alternative may not exploit the *relative* class number h(S)/h(R).  But as far as I can tell, we should expect this to be rather small (see item 3 below).

Here again is the argument with some additional details:

1.  When the original attack enumerates candidates for J, it is inherently also enumerating candidates for the relative norm ideal N(J) = wR, where

    w = (g^2 - r * f^2)/q in R

has the same absolute norm as J.  So as a side-by-side comparison, let's also consider an alternative attack that simply enumerates bounded-norm candidates for w.  Note that this enumerates only *principal* ideals, so we are indeed exploiting the large class group of R.

2.  The original attack invokes an (expensive) SG-PIP solver for each candidate J, to check whether the candidate is correct, in which case it recovers the secret key.

In the alternative attack, for each candidate w we can *trivially* check whether it's correct: just check that q*w mod r is "short."  This short value will be g^2 for the correct candidate, which immediately yields the secret key.  We can perform the check because r is large (coeffs roughly q) relative to g.

(This answers the question from the last paragraph of your email.  However, your simplest case w=1 is extremely rare, since it means r \approx -q/f^2, so r is unusually small.  In this case the key is already trivially insecure.)

3.  The alternative attack therefore does much less work per candidate than the original attack does.  All that remains is to see how the number of candidates for J and w compare: it's conceivable that limiting ourselves to a single ideal class (in S) might yield fewer J-candidates than limiting to principal ideals (in R) for w-candidates.

Such a difference can arise only if some number H > 1 of ideal classes are mapped, by the relative norm, to the principal ideal class of R.  In other words, the natural homomorphism from Cl(S) to Cl(R) is H-to-1.  In such a case, the number of J-candidates can be a factor of H smaller than the number of w-candidates.  This H is simply the *relative class number* H = h(S)/h(R), the ratio of the orders of the class groups of S and R.

How large is a typical H?  I couldn't find anything definitive -- but the general sense I get from the literature is that because S is a "random" quadratic extension of R, we should expect H to be small -- this is the "relativized" version of your statement "for most number fields, class groups are very small."  Also, people have worked very hard to construct extensions having large relative class numbers, and in doing so have had to rely on quite special structures.

Therefore, the alternative attack is indeed strictly better than the original one (modulo a plausible assumption on H).  But it is still highly suboptimal.  Letting r' be a minimal representative of h, we'd do much better to search for

   v = (g - r' * f)/q in R,

which has norm bound roughly n^(n/2) [versus n^n for w].  Of course, none of these beat simply searching for f itself among the c^n possibilities.

= = = = = = = =

Finally, you propose to modify the attack as follows:

As in NFS polynomial selection, instead of merely searching through

integral r, let's search fractions r/s.  If you don't like denominators

then you can easily clear them, converting y = sqrt(r/s) into sy =
sqrt(rs), converting the fractional ideal (y+h)R + qR into the ideal
(sy+sh)R + sqR, and converting the target (1+3f)y + 3g into the target
(1+3f)sy + 3sg, which has relative norm s^2(3g)^2 - rs(1+3f)^2, forced

to be a multiple of sq; note that sq is public... [lattice reduction] will

considerably reduce the ratios (s(3g)^2-r(1+3f)^2)/q. Of course, there's

no substitute for a serious quantitative study of how small these norms

can actually be pushed.

Then I'd suggest doing such a study!  Here's a start: the alternative viewpoint given above also applies to this variant, because one can just enumerate candidates for (s*g^2 - r*f^2)/q in R.  But just as above, it's strictly better to search for (s * g - r * f)/q, where r/s = h mod q and r,s are as short as you can make them.

Chris

[Jean-François Biasse]

Dear Colleagues,

I would like to bring up an important point about the SOLILOQUY quantum attack (the original subject of this thread of messages).

Despite what draft says, it is not a quantum polynomial time attack.

Today, at the ICERM workshop on lattices and cybersecurity, Richard Pinch from CESG described the algorithm as "something that they had reasons to think, at the time, could run in polynomial time. Richard Pinch confirmed that their draft should not be mentioned as a result, but rather as work in progress that stopped at the moment they abandoned the SOLILOQUY project.

I visited Bristol last week to discuss this matter with Dan Sheperd and Richard Pinch. They confirmed my original impression which was that they do not know the complexity of their quantum attack (despite what their draft says).

There are two main obstructions to their method. The first one is that, no matter how elaborate their "quantum fingerprint" is, no one (both inside and outside CESG) has ever analysed its properties (I actually have an internal working document that states it).

The other concerning thing is about the sampling procedure. Indeed, after the Quantum Fourier Transform, they measure the quantum state hoping to get vectors close enough to the dual of the "hidden lattice" with good enough probability. Because of the inherent imprecision due to the discretization of R^n, the only known probability is exponentially bad with the degree. Sean Hallgren does the computation in his 2005 paper. See the top of page 6 of http://www.cse.psu.edu/~sjh26/unitgroup.pdf.

Scientists from the CESG do not know how to overcome that problem. They suggested increasing the precision of the discretization, but this did not work with Hallgren's 2005 paper (thus raising serious questions on the validity of the SOLILOQUY approach).

The natural question is: if they are so far from a solution, then why did they abandon SOLILOQUY ? Interestingly, until last week, they thought that the Eisentrager-Hallgren-Kitaev-Song STOC 2014 paper (http://dl.acm.org/citation.cfm?id=2591860) solved the Principal Ideal Problem in polynomial time. I attended a talk on SOLILOQUY by Dan Sheperd last week and after he made that claim, we had to go together through the STOC paper to find out that they had simply misread the introduction.

The corollary to that question is: why not admit that the Hallgren et al. played a role in their decision (in addition to their work in progress), and why not amend the SOLILOQUY draft ? In our discussions, they made clear that their organization had an agenda in terms of image. They try to convince the general public that they see most of the scientific discoveries coming in advance. This gives their agency credibility when it comes to making recommendations on cryptography. This is apparently incompatible with admitting being wrong.

I am currently working with Fang Song on a solution to the PIP (among other things). It should also be referred to as "work in progress". Also, if we end up being right, this will not validate the CESG's approach. Indeed, there is absolutely no intersection between our approach and that suggested in the SOLILOQUY draft. If someone refers to the SOLILOQUY attack as a polynomial time one, they should bring a proof of that statement.

Regards,

Jean-François Biasse

--

You received this message because you are subscribed to the Google Groups "Cryptanalytic algorithms" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cryptanalytic-algo...@googlegroups.com.
To post to this group, send email to cryptanalyti...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/cryptanalytic-algorithms/CACOo0Qh0SDsGNdexup9hYCfCRSDhCAHUW7P1YhS_G%3DD%2ByLsUPQ%40mail.gmail.com.