NIST Workshop on Multi-Party Threshold Schemes 2020

Abstract: This talk will open the NIST workshop on multi-party threshold schemes (MPTS) 2020, presenting a viewpoint of the NIST Threshold Cryptography project on the potential for standardization of multi-party threshold schemes. In scope are threshold schemes for NIST-approved key-based cryptographic primitives, such as signing, encryption, decryption and key generation. As laid out in NISTIR 8214A, a necessary step moving forward is the definition of criteria for considering threshold schemes in a standardization effort. The talk will review the logic behind the workshop organization, describe its feedback-collection goal, and outline the program of ensuing talks.

Shamir’s threshold scheme provides a simple and elegant solution for threshold secret sharing. Publicly verifiable secret sharing (PVSS) aims at enhancing Shamir’s scheme to let anyone verify that all participants’ shares are consistent with a unique secret. The basic solution is to accompany the public-key encrypted shares for the respective participants with a noninteractive zero-knowledge proof establishing the consistency of the shares. Every qualified set of participants is thus guaranteed to find the same secret when pooling their decrypted shares. Nonqualified sets of participants will gain no information about the secret from their decrypted shares due to the information-theoretic security of Shamir’s threshold scheme. PVSS finds many applications in threshold cryptography. A major advantage of PVSS over the use of public-key threshold cryptosystems is the dynamic choice of participants each time one wishes to distribute shares of a secret, bypassing the need for any complicated protocols for distributed key generation commonly found in threshold cryptosystems.

In this talk we review the basic ideas behind PVSS and look into a range of applications in threshold cryptography. Many applications relate to secure multiparty computation (MPC) one way or another. For instance, PVSS can be used to secret-share input data among the parties running a (verifiable) MPC protocol. But PVSS can also be used to build an MPC protocol to let a number of parties jointly generate values for a randomness beacon (e.g., as in SCRAPE). In a different direction, modern scenarios pertaining to clouds and blockchains often rely on secure, replicated storage of secret values involving loosely related entities, which can be accommodated using PVSS.

Abstract: We review some ideas that allows optimizing threshold implementations of well-known cryptographic primitives with honest majority and security against malicious adversaries. Specifically, full-fledged zero-knowledge proofs of correct behavior are often not necessary and can be replaced by weaker primitives.

Abstract: The inherent difficulty of maintaining stateful environments over long periods of time gave rise to the paradigm of serverless computing, where mostly-stateless components are deployed on demand to handle computation tasks, and are teared down once their task is complete. Serverless architecture could offer the added benefit of improved resistance to targeted denial-of-service attacks. Realizing such protection, requires that the protocol only uses stateless parties. Perhaps the most famous example of this style of protocols is the Nakamoto consensus protocol used in Bitcoin. We refer to this stateless property as the You-Only-Speak-Once (YOSO) property, and initiate the formal study of it within a new YOSO model. Our model is centered around the notion of roles, which are stateless parties that can only send a single message. Furthermore, we describe several techniques for achieving YOSO MPC; both computational and information theoretic. The talk will be self contained.

Abstract: This talk will examine the methods to thresholdize the various DSA-based signature. With special emphasis on EdDSA and HashEdDSA. These are schemes in which the hash function required to produce a deterministic signature causes a particular problem for standard threshold methods.

Abstract: FROST is an improved threshold Schnorr signature scheme that allows for an optimization from a two-round signing protocol into a single-round protocol with preprocessing. FROST improves upon prior constructions as it is secure against forgery attacks which are demonstrated to be viable against similar schemes in the literature. Excitingly, there is already interest and plans for the use of FROST for practical use.In this talk, we will introduce FROST and the motivations for its design. We will review the security model under which FROST is secure, and how this security model compares to practical deployments of threshold signatures. We will discuss how FROST is compatible with existing protocols such as those that require EdDSA compatibility, as well as next steps for FROST to be deployed and standardized.

Abstract: Schnorr’s signature scheme permits an elegant threshold signing protocol due to its linear signing equation. However each new signature consumes fresh randomness, which can be a major source of issues in practice. In order to mitigate security issues due to bad randomness in deployments, EdDSA (which is a special case of Schnorr) is specified to derive its nonces as a function of the message and the secret key. Implementing this deterministic nonce derivation in a threshold fashion while only using standardized primitives (eg. SHA, AES) is challenging. In this work, we construct protocols that enable such stateless deterministic nonce derivation in a threshold setting, albeit by combining evaluations of standardized PRFs rather than thresholdizing a standardized PRF. While we do not realize a functionally equivalent threshold version of EdDSA, we demonstrate that it is practically feasible to achieve stateless deterministic nonce derivation using standardized primitives in threshold Schnorr.

