Algebraic (trapdoor) one-way functions: Constructions and applications

作者：Catalano Dario; Fiore Dario^*; Gennaro Rosario; Vamvourellis Konstantinos

来源：Theoretical Computer Science, 2015, 592: 143-165.

DOI：10.1016/j.tcs.2015.05.029

• One-way functions
• Homomorphic signatures
• Verifiable computation
• Sigma protocols

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 ring-homomorphic, meaning that it is possible to compute linear operations "in the exponent" over some ring (which may be different from Z(p) 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 not equal 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 does not require bilinear maps to obtain public verifiability.
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 arbitrary rings and in particular even small fields such as F-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.
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.

• 出版日期2015-8-9