Content deleted Content added
m Disambiguating links to RSA (link changed to RSA (cryptosystem)) using DisamAssist. |
MOS:HEAD |
||
Line 1:
{{Short description|A function computed by two parties that emulates a random oracle.}}
An '''
== Formal
Specifically, an OPRF is any function with the following properties:
Line 25:
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
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 thereby it learns nothing about what it computed.
=== Password-
Most forms of password-based key derivation suffer from the fact that passwords usually contain a [[Password_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
However, this threat can be mitigated by using the output of an OPRF that takes the password as input.
Line 37:
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 [[
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 43:
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-
For protocols such as [[Transport Layer Security|TLS]], a [[password]] can be used as the basis of a [[key agreement]] protocol, to establish temporary session keys or and mutually authenticate the client and server. In the TLS protocol, this system is called a ''Password-Authenticated Key Exchange'' or [[PAKE]].
Line 59:
</ref>
Recently, password-based keys have been used for secure backing up of encrypted chat histories in [[Messenger (software)|Facebook
=== Untraceable CAPTCHAs ===
Line 65:
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_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.
=== An
A [[password manager]] is software or a service that holds potentially many different passwords on behalf of the a single user.
Line 77:
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
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_(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
[[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 entires which they do not hold in common.
Line 95:
There are various mathematical functions that can serve as the basis to implement an OPRF.
For example, methods from [[asymmetric cryptography]], including [[
=== EC and
Elliptic Curves and prime order fields can be used to implement an OPRF. The essential idea is that the first-party (the client), must
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.
Line 109:
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).
==== Sample OPRF
The following is [[pseudocode]] for the calculations performed by the client and server using an
===== Client-side calculation =====
Line 118:
<syntaxhighlight lang="java">
byte[] computeOPRF(byte[] input) {
▲ // Apply point-hashing algorithm
// For example, as described in RFC 9380
ECPoint hashedPoint = hashToPoint(input);
// Generate a random blinding factor
Scalar b = randomScalar();
// Blind the input via a curve multiply
ECPoint blindedInput = ECMultiply(hashedPoint, b);
// Send request to server to obtain response
ECPoint serverResponse = sendRequest(blindedInput);
// Compute multiplicative inverse of b▼
Scalar inverse = modInverse(b); ▼
// Unblind the response to produce the result ▼
ECPoint result = ECMultiply(serverResponse, inverse);▼
▲ // Compute multiplicative inverse of b
// Hash the unblinded result to complete OPRF calculation ▼
return hash(result);▼
▲ ECPoint result = ECMultiply(serverResponse, inverse);
▲ return hash(result);
}
</syntaxhighlight>
Line 158 ⟶ 157:
<syntaxhighlight lang="java">
ECPoint processRequest(ECPoint blindedInput, Scalar secret) {
// Apply secret to compute the response
ECPoint response = ECMultiply(blindedInput, secret);
return response;
Line 170 ⟶ 169:
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|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
When the output of a [[
This is because due to the blinding, the party computing the blind signature learns neither the input (what is being signed) nor the output (the resulting [[digital signature]]).
Line 180 ⟶ 179:
== Extensions ==
The OPRF construction can be extended in various ways. These include: partially-oblivious,
=== Partially-
One modification to an OPRF is called a
Specifically, a P-OPRF is any function with the following properties:
Line 192 ⟶ 191:
* The second-party (''the server''), knows the ''secret'' ('''S'''), and learns the ''exposed input'' ('''E'''), but does not learn either the ''hidden input'' ('''H'''), nor the ''output'' ('''O''').
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
Such a scheme is used by the "Pythia PRF Service".<ref>{{cite journal |last1=Everspaugh |first1=Adam |last2=Chaterjee |first2=Rahul |last3=Scott |first3=Samuel |last4=Juels |first4=Ari |last5=Ristenpart |first5=Thomas |title=The Pythia PRF Service |journal=24th USENIX Security Symposium (USENIX Security 15) |date=2015 |pages=547–562 |isbn=978-1-939133-11-3 |url=https://www.usenix.org/conference/usenixsecurity15/technical-sessions/presentation/everspaugh}}</ref>
=== Threshold
For even greater security, it is possible to [[Threshold_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.
Line 204 ⟶ 203:
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.
This
=== Post-
Finding efficient [[Post-quantum_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>
Line 217 ⟶ 216:
== See also ==
* [[
* [[
* [[Oblivious
* [[
* [[
== References ==
| |||