Oblivious pseudorandom function: Difference between revisions

Revision as of 15:49, 8 September 2024

Revision as of 03:46, 30 November 2024

Line 18:

== History ==

While conventional [[Pseudorandom function family|Pseudorandom Functions]] computed by a single party were first formalized in 1986,<ref>{{cite journal |last1=Goldreich |first1=Oded |last2=Goldwasser |first2=Shafi |last3=Micali |first3=Silvio |title=How to construct random functions |journal=Journal of the ACM |date=1986 |volume=33 |issue=4 |pages=792–807 |doi=10.1145/6490.6503 |url=https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Pseudo%20Randomness/How%20To%20Construct%20Random%20Functions.pdf}}</ref> it was not until 1997 that the [[Naor–Reingold pseudorandom function|first two-party Oblivious Pseudorandom Function]] was described in the literature,<ref>{{cite journal |last1=Naor |first1=Moni |last2=Reingold |first2=Omer |title=Number-theoretic constructions of efficient pseudo-random functions |journal=Journal of the ACM |date=2004 |volume=51 |issue=2 |pages=231–262 |doi=10.1145/972639.972643 |url=https://dl.acm.org/doi/10.1145/972639.972643}}</ref> but the term "Oblivious Pseudorandom Function" was not coined until 2005 by some of the same authors.<ref>{{cite journalbook |last1=Freedman |first1=Michael |last2=Ishai |first2=Yuval |last3=Pinkas |first3=Benny |last4=Reingold |first4=Omer |titlechapter=Keyword Search and Oblivious Pseudorandom Functions |journaltitle=Theory of Cryptography Conference |series=Lecture Notes in Computer Science |date=2005 |volume=TCC 2005 |pages=303–324 |doi=10.1007/978-3-540-30576-7_17 |isbn=978-3-540-24573-5 |chapter-url=https://link.springer.com/chapter/10.1007/978-3-540-30576-7_17}}</ref>

== Applications ==

Line 221:

constructions rely on discrete-log- or factoring-type hardness assumptions. These assumptions are known to fall with the rise of quantum computers."<ref name="oprf"/></blockquote>

Two possible exceptions are [[Lattice-based cryptography|lattice-based]] OPRFs<ref>{{cite journal |last1=Albrecht |first1=Martin |last2=Davidson |first2=Alex |last3=Deo |first3=Amit |last4=Smart |first4=Nigel |title=Round-optimal Verifiable Oblivious Pseudorandom Functions From Ideal Lattices |journal=Cryptology ePrint Archive |date=2019 |volume=Paper 2019/1271 |url=https://eprint.iacr.org/2019/1271}}</ref> and [[Supersingular isogeny key exchange|isogeny-based]] OPRFs,<ref>{{cite journalbook |last1=Boneh |first1=Dan |last2=Kogan |first2=Dmitry |last3=Woo |first3=Katharine |titlechapter=Oblivious Pseudorandom Functions from Isogenies |series=Lecture Notes in Computer Science |journaltitle=Advances in Cryptology |date=2020 |volume=ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security |pages=520–550 |doi=10.1007/978-3-030-64834-3_18 |isbn=978-3-030-64833-6 |s2cid=228085090}}</ref> but more research is required to improve their efficiency and establish their security. Recent attacks on isogenies raise doubts on the security of the algorithm.<ref>{{cite book |last1=Castryck |first1=Wouter |last2=Decru |first2=Thomas |chapter=An Efficient Key Recovery Attack on SIDH |series=Lecture Notes in Computer Science |title=Advances in Cryptology |date=2023 |volume=EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques |pages=423–447 |doi=10.1007/978-3-031-30589-4_15 |isbn=978-3-031-30588-7 |s2cid=258240788 |chapter-url=https://lirias.kuleuven.be/handle/20.500.12942/722100}}</ref>

A more-secure, but less-efficient approach to realize a post-quantum secure OPRF is to use a [[secure two-party computation]] protocol to compute a PRF using a [[symmetric cryptography|symmetric key]] construction, such as [[Advanced encryption standard|AES]] or [[HMAC]].