MPTS 2023: NIST Workshop on Multi-party Threshold Schemes 2023

Welcome to the MPTS 2023: NIST Workshop on Multi-Party Threshold Schemes. The opening remarks intend to welcome the speakers and attendees, and will include a perspective from the Chief of the Computer Security Division at NIST.

[Video]

Abstract. This presentation sets intentions for the MPTS 2023 workshop (NIST Workshop on Multi-Party Threshold Schemes 2023), which is intended to gather diverse public feedback about the process envisioned in the NIST First Call for Multi-Party Threshold Schemes [NISTIR 8214C ipd (2023)] (the “Threshold Call”). The presentation will start with introductory contextual remarks about the NIST Computer Security Division, of which the Cryptographic Technology Group is part. The presentation will then recall the various subcategories in the threshold call, will explain the various sessions of talks to be presented in this workshop, and will explain the functioning of the virtual webinar.

[Slides] [Video]

Abstract. In this talk we will argue on the need to standardize diverse protocols with different tradeoffs. It isn’t possible to determine a specific protocol or tool as a “winner” due to the different deployment needs. Some examples of this needed diversity include: honest majority versus dishonest majority, low bandwidth versus low computation (there is very often such a tradeoff), efficiency versus computational assumptions, complexity of implementation versus complexity of the security proof, and so on. There are also questions regarding the security model (is adaptive security needed, is proactive security needed, etc.) There is no “right answer” as to which model is the “right one” as there is no “right answer” as to what hardness assumptions are “reasonable”. This makes standardization a challenge. However, this difficulty can be mitigated by standardizing multiple options and allowing deployers to make a choice depending on their specific setting, efficiency requirements and risk appetite. We will also raise questions (with no good answers) regarding how to deal with the natural advancement of tools in this area, so that standardization serves to advance rather than impede the field.

[Slides] [Video]

Abstract. MP-SPDZ is a versatile framework for multi-party computation implementing more that 40 protocol variants. It achieves this by heavily using C++ templating. This allows implementing a protocol only once for several domains if possible. For example, replicated secret sharing works over any ring, and MP-SPDZ uses the same code for computing modulo primes or powers of two. One way of achieving threshold cryptography is exploiting the mathematical structure of a cryptosystem based on discrete logarithm and combining it an MPC protocol in a black-box manner. This has been done with ECDSA where the domain of the secret keys is equivalent to a prime-order field, which allows run a number of MPC protocols over it. A secret sharing scheme over the secret-key domain canonically implies one over the public-key domain, and the conversion is straight-forward by applying the exponentation. In this talk, I will present the infrastructure in MP-SPDZ that underlies the implementation and code examples thereof. The simple interface makes it easy to extend to other cryptosystems with a similar structure.

[Slides] [Video]

Abstract. In this presentation, we look at threshold cryptography through the lens of secure multiparty computation (MPC), and its applications and potency as a solution to many privacy and security problems, and finally we present recent MPC based solutions for privacy-preserving analytics. MPC has been a core area of cryptography since its inception. MPC protocols enable multiple mutually distrusting parties to compute any functions on their private inputs without ever revealing their private inputs to each other. MPC decentralizes trust, resulting in more security and resilience to threats. Most importantly, MPC protects privacy while supporting computation on data.MPC protocols are very powerful and known to provide solutions to problems: notably, solutions include threshold signatures, zero-knowledge proofs/arguments, secure aggregates/analytics, secure/anonymous communication, key exchange protocols, and so on.We will review some of the application areas where there is active development using MPC (e.g., Ad Conversion, Fraud Prevention), and contrast MPC with other privacy-enhancing technologies. We will provide a brief overview of work by Stealth on practical applications of MPC protocols, including an in-depth look at a recent project where the Stealth team developed a tailored MPC protocol to enable a secure and data-private analytics query-response system in a pilot project with Virginia Longitudinal Data System (VLDS).

[Slides] [Video]

Abstract. In this presentation, I will introduce an intended submission from a multi-institution team of 12 members. Our submission aims at threshold protocols for NIST-approved symmetric-key primitives. We aim at protocols secure against active adversaries corrupting n-1 parties. We plan to submit a holistic package including all ingredients needed to build an efficient MPC protocol for any Boolean circuits and their application to any NIST-approved symmetric-key primitives (e.g., AES, SHA-2/3). Our submission consists of basic primitives (oblivious transfer, correlation robust hash functions, garbling schemes), building blocks (authenticated Beaver triples, distributed garbling schemes), and end-to-end protocols. Our submission will be accompanied by an analysis of concrete security, implementation, and discussions in the adaptive setting.

