I was taught only GGM based PRF construction in class. It's very inefficient. I am just curious about various PRF constructions from standard assumptions. Please provide a few PRF constructions from various assumptions.

  • $\begingroup$ Well, one standard assumption is that the SHA-256 compression function is a PRF, from which we can conclude that HMAC-SHA256 is a PRF (and a reasonably efficient one at that), but maybe you meant to restrict the domain of ‘standard assumptions’? $\endgroup$ Apr 26 '19 at 18:44

The most common efficient PRFs from specific assumptions are:

The Naor-Reingold PRF, which is based on the decision Diffie-Hellman assumption (DDH), and

The BPR PRF, which is based on the learning with error assumption (LWE).

Perhaps slightly less well-known is the NRR PRF, which is based on the hardness of factoring.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.