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 ℤ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 ≠ 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. These include publicly verifiable secure outsourcing of polynomials, linearly homomorphic signatures and batch execution of Sigma protocols.

Algebraic (Trapdoor) One-Way Functions and Their Applications

CATALANO, Dario;
2013-01-01

Abstract

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 ℤ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 ≠ 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. These include publicly verifiable secure outsourcing of polynomials, linearly homomorphic signatures and batch execution of Sigma protocols.
2013
978-364236593-5
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/84084
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 50
  • ???jsp.display-item.citation.isi??? ND
social impact