Algebraic structure lies at the heart of much of Cryptomania as we know it. An interesting question is the following: instead of building (Cryptomania) primitives from concrete assumptions, can we build them from simple Minicrypt primitives endowed with additional algebraic structure? In this work, we affirmatively answer this question by adding algebraic structure to the following Minicrypt primitives: one-way functions, weak unpredictable functions and weak pseudorandom functions. The algebraic structure that we consider is group homomorphism over the input/output spaces of these primitives. We show that these structured primitives can be used to construct several Cryptomania primitives in a generic manner.
Our results make it substantially easier to show the feasibility of building many cryptosystems from novel assumptions in the future. In particular, we show how to realize any CDH/DDH-based protocol with certain properties in a generic manner from input-homomorphic weak unpredictable/pseudorandom functions, and hence, from any concrete assumption that implies the existence of these structured primitives.
Our results also allow us to categorize many cryptographic protocols based on which structured Minicrypt primitive implies them. In particular, endowing Minicrypt primitives with increasingly richer algebraic structure allows us to gradually build a wider class of cryptoprimitives. This seemingly provides a hierarchical classification of many Cryptomania primitives based on the "amount" of structure inherently necessary for realizing them.
Note the changed time.
Sikhar Patranabis is a postdoc at ETH Zurich, in the Applied Cryptography group headed by Prof. Kenny Paterson since November 2019. Prior to that, he received his PhD from IIT Kharagpur, India. His research interests span all aspects of cryptography, with special focus on cryptographic complexity, database encryption, and secure implementations of cryptographic algorithms.