Multi-Party Threshold Cryptography MPTC

The multi-party threshold paradigm

Using a “secret sharing” mechanism, the secret key is split across multiple "parties". Then, if some (up to a threshold f out of n) of these parties are corrupted, the key secrecy remains uncompromised. The cryptographic operation that depends on the key is then performed via a threshold scheme, using secure multi-party computation (MPC), so that the key does not have to be reconstructed (i.e., the secret-sharing remains in place even during the computation). This threshold approach can be used to distribute trust across various operators, and is also useful to avoid various single-points of failure in the implementation.

Which cryptographic primitives can be thresholdized?

Threshold schemes can be applied to any cryptographic primitive, such as key generation, signing, encryption and decryption. The MPTC project will consider devising recommendations and guidelines pertinent to threshold schemes that are interchangeable (in the sense of NISTIR 8214A, Section 2.4) with selected primitives of interest. For example, a threshold-produced signature should be verifiable by the verification algorithm that is used for signatures produced by the conventional (non-threshold) algorithm.

The NIST Threshold Call motivates the community of cryptography experts to submit threshold schemes and other primitives in scope, to form a public body of reference material. Each submission will include (i) technical specification, (ii) open-source reference implementation, and (iii) experimental performance evaluation. The analysis will support future recommendations for subsequent processes, which may include development of technical recommendations. The final version of the call (upcoming in 2025) will set a period for submissions, followed by a period of public analysis of the gathered reference material.

The primitives in scope are organized into multiple categories, across two classes:

• Class N: NIST-specified primitives
• Class S: Special primitives not specified by NIST

Scope updates in the second public draft:

• New indexation of categories: N1...N4 (instead of old C1.1...C1.5); S1...S7 (instead of old C2.1...C2.8).
• Categories N1 (old C1.1) and N2 (old C.1.2) include primitives from the recent NIST-PQC standards.
• Category N3 (old C1.4) includes primitives from the upcoming NIST Lightweight Cryptography (Ascon-based) standard.
• Category S5 (old C2.6) narrowed the scope, becoming focused on FHE.
• The KeyGen categories (N4, S4) now also include the scope of the old subcategories about key-establishment (C1.3, C2.3).

Public drafts and feedback:

• 2025-Mar-27: NISTIR 8214C 2pd — NIST First Call for Multi-Party Threshold Schemes (Second Public Draft). See the publication page.
• 2023-Sep-26–28: NIST workshop on Multi-Party Threshold Schemes (MPTS 2023), focused on the topics of the Threshold Call. All presentations are available online.
• 2023-Jan-25: NISTIR 8214C ipd — NIST First Call for multi-party threshold schemes (initial public draft). The publication page shows the period of public comments (open until 2023-April-10). There is a compilation of public comments (see PDF file).
• 2021-Jul-02: Call 2021a for Feedback on Criteria for Threshold Schemes (see PDF file). There is a compilation of public comments (see PDF file).

Table 1. Categories of interest in Class N

Legend: 2KA = pair-wise key-agreement; AES = Advanced Encryption Standard; CDH = Cofactor Diffie-Hellman; DKG = Distributed key-generation. ECC = Elliptic-curve cryptography; ECDSA = Elliptic-curve Digital Signature Algorithm; EdDSA = Edwards-Curve Digital Signature Algorithm; KC = Key confirmation; KDM = Key derivation mechanism; Keygen = Key-generation; ML = Module Lattice (based). MQV = Menezes-Qu-Vanstone; PKE = Public-key encryption; PQC = Post-Quantum Cryptography. PreQ = pre-quantum; QR = quantum resistant; RSA = Rivest-Shamir-Adleman; RSADSA = RSA digital signature algorithm; stfl-HBS = stateful hash-based signatures.

Note: This table reflects the categories in NISTIR 8214C 2pd (mar-2025). The initial public draft (jan-2023) had a different organization.

Table 2. Subcategories and examples of primitives in Cat2

TF-PQ is a desired combination for any type of scheme; some examples show just TF to emphasize that it is welcome even if not PQ.

Legend:  Keygen = key-generation; PKE = Public-key encryption; PRF = pseudorandom function (family); PRP = pseudorandom permutation (family); PQ = post-quantum (i.e., quantum resistant); TagGen = Tag generation. TF = threshold friendly; XOF = eXtendable output function. ZKPoK = Zero-knowledge proof of knowledge.

Note: This table reflects the categories in NISTIR 8214C 2pd (mar-2025). The initial public draft (jan-2023) had a different organization: class S was category 2; categories N1...N7 were subcategories C2.1...C2.8. Category S5 is now focused on FHE (whereas the previous C2.6 was more open-ended to special types of encryption).