Abstract: Most recent works on distributed signatures have focused on ECDSA and over variants of Schnorr signatures. However, little attention has been given to constructions based on postquantum secure assumptions like the hardness of lattice problems. In this talk, we present several lattice-based multi-party signing protocols with low round complexity, following the FiatShamir with aborts paradigm due to Lyubashevsky (Asiacrypt 2009). Our constructions can be seen as distributed variants of the fast Dilithium-G signature scheme, or lattice-based counterparts of recent two-round multi-party signing protocol by Drijvers et al. (S&P 2019) in the discrete-log setting. Our result highlights several important similarities and differences which emerge when translating a discrete-log-based protocol to lattice-based one.

Abstract: There are currently two standardization efforts running in parallel at NIST: Threshold Schemes for Cryptographic Primitives, and Post-Quantum Cryptography. Unfortunately, they do not overlap, and this is a problem, since easy thresholdizability is not a property that would magically appear for majority of the cryptographic schemes. In particular, the current post-quantum standard candidates can be thresholdized only with major performance penalty. The message of this brief is that there will be need for efficient threshold post-quantum cryptography as well, and there has to be an explicit call for obtaining such schemes.   

Abstract: Due to security and usability challenges with passwords, the industry is gradually moving to biometric-based authentication. While biometrics are user-friendly, a server-side breach of biometric data is more damaging because, unlike passwords, changing biometric information is difficult. FIDO Alliance, an industry-wide effort to enable biometric authentication, uses an approach where biometric templates and measurements are stored and matched on the client device. A successful match transmits a digital signature (on a fresh challenge) to the server which can verify this. Thus, a server-side breach does not lead to a loss of sensitve user data. We introduce a new framework for Distributing FIDO that securely distributes both the biometric template and signing key among multiple devices, who can collectively perform biometric matching and signature generation without reconstructing the template or signing key on any device. We model security via a real-ideal world UC definition and design several protocols that realize this. 

Abstract: In this talk, we will present different commercial use cases for multiparty threshold schemes and show why these can actually be very diverse. We will then present a series of questions and considerations for standardisation based on different issues that have arisen in our work with customers and in building our products. These relate to both technical cryptographic aspects as well as to the security architecture of such solutions.

Abstract: Standardizing security mechanisms is a challenging and risky endeavor. When the mechanisms are as complex and multi-faceted as threshold cryptosystems, both the challenge and the risk amplify significantly. Still, the increasing dependence of society on the security of complex cryptographic constructs makes such an endeavor essential.I will attempt to highlight the potential gains and pitfalls in the current standardization effort, and propose some guidelines that will hopefully maximize the gain to society and the IT industry, while minimizing the risks. The focus will be on: (a) creating a common language and consensus; (b) the clarity, understandability, and compositionality of the requirements made and guarantees provided; (c) on the need in rigorous security analysis that asserts all that needs to be asserted.

Abstract: Correlated secret randomness is a useful resource for threshold cryptography and secure multiparty computation. A pseudorandom correlation generator (PCG) enables secure deterministic generation of long sources of correlated randomness from short, correlated seeds. The talk will cover the definition of a PCG, constructions of multiparty PCGs for linear correlations using symmetric cryptography (also known as “pseudorandom secret sharing”), and a recent line of work on PCGs for useful nonlinear correlations from different flavors of the Learning Parity with Noise (LPN) assumption. The latter includes practical methods for “silent” OT extension that use much less communication than alternative OT extension techniques.

Abstract: Oblivious Transfer (OT) is a fundamental cryptographic primitive that has been used as a building block in many efficient MPC protocols. Whilst OT inherently requires public-key cryptography, recent advances in the field show that in practice, OT can no longer be considered an expensive primitive. This is mainly due to the OT extension technique of Ishai, Kilian, Nissim and Petrank (CRYPTO 2003), which cheaply produces a large number of OTs starting from just a few seed OTs. In this talk, we will describe the actively secure OT extension protocol of Keller, Orsini and Scholl (CRYPTO 2015) and some variants, and discuss lessons learnt and subsequent developments from the last few years.

