PoW Micronomics: A Fine-Grained Model for the Economic Analysis of Proof-of-Work Blockchains (2026/1241)

Authors

Juan Garay, Texas A&M University
Yun Lu, University of Vicgoria
Julien Prat, École Polytechnique
Brady Testa, Texas A&M University
Vassilis Zikas, Georgia Tech

Abstract
Following the cryptographic security analyses of proof-of-work (PoW) blockchain protocols, a line of research has focused on their economic robustness. The two core questions asked are: How resilient is the system to rational attacks, and how profitable it is for miners to execute it. However, to our knowledge, no work to date has attempted to address them considering the full complexity of the blockchain protocol, including difficulty readjustment, which is needed to handle dynamic participation, price fluctuations, and the impact of risk. In this work, we provide a fine-grained game-theoretic analysis for Nakamoto-style PoW blockchains, which takes into account both incentives of parties to deviate and complications introduced by difficulty readjustment. Our results employ the Rational Protocol Design framework of Garay et al. [FOCS’13] and extend recent works on the economic robustness of the Bitcoin backbone protocol to the variable difficulty setting. Notably, our fine-grained specification of miners’ utility incorporates variable difficulty adjustment alongside factors like the average cost of mining and the depreciation factor, which, despite being common in economics, are typically either abstracted as exogenous parameters or ignored in the blockchain literature. We showcase the expressivity and usefulness of our formulation of utilities by using it to provide estimates and trends for such factors across several real-world cryptocurrencies.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Adaptive attacks on FESTA variants with masked-degree isogenies (2026/1240)

Authors

Tomoki Moriya, Mitsubishi Electric (Japan)

Abstract
FESTA is an isogeny-based trapdoor function proposed as a high-performance alternative in isogeny-based cryptography. Its core design principles have inspired a number of related constructions, collectively referred to as FESTA variants. The MOXZ attack is an adaptive attack that exploits malicious ciphertexts together with access to a checking oracle, aiming to compromise FESTA and its variants. This attack applies to FESTA variants whose secret keys are derived from isogenies of known degree; however, it does not extend to variants employing masked-degree isogenies. In this work, we present a novel adaptive attack that generalizes the MOXZ attack. Our attack successfully targets several FESTA variants even when their secret keys are isogenies of masked degree. We also identify POKE-4D as an exception for which our attack does not appear to be applicable.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Balanced Additive Randomized Encodings for Shuffle Differential Privacy (2026/1239)

Authors

Yu Wei, Georgia Institute of Technology
Jaspal Singh, Purdue University West Lafayette , Georgia Institute of Technology
Adya Agrawal, Georgia Institute of Technology
Vassilis Zikas, Georgia Institute of Technology

Abstract
Shuffle differential privacy (shuffle DP) offers an attractive distributed alternative to standard differential privacy. It uses a secure shuffler to permute users' randomized encodings, providing individual data privacy without a central trusted entity. A key challenge, however, is to achieve both generality and client efficiency. Under information-theoretic shuffle-DP guarantees, protocols that nearly match central-model utility are restricted to statistical tasks such as summation and histograms. In contrast, in the computational setting, additive randomized encodings (ARE), introduced by Halevi et al. (CRYPTO 2023), yield a generic compiler that achieves central-model utility for arbitrary mechanisms. However, their construction incurs prohibitive worst-case computation and communication costs for clients, making it impractical for resource-constrained devices such as mobile phones, IoT sensors, and web browsers. In this work, we present a client-efficient one-round compiler from central DP to non-robust computational shuffle DP. To achieve this, we first construct a new balanced ARE scheme, where all the clients almost equally share the computational burden in the protocol. For a mechanism $M$ over $n$ clients, this reduces the worst-case per-client computation from $O(|M|)$ in prior work to $O(|M|/n)$, where $|M|$ denotes the circuit complexity of the mechanism. The key technical ingredient is a new permute-XOR ARE primitive that enables wire splicing across independently generated garbled subcircuits. Secondly we design a more efficient ARE-to-shuffle compiler, whose client bandwidth scales with the sparsity and cross-partition structure parameter of the ARE encoding - a quantity that is always sublinear in $n$. This is an improvement over Halevi et al. (CRYPTO 2023) where each client bandwidth is $\Omega(n)$. At a high level, the first contribution improves client computation while the second improves client bandwidth. We provide an implementation of our generic compiler for differentially private tasks including selection, distinct elements, and linear contextual bandits. We obtain shuffle protocols that match the utility of their central-model counterparts with reasonable client overhead. We evaluate our method across a range of practical settings, and observe substantial gains over the compiler of Halevi et al., with per-client computational and bandwidth speedups increasing linearly in the number of clients.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

On the Additive Sensitivity of LZ77 Under Consecutive Edits (2026/1238)

Authors

Jeremiah Blocki, Purdue University West Lafayette
Seunghoon Lee, University of Waterloo

Abstract
We revisit the problem of mitigating information leakage in the widely used but insecure compress-then-encrypt paradigm. While encryption hides message contents, the ciphertext length is directly related to the length of the compressed message, which may, in turn, leak information about the {\em content} of the message itself. Recent work of Blocki et al. (TCC 2025) proposed an $(\varepsilon,\delta)$-differentially private approach that adds randomized padding calibrated to the global sensitivity of the compression algorithm, and showed that the global sensitivity of LZ77 is $O(W^{2/3}\log n)$, where $n$ is the input length and $W$ is the sliding window size. However, prior analysis focused only on sensitivity with respect to single-character edits, which leads to limited privacy guarantees when protecting longer substrings such as passwords, passphrases, cookies, or confidential user records. A natural attempt to handle longer secrets is to appeal to group privacy, but for approximate differential privacy, this leads to very poor parameter degradation: in particular, the effective value of $\delta$ can grow exponentially with the group size $g$. In this work, we introduce and study the sensitivity of compression schemes under block edits. Specifically, we define two strings to be $g$-neighbors if they differ only within a contiguous interval of length $g$. Our main technical contribution is a nearly tight characterization of the $g$-consecutive sensitivity of LZ77. We show that the $g$-consecutive sensitivity of both LZ77 variants (with and without self-referencing) is at most $O((W^{2/3}+g+\sqrt{Wg})\log n)$. In particular, when $g \leq W^{1/3}$, the bound simplifies to $O(W^{2/3}\log n)$, matching the known bound for single-character edits. Thus, calibrating noise to the single-character sensitivity of LZ77 already suffices to protect much longer contiguous substrings. We provide matching lower bounds to demonstrate that our upper bound is tight, e.g., when $n=W=O(g^2)$, the $g$-consecutive sensitivity of LZ77 is at least $\tilde{\Omega}(g^{1.5})$, matching the $\sqrt{Wg}=O(g^{1.5})$ term from our upper bound up to a logarithmic factor.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

SING: Improving the Efficiency of MPC Protocol Assignment using Graph Neural Networks (2026/1237)

Authors

Jannis Blüml, Technical University of Darmstadt
Moritz Huppert, Technical University of Darmstadt
Nora Khayata, Technical University of Darmstadt
Joachim Schmidt, Technical University of Darmstadt
Thomas Schneider, Technical University of Darmstadt

Abstract
Secure Multi-Party Computation (MPC) enables private computation, but has significantly higher overhead than plaintext execution. Hybrid MPC compilers improve concrete efficiency by mapping distinct computation parts to contextually optimal MPC protocols. However, state-of-the-art systems like Silph (Chen et al., S&P’23) depend on deployment-specific cost models that are cumbersome to retune, and compute mappings via brittle heuristics or costly Integer Linear Programming (ILP), limiting scalability and portability across protocols and deployment settings. We present SING, the first machine-learning-based framework for hybrid MPC share assignment. SING leverages Graph Neural Networks (GNNs) for: (1) imitation of Silph’s assignments, accelerating share assignment by up to $76,697\times$ with comparable quality; and (2) cost-driven learning, where we train a GNN cost predictor on synthetic or empirical costs (e.g., runtime or communication), freeze it, and train the share-assigning GNN to minimize predicted costs. The latter supports expressive non-linear cost models, avoiding ILP's linearity constraints, and enables retargeting to new protocol suites and deployment settings by re-fitting the predictor. Finally, we release our synthetic benchmark resources, including a dataset of 704 MPC circuits with wide-ranging hybrid assignments.
(show hidden)

Publication status: Published elsewhere. Minor revision. USENIX Security Symposium 2026 First uploaded: , last revision:

New bounds on private simultaneous quantum message passing (2026/1236)

Authors

Uma Girish, Columbia University
Alex May, Perimeter Institute for Theoretical Physics , Institute for Quantum Computing, University of Waterloo
Natalie Parham, Columbia University
Henry Yuen, Columbia University

Abstract
In the private simultaneous message (PSM) setting, $k$ players obtain inputs $x_i\in\{0,1\}^n$ and then independently send messages to a referee, who should learn $f(x_1,...,x_k)$ but no other information about $(x_1,...,x_k)$. The PSM setting was introduced as a minimal model for secure multiparty computation. In the quantum setting, PSM has been related to non-local quantum computation (NLQC), and has several connections to the complexity of Boolean functions. The communication and correlation cost of implementing private simultaneous message passing may be much larger than the cost without privacy, and the cost of privacy in this setting remains poorly understood. Here, we give new upper and lower bounds on the PSM model, in both the quantum and classical settings. Concretely, we prove two lower bounds: 1) Nečiporuk's measure lower bounds the entanglement required for $k$-player quantum PSM with perfect correctness. This can be evaluated to give quadratic lower bounds for some explicit functions. 2) The rank of the communication matrix of $f(x_1,x_2)$ lower bounds 2-player quantum PSM with perfect privacy but imperfect correctness. This implies a previously unknown lower bound on classical PSM with imperfect correctness. When allowing both quantum communication and shared entanglement, these two bounds are the first lower bounds on quantum PSM that make use of the privacy condition. Regarding upper bounds, we show: 1) Letting $s$ be the size of a quantum circuit computing $f$, $d_f$ be the circuit depth, $k$ the number of players, $n$ the number of bits received by each player, and $\epsilon$ the correctness parameter of the PSM protocol, we obtain the upper bound $\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O( d_f)}(s/\epsilon)$. 2) The square of the Fourier 1 norm of $f$, $\Vert \hat{f}\Vert_1^2$, upper bounds the classical PSM complexity, $\mathsf{PSM}(f)\leq O(\Vert \hat{f} \Vert^2_1)$. In proving the first upper bound, we also generalize existing $T$-depth based techniques for NLQC from $2$ to $k\geq 2$ parties, and consider cases where the Clifford layers are restricted to having small light cones. These generalizations may be of independent interest.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Authenticated Data Structures for Dynamic Workloads (2026/1235)

