Paper 2012/434
Algebraic (Trapdoor) One Way Functions and their Applications
Dario Catalano, Dario Fiore, Rosario Gennaro, and Konstantinos Vamvourellis
Abstract
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 numbertheoretic oneway 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 ringhomomorphic}, 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 oneway} 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 LinearlyHomomorphic Signatures}: We give a direct construction of FDHlike 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 (BonehFreeman, 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.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. This is the full version of the paper that appears in the proceedings of TCC 2013
 Keywords
 oneway functionsverifiable computationlinearlyhomomorphic signaturessigma protocols
 Contact author(s)
 fiore @ cs nyu edu
 History
 20130215: last of 2 revisions
 20120805: received
 See all versions
 Short URL
 https://ia.cr/2012/434
 License

CC BY
BibTeX
@misc{cryptoeprint:2012/434, 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{https://eprint.iacr.org/2012/434}}, url = {https://eprint.iacr.org/2012/434} }