*This note, and follow-up discussion, was also posted to
the cryptanalytic-algorithms
mailing list.*

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 is claimed to break
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~~ 2/3), where n is the dimension of the ideal lattices. For more
background, see the
GCHQ paper, Dan's
summary, and Dan's earlier blog post
on similar topics.

*[Update 2/21]* As a quick recap, the attack works in two
phases: first, it recovers some arbitrary generator of the principal
ideal given by the public key. This can be done classically in
subexponential time using techniques similar to the number field
sieve, or quantumly in polynomial time using recent works by
Eisenträger-Hallgren-Kitaev-Song and Biasse-Song. Then, it
classically converts the generator to a *short* generator,
which recovers the secret key. An important contribution of the GCHQ
paper is that this second step can be done nearly instantaneously—at
least for the kinds of ideals used in Soliloquy—using well-known
techniques.

*[Update 6/20]* Although the Soliloquy paper claims to give a
polynomial-time quantum algorithm for the first part of the attack, it
does not give a rigorous analysis or proof, and some experts have
pointed out technical problems with the approach. So the question of
whether there is a polynomial-time algorithm for the quantum part of
the attack still remains unresolved in the literature, though there
are ongoing efforts to address this. (All the *classical*
algorithms for both parts of the attack have been rigorously
established, however.)

In this note I'd like to shed some more light on the implications of the 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, Craig Gentry, and Jean-François Biasse for many discussions that influenced this note.)

- “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*. - 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. - 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.
- 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. - 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.

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:

- Not all (factoring-related) problems are equally hard.
- The “average case” for a problem may be easier than the “worst case.”

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 toideallattices 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 toprincipalideal 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 is indeed 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).

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 theonlyway to break the cryptosystem (within some formal attack model) on its random instances is by being able to solve the underlying lattice problem in theworst 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.)

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.

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, and Oded
Regev is coming soon. *[Update 3/23]*: the paper is
available here.)

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 for security 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.

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.

*Chris Peikert*, 19 Feb 2015