[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: (draft-sullivan-cfrg-voprf) 00 01 02 03 04

Network Working Group                                        A. Davidson
Internet-Draft                                               N. Sullivan
Intended status: Informational                                   C. Wood
Expires: January 14, 2021                                     Cloudflare
                                                           July 13, 2020


   Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups
                        draft-irtf-cfrg-voprf-04

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.

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."

   This Internet-Draft will expire on January 14, 2021.

Copyright Notice

   Copyright (c) 2020 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



Davidson, et al.        Expires January 14, 2021                [Page 1]


Internet-Draft                    OPRFs                        July 2020


   (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  . . . . . . . . . . . . . . . . . . . . . . .   3
     1.2.  Terminology . . . . . . . . . . . . . . . . . . . . . . .   5
     1.3.  Requirements  . . . . . . . . . . . . . . . . . . . . . .   5
   2.  Preliminaries . . . . . . . . . . . . . . . . . . . . . . . .   5
     2.1.  Prime-order group API . . . . . . . . . . . . . . . . . .   5
     2.2.  Other conventions . . . . . . . . . . . . . . . . . . . .   6
   3.  OPRF Protocol . . . . . . . . . . . . . . . . . . . . . . . .   7
     3.1.  Overview  . . . . . . . . . . . . . . . . . . . . . . . .   8
     3.2.  Context Setup . . . . . . . . . . . . . . . . . . . . . .   8
     3.3.  Data Structures . . . . . . . . . . . . . . . . . . . . .   9
     3.4.  Context APIs  . . . . . . . . . . . . . . . . . . . . . .  10
       3.4.1.  Server Context  . . . . . . . . . . . . . . . . . . .  10
       3.4.2.  VerifiableServerContext . . . . . . . . . . . . . . .  12
       3.4.3.  Client Context  . . . . . . . . . . . . . . . . . . .  16
       3.4.4.  VerifiableClientContext . . . . . . . . . . . . . . .  17
   4.  Ciphersuites  . . . . . . . . . . . . . . . . . . . . . . . .  19
     4.1.  OPRF(curve25519, SHA-512) . . . . . . . . . . . . . . . .  20
     4.2.  OPRF(curve448, SHA-512) . . . . . . . . . . . . . . . . .  20
     4.3.  OPRF(P-256, SHA-512)  . . . . . . . . . . . . . . . . . .  21
     4.4.  OPRF(P-384, SHA-512)  . . . . . . . . . . . . . . . . . .  22
     4.5.  OPRF(P-521, SHA-512)  . . . . . . . . . . . . . . . . . .  23
   5.  Security Considerations . . . . . . . . . . . . . . . . . . .  23
     5.1.  Security properties . . . . . . . . . . . . . . . . . . .  24
     5.2.  Cryptographic security  . . . . . . . . . . . . . . . . .  25
       5.2.1.  Computational hardness assumptions  . . . . . . . . .  25
       5.2.2.  Protocol security . . . . . . . . . . . . . . . . . .  25
       5.2.3.  Q-strong-DH oracle  . . . . . . . . . . . . . . . . .  26
       5.2.4.  Implications for ciphersuite choices  . . . . . . . .  27
     5.3.  Hashing to curve  . . . . . . . . . . . . . . . . . . . .  27
     5.4.  Timing Leaks  . . . . . . . . . . . . . . . . . . . . . .  27
     5.5.  Key rotation  . . . . . . . . . . . . . . . . . . . . . .  28
   6.  Additive blinding . . . . . . . . . . . . . . . . . . . . . .  28
     6.1.  Preprocess  . . . . . . . . . . . . . . . . . . . . . . .  29
     6.2.  Blind . . . . . . . . . . . . . . . . . . . . . . . . . .  29
     6.3.  Unblind . . . . . . . . . . . . . . . . . . . . . . . . .  30
       6.3.1.  Parameter Commitments . . . . . . . . . . . . . . . .  31
   7.  Contributors  . . . . . . . . . . . . . . . . . . . . . . . .  31



Davidson, et al.        Expires January 14, 2021                [Page 2]


Internet-Draft                    OPRFs                        July 2020


   8.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .  31
   9.  References  . . . . . . . . . . . . . . . . . . . . . . . . .  31
     9.1.  Normative References  . . . . . . . . . . . . . . . . . .  31
     9.2.  URIs  . . . . . . . . . . . . . . . . . . . . . . . . . .  34
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  34

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.  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 [OPAQUE].  The usage of a VOPRF is
   necessary in some applications, e.g., the Privacy Pass protocol
   [draft-davidson-pp-protocol], wherein this VOPRF is used to generate
   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-04 [1]:

   o  Introduce Client and Server contexts for controlling verifiability
      and required functionality.

   o  Condense API.



Davidson, et al.        Expires January 14, 2021                [Page 3]


Internet-Draft                    OPRFs                        July 2020


   o  Remove batching from standard functionality (included as an
      extension)

   o  Add Curve25519 and P-256 ciphersuites for applications that
      prevent strong-DH oracle attacks.

   o  Provide explicit prime-order group API and instantiation advice
      for each ciphersuite.

   o  Proof-of-concept implementation in sage.

   o  Remove privacy considerations advice as this depends on
      applications.

   draft-03 [2]:

   o  Certify public key during VerifiableFinalize

   o  Remove protocol integration advice

   o  Add text discussing how to perform domain separation

   o  Drop OPRF_/VOPRF_ prefix from algorithm names

   o  Make prime-order group assumption explicit

   o  Changes to algorithms accepting batched inputs

   o  Changes to construction of batched DLEQ proofs

   o  Updated ciphersuites to be consistent with hash-to-curve and added
      OPRF specific ciphersuites

   draft-02 [3]:

   o  Added section discussing cryptographic security and static DH
      oracles

   o  Updated batched proof algorithms

   draft-01 [4]:

   o  Updated ciphersuites to be in line with
      https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-04

   o  Made some necessary modular reductions more explicit





Davidson, et al.        Expires January 14, 2021                [Page 4]


Internet-Draft                    OPRFs                        July 2020


1.2.  Terminology

   The following terms are used throughout this document.

   o  PRF: Pseudorandom Function.

   o  OPRF: Oblivious Pseudorandom Function.

   o  VOPRF: Verifiable Oblivious Pseudorandom Function.

   o  Client: Protocol initiator.  Learns pseudorandom function
      evaluation as the output of the protocol.

   o  Server: Computes the pseudorandom function over a secret key.
      Learns nothing about the client's input.

   o  NIZK: Non-interactive zero knowledge.

   o  DLEQ: Discrete Logarithm Equality.

1.3.  Requirements

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].

2.  Preliminaries

2.1.  Prime-order group API

   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", it 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".  Any element "A" holds the equality "p*A=I".
   The set of scalars corresponds to "GF(p)".





Davidson, et al.        Expires January 14, 2021                [Page 5]


Internet-Draft                    OPRFs                        July 2020


   We now detail a number of member functions that can be invoked on a
   prime-order group.

   o  Order(): Outputs the order of the group (i.e. "p").

   o  Generator(): Outputs a fixed generator "G" for the group.

   o  Identity(): Outputs the identity element of the group (i.e.  "I").

   o  Serialize(A): A member function of "GG" that maps a group element
      "A" to a unique byte array "buf".

   o  Deserialize(buf): A member function of "GG" that maps a byte array
      "buf" to a group element "A".

   o  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.  Examples of
      hash to group functions satisfying this property are described for
      prime-order (sub)groups of elliptic curves, see
      [I-D.irtf-cfrg-hash-to-curve].

   o  HashToScalar(x): A member function of "GG" that deterministically
      maps an array of bytes "x" to a random element in GF(p).

   o  RandomScalar(): A member function of "GG" that generates a random,
      non-zero element in GF(p).

   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] 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 implementer.
   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 implementation of this
   interface for specific definitions of elliptic curves.

