ECCC-Report TR11-050https://eccc.weizmann.ac.il/report/2011/050Comments and Revisions published for TR11-050en-usThu, 09 Feb 2012 14:44:40 +0200
Revision 7
| Accelerated and Improved Slide- and LLL-Reduction |
Claus-Peter Schnorr
https://eccc.weizmann.ac.il/report/2011/050#revision7We 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.
Thu, 09 Feb 2012 14:44:40 +0200https://eccc.weizmann.ac.il/report/2011/050#revision7
Revision 6
| Accelerated Slide- and LLL-Reduction |
Claus-Peter Schnorr
https://eccc.weizmann.ac.il/report/2011/050#revision6 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.Fri, 09 Dec 2011 09:42:18 +0200https://eccc.weizmann.ac.il/report/2011/050#revision6
Revision 5
| Accelerated Slide- and LLL-Reduction |
Claus-Peter Schnorr
https://eccc.weizmann.ac.il/report/2011/050#revision5Given 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.Mon, 22 Aug 2011 15:00:06 +0300https://eccc.weizmann.ac.il/report/2011/050#revision5
Revision 4
| Accelerated Slide- and LLL-Reduction |
Claus-Peter Schnorr
https://eccc.weizmann.ac.il/report/2011/050#revision4Given 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.Mon, 02 May 2011 10:14:38 +0300https://eccc.weizmann.ac.il/report/2011/050#revision4
Revision 3
| Accelerated Slide- and LLL-Reduction |
Claus-Peter Schnorr
https://eccc.weizmann.ac.il/report/2011/050#revision3Given 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.Wed, 20 Apr 2011 09:34:23 +0300https://eccc.weizmann.ac.il/report/2011/050#revision3
Revision 2
| Accelerated Slide- and LLL-Reduction |
Claus-Peter Schnorr
https://eccc.weizmann.ac.il/report/2011/050#revision2Given 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.Wed, 13 Apr 2011 09:26:28 +0300https://eccc.weizmann.ac.il/report/2011/050#revision2
Revision 1
| Accelerated Slide- and LLL-Reduction |
Claus-Peter Schnorr
https://eccc.weizmann.ac.il/report/2011/050#revision1Given 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.Mon, 11 Apr 2011 14:12:19 +0300https://eccc.weizmann.ac.il/report/2011/050#revision1
Paper TR11-050
| Accelerated Slide- and LLL-Reduction |
Claus-Peter Schnorr
https://eccc.weizmann.ac.il/report/2011/050Given 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.Mon, 11 Apr 2011 10:55:45 +0300https://eccc.weizmann.ac.il/report/2011/050