InternetDraft  OPRFs  November 2020 
Davidson, et al.  Expires 6 May 2021  [Page] 
 Workgroup:
 Network Working Group
 InternetDraft:
 draftirtfcfrgvoprf05
 Published:
 Intended Status:
 Informational
 Expires:
Oblivious Pseudorandom Functions (OPRFs) using PrimeOrder Groups
Abstract
An Oblivious Pseudorandom Function (OPRF) is a twoparty 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 primeorder groups, including elliptic curves.¶
Discussion Venues
This note is to be removed before publishing as an RFC.¶
Source for this draft and an issue tracker can be found at https://github.com/cfrg/draftirtfcfrgvoprf.¶
Status of This Memo
This InternetDraft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶
InternetDrafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as InternetDrafts. The list of current InternetDrafts is at https://datatracker.ietf.org/drafts/current/.¶
InternetDrafts 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 InternetDrafts as reference material or to cite them other than as "work in progress."¶
This InternetDraft will expire on 6 May 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 (https://trustee.ietf.org/licenseinfo) 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.¶
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 twoparty protocol between a server and a client, where the server holds a PRF key k and the client holds some input x. The protocol allows both parties to cooperate in computing F(k, x) such that: the client learns F(k, x) without learning anything about k; and the server does not learn anything about x or F(k, x). A Verifiable OPRF (VOPRF) is an OPRF wherein the server can prove to the client that F(k, x) was computed using the key k.¶
The usage of OPRFs has been demonstrated in constructing a number of applications: passwordprotected secret sharing schemes [JKKX16]; privacypreserving password stores [SJKS17]; and passwordauthenticated key exchange or PAKE [ID.irtfcfrgopaque]. A VOPRF is necessary in some applications, e.g., the Privacy Pass protocol [ID.davidsonppprotocol], wherein this VOPRF is used to generate onetime authentication tokens to bypass CAPTCHA challenges. VOPRFs have also been used for passwordprotected secret sharing schemes e.g. [JKK14].¶
This document introduces an OPRF protocol built in primeorder groups, applying to finite fields of primeorder 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 publicfacing API, and its security properties.¶
1.1. Change log
 Move to ristretto255 and decaf448 ciphersuites.¶
 Clean up ciphersuite definitions.¶
 Pin domain separation tag construction to draft version.¶
 Move key generation outside of context construction functions.¶
 Editorial changes.¶
 Introduce Client and Server contexts for controlling verifiability and required functionality.¶
 Condense API.¶
 Remove batching from standard functionality (included as an extension)¶
 Add Curve25519 and P256 ciphersuites for applications that prevent strongDH oracle attacks.¶
 Provide explicit primeorder group API and instantiation advice for each ciphersuite.¶
 Proofofconcept implementation in sage.¶
 Remove privacy considerations advice as this depends on applications.¶
 Certify public key during VerifiableFinalize¶
 Remove protocol integration advice¶
 Add text discussing how to perform domain separation¶
 Drop OPRF_/VOPRF_ prefix from algorithm names¶
 Make primeorder group assumption explicit¶
 Changes to algorithms accepting batched inputs¶
 Changes to construction of batched DLEQ proofs¶
 Updated ciphersuites to be consistent with hashtocurve and added OPRF specific ciphersuites¶
1.2. Terminology
The following terms are used throughout this document.¶
 PRF: Pseudorandom Function.¶
 OPRF: Oblivious Pseudorandom Function.¶
 VOPRF: Verifiable Oblivious Pseudorandom Function.¶
 Client: Protocol initiator. Learns pseudorandom function evaluation as the output of the protocol.¶
 Server: Computes the pseudorandom function over a secret key. Learns nothing about the client's input.¶
 NIZK: Noninteractive zero knowledge.¶
 DLEQ: Discrete Logarithm Equality.¶
1.3. Requirements
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶
2. Preliminaries
2.1. Primeorder group API
In this document, we assume the construction of an additive, primeorder
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, ..., p1}
.¶
The fundamental group operation is addition +
with identity element
I
. For any elements A
and B
of the group GG
, A + B = B + A
is
also a member of GG
. Also, for any A
in GG
, there exists an element
A
such that A + (A) = (A) + A = I
. Scalar multiplication is
equivalent to the repeated application of the group operation on an
element A with itself r1
times, this is denoted as r*A = A + ... +
A
. For any element A
, the equality p*A=I
holds. Scalar base multiplication
is equivalent to the repeated application of the group operation on the
base point with itself r1
times, this is denoted as ScalarBaseMult(r)
.
The set of scalars corresponds to GF(p)
.¶
We now detail a number of member functions that can be invoked on a primeorder group.¶
 Order(): Outputs the order of GG (i.e.
p
).¶  Identity(): Outputs the identity element of the group (i.e.
I
).¶  Serialize(A): A member function of
GG
that maps a group elementA
to a unique byte arraybuf
.¶  Deserialize(buf): A member function of
GG
that maps a byte arraybuf
to a group elementA
, or fails if the input is not a valid byte representation of an element.¶  HashToGroup(x): A member function of
GG
that deterministically maps an array of bytesx
to an element ofGG
. The map must ensure that, for any adversary receivingR = HashToGroup(x)
, it is computationally difficult to reverse the mapping. Examples of hash to group functions satisfying this property are described for primeorder (sub)groups of elliptic curves, see [ID.irtfcfrghashtocurve].¶  HashToScalar(x): A member function of
GG
that deterministically maps an array of bytesx
to an element in GF(p). A recommended method for its implementation is instantiating the hash to field function, defined in [ID.irtfcfrghashtocurve] setting the target field to GF(p).¶  RandomScalar(): A member function of
GG
that chooses at random a nonzero element in GF(p).¶
It is convenient in cryptographic applications to instantiate such primeorder groups using elliptic curves, such as those detailed in [SEC2]. For some choices of elliptic curves (e.g. those detailed in [RFC7748], which require accounting for cofactors) there are some implementation issues that introduce inherent discrepancies between standard primeorder groups and the elliptic curve instantiation. In this document, all algorithms that we detail assume that the group is a primeorder group, and this MUST be upheld by any implementer. That is, any curve instantiation should be written such that any discrepancies with a primeorder 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
 We use the notation
