Fourier Techniques in Cryptography and Coding

密码学和编码中的傅立叶技术Daniele Micciancio(UCSD)2006年8月31日摘要数字计算机和通信网络经常用于越来越多的安全敏感应用程序，如在线购物、在线银行等。加密原语(即计算机执行的保护其数据的基本操作)在保护数字世界的安全方面发挥着基础作用，因此我们对其安全性的信心至关重要。遗憾的是，为了提高效率(即由计算机快速执行)，实际中使用的许多密码原语没有得到安全性的数学证明的支持。这项研究调查了密码原语的设计和分析，这些原语在严格的数学意义上既非常有效，又可证明是安全的。该项目建立在数学技术和问题(主要来自傅立叶分析和点格领域)的基础上，这些技术和问题在更广泛的角度上是有趣的，而不是安全，并可能应用于其他数学和工程领域。在实际密码设计的现状和理论密码学之间存在着巨大而令人不安的差距。自组织设计方法提供密码原语，其效率是理论构造所无法比拟的，但代价是失去所有安全保证。这项研究通过研究(散列函数和其他密码原语)既有效又可证明安全的构造来解决这一差距。研究人员主要从点格、编码理论和代数数论等领域考虑计算问题。考虑到具有特殊结构的问题(例如，循环格子)和傅立叶技术(其开发是该项目的组成部分)，作为算法设计和安全分析工具，可以获得效率。

Fourier techniques in cryptography and codingDaniele Micciancio (UCSD)August 31, 2006AbstractDigital 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.