Minicrypt primitives with algebraic structure and applications (Q5925579)

The algebraic structure lies at the heart of much of Cryptomania. An interesting question is that, instead of building (Cryptomania) primitives from concrete assumptions, is it possible to build them from simple Minicrypt primitives endowed with additional algebraic structure? In this work, the authors affirmatively answer this question by adding algebraic structure to the following Minicrypt primitives: 1. One-Way Function (OWF), 2. Weak Unpredictable Function (wUF), 3. Weak Pseudorandom Function (wPRF). The algebraic structure that they consider is a group homomorphism over the input/output spaces of these primitives. They also consider a ``bounded'' notion of homomorphism where the primitive only supports an a priori bounded number of homomorphic operations to capture lattice-based and other ``noisy'' assumptions. They show that these structured primitives can be used to construct many cryptographic protocols. In addition to that, they show how to realize any CDH/DDH-based protocol with certain properties in a generic manner using IHwUFs/IHwPRFs, and how to instantiate such a protocol from many concrete assumptions. They also consider primitives with substantially richer structures, namely Ring IHwPRFs and L-composable IHwPRFs. Their framework allows the categorization of many cryptographic protocols based on which structured Minicrypt primitive implies them. In addition, it potentially makes showing the existence of many cryptosystems from novel assumptions substantially easier in the future.