2010 · 69 citations · 11 references
ComputingComputer EngineeringComputer ScienceComputer SecurityCryptographyParallel ComputingCryptographic ComplexityInformation-theoretic CryptographyInformation-theoretic SecurityRandomized ComputationAlgebraic CryptanalysisComputational SecurityComputational Security ProofsPseudorandom FunctionsSecurity ProofsVerifiable ComputationVerifiable Random Functions
We construct an algebraic pseudorandom function (PRF) that is more efficient than the classic Naor-Reingold algebraic PRF. Our PRF is the result of adapting the cascade construction, which is the basis of HMAC, to the algebraic settings. To do so we define an augmented cascade and prove it secure when the underlying PRF satisfies a property called parallel security. We then use the augmented cascade to build new algebraic PRFs. The algebraic structure of our PRF leads to an efficient large-domain Verifiable Random Function (VRF) and a large-domain simulatable VRF.
11
How to construct random functions
Oded Goldreich, Shafi Goldwasser, Silvio Micali · Journal of the ACM · 1986 · 2.1K citations · Full text
Silvio Micali, M. O. Rabin, Salil Vadhan · 2003 · 687 citations · Full text
The Weil Pairing, and Its Efficient Calculation
Victor S. Miller · Journal of Cryptology · 2004 · 585 citations · Full text
Number-theoretic constructions of efficient pseudo-random functions
Moni Naor, Omer Reingold · 2002 · 353 citations