Project

Discipline

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

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

Number	Title	Start	Funding scheme

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.