Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

NIST Workshop on Multi-Party Threshold Schemes 2020

Three days of talks and briefs about threshold schemes, from experts in the area.

Quick Links

 Description

The MPTS2020 workshop is intended as an informal consultation step about the development of criteria for evaluating multi-party threshold schemes for the cryptographic primitives identified in NISTIR 8214A. The organizers are asking the community of stakeholders to participate by providing examples, suggestions and recommendations for the multi-party track of the standardization process considered by the NIST Threshold Cryptography (TC) project. The collected feedback will be taken into consideration in the development process.

  • What: NIST workshop on multi-party threshold schemes.
  • Goal: Collect feedback for the multi-party track of the TC project.
  • How: Invited talks (~20 min each) + Q&A; and submitted briefs (~5 min).
  • Logistics: Participation by video-conference; free attendance based on early registration.
  • When: November 4--6 (9:30am -- 13:00+).

Primitives (see NISTIR 8214A, Section 4.1): 1. RSA signing; 2. RSA decryption; 3. RSA key generation; 4. EdDSA signing; 5. ECDSA signing; 6. ECC-CDH primitive; 7. Keygen for ECC; 8. AES enciphering/deciphering

Some related topics (see NISTIR 8214A, Section 5): 1. Configurability (threshold numbers, ...); 2. Practical feasibility; 3. Security models; 4. Security properties; 5. Gadgets and modularity; 6. Validation suitability.

The Threshold Cryptography (TC) project at the National Institute of Standards and Technology (NIST) is exploring the potential for standardization of threshold schemes for cryptographic primitives. The goal of the multi-party track (see NISTIR 8214A) is to enable the distributed execution of key-based primitives when the keys are secret-shared across multiple parties. By applying a threshold scheme, the confidentiality of the original key is preserved even if some threshold number of parties are compromised. A threshold property can also extend to other security aspects,such as integrity and availability of the operation.

The current focus of the project is on devising criteria for evaluation of threshold schemes that may be proposed in the future for consideration in the TC multi-party track. To develop such criteria, it is essential to obtain meaningful and timely feedback from expert stakeholders. The NIST Workshop on Multi-Party Threshold Schemes (MPTS 2020) is organized as a step to enable the organizers to collect useful feedback from the community. The organizers ask the community to aim at recommendations that promote security, practicality and interoperability, under the umbrella of improving best practices and fostering innovation, within the scope of standardization.

Workshop structure. MPTS 2020 will be a virtual workshop. The presentations and comments will be recorded and made publicly available after the event. The workshop will last three days,with up to four hours per day. The program will be based on two types of contributions:

  • Talks: Invited talks (~20 min talk + ~5 min Q&A), focused on recommendations for criteria for threshold schemes or their elements (e.g., gadgets); each talk is followed by a short period of moderated comments and Q&A.
  • Briefs: Short talks (up to 5 min each), related to the goal of the workshop (requires submitting a title and short description).

We invite the community of stakeholders to participate in the workshop and share their views on threshold schemes for the multi-party track of NISTIR 8214A, and give recommendations on criteria for their standardization. We will publish the collected feedback after the workshop.

Content scope. This workshop and the multi-party track of the TC project cover the cryptographic primitives highlighted in Section 4.1 of NISTIR 8214A. The organizers are interested in characterizing potential threshold schemes with respect to the features in Section 5 of NISTIR 81214A. See also the Sections 2.3--2.5, 6.1 and 7.2.

Disclaimer (standards). The use of the words "standards" and "standardization" in the TC project does not imply a goal of producing new Federal Information Processing Standards (FIPS) publications. For example, the final products may include Recommendations or implementation guidelines to be incorporated in other documentation, such as (but not necessarily) Special Publications in Computer Security (SP 800).

(Note: Statistics updated on 2020-Nov-9. Identified duplicates were not counted.)

Overall workshop registrations (including all speakers): 292 individuals (includes 20 from NIST), across 40+ countries.

Webex registrations (including panelists/hosts) per event: 162 in 1st day: 158 in 2nd day; 140 in 3rd day.

Speakers (19) of invited talks: Berry Schoenmakers, Ivan Damgård, Tal Rabin, Nigel Smart, Chelsea Komlo, Yehuda Lindell, Ran Canetti, Yuval Ishai, Emmanuela Orsini, Peter Scholl, Vladimir Kolesnikov, Xiao Wang, Jean-Philippe Aumasson, Omer Shlomovits, Kris Shrishak, Nikolaos Makriyannis, Schuyler Rosefield, Muthu Venkitasubramaniam, Marcella Hastings.

