< draft-sullivan-cfrg-voprf-02.txt   draft-sullivan-cfrg-voprf-03.txt >
Network Working Group A. Davidson Network Working Group A. Davidson
Internet-Draft ISG, Royal Holloway, University of London Internet-Draft N. Sullivan
Intended status: Informational N. Sullivan Intended status: Informational Cloudflare
Expires: April 25, 2019 Cloudflare Expires: September 12, 2019 C. Wood
C. Wood
Apple Inc. Apple Inc.
October 22, 2018 March 11, 2019
Verifiable Oblivious Pseudorandom Functions (VOPRFs) in Prime-Order Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups
Groups draft-sullivan-cfrg-voprf-03
draft-sullivan-cfrg-voprf-02
Abstract Abstract
A Verifiable Oblivious Pseudorandom Function (VOPRF) is a two-party An Oblivious Pseudorandom Function (OPRF) is a two-party protocol for
protocol for computing the output of a PRF that is symmetrically computing the output of a PRF. One party (the server) holds the PRF
verifiable. In summary, the PRF key holder learns nothing of the secret key, and the other (the client) holds the PRF input. The
input while simultaneously providing proof that its private key was 'obliviousness' property ensures that the server does not learn
used during execution. VOPRFs are useful for computing one-time anything about the client's input during the evaluation. The client
unlinkable tokens that are verifiable by secret key holders. This should also not learn anything about the server's secret PRF key.
document specifies a VOPRF construction instantiated within prime- Optionally, OPRFs can also satisfy a notion 'verifiability' (VOPRF).
order subgroups, including elliptic curves. In this setting, the client can verify that the server's output is
indeed the result of evaluating the underlying PRF with just a public
key. This document specifies OPRF and VOPRF constructions
instantiated within prime-order groups, including elliptic curves.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 25, 2019. This Internet-Draft will expire on September 12, 2019.
Copyright Notice Copyright Notice
Copyright (c) 2018 IETF Trust and the persons identified as the Copyright (c) 2019 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4
1.2. Requirements . . . . . . . . . . . . . . . . . . . . . . 4 1.2. Requirements . . . . . . . . . . . . . . . . . . . . . . 5
2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Background . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Security Properties . . . . . . . . . . . . . . . . . . . . . 4 3. Security Properties . . . . . . . . . . . . . . . . . . . . . 6
4. VOPRF Protocol . . . . . . . . . . . . . . . . . . . . . . . 5 4. OPRF Protocol . . . . . . . . . . . . . . . . . . . . . . . . 6
4.1. Instantiations of GG . . . . . . . . . . . . . . . . . . 6 4.1. Protocol correctness . . . . . . . . . . . . . . . . . . 8
4.2. Algorithmic Details . . . . . . . . . . . . . . . . . . . 7 4.2. Instantiations of GG . . . . . . . . . . . . . . . . . . 8
4.2.1. VOPRF_Blind . . . . . . . . . . . . . . . . . . . . . 7 4.3. OPRF algorithms . . . . . . . . . . . . . . . . . . . . . 9
4.2.2. VOPRF_Sign . . . . . . . . . . . . . . . . . . . . . 8 4.3.1. OPRF_Setup . . . . . . . . . . . . . . . . . . . . . 9
4.2.3. VOPRF_Unblind . . . . . . . . . . . . . . . . . . . . 8 4.3.2. OPRF_Blind . . . . . . . . . . . . . . . . . . . . . 10
4.2.4. VOPRF_Finalize . . . . . . . . . . . . . . . . . . . 8 4.3.3. OPRF_Sign . . . . . . . . . . . . . . . . . . . . . . 10
5. NIZK Discrete Logarithm Equality Proof . . . . . . . . . . . 9 4.3.4. OPRF_Unblind . . . . . . . . . . . . . . . . . . . . 11
5.1. DLEQ_Generate . . . . . . . . . . . . . . . . . . . . . . 9 4.3.5. OPRF_Finalize . . . . . . . . . . . . . . . . . . . . 11
5.2. DLEQ_Verify . . . . . . . . . . . . . . . . . . . . . . . 10 4.4. VOPRF algorithms . . . . . . . . . . . . . . . . . . . . 11
5.3. Elliptic Curve Group and Hash Function Instantiations . . 10 4.4.1. VOPRF_Setup . . . . . . . . . . . . . . . . . . . . . 12
6. Security Considerations . . . . . . . . . . . . . . . . . . . 12 4.4.2. VOPRF_Blind . . . . . . . . . . . . . . . . . . . . . 12
6.1. Timing Leaks . . . . . . . . . . . . . . . . . . . . . . 13 4.4.3. VOPRF_Sign . . . . . . . . . . . . . . . . . . . . . 13
6.2. Hashing to curves . . . . . . . . . . . . . . . . . . . . 13 4.4.4. VOPRF_Unblind . . . . . . . . . . . . . . . . . . . . 13
7. Privacy Considerations . . . . . . . . . . . . . . . . . . . 13 4.4.5. VOPRF_Finalize . . . . . . . . . . . . . . . . . . . 13
7.1. Key Consistency . . . . . . . . . . . . . . . . . . . . . 13 4.5. Utility algorithms . . . . . . . . . . . . . . . . . . . 14
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 13 4.5.1. bin2scalar . . . . . . . . . . . . . . . . . . . . . 14
9. Normative References . . . . . . . . . . . . . . . . . . . . 13 4.6. Efficiency gains with pre-processing and additive
Appendix A. Test Vectors . . . . . . . . . . . . . . . . . . . . 15 blinding . . . . . . . . . . . . . . . . . . . . . . . . 14
Appendix B. Applications . . . . . . . . . . . . . . . . . . . . 17 4.6.1. OPRF_Preprocess . . . . . . . . . . . . . . . . . . . 15
B.1. Privacy Pass . . . . . . . . . . . . . . . . . . . . . . 17 4.6.2. OPRF_Blind . . . . . . . . . . . . . . . . . . . . . 15
B.2. Private Password Checker . . . . . . . . . . . . . . . . 18 4.6.3. OPRF_Unblind . . . . . . . . . . . . . . . . . . . . 16
B.2.1. Parameter Commitments . . . . . . . . . . . . . . . . 18 5. NIZK Discrete Logarithm Equality Proof . . . . . . . . . . . 16
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 18 5.1. DLEQ_Generate . . . . . . . . . . . . . . . . . . . . . . 16
5.2. DLEQ_Verify . . . . . . . . . . . . . . . . . . . . . . . 17
6. Batched VOPRF evaluation . . . . . . . . . . . . . . . . . . 17
6.1. Batched DLEQ algorithms . . . . . . . . . . . . . . . . . 18
6.1.1. Batched_DLEQ_Generate . . . . . . . . . . . . . . . . 18
6.1.2. Batched_DLEQ_Verify . . . . . . . . . . . . . . . . . 19
6.2. Modified protocol execution . . . . . . . . . . . . . . . 20
6.3. PRNG and resampling . . . . . . . . . . . . . . . . . . . 20
7. Supported ciphersuites . . . . . . . . . . . . . . . . . . . 20
7.1. ECVOPRF-P256-HKDF-SHA256-SSWU: . . . . . . . . . . . . . 20
7.2. ECVOPRF-RISTRETTO-HKDF-SHA512-Elligator2: . . . . . . . . 21
8. Security Considerations . . . . . . . . . . . . . . . . . . . 21
8.1. Timing Leaks . . . . . . . . . . . . . . . . . . . . . . 21
8.2. Hashing to curves . . . . . . . . . . . . . . . . . . . . 22
8.3. Verifiability (key consistency) . . . . . . . . . . . . . 22
9. Applications . . . . . . . . . . . . . . . . . . . . . . . . 22
9.1. Privacy Pass . . . . . . . . . . . . . . . . . . . . . . 22
9.2. Private Password Checker . . . . . . . . . . . . . . . . 23
9.2.1. Parameter Commitments . . . . . . . . . . . . . . . . 23
10. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 23
11. Normative References . . . . . . . . . . . . . . . . . . . . 23
Appendix A. Test Vectors . . . . . . . . . . . . . . . . . . . . 25
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 27
1. Introduction 1. Introduction
A pseudorandom function (PRF) F(k, x) is an efficiently computable A pseudorandom function (PRF) F(k, x) is an efficiently computable
function with secret key k on input x. Roughly, F is pseudorandom if function with secret key k on input x. Roughly, F is pseudorandom if
the output y = F(k, x) is indistinguishable from uniformly sampling the output y = F(k, x) is indistinguishable from uniformly sampling
any element in F's range for random choice of k. An oblivious PRF any element in F's range for random choice of k. An oblivious PRF
(OPRF) is a two-party protocol between a prover P and verifier V (OPRF) is a two-party protocol between a prover P and verifier V
where P holds a PRF key k and V holds some input x. The protocol where P holds a PRF key k and V holds some input x. The protocol
allows both parties to cooperate in computing F(k, x) with P's secret allows both parties to cooperate in computing F(k, x) with P's secret
key k and V's input x such that: V learns F(k, x) without learning key k and V's input x such that: V learns F(k, x) without learning
anything about k; and P does not learn anything about x. A anything about k; and P does not learn anything about x. A
Verifiable OPRF (VOPRF) is an OPRF wherein P can prove to V that F(k, Verifiable OPRF (VOPRF) is an OPRF wherein P can prove to V that F(k,
x) was computed using key k, which is bound to a trusted public key Y x) was computed using key k, which is bound to a trusted public key Y
= kG. Informally, this is done by presenting a non-interactive zero- = kG. Informally, this is done by presenting a non-interactive zero-
knowledge (NIZK) proof of equality between (G, Y) and (Z, M), where Z knowledge (NIZK) proof of equality between (G, Y) and (Z, M), where Z
= kM for some point M. = kM for some point M.
VOPRFs are useful for producing tokens that are verifiable by V. OPRFs have been shown to be useful for constructing: password-
This may be needed, for example, if V wants assurance that P did not protected secret sharing schemes [JKK14]; privacy-preserving password
use a unique key in its computation, i.e., if V wants key consistency stores [SJKS17]; and password-authenticated key exchange or PAKE
from P. This property is necessary in some applications, e.g., the [OPAQUE]. VOPRFs are useful for producing tokens that are verifiable
Privacy Pass protocol [PrivacyPass], wherein this VOPRF is used to by V. This may be needed, for example, if V wants assurance that P
generate one-time authentication tokens to bypass CAPTCHA challenges. did not use a unique key in its computation, i.e., if V wants key
consistency from P. This property is necessary in some applications,
e.g., the Privacy Pass protocol [PrivacyPass], wherein this VOPRF is
used to generate one-time authentication tokens to bypass CAPTCHA
challenges. VOPRFs have also been used for password-protected secret
sharing schemes e.g. [JKKX16].
This document introduces a VOPRF protocol built in prime-order This document introduces an OPRF protocol built in prime-order
groups. This applies to finite fields of prime-order and also groups, applying to finite fields of prime-order and also elliptic
elliptic curve (EC) settings. In the EC setting, we will refer to curve (EC) settings. The protocol has the option of being extended
the protocol as ECVOPRF. The document describes the protocol, its to a VOPRF with the addition of a NIZK proof for proving discrete log
security properties, and provides preliminary test vectors for equality relations. This proof demonstrates correctness of the
experimentation. This rest of document is structured as follows: computation using a known public key that serves as a commitment to
the server's secret key. In the EC setting, we will refer to the
protocol as ECOPRF (or ECVOPRF if verifiability is concerned). The
document describes the protocol, its security properties, and
provides preliminary test vectors for experimentation. The rest of
the document is structured as follows:
o Section Section 2: Describe background, related work, and use o Section Section 2: Describe background, related work, and use
cases of VOPRF protocols. cases of OPRF/VOPRF protocols.
o Section Section 3: Discuss security properties of VOPRFs. o Section Section 3: Discuss security properties of OPRFs/VOPRFs.
o Section Section 4: Specify a VOPRF protocol based in prime-order o Section Section 4: Specify an authentication protocol from OPRF
groups. functionality, based in prime-order groups (with an optional
verifiable mode). Algorithms are stated formally for OPRFs in
Section 4.3 and for VOPRFs in Section 4.4.
o Section Section 5: Specify the NIZK discrete logarithm equality o Section Section 5: Specify the NIZK discrete logarithm equality
construction used for verifying protocol outputs. (DLEQ) construction used for constructing the VOPRF protocol.
o Section Section 6: Specifies how the DLEQ proof mechanism can be
batched for multiple VOPRF invocations, and how this changes the
protocol execution.
o Section Section 7: Considers explicit instantiations of the
protocol in the elliptic curve setting.
o Section Section 8: Discusses the security considerations for the
OPRF and VOPRF protocol.
o Section Section 9: Discusses some existing applications of OPRF
and VOPRF protocols.
o Section Appendix A: Specifies test vectors for implementations in
the elliptic curve setting.
1.1. Terminology 1.1. Terminology
The following terms are used throughout this document. The following terms are used throughout this document.
o PRF: Pseudorandom Function. o PRF: Pseudorandom Function.
o OPRF: Oblivious PRF. o OPRF: Oblivious PRF.
o VOPRF: Verifiable Oblivious Pseudorandom Function. o VOPRF: Verifiable Oblivious Pseudorandom Function.
skipping to change at page 4, line 19 skipping to change at page 5, line 23
o DLEQ: Discrete Logarithm Equality. o DLEQ: Discrete Logarithm Equality.
1.2. Requirements 1.2. Requirements
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119]. document are to be interpreted as described in [RFC2119].
2. Background 2. Background
VOPRFs are functionally related to RSA-based blind signature schemes, OPRFs are functionally related to RSA-based blind signature schemes,
e.g., [ChaumBlindSignature]. Such a scheme works as follows. Let m e.g., [ChaumBlindSignature]. Briefly, a blind signature scheme works
be a message to be signed by a server. It is assumed to be a member as follows. Let m be a message to be signed by a server. It is
of the RSA group. Also, let N be the RSA modulus, and e and d be the assumed to be a member of the RSA group. Also, let N be the RSA
public and private keys, respectively. A prover P and verifier V modulus, and e and d be the public and private keys, respectively. A
engage in the following protocol given input m. prover P and verifier V engage in the following protocol given input
m.
1. V generates a random blinding element r from the RSA group, and 1. V generates a random blinding element r from the RSA group, and
compute m' = m^r (mod N). Send m' to the P. compute m' = m^r (mod N). Send m' to the P.
2. P uses m' to compute s' = (m')^d (mod N), and sends s' to the V. 2. P uses m' to compute s' = (m')^d (mod N), and sends s' to the V.
3. V removes the blinding factor r to obtain the original signature 3. V removes the blinding factor r to obtain the original signature
as s = (s')^(r^-1) (mod N). as s = (s')^(r^-1) (mod N).
By the properties of RSA, s is clearly a valid signature for m. OPRF By the properties of RSA, s is clearly a valid signature for m. OPRF
protocols are the symmetric equivalent to blind signatures in the protocols can be used to provide a symmetric equivalent to blind
same way that PRFs are the symmetric equivalent traditional digital signatures. Essentially the client learns y = PRF(k,x) for some
signatures. This is discussed more in the following section. input x of their choice, from a server that holds k. Since the
security of an OPRF means that x is hidden in the interaction, then
the client can later reveal x to the server along with y.
The server can verify that y is computed correctly by recomputing the
PRF on x using k. In doing so, the client provides knowledge of a
'signature' y for their value x. However, the verification procedure
is symmetric since it requires knowledge of k. This is discussed
more in the following section.
3. Security Properties 3. Security Properties
The security properties of a VOPRF protocol with functionality y = The security properties of an OPRF protocol with functionality y =
F(k, x) include those of a standard PRF. Specifically: F(k, x) include those of a standard PRF. Specifically:
o Given value x, it is infeasible to compute y = F(k, x) without o Given value x, it is infeasible to compute y = F(k, x) without
knowledge of k. knowledge of k.
o Output y = F(k, x) is indistinguishable from a random value in the o The output distribution of y = F(k, x) is indistinguishable from
domain of F. the uniform distribution in the domain of the function F.
Additionally, we require the following additional properties: Additionally, we require the following additional properties:
o Non-malleable: Given (x, y = F(k, x)), V must not be able to o Non-malleable: Given (x, y = F(k, x)), V must not be able to
generate (x', y') where x' != x and y' = F(k, x'). generate (x', y') where x' != x and y' = F(k, x').
o Verifiable: V must only complete execution of the protocol if it
asserts that P used its secret key k, associated with public key Y
= kG, in execution.
o Oblivious: P must learn nothing about V's input, and V must learn o Oblivious: P must learn nothing about V's input, and V must learn
nothing about P's private key. nothing about P's private key.
o Unlinkable: If V reveals x to P, P cannot link x to the protocol o Unlinkable: If V reveals x to P, P cannot link x to the protocol
instance in which y = F(k, x) was computed. instance in which y = F(k, x) was computed.
4. VOPRF Protocol Optionally, for any protocol that satisfies the above properties,
there is an additional security property:
In this section we describe the VOPRF protocol. Let GG be a prime- o Verifiable: V must only complete execution of the protocol if it
can successfully assert that P used its secret key k.
In practice, the notion of verifiability requires that P commits to
the key k before the actual protocol execution takes place. Then V
verifies that P has used k in the protocol using this commitment.
4. OPRF Protocol
In this section we describe the OPRF protocol. Let GG be a prime-
order additive subgroup, with two distinct hash functions H_1 and order additive subgroup, with two distinct hash functions H_1 and
H_2, where H_1 maps arbitrary input onto GG and H_2 maps arbitrary H_2, where H_1 maps arbitrary input onto GG and H_2 maps arbitrary
input to a fixed-length output, e.g., SHA256. All hash functions in input to a fixed-length output, e.g., SHA256. All hash functions in
the protocol are assumed to be random oracles. Let L be the security the protocol are modelled as random oracles. Let L be the security
parameter. Let k be the prover's (P) secret key, and Y = kG be its parameter. Let k be the prover's (P) secret key, and Y = kG be its
corresponding public key for some generator G taken from the group corresponding 'public key' for some generator G taken from the group
GG. Let x be the verifier's (V) input to the VOPRF protocol. GG. This public key is also referred to as a commitment to the key
k. Let x be the verifier's (V) input to the OPRF protocol.
(Commonly, it is a random L-bit string, though this is not required.) (Commonly, it is a random L-bit string, though this is not required.)
VOPRF begins with V randomly blinding its input for the signer. The
latter then applies its secret key to the blinded value and returns The OPRF protocol begins with V blinding its input for the signer
the result. To finish the computation, V then removes its blind and such that it appears uniformly distributed GG. The latter then
hashes the result using H_2 to yield an output. This flow is applies its secret key to the blinded value and returns the result.
illustrated below.
To finish the computation, V then removes its blind and hashes the
result using H_2 to yield an output. This flow is illustrated below.
Verifier Prover Verifier Prover
------------------------------------ ------------------------------------
r <-$ GG r <-$ GG
M = rH_1(x) M = rH_1(x)
M M
-------> ------->
Z = kM Z = kM
D = DLEQ_Generate(G,Y,M,Z) [D = DLEQ_Generate(k,G,Y,M,Z)]
Z,D Z[,D]
<------- <-------
b = DLEQ_Verify(G,Y,M,Z,D) [b = DLEQ_Verify(G,Y,M,Z,D)]
Output H_2(x, Zr^(-1)) if b=1, else "error" N = Zr^(-1)
Output H_2(x, N) [if b=1, else "error"]
DLEQ_Generate(G,Y,M,Z) and DLEQ_Verify(G,Y,M,Z,D) are described in Steps that are enclosed in square brackets (DLEQ_Generate and
Section Section 5. Intuitively, the DLEQ proof allows P to prove to DLEQ_Verify) are optional for achieving verifiability. These are
V in NIZK that the same key k is the exponent of both Y and M. In described in Section Section 5. In the verifiable mode, we assume
other words, computing the discrete logarithm of Y and Z (with that P has previously committed to their choice of key k with some
respect to G and M, respectively) results in the same value. The values (G,Y=kG) and these are publicly known by V. Notice that
committed value Y should be public before the protocol is initiated. revealing (G,Y) does not reveal k by the well-known hardness of the
discrete log problem.
The actual PRF function computed is as follows: Strictly speaking, the actual PRF function that is computed is:
F(k, x) = H_2(x, N) = H_2(x, kH_1(x)) F(k, x) = N = kH_1(x)
Note that V finishes this computation upon receiving kH_1(x) from P. It is clear that this is a PRF H_1(x) maps x to a random element in
The output from P is not the PRF value. GG, and GG is cyclic. This output is computed when the client
computes Zr^(-1) by the commutativity of the multiplication. The
client finishes the computation by outputting H_2(x,N). Note that
the output from P is not the PRF value because the actual input x is
blinded by r.
This protocol may be decomposed into a series of steps, as described This protocol may be decomposed into a series of steps, as described
below: below:
o VOPRF_Blind(x): Compute and return a blind, r, and blinded o OPRF_Setup(l): Generate am integer k of sufficient bit-length l
representation of x, denoted M. and output k.
o VOPRF_Sign(M): Sign input M using secret key k to produce Z, o OPRF_Blind(x): Compute and return a blind, r, and blinded
generate a proof D = DLEQ_Generate(G,Y,M,Z), and output (Z, D). representation of x in GG, denoted M.
o VOPRF_Unblind((Z, D), r, Y, G, M): Unblind blinded signature Z o OPRF_Sign(k,M,h): Sign input M using secret key k to produce Z,
with blind r, yielding N. Output N if 1 = DLEQ_Verify(G,Y,M,Z,D). the input h is optional and equal to the cofactor of an elliptic
curve. If h is not provided then it defaults to 1.
o OPRF_Unblind(r,Z): Unblind blinded signature Z with blind r,
yielding N and output N.
o OPRF_Finalize(x,N): Finalize N to produce the output H_2(x, N).
For verifiability we modify the algorithms of VOPRF_Setup, VOPRF_Sign
and VOPRF_Unblind to be the following:
o VOPRF_Setup(l): Generate an integer k of sufficient bit-length l
and output (k, (G,Y)) where Y = kG for some generator G in GG.
o VOPRF_Sign(k,(G,Y),M,h): Sign input M using secret key k to
produce Z. Generate a NIZK proof D = DLEQ_Generate(k,G,Y,M,Z),
and output (Z, D). The optional cofactor h can also be provided
as in OPRF_Sign.
o VOPRF_Unblind(r,G,Y,M,(Z,D)): Unblind blinded signature Z with
blind r, yielding N. Output N if 1 = DLEQ_Verify(G,Y,M,Z,D).
Otherwise, output "error". Otherwise, output "error".
o VOPRF_Finalize(N): Finalize N to produce PRF output F(k, x). We leave the rest of the OPRF algorithms unmodified. When referring
explicitly to VOPRF execution, we replace 'OPRF' in all method names
with 'VOPRF'.
4.1. Protocol correctness
Protocol correctness requires that, for any key k, input x, and (r, Protocol correctness requires that, for any key k, input x, and (r,
M) = VOPRF_Blind(x), it must be true that: M) = OPRF_Blind(x), it must be true that:
VOPRF_Finalize(x, VOPRF_Unblind(VOPRF_Sign(M), M, r)) = F(k, x) OPRF_Finalize(x, OPRF_Unblind(r,M,OPRF_Sign(k,M))) = H_2(x, F(k,x))
with overwhelming probability. with overwhelming probability. Likewise, in the verifiable setting,
we require that:
4.1. Instantiations of GG VOPRF_Finalize(x, VOPRF_Unblind(r,(G,Y),M,(VOPRF_Sign(k,(G,Y),M)))) = H_2(x, F(k,x))
with overwhelming probability, where (r, M) = VOPRF_Blind(x).
4.2. Instantiations of GG
As we remarked above, GG is a subgroup with associated prime-order p. As we remarked above, GG is a subgroup with associated prime-order p.
While we choose to write operations in the setting where GG comes While we choose to write operations in the setting where GG comes
equipped with an additive operation, we could also define the equipped with an additive operation, we could also define the
operations in the multiplicative setting. In the multiplicative operations in the multiplicative setting. In the multiplicative
setting we can choose GG to be a prime-order subgroup of a finite setting we can choose GG to be a prime-order subgroup of a finite
field FF_p. For example, let p be some large prime (e.g. > 2048 field FF_p. For example, let p be some large prime (e.g. > 2048
bits) where p = 2q+1 for some other prime q. Then the subgroup of bits) where p = 2q+1 for some other prime q. Then the subgroup of
squares of FF_p (elements u^2 where u is an element of FF_p) is squares of FF_p (elements u^2 where u is an element of FF_p) is
cyclic, and we can pick a generator of this subgroup by picking g cyclic, and we can pick a generator of this subgroup by picking g
from FF_p (ignoring the identity element). from FF_p (ignoring the identity element).
In this document, however, we are going to focus on the cases where For practicality of the protocol, it is preferable to focus on the
GG is indeed an additive subgroup. In the elliptic curve setting, cases where GG is an additive subgroup so that we can instantiate the
this amounts to choosing GG to be a prime-order subgroup of an OPRF in the elliptic curve setting. This amounts to choosing GG to
elliptic curve over base field GF(p) for prime p. There are also be a prime-order subgroup of an elliptic curve over base field GF(p)
other settings where GG is a prime-order subgroup of an elliptic for prime p. There are also other settings where GG is a prime-order
curve over a base field of non-prime order, these include the work of subgroup of an elliptic curve over a base field of non-prime order,
Ristretto [RISTRETTO] and Decaf [DECAF]. these include the work of Ristretto [RISTRETTO] and Decaf [DECAF].
We will use p > 0 generally for constructing the base field GF(p), We will use p > 0 generally for constructing the base field GF(p),
not just those where p is prime. To reiterate, we focus only on the not just those where p is prime. To reiterate, we focus only on the
additive case, and so we focus only on the cases where GF(p) is additive case, and so we focus only on the cases where GF(p) is
indeed the base field. indeed the base field.
4.2. Algorithmic Details 4.3. OPRF algorithms
This section provides algorithms for each step in the VOPRF protocol. This section provides algorithms for each step in the OPRF protocol.
We describe the VOPRF analogues in Section 4.4. We provide generic
utility algorithms in Section 4.5.
1. V computes X = H_1(x) and a random element r (blinding factor) 1. P samples a uniformly random key k <- {0,1}^l for sufficient
length l, and interprets it as an integer.
2. V computes X = H_1(x) and a random element r (blinding factor)
from GF(p), and computes M = rX. from GF(p), and computes M = rX.
2. V sends M to P. 3. V sends M to P.
3. P computes Z = kM = rkX, and D = DLEQ_Generate(G,Y,M,Z). 4. P computes Z = kM = rkX.
4. P sends (Z, D) to V. 5. In the elliptic curve setting, P multiplies Z by the cofactor
(denoted h) of the elliptic curve.
5. V ensures that 1 = DLEQ_Verify(G,Y,M,Z,D). If not, V outputs an 6. P sends Z to V.
7. V unblinds Z to compute N = r^(-1)Z = kX.
8. V outputs the pair H_2(x, N).
4.3.1. OPRF_Setup
Input:
l: Some suitable choice of key-length (e.g. as described in {{NIST}}).
Output:
k: A key chosen from {0,1}^l and interpreted as an integer value.
Steps:
1. Sample k_bin <-$ {0,1}^l
2. Output k <- bin2scalar(k_bin, l)
4.3.2. OPRF_Blind
Input:
x: V's PRF input.
Output:
r: Random scalar in [1, p - 1].
M: Blinded representation of x using blind r, an element in GG.
Steps:
1. r <-$ GF(p)
2. M := rH_1(x)
3. Output (r, M)
4.3.3. OPRF_Sign
Input:
k: Signer secret key.
M: An element in GG.
h: optional cofactor (defaults to 1).
Output:
Z: Scalar multiplication of the point M by k, element in GG.
Steps:
1. Z := kM
2. Z <- hZ
3. Output Z
4.3.4. OPRF_Unblind
Input:
r: Random scalar in [1, p - 1].
Z: An element in GG.
Output:
N: Unblinded signature, element in GG.
Steps:
1. N := (1/r)Z
2. Output N
4.3.5. OPRF_Finalize
Input:
x: PRF input string.
N: An element in GG.
Output:
y: Random element in {0,1}^L.
Steps:
1. y := H_2(x, N)
2. Output y
4.4. VOPRF algorithms
The steps in the VOPRF setting are written as:
1. P samples a uniformly random key k <- {0,1}^l for sufficient
length l, and interprets it as an integer.
2. P commits to k by computing (G,Y) for Y=kG and where G is a
generator of GG. P makes (G,Y) publicly available.
3. V computes X = H_1(x) and a random element r (blinding factor)
from GF(p), and computes M = rX.
4. V sends M to P.
5. P computes Z = kM = rkX, and D = DLEQ_Generate(k,G,Y,M,Z).
6. P sends (Z, D) to V.
7. V ensures that 1 = DLEQ_Verify(G,Y,M,Z,D). If not, V outputs an
error. error.
6. V unblinds Z to compute N = r^(-1)Z = kX. 8. V unblinds Z to compute N = r^(-1)Z = kX.
7. V outputs the pair H_2(x, N). 9. V outputs the pair H_2(x, N).
4.2.1. VOPRF_Blind 4.4.1. VOPRF_Setup
Input:
G: Public generator of GG.
l: Some suitable choice of key-length (e.g. as described in {{NIST}}).
Output:
k: A key chosen from {0,1}^l and interpreted as an integer value.
(G,Y): A pair of curve points, where Y=kG.
Steps:
1. k <- OPRF_Setup(l)
2. Y := kG
3. Output (k, (G,Y))
4.4.2. VOPRF_Blind
Input: Input:
x - V's PRF input. x: V's PRF input.
Output: Output:
r - Random scalar in [1, p - 1]. r: Random scalar in [1, p - 1].
M - Blinded representation of x using blind r, a point in GG. M: Blinded representation of x using blind r, an element in GG.
Steps: Steps:
1. r <-$ GF(p) 1. r <-$ GF(p)
2. M := rH_1(x) 2. M := rH_1(x)
5. Output (r, M) 3. Output (r, M)
4.2.2. VOPRF_Sign 4.4.3. VOPRF_Sign
Input: Input:
k: Signer secret key.
G: Public generator of group GG. G: Public generator of group GG.
Y: Signer public key. Y: Signer public key (= kG).
M - Point in GG. M: An element in GG.
h: optional cofactor (defaults to 1).
Output: Output:
Z - Scalar multiplication of k and M, point in GG. Z: Scalar multiplication of the point M by k, element in GG.
D - DLEQ proof that log_G(Y) == log_M(Z). D: DLEQ proof that log_G(Y) == log_M(Z).
Steps: Steps:
1. Z := kM 1. Z := kM
2. D = DLEQ_Generate(G,Y,M,Z) 2. Z <- hZ
2. Output (Z, D) 3. D = DLEQ_Generate(k,G,Y,M,Z)
4. Output (Z, D)
4.2.3. VOPRF_Unblind 4.4.4. VOPRF_Unblind
Input: Input:
r: Random scalar in [1, p - 1].
G: Public generator of group GG. G: Public generator of group GG.
Y: Signer public key. Y: Signer public key.
M - Blinded representation of x using blind r, a point in GG. M: Blinded representation of x using blind r, an element in GG.
Z - Point in GG. Z: An element in GG.
D - D = DLEQ_Generate(G,Y,M,Z). D: D = DLEQ_Generate(k,G,Y,M,Z).
r - Random scalar in [1, p - 1].
Output: Output:
N - Unblinded signature, point in GG. N: Unblinded signature, element in GG.
Steps: Steps:
1. N := (-r)Z 1. N := (1/r)Z
2. If 1 = DLEQ_Verify(G,Y,M,Z,D), output N 2. If 1 = DLEQ_Verify(G,Y,M,Z,D), output N
3. Output "error" 3. Output "error"
4.2.4. VOPRF_Finalize 4.4.5. VOPRF_Finalize
Input: Input:
x - PRF input string. x: PRF input string.
N - Point in GG, or "error". N: An element in GG, or "error".
Output: Output:
y - Random element in {0,1}^L, or "error" y: Random element in {0,1}^L, or "error"
Steps: Steps:
1. If N == "error", output "error". 1. If N == "error", output "error".
2. y := H_2(x, N) 2. y := H_2(x, N)
3. Output y 3. Output y
4.5. Utility algorithms
4.5.1. bin2scalar
This algorithm converts a binary string to an integer modulo p.
Input:
s: binary string (little-endian)
l: length of binary string
p: modulus
Output:
z: An integer modulo p
Steps:
1. sVec <- vec(s) (converts s to a column vector of dimension l)
2. p2Vec <- (2^0, 2^1, ..., 2^{l-1}) (row vector of dimension l)
3. z <- p2Vec * sVec (mod p)
4. Output z
4.6. Efficiency gains with pre-processing and additive blinding
In the [OPAQUE] draft, 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, computing rH_1(x) is an example
of multiplicative blinding. A valid way of computing additive
blinding would be to instead compute H_1(x)+rG, where G is the common
generator for the group.
If the client preprocesses values of the form rG, then computing
H_1(x)+rG is more efficient than computing rH_1(x) (one addition
against log_2(r)). 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 OPRF_Blind and OPRF_Unblind (and similarly for the VOPRF
variants).
We define the additive blinding variants of the above algorithms
below along with a new algorithm OPRF_Preprocess that defines how
preprocessing is carried out. The equivalent algorithms for VOPRF
are almost identical and so we do not redefine them here. Notice
that the only computation that changes is for V, the necessary
computation of P does not change.
4.6.1. OPRF_Preprocess
Input:
G: Public generator of GG
Output:
r: Random scalar in [1, p-1]
rG: An element in GG.
rY: An element in GG.
Steps:
1. r <-$ GF(p)
2. Output (r, rG, rY)
4.6.2. OPRF_Blind
Input:
x: V's PRF input.
rG: Preprocessed element of GG.
Output:
M: Blinded representation of x using blind r, an element in GG.
Steps:
1. M := H_1(x)+rG
2. Output M
4.6.3. OPRF_Unblind
Input:
rY: Preprocessed element of GG.
M: Blinded representation of x using rG, an element in GG.
Z: An element in GG.
Output:
N: Unblinded signature, element in GG.
Steps:
1. N := Z-rY
2. Output N
Notice that OPRF_Unblind computes (Z-rY) = k(H_1(x)+rG) - rkG =
kH_1(x) by the commutativity of scalar multiplication in GG. This is
the same output as in the original OPRF_Unblind algorithm.
5. NIZK Discrete Logarithm Equality Proof 5. NIZK Discrete Logarithm Equality Proof
In some cases, it may be desirable for the V to have proof that P For the VOPRF protocol we require that V is able to verify that P has
used its private key to compute Z from M. This is done by proving used its private key k to evaluate the PRF. We can do this by
log_G(Y) == log_M(Z). This may be used, for example, to ensure that showing that the original commitment (G,Y) output by VOPRF_Setup(l)
P uses the same private key for computing the VOPRF output and does satisfies log_G(Y) == log_M(Z) where Z is the output of
not attempt to "tag" individual verifiers with select keys. This VOPRF_Sign(k,(G,Y),M).
proof must not reveal the P's long-term private key to V.
Consequently, we extend the protocol in the previous section with a This may be used, for example, to ensure that P uses the same private
(non-interactive) discrete logarithm equality (DLEQ) algorithm built key for computing the VOPRF output and does not attempt to "tag"
on a Chaum-Pedersen [ChaumPedersen] proof. This proof is divided individual verifiers with select keys. This proof must not reveal
into two procedures: DLEQ_Generate and DLEQ_Verify. These are the P's long-term private key to V.
specified below.
Consequently, this allows extending the OPRF protocol with a (non-
interactive) discrete logarithm equality (DLEQ) algorithm built on a
Chaum-Pedersen [ChaumPedersen] proof. This proof is divided into two
procedures: DLEQ_Generate and DLEQ_Verify. These are specified
below.
5.1. DLEQ_Generate 5.1. DLEQ_Generate
Input: Input:
G: Public generator of group GG. k: Signer secret key.
Y: Signer public key. G: Public generator of GG.
M: Point in GG. Y: Signer public key (= kG).
Z: Point in GG. M: An element in GG.
H_3: A hash function from GG to a bitstring of length L modeled as a random oracle. Z: An element in GG.
H_3: A hash function from GG to {0,1}^L, modelled as a random oracle.
Output: Output:
D: DLEQ proof (c, s). D: DLEQ proof (c, s).
Steps: Steps:
1. r <-$ GF(p) 1. r <-$ GF(p)
2. A = rG and B = rM. 2. A := rG and B := rM.
2. c = H_3(G,Y,M,Z,A,B) 3. c <- H_3(G,Y,M,Z,A,B)
3. s = (r - ck) (mod p) 4. s := (r - ck) (mod p)
4. Output D = (c, s) 5. Output D := (c, s)
5.2. DLEQ_Verify 5.2. DLEQ_Verify
Input: Input:
G: Public generator of group GG. G: Public generator of GG.
Y: Signer public key. Y: Signer public key.
M: Point in GG. M: An element in GG.
Z: Point in GG. Z: An element in GG.
D: DLEQ proof (c, s). D: DLEQ proof (c, s).
Output: Output:
True if log_G(Y) == log_M(Z), False otherwise. True if log_G(Y) == log_M(Z), False otherwise.
Steps: Steps:
1. A' = (sG + cY) 1. A' := (sG + cY)
2. B' = (sM + cZ) 2. B' := (sM + cZ)
3. c' = H_3(G,Y,M,Z,A',B') 3. c' <- H_3(G,Y,M,Z,A',B')
4. Output c == c' 4. Output c == c'
5.3. Elliptic Curve Group and Hash Function Instantiations
This section specifies supported ECVOPRF group and hash function
instantiations. We focus on the instantiations of the VOPRF in the
elliptic curve setting for now. Eventually, we would like to provide
instantiations based on curves over non-prime-order base fields.
ECVOPRF-P256-SHA256: 6. Batched VOPRF evaluation
o G: P-256 Common applications (e.g. [PrivacyPass]) require V to obtain
multiple PRF evaluations from P. In the VOPRF case, this would also
require generation and verification of a DLEQ proof for each Zi
received by V. This is costly, both in terms of computation and
communication. To get around this, applications use a 'batching'
procedure for generating and verifying DLEQ proofs for a finite
number of PRF evaluation pairs (Mi,Zi). For n PRF evaluations:
o H_1: Simplified SWU encoding [I-D.irtf-cfrg-hash-to-curve] o Proof generation is slightly more expensive from 2n modular
exponentiations to 2n+2.
o H_2: SHA256 o Proof verification is much more efficient, from 4m modular
exponentiations to 2n+4.
o H_3: SHA256 o Communications falls from 2n to 2 group elements.
ECVOPRF-P256-SHA512: Therefore, since P is usually a powerful server, we can tolerate a
slight increase in proof generation complexity for much more
efficient communication and proof verification.
o G: P-256 In this section, we describe algorithms for batching the DLEQ
generation and verification procedure. For these algorithms we
require a pseudorandom generator PRNG: {0,1}^a x ZZ -> ({0,1}^b)^n
that takes a seed of length a and an integer n as input, and outputs
n elements in {0,1}^b.
o H_1: Simplified SWU encoding [I-D.irtf-cfrg-hash-to-curve] 6.1. Batched DLEQ algorithms
o H_2: SHA512 6.1.1. Batched_DLEQ_Generate
Input:
o H_3: SHA512 k: Signer secret key.
G: Public generator of group GG.
Y: Signer public key (= kG).
n: Number of PRF evaluations.
[Mi]: An array of points in GG of length n.
[Zi]: An array of points in GG of length n.
PRNG: A pseudorandom generator of the form above.
salt: An integer salt value for each PRNG invocation
info: A string value for splitting the domain of the PRNG
H_4: A hash function from GG^(2n+2) to {0,1}^a, modelled as a random oracle.
ECVOPRF-P384-SHA256: Output:
o G: P-384 D: DLEQ proof (c, s).
o H_1: Icart encoding [I-D.irtf-cfrg-hash-to-curve] Steps:
o H_2: SHA256 1. seed <- H_4(G,Y,[Mi,Zi]))
2. d1,...dn <- PRNG(seed,salt,info,n)
3. c1,...,cn := (int)d1,...,(int)dn
4. M := c1M1 + ... + cnMn
5. Z := c1Z1 + ... + cnZn
6. Output D <- DLEQ_Generate(k,G,Y,M,Z)
o H_3: SHA256 6.1.2. Batched_DLEQ_Verify
ECVOPRF-P384-SHA512: Input:
o G: P-384 G: Public generator of group GG.
Y: Signer public key.
[Mi]: An array of points in GG of length n.
[Zi]: An array of points in GG of length n.
D: DLEQ proof (c, s).
o H_1: Icart encoding [I-D.irtf-cfrg-hash-to-curve] Output:
o H_2: SHA512 True if log_G(Y) == log_(Mi)(Zi) for each i in 1...n, False otherwise.
o H_3: SHA512 Steps:
ECVOPRF-CURVE25519-SHA256: 1. seed <- H_4(G,Y,[Mi,Zi]))
2. d1,...dn <- PRNG(seed,salt,info,n)
3. c1,...,cn := (int)d1,...,(int)dn
4. M := c1M1 + ... + cnMn
5. Z := c1Z1 + ... + cnZn
6. Output DLEQ_Verify(G,Y,M,Z,D)
o G: Curve25519 [RFC7748] 6.2. Modified protocol execution
o H_1: Elligator2 encoding [I-D.irtf-cfrg-hash-to-curve] The VOPRF protocol from Section Section 4 changes to allow specifying
multiple blinded PRF inputs [Mi] for i in 1...n. Then P computes the
array [Zi] and replaces DLEQ_Generate with Batched_DLEQ_Generate over
these arrays. The same applies to the algorithm VOPRF_Sign. The
same applies for replacing DLEQ_Verify with Batched_DLEQ_Verify when
V verifies the response from P and during the algorithm VOPRF_Verify.
o H_2: SHA256 6.3. PRNG and resampling
o H_3: SHA256
ECVOPRF-CURVE25519-SHA512: Any function that satisfies the security properties of a pseudorandom
number generator can be used for computing the batched DLEQ proof.
For example, SHAKE-256 [SHAKE] or HKDF-SHA256 [RFC5869] would be
reasonable choices for groups that have an order of 256 bits.
o G: Curve25519 [RFC7748] We note that the PRNG outputs d1,...,dn must be smaller than the
order of the group/curve that is being used. Resampling can be
achieved by increasing the value of the iterator that is used in the
info field of the PRNG input.
o H_1: Elligator2 encoding [I-D.irtf-cfrg-hash-to-curve] 7. Supported ciphersuites
o H_2: SHA512 This section specifies supported ECVOPRF group and hash function
instantiations. We only provide ciphersuites in the EC setting as
these provide the most efficient way of instantiating the OPRF. Our
instantiation includes considerations for providing the DLEQ proofs
that make the instantiation a VOPRF. Supporting OPRF operations
(ECOPRF) alone can be allowed by simply dropping the relevant
components. In addition, we currently only support ciphersuites
demonstrating 128 bits of security.
o H_3: SHA512 7.1. ECVOPRF-P256-HKDF-SHA256-SSWU:
ECVOPRF-CURVE448-SHA256: o GG: SECP256K1 curve [SEC2]
o G: Curve448 [RFC7748] o H_1: H2C-P256-SHA256-SSWU- [I-D.irtf-cfrg-hash-to-curve]
o H_1: Elligator2 encoding [I-D.irtf-cfrg-hash-to-curve] * label: voprf_h2c
o H_2: SHA256 o H_2: SHA256
o H_3: SHA256 o H_3: SHA256
ECVOPRF-CURVE448-SHA512: o H_4: SHA256
o G: Curve448 [RFC7748] o PRNG: HKDF-SHA256
o H_1: Elligator2 encoding [I-D.irtf-cfrg-hash-to-curve] 7.2. ECVOPRF-RISTRETTO-HKDF-SHA512-Elligator2:
o GG: Ristretto [RISTRETTO]
o H_1: H2C-Curve25519-SHA512-Elligator2-Clear
[I-D.irtf-cfrg-hash-to-curve]
* label: voprf_h2c
o H_2: SHA512 o H_2: SHA512
o H_3: SHA512 o H_3: SHA512
6. Security Considerations o H_4: SHA512
o PRNG: HKDF-SHA512
In the case of Ristretto, internal point representations are
represented by Ed25519 [RFC7748] points. As a result, we can use the
same hash-to-curve encoding as we would use for Ed25519
[I-D.irtf-cfrg-hash-to-curve]. We remark that the 'label' field is
necessary for domain separation of the hash-to-curve functionality.
8. Security Considerations
Security of the protocol depends on P's secrecy of k. Best practices Security of the protocol depends on P's secrecy of k. Best practices
recommend P regularly rotate k so as to keep its window of compromise recommend P regularly rotate k so as to keep its window of compromise
small. Moreover, it each key should be generated from a source of small. Moreover, it each key should be generated from a source of
safe, cryptographic randomness. safe, cryptographic randomness.
Another critical aspect of this protocol is reliance on Another critical aspect of this protocol is reliance on
[I-D.irtf-cfrg-hash-to-curve] for mapping arbitrary input to points [I-D.irtf-cfrg-hash-to-curve] for mapping arbitrary inputs x to
on a curve. Security requires this mapping be pre-image and points on a curve. Security requires this mapping be pre-image and
collision resistant. collision resistant.
6.1. Timing Leaks 8.1. Timing Leaks
To ensure no information is leaked during protocol execution, all To ensure no information is leaked during protocol execution, all
operations that use secret data MUST be constant time. Operations operations that use secret data MUST be constant time. Operations
that SHOULD be constant time include: H_1() (hashing arbitrary that SHOULD be constant time include: H_1() (hashing arbitrary
strings to curves) and DLEQ_Generate(). strings to curves) and DLEQ_Generate().
[I-D.irtf-cfrg-hash-to-curve] describes various algorithms for [I-D.irtf-cfrg-hash-to-curve] describes various algorithms for
constant-time implementations of H_1. constant-time implementations of H_1.
6.2. Hashing to curves 8.2. Hashing to curves
We choose different encodings in relation to the elliptic curve that We choose different encodings in relation to the elliptic curve that
is used, all methods are illuminated precisely in is used, all methods are illuminated precisely in
[I-D.irtf-cfrg-hash-to-curve]. In summary, we use the simplified [I-D.irtf-cfrg-hash-to-curve]. In summary, we use the simplified
Shallue-Woestijne-Ulas algorithm for hashing binary strings to the Shallue-Woestijne-Ulas algorithm for hashing binary strings to the
P-256 curve; the Icart algorithm for hashing binary strings to P384; P-256 curve; the Icart algorithm for hashing binary strings to P384;
the Elligator2 algorithm for hashing binary strings to CURVE25519 and the Elligator2 algorithm for hashing binary strings to CURVE25519 and
CURVE448. CURVE448.
7. Privacy Considerations 8.3. Verifiability (key consistency)
7.1. Key Consistency
DLEQ proofs are essential to the protocol to allow V to check that DLEQ proofs are essential to the protocol to allow V to check that
P's designated private key was used in the computation. A side P's designated private key was used in the computation. A side
effect of this property is that it prevents P from using unique key effect of this property is that it prevents P from using a unique key
for select verifiers as a way of "tagging" them. If all verifiers for select verifiers as a way of "tagging" them. If all verifiers
expect use of a certain private key, e.g., by locating P's public key expect use of a certain private key, e.g., by locating P's public key
key published from a trusted registry, then P cannot present unique published from a trusted registry, then P cannot present unique keys
keys to an individual verifier. to an individual verifier.
8. Acknowledgements For this side effect to hold, P must also be prevented from using
other techniques to manipulate their public key within the trusted
registry to reduce client anonymity. For example, if P's public key
is rotated too frequently then this may stratify the user base into
small anonymity groups (those with VOPRF_Sign outputs taken from a
given key epoch). In this case, it may become practical to link
VOPRF sessions for a given user and thus compromises their privacy.
Similarly, if P can publish N public keys to a trusted registry then
P may be able to control presentation of these keys in such a way
that V is retroactively identified by V's key choice across multiple
requests.
9. Applications
This section describes various applications of the VOPRF protocol.
9.1. Privacy Pass
This VOPRF protocol is used by Privacy Pass system to help Tor users
bypass CAPTCHA challenges. Their system works as follows. Client C
connects - through Tor - to an edge server E serving content. Upon
receipt, E serves a CAPTCHA to C, who then solves the CAPTCHA and
supplies, in response, n blinded points. E verifies the CAPTCHA
response and, if valid, signs (at most) n blinded points, which are
then returned to C along with a batched DLEQ proof. C stores the
tokens if the batched proof verifies correctly. When C attempts to
connect to E again and is prompted with a CAPTCHA, C uses one of the
unblinded and signed points, or tokens, to derive a shared symmetric
key sk used to MAC the CAPTCHA challenge. C sends the CAPTCHA, MAC,
and token input x to E, who can use x to derive sk and verify the
CAPTCHA MAC. Thus, each token is used at most once by the system.
The Privacy Pass implementation uses the P-256 instantiation of the
VOPRF protocol. For more details, see [DGSTV18].
9.2. Private Password Checker
In this application, let D be a collection of plaintext passwords
obtained by prover P. For each password p in D, P computes
VOPRF_Sign on H_1(p), where H_1 is as described above, and stores the
result in a separate collection D'. P then publishes D' with Y, its
public key. If a client C wishes to query D' for a password p', it
runs the VOPRF protocol using p as input x to obtain output y. By
construction, y will be the signature of p hashed onto the curve. C
can then search D' for y to determine if there is a match.
Examples of such password checkers already exist, for example:
[JKKX16], [JKK14] and [SJKS17].
9.2.1. Parameter Commitments
For some applications, it may be desirable for P to bind tokens to
certain parameters, e.g., protocol versions, ciphersuites, etc. To
accomplish this, P should use a distinct scalar for each parameter
combination. Upon redemption of a token T from V, P can later verify
that T was generated using the scalar associated with the
corresponding parameters.
10. Acknowledgements
This document resulted from the work of the Privacy Pass team This document resulted from the work of the Privacy Pass team
[PrivacyPass]. [PrivacyPass]. The authors would also like to acknowledge the
helpful conversations with Hugo Krawczyk. Eli-Shaoul Khedouri
provided additional review and comments on key consistency.
9. Normative References 11. Normative References
[ChaumBlindSignature] [ChaumBlindSignature]
"Blind Signatures for Untraceable Payments", n.d., "Blind Signatures for Untraceable Payments", n.d.,
<http://sceweb.sce.uhcl.edu/yang/teaching/ <http://sceweb.sce.uhcl.edu/yang/teaching/
csci5234WebSecurityFall2011/Chaum-blind-signatures.PDF>. csci5234WebSecurityFall2011/Chaum-blind-signatures.PDF>.
[ChaumPedersen] [ChaumPedersen]
"Wallet Databases with Observers", n.d., "Wallet Databases with Observers", n.d.,
<https://chaum.com/publications/Wallet_Databases.pdf>. <https://chaum.com/publications/Wallet_Databases.pdf>.
[DECAF] "Decaf, Eliminating cofactors through point compression", [DECAF] "Decaf, Eliminating cofactors through point compression",
n.d., <https://www.shiftleft.org/papers/decaf/decaf.pdf>. n.d., <https://www.shiftleft.org/papers/decaf/decaf.pdf>.
[DGSTV18] "Privacy Pass, Bypassing Internet Challenges Anonymously", [DGSTV18] "Privacy Pass, Bypassing Internet Challenges Anonymously",
n.d., <https://www.degruyter.com/view/j/ n.d., <https://www.degruyter.com/view/j/
popets.2018.2018.issue-3/popets-2018-0026/popets- popets.2018.2018.issue-3/popets-2018-0026/
2018-0026.xml>. popets-2018-0026.xml>.
[I-D.irtf-cfrg-hash-to-curve] [I-D.irtf-cfrg-hash-to-curve]
Scott, S., Sullivan, N., and C. Wood, "Hashing to Elliptic Scott, S., Sullivan, N., and C. Wood, "Hashing to Elliptic
Curves", draft-irtf-cfrg-hash-to-curve-01 (work in Curves", draft-irtf-cfrg-hash-to-curve-02 (work in
progress), July 2018. progress), October 2018.
[JKK14] "Round-Optimal Password-Protected Secret Sharing and [JKK14] "Round-Optimal Password-Protected Secret Sharing and
T-PAKE in the Password-Only model", n.d., T-PAKE in the Password-Only model", n.d.,
<https://eprint.iacr.org/2014/650.pdf>. <https://eprint.iacr.org/2014/650.pdf>.
[JKKX16] "Highly-Efficient and Composable Password-Protected Secret [JKKX16] "Highly-Efficient and Composable Password-Protected Secret
Sharing (Or, How to Protect Your Bitcoin Wallet Online)", Sharing (Or, How to Protect Your Bitcoin Wallet Online)",
n.d., <https://eprint.iacr.org/2016/144>. n.d., <https://eprint.iacr.org/2016/144>.
[NIST] "Keylength - NIST Report on Cryptographic Key Length and
Cryptoperiod (2016)", n.d.,
<https://www.keylength.com/en/4/>.
[OPAQUE] "The OPAQUE Asymmetric PAKE Protocol", n.d.,
<https://tools.ietf.org/html/
draft-krawczyk-cfrg-opaque-01>.
[PrivacyPass] [PrivacyPass]
"Privacy Pass", n.d., <https://github.com/privacypass/ "Privacy Pass", n.d.,
challenge-bypass-server>. <https://github.com/privacypass/challenge-bypass-server>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, <https://www.rfc- DOI 10.17487/RFC2119, March 1997,
editor.org/info/rfc2119>. <https://www.rfc-editor.org/info/rfc2119>.
[RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand
Key Derivation Function (HKDF)", RFC 5869,
DOI 10.17487/RFC5869, May 2010,
<https://www.rfc-editor.org/info/rfc5869>.
[RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves [RFC7748] Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
for Security", RFC 7748, DOI 10.17487/RFC7748, January for Security", RFC 7748, DOI 10.17487/RFC7748, January
2016, <https://www.rfc-editor.org/info/rfc7748>. 2016, <https://www.rfc-editor.org/info/rfc7748>.
[RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital [RFC8032] Josefsson, S. and I. Liusvaara, "Edwards-Curve Digital
Signature Algorithm (EdDSA)", RFC 8032, Signature Algorithm (EdDSA)", RFC 8032,
DOI 10.17487/RFC8032, January 2017, <https://www.rfc- DOI 10.17487/RFC8032, January 2017,
editor.org/info/rfc8032>. <https://www.rfc-editor.org/info/rfc8032>.
[RISTRETTO] [RISTRETTO]
"The Ristretto Group", n.d., <https://ristretto.group/ "The ristretto255 Group", n.d.,
ristretto.html>. <https://tools.ietf.org/html/
draft-hdevalence-cfrg-ristretto-00>.
[SEC2] Standards for Efficient Cryptography Group (SECG), ., "SEC
2: Recommended Elliptic Curve Domain Parameters", n.d.,
<http://www.secg.org/sec2-v2.pdf>.
[SHAKE] "SHA-3 Standard, Permutation-Based Hash and Extendable-
Output Functions", n.d.,
<https://www.nist.gov/publications/sha-3-standard-
permutation-based-hash-and-extendable-output-
functions?pub_id=919061>.
[SJKS17] "SPHINX, A Password Store that Perfectly Hides from [SJKS17] "SPHINX, A Password Store that Perfectly Hides from
Itself", n.d., Itself", n.d.,
<http://webee.technion.ac.il/%7Ehugo/sphinx.pdf>. <http://webee.technion.ac.il/%7Ehugo/sphinx.pdf>.
Appendix A. Test Vectors Appendix A. Test Vectors
This section includes test vectors for the primary ECVOPRF protocol, This section includes test vectors for the ECVOPRF-P256-HKDF-SHA256
excluding DLEQ output. VOPRF ciphersuite, including batched DLEQ output.
((TODO: add DLEQ vectors))
P-224
X: 0403cd8bc2f2f3c4c647e063627ca9c9ac246e3e3ec74ab76d32d3e999c522d60ff7aa1c8b0e4 \
X: 0403cd8bc2f2f3c4c647e063627ca9c9ac246e3e3ec74ab76d32d3e999c522d60ff7aa1c8b0e4
r: c4cf3c0b3a334f805d3ce3c3b4d007fbbdaf078a42a8cbdc833e54a9
M: 046b2b8482c36e65f87528415e210cff8561c1c8e07600a159893973365617ee2c1c33eb0662d \
M: 046b2b8482c36e65f87528415e210cff8561c1c8e07600a159893973365617ee2c1c33eb0662d
k: a364119e1c932a534a8d440fef2169a0e4c458d702eca56746655845
Z: 04ed11656b4981e39242b170025bf8d5314bef75006e6c4c9afcdb9a85e21fb5fcf9055eb95d3 \
Z: 04ed11656b4981e39242b170025bf8d5314bef75006e6c4c9afcdb9a85e21fb5fcf9055eb95d3
Y: 04fd80db5301a54ee2cbc688d47cbcae9eb84f5d246e3da3e2b03e9be228ed6c57a936b6b5faf \
Y: 04fd80db5301a54ee2cbc688d47cbcae9eb84f5d246e3da3e2b03e9be228ed6c57a936b6b5faf
P-224
X: 0429e41b7e1a58e178afc522d0fb4a6d17ae883e6fd439931cf1e81456ab7ed6445dbe0a231be \
X: 0429e41b7e1a58e178afc522d0fb4a6d17ae883e6fd439931cf1e81456ab7ed6445dbe0a231be
r: 86a27e1bd51ac91eae32089015bf903fe21da8d79725edcc4dc30566
M: 04d8c8ffaa92b21aa1cc6056710bd445371e8afebd9ef0530c68cd0d09536423f78382e4f6b20 \
M: 04d8c8ffaa92b21aa1cc6056710bd445371e8afebd9ef0530c68cd0d09536423f78382e4f6b20
k: ab449c896261dc3bd1f20d87272e6c8184a2252a439f0b3140078c3d
Z: 048ac9722189b596ffe5cb986332e89008361e68f77f12a931543f63eaa01fabf6f63d5d4b3b6 \
Z: 048ac9722189b596ffe5cb986332e89008361e68f77f12a931543f63eaa01fabf6f63d5d4b3b6
Y: 046e83dff2c9b6f9e88f1091f355ad6fa637bdbd829072411ea2d74a5bf3501ccf3bcc2789d48 \
Y: 046e83dff2c9b6f9e88f1091f355ad6fa637bdbd829072411ea2d74a5bf3501ccf3bcc2789d48
P-256 P-256
X: 041b0e84c521f8dcd530d59a692d4ffa1ca05b8ba7ce22a884a511f93919ac121cc91dd588228 \ X: 04b14b08f954f5b6ab1d014b1398f03881d70842acdf06194eb96a6d08186f8cb985c1c5521 \
X: 041b0e84c521f8dcd530d59a692d4ffa1ca05b8ba7ce22a884a511f93919ac121cc91dd588228 f4ee19e290745331f7eb89a4053de0673dc8ef14cfe9bf8226c6b31
r: a3ec1dc3303a316fc06565ace0a8910da65cf498ea3884c4349b6c4fc9a2f99a r: b72265c85b1ba42cfed7caaf00d2ccac0b1a99259ba0dbb5a1fc2941526a6849
M: 04794c5a54236782088594ccdb1975e93b05ff742674cc400cb101f55c0f37e877c5ada0d72fb \ M: 046025a41f81a160c648cfe8fdcaa42e5f7da7a71055f8e23f1dc7e4204ab84b705043ba5c7 \
M: 04794c5a54236782088594ccdb1975e93b05ff742674cc400cb101f55c0f37e877c5ada0d72fb 000123e1fd058150a4d3797008f57a8b2537766d9419c7396ba5279
k: 9c103b889808a8f4cb6d76ea8b634416a286be7fa4a14e94f1478ada7f172ec3 k: f84e197c8b712cdf452d2cff52dec1bd96220ed7b9a6f66ed28c67503ae62133
Z: 0484cfda0fdcba7693672fe5e78f4c429c096ece730789e8d00ec1f7be33a6515f186dcf7aa38 \ Z: 043ab5ccb690d844dcb780b2d9e59126d62bc853ba01b2c339ba1c1b78c03e4b6adc5402f77 \
Z: 0484cfda0fdcba7693672fe5e78f4c429c096ece730789e8d00ec1f7be33a6515f186dcf7aa38 9fc29f639edc138012f0e61960e1784973b37f864e4dc8abbc68e0b
Y: 044ff2e31de9fda542c2c63314e2bce5ce2d5ccb8332dbe1115ff5740e5e60bb867994e196ead \ N: 04e8aa6792d859075821e2fba28500d6974ba776fe230ba47ef7e42be1d967654ce776f889e \
Y: 044ff2e31de9fda542c2c63314e2bce5ce2d5ccb8332dbe1115ff5740e5e60bb867994e196ead e1f374ffa0bce904408aaa4ed8a19c6cc7801022b7848031f4e442a
D: { s: faddfaf6b5d6b4b6357adf856fc1e0044614ebf9dafdb4c6541c1c9e61243c5b,
c: 8b403e170b56c915cc18864b3ab3c2502bd8f5ca25301bc03ab5138343040c7b }
P-256 P-256
X: 043ea9d81b99ac0db002ad2823f7cab28af18f83419cce6800f3d786cc00b6fd030858d073916 \ X: 047e8d567e854e6bdc95727d48b40cbb5569299e0a4e339b6d707b2da3508eb6c238d3d4cb4 \
X: 043ea9d81b99ac0db002ad2823f7cab28af18f83419cce6800f3d786cc00b6fd030858d073916 68afc6ffc82fccbda8051478d1d2c9b21ffdfd628506c873ebb1249
r: ed7294b42792760825645b635e9d92ef5a3baa70879dd59fdb1802d4a44271b2 r: f222dfe530fdbfcb02eb851867bfa8a6da1664dfc7cee4a51eb6ff83c901e15e
M: 04ec894e496d0297756a17365f866d9449e6ebc51852ab1ffa57bc29c843ef003b116f5ef1f60 \ M: 04e2efdc73747e15e38b7a1bb90fe5e4ef964b3b8dccfda428f85a431420c84efca02f0f09c \
M: 04ec894e496d0297756a17365f866d9449e6ebc51852ab1ffa57bc29c843ef003b116f5ef1f60 83a8241b44572a059ab49c080a39d0bce2d5d0b44ff5d012b5184e7
k: a324338a7254415dbedcd1855abd2503b4e5268124358d014dac4fc2c722cd67 k: fb164de0a87e601fd4435c0d7441ff822b5fa5975d0c68035beac05a82c41118
Z: 04a477c5fefd9bc6bcd8e893a1b0c6dc73b0bd23ebe952dcad810de73b8a99f5e1e216a833b32 \ Z: 049d01e1c555bd3324e8ce93a13946b98bdcc765298e6d60808f93c00bdfba2ebf48eef8f28 \
Z: 04a477c5fefd9bc6bcd8e893a1b0c6dc73b0bd23ebe952dcad810de73b8a99f5e1e216a833b32 d8c91c903ad6bea3d840f3b9631424a6cc543a0a0e1f2d487192d5b
Y: 04ffe55e2a95a21e1605c1ed11ac6bea93f00fa15a6b27e90adad470ad27f0e0fe5b8607b4689 \ N: 04723880e480b60b4415ca627585d1715ab5965570d30c94391a8b023f8854ac26f76c1d6ab \
Y: 04ffe55e2a95a21e1605c1ed11ac6bea93f00fa15a6b27e90adad470ad27f0e0fe5b8607b4689 bb38688a5affbcadad50ecbf7c93ef33ddfd735003b5a4b1a21ba14
D: { s: dfdf6ae40d141b61d5b2d72cf39c4a6c88db6ac5b12044a70c212e2bf80255b4,
P-384 c: 271979a6b51d5f71719127102621fe250e3235867cfcf8dea749c3e253b81997 }
X: 04c0b51e5dcd6a309c77bb5720bf9850279e8142b6127952595ab9092578de810a13795bceff3 \
d358f0480a61469f17ad62ebaecd0f817c1e9c7d41d536ab410e7a2b5d7a7905d1bef5499b654b0e \
d358f0480a61469f17ad62ebaecd0f817c1e9c7d41d536ab410e7a2b5d7a7905d1bef5499b654b0e
r: 889b5e4812d683c4df735971240741ff869ccf77e10c2e97bef67d6fe6b8350abe59ec8fe2bfa \
r: 889b5e4812d683c4df735971240741ff869ccf77e10c2e97bef67d6fe6b8350abe59ec8fe2bfa
M: 044e2d86fa6e53ebba7f2a9b661a2de884a8ccc68e29b68586d517eb66e8b4b7dac334c6e769d \
485d672fac3a0311877572254754e318077aec3631208c6b503c5cdfe57716e1232da64cebe46f0d \
485d672fac3a0311877572254754e318077aec3631208c6b503c5cdfe57716e1232da64cebe46f0d
k: b8c854a33c8c564d0598b1ac179546acdccad671265cff1ea5a329279272e8d21c94b7e5b6bea \
k: b8c854a33c8c564d0598b1ac179546acdccad671265cff1ea5a329279272e8d21c94b7e5b6bea
Z: 047bf23eef00e83e6cb6fb9ade5e5995cf81abb8dc73a570ff4cb7be48f21281edfed9bf76cc2 \
88b35d2df615ff711ed2a1fb85cd0b22812438665cdd300039685b3f593f4b574f9e8b294982c2a2 \
88b35d2df615ff711ed2a1fb85cd0b22812438665cdd300039685b3f593f4b574f9e8b294982c2a2
Y: 04ab4886ecf7e489a0be8529ff4b537941c95ba4ce570db537dcfad5cabc064c43f1b0a1d1b89 \
101facd93f2f9a8b5f28431489be4664f446af8a51cc7c4221f633adb4f8f2f2a073dfd83ddf8d77 \
101facd93f2f9a8b5f28431489be4664f446af8a51cc7c4221f633adb4f8f2f2a073dfd83ddf8d77
P-384
X: 047511a846277a2009f37b3583f14c8ea3af17e3a146e0e737fdc1260b6d4a18ff01f21ec3bbc \
e39e1cade76d455feadc1bb16f65cd54042e1bc5aba1dee2434f59d00698a963b902148750240f8f \
e39e1cade76d455feadc1bb16f65cd54042e1bc5aba1dee2434f59d00698a963b902148750240f8f
r: e514ef9b3ea87eafdb78da48e642daa79f036ac00228997ab8da6ac198fb888cd2fec84d52010 \
r: e514ef9b3ea87eafdb78da48e642daa79f036ac00228997ab8da6ac198fb888cd2fec84d52010
M: 04fd9b68973b0fcefcf4458b4faa1c3815bdad8975b7fb0bfc4c1db7e3f169fb3a26ddabe1b25 \
c4a23cf8a2faeb12c18f06f2227e87ede6039f55a61ef0c89ca3c582e2864fe130ea0c709f92519d \
c4a23cf8a2faeb12c18f06f2227e87ede6039f55a61ef0c89ca3c582e2864fe130ea0c709f92519d
k: bcc73da3b2adace9c4f4c32eeadef57436c97f8d395614e78aa91523e1e5d7f551ebb55e87da2 \
k: bcc73da3b2adace9c4f4c32eeadef57436c97f8d395614e78aa91523e1e5d7f551ebb55e87da2
Z: 042d885d2945cde40e490dd8497975eaeb54e4e10c5986a9688c9de915b16cf43572fd155e159 \
9e2233a75056a72b54d30092e30bb2edc70e0d90da934c27362e0e6303bafae12f13bf3d5be322e6 \
9e2233a75056a72b54d30092e30bb2edc70e0d90da934c27362e0e6303bafae12f13bf3d5be322e6
Y: 044833fba4973c1c6eae6745850866ebbb23783ea0d4d8b867e2c93acb2f01fd3d36d9cb5c491 \
ff9440c8c8e325db326bf88ddf0ba6008158a67999e18cd378d701d1f8a6a7b088dc261c85b6a78b \
ff9440c8c8e325db326bf88ddf0ba6008158a67999e18cd378d701d1f8a6a7b088dc261c85b6a78b
P-521
X: 040039d290b20c604b5c59cb85dfacd90cbf9f5e275ee8c38a8ff80df0872e8e1dd214a9ec3b2 \
2c8d75bf634739afdc09acc342542abacf35bf2a6488d084825c5d96003be29e201e75c1b78667f5 \
a64cc7207722796b225b49edaaf457fcafff4f644252ebe8057291d317f30109f1526aacbfff2308 \
a64cc7207722796b225b49edaaf457fcafff4f644252ebe8057291d317f30109f1526aacbfff2308
r: 010606612666705556ac3c28dde30f134e930b0c31bfc9715f0812e0b99f0212dc427e344cb97 \
r: 010606612666705556ac3c28dde30f134e930b0c31bfc9715f0812e0b99f0212dc427e344cb97
M: 040065366112a0598e4e5997e79e42f287f7202e5d956bef29890e963169d9eaab8d21501283c \
47dd37aca1710c8b5f456b1c044c8582ba6feef3edc997fecef7d4f40180ceb9bbbe3ab1907ea2d1 \
21ec00156848e04e323744d86444111fc09a21ca316df2cae925a0bb079d0faa2474ec8d5a96e6fa \
21ec00156848e04e323744d86444111fc09a21ca316df2cae925a0bb079d0faa2474ec8d5a96e6fa
k: 01297d92cfe6895269aa5406f2ba6cbfffbba66a11ab0db34655213624fa238c50e27177aea5d \
k: 01297d92cfe6895269aa5406f2ba6cbfffbba66a11ab0db34655213624fa238c50e27177aea5d
Z: 040151d2dc5290ebd47065680dcb4db350c4d81346680c5589f94acfb1e28418585e7f2cbfa11 \
5945d9f7b98157ea8c2ab190c6a47b939502c2f793b77ceff671f5e60086fdd1ebf960f29bf5d590 \
f8f7511d248df22d964637e2286adab4654991d338691f4673a006ff116e61afe65c914b27c3ef4c \
f8f7511d248df22d964637e2286adab4654991d338691f4673a006ff116e61afe65c914b27c3ef4c
Y: 04009534bd720bd4ebe703968a8496eec352711a81b7fe594a72ef318c2ce582b41880262a1c6 \
05079231de91e71b1301d1be4e9618e96081ccfd4f6cab92f52b860e01beec2c58cb01713e941035 \
adbe882ab4f3eaa31e27a96d210d35f6161b1487dd28d8da4a11a915182752b1450a89aad2a013c2 \
adbe882ab4f3eaa31e27a96d210d35f6161b1487dd28d8da4a11a915182752b1450a89aad2a013c2
P-521
X: 04012ea416842dfad169a9eb860b0af2af3c0140e1918ccd043650d83ad261633f20c5ca02c1b \
ffb857ab72814cf46cfc16ac9ba79887044709f72480358c4b990e46010a62336bb57b87b494b064 \
4d2b6a385f3d5b5da29e22cae33c624f561513a5e8e6669b4e99704c56157dde83994a3c0800a64b \
4d2b6a385f3d5b5da29e22cae33c624f561513a5e8e6669b4e99704c56157dde83994a3c0800a64b
r: 019d02efd97add5facc5defbb63fd74daaacda04ae7321abec0da1551b4cc980b8ce6855a28a1 \
r: 019d02efd97add5facc5defbb63fd74daaacda04ae7321abec0da1551b4cc980b8ce6855a28a1
M: 040066e3d0b5b9758c9288a725ce6724fdc3bd797a8222f07233897a5916dc167531ebc6a4710 \
cbb240684c9a02eb82214b009d636f24abb8e409e78ff1f02a1dbfb90069056693e96acd760887f9 \
6c9b1f487441b7142fb13a67deb7332194ff454b3aac89f9cf02c338dae69a700bd26844881e6106 \
6c9b1f487441b7142fb13a67deb7332194ff454b3aac89f9cf02c338dae69a700bd26844881e6106
k: 018eeea896de104bf1e772155836f6ceddab0b4c2e3e4c33ba08a6fd6db0291cfb15faff0b3c7 \
k: 018eeea896de104bf1e772155836f6ceddab0b4c2e3e4c33ba08a6fd6db0291cfb15faff0b3c7
Z: 04016825ea754324d5761ada130a1b87b03b5e2a6b0f403343925c67df39bbf85bc782909124d \
d297a1edfb049efa7ce61c626c0ad99d8cf462abcce1ee1967d8a355011e2c5a7ce621fc822a7d95 \
bf7359d938ee4a5c3431e7dd270b7fb6e95fda29cf460d89454763bb0db9b8b705503170a9ac1c7a \
bf7359d938ee4a5c3431e7dd270b7fb6e95fda29cf460d89454763bb0db9b8b705503170a9ac1c7a
Y: 04006b0413e2686c4bb62340706de7723471080093422f02dd125c3e72f3507b9200d11481468 \
74bbaa5b6108b834c892eeebab4e21f3707ee20c303ebc1e34fcd3c701f2171131ee7c5f07c1ccad \
240183d777181259761741343959d476bbc2591a1af0a516e6403a6b81423234746d7a2e8c2ce60a \
240183d777181259761741343959d476bbc2591a1af0a516e6403a6b81423234746d7a2e8c2ce60a
Appendix B. Applications
This section describes various applications of the VOPRF protocol.
B.1. Privacy Pass
This VOPRF protocol is used by Privacy Pass system to help Tor users
bypass CAPTCHA challenges. Their system works as follows. Client C
connects - through Tor - to an edge server E serving content. Upon
receipt, E serves a CAPTCHA to C, who then solves the CAPTCHA and
supplies, in response, n blinded points. E verifies the CAPTCHA
response and, if valid, signs (at most) n blinded points, which are
then returned to C. When C attempts to connect to E again and is
prompted with a CAPTCHA, C uses one of the unblinded and signed
points, or tokens, to derive a shared symmetric key sk used to MAC
the CAPTCHA challenge. C sends the CAPTCHA, MAC, and token input x
to E, who can use x to derive sk and verify the CAPTCHA MAC. Thus,
each token is used at most once by the system.
The Privacy Pass implementation uses the P-256 instantiation of the
VOPRF protocol. For more details, see [DGSTV18].
B.2. Private Password Checker
In this application, let D be a collection of plaintext passwords
obtained by prover P. For each password p in D, P computes
VOPRF_Sign(H_1(p)), where H_1 is as described above, and stores the
result in a separate collection D'. P then publishes D' with Y, its
public key. If a client C wishes to query D' for a password p', it
runs the VOPRF protocol using p as input x to obtain output y. By
construction, y will be the signature of p hashed onto the curve. C
can then search D' for y to determine if there is a match.
Examples of such password checkers already exist, for example:
[JKKX16], [JKK14] and [SJKS17].
B.2.1. Parameter Commitments
For some applications, it may be desirable for P to bind tokens to Batched DLEQ (P256)
certain parameters, e.g., protocol versions, ciphersuites, etc. To M_0: 046025a41f81a160c648cfe8fdcaa42e5f7da7a71055f8e23f1dc7e4204ab84b705043ba5c\
accomplish this, P should use a distinct scalar for each parameter 7000123e1fd058150a4d3797008f57a8b2537766d9419c7396ba5279
combination. Upon redemption of a token T from V, P can later verify M_1: 04e2efdc73747e15e38b7a1bb90fe5e4ef964b3b8dccfda428f85a431420c84efca02f0f09\
that T was generated using the scalar associated with the c83a8241b44572a059ab49c080a39d0bce2d5d0b44ff5d012b5184e7
corresponding parameters. Z_0: 043ab5ccb690d844dcb780b2d9e59126d62bc853ba01b2c339ba1c1b78c03e4b6adc5402f7\
79fc29f639edc138012f0e61960e1784973b37f864e4dc8abbc68e0b
Z_1: 04647e1ab7946b10c1c1c92dd333e2fc9e93e85fdef5939bf2f376ae859248513e0cd91115\
e48c6852d8dd173956aec7a81401c3f63a133934898d177f2a237eeb
k: f84e197c8b712cdf452d2cff52dec1bd96220ed7b9a6f66ed28c67503ae62133
PRNG: HKDF-SHA256
salt: "DLEQ_PROOF"
info: an iterator i for invoking the PRNG on M_i and Z_i
D: { s: b2123044e633d4721894d573decebc9366869fe3c6b4b79a00311ecfa46c9e34,
c: 3506df9008e60130fcddf86fdb02cbfe4ceb88ff73f66953b1606f6603309862 }
Authors' Addresses Authors' Addresses
Alex Davidson Alex Davidson
ISG, Royal Holloway, University of London Cloudflare
Egham Hill County Hall
Twickenham, TW20 0EX London, SE1 7GP
United Kingdom United Kingdom
Email: alex.davidson.2014@rhul.ac.uk Email: adavidson@cloudflare.com
Nick Sullivan Nick Sullivan
Cloudflare Cloudflare
101 Townsend St 101 Townsend St
San Francisco San Francisco
United States of America United States of America
Email: nick@cloudflare.com Email: nick@cloudflare.com
Christopher A. Wood Christopher A. Wood
Apple Inc. Apple Inc.
 End of changes. 135 change blocks. 
437 lines changed or deleted 799 lines changed or added

This html diff was produced by rfcdiff 1.47. The latest version is available from http://tools.ietf.org/tools/rfcdiff/