Number-theoretic Constructions of Efficient Pseudorandom Functions
(Citations: 250)
We describe efficient constructions for various cryptographic primitives (both in privatekeyand in public-key cryptography). We show these constructions to be at least as secure asthe decisional version of the Diffie-Hellman assumption or as the assumption that factoringis hard. Our major result is a new construction of pseudo-random functions such thatcomputing their value at any given point involves two multiple products. This is muchmore efficient than previous proposals. Furthermore,...