2.2.  Other conventions

   o  We use the notation "x <-$ Q" to denote sampling "x" from the
      uniform distribution over the set "Q".





Davidson, et al.        Expires January 14, 2021                [Page 6]


Internet-Draft                    OPRFs                        July 2020


   o  For any object "x", we write "len(x)" to denote its length in
      bytes.

   o  For two byte arrays "x" and "y", write "x || y" to denote their
      concatenation.

   o  We assume that all numbers are stored in big-endian orientation.

   o  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.

   All algorithm descriptions are written in a Python-like pseudocode.
   We use the "ABORT()" function for presentational clarity to denote
   the process of terminating the algorithm or returning an error
   accordingly.  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 a boolean "true" if "a" and "b" are equal, and
   "false" otherwise.

3.  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:

             +----------+-------+---+----------------+------+
             | Mode     | Value |   |                |      |
             +----------+-------+---+----------------+------+
             | modeBase | 0x00  |   | modeVerifiable | 0x01 |
             +----------+-------+---+----------------+------+






Davidson, et al.        Expires January 14, 2021                [Page 7]


Internet-Draft                    OPRFs                        July 2020


3.1.  Overview

   Both participants agree on the mode and a choice of ciphersuite that
   is used before the protocol exchange.  Once established, the core
   protocol runs to compute "output = F(skS, input)" as follows:

      Client(pkS, input, info)                 Server(skS, pkS)
     ----------------------------------------------------------
       token, blindToken = Blind(input)

                            blindToken
                           ---------->

                            evaluation = Evaluate(skS, pkS, blindToken)

                            evaluation
                           <----------

       issuedToken = Unblind(pkS, token, blindToken, evaluation)
       output = Finalize(input, issuedToken, info)

   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 "Unblind" the client unblinds the server
   response (and verifies the server's proof if verifiability is
   required).  In "Finalize", the client outputs a byte array
   corresponding to its input.

   Note that in the final output, the client computes Finalize over some
   auxiliary input data "info".  This parameter SHOULD be used for
   domain separation in the (V)OPRF protocol.  Specifically, any system
   which has multiple (V)OPRF applications should use separate auxiliary
   values to to ensure finalized outputs are separate.  Guidance for
   constructing info can be found in [I-D.irtf-cfrg-hash-to-curve];
   Section 3.1.

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 base mode setup functions for
   creating client and server contexts are below:









Davidson, et al.        Expires January 14, 2021                [Page 8]


