RFC 9497: Oblivious Pseudorandom Functions (OPRFs) Using Prime-Order Groups
- A. Davidson,
- A. Faz-Hernandez,
- N. Sullivan,
- C. A. Wood
Abstract
An Oblivious Pseudorandom Function (OPRF) is a two-party protocol between
a client and a server for computing the output of a Pseudorandom Function (PRF).
The server provides the PRF private key, and the client provides the PRF
input. At the end of the protocol, the client learns the PRF output without
learning anything about the PRF private key, and the server learns neither
the PRF input nor output. An OPRF can also satisfy a notion of 'verifiability'
Status of This Memo
This document is not an Internet Standards Track specification; it is published for informational purposes.¶
This document is a product of the Internet Research Task Force
(IRTF). The IRTF publishes the results of Internet
Information about the current status of this document, any
errata, and how to provide feedback on it may be obtained at
https://
Copyright Notice
Copyright (c) 2023 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://
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 indistinguishab
OPRFs have a variety of applications, including password
This document specifies OPRF, VOPRF, and POPRF protocols built upon prime-order groups. The document describes each protocol variant, along with application considerations, and their security properties.¶
This document represents the consensus of the Crypto Forum Research Group (CFRG). It is not an IETF product and is not a standard.¶
1.1. Requirements Language
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.¶
1.2. Notation and Terminology
The following functions and notation are used throughout the document.¶
All algorithms and procedures described in this document are laid out in a Python-like pseudocode. Each function takes a set of inputs and parameters and produces a set of output values. Parameters become constant values once the protocol variant and the ciphersuite are fixed.¶
The PrivateInput data type refers to inputs that are known only to the client
in the protocol, whereas the PublicInput data type refers to inputs that are
known to both the client and server in the protocol. Both PrivateInput and
PublicInput are opaque byte strings of arbitrary length no larger than 216 - 1 bytes.
This length restriction exists because PublicInput and PrivateInput values
are length-prefixed with two bytes before use throughout the protocol.¶
String values, such as "Derive
The following terms are used throughout this document.¶
- PRF:
- Pseudorandom Function¶
- OPRF:
- Oblivious Pseudorandom Function¶
- VOPRF:
- Verifiable Oblivious Pseudorandom Function¶
- POPRF:
- Partially Oblivious Pseudorandom Function¶
- Client:
- Protocol initiator. Learns PRF evaluation as the output of the protocol.¶
- Server:
- Computes the PRF using a private key. Learns nothing about the client's input or output.¶
2. Preliminaries
The protocols in this document have two primary dependencies:¶
-
Group: - A prime-order group implementing the API described below in Section 2.1. See Section 4 for specific instances of groups.¶
-
Hash: - A cryptographic hash function whose output length is
Nhbytes.¶
Section 4 specifies ciphersuites as combinations of Group and Hash.¶
2.1. Prime-Order Group
In this document, we assume the construction of an additive, prime-order
group, denoted Group, for performing all mathematical operations. In prime-order groups,
any element (other than the identity) can generate the other elements of the
group. Usually, one element
is fixed and defined as the group generator. Such groups are
uniquely determined by the choice of the prime p that defines the
order of the group. (However, different representations
of the group for a single p may exist. Section 4 lists specific groups that
indicate both the order and representation
The fundamental group operation is addition + with identity element
I. For any elements A and B of the group, A + B = B + A is
also a member of the group. Also, for any A in the group, there exists an element
-A, such that A + (-A) = (-A) + A = I. Scalar multiplication by
r is
equivalent to the repeated application of the group operation on an
element A with itself r - 1 times; this is denoted as r * A = A + ... + A.
For any element A, p * A = I. The case when the scalar multiplication is
performed on the group generator is denoted as ScalarMultGen(r).
Given two elements A and B, the discrete logarithm problem is to find
an integer k, such that B = k * A. Thus, k is the discrete logarithm of
B with respect to the base A.
The set of scalars corresponds to GF(p), a prime field of order p, and is
represented as the set of integers defined by {0, 1, ..., p - 1}.
This document uses types
Element and Scalar to denote elements of the group and its set of
scalars, respectively.¶
We now detail a number of member functions that can be invoked on a prime-order group.¶
- Order():
- Outputs the order of the group (i.e.,
p).¶ - Identity():
- Outputs the identity element of the group (i.e.,
I).¶ - Generator():
- Outputs the generator element of the group.¶
- HashToGroup(x):
- Deterministicall
y maps an array of bytes xto an element ofGroup. The map must ensure that, for any adversary receivingR = HashToGroup(x), it is computationally difficult to reverse the mapping. This function is optionally parameterized by a domain separation tag (DST); see Section 4. Security properties of this function are described in [RFC9380].¶ - HashToScalar(x):
- Deterministicall
y maps an array of bytes xto an element in GF(p). This function is optionally parameterized by a DST; see Section 4. Security properties of this function are described in [RFC9380], Section 10.5.¶ - RandomScalar():
- Chooses at random a nonzero element in GF(p).¶
- Scalar
Inverse (s ): - Returns the inverse of input Scalar
sonGF(p).¶ - Serialize
Element (A ): - Maps an Element
Ato a canonical byte arraybufof fixed-lengthNe.¶ - Deserialize
Element (buf ): - Attempts to map a byte array
bufto an ElementAand fails if the input is not the valid canonical byte representation of an element of the group. This function can raise a DeserializeError if deserialization fails or Ais the identity element of the group; see Section 4 for group-specific input validation steps.¶ - Serialize
Scalar (s ): - Maps Scalar
sto a canonical byte arraybufof fixed-lengthNs.¶ - Deserialize
Scalar (buf ): - Attempts to map a byte array
bufto Scalars. This function can raise a DeserializeError if deserialization fails; see Section 4 for group-specific input validation steps.¶
Section 4 contains details for the implementation of this interface for different prime-order groups instantiated over elliptic curves. In particular, for some choices of elliptic curves, e.g., those detailed in [RFC7748], which require accounting for cofactors, Section 4 describes required steps necessary to ensure the resulting group is of prime order.¶
2.2. Discrete Logarithm Equivalence Proofs
A proof of knowledge allows a prover to convince a verifier that some statement is true. If the prover can generate a proof without interaction with the verifier, the proof is noninteractive. If the verifier learns nothing other than whether the statement claimed by the prover is true or false, the proof is zero-knowledge.¶
This section describes a noninteractive, zero-knowledge proof for discrete logarithm equivalence (DLEQ), which is used in the construction of VOPRF and POPRF. A DLEQ proof demonstrates that two pairs of group elements have the same discrete logarithm without revealing the discrete logarithm.¶
The DLEQ proof resembles the Chaum-Pedersen [ChaumPedersen] proof, which is shown to be zero-knowledge by Jarecki, et al. [JKK14] and is noninteractive after applying the Fiat-Shamir transform [FS00]. Furthermore, Davidson, et al. [DGSTV18] showed a proof system for batching DLEQ proofs that has constant-size proofs with respect to the number of inputs. The specific DLEQ proof system presented below follows this latter construction with two modifications: (1) the transcript used to generate the seed includes more context information and (2) the individual challenges for each element in the proof is derived from a seed-prefixed hash-to-scalar invocation, rather than being sampled from a seeded Pseudorandom Number Generator (PRNG). The description is split into two subsections: one for generating the proof, which is done by servers in the verifiable protocols, and another for verifying the proof, which is done by clients in the protocol.¶
2.2.1. Proof Generation
Generating a proof is done with the GenerateProof function, as defined below.
Given Element values A and B, two non-empty lists of Element values C and D of length
m, and Scalar k, this function produces a proof that k * A == B
and k * C[i] == D[i] for each i in [0, ..., m - 1].
The output is a value of type Proof, which is a tuple of two Scalar
values. We use the notation proof[0] and proof[1] to denote
the first and second elements in this tuple, respectively.¶
GenerateProof accepts lists of inputs to amortize the cost of proof
generation. Applications can take advantage of this functionality to
produce a single, constant-sized proof for m DLEQ inputs, rather
than m proofs for m DLEQ inputs.¶
The helper function Compute is as defined below and is an
optimization of the Compute function for servers since they have
knowledge of the private key.¶
When used in the protocol described in Section 3, the parameter contextString is
as defined in Section 3.2.¶
2.2.2. Proof Verification
Verifying a proof is done with the VerifyProof function, as defined below.
This function takes Element values A and B, two non-empty lists of Element values C and D
of length m, and a Proof value output from GenerateProof. It outputs a
single boolean value indicating whether or not the proof is valid for the
given DLEQ inputs. Note this function can verify proofs on lists of inputs
whenever the proof was generated as a batched DLEQ proof with the same inputs.¶
The definition of Compute is given below.¶
When used in the protocol described in Section 3, the parameter contextString is
as defined in Section 3.2.¶
3. Protocol
In this section, we define and describe three protocol variants referred to as the OPRF, VOPRF, and POPRF modes. Each of these variants involves two messages between the client and server, but they differ slightly in terms of the security properties; see Section 7.1 for more information. A high-level description of the functionality of each mode follows.¶
In the OPRF mode, a client and server interact to compute output = F(skS, input),
where input is the client's private input, skS is the server's private key,
and output is the OPRF output. After the execution of the protocol, the
client learns the output and the server learns nothing.
This interaction is shown below.¶
In the VOPRF mode, the client additionally receives proof that the server used
skS in computing the function. To achieve verifiability, as in [JKK14], the
server provides a zero-knowledge proof that the key provided as input by the server in
the BlindEvaluate function is the same key as is used to produce the server's public key, pkS,
which the client receives as input to the protocol. This proof does not reveal the server's
private key to the client. This interaction is shown below.¶
The POPRF mode extends the VOPRF mode such that the client and
server can additionally provide the public input info, which is used in computing
the PRF. That is, the client and server interact to compute
output = F(skS, input, info), as is shown below.¶
Each protocol consists of an offline setup phase and an online phase, as described in Sections 3.2 and 3.3, respectively. Configuration details for the offline phase are described in Section 3.1.¶
3.1. Configuration
Each of the three protocol variants are identified with a one-byte value (in hexadecimal):¶
Additionally, each protocol variant is instantiated with a ciphersuite or suite. Each ciphersuite is identified with an ASCII string identifier, referred to as identifier; see Section 4 for the set of initial ciphersuite values.¶
The mode and ciphersuite identifier values are combined to create a "context string" used throughout the protocol with the following function:¶
3.2. Key Generation and Context Setup
In the offline setup phase, the server generates a fresh, random key
pair (skS, pkS). There are two ways to generate this key pair.
The first of which is using the GenerateKeyPair function described below.¶
The second way to generate the key pair is via the deterministic key
generation function DeriveKeyPair, as described in Section 3.2.1.
Applications and implementations can use either method in practice.¶
Also during the offline setup phase, both the client and server create a
context used for executing the online phase of the protocol after agreeing on a
mode and ciphersuite identifier. The context, such as OPRFServer,
is an implementation
The OPRF variant server and client contexts are created as follows:¶
The VOPRF variant server and client contexts are created as follows:¶
The POPRF variant server and client contexts are created as follows:¶
3.2.1. Deterministic Key Generation
This section describes a deterministic key generation function, DeriveKeyPair.
It accepts a seed of 32 bytes generated from a cryptographicalinfo string.
Note that, by design, knowledge of seed and info
is necessary to compute this function, which means that the secrecy of the
output private key (skS) depends on the secrecy of seed (since the info
string is public).¶
3.3. Online Protocol
In the online phase, the client and server engage in a two-message protocol to compute the protocol output. This section describes the protocol details for each protocol variant. Throughout each description, the following parameters are assumed to exist:¶
- G:
- a prime-order group implementing the API described in Section 2.1¶
- contextString:
- a
PublicInputdomain separation tag constructed during context setup, as created in Section 3.1¶ - skS and pkS:
- a Scalar and Element representing the private and public keys configured for the client and server in Section 3.2¶
Applications serialize protocol messages between the client and server for
transmission. Element values and Scalar values are serialized to byte arrays, and values
of type Proof are serialized as the concatenation of two serialized Scalar values.
Deserializing these values can fail; in which case, the application MUST abort
the protocol, raising a DeserializeError failure.¶
Applications MUST check that input Element values received over the wire are not the group identity element. This check is handled after deserializing Element values; see Section 4 for more information and requirements on input validation for each ciphersuite.¶
3.3.1. OPRF Protocol
The OPRF protocol begins with the client blinding its input, as described
by the Blind function below. Note that this function can fail with an
Invalid error for certain inputs that map to the group identity
element. Dealing with this failure is an application
Clients store blind locally and send blindedElement to the server for evaluation.
Upon receipt, servers process blindedElement using the BlindEvaluate function described
below.¶
Servers send the output evaluatedElement to clients for processing.
Recall that servers may process multiple client inputs by applying the
BlindEvaluate function to each blindedElement received and returning an
array with the corresponding evaluatedElement values.¶
Upon receipt of evaluatedElement, clients process it to complete the
OPRF evaluation with the Finalize function described below.¶
An entity that knows both the private key and the input can compute the PRF
result using the following Evaluate function.¶
3.3.2. VOPRF Protocol
The VOPRF protocol begins with the client blinding its input, using the same
Blind function as in Section 3.3.1. Clients store the output blind locally
and send blindedElement to the server for evaluation. Upon receipt,
servers process blindedElement to compute an evaluated element and a DLEQ
proof using the following BlindEvaluate function.¶
In the description above, inputs to GenerateProof are one-item
lists. Using larger lists allows servers to batch the evaluation of multiple
elements while producing a single batched DLEQ proof for them.¶
The server sends both evaluatedElement and proof back to the client.
Upon receipt, the client processes both values to complete the VOPRF computation
using the Finalize function below.¶
As in BlindEvaluate, inputs to VerifyProof are one-item lists. Clients can
verify multiple inputs at once whenever the server produced a batched DLEQ proof
for them.¶
Finally, an entity that knows both the private key and the input can compute the PRF
result using the Evaluate function described in Section 3.3.1.¶
3.3.3. POPRF Protocol
The POPRF protocol begins with the client blinding its input, using the
following modified Blind function. In this step, the client also binds a
public info value, which produces an additional tweakedKey to be used later
in the protocol. Note that this function can fail with an
Invalid error for certain private inputs that map to the group
identity element, as well as certain public inputs that, if not detected at
this point, will cause server evaluation to fail. Dealing with either failure
is an application
Clients store the outputs blind and tweakedKey locally and send blindedElement to
the server for evaluation. Upon receipt, servers process blindedElement to
compute an evaluated element and a DLEQ proof using the following BlindEvaluate function.¶
In the description above, inputs to GenerateProof are one-item
lists. Using larger lists allows servers to batch the evaluation of multiple
elements while producing a single batched DLEQ proof for them.¶
BlindEvaluate triggers InverseError when the function is about to
calculate the inverse of a zero scalar, which does not exist and therefore
yields a failure in the protocol.
This only occurs for info values that map to the private key of the server. Thus,
clients that cause this error should be assumed to know the server private key. Hence,
this error can be a signal for the server to replace its private key.¶
The server sends both evaluatedElement and proof back to the client.
Upon receipt, the client processes both values to complete the POPRF computation
using the Finalize function below.¶
As in BlindEvaluate, inputs to VerifyProof are one-item lists.
Clients can verify multiple inputs at once whenever the server produced a
batched DLEQ proof for them.¶
Finally, an entity that knows both the private key and the input can compute
the PRF result using the Evaluate function described below.¶
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. The 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
-
Group: - A prime-order group exposing the API detailed in Section 2.1, with the
generator element defined in the corresponding reference for each group. Each
group also specifies
HashToGroup,HashToScalar, and serialization functionalities. For HashToGroup, the domain separation tag (DST) is constructed in accordance with the recommendations in [RFC9380], Section 3.1. ForHashToScalar, each group specifies an integer order that is used in reducing integer values to a member of the corresponding scalar field.¶ -
Hash: - A cryptographic hash function whose output length is Nh bytes long.¶
This section includes an initial set of ciphersuites with supported groups and hash functions. It also includes implementation details for each ciphersuite, focusing on input validation. Future documents can specify additional ciphersuites as needed, provided they meet the requirements in Section 4.6.¶
For each ciphersuite, contextString is that which is computed in the Setup functions.
Applications should take caution in using ciphersuites targeting P-256 and ristretto255.
See Section 7.2 for related discussion.¶
4.1. OPRF(ristretto255, SHA-512)
This ciphersuite uses ristretto255 [RFC9496] for the Group and SHA-512 for the hash
function. The value of the ciphersuite identifier is "ristretto255
- Group:
-
- Order():
- Return 2252 + 277423177773723
5353585193779088 3648493 (see [RFC9496]).¶ - Identity():
- As defined in [RFC9496].¶
- Generator():
- As defined in [RFC9496].¶
- HashToGroup():
- Use hash
_to _ristretto255 [RFC9380] with DST = "HashToGroup-" || contextString and expand_message=expandusing SHA-512.¶_message _xmd - HashToScalar():
- Compute
uniform_bytesusingexpand_message=expand, DST = "HashToScalar-" || contextString, and an output length of 64 bytes, interpret_message _xmd uniform_bytesas a 512-bit integer in little-endian order, and reduce the integer moduloGroup.Order().¶ - Scalar
Inverse (s ): - Returns the multiplicative inverse of input Scalar
smodGroup.Order().¶ - RandomScalar():
- Implemented by returning a uniformly random Scalar in the range
[0,
G.Order()- 1]. Refer to Section 4.7 for implementation guidance.¶ - Serialize
Element (A ): - Implemented using the
Encodefunction from Section 4.3.2 of [RFC9496]; Ne = 32.¶ - Deserialize
Element (buf ): - Implemented using the
Decodefunction from Section 4.3.1 of [RFC9496]. Additionally, this function validates that the resulting element is not the group identity element. If these checks fail, deserialization returns an InputValidation Error error.¶ - Serialize
Scalar (s ): - Implemented by outputting the little-endian, 32-byte encoding of the Scalar value with the top three bits set to zero; Ns = 32.¶
- Deserialize
Scalar (buf ): - Implemented by attempting to deserialize a Scalar from a
little-endian, 32-byte string. This function can fail if the input does not
represent a Scalar in the range [0,
G.Order()- 1]. Note that this means the top three bits of the input MUST be zero.¶
- Hash:
- SHA-512; Nh = 64.¶
4.2. OPRF(decaf448, SHAKE-256)
This ciphersuite uses decaf448 [RFC9496] for the Group and SHAKE-256 for the hash
function. The value of the ciphersuite identifier is "decaf448
- Group:
-
- Order():
- Return 2446 - 138180668098951
1535200738674851 5426880336692474 8821786098945475 03885 . ¶ - Identity():
- As defined in [RFC9496].¶
- Generator():
- As defined in [RFC9496].¶
- RandomScalar():
- Implemented by returning a uniformly random Scalar in the range
[0,
G.Order()- 1]. Refer to Section 4.7 for implementation guidance.¶ - HashToGroup():
- Use hash
_to _decaf448 [RFC9380] with DST = "HashToGroup-" || contextString and expand_message=expandusing SHAKE-256.¶_message _xof - HashToScalar():
- Compute
uniform_bytesusingexpand_message=expand, DST = "HashToScalar-" || contextString, and output length 64, interpret_message _xof uniform_bytesas a 512-bit integer in little-endian order, and reduce the integer moduloGroup.Order().¶ - Scalar
Inverse (s ): - Returns the multiplicative inverse of input Scalar
smodGroup.Order().¶ - Serialize
Element (A ): - Implemented using the
Encodefunction from Section 5.3.2 of [RFC9496]; Ne = 56.¶ - Deserialize
Element (buf ): - Implemented using the
Decodefunction from Section 5.3.1 of [RFC9496]. Additionally, this function validates that the resulting element is not the group identity element. If these checks fail, deserialization returns an InputValidation Error error.¶ - Serialize
Scalar (s ): - Implemented by outputting the little-endian, 56-byte encoding of the Scalar value; Ns = 56.¶
- Deserialize
Scalar (buf ): - Implemented by attempting to deserialize a Scalar from a
little-endian, 56-byte string. This function can fail if the input does not
represent a Scalar in the range [0,
G.Order()- 1].¶
- Hash:
- SHAKE-256; Nh = 64.¶
4.3. OPRF(P-256, SHA-256)
This ciphersuite uses P-256 [NISTCurves] for the Group and SHA-256 for the hash function. The value of the ciphersuite identifier is "P256-SHA256".¶
- Group:
-
P-256 (secp256r1) [NISTCurves]¶
- Order():
- Return 0xffffffff00000
000fffffffffffff fffbce6faada7179 e84f3b9cac2fc632 551 . ¶ - Identity():
- As defined in [NISTCurves].¶
- Generator():
- As defined in [NISTCurves].¶
- RandomScalar():
- Implemented by returning a uniformly random Scalar in the range
[0,
G.Order()- 1]. Refer to Section 4.7 for implementation guidance.¶ - HashToGroup():
- Use hash_to_curve with suite P256
_XMD :SHA -256 _SSWU _RO _ [RFC9380] and DST = "HashToGroup-" || contextString.¶ - HashToScalar():
- Use hash_to_field from [RFC9380]
using L = 48,
expandwith SHA-256, DST = "HashToScalar-" || contextString, and a prime modulus equal to_message _xmd Group.Order().¶ - Scalar
Inverse (s ): - Returns the multiplicative inverse of input Scalar
smodGroup.Order().¶ - Serialize
Element (A ): - Implemented using the compressed Elliptic
-Curve -Point -to -Octet -String method according to [SEC1]; Ne = 33.¶ - Deserialize
Element (buf ): - Implemented by attempting to deserialize a 33-byte input string to
a public key using the compressed Octet
-String -to -Elliptic -Curve -Point method according to [SEC1] and then performing partial public-key validation, as defined in Section 5.6.2.3.4 of [KEYAGREEMENT]. This includes checking that the coordinates of the resulting point are in the correct range, that the point is on the curve, and that the point is not the group identity element. If these checks fail, deserialization returns an Input Validation Error error.¶ - Serialize
Scalar (s ): - Implemented using the Field
-Element -to -Octet -String conversion according to [SEC1]; Ns = 32.¶ - Deserialize
Scalar (buf ): - Implemented by attempting to deserialize a Scalar from a 32-byte
string using Octet
-String -to -Field -Element from [SEC1]. This function can fail if the input does not represent a Scalar in the range [0, G.Order()- 1].¶
- Hash:
- SHA-256; Nh = 32.¶
4.4. OPRF(P-384, SHA-384)
This ciphersuite uses P-384 [NISTCurves] for the Group and SHA-384 for the hash function. The value of the ciphersuite identifier is "P384-SHA384".¶
- Group:
-
P-384 (secp384r1) [NISTCurves]¶
- Order():
- Return 0xfffffffffffff
ffffffffffffffff ffffffffffffffff fffc7634d81f4372 ddf581a0db248b0a 77aecec196accc52 973 . ¶ - Identity():
- As defined in [NISTCurves].¶
- Generator():
- As defined in [NISTCurves].¶
- RandomScalar():
- Implemented by returning a uniformly random Scalar in the range
[0,
G.Order()- 1]. Refer to Section 4.7 for implementation guidance.¶ - HashToGroup():
- Use hash_to_curve with suite P384
_XMD :SHA -384 _SSWU _RO _ [RFC9380] and DST = "HashToGroup-" || contextString.¶ - HashToScalar():
- Use hash_to_field from [RFC9380]
using L = 72,
expandwith SHA-384, DST = "HashToScalar-" || contextString, and a prime modulus equal to_message _xmd Group.Order().¶ - Scalar
Inverse (s ): - Returns the multiplicative inverse of input Scalar
smodGroup.Order().¶ - Serialize
Element (A ): - Implemented using the compressed Elliptic
-Curve -Point -to -Octet -String method according to [SEC1]; Ne = 49.¶ - Deserialize
Element (buf ): - Implemented by attempting to deserialize a 49-byte array to
a public key using the compressed Octet
-String -to -Elliptic -Curve -Point method according to [SEC1] and then performing partial public-key validation, as defined in Section 5.6.2.3.4 of [KEYAGREEMENT]. This includes checking that the coordinates of the resulting point are in the correct range, that the point is on the curve, and that the point is not the point at infinity. Additionally, this function validates that the resulting element is not the group identity element. If these checks fail, deserialization returns an Input Validation Error error.¶ - Serialize
Scalar (s ): - Implemented using the Field
-Element -to -Octet -String conversion according to [SEC1]; Ns = 48.¶ - Deserialize
Scalar (buf ): - Implemented by attempting to deserialize a Scalar from a 48-byte
string using Octet
-String -to -Field -Element from [SEC1]. This function can fail if the input does not represent a Scalar in the range [0, G.Order()- 1].¶
- Hash:
- SHA-384; Nh = 48.¶
4.5. OPRF(P-521, SHA-512)
This ciphersuite uses P-521 [NISTCurves] for the Group and SHA-512 for the hash function. The value of the ciphersuite identifier is "P521-SHA512".¶
- Group:
-
P-521 (secp521r1) [NISTCurves]¶
- Order():
- Return 0x01fffffffffff
ffffffffffffffff ffffffffffffffff ffffffffffffffff ffffffa51868783b f2f966b7fcc0148f 709a5d03bb5c9b88 99c47aebb6fb71e9 1386409 . ¶ - Identity():
- As defined in [NISTCurves].¶
- Generator():
- As defined in [NISTCurves].¶
- RandomScalar():
- Implemented by returning a uniformly random Scalar in the range
[0,
G.Order()- 1]. Refer to Section 4.7 for implementation guidance.¶ - HashToGroup():
- Use hash_to_curve with suite P521
_XMD :SHA -512 _SSWU _RO _ [RFC9380] and DST = "HashToGroup-" || contextString.¶ - HashToScalar():
- Use hash_to_field from [RFC9380]
using L = 98,
expandwith SHA-512, DST = "HashToScalar-" || contextString, and a prime modulus equal to_message _xmd Group.Order().¶ - Scalar
Inverse (s ): - Returns the multiplicative inverse of input Scalar
smodGroup.Order().¶ - Serialize
Element (A ): - Implemented using the compressed Elliptic
-Curve -Point -to -Octet -String method according to [SEC1]; Ne = 67.¶ - Deserialize
Element (buf ): - Implemented by attempting to deserialize a 67-byte input string to
a public key using the compressed Octet
-String -to -Elliptic -Curve -Point method according to [SEC1] and then performing partial public-key validation, as defined in Section 5.6.2.3.4 of [KEYAGREEMENT]. This includes checking that the coordinates of the resulting point are in the correct range, that the point is on the curve, and that the point is not the point at infinity. Additionally, this function validates that the resulting element is not the group identity element. If these checks fail, deserialization returns an Input Validation Error error.¶ - Serialize
Scalar (s ): - Implemented using the Field
-Element -to -Octet -String conversion according to [SEC1]; Ns = 66.¶ - Deserialize
Scalar (buf ): - Implemented by attempting to deserialize a Scalar from a 66-byte
string using Octet
-String -to -Field -Element from [SEC1]. This function can fail if the input does not represent a Scalar in the range [0, G.Order()- 1].¶
- Hash:
- SHA-512; Nh = 64.¶
4.6. Future Ciphersuites
A critical requirement of implementing the prime-order group using
elliptic curves is a method to instantiate the function
HashToGroup, which maps inputs to group elements. In the elliptic
curve setting, this deterministical
In the security proof of the construction, Hash is modeled as a random
oracle. This implies that any instantiation of HashToGroup must be
pre-image and collision resistant. In Section 4, we give
instantiations of this functionality based on the functions described in
[RFC9380]. Consequently, any OPRF implementation
must adhere to the implementation and security considerations discussed
in [RFC9380] when instantiating the function.¶
The Deserialize and Deserialize functions instantiated for a
particular prime-order group corresponding to a ciphersuite MUST adhere to
the description in Section 2.1. Future ciphersuites MUST describe how input
validation is done for Deserialize and Deserialize.¶
Additionally, future ciphersuites must take care when choosing the security level of the group. See Section 7.2.3 for additional details.¶
4.7. Random Scalar Generation
Two popular algorithms for generating a random integer uniformly distributed in the range [0, G.Order() - 1] are described in the following subsections.¶
4.7.1. Rejection Sampling
Generate a random byte array with Ns bytes and attempt to map to a Scalar
by calling Deserialize in constant time. If it succeeds, return the
result. If it fails, try again with another random byte array until the
procedure succeeds. Failure to implement Deserialize in constant time
can leak information about the underlying corresponding Scalar.¶
As an optimization, if the group order is very close to a power of
2, it is acceptable to omit the rejection test completely. In
particular, if the group order is p and there is an integer b
such that |p - 2b| is less than 2(b/2), then
RandomScalar can simply return a uniformly random integer of at
most b bits.¶
4.7.2. Random Number Generation Using Extra Random Bits
Generate a random byte array with L = ceil(((3 * ceil
bytes, and interpret it as an integer; reduce the integer modulo G.Order(), and return the
result. See [RFC9380], Section 5 for the underlying derivation of L.¶
5. Application Considerations
This section describes considerations for applications, including external interface
recommendations
5.1. Input Limits
Application inputs, expressed as PrivateInput or PublicInput values, MUST be smaller
than 216 - 1 bytes in length. Applications that require longer inputs can use a cryptographic
hash function to map these longer inputs to a fixed-length input that fits within the
PublicInput or PrivateInput length bounds. Note that some cryptographic hash functions
have input length restrictions themselves, but these limits are often large enough to
not be a concern in practice. For example, SHA-256 has an input limit of 261 bytes.¶
5.2. External Interface Recommendations
In Section 3.3, the interface of the protocol functions allows that some inputs
(and outputs) to be group Element and Scalar values. However, implementations can
instead operate over Element and Scalar values internally and only expose
interfaces that operate with an application
5.3. Error Considerations
Some OPRF variants specified in this document have fallible operations. For example, Finalize
and BlindEvaluate can fail if any element received from the peer fails input validation.
The explicit errors generated throughout this specification, along with the
conditions that lead to each error, are as follows:¶
-
VerifyError: - Verifiable OPRF proof verification failed (Sections 3.3.2 and 3.3.3).¶
-
DeserializeError: - Group Element or Scalar deserialization failure (Sections 2.1 and 3.3).¶
-
Input:Validation Error - Validation of byte array inputs failed (Section 4).¶
There are other explicit errors generated in this specification; however, they occur with negligible probability in practice. We note them here for completeness.¶
-
Invalid:Input Error - OPRF Blind input produces an invalid output element (Sections 3.3.1 and 3.3.3).¶
-
InverseError: - A tweaked private key is invalid, i.e., has no multiplicative inverse (Sections 2.1 and 3.3).¶
In general, the errors in this document are meant as a guide to implementors. They are not an exhaustive list of all the errors an implementation might emit. For example, implementations might run out of memory and return a corresponding error.¶
5.4. POPRF Public Input
Functionally, the VOPRF and POPRF variants differ in that the POPRF variant
admits public input, whereas the VOPRF variant does not. Public input allows
clients and servers to cryptographical
This public input is known to both parties at the start of the protocol. It is RECOMMENDED that this public input be constructed with some type of higher-level domain separation to avoid cross protocol attacks or related issues. For example, protocols using this construction might ensure that the public input uses a unique, prefix-free encoding. See [RFC9380], Section 10.4 for further discussion on constructing domain separation values.¶
Implementations of the POPRF may choose to not let applications control info in
cases where this value is fixed or otherwise not useful to the application. In this
case, the resulting protocol is functionally equivalent to the VOPRF, which does not
admit public input.¶
6. IANA Considerations
This document has no IANA actions.¶
7. Security Considerations
This section discusses the security of the protocols defined in this specification, along with some suggestions and trade-offs that arise from the implementation of the protocol variants in this document. Note that the syntax of the POPRF variant is different from that of the OPRF and VOPRF variants since it admits an additional public input, but the same security considerations apply.¶
7.1. Security Properties
The security properties of an OPRF protocol with functionality y = F(k, x) include those of a standard PRF. Specifically:¶
- Pseudorandomness
: - For a random sampling of k, F is pseudorandom if the output
y = F(k, x) on any input x is indistinguishab
le from uniformly sampling any element in F's range.¶
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 indistinguishab
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, so a pseudorandom function must
be nonmalleable to maintain indistinguishab
- Unconditional input secrecy:
- The server does not learn anything about the client input x, even with unbounded computation.¶
In other words, an attacker with infinite computing power cannot recover any information about the client's private input x from an invocation of the protocol.¶
Essentially, input secrecy is the property that, even if the server learns the client's private input x at some point in the future, the server cannot link any particular PRF evaluation to x. This property is also known as unlinkability [DGSTV18].¶
Beyond client input secrecy, in the OPRF protocol, the server learns nothing about the output y of the function, nor does the client learn anything about the server's private key k.¶
For the VOPRF and POPRF protocol variants, there is an additional security property:¶
- Verifiable:
- The client must only complete execution of the protocol if it can successfully assert that the output it computes is correct. This is taken with respect to the private key held by the server.¶
Any VOPRF or POPRF that satisfies the 'verifiable' security property is known as 'verifiable'. 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.¶
Finally, the POPRF variant also has the following security property:¶
- Partial obliviousness:
- The client and server must be able to perform the PRF on the client's private and public input. Both the client and server know the public input, but similar to the OPRF and VOPRF protocols, the server learns nothing about the client's private input or the output of the function, and the client learns nothing about the server's private key.¶
This property becomes useful when dealing with key management operations, such as the rotation of the server's keys. Note that partial obliviousness only applies to the POPRF variant because neither the OPRF nor VOPRF variants accept public input to the protocol.¶
Since the POPRF variant has a different syntax than the OPRF and VOPRF variants,
i.e., y = F(k, x, info), the pseudorandomnes
- Pseudorandomness
: - For a random sampling of k, F is pseudorandom if the output
y = F(k, x, info) on any input pairs (x, info) is indistinguishab
le from uniformly sampling any element in F's range.¶
7.2. Security Assumptions
Below, we discuss the cryptographic security of each protocol variant from Section 3, relative to the necessary cryptographic assumptions that need to be made.¶
7.2.1. OPRF and VOPRF Assumptions
The OPRF and VOPRF protocol variants in this document are based on [JKK14]. In particular, the VOPRF construction is similar to the [JKK14] construction with the following distinguishing properties:¶
The pseudorandomnes
7.2.2. POPRF Assumptions
The POPRF construction in this document is based on the construction known as 3HashSDHI, given by [TCRSTW21]. The construction is identical to 3HashSDHI, except that this design can optionally perform multiple POPRF evaluations in one batch, whilst only constructing one DLEQ proof object. This is enabled using an established batching technique [DGSTV18].¶
PseudorandomnessBlindEvaluate queries.
(The One-More Gap Computational Diffie-Hellman assumption was the hardness assumption used to
evaluate the OPRF and VOPRF designs based on [JKK14], which is a predecessor
to the POPRF variant in Section 3.3.3.)¶
7.2.3. Static Diffie-Hellman Attack and Security Limits
A side effect of the OPRF protocol variants in this document is that they allow
instantiation of an oracle for constructing static Diffie-Hellman (DH) samples; see [BG04] and [Cheon06].
These attacks are meant to recover (bits of) the server private key.
Best-known attacks reduce the security of the prime-order group instantiation by log_2(Q) / 2
bits, where Q is the number of BlindEvaluate calls made by the attacker.¶
As a result of this class of attacks, choosing prime-order groups with a 128-bit security
level instantiates an OPRF with a reduced security level of 128 - (log_2(Q) / 2) bits of security.
Moreover, such attacks are only possible for those certain applications where the
adversary can query the OPRF directly. Applications can mitigate against this problem
in a variety of ways, e.g., by rate-limiting client queries to BlindEvaluate or by
rotating private keys. In applications where such an oracle is not made available,
this security loss does not apply.¶
In most cases, it would require an informed and persistent attacker to
launch a highly expensive attack to reduce security to anything much
below 100 bits of security. Applications that admit the aforementioned
oracle functionality and that cannot tolerate discrete logarithm security
of lower than 128 bits are RECOMMENDED to choose groups that target a
higher security level, such as decaf448 (used by ciphersuite decaf448
7.3. Domain Separation
Applications SHOULD construct input to the protocol to provide domain separation. Any system that has multiple OPRF applications should distinguish client inputs to ensure the OPRF results are separate. Guidance for constructing info can be found in [RFC9380], Section 3.1.¶
7.4. Timing Leaks
To ensure no information is leaked during protocol execution, all
operations that use secret data MUST run in constant time. This includes
all prime-order group operations and proof-specific operations that
operate on secret data, including GenerateProof and BlindEvaluate.¶
8. References
8.1. Normative References
- [KEYAGREEMENT]
-
Barker, E., Chen, L., Roginsky, A., Vassilev, A., and R. Davis, "Recommendation for pair-wise key
-establishment , NIST SP 800-56A (Rev. 3), DOI 10schemes using discrete logarithm cryptography" .6028 , , <https:///nist .sp .800 -56ar3 doi >..org /10 .6028 /nist .sp .800 -56ar3 - [RFC2119]
-
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10
.17487 , , <https:///RFC2119 www >..rfc -editor .org /info /rfc2119 - [RFC8017]
-
Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2", RFC 8017, DOI 10
.17487 , , <https:///RFC8017 www >..rfc -editor .org /info /rfc8017 - [RFC8174]
-
Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10
.17487 , , <https:///RFC8174 www >..rfc -editor .org /info /rfc8174 - [RFC9380]
-
Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R. S., and C. A. Wood, "Hashing to Elliptic Curves", RFC 9380, DOI 10
.17487 , , <https:///RFC9380 www >..rfc -editor .org /info /rfc9380 - [RFC9496]
-
de Valence, H., Grigg, J., Hamburg, M., Lovecruft, I., Tankersley, G., and F. Valsorda, "The ristretto255 and decaf448 Groups", RFC 9496, DOI 10
.17487 , , <https:///RFC9496 www >..rfc -editor .org /info /rfc9496
8.2. Informative References
- [BG04]
-
Brown, D. and R. Gallant, "The Static Diffie-Hellman Problem", , <https://
eprint >..iacr .org /2004 /306 - [ChaumPedersen]
-
Chaum, D. and T. Pedersen, "Wallet Databases with Observers", Advances in Cryptology - CRYPTO' 92, pp. 89-105, DOI 10
.1007 , , <https:///3 -540 -48071 -4 _7 doi >..org /10 .1007 /3 -540 -48071 -4 _7 - [Cheon06]
-
Cheon, J., "Security Analysis of the Strong Diffie-Hellman Problem", Advances in Cryptology - EUROCRYPT 2006, pp. 1-11, DOI 10
.1007 , , <https:///11761679 _1 doi >..org /10 .1007 /11761679 _1 - [DGSTV18]
-
Davidson, A., Goldberg, I., Sullivan, N., Tankersley, G., and F. Valsorda, "Privacy Pass: Bypassing Internet Challenges Anonymously", Proceedings on Privacy Enhancing Technologies, vol. 2018, no. 3, pp. 164-180, DOI 10
.1515 , , <https:///popets -2018 -0026 doi >..org /10 .1515 /popets -2018 -0026 - [FS00]
-
Fiat, A. and A. Shamir, "How To Prove Yourself: Practical Solutions to Identification and Signature Problems", Advances in Cryptology - CRYPTO' 86, pp. 186-194, DOI 10
.1007 , , <https:///3 -540 -47721 -7 _12 doi >..org /10 .1007 /3 -540 -47721 -7 _12 - [JKK14]
-
Jarecki, S., Kiayias, A., and H. Krawczyk, "Round-Optimal Password
-Protected , Lecture Notes in Computer Science, pp. 233-253, DOI 10Secret Sharing and T-PAKE in the Password-Only Model" .1007 , , <https:///978 -3 -662 -45608 -8 _13 doi >..org /10 .1007 /978 -3 -662 -45608 -8 _13 - [JKKX16]
-
Jarecki, S., Kiayias, A., Krawczyk, H., and J. Xu, "Highly
-Efficient , 2016 IEEE European Symposium on Security and Privacy (EuroS&P), DOI 10and Composable Password -Protected Secret Sharing (Or: How to Protect Your Bitcoin Wallet Online)" .1109 , , <https:///eurosp .2016 .30 doi >..org /10 .1109 /eurosp .2016 .30 - [NISTCurves]
-
National Institute of Standards and Technology (NIST), "Digital Signature Standard (DSS)", FIPS PUB 186-5, DOI 10
.6028 , , <https:///NIST .FIPS .186 -5 doi >..org /10 .6028 /NIST .FIPS .186 -5 - [OPAQUE]
-
Bourdrez, D., Krawczyk, H., Lewi, K., and C. A. Wood, "The OPAQUE Asymmetric PAKE Protocol", Work in Progress, Internet-Draft, draft
-irtf , , <https://-cfrg -opaque -13 datatracker >..ietf .org /doc /html /draft -irtf -cfrg -opaque -13 - [PRIVACY-PASS]
-
Celi, S., Davidson, A., Valdez, S., and C. A. Wood, "Privacy Pass Issuance Protocol", Work in Progress, Internet-Draft, draft
-ietf , , <https://-privacypass -protocol -16 datatracker >..ietf .org /doc /html /draft -ietf -privacypass -protocol -16 - [PrivacyPass]
-
"Privacy Pass", commit 085380a, , <https://
github >..com /privacypass /team - [RFC7748]
-
Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves for Security", RFC 7748, DOI 10
.17487 , , <https:///RFC7748 www >..rfc -editor .org /info /rfc7748 - [SEC1]
-
Standards for Efficient Cryptography Group (SECG), "SEC 1: Elliptic Curve Cryptography", , <https://
www >..secg .org /sec1 -v2 .pdf - [SJKS17]
-
Shirvanian, M., Jarecki, S., Krawczyk, H., and N. Saxena, "SPHINX: A Password Store that Perfectly Hides Passwords from Itself", 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS), DOI 10
.1109 , , <https:///ICDCS .2017 .64 doi >..org /10 .1109 /ICDCS .2017 .64 - [TCRSTW21]
-
Tyagi, N., Celi, S., Ristenpart, T., Sullivan, N., Tessaro, S., and C. A. Wood, "A Fast and Simple Partially Oblivious PRF, with Applications", Advances in Cryptology - EUROCRYPT 2022 pp. 674-705, DOI 10
.1007 , , <https:///978 -3 -031 -07085 -3 _23 doi >..org /10 .1007 /978 -3 -031 -07085 -3 _23
Appendix A. Test Vectors
This section includes test vectors for the protocol variants specified in this document. For each ciphersuite specified in Section 4, there is a set of test vectors for the protocol when running the OPRF, VOPRF, and POPRF modes. Each test vector lists the batch size for the evaluation. Each test vector value is encoded as a hexadecimal byte string. The fields of each test vector are described below.¶
- "Input":
- The private client input, an opaque byte string.¶
- "Info":
- The public info, an opaque byte string. Only present for POPRF test vectors.¶
- "Blind":
- The blind value output by
Blind(), a serialized Scalar ofNsbytes long.¶ - "Blinded
Element" : - The blinded value output by
Blind(), a serialized Element ofNebytes long.¶ - "Evaluated
Element" : - The evaluated element output by
BlindEvaluate(), a serialized Element ofNebytes long.¶ - "Proof":
- The serialized
Proofoutput fromGenerateProof()composed of two serialized Scalar values, eachNsbytes long. Only present for VOPRF and POPRF test vectors.¶ - "Proof
Random Scalar" : - The random Scalar
rcomputed inGenerateProof(), a serialized Scalar ofNsbytes long. Only present for VOPRF and POPRF test vectors.¶ - "Output":
- The protocol output, an opaque byte string of
Nhbytes long.¶
Test vectors with batch size B > 1 have inputs separated by a comma
",". Applicable test vectors will have B different values for the
"Input", "Blind", "Blinded
The server key material, pkSm and skSm, are listed under the mode for
each ciphersuite. Both pkSm and skSm are the serialized values of
pkS and skS, respectively, as used in the protocol. Each key pair
is derived from a seed, denoted Seed, and info string, denoted KeyInfo, which are
listed as well, using the DeriveKeyPair function from Section 3.2.¶
Acknowledgements
This document resulted from the work of the Privacy Pass team [PrivacyPass]. The authors would also like to acknowledge helpful conversations with Hugo Krawczyk. Eli-Shaoul Khedouri provided additional review and comments on key consistency. Daniel Bourdrez, Tatiana Bradley, Sofia Celi, Frank Denis, Julia Hesse, Russ Housley, Kevin Lewi, Christopher Patton, and Bas Westerbaan also provided helpful input and contributions to the document.¶