x <$ Q
to denote samplingx
from the uniform distribution over the setQ
.¶  For any object
x
, we writelen(x)
to denote its length in bytes.¶  For two byte arrays
x
andy
, writex  y
to denote their concatenation.¶  I2OSP and OS2IP: Convert a byte array to and from a nonnegative integer as described in [RFC8017]. Note that these functions operate on byte arrays in bigendian byte order.¶
All algorithm descriptions are written in a Pythonlike 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 constanttime
bytewise equality between byte arrays a
and b
. This function
returns 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 zeroknowledge 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
longterm private key to the client.¶
The following onebyte values distinguish between these two modes:¶
Mode  Value 

modeBase  0x00 
modeVerifiable  0x01 
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 produces a byte array corresponding to the output
of the OPRF protocol.¶
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
ensure finalized outputs are separate. Guidance for constructing info
can be found in [ID.irtfcfrghashtocurve]; 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. Prior to this phase, keys (skS
, pkS
)
should be generated by calling a KeyGen
function. KeyGen
generates a private and public key pair (skS
, pkS
), where skS
is a
nonzero element chosen at random from the scalar field of the
corresponding group and pkS = ScalarBaseMult(skS)
.¶
The base mode setup functions for creating client and server contexts are below:¶
def SetupBaseServer(suite, skS): 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 verifiable mode setup functions for creating client and server contexts are below:¶
def SetupVerifiableServer(suite, skS, pkS): 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)¶
Each setup function takes a ciphersuite from the list defined in Section 4. Each ciphersuite has a twobyte field ID used to identify the suite.¶
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. Each data structure description uses TLS notation (see [RFC8446], Section 3).¶
The following types are a list of aliases that are used throughout the protocol.¶
A ClientInput
is a byte array.¶
opaque ClientInput<1..2^161>;¶
A SerializedElement
is also a byte array, representing the unique
serialization of an Element
.¶
opaque SerializedElement<1..2^161>;¶
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^161>; Scalar blind<1..2^161>; } 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^161>; /* only for modeVerifiable */ } Evaluation;¶
Evaluations may also be combined in batches with a constantsize 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^161>; Scalar proof<0...2^161>; /* only for modeVerifiable */ } BatchedEvaluation;¶
3.4. Context APIs
In this section, we detail the APIs available on the client and server
(V)OPRF contexts. This document uses the types Element
and Scalar
to
denote elements of the group GG
and its underlying scalar field GF(p)
,
respectively. For notational clarity, PublicKey
is an item of type
Element
and PrivateKey
is an item of type Scalar
.¶
3.4.1. Server Context
The ServerContext encapsulates the context string constructed during
setup and the (V)OPRF key pair. It has three functions, Evaluate
,
FullEvaluate
and VerifyFinalize
described below. Evaluate
takes
serialized representations of blinded group elements from the client as inputs.¶
FullEvaluate
takes ClientInput values, and it is useful for applications
that need to compute the whole OPRF protocol on the server side only.¶
VerifyFinalize
takes ClientInput values and their corresponding output
digests from Finalize
as input, and returns true if the inputs match the outputs.¶
Note that VerifyFinalize
and FullEvaluate
are not used in the main OPRF
protocol. They are exposed as an API for building higherlevel protocols.¶
3.4.1.1. Evaluate
Input: PrivateKey skS SerializedElement blindToken Output: Evaluation Ev def Evaluate(skS, blindToken): BT = GG.Deserialize(blindToken) Z = skS * BT serializedElement = GG.Serialize(Z) Ev = Evaluation{ element: serializedElement } return Ev¶
3.4.1.2. FullEvaluate
Input: PrivateKey skS ClientInput input opaque info<1..2^161> Output: opaque output<1..2^161> def FullEvaluate(skS, input, info): P = GG.HashToGroup(input) T = skS * P issuedToken = GG.serialize(T) finalizeDST = "VOPRF05Finalize"  self.contextString hashInput = I2OSP(len(input), 2)  input  I2OSP(len(issuedToken), 2)  issuedToken  I2OSP(len(info), 2)  info  I2OSP(len(finalizeDST), 2)  finalizeDST return Hash(hashInput)¶
3.4.1.3. VerifyFinalize
Input: PrivateKey skS ClientInput input opaque info<1..2^161> opaque output<1..2^161> Output: boolean valid def VerifyFinalize(skS, input, info, output): T = GG.HashToGroup(input) element = GG.Serialize(T) issuedElement = Evaluate(skS, [element]) E = GG.Serialize(issuedElement) finalizeDST = "VOPRF05Finalize"  self.contextString hashInput = I2OSP(len(input), 2)  input  I2OSP(len(E), 2)  E  I2OSP(len(info), 2)  info  I2OSP(len(finalizeDST), 2)  finalizeDST digest = Hash(hashInput) return CT_EQUAL(digest, output)¶
[[RFC editor: please change "VOPRF05" to "RFCXXXX", where XXXX is the final number, here and elsewhere before publication.]]¶
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 GenerateProof
and ComputeComposites
, described below.¶
3.4.2.1. Evaluate
Input: PrivateKey skS PublicKey pkS SerializedElement blindToken Output: Evaluation Ev def Evaluate(skS, pkS, blindToken): BT = GG.Deserialize(blindToken) Z = skS * BT serializedElement = GG.Serialize(Z) proof = GenerateProof(skS, pkS, blindToken, serializedElement) Ev = Evaluation{ element: serializedElement, proof: proof } return Ev¶
The helper functions GenerateProof
and ComputeComposites
are defined
below.¶
3.4.2.2. GenerateProof
Input: PrivateKey skS PublicKey pkS SerializedElement blindToken SerializedElement element Output: Scalar proof[2] def GenerateProof(skS, pkS, blindToken, element) blindTokenList = [blindToken] elementList = [element] a = ComputeComposites(pkS, blindTokenList, elementList) M = GG.Deserialize(a[0]) r = GG.RandomScalar() a2 = GG.Serialize(ScalarBaseMult(r)) a3 = GG.Serialize(r * M) challengeDST = "VOPRF05challenge"  self.contextString h2Input = I2OSP(len(pkS), 2)  pkS  I2OSP(len(a[0]), 2)  a[0]  I2OSP(len(a[1]), 2)  a[1]  I2OSP(len(a2), 2)  a2  I2OSP(len(a3), 2)  a3  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 constantsize
output. This functionality lets applications batch inputs together to
produce a constantsize 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 blindToken
and element
are translated into lists before
invoking ComputeComposites
. A batched 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: PublicKey pkS SerializedElement blindTokens[m] SerializedElement elements[m] Output: SerializedElement composites[2] def ComputeComposites(pkS, blindTokens, elements): seedDST = "VOPRF05seed"  self.contextString compositeDST = "VOPRF05composite"  self.contextString h1Input = I2OSP(len(pkS), 2)  pkS  I2OSP(len(blindTokens), 2)  blindTokens  I2OSP(len(elements), 2)  elements  I2OSP(len(seedDST), 2)  seedDST seed = Hash(h1Input) M = GG.Identity() Z = GG.Identity() for i = 0 to m1: h2Input = I2OSP(len(seed), 2)  seed  I2OSP(i, 2)  I2OSP(len(compositeDST), 2)  compositeDST di = GG.HashToScalar(h2Input) Mi = GG.Deserialize(blindTokens[i]) Zi = GG.Deserialize(elements[i]) M = di * Mi + M Z = di * Zi + Z return [GG.Serialize(M), GG.Serialize(Z)]¶
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 blindToken def Blind(input): r = GG.RandomScalar() P = GG.HashToGroup(input) blindToken = GG.Serialize(r * P) token = Token{ data: input, blind: r } return (token, blindToken)¶
3.4.3.2. Unblind
Input: Token token Evaluation Ev Output: SerializedElement issuedToken def Unblind(token, Ev): r = token.blind Z = GG.Deserialize(Ev.element) N = (r^(1)) * Z issuedToken = GG.Serialize(N) return issuedToken¶
3.4.3.3. Finalize
Input: Token token SerializedElement issuedToken opaque info<1..2^161> Output: opaque output<1..2^161> def Finalize(token, issuedToken, info): finalizeDST = "VOPRF05Finalize"  self.contextString hashInput = I2OSP(len(token.data), 2)  token.data  I2OSP(len(issuedToken), 2)  issuedToken  I2OSP(len(info), 2)  info  I2OSP(len(finalizeDST), 2)  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.¶
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 blindToken Evaluation Ev Output: boolean verified def VerifyProof(pkS, blindToken, Ev): blindTokenList = [blindToken] elementList = [Ev.element] a = ComputeComposites(pkS, blindTokenList, elementList) A' = (ScalarBaseMult(Ev.proof[1]) + Ev.proof[0] * pkS) B' = (Ev.proof[1] * M + Ev.proof[0] * Z) a2 = GG.Serialize(A') a3 = GG.Serialize(B') challengeDST = "VOPRF05challenge"  self.contextString h2Input = I2OSP(len(pkS), 2)  pkS  I2OSP(len(a[0]), 2)  a[0]  I2OSP(len(a[1]), 2)  a[1]  I2OSP(len(a2), 2)  a2  I2OSP(len(a3), 2)  a3  I2OSP(len(challengeDST), 2)  challengeDST c = GG.HashToScalar(h2Input) return CT_EQUAL(c, Ev.proof[0])¶
3.4.4.2. Unblind
Input: PublicKey pkS Token token SerializedElement blindToken Evaluation Ev Output: SerializedElement issuedToken def Unblind(pkS, token, blindToken, Ev): if VerifyProof(pkS, blindToken, Ev) == false: ABORT() r = token.blind Z = GG.Deserialize(Ev.element) N = (r^(1)) * Z issuedToken = GG.Serialize(N) return issuedToken¶
4. Ciphersuites
A ciphersuite (also referred to as 'suite' in this document) for the protocol wraps the functionality required for the protocol to take place. This ciphersuite should be available to both the client and server, and agreement on the specific instantiation is assumed throughout. A ciphersuite contains instantiations of the following functionalities:¶

