Algebraic (Trapdoor) One Way Functions and their Applications
Dario Catalano, Dario Fiore, Rosario Gennaro, Konstantinos Vamvourellis · 2012
Abstract. In this paper we introduce the notion of Algebraic (Trapdoor) One Way Functions, which, roughly speaking, captures and formalizes many of the properties of number-theoretic one-way functions. Informally, a (trapdoor) one way function F: X → Y is said to be algebraic if X and Y are (finite) abelian cyclic groups, the function is homomorphic i.e. F (x) · F (y) = F (x · y), and is ringhomomorphic, meaning that it is possible to compute linear operations “in the exponent ” over some ring (which may be different from Zp where p is the order of the underlying group X) without knowing the bases. Moreover, algebraic OWFs must be flexibly one-way in the sense that given y = F (x), it must be infeasible to compute (x ′ , d) such that F (x ′ ) = y d (for d = 0). Interestingly, algebraic one way functions can be constructed from a variety of standard number theoretic assumptions, such as RSA, Factoring and CDH over bilinear groups. As a second contribution of this paper, we show several applications where algebraic (trapdoor) OWFs turn out to be useful. In particular: – Publicly Verifiable Secure Outsourcing of Polynomials: We present efficient solutions which work for rings of arbitrary size and characteristic. When instantiating our protocol with the RSA/Factoring based algebraic OWFs we obtain the first solution which supports small field size, is efficient and