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.