Internet-Draft                    OPRFs                        July 2020


   def SetupBaseserver(suite):
     (skS, _) = KeyGen(GG)
     contextString = I2OSP(modeBase, 1) + I2OSP(suite.ID, 2)
     return ServerContext(contextString, skS)

   def SetupBaseClient(suite):
     contextString = I2OSP(modeBase, 1) + I2OSP(suite.ID, 2)
     return ClientContext(contextString)

   The "KeyGen" function used above takes a group "GG" and generates a
   private and public key pair (skX, pkX), where skX is a random, non-
   zero element in the scalar field "GG" and pkX is the product of skX
   and the group's fixed generator.

   The verifiable mode setup functions for creating client and server
   contexts are below.

   def SetupVerifiableserver(suite):
     (skS, pkS) = KeyGen(GG)
     contextString = I2OSP(modeVerifiable, 1) + I2OSP(suite.ID, 2)
     return VerifiableServerContext(contextString, skS), pkS

   def SetupVerifiableClient(suite, pkS):
     contextString = I2OSP(modeVerifiable, 1) + I2OSP(suite.ID, 2)
     return VerifiableClientContext(contextString, pkS)

   For verifiable modes, servers MUST make the resulting public key
   "pkS" accessible for clients.  (Indeed, it is a required parameter
   when configuring a verifiable client context.)

   Each setup function takes a ciphersuite from the list defined in
   Section 4.  Each ciphersuite has two-byte identifier, referred to as
   "suite.ID" in the pseudocode above, that identifies the suite.
   Section 4 lists these ciphersuite identifiers.

3.3.  Data Structures

   The following is a list of data structures that are defined for
   providing inputs and outputs for each of the context interfaces
   defined in Section 3.4.

   The following types are a list of aliases that are used throughout
   the protocol.

   A "ClientInput" is a byte array.

   opaque ClientInput<1..2^16-1>;




Davidson, et al.        Expires January 14, 2021                [Page 9]


Internet-Draft                    OPRFs                        July 2020


   A "SerializedElement" is also a byte array, representing the unique
   serialization of an "Element".

   opaque SerializedElement<1..2^16-1>;

   A "Token" is an object created by a client when constructing a
   (V)OPRF protocol input.  It is stored so that it can be used after
   receiving the server response.

   struct {
     opaque data<1..2^16-1>;
     Scalar blind<1..2^16-1>;
   } Token;

   An "Evaluation" is the type output by the "Evaluate" algorithm.  The
   member "proof" is added only in verifiable contexts.

   struct {
     SerializedElement element;
     Scalar proof<0...2^16-1>; /* only for modeVerifiable */
   } Evaluation;

   Evaluations may also be combined in batches with a constant-size
   proof, producing a "BatchedEvaluation".  These carry a list of
   "SerializedElement" values and proof.  These evaluation types are
   only useful in verifiable contexts which carry proofs.

   struct {
     SerializedElement elements<1..2^16-1>;
     Scalar proof<0...2^16-1>; /* only for modeVerifiable */
   } BatchedEvaluation;

3.4.  Context APIs

   In this section, we detail the APIs available on the client and
   server OPRF contexts.  This document uses the types "Element" and
   "Scalar" to denote elements of the group "GG" and its underlying
   scalar field, respectively.  For notational clarity, "PublicKey" and
   "PrivateKey" are items of type "Element" and "Scalar", respectively.

3.4.1.  Server Context

   The ServerContext encapsulates the context string constructed during
   setup and the OPRF key pair.  It has two functions, "Evaluate" and
   "VerifyFinalize", described below.  "Evaluate" takes as input
   serialized representations of blinded group elements from the client.
   "VerifyFinalize" takes ClientInput values and their corresponding
   output digests from "Verify" and returns true if the inputs match the



Davidson, et al.        Expires January 14, 2021               [Page 10]


Internet-Draft                    OPRFs                        July 2020


   outputs.  Note that "VerifyFinalize" is not used in the main OPRF
   protocol.  It is exposed as an API for building higher-level
   protocols.

3.4.1.1.  Evaluate

   Input:

     PrivateKey skS
     PublicKey pkS
     SerializedElement blindedToken

   Output:

     Evaluation Ev

   def Evaluate(skS, pkS, blindedToken):
     BT = GG.Deserialize(blindedToken)
     Z = skS * BT
     serializedElement = GG.Serialize(Z)

     Ev = Evaluation{ element: serializedElement }

     return Ev

3.4.1.2.  VerifyFinalize

























Davidson, et al.        Expires January 14, 2021               [Page 11]


Internet-Draft                    OPRFs                        July 2020


   Input:

     PrivateKey skS
     PublicKey pkS
     ClientInput input
     opaque info<1..2^16-1>
     opaque output<1..2^16-1>

   Output:

     boolean valid

   def VerifyFinalize(skS, pkS, input, info, output):
     T = GG.HashToGroup(input)
     element = GG.Serialize(T)
     issuedElement = Evaluate(skS, pkS, [element])
     E = GG.Serialize(issuedElement)

     finalizeDST = "RFCXXXX-Finalize-" + client.contextString
     hashInput = len(input) || input ||
                 len(E) || E ||
                 len(info) || info ||
                 len(finalizeDST) || finalizeDST
     digest = Hash(hashInput)

     return CT_EQUAL(digest, output)

3.4.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 "ComputeComposites" and "GenerateProof", described below.

3.4.2.1.  Evaluate
















Davidson, et al.        Expires January 14, 2021               [Page 12]


Internet-Draft                    OPRFs                        July 2020


   Input:

     PrivateKey skS
     PublicKey pkS
     SerializedElement blindedToken

   Output:

     Evaluation Ev

   def Evaluate(skS, pkS, blindedToken):
     BT = GG.Deserialize(blindedToken)
     Z = skS * BT
     serializedElement = GG.Serialize(Z)

     proof = GenerateProof(skS, pkS, blindedToken, serializedElement)
     Ev = Evaluation{ element: serializedElement, proof: proof }

     return Ev

   The helper functions "GenerateProof" and "ComputeComposites" are
   defined below.

