MPTC Call

[Nigel Smart]

Hi Luis

Question over the following hypothetical for Cat 2....

Someone wants to submit a threshold algorithm for X.

To implement this threshold algorithm one needs all
sorts of components which have not yet been standardized,
e.g.
  - Full blown MPC protocol for some specific situation
  - ZKPoKS for a specific problem space
  - Crypto algorithms for secret sharing or
    GarbledCircuits or...
Let us call these components A, B and C.

Now in the implementation part of the submission there
seem two choices.

1) One could just give a single implementation of X, and
    the instructions to run, KATs etc. i.e. one mega doc
    with a single M1/M2/M3/M4 section. This might be easier
    to write, but it is harder to test from your end and also
    harder to apply mix-and-match re submissions.

or

2) Give a document containing 4 parts (A, B, C, and X)
    Then give sections...
        A.M1, A.M2, A.M3, A.M4
        B.M1, B.M2, B.M3, B.M4
        ....
        X.M1, X.M2, X.M3, X.M4

Now to me Option 2 makes more sense as then it is clear
to who is evaluating which components can be swapped out
and replaced with others. And in addition it may be that
NIST wants to produce some final mega doc containing
A, B and C, but not X. Or perhaps A, B and X from one submitter
and the variant of C from a different submitter.

Note even threshold primitive X itself may consist of
sub-primitives: For example KeyGen, DistSigning/DistDec,
Resharing [for proactive security]. So even the end
application X itself might be split into various protocols;
each requiring an M1/M2/M3/M4.

Leading to a structure of....
        A.M1, A.M2, A.M3, A.M4
        B.M1, B.M2, B.M3, B.M4
        ....
        Xa.M1, Xa.M2, Xa.M3, Xa.M4
        Xb.M1, Xb.M2, Xb.M3, Xb.M4
        Xc.M1, Xc.M2, Xc.M3, Xc.M4

Assuming Option 2 is to preferred, there is then the question
of parallel or sequential composition :-), i.e. do you want the
submission to be in column or row order above, i.e.
   A.M1 then A.M2 then A.M3 and so on
or
   A.M1 then B.M1 then C.M1 and so on

Yours

Nigel

[Brandao, Luis (IntlAssoc)]

Thanks Nigel, for your question in advance of the upcoming workshop and the final version of the Call.

Long answer ahead. Note: this is being answered in the public MPTC-forum.

====== Starting with a short'ish answer:

We favor modularity as an important principle, and expect that each of several submission packages will include more than one scheme/gadget within the scope of the Threshold Call. 

Recalling some notation in the call ipd (initial public draft), we have defined:

- five "main components" (M1–M5) in a submission package; and

- various (16) “sections” within the written specification component (M1).

Each main component (M1–M5) in a package will correspond to a different file or set of files&folders. Your question about (i) one "mega doc" vs. (ii) a document containing various "parts" seems mostly pertinent with respect to M1 (the written specification); nonetheless, the detailed answer ahead includes notes about every component.

The final version of the Threshold Call will modularize the component M1 into various parts. A LaTeX template will be provided, allowing (i) one main "part" for each object (threshold scheme or gadget) submitted for evaluation within some subcategory of the Call, besides (ii) a preliminary part for additional high-level content that can be referred to from the various main parts.

The features discussed in this answer are being considered in the revision of the threshold call. Further public feedback is welcome, in particular in the upcoming threshold workshop (MPTS 2023; submission by Sept 5th).

====== Continuing with more details:

=== Recall the Call ipd:

• [in lines 559-560] says that a submission package may include a family of distinguished threshold schemes based on common building blocks.

• [in lines 561-563] asks that even if a submission package proposes more than one threshold scheme, each of the five components [M1–M5] should appear only once.

• [line 614] asks that protocol descriptions modularize the description of primitives/gadgets where appropriate.

=== Types of deliverables:

The five (5) main components (M1–M5) of a submission package have different types of "deliverable":

• M1 (written specification): a compiled PDF (we will provide a LaTeX template)

• M2 (reference implementation): the source code, organized in a folder/subfolders with various files

• M3 (execution instructions): a folder including a "user manual" (e.g., can be a wiki-style set of pages, or a “man page”, and a PDF compilation thereof), and a set of scripts (files with code)

• M4 (experimental evaluation): a PDF file with a sequence of performance evaluation results; optionally, also a set of pages/files (e.g., html, svg, txt, ...) for better visualization and extraction (with more options/details)

• M5 (additional statements): separate documentation with signatures

Note on multiple submissions: anyone (person / team) may decide to make more than one submission. Each submission requires a package with components M1–M5.

Note on community coordination: We encourage teams to share their submission plans in advance (e.g., at MPTS 2023, and the MPTC forum), to enable synergies and help avoid duplication of work.

=== Modularization of component M1 (written specification)

