Skip to main content

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

The information below is for an old version of the document.
Document Type
This is an older version of an Internet-Draft that was ultimately published as RFC 9497.
Authors Alex Davidson , Nick Sullivan , Christopher A. Wood
Last updated 2019-11-04 (Latest revision 2019-07-24)
Replaces draft-sullivan-cfrg-voprf
RFC stream Internet Research Task Force (IRTF)
Formats
IETF conflict review conflict-review-irtf-cfrg-voprf, conflict-review-irtf-cfrg-voprf, conflict-review-irtf-cfrg-voprf, conflict-review-irtf-cfrg-voprf, conflict-review-irtf-cfrg-voprf, conflict-review-irtf-cfrg-voprf
Additional resources Mailing list discussion
Stream IRTF state Active RG Document
Consensus boilerplate Unknown
Document shepherd (None)
IESG IESG state Became RFC 9497 (Informational)
Telechat date (None)
Responsible AD (None)
Send notices to (None)
draft-irtf-cfrg-voprf-02
Davidson, et al.           Expires May 7, 2020                 [Page 20]
Internet-Draft                    OPRFs                    November 2019

4.8.2.  Evaluation phase

   The evaluation phase of the OPRF results in a client receiving
   pseudorandom function evaluations from the server.  It is important
   that the client is able to link the computation that it performs in
   the first step, with the output that it receives from the server.  In
   other words, the client must store the data (r,M) output by
   OPRF_Blind(x).  When it receives Z from the server, it must then use
   (r,M) as inputs to OPRF_Blind.

   In the batched setting, the client stores multiple values (ri,Mi) and
   sends each Mi to the server.  Both client and server should preserve
   this ordering throughout the evaluation phase so that the client can
   successfully finalize the output in the final step.

4.8.3.  Additional requirements

   The client input to the OPRF evaluation phase is a set of bytes x.
   These bytes are RECOMMENDED to be uniformly distributed.  If the
   bytes are sampled from a predictable distribution instead, then it is
   likely that the server will also be able to predict the client's
   input to the OPRF.  Therefore client privacy is reduced.

   Protocols that embed an OPRF evaluation MUST specify exactly how
   group elements are encoded in messages.

   The server need not not preserve any information during the
   evaluation exchange.  For efficiency and client-privacy reasons, we
   recommend that all data received from the client in the evaluation
   phase is destroyed after the server has responded.

   In the VOPRF setting, when the server sends the response, it needs to
   indicate which version of key that it has used.  This enables the
   client to retrieve the correct commitment from the public registry.
   The server MUST include a key identifier as part of its response, to
   ensure that the client can verify the contents of D correctly.

5.  NIZK Discrete Logarithm Equality Proof

   For the VOPRF protocol we require that V is able to verify that P has
   used its private key k to evaluate the PRF.  We can do this by
   showing that the original commitment (G,Y) output by VOPRF_Setup(l)
   satisfies log_G(Y) == log_M(Z) where Z is the output of
   VOPRF_Eval(k,G,Y,M).

   This may be used, for example, to ensure that P uses the same private
   key for computing the VOPRF output and does not attempt to "tag"

Davidson, et al.           Expires May 7, 2020                 [Page 21]
Internet-Draft                    OPRFs                    November 2019

   individual verifiers with select keys.  This proof must not reveal
   the P's long-term private key to V.

   Consequently, this allows extending the OPRF protocol with a (non-
   interactive) discrete logarithm equality (DLEQ) algorithm built on a
   Chaum-Pedersen [ChaumPedersen] proof.  This proof is divided into two
   procedures: DLEQ_Generate and DLEQ_Verify.  These are specified
   below.

5.1.  DLEQ_Generate

   Input:

    k: Evaluator secret key.
    G: Public fixed generator of GG.
    Y: Evaluator public key (= kG).
    M: An element in GG.
    Z: An element in GG.
    H_3: A hash function from GG to {0,1}^L, modeled as a random oracle.

   Output:

    D: DLEQ proof (c, s).

   Steps:

    1. r <-$ GF(p)
    2. A := rG and B := rM
    3. c <- H_3(G,Y,M,Z,A,B) (mod p)
    4. s := (r - ck) (mod p)
    5. Output D := (c, s)

   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 the
   key k in a similar fashion as is possible in Schnorr or (EC)DSA
   scenarios where fresh randomness is not used.