Abstract: Garbled Circuits (GC) is the classic, most popular and often the fastest approach to general secure two-party computation (2PC). In the semi-honest model, we can evaluate about two million AND gates per second on commodity devices and networks. This translates, for example, to approximately 330 shared-key AES evaluations per second. With specialized hardware or allowing precomputation, this number can be further greatly increased.Since its introduction by Andrew Yao in 1986, there have been only a small number of improvements to the basic protocol. In this talk, time permitting, I will briefly review the basic protocol and some of the improvements, such as Free-XOR and our recent work Stacked Garbling. I will also talk about stronger security models, particularly cheap-to-achieve covert and publicly verifiable covert (PVC) models.The stability, wide acceptance, simplicity, efficiency and generality of the GC protocol is unique among MPC protocols, and make it a strong candidate for standardization. A standardized GC variant would be a powerful and versatile tool, which would catalyze both wide practical adoption of rich cryptography and further MPC research.

Abstract: Authenticated garbling is a set of protocols for maliciously secure two-party and multiparty computation based on garbled circuits. Implementations have verified its scalability in both the circuit size (e.g., computing billion-sized circuits) and the number of parties (e.g., computing over hundreds of nodes distributed globally). In this talk, I will give an overview of the protocol, a demo of it running on multiple nodes, and a discussion of future directions in the context of multi-party threshold schemes.

Abstract: We study the concrete security of high-performance implementations of half-gates garbling, which all rely on (hardware-accelerated) AES. We find that current instantiations using k-bit wire labels can be completely broken, in the sense that the circuit evaluator learns all the inputs of the circuit garbler, in time O(2^k/C), where C is the total number of gates, possibly across multiple independent executions. The attack can be applied to existing circuit-garbling libraries using k = 80 and would require 267 machine-months and cost about USD 3500. With this as our motivation, we seek a way to instantiate the hash function in the half-gates scheme to achieve better concrete security. We present a construction based on AES that achieves optimal security in the single-instance setting (when only a single circuit is garbled). We also show how to modify the half-gates scheme so that its concrete security does not degrade in the multi-instance setting.

Abstract: In key management based on Multi-Party Computation (MPC) cryptographic primitives are implemented through a distributed protocol executed by a set of MPC components. A fundamental but often ignored part of this, is the way in which control over the individual MPC components is used to address the threat model of the application. This allows the nice mathematical properties of threshold cryptography to address different trust models or different threat models. In this brief we will provide two examples (one where each MPC node is owned by the same enterprise, and one where nodes reflect different policy elements as well as end-user control) and use these to start a discussion about constructing a taxonomy for how to align threats with what it offered by security architectures offered by MPC.

Abstract: The Mathematical Mesh (Mesh) is a Threshold Key Infrastructure (TKI) that uses threshold techniques to manage public key pairs and threshold key shares. The resulting architecture shares many similarities to traditional Kohnfelder model PKIs (e.g. X.509) but with significant differences. The use of threshold techniques provides the ‘key portability’ advantage of using smartcards without the need for a physical token. Devices that are connected to a Mesh profile can decrypt data and authenticate to internal or external infrastructures as authorized by the user/administrator. Authorizations are expressed as threshold key shares mediated by a Mesh service. Through the use of threshold techniques, the service is zero-trust with respect to confidentiality and integrity concerns and limited trust with respect to availability. The Mesh may be used to manage keys for traditional PKI applications (SSH, OpenPGP, S/MIME) or as a platform for building new applications. Current applications include sharing of encrypted data-at-rest between groups of users, a password vault, a contact manager and a replacement for second factor authentication schemes that actually makes sense.

Abstract: Confium is an open-source distributed trust store framework that bridges cryptographers with practical cryptography usage and supports the standardization efforts of threshold cryptography at NIST. It aims to provide a generalized environment with an extensible architecture for the development of trust stores and future cryptographic families. This presentation will briefly describe the framework, its goals and upcoming plans. Confium is a component of RNP, the openly-licensed high performance OpenPGP toolkit, selected by Mozillas Thunderbird to protect its 30+ million users to secure emails end-toend. RNP is a Ribose project. The Confium project is supported by the Next Generation Internet initiative of the European Commission; Ribose is a grantee of the Mozilla Open Source Support (MOSS) Foundational Technology award as well as the MOSS Secure Open Source award.

Abstract: In this brief we want to introduce MPC Alliance (www.mpcalliance.org). We will present:Short term plans (e.g. community building, marketing, surveys, studies); Long term plans (e.g.involvement in MPC standardization); Stats on members (e.g MPCA has tripled its membership inless than a year); Stats on trends (e.g. Over 20 cryptocurrency wallet vendors now offer MPC-based wallets, demonstrating a dramatic increase since the first MPC wallet was introduced in 2018);MPCA structure (e.g. non-profit, present the board); How can workshop attendees can help.