Abstract. Protocols for distributed key generation (DKG) in the discrete-logarithm setting (as used by, e.g., threshold ECDSA and threshold EdDSA protocols) have received a lot of attention in the past few years. But it can be difficult to determine when some DKG protocol is suitable for a particular threshold protocol due in part to the complexity of some of the DKG security notions that have been used to analyze those protocols. In this presentation, we suggest to manage this complexity by (1) separately standardizing DKG protocols and threshold signing/encryption protocols, to ensure modularity between the two; and (2) using a simulation-based approach to defining security for DKG protocols, so that different security guarantees can be cleanly expressed via different ideal functionalities. We exemplify this approach by suggesting a number of possible ideal functionalities for DKG. Moreover, we observe that most synchronous DKG protocols are not robust in that they allow even a single malicious party to prevent successful generation of a key. We highlight robustness as an important property for threshold protocols, in general, and propose an efficient, 2-round protocol for robust distributed key generation in the honest-majority setting.

[Slides] [Video]

Abstract. In this presentation, we will introduce two threshold signature submissions for the FROST and Sparkle schemes, and the teams that will be contributing towards the submissions. FROST is a two-round EdDSA threshold signature scheme, and Sparkle is a three-round EdDSA threshold signature scheme. We will discuss key differences between these two schemes, and other schemes in the literature, namely, in the security models and proving techniques. FROST is secure assuming the One-More Discrete Logarithm problem is hard, and Sparkle is secure assuming the Discrete Logarithm problem is hard. Both schemes are proven in the Random Oracle Model. In addition, we will discuss details of the submission, namely, the assumed networking models and key generation assumptions. Our submissions will assume an idealized key generation scheme, and assume only reliable public communication channels.

[Slides] [Video]

Abstract. We plan to prepare and submit an ECDSA scheme based on our most recent DKLS, DKS23 papers. This talk will discuss the other team members who are considering to join the submission, and the set of artifacts and evaluations that we plan to develop. We encourage others to join this group submission.

Abstract. In this presentation, I will begin by describing different deployment scenarios for threshold cryptography (and threshold signatures in particular), especially highlighting the unique aspects of threshold protocols run in a "federated key-management network." I will then suggest that NIST standardize two threshold variants for ECDSA signatures: a dishonest-majority protocol and an honest-majority protocol. Finally, I will discuss some observations we have had at Dfns while implementing and deploying the dishonest-majority CGGMP21 protocol for threshold ECDSA, and describe details of an honest-majority threshold ECDSA protocol we have been developing.

[Slides] [Video]

Abstract. Since its inception in 2004, BLS signature (named after its inventors Bonneh, Lynn and Shacham) has been very popular among researchers due to its uber-simple structure, small size, and plethora of features it offers. For example, BLS is a unique deterministic signature, and is readily thresholdizable due to its “key-homomorphism”. The signing procedure is completely non-interactive, once a key is setup (for example, by using a standard distributed key-generation, or DKG, in a fully decentralized setting). Therefore, it can be used in an asynchronous or partially synchronous setting immediately. Efficiency-wise, threshold BLS outperforms other threshold signatures such as ECDSA and Schorr in the signing, but incurs a higher cost during aggregation and verification due to use of pairing. Nevertheless, the signature size of BLS is much shorter. Furthermore, BLS supports easy aggregation of multiple signatures on the same messages but with different public keys (multi-signatures) and also various signatures on different messages (aggregate signatures). Due to its deterministic (and unique) nature, it can be immediately converted to a distributed VRF. Moreover, as shown by Das et al. (CCS’23) and Garg et al. (S&P’24), scalable weighted threshold signatures can be built based on BLS, without requiring a separate DKG. Other features include multiverse signatures, as constructed by Baird et al. (S&P’23). In Web3 setting variants of BLS signatures were deployed in several blockchain ecosystems, including Ethereum 2.0 for generating validation certificates (a BLS multi-signature was used in this case), and Hashgraph to generate a state proof. Furthermore, Distributed VRFs based on BLS were deployed in DRand, Dfinity, Supra DVRF. In this talk I shall present the importance of threshold BLS signatures, the amazing features it offers in the threshold setting, and also the trade-off in efficiency (due to pairing) in comparison with ECDSA and Schnorr. We would like to make a case for standardization of BLS in Category 2.1: verifiably-deterministic succinct signatures.