5.2.  DLEQ_Verify

Davidson, et al.           Expires May 7, 2020                 [Page 22]
Internet-Draft                    OPRFs                    November 2019

   Input:

    G: Public fixed generator of GG.
    Y: Evaluator public key.
    M: An element in GG.
    Z: An element in GG.
    D: DLEQ proof (c, s).

   Output:

    True if log_G(Y) == log_M(Z), False otherwise.

   Steps:

    1. A' := (sG + cY)
    2. B' := (sM + cZ)
    3. c' <- H_3(G,Y,M,Z,A',B') (mod p)
    4. Output c == c' (mod p)

5.3.  Batched VOPRF evaluation

   Common applications (e.g.  [PrivacyPass]) require V to obtain
   multiple PRF evaluations from P.  In the VOPRF case, this would also
   require generation and verification of a DLEQ proof for each Zi
   received by V.  This is costly, both in terms of computation and
   communication.  To get around this, applications use a 'batching'
   procedure for generating and verifying DLEQ proofs for a finite
   number of PRF evaluation pairs (Mi,Zi).  For n PRF evaluations:

   o  Proof generation is slightly more expensive from 2n modular
      exponentiations to 2n+2.

   o  Proof verification is much more efficient, from 4n modular
      exponentiations to 2n+4.

   o  Communications falls from 2n to 2 group elements.

   Therefore, since P is usually a powerful server, we can tolerate a
   slight increase in proof generation complexity for much more
   efficient communication and proof verification.

   In this section, we describe algorithms for batching the DLEQ
   generation and verification procedure.  For these algorithms we
   require an additional random oracle H_5: {0,1}^a x ZZ^3 -> {0,1}^b
   that takes an inputs of a binary string of length a and three integer
   values, and outputs an element in {0,1}^b.

Davidson, et al.           Expires May 7, 2020                 [Page 23]
Internet-Draft                    OPRFs                    November 2019

   We can instantiate the random oracle function H_4 using the same hash
   function that is used for H_1,H_2,H_3.  For H_5, we can also use a
   similar instantiation, or we can use a variable-length output
   generator.  For example, for groups with an order of 256-bit, valid
   instantiations include functions such as SHAKE-256 [SHAKE] or HKDF-
   Expand-SHA256 [RFC5869].

5.3.1.  Batched_DLEQ_Generate

Input:

 k: Evaluator secret key.
 G: Public fixed generator of group GG.
 Y: Evaluator public key (= kG).
 n: Number of PRF evaluations.
 [ Mi ]: An array of points in GG of length n.
 [ Zi ]: An array of points in GG of length n.
 H_4: A hash function from GG^(2n+2) to {0,1}^a, modeled as a random oracle.
 H_5: A hash function from {0,1}^a x ZZ^2 to {0,1}^b, modeled as a random oracle.
 label: An integer label value for the splitting the domain of H_5

Output:

 D: DLEQ proof (c, s).

Steps:

 1. seed <- H_4(G,Y,[Mi,Zi]))
 2. for i in [n]: di <- H_5(seed,i,label)
 3. c1,...,cn := (int)d1,...,(int)dn
 4. M := c1M1 + ... + cnMn
 5. Z := c1Z1 + ... + cnZn
 6. Output D <- DLEQ_Generate(k,G,Y,M,Z)

5.3.2.  DLEQ_Batched_Verify