Documents:

• 2023-Jan: NISTIR 8214C ipd (initial public draft): "NIST First Call for Multi-Party Threshold Schemes"; see also the received feedback.
• 2022-Aug: NISTIR 8214B ipd (initial public draft): "Notes on Threshold EdDSA/Schnorr Signatures" (on EdDSA); see also the received feedback
• 2021-Jun: Call 2021a; see also the received feedback
• 2020-July: NISTIR 8214A; see also the diff and feedback to/about Draft NISTIR 8214A (2019-Nov)
• 2019-Mar: NISTIR 8214; see also the diff and feedback to/about  Draft NISTIR 8214 (2018-Jul)

Presentations:

• 2023-Sep: presentations at the MPTS 2023 workshop
• 2020-Nov: presentations at the MPTS 2020 workshop
• 2019-Mar: presentations at the NTCW’19 workshop
• Various project-related presentations
• Some crypto-reading-club presentations of interest: 2021-06-16 (zk-SNARKs), 2022-08-10 (Threshold EdDSA), 2022-09-07 (ROS insecurity), 2022-Nov-02 (adaptive security), 2023-Jun-14 (MPC/FHE/ZKP friendly primitives)

Note: The old "single-device track" about masked circuits for block-ciphers has become a separate project.

Each NIST-organized workshop has a dedicated webpage with detailed information. These events are also listed in the "Events" page associated with the MPTC project.

• September 26–28, 2023: NIST Workshop on Multi-Party Threshold Schemes (MPTS) 2023
  • Held virtually, including 26 external talks, 1 open session of comments, 4 talks on NIST activities, 3 internal notes about the Threshold Call, 1 opening and 1 closing session.
  • The presentations Obtained feedback about the NIST First Call for Multi-Party Threshold Schemes.
  • There was a call for presentation abstracts, with a deadline of 2023-Sep-05.
• November 4–6, 2020: NIST Workshop on Multi-Party Threshold Schemes (MPTS) 2020
  • Held virtually, including 17 invited talks and 11 accepted briefs.
  • The presentations provided feedback toward criteria for multi-party threshold schemes.
  • The workshop announcement informed a deadline for submissions by 2020-Sep-30.
• March 11–12, 2019: NIST Threshold Cryptography Workshop (NTCW) 2019
  • Held in person, at the NIST campus in Gaithersburg Maryland, USA
  • Participants: with experts from industry, academia, and government.
  • The submission deadline was December 17, 2018.
  • Note: this workshop relates to an older exploratory phase, whose scope included multi-party threshold schemes and single-party masked implementations

NIST Internal Reports (NISTIR):

So far, the main publications in the project are in the form of NIST Internal Reports (NISTIR), elaborated internally at NIST and made publicly available for comments and consultation.

• NIST IR 8214C ipd: NIST First Call for Multi-Party Threshold Schemes
  • Final version: expected in the third quarter of 2023
  • Public comments: The initial public draft announced a period of public comments until 2023-Apr-10. The MPTS 2023 workshop (2023-Sep-26–28) will collect further feedback.
  • Initial public draft: Published on 2023-Jan-25. DOI:10.6028/NIST.IR.8214C.ipd
• NISTIR 8214B ipd: Notes on Threshold EdDSA/Schnorr Signatures
  • Final version: expected in the third quarter of 2023
  • Public comments: The initial public draft announced a period of public comments until 2023-Oct-24.
  • Initial public draft: Published on 2022-Aug-12. DOI:10.6028/NIST.IR.8214B.ipd
• NISTIR 8214A: NIST Roadmap Toward Criteria for Threshold Schemes for Cryptographic Primitives.
  • Final version: Published on 2020-Jul-07. DOI:10.6028/NIST.IR.8214A
  • Note: Initiated a discussion about the pertinence of considering the standardization of threshold schemes for cryptographic primitives.
  • Diff and public comments: The draft was open for public comments until 2020-Feb-10. The available "diff" highlights the changes between the draft and the final version and includes a table with the received comments.
  • Draft version: Published in the CSRC on 2019-Nov-08. DOI:10.6028/NIST.IR.8214A-draft
  • Note: The title in the draft was "Towards NIST Standards for Threshold Schemes for Cryptographic Primitives: A Preliminary Roadmap", which changed in the final version.
• NISTIR 8214: Threshold Schemes for Cryptographic Primitives: Challenges and Opportunities in Standardization and Validation of Threshold Cryptography.
  • Final version: Published in the CSRC on 2019-Mar-01.
  • Note: presents a structured approach for exploring the space of threshold schemes for potential standardization, across two tracks: multi-party and single-device.
  • Diff and public comments: The draft was open for public comments until 2018-Oct-22. The available "diff" highlights the changes between the draft and the final version and includes a table with the received comments.
  • Draft version: Published in the CSRC on 2019-Jul-26.

