AtheCrypt 2025

Abstract: Differential privacy (DP) is a key tool in privacy-preserving data analysis. Yet it remains challenging for non-privacy-experts to prove the DP of their algorithms. We propose a methodology for domain experts with limited data privacy background to empirically estimate the privacy of an arbitrary mechanism. Our Eureka moment is a new link— which we prove—between the problems of DP parameter-estimation and Bayes optimal classifiers in ML, which we believe can be of independent interest. Our estimator uses this link to achieve two desirable properties: (1) black-box, i.e., it does not require knowledge of the underlying mechanism, and (2) it has a theoretically-proven accuracy, depending on the underlying classifier used, allowing plug-and-play use of different classifiers.More concretely, motivated by the impossibility of the above task for unrestricted input domains (which we prove), we introduce a natural, application-inspired relaxation of DP which we term relative DP. Intuitively, relative DP defines a mechanism's privacy relative to an input set T, circumventing the above impossibility when T is finite. Importantly, it preserves the key intuitive privacy guarantee of DP while enjoying a number of desirable DP properties—scalability, composition, and robustness to post-processing. We then devise a black-box poly-time (ε, δ)-relative DP estimator for any poly-size T—the first privacy estimator to support mechanisms with large output spaces while having tight accuracy bounds. As a result of independent interest, we generalize our theory to develop the first Distributional Differential Privacy (DDP) estimator.We benchmark our estimator in a proof-of-concept implementation. First, using kNN as the classifier we show that our method (1) produces a tight, analytically computed (ε,δ)-DP trade-off of low-dimensional Laplace and Gaussian mechanisms—the first to do so, (2) accurately estimates the privacy spectrum of DDP mechanisms, and (3) can verify a DP mechanism's implementations, e.g., Sparse Vector Technique, Noisy Histogram, and Noisy max. Our implementation and experiments demonstrate the potential of our framework, and highlight its computational bottlenecks in estimating DP, e.g., in terms of the size of δ and the data dimensionality. Our second, neural-network-based instantiation makes a first step in showing that our method can be extended to mechanisms with high-dimensional outputs.
Joint work with Yun Lu, Malik Magdon-Ismail, Yu Wei

Abstract: This talk introduces Mysticeti a byzantine consensus protocol with low-latency and high resource efficiency. It leverages a DAG based on Threshold Clocks and incorporates innovations in pipelining and multiple leaders to reduce latency in the steady state and under crash failures. Mysticeti is the first byzantine protocol to achieve WAN latency of 0.5s for consensus commit, at a throughput of over 100k TPS that matches the state-of-the-art.
Link: https://sonnino.com/papers/mysticeti.pdf

Abstract:In the era of Web3, decentralized technologies have emerged as the cornerstone of a new digital paradigm. Backed by a decentralized blockchain architecture, the Web3 space aims to democratize all aspects of the web. From data-sharing to learning models, outsourcing computation is an established, prevalent practice. Verifiable computation makes this practice trustworthy as clients/users can now efficiently validate the integrity of a computation. As verifiable computation gets considered for applications in the Web3 space, decentralization is crucial for system reliability, ensuring that no single entity can suppress clients. At the same time, however, decentralization needs to be balanced with efficiency: clients want their computations done as quickly as possible.
Motivated by these issues, we study the trade-off between decentralization and efficiency when outsourcing computational tasks to strategic, rational solution providers. Specifically, we examine this trade-off when the client employs (1) revelation mechanisms, i.e. auctions, where solution providers bid their desired reward for completing the task by a specific deadline and then the client selects which of them will do the task and how much they will be rewarded, and (2) simple, non-revelation mechanisms, where the client commits to the set of rules she will use to map solutions at specific times to rewards and then solution providers decide whether they want to do the task or not. We completely characterize the power and limitations of revelation and non-revelation mechanisms in our model.