GG
: A primeorder group exposing the API detailed in Section 2.1, with base point defined in the corresponding reference for each group.¶ 
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, HashToScalar, and serialization functionalities.¶
Applications should take caution in using ciphersuites targeting P256 and ristretto255. See Section 5.2 for related discussion.¶
4.1. OPRF(ristretto255, SHA256)

Group: ristretto255 [RISTRETTO]¶
 HashToGroup(): hash_to_ristretto255
[ID.irtfcfrghashtocurve] with DST =
"VOPRF05"  contextString, where contextString is that which is
computed in the Setup functions, and
expand_message
=expand_message_xmd
using SHA256.¶  HashToScalar(): Use hash_to_field from [ID.irtfcfrghashtocurve] using Order() as the prime modulus, with L=48, and expand_message_xmd with SHA256.¶
 Serialization: Serialization converts group elements to 32byte strings using the 'Encode' function from [RISTRETTO]. Deserialization converts 32byte strings to group elements using the 'Decode' function from [RISTRETTO].¶
 HashToGroup(): hash_to_ristretto255
[ID.irtfcfrghashtocurve] with DST =
"VOPRF05"  contextString, where contextString is that which is
computed in the Setup functions, and
 Hash: SHA256¶
 ID: 0x0001¶
4.2. OPRF(decaf448, SHA512)

 HashToGroup(): hash_to_decaf448
