idnits 2.17.1 draft-sullivan-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.) ** There are 20 instances of too long lines in the document, the longest one being 12 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 (March 11, 2019) is 1873 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'Mi' is mentioned on line 874, but not defined == Missing Reference: 'Zi' is mentioned on line 875, but not defined == Unused Reference: 'NIST' is defined on line 1081, but no explicit reference was found in the text == Unused Reference: 'RFC8032' is defined on line 1107, but no explicit reference was found in the text == Outdated reference: A later version (-16) exists of draft-irtf-cfrg-hash-to-curve-02 == Outdated reference: A later version (-06) exists of draft-krawczyk-cfrg-opaque-01 == Outdated reference: A later version (-01) exists of draft-hdevalence-cfrg-ristretto-00 Summary: 2 errors (**), 0 flaws (~~), 8 warnings (==), 1 comment (--). 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 12, 2019 C. Wood 6 Apple Inc. 7 March 11, 2019 9 Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups 10 draft-sullivan-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 12, 2019. 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 . . . . . . . . . . . . . . . . . . . . . . . . 3 61 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 62 1.2. Requirements . . . . . . . . . . . . . . . . . . . . . . 5 63 2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 5 64 3. Security Properties . . . . . . . . . . . . . . . . . . . . . 6 65 4. OPRF Protocol . . . . . . . . . . . . . . . . . . . . . . . . 6 66 4.1. Protocol correctness . . . . . . . . . . . . . . . . . . 8 67 4.2. Instantiations of GG . . . . . . . . . . . . . . . . . . 8 68 4.3. OPRF algorithms . . . . . . . . . . . . . . . . . . . . . 9 69 4.3.1. OPRF_Setup . . . . . . . . . . . . . . . . . . . . . 9 70 4.3.2. OPRF_Blind . . . . . . . . . . . . . . . . . . . . . 10 71 4.3.3. OPRF_Sign . . . . . . . . . . . . . . . . . . . . . . 10 72 4.3.4. OPRF_Unblind . . . . . . . . . . . . . . . . . . . . 11 73 4.3.5. OPRF_Finalize . . . . . . . . . . . . . . . . . . . . 11 74 4.4. VOPRF algorithms . . . . . . . . . . . . . . . . . . . . 11 75 4.4.1. VOPRF_Setup . . . . . . . . . . . . . . . . . . . . . 12 76 4.4.2. VOPRF_Blind . . . . . . . . . . . . . . . . . . . . . 12 77 4.4.3. VOPRF_Sign . . . . . . . . . . . . . . . . . . . . . 13 78 4.4.4. VOPRF_Unblind . . . . . . . . . . . . . . . . . . . . 13 79 4.4.5. VOPRF_Finalize . . . . . . . . . . . . . . . . . . . 13 80 4.5. Utility algorithms . . . . . . . . . . . . . . . . . . . 14 81 4.5.1. bin2scalar . . . . . . . . . . . . . . . . . . . . . 14 82 4.6. Efficiency gains with pre-processing and additive 83 blinding . . . . . . . . . . . . . . . . . . . . . . . . 14 84 4.6.1. OPRF_Preprocess . . . . . . . . . . . . . . . . . . . 15 85 4.6.2. OPRF_Blind . . . . . . . . . . . . . . . . . . . . . 15 86 4.6.3. OPRF_Unblind . . . . . . . . . . . . . . . . . . . . 16 87 5. NIZK Discrete Logarithm Equality Proof . . . . . . . . . . . 16 88 5.1. DLEQ_Generate . . . . . . . . . . . . . . . . . . . . . . 16 89 5.2. DLEQ_Verify . . . . . . . . . . . . . . . . . . . . . . . 17 90 6. Batched VOPRF evaluation . . . . . . . . . . . . . . . . . . 17 91 6.1. Batched DLEQ algorithms . . . . . . . . . . . . . . . . . 18 92 6.1.1. Batched_DLEQ_Generate . . . . . . . . . . . . . . . . 18 93 6.1.2. Batched_DLEQ_Verify . . . . . . . . . . . . . . . . . 19 94 6.2. Modified protocol execution . . . . . . . . . . . . . . . 20 95 6.3. PRNG and resampling . . . . . . . . . . . . . . . . . . . 20 97 7. Supported ciphersuites . . . . . . . . . . . . . . . . . . . 20 98 7.1. ECVOPRF-P256-HKDF-SHA256-SSWU: . . . . . . . . . . . . . 20 99 7.2. ECVOPRF-RISTRETTO-HKDF-SHA512-Elligator2: . . . . . . . . 21 100 8. Security Considerations . . . . . . . . . . . . . . . . . . . 21 101 8.1. Timing Leaks . . . . . . . . . . . . . . . . . . . . . . 21 102 8.2. Hashing to curves . . . . . . . . . . . . . . . . . . . . 22 103 8.3. Verifiability (key consistency) . . . . . . . . . . . . . 22 104 9. Applications . . . . . . . . . . . . . . . . . . . . . . . . 22 105 9.1. Privacy Pass . . . . . . . . . . . . . . . . . . . . . . 22 106 9.2. Private Password Checker . . . . . . . . . . . . . . . . 23 107 9.2.1. Parameter Commitments . . . . . . . . . . . . . . . . 23 108 10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 23 109 11. Normative References . . . . . . . . . . . . . . . . . . . . 23 110 Appendix A. Test Vectors . . . . . . . . . . . . . . . . . . . . 25 111 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 27 113 1. Introduction 115 A pseudorandom function (PRF) F(k, x) is an efficiently computable 116 function with secret key k on input x. Roughly, F is pseudorandom if 117 the output y = F(k, x) is indistinguishable from uniformly sampling 118 any element in F's range for random choice of k. An oblivious PRF 119 (OPRF) is a two-party protocol between a prover P and verifier V 120 where P holds a PRF key k and V holds some input x. The protocol 121 allows both parties to cooperate in computing F(k, x) with P's secret 122 key k and V's input x such that: V learns F(k, x) without learning 123 anything about k; and P does not learn anything about x. A 124 Verifiable OPRF (VOPRF) is an OPRF wherein P can prove to V that F(k, 125 x) was computed using key k, which is bound to a trusted public key Y 126 = kG. Informally, this is done by presenting a non-interactive zero- 127 knowledge (NIZK) proof of equality between (G, Y) and (Z, M), where Z 128 = kM for some point M. 130 OPRFs have been shown to be useful for constructing: password- 131 protected secret sharing schemes [JKK14]; privacy-preserving password 132 stores [SJKS17]; and password-authenticated key exchange or PAKE 133 [OPAQUE]. VOPRFs are useful for producing tokens that are verifiable 134 by V. This may be needed, for example, if V wants assurance that P 135 did not use a unique key in its computation, i.e., if V wants key 136 consistency from P. This property is necessary in some applications, 137 e.g., the Privacy Pass protocol [PrivacyPass], wherein this VOPRF is 138 used to generate one-time authentication tokens to bypass CAPTCHA 139 challenges. VOPRFs have also been used for password-protected secret 140 sharing schemes e.g. [JKKX16]. 142 This document introduces an OPRF protocol built in prime-order 143 groups, applying to finite fields of prime-order and also elliptic 144 curve (EC) settings. The protocol has the option of being extended 145 to a VOPRF with the addition of a NIZK proof for proving discrete log 146 equality relations. This proof demonstrates correctness of the 147 computation using a known public key that serves as a commitment to 148 the server's secret key. In the EC setting, we will refer to the 149 protocol as ECOPRF (or ECVOPRF if verifiability is concerned). The 150 document describes the protocol, its security properties, and 151 provides preliminary test vectors for experimentation. The rest of 152 the document is structured as follows: 154 o Section Section 2: Describe background, related work, and use 155 cases of OPRF/VOPRF protocols. 157 o Section Section 3: Discuss security properties of OPRFs/VOPRFs. 159 o Section Section 4: Specify an authentication protocol from OPRF 160 functionality, based in prime-order groups (with an optional 161 verifiable mode). Algorithms are stated formally for OPRFs in 162 Section 4.3 and for VOPRFs in Section 4.4. 164 o Section Section 5: Specify the NIZK discrete logarithm equality 165 (DLEQ) construction used for constructing the VOPRF protocol. 167 o Section Section 6: Specifies how the DLEQ proof mechanism can be 168 batched for multiple VOPRF invocations, and how this changes the 169 protocol execution. 171 o Section Section 7: Considers explicit instantiations of the 172 protocol in the elliptic curve setting. 174 o Section Section 8: Discusses the security considerations for the 175 OPRF and VOPRF protocol. 177 o Section Section 9: Discusses some existing applications of OPRF 178 and VOPRF protocols. 180 o Section Appendix A: Specifies test vectors for implementations in 181 the elliptic curve setting. 183 1.1. Terminology 185 The following terms are used throughout this document. 187 o PRF: Pseudorandom Function. 189 o OPRF: Oblivious PRF. 191 o VOPRF: Verifiable Oblivious Pseudorandom Function. 193 o ECVOPRF: A VOPRF built on Elliptic Curves. 195 o Verifier (V): Protocol initiator when computing F(k, x). 197 o Prover (P): Holder of secret key k. 199 o NIZK: Non-interactive zero knowledge. 201 o DLEQ: Discrete Logarithm Equality. 203 1.2. Requirements 205 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 206 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 207 document are to be interpreted as described in [RFC2119]. 209 2. Background 211 OPRFs are functionally related to RSA-based blind signature schemes, 212 e.g., [ChaumBlindSignature]. Briefly, a blind signature scheme works 213 as follows. Let m be a message to be signed by a server. It is 214 assumed to be a member of the RSA group. Also, let N be the RSA 215 modulus, and e and d be the public and private keys, respectively. A 216 prover P and verifier V engage in the following protocol given input 217 m. 219 1. V generates a random blinding element r from the RSA group, and 220 compute m' = m^r (mod N). Send m' to the P. 222 2. P uses m' to compute s' = (m')^d (mod N), and sends s' to the V. 224 3. V removes the blinding factor r to obtain the original signature 225 as s = (s')^(r^-1) (mod N). 227 By the properties of RSA, s is clearly a valid signature for m. OPRF 228 protocols can be used to provide a symmetric equivalent to blind 229 signatures. Essentially the client learns y = PRF(k,x) for some 230 input x of their choice, from a server that holds k. Since the 231 security of an OPRF means that x is hidden in the interaction, then 232 the client can later reveal x to the server along with y. 234 The server can verify that y is computed correctly by recomputing the 235 PRF on x using k. In doing so, the client provides knowledge of a 236 'signature' y for their value x. However, the verification procedure 237 is symmetric since it requires knowledge of k. This is discussed 238 more in the following section. 240 3. Security Properties 242 The security properties of an OPRF protocol with functionality y = 243 F(k, x) include those of a standard PRF. Specifically: 245 o Given value x, it is infeasible to compute y = F(k, x) without 246 knowledge of k. 248 o The output distribution of y = F(k, x) is indistinguishable from 249 the uniform distribution in the domain of the function F. 251 Additionally, we require the following additional properties: 253 o Non-malleable: Given (x, y = F(k, x)), V must not be able to 254 generate (x', y') where x' != x and y' = F(k, x'). 256 o Oblivious: P must learn nothing about V's input, and V must learn 257 nothing about P's private key. 259 o Unlinkable: If V reveals x to P, P cannot link x to the protocol 260 instance in which y = F(k, x) was computed. 262 Optionally, for any protocol that satisfies the above properties, 263 there is an additional security property: 265 o Verifiable: V must only complete execution of the protocol if it 266 can successfully assert that P used its secret key k. 268 In practice, the notion of verifiability requires that P commits to 269 the key k before the actual protocol execution takes place. Then V 270 verifies that P has used k in the protocol using this commitment. 272 4. OPRF Protocol 274 In this section we describe the OPRF protocol. Let GG be a prime- 275 order additive subgroup, with two distinct hash functions H_1 and 276 H_2, where H_1 maps arbitrary input onto GG and H_2 maps arbitrary 277 input to a fixed-length output, e.g., SHA256. All hash functions in 278 the protocol are modelled as random oracles. Let L be the security 279 parameter. Let k be the prover's (P) secret key, and Y = kG be its 280 corresponding 'public key' for some generator G taken from the group 281 GG. This public key is also referred to as a commitment to the key 282 k. Let x be the verifier's (V) input to the OPRF protocol. 283 (Commonly, it is a random L-bit string, though this is not required.) 285 The OPRF protocol begins with V blinding its input for the signer 286 such that it appears uniformly distributed GG. The latter then 287 applies its secret key to the blinded value and returns the result. 289 To finish the computation, V then removes its blind and hashes the 290 result using H_2 to yield an output. This flow is illustrated below. 292 Verifier Prover 293 ------------------------------------ 294 r <-$ GG 295 M = rH_1(x) 296 M 297 -------> 298 Z = kM 299 [D = DLEQ_Generate(k,G,Y,M,Z)] 300 Z[,D] 301 <------- 302 [b = DLEQ_Verify(G,Y,M,Z,D)] 303 N = Zr^(-1) 304 Output H_2(x, N) [if b=1, else "error"] 306 Steps that are enclosed in square brackets (DLEQ_Generate and 307 DLEQ_Verify) are optional for achieving verifiability. These are 308 described in Section Section 5. In the verifiable mode, we assume 309 that P has previously committed to their choice of key k with some 310 values (G,Y=kG) and these are publicly known by V. Notice that 311 revealing (G,Y) does not reveal k by the well-known hardness of the 312 discrete log problem. 314 Strictly speaking, the actual PRF function that is computed is: 316 F(k, x) = N = kH_1(x) 318 It is clear that this is a PRF H_1(x) maps x to a random element in 319 GG, and GG is cyclic. This output is computed when the client 320 computes Zr^(-1) by the commutativity of the multiplication. The 321 client finishes the computation by outputting H_2(x,N). Note that 322 the output from P is not the PRF value because the actual input x is 323 blinded by r. 325 This protocol may be decomposed into a series of steps, as described 326 below: 328 o OPRF_Setup(l): Generate am integer k of sufficient bit-length l 329 and output k. 331 o OPRF_Blind(x): Compute and return a blind, r, and blinded 332 representation of x in GG, denoted M. 334 o OPRF_Sign(k,M,h): Sign input M using secret key k to produce Z, 335 the input h is optional and equal to the cofactor of an elliptic 336 curve. If h is not provided then it defaults to 1. 338 o OPRF_Unblind(r,Z): Unblind blinded signature Z with blind r, 339 yielding N and output N. 341 o OPRF_Finalize(x,N): Finalize N to produce the output H_2(x, N). 343 For verifiability we modify the algorithms of VOPRF_Setup, VOPRF_Sign 344 and VOPRF_Unblind to be the following: 346 o VOPRF_Setup(l): Generate an integer k of sufficient bit-length l 347 and output (k, (G,Y)) where Y = kG for some generator G in GG. 349 o VOPRF_Sign(k,(G,Y),M,h): Sign input M using secret key k to 350 produce Z. Generate a NIZK proof D = DLEQ_Generate(k,G,Y,M,Z), 351 and output (Z, D). The optional cofactor h can also be provided 352 as in OPRF_Sign. 354 o VOPRF_Unblind(r,G,Y,M,(Z,D)): Unblind blinded signature Z with 355 blind r, yielding N. Output N if 1 = DLEQ_Verify(G,Y,M,Z,D). 356 Otherwise, output "error". 358 We leave the rest of the OPRF algorithms unmodified. When referring 359 explicitly to VOPRF execution, we replace 'OPRF' in all method names 360 with 'VOPRF'. 362 4.1. Protocol correctness 364 Protocol correctness requires that, for any key k, input x, and (r, 365 M) = OPRF_Blind(x), it must be true that: 367 OPRF_Finalize(x, OPRF_Unblind(r,M,OPRF_Sign(k,M))) = H_2(x, F(k,x)) 369 with overwhelming probability. Likewise, in the verifiable setting, 370 we require that: 372 VOPRF_Finalize(x, VOPRF_Unblind(r,(G,Y),M,(VOPRF_Sign(k,(G,Y),M)))) = H_2(x, F(k,x)) 374 with overwhelming probability, where (r, M) = VOPRF_Blind(x). 376 4.2. Instantiations of GG 378 As we remarked above, GG is a subgroup with associated prime-order p. 379 While we choose to write operations in the setting where GG comes 380 equipped with an additive operation, we could also define the 381 operations in the multiplicative setting. In the multiplicative 382 setting we can choose GG to be a prime-order subgroup of a finite 383 field FF_p. For example, let p be some large prime (e.g. > 2048 384 bits) where p = 2q+1 for some other prime q. Then the subgroup of 385 squares of FF_p (elements u^2 where u is an element of FF_p) is 386 cyclic, and we can pick a generator of this subgroup by picking g 387 from FF_p (ignoring the identity element). 389 For practicality of the protocol, it is preferable to focus on the 390 cases where GG is an additive subgroup so that we can instantiate the 391 OPRF in the elliptic curve setting. This amounts to choosing GG to 392 be a prime-order subgroup of an elliptic curve over base field GF(p) 393 for prime p. There are also other settings where GG is a prime-order 394 subgroup of an elliptic curve over a base field of non-prime order, 395 these include the work of Ristretto [RISTRETTO] and Decaf [DECAF]. 397 We will use p > 0 generally for constructing the base field GF(p), 398 not just those where p is prime. To reiterate, we focus only on the 399 additive case, and so we focus only on the cases where GF(p) is 400 indeed the base field. 402 4.3. OPRF algorithms 404 This section provides algorithms for each step in the OPRF protocol. 405 We describe the VOPRF analogues in Section 4.4. We provide generic 406 utility algorithms in Section 4.5. 408 1. P samples a uniformly random key k <- {0,1}^l for sufficient 409 length l, and interprets it as an integer. 411 2. V computes X = H_1(x) and a random element r (blinding factor) 412 from GF(p), and computes M = rX. 414 3. V sends M to P. 416 4. P computes Z = kM = rkX. 418 5. In the elliptic curve setting, P multiplies Z by the cofactor 419 (denoted h) of the elliptic curve. 421 6. P sends Z to V. 423 7. V unblinds Z to compute N = r^(-1)Z = kX. 425 8. V outputs the pair H_2(x, N). 427 4.3.1. OPRF_Setup 428 Input: 430 l: Some suitable choice of key-length (e.g. as described in {{NIST}}). 432 Output: 434 k: A key chosen from {0,1}^l and interpreted as an integer value. 436 Steps: 438 1. Sample k_bin <-$ {0,1}^l 439 2. Output k <- bin2scalar(k_bin, l) 441 4.3.2. OPRF_Blind 443 Input: 445 x: V's PRF input. 447 Output: 449 r: Random scalar in [1, p - 1]. 450 M: Blinded representation of x using blind r, an element in GG. 452 Steps: 454 1. r <-$ GF(p) 455 2. M := rH_1(x) 456 3. Output (r, M) 458 4.3.3. OPRF_Sign 460 Input: 462 k: Signer secret key. 463 M: An element in GG. 464 h: optional cofactor (defaults to 1). 466 Output: 468 Z: Scalar multiplication of the point M by k, element in GG. 470 Steps: 472 1. Z := kM 473 2. Z <- hZ 474 3. Output Z 476 4.3.4. OPRF_Unblind 478 Input: 480 r: Random scalar in [1, p - 1]. 481 Z: An element in GG. 483 Output: 485 N: Unblinded signature, element in GG. 487 Steps: 489 1. N := (1/r)Z 490 2. Output N 492 4.3.5. OPRF_Finalize 494 Input: 496 x: PRF input string. 497 N: An element in GG. 499 Output: 501 y: Random element in {0,1}^L. 503 Steps: 505 1. y := H_2(x, N) 506 2. Output y 508 4.4. VOPRF algorithms 510 The steps in the VOPRF setting are written as: 512 1. P samples a uniformly random key k <- {0,1}^l for sufficient 513 length l, and interprets it as an integer. 515 2. P commits to k by computing (G,Y) for Y=kG and where G is a 516 generator of GG. P makes (G,Y) publicly available. 518 3. V computes X = H_1(x) and a random element r (blinding factor) 519 from GF(p), and computes M = rX. 521 4. V sends M to P. 523 5. P computes Z = kM = rkX, and D = DLEQ_Generate(k,G,Y,M,Z). 525 6. P sends (Z, D) to V. 527 7. V ensures that 1 = DLEQ_Verify(G,Y,M,Z,D). If not, V outputs an 528 error. 530 8. V unblinds Z to compute N = r^(-1)Z = kX. 532 9. V outputs the pair H_2(x, N). 534 4.4.1. VOPRF_Setup 536 Input: 538 G: Public generator of GG. 539 l: Some suitable choice of key-length (e.g. as described in {{NIST}}). 541 Output: 543 k: A key chosen from {0,1}^l and interpreted as an integer value. 544 (G,Y): A pair of curve points, where Y=kG. 546 Steps: 548 1. k <- OPRF_Setup(l) 549 2. Y := kG 550 3. Output (k, (G,Y)) 552 4.4.2. VOPRF_Blind 554 Input: 556 x: V's PRF input. 558 Output: 560 r: Random scalar in [1, p - 1]. 561 M: Blinded representation of x using blind r, an element in GG. 563 Steps: 565 1. r <-$ GF(p) 566 2. M := rH_1(x) 567 3. Output (r, M) 569 4.4.3. VOPRF_Sign 571 Input: 573 k: Signer secret key. 574 G: Public generator of group GG. 575 Y: Signer public key (= kG). 576 M: An element in GG. 577 h: optional cofactor (defaults to 1). 579 Output: 581 Z: Scalar multiplication of the point M by k, element in GG. 582 D: DLEQ proof that log_G(Y) == log_M(Z). 584 Steps: 586 1. Z := kM 587 2. Z <- hZ 588 3. D = DLEQ_Generate(k,G,Y,M,Z) 589 4. Output (Z, D) 591 4.4.4. VOPRF_Unblind 593 Input: 595 r: Random scalar in [1, p - 1]. 596 G: Public generator of group GG. 597 Y: Signer public key. 598 M: Blinded representation of x using blind r, an element in GG. 599 Z: An element in GG. 600 D: D = DLEQ_Generate(k,G,Y,M,Z). 602 Output: 604 N: Unblinded signature, element in GG. 606 Steps: 608 1. N := (1/r)Z 609 2. If 1 = DLEQ_Verify(G,Y,M,Z,D), output N 610 3. Output "error" 612 4.4.5. VOPRF_Finalize 613 Input: 615 x: PRF input string. 616 N: An element in GG, or "error". 618 Output: 620 y: Random element in {0,1}^L, or "error" 622 Steps: 624 1. If N == "error", output "error". 625 2. y := H_2(x, N) 626 3. Output y 628 4.5. Utility algorithms 630 4.5.1. bin2scalar 632 This algorithm converts a binary string to an integer modulo p. 634 Input: 636 s: binary string (little-endian) 637 l: length of binary string 638 p: modulus 640 Output: 642 z: An integer modulo p 644 Steps: 646 1. sVec <- vec(s) (converts s to a column vector of dimension l) 647 2. p2Vec <- (2^0, 2^1, ..., 2^{l-1}) (row vector of dimension l) 648 3. z <- p2Vec * sVec (mod p) 649 4. Output z 651 4.6. Efficiency gains with pre-processing and additive blinding 653 In the [OPAQUE] draft, it is noted that it may be more efficient to 654 use additive blinding rather than multiplicative if the client can 655 preprocess some values. For example, computing rH_1(x) is an example 656 of multiplicative blinding. A valid way of computing additive 657 blinding would be to instead compute H_1(x)+rG, where G is the common 658 generator for the group. 660 If the client preprocesses values of the form rG, then computing 661 H_1(x)+rG is more efficient than computing rH_1(x) (one addition 662 against log_2(r)). Therefore, it may be advantageous to define the 663 OPRF and VOPRF protocols using additive blinding rather than 664 multiplicative blinding. In fact the only algorithms that need to 665 change are OPRF_Blind and OPRF_Unblind (and similarly for the VOPRF 666 variants). 668 We define the additive blinding variants of the above algorithms 669 below along with a new algorithm OPRF_Preprocess that defines how 670 preprocessing is carried out. The equivalent algorithms for VOPRF 671 are almost identical and so we do not redefine them here. Notice 672 that the only computation that changes is for V, the necessary 673 computation of P does not change. 675 4.6.1. OPRF_Preprocess 677 Input: 679 G: Public generator of GG 681 Output: 683 r: Random scalar in [1, p-1] 684 rG: An element in GG. 685 rY: An element in GG. 687 Steps: 689 1. r <-$ GF(p) 690 2. Output (r, rG, rY) 692 4.6.2. OPRF_Blind 694 Input: 696 x: V's PRF input. 697 rG: Preprocessed element of GG. 699 Output: 701 M: Blinded representation of x using blind r, an element in GG. 703 Steps: 705 1. M := H_1(x)+rG 706 2. Output M 708 4.6.3. OPRF_Unblind 710 Input: 712 rY: Preprocessed element of GG. 713 M: Blinded representation of x using rG, an element in GG. 714 Z: An element in GG. 716 Output: 718 N: Unblinded signature, element in GG. 720 Steps: 722 1. N := Z-rY 723 2. Output N 725 Notice that OPRF_Unblind computes (Z-rY) = k(H_1(x)+rG) - rkG = 726 kH_1(x) by the commutativity of scalar multiplication in GG. This is 727 the same output as in the original OPRF_Unblind algorithm. 729 5. NIZK Discrete Logarithm Equality Proof 731 For the VOPRF protocol we require that V is able to verify that P has 732 used its private key k to evaluate the PRF. We can do this by 733 showing that the original commitment (G,Y) output by VOPRF_Setup(l) 734 satisfies log_G(Y) == log_M(Z) where Z is the output of 735 VOPRF_Sign(k,(G,Y),M). 737 This may be used, for example, to ensure that P uses the same private 738 key for computing the VOPRF output and does not attempt to "tag" 739 individual verifiers with select keys. This proof must not reveal 740 the P's long-term private key to V. 742 Consequently, this allows extending the OPRF protocol with a (non- 743 interactive) discrete logarithm equality (DLEQ) algorithm built on a 744 Chaum-Pedersen [ChaumPedersen] proof. This proof is divided into two 745 procedures: DLEQ_Generate and DLEQ_Verify. These are specified 746 below. 748 5.1. DLEQ_Generate 749 Input: 751 k: Signer secret key. 752 G: Public generator of GG. 753 Y: Signer public key (= kG). 754 M: An element in GG. 755 Z: An element in GG. 756 H_3: A hash function from GG to {0,1}^L, modelled as a random oracle. 758 Output: 760 D: DLEQ proof (c, s). 762 Steps: 764 1. r <-$ GF(p) 765 2. A := rG and B := rM. 766 3. c <- H_3(G,Y,M,Z,A,B) 767 4. s := (r - ck) (mod p) 768 5. Output D := (c, s) 770 5.2. DLEQ_Verify 772 Input: 774 G: Public generator of GG. 775 Y: Signer public key. 776 M: An element in GG. 777 Z: An element in GG. 778 D: DLEQ proof (c, s). 780 Output: 782 True if log_G(Y) == log_M(Z), False otherwise. 784 Steps: 786 1. A' := (sG + cY) 787 2. B' := (sM + cZ) 788 3. c' <- H_3(G,Y,M,Z,A',B') 789 4. Output c == c' 791 6. Batched VOPRF evaluation 793 Common applications (e.g. [PrivacyPass]) require V to obtain 794 multiple PRF evaluations from P. In the VOPRF case, this would also 795 require generation and verification of a DLEQ proof for each Zi 796 received by V. This is costly, both in terms of computation and 797 communication. To get around this, applications use a 'batching' 798 procedure for generating and verifying DLEQ proofs for a finite 799 number of PRF evaluation pairs (Mi,Zi). For n PRF evaluations: 801 o Proof generation is slightly more expensive from 2n modular 802 exponentiations to 2n+2. 804 o Proof verification is much more efficient, from 4m modular 805 exponentiations to 2n+4. 807 o Communications falls from 2n to 2 group elements. 809 Therefore, since P is usually a powerful server, we can tolerate a 810 slight increase in proof generation complexity for much more 811 efficient communication and proof verification. 813 In this section, we describe algorithms for batching the DLEQ 814 generation and verification procedure. For these algorithms we 815 require a pseudorandom generator PRNG: {0,1}^a x ZZ -> ({0,1}^b)^n 816 that takes a seed of length a and an integer n as input, and outputs 817 n elements in {0,1}^b. 819 6.1. Batched DLEQ algorithms 821 6.1.1. Batched_DLEQ_Generate 822 Input: 824 k: Signer secret key. 825 G: Public generator of group GG. 826 Y: Signer public key (= kG). 827 n: Number of PRF evaluations. 828 [Mi]: An array of points in GG of length n. 829 [Zi]: An array of points in GG of length n. 830 PRNG: A pseudorandom generator of the form above. 831 salt: An integer salt value for each PRNG invocation 832 info: A string value for splitting the domain of the PRNG 833 H_4: A hash function from GG^(2n+2) to {0,1}^a, modelled as a random oracle. 835 Output: 837 D: DLEQ proof (c, s). 839 Steps: 841 1. seed <- H_4(G,Y,[Mi,Zi])) 842 2. d1,...dn <- PRNG(seed,salt,info,n) 843 3. c1,...,cn := (int)d1,...,(int)dn 844 4. M := c1M1 + ... + cnMn 845 5. Z := c1Z1 + ... + cnZn 846 6. Output D <- DLEQ_Generate(k,G,Y,M,Z) 848 6.1.2. Batched_DLEQ_Verify 850 Input: 852 G: Public generator of group GG. 853 Y: Signer public key. 854 [Mi]: An array of points in GG of length n. 855 [Zi]: An array of points in GG of length n. 856 D: DLEQ proof (c, s). 858 Output: 860 True if log_G(Y) == log_(Mi)(Zi) for each i in 1...n, False otherwise. 862 Steps: 864 1. seed <- H_4(G,Y,[Mi,Zi])) 865 2. d1,...dn <- PRNG(seed,salt,info,n) 866 3. c1,...,cn := (int)d1,...,(int)dn 867 4. M := c1M1 + ... + cnMn 868 5. Z := c1Z1 + ... + cnZn 869 6. Output DLEQ_Verify(G,Y,M,Z,D) 871 6.2. Modified protocol execution 873 The VOPRF protocol from Section Section 4 changes to allow specifying 874 multiple blinded PRF inputs [Mi] for i in 1...n. Then P computes the 875 array [Zi] and replaces DLEQ_Generate with Batched_DLEQ_Generate over 876 these arrays. The same applies to the algorithm VOPRF_Sign. The 877 same applies for replacing DLEQ_Verify with Batched_DLEQ_Verify when 878 V verifies the response from P and during the algorithm VOPRF_Verify. 880 6.3. PRNG and resampling 882 Any function that satisfies the security properties of a pseudorandom 883 number generator can be used for computing the batched DLEQ proof. 884 For example, SHAKE-256 [SHAKE] or HKDF-SHA256 [RFC5869] would be 885 reasonable choices for groups that have an order of 256 bits. 887 We note that the PRNG outputs d1,...,dn must be smaller than the 888 order of the group/curve that is being used. Resampling can be 889 achieved by increasing the value of the iterator that is used in the 890 info field of the PRNG input. 892 7. Supported ciphersuites 894 This section specifies supported ECVOPRF group and hash function 895 instantiations. We only provide ciphersuites in the EC setting as 896 these provide the most efficient way of instantiating the OPRF. Our 897 instantiation includes considerations for providing the DLEQ proofs 898 that make the instantiation a VOPRF. Supporting OPRF operations 899 (ECOPRF) alone can be allowed by simply dropping the relevant 900 components. In addition, we currently only support ciphersuites 901 demonstrating 128 bits of security. 903 7.1. ECVOPRF-P256-HKDF-SHA256-SSWU: 905 o GG: SECP256K1 curve [SEC2] 907 o H_1: H2C-P256-SHA256-SSWU- [I-D.irtf-cfrg-hash-to-curve] 909 * label: voprf_h2c 911 o H_2: SHA256 913 o H_3: SHA256 915 o H_4: SHA256 917 o PRNG: HKDF-SHA256 919 7.2. ECVOPRF-RISTRETTO-HKDF-SHA512-Elligator2: 921 o GG: Ristretto [RISTRETTO] 923 o H_1: H2C-Curve25519-SHA512-Elligator2-Clear 924 [I-D.irtf-cfrg-hash-to-curve] 926 * label: voprf_h2c 928 o H_2: SHA512 930 o H_3: SHA512 932 o H_4: SHA512 934 o PRNG: HKDF-SHA512 936 In the case of Ristretto, internal point representations are 937 represented by Ed25519 [RFC7748] points. As a result, we can use the 938 same hash-to-curve encoding as we would use for Ed25519 939 [I-D.irtf-cfrg-hash-to-curve]. We remark that the 'label' field is 940 necessary for domain separation of the hash-to-curve functionality. 942 8. Security Considerations 944 Security of the protocol depends on P's secrecy of k. Best practices 945 recommend P regularly rotate k so as to keep its window of compromise 946 small. Moreover, it each key should be generated from a source of 947 safe, cryptographic randomness. 949 Another critical aspect of this protocol is reliance on 950 [I-D.irtf-cfrg-hash-to-curve] for mapping arbitrary inputs x to 951 points on a curve. Security requires this mapping be pre-image and 952 collision resistant. 954 8.1. Timing Leaks 956 To ensure no information is leaked during protocol execution, all 957 operations that use secret data MUST be constant time. Operations 958 that SHOULD be constant time include: H_1() (hashing arbitrary 959 strings to curves) and DLEQ_Generate(). 960 [I-D.irtf-cfrg-hash-to-curve] describes various algorithms for 961 constant-time implementations of H_1. 963 8.2. Hashing to curves 965 We choose different encodings in relation to the elliptic curve that 966 is used, all methods are illuminated precisely in 967 [I-D.irtf-cfrg-hash-to-curve]. In summary, we use the simplified 968 Shallue-Woestijne-Ulas algorithm for hashing binary strings to the 969 P-256 curve; the Icart algorithm for hashing binary strings to P384; 970 the Elligator2 algorithm for hashing binary strings to CURVE25519 and 971 CURVE448. 973 8.3. Verifiability (key consistency) 975 DLEQ proofs are essential to the protocol to allow V to check that 976 P's designated private key was used in the computation. A side 977 effect of this property is that it prevents P from using a unique key 978 for select verifiers as a way of "tagging" them. If all verifiers 979 expect use of a certain private key, e.g., by locating P's public key 980 published from a trusted registry, then P cannot present unique keys 981 to an individual verifier. 983 For this side effect to hold, P must also be prevented from using 984 other techniques to manipulate their public key within the trusted 985 registry to reduce client anonymity. For example, if P's public key 986 is rotated too frequently then this may stratify the user base into 987 small anonymity groups (those with VOPRF_Sign outputs taken from a 988 given key epoch). In this case, it may become practical to link 989 VOPRF sessions for a given user and thus compromises their privacy. 991 Similarly, if P can publish N public keys to a trusted registry then 992 P may be able to control presentation of these keys in such a way 993 that V is retroactively identified by V's key choice across multiple 994 requests. 996 9. Applications 998 This section describes various applications of the VOPRF protocol. 1000 9.1. Privacy Pass 1002 This VOPRF protocol is used by Privacy Pass system to help Tor users 1003 bypass CAPTCHA challenges. Their system works as follows. Client C 1004 connects - through Tor - to an edge server E serving content. Upon 1005 receipt, E serves a CAPTCHA to C, who then solves the CAPTCHA and 1006 supplies, in response, n blinded points. E verifies the CAPTCHA 1007 response and, if valid, signs (at most) n blinded points, which are 1008 then returned to C along with a batched DLEQ proof. C stores the 1009 tokens if the batched proof verifies correctly. When C attempts to 1010 connect to E again and is prompted with a CAPTCHA, C uses one of the 1011 unblinded and signed points, or tokens, to derive a shared symmetric 1012 key sk used to MAC the CAPTCHA challenge. C sends the CAPTCHA, MAC, 1013 and token input x to E, who can use x to derive sk and verify the 1014 CAPTCHA MAC. Thus, each token is used at most once by the system. 1016 The Privacy Pass implementation uses the P-256 instantiation of the 1017 VOPRF protocol. For more details, see [DGSTV18]. 1019 9.2. Private Password Checker 1021 In this application, let D be a collection of plaintext passwords 1022 obtained by prover P. For each password p in D, P computes 1023 VOPRF_Sign on H_1(p), where H_1 is as described above, and stores the 1024 result in a separate collection D'. P then publishes D' with Y, its 1025 public key. If a client C wishes to query D' for a password p', it 1026 runs the VOPRF protocol using p as input x to obtain output y. By 1027 construction, y will be the signature of p hashed onto the curve. C 1028 can then search D' for y to determine if there is a match. 1030 Examples of such password checkers already exist, for example: 1031 [JKKX16], [JKK14] and [SJKS17]. 1033 9.2.1. Parameter Commitments 1035 For some applications, it may be desirable for P to bind tokens to 1036 certain parameters, e.g., protocol versions, ciphersuites, etc. To 1037 accomplish this, P should use a distinct scalar for each parameter 1038 combination. Upon redemption of a token T from V, P can later verify 1039 that T was generated using the scalar associated with the 1040 corresponding parameters. 1042 10. Acknowledgements 1044 This document resulted from the work of the Privacy Pass team 1045 [PrivacyPass]. The authors would also like to acknowledge the 1046 helpful conversations with Hugo Krawczyk. Eli-Shaoul Khedouri 1047 provided additional review and comments on key consistency. 1049 11. Normative References 1051 [ChaumBlindSignature] 1052 "Blind Signatures for Untraceable Payments", n.d., 1053 . 1056 [ChaumPedersen] 1057 "Wallet Databases with Observers", n.d., 1058 . 1060 [DECAF] "Decaf, Eliminating cofactors through point compression", 1061 n.d., . 1063 [DGSTV18] "Privacy Pass, Bypassing Internet Challenges Anonymously", 1064 n.d., . 1068 [I-D.irtf-cfrg-hash-to-curve] 1069 Scott, S., Sullivan, N., and C. Wood, "Hashing to Elliptic 1070 Curves", draft-irtf-cfrg-hash-to-curve-02 (work in 1071 progress), October 2018. 1073 [JKK14] "Round-Optimal Password-Protected Secret Sharing and 1074 T-PAKE in the Password-Only model", n.d., 1075 . 1077 [JKKX16] "Highly-Efficient and Composable Password-Protected Secret 1078 Sharing (Or, How to Protect Your Bitcoin Wallet Online)", 1079 n.d., . 1081 [NIST] "Keylength - NIST Report on Cryptographic Key Length and 1082 Cryptoperiod (2016)", n.d., 1083 . 1085 [OPAQUE] "The OPAQUE Asymmetric PAKE Protocol", n.d., 1086 . 1089 [PrivacyPass] 1090 "Privacy Pass", n.d., 1091 . 1093 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1094 Requirement Levels", BCP 14, RFC 2119, 1095 DOI 10.17487/RFC2119, March 1997, 1096 . 1098 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 1099 Key Derivation Function (HKDF)", RFC 5869, 1100 DOI 10.17487/RFC5869, May 2010, 1101 . 1103 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 1104 for Security", RFC 7748, DOI 10.17487/RFC7748, January 1105 2016, . 1107 [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital 1108 Signature Algorithm (EdDSA)", RFC 8032, 1109 DOI 10.17487/RFC8032, January 2017, 1110 . 1112 [RISTRETTO] 1113 "The ristretto255 Group", n.d., 1114 . 1117 [SEC2] Standards for Efficient Cryptography Group (SECG), ., "SEC 1118 2: Recommended Elliptic Curve Domain Parameters", n.d., 1119 . 1121 [SHAKE] "SHA-3 Standard, Permutation-Based Hash and Extendable- 1122 Output Functions", n.d., 1123 . 1127 [SJKS17] "SPHINX, A Password Store that Perfectly Hides from 1128 Itself", n.d., 1129 . 1131 Appendix A. Test Vectors 1133 This section includes test vectors for the ECVOPRF-P256-HKDF-SHA256 1134 VOPRF ciphersuite, including batched DLEQ output. 1136 P-256 1137 X: 04b14b08f954f5b6ab1d014b1398f03881d70842acdf06194eb96a6d08186f8cb985c1c5521 \ 1138 f4ee19e290745331f7eb89a4053de0673dc8ef14cfe9bf8226c6b31 1139 r: b72265c85b1ba42cfed7caaf00d2ccac0b1a99259ba0dbb5a1fc2941526a6849 1140 M: 046025a41f81a160c648cfe8fdcaa42e5f7da7a71055f8e23f1dc7e4204ab84b705043ba5c7 \ 1141 000123e1fd058150a4d3797008f57a8b2537766d9419c7396ba5279 1142 k: f84e197c8b712cdf452d2cff52dec1bd96220ed7b9a6f66ed28c67503ae62133 1143 Z: 043ab5ccb690d844dcb780b2d9e59126d62bc853ba01b2c339ba1c1b78c03e4b6adc5402f77 \ 1144 9fc29f639edc138012f0e61960e1784973b37f864e4dc8abbc68e0b 1145 N: 04e8aa6792d859075821e2fba28500d6974ba776fe230ba47ef7e42be1d967654ce776f889e \ 1146 e1f374ffa0bce904408aaa4ed8a19c6cc7801022b7848031f4e442a 1147 D: { s: faddfaf6b5d6b4b6357adf856fc1e0044614ebf9dafdb4c6541c1c9e61243c5b, 1148 c: 8b403e170b56c915cc18864b3ab3c2502bd8f5ca25301bc03ab5138343040c7b } 1150 P-256 1151 X: 047e8d567e854e6bdc95727d48b40cbb5569299e0a4e339b6d707b2da3508eb6c238d3d4cb4 \ 1152 68afc6ffc82fccbda8051478d1d2c9b21ffdfd628506c873ebb1249 1153 r: f222dfe530fdbfcb02eb851867bfa8a6da1664dfc7cee4a51eb6ff83c901e15e 1154 M: 04e2efdc73747e15e38b7a1bb90fe5e4ef964b3b8dccfda428f85a431420c84efca02f0f09c \ 1155 83a8241b44572a059ab49c080a39d0bce2d5d0b44ff5d012b5184e7 1156 k: fb164de0a87e601fd4435c0d7441ff822b5fa5975d0c68035beac05a82c41118 1157 Z: 049d01e1c555bd3324e8ce93a13946b98bdcc765298e6d60808f93c00bdfba2ebf48eef8f28 \ 1158 d8c91c903ad6bea3d840f3b9631424a6cc543a0a0e1f2d487192d5b 1159 N: 04723880e480b60b4415ca627585d1715ab5965570d30c94391a8b023f8854ac26f76c1d6ab \ 1160 bb38688a5affbcadad50ecbf7c93ef33ddfd735003b5a4b1a21ba14 1161 D: { s: dfdf6ae40d141b61d5b2d72cf39c4a6c88db6ac5b12044a70c212e2bf80255b4, 1162 c: 271979a6b51d5f71719127102621fe250e3235867cfcf8dea749c3e253b81997 } 1164 Batched DLEQ (P256) 1165 M_0: 046025a41f81a160c648cfe8fdcaa42e5f7da7a71055f8e23f1dc7e4204ab84b705043ba5c\ 1166 7000123e1fd058150a4d3797008f57a8b2537766d9419c7396ba5279 1167 M_1: 04e2efdc73747e15e38b7a1bb90fe5e4ef964b3b8dccfda428f85a431420c84efca02f0f09\ 1168 c83a8241b44572a059ab49c080a39d0bce2d5d0b44ff5d012b5184e7 1169 Z_0: 043ab5ccb690d844dcb780b2d9e59126d62bc853ba01b2c339ba1c1b78c03e4b6adc5402f7\ 1170 79fc29f639edc138012f0e61960e1784973b37f864e4dc8abbc68e0b 1171 Z_1: 04647e1ab7946b10c1c1c92dd333e2fc9e93e85fdef5939bf2f376ae859248513e0cd91115\ 1172 e48c6852d8dd173956aec7a81401c3f63a133934898d177f2a237eeb 1173 k: f84e197c8b712cdf452d2cff52dec1bd96220ed7b9a6f66ed28c67503ae62133 1174 PRNG: HKDF-SHA256 1175 salt: "DLEQ_PROOF" 1176 info: an iterator i for invoking the PRNG on M_i and Z_i 1177 D: { s: b2123044e633d4721894d573decebc9366869fe3c6b4b79a00311ecfa46c9e34, 1178 c: 3506df9008e60130fcddf86fdb02cbfe4ceb88ff73f66953b1606f6603309862 } 1180 Authors' Addresses 1182 Alex Davidson 1183 Cloudflare 1184 County Hall 1185 London, SE1 7GP 1186 United Kingdom 1188 Email: adavidson@cloudflare.com 1190 Nick Sullivan 1191 Cloudflare 1192 101 Townsend St 1193 San Francisco 1194 United States of America 1196 Email: nick@cloudflare.com 1198 Christopher A. Wood 1199 Apple Inc. 1200 One Apple Park Way 1201 Cupertino, California 95014 1202 United States of America 1204 Email: cawood@apple.com