Oblivious pseudorandom function: Difference between revisions

Revision as of 14:09, 6 February 2024

Revision as of 02:22, 8 February 2024

Line 1:

{{Short description|Function computed by two parties that emulates a random oracle}}

An '''oblivious pseudorandom function''' (OPRF) is a [[Cryptography|cryptographic]] function, similar to a [[HMAC|keyed-hash function]], but with the distinction that in an OPRF [[Secure_twoSecure two-party_computationparty computation|two parties]] cooperate to [[Secure_multiSecure multi-party_computationparty computation|securely compute]] a [[Pseudorandom function family|pseudorandom function]] (PRF).<ref name="oprf">{{cite journal |last1=Casacuberta |first1=Sílvia |last2=Hesse |first2=Julia |last3=Lehmann |first3=Anja |title=SoK: Oblivious Pseudorandom Functions |journal=Cryptology ePrint Archive |date=2022 |volume=Paper 2022/302 |url=https://eprint.iacr.org/2022/302}}</ref>

== Definition ==

Line 10:

* The first-party (''the client''), knows the ''input'' ('''I''') and learns the ''output'' ('''O''') but does not learn the ''secret'' ('''S''')

* The second-party (''the server''), knows the ''secret'' ('''S'''), but does not learn either the input ('''I'''), nor the output ('''O''').

* The function has the same security properties as any [[Cryptographic_hash_functionCryptographic hash function|cryptographically- secure]] pseudorandom function:

** It is hard to find two inputs with the same output (i.e. it is [[Hash_collisionHash collision|collision resistant]])

** It is hard to invert (i.e. it is resistant to [[Preimage_attack|preimage attacksattack]]s)

** It is hard to distinguish the output from [[Cryptographically_secure_pseudorandom_number_generatorCryptographically secure pseudorandom number generator#Requirements|true randomness]]

The function is called an ''Oblivious'' Pseudorandom Function, because the second-party is ''oblivious'' to the function's output. This party learns no new information from participating in the calculation of the result.

However, because it is only the second-party that holds the secret, the first-party must involve the second-party to calculate the output of the [[Pseudorandom function family|pseudorandom function]] (PRF). This requirement enables the second-party to implement [[Access_control|access controlscontrol]]s, [[Rate_limitingRate limiting|throttling]], [[Audit_trailAudit trail|audit logging]] and or other security measures.

__TOC__

Line 23:

== History ==

While conventional [[Pseudorandom_function_familyPseudorandom 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 (JACM) |date=1986 |volume=33 |issue=4 |pagepages=792-807792–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%E2%80%93Reingold_pseudorandom_functionNaor–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 conference |last1=Freedman |first1=Michael |last2=Ishai |first2=Yuval |last3=Pinkas |first3=Benny |last4=Reingold |first4=Omer |title=Keyword Search and Oblivious Pseudorandom Functions |journal=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 |url=https://link.springer.com/chapter/10.1007/978-3-540-30576-7_17}}</ref>

== Applications ==

Line 29:

OPRFs have many useful applications in [[cryptography]] and [[information security]].

These include [[PBKDF2|password-based key derivation]], password-based [[key agreement]], password-hardening, untraceable [[CAPTCHA]]s, [[Password_managerPassword manager|password management]], [[Homomorphic_encryptionHomomorphic encryption|homomorphic]] [[key management]], and [[Private_set_intersection|private set intersection]].<ref name="oprf"/><ref>{{cite web |last1=Krawczyk |first1=Hugo |title=Oblivious Pseudorandom Functions and Some (Magical) Applications |url=https://www.cs.columbia.edu/~tal/4261/F19/hugo-columbia-oprf.pdf |publisher=Columbia University |access-date=31 January 2024}}</ref>

An OPRF can be viewed as a special case of [[homomorphic encryption]], as it enables another party to compute a function over an [[Ciphertext|encrypted input]] and produce a result (which remains encrypted) and therefore it learns nothing about what it computed.

Line 35:

=== Password-based key derivation ===

Most forms of password-based key derivation suffer from the fact that passwords usually contain a [[Password_strengthPassword strength|small amount of randomness]] (or entropy) compared to full-length 128- or 256-bit encryption keys. This makes keys derived from passwords vulnerable to [[brute-force attack]]s.

However, this threat can be mitigated by using the output of an OPRF that takes the password as input.

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_crackingPassword 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.

Line 45:

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.

The recovered key may then be used for authentication (e.g. performing a [[Public_key_infrastructurePublic key infrastructure|PKI-based]] authentication using a [[digital certificate]] and [[private key]]), or may be used to decrypt sensitive content, such as an encrypted [[Computer file|file]] or [[crypto wallet]].

=== Password-authenticated key exchange ===

Line 55:

With PAKE, however, the user's password is not sent to the server, preventing it from falling into an eavesdropper's hands. It can be seen as an authentication via a [[zero-knowledge password proof]].

Various '[[Password-authenticated_key_agreementauthenticated key agreement#Augmented_PAKEAugmented PAKE|augmented forms]]' of PAKE incorporate an Oblivious Pseudorandom Function so that the server never sees the user's password during the authentication, but nevertheless it is able to authenticate the client is in possession of the correct password. This is done by assuming only the client that knows the correct password, can use the OPRF to derive the correct key.

An example of an augmented PAKE that uses an OPRF in this way is ''[[Password-authenticated_key_agreementauthenticated key agreement#Augmented_PAKEAugmented PAKE|OPAQUE]]''.<ref>{{cite web |title=The OPAQUE Asymmetric PAKE Protocol (Draft) |url=https://tools.ietf.org/html/draft-irtf-cfrg-opaque-02 |publisher=[[Internet Engineering Task Force]] |first1=Hugo |last1=Krawczyk | first2=Kevin |last2= Lewi |first3=Christopher |last3=Wood|date=5 February 2021 }}</ref><ref>

{{cite web |author=Tatiana Bradley |date=2020-12-08 |title=OPAQUE: The Best Passwords Never Leave your Device |url=https://blog.cloudflare.com/opaque-oblivious-passwords/ |website=The Cloudflare Blog}}</ref><ref>

{{cite web | first1= Daniel | last1 = Bourdrez | first2= Hugo | last2= Krawczyk | first3= Kevin | last3= Lewi | first4 = Christopher A. | last4= Wood | title = The OPAQUE Asymmetric PAKE Protocol (Internet Draft) | date= 2022-07-06 | url = https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-opaque | publisher = IETF }}</ref><ref name="mgreen" >

Line 65:

</ref>

Recently, OPRFs have been applied to password-based key exchange to [[back up]] encrypted chat histories in [[WhatsApp]]<ref>{{cite journal |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=Security Analysis of the WhatsApp End-to-End Encrypted Backup Protocol |journal=Advances in Cryptology |date=2023 |volume=Advances in Cryptology – CRYPTO 2023: 43rd Annual International Cryptology Conference, CRYPTO 2023 |pages=330-361330–361 |doi=10.1007/978-3-031-38551-3_11 |url=https://dl.acm.org/doi/abs/10.1007/978-3-031-38551-3_11 |access-date=2 February 2024}}</ref> and [[Messenger (software)|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_Signal (software)|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 ===

A CAPTCHA or "Completely Automated Public [[Turing test]] to tell Computers and Humans Apart."<ref>{{Cite web |title=What is CAPTCHA? |url=https://support.google.com/a/answer/1217728 |url-status=live |archive-url=https://web.archive.org/web/20200806173938/https://support.google.com/a/answer/1217728 |archive-date=6 August 2020 |access-date=2022-09-09 |website=Google Support |publisher=Google Inc. |quote=CAPTCHA (Completely Automated Public Turing test to tell Computers and Humans Apart) is a [...]}}</ref> is a mechanism to prevent automated robots or ([[Internet_botInternet bot|bots]]) from accessing websites. Lately, mechanisms for running CAPTCHA tests have been centralized to services such as a [[Google]] and [[CloudFlare]], but this can come at the expense of user privacy.

Recently, CloudFlare developed a privacy-preserving technology called "Privacy Pass"<ref>{{cite web |last1=Sullivan |first1=Nick |title=Cloudflare supports Privacy Pass |url=https://blog.cloudflare.com/cloudflare-supports-privacy-pass/ |website=CloudFlare |date=9 November 2017 |publisher=CloudFlare.com |access-date=30 January 2024}}</ref> This technology is based on OPRFs, and enables the client's browser to obtain passes from CloudFlare and then present them to bypass CAPTCHA tests. Due to the fact that the CloudFlare service is oblivious to which passes were provided to which users, there is no way it can correlate users with the websites they visit. This prevents tracking of the user, and thereby preserves the user's privacy.

Line 83:

The first proposal for a password maanger based on OPRFs was SPHINX.<ref>{{cite journal |last1=Shirvanian |first1=Maliheh |last2=Jarecki |first2=Stanislaw |last3=Krawczykz |first3=Hugo |last4=Saxena |first4=Nitesh |title=SPHINX: A Password Store that Perfectly Hides Passwords from Itself |journal=2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS) |date=2017 |doi=10.1109/ICDCS.2017.64 |url=https://ieeexplore.ieee.org/document/7980050}}</ref>

An OPRF is used by the Password Monitor in [[Microsoft Edge]].<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/|archive-url=|archive-date=|access-date=January 1, 2021|website=Microsoft Research Blog}}</ref>.

=== A homomorphic key management system ===

Line 89:

Similarly to securing passwords managed by a password manager, an OPRF can be used to enhance the security of a [[key management system]].

For example, an OPRF enables a key-management system to issue [[Key_Key (cryptography)|cryptographic keys]] to authenticated and authorized users, without ever seeing, learning, or being in a position to learn, any of the keys it provides to users.<ref>{{cite book |last1=Jarecki |first1=Stanislaw |last2=Krawczyk |first2=Hugo |last3=Resch |first3=Jason |chapter=Updatable Oblivious Key Management for Storage Systems |date=2019 |title=Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security |volume=November 2019 |pages=379–393 |doi=10.1145/3319535.3363196 |isbn=978-1-4503-6747-9 |chapter-url=https://dl.acm.org/doi/10.1145/3319535.3363196 |access-date=Jan 27, 2024}}</ref>.

=== Private set intersection ===

Line 97:

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_limitingRate 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-6334–63 |doi=10.1007/978-3-030-56877-1_2 |url=https://dl.acm.org/doi/10.1007/978-3-030-56877-1_2}}</ref>

== Implementations ==

Line 107:

=== EC and conventional Diffie–Hellman ===

Elliptic Curves and prime order fields can be used to implement an OPRF. The essential idea is that the first-party (the client), must cryptographically ''[[Blinding_Blinding (cryptography)|blind]]'' the input prior sending it to the second-party.

This blinding can be viewed as a form of [[encryption]] that survives the computation performed by the second-party. Therefore, the first-party can [[decrypt]] what it receives from the second-party to "unblind" it, and thereby receive the same result it would have received had the input not been blinded.

When the second-party receives the blinded input, it performs a computation on it using a [[Key_Key (cryptography)|secret]]. The result of this computation must not reveal the secret.

For example, the second-party may perform a [[Elliptic_curve_point_multiplicationElliptic curve point multiplication|point multiplication]] of a point on an elliptic curve. Or it may perform a [[modular exponentiation]] modulo a large [[prime]].

The first-party, upon receipt of the result, and with knowledge of the blinding-factor, computes a function that removes the blinding factor's influence on the result returned by the second-party. This 'unblinds' the result, revealing the output of the OPRF, (or an intermediate result which is then used by the client to compute the output of the OPRF, for example, by hashing this intermediate result).

Line 153:

Notes:

The client computes the [[Modular_multiplicative_inverseModular multiplicative inverse|multiplicative inverse]] of the blinding factor. This enables it to reverse the effect of the blinding factor on the result, and obtain the result the server would have returned had the client not blinded the input.

As a final step, to complete the OPRF, the client performs a [[Cryptographic_hash_functionCryptographic hash function|one-way hash]] on the result to ensure the OPRF output is [[Discrete_uniform_distributionDiscrete uniform distribution|uniform]], completely [[pseudorandom]], and non-invertible.

===== Server-side calculation =====

Line 177:

Because the elliptic curve point multiplication is computationally difficult to invert (like the [[discrete logarithm]] problem, the client cannot feasibly learn the server's secret from the response it produces.

Note, however, that this function is vulnerable to [[Shor%27s_algorithm's algorithm|attacks]] by [[Quantum computing|quantum computers]]. A client or third party in possession of a quantum computer could solve for the server's secret knowing the result it produced for a given input.

=== RSA blind signatures ===

Line 195:

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 [[Elliptic Curve]] or [[Diffie-Hellman]] based OPRFs, then 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 journal |last1=Jarecki |first1=Stanislaw |last2=Kiayias |first2=Aggelos |last3=Krawczyk |first3=Hugo |title=Round-Optimal Password-Protected Secret Sharing and T-PAKE in the Password-Only Model |journal=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-117–11, 2014, Proceedings, Part II |pages=233-253233–253 |doi=10.1007/978-3-662-45608-8_13}}</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 |url=https://www.rfc-editor.org/info/rfc9497}}</ref>

=== Partially-oblivious PRF ===

Line 215:

=== Threshold implementations ===

For even greater security, it is possible to [[Threshold_cryptosystemThreshold cryptosystem|thresholdize the server]], such that the secret ('''S''') is not held by any individual server, and so the compromise of any single server, or set of servers below some defined threshold, will not expose the secret.

This can be done by having each server be a shareholder in a [[Secret_sharingSecret sharing|secret sharing scheme]]. Instead of using it's secret to compute the result, each server uses it's ''share'' of the secret to perform the computation.

The client then takes some subset of the server's computed results, and combines them, for example by computing a protocol known as ''interpolation in the exponent''. This recovers the same result as had the client interacted with a single server which has the full secret.

Line 225:

=== Post-quantum secure implementations ===

Finding efficient [[Post-quantum_cryptographyquantum cryptography|post-quantum]] secure implementations of OPRFs is an area of active research.<ref>{{cite journal |last1=Boneh |first1=Dan |last2=Ishai |first2=Yuval |last3=Passelègue |first3=Alain |last4=Sahai |first4=Amit |last5=Wu |first5=David |title=Exploring Crypto Dark Matter: New Simple PRF Candidates and Their Applications |journal=Cryptology ePrint Archive |date=2018 |volume=Paper 2018/1218 |url=https://eprint.iacr.org/2018/1218}}</ref>

<blockquote>"With the exception of OPRFs based on symmetric primitives, all known efficient OPRF

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_cryptographybased 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_exchangeSupersingular isogeny key exchange|isogeny-based]] OPRFs,<ref>{{cite conference |last1=Boneh |first1=Dan |last2=Kogan |first2=Dmitry |last3=Woo |first3=Katharine |chapter=Oblivious Pseudorandom Functions from Isogenies |series=Lecture Notes in Computer Science |title=Advances in Cryptology – ASIACRYPT 2020 |journal=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 |chapter-url=https://dl.acm.org/doi/10.1007/978-3-030-64834-3_18}}</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 journal |last1=Castryck |first1=Wouter |last2=Decru |first2=Thomas |title=An efficient key recovery attack on SIDH |journal=Advances in Cryptology |date=2023 |volume=EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques |pages=423-447423–447 |doi=10.1007/978-3-031-30589-4_15 |url=https://dl.acm.org/doi/abs/10.1007/978-3-031-30589-4_15}}</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]].