Oblivious pseudorandom function: Difference between revisions

Revision as of 09:41, 22 April 2025

Latest revision as of 11:05, 11 July 2025

(2 intermediate revisions by 2 users not shown)

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 |title=Theory of Cryptography |chapter=Keyword Search and Oblivious Pseudorandom Functions |title=Theory of Cryptography Conference |series=Lecture Notes in Computer Science |date=2005 |volume=TCC 20053378 |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 32:

If the secret key used in the OPRF is high-entropy, then the output of the OPRF will also be high-entropy. This thereby solves the problem of the password being low-entropy, and therefore vulnerable to [[Password cracking|cracking]] via [[brute-force attack|brute force]].

This technique is called ''password hardening''.<ref>{{cite book |last1=Ford |first1=W. |last2=Kaliski |first2=B. S. |chapter=Server-assisted generation of a strong secret from a password |title=Proceedings IEEE 9th International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises (WET ICE 2000)|date=2000 |pages=176–180 |doi=10.1109/ENABL.2000.883724 |isbn=0-7695-0798-0 |s2cid=1977743 |chapter-url=https://ieeexplore.ieee.org/document/883724}}</ref> It fills a similar purpose as [[key stretching]], but password hardening adds significantly more entropy.

Further, since each attempt at guessing a password that is hardened in this way requires interaction with a server, it prevents an [[offline attack]], and thus enables the user or system administrator to be alerted to any password-cracking attempt.

Line 55:

</ref>

Recently, OPRFs have been applied to password-based key exchange to [[back up]] encrypted chat histories in [[WhatsApp]]<ref>{{cite book |last1=Davies |first1=Gareth T. |last2=Faller |first2=Sebastian |last3=Gellert |first3=Kai |last4=Handirk |first4=Tobias |last5=Hesse |first5=Julia |last6=Horváth |first6=Máté |last7=Jager |first7=Tibor |title=Advances in Cryptology – CRYPTO 2023 |chapter=Security Analysis of the WhatsApp End-to-End Encrypted Backup Protocol |series=Lecture Notes in Computer Science |title=Advances in Cryptology |date=2023 |volume=Advances in Cryptology – CRYPTO 2023: 43rd Annual International Cryptology Conference, CRYPTO 202314084 |pages=330–361 |doi=10.1007/978-3-031-38551-3_11 |isbn=978-3-031-38550-6 |chapter-url=https://dl.acm.org/doi/abs/10.1007/978-3-031-38551-3_11 |access-date=2 February 2024}}</ref> and [[Facebook Messenger]].<ref>{{cite journal |last1=Lewi |first1=Kevin |last2=Millican |first2=Jon |last3=Raghunathan |first3=Ananth |last4=Roy |first4=Arnab |title=Oblivious Revocable Functions and Encrypted Indexing |journal=Cryptology ePrint Archive |date=2022 |volume=Paper 2022/1044 |url=https://eprint.iacr.org/2022/1044}}</ref> A similar use case is planned to be added in [[Signal (messaging app)|Signal Messenger]].<ref>{{cite web |title=Technology Preview for secure value recovery |url=https://signal.org/blog/secure-value-recovery/ |website=Signal |publisher=Signal Foundation|date=19 December 2019}}</ref>

=== Untraceable CAPTCHAs ===

Line 65:

A [[password manager]] is software or a service that holds potentially many different account credentials on behalf of the user. Access to the password manager is thus highly sensitive: an attack could expose many credentials to the attacker.

The first proposal for a password manager based on OPRFs was SPHINX.<ref>{{cite book |last1=Shirvanian |first1=Maliheh |last2=Jarecki |first2=Stanislaw |last3=Krawczykz |first3=Hugo |last4=Saxena |first4=Nitesh |chapter=SPHINX: A Password Store that Perfectly Hides Passwords from Itself |title=2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS) |date=2017 |pages=1094–1104 |doi=10.1109/ICDCS.2017.64 |isbn=978-1-5386-1792-2 |s2cid=4781641 |chapter-url=https://ieeexplore.ieee.org/document/7980050}}</ref> It uses two devices (such as the user's laptop and phone) which collaborate to compute a password for a given account (as identified by the username and website's ___domain name). Because the user's two devices exchange values according to an OPRF protocol, intercepting the connection between them does not reveal anything about the password or the internal values each device used to compute it. Requiring two devices to compute any password also ensures that a compromise of either device does not allow the attacker to compute any of the passwords. A downside of this approach is that the user always needs access to both devices whenever they want to log in to any of their accounts.

An OPRF is used by the Password Monitor in [[Microsoft Edge]] to allow querying a server for whether a credential (which the user saved in the browser) is known to be compromised, without needing to reveal this credential to the server.<ref>{{Cite web|last1=Lauter|first1=Kristin|last2=Kannepalli|first2=Sreekanth|last3=Laine|first3=Kim|last4=Cruz Moreno|first4=Radames|date=January 1, 2021|title=Password Monitor: Safeguarding passwords in Microsoft Edge|url=https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/|access-date=January 1, 2021|website=Microsoft Research Blog}}</ref>

Line 75:

=== Private set intersection ===

[[Private set intersection]] is a cryptographic technique that enables two or more parties to compare their private sets to determine which entries they share in common, but without disclosing any entiresentries which they do not hold in common.

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 journalbook |last1=Chase |first1=Melissa |last2=Miao |first2=Peihan |title=Advances in Cryptology – CRYPTO 2020 |chapter=Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF |journalseries=IACRLecture Notes in CRYPTOComputer 2020Science |date=Aug 2020 |volume=Advances in Cryptology – CRYPTO 2020: 40th Annual International Cryptology Conference |issue=Proceedings Part III12172 |pages=34–63 |doi=10.1007/978-3-030-56877-1_2 |isbn=978-3-030-56876-4 |s2cid=220126483 |chapter-url=https://dl.acm.org/doi/10.1007/978-3-030-56877-1_2|chapter-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 |title=Advances in Cryptology – ASIACRYPT 2014 |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 II8874 |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 ===

Line 201:

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 book |last1=Boneh |first1=Dan |last2=Kogan |first2=Dmitry |last3=Woo |first3=Katharine |title=Advances in Cryptology – ASIACRYPT 2020 |chapter=Oblivious Pseudorandom Functions from Isogenies |series=Lecture Notes in Computer Science |title=Advances in Cryptology |date=2020 |volume=ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security12492 |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 |title=Advances in Cryptology – EUROCRYPT 2023 |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 Techniques14008 |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]].