Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #7 to TR11-050 | 9th February 2012 14:44

Accelerated and Improved Slide- and LLL-Reduction

RSS-Feed




Revision #7
Authors: Claus-Peter Schnorr
Accepted on: 9th February 2012 14:44
Downloads: 917
Keywords: 


Abstract:

We accelerate the slide-reduction algorithm of [GN08] with blocksize k to run for a given LLL-basis B of dimension n= hk under reasonable assumptions within \ $\frac14\, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \ local SVP-computations of dimension k, where $\alpha \ge \frac 43$ is the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize k/2 the $\frac14 \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ bound further decreases to $ nh^2(1 +\log_{1+\varepsilon} \gamma_{k/2})$, where $\gamma_{k/2}$ is the Hermite constant.
These bounds are polynomial in $n$ for arbitrary bit-length of $B$. Slide-reduced bases for which the approximation factor $\|\mathbf{b}_1\|/\lambda_1$ is nearly maximal can easily be improved. If $\|\mathbf{b}_1\|/\lambda_1 = \gamma_k^{\frac{n-k}{k-1}}$ is maximal we can easily find a shortest lattice vector. We also accelerate LLL-reduction.\[1mm]

\noindent{\bf Keywords.} Block reduction, LLL-reduction, slide reduction.



Changes to previous version:

We add in Theorem 4 and Theorem 5 a fast method to improve slide-reduced bases for $k$ and $\varepsilon =0$ which maximize approximation factor $\|\mathbf{b}_1\|/\lambda_1$. A shortest lattice vector can easily be found for such worst case slide-reduced bases. For LLL-bases with $\delta =1$ this finds a shortest lattice vector in $n^2$ arithmetic steps, see Theorem 5.

On page 3 we correct the sum $ \sum_{\ell =1}^{h-1} h\ell -\ell^2 =
\frac {h^3-h}{6}$ which was wrongly written as $\sum_{\ell =1}^{h-1} h\ell -\ell^2 = \frac {h^3-h^2 -h}{6}$


Revision #6 to TR11-050 | 9th December 2011 09:42

Accelerated Slide- and LLL-Reduction





Revision #6
Authors: Claus-Peter Schnorr
Accepted on: 9th December 2011 09:42
Downloads: 941
Keywords: 


Abstract:

We accelerate the slide-reduction algorithm of [GN08] with blocksize $k$ to run for a given LLL-basis $B$ of dimension $n= hk$ under reasonable assumptions within \ $\frac14\, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \
local SVP-computations of dimension $k$, where $\alpha \ge \frac 43$ is the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize $k/2$ the $\frac14 \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ bound
further decreases to $ nh^2(1 + \log_{1+\varepsilon} \gamma_{k/2})$, where $\gamma_{k/2}$ is the Hermite constant. These bounds are polynomial in $n$ for arbitrary bit-length of $B$. We also accelerate LLL-reduction.



Changes to previous version:

We describe the algorithms ASR for accelerated almost slide reduction and ALR for accelerated LLL-reduction more explicitely. The notion of almost slide reduced basis, (asr-basis) has been slightly modified to simplify the proofs of the theorems. We indicate how to extend the algorithms to the case of highest quality where epsilon =0 so that the polynomial time bounds are preserved


Revision #5 to TR11-050 | 22nd August 2011 15:00

Accelerated Slide- and LLL-Reduction





Revision #5
Authors: Claus-Peter Schnorr
Accepted on: 22nd August 2011 15:00
Downloads: 821
Keywords: 


Abstract:

Given an LLL-basis $B$ of dimension $n= hk$ we accelerate slide-reduction with blocksize $k$ to run under a reasonable assjmption in \
$\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \
local SVP-computations in dimension $k$, where $\alpha \ge \frac 43$
measures the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize $k/2$ then the number of local SVP-computations for slide-reduction with blocksize $k$ reduces to $\frac 23 h^3(1 + \log_{1+\varepsilon} \gamma_{k/2})$. This bound is polynomial for arbitrary bit-length of $B$, it improves previous bounds considerably. We also accelerate LLL-reduction.} \\[1mm]

\noindent{\bf Keywords.} Block reduction, LLL-reduction, slide reduction.



Changes to previous version:

In the proof of Theorem 2at one point the exponent h-2\ell -1 of (\mathcal+\ell/\mathcal{D}_\ell+1) was missing and has been inserted.
Some proofs have been updated for better readability.
The integer m associated to ASR and ALR has been replaced by two different integers \mu and \bar{\mu} which enter the analysis.


Revision #4 to TR11-050 | 2nd May 2011 10:14

Accelerated Slide- and LLL-Reduction





Revision #4
Authors: Claus-Peter Schnorr
Accepted on: 2nd May 2011 10:14
Downloads: 801
Keywords: 


Abstract:

