International Association
for Cryptologic Research

Securely shuffling a secret-shared list is a vital sub-protocol in numerous applications, including secure sorting, secure list merging, secure graph proessing, oblivious RAM, and anonymous broadcast. We demonstrate how to convert the folklore constant-round protocol for secure shuffling, which employs a delegated Fisher-Yates shuffle using rerandomizable encryption, into a maliciously secure constant-round protocol. This gives the first protocol that has a linear end-to-end time for a two-party secret-shared shuffle with malicious security.

We prove the security of our protocol under the ``linear-only'' assumption on the homomorphic encryption system. We also demonstrate that another assumption, namely weak predicability, is sufficient and that it is both weaker than the linear-only assumption and sufficient for security.

On the road to eliminating censorship from modern blockchain protocols, recent work in consensus has explored protocol design choices that delegate the duty of block assembly away from a single consensus leader and instead to multiple parties, referred to as includers. As opposed to the traditional leader-based approach, which guarantees transaction inclusion in a block produced by the next correct leader, the multiple includer approach allows blockchain protocols to provide a strong censorship-resistance property for users: A timely submitted transaction is guaranteed to be included in the next confirmed block, regardless of the leader's behavior. Such a guarantee, however, comes at the cost of 2 additional rounds of latency to block confirmation, compared to the leader-based approach. Is this cost necessary? We introduce the Censorship Resistant Byzantine Broadcast (CRBB) problem, a one-shot variant that distills the core functionality underlying the multiple-includer design paradigm. We then provide a full characterization, both in synchrony and partial synchrony, of the achievable latency of CRBB in executions with a correct leader, which is the most relevant case to practice. Our main result is an inherent latency cost of two additional rounds compared to the classic Byzantine Broadcast (BB) problem. For example, synchronous protocols for CRBB require 4 rounds whenever BB requires 2 rounds. Similarly, up to a small constant in the resilience, partial synchrony protocols for CRBB require 5 rounds whenever BB requires 3 rounds.

In this paper, we present an MPC protocol in the preprocessing model with essentially the same concrete online communication and rounds as the state-of-the-art MPC protocols such as online-BGW (with precomputed Beaver tuples) for $t < n/3$ malicious corruptions. However, our protocol additionally guarantees robustness and correctness against up to $t < n/2$ malicious corruptions while the privacy threshold remains at $n/3$. This is particularly useful in settings (e.g. commodity/stock market auctions, national elections, IACR elections) where it is paramount that the correct outcome is certified, while maintaining the best possible online speed. In addition, this honest-majority correctness allows us to use optimistic Berlekamp-Welch decoding in contrast to BGW. Moreover, just like online-BGW, our protocol is responsive until a final attestation phase.

We also give a complementary verifiable input-sharing scheme for the multi-client distributed-server setting which satisfies both robustness and correctness against up to $t < n/2$ malicious servers. This is accomplished by having the servers first run a preprocessing phase that does not involve the clients. The novelty of this input-sharing scheme is that a client only interacts for one round, and hence need not be online, which, again, is highly desirable in applications such as elections/auctions.

We prove our results in the universally-composable model with statistical security against static corruptions. Our protocol is achieved by combining global authenticators of SPDZ with an augmented Reed-Solomon code in a novel manner. This augmented code enables honest-majority decoding of degree $n/2$ Reed-Solomon codes. Our particular augmentation (often referred to as robust sharing) has the additional property that the preprocessing phase can generate this augmented sharing with a factor $n$ speedup over prior information-theoretic robust sharing schemes.

In a mercurial signature, a signer signs a representative $m$ of an equivalence class of messages on behalf of a representative $\mathsf{pk}$ of an equivalence class of public keys, receiving the signature $\sigma$. One can then transform $\sigma$ into a signature $\sigma'$ on an equivalent (to $m$) message $m'$ under an equivalent (to $\mathsf{pk}$) public key $\mathsf{pk}'$. Mercurial signatures are helpful in constructing delegatable anonymous credentials: their privacy properties enable straightforward randomization of a credential chain, hiding the identity of each signer while preserving the authenticity of the overall credential. Unfortunately, without trusted setup, known constructions of mercurial signatures satisfy only a weak form of this privacy property. Specifically, an adversary who is responsible for a link in a delegation chain—and thus knows its corresponding secret key—will be able to recognize this link even after the chain has been randomized. To address this issue, Abe et al. (Asiacrypt 2024) proposed (interactive) threshold mercurial signatures (TMS), which remove the reliance on a single trusted signer by distributing the signing capability among multiple parties, none of whom knows the signing key. However, this contribution was far from practical, as it required the signers to interact with each other during the signing process.

