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

点击翻译按钮获取中文摘要

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.