idnits 2.17.1 draft-iyengar-cfrg-voprfmetadata-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There are 2 instances of too long lines in the document, the longest one being 9 characters in excess of 72. ** The abstract seems to contain references ([I-D.irtf-cfrg-voprf]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (22 February 2021) is 1159 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-11) exists of draft-irtf-cfrg-pairing-friendly-curves-09 == Outdated reference: A later version (-21) exists of draft-irtf-cfrg-voprf-06 Summary: 2 errors (**), 0 flaws (~~), 3 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 cfrg S. Iyengar 3 Internet-Draft A. Raghunathan 4 Intended status: Informational Facebook 5 Expires: 26 August 2021 22 February 2021 7 Verifiable Oblivious Pseudo-Random Functions with Public Metadata 8 draft-iyengar-cfrg-voprfmetadata-00 10 Abstract 12 This document describes a verifable mechansim to bind public metadata 13 to an existing Verifiable oblivious Pseduo-Random function 14 [I-D.irtf-cfrg-voprf] (VOPRF). Using zero knowledge proofs a 15 receiver can verify that, for an input x, a VOPRF(k, x, metadata), is 16 generated from a secret key k, as well as the given metadata. 18 Discussion Venues 20 This note is to be removed before publishing as an RFC. 22 Discussion of this document takes place on the Crypto Forum Research 23 Group mailing list (cfrg@ietf.org), which is archived at 24 https://mailarchive.ietf.org/arch/search/?email_list=cfrg. 26 Source for this draft and an issue tracker can be found at 27 https://github.com/siyengar/verifiable-attribute-based-key- 28 derivation. 30 Status of This Memo 32 This Internet-Draft is submitted in full conformance with the 33 provisions of BCP 78 and BCP 79. 35 Internet-Drafts are working documents of the Internet Engineering 36 Task Force (IETF). Note that other groups may also distribute 37 working documents as Internet-Drafts. The list of current Internet- 38 Drafts is at https://datatracker.ietf.org/drafts/current/. 40 Internet-Drafts are draft documents valid for a maximum of six months 41 and may be updated, replaced, or obsoleted by other documents at any 42 time. It is inappropriate to use Internet-Drafts as reference 43 material or to cite them other than as "work in progress." 45 This Internet-Draft will expire on 26 August 2021. 47 Copyright Notice 49 Copyright (c) 2021 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 54 license-info) in effect on the date of publication of this document. 55 Please review these documents carefully, as they describe your rights 56 and restrictions with respect to this document. Code Components 57 extracted from this document must include Simplified BSD License text 58 as described in Section 4.e of the Trust Legal Provisions and are 59 provided without warranty as described in the Simplified BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 64 1.1. Requirements . . . . . . . . . . . . . . . . . . . . . . 3 65 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 66 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 4 67 2.1. Prime-Order Group Dependency . . . . . . . . . . . . . . 4 68 2.2. Other Conventions . . . . . . . . . . . . . . . . . . . . 4 69 2.3. Discrete log proofs . . . . . . . . . . . . . . . . . . . 4 70 3. Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . 5 71 3.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 5 72 3.2. Pre-Setup . . . . . . . . . . . . . . . . . . . . . . . . 6 73 3.3. Evaluate VOPRF . . . . . . . . . . . . . . . . . . . . . 7 74 4. Application considerations . . . . . . . . . . . . . . . . . 9 75 4.1. Metadata bits . . . . . . . . . . . . . . . . . . . . . . 9 76 4.2. Encoding metadata . . . . . . . . . . . . . . . . . . . . 9 77 5. Comparison with other approaches . . . . . . . . . . . . . . 9 78 5.1. Pairings . . . . . . . . . . . . . . . . . . . . . . . . 9 79 5.2. Partially oblivious PRF . . . . . . . . . . . . . . . . . 9 80 6. Security Considerations . . . . . . . . . . . . . . . . . . . 10 81 6.1. Cryptographic security . . . . . . . . . . . . . . . . . 10 82 6.1.1. n-Diffie Hellman exponent assumption . . . . . . . . 10 83 6.1.2. Selective security vs full security . . . . . . . . . 10 84 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 85 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 86 8.1. Normative References . . . . . . . . . . . . . . . . . . 11 87 8.2. Informative References . . . . . . . . . . . . . . . . . 11 88 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 12 89 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12 91 1. Introduction 93 A VOPRF allows a client and server to evaluate a psuedo-random 94 function "F(k, x)", with secret key "k", and input "x" without the 95 client learning the key "k" and the server learning the input "x". 96 Additionally in a VOPRF, the client can verify that the output was 97 computed using the key "k". 99 One challenge in VOPRFs is to be able to bind public metadata to the 100 output of the VOPRF while keeping the VOPRF both verifiable and 101 oblivious. Unlike the input x to the VOPRF, public metadata is not 102 meant to be secret to either the client or the server. This public 103 metadata is useful in applications where being able to bind 104 application context to a VOPRF output is criticial to the security of 105 the application. 107 In this draft we describe a mechanism to bind public metadata to a 108 VOPRF by deriving the public-private keypair that is used by the 109 VOPRF from the metadata [PrivateStats]. This method allows the use 110 of existing elliptic curve VOPRF ciphers while only changing the way 111 the secret key is derived. Additionally, the key derivation 112 mechanism of the public key can be verified by a client using non- 113 interactive zero-knowledge proofs to prove that the metadata specific 114 key is derived from a master secret. 116 The draft does not describe how metadata is used, but that left to 117 specific application protocols that use this public metadata 118 mechanism. 120 1.1. Requirements 122 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 123 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 124 "OPTIONAL" in this document are to be interpreted as described in BCP 125 14 [RFC2119] [RFC8174] when, and only when, they appear in all 126 capitals, as shown here. 128 1.2. Terminology 130 The following terms are used throughout this document. 132 * PRF: Pseudorandom Function. 134 * VOPRF: Verifiable Oblivious Pseudorandom Function. 136 * Client: Protocol initiator. Learns pseudorandom function 137 evaluation as the output of the protocol. 139 * Server: Computes the pseudorandom function over a secret key. 140 Learns nothing about the client's input. 142 * NIZK: Non-interactive zero knowledge. 144 * DLEQ: Discrete Logarithm Equality. 146 2. Preliminaries 148 The document defines extensions to the VOPRF required to support 149 metadata. This document depends on the following: 151 * "GG": A prime-order group implementing the API described in 152 [I-D.irtf-cfrg-voprf] as well as the additional APIs defined below 153 in Section 2.1. 155 * "Public Metadata": The public metadata is defined as an "n" bit 156 vector. To represent "b" values, an application could use "log b" 157 bits. 159 2.1. Prime-Order Group Dependency 161 We define new member functions on the prime-order group "GG" defined 162 in [I-D.irtf-cfrg-voprf]: 164 * ScalarMult(point, scalar): A member function of "GG" that 165 multiples an element in the group with a "scalar" from "GF(p)". 167 * NewGenerator(): A member function of "GG" that samples a new 168 generator for the group. 170 2.2. Other Conventions 172 All algorithm descriptions are written in a Python-like pseudocode. 173 All scalar multiplications are performed modulo "GF(p)". 175 2.3. Discrete log proofs 177 Zero knowledge proofs for statements on discrete-logs were summarized 178 by [Camenisch97]. We describe two algorithms used in this draft on 179 "GG" to prove discrete log statements. 181 "DLEQProve(k, A, B, C, D)" proves that "B = k * A" and "D = k * C" 182 without revealing the value of "k". This type of proof is used when 183 "k" is a secret value that should not be revealed to a verifier. 185 def DLEQProve(k, A, B, C, D): 186 r = GG.RandomScalar() 187 E = r * A 188 F = r * C 189 hashInput = A || B || C || D || E || F 190 cbytes = Hash(hashInput) 191 c = GG.HashToGroup(cbytes) 192 z = r + k * c 193 return (z, E, F) 195 "DLEQVerify(A, B, C, D, proof)" verifies that the proof generated by 196 "DLEQProve" is valid. 198 def DLEQVerify(A, B, C, D, proof): 199 hashInput = A || B || C || D || proof.E || proof.F 200 cbytes = Hash(hashInput) 201 c = GG.HashToGroup(cbytes) 202 cBE = cB + proof.E 203 cDF = cD + proof.F 204 zA = proof.z * A 205 zC = proof.z * C 206 return zA == cBE && zC == cDF 208 3. Protocol 210 3.1. Overview 212 A server first generates a main key pair "(skM, pkM)", where "skM" is 213 the servers main secret key and "pkM" is the servers main public key. 214 Given public metadata "t", the server generates a keypair specific to 215 the metadata "t", "(skT, pkT) = PKGen(t, skM)", where "skT" is the 216 secret key for metadata "t" and "pkT" is its public key. Once a 217 metadata specific keypair is available, the server can be used to 218 evaluate a "VOPRF(skT, x)", where "x" is the input for the user. 219 When the VOPRF is in verifiable mode, the client also receives a NIZK 220 proof that "skT" and "pkT" are generated from "skM" and "pkM" (in 221 verifiable mode). 223 Client(pkM, input, metadata) Server(skM, pkM, metadata) 224 ---------------------------------------------------------- 225 blind, blindedElement = Blind(input) 227 blindedElement 228 ----------> 229 skT, pkT, pkProofs = PKGen(skM, metadata) 231 evaluatedElement, proof = Evaluate(skT, pkT, blindedElement) 233 evaluatedElement, pkT, proof, pkProofs 234 <---------- 236 pkVerified = PKVerify(pkM, pkT, pkProofs) 238 output = Finalize(input, blind, evaluatedElement, blindedElement, pkT, proof) 240 In the following sections we describe modifications to the VOPRF 241 scheme in [I-D.irtf-cfrg-voprf] to be able to augment an existing 242 VOPRF with public metadata. 244 3.2. Pre-Setup 246 We augment the offline context setup phase phase of the VOPRF in 247 [I-D.irtf-cfrg-voprf]. In this phase, both the client and server 248 create a context used for executing the online phase of the protocol. 250 Prior to this phase, the key pair ("skM", "pkM") should be generated 251 by using "MasterKeyGen(metadataBits)". This keypair is used as the 252 master key for VOPRFs. This master key is not used directly within 253 the VOPRF, however, public metadata is used to generate attribute 254 specific keys that are used in the VOPRF evaluation. 256 "metadataBits" here is the number of bits of metadata that are 257 required for the application of the VOPRF. "MasterKeyGen" samples 258 "n" scalar elements "a0, a1, ... an" from the group and a new 259 generator "h". "ai" is a group element associated with the "i"th bit 260 of metatadata. Public parameters are calculated by performing scalar 261 multiplicaton of "h" with each "ai". 263 def MasterKeyGen(metadataBits): 264 ais = [] 265 his = [] 266 h = GG.NewGroupGenerator() 267 a0 = GG.RandomScalar() 268 for i in range(metadataBits): 269 ai = GG.RandomScalar() 270 ais.append(ai) 271 for i in range(metadataBits): 272 hi = GG.ScalarMult(h, ais[i]) 273 his.append(hi) 274 P0 = GG.ScalarBaseMult(a0) 275 skM = (a0, ais) 276 pkM = (GG.g, h, metadataBits, P0, his) 277 return (skM, pkM) 279 3.3. Evaluate VOPRF 281 When client and server have agreed on the metadata to use for the 282 protocol, the server first executes "PKGen(skM, metadata)" to 283 generate "skT" and the proof that "skT" is derived from "skM". This 284 draft does not discuss how the client and server agree on the 285 metadata to use, and that is left to the application. 287 Note that "skM" has one group element for each bit of the metadata 288 "t", as well as the extra group element "a0". Given metadata "t", 289 "PKGen" calculates the attribute specific key by performing a scalar 290 multiplication of all the group elements in "skM" for each bit of "t" 291 that is set to "1". 293 To prove that "skT" is derived from "skM", "GenProofs" generates upto 294 "n" discrete log proofs, one for each bit of the metadata. Each 295 proof proves that "hi = ai * h" and "Pi = ai * Pi-1". This proves 296 that "ai" was correctly used for bit "i". 298 def PKGen(t, skM, pkM): 299 pis = [] 300 pi = skM.a0 301 keyBits = len(metadata) 302 for i in range(keyBits): 303 if t[i] == 0: 304 pis.append(None) 305 continue 306 pi = pi * skM[i] 307 pis.append(pi) 308 skT = pi 309 pkT = GG.ScalarMultBase(skT) 310 pkProofs = GenProofs(metadata, pis, skM, pkM) 311 return (skT, pkT, pkProofs) 313 def GenProofs(t, pis, skM, pkM): 314 proofs = [] 315 numProofs = len(pis) 316 previousPi = pkM.P0 317 for i in range(numProofs): 318 if t[i] == 0: 319 continue 320 Pi = GG.ScalarBaseMult(pis[i]) 321 proofi = DLEQProve(skM.ais[i], pkM.h, pkM.his[i], previousPi, Pi) 322 proofs.append((Pi, proofi)) 323 previousPi = Pi 324 return proofs 326 Once "PKGen" has generated a public key for a set of "metadata" bits, 327 the client can verify that "skT" is derived from "skM", using 328 "PKVerify(pkM, pkT, pkProofs)". This verifies the sequence of 329 discrete-log proofs generated by "PKGen". 331 def PKVerify(pkM, pkT, t, pkProofs): 332 previousPi = pkM.P0 333 proofVerified = True 334 for proof in pkProofs: 335 if t[i] == 0: 336 continue 337 Pi = proof.Pi 338 verified = DLEQVerify(pkM.h, pkM.his[i], previousPi, Pi, proof) 339 proofVerified = proofVerified & verified 340 previousPi = Pi 341 return proofVerified 343 A server can use "skT" generated from "PKGen" as the private key for 344 the VOPRF mechanism in [I-D.irtf-cfrg-voprf]. 346 4. Application considerations 348 4.1. Metadata bits 350 Applications must choose the maximum size in bits of the metadata 351 that they would like to support before setup of the protocol. The 352 size of the metdata impacts the following - Size of the public key - 353 Computation time for attribute and proof generation 355 For "b" being the number of metadata values needed for an 356 application, the size of the public key scales as "O(log b)". 357 Computation also scales as "O(log b)" number of scalar 358 multiplications for generating a public key and number of discrete 359 log proof generations and verifications required. 361 4.2. Encoding metadata 363 Applications must choose the number of bits of metadata required in 364 order to be able to represent all possible values for the 365 application's metadata. They MUST define their own mechanism encode 366 metadata into bits. 368 5. Comparison with other approaches 370 5.1. Pairings 372 It is possible to construct VOPRFs with public metadata using 373 pairing-friendly curves [I-D.draft-irtf-cfrg-pairing-friendly-curves] 374 with an approach in [Pythia15]. 376 However this approach has some disadvantages. Pairings are not 377 widely available in cryptographic libraries and are also not 378 compatible with existing deployed VOPRFs like in 379 [I-D.irtf-cfrg-voprf]. The approach described here allows 380 applications to use existing deployed VOPRFs while only changing the 381 mechanism of key derivation. 383 5.2. Partially oblivious PRF 385 Another approach that could be used to bind metadata to a VOPRF 386 evaluation is to use a similar method in [pOPRF18] which uses a 387 regular "PRF(k, metadata)" to derive a secret key based on the 388 metadata which is then used in the VOPRF. 390 The verifiability of public key could be achieved by publishing every 391 public key for each metadata value in a central repository, which 392 could be checked by the client. For large number of values of 393 metadata "b", this approach generates "O(b)" keys, which can be 394 difficult for clients and servers to manage. In contrast, the 395 approach described in this document, the size of the master public 396 key is "O(log b)", and the public keys of each attribute can be 397 verified against the master key later. 399 6. Security Considerations 401 6.1. Cryptographic security 403 The security properties of a VOPRF with public metadata are derived 404 from the proof in [PrivateStats] that the VOPRF defined here is a PRF 405 even after giving an adversary access to proofs from "PKGen". The 406 VOPRF defined in [I-D.irtf-cfrg-voprf] when combined with attributes 407 results in a PRF output of "PRF(skM, t, x) = a0^t1 * a1^t2 ... * 408 an^tn * H(x)". 410 6.1.1. n-Diffie Hellman exponent assumption 412 There are several variants of the Diffie-Hellman assumption and the 413 proof of the VOPRF with public metadata is based on the n-Diffie 414 Hellman exponent assumption. The n-DHE problem requires an adversary 415 to distinguish the n+1-th power of a secret "a" hidden in the 416 exponent from a random element in "GG". 418 Sample uniformly at random "d" in {0,1}, and a random "r" from 419 "GF(p)": - Given "G" is a generator in "GG" - Given "G", "a * G" , 420 "(a^2) * G", ..., "(a^n) * G" - if "d" == 0: "C = a^(n+1) * G" else: 421 "C = r * a" 423 Output "d' == d" 425 6.1.2. Selective security vs full security 427 The security properties of the VOPRF with public metadata described 428 in this draft is based on the proof in [PrivateStats] that the VOPRF 429 is a selectively-secure VRF. Selective-security is a weaker notion 430 of security that requires an adversary to commit to the challenge 431 input (in this case, the metadata and value x) before trying to break 432 the PRF. 434 In practice, if target inputs are independent of the system 435 parameters, there should not be an advantage to allowing the attacker 436 to choose the target after seeing system parameters. To convert our 437 VOPRF with public metadata to one satisfying a full security notion 438 in the random oracle model, we require that the metadata be hashed 439 with a collision-resistant hash function with sufficiently large 440 output (>=256-bits). For smaller metadata sets therefore, the 441 selectively-secure VRF is much more efficient. 443 7. IANA Considerations 445 This document has no IANA actions. 447 8. References 449 8.1. Normative References 451 [I-D.draft-irtf-cfrg-pairing-friendly-curves] 452 Sakemi, Y., Kobayashi, T., Saito, T., and R. S. Wahby, 453 "Pairing-Friendly Curves", Work in Progress, Internet- 454 Draft, draft-irtf-cfrg-pairing-friendly-curves-09, 16 455 November 2020, . 458 [I-D.irtf-cfrg-voprf] 459 Davidson, A., Faz-Hernandez, A., Sullivan, N., and C. A. 460 Wood, "Oblivious Pseudorandom Functions (OPRFs) using 461 Prime-Order Groups", Work in Progress, Internet-Draft, 462 draft-irtf-cfrg-voprf-06, 21 February 2021, 463 . 465 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 466 Requirement Levels", BCP 14, RFC 2119, 467 DOI 10.17487/RFC2119, March 1997, 468 . 470 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 471 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 472 May 2017, . 474 8.2. Informative References 476 [Camenisch97] 477 "Proof Systems for General Statements about Discrete 478 Logarithms", 479 . 481 [pOPRF18] "Threshold Partially-Oblivious PRFs with Applications to 482 Key Management", . 484 [PrivateStats] 485 "PrivateStats, De-Identified Authenticated Logging at 486 Scale", . 488 [Pythia15] "The Pythia PRF Service", 489 . 491 Acknowledgments 493 TODO acknowledge. 495 Authors' Addresses 497 Subodh Iyengar 498 Facebook 500 Email: subodh@fb.com 502 Ananth Raghunathan 503 Facebook 505 Email: ananthr@fb.com