Non-interactive zero-knowledge proofs (NIZK) are essential building blocks in threshold cryptosystems like multiparty signatures, distributed key generation, and verifiable secret sharing, allowing parties to prove correct behavior without revealing secrets. Furthermore, universally composable (UC) NIZKs enable seamless composition in the larger cryptosystems. A popular way to construct NIZKs is to compile interactive protocols using the Fiat-Shamir transform. Unfortunately, Fiat-Shamir...

The SPDZ protocol family is a popular choice for secure multi-party computation (MPC) in a dishonest majority setting with active adversaries. Over the past decade, a series of studies have focused on improving its offline phase, where special additive shares, called authenticated triples, are generated. However, to accommodate recent demands for matrix operations in secure machine learning and big integer arithmetic in distributed RSA key generation, updates to the offline phase are...

Distributed Key Generation (DKG) is a technique that enables the generation of threshold cryptography keys among a set of mutually untrusting nodes. DKG generates keys for a range of decentralized applications such as threshold signatures, multiparty computation, and Byzantine consensus. Over the past five years, research on DKG has focused on optimizing network communication protocols to improve overall system efficiency by reducing communication complexity. However, SOTA asynchronous...

A threshold signature scheme distributes the ability to generate signatures through distributed key generation and signing protocols. A threshold signature scheme should be functionally interchangeable, meaning that a signature produced by a threshold scheme should be verifiable by the same algorithm used for non-threshold signatures. To resist future attacks from quantum adversaries, lattice-based threshold signatures are desirable. However, the performance of existing lattice-based...

We propose a new framework based on random submersions — that is projection over a random subspace blinded by a small Gaussian noise — for constructing verifiable short secret sharing and showcase it to construct efficient threshold lattice-based signatures in the hash-and-sign paradigm, when based on noise flooding. This is, to our knowledge, the first hash-and-sign lattice-based threshold signature. Our threshold signature enjoys the very desirable property of robustness, including at key...

For more than forty years, two principal questions have been asked when designing verifiable election systems: how will the integrity of the results be demonstrated and how will the privacy of votes be preserved? Many approaches have been taken towards answering the first question such as use of MixNets and homomorphic tallying. But in the academic literature, the second question has always been answered in the same way: decryption capabilities are divided amongst multiple independent...

In the *Distributed Secret Sharing Generation* (DSG) problem $n$ parties wish to obliviously sample a secret-sharing of a random value $s$ taken from some finite field, without letting any of the parties learn $s$. *Distributed Key Generation* (DKG) is a closely related variant of the problem in which, in addition to their private shares, the parties also generate a public ``commitment'' $g^s$ to the secret. Both DSG and DKG are central primitives in the domain of secure multiparty...

Asynchronous Remote Key Generation (ARKG) is a primitive introduced by Frymann et al. at ACM CCS 2020. It enables a sender to generate a new public key $pk'$ for a receiver ensuring only it can, at a later time, compute the corresponding private key sk'. These key pairs are indistinguishable from freshly generated ones and can be used in various public-key cryptosystems such as digital signatures and public-key encryption. ARKG has been explored for applications in WebAuthn credential backup...

