Papers updated in last 183 days (Page 19 of 2708 results)

Last updated:  2026-08-13
Fair-Weather No More: Guaranteed Efficiency in Secure Group Messaging
James Bartusek, Nir Bitansky, Yevgeniy Dodis, Rachit Garg, and David J. Wu
Secure group messaging protocols, now standardized by the IETF as Messaging Layer Security (MLS), provide end-to-end encryption for billions of users. The cryptographic core of these protocols is continuous group key agreement (CGKA), a primitive designed to maintain a shared secret among a dynamic group while providing security guarantees like forward secrecy and post-compromise security. A critical challenge for CGKA is achieving efficiency, particularly sublinear complexity (in the size of the group), for group operations. While practical tree-based protocols like TreeKEM offer logarithmic complexity in ideal (so-called "fair-weather") scenarios, their performance degrades to linear in the worst-case, and even realistic average-case, scenarios. This performance collapse raises the fundamental question of whether any CGKA protocol can achieve provably sublinear worst-case complexity. Prior work has established significant barriers to this goal, including black-box impossibility results ruling out efficient constructions from standard public-key encryption. Theoretical solutions circumvent these barriers using powerful tools like indistinguishability obfuscation ($i\mathcal{O}$), but these constructions are astronomically inefficient and often provide weaker security guarantees, such as lacking forward secrecy. This leaves a wide gap between practical protocols with poor worst-case guarantees and theoretical solutions that are entirely impractical. In this paper, we narrow this gap by presenting the first CGKA protocol that achieves provably logarithmic worst-case complexity for both computation and communication. Our first construction is based on a falsifiable and plausibly post-quantum assumption called decomposed learning with errors (decomposed LWE), and achieves basic CGKA security (only group members know the key) and post-compromise security, but not forward secrecy. We then show how to extend our scheme in the random oracle model to achieve optimal security (including forward secrecy) while retaining worst-case sublinear communication. However, the forward-secure refresh operation takes linear time in the group size, while still producing compact ciphertexts. Our work is the first to establish that worst-case efficient CGKA is theoretically possible from simple falsifiable assumptions. Moreover, it offers a plausible roadmap towards concretely efficient constructions.
Last updated:  2026-08-13
SparseMPC: Secure Sparse Operations using Multi-Party Computation
Marc Damie
Multi-party computation (MPC) enables multiple parties to jointly process sensitive data without revealing their inputs. However, existing MPC protocols remain inefficient for high-dimensional sparse data. In plaintext, sparse linear algebra algorithms address this problem using two fundamental primitives, Scatter and Gather. We propose SparseMPC, an outsourced MPC protocol that securely implements Scatter and Gather and uses them to perform sparse matrix multiplication. Our protocol supports an arbitrary number of data owners and provides a low memory footprint, constant round complexity, and low communication cost. Beyond sparse matrix multiplication, SparseMPC provides a foundation for efficiently realizing a broader class of sparse computations in outsourced MPC.
Last updated:  2026-08-13
A Formal Security Proof of Masking: Reduction from Strong Noisy Leakage to Probing Model without Random Probing and Application to LR Primitive
Rei Ueno, Akiko Inoue, Kazuhiko Minematsu, Akira Ito, and Naofumi Homma
This paper provides upper bounds on the success rate (SR) of side-channel attacks (SCAs) on masked implementations. We present a formal security proof of additive masking over any finite abelian group—including Boolean and arithmetic maskings—through new reductions from strong noisy leakage (SNL) to the probing model. Unlike existing proofs relying on noisy leakage (NL) and random probing (RP), our proof introduces a novel security notion named leakage energy (LE), which enables a stronger bound. Our proof reveals the necessary and sufficient condition for asymptotic security of additive masking in both the NL and mutual information frameworks, which includes a resolution to an open problem in TCC 2016. Our claims are validated through numerical evaluations. As an application of our theorems, we propose a binary block-cipher based leakage-resilient primitive based on a variant of XEX, which claims $d$-th order SCA security of arithmetic masking by design under some assumptions, enabling efficient OCB-style authenticated encryption with implementation cost of $O(d)$.
Last updated:  2026-08-13
Verified Pythagorean Composition for Adaptive Cryptographic Games: Noise Flooding in Homomorphic Encryption
Yi Lee, Alexandru Cojocaru, Junyi Liu, and Xiaodi Wu
Noise flooding is a standard defense against decryption attacks on approximate homomorphic encryption, but its security proof is unusually sensitive to composition. Replacing each of \(q\) adaptive decryption answers with a statistically close simulation and applying an ordinary hybrid argument loses linearly in \(q\). The cryptographic proof instead accumulates conditional Kullback-Leibler (KL) costs and converts to statistical distance once, giving the parameter-critical square-root loss. We machine-check this argument using Rocq and SSProve. Given any fully homomorphic encryption scheme that is approximately correct and IND-CPA secure, we formalize a reduction for every \(q\)-query IND-CPAD adversary and prove \[ \Pr[\mathsf{IND\text{-}CPAD}_{\mathsf{NF}}^{\mathcal A}=1] \leq \beta_{\mathsf{CPA}}(\mathcal B_{\mathcal A,q}) + \frac{\sqrt{qn}}{2\gamma}. \] where \(n\) is the plaintext dimension and \(\gamma\) is the flooding-width multiplier. Our proof constructs a new relational program logic over SSProve semantics. Its Pythagorean judgment composes conditional KL budgets without converting them to statistical distance, and a verified trace compiler lifts a local oracle rule to arbitrary adaptive programs with a single final conversion.
Last updated:  2026-08-13
The Grand Challenge of PQC Migration: Analysis of Modern Blockchain and Intertwined Human Egoisms
Kigen Fukuda, Shin’ichiro Matsuo, Yuji Suga, and Tadahiko Ito
Since the invention of Bitcoin in 2008, blockchain technology has evolved from a simple decentralized ledger into a complex, multi-functional financial system spanning multiple layers. Despite this evolution, the cryptographic primitives foundational to this trustless system are now threatened by the emergence of quantum computers. While the necessity of Post-Quantum Cryptography (PQC) migration is widely acknowledged, blockchain remains an extremely challenging domain for cryptographic migration due to its decentralized architecture and long-term security requirements. Today, the evolving complexity has rendered simple cryptographic migration models insufficient at system scale. Furthermore, human factors rooted in economic rationality and intertwined incentives, such as investors’ pursuit of short-term profits and miners’ mining profitability, have emerged as critical obstacles to migration. This paper provides a comprehensive analysis of the challenges and current status of blockchain PQC migration as of December 2025. Specifically, we analyze the components requiring migration and their technical challenges, while systematically organizing operational barriers, including trade-offs found within migration strategies and stakeholder interests. Furthermore, we propose guidelines for future research initiatives that academia and the blockchain community should collaboratively address. By synthesizing ongoing community discussions and existing literature, this work aims to establish a foundation for navigating the path toward achieving quantum-resistant blockchains.
Last updated:  2026-08-12
Anamorphic Messaging: Analyzing the Double Ratchet, Triple Ratchet, PQ3, and MLS
Hien Chu, Alessandro Corsi, and Paul Rösler
Anamorphic cryptography targets the scenario in which a dictator does not forbid the use of cryptography but requires all users to reveal their secret keys to them. Thus, the dictator can decrypt all honestly generated ciphertexts. The approach for bypassing this is to identify spots, such as random nonces, in existing cryptographic protocols in which secret messages can be hidden using an additional secret double key. So far, the literature mostly focused on identifying such spots in simple primitives like public-key encryption or signatures; only recently, an initial work identified limited spots in Signal's Double Ratchet Algorithm. We are the first to leverage the statefulness of cryptographic communication protocols to employ continuously updated double states and, thereby, achieve Forward Security: Even if the adversary (i) observes all traffic, (ii) knows all users' regular secret key material at any stage of the protocol execution, and (iii) at some point learns the secret double state, the entire protocol execution looks benign although covert messages were previously hidden in the traffic anamorphically. We formalize this notion and also cover robustness and authenticity, which appear to be particularly relevant in the messaging context. In this new model, we study four of the most relevant messaging protocols and identify hiding spots therein: Signal's Double Ratchet, Signal's Triple Ratchet, Apple's PQ3, and the two-party core of the Messaging Layer Security Standard. We focus on the cryptographic parts of these protocols and, despite their complexity, identify surprisingly few anamorphic hiding spots. We prove that all these protocols offer forward secure, authenticated anamorphic channels and we evaluate their bandwidths: While 16 bits can be embedded in every epoch of the Double Ratchet, Triple Ratchet and PQ3 provide 176 bits, respectively 256 bits, of bandwidth per post-quantum epoch, and MLS provides 688 bits per epoch.
Last updated:  2026-08-12
RSS: Robust Signing Service using Threshold Signatures and TEEs
Filip Rezabek, Kilian Glas, Eber Christer, Xinxin Fan, and Georg Carle
Threshold signatures reduce the risk of single-key compromise by distributing signing authority, but each key share remains exposed to compromise of the software and infrastructure that execute the protocol. We present RSS, a threshold signing service that runs share generation and signing inside Trusted Execution Environments (TEEs). We integrate GG20 threshold ECDSA, FROST, and threshold BLS into the EnGINE experimentation framework and evaluate local and Google Cloud deployments using AMD SEV-SNP and Intel TDX. Our experiments separate distributed key generation (DKG), preprocessing, and online signing, and cover up to 40 logical protocol participants distributed across four physical hosts or confidential VMs (CVMs). In matched-platform comparisons, confidential execution adds limited overhead relative to protocol and deployment effects. DKG is the main scaling bottleneck: for 40 participants, it completes within seconds in the evaluated configurations, whereas signing completes in tens of milliseconds. Threshold BLS is approximately twice as slow as FROST for comparable values of $n$ and $t$. These results establish the performance feasibility of executing threshold-signature workloads inside CVMs under benign-operation assumptions. The evaluation does not cover a complete attestation-bound provisioning lifecycle, persistent-state rollback protection, or Byzantine fault behavior.
Last updated:  2026-08-12
Zero Knowledge (About) Encryption: A Comparative Security Analysis of Four Cloud-based Password Managers
Matteo Scarlata, Giovanni Torrisi, Matilda Backendal, and Kenneth G. Paterson
Zero Knowledge Encryption is a term widely used by vendors of cloud-based password managers. Although it has no strict technical meaning, the term conveys the idea that the server, who stores encrypted password vaults on behalf of users, is unable to learn anything about the contents of those vaults. The security claims made by vendors imply that this should hold even if the server is fully malicious. This threat model is justified in practice by the high sensitivity of vault data, which makes password manager servers an attractive target for breaches (as evidenced by a history of attacks). We examine the extent to which security against a fully malicious server holds true for four leading vendors who make the Zero Knowledge Encryption claim: Bitwarden, LastPass, Dashlane and 1Password. Collectively, they have more than 60 million users and 23% market share. We present 12 distinct attacks against Bitwarden, 7 against LastPass, 6 against Dashlane and 6 against 1Password. The attacks range in severity, from integrity violations of targeted user vaults to the complete compromise of all the vaults associated with an organisation. The majority of the attacks allow recovery of passwords. We have disclosed our findings to the vendors and remediation is underway. Our attacks showcase the importance of considering the malicious server threat model for cloud-based password managers. Despite vendors’ attempts to achieve security in this setting, we uncover several common design anti-patterns and cryptographic misconceptions that resulted in vulnerabilities. We discuss possible mitigations and also reflect more broadly on what can be learned from our analysis by developers of end-to-end encrypted systems.
Last updated:  2026-08-12
Quantum Advantage for Two-Party Differential Privacy
Daniel Alabi and Emil T. Khabiboulline
We introduce information-theoretically private quantum protocols for two-party Hamming distance when both parties must output the same estimate. Classically, for input length $n$, information-theoretic protocols require $\Omega(\sqrt{n})$ error under pure differential privacy and $\Omega(\sqrt{n}/\log n)$ error under strong approximate differential privacy, whereas computational security permits $O(1)$ error. In Klauck's honest, nonpreemptive, message-preserving model, we give an $O(n)$-communication quantum protocol with pure $\varepsilon$ quantum differential privacy (QDP) and expected error at most $\frac{2}{\sinh \varepsilon}+\gamma,$ for every $\gamma>0$. For approximate $(\varepsilon, \delta)$ QDP, an exact finite-cycle hockey-stick calculation yields strictly smaller error, while preserving the $O(1)$-versus-$\Omega(\sqrt{n}/\log n)$ separation for $\delta=o(1/n)$. Thus, quantum communication achieves $O(1)$ information-theoretic error, matching the accuracy available classically only under computational assumptions. The main construction uses a guarded coherent round trip and an equal-Gram rigidity principle that prevents an honest player from retaining input-dependent complementary information. We also separate this model from weaker prescribed-channel privacy, which already admits an exact classical realization, and from fully retention-robust security, against which measurement-and-abort attacks remain possible. Therefore, we identify preservation of non-orthogonal quantum messages as a resource for privacy, but leave open whether a separation exists in the malicious setting.
Last updated:  2026-08-12
Do You Need a Receipt? Anonymous Credential Revocation at Continental Scale via Private Record Certification
Kasra Edalatnejad, Sebastian Faust, Jonas Hofmann, Philipp-Florens Lehwalder, and Thomas Schneider
A key challenge in digital credential systems is revocation, that is, the ability to revoke credentials post-issuance and verify their status upon presentation. While anonymous credentials enhance privacy over classical credentials (e.g., by providing unlinkability), they complicate revocation. Existing revocation schemes for anonymous credentials often suffer from high client or verifier computation, long delays before revocation takes effect (e.g., epoch-based settings), or require updates to all users with each revocation. We present an efficient, real-time revocation system for anonymous credentials with decentralized revocation authorities based on a novel primitive called Private Record Certification (PRC). PRC enables users to obtain a certificate for a record stored in a server-managed database without the servers learning which record was requested. This primitive is of independent interest, and we construct it by combining techniques from private information retrieval and secure multi-party computation. Our revocation scheme outsources its costs to the revocation authorities and has minimal overhead for clients and verifiers, while ensuring the communication costs are sublinear in the number of credentials for the revocation authorities. We build a prototype and demonstrate that our system achieves sub-second real-time latency at a scale of over 1 billion credentials, with an online operational cost of 2.5$ per server for processing 1 million PRC queries.
Last updated:  2026-08-12
Updatable Oblivious Key Value Stores with Access Control and Application to Multi Key Searchable Encryption
Benjamin Fuller, Ariel Hamlin, Arinjita Paul, Maryam Rezapour, Ronak Sahu, Amey Shukla, and Mason Stuart
Oblivious Key-Value Stores (OKVS) (Garimella et al., CRYPTO 2021), once encoded, provide indistinguishability over keys and random values. This is an important property in many secure computation applications, such as private set intersection and multi-key searchable encryption. We introduce an Updatable Oblivious Key-Value Store with access control (UOKVS), a dynamic extension of OKVS that supports insertions over time. We provide meaningful security in the presence of updates by equipping UOKVS with fine-grained access control. As a building block in UOKVS, we provide the first analysis of oblivious insertions for Cuckoo hashing, which may be of independent interest. We show the application of UOKVS to multi-key searchable encryption where a data owner wishes to share parts of a multimap with multiple clients. We construct an oblivious multimap with insertions from UOKVS and private information retrieval (PIR). Unlike prior multi-key searchable encryption schemes, our construction supports sharing without replicating data across authorized users, substantially reducing storage costs in addition to stronger privacy guarantees. We implement our multi-key searchable encryption construction on a dataset containing up to 24 million entries using the Enron email dataset. For keywords matching 100 documents on a WAN, query processing completes in $0.6$ seconds using FrodoPIR as the underlying PIR protocol. By comparison, the scheme of Wang and Papadopoulos (Cloud Computing 2023) achieves a query time of $0.6$ seconds and also incurs data replication and leaks access patterns. Our construction reduces leakage, maintains performance, and only requires a $3.1$x storage overhead.
Last updated:  2026-08-12
Scalable, quantum-accessible, and adaptive pseudorandom quantum state and pseudorandom function-like quantum state generators
Rishabh Batra, Zhili Chen, Rahul Jain, and YaoNan Zhang
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.
Last updated:  2026-08-12
Lighthouse: Single-Server Secure Aggregation with O(1) Server-Committee Communication at Scale
Sanjam Garg, Alireza Kavousi, Dimitris Kolonelos, Erkan Tairi, and Zhipeng Wang
Secure aggregation is a core primitive for privacy-preserving federated learning, enabling a server to compute aggregates of client updates without learning individual inputs. Recent protocols have explored committee-based designs to reduce client overhead and tolerate weakly connected participants. However, existing approaches still incur communication and computation costs that scale with the number of clients and/or the size of model updates. This becomes a serious bottleneck in interaction between the server and the committee, given that model updates are high-dimensional and the committee is a small set of clients. We present Lighthouse, a new secure aggregation protocol that supports one-shot client communication and achieves constant committee computation and communication overhead with the server, independent of both the number of clients and the size of the input vector. Our protocol attains the best-known round complexity of two rounds, matching OPA (CRYPTO 2025) and TACITA (ePrint 2025) and improving upon Flamingo (IEEE S&P 2023) and Willow (CRYPTO 2025). Our core technical contribution is a novel application of recent advances in batched threshold encryption, which enables succinct server–committee interaction while preserving security and correctness. Beyond asymptotic improvements over prior works, Lighthouse yields substantial concrete efficiency gains: For an aggregation with 1024 clients, we reduce server-to-committee communication by over 100× and committee-to-server communication by over 300× compared to Flamingo and Willow. Also, we present an extension that supports dynamic client participation, a critical requirement for practical deployments at scale, while preserving the asymptotic and concrete efficiency of the static protocol for clients.
Last updated:  2026-08-12
On the Power of Polynomial Preprocessing: Proving Computations in Sublinear Time, and More
Matteo Campanelli, Mario Carrillo, Ignacio Cascudo, Dario Fiore, Danilo Francati, and Rosario Gennaro
Cryptographic proof systems enable a verifier to be convinced of a computation's correctness without re-executing it; common efficiency requirements include both succinct proofs and fast verification. In this work we put forth the general study of cryptographic proof systems with \textit{sublinear} proving time (after a preprocessing). Prior work has achieved sublinear proving only for limited computational settings (e.g., vector commitments and lookup arguments), relying on specific assumptions or through non-black-box use of cryptographic primitives. In this work we lift many of these limitations through the systematic study of a specific object: polynomial commitments (PC) with sublinear proving time, a choice motivated by the crucial role that PC play in the design of efficient cryptographic schemes. We show a simple construction of a PC with sublinear prover based on any vector commitment scheme (VC) and any preprocessing technique for fast polynomial evaluation. We prove that this PC satisfies \emph{evaluation binding}, which is the standard security notion for PC, but show it does not satisfy stronger notions of security. Next, we study applications of PCs with sublinear prover. The first one is to construct \emph{index-efficient} SNARKs, i.e., where the prover is sublinear, after preprocessing, in the size of the index (i.e., the NP-relation describing the proven statement). We propose a method to transform a class of standard Polynomial Interactive Oracle Proofs (PIOPs) into index-efficient PIOPs, obtaining two results that advance the state of the art: the first lookup argument for unstructured tables in which the prover is sublinear in the size of the table, while making only black-box use of a VC and thus allowing instantiations from generic assumptions such as collision-resistant hash functions, and the first transparent SNARK for circuits where the prover is sublinear in the number of addition gates. Finally, our last application is a transformation that builds \emph{UC-secure} SNARKs from simulation-extractable ones, with an approximately linear overhead in proving time (as opposed to quadratic in prior work).
Last updated:  2026-08-12
Vela and Carina: Fast Pairing-Based Multilinear Polynomial Commitments from Reciprocal Polynomials
Yuncong Zhang
Pairing-based multilinear polynomial commitments offer succinct verification for sum-check-based proof systems, but existing schemes trade prover work against proof size and verifier cost. Building on Mercury's representation of a multilinear evaluation as the constant coefficient of a (reciprocal) Laurent polynomial, we construct two schemes with different performance trade-offs. Vela uses inversion symmetry to derive a half-length auxiliary polynomial and opens two polynomials at $z$ and $z^{-1}$ with one univariate KZG proof. Vela has a $2\mathbb{G}_1+3\mathbb{F}$ proof, a two-term pairing check, and approximately $2N$ opening MSM scalars, at the cost of $O(N\log N)$ field operations on the prover side. Carina applies the same constant-term reduction once in each coordinate and jointly proves evaluation claims for the committed bivariate polynomial and two auxiliary polynomials with one opening at four bivariate points. The four points form a grid, allowing Carina to restructure the opening equation to save verifier works and proof size. Carina has a $4\mathbb{G}_1+8\mathbb{F}$ proof, a three-term pairing check, and $O(N)$ field operations plus exactly $N+2\sqrt{N}-6$ MSM works on the prover side. We prove perfect evaluation completeness, computational commitment binding, and knowledge soundness in the AGM and ROM, with explicit random-oracle error bounds under a falsifiable bilinear $q$-type DLOG assumption. Our curve-generic Rust implementation also provides common implementations of six pairing-based baselines. On BLS12-381 at $\mu=20$, Vela gives the smallest measured proof (200 bytes, 1.88x smaller than the next smallest) and the lowest verification median, 2.06 ms. Carina's opening median remains in the same leading tier as the prover-oriented mKZG and CHOPIN implementations, while its 452-byte proof and 2.67 ms verification median improve on both. Compared with the verifier-oriented Mercury, Carina's opening median is 1.96x faster at the cost of a 0.48 ms verification slowdown.
Last updated:  2026-08-12
Rate-Limiting Nullifiers for Gasless Sequencer Admission in Ethereum Layer-2 Rollups
Uğur Şen, Sergei Tikhomirov, Sylvain Delhomme, Nadeem Bhati, and Cyprien Grau
Blockchain networks rely on transaction fees for resource allocation and spam prevention. Ethereum's gas mechanism and its adoption by Layer-2 rollups serve this dual purpose, but gas-based fee markets produce unintended consequences: ineffective spam deterrence at low fee levels, poor user experience, privacy leakage, and revenue instability for rollup operators. We present an idealized protocol architecture for gasless sequencer admission in Ethereum Layer-2 rollups based on Rate-Limiting Nullifiers (RLN) and a non-transferable reputation token (Karma). Users transact within a per-epoch gasless quota. Transactions beyond that quota use a gas-paid overflow path. RLN enforces the quota via zero-knowledge membership proofs, preserving pseudonymity for users within quota against on-chain observers while exposing violators through reputation slashing. We present the architecture and transaction flow, analyze spam-attack economics through a parameterized cost comparison on a flat per-identity quota model (labeled flat-$N$, an analysis model for the spam stress test), and describe Status Network (SN), a deployed Ethereum L2 that implements this design.
Last updated:  2026-08-12
Asymmetric Message Franking in the Plain Model: Generic and Efficient Constructions
Milan Gonzalez-Thauvin and Keitaro Hashimoto
Asymmetric Message Franking (AMF), proposed by Tyagi et al. at Crypto’19, is a sort of signature scheme that aims to provide privacy-preserving content moderation in secure messaging applications. In this work, we present the first generic construction of AMF using a public-key encryption scheme, a signature scheme, and a ZAP proof system for NP languages. This construction yields the first AMF scheme provably secure in the plain model from standard assumptions, and has tight security. To improve the efficiency of AMF in the plain model, we build a concrete scheme from asymmetric pairing groups based on our idea for the generic construction. It achieves a signature size of 47 group elements, which is significantly smaller than an instantiation of the generic construction. Also, we provide a variant of the generic construction that yields a post-quantum secure AMF scheme in the plain model from a polynomially hard LWE assumption, demonstrating its feasibility.
Last updated:  2026-08-12
Five-Bit Axial Subspace Differential Uniformity: Exact Optima and a DDT-Support Realizability Gap
Jingchuan Ma, Yuqing Shao, Xin Wei, and Qiaoyun Huang
Subspace differential uniformity (SDU) measures the concentration of a differential distribution table (DDT) on affine subspaces. We determine the exact optima of the two axial affine-SDU coordinates in dimension five and establish a strict gap between locally admissible support designs and supports realizable by almost perfect nonlinear (APN) permutations. We first prove that every $16$-subset of $\mathbb{F}_2^5$ meets some affine $3$-flat in at least six points. Equality holds precisely for balanced quadratic indicators of polar rank four, forming a single affine orbit represented by $\operatorname{supp}(\operatorname{Tr}(x^3))$. This gives the relaxed axial optimum $12$. We then classify all $900$ ordered monomial-trace candidates $M_{r,s}(u,v)=\operatorname{Tr}(u^r v^s)$: exactly $100$ attain both relaxed axial optima, yielding $20$ labelled arrays and three product-linear types up to transpose. Despite satisfying regularity and zero-vector-sum constraints, every optimal type violates a global necessary condition for DDT realizability: its two-dimensional character transform contains a negative coefficient where a vectorial Walsh square is required. Finally, the published exhaustive affine classification of five-bit APN permutations, together with direct recomputation of all five class representatives, gives realizable axial minimum $14$, attained simultaneously by the $x^{15}$ class. Thus local incidence and vector-sum constraints permit score $12$, whereas genuine APN-permutation DDT supports require score $14$.
Last updated:  2026-08-12
MKA Meets Multidrop: Optimizing Time-to-Key-Agreement on 10BASE-T1S Ethernet
Jonathan Ndop, Isaac Molina, Guillermo Oliver, Friedrich Wiemer, and Axel Sikora
The MACsec Key Agreement protocol, defined in IEEE 802.1X, manages and distributes ephemeral Secure Association Keys for Ethernet links protected with MAC security (IEEE 802.1AE). Prior work has shown that baseline MKA may scale poorly on shared medium Ethernet multidrop links and that formal worst-case bounds significantly exceed automotive startup targets, motivating alternative solutions such as In-line Key Agreement. However, in practice, to preserve compatibility, integration effort, and alignment of standardization, automotive systems are more likely to optimize a MACsec/MKA architecture than to completely replace it. This paper presents novel automotive MKA optimizations targeting secure startup times on shared medium networks and evaluates them through detailed network simulations. Unlike previous work focused on baseline MKA or deterministic worst-case analysis, we study the full startup-time distribution of the optimized protocol under realistic startup scenarios. We quantify the effect of the proposed optimizations on Time-To-Key-Agreement and show how the resulting empirical distributions can be translated into conservative simulation-derived practical startup-time bounds suitable for OEM timing budgets. The resulting bounds are intended as simulation-derived engineering bounds under the modeled startup assumptions, complementing formal worst-case analysis with distributional information on typical, tail, and upper-end behavior.
Last updated:  2026-08-12
SwitchFold: Code-Agnostic Succinct Polynomial Commitments via Recursive Code Switching
Mingshu Cong, Tsz Hon Yuen, and Siu-Ming Yiu
We study hash-based polynomial commitment schemes (PCSs) over large prime fields that scale to witnesses containing billions of scalars. Such PCSs are important for emerging data-science-related applications of zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs). Our goal is to reduce prover time while preserving polylogarithmic proof size and verifier time. To this end, we seek code agnostic, succinct PCS constructions that can be instantiated with any linear code over any target field, allowing the most efficient code for the chosen field to be selected. Our SwitchFold construction achieves polylogarithmic verification by recursively applying the code-switching technique between codes of decreasing block lengths. Prior code-switching PCSs switch from an unstructured code to a foldable code; in contrast, SwitchFold requires no code foldability and thus decouples PCS design from code design. For a polynomial of size N and security parameter λ, instantiating SwitchFold with linear-time encodable codes yields O(N) prover time and O(λ log^2 N) proof size and verifier time. We instantiate SwitchFold with the Brakedown codes (Golovnev et al., CRYPTO ’23) and the recently proposed quasi-Abelian (QA) codes (Li et al., IACR ePrint ’26), yielding BrakeFold and QAFold, respectively. At N = 2^30, QAFold achieves the fastest prover time among all evaluated PCSs with succinct verification. Compared with TensorSwitch (Bünz et al., IACR ePrint ’25), the other code-agnostic PCS, QAFold reduces total and marginal prover time by factors of 2.2× and 2.7× under the same QA-code instantiation. With Brakedown codes, BrakeFold reduces the marginal prover time per additional opening by a factor of 2.9× relative to TensorSwitch.
Last updated:  2026-08-11
On the Limits of Consensus under Dynamic Availability and Reconfiguration
Javier Nieto, Joachim Neu, and Ling Ren
Proof-of-stake blockchains require consensus protocols that support Dynamic Availability and Reconfiguration (which we call the DAR model). Here, Dynamic Availability means that the consensus protocol should remain live even if a large number of nodes temporarily crash, and Reconfiguration means it should be possible to change the set of operating nodes over time. State-of-the-art protocols inspired by the DAR model, such as Ethereum, Cardano's Ouroboros, or Snow White, require additional model features comprising external mechanisms or node capabilities that are difficult to justify, such as social consensus or the requirement that key evolution be performed even when nodes have crashed. The key result of this paper is the necessary and sufficient adversarial condition under which consensus can be achieved in the plain DAR model, without any extra features. We then introduce an additional feature to the model that is justified by proof-of-stake blockchain designs: honest nodes complete a sign-off procedure the moment they express intent to exit from the set of operating nodes. This additional feature reduces the power of the adversary relative to the plain DAR model and helps us obtain a bootstrapping gadget that is particularly simple and efficient in the common optimistic case of few reconfigurations and no double spending.
Last updated:  2026-08-11
Breaking the Beyond-Birthday-Bound Security of $\sharp\textsf{Pencil}$
Léonard Assouline and Cécile Delerablée
$\sharp\textsf{Pencil}$ is a domain-extended pseudorandom function by Bhaumik et al, accepted at CRYPTO 2026, claiming that it achieves close to $n$-bit security beyond the birthday bound. It is used as the key-derivation layer of the $\sharp\textsf{Pencil}$-CAU authenticated-encryption mode. We show that $\sharp\textsf{Pencil}$ has a birthday-bound collision attack: its front end $\textsf{Sharp}$ compresses the second half $N_2$ of the input through the $(n-8)$-bit value \[ J(N_2) = \operatorname{msb}_{n-8}\bigl({\mathsf{E}}_{K_1}(N_2 || \texttt{0x00})\bigr), \] after which the entire computation is a deterministic function of $(N_1,J)$. Thus, for any fixed $N_1$, distinct values $N_2,N_2'$ satisfying $J(N_2)=J(N_2')$ produce identical $\sharp\textsf{Pencil}$ outputs. Such collisions occur with probability $1-e^{-1}$ after $2^{(n-7)/2}$ queries, $2^{60.5}$ when $n=128$. This yields a PRF distinguisher with constant advantage, contradicting the security bound of Theorem 4. Since $2^{60.5}$ falls below the birthday bound $2^{n/2}$ that the construction was designed to pass, the beyond birthday-bound property does not hold. Given the derived key $K_1$, an explicit collision can be constructed in approximately $10^3$ inverse-cipher evaluations in expectation. The same collision breaks $\sharp\textsf{Pencil}$-CAU, as two nonce-respecting queries can reuse the key and the nonce of the inner GCM instance, yielding the difference of the two plaintexts. The first version of the paper does not have the defect: it left $J$ untruncated, which makes the map injective and invalidates the collisions above. Reverting to it is the remedy we suggest.
Last updated:  2026-08-11
Frontdoors, Not Backdoors: Accountable Anonymity for National Digital Identity
Shailesh Mishra, Roxanne Chevalley, Martin Burkhart, and Bryan Ford
Anonymous credentials (ACs) let users prove identity claims with strong privacy guarantees, and national systems built on them $-$ EUDI and the Swiss e-ID $-$ go live soon. Due to these guarantees, however, AC systems cannot detect proof proxy attacks, where malicious users "lend" their identity by presenting their credentials on behalf of other users, exposing a fundamental gap between privacy and accountability. For instance, users could sell anonymous legal age proofs online and get away with it. This lack of accountability will act as an obstacle for AC adoption on grounds of "national safety", as exemplified by the recurring push towards chat control in the EU. Consequently, issuing authorities may well settle for less-than-ideal privacy guarantees of current solutions (e.g., batch issuance of one-show credentials). In this paper, we advocate the need for integrated accountability in ACs and introduce the cryptographic forensic trail (CFT). A CFT is a randomized encryption of a user's identity that they produce alongside each credential presentation; only when credential misuse, e.g., a proof proxy attack, is detected can the CFT be decrypted for accountability. The design of CFT is based on a legal process requiring probable cause for anonymity revocation. It enforces separation of powers between law enforcement, a judicial body, and a digital privacy advocate (NGO) using privacy-enhancing technologies. The protocol mimics checks and balances of a healthy democracy, in which neither law enforcement nor justice can track people as they will. Even if both branches colluded, the NGO can detect the misuse and block further use. We implement a prototype of CFT based on both hardware-compatible and zero-knowledge-friendly elliptic curves. Our evaluations show that CFT adds only $13-16\%$ computation overhead to credential shows on the user's end, indicating that deployment in smartphone wallets is within reach.
Last updated:  2026-08-11
Upper bounds for failure probabilities of reductions from low density subset sum problems to lattice problems on linearly independent vectors
Shoichi Kamada
As a new lattice problem, we introduce $l$-Shortest Independent Vectors Problem ($l$-SIVP for short), where $l$ is a positive integer no greater than the rank of a lattice. In the case where $l=1$, $l$-SIVP means SVP, and in the case where $l$ is the rank of a lattice, $l$-SIVP means SIVP. We estimate upper bounds on the failure probabilities of the reductions from the subset sum problems to the $l$-SIVPs in terms of Ehrhart theory. Especially, in the case of $l=1$, our upper bound is tighter than the previous result given by Coster et al. We give some considerations for dominating terms of our upper bounds of failure probabilities when $l$ is general.
Last updated:  2026-08-11
Message Injection Attacks Against Signal
Kien Tuong Truong, Noemi Terzo, and Kenneth G. Paterson
Signal is a secure messaging app offering end-to-end security for pairwise and group communications. It has tens of millions of users, and has heavily influenced the design of other secure messaging apps (including WhatsApp). Signal has been heavily analysed and, as a result, is rightly regarded as setting the "gold standard" for messaging apps by the scientific community. We present two practical attacks that break the integrity properties of Signal in its advertised threat model. Each attack arises from different features of Signal that are poorly documented and have eluded formal security analyses. The first attack, affecting Android and Desktop, arises from Signal's introduction of identities based on usernames (instead of phone numbers) in early 2022. We show that the protocol for resolving identities based on usernames and on phone numbers introduced a vulnerability that allows a malicious server to inject arbitrary messages into one-to-one conversations under specific circumstances. The injection causes a user-visible alert about a change of safety numbers, but if the users compare their safety numbers, they will be correct. The second attack is even more severe. It arises from Signal's Sealed Sender (SSS) feature, designed to allow sender identities to be hidden. We show that a combination of two errors in the SSS implementation in Android allows a malicious server to inject arbitrary messages into both one-to-one and group conversations. The errors relate to missing key checks and the loss of context when cryptographic processing is distributed across multiple software components. The attack is undetectable by users and can be mounted at any time, without any preconditions. As far as we can tell, the vulnerability has been present since the introduction of SSS in 2018. We disclosed both attacks to Signal. The vulnerabilities were promptly acknowledged and patched: the first vulnerability was fixed two days after disclosure, while the second one was patched after eight days. Beyond presenting these devastating attacks on Signal's end-to-end security guarantees, we discuss more broadly what can be learned about the challenges of deploying new security features in complex software projects.
Last updated:  2026-08-11
BitVM: Quasi-Turing Complete Computation on Bitcoin
Lukas Aumayr, Zeta Avarikioti, Robin Linus, Matteo Maffei, Andrea Pelosi, Christos Stefo, and Alexei Zamyatin
A long-standing question in the blockchain community is which class of computations are efficiently expressible in cryptocurrencies with limited scripting languages, such as Bitcoin Script. Such languages expose a reduced trusted computing base, thereby being less prone to hacks and vulnerabilities, but have long been believed to support only limited classes of payments. In this work, we confute this long-standing belief by showing for the first time that arbitrary computations can be encoded in today's Bitcoin Script without introducing any language modification or additional security assumptions, such as trusted hardware, trusted parties, or committees with an honest majority. We present BitVM, a two-party protocol that realizes a generic virtual machine by combining cryptographic primitives and economic incentives. We conduct a formal analysis of BitVM, characterizing its functionality, system assumptions, and security properties. We further demonstrate the practicality of our approach by implementing a prototype and performing an experimental evaluation: in the optimistic case (i.e., when parties agree), our protocol requires just three on-chain transactions, whereas in the pessimistic case, the number of transactions grows logarithmically with the size of the virtual machine. We exemplify the deployment potential of BitVM by building a Bitcoin-sidechain bridge application. This work not only solves a long-standing theoretical problem, but it also promises a strong practical impact, enabling the development of complex applications in Bitcoin.
Last updated:  2026-08-11
Aborting Random Oracles: How to Build them, How to Use them
Gottfried Herold, Dmitry Khovratovich, Mikhail Kudinov, Stefano Tessaro, and Benedikt Wagner
In this work, we initiate the study of aborting hash functions, i.e., hash functions that may abort on a non-negligible fraction of inputs. We introduce the aborting random oracle model (aROM), an idealized framework that extends the standard random oracle model (ROM) to account for aborts. Within this model, we derive bounds for various security notions and establish generic indifferentiability results demonstrating how to construct aborting random oracles from standard ones. Consequently, the derived bounds ultimately hold in the standard ROM. In this way, the aROM and its associated bounds provide a convenient and easy-to-use framework for analyzing cryptographic constructions that rely on potentially aborting hash functions. To illustrate the utility of our framework, we apply our techniques to two settings: (1) the analysis of SNARK-friendly incomparable hypercube encodings, a core primitive in hash-based signature schemes, and (2) the analysis of grinding in Fiat–Shamir-based non-interactive arguments. Through our generic indifferentiability results, we can easily translate these analyses into concrete security bounds in the standard (non-aborting) random oracle model.
Last updated:  2026-08-10
Lumora: A Family of Permutation-Based Wide-Block Ciphers for Post-Quantum zkSNARK Applications
Susanta Samanta, Martin Grenouilloux, Guang Gong, and Chunlei Li
The deployment of advanced cryptographic protocols such as zero-knowledge proofs (ZKPs) requires symmetric primitives optimized for fast verification inside proof systems. In frameworks based on Rank-1 Constraint Systems (R1CS), prover performance and proof size are dominated by the cost of arithmetization, specifically, by the number of nonlinear multiplication constraints. Traditional bit-oriented designs are typically inefficient under this metric. In this paper, we introduce Lumora, a family of arithmetization-oriented, permutation-based wide-block ciphers designed for efficient use inside zkSNARK circuits and for applications in post-quantum digital signatures. Each instance of Lumora follows a unified AES-like SPN structure defined over the binary extension field $\mathbb{F}_{2^n}$ for $n \in \{16,32,64\}$. The underlying permutation is instantiated as a block cipher via the Even-Mansour paradigm, which eliminates the R1CS constraint overhead of a separate key schedule, ensuring the prover's workload remains strictly focused on evaluating the public permutation. Finally, we provide a detailed security analysis of the Lumora family, together with implementation results and a comparison within the FAEST-EM-256 framework.
Last updated:  2026-08-10
On the Security of In-band Verification in End-to-End Encrypted Video Calls
Daniel Jones, Melissa Chase, Esha Ghosh, and Kim Laine
Video conferencing software, including Zoom, Microsoft Teams, and Cisco Webex, use human-driven key verification ceremonies to protect end-to-end encrypted meetings against a potentially malicious service provider. The client software shows each participant a code that they must compare; if the codes match, the call is considered secure. Prior security analyses assumed authenticated out-of-band channels for the comparison, but this is generally unrealistic. The codes are short-lived, so the ``in-band'' channel being verified is, itself, the most natural one to use. We seek to understand the implications of this common practice, asking whether it can be secure and under what conditions. To this end, we formalize the notion of a Human-to-Human Group Key Agreement protocol, modeling an authenticated group key exchange between people, rather than their cryptographic keys. We identify that the security of these protocols relies on the pre-existing capacity of people to consistently recognize one another, avoiding any global identification scheme or trusted external infrastructure. We present a construction, prove it secure in our model, derive concrete bounds, and discuss non-examples demonstrating the definition's subtlety. Our results highlight the approach's usability issues and reliance on unforgeability of human-authenticated video streams---an assumption additionally challenged by recent advances in deepfakes.
Last updated:  2026-08-10
Single-Server Verifiable PIR with Updates and Universally Composable Security
Julia Guskind, Ariel Hamlin, Ryan Little, Daniel S. Roche, and Mayank Varia
Private information retrieval (PIR) is a fundamental cryptographic primitive that allows a client to retrieve an entry of a database from a server without revealing which entry was retrieved. PIR security is traditionally defined with a distinguishing game that ensures the clients' access patterns are kept private from a semi-honest server. Verifiable PIR (VPIR) adds another game-based property that holds against a malicious server: the server is bound to a particular database and cannot cause a client to retrieve a database entry that is inconsistent with this database. Recent work by Alon and Beimel [ITC 2025] deviated from the traditional game-based PIR definitions and contributed a definition of standalone simulation-based security for multi-server PIR. Their techniques, however, do not readily extend to single-server VPIR and do not consider concurrent protocol composition when PIR is used as a building block within a larger application. In this work, we further the study of simulation-based VPIR security. We are the first to formalize a universally composable (UC) definition of VPIR in the single-server setting by giving an ideal VPIR functionality. We motivate the need for UC security by showing how game-based VPIR properties fail under sequential and concurrent protocol composition. We also demonstrate the generality of our UC VPIR functionality by providing two realizations based on a trivial PIR and VeriSimplePIR [de Castro and Lee, USENIX Security 2024]. Additionally, we introduce a new kind of VPIR, called Updatable VPIR (UVPIR), which guarantees to clients that (1) database updates are authorized by permissioned clients and (2) responses to their queries are consistent with a specific version of the PIR database. We show that UVPIR can be constructed in a black-box manner on top of any VPIR protocol.
Last updated:  2026-08-10
Large smooth twins from short lattice vectors
Erik Mulder, Bruno Sterner, and Wessel van Woerden
Finding the largest pair of consecutive $B$-smooth integers for a fixed value of $B$, also called a $B$-smooth twin, is computationally challenging. It has only been provably done for $B \leq 100$ and heuristically for $100 < B \leq 113$. We improve this by detailing a new algorithm to find such smooth twins. The core idea is to solve the shortest vector problem (SVP) in a well-constructed lattice. Using a heuristic about smooth numbers in short intervals, we give an estimate of the size of the largest smooth twin for a given $B$. We are able to significantly increase $B$ and notably report the heuristically largest twin with $B = 751$, which has $196$ bits. By slightly modifying the lattice, we are able to find even larger twins, but the resulting smoothness bound will not always be optimal. This notably includes a $213$-bit twin with $B = 997$, which is the largest twin found in this work.
Last updated:  2026-08-10
InsPIRe: Communication-Efficient PIR with Server-side Preprocessing
Rasoul Akhavan Mahdavi, Sarvar Patel, Joon Young Seo, and Kevin Yeo
We present InsPIRe that is the first private information retrieval (PIR) construction simultaneously obtaining both high-throughput and low query communication while using silent preprocessing (meaning no offline communication). Prior PIR schemes with both high-throughput and low query communication required substantial offline communication of either downloading a database hint that is 10-100x larger than the communication cost of a single query (such as SimplePIR and DoublePIR [Henzinger et al., USENIX Security 2023]) or streaming the entire database (such as Piano [Zhou et al., S&P 2024]). In contrast, recent works such as YPIR [Menon and Wu, USENIX Security 2024] avoid offline communication at the cost of increasing the query size by 1.8-2x, up to 1-2 MB per query. Our new PIR protocol, InsPIRe, obtains the best of both worlds by obtaining high-throughput and low communication without requiring any offline communication. Compared to YPIR, InsPIRe requires 5x smaller cryptographic keys, requires up to 50% less online query communication while obtaining up to 25% higher throughput. We show that InsPIRe enables improvements across a wide range of applications and database shapes including the InterPlanetary File System and private device enrollment. At the core of InsPIRe, we develop a novel ring packing algorithm, InspiRING, for transforming LWE ciphertexts into RLWE ciphertexts. InspiRING is more amenable to the silent preprocessing setting that allows moving the majority of the necessary operations to offline preprocessing. InspiRING only requires two key-switching matrices whereas prior approaches needed logarithmic key-switching matrices. We also show that InspiRING has smaller noise growth and faster packing times than prior works in the setting when the total key-switching material sizes must be small. To further reduce communication costs in the PIR protocol, InsPIRe performs the second level of PIR using homomorphic polynomial evaluation, which only requires one additional ciphertext from the client.
Last updated:  2026-08-10
Lattice-Based Rate-Limited Tokens in the Random Oracle Model
Victor Youdom Kemmoe, Anna Lysyanskaya, and Ngoc Khanh Nguyen
An anonymous credential allows a user to prove that she is authorized in an anonymous and unlinkable fashion. A rate-limited token is an anonymous credential that can only be used a limited number of times in any particular context; this means that even though we do not know which users are gaining access to a resource, there is a limit to how many resources one user may consume. Such tokens are becoming an increasingly attractive way to balance privacy with authorized access. Although a general architecture for how to obtain rate-limited tokens from digital signatures, pseudorandom functions (PRFs), and non-interactive zero-knowledge proofs (NIZKs) has been known for over twenty years, efficiently instantiating it with post-quantum-secure signatures and proofs has, until now, remained an open problem. In this work, we present the first lattice-based construction of rate-limited tokens and tackle the practical challenges associated with using lattice-based building blocks in this setting. A central difficulty lies in the absence of lattice-based PRFs that support efficient NIZK proofs of correct evaluation. We show that, in the random oracle model, a weak PRF—where adversaries are restricted to querying random inputs—suffices. We further present a weak PRF construction that both admits efficient NIZK proofs and remains secure—even when adversaries have partial control over the randomness—and extend this guarantee more generally to key-homomorphic PRFs. Another contribution, which is of independent interest, is the first lattice-based construction of partially binding commitments, a primitive introduced by Goel et al. (Eurocrypt 2022) that was previously known only under discrete-log assumptions. We give a practical construction that enables succinct disjunctive proofs via a variant of the self-stacking compiler of Goel et al. Along the way, we develop a new technique for batching CNF proofs of $\Sigma$-protocols, which allows one to efficiently prove that a value is the output of a PRF on one of a set of inputs. As a direct application, this yields logarithmic-size lattice-based ring signatures based on Fiat–Shamir-with-Aborts $\Sigma$-protocols (Lyubashevsky, Eurocrypt 2012). Finally, we observe for the first time that the anonymous counting tokens of Benhamouda, Raykova, and Seth (Asiacrypt 2023) can be obtained from anonymous rate-limited tokens. This yields a construction whose communication complexity is independent of the number of tokens that need to be issued.
Last updated:  2026-08-10
General versus linear secret sharing under statistical security
Shahram Khazaei
How few participants are needed before general secret-sharing schemes can outperform linear ones under a fixed security notion? Under statistical security, we show that the answer is five participants; under perfect security, the corresponding threshold remains unknown. It is known that the \(157\) connected access structures on five participants split into \(140\) Shannon-exact cases and seventeen exceptional cases. For the former, linear schemes attain the Shannon polymatroid region; for each of the latter, the exact linear contribution region is the all-pairs one-common-information region and is strictly smaller than the Shannon region. We investigate the statistical contribution regions of these seventeen exceptional structures. For fifteen of them, we construct a partial scheme whose contribution vector lies outside the exact linear region; Jafari--Khazaei's partial-to-statistical transfer then gives a statistically secure family with the same asymptotic vector. One dual pair remains open. For \(\Gamma_{30}\), we further show that the maximum information ratio under statistical security lies in \([14/9,1.6502)\), improving both previously established bounds; moreover, \(1.6502<5/3\), where \(5/3\) is the optimum for linear schemes.
Last updated:  2026-08-10
Improved Codes and Decoders for HQC
Sebastian Bitzer, Bharath Purtipli, and Antonia Wachter-Zeh
The Hamming Quasi-Cyclic (HQC) cryptosystem, recently selected by NIST for standardization, uses a concatenation of Reed-Muller (RM) and Reed-Solomon (RS) codes to ensure correct decryption. This work optimizes the underlying code and decoder with the goal of reducing ciphertext and public-key sizes. First, we propose a two-level generalized concatenated code (GCC), exploiting the observation that the inner RM code contains a repetition subcode. The repetition layer incurs a smaller inner failure probability and, therefore, admits a higher code rate than the RS code. Second, we develop a reliability-based decoding framework for the outer code. The inner decoder provides a reliability measure whose distribution, jointly with the decoding outcome, is bounded analytically. These bounds allow deriving conservative DFR guarantees for two erasure-assignment strategies (threshold-based and partition-based). Combining both contributions, we observe that public-key and ciphertext sizes can be reduced by up to 4.34%.
Last updated:  2026-08-09
Recursive Common Information for Group-Characterizable Random Variables
Shahram Khazaei
Common information (CI) is useful in entropy-based lower bounds for secret sharing. We study CI for group-characterizable (GC) random variables. Building on the sufficient condition of Kaboli--Khazaei--Parviz, we prove an exact pair criterion: two coset random variables $X_H$ and $X_K$ have common information if and only if the subgroups $H$ and $K$ permute, that is, $HK=KH$. Consequently, a GC tuple is $1$-CI exactly when every pair of subgroups in the meet closure of its labels permutes, whereas it is recursively CI exactly when every pair in the generated subgroup sublattice permutes. This also gives a finite algorithm for deciding recursive CI, and we exhibit a GC tuple over $S_3\times S_3$ that is $1$-CI but not $2$-CI. Since normal subgroups satisfy the recursive criterion, homomorphic random variables are recursively CI. For the twelve-participant disjoint Fano--non-Fano access structure, the Shannon lower-bound method with all separate $1$-CI extensions still gives maximum and average optima equal to one. Two depth-two recursive CI extensions instead give the lower bounds $43/41$ and $54089/51756\approx1.04508$ for the maximum and average information ratios of perfect homomorphic schemes. The same bounds hold for Abelian schemes; the exact mixed-linear and linear values are already known.
Last updated:  2026-08-09
SoK: Encrypted Mempools Through the MEV Lens
Jonathan Passerat-Palmbach
MEV and censorship, fuelled by public mempool visibility, remain existential threats to Ethereum and have recently started to spread to its layer-two ecosystem. Encrypted mempools promise to conceal transaction content until ordering is final. While this sounds appealing, their viability rests on cryptographic, economic, and deployment trade-offs. This paper systematises the evolution of threshold-encrypted mempools, from early schemes such as Shutter and Ferveo to the most recent research, and analyses how successive iterations have resolved bottlenecks like committee communication overhead, lack of pending transaction privacy, and position-dependent encryption. We highlight a convergence along four design axes, namely batched decryption to mitigate latency, silent setup to eliminate the complexity of distributed key generation, epochless encryption to remove position dependency, and collision-free encoding to prevent slot-collision censorship. We further survey the active Ethereum deployment debate, including EIP-8105 and the LUCID headliner submission, and map the requirements raised there onto the cryptographic corpus. We conclude by exposing a critical limitation common to all current proposals: blind ordering and binary decryption together suppress not only the toxic part of MEV that motivated encrypted mempools, but also the same-block auction mechanisms that return value to users and sustain geographic decentralisation of the network.
Last updated:  2026-08-09
Improved Garbled RAM via Garbled Merge
Can Liu, Lenny Liu, Ning Luo, and David Heath
Consider the problem of merging inside a garbled circuit (GC) two arrays of $w$-bit elements, yielding a single length-$n$ array. This garbled merge problem is core to garbled random access memory (GRAM), a technique that enables efficient garbling of general-purpose programs. We present a novel symmetric-key-based garbled merge that achieves a garbling size of $(w + 1) \cdot n \cdot \lambda$ bits, providing both asymptotic and concrete improvements over the state of the art. By applying our garbled merge, we obtain a symmetric-key GRAM of size $O(n \lg^3 n \cdot \lambda) \cdot \omega(1)$ for a word RAM program that manipulates words of size $\Theta(\lg n)$ bits and halts within $n$ steps, improving over the previous best result (Heath et al., CRYPTO'23) by an $O(\lg \lg n)$ factor. This communication cost was previously only achieved under the public-key-style DDH assumption (Gu et al., CRYPTO'25). We implement our construction, and our evaluation shows that our garbled merge reduces the communication cost over the DDH-based merge by about $3\times$.
Last updated:  2026-08-09
Retrieve-Compute PIR and Its Applications
Benny Applebaum and Shahar Shechter
Two-server Private Information Retrieval achieves arbitrarily small polynomial communication, but relies on a strong non-collusion assumption that is difficult to justify in practice. We introduce a new variant of two-server PIR in which one server acts as a standard \emph{compute} server, while the other is a restricted \emph{retrieval-only} server. The latter stores a public encoding of the database and merely serves requested symbols or blocks of this encoding, without performing any PIR-specific computation. We argue that such a retrieval-only server can be instantiated using existing static-content or repository-hosting services, thereby grounding the non-collusion assumption in realistic architectural and deployment constraints. Assuming Learning Parity with Noise (LPN) over the ternary field with inverse-polynomial noise rate, we construct RC-PIR with arbitrarily small polynomial communication and polynomial storage. Leveraging this construction, we derive the following unexpected applications for every constant \(k\): \begin{enumerate} \item \(k\)-server PIR with arbitrarily small polynomial communication and privacy against any coalition of \(k-1\) servers. \item \(k\)-server robust PIR with arbitrarily small polynomial communication that simultaneously achieves correctness and privacy with respect to an arbitrary monotone access structure \(\mathcal{A}\). Namely, correctness is guaranteed whenever the set of online servers \(S\) satisfies \(S \in \mathcal{A}\), while privacy holds against every coalition \(S \notin \mathcal{A}\). \item A \(k\)-party secure computation protocol for size-\(n\) truth tables also known as lookup tables, with arbitrarily small polynomial communication and passive security against any coalition of \(k-1\) parties. This result extends to active security either in the honest-majority setting, or without an honest majority assuming collision-resistant hash functions. \end{enumerate} None of these results were previously known under the LPN assumption. Along the way, we uncover new relationships between different complexity measures of PIR.
Last updated:  2026-08-09
Structural Tightness of Quadratic Multi-Query Bounds for Universal Hashing: Applications to Accordion Modes
Jonathan Fuchs
Universal hashing gives a pairwise guarantee: for two distinct messages, the probability of any fixed keyed-hash output difference is at most $\varepsilon$. Summing over the $\binom q2$ query pairs gives the familiar multi-query upper bound $\binom q2\varepsilon$, but this union bound does not show that one transcript can realize quadratically many useful pairwise events. We study when a single algebraically structured query set can do so by arranging many substantially different key conditions whose solution sets spread across the key space. Catching gives a simple chosen-offset baseline, while action-invariant grouping provides both a general analysis tool and an attack-search methodology based on message transformations, key relabelings, relative actions, and solution-set overlap. For POLYVAL, and for $\operatorname{NH}[w]$ when even $w\geq4$, we obtain zero-offset constructions in which every query uses output offset zero and balanced partial sets already achieve $\Theta(q^2\varepsilon)$ growth up to absolute constant factors. Thus the quadratic phenomenon can be intrinsic to keyed-hash algebra rather than caused by chosen output offsets. We then show that the same key-space coverage principle survives inside complete accordion modes. HCTR2 gives expected-list recovery of its derived POLYVAL subkey: the true subkey is always included and the candidate list has expected size $2$ in the ideal-permutation model. In ddd-AES the consequence is stronger than distinguishability: with $2^{65}$ fixed-tweak chosen plaintexts of length $384$ bits, exactly one observable cross-pair is the internal POLYVAL catch and it deterministically determines the full $128$-bit POLYVAL key $L$.
Last updated:  2026-08-09
Efficient Algorithms for $\mathbb{G}_2$ Subgroup Membership testing on Pairing-friendly Curves
Jianming Lin, Yu Dai, Chang-An Zhao, and Yuhao Zheng
Subgroup membership testing serves as a crucial countermeasure against small subgroup attacks, thereby ensuring the security of pairing-based cryptographic protocols. Despite its vital importance, the expensive computational requirements for membership testing on specific pairing-friendly curves pose a non-negligible challenge. In this paper, we revisit the $\mathbb{G}_2$ membership testing algorithms on KSS16 curves and propose a novel approach specifically designed for the families constructed by the KSS method (Kachisa-Schaefer-Scott method). Moreover, we generalize several previous methods for $\mathbb{G}_2$ membership testing, rendering them applicable to more generic pairing-friendly curves. Specifically, we implement an efficient $\mathbb{G}_2$ membership testing on three well-known curves KSS16-329, KSS16-330, and KSS16-766 for verification. The experimental results illustrate that our new method achieves improvements of $24.0\%$, $33.3\%$, and $29.2\%$ in terms of clock cycles compared to the state-of-the-art, respectively.
Last updated:  2026-08-08
Design and Analysis of Four-State Quantum Public-Key Encryption Scheme
Rahul Kumar and Vikas Srivastava
Quantum public-key encryption (QPKE) is an important direction for secure communication in the presence of quantum adversaries. In this paper, we analyze the four-state QPKE scheme of Liu et al. and show that its ciphertext structure leaks information about computational-basis plaintexts. We present a ciphertext-leakage attack in which an adversary, without knowing the private key, measures the quantum ciphertext component and combines the result with the exposed classical correction bit to recover the plaintext. To overcome this limitation, we propose $\mathsf{sQPKE}$, a simple quantum public-key encryption scheme. The $\mathsf{sQPKE}$scheme uses only elementary operations such as XOR, parity computation, CNOT, Hadamard, Pauli-$Y$ gates, and computational-basis measurements. We prove correctness, analyze security against ciphertext-leakage, eavesdropping, and distinguishing attacks, and validate the attack and proposed construction through Qiskit implementation and resource estimation.
Last updated:  2026-08-08
LUNA+: More Succinct Post-Quantum ZK-SNARKs from Computational Privacy
Yuki Kume, Ron Steinfeld, Amin Sakzad, and Mert Yassi
We present LUNA+, a refinement of the LUNA designated-verifier lattice-based ZK-SNARG that achieves significantly improved concrete succinctness. While the original LUNA scheme achieves quasi-optimal asymptotic proof length ($O(\lambda)$), its practical parameters are constrained by its statistical privacy analysis. This analysis, founded on a Leftover Hash Lemma with Leakage (LHLL), necessitates the use of polynomially large, but still significant "smudging" noise to guarantee statistical uniformity. This noise inflation directly propagates to larger lattice dimension and modulus parameters and, consequently, larger proof and CRS sizes. Our core contribution is a new privacy analysis that replaces this statistical foundation with a computational one. We demonstrate that the circuit privacy of LUNA's re-randomization procedure can be securely based on the computational hardness of the Matrix Hint-Module Learning With Errors (MH-MLWE) problem. This computational approach avoids the need for large statistical noise and enables a key optimization: we decouple the secret re-randomization noise from the fresh masking noise. We then formalize and solve an optimization problem to find the minimal noise parameters that satisfy both correctness and the MH-MLWE security reduction. In the process, we also introduce a new problem called Coset Error Knapsack MH-MLWE in which the MLWE error is sampled from a coset of a lattice, which we show is as hard as the standard MH-MLWE problem, and may be of independent interest. This new analysis results in substantial concrete efficiency gains. For a 128-bit security level and an R1CS instance of size $2^{16}$, LUNA+ reduces the proof size by $\approx 25\%$ (from 5.60 KB to 4.22 KB) and the compressed CRS size by $\approx 73\%$ (from 2.06 GB to 0.54 GB) compared to the original LUNA. These succinctness improvements are also accompanied by performance gains, including up to a $\approx 1.73\times$ speedup in setup, a $\approx 1.53\times$ speedup in addition and a $1.44\times$ speedup in decryption for the implementation parameters.
Last updated:  2026-08-08
Multi-Diagonal Truncated Differentials and Ciphertext-Only Attacks on Reduced-Round AES
Orhun Kara and Can Balıkçı
We present the first ciphertext-only distinguishing attack on 5-round AES and a key-recovery attack on 6-round AES for all key sizes under ASCII-encoded English-language plaintext distributions, as well as additional ciphertext-only results under uniform ASCII distributions. Our attacks are enabled by a new analytical framework for estimating truncated differential probabilities in 5-round AES, a problem that remains largely unresolved beyond restricted configurations. Existing approaches, relying on statistical sampling, integral cryptanalysis, or differential distribution tables of super S-boxes, are primarily limited to settings with a single active diagonal in the plaintext and a single passive inverse diagonal in the ciphertext. Our method extends this line of work by providing analytical estimates over a substantially broader range of configurations. We construct this framework by combining precise computations of MDS-level transition probabilities with a systematic enumeration of truncated differential characteristic classes. By organizing characteristics into equivalence classes defined by diagonal propagation patterns, we enable structured aggregation of probability contributions. This approach captures configurations with a single active diagonal in the plaintext and arbitrary passive inverse diagonals in the ciphertext, as well as the complementary setting involving multiple active diagonals in the plaintext and a single passive inverse diagonal in the ciphertext. Our results are validated through independent derivations, consistency checks against prior work, and computer-aided enumeration. More broadly, the framework offers a systematic approach to truncated differential analysis of AES and potentially other AES-like SPN ciphers.
Last updated:  2026-08-08
How to use Polynomially-Hard iO: Turing Machine Obfuscation and More
Jesko Dujmovic, Yao-Ching Hsieh, Abhishek Jain, and Willy Quach
We revisit the notion of PViO [Jain-Jin, FOCS’22] – an indistinguishability obfuscation (iO) scheme for Turing machines with unbounded input length that guarantees security for pairs of machines whose equivalence can be proven in Cook’s Theory PV. Known constructions of PViO require subexponentially-hard iO for circuits. We give the first construction based on polynomially-hard iO and other standard assumptions. We further show how to replace iO with EFiO – an efficiently falsifiable variant, thus obtaining a construction based on efficiently falsifiable assumptions. Central to our result is a new twist to the celebrated punctured programming technique [Sahai-Waters, STOC’14], where one can program an obfuscated probabilistic function on its entire input domain in one shot instead of an input-by-input manner. Our key ingredient is the notion of function secret sharing [Boyle-Gilboa-Ishai, EUROCRYPT’15]. We further show the versatility of our technique by removing the use of complexity-leveraging in two applications of iO: unleveled fully homomorphic encryption, and adaptively-sound succinct non-interactive arguments for “trapdoor” languages.
Last updated:  2026-08-07
Multi-Instance Unrecoverability of iMHF-Based Password Hashing
Charles Dodd, Pooya Farshim, Siamak F. Shahandashti, and Karl Southern
The study of memory-hard functions (MHFs) has so far focused mainly on provable guarantees on the expected minimum cumulative memory complexity (CMC) required per \emph{evaluation} when amortized over multiple instances. Such results, however, say nothing about whether the passwords in a compromised password bank remain \emph{unrecoverable}. Indeed, a construction can be memory-hard while still leaking information about its input. We provide the first formal treatment of the unrecoverability of graph-based data-independent MHFs (iMHFs) in the multi-instance setting. Multi-instance security is the widely accepted security model when inputs have low entropy or are correlated, and requires the adversarial effort to scale linearly with the number of instances broken. To prove these results, we extend the ex-post-facto pebbling technique of Alwen and Serbinenko (STOC'15) and the unguessability reductions of Farshim and Tessaro (EUROCRYPT'21). We then combine the two resulting frameworks to bound the number of guesses of adversaries with a given \emph{maximum} CMC (over the random oracle and adversary coins) in terms of the pebbling complexity of the graph underlying the iMHF. Combined with known lower bounds on the pebbling complexity of Catena's underlying graph, we obtain concrete unrecoverability bounds for Catena, showing in particular that adversarial advantage diminishes exponentially with the number of instances recovered, with the per-instance advantage growing linearly in the maximum CMC of the adversary.
Last updated:  2026-08-07
MAYO Lite: a Low-RAM Implementation of the MAYO Signature Scheme
Sven Bauer, Fabrizio De Santis, and Florian Wilde
MAYO is a signature scheme based on the Unbalanced Oil and Vinegar (UOV) construction and a third round candidate in the NIST standardization process for additional post-quantum signature schemes. We present a memory-optimized pure- C implementation of MAYO signature verification that reduces RAM consumption by 97–99% compared to the reference implementation provided by the PQM4 project [KPR+] at the cost of increasing runtime by 50–200% and while maintaining code size. This reduction finally enables verifying MAYO signatures on smart cards and small microcontrollers with only a few kilobytes of RAM. We achieve it through three coupled design choices: a) we expand the public key vector-by-vector on the fly rather than all at once at the start; b) we reorder the calculation of the matrix product SPS so that each vector of P is used exactly once, which avoids repeated expansions; and c) we add precomputed multiples of each P-vector directly onto the result instead of accumulating P-vectors before multiplication. We provide results using the PQM4 framework for all parameter sets listed in the specification and supported by PQM4 on our platform, including three main parameter sets MAYO{1,2,3}. This enables direct comparison with other post-quantum digital signature schemes. Further parameter sets not supported by PQM4, including the fourth main parameter set MAYO5, are measured on our own framework, which supports key and signature generation on the host. Our results for non-standard MAYO parameter sets offer insights into the performance and scalability of the proposed approach that may inform ongoing standardization efforts.
Last updated:  2026-08-07
Compressed Key Exchange Protocol from Orientations of Large Discriminant Using AVX-512
Yuhao Zheng, Jianming Lin, Yutong Liang, Yanzhen Ren, Huixin Zhang, and Chang-An Zhao
CSIDH (Commutative Supersingular Isogeny Diffie--Hellman) is a class-group-based key-exchange protocol operated on supersingular elliptic curves, which, at the time of its proposal, exhibited several attractive selling points such as non-interactivity. Unfortunately, CSIDH is vulnerable to the sub-exponentiation attack--Kuperberg's algorithm, thereby requiring large parameters to ensure security. A recent work based on oriented elliptic curves with large discriminants, proposed by Houben, allows for a significantly small base field (around 255 bits). We name this protocol CSIDH-LDO. However, the practicality of CSIDH-LDO is currently hindered by the necessity of performing multiple group actions and its huge public-key size. In this paper, we address these bottlenecks by presenting highly optimized constant-time implementations alongside an effective public-key compression framework for CSIDH-LDO. We combine algorithmic improvements, specifically scalar multiplication by differential addition chains and isogeny computation on the twisted Edwards model, with \textit{limb-slicing} to exploit parallelism via Intel's AVX-512 instructions. To resolve the architectural mismatch when mapping $r \in \{7, 13\}$ group actions to 8-lane SIMD registers, we evaluate two parallel scheduling strategies. While a dummy-based approach allows us to leverage efficient $\mathbb{F}_{p^2}$-arithmetic, our dummy-free strategy systematically exploits internal parallelism to fully saturate the 512-bit vectors without redundant computations. Benchmarks on an Intel Tiger Lake processor demonstrate our parallel implementations achieve speedups of up to 3.40$\times$ (AVX-512F) and 7.30$\times$ (AVX-512IFMA) over an optimized x64 assembly baseline. Furthermore, we establish a formal framework for public-key compression tailored for CSIDH-LDO. Specifically, we propose two efficient techniques that achieve a compact public key representation of approximately $(r+2)\log_2(p)$ bits, thereby significantly reducing communication bandwidth. To the best of our knowledge, this work is the first to demonstrate the efficacy of SIMD parallelization combined with optimized compression for isogeny-based protocols derived from orientations of large discriminants.
Last updated:  2026-08-07
Counters and Nonces for Mitigating Ciphertext Side Channels
Moritz Peters, Jens Alich, Ashwin Jha, Gregor Leander, Yuval Yarom, and Tim Güneysu
Recent works have highlighted the risk of deterministic memory encryption, as used for example in AMD SEV. In the so-called ciphertext side-channel attack, an adversary leaks sensitive information, such as cryptographic keys, from an encrypted VM by observing changes in the encrypted contents of the memory. To date, countermeasures have been quite restricted in scope and have not addressed the root cause. Alternatively, some studies suggest adding freshness to memory encryption. However, this approach is considered impractical due to the performance overhead introduced by fetching such freshness values for every single memory access. In this work, we propose an efficient approach for eliminating most of the overhead of fetching the aforementioned freshness. Our core idea is to repurpose the ECC memory area to efficiently store random nonces or counters. We propose a range of implementations with varying trade-offs between security guarantees and performance overhead, and demonstrate that we can achieve a solid baseline security even with small random nonces. By leaving a portion of ECC memory unused, we show that it is possible to efficiently integrate protection mechanisms such as memory integrity and memory tagging, while limiting the overall performance overhead to approximately 2%.
Last updated:  2026-08-07
Preprocessed Private Function Evaluation: Achieving Sublinear Online Complexity for Lookup Tables
Tanping Zhou, Xiaoyi Wang, Yi Qu, Wenchao Liu, Long Chen, and Zhenfeng Zhang
Private Function Evaluation (PFE) facilitates the secure computation of private functions on private inputs in an oblivious manner, ensuring that both the function and the inputs remain confidential throughout the entire computational process. PFE has garnered significant attention due to its critical applications in various domains, such as privacy-preserving healthcare systems and privacy-preserving credit checks, where safeguarding the confidentiality of the function itself is of paramount importance. However, despite its broad applicability, existing PFE schemes often exhibit inefficiencies, even in relatively straightforward scenarios such as the evaluation of lookup tables. To mitigate these limitations, we propose a novel variant of PFE, termed Preprocessed Private Function Evaluation (PPFE), which leverages preprocessing techniques to significantly enhance the efficiency of online computations. Within this framework, we introduce a specialized construction tailored specifically for lookup table operations, achieving sublinear complexity during the online computation phase. The efficacy of the proposed approach is demonstrated through experimental evaluations. For a lookup table of size $2^{24}$, the online computation time required to process a single query is about 3 milliseconds, representing a performance improvement of more than an order of magnitude compared to existing results. Furthermore, the proposed scheme exhibits strong scalability, effectively handling thousands of adaptive queries within the same framework.
Last updated:  2026-08-06
On the Suitability of Syndrome Decoding for Proof-of-Work under Quantum Adversaries: Design and Analysis
Aleck Nash, Kim-Kwang Raymond Choo, and Henry Chimal-Dzul
Proof-of-work (PoW) remains a fundamental mechanism for achieving decentralized consensus, most commonly instantiated using cryptographic hash functions. In such constructions, mining takes the form of an unstructured search problem over a large input space, where miners repeatedly evaluate candidate solutions until a valid one is found. While this design has proven effective in practice, it admits a quadratic quantum speedup via Grover’s algorithm, raising concerns about the long-term security of hash-based mining. Motivated by this limitation, we investigate the use of code-based cryptographic problems as an al- ternative foundation for proof-of-work. In particular, we focus on the syndrome decoding problem and examine its classical and quantum com- plexity based on current state-of-the-art information-set decoding (ISD) algorithms and their quantum variants, comparing the resulting quantum advantage with that of hash-based and lattice-based constructions. Building on this analysis, we propose a proof-of-work construction based on the Syndrome Decoding Problem (SDP) with a structured profile constraint, which enables controlled variation of solution density and difficulty. Under the standard random-instance heuristic, we derive ex- pressions for the expected number of solutions and the probability of successful mining, providing a principled basis for parameter selection.
Last updated:  2026-08-06
A Practical Key-Recovery Attack on GRAFHEN
Jules Dumezy
We give a structural cryptanalysis of GRAFHEN, a proposed group-based fully homomorphic encryption scheme whose public rewriting rules hide a group representation used for decryption. Under the designers' isomorphism hypothesis, the compatible representations in a finite target $T$ form one free $\mathrm{Aut}(T)$-orbit. Thus every representative induces the same zero predicate. For a fixed publication, the published key-class expression is the expected trial count of uniform verified sampling rather than a lower bound on reconstruction work. More generally, a homomorphism $\psi$ gives the correct zero predicate exactly when $\ker\psi\cap\Gamma\subseteq\Lambda$, where $\Gamma$ is the ciphertext set of the presented group and $\Lambda$ its zero-ciphertext subgroup. After reconstruction, we give a finite-sample distinguishing bound for independent zero queries and an independent challenge. It requires neither uniform sampling nor generation of the full zero subgroup. For matched query and challenge distributions, the target alone puts the advantage above $1/2$ after $14$ queries at degree $7$ and $26$ at degree $11$. Our attack, HEnbane, combines automorphism-reduced search over complete group elements with algebraic forcing from short public consequences. At the level of a generic algorithmic schema, an uncapped whole-element branching fallback makes reconstruction complete for every finite effectively enumerable target with enumerable element-orbit representatives. The released software instantiates this schema for its supported symmetric-group targets and the fixed target $\mathrm{PSL}_2(343)$. The two-seed force chains used by all supplied instances are a fast path rather than a completeness assumption. It decrypts all five released symmetric challenges, with a slowest ten-run mean of $25.4$ seconds. It also solves the author-supplied $\mathrm{SL}_2(343)$ challenge for the revised parameters by reconstructing in the $\mathrm{PSL}_2(343)$ quotient and recovering the ten central lift signs over $\mathbb F_2$, averaging $37.7$ seconds end to end without exact-order hints.
Last updated:  2026-08-06
Notes on the ideal arithmetic correlations of $N$-ary sequences
Feifei Yan and Pinhui Ke
In this paper, we investigate the nonexistence of $N$-ary sequences with ideal arithmetic correlation. We prove that there exist no ternary, quaternary, or $6$-ary sequences with ideal arithmetic autocorrelation when the connection integer is an odd prime power $p^{t}$ and $\textup{ord}_{p^{t}}(N)=\phi(p^{t})/4$, where $\phi$ denotes Euler's totient function. Furthermore, when the connection integer is an odd prime $p$ and $\textup{ord}_{p}(N)=\phi(p)/6$, no such ternary, quaternary, or $6$-ary sequences exist for ideal arithmetic correlation. This includes in particular the case $p\equiv7(\textup{mod}12)$, for which $\textup{ord}_{p}(N)=\phi(p)/6$ and we further show that no $N$-ary sequence with ideal arithmetic correlation exists for any prime $N>2$. These results provide further evidence that ideal arithmetic correlation is highly restrictive in the $N$-ary setting.
Last updated:  2026-08-06
When Does Being Selfish Pay Off? Temporal Composability and Profitability in Selfish Mining
Colin Finkbeiner, Connor Shaw, and Ghada Almashaqbeh
Selfish mining undermines incentive compatibility of proof-of-work blockchains, letting a miner earn disproportionate rewards at a hashrate lower than the majority threshold. A decade of work has asked whether a strategy is profitable, however, far less is understood about when it becomes profitable. Timing is critical since selfish mining operates at a loss before it turns a profit, typically requiring tens of weeks to break even in the classic case. In this paper, we present a holistic study of the time-to-profitability (TTP) of existing selfish mining strategies structured around four contributions. First, in the single-attacker setting, we characterize TTP across the full strategy space and find that TTP-minimizing and profit-maximizing strategies frequently diverge, making attack horizon a critical metric. In particular, under realistic fee dynamics, the use of incentive transactions to recruit honest-but-rational miners enable incentivized strategies to reach profitability up to $15\times$ faster than classic selfish mining at the same hash rate. Second, we explore TTP for the first time in the multi-attacker setting, showing that the difference in strategies between opposing attackers has a dramatic impact on joint-profitability lag. Third, we generalize intermittent selfish mining by exploring temporal composition over the full strategy space and show that its purported benefits are largely overstated. That is, alternating strategies rarely outperform the best static strategy in terms of either TTP or long-term profits. Finally, and building off our earlier findings, we explore adaptive, state-conditioned strategy selection at the difficulty adjustment period (DAP) level. We compare a general-purpose LLM agent against a fixed decision-tree selector, both implementing the same selection criteria. We find that both selectors reliably identify profit-maximizing strategies from observed network conditions, at a low operating cost, lowering the expertise barrier to exploiting adaptive selfish mining.
Last updated:  2026-08-06
SHARMONY: Composing SHA-2 and SHA-3 Hardware for Crypto-Agile PQC
Liga Anwar, Carlos Andres Lara-Nino, Jong-Yeon Park, and Michael Hutter
This work composes SHA-2 and SHA-3 into a unified hardware architecture, bringing them together as a single, efficient cryptographic ensemble. This need is driven in particular by Post-Quantum Cryptography (PQC), where different standardized schemes rely on either SHA-2 or SHA-3/SHAKE primitives. Rather than enforcing strict round-level unification, the proposed design applies selective sharing across the most area-critical components, including a shared 25x64-bit register bank, shared round-constant storage, and unified padding and control logic while maintaining full compliance with FIPS 180-4 and FIPS 202. In addition, a duet execution mode exploits the otherwise underutilized upper half of the 64-bit datapath to process two independent SHA-224/256 streams in parallel, benefiting Merkle-tree-based constructions in hash-based PQC. The design is implemented and synthesized on an Artix-7 FPGA, occupying 5,873 LUTs and 2,310 FFs. Experimental results show that SHARMONY achieves a throughput of 1,959 Mbps for SHA-256, representing improvements of 100-152% over the SHA-256 engines of SLotH, Sphincslet, OpenTitan, and Caliptra. At the same time, SHARMONY reduces LUT utilization by an average of 40% and FF utilization by an average of 55% compared to combined designs constructed from separate SHA-2 and SHA-3 implementations.
Last updated:  2026-08-06
Lattice-based Signature Schemes for Bitcoin
Dmytro Zakharov, Mikhail Kudinov, Viktoria Balatska, and Yaroslava Chopa
Lattice-based cryptography offers a promising direction for transitioning Bitcoin toward post-quantum security, serving as a secure replacement for currently deployed discrete logarithm signatures. The primary advantages of lattice-based signature schemes include the compact combined size of signatures and public keys (e.g., in some cases below 1.6 KB), the robustness of underlying security assumptions, and an algebraic structure that, while not yet yielding practical constructions, holds potential for advanced functionality such as threshold and multi-signatures, compared to hash-based constructions. In this paper, we present a self-contained review of three lattice-based signature schemes, with Bitcoin's post-quantum transition as the motivating application: Dilithium, Falcon, and Hawk. The latter was recently withdrawn from NIST standardization following a key-recovery attack; we retain it because its design paradigm remains of independent interest. For each protocol, we detail the high-level intuition, the necessary technical preliminaries, low-level mechanics, performance, and security analysis. We then assess the deployment aspects relevant to Bitcoin: the on-chain footprint, determined by the combined public-key and signature size and compared against hash-based alternatives; the target security level for outputs that may remain unspent for decades; implementation constraints, such as Falcon's floating-point signing; and wallet key derivation. No prior exposure to lattice-based cryptography is assumed: all the required background is developed within the document.
Last updated:  2026-08-06
Two-Limb CRT Ring-LWE Encryption with Exact Decryption and Public Re-randomization
Damir Vodenicarevic, Andrei Fleiser, Pierre Seznec, Karen Mayen Naranjo, Lucas Foucher, Léo Besançon, Thybault Alabarbe, Jean-François Morcillo, Benjamin Reynes, and Lilian Urvoy
Anonymity infrastructures such as mix networks, anonymous storage, and privacy-preserving replication rely on public re-randomization: any party holding only public information can transform a ciphertext into a fresh-looking encryption of the same plaintext, hiding the linkage between the two. Classical ElGamal-based solutions are broken by quantum adversaries, while existing lattice-based alternatives carry very large ciphertexts with unanalyzed noise growth, rely on heavyweight homomorphic-encryption stacks with approximate (rounded) decryption, or lack a precise analysis of how many re-randomizations are safe. We address this gap with a practical Ring Learning with Errors (Ring-LWE) public-key encryption scheme supporting public re-randomization without ciphertext growth. Our construction is Lyubashevsky–Peikert–Regev / Fan–Vercauteren (LPR/BFV)-style encryption over $R=\mathbb{Z}[x]/(x^n+1)$ with $n=4096$, engineered around a two-limb Chinese Remainder Theorem (CRT) modulus $q=t\cdot q_2$ with 32-bit primes. Embedding plaintext as $\Delta M = q_2 M$ makes the message vanish modulo $q_2$, so the $q_2$-limb carries only the decryption noise, enabling exact message recovery without rounding. We prove correctness with explicit decryption-failure bounds that remain valid under repeated re-randomization, via an aggregation lemma showing that arbitrarily many re-randomizations affect decryption only through a single aggregated randomness triple. We also prove that two-limb ciphertexts are pseudorandom (indistinguishable from uniform, IND\$) under Decision Ring-LWE over the combined modulus $q=tq_2$; security against chosen-plaintext attack (IND-CPA) and re-randomization unlinkability follow. A constant-time Rust implementation encrypts in 0.80 ms, re-randomizes in 0.51 ms, and decrypts in 0.21 ms per 64 KiB ciphertext carrying 15.5 KiB of payload on a fixed-frequency 3.8 GHz CPU—on par with a modulus-matched Microsoft SEAL baseline—and passes timing-leakage tests. Empirical noise simulations validate the analysis.
Last updated:  2026-08-06
Adaptive-Input-Secure Updatable Private Set Union
Seongbong Choi, Jiseung Kim, and Hyung Tae Lee
In multi-epoch deployments, private set union~(PSU) operates in an adaptive-input loop: after observing the union at epoch $t$, the receiver may choose its next input for epoch $t+1$. Liu et al.~(EUROCRYPT 2026) formalized this multi-epoch adaptive-input setting for updatable private set intersection and provided an instantiation, but their framework does not extend to PSU. Meanwhile, existing PSU protocols are analyzed only in the single-shot setting. We present the first semi-honest, adaptive-input-secure updatable PSU protocol supporting two-sided add/delete updates in the multi-epoch adaptive-input setting of Liu et al. Our construction is built around a new primitive, the updatable oblivious key-value store (uOKVS). Its defining rule, distributional erasure, requires each refresh to be distributed identically to a fresh static encoding of the current key set, rather than merely indistinguishably. We realize uOKVS by combining the Band-OKVS of Bienstock et al. with a PRF under a persistent key. The resulting refresh reuses a cached factorization, so its per-epoch encoding cost scales linearly rather than quadratically in the band width $w$. Building on this layer, we obtain a multi-epoch PSU protocol whose leakage is limited to set and update cardinalities, even against adaptive-input adversaries. We implement the protocol and benchmark it in a single-threaded setting. At $n = 2^{20}$ with per-epoch updates $\Delta = 55$ over $10$ epochs, the online per-epoch wall-clock time is $1.41$ s on LAN, yielding a $30.9\times$--$98.9\times$ speedup over prior static PSU protocols re-executed from scratch at each epoch.
Last updated:  2026-08-06
Secure and Privacy-preserving CBDC Offline Payments using a Secure Element
Uncategorized
Elli Androulaki, Angelo De Caro, Kaoutar El Khiyaoui, Romain Gay, Rebekah Mercer, and Alessandro Sorniotti
Show abstract
Uncategorized
Offline payments present an opportunity for central bank digital currency to address the lack of digital financial inclusion plaguing existing digital payment solutions. However, the design of secure offline payments is a complex undertaking; for example, the lack of connectivity during the payments renders double spending attacks trivial. While the identification of double spenders and penal sanctions may curb attacks by individuals, they may not be sufficient against concerted efforts by states or well-funded institutions. It is hence important to also rely on preventive measures that reduce the scale of such attacks. An example of such a measure is secure elements. These however are limited in compute and storage, making the design of solutions that offer comparable privacy guarantees to those of physical cash challenging. We address this with a protocol that offloads most of the payment computation to the user’s mobile device and restricts the computation on the secure element to deleting spent tokens, and generating a signature with a computation equivalent to that of ECDSA. We claim that the use of mobile devices or enhanced smart card-based devices are required for secure consumer-to-consumer payments. To further harden the protocol, we enable the efficient identification of double spenders on the off-chance an attacker successfully double spends. Finally, we prove its security in the ideal/real world paradigm, and evaluate its performance to demonstrate its practicality.
Last updated:  2026-08-06
The Equivalence of Two Quadratic Based IBEs
George Teseleanu
In this short note, we show that two identity-based encryption schemes, introduced by Joye and Zhao et al., which appear different, are essentially the same scheme. The only difference between them is that one prioritizes speed (Zhao et al.), while the other prioritizes bandwidth (Joye). We also show how to speed-up Joye's scheme at the cost of adding at most one integer to the public key, thereby achieving a better encryption complexity, while having the same bandwidth requirements.
Last updated:  2026-08-06
Sub-Cubic Homomorphic Matrix Multiplication via Self-Dual Normal Bases
Efe İzbudak, Kubra Kaytanci, Ferruh Ozbudak, and Erkay Savas
This paper analyzes the bilinear embedding of matrix algebras into commutative cyclotomic rings. We apply the Cohn-Umans method. This establishes that single-multiplication bilinear monomial embeddings require a ring degree of $\widetilde{\Omega}(N^3)$. We circumvent this bound by routing Strassen tensor rank decompositions through orthogonal Chinese Remainder Theorem ideals. This reduces the asymptotic complexity to $\widetilde{\Omega}(N^{\log_2 7})$. We optimize the coprime tensor decomposition. Embedding the inner tensor into the maximal real subfield satisfies the Lempel-Weinberger parity constraint. This guarantees the existence of a Self-Dual Normal Basis, reducing the required basis generators to a single element and mathematically halving the homomorphic trace depth. Canonical integer polynomial lifts ensure uniform norm bounds. Type I Optimal Normal Bases bound the trace dual expansions to an $O(1)$ constant. By invoking Kronecker's theorem, we prove that the polynomial power basis minimizes the canonical expansion for the non-evaluated tensor components. A towered evaluation over composite degrees controls noise propagation. This decouples key-switching errors into a logarithmic bound. We generalize the embedding to Galois rings via Hensel's and Nakayama's lemmas to support high-precision integer arithmetic. Furthermore, we extend the architecture to boundless matrices exceeding the fixed ring capacity via a multi-ciphertext block-Strassen decomposition. By deferring the homomorphic trace operator to post-Strassen recombination, we completely eliminate homomorphic basis-switching, achieving an asymptotic complexity of $O(N^{\log_2 7 - 1/\rho})$ multiplications and $\widetilde{O}(N^{2 - 2/(\rho \log_2 7)})$ automorphisms for matrices of arbitrary dimension. Empirical benchmarks over the BGV scheme validate the approach. A multi-threaded towered trace evaluates $32 \times 32$ matrices in $141.3$ milliseconds at a security level of $\lambda=148$ using one ciphertext-ciphertext multiplication. We achieve a speedup factor of $2.49$ over multi-threaded baselines.
Last updated:  2026-08-06
On $k$-way split multiplication algorithms
Mehmet Özgün Cihangir and Oğuz Yayla
Efficient polynomial multiplication and matrix-vector operations are fundamental to computational algebra and modern cryptography. In lattice-based post-quantum cryptography (PQC), schemes utilizing Number Theoretic Transform (NTT)-unfriendly rings require highly optimized subquadratic multiplication algorithms. In this paper, we establish a rigorous mathematical framework for generalized $k$-way split polynomial multiplication and Toeplitz Matrix-Vector Product (TMVP) algorithms over arbitrary fields. First, we construct generalized $k$-way Schoolbook and Karatsuba multiplication algorithms, deriving exact closed-form recurrence relations and arithmetic complexities for any integer $k$. Second, we introduce a novel $k$-way TMVP algorithm utilizing optimal evaluation points and matrix row-reversal techniques. We mathematically prove that this generalized formulation strictly achieves the theoretical interpolation lower bound, requiring exactly $2k-1$ subproblems and yielding a subquadratic asymptotic complexity of $O(n^{\log_k(2k-1)})$. Furthermore, we determine the optimal consecutive application sequence of $k$-way Karatsuba and Schoolbook algorithms for any input size $n$, proving that the peak efficiency is driven entirely by the prime factorization of $n$. Finally, we establish exact algebraic crossover thresholds, demonstrating that our generalized TMVP formulas and optimal algorithmic sequences significantly outperform state-of-the-art unequal $k$-way splits and classical combinations in the literature, providing minimum arithmetic operation counts for $k \in \{5, 6, 8, 12\}$ and inputs of power-of-two and power-of-three dimensions.
Last updated:  2026-08-06
AES-Based Grinding for MPC-in-the-Head Signatures
Matthieu Rivain
Grinding is a technique which introduces a proof of work into the Fiat-Shamir transform: by constraining the challenge to satisfy a $w$-bit condition, forging a proof requires about $2^w/\varepsilon$ evaluations of the hash function instead of $1/\varepsilon$, where $\varepsilon$ is the soundness error of the underlying protocol. This allows one to select reduced parameters, yielding shorter proofs and signatures. Grinding is used in FAEST, MQOM and SDitH, the three MPC-in-the-Head schemes selected for the third round of the NIST additional post-quantum signature standardization process, where it is instantiated with Keccak. In this short paper, we investigate grinding schemes in which the proof of work is expressed in terms of block cipher computations, specifically AES, which is significantly faster than Keccak on modern CPUs, is already a building block of these schemes, and underlies the very definition of the NIST security categories. We formalize the notion of grinding scheme together with a protocol-agnostic security notion, we propose a construction performing two cipher calls per iteration, and we prove, in the ideal cipher and random oracle models, that an adversary making $Q_E$ cipher queries breaks it with probability at most $\frac{4}{3} \cdot \varepsilon\, Q_E / 2^w$, up to negligible terms. We further generalize the scheme to use more cipher calls per iteration, which makes the constant $\frac43$ tend to $1$.
Last updated:  2026-08-06
A Unified Treatment of Reachability and Indistinguishability Properties: First-Order Logic with Overwhelming Truth
Gergei Bana and Mitsuhiro Okada
In the formal verification of complexity-theoretic properties of cryptography, researchers have traditionally attempted to capture ``overwhelming truth'' (satisfaction with all but negligible probability) via satisfaction on individual traces of probabilistic execution. However, this approach introduces significant complexity when quantification is present: satisfaction of existential quantification over traces often produces witnesses---such as nonce-guessing oracles---that, without further constraints, may not correspond to meaningful global objects like PPT algorithms respecting causal structure. This discrepancy creates significant obstacles when attempting to combine trace properties, such as reachability, with properties that are defined on non-negligible sets such as computability, or global properties, such as algorithmic indistinguishability. We resolve this by shifting from defining local satisfaction as satisfaction on individual traces to a semantics based on ever-decreasing non-negligible sets. We demonstrate that the logical key to this unification lies in first-order modal logic S4 with \emph{non-negligible sets} as possible worlds, rather than the propositional S5 fragment with \emph{traces} as possible worlds suggested in previous investigations by the Squirrel Prover team. By introducing a PPT computational first-order S4 Kripke semantics and adopting Fitting's embedding for trace properties, we provide a unified quantified treatment of overwhelming truth for trace properties and indistinguishability, together with a first-order calculus, $\mathsf{BC}^+$, whose sole modal operator is the overwhelming-truth bracket $[\,\cdot\,]$. The calculus is sound and, on its fragment, derives exactly the theorems of first-order S4 with persistence; computational completeness holds on the fragment; cut elimination holds propositionally, while at first order every cut is confined to an optimal Barcan shape. We show that Fitting's embedding naturally accommodates the higher-order quantification used in the Squirrel prover by interpreting function types as sorts in a many-sorted first-order logic; this reduces the need for the specialized \texttt{const} predicate and its associated structural restrictions. Finally, using our findings, we present a hybrid semantics for CryptoVampire that eliminates the need for bounded Skolemization.
Last updated:  2026-08-06
Quantum Circuit Optimization with LLMs under a Structured Guideline
Kyungbae Jang, Hyunji Kim, Hwajeong Seo, and Anupam Chattopadhyay
The cost of quantum cryptanalysis is dominated by the quantum circuit of the target cipher. Estimating the quantum attack cost of a cipher thus requires building that circuit and measuring its qubit count, Toffoli count, and Toffoli depth. This is manual work that needs expert knowledge and must be redone for each cipher and each cost target. Large language models handle ordinary programming well, but their use in constructing quantum circuits for ciphers is still limited. In this work, we collect quantum circuit optimization techniques that apply across many ciphers. We write these techniques into a guideline for a general-purpose LLM. Given this guideline and a single target cipher, the model produces two circuits. One minimizes the qubit count, and the other minimizes the Toffoli depth. Each circuit is verified against the test vectors of the cipher before its resources are estimated. Using this approach, we implement quantum circuits of CRAFT, MANTIS, QARMA, mCrypton, EPCBC, and Pyjamask for which quantum circuit implementations have not previously been reported. We further apply the same approach to ciphers with existing implementations. Without access to prior results, the generated circuits reach resource counts comparable to manually optimized ones.
Last updated:  2026-08-06
SoK: Research Motivations of Public-Key Cryptography
Fuchun Guo, Willy Susilo, Xiaofeng Chen, Peng Jiang, Jianchang Lai, and Zhen Zhao
The design, proposal, and analysis of cryptographic primitives (schemes and protocols) is one of the primary research fields in cryptology. To advance this research field, in this paper, we systematically introduce the research motivations for proposing new constructions (for a primitive) in public-key cryptography. We found that all research motivations aim to produce more benefits for certain users, including practicality, security, and functionalities, although some of the benefits may not be obvious or may only hold conditionally. We have categorized the approaches for exploring more benefits into 3 ways, 6 types, 17 areas, and 40 research strategies. Each research strategy is presented as ``From less-beneficial (in the first construction) To more-beneficial (in the second construction)". This SoK paper aims to provide valuable insights into the driving forces behind advancements in public-key cryptography, facilitating future research efforts in this field.
Last updated:  2026-08-05
Triple Cryptanalysis of Isogeny-Based VRFs from Asiacrypt 2025
Yi-Fu Lai, Yu Yu, and Xiaogang Zhou
Levin and Pedersen proposed at Asiacrypt2025 a new verifiable random function (VRF) based on a CGL-analogue hash function constructed from radical isogenies. Their construction applies the same secret radical-CGL walk to a public starting curve and a message-dependent curve, and uses an R1CS proof relation to show that the two walks use the same secret key. We present a two-stage attack on this construction. The first stage concerns the unspecified representation of the public key. The reported key size indicates that the public curve is stored as a \(j\)-invariant, whereas both the specified radical-CGL computation use two coefficients to represent a curve. By exploiting this form we can produce two different VRF outputs under the same public key and message, breaking the unique provability. Hence, the output of the radical-CGL computation must follow the specification. In the second stage, we exploit these coefficients to recover the VRF secret key. With \(1536\) queries, our implementation recovers the complete \(256\)-bit secret in 30 minutes, thereby breaking residual pseudorandomness. Interestingly, we also observe that the using public key alone without queries can sometimes reveal one or two bits of the secret walk. Besides, we extend Lai's observation to obtain a one-query attack on the group-action-based VRF proposed in the same paper with advantage closed to 1/2. Together, these constitute three attacks on their work.
Last updated:  2026-08-05
Oblivious Single Access Machines are Concretely Efficient
Sage Pia, Ananya Appan, Maryam Rezapour, Amey Shukla, Nikhil Date, Benjamin Fuller, Ling Ren, and David Heath
Oblivious algorithms allow a space-constrained client program to securely outsource storage to an untrusted server. Any program can be compiled to an oblivious form via Oblivious RAM (ORAM), but this is asymptotically and concretely expensive. Recent work (Appan et al., CCS'24) proposed a weakening of ORAM called Oblivious Single Access Machine (OSAM), which offers asymptotically-improved oblivious compilation for many programs, including those that manipulate graph data structures. While of theoretical interest, OSAM graph algorithms were worse than generic ORAM, even for large graphs (tested on graphs of size up to $2^{25}$). This work improves the concrete costs of OSAM-based oblivious algorithms. In short, the original work on OSAM proposed algorithms for manipulating objects with pointers to other objects, but their management of pointers involves non-trivial and concretely-expensive algorithms. Our work greatly simplifies and improves the efficiency of OSAM-based pointer handling by co-designing (1) pointer-friendly modifications to the underlying Path ORAM algorithm and (2) new algorithms for managing pointers and building graphs from pointers. Our work provides generic and easy-to-use oblivious tools with concretely better performance than state-of-the-art generic tools. Natural graph algorithms can now be automatically compiled to an oblivious form while enjoying up to a $4$x improvement in performance as compared to generic Path ORAM (and at least $8$x as compared to the original OSAM).
Last updated:  2026-08-05
Formal Security Analysis of the Olvid Messenger
Noemi Terzo, Cas Cremers, Ruben Gonzalez, Peter Schwabe, Yuval Yarom, and Zhiyuan Zhang
We perform the first formal security analysis of the cryptographic core of Olvid, an end-to-end encrypted messaging app notably used by French government officials, including ministers. Despite its deployment in sensitive contexts and its role in critical communications infrastructure, Olvid's cryptographic security has received little independent analysis. To address this gap, we develop detailed models of Olvid's authenticated key exchange and continuous key agreement protocols. We formally verify that our protocol models achieve security properties such as mutual authentication, session-key secrecy, forward secrecy, and replay protection, under an active Dolev-Yao network adversary model that can compromise parties. While we constructively prove that the protocol design meets core security guarantees, our analysis also reveals that, contrary to its claims, the protocol does not meet strong modern security properties that are met by other state-of-the-art secure-messaging protocols, such as Signal. For example, we show in our formal analysis that Olvid is not secure in modern security models such as eCK. Along the way, we uncover a potential timing leakage, and discuss Olvid's anonymity claims.
Last updated:  2026-08-05
Extending the Applicability of Algebraic Key Recovery Attacks on the UOV Signature Scheme
Yasuhiko Ikematsu and Hiroki Furue
The Unbalanced Oil and Vinegar (UOV) scheme was proposed by Kipnis et al. in 1999 as a multivariate signature scheme. Owing to its small signature size and its resistance to various attacks over more than two decades, UOV has become one of the leading candidates in multivariate public key cryptography. In 2025, Ran proposed a novel algebraic key recovery attack exploiting the algebraic structure of UOV, which reduced the security of several parameter sets of UOV and its variants submitted to the second round of the NIST PQC standardization process for additional signatures. This attack was improved by Jin et al., and Furue and Ikematsu, forming a line of attacks that has significantly advanced the cryptanalysis of UOV. However, Ran's attack is applicable only when $v<2m$, where $v$ denotes the number of vinegar variables and $m$ the number of public polynomials. In fact, when $v\ge 2m$, an additional kernel element of the ideal generated by the public polynomials appears, preventing the attack from recovering the oil subspace. A similar issue arises in the improvements by Jin et al., and Furue and Ikematsu. In this paper, we propose a method that overcomes this issue, extending the applicability of this line of attacks to the case where such an additional kernel element appears. Applying our method to SNOVA via the lifting technique of Nakamura et al., we show that the claimed security levels of some parameter sets of SNOVA in the second round of NIST PQC standardization process for additional signatures are reduced. In particular, for the parameter set $(v,o,q,l)=(37,17,16,2)$ of NIST security level I, although Ran's attack is not applicable, our method reduces the estimated security to $2^{103}$ gate operations, which matches the complexity of the attack by Bros et al. in 2026.
Last updated:  2026-08-05
Flip a Failure into a Success: Improved Bit Flipping Decoding for QC-MDPC Codes
Paolo Santini, Davide De Zuane, Alessio Baldelli, and Marco Baldi
Quasi-Cyclic Moderate-Density Parity-Check (QC-MDPC) codes are a family of error correcting codes admitting parity-check matrices composed of sparse circulant blocks. QC-MDPC codes have been used for the design of BIKE, one of the finalists in the NIST competition for the standardization of post-quantum cryptography. Decoding of QC-MDPC codes with cryptographically relevant parameters is intrinsically bound to fail, resulting in a decoding failure rate (DFR) that is nonzero. To achieve INDistinguishability under Adaptively Chosen Ciphertext Attacks (IND-CCA2), the DFR must not exceed $2^{-\lambda}$, with $\lambda$ being the security parameter. QC-MDPC codes are customarily decoded with a Bit Flipping (BF) algorithm. Especially at very low DFR values, error patterns having a large intersection with near-codewords (which are vectors corresponding to columns of the parity-check matrix, up to some shift) are the main cause of decoding failures. In this paper, we show how a BF decoder can be tweaked to exploit the knowledge about near-codewords. Since error vectors that cause decoding failures are likely making the decoder converge to the closest near-codeword (i.e., to the near-codeword with the largest amount of overlapping positions with the error vector), we exploit such a harmful but predictable behavior: we let the decoder recognize, and consequently correct, syndromes of near-codewords. This modification comes with a very mild computational overhead and can be applied to any BF decoder. As a concrete application, we focus on BIKE parameters for NIST security category 1. We show that a recently proposed BF variant called $\textsf{BF}\text{-}\textsf{Max}$ outperforms significantly the two decoders used by BIKE within the NIST competition, achieving a significantly lower DFR with a comparable computational complexity.
Last updated:  2026-08-05
Forget-IT: Optimal Good-Case Latency For Information-Theoretic BFT
Ittai Abraham, Sourav Das, Yuval Efron, and Jovan Komatovic
The good-case latency of a consensus protocol measures the latency from block proposal by a consensus leader to decision, in the case in which the leader is correct. It is arguably the efficiency metric most pertinent for discussing the practical latency performance of consensus protocols. Well understood in the context of the authenticated setting, with PBFT [Castro 99], Tendermint [Buchman 16] & Simplex [Chan, Pass 23] achieving the optimal good-case latency of 3 rounds, significant gaps remain in the unauthenticated setting. We present Forget-IT, an unauthenticated consensus protocol with optimal good-case latency of 3 rounds. Furthermore, our protocol only requires constant persistent storage, and has $O(n^2)$ message complexity per view.
Last updated:  2026-08-05
A Systematic Literature Review on Optimising CRYSTALS-Dilithium (ML-DSA) Performance for IoT Devices via Lightweight Hashing
Ceasar Njuguna Ngunu and Edward Ombui
Background: The migration to post-quantum cryptography confronts resource-constrained Internet of Things (IoT) devices with a material performance cost. CRYSTALS-Dilithium, standardised as the Module-Lattice-Based Digital Signature Algorithm (ML-DSA) in FIPS 204, fixes the Keccak-based SHAKE functions as its only symmetric primitives, and profiling on embedded platforms identifies hashing as the largest single contributor to the scheme’s software cost. This review synthesises the performance evidence for ML-DSA on constrained platforms, classifies the optimisation strategies pursued in the literature, and tests whether any published work substitutes a standardised lightweight extendable-output function for SHAKE within the scheme. Methods: Following Kitchenham’s guidelines and the PRISMA 2020 statement, we searched IEEE Xplore, the ACM Digital Library, Scopus, and SpringerLink for peer-reviewed studies published from January 2020 onwards, complemented by backward and forward snowballing and by targeted update searches through July 2026. A protocol was prepared in advance of the search. From 115 database records and 22 records identified through other methods, 40 primary studies met the inclusion criteria. Results: On the ARM Cortex-M4, optimised software implementations of Dilithium3 require 10,667 kilocycles on average for signing and 2,321 kilocycles for verification; on the Cortex-M7, Dilithium-2 verification averages 1,429 kilocycles (6.6ms at 216MHz), with signing spanning 1,835 to 16,440 kilocycles due to rejection sampling. Optimisation efforts fall into four categories: hardware acceleration, platform-specific software optimisation, protocol-level adaptation, and optimisation of the incumbent Keccak primitive itself. Architecture-specific Keccak optimisation reduces hashing’s share of Dilithium’s runtime on the Cortex-M4 by only 2.46 to 5.03 percentage points, indicating that the bottleneck largely survives direct attack. Replacing Keccak with Ascon inside the sibling scheme Kyber yields a 24 to 25% cycle reduction and a 2 to 8% memory reduction on the Cortex-M4. No peer-reviewed study applies this substitution to ML-DSA. Conclusions: With FIPS 204 and NIST SP 800-232 both final, the cost of ML-DSA’s primitive choice on constrained platforms is a well-posed and unanswered question on both sides. We specify a per-call-site Dilithium–Ascon evaluation, including its security constraints and non conformance status, as the priority direction for software-only optimisation of post-quantum signatures on IoT devices. Keywords: post-quantum cryptography; ML-DSA; CRYSTALS-Dilithium; Ascon; lightweight cryptography; Internet of Things; systematic literature review
Last updated:  2026-08-05
DuetORAM: Two-Server Distributed ORAM with Constant Rounds and O(log N) Communication
Feng Li, Xiangfu Song, Yingying Li, Lisha Yao, Guomin Yang, Tianwei Zhang, and Robert H. Deng
Distributed Oblivious RAM (DORAM) is a promising building block for privacy-preserving cloud databases and outsourced storage systems. However, existing two-server designs often rely on slow linear scans or heavy cryptographic primitives, making them struggle to balance efficiency and bandwidth, and thus hindering their practical deployment. We present DuetORAM, a two-server DORAM that achieves constant-round access with $O(\log N)$ communication while avoiding these computational bottlenecks. Our key idea is a replicated-to-shared block encoding that allows servers to keep identical ciphertexts for efficient PIR-based retrieval, while locally interpreting them as secret shares to enable oblivious eviction via a lightweight shuffle. We further design a secret-shared shuffle with an offline-online decomposition that shifts most bandwidth-intensive work to a preprocessing phase, significantly reducing online communication. We implement a prototype of DuetORAM and evaluate it under diverse network conditions. Our results show that DuetORAM outperforms both the state-of-the-art two-server scheme DUORAM (reducing retrieval latency by up to 170$\times$ in LAN settings), and three-server design S$^3$ORAM (reducing retrieval latency by 1.7$\times$ in LAN and accelerating eviction by 7$\times$ in LAN and 5$\times$ in WAN, respectively).
Last updated:  2026-08-05
DYNAFIX: Dynamic Fixed‑Point Encoding for Arbitrary‑Range MPC
Yuntian Chen, Tianpei Lu, Zhanyong Tang, Bingsheng Zhang, Wenjing Yang, Zhuzhu Wang, and Kui Ren
Privacy-preserving computation over real numbers typically employs either floating-point or fixed-point arithmetic. While fixed-point methods are highly efficient, they struggle to handle wide dynamic ranges. Conversely, floating-point methods support a much larger numerical scope but incur overheads more than a hundred times higher than their fixed-point counterparts. In this paper, we propose DYNAFIX, a dynamic fixed-point computation scheme that strikes a balance between floating-point and fixed-point arithmetic. Compared to traditional fixed-point approaches, our scheme supports an arbitrary numerical range; compared to floating-point computation, it maintains performance comparable to fixed-point execution. Experimental results demonstrate that our method achieves a $24.1\times$ speedup over the state-of-the-art when evaluating high-precision functions, such as the exponential function.
Last updated:  2026-08-05
Beyond Affine Invariants: A Hamming-Weight Correlation Metric for Template-CPA Leakage in Key-Dependent S-boxes
Wiesław Maleszewski
Classical selection criteria for cryptographic S-boxes—nonlinearity $\mathrm{NL}$, differential uniformity $\delta$, boomerang uniformity $\beta_{\mathrm{B}}$, algebraic degree $\deg$—are invariants of affine equivalence. That property is exactly what blinds them to a class of side-channel weaknesses. The correlation-power-analysis (CPA) template distinguisher is governed by the Hamming-weight functional, and Hamming weight is not affine-invariant; it does not descend to the affine-equivalence quotient on which the classical criteria live. Two S-boxes with identical $(\mathrm{NL},\delta,\beta_{\mathrm{B}},\deg)$ can therefore leak differently under template CPA. We make this precise for the key-dependent family $S^{\mathcal{G}}(x)=A\,\iota(x)\oplus c$, with $\iota$ the multiplicative inverse in $\mathrm{GF}(2^8)$ and $(A,c)\in\mathrm{GL}(8,\mathbb{F}_2)\times\mathbb{F}_2^8$ drawn from a byte stream $\mathcal{G}$. A structural proposition fixes the four invariants at $(112,4,6,7)$ across the entire family; they carry no information about $\mathcal{G}$. We introduce the Hamming-weight template correlation $\rho_{\mathrm{HW}}(\cdot,S_{\mathrm{AES}})$, identify it as the population statistic controlling the AES-template CPA distinguisher, and show that it resolves the fiber the classical invariants collapse. As a stress test we instantiate $\mathcal{G}$ with three sources of contrasting regularity—a system CSPRNG, a discretised logistic map, and a $\sin(1/x)$/xxHash hybrid—and sample $3\times10^{5}$ S-boxes from a single master seed. The classical invariants are identical everywhere, as predicted. The metric is not. The logistic source widens the $\rho_{\mathrm{HW}}$ distribution against $S_{\mathrm{AES}}$ by $12$–$13\%$ ($\sigma_\ell=0.0704$ vs. $0.0626/0.0623$; Levene $p<10^{-180}$). The widening vanishes against a uniform-random reference permutation (Levene $p>0.13$), survives an exact Q1.31 fixed-point reimplementation at $3.1\%$, and does not appear for a tent-map control. Propagated through the Mangard–Oswald–Popp trace-budget model and checked against a $2.16\times10^{5}$-attack Monte-Carlo CPA simulation, it yields a $29\%$ relative excess in AES-template success rate at $\mathrm{SNR}=10$, $N=10^3$ (empirical ratio $1.29$, analytic $1.26$). By every standard effect-size measure the widening is small (Cohen's $d=0.128$ on $|\rho_{\mathrm{HW}}|$, Cohen's $h=0.130$ on the attackable fraction); its significance is detectability, not magnitude. The contribution is a measurement axis, not a weak generator: a metric that flags template-CPA leakage where $\mathrm{NL}=112$, $\delta=4$ report perfect scores.
Last updated:  2026-08-05
Privacy-Preserving Inclusion Lists
Zhengwei Tong, Saba Eskandarian, and Kartik Nayak
Blockchains aim to provide open access and censorship resistance, but centralization of block production in blockchains like Ethereum undermines these goals. Inclusion List (IL) protocols mitigate this by requiring block proposers to include transactions selected by an IL committee to enforce the inclusion of transactions that appear to have been censored. However, protecting the confidentiality of individual committee members’ contributions is essential to prevent retaliation and ensure robust censorship resistance. We propose a lightweight, privacy-preserving inclusion list protocol that allows committees to collectively construct transaction lists while hiding individual contributions and ensuring plausible deniability. Our approach builds on multiparty computation (MPC) techniques to achieve strong privacy without relying on heavyweight cryptography or anonymous broadcast channels. We implement two variants of our protocol design: an optimistic version providing malicious security with abort (latency $\sim 4.0$s) for speed, and a robust variant (latency $\sim 124.7$s) for guaranteed output delivery in the presence of a Byzantine threshold of $t < n/3$ malicious parties.
Last updated:  2026-08-05
Private Identity-based Bulletin Boards for Anonymous Messaging and Other Online Services
Karim Eldefrawy, Stanislaw Jarecki, Ben Terner, and Gene Tsudik
Secure and anonymous messaging has many compelling use-cases and is becoming increasingly popular. In this paper, we consider it in the context of delay-and-disruption-prone networks, which are characterized by handicapped network access, disrupted operation, censorship, and intermittent network outages. With such settings in mind, we define and design a Private Identity-Based Bulletin Board (PIB^3) scheme, which allows users to anonymously post and retrieve messages to and from a distributed database, and supports communication between users without pre-established setup or pre-exchanged keys. Anyone can encrypt a message for an identity and public epoch, such that only the party with the decryption key for that identity can identify, retrieve, and decrypt the message. Against one corrupted non-colluding PIB^3 server, the server learns neither the recipient identity nor the retrieved record indices beyond the leakage explicitly modeled by the scheme: the public epoch, the database size, and the number of retrievals made by the receiver. If retrieval-count privacy is required, retrievals can be padded to a fixed bound. The multi-server construction extends this guarantee to larger server sets, and gives coalition privacy whenever the underlying multi-server PIR scheme is private against the corresponding coalition. Contributions of this work are: (1) formally defining functionality and security requirements for PIB^3-s, (2) defining and constructing a Hierarchical Identity-based Encryption (HIBE) scheme with searchable ciphertexts, which serves as a building block for the proposed PIB^3 scheme and may be of independent interest, (3) designing an efficient PIB^3 scheme that can be realized with $n\geq 2$ servers based on the HIBE scheme with searchable ciphertexts combined with additional primitives, and (4) implementing a functional PIB^3 prototype which demonstrates practicality of the entire concept and allows us to assess its performance empirically.
Last updated:  2026-08-05
Order Auctions with Private Position Preferences
Ruijie Wang and Aviv Yaish
We study auctions where two positions are sold to unit-demand bidders with private heterogeneous order preferences: some are specialists who value only the first position, while others are generalists indifferent between the two. First, we consider a first-price rule which allocates the first and second items to the highest and second-highest bidders, respectively. We show that no strategy profile ex-post implements the efficient allocation at every type profile, irrespective of payments, and provide a distribution-free equilibrium welfare guarantee of 1/2. To augment this result, we prove that for deterministic one-round auctions and discrete bids, the efficient allocation requires each bidder to communicate at least one bit more than its bid's binary representation. We next ask what the same bit accomplishes in winner-pays-bid formats where bidders can also specify specific item preferences. In particular, we show that this strengthens our distribution-free equilibrium welfare guarantee to 1-1/e. Finally, we discuss the applicability to priority service, blockchain transaction ordering, and cloud compute and artificial intelligence (AI) marketplaces.
Last updated:  2026-08-04
Algorithmic Optimization of the Gaussian Sampler in the FN-DSA Post-Quantum Signature Scheme
Nicolas HOULÈS and Thibaut Heckmann
The post-quantum signature scheme Falcon (FN-DSA), currently being standardized by NIST as FIPS 206 (Initial Public Draft submitted August 2025, final standard expected 2026-2027), relies on a discrete Gaussian sampler whose critical bottleneck is the function fpr_expm_p63, computing $\lfloor \exp(-x) \cdot 2^{63} \rfloor$ for $x \in [0, \ln 2)$. While the reference implementation already employs a degree-12 fixed-point polynomial (FACCT), no segmented approximation has been studied for this specific function, nor has empirical timing security been published on ARM Cortex-M3 (emulated or physical). This paper presents a systematic study of piecewise polynomial approximation applied to fpr_expm_p63, combining the Remez exchange algorithm (computed with 50 decimal digits of precision via mpmath), fixed-point arithmetic, and Horner evaluation. Two configurations are implemented and evaluated: a 32-segment degree-6 approximation at scale $2^{62}$ targeting x86-64, and a 16-segment degree-3 approximation at scale $2^{31}$ (256-byte LUT) targeting ARM Cortex-M3 IoT devices without hardware floating-point unit (FPU). Against the authentic FACCT reference from Falcon's fpr.c, ported verbatim to ARM Cortex-M3 (emulated via QEMU user-mode with arm-linux-gnueabi -mfloat-abi=soft), our implementation achieves a $1.28\times$ median speedup across 30 independent runs (range $1.24\times$ to $1.33\times$), measured with a rigorous anti-noise protocol combining batch measurement, aggressive warm-up, ref/opt interleaving, and percentile filtering (P5-P95). DUDECT timing leakage tests confirm that both the FACCT reference (t-score $\in [0.05, 2.51]$) and our implementation (t-score $\in [1.99, 5.24]$) remain within statistical safety thresholds in the vast majority of runs (FACCT: 30/30; optimized: 27/30). Static instruction-level analysis via objdump disassembly provides deterministic constant-time evidence: zero data-dependent conditional branches, zero FPU instructions, and zero soft-float calls, yielding a branchless fixed-point Horner core; however, the full constant-time claim is limited to the tested compilation target and memory model. To the best of our knowledge, this constitutes the first comparative study of segmented versus global polynomial approximation for fpr_expm_p63 in the FN-DSA context, and the first empirical DUDECT measurement of this function on emulated ARM Cortex-M3 against the authentic FACCT reference. Physical hardware validation on STM32F103 is identified as future work.
Last updated:  2026-08-04
Distributed Monotone Policy Encryption with Stronger Security for DNFs and Threshold Policies from Lattices
Rishab Goyal and Saikumar Yadugiri
Distributed monotone-policy encryption (DPE) lets each user sample and publish its own key, after which anyone can encrypt to a list of published keys under a monotone access policy that determines which coalitions can decrypt. Silent threshold encryption is the $t$-out-of-$N$ special case. What makes the primitive non-trivial is compactness, where the ciphertext stays sublinear in the policy description. Every post-quantum DPE scheme so far settles for selective security, fixing the challenge policy and the corrupted positions before setup, and complexity leveraging cannot close the gap without giving up compactness. The one DPE scheme known in the stronger static model, where the policy and the placement of malicious keys are chosen adaptively, relies on witness encryption (Devadas-Jain-Waters-Wu, Asiacrypt'25). We give the first statically secure DPE schemes from falsifiable lattice assumptions. For DNF policies, ciphertexts are of size $\mathsf{poly}(\lambda, \log N)$, independent of the number and widths of the clauses, and public keys, secret keys, and partial decryptions are of size $\mathsf{poly}(\lambda)$. For $t$-out-of-$N$ threshold policies, ciphertext of size $\tau^6 \cdot \mathsf{poly}(\lambda)$ for $\tau = \min(t^2, N - t)$, improving to $\tau^2 \cdot \mathsf{poly}(\lambda)$ given a common reference string. We prove security under decomposed LWE, and the improved threshold parameters under succinct LWE, in the random oracle model. Our constructions generalize the equivocal encryption framework of Goyal-Yadugiri to policies. We define equivocal DPE, which simulates public keys and partial decryptions and withholds the equivocation trapdoor while releasing the public coins that accompany a ciphertext, and compiles to static DPE with no loss in parameters.
Last updated:  2026-08-04
Efficient Large-Integer Arithmetic for FHE
Ahmad Al Badawi, Andreea Alexandru, Gurgen Arakelov, Charles Gouert, Sergey Gomenyuk, Valentina Kononova, Yarkın Doröz, and Yuriy Polyakov
Fully Homomorphic Encryption (FHE) has emerged as one of the key technologies for privacy-preserving computation, enabling arbitrary computation directly on encrypted data. Vectorized FHE schemes, such as Brakerski/Fan--Vercauteren (BFV), Brakerski--Gentry--Vaikuntanathan (BGV), and Cheon--Kim--Kim--Song (CKKS), are typically used in applications dealing with large datasets, for example, confidential database queries and private ML inference. These FHE schemes are based on the computational hardness of Ring Learning with Errors (RLWE) and share a common algebraic foundation: arithmetic over high-dimensional polynomial rings with coefficient moduli spanning hundreds or thousands of bits, far exceeding the native arithmetic capabilities of modern processors. This article surveys the evolution of large-integer arithmetic in RLWE-based FHE libraries, with a focus on the Residue Number System (RNS) techniques used in practically all modern implementations. We give a formal treatment of the two fundamental RNS building blocks --- basis extension and scaling --- that require information about the magnitude of a large value and are therefore incompatible with a purely residue-wise view of arithmetic. We contrast the two principal algorithmic approaches to these operations: the integer-only approach of Bajard, Eynard, Hasan, and Zucca (BEHZ), which tolerates approximation overflows and corrects them with auxiliary redundant moduli, and the floating-point approach of Halevi, Polyakov, and Shoup (HPS). We then show how these primitives compose into the higher-level RNS procedures used across all vectorized RLWE schemes and review how their adoption reshaped the architecture and performance of libraries such as HElib, SEAL, PALISADE/OpenFHE, HEAAN, and Lattigo. We give particular attention to the scaling error inherent in the original Full RNS variant of CKKS, and to the more recent techniques --- reduced-error scaling, composite scaling, and grafting --- that eliminate it or restore flexible, high-precision rescaling from within the residue representation. We also cover GPU-accelerated implementations and close by discussing a renewed, and so far exploratory, interest in positional (non-RNS) representations, raising the question of how such approaches might compare with the Full RNS variants that dominate FHE implementations today.
Last updated:  2026-08-04
BORG: Extendable Distributed Vector Commitments from Reconfigurable Erasure Codes
Nicolas Alhaddad, Eran Tromer, and Mayank Varia
Updatable vector commitments let users store and authenticate values contained within an evolving data vector. Existing work on updatable vector commitments studies how clients can store only the values and authentication proofs relevant to them, and can refresh stale opening proofs, with the help of an online maintainer that keeps the current vector and proof state. This work studies the complementary problem: how to decentralize the maintainer, in order to distribute the cost and availability requirements. We formalize this problem as extendable distributed vector commitments (EDVC). A public control plane, such as consensus or a trusted party, determines batches of updates and extensions of stored vector. Maintainers accept and apply a batch only after validating it against the current authenticated state. The resulting state is stored across many maintainer nodes, each of which holds a publicly assigned coded data fragment and updates it non-interactively. A stale client can obtain the current state, and a fresh authenticated opening, from the current maintainers (without replaying the updates history). We construct the first EDVC protocol, called Borg, from two components: a sparse vector commitment, and a coded storage layer that can be updated by linear operations. This construction applies when all active positions lie within a known growing prefix of the vector. We then construct a coded storage layer with the operations needed for this setting, including single-position openings, aligned range openings, public updates, adding new nodes, repairing failed nodes, and moving storage responsibilities between nodes. This is then used to flexibly distribute the data alongside a sparse Merkle tree for authentication. Our construction is particularly simple when the maintained data is an append-only public log (e.g., a blockchain’s block archive, or certificate transparency logs). In this setting, distributed updates to the data and its authentication structure can be made just by broadcasting the new log entries, with no coordination across maintainer nodes. We empirically evaluate maintainers’ cost for various workflows, showing that nodes can process hundreds of thousands of updates per second. We also show that node addition, repair of lost local state, and changes to the proof-serving threshold can all be supported efficiently.
Last updated:  2026-08-04
Compact Verifiable Shuffles for ElGamal Ciphertexts
Yuxi Xue, Xingye Lu, and Man Ho Au
A verifiable shuffle proves that output ciphertexts are a rerandomized permutation of the inputs without revealing the permutation or rerandomization factors. It is a core primitive in mix-nets for electronic voting and blockchain-based anonymization, where each mix server publishes an auditable proof. Existing deployed schemes typically have proof size $O(N)$ or $O(\sqrt{N})$ in the number of ciphertexts $N$, making shuffle proofs a major bandwidth cost. We present a logarithmic-size verifiable shuffle for ElGamal ciphertexts. The logarithmic term in our proof size is one third of that in the previously known logarithmic construction for the same shuffle relation by Hoffmann et al. (CCS 2019). Our protocol is public coin, non-interactive via the Fiat--Shamir transform, and relies on an updatable structured reference string that can be generated once in a powers-of-tau ceremony and reused across applications. We implement the protocol in Rust and provide, to our knowledge, the first benchmarks for a logarithmic-size ElGamal shuffle. At \(N=2^{20}\), the proof is 2.6 KiB. In a four-server mix-net election, the four shuffle proofs occupy approximately 10.6 KiB in total, excluding ballot-validity and decryption proofs.
Last updated:  2026-08-04
UFOs: A Very Efficient Multivariate Public Key Signature Scheme
Gilles Macario-Rat
We present UFOs, a multivariate public-key signature scheme in the Unbalanced Oil and Vinegar (UOV) family. The scheme replaces generic quadratic polynomials with a structured subclass based on Frobenius-type quadratic forms, yielding a compressed public-key representation while retaining the efficient UOV signing procedure. We describe the key-generation, signing, and verification algorithms, and we detail the derivation of the public system from a compact secret description. We discuss security in the standard multivariate setting, including direct algebraic attacks and key-recovery approaches, and we formalize the underlying computational problems induced by the proposed structure. Finally, we report implementation results quantifying the costs of key generation, signing, and verification, as well as the resulting public-key and signature sizes.
Last updated:  2026-08-04
Algebraic Analysis of Homomorphic Trace Evaluation and Its Applications
Han Xia
Field trace evaluation has emerged as a powerful tool in fully homomorphic encryption, with broad applications ranging from bootstrapping algorithms to privacy-preserving protocols. Recent advances have significantly reduced its noise growth by combining tower-based evaluation strategies with rescaling operations. However, existing analyses rely on uniform noise bounds that fail to capture the actual noise behavior across different coefficients, leading to substantial gaps between theoretical estimates and empirical observations. In this work, we present a refined algebraic analysis of trace evaluation over power-of-two cyclotomics that uncovers structured cancellation effects among noise coefficients induced by subsequent linear operators, in particular the trace mappings of subextensions. We show that, except for the constant term, the variance of each output noise coefficient depends on the 2-adic valuation of its index, yielding bounds that improve upon prior uniform estimates by a factor of $O(\log n)$ both for non-constant coefficients and after a subsequent plaintext-ciphertext multiplication, where $n$ is the ring degree. We further extend our analysis to two typical algorithmic applications of trace evaluation. For ciphertext packing, we derive a non-recursive formulation that admits a cleaner structure and slightly tighter noise estimates. For coefficient extraction, our coefficient-wise analysis improves upon prior uniform variance bounds by factors ranging from $\Theta(n)$ to $\Theta(n^2)$ for non-constant coefficients and by a factor of $O(n)$ after post-multiplication. Experimental results confirm that the observed noise variances follow the coefficient-wise pattern predicted by our analysis and demonstrate pronounced improvements over existing estimates, providing effective guidance for parameter selection and system configuration in practice.
Last updated:  2026-08-04
Design and Analysis of Quantum Designated Verifier Signature Scheme
Shanu Poddar and Vikas Srivastava
Designated Verifier Signatures (DVS) are an important variant of digital signatures that ensure only a specified verifier can validate a signature, while preserving non-transferability. With the advent of quantum computing, several quantum DVS schemes have been proposed to achieve quantum security. In this paper, we revisit the quantum DVS protocol of Xin et al. [Quantum Information Processing, 2022] and provide a structural cryptanalysis of its design. We show that the scheme admits an existential forgery under a chosen-message attack: given a valid quantum signature on one message, an adversary can efficiently transform it into a valid signature on another message without knowledge of the signer’s private key. To address this weakness, we propose a minimal countermeasure based on QKD-derived keys and quantum one-time pad encryption.
Last updated:  2026-08-04
Subfield attack: leveraging composite-degree extensions in the Quotient Ring transform
Pierre Pébereau
The VOX signature scheme is a multivariate signature scheme which was submitted to the Round 1 Additional Digital Signature Schemes NIST process. VOX relies on the Hat Plus perturbation and the Quotient-Ring transform (QR). We formalize a dimension criterion enabling the direct attack to be used as a key recovery attack against UOV schemes. This enables a practical cryptanalysis of the Round 1 VOX parameters. Next, we show that some of the alternative parameters proposed for VOX after attacks on the Round 1 submission are still vulnerable. More precisely, these parameters were chosen to defeat an attack of Furue and Ikematsu in the field extension defined by the QR parameter. We observe that one may use a smaller field extension of any degree dividing the QR parameter, in which case the attacks apply again. These attacks are relevant for a subset of the parameter sets proposed for VOX: I, Ic, III, IIIa, V, Vb. In particular, we apply the subfield framework to our previous dimension criterion for the direct attack. We estimate the cost of our attack on these parameter sets and find costs of at most 2^67 gates, and significantly lower in most cases. In practice on a commercial laptop, our attack requires 0.3s, 1.35s, 0.56s for parameter sets I, III, V for VOX, and 56.7s, 6.11s for the alternative parameter sets IIIa, Vb. Our analysis also improves the cryptanalysis of some alternative parameters proposed by Guo and Ding, and of the ``Minus'' variant of VOX.
Last updated:  2026-08-04
SoK: Verifiable Integrity Claims for Privacy-Preserving Federated Learning
Andrea Rizzini, Marco Esposito, Tommaso Gagliardoni, and Francesco Bruschi
Federated Learning (FL) is an advancement in Machine Learning motivated by the need to preserve the privacy of the data used to train models. While it effectively addresses this issue, the multi-participant paradigm on which it is based introduces several challenges. Among these are the risks that participating entities may behave dishonestly and fail to perform their tasks correctly. This misbehavior, in turn, also threatens privacy, because an undetected deviation in training or aggregation can silently undermine the confidentiality guarantees that FL was designed to provide. This motivates mechanisms that provide checkable evidence that released checkpoints are consistent with a declared learning specification and an auditable execution trace. In this SoK, we model federated learning as an append-only transcript of submissions, admissions, aggregation, and finalization events, and formalize verifiability as a collection of integrity claims issued by clients and the aggregator, and checked by different verifier classes. We derive a taxonomy of recurring client-side and aggregator-side claims and use it to analyze representative verifiable FL (VFL) systems spanning Zero-Knowledge Proofs (ZKP) and Trusted Execution Environment (TEE) technologies. Our analysis suggests that, while verifiable aggregation is comparatively mature, data verifiability appears feasible but still sparsely adopted in practice, and verifiable training remain costly and rarely scale to modern models.
Last updated:  2026-08-04
Embedded Elliptic Curves and Embedded Families for SNARK-Friendly Elliptic Curves
Aurore Guillevic and Simon Masson
In 2021, Masson, Sanso, and Zhang introduced the Bandersnatch curve associated to the BLS12-381 pairing-friendly curve, an elliptic curve designed for zero-knowledge proofs requiring circuits with a curve arithmetic. This type of curve is useful for privacy-preserving protocols, and more generally for succinct validity proof using pairing-based SNARKs. An embedded curve is defined over a field whose order is the group order of its associated curve. In this way, the pairing-friendly curve is used to express a zero-knowledge proof (such as a SNARK) of a statement taking place on the embedded curve. Contrary to the previous embedded curves (such as CØCØ, JubJub), Bandersnatch was built with the complex multiplication (CM) method, in order to ensure a very small discriminant (-8, whose magnitude is small), and thus efficient scalar multiplication thanks to the GLV technique. The algorithm provided by Masson, Sanso, and Zhang for searching this type of curves requires computation of Hilbert class polynomials, making the search of curve slow. It was not known whether Bandersnatch was an exceptional curve or whether comparable curves exist, of larger discriminants. This paper highlights the technicalities of the CM method already in use in the 90s to generate curve parameters of chosen order. This old technique allows revisiting the curve search of Bandersnatch, providing a dramatic speed-up improvement. This paper presents two algorithms: one to generate embedded elliptic curves of SNARK-friendly elliptic curves, with a variable discriminant; a second to generate families (parameterized by polynomials) with a fixed discriminant. When the (negative) discriminant is -3 modulo 4, it is possible to obtain a prime-order curve, and form a cycle. To illustrate this, we apply the technique first to generate more embedded curves like Bandersnatch with BLS12-381, such as a curve of discriminant -6673027, defining a plain twist-secure cycle. We also comment on the scarcity of Bandersnatch-like CM curves, and recall that with this generic algorithm, it is only a question of core-hours to find them. Second, we show the link between a paper of Ben Smith in 2015 and the work of Dai, Lin, Zhao, and Zhou in 2023, obtaining prime-order parameterized families of embedded curves of fixed discriminant, such as -3 for BLS and KSS18 curves. With KSS16 curves, the discriminant -4 is also possible (the curve has an even order). The technique can work with any KSS, Scott--Guillevic, Gasnier--Guillevic, or other fixed-discriminant parameterized family of pairing-friendly curves. This paper provides a more general point of view on embedded curves such as Bandersnatch, putting into perspective the works of Masson, Sanso, and Zhang, and Sanso and El Housni. The Python/SageMath scripts are available at https://gitlab.inria.fr/zk-curves/cm-embedded-curves/.
Last updated:  2026-08-04
Survey: Six Years of Neural Differential Cryptanalysis
David Gerault, Anna Hambitzer, Moritz Huppert, and Stjepan Picek
At CRYPTO 2019, A. Gohr introduced Neural Differential Cryptanalysis and used deep learning to improve the state of the art in cryptanalysis of 11-round SPECK32. As of February 2025, Gohr’s article has been cited 238 times on Google Scholar. The variety of targeted cryptographic primitives, techniques, settings, and evaluation methodologies that appear in these follow-up works provides a basis for a careful survey, which we provide in this paper. More specifically, we propose a taxonomy of these 238 publications and systematically review the 71 papers focusing on neural differential distinguishers, pointing out promising directions and recent advances in explainability and key-recovery attacks. We then highlight future challenges in the field, particularly the need for improved comparability of neural distinguishers and advancements in scaling. This holistic survey helps researchers and engineers to identify the leading neural differential attacks, compare their performance, and highlight the outstanding open problems in AI-assisted cryptanalysis.
Last updated:  2026-08-04
Power side-channel leakage distinguishers on LESSv2.0 - Exploiting sparse columns in Gaussian Elimination
Maciej Czuprynko, Rishub Nagpal, Tobias Schneider, and Sujoy Sinha Roy
We present the first passive side-channel distinguisher on LESSv2.0, a second-round candidate in NIST’s call for additional post-quantum digital signature schemes. We target the Gaussian elimination at the core of LESS and and present a method to exploit algorithmic leakage arising from the manipulation of sparse versus dense columns. We show that this leakage, while trivially available in non-constant-time implementations, also persists in constant-time implementations and can be exploited using a distinguisher. Concretely, the proposed attack relies only on distinguishing zero-valued computations from random ones that are repeatedly evaluated during the computation, leading to a large attack surface and making the attack robust to noise. Through simulation, we experimentally show that the required number of observed signatures lies between 300 and 2357 depending on the parameter set. This relatively large number is due to the targeted information being inherently noisy, leading to a correlation-based key recovery attack, even with noiseless leakage. Furthermore, we discuss three common countermeasures: first-order masking, shuffling and blinding. Finally, we validate our approach on implementations with and without masking by showing the presence of leakage on a physical target.
Last updated:  2026-08-04
Paras: Actively Secure Two-Server Private Histograms
Dimitris Mouris, Lucas Piske, Pratik Sarkar, Ni Trieu, and Mehmet Ugurbil
Private histogram computation is a fundamental building block for many data analytics tasks, enabling frequency analysis without revealing individual inputs. Existing protocols achieving robustness against malicious clients and servers typically require three servers with limited adversarial tolerance, restricting practicality. In this work, we present Paras, the first two-server protocol for private histogram computation that achieves robustness against collusion between a malicious server and arbitrarily many malicious clients. Paras builds upon distributed point function-based approaches and introduces novel consistency checks leveraging vector oblivious linear evaluation (VOLE) to enforce both input correctness and output integrity. To realize these checks, we design two new cryptographic primitives: (1) aBV, an authenticated bit verification protocol that ensures VOLE committed shares correspond to valid bits, and (2) adIPA, an authenticated double inner product argument that enables secure consistency checks across two different VOLE sessions. These primitives may be of independent interest for other secure computation tasks. We show that Paras is highly efficient and scalable: clients incur minimal cost independent of domain size, while servers achieve low per-client runtime, communication, and storage even at scale. For example, with 8192 clients over a domain of 128 inputs, each server requires only 14 ms runtime and 24 KB communication per client.
Last updated:  2026-08-04
One Discrete Gaussian Sample in $2^{n/2+o(n)}$ Time
Jiseung Kim
Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS; STOC 2015) sample $2^{n/2}$ discrete Gaussians at an arbitrary parameter in $2^{n+o(n)}$ time, and above smoothing in $2^{n/2+o(n)}$ time. They ask whether the latter bound suffices for one sample at an arbitrary parameter. We answer this question affirmatively: for every rank-$n$ lattice $L\subseteq\R^n$ specified by a rational basis and every rational $s^2>0$, we produce one sample from $D_{L,s}$ within statistical distance $\exp(-\Omega(n^3))$ in expected $2^{n/2+o(n)}$ time and $2^{n/2+o(n)}$ space on every execution. The algorithm samples from random superlattices that are smooth at the required scale with constant probability and outputs the first point in $L$; a Gaussian-mass comparison shows that the $2^{n/2}$ samples produced by one ADRS call contain a point of $L$ with inverse-polynomial probability. The factor $2^{n/2}$ is tight in this Gaussian-mass comparison. For every fixed rational $\alpha<1.4697$, the same comparison gives a sub-$2^n$ algorithm for exact CVP on targets satisfying $\dist(y,L)\le\alpha\lambda_1(L)$, without a uniqueness assumption, and an exact-SVP algorithm in $2^{0.7315n+o(n)}$ time.
Last updated:  2026-08-04
zk-Cinema: Proving Video Provenance in Zero Knowledge
Alexander Frolov, Jianfeng Guo, Xinyi Zhao, Trisha Datta, Dan Boneh, and Ian Miers
Video provenance is an important problem on the modern internet. In response, the Coalition for Content Provenance and Authenticity (C2PA) has developed a standard for verifying video and image provenance where cameras sign captured videos with an on-device secret key. Since videos are generally edited and resized before be- ing posted, the C2PA signature from a camera cannot be used as is to verify provenance of published videos. Prior work has developed zero-knowledge techniques for verifying provenance of edited im- ages and videos. In this work, we develop new efficient techniques for producing such zero-knowledge proofs. First, we show how to represent common video edits as matrix multiplications in a form that is particularly friendly for zero-knowledge provers and enables a number of optimizations. Second, we develop a SNARK-friendly video representation, which we call sfvr, that reduces prover work for video editing. Third, we design new efficient methods for incor- porating signed data into a SNARK proof. To evaluate our designs, we built an end-to-end system for proving edits to a signed video. In our end-to-end system, we optimize the NeutronNova folding scheme for high-arity folding. To scale the size of our Neutron- Nova proofs, we implement a “Read-Write Streaming” version of NeutronNova to take advantage of high-performance storage and parallel computing resources. Our system achieves competitive performance and scale relative to prior work.
Last updated:  2026-08-04
Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-point Hessian
Minki Hhan
We present randomized algorithms for the shortest vector problem (SVP). For the $n$-dimensional lattice $\mathcal L$, our algorithms solve SVP in time $2^{0.6039n+o(n)}$ classically and $2^{0.5411n+o(n)}$ quantumly and space $2^{0.5n+o(n)}$, improving the previous best algorithm running in $2^{n+o(n)}$ time and space of Aggarwal, Dadush, Regev, and Stephens-Davidowitz [STOC'15]. Our algorithms heavily use the property of the Hessian of the periodic Gaussian function at the half shortest vector: For a shortest vector $v \in \mathcal L$, the Hessian at $v/2$ has the eigenvector close to $v$, which can be used to recover $v$ using the (preprocessing) bounded distance decoding algorithm. Given the periodicity modulo $\mathcal L$, the candidate midpoints are indexed by the parity classes in $\mathcal L/2\mathcal L$. Our algorithm searches for the class of a shortest vector by estimating the corresponding Hessians using discrete Gaussian samples. We optimize the algorithm using random sublattice cosets and various sampling technique, achieving the final complexity. The optimization techniques may be of independent interest.
Last updated:  2026-08-04
Baker: A Privacy-Preserving, NIZK-free and Efficient Payment Channel Hub Supporting Bidirectional Channels
Wenjing Li, Zi Li, Yuan Zhang, and Sheng Zhong
Payment Channel Hub (PCH) improves blockchain scalability by enabling off-chain transactions via an untrusted intermediary known as the tumbler. However, existing PCHs either fail to guarantee the unlinkability privacy or rely on inefficient non-interactive zero-knowledge (NIZK) proofs. Recently, Ge et al. proposed Accio, a privacy-preserving PCH that eliminates the need for NIZK proofs. Nevertheless, Accio only supports unidirectional channels which results in high on-chain costs and routing inefficiencies. In this paper, we present Baker, the first bidirectional payment channel hub that operates without NIZK proofs and guarantees unlinkability. Unlike prior PCH solutions that maintain channel balance using a single state, Baker introduces a novel design in which each non-tumbler user maintains two separate pockets to record the channel balance. To ensure payment atomicity, Baker further designs a novel cryptographic primitive named Aggregatable Adaptor Signature (AAS) to enable atomic signature exchanges and signature aggregation. We implement Baker and empirically demonstrate its advantages over state-of-the-art protocols. Compared to BlindHub, which relies on NIZK proofs for privacy, Baker reduces off-chain communication overhead to 0.0036%. Moreover, the off-chain computation overhead of Baker is 7% of that of BlindHub and 40% of TBPChannel. Relative to Accio, Baker incurs only 80% of its on-chain cost and enjoys a 25% higher average transaction success rate.
Last updated:  2026-08-03
Breaking ADP-Based Witness Encryption
Muhammad El Gebali, Yaroslav Rebenko, Markus Schofnegger, and Lev Soukhanov
Witness encryption (WE) allows one party to encrypt a message under an arbitrary satisfiable circuit, so that anyone holding a satisfying input can decrypt. Efficient WE enables numerous modern applications, such as identity-based and attribute-based encryption. Recent candidates for efficient WE base their security on rank properties of structured ciphertext matrices, which encode the validity of a given witness. This shrinks ciphertext sizes considerably compared to previous constructions, but rests on heuristic arguments rather than security reductions. We describe two attacks against two such constructions, namely the affine determinant program (ADP) construction from 2020 and its arithmetic extension, the AADP, from 2026. The first attack observes that for sparse circuits, the natural regime for both schemes, commutators formed from the public ciphertext matrices have unexpectedly low rank. Elementary linear algebra on these matrices then recovers the encrypted message directly from the public ciphertext, without knowledge of any witness, and hence breaks the security of both schemes. The second attack linearizes the nearly-skew-symmetric (NSS) variant of the ADP construction, recovering the encryption randomness and the message. To our knowledge, ours are the first attacks against these WE candidates, and we verify both in practice.
Last updated:  2026-08-03
HAWK-$n$ Key Recovery Reduces to SVP in Dimension $n/2 + 1$
Zygimantas Straznickas and Stephen A. Weis
HAWK is a lattice signature scheme that is currently a third-round candidate in NIST's post-quantum signature competition. We give an unconditional, deterministic polynomial-time reduction from HAWK-$n$ key recovery over $K_n=\mathbb{Q}(\zeta_{2^\ell})$ to $\mathrm{poly}(n)$ calls to an exact Shortest Vector Problem (SVP) oracle in dimension $n/2+1$, where $n=2^{\ell-1}$ is the ring degree. The reduction uses a nontrivial automorphism of the key lattice, supplied by the Galois involution $\tau:\zeta\mapsto-\zeta$ and recoverable as a shortest vector of a public rank-$n$ lattice isometric, up to scaling, to $\mathbb{Z}^{n/2+1}\oplus\sqrt{2}\,\mathbb{Z}^{n/2-1}$. Ducas's block reduction on this near-hypercubic class finds the automorphism, and the descent of van Gent and Pulles recovers the key from it. In the gate-count model, the attack lowers the key-recovery cost of HAWK-512 from $2^{150}$ to $2^{108}$ and of HAWK-1024 from $2^{288}$ to $2^{182}$. We demonstrate this with a practical implementation that recovers a HAWK-256 secret key end-to-end in a few hours on a single server. The construction does not transfer to Falcon. Conductors $m\in\{p^k,2p^k\}$ ($p$ an odd prime), i.e.\ the $m>4$ with cyclic $(\mathbb{Z}/m)^\times$, evade the attack.
Last updated:  2026-08-03
2PC Memory-Manipulating Programs with Constant Overhead
David Heath
General-purpose secure multiparty computation (MPC) remains bottlenecked in large part by a lack of efficient techniques for handling memory access. We demonstrate a remarkably simple and efficient 2PC instantiation of random access memory (RAM), based on distributed point functions (DPFs, Gilboa and Ishai, Eurocrypt'14). Our semi-honest 2PC protocol can be achieved from oblivious transfer (OT) and a black-box pseudorandom generator (PRG). For a memory storing large enough data words, our 2PC RAM incurs constant communication overhead per access. Like prior works using DPFs to achieve memory access, our work incurs linear computation per access, but per-access communication is lean. Our 2PC RAM is built on top of an obliviousness-friendly model of computation called the single access machine model (SAM, Appan et al., CCS'24). In the SAM model, each memory slot can be read at most once. We present a simple 2PC SAM protocol, where each single-access memory operation incurs at most $O(w + \lambda \lg n)$ bits of communication, where $w$ is the word size, $n$ is the number of memory words, and $\lambda$ is a security parameter. Of this cost, only $2w + 2\lg n$ bits are incurred in the online phase. There are now many oblivious algorithms that compile directly to SAM more efficiently than via a compilation to RAM, and our 2PC SAM can instantiate these algorithms. As one example, we can use our 2PC SAM to implement privacy-preserving graph traversal (DFS or BFS) over a secret-shared size-$n$ graph while revealing nothing beyond the runtime of the SAM program. Our construction achieves online communication $O(n \lg n)$ bits, asymptotically matching the number of bits touched in a corresponding cleartext graph traversal.
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.