[Slides] [Video]

Abstract. Very brief comments explaining how some privacy-enhancing cryptographic (PEC) tools (fully-homomorphic encryption, zero-knowledge proofs, and attribute-based encryption) appear (or will be revised) in the NIST Threshold Call.

[Slides] [Video]

In this talk, I will discuss the public comments prepared by Ahmad Al Badawi, Andreea Alexandru, Nicholas Genise, Daniele Micciancio, Yuriy Polyakov, Saraswathy R.V. and Vinod Vaikuntanathan (see https://csrc.nist.gov/files/pubs/ir/8214/c/ipd/docs/nistir-8214c-ipd-public-feedback.pdf for the detailed version of the comments). Our comments are for Fully Homomorphic Encryption (FHE) schemes based on LWE and Ring/Module LWE over power-of-two cyclotomic rings, since this is what is most commonly implemented in open-source libraries. Our comments can apply to other FHE schemes with different hardness assumptions as well (e.g., NTRU). The comments covered in my talk include: (1) Motivation for standardizing (Threshold) Fully-Homomorphic Encryption; (2) FHE use cases; (3) FHE schemes’ Threshold friendliness; (4) Open-source implementations.

[Slides] [Video]

Abstract. Fully homomorphic encryption (FHE) is a cryptographic primitive that allows performing computation on encrypted data. It is mentioned by NISTIR 8214C, e.g., in the FHE-Based AES Oblivious Enciphering example. Here, an FHE capability a.k.a transciphering is used for decrypting an AES ciphertext under FHE. There are various transciphering implementations of AES under FHE and recently, we showed that using the CKKS FHE scheme with 128-bit security and commodity GPU, it is possible to decrypt 512 KBs of AES256-CTR encrypted data under FHE encryption in only 2.33 minutes, i.e., only 4.3 milliseconds per AES block, and several orders-of-magnitude faster than reported before when using other FHE schemes such as BGV, B/FV, or TFHE. Today, many applications prefer using an Authenticated Encryption with Associated Data (AEAD) scheme such as AES-GCM instead of just symmetric encryption because the latter only provides confidentiality while the former also provides integrity for the encrypted data. To this end, we showed for the first time that it is possible to decrypt 512KB of AES256-GCM encrypted data under CKKS in 7.66 minutes, i.e., only 14 milliseconds per AES block. In this short talk, we intend to inform the community about our results and implementation. In addition, we will present the concept of Authenticated Transciphering (AT), which is needed for maintaining the integrity guarantees provided by AEAD schemes. This is especially relevant in the context of threshold decryption where each party can see the plaintext, and therefore the AT scheme should nullify the encrypted content if the integrity verification fails to prevent the spreading of the unverified data. While the AT concept refers to all FHE and threshold-FHE schemes, it is particularly challenging when using CKKS. Moreover, as mentioned in Comment Set #5 to NISTIR 8214C, there is a challenge with using threshold-CKKS-based solutions even in the passive security model due to the CKKS error model. We think that because of the benefits that CKKS provides, even in the case of decrypting AES-GCM ciphertexts, it is worth raising the question of whether CKKS fits for threshold constructions again to the community while suggesting several research directions to resolve the issue raised in Comment Set #5. This will enable threshold-FHE-based solution designers to include more efficient CKKS-based implementations in their proposals.

[Video]

Abstract. ZKProof is an open-industry academic initiative that seeks to mainstream zero-knowledge proof (ZKP) cryptography through aninclusive, community-driven standardization process that focuses on interoperability and security. NIST's call for threshold schemes is of interest to us because we believe we could have a good solution to the zero-knowledge proofs of knowledge requested in the draft call. Recently there has been a drive to write end-to-end specifications for at least one general purpose zero-knowledge proof through multiple working groups. These working groups boast profound expertise in the zero-knowledge domain, encompassing both academic scholars and seasoned developers. However, there is a need for more input from people who have prior experience writing standards documentation. We would like to encourage involvement from audience members who have previously been involved in standards but who may not be experts in zero-knowledge.

[Slides] [Video]

Abstract. Ligetron is an efficient post-quantum sublinear non-interactive zero-knowledge system that can be deployed as a web application and scales to billions of gates.  Core to our construction is identifying a good intermediate representation, namely Web Assembly (WASM) that is: (1) versatile to represent complex computations, (2) can be compiled from most popular high-level languages, and (3) embodies rich semantics to derive space-efficiency. Ligetron can take as input an NP relations expressed as a WASM code. This allows us to easily tool new applications by coding in a high-level language such as C/C++/Rust and cross-compile to WASM using standard compilers (eg, emcripten).

[Slides] [Video]

Abstract. In this talk, we will discuss the developments in the field of (multi-authority) attribute-based encryption (ABE) that we feel are applicable to the NIST call for threshold schemes. Ciphertext-policy attribute-based encryption (CP-ABE) is a type of public-key encryption that associates the secret keys with attribute sets and the ciphertexts with policies. In particular, the policy dictates who is granted access to the plaintext. Although most proposed CP-ABE schemes employ a single authority to generate the secret keys, variants exist that allow multiple authorities to generate the secret keys for users. This type of CP-ABE is called multi-authority ABE (MA-ABE). A notable advantage of MA-ABE is that it does not have a single point of failure, both in terms of security and availability. It has therefore been considered extensively for various practical settings. Within the subfield of MA-ABE, there exist different flavors of schemes in terms of correctness and security. In particular, an important distinction is whether the access structure that dictates the thresholdization among the authorities is applied in the master secret keys (upon setup) or in the ciphertexts. Applying the thresholdization in the ciphertexts generally provides more flexibility, as it allows encrypting users to determine the thresholdization based on their requirements. Furthermore, it allows authorities to join or leave the system at any point in time, without requiring that new master secret keys are generated. Another distinction is in whether the authorities can manage different sets of attributes. An advantage of this is that MA-ABE can be applied in settings with multiple trust domains, e.g., medical settings with hospitals, insurance companies and research institutes. With this talk, we intend to inform potential submitters of these different types of MA-ABE and why it is important to consider these differences in the NIST call for threshold schemes.

[Slides] [Video]

Abstract. In this presentation we give a brief note about the main requirements of a threshold signing scheme for the TLS protocol. Separating the signing capabilities across multiple remote parties helps to reduce the damage after a (part of a) key is compromised. Reverse proxies that terminate TLS connections have particular requirements for the use of a threshold signing algorithm. We developed an implementation for threshold RSA, and currently working on the ECDSA case.

[Slides] [Video]

Abstract. Multi-Party Computation (MPC) has become a major tool for protecting hundreds of billions of dollars in cryptocurrency wallets. MPC protocols are currently powering the wallets of Coinbase, Binance, Zengo, BitGo, Fireblocks and many other fintech companies servicing thousands of financial institutions and hundreds of millions of end-user consumers. In this talk, we present four novel key-extraction attacks on popular MPC signing protocols showing how a single corruptedparty may extract the secret in full during the MPC signing process. Our attacks are highly practical (the practicality of the attackdepends on the number of signature-generation ceremonies the attacker participates in before extracting the key). Namely, weshow key-extraction attacks against different threshold-ECDSA protocols/implementations requiring 10$^6$, 256, 16, and *onesignature*, respectively. In addition, we provide proof-of-concept code that implements our attacks. In the interest of drafting specifications for threshold schemes, this talk offers key insights into the considerations and potential pitfalls when utilizing Paillier encryption in an MPC setting.

[Slides] [Video]

Abstract. In this talk, we discuss the conditions under which straight-line extractable non-interactive zero knowledge proofs (NIZKs) in the random oracle model (i.e. without a common reference string) permit threshold realizations that are black-box in the same random oracle. We show that even in the semi-honest setting, any secure protocol to compute such a NIZK cannot make black-box use of the random oracle or a hash function instantiating it if security against all-but-one corruptions is desired, unless the size of the NIZK grows with the number of parties. This presents a fundamental barrier to constructing efficient protocols to securely distribute the computation of NIZKs (and signatures) based on MPC-in-the-head, PCPs/IOPs, and sigma protocols compiled with transformations due to Fischlin, Pass, or Unruh. When the adversary is restricted to corrupt only a constant fraction of parties, we give a positive result by means of a tailored construction, which demonstrates that our impossibility does not extend to weaker corruption models in general.The paper on which this talk is based is available online at https://eprint.iacr.org/2023/1381

[Slides] [Video]

Abstract: In July 2022, NIST selected four public-key quantum-resistant algorithms for standardization after a lengthy evaluation period: Crystals-Kyber, Crystals-Dilithium, Falcon, and SPHINCS+.  Last month the draft versions of the standards were posted for public comment, with the goal of having the first post-quantum cryptographic (PQC) standards finalized and published in 2024.  In this talk, I will give a quick summary of the PQC project, and then briefly discuss how the four selected algorithms work from a high level.  It may be interesting to explore if threshold-friendly implementations of these algorithms are possible.

[Slides] [Video]

Abstract: In the last two decades, there have been a lot of developments in building quantum computers; this is why, in 2017, NIST launched its call for cryptosystems that would resist both classical and quantum computers. Such cryptosystems are said to be quantum-resistant or post-quantum. The goal of this process, referred to as the NIST Post-Quantum Cryptography (PQC) Standardization Process, is to select a list of post-quantum cryptosystems, namely encryption (more precisely KEM) and signature schemes, for standardization. In summer 2022, after roughly 5 years of competition, 4 algorithms were selected to be standardized: Kyber, Dilithium, Falcon and Sphincs+. However, this does not mean the end of the competition, indeed since 3 out of 4 of these candidates are lattice-based schemes, NIST issued an additional call for signatures for the sake of diversity. Concurrently to the aforementioned selection of 4 new PQ standards, NIST selected 4 "alternate" candidates to be further studied by the community; this process is referred to as the Round 4 of NIST PQC Standardization process. Since SIKE, the only isogeny-based candidate got broken, this left 3 code-based alternate candidates, among which NIST could standardize one or several in the coming year(s). In this talk, we will go through the different categories (and their associated mathematical hard problems) for the Round 1 candidates for the additional call. In fact, among the 40 accepted candidates, there are 6+ categories of post-quantum cryptography. Last but not least, we will see a very high level overview of the key generation processes for the Round 4 candidates so that one can check if they are potential threshold friendly schemes.

[Slides] [Video]

Abstract: In February of 2023, NIST announced the decision to standardize the Ascon family for lightweight cryptography applications. This talk provides an overview of the process, and explains the next steps.

[Slides] [Video]

Abstract. In this talk the National Institute of Standards and Technology (NIST) Cryptographic Algorithm Validation Program (CAVP) will be introduced and the methods of algorithm validation will be explained.

[Slides] [Video]

Abstract. Very brief comments explaining how gadgets and modularity are taken into account in the NIST Threshold Call, and some corresponding updates expected in the upcoming revised version of the Call.

[Slides] [Video]

Abstract. In this talk, we present two gadgets in general-purpose MPC for threshold symmetric-key primitives: correlation robust hash functions for better concrete security and authenticated garbling schemes for better concrete efficiency. Firstly, we show the construction of a tweakable circular correlation robust hash (TCCRH) function with high concrete security. It is useful in popular garbling schemes and also for converting correlated OT to standard OT. We show an efficient instantiation of TCCRH based solely on AES modeled as an ideal cipher. The integration of TCCRH and half-gates garbling achieves optimal security. Secondly, we introduce the basic authenticated garbling gadget and explain how it enables active security without relying on generic and “heavy” machinery like cut-and-choose. We also briefly mention our recent progress that further improves the asymptotic efficiency of this gadget, bringing communication close to its semi-honest counterpart.

[Slides] [Video]

Abstract. Garbled Circuits (GC) is a general technique for two-party secure computation (2PC).  Classic GC, modernized with Free-XOR, half-gates, etc, is currently the most efficient 2PC technique for most settings (a setting is defined by a network/compute configuration and computed function).  The main GC cost bottleneck is that of the transmission of the encrypted (garbled) circuit. The most significant drawback of GC is that it relies on the Boolean circuit representation of the computed function. In this talk, I will discuss a Garbled Circuit (GC) gadget Stacked Garbling (SGC).  SGC equips Boolean circuits with conditional branching and allows to efficiently evaluate one of several of the branch clauses.   Specifically, the communication for evaluating the conditional is proportional to the single longest branch (vs all branches in classic GC). I will briefly discuss the usefulness of the SGC gadget in MPC, particularly as we move from Boolean circuits to the more powerful RAM machine model of representing the computed functions.

[Slides] [Video]

Abstract. Garbled Circuit (GC) is a fundamental technique for achieving secure two-party computation (2PC). Classic GC allows two parties to securely execute any program over their joint private inputs, so long that program is expressed as a Boolean circuit. The requirement that programs be expressed as a Boolean circuit is a weakness of the approach, as many programs are more efficient when expressed in other forms. In this talk, I will discuss two GC gadgets: One-Hot Garbling and Garbled RAM. Roughly speaking, these gadgets upgrade GC with the ability to efficiently handle lookup tables and arrays. These capabilities are traditionally expensive to encode as circuits, and their efficient handling can accelerate many secure computations. I will explain how these basic tools are useful in the broad context of MPC, and how they might be useful in specific contexts, such as the secure evaluation of block ciphers.

[Slides] [Video]

Abstract. In this talk, I will discuss the potential and suitability of standardizing gadgets for correlated randomness generation, including vector oblivious linear evaluation (VOLE) and pseudorandom correlation generators (PCGs). VOLE has proven to be an important building block for MPC and ZK, which many threshold protocols depend upon. PCGs can provide succinct methods for obtaining VOLE, as well as more general types of correlated randomness. However, they also come with their own definitional challenges, such as the need for either a trusted key generation procedure or a distributed setup protocol.

[Slides] [Video]

Abstract. The brief session 1b within MPTS 2023 (NIST Workshop for Multi-Party Threshold Schemes 2023) allows for additional oral comments about the NIST Threshold Call/Process. The number of allowed interventions will be limited to the available time slot. Each intervention should not exceed 3 minutes.

List of interventions (time in the edited session video: main commenter: informal description of topic):

• 00:00: Luís Brandão: Introducing the feedback session.
• 00:50: Thomas Prest: Number of queries to define security.
• 05:10: Jonathan Katz: Submissions with various parts versus multiple submissions.
• 07:00: Luís Brandão: Motivate conversation on networking.
• 07:34: Aniket Kate (AK): On networking assumptions and gadgets.
• 09:48: Nigel Smart: On too many options to implement.
• 12:39: Jonathan Katz: Communication model (broadcast; point-to-point).
• 17:15: Aniket Kate: On (in)comparability of efficiency between various options.
• 19:06: Samuel Ranellucci: How much rigor to strive for in a specification.
• 21:08: Rene Peralta: On evaluation of security arguments / community consensus.
• 21:34: Luís Brandão: Wrapping up the feedback session.

During the session, a slide was shown with several suggested topics:

1. Scope of the Threshold Call: refinements to the description of subcategories.
2. Submission requirements in the Threshold Call: needed clarifications.
3. Expressions of interest: intended concrete submissions (and possible submitter team).
4. Need and adoptability: special features and primitives useful for specific applications.
5. Inspiration: suggestions to the community, for submission of concrete threshold schemes.
6. Frameworks: pertinent system models, security formulations, and threshold parameters.
7. Pre/post quantum: concrete pre-quantum versus post-quantum cases worth focusing on.
8. Technicalities: challenges about concrete primitives / threshold schemes / assumptions.
9. External efforts: other processes developing related reference material or specifications.

[Video]

Abstract. The algorithms of Fully Homomorphic Encryption (FHE) schemes are intricate, even under a passive-security model, which is used in state-of-the-art open-source FHE libraries. This talk will describe threshold FHE algorithms and protocols, then discuss the challenges in building and standardizing threshold FHE in an active security model. We suggest a path starting from threshold key generation and threshold decryption, to linearly homomorphic schemes, and finally to fully homomorphic evaluation, and outline some of the challenges associated with these steps, which have to be considered for standardization.

[Slides] [Video]

Abstract. In this presentation, we will focus on a multi-cloud storage security use case. We present a multiparty threshold protocol that leverages multiple cloud service providers (CSPs). Our solution allows a client to store data by sending it to a proxy, which splits it before spreading the shares amongst a set of CSPs. We make use of a combination of primitives, including Secret Sharing Schemes (SSS), All-Or-Nothing Transform (AONT), and an additive Homomorphic Encryption (HE) scheme. This combination brings full confidentiality, integrity and availability without the need for long-term keys. At a high level, the client encrypts its data with an AONT and HE, before the proxy fragments it and spreads the shares over several CSPs using a Threshold SSS. An AONT is a keyless transformation, that makes it impossible to recover the original data unless the entirety of its output is known. To bring confidentiality w.r.t to the proxy, after passing its data through an AONT, the client homomorphically encrypts the first 256 bits of the output.

This HE encrypted part is homomorphically split by the proxy with a secure SSS (e.g. Shamir's), and the rest of the AONT is distributed with a memory-efficient threshold algorithm (e.g. Reed Solomon codes), as no information can leak from it. The AONT is the key to combine both the confidentiality of a secure SSS and the memory efficiency of Reed Solomon codes, even when one considers the proxy or any collusion of CSPs below the threshold might be adversaries. The keyless property of the AONT paired with homomorphic secret sharing removes the need for any long-term keys. Our solution enhances security compared to customers holding data on premise, and can be useful for compliance issues with holding data in the Cloud. Especially when appropriate technical measures are required, as in the California Consumer Privacy Act or the General Data Protection Regulation. This use case shows how AONT combined with other gadgets can be used as a building block for Multiparty Threshold Cryptography use case.

[Slides] [Video]

Abstract. In this presentation we present current work in progress specification for Verifiable Oblivious PRFs, developed at IETF/CFRG. An Oblivious Pseudorandom Function (OPRF) is a party protocol between client and server for computing the output of a Pseudorandom Function (PRF). The protocol is verifiable if the client can verify whether the server used a specific key.  A (V)OPRF is used as a building block for other protocols such as in Privacy Pass unlikable tokens and in OPAQUE, a password-authenticated key exchange. Finally, a Discrete-Logarithm Equivalence (DLEQ) zero knowledge-proof is also defined as part of the specification.

[Slides] [Video]

Abstract. The original t-out-of-n threshold secret sharing scheme, Shamir’s scheme, is based on polynomial evaluation and interpolation.  While useful in many applications, such as key management and secure multi-party computation (MPC), the scheme comes with several, often-acceptable limitations: (1) due to interpolation, the secret must live in a group (finite field) where every element has a unique multiplicative inverse, and (2) there must be more group elements than shares.  In this presentation, we present a technique for building a t-out-of-n threshold secret sharing scheme from any n-out-of-n secret sharing scheme (particularly, even those that do not satisfy the aforementioned conditions).  Then, we examine the features and limitations of these constructed schemes to draw inferences about the flexibility and feasibility of threshold secret sharing in general.  In particular, we consider operations (inspired by real-world use cases) which can be computed without communication in some of the constructed schemes (but not in any variant of Shamir’s scheme).  We discuss how the proposed work relates directly to threshold schemes for crypto primitives, such as those considered in the NIST call for multi-party threshold schemes, considering that the added flexibility of the approach enables the use of multiple mathematical structures (with various algebraic and homomorphic properties) as a foundation for a threshold scheme.

[Video]

Abstract. Threshold signature protocols in the literature commonly rely on broadcast channels for security and termination. Assuming (bounded) synchrony, a broadcast channel can be built over point-to-point channels between computing parties. However, for latency-sensitive applications such as distributed random beacons and threshold wallets, the Internet cannot be considered to be bounded synchronous. And, broadcast channels cannot be realized, by definition, if the network is not synchronous. Many contemporary threshold cryptographic proposals leverage blockchains as broadcast channels. However, blockchains (i.e., state machine replication (SMR) systems) only ensure that any two honest parties store the same prefix of messages in their logs. This makes SMR unsuitable as true broadcast channels. Indeed, an adversary can force an honest sender's message to not appear on a blockchain in time unless for an exorbitant broadcast time-out value. In this talk, we advocate an alternative-but-natural design approach for building threshold cryptosystems in practice. Thanks to tremendous growth in the SMR/blockchain space in the last decade, we now have SMR solutions that offer sub-second level latency and throughput above 100K msg/sec. We propose to employ these extensively available blockchains for building threshold cryptography solutions; however, we treat them as SMRs and not as broadcast channels. In the talk, we will first focus on a key gadget/primitive that is highly suitable for this setting: non-interactive (publicly verifiable) secret sharing (PVSS). We will demonstrate how the PVSS and SMR combination allows us to develop a distributed key generation setup for ECDSA, EdDSA/Schnorr, and BLS signatures. While building threshold BLS signatures will be straightforward in this setup, we will need secure multi-party computation (MPC) capability for threshold ECDSA/EdDSA signatures. In the talk, we will then present how to build these solutions using threshold additive-homomorphic encryption as a gadget along with  PVSS and SMR for MPC. Finally, we will discuss solutions and challenges towards converting any broadcast-based threshold cryptosystem to one using an SMR.

[Slides] [Video]

Abstract. Recalling all presentations given at MPTS 2023, final remarks and thank you notes to all participants (speakers, attendees, session chairs), and good bye.

[Video]