We want the component M1 to be a single PDF file. This document may contain multiple "parts", each enclosing the specification of an object (threshold scheme or gadget) being proposed for subsequent public analysis. We will accordingly revise in NISTIR 8214C the description of M1.

For example, a submission that specifies three threshold schemes, and makes use of nine building blocks, may (for example) chose to:

• use a preliminary "part” to describe five (5) building blocks at a high-level;

• use four (4) main “parts” to thoroughly specify the other four (4) building blocks, to also be considered as a standalone proposed object in some subcategory of the Call;

• use three (3) main “parts” to thoroughly describe each of the three threshold schemes.

See an expansion of this example at the end of this email. 

A “part” with various protocols: The written specification of a threshold scheme (within one "part" of M1) may itself also include various protocols (each in a separate subsection). The document can still modularize these protocols, whilst pointing out common dependencies and other common factors (e.g., system model). For example, a threshold scheme for a signing primitive may be submitted as a bundle of a (i) threshold signing protocol, (ii) a distributed key-resharing protocol, (iii) a corrupt-party blaming/exclusion protocol in case of abort, and/or (iv) variants corresponding to different system models or threshold/corruption profiles. For example, the execution of (iii) may depend on the result of a previous execution of (i) or (ii).

Identifying different subsets of submitters per part: It is encouraged that a submitting team reaches out in advance to the main inventors/authors of the scheme/object specified in each main “part” of M1, to invite them to be part of the submitter team of that “part”. The revision of M1 in the Threshold Call (NISTIR 8214C) will allow different “parts” to identify different sets of authors/submitters.

====== Modularization of component M2 (open-source reference implementation).

We expect source code to be naturally organized across various subfolders, each with various files. Each "part" in M1 may have a corresponding subfolder in "M2". Even gadgets that are “only-used” (but not thoroughly specified in M1 — see the example in P.S.) must also include a corresponding open-source implementation in M2. Naturally, the source-code obtained from external sources must contain proper attribution and have a corresponding compatible open-source license.

====== Modularization of component M3 (execution instructions).

There should be instructions (user manual and scripts) for the execution of code (of M2) corresponding to each main “part” of M1. The "user manual" can include a compilation covering all parts.

====== Modularization of component M4 (experimental evaluation).

One PDF file, separate from M1, should include a sequence (across the various “parts” of M1) of explanations and results, including a description of the experimental setting, the measured performance, and an analysis/interpretation of the obtained results. This should cover the various “parts” of M1. M2 can optionally include additional auxiliary material, e.g., a set of pages/files (e.g., html, svg, txt, ...) for better visualization/extraction with more options/details.

====== Modularization of component M5 (additional statements).

M5 asks for a statement from each member of the submission team. The statement for each submitter will identify the applicable components/parts of the submission. In the simplest case, all authors will assume responsibility for every component/part. In a more complex case, different submitters may claim responsibility for different components/parts.

====== An example of multiple parts/schemes in a submission:

Consider the following example exercising what is thoroughly specified vs. what is specified at a high level.

Multiple threshold schemes and gadgets: For example, consider a submission package that specifies three (3) threshold schemes: e.g., one for a distributed key-generation, and two threshold signing algorithms (corresponding to different signing primitives, though possibly reliant on a common keygen). Consider that to specify these three threshold schemes it is relevant to modularly “specify” or “use” (see paragraph below) up to nine (9) different gadgets/subprotocols (G1–G9). For example, the hypothetical gadgets could be: a verifiable secret-sharing scheme (G1), a secret-resharing protocol (G2), a broadcast protocol (G3), a garbling scheme (G4), a 1-out-of-2 oblivious transfer (G5), a linearly-homomorphic encryption scheme (G6), a special commitment scheme (G7), a vector oblivious linear evaluation protocol (G8), a ZKPoK (G9).

On “specified/submitted” vs. “only-used” gadgets: a submitter team may propose four (4) of the nine (9) gadgets as objects for the body of reference material being collected/analyzed by the "threshold process". Conceivable, the other five (5) gadgets can be simply explained at high level (interface and security properties), while referring to external bibliography for their thorough specification.

In this case, the former four (4) gadgets should be thoroughly specified in low-level detail, each in a separate main “part” of M1, following the guidelines for “written specification” of a threshold scheme or gadget (to be updated in the final version of the Threshold Call); the latter five (5) gadgets can be described altogether more simply (i) in the preliminary part or (ii) in a section of auxiliary high-level explanations of needed gadgets, but without a full internal description. Each of the three threshold schemes mentioned in the example would also have its own corresponding main “part” in M1.

--
Luís Brandão

NIST/Strativia: Foreign Guest Researcher at NIST (Contractor via Strativia)

---

From: Nigel Smart
Sent: Thursday, August 24, 2023 07:53
To: MPTC-...@list.nist.gov
Cc: Nigel Smart; Brandao, Luis (IntlAssoc)
Subject: MPTC Call