CSE206A: Projects

• Explore a topic not covered in class by reading a small number of related papers (typically, 2 or 3), and writing a creative summary that explains the problem addressed in the papers, known solutions, and open problems. No original research result is expected as part of the project, but you should at least be able to describe what the open problems are in the specific area considered in your project.
• Experiment with lattice reduction algorithms, and write a report on your work. Typically, this will address a cryptanalysis problem, but other applications of lattices are fine too. You can try to attack a new cryptanalysis problem if you wish, or more simply try to reproduce and extend the results from some published paper. Since some of the papers below were published 10 or more years ago, you may find out that what you can or cannot do within a reasonable amount of time with today's computers is quite different from what could be done when the paper was written.
• Solve any of the open problems given in class, and write a paper about it. This may be quite challenging, but even partial results would make a fine project.
• If you wish to do something that does not fit the above options, just talk to the instructor.

Here are some ideas for possible project topics:

• Chinese Reminder Codes: using lattices to decode error correcting codes based on CRT.
  • Guruswami, Sahai, Sudan, Soft-decision Decoding of Chinese Remainder Codes, FOCS 2000
  • Boneh, Finding Smooth Integers in Short Intervals Using CRT Decoding, JCSS 64:768-784, 2002. (Prelim. STOC 2000)
  • Goldreich, Ron, Sudan, Chinese Remaindering with Errors, IEEE Trans. on IT 46(4):1330-1338, 2000. (Prelim. STOC 1999)
• Improving the LLL approximation factor
  • Rankin's Constant and Blockwise Lattice Reduction(CRYPTO 2006)
  • Blockwise Lattice Basis Reduction Revisited (CLC 2006)
  • The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice (STOC 2003)
  • Schnorr, "A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms", TCS 53(2-3):201-224, 1987
• Speeding up LLL reduction:
  • Floating-Point LLL Revisited (EUROCRYPT '05)
  • Fast LLL-Type Lattice Reduction(Inform. and Comput., 2006)
• HNF algorithms
  • Micciancio, Warinschi, A linear space algorithm for computing the Hermite normal form , ISSAC 2001
  • Storjohan, Computing Hermite and Smith normal forms of triangular integer matrices, Linear Algebra and its Applications, 282(1-3):25-45, 1998
  • Storjohan, Labahn, Asymptotically fast computation of Hermite normal forms of integer matrices, ISSAC 1996.
• Cryptanalysis of DSS under various attack scenarios:
  • Bellare, Goldwasser, Micciancio, "Pseudo-random" generators within cryptographic applications: the DSS case, Crypto 1997
  • Nguyen, Shparlinski, The insecurity of the Digital Signature Algorithms with partially known nonces, J. Cryptology 15(3):151-176, 2001

You can find many other links to papers related to lattice algorithms and applications at the following sites.

• Damien Stehle' links on Algorithmics and Lattices
• Helger Lipmaa's links on Lattice Cryptography and Reduction

If you want to learn more about lattice cryptanalysis, the following survey papers cover a wide range of applications and attacks:

• The Two Faces of Lattices in Cryptology, CaLC 2001
• Lattice Reduction: a Toolbox for the Cryptanalyst, J.Crypto 11(3), 1998

Below is a list of papers describing lattice attacks that appeared in conferences like Crypto, Eurocrypt, Asiacrypt, PKC, SAC, etc. The papers are listed in reverse chronological order, so some of the papers at the bottom of the list contain among the simplest lattice based attacks..

• The Insecurity of Esign in Practical Implementation
• Analysis of the Insecurity of ECMQV with Partially Known Nonces
• Attacking Unbalanced RSA-CRT Using SPA
• Key Recovery Attacks on NTRU without Ciphertext Validation Routine
• New Partial Key Exposure Attacks on RSA
• The Impact of Decryption Failures on the Security of NTRU Encryption
• Hypercubic Lattice Reduction and Analysis of GGH and NTRU Signatures
• On the Security of RDSA
• Enhancing Simple Power-Analysis Attacks on Elliptic Curve Cryptosystems
• Cryptanalysis of Unbalanced RSA with Small CRT-Exponent
• Cryptanalysis of the Revised NTRU Signature Scheme
• Lattice Attacks on RSA-Encrypted IP and TCP
• On the Insecurity of a Server-Aided RSA Protocol
• Cryptanalysis of the NTRU Signature Scheme (NSS) from Eurocrypt 2001
• The Two Faces of Lattices in Cryptology
• Low Secret Exponent RSA Revisited
• Approximate Integer Common Divisors
• The Insecurity of Nyberg-Rueppel and Other DSA-Like Signature Schemes with Partially Known Nonces
• Information Leakage Attacks against Smart Card Implementations of the Elliptic Curve Digital Signature Algorith
• Key Recovery and Message Attacks on NTRU-Composite
• A Chosen-Ciphertext Attack against NTRU
• Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto'97
• Factoring N = p^r q for Large r
• Cryptanalysis of RSA with Private Key d Less than N^0.292
• The Effectiveness of Lattice Attacks Against Low-Exponent RSA
• Cryptanalysis of a Fast Public Key Cryptosystem Presented at SAC '97
• The Beguin-Quisquater Server-Aided RSA Protocol from Crypto '95 is Not Secure
• An Attack on RSA Given a Small Fraction of the Private Key Bits
• Cryptanalysis of the Ajtai-Dwork Cryptosystem
• Cryptanalysis of the Chor-Rivest Cryptosystem
• Lattices and Cryptography: An Overview
• Speeding up Discrete Log and Factoring Based Schemes via Precomputations
• Merkle-Hellman Revisited: A Cryptanalysis of the Qu-Vanstone Cryptosystem Based on Group Factorizations
• A Multiplicative Attack Using LLL Algorithm on RSA Signatures with Redundancy
• Low-Exponent RSA with Related Messages
• The Cryptanalysis of a New Public-Key Cryptosystem Based on Modular Knapsacks
• Cryptanalysis of a Public-Key Cryptosystem Based on Approximations by Rational Numbers
• Cryptanalysis of Short RSA Secret Exponents
• How to Break Okamoto's Cryptosystem by Reducing Lattice Bases

Here are a few more papers about lattice algorithms and applications:

• A Lattice Based General Blind Watermark Scheme
• The Hardness of Hensel Lifting: The Case of RSA and Discrete Logarithm
• An Advantage of Low-Exponent RSA with Modulus Primes Sharing Least Significant Bits
• A Faster Lattice Reduction Method Using Quantum Search
• Computing the M = U U t Integer Matrix Decomposition