I am trying to understand how exactly lattice reduction and LWE are linked.
The attacks on LWE I have seen all use lattice reduction in some way or another, dual attacks, uSVP type and so on.
Naively, if I just care about (a couple of) short vectors, it seems overkill to produce a full basis change.
So, what is the intuition behind using the lattice reduction like that?
Something I can imagine is that one needs to make the vectors progressively more orthogonal to have a chance at producing anything short. Does that make any sense?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$– Community BotCommented Mar 22 at 2:29
-
$\begingroup$ @Community what is this bot basing this comment on? $\endgroup$– nnolteCommented Mar 22 at 16:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Lattice basis reduction is not a priori a part of LWE cryptanalysis. It is easy enough to construct relatively effective attacks using only the sieving methods of Ajtai, Kumar and Sivakumar and improvement using the hashing/filtering methods of Larrhoven et al. Lattice reduction can be a useful, practical step in sieving, but not a strictly necessary one.
The useful feature of reduced bases in lattice cryptanalysis is better reduced bases allow more efficient enumeration of all lattice vectors of length below a certain bound. This can be extended to an exhaust of all vectors below the short vector bound which is approximately the approach taken in Schnorr-Euchner enumeration. The quality of a reduction is measured by the lengths of the Gram-Schnmidt vectors associated to a reduced basis, and the work to exhaustively enumerate can be expressed in terms of these values. The trade-off to produce a really reduced basis and the subsequent work to enumerate the shortest vectors is one approach to lattice cryptanalysis, but asymptotically not as effective as sieving.
For lattice problems of current interest, practical attacks seem to hybridise a number of techniques, including sieving, reduction and enumeration. The methods themselves interact: sieving can be an effective way to achieve large block reduction and reduction can be a useful first step before generating a large number of vectors of similar length at the start of sieving.
