Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### Accelerated and Improved Slide- and LLL-Reduction

Revision #7
Authors: Claus-Peter Schnorr
Accepted on: 9th February 2012 14:44
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
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
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
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
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
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:

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
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
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