[ID.irtfcfrghashtocurve] with DST =
"VOPRF05"  contextString, where contextString is that which is
computed in the Setup functions, and
expand_message
=expand_message_xmd
using SHA512.¶  HashToScalar(): Use hash_to_field from [ID.irtfcfrghashtocurve]
using Order() as the prime modulus, with L=84, and
expand_message_xmd
with SHA512.¶  Serialization: Serialization converts group elements to 56byte strings using the 'Encode' function from [RISTRETTO]. Deserialization converts 56byte strings to group elements using the 'Decode' function from [RISTRETTO].¶
 HashToGroup(): hash_to_decaf448
[ID.irtfcfrghashtocurve] with DST =
"VOPRF05"  contextString, where contextString is that which is
computed in the Setup functions, and
 Hash: SHA512¶
 ID: 0x0002¶
4.3. OPRF(P256, SHA256)

Group: P256 (secp256r1) [x9.62]¶
 HashToGroup(): P256_XMD:SHA256_SSWU_RO_ [ID.irtfcfrghashtocurve] with DST = "VOPRF05"  contextString, where contextString is that which is computed in the Setup functions.¶
 HashToScalar(): Use hash_to_field from [ID.irtfcfrghashtocurve]
using Order() as the prime modulus, with L=48, and
expand_message_xmd
with SHA256.¶  Serialization: The compressed point encoding for the curve [SEC1] consisting of 33 bytes.¶
 Hash: SHA256¶
 ID: 0x0003¶
