### Number-theoretic constructions of efficient pseudo-random functionsNumber-theoretic constructions of efficient pseudo-random functions

Access Restriction
Subscribed

 Author Naor, Moni ♦ Reingold, Omer Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2004 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Pseudo-random functions ♦ Constant-depth threshold circuits ♦ Decision Diffie--Hellman ♦ Factoring ♦ Learning theory ♦ Natural proofs Abstract We describe efficient constructions for various cryptographic primitives in private-key as well as public-key cryptography. Our main results are two new constructions of pseudo-random functions. We prove the pseudo-randomness of one construction under the assumption that $\textit{factoring}$ (Blum integers) is hard while the other construction is pseudo-random if the decisional version of the Diffie--Hellman assumption holds. Computing the value of our functions at any given point involves two subset products. This is much more efficient than previous proposals. Furthermore, these functions have the advantage of being in $TC^{0}$ (the class of functions computable by constant depth circuits consisting of a polynomial number of threshold gates). This fact has several interesting applications. The simple algebraic structure of the functions implies additional features such as a zero-knowledge proof for statements of the form $"\textit{y}$ = $f_{s}(x)"$ and $"\textit{y}$ &neq; $f_{s}(x)"$ given a commitment to a key $\textit{s}$ of a pseudo-random function $f_{s}.$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2004-03-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 51 Issue Number 2 Page Count 32 Starting Page 231 Ending Page 262

#### Open content in new tab

Source: ACM Digital Library