The Experts below are selected from a list of 210 Experts worldwide ranked by ideXlab platform

Dandapani Sivakumar - One of the best experts on this subject based on the ideXlab platform.

Ravi Kumar - One of the best experts on this subject based on the ideXlab platform.

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, 2002
    Co-Authors: Miklós Ajtai, Ravi Kumar, D Sivakumar
    Abstract:

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

  • CaLC - An Overview of the Sieve Algorithm for the Shortest Lattice Vector Problem
    Lecture Notes in Computer Science, 2001
    Co-Authors: Miklós Ajtai, Ravi Kumar, Dandapani Sivakumar
    Abstract:

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

  • a sieve algorithm for the Shortest Lattice Vector problem
    Symposium on the Theory of Computing, 2001
    Co-Authors: Miklós Ajtai, Ravi Kumar, Dandapani Sivakumar
    Abstract:

    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, 2001
    Co-Authors: Miklós Ajtai, Ravi Kumar, Dhenuvakonda Sivakumar
    Abstract:

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

  • STOC - A sieve algorithm for the Shortest Lattice Vector problem
    Proceedings of the thirty-third annual ACM symposium on Theory of computing - STOC '01, 2001
    Co-Authors: Miklós Ajtai, Ravi Kumar, Dandapani Sivakumar
    Abstract:

    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.

Jin-yi Cai - One of the best experts on this subject based on the ideXlab platform.

  • A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor
    Discrete Applied Mathematics, 2003
    Co-Authors: Jin-yi Cai
    Abstract:

    We prove a new transference theorem in the geometry of numbers, giving optimal bounds relating the successive minima of a Lattice with the minimal length of generating Vectors of its dual. It generalizes the transference theorem due to Banaszczyk. We also prove a stronger bound for the special class of Lattices possessing ne-unique Shortest Lattice Vectors. The theorem imply consequent improvement of the Ajtai connection factors in the connection of average-case to worst-case complexity of the Shortest Lattice Vector problem. Our proofs are non-constructive, based on discrete Fourier transform.

  • COCOON - A new transference theorem in the geometry of numbers
    Lecture Notes in Computer Science, 1999
    Co-Authors: Jin-yi Cai
    Abstract:

    We prove a new transference theorem in the geometry of numbers, giving optimal bounds relating the successive minima of a Lattice with the minimal length of generating Vectors of its dual. It generalizes the transference theorem due to Banaszczyk. The theorem is motivated by our efforts to improve Ajtai's connection factors in the connection of average-case to worst-case complexity of the Shortest Lattice Vector problem. Our proofs are non-constructive, based on methods from harmonic analysis.

  • A Lattice-Based Public-Key Cryptosystem
    Information & Computation, 1999
    Co-Authors: Jin-yi Cai, Thomas W. Cusick
    Abstract:

    Ajtai recently found a random class of Lattices of integer points for which he could prove the following worst-case/average-case equivalence result: If there is a probabilistic polynomial time algorithm which finds a short Vector in a random Lattice from the class, then there is also a probabilistic polynomial time algorithm which solves several problems related to the Shortest Lattice Vector problem (SVP) in any n-dimensional Lattice. Ajtai and Dwork then designed a public-key cryptosystem which is provably secure unless the worst case of a version of the SVP can be solved in probabilistic polynomial time. However, their cryptosystem suffers from massive data expansion because it encrypts data bit-by-bit. Here we present a public-key cryptosystem based on similar ideas, but with much less data expansion.

  • Approximating the SVP to within a Factor (1+1/dimε) Is NP-Hard under Randomized Reductions
    Journal of Computer and System Sciences, 1999
    Co-Authors: Jin-yi Cai, Ajay Nerurkar
    Abstract:

    Recently Ajtai showed that to approximate the Shortest Lattice Vector in the l2-norm within a factor (1+2?dimk), for a sufficiently large constant k, is NP-hard under randomized reductions. We improve this result to show that to approximate a Shortest Lattice Vector within a factor (1+dim??), for any ?>0, is NP-hard under randomized reductions. Our proof also works for arbitrary lp-norms, 1?p

  • Selected Areas in Cryptography - A Lattice-Based Public-Key Cryptosystem
    Selected Areas in Cryptography, 1999
    Co-Authors: Jin-yi Cai, Thomas W. Cusick
    Abstract:

    Ajtai recently found a random class of Lattices of integer points for which he could prove the following worst-case/average-case equivalence result: If there is a probabilistic polynomial time algorithm which finds a short Vector in a random Lattice from the class, then there is also a probabilistic polynomial time algorithm which solves several problems related to the Shortest Lattice Vector problem (SVP) in any n-dimensional Lattice. Ajtai and Dwork then designed a public-key cryptosystem which is provably secure unless the worst case of a version of the SVP can be solved in probabilistic polynomial time. However, their cryptosystem suffers from massive data expansion because it encrypts data bit-by-bit. Here we present a public-key cryptosystem based on similar ideas, but with much less data expansion.