3.4.2.2.  GenerateProof



























Davidson, et al.        Expires January 14, 2021               [Page 13]


Internet-Draft                    OPRFs                        July 2020


   Input:

     PrivateKey skS
     PublicKey pkS
     SerializedElement blindedToken
     SerializedElement element

   Output:

     Scalar proof[2]

   def GenerateProof(skS, pkS, blindedToken, element)
     G = GG.Generator()
     gen = GG.Serialize(G)

     blindTokenList = [blindedToken]
     elementList = [element]

     (a1, a2) = ComputeComposites(gen, pkS, blindTokenList, elementList)

     M = GG.Deserialize(a1)
     r = GG.RandomScalar()
     a3 = GG.Serialize(r * G)
     a4 = GG.Serialize(r * M)

     challengeDST = "RFCXXXX-challenge-" + self.contextString
     h2Input = I2OSP(len(gen), 2) || gen ||
               I2OSP(len(pkS), 2) || pkS ||
               I2OSP(len(a1), 2) || a1 || I2OSP(len(a2), 2) || a2 ||
               I2OSP(len(a3), 2) || a3 || I2OSP(len(a4), 2) || a4 ||
               I2OSP(len(challengeDST), 2) || challengeDST

     c = GG.HashToScalar(h2Input)
     s = (r - c * skS) mod p

     return (c, s)

3.4.2.2.1.  Batching inputs

   Unlike other functions, "ComputeComposites" takes lists of inputs,
   rather than a single input.  It is optimized to produce a constant-
   size output.  This functionality lets applications batch inputs
   together to produce a constant-size proofs from "GenerateProof".
   Applications can take advantage of this functionality by invoking
   "GenerateProof" on batches of inputs.  (Notice that in the pseudocode
   above, the single inputs "blindedToken" and "element" are translated
   into lists before invoking "ComputeComposites".  A batched




Davidson, et al.        Expires January 14, 2021               [Page 14]


Internet-Draft                    OPRFs                        July 2020


   "GenerateProof" variant would permit lists of inputs, and no list
   translation would be needed.)

   Note that using batched inputs creates a "BatchedEvaluation" object
   as the output of "Evaluate".

3.4.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.4.2.3.  ComputeComposites

   Input:

     SerializedElement gen
     PublicKey pkS
     SerializedElement blindedTokens[m]
     SerializedElement elements[m]

   Output:

     SerializedElement composites[2]

   def ComputeComposites(gen, pkS, blindedTokens, elements):
     seedDST = "RFCXXXX-seed-" + self.contextString
     compositeDST = "RFCXXXX-composite-" + self.contextString
     h1Input = I2OSP(len(gen), 2) || gen ||
               I2OSP(len(pkS), 2) || pkS ||
               I2OSP(len(blindedTokens), 2) || blindedTokens ||
               I2OSP(len(elements), 2) || elements ||
               I2OSP(len(seedDST), 2) || seedDST

     seed = Hash(h1Input)
     M = GG.Identity()
     Z = GG.Identity()
     for i = 0 to m:
       h2Input = I2OSP(len(seed), 2) || seed || I2OSP(i, 2) ||
                 I2OSP(len(compositeDST), 2) || compositeDST
       di = GG.HashToScalar(h2Input)
       Mi = GG.Deserialize(blindedTokens[i])
       Zi = GG.Deserialize(elements[i])
       M = di * Mi + M
       Z = di * Zi + Z
    return [GG.Serialize(M), GG.Serialize(Z)]




Davidson, et al.        Expires January 14, 2021               [Page 15]


Internet-Draft                    OPRFs                        July 2020


3.4.3.  Client Context

   The ClientContext encapsulates the context string constructed during
   setup.  It has three functions, "Blind()", "Unblind()", and
   "Finalize()", as described below.

3.4.3.1.  Blind

   We note here that the blinding mechanism that we use can be modified
   slightly with the opportunity for making performance gains in some
   scenarios.  We detail these modifications in Section 6.

   Input:

     ClientInput input

   Output:

     Token token
     SerializedElement blindedToken

   def Blind(input):
     r = GG.RandomScalar()
     P = GG.HashToGroup(input)
     blindedToken = GG.Serialize(r * P)

     token = Token{ data: input, blind: r }

     return (token, blindedToken)

3.4.3.2.  Unblind




















Davidson, et al.        Expires January 14, 2021               [Page 16]


Internet-Draft                    OPRFs                        July 2020


   Input:

     PublicKey pkS
     Token token
     SerializedElement blindedToken
     Evaluation Ev

   Output:

     SerializedElement unblindedToken

   def Unblind(pkS, token, blindedToken, Ev):
     r = token.blind
     Z = GG.Deserialize(Ev.element)
     N = (r^(-1)) * Z

     unblindedToken = GG.Serialize(N)

     return unblindedToken

3.4.3.3.  Finalize

   Input:

     Token T
     SerializedElement E
     opaque info<1..2^16-1>

   Output:

     opaque output<1..2^16-1>

   def Finalize(T, E, info):
     finalizeDST = "RFCXXXX-Finalize-" + self.contextString
     hashInput = len(T.data) || T.data ||
                 len(E) || E ||
                 len(info) || info ||
                 len(finalizeDST) || finalizeDST
     return Hash(hashInput)

3.4.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.




Davidson, et al.        Expires January 14, 2021               [Page 17]


