Project

Back to overview

Lattice algorithms: development of algorithms using the representation technique

English title Lattice algorithms: development of algorithms using the representation technique
Applicant Lenstra Arjen K.
Number 153113
Funding scheme Project funding
Research institution Laboratoire de cryptologie algorithmique EPFL - IC - IIF - LACAL
Institution of higher education EPF Lausanne - EPFL
Main discipline Mathematics
Start/End 01.05.2014 - 30.04.2016
Approved amount 188'600.00
Show all

All Disciplines (2)

Discipline
Mathematics
Information Technology

Keywords (8)

lattice; IT-security; cryptography; privacy; algorithms; decomposition approach; mathematical problem; internet

Lay Summary (German)

Lead
Das digitale Zeitalter stellt neue Herausforderungen bezüglich Sicherheit und Privatsphäre an die Technologie.Beim Online-Banking oder bargeldlosen Zahlen werden im Hintergrund kryptographische Verfahren benutzt, die auf gewissen mathematischen Problemen beruhen (z.B. Faktorisierung einer grossen Zahl oder das diskrete Logarithmus Problem). Ein breites Forschungsfeld der Kryptographie ist die Entwicklung von Methoden zum Lösen der zugrundeliegenden Probleme, da damit Schwachstellen aufgedeckt werden können und die Sicherheit eingeschätzt werden kann. In den 80er Jahren wurden Methoden entwickelt, die auf Gittern im euklidischen Raum beruhen. Zusätzlich bieten Gitter selber schwierig zu lösende mathematische Probleme, so dass seitdem zusätzlich vielversprechende neue Kryptosysteme entwickelt wurden, deren Sicherheit auf Gitterproblemen basiert.
Lay summary

Inhalt und Ziel des Forschungsprojekts

In unserem Projekt erforschen wir verschiedene Methoden, um Gitterprobleme effizient zu lösen und damit die Sicherheit von Kryptosystemen besser einzuschätzen. Heutige Algorithmen basieren auf Konzepten von 1994 und 2001, die in der Folgezeit verbessert und optimiert wurden. Wir verfolgen einen komplett neuartigen Ansatz auf Basis von kürzlich veröffentlichen Ergebnissen aus dem Bereich der Kodierungstheorie. Diese Ergebnisse können in veränderter Form ebenfalls auf Gitter angewendet werden. Sie stellen dadurch eine neue Methode dar, die unabhängig von bisher verwendeten algorithmischen Ansätzen ist.

Wissenschaftlicher und gesellschaftlicher Kontext des Forschungsprojekts

Unsere Arbeit liegt im Bereich der kryptographischen Grundlagenforschung, die Wissenschaftsbereiche der Informatik und Mathematik miteinander verbindet. Die Ergebnisse der Forschung tragen dazu bei, die Sicherheit von digitalen Diensten zu gewährleisten und die Privatsphäre der Nutzer zu schützen.

 

Direct link to Lay Summary Last update: 28.03.2014

Responsible applicant and co-applicants

Employees

Publications

Publication
Efficient (ideal) lattice sieving using cross-polytope LSH
Becker Anja, van Laarhoven Thijs (2016), Efficient (ideal) lattice sieving using cross-polytope LSH, in International Conference on Cryptology, AFRICACRYPT 2016, FES, Marocco.
New directions in nearest neighbor searching with applications to lattice sieving
Becker Anja, Ducas Léo, Gama Nicolas, Laarhoven Thijs (2016), New directions in nearest neighbor searching with applications to lattice sieving, in Proceedings of 27th ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, Virginia, USAACM, proceedings SODA 2016.
Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search
Becker Anja, Gama Nicolas, Joux Antoine (2016), Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search, IACR, eprint archive.

Collaboration

Group / person Country
Types of collaboration
l’université de Versailles-Saint-Quentin-en-Yvelines France (Europe)
- in-depth/constructive exchanges on approaches, methods or results
- Publication
ENS Paris France (Europe)
- in-depth/constructive exchanges on approaches, methods or results

Associated projects

Number Title Start Funding scheme
144981 Scientific computing using commodity hardware 01.10.2014 R'EQUIP
126368 Theoretical and practical aspects of parallelized integer lattice reduction and related problems 01.03.2010 Project funding
119776 Computational cryptanalysis of asymmetric cryptosystems: Theory and Practice 01.06.2008 Project funding

Abstract

In the last years, Euclidean lattices, used since the 1980s as a cryptanalytic tool, havebeen (re)discovered as a powerful tool to build cryptographic schemes. Cryptographybased on lattices has several attractive features:1. Security: the best algorithms to solve the underlying problems require exponentialtime in the dimension, the main security parameter, even against quantum adversaries.This must be compared with factoring based cryptosystems (e.g. RSA)which can be broken in subexponential time and even in polynomial time usingquantum computers. Moreover, lattice cryptography is supported by strongworst-case/average-case reductions, which indicate that the random instances usedin cryptography do not suffer from unforeseen "structural weakness". Resistanceagainst quantum computer attacks remains unproven, however.2. Efficiency: lattice operations are mainly simple, fast and parallelizable (typicaloperations are the selection of uniformly random integer matrices, and modularevaluation of simple linear function). By contrast, the operations used in classicalcryptography are much more complex (generation of large primes, exponentiation)and are more difficult to parallelize.3. Versatility: the simplicity of trapdoors leads to a large number of theoretical applications,from identity-based encryption to fully homomorphic encryption (FHE),for which a potentially very useful feature is to distribute a computation on thecloud without revealing the data on which the computation is performed.Algorithms for the lattice problems are furthermore of interest as they can be appliedto other problems such as integer programming, factoring polynomials with rationalcoefficients, integer relation finding, as well as problems in communication theory andthey can be used to break RSA and DSA in special cases. Furthermore, the latticereduction algorithm LLL was successfully used to break cryptosystems based on the lowdensity knapsack problem.The project aims at developing a promising new technique to solve hard lattice problemson which the security of cryptographic schemes relies. The best up-to-date algorithmsdate back to concepts developed in 1994 and 2001. In the following years,researchers have optimized the algorithms and tightened the parameters. The projectaims at developing new algorithmic techniques that will lead to a better understandingof lattice problems and weak instances. Our last years work has shown promising firstresults which show that one can adapt the representation technique to the area of latticecryptography. The technique was successfully introduced and applied for two othermathematical problems used in cryptography. During the project we would like to investigatethis idea further, i.e., to extend the technique to lattice problems, and to verify ifit leads to interesting speed-ups.
-