Abstract: Threshold wallets leverage threshold signature schemes (TSS) to distribute signing rights across multiple parties when issuing blockchain transactions. These provide greater assurance against insider fraud, and are sometimes seen as an alternative to methods using a trusted execution environment to issue the signature. This talk describes the authors’ experience with building and analyzing TSS technology, notably the finding of attacks on TSS implementations used by leading organizations such as major exchanges.

Abstract: While prior work has shown that computing k^(-1) is the main challenge for threshold ECDSA and often resort to specialized protocols in order to obtain k^(-1), we show that out-of-the-box MPC suffices to compute a threshold ECDSA signature with essentially the same efficiency as the best existing schemes. To illustrate this generality, we implement our technique with all protocols supported by MP-SPDZ, allowing us to examine the trade-offs (in terms of efficiency) one has to make when choosing between different corruption models (malicious vs. semi-honest) and corruption thresholds (honest vs. dishonest majority). Our technique in particular shines in the preprocessing model, where one wants to make many signatures with the same key.

At the center of our protocol is a generic transformation of a secret-sharing scheme based on the following observation: Let G be a generator of group G of order p. Then, given an additive secret-sharing [x] over a field Zp, the value [x]G can be viewed as an additive secret-sharing over G. Notice that this transformation is entirely local. We achieve active security for the protocol over G using regular SPDZ type MACs. If the base Zp protocol is secured with SPDZ MACs, then the G protocol is secure as well, using the same MACs. Key generation, which has been costly in prior works, is simply generating a sharing of random element [x], converting it to a sharing of [xG] and opening it towards everyone to get the public key.

We use our threshold ECDSA protocol to secure DNSSEC keys. Very few domain owners run their own authoritative name servers and zone management is outsourced to DNS operators. Although outsourcing provides benefits such as increased availability of zones and fewer misconfigurations, several issues related to key management arise when DNSSEC is used. These issues extend from the domain owner relinquishing control of private keys to the DNS operator reusing keys for thousands of domains to the possibility of domain takedown by governments. We show how private keys can be secured in the outsourced DNS setting through threshold ECDSA.

Abstract: Building on the Gennaro & Goldfeder and Lindell & Nof protocols (CCS ’18), we present two threshold ECDSA protocols, for any number of signatories and any threshold, that improve as follows over the state of the art:

• For both protocols, only the last round requires knowledge of the message, and the other rounds can take place in a preprocessing stage, lending to a non-interactive threshold ECDSA protocol.
• Both protocols withstand adaptive corruption of signatories. Furthermore, they include a periodic refresh mechanism and offer full proactive security.
• Both protocols realize an ideal threshold signature functionality within the UC framework, in the global random oracle model, assuming Strong RSA, DDH, semantic security of the Paillier encryption, and a somewhat enhanced variant of existential unforgeability of ECDSA.
• Both protocols achieve accountability by identifying corrupted parties in case of failure to generate a valid signature.

The two protocols are distinguished by the round-complexity and the identification process for detecting cheating parties. Namely:

• For the first protocol, signature generation takes only 4 rounds (down from the current state of the art of 8 rounds), but the identification process requires computation and communication that is quadratic in the number of parties.
• For the second protocol, the identification process requires computation and communication that is only linear in the number of parties, but signature generation takes 7 rounds.

These properties (low latency, compatibility with cold-wallet architectures, proactive security, identifiable abort and composable security) make the two protocols ideal for threshold wallets for ECDSA-based cryptocurrencies.

Abstract: We present a new multiparty protocol for the distributed generation of biprime RSA moduli, with security against any subset of maliciously colluding parties assuming oblivious transfer and the hardness of factoring. Our protocol is highly modular, and its uppermost layer can be viewed as a template that generalizes the structure of prior works and leads to a simpler security proof. We introduce a combined sampling-and-sieving technique that eliminates both the inherent leakage in the approach of Frederiksen et al. (Crypto’18), and the dependence upon additively homomorphic encryption in the approach of Hazay et al. (JCrypt’19). We combine this technique with an efficient, privacy-free check to detect malicious behavior retroactively when a sampled candidate is not a biprime, and thereby overcome covert rejection-sampling attacks and achieve both asymptotic and concrete efficiency improvements over the previous state of the art.

