Representing hard lattices with O(n log n) bits

ABSTRACT

We present a variant of the Ajtai-Dwork public-key cryptosystem where the size of the public-key is only O(nlog n) bits and the encrypted text/clear text ratio is also O(nlog n). This is true with the assumption that all of the participants in the cryptosystem share O(n²log n) random bits which has to be picked only once and the users of the cryptosystem get them e.g. together with the software implementing the protocol. The public key is a random lattice with an n^c-unique nonzero shortest vector, where the constant c>1‾2 can be picked arbitrarily close to 1‾2, and we pick the lattice according to a distribution described in the paper. We do not prove a worst-case average-case equivalence but the security of the system follows from the hardness of a randomized diophantine approximation problem related to a well-known theorem of Dirichlet.

REFERENCES

• 1: Miklós Ajtai , Cynthia Dwork, A public-key cryptosystem with worst-case/average-case equivalence, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.284-293, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258604]
• 2: Miklós Ajtai , Ravi Kumar , D. Sivakumar, A sieve algorithm for the shortest lattice vector problem, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.601-610, July 2001, Hersonissos, Greece [doi>10.1145/380752.380857]
• 3: W. Banaszczyk, New bounds in some transference theorems in the geometry of numbers. Matematische Annalen 296(4):625--635, 1993.
• 4: Oded Goldreich , Shafi Goldwasser , Shai Halevi, Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.105-111, August 17-21, 1997
• 5: P. M. Gruber and C. G. Lekkerkerker. Geometry of Numbers, Chapter 3. North Holland 1987.
• 6: P. R. Halmos. Measure Theory D. Van Nostrand Company, 1950.
• 7: Jeffrey Hoffstein , Jill Pipher , Joseph H. Silverman, NTRU: A Ring-Based Public Key Cryptosystem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.267-288, June 21-25, 1998
• 8: A. K. Lenstra, H. W. Lenstra, L. Lovász Factoring polynomials with rational coefficients, Math. Ann. 261, 515-534 (1982).
• 9: Daniele Micciancio, Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.356-365, November 16-19, 2002
• 10: Daniele Micciancio, Improving Lattice Based Cryptosystems Using the Hermite Normal Form, Revised Papers from the International Conference on Cryptography and Lattices, p.126-145, March 29-30, 2001
• 11: Oded Regev, New lattice based cryptographic constructions, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780603]
• 12: C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theoretical Computer Science, v.53 n.2-3, p.201-224, Aug. 1987 [doi>10.1016/0304-3975(87)90064-8 ]
• 13: Wolfgang M. Schmidt Diophantine approximation, Springer Lecture Notes, Springer 1970.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
algorithm, lattice, public-key cryptosystem