Thumbnail
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

   Open content in new tab
Source: ACM Digital Library