High Performance Pseudorandom Secret Sharing (PRSS)

Internet-Draft	PRSS	August 2024
Thomson & Savage	Expires 10 February 2025	[Page]

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).¶

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.¶

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.¶

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:¶

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 secret, enc, to the receiver. The receiver decapsulates this value to obtain the shared 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 KDFs 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:¶

The ASCII encoding [ASCII] of the string "PRSS-00".¶
The identifier for the chosen KEM from Section 7.1 of [HPKE], encoded in two bytes in network byte order.¶
The identifier for the chosen KDF from Section 7.2 of [HPKE], encoded in two bytes in network byte order.¶
The identifier for the chosen PRF from Section 6, encoded in two bytes in network byte order.¶
The value of pk_bytes, the public key from the receiver.¶
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),
            pk_bytes,
            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.¶

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_id) 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_id):
    context = kdf.Expand(prk = extracted, info = ctx_id, 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.¶

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.¶

Table 1: Pseudorandom Function Summary
PRF Name	Identifier	Nk	Mi	Mo
PRF_AES_128	0x0001	16	2⁴²	2¹²⁸
PRF_AES_256	0x0002	32	2⁴³	2¹²⁸

Both AES PRFs use the same process:¶

The input, i, is converted to a 16-byte input using a little-endian encoding.¶
These bytes are then input to the AES function to produce a 16 byte output.¶
The AES input and output are XORed produce a 16 byte sequence.¶
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))

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.¶

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 is 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.¶

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ⁿ (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. For large values of n, multiple invocations of the PRF can be used.¶

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ⁿ. 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ⁿ. 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.¶

For example, an application might seek to produce values in the prime field p = 2⁶¹ - 1. Using the AES PRF, where Mo is 2¹²⁸, 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⁴⁸ 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⁶⁴ 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).¶

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⁴², which assumes a value of q no more than 2⁴⁴.¶

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⁴³ 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 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, <https://doi.org/10.6028/nist.fips.197>.
[ASCII]: Cerf, V., "ASCII format for network interchange", STD 80, RFC 20, DOI 10.17487/RFC0020, October 1969, <https://www.rfc-editor.org/rfc/rfc20>.
[HPKE]: Barnes, R., Bhargavan, K., Lipp, B., and C. Wood, "Hybrid Public Key Encryption", RFC 9180, DOI 10.17487/RFC9180, February 2022, <https://www.rfc-editor.org/rfc/rfc9180>.
[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>.
[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, <https://www.rfc-editor.org/rfc/rfc8126>.
[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>.
[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, <https://www.rfc-editor.org/rfc/rfc8017>.

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, Lecture Notes in Computer Science pp. 342-362, DOI 10.1007/978-3-540-30576-7_19, ISBN ["9783540245735", "9783540305767"], 2005, <https://doi.org/10.1007/978-3-540-30576-7_19>.
[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, Lecture Notes in Computer Science pp. 793-822, DOI 10.1007/978-3-030-56880-1_28, ISBN ["9783030568795", "9783030568801"], 2020, <https://doi.org/10.1007/978-3-030-56880-1_28>.
[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, <https://doi.org/10.1109/sp40000.2020.00016>.
[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, <https://www.rfc-editor.org/rfc/rfc9420>.
[TLS]: Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, <https://www.rfc-editor.org/rfc/rfc8446>.
[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, <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vdaf-10>.