[NR97] Number-Theoretic Constructions of Efficient Pseudo-Random Functions

Authors: Moni Naor, Omer Reingold | Venue: FOCS 1997 | Source

Abstract

We describe efficient constructions for pseudorandom functions and pseudorandom permutations based on the hardness of the decisional Diffie-Hellman (DDH) problem. Given a group $\mathbb{G}$ of prime order $p$ with generator $g$ in which DDH is hard, and a secret key $(a_1,\dots ,a_n)\in {\mathbb{Z}}_p^n$, the Naor-Reingold PRF maps $x=(x_1,\dots ,x_n)\in \{0,1{\}}^n$ to $g^{a_0\cdot a_1^{x_1}\cdots a_n^{x_n}}$. The proof of security relies on the DDH assumption and a hybrid argument over the input bits. The resulting PRF can be evaluated very efficiently: a single group exponentiation suffices for each input, making it considerably more efficient than the tree-based GGM construction when the domain is fixed.

BibTeX

Copy

@Inproceedings{FOCS:NaoRei97,
  author = {Moni Naor and Omer Reingold},
  title = {Number-theoretic Constructions of Efficient Pseudo-random Functions},
  pages = {458--467},
  booktitle = {38th Annual Symposium on Foundations of Computer Science},
  address = {Miami Beach, Florida},
  month = {oct~19--22},
  publisher = {{IEEE} Computer Society Press},
  year = {1997},
  doi = {10.1109/SFCS.1997.646134},
}