4.4. OPRF(P384, SHA512)

Group: P384 (secp384r1) [x9.62]¶
 HashToGroup(): P384_XMD:SHA512_SSWU_RO_ [ID.irtfcfrghashtocurve] with DST = "VOPRF05"  contextString, where contextString is that which is computed in the Setup functions.¶
 HashToScalar(): Use hash_to_field from [ID.irtfcfrghashtocurve]
using Order() as the prime modulus, with L=72, and
expand_message_xmd
with SHA512.¶  Serialization: The compressed point encoding for the curve [SEC1] consisting of 49 bytes.¶
 Hash: SHA512¶
 ID: 0x0004¶
4.5. OPRF(P521, SHA512)

Group: P521 (secp521r1) [x9.62]¶
 HashToGroup(): P521_XMD:SHA512_SSWU_RO_ [ID.irtfcfrghashtocurve] with DST = "VOPRF05"  contextString, where contextString is that which is computed in the Setup functions.¶
 HashToScalar(): Use hash_to_field from [ID.irtfcfrghashtocurve]
using Order() as the prime modulus, with L=98, and
expand_message_xmd
with SHA512.¶  Serialization: The compressed point encoding for the curve [SEC1] consisting of 67 bytes.¶
 Hash: SHA512¶
 ID: 0x0005¶
