| Soliloquy | D. J. Bernstein | 08/02/15 14:18 | 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 |
| Re: Soliloquy | Chris Peikert | 19/02/15 14:13 | (An HTML version of this message can be found at 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 , Dan's summary at , and Dan's earlier blog post on similar topics at 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. |
| Re: Soliloquy | D. J. Bernstein | 19/02/15 18:27 | Chris Peikert writes: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 |
| Re: Soliloquy | Chris Peikert | 19/02/15 20:28 | Chris Peikert writes: 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.
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).
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 |
| Re: Soliloquy | Chris Peikert | 19/02/15 21:14 | A correction/clarification:
The online cost is zero for quantum. For non-quantum, it is at most subexponential. |
| Re: Soliloquy | Vadim Lyubashevsky | 20/02/15 03:30 |
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
|
| Re: Soliloquy | Chris Peikert | 20/02/15 05:10 |
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 |
| Re: Soliloquy | D. J. Bernstein | 20/02/15 09:55 | Christopher J Peikert writes: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 itactually 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. |
| Re: Soliloquy | Chris Peikert | 20/02/15 12:32 | 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:
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. |
| Re: Soliloquy | D. J. Bernstein | 21/02/15 09:53 | Christopher J Peikert writes: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. 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 |
| Re: Soliloquy | Chris Peikert | 21/02/15 13:05 | On Sat, Feb 21, 2015 at 12:54 PM, D. J. Bernstein <d...@cr.yp.to> wrote: Christopher J Peikert writes:polynomial. Define R as \Z[x]/\Phi_N(x). Then R is the ring of integers of K.
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 elementsR^2 such that v is congruent to uh modulo q. This is all fine.
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!
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 |
| Re: Soliloquy | D. J. Bernstein | 21/02/15 18:59 | Christopher J Peikert writes: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. :-) 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. 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. 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 |
| Re: Soliloquy | Chris Peikert | 22/02/15 07:15 | On Saturday, February 21, 2015, D. J. Bernstein <d...@cr.yp.to> wrote:Christopher J Peikert writes: 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.
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. 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 Not if you redefine the problem, I can't! What I'm saying is that there's a plausible way to break NTRU _if_ onehas 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). 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?
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? |
| Re: Soliloquy | D. J. Bernstein | 22/02/15 13:15 | Christopher J Peikert writes: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. 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. 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. 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 |
| Re: Soliloquy | Thomas Wunderer | 03/03/15 02:32 | 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
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
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 |
| cyclotomic units | D. J. Bernstein | 05/03/15 08:52 | Thomas Wunderer writes: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 |
| Re: cyclotomic units | Chris Peikert | 05/03/15 09:10 | 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
|
| Re: Soliloquy | Chris Peikert | 01/04/15 09:39 |
I replied: > NTRU lattices have a "quasi-cyclic" structure, in which the two halves 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.)
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) inshort nonzero vector (f,g) of L, given h. So far, so good. We know that the ideal I contains the short element f*y+g. The only This is indeed the key question. If r is chosen to be small, let's say the minimal representative of h^2modulo q (assuming that's not a square), then the norm g^2-r*f^2there can't be much gap between (f*y + g)S and I: the ratio is some 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:
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 ~~~~~
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() |
| Re: Soliloquy | D. J. Bernstein | 05/04/15 11:10 | Christopher J Peikert writes: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. 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. 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. 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 |
| Re: Soliloquy | Chris Peikert | 07/04/15 11:17 | There were two main points to my previous note. The first concerns the runtime of the proposed attack:
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:
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:
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 |
| Re: Soliloquy | Jean-François Biasse | 23/04/15 11:22 | Dear Colleagues, I would like to bring up an important point about the SOLILOQUY quantum attack (the original subject of this thread of messages).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. --You received this message because you are subscribed to the Google Groups "Cryptanalytic algorithms" group.To view this discussion on the web visit https://groups.google.com/d/msgid/cryptanalytic-algorithms/CACOo0Qh0SDsGNdexup9hYCfCRSDhCAHUW7P1YhS_G%3DD%2ByLsUPQ%40mail.gmail.com. |