zbMATH — the first resource for mathematics

Number-theoretic constructions of efficient pseudo-random functions. (English) Zbl 1248.94086
Summary: 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 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 \(\mathrm{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 “\(y = f_s(x)\)” and “\(y \neq f_s(x)\)” given a commitment to a key \(s\) of a pseudo-random function \(f_s\).
Reviewer: Reviewer (Berlin)

94A60 Cryptography
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI