Threshold ECDSA schemes distribute the capability of issuing signatures to multiple parties. They have been used in practical MPC wallets holding cryptocurrencies. However, most prior protocols are not robust, wherein even one misbehaving or non-responsive party would mandate an abort. Robust schemes have been proposed (Wong et al., NDSS ’23, ’24), but they do not match state-of-the-art number of rounds which is only three (Doerner et al., S&P ’24). In this work, we propose robust threshold ECDSA schemes RompSig-Q and RompSig-L that each take three rounds (where the first two are broadcasts, whereas the non-robust scheme of Doerner et al. uses no broadcasts). Building on the works of Wong et al. and further optimized towards saving bandwidth, they respectively take each signer (1.0t+ 1.6) KiB and 3.0 KiB outbound broadcast communication, and thus exhibit bandwidth efficiency that is competitive in practical scenarios where broadcasts are natively handled. RompSig-Q preprocesses multiplications and features fast online signing; RompSig-L leverages threshold CL encryption for scalability and dynamic participation.

We propose the first two-round multi-party signing protocol for the Elliptic Curve Digital Signature Algorithm (ECDSA) in the threshold-optimal setting, reducing the number of rounds by one compared to the state of the art (Doerner et al., S&P '24). We also resolve the security issue of presigning pointed out by Groth and Shoup (Eurocrypt '22), evading a security loss that increases with the number of pre-released, unused presignatures, for the first time among threshold-optimal schemes. Our construction builds on Non-Interactive Multiplication (NIM), a notion proposed by Boyle et al. (PKC '25), which allows parties to evaluate multiplications on secret-shared values in one round. In particular, we use the construction of Abram et al. (Eurocrypt '24) instantiated with class groups. The setup is minimal and transparent, consisting of only two class-group generators. The signing protocol is efficient in bandwidth, with a message size of 1.9 KiB at 128-bit security, and has competitive computational performance.

The proof-of-stake (PoS) protocols aim to reduce the unnecessary computing power waste seen in Bitcoin. Various practical and provably secure designs have been proposed, like Ouroboros Praos (Eurocrypt 2018) and Snow White (FC 2019). However, the essential security property of unpredictability in these protocols remains insufficiently explored. This paper delves into this property in the cryptographic setting to achieve the "best possible" unpredictability for PoS protocols.We first present an impossibility result for all PoS protocols under the single-extension design framework, where each honest player extends one chain per round. The state-of-the-art permissionless PoS protocols (e.g., Praos, Snow White, and more), are all under this single-extension framework. Our impossibility result states that, if a single-extension PoS protocol achieves the best possible unpredictability, then this protocol cannot be proven secure unless more than 73% of stake is honest.To overcome this impossibility, we introduce a new design framework called multi-extension PoS, allowing each honest player to extend multiple chains using greedy strategy in a round. This strategy allows us to construct a class of PoS protocols that achieve the best possible unpredictability. Additionally, we design a new tiebreak rule for the multi-extension protocol to choose the best chain that can be extended faster, ensuring that the adversary cannot slow-down the chain growth of honest players. It is noteworthy that these protocols can be proven secure, assuming a much smaller fraction (e.g., 57%) of stake to be honest.For a comprehensive security analysis in the cryptographic setting, we develop several new techniques. Analyzing chain growth becomes highly non-trivial as players can extend multiple chains. We introduce a new analysis framework using the Markov chain to assess the chain growth of a multi-extension protocol. To prove the common prefix property, we introduce a concept called "virtual chains" and present a reduction from the regular version of the common prefix to "common prefix w.r.t. virtual chains."

Byzantine Fault-Tolerant (BFT) consensus protocols are increasingly utilized in blockchain environments. In such protocols, the leader node holds the authority to dictate the transaction order, potentially impacting the fairness of decentralized finance (DeFi) applications. For instance, attackers can exploit this to manipulate transaction order and conduct front-running attacks. The concept of order-fairness, which recently emerged, has become a critical property for preventing a single node from unilaterally determining transaction order. Protocols designed to uphold order-fairness often rely on the sequence in which transactions appear across the network, a factor that can be influenced by the network’s topology. However, this approach has inherent limitations, such as challenges in avoiding Condorcet cycles (Kelkar et al., Crypto 2020).To address these challenges, we propose a novel definition of fairness that requires concealing transaction content before ordering. Additionally, we extend the definitions of liveness and safety of consensus protocols to cover the transaction decryption process, guaranteeing the successful decryption of transactions. Based on the existing BFT protocol and utilizing threshold encryption algorithms, we designed a framework called EquiBFT which can incorporate fairness to BFT protocols. We have proven that the EquiBFT satisfies fairness while ensuring the liveness and safety. We implemented this framework based on HotStuff (Yin et al., PODC 2019) and validated its feasibility in a real-world network environment.

Single Input Functionality (SIF) is a special case of MPC, where only one distinguished party called dealer holds the secret input. SIF allows the dealer to complete a computation task and send to other parties their respective outputs without revealing any additional information about its secret input. SIF has many applications, including multiple-verifier zero-knowledge and verifiable relation sharing, etc. Recently, several works devote to round-efficient realization of SIF, and achieve 2-round communication in the honest majority setting (Applebaum et al., Crypto 2022; Baum et al., CCS 2022; Yang and Wang, Asiacrypt 2022). In this work, we focus on concrete efficiency and propose the first practical construction for SIF against a dishonest majority in the preprocessing model; moreover, the online phase of our protocol is only 2-round and is highly efficient, as it requires no cryptographic operations and achieves information theoretical security. For SIF among 5 parties, our scheme takes 152.34ms (total) to evaluate an AES-128 circuit with 7.36ms online time. Compared to the state-of-the-art (honest majority) solution (Baum et al., CCS 2022), our protocol is roughly 2 × faster in the online phase, although more preprocessing time is needed. Compared to the state-of-the-art generic MPC against a dishonest majority (Wang et al., CCS 2017; Cramer et al., Crypto 2018), our protocol outperforms them with respect to both total running time and online running time.

The proof-of-stake (PoS) protocols aim to reduce the unnecessary computing power waste seen in Bitcoin. Various practical and provably secure designs have been proposed, like Ouroboros Praos (Eurocrypt 2018) and Snow White (FC 2019). However, the essential security property of unpredictability in these protocols remains insufficiently explored. This paper delves into this property in the cryptographic setting to achieve the "best possible" unpredictability for PoS. We first present an impossibility result for all PoS protocols under the single-extension design framework, where each honest player extends one chain per round. The state-of-the-art permissionless PoS protocols (e.g., Praos, Snow White, and more), are all under this single-extension framework. Our impossibility result states that, if a single-extension PoS protocol achieves the best possible unpredictability, then this protocol cannot be proven secure unless more than 73% of stake is honest. To overcome this impossibility, we introduce a new design framework called multi-extension PoS, allowing each honest player to extend multiple chains using a greedy strategy in a round. This strategy allows us to construct a class of PoS protocols that achieve the best possible unpredictability. It is noteworthy that these protocols can be proven secure, assuming a much smaller fraction (e.g., 57%) of stake to be honest.

Non-interactive zero-knowledge proof or argument (NIZK) systems are widely used in many security sensitive applications to enhance computation integrity, privacy and scalability. In such systems, a prover wants to convince one or more verifiers that the result of a public function is correctly computed without revealing the (potential) private input, such as the witness. In this work, we introduce a new notion, called scriptable SNARK, where the prover and verifier(s) can specify the function (or language instance) to be proven via a script. We formalize this notion in UC framework and provide a generic trusted hardware based solution. We then instantiate our solution in both SGX and Trustzone with Lua script engine. The system can be easily used by typical programmers without any cryptographic background. The benchmark result shows that our solution is better than all the known SNARK proof systems w.r.t. prover’s running time (1000 times faster), verifier’s running time, and the proof size. In addition, we also give a lightweight scriptable SNARK protocol for hardware with limited state, e.g., Θ ( λ ) bits. Finally, we show how the proposed scriptable SNARK can be readily deployed to solve many well-known problems in the blockchain context, e.g. verifier’s dilemma, fast joining for new players, etc.