Speakers (11) of accepted briefs: Yashvanth Kondi, Akira Takahashi, Jan Willemson, Saikrishna Badrinarayanan, Xiao Wang, Jakob Pagter, Phillip Hallam-Baker, Ronald Tse, Frank Wiener, Damian Straszak, Jack Doerner.

Session chairs (5): Luís Brandão, Michael Davidson, Dustin Moody, René Peralta, Apostol Vassilev.

Workshop/program chair (1): Luís Brandão.

(Each listing of names follows the order of the corresponding talks/briefs/sessions at the workshop.)

Thanks to Donal Whitfield for explaining, prior to the workshop, the workings of the video-conference platform.

Statistics based on answers provided in the workshop registration form

Registrations per country

292 registrations across 40+ countries.

Pie chart, showing the number of registrants per country

The USA count includes 20 from NIST.

Familiarity with NISTIR 8214A

Yes: 122; No: 164; N/A: 6

Image showing the cover of NISTIR 8214A

In which primitives are you most interested in?

Primitives of interest

(Multiple answers allowed; answers not mandatory)

What threshold-related topics are of most interest to you?

Topics of interest

(Multiple answers allowed; answers not mandatory)

Deadlines:
  • September 30: early registration (free)
  • September 30: submission of title + abstract for brief intervention (submissions phase 1)
  • October 28: late registration (also free -- the video-conference platform allows it)
  • October 28: submission of title + abstract for brief intervention (submissions phase 2)
  • November 6: We will accept registrations arriving after Oct 28, but there may be a delay in allowing the connection to the virtual event

How to register as an attendee for MPTS 2020:

There are two needed (sequential) registrations for attendees:

Registration 1. Submit the workshop registration form:

https://docs.google.com/forms/d/e/1FAIpQLScY7P4HOG-GhaX5FiaP_DGudiwcyBIqk9cJRzXotCrCg79y-w/viewform

After someone reads your submitted form, you will receive (from a nist.gov email) a "registration password" for the Webex events, as well as the Webex event password.

Registration 2. Apply for a Webex Registration ID for each day of the event:

https://nist-secure.webex.com/nist-secure/onstage/g.php?PRID=a6b80f9da4bda97b06dbaf47a2f6fe4f

The workshop occurs as three Webex virtual events (one per day of the workshop). To connect as an attendee in each event day, first register (with Webex) your email address for the event. You will then receive an email from Webex with a "registration " id, which you'll need (along with the event password, received in step 1) to login to the virtual event.

Note: If you are a presenter, your role in the webex event will be as "Panelist", instead of "Attendee". In such case you will receive different instructions by email.

Submit a proposal for a "brief":

To submit a proposed "brief", please email workshop-MPTS-2020@nist.gov, preferably by September 30 (phase 1) or October 28 (phase 2):

  • Use email subject "MPTS2020 brief: "

  • Include the contact details of the speaker.

  • Attach a 1-page file in PDF format containing: title, name, and abstract.

Lodging Info:

Virtual workshop

For questions or comments related to the workshop, please send an email to "workshop-MPTS-2020 at nist.gov"

Schedule — List of Presentations

Please check the Workshop Program (PDF file) for further details: bios of talks' speakers; abstracts; collaborators.

Session 1a (talks). Session chair: Luís Brandão.

Session 1b (talks). Session chair: Michael Davidson.

Session 1c (briefs): Session chair: Dustin Moody.

09:15--09:35: Virtual arrival

Session 2a (talks): Session chair: Luís Brandão.

Session 2b (talks): Session chair: Rene Peralta.

Session 2c (briefs): Session chair: Apostol Vassilev.

09:15--09:35: Virtual arrival

Session 3a (talks): Session chair: Apostol Vassilev.

Session 3b (talks): Session chair: Rene Peralta.

Session 3c (briefs): Session chair: Luís Brandão.

Each talk was scheduled for 25 min (~20 min monologue + ~5 min Q&A).

Each brief was scheduled for 6 min (5 min talk, plus 1 min transition).

(Schedule details updated on November 20, 2020)

Selected Presentations
November 4, 2020 Type
9:35 AM Let’s talk about multi-party threshold schemes
Luís T. A. N. Brandão - NIST/Strativia

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.

Presentation
10:00 AM Publicly Verifiable Secret Sharing and Its Use in Threshold Cryptography
Berry Schoenmakers - Eindhoven University of Technology

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.

