Algebraic (Trapdoor) One-Way Functions and Their Applications

摘要: In this paper we introduce the notion of Algebraic (Trapdoor) One Way Functions, which, roughly speaking, captures and formalizes many properties number-theoretic one-way functions. Informally, a (trapdoor) one way function F: X#8594;Y is said to be algebraic if X Y are (finite) abelian cyclic groups, homomorphic i.e. F(x)·F(y)=F(x ·y), ring-homomorphic, meaning that it possible compute linear operations 'in exponent' over some ring (which may different from ℤp where p order underlying group X) without knowing bases. Moreover, OWFs must flexibly in sense given y=F(x), infeasible (x′, d) such F(x′)=yd (for d≠0). Interestingly, functions can constructed variety standard number theoretic assumptions, as RSA, Factoring CDH bilinear groups. As second contribution paper, show several applications turn out useful. These include publicly verifiable secure outsourcing polynomials, linearly signatures batch execution Sigma protocols.