Internet-Draft                    OPRFs                        July 2020


3.4.4.1.  VerifyProof

   This algorithm outputs a boolean "verified" which indicates whether
   the proof inside of the evaluation verifies correctly, or not.

   Input:

     PublicKey pkS
     SerializedElement blindedToken
     Evaluation Ev

   Output:

     boolean verified

   def VerifyProof(pkS, blindedToken, Ev):
     G = GG.Generator()
     gen = GG.Serialize(G)

     blindTokenList = [blindedToken]
     elementList = [Ev.element]

     (a1, a2) = ComputeComposites(gen, pkS, blindTokenList, elementList)

     A' = (Ev.proof[1] * G + Ev.proof[0] * pkS)
     B' = (Ev.proof[1] * M + Ev.proof[0] * Z)
     a3 = GG.Serialize(A')
     a4 = GG.Serialize(B')

     challengeDST = "RFCXXXX-challenge-" + self.contextString
     h2Input = I2OSP(len(gen), 2) || gen ||
               I2OSP(len(pkS), 2) || pkS ||
               I2OSP(len(a1), 2) || a1 ||
               I2OSP(len(a2), 2) || a2 ||
               I2OSP(len(a3), 2) || a3 ||
               I2OSP(len(a4), 2) || a4 ||
               I2OSP(len(challengeDST), 2) || challengeDST

     c  = GG.HashToScalar(h2Input)

     return CT_EQUAL(c, Ev.proof[0])

3.4.4.2.  Unblind








Davidson, et al.        Expires January 14, 2021               [Page 18]


Internet-Draft                    OPRFs                        July 2020


   Input:

     PublicKey pkS
     Token token
     SerializedElement blindedToken
     Evaluation Ev

   Output:

     SerializedElement unblindedToken

   def Unblind(pkS, token, blindedToken, Ev):
     if VerifyProof(pkS, blindedToken, Ev) == false:
       ABORT()

     r = token.blind
     Z = GG.Deserialize(Ev.element)
     N = (r^(-1)) * Z

     unblindedToken = GG.Serialize(N)

     return unblindedToken

4.  Ciphersuites

   A ciphersuite 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.

   o  "GG": A prime-order group exposing the API detailed in
      Section 2.1.

   o  "Hash": A cryptographic hash function that is indifferentiable
      from a Random Oracle.

   This section specifies supported VOPRF group and hash function
   instantiations.  For each group, we specify the HashToGroup and
   Serialize functionalities.  The Deserialize functionality is the
   inverse of the corresponding Serialize functionality.

   We only provide ciphersuites in the elliptic curve setting as these
   provide the most efficient way of instantiating the OPRF.

   Applications should take caution in using ciphersuites targeting
   P-256 and curve25519.  See Section 5.2 for related discussion.




Davidson, et al.        Expires January 14, 2021               [Page 19]


Internet-Draft                    OPRFs                        July 2020


   [[OPEN ISSUE: Replace Curve25519 and Curve448 with Ristretto/Decaf]]

4.1.  OPRF(curve25519, SHA-512)

   o  Group:

      *  Elliptic curve: curve25519 [RFC7748]

      *  Generator(): Return the point with the following affine
         coordinates:

         +  x = "09"

         +  y = "5F51E65E475F794B1FE122D388B72EB36DC2B28192839E4DD6163A5
            D81312C14"

      *  HashToGroup(): curve25519_XMD:SHA-512_ELL2_RO_
         [I-D.irtf-cfrg-hash-to-curve] with DST "RFCXXXX-
         curve25519_XMD:SHA-512_ELL2_RO_"

      *  Serialization: The standard 32-byte representation of the
         public key [RFC7748]

      *  Order(): Returns "1000000000000000000000000000000014DEF9DEA2F79
         CD65812631A5CF5D3ED"

      *  Addition: Adding curve points directly corresponds to the group
         addition operation.

      *  Deserialization: Implementers must check for each untrusted
         input point whether it's a member of the big prime-order
         subgroup of the curve.  This can be done by scalar multiplying
         the point by Order() and checking whether it's zero.

   o  Hash: SHA-512

   o  ID: 0x0001

4.2.  OPRF(curve448, SHA-512)

   o  Group:

      *  Elliptic curve: curve448 [RFC7748]

      *  Generator(): Return the point with the following affine
         coordinates:

         +  x = "05"



Davidson, et al.        Expires January 14, 2021               [Page 20]


Internet-Draft                    OPRFs                        July 2020


         +  y = "7D235D1295F5B1F66C98AB6E58326FCECBAE5D34F55545D060F75DC
            28DF3F6EDB8027E2346430D211312C4B150677AF76FD7223D457B5B1A"

      *  HashToGroup(): curve448_XMD:SHA-512_ELL2_RO_
         [I-D.irtf-cfrg-hash-to-curve] with DST "RFCXXXX-
         curve448_XMD:SHA-512_ELL2_RO_"

      *  Serialization: The standard 56-byte representation of the
         public key [RFC7748]

      *  Order(): Returns "3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
         FFFFFFFFFFF7CCA23E9C44EDB49AED63690216CC2728DC58F552378C292AB58
         44F3"

      *  Addition: Adding curve points directly corresponds to the group
         addition operation.

      *  Deserialization: Implementers must check for each untrusted
         input point whether it's a member of the big prime-order
         subgroup of the curve.  This can be done by scalar multiplying
         the point by Order() and checking whether it's zero.

   o  Hash: SHA-512

   o  ID: 0x0002

4.3.  OPRF(P-256, SHA-512)

   o  Group:

      *  Elliptic curve: P-256 (secp256r1) [x9.62]

      *  Generator(): Return the point with the following affine
         coordinates:

         +  x = "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A1394
            5D898C296"

         +  y = "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406
            837BF51F5"

      *  HashToGroup(): P256_XMD:SHA-256_SSWU_RO_
         [I-D.irtf-cfrg-hash-to-curve] with DST "RFCXXXX-P256_XMD:SHA-
         256_SSWU_RO_"

      *  Serialization: The compressed point encoding for the curve
         [SEC1] consisting of 33 bytes.




Davidson, et al.        Expires January 14, 2021               [Page 21]


Internet-Draft                    OPRFs                        July 2020


      *  Order(): Returns "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179
         E84F3B9CAC2FC632551"

      *  Addition: Adding curve points directly corresponds to the group
         addition operation.

      *  Scalar multiplication: Scalar multiplication of curve points
         directly corresponds with scalar multiplication in the group.

   o  Hash: SHA-512

   o  ID: 0x0003

4.4.  OPRF(P-384, SHA-512)

   o  Group:

      *  Elliptic curve: P-384 (secp384r1) [x9.62]

      *  Generator(): Return the point with the following affine
         coordinates:

         +  x = "AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E
            082542A385502F25DBF55296C3A545E3872760AB7"

         +  y = "3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA311
            3B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F"

      *  HashToGroup(): P384_XMD:SHA-512_SSWU_RO_
         [I-D.irtf-cfrg-hash-to-curve] with DST "RFCXXXX-P384_XMD:SHA-
         512_SSWU_RO_"

      *  Serialization: The compressed point encoding for the curve
         [SEC1] consisting of 49 bytes.

      *  Order(): Returns "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
         FFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973"

      *  Addition: Adding curve points directly corresponds to the group
         addition operation.

      *  Scalar multiplication: Scalar multiplication of curve points
         directly corresponds with scalar multiplication in the group.

   o  Hash: SHA-512

   o  ID: 0x0004




Davidson, et al.        Expires January 14, 2021               [Page 22]


Internet-Draft                    OPRFs                        July 2020


4.5.  OPRF(P-521, SHA-512)

   o  Group:

      *  Elliptic curve: P-521 (secp521r1) [x9.62]

      *  Generator(): Return the point with the following affine
         coordinates:

         +  x = "00C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F82
            8AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429
            BF97E7E31C2E5BD66"

         +  y = "011839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817A
            FBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24
            088BE94769FD16650"

      *  HashToGroup(): P521_XMD:SHA-512_SSWU_RO_
         [I-D.irtf-cfrg-hash-to-curve] with DST "RFCXXXX-P521_XMD:SHA-
         512_SSWU_RO_"

      *  Serialization: The compressed point encoding for the curve
         [SEC1] consisting of 67 bytes.

      *  Order(): Returns "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
         FFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B88
         99C47AEBB6FB71E91386409"

      *  Addition: Adding curve points directly corresponds to the group
         addition operation.

      *  Scalar multiplication: Scalar multiplication of curve points
         directly corresponds with scalar multiplication in the group.

   o  Hash: SHA-512

   o  ID: 0x0005

5.  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.








Davidson, et al.        Expires January 14, 2021               [Page 23]


Internet-Draft                    OPRFs                        July 2020


5.1.  Security properties

   The security properties of an OPRF protocol with functionality y =
   F(k, x) include those of a standard PRF.  Specifically:

   o  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:

   o  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:

   o  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.




Davidson, et al.        Expires January 14, 2021               [Page 24]


Internet-Draft                    OPRFs                        July 2020


5.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.

5.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 FFp be the
   finite field of order p.

5.2.1.1.  Discrete-log (DL) problem

   Given G, a generator of GG, and H = hG for some h in FFp; output h.

5.2.1.2.  Decisional Diffie-Hellman (DDH) problem

   Sample a uniformly random bit d in {0,1}. Given (G, aG, bG, C),
   where:

   o  G is a generator of GG;

   o  a,b are elements of FFp;

   o  if d == 0: C = abG; else: C is sampled uniformly GG(sp).

   Output d' == d.

5.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.




Davidson, et al.        Expires January 14, 2021               [Page 25]


Internet-Draft                    OPRFs                        July 2020


    Given:
    - G, k * G, G_1, ... , G_N where G, G_1, ... G_N are 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 5.1 under the OMDH assumption in the universal
   composability (UC) security model.

5.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 FFp

   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) bits.

   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) =
   20 bits.

   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 submit Q queries to the OPRF can use the aforementioned



