Privacy Preserving Measurement M. Thomson Internet-Draft Mozilla Intended status: Standards Track B. Savage Expires: 9 January 2025 Meta 8 July 2024 High Performance Pseudorandom Secret Sharing (PRSS) draft-thomson-ppm-prss-00 Abstract Pseudorandom secret sharing (PRSS) enables the generation of a large number of shared pseudorandom values from a single shared seed. This is useful in contexts where a large amount of shared randomness is needed, such as multi-party computation (MPC). About This Document This note is to be removed before publishing as an RFC. The latest revision of this draft can be found at https://private- attribution.github.io/i-d/draft-thomson-ppm-prss.html. Status information for this document may be found at https://datatracker.ietf.org/doc/draft-thomson-ppm-prss/. Discussion of this document takes place on the Privacy Preserving Measurement Working Group mailing list (mailto:ppm@ietf.org), which is archived at https://mailarchive.ietf.org/arch/browse/ppm/. Subscribe at https://www.ietf.org/mailman/listinfo/ppm/. Source for this draft and an issue tracker can be found at https://github.com/private-attribution/i-d. 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." Thomson & Savage Expires 9 January 2025 [Page 1] Internet-Draft PRSS July 2024 This Internet-Draft will expire on 9 January 2025. Copyright Notice Copyright (c) 2024 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 Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Two-Party Protocol . . . . . . . . . . . . . . . . . . . 3 2. Conventions and Definitions . . . . . . . . . . . . . . . . . 3 3. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4. Key Agreement . . . . . . . . . . . . . . . . . . . . . . . . 5 5. Randomness Contexts . . . . . . . . . . . . . . . . . . . . . 6 5.1. Entropy Extraction . . . . . . . . . . . . . . . . . . . 6 5.2. Creating Randomness Contexts . . . . . . . . . . . . . . 8 6. Pseudorandom Function . . . . . . . . . . . . . . . . . . . . 8 6.1. Cached-Key AES PRF . . . . . . . . . . . . . . . . . . . 9 7. Randomness Usage Modes . . . . . . . . . . . . . . . . . . . 10 7.1. Sequential Randomness . . . . . . . . . . . . . . . . . . 10 7.2. Indexed Randomness . . . . . . . . . . . . . . . . . . . 11 8. Sampling from the PRF Output . . . . . . . . . . . . . . . . 11 8.1. Available Randomness . . . . . . . . . . . . . . . . . . 11 8.2. Binary Sampling . . . . . . . . . . . . . . . . . . . . . 12 8.3. Rejection Sampling . . . . . . . . . . . . . . . . . . . 12 8.4. Oversampling . . . . . . . . . . . . . . . . . . . . . . 12 9. Security Considerations . . . . . . . . . . . . . . . . . . . 13 9.1. Usage Limit Analysis . . . . . . . . . . . . . . . . . . 13 9.2. Formal Analysis . . . . . . . . . . . . . . . . . . . . . 14 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 15 11.1. Normative References . . . . . . . . . . . . . . . . . . 15 11.2. Informative References . . . . . . . . . . . . . . . . . 16 Appendix A. Alternative Designs . . . . . . . . . . . . . . . . 17 Appendix B. Application to 2-of-3 Replicated Secret Sharing . . 17 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 18 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 18 Thomson & Savage Expires 9 January 2025 [Page 2] Internet-Draft PRSS July 2024 1. Introduction A number of protocols benefit from having some means by which protocol entities agree on a random value. This is particularly useful in multi-party computation (MPC), such as the three-party, honest majority setting, where many protocols rely on being able to generate large amounts of shared randomness. Pseudorandom secret sharing (PRSS) [CDI05] is a means of non- interactively establishing multiple shared values from a single shared secret. This document describes a concrete PRSS protocol that can efficiently produce large quantities of shared randomness. This protocol is parameterized and offers algorithm agility. This protocol combines a chosen key encapsulation method (KEM) and key derivation function (KDF) to generate shared secrets. These shared secrets form the basis of a randomness context (Section 5) in which a chosen lightweight pseudorandom function (PRF) is used to generate large amounts of shared randomness. Each randomness context can either be used as a sequential source of randomness Section 7.1 or as an indexed source Section 7.2, depending on need. 1.1. Two-Party Protocol This document describes a PRSS protocol for two parties. The set of KEMs defined only work in a two-party context. If the goal is to create randomness that is shared with more than one entity, group key exchange methods, such as MLS [MLS], could be adapted as a means of key agreement, retaining the other elements of this protocol unchanged. 2. Conventions and Definitions 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. This document uses the term "participant" to refer to entities that execute the protocol. Thomson & Savage Expires 9 January 2025 [Page 3] Internet-Draft PRSS July 2024 Notation for KEM and KDF functions is taken from [HPKE]. e = I2OSP(n, i) and i = OS2IP(e) functions are taken from [RSA] and describe encoding and decoding non-negative integers to and from a byte string, respectively, using network byte order. rev() reverses the order of a sequence of bytes; concat() concatenates multiple sequences of bytes; xor() computes the exclusive or of byte strings or integers of the same type; x[a..b] takes a range of bytes indexed from a (inclusive) to b (exclusive) from x. 3. Overview A PRSS begins with the establishment of a shared secret. This protocol uses a KEM to establish this value. This is the only communication that occurs between participants; see Figure 1 and Section 4. +----------+ +----------+ | Sender | | Receiver | +----+-----+ +----+-----+ | | |<---------- pk -----------+ | | +---------- enc ---------->| | | Figure 1: Key Agreement From this shared secret, a KDF is used to generate one or more randomness contexts; see Section 5. Each randomness context can be used independently to produce many random values through the use of a PRF; see Figure 2 and Section 6. Thomson & Savage Expires 9 January 2025 [Page 4] Internet-Draft PRSS July 2024 shared secret | | v Extract() | | |\ | `--> Expand(secret, info_0) --> PRF(context_0, 0) | --> PRF(context_0, 1) | --> PRF(context_0, 2) | --> PRF(context_0, 3) | --> PRF(context_0, 4) | --> PRF(context_0, 5) | ... |\ | `--> Expand(secret, info_1) --> PRF(context_1, 0) |\ | `--> Expand(secret, info_2) --> PRF(context_2, 0) ... Figure 2: PRSS Key Schedule This document describes both sequential (Section 7.1) and indexed (Section 7.2) access to randomness contexts, with different sampling methods (Section 8). 4. Key Agreement The first stage of the protocol is key agreement. In this phase, participants communicate and establish a shared secret. Protocol participants are assumed to have a means of authenticating each other. A confidential communications channel is not necessary, though the use of TLS [TLS] for authentication purposes will also provide confidentiality in most cases. This document uses the system of describing, naming, and identifying KEMs defined in [HPKE]. For use in PRSS, a KEM is first chosen for use. KEM identifiers from Section 7.1 of [HPKE] are used for identification and can be used in negotiation. Once a KEM is chosen, one participant is assigned the "sender" role; the other participant becomes the "receiver". The receiver commences by generating a KEM key pair as follows: Thomson & Savage Expires 9 January 2025 [Page 5] Internet-Draft PRSS July 2024 def sk, pk_bytes = KeyGen(kem): sk, pk = kem.GenerateKeyPair() pk_bytes = kem.SerializePublicKey(pk) The receiver advertises their public key to the sender by transmitting pk_bytes. The sender then encapsulates the KEM shared secret as follows: def ss, enc = Send(kem, pk_bytes): pk = kem.DeserializePublicKey(pk_bytes) ss, enc = kem.Encap(pk) The sender then sends the encapsulated public key, enc, to the receiver. The receiver decapsulates this value to obtain the shared secret, secret: def ss = Receive(kem, sk, enc): ss = kem.Decap(enc, sk) This produces a value, ss, that is Nsecret bytes in length. 5. Randomness Contexts The single shared secret that is produced by a KEM is not suitable for use as a source of randomness. A key derivation function (KDF) is used to first extract randomness from the secret and then to expand it for use in different contexts. A randomness context is a concept that is defined by protocols that use PRSS. Each context is identified by a unique string of bytes. This string is passed to the KDF to produce a shared value that is unique to that context. This document uses the system of describing, naming, and identifying KEMs defined in [HPKE]. A KDF is first chosen for use. KDF identifiers from Section 7.2 of [HPKE] are used for identification and can be used in negotiation. 5.1. Entropy Extraction A labeled method of entropy extraction is used by this document to ensure that the randomness provided is bound to both the chosen protocol parameters (KEM, KDF, and PRF) as well as the values chosen by participants during key agreement. Each participant constructs a byte sequence by concatenating the following sequences of bytes: Thomson & Savage Expires 9 January 2025 [Page 6] Internet-Draft PRSS July 2024 1. The ASCII encoding [ASCII] of the string "PRSS-00". 2. The identifier for the chosen KEM from Section 7.1 of [HPKE], encoded in two bytes in network byte order. 3. The identifier for the chosen KDF from Section 7.2 of [HPKE], encoded in two bytes in network byte order. 4. The identifier for the chosen PRF from Section 6, encoded in two bytes in network byte order. 5. A two byte encoding of the KEM parameter Npk in network byte order. 6. The value of pk_bytes, the public key from the receiver. 7. A two byte encoding of the KEM parameter Nenc in network byte order. 8. The value of enc, the key encapsulation from the sender. Note: Draft versions of this protocol will be identified as "PRSS- 00". The suffix of this string matches the draft revision in which the scheme last changed. The string will not be updated unless the scheme changes in an incompatible fashion. A final version might either omit this suffix or include a different string. This byte sequence is provided as the ikm input to the Extract() function of the chosen KDF. The shared secret, ss, is provided as the salt input, as follows: def extracted = LabeledExtract(kem, kdf, prf, ss, pk_bytes, enc): label = concat( ascii("PRSS-00"), I2OSP(kem.id, 2), I2OSP(kdf.id, 2), I2OSP(prf.id, 2), I2OSP(kem.Npk, 2), pk_bytes, I2OSP(kem.Nenc, 2), enc, ) extracted = kdf.Extract(salt = ss, ikm = label) This process extracts shared entropy that is bound to this protocol and the context in which it was created. Thomson & Savage Expires 9 January 2025 [Page 7] Internet-Draft PRSS July 2024 5.2. Creating Randomness Contexts A randomness context is identified by a byte sequence. Applications that use PRSS need to describe how each randomness context it uses is identified. Participants with the same shared entropy and the same randomness context identifier will produce the same randomness. A randomness context is produced by invoking the Expand() function of the chosen KDF, passing the shared entropy generated in Section 5.1 as the prk input, the byte sequence that identifies the context (ctxᵢd) as the info input, and the PRF parameter Nk as the L input (see Section 6), as follows: def context = Context.new(kdf, prf, extracted, ctxᵢd): context = kdf.Expand(prk = extracted, info = ctxᵢd, L = prf.Nk) The expanded entropy produced by this process is the only information that is essential for a randomness context, though a real instantiation might also track which KEM, KDF, and PRF are used. 6. Pseudorandom Function A PRF is instantiated with a secret key, k, and provides a single function PRF(i). This document adapts the PRF interface to take a non-negative integer as input and to produce a non-negative integer as output. New PRF definitions MUST define three parameters: * the size of the key (Nk), * the maximum allowed value for the input (Mi), and * the maximum value that can be produced as output (Mo). Importantly, the maximum input value SHOULD reflect a limit that is based on keeping attacker advantage negligible relative to an ideal PRF. Any advantage needs to be bounded when an attacker is able to obtain output values for all input values between 0 (inclusive) and that maximum (exclusive). The maximum input (Mi) is therefore likely to be less than the underlying function might otherwise permit. This assumes the usage modes from Section 7; alternative usage modes that pass inputs that are randomized or sparse across the entire input space of the underlying function are possible, but these have not been specified. Thomson & Savage Expires 9 January 2025 [Page 8] Internet-Draft PRSS July 2024 Each PRF is identified by a two-byte identifier, allocated using the process in Section 10. 6.1. Cached-Key AES PRF This document defines a PRF based on that described in [GKWY20]. This provides a PRF that has circular correlation robustness. This PRF uses the AES function, either AES-128 or AES-256, as defined in [AES]. Both of these functions accept a 16 byte input. The primary difference in these functions is the size of the key; AES-128 uses a 16 byte key, whereas AES-256 uses a 32 byte key. This information is summarized in Table 1. +=============+============+====+======+=======+ | PRF Name | Identifier | Nk | Mi | Mo | +=============+============+====+======+=======+ | PRF_AES_128 | 0x0001 | 16 | 2^42 | 2^128 | +-------------+------------+----+------+-------+ | PRF_AES_256 | 0x0002 | 32 | 2^43 | 2^128 | +-------------+------------+----+------+-------+ Table 1: Pseudorandom Function Summary Both AES PRFs use the same process: 1. The input, i, is converted to a 16-byte input using a little- endian encoding. 2. These bytes are then input to the AES function to produce a 16 byte output. 3. The AES input and output are XORed produce a 16 byte sequence. 4. The byte sequence is interpreted as an integer using little- endian encoding to produce the output randomness. The process in pseudocode is: def randomness = Context.PRF(i): input = rev(I2OSP(i, 16)) output = aes(k, input) r_bytes = xor(output, input) randomness = OS2IP(rev(r_bytes)) Thomson & Savage Expires 9 January 2025 [Page 9] Internet-Draft PRSS July 2024 This step is performance-sensitive, so little endian encoding is chosen to match the endianness of most hardware that is in use. This PRF uses a constant key, which allows implementations to avoid computing the key expansion on each PRF invocation by caching the expanded values. Note: A similar PRF core is described in Section 6.2.2 of [VDAF], based on the analysis in [GKWWY20]. The function described in this document operates from a limited input domain that always results in the high bits being zero in all cases, making the difference between the two approaches negligible; these approaches consequently only differ in the placement of the input bits. 7. Randomness Usage Modes The same PRF input MUST NOT be used more than once. Using the same input more than once will produce identical outputs, which might be exploited by an attacker. This section describes two basic access modes for randomness contexts that provide some safeguards against accidental reuse of inputs: * A sequential randomness context provides access using a counter; see Section 7.1. * An indexed randomness context provides concurrent access; see Section 7.2. These usages are incompatible; only one mode of access can be used for a given context. These usage modes are intended to use a contiguous block of input values, starting from 0. The definition of the Mi parameter of the PRF function (see Section 6.1) assumes this usage model. 7.1. Sequential Randomness In this mode, a counter, starting at zero, is retained with the randomness context. Each use of the randomness context first uses that counter as input to the PRF, then increments it. def randomness = Context.next(): randomness = Context.PRF(this.counter) this.counter = this.counter + 1 This is the simplest access scheme, which is compatible with any sampling method; see Section 8. Thomson & Savage Expires 9 January 2025 [Page 10] Internet-Draft PRSS July 2024 7.2. Indexed Randomness Indexed randomness ties the use of the randomness context to a sequence of application records. The processing of each record is defined to each use M invocations of a certain randomness context. Therefore, for a given record, r, and usage, m, the context is invoked as context.PRF(r * M + m). The simplest indexing scheme sets M to 1. Indexed usage is best suited to applications where individual records might be processed concurrently. Using indices based on identifiers from an application, such as record indices, can ensure that the same PRF input is only used once and frees the randomness context from maintaining its own counter. Binary sampling (Section 8.2) or oversampling (Section 8.4) are best suited for use with indexed modes. Rejection sampling (Section 8.3) is likely to be unsuitable for an indexed mode because it requires an unpredictable number of PRF invocations to successfully complete. 8. Sampling from the PRF Output PRSS natively produces a uniformly random value in the range from 0 (inclusive) to Mo (exclusive). Many applications of PRSS require the selection of a uniform random value from a fixed range of values. 8.1. Available Randomness The total randomness available is limited by the entropy from the chosen KEM, KDF, and PRF. Each KEM is only able to convey a maximum amount of entropy. Similarly, each KDF is limited in the amount of entropy it only able to retain. Finally, each PRF also has limits that might further reduce the maximum entropy available. Selecting values from a range that is larger than the available entropy will affect the uniformity of the output. In particular, these methods MUST NOT be used to select from a range that has more values than the Mo parameter of the chosen PRF. If values larger than Mo are needed, the output of multiple PRF invocations can be combined. With k invocations, the effective value of Mo increases to Mo^k. Thomson & Savage Expires 9 January 2025 [Page 11] Internet-Draft PRSS July 2024 8.2. Binary Sampling If the range of desired values is a whole power of 2, then simple bit operations can be used to obtain a value. For a maximum of 2^n (exclusive), bitwise operations can produce a value of randomness & ((1 << n) - 1). Binary sampling produces uniformly random values with the only drawback being the constraint on its output range. For small values of n, the same PRF invocation could be used to produce multiple values, depending on the value of Mo for the chosen PRF. 8.3. Rejection Sampling Rejection sampling takes random values until the resulting value is in range. For values in the range 0 (inclusive) to m (exclusive), the value m is rounded up to the next power of 2; that is, an integer n is chosen such that 2^(n-1) < m <= 2^n. Then, binary sampling (Section 8.2) is applied repeatedly for this larger range until the resulting value is less than m. Rejection sampling provides uniform randomness across the range from 0 to m without bias. However, rejection sampling can require an indefinite number of PRF invocations to produce a result. Rejection is more likely -- and so the expected number of PRF invocations increases -- when m is closer to 2^(n-1) than 2^n. This can make rejection sampling unsuitable for use with indexed randomness (Section 7.2). Rejection sampling might be used a limited number of times before falling back to oversampling (Section 8.4), which can reduce oversampling bias while capping the number of PRF invocations. 8.4. Oversampling For a target range that is much smaller than the range of values produced by the PRF, reducing the PRF output modulo the maximum in the range can produce outputs with negligible bias. Thomson & Savage Expires 9 January 2025 [Page 12] Internet-Draft PRSS July 2024 For example, an application goal might seek to produce values in the prime field p = 2^61 - 1. Using the AES PRF, where Mo is 2^128, and reducing its output modulo p results in a bias that causes the first 64 values of the field to be chosen with a probability of about 2^-67 more than other values. This degree of bias might be acceptable in some applications. To avoid excessive bias, applications SHOULD NOT use oversampling where the output is less than 2^48 times smaller than Mo. The output of multiple PRF invocations could be combined to reduce bias. 9. Security Considerations This document describes a small component of a larger system. A discussion of considerations necessary to ensure correct application of the included techniques is provided in relevant sections. This section concentrates on a more general analysis of these mechanisms. 9.1. Usage Limit Analysis The usage limits in Section 6.1 ensure that attacker advantage remains small. Theorem 4 of [GKWY20] models the underlying permutation function as an ideal PRP and shows that attacker advantage comprises two components: * a computational limit of q²/(2*2^k) that is based solely on attacker work (q) and the key size (k) of the permutation * a usage limit of 2pq/2^b that provides advantage proportional to the number of uses of the PRF (p), with the entropy of the pseudorandom function (b) acting to counteract attacker advantage The number of uses (p) are only affected by the second component, as the first component is unaffected by usage of the permutation. However, the first component guides our assumptions about the number of times the attacker might be willing to invoke the permutation (q). The result shows that statistical security is provided based on the birthday bound. For instance, q being 2^64 results in a disastrous advantage of 0.5 for the AES-128 key size of 128 bits. This first term therefore places an upper bound on the value that q can take before an attacker can rely solely on this computational limit. We use this first component to bound the value of q for the second component. If advantage is equally divided between each component we can bound q to be at most 2⁽(k-a)/2), where a is the desired attacker advantage in bits (that is, advantage is at most 2^-a). Thomson & Savage Expires 9 January 2025 [Page 13] Internet-Draft PRSS July 2024 Using that value for q and an advantage of (2^a)/2 for the second component leads to a limit for p of 2⁽b-(k+a)/2-2). For example, to obtain 40 bits of security, the value of p for AES-128 is limited to 2^42, which assumes a value of q no more than 2^44. For AES-256, the larger key size means that the first component is negligible for any value of q, unless p and a are both very small. This is due to AES-256 having the same 128-bit block size as AES-128. Consequently, increasing q only reduces the value of p. On this basis, the same q value can be used for AES-256 as for AES- 128. The usage limit for AES-256 can be doubled to 2⁽b-(k+a)/2-1) (2^43 for 40 bits of security; the first component is a negligible 2^-169). This analysis models AES as an ideal pseudorandom permutation. 9.2. Formal Analysis TODO 10. IANA Considerations This document establishes a new registry for "PRF Functions", under the grouping "PRSS". This registry operates on a "Expert Review" for provisional registrations or the "Specification Required" policy for permanent registrations [RFC8126]. Experts for the registry are advised to reject registrations only when the requests are invalid, abusive, or duplicative of existing entries. New entries for the "PRF Functions" registry MUST include the following information: Name: A short mnemonic for the PRF. Identifier: An identifier from the range 0 to 65535 (inclusive). Nk: The number of bytes in the PRF key. Mi: The maximum value of the PRF input. Mo: The maximum value of the PRF output. Status: Either "permanent" or "provisional". Specification: A reference to a specification for the PRF. Citing a specification is optional for provisional registrations. Last Updated: The date of when the registration was last updated. The name and identifier MUST be unique within this registry. No special allowance is made for private use or experimentation in this registry. People conducting experiments are encouraged to provisionally register a codepoint so that conflicting use of the Thomson & Savage Expires 9 January 2025 [Page 14] Internet-Draft PRSS July 2024 same identifier can be avoided. New PRFs are encouraged to use an identifier that is selected at random. IANA are advised not to perform allocation for identifiers, but to use the identifier that is provided with the registration. Provisional registrations MAY be removed on request. Experts can approve removal after having first attempted to determine that the value is no longer in use and attempting to contact registrants. Two months notice MUST be provided before removing a registration, even when the original registrant requests removal. Any entry that are in standards track RFCs or that has been updated in the past 24 months cannot be removed. A request to update an entry can be made at any time; any request only refreshes the "Last Updated" field can be allowed automatically, without consulting the assigned experts. Starting values for the registry are shown in Table 1; these entries are given a "permanent" status and entries reference Section 6 of this document. 11. References 11.1. Normative References [AES] "Advanced encryption standard (AES)", National Institute of Standards and Technology, DOI 10.6028/nist.fips.197, November 2001, . [ASCII] Cerf, V., "ASCII format for network interchange", STD 80, RFC 20, DOI 10.17487/RFC0020, October 1969, . [HPKE] Barnes, R., Bhargavan, K., Lipp, B., and C. Wood, "Hybrid Public Key Encryption", RFC 9180, DOI 10.17487/RFC9180, February 2022, . [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC8126] Cotton, M., Leiba, B., and T. Narten, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 8126, DOI 10.17487/RFC8126, June 2017, . Thomson & Savage Expires 9 January 2025 [Page 15] Internet-Draft PRSS July 2024 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, . [RSA] Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2", RFC 8017, DOI 10.17487/RFC8017, November 2016, . 11.2. Informative References [CDI05] Cramer, R., Damgård, I., and Y. Ishai, "Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation", Springer Berlin Heidelberg, Theory of Cryptography pp. 342-362, DOI 10.1007/978-3-540-30576-7_19, ISBN ["9783540245735", "9783540305767"], 2005, . [GKWWY20] Guo, C., Katz, J., Wang, X., Weng, C., and Y. Yu, "Better Concrete Security for Half-Gates Garbling (in the Multi- instance Setting)", Springer International Publishing, Advances in Cryptology – CRYPTO 2020 pp. 793-822, DOI 10.1007/978-3-030-56880-1_28, ISBN ["9783030568795", "9783030568801"], 2020, . [GKWY20] Guo, C., Katz, J., Wang, X., and Y. Yu, "Efficient and Secure Multiparty Computation from Fixed-Key Block Ciphers", IEEE, 2020 IEEE Symposium on Security and Privacy (SP), DOI 10.1109/sp40000.2020.00016, May 2020, . [MLS] Barnes, R., Beurdouche, B., Robert, R., Millican, J., Omara, E., and K. Cohn-Gordon, "The Messaging Layer Security (MLS) Protocol", RFC 9420, DOI 10.17487/RFC9420, July 2023, . [TLS] Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, . [VDAF] Barnes, R., Cook, D., Patton, C., and P. Schoppmann, "Verifiable Distributed Aggregation Functions", Work in Progress, Internet-Draft, draft-irtf-cfrg-vdaf-10, 8 July 2024, . Thomson & Savage Expires 9 January 2025 [Page 16] Internet-Draft PRSS July 2024 Appendix A. Alternative Designs Where a small number of shared secrets is desired, communication can be a good substitute for the methods described in this document. Depending on the context, protocol participants can use one of a range of methods to agree on a random value. This might involve the use of the KEM and KDF method described in Section 4, a commit-then- reveal protocol, or one of many alternative protocols. TLS exporters Section 7.5 of [TLS] are an existing example of pseudorandom secret sharing. TLS exporters are suitable for small numbers of secrets if a TLS connection is available for use, but TLS exporters are an not efficient means of generating large amounts of randomness. In some applications, a TLS exporter might be used in place of the KEM to produce a shared secret; alternatively, the randomness context identifier might be provided as context to a TLS exporter so that a randomness context might be produced directly. Appendix B. Application to 2-of-3 Replicated Secret Sharing This section describes how PRSS might be used to produce replicated shares for use with replicated secret sharing MPC protocols that use additive or XOR secret sharing. [CDI05] describes how to use PRSS for protocols that use polynomial shares. The simplest replicated secret sharing involves three participants that are arranged logically in a ring. Each participant receives two of the three shares of values. In this scheme, each participant has one share in common with the participant to its left and right respectively. Executing PRSS in this setting requires use of the protocol in a pairwise fashion; each participant executes the protocol once with the participant to its left and once with the participant to its right. As long as participants agree on parameters - which randomness context is used (Section 5), which mode is used (Section 7), which index (if using an indexed mode; Section 7.2), and the sampling method (Section 8) - this produces replicated shares of a random value that is not known to any single participant. [CDI05] also describes how shares of a known, specific value might be produced using the same scheme, but this is more trivially accomplished in this setting by setting a pre-arranged share value to the desired value and all others to zero. Thomson & Savage Expires 9 January 2025 [Page 17] Internet-Draft PRSS July 2024 Acknowledgments TODO acknowledge. Authors' Addresses Martin Thomson Mozilla Email: mt@lowentropy.net Ben Savage Meta Email: btsavage@meta.com Thomson & Savage Expires 9 January 2025 [Page 18]