idnits 2.17.1 draft-irtf-cfrg-voprf-05.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 is 1 instance of too long lines in the document, the longest one being 2 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 (2 November 2020) is 1242 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: '2' on line 684 -- Looks like a reference, but probably isn't: '0' on line 820 -- Looks like a reference, but probably isn't: '1' on line 813 == Outdated reference: A later version (-16) exists of draft-irtf-cfrg-hash-to-curve-10 == Outdated reference: A later version (-14) exists of draft-irtf-cfrg-opaque-00 == Outdated reference: A later version (-08) exists of draft-irtf-cfrg-ristretto255-decaf448-00 Summary: 2 errors (**), 0 flaws (~~), 4 warnings (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group A. Davidson 3 Internet-Draft A. Faz-Hernandez 4 Intended status: Informational N. Sullivan 5 Expires: 6 May 2021 C.A. Wood 6 Cloudflare 7 2 November 2020 9 Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups 10 draft-irtf-cfrg-voprf-05 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 Discussion Venues 28 This note is to be removed before publishing as an RFC. 30 Source for this draft and an issue tracker can be found at 31 https://github.com/cfrg/draft-irtf-cfrg-voprf. 33 Status of This Memo 35 This Internet-Draft is submitted in full conformance with the 36 provisions of BCP 78 and BCP 79. 38 Internet-Drafts are working documents of the Internet Engineering 39 Task Force (IETF). Note that other groups may also distribute 40 working documents as Internet-Drafts. The list of current Internet- 41 Drafts is at https://datatracker.ietf.org/drafts/current/. 43 Internet-Drafts are draft documents valid for a maximum of six months 44 and may be updated, replaced, or obsoleted by other documents at any 45 time. It is inappropriate to use Internet-Drafts as reference 46 material or to cite them other than as "work in progress." 48 This Internet-Draft will expire on 6 May 2021. 50 Copyright Notice 52 Copyright (c) 2020 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 57 license-info) in effect on the date of publication of this document. 58 Please review these documents carefully, as they describe your rights 59 and restrictions with respect to this document. Code Components 60 extracted from this document must include Simplified BSD License text 61 as described in Section 4.e of the Trust Legal Provisions and are 62 provided without warranty as described in the Simplified BSD License. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 67 1.1. Change log . . . . . . . . . . . . . . . . . . . . . . . 4 68 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 5 69 1.3. Requirements . . . . . . . . . . . . . . . . . . . . . . 5 70 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 6 71 2.1. Prime-order group API . . . . . . . . . . . . . . . . . . 6 72 2.2. Other conventions . . . . . . . . . . . . . . . . . . . . 7 73 3. OPRF Protocol . . . . . . . . . . . . . . . . . . . . . . . . 8 74 3.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 8 75 3.2. Context Setup . . . . . . . . . . . . . . . . . . . . . . 9 76 3.3. Data Structures . . . . . . . . . . . . . . . . . . . . . 10 77 3.4. Context APIs . . . . . . . . . . . . . . . . . . . . . . 11 78 3.4.1. Server Context . . . . . . . . . . . . . . . . . . . 11 79 3.4.2. VerifiableServerContext . . . . . . . . . . . . . . . 13 80 3.4.3. Client Context . . . . . . . . . . . . . . . . . . . 16 81 3.4.4. VerifiableClientContext . . . . . . . . . . . . . . . 18 82 4. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 20 83 4.1. OPRF(ristretto255, SHA-256) . . . . . . . . . . . . . . . 21 84 4.2. OPRF(decaf448, SHA-512) . . . . . . . . . . . . . . . . . 21 85 4.3. OPRF(P-256, SHA-256) . . . . . . . . . . . . . . . . . . 22 86 4.4. OPRF(P-384, SHA-512) . . . . . . . . . . . . . . . . . . 22 87 4.5. OPRF(P-521, SHA-512) . . . . . . . . . . . . . . . . . . 22 88 5. Security Considerations . . . . . . . . . . . . . . . . . . . 23 89 5.1. Security properties . . . . . . . . . . . . . . . . . . . 23 90 5.2. Cryptographic security . . . . . . . . . . . . . . . . . 24 91 5.2.1. Computational hardness assumptions . . . . . . . . . 24 92 5.2.2. Protocol security . . . . . . . . . . . . . . . . . . 25 93 5.2.3. Q-strong-DH oracle . . . . . . . . . . . . . . . . . 25 94 5.2.4. Implications for ciphersuite choices . . . . . . . . 26 95 5.3. Hashing to curve . . . . . . . . . . . . . . . . . . . . 26 96 5.4. Timing Leaks . . . . . . . . . . . . . . . . . . . . . . 27 97 5.5. Key rotation . . . . . . . . . . . . . . . . . . . . . . 27 99 6. Additive blinding . . . . . . . . . . . . . . . . . . . . . . 27 100 6.1. Preprocess . . . . . . . . . . . . . . . . . . . . . . . 28 101 6.2. Blind . . . . . . . . . . . . . . . . . . . . . . . . . . 28 102 6.3. Unblind . . . . . . . . . . . . . . . . . . . . . . . . . 29 103 6.3.1. Parameter Commitments . . . . . . . . . . . . . . . . 30 104 7. Contributors . . . . . . . . . . . . . . . . . . . . . . . . 30 105 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 30 106 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 30 107 9.1. Normative References . . . . . . . . . . . . . . . . . . 30 108 9.2. Informative References . . . . . . . . . . . . . . . . . 32 109 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 32 111 1. Introduction 113 A pseudorandom function (PRF) F(k, x) is an efficiently computable 114 function taking a private key k and a value x as input. This 115 function is pseudorandom if the keyed function K(_) = F(K, _) is 116 indistinguishable from a randomly sampled function acting on the same 117 domain and range as K(). An oblivious PRF (OPRF) is a two-party 118 protocol between a server and a client, where the server holds a PRF 119 key k and the client holds some input x. The protocol allows both 120 parties to cooperate in computing F(k, x) such that: the client 121 learns F(k, x) without learning anything about k; and the server does 122 not learn anything about x or F(k, x). A Verifiable OPRF (VOPRF) is 123 an OPRF wherein the server can prove to the client that F(k, x) was 124 computed using the key k. 126 The usage of OPRFs has been demonstrated in constructing a number of 127 applications: password-protected secret sharing schemes [JKKX16]; 128 privacy-preserving password stores [SJKS17]; and password- 129 authenticated key exchange or PAKE [I-D.irtf-cfrg-opaque]. A VOPRF 130 is necessary in some applications, e.g., the Privacy Pass protocol 131 [I-D.davidson-pp-protocol], wherein this VOPRF is used to generate 132 one-time authentication tokens to bypass CAPTCHA challenges. VOPRFs 133 have also been used for password-protected secret sharing schemes 134 e.g. [JKK14]. 136 This document introduces an OPRF protocol built in prime-order 137 groups, applying to finite fields of prime-order and also elliptic 138 curve (EC) groups. The protocol has the option of being extended to 139 a VOPRF with the addition of a NIZK proof for proving discrete log 140 equality relations. This proof demonstrates correctness of the 141 computation, using a known public key that serves as a commitment to 142 the server's secret key. The document describes the protocol, the 143 public-facing API, and its security properties. 145 1.1. Change log 147 draft-05 (https://tools.ietf.org/html/draft-irtf-cfrg-voprf-05): 149 * Move to ristretto255 and decaf448 ciphersuites. 151 * Clean up ciphersuite definitions. 153 * Pin domain separation tag construction to draft version. 155 * Move key generation outside of context construction functions. 157 * Editorial changes. 159 draft-04 (https://tools.ietf.org/html/draft-irtf-cfrg-voprf-04): 161 * Introduce Client and Server contexts for controlling verifiability 162 and required functionality. 164 * Condense API. 166 * Remove batching from standard functionality (included as an 167 extension) 169 * Add Curve25519 and P-256 ciphersuites for applications that 170 prevent strong-DH oracle attacks. 172 * Provide explicit prime-order group API and instantiation advice 173 for each ciphersuite. 175 * Proof-of-concept implementation in sage. 177 * Remove privacy considerations advice as this depends on 178 applications. 180 draft-03 (https://tools.ietf.org/html/draft-irtf-cfrg-voprf-03): 182 * Certify public key during VerifiableFinalize 184 * Remove protocol integration advice 186 * Add text discussing how to perform domain separation 188 * Drop OPRF_/VOPRF_ prefix from algorithm names 190 * Make prime-order group assumption explicit 192 * Changes to algorithms accepting batched inputs 193 * Changes to construction of batched DLEQ proofs 195 * Updated ciphersuites to be consistent with hash-to-curve and added 196 OPRF specific ciphersuites 198 draft-02 (https://tools.ietf.org/html/draft-irtf-cfrg-voprf-02): 200 * Added section discussing cryptographic security and static DH 201 oracles 203 * Updated batched proof algorithms 205 draft-01 (https://tools.ietf.org/html/draft-irtf-cfrg-voprf-01): 207 * Updated ciphersuites to be in line with 208 https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-04 210 * Made some necessary modular reductions more explicit 212 1.2. Terminology 214 The following terms are used throughout this document. 216 * PRF: Pseudorandom Function. 218 * OPRF: Oblivious Pseudorandom Function. 220 * VOPRF: Verifiable Oblivious Pseudorandom Function. 222 * Client: Protocol initiator. Learns pseudorandom function 223 evaluation as the output of the protocol. 225 * Server: Computes the pseudorandom function over a secret key. 226 Learns nothing about the client's input. 228 * NIZK: Non-interactive zero knowledge. 230 * DLEQ: Discrete Logarithm Equality. 232 1.3. Requirements 234 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 235 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 236 "OPTIONAL" in this document are to be interpreted as described in 237 BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all 238 capitals, as shown here. 240 2. Preliminaries 242 2.1. Prime-order group API 244 In this document, we assume the construction of an additive, prime- 245 order group "GG" for performing all mathematical operations. Such 246 groups are uniquely determined by the choice of the prime "p" that 247 defines the order of the group. We use "GF(p)" to represent the 248 finite field of order "p". For the purpose of understanding and 249 implementing this document, we take "GF(p)" to be equal to the set of 250 integers defined by "{0, 1, ..., p-1}". 252 The fundamental group operation is addition "+" with identity element 253 "I". For any elements "A" and "B" of the group "GG", "A + B = B + A" 254 is also a member of "GG". Also, for any "A" in "GG", there exists an 255 element "-A" such that "A + (-A) = (-A) + A = I". Scalar 256 multiplication is equivalent to the repeated application of the group 257 operation on an element A with itself "r-1" times, this is denoted as 258 "r*A = A + ... + A". For any element "A", the equality "p*A=I" 259 holds. Scalar base multiplication is equivalent to the repeated 260 application of the group operation on the base point with itself 261 "r-1" times, this is denoted as "ScalarBaseMult(r)". The set of 262 scalars corresponds to "GF(p)". 264 We now detail a number of member functions that can be invoked on a 265 prime-order group. 267 * Order(): Outputs the order of GG (i.e. "p"). 269 * Identity(): Outputs the identity element of the group (i.e. "I"). 271 * Serialize(A): A member function of "GG" that maps a group element 272 "A" to a unique byte array "buf". 274 * Deserialize(buf): A member function of "GG" that maps a byte array 275 "buf" to a group element "A", or fails if the input is not a valid 276 byte representation of an element. 278 * HashToGroup(x): A member function of "GG" that deterministically 279 maps an array of bytes "x" to an element of "GG". The map must 280 ensure that, for any adversary receiving "R = HashToGroup(x)", it 281 is computationally difficult to reverse the mapping. Examples of 282 hash to group functions satisfying this property are described for 283 prime-order (sub)groups of elliptic curves, see 284 [I-D.irtf-cfrg-hash-to-curve]. 286 * HashToScalar(x): A member function of "GG" that deterministically 287 maps an array of bytes "x" to an element in GF(p). A recommended 288 method for its implementation is instantiating the hash to field 289 function, defined in [I-D.irtf-cfrg-hash-to-curve] setting the 290 target field to GF(p). 292 * RandomScalar(): A member function of "GG" that chooses at random a 293 non-zero element in GF(p). 295 It is convenient in cryptographic applications to instantiate such 296 prime-order groups using elliptic curves, such as those detailed in 297 [SEC2]. For some choices of elliptic curves (e.g. those detailed in 298 [RFC7748], which require accounting for cofactors) there are some 299 implementation issues that introduce inherent discrepancies between 300 standard prime-order groups and the elliptic curve instantiation. In 301 this document, all algorithms that we detail assume that the group is 302 a prime-order group, and this MUST be upheld by any implementer. 303 That is, any curve instantiation should be written such that any 304 discrepancies with a prime-order group instantiation are removed. 305 See Section 4 for advice corresponding to implementation of this 306 interface for specific definitions of elliptic curves. 308 2.2. Other conventions 310 * We use the notation "x <-$ Q" to denote sampling "x" from the 311 uniform distribution over the set "Q". 313 * For any object "x", we write "len(x)" to denote its length in 314 bytes. 316 * For two byte arrays "x" and "y", write "x || y" to denote their 317 concatenation. 319 * I2OSP and OS2IP: Convert a byte array to and from a non-negative 320 integer as described in [RFC8017]. Note that these functions 321 operate on byte arrays in big-endian byte order. 323 All algorithm descriptions are written in a Python-like pseudocode. 324 We use the "ABORT()" function for presentational clarity to denote 325 the process of terminating the algorithm or returning an error 326 accordingly. We also use the "CT_EQUAL(a, b)" function to represent 327 constant-time byte-wise equality between byte arrays "a" and "b". 328 This function returns "true" if "a" and "b" are equal, and "false" 329 otherwise. 331 3. OPRF Protocol 333 In this section, we define two OPRF variants: a base mode and 334 verifiable mode. In the base mode, a client and server interact to 335 compute y = F(skS, x), where x is the client's input, skS is the 336 server's private key, and y is the OPRF output. The client learns y 337 and the server learns nothing. In the verifiable mode, the client 338 also gets proof that the server used skS in computing the function. 340 To achieve verifiability, as in the original work of [JKK14], we 341 provide a zero-knowledge proof that the key provided as input by the 342 server in the "Evaluate" function is the same key as it used to 343 produce their public key. As an example of the nature of attacks 344 that this prevents, this ensures that the server uses the same 345 private key for computing the VOPRF output and does not attempt to 346 "tag" individual servers with select keys. This proof must not 347 reveal the server's long-term private key to the client. 349 The following one-byte values distinguish between these two modes: 351 +================+=======+ 352 | Mode | Value | 353 +================+=======+ 354 | modeBase | 0x00 | 355 +----------------+-------+ 356 | modeVerifiable | 0x01 | 357 +----------------+-------+ 359 Table 1 361 3.1. Overview 363 Both participants agree on the mode and a choice of ciphersuite that 364 is used before the protocol exchange. Once established, the core 365 protocol runs to compute "output = F(skS, input)" as follows: 367 Client(pkS, input, info) Server(skS, pkS) 368 ---------------------------------------------------------- 369 token, blindToken = Blind(input) 371 blindToken 372 ----------> 374 evaluation = Evaluate(skS, pkS, blindToken) 376 evaluation 377 <---------- 379 issuedToken = Unblind(pkS, token, blindToken, evaluation) 380 output = Finalize(input, issuedToken, info) 382 In "Blind" the client generates a token and blinding data. The 383 server computes the (V)OPRF evaluation in "Evaluation" over the 384 client's blinded token. In "Unblind" the client unblinds the server 385 response (and verifies the server's proof if verifiability is 386 required). In "Finalize", the client produces a byte array 387 corresponding to the output of the OPRF protocol. 389 Note that in the final output, the client computes Finalize over some 390 auxiliary input data "info". This parameter SHOULD be used for 391 domain separation in the (V)OPRF protocol. Specifically, any system 392 which has multiple (V)OPRF applications should use separate auxiliary 393 values to ensure finalized outputs are separate. Guidance for 394 constructing info can be found in [I-D.irtf-cfrg-hash-to-curve]; 395 Section 3.1. 397 3.2. Context Setup 399 Both modes of the OPRF involve an offline setup phase. In this 400 phase, both the client and server create a context used for executing 401 the online phase of the protocol. Prior to this phase, keys ("skS", 402 "pkS") should be generated by calling a "KeyGen" function. "KeyGen" 403 generates a private and public key pair ("skS", "pkS"), where "skS" 404 is a non-zero element chosen at random from the scalar field of the 405 corresponding group and "pkS = ScalarBaseMult(skS)". 407 The base mode setup functions for creating client and server contexts 408 are below: 410 def SetupBaseServer(suite, skS): 411 contextString = I2OSP(modeBase, 1) || I2OSP(suite.ID, 2) 412 return ServerContext(contextString, skS) 414 def SetupBaseClient(suite): 415 contextString = I2OSP(modeBase, 1) || I2OSP(suite.ID, 2) 416 return ClientContext(contextString) 418 The verifiable mode setup functions for creating client and server 419 contexts are below: 421 def SetupVerifiableServer(suite, skS, pkS): 422 contextString = I2OSP(modeVerifiable, 1) || I2OSP(suite.ID, 2) 423 return VerifiableServerContext(contextString, skS), pkS 425 def SetupVerifiableClient(suite, pkS): 426 contextString = I2OSP(modeVerifiable, 1) || I2OSP(suite.ID, 2) 427 return VerifiableClientContext(contextString, pkS) 429 Each setup function takes a ciphersuite from the list defined in 430 Section 4. Each ciphersuite has a two-byte field ID used to identify 431 the suite. 433 3.3. Data Structures 435 The following is a list of data structures that are defined for 436 providing inputs and outputs for each of the context interfaces 437 defined in Section 3.4. Each data structure description uses TLS 438 notation (see [RFC8446], Section 3). 440 The following types are a list of aliases that are used throughout 441 the protocol. 443 A "ClientInput" is a byte array. 445 opaque ClientInput<1..2^16-1>; 447 A "SerializedElement" is also a byte array, representing the unique 448 serialization of an "Element". 450 opaque SerializedElement<1..2^16-1>; 452 A "Token" is an object created by a client when constructing a 453 (V)OPRF protocol input. It is stored so that it can be used after 454 receiving the server response. 456 struct { 457 opaque data<1..2^16-1>; 458 Scalar blind<1..2^16-1>; 459 } Token; 461 An "Evaluation" is the type output by the "Evaluate" algorithm. The 462 member "proof" is added only in verifiable contexts. 464 struct { 465 SerializedElement element; 466 Scalar proof<0...2^16-1>; /* only for modeVerifiable */ 467 } Evaluation; 469 Evaluations may also be combined in batches with a constant-size 470 proof, producing a "BatchedEvaluation". These carry a list of 471 "SerializedElement" values and proof. These evaluation types are 472 only useful in verifiable contexts which carry proofs. 474 struct { 475 SerializedElement elements<1..2^16-1>; 476 Scalar proof<0...2^16-1>; /* only for modeVerifiable */ 477 } BatchedEvaluation; 479 3.4. Context APIs 481 In this section, we detail the APIs available on the client and 482 server (V)OPRF contexts. This document uses the types "Element" and 483 "Scalar" to denote elements of the group "GG" and its underlying 484 scalar field "GF(p)", respectively. For notational clarity, 485 "PublicKey" is an item of type "Element" and "PrivateKey" is an item 486 of type "Scalar". 488 3.4.1. Server Context 490 The ServerContext encapsulates the context string constructed during 491 setup and the (V)OPRF key pair. It has three functions, "Evaluate", 492 "FullEvaluate" and "VerifyFinalize" described below. "Evaluate" 493 takes serialized representations of blinded group elements from the 494 client as inputs. 496 "FullEvaluate" takes ClientInput values, and it is useful for 497 applications that need to compute the whole OPRF protocol on the 498 server side only. 500 "VerifyFinalize" takes ClientInput values and their corresponding 501 output digests from "Finalize" as input, and returns true if the 502 inputs match the outputs. 504 Note that "VerifyFinalize" and "FullEvaluate" are not used in the 505 main OPRF protocol. They are exposed as an API for building higher- 506 level protocols. 508 3.4.1.1. Evaluate 510 Input: 512 PrivateKey skS 513 SerializedElement blindToken 515 Output: 517 Evaluation Ev 519 def Evaluate(skS, blindToken): 520 BT = GG.Deserialize(blindToken) 521 Z = skS * BT 522 serializedElement = GG.Serialize(Z) 524 Ev = Evaluation{ element: serializedElement } 526 return Ev 528 3.4.1.2. FullEvaluate 530 Input: 532 PrivateKey skS 533 ClientInput input 534 opaque info<1..2^16-1> 536 Output: 538 opaque output<1..2^16-1> 540 def FullEvaluate(skS, input, info): 541 P = GG.HashToGroup(input) 542 T = skS * P 543 issuedToken = GG.serialize(T) 545 finalizeDST = "VOPRF05-Finalize-" || self.contextString 546 hashInput = I2OSP(len(input), 2) || input || 547 I2OSP(len(issuedToken), 2) || issuedToken || 548 I2OSP(len(info), 2) || info || 549 I2OSP(len(finalizeDST), 2) || finalizeDST 551 return Hash(hashInput) 553 3.4.1.3. VerifyFinalize 555 Input: 557 PrivateKey skS 558 ClientInput input 559 opaque info<1..2^16-1> 560 opaque output<1..2^16-1> 562 Output: 564 boolean valid 566 def VerifyFinalize(skS, input, info, output): 567 T = GG.HashToGroup(input) 568 element = GG.Serialize(T) 569 issuedElement = Evaluate(skS, [element]) 570 E = GG.Serialize(issuedElement) 572 finalizeDST = "VOPRF05-Finalize-" || self.contextString 573 hashInput = I2OSP(len(input), 2) || input || 574 I2OSP(len(E), 2) || E || 575 I2OSP(len(info), 2) || info || 576 I2OSP(len(finalizeDST), 2) || finalizeDST 578 digest = Hash(hashInput) 580 return CT_EQUAL(digest, output) 582 [[RFC editor: please change "VOPRF05" to "RFCXXXX", where XXXX is the 583 final number, here and elsewhere before publication.]] 585 3.4.2. VerifiableServerContext 587 The VerifiableServerContext extends the base ServerContext with an 588 augmented "Evaluate()" function. This function produces a proof that 589 "skS" was used in computing the result. It makes use of the helper 590 functions "GenerateProof" and "ComputeComposites", described below. 592 3.4.2.1. Evaluate 593 Input: 595 PrivateKey skS 596 PublicKey pkS 597 SerializedElement blindToken 599 Output: 601 Evaluation Ev 603 def Evaluate(skS, pkS, blindToken): 604 BT = GG.Deserialize(blindToken) 605 Z = skS * BT 606 serializedElement = GG.Serialize(Z) 608 proof = GenerateProof(skS, pkS, blindToken, serializedElement) 609 Ev = Evaluation{ element: serializedElement, proof: proof } 611 return Ev 613 The helper functions "GenerateProof" and "ComputeComposites" are 614 defined below. 616 3.4.2.2. GenerateProof 617 Input: 619 PrivateKey skS 620 PublicKey pkS 621 SerializedElement blindToken 622 SerializedElement element 624 Output: 626 Scalar proof[2] 628 def GenerateProof(skS, pkS, blindToken, element) 629 blindTokenList = [blindToken] 630 elementList = [element] 632 a = ComputeComposites(pkS, blindTokenList, elementList) 634 M = GG.Deserialize(a[0]) 635 r = GG.RandomScalar() 636 a2 = GG.Serialize(ScalarBaseMult(r)) 637 a3 = GG.Serialize(r * M) 639 challengeDST = "VOPRF05-challenge-" || self.contextString 640 h2Input = I2OSP(len(pkS), 2) || pkS || 641 I2OSP(len(a[0]), 2) || a[0] || 642 I2OSP(len(a[1]), 2) || a[1] || 643 I2OSP(len(a2), 2) || a2 || 644 I2OSP(len(a3), 2) || a3 || 645 I2OSP(len(challengeDST), 2) || challengeDST 647 c = GG.HashToScalar(h2Input) 648 s = (r - c * skS) mod p 650 return [c, s] 652 3.4.2.2.1. Batching inputs 654 Unlike other functions, "ComputeComposites" takes lists of inputs, 655 rather than a single input. It is optimized to produce a constant- 656 size output. This functionality lets applications batch inputs 657 together to produce a constant-size proofs from "GenerateProof". 658 Applications can take advantage of this functionality by invoking 659 "GenerateProof" on batches of inputs. (Notice that in the pseudocode 660 above, the single inputs "blindToken" and "element" are translated 661 into lists before invoking "ComputeComposites". A batched 662 "GenerateProof" variant would permit lists of inputs, and no list 663 translation would be needed.) 664 Note that using batched inputs creates a "BatchedEvaluation" object 665 as the output of "Evaluate". 667 3.4.2.2.2. Fresh randomness 669 We note here that it is essential that a different "r" value is used 670 for every invocation. If this is not done, then this may leak "skS" 671 as is possible in Schnorr or (EC)DSA scenarios where fresh randomness 672 is not used. 674 3.4.2.3. ComputeComposites 676 Input: 678 PublicKey pkS 679 SerializedElement blindTokens[m] 680 SerializedElement elements[m] 682 Output: 684 SerializedElement composites[2] 686 def ComputeComposites(pkS, blindTokens, elements): 687 seedDST = "VOPRF05-seed-" || self.contextString 688 compositeDST = "VOPRF05-composite-" || self.contextString 689 h1Input = I2OSP(len(pkS), 2) || pkS || 690 I2OSP(len(blindTokens), 2) || blindTokens || 691 I2OSP(len(elements), 2) || elements || 692 I2OSP(len(seedDST), 2) || seedDST 694 seed = Hash(h1Input) 695 M = GG.Identity() 696 Z = GG.Identity() 697 for i = 0 to m-1: 698 h2Input = I2OSP(len(seed), 2) || seed || I2OSP(i, 2) || 699 I2OSP(len(compositeDST), 2) || compositeDST 700 di = GG.HashToScalar(h2Input) 701 Mi = GG.Deserialize(blindTokens[i]) 702 Zi = GG.Deserialize(elements[i]) 703 M = di * Mi + M 704 Z = di * Zi + Z 705 return [GG.Serialize(M), GG.Serialize(Z)] 707 3.4.3. Client Context 709 The ClientContext encapsulates the context string constructed during 710 setup. It has three functions, "Blind()", "Unblind()", and 711 "Finalize()", as described below. 713 3.4.3.1. Blind 715 We note here that the blinding mechanism that we use can be modified 716 slightly with the opportunity for making performance gains in some 717 scenarios. We detail these modifications in Section 6. 719 Input: 721 ClientInput input 723 Output: 725 Token token 726 SerializedElement blindToken 728 def Blind(input): 729 r = GG.RandomScalar() 730 P = GG.HashToGroup(input) 731 blindToken = GG.Serialize(r * P) 733 token = Token{ data: input, blind: r } 735 return (token, blindToken) 737 3.4.3.2. Unblind 739 Input: 741 Token token 742 Evaluation Ev 744 Output: 746 SerializedElement issuedToken 748 def Unblind(token, Ev): 749 r = token.blind 750 Z = GG.Deserialize(Ev.element) 751 N = (r^(-1)) * Z 753 issuedToken = GG.Serialize(N) 755 return issuedToken 757 3.4.3.3. Finalize 758 Input: 760 Token token 761 SerializedElement issuedToken 762 opaque info<1..2^16-1> 764 Output: 766 opaque output<1..2^16-1> 768 def Finalize(token, issuedToken, info): 769 finalizeDST = "VOPRF05-Finalize-" || self.contextString 770 hashInput = I2OSP(len(token.data), 2) || token.data || 771 I2OSP(len(issuedToken), 2) || issuedToken || 772 I2OSP(len(info), 2) || info || 773 I2OSP(len(finalizeDST), 2) || finalizeDST 774 return Hash(hashInput) 776 3.4.4. VerifiableClientContext 778 The VerifiableClientContext extends the base ClientContext with the 779 desired server public key "pkS" with an augmented "Unblind()" 780 function. This function verifies an evaluation proof using "pkS". 781 It makes use of the helper function "ComputeComposites" described 782 above. It has one helper function, "VerifyProof()", defined below. 784 3.4.4.1. VerifyProof 786 This algorithm outputs a boolean "verified" which indicates whether 787 the proof inside of the evaluation verifies correctly, or not. 789 Input: 791 PublicKey pkS 792 SerializedElement blindToken 793 Evaluation Ev 795 Output: 797 boolean verified 799 def VerifyProof(pkS, blindToken, Ev): 800 blindTokenList = [blindToken] 801 elementList = [Ev.element] 803 a = ComputeComposites(pkS, blindTokenList, elementList) 805 A' = (ScalarBaseMult(Ev.proof[1]) + Ev.proof[0] * pkS) 806 B' = (Ev.proof[1] * M + Ev.proof[0] * Z) 807 a2 = GG.Serialize(A') 808 a3 = GG.Serialize(B') 810 challengeDST = "VOPRF05-challenge-" || self.contextString 811 h2Input = I2OSP(len(pkS), 2) || pkS || 812 I2OSP(len(a[0]), 2) || a[0] || 813 I2OSP(len(a[1]), 2) || a[1] || 814 I2OSP(len(a2), 2) || a2 || 815 I2OSP(len(a3), 2) || a3 || 816 I2OSP(len(challengeDST), 2) || challengeDST 818 c = GG.HashToScalar(h2Input) 820 return CT_EQUAL(c, Ev.proof[0]) 822 3.4.4.2. Unblind 823 Input: 825 PublicKey pkS 826 Token token 827 SerializedElement blindToken 828 Evaluation Ev 830 Output: 832 SerializedElement issuedToken 834 def Unblind(pkS, token, blindToken, Ev): 835 if VerifyProof(pkS, blindToken, Ev) == false: 836 ABORT() 838 r = token.blind 839 Z = GG.Deserialize(Ev.element) 840 N = (r^(-1)) * Z 842 issuedToken = GG.Serialize(N) 844 return issuedToken 846 4. Ciphersuites 848 A ciphersuite (also referred to as 'suite' in this document) for the 849 protocol wraps the functionality required for the protocol to take 850 place. This ciphersuite should be available to both the client and 851 server, and agreement on the specific instantiation is assumed 852 throughout. A ciphersuite contains instantiations of the following 853 functionalities: 855 * "GG": A prime-order group exposing the API detailed in 856 Section 2.1, with base point defined in the corresponding 857 reference for each group. 859 * "Hash": A cryptographic hash function that is indifferentiable 860 from a Random Oracle. 862 This section specifies supported VOPRF group and hash function 863 instantiations. For each group, we specify the HashToGroup, 864 HashToScalar, and serialization functionalities. 866 Applications should take caution in using ciphersuites targeting 867 P-256 and ristretto255. See Section 5.2 for related discussion. 869 4.1. OPRF(ristretto255, SHA-256) 871 * Group: ristretto255 [RISTRETTO] 873 - HashToGroup(): hash_to_ristretto255 874 [I-D.irtf-cfrg-hash-to-curve] with DST = "VOPRF05-" || 875 contextString, where contextString is that which is computed in 876 the Setup functions, and "expand_message" = 877 "expand_message_xmd" using SHA-256. 879 - HashToScalar(): Use hash_to_field from 880 [I-D.irtf-cfrg-hash-to-curve] using Order() as the prime 881 modulus, with L=48, and expand_message_xmd with SHA-256. 883 - Serialization: Serialization converts group elements to 32-byte 884 strings using the 'Encode' function from [RISTRETTO]. 885 Deserialization converts 32-byte strings to group elements 886 using the 'Decode' function from [RISTRETTO]. 888 * Hash: SHA-256 890 * ID: 0x0001 892 4.2. OPRF(decaf448, SHA-512) 894 * Group: decaf448 [RISTRETTO] 896 - HashToGroup(): hash_to_decaf448 [I-D.irtf-cfrg-hash-to-curve] 897 with DST = "VOPRF05-" || contextString, where contextString is 898 that which is computed in the Setup functions, and 899 "expand_message" = "expand_message_xmd" using SHA-512. 901 - HashToScalar(): Use hash_to_field from 902 [I-D.irtf-cfrg-hash-to-curve] using Order() as the prime 903 modulus, with L=84, and "expand_message_xmd" with SHA-512. 905 - Serialization: Serialization converts group elements to 56-byte 906 strings using the 'Encode' function from [RISTRETTO]. 907 Deserialization converts 56-byte strings to group elements 908 using the 'Decode' function from [RISTRETTO]. 910 * Hash: SHA-512 912 * ID: 0x0002 914 4.3. OPRF(P-256, SHA-256) 916 * Group: P-256 (secp256r1) [x9.62] 918 - HashToGroup(): P256_XMD:SHA-256_SSWU_RO_ 919 [I-D.irtf-cfrg-hash-to-curve] with DST = "VOPRF05-" || 920 contextString, where contextString is that which is computed in 921 the Setup functions. 923 - HashToScalar(): Use hash_to_field from 924 [I-D.irtf-cfrg-hash-to-curve] using Order() as the prime 925 modulus, with L=48, and "expand_message_xmd" with SHA-256. 927 - Serialization: The compressed point encoding for the curve 928 [SEC1] consisting of 33 bytes. 930 * Hash: SHA-256 932 * ID: 0x0003 934 4.4. OPRF(P-384, SHA-512) 936 * Group: P-384 (secp384r1) [x9.62] 938 - HashToGroup(): P384_XMD:SHA-512_SSWU_RO_ 939 [I-D.irtf-cfrg-hash-to-curve] with DST = "VOPRF05-" || 940 contextString, where contextString is that which is computed in 941 the Setup functions. 943 - HashToScalar(): Use hash_to_field from 944 [I-D.irtf-cfrg-hash-to-curve] using Order() as the prime 945 modulus, with L=72, and "expand_message_xmd" with SHA-512. 947 - Serialization: The compressed point encoding for the curve 948 [SEC1] consisting of 49 bytes. 950 * Hash: SHA-512 952 * ID: 0x0004 954 4.5. OPRF(P-521, SHA-512) 956 * Group: P-521 (secp521r1) [x9.62] 958 - HashToGroup(): P521_XMD:SHA-512_SSWU_RO_ 959 [I-D.irtf-cfrg-hash-to-curve] with DST = "VOPRF05-" || 960 contextString, where contextString is that which is computed in 961 the Setup functions. 963 - HashToScalar(): Use hash_to_field from 964 [I-D.irtf-cfrg-hash-to-curve] using Order() as the prime 965 modulus, with L=98, and "expand_message_xmd" with SHA-512. 967 - Serialization: The compressed point encoding for the curve 968 [SEC1] consisting of 67 bytes. 970 * Hash: SHA-512 972 * ID: 0x0005 974 5. Security Considerations 976 This section discusses the cryptographic security of our protocol, 977 along with some suggestions and trade-offs that arise from the 978 implementation of an OPRF. 980 5.1. Security properties 982 The security properties of an OPRF protocol with functionality y = 983 F(k, x) include those of a standard PRF. Specifically: 985 * Pseudorandomness: F is pseudorandom if the output y = F(k,x) on 986 any input x is indistinguishable from uniformly sampling any 987 element in F's range, for a random sampling of k. 989 In other words, consider an adversary that picks inputs x from the 990 domain of F and evaluates F on (k,x) (without knowledge of randomly 991 sampled k). Then the output distribution F(k,x) is indistinguishable 992 from the output distribution of a randomly chosen function with the 993 same domain and range. 995 A consequence of showing that a function is pseudorandom, is that it 996 is necessarily non-malleable (i.e. we cannot compute a new evaluation 997 of F from an existing evaluation). A genuinely random function will 998 be non-malleable with high probability, and so a pseudorandom 999 function must be non-malleable to maintain indistinguishability. 1001 An OPRF protocol must also satisfy the following property: 1003 * Oblivious: The server must learn nothing about the client's input 1004 or the output of the function. In addition, the client must learn 1005 nothing about the server's private key. 1007 Essentially, obliviousness tells us that, even if the server learns 1008 the client's input x at some point in the future, then the server 1009 will not be able to link any particular OPRF evaluation to x. This 1010 property is also known as unlinkability [DGSTV18]. 1012 Optionally, for any protocol that satisfies the above properties, 1013 there is an additional security property: 1015 * Verifiable: The client must only complete execution of the 1016 protocol if it can successfully assert that the OPRF output it 1017 computes is correct. This is taken with respect to the OPRF key 1018 held by the server. 1020 Any OPRF that satisfies the 'verifiable' security property is known 1021 as a verifiable OPRF, or VOPRF for short. In practice, the notion of 1022 verifiability requires that the server commits to the key before the 1023 actual protocol execution takes place. Then the client verifies that 1024 the server has used the key in the protocol using this commitment. 1025 In the following, we may also refer to this commitment as a public 1026 key. 1028 5.2. Cryptographic security 1030 Below, we discuss the cryptographic security of the (V)OPRF protocol 1031 from Section 3, relative to the necessary cryptographic assumptions 1032 that need to be made. 1034 5.2.1. Computational hardness assumptions 1036 Each assumption states that the problems specified below are 1037 computationally difficult to solve in relation to a particular choice 1038 of security parameter "sp". 1040 Let GG = GG(sp) be a group with prime-order p, and let FFp be the 1041 finite field of order p. 1043 5.2.1.1. Discrete-log (DL) problem 1045 Given G, a generator of GG, and H = hG for some h in FFp; output h. 1047 5.2.1.2. Decisional Diffie-Hellman (DDH) problem 1049 Sample a uniformly random bit d in {0,1}. Given (G, aG, bG, C), 1050 where: 1052 * G is a generator of GG; 1054 * a,b are elements of FFp; 1056 * if d == 0: C = abG; else: C is sampled uniformly GG(sp). 1058 Output d' == d. 1060 5.2.2. Protocol security 1062 Our OPRF construction is based on the VOPRF construction known as 1063 2HashDH-NIZK given by [JKK14]; essentially without providing zero- 1064 knowledge proofs that verify that the output is correct. Our VOPRF 1065 construction is identical to the [JKK14] construction, except that we 1066 can optionally perform multiple VOPRF evaluations in one go, whilst 1067 only constructing one NIZK proof object. This is enabled using an 1068 established batching technique. 1070 Consequently the cryptographic security of our construction is based 1071 on the assumption that the One-More Gap DH is computationally 1072 difficult to solve. 1074 The (N,Q)-One-More Gap DH (OMDH) problem asks the following. 1076 Given: 1077 - G, k * G, G_1, ... , G_N where G, G_1, ... G_N are elements of GG; 1078 - oracle access to an OPRF functionality using the key k; 1079 - oracle access to DDH solvers. 1081 Find Q+1 pairs of the form below: 1083 (G_{j_s}, k * G_{j_s}) 1085 where the following conditions hold: 1086 - s is a number between 1 and Q+1; 1087 - j_s is a number between 1 and N for each s; 1088 - Q is the number of allowed queries. 1090 The original paper [JKK14] gives a security proof that the 2HashDH- 1091 NIZK construction satisfies the security guarantees of a VOPRF 1092 protocol Section 5.1 under the OMDH assumption in the universal 1093 composability (UC) security model. 1095 5.2.3. Q-strong-DH oracle 1097 A side-effect of our OPRF design is that it allows instantiation of a 1098 oracle for constructing Q-strong-DH (Q-sDH) samples. The Q-Strong-DH 1099 problem asks the following. 1101 Given G1, G2, h*G2, (h^2)*G2, ..., (h^Q)*G2; for G1 and G2 1102 generators of GG. 1104 Output ( (1/(k+c))*G1, c ) where c is an element of FFp 1106 The assumption that this problem is hard was first introduced in 1107 [BB04]. Since then, there have been a number of cryptanalytic 1108 studies that have reduced the security of the assumption below that 1109 implied by the group instantiation (for example, [BG04] and 1110 [Cheon06]). In summary, the attacks reduce the security of the group 1111 instantiation by log_2(Q) bits. 1113 As an example, suppose that a group instantiation is used that 1114 provides 128 bits of security against discrete log cryptanalysis. 1115 Then an adversary with access to a Q-sDH oracle and makes Q=2^20 1116 queries can reduce the security of the instantiation by log_2(2^20) = 1117 20 bits. 1119 Notice that it is easy to instantiate a Q-sDH oracle using the OPRF 1120 functionality that we provide. A client can just submit sequential 1121 queries of the form (G, k * G, (k^2)G, ..., (k^(Q-1))G), where each 1122 query is the output of the previous interaction. This means that any 1123 client that submit Q queries to the OPRF can use the aforementioned 1124 attacks to reduce security of the group instantiation by log_2(Q) 1125 bits. 1127 Recall that from a malicious client's perspective, the adversary wins 1128 if they can distinguish the OPRF interaction from a protocol that 1129 computes the ideal functionality provided by the PRF. 1131 5.2.4. Implications for ciphersuite choices 1133 The OPRF instantiations that we recommend in this document are 1134 informed by the cryptanalytic discussion above. In particular, 1135 choosing elliptic curves configurations that describe 128-bit group 1136 instantiations would appear to in fact instantiate an OPRF with 1137 128-log_2(Q) bits of security. 1139 In most cases, it would require an informed and persistent attacker 1140 to launch a highly expensive attack to reduce security to anything 1141 much below 100 bits of security. We see this possibility as 1142 something that may result in problems in the future. For 1143 applications that cannot tolerate discrete logarithm security of 1144 lower than 128 bits, we recommend only implementing ciphersuites with 1145 IDs: 0x0002, 0x0004, and 0x0005. 1147 5.3. Hashing to curve 1149 A critical requirement of implementing the prime-order group using 1150 elliptic curves is a method to instantiate the function 1151 "GG.HashToGroup", that maps inputs to group elements. In the 1152 elliptic curve setting, this deterministically maps inputs x (as byte 1153 arrays) to uniformly chosen points on the curve. 1155 In the security proof of the construction Hash is modeled as a random 1156 oracle. This implies that any instantiation of "GG.HashToGroup" must 1157 be pre-image and collision resistant. In Section 4 we give 1158 instantiations of this functionality based on the functions described 1159 in [I-D.irtf-cfrg-hash-to-curve]. Consequently, any OPRF 1160 implementation must adhere to the implementation and security 1161 considerations discussed in [I-D.irtf-cfrg-hash-to-curve] when 1162 instantiating the function. 1164 5.4. Timing Leaks 1166 To ensure no information is leaked during protocol execution, all 1167 operations that use secret data MUST run in constant time. 1168 Operations that SHOULD run in constant time include all prime-order 1169 group operations and proof-specific operations ("GenerateProof()" and 1170 "VerifyProof()"). 1172 5.5. Key rotation 1174 Since the server's key is critical to security, the longer it is 1175 exposed by performing (V)OPRF operations on client inputs, the longer 1176 it is possible that the key can be compromised. For example,if the 1177 key is kept in circulation for a long period of time, then it also 1178 allows the clients to make enough queries to launch more powerful 1179 variants of the Q-sDH attacks from Section 5.2.3. 1181 To combat attacks of this nature, regular key rotation should be 1182 employed on the server-side. A suitable key-cycle for a key used to 1183 compute (V)OPRF evaluations would be between one week and six months. 1185 6. Additive blinding 1187 Let "H" refer to the function "GG.HashToGroup", in Section 2.1 we 1188 assume that the client-side blinding is carried out directly on the 1189 output of "H(x)", i.e. computing "r * H(x)" for some "r <-$ GF(p)". 1190 In the [I-D.irtf-cfrg-opaque] document, it is noted that it may be 1191 more efficient to use additive blinding (rather than multiplicative) 1192 if the client can preprocess some values. For example, a valid way 1193 of computing additive blinding would be to instead compute "H(x) + (r 1194 * G)", where "G" is the fixed generator for the group "GG". 1196 The advantage of additive blinding is that it allows the client to 1197 pre-process tables of blinded scalar multiplications for "G". This 1198 may give it a computational efficiency advantage (due to the fact 1199 that a fixed-base multiplication can be calculated faster than a 1200 variable-base multiplication). Pre-processing also reduces the 1201 amount of computation that needs to be done in the online exchange. 1202 Choosing one of these values "r * G" (where "r" is the scalar value 1203 that is used), then computing "H(x) + (r * G)" is more efficient than 1204 computing "r * H(x)". Therefore, it may be advantageous to define 1205 the OPRF and VOPRF protocols using additive blinding (rather than 1206 multiplicative) blinding. In fact, the only algorithms that need to 1207 change are Blind and Unblind (and similarly for the VOPRF variants). 1209 We define the variants of the algorithms in Section 3.4 for 1210 performing additive blinding below, along with a new algorithm 1211 "Preprocess". The "Preprocess" algorithm can take place offline and 1212 before the rest of the OPRF protocol. The Blind algorithm takes the 1213 preprocessed values as inputs, but the signature of Unblind remains 1214 the same. 1216 6.1. Preprocess 1218 struct { 1219 Scalar blind; 1220 SerializedElement blindedGenerator; 1221 SerializedElement blindedPublicKey; 1222 } PreprocessedBlind; 1224 Input: 1226 PublicKey pkS 1228 Output: 1230 PrepocessedBlind preproc 1232 def Preprocess(pkS): 1233 PK = GG.Deserialize(pkS) 1234 r = GG.RandomScalar() 1235 blindedGenerator = GG.Serialize(ScalarBaseMult(r)) 1236 blindedPublicKey = GG.Serialize(r * PK) 1238 preproc = PrepocessedBlind{ 1239 blind: r, 1240 blindedGenerator: blindedGenerator, 1241 blindedPublicKey: blindedPublicKey, 1242 } 1244 return preproc 1246 6.2. Blind 1247 Input: 1249 ClientInput input 1250 PreprocessedBlind preproc 1252 Output: 1254 Token token 1255 SerializedElement blindToken 1257 def Blind(input, preproc): 1258 Q = GG.Deserialize(preproc.blindedGenerator) /* Q = ScalarBaseMult(r) */ 1259 P = GG.HashToGroup(input) 1261 token = Token{ 1262 data: input, 1263 blind: preproc.blindedPublicKey 1264 } 1265 blindToken = GG.Serialize(P + Q) /* P + ScalarBaseMult(r) */ 1267 return (token, blindToken) 1269 6.3. Unblind 1271 Input: 1273 Token token 1274 Evaluation ev 1275 SerializedElement blindToken 1277 Output: 1279 SerializedElement unblinded 1281 def Unblind(token, ev, blindToken): 1282 PKR = GG.Deserialize(token.blind) 1283 Z = GG.Deserialize(ev.element) 1284 N := Z - PKR 1286 issuedToken = GG.Serialize(N) 1288 return issuedToken 1290 Let "P = GG.HashToGroup(x)". Notice that Unblind computes: 1292 Z - PKR = k * (P + r * G) - r * pkS 1293 = k * P + k * (r * G) - r * (k * G) 1294 = k * P 1296 by the commutativity of scalar multiplication in GG. This is the 1297 same output as in the "Unblind" algorithm for multiplicative 1298 blinding. 1300 Note that the verifiable variant of "Unblind" works as above but 1301 includes the step to "VerifyProof", as specified in Section 3.4.4. 1303 6.3.1. Parameter Commitments 1305 For some applications, it may be desirable for server to bind tokens 1306 to certain parameters, e.g., protocol versions, ciphersuites, etc. 1307 To accomplish this, server should use a distinct scalar for each 1308 parameter combination. Upon redemption of a token T from the client, 1309 server can later verify that T was generated using the scalar 1310 associated with the corresponding parameters. 1312 7. Contributors 1314 * Sofia Celi (cherenkov@riseup.net) 1316 * Alex Davidson (alex.davidson92@gmail.com) 1318 * Armando Faz Hernandez (armfazh@cloudflare.com) 1320 * Eli-Shaoul Khedouri (eli@intuitionmachines.com) 1322 * Nick Sullivan (nick@cloudflare.com) 1324 * Christopher A. Wood (caw@heapingbits.net) 1326 8. Acknowledgements 1328 This document resulted from the work of the Privacy Pass team 1329 [PrivacyPass]. The authors would also like to acknowledge the 1330 helpful conversations with Hugo Krawczyk. Eli-Shaoul Khedouri 1331 provided additional review and comments on key consistency. 1333 9. References 1335 9.1. Normative References 1337 [BB04] "Short Signatures Without Random Oracles", 1338 . 1340 [BG04] "The Static Diffie-Hellman Problem", 1341 . 1343 [Cheon06] "Security Analysis of the Strong Diffie-Hellman Problem", 1344 . 1347 [DGSTV18] "Privacy Pass, Bypassing Internet Challenges Anonymously", 1348 . 1351 [I-D.davidson-pp-protocol] 1352 Davidson, A., "Privacy Pass: The Protocol", Work in 1353 Progress, Internet-Draft, draft-davidson-pp-protocol-01, 1354 13 July 2020, . 1357 [I-D.irtf-cfrg-hash-to-curve] 1358 Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R., and 1359 C. Wood, "Hashing to Elliptic Curves", Work in Progress, 1360 Internet-Draft, draft-irtf-cfrg-hash-to-curve-10, 11 1361 October 2020, . 1364 [I-D.irtf-cfrg-opaque] 1365 Krawczyk, H., Lewi, K., and C. Wood, "The OPAQUE 1366 Asymmetric PAKE Protocol", Work in Progress, Internet- 1367 Draft, draft-irtf-cfrg-opaque-00, 28 September 2020, 1368 . 1371 [JKK14] "Round-Optimal Password-Protected Secret Sharing and 1372 T-PAKE in the Password-Only model", 1373 . 1375 [JKKX16] "Highly-Efficient and Composable Password-Protected Secret 1376 Sharing (Or, How to Protect Your Bitcoin Wallet Online)", 1377 . 1379 [PrivacyPass] 1380 "Privacy Pass", 1381 . 1383 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1384 Requirement Levels", BCP 14, RFC 2119, 1385 DOI 10.17487/RFC2119, March 1997, 1386 . 1388 [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves 1389 for Security", RFC 7748, DOI 10.17487/RFC7748, January 1390 2016, . 1392 [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, 1393 "PKCS #1: RSA Cryptography Specifications Version 2.2", 1394 RFC 8017, DOI 10.17487/RFC8017, November 2016, 1395 . 1397 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 1398 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 1399 May 2017, . 1401 [RISTRETTO] 1402 Valence, H., Grigg, J., Tankersley, G., Valsorda, F., 1403 Lovecruft, I., and M. Hamburg, "The ristretto255 and 1404 decaf448 Groups", Work in Progress, Internet-Draft, draft- 1405 irtf-cfrg-ristretto255-decaf448-00, 5 October 2020, 1406 . 1409 [SEC1] Standards for Efficient Cryptography Group (SECG), ., "SEC 1410 1: Elliptic Curve Cryptography", 1411 . 1413 [SEC2] Standards for Efficient Cryptography Group (SECG), ., "SEC 1414 2: Recommended Elliptic Curve Domain Parameters", 1415 . 1417 [SJKS17] "SPHINX, A Password Store that Perfectly Hides from 1418 Itself", . 1420 [x9.62] ANSI, "Public Key Cryptography for the Financial Services 1421 Industry: the Elliptic Curve Digital Signature Algorithm 1422 (ECDSA)", ANSI X9.62-1998, September 1998. 1424 9.2. Informative References 1426 [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol 1427 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 1428 . 1430 Authors' Addresses 1432 Alex Davidson 1433 Cloudflare 1434 County Hall 1435 London, SE1 7GP 1436 United Kingdom 1438 Email: alex.davidson92@gmail.com 1439 Armando Faz-Hernandez 1440 Cloudflare 1441 101 Townsend St 1442 San Francisco, 1443 United States of America 1445 Email: armfazh@cloudflare.com 1447 Nick Sullivan 1448 Cloudflare 1449 101 Townsend St 1450 San Francisco, 1451 United States of America 1453 Email: nick@cloudflare.com 1455 Christopher A. Wood 1456 Cloudflare 1457 101 Townsend St 1458 San Francisco, 1459 United States of America 1461 Email: caw@heapingbits.net