Davidson, et al.           Expires May 7, 2020                 [Page 24]
Internet-Draft                    OPRFs                    November 2019

 Input:

  G: Public fixed generator of group GG.
  Y: Evaluator public key.
  [ Mi ]: An array of points in GG of length n.
  [ Zi ]: An array of points in GG of length n.
  D: DLEQ proof (c, s).

 Output:

  True if log_G(Y) == log_(Mi)(Zi) for each i in 1...n, False otherwise.

 Steps:

  1. seed <- H_4(G,Y,[Mi,Zi]))
  2. i' := i
  3. for i in [n]:
     1. di <- H_5(seed,i',info)
     2. if di > p:
        1. i' = i'+1
        2. i = i-1 // decrement and try again
        3. continue
  4. c1,...,cn := (int)d1,...,(int)dn
  5. M := c1M1 + ... + cnMn
  6. Z := c1Z1 + ... + cnZn
  7. Output DLEQ_Verify(G,Y,M,Z,D)

5.3.3.  Modified protocol execution

   The VOPRF protocol from Section Section 4 changes to allow specifying
   multiple blinded PRF inputs [ Mi ] for i in 1...n.  P computes the
   array [ Zi ] and replaces DLEQ_Generate with DLEQ_Batched_Generate
   over these arrays.  The same applies to the algorithm VOPRF_Eval.
   The same applies for replacing DLEQ_Verify with DLEQ_Batched_Verify
   when V verifies the response from P and during the algorithm
   VOPRF_Unblind.

5.3.4.  Random oracle instantiations for proofs

   We can instantiate the random oracle function H_4 using the same hash
   function that is used for H_1,H_2,H_3.  For H_5, we can also use a
   similar instantiation, or we can use a variable-length output
   generator.  For example, for groups with an order of 256-bit, valid
   instantiations include functions such as SHAKE-256 [SHAKE] or HKDF-
   Expand-SHA256 [RFC5869].

Davidson, et al.           Expires May 7, 2020                 [Page 25]
Internet-Draft                    OPRFs                    November 2019

   Input:

    [ ri ]: Random scalars in [1, p - 1].
    G: Public fixed generator of group GG.
    Y: Evaluator public key.
    [ Mi ]: Blinded elements of GG.
    [ Zi ]: Server-generated elements in GG.
    D: A batched DLEQ proof object.

   Output:

    N: element in GG, or "error".

   Steps:

    1. N := (r^(-1))Z
    2. If 1 = DLEQ_Batched_Verify(G,Y,[ Mi ],[ Zi ],D), output N
    3. Output "error"

6.  Supported ciphersuites

   This section specifies supported VOPRF group and hash function
   instantiations.  We only provide ciphersuites in the EC setting as
   these provide the most efficient way of instantiating the OPRF.  Our
   instantiation includes considerations for providing the DLEQ proofs
   that make the instantiation a VOPRF.  Supporting OPRF operations
   alone can be allowed by simply dropping the relevant components.  For
   reasons that are detailed in Section 8.1, we only consider
   ciphersuites that provide strictly greater than 128 bits of security
   [NIST].

6.1.  VOPRF-curve448-HKDF-SHA512-ELL2:

   o  GG: curve448 [RFC7748]

   o  H_1: curve448-SHA512-ELL2-RO [I-D.irtf-cfrg-hash-to-curve]

      *  label: voprf_h2c

   o  H_2: HMAC_SHA512 [RFC2104]

   o  H_3: SHA512

   o  H_4: SHA512

   o  H_5: HKDF-Expand-SHA512

Davidson, et al.           Expires May 7, 2020                 [Page 26]
Internet-Draft                    OPRFs                    November 2019

6.2.  VOPRF-p384-HKDF-SHA512-ICART:

   o  GG: secp384r1 [SEC2]

   o  H_1: P384-SHA512-ICART-RO [I-D.irtf-cfrg-hash-to-curve]

      *  label: voprf_h2c

   o  H_2: HMAC_SHA512 [RFC2104]

   o  H_3: SHA512

   o  H_4: SHA512

   o  H_5: HKDF-Expand-SHA512

6.3.  VOPRF-p521-HKDF-SHA512-SSWU:

   o  GG: secp521r1 [SEC2]

   o  H_1: P521-SHA512-SSWU-RO [I-D.irtf-cfrg-hash-to-curve]

      *  label: voprf_h2c

   o  H_2: HMAC_SHA512 [RFC2104]

   o  H_3: SHA512

   o  H_4: SHA512

   o  H_5: HKDF-Expand-SHA512

   We remark that the 'label' field is necessary for domain separation
   of the hash-to-curve functionality.

7.  Recommended protocol integration

   We describe some recommendations and suggestions on the topic of
   integrating the (V)OPRF protocol from Section 4 into wider protocols.
   It should be noted that since [JKK14] provides a security proof of
   the VPRF construction in the UC security model, then any UC-secure
   protocol that uses the OPRF construction as an atomic instantiation
   will remain UC-secure.

   As a result we recommend that any protocol that wishes to include an
   OPRF stage does so by implementing all OPRF evaluation functionality
   as a contiguous block of operations during the protocol.  This does
   not include the OPRF setup phase, which should be run before the

Davidson, et al.           Expires May 7, 2020                 [Page 27]
Internet-Draft                    OPRFs                    November 2019

   entire protocol interaction.  For example, such an instantiation for
   a wider protocol W would look like the following.

       ================================================================
                              OPRF setup phase
       ================================================================

       > ...
       > BEGIN(protocol W)
       > ...
       > PAUSE(protocol W)

       ================================================================
                            OPRF evaluation phase
       ================================================================

       > RESTART(protocol W)
       > ...
       > END(protocol W)

   In other words, no messages from protocol W should take place during
   the OPRF protocol instantiation.  This DOES NOT preclude the
   participants in protocol W from using the outputs of the OPRF
   evaluation, once the OPRF protocol is complete.  Note that the OPRF
   protocol can involve batched evaluations, as well as single
   evaluations.

7.1.  Setup phase

   In the VOPRF setting, the server must send to the client (p,Y) where
   p is the prime used in instantiating the group used for the VOPRF
   operations, and Y is a commitment to the server key k.  From this
   information, the client and server must agree on a generator G for
   the group description.  It is important that the generator G of GG is
   not chosen by the server, and that it is agreed upon before the
   protocol starts.  In the elliptic curve setting, we recommend that G
   is chosen as the standard generator for the curve.

   As we mentioned above, if an implementer wants to embed OPRF
   evaluation as part of a wider protocol, then we recommend that this
   setup phase should occur before all communication takes place;
   including all communication required for the wider protocol.  We
   recommend that any server implementation only implements one group
   instantiation at any one time.  This means that the client does not
   have to pick a specific instantiation when it sends the first
   evaluation message.

Davidson, et al.           Expires May 7, 2020                 [Page 28]
Internet-Draft                    OPRFs                    November 2019

7.2.  Evaluation phase

   The evaluation phase of the OPRF results in a client receiving
   pseudorandom function evaluations from the server.  It is important
   that the client is able to link the computation that it performs in
   the first step, with the output that it receives from the server.  In
   other words, the client must store the data (r,M) output by
   OPRF_Blind(x).  When it receives Z from the server, it must then use
   (r,M) as inputs to OPRF_Blind.

   In the batched setting, the client stores multiple values (ri,Mi) and
   sends each Mi to the server.  Both client and server should preserve
   this ordering throughout the evaluation phase so that the client can
   successfully finalize the output in the final step.

7.3.  Client-specific considerations

7.3.1.  Inputs

   The client input to the OPRF evaluation phase is a set of bytes x.
   These bytes do not have to be uniformly distributed.  However, we
   should note that if the bytes are sampled from a predictable
   distribution, then it is likely that the server will also be able to
   predict the client's input to the OPRF.  Therefore the utility of
   client privacy is reduced somewhat.

7.3.2.  Output

   The client receives y = H_2(DST, x .. N) at the end of the protocol.
   We suggest that clients store the pair (x, y) as bytes.  This allows
   the client to use the the output of the protocol in conjunction with
   the input used to create it later.

7.3.3.  Messages

   The client message contains a group element and should be encoded as
   bytes.  In the elliptic curve setting this corresponds to an encoded
   curve point.  Both compressed and uncompressed point encodings should
   be supported by the server.  The length of the point encoding should
   be enough to determine the encoding of the point.

7.4.  Server-specific considerations

7.4.1.  Setup

   As mentioned previously, the server should pick a single group
   instantiation and advertise this as the only way of evaluating the
   OPRF.

Davidson, et al.           Expires May 7, 2020                 [Page 29]
Internet-Draft                    OPRFs                    November 2019

7.4.2.  Inputs

   The server input to the evaluation phase is a key k.  This key can be
   stored simply as bytes.  The key must be protected at all times.  If
   the server ever suspects that the key has been compromised then it
   must be rotated immediately.  In addition, the key should be rotated
   somewhat frequently for security reasons to reduce the impact of an
   unknown compromise.  For more information on appropriate key
   schedules, see Section 8.5.

   Every time the server key is rotated, a new setup phase will have to
   be run.  The server should publish public key commitments (Y) to a
   public, trusted registry to avoid notifying all client's
   individually.  The registry should be considered tamper-proof from
   the client perspective and should retain a history of all edits.  We
   recommend that all commitments come with an expiry date to enforce
   rotation policies, and optionally a signature using a long-term
   signing key (with public verification key made available via another
   public beacon).  The signature is only necessary to prevent active
   attackers that may be able to route the client to an untrusted
   registry.

   Below, we recommend the following proposed JSON structure for holding
   public commitment data.

   {
     "Y": <bytes_of_commitment>,
     "expiry": <date-of-expiry>,
     "sig": <commitment_signature>
   }

   This data should be retrieved and validated by the client when
   verifying VOPRF messages from the server.  For efficiency reasons,
   the client may want to cache the value of "Y" and "expiry".  Any
   commitment that has expired should not be used by the client.

   Each commitment should be versioned according to some obvious
   convention.  After a key rotation the server should append a new
   commitment object with a new version tag.

7.4.3.  Outputs

   The server need not not preserve any information during the
   evaluation exchange.  For efficiency and client-privacy reasons, we
   recommend that all data received from the client in the evaluation
   phase is destroyed after the server has responded.

Davidson, et al.           Expires May 7, 2020                 [Page 30]
Internet-Draft                    OPRFs                    November 2019

7.4.4.  Messages

   In the VOPRF setting, when the server sends the response, it needs to
   indicate which version of key that it has used.  This enables the
   client to retrieve the correct commitment from the public registry.
   We recommend that the server sends it's response as a JSON object
   that specifies separate members for the values Z and D, along with
   the key version that is used.

8.  Security Considerations

   This section discusses the cryptographic security of our protocol,
   along with some suggestions and trade-offs that arise from the
   implementation of the implementation of an OPRF.

8.1.  Cryptographic security

   We discuss the cryptographic security of the OPRF protocol from
   Section 4, relative to the necessary cryptographic assumptions that
   need to be made.

8.1.1.  Computational hardness assumptions

   Each assumption states that the problems specified below are
   computationally difficult to solve in relation to sp (the security
   parameter).  In other words, the probability that an adversary has in
   solving the problem is bounded by a function negl(sp), where negl(sp)
   < 1/f(sp) for all polynomial functions f().

   Let GG = GG(sp) be a group with prime-order p, and let FFp be the
   finite field of order p.

8.1.1.1.  Discrete-log (DL) problem

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

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

Davidson, et al.           Expires May 7, 2020                 [Page 31]
Internet-Draft                    OPRFs                    November 2019

8.1.2.  Protocol security

   As aforementioned, our OPRF and VOPRF constructions are based heavily
   on the 2HashDH-NIZK construction given in [JKK14], except for
   considerations on how we instantiate the NIZK DLEQ proof system.
   This means that the cryptographic security of our construction is
   also 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, kG, G_1, ... , G_N where G, G1, ... GN are elements of the group 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}, kG_{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 3.1 under the OMDH assumption in the universal
   composability (UC) security model.  Without the NIZK proof system,
   the protocol instantiates an OPRF protocol only.  See the paper for
   further details.

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

Davidson, et al.           Expires May 7, 2020                 [Page 32]
Internet-Draft                    OPRFs                    November 2019

   As an example, suppose that a group instantiation is used that
   provides 128 bits of security.  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, kG, (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
   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.

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

   While 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.  Therefore, all of our ciphersuites
   in Section 6 come with a minimum group instantiation corresponding to
   196 bits of security.  This would require an adversary to launch a
   minimum of Q = 2^(68) queries to reduce security to 128 bits using
   the Q-sDH attacks.  As a result, it appears prohibitively expensive
   to launch credible attacks on these parameters with our current
   understanding of the attack surface.

8.2.  Hashing to curve

   A critical aspect of implementing this protocol using elliptic curve
   group instantiations is a method of instantiating the function H1,
   that maps inputs to group elements.  In the elliptic curve setting,
   this must be a deterministic function that maps arbitrary inputs x
   (as bytes) to uniformly chosen points in the curve.

   In the security proof of the construction H1 is modeled as a random
   oracle.  This implies that any instantiation of H1 must be pre-image
   and collision resistant.  In Section 6 we give instantiations of this
   functionality based on the functions described in

Davidson, et al.           Expires May 7, 2020                 [Page 33]
Internet-Draft                    OPRFs                    November 2019

   [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 H1.

8.3.  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: H_1() (hashing arbitrary
   strings to curves) and DLEQ_Generate().  As mentioned previously,
   [I-D.irtf-cfrg-hash-to-curve] describes various algorithms for
   constant-time implementations of H_1.

8.4.  User segregation

   The aim of the OPRF functionality is to allow clients receive
   pseudorandom function evaluations on their own inputs, without
   compromising their own privacy with respect to the server.  In many
   applications (for example, [PrivacyPass]) the client may choose to
   reveal their original input, after an invocation of the OPRF
   protocol, along with their OPRF output.  This can prove to the server
   that it has received a valid OPRF output in the past.  Since the
   server does not reveal learn anything about the OPRF output, it
   should not be able to link the client to any previous protocol
   instantiation.

   Consider a malicious server that manages to segregate the user base
   into different sets.  Then this reduces the effective privacy of all
   of the clients involved, since the client above belongs to a smaller
   set of users than previously hoped.  In general, if the user-base of
   the OPRF functionality is quite small, then the obliviousness of
   clients is limited.  That is, smaller user-bases mean that the server
   is able to identify client's with higher certainty.

   In summary, an OPRF instantiation effectively comes with an
   additional privacy parameter pp.  If all clients of the OPRF make one
   query and then subsequently reveal their OPRF input afterwards, then
   the server should be link the revealed input to a protocol
   instantiation with probability 1/pp.

   Below, we provide a few techniques that could be used to abuse
   client-privacy in the OPRF construction by segregating the user-base,
   along with some mitigations.

Davidson, et al.           Expires May 7, 2020                 [Page 34]
Internet-Draft                    OPRFs                    November 2019

8.4.1.  Linkage patterns

   If the server is able to ascertain patterns of usage for some clients
   - such as timings associated with usage - then the effective privacy
   of the clients is reduced to the number of users that fit each usage
   pattern.  Along with early registration patterns, where early
   adopters initially have less privacy due to a low number of
   registered users, such problems are inherent to any anonymity-
   preserving system.

8.4.2.  Evaluation on multiple keys

   Such an attack consists of the server evaluating the OPRF on multiple
   different keys related to the number of clients that use the
   functionality.  As an extreme, the server could evaluate the OPRF
   with a different key for each client.  If the client then revealed
   their hidden information at a later date then the server would
   immediately know which initial request they launched.

   The VOPRF variant helps mitigate this attack since each server
   evaluation can be bound to a known public key.  However, there are
   still ways that the VOPRF construction can be abused.  In particular:

   o  If the server successfully provisions a large number of keys that
      are trusted by clients, then the server can divide the user-base
      by the number of keys that are currently in use.  As such, clients
      should only trust a small number (2 or 3 ideally) of server keys
      at any one time.  Additionally, a tamper-proof audit log system
      akin to existing work on Key Transparency [keytrans] could be used
      to ensure that a server is abiding by the key policy.  This would
      force the server to be held accountable for their key updates, and
      thus higher key update frequencies can be better managed on the
      client-side.

   o  If the server rotates their key frequently, then this may result
      in client's holding out-of-date information from a past
      interaction.  Such information can also be used to segregate the
      user-base based on the last time that they accessed the OPRF
      protocol.  Similarly to the above, server key rotations must be
      kept to relatively infrequent intervals (such as once per month).
      This will prevent too many clients from being segregated into
      different groups related to the time that they accessed the
      functionality.  There are viable reasons for rotating the server
      key (for protecting against malicious clients) that we address
      more closely in Section 8.5.

   Since key provisioning requires careful handling, all public keys
   should be accessible from a client-trusted registry with a way of

Davidson, et al.           Expires May 7, 2020                 [Page 35]
Internet-Draft                    OPRFs                    November 2019

   auditing the history of key updates.  We also recommend that public
   keys have a corresponding expiry date that clients can use to prevent
   the server from using keys that have been provisioned for a long
   period of time.

8.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 instance, if the
   key is kept in production for a long period of time, then this may
   grant the client the ability to hoard large numbers of tokens.  This
   has negative impacts for some of the applications that we consider in
   Section 9.  As another 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 8.1.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.

   As we discussed in Section 8.4.2, key rotation cycles that are too
   frequent (in the order of days) can lead to large segregation of the
   wider user base.  As such, the length of the key cycles represent a
   trade-off between greater server key security (for shorter cycles),
   and better client privacy (for longer cycles).  In situations where
   client privacy is paramount, longer key cycles should be employed.
   Otherwise, shorter key cycles can be managed if the server uses a Key
   Transparency-type system [keytrans]; this allows clients to publicly
   audit their rotations.

9.  Applications

   This section describes various applications of the (V)OPRF protocol.

9.1.  Privacy Pass

   This VOPRF protocol is used by the Privacy Pass system [PrivacyPass]
   to help Tor users bypass CAPTCHA challenges.  Their system works as
   follows.  Client C connects - through Tor - to an edge server E
   serving content.  Upon receipt, E serves a CAPTCHA to C, who then
   solves the CAPTCHA and supplies, in response, n blinded points.  E
   verifies the CAPTCHA response and, if valid, signs (at most) n
   blinded points, which are then returned to C along with a batched
   DLEQ proof.  C stores the tokens if the batched proof verifies
   correctly.  When C attempts to connect to E again and is prompted
   with a CAPTCHA, C uses one of the unblinded and signed points, or

Davidson, et al.           Expires May 7, 2020                 [Page 36]
Internet-Draft                    OPRFs                    November 2019

   tokens, to derive a shared symmetric key sk used to MAC the CAPTCHA
   challenge.  C sends the CAPTCHA, MAC, and token input x to E, who can
   use x to derive sk and verify the CAPTCHA MAC.  Thus, each token is
   used at most once by the system.

   The Privacy Pass implementation uses the P-256 instantiation of the
   VOPRF protocol.  For more details, see [DGSTV18].

9.2.  Private Password Checker

   In this application, let D be a collection of plaintext passwords
   obtained by prover P.  For each password p in D, P computes
   VOPRF_Eval on H_1(p), where H_1 is as described above, and stores the
   result in a separate collection D'.  P then publishes D' with Y, its
   public key.  If a client C wishes to query D' for a password p', it
   runs the VOPRF protocol using p as input x to obtain output y.  By
   construction, y will be the OPRF evaluation of p hashed onto the
   curve.  C can then search D' for y to determine if there is a match.

   Concrete examples of important applications in the password domain
   include:

   o  password-protected storage [JKK14], [JKKX16];

   o  perfectly-hiding password management [SJKS17];

   o  password-protected secret-sharing [JKKX17].

9.2.1.  Parameter Commitments

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

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

Davidson, et al.           Expires May 7, 2020                 [Page 37]
Internet-Draft                    OPRFs                    November 2019

11.  References

11.1.  Normative References

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

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

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

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

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

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

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

   [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-05 (work in progress), November 2019.

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

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

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

Davidson, et al.           Expires May 7, 2020                 [Page 38]
Internet-Draft                    OPRFs                    November 2019

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

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

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

   [PrivacyPass]
              "Privacy Pass", n.d.,
              <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>.

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

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

Davidson, et al.           Expires May 7, 2020                 [Page 39]
Internet-Draft                    OPRFs                    November 2019

   [SHAKE]    "SHA-3 Standard, Permutation-Based Hash and Extendable-
              Output Functions", n.d.,
              <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", n.d., <https://eprint.iacr.org/2018/695>.

11.2.  URIs

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

Appendix A.  Test Vectors

   [[TODO: add when done]]

Authors' Addresses

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

   Email: adavidson@cloudflare.com

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

   Email: nick@cloudflare.com

   Christopher A. Wood
   Apple Inc.
   One Apple Park Way
   Cupertino, California 95014
   United States of America

   Email: cawood@apple.com

Davidson, et al.           Expires May 7, 2020                 [Page 40]