Security of threshold schemes in the Threshold Call

[Brandao, Luis (IntlAssoc)]

Dear MPTC-forum,

Following recently received questions, here is some clarification about security requirements for threshold schemes to be submitted to the Threshold Call. Related text from the second public draft (IR 8214C 2pd) will be correspondingly improved in the final version.

(The use of "shall" and "should" denotes requirement and recommendation, respectively.)

T1. Informal summary (compare with section 8.2.2 and 8.2.3)

For submission of threshold schemes: 

• (i) active security shall be proven;
• (ii) adaptive security shall be technically argued for; and
• (iii) an envisioned mechanism for proactive security should be discussed (possibly informally and/or by reference).

These security characteristics in the threshold setting are meant with regard to (wrt) critical safety properties (e.g., key secrecy), rather than wrt every conceivable security property (e.g., availability).  For instance, security-with-abort formulations are acceptable.

T2. Types of adversarial corruption in the threshold setting

Section 8.2.2 mentions three corruption characterizations of interest: active, adaptive, and mobile.  The "shall" (requirement) used in this section is meant to imply a need to *consider* the consequences of active, adaptive, and mobile types of corruption, but it does not establish a requirement for proving security against those combined types of corruptions. 

For example, it is useful to know what goes wrong when the corruption threshold is surpassed, if the adversary keeps steadily corrupting additional parties, even if the submitted crypto-system does not include a protocol for recovering corrupted parties back to a healthy state.

T3. Active security (Section 8.2.3, item 1)

It's a requirement that submitted threshold schemes can be proven secure wrt a formulation (e.g., game-based or simulation based) where some of the parties can maliciously deviate from the prescribed protocol.  It's up to the submitting team to present the security formulation (e.g., based on an ideal functionality, or games), and corresponding security proof.  Active security is required wrt critical safety properties (e.g., key-secrecy, unforgeability), whereas other properties can be compromised.

The requirement of provable active security can be limited to a setting with some well-identified trusted setup and/or assumptions, including about the actual input given to the cryptographic operation.  For example, a threshold FHE-decryption scheme can be submitted as actively secure for a restricted use case where the input ciphertext is assumed to have been honestly produced.  Naturally, it is relevant to be aware of the insecurity consequences of not meeting the prescribed trusted setup.

The security proof of the submitted threshold scheme can make security assumptions about building blocks (e.g., broadcast). The proof in the specification document still has to list and explain those assumptions, and include appropriate references to publicly-accessible-for-free security analysis of the building blocks. Also, the implementation will have to include code for the building blocks.

T4. Adaptive security (Section 8.2.3, item 2)

The requirement is that there is a best-effort technical discussion about security against an adversary capable of adaptive corruptions.  In particular, the Threshold Call wants to avoid pathological protocols that, despite being proven secure against static corruptions, would leak the secret key (or break some other critical safety property) in case of adaptive corruptions.  A proof of security against adaptive corruptions is not required, but it would add value.

Section C2.2 acknowledges the challenge of proving security in case of adaptive corruptions.  As mentioned in the ipd and 2pd (and also in the 2021 Call for Feedback on Criteria): "Feedback is welcome on security formulations and reference approaches that simultaneously enable both practical feasibility and security (for properties of interest) against adaptive corruptions, as well as acceptable tradeoffs."

T5. Compatibility with recovery mechanisms (i.e., against a mobile adversary) (Section 8.2.3, item 3).

A submitted threshold scheme is not required to include mechanisms (proactive or reactive) for restoring a party to a healthy state.  However, the submission "should" (i.e., is encouraged to) discuss how it envisions corresponding augmentations.  For example, is it trivial or are there challenges in integrating some specific recovery mechanism (e.g., secret resharing) to handle the case of past-leaked shares?  If such augmentation is submitted, that's a welcome bonus.  For the reactive-recovery case, the property of identifiable abort is of interest.

T6. Informal example

The following combination is possible in a submission of a threshold scheme:

- static-active security-with-abort is proven in a simulation-based of game-based setting;

- adaptive-active security is technically argued for in a manner less formal than a proof;

- proactive security is argued for as achievable with an ad-hoc subprotocol/phase that is not specified/implemented (but is referenced) in the submission.

Enhanced security properties/analysis besides the required minimum are also welcome, e.g., a proof of security against adaptive corruptions, a subprotocol for proactive recovery, or a process for safely handling maliciously produced inputs. A threshold scheme can understandably be less efficient in order to provide more challenging security guarantees. 

T7. Security strength

Section 8.1 in the 2pd considers requirements on security strength (e.g. 128-bit security level).  However, a threshold scheme may have different security strengths across the static and adaptive corruption scenarios.  The specified requirement of minimal security strength (for specification, implementation, and evaluation) can be assumed to relate to the active-static case.  We encourage submissions to also explain which parameters are needed to achieve 128 bits of active-adaptive security.

Feel free to share (not secret-share) related insights in this thread. We also welcome further questions or comments. 

Regards, Luís and René

--

Luís Brandão

NIST Associate (Foreign Guest Researcher, Contractor from Strativia)