idnits 2.17.1 draft-irtf-cfrg-voprf-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 09, 2020) is 1507 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 1758 -- Looks like a reference, but probably isn't: '2' on line 1760 -- Looks like a reference, but probably isn't: '3' on line 1762 == Outdated reference: A later version (-16) exists of draft-irtf-cfrg-hash-to-curve-05 Summary: 1 error (**), 0 flaws (~~), 2 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group A. Davidson 3 Internet-Draft N. Sullivan 4 Intended status: Informational Cloudflare 5 Expires: September 10, 2020 C. Wood 6 Apple Inc. 7 March 09, 2020 9 Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups 10 draft-irtf-cfrg-voprf-03 12 Abstract 14 An Oblivious Pseudorandom Function (OPRF) is a two-party protocol for 15 computing the output of a PRF. One party (the server) holds the PRF 16 secret key, and the other (the client) holds the PRF input. The 17 'obliviousness' property ensures that the server does not learn 18 anything about the client's input during the evaluation. The client 19 should also not learn anything about the server's secret PRF key. 20 Optionally, OPRFs can also satisfy a notion 'verifiability' (VOPRF). 21 In this setting, the client can verify that the server's output is 22 indeed the result of evaluating the underlying PRF with just a public 23 key. This document specifies OPRF and VOPRF constructions 24 instantiated within prime-order groups, including elliptic curves. 26 Status of This Memo 28 This Internet-Draft is submitted in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF). Note that other groups may also distribute 33 working documents as Internet-Drafts. The list of current Internet- 34 Drafts is at https://datatracker.ietf.org/drafts/current/. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 This Internet-Draft will expire on September 10, 2020. 43 Copyright Notice 45 Copyright (c) 2020 IETF Trust and the persons identified as the 46 document authors. All rights reserved. 48 This document is subject to BCP 78 and the IETF Trust's Legal 49 Provisions Relating to IETF Documents 50 (https://trustee.ietf.org/license-info) in effect on the date of 51 publication of this document. Please review these documents 52 carefully, as they describe your rights and restrictions with respect 53 to this document. Code Components extracted from this document must 54 include Simplified BSD License text as described in Section 4.e of 55 the Trust Legal Provisions and are provided without warranty as 56 described in the Simplified BSD License. 58 Table of Contents 60 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 61 1.1. Change log . . . . . . . . . . . . . . . . . . . . . . . 5 62 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 6 63 1.3. Requirements . . . . . . . . . . . . . . . . . . . . . . 6 64 2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 6 65 3. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 7 66 3.1. Security Properties . . . . . . . . . . . . . . . . . . . 7 67 3.2. Prime-order group instantiation . . . . . . . . . . . . . 8 68 3.3. Conventions . . . . . . . . . . . . . . . . . . . . . . . 8 69 3.3.1. Binary strings . . . . . . . . . . . . . . . . . . . 8 70 3.3.2. Group notation . . . . . . . . . . . . . . . . . . . 9 71 4. OPRF Protocol . . . . . . . . . . . . . . . . . . . . . . . . 9 72 4.1. Design . . . . . . . . . . . . . . . . . . . . . . . . . 10 73 4.2. Protocol functionality . . . . . . . . . . . . . . . . . 11 74 4.2.1. Generalized OPRF . . . . . . . . . . . . . . . . . . 12 75 4.2.2. Generalized VOPRF . . . . . . . . . . . . . . . . . . 13 76 4.3. Protocol correctness . . . . . . . . . . . . . . . . . . 14 77 4.4. Domain separation . . . . . . . . . . . . . . . . . . . . 14 78 4.5. Instantiations of GG . . . . . . . . . . . . . . . . . . 14 79 4.6. OPRF algorithms . . . . . . . . . . . . . . . . . . . . . 15 80 4.6.1. Setup . . . . . . . . . . . . . . . . . . . . . . . . 15 81 4.6.2. Blind . . . . . . . . . . . . . . . . . . . . . . . . 15 82 4.6.3. Evaluate . . . . . . . . . . . . . . . . . . . . . . 16 83 4.6.4. Unblind . . . . . . . . . . . . . . . . . . . . . . . 16 84 4.6.5. Finalize . . . . . . . . . . . . . . . . . . . . . . 17 85 4.7. VOPRF algorithms . . . . . . . . . . . . . . . . . . . . 17 86 4.7.1. VerifiableSetup . . . . . . . . . . . . . . . . . . . 17 87 4.7.2. VerifiableBlind . . . . . . . . . . . . . . . . . . . 17 88 4.7.3. VerifiableEvaluate . . . . . . . . . . . . . . . . . 18 89 4.7.4. VerifiableUnblind . . . . . . . . . . . . . . . . . . 18 90 4.7.5. VerifiableFinalize . . . . . . . . . . . . . . . . . 19 91 4.8. Efficiency gains with pre-processing and fixed-base 92 blinding . . . . . . . . . . . . . . . . . . . . . . . . 19 93 4.8.1. Preprocess . . . . . . . . . . . . . . . . . . . . . 20 94 4.8.2. Blind . . . . . . . . . . . . . . . . . . . . . . . . 20 95 4.8.3. Unblind . . . . . . . . . . . . . . . . . . . . . . . 21 97 5. NIZK Discrete Logarithm Equality Proof . . . . . . . . . . . 21 98 5.1. DLEQ_Generate . . . . . . . . . . . . . . . . . . . . . . 22 99 5.2. DLEQ_Verify . . . . . . . . . . . . . . . . . . . . . . . 22 100 6. Batched VOPRF evaluation . . . . . . . . . . . . . . . . . . 23 101 6.1. Batched_DLEQ_Generate . . . . . . . . . . . . . . . . . . 24 102 6.2. DLEQ_Batched_Verify . . . . . . . . . . . . . . . . . . . 24 103 6.3. Modified algorithms . . . . . . . . . . . . . . . . . . . 25 104 6.3.1. VerifiableBlind . . . . . . . . . . . . . . . . . . . 25 105 6.3.2. VerifiableEvaluate . . . . . . . . . . . . . . . . . 26 106 6.3.3. VerifiableUnblind . . . . . . . . . . . . . . . . . . 26 107 6.3.4. VerifiableFinalize . . . . . . . . . . . . . . . . . 27 108 6.4. Random oracle instantiations for proofs . . . . . . . . . 27 109 7. Supported ciphersuites . . . . . . . . . . . . . . . . . . . 28 110 7.1. OPRF-curve448-HKDF-SHA512-ELL2-RO: . . . . . . . . . . . 28 111 7.2. OPRF-P384-HKDF-SHA512-SSWU-RO: . . . . . . . . . . . . . 28 112 7.3. OPRF-P521-HKDF-SHA512-SSWU-RO: . . . . . . . . . . . . . 29 113 7.4. VOPRF-curve448-HKDF-SHA512-ELL2-RO: . . . . . . . . . . . 29 114 7.5. VOPRF-P384-HKDF-SHA512-SSWU-RO: . . . . . . . . . . . . . 29 115 7.6. VOPRF-P521-HKDF-SHA512-SSWU-RO: . . . . . . . . . . . . . 30 116 8. Security Considerations . . . . . . . . . . . . . . . . . . . 30 117 8.1. Cryptographic security . . . . . . . . . . . . . . . . . 30 118 8.1.1. Computational hardness assumptions . . . . . . . . . 30 119 8.1.2. Protocol security . . . . . . . . . . . . . . . . . . 31 120 8.1.3. Q-strong-DH oracle . . . . . . . . . . . . . . . . . 32 121 8.1.4. Implications for ciphersuite choices . . . . . . . . 32 122 8.2. Hashing to curve . . . . . . . . . . . . . . . . . . . . 33 123 8.3. Timing Leaks . . . . . . . . . . . . . . . . . . . . . . 33 124 8.4. User segregation . . . . . . . . . . . . . . . . . . . . 33 125 8.4.1. Linkage patterns . . . . . . . . . . . . . . . . . . 34 126 8.4.2. Evaluation on multiple keys . . . . . . . . . . . . . 34 127 8.5. Key rotation . . . . . . . . . . . . . . . . . . . . . . 35 128 9. Applications . . . . . . . . . . . . . . . . . . . . . . . . 36 129 9.1. Privacy Pass . . . . . . . . . . . . . . . . . . . . . . 36 130 9.2. Private Password Checker . . . . . . . . . . . . . . . . 36 131 9.2.1. Parameter Commitments . . . . . . . . . . . . . . . . 37 132 10. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 37 133 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 37 134 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 37 135 12.1. Normative References . . . . . . . . . . . . . . . . . . 37 136 12.2. URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 39 137 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 39 139 1. Introduction 141 A pseudorandom function (PRF) F(k, x) is an efficiently computable 142 function with secret key k on input x. Roughly, F is pseudorandom if 143 the output y = F(k, x) is indistinguishable from uniformly sampling 144 any element in F's range for random choice of k. An oblivious PRF 145 (OPRF) is a two-party protocol between a prover P and verifier V 146 where P holds a PRF key k and V holds some input x. The protocol 147 allows both parties to cooperate in computing F(k, x) with P's secret 148 key k and V's input x such that: V learns F(k, x) without learning 149 anything about k; and P does not learn anything about x. A 150 Verifiable OPRF (VOPRF) is an OPRF wherein P can prove to V that F(k, 151 x) was computed using key k, which is bound to a trusted public key Y 152 = kG. Informally, this is done by presenting a non-interactive zero- 153 knowledge (NIZK) proof of equality between (G, Y) and (Z, M), where Z 154 = kM for some point M. 156 OPRFs have been shown to be useful for constructing: password- 157 protected secret sharing schemes [JKK14]; privacy-preserving password 158 stores [SJKS17]; and password-authenticated key exchange or PAKE 159 [OPAQUE]. VOPRFs are useful for producing tokens that are verifiable 160 by V. This may be needed, for example, if V wants assurance that P 161 did not use a unique key in its computation, i.e., if V wants key 162 consistency from P. This property is necessary in some applications, 163 e.g., the Privacy Pass protocol [PrivacyPass], wherein this VOPRF is 164 used to generate one-time authentication tokens to bypass CAPTCHA 165 challenges. VOPRFs have also been used for password-protected secret 166 sharing schemes e.g. [JKKX16]. 168 This document introduces an OPRF protocol built in prime-order 169 groups, applying to finite fields of prime-order and also elliptic 170 curve (EC) settings. The protocol has the option of being extended 171 to a VOPRF with the addition of a NIZK proof for proving discrete log 172 equality relations. This proof demonstrates correctness of the 173 computation using a known public key that serves as a commitment to 174 the server's secret key. The document describes the protocol, its 175 security properties, and provides preliminary test vectors for 176 experimentation. The rest of the document is structured as follows: 178 o Section 2: Describe background, related work, and use cases of 179 OPRF/VOPRF protocols. 181 o Section 3: Describe conventions and assumptions made relating to 182 security of (V)OPRFs and prime-order group instantiations. 184 o Section 4: Specify an authentication protocol from OPRF 185 functionality, based in prime-order groups (with an optional 186 verifiable mode). Algorithms are stated formally for OPRFs in 187 Section 4.6 and for VOPRFs in Section 4.7. 189 o Section 5: Specify the NIZK discrete logarithm equality (DLEQ) 190 construction used for constructing the VOPRF protocol. 192 o Section 6: Specifies how the DLEQ proof mechanism can be batched 193 for multiple VOPRF invocations, and how this changes the protocol 194 execution. 196 o Section 7: Considers explicit instantiations of the protocol in 197 the elliptic curve setting. 199 o Section 8: Discusses the security considerations for the OPRF and 200 VOPRF protocol. 202 o Section 9: Discusses some existing applications of OPRF and VOPRF 203 protocols. 205 1.1. Change log 207 draft-03 [1]: 209 o Certify public key during VerifiableFinalize 211 o Remove protocol integration advice 213 o Add text discussing how to perform domain separation 215 o Drop OPRF_/VOPRF_ prefix from algorithm names 217 o Make prime-order group assumption explicit 219 o Changes to algorithms accepting batched inputs 221 o Changes to construction of batched DLEQ proofs 223 o Updated ciphersuites to be consistent with hash-to-curve and added 224 OPRF specific ciphersuites 226 draft-02 [2]: 228 o Added section discussing cryptographic security and static DH 229 oracles 231 o Updated batched proof algorithms 233 draft-01 [3]: 235 o Updated ciphersuites to be in line with 236 https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-04 238 o Made some necessary modular reductions more explicit 240 1.2. Terminology 242 The following terms are used throughout this document. 244 o PRF: Pseudorandom Function. 246 o OPRF: Oblivious PRF. 248 o VOPRF: Verifiable Oblivious Pseudorandom Function. 250 o Verifier (V): Protocol initiator when computing F(k, x), also 251 known as client. 253 o Prover (P): Holder of secret key k, also known as server. 255 o NIZK: Non-interactive zero knowledge. 257 o DLEQ: Discrete Logarithm Equality. 259 1.3. Requirements 261 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 262 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 263 document are to be interpreted as described in [RFC2119]. 265 2. Background 267 OPRFs are functionally related to blind signature schemes. In such a 268 scheme, a client can receive signatures on private data, under the 269 signing key of some server. The security properties of such a scheme 270 dictate that the client learns nothing about the signing key, and 271 that the server learns nothing about the data that is signed. One of 272 the more popular blind signature schemes is based on the RSA 273 cryptosystem and is known as Blind RSA [ChaumBlindSignature]. 275 OPRF protocols can thought of as symmetric alternatives to blind 276 signatures. Essentially the client learns y = PRF(k,x) for some 277 input x of their choice, from a server that holds k. Since the 278 security of an OPRF means that x is hidden in the interaction, then 279 the client can later reveal x to the server along with y. 281 The server can verify that y is computed correctly by recomputing the 282 PRF on x using k. In doing so, the client provides knowledge of a 283 'signature' y for their value x. The verification procedure is thus 284 symmetric as it requires knowledge of the key k. This is discussed 285 more in the following section. 287 3. Preliminaries 289 We start by detailing some necessary cryptographic definitions. 291 3.1. Security Properties 293 The security properties of an OPRF protocol with functionality y = 294 F(k, x) include those of a standard PRF. Specifically: 296 o Pseudorandomness: F is pseudorandom if the output y = F(k,x) on 297 any input x is indistinguishable from uniformly sampling any 298 element in F's range, for a random sampling of k. 300 In other words, for an adversary that can pick inputs x from the 301 domain of F and can evaluate F on (k,x) (without knowledge of 302 randomly sampled k), then the output distribution F(k,x) is 303 indistinguishable from the uniform distribution in the range of F. 305 A consequence of showing that a function is pseudorandom, is that it 306 is necessarily non-malleable (i.e. we cannot compute a new evaluation 307 of F from an existing evaluation). A genuinely random function will 308 be non-malleable with high probability, and so a pseudorandom 309 function must be non-malleable to maintain indistinguishability. 311 An OPRF protocol must also satisfy the following property: 313 o Oblivious: P must learn nothing about V's input or the output of 314 the function. In addition, V must learn nothing about P's private 315 key. 317 Essentially, obliviousness tells us that, even if P learns V's input 318 x at some point in the future, then P will not be able to link any 319 particular OPRF evaluation to x. This property is also known as 320 unlinkability [DGSTV18]. 322 Optionally, for any protocol that satisfies the above properties, 323 there is an additional security property: 325 o Verifiable: V must only complete execution of the protocol if it 326 can successfully assert that the OPRF output computed by V is 327 correct, with respect to the OPRF key held by P. 329 Any OPRF that satisfies the 'verifiable' security property is known 330 as a verifiable OPRF, or VOPRF for short. In practice, the notion of 331 verifiability requires that P commits to the key k before the actual 332 protocol execution takes place. Then V verifies that P has used k in 333 the protocol using this commitment. In the following, we may also 334 refer to this commitment as a public key. 336 3.2. Prime-order group instantiation 338 In this document, we assume the construction of a prime-order group 339 GG for performing all mathematical operations. Such a group MUST 340 provide the interface provided by cyclic group under the addition 341 operation (for example, well-defined addition of group elements). We 342 also assume the presence of a fixed generator G that can be detailed 343 as a fixed parameter in the description of the group. We write p = 344 order(GG) to represent the order of the group throughout this 345 document. 347 It is common in cryptographic applications to instantiate such prime- 348 order groups using elliptic curves, such as those detailed in [SEC2]. 349 For some choices of elliptic curves (e.g. those detailed in [RFC7748] 350 require accounting for cofactors) there are some implementation 351 issues that introduce inherent discrepancies between standard prime- 352 order groups and the elliptic curve instantiation. In this document, 353 all algorithms that we detail assume that the group is a prime-order 354 group, and this MUST be upheld by any implementer. That is, any 355 curve instantiation should be written such that any discrepancies 356 with a prime-order group instantiation are removed. In the case of 357 cofactors, for example, this can be done by building cofactor 358 multiplication into all elliptic curve operations. 360 3.3. Conventions 362 We detail a list of conventions that we use throughout this document. 364 3.3.1. Binary strings 366 o We use the notation x <-$ Q to denote sampling x from the uniform 367 distribution over the set Q. 369 o We use x <- {0,1}^u to denote sampling x uniformly from the set of 370 binary strings of length u. We may interpret x afterwards as a 371 byte array. 373 o We say that x is a binary string of arbitrary-length (or 374 alternatively sampled from {0,1}^*) if there is no fixed-size 375 requirement on x. 377 o For two byte arrays x & y, write x .. y to denote their 378 concatenation. 380 3.3.2. Group notation 382 o We use the letter p to denote the order of a group GG throughout, 383 where the instantiation of the specific group is defined by 384 context. 386 o For elements A & B of GG, we write A + B to denote the addition of 387 thr group elements. 389 o We use GF(p) to denote the Galois Field of scalar values 390 associated with the group GG. 392 o For a scalar r in GF(p), and a group element A, we write rA to 393 denote the scalar multiplication of A. 395 o For two scalars r, s in GF(p), we use r+s to denote the resulting 396 scalar in GF(p) (we may optionally write r+s mod p to make the 397 modular reduction explicit). 399 4. OPRF Protocol 401 In this section we describe the OPRF and VOPRF protocols. Recall 402 that such a protocol takes place between a verifier (V) and a prover 403 (P). Commonly, V is a client and P is a server, and so we use these 404 names interchangeably throughout. We always operate under the 405 assumption that the verifier is a client, and the prover is a server 406 in the interaction (and so we will use these names interchangeably 407 throughout). The server holds a secret key k for a PRF. The 408 protocol allows the client to learn PRF evaluations on chosen inputs 409 x in such a way that the server learns nothing of x. 411 Our OPRF construction is based on the VOPRF construction known as 412 2HashDH-NIZK given by [JKK14]; essentially without providing zero- 413 knowledge proofs that verify that the output is correct. Our VOPRF 414 construction (including the NIZK DLEQ proofs from Section 5) is 415 identical to the [JKK14] construction. With batched proofs 416 (Section 6) our construction differs slightly in that we can perform 417 multiple VOPRF evaluations in one go, whilst only constructing one 418 NIZK proof object. 420 In this section we describe the OPRF and VOPRF protocols. Recall 421 that such a protocol takes place between a verifier (V) and a prover 422 (P). We may commonly think of the verifier as the client, and the 423 prover as the server in the interaction (we will use these names 424 interchangeably throughout). The server holds a key k for a PRF. 425 The protocol allows the client to learn PRF evaluations on chosen 426 inputs x without revealing x to the server. 428 Our OPRF construction is based on the VOPRF construction known as 429 2HashDH-NIZK given by [JKK14]; essentially without providing zero- 430 knowledge proofs that verify that the output is correct. Our VOPRF 431 construction (including the NIZK DLEQ proofs from Section 5) is 432 identical to the [JKK14] construction. With batched proofs 433 (Section 6) our construction differs slightly in that we can perform 434 multiple VOPRF evaluations in one go, whilst only constructing one 435 NIZK proof object. 437 4.1. Design 439 Let GG be an additive group of prime-order p, let GF(p) be the Galois 440 field defined by the integers modulo p. Define distinct hash 441 functions H_1 and H_2, where H_1 maps arbitrary input onto GG (H_1: 442 {0,1}^* -> GG) and H_2 maps two arbitrary inputs to a fixed-length 443 (w) output (H_2: {0,1}^u x {0,1}^v -> {0,1}^w), e.g., HMAC_SHA256. 444 All hash functions in the protocol are modeled as random oracles. 445 Let L be the security parameter. Let k be the prover's secret key, 446 and Y = kG be its corresponding 'public key' for some fixed generator 447 G taken from the description of the group GG. This public key Y is 448 also referred to as a commitment to the OPRF key k, and the pair 449 (G,Y) as a commitment pair. Let x be the binary string that is the 450 verifier's input to the OPRF protocol (this can be of arbitrary 451 length). 453 The OPRF protocol begins with V blinding its input for the OPRF 454 evaluator such that it appears uniformly distributed GG. The latter 455 then applies its secret key to the blinded value and returns the 456 result. To finish the computation, V then removes its blind and 457 hashes the result (along with a domain separating label DST) using 458 H_2 to yield an output. This flow is illustrated below. 460 Verifier(x) Prover(k) 461 ---------------------------------------------------------- 462 r <-$ GF(p) 463 M = rH_1(x) mod p 464 M 465 -------> 466 Z = kM mod p 467 [D = DLEQ_Generate(k,G,Y,M,Z)] 468 Z[,D] 469 <------- 470 [b = DLEQ_Verify(G,Y,M,Z,D)] 471 N = Zr^(-1) mod p 472 Output H_2(DST, x .. N) mod p [if b=1, else "error"] 474 Steps that are enclosed in square brackets (DLEQ_Generate and 475 DLEQ_Verify) are optional for achieving verifiability. These are 476 described in Section 5. In the verifiable mode, we assume that P has 477 previously committed to their choice of key k with some values 478 (G,Y=kG) and these are publicly known by V. Notice that revealing 479 (G,Y) does not reveal k by the well-known hardness of the discrete 480 log problem. 482 Strictly speaking, the actual PRF function that is computed is: 484 F(k, x) = N = kH_1(x) 486 It is clear that this is a PRF H_1(x) maps x to a random element in 487 GG, and GG is cyclic. This output is computed when the client 488 computes Zr^(-1) by the commutativity of the multiplication. The 489 client finishes the computation by outputting H_2(DST, x .. N). Note 490 that the output from P is not the PRF value because the actual input 491 x is blinded by r. 493 The security of our construction is discussed in more detail in 494 Section 8.1.2. 496 4.2. Protocol functionality 498 This protocol may be decomposed into a series of steps, as described 499 below: 501 o Setup(l): Let GG=GG(l) be a group with a prime-order p=p(l) (e.g., 502 p is l-bits long). Randomly sample an integer k in GF(p) and 503 output (k,GG) 505 o Blind(x): Compute and return a blind, r, and blinded 506 representation of x in GG, denoted M. 508 o Evaluate(k,M,h?): Evaluates on input M using secret key k to 509 produce Z, the input h is optional and equal to the cofactor of an 510 elliptic curve. If h is not provided then it defaults to 1. 512 o Unblind(r,Z): Unblind blinded OPRF evaluation Z with blind r, 513 yielding N and output N. 515 o Finalize(x,N,aux?): Finalize N by first computing dk := H_2(DST, x 516 .. N). Subsequently output y := H_2(dk, aux), where aux is some 517 auxiliary data encoded as a byte string. If aux is not specified, 518 it defaults to the empty byte string. 520 For verifiability (VOPRF) we modify the algorithms of 521 VerifiableSetup, VerifiableEvaluate and VerifiableUnblind to be the 522 following: 524 o VerifiableSetup(l): Run (k,GG) = Setup(l), compute Y = kG, where G 525 is a generator of the group GG. Output (k,GG,Y). 527 o VerifiableEvaluate(k,G,Y,M,h?): Evaluates on input M using secret 528 key k to produce Z. Generate a NIZK proof D = 529 DLEQ_Generate(k,G,Y,M,Z), and output (Z, D). The optional 530 cofactor h can also be provided, as in Evaluate. 532 o VerifiableUnblind(r,G,Y,M,Z,D): Unblind blinded OPRF evaluation Z 533 with blind r, yielding N. Output N if 1 = DLEQ_Verify(G,Y,M,Z,D). 534 Otherwise, output "error". 536 o VerifiableFinalize(x,Y,N,aux?): Same as Finalize, except we now 537 compute dk := H_2(DST, x .. Y .. N), i.e. we also certify the 538 public key in the finalization process. 540 We leave the rest of the OPRF algorithms unmodified. When referring 541 explicitly to VOPRF execution, we replace 'OPRF' in all method names 542 with 'VOPRF'. We describe explicit instantiations of these functions 543 in Section 4.6 and Section 4.7. 545 4.2.1. Generalized OPRF 547 Using the API provided by the functions above, we can restate the 548 OPRF protocol using the following descriptions. The first protocol 549 refers to the OPRF setup phase that is run by the server. This 550 generates the secret input used by the server and the public 551 information that is given to the client. 553 OPRF setup phase: 555 Verifier() Prover(l) 556 ---------------------------------------------------------- 557 (k,GG) = Setup(l) 558 GG 559 <------- 561 OPRF evaluation phase: 563 Verifier(x,aux) Prover(k) 564 ---------------------------------------------------------- 565 (r, M) = Blind(x) 566 M 567 -------> 568 Z = Evaluate(k,M) 569 Z 570 <------- 571 N = Unblind(r,Z) 572 Output Finalize(x,N,aux) 574 Note that in the final output, the client computes Finalize over some 575 auxiliary input data aux. 577 4.2.2. Generalized VOPRF 579 The generalized VOPRF functionality differs slightly from the OPRF 580 protocol above. Firstly, the server sends over an extra commitment 581 value Y = kG, where G is a common generator known to both 582 participants. Secondly, the server sends over both outputs from 583 VerifiableEvaluate in the evaluation phase, and the client also 584 verifies the server's output. 586 VOPRF setup phase: 588 Verifier() Prover(l) 589 ---------------------------------------------------------- 590 (k,GG,Y) = VerifiableSetup(l) 591 (GG,Y) 592 <------- 594 VOPRF evaluation phase: 596 Verifier(x,Y,aux) Prover(k) 597 ---------------------------------------------------------- 598 (r, M) = VerifiableBlind(x) 599 M 600 -------> 601 (Z,D) = VerifiableEvaluate(k,G,Y,M) 602 (Z,D) 603 <------- 604 N = VerifiableUnblind(r,G,Y,M,Z,D) 605 Output VerifiableFinalize(x,Y,N,aux) 607 4.3. Protocol correctness 609 Protocol correctness requires that, for any key k, input x, and (r, 610 M) = Blind(x), it must be true that: 612 Finalize(x, Unblind(r,M,Evaluate(k,M)), aux) 613 == H_2(H_2(DST, x .. F(k,x)), aux) 615 with overwhelming probability. Likewise, in the verifiable setting, 616 we require that: 618 Z = VerifiableEvaluate(k,G,Y,M) 619 VerifiableFinalize(x, Y, VerifiableUnblind(r,G,Y,M,Z), aux) 620 == H_2(H_2(DST, x .. F(k,x)), aux) 622 with overwhelming probability, where (r, M) = VerifiableBlind(x). In 623 other words, the inner H_2 invocation effectively derives a key, dk, 624 from the input data DST, x, N. The outer invocation derives the 625 output y by evaluating H_2 over dk and auxiliary data aux. 627 4.4. Domain separation 629 The Finalize procedure accepts optional auxiliary byte string input 630 (aux) as a means of modifying the PRF output. This parameter SHOULD 631 be used for domain separation in (V)OPRF the protocol. Specifically, 632 any system which has multiple (V)OPRF applications should use 633 separate aux values to to ensure finalized outputs are separate. 634 Guidance for constructing aux can be found in 635 [I-D.irtf-cfrg-hash-to-curve]; Section 3.1. 637 4.5. Instantiations of GG 639 As we remarked above, GG is a group with associated prime-order p. 640 While we choose to write operations in the setting where GG comes 641 equipped with an additive operation, we could also define the 642 operations in the multiplicative setting. In the multiplicative 643 setting we can choose GG to be a prime-order subgroup of a finite 644 field FF_p. For example, let p be some large prime (e.g. > 2048 645 bits) where p = 2q+1 for some other prime q. Then the subgroup of 646 squares of FF_p (elements u^2 where u is an element of FF_p) is 647 cyclic, and we can pick a generator of this subgroup by picking G 648 from FF_p (ignoring the identity element). 650 For practicality of the protocol, it is preferable to focus on the 651 cases where GG is an additive subgroup so that we can instantiate the 652 OPRF in the elliptic curve setting. This amounts to choosing GG to 653 be a prime-order subgroup of an elliptic curve over base field GF(p) 654 for prime p. There are also other settings where GG is a prime-order 655 subgroup of an elliptic curve over a base field of non-prime order, 656 these include the work of Ristretto [RISTRETTO] and Decaf [DECAF]. 658 We will use p > 0 generally for constructing the base field GF(p), 659 not just those where p is prime. To reiterate, we focus only on the 660 additive case, and so we focus only on the cases where GF(p) is 661 indeed the base field. 663 Unless otherwise stated, we will always assume that the generator G 664 that we use for the group GG is a fixed generator. This generator 665 should be available to both the client and the server ahead of the 666 protocol, or derived for each different group instantiation using a 667 fixed method. In the elliptic curve setting, we recommend using the 668 fixed generators that are given as part of the curve description. 670 4.6. OPRF algorithms 672 This section provides descriptions of the algorithms used in the 673 generalized protocols from Section 4.2.1. We describe the VOPRF 674 analogues for the protocols in Section 4.2.2 later in Section 4.7. 676 We note here that the blinding mechanism that we use can be modified 677 slightly with the opportunity for making performance gains in some 678 scenarios. We detail these modifications in Section Section 4.8. 680 4.6.1. Setup 682 Input: 684 l: Some suitable choice of prime length for instantiating a group 685 structure (e.g. as described in [NIST]). 687 Output: 689 k: A key chosen from {0,1}^l and interpreted as a scalar in [1,p-1]. 690 GG: A cyclic group with prime-order p of length l bits. 692 Steps: 694 1. Construct a group GG = GG(l) with prime-order p of length l bits 695 2. k <-$ GF(p) 696 3. Output (k,GG) 698 4.6.2. Blind 699 Input: 701 x: Binary string taken from {0,1}^*. 703 Output: 705 r: Random scalar in [1, p - 1]. 706 M: An element in GG. 708 Steps: 710 1. r <-$ GF(p) 711 2. M := rH_1(x) 712 3. Output (r, M) 714 4.6.3. Evaluate 716 Input: 718 k: A scalar value taken from [1,p-1]. 719 M: An element in GG. 721 Output: 723 Z: An element in GG. 725 Steps: 727 1. Z := kM 728 2. Output Z 730 4.6.4. Unblind 732 Input: 734 r: Random scalar in [1, p - 1]. 735 Z: An element in GG. 737 Output: 739 N: An element in GG. 741 Steps: 743 1. N := (r^(-1))Z 744 2. Output N 746 4.6.5. Finalize 748 Input: 750 x: Binary string taken from {0,1}^*. 751 N: An element in GG. 752 aux: Arbitrary auxiliary data (as bytes). 754 Output: 756 y: Random element in {0,1}^L. 758 Steps: 760 1. DST := "oprf_derive_output" 761 2. dk := H_2(DST, x .. N) 762 3. y := H_2(dk, aux) 763 4. Output y 765 4.7. VOPRF algorithms 767 We make modifications to the aforementioned algorithms in the VOPRF 768 setting. 770 4.7.1. VerifiableSetup 772 Input: 774 G: Public fixed generator of GG. 775 l: Some suitable choice of key-length (e.g. as described in [NIST]). 777 Output: 779 k: A key chosen from {0,1}^l and interpreted as a scalar in [1,p-1]. 780 GG: A cyclic group with prime-order p of length l bits. 781 Y: A group element in GG. 783 Steps: 785 1. (k,GG) <- Setup(l) 786 2. Y := kG 787 3. Output (k,GG,Y) 789 4.7.2. VerifiableBlind 790 Input: 792 x: V's PRF input. 794 Output: 796 r: Random scalar in [1, p - 1]. 797 M: An element in GG. 799 Steps: 801 1. r <-$ GF(p) 802 2. M := rH_1(x) 803 3. Output (r,M) 805 4.7.3. VerifiableEvaluate 807 Input: 809 k: A random scalar in [1,p-1]. 810 G: Public fixed generator of group GG. 811 Y: An element in GG. 812 M: An element in GG. 814 Output: 816 Z: An element in GG. 817 D: DLEQ proof that log_G(Y) == log_M(Z). 819 Steps: 821 1. Z := kM 822 2. Z <- hZ 823 3. D = DLEQ_Generate(k,G,Y,M,Z) 824 4. Output (Z, D) 826 4.7.4. VerifiableUnblind 827 Input: 829 r: Random scalar in [1, p - 1]. 830 G: Public fixed generator of group GG. 831 Y: An element in GG. 832 M: An element in GG. 833 Z: An element in GG. 834 D: DLEQ proof object. 836 Output: 838 N: An element in GG. 840 Steps: 842 1. if DLEQ_Verify(G,Y,M,Z,D) == false: output "error" 843 2. N := (r^(-1))Z 844 3. Output N 846 4.7.5. VerifiableFinalize 848 Input: 850 x: Binary string in {0,1}^*. 851 Y: An element in GG. 852 N: An element in GG, or "error". 853 aux: Arbitrary auxiliary data in {0,1}^*. 855 Output: 857 y: Random element in {0,1}^L, or "error" 859 Steps: 861 1. If N == "error", output "error". 862 2. DST := "voprf_derive_output" 863 3. dk := H_2(DST, x .. Y .. N) 864 4. y := H_2(dk, aux) 865 5. Output y 867 4.8. Efficiency gains with pre-processing and fixed-base blinding 869 In Section Section 4.6 we assume that the client-side blinding is 870 carried out directly on the output of H_1(x), i.e. computing rH_1(x) 871 for some r <-$ GF(p). In the [OPAQUE] draft, it is noted that it may 872 be more efficient to use additive blinding rather than multiplicative 873 if the client can preprocess some values. For example, a valid way 874 of computing additive blinding would be to instead compute H_1(x)+rG, 875 where G is the fixed generator for the group GG. 877 We refer to the 'multiplicative' blinding as variable-base blinding 878 (VBB), since the base of the blinding (H_1(x)) varies with each 879 instantiation. We refer to the additive blinding case as fixed-base 880 blinding (FBB) since the blinding is applied to the same generator 881 each time (when computing rG). 883 By pre-processing tables of blinded scalar multiplications for the 884 specific choice of G it is possible to gain a computational 885 advantage. Choosing one of these values rG (where r is the scalar 886 value that is used), then computing H_1(x)+rG is more efficient than 887 computing rH_1(x) (one addition against log_2(r)). Therefore, it may 888 be advantageous to define the OPRF and VOPRF protocols using additive 889 blinding rather than multiplicative blinding. In fact, the only 890 algorithms that need to change are Blind and Unblind (and similarly 891 for the VOPRF variants). 893 We define the FBB variants of the algorithms in Section 4.6 below 894 along with a new algorithm Preprocess that defines how preprocessing 895 is carried out. The equivalent algorithms for VOPRF are almost 896 identical and so we do not redefine them here. Notice that the only 897 computation that changes is for V, the necessary computation of P 898 does not change. 900 4.8.1. Preprocess 902 Input: 904 G: Public fixed generator of GG 906 Output: 908 r: Random scalar in [1, p-1] 909 rG: An element in GG. 910 rY: An element in GG. 912 Steps: 914 1. r <-$ GF(p) 915 2. Output (r, rG, rY) 917 4.8.2. Blind 918 Input: 920 x: Binary string in {0,1}^*. 921 rG: An element in GG. 923 Output: 925 M: An element in GG. 927 Steps: 929 1. M := H_1(x)+rG 930 2. Output M 932 4.8.3. Unblind 934 Input: 936 rY: An element in GG. 937 M: An element in GG. 938 Z: An element in GG. 940 Output: 942 N: An element in GG. 944 Steps: 946 1. N := Z-rY 947 2. Output N 949 Notice that Unblind computes (Z-rY) = k(H_1(x)+rG) - rkG = kH_1(x) by 950 the commutativity of scalar multiplication in GG. This is the same 951 output as in the original Unblind algorithm. 953 5. NIZK Discrete Logarithm Equality Proof 955 For the VOPRF protocol we require that V is able to verify that P has 956 used its private key k to evaluate the PRF. We can do this by 957 showing that the original commitment (G,Y) output by 958 VerifiableSetup(l) satisfies log_G(Y) == log_M(Z) where Z is the 959 output of VerifiableEvaluate(k,G,Y,M). 961 This may be used, for example, to ensure that P uses the same private 962 key for computing the VOPRF output and does not attempt to "tag" 963 individual verifiers with select keys. This proof must not reveal 964 the P's long-term private key to V. 966 Consequently, this allows extending the OPRF protocol with a (non- 967 interactive) discrete logarithm equality (DLEQ) algorithm built on a 968 Chaum-Pedersen [ChaumPedersen] proof. This proof is divided into two 969 procedures: DLEQ_Generate and DLEQ_Verify. These are specified 970 below. 972 5.1. DLEQ_Generate 974 Input: 976 k: Evaluator secret key. 977 G: Public fixed generator of GG. 978 Y: Evaluator public key (= kG). 979 M: An element in GG. 980 Z: An element in GG. 981 H_3: A hash function from GG to {0,1}^L, modeled as a random oracle. 983 Output: 985 D: DLEQ proof (c, s). 987 Steps: 989 1. r <-$ GF(p) 990 2. A := rG 991 3. B := rM 992 4. c <- H_3(G,Y,M,Z,A,B) (mod p) 993 5. s := (r - ck) (mod p) 994 6. Output D := (c, s) 996 We note here that it is essential that a different r value is used 997 for every invocation. If this is not done, then this may leak the 998 key k in a similar fashion as is possible in Schnorr or (EC)DSA 999 scenarios where fresh randomness is not used. 1001 5.2. DLEQ_Verify 1002 Input: 1004 G: Public fixed generator of GG. 1005 Y: Evaluator public key. 1006 M: An element in GG. 1007 Z: An element in GG. 1008 D: DLEQ proof (c, s). 1010 Output: 1012 True if log_G(Y) == log_M(Z), False otherwise. 1014 Steps: 1016 1. A' := (sG + cY) 1017 2. B' := (sM + cZ) 1018 3. c' <- H_3(G,Y,M,Z,A',B') (mod p) 1019 4. Output c == c' (mod p) 1021 6. Batched VOPRF evaluation 1023 Common applications (e.g. [PrivacyPass]) require V to obtain 1024 multiple PRF evaluations from P. In the VOPRF case, this would 1025 naively require running multiple protocol invocations. This is 1026 costly, both in terms of computation and communication. To get 1027 around this, applications can use a 'batching' procedure for 1028 generating and verifying DLEQ proofs for a finite number of PRF 1029 evaluation pairs (Mi,Zi). For n PRF evaluations: 1031 o Proof generation is slightly more expensive from 2n modular 1032 exponentiations to 2n+2. 1034 o Proof verification is much more efficient, from 4n modular 1035 exponentiations to 2n+4. 1037 o Communications falls from 2n to 2 group elements. 1039 Since P is the VOPRF server, it may be able to tolerate a slight 1040 increase in proof generation complexity for much more efficient 1041 communication and proof verification. 1043 In this section, we describe algorithms for batching the DLEQ 1044 generation and verification procedure. For these algorithms we 1045 require two additional hash functions H_4: GG^(2n+2) -> {0,1}^a, and 1046 H_5: {0,1}^a x ZZ^3 -> {0,1}^b (both modeled as random oracles). 1048 We can instantiate the random oracle function H_4 using the same hash 1049 function that is used for H_3 previously. For H_5, we can also use a 1050 similar instantiation, or we can use a variable-length output 1051 generator. For example, for groups with an order of 256-bit, valid 1052 instantiations include functions such as SHAKE-256 [SHAKE] or HKDF- 1053 Expand-SHA256 [RFC5869]. This is preferable in situations where we 1054 may require outputs that are larger than 512 bits in length, for 1055 example. 1057 6.1. Batched_DLEQ_Generate 1059 Input: 1061 k: Evaluator secret key. 1062 G: Public fixed generator of group GG (with order p). 1063 Y: Evaluator public key (= kG). 1064 n: Number of PRF evaluations. 1065 [ Mi ]: An array of points in GG of length n. 1066 [ Zi ]: An array of points in GG of length n. 1067 H_4: A random oracle hash function from GG^(2n+2) to {0,1}^a. 1068 H_5: A random oracle hash function from {0,1}^a x ZZ^2 to {0,1}^b. 1069 label: An integer label value for the splitting the domain of H_5 1071 Output: 1073 D: DLEQ proof (c, s). 1075 Steps: 1077 1. seed <- H_4(G,Y,[Mi,Zi])) 1078 2. i' := i 1079 3. for i in [m]: 1080 1. di <- H_5(seed,i',info) 1081 2. if di > p: 1082 1. i' = i'+1 1083 2. i = i-1 // decrement and try again 1084 3. continue 1085 4. c1,...,cn := (int)d1,...,(int)dn 1086 5. M := c1M1 + ... + cnMn 1087 6. Z := c1Z1 + ... + cnZn 1088 7. Output DLEQ_Generate(k,G,Y,M,Z) 1090 6.2. DLEQ_Batched_Verify 1091 Input: 1093 G: Public fixed generator of group GG (with order p). 1094 Y: Evaluator public key. 1095 [ Mi ]: An array of points in GG of length n. 1096 [ Zi ]: An array of points in GG of length n. 1097 D: DLEQ proof (c, s). 1099 Output: 1101 True if log_G(Y) == log_(Mi)(Zi) for each i in 1...n, False otherwise. 1103 Steps: 1105 1. seed <- H_4(G,Y,[Mi,Zi])) 1106 2. i' := i 1107 3. for i in [m]: 1108 1. di <- H_5(seed,i',info) 1109 2. if di > p: 1110 1. i' = i'+1 1111 2. i = i-1 // decrement and try again 1112 3. continue 1113 4. c1,...,cn := (int)d1,...,(int)dn 1114 5. M := c1M1 + ... + cnMn 1115 6. Z := c1Z1 + ... + cnZn 1116 7. Output DLEQ_Verify(G,Y,M,Z,D) 1118 6.3. Modified algorithms 1120 The VOPRF protocol from Section Section 4 changes to allow specifying 1121 multiple blinded PRF inputs "[ Mi ]" for i in 1...n. P computes the 1122 array "[ Zi]" and replaces DLEQ_Generate with DLEQ_Batched_Generate 1123 over these arrays. Concretely, we modify the following algorithms: 1125 6.3.1. VerifiableBlind 1126 Input: 1128 [ xi ]: An array of m binary strings taken from {0,1}^*. 1130 Output: 1132 [ ri ]: An array of m random scalars in [1, p - 1]. 1133 [ Mi ]: An array of elements in GG. 1135 Steps: 1137 1. groupElems = [] 1138 2. blinds = [] 1139 3. for i in [m]: 1140 1. ri <-$ GF(p) 1141 2. Mi := rH_1(xi) 1142 3. blinds.push(ri) 1143 4. groupElems.push(Mi) 1144 4. Output (blinds, groupElems) 1146 6.3.2. VerifiableEvaluate 1148 Input: 1150 k: Evaluator secret key. 1151 G: Public fixed generator of group GG. 1152 Y: Evaluator public key (= kG). 1153 [ Mi ]: An array of m elements in GG. 1155 Output: 1157 [ Zi ]: An array of m elements in GG. 1158 D: Batched DLEQ proof object. 1160 Steps: 1162 1. outputElems = [] 1163 2. for i in [m]: 1164 1. Zi := kMi 1165 2. outputElems.push(Zi) 1166 3. D = Batched_DLEQ_Generate(k,G,Y,[ Mi ],outputElems) 1167 4. Output (outputElems, D) 1169 6.3.3. VerifiableUnblind 1170 Input: 1172 G: Public fixed generator of group GG. 1173 Y: Evaluator public key (= kG). 1174 [ Mi ]: An array of m elements in GG. 1175 [ Zi ]: An array of m elements in GG. 1176 [ ri ]: An array of m random scalars in [1, p - 1]. 1177 D: Batched DLEQ proof object. 1179 Output: 1181 [ Ni ]: An array of n elements in GG. 1183 Steps: 1185 1. if !Batch_DLEQ_Verify(G,Y,[ Mi ],[ Zi ],D): Output "error" 1186 2. N = [] 1187 3. for i in [m]: 1188 1. Ni := (ri^(-1))Zi 1189 2. N.push(Ni) 1190 4. Output N 1192 6.3.4. VerifiableFinalize 1194 The description of this algorithm does not change in the batched 1195 case. Instead, the protocol description in Section 4.2.2 changes so 1196 that "VerifiableFinalize" runs once for each of the outputs of 1197 "VerifiableUnblind". 1199 6.4. Random oracle instantiations for proofs 1201 We can instantiate the random oracle function H_4 using the same hash 1202 function that is used for H_1,H_2,H_3. For H_5, we can also use a 1203 similar instantiation, or we can use a variable-length output 1204 generator. For example, for groups with an order of 256-bit, valid 1205 instantiations include functions such as SHAKE-256 [SHAKE] or HKDF- 1206 Expand-SHA256 [RFC5869]. 1208 Input: 1210 [ ri ]: Random scalars in [1, p - 1]. 1211 G: Public fixed generator of group GG. 1212 Y: Evaluator public key. 1213 [ Mi ]: Blinded elements of GG. 1214 [ Zi ]: Server-generated elements in GG. 1215 D: A batched DLEQ proof object. 1217 Output: 1219 N: element in GG, or "error". 1221 Steps: 1223 1. N := (r^(-1))Z 1224 2. If 1 = DLEQ_Batched_Verify(G,Y,[ Mi ],[ Zi ],D), output N 1225 3. Output "error" 1227 7. Supported ciphersuites 1229 This section specifies supported VOPRF group and hash function 1230 instantiations. We only provide ciphersuites in the EC setting as 1231 these provide the most efficient way of instantiating the OPRF. Our 1232 instantiation includes considerations for providing the DLEQ proofs 1233 that make the instantiation a VOPRF. Supporting OPRF operations 1234 alone can be allowed by simply dropping the relevant components. For 1235 reasons that are detailed in Section 8.1, we only consider 1236 ciphersuites that provide strictly greater than 128 bits of security 1237 [NIST]. 1239 7.1. OPRF-curve448-HKDF-SHA512-ELL2-RO: 1241 o GG: curve448 [RFC7748] 1243 o H_1: curve448-SHA512-ELL2-RO [I-D.irtf-cfrg-hash-to-curve] 1245 * hash-to-curve DST: "RFCXXXX-OPRF-curve448-SHA512-ELL2-RO-" 1247 o H_2: HMAC_SHA512 [RFC2104] 1249 o H_3: SHA512 1251 7.2. OPRF-P384-HKDF-SHA512-SSWU-RO: 1253 o GG: secp384r1 [SEC2] 1255 o H_1: P384-SHA512-SSWU-RO [I-D.irtf-cfrg-hash-to-curve] 1256 * hash-to-curve DST: "RFCXXXX-OPRF-P384-SHA512-SSWU-RO-" 1258 o H_2: HMAC_SHA512 [RFC2104] 1260 o H_3: SHA512 1262 7.3. OPRF-P521-HKDF-SHA512-SSWU-RO: 1264 o GG: secp521r1 [SEC2] 1266 o H_1: P521-SHA512-SSWU-RO [I-D.irtf-cfrg-hash-to-curve] 1268 * hash-to-curve DST: "RFCXXXX-OPRF-P521-SHA512-SSWU-RO-" 1270 o H_2: HMAC_SHA512 [RFC2104] 1272 o H_3: SHA512 1274 7.4. VOPRF-curve448-HKDF-SHA512-ELL2-RO: 1276 o GG: curve448 [RFC7748] 1278 o H_1: curve448-SHA512-ELL2-RO [I-D.irtf-cfrg-hash-to-curve] 1280 * hash-to-curve DST: "RFCXXXX-VOPRF-curve448-SHA512-ELL2-RO-" 1282 o H_2: HMAC_SHA512 [RFC2104] 1284 o H_3: SHA512 1286 o H_4: SHA512 1288 o H_5: HKDF-Expand-SHA512 1290 7.5. VOPRF-P384-HKDF-SHA512-SSWU-RO: 1292 o GG: secp384r1 [SEC2] 1294 o H_1: P384-SHA512-SSWU-RO [I-D.irtf-cfrg-hash-to-curve] 1296 * hash-to-curve DST: "RFCXXXX-VOPRF-P384-SHA512-SSWU-RO-" 1298 o H_2: HMAC_SHA512 [RFC2104] 1300 o H_3: SHA512 1302 o H_4: SHA512 1303 o H_5: HKDF-Expand-SHA512 1305 7.6. VOPRF-P521-HKDF-SHA512-SSWU-RO: 1307 o GG: secp521r1 [SEC2] 1309 o H_1: P521-SHA512-SSWU-RO [I-D.irtf-cfrg-hash-to-curve] 1311 * hash-to-curve DST: "RFCXXXX-VOPRF-P521-SHA512-SSWU-RO-" 1313 o H_2: HMAC_SHA512 [RFC2104] 1315 o H_3: SHA512 1317 o H_4: SHA512 1319 o H_5: HKDF-Expand-SHA512 1321 We remark that the 'hash-to-curve DST' field is necessary for domain 1322 separation of the hash-to-curve functionality. 1324 8. Security Considerations 1326 This section discusses the cryptographic security of our protocol, 1327 along with some suggestions and trade-offs that arise from the 1328 implementation of the implementation of an OPRF. 1330 8.1. Cryptographic security 1332 We discuss the cryptographic security of the OPRF protocol from 1333 Section 4, relative to the necessary cryptographic assumptions that 1334 need to be made. 1336 8.1.1. Computational hardness assumptions 1338 Each assumption states that the problems specified below are 1339 computationally difficult to solve in relation to sp (the security 1340 parameter). In other words, the probability that an adversary has in 1341 solving the problem is bounded by a function negl(sp), where negl(sp) 1342 < 1/f(sp) for all polynomial functions f(). 1344 Let GG = GG(sp) be a group with prime-order p, and let FFp be the 1345 finite field of order p. 1347 8.1.1.1. Discrete-log (DL) problem 1349 Given G, a generator of GG, and H = hG for some h in FFp; output h. 1351 8.1.1.2. Decisional Diffie-Hellman (DDH) problem 1353 Sample a uniformly random bit d in {0,1}. Given (G, aG, bG, C), 1354 where: 1356 o G is a generator of GG; 1358 o a,b are elements of FFp; 1360 o if d == 0: C = abG; else: C is sampled uniformly GG(sp). 1362 Output d' == d. 1364 8.1.2. Protocol security 1366 As aforementioned, our OPRF and VOPRF constructions are based heavily 1367 on the 2HashDH-NIZK construction given in [JKK14], except for 1368 considerations on how we instantiate the NIZK DLEQ proof system. 1369 This means that the cryptographic security of our construction is 1370 also based on the assumption that the One-More Gap DH is 1371 computationally difficult to solve. 1373 The (N,Q)-One-More Gap DH (OMDH) problem asks the following. 1375 Given: 1376 - G, kG, G_1, ... , G_N where G, G1, ... GN are elements od GG; 1377 - oracle access to an OPRF functionality using the key k; 1378 - oracle access to DDH solvers. 1380 Find Q+1 pairs of the form below: 1382 (G_{j_s}, kG_{j_s}) 1384 where the following conditions hold: 1385 - s is a number between 1 and Q+1; 1386 - j_s is a number between 1 and N for each s; 1387 - Q is the number of allowed queries. 1389 The original paper [JKK14] gives a security proof that the 2HashDH- 1390 NIZK construction satisfies the security guarantees of a VOPRF 1391 protocol Section 3.1 under the OMDH assumption in the universal 1392 composability (UC) security model. Without the NIZK proof system, 1393 the protocol instantiates an OPRF protocol only. See the paper for 1394 further details. 1396 8.1.3. Q-strong-DH oracle 1398 A side-effect of our OPRF design is that it allows instantiation of a 1399 oracle for constructing Q-strong-DH (Q-sDH) samples. The Q-Strong-DH 1400 problem asks the following. 1402 Given G1, G2, h*G2, (h^2)*G2, ..., (h^Q)*G2; for G1 and G2 1403 generators of GG. 1405 Output ( (1/(k+c))*G1, c ) where c is an element of FFp 1407 The assumption that this problem is hard was first introduced in 1408 [BB04]. Since then, there have been a number of cryptanalytic 1409 studies that have reduced the security of the assumption below that 1410 implied by the group instantiation (for example, [BG04] and 1411 [Cheon06]). In summary, the attacks reduce the security of the group 1412 instantiation by log_2(Q) bits. 1414 As an example, suppose that a group instantiation is used that 1415 provides 128 bits of security. Then an adversary with access to a 1416 Q-sDH oracle and makes Q=2^20 queries can reduce the security of the 1417 instantiation by log_2(2^20) = 20 bits. 1419 Notice that it is easy to instantiate a Q-sDH oracle using the OPRF 1420 functionality that we provide. A client can just submit sequential 1421 queries of the form (G, kG, (k^2)G, ..., (k^(Q-1))G), where each 1422 query is the output of the previous interaction. This means that any 1423 client that submit Q queries to the OPRF can use the aforementioned 1424 attacks to reduce security of the group instantiation by log_2(Q) 1425 bits. 1427 Recall that from a malicious client's perspective, the adversary wins 1428 if they can distinguish the OPRF interaction from a protocol that 1429 computes the ideal functionality provided by the PRF. 1431 8.1.4. Implications for ciphersuite choices 1433 The OPRF instantiations that we recommend in this document are 1434 informed by the cryptanalytic discussion above. In particular, 1435 choosing elliptic curves configurations that describe 128-bit group 1436 instantiations would appear to in fact instantiate an OPRF with 1437 128-log_2(Q) bits of security. 1439 While it would require an informed and persistent attacker to launch 1440 a highly expensive attack to reduce security to anything much below 1441 100 bits of security, we see this possibility as something that may 1442 result in problems in the future. Therefore, all of our ciphersuites 1443 in Section 7 come with a minimum group instantiation corresponding to 1444 196 bits of security. This would require an adversary to launch a 1445 minimum of Q = 2^(68) queries to reduce security to 128 bits using 1446 the Q-sDH attacks. As a result, it appears prohibitively expensive 1447 to launch credible attacks on these parameters with our current 1448 understanding of the attack surface. 1450 8.2. Hashing to curve 1452 A critical aspect of implementing this protocol using elliptic curve 1453 group instantiations is a method of instantiating the function H1, 1454 that maps inputs to group elements. In the elliptic curve setting, 1455 this must be a deterministic function that maps arbitrary inputs x 1456 (as bytes) to uniformly chosen points in the curve. 1458 In the security proof of the construction H1 is modeled as a random 1459 oracle. This implies that any instantiation of H1 must be pre-image 1460 and collision resistant. In Section 7 we give instantiations of this 1461 functionality based on the functions described in 1462 [I-D.irtf-cfrg-hash-to-curve]. Consequently, any OPRF implementation 1463 must adhere to the implementation and security considerations 1464 discussed in [I-D.irtf-cfrg-hash-to-curve] when instantiating the 1465 function H1. 1467 8.3. Timing Leaks 1469 To ensure no information is leaked during protocol execution, all 1470 operations that use secret data MUST be constant time. Operations 1471 that SHOULD be constant time include: H_1() (hashing arbitrary 1472 strings to curves) and DLEQ_Generate(). As mentioned previously, 1473 [I-D.irtf-cfrg-hash-to-curve] describes various algorithms for 1474 constant-time implementations of H_1. 1476 8.4. User segregation 1478 The aim of the OPRF functionality is to allow clients receive 1479 pseudorandom function evaluations on their own inputs, without 1480 compromising their own privacy with respect to the server. In many 1481 applications (for example, [PrivacyPass]) the client may choose to 1482 reveal their original input, after an invocation of the OPRF 1483 protocol, along with their OPRF output. This can prove to the server 1484 that it has received a valid OPRF output in the past. Since the 1485 server does not reveal learn anything about the OPRF output, it 1486 should not be able to link the client to any previous protocol 1487 instantiation. 1489 Consider a malicious server that manages to segregate the user base 1490 into different sets. Then this reduces the effective privacy of all 1491 of the clients involved, since the client above belongs to a smaller 1492 set of users than previously hoped. In general, if the user-base of 1493 the OPRF functionality is quite small, then the obliviousness of 1494 clients is limited. That is, smaller user-bases mean that the server 1495 is able to identify client's with higher certainty. 1497 In summary, an OPRF instantiation effectively comes with an 1498 additional privacy parameter pp. If all clients of the OPRF make one 1499 query and then subsequently reveal their OPRF input afterwards, then 1500 the server should be link the revealed input to a protocol 1501 instantiation with probability 1/pp. 1503 Below, we provide a few techniques that could be used to abuse 1504 client-privacy in the OPRF construction by segregating the user-base, 1505 along with some mitigations. 1507 8.4.1. Linkage patterns 1509 If the server is able to ascertain patterns of usage for some clients 1510 - such as timings associated with usage - then the effective privacy 1511 of the clients is reduced to the number of users that fit each usage 1512 pattern. Along with early registration patterns, where early 1513 adopters initially have less privacy due to a low number of 1514 registered users, such problems are inherent to any anonymity- 1515 preserving system. 1517 8.4.2. Evaluation on multiple keys 1519 Such an attack consists of the server evaluating the OPRF on multiple 1520 different keys related to the number of clients that use the 1521 functionality. As an extreme, the server could evaluate the OPRF 1522 with a different key for each client. If the client then revealed 1523 their hidden information at a later date then the server would 1524 immediately know which initial request they launched. 1526 The VOPRF variant helps mitigate this attack since each server 1527 evaluation can be bound to a known public key. However, there are 1528 still ways that the VOPRF construction can be abused. In particular: 1530 o If the server successfully provisions a large number of keys that 1531 are trusted by clients, then the server can divide the user-base 1532 by the number of keys that are currently in use. As such, clients 1533 should only trust a small number (2 or 3 ideally) of server keys 1534 at any one time. Additionally, a tamper-proof audit log system 1535 akin to existing work on Key Transparency [keytrans] could be used 1536 to ensure that a server is abiding by the key policy. This would 1537 force the server to be held accountable for their key updates, and 1538 thus higher key update frequencies can be better managed on the 1539 client-side. 1541 o If the server rotates their key frequently, then this may result 1542 in client's holding out-of-date information from a past 1543 interaction. Such information can also be used to segregate the 1544 user-base based on the last time that they accessed the OPRF 1545 protocol. Similarly to the above, server key rotations must be 1546 kept to relatively infrequent intervals (such as once per month). 1547 This will prevent too many clients from being segregated into 1548 different groups related to the time that they accessed the 1549 functionality. There are viable reasons for rotating the server 1550 key (for protecting against malicious clients) that we address 1551 more closely in Section 8.5. 1553 Since key provisioning requires careful handling, all public keys 1554 should be accessible from a client-trusted registry with a way of 1555 auditing the history of key updates. We also recommend that public 1556 keys have a corresponding expiry date that clients can use to prevent 1557 the server from using keys that have been provisioned for a long 1558 period of time. 1560 8.5. Key rotation 1562 Since the server's key is critical to security, the longer it is 1563 exposed by performing (V)OPRF operations on client inputs, the longer 1564 it is possible that the key can be compromised. For instance, if the 1565 key is kept in production for a long period of time, then this may 1566 grant the client the ability to hoard large numbers of tokens. This 1567 has negative impacts for some of the applications that we consider in 1568 Section 9. As another example, if the key is kept in circulation for 1569 a long period of time, then it also allows the clients to make enough 1570 queries to launch more powerful variants of the Q-sDH attacks from 1571 Section 8.1.3. 1573 To combat attacks of this nature, regular key rotation should be 1574 employed on the server-side. A suitable key-cycle for a key used to 1575 compute (V)OPRF evaluations would be between one week and six months. 1577 As we discussed in Section 8.4.2, key rotation cycles that are too 1578 frequent (in the order of days) can lead to large segregation of the 1579 wider user base. As such, the length of the key cycles represent a 1580 trade-off between greater server key security (for shorter cycles), 1581 and better client privacy (for longer cycles). In situations where 1582 client privacy is paramount, longer key cycles should be employed. 1583 Otherwise, shorter key cycles can be managed if the server uses a Key 1584 Transparency-type system [keytrans]; this allows clients to publicly 1585 audit their rotations. 1587 9. Applications 1589 This section describes various applications of the (V)OPRF protocol. 1591 9.1. Privacy Pass 1593 This VOPRF protocol is used by the Privacy Pass system [PrivacyPass] 1594 to help Tor users bypass CAPTCHA challenges. Their system works as 1595 follows. Client C connects - through Tor - to an edge server E 1596 serving content. Upon receipt, E serves a CAPTCHA to C, who then 1597 solves the CAPTCHA and supplies, in response, n blinded points. E 1598 verifies the CAPTCHA response and, if valid, signs (at most) n 1599 blinded points, which are then returned to C along with a batched 1600 DLEQ proof. C stores the tokens if the batched proof verifies 1601 correctly. When C attempts to connect to E again and is prompted 1602 with a CAPTCHA, C uses one of the unblinded and signed points, or 1603 tokens, to derive a shared symmetric key sk used to MAC the CAPTCHA 1604 challenge. C sends the CAPTCHA, MAC, and token input x to E, who can 1605 use x to derive sk and verify the CAPTCHA MAC. Thus, each token is 1606 used at most once by the system. 1608 The Privacy Pass implementation uses the P-256 instantiation of the 1609 VOPRF protocol. For more details, see [DGSTV18]. 1611 9.2. Private Password Checker 1613 In this application, let D be a collection of plaintext passwords 1614 obtained by prover P. For each password p in D, P computes 1615 VerifiableEvaluate on H_1(p), where H_1 is as described above, and 1616 stores the result in a separate collection D'. P then publishes D' 1617 with Y, its public key. If a client C wishes to query D' for a 1618 password p', it runs the VOPRF protocol using p as input x to obtain 1619 output y. By construction, y will be the OPRF evaluation of p hashed 1620 onto the curve. C can then search D' for y to determine if there is 1621 a match. 1623 Concrete examples of important applications in the password domain 1624 include: 1626 o password-protected storage [JKK14], [JKKX16]; 1628 o perfectly-hiding password management [SJKS17]; 1630 o password-protected secret-sharing [JKKX17]. 1632 9.2.1. Parameter Commitments 1634 For some applications, it may be desirable for P to bind tokens to 1635 certain parameters, e.g., protocol versions, ciphersuites, etc. To 1636 accomplish this, P should use a distinct scalar for each parameter 1637 combination. Upon redemption of a token T from V, P can later verify 1638 that T was generated using the scalar associated with the 1639 corresponding parameters. 1641 10. Contributors 1643 o Alex Davidson (alex.davidson92@gmail.com) 1645 o Nick Sullivan (nick@cloudflare.com) 1647 o Chris Wood (cawood@apple.com) 1649 o Eli-Shaoul Khedouri (eli@intuitionmachines.com) 1651 11. Acknowledgements 1653 This document resulted from the work of the Privacy Pass team 1654 [PrivacyPass]. The authors would also like to acknowledge the 1655 helpful conversations with Hugo Krawczyk. Eli-Shaoul Khedouri 1656 provided additional review and comments on key consistency. 1658 12. References 1660 12.1. Normative References 1662 [BB04] "Short Signatures Without Random Oracles", 1663 . 1665 [BG04] "The Static Diffie-Hellman Problem", 1666 . 1668 [ChaumBlindSignature] 1669 "Blind Signatures for Untraceable Payments", 1670 . 1673 [ChaumPedersen] 1674 "Wallet Databases with Observers", 1675 . 1677 [Cheon06] "Security Analysis of the Strong Diffie-Hellman Problem", 1678 . 1681 [DECAF] "Decaf, Eliminating cofactors through point compression", 1682 . 1684 [DGSTV18] "Privacy Pass, Bypassing Internet Challenges Anonymously", 1685 . 1688 [I-D.irtf-cfrg-hash-to-curve] 1689 Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R., and 1690 C. Wood, "Hashing to Elliptic Curves", draft-irtf-cfrg- 1691 hash-to-curve-05 (work in progress), November 2019. 1693 [JKK14] "Round-Optimal Password-Protected Secret Sharing and 1694 T-PAKE in the Password-Only model", 1695 . 1697 [JKKX16] "Highly-Efficient and Composable Password-Protected Secret 1698 Sharing (Or, How to Protect Your Bitcoin Wallet Online)", 1699 . 1701 [JKKX17] "TOPPSS: Cost-minimal Password-Protected Secret Sharing 1702 based on Threshold OPRF", 1703 . 1705 [keytrans] 1706 "Security Through Transparency", 1707 . 1710 [NIST] "Keylength - NIST Report on Cryptographic Key Length and 1711 Cryptoperiod (2016)", . 1713 [OPAQUE] "The OPAQUE Asymmetric PAKE Protocol", 1714 . 1717 [PrivacyPass] 1718 "Privacy Pass", 1719 . 1721 [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 1722 Hashing for Message Authentication", RFC 2104, 1723 DOI 10.17487/RFC2104, February 1997, 1724 . 1726 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1727 Requirement Levels", BCP 14, RFC 2119, 1728 DOI 10.17487/RFC2119, March 1997, 1729 . 1731 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 1732 Key Derivation Function (HKDF)", RFC 5869, 1733 DOI 10.17487/RFC5869, May 2010, 1734 . 1736 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 1737 for Security", RFC 7748, DOI 10.17487/RFC7748, January 1738 2016, . 1740 [RISTRETTO] 1741 "The ristretto255 Group", . 1744 [SEC2] Standards for Efficient Cryptography Group (SECG), ., "SEC 1745 2: Recommended Elliptic Curve Domain Parameters", 1746 . 1748 [SHAKE] "SHA-3 Standard, Permutation-Based Hash and Extendable- 1749 Output Functions", . 1753 [SJKS17] "SPHINX, A Password Store that Perfectly Hides from 1754 Itself", . 1756 12.2. URIs 1758 [1] https://tools.ietf.org/html/draft-irtf-cfrg-voprf-03 1760 [2] https://tools.ietf.org/html/draft-irtf-cfrg-voprf-02 1762 [3] https://tools.ietf.org/html/draft-irtf-cfrg-voprf-01 1764 Authors' Addresses 1766 Alex Davidson 1767 Cloudflare 1768 County Hall 1769 London, SE1 7GP 1770 United Kingdom 1772 Email: adavidson@cloudflare.com 1773 Nick Sullivan 1774 Cloudflare 1775 101 Townsend St 1776 San Francisco 1777 United States of America 1779 Email: nick@cloudflare.com 1781 Christopher A. Wood 1782 Apple Inc. 1783 One Apple Park Way 1784 Cupertino, California 95014 1785 United States of America 1787 Email: cawood@apple.com