Internet DRAFT - draft-iyengar-cfrg-voprfmetadata
draft-iyengar-cfrg-voprfmetadata
cfrg S. Iyengar
Internet-Draft A. Raghunathan
Intended status: Informational Facebook
Expires: 26 August 2021 22 February 2021
Verifiable Oblivious Pseudo-Random Functions with Public Metadata
draft-iyengar-cfrg-voprfmetadata-00
Abstract
This document describes a verifable mechansim to bind public metadata
to an existing Verifiable oblivious Pseduo-Random function
[I-D.irtf-cfrg-voprf] (VOPRF). Using zero knowledge proofs a
receiver can verify that, for an input x, a VOPRF(k, x, metadata), is
generated from a secret key k, as well as the given metadata.
Discussion Venues
This note is to be removed before publishing as an RFC.
Discussion of this document takes place on the Crypto Forum Research
Group mailing list (cfrg@ietf.org), which is archived at
https://mailarchive.ietf.org/arch/search/?email_list=cfrg.
Source for this draft and an issue tracker can be found at
https://github.com/siyengar/verifiable-attribute-based-key-
derivation.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on 26 August 2021.
Iyengar & Raghunathan Expires 26 August 2021 [Page 1]
Internet-Draft TODO - Abbreviation February 2021
Copyright Notice
Copyright (c) 2021 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document. Code Components
extracted from this document must include Simplified BSD License text
as described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Requirements . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3
2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1. Prime-Order Group Dependency . . . . . . . . . . . . . . 4
2.2. Other Conventions . . . . . . . . . . . . . . . . . . . . 4
2.3. Discrete log proofs . . . . . . . . . . . . . . . . . . . 4
3. Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2. Pre-Setup . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3. Evaluate VOPRF . . . . . . . . . . . . . . . . . . . . . 7
4. Application considerations . . . . . . . . . . . . . . . . . 9
4.1. Metadata bits . . . . . . . . . . . . . . . . . . . . . . 9
4.2. Encoding metadata . . . . . . . . . . . . . . . . . . . . 9
5. Comparison with other approaches . . . . . . . . . . . . . . 9
5.1. Pairings . . . . . . . . . . . . . . . . . . . . . . . . 9
5.2. Partially oblivious PRF . . . . . . . . . . . . . . . . . 9
6. Security Considerations . . . . . . . . . . . . . . . . . . . 10
6.1. Cryptographic security . . . . . . . . . . . . . . . . . 10
6.1.1. n-Diffie Hellman exponent assumption . . . . . . . . 10
6.1.2. Selective security vs full security . . . . . . . . . 10
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11
8. References . . . . . . . . . . . . . . . . . . . . . . . . . 11
8.1. Normative References . . . . . . . . . . . . . . . . . . 11
8.2. Informative References . . . . . . . . . . . . . . . . . 11
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 12
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12
Iyengar & Raghunathan Expires 26 August 2021 [Page 2]
Internet-Draft TODO - Abbreviation February 2021
1. Introduction
A VOPRF allows a client and server to evaluate a psuedo-random
function "F(k, x)", with secret key "k", and input "x" without the
client learning the key "k" and the server learning the input "x".
Additionally in a VOPRF, the client can verify that the output was
computed using the key "k".
One challenge in VOPRFs is to be able to bind public metadata to the
output of the VOPRF while keeping the VOPRF both verifiable and
oblivious. Unlike the input x to the VOPRF, public metadata is not
meant to be secret to either the client or the server. This public
metadata is useful in applications where being able to bind
application context to a VOPRF output is criticial to the security of
the application.
In this draft we describe a mechanism to bind public metadata to a
VOPRF by deriving the public-private keypair that is used by the
VOPRF from the metadata [PrivateStats]. This method allows the use
of existing elliptic curve VOPRF ciphers while only changing the way
the secret key is derived. Additionally, the key derivation
mechanism of the public key can be verified by a client using non-
interactive zero-knowledge proofs to prove that the metadata specific
key is derived from a master secret.
The draft does not describe how metadata is used, but that left to
specific application protocols that use this public metadata
mechanism.
1.1. Requirements
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in BCP
14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here.
1.2. Terminology
The following terms are used throughout this document.
* PRF: Pseudorandom Function.
* VOPRF: Verifiable Oblivious Pseudorandom Function.
* Client: Protocol initiator. Learns pseudorandom function
evaluation as the output of the protocol.
Iyengar & Raghunathan Expires 26 August 2021 [Page 3]
Internet-Draft TODO - Abbreviation February 2021
* Server: Computes the pseudorandom function over a secret key.
Learns nothing about the client's input.
* NIZK: Non-interactive zero knowledge.
* DLEQ: Discrete Logarithm Equality.
2. Preliminaries
The document defines extensions to the VOPRF required to support
metadata. This document depends on the following:
* "GG": A prime-order group implementing the API described in
[I-D.irtf-cfrg-voprf] as well as the additional APIs defined below
in Section 2.1.
* "Public Metadata": The public metadata is defined as an "n" bit
vector. To represent "b" values, an application could use "log b"
bits.
2.1. Prime-Order Group Dependency
We define new member functions on the prime-order group "GG" defined
in [I-D.irtf-cfrg-voprf]:
* ScalarMult(point, scalar): A member function of "GG" that
multiples an element in the group with a "scalar" from "GF(p)".
* NewGenerator(): A member function of "GG" that samples a new
generator for the group.
2.2. Other Conventions
All algorithm descriptions are written in a Python-like pseudocode.
All scalar multiplications are performed modulo "GF(p)".
2.3. Discrete log proofs
Zero knowledge proofs for statements on discrete-logs were summarized
by [Camenisch97]. We describe two algorithms used in this draft on
"GG" to prove discrete log statements.
"DLEQProve(k, A, B, C, D)" proves that "B = k * A" and "D = k * C"
without revealing the value of "k". This type of proof is used when
"k" is a secret value that should not be revealed to a verifier.
Iyengar & Raghunathan Expires 26 August 2021 [Page 4]
Internet-Draft TODO - Abbreviation February 2021
def DLEQProve(k, A, B, C, D):
r = GG.RandomScalar()
E = r * A
F = r * C
hashInput = A || B || C || D || E || F
cbytes = Hash(hashInput)
c = GG.HashToGroup(cbytes)
z = r + k * c
return (z, E, F)
"DLEQVerify(A, B, C, D, proof)" verifies that the proof generated by
"DLEQProve" is valid.
def DLEQVerify(A, B, C, D, proof):
hashInput = A || B || C || D || proof.E || proof.F
cbytes = Hash(hashInput)
c = GG.HashToGroup(cbytes)
cBE = cB + proof.E
cDF = cD + proof.F
zA = proof.z * A
zC = proof.z * C
return zA == cBE && zC == cDF
3. Protocol
3.1. Overview
A server first generates a main key pair "(skM, pkM)", where "skM" is
the servers main secret key and "pkM" is the servers main public key.
Given public metadata "t", the server generates a keypair specific to
the metadata "t", "(skT, pkT) = PKGen(t, skM)", where "skT" is the
secret key for metadata "t" and "pkT" is its public key. Once a
metadata specific keypair is available, the server can be used to
evaluate a "VOPRF(skT, x)", where "x" is the input for the user.
When the VOPRF is in verifiable mode, the client also receives a NIZK
proof that "skT" and "pkT" are generated from "skM" and "pkM" (in
verifiable mode).
Iyengar & Raghunathan Expires 26 August 2021 [Page 5]
Internet-Draft TODO - Abbreviation February 2021
Client(pkM, input, metadata) Server(skM, pkM, metadata)
----------------------------------------------------------
blind, blindedElement = Blind(input)
blindedElement
---------->
skT, pkT, pkProofs = PKGen(skM, metadata)
evaluatedElement, proof = Evaluate(skT, pkT, blindedElement)
evaluatedElement, pkT, proof, pkProofs
<----------
pkVerified = PKVerify(pkM, pkT, pkProofs)
output = Finalize(input, blind, evaluatedElement, blindedElement, pkT, proof)
In the following sections we describe modifications to the VOPRF
scheme in [I-D.irtf-cfrg-voprf] to be able to augment an existing
VOPRF with public metadata.
3.2. Pre-Setup
We augment the offline context setup phase phase of the VOPRF in
[I-D.irtf-cfrg-voprf]. In this phase, both the client and server
create a context used for executing the online phase of the protocol.
Prior to this phase, the key pair ("skM", "pkM") should be generated
by using "MasterKeyGen(metadataBits)". This keypair is used as the
master key for VOPRFs. This master key is not used directly within
the VOPRF, however, public metadata is used to generate attribute
specific keys that are used in the VOPRF evaluation.
"metadataBits" here is the number of bits of metadata that are
required for the application of the VOPRF. "MasterKeyGen" samples
"n" scalar elements "a0, a1, ... an" from the group and a new
generator "h". "ai" is a group element associated with the "i"th bit
of metatadata. Public parameters are calculated by performing scalar
multiplicaton of "h" with each "ai".
Iyengar & Raghunathan Expires 26 August 2021 [Page 6]
Internet-Draft TODO - Abbreviation February 2021
def MasterKeyGen(metadataBits):
ais = []
his = []
h = GG.NewGroupGenerator()
a0 = GG.RandomScalar()
for i in range(metadataBits):
ai = GG.RandomScalar()
ais.append(ai)
for i in range(metadataBits):
hi = GG.ScalarMult(h, ais[i])
his.append(hi)
P0 = GG.ScalarBaseMult(a0)
skM = (a0, ais)
pkM = (GG.g, h, metadataBits, P0, his)
return (skM, pkM)
3.3. Evaluate VOPRF
When client and server have agreed on the metadata to use for the
protocol, the server first executes "PKGen(skM, metadata)" to
generate "skT" and the proof that "skT" is derived from "skM". This
draft does not discuss how the client and server agree on the
metadata to use, and that is left to the application.
Note that "skM" has one group element for each bit of the metadata
"t", as well as the extra group element "a0". Given metadata "t",
"PKGen" calculates the attribute specific key by performing a scalar
multiplication of all the group elements in "skM" for each bit of "t"
that is set to "1".
To prove that "skT" is derived from "skM", "GenProofs" generates upto
"n" discrete log proofs, one for each bit of the metadata. Each
proof proves that "hi = ai * h" and "Pi = ai * Pi-1". This proves
that "ai" was correctly used for bit "i".
Iyengar & Raghunathan Expires 26 August 2021 [Page 7]
Internet-Draft TODO - Abbreviation February 2021
def PKGen(t, skM, pkM):
pis = []
pi = skM.a0
keyBits = len(metadata)
for i in range(keyBits):
if t[i] == 0:
pis.append(None)
continue
pi = pi * skM[i]
pis.append(pi)
skT = pi
pkT = GG.ScalarMultBase(skT)
pkProofs = GenProofs(metadata, pis, skM, pkM)
return (skT, pkT, pkProofs)
def GenProofs(t, pis, skM, pkM):
proofs = []
numProofs = len(pis)
previousPi = pkM.P0
for i in range(numProofs):
if t[i] == 0:
continue
Pi = GG.ScalarBaseMult(pis[i])
proofi = DLEQProve(skM.ais[i], pkM.h, pkM.his[i], previousPi, Pi)
proofs.append((Pi, proofi))
previousPi = Pi
return proofs
Once "PKGen" has generated a public key for a set of "metadata" bits,
the client can verify that "skT" is derived from "skM", using
"PKVerify(pkM, pkT, pkProofs)". This verifies the sequence of
discrete-log proofs generated by "PKGen".
def PKVerify(pkM, pkT, t, pkProofs):
previousPi = pkM.P0
proofVerified = True
for proof in pkProofs:
if t[i] == 0:
continue
Pi = proof.Pi
verified = DLEQVerify(pkM.h, pkM.his[i], previousPi, Pi, proof)
proofVerified = proofVerified & verified
previousPi = Pi
return proofVerified
A server can use "skT" generated from "PKGen" as the private key for
the VOPRF mechanism in [I-D.irtf-cfrg-voprf].
Iyengar & Raghunathan Expires 26 August 2021 [Page 8]
Internet-Draft TODO - Abbreviation February 2021
4. Application considerations
4.1. Metadata bits
Applications must choose the maximum size in bits of the metadata
that they would like to support before setup of the protocol. The
size of the metdata impacts the following - Size of the public key -
Computation time for attribute and proof generation
For "b" being the number of metadata values needed for an
application, the size of the public key scales as "O(log b)".
Computation also scales as "O(log b)" number of scalar
multiplications for generating a public key and number of discrete
log proof generations and verifications required.
4.2. Encoding metadata
Applications must choose the number of bits of metadata required in
order to be able to represent all possible values for the
application's metadata. They MUST define their own mechanism encode
metadata into bits.
5. Comparison with other approaches
5.1. Pairings
It is possible to construct VOPRFs with public metadata using
pairing-friendly curves [I-D.draft-irtf-cfrg-pairing-friendly-curves]
with an approach in [Pythia15].
However this approach has some disadvantages. Pairings are not
widely available in cryptographic libraries and are also not
compatible with existing deployed VOPRFs like in
[I-D.irtf-cfrg-voprf]. The approach described here allows
applications to use existing deployed VOPRFs while only changing the
mechanism of key derivation.
5.2. Partially oblivious PRF
Another approach that could be used to bind metadata to a VOPRF
evaluation is to use a similar method in [pOPRF18] which uses a
regular "PRF(k, metadata)" to derive a secret key based on the
metadata which is then used in the VOPRF.
The verifiability of public key could be achieved by publishing every
public key for each metadata value in a central repository, which
could be checked by the client. For large number of values of
metadata "b", this approach generates "O(b)" keys, which can be
Iyengar & Raghunathan Expires 26 August 2021 [Page 9]
Internet-Draft TODO - Abbreviation February 2021
difficult for clients and servers to manage. In contrast, the
approach described in this document, the size of the master public
key is "O(log b)", and the public keys of each attribute can be
verified against the master key later.
6. Security Considerations
6.1. Cryptographic security
The security properties of a VOPRF with public metadata are derived
from the proof in [PrivateStats] that the VOPRF defined here is a PRF
even after giving an adversary access to proofs from "PKGen". The
VOPRF defined in [I-D.irtf-cfrg-voprf] when combined with attributes
results in a PRF output of "PRF(skM, t, x) = a0^t1 * a1^t2 ... *
an^tn * H(x)".
6.1.1. n-Diffie Hellman exponent assumption
There are several variants of the Diffie-Hellman assumption and the
proof of the VOPRF with public metadata is based on the n-Diffie
Hellman exponent assumption. The n-DHE problem requires an adversary
to distinguish the n+1-th power of a secret "a" hidden in the
exponent from a random element in "GG".
Sample uniformly at random "d" in {0,1}, and a random "r" from
"GF(p)": - Given "G" is a generator in "GG" - Given "G", "a * G" ,
"(a^2) * G", ..., "(a^n) * G" - if "d" == 0: "C = a^(n+1) * G" else:
"C = r * a"
Output "d' == d"
6.1.2. Selective security vs full security
The security properties of the VOPRF with public metadata described
in this draft is based on the proof in [PrivateStats] that the VOPRF
is a selectively-secure VRF. Selective-security is a weaker notion
of security that requires an adversary to commit to the challenge
input (in this case, the metadata and value x) before trying to break
the PRF.
In practice, if target inputs are independent of the system
parameters, there should not be an advantage to allowing the attacker
to choose the target after seeing system parameters. To convert our
VOPRF with public metadata to one satisfying a full security notion
in the random oracle model, we require that the metadata be hashed
with a collision-resistant hash function with sufficiently large
output (>=256-bits). For smaller metadata sets therefore, the
selectively-secure VRF is much more efficient.
Iyengar & Raghunathan Expires 26 August 2021 [Page 10]
Internet-Draft TODO - Abbreviation February 2021
7. IANA Considerations
This document has no IANA actions.
8. References
8.1. Normative References
[I-D.draft-irtf-cfrg-pairing-friendly-curves]
Sakemi, Y., Kobayashi, T., Saito, T., and R. S. Wahby,
"Pairing-Friendly Curves", Work in Progress, Internet-
Draft, draft-irtf-cfrg-pairing-friendly-curves-09, 16
November 2020, <https://tools.ietf.org/html/draft-irtf-
cfrg-pairing-friendly-curves-09>.
[I-D.irtf-cfrg-voprf]
Davidson, A., Faz-Hernandez, A., Sullivan, N., and C. A.
Wood, "Oblivious Pseudorandom Functions (OPRFs) using
Prime-Order Groups", Work in Progress, Internet-Draft,
draft-irtf-cfrg-voprf-06, 21 February 2021,
<https://tools.ietf.org/html/draft-irtf-cfrg-voprf-06>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/rfc/rfc2119>.
[RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.
8.2. Informative References
[Camenisch97]
"Proof Systems for General Statements about Discrete
Logarithms",
<https://crypto.ethz.ch/publications/files/CamSta97b.pdf>.
[pOPRF18] "Threshold Partially-Oblivious PRFs with Applications to
Key Management", <https://eprint.iacr.org/2018/733>.
[PrivateStats]
"PrivateStats, De-Identified Authenticated Logging at
Scale", <https://research.fb.com/privatestats>.
[Pythia15] "The Pythia PRF Service",
<https://eprint.iacr.org/2015/644.pdf>.
Iyengar & Raghunathan Expires 26 August 2021 [Page 11]
Internet-Draft TODO - Abbreviation February 2021
Acknowledgments
TODO acknowledge.
Authors' Addresses
Subodh Iyengar
Facebook
Email: subodh@fb.com
Ananth Raghunathan
Facebook
Email: ananthr@fb.com
Iyengar & Raghunathan Expires 26 August 2021 [Page 12]