Abstract: We present a novel protocol for two-party ECDSA that achieves two rounds (a single back-and-forth communication) at the cost of a single oblivious linear function evaluation (OLE). In comparison, the previous work of Boneh et al.~(EUROCRYPT 2025) achieves two rounds but requires expensive zero-knowledge proofs on top of the OLE. We demonstrate this by proving that in the generic group model, any adversary capable of generating forgeries for our protocol can be transformed into an adversary that finds preimages for the ECDSA message digest function (e.g., the SHA family). Interestingly, our analysis is closely related to, and has ramifications for, the `presignatures' mode of operation—Canetti et al.~(CCS 2020), Groth and Shoup (EUROCRYPT 2022).
Motivated by applications to embedded cryptocurrency wallets, where a single server maintains distinct, shared public keys with separate clients (i.e., a star-shaped topology), and with the goal of minimizing communication, we instantiate our protocol using Paillier encryption and suitable zero-knowledge proofs. To reduce computational overhead, we thoroughly optimize all components of our protocol under sound cryptographic assumptions, specifically small-exponent variants of RSA-style assumptions. Finally, we implement our protocol and provide benchmarks. At the 128-bit security level, the signing phase requires approximately 50ms of computation time on a standard linux machine, and 2KB of bandwidth.

Abstract: Anonymous tokens are a form of lightweight privacy‑preserving cryptographic credentials that let a user obtain a signed token from an authority and later redeem it, without anyone being able to link the two events. In this talk I will present two extensions of anonymous tokens. First, I will discuss our CCS 2024 work on blind multi-signatures for anonymous tokens, which enables decentralized issuance: any subset of issuers can jointly sign a compact token that remains unlinkable even if they all collude, drastically reducing trust in any single signer. Then, I will discuss our very recent work that allows for non-interactive issuance of anonymous tokens (with private metada bit). The non-interactiveness of the issuance process allows for preprocessing and can significantly increase the efficiency of the issuing process.

Abstract: Blockchains enable decentralised applications that withstand Byzantine failures and do not need a central authority. Sadly, their massive replication requirements preclude their use on constrained devices.
We propose a novel blockchain-based protocol which forgoes replication without affecting the append-only nature of blockchains. This is suitable for maintaining data integrity over networks of storage-constrained devices. Our solution provides something more specific than a general blockchain: a feed storage, i.e., a mechanism that stores the communications of multiple parties, with each party's contributions stored and ordered separately. Our design avoids consensus and its overheads. Our motivating application is securely storing sensor data of containers in cargo ships.
We elucidate the practical promise of NodeChain in several ways: We (i) formally prove the security of our protocol in the \emph{Universal Composition} (UC) setting, as well as (ii) provide a small-scale proof-of-concept implementation, (iii) a performance simulation of large-scale deployments that showcases a reduction in storage of more than $1000\times$ compared to traditional blockchains, and (iv) a resilience simulation that predicts the effects of network jamming attacks.

Abstract: Decentralized storage systems face a fundamental trade-off between replication overhead, recovery efficiency, and security guarantees. Current approaches either rely on full replication, incurring substantial storage costs, or employ trivial erasure coding schemes that struggle with efficient recovery, especially under high storage-node churn. We present Walrus, a novel decentralized blob storage system that addresses these limitations through multiple technical innovations.
At the core of Walrus is Red Stuff, a two-dimensional erasure coding protocol that achieves high security with only a 4.5x replication factor while enabling self-healing recovery that requires bandwidth proportional to only the lost data (𝑂 (|𝑏𝑙𝑜𝑏|/𝑛) versus 𝑂 (|𝑏𝑙𝑜𝑏|) in traditional systems). Crucially, Red Stuff is the first protocol to support storage challenges in asynchronous networks, preventing adversaries from exploiting network delays to pass verification without actually storing data.
Walrus also introduces a novel multi-stage epoch change protocol that efficiently handles storage node churn while maintaining uninterrupted availability during committee transitions. Our system incorporates authenticated data structures to defend against malicious clients and ensures data consistency throughout storage and retrieval processes.

Abstract: Blockchain light clients (LCs) are agents with limited computational or storage resources who cannot maintain a fully validated local copy of the ledger state. Instead, they rely on service providers (SPs), typically full nodes, to access data required for tasks such as constructing transactions or interacting with off-chain applications.
In this work, we introduce Cavefish, a novel protocol for UTxO-based platforms that enables LCs to interact with the ledger and submit transactions with minimal trust, storage, and computation. Cavefish defines a two-party computation protocol between an LC and an SP, in which the LC specifies a transaction and the SP constructs it. Consequently, the LC only receives a blinded version of the transaction, preventing it from modifying or reusing the transaction while still being able to verify that the transaction matches the original intent of the LC. The SP is compensated inside the constructed transaction, eliminating the need for another protocol or exchange.
To support this, we propose a variant of the predicate blind signature (PBS) scheme of Fuchsbauer and Wolf (Eurocrypt 2024), allowing the SP to obtain a valid signature on the unblinded transaction, which it can then broadcast on the network and post on chain. Moreover, the resulting signatures verify as standard Schnorr signatures. Our construction achieves a trustless interaction in which the LC achieves their transaction goal, and the SP receives fair compensation for their effort. When Cavefish is combined with hierarchical deterministic (HD) wallets, the LC can provide a single public key and chain code to the SP, reducing communication footprint to a minimum.
To further optimize communication and computational overhead, our PBS variant relaxes the unlinkability guarantees of traditional blind signatures in favor of efficiency. We argue that this relaxation is adequate, since transactions only need to be kept private until posted on a public ledger. We implement and benchmark the Non-interactive Argument of Knowledge (NArg) component of our protocol on two major UTxO-based blockchains. Despite being the most computationally demanding part, our results show that proving and verification times, as well as circuit sizes, are practical for real-world deployment.