Authors

Ziheng (Tom) Shangguan, University of California, Santa Barbara
Aviv Yaish, Yale University , IC3 , Complexity Science Hub, Vienna
Dahlia Malkhi, University of California, Santa Barbara

Abstract
We introduce the Huffman-Merkle Tree (HMT), an authenticated data structure (ADS) optimized for dynamic workloads where some items may be more frequently accessed than others, and access frequencies change over time. An ADS allows proving item membership against a short commitment to a large mutable state, with applications including verifiable storage, Internet transparency services, and blockchains. Optimizing ADS performance under continuously changing access frequencies has not been fully addressed before, neither in theory nor in practice. HMT tackles access skew via tiering: "hot" items are stored according to a Huffman coding layout where frequently accessed items are closer to the root and thus contribute less to overall costs, while a binary Merkle Tree (MT) is used for cold and new elements to lower their update overhead. To efficiently handle dynamic workloads, we incrementally apply and batch layout changes, track access frequencies via count-min sketch, use a tier promotion cache, and consider various tier migration policies. We implement HMT and compare it on real-world data against Ethereum's Merkle Patricia Trie (MPT) ADS and its proposed replacement, the Unified Binary Tree (UBT). Our evaluation considers two metrics: the amount of hashing per ADS update and access-weighted membership-proof size. The latter metric captures both the cost of accessing each item and its access frequency. We find that the best HMT policy uses about 2.4x and 0.34x less average hash operations than MPT and UBT respectively, while featuring proofs shorter by 0.18x than MPT and 0.55x than UBT.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Designing Incentives for Responsive Consensus Protocols (2026/1234)

Authors

Mahimna Kelkar, Columbia University
Ertem Nusret Tas, a16z Crypto Research
Maryam Bahrani, Ritual
Tim Roughgarden, Columbia University

Abstract
Modern consensus protocols often aspire to be responsive---that is, to confirm transactions in time proportional to the actual network delays as opposed to a (typically much larger) worst-case bound on network delays. Responsiveness can yield substantial practical improvements in both protocol latency and throughput. In blockchain settings, however, block proposers commonly have economic incentives (most notably MEV) to delay their blocks, a phenomenon repeatedly observed in practice, e.g., in the block production supply chains for Ethereum and Solana. Such incentives clash with responsiveness in existing protocol designs. This paper develops a rigorous framework for designing incentive-compatible responsive consensus protocols. We first consider the canonical case of single-leader protocols and establish feasibility results characterizing the conditions on the distribution of network latency under which responsiveness can be incentivized through a suitable reward function. We further quantify the amount of stake required from the leader to deter dishonest delays. We then show strong positive results for protocols with multiple leaders, demonstrating that the multi-leader approach is fundamentally superior to single-leader designs for resolving the tension between responsiveness and incentive-compatibility: by forcing leaders to compete for rewards, much of the burden otherwise placed on the incentive mechanism is alleviated. Notably, this results in simpler reward mechanisms with no stake requirements that also remain feasible in parameter regimes which are provably impossible under a single leader.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Implementation of Learning with Errors in Non-Commuting Multiplicative Groups (2026/1233)

Authors

Aleksejus Mihalkovich, Kaunas University of Technology
Lina Dindiene, Kaunas University of Technology
Eligijus Sakalauskas, Kaunas University of Technology

Abstract
In this paper, we demonstrate a way to generalize learning with errors (LWE) to the family of so-called modular-maximal cyclic groups which are non-commuting. Since the group $\mathbb{M}_{2^t}$ has two cycles of maximal multiplicative order, we use this fact to construct an accurate criterion for restoring the message bit with overwhelming probability. Furthermore, we implement the original idea by O. Regev in the considered group to gain benefits from the non-commutativity of $\mathbb{M}_{2^t}$. Also we prove that using this approach we can achieve a level of security comparable to the original idea.
(show hidden)

Publication status: Published elsewhere. Minor revision. https://arxiv.org/pdf/2509.11237 First uploaded: , last revision:

A Heuristic Subexponential Attack on the McEliece Cryptosystem (2026/1232)

Authors

Pierre Briaud, XLIM , Centre National de la Recherche Scientifique
Axel Lemoine, French Institute for Research in Computer Science and Automation , Direction Générale de l'Armement
Hugues Randriambololona, ANSSI , Télécom ParisTech
Jean-Pierre Tillich, French Institute for Research in Computer Science and Automation

Abstract
We provide a new way of performing an algebraic attack on the McEliece cryptosystem based on binary Goppa codes. It also applies in general to the case where the field over which the Goppa code is defined is of even characteristic. It is based on a new algebraic modeling for finding as in [CMT23,M25,BLT26] matrices of rank $2$ in the code of quadratic relations related to the Goppa code that is attacked. Such matrices are then used to recover the secret algebraic structure of the code. This breaks the scheme. A byproduct of our approach is a new distinguisher for Goppa codes in even characteristic which is as the syzygy distinguisher of [R25] subexponential in the security parameter of the scheme. We demonstrate the effectiveness of our attack on McEliece TII challenges, some of which having been studied in [BLT26], and aimed at having $83$,$89$,$119$,$166$, $210$ and even $248$ bit security respectively and CFS keys with parameters $r=9$ and $m=16$, corresponding to a security of $74.9$ bits according to [LS12]. This CFS key was not attacked in practice in [BLT26] and took us 14 hours of computation and 24GB of RAM. We make the conjecture that this attack has a complexity which is of the same nature as the distinguisher, namely subexponential in the security parameter.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

The Best of Both Worlds: Hybrid Authenticated Key Exchange for QKD(N) without Signatures (2026/1231)

Authors

Sebastian Clermont, TU Darmstadt
Johanna Henrich, Darmstadt University of Applied Sciences

Abstract
Post-Quantum Cryptography (PQC) and Quantum Key Distribution (QKD) are both contenders for securing communication against quantum adversaries, but are at different stages of maturity. For hedging security risks, hybridization is the default approach. Unlike previous research on classical–post-quantum hybrids, we propose a QKD-PQC hybrid for Authenticated Key Exchange (AKE). To minimize the attack surface, we completely remove the requirement for digital signature schemes and propose a Hybrid Authenticated Key Exchange (HAKE) that combines Post-Quantum (PQ) AKE and QKD key agreement, leveraging Key Encapsulation Mechanisms (KEMs) for both key exchange and authentication. Our fully modular security analysis, based on the recent multi-input Key Derivation Function (KDF) framework by Backendal et al. (Eurocrypt 2025), establishes AKE security in the CK01 model and yields a conditional information-theoretic security guarantee when the QKD component is uncompromised; a property not achieved by prior hybrid protocols. We demonstrate the protocol’s practical feasibility with benchmarks using ML-KEM, FrodoKEM, and Classic McEliece.
(show hidden)

Publication status: Published elsewhere. Minor revision. Africacrypt 2026 First uploaded: , last revision:

Formula Freshness for Staged Hybrid Authenticated Key Exchange (2026/1230)

Authors

Anis Bkakria, IRT SystemX
Merland Chrislain Chadrel BAFOUETILA

Abstract
Hybrid post-quantum migration is entering deployed handshake designs, but hybrid KEM security protects only one shared-secret input. It does not by itself say whether handshake, application, exporter, or resumption material remains pseudorandom after branch reveals, stage-key reveals, selective corruptions, or late corruptions. We characterize these staged claims through branch-formula freshness: each stage receives a monotone formula over branch exposure, authentication freshness, transcript binding, KDF ancestry, and explicit non-reveal atoms. Secrecy follows by replacing a surviving branch contribution and then using a labelled HKDF/PRF-style target-hiding argument along a fresh KDF cut; agreement follows separately from authentication binding and injective transcript representation. We also give selector-local accounting, where a fixed admissible witness selector determines which surviving branches and KDF cuts are charged. For scoped TLS 1.3 ECDHE--ML-KEM 1-RTT, we identify the branch-replacement, HKDF-path, and binding assumptions that imply concrete preservation bounds for handshake, application, exporter, and resumption targets.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Invisible Traces: Subversion Attacks on Batch-Issued Credentials (2026/1229)

Authors

Anna-Birgitta Burmeister, Hasso Plattner Institute , University of Potsdam
Anna Fennig, Hasso Plattner Institute , University of Potsdam
Andreas Franke, Hasso Plattner Institute , University of Potsdam
Karla Friedrichs, Hasso Plattner Institute , University of Potsdam
Anja Lehmann, Hasso Plattner Institute , University of Potsdam
Kurt-Kester Leißering, Hasso Plattner Institute , University of Potsdam
Konrad Letz, Hasso Plattner Institute , University of Potsdam
Cavit Özbay, Hasso Plattner Institute , University of Potsdam

