The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
Ravi Kumar - One of the best experts on this subject based on the ideXlab platform.
-
sampling short Lattice Vectors and the closest Lattice Vector problem
Conference on Computational Complexity, 2002Co-Authors: Miklós Ajtai, Ravi Kumar, D SivakumarAbstract:We present a 2/sup O(n)/ time Turing reduction from the closest Lattice Vector problem to the shortest Lattice Vector problem. Our reduction assumes access to a subroutine that solves SVP exactly and a subroutine to sample short Vectors from a Lattice, and computes a (1+/spl epsi/)-approximation to CVP As a consequence, using the SVP algorithm from (Ajtai et al., 2001), we obtain a randomized 2[O(1+/spl epsi//sup -1/)n] algorithm to obtain a (1+/spl epsi/)-approximation for the closest Lattice Vector problem in n dimensions. This improves the existing time bound of O(n!) for CVP achieved by a deterministic algorithm in (Blomer, 2000).
-
a sieve algorithm for the shortest Lattice Vector problem
Symposium on the Theory of Computing, 2001Co-Authors: Miklós Ajtai, Ravi Kumar, Dandapani SivakumarAbstract:We present a randomized 2^{ O(n) } time algorithm to compute a shortest non-zero Vector in an n -dimensional rational Lattice. The best known time upper bound for this problem was 2^{ O(n \log n )} first given by Kannan [7] in 1983. We obtain several consequences of this algorithm for related problems on Lattices and codes, including an improvement for polynomial time approximations to the shortest Vector problem. In this improvement we gain a factor of log log n in the exponent of the approximating factor.
-
an overview of the sieve algorithm for the shortest Lattice Vector problem
Lecture Notes in Computer Science, 2001Co-Authors: Miklós Ajtai, Ravi Kumar, Dhenuvakonda SivakumarAbstract:We present an overview of a randomized 2g(n) time algorithm to compute a shortest non-zero Vector in an n-dimensional rational Lattice. The complete details of this algorithm can be found in [2].
-
on polynomial approximation to the shortest Lattice Vector length
Symposium on Discrete Algorithms, 2001Co-Authors: Ravi Kumar, Dandapani SivakumarAbstract:We obtain a 2O(n/∈) time algorithm to approximate the length of the shortest Vector in an n-dimensional Lattice to within a factor of n3+∈.
-
a note on the shortest Lattice Vector problem
Conference on Computational Complexity, 1999Co-Authors: Ravi Kumar, Dandapani SivakumarAbstract:We show that the problem of deciding whether a given rational Lattice L has a Vector of length less than some given value r is NP-hard under randomized reductions, even under the promise that L has exactly zero or one Vector of length less than r.
Dandapani Sivakumar - One of the best experts on this subject based on the ideXlab platform.
-
a sieve algorithm for the shortest Lattice Vector problem
Symposium on the Theory of Computing, 2001Co-Authors: Miklós Ajtai, Ravi Kumar, Dandapani SivakumarAbstract:We present a randomized 2^{ O(n) } time algorithm to compute a shortest non-zero Vector in an n -dimensional rational Lattice. The best known time upper bound for this problem was 2^{ O(n \log n )} first given by Kannan [7] in 1983. We obtain several consequences of this algorithm for related problems on Lattices and codes, including an improvement for polynomial time approximations to the shortest Vector problem. In this improvement we gain a factor of log log n in the exponent of the approximating factor.
-
on polynomial approximation to the shortest Lattice Vector length
Symposium on Discrete Algorithms, 2001Co-Authors: Ravi Kumar, Dandapani SivakumarAbstract:We obtain a 2O(n/∈) time algorithm to approximate the length of the shortest Vector in an n-dimensional Lattice to within a factor of n3+∈.
-
a note on the shortest Lattice Vector problem
Conference on Computational Complexity, 1999Co-Authors: Ravi Kumar, Dandapani SivakumarAbstract:We show that the problem of deciding whether a given rational Lattice L has a Vector of length less than some given value r is NP-hard under randomized reductions, even under the promise that L has exactly zero or one Vector of length less than r.
Damien Stehle - One of the best experts on this subject based on the ideXlab platform.
-
algorithms for the shortest and closest Lattice Vector problems
IWCC'11 Proceedings of the Third international conference on Coding and cryptology, 2011Co-Authors: Guillaume Hanrot, Xavier Pujol, Damien StehleAbstract:We present the state of the art solvers of the Shortest and Closest Lattice Vector Problems in the Euclidean norm. We recall the three main families of algorithms for these problems, namely the algorithm by Micciancio and Voulgaris based on the Voronoi cell [STOC'10], the Monte-Carlo algorithms derived from the Ajtai, Kumar and Sivakumar algorithm [STOC'01] and the enumeration algorithms originally elaborated by Kannan [STOC'83] and Fincke and Pohst [EUROCAL'83]. We concentrate on the theoretical worst-case complexity bounds, but also consider some practical facets of these algorithms.
-
solving the shortest Lattice Vector problem in time 2 2 465n
IACR Cryptol. ePrint Arch., 2009Co-Authors: Xavier Pujol, Damien StehleAbstract:The Shortest Lattice Vector Problem is central in Lattice-based cryptography, as well as in many areas of computational mathematics and computer science, such as computational number theory and combinatorial optimisation. We present an algorithm for solving it in time 2 2.465n+o(n) and space 2 1.233n+o(n) , where n is the Lattice dimension. This improves the best previously known algo- rithm, by Micciancio and Voulgaris (SODA 2010), which runs in time 2 3.199n+o(n) and space 2 1.325n+o(n) .
-
improved analysis of kannan s shortest Lattice Vector algorithm
International Cryptology Conference, 2007Co-Authors: Guillaume Hanrot, Damien StehleAbstract:The security of Lattice-based cryptosystems such as NTRU, GGH and Ajtai-Dwork essentially relies upon the intractability of computing a shortest non-zero Lattice Vector and a closest Lattice Vector to a given target Vector in high dimensions. The best algorithms for these tasks are due to Kannan, and, though remarkably simple, their complexity estimates have not been improved since over twenty years. Kannan's algorithm for solving the shortest Vector problem (SVP) is in particular crucial in Schnorr's celebrated block reduction algorithm, on which rely the best known generic attacks against the Lattice-based encryption schemes mentioned above. In this paper we improve the complexity upper-bounds of Kannan's algorithms. The analysis provides new insight on the practical cost of solving SVP, and helps progressing towards providing meaningful key-sizes.
-
Improved Analysis of Kannan's Shortest Lattice Vector Algorithm
2007Co-Authors: Guillaume Hanrot, Damien StehleAbstract:The security of Lattice-based cryptosystems such as NTRU, GGH and Ajtai-Dwork essentially relies upon the intractability of computing a shortest non-zero Lattice Vector and a closest Lattice Vector to a given target Vector in high dimensions. The best algorithms for these tasks are due to Kannan, and, though remarkably simple, their complexity estimates have not been improved since more than twenty years. Kannan's algorithm for solving the shortest Vector problem is in particular crucial in Schnorr's celebrated block reduction algorithm, on which are based the best known attacks against the Lattice-based encryption schemes mentioned above. Understanding precisely Kannan's algorithm is of prime importance for providing meaningful key-sizes. In this paper we improve the complexity analyses of Kannan's algorithms and discuss the possibility of improving the underlying enumeration strategy.
Miklós Ajtai - One of the best experts on this subject based on the ideXlab platform.
-
sampling short Lattice Vectors and the closest Lattice Vector problem
Conference on Computational Complexity, 2002Co-Authors: Miklós Ajtai, Ravi Kumar, D SivakumarAbstract:We present a 2/sup O(n)/ time Turing reduction from the closest Lattice Vector problem to the shortest Lattice Vector problem. Our reduction assumes access to a subroutine that solves SVP exactly and a subroutine to sample short Vectors from a Lattice, and computes a (1+/spl epsi/)-approximation to CVP As a consequence, using the SVP algorithm from (Ajtai et al., 2001), we obtain a randomized 2[O(1+/spl epsi//sup -1/)n] algorithm to obtain a (1+/spl epsi/)-approximation for the closest Lattice Vector problem in n dimensions. This improves the existing time bound of O(n!) for CVP achieved by a deterministic algorithm in (Blomer, 2000).
-
a sieve algorithm for the shortest Lattice Vector problem
Symposium on the Theory of Computing, 2001Co-Authors: Miklós Ajtai, Ravi Kumar, Dandapani SivakumarAbstract:We present a randomized 2^{ O(n) } time algorithm to compute a shortest non-zero Vector in an n -dimensional rational Lattice. The best known time upper bound for this problem was 2^{ O(n \log n )} first given by Kannan [7] in 1983. We obtain several consequences of this algorithm for related problems on Lattices and codes, including an improvement for polynomial time approximations to the shortest Vector problem. In this improvement we gain a factor of log log n in the exponent of the approximating factor.
-
an overview of the sieve algorithm for the shortest Lattice Vector problem
Lecture Notes in Computer Science, 2001Co-Authors: Miklós Ajtai, Ravi Kumar, Dhenuvakonda SivakumarAbstract:We present an overview of a randomized 2g(n) time algorithm to compute a shortest non-zero Vector in an n-dimensional rational Lattice. The complete details of this algorithm can be found in [2].
T R Fischer - One of the best experts on this subject based on the ideXlab platform.
-
an entropy coded Lattice Vector quantizer for transform and subband image coding
IEEE Transactions on Image Processing, 1996Co-Authors: Z Mohdyusof, T R FischerAbstract:A Lattice-based Vector quantizer (VQ) and noiseless code are proposed for transform and subband image coding. The quantization is simple to implement, and no Vector codebooks need to be stored. The noiseless code enumerates Lattice codeVectors based on their (weighted) l/sub 1/ norm. A software implementation is able to handle Lattice codebooks of size 2/sup 256/. The image coding performance is shown to be comparable or superior to the best encoding methods reported in the literature.
-
subband image coding using a fixed rate Lattice Vector quantizer
International Conference on Image Processing, 1995Co-Authors: Z Mohdyusof, T R FischerAbstract:We present a fixed-rate Lattice VQ (FRLVQ) for subband image coding. The fixed-rate Lattice VQ is an extension of the entropy-coded Lattice Vector quantizer (ECLVQ) [Mohdyusof and Fischer, 1994]. For an error-free channel, image coding using ECLVQ provides competitive performance with other methods. ECLVQ is a variable length coder, hence a single bit error in the encoded bit stream could lead to error propagation resulting in severe degradation in image quality. A fixed-rate Lattice VQ is constructed from the ECLVQ by grouping together several Vectors as a "macroblock". The macroblock is encoded at a fixed rate, while allowing a variety of encoding rates for each Vector in the macroblock. In the event of a transmission error, error propagation is confined to that particular macroblock. In this work we assume the encoded bit stream is transmitted over a binary symmetric channel. The simulation results show that the FRLVQ subband image coding provides competitive performance with other fixed-rate image coding systems. The simulation results also indicate FRLVQ performance degrades gracefully in the presence of channel noise.
-
two stage Vector quantization Lattice Vector quantization
International Symposium on Information Theory, 1994Co-Authors: T R FischerAbstract:A two-stage Vector quantizer is introduced that uses an unstructured first-stage codebook and a second-stage Lattice codebook. Joint optimum two-stage encoding is accomplished by exhaustive search of the parent codebook of the two-stage product code. Due to the relative ease of Lattice Vector quantization, optimum encoding is feasible for moderate-to-large encoding rates and Vector dimensions, provided the first-stage codebook size is kept reasonable. For memoryless Gaussian and Laplacian sources, encoding rates of 2 to 3 b/sample, and Vector dimensions of 8 to 35 the signal-to-noise ratio performance is comparable or superior to equivalent-delay encoding results previously reported. For Gaussian sources with memory, the effectiveness of the encoding method is dependent on the feasibility of using a large enough first-stage Vector quantizer codebook to exploit most of the source memory. >