**Algebraic (Trapdoor) One Way Functions and their Applications**

*Dario Catalano and Dario Fiore and 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 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.

**Category / Keywords: **one-way functions, verifiable computation, linearly-homomorphic signatures, sigma protocols

**Publication Info: **This is the full version of the paper that appears in the proceedings of TCC 2013

**Date: **received 31 Jul 2012, last revised 15 Feb 2013

**Contact author: **fiore at cs nyu edu

**Available format(s): **PDF | BibTeX Citation

**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.

**Version: **20130215:084531 (All versions of this report)

**Short URL: **ia.cr/2012/434

[ Cryptology ePrint archive ]