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

Last updated:  2026-11-08
The Closest Vector Problem on Gadget Lattices: Efficient Algorithms and Voronoi Geometry
Daniele Micciancio
Gadget lattices are a prominent family of lattices widely used in lattice-based cryptography, error-correcting codes, and computational complexity. We present efficient algorithms for the Closest Vector Problem (CVP) on power and CRT gadget lattices and their duals, handling arbitrary real-valued target vectors. For the parity-check power gadget lattice, we give a practical, deterministic O(n) linear-time exact CVP solver based on a new, specialized "deferred greedy" graph-cut technique. Through an explicit characterization of the Voronoi cell, we provide a comprehensive analysis of existing decoders: we prove that the standard BDD algorithm of Micciancio and Peikert (2012) unexpectedly solves CVP exactly for odd base b and integer targets, but degrades to a worst-case approximation factor of n^0.5 for binary base b=2 and continuous targets. Furthermore, we prove that standard pruned sphere decoding requires exponential time exp(Omega(n)) even when using a geometrically optimal basis. For the dual (generator) power gadget lattice, we construct an obtuse superbasis---proving for the first time that it is a lattice of "Voronoi's first kind"---which yields a polynomial-time O(n^3) exact CVP algorithm via graph min-cut reductions. Geometrically, we determine all successive minima and enumerate the facets of their Voronoi cells. In particular, we show that while the parity-check lattice has a sparse Voronoi cell with n^2+n facets, the generator lattice reaches the theoretical upper bound of 2(2^n-1) facets. Finally, we observe that CRT gadget lattices and their duals admit an orthogonal basis, yielding trivial linear-time CVP algorithms.
Last updated:  2026-11-08
An Agile Homomorphic Encryption and ML-KEM Scheme for Privacy-Preserving Health Data Processing
Daniel RESENDE, Nadia El Mrabet, and Ulrich Kühne
The storage and processing of health data raise serious privacy con- cerns; therefore, the data must be encrypted. Fully Homomorphic Encryption (FHE) allows computations on encrypted data, which makes it a very promising technology in this context. However, although the efficiency of FHE algorithms has improved in recent years, they remain very complex. The security of several prominent FHE schemes is based on variants of the Learning With Errors (LWE) problem, which is also the basis of Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM), the new post-quantum standard for asymmetric encryption. In this paper, we propose an agile cryptographic scheme – combining ML-KEM and BGV – that allows efficient implementations in an embedded use case. We describe the parameter selection for the proposed scheme and show its feasibility with a proof-of-concept implementation.
Last updated:  2026-11-08
Twisted Towers: A Faster and Fully Costed SexTNFS Attack
Gautam Botrel
We study the Special exTNFS attack on discrete logarithms in the target group $\mathbb{G}_T$ of BLS12-381. We give a (6,2) design in which every step is priced in one instruction-level model: relation collection, cofactorisation, filtering, linear algebra, the Block Wiedemann generator and both individual logarithms, at success probability at least 0.39. The design rests on an explicit twisted tower. The sextic base field has an involution $\sigma$ and a unit $c$ with $c\,\sigma(c)=-1$, so $\tau:(y,x)\mapsto(\sigma y,cx)$ has order 4 and acts on $\mathbb{F}_{p^{12}}$ as $\mathrm{Frob}^3$. Relations and ideals then come in orbits of four. The quotient linear system has Gaussian-integer entries read modulo $r$, and ten Schirokauer maps suffice. A norm-2 element of the base field enables a coset sieve. We also observe that yield estimates over TNFS coefficient cubes count unit multiples $(\varepsilon a,\varepsilon b)$ as distinct relations. For the valid polynomial pair closest to the published BLS12-381 design, only $2^{-2.81}$ of the smoothness-weighted cube points give distinct relations. Under stated heuristics the ledger is $2^{115.72}$ dense $\mathbb{F}_{p^{12}}$-multiplication equivalents, about $2^{130}$ AArch64 instructions. Under our instruction model and transferred pricing assumptions, the design is estimated to cost 0.74 to 1.08 bit less (about 0.8) than a fundamental-domain version of the published design. Under the published cost models the difference ranges from 0.57 bit in our favour to 0.19 bit against. Nothing was run at full size, and the practical security of BLS12-381 is unchanged.
Last updated:  2026-11-08
Non-Interactive Threshold Mercurial Signatures with Applications to Threshold DAC
Scott Griffy, Nicholas Jankovic, Anna Lysyanskaya, and Arup Mondal
In a mercurial signature, a signer signs a representative $m$ of an equivalence class of messages on behalf of a representative $\mathsf{pk}$ of an equivalence class of public keys, receiving the signature $\sigma$. One can then transform $\sigma$ into a signature $\sigma'$ on an equivalent (to $m$) message $m'$ under an equivalent (to $\mathsf{pk}$) public key $\mathsf{pk}'$. Mercurial signatures are helpful in constructing delegatable anonymous credentials (DACs): their privacy properties enable straightforward randomization of a credential chain, hiding the identity of each signer while preserving the authenticity of the overall credential. Unfortunately, without trusted setup, known constructions of mercurial signatures satisfy only a weak form of this privacy property. Specifically, an adversary who is responsible for a link in a delegation chain—and thus knows its corresponding secret key—will be able to recognize this link even after the chain has been randomized. To address this issue, Abe et al. (Asiacrypt 2024) proposed (interactive) threshold mercurial signatures (TMS), which remove the reliance on a single trusted signer by distributing the signing capability among multiple parties, none of whom knows the signing key. However, this contribution was far from practical, as it required the signers to interact with each other during the signing process. In this work, we define and construct the first non-interactive TMS, where each signer computes its partial signature locally, and any $t$ of them combine into an ordinary mercurial signature. This is done using the mercurial signature of Mir et al. (CCS 2023) as a starting point. We also enable the Mir et al. construction to sign its own public keys, a property that is essential for DACs but had been left as an open question. Taking these two contributions together, we build the first non-interactive threshold delegatable anonymous credentials with non-transferable credentials.
Last updated:  2026-11-08
Archive Certificates for ML-DSA-87 Authorizations from an Exact Bounded Relation
Yacine Alloul
A blockchain that signs every transaction with FIPS 204 ML-DSA-87 keeps 4,627 bytes of signature per transaction forever. We describe and measure an archive certificate: one hash-based proof, for a range of already validated blocks, of knowledge of canonical FIPS 204 signatures on exactly the recorded messages under the keys resolved from chain state. Fresh blocks keep native verification. The construction starts from an exact bounded relation for ML-DSA-87 verification once the high bits $u = w'_1$ are fixed. The main certificate keeps $u$ hidden and proves the SHAKE256 challenge hash inside the proof, by a GKR argument for Keccak-f[1600] over the same WHIR commitment as the lattice relation. For 65,536 signatures we measured 104.09 bytes per signature in a Johnson-regime family, which has a classical bound only, and 126.89 in a unique-decoding family, against 4,627 bytes raw. The price is a slow prover and a verifier slower than native verification. At $2^{64}$ queries and $2^{20}$ verification submissions, under the compiler, coding and extractor-efficiency hypotheses specified in the security analysis, the classical random-oracle extraction error is below $2^{-188.07}$ for the Johnson family and below $2^{-201.99}$ for unique decoding. In the quantum random oracle model we state, for the unique-decoding family only, an extraction-failure bound below $2^{-129.67}$ at $2^{64}$ quantum queries and $2^{20}$ verification submissions; it is not a work factor. Lean 4 checks Lemmas 1 to 4 and the WHIR steps at the scopes detailed in the formal-verification section, the registered interactive theorem's conditions K1–K4, exact ledger arithmetic, and conditional compiler compositions. The extractor's efficiency condition K5 is derived in a defined bit-cost model from two implementation premises that remain open. The link between the interactive predicate and the ledger is proved within an abstract compiler interface; concrete compiled security games and correspondence with the Rust verifier remain outside the checked result. The bundles identified in that section are also verified with AXLE. An external review is outstanding, and certificate-only bootstrap remains disabled under the stated deployment conditions.
Last updated:  2026-11-08
γ₁₁: Unequal Triangles and Adapted References — the macadamia 0050
Rémi Géraud-Stewart and David Naccache
This paper settles the ninth of the ten macadamias of the series on the Hermite constant in dimension 11: the perfect form $P$ = 0050:024468269 of rank 9, of determinant 8192/9 at minimum 4. The root paper reduces $\gamma_{11}$ to chains $L\supset M\supset N$ of lattices of ranks 11, 10, 9, each with minimum at least 4; we prove that every admissible chain whose rank-9 member is admissibly marked by $P$ has $\det L\ge 972$. No argument at rank 10 can do this, because an actual lattice of rank 10 with determinant $3328/3<4\cdot 972^{9/11}$ lies over $P$. The proof is computer-assisted, with explicit finite checks. Its decisive step is elementary: the three additive dual vectors of a section covector and the first normal usually have different lengths, and keeping the three lengths in the circle obstruction, instead of their maximum, gives a determinant cap that sharpens every subsequent contact and spectral bound. Adapted reference forms turn the contact conditions into exact rational tests, a common slack is retained throughout, and four computational results reduce the problem to a five-parameter root, exhausted by a finite cover of 6 993 terminal regions replayed in exact arithmetic.
Last updated:  2026-11-08
γ₁₁: One Selected Contact, Two Linked Blocks — the macadamia 0030
Rémi Géraud-Stewart and David Naccache
This paper is one of five companion papers completing the proof of $\gamma_{11}=4/\sqrt[11]{972}$ announced in the root paper and assembled in “A Focus on Hermite Constant 11”. The root paper reduces a lattice of rank 11 with minimum 4 and determinant below 972 to a chain of sections of ranks 11, 10 and 9 whose rank-9 member is admissibly marked by one of 4 487 813 perfect forms; ten of them, the macadamias, lie under an actual lattice of rank 10 and need proofs of their own. We settle the first, the form 0030:030301719 of $\Lambda_9$ under $\Lambda_{10}$, where the bound has little margin. The argument selects one contact of the reference lattice from the actual metric, keeps the off-diagonal column shared by two eight-dimensional blocks of the section metric, applies one determinant–trace theorem to both blocks, and closes with a rational cover of three scalar parameters. The proof is computer-assisted: its finite inputs are three outer-range covers, two middle-range covers with 10 498 and 1 140 leaves, an annulus tree with 3 567 leaves and four smaller trees, every leaf checked in exact rational arithmetic.
Last updated:  2026-11-08
γ₁₁: Reduction by Sections — the macadamias 0019 and 0017
Rémi Géraud-Stewart and David Naccache
The root paper of this series reduces the value $\gamma_{11}=4/\sqrt[11]{972}$ of the Hermite constant in dimension 11 to a statement about chains $L\supset M\supset N$ of lattices of ranks 11, 10 and 9 whose rank-9 member lies over one of 4 487 813 perfect forms of rank 9; the $\gamma_{11}$ paper settles all of them but ten, the macadamias. This paper settles two of the ten: 0019:030884313 (the form $P_S$ of the root paper, an extension of $E_8$ by a simplex vector) and 0017:001746552 (the form $P_K$, KAPPA9.2). We prove that every admissible chain whose rank-9 member is admissibly marked by the form has $\det L\ge 972$. The method is a reduction by sections: for 0019 the nine simplex contacts turn the problem into one about an eight-dimensional covariance matrix, and a tree of 17 347 nodes with 7 743 scalar determinant witnesses covers the remaining box; for 0017 a two-vector flag bound and the decomposition of the section metric along a short-dual plane and its rank-seven kernel reduce the problem to five parameters, covered by a tree of 3 010 595 nodes. The proof is computer-assisted: every finite check is stated as a Computational result, and the verification records in the certificate archive are named.
Last updated:  2026-11-08
γ₁₁: A Finite Spectral Relaxation — the macadamia 0008
Rémi Géraud-Stewart and David Naccache
The root paper of this series reduces $\gamma_{11}=4/\sqrt[11]{972}$ to a statement about chains of lattices $L\supset M\supset N$ of ranks 11, 10 and 9, cut along shortest dual vectors, whose rank-9 member lies over one of 4 487 813 perfect forms. Ten of these forms, the macadamias, lie under an actual lattice of rank 10 of small determinant and need a proof at rank 11, where the bound 972 is attained. This paper settles the form 0008:022143116, which lies under a section of $K_{11}$ with 276 minimal vectors: every admissible chain whose rank-9 member is admissibly marked by this form has $\det L\ge 972$. In coordinates aligned with the form, the section metric is $S=I+E$ with three blocks of size three. Two sufficient flag tests come from short dual covectors and integral triangles; local reductions, proved from rational comparisons and Bernstein or Sturm certificates, remove explicit regions of the parameters; every remaining real spectrum is mapped, with explicit allowances, into a finite relaxation on 81 grid nodes, which a tree of 400 nodes with 1 091 rational certificates, replayed in two exact arithmetic implementations, excludes. The proof is computer-assisted, with explicit finite checks stated as one Computational result.
Last updated:  2026-11-08
γ₁₁: Contact Geometry — the macadamias 0001, 0014, 0059 and 0015
Rémi Géraud-Stewart and David Naccache
The root paper of this series reduces the value $\gamma_{11}=4/\sqrt[11]{972}$ of the Hermite constant to a statement about chains of lattices $L\supset M\supset N$ of ranks 11, 10 and 9 whose rank-9 member lies, in the sense of Voronoi, over one of 4 487 813 perfect forms; the $\gamma_{11}$ paper excludes all of them but ten, the macadamias. This paper settles four macadamias, the forms 0001:010488327, 0014:001749549, 0059:016902802 and 0015:030291998, by one method: the geometry of the contacts of the form. A section frame of short dual vectors forces the first gluing of $M$ over $N$ to lie near one of finitely many coherent centres; at such a centre the rank-10 metric is compared with an explicit reference lattice, whose Delaunay cells and contact identities give a uniform bound on its covering radius; and a primitive-extension inequality turns that bound into $\det L\ge 972$. The proof is computer-assisted: every finite check it uses is stated as a Computational result with the records of the certificate archive that certify it, and all comparisons are between explicit rational numbers.
Last updated:  2026-11-08
A Focus on Hermite Constant 11
Rémi Géraud-Stewart and David Naccache
This paper assembles the dimension-eleven argument in a series on the Hermite constants in dimensions ten, eleven and twelve. The root paper reduces a hypothetical lattice of minimum 4 and determinant below 972 to a chain of sections of ranks eleven, ten and nine. Its rank-nine section is marked by a perfect form below an explicit determinant cutoff. The global finite computation leaves 4 487 813 candidate forms and excludes all but ten by certificates. We state the mathematical content of these certificates, describe their data and checking rules, and prove why every valid certificate excludes the corresponding form. The four formats are trace, domain, glue and tree certificates; each tree must cover its entire stated domain. One of the ten remaining cases, 0052:005247066, is treated here by a complete gluing cover. Five companion papers settle the other nine. We also prove the common inequalities used by those local arguments. The resulting bound is $\gamma_{11}=4/\sqrt[11]{972}$, conditional on the attributed rank-nine classification, the rank-ten census and the stated global and local finite checks.
Last updated:  2026-11-08
The Hermite Constants in Dimensions 10, 11 and 12
Rémi Géraud-Stewart and David Naccache
This paper introduces a series of seven papers establishing $\gamma_{10}^{10}=4^{10}/768$, $\gamma_{11}^{11}=4^{11}/972$ and $\gamma_{12}=4/\sqrt{3}$, under the attributed classification of perfect forms of rank nine and the explicitly stated computational inputs. The argument treats the dimensions in order. In dimension ten, a section orthogonal to a shortest dual vector is compared with a perfect form. A completed exact census leaves three possible reference forms, and matrix inequalities exclude a determinant below 768 in each case. In dimension eleven, two successive sections give a chain of ranks eleven, ten and nine. The dimension-ten bound controls the determinant of the last section. The verified global census and preliminary certificates reduce the problem to ten local cases: nine are treated in five companion papers, and one in “A Focus on Hermite Constant 11”. The local arguments combine contact geometry, section bounds and finite rational covers. Mordell’s inequality then gives the dimension-twelve upper bound, matched by the Coxeter–Todd lattice. We prove the common reduction, explain the dependency between the papers, and state exactly which finite assertions must be checked. The accompanying Lean development verifies the complete analytic deduction from those inputs; external exact checkers verify the large certificate data.
Last updated:  2026-11-08
Incrementally Verifiable Oracle Aided Computation
Shafi Goldwasser and Yael Tauman Kalai
Incrementally verifiable computation ($\IVC$) allows a prover to maintain a short proof that can be efficiently updated after each computation step, without retaining or recomputing the preceding execution. In the context of AI safety, the need for incremental verification is particularly important, as AI systems interact with users over time and perform further computation after each interaction. However, standard $\IVC$ schemes do not directly address a crucial feature of AI tasks: their dependence on external information and expertise. Indeed, the UK AISI Alignment Team~\cite{IrvingM25} emphasizes that verification methods for AI safety should accommodate access to external information and human judgment. This is the topic of this paper. We construct $\IVC$ schemes for {\em oracle-aided} computations under the Learning with Errors ($\LWE$) assumption by first constructing succinct non-interactive arguments ($\SNARG$s), and then extending them to the incremental setting. We consider the following two settings, where below, $\lambda$ is the security parameter, $n$ is the input length, and $T$, $S$, and $Q$ are the time, space, and oracle-query bounds. \begin{itemize} \item \textbf{Robust computations.} For bounded-space computations, including non-deterministic computations, in which every accepting purported execution on a false input contains at least an $\varepsilon$-fraction of incorrect oracle answers, we construct {\em privately verifiable} $\SNARG$s and $\IVC$. For $\IVC$, the corresponding robustness condition is imposed on the claimed configuration. Public parameters, private verification keys, and proofs have length $\poly(\lambda,S,\log T,1/\varepsilon)$, and verification uses $O(\lambda/\varepsilon)$ oracle calls. We complement this result with a lower bound ruling out (deterministic) publicly verifiable $\SNARG$s and $\IVC$s with public parameters of length $o(n)$, and $o(Q)$ verifier oracle queries. \item \textbf{Signed oracles.} For oracles that digitally sign their query-answer pairs, we construct publicly verifiable $\SNARG$s and $\IVC$ without a robustness assumption, and with oracle-free setup and verification. Public parameters and proofs have length $\poly(\lambda,S,\log T)$. For deterministic computations with oracle query and answer lengths $\poly(\lambda,\log T)$, we remove the dependence on $S$, obtaining public parameter and proof lengths $\poly(\lambda,\log T)$. \end{itemize} All our constructions have adaptive completeness and soundness. Sub-exponential hardness of $\LWE$ suffices for all constructions; polynomial hardness suffices in the deterministic signed-oracle setting when $T$ is polynomially bounded in $\lambda$. All cryptographic assumptions are required to hold even given access to the underlying oracle.
Last updated:  2026-11-08
Revisiting the Security of OleF, t-OleF, and OlÆF
Tingting Guo, Peng Wang, Shuping Mao, Yan Jia, and Jiadong Han
We revisit the security of OleF, t-OleF, and \olaef\ and identify two independent security flaws. First, we establish a mask-compensation relation between continuation and termination processing in OleF and t-OleF. Exploiting this relation, we construct a two-encryption-query distinguisher against OleF with advantage $1-2^{-2n}$. We further give two concrete AXU hash families for which the same attack applies to t-OleF, revealing flaws in the original DOSPRP and SPRTOP security proofs. We extend these attacks to \olaef\ through valid encodings, breaking its privacy and integrity. In particular, the integrity forgery succeeds with probability $1$ under full-domain verification when the target expansion length is $1$ and extends to larger expansion lengths under suffix-only verification. Second, we refute the claimed ideal RUP integrity bound for variable-expansion online authenticated encryption. Even with an ideal tweakable online permutation, prior unverified decryption queries at smaller expansion lengths can reveal part of the target authentication suffix. We construct counterexamples showing that two such decryption queries and one forgery attempt achieve a success probability of $3/8$, exceeding the claimed bound of $1/4$. We also derive a general expression for the forgery success probability. Finally, we discuss the corresponding repairing
Last updated:  2026-11-08
LedgerHedger: Gas Reservation for Smart-Contract Security
Itay Tsabary, Alex Manuskin, Roi Bar-Zur, and Ittay Eyal
In smart contract blockchain platforms such as Ethereum, users interact with the system by issuing transactions. System operators called miners or validators add those transactions to the blockchain. Users attach to each transaction a fee, which is collected by the miner who placed it in the blockchain. Miners naturally prioritize better-paying transactions. This process creates a volatile fee market due to limited throughput and fluctuating demand. The fee required to place a transaction in the future is unknown; yet, ensuring timely transaction confirmation is critical for securing smart contracts that represent billions of dollars and underpin prominent blockchain scaling solutions. We present LedgerHedger, a novel mechanism that guarantees the confirmation of a transaction within a specified time frame. Due to the absence of external enforcement in decentralized systems, LedgerHedger uses incentives. Its core is a hedging agreement between a transaction issuer and a second party, possibly a miner. The issuing party pays for the transaction upfront while the second party commits to paying any necessary fees when the transaction is issued in the future, even if they exceed the original payment. LedgerHedger gives rise to a strategic game, where the issuing party deposits the transaction payment and the committing party deposits a collateral. During the target time frame, the latter is required to confirm the transaction if it exists, or they have the option to withdraw the payment and the collateral if the transaction is not presented. We demonstrate that for a broad range of parameters, a subgame perfect equilibrium exists where both parties are incentivized to act as desired, thereby guaranteeing transaction confirmation. We implement LedgerHedger and deploy it on an Ethereum test network, showcasing its efficacy and minor overhead.
Last updated:  2026-11-08
Deep Bribe: Predicting the Rise of Bribery in Blockchain Mining with Deep RL
Roi Bar-Zur, Danielle Dori, Sharon Vardi, Ittay Eyal, and Aviv Tamar
Blockchain security relies on incentives to ensure participants, called miners, cooperate and behave as the protocol dictates. Such protocols have a security threshold – a miner whose relative computational power is larger than the threshold can deviate to improve her revenue. Moreover, blockchain participants can behave in a petty compliant manner: usually follow the protocol, but deviate to increase revenue when deviation cannot be distinguished externally from the prescribed behavior. The effect of petty compliant miners on the security threshold of blockchains is not well understood. Due to the complexity of the analysis, it remained an open question since Carlsten et al. identified it in 2016. In this work, we use deep Reinforcement Learning (RL) to analyze how a rational miner performs selfish mining by deviating from the protocol to maximize revenue when petty compliant miners are present. We find that a selfish miner can exploit petty compliant miners to increase her revenue by bribing them. Our method reveals that the security threshold is lower when petty compliant miners are present. In particular, with parameters estimated from the Bitcoin blockchain, we find the threshold drops from the known value of 25% to only 21% (or 19%) when 50% (or 75%) of the other miners are petty compliant. Hence, our deep RL analysis puts the open question to rest; the presence of petty compliant miners exacerbates a blockchain’s vulnerability to selfish mining and is a major security threat.
Last updated:  2026-11-08
WeRLman: To Tackle Whale (Transactions), Go Deep (RL)
Roi Bar-Zur, Ameer Abu-Hanna, Ittay Eyal, and Aviv Tamar
The security of proof-of-work blockchain protocols critically relies on incentives. Their operators, called miners, receive rewards for creating blocks containing user-generated transactions. Each block rewards its creator with newly minted tokens and with transaction fees paid by the users. The protocol stability is violated if any of the miners surpasses a threshold ratio of the computational power; she is then motivated to deviate with selfish mining and increase her rewards. Previous analyses of selfish mining strategies assumed constant rewards. But with statistics from operational systems, we show that there are occasional whales- blocks with exceptional rewards. Modeling this behavior implies a state-space that grows exponentially with the parameters, becoming prohibitively large for existing analysis tools. We present the WeRLman framework to analyze such models. WeRLman uses deep Reinforcement Learning (RL), inspired by the state-of-the-art AlphaGo Zero algorithm. Directly extending AlphaGo Zero to a stochastic model leads to high sampling noise, which is detrimental to the learning process. Therefore, WeRLman employs novel variance reduction techniques by exploiting the recurrent nature of the system and prior knowledge of transition probabilities. Evaluating WeRLman against models we can accurately solve demonstrates it achieves unprecedented accuracy in deep RL for blockchain. We use WeRLman to analyze the incentives of a rational miner in various settings and upper-bound the security threshold of Bitcoin-like blockchains. We show, for the first time, a negative relationship between fee variability and the security threshold. The previously known bound, with constant rewards, stands at 0.25. We show that considering whale transactions reduces this threshold considerably. In particular, with Bitcoin historical fees and its future minting policy, its threshold for deviation will drop to 0.2 in 10 years, 0.17 in 20 years, and to 0.12 in 30 years. With recent fees from the Ethereum smart-contract platform, the threshold drops to 0.17. These are below the common sizes of large miners.
Last updated:  2026-11-08
Threshold Batched Attribute-Based Encryption from Succinct LWE
Shayeef Murshid, Ramprasad Sarkar, and Mriganka Mandal
Batched identity-based encryption (BIBE) enables a single compact key to decrypt ciphertexts associated with a designated batch of identities. Batched attribute-based encryption (B-ABE) extends this functionality to attribute-based access control, while threshold batched attribute-based encryption (TB-ABE) further distributes the decryption capability among multiple parties. Existing constructions of TB-ABE rely on bilinear pairings, motivating post-quantum alternatives. In this work, we give, to the best of our knowledge, the first lattice-based candidate construction of TB-ABE. Our construction combines the succinct polynomial-digest mechanism underlying lattice-based BIBE with key-homomorphic evaluation for arithmetic-circuit policies and linear secret sharing. We prove security under the ℓ-succinct LWE assumption, assuming the required share-uniformity property of the underlying ramp threshold sharing scheme.
Last updated:  2026-11-08
Designing Quantum-Safe Network Architectures via Certified Randomness Distribution
Filip-Ioan Ceară and Diana Maimuţ
We propose an alternative design for quantum-safe network architectures, based on distributing certified randomness generated by different trust-level QRNGs. Our modular methodology aggregates high-trust entropy from upper network layers with local contributions, enhancing the security guarantees of locally available random sequences. Leveraging the physical guarantees of QRNGs and symmetric-key cryptographic algorithms for node authentication, our approach enables immediately deployable, quantum-safe infrastructures. Such a paradigm bypasses the practical security limitations of current QKD-based solutions, while avoiding massive key sizes and latency inherent to asymmetric PQC implementations.
Last updated:  2026-11-08
Generalized Batched Decomposition Key-Switching for CKKS
Antonio J. Peña, Zaira Pindado, and Hugo Sanz-González
In lattice-based homomorphic encryption schemes, ciphertexts carry an inherent noise that grows as computation advances. The key-switching procedure of these schemes allows the homomorphic re-encryption of a ciphertext under a new secret key, but it incurs substantial noise growth and computational cost. In this work, we generalize the RNS-based decomposition technique of the CKKS scheme to an arbitrary number of input polynomials and secret keys. Performing multiple relinearizations and rotations in batch enables one to hoist the modulus lowering and decomposition steps of key-switching, respectively, which restricts noise growth and avoids redundant computation. We prove the security and correctness of all the proposed algorithms, and derive explicit noise bounds for them. As an application, we introduce a ternary multiplication algorithm that relinearizes the non-affine components of a product of three ciphertexts in batch, and performs rescaling in two phases so that relinearization runs at a lower modulus level. Compared with the usual sequence of two binary multiplications, this algorithm introduces a single key-switching error term, improving precision by up to half a bit and reducing latency by up to 1.31×. We generalize to n-ary ciphertext multiplication via a polynomial-time algorithm that combines binary and ternary multiplications into a tree of optimum depth minimizing a given latency cost function. Such products arise, for instance, in the SHIP bootstrapping algorithm; experiments with 128-bit-secure parameters on top of the Lattigo library show an average speedup of 1.20× over the standard approach for n = 192 with 32 threads. Further examples illustrate the impact of these optimizations on private deep neural network inference. In addition, we provide—to the best of our knowledge—the first noise analysis of the double-hoisted BSGS matrix-vector multiplication algorithm of Bossuat et al. (2021), a building block of state-of-the-art CKKS bootstrapping circuits. We discuss a novel optimization concerning the automorphism applications during its giant steps.
Last updated:  2026-11-08
The Minimum Bucket Capacity for Reliable Path ORAM
Yijia Chang and Man Ho Au
Path ORAM hides memory access patterns by storing $N$ data blocks in a binary tree whose buckets have capacity $Z$, using a client-side stash for blocks that cannot be placed in the tree. Smaller buckets reduce storage and communication costs but increase the risk of stash overflow. The revised Path ORAM analysis in 2014 established an exponentially decreasing stash overflow probability for $Z \geq 5$. Experiments suggest small stashes at $Z=4$ and substantially larger ones at $Z=3$. However, it remained unknown whether $Z=4$ admits a uniform exponential stash bound or whether such a bound is impossible at $Z=3$. We establish a sharp threshold at $Z=4$ for binary Path ORAM with tree depth $L=\lceil \log_2 N \rceil$. For $Z=4$, we prove that, uniformly over all database sizes and fixed access sequences, the stash size $S$ after the final refill satisfies \[ \Pr[S>R] \leq \frac{23}{28}\left(\frac{5}{7}\right)^R \] for every integer $R \geq 0$. For $Z=3$, we exhibit a family of instances on which a single sequential scan of all $N$ blocks produces a stash of size $\Omega(N)$ with probability bounded away from zero. Thus, four is the minimum bucket capacity admitting a uniform exponential stash bound: a logarithmic stash suffices for polynomial-length executions with inverse-polynomial failure probability at $Z=4$, whereas at $Z=3$ no sublinear stash can make the overflow probability vanish uniformly. Our proofs connect the actual Path ORAM process with dependent node loads to an auxiliary model with independent geometric node loads. This independence enables a recursive analysis of overflow that avoids the union bound over rooted subtrees used in the previous $Z=5$ proof. The main challenge is to transfer bounds from the auxiliary model to the actual process, which requires different techniques for the upper and lower bounds. For $Z=4$, we develop a two-stage randomization argument that bounds the actual process's exponential overflow moment by that of the auxiliary model. For $Z=3$, we develop a local continuous-time approximation with controlled errors that transfers an overflow surplus from the auxiliary model to the actual process, yielding the linear stash lower bound. Together, these arguments establish the sharp threshold at bucket capacity four.
Last updated:  2026-11-08
Atlantis: Lattice-based Anonymous Tokens with Private Metadata Bit
Foteini Baldimtsi and Aayush Yadav
Anonymous tokens with private metadata bit (ATPM) allow an issuer to embed a hidden trust flag, as a single bit, within issued tokens. The bit remains hidden from the clients, but verifiers can read the bit and rate-limit or discard tokens marked suspect. A series of ATPM constructions exist in the literature, however all current constructions rely on classical hardness assumptions such as RSA groups, pairings, or elliptic-curve VRFs and do not provide any post-quantum security guarantees. In this work we present, the first ATPM scheme based on lattice assumptions. Tokens generated with our scheme are publicly verifiable, and privately bit-extractable given partial knowledge of the issuing authority's secret. Our design follows the Fischlin blind-signature paradigm and enriches it with lattice-based linearly-homomorphic encryption to carry the hidden bit. We also instantiate our scheme from Falcon-512 and the efficient LNP22 lattice NIZK proof system (Lyubashevsky et. al, Crypto '22). The resulting protocol, which we call $\textsf{Atlantis}$, requires 70 KB of client-issuer communication and yields 129 KB tokens.
Last updated:  2026-11-08
Catalytic Tree Evaluation From Matching Vectors
Alexandra Henzinger, Edward Pyne, and Seyoon Ragavan
We give new algorithms for tree evaluation (S. Cook et al. TOCT 2012) in the catalytic-computing model (Buhrman et al. STOC 2014). Two existing approaches aim to solve tree evaluation (TreeEval) in low space: on the one hand, J. Cook and Mertz (STOC 2024) give an algorithm for TreeEval running in super-logarithmic space $O(\log n\log\log n)$ and super-polynomial time $n^{O(\log\log n)}$. On the other hand, an earlier algorithm of J. Cook and Mertz (STOC 2020), run on a catalytic tape, solves TreeEval in logarithmic $O(\log n)$ free space and polynomial time, but with polynomial $O(\sqrt{n})$ catalytic space. We show that the latter result can be improved. We give a catalytic algorithm for TreeEval with logarithmic $O(\log n)$ free space, polynomial runtime, and subpolynomial $2^{O(\log^\epsilon n)}$ catalytic space (for any $\epsilon > 0$). Our result also implies an improved simulation of time by \textit{catalytic} space, via the reduction of Williams (STOC 2025). Our TreeEval algorithm comes from a framework, inspired by private information retrieval, that generically reduces tree evaluation to two combinatorial objects: matching-vector families and \emph{decoders} (a new object we define that closely resembles decoding polynomials). These ingredients' parameters directly govern an algorithm's resources: the vectors' dimension determines its catalytic space, and the decoder's sparsity determines its free space and runtime. In addition to enabling our new algorithm, this framework explains existing tradeoffs, for example why the Cook–Mertz algorithm needs super-logarithmic space but no catalytic tape. It also lets better matching-vector families or decoders plug in directly to give better algorithms.
Last updated:  2026-11-07
Dynark: Making Groth16 Dynamic
Tianyu Zhang, Yupeng Ouyang, and Yupeng Zhang
In recent years, numerous new and more efficient constructions of zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) have been proposed, motivated by their growing practical applications. However, in most schemes, when the witness is changed, the prover has to recompute the proof from scratch even if the new witness is close to the old one. This is inefficient for applications where proofs are generated for dynamically changing witnesses with small changes. In this paper, we introduce DYNARK, a dynamic zkSNARK scheme that can update the proof in sublinear time when the change of the witness is small. DYNARK is built on top of the seminal zkSNARK protocol of Groth, 2016. In the semi-dynamic setting, for an R1CS of size $n$, after a preprocessing of $O(n\log n)$ group operations on the original witness, it only takes $O(d)$ group operations and $O(d\log^2 d)$ field operations to update the proof for a new witness with distance $d$ from the original witness, which is nearly optimal. In the fully-dynamic setting, the update time of DYNARK is $O(d\sqrt{n\log n})$ group operations and $O(d\log^2 d)$ field operations. Both the proof size and the verifier time are $O(1)$, which are exactly the same as Groth16. Compared to the scheme in a prior work by Wang et al. 2024, we reduce the proof size from $O(\sqrt{n})$ to $O(1)$ without relying on pairing product arguments or another zkSNARK, and the update time and the verifier time of DYNARK are faster in practice. Experimental results show that for $n=2^{20}$, after a one-time preprocessing of 74.3 seconds, it merely takes 3 milliseconds to update the proof in our semi-dynamic zkSNARK for $d=1$, and 60 milliseconds to update the proof in our fully-dynamic zkSNARK. These are 1433$\times$ and 73$\times$ faster than Groth16, respectively. The proof size is 192 bytes and the verifier time is 4.4 milliseconds. The system is fully compatible with any existing deployment of Groth16 without changing the trusted setup, the proof and the verification algorithm.
Last updated:  2026-11-07
How to Revoke Users in Encryption Schemes?
Sanjam Garg, Dimitris Kolonelos, Benjamin Ostrovsky, and Guru-Vamsi Policharla
Revocation is essential for keeping encryption secure as keys leak, devices are compromised or users leave the system. We revisit the problem of revocation for encryption schemes and give, to our knowledge, the first approach combining anonymous, collusion-resistant revocation with unchanged keys and access rules, succinct ciphertext overhead and a trustless revocation authority, i.e. that cannot decrypt. Revoking a user publishes one random-looking pseudonym, without telling encryptors whose key was revoked. A party can decrypt future ciphertexts only if it is unrevoked and satisfies the original access decryption rule. Our core observation is that revocation is, at heart, witness encryption for the statement that one satisfies the access rule and that the pseudonym bound to one's key has not been revoked. Although general-purpose witness encryption remains far from practical, we observe that the statements arising from revocation are simple and algebraic, and we show that they fall within the special-purpose framework of Garg et al. (CRYPTO 2025), which compiles short arguments of knowledge (called ``gadgets'') into efficient witness encryption using bilinear groups. Our technical contribution is a pair of succinct non-membership gadgets for this framework, one for a single hidden pseudonym and one that certifies non-revocation jointly for all users selected by an access rule. Both gadgets are generic and modular, as they compose with the gadgets expressing a wide range of access rules, and thus provide a single revocation mechanism that is designed once and reused across different encryption schemes, without redesigning either the scheme or the revocation. These gadgets yield the following applications. First, we give a black-box transformation adding revocation to arbitrary independently instantiated public-key encryption, with constant-size cryptographic ciphertext overhead. For unrevoked users, confidentiality continues to rely only on the security of the underlying scheme. Then, we demonstrate applications to advanced encryption scheme, constructing revocable schemes for distributed broadcast, registered attribute-based, and registered threshold encryption, with succinct cryptographic ciphertext components and threshold decryption shares. We prove adaptive security of our schemes in the generic bilinear-group and random-oracle models.
Last updated:  2026-11-07
Round-Optimal Statistical Verifiable Secret Sharing with Polynomial Complexity
Chen-Da Liu-Zhang and Elisaweta Masserova
Verifiable secret sharing (Chor, Goldwasser, Micali, and Awerbuch; FOCS'85) is a central primitive in secure computation, and its round complexity has been studied extensively. Rabin and Ben-Or [STOC'89] established the feasibility of statistical security up to $t<n/2$ corruptions, and Patra, Choudhary, Rabin, and Rangan [Crypto'09] showed that three sharing rounds are necessary. The work of Applebaum, Kachlon and Patra [STOC'23] introduced the first round-optimal VSS with three rounds of sharing and one round for reconstruction, albeit with exponential communication in the number of parties. We give the first round-optimal statistical VSS that has polynomial communication and computation for $t<n/2$. This resolves the efficiency question left open by Applebaum, Kachlon and Patra. The protocol is obtained from a new notion of weak secret sharing, in which the reconstruction-time freedom of a corrupt dealer is limited to choosing verification keys, which is of independent interest.
Last updated:  2026-11-07
From Degree Three to Degree Two: Statistical Randomized Encodings for All Functions
Emmanuela Orsini and Arpita Patra
A randomized encoding represents a function by a simpler randomized map whose output allows recovery of the function value while revealing essentially no further information about the input. Perfectly correct and perfectly private encodings of degree three over $\F_2$ are known for every Boolean function, but degree two cannot provide these guarantees for all functions (Ishai and Kushilevitz, FOCS 2000 and ICALP 2002). Whether degree two suffices when small statistical errors are allowed in both correctness and privacy has remained open. We construct quadratic randomized encodings of every Boolean function with exponentially small correctness and statistical privacy errors. The degree bound holds jointly in the input bits and independent uniform random bits, and the construction, encoder, decoder and simulator have complexity polynomial in the total size of mod-2 branching programs computing the function's output bits and in the security parameter. Our encodings also achieve decomposability and output locality three, meaning that each encoded bit depends on at most three input and random bits. These results resolve the degree-two and locality-three questions for statistical randomized encodings (Ishai, 2013). As an application, we obtain one-way functions of optimal output locality three from one-way functions in polynomial-time uniform $\mathrm{NC}^1$, improving the previous locality-four result under the same assumption (Applebaum, Ishai and Kushilevitz, FOCS 2004). We also obtain quadratic multiparty randomized encodings with negligible correctness and statistical privacy errors against semi-honest corruption of any coalition of parties. Previous general constructions for $k\ge4$ parties provided perfect correctness and privacy against at most $\lfloor 2k/3\rfloor$ corruptions (Applebaum, Ishai, Karni and Patra, CRYPTO 2022). Through known reductions, our encodings yield non-interactive reductions of every functionality to a fixed three-party functionality and three-round protocols in the two-round OT-hybrid model, with negligible correctness and statistical privacy errors against every coalition. They also yield non-interactive client--server protocols for every function whenever a majority of the servers is honest, even when corrupted servers collude with any set of clients. This server threshold is optimal in this model when privacy is required against arbitrary client coalitions.
Last updated:  2026-11-07
Linear Cryptanalysis with Bibrace Characters: Weak-Key Distinguishers for CRAFT
Roberto Civino
Linear cryptanalysis measures the correlation of a cipher with the characters of the group used to define differences. If that group is replaced by a second elementary abelian group structure on the same set, here the one coming from a binary bibrace, then the admissible masks are no longer the ordinary scalar products: exactly half of them survive, and the other half are forced to be quadratic. Beyne's geometric approach develops linear cryptanalysis over an arbitrary finite abelian group, providing a natural framework for this setting. We instantiate it on the group of a particular bibrace and apply it to CRAFT. Over this group the MIDORI/CRAFT S-box has four probability-one relations, forming a small subgroup of the dual which the S-box preserves in both directions. A trail that stays inside that subgroup is determined by its first mask and propagates linearly, so the search for the best such trail is a minimum weight codeword problem, which we solve exactly by complete enumeration. A trail costs correlation, and it restricts the key to a weak-key class. We show that the exact reading, obtained by analysing the diffusion layer and the key addition together rather than separately, gives a class several bits larger than the one obtained cell by cell. One concrete consequence is that CRAFT's round constants, whatever their values, impose no restriction at all. On CRAFT we obtain weak-key distinguishers up to eighteen rounds. At fourteen rounds a single trail has squared correlation $2^{-44}$ over a class of $2^{108}$ keys, against $2^{-62.12}$ for the designers' linear hull, which is the best known linear result on the cipher and holds for all keys. On that class the trail alone therefore exceeds the best linear correlation by eighteen bits at equal round count. Half of the optimal trails begin and end with ordinary linear masks, so these are linear approximations of CRAFT in the usual sense. A contrasting analysis of MIDORI64, which shares the S-box, traces its protection to the round constants and describes two known invariants of that cipher through other bibraces.
Last updated:  2026-11-07
SoK: Understanding Virtual Machines over Fully Homomorphic Encryption
Song Bian, Ziwei Ma, Yunhao Fu, Haowen Pan, Ruiyu Shen, Zhou Zhang, Ran Mao, Zaidong Li, Yintai Sun, Ruoyi Li, and Zhenyu Guan
We survey the current literature on fully homomorphic encryption (FHE) from a virtual machine (VM) perspective. We observe that programs behave in an intrinsically different way over FHE than on plaintext, forming a new paradigm of computation that is fundamentally constrained by the obliviousness of data. To better understand the computational properties, we compile more than 125 works to formulate a cross-layer systematic view of FHE VMs, with a special focus on understanding the concrete programming models over encrypted data. In particular, we identify three distinct forms of VMs over FHE, namely, the SISD VM, the SIMD VM, and the hybrid VM. To aid the cross-layer systematization, we also discuss how current FHE compilers and hardware accelerators can be applied to enhance the usability and performance of the respective VMs. In the experiment, we test eight VM instructions with varying precision as well as two end-to-end application programs to quantitatively assess the concrete design trade-offs for each of the VM paradigms. We conclude that FHE VMs of different types exhibit distinct utility and performance characteristics, necessitating new design methodologies to be developed in a cross-layer manner.
Last updated:  2026-11-07
Jazzline: Composable CryptoLine Functional Correctness Proofs for Jasmin Programs
José Bacelar Almeida, Manuel Barbosa, Gilles Barthe, Lionel Blatter, Gustavo Delerue, João Diogo Duarte, Benjamin Gregoire, Tiago Oliveira, Miguel Quaresma, Pierre-Yves Strub, Ming-Hsien Tsai, Bow-Yaw Wang, and Bo-Yin Yang
Jasmin is a programming language for high-speed and high-assurance cryptography. Correctness proofs of Jasmin programs are typically carried out deductively in EasyCrypt. This allows generality, modularity and composable reasoning, but does not scale well for low-level architecture-specific routines. CryptoLine offers a semi-automatic approach to formally verify algebraically-rich low-level cryptographic routines. CryptoLine proofs are self-contained: they are not integrated into higher-level formal verification developments. This paper shows how to soundly use CryptoLine to discharge subgoals in functional correctness proofs for complex Jasmin programs. We extend Jasmin with annotations and provide an automatic translation into a CryptoLine model, where most complex transformations are certified. We also formalize and implement the automatic extraction of the semantics of a CryptoLine proof
Last updated:  2026-11-07
Radical 3-isogenies for the ideal class group actions on $(2, \varepsilon)$-structures
Masaomi Shibata, Hiroshi Onuki, and Tsuyoshi Takagi
Chenu and Smith introduced the notion of $(d,\varepsilon)$-structures, pairs consisting of an elliptic curve over $\mathbb{F}_{p^2}$ and an isogeny of degree $d$ from the curve to its Galois conjugate, and defined an ideal class group action on supersingular $(d,\varepsilon)$-structures, inherited from the action on oriented supersingular elliptic curves. They also outlined extensions of the CSIDH key exchange and of the Delfs–Galbraith algorithm for the supersingular isogeny problem. In particular, they suggested that the latter, called the generalized Delfs–Galbraith algorithm, may be faster than the original one by a constant factor for small $d$, provided that the class group action on $(d,\varepsilon)$-structures can be evaluated efficiently. In this paper, we focus on the case $d = 2$ and present explicit radical $3$-isogenies for evaluating the action of the class of a prime ideal above $3$. Note that $3$ is the norm of the acting ideal, not the degree $d$ of the isogeny defining a structure; a radical $3$-isogeny maps a $(2,\varepsilon)$-structure to another. Our approach relies on two representations of $(2,\varepsilon)$-structures, by reductions of degree-$2$ $\mathbb{Q}$-curves and by Montgomery curves. We show that any $(2,\varepsilon)$-structure can be represented as a pair of a curve coefficient and a single sign, and from these representations we derive radical $3$-isogenies that efficiently implement the action. As an application, we give an explicit meet-in-the-middle algorithm for finding an ideal class connecting two given $(2,\varepsilon)$-structures, which is a part of the generalized Delfs–Galbraith algorithm.
Last updated:  2026-11-07
A proof of P≠NP (New symmetric encryption algorithm against any linear attacks and differential attacks)
Gao Ming
P vs NP problem is the most important unresolved problem in the field of computational complexity. Its impact has penetrated into all aspects of algorithm design, especially in the field of cryptography. The security of cryptographic algorithms based on short keys depends on whether P is equal to NP. In fact, the security requirements for cryptographic keys are much stricter than those for P$\neq$NP, the security of the key must ensure not only a sufficiently high computational complexity to crack it, but also consider the security of each bit of the key, while fully avoiding the effectiveness of various attack methods. In this paper, we innovatively propose a new encoding mechanism and develop a novel block symmetric encryption algorithm, which be named Eagle, whose encryption and decryption can be completed in linear time. The key consists of 12 variables, for the attacker, in the case when only the plaintext-ciphertext correspondence is known, the problem of cracking the key is equivalent to solving a system of equations about 12 unknown variables $(w_{1}, w_{2}, ..., w_{11}, w_{12})$ together with some implicit variables which are generated by the encryption process. In this paper, we will prove that there is no universal algorithm without brute-force searching at least one variable during the process of verifying five variables $(w_{1}$, $w_{2}$, $w_{3}$, $w_{4}$, $w_{9})$ whose computational complexity is not greater than solving the 12 variables. After performing elimination the implicit variables, the problem of verifying the five variables will be equivalently transformed into a series of general quintic equations about one variable $w_{11} \oplus w_{12}$ with coefficient given by other six variables $(w_{5}$, $w_{6}$, $w_{7}$, $w_{8}$, $w_{10}$, $w_{11})$, according to the conclusion that ``there is no algebraic solution to quintic equations", we can't establish a system of algebraic equations only containing the six variables $(w_{5}$, $w_{6}$, $w_{7}$, $w_{8}$, $w_{10}$, $w_{11})$ without $w_{11} \oplus w_{12}$. Without solving the six variables, the problem of verifying the five variables $(w_{1}$, $w_{2}$, $w_{3}$, $w_{4}$, $w_{9})$ is equivalent to solve the slope of a line given only the x-coordinates of several points on it, this implies that there is no universal algorithm without brute-force searching at least one variable to verify the five variables $(w_{1}$, $w_{2}$, $w_{3}$, $w_{4}$, $w_{9})$. Since the computational complexity of brute-force searching any single variable is exponential, thus the complexity of cracking the key is exponential. Thus decryption is a one-way function, and according to ``the existence of one-way function means P$\neq$NP", solving the unsolved problem of P vs NP. In addition, we further constructed another block symmetric encryption algorithm, which be named $Eagle^{*}$. The key of $Eagle^{*}$ is composed of three independent variables. Given any plaintext ciphertext correspondences, the problem of verifying any two variables in the key is equivalent to solving a system of quintic equations. Based on the conclusion that there is no algebraic solution to quintic equations, we assert that there is no fast algorithm to verify any two variables, and thus the computational complexity of cracking the key is equal to the computational complexity of completely exhausting the three variables. In addition, we conducted an in-depth analysis that without cracking the key, it is not possible to directly decrypt new ciphertext by simply collecting a large number of ciphertext plaintext correspondences. Due to the fact that ciphertext consists of four parts, three parts are completely random, while the other small part is calculated using plaintexts, keys, and random numbers, and their distribution is also completely random, thus $Eagle^{*}$ is resistant to all forms of linear and differential attacks.
Last updated:  2026-11-07
Registration-based Encryption with Logarithmic Registration
Xingfu Yan, Guiqiu Liao, Fan Yang, Haining Yang, Zheng Gong, Fucai Luo, and Bowen Zhao
Registration-based encryption (RBE) preserves IBE's identity-only encryption interface while eliminating key escrow: users generate their own keys, and a Key Curator manages only registered public keys. However, this design introduces a new challenge: user registration, since every joining user rrequires KC to update the registry. Although theoretical RBE constructions achieve polylogarithmic registration, they rely on costly cryptographic techniques and remain impractical. In existing deployable black-box RBE, registration takes $O(\sqrt{N})$ time ($N$ denotes the maximum user capacity). This gap between theoretical registration efficiency and deployability makes registration a key performance bottleneck for large-scale deployments of pairing-based RBE. This work presents a black-box pairing-based RBE construction under the decisional $(R,S,T,f)$-Diffie-Hellman assumption. Build on the multilinear tree, when registering a user's public key, KC updates only the corresponding root-to-leaf path associated with the user. Therefore, registration in our construction takes $O(\log \sqrt{N})$ time for the maximum user capacity $N$. Moreover, we provides membership and non-membership verification, and their batch verification supports to check registration status of multiple users. Experiments show registration and key generation complete in milliseconds when $N=10^7$. Compared with Glaeser et al. (CCS'23), our scheme accelerates registration by up to \(158\times\) and key generation by up to \(230\times\) with practical overheads.
Last updated:  2026-11-07
Overcoming Padding in Cryptography via Hardness of Certifying Random Strings
Yao-Ching Hsieh, Abhishek Jain, Jiatu Li, and Surya Mathialagan
Modern cryptography relies on a provable security paradigm where the security of a primitive is established from the intractability of one or more computational problems. Hybrid arguments are central to this approach. Somewhat unexpectedly, many security proofs in the literature that use this methodology require hybrids with description-size larger than the real scheme. To argue security, the real scheme is artificially padded to match this size. This so-called “superfluous padding” phenomenon is surprisingly commonplace and poses a barrier to achieving succinct cryptographic primitives where the size of the scheme parameters does not grow with the input length. We present a framework to eliminate padding in cryptography. We demonstrate several applications, including rate-1 iO, succinct (and extractable) witness encryption and succinct non-interactive arguments with short CRS for subclasses of NP, and multi-input functional encryption for functions with unbounded arity. To obtain our results, we establish a new connection between cryptography and proof complexity. Central to our approach is the notion of proof-complexity generators (PCGs) [Krajíček'01, Alekhnovich, Ben-Sasson, Razborov, Wigderson'04], which, informally speaking, formalizes the hardness of certifying random (incompressible) strings with propositional proof systems. Our applications are derived from a master theorem that lifts cryptographic security on “compressible instances” to security on any instance under the existence of PCGs. Due to its broad scope, this theorem might find future application
Last updated:  2026-11-07
Repeated Masks, Predictable Splices: Breaking AESpolyW and Its AEAD Applications
Shuping Mao, Peng Wang, Jiadong Han, Tingting Guo, Yan Jia, and Ying Chen
AESpolyW, presented at the 2026 IEEE Symposium on Security and Privacy, is a wide-block encryption mode that preserves the length of each message. Its design lets operations of the Advanced Encryption Standard (AES) overlap with hash computations based on polynomial evaluation. Our attacks splice ciphertexts by copying blocks from one ciphertext to the same positions in another. On five-block messages, two encryption queries and one decryption query at a fixed public parameter, called a tweak, distinguish AESpolyW from a random permutation at that tweak. The two probabilities of reporting AESpolyW differ by more than \(1-2^{-3n}\), where \(n\) is the block size in bits. When AESpolyW decrypts the splice, an internal block-cipher inversion takes an output from an earlier encryption. The published proof treats such reuse as unlikely. The splice also works across distinct tweaks. We also attack three AESpolyW-based schemes for authenticated encryption with associated data (AEAD). All three use encode-then-encipher, adding a zero block before encryption and checking it after decryption. The zero block goes at the end, after the first block, or at the beginning. The tweak \(T=A\|\nu\) concatenates one block of associated data \(A\), which is authenticated without encryption, and one block of nonce \(\nu\), a public value intended for one-time use per key. Two encryptions at distinct nonces suffice to forge a new ciphertext that passes verification with probability one. In the experiment for indistinguishability under chosen-ciphertext attack (IND-CCA), we use one auxiliary encryption at a nonce distinct from the challenge nonce and at most one decryption. This identifies which of two chosen plaintexts was encrypted in the challenge with probability one.
Last updated:  2026-11-07
QUASI: Post-Quantum Quorum Attestation of Pre-Validated Statements
Maksym Ioffe and Dahlia Malkhi
We present QUASI, a newly conceived class of protocols that enable a group of parties to produce a publicly verifiable attestation about a pre-validated statement. Designed for quorum-based systems, QUASI enables parties to attest to external entities that the statement is valid. Surprisingly, each party need not sign the entire statement: authenticating only a small subset of symbols suffices for the quorum to attest to the whole. A simple deterministic construction illustrates this possibility. Built purely from hashing and error correction, QUASI achieves small per-party contributions and low attestation generation and verification costs, without relying on SNARKs for aggregation. Our main contribution is a randomized construction achieving reductions of more than $10\times$ in per-party contribution size and hash computations for generation and verification, compared with full hash-based signatures. QUASI is a generic primitive supporting diverse applications. Two principal use cases are external attestation for signature-free consensus, enabling clients to verify statements about committed state; and preprocessing for SNARK-based aggregation, compounding QUASI's savings with succinct-proof compression.
Last updated:  2026-11-07
Pastel: Single Secret Leader Election with Private Weights
Jung Hee Cheon, Kevin Choi, Intak Hwang, Jaehee Kang, Alireza Kavousi, Junho Lee, and Yongdong Yeo
A single secret leader election (SSLE) protocol allows an election of exactly one leader among $n$ parties in a secrecy-preserving manner, where only the elected leader knows it has won until it publicly announces and claims leadership. Motivated by proof-of-stake blockchains where stakes are stored in an encrypted or committed form for the sake of privacy, we design and implement the first SSLE protocol with private weights. Each party's probability of winning an election in our protocol is weighted by stake, and these weights are private. Prior schemes in the literature only allow probabilistic (i.e. expectation of one but can be zero or many leaders) elections in the same setting. Preserving privacy also means public verification is paramount in order for a protocol to be practically reliable. In this respect, our protocol achieves security against malicious adversaries with a concrete implementation. In particular, we concretely implement the needed zero-knowledge proofs and thus do not rely on slashing (financial penalties) to achieve end-to-end malicious security, though slashing can still serve as a performance optimization. Along the way, we observe that previous SSLE protocols in a setting without private weights (either unweighted or with public weights) are either maliciously secure with implementation or post-quantum secure but not both, while our protocol achieves both.
Last updated:  2026-11-06
An improved algorithm to solve the isogeny problem in dimension 2 with precomputation
Maria Corte-Real Santos
We give a new algorithm for the superspecial isogeny problem in dimension $2$. After a one-time precomputation depending only on $p$ (which succeeds with overwhelming probability), each instance is solved in expected time and memory $p^{3/4+o(1)}$. This result is unconditional, relying on no heuristics. Including the precomputation, a single instance is solved in time $p^{19/23+o(1)}$, improving on the $p^{1+o(1)}$ of the Costello-Smith algorithm. The improvement holds even with the same memory as (the rigorous version of) their algorithm. The key ingredient is an algorithm that computes the equations of the Humbert surfaces $\mathcal{H}_{N^2}$ modulo $p$ for all $N$ up to a bound $D$ growing with $p$. These equations give a membership test for optimally $(N,N)$-split surfaces, which we evaluate in batches using fast multipoint evaluation. This speeds up the bottleneck of the Costello-Smith algorithm: finding an isogeny from a superspecial principally polarised abelian surface to a product of supersingular elliptic curves.
Last updated:  2026-11-06
FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design
William Diamond, Fatima Elsheimy, Dahlia Malkhi, Geoff Ramseyer, and Srivatsan Sridhar
Decentralized exchanges typically give traders no execution guarantee until a block is finalized. In the meantime, external prices move, traders strategically delay submission, and block producers can influence inclusion and ordering. We introduce FirstSwap, a DEX built on a constant-function market maker pricing curve that gives traders an early pre-approval before consensus, guaranteeing inclusion and execution within their submitted price limit, with final ordering determined by limit prices rather than by a block producer. We demonstrate the benefits of trade pre-approvals in an economic model combining auction theory with CEX-DEX arbitrage. When the CEX price changes gradually, FirstSwap rewards earlier traders with better prices, discouraging strategic delay and yielding higher social welfare and gains to AMM liquidity providers than a batch auction. When the CEX price jumps abruptly, FirstSwap yields higher welfare and smaller AMM losses than fair ordering. The central challenge is delivering fast trade pre-approvals without consensus. We introduce a decentralized, scaled admissibility protocol under which each validator reserves only a fraction of the available liquidity at every price. A trader obtains approval in a single round of messages with a quorum of validators. Somewhat surprisingly, despite Byzantine validators who may approve trades arbitrarily, we show that all quorum-certified trades are jointly admissible and execute within their limits. Our protocol extends naturally to a setting where buy and sell orders can be pre-approved against each other before a block is finalized.
Last updated:  2026-11-06
On Proximity Gaps for Expander Codes
Kobi Gurkan, Andrija Novakovic, and Ron D. Rothblum
Proximity gaps describe a phenomenon concerning random linear combinations of words and their distance from a linear error-correcting code. Informally, they address the following question: if a collection of words is jointly far from the code, is a random linear combination of those words likely to also remain far from the code? Motivated by applications to concretely efficient proof systems, in this note we study this question for expander codes, a class of low-density parity-check (LDPC) codes. Recent works of Goyal and Guruswami (STOC 2026) and Goyal, Guruswami, Sun, and Wootters (RANDOM 2026; arXiv 2026) establish proximity gaps approaching capacity for random LDPC ensembles, but only asymptotically and for very large degrees and field sizes, well beyond what is used in practical proof systems. We focus on general expander codes (not necessarily random) with small degree. Building on the smoothness property of expander codes due to Dinur, Sudan, and Wigderson (RANDOM 2006), we show that such codes have proximity gaps up to nearly half of the distance guaranteed by their expansion.
Last updated:  2026-11-06
SNARKs from LWE via Non-black-box Reductions
Zhengzhong Jin, Mingqi Lu, and Bo Peng
We construct the first succinct non-interactive arguments of knowledge (SNARKs) from the polynomial-hardness of Learning with Errors (LWE) for a subclass of UP languages whose witness unambiguity has a polynomial-size Extended Frege ($\mathcal{EF}$) proof. Our construction achieves the following soundness guarantee: For any fixed sequence of false instances $\{x_\lambda\}_{\lambda\in\mathbb{N}}$, there exists a (non-constructive) constant $c>0$ such that, whenever the uniform random CRS length exceeds $\lambda^c$, the construction achieves infinitely-often soundness for this sequence $\{x_\lambda\}_{\lambda\in\mathbb{N}}$: for any polynomial-time cheating prover $\{\mathcal{A}_\lambda\}_{\lambda\in\mathbb{N}}$, the probability that $\mathcal{A}_\lambda$ outputs an accepting proof for $x_\lambda$ is negligible for infinitely many $\lambda$. As intermediate results, we also obtain: - SNARGs for any NP language that has polynomial-size $\mathcal{EF}$ proofs of witness unambiguity for all instances outside of the language, based on polynomial-hard LWE, achieving the same style of soundness guarantee. - SNARKs for all true instances in any language $L \in \mathsf{UP}$ where every instance has a polynomial-size $\mathcal{EF}$ proof of witness unambiguity, under polynomial hardness of LWE, without soundness guarantees for false instances. To achieve our main result, we employ a non-black-box soundness reduction. Along the way, we introduce a new logical proof system, the \emph{Cryptographic Extended Frege} ($\mathcal{CEF}$) system, which extends $\mathcal{EF}$ with rules for formalizing the indistinguishability in cryptographic security proofs. Building on the Encrypt-hash-and-BARG framework of [Jin–Kalai–Lombardi–Vaikuntanathan, STOC’24], we further obtain SNARGs for NP languages that have $\mathcal{CEF}$ proofs of non-membership, which may be of independent interest.
Last updated:  2026-11-06
Actively Secure PIR from Verifiable Linear Relations over Rings
Louis Tremblay Thibault
Privately retrieving data from a database without revealing which element is being retrieved is a fundamental problem in cryptography with many diverse applications. State-of-the-art solutions to this problem are generally based on homomorphic encryption, which offers security only against passive adversaries. In this work, we contribute to the recently introduced notion of Verifiable Private Information Retrieval (vPIR), which leverages verifiable computation to achieve security against active adversaries. We present a new sum-check based interactive oracle proof for linear relations over power-of-two cyclotomic rings, and show how to instantiate it into a vPIR protocol using Ring-LWE. Our solution is concretely efficient, offers the best possible security guarantees and is plausibly post-quantum secure. We additionally provide an open-source Rust implementation. Our server time improves on prior work's IOP by more than an order of magnitude, leading to a factor two end-to-end performance improvement. Compared to vPIR prior work, on a 4 GiB database, our offline communication and client storage are of 128 MiB, against 3.29 GiB. Preprocessing is run once per database and amortized over an unbounded number of queries.
Last updated:  2026-11-06
The GGM PRF Construction is Optimal
Bar Alon, Itai Dinur, and Muthuramakrishnan Venkitasubramaniam
We study the complexity of fully black-box constructions of pseudorandom functions (PRFs) from pseudorandom generators (PRGs). The seminal work of Goldreich, Goldwasser, and Micali (JACM 1986), combined with Levin’s domain-extension technique, yields PRFs that make a superlogarithmic number of adaptive calls to a length-doubling PRG. A long-standing open problem is whether fewer calls suffice for fully black-box constructions. Despite progress for restricted classes of constructions and reductions, previous results have not been able to rule out even a single-call construction in full generality. A related question asks how many calls are needed to amplify a PRG’s stretch from \(r\) bits to \(\rho>r\) bits. Our main result establishes the asymptotic optimality of the GGM construction with domain compression, both in the number of calls and in adaptivity, for length-doubling PRGs. More generally, for a PRG with seed length \(n\) and stretch \(r(n)\), we rule out fully black-box PRF constructions with \(d(n)\) adaptive rounds whenever \(d(n)\log(2+r(n)/n)=O(\log n)\), even allowing polynomially many calls per round. Our bounds hold for one-bit weak PRFs on domains of superpolynomial size. In particular, they exclude all polynomial-query nonadaptive constructions from PRGs of arbitrary polynomial stretch and require superlogarithmically many rounds when the underlying PRG doubles its input length. We further show impossibility results for fully black-box non-adaptive PRG stretch amplification. First, we show that a non-adaptive construction of a $\rho$-bit stretch PRG from an $r$-bit stretch PRG requires $\Omega(\tfrac{\rho}{r+\log n})$ calls. Second, we show that it is impossible to construct a length-doubling PRG from an $o(n)$-bit stretch PRG with non-adaptive calls. Our techniques combine and extend two prior lines of work. First, we develop a sensitivity framework that measures the effect of changing a uniformly chosen oracle entry and transfers this stability through black-box reductions, extending the sensitivity arguments of Bitansky et al. (CRYPTO 2017) and Bitansky and Degwekar (TCC 2019). Second, we extend the scoring mechanism of Alon et al. (CRYPTO 2026) and integrate it with our framework. Finally, we show that the sensitivity framework applies to constructions from one-way permutations. Specifically, we show another proof of Simon's impossibility of basing collision-resistant hash functions on one-way permutations. Our new proof can be viewed as an abstraction of the argument by Bitansky and Degwekar.
Last updated:  2026-11-06
Filtered merges make deeper representation trees pay: Subset Sum and Meet-LWE
Nick Howgrave-Graham
Dubiner's bucketing codes, used as type-class filters on representation coordinates, let a merge avoid generating matched pairs with the wrong split pattern. We show that in representation trees their main effect is to make depth pay. For random density-one Subset Sum they improve the exponent of Bonnetain, Bricout, Schrottenloher and Shen from 0.2831 (our recomputation) to 0.2690, at depth 5; no better point was found up to depth 9. For May's Meet-LWE on ternary keys they improve the asymptotic exponent by 0.013–0.023 for key weights ω ≥ 0.375. Filters can pay only at merges where most matched pairs have the wrong split pattern, and do pay where such merges bind; we show both where this holds and where it fails. A survival recursion justifies the accounting, a symmetry lemma shows that the filters cannot bias the planted solution, and simulations support the remaining heuristics.
Last updated:  2026-11-06
Parallelizable modes for duplex-based authenticated encryption
Joan Daemen, Silvia Mella, and Gilles Van Assche
This note enriches the SHAKE and TurboSHAKE-based authenticated encryption schemes defined by Daemen et al. at EuroS&P 2025 with parallelizable ones, while keeping their security properties. The main contribution is a new deck cipher mode, called FlightDeck, that has the ability of processing input strings similarly to KangarooTwelve and producing output strings as in counter mode, so both parallelizable. We then instantiate FlightDeck on top of the overwrite duplex (OD) construction, in turn on top of a Keccak-p permutation. Combined with a deck cipher-based mode like Deck-BO, the security of the resulting authenticated encryption schemes reduces to the PRF security of keyed (Turbo)SHAKE and to the collision resistance of (Turbo)SHAKE. Compared to the schemes defined at EuroS&P 2025, replacing UpperDeck with FlightDeck greatly improves their software efficiency as one can implement them with Keccak-p permutations evaluated in parallel.
Last updated:  2026-11-06
Testing CCZ-equivalence to permutations via projections of Walsh zero spaces, with applications to APN functions
Emanuele Bellini
Whether almost perfect nonlinear (APN) permutations exist in even dimension $n\ge 8$ is a long-standing open question, the big APN problem. The only example known in even dimension, on six bits, was found from a quadratic APN function that is not itself a permutation, by Carlet--Charpin--Zinoviev (CCZ) equivalence. It is therefore natural to test APN functions for CCZ-equivalence to a permutation. This amounts to finding two complementary $n$-dimensional subspaces among the zeros of the Walsh transform, which lie in $\mathbb{F}_2^{2n}$. A known necessary condition only uses their projections to $\mathbb{F}_2^n$ and cannot decide every case. We give an exact test for functions whose Walsh supports are affine, including all quadratic functions. It reconstructs the subspaces from their projections, through searches for subspaces of $\mathbb{F}_2^n$ and for constrained bilinear maps. On the benchmarked functions in dimension twelve, it lists them $39$ to $55$ times faster than the generic search of the commonly used sboxU library. We then study the functions $x^3+a^{-1}\mathrm{Tr}(a^3x^9)$, which Göloğlu and Pavlů proved not to be CCZ-equivalent to permutations when $4$ divides $n$. With their result, our computations show that this holds for every even $n\le 24$. In dimension $18$ the necessary condition is satisfied, and the new test decides the case. We conjecture this for every even dimension. We also compile $25$ classes of quadratic APN functions in dimension ten from published instances, with equivalence certificates. No function in these classes or in their switching closure is CCZ-equivalent to a permutation. All code and data are public.
Last updated:  2026-11-06
More from Less: Composable General Multi-Party Computation with Global Public Verifiability from a Single Enclave Only
Saskia Bayreuther, Robin Berger, Felix Dörre, Eva Hetzel, Yufan Jiang, Christian Martin, Jeremias Mechler, and Jörn Müller-Quade
Trusted Execution Environments (TEEs), also known as secure enclaves, such as Intel SGX, Intel TDX, and AMD SEV, are seeing widespread use to perform computations on highly sensitive data. Several formal models exist to analyze the security of cryptographic protocols using TEEs, notably the one by Pass et al. (EUROCRYPT 2017) for attested computations in the Generalized UC framework. Using this model and the proposed global ideal functionality $\mathcal{G}_{\mathrm{att}}^{\mathrm{PST}}$, provably secure multi-party computations with practical efficiency are possible. Attested computations are achieved by having enclave outputs signed with a key pair held by $\mathcal{G}_{\mathrm{att}}^{\mathrm{PST}}$, together with the enclave's code. Being a global functionality, the verification key can be obtained by any party. Perhaps surprisingly, this model does not give rise to a meaningful notion of public verifiability, i. e. the ability of external parties to plausibly verify results, even though some commercially available enclaves allow exactly that. We formalize this intuition in the form of an impossibility result and propose a novel simulation technique where equivocation is not handled by the simulator resp. adversary anymore, but in a coordinated effort between our new functionality $\mathcal{G}_{\mathrm{att}}$ and a (local) ideal functionality $\mathcal{F}$ that is realized with public verifiability. To this end, several technical problems need to be solved, in particular to ensure that this new mechanism cannot be abused. While this approach is unconventional, to the best of our knowledge it is the first to achieve a general variant of public verifiability, a) even when all protocol parties are corrupted and $\mathcal{F}$ is probabilistic and, b) where guarantees of honest (external) verifiers are not affected by simulation at all. We call the latter property global public verifiability. We also address a second impossibility result of Pass et al., namely the requirement that every protocol party needs a TEE (even in a setting without public verifiability), unless an additional (global) setup is used. We address this impossibility result by introducing designated-verifier attestations that are only valid for a single party in a single protocol execution, akin to what is possible with real-world enclaves. Using our improved model, we propose protocols for (globally publicly verifiable) composable general MPC and prove their security under the notion of Universal Composition with Global Subroutines (Badertscher et al., TCC 2020) and static malicious corruptions.
Last updated:  2026-11-06
Exploring the Set of APN Functions
Jules Baudrin, Pierre Galissant, and Léo Perrin
An Almost Perfect Nonlinear (APN) function $F : \mathbb{F}_2^n \to \mathbb{F}_2^n$ provides optimal protection against differential attacks, meaning that the equation $F(x+a)=F(x)+b$ has at most 2 solutions~$x$ when $a \neq 0$. Setting aside some sporadic examples, such functions are hard to find in practice, and whether there exists APN bijections of $ \mathbb{F}_2^n$ when $n > 6$ is even (the Big APN Problem) is still unknown. In this paper, we provide the tools needed to explore the complete set of known APN functions. Indeed, for a given APN function $F$, we in fact know many: all functions CCZ-equivalent to $F$ are also APN, and so are its switching neighbours. These notions have been in the literature for many years, but several unknowns remain that complicate the exploration of the corresponding functions in practice: a given function has too many switching neighbours, and the algorithms that are known to iterate through a CCZ-equivalence class return multiple representatives per extended-affine (EA) equivalence class. We solve both problems. First, we show how to partition precisely the CCZ-equivalence class of a quadratic APN function in practice, and thus obtain exactly one representative per EA-equivalence class. To achieve this, we carefully investigate the set of the automorphisms of the graph of a quadratic APN function, and show how to generate them very efficiently using the ortho-derivative. Second, we provide the first detailed investigation of the set of the switching neighbours of a function, show in particular how an overwhelming majority of them are trivial, and explain how to get rid of those. Incidentally, we build a new extended-affine equivalence class invariant using the resulting set of non-trivial switching neighbours. For both theoretical contributions, we pushed highly-efficient and easy to re-use implementations of the corresponding algorithms to the sboxU library. It allowed us to generate databases containing all known APN functions for $n=6$ and $n=7$. For $n=8$, our algorithms are efficient-enough that we can investigate the properties of the millions of quadratic APN function recently exhibited. In the process, we generate a few thousands of new CCZ-equivalence classes. In the light of our work, the successes of the exploration strategies for $n=6$ (i.e. finding an APN function inequivalent to any monomial and quadratic mapping, and finding an APN bijection in even dimension) seems to be an artifact due to the small dimension that we show not to work for dimension 8 and which we do not expect to work either when the dimension is greater.
Last updated:  2026-11-06
More Salt, Please: A Simple Compiler for Post-Quantum Strong aPAKE
William Riccardo Duro, Sebastian Faller, Julia Hesse, and Máté Horváth
Resistance to precomputation attacks is a central security goal in password-based cryptography, as it drastically increases the runtime of brute-force attacks on breached password hashes. Strong asymmetric password-authenticated key exchange (saPAKE), which enforces such precomputation resistance, is standardized by the IRTF and deployed today at large scale. Unfortunately, no practical and easy-to-deploy saPAKE exists yet that withstands quantum attackers. Current constructions use rate-limiting tools such as oblivious pseudo-random functions (OPRFs), of which post-quantum versions are significantly more costly and complex than their discrete-log based counterparts. In this paper, we take a new approach to precomputation resistance. Starting from the compilers from PAKE to aPAKE by Gentry-MacKenzie-Ramzan (Crypto 2006) and Liu-Lyu-Han (Asiacrypt 2024), we propose a password file ratchet that adds precomputation resistance to these compilers through continuously updating the password file. The update is a simple salted hash. With a variety of practical post-quantum PAKEs at hand, this yields a ready-to-deploy post-quantum saPAKE at the trade-off of a changing server state.
Last updated:  2026-11-06
Stop Calling Them Provers: The Case for Calling ProVerif and Tamarin Symbolic Protocol Analyzers
Nadim Kobeissi
A claim that a cryptographic protocol has been proved secure depends on the theory, the analysis software, the protocol model, and the security property being checked. I examine each of these for ProVerif and Tamarin. An audit of their published soundness arguments finds false statements, missing proofs, and gaps between the procedures justified on paper and those the tools run. I also reproduce previously reported bugs that cause Tamarin to accept false claims about the submitted models. ProVerif supplies no certificate for its full analysis, while Tamarin replays its proof tree with its own solver, leaving the correctness of that code to be trusted. A correct symbolic result can still fall short of the security claim made for a protocol. Models can omit behavior in parsers and state machines; secrecy queries can allow information to leak; and equations for cryptographic primitives need justification before they support computational guarantees. Better models, stronger queries and computational soundness arguments can address these problems, but someone must establish that they apply to the protocol at hand. For these reasons and more, I argue that calling ProVerif and Tamarin "provers" is misleading: we should call them symbolic protocol analyzers and report their results with the models, assumptions and evidence that support them. They remain useful for finding attacks and establishing symbolic properties, including for unbounded sessions.
Last updated:  2026-11-06
Practical Optimal Bucket Sets with Power-of-Two Radices for LFG-Based MSM Algorithms
Guiwen Luo
Fixed point multi-scalar multiplication (MSM) is a major computational component of pairing-based SNARK proof generation. The Luo--Fu--Gong (LFG) framework is a variant of Pippenger's bucket method that uses a multiplier set $M$ and precomputed point multiples to reduce the number of buckets and online point additions. For radix $q$ and a positive multiplier set $M$, covering all digit residues requires a bucket set of size at least $q/(2|M|)$. Previous constructions approaching this bound based on primitive roots or power-residue classes impose radix restrictions that exclude $q=2^c$, thereby requiring additional binary-to-radix conversion in software implementations. We present two main bucket set constructions for power-of-two radices $q=2^c$, using the multiplier sets $M=\{1,2,3\}$ and $M=\{1,3\}$, respectively. Their cardinalities are $q/6+O(\log q)$ and $q/4+2$, respectively, so both asymptotically attain the counting bound $q/(2|M|)$ while allowing efficient radix-digit extraction through shifts and masks. We further give two generalizations. Using consecutive powers of $3$ as multipliers yields bucket sets of size $q/(2\ell)+O(\log q)$ for every fixed positive integer $\ell$. For $\ell=2^d$ and $c\ge d+2$, consecutive odd multipliers yield bucket sets of size $q/(2\ell)+d+1$. We also present scalar conversion and two strategies for handling the leading digit, allowing the bucket set constructions to be used within the LFG framework.
Last updated:  2026-11-06
MuCPay: Breaking the Quadratic Bottleneck in Scriptless Multi-Party Oracle-Based Conditional Payments
Yaning Wang, Na Wang, Chuan Li, Yongda Zhang, and Junsong Fu
Oracle-based conditional payments triggered by real-world events support decentralized finance applications. However, dense independent bilateral deployments require $\Theta(Nn^2)$ outcome authorizations and $\Theta(n^2)$ settlement signatures for $n$ parties and $N$ outcomes. To go beyond two-party settings, we propose MuCPay, a multi-party oracle-based conditional payment protocol combining (i) $\Theta(Nn)$ off-chain signing shares with one on-chain settlement signature and (ii) BIP340-compatible scriptless settlement on Bitcoin. At its core, MuCPay introduces hash-bound adaptor multi-signatures (HB-AMS) that aggregate parties' conditional authorizations into a compact joint pre-signature. Its single-nonce structure and hash-bound adaptor integration enable efficient multi-party pre-signing. Unlike Double-Layer AMS (EuroS&P'26), HB-AMS produces a standard BIP340 signature under an aggregate public key, enabling direct Taproot key-path settlement. Under static corruption with one honest signer, we prove concurrent new-message unforgeability (CUF) and early-settlement resistance (ES) under our stated algebraic random-oracle model. For 128 parties and 16 outcomes, median complete local preparation takes 2.093 s. For protocol preparation (1.862 s for MuCPay), native-profile projections place VweTS (NDSS’23) and ParaSwap (USENIX’25) work at 1.67 × 10⁴ and 5.05 × 10⁵ times MuCPay's, respectively. Settlement uses one 64-byte signature, while the modeled independent-DLC deployment requires 281.5× as many transaction vbytes. These results demonstrate practical, scalable multi-party oracle-based conditional payments.
Last updated:  2026-11-06
Applying Combinatorial Techniques To Find Minimal Non-Complete Set Coverings
Enrico Piccione and Jan Vorloeper
One of the most prominent hardware countermeasures against side-channel attacks are threshold implementations (TIs). The technique uses masking to split the operations in a cryptographic algorithm into several ones operating on shares. The coverage and non-completeness requirements of TIs are mathematically described by the notion of non-complete set coverings (NCSCs). Importantly, the number of members inside an NCSC determines the number of output shares and therefore directly impacts the complexity of the resulting TI. In this work, we derive new lower bounds on the minimal number of members of NCSCs and obtain new upper bounds by explicit constructions. We present a group-theoretic construction of balanced NCSCs, in which the numbers of input and output shares coincide, together with a search algorithm based on intersections of group translates. Our methods determine the smallest balanced coverings in two previously unresolved cases and yield exact minima and classifications of optimal coverings for an infinite family of parameters. These results resolve all four explicit open problems posed by Farr\`as, Fidalgo and Lara-Nino.
Last updated:  2026-11-06
Exploiting Matrix-Vector Multiplication in AIMer: Single-Trace Attacks on Key Generation and Signing
Süleyman Emir Akın, Abdullah Talayhan, and Özcan Öztürk
This paper presents two side-channel attacks against AIMer v3.0, one of the two signature schemes selected in the Korean Post-Quantum Cryptography (KpqC) competition. Both are single-trace attacks that recover the full secret key without a profiling phase, one against key generation and one against signing. Both target the same routine: the matrix-vector multiplication invoked by either phase expands each bit of its secret operand into an all-zero or an all-one mask, which then gates the accumulation of the corresponding public matrix row. A single execution therefore leaks one distinguishable segment per secret bit. What makes the attacks non-profiled is that each attacked trace carries its own labelled training set. During key generation, creating the dense invertible public matrices invokes the matrix-vector multiplication routine hundreds of times, on operands that are public. In signing the same derivation takes place, and in addition the signature itself opens all but one of the $N$ parties of every repetition, so the bits of nearly every multiplication in the trace are public. In both attacks we use a supervised classifier to recover the unknown value. In key generation that value is the private key itself, whereas in signing there are three distinct routes to it: the key itself, a party's share of the key, and a party's share of an S-box output. Recovering any one of them is enough to recover the private key. We validate both attacks on an ARM Cortex-M4: one trace recovers the exact secret key from every capture we took, $100$ key generations for each of AES-128, AES-192 and AES-256, and $100$ signatures for each of AES-128f, AES-192f and AES-256f. We also discuss possible countermeasures.
Last updated:  2026-11-06
Fully Homomorphic Encryption: A Mathematical Introduction
Sara Logsdon
We provide a mathematical introduction to fully homomorphic encryption (FHE), which enables computations to be performed on encrypted data without requiring decryption. We begin with a brief overview of the historical development of FHE, then focus on Fully Homomorphic Encryption over the Torus (TFHE), describing its underlying mathematical structure and fundamental homomorphic operations. Particular attention is given to key switching and bootstrapping, including their roles in managing ciphertext noise and supporting computations of greater depth. Our aim is to provide an accessible mathematical foundation for understanding the mechanisms underlying TFHE and their significance in the development of practical fully homomorphic encryption.
Last updated:  2026-11-06
BeaverDam: A Post-Quantum Threshold Key Recovery Protocol from a One-Time Threshold Oblivious Random Function
Benedikt Auerbach, Shuichi Katsumata, Kaoru Takemure, and Ida Tucker
Secure backups are a practical necessity of E2EE messaging apps, typically relying on password-protected key-recovery (PPKR) protocols. These allow users to turn a human-memorable password into a cryptographic key with the help of a server. Recently, Signal and Juicebox proposed threshold PPKR (tPPKR) protocols, removing the trust on a centralized server. Unfortunately, known solutions are only classically secure, lagging behind the shift toward post-quantum (PQ), or to be more precise, hybrid secure E2EE. We present BeaverDam, a novel tPPKR protocol that is PQ secure with efficiency close to existing classical protocols. It also easily extends to hybrid security, standing as the first concretely efficient hybrid-secure tPPKR protocol. BeaverDam relies on a new primitive we introduce --- one-time threshold oblivious random functions (tORF). Unlike full-fledged OPRFs, which are notoriously difficult to construct in a PQ-secure manner, one-time tORF offers weaker but sufficient security guarantees tailored to the tPPKR setting. We then construct an efficient one-time tORF called Beaver, inspired by multi-party computation (MPC) techniques. Owing to the one-time feature, we only need to securely compute a 2-wise independent hash function, making our protocol very efficient. We conclude by presenting a practical instantiation of BeaverDam and comparing its performance to state-of-the-art classical tPPKR protocols, namely Signal's SVR3 and Juicebox.
Last updated:  2026-11-06
Weights Come Almost for Free in Ramp Threshold Cryptography
Aarushi Goel and Mingyuan Wang
A weighted threshold access structure assigns a weight to each party and authorizes a subset of parties whenever their total weight exceeds a prescribed threshold. Most existing approaches to designing multiparty cryptographic protocols in the weighted threshold setting, however, either incur complexity that grows with the total weight assigned to the parties or remain far from concretely efficient. Toward \emph{concretely efficient} weighted threshold primitives, we take a different route and relax to the \emph{ramp} setting, in which two thresholds are prescribed: a subset whose total weight falls below an $\alpha$ fraction of the total is unauthorized, while a subset whose total weight exceeds a $\beta$ fraction is authorized. Exploiting the gap between these two thresholds, we obtain the following results. 1. Given any weighted ramp threshold access structure with privacy threshold $\alpha$ and reconstruction threshold $\beta$, where $0\!<\!\alpha\!<\!\beta\!<\!1$, we present a weight compression technique that reduces the total weight to $\approx n/(2(\beta-\alpha))$ while preserving the authorized and unauthorized sets. Combined with the standard player-virtualization paradigm, this yields concretely efficient weighted threshold cryptographic protocols with only a multiplicative overhead of $\approx 1/(2(\beta-\alpha))$ over their unweighted counterparts. Previously, the best known compression technique in this setting, due to Benhamouda et al.~[ITC'23], achieved total weight $\approx 5n/(\beta-\alpha)$. 2. Player virtualization has an inherent drawback: a party's share size and workload grow in proportion to its (compressed) weight, so the parties in which the most trust is placed also bear the largest computational and communication costs. Thus, although the \emph{overall} overhead is $O(1)$, the cost borne by a single party can still be $O(n)$ times that in the unweighted setting. Our second result removes this imbalance. Building on our compression technique, we construct a linear secret-sharing scheme in which every party receives a share of size $\widetilde{O}(1)$, independent of its weight, for a total share size of $\widetilde{O}(n)$, nearly matching the $O(n)$ complexity of standard unweighted threshold secret sharing.
Last updated:  2026-11-06
Weighted Cryptography with Weight-Independent Complexity
Aarushi Goel, Swagata Sasmal, and Mingyuan Wang
Cryptographic primitives involving multiple participants, such as secure multiparty computation (MPC), threshold signatures, and threshold encryption, are typically designed under the assumption that at least a threshold number of participants remain honest and non-colluding. However, many real-world applications require more expressive access structures beyond simple thresholds. A prominent example is the weighted threshold access structure, where each party is assigned a weight and security holds as long as the total weight of corrupted parties does not exceed a specified threshold. Despite the practical relevance of such access structures, our understanding of efficient constructions supporting them remains limited. For instance, existing approaches for weighted MPC and weighted threshold encryption incur costs that scale with the total assigned weights to all parties or rely on non-black-box use of cryptography. In this work, we present the first black-box constructions of the following weighted cryptosystems with weight-independent complexity in the trusted setup model: (i) a weighted MPC protocol with guaranteed output delivery, (ii) a semi-honest weighted threshold encryption scheme and (iii) a semi-honest weighted threshold Schnorr signature scheme. At the heart of our constructions is a new succinct computational secret sharing scheme with linear homomorphism for weighted threshold access structures. We provide two concrete instantiations of this primitive, based on the Decisional Composite Residuosity (DCR) assumption and the Learning With Errors (LWE) assumption, respectively. Furthermore, our constructions extend to any general access structure that can be represented efficiently as a monotone Boolean circuit.
Last updated:  2026-11-05
New Results in Adaptively-Secure Broadcast Encryption and Succinct Computational Secret Sharing from Standard Lattices
Rishab Goyal and Saikumar Yadugiri
Projective pseudorandom generators (PPRGs), introduced by [Applebaum et al.; STOC'23], expand a short seed into a long pseudorandom string, with a special feature that one can generate a short $\textit{projected}$ key, for any set $S$, such that it reveals the output bits in $S$ while preserving pseudorandomness of the remaining bits. They demonstrated that PPRGs can bypass the 'representation size barrier' in computational secret sharing schemes, and designed PPRGs assuming hardness of a variety of standard cryptographic assumptions. Later, [Hsieh, Waters, and Wu; EUROCRYPT'25] showed that PPRGs can also be used to design adaptively-secure broadcast encryption in the standard model, without relying on unprovable heuristics. In this work, we design succinct computational secret sharing schemes for graph access structures and adaptively-secure flexible broadcast encryption in the standard model, both with optimal parameters. The main driver for both our results is a new construction of a compact programmable pseudorandom set sampler (PPS), introduced by [Goyal and Yadugiri; CRYPTO'26], from standard Learning with Errors (LWE) assumption [Regev; STOC'05]. We show that PPS generically imply PPRGs with many useful properties and, moreover, by replacing PPRGs with PPS we can achieve full succinctness in the underlying applications to secret sharing and adaptive security compilers for broadcast encryption. This yields the $\textit{first}$ flexible broadcast encryption scheme in the standard model from $\textit{any}$ falsifiable assumption with fully compact ciphertext size, and a succinct computational secret sharing for evolving graph access structures with optimal share size from standard LWE.
Last updated:  2026-11-05
Vector Commit-and-Reduce Schemes
Anubhav Baweja, Pratyush Mishra, Tushar Mopuri, and Bharath Namboothiry
Hash-based argument systems are seeing increasing adoption in practice, owing to their ease of deployment, fast provers, and plausible post-quantum security. However, they still lag behind elliptic-curve counterparts due to their large proof sizes and (comparatively more) expensive verifiers. Attempts to optimize these metrics have focused on one of the two ingredients underlying these arguments, namely Interactive Oracle Reductions, leaving the other ingredient, Vector Commitments (VC) schemes largely ignored. This is in part because Merkle trees are the best known hash-based VC scheme to date. To make progress on this front, we introduce Vector Commit-and-Reduce (VCR) schemes. These generalize VC schemes by allowing both the commitment and opening algorithms to be interactive protocols, and moreover by allowing the opening algorithm to be a reduction instead of an argument. By requiring VCR schemes to satisfy strong round-by-round knowledge soundness notions, we show how they can be used to construct hash-based reductions from IORs. Our transformation extends prior work which used (non-interactive) VC schemes. We also provide a construction of a VCR scheme, Canopy, that greatly reduces proof size and verifier time by reducing the vector opening claims to proximity claims about certain (committed) codewords. This latter feature enables us to use a wide variety of techniques for proving, batching, and accumulating these claims, and indeed we use these to obtain both concrete and asymptotic improvements for hash-based arguments and reductions. For SNARKs based on the Bolt code [CRYPTO 2026], we reduce proof sizes by 50\% and verifier hashes by $3\times$ with only a 5-15$\%$ prover overhead. For SNARKs based on the Reed-Solomon code, we reduce proof sizes by 20$\%$, and verifier hashes by $1.5\times$ with only a 20$\%$ prover overhead. We also construct hash-based Proof-Carrying Data where the recursion overhead is $O(\lambda \sqrt{\log N})$ hashes; in comparison, the state-of-the-art requires $\Omega(\lambda {\log N})$ hashes.
Last updated:  2026-11-05
How to Trace Viral Content in End-to-End Encrypted Messaging
Pedro Branco, Matthew Green, Aditya Hegde, Abhishek Jain, and Gabriel Kaptchuk
We study the problem of combating *viral* misinformation campaigns in end-to-end encrypted (E2EE) messaging systems such as WhatsApp. We propose a new notion of Hop Tracking Signatures (HTS) that allows for tracing originators of messages that have been propagated on long forwarding paths (i.e., gone viral), while preserving anonymity of everyone else. We define security for HTS against malicious servers. We present both negative and positive results for HTS: on the one hand, we show that HTS does not admit succinct constructions if tracing and anonymity thresholds differ by exactly one "hop". On the other hand, by allowing for a larger gap between tracing and anonymity thresholds, we can build succinct HTS schemes where the signature size does not grow with the forwarding path. Our positive result relies on streaming algorithms and strong cryptographic assumptions. Prior works on tracing within E2EE messaging systems either do not achieve security against malicious servers or focus only on tracing originators of pre-defined banned content.
Last updated:  2026-11-05
SETH: Subcode Equivalence in the Head
Marco Baldi, Michele Battagliola, Rahmi El Mechri, Laura Mattiuz, Marco Rinaudo, Paolo Santini, Riccardo Schiavoni, and Edoardo Signorini
The Multi-Party Computation in the Head (MPCitH) paradigm has proven to be a versatile tool to design post-quantum digital signature schemes. Recently, MPCitH was improved with Threshold Computation in the Head (TCitH) and Vector Oblivious Linear Evaluation in the Head (VOLEitH). In this paper, we propose two polynomial models for the Subcode Equivalence Problem (SEP) and derive TCitH and VOLEitH signatures from them. The resulting scheme has better performance when compared to other SEP-based signature schemes and also features shorter signatures when compared to other schemes based on similar assumptions.
Last updated:  2026-11-05
Flying, Not Floating: Precise Fixed-Point Falcon on Embedded Processors
Stef Halmans, Amit Kumar, and Tim Güneysu
The Falcon digital signature scheme, under standardization as FN-DSA, requires real-number arithmetic during signing, with its security dependent on numerical precision. Recently, De Almeida Braga et al. (CRYPTO 2026) showed that Falcon-512 can sign in 64.64 fixed-point arithmetic on 64-bit hosts. In this work, we present the first fixed-point FN-DSA signer for microcontrollers, using 32.64 arithmetic in constant-time Cortex-M4 assembly for Falcon-512 and Falcon-1024. Although a straightforward fixed-point implementation is less precise than double precision, our new techniques successfully restore precision. They keep reciprocals, inverse square roots and small constants wide and round once at the consumer. We evaluate them with known techniques on both arithmetics and both degrees. Our signer needs around $45\%$ fewer cycles than double-precision emulation for Falcon-512 Falcon-1024, and its measured precision supports $2^{99.7}$ $2^{96.7}$ queries per key, against $2^{61.5}$ $2^{58.7}$ for double precision and the target of $2^{64}$. Our $12$-byte words raise signing RAM from $59n$ to $83n$ bytes. We also show which implementation choices lift double-precision c-fn-dsa above $2^{64}$ while making it faster. We derive key generation bounds for Falcon-1024, accepting $72.3\%$ of keys where the Falcon-512 values accept $8.5\%$, and provide recommendations for the fixed-point FN-DSA that NIST plans.
Last updated:  2026-11-05
Revisiting Linkable Ring Signatures with Logarithmic Verification Complexity
Danai Balla and Pyrros Chaidos
Ring Signatures allow a user to sign on behalf of an ad-hoc set of public keys, while hiding their identity inside that set. Linkable Ring Signatures (LRS) add the functionality of detecting signatures originating from the same signer. They have found many applications in anonymous transactions and e-voting. The LLRing family of linkable ring signature schemes by Hui and Chau (ESORICS 2024) is one of the more efficient LRS schemes. However, we show that it has an unlinkability vulnerability, meaning an adversary can create more unlinkable signatures than the number of secret keys they own. The vulnerability is caused by the introduction of unwanted structure to base elements used in proofs. We also find a similar attack against the Threshold Ring Referral (TRR) scheme of Ta, Hui, and Chau (Security and Privacy 2025), rendering it unsound. We show how to achieve strong linkability with logarithmic verification complexity in the pairing based setting by first reverting the unsafe construction of base elements, and by also adjusting the arguments of knowledge used in order to maintain efficiency. We separate the design and analysis of the scheme from the instantiation of the knowledge arguments, which helps prevent unwanted interactions between the two, and can provide easier upgrades to more efficient proof systems.
Last updated:  2026-11-05
Hidden Curves and Short Duals: Cubic Jets, Dual Leaks, and the Limits of Masked-Code Encryption
Yongge Wang
Masked-code encryption hides a decodable code behind a transformation meant to make it look random. We study the two masks proposed as compact alternatives to Goppa codes---Wang's RLCE and the $(U\,|\,U{+}V)$ construction of UVW-KEM---over the decodable hidden codes they have been or could be applied to, and find that, among the families examined, none yields a compact trapdoor. Over Reed--Solomon and algebraic-geometry codes the mask hides a \emph{curve}, and curves are not hidden from jets. We explain the October 2026 key recovery of UVW-KEM (NGCC) and show it is not specific to UVW: for \emph{hidden-pairing codes} we bound from below the dependencies among order-$r$ jets of degree-$d$ forms at the columns of any shortening---for cubics $2k_1-k_2-k_l+2$ (UVW) and $2(n{-}k)-w-k_l+2$ (RLCE), attained in every regime tested, and we prove that the structured part of the dependency space carries the pairing and the secret ratios in closed form. Every proposed UVW parameter set has the predicted cubic deficiency (key recovery has been demonstrated at UVW-KEM-128). RLCE's long-key regime $w\ge n-k$, out of reach of the square-code attack for eight years, falls at degree three: on a full-size Level-1 parameter set we recover an equivalent key from the public key alone and decrypt fresh ciphertexts. HermitianRLCE is distinguished the same way. A forcing law, a master count and a redundancy law make the \emph{jet degree} an invariant of hidden-pairing codes: within that model, each unit of structural depth costs a unit of redundancy. Without a curve the masks fail differently: both \emph{preserve the dual} of the hidden code, at most doubling the weight of every dual word. polarRLCE at rate $\le2/3$ leaks dual words found in $47$--$94$ bits; at higher rates no certified decoding radius supports $143$-bit security up to length $16384$, and at $32768$ the key is $58$\,MiB, $234\times$ Classic McEliece. LDPC codes leak their sparse checks, MDPC codes are better left unmasked, and UVW carries a matched-pair subspace for every hidden code. Reed--Muller-heavy codes under RLCE resist every attack here at $4$\,MiB keys, but only if a decoder at $3.4\times$ the bounded-distance radius exists.
Last updated:  2026-11-05
Complete Fairness in Secure Two-party Computation from Quantum One-Wayness
Arpita Maitra, Goutam Paul, Asim K. Pal, Asmita Samanta, and Hridam Basu
In 1997, Mayers, and Lo and Chau, in their papers proved that if one of the parties is malicious, it is not possible to achieve unconditional security in quantum bit-commitment (Phy. Rev. Lett, 1997). Moreover, Lo showed that it is not possible to achieve unconditional security in two-party quantum computation (Phy. Rev. A, 1997). However, restricting the computational power of the adversary, via assumptions like the existence of one-wayness, it has been shown that secure quantum bit-commitment is indeed possible by Dumais, Mayers, and Salvail (EUROCRYPT 2000). In their paper, they showed that with the assumption of a one-way permutation that is secure against any polynomial-time quantum adversary, one can achieve a secure quantum bit-commitment scheme. Although security is guaranteed, complete fairness remains an issue in quantum two-party computation for the real-world framework. In this paper, we show for the first time that secure two-party quantum computation with complete fairness is achievable for the same class of functions as studied by Gordon, Hazay, Katz, and Lindell (STOC 2008) in the classical domain. This seems to stand in sharp contrast to the impossibility result of Ben-Or, Crepeau, Gottesman, Hassidim, and Smith (FOCS 2006). However, they considered a malicious quantum adversary with unconditional computational power and used a broadcast channel. On the other hand, we use the hybrid model idea of Gordon, Hazay, Katz, and Lindell with a non-simultaneous channel and the idea of composition by Ran Canetti (Journal of Cryptology, 2000) to achieve complete fairness in the quantum domain, under the assumption of a computationally bounded adversary. At first, we design secure two-party computation protocols in a hybrid model, using a trusted third party. Then we prove how these protocols achieve complete fairness in the hybrid model. Finally, we construct a secure two-party communication protocol and show how we can use this to remove the trusted third party of the hybrid model and achieve both security and complete fairness in the real-world model. In this context, we devise a zero-knowledge proof and use it as an important tool in our protocol.
Last updated:  2026-11-05
Symbolic forward secrecy analysis of ML-KEM
Varsha Jarali and Shashi Kant Pandey
Post-quantum Key Encapsulation Mechanisms (KEMs) rely on generic transformations to achieve active security. Specifically, ML-KEM (FIPS 203) applies the Fujisaki--Okamoto (FO) transform to a lattice-based public-key encryption scheme, Kyber.CPAPKE, to construct an IND-CCA2 secure key exchange protocol, ML-KEM. While NIST standards and associated special publications discuss guidelines for establishing larger shared keying material using ML-KEM, formal symbolic proofs to evaluate these operational setups remain sparse. This work addresses this gap by conducting a formal symbolic analysis of ML-KEM using \textsf{ProVerif}. First, we verify the core primitive, establishing symbolic proofs for session key confidentiality, key agreement soundness, and Fujisaki--Okamoto implicit rejection fallback secrecy. Second, we examine the temporal security guarantees of ML-KEM under long-term static key leakage. Using \textsf{ProVerif}'s global phase constructs, we demonstrate that standalone static ML-KEM does not preserve Perfect Forward Secrecy (PFS), rendering repeated static encapsulation for additional key share establishment vulnerable to retroactive decapsulation. Lastly, we formally model and verify that deploying ML-KEM with ephemeral key rotation or ratcheting mechanisms mitigates this vulnerability, providing robust forward secrecy and complete session domain separation.
Last updated:  2026-11-05
The Authentication Complexity of Byzantine Consensus
Kecheng Shi
Byzantine broadcast and Byzantine agreement are fundamental problems in distributed computing and building blocks for secure multiparty computation. In complete synchronous networks of $n$ parties with channels identifying the immediate sender, classical results establish how authentication changes resilience to $t$ Byzantine faults. Without initially authenticated public keys, both tasks are possible if and only if $n>3t$~\cite{PSL80}. With a complete public-key infrastructure (PKI), broadcast tolerates every $t<n$~\cite{DS83}, and agreement is possible if and only if $n>2t$. These thresholds leave a substantial gap: \emph{how much initial authentication is necessary for a given fault bound, and how does its distribution affect feasibility?} We study this question by allowing each party's designated public verification key to be initially authenticated to any subset of the other parties. We represent this setup by a directed authentication graph $G$ whose vertices are parties, with an edge $x\to y$ exactly when $y$ is a \emph{verifier} of $x$: that is, $x$'s designated public verification key is initially authenticated to $y$. We count each edge as one unit and define \emph{authentication complexity} as the \emph{minimum} total bindings over all setups and protocols achieving the required task and fault tolerance. Protocols may establish further authentication during execution without adding initial cost. We give a tight graph characterization of the initial authentication setups that support agreement, including when each party knows only its own initial key table and is not given the authentication graph. For $2t<n\le3t$ and $r=n-2t$, we show that agreement has authentication complexity $\Theta(\min\{n^2,(n^2/r)\ln(en/r)\})$ and give a protocol with polynomial local computation. At $n=2t+1$, broadcast requires $\Omega(n\ln^2 n/\ln\ln n)$ initial authentications, and has a construction using $O(n^{3/2}\sqrt{\ln n})$ initial authentications. At this threshold, we also show a complete PKI setup is necessary for agreement. Surprisingly, broadcast has subquadratic authentication complexity even when $t=n/2+o(n)$. For every fixed fault fraction $\alpha\in(1/2,1)$, we show its authentication complexity is $\Theta_\alpha(n^2)$. We also determine the exact authentication complexity of broadcast at maximum resilience: $\binom n2-1$ initial authentications suffice and are necessary to tolerate $t=n-1$ faults.
Last updated:  2026-11-05
Quantum Key Exchange from Public Quantum Money
Eli Goldin and Tomoyuki Morimae
Two-message quantum key exchange (2QKE) cannot be realized in a statistically secure way, and therefore some computational assumptions are required [Malavolta and Walter 2024]. So far, the known weakest assumption for 2QKE is the existence of one-way functions (OWFs): Malavolta and Walter constructed (even everlasting-secure) 2QKE from OWFs [Malavolta and Walter 2024], and Kitagawa, Morimae, Nishimaki, and Yamakawa constructed quantum public-key encryption (QPKE) with quantum public keys, which implies 2QKE, from OWFs [Kitagawa, Morimae, Nishimaki and Yamakawa 2024]. Can we construct 2QKE from a weaker assumption than OWFs? In this paper, we give the first complete characterization of 2QKE. We show that the following four primitives are (existentially) equivalent: everlasting-secure 2QKE, standard 2QKE, efficiently-verifiable state puzzles (EV-StatePuzzs), and one-time secure digital signatures with quantum signatures and signing keys. Because EV-StatePuzzs are potentially weaker than OWFs [Kretschmer, Qian and Tal 2025], the equivalence implies that 2QKE are potentially weaker than OWFs. Moreover, our result shows the equivalence between standard 2QKE and everlasting-secure 2QKE, which means that everlasting security comes for free. Finally, one-shot signatures, quantum lightning, and public-key quantum money mini-schemes imply EV-StatePuzzs, and therefore, our result also gives a new lowerbound, namely everlasting-secure 2QKE, of these public-key unclonable primitives. We also show that one-shot signatures imply QPKE with quantum public keys [Kitagawa, Morimae, Nishimaki and Yamakawa, 2024] constructed QPKE with quantum public keys from OWFs, and it was open whether QPKE with quantum public keys can be constructed from an assumption weaker than or incomparable to OWFs. Our result gives a potential answer to this question since one-shot signatures seem to be incomparable with OWFs. Moreover, QPKE constructed from one-shot signatures has an additional functionality, which we call certified freeze, that allows the receiver to publish a publicly verifiable classical certificate that computationally binds the receiver to an upper bound on the total number of distinct valid ciphertexts under its verification key.
Last updated:  2026-11-05
Optimal Early-Stopping Broadcast via Exponential Information Gathering
Giovanni Deligios, Fatima Elsheimy, Simon Holmgaard Kamp, Ivana Klasovita, Chen-Da Liu-Zhang, Julian Loss, and Charalampos Papamanthou
Early-stopping broadcast protocols guarantee termination based on the actual number of malicious parties, $f \leq t$, encountered during execution, rather than the worst-case scenario of $t < n$ corruptions. The seminal work of Dolev, Reischuk, and Strong~[JACM'90] established that $\min\{f+2,\, t+1\}$ rounds are necessary. The influential works of Berman, Garay, and Perry~[WDAG'92] and Abraham and Dolev~[STOC'15] introduced the first protocols achieving this optimal bound in the $t < n/3$ (unconditional, no setup) regime, while Perry and Toueg~[Tech.\ Report'84] gave the first protocol for the $t < n/2$ setting (with plain PKI), achieving $2 \cdot \min\{f+2,\, t+1\}$ rounds. Despite this early progress, closing the gap to the optimal bound in the computational setting has remained a longstanding open problem, and only recently has progress been made. The best known result in the $t < n/2$ regime is due to Elsheimy, Loss, and Papamanthou~[Eprint'25], achieving $f + O(\sqrt{f})$ rounds. In the dishonest-majority regime, the best known result is due to Deligios, Klasovita, and Liu-Zhang~[Eurocrypt'25], who obtain the first asymptotically optimal protocol, with $O(f)$ round complexity, for $t = (1-\epsilon)n$, where $\epsilon > 0$ is a constant. In this work, we advance the state of the art in two directions. First, in the $t < n/2$ setting with plain PKI, we present a broadcast protocol in which all parties output within optimal $\min\{f+2,\, t+1\}$ rounds. Second, we complete the picture by introducing the first protocol that is optimally resilient ($t < n$) and asymptotically matches the lower bound for any number of corruptions $t < n$. By leveraging exponential information gathering (EIG) graphs, our constructions establish that these round bounds are achievable, providing the first feasibility result for optimal-round protocols, albeit at the cost of exponential communication complexity.
Last updated:  2026-11-05
Privacy-Preserving Multi-Institutional Clinical Prediction via Multiparty Encrypted Newton-CG Logistic Regression
Xiaokang Dai, Weijie Miao, Wenyuan Wu, and Yong Feng
Multi-institutional clinical prediction can benefit from larger and more diverse patient populations, but privacy and data-governance constraints often prevent pooling patient-level records. This study aims to enable collaborative logistic-regression training while keeping such records local. We developed a framework combining multiparty Cheon–Kim–Kim–Song (CKKS) homomorphic encryption with Newton–conjugate gradient optimization. Each institution computes local gradient and damped Hessian contributions, while only encrypted fixed-dimensional statistics are aggregated. The global Newton system is solved by encrypted preconditioned conjugate gradient with diagonal preconditioning and delayed division, making the dominant homomorphic cost depend mainly on model dimension. We evaluated the framework on nine clinical-prediction tasks from NHANES 2017–2018 and on the PIMA Diabetes and Breast Cancer Wisconsin datasets. Across the nine NHANES tasks, mean absolute deviations from pooled-data plaintext Newton training were below 0.002 for area under the receiver operating characteristic curve, area under the precision–recall curve, and average precision. Five-fold cross-validation accuracy was (77.21 ± 1.28)% on PIMA Diabetes and (96.42 ± 1.44)% on Breast Cancer Wisconsin. Under a common 20-iteration budget, the proposed method achieved approximately 3.85× faster training and nearly 90% lower peak memory use than a reproduced multiparty encrypted first-order baseline, while attaining a lower final relative gradient and closer agreement with plaintext Newton. These results show that exploiting locally computed Newton statistics can preserve predictive utility while substantially reducing encrypted training cost, supporting privacy-preserving multi-institutional clinical prediction without pooling patient-level data.
Last updated:  2026-11-05
Rotom: A Microcontroller-Oriented Tweakable Block Cipher Using Modular Multiplication (Full Version)
Kento Morita, Kazuhiko Minematsu, Kosei Sakamoto, Kazuma Taka, Rei Ueno, and Takanori Isobe
We propose Rotom, a family of 128-bit tweakable block ciphers designed for efficient software implementation on 32-bit microcontrollers. The central design idea is to use modular multiplication as a compact and software-efficient source of strong nonlinearity. Rotom instantiates this idea with a fixed 16-bit S-box built from odd constant multiplication modulo $2^{16}$ interleaved with lightweight linear maps, and combines it with a software-friendly recursive linear layer over four 32-bit words, a compact tweakey schedule, and modular-addition boundary key mixing. In contrast to typical ARX-based ciphers, Rotom provides explicit differential and linear characteristic bounds by design. These bounds are obtained by exhaustively computing the local transition probabilities of its fixed 16-bit S-box and combining them with active-S-box bounds induced by its recursive linear layer. Implementation results on ARM Cortex-M3 and Cortex-M4 show that Rotom achieves cycle counts close to Speck, substantially lower than those of MSX, and faster than representative fixsliced AES implementations, while providing tweak support and cipher-level differential and linear bounds. Overall, Rotom combines the efficiency of software-oriented arithmetic instructions with the explicit security evaluation enabled by a fixed-S-box structure.
Last updated:  2026-11-05
Bridging Correlation Measures and Unpredictability: Sharp Bounds and Insights for TRNG Validation
Maciej Skorski and Onur Günlü
Do small correlations certify high unpredictability? We answer this for the high-order correlation measures (Mauduit and Sárközy) and finite-memory sources. We develop minimax sharp bounds on next-bit prediction from high-order correlations and show that the min-entropy-rate deficit is linear in the largest correlation, with optimal first-order constants. We also bridge population and sample correlations through ergodic limits and finite-sample guarantees. As an application, we show that the validation method for true random number generators recently proposed at WAIFI 2026 over-rejects: shrinking (sub-constant) thresholds strongly reject sources of nearly full entropy.
Last updated:  2026-11-05
LAMP: Linear Verification of Matrix Multiplication via Proximity Testing
Kyeongtae Lee, Byeongkyu Han, Jihye Kim, and Hyunok Oh
Verifiable computation systems often need to prove large matrix multiplication statements, but a direct SNARK arithmetization of a \(k \times k\) product requires \(\mathcal{O}(k^3)\) constraints. Freivalds' randomized check reduces the algebraic computation to vector-matrix products, but proving those products inside a SNARK still costs \(\mathcal{O}(k^2)\) constraints. We present LAMP, a matrix-multiplication checking protocol that combines Freivalds' randomized check with proximity testing over linear error-correcting codes. The prover commits to encoded matrices and intermediate vectors before the sampled query positions are derived. The CP-SNARK circuit then checks only the sampled codeword positions and commits to the values used inside the circuit, while Merkle openings and CP-Link proofs ensure consistency between the in-circuit witnesses and the externally committed values. We prove soundness for this committed-input setting under the soundness of the SNARK backend, the binding of the commitments, the correctness of the CP-Link checks, and the relative distance and unique-decoding radius of the Reed--Solomon code. For a fixed number \(t\) of sampled positions, the main in-circuit SNARK relation has \(\mathcal{O}(tk+E_{\mathsf{code}})\) constraints, with additional \(\mathcal{O}(t\log n)+E_{\mathsf{link}}(k,t)\) backend work for Merkle openings and CP-Link checks. We implement LAMP in Go and compare it with a Freivalds-based SNARK circuit. In the matrix benchmark at \(k=2^{12}\), LAMP reduces the constraint count by \(9.68\times\) and shortens proof generation time by \(5.81\times\); verification remains approximately \(0.13\,\text{s}\) across the measured range.
Last updated:  2026-11-05
Bounded Information: PAC Certification of Multivariate Side-Channel Traces
Kuheli Pratihar, Nimish Mishra, and Debdeep Mukhopadhyay
Side-channel leakage certification aims to quantify what an attacker can learn about a secret variable from observed leakage. Existing information-theoretic estimators, such as perceived information (PI), hypothetical information (HI), and nonparametric mutual information (MI), aim to quantify distributional leakage, but they become unstable in high-dimensional traces and do not provide a finite-sample certificate of the best attacker. We introduce \emph{Bounded Information} (BI), a probably approximately correct (PAC)-style finite-sample certification method that upper-bounds the exact-recovery success of a fixed attacker scope on unseen traces. The attacker suite certificate, $\mathrm{BI}^{\mathrm{suite}}$, applies a KL-binomial confidence interval with a union bound over a fixed suite that contains every trained attacker, preprocessing choice, and hyperparameter. BI therefore turns standard profiled-attack evaluation into an auditable certificate with an explicit attacker scope and confidence level. We further define $\mathrm{BI}^{\mathrm{loc}}(\varepsilon)$ to bound the recovery success of attackers whose normalized scores differ by at most $\varepsilon$ from those of a model in the suite. Across eight side-channel benchmarks with trace dimensions up to $7{,}000$, BI provides stable certificates without density estimation, and its tightness diagnostics tell an evaluator whether a certified value is a genuine measurement of leakage or a conservative bound that more attack traces would tighten.
Last updated:  2026-11-05
Memory-Efficient HQC Implementations on Cortex-M3 and Cortex-M7
Minjoo Sim, Siwoo Eum, Minwoo Lee, Seungwon Lee, Gyeongju Song, Lee Wai Kong, Anupam Chattopadhyay, and Hwajeong Seo
In the Hamming Quasi-Cyclic (HQC) key encapsulation mechanism (KEM), eliminating the polynomial product buffer still leaves serialized inputs, operands, and candidate ciphertexts that may coexist during decapsulation. We organize storage around the last use of each value. Comparing each candidate component before producing the next allows both to share one workspace, while deterministic regeneration shortens the lifetimes of ephemeral supports. Our lifetime analysis relates the measured footprint to the values that coexist during reencryption in our compact design. We read dense operands directly from serialized inputs and reuse output storage as workspace before final serialization during key generation and encapsulation. These choices reduce overlapping storage across the complete KEM and complement established support-form and Zero-Buffer multiplication. We evaluate this organization for all three HQC parameter sets on ARM Cortex-M3 and Cortex-M7 under the August 2025 specification. In a cumulative Cortex-M3 HQC-256 comparison, combined representation and lifetime changes reduced the stack by 38.9% relative to a Zero-Buffer configuration that already uses component-wise ciphertext comparison. Using a separate configuration, we measured decapsulation footprints of 36,858 bytes on Cortex-M3 and 36,850 bytes on Cortex-M7, including peak operation stack and serialized input/output storage. The common object layout accounts for most of these footprints. In the evaluated configurations, the relative increase in decapsulation cycles from the direct to the compact implementation is larger on Cortex-M7 than on Cortex-M3. Retaining supports reduces cycles when memory permits. The kernels retain support-dependent control flow and memory accesses; we did not establish complete-KEM constant-time execution or physical side-channel resistance.
Last updated:  2026-11-05
Formalizing PQC Signature Transition: Case of PoW Blockchain Against On-Spend Attack
Kigen Fukuda and Shin’ichiro Matsuo
It is getting widely recognized that quantum computers pose a fundamental threat to blockchain security. The transaction signature transition to Post-quantum cryptography (PQC) is therefore an urgent challenge. However, it remains unclear how much quantum computing power would be sufficient to compromise blockchain security and, consequently, by when the transition should be completed. To address these questions theoretically, we first formalize the signature transition process and the quantum adversary based on the well-known Bitcoin backbone protocol framework. We then establish a threshold for the chain's tolerable quantum adversary capability. Specifically, we prove that a security property \emph{migration liveness} holds with overwhelming probability if $$ \Delta_{\mathrm{eff}} \geq \left\lceil \frac{4}{(1 - \epsilon)f} \right\rceil, \quad\text{and}\quad f \cdot \Delta_{\mathrm{eff}} = \Omega(\log^{2}\kappa) $$ where $\Delta_{\mathrm{eff}}$ is the number of rounds the quantum adversary needs to produce a forged transaction after the broadcast of a migration transaction, $f$ is the honest mining success probability, $\epsilon$ is the concentration quality of the underlying random variables, and $\kappa$ is the security parameter. We further generalize the analysis to derive a relationship between the transition process and the tolerable quantum adversary capability, providing a theoretical basis for designing secure signature transition plans.
Last updated:  2026-11-05
Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space
Jiseung Kim, Minkyu Kim, and Hyung Tae Lee
We give a randomized, rank-preserving reduction from exact $\ell_p$-CVP to exact Euclidean SVP for every integer $p\ge2$. For rational inputs of bit length $\ell$ on full-rank lattices $L\subset\mathbb R^N$, the reduction uses $(Cp)^N\poly(p,\ell)$ oracle calls and additional bit operations, where $C$ is an absolute constant. It uses $\poly(p,\ell)$ working space outside the oracle, and all oracle queries have rank $N$ and $\poly(p,\ell)$ bit complexity. For $p=2$, the reduction transfers polynomial-space exact SVP algorithms to exact CVP with $2^{O(N)}\poly(\ell)$ time overhead. Instantiating it with the SVP algorithms of Kannan and of Feng, Gao and Liu yields randomized polynomial-space CVP algorithms running in time $N^{N/(2e)+o(N)}$ and $N^{N/(4e)+o(N)}$, respectively. For every fixed integer $p\ge3$, the same reduction yields exact $\ell_p$-CVP algorithms for arbitrary rational targets either in randomized time and space $2^{O(N)}$, or in randomized time $N^{N/(4e)+o(N)}$ and polynomial space. These algorithmic bounds are up to polynomial factors in $\ell$. The reduction performs local search sequentially over the cosets of \(2L\), where \(L\) is the input lattice, while tracking the excess of the current objective value over the optimum. Within a coset containing a closest vector, midpoint inequalities bound the unknown correction in terms of this excess, which in turn allows us to construct many short corrections that reduce the excess bound by a factor of four. A counting argument shows that these improving corrections form a sufficiently large fraction of the lattice points in a known search region, and a sparsification-based sampler assigns sufficiently large probability to every nonzero vector in that region, using at most one SVP call per sample. Repeating this improvement over polynomially many stages yields exact recovery. For \(p\ge3\), the same framework is extended using a diagonal weighted norm computed from the current point.
Last updated:  2026-11-05
Structured Quantum Hardness from Unstructured Assumptions
Xiao Liang, Takashi Yamakawa, and Chak Fai Yung
Whether useful structured hardness can arise from unstructured assumptions is a fundamental question in complexity and cryptography. The longstanding Bennett–Gill question asks whether $\mathsf{NP}\cap\mathsf{coNP}$ remains hard relative to a random oracle; [GIKKLS, STOC 2023] recently gave a conditional affirmative answer in the classical setting. We establish the quantum analogue: if $\mathsf{UP}\not\subseteq\mathsf{BQP}$, then $\mathsf{NP}^{O}\cap\mathsf{coNP}^{O}\not\subseteq\mathsf{BQP}^{O}$ with probability $1$ over a random oracle $O$. Beyond extending the classical result, this separation has a distinctly quantum significance: Shor’s algorithms defeat canonical number-theoretic hardness candidates, while lattice assumptions and other leading post-quantum cryptographic assumptions do not directly supply hard languages with two-sided classical certification on every input. Our conditional oracle separation provides evidence that such structured quantum hardness can nevertheless arise from unstructured sources. Complementing this result, we rule out fully black-box quantum reductions of worst-case quantum hardness in $\mathsf{NP}\cap\mathsf{coNP}$ to post-quantum injective one-way functions and indistinguishability obfuscation. This barrier excludes a broad class of black-box approaches to deriving structured quantum hardness from generic cryptographic primitives, providing partial evidence that the non-black-box techniques in our first result are essential.
Last updated:  2026-11-05
Optimizations and First-Order Masking of AIMer on Cortex-M4
DongCheon Kim, Jaeseung Han, Dong-Guk Han, and Seog Chung Seo
We optimize AIMer-128f on Cortex-M4 and propose first-order masking of its signing. Since squaring is a Frobenius map about $\times 16$ cheaper than multiplication, we restructure AIM2's inverse-Mersenne S-box into a Frobenius-shifted addition chain, cutting multiplications per S-box from 24/23 to 9/10. Since one multiplication-check operand is constant across $N = 16$ parties, we build the partial-product table once and reuse it. Both are orthogonal to single-multiplication acceleration, and with a Radix-16 multiplier on NUCLEO-L4R5ZI, keygen/sign/verify drop 18.55%/3.94%/7.30%. 1-PINI gadgets on every sensitive operation give first-order probing security. TVLA finds no first-order leakage in 100,000 traces. Masking costs $\times 10.5$, itself improved 5.20%.
Last updated:  2026-11-05
Breaking $\mathsf{TraintoDefend}$ via Adaptive Neuron Clustering in Cryptanalytic Model Extraction
Haojie Wu, Haolin Liu, Tianshuo Cong, and Guoyan Zhang
Cryptanalytic model extraction poses a fundamental threat to deep learning model confidentiality by enabling precise parameter recovery with theoretical guarantees of functional equivalence. To counter this growing threat, $\mathsf{Train to Defend}$ (NeurIPS 2025) was proposed as the first dedicated defense against cryptanalytic extraction and remains the only defense believed to be effective to date. It encourages neurons to learn similar weights so that they switch activation states together, making their individual contributions harder to distinguish. However, we notice that neurons with similar weights need not switch activation states together under small perturbations. Instead, weight similarity can cause the original clustering rule to merge signatures from distinct neurons when only a subset of their normalized weight coordinates agree. Motivated by this observation, we introduce $\mathsf{SimBreak}$, an adaptive clustering rule that breaks the weight-similarity defense of $\mathsf{Train to Defend}$. $\mathsf{SimBreak}$ estimates a relative scale from all jointly observed weight coordinates and uses the same scale to test both weight direction and bias consistency. Across six protected fully connected networks trained on MNIST, $\mathsf{SimBreak}$ raises target layer signature recovery from $0\%$ to $100\%$, with a maximum relative recovery error of $2^{-22.27}$. Our work challenges the use of neuron weight similarity as a sufficient basis for protection and establishes adaptive evaluation as essential to assessing cryptanalytic extraction defenses.
Last updated:  2026-11-05
Tamper-Resilient Quantum Key Encapsulation with Coherent Ciphertexts from qOWFs in the QROM
Shiyu He
Kitagawa et al. (CRYPTO 2024) constructed the first tamper-resilient, chosen-ciphertext-secure public-key encryption from quantum-secure one-way functions (qOWFs). However, their construction assumes authenticated classical channels and measures intermediate signed-phase states to produce classical ciphertexts. Therefore we ask whether coherent quantum ciphertexts can support active security and certified deletion over unauthenticated classical and quantum channels. We construct the first tamper-resilient quantum key-encapsulation mechanism (QKEM) from qOWFs with coherent quantum ciphertexts and genuine validity-feedback confidentiality in the quantum random-oracle model. Our scheme, designated Signed-Fourier QKEM, retains signed coherence through honest encapsulation to form a state-consuming quantum ciphertext. Aside from an authentic root verification key, all transmitted classical metadata and quantum registers are subject to arbitrary adversarial tampering and entanglement. With one quantum public key per independent signing domain and a challenge serial unused in pre-challenge decapsulation queries, we prove session-key confidentiality under genuine different-header decapsulation, including queries sharing the challenge serial, and genuine same-header validity feedback. We also establish fixed-header key robustness against adaptive decapsulation attacks, bounding wrong-key acceptance by a negligible probability. Furthermore, our scheme provides publicly verifiable computational certified deletion, protecting session-key privacy against subsequent, complete exposure of the receiver's secret state. Finally, composing our QKEM with a classical one-time private data encapsulation mechanism yields header-restricted chosen-ciphertext confidentiality for arbitrary polynomial-length messages.
Last updated:  2026-11-05
One-Way Functions and Local Descriptions of Random Data
Dimitrios Myrisiotis
Sample compression describes a labeled sample by retained examples and extra information from which a decoder recovers the labels. We show that estimating the length of the shortest such description of random data is hard on average if and only if one-way functions exist. As in Hirahara and Nanashima's (FOCS 2023) consistent pointwise programs, the decoder labels each sample point separately, as a hypothesis does, but in our main result the labels are random rather than given by a concept. To label a point, it sees only that point, the retained examples with one extra bit each, a program, and a public random string revealed before the description is chosen. The length counts the choice of retained examples, their extra bits and the program, not the examples themselves. The task is to output a number between the $1/2$ and $3/4$ quantiles of the shortest length over the public string, up to an additive $a\lceil\log_2m\rceil$ for $m$ points and a fixed integer $a\ge0$. The main result takes polynomially many, at least $8n$, uniform $n$-bit points with independent uniform labels and any large enough polynomial time bound per query. If one-way functions exist, every efficient randomized algorithm fails to output such a number for all large $n$ with probability above an inverse polynomial that is the same for all algorithms and time bounds. Otherwise, for every inverse polynomial, some such algorithm fails with at most that probability for infinitely many $n$. For hardness, labels derived from one-way functions look random yet have short local descriptions, which random labels rarely have. The converse inverts a function that generates descriptions. One-way functions also exist if and only if estimating between the quantiles is hard, at some suitable time bound, for some PAC-style samplable data of the same sizes, labeled by a concept independent of the points.
Last updated:  2026-11-05
Otter: A Provably MEV-Resilient Automated Market Maker via Surplus Redistribution
Elaine Shi, Mengqian Zhang, Hao Chung, and Yuhao Li
Miner extractable value (MEV) in automated market makers allows block builders to profit from transaction ordering and injected trades, imposing costs on users and contributing to builder centralization. We introduce Otter (Optimal Truthful Trading with Excess Redistribution), a two-asset batch AMM that achieves provable MEV resilience when the consensus layer provides censorship resilience and block space is uncongested. In particular, Otter makes truthful behavior a dominant strategy for both users and builders. Consequently, a builder cannot profit from strategic deviations, including reordering bids or injecting sybil bids. These guarantees continue to hold even when the builder is itself a trader with intrinsic value. Moreover, we show that our mechanism maximizes social welfare, in a strong sense, within a natural class of mechanisms satisfying the desired game-theoretic properties. To achieve these guarantees, we introduce a new paradigm called surplus redistribution, which provably prevents residual surplus from being captured as MEV by redirecting it to the broader community. Specifically, the pool's output tokens need not be distributed entirely among the users in the current batch. Instead, any residual surplus may be transferred, for example, to a smart contract governed by the decentralized community. The accumulated surplus can subsequently be used to benefit community members in ways that preserve the mechanism's game-theoretic guarantees --- for example, by subsidizing traders' transaction fees, rewarding liquidity providers, or returning assets to the pool to reduce price impact and slippage for future traders. Our approach relies on the underlying consensus layer to provide censorship resilience. We motivate the necessity of this assumption through an impossibility result showing that the desired game-theoretic guarantees become unattainable when the builder is additionally allowed to censor transactions. Thus, our results also provide a mathematically formal demonstration of how consensus-level security guarantees can fundamentally expand what is achievable at the application (i.e., smart-contract) layer. Finally, we establish additional results characterizing the builder fee structures compatible with our desired incentive guarantees.
Last updated:  2026-11-05
Quadratic Extractors
Gautam Chandrasekaran, Jesse Goodman, and David Zuckerman
A quadratic source is a random variable $X\sim\mathbb{F}_2^n$ generated by applying $n$ quadratics to a hidden uniform string. Previously, the best-known explicit extractor for this model required min-entropy roughly $k=n-\sqrt{\log n}$. In this paper, we give an explicit construction for min-entropy $k=\mathrm{polylog}(n)$. Even for the special case of $2$-local sources, where each bit of $X$ depends on two hidden uniform bits, achieving an entropy requirement below $k=\sqrt{n}$ was an important open problem. This is because such sources provably cannot be reduced (in a black-box manner) to our most powerful general-purpose seedless extractor, known as a sumset extractor. Our new extractor bypasses this barrier, providing the first explicit construction to go beyond sumset extraction.
Last updated:  2026-11-04
Separating Pseudorandom Codes from Quantum Random Oracles
Nico Döttling, Anne Müller, and Mahesh Sreekumar Rajasree
Pseudorandom codes (PRCs) combine two seemingly conflicting goals: robustness to noise and computational indistinguishability from random strings. Recent work has shown that classical symmetric-key PRCs over binary alphabets cannot be constructed from minimal cryptographic assumptions, such as one-way functions, via black-box reductions. In this work, we revisit this question in the presence of quantum computation and quantum information. We first consider pseudorandom codes with classical codewords but quantum algorithms. We prove that symmetric-key pseudorandom codes robust to Bernoulli noise admit no black-box construction from quantum random oracles, and hence from quantum-secure one-way functions. This establishes that the classical black-box barrier for PRCs persists even in the quantum computational setting. Motivated by this separation, we investigate the notion of quantum pseudorandom codes (QPRCs), in which codewords are quantum states and security is defined via computational indistinguishability from Haar-random states. We then present several positive results. Assuming quantum-secure one-way functions, we construct QPRCs that are secure against a single encoding query, allow multiple copies of the challenge state, and tolerate an error rate matching that of any classical uniquely decodable binary error-correcting code against a dephasing or bit-flip channel. We also show that the PRFS with proof of destruction due to Behera et al. (TCC 2023) can be extended to a 0-bit QPRC that is secure against multiple encoding queries and tolerates unbounded phase errors but only a constant number of bit-flip errors. Finally, assuming the existence of quantum-secure single-query pseudorandom states (1PRS), we construct single-query single-copy QPRC that tolerate arbitrary Pauli noise up to the decoding radius of a quantum error-correcting code with unique decoding.
Last updated:  2026-11-04
Vectorized (2, 2)-Isogenies in the Theta Model Using AVX-512 and Applications to SQIsign
Marius A. Aardal, Diego F. Aranha, Patrick Longa, and Giacomo Pope
Higher-dimensional isogenies have emerged as a powerful building block for isogeny-based cryptography, with recent protocols such as SQIsign relying on the efficient evaluation of $(2^n, 2^n)$-isogenies. Despite their attractive security and compactness properties, these schemes remain computationally expensive and improving their performance is an important step for their real-world use. In this work, we present a high-performance AVX-512 implementation of two-dimensional isogenies that effectively exploits their data-level parallelism. We develop a code generator that produces efficient AVX-512 implementations of arithmetic over $\mathbb{F}_p$ and $\mathbb{F}_{p^2}$ for Montgomery-friendly primes of the form $p=c\cdot 2^e-1$ with $e\approx \log_2(p)$, covering the family of primes used by several protocols based on two-dimensional isogenies, including SQIsign. Building on this arithmetic, we vectorize the $(2^n, 2^n)$-isogeny formulas by Dartois et al. (ASIACRYPT 2024), achieving significant speedups over the corresponding, highly-optimized scalar implementation that uses x86-64 assembly. As an application, we accelerate the Round 2 version of SQIsign verification and obtain speedups of $2.5\times$ at NIST security level I and $3.2\times$ and $3.3\times$ at levels III and V, respectively. Our code generator also readily supports the larger primes of Round 3 SQIsign, for which we obtain verification speedups between $3.1\times$ and $3.4\times$.
Last updated:  2026-11-04
STIR/SHAKEN: A Cocktail of Cryptographic Clumsiness
Josh Brown, Matthew Hardeman, and Paul Grubbs
Scams and fraudulent robocalls are rampant in the telephone system. Fraudsters often employ call spoofing to impersonate a known caller to the victim, making it difficult to detect and block the fraudster’s calls. In an effort to combat call spoofing, the U.S. government in 2019 mandated the use of a new suite of protocols called STIR/SHAKEN. In STIR/SHAKEN, providers include a cryptographically-signed assertion about the caller’s identity and other metadata in call headers. This serves both to authentically convey this metadata between providers during call routing and to provide reportable, verifiable evidence of bad behavior by providers that originate fraudulent calls. This paper asks whether STIR/SHAKEN achieves its security goals, and at what cost to the telephone system. On security we find serious structural weaknesses: a year of STIR/SHAKEN certificates observed in production call traffic shows a PKI riddled with noncompliance—nearly half of valid certificates violate the specifications—a provider can prevent later verification of a STIR/SHAKEN assertion by taking its certificate offline, and a header-malleability flaw, which we verified in test calls placed with the help of a real telephone provider, causes a spoofed caller ID to be displayed as verified on some phones. The cost, meanwhile, has been steep: STIR/SHAKEN deployment has created systemic new harms to the privacy of all phone users. These new privacy harms take two forms. First, signing call metadata renders it cryptographically non-repudiable: for the first time in the phone system’s 150-year history, there is publicly verifiable proof that a call took place. Second, STIR/SHAKEN’s complexity pushes providers to outsource signing and verification—roughly half of the 29 providers we surveyed do so, most to a handful of dominant vendors—causing widespread new leakage of sensitive call metadata to off-path third parties. (One such off-path third party, Neustar, was acquired in 2021 by TransUnion, one of the three nationwide U.S. credit bureaus. Neustar authenticates over 30 billion calls per month—and TransUnion sells a “Phone Behavior Intelligence” product advertising “insight into billions of call transactions” obtained through its “deep carrier relationships.”) These structural harms sit atop implementation failures: our tests also found implementations that completely break the federally-mandated *67 caller-privacy mechanism. Finally, we propose solutions to the problems we identify. To fix the PKI, STIR/SHAKEN should adopt certificate transparency; a public certificate log also stops providers from taking certificates offline to defeat later verification. Our remaining solutions are cryptographic, and share a prerequisite STIR/SHAKEN cannot currently meet: the origin provider must learn the destination provider’s public key. We thus design a backwards-compatible key discovery mechanism that uses SIP error messages. We then attack the privacy harms directly: replacing STIR/SHAKEN’s signatures with asymmetric message franking (AMF) makes call metadata deniable again, and issuing AMFs blindly keeps it hidden from outsourced signers. We design the first blind signing protocol for the AMF construction of Tyagi et al., along with new security definitions capturing requirements novel to the setting, such as verifier-hiding blindness. To our knowledge, we thereby initiate the formal study of blind signing for designated-verifier signatures; we believe this is of independent interest.
Last updated:  2026-11-04
Can Fully Homomorphic Encryption on Public Blockchains Protect Sensitive Medical Consultations? A Security and Privacy Assessment
Nizamuddeen Shahruddeen
%===================================================================== \begin{abstract} People seeking care for stigmatised conditions often delay treatment because they fear exposure, yet digital health services routinely expose user data and metadata. Fully homomorphic encryption (FHE) now allows smart contracts on public blockchains to hold encrypted data whose decryption is governed by contract rules. This paper assesses whether this approach can protect sensitive medical consultations. We present ConfidentialCare, a prototype built on Zama's fhEVM and the Ethereum Sepolia testnet, in which patients' symptoms are encrypted in the browser and only an authorised doctor may decrypt them. We evaluated three versions of the system through metadata inspection, access-control tests and attack experiments, asking what FHE protects and whether access to patient data can be controlled. Consultation content remained confidential in all tested cases, and the design collects no names, emails or accounts. However, public on-chain metadata revealed which wallet consulted which doctor, the doctor's specialty, when, and the approximate length of each message, and this history would be exposed permanently if the wallet were ever linked to the patient. We also found that a doctor granted access could re-share a patient's encrypted data, both through a confused-deputy flaw in the application contract, which we fixed, and directly through fhEVM's access control list, and that neither withdrawing access nor closing a consultation removed it. A redesign based on time-limited, revocable delegation prevented re-sharing, and Zama's live service enforced its revocation and expiry immediately. On Sepolia, Zama's key-management service refused decryption without a valid delegation, and revocation took effect within the same block in all six trials. We conclude that FHE protects what patients disclose, but not the fact or context of seeking care, and that in fhEVM a permission to decrypt is also a permission to share. \end{abstract}
Last updated:  2026-11-04
Adams Bridge (V2.0) Accelerator: Bridging the Post-Quantum Transition
Mojtaba Bisheh-Niasar, Emre Karabulut, Kiran Upadhyayula, Michael Norris, and Bharat Pillilli
Quantum computing threatens widely deployed public-key cryptosystems, driving the urgent adoption of post-quantum cryptography (PQC) in cloud and hardware-accelerated security infrastructures. This paper presents \emph{Adams Bridge}, an industry-grade hardware accelerator for lattice-based PQC that integrates ML-KEM and ML-DSA within a unified architecture to maximize hardware reuse and silicon efficiency. The design features a staged, pipelined datapath that exploits multi-level parallelism to accelerate polynomial operations shared by both schemes. An optimized NTT/INTT and point-wise multiplication engine is tightly coupled with a high-throughput Keccak core and efficient hardware sampling, reducing memory overhead and eliminating pipeline stalls. Synthesized in 5\,nm technology and operating at 600\,MHz, Adams Bridge achieves the best reported Area-Time (AT) efficiency among unified designs under an iso-security comparison, improving AT by 1.4$\times$ (ML-KEM) and 2.7$\times$ (ML-DSA) over state-of-the-art architectures. The three phases of ML-DSA complete in 26, 61, and 31~$\mu$s, respectively, while ML-KEM takes 11, 14, and 20~$\mu$s for its corresponding stages. When scaled to 1~GHz, Adams Bridge achieves up to 1.22$\times$ and 2.21$\times$ performance improvements for ML-KEM and ML-DSA, respectively. To address physical attack vectors, the accelerator embeds hardware-level side-channel countermeasures, including masking, shuffling, and constant-time control and arithmetic, mitigating information leakage without compromising performance. Empirical TVLA evaluation up to one million traces confirms the elimination of first-order leakage in critical datapaths. Targeted for deployment within the open-source Caliptra Root of Trust (RoT), Adams Bridge represents the first open-source PQC accelerator under the Apache 2.0 license designed for real-world hardware security systems.
Last updated:  2026-11-04
Sumcheck bit packing
Matteo Frigo and abhi shelat
Circuit-based zero-knowledge proofs over large fields waste most of a field element when they commit to a single bit. We study the problem of committing to packed witnesses, in which $m$ bits are stored in one element of $GF(2^m)$, while still allowing the proof system to verify linear claims about the individual bits. Prior approaches to this problem either (a) scale to packing only 4 bits[Fs24], (b) require tensor-structured claims and additional sumcheck rounds that incur larger soundness error [DP23,DP25], or (c) rely on Frobenius automorphisms [Koc26]. In contrast, we present a simpler reduction that exploits only the $GF(2)$-linearity of the field trace and achieves soundness error $2^{-m}$ for arbitrary bit-linear claims. We then use a characterization of trace-zero field elements to make the reduction zero-knowledge over any hiding linear commitment scheme: whereas previous constructions verify $O(m^2)$ or $O(m)$quadratic constraints in the commitment scheme, our protocol requires only linear constraints.
Last updated:  2026-11-04
Fast Provable Algorithms for Approximate CVP and Exact SVP on Random \(q\)-ary Lattices
Jiseung Kim, Junhyuk Kwon, Changmin Lee, and JeongHwan Lee
We give provable randomized algorithms for the $\gamma$-approximate Closest Vector Problem ($\gamma$-CVP) with $\gamma=5/3$ and the exact Shortest Vector Problem (SVP) in the Euclidean norm on random $q$-ary lattices. These lattices consist of the integer vectors mapped to zero modulo $q$ by a uniformly random matrix $\mathbf{H}\in(\mathbb{Z}/q\mathbb{Z})^{m\times n}$, for any integer $q\ge2$. For input density $\delta=m\log_2q/n$ with $0\le\delta\le1$, the running times are $2^{0.2668n+o(n)}$ for $5/3$-CVP and $2^{0.2741n+o(n)}$ for exact SVP, with polynomial input-length factors suppressed. For $1<\delta\le3/2$, the respective bounds are $2^{0.56n+o(n)}$ and $2^{0.468n+o(n)}$. For all but a negligible fraction of matrices, both algorithms succeed with overwhelming probability over their internal randomness. Notably, for $0\le\delta\le1$, our provable bounds fall below even the $2^{0.2925n+o(n)}$ heuristic estimate for classical lattice sieving. As a cryptographic application, we prove that signatures in the original construction of Gentry, Peikert, and Vaikuntanathan (GPV) can be forged in time $2^{0.0534n+o(n)}$ for $n\ge5m\log_2q$. For a $128$-bit security target, a leading-term estimate gives $n\approx2400$ and a public key of roughly $144$ kB, indicating a substantial storage burden.
Last updated:  2026-11-04
Projective Jet Geometry and Hold-Out Rank of Binary Goppa Codes
Yongge Wang
We develop a projective-geometric and algebraic framework for the higher-order polynomial relations among the public generator-matrix columns of a binary Goppa code, the relations exploited by the recent structural distinguishers and key-recovery methods for Classic McEliece. The alternant representation realizes the public columns as rational points on a hidden curve parametrized over $\F_{2^m}$; higher-order vanishing conditions become fat-point conditions, pulled back along the hidden parametrization. Our first contribution is an exact characterization of a codimension-$t$ ambient space containing all products of $d$ code polynomials: the products satisfy $(\pi^dh)'\equiv0\pmod{g^2}$ for the support polynomial $\pi$ and the Goppa polynomial $g$, and the space of degree-$\le dD$ polynomials with this property has dimension $dD+1-t$ once $dD\ge2t-1$. Equality with the actual product space is proved in a local regime, verified computationally on every instance tested, and stated as a conjecture. Our second contribution is a Frobenius-descent theorem: a binary form vanishes on the hidden curve if and only if it vanishes on the union of its $m$ Frobenius conjugates, with the $\F_2$-dimension of such forms equal to the $K$-dimension of the ideal of the union; from it we derive Hilbert-function bounds, including a multilinear version attained on all but one of the twenty-seven keys with $t\ge5$ tested (and missed by one on that key), and the local structure of the pulled-back forms at the roots of $g$. We then analyze the universal dependencies among Hasse-jet conditions in the multilinear setting of the attacks: a closed formula for the rank at a single column, and an explicit family of $\binom{k}{2s-d-2}$ relations between the conditions at any two columns. At a held-out column we prove an exact codimension formula for the Goppa subcode generated by the gradients of the vanishing forms. Finally, running our experimental pipeline (the jet system of the attacks, without the key-recovery steps) on six independently generated keys of a Classic-McEliece-shaped code shows that the kernel dimension is comparable to that of a random control, while every kernel form exhibits the predicted hidden-curve vanishing, the gradients span the predicted subcode, and the first-order normal data of the kernel is nearly independent of the key. Together these results explain the main components of the nuisance space of the recent attacks and isolate the conjectures that remain for an exact description of the kernel.
Last updated:  2026-11-04
HqcLethe: Streaming HQC Encapsulation for Tiny Stateless Servers
Wind Wong and Klaus v. Gleissenthall
Stateless post-quantum authenticated key exchanges such as post-quantum WireGuard hedge against unexpected cryptanalytic advances by combining a lattice KEM with code-based Classic McEliece. However, recent attacks have led Germany's BSI to advise against McEliece, which leaves these protocols with lattices alone. HQC, the code-based KEM that NIST selected, could restore diversity, but its keys do not fit in a single packet, so a server would have to buffer multi-packet handshakes. This would leave an attack surface for memory exhaustion, which is what WireGuard's stateless handshake was designed to avoid in the first place. McTiny demonstrated that stateless key encapsulation for Classic McEliece is possible by streaming key blocks one-at-a-time. However, HQC's encapsulation does not split as easily into individual packets, as cyclic polynomial multiplication, unlike matrix-vector multiplication, is inherently non-local. We present HqcLethe, a stateless key exchange that streams an HQC encapsulation in packet-sized pieces. It uses the Chinese remainder theorem to split the polynomial multiplication into independent remainders, one per packet, and masks them so that they reveal no more than an ordinary HQC ciphertext, which we prove in Rocq with SSProve; we also verify session secrecy, server authentication and forward secrecy in ProVerif. Client puzzles bound CPU exhaustion, and HqcLethe removes memory exhaustion: on a Raspberry Pi 3B+, each worker runs in a fixed 1.2-1.6 MiB. At category 5 it sends 27x fewer bytes and uses 9.0x less server CPU than McTiny, the earlier stateless code-based design.
Last updated:  2026-11-04
Keyber: Recovering the Signal by Amplifying the Noise in ML-KEM
Vipin Kumar, Prathamesh Ram, Suparna Kundu, and Dhiman Saha
ML-KEM (FIPS 203) is now being deployed in real-world applications to provide security against adversaries with quantum computers. Therefore, the resistance of ML-KEM’s implementations to physical attacks requires thorough evaluation. So far, fault attacks on ML-KEM have targeted the decapsulation operation. The key generation operation has received little attention from a fault-attack perspective. In this work, we present Keyber, the first statistical ineffective fault attack (SIFA) on the key generation of ML-KEM. Keyber is a key-recovery attack that needs only a single fault in key generation. The fault adds a known value to the error vector. Thus, the public key becomes faulty, while the seed of the public matrix remains intact. Every subsequent decapsulation, therefore, carries a known induced error. The adversary encapsulates locally and keeps only ciphertexts whose induced error peaks at exactly one coefficient. A decapsulation failure can then be attributed to that coefficient. Each query yields one linear inequality on the secret key, with no further faults. We observe that approximately 0.2-27% of encapsulations are usable for different parameter sets of ML-KEM. The full secret key is recovered using up to 30,000 inequalities across all security levels. We also realise the attack for ML-KEM-512 on an ARM Cortex-M4 device using a single over-clock fault. We then recover the entire secret key end-to-end. A single fault in this one-time operation thus compromises the key for its entire lifetime. Protecting ML-KEM, therefore, demands hardening not only decapsulation, but also key generation.
Last updated:  2026-11-04
Cryptanalysis of Pairing-Based Additive Masking with Prime-Field Secrets
Harliv Singh
We analyze the public values generated by a pairing-based multi-secret sharing construction in which each secret is added to a power of a common pairing value. The secrets lie in the prime subfield of the extension field containing the public values. We show that the first two public values determine the common mask whenever an explicit nonzero condition holds. We also show that the exceptional case is resolved for the parameter set considered in the numerical example. Consequently, the complete public transcript determines every secret, without requiring a participant share or an initially compromised secret. We further describe two related forms of leakage: recovery of all secrets after disclosure of one suitable secret, and a reduction in the possible values of a secret from a single public value. Our conclusions concern the field-valued, common-base masking construction analyzed here; they do not imply that pairing-based secret sharing in general is insecure.
Last updated:  2026-11-04
BASTION: Lock-Step, Staggered and Sequential Share Schedules for a First-Order Masked ML-KEM NTT on FPGA
Marcos Lázaro Díaz
The Number Theoretic Transform (NTT) is the arithmetic core of ML-KEM (FIPS 203) and a prominent side-channel target in hardware. Because the transform is linear, first-order arithmetic masking applies share-wise without fresh randomness, which leaves one design decision open: when each share is processed. Published designs process the shares in sequence on one datapath, or on one datapath per share started a configurable delay apart and in random order; running both datapaths in lock-step is the third option. We implement the three schedules on one first-order masked NTT core for ML-KEM on Artix-7 and measure their cost and pre-silicon leakage under one synthesis flow. An iso-architectural unmasked control separates the cost of masking from that of parallelisation: the delivered lock-step core costs 1.56x the LUTs, 2.33x the slices and twice the DSPs of the control at an unchanged cycle count and 196.1 instead of 227.3 MHz, while the sequential core needs 9 LUTs more than the control at twice the cycles. We state when a set of samples combines both shares of a secret, measure the criterion on the RTL and use it as a cycle-accurate oracle. On a whole-design toggle model that sums both share domains, calibrated with injected flaws detected within 750 traces, no schedule leaks at first order in five pairs of runs of 10^5 traces. At second order the schedules form a scale: the lock-step core leaks in single samples, the sequential core only at the pair of samples that its public offset relates, and the staggered core in both ways at every delay we tested short of one transform. Every detected sample lies in the support view of the oracle, which flags up to 80% of the samples of a window for the univariate test, and some lie outside its form view, so lazy reduction matters. A check on the routed netlist finds no cell shared by the domains of the lock-step and staggered cores, and finds the cells that synthesis shares once the preservation attributes are removed. Silicon validation is left to future work.
Last updated:  2026-11-04
Attacks on Goldreich's Pseudorandom Generators by Grouping and Solving
Ximing Fu, Mo Li, Shihan Lyu, and Chuanyi Liu
Goldreich's pseudorandom generators (PRGs) with constant locality admit highly parallel implementations, yet the concrete security of instantiations based on the $\xor\text{-}\thr$ predicate has remained unclear. In this work, we present novel seed recovery attacks on Goldreich's PRGs instantiated on \(\xor\text{-}\thr\) predicates with $m=n^s$, where $m$ and $n$ are the length of output and input, respectively. By partitioning the output bits into groups according to common input bits, high-biased noisy equations can be derived for the group whose common input bits are all 1s (or all 0s). Leveraging two solvers tailored to these equations, we achieve the seed recovery attacks, which needs roughly $2^{n(1-\log_2{(1 + \frac{2s}{\sqrt{2\pi (b-s)}})})}$ calls to Gaussian elimination when the input length of the $\thr$ predicate $b\geq (n-s)^{1/s}+s-1$ with small stretch $s$. Applying our attack to the asymptotic \(\xor\text{-}\maj\) family proposed in STOC 2016 yields complexity \(2^{\,n\!\left(1-\log_{2}\!\left(1+\sqrt{\frac{s}{18\pi}}\right)\right)} \le 2^{0.82n}\), i.e., at least a \(2^{0.18n}\) speedup over exhaustive search for any stretch \(s>1\). We also deploy our attack on an instance used in the construction of silent oblivious transfer protocols (Eurocrypt 2024) with \(n = 256\). This attack is capable of breaking the instance using approximately \(2^{31.3}\) calls to Gaussian elimination over 244 variables. We successfully implemented the attack on a cluster of 14 CPU cores, recovering the seed in 71 hours, demonstrating the attack's efficiency. Beyond PRGs, with appropriate adaptations our method extends to FiLIP stream ciphers instantiated with $\thr$-related predicates. Our evaluation indicates that most FiLIP instances do not meet their claimed security. For instance, the configuration \(\xor_{100}\text{-}\thr_{11,22}\text{-}\thr_{11,22}\) is broken in about \(2^{59}\) calls to Gaussian elimination over 357 variables despite a 397-bit key and a claimed 80-bit security level.
Last updated:  2026-11-04
Statistically Secure Asynchronous MPC with Linear Communication and $\mathcal{O}(n^5)$ Additive Overhead
Xiaoyu Ji and Yifan Song
Secure multiparty computation (MPC) allows distrusted parties to jointly evaluate a common function while keeping their inputs private. In this work, we focus on improving the communication complexity of information-theoretic asynchronous MPC with optimal resilience ($t < n/3$). The current state-of-the-art work in this setting by Goyal, Liu-Zhang, and Song [Crypto’24] achieves amortized linear communication per gate with $\mathcal{O}(n^{14}\kappa)$ field elements additive overhead, where $\kappa$ is the security parameter. In comparison, the best-known result in the synchronous setting by Goyal, Song, and Zhu [Crypto’20] achieves amortized linear communication per gate with only $\mathcal{O}(n^{6})$ field elements additive overhead, revealing a significant gap that we aim to close. This work closes this gap and goes further. We present the first statistically secure asynchronous MPC protocol achieving amortized linear communication per gate with only $\mathcal{O}(n^{5})$ field elements additive overhead assuming a functionality for Agreement on Common Set (ACS). With the best-known instantiation for ACS, we obtain an asynchronous MPC protocol in the plain model with additive overhead $\mathcal{O}(n^5)$ field elements in expectation. In the setting of statistical security with optimal resilience, this even surpasses the best synchronous result. Technically, our contributions include (i) a new protocol for generating Beaver triples with linear communication per triple and $\mathcal{O}(n^3)$ field elements additive overhead assuming functionalities for generating random degree-$t$ Shamir sharings and ACS, and (ii) a new protocol for generating random degree-$t$ Shamir sharings with linear communication per sharing and $\mathcal{O}(n^{5})$ field elements additive overhead assuming a functionality for ACS. Along the way, we also construct a new protocol for asynchronous complete secret sharing (ACSS) with linear communication per sharing and $\mathcal{O}(n^5)$ field elements additive overhead, and a parallel version of ACSS that maintains the same additive overhead assuming a functionality for ACS, which may be of independent interest.
Last updated:  2026-11-04
Qlapoty: Improved analysis and efficiency for quaternionic ideal to isogeny transformation
Max Duparc, Antonin Leroux, and Sina Schaeffler
The quaternionic ideal-to-isogeny translation is a central building block of SQIsign. While the Qlapoti algorithm by Borin, Invernizzi, Corte-Real Santos, Eriksen, Mula, Schaeffler and Vercauteren significantly simplified and accelerated this step, it does not treat several technical details in sufficient depth, resulting in a flawed analysis of its failure probability. Additionally, several discrepancies between the implementation of Qlapoti and the paper's pseudocode were never analyzed explicitly. We address these shortcomings and add further improvements, resulting in a new norm equation solving algorithm with negligible failure probability. Our C implementations shows 6x to 9x speedups compared to Qlapoti’s norm equation solver, and 1.3x-2.1x speedups for a SQIsign NIST2 signature (depending on parameter sets).
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.