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.)
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:
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 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
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.)
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 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