Content deleted Content added
Jasonkresch (talk | contribs) m →Verifiable OPRF: Made x an exponent. |
Jasonkresch (talk | contribs) Updated references throughout document |
||
Line 1:
{{Short description|A 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
==
Specifically, an OPRF is
* The parties compute: '''O''' = OPRF('''I''', '''S''')
* 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_function|cryptographically-secure]] pseudorandom function:
** It is hard to find two inputs with the same output (i.e. it is [[Hash_collision|collision resistant]]
** It is hard to invert (i.e. it is resistant to [[Preimage_attack|preimage attacks]])
** It is hard to distinguish the output from [[Cryptographically_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 [[
__TOC__
Line 19 ⟶ 23:
== History ==
While conventional [[Pseudorandom_function_family|Pseudorandom Functions]] computed by a single party were first
== Applications ==
Line 41 ⟶ 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_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 ===
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]].
To overcome this, various '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_agreement#Augmented_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>
Line 59 ⟶ 65:
</ref>
Recently,
=== Untraceable CAPTCHAs ===
Line 74 ⟶ 80:
By using an OPRF, however, passwords for an individual site can be derived from a single [[master password]], without the service being in a position to learn either the user's master password, nor any of the derived passwords produced from it.
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>.
Line 187 ⟶ 195:
Fortunately, most OPRFs support verifiability. For example, when using [[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<sup>x</sup>'', 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-11, 2014, Proceedings, Part II |pages=233-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 201 ⟶ 209:
The use case for this is when the server needs to implement specific throttling or access controls on the exposed input ('''E'''), for example, ('''E''') could be a file path, or user name, for which the server enforces [[access control]]s, and only services requests when the requesting user is authorized.
Recently, versions of P-OPRFs not based on pairings have appeared, such as a version standardized in the [[IETF]] [[Request for Comments|RFC]] 9497.<ref name="voprf"/> as well in a more recent improvement.<ref>{{cite journal |last1=Tyagi |first1=Nirvan |last2=Celi |first2=Sofı́a |last3=Ristenpart |first3=Thomas |last4=Sullivan |first4=Nick |last5=Tessaro |first5=Stefano |last6=Wood |first6=Christopher A. |title=A Fast and Simple Partially Oblivious PRF, with Applications |journal=Cryptology ePrint Archive |date=2021 |volume=Paper 2021/864 |url=https://eprint.iacr.org/2021/864}}</ref>
=== Threshold implementations ===
Line 220 ⟶ 230:
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 |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-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]].
== See also ==
Line 228 ⟶ 240:
* [[Oblivious transfer]]
* [[Secure multi-party computation]]
* [[Cryptographic protocol]]
* [[Homomorphic encryption]]
| |||