idnits 2.17.1 draft-irtf-cfrg-voprf-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 13, 2020) is 1383 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '1' on line 1478 -- Looks like a reference, but probably isn't: '2' on line 1480 -- Looks like a reference, but probably isn't: '3' on line 1482 -- Looks like a reference, but probably isn't: '4' on line 1484 -- Looks like a reference, but probably isn't: '0' on line 770 == Unused Reference: 'ChaumBlindSignature' is defined on line 1370, but no explicit reference was found in the text == Unused Reference: 'ChaumPedersen' is defined on line 1375, but no explicit reference was found in the text == Unused Reference: 'DECAF' is defined on line 1383, but no explicit reference was found in the text == Unused Reference: 'JKKX17' is defined on line 1408, but no explicit reference was found in the text == Unused Reference: 'NIST' is defined on line 1417, but no explicit reference was found in the text == Unused Reference: 'RFC2104' is defined on line 1428, but no explicit reference was found in the text == Unused Reference: 'RFC5869' is defined on line 1438, but no explicit reference was found in the text == Unused Reference: 'RISTRETTO' is defined on line 1452, but no explicit reference was found in the text == Unused Reference: 'SHAKE' is defined on line 1464, but no explicit reference was found in the text == Outdated reference: A later version (-16) exists of draft-irtf-cfrg-hash-to-curve-09 Summary: 1 error (**), 0 flaws (~~), 11 warnings (==), 7 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 C. Wood 5 Expires: January 14, 2021 Cloudflare 6 July 13, 2020 8 Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups 9 draft-irtf-cfrg-voprf-04 11 Abstract 13 An Oblivious Pseudorandom Function (OPRF) is a two-party protocol for 14 computing the output of a PRF. One party (the server) holds the PRF 15 secret key, and the other (the client) holds the PRF input. The 16 'obliviousness' property ensures that the server does not learn 17 anything about the client's input during the evaluation. The client 18 should also not learn anything about the server's secret PRF key. 19 Optionally, OPRFs can also satisfy a notion 'verifiability' (VOPRF). 20 In this setting, the client can verify that the server's output is 21 indeed the result of evaluating the underlying PRF with just a public 22 key. This document specifies OPRF and VOPRF constructions 23 instantiated within prime-order groups, including elliptic curves. 25 Status of This Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at https://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on January 14, 2021. 42 Copyright Notice 44 Copyright (c) 2020 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents 49 (https://trustee.ietf.org/license-info) in effect on the date of 50 publication of this document. Please review these documents 51 carefully, as they describe your rights and restrictions with respect 52 to this document. Code Components extracted from this document must 53 include Simplified BSD License text as described in Section 4.e of 54 the Trust Legal Provisions and are provided without warranty as 55 described in the Simplified BSD License. 57 Table of Contents 59 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 60 1.1. Change log . . . . . . . . . . . . . . . . . . . . . . . 3 61 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 5 62 1.3. Requirements . . . . . . . . . . . . . . . . . . . . . . 5 63 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 5 64 2.1. Prime-order group API . . . . . . . . . . . . . . . . . . 5 65 2.2. Other conventions . . . . . . . . . . . . . . . . . . . . 6 66 3. OPRF Protocol . . . . . . . . . . . . . . . . . . . . . . . . 7 67 3.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 8 68 3.2. Context Setup . . . . . . . . . . . . . . . . . . . . . . 8 69 3.3. Data Structures . . . . . . . . . . . . . . . . . . . . . 9 70 3.4. Context APIs . . . . . . . . . . . . . . . . . . . . . . 10 71 3.4.1. Server Context . . . . . . . . . . . . . . . . . . . 10 72 3.4.2. VerifiableServerContext . . . . . . . . . . . . . . . 12 73 3.4.3. Client Context . . . . . . . . . . . . . . . . . . . 16 74 3.4.4. VerifiableClientContext . . . . . . . . . . . . . . . 17 75 4. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 19 76 4.1. OPRF(curve25519, SHA-512) . . . . . . . . . . . . . . . . 20 77 4.2. OPRF(curve448, SHA-512) . . . . . . . . . . . . . . . . . 20 78 4.3. OPRF(P-256, SHA-512) . . . . . . . . . . . . . . . . . . 21 79 4.4. OPRF(P-384, SHA-512) . . . . . . . . . . . . . . . . . . 22 80 4.5. OPRF(P-521, SHA-512) . . . . . . . . . . . . . . . . . . 23 81 5. Security Considerations . . . . . . . . . . . . . . . . . . . 23 82 5.1. Security properties . . . . . . . . . . . . . . . . . . . 24 83 5.2. Cryptographic security . . . . . . . . . . . . . . . . . 25 84 5.2.1. Computational hardness assumptions . . . . . . . . . 25 85 5.2.2. Protocol security . . . . . . . . . . . . . . . . . . 25 86 5.2.3. Q-strong-DH oracle . . . . . . . . . . . . . . . . . 26 87 5.2.4. Implications for ciphersuite choices . . . . . . . . 27 88 5.3. Hashing to curve . . . . . . . . . . . . . . . . . . . . 27 89 5.4. Timing Leaks . . . . . . . . . . . . . . . . . . . . . . 27 90 5.5. Key rotation . . . . . . . . . . . . . . . . . . . . . . 28 91 6. Additive blinding . . . . . . . . . . . . . . . . . . . . . . 28 92 6.1. Preprocess . . . . . . . . . . . . . . . . . . . . . . . 29 93 6.2. Blind . . . . . . . . . . . . . . . . . . . . . . . . . . 29 94 6.3. Unblind . . . . . . . . . . . . . . . . . . . . . . . . . 30 95 6.3.1. Parameter Commitments . . . . . . . . . . . . . . . . 31 96 7. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 31 97 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 31 98 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 31 99 9.1. Normative References . . . . . . . . . . . . . . . . . . 31 100 9.2. URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 34 101 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 34 103 1. Introduction 105 A pseudorandom function (PRF) F(k, x) is an efficiently computable 106 function taking a private key k and a value x as input. This 107 function is pseudorandom if the keyed function K(_) = F(K, _) is 108 indistinguishable from a randomly sampled function acting on the same 109 domain and range as K(). An oblivious PRF (OPRF) is a two-party 110 protocol between a server and a client, where the server holds a PRF 111 key k and the client holds some input x. The protocol allows both 112 parties to cooperate in computing F(k, x) such that: the client 113 learns F(k, x) without learning anything about k; and the server does 114 not learn anything about x. A Verifiable OPRF (VOPRF) is an OPRF 115 wherein the server can prove to the client that F(k, x) was computed 116 using the key k. 118 The usage of OPRFs has been demonstrated in constructing a number of 119 applications: password-protected secret sharing schemes [JKKX16]; 120 privacy-preserving password stores [SJKS17]; and password- 121 authenticated key exchange or PAKE [OPAQUE]. The usage of a VOPRF is 122 necessary in some applications, e.g., the Privacy Pass protocol 123 [draft-davidson-pp-protocol], wherein this VOPRF is used to generate 124 one-time authentication tokens to bypass CAPTCHA challenges. VOPRFs 125 have also been used for password-protected secret sharing schemes 126 e.g. [JKK14]. 128 This document introduces an OPRF protocol built in prime-order 129 groups, applying to finite fields of prime-order and also elliptic 130 curve (EC) groups. The protocol has the option of being extended to 131 a VOPRF with the addition of a NIZK proof for proving discrete log 132 equality relations. This proof demonstrates correctness of the 133 computation, using a known public key that serves as a commitment to 134 the server's secret key. The document describes the protocol, the 135 public-facing API, and its security properties. 137 1.1. Change log 139 draft-04 [1]: 141 o Introduce Client and Server contexts for controlling verifiability 142 and required functionality. 144 o Condense API. 146 o Remove batching from standard functionality (included as an 147 extension) 149 o Add Curve25519 and P-256 ciphersuites for applications that 150 prevent strong-DH oracle attacks. 152 o Provide explicit prime-order group API and instantiation advice 153 for each ciphersuite. 155 o Proof-of-concept implementation in sage. 157 o Remove privacy considerations advice as this depends on 158 applications. 160 draft-03 [2]: 162 o Certify public key during VerifiableFinalize 164 o Remove protocol integration advice 166 o Add text discussing how to perform domain separation 168 o Drop OPRF_/VOPRF_ prefix from algorithm names 170 o Make prime-order group assumption explicit 172 o Changes to algorithms accepting batched inputs 174 o Changes to construction of batched DLEQ proofs 176 o Updated ciphersuites to be consistent with hash-to-curve and added 177 OPRF specific ciphersuites 179 draft-02 [3]: 181 o Added section discussing cryptographic security and static DH 182 oracles 184 o Updated batched proof algorithms 186 draft-01 [4]: 188 o Updated ciphersuites to be in line with 189 https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-04 191 o Made some necessary modular reductions more explicit 193 1.2. Terminology 195 The following terms are used throughout this document. 197 o PRF: Pseudorandom Function. 199 o OPRF: Oblivious Pseudorandom Function. 201 o VOPRF: Verifiable Oblivious Pseudorandom Function. 203 o Client: Protocol initiator. Learns pseudorandom function 204 evaluation as the output of the protocol. 206 o Server: Computes the pseudorandom function over a secret key. 207 Learns nothing about the client's input. 209 o NIZK: Non-interactive zero knowledge. 211 o DLEQ: Discrete Logarithm Equality. 213 1.3. Requirements 215 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 216 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 217 document are to be interpreted as described in [RFC2119]. 219 2. Preliminaries 221 2.1. Prime-order group API 223 In this document, we assume the construction of an additive, prime- 224 order group "GG" for performing all mathematical operations. Such 225 groups are uniquely determined by the choice of the prime "p" that 226 defines the order of the group. We use "GF(p)" to represent the 227 finite field of order "p". For the purpose of understanding and 228 implementing this document, we take "GF(p)" to be equal to the set of 229 integers defined by "{0, 1, ..., p-1}". 231 The fundamental group operation is addition "+" with identity element 232 "I". For any elements "A" and "B" of the group "GG", "A + B = B + A" 233 is also a member of "GG". Also, for any "A" in "GG", it exists an 234 element "-A" such that "A + (-A) = (-A) + A = I". Scalar 235 multiplication is equivalent to the repeated application of the group 236 operation on an element A with itself "r-1" times, this is denoted as 237 "r*A = A + ... + A". Any element "A" holds the equality "p*A=I". 238 The set of scalars corresponds to "GF(p)". 240 We now detail a number of member functions that can be invoked on a 241 prime-order group. 243 o Order(): Outputs the order of the group (i.e. "p"). 245 o Generator(): Outputs a fixed generator "G" for the group. 247 o Identity(): Outputs the identity element of the group (i.e. "I"). 249 o Serialize(A): A member function of "GG" that maps a group element 250 "A" to a unique byte array "buf". 252 o Deserialize(buf): A member function of "GG" that maps a byte array 253 "buf" to a group element "A". 255 o HashToGroup(x): A member function of "GG" that deterministically 256 maps an array of bytes "x" to an element of "GG". The map must 257 ensure that, for any adversary receiving "R = HashToGroup(x)", it 258 is computationally difficult to reverse the mapping. Examples of 259 hash to group functions satisfying this property are described for 260 prime-order (sub)groups of elliptic curves, see 261 [I-D.irtf-cfrg-hash-to-curve]. 263 o HashToScalar(x): A member function of "GG" that deterministically 264 maps an array of bytes "x" to a random element in GF(p). 266 o RandomScalar(): A member function of "GG" that generates a random, 267 non-zero element in GF(p). 269 It is convenient in cryptographic applications to instantiate such 270 prime-order groups using elliptic curves, such as those detailed in 271 [SEC2]. For some choices of elliptic curves (e.g. those detailed in 272 [RFC7748] require accounting for cofactors) there are some 273 implementation issues that introduce inherent discrepancies between 274 standard prime-order groups and the elliptic curve instantiation. In 275 this document, all algorithms that we detail assume that the group is 276 a prime-order group, and this MUST be upheld by any implementer. 277 That is, any curve instantiation should be written such that any 278 discrepancies with a prime-order group instantiation are removed. 279 See Section 4 for advice corresponding to implementation of this 280 interface for specific definitions of elliptic curves. 282 2.2. Other conventions 284 o We use the notation "x <-$ Q" to denote sampling "x" from the 285 uniform distribution over the set "Q". 287 o For any object "x", we write "len(x)" to denote its length in 288 bytes. 290 o For two byte arrays "x" and "y", write "x || y" to denote their 291 concatenation. 293 o We assume that all numbers are stored in big-endian orientation. 295 o I2OSP and OS2IP: Convert a byte array to and from a non-negative 296 integer as described in [RFC8017]. Note that these functions 297 operate on byte arrays in big-endian byte order. 299 All algorithm descriptions are written in a Python-like pseudocode. 300 We use the "ABORT()" function for presentational clarity to denote 301 the process of terminating the algorithm or returning an error 302 accordingly. We also use the "CT_EQUAL(a, b)" function to represent 303 constant-time byte-wise equality between byte arrays "a" and "b". 304 This function returns a boolean "true" if "a" and "b" are equal, and 305 "false" otherwise. 307 3. OPRF Protocol 309 In this section, we define two OPRF variants: a base mode and 310 verifiable mode. In the base mode, a client and server interact to 311 compute y = F(skS, x), where x is the client's input, skS is the 312 server's private key, and y is the OPRF output. The client learns y 313 and the server learns nothing. In the verifiable mode, the client 314 also gets proof that the server used skS in computing the function. 316 To achieve verifiability, as in the original work of [JKK14], we 317 provide a zero-knowledge proof that the key provided as input by the 318 server in the "Evaluate" function is the same key as it used to 319 produce their public key. As an example of the nature of attacks 320 that this prevents, this ensures that the server uses the same 321 private key for computing the VOPRF output and does not attempt to 322 "tag" individual servers with select keys. This proof must not 323 reveal the server's long-term private key to the client. 325 The following one-byte values distinguish between these two modes: 327 +----------+-------+---+----------------+------+ 328 | Mode | Value | | | | 329 +----------+-------+---+----------------+------+ 330 | modeBase | 0x00 | | modeVerifiable | 0x01 | 331 +----------+-------+---+----------------+------+ 333 3.1. Overview 335 Both participants agree on the mode and a choice of ciphersuite that 336 is used before the protocol exchange. Once established, the core 337 protocol runs to compute "output = F(skS, input)" as follows: 339 Client(pkS, input, info) Server(skS, pkS) 340 ---------------------------------------------------------- 341 token, blindToken = Blind(input) 343 blindToken 344 ----------> 346 evaluation = Evaluate(skS, pkS, blindToken) 348 evaluation 349 <---------- 351 issuedToken = Unblind(pkS, token, blindToken, evaluation) 352 output = Finalize(input, issuedToken, info) 354 In "Blind" the client generates a token and blinding data. The 355 server computes the (V)OPRF evaluation in "Evaluation" over the 356 client's blinded token. In "Unblind" the client unblinds the server 357 response (and verifies the server's proof if verifiability is 358 required). In "Finalize", the client outputs a byte array 359 corresponding to its input. 361 Note that in the final output, the client computes Finalize over some 362 auxiliary input data "info". This parameter SHOULD be used for 363 domain separation in the (V)OPRF protocol. Specifically, any system 364 which has multiple (V)OPRF applications should use separate auxiliary 365 values to to ensure finalized outputs are separate. Guidance for 366 constructing info can be found in [I-D.irtf-cfrg-hash-to-curve]; 367 Section 3.1. 369 3.2. Context Setup 371 Both modes of the OPRF involve an offline setup phase. In this 372 phase, both the client and server create a context used for executing 373 the online phase of the protocol. The base mode setup functions for 374 creating client and server contexts are below: 376 def SetupBaseserver(suite): 377 (skS, _) = KeyGen(GG) 378 contextString = I2OSP(modeBase, 1) + I2OSP(suite.ID, 2) 379 return ServerContext(contextString, skS) 381 def SetupBaseClient(suite): 382 contextString = I2OSP(modeBase, 1) + I2OSP(suite.ID, 2) 383 return ClientContext(contextString) 385 The "KeyGen" function used above takes a group "GG" and generates a 386 private and public key pair (skX, pkX), where skX is a random, non- 387 zero element in the scalar field "GG" and pkX is the product of skX 388 and the group's fixed generator. 390 The verifiable mode setup functions for creating client and server 391 contexts are below. 393 def SetupVerifiableserver(suite): 394 (skS, pkS) = KeyGen(GG) 395 contextString = I2OSP(modeVerifiable, 1) + I2OSP(suite.ID, 2) 396 return VerifiableServerContext(contextString, skS), pkS 398 def SetupVerifiableClient(suite, pkS): 399 contextString = I2OSP(modeVerifiable, 1) + I2OSP(suite.ID, 2) 400 return VerifiableClientContext(contextString, pkS) 402 For verifiable modes, servers MUST make the resulting public key 403 "pkS" accessible for clients. (Indeed, it is a required parameter 404 when configuring a verifiable client context.) 406 Each setup function takes a ciphersuite from the list defined in 407 Section 4. Each ciphersuite has two-byte identifier, referred to as 408 "suite.ID" in the pseudocode above, that identifies the suite. 409 Section 4 lists these ciphersuite identifiers. 411 3.3. Data Structures 413 The following is a list of data structures that are defined for 414 providing inputs and outputs for each of the context interfaces 415 defined in Section 3.4. 417 The following types are a list of aliases that are used throughout 418 the protocol. 420 A "ClientInput" is a byte array. 422 opaque ClientInput<1..2^16-1>; 423 A "SerializedElement" is also a byte array, representing the unique 424 serialization of an "Element". 426 opaque SerializedElement<1..2^16-1>; 428 A "Token" is an object created by a client when constructing a 429 (V)OPRF protocol input. It is stored so that it can be used after 430 receiving the server response. 432 struct { 433 opaque data<1..2^16-1>; 434 Scalar blind<1..2^16-1>; 435 } Token; 437 An "Evaluation" is the type output by the "Evaluate" algorithm. The 438 member "proof" is added only in verifiable contexts. 440 struct { 441 SerializedElement element; 442 Scalar proof<0...2^16-1>; /* only for modeVerifiable */ 443 } Evaluation; 445 Evaluations may also be combined in batches with a constant-size 446 proof, producing a "BatchedEvaluation". These carry a list of 447 "SerializedElement" values and proof. These evaluation types are 448 only useful in verifiable contexts which carry proofs. 450 struct { 451 SerializedElement elements<1..2^16-1>; 452 Scalar proof<0...2^16-1>; /* only for modeVerifiable */ 453 } BatchedEvaluation; 455 3.4. Context APIs 457 In this section, we detail the APIs available on the client and 458 server OPRF contexts. This document uses the types "Element" and 459 "Scalar" to denote elements of the group "GG" and its underlying 460 scalar field, respectively. For notational clarity, "PublicKey" and 461 "PrivateKey" are items of type "Element" and "Scalar", respectively. 463 3.4.1. Server Context 465 The ServerContext encapsulates the context string constructed during 466 setup and the OPRF key pair. It has two functions, "Evaluate" and 467 "VerifyFinalize", described below. "Evaluate" takes as input 468 serialized representations of blinded group elements from the client. 469 "VerifyFinalize" takes ClientInput values and their corresponding 470 output digests from "Verify" and returns true if the inputs match the 471 outputs. Note that "VerifyFinalize" is not used in the main OPRF 472 protocol. It is exposed as an API for building higher-level 473 protocols. 475 3.4.1.1. Evaluate 477 Input: 479 PrivateKey skS 480 PublicKey pkS 481 SerializedElement blindedToken 483 Output: 485 Evaluation Ev 487 def Evaluate(skS, pkS, blindedToken): 488 BT = GG.Deserialize(blindedToken) 489 Z = skS * BT 490 serializedElement = GG.Serialize(Z) 492 Ev = Evaluation{ element: serializedElement } 494 return Ev 496 3.4.1.2. VerifyFinalize 497 Input: 499 PrivateKey skS 500 PublicKey pkS 501 ClientInput input 502 opaque info<1..2^16-1> 503 opaque output<1..2^16-1> 505 Output: 507 boolean valid 509 def VerifyFinalize(skS, pkS, input, info, output): 510 T = GG.HashToGroup(input) 511 element = GG.Serialize(T) 512 issuedElement = Evaluate(skS, pkS, [element]) 513 E = GG.Serialize(issuedElement) 515 finalizeDST = "RFCXXXX-Finalize-" + client.contextString 516 hashInput = len(input) || input || 517 len(E) || E || 518 len(info) || info || 519 len(finalizeDST) || finalizeDST 520 digest = Hash(hashInput) 522 return CT_EQUAL(digest, output) 524 3.4.2. VerifiableServerContext 526 The VerifiableServerContext extends the base ServerContext with an 527 augmented "Evaluate()" function. This function produces a proof that 528 "skS" was used in computing the result. It makes use of the helper 529 functions "ComputeComposites" and "GenerateProof", described below. 531 3.4.2.1. Evaluate 532 Input: 534 PrivateKey skS 535 PublicKey pkS 536 SerializedElement blindedToken 538 Output: 540 Evaluation Ev 542 def Evaluate(skS, pkS, blindedToken): 543 BT = GG.Deserialize(blindedToken) 544 Z = skS * BT 545 serializedElement = GG.Serialize(Z) 547 proof = GenerateProof(skS, pkS, blindedToken, serializedElement) 548 Ev = Evaluation{ element: serializedElement, proof: proof } 550 return Ev 552 The helper functions "GenerateProof" and "ComputeComposites" are 553 defined below. 555 3.4.2.2. GenerateProof 556 Input: 558 PrivateKey skS 559 PublicKey pkS 560 SerializedElement blindedToken 561 SerializedElement element 563 Output: 565 Scalar proof[2] 567 def GenerateProof(skS, pkS, blindedToken, element) 568 G = GG.Generator() 569 gen = GG.Serialize(G) 571 blindTokenList = [blindedToken] 572 elementList = [element] 574 (a1, a2) = ComputeComposites(gen, pkS, blindTokenList, elementList) 576 M = GG.Deserialize(a1) 577 r = GG.RandomScalar() 578 a3 = GG.Serialize(r * G) 579 a4 = GG.Serialize(r * M) 581 challengeDST = "RFCXXXX-challenge-" + self.contextString 582 h2Input = I2OSP(len(gen), 2) || gen || 583 I2OSP(len(pkS), 2) || pkS || 584 I2OSP(len(a1), 2) || a1 || I2OSP(len(a2), 2) || a2 || 585 I2OSP(len(a3), 2) || a3 || I2OSP(len(a4), 2) || a4 || 586 I2OSP(len(challengeDST), 2) || challengeDST 588 c = GG.HashToScalar(h2Input) 589 s = (r - c * skS) mod p 591 return (c, s) 593 3.4.2.2.1. Batching inputs 595 Unlike other functions, "ComputeComposites" takes lists of inputs, 596 rather than a single input. It is optimized to produce a constant- 597 size output. This functionality lets applications batch inputs 598 together to produce a constant-size proofs from "GenerateProof". 599 Applications can take advantage of this functionality by invoking 600 "GenerateProof" on batches of inputs. (Notice that in the pseudocode 601 above, the single inputs "blindedToken" and "element" are translated 602 into lists before invoking "ComputeComposites". A batched 603 "GenerateProof" variant would permit lists of inputs, and no list 604 translation would be needed.) 606 Note that using batched inputs creates a "BatchedEvaluation" object 607 as the output of "Evaluate". 609 3.4.2.2.2. Fresh randomness 611 We note here that it is essential that a different r value is used 612 for every invocation. If this is not done, then this may leak "skS" 613 as is possible in Schnorr or (EC)DSA scenarios where fresh randomness 614 is not used. 616 3.4.2.3. ComputeComposites 618 Input: 620 SerializedElement gen 621 PublicKey pkS 622 SerializedElement blindedTokens[m] 623 SerializedElement elements[m] 625 Output: 627 SerializedElement composites[2] 629 def ComputeComposites(gen, pkS, blindedTokens, elements): 630 seedDST = "RFCXXXX-seed-" + self.contextString 631 compositeDST = "RFCXXXX-composite-" + self.contextString 632 h1Input = I2OSP(len(gen), 2) || gen || 633 I2OSP(len(pkS), 2) || pkS || 634 I2OSP(len(blindedTokens), 2) || blindedTokens || 635 I2OSP(len(elements), 2) || elements || 636 I2OSP(len(seedDST), 2) || seedDST 638 seed = Hash(h1Input) 639 M = GG.Identity() 640 Z = GG.Identity() 641 for i = 0 to m: 642 h2Input = I2OSP(len(seed), 2) || seed || I2OSP(i, 2) || 643 I2OSP(len(compositeDST), 2) || compositeDST 644 di = GG.HashToScalar(h2Input) 645 Mi = GG.Deserialize(blindedTokens[i]) 646 Zi = GG.Deserialize(elements[i]) 647 M = di * Mi + M 648 Z = di * Zi + Z 649 return [GG.Serialize(M), GG.Serialize(Z)] 651 3.4.3. Client Context 653 The ClientContext encapsulates the context string constructed during 654 setup. It has three functions, "Blind()", "Unblind()", and 655 "Finalize()", as described below. 657 3.4.3.1. Blind 659 We note here that the blinding mechanism that we use can be modified 660 slightly with the opportunity for making performance gains in some 661 scenarios. We detail these modifications in Section 6. 663 Input: 665 ClientInput input 667 Output: 669 Token token 670 SerializedElement blindedToken 672 def Blind(input): 673 r = GG.RandomScalar() 674 P = GG.HashToGroup(input) 675 blindedToken = GG.Serialize(r * P) 677 token = Token{ data: input, blind: r } 679 return (token, blindedToken) 681 3.4.3.2. Unblind 682 Input: 684 PublicKey pkS 685 Token token 686 SerializedElement blindedToken 687 Evaluation Ev 689 Output: 691 SerializedElement unblindedToken 693 def Unblind(pkS, token, blindedToken, Ev): 694 r = token.blind 695 Z = GG.Deserialize(Ev.element) 696 N = (r^(-1)) * Z 698 unblindedToken = GG.Serialize(N) 700 return unblindedToken 702 3.4.3.3. Finalize 704 Input: 706 Token T 707 SerializedElement E 708 opaque info<1..2^16-1> 710 Output: 712 opaque output<1..2^16-1> 714 def Finalize(T, E, info): 715 finalizeDST = "RFCXXXX-Finalize-" + self.contextString 716 hashInput = len(T.data) || T.data || 717 len(E) || E || 718 len(info) || info || 719 len(finalizeDST) || finalizeDST 720 return Hash(hashInput) 722 3.4.4. VerifiableClientContext 724 The VerifiableClientContext extends the base ClientContext with the 725 desired server public key "pkS" with an augmented "Unblind()" 726 function. This function verifies an evaluation proof using "pkS". 727 It makes use of the helper function "ComputeComposites" described 728 above. It has one helper function, "VerifyProof()", defined below. 730 3.4.4.1. VerifyProof 732 This algorithm outputs a boolean "verified" which indicates whether 733 the proof inside of the evaluation verifies correctly, or not. 735 Input: 737 PublicKey pkS 738 SerializedElement blindedToken 739 Evaluation Ev 741 Output: 743 boolean verified 745 def VerifyProof(pkS, blindedToken, Ev): 746 G = GG.Generator() 747 gen = GG.Serialize(G) 749 blindTokenList = [blindedToken] 750 elementList = [Ev.element] 752 (a1, a2) = ComputeComposites(gen, pkS, blindTokenList, elementList) 754 A' = (Ev.proof[1] * G + Ev.proof[0] * pkS) 755 B' = (Ev.proof[1] * M + Ev.proof[0] * Z) 756 a3 = GG.Serialize(A') 757 a4 = GG.Serialize(B') 759 challengeDST = "RFCXXXX-challenge-" + self.contextString 760 h2Input = I2OSP(len(gen), 2) || gen || 761 I2OSP(len(pkS), 2) || pkS || 762 I2OSP(len(a1), 2) || a1 || 763 I2OSP(len(a2), 2) || a2 || 764 I2OSP(len(a3), 2) || a3 || 765 I2OSP(len(a4), 2) || a4 || 766 I2OSP(len(challengeDST), 2) || challengeDST 768 c = GG.HashToScalar(h2Input) 770 return CT_EQUAL(c, Ev.proof[0]) 772 3.4.4.2. Unblind 773 Input: 775 PublicKey pkS 776 Token token 777 SerializedElement blindedToken 778 Evaluation Ev 780 Output: 782 SerializedElement unblindedToken 784 def Unblind(pkS, token, blindedToken, Ev): 785 if VerifyProof(pkS, blindedToken, Ev) == false: 786 ABORT() 788 r = token.blind 789 Z = GG.Deserialize(Ev.element) 790 N = (r^(-1)) * Z 792 unblindedToken = GG.Serialize(N) 794 return unblindedToken 796 4. Ciphersuites 798 A ciphersuite for the protocol wraps the functionality required for 799 the protocol to take place. This ciphersuite should be available to 800 both the client and server, and agreement on the specific 801 instantiation is assumed throughout. A ciphersuite contains 802 instantiations of the following functionalities. 804 o "GG": A prime-order group exposing the API detailed in 805 Section 2.1. 807 o "Hash": A cryptographic hash function that is indifferentiable 808 from a Random Oracle. 810 This section specifies supported VOPRF group and hash function 811 instantiations. For each group, we specify the HashToGroup and 812 Serialize functionalities. The Deserialize functionality is the 813 inverse of the corresponding Serialize functionality. 815 We only provide ciphersuites in the elliptic curve setting as these 816 provide the most efficient way of instantiating the OPRF. 818 Applications should take caution in using ciphersuites targeting 819 P-256 and curve25519. See Section 5.2 for related discussion. 821 [[OPEN ISSUE: Replace Curve25519 and Curve448 with Ristretto/Decaf]] 823 4.1. OPRF(curve25519, SHA-512) 825 o Group: 827 * Elliptic curve: curve25519 [RFC7748] 829 * Generator(): Return the point with the following affine 830 coordinates: 832 + x = "09" 834 + y = "5F51E65E475F794B1FE122D388B72EB36DC2B28192839E4DD6163A5 835 D81312C14" 837 * HashToGroup(): curve25519_XMD:SHA-512_ELL2_RO_ 838 [I-D.irtf-cfrg-hash-to-curve] with DST "RFCXXXX- 839 curve25519_XMD:SHA-512_ELL2_RO_" 841 * Serialization: The standard 32-byte representation of the 842 public key [RFC7748] 844 * Order(): Returns "1000000000000000000000000000000014DEF9DEA2F79 845 CD65812631A5CF5D3ED" 847 * Addition: Adding curve points directly corresponds to the group 848 addition operation. 850 * Deserialization: Implementers must check for each untrusted 851 input point whether it's a member of the big prime-order 852 subgroup of the curve. This can be done by scalar multiplying 853 the point by Order() and checking whether it's zero. 855 o Hash: SHA-512 857 o ID: 0x0001 859 4.2. OPRF(curve448, SHA-512) 861 o Group: 863 * Elliptic curve: curve448 [RFC7748] 865 * Generator(): Return the point with the following affine 866 coordinates: 868 + x = "05" 869 + y = "7D235D1295F5B1F66C98AB6E58326FCECBAE5D34F55545D060F75DC 870 28DF3F6EDB8027E2346430D211312C4B150677AF76FD7223D457B5B1A" 872 * HashToGroup(): curve448_XMD:SHA-512_ELL2_RO_ 873 [I-D.irtf-cfrg-hash-to-curve] with DST "RFCXXXX- 874 curve448_XMD:SHA-512_ELL2_RO_" 876 * Serialization: The standard 56-byte representation of the 877 public key [RFC7748] 879 * Order(): Returns "3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 880 FFFFFFFFFFF7CCA23E9C44EDB49AED63690216CC2728DC58F552378C292AB58 881 44F3" 883 * Addition: Adding curve points directly corresponds to the group 884 addition operation. 886 * Deserialization: Implementers must check for each untrusted 887 input point whether it's a member of the big prime-order 888 subgroup of the curve. This can be done by scalar multiplying 889 the point by Order() and checking whether it's zero. 891 o Hash: SHA-512 893 o ID: 0x0002 895 4.3. OPRF(P-256, SHA-512) 897 o Group: 899 * Elliptic curve: P-256 (secp256r1) [x9.62] 901 * Generator(): Return the point with the following affine 902 coordinates: 904 + x = "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A1394 905 5D898C296" 907 + y = "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406 908 837BF51F5" 910 * HashToGroup(): P256_XMD:SHA-256_SSWU_RO_ 911 [I-D.irtf-cfrg-hash-to-curve] with DST "RFCXXXX-P256_XMD:SHA- 912 256_SSWU_RO_" 914 * Serialization: The compressed point encoding for the curve 915 [SEC1] consisting of 33 bytes. 917 * Order(): Returns "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179 918 E84F3B9CAC2FC632551" 920 * Addition: Adding curve points directly corresponds to the group 921 addition operation. 923 * Scalar multiplication: Scalar multiplication of curve points 924 directly corresponds with scalar multiplication in the group. 926 o Hash: SHA-512 928 o ID: 0x0003 930 4.4. OPRF(P-384, SHA-512) 932 o Group: 934 * Elliptic curve: P-384 (secp384r1) [x9.62] 936 * Generator(): Return the point with the following affine 937 coordinates: 939 + x = "AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E 940 082542A385502F25DBF55296C3A545E3872760AB7" 942 + y = "3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA311 943 3B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F" 945 * HashToGroup(): P384_XMD:SHA-512_SSWU_RO_ 946 [I-D.irtf-cfrg-hash-to-curve] with DST "RFCXXXX-P384_XMD:SHA- 947 512_SSWU_RO_" 949 * Serialization: The compressed point encoding for the curve 950 [SEC1] consisting of 49 bytes. 952 * Order(): Returns "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 953 FFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973" 955 * Addition: Adding curve points directly corresponds to the group 956 addition operation. 958 * Scalar multiplication: Scalar multiplication of curve points 959 directly corresponds with scalar multiplication in the group. 961 o Hash: SHA-512 963 o ID: 0x0004 965 4.5. OPRF(P-521, SHA-512) 967 o Group: 969 * Elliptic curve: P-521 (secp521r1) [x9.62] 971 * Generator(): Return the point with the following affine 972 coordinates: 974 + x = "00C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F82 975 8AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429 976 BF97E7E31C2E5BD66" 978 + y = "011839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817A 979 FBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24 980 088BE94769FD16650" 982 * HashToGroup(): P521_XMD:SHA-512_SSWU_RO_ 983 [I-D.irtf-cfrg-hash-to-curve] with DST "RFCXXXX-P521_XMD:SHA- 984 512_SSWU_RO_" 986 * Serialization: The compressed point encoding for the curve 987 [SEC1] consisting of 67 bytes. 989 * Order(): Returns "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF 990 FFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B88 991 99C47AEBB6FB71E91386409" 993 * Addition: Adding curve points directly corresponds to the group 994 addition operation. 996 * Scalar multiplication: Scalar multiplication of curve points 997 directly corresponds with scalar multiplication in the group. 999 o Hash: SHA-512 1001 o ID: 0x0005 1003 5. Security Considerations 1005 This section discusses the cryptographic security of our protocol, 1006 along with some suggestions and trade-offs that arise from the 1007 implementation of an OPRF. 1009 5.1. Security properties 1011 The security properties of an OPRF protocol with functionality y = 1012 F(k, x) include those of a standard PRF. Specifically: 1014 o Pseudorandomness: F is pseudorandom if the output y = F(k,x) on 1015 any input x is indistinguishable from uniformly sampling any 1016 element in F's range, for a random sampling of k. 1018 In other words, consider an adversary that picks inputs x from the 1019 domain of F and evaluates F on (k,x) (without knowledge of randomly 1020 sampled k). Then the output distribution F(k,x) is indistinguishable 1021 from the output distribution of a randomly chosen function with the 1022 same domain and range. 1024 A consequence of showing that a function is pseudorandom, is that it 1025 is necessarily non-malleable (i.e. we cannot compute a new evaluation 1026 of F from an existing evaluation). A genuinely random function will 1027 be non-malleable with high probability, and so a pseudorandom 1028 function must be non-malleable to maintain indistinguishability. 1030 An OPRF protocol must also satisfy the following property: 1032 o Oblivious: The server must learn nothing about the client's input 1033 or the output of the function. In addition, the client must learn 1034 nothing about the server's private key. 1036 Essentially, obliviousness tells us that, even if the server learns 1037 the client's input x at some point in the future, then the server 1038 will not be able to link any particular OPRF evaluation to x. This 1039 property is also known as unlinkability [DGSTV18]. 1041 Optionally, for any protocol that satisfies the above properties, 1042 there is an additional security property: 1044 o Verifiable: The client must only complete execution of the 1045 protocol if it can successfully assert that the OPRF output it 1046 computes is correct. This is taken with respect to the OPRF key 1047 held by the server. 1049 Any OPRF that satisfies the 'verifiable' security property is known 1050 as a verifiable OPRF, or VOPRF for short. In practice, the notion of 1051 verifiability requires that the server commits to the key before the 1052 actual protocol execution takes place. Then the client verifies that 1053 the server has used the key in the protocol using this commitment. 1054 In the following, we may also refer to this commitment as a public 1055 key. 1057 5.2. Cryptographic security 1059 Below, we discuss the cryptographic security of the (V)OPRF protocol 1060 from Section 3, relative to the necessary cryptographic assumptions 1061 that need to be made. 1063 5.2.1. Computational hardness assumptions 1065 Each assumption states that the problems specified below are 1066 computationally difficult to solve in relation to a particular choice 1067 of security parameter "sp". 1069 Let GG = GG(sp) be a group with prime-order p, and let FFp be the 1070 finite field of order p. 1072 5.2.1.1. Discrete-log (DL) problem 1074 Given G, a generator of GG, and H = hG for some h in FFp; output h. 1076 5.2.1.2. Decisional Diffie-Hellman (DDH) problem 1078 Sample a uniformly random bit d in {0,1}. Given (G, aG, bG, C), 1079 where: 1081 o G is a generator of GG; 1083 o a,b are elements of FFp; 1085 o if d == 0: C = abG; else: C is sampled uniformly GG(sp). 1087 Output d' == d. 1089 5.2.2. Protocol security 1091 Our OPRF construction is based on the VOPRF construction known as 1092 2HashDH-NIZK given by [JKK14]; essentially without providing zero- 1093 knowledge proofs that verify that the output is correct. Our VOPRF 1094 construction is identical to the [JKK14] construction, except that we 1095 can optionally perform multiple VOPRF evaluations in one go, whilst 1096 only constructing one NIZK proof object. This is enabled using an 1097 established batching technique. 1099 Consequently the cryptographic security of our construction is based 1100 on the assumption that the One-More Gap DH is computationally 1101 difficult to solve. 1103 The (N,Q)-One-More Gap DH (OMDH) problem asks the following. 1105 Given: 1106 - G, k * G, G_1, ... , G_N where G, G_1, ... G_N are elements of GG; 1107 - oracle access to an OPRF functionality using the key k; 1108 - oracle access to DDH solvers. 1110 Find Q+1 pairs of the form below: 1112 (G_{j_s}, k * G_{j_s}) 1114 where the following conditions hold: 1115 - s is a number between 1 and Q+1; 1116 - j_s is a number between 1 and N for each s; 1117 - Q is the number of allowed queries. 1119 The original paper [JKK14] gives a security proof that the 2HashDH- 1120 NIZK construction satisfies the security guarantees of a VOPRF 1121 protocol Section 5.1 under the OMDH assumption in the universal 1122 composability (UC) security model. 1124 5.2.3. Q-strong-DH oracle 1126 A side-effect of our OPRF design is that it allows instantiation of a 1127 oracle for constructing Q-strong-DH (Q-sDH) samples. The Q-Strong-DH 1128 problem asks the following. 1130 Given G1, G2, h*G2, (h^2)*G2, ..., (h^Q)*G2; for G1 and G2 1131 generators of GG. 1133 Output ( (1/(k+c))*G1, c ) where c is an element of FFp 1135 The assumption that this problem is hard was first introduced in 1136 [BB04]. Since then, there have been a number of cryptanalytic 1137 studies that have reduced the security of the assumption below that 1138 implied by the group instantiation (for example, [BG04] and 1139 [Cheon06]). In summary, the attacks reduce the security of the group 1140 instantiation by log_2(Q) bits. 1142 As an example, suppose that a group instantiation is used that 1143 provides 128 bits of security against discrete log cryptanalysis. 1144 Then an adversary with access to a Q-sDH oracle and makes Q=2^20 1145 queries can reduce the security of the instantiation by log_2(2^20) = 1146 20 bits. 1148 Notice that it is easy to instantiate a Q-sDH oracle using the OPRF 1149 functionality that we provide. A client can just submit sequential 1150 queries of the form (G, k * G, (k^2)G, ..., (k^(Q-1))G), where each 1151 query is the output of the previous interaction. This means that any 1152 client that submit Q queries to the OPRF can use the aforementioned 1153 attacks to reduce security of the group instantiation by log_2(Q) 1154 bits. 1156 Recall that from a malicious client's perspective, the adversary wins 1157 if they can distinguish the OPRF interaction from a protocol that 1158 computes the ideal functionality provided by the PRF. 1160 5.2.4. Implications for ciphersuite choices 1162 The OPRF instantiations that we recommend in this document are 1163 informed by the cryptanalytic discussion above. In particular, 1164 choosing elliptic curves configurations that describe 128-bit group 1165 instantiations would appear to in fact instantiate an OPRF with 1166 128-log_2(Q) bits of security. 1168 In most cases, it would require an informed and persistent attacker 1169 to launch a highly expensive attack to reduce security to anything 1170 much below 100 bits of security. We see this possibility as 1171 something that may result in problems in the future. For 1172 applications that cannot tolerate discrete logarithm security of 1173 lower than 128 bits, we recommend only implementing ciphersuites with 1174 IDs: 0x0002, 0x0004, and 0x0005. 1176 5.3. Hashing to curve 1178 A critical requirement of implementing the prime-order group using 1179 elliptic curves is a method to instantiate the function 1180 "GG.HashToGroup", that maps inputs to group elements. In the 1181 elliptic curve setting, this deterministically maps inputs x (as byte 1182 arrays) to uniformly chosen points in the curve. 1184 In the security proof of the construction Hash is modeled as a random 1185 oracle. This implies that any instantiation of "GG.HashToGroup" must 1186 be pre-image and collision resistant. In Section 4 we give 1187 instantiations of this functionality based on the functions described 1188 in [I-D.irtf-cfrg-hash-to-curve]. Consequently, any OPRF 1189 implementation must adhere to the implementation and security 1190 considerations discussed in [I-D.irtf-cfrg-hash-to-curve] when 1191 instantiating the function. 1193 5.4. Timing Leaks 1195 To ensure no information is leaked during protocol execution, all 1196 operations that use secret data MUST be constant time. Operations 1197 that SHOULD be constant time include all prime-order group operations 1198 and proof-specific operations ("GenerateProof()" and 1199 "VerifyProof()"). 1201 5.5. Key rotation 1203 Since the server's key is critical to security, the longer it is 1204 exposed by performing (V)OPRF operations on client inputs, the longer 1205 it is possible that the key can be compromised. For example,if the 1206 key is kept in circulation for a long period of time, then it also 1207 allows the clients to make enough queries to launch more powerful 1208 variants of the Q-sDH attacks from Section 5.2.3. 1210 To combat attacks of this nature, regular key rotation should be 1211 employed on the server-side. A suitable key-cycle for a key used to 1212 compute (V)OPRF evaluations would be between one week and six months. 1214 6. Additive blinding 1216 Let "H" refer to the function "GG.HashToGroup", in Section 2.1 we 1217 assume that the client-side blinding is carried out directly on the 1218 output of "H(x)", i.e. computing "r * H(x)" for some "r <-$ GF(p)". 1219 In the [OPAQUE] document, it is noted that it may be more efficient 1220 to use additive blinding (rather than multiplicative) if the client 1221 can preprocess some values. For example, a valid way of computing 1222 additive blinding would be to instead compute "H(x) + (r * G)", where 1223 "G" is the fixed generator for the group "GG". 1225 The advantage of additive blinding is that it allows the client to 1226 pre-process tables of blinded scalar multiplications for "G". This 1227 may give it a computational efficiency advantage (due to the fact 1228 that a fixed-base multiplication can be calculated faster than a 1229 variable-base multiplication). Pre-processing also reduces the 1230 amount of computation that needs to be done in the online exchange. 1231 Choosing one of these values "r * G" (where "r" is the scalar value 1232 that is used), then computing "H(x) + (r * G)" is more efficient than 1233 computing "r * H(x)". Therefore, it may be advantageous to define 1234 the OPRF and VOPRF protocols using additive blinding (rather than 1235 multiplicative) blinding. In fact, the only algorithms that need to 1236 change are Blind and Unblind (and similarly for the VOPRF variants). 1238 We define the variants of the algorithms in Section 3.4 for 1239 performing additive blinding below, along with a new algorithm 1240 "Preprocess". The "Preprocess" algorithm can take place offline and 1241 before the rest of the OPRF protocol. The Blind algorithm takes the 1242 preprocessed values as inputs, but the signature of Unblind remains 1243 the same. 1245 6.1. Preprocess 1247 struct { 1248 Scalar blind; 1249 SerializedElement blindedGenerator; 1250 SerializedElement blindedPublicKey; 1251 } PreprocessedBlind; 1253 Input: 1255 PublicKey pkS 1257 Output: 1259 PrepocessedBlind preproc 1261 def Preprocess(pkS): 1262 PK = GG.Deserialize(pkS) 1263 r = GG.RandomScalar() 1264 blindedGenerator = GG.Serialize(r * GG.Generator()) 1265 blindedPublicKey = GG.Serialize(r * PK) 1267 preproc = PrepocessedBlind{ 1268 blind: r, 1269 blindedGenerator: blindedGenerator, 1270 blindedPublicKey: blindedPublicKey, 1271 } 1273 return preproc 1275 6.2. Blind 1276 Input: 1278 ClientInput input 1279 PreprocessedBlind preproc 1281 Output: 1283 Token token 1284 SerializedElement blindedToken 1286 def Blind(input, preproc): 1287 Q = GG.Deserialize(preproc.blindedGenerator) /* Q = r * G */ 1288 P = GG.HashToGroup(input) 1290 token = Token{ 1291 data: input, 1292 blind: preproc.blindedPublicKey 1293 } 1294 blindedToken = GG.Serialize(P + Q) /* P + r * G */ 1296 return (token, blindedToken) 1298 6.3. Unblind 1300 Input: 1302 Token token 1303 Evaluation ev 1304 SerializedElement blindedToken 1306 Output: 1308 SerializedElement unblinded 1310 def Unblind(token, ev, blindedToken): 1311 PKR = GG.Deserialize(token.blind) 1312 Z = GG.Deserialize(ev.element) 1313 N := Z - PKR 1315 unblindedToken = GG.Serialize(N) 1317 return unblindedToken 1319 Let "P = GG.HashToGroup(x)". Notice that Unblind computes: 1321 Z - PKR = k * (P + r * G) - r * pkS 1322 = k * P + k * (r * G) - r * (k * G) 1323 = k * P 1325 by the commutativity of scalar multiplication in GG. This is the 1326 same output as in the "Unblind" algorithm for multiplicative 1327 blinding. 1329 Note that the verifiable variant of "Unblind" works as above but 1330 includes the step to "VerifyProof", as specified in Section 3.4.4. 1332 6.3.1. Parameter Commitments 1334 For some applications, it may be desirable for server to bind tokens 1335 to certain parameters, e.g., protocol versions, ciphersuites, etc. 1336 To accomplish this, server should use a distinct scalar for each 1337 parameter combination. Upon redemption of a token T from the client, 1338 server can later verify that T was generated using the scalar 1339 associated with the corresponding parameters. 1341 7. Contributors 1343 o Alex Davidson (alex.davidson92@gmail.com) 1345 o Nick Sullivan (nick@cloudflare.com) 1347 o Chris Wood (caw@heapingbits.net) 1349 o Eli-Shaoul Khedouri (eli@intuitionmachines.com) 1351 o Armando Faz Hernandez (armfazh@cloudflare.com) 1353 8. Acknowledgements 1355 This document resulted from the work of the Privacy Pass team 1356 [PrivacyPass]. The authors would also like to acknowledge the 1357 helpful conversations with Hugo Krawczyk. Eli-Shaoul Khedouri 1358 provided additional review and comments on key consistency. 1360 9. References 1362 9.1. Normative References 1364 [BB04] "Short Signatures Without Random Oracles", 1365 . 1367 [BG04] "The Static Diffie-Hellman Problem", 1368 . 1370 [ChaumBlindSignature] 1371 "Blind Signatures for Untraceable Payments", 1372 . 1375 [ChaumPedersen] 1376 "Wallet Databases with Observers", 1377 . 1379 [Cheon06] "Security Analysis of the Strong Diffie-Hellman Problem", 1380 . 1383 [DECAF] "Decaf, Eliminating cofactors through point compression", 1384 . 1386 [DGSTV18] "Privacy Pass, Bypassing Internet Challenges Anonymously", 1387 . 1390 [draft-davidson-pp-protocol] 1391 Davidson, A., "Privacy Pass: The Protocol", n.d., 1392 . 1395 [I-D.irtf-cfrg-hash-to-curve] 1396 Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R., and 1397 C. Wood, "Hashing to Elliptic Curves", draft-irtf-cfrg- 1398 hash-to-curve-09 (work in progress), June 2020. 1400 [JKK14] "Round-Optimal Password-Protected Secret Sharing and 1401 T-PAKE in the Password-Only model", 1402 . 1404 [JKKX16] "Highly-Efficient and Composable Password-Protected Secret 1405 Sharing (Or, How to Protect Your Bitcoin Wallet Online)", 1406 . 1408 [JKKX17] "TOPPSS: Cost-minimal Password-Protected Secret Sharing 1409 based on Threshold OPRF", 1410 . 1412 [keytrans] 1413 "Security Through Transparency", 1414 . 1417 [NIST] "Keylength - NIST Report on Cryptographic Key Length and 1418 Cryptoperiod (2016)", . 1420 [OPAQUE] "The OPAQUE Asymmetric PAKE Protocol", 1421 . 1424 [PrivacyPass] 1425 "Privacy Pass", 1426 . 1428 [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 1429 Hashing for Message Authentication", RFC 2104, 1430 DOI 10.17487/RFC2104, February 1997, 1431 . 1433 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1434 Requirement Levels", BCP 14, RFC 2119, 1435 DOI 10.17487/RFC2119, March 1997, 1436 . 1438 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 1439 Key Derivation Function (HKDF)", RFC 5869, 1440 DOI 10.17487/RFC5869, May 2010, 1441 . 1443 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 1444 for Security", RFC 7748, DOI 10.17487/RFC7748, January 1445 2016, . 1447 [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, 1448 "PKCS #1: RSA Cryptography Specifications Version 2.2", 1449 RFC 8017, DOI 10.17487/RFC8017, November 2016, 1450 . 1452 [RISTRETTO] 1453 "The ristretto255 Group", . 1456 [SEC1] Standards for Efficient Cryptography Group (SECG), ., "SEC 1457 1: Elliptic Curve Cryptography", 1458 . 1460 [SEC2] Standards for Efficient Cryptography Group (SECG), ., "SEC 1461 2: Recommended Elliptic Curve Domain Parameters", 1462 . 1464 [SHAKE] "SHA-3 Standard, Permutation-Based Hash and Extendable- 1465 Output Functions", . 1469 [SJKS17] "SPHINX, A Password Store that Perfectly Hides from 1470 Itself", . 1472 [x9.62] ANSI, "Public Key Cryptography for the Financial Services 1473 Industry: the Elliptic Curve Digital Signature Algorithm 1474 (ECDSA)", ANSI X9.62-1998, September 1998. 1476 9.2. URIs 1478 [1] https://tools.ietf.org/html/draft-irtf-cfrg-voprf-04 1480 [2] https://tools.ietf.org/html/draft-irtf-cfrg-voprf-03 1482 [3] https://tools.ietf.org/html/draft-irtf-cfrg-voprf-02 1484 [4] https://tools.ietf.org/html/draft-irtf-cfrg-voprf-01 1486 Authors' Addresses 1488 Alex Davidson 1489 Cloudflare 1490 County Hall 1491 London, SE1 7GP 1492 United Kingdom 1494 Email: alex.davidson92@gmail.com 1496 Nick Sullivan 1497 Cloudflare 1498 101 Townsend St 1499 San Francisco 1500 United States of America 1502 Email: nick@cloudflare.com 1503 Christopher A. Wood 1504 Cloudflare 1505 101 Townsend St 1506 San Francisco 1507 United States of America 1509 Email: caw@heapingbits.net