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, . [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, . [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . 8.2. Informative References [Camenisch97] "Proof Systems for General Statements about Discrete Logarithms", . [pOPRF18] "Threshold Partially-Oblivious PRFs with Applications to Key Management", . [PrivateStats] "PrivateStats, De-Identified Authenticated Logging at Scale", . [Pythia15] "The Pythia PRF Service", . 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]