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, <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>.
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, <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, Theory of
Cryptography 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,
Advances in Cryptology – CRYPTO 2020 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>.
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]