Abstract
All EU member states are required to roll out a digital identity system - the European Digital Identity (EUDI) wallet - by the end of 2026. Strong privacy is at the core of the underlying regulation, which mandates the EUDI wallet to support selective disclosure and unlinkability. The wallet currently being developed relies on the batch issuance of one-time ECDSA credentials that sign attributes through individually salted hashes for selective disclosure. This solution is known to achieve only a weak form of unlinkability, where the credential issuer must be honest: a malicious issuer could trace users through the salted hashes it signs and the signature value itself. But such a tracing attack requires the issuer to store all signed data and communicate with the verifying parties for tracing, which can be argued to be too cumbersome or obvious to happen in reality. In this work, we therefore initiate the study of a more subtle type of subversion attacks. Therein, the issuer can deviate from the issuance protocol, with two goals: (i) enabling verifiers in possession of a short tracing key to de-anonymize users and (ii) keeping this deviation undetectable from users. We formalize unlinkability against such subversion attacks, and show that batch-issued credentials with salted hashes do not achieve that form of privacy. We present several undetectable subversion attacks against batch-issued ECDSA credentials and suggest lightweight mechanisms to provably mediate them.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Advancing Pseudorandom Codes: Beyond Parity Checks and Standard-Model CCA1 Security (2026/1228)

Authors

Yu Chen, School of Cyber Science and Technology, Shandong University, Qingdao 266237, China
Xinyu Mao, Thomas Lord Department of Computer Science, University of Southern California
Hongxu Yi, School of Cyber Science and Technology, Shandong University, Qingdao 266237, China

Abstract
Pseudorandom codes (PRCs) are error-correcting codes whose codewords are computationally indistinguishable from uniform random strings, a primitive motivated by the need to robustly watermark generative AI models. While recent breakthroughs have established the feasibility of PRCs, critical challenges remain regarding the diversity of their underlying cryptographic assumptions and their security against active adversaries. This work advances the study of PRCs on two complementary fronts: structural diversity and advanced security. On the structural side, we propose a novel PRC template that departs from the prior one based on sparse parity-check trapdoors. We introduce a new LPN-type assumption, formalized as Dense-Planted LPN, which postulates $(\mathbf{M}\mathbf{T}, \ \mathbf{M}\mathbf{T}\mathbf{s}+\mathbf{e})\ \approx_c\ (\mathbf{M}\mathbf{T}, \ \mathbf{u})$, where $\mathbf{T}$ is a random dense matrix and $\mathbf{M}$ is sampled from a distribution containing a planted structure. This hidden structure enables a completely new decoding mechanism based on a local-window search rather than global parity checks. Notably, this template provides a viable path toward constructing PRCs from assumptions beyond code-based ones, including Learning with Errors (LWE) assumptions. On the security side, we construct the first public-key PRC secure against pre-challenge chosen-codeword attacks (CCA1) in the standard model. In realistic watermarking deployments where detectors are exposed as public services, CCA security is essential. However, prior CCA-secure PRCs were only achievable in the random oracle model. By formally introducing and instantiating a robust tag-based equivocal bit commitment scheme combined with robust hinting PRGs, we demonstrate that CCA1 security can be achieved in the standard model without sacrificing decoding robustness.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Chosen Ciphertext Secure Pseudorandom Codes in the Standard Model (2026/1227)

Authors

Nico Döttling, CISPA Helmholtz Center for Information Security
Antoine Joux, CISPA Helmholtz Center for Information Security
Venkata Koppula, Indian Institute of Technology Delhi
Mahesh Sreekumar Rajasree, CISPA Helmholtz Center for Information Security
Hendrik Waldner, CISPA Helmholtz Center for Information Security

Abstract
Pseudorandom codes (PRCs), recently proposed by Christ and Gunn (CRYPTO'24), are encryption schemes that have pseudorandom ciphertexts and a decryption algorithm which is resilient against a bounded number of Hamming errors. This notion provides a significant strengthening over standard PKE and has exciting applications in, e.g., watermarking LLMs. The recent work of Alrabiah et al. (STOC'25) initiated the study of CCA-secure public-key PRCs, where the adversary is additionally given access to a decoding oracle. In terms of realizations, they provide one that can be proven secure in the random oracle model. Constructing CCA-secure public-key PRCs in the standard model remained an open problem. In this work, we resolve this problem and provide the first construction of CCA-secure public-key PRCs in the standard model. Our construction achieves a constant rate and can decode from a constant fraction of adversarial errors. In fact, our construction is a general blueprint that can be instantiated from a broad range of standard cryptographic assumptions. As an additional contribution, we construct a strong adaptively robust public-key pseudorandom code with conjectured sub-exponential security based on a new family of assumptions we call Noisy McEliece. In a nutshell, these assumptions mask a scrambled generator matrix from an efficiently decodable inner-code family with sparse Bernoulli noise; this additional error is meant to obscure the algebraic structure targeted by known attacks and thereby permits candidate instantiations from broader classes of codes.
(show hidden)

Publication status: A major revision of an IACR publication in CRYPTO 2026 First uploaded: , last revision:

Changing of the Guards with Two Shares - Security Flaws, Corrrections, and Application to Low-Latency AES (2026/1226)

Authors

Feng Zhou, University of Chinese Academy of Sciences , TCA Laboratory, Institute of Software, Chinese Academy of Sciences , Zhongguancun Laboratory
Gehui Yang, University of Chinese Academy of Sciences , TCA Laboratory, Institute of Software, Chinese Academy of Sciences
Junhuai Yang, University of Chinese Academy of Sciences , TCA Laboratory, Institute of Software, Chinese Academy of Sciences
Hua Chen, TCA Laboratory, Institute of Software, Chinese Academy of Sciences
Limin Fan, TCA Laboratory, Institute of Software, Chinese Academy of Sciences

Abstract
Masking stands as one of the most effective countermeasures against side-channel attacks. While a number of recent works have investigated first-order masking schemes that eliminate the need for fresh randomness, most existing solutions trade off this randomness reduction against increased latency or area overhead. This paper targets the simultaneous achievement of low latency and zero fresh randomness. To this end, we make the following contributions. First, we identify a security flaw in the round-based design proposed by Askeland et al.\ at CARDIS 2022, which builds upon the Changing of the Guards (COTG) technique. Second, we propose a revised construction that rectifies this vulnerability without incurring any additional randomness or latency penalty. Finally, by integrating the Time Sharing Masking (TSM) S-box introduced at CHES 2025, we present a first-order masked AES implementation with a latency of 20 clock cycles that requires no fresh randomness.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Towards Post-Quantum Secure eSIM Provisioning Protocols (2026/1225)

Authors

Harrison Banda, University of Regensburg
Hannes Bartz, German Aerospace Center (DLR)
Juliane Krämer, University of Regensburg
Michael Meyer, University of Regensburg
Vincent Quentin Ulitzsch, Massachusetts Institute of Technology

Abstract
The eSIM specification enables remote SIM provisioning without the need to hand out a physical SIM card. Instead of a physical SIM card, the subscriber downloads a SIM profile, which contains a subscriber's identity and authentication key material, to their embedded UICC, a discrete, embedded chip in the user's phone. This provisioning process is specified in the remote SIM provisioning (RSP) protocol and is secured through contemporary public-key cryptography. However, the potential advent of general-purpose quantum computers threatens the security of RSP. This paper provides a quantum threat analysis of the RSP protocol, considering both Harvest Now, Decrypt Later attacks and active quantum attacks. To alleviate this threat, this paper introduces PQC-RSP, a post quantum secure version of the RSP protocol. The main challenge we address is the introduction of key encapsulation mechanisms (KEMs) into the RSP protocol, both in a PQC-only and hybrid version, and the security implications of this modification. We prove the security of PQC-RSP and review the performance overhead introduced through the usage of post quantum cryptography.
(show hidden)

Publication status: Published elsewhere. Major revision. ACNS 2026 First uploaded: , last revision:

On Arithmetic Private Information Retrieval: Why Code-Based PIR (Usually) Fails (2026/1224)

Authors

Benny Applebaum, Tel Aviv University
Yuval Ishai, Technion – Israel Institute of Technology
Shahar Shechter, Tel Aviv University

