Paper 2012/434

Algebraic (Trapdoor) One Way Functions and their Applications

Dario Catalano, Dario Fiore, Rosario Gennaro, and Konstantinos Vamvourellis


In this paper we introduce the notion of {\em 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 \to Y$ is said to be algebraic if $X$ and $Y$ are (finite) abelian cyclic groups, the function is {\em homomorphic} i.e. $F(x)\cdot F(y) = F(x \cdot y)$, and is {\em ring-homomorphic}, meaning that it is possible to compute linear operations ``in the exponent'' over some ring (which may be different from $\ZZ_p$ where $p$ is the order of the underlying group $X$) without knowing the bases. Moreover, algebraic OWFs must be {\em 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 \neq 0$). Interestingly, algebraic one way functions can be constructed from a variety of {\em 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: - {\em 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 does not require bilinear maps to obtain public verifiability. - {\em Linearly-Homomorphic Signatures}: We give a direct construction of FDH-like linearly homomorphic signatures from algebraic (trapdoor) one way permutations. Our constructions support messages and homomorphic operations over {\em arbitrary} rings and in particular even small fields such as $\FF_2$. While it was already known how to realize linearly homomorphic signatures over small fields (Boneh-Freeman, Eurocrypt 2011), from lattices in the random oracle model, ours are the first schemes achieving this in a very efficient way from Factoring/RSA. - {\em Batch execution of Sigma protocols}: We construct a simple and efficient Sigma protocol for any algebraic OWP and show a ``batch'' version of it, i.e. a protocol where many statements can be proven at a cost (slightly superior) of the cost of a single execution of the original protocol. Given our RSA/Factoring instantiations of algebraic OWP, this yields, to the best of our knowledge, the first batch verifiable Sigma protocol for groups of unknown order.

Note: This paper subsumes the work "Improved Publicly Verifiable Delegation of Large Polynomials and Matrix Computations" by Dario Fiore and Rosario Gennaro, appeared in an earlier version of this eprint post.

Available format(s)
Publication info
Published elsewhere. This is the full version of the paper that appears in the proceedings of TCC 2013
one-way functionsverifiable computationlinearly-homomorphic signaturessigma protocols
Contact author(s)
fiore @ cs nyu edu
2013-02-15: last of 2 revisions
2012-08-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dario Catalano and Dario Fiore and Rosario Gennaro and Konstantinos Vamvourellis},
      title = {Algebraic (Trapdoor) One Way Functions and their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2012/434},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.