TC: Small: Lossy Trapdoor Functions - Applications, Realizations and Beyond

基础密码学的一个中心目标是找到一个原语，它实现了所有有趣的密码学应用，但其安全性基于一个简单的假设-理想情况下是一个弱的一般假设。最近，随着Lossy Trapdoor Functions的引入，在这个方向上迈出了重要的一步。有耗陷门函数（TDF）族允许用户生成可公开计算的函数f和对应的陷门t，使得用户可以在给定f（x）的情况下恢复x。另外，用户可以生成一个函数g，使得g失去关于输入x的信息;此外，没有计算上有界的对手可以区分它是否被给予了一个单射或有损函数的描述。有损陷门函数产生了一系列密码学应用，包括：单射陷门函数，选择密文安全加密，抗碰撞哈希函数和不经意传输（OT）。此外，人们可以从几个标准的数论假设实现有耗TDFs：决定性Diffie-Hellman，格中的最短向量（SVP）问题和复合剩余问题。总之，这解决了两个长期存在的开放问题：实现基于非因式分解的陷门函数，并从基于格的假设建立选择密文安全加密系统。这项工作将奋进实现从简单的一般假设建立所有密码学的最终目标取得重大进展。将遵循以下方向。首先，这项工作的目的是从较弱的数论假设和一般假设中创建新的结构。其次，该项目将在基于身份的密码系统中建立陷阱门。 构建基于身份的陷门将使基于身份的上下文中的“确定性排除”等应用成为可能。第三，建立新的非交互式证据系统。该项目将研究与通用哈希证明系统的关系，并创建新的非交互式零知识证明系统。该项目将有助于我们对密码学的基础理解。研究结果将通过会议、期刊和特邀演讲进行传播。此外，资金将用于支持研究生，并在UT奥斯汀建立一个密码学项目。

A central goal in foundational cryptography is to find a primitive that realizes all interesting cryptographic applications, and yet has its security based on a simple assumption --- ideally a weak general assumption. Recently, a significant step in this direction was made with the introduction of Lossy Trapdoor Functions. A family of Lossy Trapdoor Functions (TDF) lets a user generate a publicly computable function, f, and corresponding trapdoor, t, such the user can recover x given f(x). Alternatively, the user can generate a function g such that g looses information about the input x; moreover, no computationally bounded adversary can distinguish whether it is given the description of an injective or lossy function.Lossy Trapdoor Functions give rise to a host of cryptographic applications including: injective trapdoor functions, chosen-ciphertext secure encryption, collision-resistant hash functions, and oblivious transfer (OT). Furthermore, one can realize Lossy TDFs from several standard number theoretic assumptions: Decisional Diffie-Hellman, the Shortest Vector (SVP) problem in lattices, and the Composite Residuosity problem. Taken all together this solved two longstanding open problems: realizing non-factoring based trapdoor functions; and building chosen ciphertext secure encryption systems from lattice-based assumptions.This work will endeavor to make significant progress towards realizing the ultimate goal of building all of cryptography from simple general assumptions. The following directions will be pursued. First, the work will aim to create new constructions from both weaker number theoretic assumptions and from general assumptions. Second, the project will build trapdoors into Identity-Based Cryptosystems. Constructing identity-based trapdoors will enable applications such as ``deterministic encryption'' in the Identity-Based context. Third, it will build new Non-Interactive Proof Systems. The project will study the relationship to Universal Hash Proof Systems and create new Non-Interactive Zero Knowledge Proof Systems.This project will contribute to our foundational understanding of cryptography. Results will be disseminated through conferences, journals, and invited talks. In addition, funding will be used to support graduate students and build a cryptography program at UT Austin.