Davidson, et al.        Expires January 14, 2021               [Page 26]


Internet-Draft                    OPRFs                        July 2020


   attacks to reduce security of the group instantiation by log_2(Q)
   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.

5.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) bits of security.

   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 cannot tolerate discrete logarithm security of
   lower than 128 bits, we recommend only implementing ciphersuites with
   IDs: 0x0002, 0x0004, and 0x0005.

5.3.  Hashing to curve

   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 in 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.

5.4.  Timing Leaks

   To ensure no information is leaked during protocol execution, all
   operations that use secret data MUST be constant time.  Operations
   that SHOULD be constant time include all prime-order group operations
   and proof-specific operations ("GenerateProof()" and
   "VerifyProof()").




Davidson, et al.        Expires January 14, 2021               [Page 27]


Internet-Draft                    OPRFs                        July 2020


5.5.  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 5.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.  Additive blinding

   Let "H" refer to the function "GG.HashToGroup", in Section 2.1 we
   assume that the client-side blinding is carried out directly on the
   output of "H(x)", i.e. computing "r * H(x)" for some "r <-$ GF(p)".
   In the [OPAQUE] document, it is noted that it may be more efficient
   to use additive blinding (rather than multiplicative) if the client
   can preprocess some values.  For example, a valid way of computing
   additive blinding would be to instead compute "H(x) + (r * G)", where
   "G" is the fixed generator for the group "GG".

   The advantage of additive blinding is that it allows the client to
   pre-process tables of blinded scalar multiplications for "G".  This
   may give it 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.
   Choosing one of these values "r * G" (where "r" is the scalar value
   that is used), then computing "H(x) + (r * G)" is more efficient than
   computing "r * H(x)".  Therefore, it may be advantageous to define
   the OPRF and VOPRF protocols using additive blinding (rather than
   multiplicative) blinding.  In fact, the only algorithms that need to
   change are Blind and Unblind (and similarly for the VOPRF variants).

   We define the variants of the algorithms in Section 3.4 for
   performing additive blinding below, along with a new algorithm
   "Preprocess".  The "Preprocess" algorithm can take place offline and
   before the rest of the OPRF protocol.  The Blind algorithm takes the
   preprocessed values as inputs, but the signature of Unblind remains
   the same.








