Network Working Group A. Davidson Internet-Draft Brave Software Intended status: Informational A. Faz-Hernandez Expires: 7 January 2022 N. Sullivan C.A. Wood Cloudflare 6 July 2021 Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups draft-irtf-cfrg-voprf-07 Abstract An Oblivious Pseudorandom Function (OPRF) is a two-party protocol for computing the output of a PRF. One party (the server) holds the PRF secret key, and the other (the client) holds the PRF input. The 'obliviousness' property ensures that the server does not learn anything about the client's input during the evaluation. The client should also not learn anything about the server's secret PRF key. Optionally, OPRFs can also satisfy a notion 'verifiability' (VOPRF). In this setting, the client can verify that the server's output is indeed the result of evaluating the underlying PRF with just a public key. This document specifies OPRF and VOPRF constructions instantiated within prime-order groups, including elliptic curves. Discussion Venues This note is to be removed before publishing as an RFC. Source for this draft and an issue tracker can be found at https://github.com/cfrg/draft-irtf-cfrg-voprf. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." Davidson, et al. Expires 7 January 2022 [Page 1] Internet-Draft OPRFs July 2021 This Internet-Draft will expire on 7 January 2022. Copyright Notice Copyright (c) 2021 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/ license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Change log . . . . . . . . . . . . . . . . . . . . . . . 4 1.2. Requirements . . . . . . . . . . . . . . . . . . . . . . 6 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1. Prime-Order Group Dependency . . . . . . . . . . . . . . 7 2.2. Conventions and Terminology . . . . . . . . . . . . . . . 8 3. (V)OPRF Protocol . . . . . . . . . . . . . . . . . . . . . . 9 3.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2. Context Setup . . . . . . . . . . . . . . . . . . . . . . 10 3.3. Context APIs . . . . . . . . . . . . . . . . . . . . . . 11 3.3.1. Server Context . . . . . . . . . . . . . . . . . . . 12 3.3.2. VerifiableServerContext . . . . . . . . . . . . . . . 14 3.3.3. Client Context . . . . . . . . . . . . . . . . . . . 18 3.3.4. VerifiableClientContext . . . . . . . . . . . . . . . 20 4. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 25 4.1. OPRF(ristretto255, SHA-512) . . . . . . . . . . . . . . . 25 4.2. OPRF(decaf448, SHAKE-256) . . . . . . . . . . . . . . . . 26 4.3. OPRF(P-256, SHA-256) . . . . . . . . . . . . . . . . . . 26 4.4. OPRF(P-384, SHA-512) . . . . . . . . . . . . . . . . . . 27 4.5. OPRF(P-521, SHA-512) . . . . . . . . . . . . . . . . . . 27 5. API Considerations . . . . . . . . . . . . . . . . . . . . . 28 6. Security Considerations . . . . . . . . . . . . . . . . . . . 28 6.1. Security Properties . . . . . . . . . . . . . . . . . . . 28 6.2. Cryptographic Security . . . . . . . . . . . . . . . . . 29 6.2.1. Computational Hardness Assumptions . . . . . . . . . 29 6.2.2. Protocol Security . . . . . . . . . . . . . . . . . . 30 6.2.3. Q-Strong-DH Oracle . . . . . . . . . . . . . . . . . 31 6.2.4. Implications for Ciphersuite Choices . . . . . . . . 32 6.3. Domain Separation . . . . . . . . . . . . . . . . . . . . 32 6.4. Element and Scalar Validation . . . . . . . . . . . . . . 32 Davidson, et al. Expires 7 January 2022 [Page 2] Internet-Draft OPRFs July 2021 6.5. Hashing to Group . . . . . . . . . . . . . . . . . . . . 33 6.6. Blinding Considerations . . . . . . . . . . . . . . . . . 33 6.7. Timing Leaks . . . . . . . . . . . . . . . . . . . . . . 34 6.8. Key Rotation . . . . . . . . . . . . . . . . . . . . . . 34 6.8.1. Parameter Commitments . . . . . . . . . . . . . . . . 34 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 35 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 35 8.1. Normative References . . . . . . . . . . . . . . . . . . 35 8.2. Informative References . . . . . . . . . . . . . . . . . 37 Appendix A. Test Vectors . . . . . . . . . . . . . . . . . . . . 37 A.1. OPRF(ristretto255, SHA-512) . . . . . . . . . . . . . . . 38 A.1.1. Base Mode . . . . . . . . . . . . . . . . . . . . . . 38 A.1.2. Verifiable Mode . . . . . . . . . . . . . . . . . . . 39 A.2. OPRF(decaf448, SHAKE-256) . . . . . . . . . . . . . . . . 40 A.2.1. Base Mode . . . . . . . . . . . . . . . . . . . . . . 40 A.2.2. Verifiable Mode . . . . . . . . . . . . . . . . . . . 41 A.3. OPRF(P-256, SHA-256) . . . . . . . . . . . . . . . . . . 43 A.3.1. Base Mode . . . . . . . . . . . . . . . . . . . . . . 43 A.3.2. Verifiable Mode . . . . . . . . . . . . . . . . . . . 44 A.4. OPRF(P-384, SHA-512) . . . . . . . . . . . . . . . . . . 45 A.4.1. Base Mode . . . . . . . . . . . . . . . . . . . . . . 45 A.4.2. Verifiable Mode . . . . . . . . . . . . . . . . . . . 46 A.5. OPRF(P-521, SHA-512) . . . . . . . . . . . . . . . . . . 48 A.5.1. Base Mode . . . . . . . . . . . . . . . . . . . . . . 48 A.5.2. Verifiable Mode . . . . . . . . . . . . . . . . . . . 49 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 51 1. Introduction A pseudorandom function (PRF) F(k, x) is an efficiently computable function taking a private key k and a value x as input. This function is pseudorandom if the keyed function K(_) = F(K, _) is indistinguishable from a randomly sampled function acting on the same domain and range as K(). An oblivious PRF (OPRF) is a two-party protocol between a server and a client, where the server holds a PRF key k and the client holds some input x. The protocol allows both parties to cooperate in computing F(k, x) such that: the client learns F(k, x) without learning anything about k; and the server does not learn anything about x or F(k, x). A Verifiable OPRF (VOPRF) is an OPRF wherein the server can prove to the client that F(k, x) was computed using the key k. The usage of OPRFs has been demonstrated in constructing a number of applications: password-protected secret sharing schemes [JKKX16]; privacy-preserving password stores [SJKS17]; and password- authenticated key exchange or PAKE [I-D.irtf-cfrg-opaque]. A VOPRF is necessary in some applications, e.g., the Privacy Pass protocol [I-D.davidson-pp-protocol], wherein this VOPRF is used to generate Davidson, et al. Expires 7 January 2022 [Page 3] Internet-Draft OPRFs July 2021 one-time authentication tokens to bypass CAPTCHA challenges. VOPRFs have also been used for password-protected secret sharing schemes e.g. [JKK14]. This document introduces an OPRF protocol built in prime-order groups, applying to finite fields of prime-order and also elliptic curve (EC) groups. The protocol has the option of being extended to a VOPRF with the addition of a NIZK proof for proving discrete log equality relations. This proof demonstrates correctness of the computation, using a known public key that serves as a commitment to the server's secret key. The document describes the protocol, the public-facing API, and its security properties. 1.1. Change log draft-07 (https://tools.ietf.org/html/draft-irtf-cfrg-voprf-07): * Bind blinding mechanism to mode (additive for verifiable mode and multiplicative for base mode). * Add explicit errors for deserialization. * Document explicit errors and API considerations. * Adopt SHAKE-256 for decaf448 ciphersuite. * Normalize HashToScalar functionality for all ciphersuites. * Refactor and generalize DLEQ proof functionality and domain separation tags for use in other protocols. * Update test vectors. * Apply various editorial changes. draft-06 (https://tools.ietf.org/html/draft-irtf-cfrg-voprf-06): * Specify of group element and scalar serialization. * Remove info parameter from the protocol API and update domain separation guidance. * Fold Unblind function into Finalize. * Optimize ComputeComposites for servers (using knowledge of the private key). * Specify deterministic key generation method. Davidson, et al. Expires 7 January 2022 [Page 4] Internet-Draft OPRFs July 2021 * Update test vectors. * Apply various editorial changes. draft-05 (https://tools.ietf.org/html/draft-irtf-cfrg-voprf-05): * Move to ristretto255 and decaf448 ciphersuites. * Clean up ciphersuite definitions. * Pin domain separation tag construction to draft version. * Move key generation outside of context construction functions. * Editorial changes. draft-04 (https://tools.ietf.org/html/draft-irtf-cfrg-voprf-04): * Introduce Client and Server contexts for controlling verifiability and required functionality. * Condense API. * Remove batching from standard functionality (included as an extension) * Add Curve25519 and P-256 ciphersuites for applications that prevent strong-DH oracle attacks. * Provide explicit prime-order group API and instantiation advice for each ciphersuite. * Proof-of-concept implementation in sage. * Remove privacy considerations advice as this depends on applications. draft-03 (https://tools.ietf.org/html/draft-irtf-cfrg-voprf-03): * Certify public key during VerifiableFinalize. * Remove protocol integration advice. * Add text discussing how to perform domain separation. * Drop OPRF_/VOPRF_ prefix from algorithm names. * Make prime-order group assumption explicit. Davidson, et al. Expires 7 January 2022 [Page 5] Internet-Draft OPRFs July 2021 * Changes to algorithms accepting batched inputs. * Changes to construction of batched DLEQ proofs. * Updated ciphersuites to be consistent with hash-to-curve and added OPRF specific ciphersuites. draft-02 (https://tools.ietf.org/html/draft-irtf-cfrg-voprf-02): * Added section discussing cryptographic security and static DH oracles. * Updated batched proof algorithms. draft-01 (https://tools.ietf.org/html/draft-irtf-cfrg-voprf-01): * Updated ciphersuites to be in line with https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-04. * Made some necessary modular reductions more explicit. 1.2. Requirements The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here. 2. Preliminaries The (V)OPRF protocol in this document has two primary dependencies: * "GG": A prime-order group implementing the API described below in Section 2.1, with base point defined in the corresponding reference for each group. (See Section 4 for these base points.) * "Hash": A cryptographic hash function that is indifferentiable from a Random Oracle, whose output length is Nh bytes long. Section 4 specifies ciphersuites as combinations of "GG" and "Hash". Davidson, et al. Expires 7 January 2022 [Page 6] Internet-Draft OPRFs July 2021 2.1. Prime-Order Group Dependency In this document, we assume the construction of an additive, prime- order group "GG" for performing all mathematical operations. Such groups are uniquely determined by the choice of the prime "p" that defines the order of the group. We use "GF(p)" to represent the finite field of order "p". For the purpose of understanding and implementing this document, we take "GF(p)" to be equal to the set of integers defined by "{0, 1, ..., p-1}". The fundamental group operation is addition "+" with identity element "I". For any elements "A" and "B" of the group "GG", "A + B = B + A" is also a member of "GG". Also, for any "A" in "GG", there exists an element "-A" such that "A + (-A) = (-A) + A = I". Scalar multiplication is equivalent to the repeated application of the group operation on an element A with itself "r-1" times, this is denoted as "r*A = A + ... + A". For any element "A", "p*A=I". We denote "G" as the fixed generator of the group. Scalar base multiplication is equivalent to the repeated application of the group operation "G" with itself "r-1" times, this is denoted as "ScalarBaseMult(r)". The set of scalars corresponds to "GF(p)". This document uses types "Element" and "Scalar" to denote elements of the group "GG" and its set of scalars, respectively. We now detail a number of member functions that can be invoked on a prime-order group "GG". * Order(): Outputs the order of "GG" (i.e. "p"). * Identity(): Outputs the identity element of the group (i.e. "I"). * HashToGroup(x): A member function of "GG" that deterministically maps an array of bytes "x" to an element of "GG". The map must ensure that, for any adversary receiving "R = HashToGroup(x)", it is computationally difficult to reverse the mapping. This function is optionally parameterized by a domain separation tag (DST); see Section 4. * HashToScalar(x): A member function of "GG" that deterministically maps an array of bytes "x" to an element in GF(p). This function is optionally parameterized by a DST; see Section 4. * RandomScalar(): A member function of "GG" that chooses at random a non-zero element in GF(p). * SerializeElement(A): A member function of "GG" that maps a group element "A" to a unique byte array "buf" of fixed length "Ne". The output type of this function is "SerializedElement". Davidson, et al. Expires 7 January 2022 [Page 7] Internet-Draft OPRFs July 2021 * DeserializeElement(buf): A member function of "GG" that maps a byte array "buf" to a group element "A", or fails if the input is not a valid byte representation of an element. This function can raise a DeserializeError if deserialization fails or "A" is the identity element of the group; see Section 6.4. * SerializeScalar(s): A member function of "GG" that maps a scalar element "s" to a unique byte array "buf" of fixed length "Ns". The output type of this function is "SerializedScalar". * DeserializeScalar(buf): A member function of "GG" that maps a byte array "buf" to a scalar "s", or fails if the input is not a valid byte representation of a scalar. This function can raise a DeserializeError if deserialization fails; see Section 6.4. Two functions can be used for generating a (V)OPRF key pair ("skS", "pkS") where "skS" is a non-zero integer less than "p" and "pkS = ScalarBaseMult(skS)": "GenerateKeyPair" and "DeriveKeyPair". "GenerateKeyPair" is a randomized function that outputs a fresh key pair ("skS", "pkS") upon ever invocation. "DeriveKeyPair" is a deterministic function that generates private key "skS" from a random byte string "seed", which SHOULD have at least "Ns" bytes of entropy, and then computes "pkS = ScalarBaseMult(skS)". It is convenient in cryptographic applications to instantiate such prime-order groups using elliptic curves, such as those detailed in [SEC2]. For some choices of elliptic curves (e.g. those detailed in [RFC7748], which require accounting for cofactors) there are some implementation issues that introduce inherent discrepancies between standard prime-order groups and the elliptic curve instantiation. In this document, all algorithms that we detail assume that the group is a prime-order group, and this MUST be upheld by any implementation. That is, any curve instantiation should be written such that any discrepancies with a prime-order group instantiation are removed. See Section 4 for advice corresponding to the implementation of this interface for specific definitions of elliptic curves. 2.2. Conventions and Terminology The following conventions are used throughout the document. * For any object "x", we write "len(x)" to denote its length in bytes. * For two byte arrays "x" and "y", write "x || y" to denote their concatenation. Davidson, et al. Expires 7 January 2022 [Page 8] Internet-Draft OPRFs July 2021 * I2OSP and OS2IP: Convert a byte array to and from a non-negative integer as described in [RFC8017]. Note that these functions operate on byte arrays in big-endian byte order. Data structure descriptions use TLS notation [RFC8446], Section 3. All algorithm descriptions are written in a Python-like pseudocode. We also use the "CT_EQUAL(a, b)" function to represent constant-time byte-wise equality between byte arrays "a" and "b". This function returns "true" if "a" and "b" are equal, and "false" otherwise. The following terms are used throughout this document. * PRF: Pseudorandom Function. * OPRF: Oblivious Pseudorandom Function. * VOPRF: Verifiable Oblivious Pseudorandom Function. * Client: Protocol initiator. Learns pseudorandom function evaluation as the output of the protocol. * Server: Computes the pseudorandom function over a secret key. Learns nothing about the client's input. * NIZK: Non-interactive zero knowledge. * DLEQ: Discrete Logarithm Equality. 3. (V)OPRF Protocol In this section, we define two OPRF variants: a base mode and verifiable mode. In the base mode, a client and server interact to compute y = F(skS, x), where x is the client's input, skS is the server's private key, and y is the OPRF output. The client learns y and the server learns nothing. In the verifiable mode, the client also gets proof that the server used skS in computing the function. To achieve verifiability, as in the original work of [JKK14], we provide a zero-knowledge proof that the key provided as input by the server in the "Evaluate" function is the same key as it used to produce their public key. As an example of the nature of attacks that this prevents, this ensures that the server uses the same private key for computing the VOPRF output and does not attempt to "tag" individual servers with select keys. This proof must not reveal the server's long-term private key to the client. The following one-byte values distinguish between these two modes: Davidson, et al. Expires 7 January 2022 [Page 9] Internet-Draft OPRFs July 2021 +================+=======+ | Mode | Value | +================+=======+ | modeBase | 0x00 | +----------------+-------+ | modeVerifiable | 0x01 | +----------------+-------+ Table 1 3.1. Overview Both participants agree on the mode and a choice of ciphersuite that is used before the protocol exchange. Once established, the base mode of the protocol runs to compute "output = F(skS, input)" as follows: Client(input) Server(skS) ---------------------------------------------------------- blind, blindedElement = Blind(input) blindedElement ----------> evaluatedElement, proof = Evaluate(skS, blindedElement) evaluatedElement <---------- output = Finalize(input, blind, evaluatedElement, blindedElement) In "Blind" the client generates a token and blinding data. The server computes the (V)OPRF evaluation in "Evaluation" over the client's blinded token. In "Finalize" the client unblinds the server response and produces a byte array corresponding to the output of the OPRF protocol. In the verifiable mode of the protocol, the server additionally computes a proof in Evaluate. The client verifies this proof using the server's expected public key before completing the protocol and producing the protocol output. 3.2. Context Setup Both modes of the OPRF involve an offline setup phase. In this phase, both the client and server create a context used for executing the online phase of the protocol. The key pair ("skS", "pkS") should be generated by calling either "GenerateKeyPair" or "DeriveKeyPair". Davidson, et al. Expires 7 January 2022 [Page 10] Internet-Draft OPRFs July 2021 The base mode setup functions for creating client and server contexts are below: def SetupBaseServer(suite, skS): contextString = "VOPRF07-" || I2OSP(modeBase, 1) || I2OSP(suite.ID, 2) return ServerContext(contextString, skS) def SetupBaseClient(suite): contextString = "VOPRF07-" || I2OSP(modeBase, 1) || I2OSP(suite.ID, 2) return ClientContext(contextString) The verifiable mode setup functions for creating client and server contexts are below: def SetupVerifiableServer(suite, skS, pkS): contextString = "VOPRF07-" || I2OSP(modeVerifiable, 1) || I2OSP(suite.ID, 2) return VerifiableServerContext(contextString, skS) def SetupVerifiableClient(suite, pkS): contextString = "VOPRF07-" || I2OSP(modeVerifiable, 1) || I2OSP(suite.ID, 2) return VerifiableClientContext(contextString, pkS) Each setup function takes a ciphersuite from the list defined in Section 4. Each ciphersuite has a two-byte field ID used to identify the suite. [[RFC editor: please change "VOPRF07" to "RFCXXXX", where XXXX is the final number, here and elsewhere before publication.]] 3.3. Context APIs In this section, we detail the APIs available on the client and server (V)OPRF contexts. Each API has the following implicit parameters: * GG, a prime-order group implementing the API described in Section 2.1. * contextString, a domain separation tag taken from the client or server context. The data type "ClientInput" is an opaque byte string of arbitrary length no larger than 2^13 octets. "Proof" is a concatenated sequence of two "SerializedScalar" values, as shown below. Davidson, et al. Expires 7 January 2022 [Page 11] Internet-Draft OPRFs July 2021 SerializedScalar Proof[2*Ns]; 3.3.1. Server Context The ServerContext encapsulates the context string constructed during setup and the (V)OPRF key pair. It has three functions, "Evaluate", "FullEvaluate" and "VerifyFinalize" described below. "Evaluate" takes serialized representations of blinded group elements from the client as inputs. "FullEvaluate" takes ClientInput values, and it is useful for applications that need to compute the whole OPRF protocol on the server side only. "VerifyFinalize" takes ClientInput values and their corresponding output digests from "Finalize" as input, and returns true if the inputs match the outputs. Note that "VerifyFinalize" and "FullEvaluate" are not used in the main OPRF protocol. They are exposed as an API for building higher- level protocols. 3.3.1.1. Evaluate Input: Scalar skS SerializedElement blindedElement Output: SerializedElement evaluatedElement Errors: DeserializeError def Evaluate(skS, blindedElement): R = GG.DeserializeElement(blindedElement) Z = skS * R evaluatedElement = GG.SerializeElement(Z) return evaluatedElement 3.3.1.2. FullEvaluate Davidson, et al. Expires 7 January 2022 [Page 12] Internet-Draft OPRFs July 2021 Input: Scalar skS ClientInput input Output: opaque output[Nh] def FullEvaluate(skS, input): P = GG.HashToGroup(input) T = skS * P issuedElement = GG.SerializeElement(T) finalizeDST = "Finalize-" || contextString hashInput = I2OSP(len(input), 2) || input || I2OSP(len(issuedElement), 2) || issuedElement || I2OSP(len(finalizeDST), 2) || finalizeDST return Hash(hashInput) 3.3.1.3. VerifyFinalize Input: Scalar skS ClientInput input opaque output[Nh] Output: boolean valid def VerifyFinalize(skS, input, output): T = GG.HashToGroup(input) element = GG.SerializeElement(T) issuedElement = Evaluate(skS, [element]) E = GG.SerializeElement(issuedElement) finalizeDST = "Finalize-" || contextString hashInput = I2OSP(len(input), 2) || input || I2OSP(len(E), 2) || E || I2OSP(len(finalizeDST), 2) || finalizeDST digest = Hash(hashInput) return CT_EQUAL(digest, output) Davidson, et al. Expires 7 January 2022 [Page 13] Internet-Draft OPRFs July 2021 3.3.2. VerifiableServerContext The VerifiableServerContext extends the base ServerContext with an augmented "Evaluate()" function. This function produces a proof that "skS" was used in computing the result. It makes use of the helper functions "GenerateProof" and "ComputeComposites", described below. 3.3.2.1. Evaluate Input: Scalar skS Element pkS SerializedElement blindedElement Output: SerializedElement evaluatedElement Proof proof Errors: DeserializeError def Evaluate(skS, pkS, blindedElement): R = GG.DeserializeElement(blindedElement) Z = skS * R evaluatedElement = GG.SerializeElement(Z) proof = GenerateProof(skS, G, pkS, R, Z) return evaluatedElement, proof The helper functions "GenerateProof" and "ComputeComposites" are defined below. 3.3.2.2. GenerateProof Davidson, et al. Expires 7 January 2022 [Page 14] Internet-Draft OPRFs July 2021 Input: Scalar k Element A Element B Element C Element D Output: Proof proof def GenerateProof(k, A, B, C, D) Cs = [C] Ds = [D] a = ComputeCompositesFast(k, B, Cs, Ds) r = GG.RandomScalar() M = a[0] Z = a[1] t2 = r * A t3 = r * M Bm = GG.SerializeElement(B) a0 = GG.SerializeElement(M) a1 = GG.SerializeElement(Z) a2 = GG.SerializeElement(t2) a3 = GG.SerializeElement(t3) challengeDST = "Challenge-" || contextString h2Input = I2OSP(len(Bm), 2) || Bm || I2OSP(len(a0), 2) || a0 || I2OSP(len(a1), 2) || a1 || I2OSP(len(a2), 2) || a2 || I2OSP(len(a3), 2) || a3 || I2OSP(len(challengeDST), 2) || challengeDST c = GG.HashToScalar(h2Input) s = (r - c * k) mod p proof = [GG.SerializeScalar(c), GG.SerializeScalar(s)] return proof Davidson, et al. Expires 7 January 2022 [Page 15] Internet-Draft OPRFs July 2021 3.3.2.2.1. Batching inputs Unlike other functions, "ComputeComposites" takes lists of inputs, rather than a single input. Applications can take advantage of this functionality by invoking "GenerateProof" on batches of inputs to produce a combined, constant-size proof. (In the pseudocode above, the single inputs "blindedElement" and "evaluatedElement" are passed as one-item lists to "ComputeComposites".) In particular, servers can produce a single, constant-sized proof for N client inputs sent in a single request, rather than one proof per client input. This optimization benefits clients and servers since it amortizes the cost of proof generation and bandwidth across multiple requests. 3.3.2.2.2. Fresh Randomness We note here that it is essential that a different "r" value is used for every invocation. If this is not done, then this may leak "skS" as is possible in Schnorr or (EC)DSA scenarios where fresh randomness is not used. 3.3.2.3. ComputeComposites The definition of "ComputeComposites" is given below. This function is used both on generation and verification of the proof. Davidson, et al. Expires 7 January 2022 [Page 16] Internet-Draft OPRFs July 2021 Input: Element B Element Cs[m] Element Ds[m] Output: Element composites[2] def ComputeComposites(B, Cs, Ds): Bm = GG.SerializeElement(B) seedDST = "Seed-" || contextString compositeDST = "Composite-" || contextString h1Input = I2OSP(len(Bm), 2) || Bm || I2OSP(len(seedDST), 2) || seedDST seed = Hash(h1Input) M = GG.Identity() Z = GG.Identity() for i = 0 to m-1: Ci = GG.SerializeElement(Cs[i]) Di = GG.SerializeElement(Ds[i]) h2Input = I2OSP(len(seed), 2) || seed || I2OSP(i, 2) || I2OSP(len(Ci), 2) || Ci || I2OSP(len(Di), 2) || Di || I2OSP(len(compositeDST), 2) || compositeDST di = GG.HashToScalar(h2Input) M = di * Cs[i] + M Z = di * Ds[i] + Z return [M, Z] If the private key is known, as is the case for the server, this function can be optimized as shown in "ComputeCompositesFast" below. Davidson, et al. Expires 7 January 2022 [Page 17] Internet-Draft OPRFs July 2021 Input: Scalar k Element B Element Cs[m] Element Ds[m] Output: Element composites[2] def ComputeCompositesFast(k, B, Cs, Ds): Bm = GG.SerializeElement(B) seedDST = "Seed-" || contextString compositeDST = "Composite-" || contextString h1Input = I2OSP(len(Bm), 2) || Bm || I2OSP(len(seedDST), 2) || seedDST seed = Hash(h1Input) M = GG.Identity() for i = 0 to m-1: Ci = GG.SerializeElement(Cs[i]) Di = GG.SerializeElement(Ds[i]) h2Input = I2OSP(len(seed), 2) || seed || I2OSP(i, 2) || I2OSP(len(Ci), 2) || Ci || I2OSP(len(Di), 2) || Di || I2OSP(len(compositeDST), 2) || compositeDST di = GG.HashToScalar(h2Input) M = di * Cs[i] + M Z = k * M return [M, Z] 3.3.3. Client Context The ClientContext encapsulates the context string constructed during setup. It has two functions, "Blind()" and "Finalize()", as described below. It also has an internal function, "Unblind()", which is used by "Finalize". The implementation of these functions varies depending on the mode. Davidson, et al. Expires 7 January 2022 [Page 18] Internet-Draft OPRFs July 2021 3.3.3.1. Blind In this mode, blinding is done multiplicatively. Under certain application circumstances, the more optimal additive blinding mechanism described in Section 3.3.4.2 can be used. See Section 6.6 for more details. "Blind" is implemented as follows. Input: ClientInput input Output: Scalar blind SerializedElement blindedElement def Blind(input): blind = GG.RandomScalar() P = GG.HashToGroup(input) blindedElement = GG.SerializeElement(blind * P) return blind, blindedElement The inverse "Unblind" is implemented as follows. Input: Scalar blind SerializedElement evaluatedElement Output: SerializedElement unblindedElement Errors: DeserializeError def Unblind(blind, evaluatedElement, ...): Z = GG.DeserializeElement(evaluatedElement) N = (blind^(-1)) * Z unblindedElement = GG.SerializeElement(N) return unblindedElement Davidson, et al. Expires 7 January 2022 [Page 19] Internet-Draft OPRFs July 2021 3.3.3.2. Finalize "Finalize" depends on the internal "Unblind" function. In this mode, "Finalize" and does not include all inputs listed in Section 3.1. These additional inputs are only useful for the verifiable mode, described in Section 3.3.4.3. Input: ClientInput input Scalar blind SerializedElement evaluatedElement Output: opaque output[Nh] def Finalize(input, blind, evaluatedElement): unblindedElement = Unblind(blind, evaluatedElement) finalizeDST = "Finalize-" || contextString hashInput = I2OSP(len(input), 2) || input || I2OSP(len(unblindedElement), 2) || unblindedElement || I2OSP(len(finalizeDST), 2) || finalizeDST return Hash(hashInput) 3.3.4. VerifiableClientContext The VerifiableClientContext extends the base ClientContext with the desired server public key "pkS" with an augmented "Unblind()" function. This function verifies an evaluation proof using "pkS". It makes use of the helper function "ComputeComposites" described above. It has one helper function, "VerifyProof()", defined below. 3.3.4.1. VerifyProof This algorithm outputs a boolean "verified" which indicates whether the proof inside of the evaluation verifies correctly, or not. Davidson, et al. Expires 7 January 2022 [Page 20] Internet-Draft OPRFs July 2021 Input: Element A Element B Element C Element D Proof proof Output: boolean verified def VerifyProof(A, B, C, D, proof): Cs = [C] Ds = [D] a = ComputeComposites(B, Cs, Ds) c = GG.DeserializeScalar(proof[0]) s = GG.DeserializeScalar(proof[1]) M = a[0] Z = a[1] t2 = ((s * A) + (c * B)) t3 = ((s * M) + (c * Z)) Bm = GG.SerializeElement(B) a0 = GG.SerializeElement(M) a1 = GG.SerializeElement(Z) a2 = GG.SerializeElement(t2) a3 = GG.SerializeElement(t3) challengeDST = "Challenge-" || contextString h2Input = I2OSP(len(Bm), 2) || Bm || I2OSP(len(a0), 2) || a0 || I2OSP(len(a1), 2) || a1 || I2OSP(len(a2), 2) || a2 || I2OSP(len(a3), 2) || a3 || I2OSP(len(challengeDST), 2) || challengeDST expectedC = GG.HashToScalar(h2Input) return CT_EQUAL(expectedC, c) Davidson, et al. Expires 7 January 2022 [Page 21] Internet-Draft OPRFs July 2021 3.3.4.2. Verifiable Blind In this mode, where the server public key is available for proof verification, blinding is done additively. This variant is named "VerifiableBlind" and "VerifiableUnblind". It takes two inputs: the client input and a blinded version of the group generator. The latter is computed using a function called "VerifiablePreprocess", also described below. "VerifiableBlind" is implemented as follows. Input: ClientInput input Element blindedGenerator Output: SerializedElement blindedElement def VerifiableBlind(input, blindedGenerator): P = GG.HashToGroup(input) blindedElement = GG.SerializeElement(P + blindedGenerator) return blindedElement The inverse "VerifiableUnblind" is implemented as follows. This function can raise an exception if element deserialization or proof verification fails. Davidson, et al. Expires 7 January 2022 [Page 22] Internet-Draft OPRFs July 2021 Input: Element blindedPublicKey SerializedElement evaluatedElement SerializedElement blindedElement Element pkS Scalar proof Output: SerializedElement unblindedElement Errors: DeserializeError, VerifyError def VerifiableUnblind(blindedPublicKey, evaluatedElement, blindedElement, pkS, proof): Z = GG.DeserializeElement(evaluatedElement) R = GG.DeserializeElement(blindedElement) if VerifyProof(G, pkS, R, Z, proof) == false: raise VerifyError N := Z - blindedPublicKey unblindedElement = GG.SerializeElement(N) return unblindedElement The internal "VerifiablePreprocess" function computes a blind and uses it to compute a corresponding blinded version of the group generator and server public key. This function can be used to pre- compute tables of values for future invocations of the protocol, or it can be computed only when needed for a single invocation of the protocol. Davidson, et al. Expires 7 January 2022 [Page 23] Internet-Draft OPRFs July 2021 Input: Element pkS Output: Element blindedGenerator Element blindedPublicKey Scalar blind def Preprocess(pkS): blind = GG.RandomScalar() blindedGenerator = ScalarBaseMult(blind) blindedPublicKey = pkS * blind return blindedGenerator, blindedPublicKey, blind 3.3.4.3. Verifiable Finalize Input: ClientInput input Element blindedPublicKey SerializedElement evaluatedElement SerializedElement blindedElement Element pkS Scalar proof Output: opaque output[Nh] def Finalize(input, blindedPublicKey, evaluatedElement, blindedElement, pkS, proof): unblindedElement = VerifiableUnblind(blindedPublicKey, evaluatedElement, blindedElement, pkS, proof) finalizeDST = "Finalize-" || contextString hashInput = I2OSP(len(input), 2) || input || I2OSP(len(unblindedElement), 2) || unblindedElement || I2OSP(len(finalizeDST), 2) || finalizeDST return Hash(hashInput) Davidson, et al. Expires 7 January 2022 [Page 24] Internet-Draft OPRFs July 2021 4. Ciphersuites A ciphersuite (also referred to as 'suite' in this document) for the protocol wraps the functionality required for the protocol to take place. This ciphersuite should be available to both the client and server, and agreement on the specific instantiation is assumed throughout. A ciphersuite contains instantiations of the following functionalities: * "GG": A prime-order group exposing the API detailed in Section 2.1, with base point defined in the corresponding reference for each group. Each group also specifies HashToGroup, HashToScalar, and serialization functionalities. For HashToGroup, the domain separation tag (DST) is constructed in accordance with the recommendations in [I-D.irtf-cfrg-hash-to-curve], Section 3.1. For HashToScalar, each group specifies an integer order that is used in reducing integer values to a member of the corresponding scalar field. * "Hash": A cryptographic hash function that is indifferentiable from a Random Oracle, whose output length is Nh bytes long. This section specifies ciphersuites with supported groups and hash functions. For each ciphersuite, contextString is that which is computed in the Setup functions. Applications should take caution in using ciphersuites targeting P-256 and ristretto255. See Section 6.2 for related discussion. 4.1. OPRF(ristretto255, SHA-512) * Group: ristretto255 [RISTRETTO] - HashToGroup(): Use hash_to_ristretto255 [I-D.irtf-cfrg-hash-to-curve] with DST = "HashToGroup-" || contextString, and "expand_message" = "expand_message_xmd" using SHA-512. - HashToScalar(): Compute "uniform_bytes" using "expand_message" = "expand_message_xmd", DST = "HashToScalar-" || contextString, and output length 64, interpret "uniform_bytes" as a 512-bit integer in little-endian order, and reduce the integer modulo "Order()". - Serialization: Both group elements and scalars are encoded in Ne = Ns = 32 bytes. For group elements, use the 'Encode' and 'Decode' functions from [RISTRETTO]. For scalars, ensure they are fully reduced modulo "Order()" and in little-endian order. Davidson, et al. Expires 7 January 2022 [Page 25] Internet-Draft OPRFs July 2021 * Hash: SHA-512, and Nh = 64. * ID: 0x0001 4.2. OPRF(decaf448, SHAKE-256) * Group: decaf448 [RISTRETTO] - HashToGroup(): Use hash_to_decaf448 [I-D.irtf-cfrg-hash-to-curve] with DST = "HashToGroup-" || contextString, and "expand_message" = "expand_message_xof" using SHAKE-256. - HashToScalar(): Compute "uniform_bytes" using "expand_message" = "expand_message_xof", DST = "HashToScalar-" || contextString, and output length 64, interpret "uniform_bytes" as a 512-bit integer in little-endian order, and reduce the integer modulo "Order()". - Serialization: Both group elements and scalars are encoded in Ne = Ns = 56 bytes. For group elements, use the 'Encode' and 'Decode' functions from [RISTRETTO]. For scalars, ensure they are fully reduced modulo "Order()" and in little-endian order. * Hash: SHAKE-256, and Nh = 64. * ID: 0x0002 4.3. OPRF(P-256, SHA-256) * Group: P-256 (secp256r1) [x9.62] - HashToGroup(): Use hash_to_curve with suite P256_XMD:SHA- 256_SSWU_RO_ [I-D.irtf-cfrg-hash-to-curve] and DST = "HashToGroup-" || contextString. - HashToScalar(): Use hash_to_field from [I-D.irtf-cfrg-hash-to-curve] using L = 48, "expand_message_xmd" with SHA-256, DST = "HashToScalar-" || contextString, and prime modulus equal to "Order()". - Serialization: Elements are serialized as Ne = 33 byte strings using compressed point encoding for the curve [SEC1]. Scalars are serialized as Ns = 32 byte strings by fully reducing the value modulo "Order()" and in big-endian order. * Hash: SHA-256, and Nh = 32. Davidson, et al. Expires 7 January 2022 [Page 26] Internet-Draft OPRFs July 2021 * ID: 0x0003 4.4. OPRF(P-384, SHA-512) * Group: P-384 (secp384r1) [x9.62] - HashToGroup(): Use hash_to_curve with suite P384_XMD:SHA- 512_SSWU_RO_ [I-D.irtf-cfrg-hash-to-curve] and DST = "HashToGroup-" || contextString. - HashToScalar(): Use hash_to_field from [I-D.irtf-cfrg-hash-to-curve] using L = 72, "expand_message_xmd" with SHA-512, DST = "HashToScalar-" || contextString, and prime modulus equal to "Order()". - Serialization: Elements are serialized as Ne = 49 byte strings using compressed point encoding for the curve [SEC1]. Scalars are serialized as Ns = 48 byte strings by fully reducing the value modulo "Order()" and in big-endian order. * Hash: SHA-512, and Nh = 64. * ID: 0x0004 4.5. OPRF(P-521, SHA-512) * Group: P-521 (secp521r1) [x9.62] - HashToGroup(): Use hash_to_curve with suite P521_XMD:SHA- 512_SSWU_RO_ [I-D.irtf-cfrg-hash-to-curve] and DST = "HashToGroup-" || contextString. - HashToScalar(): Use hash_to_field from [I-D.irtf-cfrg-hash-to-curve] using L = 98, "expand_message_xmd" with SHA-512, DST = "HashToScalar-" || contextString, and prime modulus equal to "Order()". - Serialization: Elements are serialized as Ne = 67 byte strings using compressed point encoding for the curve [SEC1]. Scalars are serialized as Ns = 66 byte strings by fully reducing the value modulo "Order()" and in big-endian order. * Hash: SHA-512, and Nh = 64. * ID: 0x0005 Davidson, et al. Expires 7 January 2022 [Page 27] Internet-Draft OPRFs July 2021 5. API Considerations Some VOPRF APIs specified in this document are fallible. For example, "Finalize" and "Evaluate" can fail if any element received from the peer fails deserialization. The explicit errors generated throughout this specification, along with the conditions that lead to each error, are as follows: * "VerifyError": VOPRF proof verification failed; Section 3.3.4.2. * "DeserializeError": Group element or scalar deserialization failure; Section 2.1. The errors in this document are meant as a guide to implementors. They are not an exhaustive list of all the errors an implementation might emit. For example, implementations might run out of memory and return a corresponding error. 6. Security Considerations This section discusses the cryptographic security of our protocol, along with some suggestions and trade-offs that arise from the implementation of an OPRF. 6.1. Security Properties The security properties of an OPRF protocol with functionality y = F(k, x) include those of a standard PRF. Specifically: * Pseudorandomness: F is pseudorandom if the output y = F(k,x) on any input x is indistinguishable from uniformly sampling any element in F's range, for a random sampling of k. In other words, consider an adversary that picks inputs x from the domain of F and evaluates F on (k,x) (without knowledge of randomly sampled k). Then the output distribution F(k,x) is indistinguishable from the output distribution of a randomly chosen function with the same domain and range. A consequence of showing that a function is pseudorandom, is that it is necessarily non-malleable (i.e. we cannot compute a new evaluation of F from an existing evaluation). A genuinely random function will be non-malleable with high probability, and so a pseudorandom function must be non-malleable to maintain indistinguishability. An OPRF protocol must also satisfy the following property: Davidson, et al. Expires 7 January 2022 [Page 28] Internet-Draft OPRFs July 2021 * Oblivious: The server must learn nothing about the client's input or the output of the function. In addition, the client must learn nothing about the server's private key. Essentially, obliviousness tells us that, even if the server learns the client's input x at some point in the future, then the server will not be able to link any particular OPRF evaluation to x. This property is also known as unlinkability [DGSTV18]. Optionally, for any protocol that satisfies the above properties, there is an additional security property: * Verifiable: The client must only complete execution of the protocol if it can successfully assert that the OPRF output it computes is correct. This is taken with respect to the OPRF key held by the server. Any OPRF that satisfies the 'verifiable' security property is known as a verifiable OPRF, or VOPRF for short. In practice, the notion of verifiability requires that the server commits to the key before the actual protocol execution takes place. Then the client verifies that the server has used the key in the protocol using this commitment. In the following, we may also refer to this commitment as a public key. 6.2. Cryptographic Security Below, we discuss the cryptographic security of the (V)OPRF protocol from Section 3, relative to the necessary cryptographic assumptions that need to be made. 6.2.1. Computational Hardness Assumptions Each assumption states that the problems specified below are computationally difficult to solve in relation to a particular choice of security parameter "sp". Let GG = GG(sp) be a group with prime-order p, and let GF(p) be a finite field of order p. 6.2.1.1. Discrete-log (DL) Problem Given G, a generator of GG, and H = hG for some h in GF(p); output h. 6.2.1.2. Decisional Diffie-Hellman (DDH) Problem Sample uniformly at random d in {0,1}. Given (G, aG, bG, C), where Davidson, et al. Expires 7 January 2022 [Page 29] Internet-Draft OPRFs July 2021 * G is a generator of GG; * a,b are elements of GF(p); * if d == 0: C = abG; else: C is sampled uniformly at random from GG. Output d' == d. 6.2.2. Protocol Security Our OPRF construction is based on the VOPRF construction known as 2HashDH-NIZK given by [JKK14]; essentially without providing zero- knowledge proofs that verify that the output is correct. Our VOPRF construction is identical to the [JKK14] construction, except that we can optionally perform multiple VOPRF evaluations in one go, whilst only constructing one NIZK proof object. This is enabled using an established batching technique. Consequently, the cryptographic security of our construction is based on the assumption that the One-More Gap DH is computationally difficult to solve. The (N,Q)-One-More Gap DH (OMDH) problem asks the following. Given: - G, k * G, and (G_1, ... , G_N), all elements of GG; - oracle access to an OPRF functionality using the key k; - oracle access to DDH solvers. Find Q+1 pairs of the form below: (G_{j_s}, k * G_{j_s}) where the following conditions hold: - s is a number between 1 and Q+1; - j_s is a number between 1 and N for each s; - Q is the number of allowed queries. The original paper [JKK14] gives a security proof that the 2HashDH- NIZK construction satisfies the security guarantees of a VOPRF protocol Section 6.1 under the OMDH assumption in the universal composability (UC) security model. Davidson, et al. Expires 7 January 2022 [Page 30] Internet-Draft OPRFs July 2021 6.2.3. Q-Strong-DH Oracle A side-effect of our OPRF design is that it allows instantiation of a oracle for constructing Q-strong-DH (Q-sDH) samples. The Q-Strong-DH problem asks the following. Given G1, G2, h*G2, (h^2)*G2, ..., (h^Q)*G2; for G1 and G2 generators of GG. Output ( (1/(k+c))*G1, c ) where c is an element of GF(p) The assumption that this problem is hard was first introduced in [BB04]. Since then, there have been a number of cryptanalytic studies that have reduced the security of the assumption below that implied by the group instantiation (for example, [BG04] and [Cheon06]). In summary, the attacks reduce the security of the group instantiation by log_2(Q)/2 bits. Note that the attacks only work in situations where Q divides p-1 or p+1, where p is the order of the prime-order group used to instantiate the OPRF. As an example, suppose that a group instantiation is used that provides 128 bits of security against discrete log cryptanalysis. Then an adversary with access to a Q-sDH oracle and makes Q=2^20 queries can reduce the security of the instantiation by log_2(2^20)/2 = 10 bits. Launching an attack would require 2^(p/2-log_2(Q)/2) bits of memory. Notice that it is easy to instantiate a Q-sDH oracle using the OPRF functionality that we provide. A client can just submit sequential queries of the form (G, k * G, (k^2)G, ..., (k^(Q-1))G), where each query is the output of the previous interaction. This means that any client that submits Q queries to the OPRF can use the aforementioned attacks to reduce the security of the group instantiation by (log_2(Q)/2) bits. Recall that from a malicious client's perspective, the adversary wins if they can distinguish the OPRF interaction from a protocol that computes the ideal functionality provided by the PRF. Davidson, et al. Expires 7 January 2022 [Page 31] Internet-Draft OPRFs July 2021 6.2.4. Implications for Ciphersuite Choices The OPRF instantiations that we recommend in this document are informed by the cryptanalytic discussion above. In particular, choosing elliptic curves configurations that describe 128-bit group instantiations would appear to in fact instantiate an OPRF with 128-(log_2(Q)/2) bits of security. Moreover, such attacks are only possible for those certain applications where the adversary can query the OPRF directly. In applications where such an oracle is not made available this security loss does not apply. In most cases, it would require an informed and persistent attacker to launch a highly expensive attack to reduce security to anything much below 100 bits of security. We see this possibility as something that may result in problems in the future. For applications that admit the aforementioned oracle functionality, and that cannot tolerate discrete logarithm security of lower than 128 bits, we recommend only implementing ciphersuites with IDs 0x0002, 0x0004, and 0x0005. 6.3. Domain Separation Applications SHOULD construct input to the protocol to provide domain separation. Any system which has multiple (V)OPRF applications should distinguish client inputs to ensure the OPRF results are separate. Guidance for constructing info can be found in [I-D.irtf-cfrg-hash-to-curve]; Section 3.1. 6.4. Element and Scalar Validation The DeserializeElement function recovers a group element from an arbitrary byte array. This function validates that the element is a proper member of the group and is not the identity element, and returns an error if either condition is not met. For P-256, P-384, and P-521 ciphersuites, this function performs partial public-key validation as defined in Section 5.6.2.3.4 of [keyagreement]. This includes checking that the coordinates are in the correct range, that the point is on the curve, and that the point is not the point at infinity. If these checks fail, deserialization returns an error. For ristretto255 and decaf448, elements are deserialized by invoking the Decode function from [RISTRETTO], Section 4.3.1 and [RISTRETTO], Section 5.3.1, respectively, which returns false if the element is invalid. If this function returns false, deserialization returns an error. Davidson, et al. Expires 7 January 2022 [Page 32] Internet-Draft OPRFs July 2021 The DeserializeScalar function recovers a scalar field element from an arbitrary byte array. Like DeserializeElement, this function validates that the element is a member of the scalar field and returns an error if this condition is not met. For P-256, P-384, and P-521 ciphersuites, this function ensures that the input, when treated as a big-endian integer, is a value between 0 and "Order()". For ristretto255 and decaf448, this function ensures that the input, when treated as a little-endian integer, is a valud between 0 and "Order()". 6.5. Hashing to Group A critical requirement of implementing the prime-order group using elliptic curves is a method to instantiate the function "GG.HashToGroup", that maps inputs to group elements. In the elliptic curve setting, this deterministically maps inputs x (as byte arrays) to uniformly chosen points on the curve. In the security proof of the construction Hash is modeled as a random oracle. This implies that any instantiation of "GG.HashToGroup" must be pre-image and collision resistant. In Section 4 we give instantiations of this functionality based on the functions described in [I-D.irtf-cfrg-hash-to-curve]. Consequently, any OPRF implementation must adhere to the implementation and security considerations discussed in [I-D.irtf-cfrg-hash-to-curve] when instantiating the function. 6.6. Blinding Considerations This document makes use of two types of blinding variants: multiplicative and additive. The advantage of additive blinding is that it allows the client to pre-process tables of blinded scalar multiplications for the group generator and server public key. This can provide a computational efficiency advantage (due to the fact that a fixed-base multiplication can be calculated faster than a variable-base multiplication). Pre-processing also reduces the amount of computation that needs to be done in the online exchange. However, the choice of blinding mechanism has security implications. [JKX21] analyze the security properties of both blinding mechanisms used in this document. The results can be summarized as follows: * Multiplicative blinding is safe for all applications. * Additive blinding is possibly unsafe, unless one of the following conditions are met: Davidson, et al. Expires 7 January 2022 [Page 33] Internet-Draft OPRFs July 2021 - The client has a certified copy of the server public key (as is the case in the verifiable mode); - The client input has high entropy; and - The client mixes the public key into the OPRF evaluation. To avoid security issues with the base mode, where some of the above conditions may not be met, this specification RECOMMENDS use of multiplicative blinding. This is because it is not known if the server public key is available or if the client input has high entropy. Applications wherein either of these conditions are true MAY use additive blinding. The verifiable mode always makes use of the more efficient additive blinding variant, as the public key is always available for verifying the proof. 6.7. Timing Leaks To ensure no information is leaked during protocol execution, all operations that use secret data MUST run in constant time. Operations that SHOULD run in constant time include all prime-order group operations and proof-specific operations ("GenerateProof()" and "VerifyProof()"). 6.8. Key Rotation Since the server's key is critical to security, the longer it is exposed by performing (V)OPRF operations on client inputs, the longer it is possible that the key can be compromised. For example, if the key is kept in circulation for a long period of time, then it also allows the clients to make enough queries to launch more powerful variants of the Q-sDH attacks from Section 6.2.3. To combat attacks of this nature, regular key rotation should be employed on the server-side. A suitable key-cycle for a key used to compute (V)OPRF evaluations would be between one week and six months. 6.8.1. Parameter Commitments For some applications, it may be desirable for the server to bind tokens to certain parameters, e.g., protocol versions, ciphersuites, etc. To accomplish this, the server should use a distinct scalar for each parameter combination. Upon redemption of a token T from the client, the server can later verify that T was generated using the scalar associated with the corresponding parameters. Davidson, et al. Expires 7 January 2022 [Page 34] Internet-Draft OPRFs July 2021 7. Acknowledgements This document resulted from the work of the Privacy Pass team [PrivacyPass]. The authors would also like to acknowledge helpful conversations with Hugo Krawczyk. Eli-Shaoul Khedouri provided additional review and comments on key consistency. Daniel Bourdrez, Tatiana Bradley, Sofia Celi, Frank Denis, and Bas Westerbaan also provided helpful input and contributions to the document. 8. References 8.1. Normative References [BB04] "Short Signatures Without Random Oracles", . [BG04] "The Static Diffie-Hellman Problem", . [Cheon06] "Security Analysis of the Strong Diffie-Hellman Problem", . [DGSTV18] "Privacy Pass, Bypassing Internet Challenges Anonymously", . [I-D.davidson-pp-protocol] Davidson, A., "Privacy Pass: The Protocol", Work in Progress, Internet-Draft, draft-davidson-pp-protocol-01, 13 July 2020, . [I-D.irtf-cfrg-hash-to-curve] Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R. S., and C. A. Wood, "Hashing to Elliptic Curves", Work in Progress, Internet-Draft, draft-irtf-cfrg-hash-to-curve- 11, 13 April 2021, . [I-D.irtf-cfrg-opaque] Krawczyk, H., Bourdrez, D., Lewi, K., and C. A. Wood, "The OPAQUE Asymmetric PAKE Protocol", Work in Progress, Internet-Draft, draft-irtf-cfrg-opaque-05, 7 June 2021, . Davidson, et al. Expires 7 January 2022 [Page 35] Internet-Draft OPRFs July 2021 [JKK14] "Round-Optimal Password-Protected Secret Sharing and T-PAKE in the Password-Only model", . [JKKX16] "Highly-Efficient and Composable Password-Protected Secret Sharing (Or, How to Protect Your Bitcoin Wallet Online)", . [PrivacyPass] "Privacy Pass", . [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10.17487/RFC7748, January 2016, . [RFC8017] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2", RFC 8017, DOI 10.17487/RFC8017, November 2016, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . [RISTRETTO] Valence, H. D., Grigg, J., Tankersley, G., Valsorda, F., Lovecruft, I., and M. Hamburg, "The ristretto255 and decaf448 Groups", Work in Progress, Internet-Draft, draft- irtf-cfrg-ristretto255-decaf448-00, 5 October 2020, . [SEC1] Standards for Efficient Cryptography Group (SECG), ., "SEC 1: Elliptic Curve Cryptography", . [SEC2] Standards for Efficient Cryptography Group (SECG), ., "SEC 2: Recommended Elliptic Curve Domain Parameters", . [SJKS17] "SPHINX, A Password Store that Perfectly Hides from Itself", . Davidson, et al. Expires 7 January 2022 [Page 36] Internet-Draft OPRFs July 2021 [x9.62] ANSI, "Public Key Cryptography for the Financial Services Industry: the Elliptic Curve Digital Signature Algorithm (ECDSA)", ANSI X9.62-1998, September 1998. 8.2. Informative References [JKX21] Jarecki, S., Krawczyk, H., and J. Xu, "On the (In)Security of the Diffie-Hellman Oblivious PRF with Multiplicative Blinding", PKC'21 , March 2021, . [keyagreement] Barker, E., Chen, L., Roginsky, A., Vassilev, A., and R. Davis, "Recommendation for pair-wise key-establishment schemes using discrete logarithm cryptography", National Institute of Standards and Technology report, DOI 10.6028/nist.sp.800-56ar3, April 2018, . [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, . Appendix A. Test Vectors This section includes test vectors for the (V)OPRF protocol specified in this document. For each ciphersuite specified in Section 4, there is a set of test vectors for the protocol when run in the base mode and verifiable mode. Each test vector lists the batch size for the evaluation. Each test vector value is encoded as a hexadecimal byte string. The label for each test vector value is described below. * "Input": The client input, an opaque byte string. * "Blind": The blind value output by "Blind()", a serialized "Scalar" of "Ns" bytes long. * "BlindedElement": The blinded value output by "Blind()", a serialized "Element" of "Ne" bytes long. * "EvaluatedElement": The evaluated element output by "Evaluate()", a serialized "Element" of "Ne" bytes long. * "EvaluationProofC": The "c" component of the Evaluation proof (only listed for verifiable mode test vectors), a serialized "Scalar" of "Ns" bytes long. Davidson, et al. Expires 7 January 2022 [Page 37] Internet-Draft OPRFs July 2021 * "EvaluationProofS": The "s" component of the Evaluation proof (only listed for verifiable mode test vectors), a serialized "Scalar" of "Ns" bytes long. * "Output": The OPRF output, a byte string of length "Nh" bytes. Test vectors with batch size B > 1 have inputs separated by a comma ",". Applicable test vectors will have B different values for the "Input", "Blind", "BlindedElement", "EvaluationElement", and "Output" fields. Base mode uses multiplicative blinding while verifiable mode uses additive blinding, as described in Section 3.3.3 and Section 3.3.4, respectively. The server key material, "pkSm" and "skSm", are listed under the mode for each ciphersuite. Both "pkSm" and "skSm" are the serialized values of "pkS" and "skS", respectively, as used in the protocol. Each key pair is derived from a "seed", which is listed as well, using the following implementation of "DeriveKeyPair": def DeriveKeyPair(mode, suite, seed): skS = GG.HashToScalar(seed, DST = "HashToScalar-" || contextString) pkS = ScalarBaseMult(skS) return skS, pkS A.1. OPRF(ristretto255, SHA-512) A.1.1. Base Mode seed = a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a 3a3 skSm = caeff69352df4905a9121a4997704ca8cee1524a110819eb87deba1a39ec1 701 A.1.1.1. Test Vector 1, Batch Size 1 Input = 00 Blind = c604c785ada70d77a5256ae21767de8c3304115237d262134f5e46e512cf 8e03 BlindedElement = fc20e03aff3a9de9b37e8d35886ade11ec7d85c2a1fb5bb0b16 86c64e07ac467 EvaluationElement = 7c72cc293cd7d44c0b57c273f27befd598b132edc665694b dc9c42a4d3083c0a Output = e3a209dce2d3ea3d84fcddb282818caebb756a341e08a310d9904314f53 92085d13c3f76339d745db0f46974a6049c3ea9546305af55d37760b2136d9b3f013 4 Davidson, et al. Expires 7 January 2022 [Page 38] Internet-Draft OPRFs July 2021 A.1.1.2. Test Vector 2, Batch Size 1 Input = 5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a Blind = 5ed895206bfc53316d307b23e46ecc6623afb3086da74189a416012be037 e50b BlindedElement = 483d4f39de5ff77fa0f9a0ad2334dd5bf87f2cda868539d21de 67ce49e7d1536 EvaluationElement = 026f2758fc62f02a7ff95f35ec6f20186aa57c0274361655 543ea235d7b2aa34 Output = 2c17dc3e9398dadb44bb2d3360c446302e99f1fe0ec40f0b1ad25c9cf00 2be1e4b41b4900ef056537fe8c14532ccea4d796f5feab9541af48057d83c0db86fe 9 A.1.2. Verifiable Mode seed = a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a 3a3 skSm = ac37d5850510299406ea8eb8fa226a7bfc2467a4b070d6c7bf667948b9600 b00 pkSm = 0c0254e22063cae3e1bae02fb6fa20882664a117c0278eda6bda3372c0dd9 860 A.1.2.1. Test Vector 1, Batch Size 1 Input = 00 Blind = ed8366feb6b1d05d1f46acb727061e43aadfafe9c10e5a64e7518d63e326 3503 BlindedElement = 66a2835d9da73ecf1ea433bca7ae2b887995cf4b1ffc14f77de 0a417e880a534 EvaluationElement = 8ac09f2a720b3ff03373776edaff052ac4cbe685737df20b 82f6ae1829b21f25 EvaluationProofC = a82634a5381954a31a2f537f76a6765ed6965ed5a48599b41 064d213b06e4b0f EvaluationProofS = 4b8e4ce683fdc433965db51efb9573a669e83ed5982b05a48 3b71fa181179e0c Output = e694146179b874ff64f0c9ec59c292031e7d3386703d0ed129cfee98eec eeb184c0335c7c28be75f7298a33a48c05b2acbd36169a075e495f710c490b404ce3 0 A.1.2.2. Test Vector 2, Batch Size 1 Davidson, et al. Expires 7 January 2022 [Page 39] Internet-Draft OPRFs July 2021 Input = 5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a Blind = e6d0f1d89ad552e383d6c6f4e8598cc3037d6e274d22da3089e7afbd4171 ea02 BlindedElement = 122d4446e76662865ff48a7f1117eab928cfdaafca237e3b424 7cb9c6761fd0f EvaluationElement = 6438480e8cbff8afbcd23f8655910388a9251874b008e1aa 9ff36f3f89c0e02a EvaluationProofC = c7a18f8d95aceb7f5948cb3c8747b3d33900a6f3d7ccb9236 5860da919ebd705 EvaluationProofS = 67e02e92883fa976ca171b87807450af9ac638581311bd5bc cc9efa8ddae020a Output = aa5475f7d60613eab56bf317ea10340ed26be9cbea9685f2617f5a68d55 09a485a15d4db1b41c3ef0f68dd54cc3a4a53d92813797babb0683b71263f5e63b3f 6 A.1.2.3. Test Vector 3, Batch Size 2 Input = 00,5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a Blind = 80513e77795feeec6d2c450589b0e1b178febd5c193a9fcba0d27f0a06e0 d50f,533c2e6d91c934f919ac218973be55ba0d7b234160a0d4cf3bddafbda99e2e0 c BlindedElement = 025529520d154b88dde799ad81b4bad43c10d2d983c866304b3 65de3062d5c16,68b7ead5133c421ac2052e384421b7d306fe698245e0bebe4d0058 bb7daf1b69 EvaluationElement = e27c872c0f0e04aa86927c28b42fb3181c312741296d6dc6 247b3152ea7bb81f,f07381baa4420ed5cf1bb4e52f3e1a32a9372b17161e11086d1 18b424f87a104 EvaluationProofC = fa1af76c86aaa73a4abb577f5a30ff9b8aced055120ae0390 b73f51d173c620a EvaluationProofS = 51ccd568a3494f627eee67660a44133706d67d88a9652aee1 02f999553214e06 Output = e694146179b874ff64f0c9ec59c292031e7d3386703d0ed129cfee98eec eeb184c0335c7c28be75f7298a33a48c05b2acbd36169a075e495f710c490b404ce3 0,aa5475f7d60613eab56bf317ea10340ed26be9cbea9685f2617f5a68d5509a485a 15d4db1b41c3ef0f68dd54cc3a4a53d92813797babb0683b71263f5e63b3f6 A.2. OPRF(decaf448, SHAKE-256) A.2.1. Base Mode seed = a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a 3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3 skSm = 78f2622804104209f7e015370ff98f4a3cbf311e6784e9f4944f8a252dc08 e916d9ab1a60dc905f0e56631903ecd4ae6e15291776d61460b A.2.1.1. Test Vector 1, Batch Size 1 Davidson, et al. Expires 7 January 2022 [Page 40] Internet-Draft OPRFs July 2021 Input = 00 Blind = d1080372f0fcf8c5eace50914e7127f576725f215cc7c111673c635ce668 bbbb9b50601ad89b358ab8c23ed0b6c9d040365ec9d060868714 BlindedElement = 984e0a443ee194090737df4afb402253f216b77650c91d252b6 638e1179723d51a4154b88eae396f1320f5df3c4b17f779516c456e364bd1 EvaluationElement = ec07794d109d5dd976bac4f23a4d041f4abd17017af78add 5dd87c66db44590131e23dd3e30310f43284b9e0b874041105eb8201ad584830 Output = e2d48872c64bd0e62cd6165c0a75399bbf6cecf39b85230c2748ccf7ebf 376d28394ac0b9518e1adb070c6952b5ab897e1cbce5f9d78ec8935de59f58210321 a A.2.1.2. Test Vector 2, Batch Size 1 Input = 5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a Blind = aed1ffa44fd8f0ed16373606a3cf7df589cca86d8ea1abbf5768771dbef3 d401c74ae55ba1e28b9565e1e4018eb261a14134a4ce60c1c718 BlindedElement = 4aa751f84b2634b73efa364b03e60b92b84f457576e6b369eea b76140e3859d10d2e98174f13f5a2c70670529ccf093d5f1aaf355b4f830b EvaluationElement = 429e9d382354f8079cc1e353ef431243cdfca5ec35eb662f 2214b96483e5e6392f15734dd56d65c0c1600d7fd685315831d11f3c33e7230d Output = b57a408fa6dafe00091e6f6b3d0086bc21ae9c4ead173987672e92f7116 2fea3970341cd63bc33ca442302474bbf95db41cd2b9fa0f2a607b6b4f57443a2f4b 5 A.2.2. Verifiable Mode seed = a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a 3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3 skSm = 9eb722f7fee9f61f24ad31bc42309f73648cf4393929e8f5f333fe10c6975 c827a1eba4e03ae2fa8735db2f63f6c98c7af6010e64c81f535 pkSm = b6e2751176d57836fe1dfbdbbdc78a1b5c5a52f831226c9d8dfdf5daf8f46 6e310e80978e9b81c387f5bc85cc7ef5567f4dd3ba7674579a2 A.2.2.1. Test Vector 1, Batch Size 1 Davidson, et al. Expires 7 January 2022 [Page 41] Internet-Draft OPRFs July 2021 Input = 00 Blind = 4c936db1779a621b6c71475ac3111fd5703a59b713929f36dfd1e892a7fe 814479c93d8b4b6e11d1f6fe5351e51457b665fa7b76074e531f BlindedElement = c0c9b0d321c4e7c8c13b910428196af3f36d5dae4796e2577fb 51493d3204cc1ee7732d81e0429195e4ad9226b84797feb261bfb2dbe48e9 EvaluationElement = a8f7614c46fb27a49f22fd3d3795d4f96667dfa075d967d7 3e32e9eb0e6705055dfc4446b20c8600cb1a6e636b9066217690c9ee9cd509c0 EvaluationProofC = 199a534bc888fb31dc08a1a1374c669ae61578ba7d51c0d40 f5169e35f95eda58fa7801d30593206b4df72de0680956dff2d8ded5b56e324 EvaluationProofS = 91370471e63326a97f0b2830c4caf95129ac603fd504496fc cb559c9109e079c49a504acbef4dd6e64ef2f429286f40ff00f4c6a7a57a107 Output = 31c251b66b1fafa46519252c9fc018dd117f219697f45e38bda7253d9cd 02d5a631600387c4863139ea79b3c036c706e70040d2148c43fa2fd47ea3d1d6f42e 5 A.2.2.2. Test Vector 2, Batch Size 1 Input = 5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a Blind = 15b3355179392f40c3d5a15f0d5ffc354e340454ec779f575e4573a3886a b5e57e4da2985cea9e32f6d95539ce2c7189e1bd7462e8c5483a BlindedElement = 3c05e826c9d885fd29bf537acc3bcc279c0821bd65cf21d9dcc 99a15af2474df8b3903f220cce9a9f7966a3991c37ae69a73deca4925ab58 EvaluationElement = ac1821113a6748a66c75ac71bedf2784402b60cbf9df16c3 cfc0ba1a240edfaa5ea5f35a5d5fa8221d60deeceb9dd14a6c4ed0ef01f2f2b4 EvaluationProofC = 2129b555a89ee00a826ae0080a71874a2b7612dfa3357c32f 3c1421cb0f93168eee21d72e0d279e772fed4724397463c4972ec8b09f50a2f EvaluationProofS = a1ec1562977cb52a458e26736e350ac02e09f709b81788f6b 944022c2313a1217134b9cc6232ac86d6b758d2b906ac5d9158a13e7221ec32 Output = e7956cc9410d6a906a0293172e816750cfc099d04db7af8a8970b3bb20d 73cbec56d61a969ff1db724b1701cbf63ad570b591a1fde2c7f409dee29457a6c5d8 c A.2.2.3. Test Vector 3, Batch Size 2 Davidson, et al. Expires 7 January 2022 [Page 42] Internet-Draft OPRFs July 2021 Input = 00,5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a Blind = 614bb578f29cc677ea9e7aea3e4839413997e020f9377b63c13584156a09 a46dd2a425c41eac0e313a47e99d05df72c6e1d58e6592577a0d,4c115060bca87db 7d73e00cbb8559f84cb7a221b235b0950a0ab553f03f10e1386abe954011b7da62bb 6599418ef90b5d4ea98cc28aff517 BlindedElement = e2f4aa0e9d09c39cc6f9f58fa4e99af814977f3033cfe613d7c e525ebf62b93970e4e32b99c1f8090b55d55fb9cb6180c864b5ea29342f98,6ec406 36ebae90b96df53d451c47a26231c7975ab0b3f2af61f8b6d6455662a08cdeb92ccb 6bc08d6c0a6662435f693f55c043bd4d366b01 EvaluationElement = 32f832dcf7d7d493c1c23c3cd94546aef8ffbc455ac16ebe c2d892d9e731581b41790879e735cb825574552af397a787b47593f095f5a40f,ea5 eee6f8206ceaa109b2c0fcf7807d3b585c751e1476ab140515972eac3a9a847b4858 871e4d92c69a7c8e32bcbaa2aa59d876f02b083b8 EvaluationProofC = 170d265464be75ee7e820f4b90b4f6ded3c379607b103eeb9 e04026f07eb89ae233169af78b32d79dfa40a7bbce0d16c6a3562345e44471f EvaluationProofS = ec007985eb27fa7931793801f3e060b272ac12610419ca411 52b24e7fab94e639cd85d95b9f6fa16ec32715fd4028f6441d4c5e06a0e2c3c Output = 31c251b66b1fafa46519252c9fc018dd117f219697f45e38bda7253d9cd 02d5a631600387c4863139ea79b3c036c706e70040d2148c43fa2fd47ea3d1d6f42e 5,e7956cc9410d6a906a0293172e816750cfc099d04db7af8a8970b3bb20d73cbec5 6d61a969ff1db724b1701cbf63ad570b591a1fde2c7f409dee29457a6c5d8c A.3. OPRF(P-256, SHA-256) A.3.1. Base Mode seed = a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a 3a3 skSm = a1b2355828f2c76de6749af9d093bd9fe0f2cada3ec653cd9a6d3126a7a78 27b A.3.1.1. Test Vector 1, Batch Size 1 Input = 00 Blind = 5d9e7f6efd3093c32ecceabd57fb03cf760c926d2a7bfa265babf29ec98a f0d0 BlindedElement = 03e3c379698da853d9844098fa0ac676970d5ec24167b598714 cd2ee188604ddd2 EvaluationElement = 03ea54e8d095332d1a601a3f8a5013188aea036bf9b56323 6f7fd3b046908b42fd Output = 464e3e51e4086a824d9a2f939524d7069ae4072a788bc9d5daa0762b258 26437 A.3.1.2. Test Vector 2, Batch Size 1 Davidson, et al. Expires 7 January 2022 [Page 43] Internet-Draft OPRFs July 2021 Input = 5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a Blind = 825155ab61f17605af2ae2e935c78d857c9407bcd45128d57d338f1671b5 fcbe BlindedElement = 030b40be181ffbb3c3ae4a4911287c43261f5e4034781def69c 51608f372a02102 EvaluationElement = 03115ad70ea55dbb4006da0ee3589a3582f31ef9cd143996 d1e31a25ad3abdcf6f Output = b597d58c843d0f9d2712121b0a3e2912ebee1c829eed3089eade9af4359 ab275 A.3.2. Verifiable Mode seed = a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a 3a3 skSm = 4e7804245a743c59d624457677294e04a8bc4bdcd94f0d3bd54f568067489 d34 pkSm = 03b51a0af95c819b09ee80c2056cf0ab0551a5355266d3a0aaff90c3fe915 ed892 A.3.2.1. Test Vector 1, Batch Size 1 Input = 00 Blind = cee64d86fd20ab4caa264a26c0e3d42fb773b3173ba76f9588c9b14779bd 8d91 BlindedElement = 03a734663e3eb29474c79996fe1d0662071594ed7a27832e214 9bad364e44784c5 EvaluationElement = 022ca51b981dd6bd5e08ad7f16ed0e08e67270fe2fc0df76 0be8f95019ffba50c6 EvaluationProofC = d7403f40351dc210d55b78ee34671b2f239faf264b5af8aec a3101ada4ff8643 EvaluationProofS = 6d7cb0e2697bf197578e6dde7abf09d31cf782260e471c930 e79acc6949df83e Output = 63e261480afa379117f23016997d6c8558262407d54c588881b74650a7c cdfd1 A.3.2.2. Test Vector 2, Batch Size 1 Davidson, et al. Expires 7 January 2022 [Page 44] Internet-Draft OPRFs July 2021 Input = 5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a Blind = 5c4b401063eff0bf242b4cd534a79bacfc2e715b2db1e7a3ad4ff8af1b24 daa2 BlindedElement = 03b6bc0a56d6ed8461a06605c1b293e768d418dc9c42b8851c1 a49292456dd1dad EvaluationElement = 0349529dc853a564345aa04a9512a088ad69c5064b1108f8 edfe914c5b74e03f58 EvaluationProofC = 88185c7c3a5fdebf24fc37c39925d745b4a286ec9234f32a3 dbf36c5b5261230 EvaluationProofS = aac945f48e297e4d70ed819688176030ffe370bfe2292a12c 4570b83ba7912a0 Output = 1232618e21b6c287ac80fcbe3fbc5013d6ec858a1529abf628514c0c19c 16570 A.3.2.3. Test Vector 3, Batch Size 2 Input = 00,5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a Blind = f0c7822ba317fb5e86028c44b92bd3aedcf6744d388ca013ef33edd36930 4eda,3b9631be9f8b274d9aaf671bfb6a775229bf435021b89c683259773bc686956 b BlindedElement = 02fbfb72be2e5df24abb1791489e3a77f9d30b28bafea7ba7c0 f2c31bbf3deb851,0357f017a6cb76f545233c96b806165b52fb7ab700708f817cf3 501b789f8d57fb EvaluationElement = 0350f7984730eb0a6fa95e795b68a13b3d461bf0c9bfa6e4 a33709b08f65ae528b,026061aa05c776aa08fd96c7eb284051f8a1303d989a1c8b5 e9a478e5c9f37207f EvaluationProofC = a6e08a019deaf2eba7f40162be527bb574db98679662bb97e 0db02d58638d0dc EvaluationProofS = 65dc2e6b64e172d8b7f6dac088737f4612a1ea455801eed6d 140554bed0903dd Output = 63e261480afa379117f23016997d6c8558262407d54c588881b74650a7c cdfd1,1232618e21b6c287ac80fcbe3fbc5013d6ec858a1529abf628514c0c19c165 70 A.4. OPRF(P-384, SHA-512) A.4.1. Base Mode seed = a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a 3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3 skSm = ef1b52c12cdf43dc260bf5425a30cde7d708ec34b38dcfbdc2946d7baf525 361e797f6a98f1ebd80f64865f21cde1c6d A.4.1.1. Test Vector 1, Batch Size 1 Davidson, et al. Expires 7 January 2022 [Page 45] Internet-Draft OPRFs July 2021 Input = 00 Blind = 359073c015b92d15450f7fb395bf52c6ea98384c491fe4e4d423b59de7b0 df382902c13bdc9993d3717bda68fc080b99 BlindedElement = 02fa3115c21ffcacc09ca470729b725781f84333e217cfeec2b 8ba6a54ce492ede7ead3714c5b177427ef853effb1b5c24 EvaluationElement = 020407d59b1497e23f6ff1af68631657dd31c418a8f5e3e9 4878e842ace8b72514f90f95909284069ca88b7728ba5fcdc8 Output = a1a1e468268164ad307b7bb5a92add28ed42117f5ca4dfd6e6534c56183 4ac65f394d0eb25489a22420d52c605931745a6683638b648d230b7599c7c78cb0b1 5 A.4.1.2. Test Vector 2, Batch Size 1 Input = 5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a Blind = 21ece4f9b6ffd01ce82082545413bd9bb5e8f3c63b86ae88d9ce0530b01c b1c23382c7ec9bdd6e75898e4877d8e2bc17 BlindedElement = 025fddc89a832089a59120df742acb34dba82b26afcae977961 57df238b5905c494a23c56b1f485cbbff78d31df7fa1492 EvaluationElement = 03ab50834f953a0b27afdad59cb18c6ffa3d95dfc265467b d7dfe96935b6cef735daa39f7a08853092f47323371695153d Output = b5ef8dbe81d0fd8bbcd104d5f729aaa1d8b7378ab0c6da84c1a13152891 ac71a069bc9654f7f6c3f9dfc6b9e5d47996e81d7679992300216afe9a759f737741 e A.4.2. Verifiable Mode seed = a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a 3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3 skSm = 67ee1c9e67566d87bfcca9e5dac4bfdb8bdd727c031133fac2aa9ba6c41e6 1e5f8fd401b5d76c7d54b15b15932797479 pkSm = 029b51b2ce9c499f2056e65e0f41d60960f9c4795c0cf94af273ce840c20b e4cdf87690b6b121b37d399b49afcc2ec9ac3 A.4.2.1. Test Vector 1, Batch Size 1 Davidson, et al. Expires 7 January 2022 [Page 46] Internet-Draft OPRFs July 2021 Input = 00 Blind = 102f6338df84c9602bfa9e7d690b1f7a173d07e6d54a419db4a6308f8b09 589e4283efb9cd1ee4061c6bf884e60a8774 BlindedElement = 03dacf29b7369164ab41eb0388a8258def9ff09933b3a2abed4 a400327810b0b5d940a4d4710473f61266a6d2b20e6786d EvaluationElement = 020b0ee924fc9a6f9b51894b3db9df3f2e1f29eb46f41a59 7aaa81942e1f6673f38c47db05924d08867cc7b45ffd5bfba0 EvaluationProofC = 79fe0dbfc6fd433b155f98fd4a019de4d7ffeef4bd6eb10a8 bf5a03602f20ef99ac2e05ca497f6276338b6f523bcf4b2 EvaluationProofS = 4ad2a121801039a9368f3aeb7011b553d18e7f4406c63ddfb 5799a9f53e3fc11c939b591ebc670a7297c66624d62ff49 Output = 8cf810d1e5750dffe92ad14749c007bbcfea47153eb49007edafd30201d deca63730db8acdec0ca7fd8db2a96775e3f17c7d41db40d469c1054ac0d3f709cf2 b A.4.2.2. Test Vector 2, Batch Size 1 Input = 5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a Blind = 8aec1d0c3d16afd032da7ba961449a56cec6fb918e932b06d5778ac7f67b ecfb3e3869237f74106241777f230582e84a BlindedElement = 027c6fc6f8ddf937b6c44183a39246ab26d0caf5ad7dd13e556 acbb997cd66295e66511a78df5e216a4d354bc7e909e027 EvaluationElement = 025b559f59b4e3417bf26956af2675c9e3f3cd5d97e1c507 8dc880e8bfb0858a34fb9ba9744b7d9d66effc3e8faf02371a EvaluationProofC = 144948b5d60dbf8b3cb15a5808e6cd35715db57e0c5e4e237 1a0d7b18bdea59e9e0e53dd9e618010544c5e33a52c6565 EvaluationProofS = f237c5f04902be869bd21b94118c58fe2d1aacb182bab2271 ea107afc9da3a97aadaac27022b46980ffd5ab828c54df5 Output = 2c7f0e808bd75781c1673bfa14de23347a0ef3a4c413312bc4368387ae3 bd6da250f726f1b5dcade0187f0ac378e54fdd3792e3a66ce9482c42631909e9de1d 8 A.4.2.3. Test Vector 3, Batch Size 2 Davidson, et al. Expires 7 January 2022 [Page 47] Internet-Draft OPRFs July 2021 Input = 00,5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a Blind = 41fabd4722d92472d858051ce9ad1a533176a862c697b2c392aff2aeb77e b20c2ae6ba52fe31e13e03bf1d9f39878b23,51171628f1d28bb7402ca4aea6465e2 67b7f977a1fb71593281099ef2625644aee0b6c5f5e6e01a2b052b3bd4caf539b BlindedElement = 030117571255e98fe43636c07b1d6a2e793563bf50644946144 7295678c707c4e9214d9805fcc3df35acfb29b775fab1f0,039e9c4a303efc469e20 00965c7a023dabc43f88caea4e8b47e3b737ee8fc30ba93480d29b9e1e3e59cedfa2 a5f4aeb9dd EvaluationElement = 032a382fdef3f63c6bd4fbdc26448773356880a1d7e16ec4 0f35374714e49cc725ea84e33b69e188f68fb782c558263ce0,02f88eaba928531d8 357e808cb7148c0de204d5d589a6bba770c4cfa448876a029aea214c3e0bb6a693a7 d88b001dbc098 EvaluationProofC = 0bc83100bf6b3ac8d8ad46f3973c107441edfa551f5622286 751698617f809713e749492e1310241bd0f66c657d74f8b EvaluationProofS = 09b2fc47495de88f2dbde5ea6f0abc24d750861b6a25adca3 a36e65ac1e0913a2f988e0684e520fd3b63be47e57914b4 Output = 8cf810d1e5750dffe92ad14749c007bbcfea47153eb49007edafd30201d deca63730db8acdec0ca7fd8db2a96775e3f17c7d41db40d469c1054ac0d3f709cf2 b,2c7f0e808bd75781c1673bfa14de23347a0ef3a4c413312bc4368387ae3bd6da25 0f726f1b5dcade0187f0ac378e54fdd3792e3a66ce9482c42631909e9de1d8 A.5. OPRF(P-521, SHA-512) A.5.1. Base Mode seed = a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a 3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a 3a3 skSm = 016ee706f30ce7e15e4ffa3114c7d59a7b6f302d531ca60419be39d1cd43e e13b1fc8398b7f63a900cdc49c6e99f65a74403db2fa739927a2ee288cff857d9d84 ecf A.5.1.1. Test Vector 1, Batch Size 1 Input = 00 Blind = 01b983705fcc9a39607288b935b0797ac6b3c4b2e848823ac9ae16b3a3b5 816be03432370deb7c3c17d9fc7cb4e0ce646e04e42d638e0fa7a434ed340772a8b5 d626 BlindedElement = 0301f0a8c68e58f5571bd39fe3b0b2aa055a8c34e3d68ba0d2e d177db0bc7575d477ed8f557596feb5ac568fe738eee8cff7dcb56dc78f52bf381c0 912e0e84b5a3f5b EvaluationElement = 0200babff80ca9060825acc2e53da599016aa4685f3c3f38 ad71dafe4200b26a588cd040fb56947c78929fc1bc56075bedbb363f28bcf65e33c6 fe7f938783a2dfa97e Output = da67996ac63b34db17ae15c98edd21565286d7549970f260c2f1360c62e 418c3695fa61e50c39df59be2e14376abb6732c07a627a7b49ac4615544e95b47afa c Davidson, et al. Expires 7 January 2022 [Page 48] Internet-Draft OPRFs July 2021 A.5.1.2. Test Vector 2, Batch Size 1 Input = 5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a Blind = 01a03b1096b0316bc8567c89bd70267d35c8ddcb2be2cdc867089a2eb5cf 471b1e6eb4b043b9644c8539857abe3a2022e9c9fd6a1695bbabe8add48bcd149ff3 b841 BlindedElement = 030099c35342a43221c6e03debfb17bad71b62e04c9242aa6e9 f2f915163ef4f5b8b7fe1740a4d636c36bd5c73ca39c69992dc7f6dff8f232125efc 22af4df8352fea2 EvaluationElement = 03017c756b73ddbaa80c2ee4ad61e431ac2494f80c258065 23c6be5cff2f544540d74263a4c93fb4e43e8411fc145448013c376d7ddb73f001cb c9c5529b693b0e1aa8 Output = 3d8405a1f73a8c2fb87bb1136499991fe0c4708b64767531385dc6db106 f09d47868860fbb47bc1ac6a466673bb52ef304cba124580109ea41b2734eb3cd14c 5 A.5.2. Verifiable Mode seed = a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a 3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a3a 3a3 skSm = 0017674057e06c5e3e8a331f2dc3558540701c9cd0f4c19126d5972af6a01 447b312d05a06dab3e9e07c891d749444c27ede0897ad42aea03b887eb5db93e3f29 a86 pkSm = 0201ee4e2eaa74728f577f4bb282c5440cd454fdee1d79b15a36d34b5e5a1 25e3ccc0f99e32cc0a6a15b5652a0c8a424860c6753f685d0e1e150ceba24ca3386f 29216 A.5.2.1. Test Vector 1, Batch Size 1 Davidson, et al. Expires 7 January 2022 [Page 49] Internet-Draft OPRFs July 2021 Input = 00 Blind = 00bbb82117c88bbd91b8954e16c0b9ceed3ce992b198be1ebfba9ba970db d75beefbfc6d056b7f7ba1ef79f4facbf2d912c26ce2ecc5bb8d66419b379952e96b d6f5 BlindedElement = 03017f6448132acb88e7b3c4324f9d9608e27a95dc9ac643915 a9e85618ed09b7072729237646da9a0d37a1169c148cb13041817ccf6e2eb37b512f f89d1850718ec50 EvaluationElement = 0300db733bf9d6441b04d9f650b3a572252200f84dc15d67 e75d6417479db3dc5c1f29cefc0e3578858ad3ec6037d3ea2f03b2d60ba5fe9f6aa4 b408ee128204bbb334 EvaluationProofC = 002097435da1befb7ad15ad2d25ad3e56b0eccbec5087d773 94039c2871a020dcf30deb4d95b5050f5febe1ebda4547870d46b1d3cef4dd04f793 e6016a23d180285 EvaluationProofS = 01976fbe0ce1922c14eef7ad402cb463d6f11ba2ae402a19e 4bc514c814b42d226175f76353c2b0bad26f98985e5f3b96a8e5557d78b7bc13eb8c 44cafb9f441772c Output = 64b90ccb524dc125290bda4f6102871a8580d9cb0dfe1c0e46ae87d70a1 690ddf7ed5d970ac3b51e959a8769fd8e5ee5a92ebf4e74db6104fc4334258b128d5 0 A.5.2.2. Test Vector 2, Batch Size 1 Input = 5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a Blind = 009055c99bf9591cb0eab2a72d044c05ca2cc2ef9b609a38546f74b6d688 f70cf205f782fa11a0d61b2f5a8a2a1143368327f3077c68a1545e9aafbba6a90dc0 d40a BlindedElement = 0201a8d0747e840cedd4586ca5382ef51031c9fb7074fcf6c9b 7acd6c74ee80dd33efa01f91cd3f50c9685fdea84c8a779cf8a3a6caedeb8050a782 241f8469d641d1a EvaluationElement = 0200470a42df4d40ddaebb7e4a3e308c09396e4f0217fb62 ffd1aad6f35449c41e655a0b073a82003b192685dc5567096a2ad690128dfdd62693 c97cd54e536b044ad5 EvaluationProofC = 01c01a155fd0c0e690f44cd2e4771b9c4cbc95d84e517f103 79b5e59e643c4c28b480b2a582e8dc03f1fb1f9dd26b73a7fbc9443c5cf543d288d4 3d078fe9db1f3a1 EvaluationProofS = 01bb2e45130b23cf6af1ac7777ac1c6189d0b3740c6fb1130 69bed943fd19d4093c6c1ffd872964189a02f5948d7f06d2090321510a46beabe6b6 19d84d4c23065f5 Output = 93d48a50859a56aabe4d19f4517eff37494959536381b8c072f7d968335 dae63d62b98b448160be9559c680a4bb2aee54acd8f26fd2ce6d6e7f714124a5c56b 5 A.5.2.3. Test Vector 3, Batch Size 2 Davidson, et al. Expires 7 January 2022 [Page 50] Internet-Draft OPRFs July 2021 Input = 00,5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a Blind = 01c6cf092d80c7cf2cb55388d899515238094c800bdd9c65f71780ba85f5 ae9b4703e17e559ca3ccd1944f9a70536c175f11a827452672b60d4e9f89eba28104 6e29,00cba1ba1a337759061965a423d9d3d6e1e1006dc8984ad28a4c93ecfc36fc2 171046b3c4284855cfa2434ed98db9e68a597db2c14728fade716a6a82d600444b26 e BlindedElement = 020043edd4cc7f6131931455923f988620f03077d89cfc51c65 bb2f026312352dd9ccb8df17184cf8e5b3a08cfd12e12beaecbabc82b2a8c3ecf16b e13ff4996b48e47,0300c958264a3308f411c69561ad13a61581c4d4ffecc3feff4c 0b5041b86a4a2b1b40b36a9d71ad5f0bde53514b06484fb0536dd601e42380580514 d9b7399249b406 EvaluationElement = 020011583e8c7d713ed23d2f6c2261923ef30a7534593b10 26511914b97f91a590cf50599901af6a86892abcd433b5073d869d7b330b9f4273d5 b0c614275cf0bf0c4e,02003ab9ffa4f5331b53a208999d1200b870683a53a065b3d e57bad18a02f206968854c1d5bb94e3a7f946e3f3a6313ef2b6a9327ab160d7d2637 8dd3a880a1f002f6f EvaluationProofC = 01dff218da0d67f76a979a4c3677a67d59a174e8e122f3d13 c0494611fe1c766d2ea08fee354ef3c7db3a6b3a3d7d75ea6a1f7e1deff35bccf27a 43ddf33ab1bf4aa EvaluationProofS = 00434d173267092e93912d2d2714a357bb570f3105fae0191 e33e19a5eb9bb1656f361c533770fc90dc7ecaec88d0e6855c525118a1f857e7abbf 46d6b159dc4f271 Output = 64b90ccb524dc125290bda4f6102871a8580d9cb0dfe1c0e46ae87d70a1 690ddf7ed5d970ac3b51e959a8769fd8e5ee5a92ebf4e74db6104fc4334258b128d5 0,93d48a50859a56aabe4d19f4517eff37494959536381b8c072f7d968335dae63d6 2b98b448160be9559c680a4bb2aee54acd8f26fd2ce6d6e7f714124a5c56b5 Authors' Addresses Alex Davidson Brave Software Email: alex.davidson92@gmail.com Armando Faz-Hernandez Cloudflare 101 Townsend St San Francisco, United States of America Email: armfazh@cloudflare.com Davidson, et al. Expires 7 January 2022 [Page 51] Internet-Draft OPRFs July 2021 Nick Sullivan Cloudflare 101 Townsend St San Francisco, United States of America Email: nick@cloudflare.com Christopher A. Wood Cloudflare 101 Townsend St San Francisco, United States of America Email: caw@heapingbits.net Davidson, et al. Expires 7 January 2022 [Page 52]