FHE category (S5) in the Threshold Call

[Brandao, Luis (IntlAssoc)]

Dear MPTC-forum,

Following recently received questions about the FHE category (S5) in the Threshold Call, here are some clarifications.

H1. Security formulation of the conventional FHE scheme

While a submitted threshold scheme for an FHE primitive needs to be actively secure, its setup can assume that the input ciphertext was honestly produced. In particular, the team does not have to specify or consider an underlying "Verifiable FHE" scheme. Naturally, the limitations regarding trust assumptions need to be clearly stated. The variety of limitations and features across submissions is expected to offer valuable insights for shaping future recommendations.

H2. Threshold Encryption

In section 10.5, the paragraph "Threshold Scheme" requires at least decryption or encryption to be thresholdized in an FHE-category submission.  The ipd was stricter by requiring threshold decryption.  Considerations about threshold encryption:

• In threshold public-key encryption, the input plaintext is distributed (among multiple parties) as a secret-shared secret value (possibly prepared using some kind of verifiable secret sharing), and the goal is to compute a correct encryption of the reconstructed secret.
• In threshold symmetric-key encryption: the secret key is itself secret shared. The input plaintext may or may not be secret-shared.

H3. Exact and Approximate FHE

The auxiliary (informative) description in appendix B.1 explains FHE only in an exact setting, e.g., where Dec(F(Enc(p)))=f(p), for F=hom(f).  However, the category is also open to approximate FHE schemes, i.e., those whose homomorphic evaluations introduce some error (noise) in the corresponding plaintext operations.

H4. Level at which to explain the conventional FHE scheme

Section 10.5 of the 2pd asks that, in a submission of a threshold scheme for some FHE-related primitive, the underlying conventional (i.e., non-threshold) FHE scheme (tuple of algorithms) should be explained, either "thoroughly" or "at a high level". To clarify:

• "Thorough": Full-fledged specification, as a "crypto-system" part in the specification document (CS x). (Note: The 2pd incorrectly mentioned section Pre4).  In this case, the submission shall also include implementation and performance evaluation of the conventional FHE scheme.
• "High level": Basic auxiliary description of the conventional scheme, including notation, syntax, and security properties, and allowing determination of the interchangeability requirements (see section 3.3 in the 2pd).  The team decides how much detail to include, as deemed useful to understand the actual threshold scheme(s). This description should be organized in (sub)subsections of section Pre4 (in the Preliminaries Part) or/and of section Csx.3 of the *part* where the corresponding threshold scheme is explained. See sections 5.3 and 5.4 of the Threshold Call 2pd.  Such a submission does not have to benchmark the conventional FHE scheme.

H5. On the need or not to benchmark the conventional FHE

In section 10.5 of the 2pd, paragraph "Benchmarking of the conventional scheme", the first "should" statement is actually meant as follows: if the conventional FHE scheme is "thoroughly" specified as a standalone crypto-system, then the submission shall include a corresponding implementation and experimental evaluation (see sections 6 and 7 of the 2pd); otherwise, if the conventional FHE scheme is only specified at a "high level", then the implementation and benchmarking of the conventional FHE scheme are optional.

In any case, the actual threshold scheme (for some FHE primitive) shall be benchmarked.

H6. On choosing use cases (workloads) to benchmark a conventional FHE scheme

Also in section 10.5, paragraph "Benchmarking of the conventional scheme", the sentence "should at least ... for one use case in which it performs well" is meant as a suggestion/encouragement for making a good case for the proposed FHE scheme. However, the team has discretion on which use case(s) to consider.

In section B.1.1, the description of an FHE-based oblivious enciphering is meant as an example for illustrative purposes. If a team decides to benchmark a conventional FHE scheme, then it's up to the team to choose, explain and motivate one (or more) use case(s) for benchmarking.

So, the following from section 10.5 remains applicable: 

• “The selection of the benchmarking use-cases to evaluate performance [...] is left to the discretion of the submitters of an FHE scheme. Yet, submissions are encouraged to use benchmarking approaches emerging, reviewed or endorsed by community efforts."
• "Each submission should at least [read as "Teams are encouraged to"] (i) showcase performance for one use case in which it [the FHE scheme] performs well, and (ii) explain the anticipated real-world adoptability of that application (see Csx.6). For comparison, the benchmarking is encouraged to also measure performance for some operation that is anticipated to perform better by a different FHE scheme.”

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

Regards, Luís and René

--

Luís Brandão

NIST Associate (Foreign Guest Researcher, Contractor from Strativia)