Davidson, et al.        Expires January 14, 2021               [Page 28]


Internet-Draft                    OPRFs                        July 2020


6.1.  Preprocess

   struct {
     Scalar blind;
     SerializedElement blindedGenerator;
     SerializedElement blindedPublicKey;
   } PreprocessedBlind;

   Input:

     PublicKey pkS

   Output:

     PrepocessedBlind preproc

   def Preprocess(pkS):
     PK = GG.Deserialize(pkS)
     r = GG.RandomScalar()
     blindedGenerator = GG.Serialize(r * GG.Generator())
     blindedPublicKey = GG.Serialize(r * PK)

     preproc = PrepocessedBlind{
       blind: r,
       blindedGenerator: blindedGenerator,
       blindedPublicKey: blindedPublicKey,
     }

     return preproc

6.2.  Blind




















Davidson, et al.        Expires January 14, 2021               [Page 29]


Internet-Draft                    OPRFs                        July 2020


   Input:

     ClientInput input
     PreprocessedBlind preproc

   Output:

     Token token
     SerializedElement blindedToken

   def Blind(input, preproc):
     Q = GG.Deserialize(preproc.blindedGenerator) /* Q = r * G */
     P = GG.HashToGroup(input)

     token = Token{
       data: input,
       blind: preproc.blindedPublicKey
     }
     blindedToken = GG.Serialize(P + Q)           /* P + r * G */

     return (token, blindedToken)

6.3.  Unblind

   Input:

     Token token
     Evaluation ev
     SerializedElement blindedToken

   Output:

    SerializedElement unblinded

   def Unblind(token, ev, blindedToken):
     PKR = GG.Deserialize(token.blind)
     Z = GG.Deserialize(ev.element)
     N := Z - PKR

     unblindedToken = GG.Serialize(N)

     return unblindedToken

   Let "P = GG.HashToGroup(x)".  Notice that Unblind computes:

   Z - PKR = k * (P + r * G) - r * pkS
           = k * P + k * (r * G) - r * (k * G)
           = k * P



Davidson, et al.        Expires January 14, 2021               [Page 30]


Internet-Draft                    OPRFs                        July 2020


   by the commutativity of scalar multiplication in GG.  This is the
   same output as in the "Unblind" algorithm for multiplicative
   blinding.

   Note that the verifiable variant of "Unblind" works as above but
   includes the step to "VerifyProof", as specified in Section 3.4.4.

6.3.1.  Parameter Commitments

   For some applications, it may be desirable for server to bind tokens
   to certain parameters, e.g., protocol versions, ciphersuites, etc.
   To accomplish this, server should use a distinct scalar for each
   parameter combination.  Upon redemption of a token T from the client,
   server can later verify that T was generated using the scalar
   associated with the corresponding parameters.

7.  Contributors

   o  Alex Davidson (alex.davidson92@gmail.com)

   o  Nick Sullivan (nick@cloudflare.com)

   o  Chris Wood (caw@heapingbits.net)

   o  Eli-Shaoul Khedouri (eli@intuitionmachines.com)

   o  Armando Faz Hernandez (armfazh@cloudflare.com)

8.  Acknowledgements

   This document resulted from the work of the Privacy Pass team
   [PrivacyPass].  The authors would also like to acknowledge the
   helpful conversations with Hugo Krawczyk.  Eli-Shaoul Khedouri
   provided additional review and comments on key consistency.

9.  References

9.1.  Normative References

   [BB04]     "Short Signatures Without Random Oracles",
              <http://ai.stanford.edu/~xb/eurocrypt04a/bbsigs.pdf>.

   [BG04]     "The Static Diffie-Hellman Problem",
              <https://eprint.iacr.org/2004/306>.







Davidson, et al.        Expires January 14, 2021               [Page 31]


