Fourier Techniques in Cryptography and Coding

University Of California-San Diego, La Jolla CA

Investigators

Abstract

Fourier techniques in cryptography and coding Daniele Micciancio (UCSD) August 31, 2006 Abstract Digital computers and communication networks are routinely used in a growing number of security sensitive applications, like on-line shopping, on-line banking, etc. Cryptographic primitives (i.e., the basic operations performed by computers to protect their data) play a fundamental role in securing the digital world, so our confidence in their security is paramount. Unfortunately, for the sake of efficiency (i.e., fast execution by computers), many cryptographic primitives used in practice are not supported by mathematical proofs of security. This research investigates the design and analysis of cryptographic primitives that are both very efficient and provably secure in a rigorous mathematical sense. The project builds on mathematical techniques and problems (mostly from the areas of Fourier analysis and point lattices) that are interesting in a broader perspective, beyond security, with potential applications to other areas of mathematics and engineering. There is a wide and discomfortable gap between the current state of the art in practical crypto- graphic design and theoretical cryptography. Ad-hoc design methods offer cryptographic primitives whose efficiency is unmatched by theoretical constructions, but at the price of loosing every security guarantee. This research addresses this gap by investigating constructions (of hash functions and other cryptographic primitives) that are both efficient and provably secure. The investigators consider computational problems mostly from the areas of point lattices, coding theory and algebraic number theory. Efficiency is achieved considering problems with special structure (e.g., cyclic lattices), and Fourier techniques (whose development is an integral part of the project) both as algorithmic design and security analysis tools.