Multi-Party Computation (MPC) and Threshold schemes
Secure Multiparty Computation (MPC)
(Secure) Multiparty Computation (MPC) allows multiple parties to jointly (distributively) perform a computation, using everyone's inputs, but without actually sharing the private inputs with one another. Depending on the desired functionality, each party may also obtain a private output. MPC is one of the main techniques of interest to the PEC project. Reference material about MPC has been collected across a number of events:
NIST Threshold Call
The upcoming NIST First Call for Multi-Party Threshold Schemes (NISTIR 8214C) — see the Second Public Draft (2pd) and the public comments about the Initial Public Draft (IPD) — will solicit public proposals of threshold schemes (multi-party protocols) for various cryptographic primitives. The NIST Workshop on Multi-Party Threshold Schemes (MPTS) 2023 collected further feedback before the final version of the Call.
The "NIST Threshold Call" will explore techniques of MPC (secure multiparty computation), ZKP (zero-knowledge proofs), and FHE (fully-homomorphic encryption). More details about the public call can be found in the webpage of the NIST Multi-Party Threshold Cryptography (MPTC) project.
The call has a wide scope organized into categories across two classes: class N (for NIST-standardized primitives) and class S (for Special primitives not standardized by NIST). The next table is from NIST IR8214C 2pd.
Categories across two classes in the NIST Threshold Call
| |
Sign |
PKE |
Symm |
KeyGen |
FHE |
ZKPoK |
Gadgets |
| Class N |
N1 |
N2 |
N3 |
N4 |
|
|
|
| Class S |
S1 |
S2 |
S3 |
S4 |
S5 |
S6 |
S7 |
Class S brings an opportunity to explore primitives that are not present in current NIST standards. The analysis of submitted schemes will include engagement by the MPTC and the PEC projects. The table below is an adaptation of the Table 3 in draft call (NIST IR8214C ipd).
Categories in Class S of the NIST Threshold Call
| Category: Type |
Example related schemes |
Example primitive |
| S1: Signing |
TF succinct & verifiable-deterministic signatures; TF-PQ signatures |
Sign |
| S2: PKE |
TF-PQ public-key encryption (PKE) |
Sign |
| S4: Symmetric |
TF cipher/PRP, TF PRF/MAC, hash/XOF
|
Decrypt, Encrypt (a secret value), TagGen, hash
|
| S5: Keygen |
Any of the above or below (inc. non-PKE primitives for key-establishment) |
KeyGen |
| S5: FHE |
Fully-homomorphic encryption (FHE) |
Decryption; keyGen |
| S6: ZKPoK |
ZKPoK of private key |
ZKPoK.Generate |
| S7: Gadgets |
Garbled circuit (GC) |
GC.generate; GC.evaluate |
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.
