idnits 2.17.1 draft-irtf-cfrg-voprf-02.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.) ** There are 5 instances of too long lines in the document, the longest one being 9 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 04, 2019) is 1634 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 1773 == Outdated reference: A later version (-16) exists of draft-irtf-cfrg-hash-to-curve-05 == Outdated reference: A later version (-06) exists of draft-krawczyk-cfrg-opaque-02 Summary: 2 errors (**), 0 flaws (~~), 3 warnings (==), 2 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: May 7, 2020 C. Wood 6 Apple Inc. 7 November 04, 2019 9 Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups 10 draft-irtf-cfrg-voprf-02 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 May 7, 2020. 43 Copyright Notice 45 Copyright (c) 2019 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 . . . . . . . . . . . . . . . . . . . . . . . . 4 61 1.1. Change log . . . . . . . . . . . . . . . . . . . . . . . 5 62 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 5 63 1.3. Requirements . . . . . . . . . . . . . . . . . . . . . . 6 64 2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 6 65 3. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 6 66 3.1. Security Properties . . . . . . . . . . . . . . . . . . . 6 67 4. OPRF Protocol . . . . . . . . . . . . . . . . . . . . . . . . 7 68 4.1. Design . . . . . . . . . . . . . . . . . . . . . . . . . 8 69 4.2. Protocol functionality . . . . . . . . . . . . . . . . . 9 70 4.2.1. Generalized OPRF . . . . . . . . . . . . . . . . . . 10 71 4.2.2. Generalized VOPRF . . . . . . . . . . . . . . . . . . 11 72 4.3. Protocol correctness . . . . . . . . . . . . . . . . . . 11 73 4.4. Instantiations of GG . . . . . . . . . . . . . . . . . . 11 74 4.5. OPRF algorithms . . . . . . . . . . . . . . . . . . . . . 12 75 4.5.1. OPRF_Setup . . . . . . . . . . . . . . . . . . . . . 12 76 4.5.2. OPRF_Blind . . . . . . . . . . . . . . . . . . . . . 13 77 4.5.3. OPRF_Eval . . . . . . . . . . . . . . . . . . . . . . 13 78 4.5.4. OPRF_Unblind . . . . . . . . . . . . . . . . . . . . 14 79 4.5.5. OPRF_Finalize . . . . . . . . . . . . . . . . . . . . 14 80 4.6. VOPRF algorithms . . . . . . . . . . . . . . . . . . . . 15 81 4.6.1. VOPRF_Setup . . . . . . . . . . . . . . . . . . . . . 15 82 4.6.2. VOPRF_Blind . . . . . . . . . . . . . . . . . . . . . 15 83 4.6.3. VOPRF_Eval . . . . . . . . . . . . . . . . . . . . . 16 84 4.6.4. VOPRF_Unblind . . . . . . . . . . . . . . . . . . . . 16 85 4.6.5. VOPRF_Finalize . . . . . . . . . . . . . . . . . . . 17 86 4.7. Efficiency gains with pre-processing and fixed-base 87 blinding . . . . . . . . . . . . . . . . . . . . . . . . 17 88 4.7.1. OPRF_Preprocess . . . . . . . . . . . . . . . . . . . 18 89 4.7.2. OPRF_Blind . . . . . . . . . . . . . . . . . . . . . 18 90 4.7.3. OPRF_Unblind . . . . . . . . . . . . . . . . . . . . 19 91 4.8. Recommended protocol integration . . . . . . . . . . . . 19 92 4.8.1. Setup phase . . . . . . . . . . . . . . . . . . . . . 20 93 4.8.2. Evaluation phase . . . . . . . . . . . . . . . . . . 21 94 4.8.3. Additional requirements . . . . . . . . . . . . . . . 21 95 5. NIZK Discrete Logarithm Equality Proof . . . . . . . . . . . 21 96 5.1. DLEQ_Generate . . . . . . . . . . . . . . . . . . . . . . 22 97 5.2. DLEQ_Verify . . . . . . . . . . . . . . . . . . . . . . . 22 98 5.3. Batched VOPRF evaluation . . . . . . . . . . . . . . . . 23 99 5.3.1. Batched_DLEQ_Generate . . . . . . . . . . . . . . . . 24 100 5.3.2. DLEQ_Batched_Verify . . . . . . . . . . . . . . . . . 24 101 5.3.3. Modified protocol execution . . . . . . . . . . . . . 25 102 5.3.4. Random oracle instantiations for proofs . . . . . . . 25 103 6. Supported ciphersuites . . . . . . . . . . . . . . . . . . . 26 104 6.1. VOPRF-curve448-HKDF-SHA512-ELL2: . . . . . . . . . . . . 26 105 6.2. VOPRF-p384-HKDF-SHA512-ICART: . . . . . . . . . . . . . . 27 106 6.3. VOPRF-p521-HKDF-SHA512-SSWU: . . . . . . . . . . . . . . 27 107 7. Recommended protocol integration . . . . . . . . . . . . . . 27 108 7.1. Setup phase . . . . . . . . . . . . . . . . . . . . . . . 28 109 7.2. Evaluation phase . . . . . . . . . . . . . . . . . . . . 29 110 7.3. Client-specific considerations . . . . . . . . . . . . . 29 111 7.3.1. Inputs . . . . . . . . . . . . . . . . . . . . . . . 29 112 7.3.2. Output . . . . . . . . . . . . . . . . . . . . . . . 29 113 7.3.3. Messages . . . . . . . . . . . . . . . . . . . . . . 29 114 7.4. Server-specific considerations . . . . . . . . . . . . . 29 115 7.4.1. Setup . . . . . . . . . . . . . . . . . . . . . . . . 29 116 7.4.2. Inputs . . . . . . . . . . . . . . . . . . . . . . . 30 117 7.4.3. Outputs . . . . . . . . . . . . . . . . . . . . . . . 30 118 7.4.4. Messages . . . . . . . . . . . . . . . . . . . . . . 31 119 8. Security Considerations . . . . . . . . . . . . . . . . . . . 31 120 8.1. Cryptographic security . . . . . . . . . . . . . . . . . 31 121 8.1.1. Computational hardness assumptions . . . . . . . . . 31 122 8.1.2. Protocol security . . . . . . . . . . . . . . . . . . 32 123 8.1.3. Q-strong-DH oracle . . . . . . . . . . . . . . . . . 32 124 8.1.4. Implications for ciphersuite choices . . . . . . . . 33 125 8.2. Hashing to curve . . . . . . . . . . . . . . . . . . . . 33 126 8.3. Timing Leaks . . . . . . . . . . . . . . . . . . . . . . 34 127 8.4. User segregation . . . . . . . . . . . . . . . . . . . . 34 128 8.4.1. Linkage patterns . . . . . . . . . . . . . . . . . . 35 129 8.4.2. Evaluation on multiple keys . . . . . . . . . . . . . 35 130 8.5. Key rotation . . . . . . . . . . . . . . . . . . . . . . 36 131 9. Applications . . . . . . . . . . . . . . . . . . . . . . . . 36 132 9.1. Privacy Pass . . . . . . . . . . . . . . . . . . . . . . 36 133 9.2. Private Password Checker . . . . . . . . . . . . . . . . 37 134 9.2.1. Parameter Commitments . . . . . . . . . . . . . . . . 37 135 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 37 136 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 38 137 11.1. Normative References . . . . . . . . . . . . . . . . . . 38 138 11.2. URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 40 139 Appendix A. Test Vectors . . . . . . . . . . . . . . . . . . . . 40 140 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 40 142 1. Introduction 144 A pseudorandom function (PRF) F(k, x) is an efficiently computable 145 function with secret key k on input x. Roughly, F is pseudorandom if 146 the output y = F(k, x) is indistinguishable from uniformly sampling 147 any element in F's range for random choice of k. An oblivious PRF 148 (OPRF) is a two-party protocol between a prover P and verifier V 149 where P holds a PRF key k and V holds some input x. The protocol 150 allows both parties to cooperate in computing F(k, x) with P's secret 151 key k and V's input x such that: V learns F(k, x) without learning 152 anything about k; and P does not learn anything about x. A 153 Verifiable OPRF (VOPRF) is an OPRF wherein P can prove to V that F(k, 154 x) was computed using key k, which is bound to a trusted public key Y 155 = kG. Informally, this is done by presenting a non-interactive zero- 156 knowledge (NIZK) proof of equality between (G, Y) and (Z, M), where Z 157 = kM for some point M. 159 OPRFs have been shown to be useful for constructing: password- 160 protected secret sharing schemes [JKK14]; privacy-preserving password 161 stores [SJKS17]; and password-authenticated key exchange or PAKE 162 [OPAQUE]. VOPRFs are useful for producing tokens that are verifiable 163 by V. This may be needed, for example, if V wants assurance that P 164 did not use a unique key in its computation, i.e., if V wants key 165 consistency from P. This property is necessary in some applications, 166 e.g., the Privacy Pass protocol [PrivacyPass], wherein this VOPRF is 167 used to generate one-time authentication tokens to bypass CAPTCHA 168 challenges. VOPRFs have also been used for password-protected secret 169 sharing schemes e.g. [JKKX16]. 171 This document introduces an OPRF protocol built in prime-order 172 groups, applying to finite fields of prime-order and also elliptic 173 curve (EC) settings. The protocol has the option of being extended 174 to a VOPRF with the addition of a NIZK proof for proving discrete log 175 equality relations. This proof demonstrates correctness of the 176 computation using a known public key that serves as a commitment to 177 the server's secret key. The document describes the protocol, its 178 security properties, and provides preliminary test vectors for 179 experimentation. The rest of the document is structured as follows: 181 o Section 2: Describe background, related work, and use cases of 182 OPRF/VOPRF protocols. 184 o Section 3.1: Discuss security properties of OPRFs/VOPRFs. 186 o Section 4: Specify an authentication protocol from OPRF 187 functionality, based in prime-order groups (with an optional 188 verifiable mode). Algorithms are stated formally for OPRFs in 189 Section 4.5 and for VOPRFs in Section 4.6. 191 o Section 5: Specify the NIZK discrete logarithm equality (DLEQ) 192 construction used for constructing the VOPRF protocol. 194 o Section 5.3: Specifies how the DLEQ proof mechanism can be batched 195 for multiple VOPRF invocations, and how this changes the protocol 196 execution. 198 o Section 6: Considers explicit instantiations of the protocol in 199 the elliptic curve setting. 201 o Section 8: Discusses the security considerations for the OPRF and 202 VOPRF protocol. 204 o Section 9: Discusses some existing applications of OPRF and VOPRF 205 protocols. 207 o Appendix A: Specifies test vectors for implementations in the 208 elliptic curve setting. 210 1.1. Change log 212 draft-01 [1]: 214 o Updated ciphersuites to be in line with 215 https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-04 217 o Made some necessary modular reductions more explicit 219 1.2. Terminology 221 The following terms are used throughout this document. 223 o PRF: Pseudorandom Function. 225 o OPRF: Oblivious PRF. 227 o VOPRF: Verifiable Oblivious Pseudorandom Function. 229 o Verifier (V): Protocol initiator when computing F(k, x), also 230 known as client. 232 o Prover (P): Holder of secret key k, also known as server. 234 o NIZK: Non-interactive zero knowledge. 236 o DLEQ: Discrete Logarithm Equality. 238 1.3. Requirements 240 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 241 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 242 document are to be interpreted as described in [RFC2119]. 244 2. Background 246 OPRFs are functionally related to blind signature schemes. In such a 247 scheme, a client can receive signatures on private data, under the 248 signing key of some server. The security properties of such a scheme 249 dictate that the client learns nothing about the signing key, and 250 that the server learns nothing about the data that is signed. One of 251 the more popular blind signature schemes is based on the RSA 252 cryptosystem and is known as Blind RSA [ChaumBlindSignature]. 254 OPRF protocols can thought of as symmetric alternatives to blind 255 signatures. Essentially the client learns y = PRF(k,x) for some 256 input x of their choice, from a server that holds k. Since the 257 security of an OPRF means that x is hidden in the interaction, then 258 the client can later reveal x to the server along with y. 260 The server can verify that y is computed correctly by recomputing the 261 PRF on x using k. In doing so, the client provides knowledge of a 262 'signature' y for their value x. The verification procedure is thus 263 symmetric as it requires knowledge of the key k. This is discussed 264 more in the following section. 266 3. Preliminaries 268 We start by detailing some necessary cryptographic definitions. 270 3.1. Security Properties 272 The security properties of an OPRF protocol with functionality y = 273 F(k, x) include those of a standard PRF. Specifically: 275 o Pseudorandomness: F is pseudorandom if the output y = F(k,x) on 276 any input x is indistinguishable from uniformly sampling any 277 element in F's range, for a random sampling of k. 279 In other words, for an adversary that can pick inputs x from the 280 domain of F and can evaluate F on (k,x) (without knowledge of 281 randomly sampled k), then the output distribution F(k,x) is 282 indistinguishable from the uniform distribution in the range of F. 284 A consequence of showing that a function is pseudorandom, is that it 285 is necessarily non-malleable (i.e. we cannot compute a new evaluation 286 of F from an existing evaluation). A genuinely random function will 287 be non-malleable with high probability, and so a pseudorandom 288 function must be non-malleable to maintain indistinguishability. 290 An OPRF protocol must also satisfy the following property: 292 o Oblivious: P must learn nothing about V's input or the output of 293 the function. In addition, V must learn nothing about P's private 294 key. 296 Essentially, obliviousness tells us that, even if P learns V's input 297 x at some point in the future, then P will not be able to link any 298 particular OPRF evaluation to x. This property is also known as 299 unlinkability [DGSTV18]. 301 Optionally, for any protocol that satisfies the above properties, 302 there is an additional security property: 304 o Verifiable: V must only complete execution of the protocol if it 305 can successfully assert that the OPRF output computed by V is 306 correct, with respect to the OPRF key held by P. 308 Any OPRF that satisfies the 'verifiable' security property is known 309 as a verifiable OPRF, or VOPRF for short. In practice, the notion of 310 verifiability requires that P commits to the key k before the actual 311 protocol execution takes place. Then V verifies that P has used k in 312 the protocol using this commitment. In the following, we may also 313 refer to this commitment as a public key. 315 4. OPRF Protocol 317 In this section we describe the OPRF and VOPRF protocols. Recall 318 that such a protocol takes place between a verifier (V) and a prover 319 (P). Commonly, V is a client and P is a server, and so we use these 320 names interchangeably throughout. think of the verifier as the 321 client, and the prover as the server in the interaction (we will use 322 these names interchangeably throughout). The server holds a secret 323 key k for a PRF. The protocol allows the client to learn PRF 324 evaluations on chosen inputs x in such a way that the server learns 325 nothing of x. 327 Our OPRF construction is based on the VOPRF construction known as 328 2HashDH-NIZK given by [JKK14]; essentially without providing zero- 329 knowledge proofs that verify that the output is correct. Our VOPRF 330 construction (including the NIZK DLEQ proofs from Section 5) is 331 identical to the [JKK14] construction. With batched proofs 332 (Section 5.3) our construction differs slightly in that we can 333 perform multiple VOPRF evaluations in one go, whilst only 334 constructing one NIZK proof object. 336 In this section we describe the OPRF and VOPRF protocols. Recall 337 that such a protocol takes place between a verifier (V) and a prover 338 (P). We may commonly think of the verifier as the client, and the 339 prover as the server in the interaction (we will use these names 340 interchangeably throughout). The server holds a key k for a PRF. 341 The protocol allows the client to learn PRF evaluations on chosen 342 inputs x without revealing x to the server. 344 Our OPRF construction is based on the VOPRF construction known as 345 2HashDH-NIZK given by [JKK14]; essentially without providing zero- 346 knowledge proofs that verify that the output is correct. Our VOPRF 347 construction (including the NIZK DLEQ proofs from Section 5) is 348 identical to the [JKK14] construction. With batched proofs 349 (Section 5.3) our construction differs slightly in that we can 350 perform multiple VOPRF evaluations in one go, whilst only 351 constructing one NIZK proof object. 353 4.1. Design 355 Let GG be an additive group of prime-order p, let GF(p) be the Galois 356 field defined by the integers modulo p. Define distinct hash 357 functions H_1 and H_2, where H_1 maps arbitrary input onto GG and H_2 358 maps arbitrary input to a fixed-length output, e.g., SHA256. All 359 hash functions in the protocol are modeled as random oracles. Let L 360 be the security parameter. Let k be the prover's secret key, and Y = 361 kG be its corresponding 'public key' for some fixed generator G taken 362 from the description of the group GG. This public key Y is also 363 referred to as a commitment to the OPRF key k, and the pair (G,Y) as 364 a commitment pair. Let x be the verifier's input to the OPRF 365 protocol (commonly, it is a random L-bit string, though this is not 366 required). 368 The OPRF protocol begins with V blinding its input for the OPRF 369 evaluator such that it appears uniformly distributed GG. The latter 370 then applies its secret key to the blinded value and returns the 371 result. To finish the computation, V then removes its blind and 372 hashes the result (along with a domain separating label DST) using 373 H_2 to yield an output. This flow is illustrated below. We use the 374 notation x .. N to denote the concatenation of the bytes of x and N. 376 Verifier(x) Prover(k) 377 ---------------------------------------------------------- 378 r <-$ GF(p) 379 M = rH_1(x) mod p 380 M 381 -------> 382 Z = kM mod p 383 [D = DLEQ_Generate(k,G,Y,M,Z)] 384 Z[,D] 385 <------- 386 [b = DLEQ_Verify(G,Y,M,Z,D)] 387 N = Zr^(-1) mod p 388 Output H_2(DST, x .. N) mod p [if b=1, else "error"] 390 Steps that are enclosed in square brackets (DLEQ_Generate and 391 DLEQ_Verify) are optional for achieving verifiability. These are 392 described in Section 5. In the verifiable mode, we assume that P has 393 previously committed to their choice of key k with some values 394 (G,Y=kG) and these are publicly known by V. Notice that revealing 395 (G,Y) does not reveal k by the well-known hardness of the discrete 396 log problem. 398 Strictly speaking, the actual PRF function that is computed is: 400 F(k, x) = N = kH_1(x) 402 It is clear that this is a PRF H_1(x) maps x to a random element in 403 GG, and GG is cyclic. This output is computed when the client 404 computes Zr^(-1) by the commutativity of the multiplication. The 405 client finishes the computation by outputting H_2(x,N). Note that 406 the output from P is not the PRF value because the actual input x is 407 blinded by r. 409 The security of our construction is discussed in more detail in 410 Section 8.1.2. We discuss the considerations that should be made 411 when embedding (V)OPRF protocols into wider protocols in Section 4.8. 413 4.2. Protocol functionality 415 This protocol may be decomposed into a series of steps, as described 416 below: 418 o OPRF_Setup(l): Let GG=GG(l) be a group with a prime-order p=p(l) 419 (e.g., p is l-bits long). Randomly sample an integer k in GF(p) 420 and output (k,p) 422 o OPRF_Blind(x): Compute and return a blind, r, and blinded 423 representation of x in GG, denoted M. 425 o OPRF_Eval(k,M,h?): Evaluates on input M using secret key k to 426 produce Z, the input h is optional and equal to the cofactor of an 427 elliptic curve. If h is not provided then it defaults to 1. 429 o OPRF_Unblind(r,Z): Unblind blinded OPRF evaluation Z with blind r, 430 yielding N and output N. 432 o OPRF_Finalize(x,N,aux): Finalize N by first computing dk := 433 H_2(DST, x .. N). Subsequently output y := H_2(dk, aux), where 434 aux is some auxiliary data. 436 For verifiability (VOPRF) we modify the algorithms of VOPRF_Setup, 437 VOPRF_Eval and VOPRF_Unblind to be the following: 439 o VOPRF_Setup(l): Run (k,p) = OPRF_Setup(l), compute Y = kG, where G 440 is a generator of the group GG. Output (k,p,Y). 442 o VOPRF_Eval(k,G,Y,M,h?): Evaluates on input M using secret key k to 443 produce Z. Generate a NIZK proof D = DLEQ_Generate(k,G,Y,M,Z), 444 and output (Z, D). The optional cofactor h can also be provided, 445 as in OPRF_Eval. 447 o VOPRF_Unblind(r,G,Y,M,Z,D): Unblind blinded OPRF evaluation Z with 448 blind r, yielding N. Output N if 1 = DLEQ_Verify(G,Y,M,Z,D). 449 Otherwise, output "error". 451 We leave the rest of the OPRF algorithms unmodified. When referring 452 explicitly to VOPRF execution, we replace 'OPRF' in all method names 453 with 'VOPRF'. We describe explicit instantiations of these functions 454 in Section 4.5 and Section 4.6. 456 4.2.1. Generalized OPRF 458 Using the API provided by the functions above, we can restate the 459 OPRF protocol using the following descriptions. The first protocol 460 refers to the OPRF setup phase that is run by the server. This 461 generates the secret input used by the server and the public 462 information that is given to the client. 464 OPRF setup phase: ~~~ Verifier() Prover(l) 465 --------------------------------------- (k,p) = OPRF_Setup(l) p 466 <----- ~~~ 468 OPRF evaluation phase: ~~~ Verifier(x,aux) Prover(k) 469 --------------------------------------- (r, M) = OPRF_Blind(x) M 470 -----> Z = OPRF_Eval(k,M) Z <----- N = OPRF_Unblind(r,Z) Output 471 OPRF_Finalize(x,N,aux) ~~~ 472 Note that in the final output, the client computes OPRF_Finalize over 473 some auxiliary input data aux. 475 4.2.2. Generalized VOPRF 477 The generalized VOPRF functionality differs slightly from the OPRF 478 protocol above. Firstly, the server sends over an extra commitment 479 value Y = kG, where G is a common generator known to both 480 participants. Secondly, the server sends over both outputs from 481 VOPRF_Eval in the evaluation phase, and the client also verifies the 482 server's output. 484 VOPRF setup phase: ~~~ Verifier() Prover(l) 485 --------------------------------------- (k,p,Y) = VOPRF_Setup(l) 486 (p,Y) <----- ~~~ 488 VOPRF evaluation phase: ~~~ Verifier(x,Y,aux) Prover(k) 489 --------------------------------------- (r, M) = VOPRF_Blind(x) M 490 -----> (Z,D) = VOPRF_Eval(k,G,Y,M) (Z,D) <----- N = 491 VOPRF_Unblind(r,G,Y,M,Z,D) Output VOPRF_Finalize(x,N,aux) ~~~ 493 4.3. Protocol correctness 495 Protocol correctness requires that, for any key k, input x, and (r, 496 M) = OPRF_Blind(x), it must be true that: 498 OPRF_Finalize(x, OPRF_Unblind(r,M,OPRF_Eval(k,M)), aux) 499 == H_2(H_2(DST, x .. F(k,x)), aux) 501 with overwhelming probability. Likewise, in the verifiable setting, 502 we require that: 504 VOPRF_Finalize(x, VOPRF_Unblind(r,G,Y,M,(VOPRF_Eval(k,G,Y,M))), aux) 505 == H_2(H_2(DST, x .. F(k,x)), aux) 507 with overwhelming probability, where (r, M) = VOPRF_Blind(x). In 508 other words, the inner H_2 invocation effectively derives a key, dk, 509 from the input data DST, x, N. The outer invocation derives the 510 output y by evaluating H_2 over dk and auxiliary data aux. 512 4.4. Instantiations of GG 514 As we remarked above, GG is a subgroup with associated prime-order p. 515 While we choose to write operations in the setting where GG comes 516 equipped with an additive operation, we could also define the 517 operations in the multiplicative setting. In the multiplicative 518 setting we can choose GG to be a prime-order subgroup of a finite 519 field FF_p. For example, let p be some large prime (e.g. > 2048 520 bits) where p = 2q+1 for some other prime q. Then the subgroup of 521 squares of FF_p (elements u^2 where u is an element of FF_p) is 522 cyclic, and we can pick a generator of this subgroup by picking G 523 from FF_p (ignoring the identity element). 525 For practicality of the protocol, it is preferable to focus on the 526 cases where GG is an additive subgroup so that we can instantiate the 527 OPRF in the elliptic curve setting. This amounts to choosing GG to 528 be a prime-order subgroup of an elliptic curve over base field GF(p) 529 for prime p. There are also other settings where GG is a prime-order 530 subgroup of an elliptic curve over a base field of non-prime order, 531 these include the work of Ristretto [RISTRETTO] and Decaf [DECAF]. 533 We will use p > 0 generally for constructing the base field GF(p), 534 not just those where p is prime. To reiterate, we focus only on the 535 additive case, and so we focus only on the cases where GF(p) is 536 indeed the base field. 538 Unless otherwise stated, we will always assume that the generator G 539 that we use for the group GG is a fixed generator. This generator 540 should be available to both the client and the server ahead of the 541 protocol, or derived for each different group instantiation using a 542 fixed method. In the elliptic curve setting, we recommend using the 543 fixed generators that are given as part of the curve description. 545 4.5. OPRF algorithms 547 This section provides descriptions of the algorithms used in the 548 generalized protocols from Section 4.2.1. We describe the VOPRF 549 analogues for the protocols in Section 4.2.2 later in Section 4.6. 551 We note here that the blinding mechanism that we use can be modified 552 slightly with the opportunity for making performance gains in some 553 scenarios. We detail these modifications in Section Section 4.7. 555 4.5.1. OPRF_Setup 556 Input: 558 l: Some suitable choice of prime length for instantiating a group structure 559 (e.g. as described in [NIST]). 561 Output: 563 k: A key chosen from {0,1}^l and interpreted as an integer value. 565 Steps: 567 1. Let GG = GG(l) be a group with prime-order p of length l bits 568 2. Sample a uniform scalar k <-$ GF(p) 569 3. Output (k,p) 571 4.5.2. OPRF_Blind 573 Input: 575 x: V's PRF input. 577 Output: 579 r: Random scalar in [1, p - 1]. 580 M: Blinded representation of x using blind r, an element in GG. 582 Steps: 584 1. r <-$ GF(p) 585 2. M := rH_1(x) 586 3. Output (r, M) 588 4.5.3. OPRF_Eval 589 Input: 591 k: Evaluator secret key. 592 M: An element in GG. 593 h: optional cofactor (defaults to 1). 595 Output: 597 Z: Scalar multiplication of the point M by k, element in GG. 599 Steps: 601 1. Z := kM 602 2. Z <- hZ 603 3. Output Z 605 4.5.4. OPRF_Unblind 607 Input: 609 r: Random scalar in [1, p - 1]. 610 Z: An element in GG. 612 Output: 614 N: Unblinded OPRF evaluation, element in GG. 616 Steps: 618 1. N := (r^(-1))Z 619 2. Output N 621 4.5.5. OPRF_Finalize 622 Input: 624 x: PRF input string. 625 N: An element in GG. 626 aux: Arbitrary auxiliary data 628 Output: 630 y: Random element in {0,1}^L. 632 Steps: 634 1. DST := "oprf_derive_output" 635 2. dk := H_2(DST, x .. N) 636 3. y := H_2(dk, aux) 637 4. Output y 639 4.6. VOPRF algorithms 641 We make modifications to the aforementioned algorithms in the VOPRF 642 setting. 644 4.6.1. VOPRF_Setup 646 Input: 648 G: Public fixed generator of GG. 649 l: Some suitable choice of key-length (e.g. as described in [NIST]). 651 Output: 653 k: A key chosen from {0,1}^l and interpreted as an integer value. 654 (G,Y): A pair of curve points, where Y=kG. 656 Steps: 658 1. (k,p) <- OPRF_Setup(l) 659 2. Y := kG 660 3. Output (k,p,Y) 662 4.6.2. VOPRF_Blind 663 Input: 665 x: V's PRF input. 667 Output: 669 r: Random scalar in [1, p - 1]. 670 M: Blinded representation of x using blind r, an element in GG. 672 Steps: 674 1. r <-$ GF(p) 675 2. M := rH_1(x) 676 3. Output (r, M) 678 4.6.3. VOPRF_Eval 680 Input: 682 k: Evaluator secret key. 683 G: Public fixed generator of group GG. 684 Y: Evaluator public key (= kG). 685 M: An element in GG. 686 h: optional cofactor (defaults to 1). 688 Output: 690 Z: Scalar multiplication of the point M by k, element in GG. 691 D: DLEQ proof that log_G(Y) == log_M(Z). 693 Steps: 695 1. Z := kM 696 2. Z <- hZ 697 3. D = DLEQ_Generate(k,G,Y,M,Z) 698 4. Output (Z, D) 700 4.6.4. VOPRF_Unblind 701 Input: 703 r: Random scalar in [1, p - 1]. 704 G: Public fixed generator of group GG. 705 Y: Evaluator public key. 706 M: Blinded representation of x using blind r, an element in GG. 707 Z: An element in GG. 708 D: D = DLEQ_Generate(k,G,Y,M,Z). 710 Output: 712 N: Unblinded OPRF evaluation, element in GG. 714 Steps: 716 1. N := (r^(-1))Z 717 2. If 1 = DLEQ_Verify(G,Y,M,Z,D), output N 718 3. Output "error" 720 4.6.5. VOPRF_Finalize 722 Input: 724 x: PRF input string. 725 N: An element in GG, or "error". 726 aux: Arbitrary auxiliary data. 728 Output: 730 y: Random element in {0,1}^L, or "error" 732 Steps: 734 1. If N == "error", output "error". 735 2. DST := "voprf_derive_output" 736 3. dk := H_2(DST, x .. N) 737 4. y := H_2(dk, aux) 738 5. Output y 740 4.7. Efficiency gains with pre-processing and fixed-base blinding 742 In Section Section 4.5 we assume that the client-side blinding is 743 carried out directly on the output of H_1(x), i.e. computing rH_1(x) 744 for some r <-$ GF(p). In the [OPAQUE] draft, it is noted that it may 745 be more efficient to use additive blinding rather than multiplicative 746 if the client can preprocess some values. For example, a valid way 747 of computing additive blinding would be to instead compute H_1(x)+rG, 748 where G is the fixed generator for the group GG. 750 We refer to the 'multiplicative' blinding as variable-base blinding 751 (VBB), since the base of the blinding (H_1(x)) varies with each 752 instantiation. We refer to the additive blinding case as fixed-base 753 blinding (FBB) since the blinding is applied to the same generator 754 each time (when computing rG). 756 By pre-processing tables of blinded scalar multiplications for the 757 specific choice of G it is possible to gain a computational 758 advantage. Choosing one of these values rG (where r is the scalar 759 value that is used), then computing H_1(x)+rG is more efficient than 760 computing rH_1(x) (one addition against log_2(r)). Therefore, it may 761 be advantageous to define the OPRF and VOPRF protocols using additive 762 blinding rather than multiplicative blinding. In fact, the only 763 algorithms that need to change are OPRF_Blind and OPRF_Unblind (and 764 similarly for the VOPRF variants). 766 We define the FBB variants of the algorithms in Section 4.5 below 767 along with a new algorithm OPRF_Preprocess that defines how 768 preprocessing is carried out. The equivalent algorithms for VOPRF 769 are almost identical and so we do not redefine them here. Notice 770 that the only computation that changes is for V, the necessary 771 computation of P does not change. 773 4.7.1. OPRF_Preprocess 775 Input: 777 G: Public fixed generator of GG 779 Output: 781 r: Random scalar in [1, p-1] 782 rG: An element in GG. 783 rY: An element in GG. 785 Steps: 787 1. r <-$ GF(p) 788 2. Output (r, rG, rY) 790 4.7.2. OPRF_Blind 791 Input: 793 x: V's PRF input. 794 rG: Preprocessed element of GG. 796 Output: 798 M: Blinded representation of x using blind r, an element in GG. 800 Steps: 802 1. M := H_1(x)+rG 803 2. Output M 805 4.7.3. OPRF_Unblind 807 Input: 809 rY: Preprocessed element of GG. 810 M: Blinded representation of x using rG, an element in GG. 811 Z: An element in GG. 813 Output: 815 N: Unblinded OPRF evaluation, element in GG. 817 Steps: 819 1. N := Z-rY 820 2. Output N 822 Notice that OPRF_Unblind computes (Z-rY) = k(H_1(x)+rG) - rkG = 823 kH_1(x) by the commutativity of scalar multiplication in GG. This is 824 the same output as in the original OPRF_Unblind algorithm. 826 4.8. Recommended protocol integration 828 We describe some recommendations and suggestions on the topic of 829 integrating the (V)OPRF protocol from Section 4 into wider protocols. 830 It should be noted that since [JKK14] provides a security proof of 831 the VOPRF construction in the UC security model, then any UC-secure 832 protocol that uses the OPRF construction as an atomic instantiation 833 will remain UC-secure. 835 Thus, it is RECOMMENDED that any protocol that wishes to include an 836 OPRF stage does so by implementing all OPRF evaluation functionality 837 as a contiguous block of operations during the protocol. This does 838 not include the OPRF setup phase, which should be run before the 839 entire protocol interaction. For example, such an instantiation for 840 a wider protocol W would look like the following. 842 ================================================================ 843 OPRF setup phase 844 ================================================================ 846 > ... 847 > BEGIN(protocol W) 848 > ... 849 > PAUSE(protocol W) 851 ================================================================ 852 OPRF evaluation phase 853 ================================================================ 855 > RESTART(protocol W) 856 > ... 857 > END(protocol W) 859 In other words, no messages from protocol W should take place during 860 the OPRF protocol instantiation. This DOES NOT preclude the 861 participants in protocol W from using the outputs of the OPRF 862 evaluation, once the OPRF protocol is complete. Note that the OPRF 863 protocol can involve batched evaluations, as well as single 864 evaluations. 866 4.8.1. Setup phase 868 In the VOPRF setting, the server must send to the client (p,Y) where 869 p is the prime used in instantiating the group used for the VOPRF 870 operations, and Y is a commitment to the server key k. From this 871 information, the client and server must agree on a generator G for 872 the group description. It is important that the generator G of GG is 873 not chosen by the server, and that it is agreed upon before the 874 protocol starts. In the elliptic curve setting, we recommend that G 875 is chosen as the standard generator for the curve. 877 As we mentioned above, if an implementer wants to embed OPRF 878 evaluation as part of a wider protocol, then we recommend that this 879 setup phase should occur before all communication takes place; 880 including all communication required for the wider protocol. We 881 recommend that any server implementation only implements one group 882 instantiation at any one time. This means that the client does not 883 have to pick a specific instantiation when it sends the first 884 evaluation message. 886 4.8.2. Evaluation phase 888 The evaluation phase of the OPRF results in a client receiving 889 pseudorandom function evaluations from the server. It is important 890 that the client is able to link the computation that it performs in 891 the first step, with the output that it receives from the server. In 892 other words, the client must store the data (r,M) output by 893 OPRF_Blind(x). When it receives Z from the server, it must then use 894 (r,M) as inputs to OPRF_Blind. 896 In the batched setting, the client stores multiple values (ri,Mi) and 897 sends each Mi to the server. Both client and server should preserve 898 this ordering throughout the evaluation phase so that the client can 899 successfully finalize the output in the final step. 901 4.8.3. Additional requirements 903 The client input to the OPRF evaluation phase is a set of bytes x. 904 These bytes are RECOMMENDED to be uniformly distributed. If the 905 bytes are sampled from a predictable distribution instead, then it is 906 likely that the server will also be able to predict the client's 907 input to the OPRF. Therefore client privacy is reduced. 909 Protocols that embed an OPRF evaluation MUST specify exactly how 910 group elements are encoded in messages. 912 The server need not not preserve any information during the 913 evaluation exchange. For efficiency and client-privacy reasons, we 914 recommend that all data received from the client in the evaluation 915 phase is destroyed after the server has responded. 917 In the VOPRF setting, when the server sends the response, it needs to 918 indicate which version of key that it has used. This enables the 919 client to retrieve the correct commitment from the public registry. 920 The server MUST include a key identifier as part of its response, to 921 ensure that the client can verify the contents of D correctly. 923 5. NIZK Discrete Logarithm Equality Proof 925 For the VOPRF protocol we require that V is able to verify that P has 926 used its private key k to evaluate the PRF. We can do this by 927 showing that the original commitment (G,Y) output by VOPRF_Setup(l) 928 satisfies log_G(Y) == log_M(Z) where Z is the output of 929 VOPRF_Eval(k,G,Y,M). 931 This may be used, for example, to ensure that P uses the same private 932 key for computing the VOPRF output and does not attempt to "tag" 933 individual verifiers with select keys. This proof must not reveal 934 the P's long-term private key to V. 936 Consequently, this allows extending the OPRF protocol with a (non- 937 interactive) discrete logarithm equality (DLEQ) algorithm built on a 938 Chaum-Pedersen [ChaumPedersen] proof. This proof is divided into two 939 procedures: DLEQ_Generate and DLEQ_Verify. These are specified 940 below. 942 5.1. DLEQ_Generate 944 Input: 946 k: Evaluator secret key. 947 G: Public fixed generator of GG. 948 Y: Evaluator public key (= kG). 949 M: An element in GG. 950 Z: An element in GG. 951 H_3: A hash function from GG to {0,1}^L, modeled as a random oracle. 953 Output: 955 D: DLEQ proof (c, s). 957 Steps: 959 1. r <-$ GF(p) 960 2. A := rG and B := rM 961 3. c <- H_3(G,Y,M,Z,A,B) (mod p) 962 4. s := (r - ck) (mod p) 963 5. Output D := (c, s) 965 We note here that it is essential that a different r value is used 966 for every invocation. If this is not done, then this may leak the 967 key k in a similar fashion as is possible in Schnorr or (EC)DSA 968 scenarios where fresh randomness is not used. 970 5.2. DLEQ_Verify 971 Input: 973 G: Public fixed generator of GG. 974 Y: Evaluator public key. 975 M: An element in GG. 976 Z: An element in GG. 977 D: DLEQ proof (c, s). 979 Output: 981 True if log_G(Y) == log_M(Z), False otherwise. 983 Steps: 985 1. A' := (sG + cY) 986 2. B' := (sM + cZ) 987 3. c' <- H_3(G,Y,M,Z,A',B') (mod p) 988 4. Output c == c' (mod p) 990 5.3. Batched VOPRF evaluation 992 Common applications (e.g. [PrivacyPass]) require V to obtain 993 multiple PRF evaluations from P. In the VOPRF case, this would also 994 require generation and verification of a DLEQ proof for each Zi 995 received by V. This is costly, both in terms of computation and 996 communication. To get around this, applications use a 'batching' 997 procedure for generating and verifying DLEQ proofs for a finite 998 number of PRF evaluation pairs (Mi,Zi). For n PRF evaluations: 1000 o Proof generation is slightly more expensive from 2n modular 1001 exponentiations to 2n+2. 1003 o Proof verification is much more efficient, from 4n modular 1004 exponentiations to 2n+4. 1006 o Communications falls from 2n to 2 group elements. 1008 Therefore, since P is usually a powerful server, we can tolerate a 1009 slight increase in proof generation complexity for much more 1010 efficient communication and proof verification. 1012 In this section, we describe algorithms for batching the DLEQ 1013 generation and verification procedure. For these algorithms we 1014 require an additional random oracle H_5: {0,1}^a x ZZ^3 -> {0,1}^b 1015 that takes an inputs of a binary string of length a and three integer 1016 values, and outputs an element in {0,1}^b. 1018 We can instantiate the random oracle function H_4 using the same hash 1019 function that is used for H_1,H_2,H_3. For H_5, we can also use a 1020 similar instantiation, or we can use a variable-length output 1021 generator. For example, for groups with an order of 256-bit, valid 1022 instantiations include functions such as SHAKE-256 [SHAKE] or HKDF- 1023 Expand-SHA256 [RFC5869]. 1025 5.3.1. Batched_DLEQ_Generate 1027 Input: 1029 k: Evaluator secret key. 1030 G: Public fixed generator of group GG. 1031 Y: Evaluator public key (= kG). 1032 n: Number of PRF evaluations. 1033 [ Mi ]: An array of points in GG of length n. 1034 [ Zi ]: An array of points in GG of length n. 1035 H_4: A hash function from GG^(2n+2) to {0,1}^a, modeled as a random oracle. 1036 H_5: A hash function from {0,1}^a x ZZ^2 to {0,1}^b, modeled as a random oracle. 1037 label: An integer label value for the splitting the domain of H_5 1039 Output: 1041 D: DLEQ proof (c, s). 1043 Steps: 1045 1. seed <- H_4(G,Y,[Mi,Zi])) 1046 2. for i in [n]: di <- H_5(seed,i,label) 1047 3. c1,...,cn := (int)d1,...,(int)dn 1048 4. M := c1M1 + ... + cnMn 1049 5. Z := c1Z1 + ... + cnZn 1050 6. Output D <- DLEQ_Generate(k,G,Y,M,Z) 1052 5.3.2. DLEQ_Batched_Verify 1053 Input: 1055 G: Public fixed generator of group GG. 1056 Y: Evaluator public key. 1057 [ Mi ]: An array of points in GG of length n. 1058 [ Zi ]: An array of points in GG of length n. 1059 D: DLEQ proof (c, s). 1061 Output: 1063 True if log_G(Y) == log_(Mi)(Zi) for each i in 1...n, False otherwise. 1065 Steps: 1067 1. seed <- H_4(G,Y,[Mi,Zi])) 1068 2. i' := i 1069 3. for i in [n]: 1070 1. di <- H_5(seed,i',info) 1071 2. if di > p: 1072 1. i' = i'+1 1073 2. i = i-1 // decrement and try again 1074 3. continue 1075 4. c1,...,cn := (int)d1,...,(int)dn 1076 5. M := c1M1 + ... + cnMn 1077 6. Z := c1Z1 + ... + cnZn 1078 7. Output DLEQ_Verify(G,Y,M,Z,D) 1080 5.3.3. Modified protocol execution 1082 The VOPRF protocol from Section Section 4 changes to allow specifying 1083 multiple blinded PRF inputs [ Mi ] for i in 1...n. P computes the 1084 array [ Zi ] and replaces DLEQ_Generate with DLEQ_Batched_Generate 1085 over these arrays. The same applies to the algorithm VOPRF_Eval. 1086 The same applies for replacing DLEQ_Verify with DLEQ_Batched_Verify 1087 when V verifies the response from P and during the algorithm 1088 VOPRF_Unblind. 1090 5.3.4. Random oracle instantiations for proofs 1092 We can instantiate the random oracle function H_4 using the same hash 1093 function that is used for H_1,H_2,H_3. For H_5, we can also use a 1094 similar instantiation, or we can use a variable-length output 1095 generator. For example, for groups with an order of 256-bit, valid 1096 instantiations include functions such as SHAKE-256 [SHAKE] or HKDF- 1097 Expand-SHA256 [RFC5869]. 1099 Input: 1101 [ ri ]: Random scalars in [1, p - 1]. 1102 G: Public fixed generator of group GG. 1103 Y: Evaluator public key. 1104 [ Mi ]: Blinded elements of GG. 1105 [ Zi ]: Server-generated elements in GG. 1106 D: A batched DLEQ proof object. 1108 Output: 1110 N: element in GG, or "error". 1112 Steps: 1114 1. N := (r^(-1))Z 1115 2. If 1 = DLEQ_Batched_Verify(G,Y,[ Mi ],[ Zi ],D), output N 1116 3. Output "error" 1118 6. Supported ciphersuites 1120 This section specifies supported VOPRF group and hash function 1121 instantiations. We only provide ciphersuites in the EC setting as 1122 these provide the most efficient way of instantiating the OPRF. Our 1123 instantiation includes considerations for providing the DLEQ proofs 1124 that make the instantiation a VOPRF. Supporting OPRF operations 1125 alone can be allowed by simply dropping the relevant components. For 1126 reasons that are detailed in Section 8.1, we only consider 1127 ciphersuites that provide strictly greater than 128 bits of security 1128 [NIST]. 1130 6.1. VOPRF-curve448-HKDF-SHA512-ELL2: 1132 o GG: curve448 [RFC7748] 1134 o H_1: curve448-SHA512-ELL2-RO [I-D.irtf-cfrg-hash-to-curve] 1136 * label: voprf_h2c 1138 o H_2: HMAC_SHA512 [RFC2104] 1140 o H_3: SHA512 1142 o H_4: SHA512 1144 o H_5: HKDF-Expand-SHA512 1146 6.2. VOPRF-p384-HKDF-SHA512-ICART: 1148 o GG: secp384r1 [SEC2] 1150 o H_1: P384-SHA512-ICART-RO [I-D.irtf-cfrg-hash-to-curve] 1152 * label: voprf_h2c 1154 o H_2: HMAC_SHA512 [RFC2104] 1156 o H_3: SHA512 1158 o H_4: SHA512 1160 o H_5: HKDF-Expand-SHA512 1162 6.3. VOPRF-p521-HKDF-SHA512-SSWU: 1164 o GG: secp521r1 [SEC2] 1166 o H_1: P521-SHA512-SSWU-RO [I-D.irtf-cfrg-hash-to-curve] 1168 * label: voprf_h2c 1170 o H_2: HMAC_SHA512 [RFC2104] 1172 o H_3: SHA512 1174 o H_4: SHA512 1176 o H_5: HKDF-Expand-SHA512 1178 We remark that the 'label' field is necessary for domain separation 1179 of the hash-to-curve functionality. 1181 7. Recommended protocol integration 1183 We describe some recommendations and suggestions on the topic of 1184 integrating the (V)OPRF protocol from Section 4 into wider protocols. 1185 It should be noted that since [JKK14] provides a security proof of 1186 the VPRF construction in the UC security model, then any UC-secure 1187 protocol that uses the OPRF construction as an atomic instantiation 1188 will remain UC-secure. 1190 As a result we recommend that any protocol that wishes to include an 1191 OPRF stage does so by implementing all OPRF evaluation functionality 1192 as a contiguous block of operations during the protocol. This does 1193 not include the OPRF setup phase, which should be run before the 1194 entire protocol interaction. For example, such an instantiation for 1195 a wider protocol W would look like the following. 1197 ================================================================ 1198 OPRF setup phase 1199 ================================================================ 1201 > ... 1202 > BEGIN(protocol W) 1203 > ... 1204 > PAUSE(protocol W) 1206 ================================================================ 1207 OPRF evaluation phase 1208 ================================================================ 1210 > RESTART(protocol W) 1211 > ... 1212 > END(protocol W) 1214 In other words, no messages from protocol W should take place during 1215 the OPRF protocol instantiation. This DOES NOT preclude the 1216 participants in protocol W from using the outputs of the OPRF 1217 evaluation, once the OPRF protocol is complete. Note that the OPRF 1218 protocol can involve batched evaluations, as well as single 1219 evaluations. 1221 7.1. Setup phase 1223 In the VOPRF setting, the server must send to the client (p,Y) where 1224 p is the prime used in instantiating the group used for the VOPRF 1225 operations, and Y is a commitment to the server key k. From this 1226 information, the client and server must agree on a generator G for 1227 the group description. It is important that the generator G of GG is 1228 not chosen by the server, and that it is agreed upon before the 1229 protocol starts. In the elliptic curve setting, we recommend that G 1230 is chosen as the standard generator for the curve. 1232 As we mentioned above, if an implementer wants to embed OPRF 1233 evaluation as part of a wider protocol, then we recommend that this 1234 setup phase should occur before all communication takes place; 1235 including all communication required for the wider protocol. We 1236 recommend that any server implementation only implements one group 1237 instantiation at any one time. This means that the client does not 1238 have to pick a specific instantiation when it sends the first 1239 evaluation message. 1241 7.2. Evaluation phase 1243 The evaluation phase of the OPRF results in a client receiving 1244 pseudorandom function evaluations from the server. It is important 1245 that the client is able to link the computation that it performs in 1246 the first step, with the output that it receives from the server. In 1247 other words, the client must store the data (r,M) output by 1248 OPRF_Blind(x). When it receives Z from the server, it must then use 1249 (r,M) as inputs to OPRF_Blind. 1251 In the batched setting, the client stores multiple values (ri,Mi) and 1252 sends each Mi to the server. Both client and server should preserve 1253 this ordering throughout the evaluation phase so that the client can 1254 successfully finalize the output in the final step. 1256 7.3. Client-specific considerations 1258 7.3.1. Inputs 1260 The client input to the OPRF evaluation phase is a set of bytes x. 1261 These bytes do not have to be uniformly distributed. However, we 1262 should note that if the bytes are sampled from a predictable 1263 distribution, then it is likely that the server will also be able to 1264 predict the client's input to the OPRF. Therefore the utility of 1265 client privacy is reduced somewhat. 1267 7.3.2. Output 1269 The client receives y = H_2(DST, x .. N) at the end of the protocol. 1270 We suggest that clients store the pair (x, y) as bytes. This allows 1271 the client to use the the output of the protocol in conjunction with 1272 the input used to create it later. 1274 7.3.3. Messages 1276 The client message contains a group element and should be encoded as 1277 bytes. In the elliptic curve setting this corresponds to an encoded 1278 curve point. Both compressed and uncompressed point encodings should 1279 be supported by the server. The length of the point encoding should 1280 be enough to determine the encoding of the point. 1282 7.4. Server-specific considerations 1284 7.4.1. Setup 1286 As mentioned previously, the server should pick a single group 1287 instantiation and advertise this as the only way of evaluating the 1288 OPRF. 1290 7.4.2. Inputs 1292 The server input to the evaluation phase is a key k. This key can be 1293 stored simply as bytes. The key must be protected at all times. If 1294 the server ever suspects that the key has been compromised then it 1295 must be rotated immediately. In addition, the key should be rotated 1296 somewhat frequently for security reasons to reduce the impact of an 1297 unknown compromise. For more information on appropriate key 1298 schedules, see Section 8.5. 1300 Every time the server key is rotated, a new setup phase will have to 1301 be run. The server should publish public key commitments (Y) to a 1302 public, trusted registry to avoid notifying all client's 1303 individually. The registry should be considered tamper-proof from 1304 the client perspective and should retain a history of all edits. We 1305 recommend that all commitments come with an expiry date to enforce 1306 rotation policies, and optionally a signature using a long-term 1307 signing key (with public verification key made available via another 1308 public beacon). The signature is only necessary to prevent active 1309 attackers that may be able to route the client to an untrusted 1310 registry. 1312 Below, we recommend the following proposed JSON structure for holding 1313 public commitment data. 1315 { 1316 "Y": , 1317 "expiry": , 1318 "sig": 1319 } 1321 This data should be retrieved and validated by the client when 1322 verifying VOPRF messages from the server. For efficiency reasons, 1323 the client may want to cache the value of "Y" and "expiry". Any 1324 commitment that has expired should not be used by the client. 1326 Each commitment should be versioned according to some obvious 1327 convention. After a key rotation the server should append a new 1328 commitment object with a new version tag. 1330 7.4.3. Outputs 1332 The server need not not preserve any information during the 1333 evaluation exchange. For efficiency and client-privacy reasons, we 1334 recommend that all data received from the client in the evaluation 1335 phase is destroyed after the server has responded. 1337 7.4.4. Messages 1339 In the VOPRF setting, when the server sends the response, it needs to 1340 indicate which version of key that it has used. This enables the 1341 client to retrieve the correct commitment from the public registry. 1342 We recommend that the server sends it's response as a JSON object 1343 that specifies separate members for the values Z and D, along with 1344 the key version that is used. 1346 8. Security Considerations 1348 This section discusses the cryptographic security of our protocol, 1349 along with some suggestions and trade-offs that arise from the 1350 implementation of the implementation of an OPRF. 1352 8.1. Cryptographic security 1354 We discuss the cryptographic security of the OPRF protocol from 1355 Section 4, relative to the necessary cryptographic assumptions that 1356 need to be made. 1358 8.1.1. Computational hardness assumptions 1360 Each assumption states that the problems specified below are 1361 computationally difficult to solve in relation to sp (the security 1362 parameter). In other words, the probability that an adversary has in 1363 solving the problem is bounded by a function negl(sp), where negl(sp) 1364 < 1/f(sp) for all polynomial functions f(). 1366 Let GG = GG(sp) be a group with prime-order p, and let FFp be the 1367 finite field of order p. 1369 8.1.1.1. Discrete-log (DL) problem 1371 Given G, a generator of GG, and H = hG for some h in FFp; output h. 1373 8.1.1.2. Decisional Diffie-Hellman (DDH) problem 1375 Sample a uniformly random bit d in {0,1}. Given (G, aG, bG, C), 1376 where: 1378 o G is a generator of GG; 1380 o a,b are elements of FFp; 1382 o if d == 0: C = abG; else: C is sampled uniformly GG(sp). 1384 Output d' == d. 1386 8.1.2. Protocol security 1388 As aforementioned, our OPRF and VOPRF constructions are based heavily 1389 on the 2HashDH-NIZK construction given in [JKK14], except for 1390 considerations on how we instantiate the NIZK DLEQ proof system. 1391 This means that the cryptographic security of our construction is 1392 also based on the assumption that the One-More Gap DH is 1393 computationally difficult to solve. 1395 The (N,Q)-One-More Gap DH (OMDH) problem asks the following. 1397 Given: 1398 - G, kG, G_1, ... , G_N where G, G1, ... GN are elements of the group GG; 1399 - oracle access to an OPRF functionality using the key k; 1400 - oracle access to DDH solvers. 1402 Find Q+1 pairs of the form below: 1404 (G_{j_s}, kG_{j_s}) 1406 where the following conditions hold: 1407 - s is a number between 1 and Q+1; 1408 - j_s is a number between 1 and N for each s; 1409 - Q is the number of allowed queries. 1411 The original paper [JKK14] gives a security proof that the 2HashDH- 1412 NIZK construction satisfies the security guarantees of a VOPRF 1413 protocol Section 3.1 under the OMDH assumption in the universal 1414 composability (UC) security model. Without the NIZK proof system, 1415 the protocol instantiates an OPRF protocol only. See the paper for 1416 further details. 1418 8.1.3. Q-strong-DH oracle 1420 A side-effect of our OPRF design is that it allows instantiation of a 1421 oracle for constructing Q-strong-DH (Q-sDH) samples. The Q-Strong-DH 1422 problem asks the following. 1424 Given G1, G2, h*G2, (h^2)*G2, ..., (h^Q)*G2; for G1 and G2 generators of GG. 1426 Output ( (1/(k+c))*G1, c ) where c is an element of FFp 1428 The assumption that this problem is hard was first introduced in 1429 [BB04]. Since then, there have been a number of cryptanalytic 1430 studies that have reduced the security of the assumption below that 1431 implied by the group instantiation (for example, [BG04] and 1432 [Cheon06]). In summary, the attacks reduce the security of the group 1433 instantiation by log_2(Q) bits. 1435 As an example, suppose that a group instantiation is used that 1436 provides 128 bits of security. Then an adversary with access to a 1437 Q-sDH oracle and makes Q=2^20 queries can reduce the security of the 1438 instantiation by log_2(2^20) = 20 bits. 1440 Notice that it is easy to instantiate a Q-sDH oracle using the OPRF 1441 functionality that we provide. A client can just submit sequential 1442 queries of the form (G, kG, (k^2)G, ..., (k^(Q-1))G), where each 1443 query is the output of the previous interaction. This means that any 1444 client that submit Q queries to the OPRF can use the aforementioned 1445 attacks to reduce security of the group instantiation by log_2(Q) 1446 bits. 1448 Recall that from a malicious client's perspective, the adversary wins 1449 if they can distinguish the OPRF interaction from a protocol that 1450 computes the ideal functionality provided by the PRF. 1452 8.1.4. Implications for ciphersuite choices 1454 The OPRF instantiations that we recommend in this document are 1455 informed by the cryptanalytic discussion above. In particular, 1456 choosing elliptic curves configurations that describe 128-bit group 1457 instantiations would appear to in fact instantiate an OPRF with 1458 128-log_2(Q) bits of security. 1460 While it would require an informed and persistent attacker to launch 1461 a highly expensive attack to reduce security to anything much below 1462 100 bits of security, we see this possibility as something that may 1463 result in problems in the future. Therefore, all of our ciphersuites 1464 in Section 6 come with a minimum group instantiation corresponding to 1465 196 bits of security. This would require an adversary to launch a 1466 minimum of Q = 2^(68) queries to reduce security to 128 bits using 1467 the Q-sDH attacks. As a result, it appears prohibitively expensive 1468 to launch credible attacks on these parameters with our current 1469 understanding of the attack surface. 1471 8.2. Hashing to curve 1473 A critical aspect of implementing this protocol using elliptic curve 1474 group instantiations is a method of instantiating the function H1, 1475 that maps inputs to group elements. In the elliptic curve setting, 1476 this must be a deterministic function that maps arbitrary inputs x 1477 (as bytes) to uniformly chosen points in the curve. 1479 In the security proof of the construction H1 is modeled as a random 1480 oracle. This implies that any instantiation of H1 must be pre-image 1481 and collision resistant. In Section 6 we give instantiations of this 1482 functionality based on the functions described in 1484 [I-D.irtf-cfrg-hash-to-curve]. Consequently, any OPRF implementation 1485 must adhere to the implementation and security considerations 1486 discussed in [I-D.irtf-cfrg-hash-to-curve] when instantiating the 1487 function H1. 1489 8.3. Timing Leaks 1491 To ensure no information is leaked during protocol execution, all 1492 operations that use secret data MUST be constant time. Operations 1493 that SHOULD be constant time include: H_1() (hashing arbitrary 1494 strings to curves) and DLEQ_Generate(). As mentioned previously, 1495 [I-D.irtf-cfrg-hash-to-curve] describes various algorithms for 1496 constant-time implementations of H_1. 1498 8.4. User segregation 1500 The aim of the OPRF functionality is to allow clients receive 1501 pseudorandom function evaluations on their own inputs, without 1502 compromising their own privacy with respect to the server. In many 1503 applications (for example, [PrivacyPass]) the client may choose to 1504 reveal their original input, after an invocation of the OPRF 1505 protocol, along with their OPRF output. This can prove to the server 1506 that it has received a valid OPRF output in the past. Since the 1507 server does not reveal learn anything about the OPRF output, it 1508 should not be able to link the client to any previous protocol 1509 instantiation. 1511 Consider a malicious server that manages to segregate the user base 1512 into different sets. Then this reduces the effective privacy of all 1513 of the clients involved, since the client above belongs to a smaller 1514 set of users than previously hoped. In general, if the user-base of 1515 the OPRF functionality is quite small, then the obliviousness of 1516 clients is limited. That is, smaller user-bases mean that the server 1517 is able to identify client's with higher certainty. 1519 In summary, an OPRF instantiation effectively comes with an 1520 additional privacy parameter pp. If all clients of the OPRF make one 1521 query and then subsequently reveal their OPRF input afterwards, then 1522 the server should be link the revealed input to a protocol 1523 instantiation with probability 1/pp. 1525 Below, we provide a few techniques that could be used to abuse 1526 client-privacy in the OPRF construction by segregating the user-base, 1527 along with some mitigations. 1529 8.4.1. Linkage patterns 1531 If the server is able to ascertain patterns of usage for some clients 1532 - such as timings associated with usage - then the effective privacy 1533 of the clients is reduced to the number of users that fit each usage 1534 pattern. Along with early registration patterns, where early 1535 adopters initially have less privacy due to a low number of 1536 registered users, such problems are inherent to any anonymity- 1537 preserving system. 1539 8.4.2. Evaluation on multiple keys 1541 Such an attack consists of the server evaluating the OPRF on multiple 1542 different keys related to the number of clients that use the 1543 functionality. As an extreme, the server could evaluate the OPRF 1544 with a different key for each client. If the client then revealed 1545 their hidden information at a later date then the server would 1546 immediately know which initial request they launched. 1548 The VOPRF variant helps mitigate this attack since each server 1549 evaluation can be bound to a known public key. However, there are 1550 still ways that the VOPRF construction can be abused. In particular: 1552 o If the server successfully provisions a large number of keys that 1553 are trusted by clients, then the server can divide the user-base 1554 by the number of keys that are currently in use. As such, clients 1555 should only trust a small number (2 or 3 ideally) of server keys 1556 at any one time. Additionally, a tamper-proof audit log system 1557 akin to existing work on Key Transparency [keytrans] could be used 1558 to ensure that a server is abiding by the key policy. This would 1559 force the server to be held accountable for their key updates, and 1560 thus higher key update frequencies can be better managed on the 1561 client-side. 1563 o If the server rotates their key frequently, then this may result 1564 in client's holding out-of-date information from a past 1565 interaction. Such information can also be used to segregate the 1566 user-base based on the last time that they accessed the OPRF 1567 protocol. Similarly to the above, server key rotations must be 1568 kept to relatively infrequent intervals (such as once per month). 1569 This will prevent too many clients from being segregated into 1570 different groups related to the time that they accessed the 1571 functionality. There are viable reasons for rotating the server 1572 key (for protecting against malicious clients) that we address 1573 more closely in Section 8.5. 1575 Since key provisioning requires careful handling, all public keys 1576 should be accessible from a client-trusted registry with a way of 1577 auditing the history of key updates. We also recommend that public 1578 keys have a corresponding expiry date that clients can use to prevent 1579 the server from using keys that have been provisioned for a long 1580 period of time. 1582 8.5. Key rotation 1584 Since the server's key is critical to security, the longer it is 1585 exposed by performing (V)OPRF operations on client inputs, the longer 1586 it is possible that the key can be compromised. For instance, if the 1587 key is kept in production for a long period of time, then this may 1588 grant the client the ability to hoard large numbers of tokens. This 1589 has negative impacts for some of the applications that we consider in 1590 Section 9. As another example, if the key is kept in circulation for 1591 a long period of time, then it also allows the clients to make enough 1592 queries to launch more powerful variants of the Q-sDH attacks from 1593 Section 8.1.3. 1595 To combat attacks of this nature, regular key rotation should be 1596 employed on the server-side. A suitable key-cycle for a key used to 1597 compute (V)OPRF evaluations would be between one week and six months. 1599 As we discussed in Section 8.4.2, key rotation cycles that are too 1600 frequent (in the order of days) can lead to large segregation of the 1601 wider user base. As such, the length of the key cycles represent a 1602 trade-off between greater server key security (for shorter cycles), 1603 and better client privacy (for longer cycles). In situations where 1604 client privacy is paramount, longer key cycles should be employed. 1605 Otherwise, shorter key cycles can be managed if the server uses a Key 1606 Transparency-type system [keytrans]; this allows clients to publicly 1607 audit their rotations. 1609 9. Applications 1611 This section describes various applications of the (V)OPRF protocol. 1613 9.1. Privacy Pass 1615 This VOPRF protocol is used by the Privacy Pass system [PrivacyPass] 1616 to help Tor users bypass CAPTCHA challenges. Their system works as 1617 follows. Client C connects - through Tor - to an edge server E 1618 serving content. Upon receipt, E serves a CAPTCHA to C, who then 1619 solves the CAPTCHA and supplies, in response, n blinded points. E 1620 verifies the CAPTCHA response and, if valid, signs (at most) n 1621 blinded points, which are then returned to C along with a batched 1622 DLEQ proof. C stores the tokens if the batched proof verifies 1623 correctly. When C attempts to connect to E again and is prompted 1624 with a CAPTCHA, C uses one of the unblinded and signed points, or 1625 tokens, to derive a shared symmetric key sk used to MAC the CAPTCHA 1626 challenge. C sends the CAPTCHA, MAC, and token input x to E, who can 1627 use x to derive sk and verify the CAPTCHA MAC. Thus, each token is 1628 used at most once by the system. 1630 The Privacy Pass implementation uses the P-256 instantiation of the 1631 VOPRF protocol. For more details, see [DGSTV18]. 1633 9.2. Private Password Checker 1635 In this application, let D be a collection of plaintext passwords 1636 obtained by prover P. For each password p in D, P computes 1637 VOPRF_Eval on H_1(p), where H_1 is as described above, and stores the 1638 result in a separate collection D'. P then publishes D' with Y, its 1639 public key. If a client C wishes to query D' for a password p', it 1640 runs the VOPRF protocol using p as input x to obtain output y. By 1641 construction, y will be the OPRF evaluation of p hashed onto the 1642 curve. C can then search D' for y to determine if there is a match. 1644 Concrete examples of important applications in the password domain 1645 include: 1647 o password-protected storage [JKK14], [JKKX16]; 1649 o perfectly-hiding password management [SJKS17]; 1651 o password-protected secret-sharing [JKKX17]. 1653 9.2.1. Parameter Commitments 1655 For some applications, it may be desirable for P to bind tokens to 1656 certain parameters, e.g., protocol versions, ciphersuites, etc. To 1657 accomplish this, P should use a distinct scalar for each parameter 1658 combination. Upon redemption of a token T from V, P can later verify 1659 that T was generated using the scalar associated with the 1660 corresponding parameters. 1662 10. Acknowledgements 1664 This document resulted from the work of the Privacy Pass team 1665 [PrivacyPass]. The authors would also like to acknowledge the 1666 helpful conversations with Hugo Krawczyk. Eli-Shaoul Khedouri 1667 provided additional review and comments on key consistency. 1669 11. References 1671 11.1. Normative References 1673 [BB04] "Short Signatures Without Random Oracles", n.d., 1674 . 1676 [BG04] "The Static Diffie-Hellman Problem", n.d., 1677 . 1679 [ChaumBlindSignature] 1680 "Blind Signatures for Untraceable Payments", n.d., 1681 . 1684 [ChaumPedersen] 1685 "Wallet Databases with Observers", n.d., 1686 . 1688 [Cheon06] "Security Analysis of the Strong Diffie-Hellman Problem", 1689 n.d., . 1692 [DECAF] "Decaf, Eliminating cofactors through point compression", 1693 n.d., . 1695 [DGSTV18] "Privacy Pass, Bypassing Internet Challenges Anonymously", 1696 n.d., . 1700 [I-D.irtf-cfrg-hash-to-curve] 1701 Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R., and 1702 C. Wood, "Hashing to Elliptic Curves", draft-irtf-cfrg- 1703 hash-to-curve-05 (work in progress), November 2019. 1705 [JKK14] "Round-Optimal Password-Protected Secret Sharing and 1706 T-PAKE in the Password-Only model", n.d., 1707 . 1709 [JKKX16] "Highly-Efficient and Composable Password-Protected Secret 1710 Sharing (Or, How to Protect Your Bitcoin Wallet Online)", 1711 n.d., . 1713 [JKKX17] "TOPPSS: Cost-minimal Password-Protected Secret Sharing 1714 based on Threshold OPRF", n.d., 1715 . 1717 [keytrans] 1718 "Security Through Transparency", n.d., 1719 . 1722 [NIST] "Keylength - NIST Report on Cryptographic Key Length and 1723 Cryptoperiod (2016)", n.d., 1724 . 1726 [OPAQUE] "The OPAQUE Asymmetric PAKE Protocol", n.d., 1727 . 1730 [PrivacyPass] 1731 "Privacy Pass", n.d., 1732 . 1734 [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 1735 Hashing for Message Authentication", RFC 2104, 1736 DOI 10.17487/RFC2104, February 1997, 1737 . 1739 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1740 Requirement Levels", BCP 14, RFC 2119, 1741 DOI 10.17487/RFC2119, March 1997, 1742 . 1744 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 1745 Key Derivation Function (HKDF)", RFC 5869, 1746 DOI 10.17487/RFC5869, May 2010, 1747 . 1749 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 1750 for Security", RFC 7748, DOI 10.17487/RFC7748, January 1751 2016, . 1753 [RISTRETTO] 1754 "The ristretto255 Group", n.d., 1755 . 1758 [SEC2] Standards for Efficient Cryptography Group (SECG), ., "SEC 1759 2: Recommended Elliptic Curve Domain Parameters", n.d., 1760 . 1762 [SHAKE] "SHA-3 Standard, Permutation-Based Hash and Extendable- 1763 Output Functions", n.d., 1764 . 1768 [SJKS17] "SPHINX, A Password Store that Perfectly Hides from 1769 Itself", n.d., . 1771 11.2. URIs 1773 [1] https://tools.ietf.org/html/draft-irtf-cfrg-voprf-00 1775 Appendix A. Test Vectors 1777 [[TODO: add when done]] 1779 Authors' Addresses 1781 Alex Davidson 1782 Cloudflare 1783 County Hall 1784 London, SE1 7GP 1785 United Kingdom 1787 Email: adavidson@cloudflare.com 1789 Nick Sullivan 1790 Cloudflare 1791 101 Townsend St 1792 San Francisco 1793 United States of America 1795 Email: nick@cloudflare.com 1797 Christopher A. Wood 1798 Apple Inc. 1799 One Apple Park Way 1800 Cupertino, California 95014 1801 United States of America 1803 Email: cawood@apple.com