Internet-Draft                    OPRFs                        July 2020


   [ChaumBlindSignature]
              "Blind Signatures for Untraceable Payments",
              <http://sceweb.sce.uhcl.edu/yang/teaching/
              csci5234WebSecurityFall2011/Chaum-blind-signatures.PDF>.

   [ChaumPedersen]
              "Wallet Databases with Observers",
              <https://chaum.com/publications/Wallet_Databases.pdf>.

   [Cheon06]  "Security Analysis of the Strong Diffie-Hellman Problem",
              <https://www.iacr.org/archive/
              eurocrypt2006/40040001/40040001.pdf>.

   [DECAF]    "Decaf, Eliminating cofactors through point compression",
              <https://www.shiftleft.org/papers/decaf/decaf.pdf>.

   [DGSTV18]  "Privacy Pass, Bypassing Internet Challenges Anonymously",
              <https://www.degruyter.com/view/j/popets.2018.2018.issue-
              3/popets-2018-0026/popets-2018-0026.xml>.

   [draft-davidson-pp-protocol]
              Davidson, A., "Privacy Pass: The Protocol", n.d.,
              <https://tools.ietf.org/html/draft-davidson-pp-protocol-
              00>.

   [I-D.irtf-cfrg-hash-to-curve]
              Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R., and
              C. Wood, "Hashing to Elliptic Curves", draft-irtf-cfrg-
              hash-to-curve-09 (work in progress), June 2020.

   [JKK14]    "Round-Optimal Password-Protected Secret Sharing and
              T-PAKE in the Password-Only model",
              <https://eprint.iacr.org/2014/650>.

   [JKKX16]   "Highly-Efficient and Composable Password-Protected Secret
              Sharing (Or, How to Protect Your Bitcoin Wallet Online)",
              <https://eprint.iacr.org/2016/144>.

   [JKKX17]   "TOPPSS: Cost-minimal Password-Protected Secret Sharing
              based on Threshold OPRF",
              <https://eprint.iacr.org/2017/363>.

   [keytrans]
              "Security Through Transparency",
              <https://security.googleblog.com/2017/01/security-through-
              transparency.html>.





Davidson, et al.        Expires January 14, 2021               [Page 32]


Internet-Draft                    OPRFs                        July 2020


   [NIST]     "Keylength - NIST Report on Cryptographic Key Length and
              Cryptoperiod (2016)", <https://www.keylength.com/en/4/>.

   [OPAQUE]   "The OPAQUE Asymmetric PAKE Protocol",
              <https://tools.ietf.org/html/draft-krawczyk-cfrg-opaque-
              02>.

   [PrivacyPass]
              "Privacy Pass",
              <https://github.com/privacypass/challenge-bypass-server>.

   [RFC2104]  Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-
              Hashing for Message Authentication", RFC 2104,
              DOI 10.17487/RFC2104, February 1997,
              <https://www.rfc-editor.org/info/rfc2104>.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/info/rfc2119>.

   [RFC5869]  Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand
              Key Derivation Function (HKDF)", RFC 5869,
              DOI 10.17487/RFC5869, May 2010,
              <https://www.rfc-editor.org/info/rfc5869>.

   [RFC7748]  Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
              for Security", RFC 7748, DOI 10.17487/RFC7748, January
              2016, <https://www.rfc-editor.org/info/rfc7748>.

   [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,
              <https://www.rfc-editor.org/info/rfc8017>.

   [RISTRETTO]
              "The ristretto255 Group", <https://tools.ietf.org/html/
              draft-hdevalence-cfrg-ristretto-01>.

   [SEC1]     Standards for Efficient Cryptography Group (SECG), ., "SEC
              1: Elliptic Curve Cryptography",
              <https://www.secg.org/sec1-v2.pdff>.

   [SEC2]     Standards for Efficient Cryptography Group (SECG), ., "SEC
              2: Recommended Elliptic Curve Domain Parameters",
              <http://www.secg.org/sec2-v2.pdf>.





Davidson, et al.        Expires January 14, 2021               [Page 33]


Internet-Draft                    OPRFs                        July 2020


   [SHAKE]    "SHA-3 Standard, Permutation-Based Hash and Extendable-
              Output Functions", <https://www.nist.gov/publications/sha-
              3-standard-permutation-based-hash-and-extendable-output-
              functions?pub_id=919061>.

   [SJKS17]   "SPHINX, A Password Store that Perfectly Hides from
              Itself", <https://eprint.iacr.org/2018/695>.

   [x9.62]    ANSI, "Public Key Cryptography for the Financial Services
              Industry: the Elliptic Curve Digital Signature Algorithm
              (ECDSA)", ANSI X9.62-1998, September 1998.

9.2.  URIs

   [1] https://tools.ietf.org/html/draft-irtf-cfrg-voprf-04

   [2] https://tools.ietf.org/html/draft-irtf-cfrg-voprf-03

   [3] https://tools.ietf.org/html/draft-irtf-cfrg-voprf-02

   [4] https://tools.ietf.org/html/draft-irtf-cfrg-voprf-01

Authors' Addresses

   Alex Davidson
   Cloudflare
   County Hall
   London, SE1 7GP
   United Kingdom

   Email: alex.davidson92@gmail.com


   Nick Sullivan
   Cloudflare
   101 Townsend St
   San Francisco
   United States of America

   Email: nick@cloudflare.com











Davidson, et al.        Expires January 14, 2021               [Page 34]


Internet-Draft                    OPRFs                        July 2020


   Christopher A. Wood
   Cloudflare
   101 Townsend St
   San Francisco
   United States of America

   Email: caw@heapingbits.net












































Davidson, et al.        Expires January 14, 2021               [Page 35]


Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/