5. Security Considerations
This section discusses the cryptographic security of our protocol, along with some suggestions and tradeoffs that arise from the implementation of an OPRF.¶
5.1. Security properties
The security properties of an OPRF protocol with functionality y = F(k, x) include those of a standard PRF. Specifically:¶
 Pseudorandomness: F is pseudorandom if the output y = F(k,x) on any input x is indistinguishable from uniformly sampling any element in F's range, for a random sampling of k.¶
In other words, consider an adversary that picks inputs x from the domain of F and evaluates F on (k,x) (without knowledge of randomly sampled k). Then the output distribution F(k,x) is indistinguishable from the output distribution of a randomly chosen function with the same domain and range.¶
A consequence of showing that a function is pseudorandom, is that it is necessarily nonmalleable (i.e. we cannot compute a new evaluation of F from an existing evaluation). A genuinely random function will be nonmalleable with high probability, and so a pseudorandom function must be nonmalleable to maintain indistinguishability.¶
An OPRF protocol must also satisfy the following property:¶
 Oblivious: The server must learn nothing about the client's input or the output of the function. In addition, the client must learn nothing about the server's private key.¶
Essentially, obliviousness tells us that, even if the server learns the client's input x at some point in the future, then the server will not be able to link any particular OPRF evaluation to x. This property is also known as unlinkability [DGSTV18].¶
Optionally, for any protocol that satisfies the above properties, there is an additional security property:¶
 Verifiable: The client must only complete execution of the protocol if it can successfully assert that the OPRF output it computes is correct. This is taken with respect to the OPRF key held by the server.¶