Cryptocurrencies have recently gained huge popularity. It is desirable to come up with effective approaches to constructing better blockchain protocols. In this paper, inspired by the 2-hop design by Duong et al (ePrint 2016/716), we put forth a generic paradigm for blockchain design, called n-hop blockchain. It includes one main chain, which is supported by (n -- 1) supporting chains; hence, the main chain can achieve better security performance. In our paradigm, we show that our n-hop design can be easily extended to (n + 1)-hop design. To demonstrate the power of our paradigm, we showcase two instantiations: 2-hop blockchain variant, a combination of proof-of-stake and proof-of-work, and 3-hop blockchain variant, which is extended from 2-hop blockchain variant by adding Byzantine fault tolerance blockchain in 3rd hop.

Notable recent security incidents have generated intense interest in adversaries which attempt to subvert---perhaps covertly---crypto\-graphic algorithms. In this paper we develop (IND-CPA) Semantically Secure encryption in this challenging setting. This fundamental encryption primitive has been previously studied in the "kleptographic setting," though existing results must relax the model by introducing trusted components or otherwise constraining the subversion power of the adversary: designing a Public Key System that is kletographically semantically secure (with minimal trust) has remained elusive to date. In this work, we finally achieve such systems, even when all relevant cryptographic algorithms are subject to adversarial (kleptographic) subversion. To this end we exploit novel inter-component randomized cryptographic checking techniques (with an offline checking component), combined with common and simple software engineering modular programming techniques (applied to the system's black box specification level). Moreover, our methodology yields a strong generic technique for the preservation of any semantically secure cryptosystem when incorporated into the strong kleptographic adversary setting.

The existing (election) voting systems, e.g., representative democracy, have many limitations and often fail to serve the best interest of the people in collective decision making. To address this issue, the concept of liquid democracy has been emerging as an alternative decision-making model to make better use of "the wisdom of crowds". Very recently, a few liquid democracy implementations, e.g. Google Votes and Decentralized Autonomous Organization (DAO), are released; however, those systems only focus on the functionality aspect, as no privacy/anonymity is considered. In this work, we, for the first time, provide a rigorous study of liquid democracy under the Universal Composability (UC) frame- work. In the literature, liquid democracy was achieved via two separate stages -- delegation and voting. We propose an efficient liquid democracy e-voting scheme that uni es these two stages. At the core of our design is a new voting concept called statement voting, which can be viewed as a natural extension of the conventional voting approaches. We remark that our statement voting can be extended to enable more complex voting and generic ledger-based non-interactive multi-party computation. We believe that the statement voting concept opens a door for constructing a new class of e-voting schemes.

Since many cryptographic schemes are about performing computation on data, it is important to consider a computation model which captures the prominent features of modern system architecture. Parallel random access machine (PRAM) is such an abstraction which not only models multiprocessor platforms, but also new frameworks supporting massive parallel computation such as MapReduce.

Universally composable (UC) protocols retain their security properties even when run concurrently alongside arbitrary other protocols. Unfortunately, it is known that UC multiparty computation (for general functionalities, and without assuming honest majority) is impossible without some form of setup. To circumvent this impossibility, various complete setup assumptions have been proposed. With only a few exceptions, past work has viewed these setup assumptions as being implemented by some ideal, incorruptible entity. Any such entity is thus a single point of failure, and security fails catastrophically in case the setup entity is subverted by an adversary. We propose here a clean, general, and generic approach for distributing trust among m arbitrary setups, by modeling potential corruption of setups within the UC framework, where such corruption might be fail-stop, passive, or arbitrary and is in addition to possible corruption of the parties themselves. We show several feasibility and impossibility results in this model, for different specifications of the corruptible sets. For example, we show that given m complete setups, up to t of which might be actively corrupted in an adaptive manner, general multiparty computation with no honest majority is possible if and only if t < m/2.

We consider the classical problem of synchronous broadcast with dishonest majority, when a public-key infrastructure and digital signatures are available. In a surprising result, Hirt and Zikas (Eurocrypt 2010) recently observed that all existing protocols for this task are insecure against an adaptive adversary who can choose which parties to corrupt as the protocol progresses. Moreover, they prove an impossibility result for adaptively secure broadcast in their setting. We argue that the communication model adopted by Hirt and Zikas is unrealistically pes-simistic. We revisit the problem of adaptively secure broadcast in a more natural synchronous model (with rushing), and show that broadcast is possible in this setting for an arbitrary num-ber of corruptions. Our positive result holds under a strong, simulation-based definition in the universal-composability framework. We also study the impact of adaptive attacks on protocols for secure multi-party computation where broadcast is used as a sub-routine. 1

Nowadays it is widely accepted to formulate the security of a protocol carrying out a given task via the “trustedparty paradigm,” where the protocol execution is compared with an ideal process where the outputs are computed by a trusted party that sees all the inputs. A protocol is said to securely carry out a given task if running the protocol with a realistic adversary amounts to “emulating” the ideal process with the appropriate trusted party. In the Universal Composability (UC) framework the program run by the trusted party is called an ideal functionality. While this simulation-based security formulation provides strong security guarantees, its usefulness is contingent on the properties and correct specification of the ideal functionality, which, as demonstrated in recent years by the coexistence of complex, multiple functionalities for the same task as well as by their “unstable” nature, does not seem to be an easy task. In this paper we address this problem, by introducing a general methodology for the sound specification of ideal functionalities. First, we introduce the class of canonical ideal functionalities for a cryptographic task, which unifies the syntactic specification of a large class of cryptographic tasks under the same basic template functionality. Furthermore, this representation enables the isolation of the individual properties of a cryptographic task as separate members of the corresponding class. By endowing the class of canonical functionalities with an algebraic structure we are able to combine basic functionalities to a single final canonical functionality for a given task. Effectively, this puts forth a bottom-up approach for the specification of ideal functionalities: first one defines a set of basic constituent functionalities for the task at hand, and then combines them into a single ideal functionality taking advantage of the algebraic structure. In our framework, the constituent functionalities of a task can be derived either directly or, following a translation strategy we introduce, from existing game-based definitions; such definitions have in many cases captured desired individual properties of cryptographic tasks, albeit in less adversarial settings. Our translation methodology entails a sequence of steps that systematically derive a corresponding canonical functionality given a game-based definition, effectively “lifting” the game-based definition to its composition-safe version. We showcase our methodology by applying it to a variety of basic cryptographic tasks, including commitments, digital signatures, zero-knowledge proofs, and oblivious transfer. While in some cases our derived canonical functionalities are equivalent to existing formulations, thus attesting to the validity of our approach, in others they differ, enabling us to “debug” previous definitions and pinpoint their shortcomings.

This study introduces hidden identity-based signatures (Hidden-IBS), a type of digital signatures that provide mediated signer-anonymity on top of Shamir's identity-based signatures. The motivation of the new signature primitive is to resolve an important issue with the kind of anonymity offered by ‘group signatures’ where it is required that either the group membership list be public for opening signatures or that the opening authority be dependent on the group manager for its operation. Contrary to this, Hidden-IBS does not require the maintenance of a group membership list for opening signatures and they enable an opening authority that is totally independent of the group manager. As the authors argue this makes Hidden-IBS much more attractive than group signatures for a number of applications. In this study, the authors provide a formal model of Hidden-IBS as well as two efficient constructions that realise the new primitive. To demonstrate the power of the new primitive, the authors apply it to solve a problem of current onion-routing systems focusing on the Tor system in particular.