Oblivious pseudorandom function: Difference between revisions

Revision as of 09:41, 22 April 2025

Revision as of 15:06, 25 May 2025

Line 16:

== 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|url-access=subscription }}</ref> but the term "oblivious pseudorandom function" was not coined until 2005 by some of the same authors.<ref>{{cite book |last1=Freedman |first1=Michael |last2=Ishai |first2=Yuval |last3=Pinkas |first3=Benny |last4=Reingold |first4=Omer |chapter=Keyword Search and Oblivious Pseudorandom Functions |title=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 79:

For example, private set intersection could be used by two users of a social network to determine which friends they have in common, without revealing the identities of friends they do not have in common. To do this, they could share the outputs of an OPRF applied to the friend's identity (e.g., the friend's phone number or e-mail address).

The output of the OPRF cannot be inverted to determine the identity of the user, and since the OPRF may be [[Rate limiting|rate-limited]], it will prevent a brute-force attack (e.g., iterating over all possible phone numbers).<ref>{{cite journal |last1=Chase |first1=Melissa |last2=Miao |first2=Peihan |title=Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF |journal=IACR in CRYPTO 2020 |date=Aug 2020 |volume=Advances in Cryptology – CRYPTO 2020: 40th Annual International Cryptology Conference |issue=Proceedings Part III |pages=34–63 |doi=10.1007/978-3-030-56877-1_2 |s2cid=220126483 |url=https://dl.acm.org/doi/10.1007/978-3-030-56877-1_2|url-access=subscription }}</ref>

== Implementations ==

Line 169:

Fortunately, most OPRFs support verifiability. For example, when using [[RSA (cryptosystem)|RSA]] blind signatures as the underlying construction, the client can, with the public key, verify the correctness of the resulting [[digital signature]].

When using OPRFs based on [[elliptic curve]] or [[Diffie–Hellman]], knowing the public key ''y = g^x'' it is possible to use a second request to the OPRF server to create a [[zero-knowledge proof]] of correctness for the previous result.<ref>{{cite book |last1=Jarecki |first1=Stanislaw |last2=Kiayias |first2=Aggelos |last3=Krawczyk |first3=Hugo |chapter=Round-Optimal Password-Protected Secret Sharing and T-PAKE in the Password-Only Model |series=Lecture Notes in Computer Science |title=Advances in Cryptology |date=2014 |volume=ASIACRYPT 2014 – 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7–11, 2014, Proceedings, Part II |pages=233–253 |doi=10.1007/978-3-662-45608-8_13|isbn=978-3-662-45607-1 }}</ref><ref name="voprf">{{cite journal |last1=Davidson |first1=Alex |last2=Faz-Hernandez |first2=Armando |last3=Sullivan |first3=Nick |last4=Wood |first4=Christopher A. |title=Oblivious Pseudorandom Functions (OPRFs) Using Prime-Order Groups |journal=Internet Engineering Task Force |date=2023 |volume=RFC 9497 |doi=10.17487/RFC9497 |s2cid=149835146 |url=https://www.rfc-editor.org/info/rfc9497|url-access=subscription }}</ref>

=== Partially oblivious PRF ===