Papers updated in last 183 days (Page 9 of 2708 results)
The Graded Monoidal Action for Cryptography
We give a new framework for constructing post-quantum protocols based on graded monoidal actions. An essential difference between the graded monoidal action framework and the cryptographic group action framework is that our higher-rank problems give rise to infinite structures, where elements do not admit inverses, while cryptographic group actions are finite by definition. Nevertheless, we show that the hard problems for cryptographic group actions reduces to the corresponding family of hard problems for graded monoidal actions. However, the main motivation is that for general graded monoidal actions, the relevant problems admit no known subexponential quantum attacks, while still having enough structure to formulate some protocols based on cryptographic group actions, such as the Diffie-Hellman key-exchange.
Our framework can, to the extent we make clear in the paper, be instantiated with the module-action on oriented principally polarized abelian varieties (PPAV's), generalizing the class group action on oriented elliptic curves. Although the theory involving the module-action is quite involved, the formulation of a graded monoidal action is strikingly simple, making it a suitable abstraction for constructing protocols in, which can then be instantiated with the module-action.
Settling Conjectures on Linear Structures of Inverse ChiChi Generalizations Four Proofs and a Counterexample
Belkheyar et al. introduced ChiChi as the even-dimensional, low-latency nonlinear core of ChiLow (Eurocrypt 2025), and Andreoli et al. generalized it into the SWAP and 4-cycle families (ToSC 2025/3), conjecturing five bounds on the linear height and component linear nullity of their inverses, supported by experiments in small dimensions. We settle all five conjectures: Conjectures 1–4 hold for every admissible branch length, and Conjecture 5 is false. In addition, we derive consequences for ChiLow's design and correct one value in the data of Andreoli et al.
AsyncLS: an iUC Framework for Wallet-Based Asynchronous Ledger Services
We define an asynchronous ledger service ($\mathsf{AsyncLS}$) in the IITM-based universal composability (iUC) framework. The wallet-based service exposes a general state machine for a decentralized ledger-based application through registration, reads of committed application state, authenticated submission, and status queries with immutable final results. Each logical request binds the user's authorization to a finalized checkpoint and the applicable execution context. A confirmed outcome identifies the first eligible transaction and records application success or rejection. Strict expiry requires complete processing beyond the eligible height window with no recorded outcome, and certifies that the request has no application effect.
We construct a protocol $\mathbf{\Pi}_{\mathsf{AsyncLS}}$ that realizes the ideal service using four components: Wallet, Relay, Adapter, and Replay. The proof separates the service construction from the implementations of Relay and Adapter while preserving ledger, clock, authentication, and setup interactions. We prove realization for the trusted and local implementations under their respective execution and trust assumptions.
We use the service to construct an ORDI interactive payment and a parameterized execution layer above transaction ordering. These examples distinguish the ledger interaction protocol from the application state and effects exposed by the service. Each use requires the stated authorization, setup, ledger, clock, authentication, and ledger-effect assumptions.
MIKE: a fast and compact post-quantum NIKE
We introduce MIKE (Module Isogeny Key Exchange), a post-quantum NIKE (Non Interactive Key Exchange) whose security relies on the CDH problem for the rank-$2$ Hermitian module action on supersingular elliptic curves.
For NIST level~$1$, MIKE has very compact public keys of 80B, and using our constant time C implementation, the key generation takes 0.65ms and the shared secret takes 4.9ms (including key validation) on a AMD CPU at 3.3GHz.
Truffle: Maliciously Secure Three-Party Shuffles with Applications to Parsing
Deploying Secure Multiparty Computation (MPC) to operate on data from real world sources requires many connective elements that have not received much attention in the literature. One prominent example is that MPC protocols typically assume conveniently structured data, whereas data in the real world comes in formats that are meant to be handled by string parsing engines. In this work, we give a new constant round protocol for securely parsing secret shared strings into an MPC-friendly format, built upon secure shuffle as a key primitive.
Secure shuffle applies a permutation to a list while keeping both the permutation and the underlying data secret-shared at all times. While highly efficient protocols exist in the semi-honest setting, achieving malicious security has incurred significant overhead in both rounds and communication.
We present Truffle, a new three-party shuffle protocol that is secure against one active corruption to bridge this gap. Truffle achieves an amortised round complexity that for the first time matches the state-of-the-art semi-honest protocol, while incurring only sublinear communication overhead. The core technique that underlies Truffle is a novel distributed verifier zero-knowledge proof that checks the correctness of a putative shuffle. We implement Truffle and show via benchmarks that it is performant enough to handle real application data.
Beyond parsing secret shared data, secure shuffle finds applications in graph analytics, anonymous communication, Distributed Oblivious RAM, aggregate statistics, and secure sorting, each of which stand to benefit from the improvement that Truffle provides.
Post-Quantum Anonymous Signatures from the Lattice Isomorphism Group Action
Post-quantum assumptions may not rely on the difficulty of finding secret subgroups as many classical schemes did. Instead, several assumptions make use of more general group actions, with the hope that quantum algorithms are not helpful in this less structured setting. Group action-based constructions were first presented in the context of isogenies in which an ideal class group acts on elliptic curves, but equivalence problems in error-correcting codes and lattices also exhibit such structures.
Previous works presented anonymity-preserving constructions in a generic group action framework; however, they were not general enough to encompass the group action underlying the Lattice Isomorphism Problem (LIP), for which the acting group is countably infinite and non-commutative.
We bridge this gap by, from zero-knowledge proofs of OR statements, building generic blind signatures and strong designated-verifier signatures with non-delegability from standard assumptions corresponding to a generalised group action inverse problem.
Hell’s Bells: A Neural Network Pipeline for Ternary Fast Matrix Multiplication Algorithms
We present a neural network-based pipeline for efficiently generating fast matrix multiplication (FMM) algorithms of small but arbitrary dimensions $(n,m,k)$. Our neural network is general and tunable to output FMM schemes with specific properties, and in this paper we specifically target aspects that are useful and important in practical implementation, such as ternarity (coefficients in $\{-1, 0, 1\}$), sparseness and a low number of additions after optimization (addition reduction carried out separately).
We generate and optimize thousands of FMM algorithms and show that our generation method is beneficial in terms of performance across the entire FMM pipeline (both the FMM generation itself and optimization of additions).
We discuss performance metrics and utilize heatmaps to visualize and understand this performance.
We achieve record-low arithmetic (additive) complexity for various combinations of dimensions. For $(n,m,k) = (2,2,k)$, our method performs particularly well. Our improvement compared to previous results increases with $k$.
We show that the (addition) optimization process can behave very differently depending on the dimensions considered, indicating how further improvements (beyond our results) can be targeted.
In particular, in the $(n,m,k) = (2,2,k)$ setting, we show evidence of structural FMM properties coming into play, concretely showing that FMM generation with a minimal number of additions is sometimes suboptimal with respect to the entire FMM pipeline.
Finally, we make our neural network implementation, our generated FMM schemes, heatmap utilities and datasets publicly available.
PoP! Goes the VOLE: Shorter Proofs of Possession for KEM Certificates
The shift to Post-Quantum Cryptography (PQC, a.k.a. quantum-resistant cryptography) is considered the immediate solution to the threat posed to public key cryptography/PKI by quantum computers. Due to the variety of PQC algorithms (and their characteristics), researchers have proposed different PQC migration strategies. For example, KEMTLS (Schwabe, Stebila, and Wiggers, CCS '20) replaces TLS handshake signing operations by Key Encapsulation Mechanisms (KEMs).
However, KEMTLS requires KEM-based certificates (i.e., a certificate with a KEM public key), and the question of issuing KEM certificates on a large scale
has received limited attention from the community. We address this research gap by comparing the performance of different Proof of Possession (PoP) approaches for KEMs and assessing their viability for practical adoption.
To this end, we first propose and implement a non-interactive PoP for Hamming Quasi-Cyclic (HQC), a code-based post-quantum KEM selected by NIST for standardization. Our PoP is instantiated via the VOLE-in-the-Head (VOLEitH) paradigm. %VOLEitH is based on Vector Oblivious Linear Evaluation (VOLE).
Setting, reproducibility, and practicality as design goals, we integrate and benchmark our approach against PoPs for Kyber and FrodoKEM (from Güneysu et al., CCS '22) in the ACME protocol for automatic certificate issuance. Our results show that, in general, Kyber allows faster issuance of KEM certificates but at a cost of losing either compatibility with the protocol (necessitating significant alterations to proposed internet standards)
or breaking compatibility/compliance with NIST standards. Notably, our PoP for HQC holds compliance, compatibility, \emph{and} achieves smaller proof sizes. We also report integration choices and considerations, as well as network traffic analysis stemming from larger (KEM-based) Certificate Signing Requests (CSRs). Our testbed demonstrates the impact of large CSRs by simulating an unstable network. It shows that HQC-PoP's performance is competitive with the fastest options, thanks to its smaller proof sizes.
Shorter Few-Time Signatures from Hash Chains and Blockwise Forced Pruning
SLH-DSA is a standardized stateless hash-based signature scheme based on SPHINCS$^+$, but its signatures remain large. PORS+FP uses forced pruning to reduce the size of the bottom few-time signature (FTS) component, while BPORS+FP distributes repeated uses among independent PORS child keys. In BPORS+FP, each selected leaf reveals a fixed secret value, and a single pruning budget limits the total number of authentication nodes across all coordinates. We introduce BPORS-C+BFP, which replaces each secret at a child leaf with a short hash chain and assigns a separate authentication budget to each block of coordinates. The child Merkle tree authenticates each chain endpoint. Each selected chain still contributes one hash value to the signature, while its opening depth provides an additional encoding choice. For a fixed set of selected chains, a constant-sum constraint prevents forward hashing alone from converting one valid depth tuple into another.
Under repeated use, signatures may disclose different positions on the same chain. We derive a generating-function upper bound on coverage and an exact counting method for individual pruning blocks that accounts for these disclosures and target acceptance. Separate block budgets confine pruning-induced dependencies, reducing the number of coordinates counted jointly and making exact calculation practical for small blocks.
Replacing FORS in SPHINCS+ while keeping the hypertree and one-time signature parameters fixed, BPORS-C+BFP reduces complete-signature sizes by $8.3\%$--$18.1\%$ across six standard settings, compared with $3.7\%$--$13.4\%$ for BPORS+FP. Across three limited-use settings, the reductions relative to FORS are $32.5\%$--$36.5\%$ for BPORS-C+BFP and $22.0\%$--$26.0\%$ for BPORS+FP.
PairSwitch: Efficient Galois-Paired Key Switching for Gentry–Lee Matrix FHE
Matrix-native fully homomorphic encryption, introduced by Gentry and Lee, multiplies encrypted matrices with a Trace product and returns its four-component output to an ordinary ciphertext with a BigSwitch, whose keys over an extended ring dominate the key material of the scheme. Existing BigSwitches follow two routes: they either store one key per source, as in the original construction, or factor the secret through the trace and relinearize at run time, as in the Trace-Factored BigSwitch (TFB) of Park et al., which halves the keys at the price of $50\%$ more key switches and a whole switching error multiplied by the secret. Meanwhile, the Galois splitting of Park (Eurocrypt'25) decomposes such switches into base-ring diagonals, but it has not been used to reduce their keys. However, whether a BigSwitch can publish only the keys of TFB and still run at the speed of the original one has remained open.
In this work, we first propose the pair-merge BigSwitch, which observes that the diagonals of a split BigSwitch are indexed by an inversion-closed coset $\kappa H$ and rewrites the target of a diagonal as $x\,g(s)+y\,s\,g(s)=g\big(g^{-1}(x)\,s+g^{-1}(y)\,s\,g^{-1}(s)\big)$, so that it borrows the product key of its inverse at the cost of one Galois step; it makes the $2n$ key switches of the original BigSwitch with $n/2+1$ instead of $n$ product keys, and we prove that no per-diagonal BigSwitch with $2n$ key switches holds fewer than $3n/2+1$ keys. Building on it, we propose public key rebasing, which turns Galois keys into product keys with one relinearization key placed one small modulus layer above the chain, so that the client publishes only the keys of TFB and a 10.6 MiB layer key, at the price of $1.5\times$ the resident keys of TFB on the server. Consequently, together with a Hermitian hop that finishes a partner diagonal of a Gram product with one Galois step, PairSwitch makes $2n$ key switches on general inputs and $3n/2+1$ on Gram products.
On the parameters of Park et al. ($n=256$, $p=17$, $\log_2 PQ=200$), our implementation runs a BigSwitch $1.89$--$1.99\times$ faster than TFB and $1.28$--$1.38\times$ faster than the original BigSwitch, with $2.4$ bits less noise than TFB and $4.3$ bits more than the original, at a $128.3$-bit layer key; it is $2.45\times$ faster than TFB on Gram inputs. Our implementation and the raw logs are available at https://github.com/acprk/pairswitch-gl.
K-LMS: Design, Implementation, and Evaluation of Leighton–Micali Signatures with Korean Cryptographic Primitives
Hash-based signatures are the most conservative post-
quantum signature family, and the stateful schemes XMSS and LMS
are both standardized by NIST. Prior work has instantiated XMSS and
SPHINCS+ with Korean cryptographic primitives, but no comparable
Korean-primitive study exists for LMS. We fill that gap with K-LMS, an
experimental variant that preserves the full LMS structure and domain
separation and replaces only the hash. The substituted hashes are the
Korean hash function LSH-256, in both its reference and its vectorized
implementation, and a Tandem-DM double-block-length construction
over the Korean block ciphers CHAM, LEA, and ARIA. A non-invasive
bridge over the reference LMS implementation realizes eight interchange-
able backends without editing a line of it. We evaluate key generation,
signing, and verification latency, key and signature sizes, peak memory,
a sweep over tree height and the Winternitz parameter, and implemen-
tation complexity. Hash substitution leaves key and signature sizes, and
the memory requirement of the LMS data structures, unchanged. We
also isolate two measurement pitfalls that can distort such comparisons:
a vector dispatch wrapper that re-runs its capability check on every
digest, which costs an order of magnitude on our virtualized host, and
the choice of software or hardware-accelerated SHA-256 as the baseline,
which shifts any LSH vs. SHA-2 conclusion by a factor of about six.
Profiling shows that LMS is dominated by 55-byte one-shot hashes
(about 94 % of all calls), so scheme-level ranking cannot be extrapolated
from long-message hash benchmarks. Against a fair software baseline,
LSH-256 K-LMS signing is on par with SHA-256 LMS (0.84×), while
hardware acceleration retains a ∼3.6× advantage where it is available.
On the same host and with identical LSH-256 code, K-LMS runs 3.3–
3.9× faster than the published K-XMSS implementation, because LMS
needs one hash call per Winternitz chain step where XMSS needs three.
DP-Guided Schedule Selection for $\mathbb{F}_2[x]$ Multiplication across ISAs
Efficient multiplication over $\mathbb{F}_2[x]$ is a core primitive in classical and post-quantum cryptographic software. As ARM and RISC-V become increasingly relevant for open-source cryptographic libraries such as OpenSSL and liboqs, arithmetic kernels must be retuned across a wider range of Instruction Set Architectures (ISAs). High-performance arithmetic libraries recursively apply Karatsuba- and Toom-style decomposition rules, each splitting the operands into smaller subproblems and recombining the resulting products. The resulting decomposition schedule is the recursive tree of rule choices from the top-level multiplication down to the base kernels. However, hand-tuned schedules can miss better decompositions at large operand sizes, while ISA-specific primitive costs complicate cross-platform retuning.
In this paper, we formulate recursive $\mathbb{F}_2[x]$ multiplication as a schedule-selection problem. The recursive rule space has optimal substructure, allowing dynamic programming (DP) over a compact ISA profile that accounts for base multiplication, XORs, memory traffic, and recursive overhead. The resulting schedules are materialized as dispatch tables or fixed-size kernels. Across x86-64, ARM64, RISC-V64, and RP2040, DP costs track runtime trends across input sizes, and the full rule set achieves $1.04$–$1.18\times$ geomean speedup over gf2x. HQC and BIKE integrations on the three 64-bit platforms yield $1.06$–$1.21\times$ and $1.01$–$1.70\times$ end-to-end speedups, respectively, against their platform baselines. We also evaluate Classic McEliece on these platforms. With prepared profiles, HQC/BIKE schedule selection takes 0.075–0.762 seconds, avoiding candidate compilation and benchmarking during search. The scheme provides a systematic alternative to hand tuning and measurement-driven per-size empirical search, reducing the effort required to port and retune carry-less multiplication kernels.
Extract-Amplify-Measure: Single-Sided and Tight O2H with Applications to CCA Security in the Quantum Random Oracle Model
The One-Way-to-Hiding (O2H) theorem is a useful tool for analyzing reprogramming in the quantum random oracle model (QROM). It bounds the distinguishing advantage by the probability $\epsilon$ that a one-wayness attacker finds the reprogrammed point. A sequence of works has improved the tightness of this theorem. Currently, the Measure-Rewind-Extract O2H (MRE-O2H) theorem proved by Ge et al. (ASIACRYPT 2024) achieves the tightest known upper bound of $O(\sqrt{q}\cdot\epsilon)$, where $q$ is the number of quantum queries. This theorem follows the Double-Sided idea introduced by Bindel et al. (TCC 2019), which requires the one-wayness attacker to access both the original and reprogrammed random oracles, thereby imposing stronger requirements on the reduction. Moreover, it incurs a $q$-dependent loss of $O(\sqrt{q})$.
In this paper, we address these limitations by proving two Extract-Amplify-Measure (EAM) O2H theorems. First, we prove a Single-Sided EAM-O2H (SSEAM-O2H) theorem, which achieves the same $O(\sqrt{q}\cdot\epsilon)$ upper bound as the MRE-O2H theorem, while the resulting attacker only needs access to either the original or the reprogrammed random oracle, reducing the requirements on the underlying reduction. Second, we prove a Double-Sided EAM-O2H (DSEAM-O2H) theorem, which retains the Double-Sided idea used in the MRE-O2H theorem but removes the $q$-dependent loss, yielding a tight $O(\epsilon)$ upper bound.
As applications, we revisit the security of several Fujisaki--Okamoto variants proposed by Hofheinz et al. (TCC 2017) in the QROM, namely $\textsf{U}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}_{m}$, $\mathsf{FO}^{\bot}$, and $\mathsf{FO}^{\bot}_{m}$, and obtain the following results:
The \textsf{IND-CCA} security of $\textsf{U}^{\slashed{\bot}}$ can be reduced to the \textsf{OW-CPA} security of the underlying PKE scheme. Compared with the previous proofs by Bindel et al. (TCC 2019) and Kuchta et al. (EUROCRYPT 2020), we avoid both the square-root loss and the $q$-dependent loss in the underlying adversary's \textsf{OW-CPA} advantage.
The \textsf{IND-CCA} security of $\mathsf{FO}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}_{m}$, $\mathsf{FO}^{\bot}$, and $\mathsf{FO}^{\bot}_{m}$ can be reduced to the \textsf{IND-CPA} security of the underlying PKE scheme. Compared with the previous proofs by Ge et al. (ASIACRYPT 2024), we reduce the $q$-dependent loss from $O(q^{1.5})$ to $O(q^{0.5})$.
Assuming unique randomness recoverability, the \textsf{IND-CCA} security of $\mathsf{FO}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}_{m}$, $\mathsf{FO}^{\bot}$, and $\mathsf{FO}^{\bot}_{m}$ can be reduced to the \textsf{OW-CPA} security of the underlying PKE scheme. Compared with the previous proofs by Ge et al. (ASIACRYPT 2024), we avoid the $q$-dependent loss in the underlying adversary's \textsf{OW-CPA} advantage.
Improving GIJS Key Recovery for Classic McEliece
Classic McEliece is a post-quantum encryption scheme. Its public key is a generator matrix of a secret binary Goppa code. Its security levels are set by generic decoding attacks, which cost $2^{151}$ to $2^{287}$ bit operations for the five parameter sets.
Ghoshal, Ishai, Jain and Sun (GIJS26) recently gave the first test that tells a public key from a random matrix at a lower cost, an estimated $2^{114}$ to $2^{124}$ bit operations. They have since extended it to recover the secret key. The test is one large sparse linear-algebra computation, which we call a run.
We improve this attack in two ways. First, we lower the cost of a run to $2^{89}$ to $2^{98}$ bit operations. If every operation is charged for the memory that it addresses, at square-root cost, a run costs $2^{107}$ to $2^{117}$. This is our best estimate, and it is below the cost of generic decoding with free memory. The Classic McEliece security guide charges every operation for the whole memory. Under that rule a run costs $2^{117}$ to $2^{128}$, against $2^{159}$ to $2^{316}$ for generic decoding.
Second, we give two ways to recover the secret key. One rests on a theorem that we prove and needs $100$ to $1400$ runs. The other builds on the key recovery of GIJS26 and needs a single run.
None of this is close to practical, and a run at full size cannot be tested. The costs rest on four heuristic assumptions, which we state and test on small keys. There the first attack recovered the secret key with polynomials of degree $5$, and the second with degrees $5$, $6$ and $7$. Degree $7$ is the degree of the attack on Classic McEliece. Small keys deviated from the assumptions in a few ways. We identify the cause of each deviation and argue that it does not occur at full size. As a demonstration we recovered the secret key of instance~253 of the TII McEliece key-recovery challenges
($m=8$, $t=9$, $n=214$), a toy-sized code that had not been solved.
StOMR: Stateful Oblivious Message Retrieval
Oblivious Message Retrieval (OMR) enables recipients to retrieve messages from an untrusted server without revealing which messages correspond to them. OMR is useful for privacy-preserving systems such as anonymous messaging and blockchains. Existing constructions are inherently built in the public-key setting and use Fully Homomorphic Encryption (FHE) to allow a detector to scan a public bulletin board and produce a compact encrypted digest containing only relevant messages. However, this design incurs a major practical limitation: sender-published signals are large (hundreds of kilobytes), leading to significant bandwidth, storage, and on-chain costs.
In this work, we explore the efficiency gains achievable by moving to a private, stateful setting, and introduce stateful OMR, a new model in which senders and receivers maintain lightweight private state to enable more efficient anonymous communication. Based on this model, we design StOMR, a protocol that significantly reduces the size of sender signals compared to prior approaches. To support the required shared state, we further introduce an OMR Key Encapsulation Mechanism (OMR-KEM), which allows users to privately establish shared state and instantiate stateful OMR without out-of-band channels.
We implement StOMR in C++ and evaluate it against the state-of-the-art systems PerfOMR (USENIX Security '24), SophOMR (USENIX Security '26), and InstantOMR (USENIX Security '26). Our results show that StOMR preserves detector performance while achieving a signal size approximately 550×, 650×, and 178× smaller than PerfOMR, SophOMR, and InstantOMR, respectively.
A Cryptographic Perspective on Fingerprinting Machine Learning Model Weights
We introduce a cryptographic framework for fingerprinting machine learning models, enabling model providers to train models that can later be attributed to them. Our framework captures an honest setting in which providers distribute base models that users may subsequently modify to adapt them to their own applications (e.g., through finetuning). We formalize three properties for fingerprinting schemes: (1) quality preservation or undetectability: fingerprinted models must remain computationally indistinguishable from models produced by an underlying training algorithm, (2) robustness: the fingerprint must remain detectable even after the model weights are subject to permitted modification, and (3) unforgeability: no computationally bounded trainer can forge the fingerprint except by applying a permitted modification to an existing fingerprinted model. Under the continuous learning with errors assumption (Bruna et al, 2021), we construct a robust and unforgeable fingerprinting scheme for modifications in $\ell_2$. The scheme achieves undetectability with respect to any given noisy training algorithm, meaning any algorithm whose output weights can be decomposed into independent Gaussian and non-Gaussian components.
Along the way, we introduce two new technical tools. The first is a form of steganography; we develop a method for undetectably modifying a noisy training algorithm so that its output weights secretly encode a message. The embedded message remains decodable even after bounded $\ell_2$ perturbations to the weights. Second, we introduce the pancake alignment problem, a "semi-search" variant of homogeneous continuous learning with errors (hCLWE). Given hCLWE samples generated from a random secret, the goal is to recover a direction that is sufficiently aligned with the secret. We provide evidence for the hardness of pancake alignment in certain parameter regimes via reductions from continuous learning with errors.
Auxiliary Isogeny Freedom in SQIsign's Two-Dimensional Representation
SQIsign encodes its response isogeny via a two-dimensional
representation on a product of elliptic curves, using the Kani
construction. We analyze the algebraic structure of this encoding
in detail, with a focus on the role of the auxiliary isogeny and
its implications for strong unforgeability.
We show that the anti-isometry $\psi$ determining the Kani kernel
is publicly computable from the torsion-point images of the
component and auxiliary isogenies alone, that the automorphism
orbit $\{\psi, -\psi\}$ is the only torsion-level source of
encoding non-uniqueness on a fixed product surface, and that every
auxiliary of the correct degree is commitment-compatible by Kani's
theorem. The sole barrier to producing an alternative encoding is
the construction of a new auxiliary isogeny of the required
(generically non-smooth) degree from the challenge curve.
We demonstrate that this barrier falls whenever
a single small prime divides the auxiliary
degree $2^f - q$: the adversary reroutes the terminal
$\ell$-isogeny step at the codomain of the honest auxiliary,
preserving the total degree exactly. Since generic odd integers
possess small prime factors with overwhelming probability, this
establishes that canonicalization of the basis change matrix
does not suffice for strong unforgeability.
We analyze the signing algorithm's dependency structure to show
that the auxiliary cannot be bound into the Fiat-Shamir hash
without a protocol redesign, and conclude with a structural
comparison of ECDSA (where canonicalization suffices), SQIsign
(where it does not), and salt-PRISM (which achieves strong
unforgeability via a salted hash-to-prime mechanism that
eliminates the auxiliary freedom entirely).
BABE: Verifying Proofs on Bitcoin Made 1000x Cheaper
Endowing Bitcoin with the ability to verify succinct proofs has been a longstanding problem with important applications such as scaling Bitcoin and allowing the Bitcoin asset to be used in other blockchains trustlessly. It is a challenging problem due to the lack of expressiveness in the Bitcoin scripting language and the small Bitcoin block space. BitVM2 is the state-of-the-art verification protocol for Bitcoin used in several mainnets and testnets, but it suffers from very high on-chain Bitcoin transaction fees in the unhappy path (over $14,000 in a recent experiment). Recent research BitVM3 dramatically reduces this on-chain cost by using a garbled SNARK verifier circuit to shift most of the verification off-chain, but each garbled circuit is 42 Gibytes in size, so the off-chain storage and setup costs are huge. This paper introduces BABE, a new proof verification protocol on Bitcoin, which preserves BitVM3's savings of on-chain costs but reduces its off-chain storage and setup costs by three orders of magnitude. BABE uses a witness encryption scheme for linear pairing relations to verify Groth16 proofs. Since Groth16 verification involves non-linear pairings, this witness encryption scheme is augmented with a secure two-party computation protocol implemented using a very efficient garbled circuit for scalar multiplication on elliptic curves. The design of this garbled circuit builds on a recent work, Argo MAC, which gives an efficient garbling scheme to compute homomorphic MACs on such curves.
Simple Extremely Lossy Functions from Small-Exponent Hashing
Extremely Lossy Functions (ELFs) are a standard model primitive that captures many useful properties of random oracles (Zhandry, Crypto 2016). While there are many variations of ELFs with additional properties, every construction (excluding obfuscation) has followed essentially the same template of bootstrapping from a sequence of ELFs secure only against fixed-size adversaries, and every construction was based on only the exponential hardness of DDH (or $k$-Lin), an assumption that is only reasonable over elliptic curves.
We introduce and construct Extremely Lossy Trapdoor Hashing (ELTDH), a stronger notion that implies all known variations of ELFs. Our construction achieves ELTDH in one go, without bootstrapping from schemes secure for only fixed-size adversaries, which makes it simpler and more efficient than existing ELFs. We assume exponential security of the small-exponent discrete logarithm, together with polynomial security of decisional composite residuosity (DCR). Exponential security is only required in the size of the secret exponent, not the size of the group, so the assumption plausibly holds for multiplication modulo $N^2$ (and for many other cryptographic groups), despite the subexponential-time discrete logarithm attacks from index calculus. Our results diversify the assumptions underlying ELFs, while also giving a simpler construction.
Issuer-Hiding Anonymous Tokens and Credentials from Key-Randomizable Signatures
Anonymous authentication schemes allow a user to prove they have been authorized by some issuer, without revealing any additional information about the user's identity. Two variants are currently seeing strong real-world interest. Anonymous tokens (ATs) allow one-time proofs of authorization, e.g., for privacy-preserving rate limiting as currently being pursued in the MoLE effort at the IETF. Anonymous credentials (ACs) incorporate attributes that can be selectively disclosed in an unbounded number of proofs; these underpin digital-identity systems such as the European Digital Identity (EUDI) wallet.
Both anonymous tokens and credentials are envisioned as being deployed in systems with multiple issuers. In standard schemes, proofs reveal which issuer authorized a user, leaking more information than necessary and shrinking a user's anonymity set. To address this, there has been significant recent interest in issuer-hiding schemes that only reveal that the authorizing issuer lies in a specified policy set.
We present generic constructions of issuer-hiding ATs/ACs based on key-randomizable signatures that give rise to several efficient instantiations. Specifically, we show efficient issuer-hiding ATs based on the Tessaro–Zhu blind-signature scheme, and efficient issuer-hiding ACs (without policy keys) compatible with existing BBS-based schemes.
Explicit Nonlinear Functions beyond the Fourier bound
We study the problem of constructing highly nonlinear vectorial maps $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$.
Concretely, we want an $F$ and an $A = A(m,n)>0$ as small as possible, so that for every affine map $L: \mathbb{F}_2^n \to \mathbb{F}_2^m$ (of the form $L(x) = Mx + b$) we have:
$$
\operatorname{agree}(F,L) := |\{x \in \mathbb{F}_2^n \mid F(x) = L(x)\}| \leq A.
$$
Such questions have been studied by Nyberg [1991, 1993], Carlet and Ding [2004, 2007], Liu, Mesnager and Chen [2017], Nagy [2025],
and Biryukov, Turecek, and Udovenko [2026].
There is a classical method of constructing such functions from bent-functions and Fourier analytic ideas; the best bound achievable by this method is:
$$
A(m,n) = \Theta(2^{n-m} + 2^{n/2}),
$$
and in particular, is never smaller than $2^{n/2}$.
In this work, we show how to construct highly nonlinear functions beyond this Fourier bound. Concretely, we show how to construct for every $\gamma>0$, a function
$F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ with $m = \mathcal{O}_{\gamma}(n)$, achieving
$$
A(m,n) \leq (1+\gamma)^n.
$$
Surprisingly, we even achieve the same quantitative behavior for the much harder question of having low agreement with $m$-tuples of degree $d$ polynomials $Q: \mathbb{F}_2^n \to \mathbb{F}_2^m$, with $m = \mathcal{O}_{\gamma,d}(n)$. Here the previously best bounds were of the form $A(m,n) = \mathcal{O}(2^{-\frac{n}{2^{d+1}}} \cdot 2^n)$ of Ben-Sasson and Kopparty [Kopparty's thesis, 2010], based on Gowers-norm-type arguments.
All our results generalize to all finite fields $\mathbb{F}_q$ in place of $\mathbb{F}_2$.
Our methods are based on a new connection to classical results on counting solutions to systems of polynomial equations via algebraic methods. This connection brings us to basic questions in combinatorics, about graphs and hypergraphs with simultaneously a small number of edges and independent sets.
Multiplying Not-So-Big Integers with FFTs: Finding and Pushing the Crossover on Large Modern OoO ARM CPUs
Established multiple-precision software generally reserves Fast-Fourier Transform (FFT) multiplication for very large operands; for example, GMP reports full-product FFT thresholds of roughly 3000--10000 limbs. Becker et al. showed that Number-Theoretic Transform (NTT) multiplication can become advantageous much earlier on Cortex-M microcontrollers. It thus becomes an interesting engineering question to check where the crossover actually takes place on a big modern CPU. Our first-generation implementation on Cortex-A76 and Neoverse-N1 shows that the crossover point is around 10k bits when using ARMv8+ with Neon, using optimized and verified code. Motivated by the tighter Barrett bound of Becker, we developed the Second implementation, which eliminates additional reductions and pushes the crossover below 5.6k bits. We integrate our multipliers into OpenSSL RSA, resulting in end-to-end speedup for the public-key operations.
Post-Quantum Time-Lock Puzzle from Isogenies
We construct the first (conjectured) post-quantum Time Lock Puzzle (TLP) from isogenies. Our construction avoids setup/preprocessing and achieves non-trivial efficiency, where puzzle generation runs in time $\sqrt{T}$ . We prove security in the quantum random oracle model (QROM)
under a new conjecture about the sequentiality of isogeny pushforward computations, for which we provide a thorough justification. The only other (conjectured) post-quantum TLP constructions rely on heavy cryptographic machinery from lattice-based assumptions.
We also provide, to the best of our knowledge, the first proof-of-concept implementation of a candidate post-quantum TLP. On an Apple M3 CPU, for a one-hour target delay, total puzzle generation, including setup, takes 2.9 minutes serially and 100.5 seconds with four generation workers. Our experiments demonstrate the practicality of the complete design and show that the quadratic gap between puzzle generation and solving in theory also translates into a meaningful concrete separation.
As a stepping stone towards our main result, we provide a new TLP from isogenies in the preprocessing model from a combination of the sequentiality of isogeny walks in the $F_{p^2}$ graph and the hardness of computational Diffie-Hellman (CDH) over cyclic prime-order groups. This improves the assumptions underlying the only known TLP from isogenies in the preprocessing model, which required pairing based assumptions instead of just discrete log. We further adapt this construction to achieve non-trivial efficiency of $\sqrt{T}$ in puzzle generation without setup/preprocessing.
MULTISS: Long-Term Secure Distributed Storage over Remote QKD Networks
We introduce MULTISS, a distributed storage protocol over multiple remote Quantum Key Distribution (QKD) networks that ensures long-term data confidentiality. MULTISS is designed to combine several QKD networks, as QKD links are inherently limited in range, and to connect these networks through classical cryptographic channels. It relies on a hierarchical secret sharing scheme that makes certain shares mandatory for the reconstruction of the original secret. Hence, MULTISS offers a secure distributed storage solution in a scenario that is compatible with the current deployment of quantum networks. We prove that MULTISS preserves the confidentiality of stored data even if an adversary (i) gains full access to all nodes of a subset of the QKD networks, or (ii) records all classical communications between distant QKD networks and compromises them at a later stage. We show that it provides strictly stronger security guarantees than existing QKD-storage protocols.
Our protocol also includes a procedure to update the shares without reconstructing the original data. In addition, we provide a recovery mechanism that tolerates the complete compromise of some QKD networks. We further introduce a variant of the protocol, called the local-mode, that minimizes the communication overhead of the recovery procedure when deployed over specific network topologies.
On the Instantiability of the Fujisaki–Okamoto Transform for Trapdoor Functions
The Fujisaki--Okamoto (FO) transform (Journal of Cryptology, 2013) is the standard route from weakly secure public-key encryption to chosen-ciphertext security, and it underlies many practical post-quantum key-encapsulation schemes, including ML-KEM. Security proofs for FO are set in the (quantum) random oracle models. FO uses two hash functions: the derandomization hash~$H$, which turns the base scheme into a deterministic trapdoor function (TDF) by Encrypt-with-Hash, and the key-derivation hash~$G$. We ask whether it is possible to instantiate the hash functions in the FO transform while retaining its security guarantees.
While prior work mainly focused on the $H$ step, our focus is the $G$ step, and we take an underlying injective TDF as given. We first show that the message-only implicit-rejection variant \smash{$\UmIR$}, a key-encapsulation mechanism formulation of FO that follows ML-KEM's choices of rejection and key derivation, is \emph{uninstantiable} in general. Namely, assuming standard LWE and subexponentially secure indistinguishability obfuscation and puncturable PRFs, for every efficient hash function family~$G$ with superlogarithmic output
length there is a one-way, perfectly correct injective trapdoor function for which the resulting KEM is not IND-CCA2 secure.
We next give sufficient conditions on~$G$ to instantiate the TDF-based \emph{hybrid-encryption} formulation of FO, rather than the KEM version. To this end, we introduce \emph{distributional injective extractability} (\DINJEXT{}), a new hash function property defined relative to a partially injective ``wrapping function.'' Under this assumption relative to the FO-derived wrapping function, combined with an achievable form of universal computational extractor security (Bellare, Hoang, and Keelveedhi, CRYPTO 2013) on $G$ and suitable assumptions on the base schemes, we obtain standard-model IND-CCA2 security. As evidence that \DINJEXT{} is achievable, we show that a random oracle satisfies it for every partially injective wrapping function, and that a quantum random oracle satisfies a formulation of it for the FO wrapping function, in both cases even relative to an oblivious sampling oracle. We leave a standard-model construction open.
Comparative Evaluation of Open-Source Gröbner Basis Implementations for Small-Scale AES Polynomial Systems over GF(2)
The practical performance of Gröbner basis implementations depends on the
polynomial systems being solved. This work evaluates 20 open-source imple-
mentations with Magma as a proprietary reference on systems derived from
small-scale AES over GF(2). The Easy, Medium, and Hard experiments use
field equations and ten input instances each, comparing wall-clock runtime, peak
memory, success rate, and CPU usage. Implementations with no successful runs
are excluded from subsequent experiments. In Hard, msolve and Singular’s slimgb
completed all ten runs successfully, with mean runtimes of 164 and 269 seconds
and mean peak memory consumption of 3693 and 4343 MiB, respectively, com-
pared with 319 seconds and 16853 MiB for Magma. During these runs, msolve
used an average of 13.4 CPU cores, while slimgb and Magma used about one
core each. Magma had the shortest mean runtime in Medium, whereas msolve
was fastest in Easy and Hard. Changing the plaintext-ciphertext pair count
affected implementations differently, and runtimes varied between instances. The
results show that open-source implementations can be competitive alternatives
to Magma, with their relative performance depending on the input systems.
MiniSHAKE
The overwhelming majority of the Keccak instances standardized and
used in practice today make use of the Keccak-$f$ [1600] permutation or reduced-round versions of it. There are a few use cases where using a smaller permutation width would be beneficial, notably when one has to hash many very short messages. To address this, the present note defines instances that use the Keccak-$p$[800, $n_r = 12$] permutation, collectively under the name MiniSHAKE.
A Kleptographic Attack on CSIDH
This note reports an attack scenario for CSIDH that does not appear to have been considered in the literature. A subverted device of Alice can leak a shared curve between Alice and Bob through Alice's public curves in later CSIDH sessions. The attack adapts the Young--Yung kleptographic attack from classical Diffie--Hellman to CSIDH using the Goldreich--Levin theorem and rejection sampling. We prove that a CSIDH public curve $[\mathfrak a]\star E_0$ remains computationally indistinguishable from an honest public curve even when its secret class $[\mathfrak a]$ is rejection-sampled according to a hard-core bit of a hidden parallelization curve $[\mathfrak a][\mathfrak c]\star E_0$ formed by the same class $[\mathfrak a]$ together with an independent curve $[\mathfrak c]\star E_0$. The proofs rely only on the computational assumptions underlying CSIDH itself. We hope that this note provides a useful starting point for the study of algorithm-substitution attacks in isogeny-based cryptography, complementing existing work on side-channel and fault attacks.
Combined Stability: Protecting against Combined Attacks
Physical attacks pose serious challenges to the secure implementation of cryptographic algorithms. While side-channel analysis (SCA) has received significant attention, leading to well-established countermeasures, fault attacks and especially their combination with SCA (i.e., combined attacks) remain less researched. Addressing such combined attacks often requires a careful integration of masking and redundancy techniques to resist the reciprocal effects of faults and probes. Recent research on combined security has gained momentum, with most approaches relying on composable security notions involving error correction, typically applied after each nonlinear operation. While effective, this approach introduces an area and performance overhead, along with additional security challenges posed by the correction circuits themselves.
In this work, we take a different direction, following the concept of stability introduced in StaTI (CHES 2024), which ensures fault propagation to protect against ineffective faults. We extend this concept to combined security by proposing a new composable security notion, combined stability, which integrates an extended stability notion, diffused stability, with arbitrarily composable glitch-extended probing security notions. Notably, this framework requires only a single error detection at the end of the computation, avoiding costly intermediate error checks and corrections. To demonstrate practicality, we describe a combined secure AES S-box hardware implementation. Our results show that this approach, achieving combined security with competitive implementation costs, offers a promising alternative to error-correction-based schemes.
Picking up the Fallen Mask: Breaking and Fixing the RS-Mask Countermeasure
Physical attacks pose a major challenge to the secure implementation of cryptographic algorithms. Although significant progress has been made in countering passive attacks such as side-channel analysis (SCA), protection against fault attacks is still less developed. One reason for this is the broader and more complex nature of fault attacks, which makes it difficult to create standardized fault evaluation methodologies for countermeasures like those used for SCA. This makes it easier to overlook potential vulnerabilities that attackers could exploit. RS-Mask, published at HOST 2020, is such a countermeasure that has been affected by the absence of a systematic analysis method. The fundamental concept behind the countermeasure is to maintain a uniform distribution of variables, regardless of whether they are faulty or correct. This property is particularly effective against Statistical Ineffective Fault Attacks (SIFA), which exploit the dependency between fault propagation and the secret data.
In this work, we present several fault scenarios involving single fault injections on the AES implementation protected with RS-Mask, where the fault propagation depends on the secret data. This happens because the random space mapping used in RS-Mask countermeasure retains a dependency on the secret data, as it is derived based on the S-box input. To address this, we propose a new countermeasure based on the core concept of RS-Mask, implementing a single mapping for all S-box inputs, involving an intrinsic duplication. Next, we evaluate the effectiveness of the new countermeasure against fault attacks by comparing the fault detection rate across all possible fault locations and values for every input. Additionally, we examine the output differences between faulty and correct outputs for each input. Our results show that the detection rate is uniform for each input, which ensures security against statistical attacks utilizing both effective and ineffective faults. Moreover, the output differences being uniform for each input ensures security against differential fault attacks.
StaMAC: Fault Protection via Stable-MAC Tags
Fault attacks pose a significant threat to cryptographic implementations, motivating the development of countermeasures, primarily based on a combination of redundancy and masking techniques. Redundancy, in these countermeasures, is often implemented via duplication or linear codes. However, their inherent structure remains susceptible to strategic fault injections bypassing error checks. To address this, the CAPA countermeasure from CRYPTO 2018 leveraged information-theoretic MAC tags for protection against fault and combined attacks. However, a recent attack has shown that CAPA can only protect against either side-channel analysis or fault attacks, but not both simultaneously, and with significant hardware costs. Its successor, M&M, improves efficiency but lacks protection against ineffective faults.
In this paper, we propose StaMAC, a framework aimed at securely incorporating MAC tags against both side-channel and fault adversaries in a non-combined scenario. We extend the security notions outlined in StaTI from TCHES 2024, and propose the notion of MAC-stability, ensuring fault propagation in masked and MACed circuits, necessitating only a single error check at the end of the computation. Additionally, we show that the stability notion from StaTI is arbitrarily composable (whereas it was previously thought to be only serially composable), making it the first arbitrary composable fault security notion which does not require intermediate error checks or correction. Then, we establish the improved protection of masking combined with MAC tags compared to linear encoding techniques by showing bounds on the advantage considering several fault adversaries: a gate/register faulting adversary, an arbitrary register faulting adversary, and a random register faulting adversary. Then, we show how to transform any probing secure circuit to protect against fault attacks using the proposed MAC-stable gadgets implementing field operations. Finally, we demonstrate StaMAC on an AES implementation, evaluating its security and hardware costs compared to the countermeasures using MAC tags.
SoK: Parameterization of Fault Adversary Models - Connecting Theory and Practice
Since the first fault attack by Boneh et al. in 1997, various physical fault injection mechanisms have been explored to induce errors in electronic systems. Subsequent fault analysis methods of these errors have been studied, and successfully used to attack many cryptographic implementations. This poses a significant challenge to the secure implementation of cryptographic algorithms. To address this, numerous countermeasures have been proposed. Nevertheless, these countermeasures are primarily designed to protect against the particular assumptions made by the fault analysis methods. These assumptions, however, encompass only a limited range of the capabilities inherent to physical fault injection mechanisms.
In this paper, we narrow our focus to fault attacks and countermeasures specific to ASICs, and introduce a novel parameterized fault adversary model capturing an adversary's control over an ASIC. We systematically map (a) the physical fault injection mechanisms, (b) adversary models assumed in fault analysis, and (c) adversary models used to design countermeasures into our introduced model. This model forms the basis for our comprehensive exploration that covers a broad spectrum of fault attacks and countermeasures within symmetric key cryptography as a comprehensive survey. Furthermore, our investigation highlights a notable misalignment among the adversary models assumed in countermeasures, fault attacks, and the intrinsic capabilities of the physical fault injection mechanisms. Through this study, we emphasize the need to reevaluate existing fault adversary models, and advocate for the development of a unified model.
iX3DH: Post-Quantum Subversion-Resilient X3DH Key-Exchange from Isogenies
Uncategorized
Uncategorized
Secure messaging runs on commodity devices that can be subverted by malware or supply-chain attacks. Reverse firewalls address this threat by interposing a user-side device that mediates the communication of a potentially compromised end-point. Recently, Dodis et, al. (CRYPTO 2025) proposed a reverse firewall design for protecting Signal, including its Diffie-Hellman based X3DH handshake, against subversion. With Signal and other platforms now migrating to post-quantum cryptography, however, extending this protection to post-quantum, Signal-conforming authenticated key exchanges (AKE) remains a challenge.
We present iX3DH, a post-quantum X3DH-style protocol from commutative group-action Diffie-Hellman. Its public group-action values can be re-randomized by a reverse firewall, removing subliminal information from these values. We prove AKE security of iX3DH in the QROM against quantum polynomial-time adversaries, relying on the quantum-accessible group-action gap-CDH assumption, PRF security, and EU-CMA security of a PQ unique signature scheme. We then prove that the reverse firewalls are exfiltration-resistant and preserve security against subversions that maintain functionality and are explainable. To prevent subliminal channels within the signature transcript, we construct IBIS, the first candidate post-quantum unique signature scheme. By integrating IBIS with our firewall-friendly handshake, iX3DH achieves post-quantum AKE security under subversion attacks.
Optimized LLL Algorithm
The LLL algorithm involves reductions and swaps, corresponding to projection and ordering conditions. But the transformation $\vec{b}'_i\leftarrow \vec{b}_i- \lfloor\mu_{i,k} \rceil\vec{b}_k$ is not a general size-reduction, where $\mu_{i,k}=\frac{\langle \vec{b}_i, \vec{b}_k^* \rangle}{\langle \vec{b}_k^*, \vec{b}_k^* \rangle} $, $\vec{b}_k^*$ is the orthogonalized vector of $\vec{b}_k$, which cannot ensure $\|\vec{b}'_i\|\leq \|\vec{b}_i\|$. The condition $ (\delta-\mu_{i+1,i}^2)\|\vec{b}_i^*\|^2\leq \|\vec{b}_{i+1}^*\|^2$ for $ \delta\in(1/4, 1)$, cannot ensure $\|\vec{b}_i\|\leq \|\vec{b}_{i+1}\|$. The two drawbacks possibly result in: (1) the first vector could be longer than others, (2) some vectors could be further reduced. In this paper, we present an optimized LLL algorithm which is independent of rthogonalization and reduces the complexity from $O(n^4)$ to $O(n^3)$. By a probabilistic argument, we show the new algorithm runs in polynomial time.
One-Round Threshold XMSS and SPHINCS+ from Fully Homomorphic Encryption
While hash-based signatures such as XMSS and SPHINCS$^+$ are well-established and play a key role in post-quantum cryptography, thresholdizing them to enable use in distributed systems remains a challenge. In particular, their lack of exploitable structure prevents any algebraic attempts that are otherwise possible in the context of classical signatures such as ECDSA, Schnorr, RSA, or BLS, whereas general-purpose MPC techniques are costly in round complexity.
In this work, we construct and implement the first one-round threshold protocol for XMSS and SPHINCS$^+$, with concrete parameters yielding full backward compatibility. At a high level, the secret key is shared among the signing parties while the signing algorithm is evaluated homomorphically using a threshold fully homomorphic encryption scheme. Any $t$-of-$n$ parties, via threshold decryption, can collaboratively derive the signature, which is accepted by the unmodified RFC 8391 or FIPS 205 verifier.
At a technical level, we develop efficient homomorphic SHAKE evaluation over discrete CKKS for varying batch sizes. Analyzing XMSS and SPHINCS$^+$ signing reveals parallel hash computations and data-dependent selections, which we handle through batching and homomorphic lookup to obtain end-to-end circuits. Our implementation amortizes SHAKE256/256 evaluation to $3.4\,\text{ms}$ per hash and completes online threshold XMSS signing in $0.69\,\text{s}$. Threshold SPHINCS$^+$ has roughly two orders of magnitude higher signing latency but over an order of magnitude lower setup latency than XMSS.
Deniability for Signed Credentials: Revisiting the Authenticated Channel vs. Signed Data Debate in the EUDI Wallet
The European Digital Identity Wallet (EUDI Wallet) is currently adopting ECDSA-based signed credentials as part of its core architecture, which raised concerns that such designs inherently lack plausible deniability compared to authenticated-channel approaches such as the German electronic identity card. This paper revisits this perceived trade-off and argues that it is not a property of signature schemes themselves, but of the credential presentation protocol. We show that standard cryptographic techniques - specifically lightweight OR-proofs over the native ECDSA verification equation - can be used to transform signed credential presentations into non-transferable, verifier-bound transcripts.
Our contribution is not a new cryptographic primitive, but a careful instantiation of well-established techniques within the EUDI context, showing that deniability can be added to signed credentials while preserving their deployment advantages.
Area-Efficient Hardware Architecture of the Post-Quantum HQC Cryptosystem with Side-Channel Protection
The Hamming-Quasi Cyclic (HQC) is the Post-Quantum Cryptography (PQC) Key Encapsulation Mechanism (KEM) algorithm recently selected by the National Institute of Standards and Technology (NIST) for standardization as an alternative candidate for the KEM category. While the algorithm is mathematically robust, several studies state that the physical implementation of HQC remains vulnerable to power-based side-channel attacks (SCA). Countermeasures for such SCAs primarily focus on masking and shuffling, which severely increase hardware resources, introducing additional performance overhead. To address this problem, this paper presents a resource-efficient, constant-time hardware architecture for HQC that features a novel idle-hardware reuse strategy as an SCA countermeasure. By intentionally reusing the KECCAK hardware to generate dynamic power during decoding, the proposed architecture scrambles secret-dependent power correlations with less than 0.5% area overhead for the countermeasure logic. The complete design is fully parameterized to support all NIST security categories (HQC-128, HQC-192, and HQC-256). A prototype implementation on an Artix-7 FPGA achieves a maximum clock frequency of 139 MHz while consuming 11,489 LUTs, 6,785 FFs, and 4 DSPs. Functional correctness is verified via NIST Known Answer Tests (KATs) across Key Generation, Encapsulation, and Decapsulation operations, and Test Vector Leakage Assessment (TVLA) confirms significant suppression of side-channel leakage.
Glimpsing the Leakage Flow for Deep Learning-Based Side-Channel Analysis using Stochastic Leakage Model
Deep learning has become the dominant method for profiled Side-Channel Analysis (SCA), successfully recovering secret keys even in the presence of strong countermeasures. Despite its efficacy, Deep Neural Networks (DNNs) are predominantly black-box in nature. Evaluators do not know what information leakages are extracted and utilized across the network's layers. Yet, understanding this leakage flow is vital for designing more resilient cryptographic implementations. Existing explainability techniques often do not provide any explanation of the leakages at specific points within a layer's feature representation.
In this work, we introduce GlimpseDNN, a novel model-agnostic framework designed to provide layer-by-layer visualizations that reveal how DNNs process physical leakage traces to achieve secret key recovery. GlimpseDNN utilizes the stochastic leakage model to provide characterization of the underlying leakage in the intermediate features of each layer. A key advantage of the stochastic leakage model is its dual capability: it can learn complex leakage models and is inherently interpretable through its learned weights. We validate the GlimpseDNN framework on a simulated traces and various public datasets, including ASCADf, ASCADr, ASCADf_desync50 and ASCADf_desync100. In particular, we show that even when leakages fail to be captured in the original traces, the GlimpseDNN framework manages to find these leakages by considering the deeper layers of the well-trained DNN. This provides evaluators an alternative to glimpse the underlying leakage for identifying specific implementation vulnerabilities used by DNN, ultimately aiding in the design of more robust, side-channel-resistant hardware.
On the Fault Injection Security of White-box Ciphers
White-box security settings assume an extremely powerful adversary having full visibility and control of the software implementation and internal computations.
Leakage-based attacks extract secret information via a local passive attacker (e.g., malware) and transmit it to a remote server.
However, an active adversary, who can perform fault injections in a white box setting, has received limited attention, especially in the symmetric-key setting.
In this paper, we initiate a formal study of active data-only adversaries in
the white-box setting. Such adversaries preserve the control flow of the
implementation but corrupt a bounded number of key-embedded lookup-table
entries, enabling precise and repeatable manipulation of table values.
Unlike leakage-based attacks, which are constrained by the bandwidth and
existence of firewalls, such fault attacks can operate entirely locally. We focus
on a data-only tampering adversary that preserves the control flow of the
white-box implementation, but corrupts a bounded number of key-embedded
lookup-table entries.
Even under this stealth-preserving restriction, the
adversary can cryptographically weaken the implementation and make faulty
ciphertexts significantly easier to decrypt. We formalize such an active adversary by defining a new security notion and studying its impact on contemporary table-based white-box implementations.
Our analyses reveal a structural disparity between two major design paradigms: Feistel-based white-box ciphers appear significantly more vulnerable to fault injection than SPN-based designs. Finally, we propose a software-based fault detection mechanism that detects fault injections with high probability, strengthening resilience. We provide detailed analysis of the SPN-based cipher WEM (the same analyses also work for other SPN-based ciphers like SPNbox), and two Feistel-based ciphers SPACE and Galaxy. Our analyses reveal that SPACE and Galaxy are significantly more vulnerable than WEM, under our fault-based security setting. Precisely, we show that WEM achieves high security under all the adversarial models, whereas SPACE and Galaxy instances can be attacked with a very high message recovery probability of $2^{-8}$, when the adversary can choose the fault positions and the values and corrupts up to one fourth of the implementation table entries.
Rare-Event Decorrelation for Linear Tests of Low-Complexity Pseudorandom Functions
Linear tests are a basic obstacle to pseudorandom functions built from
low-depth circuits and secret linear or affine maps. Ball, Ducros, Erabelli, Kohl, Resch, and Scholl left open whether their bounded-query strong-PRF candidate in $\mathrm{AC}^0[2]$ resists general non-adaptive linear tests with polynomially many chosen queries. Boyle, Couteau, Gilboa, Ishai, Kohl, and Scholl left linear-attack resistance of their Sipser-based weak-PRF candidate open.
We address both questions through a common correlation argument based on rare local events. Repeated Cauchy--Schwarz reduces the original correlation to a parity correlation of indicators of substantially rarer events while preserving the independence supplied by the underlying linear forms. Pairwise independence suffices to bound the resulting parity correlation by a constant below $1$, while higher-order independence gives stronger cancellation.
For the candidate of Ball et al., this resolves the open problem for arbitrary polynomially many non-adaptive queries with unrestricted linear or affine dependencies. More generally, for every fixed $a\in(0,1)$ and
$q\le2^{a(\log_2\lambda)^2}$, every such linear test has bias $\exp(-\lambda^{1-a-o(1)})$.
For the Sipser-based family of Boyle et al., for every fixed $0<\varepsilon<2$, with overwhelming probability over $Q\le2^{(2-\varepsilon)(\log_2\lambda)^2}$ random samples, every linear attack
has bias $\exp(-\lambda^{\varepsilon-o(1)})$. This establishes linear-attack resistance throughout this quasipolynomial-sample regime. Extending the guarantee to the conjectured subexponential weak-PRF regime remains open.
HCTR$^{++}$ : A Beyond Birthday Bound Secure HCTR2 Variant
Current industry-standard block cipher modes of operation, such as CBC and GCM, are fundamentally limited by the birthday bound $O(2^{n/2})$, a constraint that has evolved from a theoretical concern into a practical security bottleneck in contemporary high-throughput, high-data-volume environments. To address this, the cryptographic community and NIST are prioritizing Beyond Birthday Bound (BBB) security to extend the operational security margin toward the full block size $O(2^n)$. Achieving BBB security requires a departure from traditional constructions, primarily utilizing three methodologies: XOR of Permutations (XORP), Tweakable Block Ciphers (TBCs), and Fresh Re-keying. While none of these innovative BBB modes have been formally standardized, NIST has initiated the Accordion Mode project, defining a new primitive class: the Tweakable Variable-Input-Length Strong Pseudorandom Permutation (VIL-SPRP). This primitive treats the entire message as a single, indivisible block and expects the submission of BBB-secure variants. To contribute to this standardization effort, we propose a simple BBB-secure variant of the HCTR2 algorithm based on Fresh Re-keying and a $2n$-bit $\varepsilon$-uniform-AXU keyed hash family. Under the stated hash assumptions and the ideal-cipher model, the construction achieves a beyond-birthday-bound security profile for bounded message lengths and sufficiently restricted tweak repetition. We first explain the core BBB methodologies, then discuss the operational mechanism of HCTR2, and finally present our proposed BBB-secure construction.
BOLT-FHE: An Efficient Unified Framework for GPU-based TFHE Bootstrapping via On-Chip Local Tiling Strategies
Bootstrapping is the main performance bottleneck in bitwise Fully Homomorphic Encryption (FHE), and practical acceleration requires careful orchestration of the blind rotation and external product chain under GPU resource constraints. This paper presents BOLT-FHE, a GPU bootstrapping framework that emphasizes block-local execution, on-chip tiling, and a unified MegaKernel supporting both gadget decomposition and modulus raising, with optional support for a recently proposed technique (Bergerat et al, CHES 2025) based on the common mask assumption (CM packing). Our design keeps the accumulator update chain within a single thread block and fuses NTT/INTT, external products, and accumulator updates using a fixed execution template. Two compile-time parameters—WPP (warps per polynomial) and IPT (items per thread)—control multi-warp cooperation and per-thread register footprint, enabling consistent kernel structure across different parameter sets.
On an NVIDIA RTX 4090, BOLT-FHE reaches 40,166 bootstrappings per second at 128-bit security, demonstrating high-throughput TFHE bootstrapping on a commodity GPU. Compared to the state-of-the-art GPU implementation VeloFHE (Shen et al, CHES 2025), BOLT-FHE achieves 1.85×–2.92× speedups with gadget decomposition. In particular, for modulus raising, BOLT-FHE improves by 2.38×–2.42× without CM packing, and by 3.17×–3.31× under the best packing configuration, reflecting the combined benefits of fused arithmetic, more regular memory access, and amortization enabled by CM packing. Overall, BOLT-FHE shows that a portable, fused-kernel organization with explicit on-chip budgeting can substantially improve TFHE bootstrapping throughput while remaining compatible with both noise management paths.
GPU-Assisted FAEST v3 Signing: Challenge Grinding and CPU–GPU Pipelining
Applying a GPU to FAEST v3 signing requires more than exploiting parallel computation: challenge grinding must preserve the minimum accepting counter selected by the original signing procedure, and single-sign latency and multi-sign throughput must be evaluated under distinct execution conditions. We implement GPU-assisted challenge grinding in which the GPU filters candidates over contiguous counter ranges in parallel, while the CPU performs the final acceptance checks in increasing counter order. For multiple independent signatures, we construct a CPU–GPU hybrid pipeline with two alternating signing-state slots, allowing CPU work for one slot to proceed while the GPU batch for the other slot is executing. Across the six non-EM FAEST v3 parameter sets evaluated on the same CPU–GPU system, the CPU–GPU path has lower representative single-sign latency for four parameter sets, whereas the optimized CPU path is lower for two. The largest representative same-session CPU/CPU–GPU latency ratio is 1.602799 for FAEST-192s. For multi-sign throughput with \(B \in \{2,4,8\}\), the CPU–GPU path has higher representative throughput in 9 of the 18 parameter–batch-size combinations, while the CPU path is higher in the remaining 9 under the predefined primary aggregation rule. Correctness validation confirms that GPU-assisted challenge grinding produces the same minimum accepting counter and final signature as the reference path for the evaluated configurations. These results show that the performance effect of GPU assistance is not uniform across the evaluated FAEST v3 signing configurations and depends on both the parameter set and whether the execution targets single-sign latency or the throughput of multiple independent signatures.
Processing-Time Effects on PQC-Based Over-the-Air Rekeying over CCSDS TC/TM Links
When post-quantum cryptography (PQC)-based over-the-air rekeying (OTAR) is evaluated over CCSDS Telecommand (TC) and Telemetry (TM) links, omitting endpoint processing time can change not only the final transport outcome but also the protocol execution path shaped by COP-1 retransmission and CLCW return feedback. This study instantiates the P1–P2–P3 exchange of a PQC-based Space Data Link Security (SDLS) key update over a CCSDS TC/TM transport model and performs paired comparisons between a zero-processing baseline, T₀, and a processing-aware model, T₁, whose service times are measured at seven logical stages of a study-specific Triple-KEM reference implementation. The two models are compared at three observation levels—final transport outcome, canonical event path, and continuous timing—while varying processing scale, finite contact time, direction-specific loss, and schedule phase. Under the canonical schedule with measured processing at αs = 1, no final-transport-outcome discordance is observed in the evaluated BCH and LDPC(512,256) TC-only or TM-only conditions, although some paired trials follow different canonical event paths. At some predefined TM-only processing-scale points, bidirectional final-outcome discordance is observed between success and P2-stage failure. The agreement state also varies with the evaluated finite contact time, and a schedule-phase case exhibits a larger transport-completion timing difference aligned with the TM slot structure. Under the evaluated conditions, the effect of omitting processing time therefore cannot be characterized by success or failure alone and must be interpreted together with event-path, timing, contact-time, and schedule conditions.
N2SF-Based Post-Quantum Cryptography Migration Framework for Data in National and Public Institutions
This paper proposes post-quantum cryptography (PQC) migration decision criteria for data in national and public institutions, based on the protection requirements of the National Network Security Framework (N2SF) and the cryptographic dependencies and operational states of data. The criteria distinguish payload retention, key rewrapping, re-encryption, communication migration, and signature renewal. Required actions are separated from decisions to allow, defer, or deny execution. Completion requires consistent results for the same object and version, recovery of registered copies, and current authority. A reference implementation examined these decisions under supported conditions. In 225 policy trials, completion/read rechecking and per-stage rechecking exhibited none of the unauthorized completions or reads observed with initial-decision reuse. Nine interruption trials confirmed resumption by reconciling artifacts with records. These results support the feasibility of the criteria in the local reference environment; institutional approval, production key management, and long-term preservation continuity remain unvalidated.
On Best-Possible One-Time Programs
One-time programs (OTPs) aim to let a user evaluate a program on a single input while revealing nothing else. Classical OTPs require hardware assumptions. Quantum measurement offers a possible physical basis for one-time use: obtaining an output may irreversibly disturb the program needed for further computation. Yet deterministic functionalities remain impossible due to gentle-measurement attacks (Broadbent, Gutoski and Stebila, 2013). While recent works achieve positive results for randomized functionalities with high-entropy outputs (Gunn, Movassagh 2025; Gupte, Liu, Raizes, Roberts, Vaikuntanathan 2025), the fundamental limits and the strongest achievable security notions remain poorly understood.
Inspired by classical obfuscation, we ask for a “best-possible” one-time compiler: a generic transformation that, for any functionality, leaks the least amount of information compared with any other one-time implementation. We show that a generic best-possible one-time compiler cannot exist even for classical randomized functionalities assuming $\mathsf{SZK} \not\subseteq \mathsf{BQP}$.
Given this impossibility, we identify a natural subclass of one-time compilers called “testable one-time program” compilers, which output quantum states augmented with reflection programs for themselves. (1) We formulate a simplified, generalized Single-Effective-Query (SEQ) simulation security notion for quantum channels. The definition uses self-adjoint implementations whose behavior under arbitrary quantum interactions depends only on the channel. We show that SEQ security implies best-possible testable one-time security. (2) We construct SEQ-secure OTPs for all quantum functionalities in the classical oracle model, yielding the first positive results for arbitrary quantum channels beyond classical randomized functionalities. Thus, SEQ security could serve as a testable one-time analogue of virtual black-box (VBB) security in the many-time obfuscation setting.
Finally, we propose stateful quantum indistinguishability obfuscation (stateful quantum iO) — quantum state obfuscation for stateful quantum programs. It implies best-possible testable OTPs and is achievable in the classical oracle model, thus giving us a promising approach towards best-possible testable OTPs in the plain model.
X-Wing on Cortex-M85: Architecture-Aware Integration and End-to-End Evaluation
X-Wing combines ML-KEM-768 and X25519 for hybrid key establishment. On Cortex-M85, we adapted the coefficient representation and storage order of an MVE NTT to the existing ML-KEM path and optimized data-format transformations and X25519 arithmetic while preserving draft-10. During encapsulation, the two X25519 results share an inversion. We compared the eight-technique integrated implementation B8 with the baseline A0 in the same executable. Across ten paired comparisons from five independent reflashes of one EK-RA8M1 board, the minimum reported cycle reductions were 18.61% for key generation, 18.89% for encapsulation, 12.25% for decapsulation reusing an expanded key, and 15.22% for decapsulation including seed expansion. Nonvolatile storage increased by 35,692 B, including a 33,024 B fixed-base table. We separately report the cost and validation of B8S, which corrects identified secret-sign-dependent operand-address selections in B8. Some key-varying tests retained timing signals after this correction. Their causes remained partly unresolved, so no whole-program constant-time pass is claimed for B8S.
Batched LSH on ARMv8 NEON and Its Application to K-SPHINCS+
With FIPS 205 standardizing post-quantum signatures and ARMv8 spanning mobile, embedded, and server platforms, fast hash-based signing on ARM has become a pressing need. Since these schemes are dominated by hash calls, hash optimization largely determines performance. K-SPHINCS+ replaces the internal hash of stateless SPHINCS+ with LSH, a Korean standard hash family. However, prior K-SPHINCS+ work provides only reference C code, and existing ARMv8 LSH implementations mainly optimize single-call latency. We present two results on ARMv8-A. First, we reimplement three published LSH optimizations in hand-written AArch64 NEON assembly: the 2019 word-permutation technique; the 2023 ARMv8 P-domain placement and LSH-256 2-way approach; and the 2024 AVX-512 word-parallel and GPU lane-batching designs. We also test whether NEON scheduling guidance from a 2022 AArch64 Keccak/SPHINCS+ paper transfers to LSH. Every variant must pass 2,063 public known-answer test vectors and a differential test suite before benchmarking. No single-message NEON implementation beats the KISA portable C code compiled with clang -O3 (0.75–0.90×). Only message-parallel batching wins: for LSH-256, hashing two or four independent messages across NEON lanes reaches 1.53–1.66× and about 2.0× the throughput of sequential C. Second, we build, to our knowledge, the first optimized K-SPHINCS+ by integrating a four-message LSH batch core into the WOTS+ chain, FORS leaf, and Merkle tree computations of the SPHINCS+ reference framework. All six parameter sets pass the framework’s tests, and all three hash backends (reference C, single-message NEON, four-message NEON) produce byte-identical signatures. On the same machine, batched K-SPHINCS+ signs 2.5–2.6× faster than K-SPHINCS+ with reference C LSH and, for the 128-bit parameter sets, 2.9–3.2× faster than the SHA-256/SHAKE256 SPHINCS+ reference implementations. All code and raw measurements are public.
Optimized NEON Implementation of MAYO on Apple M1
MAYO is one of nine third-round candidates in NIST’s process for additional post-quantum signatures. Its third-round specification of August 2026 changed the level-1 parameters and added a hash-derived linear term Λ to the verification equation, so earlier optimised implementations no longer match it. We present an optimised NEON implementation of MAYO Round 3 for the Apple M1 and compare it with the upstream NEON code on the same machine. A generator emits the sixteen GF(16) kernels of each parameter set as assembly whose output is byte-identical to that of the upstream intrinsics. Apart from the Λ kernel, the large kernels reach 86–96% of the speed an operation-count model predicts. A transposed constant-time echelon form needs 55–70% fewer cycles than the upstream one. An eight-way interleaved AES expands the public matrices at 0.18 instead of 0.43 cycles per byte. The linear term is expanded with NEON; with our changes off, its portable-C AES derivation takes 10–22% of signing and 18–37% of verification. As medians over seven function alignments, compact-key signing is 1.99–2.12 times faster than upstream on all four sets, and verification 2.11–2.62 times. A constant-time campaign with matched null runs finds the linear-algebra tests indistinguishable from their nulls, at 25% power for a twofold dispersion. The MAYO₂ signature test differs. Verification, which holds no secret, shows a key-fixed timing effect on public data, upstream as well; the signature test does not separate it from a secret one. All measurements are on one M1 Pro.
Output Policies for Anomaly Detection with Homomorphic Encryption: Threshold Resolution, Decision Preservation, and Numerical Stability
Homomorphic encryption computes anomaly scores without exposing inputs, but released scores and decisions can reveal a private threshold. We evaluate whether output policies limit numerical threshold information while preserving existing decisions, and whether this limitation also impedes decision prediction on other inputs. Policies distinguish internal-score and released-score decisions and share decision-loss and score-distortion constraints. Thresholds were estimated in all 45 plaintext experiments combining three intrusion-detection datasets, three scoring models, and five seeds. All 45 CKKS experiments combining the same datasets, five autoencoder seeds, and three independent keys yielded threshold-containing intervals after revalidating supplied starting intervals. A 16-query cap stopped every plaintext baseline search but served only 16 of 512 separate usage requests, reducing availability. Under random splitting, released-score quantization preserved 99.864% of decisions on average while limiting numerical threshold precision. Surrogates trained on 128 decision-only responses achieved mean balanced accuracy 0.817. With training-only preprocessing and a CIC-IDS2017 weekday split, model-wise balanced accuracies were 0.816–0.911. Separating time and Flow IDs across five resampled evaluations reduced model-wise means to approximately 0.5, showing that prediction transfer depends on data splitting. Threshold-dependent reselection of quantization width changed responses that matched under fixed widths. Selected CKKS boundary tests yielded one released-decision mismatch in 57 queries. Numerical threshold information and service decision prediction therefore require separate protection goals. Output policies must assess decision preservation and response rate alongside policy selection, data splitting, and numerical boundary conditions.
Verifier-Aligned Canonical Source Binding for Homomorphic Encryption Computations
q0 preprocessing verification and native HE computation verification can each succeed without establishing that their results refer to the same canonical source. To address this source mismatch across verification paths, we propose a verifier-aligned public-input transfer procedure that links heterogeneous authenticated artifacts to a single canonical-source relation. The public verifier reconstructs challenges and targets from the actual statements, roots, approved verification keys, and authenticated positions. The chunk circuits then verify the source and mask commitments together with the canonical range, sign, and partial-sum relations. The full-input implementation processes 524,288 coefficients across 128 blocks and 4,096 native-bridge chunks. Public reconstruction and verification without stored challenge caches take 184.77 seconds, with 27,345,153 B of explicit public data. In a representative-block comparison for the same relation, sharing duplicate hash, range, and sign computations reduces the number of constraints by 33.53% and proving time by 31.10%, while preserving the proof-body size. In contrast, three upstream proof artifacts account for 88.44% of the total public data. These results show that eliminating redundant circuit computations is effective for reducing prover-side cost, whereas the dominant public-data cost originates from separate upstream proof artifacts. Prover computation and public-data size should therefore be treated as distinct optimization targets in source-binding verification. This work specifies the common-source relation between heterogeneous HE verification results and evaluates its implementation at full input scale.
HyBind: Structural Analysis of PQ/T Hybrid Cryptographic Usage
The quantum threat to traditional public-key cryptography makes migration to post-quantum cryptography necessary. During migration, the presence of both post-quantum and traditional (PQ/T) algorithms does not establish that their outputs jointly determine a key or verification decision. We propose HyBind, an intraprocedural Python source-analysis framework using registered API contracts. HyBind traces component secrets to returned keys and checks whether signature acceptance requires both verifiers to succeed. Function-return and execution-effect checks account for alternative outcomes and changes to local bindings. Two internal presence-based heuristics give identical decisions for joint versus omitted secret contribution and AND versus OR verification, while HyBind distinguishes these structures. All 50 controlled fixtures match their specified outputs with the annotation assumption enabled. A separate suite of 33 programs, including 15 using native cryptographic APIs, matches its specified positive-finding counts in both settings. Native runtime checks exercise ML-KEM/X25519 key derivation and ML-DSA/Ed25519 acceptance. Relaxing return or effect requirements admits traditional-only key results as hybrid findings in the evaluated cases. HyBind provides the contributing calls and outcome evidence needed to review whether an individual traditional invocation participates in a PQ/T hybrid.
Game-Theoretically Fair Distributed Coin Tossing With Private Preferences
Secure coin-tossing is typically modeled as an input-less functionality, where parties with no private inputs jointly generate a fair coin. In the dishonest majority setting, however, a strongly fair coin-tossing protocol is impossible. To circumvent this barrier, recent work has adopted the weaker notion of game-theoretic fairness, where adversaries are rational parties with preferences for specific outcomes, seeking to bias the coin in their favor.
Yet these preferences may encode secret information, making prior protocols that assume preferences are public, fundamentally incompatible with privacy.
We initiate a comprehensive study of privacy-preserving game-theoretically fair coin-tossing, where the preferences of honest parties remain private.
We propose a simulation-based security framework and a new ideal functionality that reconciles both preference-privacy and game-theoretic fairness. A key ingredient is a certifying authority that authenticates each party’s preference and publishes only aggregate statistics, preventing misreporting while hiding parties' preferences.
The functionality guarantees that every honest party receives an output: either a uniform coin; or, if an adversary deviates, a coin that strictly decreases the adversarial coalition's expected utility.
Within this framework, we construct a protocol realizing our ideal functionality under standard cryptographic assumptions that works for both binary and general $m$-sided coin-tossing. Our schemes tolerate the same optimal (or nearly optimal) corruption thresholds as the best known protocols with public preferences (Wu-Asharov-Shi, EUROCRYPT '22; Thyagarajan-Wu-Soni, CRYPTO '24). Technically, our protocols combine authenticated preferences with an anonymous communication layer that decouples identities from preference-dependent actions, together with a deviation-penalty mechanism that enforces game-theoretic fairness.
Our work is the first to reconcile game-theoretic fairness with preference privacy, offering new definitional tools and efficient protocols for rational multi-party computation in dishonest majority settings.
Public-coin Differing-input Obfuscation from KOALA and iO
We show that the recent construction of witness encryption (Hair and Sahai, arXiv:2609.18275v1) is a public-coin extractable witness encryption scheme under the Knowledge of Orthogonality Assumption, or KOALA for short (Buellens-Wee, PKC 2019). As an immediate application, we obtain public-coin differing-input obfuscation (diO) from KOALA and indistinguishability obfuscation (iO).
Randomness-Anchored Runtime Discovery of Cryptographic Operations on Linux Using eBPF
Migration to post-quantum cryptography requires knowing not only which cryptographic libraries are present on a system, but which algorithms are actually executed at runtime. Static binary analysis answers the former question; the latter requires dynamic observation. We present a runtime cryptographic discovery system for Linux, built on eBPF user-space probes, that detects classical and post-quantum operations as they execute. Because key generation and encapsulation consume fresh randomness, the system treats randomness observations as temporal anchors and correlates them with the cryptographic calls that follow in the same process, producing a stream of confidence-scored events for a runtime cryptographic inventory. An ablation over three detection configurations shows that randomness alone is not a sound detector, while API detection reaches perfect precision and recall on classical and ML-KEM workloads with no false positives on random-only negatives, and the randomness anchor raises the confidence of those detections without adding any. A single probe set also covers native post-quantum support in current OpenSSL releases. Median detection latency is 28 μs (P99 48 μs), largely insensitive to a four-round tuning sweep, with overhead of 14–18% on a key-generation-bound workload, full detection under sustained and concurrent load, and stable behavior over a one-hour run. A case study across nine application cases drawn from or paired with the QED datasets shows where static and runtime views agree and how probe coverage determines what runtime discovery can observe.
Role-Specific Signature Placement in TLS 1.3: Cost Propagation and PQC Migration
Certificate issuance and per-connection signing impose different costs in TLS 1.3, and authentication cost can change depending on how signature algorithms are assigned to Root, Intermediate, and Leaf roles. PQC migration should therefore consider not only algorithm performance, but also role placement, certificate structure, network conditions, and server load. We evaluate all 13³ role placements formed by 13 signature parameter sets while holding the algorithm composition fixed and changing only the role order. The evaluation covers cryptographic operations, certificate issuance, path validation, TLS authentication, mixed traditional–PQC chains, network profiles, session resumption, and concurrent load. Across 286 groups containing three distinct algorithms, the median maximum/minimum ratios are 2.085 for TLS latency, 4.310 for Certificate body size, and 4.551 for path validation. Thus, role placement alone can produce about a two-fold difference in TLS latency and more than four-fold differences in certificate size and path-validation cost. Direct Root–Intermediate swaps yield a median TLS ratio of 1.003, whereas swaps involving the Leaf yield 1.775–1.788, indicating a stronger influence of Leaf placement. In eight ML-DSA-65/SLH-DSA-SHAKE-192s placements, two candidates remain nondominated when only the Certificate message is considered, but only one remains when the Leaf signature in CertificateVerify is included. This shows that certificate size alone may not represent the transmission cost of the full TLS authentication path. PQC certificate-chain design should therefore consider role-specific computation and transmission costs under the intended network and load conditions.
Post-Quantum Command Authentication for Unmanned Systems: A KpqC Feasibility Study under Real-Time and Bandwidth Constraints
The command and authentication channels of unmanned systems (UAVs and UGVs) still rely on classical public-key cryptography, which large-scale quantum computers threaten. Migrating these channels to post-quantum cryptography (PQC) is therefore imperative, yet PQC keys and signatures are substantially larger, and sometimes slower, than their classical counterparts, while command links are tightly constrained in message rate, maximum transmission unit (MTU), latency deadline, and bandwidth. Whether a given PQC algorithm fits such a budget, and how to mitigate it when it does not, remains an open and practically important question. This paper studies the application of Korean PQC (KpqC: HAETAE, AIMer, SMAUG-T, NTRU+) to the authentication and key-establishment path of ROS2/DDS-Security, framed as a command-channel size-latency budget problem. We keep KpqC as the subject of study while using the NIST standards (ML-KEM, ML-DSA, SLH-DSA) as a familiar yardstick and classical ECDSA/ECDH as the migration baseline, giving a classical→NIST→KpqC three-way comparison on a single, consistent testbed. We define a feasibility envelope that maps each algorithm to the channel conditions it can meet, and we validate it with authentication-handshake measurements over emulated constrained links on a two-node testbed. Our results yield an application guideline indicating which KpqC candidate is admissible for which command-channel budget.
Deploying Native-Rust KpqC: Pluggable Post-Quantum KEMs and Signatures across TLS, Space Links, and the OQS Ecosystem
Post-quantum migration is no longer only an algorithm problem but a deployment problem: standardized schemes must be dropped into real protocol stacks, on real (often resource-constrained) targets, without giving up memory safety. The Korean Post-Quantum Cryptography (KpqC) competition standardized two KEMs (NTRU+, SMAUG-T) and two signature schemes (HAETAE, AIMer), distributed as memory-unsafe C. Building on our native-Rust KpqC implementation, we expose the schemes through a single pluggable provider and evaluate them across three deployment front-ends: (i) a rustls TLS 1.3 key-exchange group, (ii) an Open Quantum Safe (OQS) compatible C ABI that lets the native-Rust code stand in for the C reference behind the liboqs API, and (iii) an analytical CCSDS/SDLS satellite constrained-link model. All three are demonstrated end-to-end: a complete TLS 1.3 handshake using only a KpqC KEM for key establishment, a C program that drives the Rust KEMs and signatures through the OQS-shaped ABI, and a fragmentation/latency analysis over illustrative LEO/GEO link profiles. This work extends our earlier C/OQS-OpenSSL TLS benchmark of KpqC (Sim et al.) with a memory-safe Rust implementation, an explicit memory-footprint axis, and deployment breadth beyond localhost/LAN. On a constrained space link, the compact SMAUG-T key exchanges (SMAUG-TiMER 1280 B, SMAUG-T1 1344 B) are smaller and faster than ML-KEM-768 (2272 B). All seven KpqC KEM parameter sets and four signatures (AIMer and HAETAE modes 2/3/5) are demonstrated across the three front-ends. We further give NTRU+ a full memory-optimized build for all three sets, byte-identical and KAT-verified, that cuts peak stack by up to 25% at no measurable time cost (≈ 0.99× handshake latency).
Measuring Parallel Execution of Classical–PQC Component Pairs in Hybrid TLS 1.3
Hybrid key exchange and Composite ML-DSA signatures in TLS 1.3 split one operation into a classical component and a post-quantum cryptography (PQC) component that do not depend on each other. Using a cryptographic workload of the TLS handshake rather than a full TLS connection, this paper measures whether running the two components at the same time on two pthread worker threads reduces latency compared with sequential execution. We evaluate the three ECDHE–ML-KEM groups of RFC 10024 with the matching Composite ML-DSA schemes, each with server authentication and mutual authentication (mTLS). Parallel execution keeps the order of operations, overlaps only the component pair of one operation, and is timed with all synchronization cost included. In an ARM and an x86 environment, parallel execution was faster in all six conditions, with speedups of 1.157×–1.281× and 1.041×–1.235×. The gain was large in the signature stages, where the two components take similar time, and small or negative in the key exchange stages, where one component dominates. In a low-power x86 environment, however, the same source code was slower in all six conditions (0.800×–0.917×). There, the overhead of waking and waiting for the worker threads exceeded the time saved, and it grew with the stage length, so a fixed cost per pair does not explain it. Independence of the components therefore does not guarantee a gain, and parallelization should be applied only after measuring in the target environment.
Optimizing Montgomery Arithmetic for RSA on Cortex-M0+ and Cortex-M3
Cryptographic tokens that retain RSA credentials for compatibility with existing authentication systems require efficient private-key operations on small processors. Cortex-M0+ (M0+) lacks native widening multiplication, whereas Cortex-M3 (M3) provides it with operand-dependent latency. We optimize Montgomery multiplication and squaring using 15-bit limbs and integrate the kernels into RSA-2048 and RSA-3072 private operations based on the Chinese remainder theorem (CRT). On M0+, a wrapped sum and accumulated block quotients enable exact carry recovery. The squaring schedule integrates square and reduction columns without storing the complete square. On M3, we retain the established half-diagonal representation and double each buffer limb when it is first incorporated into Montgomery reduction, eliminating a separate buffer traversal. We establish accumulator bounds for exact Montgomery digit and carry recovery in both schedules. At operand widths of 1024 and 1536 bits, the M0+ representation and register mapping reduce Montgomery multiplication and squaring cycles by 12.60% to 13.11% against blocked two-word controls. The M3 schedule reduces Montgomery squaring cycles by 2.12% to 3.08% with half-diagonal initialization and triangular accumulation held fixed. Kernel replacement in otherwise unchanged RSA implementations reduces warm CRT cycles by 12.59% to 12.80% on M0+ and by 1.69% to 2.39% on M3. Our M3 Montgomery multiplication also uses 31.47% fewer cycles than a reproduced number-theoretic transform (NTT) implementation for 2048-bit operands with matched integers and canonical outputs.
Pseudorandom Codes from LWE
A pseudorandom code (PRC), introduced by Christ and Gunn (Crypto 2024), is an error-correcting code whose codewords look uniformly random to anyone without the secret key. PRCs not only are natural cryptographic objects to study in their own right, but also have interesting applications such as undetectable watermarking of AI-generated content. Previous PRC constructions have centered on Learning Parity with Noise (LPN), often combined with additional assumptions. In particular, the original PRC of Christ and Gunn is based either on standard LPN together with the planted XOR assumption of Agrawal et al. (Crypto 2024), or on subexponential LPN.
In this work, we construct PRCs from Learning with Errors (LWE), providing an alternative foundation for PRCs. Our construction is simple: a codeword is the one-bit rounding of an LWE sample, masked by a random string. The construction can be easily understood as an LWE analogue of the PRC of Christ and Gunn. Indeed, like theirs, it is based either on standard LWE together with the hardness of the planted $t$-SUM problem of Agrawal et al., or on subexponential LWE. However, as the rounding is not linear, its robustness is less straightforward, and we prove it using Fourier analysis.
Plotkin Attacks! On the (Mis)use of Raptor Codes in Asynchronous Verifiable Information Dispersal
Some asynchronous verifiable information dispersal (AVID) and data-availability protocols certify that a disperser's message is available once $2f+1$ of $n=3f+1$ parties, at most $f$ of them Byzantine, attest that they hold their erasure-coded fragments, and defer reconstruction and validation of the encoding until later. We call this design pattern reconstruct-later AVID. If the $f$ Byzantine attesters later withhold their fragments, reconstruction must succeed from the $f+1$ honest fragments that remain, and a Byzantine disperser chooses which $f+1$ after seeing the encoding symbols assigned to the honest parties. We call a subset of fragments that does not determine the message bad. Raptor codes are a tempting choice here: with modest coding overhead they have very small decoding-failure probability under random erasures, and a preliminary Walrus design and an earlier Walrus testnet used RaptorQ in this way. We show that the pattern is insecure with the standardized Raptor codes R10 (RFC 5053) and RaptorQ (RFC 6330). For a message of $K$ input symbols, every assignment of R10 encoding symbols to the honest parties contains a bad $(f+1)$-subset whenever $K>\lfloor\log_2(2f+2)\rfloor$, and every RaptorQ assignment whenever $K>7H_{\mathrm{HDPC}}+\lfloor\log_2(2f+2)\rfloor$, where $H_{\mathrm{HDPC}}$ is RFC 6330's number of high-density parity-check symbols. Under slightly stronger conditions, randomized polynomial-time algorithms find such subsets, and an implementation of the RaptorQ attack defeats an RFC 6330 decoder on every adversarial subset tested. The key ingredient is the Plotkin bound, which forces a nonzero input whose encoded image has low Hamming weight. For RaptorQ at $n=3f+1$, an empirical attack over $\mathbb{F}_{256}$ succeeds at every tested $f$ from $9$ to $45$ with $K=f+1$, far below the $f=77$ at which the bound above first applies, and empirical attacks over $\mathbb{F}_4$, $\mathbb{F}_{16}$, and $\mathbb{F}_{256}$ succeed at values of $K$ well below that bound. For R10, a smaller $K$ does not help: for every standardized $34\le K\le8192$ and every $n$ with $3f+1\le n\le4f\le65520$, explicit certificates give a bad subset for every assignment to the honest parties when the encoding-symbol identifiers (ESIs) are $0,1,\ldots,n-1$, and with probability at least $1/2$ when the ESIs are uniformly random. Benchmarks of our implementations show that the MDS alternative costs little: in our parameter regime, Reed-Solomon is often faster than, and never more than a small constant factor slower than, either R10 or RaptorQ, for both encoding and decoding.
Bandwidth-Balanced Reliable Broadcast in Stake-Weighted Networks
Consider an asynchronous network of $n$ validators in which Byzantine validators hold less than one third of the stake. In erasure-coded reliable broadcast, validators relay fragments of the sender's message. A validator's relay-upload cost is the amount of fragment data it transmits outside the sender's initial dispersal. Assigning each validator a number of fragments proportional to its stake makes the heaviest validators relay far more data than the rest. We show that this imbalance is unnecessary.
We give Balanced CT and Balanced MiniCast, adaptations of Cachin-Tessaro (CT) and MiniCast (Locher and Shoup, EUROCRYPT 2025) that retain stake-weighted voting but assign one fragment to each validator, giving every honest validator the same relay-upload bound. Their maximum relay-upload costs depend on how few validators can exceed one third of the total stake for CT, or two thirds for MiniCast. Stake skew can amplify MiniCast's advantage beyond the approximately twofold improvement in equal-stake networks. For the real-world Monad distribution with $n=200$, the leading maximum relay-upload costs, as multiples of the message size, are approximately $72.2$ for CT with proportional assignment, $8.7$ for Balanced CT, and $2.2$ for Balanced MiniCast.
The balanced constructions pay for their low maximum cost with a higher total relay-upload cost. To reduce that total while retaining a prescribed maximum-cost bound, we give a new Capped Swiper heuristic. On eight real-world stake distributions, with at most $4n$ fragments per code, it lowers total relay-upload cost by 19-81% for CT and 16-71% for MiniCast relative to their balanced counterparts, while keeping maximum relay-upload cost at most 10% higher. We also give sender-aware variants of both constructions in which the sender relays no fragment data, reducing its per-broadcast burden.
Query-Limited RAM Programs and their Applications
Quantum one-time programs (Broadbent, Gutoski and Stebila, CRYPTO 2013) or OTPs for short, enable a functionality to be encoded into a quantum token that can be evaluated on a single chosen input and then becomes unusable. While powerful, this primitive is inherently stateless and tied to a setting in which a quantum token needs to be issued and distributed for every single evaluation of a circuit. This raises a natural question: can the one-time computation paradigm be extended to richer, stateful forms of controlled access, and would such an extension offer inherent advantages beyond standard OTPs?
We introduce query-limited RAM programs (QLPs), a RAM-generalization of QOTPs that supports structured, stateful computation under bounded or policy-driven access. QLPs allow controlled sequences of evaluations while preventing adversarial forking or rollback of computational state. This enables new applications beyond stateless one-time programs, including quantum tokens for Turing Machines whose size depends only on code length (and not runtime), transferable $k$-time or budget-limited programs, and low-communication mechanisms for delegating computation in settings such as Software-as-a-Service.
To construct QLPs, we introduce one-shot programs, unifying one-shot signatures (Amos, Georgiou, Kiayias and Zhandry, STOC 2020) with the single effective query paradigm (Gupte, Liu, Raizes, Roberts and Vaikuntanathan, STOC 2025). We prove that one-shot programs generically imply query-limited programs, demonstrating that the strengthened unclonability guarantees of one-shot signatures translate into enhanced functionality. Along the way, we clarify the relationship between signature-token primitives and quantum one-time programs via generic constructions, essentially showing that one-time signing programs imply one-time general computation.
How to Attack Poseidon via Smart Subspace Restriction
Poseidon [Grassi, Khovratovich, Rechberger, Roy, and Schofnegger; USENIX'21] is an arithmetization-oriented (AO) hash function designed to be highly efficient in real-world zero-knowledge (ZK) applications. As a sponge-based construction, its algebraic security inherently relies on its underlying permutation, Poseidon-$\pi$, and the dense mixing of its layers: the initial full rounds ($R_{f_0}$), middle partial rounds ($R_p$), and final full rounds ($R_{f_1}$). One of the common approaches to argue security is to bound the effort of solving the $k$-Constrained-Input $k$-Constrained-Output (CICO-$k$) problem over this permutation of state size $t\geq2k$. Recent cryptanalysis has utilized subspace restriction to mitigate algebraic degree growth in Poseidon and used it to argue improvements in CICO-$k$ solving, though prior methods have faced strict limits on the number of rounds they can successfully bypass (more specifically, $<2$) and have targeted $k\leq2$.
In this paper, we introduce a unified mathematical framework for advanced subspace restriction in Poseidon cryptanalysis. We first present a baseline gadget; Generalized S-Box Skipping via Subspace Restriction (GSR); that deterministically absorbs $2t-2k$ total S-boxes across: one initial full round ($t$ S-boxes) and $t-2k$ partial rounds (one S-box per round). This significantly reduces the polynomial degree of the Poseidon multivariate polynomial system. By restricting the subspace of the total constraints satisfying solutions, independent of the round constants and MDS matrix selection, the distinguisher expends input degrees of freedom (DoFs) to linearize the internal state transitions where the dense algebraic mixing usually occurs.
We then explain and break the first theoretical barrier that confines such subspace restriction techniques to configurations with exactly $R_{f_0}=1$ initial full round. We formalize $(k+1)$-wise collapsing, a non-trivial DoF consumption framework. By parameterizing the system from an intermediate state and formulating constraints backwards, Round 1 is naturally skipped at zero cost. Building on this baseline, for $R_{f_0} \ge 2$ and under the CICO-$k$ setting, $(k+1)$-wise collapsing non-trivially expends a portion of the available DoFs to project state variables into the nullspace of targeted inverse MDS submatrices. This forces a perfect algebraic cancellation of non-linear inverse S-boxes, effectively absorbing the second full round entirely.
We show how the residual DoFs, after applying $(k+1)$-wise collapsing, can be either used to combine GSR for partial round skipping or alternatively deployed for bidirectional collapsing, i.e., to skip almost one full round from the back (defeating prepended/appended linear layer defenses) or can be used to construct exactly determined zero-dimensional ideals of strict degree-$3^{1+R_{f_1}}$ for $R_{f_0}=3$ instances.
Our framework drastically improves upon the state-of-the-art algebraic limits of Poseidon, most notably by identifying a critical gap in derived theoretical cryptanalysis bounds. We demonstrate that monolithic Macaulay matrix approximations heavily over-estimate true solving complexity. By utilizing residual DoFs to construct exactly determined zero-dimensional ideals of strict degree-3 for $R_{f_0}=3$ instances, we empirically validate our framework by tracking the step-wise intermediate peak of Faugère's $F_4$ algorithm in $\mathtt{msolve}$. Through this, we successfully extract the Gröbner basis for a mathematically intractable $(3,8,0)$ instance of Poseidon with KoalaBear ($t=24$) in under 5 minutes on a standard 96-thread server.
Further, in terms of monolithic complexities, where baseline estimates shows a mathematically intractable $F_4$ and FGLM time complexities of $\approx 2^{560}$ and $\approx 2^{404}$ bit operations, respectively, for a $(3,10,3)$ CICO-1 configuration, our framework successfully isolates the system into a degree-$3^4$ ideal, reducing the theoretical time complexities to $\approx 2^{121}$ and $\approx 2^{71}$ bit operations, respectively. Similarly, for a $(3,5,3)$ CICO-2 instance, we achieve a reduction in $F_4$ and FGLM time complexities from $\approx 2^{540}$ and $\approx 2^{390}$, respectively, to $\approx 2^{100}$ and $\approx 2^{69}$ bit operations, respectively, thereby bringing heavily constrained Gröbner basis attacks significantly closer to practical feasibility.
We then demonstrate how deploying $(k+1)$-wise collapsing combined with GSR significantly improves the reach of interpolation-based and resultant-based CICO attacks on configurations targeting $R_{f_0}=2$. For the industry standard KoalaBear instance where $(R_{f_0},R_p,R_{f_1})=(4,23,4)$, our results achieve penetrations up to (2,14,4), i.e., 20 rounds for CICO-1, and (2,9,4), i.e., 15 rounds for CICO-2.
Finally, when applying our baseline GSR technique only to $R_{f_0}=1$ configurations, our results further extend the attack reach to larger round-reduced versions. We successfully attack up to (1,23,4), i.e., 28 out of 31 rounds for CICO-1, and (1,20,4), i.e., 25 out of 31 rounds for CICO-2, overall establishing new practical limits for subspace restriction against Poseidon.
Obscura: Privacy-Preserving Protocol for the Algorand Blockchain Using LSAG Ring Signatures
While public blockchains provide transparent and auditable transaction histories, they inherently compromise user privacy. Existing privacy-enhancing protocols, such as those deployed on Ethereum, typically rely on succinct zero-knowledge proofs (zk-SNARKs) to obscure the transaction graph. However, implementing comparable cryptographic guarantees on high-throughput blockchains like Algorand is challenging due to strict per-call execution budgets and the state contention introduced by global Merkle accumulators. This paper presents Obscura, a decentralized, non-custodial privacy protocol tailored for constrained smart contract environments. Obscura achieves transaction anonymity using Linkable Spontaneous Anonymous Group (LSAG) signatures over the BN254 elliptic curve, verified entirely on-chain. To overcome limitations of the Algorand Virtual Machine (AVM), we introduce a novel state model that leverages Algorand's Box Storage for $O(1)$ commitment membership checks, eliminating the need for global Merkle accumulators, and a dynamic opcode-budget expansion mechanism via pooled inner application calls. Our implementation demonstrates that signer-ambiguous privacy is practical and efficient on Algorand without relying on trusted setups or succinct proofs. Obscura provides a robust privacy layer for transparent ledgers, bridging the gap between high-throughput blockchain architectures and the dual requirements of cryptographic privacy and selective auditability.
Bitwise-Optimal Cryptography: From One-Wayness to Pseudorandomness and Target Collision Resistance
We study cryptographic primitives that are both locally computable (i.e., in $\mathrm{NC}^0$) and exponentially secure. For pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs), we further require linear stretch and linear compression, respectively, which is essentially the best one can hope for in this setting. Such primitives simultaneously achieve an extreme level of security and efficiency: each output bit inspects only a constant number of input bits, while each input bit buys a constant amount of security and expansion/shrinkage, in an amortized sense. We refer to such primitives as \emph{bitwise optimal}.
We prove that bitwise-optimal PRGs and UOWHFs can be obtained from \emph{any} exponentially secure one-way function (OWF) in $\mathrm{NC}^0$, thereby establishing an equivalence between these three primitives in the bitwise-optimal regime. Notably, an analogous equivalence is not known in the exponential-security regime for general, unrestricted cryptographic primitives without imposing an additional regularity condition.
Our results combine the machinery of the author (Applebaum, FOCS'17) with new structural results on locally computable functions that may be of independent interest. We prove a sparsification theorem that reduces the output length of any exponentially secure local OWF to $O(n)$ while preserving exponential hardness, an input-locality reduction that bounds the number of outputs affected by each input bit, and a structural theorem showing that functions with bounded input locality are typically almost regular. Together, these ingredients remove the regularity assumption required by previous constructions and yield a non-black-box transformation from exponentially secure OWFs in $\mathrm{NC}^0$ to bitwise-optimal PRGs and UOWHFs. As an additional contribution, we prove a projection-based compression theorem for locally samplable sources.
Kettle: Short Post-Quantum Threshold Signatures from the HAWK Signature Scheme
HAWK is a lattice-based hash-and-sign signature scheme that
was a third round candidate in the NIST additional call for
post-quantum signatures. It has short signatures and keys, as
well as fast and portable signing and verification. However,
in response to a highly-publicized AI-driven cryptanalytic
result that reduced its security (roughly doubling the required
dimension to achieve a given security level), the authors de-
cided to withdraw from the competition. The need to increase
parameters was seen as limiting the size advantage of HAWK
compared to the already selected lattice schemes ML-DSA
and Falcon, which was one of its primary selling points along-
side speed and the lack of floating-point arithmetic.
In this paper, we identify another attractive aspect of the
HAWK design that is not affected by the AI attack and has
been overlooked so far: its surprising friendliness to multi-
party computation (MPC). Indeed, HAWK signing can be
achieved in a generic way from a small collection of basic
composable MPC functionalities (like integer multiplication,
uniform random generation, etc.) in such a way that instanti-
ating those functionalities using MPC protocols with given
security properties (semi-honest vs. malicious, honest vs. dis-
honest majority, etc.) yields a secure protocol for MPC signing
with those same properties.
As a result, we obtain Kettle, a UC-secure threshold signa-
ture protocol that outputs specification-compliant HAWK sig-
natures and scales to an arbitrary number of parties. It offers
essentially the shortest signature size so far for a lattice-based
threshold signature, while achieving significantly lower round
complexity and online communication cost than other thresh-
old protocols built from pre-existing, non-threshold lattice-
based signatures (like ML-DSA and Falcon): as low as 2
online rounds (a dozen rounds total) and 2 kB online com-
munication per party, depending on the specific setting and
optimization choices.
We also provide a proof-of-concept implementation of our
approach in the MP-SPDZ framework, which can be instanti-
ated with any number of parties, any threshold, and a variety
of security properties.
Trapdoor Projective Sampling and Identity-Based Anonymous Broadcast
In anonymous broadcast encryption, a ciphertext hides both the message and the set of recipients. In the general case, a lower bound of Kiayias and Samari forces the ciphertext to grow linearly with the number of recipients, a bound already met by the trivial per-recipient solution. The bounded universe is the setting where anonymous broadcast becomes concise, even asymptotically optimal and as efficient as the underlying public-key encryption. Far from a mere restriction, it is the building block for anamorphic communication against a dictator, where one must reach many (but boundedly many) recipients covertly, as put forth in the DPPY scheme at Eurocrypt '25. DPPY is, however, secret-key anamorphic encryption, where the broadcast layer itself must be hidden. Even a public-key variant does not suffice against a strong adversary, since a per-recipient public key lets a dictator ask for the matching secret key. This motivates hiding identities directly, with no recipient public key published, leading to identity-based anonymous broadcast in the bounded model, the focus of this paper.
Technically, projective sampling (Ling, Phan, Stehlé and Steinfeld, LPSS, CRYPTO ’14), the tool underlying concise anonymous broadcast encryption, offers no key extraction: private keys cannot be produced from a projected key fixed in advance. We introduce trapdoor projective sampling that reverses the order of key generation in projective sampling: projected keys are fixed first as hashes of identities and compatible private keys are then preimage-sampled with a trapdoor. Adding a trapdoor is always a challenging objective, and we achieve it by showing that the LPSS projection space can be made far narrower - from m×(m−n) down to m×2n - without breaking the k-LWE security argument, and it is exactly at this width that the projection matrix can be generated with a trapdoor. We formalise the notion of trapdoor projective sampling with new security requirements, instantiate it from k-LWE, and obtain an identity-based anonymous broadcast whose ciphertext is as in LPSS, DPPY schemes. We also extend it to an unbounded identity universe under static corruption, with target sets kept bounded and adaptive.
A unified toolkit for advanced arithmetic in FHE
We suggest an extension of discrete--CKKS that enables advanced computations over real, Boolean and large integers (e.g., 64/128-bit), including standard arithmetic operations, comparison, shift, bit length, quotient, square root, and other non linear functions based on binary representation. The flexibility of our approach lies in the synergy between the integer and the real arithmetic layers. At the core of our approach lies indeed a novel non-iterative binary decomposition technique extracting the $i$-th bit of $x$ by evaluating an approximation of $\lfloor x/2^i \rfloor \bmod 2$, very efficient when $x$ has at most 8 bits.
We show how such procedure can decompose not only a value $x$, but also a more general $g(x)$ at no additional cost by generalizing the evaluation to $\lfloor g(x)/2^i \rfloor$, enabling fast LUT evaluation over integers. Interestingly, the output of our LUTs can be arbitrarily large at the cost of requiring redundant slots: this unlocks the computation of large seeds for Newton--Raphson algorithms, enabling for the first time the practical evaluation of (exact) non linear functions over large integers such as square root and quotient within the discrete--CKKS family of schemes.
By supporting computations over different domains, our framework is usable in various applications: smart contracts naturally fit our framework, as it efficiently supports both arbitrary logical gates and operations over large integers. It also allows integer computations on the output class of a real-valued neural network, such as metadata lookup.
Compared to the state-of-the-art by Gao and Zheng (CRYPTO '26), our solution does not require ad-hoc encoding or expensive integer to Boolean conversions, making it more suitable when some non arithmetic structure is involved. %has lower latency on all standard integer operations (additions, multiplications, comparisons and logical shifts), and we additionally support nonlinear integer operations.
Our current limitation lies in the throughput, which is lower.
We additionally provide an open source proof of concept for GPU, showing that our work has better latency and throughput than TFHE-rs on most arithmetic and non-arithmetic operations.
The Power of Permutable PRPs: Towards Trapdoor Permutations with Full Key and Message Domains
Shmueli and Zhandry introduced permutable pseudorandom permutations (PRPs) and used them to construct trapdoor permutations with a full message domain but a sparse public-key space. We extend this approach to construct puncturable trapdoor permutations with full message and per-instance key domains in the common-reference-string (CRS) model. Our construction assumes a secure permutable PRP for general swaps, indistinguishability obfuscation, and an injective length-doubling pseudorandom generator, all secure against polynomial-time adversaries. Instantiating the underlying permutable PRP from indistinguishability obfuscation and one-way functions requires subexponential security.
A one-time setup produces a CRS and a master trapdoor. For every honestly generated CRS, every bit string of the prescribed key length indexes a permutation of the full message space, allowing uniform public-key sampling without validation or rejection. The master trapdoor derives an inversion trapdoor for every key. The family supports two-level puncturing: the master trapdoor can be punctured at a key, and an individual trapdoor can be punctured at an output. For a uniformly sampled challenge key and output, recovering the missing preimage remains hard even when both punctured trapdoors are revealed. To our knowledge, this is the first family combining these full-domain properties, master trapdoor derivation, and two-level punctured security.
We give three applications. In the random-oracle model, the family yields deterministic identity-based encryption with zero ciphertext expansion and adaptive weak-source pseudorandomness under a computational hardness condition on message sources. Security holds even given a key that decrypts every ciphertext except the challenge under the selected identity. The family also yields identity-based signatures with perfect uniqueness and adaptive unforgeability in the random-oracle model. Finally, puncturable trapdoors give a direct construction of hard-on-average End-of-Line instances, establishing PPAD hardness without passing through Sink-of-Verifiable-Line.
On the Concrete Hardness Gap Between MLWE and LWE
Concrete security estimates for Module LWE (MLWE) over an appropriate ring are often obtained by translating to an "equivalent" unstructured LWE instance, which implicitly treats algebraic structure as a pure efficiency gain with no impact on security. We show that this heuristic fails for realistic parameters. In common MLWE/RLWE instantiations, an attacker can exploit symmetries to obtain hybrid attacks that are strictly stronger than the best corresponding attack on LWE, translating to a concrete hardness gap between MLWE and LWE.
Our starting point is the observation that many cryptographically relevant rings admit coefficient isometries: ring elements whose multiplication acts as a signed permutation on coefficient vectors and preserves the secret and error distributions of interest. Multiplying an MLWE instance by such an isometry creates many derived instances that share the same public matrix and are therefore compatible with the same expensive offline preprocessing in hybrid attacks. We formalise this mechanism and incorporate it into both primal and dual hybrid frameworks.
We instantiate coefficient isometries for power-of-two cyclotomic rings, and quantify the resulting advantage in two regimes. For sparse-secret RLWE (popular in homomorphic encryption), isometry-enabled hybrids yield gaps of up to 14.2 bits over LWE-based estimates. For the standardised Kyber/ML-KEM parameters, we obtain an MLWE hardness reduction of around 1 bit due to the ring structure. Our results demonstrate that the widely assumed equivalence between LWE and MLWE in power-of-two cyclotomics does not hold, with real world consequences for deployed schemes.
Titan: Efficient Polynomial Commitments from IOPs over Groups
In this paper, we propose Titan, an efficient polynomial commitment scheme (PCS) with transparent setup. It achieves commitment time of $O(n)$, evaluation time of $O(\sqrt{n})$ while the proof size and verification scales as $O(\sqrt[4]{n})$. Titan features an order of magnitude smaller proof sizes than hash based PCS, while featuring a significantly more efficient prover and verifier compared to state of the art group based schemes like Dory and Hyrax. To achieve this balance, Titan borrows two-tiered commitments from Dory, and realizes outer commitment using interactive protocols of proximity (IOPP) over groups, such as Basefold and WHIR, instead of expensive bilinear pairings. This allows Titan to be instantiated over general curves with discrete-log hardness such as Pasta Curves, instead of requiring pairing friendly curves.
We compile a variant of Spartan protocol for R1CS with Titan PCS to realize a SNARK. Our SNARK construction preserves the prover efficiency of the existing Spartan protocol, while improving proof size and verification quadratically from $O(\sqrt{n})$ to $O(\sqrt[4]{n})$. Concretely, for circuits of size $\geq 2^{22}$ this results in around $3\times$ more efficient proof size and verification.
Our blueprint of combining IOPPs over groups with Pedersen style inner commitments is of independent interest, as are several optimizations towards efficiently realizing WHIR IOPP over prime-order groups.
BitZ: proofs and commitments in arbitrary rings through binary fields
We introduce BitZ, a hash-based Polynomial Commitment Scheme (PCS) for committing to multilinear polynomials $\mathbf{f}$ with coefficients in an arbitrary finitely generated ring $S$, e.g.\ a finite field $\mathbb{F}$, the integers $\mathbb{Z}$, a cyclotomic ring, etc. Moreover, given another arbitrary ring $R$ and a ring homomorphism $\psi:S\to R$, BitZ then proves evaluation claims over $R$ for the polynomial $\psi(\mathbf{f})$. BitZ's costs depend almost exclusively on the number of bits in the coefficients of $\mathbf{f}$, and not on $S$, $R$ or $\psi$. Moreover, BitZ provides range checks (or more generally, bit-size checks) essentially for free.
BitZ can thus be used as a PCS in essentially any proof system. We do so to build a SNARK, called BitZ-SNARK, for integer polynomial constraints, following the fingerprinting technique of Campanelli and Hall-Andersen, where one commits over $\mathbb{Z}$ and proves the constraints over a random prime field $\mathbb{F}_q$, i.e. BitZ is deployed with $S=\mathbb{Z}$, $R=\mathbb{F}_q$, and $\psi$ reduction modulo $q$. BitZ applies equally to other ring-based proof systems, or field-based ones.
To commit to $\mathbf{f}$, BitZ first decomposes $\mathbf{f}$ into a string of bits, and then commits to it over a binary field $\mathbb{F}_{2^{\nu}}$, in packed form. The scheme then proves the linear claim on $\psi(\mathbf{f})$ over the arbitrary ring $R$, even though it committed to the bits forming $\mathbf{f}$ over a binary field.
We implement BitZ-SNARK and use it to prove, among others, SHA-256 hashing followed by ECDSA signature verification; RSA modular exponentiation and Poseidon hashing; integer multiplication; and SHA-256 hashing followed by multiplication modulo $2^{32}$, consistently obtaining better performance than prior approaches on most tasks. As an example, we achieve a throughput of $9$ million proved 32-bit integer multiplications per second on a MacBook Air M5 24 GB (10 threads, CPU-only) with proof sizes under $200$ kB. We prove a SHA-256 hash of a $2$ kB ($2^5$ compressions) message followed by a P-256 ECDSA signature verification with $32$ ms and $3.1$ ms prover and verifier time, respectively, and with a proof of $65$ kB, single-threaded. With $10$ threads the times are $17$ ms and $3.7$ ms.
Rotate Once, Read Many Times: on the Output Noise of Multi-Value Bootstrapping
In FHEW/TFHE, a programmable bootstrap evaluates an arbitrary function of the encrypted
message, encoded as the \emph{test polynomial} of a blind rotation. We work in a
prime-power cyclotomic ring whose prime is the plaintext modulus $p$ (a
\emph{design choice} that leaves the ring degree free as a security parameter) and
compare the \emph{Single-Value Mode} (SVM), one rotation per function, with the
\emph{Multi-Value Mode} (MVM), one \emph{function-independent} rotation shared by all.
Factoring the test polynomial as $v^*_f = \mathfrak B^*_f\cdot \mathfrak w$, the function
carried by the dual module and the rotated factor by the torus, lets a single
hypothesis (a centered accumulator error of \emph{arbitrary} covariance $G$) cover
both modes: the two variances are values of one $G$-form, and their ratio is the exact
amplification.
The $f$-independent factorizations are then parametrized by a non-zero ring element, the
cofactor, and by the integer lift of the table: at a random lift the cofactor is chosen
by a shortest-vector problem for an explicit quadratic form, then the lift by a
closest-vector problem of rank $p-1$. In the
spherical model that form is a trace norm and two designs compete: the canonical
cofactor, of noise cost $p(p+1)/6$, and the pivot, which reads the
integer table itself at noise cost $2p$, at a random lift; the optimized lift then favours
the canonical cofactor on the generic tables. Under the other natural covariance, the block
Laplacian, it is optimal for every $p$. Both cofactors are measured, in the key-noise regime, on a complete implementation, publicly available.
Enhancing One-Way to Hiding Theorems with Amplitude Amplification
The one-way to hiding (O2H) theorem and its variants, which bound the distinguishing advantage in terms of the one-way advantage, are widely used in security proofs in the quantum random oracle model (QROM), particularly for key encapsulation mechanisms (KEMs). However, existing O2H bounds typically incur a security loss depending on the adversary's oracle query depth $d$ (i.e. the number of sequential layers of parallel queries), which can make both computational and information-theoretic bounds in KEM security proofs less tight.
In this work, we establish a generic amplitude-amplification-based technique to many O2H variants to remove their depth-dependent factors by these theorems in the advantage bounds.This covers the Semi-Classical O2H (SC-O2H) [Ambainis et al., CRYPTO 2019] and Measure-Rewind-Extract O2H (MRE-O2H) [Ge et al., ASIACRYPT 2024] theorems, in which the constructed one-way adversaries have access to an indicator oracle $\mathbf{1}_S$ that checks whether the input is a valid solution to the one-way game.
We identify conditions under which our enhanced O2H theorems can replace the original O2H theorems in existing security proofs. These conditions hold for a range of security proofs, including IND-CCA security proofs for KEMs obtained from variants of the U transformation in the Fujisaki-Okamoto (FO) framework. Applying our enhanced theorems in these proofs yields the following improvements in the depth dependence of security bounds:
- When the one-way advantage is bounded information-theoretically, our technique eliminates the depth-dependent factors with only a constant-factor loss in the security bound.
- When the one-way advantage is bounded by computational hardness assumptions, our technique eliminates the depth-dependent factors $d$ for SC-O2H and $\sqrt{d}$ for MRE-O2H, at the cost of increasing the constructed one-way adversary's running time by a factor that is only of the order of the square roots of the eliminated losses, namely $O(\sqrt{d})$ for SC-O2H and $O(\sqrt[4]{d})$ for MRE-O2H.
What Makes Lattice Key Generation Expensive? Controlled Cost Attribution with Structured LWR, ML-KEM, and HAETAE on Cortex-M4
End-to-end cycle counts quantify lattice key-generation time on a microcontroller, but not which implementation decisions create that cost. We develop a controlled attribution method for public structure, candidate admission, and transform lifetime: how public data are organised, when candidate acceptance is checked, and whether transformed secret state is retained or reconstructed. On a fixed STM32L476RG Cortex-M4 target, paired runs within one executable keep the relevant secret, accepted candidate, or output key unchanged; separate measurements record resource effects. In our Bos-based structured-LWR implementation, reorganising public data exposes expansion and multiplication cost, and same-key, first-attempt comparisons show nearly additive admission and lifetime effects. We then test whether these explanations transfer across algorithms and rejection structures. In ML-KEM-512, whose KeyGen has no candidate rejection, retaining the secret's NTT-domain representation reduces cycles; a pre-specified ML-KEM-768 test preserves this direction but shows that the saving does not scale with module rank alone. HAETAE-5 tests both decisions inside a retrying KeyGen. Early checking stops rejected candidates before matrix computation, whereas deferred checking repeats matrix work across attempts and, under recomputation, rebuilds transformed secret state. The interaction grows with the retry count, while retention saves cycles at the cost of a larger KeyGen frame. Together, these experiments establish a compositional account of KeyGen cost: public structure defines the downstream computation for each candidate, while candidate admission and transform lifetime determine how many candidates execute it and how often reusable transformed representations are rebuilt. These relations yield directional predictions across the tested KeyGen structures, with paired measurements quantifying their cycle and storage consequences.
Automorphism-Compatible NTT and its Application to Homomorphic Encryption
For $N$ a power of $2$, the negacyclic number-theoretic transform (NTT) maps a degree $N-1$ polynomial to its evaluations at the $N$ primitive $2N$th roots of unity.
In-place butterfly algorithms such as Cooley-Tukey and Gentleman-Sande compute
the negacyclic NTT in $O(N\log N)$ time and output the evaluations in a specific, standard order. We give in-place butterfly algorithms for the negacyclic NTT and its inverse that instead output the evaluations in an automorphism-compatible order. These algorithms have the same structure as Cooley-Tukey and Gentleman-Sande,
differing only in their precomputed twiddle factors. Our automorphism-compatible butterfly algorithms are applicable to the packed fully homomorphic encryption (FHE) schemes CKKS and BGV/BFV, where the negacyclic NTT is a major component of ciphertext arithmetic. Using our automorphism-compatible butterfly algorithms, Galois automorphisms can be applied to ciphertexts stored in double-CRT format via a simple cyclic shift or adjacent-pair swap of the data. This is contrast to butterfly algorithms currently used that output in the standard order, where applying an automorphism requires performing an arbitrary-looking permutation of the stored data. Our automorphism-compatible butterfly algorithms remove the need for a dedicated automorphism functional unit used in FHE hardware accelerators.
The Humbert Form of Discriminant 36, and What It Says About Splitting Detection
Explicit equations for the locus $\mathcal{L}_n$ of genus-two curves with a maximal degree-$n$
elliptic subcover have been computed only for $n \le 5$, and by elimination, whose cost is
not predictable in advance. The degree formula of [22] changes this. It gives
$\deg_w F_n = k(H_{n^2}) - 10\,\nu(n)$ in closed form, and with it a reduced monomial support
for the associated Humbert modular form $G_{n^2}$, so that the reconstruction becomes a
determined linear problem whose every dimension is known before any computation begins.
We carry this out for the first new case it opens, discriminant $36$: we determine
$k(H_{36}) = 720$, $\nu(6) = 12$, $\deg_w F_6 = 600$ and an admissible modular basis of size
$41962$, and we compute the four Siegel generators explicitly along Kumar's rational
parametrisation of $H_{36}$, obtaining in particular a complete factorisation of $\chi_{10}$
whose factors recover the degenerate loci of the family from the modular side. We then draw
the consequences for isogeny-based cryptography. The equation $\overline{F}_n$ decides
optimal $(n,n)$-splitting at every point of the moduli space in characteristic $p$, with no
hypothesis on the Newton polygon; this is asserted but not proved in the cryptographic
literature, and the available proof excluded exactly the superspecial locus where the
question is asked. The weight $k(H_{n^2})$ bounds, unconditionally and with explicit
constants, the number of superspecial nodes that detection at level $n$ adds to the target
set of the best known attack in dimension two. And the same torsion count $\nu(n)$ that
appears in the degree formula governs the cost of both known detection routes, which places
a barrier on raising the level and singles out $n = 6$ as the one case where a new equation
can matter in practice.
It Takes Two: Proofs of Work for Fiat–Shamir
In the random oracle model (ROM), proof of work (PoW) serves two roles in the Fiat–Shamir transformation. First, in challenge grinding, the prover must solve a puzzle for each candidate challenge, which amplifies soundness and reduces proof size and verifier time. This requires a non-amortizing PoW: computing $k$ distinct accepted puzzle–solution–proof triples costs, in expectation, roughly $k$ times the work of computing one. Second, PoW can prevent diagonalization attacks, in which the statement's circuit computes its own challenge. The XFS transformation of Arnon and Yogev (CRYPTO 2025) uses a strong PoW: an adversary that does substantially less work than the honest prover solves a random puzzle with only negligible probability, even after bounded preprocessing.
Can a single PoW be both strong and non-amortizing? We prove that it cannot, whenever the verifier is sufficiently cheaper than the prover. Our main technical tool converts computational uniqueness into statistical uniqueness without increasing verifier query complexity. Combined with the search bound of Guan, Riazanov, and Yuan (CRYPTO 2025), which builds on Smyth (STOC 2002), it resolves their open question.
To overcome this barrier, our XFS-with-grinding transformation for relativized $\Sigma$-protocols composes a strong PoW with a non-amortizing one. The resulting non-interactive argument retains the soundness amplification of grinding and the security guarantee of XFS in the relativized ROM, with additive prover work for the two PoWs.
On the hull attacks against Construction A lattices
In this paper, we present an algorithm for solving the Lattice Isomorphism Problem between input lattices that are isometric to the Construction A lattice of a certain code C. Our algorithm is a direct extension of a method due to Ducas and Gibbons (PKC 2023). We prove that the run time of our algorithm is $2^{O(n)}$ and that its success probability is $1+o(1)$ over a random choice of C. Crucially, our method works when the hull of C has arbitrary dimension while the method of Ducas and Gibbons is restricted to the case of a trivial hull.
Indistinguishability Lifting for Keyed Oracles, Compressed Ideal Cipher, and More Applications
Cryptographic security proofs often involve an adversary interacting with a larger, keyed oracle that consists of (potentially exponentially) many independent instances of a smaller, base oracle. Examples include ideal ciphers, which provide access to an independent random permutation for each key, and random oracles, which provide an independent random bit string for each input. However, showing quantum indistinguishability between two such keyed oracles can be tricky, since a single query made by an adversary may involve a superposition that covers all instances of the base oracles simultaneously.
In this paper, we establish a generic indistinguishability lifting theorem of the following form: if the two base oracles are indistinguishable under quantum queries, then their corresponding keyed oracles are too, up to an O(q^2) multiplicative loss in distinguishing advantage, where q is the number of queries made by the adversary. Our lifting theorem applies to both statistical and computational settings, and to oracles that are stateful as well. It is also optimal in that it matches the obvious Grover search attack for a certain (contrived) choice of oracles.
As an immediate application, we extend Carolan's compressed permutation oracle to an efficiently implementable compressed ideal cipher, and use it to prove preimage resistance of the Davies-Meyer compression function in the quantum ideal cipher model. Thanks to our lifting theorem, the soundness of our compressed ideal cipher reduces to that of Carolan's oracle, and any further improvement on the latter would automatically carry over to the former.
As our second application, we give a modular construction that doubles the message length of any quantum-secure strong pseudorandom permutation. Along the way, we show that an existing two-round tweakable Feistel construction is indistinguishable from a random permutation under quantum bidirectional queries. This is done via a dedicated polynomial-method argument, which may be of independent interest.
Comparing Privacy-Preserving Revocation for the EUDI Wallet
The European Digital Identity Wallet has integrated anonymous credentials into its technical specifications, and singles out four constructions for privacy-preserving revocation, drawn from two families: positive dynamic accumulators and signed-pairs. The two families are described in the literature in substantially different terms, and no common basis for comparing them exists, which currently prevents informed and quantitative decision making. In this work, we give a unified treatment of both families, showing that signed-pairs, despite their very different presentation, can be expressed in the standard accumulator syntax. We use this to define a single revocation mechanism that any of the four constructions instantiates, which in turn allows us to compare the resulting mechanisms both at the protocol level and empirically. We measure the performance of all four across the full revocation lifecycle, on server-class hardware for the Status Manager and on a smartphone for the Holder and Verifier, with parameters taken from a live national eID scheme. No construction dominates in every aspect, and we make the resulting trade-offs explicit, showing which construction suits which deployment, and identify promising avenues for further improvement at the protocol level.
Fixed-Budget Allocation in Neural Differential Distinguishers
Neural differential distinguishers are usually compared at a fixed number of
labeled samples. However, different input representations may require different
numbers of ciphertexts per sample, making fixed-sample comparisons potentially
misleading from a cryptanalytic data-complexity perspective. In this paper, we
study neural differential distinguishers under a fixed ciphertext budget. We ask
whether the available encryption queries should be spent on more independent
plaintext bases, or on richer samples containing more ciphertext-difference
rows.
We introduce a shared-base multi-difference representation in which several
input differences are applied around the same plaintext base, and compare it
with the standard single-difference baseline and an independent-pair control
representation. Experiments on GIFT-64, PRESENT-64, RECTANGLE-64, and
SPECK-64/128 show that the single-difference baseline is rarely the best
fixed-budget allocation. Adding more difference rows often improves the
distinguisher even though it reduces the number of independent training samples.
At the same time, the best tested number of rows is not universal: logistic
regression often benefits from larger representations, while a multilayer
perceptron frequently prefers intermediate values due to sample-starvation and
overfitting.
We further test several non-adaptive difference sets and observe that the main
trend is not tied to a single hand-picked set. The results suggest that the
number of differences per sample should be treated as an explicit design
parameter in neural differential cryptanalysis, and that fixed-budget evaluation
is necessary for comparing richer neural distinguisher inputs fairly.
ATLAS: A Compact Module-LWR Signature Scheme
We present $\mathsf{ATLAS}$, a lattice-based digital signature scheme built on the Fiat--Shamir with aborts paradigm, with security based on the hardness of the Module Learning with Rounding ($\mathsf{MLWR}$) problem. Unlike $\mathsf{Dilithium}$'s $\mathbf{t} = \mathbf{As}_1 + \mathbf{s}_2$ construction or $\mathsf{HAETAE}$'s bimodal, hyperball-uniform instantiation, $\mathsf{ATLAS}$ derives its public key via deterministic rounding, $\mathbf{t} = \lfloor \tfrac{p}{q}\mathbf{As}_1 \rceil$, eliminating the error term $\mathbf{s}_2$ and the explicit noise sampling it requires. This reduces key-generation cost and secret-key storage, and removes a component that both $\mathsf{Dilithium}$ and $\mathsf{HAETAE}$ would otherwise need to support, while keeping $\mathsf{ATLAS}$ structurally close to $\mathsf{Dilithium}$ to inherit its well-studied design and cryptanalytic track record.
$\mathsf{ATLAS}$ targets three classical security levels, 128, 256, and 512 bits, using the smallest feasible ring degree $n$ and challenge weight $\kappa$ for each, with module dimensions $(k,l)$ tuned per level. To our knowledge, this includes the first \mlwr-based signature parameter set at the 512-bit level. $\mathsf{ATLAS}$ further adopts power-of-two moduli (e.g., $q=2^{23}$, $p=2^{18}$), replacing modular reduction with bitwise operations and removing rejection sampling from key parts of the scheme. Since such moduli preclude conventional NTT-based multiplication, we design a hierarchical Toom-Cook/Karatsuba decomposition with degree-8 schoolbook multiplication as its base case, accelerated via AVX2 vectorization and strided memory access. Finally, $\mathsf{ATLAS}$ supports both $\mathsf{SHAKE}$ and $\mathsf{KDF-SM3}$ as interchangeable symmetric back-ends, and we quantify the overhead of the $\mathsf{SM3}$-based instantiation relative to $\mathsf{SHAKE}$.
Understanding Sigma Protocols via MPC-in-the-Head
In this paper, we propose an understanding of classical Sigma protocols (as denoted by $\Sigma$-protocols in the literature) through the lens of the MPC-in-the-head (MPCitH) paradigm. We seek not to construct new schemes, but to build a formal bridge connecting these two foundational areas. While many elegant yet foundational Sigma-protocols were introduced decades ago as standalone algebraic or combinatorial interactive proofs, reconsidering them via the modern aspect of (extended) MPCitH significantly enhances our cryptographic insight into their underlying structures.
We present a formal mapping that translates classical commitment-challenge-and-response into the internal views of virtual parties, communicating via private point-to-point or public broadcast channels, secret-sharing schemes, commitments, and MPC consistency/correctness checks. By deconstructing algebraic schemes as linear secret-sharing protocols over public channels and combinatorial schemes as discrete threshold MPC instances over private/public channels, we isolate the exact structural reasons why their soundness and efficiency characteristics diverge. The protocols include:
- Algebraic schemes: Schnorr, Okamoto, Chaum-Pedersen, Guillou-Quisquater, GMR for QR and discrete log over an unknown-order group.
- Combinatorial schemes:
Stern, GMW for Graph 3-Coloring, and Graph Isomorphism, among others.
Although reinterpreting these already elegant, classic proofs using a heavy-weight machinery like MPCitH might seem redundant, it deepens our understanding of their underlying design principles.
SCORE: A SlotToCoeff Optimization for Real-Vector Encryption in CKKS
We present SCORE, a tweaked version of the SlotToCoeff operation tailored to the context of encrypted real vectors in the CKKS scheme, where SCORE stands for “SlotToCoeff Optimization for Real-Vector Encryption”. This approach accelerates CKKS bootstrapping algorithms that employ the SlotToCoeff operation as their final step, provided the inputs are encryptions of real vectors. SCORE constitutes a conceptually simple refinement of the conventional SlotToCoeff step that can be seamlessly incorporated into existing bootstrapping algorithms. Despite its minimal nature, the technique yields tangible performance improvements. We demonstrate its utility through proof-of-concept implementations for two such algorithms: the conventional bootstrapping algorithm and the SPRU algorithm, which is particularly efficient for ciphertexts containing a small number of encrypted slots. Our results indicate notable performance gains of up to $2\times$ compared to the original formulations of the algorithms.
Mechanized Proofs of ORAM Correctness, Security, and Failure Bounds
ORAM is a fundamental cryptographic technique that permits outsourcing memory storage while probabilistically hiding memory access patterns of client programs.
We use the EasyCrypt proof assistant to obtain fully mechanized proofs of correctness and security of Simple ORAM [Chung and Pass, 2013] and Path ORAM [Stefanov et al., CCS 2013].
To the best of our knowledge, these are the first machine-checked proofs that cover the correctness bound, i.e., the failure probability, of an ORAM construction.
Our proofs refine, simplify, clarify and slightly improve the paper proofs, and many parts of our development can be reused to obtain similar results for other ORAM constructions.
As a final contribution, we provide a general library that handles the recursive composition of ORAM constructions to reduce storage demands on the client, and apply this to Path ORAM to capture a practically-relevant instantiation.
Automated Search for Periodic Functions in Quantum Attacks: Distinguishers and Key-Recovery Attacks
Quantum attacks based on Simon's algorithm rely on Boolean functions with hidden XOR periods. At ASIACRYPT 2025, Liu et al. introduced a symbolic automated search model for periodic functions used in distinguishers. However, for distinguishers on target ciphers, the search mainly works with truncated differences and does not jointly constrain exact differential propagation. A separate modeling gap arises in the key-recovery setting: the model does not cover the key-dependent periodic functions used in the polynomial-time key-recovery attacks presented by Canale et al. at CRYPTO 2022. In this work, we study automated search for two classes of periodic functions: periodic functions for distinguishers and key-dependent periodic functions for polynomial-time key-recovery attacks. For the former, we refine the symbolic search model of Liu et al. by adding fixed input differences, differential propagation, and probability constraints. Based on this model, we extend the periodic distinguishers of TWINE and LBlock from 10 rounds to 12 rounds, obtain a 12-round periodic distinguisher for LBlock-S, and find a full-round periodic distinguisher for ALLPC with verified probability \(2^{-9.06}\). For key recovery, we adapt the symbolic-state tracking used for distinguishers to key-dependent values. The model tracks key-dependent shifts and checks that the periodic core is exposed through an output-computable expression. With this model, we extend the attack on MISTY L-FK from 5 to 6 rounds and obtain new polynomial-time key-recovery attacks on Type-1/2 GFS and Skipjack-B variants with FK or KF round functions.
SPIN: Fast Codes for Correlation Generation and Polynomial Commitments
Binary codes used in correlation generation and proof systems need strong distance, fast ordinary and transposed encoding, and regular memory access. We introduce Single-Permutation INterleaved (SPIN) codes, combining a blockwise outer encoder, one global interleaver, and a recursive inner.
Our main result is a Structured SPIN family with rate $1/2$ and $O(N)$ bit operations for ordinary and transposed encoding at its native output lengths $N$. With probability $1-o(1)$ over the random choice of the code, its minimum distance exceeds $0.11N$. The proof combines outer spectrum bounds with an analysis of structured support spreading and recursive state mixing. We formally verify these distance and rate guarantees in Lean.
For finite lengths, a BCH-derived outer constituent and a fixed recursive inner give rate $1/2$ and relative distance greater than $0.10$, with setup-failure probability below $2^{-40}$. We certify this bound at message lengths $2^{16}$, $2^{18}$, $2^{20}$, $2^{22}$, and $2^{24}$ using rigorous spectrum inequalities, without assuming the constituent's exact weight spectrum.
For pseudorandom correlation generators (PCGs), SPIN's transposed encoder computes $2^{20}$ $128$-bit correlation blocks in about $9.3$\,ms on one Ryzen 9 7950X thread after precomputation. This is approximately $3.4\times$ faster than the original rate-$1/2$ BAA codes of Kolesnikov et al.\ (CRYPTO 2026). Ordinary encoding has similar cost.
With a precomputed code, libOTe's regular-noise Silent OT sender achieves $89.0$ million hashed OTs per second on one core, in batches of $2^{18}$. Timings exclude initial setup, base-correlation generation, and network transport.
We also use SPIN in a Brakedown-style polynomial commitment scheme and integrate it into Flock. Commitment and one opening of $512$\,MiB take $509$\,ms on one core, with a 100-bit interactive fixed-matrix testing target; this excludes code-setup failure, extraction, and Fiat-shamir reductions. Within an optimized Flock implementation, replacing Ligerito with SPIN--Brakedown improves prover throughput by $1.63$--$2.29\times$ at the measured workloads, with larger proofs and slower verification. The comparison gives both backends the applicable shared implementation optimizations.
Fast Linear Codes over Large Fields: Addition-Only and Small-Coefficient Encoders
We construct fast linear codes over large fields using addition-only encoders and variants with small integer coefficients. A local precode is followed by rounds of a random permutation and a scan, a linear recurrence with a short feedback window. At dimension $2^{20}$, rate $1/2$, and $p=2^{128}-159$, two plain accumulators (unweighted prefix sums) give relative distance above $11.7\%$, except with probability below $2^{-49.64}$ over the sampling of the encoder. A binary subset-sum precode instead gives distance above $12.56\%$, except with probability below $2^{-22.05}$. These addition-only encoders use fewer than $6.8125n$ and $3.3125n$ field additions, respectively, for output length $n$. Both exceed the binary rate-$1/2$ Gilbert--Varshamov benchmark. The proof counts the supports and ranks of the zero equations a codeword must satisfy, retaining the dependence between cancellations.
Coefficient size and scan width extend the tradeoff. On one core, with a common implementation and setup failure below $2^{-40}$, encoding time ranges from $12.171$ ms at proved distance above $11.7\%$ to $32.342$ ms above $42.987\%$. A coefficient-independent upper bound limits every encoder with two width-one scans after the Newton precode to $39.6855\%$.
The distance and setup-failure bounds hold over $\mathbb F_p$ and every finite extension, covering all nonzero messages after setup. Timings are for $\mathbb F_p$. Extension preserves distance exactly because the encoder coefficients lie in the prime subfield. Changing characteristic requires a separate argument; we give field-transfer results in both directions, including counterexamples.
Expander-Based Codes at the Gilbert–Varshamov Bound
We prove that Expand--Accumulate (EA) codes approach the Gilbert--Varshamov (GV) distance as the code length grows. The result holds over the binary field and every fixed finite field. At fixed rate, encoding uses $O(n\log n)$ expected field operations, with a tunable inverse-polynomial probability of sampling a bad code. Fixed-memory wrapped binary Expand--Convolute (EC) codes satisfy the same guarantee. Allowing $O(n\log^2 n)$ expected field operations makes sampling failure negligible in the code length.
These codes combine a sparse random linear map with an invertible recursive map. Our analysis uses exact input--output weight enumerators in place of the earlier concentration bounds. It also gives tighter constants in the logarithmic expected degree. For EA-based pseudorandom correlation functions, these bounds improve the degree--distance tradeoff that controls local evaluation cost.
Separately, we obtain finite-length bounds at small degrees by replacing independent incidence with regional regularity. At rate one half, a two-sided regular EC ensemble with left/right degrees $10/5$ and memory $15$ reaches $99.99\%$ of the binary GV distance. The probability of sampling a generator below this distance is less than $2^{-32.49}$.
We extend the construction to finite fields using independent nonzero edge labels and full-field convolution coefficients. These coefficients mix field components; scalar extension of a binary matrix does not. Over $\F_{2^{128}}$, degrees $24/12$ with memory $5$ reach $98.41\%$ of the rate-one-half GV distance with sampling failure below $2^{-45.03}$; degrees $26/13$ with memory $4$ reach the same distance with failure below $2^{-135.20}$. Every finite claim is certified with outward-rounded interval arithmetic. The results concern minimum distance of sampled ensembles; they do not provide a decoder or a complete protocol-security proof.
Fully Distributed Multi-Point Functions for PCGs and Beyond
We give fully distributed multi-point function (DMPF) constructions that
share a sparse map over a domain of size $N$. Setup takes secret-shared indices; each later expansion takes new payloads for those indices and returns shares of the map. Our main construction, Waterfall Cuckoo, samples public hashes before assigning the inputs to bins. An occupancy scan followed by bounded repair finds the assignment; a hidden permutation conceals it during routing. Sparse DPFs then provide $4N$ or $3N$ leaf work per expansion, replacing the $tN$ work of $t$ independent DPFs. We prove correctness and semi-honest simulation in the ideal-subprotocol model, with an explicit routing-error bound.
For the random sparse supports in Ring-LPN PCGs, we also give Reverse Cuckoo, a $2N$-expansion specialization. It programs hashes around a hidden placement and leaks information about the support: in the ideal hash model, outputs are weighted by their number of valid placements. We characterize the idealized leakage, state the additional decisional Ring-LPN assumption, and evaluate leakage-aware decoding attacks. A separate analysis bounds the concrete hash evaluator's batch correctness error below $2^{-40}$ at ring degree $2^{20}$ with the support-rejection filter specified in the analysis.
Our measurements use a variant of this specialized Reverse-Cuckoo pipeline without support rejection or AES rekeying, and with different mask, permutation, and evaluator-seed sampling rules. At degree $2^{20}$ it produces 1.81 million Goldilocks-field OLEs per second, with 12.99 MB communicated per expansion. Against the reported FHE baseline at the same field and degree, these figures give $6.57\times$ higher throughput and $13.60\times$ lower expansion communication. Setup costs and comparisons with the sum-of-DPFs baseline are reported separately. Waterfall's costs are modeled; gains for other fields, rings, and PCG constructions remain application-dependent.
An Input-Fed AES-Round Family for Fixed-Length Hashing
Secure computation often hashes high-entropy fixed-length values in inner loops. A public permutation with terminal Davies--Meyer feed-forward can expose the permutation value when an application applies another feed-forward step. We study an input-fed alternative that injects the input after every AES round.
The base construction, $H_{128}:\{0,1\}^{128}\to\{0,1\}^{128}$, uses ten full AESENC-style rounds with keys $x+c_i$ and no AES key expansion. Its concrete analysis adapts differential, collision, linear, integral, and meet-in-he-middle (MITM) methods to this shared-input round-key interface. We prove a three-round integral distinguisher and give a five-round anchored MITM attack candidate with estimated time $2^{120}$; the remaining results provide reduced-round evidence rather than a proof of random-function behavior. On an AMD Ryzen 9 7950X, measured scalar and eight-lane AES-NI costs are within one percent of fixed-key AES-128; a sixteen-block VAES kernel is 2.3\% slower.
Two extensions use the same input-fed principle. The tweakable construction $H_{128}^{\mathsf{tw}}$ splits a 72-bit public counter into an eight-bit tweak and a 64-bit epoch. One public schedule serves 256 consecutive positions, and consecutive fixed-key AES outputs under a published key supply the epoch schedules. Within one epoch, a pair with different tweaks can cancel at most one complete boundary injection. The construction also admits an exact 256-query two-round integral distinguisher. The wide construction $H_{256}$ maps 256 bits to 256 bits. It uses two AES lanes and adopts the column permutation and round constants of Haraka-256 v2 [KLMR16]. We analyze the differential, integral, collision, slide, rebound, and MITM mechanisms introduced by these extensions.
A supporting ideal-permutation analysis shows that affine wrappers with one or two permutation calls fail generically. For three calls with independently uniform public constants, it gives a birthday-order bound when the distinguisher completes its primitive queries before querying the target. Finally, we define checkable punctured vectors and prove a GM-style protocol secure against static semi-honest corruptions in the ideal-OT and random-oracle model.
Jolt-QED: Formally Verifying Bytecode Expansions In Lean
In this work, we verify, using the Lean 4 proof assistant, that the Jolt zk-VM's expanded programs faithfully emulate a RISC-V CPU. Prior work translated the official Sail specification of RISC-V into Lean. We extend this model to define the Jolt ISA in Lean. We build a generator that runs Jolt's Rust bytecode expander and renders its output as Lean programs. Finally, for 51 out of 58 such programs, we prove these expansions are equivalent to their corresponding RISC-V instructions. This lays the groundwork for proving completeness and soundness of further stages of Jolt's proving pipeline.
When Masking Preimage Computation Isn’t Enough: A Power Analysis Attack on Masked Implementations of Falcon
In this paper, we present a novel power analysis attack targeting a Falcon implementation protected by a masked preimage computation. By analyzing the ratio between the real and imaginary parts of the public hash polynomial, we demonstrate that the leakage during the share recombination phase can be exploited to recover the secret key. We propose two attack variants: a chosen-message attack, where the adversary controls input messages to force extreme coefficient ratios, and a non-chosen-message attack that filters for naturally occurring vulnerable hashes. Through experimental evaluations using the ELMO leakage simulator for an ARM Cortex-M0 architecture, our experiments achieve a 98.3% success rate with 4,000 traces. Finally, while a fully masked implementation of Falcon prevents our attack, we propose a practical countermeasure based on rejection sampling to avoid the prohibitive computational overhead of a fully masked Gaussian sampler.
Batched and Packed (Publicly) Verifiable Secret Sharing: A Unified Framework and Applications
Verifiable Secret Sharing (VSS) allows a dealer to distribute a secret among $n$ parties so that each can verify their share's validity, and any qualified subset can reconstruct the secret. Publicly Verifiable Secret Sharing (PVSS) extends VSS by enabling anyone to verify the correctness of distributed shares. Both VSS and PVSS schemes are core building blocks in many cryptographic applications. We introduce a $k$-batched and $l$-packed extension of $\Pi$, a unified framework from PKC 2025 for Shamir-based computational VSS in the synchronous setting with optimal resilience. Our framework enables the sharing and verification of $l\times k$ secrets in a single protocol execution, offering a tunable trade-off between efficiency and robustness: the $k$-batched, non-packed variant ($l=1$) improves performance while maintaining optimal resilience, whereas the $k$-batched, $l$-packed variant achieves even greater efficiency at the cost of slightly reduced fault tolerance. Using this framework, we construct several Batched and Packed (BP) VSS and PVSS schemes that significantly reduce both computational and communication costs for the dealer and parties. When sharing many secrets, two of our VSS schemes and our PVSS scheme perform almost as efficiently as plain Shamir sharing. For example, when sharing more than 100 secrets, the overhead of our hash-based BP-VSS is below 3%, for our BP-VSS with information-theoretic privacy it remains around 8%, and for our BP-PVSS it is under 1%. These results show that verifiability in Shamir secret sharing can be achieved in post-quantum and large-scale settings with negligible overhead for the dealer. Our proposed BP-PVSS scheme is the first that can achieve these properties and outperforms existing state-of-the-art protocols. We discuss several applications and, as a concrete case study, use our BP-PVSS scheme to revisit the ALBATROSS randomness generation protocol from ASIACRYPT 2020, yielding a more efficient variant.
Breaking the $n^2$ Barrier: Information-Theoretic MPC with Sub-Quadratic Communication
Secure multi-party computation (MPC) considers the problem of securely computing a function across $n$ parties such that no adversary controlling $t$ corrupted parties may learn any additional information beyond the function output. For information-theoretic security in the honest majority setting, recent works have made tremendous progress in reducing the MPC communication costs for large circuits obtaining as low as $\tilde{O}(|C|)$ total communication. To date, all information-theoretic MPC protocols require an additive $\tilde{\Omega}(n^2)$ communication independent of the circuit size that becomes the dominant cost for small circuits.
In this work, we consider the problem of building more efficient information-theoretic MPC protocols with $o(n^2)$ communication for small circuits. For corruption threshold $t< (1/2-\epsilon)\cdot n$, we present an information-theoretic MPC protocol secure against adaptive and malicious adversaries with subquadratic communication for a wide range of circuits, including those in which the number of input parties $I$ satisfies $|I| = o(n)$, circuit size $|C| = o(n^{1.5}/|I|)$, and circuit depth $\mathsf{depth}(C) = o(n)$; for example, $|C| = o(n^{3/4})$ and $|I| = o(n^{3/4})$ input parties. To our knowledge, this is the first information-theoretic MPC protocol with $o(n^2)$ communication for a wide-range of circuit classes. Furthermore, we note the requirement of sublinear input parties $|I| = o(n)$ is necessary to obtain $o(n^2)$ communication due to the $\Omega(|I| \cdot n)$ lower bound by Damgård {\em et al.} [EUROCRYPT'16]. To obtain our new MPC protocol, we develop new techniques for key MPC subroutines including randomness generation, player virtualization and output reconstruction with $o(n^2)$ communication leveraging the sublinear number of input parties, $|I| = o(n)$, and randomized output distribution with unpredictable communication patterns.
Finally, we also prove a separation showing that $o(n^2)$ communication MPC is impossible for adversaries with stronger than standard adaptive rushing capabilities even for constant-size circuits.
Low-Noise Multi-Value Bootstrapping via Log-Unit Lattice Search and LUT Shifting
Programmable bootstrapping is a central procedure in the FHEW and TFHE families of fully homomorphic encryption schemes, but its computational cost remains a major performance bottleneck. Multi-value bootstrapping amortizes this cost by sharing a blind rotation among several functions evaluated on the same encrypted input. However, the standard choice of common factor for multi-value bootstrapping can produce unnecessarily large noise amplification for many collections of lookup tables, thereby reducing the practical benefits of sharing the blind rotation. The main contribution of this work is a log-unit lattice search for selecting common factors that substantially reduce this amplification. This search is complemented with LUT shifting, which generates alternative function-preserving test-polynomial representations and further enlarges the search space. Both optimizations are performed offline and leave the online procedure of multi-value bootstrapping essentially unchanged. The proposed construction is evaluated in TFHE at failure probability $2^{-128}$. For example, on 256-bit homomorphic integer multiplication, it achieves a latency speed-up of $1.47\times$ and a throughput improvement of $1.59\times$ relative to a baseline that evaluates each output with a separate programmable bootstrapping.
Three-Move Blind Signatures from DL
This paper considers the problem of building blind signatures in pairing-free groups. We provide the first three-move blind signature which is provably one-more unforgeable, in the random-oracle model, under the minimal assumption that the discrete logarithm (DL) problem is hard. Our construction in fact achieves one-more strong unforgeability, and also supports partial blindness. Blindness is statistical, also in the ROM. Our construction makes black-box use of the underlying group and does not rely on non-black-box techniques. For most such constructions, three moves are necessary by a recent result of Dietz, Kastner, and Tessaro (CRYPTO '26).
We build on recent work by Chairattana-Apirom, Reichle, and Tessaro (CRYPTO '26), which achieved the same combination of round complexity and security guarantees, but under the stronger decisional Diffie--Hellman (DDH) assumption. In particular, we follow the same paradigm of boosting the security of a weakly secure scheme (namely, the Okamoto--Schnorr blind signature) to a fully secure one by authenticating the initial nonce. We provide, however, a substantially different instantiation of this paradigm that dispenses with the use of DDH and establishes security from DL alone.