Abstract: In this work, we design and implement the first protocol for distributed generation of an RSA modulus that can support thousands of parties and offers security against active corruption of an arbitrary number of parties. In a nutshell, we first design a highly optimized protocol for this scale that is secure against passive corruptions, and then amplify its security to withstand active corruptions using lightweight succinct zero-knowledge proofs. Our protocol achieves security with “identifiable abort,” where a corrupted party is identified whenever the protocol aborts, and supports public verifiability. Our protocol against passive corruptions extends the recent work of Chen et al. (CRYPTO 2020) that, in turn, is based on the blueprint introduced in the original work of Boneh-Franklin protocol (CRYPTO 1997, J. ACM, 2001). Specifically, we reduce the task of sampling a modulus to secure distributed multiplication, which we implement via an efficient threshold additively homomorphic encryption scheme based on the Ring-LWE assumption. This results in a protocol where the (amortized) per-party communication cost grows logarithmically in the number of parties. In order to minimize the work done by the parties, we employ a “publicly verifiable” coordinator that is connected to all parties and only performs computations on public data. We implemented both the passive and the active variants of our protocol and ran experiments using 2 to 4,000 parties. This is the first implementation of any MPC protocol that can scale to more than 1,000 parties. For generating a 2048-bit modulus among 1,000 parties, our passive protocol executed in under 4 minutes and the active variant ran in 25 minutes.

Abstract: Secure multi-party computation allows a group of mutually distrustful parties to compute a joint function on their inputs without revealing any information beyond the result of the computation. This type of computation is extremely powerful and has wide-ranging applications in academia, industry, and government. In recent years, general-purpose compilers for executing MPC on arbitrary functions have rapidly advanced the state of the art. However, the field is changing so rapidly that it is difficult even for experts to keep track of the varied capabilities of modern frameworks. In this talk, I will describe our survey of general-purpose compilers for secure multi-party computation. We evaluated the tools on a range of criteria, including language expressibility, capabilities of the cryptographic back-end, and accessibility to developers. I will discuss the limitations in documentation and software engineering we identified and discuss how the findings from this work can be used when evaluating multi-party threshold schemes.

Abstract: An important application for threshold signature schemes and specifically for ECDSA is decentralized custody over digital assets. The main idea here is for a committee of nodes to jointly control an asset by maintaining a threshold key allowing to move or spend this asset. Decisions on what actions to perform come either from an external control system, or are made via some form of consensus within the group of nodes. Since we cannot assume that all nodes behave honestly in such systems, a property of crucial importance is "robustness" of signing. This means that whenever a decision to sign a message is made, the committee of nodes should succeed in producing a valid signature, despite adversarial behavior of a subset of them. We propose a new dishonest majority threshold ECDSA protocol that offers robustness and does not require choosing a subset of honest signers for a signature to be generated.

Abstract: The Elliptic Curve Digital Signature Algorithm (ECDSA) is one of the most widely used schemes in deployed cryptography. Through its applications in code and binary authentication, web security, and cryptocurrency, it is likely one of the few cryptographic algorithms encountered on a daily basis by the average person. Standardizing a design for a threshold variant of ECDSA will be significant progress toward standardizing building blocks for threshold cryptosystems at large. However, the design of ECDSA is such that executing multi-party or threshold signatures in a secure manner is challenging: unlike other, less widespread signature schemes, secure multi-party ECDSA requires custom protocols, which has heretofore implied reliance upon additional cryptographic assumptions and primitives such as the Paillier cryptosystem. We introduce new protocols for multi-party ECDSA key-generation and signing with arbitrary thresholds that are secure against malicious adversaries in the Random Oracle Model assuming only the Computational Diffie-Hellman Assumption. We instantiate our protocols using the same hash function and elliptic curve group used by the ECDSA signature being computed. Our threshold t scheme requires log(t)+6 rounds of communication with scope for adjustment to constant rounds if desired, and when t = 2 we provide an optimized two message protocol. Furthermore, our protocols are non-interactive in the preprocessing model. We evaluate our implementations and find that the wall-clock time for computing a signature through our two-party protocol comes to within a factor of 18 of local signatures. Concretely, two parties can jointly sign a message in just over three milliseconds. We also demonstrate the feasibility of signing with a low-power device (as in the setting of 2-factor authentication) by computing a signature between two Raspberry Pi devices in under 60 milliseconds.

Final comments in the end session of the MPTS workshop. Includes updates statistics of registrations, thank you note, and a few comments from the audience.