Our paper "Optimistic, Signature-Free Reliable Broadcast and Its Applications" (arxiv.org/abs/2505.02761) received a Distinguished Paper Award at ACM CCS 2025. A bit of bragging ;)
The effort was led by @nibeshrestha.bsky.social from Supra Labs
Deadline in 46 hr! Hope your ACNS 2026 (acns26-cycle1.hotcrp.com) submissions are coming along well.
Please note that ACNS 2026 will accommodate remote presentations in cases where visa issues arise.
Abstract. Multiparty computation (MPC) is a topic of growing interest for privacy-preserving computation tasks. A few MPC libraries have been developed, and newer protocols are regularly proposed to reduce the latency overhead, improve scalability, and achieve strong termination guarantees. However, most current MPC protocols are designed and implemented assuming network synchrony: in theory, they assume that all messages are delivered within a known time bound, while for experimental analysis, most assume all nodes to be honest, such that the time bounds are never deployed. While deploying MPC systems in the wild and trying to minimize the latency, network synchrony is indeed a strong assumption to make: natural adverse network conditions can break the safety and/or liveness of the protocol due to simply delayed messages. Asynchronous MPC (AMPC) protocols can overcome the challenge as they do not assume fixed time bounds for message delivery delays; however, AMPC faces a natural threshold barrier of 2/3rd honest majority and introduces significant computation and/or communication overheads. This work aims to achieve the best-of-both network models by designing a practical AMPC protocol that has stronger resilience guarantees matching those for synchronous MPC. We achieve this by adopting the emerging helper-aided model, and designing protocols that achieve fairness not only in the simple honest majority setting but also in the dishonest majority setting. Our protocols follow the standard preprocessing-online paradigm, enabling a lightweight and fast input-dependent online phase. In the honest majority setting, our protocol relies solely on lightweight cryptographic operations. In the dishonest majority setting, the protocol requires oblivious transfer (OT) during preprocessing, which we prove is necessary in this setting. We implement our constructions and provide a thorough performance comparison with state-of-the-art MPC protocols in the helper-aided model. Our experiments demonstrate that our protocols substantially outperform the state-of-the-art helper-aided MPC scheme, while being significantly more resilient to network delays.
Image showing part 2 of abstract.
Image showing part 3 of abstract.
Breaking the Barrier for Asynchronous MPC with a Friend (Banashri Karmakar, Aniket Kate, Shravani Patil, Arpita Patra, Sikhar Patranabis, Protik Paul, Divya Ravi) ia.cr/2025/1736
Join us in shaping the program at Applied Cryptography and Network Security (ACNS) 2026 in New York.
(acns2026.github.io)
The first deadline is this Friday AoE.
Abstract. Multi-party computation (MPC) enables a set of mutually n distrusting parties to compute any function on their private inputs. Mainly, MPC facilitates agreement on the function’s output while preserving the secrecy of honest inputs, even against a subset of t parties controlled by an adversary. With applications spanning from anonymous broadcast to private auctions, MPC is considered a cornerstone of distributed cryptography, and significant research efforts have been aimed at making MPC practical in the last decade. However, most libraries either make strong assumptions like the network being bounded synchronous, or incur high computation overhead from the extensive use of expensive public-key operations that prevent them from scaling beyond a few dozen parties. This work presents Velox, an asynchronous MPC protocol that offers fairness against an optimal adversary corrupting up to $t<\frac{n}{3}$ parties. Velox significantly enhances practicality by leveraging lightweight cryptographic primitives - such as symmetric-key encryption and hash functions - which are 2-3 orders of magnitude faster than public-key operations, resulting in substantial computational efficiency. Moreover, Velox is highly communication-efficient, with linear amortized communication relative to circuit size and only 𝒪(n³) field elements of additive overhead. Concretely, Velox requires just 9.33 field elements per party per multiplication gate, more than 10× reduction compared to the state of the art. Moreover, Velox also offers Post-Quantum Security as lightweight cryptographic primitives retain their security against a quantum adversary. We implement Velox comprehensively, covering both offline and online phases, and evaluate its performance on a geographically distributed testbed through a real-world application: anonymous broadcast. Our implementation securely shuffles a batch of k = 256 messages in 4 seconds with n = 16 parties and 18 seconds with n = 64 parties, a 36× and 28.6× reduction in latency compared to the prior best work. At scale with n = 112 parties, Velox is able to shuffle the same batch of messages in under 50 seconds from end to end, illustrating its effectiveness and scalability. Overall, our work removes significant barriers faced by prior asynchronous MPC solutions, making asynchronous MPC practical and efficient for large-scale deployments involving 100s of parties.
Image showing part 2 of abstract.
Image showing part 3 of abstract.
Velox: Scalable Fair Asynchronous MPC from Lightweight Cryptography (Akhil Bandarupalli, Xiaoyu Ji, Aniket Kate, Chen-Da Liu-Zhang, Daniel Pöllmann, Yifan Song) ia.cr/2025/1630
Abstract. In a Web3 (blockchain) setting, account recovery allows users to regain access to their accounts after losing their authentication credentials. Although recovery mechanisms are well-established and extensively analyzed in the context of Web2 systems, Web3 presents distinct challenges. Web3 account access is typically tied to cryptographic key pairs, and private keys are not entrusted to centralized entities. This design improves security, but significantly complicates the recovery process, making it difficult or even impossible for users to regain access after loss of keys. Given the critical role that recovery plays in ensuring long-term feasibility and trust in digital systems, a range of recovery mechanisms has been proposed to accommodate the unique properties of Web3. These mechanisms aim to help users manage key loss without introducing undue friction or risk. Although there has been an exponential increase in the use of cryptocurrency wallets in the last decade, the popularity and usage of the corresponding recovery mechanisms remain unclear. Furthermore, it is still unclear how users perceive these recovery mechanisms and what they expect from them. In this work, our objective is to empirically understand and analyze user perceptions of the various recovery mechanisms. To this end, we conducted a user survey of 331 participants and asked them to rate different mechanisms on usability, security, and availability. The results show interesting aspects of the user preferences, including their view of sharing keys among different devices and trusting their friends or family. Based on our findings, we provide insight and future directions for the developer and research community.
Image showing part 2 of abstract.
Web3 Recovery Mechanisms and User Preferences (Easwar Vivek Mangipudi, Panagiotis Chatzigiannis, Konstantinos Chalkias, Aniket Kate, Mohsen Minaei, Mainack Mondal) ia.cr/2025/1687
Call for Papers (CFP) is up for ACNS 2026
(first deadline in a month)
Place: New York City
acns2026.github.io
Abstract. We present Hydrangea, a partially synchronous Byzantine fault-tolerant state machine replication protocol that achieves a latency of two rounds optimistically while maintaining high adversarial resilience. In particular, for a system of n = 3f + 3p + 1 parties, if up to p parties are faulty, then the protocol can obtain a latency of two rounds. Otherwise, the protocol can obtain a latency of three rounds while tolerating f Byzantine faults and p crash faults {}.
Hydrangea: Optimistic Two-Round Partial Synchrony with One-Third Fault Resilience (Nibesh Shrestha, Aniket Kate, Kartik Nayak) ia.cr/2025/1112
Building anonymous post-office protocols without getting restricted by post-box sizes... via
Oblivious shuffle + ORAM + OMR
Abstract. Directed Acyclic Graph (DAG)-based BFT consensus protocols often suffer from limited throughput and scalability due to bandwidth-intensive data replication to all participants. However, it is sufficient to replicate data to a smaller sub-committee of parties that holds an honest majority with high probability. In this work, we introduce tribe-assisted reliable broadcast, a novel primitive that ensures reliable broadcast (RBC) properties within a smaller honest-majority sub-committee—referred to as a clan—drawn from the entire network, called the tribe. Leveraging this primitive, we develop two efficient DAG-based BFT consensus protocols. First, we present a single-clan protocol, in which a single clan is elected from the tribe, and data is disseminated exclusively to this designated clan using tribe-assisted RBC. We then extend this design to a multi-clan setting, where multiple clans are elected and data is distributed within each respective clan via the same mechanism. Experimental results demonstrate that both protocols offer substantial improvements in throughput and latency over existing DAG-based BFT protocols, even at moderately large scales.
Image showing part 2 of abstract.
Towards Improving Throughput and Scalability of DAG-based BFT SMR (Nibesh Shrestha, Aniket Kate) ia.cr/2025/877
![Abstract. Web3 applications, such as on-chain gaming, require unbiased and publicly verifiable randomness that can be obtained quickly and cost-effectively whenever needed. Existing services, such as those based on Verifiable Random Functions (VRF), incur network delays and high fees due to their highly interactive nature. FlexiRand [CCS 2023] addressed these problems by hiding the output of the VRF and using that as a seed to derive many randomnesses locally. These randomnesses are instantly available for usage. However, these randomnesses can not be verified independently (or instantly) without disclosing the seed, leaving scope for malicious actors to cheat.
To solve this problem, we introduce a new notion, called instantly-verifiable VRF (iVRF), which enables the generation of many randomnesses from one VRF output seed, such that each of them is verifiable independently - this enables the first solution to cost − effectively generate randomnesses, such that they are instantly available and also independently/instantly verifiable.
To instantiate we propose a generic construction called InstaRand - it combines any (possibly distributed) VRF at the server’s end with another VRF at the client’s end to construct an iVRF. Our specific instantiation uses the BLS-based GLOW-DVRF [Euro S&P 2021] at the server’s end and the DDH-based VRF of Goldberg et al. [RFC 2023] at the client’s end. We use the universal composability framework to analyze the security. Moreover, due to its generality, InstaRand can be instantiated with any post-quantum secure VRF to yield a post-quantum secure iVRF.
Our experiments demonstrate that our instantiation of InstaRand is highly practical. The client incurs a one − time cost to generate the seed (server’s VRF output) by querying the GLOW-dVRF servers once. Once the seed is set up, the client locally generates the pseudorandom value on demand in 0.18 ms, avoiding the client-server round-trip delay. Each value can be independently verified in 0.22 ms. This yields a 400× improvement in terms of output generation and 20× improvement in verification cost over existing solutions.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fwa55bujvdrwlwlwgqmmxmuf/bafkreihjxmem35yktb4ht3zqe4xtplbrpgsgc2jclsmehuxiqiix4sqxte)
Abstract. Web3 applications, such as on-chain gaming, require unbiased and publicly verifiable randomness that can be obtained quickly and cost-effectively whenever needed. Existing services, such as those based on Verifiable Random Functions (VRF), incur network delays and high fees due to their highly interactive nature. FlexiRand [CCS 2023] addressed these problems by hiding the output of the VRF and using that as a seed to derive many randomnesses locally. These randomnesses are instantly available for usage. However, these randomnesses can not be verified independently (or instantly) without disclosing the seed, leaving scope for malicious actors to cheat. To solve this problem, we introduce a new notion, called instantly-verifiable VRF (iVRF), which enables the generation of many randomnesses from one VRF output seed, such that each of them is verifiable independently - this enables the first solution to cost − effectively generate randomnesses, such that they are instantly available and also independently/instantly verifiable. To instantiate we propose a generic construction called InstaRand - it combines any (possibly distributed) VRF at the server’s end with another VRF at the client’s end to construct an iVRF. Our specific instantiation uses the BLS-based GLOW-DVRF [Euro S&P 2021] at the server’s end and the DDH-based VRF of Goldberg et al. [RFC 2023] at the client’s end. We use the universal composability framework to analyze the security. Moreover, due to its generality, InstaRand can be instantiated with any post-quantum secure VRF to yield a post-quantum secure iVRF. Our experiments demonstrate that our instantiation of InstaRand is highly practical. The client incurs a one − time cost to generate the seed (server’s VRF output) by querying the GLOW-dVRF servers once. Once the seed is set up, the client locally generates the pseudorandom value on demand in 0.18 ms, avoiding the client-server round-trip delay. Each value can be independently verified in 0.22 ms. This yields a 400× improvement in terms of output generation and 20× improvement in verification cost over existing solutions.
Image showing part 2 of abstract.
InstaRand: Instantly Available and Instantly Verifiable On-chain Randomness (Jacob Gorman, Lucjan Hanzlik, Aniket Kate, Pratyay Mukherjee, Pratik Sarkar, Sri AravindaKrishnan Thyagarajan) ia.cr/2025/896
![Abstract. The works of Garg et al. [S&P’24] (aka hinTS) and Das et al. [CCS’23] introduced the notion of silent threshold signatures (STS) - where a set of signers silently perform local computation to generate a public verification key. To sign a message, any set of t signers sign the message non-interactively and these are aggregated into a constant-sized signature. This paradigm avoids performing expensive Distributed Key Generation procedure for each set of signers while keeping the public verification key constant-sized.
In this work, we propose the notion of committee-based silent threshold signature (c-STS) scheme. In a c-STS scheme, a set of signers initially perform a one-time setup to generate the verification key, and then a subset of signers are randomly chosen for an epoch to perform the threshold signing while the other signers are not authorized to sign during that epoch. This captures existing systems like Ethereum Altair and Dfinity where only a specific committee is authorized to sign in a designated epoch. The existing STS schemes cannot be extended to the committee setting because the signature verification only attests to the number of signing parties, not which committee they belong to.
So, we upgrade hinTS to the committee setting by proposing Dyna-hinTS. It is the first c-STS scheme and it requires a one-time silent setup and generates a one-time public verification key that does not vary with the committee. Assuming a set of 1024 signers (with corrupt 682 signers), hinTS generates an aggregated signature in 1.7s whereas Dyna-hinTS generates it in 0.35s within a committee of 80 signers. This yields a 4.9× improvement over hinTS for signature generation at the cost of increasing signature verification time by 4% over hinTS. Dyna-hinTS supports general access structure, weighted signatures and improves existing multiverse threshold signatures.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fwa55bujvdrwlwlwgqmmxmuf/bafkreig4bpukjabp26mmfqfl72775bgs7ifio4clfzehb5vtxpwcvoubae)
Abstract. The works of Garg et al. [S&P’24] (aka hinTS) and Das et al. [CCS’23] introduced the notion of silent threshold signatures (STS) - where a set of signers silently perform local computation to generate a public verification key. To sign a message, any set of t signers sign the message non-interactively and these are aggregated into a constant-sized signature. This paradigm avoids performing expensive Distributed Key Generation procedure for each set of signers while keeping the public verification key constant-sized. In this work, we propose the notion of committee-based silent threshold signature (c-STS) scheme. In a c-STS scheme, a set of signers initially perform a one-time setup to generate the verification key, and then a subset of signers are randomly chosen for an epoch to perform the threshold signing while the other signers are not authorized to sign during that epoch. This captures existing systems like Ethereum Altair and Dfinity where only a specific committee is authorized to sign in a designated epoch. The existing STS schemes cannot be extended to the committee setting because the signature verification only attests to the number of signing parties, not which committee they belong to. So, we upgrade hinTS to the committee setting by proposing Dyna-hinTS. It is the first c-STS scheme and it requires a one-time silent setup and generates a one-time public verification key that does not vary with the committee. Assuming a set of 1024 signers (with corrupt 682 signers), hinTS generates an aggregated signature in 1.7s whereas Dyna-hinTS generates it in 0.35s within a committee of 80 signers. This yields a 4.9× improvement over hinTS for signature generation at the cost of increasing signature verification time by 4% over hinTS. Dyna-hinTS supports general access structure, weighted signatures and improves existing multiverse threshold signatures.
Image showing part 2 of abstract.
Dyna-hinTS: Silent Threshold Signatures for Dynamic Committees (Aniket Kate, Pratyay Mukherjee, Samipa Samanta, Pratik Sarkar) ia.cr/2025/631
Happy to announce our paper "VRaaS: Verifiable Randomness as a Service on Blockchains" was accepted into IEEE CSF 2025. Led by @pratikscrypto.bsky.social @aniketkate.bsky.social, and Jacob Gorman from Supra. The paper can be found here eprint.iacr.org/2024/957
Looking forward to attending Real-World Crypto '25 rwc.iacr.org/2025/ next week. I should be there from Tuesday afternoon to Friday evening.
I will present our Tor Directory Authorities (zhtluo.com/paper/Attack...) work on Friday afternoon.
Abstract. In verifiable secret sharing (VSS), a dealer shares a secret input among several parties, ensuring each share is verifiable. Motivated by its applications in the blockchain space, we focus on a VSS where parties holding shares are not allowed to reconstruct the dealer’s secret (even partially) on their own terms, which we address as privacy-targeted collusion if attempted. In this context, our work investigates mechanisms deterring such collusion in VSS among rational and malicious parties. For this problem, we make both algorithmic and combinatorial contributions: 1. We provide two collusion-deterrent mechanisms to discourage parties from colluding and recovering the dealer’s secret. Notably, when it is desired to achieve fairness—where non-colluding parties are not at a loss—while allowing for the best achievable malicious fault tolerance, we define “trackable access structures” (TAS) and design a deterrence mechanism tailored for VSS on these structures. 2. We estimate the size of the optimal TAS, construct them from Steiner systems, provide highly robust TAS using partial Steiner systems, and present efficient secret sharing schemes for the latter close-to-optimal TAS for various parameter regimes. 3. We demonstrate that trackability in access structures is connected to combinatorial objects like (partial) Steiner systems, uniform subsets with restricted intersections, and appropriate binary codes. The robustness of access structures is equivalent to the minimum vertex cover of hypergraphs. We believe these connections between cryptography, game theory, and discrete mathematics will be of broader interest.
Image showing part 2 of abstract.
Disincentivize Collusion in Verifiable Secret Sharing (Tiantian Gong, Aniket Kate, Hemanta K. Maji, Hai H. Nguyen) ia.cr/2025/446
Abstract. Blockchain service offerings have seen a rapid rise in recent times. Many of these services realize a decentralized architecture with a threshold adversary to avoid a single point of failure and to mitigate key escrow issues. While payments to such services are straightforward in systems supporting smart contracts, achieving fairness poses challenges in systems like Bitcoin, adhering to the UTXO model with limited scripting capabilities. This is especially challenging without smart contracts, as we wish to pay only the required threshold of t + 1 out of the n servers offering the service together, without any server claiming the payment twice. In this paper, we introduce VITARIT 1, a novel payment solution tailored for threshold cryptographic services in UTXO systems like Bitcoin. Our approach guarantees robust provable security while facilitating practical deployment. We focus on the t-out-of-n distributed threshold verifiable random function (VRF) service with certain properties, such as threshold BLS signatures, a recently highlighted area of interest. Our protocol enables clients to request verifiable random function (VRF) values from the threshold service, triggering payments to up to t + 1 servers of the distributed threshold VRF. Our efficient design relies on simple transactions using signature verification scripts, making it immediately applicable in Bitcoin-like systems. We also introduce new tools and techniques at both the cryptographic and transaction layers, including a novel signature-VRF exchange protocol for standard constructions, which may be of independent interest. Addition- ally, our transaction flow design prevents malicious servers from claiming payments twice, offering broader implications for decentralized payment systems. Our prototype implementation shows that in the two-party interaction, the client takes 126.4 msec, and the server takes 204 msec, demonstrating practicality and deployability of the system
Image showing part 2 of abstract.
VITARIT: Paying for Threshold Services on Bitcoin and Friends (Lucjan Hanzlik, Aniket Kate, Easwar Vivek Mangipudi, Pratyay Mukherjee, Sri AravindaKrishnan Thyagarajan) ia.cr/2025/174
I am looking forward to attending Real-Wolrd Crypto in Sofia in March'25. #RWC
I will be presenting our work on attacking and improving the Tor directory authority (distributed) system: zhtluo.com/paper/Attack...
The list of accepted talk at @rwc.iacr.org is now available: rwc.iacr.org/2025/accepte... Early registration ends 26 February. CC: programme co-chair @nicksullivan.org
There are now *three* official co-located events for #RealWorldCrypto 2025.
* Real-World MPC (RWMPC)
* The 4th Annual FHE.org conference on Fully Homomorphic Encryption
* The 3rd Annual Real World Post-Quantum Cryptography Workshop (RWPQC 2024)
rwc.iacr.org/2025/colocat...
