Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Multi-Party Threshold Cryptography MPTC

Overview

The multi-party paradigm of threshold cryptography enables threshold schemes, for a secure distribution of trust in the operation of cryptographic primitives.


The NIST Threshold Call

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.

NISTIR 8214C ipd — NIST First Call for multi-party threshold schemes (initial public draft) — was published on 2023-Jan-25. This is the draft of a call that motivates the community of expert stakeholders to submit proposals of threshold schemes (including technical specification, security analysis, open-source reference implementation, performance evaluation) for primitives in two categories:

  • Cat1: selected NIST-specified primitives (see Table 1).
  • Cat2: other primitives not specified by NIST (see Table 2).

As detailed in the publication page, a formal period of public comments was open until 2023-April-10 (the compilation was published here). Furthermore, in September 26–28, 2023, NIST organized MPTS 2023, a workshop focused on the topics of the Threshold Call. The upcoming revision of NISTIR 8214C ipd will make several adjustments, including the scope of several subcategories:

Once the final call is published and concrete threshold schemes are submitted, the collected reference material will be analyzed and the conclusions will support the future development of recommendations and guidelines.

Table 1. Subcategories of interest in Cat1

Subcategory: Type Families of specifications Section (in the call)
C1.1: Signing

[PreQ] EdDSA sign; ECDSA sign; RSADSA sign

[QR stateless] ML-DSA sign; SLH-DSA sign; Falcon (to appear) sign

[QR stateful]: XMSS sign; LMS sign

A.1
C1.2: PKE

[PreQ] RSA encryption & decryption

[QR] ML-KEM encryption & decryption

A.2
C1.3: 2KA ECC-CDH & ECC-MQV primitives A.3
C1.4: Symmetric

Key-based: AES (blockcipher) & ASCON (AEAD) encipher and decipher; C/H/K-MAC

Key-less: SHA2 & SHA3 hash; Keccak & ASCON XOF

A.4
C1.5: Keygen (aka DKG)

ECC keygen; RSA keygen; bitstring keygen

QR keygen for ML, SLH, Falcon, and stateful-HBS

A.5

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.

Table 2. Subcategories and examples of primitives in Cat2

Subcategory: Type Example scheme Example primitive
C2.1: Signing TF succinct & verifiable-deterministic signatures Sign
  TF-QR signatures Sign
C2.2: PKE TF-QR public-key encryption (PKE) Decrypt; encrypt (a secret value)
C2.3: KA Low-round multi-party key-agreement (KA) Single-party primitives
C2.4: Symmetric TF PRP (e.g., blockcipher) or PRF (e.g., for MAC or key-derivation) Encipher, decipher, MAC
  Hash or XOF Hash function, XOF
C2.5: Keygen Any of the above or below Keygen
C2.6: FHE QR Fully-homomorphic encryption (FHE) Decryption; keygens
C2.7: ZKPoK ZKPoK of private key ZKPoK.Generate
C2.8: Gadgets Garbled circuit (GC) GC.generate; GC.evaluate

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

Legend:  2KE = pair-wise key-establishment; Keygen = key-generation; PKE = Public-key encryption; PRF = pseudorandom function (family); PRP = pseudorandom permutation (family); QR = quantum resistant; TF = threshold friendly; ZKPoK = Zero-knowledge proof of knowledge.

Note: the initial public draft had "C2.6 = Advanced" (inc. FHE, IBE and ABE), but the 2pd will narrow it down to just FHE.

Project Progress and Milestones

Documents:

Presentations:

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 46, 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 1112, 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.

Collaboration

The project will drive an open and transparent standardization process based on established NIST principles. The process involves engaging with and incorporating feedback from the community of stakeholders, including researchers and practitioners in academia, industry and government. To receive announcements pertinent to collaboration with the Threshold Cryptography project, consider subscribing to the MPTC-forum. The messaegs are publicly available at https://groups.google.com/a/list.nist.gov/g/mptc-forum

Specific collaboration is expected in the form of high-quality submissions to the upcoming NIST First Call for Multi-Party Threshold Schemes, and the subsequent public analysis of the set of submitted schemes.

Public feedback

The MPTC project has received useful community feedback about the multi-party threshold setting.

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.

Feedback about NISTIR’s

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

Feedback in NIST workshops

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

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

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

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

  • 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}.

Additional Pages

Email List (MPTC Forum)

Contacts

Reach us at threshold-MP (at) nist (dot) gov

Luís T. A. N. Brandão - NIST/Strativia
luis.brandao@nist.gov

Michael Davidson - NIST

René Peralta - NIST

Dustin Moody - NIST

Created July 26, 2018, Updated September 26, 2024