Given an LLL-basis $B$ of dimension $n= hk$ we accelerate slide-reduction with blocksize $k$ to run under a reasonable assjmption in \
$\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \
local SVP-computations in dimension $k$, where $\alpha \ge \frac 43$
measures the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize $k/2$ then the number of local SVP-computations for slide-reduction with blocksize $k$ reduces to $\frac 23 h^3(1 + \log_{1+\varepsilon} \gamma_{k/2})$. This bound is polynomial for arbitrary bit-length of $B$, it improves previous bounds considerably. We also accelerate LLL-reduction.} \\[1mm]

\noindent{\bf Keywords.} Block reduction, LLL-reduction, slide reduction.



Changes to previous version:

misprint in reference [S06]


Revision #3 to TR11-050 | 20th April 2011 09:34

Accelerated Slide- and LLL-Reduction





Revision #3
Authors: Claus-Peter Schnorr
Accepted on: 20th April 2011 09:34
Downloads: 1473
Keywords: 


Abstract:

Given an LLL-basis $B$ of dimension $n= hk$ we accelerate slide-reduction with blocksize $k$ to run under a reasonable assjmption in \
$\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \ local SVP-computations in dimension $k$, where $\alpha \ge \frac 43$
measures the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize $k/2$ then the number of local SVP-computations for slide-reduction with blocksize $k$ reduces to $\frac 23 h^3(1 + \log_{1+\varepsilon} \gamma_{k/2})$. This bound is polynomial for arbitrary bit-length of $B$, it improves previous bounds considerably. We also accelerate LLL-reduction.}

\noindent{\bf Keywords.} Block reduction, LLL-reduction, slide reduction.



Changes to previous version:

The paragraph Time bound compared to[GN08] on page 3
has been revised


Revision #2 to TR11-050 | 13th April 2011 09:26

Accelerated Slide- and LLL-Reduction





Revision #2
Authors: Claus-Peter Schnorr
Accepted on: 13th April 2011 09:26
Downloads: 964
Keywords: 


Abstract:

Given an LLL-basis $B$ of dimension $n= hk$ we accelerate slide-reduction with blocksize $k$ to run under a reasonable assjmption in \
$\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \
local SVP-computations in dimension $k$, where $\alpha \ge \frac 43$
measures the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize $k/2$ then the number of local SVP-computations for slide-reduction with blocksize $k$ reduces to $\frac 23 h^3(1 + \log_{1+\varepsilon} \gamma_{k/2})$. This bound is polynomial for arbitrary bit-length of $B$, it improves previous bounds considerably. We also accelerate LLL-reduction.} \\[1mm]

\noindent{\bf Keywords.} Block reduction, LLL-reduction, slide reduction.



Changes to previous version:

The reference [HPS11]has been added


Revision #1 to TR11-050 | 11th April 2011 14:12

Accelerated Slide- and LLL-Reduction





Revision #1
Authors: Claus-Peter Schnorr
Accepted on: 11th April 2011 14:12
Downloads: 1206
Keywords: 


Abstract:

Given an LLL-basis $B$ of dimension $n= hk$ we accelerate slide-reduction with blocksize $k$ to run under a reasonable assumption in \ $\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \ local SVP-computations in dimension $k$, where $\alpha \ge \frac 43$ measures the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize $k/2$ then the number of local SVP-computations for slide-reduction with blocksize $k$ reduces to $\frac 23 h^3(1 + \log_{1\varepsilon} \gamma_{k/2})$. This bound is polynomial for arbitrary bit-length of $B$, it improves previous bounds considerably. We also accelerate LLL-reduction.} \\[1mm]

\noindent{\bf Keywords.} Block reduction, LLL-reduction, slide reduction.



Changes to previous version:

the misprint "assjmption" in the abstract is corrected to assumption


Paper:

TR11-050 | 11th April 2011 10:18

Accelerated Slide- and LLL-Reduction





TR11-050
Authors: Claus-Peter Schnorr
Publication: 11th April 2011 10:55
Downloads: 1172
Keywords: 


Abstract:

Given an LLL-basis $B$ of dimension $n= hk$ we accelerate slide-reduction with blocksize $k$ to run under a reasonable assjmption in \
$\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \
local SVP-computations in dimension $k$, where $\alpha \ge \frac 43$
measures the quality of the given LLL-basis and $\varepsilon$ is the quality of slide-reduction. If the given basis $B$ is already slide-reduced for blocksize $k/2$ then the number of local SVP-computations for slide-reduction with blocksize $k$ reduces to $\frac 23 h^3(1 + \log_{1+\varepsilon} \gamma_{k/2})$. This bound is polynomial for arbitrary bit-length of $B$, it improves previous bounds considerably. We also accelerate LLL-reduction.} \\[1mm]

\noindent{\bf Keywords.} Block reduction, LLL-reduction, slide reduction.



ISSN 1433-8092 | Imprint