Abstract
We initiate the study of arithmetic private information retrieval (APIR) schemes, in which the database is a vector of field elements and the scheme makes a black-box use of the field. We obtain the following results. 1. Our main result is a negative one: We show that no single-server APIR scheme can achieve non-trivial download cost smaller than $n$ field elements. We observe that recent proposals for code-based PIR (Holzbaur et al., ISIT'20; Verma and Hollanti, ISIT'24) are arithmetic, and show how to break them within a few minutes on a standard workstation for all suggested parameters. 2. We complement the above by positive results in alternative models. Concretely, we show that with either two servers or a single server with secret-key preprocessing, it is possible to construct computationally secure APIR schemes based on well-studied coding assumptions. This is achieved by arithmetizing the distributed-point-function-based PIR of Boyle et al.(CCS'16), and by observing that the recent construction of secret-key single-server PIR by Chen et al.(STOC'26) also arithmetizes. 3. Finally, we characterize the existence of information-theoretic two-server APIR schemes in linear-algebraic terms, and show that communication of $O(n^{1/3})$ can be achieved in this setting based on the original approach of Chor et al.(FOCS'95). The optimality of this result remains an interesting open question.
(show hidden)

Publication status: A major revision of an IACR publication in CRYPTO 2026 First uploaded: , last revision:

Neon NTT - (Auto)formalised (2026/1223)

Authors

Hanno Becker, Amazon Web Services

Abstract
This document provides a machine-checked Isabelle/HOL formalisation of the modular-arithmetic core of the Neon NTT paper of Becker, Hwang, Kannwischer, Yang, and Yang. We develop parametric theories of Barrett and Montgomery reduction and multiplication; the equivalence of Barrett and Montgomery arithmetic; the doubling- and rounding-Montgomery variants; and correctness and bounds theorems for Neon assembly kernels, against a hand-written model of the word arithmetic underlying the relevant Neon instructions. The development is a directed auto-formalisation: definitions, theorem statements, and proofs were produced by Claude Opus 4.7 and 4.8 using AutoCorrode's LLM-Isabelle integration layers. The human author set the architecture, chose abstractions and proof strategies, often nudged the model toward shorter or cleaner proofs, and controlled which output entered the development. This document is auto-generated from the Isabelle sources through Isabelle’s document preparation system, eliminating drift between prose and formal artifact.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

UCX is All You Need: A Universal Transform for Committing Authenticated Encryption (2026/1222)

Authors

Mihir Bellare, University of California, San Diego
Rishabh Ranjan, University of California, San Diego
Nujud Senan, King Abdulaziz City for Science and Technology
Basel Alomair, King Abdulaziz City for Science and Technology , University of Washington , HUMAIN

Abstract
Emerging attacks and applications have motivated the development of transforms that turn a given AE scheme into a committing AE (cAE) one. We give a new transform called UCX with the following attributes: It does not require the starting scheme to be tag based, works for schemes in the broad AE5 framework rather than the limited AE1 one, and preserves both UNAE (Unique Nonce AE) and MRAE (Misuse Resistant AE) security. No prior transform is ``universal'' in the sense of having the combination of all these properties. The use of UCX in place of prior, limited transforms reduces the risk of error and failure in the real world, where choices may be made by application developers and hidden in software libraries. The committing security of UCX is shown in the ideal-cipher model, and its AE5-security in the standard model. To design UCX, we introduce and build a new primitive, that we call a Tweakable Committing Concealer, and that may be of independent interest.
(show hidden)

Publication status: A minor revision of an IACR publication in CRYPTO 2026 First uploaded: , last revision:

Achieving Shannon Capacity for Computationally Bounded Errors (2026/1221)

Authors

George Lu, The University of Texas at Austin
Jad Silbak, Massachusetts Institute of Technology
Daniel Wichs, Northeastern University , NTT Research

Abstract
We study error correction in a computationally bounded world, where errors are introduced by an arbitrary polynomial-time adversarial channel. Recent works construct seeded codes in this model, where the encoding and decoding procedure share a public random seed. They achieve significantly better tradeoffs between rate and error tolerance than what is possible information theoretically for unique decoding, essentially matching the parameters of the best known efficiently list-decodable codes. Over the binary alphabet, however, this is still well short of the optimal Shannon capacity with rate $R \approx 1 - H_2(p)$ for a $p < 1/4$ fraction of errors. Even heuristic constructions meeting this target were not previously known. We make progress towards this goal. - $\textbf{Secret-Key Codes.}$ We first study secret-key codes, where the encoder and decoder share a secret key hidden from the adversarial channel. Lipton (STACS '94) constructed one-time secure secret-key codes achieving Shannon capacity in this setting, but it was unknown whether one can get CPA (resp. CCA) security where the adversary may query an encoding oracle (resp. also a decoding oracle). We construct CCA-secure secret-key codes achieving Shannon capacity via pseudorandom codes (PRCs). - $\textbf{Seeded Codes (Heuristic).}$ We can heuristically upgrade the resulting secret-key codes to seeded codes by publishing an obfuscation of the encoding/decoding procedures with a hard-coded secret key as a seed. Security holds in the ideal obfuscation model. - $\textbf{Public-key Codes.}$ We also consider public-key codes, where the decoder has a secret key and the encoder has the corresponding public key. We construct such CPA-secure public-key codes achieving Shannon capacity with unique decoding for $p < 1/4$ errors, and list decoding all the way to $p < 1/2$ errors, assuming PRCs and the subexponential security of standard crypto assumptions (e.g., LWE or DDH or QR or DCR). We also show how to get CCA security in the random oracle model. Our secret-key and public-key codes meeting Shannon capacity are also simultaneously pseudorandom codes.
(show hidden)

Publication status: A minor revision of an IACR publication in CRYPTO 2026 First uploaded: , last revision:

Explicit Transformations from Edge-Depth-Robust to Node-Depth-Robust Graphs with Improved Concrete Efficiency (2026/1220)

Authors

Jeremiah Blocki, Purdue University West Lafayette
Nathan Smearsoll, Purdue University West Lafayette

Abstract
Depth-robust directed acyclic graphs (DAGs) are an important combinatorial primitive in cryptography, with applications to memory-hard functions, proofs of space, and proofs of sequential work. These applications require node depth-robustness, yet constructing sparse graphs with strong concrete guarantees remains a longstanding challenge. By contrast, edge depth-robust graphs are easier to construct explicitly and achieve better parameters, motivating the problem of efficiently transforming edge-depth-robust graphs into node-depth-robust graphs. We give a new and substantially more efficient transformation from edge-depth-robust graphs to node-depth-robust graphs. We give a new and substantially more efficient transformation from edge-depth-robust graphs to node-depth-robust graphs. Prior work of Blocki and Cinkoske (ITCS 2021) gave a general transformation by replacing each node with an ST-robust graph, resulting in extraordinarily large overhead and relying on non-explicit components. In contrast, our transformation replaces each node with a single superconcentrator rather than an ST-robust graph, yielding an explicit construction whenever the input graph is explicit, with dramatically improved concrete efficiency. Formally, given an $(e,d)$-edge-depth-robust graph $G$ with $N$ nodes and $m$ edges, our transformation generates a graph $G'=Transform(G_N)$ with $N' = O(m)$ nodes, constant indegree, and $(e/3,\, 2d-1)$-node depth-robustness. We also show that the transformation preserves fractional depth-robustness. Moreover, when $m=\omega(N)$, we show that our transformation can amplify depth --- overcoming a key limitation of prior work. In particular, for any parameter $d'$, we can obtain a constant-indegree graph $G'$ with $N' = O(m+d'N)$ nodes and $(e/3,\, (d-e)d')$-node depth-robustness, yielding asymptotically tighter results in the important setting where $m = \omega(N)$ and $e \geq d$ by setting $d' \sim m/N$. As an application, We provide a novel analysis of Schnitger's edge-depth-robust graph construction (FOCS 1983). We show that the graph $G_n$, which has $N=2^{n+1}-1$ nodes and $m \leq n2^{n}$ edges, is $(e,2d-1)$-edge-depth robust for all $e + d \leq 2^n$. Applying our transformation yields an explicit DAG on $N'$ nodes with maximum indegree $2$ and depth-robustness parameters $e = \Omega(N'/\log N')$ and $d = \Omega(N')$, matching the best known asymptotic trade-offs—even compared with non-explicit constructions—while improving the best previously known concrete ed-product lower bound by a multiplicative factor of 6.6.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Algorithms for solving the isogeny problem with oriented elliptic curves (2026/1219)

Authors

Maria Corte-Real Santos, École Normale Supérieure de Lyon , French National Centre for Scientific Research
Arthur Herlédan Le Merdy, KU Leuven
Joseph Macula, University of Colorado Boulder
Michael Meyer, University of Regensburg
Travis Morrison, Virginia Tech
Eli Orvis, University of Colorado Boulder

Abstract
We introduce WayFinder, a framework for generalizing the Delfs-Galbraith and SuperSolver algorithms for the supersingular isogeny problem. Our framework extends the search for elliptic curves with an orientation by an order containing $\mathbb{Z}[\ell \sqrt{-p}]$ to more general orders, and we derive a cost model for such generalisations. Our cost model not only works in a more general context, but also provides more accurate predictions when applied to SuperSolver. We instantiate WayFinder for orders containing $\mathbb{Z}[\ell_1\sqrt{-\ell_2p}]$ where $\ell_i$ are $1$ or primes such that the modular curve $X_0(\ell_2)$ has genus $0$. We then introduce a low-storage algorithm for computing an isogeny between two oriented supersingular elliptic curves, even when the curves are oriented by distinct orders. Together, these provide an algorithm that improves on the state of the art for solving the isogeny problem, and a cost model with potential applications to parameter selection in isogeny-based cryptography.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

High-Accuracy, Poisoning-Resilient Frequency Estimation in the Shuffle Model (2026/1218)

Authors

Shaoqiang Wu, Nankai University
Jingyu Jia, Nankai University
Yikuan Zhu, Nankai University
Xinhao Li, Nankai University
Changyu Dong, Guangzhou University
Zheli Liu, Nankai University

Abstract
We study frequency estimation in the shuffle model of differential privacy under poisoning attacks, where corrupted users may deviate from the local randomizer to inject crafted in-domain messages. Existing shuffle-model protocols face a core tension: achieving low estimation error relies on flexible multi-message noise generation, which can amplify poisoning influence once messages are anonymized by shuffling. To address this tension, we propose a symmetric binomial-sum noise distribution (i.e., $\mathrm{Bin}(n/2,p) + \mathrm{Bin}(n/2,1-p)$), which preserves high accuracy while limiting the impact of crafted in-domain messages. We realize this distribution via preprocessing-guided noise generation, which routes a balanced collection of mode flags through the shuffler so that each user receives a randomly assigned mode flag that fixes their noise-sampling behavior prior to shuffling. For binary estimation, our protocol requires a single Bernoulli trial per user and at most $2$ messages per user ($1.5$ on average), while bounding the worst-case poisoning influence of a single corrupted user by $O(1/n)$. We extend the protocol to histograms, including large domains via hashing, and provide formal privacy, accuracy, and robustness guarantees. Experiments on real datasets show that our protocols remain resilient under poisoning and reduce MAE by up to nearly $2\times$ over the strongest baseline at comparable per-user communication on small-domain workloads, and stay on par with it on large domains.
(show hidden)

Publication status: Published elsewhere. Major revision. USENIX Security 2026 First uploaded: , last revision:

Secure Computation against $\mathsf{NC^1}$ Leakage without Secure Hardware (2026/1217)

Authors

Yuyu Wang, University of Electronic Science and Technology of China

Abstract
In this work, we construct (stateful) leakage-resilient circuits (LRCs) secure against bounded-output-length leakage functions computable by \(\mathsf{NC}^1\) circuits under the mild worst-case assumption \(\mathsf{NC}^1 \subsetneq \oplus\mathsf{L}/\mathsf{poly}\), without relying on any leak-free hardware components, thereby resolving the open problem left by Bogdanov, Ishai, and Srinivasan (Journal of Cryptology, 2021) and Wang (CRYPTO 2025). Concretely, we first construct a leakage-tolerant circuit with succinct setup (sAI-LTC) secure against 2-adaptive \(\mathsf{NC}^1\) leakage, and then generically combine it with a 2-adaptive leakage-resilient composable encoding scheme to obtain the desired LRC. We further give a direct non-black-box instantiation that optimizes the compiled circuit size at the cost of a slightly larger setup, matching the circuit size of Wang's construction that relies on leak-free hardware while using a more compact setup. Finally, we show that our sAI-LTC generically implies a fine-grained multi-theorem non-interactive proof system for all \(\mathsf{NP}\), with compact common reference strings, perfect soundness, and multi-theorem zero-knowledge with offline simulation against \(\mathsf{NC}^1\) adversaries.
(show hidden)

Publication status: A major revision of an IACR publication in CRYPTO 2026 First uploaded: , last revision:

New Quantum-Classical Algorithm or the Discrete Logarithm Problem over $\mathbb{Z}_{p}^{*}$ (2026/1216)

Authors

Hidenori Kuwakado, Kansai University
Shoichi Hirose, University of Fukui

Abstract
Shor demonstrated that the discrete logarithm problem in the multiplicative roup $\mathbb{Z}_{p}^{*}$, where $p$ is an odd prime, can be solved fficiently using a period-finding algorithm based on the quantum Fourier transform. In this paper, we propose a quantum-classical algorithm based on algebraic properties that do not rely on periodicity. Specifically, we show that the hardcore predicate for the discrete logarithm problem, which was introduced by Blum and Micali, can be reduced, using the swap test, to the problem of distinguishing between two Bernoulli distributions. In our algorithm, although the swap test is used as a quantum subroutine, most of the computation is performed classically. Moreover, the algorithm does not require the quantum Fourier transform.
(show hidden)

Publication status: Published elsewhere. Major revision. The 54th Quantum Information Technology Symposium First uploaded: , last revision:

On the Cryptographic Structure Required for Verifying Qubits (2026/1215)

Authors

James Bartusek, Columbia University
Itay Shalit, Stanford University

Abstract
Classically testing for the presence of anti-commuting operators on a quantum device is a critical tool underpinning recent progress in classical verification of quantum computation. While such tests can be based on cryptographic assumptions, known constructions rely on highly structured assumptions, e.g. trapdoor claw-free functions. In this work, we seek to explain this state of affairs by constructing strong cryptography from (certain forms of) classical tests of anti-commutation. In particular, we formulate the notion of a test of non-commutation (ToNC), an interactive protocol between a quantum prover and classical verifier in which the prover's final-round response is obtained by measuring one of two binary observables 𝑃₀, 𝑃₁ depending on the verifier's challenge bit 𝑐. We prove that, for a broad range of parameters, ToNC implies classical-communication key agreement (KA), and ToNC combined with one-way functions implies oblivious transfer (OT). Along the way, we develop tools for and provide the first known results on hardness amplification for post-quantum KA and OT, where communication is classical but adversaries may be quantum. In particular, we prove the following results of independent interest. - Post-quantum hard-core measure theorem: For any efficiently sampleable high-min-entropy distribution 𝐷 over pairs (𝑥,𝑏) such that quantum circuits have advantage at most 𝛿 in predicting 𝑏 from 𝑥, there exists a sub-distribution 𝑀≼𝐷 of density 1-𝛿 on which 𝑏 is nearly optimally quantum-hard to predict. - Post-quantum interactive XOR lemma: Given any classically-interactive protocol, if quantum adversaries have advantage at most 𝛿 in guessing a private challenger bit 𝑏, then two sequential repetitions reduce the advantage for predicting the XOR of the challenger bits 𝑏₁⊕𝑏₂ to at most 𝛿² + negl(𝜆).
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Faster Leader-Based Consensus via Certificates of Exclusivity and Overlapping Iterations (2026/1214)

Authors

Matthieu Rambaud, Télécom Paris

Abstract
Blockchain consensus protocols, also known as BFT state-machine replication, enable a system of $n$ players to decide an ever-growing chain of blocks. We consider partial synchrony: after an unknown time GST, messages sent by honest players are delivered within an unknown actual delay $\delta$, and a known bound $\Delta$ satisfies $\delta \leq \Delta$. This setting imposes $t<n/3$ corruptions. We study leader-based consensus, a class with the smallest known latency metrics when sufficiently many designated leaders behave honestly. We consider the mainstream metric of {expected latency in the view-based sense:} for a transaction known to all honest players having entered a post-GST iteration, this is the expected time until that transaction appears in a decided block, under independent random leaders. We introduce Hamster, a rotating-leader consensus protocol, which reduces this expected latency to $\Delta+4\delta$, down from the previous $1.5\Delta+3.5\delta$ bound achieved by Simplex (Chan-Pass, TCC'23) for the same view-based metric. Hamster also brings this latency further down to $\Delta+3.5\delta$ for adversaries that do not get publicly caught equivocating. The main technical novelty is a certificate of exclusivity for a block $B$. It is shown by the next leader as evidence that players can safely vote for a child of $B$. A certificate of exclusivity is an interpolation between a quorum certificate and a timeout certificate, in that it is formed from a mix of votes for a unique block $B$ and complaint votes, proving that $B$ is the only non-dummy block that can still obtain a decision certificate for that iteration. The other novelty of Hamster is the use of {overlapping iterations: after a process has supported a newer proposal, the protocol may still allow it to support a safe proposal of an earlier iteration}. This overlap is what allows old honest proposals to be decided in time despite players advancing iterations faster. We also analyze another metric, called the {pessimistic block proposal time}, which is the time during which a bad leader can delay the proposal of a transaction in a block which will be decided. Hamster achieves a pessimistic block proposal time of $2\Delta+2\delta$, refined to $2\Delta+\delta$ for leaders not caught equivocating, down from $3\Delta+\delta$ for Simplex.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Another Look at Non-Frameability in Group Signatures for Anonymous Auctions (2026/1213)

Authors

Cao Shiqi, Kanazawa University
Keita Emura, Kanazawa University , National Institute of Advanced Industrial Science and Technology

Abstract
In addition to anonymity and traceability, which are the primary security properties of group signatures, non‑frameability is also defined (Bellare-Shi-Zhang, CT-RSA 2005). This property guarantees that even an adversary colluding with all authorities (the opener and the issuer) cannot produce a signature that frames an honest user, and it is regarded as a security notion that protects users. In this short note, we introduce a new perspective on non-frameability, namely that it can also protect the authorities, and we examine its significance in the context of anonymous auctions, a well‑known application of group signatures. We show that non-frameability serves as an effective countermeasure against situations in which a winning bidder falsely claims not to have placed a bid and accuses the organizer of forgery.
(show hidden)

Publication status: Published elsewhere. Minor revision. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 2027 First uploaded: , last revision:

SecLoRA: Secure Aggregation of Low-Rank Matrix Products via Functional Encryption (2026/1212)

Authors

Jiangtao Li, Shanghai University
Wei Zhang, Shanghai University
Chen Gong, Shanghai University
Jason (Minhui) Xue, CSIRO , Adelaide University
Junqing Gong, East China Normal University

Abstract
Federated fine-tuning of Large Language Models via Low Rank Adaptation (LoRA) faces a critical privacy-efficiency trade-off: low-rank factors can leak sensitive data, yet standard secure aggregation is restricted to linear operations. Existing solutions for aggregating matrix products (e.g., $\mathbf{B}_i \mathbf{A}_i$) either sacrifice exactness, depend on a trusted third party, or incur prohibitive costs at scale. We present SecLoRA, the first decentralized framework achieving exact aggregation of LoRA updates with linear communication complexity. The core of SecLoRA is a novel cryptographic primitive: Pairwise Composable Multi-Client Functional Encryption (PC-DMCFE). Unlike traditional functional encryption, which treats ciphertext recombination as an attack, the dual-encryption architecture of PC-DMCFE ($\mathsf{Enc}_A, \mathsf{Enc}_B$) is intentionally designed to harness this property. It allows any ciphertexts $\mathsf{ct}_A$ and $\mathsf{ct}_B$ to be arbitrarily paired and evaluated via a functional key to reveal their inner product. This unique property enables secure and decentralized aggregation of matrix products without losing LoRA's linear communication advantages. Furthermore, SecLoRA ensures round-isolated decryption to prevent temporal leakage without extra interaction. Evaluation shows that SecLoRA is practical for cross-silo deployments.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Private Information Retrieval: Share Conversions vs. Decoding Polynomials (2026/1211)

Authors

Amos Beimel, Ben Gurion University
Or Lasri, Ben Gurion University

Abstract
A private information retrieval (PIR) protocol enables a client to retrieve a bit from an $N$ bit database replicated among $k$ servers in such a way that each server learns no information about the retrieved bit. Modern PIR protocols with information-theoretic privacy (Efremenko, SICOMP, 2012; Dvir and Gopi, STOC, 2015; Ghasemi et al., STOC, 25) are based on matching vectors over a composite number $m$. To construct a PIR protocol from the matching vectors, these protocols use a decoding polynomial, a sparse polynomial that returns a non-zero value on 1 and returns zero on a certain set implied by the matching vectors. Beimel et al. (CCC, 2012) abstracted the properties required by the transformation computed by the decoding polynomial, defining the notion of share conversion. In such a conversion, a set of parties is given shares of a secret in one secret-sharing scheme, and each party locally computes a new share (without any communication) such that the new shares are shares in a second secret-sharing scheme of a related secret. Beimel et al. showed that share conversion can replace the decoding polynomial in the PIR protocol of Efremenko and constructed a share conversion from the ring $\mathbb{Z}_6$ to the field $\mathbb{F}_{2^2}$. This share conversion cannot be computed by a decoding polynomial, as decoding polynomials convert shares from a ring $\mathbb{Z}_m$ to a finite field of characteristic $p$ such that $p$ does not divide $m$. Alon et al. (TCC, 2025) simplified and generalized the PIR protocols of Dvir and Gopi and Ghasemi et al., using share conversion; however, in this protocol, the share conversion is from a ring $\mathbb{Z}_m$ to a finite field of characteristic $p$ such that $p$ does not divide $m$. In this paper, we study the power of share conversions. Our main result proves that if there is a $k$-party share conversion from a ring $\mathbb{Z}_m$ to a finite field of characteristic $p$ such that $p$ does not divide $m$, then there is a $k$ sparse decoding polynomial from a ring $\mathbb{Z}_m$ to a finite field of characteristic $p$. This result implies that using share conversion in the protocol of Alon et al. can only improve the communication complexity by a constant factor. In addition, we show that if there is a $k$-party share conversion from a ring $\mathbb{Z}_m$ to a finite field, where $m$ is a product of $r$ distinct primes, then $k\geq r+1$, i.e., the number of servers in the resulting PIR protocols using the appropriate matching vectors is at least $r+1$. A similar result was recently proved by Ghasemi and Kopparty (ITCS 26); our lower bound also applies to the case in which the characteristic of the field divides $m$.
(show hidden)

Publication status: Published by the IACR in CRYPTO 2026 First uploaded: , last revision:

Uncloneable Cryptography in Linear Quantum Memory (2026/1210)

Authors

Andrew Huang, Massachusetts Institute of Technology
Omri Shmueli, NTT Basic Research Laboratories
Vinod Vaikuntanathan, Massachusetts Institute of Technology
Mark Zhandry, NTT Basic Research Laboratories , Stanford University

Abstract
Quantum cryptography is a rapidly developing area which leverages quantum information to accomplish classically impossible tasks. In many of these protocols, quantum states are used as long-term cryptographic keys, relying on the quantum no-cloning theorem to ensure that the keys cannot be copied by an adversary. Unfortunately, quantum state tend to decohere, and hence, persistent quantum memory is and will remain one of the most valuable and challenging resources for quantum computers. As such, it will be important to minimize the extent to which our protocols use persistent quantum memory. In this work, we consider the case of one-shot signatures (OSS), and more general quantum signing tokens, important uncloneable primitives where quantum signing keys allow for signing a single message but not two. Very recently, the first OSS scheme was constructed unconditionally in a classical oracle model as well as in the standard model under cryptographic assumptions (Shmueli and Zhandry, CRYPTO 2025). We observe that the quantum memory required for these protocols is a large polynomial (in the security parameter). The main contribution of this work is to significantly decrease the quantum secret key size, in some cases achieving the asymptotically optimal size. One of our schemes guarantees perfect correctness and the other one admits a parallel signing algorithm for long messages. We also achieve strong signature incompressibility, which implies a public-key quantum fire scheme (Çakan, Goyal and Shmueli, QCrypt 2025) with perfect correctness. During the course of this work, we develop novel techniques for proving the security of cryptosystems using coset states, one of the main tools used in uncloneable cryptography.
(show hidden)

Publication status: A major revision of an IACR publication in CRYPTO 2026 First uploaded: , last revision:

Latency-Aware, High-Throughput Homomorphic AES Evaluation with CKKS (2026/1209)

Authors

Taeseong Kim, Seoul National University
Jonghoo Lee, CryptoLab, Inc.
Taeyeong Noh, CryptoLab, Inc.
Jung Hee Cheon, Seoul National University , CryptoLab, Inc.
Guillaume Hanrot, CryptoLab, Inc.

Abstract
Homomorphic Advanced Encryption Standard (AES) evaluation refers to evaluating the AES circuit with a fully homomorphic encryption (FHE)-encrypted secret key. Applications include in particular Transciphering, which converts AES-encrypted data into FHE ciphertexts without exposing the secret key. Existing homomorphic AES evaluations show a clear separation between latency-oriented solutions and throughput-oriented solutions. CKKS-based methods exploit massive SIMD parallelism and focus on throughput by processing many AES blocks in parallel. They are hardly suitable for latency-critical settings. In contrast, TFHE-based methods process a small number of blocks efficiently. They are preferable for low-latency settings, but provide very limited throughput. In this work, we show that AES-CKKS evaluation can achieve both interactive latency and high throughput. Our first variant is optimized for latency and decrypts a single AES block in only 34ms on an NVIDIA RTX-5090. This is more than 4× faster than recent TFHE-based state-of-the-art approaches. Our second variant is based on a new embedding of $\textrm{GF}(16)$, the finite field with 16 elements, into CKKS message space. It is optimized for throughput and processes up to 2048 AES blocks at once, achieving over 200KB/s throughput (a more than 3.1× improvement over the state-of-the-art CKKS-based approaches), while maintaining latency comparable to TFHE-based methods. To the best of our knowledge, this is the first AES-FHE evaluation algorithm combining good latency and throughput properties, bringing homomorphic outsourcing with AES within reach of real-time applications on constrained devices. Our main ingredients are redundant structures that maximize SIMD utilization, improved algorithms for the SubBytes step (one of them being based on inversion in $\textrm{GF}(256)$ using CKKS), fusion of linear layers into bootstrapping, and carefully crafted FHE parameters.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Preimage sampleable function families without discrete Gaussians (2026/1208)

Authors

Eamonn W. Postlethwaite, King's College London
Filip Trenkić, King's College London

Abstract
We construct preimage sampleable function families on $q$-ary lattices [Gentry–Peikert–Vaikuntanathan, STOC'08] for which preimage sampling reduces to sampling uniform points of unitriangular lattices from simple polytopes: affine linear transforms on the $\ell_1$ and $\ell_\infty$ balls, and a scaled intersection thereof. We build the necessary samplers by adapting an algorithm of [Kannan–Vempala, STOC'97] and improving its analysis. This sampling requires only uniform bits and affine linear transforms on the uniform distribution on $[0,1]$. The collision resistance of these families relies on the short integer solutions problem [Ajtai, STOC'96] in various $\ell_p$ norms. Considering the Lee metric as the $\ell_1$ norm in $q$-ary lattices, we answer an open question to construct such families for the Lee metric [Hörmann–van Woerden, CRYPTO'24]. We also answer an open question of [Plançon--Prest, PKC'21] by sampling from polytopes with inradius smaller by a factor almost square root in the lattice rank. We provide a generic framework for constructing preimage sampleable function families from polytopes with sufficient conditions for realising it. While our parameters are worse than prior discrete Gaussian based constructions, such distributions are challenging from a physical security perspective.
(show hidden)

Publication status: Published by the IACR in CRYPTO 2026 First uploaded: , last revision:

"Sticking their heads out above the parapets": Lived Experiences of Legal Risks in Research (Extended) (2026/1207)

Authors

Sunoo Park, New York University
Daniel R. Thomas, University of Strathclyde

Abstract
Overbroad computer crime, intellectual property, and other laws are well known to create legal risks that can discourage essential research. Notable examples include the US Computer Fraud and Abuse Act and the UK Computer Misuse Act. Because such laws fail to distinguish malicious hacking from good-faith testing and research, researchers face serious legal risks for public-interest research activity like identifying software or hardware vulnerabilities or scraping data. Despite the research community's broad awareness of these risks, our understanding of their practical impacts is limited, as most of the community's knowledge comes from anecdotal evidence rather than systematic study. We conduct the first qualitative study focused on researchers' lived experiences, to empirically document the *impacts of legal risks and threats* on research and researchers*, and *how researchers navigate legal risk situations*. Our study engages two participant groups: researchers with legal-risk experiences in the UK or the US ($N_R=36$), who discuss 130 projects and incidents spanning over three decades, and professionals that offer support to researchers navigating legal risks ($N_S=8$), who have collectively supported thousands of researchers. We thus provide an unprecedented big-picture view of researchers' experiences with legal risks. We synthesise actionable strategies for researchers, and our findings provide evidence to support policy reform.
(show hidden)

Publication status: Published elsewhere. Major revision. USENIX Security Symposium 2026 First uploaded: , last revision:

Scalable, quantum-accessible, and adaptive pseudorandom quantum state and pseudorandom function-like quantum state generators (2026/1206)

Authors

Rishabh Batra, Centre for Quantum Technologies, Singapore , National University of Singapore
Zhili Chen, Centre for Quantum Technologies, Singapore , National University of Singapore
Rahul Jain, Centre for Quantum Technologies, Singapore , National University of Singapore , MajuLab, UMI 3654, Singapore
YaoNan Zhang, Centre for Quantum Technologies, Singapore , National University of Singapore

Abstract
We show new constructions for pseudorandom quantum states (PRS) and pseudorandom function-like quantum state (PRFS) generators satisfying scalability, which means the security parameter can be much larger than the number of qubits, quantum accessibility, which means the adversary can provide quantum input, and adaptivity, which means the adversary can query it adaptively. We present an isometric procedure to prepare quantum states that can be arbitrarily random (i.e., the trace distance from the Haar-random state can be arbitrarily small for the true random case, or the distinguishing advantage can be arbitrarily small for the pseudorandom case). This naturally gives the first construction for scalable, quantum-accessible, and adaptive PRFS assuming quantum-secure one-way functions. Compared to prior PRFS works, we use a stronger definition of quantum accessibility in which the adversary can be ancilla-assisted, i.e., the input state may not be pure and could be entangled with other quantum registers. Thus, our result also gives the first (fully) quantum-accessible PRFS. Our PRFS construction implies various primitives, including long-input PRFS, short-input PRFS, short-output PRFS, non-adaptive PRFS, and classically-accessible adaptive PRFS. This new construction may be helpful in simplifying the microcrypt zoo.
(show hidden)

Publication status: A major revision of an IACR publication in CRYPTO 2026 First uploaded: , last revision:

StakeNote: A Proof-of-Stake Protocol for CryptoNote Payments (2026/1205)

Authors

Bernardo David, Common Prefix , IT University of Copenhagen (ITU)
Dimitris Karakostas, Common Prefix

Abstract
This work proposes StakeNote, a distributed ledger protocol that combines Proof-of-Stake (PoS) with privacy and anonymity preserving payments. The protocol combines Ouroboros Praos, a provably secure PoS protocol, with CryptoNote, a privacy-preserving payment system based on ring signatures which has been widely used in practice. We prove that StakeNote inherits the security guarantees of Ouroboros Praos and the privacy guarantees of CryptoNote and we demonstrate its practicality via a proof of concept implementation, where block creation requires less than 25 ms and eligibility proofs are approx. 3 KB for anonymity sets of size 16. Finally, we discuss heuristic enhancements that potentially increase privacy and enable dynamic participation.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Robust Single-Trace Full-Key Extraction from Million-Point Traces With Cross-Implementation Transfer (2026/1204)

Authors

Aron Gohr, cryptosolutions
Friederike Laus, Independent Researcher
Gregor Leander, Ruhr University Bochum

Abstract
End-to-end deep-learning side-channel attacks on public-key implementations have recently become possible even for million-sample traces. However, existing methods require large computational resources and extract only partial key shares, which means that dedicated post-processing is required to turn detected leakage into demonstrations of successful key recovery attacks. We present an end-to-end sequence-to-sequence prediction approach to recover complete 256-bit key shares from single raw traces on the SCAAML ECC datasets recently studied by Bursztein et al (TCHES 2024). Our solution combines aggressive trace compression for dimensionality reduction with a 1-D U-Net trained using Connectionist Temporal Classification loss. The key idea is to decouple detecting leakage from mapping each leakage site to the correct part of the secret: the network outputs an annotated map of the trace marking likely leakage sites, and a greedy decoder reconstructs the ordered key bits from that map. Using synthetic tasks, we show that this division of labor circumvents a fundamental problem that causes neural network architectures and training methods commonly used in side-channel analysis to struggle with massive multi-target or misaligned extraction tasks. As a result, we are able to train a single extractor that achieves high accuracy on all four SCAAML ECC datasets in a single training run that takes minutes on a single GPU. The resulting extractors are robust, essentially maintaining their performance under large misalignment (we empirically tested rotations up to \(61\%\) of trace length), while degrading gracefully under a variety of trace corruptions, and even time reversal. They transfer across key shares and datasets with little degradation and no retraining. The U-Net outputs also yield prediction maps that localize leakage along the trace prior to decoding.
(show hidden)

Publication status: A major revision of an IACR publication in CRYPTO 2026 First uploaded: , last revision:

Signatures with Post-Compromise Accountability (2026/1203)

Authors

Dennis Dayanikli, Hasso Plattner Institute, University of Potsdam
Johannes Lang, Technische Universität Dresden
Anja Lehmann, Hasso Plattner Institute, University of Potsdam

Abstract
Cryptographic signatures play an integral part in ensuring authenticity and integrity in digital systems. Their security crucially relies on the secrecy of the signing key, since knowledge of this key enables an adversary to generate valid signatures on any message. Once a signing key is compromised, the standard countermeasure is to revoke the corresponding public key and to invalidate all signatures produced for this key. However, with this approach even legitimate signatures created by the honest signer would retroactively lose their validity. In this work, we initiate the formal study of a new approach - Signatures with Post-Compromise Accountability (SPCA) - which provides security guarantees even after the secret key was compromised. This notion effectively introduces a grace period for the legitimate key owner, during which the validity of honestly generated signatures is preserved despite the adversary’s knowledge of the secret key. We formally define SPCA and its security guarantees, and present two constructions achieving this notion. Our first construction generalizes the signature-in-signature approach of Błaśkiewicz et al. (ESORICS '21), where an inner signature is embedded into the randomness of an outer signature. This construction, however, requires revealing the signing secret key during revalidation. Our second construction overcomes this limitation by enabling revalidation without disclosing the secret key, yielding stronger security guarantees.
(show hidden)

Publication status: Published elsewhere. Major revision. SCN 2026 - 15th International Conference on Security and Cryptography for Networks First uploaded: , last revision:

Morphic Accumulators and Applications: Optimal Range Proofs, Polynomial Commitments, and Ring Signatures (2026/1202)

Authors

Dimitrios Papadopoulos, Hong Kong University of Science and Technology
Qiang Tang, The University of Sydney
Jiajun Xin, The University of Sydney

Abstract
Cryptographic accumulators based on groups of unknown order (GUO) provide constant-size set membership proofs. For security purposes, existing works require first encoding set elements via division-intractable (DI) hash functions, typically instantiated as random oracles that destroy any algebraic structure. This confines GUO-based accumulators to a purely set-membership role, making them "incompatible" with various existing cryptographic proof techniques over committed integers in the same groups as the GUO, such as constant-size proofs of exponentiation and modular exponent relations. We introduce the notion of morphic accumulators, which replaces the DI hash with a discrete logarithm encoding $H_g(x) = g^x$, mapping set elements to a group before accumulation. We prove, under a variant of the subset product assumption in the generic group model, that this encoding is inherently division intractable, achieving the same security guarantee as random-oracle DI hashes, while simultaneously being a group homomorphism: accumulated elements retain their group-algebraic relationships. This resolves a fundamental tension between compact representation and algebraic structure: the accumulator serves simultaneously as a binding commitment to a set and as a substrate for homomorphic computation over its elements. Morphic accumulators yield asymptotically optimal constructions across multiple domains: range proofs with $O(n)$ prover time, $O(1)$ proof size, $O(1)$ verification with transparent setups (the first scheme to simultaneously achieve these optimal bounds); polynomial commitments with $O(n)$ prover and $O(1)$ proof size, resolving the cubic bottleneck in prior constant-proof-size GUO-based schemes; and the first linkable ring signatures with $O(1)$ signature size, transparent setup, $O(n)$ offline signing and $O(1)$ online signing.
(show hidden)

Publication status: A major revision of an IACR publication in CRYPTO 2026 First uploaded: , last revision:

Silentium revisited: Pseudorandom Beaver Triple Expansion (2026/1201)

Authors

Vincent Rieder
Enrico Sorbera, Fondazione Bruno Kessler , University Of Trento,

Abstract
In the line of the SPDZ protocol for secure multi-party computation, the generation of Beaver triples is the most expensive task. Silentium (Rieder, PrivCryp 25) is the implementation of a Pseudorandom Correlation Generator (PCG) for Beaver triples (Boyle et al., Crypto 20). PCGs focus on low-communication costs., e.g. their PCG reduces the communication by one order of magnitude compared to protocols in MP-SPDZ. Silentium is an implementation of their PCG, achieving similar running times than MP-SPDZ. We make three theoretical contributions to Silentium, including an implementation. First, we make a practical proposal how to generate Beaver triples over binary fields F2λ, which extends the previous setting over prime fields. For this, we propose a suitable instantiation of the Number Theoretic Transform. Second, we show how to use the binary triples to construct what we call a Beaver triple expansion scheme, that is we construct a scheme that expands a small batch of Beaver triples into a large batch of Beaver triples, in the sense of recently established oblivious transfer extension schemes. This feature enables an efficient preprocessing stage for the PCG, closing a practical issue of Silentium. Finally, we provide details about the Silentium implementation, by clearing a technical bug in the initial theoretical protocol description.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Character Block Encodings for Discrete CKKS: Single-Level LUTs and Low-Depth Arithmetic (2026/1200)

Authors

Jules Dumezy, CEA LIST , University of Paris-Saclay
Elias Suvanto, University of Luxembourg

Abstract
Functional bootstrapping has made discrete computation practical in the Cheon-Kim-Kim-Song (CKKS) scheme, but it fuses four distinct tasks - lookup table (LUT) evaluation, modular reduction, noise cleaning, and ciphertext refreshing - into a single rigid pipeline. As a consequence, a generic LUT over an alphabet of size $t$ costs multiplicative depth proportional to $\log_2 t$ and consumes a large share of the modulus budget during a fixed bootstrapping procedure, invoked each time a LUT evaluation or modular reduction is needed. We show that this pipeline can be unbundled by changing the representation, rather than optimizing the bootstrapping, through block encodings. A finite-alphabet value is carried across several CKKS slots whose coordinates form a basis of functions on the alphabet, typically the characters of a finite abelian group. In such a basis, every LUT is an affine plaintext map evaluated in a single multiplicative level, with depth independent of $t$. Modular reduction comes for free: a block encoding cannot represent anything but a residue, so arithmetic modulo $t$ is native. Because the encoded values lie on the unit circle, noise growth is independent of the alphabet size $t$. In the worst case, it matches the noise growth of standard discrete CKKS on the smallest alphabet $\mathbb Z_2$, and in more typical workloads it is linear in the number of operations, exponentially better than discrete CKKS at every $t > 2$. Noise cleaning becomes a constant-depth procedure of at most four levels, because the alphabet-dependent part is an LUT and only a fixed-degree-3 smoothstep is nonlinear. Finally, since LUTs are no longer part of the bootstrapping, refreshing reverts to its classical role as a maintenance operation invoked only to regain multiplicative depth. Any CKKS bootstrapping can be used, rather than a constrained and expensive pipeline. We instantiate the framework with several block encodings that make modular addition, modular multiplication, xor or min/max possible with a single CKKS multiplication. We use them to build CRT arithmetic over large composite moduli, and finite-state prefix scans for radix addition and subtraction in depth $4 + \lceil\log_2 d\rceil$ and for equality and comparison in depth $3 + \lceil\log_2 d\rceil$ for $d$ radix digits. For example, a 256-bit CRT modular addition or multiplication consumes a single multiplicative level and has a latency of 4.7 ms on a single thread.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

A Post-Quantum Commitment Scheme from Richelot Isogeny Walks on Superspecial Genus-2 Jacobians (2026/1199)

Authors

Nouhou Abdou Idris, Mohammed VI Polytechnic University
Mustapha Hedabou, Mohammed VI Polytechnic University

Abstract
We present a post-quantum commitment scheme based on kernel-tagged punctured Richelot isogeny walks on superspecial genus-2 Jacobians. The puncturing rule skips every step landing in the product locus, detected by I10 = 0, so honest executions remain in the Jacobian locus and avoid the entry point of known product-locus attacks. Each opening is encoded as a deterministic non-backtracking walk together with a kernel tag recording its action on a small public auxiliary torsion basis. The tag is verified as part of the opening and is kept explicit throughout the security analysis. In particular, scalar-related collisions force equality of the ordered kernel sequence and hence equality of the tag, so any nontrivial binding attack yields a short non-scalar endomorphism. Using spectral bounds for the Richelot graph, we show that puncturing preserves rapid mixing for logarithmic walk lengths, which yields statistical hiding for the tagged punctured scheme. We therefore reduce binding to the Short Richelot Endomorphism Problem (SREP), relate SREP to the One-Endomorphism Problem and, under a standard KLPT2 -style heuristic, to the endomorphism-ring problem. A SageMath prototype based on (2, 2)-Kummer isogenies indicates practical performance at standard security levels.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Splittings and Endomorphism Rings (2026/1198)

Authors

Péter Kutas, University of Birmingham , Eötvös Loránd University
Min-Yi Shen

Abstract
Finding a nontrivial endomorphism of a given supersingular elliptic curve is a hardness assumption of isogeny-based cryptography. We prove the reduction from it to the problem of finding a splitting of a given principally polarized abelian surface. By using this new reduction, we also prove the heuristic equivalence of the splitting problem with a degree restriction and the endomorphism ring problem in dimension two.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

VOBE: Verifiable Outsourced Batched Encryption for Secure Delegation of Batched Decryption (2026/1197)

Authors

Kwangsu Lee, Sejong University

Abstract
Batched encryption (BE) has emerged as a novel public-key cryptographic paradigm that enables the efficient decryption of a designated batch of $B$ ciphertexts simultaneously. By incorporating threshold decryption capabilities into this framework, batched threshold encryption (BTE) further decentralizes the decryption process. While both BE and BTE serve as highly effective solutions for mitigating Miner Extractable Value (MEV) attacks in blockchain networks by providing robust mempool privacy, ciphertext integrity, and communication efficiency, they still suffer from heavy computational overhead during the ciphertext decryption phase. In this paper, we address this computational bottleneck by introducing a novel framework that delegates the heavy decryption workloads to an untrusted cloud server while enabling verifiability of the outsourced computations. To achieve this, we first propose an outsourced batched identity-based encryption (O-BIBE) scheme by integrating outsourcing functionalities into the conventional BIBE paradigm, accompanied by a rigorous security proof. We then construct a verifiable outsourced batched encryption (VOBE) scheme by strategically combining O-BIBE with other core cryptographic building blocks and formally prove its security. To eliminate the single point of failure and enhance threshold resiliency, we extend our framework to the threshold setting by developing an outsourced threshold batched identity-based encryption (O-TBIBE) scheme. Building upon this, we propose a verifiable outsourced batched threshold encryption (VOBTE) scheme, which successfully achieves decentralized threshold resilience. Our proposed VOBE and VOBTE schemes are the first to concurrently guarantee ciphertext integrity and mempool privacy against sophisticated blockchain attacks, while significantly reducing decryption costs via efficient and verifiable outsourcing.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Grand Danois: Succinct Multilinear Polynomial Commitments over Lattices (2026/1196)

Authors

Anders Kallesoe, Aarhus University
Hamidreza Khoshakhlagh, Aarhus University , Partisia ApS

Abstract
We present Grand Danois, a new post-quantum multilinear polynomial commitment scheme from lattices for polynomials over $\mathbb{F}_q$ that achieves polylogarithmic $O(\lambda \ell)$ verification complexity and proof sizes. We build on the general approach introduced in Hachi (ePrint 2026/156) with two key changes. First, we switch to the vanishing Short Integer Solution (vSIS) assumption to obtain structured public parameters for our commitment scheme and utilize this structure to design an adapted sumcheck protocol amenable to succinct verification. Second, we modify the quadratic relation used in Hachi and Greyhound (CRYPTO 2024) so that it becomes compatible with proving norm bounds using Johnson-Lindenstrauss projections. This is achieved through an adaptation of the structured projection strategy introduced in RoK and Roll (ASIACRYPT 2025). This has the benefit for communication complexity in that proving norm bounds and correct polynomial evaluation are integrated into a single protocol, reducing the number of commitments sent by the prover. Furthermore, we impose additional structure on our random projections to reduce the witness size even more aggressively during each round of recursion without sacrificing verification complexity. Under the vSIS assumption, our construction yields an estimated proof size of roughly $80-90$ KB for $2^{32}$-size polynomial evaluations.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

DecryptChain: A Permissionless Proof-of-Work Encrypted Mempool (2026/1195)

Authors

Nicolas Alhaddad, Boston University
Alireza Kavousi, University College London

Abstract
Blockchain mempool transparency fuels Maximal Extractable Value (MEV), where attackers can front-run, back-run, and reorder transactions as soon as they appear. Encrypted mempools aim to delay the release of information until block commitment, yet nearly all existing designs rely on a trusted decryption committee. This creates two structural problems. First, committee members hold decryption material by design, so a colluding threshold can reconstruct the decryption key and learn transactions before block commitment. Second, once such a committee becomes malicious, honest parties have no easy in-protocol way to recover: restoring privacy for future epochs requires an external intervention such as a hard fork that replaces the committee and rotates the long-lived cryptographic material. In this work, we ask whether encrypted mempools can instead use proof-of-work to realize an open and recoverable decryption committee. We then introduce DecryptChain, a permissionless proof-of-work encrypted mempool in which decryption authority is not assigned to persistent identities or long-lived key shares. Instead, decryption is continuously re-contested through public computational work. Even if an adversary successfully breaches one epoch, it gains no reusable secret for future epochs; honest parties can always re-enter and recover the decryption process by contributing sufficient work. DecryptChain decouples block production from decryption, enabling it to operate as a Layer-2 timely decryption service on any underlying blockchain while preserving eventual decryption for committed on-chain encrypted transactions.
(show hidden)

Publication status: Preprint. First uploaded: , last revision:

Unconditionally Secure MPC for Boolean Circuits with Constant Communication (2026/1194)

Authors

Yubo Zeng, Laboratory of Trusted Computing and Information Assurance, Institute of Software, Chinese Academy of Sciences, Beijing, China
Kang Yang, State Key Laboratory of Cryptology, Beijing, China
Dengguo Feng, Laboratory of Trusted Computing and Information Assurance, Institute of Software, Chinese Academy of Sciences, Beijing, China
Min Zhang, Laboratory of Trusted Computing and Information Assurance, Institute of Software, Chinese Academy of Sciences, Beijing, China

Abstract
The communication complexity of unconditionally Secure Multi-Party Computation (MPC) protocols has been studied by a series of works in the honest-majority setting. For evaluating an arbitrary Boolean circuit, the state-of-the-art MPC protocol by Goyal et al. (Crypto 2021 and Crypto 2022) achieves the total communication cost of $O(\log n)$ bits per gate, where $n$ is the number of parties. In this work, we present the first unconditional MPC protocol for any Boolean circuit with communication of $O(1)$ bits per gate. We first construct an unconditionally secure protocol in the presence of semi-honest adversaries, and then strengthen it to guarantee security against malicious adversaries with the same communication efficiency.
(show hidden)

Publication status: Published elsewhere. Major revision. A major revision of an IACR publication in Crypto 2026 First uploaded: , last revision:

Cryptanalytic Properties of Mealy Machines (2026/1193)

Authors

Zhongfeng Niu, Nanyang Technological University
Tim Beyne, KU Leuven
Kai Hu, Shandong University
Meiqin Wang, Shandong University

Abstract
This paper proposes a systematic approach to compute cryptanalytic properties of arbitrary Mealy machines or S-functions. Based on the geometric approach to cryptanalysis, we provide a uniform formula for any cryptanalytic property of such a function, as long as the property is compatible with the way its input and output are split into chunks. Examples include linear, (quasi) differential, (ultrametric) integral, differential-linear, and boomerang properties. To illustrate our results, we compute these properties for several important examples, including modular additions, the Chi- and ChiChi-functions, and the SHA-1 step function. As proof-of-concept applications, we construct a boomerang distinguisher for the Subterranean permutation, and show how to compute the correlations of conditional linear approximations in partitioning-based differential-linear attacks more accurately. Our results also lead to a new approach to compute the algebraic normal form of the inverse of the Chi-function.
(show hidden)

Publication status: A minor revision of an IACR publication in CRYPTO 2026 First uploaded: , last revision:

Lower Bounds on Black-Box Constructions of Pseudorandom Functions (2026/1192)

Authors

Bar Alon, Tel Aviv University
Itai Dinur, Ben-Gurion University of the Negev , Georgetown University
Muthuramakrishnan Venkitasubramaniam, Georgetown University

Abstract
In their seminal work, Goldreich, Goldwasser, and Micali [CRYPTO 1984] constructed a pseudorandom function (PRF) using a black-box access to a pseudorandom generator (PRG). When combined with Levin's domain extension technique, the GGM construction invokes the PRG $\omega(\log n)$ times, where $n$ denotes the input length to the PRG. To this day, no black-box construction achieving fewer calls is known. Recently, Beimel, Malkin, and Mazor [CRYPTO 2024] showed that for a certain family of constructions, which they termed \emph{tree constructions}, the GGM construction is optimal. However, the basic challenge of whether a PRF can be built with just \emph{one invocation} of the PRG still remains open. In this work, we consider fully black-box constructions of PRFs from PRGs, where both the construction and the reduction are required to be black-box, and the number of interactions the reduction makes with the adversary is independent of the number of oracle calls the adversary makes to its underlying function within each interaction. Our main result shows that no such construction can have $o(n/\log n)$ and $o(\mathsf{in}/\log\mathsf{in})$ \emph{non-adaptive} calls to the PRG, where $\mathsf{in}$ is the input length of the PRF. This impossibility holds even for weak PRFs with one-bit output, where the adversary is restricted to making i.i.d. uniformly random queries. In addition, we prove a lower bound for weak PRFs with sufficiently long outputs that holds even when the construction is allowed to make adaptive queries to the PRG.
(show hidden)

Publication status: Published by the IACR in CRYPTO 2026 First uploaded: , last revision: