Chris Peikert writes:
> All one needs to break SG-Principal-SVP in a given ring is a reasonably
> good basis of the ring's log-unit lattice, and it's reasonable to
> expect that such bases exist and can be found for many classes of rings.
Of course the lattice _has_ a good basis, but why should a good basis be
easy to find?
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.
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.
Such an algorithm would, I think, be a solid step towards breaking much
larger parts of ideal-lattice cryptography. For example, I think that
short nonzero vectors in NTRU lattices for a degree-n field can be
viewed as short generators of principal-ideal lattices for a degree-2n
field, implying that degree-n NTRU would be broken by a solution to the
short-generator problem for the degree-2n field.I would be very interested to know if this is really true. I think people have attempted such a connection in the past, but to my knowledge it has never worked out. NTRU lattices have a "quasi-cyclic" structure, in which the two halves of the 2n coordinates "rotate" in concert -- I don't know whether this can be encoded as a principal ideal in a degree-2n number field.However, suppose it did work out, and NTRU -- which does not have any security reduction, worst-case or otherwise -- does indeed fall to an attack on the SG-Principal-SVP problem. Then this would be another piece of evidence in favor of having worst-case security reductions from harder problems like Ideal-SVP.
Chris
Such an algorithm would, I think, be a solid step towards breaking much
larger parts of ideal-lattice cryptography. For example, I think that
short nonzero vectors in NTRU lattices for a degree-n field can be
viewed as short generators of principal-ideal lattices for a degree-2n
field, implying that degree-n NTRU would be broken by a solution to the
short-generator problem for the degree-2n field.I would be very interested to know if this is really true. I think people have attempted such a connection in the past, but to my knowledge it has never worked out. NTRU lattices have a "quasi-cyclic" structure, in which the two halves of the 2n coordinates "rotate" in concert -- I don't know whether this can be encoded as a principal ideal in a degree-2n number field.However, suppose it did work out, and NTRU -- which does not have any security reduction, worst-case or otherwise -- does indeed fall to an attack on the SG-Principal-SVP problem. Then this would be another piece of evidence in favor of having worst-case security reductions from harder problems like Ideal-SVP.The existence of a map that Dan mentions would be quite scary for all of ideal lattice crypto -- proofs or not. As Chris said, NTRU lattices have a quasi-cyclic structure where the two halves of the 2n coordinates "rotate in concert". But analogously, Ring-LWE lattices have a quasi-cyclic structure where the three thirds of the 3n coordinates "rotate in concert", and the elements are basically just as short as in NTRU lattices. So presumably, if one could transform an NTRU lattice into a principal ideal lattice of dimension 2n, one could possibly do the same thing with a Ring-LWE lattice into dimension 3n. This is of course not a proof and there could be some weird reason that it works for NTRU and not for Ring-LWE, but it would be kind of surprising (and very enlightening).
Christopher J Peikert writes:
> I am not claiming that it really *is* free -- only that it is safer to
> treat it as if it could be free, because it's a fixed one-time cost
> that is amortized over all keys in the world.
Underestimating the attack cost isn't necessarily "safer". Consider the
problem faced by a user who wants to choose the strongest system that he
can, subject to performance constraints: maybe X is stronger than Y, but
your underestimate of the security of X is _below_ your underestimate of
the security of Y, misleading the user into choosing Y.
Christopher J Peikert writes:
> NTRU lattices have a "quasi-cyclic" structure, in which the two halves
> of the 2n coordinates "rotate" in concert -- I don't know whether this
> can be encoded as a principal ideal in a degree-2n number field.
Define K as \Q[x]/\Phi_N(x), where as usual \Phi_N is the Nth cyclotomic
polynomial. Define R as \Z[x]/\Phi_N(x). Then R is the ring of integers of K.
Define L as K[y]/(y^2-r), where r is a non-square in R. Then L is a
degree-2n number field. Define S as R[y]/(y^2-r).
For comparison: In NTRU, the secret key consists of two short elements
f,g of R, where 3g and 1+3f are both invertible in R/q; here q is a
standard integer. The public key h in R is a minimal representative of
3g/(1+3f) modulo q. Define the "NTRU lattice" L as the set of (u,v) in
R^2 such that v is congruent to uh modulo q.
Assume that r is congruent to h^2 modulo q (i.e., r-h^2 is in qR), and
define I as the R-submodule (y+h)R + qR of S. Then I is an ideal of S.
This 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.
> I think people have attempted such a connection in the past, but to my
> knowledge it has never worked out.
You keep making vague claims that people have tried attacking various
problems. Could you please get in the habit of providing evidence to
back up these claims? Anyone interested in working on better algorithms
will want to see the details of _what_ has been tried before, what the
methods _did_ succeed in doing, and what the methods did _not_ succeed
in doing. If this documentation doesn't exist then it's much more likely
that there haven't been any serious efforts.
Christopher J Peikert writes:
> Across math and science, serious attempts that fail to solve problems
> are rarely written up in any detail or made public (for one thing,
> conferences and journals tend not to publish them).
My experience is that pretty much every useful algorithmic idea starts
out solving _some_ problems.
> We can't preprocess S before seeing the public key, and we have
> little idea what the units of S look like ahead of time.
Why are you now commenting on the hardness of the short-generator
problem? Weren't you, a moment ago, dismissing the short-generator
problem as being irrelevant to lattice-based cryptography?
one can't be so cavalier regarding the
importance of the short-generator problem.
What I'm saying is that there's a plausible way to break NTRU _if_ one
has a solution to ...
As for the hardness of the problem, I agree that the GCHQ idea doesn't
instantly solve the whole problem, but my blog post explains a concrete
strategy to exploit subfields to make unit CVP easier.
> This choice of S completely distorts the *geometry* of the problem
No: your preconceived notion of "short" simply isn't relevant here. What
ultimately matters is that the log of the generator is close enough to 0
to be found efficiently by the unit CVP attack.
Hello,
Dan wrote:
„I'd also encourage new researchers to introduce themselves here, say what they're thinking of working on, and ask what has been done already, so that we can all avoid accidental duplication of effort.“
I would like to take this opportunity to introduce myself. My name is Thomas Wunderer and I am a new PhD student here at Technische Universität Darmstadt working on lattice-based cryptography. Because of my background in algebraic number theory, at the moment my main interest lies in ideal lattices.
This is an incomplete list of interesting research topics I have gathered so far:
1. 1. Finding some generator of a principal ideal.
2. 2. Given some generator of a principal ideal, find a short generator.
3. 3. Is there a connection between short(est) generators and short(est) vectors?
4. 4. Given a (shortest) generator of a principal ideal lattice, is SVP/CVP easy/easier to solve?
5. 5. Apply the obtained results to specific schemes.
6. 6. How to deal with the mod q structure?
7. 7. Anything non-trivial about non-principal ideal lattices.
8. 8. Expanding on the “dimension-halvening technique” for principal ideal lattices using the Gentry-Szydlo algorithm (described here https://eprint.iacr.org/2012/610.pdf)
9. 9. Identifying more weak instances (see Dan’s other topic in the group).
As I am just starting out, choosing first topics to begin with seems not too easy. So if you have any advice, I would be happy if you let me know. If you have any additions to the list, feel free to extend it. Also, if you have done or are aware of any work in these (or similar) areas, please share your knowledge.
I will now ask some specific questions related to some of the above topics. The questions are motivated by quotes from this discussion, but I encourage everyone, not just the author of the quotes, to answer.
Ad 1.:
Dan wrote:
“My blog
post http://blog.cr.yp.to/20140213-ideal.html says that this is
all wrong: the computation, optimized sensibly, should be heavily
subexponential in the field degree.”
Has there been some progress (in special cases)? In my understanding, finding a generator of a principal ideal is still considered a very difficult task in algebraic number theory. I hope to talk more with Jean-François Biasse at the Mathematics of Lattices Workshop (http://icerm.brown.edu/topical_workshops/tw15-7-mlc/) about this topic.
Ad 2.:
Dan wrote:
“Of course
the [log unit] lattice _has_ a good basis, but why should a good basis be
easy to find? Here are the approaches that we've seen: […] For cyclotomics:
simply _write down_ a good basis (polynomial time), as GCHQ suggested.”
Does this work this easy for all cyclotomics or just special cases (e.g. power-of-two)? If I remember it correctly, the GCHQ paper makes some assumptions, and I am not sure in which cases they are actually satisfied.
Ad 3. and 4.:
Chris wrote:
“SG-Principal-SVP: same as Principal-SVP, but specialized to principal ideals that are promised to have a short generator g. (Such ideals are a very small fraction of all principal ideals.)”
And
“But for the vast majority of principal ideals, even the shortest generator is an invalid solution to Principal-SVP, because it is *much* longer than the shortest lattice vector, by a factor of 2^sqrt{n} or so.”
I agree to consider the case where one is promised a short generator as a separate case. But how do you draw the conclusion that such principal ideals are a very small fraction? In particular, where does the factor 2^sqrt(n) come from? I remember that I have heard statements like “typical generators are short” as well as statements similar to yours, but no evidence to support either claim. Did you (or somebody else) collect some empirical data about the relation between short(est) vectors and short(est) generators? I recently read a PhD thesis that wants to connect short generators and short vectors (http://repository.lib.ncsu.edu/ir/bitstream/1840.16/10072/1/etd.pdf). Although the results are not too convincing, he seems to believe that there is a connection between short(est) vectors and short(est) generators. The author first shows that in dimension 1 and 2, shortest vectors are always generators (not relevant for crypto). Then he presents empirical tests in higher dimensions showing that with high probability (at least 95 %) the “short” vector output by LLL given the rotation basis of a generator is a generator of the same ideal. He then suggests that therefore short(est) vectors in a principal ideal might be generators. This is the part I was referring to as “not too convincing”. It might be that this is a special property of LLL when given a rotation basis, this could be true for the “somewhat short” vector output by LLL but false for shortest vectors, and so on. By the way, the author points these problems out himself, so he is not to be blamed.
Ad 5.:
Dan mentioned the idea of applying the attack to NTRU. I will not go into this right now, but leave this for a future post. Maybe there are more interesting ideas to rewrite shortest vector problems as short generator problems.
Ad 6.:
Chris wrote:
“In conclusion, NTRU and Ring-LWE lattices do not appear to be principal ideals, or even ideals at all, but merely R_q-modules”
This is a valid point I wondered about before. How do you overcome this obstacle? Are there any ideas?
- Thomas
--
You received this message because you are subscribed to the Google Groups "Cryptanalytic algorithms" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cryptanalytic-algo...@googlegroups.com.
To post to this group, send email to cryptanalyti...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cryptanalytic-algorithms/20150305165237.8911.qmail%40cr.yp.to.
For more options, visit https://groups.google.com/d/optout.
Such an algorithm would, I think, be a solid step towards breaking muchlarger parts of ideal-lattice cryptography. For example, I think thatshort nonzero vectors in NTRU lattices for a degree-n field can beviewed as short generators of principal-ideal lattices for a degree-2nfield, implying that degree-n NTRU would be broken by a solution to theshort-generator problem for the degree-2n field.
> NTRU lattices have a "quasi-cyclic" structure, in which the two halves
> of the 2n coordinates "rotate" in concert -- I don't know whether this
> can be encoded as a principal ideal in a degree-2n number field.
Define K as \Q[x]/\Phi_N(x), where as usual \Phi_N is the Nth cyclotomic
polynomial. Then K is a degree-n number field for n = \phi(N), where as
usual phi(N) = deg \Phi_N. For example, if N is in {2,4,8,...} then
n = N/2 and \Phi_N(x) = x^n + 1.
Define R as \Z[x]/\Phi_N(x). Then R is the ring of integers of K.
Define L as K[y]/(y^2-r), where r is a non-square in R. Then L is a
degree-2n number field.
Define S as R[y]/(y^2-r). S isn't necessarily the ring of integers of L,
but it's close enough that everything I'll say about ideals of S can
easily be adapted to ideals of the ring of integers.
Define the "NTRU lattice" L as the set of (u,v) in
R^2 such that v is congruent to uh modulo q, i.e., as the R-submodule
(1,h)R + (0,q)R
of R^2. The NTRU key-recovery problem is the problem of finding the
short nonzero vector (f,g) of L, given h.
Assume that r is congruent to h^2 modulo q (i.e., r-h^2 is in qR), and
define I as the R-submodule (y+h)R + qR of S. Then I is an ideal of S,
since
y(y+h) = yh + r = (y+h)h + r-h^2 and
yq = (y+h)q - hq
are both in I. Furthermore, I is the preimage of L under the standard
R-module map from S to R^2 that maps 1 to (0,1) and maps y to (1,0).
This ideal I has a short nonzero vector f*y + g, and the NTRU
key-recovery problem is exactly the problem of finding this vector.
We know that the ideal I contains the short element f*y+g. The only
remaining question is whether I _equals_ (f*y+g)S.
If r is chosen to be small, let's say the minimal representative of h^2
modulo q (assuming that's not a square), then the norm g^2-r*f^2
is a small multiple of q (since f and g are short). This means that
there can't be much gap between (f*y + g)S and I: the ratio is some
small ideal J, and replacing I by IJ will give us exactly the desired
ideal (f*y + g)S. At this point there's a quantitative question of
what exactly "small" means and how many choices for J there are; I'd
resort to computer experiments to get a handle on this.
The ideal J has huge norm, and there are far too many candidates to enumerate.
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.
The number of candidates for the unknown ideal J = I' * I^-1 of S is far too large -- much larger than the exponential number c^n of possible secret keys.
It's not just an unlucky happenstance that the number of candidates for J is too large; it's essentially inherent to the setup of the attack. This is because we can alternatively view the attack as a (highly suboptimal) enumeration to solve an easy relation on the NTRU key -- without resorting to extension rings, SG-PIP, etc.
As in NFS polynomial selection, instead of merely searching throughintegral r, let's search fractions r/s. If you don't like denominatorsthen you can easily clear them, converting y = sqrt(r/s) into sy =
sqrt(rs), converting the fractional ideal (y+h)R + qR into the ideal
(sy+sh)R + sqR, and converting the target (1+3f)y + 3g into the target
(1+3f)sy + 3sg, which has relative norm s^2(3g)^2 - rs(1+3f)^2, forced
to be a multiple of sq; note that sq is public... [lattice reduction] will
considerably reduce the ratios (s(3g)^2-r(1+3f)^2)/q. Of course, there'sno substitute for a serious quantitative study of how small these normscan actually be pushed.
--
You received this message because you are subscribed to the Google Groups "Cryptanalytic algorithms" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cryptanalytic-algo...@googlegroups.com.
To post to this group, send email to cryptanalyti...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cryptanalytic-algorithms/CACOo0Qh0SDsGNdexup9hYCfCRSDhCAHUW7P1YhS_G%3DD%2ByLsUPQ%40mail.gmail.com.