In this paper we propose verifiable secret sharing (VSS) schemes secure for any honest majority in the synchronous model, and that only use symmetric-key cryptographic tools, therefore having plausibly post-quantum security. Compared to the state-of-the-art scheme with these features (Atapoor et al., Asiacrypt `23), our main improvement lies on the complexity of the ``optimistic'' scenario where the dealer and all but a small number of receivers behave honestly in the sharing phase: in this...

We present distributed key generation and decryption protocols for an additively homomorphic cryptosystem based on class groups, improving on a similar system proposed by Braun, Damgård, and Orlandi at CRYPTO '23. Our key generation is similarly constant round but achieves lower communication complexity than the previous work. This improvement is in part the result of relaxing the reconstruction property required of the underlying integer verifiable secret sharing scheme. This eliminates the...

Mercurial signatures are an extension of equivalence class signatures that allow malleability for the public keys, messages, and signatures within the respective classes. Unfortunately, the most efficient construction to date suffers from a weak public key class-hiding property, where the original signer with the signing key can link the public keys in the same class. This is a severe limitation in their applications, where the signer is often considered untrustworthy of privacy. This...

Multi-valued Validated Asynchronous Byzantine Agreement ($\mathsf{MVBA}$) is one essential primitive for many distributed protocols, such as asynchronous Byzantine fault-tolerant scenarios like atomic broadcast ($\mathsf{ABC}$), asynchronous distributed key generation, and many others. Recent efforts (Lu et al, PODC' 20) have pushed the communication complexity of $\mathsf{MVBA}$ to optimal $O(\ell n + \lambda n^2)$, which, however, heavily rely on ``heavyweight'' cryptographic tools,...

Verifiable random functions (VRFs) are pseudorandom functions with the addition that the function owner can prove that a generated output is correct (i.e., generated correctly relative to a committed key). In this paper we introduce the notion of an exponent-VRF (eVRF): a VRF that does not provide its output $y$ explicitly, but instead provides $Y = y \cdot G$, where $G$ is a generator of some finite cyclic group (or $Y=g^y$ in multiplicative notation). We construct eVRFs from DDH and from...

With the rapidly evolving landscape of cryptography, blockchain technology has advanced to cater to diverse user requirements, leading to the emergence of a multi-chain ecosystem featuring various use cases characterized by distinct transaction speed and decentralization trade-offs. At the heart of this evolution lies digital signature schemes, responsible for safeguarding blockchain-based assets such as ECDSA, Schnorr, and EdDSA, among others. However, a critical gap exists in the...

Asynchronous complete secret sharing (ACSS) is a foundational primitive in the design of distributed algorithms and cryptosystems that require secrecy. Dual-threshold ACSS permits a dealer to distribute a secret to a collection of $n$ servers so that everyone holds shares of a polynomial containing the dealer's secret. This work contributes a new ACSS protocol, called Haven++, that uses packing and batching to make asymptotic and concrete advances in the design and application of ACSS for...

In this paper, we propose a novel bi-primality test to determine whether $N=pq$ is the product of two primes on any RSA modulus in which we relaxed the restriction, $p\equiv q \equiv 3 \Mod{4}$, that was assumed in most of current bi-primality tests. Our bi-primality test is generalized from Lucas primality test to the bi-prime case. Our test always accepts when $p$ and $q$ are both prime, and otherwise accepts with probability at most $1/2$. In addition, we also prove that the...

Shared randomness in blockchain can expand its support for randomized applications and can also help strengthen its security. Many existing blockchains rely on external randomness beacons for shared randomness, but this approach reduces fault tolerance, increases latency, and complicates application development. An alternate approach is to let the blockchain validators generate fresh shared randomness themselves once for every block. We refer to such a design as the \emph{on-chain}...

Several distributed protocols, including distributed key generation (DKG) and interactive consistency (IC), depend on $\mathcal{O}(n)$ instances of Byzantine Broadcast or Byzantine Agreement among $n$ nodes, resulting in ${\Theta}(n^3)$ communication overhead. In this paper, we provide a new methodology of realizing such broadcasts we call DRAGON: Decentralization at the cost of Representation after Arbitrary GrOupiNg. At the core of it, we arbitrarily group nodes into small ``shards''...

A randomness beacon is a source of continuous and publicly verifiable randomness which is of crucial importance for many applications. Existing works on randomness beacons suffer from at least one of the following drawbacks: (i) security only against static (i.e., non-adaptive) adversaries, (ii) each epoch takes many rounds of communication, or (iii) computationally expensive tools such as proof-of-work (PoW) or verifiable delay functions (VDF). In this work, we introduce GRandLine, the...

A multisignature scheme is used to aggregate signatures by multiple parties on a common message $m$ into a single short signature on $m$. Multisignatures are used widely in practice, most notably, in proof-of-stake consensus protocols. In existing multisignature schemes, the verifier needs the public keys of all the signers in order to verify a multisignature issued by some subset of signers. We construct new practical multisignature schemes with three properties: (i) the verifier only...

The classical distributed key generation protocols (DKG) are resurging due to their widespread applications in blockchain. While efforts have been made to improve DKG communication, practical large-scale deployments are still yet to come due to various challenges, including the heavy computation and communication (particularly broadcast) overhead in their adversarial cases. In this paper, we propose a practical DKG for DLog-based cryptosystems, which achieves (quasi-)linear computation and...

Publicly Verifiable Secret Sharing (PVSS) allows a dealer to publish encrypted shares of a secret so that parties holding the corresponding decryption keys may later reconstruct it. Both dealing and reconstruction are non-interactive and any verifier can check their validity. PVSS finds applications in randomness beacons, distributed key generation (DKG) and in YOSO MPC (Gentry et al. CRYPTO'21), when endowed with suitable publicly verifiable re-sharing as in YOLO YOSO (Cascudo et al....

Cryptographic applications often require proving statements about hidden secrets satisfying certain circuit relations. Moreover, these proofs must often be generated obliviously, i.e., without knowledge of the secret. This work presents a new technique called --- FRI on hidden values --- for efficiently proving such statements. This technique enables a polynomial commitment scheme for values hidden inside linearly homomorphic primitives, such as linearly homomorphic encryption, linearly...

In the past decade, blockchains have seen various financial and technological innovations, with cryptocurrencies reaching a market cap of over 1 trillion dollars. However, scalability is one of the key issues hindering the deployment of blockchains in many applications. To improve the throughput of the transactions, zkRollups and zkEVM techniques using the cryptographic primitive of zero-knowledge proofs (ZKPs) have been proposed and many companies are adopting these technologies in the...

Distributed key management (DKM) services are multi-party services that allow their users to outsource the generation, storage, and usage of cryptographic private keys, while guaranteeing that none of the involved service providers learn the private keys in the clear. This is typically achieved through distributed key generation (DKG) protocols, where the service providers generate the keys on behalf of the users in an interactive protocol, and each of the servers stores a share of each key...

We present new protocols for threshold Schnorr signatures that work in an asynchronous communication setting, providing robustness and optimal resilience. These protocols provide unprecedented performance in terms of communication and computational complexity. In terms of communication complexity, for each signature, a single party must transmit a few dozen group elements and scalars across the network (independent of the size of the signing committee). In terms of computational...

Protocols for distributed (threshold) key generation (DKG) in the discrete-logarithm setting have received a tremendous amount of attention in the past few years. Several synchronous DKG protocols have been proposed, but most such protocols are not fully secure: they either allow corrupted parties to bias the key, or are not robust and allow malicious parties to prevent successful generation of a key. We explore the round complexity of fully secure DKG in the honest-majority setting where...

In the threshold version of Paillier's encryption scheme, a set of parties collectively holds the secret decryption key through a secret sharing scheme. Whenever a ciphertext is to be decrypted, the parties send their decryption shares, which are then verified for correctness and combined into the plaintext. The scheme has been widely adopted in various applications, from secure voting to general purpose MPC protocols. However, among the handful existing proposals for a maliciously...

Threshold signatures are digital signature schemes in which a set of $n$ signers specify a threshold $t$ such that any subset of size $t$ is authorized to produce signatures on behalf of the group. There has recently been a renewed interest in this primitive, largely driven by the need to secure highly valuable signing keys, e.g., DNSSEC keys or keys protecting digital wallets in the cryptocurrency ecosystem. Of special interest is FROST, a practical Schnorr threshold signature scheme, which...

A Distributed Key Generation (DKG) protocol is an essential component of threshold cryptography. DKGs enable a group of parties to generate a secret and public key pair in a distributed manner so that the secret key is protected from being exposed, even if a certain number of parties are compromised. Robustness further guarantees that the construction of the key pair is always successful, even if malicious parties try to sabotage the computation. In this paper, we construct two efficient...

In this brief, we realize different architectural techniques towards improving the performance of post-quantum cryptography (PQC) algorithms when implemented as hardware accelerators on an application-specific integrated circuit (ASIC) platform. Having SABER as a case study, we designed a 256-bit wide architecture geared for high-speed cryptographic applications that incorporates smaller and distributed SRAM memory blocks. Moreover, we have adapted the building blocks of SABER to process...

The applications of Hierarchical Deterministic Wallet are rapidly growing in various areas such as cryptocurrency exchanges and hardware wallets. Improving privacy and security is more important than ever. In this study, we proposed a protocol that fully support a two-party computation of BIP32. Our protocol, similar to the distributed key generation, can generate each party’s secret share, the common chain-code, and the public key without revealing a seed and any descendant private keys. We...

Secure distributed generation of RSA moduli (e.g., generating $N=pq$ where none of the parties learns anything about $p$ or $q$) is an important cryptographic task, that is needed both in threshold implementations of RSA-based cryptosystems and in other, advanced cryptographic protocols that assume that all the parties have access to a trusted RSA modulo. In this paper, we provide a novel protocol for secure distributed RSA key generation based on the Miller-Rabin test. Compared with the...

We propose hinTS --- a new threshold signature scheme built on top of the widely used BLS signatures. Our scheme enjoys the following attractive features: \begin{itemize} \item A {\em silent setup} process where the joint public key of the parties is computed as a deterministic function of their locally computed public keys. \item Support for {\em dynamic} choice of thresholds and signers, after the silent setup, without further interaction. \item Support for {\em general}...

We put forward a non-interactive verifiable secret sharing (NI-VSS) scheme using class groups – we call it cgVSS. Our construction follows the standard framework of encrypting the shares to a set of recipients and generating a non-interactive proof of correct sharing. However, as opposed to prior works, such as Groth’s [Eprint 2021], or Gentry et al.’s [Eurocrypt 2022], we do not require any range proof - this is possible due to the unique structure of class groups, that enables efficient...

We describe high-throughput threshold protocols with guaranteed output delivery for generating Schnorr-type signatures. The protocols run a single message-independent interactive ephemeral randomness generation procedure (e.g., DKG) followed by a \emph{non-interactive} multi-message signature generation procedure. The protocols offer significant increase in throughput already for as few as ten parties while remaining highly-efficient for many hundreds of parties with thousands of signatures...

In this work, we present a novel generic construction for a Distributed Key Generation (DKG) scheme. Our generic construction relies on three modular cryptographic building blocks. The first is an aggregatable Verifiable Secret Sharing (AgVSS) scheme, the second is a Non-Interactive Key Exchange (NIKE) scheme, and the third is a secure hash function. We give formal definitions for the AgVSS and NIKE schemes, as well as concrete constructions. The utility of this generic construction is...

Private Stream Aggregation (PSA) schemes are efficient protocols for distributed data analytics. In a PSA scheme, a set of data producers can encrypt data for a central party so that it learns the sum of all encrypted values, but nothing about each individual value. Thus, a trusted aggregator is avoided. However, all known PSA schemes still require a trusted party for key generation. In this paper we propose the first PSA scheme that does not rely on a trusted party. We argue its security...

Aggregate statistics derived from time-series data collected by individual users are extremely beneficial in diverse fields, such as e-health applications, IoT-based smart metering networks, and federated learning systems. Since user data are privacy-sensitive in many cases, the untrusted aggregator may only infer the aggregation without breaching individual privacy. To this aim, secure aggregation techniques have been extensively researched over the past years. However, most existing...

Privacy-preserving neural network based on secure multi-party computation (MPC) enables multiple parties to jointly train neural network models without revealing sensitive data. In privacy-preserving neural network, the high communication costs of securely computing non-linear functions is the primary performance bottleneck. For commonly used non-linear functions, such as ReLU, existing work adopts an offline-online computation paradigm and utilizes distributed comparison function (DCF) to...

A distributed point function (DPF) (Gilboa-Ishai, Eurocrypt 2014) is a cryptographic primitive that enables compressed additive secret-sharing of a secret weight-1 vector across two or more servers. DPFs support a wide range of cryptographic applications, including efficient private information retrieval, secure aggregation, and more. Up to now, the study of DPFs was restricted to the computational security setting, relying on one-way functions. This assumption is necessary in the case of a...

We present Bingo, an adaptively secure and optimally resilient packed asynchronous verifiable secret sharing (PAVSS) protocol that allows a dealer to share $f+1$ secrets with a total communication complexity of $O(\lambda n^2)$ words, where $\lambda$ is the security parameter and $n$ is the number of parties. Using Bingo, we obtain an adaptively secure validated asynchronous Byzantine agreement (VABA) protocol that uses $O(\lambda n^3)$ expected words and constant expected time, which we in...

Distributed key generation (DKG) allows bootstrapping threshold cryptosystems without relying on a trusted party, nowadays enabling fully decentralized applications in blockchains and multiparty computation (MPC). While we have recently seen new advancements for asynchronous DKG (ADKG) protocols, their performance remains the bottleneck for many applications, with only one protocol being implemented (DYX+ ADKG, IEEE S&P 2022). DYX+ ADKG relies on the Decisional Composite Residuosity...

In permissionless consensus, the ordering of transactions or inputs in each block is freely determined by an anonymously elected block leader. A rational block leader will choose an ordering of inputs that maximizes financial gain; the emergence of automatic market makers in decentralized finance enables the block leader to front-run honest trade orders by injecting its own inputs prior to and after honest trades. Front-running is rampant in decentralized finance and reduces the utility of...

GGM tree is widely used in the design of correlated oblivious transfer (COT), subfield vector oblivious linear evaluation (sVOLE), distributed point function (DPF), and distributed comparison function (DCF). Often, the cost associated with GGM tree dominates the computation and communication of these protocols. In this paper, we propose a suite of optimizations that can reduce this cost by half. • Halving the cost of COT and sVOLE. Our COT protocol introduces extra correlation to each...

Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted party. DKG is an essential building block to many decentralized protocols such as randomness beacons, threshold signatures, Byzantine consensus, and multiparty computation. While significant progress has been made recently, existing asynchronous DKG constructions are inefficient when the reconstruction threshold is larger than one-third of the total nodes. In this paper, we present a simple...

Distributed key generation (DKG) protocols are an essential building block for threshold cryptosystems. Many DKG protocols tolerate up to $t_s<n/2$ corruptions assuming a well-behaved synchronous network, but become insecure as soon as the network delay becomes unstable. On the other hand, solutions in the asynchronous model operate under arbitrary network conditions, but only tolerate $t_a<n/3$ corruptions, even when the network is well-behaved. In this work, we ask whether one can...

In this paper we introduce dCommon - auditable and programmable MPC as a service for solving multichain governance coordination problems throughout DeFi and Web3; Along with its on-chain part Common Interest Protocol (CIP) - an autonomous and immutable registry smart contract suite. CIP enables arbitrary business logic for off-chain computations using dCommon’s network/subnetworks with Ethereum smart contracts. In Stakehouse, CIP facilitates a trustless recovery of signing keys and key...

CSI-FiSh is one of the most efficient isogeny-based signature schemes, which is proven to be secure in the Quantum Random Oracle Model (QROM). However, there is a bottleneck in CSI-FiSh in the threshold setting, which is that its public key needs to be generated by using $k-1$ secret keys. This leads to very inefficient threshold key generation protocols and also forces the parties to store $k-1$ secret shares. We present CSI-SharK, a new variant of $\textit{CSI}$-FiSh that has more...

Public blockchains are state machines replicated via distributed consensus protocols. Information on blockchains is public by default---marking privacy as one of the key challenges. We identify two shortcomings of existing approaches to building blockchains for general privacy-preserving applications, namely (1) the reliance on external trust assumptions and (2) the dependency on execution environments (on-chain, off-chain, zero-knowledge, etc.) with heterogeneous programming...

A distributed point function (DPF) is a cryptographic primitive that enables compressed additive sharing of a secret unit vector across two or more parties. Despite growing ubiquity within applications and notable research efforts, the best 2-party DPF construction to date remains the tree-based construction from (Boyle et al, CCS'16), with no significantly new approaches since. We present a new framework for 2-party DPF construction, which applies in the setting of feasible...

Secret sharing is an essential tool for many distributed applications, including distributed key generation and multiparty computation. For many practical applications, we would like to tolerate network churn, meaning participants can dynamically enter and leave the pool of protocol participants as they please. Such protocols, called Dynamic-committee Proactive Secret Sharing (DPSS), have recently been studied; however, existing DPSS protocols do not gracefully handle faults: the presence...

A distributed network has Mempool Privacy if transactions remain en- crypted until their inclusion is finalized, and inclusion guarantees decryption and execution. Mempool Privacy is highly desirable to prevent transaction censorship and a broad class of MEV attacks. We present Ferveo, a fast protocol for Mempool Privacy on BFT consensus blockchains, such as those based on Tendermint. Blockchain validators use new Distributed Key Generation and Threshold Public Key Encryption schemes to...

Threshold signatures are a crucial tool for many distributed protocols. As shown by Cachin, Kursawe, and Shoup (PODC '00), schemes with unique signatures are of particular importance, as they allow to implement distributed coin flipping very efficiently and without any timing assumptions. This makes them an ideal building block for (inherently randomized) asynchronous consensus protocols. The threshold BLS signature of Boldyreva (PKC '03) is both unique and very compact, but unfortunately...

We consider protocols for secure multi-party computation (MPC) under honest majority, i.e., for $n$=$2t+1$ players of which $t$ are corrupt, that achieve guaranteed output delivery (GOD), and operate in a single initial round of broadcast (BC), followed by steps of asynchronous peer-to-peer (P2P) messages. The power of closely related ``hybrid networks'' was studied in [Fitzi-Nielsen, Disc'09], [BHN, Podc'10] and [Patra-Ravi, IEEE Tr. Inf. Theory'18]. The interest of such protocols is that...

Recently, number-theoretic assumptions including DDH, DCR and QR have been used to build powerful tools for secure computation, in the form of homomorphic secret-sharing (HSS), which leads to secure two-party computation protocols with succinct communication, and pseudorandom correlation functions (PCFs), which allow non-interactive generation of a large quantity of correlated randomness. In this work, we present a group-theoretic framework for these classes of constructions, which unifies...

This work considers two prominent key management problems in the blockchain space: (i) allowing a (distributed) blockchain system to securely airdrop/send some tokens to a potential client Bob, who is yet to set up the required cryptographic key for the system, and (ii) creating a (distributed) cross-chain bridge that allows interoperability at scale by allowing a (changing) set of nodes in a blockchain to perform transactions on the other blockchain. The existing solutions for the first...

We build the first sub-linear (in fact, potentially constant-time) public-key searchable encryption system: − server can publish a public key $PK$. − anybody can build an encrypted index for document $D$ under $PK$. − client holding the index can obtain a token $z_w$ from the server to check if a keyword $w$ belongs to $D$. − search using $z_w$ is almost as fast (e.g., sub-linear) as the non-private search. − server granting the token does not learn anything about the document $D$, beyond...

Asynchronous Byzantine fault-tolerant (BFT) protocols assuming no timing assumptions are inherently more robust than their partially synchronous counterparts, but typically have much weaker security guarantees. We design and implement WaterBear, a family of new and efficient asynchronous BFT protocols matching all security guarantees of partially synchronous protocols. To achieve the goal, we have developed the local coin (flipping a coin locally and independently at each replica)...

Ever since the appearance of quantum computers, prime factoring and discrete logarithm based cryptography has been put in question, giving birth to the so called post-quantum cryptography. The most prominent field in post-quantum cryptography is lattice-based cryptography, protocols that are proved to be as difficult to break as certain difficult lattice problems like Learning With Errors (LWE) or Ring Learning With Errors (RLWE). Furthermore, the application of cryptographic techniques to...

We revisit decentralized random beacons with a focus on practical distributed applications. Decentralized random beacons (Beaver and So, Eurocrypt 1993) provide the functionality for $n$ parties to generate an unpredictable sequence of bits in a way that cannot be biased, which is useful for any decentralized protocol requiring trusted randomness. Existing beacon constructions are highly inefficient in practical settings where protocol parties need to rejoin after crashes or disconnections,...

Distributed key generation (DKG) is an important building block in designing many efficient distributed protocols. In this work, we initiate the study of communication complexity and latency of distributed key generation protocols under a synchronous network in a point-to-point network. Our key result is the first synchronous DKG protocol for discrete log-based cryptosystems with $O(\kappa n^3)$ communication complexity ($\kappa$ denotes a security parameter) that tolerates $t < n/2$...

The pseudorandom sampling of constant weight words, as it is currently implemented in cryptographic schemes like BIKE or HQC, is prone to the leakage of information on the seed being used for the pseudorandom number generation. This creates a vulnerability when the semantic security conversion requires a deterministic re-encryption. This observation was first made in [HLS21] about HQC and a timing attack was presented to recover the secret key. As suggested in [HLS21] a similar attack...

Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted third party and is a building block to decentralized protocols such as randomness beacons, threshold signatures, and general multiparty computation. Until recently, DKG protocols have assumed the synchronous model and thus are vulnerable when their underlying network assumptions do not hold. The recent advancements in asynchronous DKG protocols are insufficient as they either have poor...

This work investigates efficient multi-party signature schemes in the discrete logarithm setting. We focus on a concurrent model, in which an arbitrary number of signing sessions may occur in parallel. Our primary contributions are: (1) a modular framework for proving the security of Schnorr multisignature and threshold signature schemes, (2) an optimization of the two-round threshold signature scheme $\mathsf{FROST}$ that we call $\mathsf{FROST2}$, and (3) the application of our framework...

A $(t,n)$-public key threshold cryptosystem allows distributing the execution of a cryptographic task among a set of $n$ parties by splitting the secret key required for the computation into $n$ shares. A subset of at least $t+1$ honest parties is required to execute the task of the cryptosystem correctly, while security is guaranteed as long as at most $t < \frac{n}{2}$ parties are corrupted. Unfortunately, traditional threshold cryptosystems do not scale well, when executed at large-scale...

Timed commitments [Boneh and Naor, CRYPTO 2000] are the timed analogue of standard commitments, where the commitment can be non-interactively opened after a pre-specified amount of time passes. Timed commitments have a large spectrum of applications, such as sealed bid auctions, fair contract signing, fair multi-party computation, and cryptocurrency payments. Unfortunately, all practical constructions rely on a (private-coin) trusted setup and do not scale well with the number of...

Many decentralized applications require a common source of randomness that cannot be biased or predicted by any single party. Randomness beacons provide such a functionality, allowing parties to periodically obtain fresh random outputs and verify that they are computed correctly. In this work, we propose Mt. Random, a multi-tiered randomness beacon that combines Publicly Verifiable Secret Sharing (PVSS) and (Threshold) Verifiable Random Function (VRF) techniques in order to provide...

We study new candidates for symmetric cryptographic primitives that leverage alternation between linear functions over $\mathbb{Z}_2$ and $\mathbb{Z}_3$ to support fast protocols for secure multiparty computation (MPC). This continues the study of weak pseudorandom functions of this kind initiated by Boneh et al. (TCC 2018) and Cheon et al. (PKC 2021). We make the following contributions. (Candidates). We propose new designs of symmetric primitives based on alternating moduli. These...

Though recent breakthroughs greatly improved the efficiency of asynchronous Byzantine agreement (BA) protocols, they mainly focused on the setting with private setups, e.g., assuming established non-interactive threshold cryptosystems. Challenges remain to reduce the large communication complexities in the absence of such setups. For example, Abraham et al. (PODC'21) recently gave the first private-setup free construction for asynchronous validated BA (VBA) with expected $\mathcal{O}(n^3)$...

In this paper, we introduce the problem of Asynchronous Data Dissemination (ADD). Intuitively, an ADD protocol disseminates a message to all honest nodes in an asynchronous network, given that at least $t+1$ honest nodes initially hold the message where $t$ is the maximum number of malicious nodes. We design a simple and efficient ADD protocol for $n$ parties that is information-theoretically secure, tolerates up to one-third malicious nodes, and has a communication cost of $O(n|M|+n^2)$ for...

White-box cryptography has been proposed as a software protection technique for applications where limited or no hardware-based security is available. In recent years it has been crucial for enabling the security of mobile payment applications. In this paper we continue a recent line of research on device binding for white-box cryptography. Device binding ensures that a white-box program is only executable on one specific device and is unusable elsewhere. Building on this, we ask the...

Single Secret Leader Election (SSLE) protocols allow a set of users to elect a leader among them so that the identity of the winner remains secret until she decides to reveal herself. This notion was formalized and implemented in a recent result by Boneh, et al. (ACM Advances on Financial Technology 2020) and finds important applications in the area of Proof of Stake blockchains. In this paper we put forward new SSLE solutions that advance the state of the art both from a theoretical and a...

We present a non-interactive publicly verifiable secret sharing scheme where a dealer can construct a Shamir secret sharing of a field element and confidentially yet verifiably distribute shares to multiple receivers. We also develop a non-interactive publicly verifiable resharing scheme where existing share holders of a Shamir secret sharing can create a new Shamir secret sharing of the same secret and distribute it to a set of receivers in a confidential, yet verifiable manner. A public...

We describe a simple method for solving the distributed discrete logarithm problem in Paillier groups, allowing two parties to locally convert multiplicative shares of a secret (in the exponent) into additive shares. Our algorithm is perfectly correct, unlike previous methods with an inverse polynomial error probability. We obtain the following applications and further results. - Homomorphic secret sharing. We construct homomorphic secret sharing for branching programs with *negligible*...

In this paper, we introduce a distributed key generation (DKG) protocol with aggregatable and publicly-verifiable transcripts. Compared with prior publicly-verifiable approaches, our DKG reduces the size of the final transcript and the time to verify it from $O(n^2)$ to $O(n log(n))$, where $n$ denotes the number of parties. As compared with prior non-publicly-verifiable approaches, our DKG leverages gossip rather than all-to-all communication to reduce verification and communication...

A single-sign-on (SSO) is an authentication system that allows a user to log in with a single identity and password to any of several related, yet independent, server applications. SSO solutions eliminate the need for users to repeatedly prove their identities to different applications and hold different credentials for each application. Token-based authentication is commonly used to enable an SSO experience on the web, and on enterprise networks. A large body of work considers distributed...

Anonymous attestation for secure hardware platforms leverages tailored group signature schemes and assumes the hardware to be trusted. Yet, there is an ever increasing concern on the trustworthiness of hardware components and embedded systems. A subverted hardware may, for example, use its signatures to exfiltrate identifying information or even the signing key. In this paper we focus on Enhanced Privacy ID (EPID)---a popular anonymous attestation scheme used in commodity secure hardware...

We present an honest-majority Distributed Key Generation protocol (DKG) based on Shamir's $(k,n)$-threshold secret sharing in the setting of Very Hard Homogenous Spaces (VHHS). DKG's in the DLOG setting use Pedersen commitments, for which there is no known analogue in the VHHS setting. As a replacement, we introduce a new primitive called piecewise verifiable proofs, which allow a prover to prove that a list of NP-statements is valid with respect to a common witness, and such that the...

When electronic wallets are transferred by more than one party, the level of security can be enhanced by decentralising the distribution of authorisation amongst those parties. Threshold signature schemes enable this functionality by allowing multiple cosigners to cooperate in order to create a joint signature. These cosigners interact to sign a transaction which then confirms that a wallet has been transferred. However, in the event of a post-quantum attack, existing threshold signature...

Generating randomness collectively has been a long standing problem in distributed computing. It plays a critical role not only in the design of state-of-the-art BFT and blockchain protocols, but also for a range of applications far beyond this field. We present RandRunner, a random beacon protocol with a unique set of guarantees that targets a realistic system model. Our design avoids the necessity of a (Byzantine fault-tolerant) consensus protocol and its accompanying high complexity and...

Traditional threshold cryptosystems have decentralized core cryptographic primitives like key generation, decryption and signatures. Most threshold cryptosystems, however, rely on special purpose protocols that cannot easily be integrated into more complex multiparty protocols. In this work, we design and implement decentralized versions of lattice-based and elliptic-curve-based public-key cryptoystems using generic secure multiparty computation (MPC) protocols. These are standard...

Accumulators provide compact representations of large sets and compact membership witnesses. Besides constant-size witnesses, public-key accumulators provide efficient updates of both the accumulator itself and the witness. However, bilinear group based accumulators come with drawbacks: they require a trusted setup and their performance is not practical for real-world applications with large sets. In this paper, we introduce multi-party public-key accumulators dubbed dynamic (threshold)...

Threshold ECDSA signatures have received much attention in recent years due to the widespread use of ECDSA in cryptocurrencies. While various protocols now exist that admit efficient distributed key generation and signing, these protocols have two main drawbacks. Firstly, if a player misbehaves, the protocol will abort, but all current protocols give no way to detect which player is responsible for the abort. In distributed settings, this can be catastrophic as any player can cause the...

Many blockchain researches focus on the privacy protection. However, criminals can leverage strong privacy protection of the blockchain to do illegal crimes (such as ransomware) without being punished. These crimes have caused huge losses to society and users. Implementing identity tracing is an important step in dealing with issues arising from privacy protection. In this paper, we propose a blockchain traceable scheme with oversight function (BTSOF). The design of BTSOF builds on SkyEye...

In this paper, a multivariate polynomial and exponential mappings based password protocol is presented. The method can be utilized in public domains. The key generator generates a vector, intended to be used as a password by the authentication protocol subsequently, such that when the vector is substituted and evaluated in certain fixed multivariate polynomials -- that may be listed in a public domain -- the value $0$ is found as a result of proper authentication. The public domain in this...

Vector commitments with subvector openings (SVC) [Lai-Malavolta, Boneh-Bunz-Fisch; CRYPTO'19] allow one to open a committed vector at a set of positions with an opening of size independent of both the vector's length and the number of opened positions. We continue the study of SVC with two goals in mind: improving their efficiency and making them more suitable to decentralized settings. We address both problems by proposing a new notion for VC that we call incremental aggregation and that...

A shuffle argument is a cryptographic primitive for proving correct behaviour of mix-networks without leaking any private information. Several recent constructions of non-interactive shuffle arguments avoid the random oracle model but require the public key to be trusted. We augment the most efficient argument by Fauzi et al. [Asiacrypt 2017] with a distributed key generation protocol that assures soundness of the argument if at least one party in the protocol is honest and additionally...

We present an actively secure, practical protocol to generate the distributed secret keys needed in the SPDZ offline protocol. The resulting distribution of the public and secret keys is such that the associated SHE `noise' analysis is the same as if the distributed keys were generated by a trusted setup. We implemented the presented protocol for distributed BGV key generation within the SCALE-MAMBA framework. Our method makes use of a new method for creating doubly (or even more)...

Recent works on distributed garbling have provided highly efficient solutions for constant-round MPC tolerating an arbitrary number of corruptions. In this work, we improve upon state-of-the-art protocols in this paradigm for further performance gain. First, we propose a new protocol for generating authenticated AND triples, which is a key building block in many recent works. -- We propose a new authenticated bit protocol in the two-party and multi-party settings from bare IKNP OT...

We investigate concretely efficient protocols for distributed oblivious linear evaluation over vectors (Vector-OLE). Boyle et al. (CCS 2018) proposed a protocol for secure distributed pseudorandom Vector-OLE generation using sublinear communication, but they did not provide an implementation. Their construction is based on a variant of the LPN assumption and assumes a distributed key generation protocol for single-point Function Secret Sharing (FSS), as well as an efficient batching scheme...

In this paper, we present the first fully asynchronous distributed key generation (ADKG) algorithm as well as the first distributed key generation algorithm that can create keys with a dual $(f,2f+1)-$threshold that are necessary for scalable consensus (which so far needs a trusted dealer assumption). In order to create a DKG with a dual $(f,2f+1)-$ threshold we first answer in the affirmative the open question posed by Cachin et al. how to create an AVSS protocol with recovery thresholds $...

Distributed key generation (DKG) is a fundamental building block for a variety of cryptographic schemes and protocols, such as threshold cryptography, multi-party coin tossing schemes, public randomness beacons and consensus protocols. More recently, the surge in interest for blockchain technologies, and in particular the quest for developing scalable protocol designs, has renewed and strengthened the need for efficient and practical DKG schemes. Surprisingly, given the broad range of...

Permissioned Blockchain has become quite popular with enterprises forming consortium since it prioritizes trust over privacy. One of the popular platforms for distributed ledger solution, Hyperledger Fabric, requires a transaction to be endorsed or approved by a group of special members known as endorsers before undergoing validation. To endorse a transaction, an endorser mentions its identity along with the signature so that it can be verified later. However, for certain transactions,...

Many cryptocurrencies, such as Bitcoin and Ethereum, do not provide any financial privacy to their users. These systems cannot be used as a medium of exchange as long as they are transparent. Therefore the lack of privacy is the largest hurdle for cryptocurrency mass adoption next to scalability issues. Although many privacy-enhancing schemes had been already proposed in the literature, most of them did not get traction due to either their complexity or their adoption would rely on severe...

ECDSA is a widely adopted digital signature standard. Unfortunately, efficient distributed variants of this primitive are notoriously hard to achieve and known solutions often require expensive zero knowledge proofs to deal with malicious adversaries. For the two party case, Lindell [Lin17] recently managed to get an efficient solution which, to achieve simulation-based security, relies on an interactive, non standard, assumption on Paillier's cryptosystem. In this paper we generalize...

A threshold signature scheme enables distributed signing among $n$ players such that any subgroup of size $t+1$ can sign, whereas any group with $t$ or fewer players cannot. While there exist previous threshold schemes for the ECDSA signature scheme, we present the first protocol that supports multiparty signatures for any $t \leq n$ with efficient, dealerless key generation. Our protocol is faster than previous solutions and significantly reduces the communication complexity as well. We...

Migration of security applications to the cloud poses unique challenges in key management and protection: asymmetric keys which would previously have resided in tamper-resistant, on-premise Hardware Security Modules (HSM) now must either continue to reside in non-cloud HSMs (with attendant communication and integration issues) or must be removed from HSMs and exposed to cloud-based threats beyond an organization's control, e.g. accidental loss, warranted seizure, theft etc. Threshold...

Multikey fully homomorphic encryption (MFHE) allows homomorphic operations between ciphertexts encrypted under different keys. In applications for secure multiparty computation (MPC)protocols, MFHE can be more advantageous than usual fully homomorphic encryption (FHE) since users do not need to agree with a common public key before the computation when using MFHE. In EUROCRYPT 2016, Mukherjee and Wichs constructed a secure MPC protocol in only two rounds via MFHE which deals with a common...

We show how to build distributed key generation and distributed decryption procedures for the LIMA Ring-LWE based post-quantum cryptosystem. Our protocols implement the CCA variants of distributed decryption and are actively secure (with abort) in the case of three parties and honest majority. Our protocols make use of a combination of problem specific MPC protocols, generic garbled circuit based MPC and generic Linear Secret Sharing based MPC. We also, as a by-product, report on the first...