Collaborative Research: CT-ISG: Efficient Cryptography Based on Lattices

只有两个数论假设-分解的难度和计算离散对数的难度-基本上构成了当今广泛使用的所有公钥密码系统的基础。对于较低级别的原语，如哈希函数、随机数生成器和流密码，情况甚至更糟：现有的可证明安全的构造效率太低，无法与实用的替代方案如SHA-1或AES竞争，因此目前使用的原语没有严格的安全性理由。这项研究将研究基于格的新的计算假设。基于这些假设，研究人员将寻求设计出与现有部署的方案相比既可证明是安全的，又具有相当效率的密码原语。这项研究将探索使用格来构造基本的密码原语，包括哈希函数、伪随机生成器、共享密钥认证协议、公钥加密方案(包括那些防止选择密文攻击的方案)和数字签名。这项工作的教育部分将集中在培养研究生以及开发基于格子的密码学的入门水平调查。

Only two number-theoretic assumptions --- hardness of factoring and ofcomputing discrete logarithms --- underlie essentially all public-keycryptosystems in widespread use today. For lower-level primitivessuch as hash functions, random number generators, and stream ciphers,the situation is even worse: existing provably-secure constructionsare too inefficient to compete with practical alternatives such asSHA-1 or AES, and so the primitives in use today have no rigorousjustification for their security. This research will investigate new classes of computationalassumptions based on lattices. Based on these assumptions, theinvestigators will seek to design cryptographic primitives that areboth provably secure and comparably efficient to existing, deployedschemes. The research will explore the use of lattices to constructbasic cryptographic primitives, including hash functions, pseudorandomgenerators, shared-key authentication protocols, public-key encryptionschemes (including those secure against chosen-ciphertext attacks),and digital signatures. The educational component of this work willfocus on educating graduate students as well as developing introductory-level surveys of lattice-based cryptography.