< 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/ |