Any OPRF that satisfies the 'verifiable' security property is known as a verifiable OPRF, or VOPRF for short. In practice, the notion of verifiability requires that the server commits to the key before the actual protocol execution takes place. Then the client verifies that the server has used the key in the protocol using this commitment. In the following, we may also refer to this commitment as a public key.¶
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 primeorder p, and let FFp be the finite field of order p.¶
5.2.1.1. Discretelog (DL) problem
Given G, a generator of GG, and H = hG for some h in FFp; output h.¶
5.2.2. Protocol security
Our OPRF construction is based on the VOPRF construction known as 2HashDHNIZK given by [JKK14]; essentially without providing zeroknowledge 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 OneMore Gap DH is computationally difficult to solve.¶
The (N,Q)OneMore Gap DH (OMDH) problem asks the following.¶
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 2HashDHNIZK 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. QstrongDH oracle
A sideeffect of our OPRF design is that it allows instantiation of a oracle for constructing QstrongDH (QsDH) samples. The QStrongDH 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 QsDH 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 QsDH 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^(Q1))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.¶
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 128bit group instantiations would appear to in fact instantiate an OPRF with 128log_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 primeorder group using
elliptic curves is a method to instantiate the function
GG.HashToGroup
, that maps inputs to group elements. In the elliptic
curve setting, this deterministically maps inputs x (as byte arrays) to
uniformly chosen points on the curve.¶
In the security proof of the construction Hash is modeled as a random
oracle. This implies that any instantiation of GG.HashToGroup
must be
preimage and collision resistant. In Section 4 we give
instantiations of this functionality based on the functions described in
[ID.irtfcfrghashtocurve]. Consequently, any OPRF implementation
must adhere to the implementation and security considerations discussed
in [ID.irtfcfrghashtocurve] when instantiating the function.¶
5.4. Timing Leaks
To ensure no information is leaked during protocol execution, all
operations that use secret data MUST run in constant time. Operations that
SHOULD run in constant time include all primeorder group operations and
proofspecific operations (GenerateProof()
and VerifyProof()
).¶
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 QsDH attacks from Section 5.2.3.¶
To combat attacks of this nature, regular key rotation should be employed on the serverside. A suitable keycycle 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 clientside blinding is carried out directly on the output of
H(x)
, i.e. computing r * H(x)
for some r <$ GF(p)
. In the
[ID.irtfcfrgopaque] 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
preprocess tables of blinded scalar multiplications for G
. This may
give it a computational efficiency advantage (due to the fact that a
fixedbase multiplication can be calculated faster than a variablebase
multiplication). Preprocessing 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.¶
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(ScalarBaseMult(r)) blindedPublicKey = GG.Serialize(r * PK) preproc = PrepocessedBlind{ blind: r, blindedGenerator: blindedGenerator, blindedPublicKey: blindedPublicKey, } return preproc¶
6.2. Blind
Input: ClientInput input PreprocessedBlind preproc Output: Token token SerializedElement blindToken def Blind(input, preproc): Q = GG.Deserialize(preproc.blindedGenerator) /* Q = ScalarBaseMult(r) */ P = GG.HashToGroup(input) token = Token{ data: input, blind: preproc.blindedPublicKey } blindToken = GG.Serialize(P + Q) /* P + ScalarBaseMult(r) */ return (token, blindToken)¶
6.3. Unblind
Input: Token token Evaluation ev SerializedElement blindToken Output: SerializedElement unblinded def Unblind(token, ev, blindToken): PKR = GG.Deserialize(token.blind) Z = GG.Deserialize(ev.element) N := Z  PKR issuedToken = GG.Serialize(N) return issuedToken¶
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¶
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.¶
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. EliShaoul 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 DiffieHellman Problem", <https://eprint.iacr.org/2004/306>.
 [Cheon06]
 "Security Analysis of the Strong DiffieHellman Problem", <https://www.iacr.org/archive/eurocrypt2006/40040001/40040001.pdf>.
 [DGSTV18]
 "Privacy Pass, Bypassing Internet Challenges Anonymously", <https://www.degruyter.com/view/j/popets.2018.2018.issue3/popets20180026/popets20180026.xml>.
 [ID.davidsonppprotocol]
 Davidson, A., "Privacy Pass: The Protocol", Work in Progress, InternetDraft, draftdavidsonppprotocol01, , <http://www.ietf.org/internetdrafts/draftdavidsonppprotocol01.txt>.
 [ID.irtfcfrghashtocurve]
 FazHernandez, A., Scott, S., Sullivan, N., Wahby, R., and C. Wood, "Hashing to Elliptic Curves", Work in Progress, InternetDraft, draftirtfcfrghashtocurve10, , <http://www.ietf.org/internetdrafts/draftirtfcfrghashtocurve10.txt>.
 [ID.irtfcfrgopaque]
 Krawczyk, H., Lewi, K., and C. Wood, "The OPAQUE Asymmetric PAKE Protocol", Work in Progress, InternetDraft, draftirtfcfrgopaque00, , <http://www.ietf.org/internetdrafts/draftirtfcfrgopaque00.txt>.
 [JKK14]
 "RoundOptimal PasswordProtected Secret Sharing and TPAKE in the PasswordOnly model", <https://eprint.iacr.org/2014/650>.
 [JKKX16]
 "HighlyEfficient and Composable PasswordProtected Secret Sharing (Or, How to Protect Your Bitcoin Wallet Online)", <https://eprint.iacr.org/2016/144>.
 [PrivacyPass]
 "Privacy Pass", <https://github.com/privacypass/challengebypassserver>.
 [RFC2119]
 Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <https://www.rfceditor.org/info/rfc2119>.
 [RFC7748]
 Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10.17487/RFC7748, , <https://www.rfceditor.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, , <https://www.rfceditor.org/info/rfc8017>.
 [RFC8174]
 Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, , <https://www.rfceditor.org/info/rfc8174>.
 [RISTRETTO]
 Valence, H., Grigg, J., Tankersley, G., Valsorda, F., Lovecruft, I., and M. Hamburg, "The ristretto255 and decaf448 Groups", Work in Progress, InternetDraft, draftirtfcfrgristretto255decaf44800, , <http://www.ietf.org/internetdrafts/draftirtfcfrgristretto255decaf44800.txt>.
 [SEC1]
 Standards for Efficient Cryptography Group (SECG), ., "SEC 1: Elliptic Curve Cryptography", <https://www.secg.org/sec1v2.pdff>.
 [SEC2]
 Standards for Efficient Cryptography Group (SECG), ., "SEC 2: Recommended Elliptic Curve Domain Parameters", <http://www.secg.org/sec2v2.pdf>.
 [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.621998, .
9.2. Informative References
 [RFC8446]
 Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10.17487/RFC8446, , <https://www.rfceditor.org/info/rfc8446>.