In this work, we define and realize non-interactive TMS, where each participant non-interactively computes its contribution to the threshold mercurial signature. Our construction also substantially reduces the overall communication complexity. It uses the mercurial signature scheme of Mir et al. (CCS 2023) as a starting point. Further, we introduce threshold delegatable anonymous credentials (TDAC) and use a non-interactive TMS to construct them.

A sender wishes to consistently broadcast a message on the dark web, so that whoever is around and active will agree on it even when the sender is malicious. No assumptions on the number of honest parties, or blockchain-style ``tricks''---like balanced resource-allocation (e.g., hashing power or stake ownership)---can be made.

The above is an instance of Byzantine broadcast (BB) in the unknown-participants setting (``UP Broadcast'' for short). Despite four decades of extensive research on dishonest-majority BB, all existing approaches (e.g., the well-known Dolev-Strong protocol) fail to solve this problem, as they crucially rely on knowing the number of protocol participants---or the make blockchain-style assumptions on available resources. The challenge, which might appear as an inherent limitation, is that without any such assumption malicious parties can join the protocol at any point during its execution, making it arduous for other parties to terminate without violating consistency. So one might wonder: Is this even possible?

In this work, we provide the first definitions of UP Broadcast that incorporate both static and dynamic participation and corruption of arbitrary many parties. Interestingly, even formally defining the problem turns out to be non-trivial as one needs to deviate from the model used in classical BB approaches. We then provide the strongest possible (and in our opinion, unexpected) answer to the above question: Yes, it is! We provide a polynomial-time deterministic UP Broadcast protocol. In the process we also solve UP Interactive Consistency, which corresponds to the multi-sender version of the problem. Our constructions are in the standard, synchronous model of protocol execution, and they offer consistency and validity guarantees to every party who is present throughout the protocol execution.

We next turn to the question of round complexity and prove that our protocols are optimal against adversaries who can corrupt arbitrarily many parties; this optimality applies even to randomized protocols. Finally, we ask, what if parties join in the middle of the protocol execution? We provide a negative result for unrestricted dynamic participation; on the positive side, we devise definitions that offer best-possible guarantees (also to such ``late'' parties), and present corresponding constructions that remain round-optimal.

Recent attacks on private set intersection (PSI) and PSI-like protocols have demonstrated that input privacy can be compromised when parties maliciously choose their inputs, even in protocols proven secure against malicious adversaries. To counter such attacks, Authorized PSI (APSI) introduces a judge who authorizes the elements of the parties before the intersection is computed. Falzon and Markatou (PETS 2025) proposed Partial-APSI, a privacy-preserving variant of APSI that prevents revealing the entire set to a judge. Their Partial-APSI protocol requires significant bandwidth overhead due to the use of bilinear pairings and because the judge must sign each element in the input set. In this work, we present a bandwidth-efficient Partial-APSI protocol that outperforms Falzon and Markatou, both asymptotically and empirically. For example, for sets of size $2^{20}$, we require around $21\times$ less bandwidth and are about $6\times$ faster over a LAN network. In addition to our protocol, we model the real-world behavior of rational parties through a game-theoretic analysis. We introduce payout mechanisms for detected cheating and establish lower bounds on their values, ensuring that the best strategy for rational parties is to provide honest input.

Private BitTorrent trackers enforce upload-to-download ratios to prevent free-riding, but suffer from three critical weaknesses: reputation cannot move between trackers, centralized servers create single points of failure, and upload statistics are self-reported and unverifiable. When a tracker shuts down (whether by operator choice, technical failure, or legal action) users lose their contribution history and cannot prove their standing to new communities. We address these problems by storing reputation in smart contracts and replacing self-reports with cryptographic attestations. Receiving peers sign receipts for transferred pieces, which the tracker aggregates and verifies before updating on-chain reputation. Trackers run in Trusted Execution Environments (TEEs) to guarantee correct aggregation and prevent manipulation of state. If a tracker is unavailable, peers use an authenticated Distributed Hash Table (DHT) for discovery: the on-chain reputation acts as a Public Key Infrastructure (PKI), so peers can verify each other and maintain access control without the tracker. This design persists reputation across tracker failures and makes it portable to new instances through single-hop migration in factory-deployed contracts. We formalize the security requirements, prove correctness under standard cryptographic assumptions, and evaluate a prototype on Intel TDX. Measurements show that transfer receipts adds less than 6\% overhead with typical piece sizes, and signature aggregation speeds up verification by $2.5\times$.