Presentation
10:25 AM Optimizing honest majority threshold cryptosystems
Ivan Damgård - Aarhus University

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.

Presentation
11:05 AM You Only Speak Once – Secure MPC with Stateless Ephemeral Roles
Tal Rabin - Algorand Foundation

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.

Presentation
11:30 AM Thresholdizing DSA, Schnorr, EdDSA, HashEdDSA, ...
Nigel Smart - KU Leuven

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.

Presentation
11:55 AM FROST: Flexible Round-Optimized Schnorr Threshold Signatures and Extensibility to EdDSA
Chelsea Komlo - University of Waterloo and Zcash Foundation

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.

Presentation
12:30 PM Threshold Schnorr with Stateless Deterministic Signing
Yashvanth Kondi - Northeastern University

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.

Presentation
12:36 PM Lattice-based Distributed Signing Protocols from the Fiat–Shamir with Aborts Paradigm
Akira Takahashi - Aarhus University

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.

Presentation
12:42 PM On the need for threshold post-quantum (signature) schemes
Jan Willemson - Cybernetica

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.   

Presentation
12:48 PM BETA: Biometric Enabled Threshold Authentication
Saikrishna Badrinarayanan - Visa Research

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. 

Presentation
November 5, 2020 Type
9:35 AM Settings and Considerations for Standardizing Multi-Party Threshold Schemes
Yehuda Lindell - Unbound Tech and BIU

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.

Presentation
10:00 AM Standardizing Security: The case of threshold cryptography
Ran Canetti - Boston University

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.

Presentation
10:25 AM Pseudorandom Correlation Generators: Secure Computation with Silent Preprocessing
Yuval Ishai - Technion

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.

Presentation
11:05 AM Efficient Actively Secure OT Extension: 5 Years Later
Emmanuela Orsini - KU Leuven
Peter Scholl - Aarhus University

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.

Presentation
11:30 AM Let’s Standardize Garbled Circuits!
Vladimir Kolesnikov - Georgia Tech

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.

Presentation
11:55 AM Global-Scale Threshold AES (and SHA256)
Xiao Wang - Northwestern University

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.

Presentation
12:30 PM Better Concrete Security for Half-Gates Garbling (in the Multi-Instance Setting)
Xiao Wang - Northwestern University

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.

Presentation
12:36 PM MPC-based key management – Using threshold trust to address different threat models
Jakob Pagter - Sepior

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.

Presentation
12:42 PM Towards a Threshold Key Infrastructure
Phillip Hallam-Baker - Comodo

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.

Presentation
12:48 PM Confium: an open source framework to support threshold cryptography standardization
Ronald Tse - Ribose

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.

Presentation
12:54 PM The MPC Alliance (MPCA), Status and Roadmap
Frank Wiener - Sepior

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.

Presentation
November 6, 2020 Type
9:35 AM Attacks to deployed threshold signatures
Jean-Phillippe Aumasson - ZenGo
Omer Shlomovitz - Taurus

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.

Presentation
10:00 AM Securing DNSSEC Keys via Threshold ECDSA from generic MPC
Kris Shrishak - TU Darmstadt

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.

Presentation
10:25 AM UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts
Nikolaos Makriyannis - Fireblocks

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.

Presentation
11:05 AM Multiparty Generation of an RSA Modulus
Schuyler Rosefield - Northeastern University

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.

Presentation
11:30 AM Scaling Distributed RSA Modulus Generation with a Dishonest Majority
Muthu Venkitasubramaniam - Ligero, Inc. and University of Rochester

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.

Presentation
11:55 AM How MPC Frameworks Use Threshold Cryptography
Marcella Hastings - University of Pennsylvania

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.

Presentation
12:30 PM Robustness for Dishonest Majority in Threshold ECDSA
Damian Straszak - Cardinal Cryptography

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.

Presentation
12:36 PM A Multiparty Computation Approach to Threshold ECDSA
Jack Doerner - Northeastern University

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.

Presentation
12:42 PM MPTS 2020 Final Comments
Luís T. A. N. Brandão - NIST/Strativia

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.

Presentation

Event Details

Starts: November 04, 2020 - 09:30 AM EST
Ends: November 06, 2020 - 01:00 PM EST
November 4--6, 2020, 9:30am--1pm EST

Format: Virtual Type: Workshop

Attendance Type: Open to public
Audience Type: Academia

Related Topics

Security and Privacy: cryptography

Created August 13, 2020, Updated June 16, 2021