Constructing and leveraging one-way function with encryption




Satyanarayana, Vusirikala

Journal Title

Journal ISSN

Volume Title



Over the last few years, there has been a surge of new cryptographic results, including Laconic oblivious transfer [30], (anonymous/ hierarchical) Identity-based Encryption [38, 42, 21], Trapdoor functions [46, 44, 39], Chosen-ciphertext security transformations [75, 74], Registration-Based Encryption [47, 48, 58], due to a beautiful framework recently introduced in the works of Cho et al. [30], and Döttling and Garg [38]. The primitive one-way function with encryption (OWFE) [46, 44] and its relatives (chameleon encryption, one-time signatures with encryption, hinting PRGs, trapdoor hash encryption, batch encryption) [38, 42, 21, 75, 41] have been a centerpiece in all these results. While there exist multiple realizations of OWFE (and its relatives) from a variety of assumptions such as CDH, Factoring, and LWE, all such constructions fall under the same general "missing block" framework [30, 38]. Although this framework has been instrumental in opening up a new pathway towards various cryptographic functionalities via the abstraction of OWFE (and its relatives), it has been accompanied by undesirable inefficiencies that might inhibit a much wider adoption in many practical scenarios. Motivated by the surging importance of the OWFE abstraction (and its relatives), a natural question to ask is whether the existing approaches can be diversified to obtain more constructions from different assumptions and develop newer frameworks. We believe answering this question will eventually lead to important and previously unexplored performance trade-offs in this novel cryptographic paradigm's overarching applications. In this thesis, we propose a new accumulation-style framework for building a new class of OWFE constructions with a special focus on achieving shorter ciphertext size. Such performance improvements parlay into shorter parameters in their corresponding applications. Our OWFE constructions outperform in terms of ciphertext size and encryption time, but this comes at the cost of larger evaluation and setup times. We also provide concrete performance measurements for our constructions and compare them with existing approaches. We believe highlighting such trade-offs will lead to wider adoption of these abstractions in a practical sense. In the second part of the thesis, we study an application of One-Way Function with Encryption. In Identity-based systems, there is a trusted authority that stores some secret information that gives him the ability to break the system's security if he turns malicious. To solve this problem, [47, 48] proposed the notion of Registration-Based Encryption (RBE) and construct it from One-Way Function with Encryption and Garbling schemes. Here, each user of the system generates a public and secret key on their own and gives only their public information to the trusted authority. The trusted authority simply accumulates the public information collected from all the users in the system and publishes and master public key. The trusted authority does not store any secret information. However, a malicious authority could still harm the system by generating the master public key arbitrarily. We propose the notion of verifiable RBE, where any user of the system can obtain short and easily verifiable proof that the authority is doing its job honestly. We build verifiable RBE from One-Way Function with Encryption and Garbling. Our construction is more efficient than the earlier known constructions.


LCSH Subject Headings