Damien Stehle - One of the best experts on this subject based on the ideXlab platform.

  • Accelerating Lattice reduction with FPGAs
    2010
    Co-Authors: Jérémie Detrey, Xavier Pujol, Guillaume Hanrot, Damien Stehle
    Abstract:

    We describe an FPGA accelerator for the Kannan­–Fincke­–Pohst enumeration algorithm (KFP) solving the Shortest Lattice Vector Problem (SVP). This is the first FPGA implementation of KFP specifically targeting cryptographically relevant dimensions. In order to optimize this implementation, we theoretically and experimentally study several facets of KFP, including its efficient parallelization and its underlying arithmetic. Our FPGA accelerator can be used for both solving stand-alone instances of SVP (within a hybrid CPU­–FPGA compound) or myriads of smaller dimensional SVP instances arising in a BKZ-type algorithm. For devices of comparable costs, our FPGA implementation is faster than a multi-core CPU implementation by a factor around 2.12.

  • LATINCRYPT - Accelerating Lattice reduction with FPGAs
    Lecture Notes in Computer Science, 2010
    Co-Authors: Jérémie Detrey, Xavier Pujol, Guillaume Hanrot, Damien Stehle
    Abstract:

    We describe an FPGA accelerator for the Kannan-Fincke-Pohst enumeration algorithm (KFP) solving the Shortest Lattice Vector Problem (SVP). This is the first FPGA implementation of KFP specifically targeting cryptographically relevant dimensions. In order to optimize this implementation, we theoretically and experimentally study several facets of KFP, including its efficient parallelization and its underlying arithmetic. Our FPGA accelerator can be used for both solving stand-alone instances of SVP (within a hybrid CPU-FPGA compound) or myriads of smaller dimensional SVP instances arising in a BKZ-type algorithm. For devices of comparable costs, our FPGA implementation is faster than a multi-core CPU implementation by a factor around 2.12.

  • solving the Shortest Lattice Vector problem in time 2 2 465n
    IACR Cryptol. ePrint Arch., 2009
    Co-Authors: Xavier Pujol, Damien Stehle
    Abstract:

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

  • Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases
    arXiv: Number Theory, 2008
    Co-Authors: Guillaume Hanrot, Damien Stehle
    Abstract:

    The Hermite-Korkine-Zolotarev reduction plays a central role in strong Lattice reduction algorithms. By building upon a technique introduced by Ajtai, we show the existence of Hermite-Korkine-Zolotarev reduced bases that are arguably least reduced. We prove that for such bases, Kannan's algorithm solving the Shortest Lattice Vector problem requires~$d^{\frac{d}{2\e}(1+o(1))}$ bit operations in dimension~$d$. This matches the best complexity upper bound known for this algorithm. These bases also provide lower bounds on Schnorr's constants~$\alpha_d$ and~$\beta_d$ that are essentially equal to the best upper bounds. Finally, we also show the existence of particularly bad bases for Schnorr's hierarchy of reductions.

  • improved analysis of kannan s Shortest Lattice Vector algorithm
    International Cryptology Conference, 2007
    Co-Authors: Guillaume Hanrot, Damien Stehle
    Abstract:

    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.