The MPTC project intends to drive an open and transparent process (see IR 7977), welcoming and considering feedback from the community of stakeholders, including researchers and practitioners in academia, industry and government. The project has received useful community feedback about the multi-party threshold setting, including the references listed below:

MPTC forum

To receive announcements pertinent to opportunities for collaboration, feedback, and workshops, consider subscribing to the MPTC-forum. The messages are publicly available at https://groups.google.com/a/list.nist.gov/g/mptc-forum

Call 2021a for Feedback on Criteria for Threshold Schemes:

An earlier related call for focused feedback on criteria for threshold schemes (Call 2021a) solicited anticipated comments on the following topics: scope of proposals; security idealization; security vs. adversary types; system model; threshold profiles; building blocks.

• Original call (2021-July-02): Call 2021a for Feedback on Criteria for Threshold Schemes 
• Received feedback (compiled on 2022-Aug-30): Compilation of Feedback to NIST-MPTC Call 2021a

Feedback about NISTIR’s

The NIST reports on threshold schemes have benefited from public comments, as described in:

• Public comments on NISTIR 8214C ipd (initial public draft)
• Public comments on NISTIR 8214B ipd (initial public draft)
• Diff and public comments on NISTIR 8214A
• Diff and public comments on NISTIR 8214

Feedback in NIST workshops

Topics of various presentation at NTCW 2019, MPTS 2020, MPTS 2023, WPEC 2024:

• Standardization setting: [2019] I1.2 (TC readiness); [2020] 2a1 (MPC settings), 2a2 (composability); [2023] 1a1 (diversity).

• Threshold RSA keygen: 1a3 (honest majority threshold schemes).

• Threshold ECDSA: [2019] I4.2, I.5.1 (a, b, c); [2020] 3a2, 3a3, 3c1, 3c2; [2023] 1b3, 1b4.

• Threshold Schnorr/EdDSA: [2019] II4; [2020] 1b2 (MPC-based), 1b3 (prob.), 1c1; [2023] 1b2 (prob.).

• Threshold AES: [2020] 2b3; [2023] 1a4.

• Threshold RSA keygen: [2020] 3b1, 3b2.

• Threshold DL Keygen: [2023] 1b1.

• PEC-related: [2023] 2a1, 2a2 and 3c1 (FHE), 2a3 and 2a4 (ZKP), 2a5 (ABE)

• Threshold for other primitives: [2023] 1b5 (BLS).

• Gadgets / building blocks: [2020]: 2b2+2c1 (garbled circuits), OT (2b1), PCG (2a3), PVSS (1a2); [2023] 3a1 (auth garbling), 3a2 (stacked garbling), 3a3 (garbled lookup tables), 3a4 (VOLE), 3c2 (AONT), 3c3 (VORF), 3c5 (networking).

• Platforms/frameworks/endeavors: [2019] I1.3, II4.3; [2020] 3b3 (frameworks), 2c2, 2c3, 2c4, 2c5 (MPC Alliance); [2023] 1a2 (SPDZ), [2024] 3a5 (MPC Alliance).

• Attacks: [2020] 3a1 (attacks), 2b2 (key-extraction).

• Theory: [2019] II4.1 (multi-signatures); [2023] 2b3 (random-oracle); [2024] 3a2 (tutorial)

• Threshold post-quantum: [2019] I3.1; [2020] 1c2, 1c3.

• Others applications/comments: [2019] II4.4; [2020] 1b1, 1c4; [2023] 1a3, 2b1 (TLS).

• Secret sharing variants: II3.1 (leakage resilient)

• Variants: [2019] I4.1 (signatures), II3.2 (symmetric encryption), II4.2 (signing).

NIST presentations:

• NIST standards related: [2019] I2.1 (approach), I6.1 (validation) I2.2 (PQC & EC); [2023] 2c1 & 2c2 (PQC), 2c3 (LWC), 2c4 (Validation), 2a0 (PEC tools), 3a0 (gadgets).

• Intros about the threshold-crypto project or call: [2019] I1.1, [2020] 1a1; [2023] 101.

Legend of indices:

- For NTCW 2019, indices are Xyz, with X in {I, II} (day), y in {1,…,5} (session in the day), z in {1,2,3}.

- For MPTS 2020 and MPTS 2023, indices are xyz, with x in {0, 1,2,3} (day), y in {a,b,c,d} (session in the day), z in {0,…,5}.