Determining the precise parts of the key that need to be guessed in a key-recovery attack is fundamental for judging its cost: if the same attack can be executed by guessing less key material, then the cipher's resistance against this attack is overestimated. Although a multitude of prior works provide upper bounds on the key material required, and although these bounds might be tight in some special cases, a precise evaluation of the required key material and the tightness of these bounds is still missing. We remedy this by enumerating linear trails to iteratively compute the affine hull of the support of the Fourier transform of the key-recovery map. This leads to a generic and practical algorithm that identifies the smallest subspace of key material to be guessed. This algorithm is ready to be used in many different attacks and for a large variety of cipher structures. We demonstrate its impact by showcasing improvements on several published integral, linear, differential-linear, and zero-correlation attacks on the block ciphers PRESENT, SIMON, SKINNY, and GIFT.

We consider (boolean or arithmetic) circuits in which every gate may compute an arbitrary function of its input gates. We show a novel tradeoff between a circuit's size and its fan-in: \begin{quote} Any function which may be computed using $s$ fan-in $2$ gates can alternatively be computed using $s/3\ (1+O(1/\sqrt{k}))$ fan-in $k$ gates. \end{quote} This asymptotically improves the previous bound of $2s/5\ (1+O(1/k))$ by Charbit, Couteau, Meyer, and Naserasr [TCC'24]. Among other applications, this improves the communication complexity of secure multiparty computation in the correlated randomness model. \emph{Any} $n$-input $m$-output circuit with $s$ internal gates (over arbitrary binary gates) can be securely computed in the correlated randomness model with per party communication $s/3 + n + m$ and computation $\widetilde{O}(s)$. Our paper stands at the intersection of cryptography, complexity theory, and graph theory, but our main technical contribution is one to extremal combinatorics: we establish that every order-$n$ $2$-degenerate graph admits a planarising set of size at most $\lfloor n/3 \rfloor$. Our main conceptual contribution is to relate the existence of sublinear-size (directed) $k$-path transversals to well-studied graph parameters. Along the way, we uncover a recurringly overstated lemma throughout the literature on sublinear-size vertex-separators and hyperfinite graphs. According to this lemma, any monotone graph class admitting sublinear-size balanced vertex separators should be weakly hyperfinite. However, this is contradicted by a graph class put forward by [Moshkovitz and Shapira, Random Structures \& Algorithms'15]. Unfortunately, the lemma appears in highly influencial works such as [Henzinger, Klein, Rao, and Subramanian, STOC'94 \& JCSS'97], or the textbook of Nešetřil and Ossona de Mendez [\emph{Sparsity}, Springer'12], and in turn it is used in a significant number of papers. Thankfully a slightly weaker version of this lemma is true, with a caveat on how sublinear the vertex separators needs to be, and we provide the correction as a service to the community.

An attribute-based encryption (ABE) scheme is "large-universe" if its attribute universe is superpolynomial and is not enumerated during setup. In the multi-authority setting, we further require that each authority can independently manage a superpolynomial set of attributes and dynamically issue an arbitrary polynomial number of secret keys per user. Although large-universe (multi-authority) ABE from pairings is well studied, explicit lattice-based constructions have remained elusive. In the centralized setting, a standard workaround is to instantiate lattice-based ABE for general circuits and encode each attribute as a bit string; however, unless one adopts non-standard lattice assumptions, this approach typically yields prohibitively large ciphertexts. In the multi-authority setting, even though lattice-based ABE for general circuits is known, this bit-encoding approach applied to those schemes does not yield a genuine large-universe construction. We close this gap by presenting the first lattice-based large-universe (multi-authority) ABE schemes under the Learning With Errors (LWE) assumption, achieving ciphertext and key sizes that are comparable to those in the pairing-based setting. Concretely, we construct: • a large-universe key-policy ABE scheme with ciphertext size $O(t)$; • a large-universe ciphertext-policy ABE scheme with ciphertext size $O(|f|)$; and • a large-universe multi-authority ABE scheme, where $t$ is the number of attributes, $|f|$ is the policy size, and the $O(\cdot)$ notation suppresses $\tilde{O}(\lambda)$ factors. All schemes support policies in disjunctive normal form (DNF) and are proved secure in the random oracle model. We further develop more efficient variants of our key-policy and ciphertext-policy ABE schemes over ideal lattices under the Ring-LWE assumption, aiming for practical performance on the order of seconds to minutes. Experimental results from our implementations confirm practical runtimes and memory consumption, providing concrete evidence that large-universe lattice-based ABE is feasible for efficient real-world deployment.

For a linear code $C\subseteq\mathbb{F}_q^n$, we say that $C$ satisfies the proximity-gaps property up to distance $\delta_1$ if, for every $\delta_2>\delta_1$ and every $f,g\in\mathbb{F}_q^n$, at least one of which is $\delta_2$-far from $C$ in relative Hamming distance, there are only a small fraction—typically at most $\operatorname{poly}(n)/q$—of exceptional coefficients $z\in\mathbb{F}_q$ for which $f+zg$ is $\delta_1$-close to $C$. The work [BGKS20] shows that every linear code of relative distance $\delta$ satisfies proximity gaps up to the one-and-a-half Johnson radius \[ J_{3/2}(\delta)=1-(1-\delta)^{1/3}. \]We prove that this threshold is tight for general linear codes at every distance $0<\delta<1$. Specifically, for every $0<\delta<1$, we construct a linear code of relative distance arbitrarily close to $\delta$ and words $f,g\in\mathbb{F}_q^n$ that are both \[ 1-(1-\delta)^{4/9} \]far from the code, but for which a constant fraction of coefficients $z\in\mathbb{F}_q$ make $f+zg$ nearly $J_{3/2}(\delta)$-close to the code. Our counterexamples continue to hold even when a fixed amount of distance-dependent slack is allowed.

Let $H_1:=\liminf_{n\to\infty}(p_{n+1}-p_n)$, where $p_n$ is the $n$-th prime. The twin-prime conjecture asserts that $H_1=2$. Zhang [Zha14] proved the first finite bound, $H_1<7\times10^7$. Maynard [May15] improved this bound to $H_1\le600$. Polymath [D. 14b] subsequently established $H_1\le246$. Stadlmann [Sta26] further improved the bound to $H_1\le240$. In this paper, we prove $H_1\leq236$.

Dynamic zkSNARKs were recently introduced by Wang et al. [Eurocrypt, 2026]. This primitive extends standard zkSNARKs with an update algorithm that adapts a proof to a new statement in time sublinear in the circuit size, provided the witness changes in few positions. However, existing constructions either need a circuit-specific setup or, in the universal case, send over $130$ group elements and require over $180$ pairings. As is the case for universal zkSNARKs, dynamic ones can be built from dynamic arguments for Hadamard products and linear relations. Wang et al. handle the latter in the particular case of a permutation matrix, via a sparse argument---a protocol whose prover runs in time proportional to the Hamming weight of the witness. Nevertheless, their techniques do not directly extend to the arbitrary matrices arising in constraint systems such as R1CS or CCS. Furthermore, the standard approach for proving general linear relations is unsuitable for the sparse setting because of a witness-independent step: the prover commits to an auxiliary polynomial determined by the matrices alone, and is hence dense regardless of how sparse the witness might be. Our first contribution is a sparse zkSNARK for linear relations, which we build from a fully witness-dependent argument together with what we call a rational encoding of the matrices. As our second contribution, we develop a compiler that turns any sparse argument for a linear relation into a dynamic one, while preserving the zero-knowledge property of the underlying scheme. Instantiated for Plonk and R1CS-lite, our techniques yield universal dynamic zkSNARKs with at most $20$ group elements per proof and $23$ verifier pairings---over $6.5\times$ and $7.8\times$ fewer than the state of the art---as well as asymptotically faster updates. We also show how both of our constructions can be de-amortized.

FUTURE is a lightweight block cipher with a 64-bit block, a 128-bit key and $10$ rounds, proposed at AFRICACRYPT 2022 for low-latency hardware. This study analyzes FUTURE in the related-key setting with a bit-level constraint model that carries the exact weights of the differential distribution table and the exact entries of the boomerang connectivity table, and whose objective function $2w_0 + 2w_1 + w_{\mathrm{bct}} = -\log_2(p^2q^2r)$ optimizes both sub-ciphers and the middle layer of the sandwich framework together. The model returns a full-round distinguisher whose objective function value $36$ is optimal over all switching rounds and whose probability is $P = \hat{p}^2\,\bar{r}\,\hat{q}^2 = 11\cdot 2^{-39} \approx 2^{-35.54}$, at a cost of $2^{37.54}$ queries under four related keys and $2^{37.54}$ XOR operations. Running it on the full cipher over $2^{44.34}$ quartets returns $341$ right quartets and an experimental probability of $2^{-35.92}$, in $63.9$ hours on an ordinary personal computer; at the previous full-round probability $2^{-45.8}$ the same computer would take about $6.8$ years. The distinguisher is therefore a practical one, and improves the best previously known full-round related-key boomerang distinguisher of FUTURE by a factor of $2^{10.26}$ in probability, in data and in time. An $8$-round distinguisher placed into the unified key recovery framework further gives a full-round attack with $2^{51.05}$ data, $2^{64}$ time and $2^{64}$ memory, whose time complexity attains the optimum of the framework at any memory within the codebook and improves the best previously known attack by a factor of $2^{6}$.

Proving the correctness of computations over a large dataset via succinct non-interactive arguments of knowledge (SNARKs) entails the large overhead of ``loading'' the dataset in the SNARK. However, certain computations may only need to access a small fraction of the dataset (e.g., a database query that only accesses a subset of table rows and then computes an aggregation function). The standard way of \emph{efficiently} proving such computations is to use \emph{lookup arguments with sublinear prover complexity} to load only necessary data to the SNARK. Unfortunately, all prior schemes are \emph{static}: even a single change to the dataset forces the prover to re-run an expensive pre-processing step, linear to the dataset size. The only exemption is the recent work of Dutta et al., (CCS'24) that proposed a lookup argument with \emph{amortized} sublinear updates---based on re-running the pre-processing phase periodically, when too many changes have been accumulated. In this work, we present Rogue, the first lookup argument with sublinear prover time and updates that \emph{always} take time proportional only to the number of incurred changes. Indeed, Rogue is actually a \emph{matrix lookup argument}, supporting entire row lookups in time proportional to the number of rows (and independent of their size)! It has very good practical performance, e.g., for a $2^{20}\times 2^7$ matrix and $2^{10}$ row accesses, Rogue achieves $\times 21$-$942$ and $\times 76$-$30000$ faster lookups and updates, respectively, compared to prior works. We then use Rogue to build RogueDB, the first verifiable database system for arbitrary SQL queries that supports authenticated indexes, hence achieves prover time sublinear to the database. Compared with prior schemes with succinct proofs, vSQL (Zhang et al., IEEE S\&P'17) and PoneglyphDB (Gu et al., SIGMOD'25), we get $\times 42.8$-$\times 8624.1$ and $\times 149.6$-$\times 11362.4$ faster prover times, for various SQL queries from the TPC-H benchmark.

Adaptor signatures have emerged as a powerful contract-minimal mechanism for fair exchange on blockchains, enabling efficient and privacy-preserving atomic swaps and conditional payments. However, existing adaptor schemes are limited to narrow classes of NP relations (e.g., discrete logarithm secrets) and specific signature schemes, limiting their scope both in terms of constructions and applications. This work addresses this gap by presenting a new framework that supports arbitrary NP relations and a broad range of signature schemes, significantly extending the reach of adaptor signatures beyond prior works and broadening the design space for adaptor signature constructions. Our framework also yields adaptor signatures that are compatible with today's blockchain systems. More specifically, we devise two general compilers for adaptor signatures. First, we show how to efficiently lift adaptor signatures from structured languages (such as discrete log relations) to general NP languages with the help of degree-$2$ homomorphic encryption, resulting in adaptors for standard signature schemes and general NP languages. Secondly, we develop a compiler that transforms any signature scheme with a subliminal channel into an adaptor signature scheme for general NP languages using circuit-private fully homomorphic encryption. Signatures with subliminal channels enable the encoding of witnesses in the signing randomness, and include randomness-recoverable schemes like Schnorr, ECDSA, CL, BBS, as well as salted versions of deterministic signatures schemes like BLS and RSA. Both constructions achieve a novel property called statement truth privacy, which guarantees that a buyer learns nothing about the underlying statement, not even its truth, unless the protocol successfully completes.

Blind signatures and multi‑signatures are well‑known primitives, but blind multi‑signatures (BMS), which combine both these primitives, were only recently formalized by Karantaidou et al (CCS'24). A BMS scheme allows a user to obtain a compact signature on a common hidden message from a group of signers such that even if the signers collude, they cannot learn the message or link the final signature to any particular interaction. In this paper, we introduce BMuSig2, a 2-round concurrently secure blind multi-signature scheme whose signatures and verification match standard Schnorr signatures. This design enables systems using Schnorr signatures to adopt BMuSig2 as a drop-in replacement, requiring changes only to the issuance phase, while leaving verification unchanged. BMuSig2 builds on MuSig2 multi-signatures (CRYPTO’21) and integrates techniques from a recent blind signature scheme (CRYPTO’24) that leverages non-interactive zero-knowledge (NIZK) arguments and public-key encryption (PKE) to achieve concurrent security. We formally prove the security of BMuSig2 by relying on the unforgeability of MuSig2 and the security of the underlying NIZK and PKE components. We also provide a proof-of-concept implementation to demonstrate its practical efficiency.

As machine learning increasingly moves to edge devices, model owners must trust predictions produced on devices and inputs outside their direct control. This trust is challenged by adversarial inputs, where carefully crafted perturbations can induce incorrect predictions. Existing black-box defenses can detect such inputs using microarchitectural signals, but provide no privacy-preserving mechanism for a remote model owner to verify the detection outcome. In this work, we introduce VERA, a framework for verifiable and privacy-preserving adversarial detection at the edge. VERA combines lightweight Hardware Performance Counter (HPC) monitoring with Zero-Knowledge Range Proofs (ZKRPs). Adversarial perturbations can alter internal activation patterns and consequently the microarchitectural behavior of inference, which can be captured through HPC measurements. Rather than revealing these potentially sensitive measurements, VERA allows an edge device to prove that a committed HPC value lies within a calibrated benign range without disclosing the value itself. This avoids the overhead of general-purpose zk-SNARKs and enables lightweight verification on resource-constrained devices. We formalize VERA as a black-box framework that can combine an HPC-based adversarial detector with an interactive ZKRP, which can also be made non-interactive using the Fiat--Shamir transform. We evaluate VERA against multiple adversarial attacks on MNIST and CIFAR-10. Our results show millisecond-scale verification overhead, with proof-generation costs amortizable across batches of inferences. To the best of our knowledge, VERA is the first framework to provide privacy-preserving cryptographic evidence that an edge inference exhibits microarchitectural behavior within a calibrated benign regime.

We present Symplex, a pairing-based zkSNARK for R1CS that preserves the syntax of Groth16: a $2G_1{+}1G_2$ proof, and a verifier with three pairings and one public-input multi-scalar multiplication (MSM), while {\it strictly reducing prover cost}. For constraint count $n$, wire count $m$, public-input count $\ell$, and $\kappa=\min\{n,m+1\}$, Symplex's prover uses four FFTs of size $n$ rather than the six of our coset-Lagrange Groth16 comparator, and its larger $G_1$-MSM has width $m+n-\ell+4$ rather than the adaptively based Groth16 width $2\kappa+m+n-\ell+3$. The matched Groth16 prover derives three length-$n$ vectors from the R1CS instance, converts each between coefficient and evaluation form, and commits the quotient with a size-$n$ coset-Lagrange column, resulting in six FFTs in total. Its usual monomial quotient column has one fewer CRS element but requires a final inverse FFT. Symplex instead uses the partial-fraction techniques of Jutla, Nema, Roy (EuroCrypt 2026) allowing the output-wire selector polynomials to be precomputed into the per-wire CRS bundles during setup. So, only the left- and right-wire vectors require FFT-based processing at proving time. The verifier is unchanged (three pairings, one public-input MSM). On a BLS12-381 prototype of Symplex that shares sparse R1CS, FFT, and pairing code with Groth16, a Circom circuit chaining SHA-256 ten times gives a $1.84\times$ prover speedup with online verification at $\approx 2.6\,\mathrm{ms}$ for both schemes. The uniform algebraic extraction argument, perfect completeness, and perfect zero-knowledge are machine-checked in Lean~4. Polymath (Lipmaa, CRYPTO 2024) and PARI (Dellepere, Mishra, and Shirzad, USENIX Security 2026) shrink the proof using a squared R1CS arithmetization. Polymath proves soundness in the AGMOS model, and PARI does not provide zero-knowledge in the stated construction. Symplex keeps Groth16's proof shape and standard R1CS arithmetization, and is proved knowledge-sound in the standard Generic Group Model.

Zero-knowledge proofs of set membership underpin privacy-preserving constructions such as ring signatures and anonymous credentials. Existing succinct constructions rely mainly on the Fiat--Shamir transform in the Random Oracle Model (ROM), while standard-model non-interactive proofs from post-quantum assumptions remain either generic and inefficient or asymptotically compact yet concretely impractical. A key obstacle is that existing lattice-based zero-knowledge systems operate over a single ambient modulus, forcing heterogeneous components to be homogenized, inflating parameters and weakening reductions. We introduce the first \emph{compact lattice-based NIZK arguments for set membership in the standard model} with proof size logarithmic in the set cardinality. Our construction matches the logarithmic proof size of accumulator-based ROM constructions while achieving post-quantum security without random oracles. The main technical ingredient is a new trapdoor $\Sigma$-protocol supporting linear relations modulo multiple heterogeneous moduli, allowing such relations to be handled at their native moduli without homogenization. This yields a modular approach to compact proofs compatible with lattice accumulators. As an application, we construct lattice-based ring signatures of size $O(\log R)\cdot \widetilde{O}(\lambda^{2})$ bits, improving the dependence on the security parameter $\lambda$ quadratically over the plain-model construction of Chatterjee et al. (CRYPTO~2021) while retaining optimal logarithmic dependence on the ring size $R$. Our construction is in the CRS model, which partly enables this improvement. The scheme achieves statistical anonymity and unforgeability under standard Module-LWE and Module-SIS assumptions. We also develop two additional tools of independent interest: (i) a generalized Merkle-tree accumulator over module lattices with base-$B$ decomposition, enabling finer efficiency--assumption trade-offs; and (ii) a message-binding technique that removes the need for costly lattice one-time signatures in standard-model ring signatures.

We correct two errors in Section~8 of the above-mentioned paper concerning the seed parameters proposed for BLS27 elliptic curves (embedding degree $k=27$) at the $256$-bit and $192$-bit security levels. In both instances, the disclosed seeds produce a composite $r(x)$, violating the primality condition essential for constructing pairing-friendly curves. Additionally, for the $192$-bit seed the characteristic $p(x)$ is also composite. We provide verified corrected seeds for each security level, obtained by exhaustive search, and confirm with SageMath that both $p(x)$ and $r(x)$ are prime in each case. All other results of the original paper remain valid.

Keyword private information retrieval (Keyword PIR) enables a client to retrieve the value associated with a keyword from a database while keeping the queried keyword private, thereby generalizing traditional private information retrieval, known as index PIR. The state-of-the-art by Hao et al. (USENIX 2025) has several limitations. First, their generic construction requires three invocations of an underlying index-PIR protocol. Second, to reduce this overhead, they propose a specialized design combining SimplePIR with hash tables. However, this approach inherits SimplePIR's large client-side hint, resulting in substantial per-database storage costs on the client side. Moreover, it allows clients to retrieve information beyond the value associated with the queried keyword. In this work, we present a novel and practical Keyword PIR framework that addresses these limitations. Our construction extends the hintless KsPIR scheme of Luo et al. (CCS 2024) to the keyword setting, ensuring that a semi-honest client retrieves only the value corresponding to the queried keyword. The construction leverages the linear homomorphic technique of Peikert and Pepin (TCC 2025). To accelerate homomorphic evaluation, we design a baby-step giant-step (BSGS) implementation and an offline/online decomposition based on a Galois-theoretic formulation. Experimental results show a mean online speedup of $2.65\times$ over the generic framework when instantiated with the same index-PIR scheme, for databases containing up to $2^{22}$ entries.

—Internet-of-Things (IoT) nodes must protect sensed data while operating with limited processing capability, memory, and battery capacity. In August 2025, the National Institute of Standards and Technology (NIST) finalized SP 800-232, which standardizes the Ascon family for constrained devices. This paper presents ASCON-Edge, a reproducible protocol for evaluating the security, performance, memory cost, and directly measured energy cost of standardized Ascon-AEAD128 on resource-constrained IoT nodes. The protocol compares Ascon-AEAD128 with AES 128-GCM and ChaCha20-Poly1305 using identical message sizes, associated data, timing boundaries, build conditions, and security tests. It defines a deterministic workload, a nonce uniqueness and replay policy, a hardware-freeze record, raw-data fields, statistical summaries, direct-energy rules, and functional acceptance criteria. It also separates AEAD guarantees from application-layer responsibilities for replay prevention and key handling. A targeted literature synthesis motivates a final-standard, workload-aware comparison protocol. This is a methodology and reproducibility paper: it reports deterministic packet-format overhead, but deliberately does not claim hardware benchmark measurements before a frozen platform and raw data are available.

We consider methods for scalar multiplication on an elliptic curve where the scalar digits are processed from left to right, that is, from most significant to least significant. We analyze exceptions that may arise during point addition and doubling throughout the multiplication. Eliminating such exceptions is critical for achieving constant-time execution and preventing timing attacks. We establish conditions under which exceptions occur only at the final addition or not at all. Guided by these conditions, one can ensure constant-time behavior by performing all doublings and all intermediate additions using fast formulas that require no exception handling. We examine two variants of the Comb method: SAB-Set and LSB-Set. For both variants, we prove that the constant-time conditions are satisfied under mild restrictions on the base point order and Comb parameters. Additionally, we propose a convenient scalar recoding algorithm for the SAB-Set variant.

Neural networks based machine learning models are used in many classification problems yet privacy issues in model usage are mostly unresolved. When a model owner provides their model to other parties for inference, either the model owner has to share the parameters of the model or the model user must share their query and result with the model owner. Depending on the usage scenario, the user’s query or query result could contain sensitive information that the model provider should not see. And on the other hand, the model parameters themselves could be a valuable business secret or leak private training data. In such cases, neural network inference must be performed in a privacy preserving manner, for example, using secure multi-party computation (MPC). We propose protocols for the private inference of neural networks and evaluate them within the Sharemind MPC secure computation framework. Our protocols are based on the per-tensor quantisation scheme in PyTorch which maps floating point model parameters to 8-bit integer values. Quantisation improves the efficiency of our protocols and our protocols are interoperable with models trained using PyTorch. We extend constant round integer convolution and matrix multiplication protocols for quantised model weights, propose constant round protocols for re-quantising values and analyse the optimal secret share bit width for efficient re-quantisation. The resulting protocols are used to evaluate the VGG16 image classification network with an amortised throughput of 24.3 s per image classification in a LAN setting.

Post-election Risk-Limiting Audits (RLAs) provide statistical guarantees of election outcomes by hand-counting randomly selected paper ballots. However, standard RLAs assume that ballots remain unaltered in storage between election day and the audit, but voters cannot verify this assumption. Prior frameworks, such as VAULT (E-VOTE-ID 2019), attempt to make the audit process verifiable, but they require the public to trust the Election Authority (EA) to honestly sample ballots at random and correctly interpret the voters' choices into cryptographic commitments. Furthermore, they are typically ballot-level, requiring a 1-to-1 mapping between individual paper ballots and digital records. The EA also needs to interactively open commitments during the audit. To address these limitations, we propose the first verifiable batch-level RLA scheme, which shifts the trust anchor from the EA directly to the voter and operates on groups of ballots (batches) to eliminate individual tracking hurdles. Our scheme introduces a peel-and-vote paper ballot design with removable flaps containing pre-printed cryptograms. A voter selects a candidate by removing the corresponding flap, and retains the flap as a receipt, while the same cryptogram printed on the receipt is also published on a bulletin board. In our scheme, a batch contains a group of cryptographically related ballots that are randomly distributed across the precincts before the election. Once all cryptograms in a batch are published, anyone can independently compute the tally for that batch, achieving a self-tallying property. Intuitively, our scheme transforms a national-scale election into many smaller self-tallying elections: one for each batch. Based on historical US election data, we show that when the ballot loss rates remain below 0.5%, the scheme enables tally verification for 61% of randomly selected ballots with a batch size of 100, or 37% with a batch size of 200. These figures are substantially higher than the 0.01-0.3% sampling coverage typically achieved in RLAs. This improvement stems from the fact that auditing is built directly into the paper ballot design in our scheme as an always-on feature, rather than being treated as an optional manual post-election process.

A common pipeline of cryptographic research is: a theory paper asks an interesting question which triggers a line of works; then the problem remains dormant until technology catches up and makes the problem potentially relevant for practice; this triggers a renewed interest which at times pushes the originally theoretical ideas to practice. Several highly influential ideas have followed this pipeline: e.g., the original work on Oblivious RAMs by Goldreich and Ostrovsky [STOC'87\&90], polynomial commitments by Kate, Zaverucha, and Goldberg [ASIACRYPT'10], and many others. A problem that shows early signs of this pattern is early-stopping Byzantine Agreement (esBA): esBA protocols whose round complexity depends on the number $f$ of {\em actually} faulty parties rather than on (an upper bound on) the number $t$ of {\em potentially} faulty parties. Although it is fair to say that esBA protocols are not (yet) within the practical realm, their potential to improve large scale distributed systems like blockchain ledgers has fueled a number of recent novel results pushing the envelope in esBA feasibility (e.g., Loss and Nielsen [EUROCRYPT'24] and Elsheimy, Loss, and Papamanthou [ASIACRYPT'24]). The original starting point of this work has been to advance on the above feasibility questions. But as is common for problems following this trajectory, renewed interest often comes with observations about issues in the assumed definitions and models. Interestingly, our investigation revealed an issue with how the existing literature has been computing the round complexity of such protocols, which yields (previously unobserved) inconsistencies in the literature of esBA and more generally of synchronous protocols. In a nutshell, the inconsistencies stem from the fact that the last round of several esBA protocols has parties terminating as soon as they send a message to other parties, i.e., they don't need to wait to receive messages sent to them in that round. So, should we count this as an extra round or not? As we observe, different works give different answers to this question, and the answer one adopts affects the claimed tightness of the corresponding bounds. Building on the above observation, our work proposes a fine-grained manner of counting synchronous rounds that is both intuitive and resolves these inconsistencies. In a nutshell, our counting distinguishes between rounds in which parties might both send and receive messages, and rounds in which parties only need to send messages. Examining the existing literature through the lens of this round-counting methodology exposes gaps and new open questions in the relevant literature. We resolve these gaps and extend the landscape by several new results.

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.

Evaluating the hardness of the Shortest Vector Problem (SVP) is essential for selecting secure parameters in lattice-based cryptography. The fastest current SVP solvers are based on variants of G6K, but their large memory consumption remains a major bottleneck, making high-dimensional executions difficult. A common strategy for alleviating this memory bottleneck is strong basis reduction preprocessing before a sieve-based algorithm. This strategy can solve SVP instances in higher dimensions than standalone G6K under the same memory constraints, but the time required for basis reduction becomes a major issue. ProPnjBKZ, a fast basis reduction algorithm optimized by Wang et al., is currently used as a promising preprocessing method for solving high-dimensional SVP instances. In this paper, we identify that, in the ProPnjBKZ-based SVP-solving pipeline, memory resources can remain underutilized during the preprocessing phase, since ProPnjBKZ requires less memory than the subsequent high-dimensional sieving process. Based on this observation, we propose AH-BKZ, which exploits such unused computational resources by asynchronously running multiple SVP oracles, thereby accelerating basis reduction. Our experiments show that, compared with ProPnjBKZ-based preprocessing, AH-BKZ reduces the overall runtime by up to 23.1% and by 18.6% on average among successful runs for dimensions 124-148 under comparable peak memory constraints. Moreover, in a supplementary experiment conducted in a larger computational environment, AH-BKZ set new solving records for dimension 163 in the TU Darmstadt SVP Challenge and for dimension 164 in the Ideal Lattice Challenge.

BOGI-based ciphers extend the design space of GIFT by combining 4-bit S-boxes with bit permutations satisfying the ``Bad Output must go to Good Input'' principle. Prior work reduced this space to 41,472 parameter representatives, but did not determine whether their complete differential and linear trail spaces were distinct. We define DC/LC-equivalence in terms of weight-preserving bijections between the differential and linear trail sets of two ciphers for an arbitrary number of rounds, and give sufficient conditions based on permutation characteristics and trail reversal. For each pair of mixing permutations and each 4-bit permutation, we decide exactly whether the required initial word permutation exists. The relations generated by these transformations and trail reversal partition the 41,472 ciphers into 864 classes of size 48 for BOGI-64 and 5,184 classes of size 8 for BOGI-128. Using the BOGI-128 classification, we perform differential and linear best-trail searches through round 20, completing both searches for 5,081 classes. These results and additional threshold decisions show that the earliest round at which both best-trail weights reach 128 bits is round 19, attained by at least 59 classes. The class containing GIFT-128 reaches both thresholds at round 22. Thus, at least 59 classes reach both thresholds three rounds earlier than the GIFT-128 class. We also compare selected BOGI-64 and BOGI-128 instances with GIFT in hardware and software. The resulting security and implementation data can support component selection in future GIFT-based primitives.

We design the first collusion-resistant constrained PRFs (CPRFs) for a non-trivial and expressive class of constraints from standard LWE. The two predicate classes for which we design CPRFs are: compute-&-compare and predicated range constraints. We improve our CPRF for compute-&-compare predicates to also satisfy collusion-resistant constraint privacy. An additional feature of our CPRFs is that they also satisfy (almost-)key-homomorphic property. Prior to this work, we did not have any post-quantum collusion-resistant CPRF beyond prefixfixing constraints, and collusion-resistant CPRFs for expressive predicates relied on either code obfuscation or multilinear maps. As an immediate application, we obtain a two-sided predicate encryption (PE) and functional encryption (FE) for the compute-&-compare class in the symmetric-key setting. Prior to this work, we did not have any post-quantum construction for 2-sided PE/FE beyond inner product predicates. An important contribution of this work is to introduce a new framework of purifying functionality. The main motivation behind our new framework is to systematically eliminate zeroizing attacks, which have been a highly successful cryptanalysis paradigm for breaking various candidates for advanced cryptographic objects.

Bitcoin's proof-of-work (PoW)-based protocol is remarkable for how little it asks of its participants. Not only can miners take breaks from work whenever they please, but it is almost unique in offering a path of contrition: corrupt miners can reclaim honest status simply by resuming mining on the longest chain. The protocol only requires that honest miners hold the majority of computational power at any given time. Analogous proof-of-stake (PoS) protocols, usually formalized via the sleepy model of Pass and Shi (2017), have fallen short of matching this robustness. In fact, sleepy consensus protocols in the plain PKI model must heavily restrict fluctuations in adversarial participation over time. The recent work of Efron, Neu, Pitassi (2025) enables fully fluctuating participation in the sleepy model by introducing the external adversary model. Their protocol, however, relies on verifiable delay functions (VDFs), a strong cryptographic primitive that somewhat resembles PoW, by assuming that the adversary cannot compute sequential work significantly faster than honest nodes. In this work, we design a sleepy consensus protocol for fully fluctuating participation with an external adversary under an honest majority, from minimal assumptions: a public key infrastructure (PKI) and a verifiable random function (VRF). In particular, we make no VDF or hardware assumptions. Our key technique is graded wakeness, a novel primitive that allows nodes to form consistent opinions on which other nodes are awake. We further extend our protocol to handle uncorruption, where corrupt nodes return to honesty. This extension requires only a mild additional assumption on the unpredictability of VRF outputs for liveness.

The Domain Name System (DNS) was conceived with reliability, speed, and scalability in mind, with limited consideration for privacy. Different solutions have been proposed to make DNS more privacy preserving, mostly focusing on confidentiality in transit and networking approaches to achieve unlinkability. However, DNS queries are still observable in plaintext during processing. In this work, we investigate how to achieve privacy against all involved servers through private DNS lookups via single-server private information retrieval (PIR). For this, we design a new PIR protocol that is optimized for the DNS setting. In addition to using ideas from NTTlessPIR (Li et al., CRYPTO 2024), we design a new algorithm to efficiently perform RLWE-based matrix-vector multiplication. As opposed to previous methods, it does not require NTT-friendly plaintext moduli, uses only a single key-switching key, and causes significantly lower noise growth. For a single database of 2 billion entries (the estimated number of domains in the world), our protocol allows clients to perform PIR queries with about 80KB of communication, and less than 5 seconds of server computation time. This outperforms all previous PIR schemes in terms of communication cost, at only slightly increased runtime. Additionally, our end-to-end evaluation of iterative DNS resolution across three nameservers shows sub-second lookups in smaller settings and under 5 seconds with 264KB communication for querying .com domains, which can be practical when used selectively for privacy-sensitive web browsing activities.

Cloud computing has been a prominent technology that allows users to store their data and outsource intensive computations. However, users of cloud services are also concerned about protecting the confidentiality of their data against attacks that can leak sensitive information. Although traditional cryptography can be used to protect static data or data being transmitted over a network, it does not support processing of encrypted data. Homomorphic encryption can be used to allow processing directly on encrypted data, but a dishonest cloud provider can alter the computations performed, thus violating the integrity of the results. To overcome these issues, we propose PEEV (Parse, Encrypt, Execute, Verify), a framework that allows a developer with no background in cryptography to write programs operating on encrypted data, outsource computations to a remote server, and verify the correctness of the computations. The proposed framework relies on homomorphic encryption techniques as well as zero-knowledge proofs to achieve verifiable privacy-preserving computation. It supports practical deployments with low performance overheads and allows developers to express their encrypted programs in a high-level language, abstracting away the complexities of encryption and verification.

Fully homomorphic encryption (FHE) allows a server to run inference directly on encrypted data, making it a promising foundation for private transformer inference. Its dominant scheme, CKKS, has no native matrix multiplication, so the encrypted matrix multiplications at the heart of transformers dominate inference cost. The recent GL scheme supports matrix multiplication natively, but its ciphertexts, plaintexts, and evaluation keys are so large that a direct GPU implementation would require terabytes of VRAM for even small language models. We present Terrazzo, a GPU framework for the GL scheme, co-designed across cryptography, algorithms, and kernels to fit private inference on a commodity GPU. Terrazzo bootstraps into a compact Y-decoded representation, so nonlinear layers never hold full ciphertexts live; tiles all work over GL's independently schedulable ciphertext slices, sizing each tile per level against an L2 and occupancy model; confines grafting-based modulus management to application levels around a sprout-free bootstrap; and keeps every model weight at its cleartext footprint with an expansion-free plaintext pipeline. On BERT-base at full 256-input occupancy, Terrazzo achieves a 7.04 s amortized time per input on a consumer 32 GB RTX 5090. Its A100 time is 29.98 s amortized, a 2.20-20.09x speedup over prior single-A100 systems. Per-slice bootstrap speedup is 1.12–2.03x on the RTX 5090 and 1.08-1.36x on the A100.

Homomorphic computation on large integers requires both arithmetic and non-arithmetic (e.g., Boolean) operations. The radix-based method by Cha et al. (EUROCRYPT'26) supports both operation types over arbitrary $n$-bit integers with a complexity of \(O(\log n)\) and \(O(1)\) bootstrapping, respectively. Meanwhile, the triangle encoding method by Gao and Zheng (CRYPTO'26) has a complexity of \(O(1)\) bootstrapping in arithmetic mode, but is restricted to power-of-two integers. Its arithmetic-to-Boolean (A2B) conversions also needs \(O(n)\) bootstrapping and is only \(O(1)\) in the amortized sense. This work improves both methods by supporting computation over arbitrary moduli with \(O(1)\) bootstrapping for both operation types, and is a generalization of Gao and Zheng's approach. Our first contribution is a framework for efficient homomorphic arithmetic over arbitrary plaintext moduli. It supports flexible radix representations and uses a CVP-based method to find defining polynomials with well-conditioned canonical embeddings and small norm growth under ring operations. When the method fails to find suitable defining polynomials, we use homomorphic Montgomery multiplication over radix-friendly plaintext rings, where each Montgomery reduction requires only $O(1)$ bootstrapping calls. Our second contribution is an efficient arithmetic-to-digit (A2D) conversion using $O(1)$ bootstrapping calls, independent of the radix used by the arithmetic representation. We implemented our method in OpenFHE. For P-384 and Curve25519, our arithmetic multiplication achieves $8.67\sim10.26\times$ and $12.57\sim13.41\times$ lower latency than CPL26's LazyMult and ExactMult, respectively. The speedups increase to $17.47\sim27.24\times$ and $25.35\sim35.63\times$ in the amortized setting. For RSA-1024 and RSA-2048, our arbitrary-modulus multiplication achieves $4.25\times$ and $7.58\times$ lower latency and $16.74\times$ and $29.85\times$ lower amortized time than CPL26's ExactMult, respectively. For 64-, 128-, and 256-bit messages, our A2B conversion is $3.75\times$, $6.40\times$, and $14.17\times$ faster than GZ26, respectively.

We show that for every polynomial $T,b \colon \mathbb{N} \to \mathbb{N}$, there exist an $O(1)$-query probabilistically checkable proof (PCP) for $\operatorname{NTIME}(T)$ of length $\widetilde{O}\bigl(T(n)+b(n)^2\bigr)$, which is $b(n)$-query perfect zero knowledge. This strictly improves on the polynomial-length zero-knowledge PCPs of Gur, O'Connor, and Spooner (STOC 2024; STOC 2025). Our construction builds on the PCPs of Ben-Sasson and Sudan (SICOMP 2008) and Dinur (JACM 2007). We prove the zero-knowledge property of our PCPs via the new machinery of locally simulatable sheaf codes.

Public-key pseudorandom codes (PRCs) combine two seemingly conflicting properties: their codewords are computationally indistinguishable from uniformly random strings, yet a secret-key decoder can recover the encoded message even after a bounded Hamming corruption. Security against chosen-plaintext (CPA) attacks asks that an encoding of a chosen message appears uniform. Security against adaptive chosen-ciphertext (CCA2) attacks additionally gives the adversary adaptive access to a decoding oracle for codewords outside the Hamming ball around the challenge encoding. Döttling et al. (CRYPTO 2026) showed how to realize CCA2-secure PRCs in the standard model through a generic compiler based on the Koppula-Waters hinting pseudorandom generator framework. We give a substantially simpler black-box compiler. Starting from any adaptively $\alpha$-robust, CPA-pseudorandom PRC and using only a secure PRG and an almost perfectly correct IND-CCA2-secure PKE scheme, our compiler constructs an adaptively $\alpha/2$-robust, $\alpha/2$-CCA2-pseudorandom PRC. The compiled PRC has twice the codeword length of the underlying PRC and therefore loses only a factor of two in its relative decoding radius; in particular, it preserves a constant relative decoding radius.

Iasta is a stream cipher designed for hybrid homomorphic encryption (HHE), with claimed $128$-bit security for its Iasta-3 and Iasta-4 instances. In this work, we present the first third-party cryptanalysis of the full-round Iasta-3 and Iasta-4 instances and further extend our approach to Iasta-5. Our cryptanalysis exploits the restricted randomness and structured construction of the nonce-dependent affine-layer matrices. We show that the matrix space contains only $2^{31.30}$ and $2^{19.62}$ distinct matrices for Iasta-3 and Iasta-4/5, respectively, compared with the $2^{29}$ and $2^{22}$ matrix randomness claimed by the designers. This restricted matrix space enables us to construct weak nonces that induce an identical matrix in the final affine layer. For such nonces, we peel off the final Cube transformation, yielding polynomial equations of degree at most $2^{d-1}$ in the secret-key coefficients, which we solve using linearization. We further consider the more restrictive class of nonces that induce identical matrices in both the initial and final affine layers. This allows us to additionally peel off the first non-linear layer, reducing the degree of the resulting equations to at most $2^{d-2}$ at the cost of introducing additional linearization variables. This extended attack substantially improves the attack complexity for Iasta-4 and Iasta-5. For Iasta-3 and Iasta-4, our best estimated attack complexities are $2^{59}$ and $2^{67}$ operations, respectively, under $\omega=2$, reducing the claimed $128$-bit security level to an almost square-root security level. Even under the conservative setting $\omega=3$, the attack requires approximately $2^{80}$ and $2^{82}$ operations against Iasta-3 and Iasta-4, respectively, both below $2^{128}$. For Iasta-5, the extended attack achieves an estimated complexity of $2^{99}$ operations under $\omega=2$. Although no overall security level is explicitly specified for Iasta-5, this result demonstrates that our attack can also reach a complexity below $2^{128}$ for this instance. In all three instances, our attacks reveal a structural weakness in Iasta arising from the restricted space of nonce-dependent affine-layer matrices.

Minimizing the data complexity required to recover the secret key of reduced-round block ciphers is a fundamental problem in symmetric cryptanalysis. Here, we introduce Polytopic Sieving, a data-efficient key-recovery framework and apply it to reduced-round AES. By characterizing the algebraic dependencies of anchor bytes (the reference state values that govern differential transitions across S-boxes), we show that cross-column and cross-row geometric consistency substantially restricts the realizable subkey space. We apply this framework to 4-round AES to achieve a practical key recovery using only 3 chosen plaintexts in $2^{40}$ time complexity or 4 chosen plaintexts in less than $2^{34}$ time complexity. This sets a new benchmark for data efficiency of polytopic attacks, and outperforms other recent techniques such as Subspace Trail Cryptanalysis and Mixture-Integral attacks on very low data targets. Furthermore, we extend our framework to a 5-round attack which requires only 10 plaintexts. By pairing our sieving with a dissected meet-in-the-middle approach, we can reduce both the data and time complexity over the previously best known polytopic attacks. These results establish the lowest data requirements known to date for practical key recovery on 4-round AES.

Vector oblivious linear evaluation (VOLE) is a type of correlation that is widely used in multiparty computation (MPC) and zero-knowledge (ZK) proofs. Recently, the generation of VOLE correlation has become very efficient due to the pseudorandom correlation generator (PCGs) paradigm (Boyle et al. CCS 2018) and SoftSpokenOT (Roy Crypto 2022). This has driven a line of research on VOLE-based ZK, which enjoys linear prover time, low memory cost and post-quantum security. However, most existing works build VOLE and VOLE-based ZK over finite fields, whereas the constructions over integer rings are less satisfactory, especially in terms of communication and public verifiability. In this work, we address some of these problems using a newly introduced primitive called subring VOLE (srVOLE), which is a generalization of subfield VOLE to Galois rings. Specifically, (1) We propose two maliciously secure srVOLE protocols. One is a PCG-like protocol that achieves extremely low amortized communication. The other is a SoftSpoken-like protocol, which is compatible with the VOLE-in-the-head (VOLEitH) technique and thus can be used to construct publicly verifiable VOLE-based ZK. (2) We find that the VOLE correlation over $\mathbb{Z}_{2^k}$ used in Moz$\mathbb{Z}_{2^k}$arella (Baum et al. Crypto 2022) is a special case of our srVOLE. Therefore, based on our construction, their designated-verifier ZK protocol can be made publicly verifiable. (3) We adapt the QuickSilver (Yang et al. CCS 2021) protocols to any Galois ring and compare with existing VOLE-based ZK protocols over rings. For circuit satisfiability, our protocol only communicates 1 subring element per multiplication gate, reducing the communication by more than half. For polynomial satisfiability, our protocol supports arbitrary low-degree relations, overcoming the restrictions of existing work on degree-2 relations.

Mixnets provide network-level anonymity, traded off with increased communication latency, which consequently limits their applicability to only latency-tolerant applications, shrinking the anonymity set to clients engaged in such use cases. Addressing this issue requires optimizing latency, as recently explored in LARMix (NDSS’24) and LAMP (NDSS’25) through node arrangement and strategic routing. However, these approaches are tailored to specific mixnet designs, rely on simplified models and trust assumptions, or suffer from limited practical efficiency. In contrast, OptiMix bridges these gaps by introducing a general low-latency mixnet model adaptable to all well-established designs. To this end, we first propose an efficient distributed protocol for arranging nodes in mixnets that achieves low-latency properties while maintaining unbiasability against adversaries. Second, we introduce novel strategic routing schemes that optimize communication latency. Third, we design a load-balancing algorithm that evenly distributes traffic without undermining the latency-optimized characteristics of the routing strategies. Fourth, we conduct extensive evaluations using data from the deployed Nym mixnet, demonstrating substantial latency reductions with minimal anonymity loss across various mixnet designs—achieving up to $4\times$ performance gains over state-of-the-art solutions. Finally, considering that latency reduction incurs either anonymity degradation or increased bandwidth overhead—as stated by the anonymity trilemma—we propose a cover-routing mechanism that enables clients to benefit from low-latency mixnets without compromising anonymity, at the modest cost of generating additional cover traffic.

Fully homomorphic encryption (FHE) allows a server to run a language model directly on encrypted user prompts, but current approaches remain prohibitively slow. Ciphertexts natively support only addition, multiplication, and rotation, and multiplications may be composed only to a bounded depth before a costly bootstrapping operation is required to continue. Every nonlinearity must therefore be approximated by an iterative method; each iteration increasing the number of multiplications. A higher iteration count buys precision but exhausts the available depth more frequently and thus triggers more bootstraps, which dominate latency. We introduce Homomorphic Encryption-Aware Training (HEAT), a fine-tuning method that makes the per-nonlinearity iteration counts learnable, enabling them and the model weights to co-adapt during training. HEAT optimizes iterations with respect to the task objective, allowing the model to adapt to approximation errors encountered during inference without architectural changes or retraining from scratch. We further relate iteration count to quantization bit width and bound, at fixed weights, the gap between our objective and quantization-aware training. On encrypted GPT-2 decoding, HEAT reduces iterations by $3.1\times$, bootstraps by $1.6\times$, and end-to-end latency by $1.4\times$, while improving decode agreement over the calibrated encrypted baseline.

We put forward a generalization of attribute-based signcryption, called anonymous attribute-based signcryption (A$^2$BSC). Beyond message confidentiality and ciphertext unforgeability, A$^2$BSC further requires \textit{ciphertext anonymity}: no information about the signcryptor's attributes or ciphertext-related attributes/policies is leaked, regardless of the decryption outcome. Specifically, we begin by establishing the syntax and security notions for A$^2$BSC within a \textit{unified} framework, which encompasses various variants (key-policy, ciphertext-policy, dual-policy, and a hierarchical dual-policy variant called Special A$^2$BSC). Then, we construct a Special A$^2$BSC scheme for \textit{general policies} (modeled as bounded-depth Boolean circuits) from the succinct learning with errors and the basis-augmented short integer solution assumptions in the standard model, hence achieving post-quantum security. This naturally yields lattice-based instantiations of both ciphertext-policy and dual-policy A$^2$BSC. Beyond its independent interest, we also show the expressiveness and generality of our A$^2$BSC by exploring its application to matchmaking encryption (ME) and arranged matchmaking encryption (AME) proposed by Ateniese et al. (Crypto '19). As a byproduct, we give generic constructions of both ME and AME for \textit{arbitrary policies} against unbounded collusions, and strengthen the CPA-privacy of (A)ME to achieve CCA security. The latter is achieved for free in our construction, as A$^2$BSC natively provides CCA security. Overall, our new solution enhances the diversity of approaches for building the advanced primitive (A)ME.

This work studies asynchronous verifiable secret sharing (AVSS) and asynchronous multi-party computation (AMPC) in the blockchain-hybrid model, where parties have black-box access to an ideal (asynchronous) blockchain functionality providing only persistence and eventual liveness. Motivated by the practical deployment of MPC in blockchain applications such as privacy-preserving payments and threshold wallets, we investigate whether blockchain access can improve the classical resilience bound of $n > 3t$, where $n$ is the total number of parties, and $t$ is the number of parties that can be compromised by an adversary. In particular, in the blockchain-hybrid model, we provide a comprehensive set of lower and upper bounds across three cryptographic settings: (i) no trusted setup, (ii) trusted setup with Minicrypt assumptions, (iii) trusted setup with public-key assumptions. 1. We show that without a trusted setup, or under Minicrypt assumptions, even with a setup, the classical resilience bound for AMPC is inherent: AMPC is impossible for $n \leq 3t$, even against weaker fail-stop or omission adversaries. 2. We establish separations between AVSS and AMPC in the intermediate regime $2t < n \leq 3t$: against a fail-stop adversary, unlike AMPC, AVSS is possible for $n>2t$ without any setup. Moreover, against a Byzantine adversary, again unlike AMPC, AVSS is possible for $n>2t$ under Minicrypt assumptions with a setup. 3. In contrast, under public-key assumptions with trusted setup, we construct an AMPC protocol tolerating Byzantine adversaries whenever $n>2t$. Our protocol leverages threshold homomorphic encryption, threshold signatures, commitments, and zero-knowledge proofs to minimize on-chain communication, achieving blockchain communication complexity independent of the circuit size. In the process, we define an efficient agreement on a common subset primitive for large messages in the blockchain-hybrid model, which can be of independent interest for secure distributed computing systems.

This paper presents a new randomized algorithm for solving the exact shortest vector problem. For the $n$-dimensional lattice $\mathcal L$, our algorithm runs in time and space $2^{n/2+o(n)}$. Our algorithm can be viewed as a $q$-ary analogue of the midpoint Hessian for an odd prime $q$; more precisely, we use the fact that, for a shortest vector $v$, the gradient (rather than Hessian) of the periodic Gaussian function at $v/q$ is nearly proportional to $v$ (up to sign), even after aggregation over a relatively large random affine coset. We compute the relevant coset gradient along a chain of intermediate lattices using a combinatorial procedure inspired by Wagner's generalized birthday algorithm, yielding the $2^{n/2+o(n)}$ time and space complexity. A variant of the algorithm solves the exact closest vector problem on every input $(y,\mathcal L)$ with a distance guarantee $\operatorname{dist}(y,\mathcal L)\le 1.039\lambda_1(\mathcal L)$ within the same time and space complexity. This guarantee holds for a random target and a random lattice drawn according to the Haar-Siegel measure. Thus, this algorithm solves a closest vector problem on such random instances in time and space $2^{n/2+o(n)}$.

To the best of our knowledge, existing differential-neural cryptanalysis have not yet shown a clear round advantage over the strongest comparable classical analyses. Recent Fourier-based interpretability results show that, under a difference-only representation, features extracted from differential-neural distinguishers can be interpreted as classical differential-linear masks. This suggests a possible route toward longer-round classical cryptanalysis and motivates our question: can such neural-discovered masks serve as useful candidates in the search for long-round differential-linear distinguishers of ARX ciphers? As a prerequisite to the long-round study, we first characterize the short-round differential-linear candidates exposed by difference-only differential-neural distinguishers. We introduce Conv1DFully to facilitate mask-level analysis by removing the residual tower and reorganizing the first convolution along the ciphertext-difference bit dimension. On Speck32/64, the dominant differential-linear feature remains preserved after these modifications. On SipHash, we compare Fourier masks extracted from trained distinguishers with an exhaustive evaluation of a low-Hamming-weight output-mask space. The neural-extracted masks are concentrated among high-correlation differential-linear approximations, including several of the strongest candidates examined. These experiments provide a controlled basis for treating neural-extracted masks as candidates in the subsequent long-round analysis. We then examine their utility in the known 18-round Speck128/128 distinguisher with a 5+8+5 decomposition. Under the same middle input difference, an 8-round difference-only differential-neural distinguisher recurrently exposes several masks with substantially stronger local middle correlations than the classically selected mask. However, after 5-round single XOR-linear extensions, these masks yield considerably weaker overall 18-round correlations. We further impose sparsity guidance on the first convolutional layer to promote low-Hamming-weight candidates. Under this guidance, the intermediate mask used in the classical 18-round distinguisher is recovered in the first-layer candidate set in 9 of 30 independent runs, showing that the neural model can reproduce a long-round-useful classical candidate. Nevertheless, this recovery is not stable, and the final neural decision rule still favors locally stronger features rather than the classically selected mask. These results indicate that differential-neural distinguishers can assist long-round candidate generation, while reliable recovery and long-round-aware prioritization remain unresolved.

Folding schemes compress many instances of a relation into a single accumulated one and, via composition with the Fiat-Shamir heuristic, yield SNARKs for arbitrarily large computations. However, essentially every folding scheme beyond Nova itself (including the lattice-based SuperNeo [NS26], LatticeFold(+) [BC24,BC25], and Cyclo [GLLO26]) is only randomizing, not blinding (i.e. honest-verifier zero-knowledge): its folding transcript leaks information about the witnesses being folded. We present LatticeBlindFold, a first lattice-based, plausibly post-quantum-secure analogue of the NovaBlindFold protocol [KS23,KS25], obtained by making SuperNeo blinding. This is a first step, intended to establish feasibility; for simplicity we restrict to the interactive setting. We also hope the note serves as a record of the difficulties one encounters in achieving zero-knowledge for lattice-based folding schemes. Our central technical device is the ABDLOP commitment scheme [BDL+16,LNP22], used as a commit-and-prove backbone. We mask SuperNeo's Sum-Check transcript via Libra-style polynomial masking, replace its plaintext evaluation hints with ABDLOP commitments checked homomorphically, and employ rejection sampling so that the randomized folded instance-witness pair, salts included, is simulatable. Since ABDLOP is only known to be secure over the base ring R_F and not over the extension ring R_K that SuperNeo's Sum-Check runs over, we give a component-wise instantiation of ABDLOP over R_K, translating every relation into a pair of R_F-relations once, at the level of public parameters. The resulting protocol is complete, knowledge-sound, and blinding (when a single fresh R1CS instance is folded), with security reducing to Module-SIS/Module-LWE assumptions over cyclotomic rings (together with the Extended-MLWE variant of [LNS20]). Completeness moves from perfect completeness to a statistical one, due to the introduction of rejection sampling. The price of blinding is paid through the parameters rather than the asymptotics. Rejection sampling forces a norm-decomposition depth k = Θ(log n_F), whereas SuperNeo needs only k = Θ(1). We record as a corollary an accumulator-free variant, dropping the prover-sampled blinding pairs that the main protocol carries for interface compatibility with SuperNeo's folding step, which saves a few decomposition digits (k = 26 rather than 31 at our parameters) at no cost in blinding. At a matched k the two schemes agree in prover time, verifier time, and communication up to constant factors, but measured against SuperNeo at its native parameters LatticeBlindFold carries a Θ(log n_F) multiplicative overhead in all three. Once again, all security figures we quote are interactive; a Fiat-Shamir transform instantiation would require a higher degree fields while here we focus on degree 2 for simplicity of exposition. LatticeBlindFold inherits SuperNeo's compatibility with small-field arithmetic and offers a modular, plausibly post-quantum-safe route to introducing zero-knowledge on top of a SNARK. We stress the shape of what we prove here: the LatticeBlindFold step is a single interactive step, taking its input uncommitted and outputting k committed evaluation claims together with the ABDLOP openings certifying them. Turning it into a deployable wrapper requires a decider for those claims, whether by having a downstream verifier consume them directly or by arithmetizing the ABDLOP verification; we do not construct one here, and neither recursive composition nor the instance-in/instance-out folding interface is claimed. This work is directly motivated by the Jolt Atlas zkML framework [BCDG26].

Let $q$ range over primes congruent to $3$ modulo $4$. Let $\zeta_q$ be a primitive $q$th root of unity, and put $K=\mathbb{Q}(\zeta_q)$, with ring of integers $\mathcal{O}_K=\mathbb{Z}[\zeta_q]$. We prove that the decision version of the Shortest Vector Problem ($\mathrm{SVP}$) in the $\ell_2$-norm is $\mathrm{NP}$-complete on full-rank free submodules of $\mathcal{O}_K^2$ by a deterministic polynomial-time many-one reduction from Exact Cover by 3-Sets (X3C). The module rank is fixed at two. As a $\mathbb{Z}$-lattice, the module has rank $2(q-1)$, which grows with $q$. The main obstacle is closure under the action of $\mathcal{O}_K$. A module containing a nonzero vector also contains every scalar multiple of that vector by a nonzero element of $\mathcal{O}_K$, and some of these multiples may be shorter. Three ideas overcome this obstacle. First, we map the Bennett--Peikert Reed--Solomon lattice to a principal cyclotomic ideal and use Wan's point-count estimates to prove that a coset of this ideal contains many binary coefficient representatives. Second, a checker based on a quadratic Gauss sum turns the X3C equations into a canonical squared norm. Third, the checker and a second module coordinate combine with a separation bound for ideal cosets to rule out every unintended vector created by the $\mathcal{O}_K$-action. Each constructed instance consists of a prime $q\equiv3\pmod4$, two integral generators whose $2\times2$ generator matrix has nonzero determinant, and an integer squared threshold. The construction also gives $\mathrm{NP}$-hardness of search-$\mathrm{SVP}$ under polynomial-time Turing reductions.

Digital identity systems are becoming increasingly prevalent, driven by regulatory efforts such as the European Digital Identity (EUDI) Wallet. Yet these systems usually do not achieve strong privacy guarantees as offered by anonymous credentials, since they rely on standardized curves and widespread signature schemes like ECDSA that are incompatible with pairing-based primitives underpinning most anonymous credential constructions. Recent work bridges this gap by retrofitting such legacy credentials with anonymous-credential properties via zero-knowledge proofs, requiring no issuer-side modifications. However, none of these constructions supports delegation: the ability for users to pass on a restricted credential derived from their own to another party, while all parties along the delegation chain maintain full anonymity. Delegatable anonymous credentials (DACs) provide exactly these guarantees, but are likewise incompatible with existing deployments. We present the first DAC scheme built directly on top of legacy credentials. Our construction requires no issuance infrastructure changes, and yields constant-size credentials independent of delegation depth, with full unlinkability along the chain and selective attribute disclosure at every level. We instantiate it for credentials based on JSON Web Tokens (JWTs) signed with ECDSA using Plonky2 as the recursive proving backend, contributing a secure in-circuit JWT parser that closes vulnerabilities in prior work and a Plonky2 extension for cyclic recursion with per-step zero-knowledge. At 64 attributes, delegation takes 1.2 s and verification only 3.3 ms, with a constant proof size across all delegation levels

NTRU-based encryption enjoys compact keys and ciphertexts and admits non-interactive distributed decryption, making it an attractive basis for threshold encryption with applications to threshold FHE, threshold signatures, and electronic voting. All known protocols, however, assume a secret key shared by a trusted dealer. The public NTRU key $h = f^{-1}g$ is a nonlinear function of the secret, so distributed key generation (DKG) techniques for LWE-based schemes do not apply, and generic MPC is prohibitively expensive. We present the first dedicated DKG protocol for NTRU. Each party publishes an NTRU sample, defining a joint public key whose secret key is shared multiplicatively, and a multiplicative-to-additive (MtA) conversion yields the additive sharing required for non-interactive decryption. The protocol runs in few rounds and is actively secure with abort. At the heart of our DKG lies the MtA conversion, for which we give two efficient lattice-based certified constructions; one from additively homomorphic NTRU encryption and one from homomorphic secret sharing, both of which may be of independent interest. We demonstrate the protocol by building a threshold variant of NTRU-Encrypt, which we prove secure and instantiate with concrete parameters.

Cryptographic protocols are the foundation of secure digital communication, yet their design remains error-prone, as evidenced by the vulnerabilities that have plagued even the most widely adopted protocols throughout history. Security properties are typically formalized using either trace properties or indistinguishability, each addressing distinct security guarantees, such as agreement and authenticity for the former and anonymity and strong secrecy for the latter. Formal verification of cryptographic protocols spans both symbolic and computational models. While symbolic techniques enable automation and scalability, they do not provide computational security guarantees. Computational models, though robust, are harder to formalize and automate. Recent advances, such as the Computationally Complete Symbolic Attacker (CCSA) model and its logic, the Bana-Comon Logic (BC Logic), bridge this gap by supporting both trace properties and indistinguishability. However, despite significant progress in proof assistants, automating indistinguishability remains a challenge due to its combination of unstructured equality theories, complex non-classical calculus, and partially inductive reasoning—all requiring expert knowledge in both cryptography and logic. This paper introduces a novel approach to automate indistinguishability proofs in the CCSA model, implemented in the automated prover CryptoVampire2. We extend CryptoVampire to support indistinguishability by designing golgge, a Prolog-inspired backtracking engine over equality graphs (e-graphs), which provides strong, rewrite-driven equational reasoning capabilities. We adapt the BC Logic rules to this new framework, yielding semantically compatible statements. The effectiveness of our approach is demonstrated by automating all indistinguishability goals in the Squirrel repository.

Under-constrained arithmetic circuits are a recurring source of soundness failures in zero-knowledge applications: after fixing the public statement, a malicious prover may be able to assign a security-relevant wire in more than one way while still satisfying the circuit. Existing tools attack this uniqueness question with solver-based checking, direct polynomial solving, abstract interpretation, or fuzzing. We study a complementary algebraic diagnostic based on exact Jacobian linear algebra. The method separates three notions that are often conflated: first-order rigidity at a sampled witness, finite algebraic dependence on an irreducible component, and uniqueness over the circuit field. At a satisfying assignment, the kernel of the constraint Jacobian augmented with rows fixing the statement coordinates is the Zariski tangent space of the corresponding fibre scheme, so motion of a target coordinate in this kernel certifies infinitesimal freedom at that witness. Under suitable separability hypotheses, the associated differential representation also recovers component-wise algebraic dependence, while a certified triangular degree calculus provides multiplicity bounds for locally rigid targets. An exact sparse implementation classifies public benchmarks (chain, tree, Merkle-path, and EdDSA topologies, up to 66,000 constraints) in at most a second per instance on commodity hardware, has been exercised on industrial gnark circuits in the 6k-60k-constraint range, and carries over to PLONKish standard-gate systems in a measured end-to-end check (lookup arguments remain future work); a checkable degree budget (m < log₂ p quadratic constraints) discharges the separability hypothesis at gadget scale. Conversely, when the rank computation itself certifies a smooth witness (full row rank, or full rank after vacuous guard rows are discharged by explicit local-redundancy identities), effective Lang-Weil bounds convert infinitesimal freedom into at least p/(2 deg C) distinct finite-field values of the target among genuine satisfying assignments, so in that regime the local diagnostic becomes a sound non-uniqueness certificate. For quadratic constraints, an additional affine-line certificate converts a tangent vector into p explicit satisfying assignments whenever every quadratic directional coefficient vanishes; its checker uses sparse field evaluations and needs no smoothness assumption. A second-order parabola variant extends the construction to curved families through one further linear solve, certifying targets that first order cannot move. Projected tangent dimension distinguishes the number of free target wires from their independent degrees of freedom. The principal limitation is witness locality, and we state it as a theorem rather than an observation: an explicit 20-constraint instance admits two satisfying assignments agreeing on the statement such that every target is first-order rigid at one while all five targets are infinitesimally free, indeed p-fold free, at the other. The same separation occurs in deployed code: in a measured 2,396-constraint gnark 0.14.0 scalar-multiplication gadget, an honest witness exposes no free target wires, a degenerate adversarial witness exposes five, and an explicit second satisfying witness confirms the freedom. We therefore position Jacobian analysis as a scalable candidate detector and localisation tool, to be combined with adversarial witness generation and solver- or certificate-based confirmation.

We present an open dataset of electromagnetic (EM) traces captured during the decapsulation operation of ML-KEM (Kyber), the key encapsulation mechanism standardised by NIST in FIPS 203. Each trace is windowed on a single pair-pointwise polynomial multiplication, in which the decapsulation key is one of the operands, making it a recurring target of published side-channel key-recovery attacks. The dataset covers three widely used implementations: the CRYSTALS reference implementation, the Cortex-M4 optimised pqm4 implementation, and the first-order masked mkm4 implementation, with 200k traces per implementation. For the masked implementation we release the traces of both shares, enabling first-order leakage assessment and share-wise analysis rather than attacks on unprotected code alone. All measurements were taken on an STM32F407 Cortex-M4 microcontroller using a near-field EM probe. Compared to previously published datasets targeting the same operation, which provide power measurements of the unprotected reference implementation only, this dataset contributes an EM modality and covers optimised and masked code. The traces and the associated sensitive variables are distributed as chunked NumPy arrays, so that researchers without access to measurement equipment can reproduce and extend side-channel analyses of ML-KEM.

Threshold secret sharing schemes (TSSS) enable a dealer to distribute a secret among multiple participants such that only authorized subsets can reconstruct the secret while unauthorized subsets obtain no information. Existing secret sharing schemes (SSS) are often constrained by limited secret size, non-threshold access structures, or the absence of mechanisms for verifying the authenticity of shares and the integrity of the reconstructed secret. In this paper, we propose a novel $(k,n)$-threshold secret sharing scheme based on linear Maximum Distance Separable (MDS) codes. The proposed construction supports the sharing of comparatively larger secrets by representing the secret as a matrix over a finite field and exploits the linearity of MDS codes to achieve efficient share generation and reconstruction. To strengthen reliability, the scheme incorporates cryptographic hash functions for share authentication and integrity verification of the reconstructed secret. We prove that the proposed scheme satisfies correctness and perfect secrecy, thereby providing unconditional security against unauthorized coalitions. Experimental evaluation demonstrates that the proposed construction achieves efficient share generation and reconstruction while outperforming existing code-based secret sharing schemes in terms of supported secret size, scalability, and practical runtime.

Open-weight models allow clients to run LLMs locally, thus keeping their data private from untrusted providers. However, running large models requires massive hardware and storage resources (especially challenging on resource-constrained devices like smartphones), limiting local execution to smaller models. This leaves clients with a frustrating compromise: settle for a less-capable model that can be run locally, or sacrifice privacy by sending queries to an external server. We present an efficient protocol that allows a client to privately and verifiably outsource LLM inference of an open-weight model to a pair of malicious (but non-colluding) servers. Privacy implies that neither server learns anything about the client's queries. At the same time, the client can verify the claimed result using information posted by the model owner along with the model weights. Compared to prior state-of-the-art for private LLM inference (SIGMA, PETS' 24) -- which does not provide verifiability -- our protocol is $\approx$11--14$\times$ faster while imposing no overhead at the servers (beyond the cost of inference in the original model). Our protocol also scales to larger models not supported by prior work: for example, with our protocol a client can run the Llama 2-70B model using just 179~MB of local storage (instead of the 140~GB required to run the model locally).

The Wrong-Key Randomization (WKR) hypothesis governs data-complexity estimates in differential cryptanalysis: wrong-key guesses are assumed to behave as a random permutation would. Exact computation of fixed-key differential probabilities was, until recently, infeasible. We use quasidifferential trails to compute the exact wrong-key distribution for the key-recovery map \(G_{k,k'} = F_{k'}^{-1}\!\circ F_k\) in PRESENT-like SPNs. A mask-first reformulation exposes a Walsh--Hadamard structure; restricting the transform to the low-dimensional support, together with SMT-guided trail enumeration, reduces the cost: for a 16-bit toy cipher, from~\(2^{80}\) to~\(2^{13}\); for \presentCipher, from~\(2^{192}\) to~\(2^{30}\); and for GIFT, from~\(2^{192}\) to~\(2^{32}\). For the toy cipher, PRESENT and GIFT, the computed distribution is a structured mixture: a large zero-probability class coexists with bottleneck classes orders of magnitude above the random-permutation mean, and nothing lies between them. Such a distribution is not unimodal, so no Poisson or binomial law fits it for any parameter and the hypothesis is formally false for all three targets. For PRESENT, however, we show that this deviation does not affect the security of Wang's 14-round differential attack. We cast the computed distribution as a structured composite hypothesis---the differential counterpart of the random-permutation/composite-hypothesis model used for wrong keys in linear cryptanalysis--and show that the shape of the wrong-key distribution, not merely its mean, governs how many wrong keys survive the key-recovery filter. For PRESENT with Wang's distinguisher, the structural signal is carried only by the right pairs, whose weight is too small for the deviation to surface; the hypothesis remains a safe heuristic in this case despite being formally false. Our SMT-based enumeration tool is publicly available.

Bootstrapping is the computational bottleneck of BGV/BFV fully homomorphic encryption, scaling particularly poorly with large plaintext primes. Its two dominant stages: digit extraction and linear transforms. Recent work has reduced the digit-extraction polynomial degree via null-polynomial lattices and bounded-support constructions, but both evaluate the reduced polynomial via generic Paterson--Stockmeyer at cost $O(\sqrt{d})$ . We present two algebraic optimizations that address both stages simultaneously. For digit extraction, we prove that choosing the auxiliary radix $A$ with $A^2\equiv -1\pmod{p}$ induces an order-four character filter, forcing the canonical digit-extraction polynomial to satisfy $P_A(AX)+AP_A(X)=AX$ and eliminating all monomials $X^k$ with $k\not\equiv 1,3\pmod{4}$. The resulting structured decomposition$P_A(X)=\tfrac{1}{2}X+X^3Q(X^4)$ reduces non-scalar multiplications from $O(\sqrt{d})$ to $O(\sqrt{d/r})$. For linear transforms, we provide first concrete instantiation of a Galois-structured mixed-radix butterfly decomposition for non-power-of-two cyclotomics, reducing the automorphism count from $O(\sqrt{D})$ to $O(\log D)$. On the standard NTT-friendly large-prime set ($p=65537$, $m=2^{16}$, $32768$ slots), our single-threaded \HElib{} implementation achieves a $1.85\times$ digit-extraction speedup ($20.06$s to $10.81$s) and a $1.27\times$ total thin-bootstrapping speedup ($42.3$s to $33.3$s) over the state-of-the-art Ma et al.\ baseline, the three stages the method does not touch moving by at most one per cent. All comparisons are made against the Ma et al.\ baselines, run in the identical pipeline at the same auxiliary radix; across nineteen encrypted parameter sets with $1297\le p\le 65537$, the digit-extraction speedup is $1.72$--$1.88\times$ on general cyclotomic rings ($37637\le m\le 65047$) and $1.84$--$2.13\times$ on the power-of-two ring $m=2^{16}$. Every set we recommend is quoted with concrete bit security.

When communication systems are subject to strict external control, a powerful authority may monitor all transmitted messages and compel users to surrender their secret keys, thereby undermining user autonomy and the confidentiality of keys in encrypted communication. Anamorphic encryption (AE) enables covert communication under such surveillance by embedding hidden messages into innocent-looking ciphertexts. However, existing lattice-based AE constructions remain limited and typically rely on lattice trapdoor techniques, which impose restrictive parameter requirements and hinder their deployment in practical post-quantum cryptosystems such as Kyber. Moreover, existing constructions do not address the challenge of enabling covert communication among multiple parties under dictator-controlled environments. In this work, we propose \textbf{Threshold Anamorphic Encryption (TAE)}, a new cryptographic primitive that extends receiver-AE to the \textbf{$N$-out-of-$N$ threshold setting}, where the covert message can be recovered only through the collaboration of all $N$ participants. Then we propose \textbf{TAKyber}, a concrete instantiation of TAE constructed from the KyberPKE framework. TAKyber embeds covert information into the randomness of ciphertexts rather than the public matrix structure, avoiding the large aspect-ratio requirement imposed by lattice trapdoor techniques and enabling deployment on Kyber and other lattice-based encryption schemes whose public matrices do not satisfy such requirements. Furthermore, TAKyber distributes covert information into multiple components during encryption and enables \textbf{all $N$ participants to jointly reconstruct the covert ciphertext}, while preventing any subset of fewer than $N$ participants without the double key from obtaining any information about the covert message. Finally, we apply TAKyber to privacy-preserving federated learning, where participants can securely exchange encrypted model gradients while simultaneously transmitting covert information through the anamorphic channel under dictator-controlled environments.

In this work we present a new variant of the non-interactive key exchange (NIKE) scheme based on the learning with errors (LWE) assumption and prove its security with a security reduction that incurs a security loss that is only linear in the number of users. This improves upon all prior reductions for lattice-based NIKE schemes, which had a security loss that is quadratic in the number of users. Our tight reduction can handle the setting with super-polynomial modulus-to-noise ratio and negligible correctness error as well as the more challenging setting with polynomial modulus-to-noise ratio and inverse polynomial correctness error. We also give a matching lower bound on the tightness for a natural class of lattice-based NIKE schemes (that captures all existing variants of lattice-based NIKE), showing that our security loss is optimal (up to constant factors). This generalizes a lower bound by Hesse, Hofheinz and Kohl (Crypto 2018) and is the first lower bound for the tightness of lattice-based NIKE schemes. Several previous lower bounds for the tightness of NIKE exist, but none of them can be applied to lattice-based schemes.

Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS) gave a $2^{n+o(n)}$ time algorithm for the Shortest Vector Problem (SVP) based on discrete Gaussian sampling (DGS), together with an honest sampler producing $2^{n/2}$ samples above the smoothing parameter in $2^{n/2+o(n)}$ time and space. Gao, Feng, and Hu (GFH) subsequently introduced DGS on random prime-index superlattices, making this sampler available at the shortest vector scale and obtaining a $2^{0.7314n+o(n)}$ time algorithm. In a different direction, the Becker--Ducas--Gama--Laarhoven (BDGL) sieve uses spherical product codes to find correlated pairs and runs in $2^{0.2925n+o(n)}$ time under the random list heuristic. We combine the random superlattice DGS framework with a single BDGL product code decoding layer. The algorithm splits the DGS output into two lists. For a fixed shortest vector $v$, the Gaussian midpoint identity turns the event $X-Y=v$ into a birthday event, while equal quotient labels certify that the reported difference belongs to the input lattice. The product code decoder locates the corresponding pair without enumerating all pairwise differences. Our analysis makes no random list assumption. For a fixed shortest vector $v$, once the retained lists contain a pair $x,y$ with $x-y=v$, the BDGL product code finds that pair with high probability. We extend the product code analysis so that this guarantee is compatible with the claimed time and space bounds. A centered quotient line gives a $2^{0.5822n+o(n)}$ time algorithm. We then replace the line through the zero residue with a random affine translate. This lets us target a rarer midpoint shell. As a result, we obtain a randomized classical algorithm for SVP that runs in $2^{0.5596n+o(n)}$ time and uses $2^{n/2+o(n)}$ space.

ARX-based cryptographic primitives have received considerable attention for their efficient software implementations. For a long time, however, constructing ARX primitives with provable resistance against single-trail differential and linear cryptanalysis remained an open problem. Dinu et al. addressed this problem by introducing the Long Trail Strategy (LTS), the first general design strategy for establishing such bounds for ARX symmetric-key primitives. A remaining challenge in applying LTS is the systematic design and analysis of large-state S-boxes that combine efficient implementation with strong multi-iteration differential and linear bounds. More recently, Yan et al. introduced a general framework for designing and analyzing such S-boxes, with the AFS family serving as a concrete instantiation. Given their excellent multi-iteration security bounds and outstanding software implementation efficiency, AFS boxes offer a viable solution to the core challenging problem in ARX cryptography—systematic design, accurate analysis, and the pursuit of an extreme and compact balance between cryptographic security and implementation performance. We thus argue that the potential of AFS boxes as nonlinear components in LTS-based primitives has long been undervalued. To demonstrate this potential and address the broader design challenge, we use AFS-64 to construct APEX, an efficient and extensible family of cryptographic permutations spanning state widths from 64 to 1536 bits. We then instantiate APEX in a broad range of symmetric primitives to demonstrate its extensibility and translate the security and implementation advantages of AFS into complete cryptographic designs. These include small-state hash functions and extendable-output functions, authenticated encryption with associated data (AEAD) schemes, an ultralightweight block cipher, large-state block and tweakable block ciphers, and large-state hash functions based on the Sponge-F mode and designed for China's Next-Generation Commercial Cryptographic Algorithms program. We derive differential and linear long-trail bounds for the underlying permutations and adapt the long-trail analysis to rate-restricted, same-capacity, and related-tweak settings. Together with analyses of other major attack classes, these results support the selected step counts and the stated security claims. Optimized implementations on 8-bit AVR, 32-bit ARMv7-M, and x86-64 demonstrate the practical software efficiency of APEX across diverse processor architectures. For 64-byte (resp. 1536-byte) messages, the small-state APEX-HASH functions achieve $1.14\text{--}1.37\times$ (resp. $1.14\text{--}1.17\times$) and $1.15\text{--}1.16\times$ (resp. $1.18\text{--}1.20\times$) the throughput of the corresponding Esch instances on AVR and ARM, respectively. The small-state APEX-AEAD schemes similarly achieve $1.17\text{--}1.48\times$ (resp. $1.14\text{--}1.19\times$) and $1.15\text{--}1.19\times$ (resp. $1.12\text{--}1.15\times$) the throughput of the corresponding Schwaemm instances. For the large-state hash functions targeting the NGCC program, $\mathrm{APEX}_{1536}^{12}\text{-HASH-F-512}$ achieves $2.09\times$ and $2.88\times$ the throughput of the fastest listed SHA3-512 implementations on x86-64 and ARM, respectively, for a 1-MiB message. The higher-security $\mathrm{APEX}_{1536}^{16}\text{-HASH-F-768}$ and $\mathrm{APEX}_{1536}^{20}\text{-HASH-F-1024}$ profiles achieve 6.02 and 11.82 cycles/byte on x86-64, and 123.72 and 239.63 cycles/byte on ARM, respectively. For block-cipher applications, the ultralightweight $\mathrm{APEX}_{64}^{8}\text{-BC-128}$ achieves encryption and decryption speedups of $1.18\text{--}1.21\times$ over CRAX-S across AVR and ARM, while the large-state $\mathrm{APEX}_{256}^{15}\text{-BC-256}$ achieves $1.77\times$ and $1.65\times$ speedups over SATURNIN-256/256 for encryption and decryption on ARM, respectively. The tweakable block cipher $\mathrm{APEX}_{256}^{15}\text{-TBC-256/128}$ achieves $1.38\times$ and $1.39\times$ speedups over TRAX-L for encryption and decryption, respectively. Taken together, these results show that APEX combines extensibility across state sizes and primitive classes with efficient software implementations on markedly different processor architectures.

We propose the arithmetization-oriented (AO) hash function Arion, following a permutation-based design approach. We first define the permutation Arion-π over the finite field F_p, where (p > 2) is prime. The design of Arion-π is based on the recently introduced generalized triangular polynomial system, a novel algebraic framework for constructing cryptographic permutations using polynomials over finite fields. Using this permutation, we define the hash function Arion in two modes: the well-established Sponge construction and a feed-forward truncation mode (Trunc). Secure parameter sets are specified for prime fields commonly used in zero-knowledge proof applications, including the scalar fields of the BLS12-381 and BN254 elliptic curves. We provide an extensive security analysis of Arion, with particular emphasis on algebraic techniques — including interpolation and polynomial system solving (PoSSo) based techniques, such as Gröbner basis computations, and resultants — which are especially relevant for cryptographic primitives defined over prime fields. To the best of our knowledge, Arion is the first hash function whose security analysis is explicitly based on the algebraic invariant of the underlying ideal - the quotient ring dimension. In particular, we explicitly determine the dimension of the quotient ring associated with the CICO problem induced by the hashing modes. Furthermore, our analysis of the CICO-t problem applies to any t ≥ 1 and covers both the Sponge and feed-forward constructions. We evaluate the efficiency of Arion across several arithmetization frameworks — R1CS, Plonk, and AIR — and compare it with prominent AO hash functions, including Poseidon, Poseidon2, Anemoi, Griffin, and Rescue. Our results show that Arion is frequently the best-performing design in the Plonk setting and remains highly competitive, often ranking second, in both RoneCS and AIR. In terms of native performance, Arion is the only construction based on high-degree power maps that achieves performance comparable to Poseidon/Poseidon2. This makes it an attractive choice for applications where both zero-knowledge proving efficiency and native evaluation costs are important considerations.

Arithmetic logic units (ALU) combine word-level arithmetic with bitwise operations over encrypted data. The state-of-the-art scheme, GZ26 (CRYPTO'26), constructs an ALU in CKKS via triangle encoding, but has two limitations: the radix-$2$ design restricts packing capacity, while the arithmetic-to-Boolean (A2B) conversion requires $O(\ell)$ functional bootstrappings for $\ell$-bit message without batching independent ciphertexts. In this paper, we first generalize triangle encoding to arbitrary integer bases while preserving leveled modular arithmetic in CKKS. Larger bases reduce the number of slots required per message, allowing more messages to be packed into each ciphertext. %To ensure correct decoding despite rounding during CKKS plaintext encoding, we derive sufficient conditions relating the digit base to the encoding scale. For power-of-two digit bases, we introduce an A2B conversion using two functional bootstrapping after overflow refreshing, without batching independent ciphertexts. Our key insight is to transform triangle encoding into radix representation with unknown carries, from which candidate bits can be extracted using a single multi-value functional bootstrapping. Specifically, we first cancel the overflow shared by neighboring windows using one functional bootstrapping followed by linear operations, leaving expressions involving only radix digits and adjacent binary carries. Then we use a multi-value functional bootstrapping to jointly extract candidate bits and evaluate the local carry state, which determines how carries propagate between windows. Finally, we recover the canonical bits through parallel carry propagation and bit correction, using only leveled homomorphic operations. We implement our scheme in OpenFHE and evaluate it for 64-bit, 128-bit, and 256-bit message. The experimental results show that using \(d=2\) achieves the lowest latency for A2B conversion, yielding \(3.49\times\)--\(9.71\times\) speedups over GZ26 at the same packing capacity. In addition, using \(d=32\) increases the packing capacity and achieves the best amortized performance, yielding \(8.15\times\)--\(28.47\times\) speedups.

Polynomial commitment schemes (PCSs) are fundamental building blocks of modern zkSNARKs and often dominate their concrete prover and verifier costs. We introduce $\mathsf{Quasar}$, a field-agnostic PCS for multilinear polynomials that combines Quasi-Abelian (QA) codes with BaseFold (Zeilberger et al., CRYPTO 2024) through code switching (Ron-Zewi and Rothblum, JACM 2024). For a polynomial of length $N$ and security parameter $\lambda$, $\mathsf{Quasar}$ achieves concretely fast $O(N\log N)$ commitment, $O(N)$ evaluation time, and $O(\lambda\log^2 N)$ proof size and verifier time. Our starting point is a recent work of Li et al. (CRYPTO 2026), which shows that QA codes have fast encoding and strong concrete distance. This opens the door to building efficient PCSs from QA codes via Brakedown's paradigm (Golovnev et al., CRYPTO 2023). However, a direct instantiation, called QAPCS, inherits square-root proof size and verifier time, falling short of practical efficiency when $N$ is as large as $2^{25}$. We overcome this crucial limitation by showing that QA codes are essentially code-switchable. In contrast to existing code-switching arguments that utilize algebraic structures of either generator matrices or parity-check matrices, we look into QA encoding algorithms and propose an efficient encoding-oriented argument. Consequently, $\mathsf{Quasar}$ simultaneously enjoys fast proving from QAPCS, and polylogarithmic verification of BaseFold. We implement $\mathsf{Quasar}$ over the 127-bit Mersenne prime field with rate $1/2$ and 100-bit security. Under the 32-thread CPU setting, $\mathsf{Quasar}$ accelerates commitment and evaluation over BaseFold by $13.6\times$--$20.6\times$ and $5.2\times$--$63.8\times$, respectively. It is also $2.2\times$--$6.0\times$ faster in commitment than Brakedown and $2.1\times$--$4.0\times$ faster in commitment and $17.4\times$--$237.6\times$ faster in evaluation than BrakingBase, while providing smaller proofs and faster verification than both. Compared with QAPCS, it achieves up to $4.3\times$ faster verification and $2.9\times$ smaller proofs. Moreover, we observe that QA encoding naturally exposes massive parallelism, enabling a GPU acceleration strategy that is not directly available to the other code families. Across message lengths from $2^{12}$ to $2^{25}$, the GPU encoder is $32.9\times$--$148.3\times$ faster than the 32-thread CPU implementation. Over polynomial sizes $2^{20}$--$2^{29}$, the commitment with GPU acceleration further achieve a $3.4\times$--$16.7\times$ speedup relative to its 32-thread CPU implementation.

The Fiat--Shamir (FS) transformation is a technique that converts interactive protocols into non-interactive ones. FS is secure in idealized models such as the random oracle model (ROM) (if the interactive protocol satisfies a condition known as state-restoration soundness). It is known that there are protocols whose FS transformation is secure in the ROM, yet insecure when instantiated with any concrete hash function. Historically, these protocols were contrived (as in, they were designed so their FS transformation would be unsound). Khovratovich, Rothblum and Soukhanov (CRYPTO 2025) showed that a class of natural (and practically deployed) protocols based on a protocol of Goldwasser, Kalai and Rothblum (JACM 2015) was also unsound when compiled with FS and any concrete hash function. We extend the attack to a different class of protocols: those whose instances are generated by running a program. This setting covers concrete trends in modern proof systems, in which the computation to be proven is described by a program (often adversarialy generated) which is then either compiled or autonomously converted into an instance of target relation such as rank-1 constraint satisfaction (R1CS). We show that, when the conversion process is "expressive enough", an adversary controlling the program code can break soundness of the non-interactive proof system. The attacks generalize to a wide class of protocols: any protocol in which a cheating prover can prepare an accepting transcript before the statement is bound. We show that variants of the Spartan (CRYPTO 2020) and Aurora (EUROCRYPT 2019) proof systems for R1CS fall in this class. Complementing the attacks, we formalize a mitigation: deriving the first Fiat--Shamir challenge from the generated statement, rather than from the program that generates it, provably reduces the soundness of the compiled protocol to that of the underlying protocol for the non-generated relation.

ChaCha is one of the most extensively deployed symmetric ciphers. The security margin of ChaCha is directly related to the safety of many widely used lightweight security protocols and operating systems for constrained devices, such as TLS 1.3, SSH, Noise, WireGuard, S/MIME 4.0, Linux, Android, Chromium/Chrome, Firefox and Safari. This paper introduces a novel \textit{guessed key covering technique}. The objective of this technique is to identify partitioning-based functions whose required key bits are covered by those guessed for bit puncturing-based functions, enabling them to be processed jointly. Building on this, we propose a refined framework for differential-linear cryptanalysis of ChaCha called \texttt{ReBitP}, which combines the ideas of the bit puncturing technique, the partitioning technique and a two-phase distillation strategy. The key insight of \texttt{ReBitP} is to incorporate a carefully selected set of functions that are evaluated using the partitioning technique with different tail lengths into the first phase, without requiring additional key bits to be guessed. This early filtering via parity checks simultaneously lowers the time cost of the first phase and the time complexity of constructing the distillation table in the second phase. As applications, enhanced key recovery attacks on 7- and 7.5-round ChaCha256 are presented, achieving time complexities of $2^{142.08}$ and $2^{242.02}$, respectively. The cryptanalytic results are $2^{6.12}$ and $2^{1.58}$ times faster than the existing attacks, respectively. So far as we know, these are the best known key recovery attacks on 7- and 7.5-round ChaCha256. This definitely demonstrates the superiority of the refined framework \texttt{ReBitP}.

Fully Homomorphic Encryption (FHE) has served as a theoretical building block for cryptographic primitives, but concrete instantiations remain limited by the cost of generic homomorphic computation. One example is the universal thresholdizer that compiles any (deterministic) signature scheme into a multi-party threshold signature scheme with a one-round signing protocol (Boneh et al., Crypto'18), where the signing algorithm is homomorphically evaluated without communication with other parties. Practically, however, the signing algorithm itself often involves different types of computation. For example, ECDSA requires a hash function, point arithmetic over the high-precision defining field $\mathbb{F}_p$, and base-point group arithmetic over $\mathbb{F}_u$. Generic schemes like DM/CGGI take days to complete the homomorphic evaluation. Recent schemes like Boneh--Kim (Crypto'25), Cha--Park--Lee (Eurocrypt'26) and Gao--Zheng (Crypto'26) either support only one computation type, or lack efficient conversion methods. We propose a new FHE scheme whose arithmetic logic unit supports both large prime modulus arithmetic and bit-level operations. We then specialize it to the $\mathbb{F}_p$ mode, the $\mathbb{F}_u$ mode and the Boolean mode for ECDSA. Our key component is a homomorphic canonicalization operation that restores the unique bit representation of the encrypted messages. It requires a constant number of CKKS bootstrapping operations regardless of the bit-width of the prime moduli, and it therefore enables efficient high-precision conversions like $\mathbb{F}_p$-to-$\mathbb{F}_u$ modular reduction and $\mathbb{F}_u$-to-Boolean conversion. The conversion to Boolean mode is essential to allow noise flooding in the threshold decryption process. For the workload of $\mathbb{F}_u$ modular multiplication followed by conversion to bit representation in GPU, we estimate a 14.5$\times$ and $\sim$19000$\times$ better amortized latency compared with Montgomery-based approach in Cha--Park--Lee and TFHE-rs based approach, respectively. Our end-to-end homomorphic ECDSA signing experiment takes 56s on an NVIDIA RTX Pro 6000 GPU. To the best of our knowledge, it is the first concrete FHE-based construction towards threshold ECDSA with one-round signing.

Wagner's $k$-tree algorithm solves the generalized birthday problem and underlies preimage attacks on randomize-then-combine incremental hashes (EUROCRYPT '97) such as iSHAKE, LtHash, and AdHash. In its full-index execution, the $2^{k-1}$ index entries dominate peak memory at large $k$, and index trimming narrows each entry but leaves their number intact. Tang et al. (TCHES '26) introduced post-retrieval for the single-chain algorithm and left the $2^k$ exponent of the $k$-tree setting as an open problem. We resolve it by extending post-retrieval to the $k$-tree algorithm. This cuts the peak working memory to $P_k\ell N = O(k^2 \ell N)$, removing the $2^{k-1}$ index entries from the forward pass at the cost of a $\Theta(k)$ time overhead. Free $\delta$-level caching shrinks this time factor at no memory cost. The trade-off is starkly asymmetric: it removes an exponential number of index entries for only a linear recovery-time overhead. As a practical application, we revisit the list-item-reduction landscape for the $k$-tree algorithm under the memory-time product metric, $\mathsf{MT} = M \cdot T$. The gain is regime-dependent: for small $k$ the index entries do not yet dominate, so the recovery overhead outweighs the saving. For large $k$ the saving dominates, lowering the optimized $\log_2 \mathsf{MT}$ from $4\sqrt{n}$ to $2\sqrt{2n}$ at leading order. For fixed-size iSHAKE preimage attacks, we save approximately $51$ and $122$ bits over state-of-the-art index trimming for iSHAKE-128 and iSHAKE-256, respectively, in the unlimited-block setting, narrowing to roughly $6$ and $8$ bits under block-count caps.

Pessiland is a world where NP is hard on average but one-way functions (OWFs) do not exist [Impagliazzo 1995]. Because almost all classical cryptographic primitives imply OWFs [Impagliazzo and Luby 1989], there is almost no classical cryptography in Pessiland. On the other hand, quantum cryptography can exist even when OWFs do not [Kretschmer 2021; Morimae and Yamakawa 2022; Ananth, Qian and Yuen 2022]. Is there a quantum analogue of Pessiland where NP is hard on average but even quantum cryptography does not exist? In this paper, we show that such a miserable world, Quantum Pessiland, exists: there is a quantum oracle relative to which $UP\cap coUP$ is hard on average against quantum polynomial-time algorithms with quantum advice, yet auxiliary-input EFI pairs do not exist. We also show that there is a classical oracle relative to which $UP\cap coUP$ is hard on average against quantum polynomial-time algorithms with quantum advice, yet classically-secure auxiliary-input one-way puzzles (OWPuzzs) do not exist. Almost all quantum cryptographic primitives imply EFI pairs or OWPuzzs, and therefore these results mean that there is almost no quantum cryptography relative to these oracles. We further show that relative to the classical oracle, SampBQP = SampBPP, and therefore there is no sampling-based quantum advantage in Quantum Pessiland. Finally, because our average-case hardness of $UP\cap coUP$ implies $P^{\#P}\not\subseteq i.o.BQP/qpoly$, our result also implies that a non-relativizing proof technique is necessary to construct OWPuzzs solely from $P^{\#P}\not\subseteq i.o.BQP/qpoly$, which gives a partial negative answer to the open problem of [Khurana and Tomer 2025].

White-box security settings assume an extremely powerful adversary having full visibility and control of the software implementation and internal computations. Leakage-based attacks extract secret information via a local passive attacker (e.g., malware) and transmit it to a remote server. However, an active adversary, who can perform fault injections in a white box setting, has received limited attention, especially in the symmetric-key setting. In this paper, we initiate a formal study of active data-only adversaries in the white-box setting. Such adversaries preserve the control flow of the implementation but corrupt a bounded number of key-embedded lookup-table entries, enabling precise and repeatable manipulation of table values. Unlike leakage-based attacks, which are constrained by the bandwidth and existence of firewalls, such fault attacks can operate entirely locally. We focus on a data-only tampering adversary that preserves the control flow of the white-box implementation, but corrupts a bounded number of key-embedded lookup-table entries. Even under this stealth-preserving restriction, the adversary can cryptographically weaken the implementation and make faulty ciphertexts significantly easier to decrypt. We formalize such an active adversary by defining a new security notion and studying its impact on contemporary table-based white-box implementations. Our analyses reveal a structural disparity between two major design paradigms: Feistel-based white-box ciphers appear significantly more vulnerable to fault injection than SPN-based designs. Finally, we propose a software-based fault detection mechanism that detects fault injections with high probability, strengthening resilience. We provide detailed analysis of the SPN-based cipher WEM (the same analyses also work for other SPN-based ciphers like SPNbox), and two Feistel-based ciphers SPACE and Galaxy. Our analyses reveal that SPACE and Galaxy are significantly more vulnerable than WEM, under our fault-based security setting. Precisely, we show that WEM achieves high security under all the adversarial models, whereas SPACE and Galaxy instances can be attacked with a very high message recovery probability of $2^{-8}$, when the adversary can choose the fault positions and the values and corrupts up to one fourth of the implementation table entries.

We present a hybrid password-authenticated key exchange (PAKE) protocol that is secure against harvest-now-decrypt-later (HNDL) attacks by quantum adversaries, and is universally composable under the parallel composition framework of Lyu and Liu (EUROCRYPT 2025). Existing hybrid PAKE constructions combine a classical PAKE with a post-quantum (PQ) PAKE, with the overall security intended to rely on the stronger of the two. However, identifying which PAKE is stronger is non-trivial, given the limited maturity of post-quantum PAKE designs. Recognizing that the immediate quantum threat is passive, we propose a different hybrid compiler: rather than combining two PAKEs, we encapsulate a classical PAKE within a standard post-quantum Key Encapsulation Mechanism (KEM). This modular separation avoids the fragility of post-quantum password handling while neutralizing HNDL attacks. Our compiler works with any two-pass or three-pass PAKEs. As a concrete instantiation, we construct a three-pass protocol that combines J-PAKE and a post-quantum KEM. We also implement the resulting protocol and provide performance results demonstrating that the hybrid construction remains practical, with the complete handshake executing in $2.81\text{ ms}$. This construction has the distinctive advantage that it does not require any ideal cipher, (constant-time) hash-to-curve, or trusted setup assumptions. Within the Lyu-Liu framework, we show that J-PAKE satisfies the notion of a Full DH-type PAKE. We model the KEM as a password-independent Simulatable DH-type component satisfying the minimal simulation properties required for parallel composition. To capture the prospective quantum threat, we formalize a stronger variant of the standard HNDL threat model—where the quantum adversary is explicitly granted the plaintext password—and prove that our protocol achieves Session Key Security and Post-Quantum Forward Secrecy. Our construction relies solely on standardized and widely deployed primitives, yielding a hybrid PAKE that is UC-secure, efficient, and well-suited for real-world deployment during the post-quantum transition.

Matchmaking encryption (ME) enables bilateral access control with private policies, but existing pairing-based constructions tie receiver-side authorization cost to the policy size. This is especially problematic when one party holds a large hidden policy while the other holds only a small attribute set. We present Silent-Share, a bilateral hidden-policy threshold access-control protocol that decouples policy representation from pairing-based authorization. The construction combines a one-sided hidden-threshold policy-based key encapsulation mechanism (PB-KEM) with a sparse group-valued oblivious key-value store (GOKVS). The GOKVS compactly encodes policy-dependent group elements, so a receiver holding attribute set $\mathcal{A}$ performs exactly $2|\mathcal{A}|$ pairings, independent of the policy size $|\mathcal{P}|$ and threshold $d$. Total decapsulation additionally incurs a hidden-threshold reconstruction cost, characterized separately. Two independent one-sided instances are composed and bound with AES-GCM to realize bilateral authorization. We prove one-sided KEM confidentiality and policy hiding in the random-oracle model under a hidden common exponent assumption, and extend these guarantees to the bilateral composition. Our implementation on BN254 shows that, when the correct $d$-subset is provided, one-sided decapsulation for $|\mathcal{A}|=10$ takes about $394$ ms, dominated by pairing operations. The pairing-based authorization layer remains flat as $|\mathcal{P}|$ grows from $50$ to $800$, confirming the policy-size independence. The hidden-threshold reconstruction cost is reported separately and can dominate when $|\mathcal{A}|$ is large. Encapsulation is approximately $2$--$3\times$ faster than fuzzy matchmaking encryption across the tested parameter range.

The wedge attack of Ran (EUROCRYPT 2026) recovers the secret oil space of a UOV public key over fields of characteristic two by exploiting the fact that the polar forms of the public map are alternating. It has since been generalized in several directions, each carrying its own algebraic tools, e.g., Jin et al. (PKC 2026). Working directly with the polynomials of an oil and vinegar map, we give a simpler description of the attack, based on a dual decomposition of oil-vinegar polynomials, and we recover the original wedge attack and its odd-characteristic analogue as special cases. This framework leads to a generalization, which we call the extended wedge attack. We identify two explicit conditions on the parameters that guarantee that the attack terminates with the recovery of the secret space. We also prove that the matrix of the extended wedge attack is permutation equivalent to the truncated Macaulay matrix in the attack by Furue-Ikematsu (CRYPTO 2026).

We prove that the Succinct Learning with Errors assumption, introduced by Wee (CRYPTO '24), and the Decomposed Learning with Errors assumption, introduced by Abram, Malavolta, and Roy (CRYPTO '25), are equivalent under appropriate parameter settings. Abram, Malavolta, and Roy proved that Succinct LWE implies Decomposed LWE. We establish the converse implication, showing that Decomposed LWE implies Succinct LWE.

Mutual TLS (mTLS) authenticates both peers and therefore incurs post-quantum signature costs on every connection. Concurrent handshakes expose independent ML-DSA operations, but executing them jointly is difficult: signing is rejection-divergent, verification uses heterogeneous keys, and synchronous TLS APIs expose authentication work one connection at a time. We present WeaveTLS, a wire-transparent architecture that executes ML-DSA authentication across concurrent TLS connections. Its primitive interface combines rejection-aware slot refill with per-request expanded-key handles, supporting both unrelated client keys and shared issuer keys. A stackless OpenSSL continuation lets an nginx worker suspend authentication, expose work from other connections, and execute compatible operations through optimized single-request, four-request, or eight-request AVX-512 kernels without fibers or cross-thread handoff. WeaveTLS preserves the TLS authentication barrier, certificate validation, and wire protocol. On an AMD Ryzen 9 9950X3D, WeaveTLS improves one-core nginx mTLS throughput by 2.81-4.31$\times$ over OpenSSL's default ML-DSA path and by 2.19-3.29$\times$ over a synchronous reference-C control in the same provider across ML-DSA-44/65/87. At the primitive boundary, expanded-key eight-request verification is 1.65-2.23$\times$ faster than matched cached AVX2, and rejection-aware refill makes ML-DSA-65 signing 1.90$\times$ faster than otherwise identical lockstep scheduling. Cohort publication also weakens client-visible rejection timing under load, reducing attempt-count/latency correlation to 0.063 at concurrency 16 and 0.008 at 64; singleton execution retains the signal.

Ethereum Proof-of-Stake (PoS) clients must verify large volumes of Boneh--Lynn--Shacham (BLS) signatures for attestations, sync-committee messages, and other consensus-critical objects within fixed slot deadlines. This recurring cost competes with state transition, fork choice, and message propagation for client CPU time, so reducing it increases the verification headroom available under bursty load. Prior cryptographic-engineering work has shown that SIMD can substantially accelerate BLS verification kernels, but these gains do not automatically survive client software boundaries, runtime scheduling, and irregular verification ranges. We present AVXPoS, a client-aware batching framework for BLS verification in the Prysm Ethereum PoS client. AVXPoS treats batched verification as a client-level systems problem: it preserves Prysm's verification semantics while reorganizing protocol-shaped requests into native batched states that expose SIMD parallelism across API, worker, and native-backend boundaries. We instantiate AVXPoS with an AVX-512 backend for BLS12-381, combining Go-side range formation with C-side width-adaptive dispatch. On a resource-constrained two-core Intel host, AVXPoS gains $1.44$--$2.10\times$ over Prysm's production \texttt{blst} backend at selected small batch sizes that bracket the post-aggregation $p50/p95/p99$ batch-size quantiles of an all-subnets steady-state mainnet stress trace, and reaches up to $3.18\times$ in controlled capacity sweeps. On a 16-core AMD host, a production checkpoint-backfill verifier at Ethereum's 128-block request cap improves by $1.81\times$. Cross-platform results indicate that the relative speedup depends in part on Prysm's worker budget, because worker partitioning determines how much SIMD parallelism remains within each native range.

In recent years, threshold encryption has gained a lot of interest, particularly due to its potential use in encrypted mempools in blockchains. Standard security models allow the adversary to corrupt parties either statically (i.e., fixed at the onset of the game) or adaptively (i.e., via an oracle one-by-one, depending on keys and ciphertexts). In this work, we observe that neither of these models captures the case in which a party decides to become corrupted based on secret information. For instance, in an encrypted mempool application with randomly rotating committees, an adversary may set up a smart contract that pays parties who reveal their decryption share, and parties decide whether to claim it based on, say, whether they are on the next committee. Such corruptions are not fixed in advance, but they are also not chosen solely by an external adversary based on public information. We initiate the formal study of such internally motivated corruptions and partial decryptions. We introduce a security framework in which each party's corruption behavior may depend on its local secret state. That is, on a corruption, the adversary can submit a motivation function and all parties for which this motivation function outputs $1$ (on their secret information) are corrupted. A similar internally motivated behavior is allowed for releasing partial decryptions. We then study threshold encryption under this stronger notion of security. In particular, we show: - Negative Results: We show that for certain classes of motivation functions and number of queries, no threshold encryption scheme can satisfy security. We also show a concrete practical attack with internally motivated corruptions against a scheme that has been proven secure with standard corruptions. - Positive Results: We give two efficient classes of constructions from the (Bilinear) Diffie-Hellman assumptions in the random oracle model. The first is secure when partial decryptions on the challenge ciphertext are internally motivated. The second additionally allows internally motivated corruptions.

ARX-based design is a major building block of modern cryptographic ciphers due to its efficiency in software. Forr\'{o} is an ARX-based stream cipher proposed by Coutinho et al. at ASIACRYPT 2022, which was designed to provide higher security margin than the ChaCha stream cipher. In this paper, we propose a full automated MILP model called \textit{MinForr\'{o}}, to derive linear approximations for the Forr\'{o} stream cipher. For the differential part, a two-stage strategy to search for single-bit differential trails with high differential correlations is presented, which helps us to find the first-ever 3-round differential trails for Forr\'{o}. By combining the linear approximations obtained by \textit{MinForr\'{o}} and 3-round differential trail for Forr\'{o}, we propose improved differential-linear distinguishers for 4-, 5-, 5.25-, 5.5-, 5.75-, 6-, 6.25- and 6.5-round Forr\'{o} with complexities ${2^{32.44}}$, ${2^{46}}$, ${2^{50}}$, ${2^{64.32}}$, ${2^{87.12}}$, ${2^{117.92}}$, ${2^{174.92}}$ and ${2^{226.88}}$, respectively. The proposed differential-linear distinguishers for 4-, 5-, 5.25- and 5.5-round Forr\'{o} significantly improve the existing distinguishers by factors of ${2^{4.11}}$, ${2^{83.68}}$, ${2^{127.64}}$ and ${2^{178.20}}$, respectively. To the best of our knowledge, this is the first differential-linear distinguisher for Forr\'{o} that reaches 6.5 rounds, which is a significant advancement over the existing record of 5.5 rounds. We have implemented the differential-linear distinguishers for 4- and 5-round Forr\'{o} on a common PC, and the experimental results confirm the correctness of these distinguishers. Furthermore, when combined with the \textit{Probabilistic Neutral Bits} (PNB) technique, we obtain key recovery attacks on 5.5-, 6-, 6.5- and 6.75-round Forr\'{o} with time complexities ${2^{149.20}}$, ${2^{151.84}}$, ${2^{213.49}}$ and ${2^{251.97}}$, respectively. The proposed key recovery attack on 5.5-round Forr\'{o} significantly improves the time complexity of the existing attack by a factor of ${2^{75.84}}$. To the best of our knowledge, this is the first key recovery attack on Forr\'{o} that reaches 6.75 rounds, which is a significant advancement over the existing record of 5.5 rounds.

The European Digital Identity Wallet has integrated anonymous credentials into its technical specifications, and singles out four constructions for privacy-preserving revocation, drawn from two families: positive dynamic accumulators and signed-pairs. The two families are described in the literature in substantially different terms, and no common basis for comparing them exists, which currently prevents informed and quantitative decision making. In this work, we give a unified treatment of both families, showing that signed-pairs, despite their very different presentation, can be expressed in the standard accumulator syntax. We use this to define a single revocation mechanism that any of the four constructions instantiates, which in turn allows us to compare the resulting mechanisms both at the protocol level and empirically. We measure the performance of all four across the full revocation lifecycle, on server-class hardware for the Status Manager and on a smartphone for the Holder and Verifier, with parameters taken from a live national eID scheme. No construction dominates in every aspect, and we make the resulting trade-offs explicit, showing which construction suits which deployment, and identify promising avenues for further improvement at the protocol level.

We present a new variant of the memoryless Delfs-Galbraith algorithm for finding an isogeny path from any given supersingular elliptic curve to a curve with known endomorphism ring. Through existing polynomial-time reductions, our algorithm allows one to solve the supersingular endomorphism-ring problem which lies at the heart of isogeny-based cryptography. For arbitrary characteristics $p$ our algorithm asymptotically outperforms the previous best Delfs-Galbraith variant by a logarithmic factor; and matches the best previous asymptotic for characteristics with favourable structure. In addition to the asymptotic analysis, we also calculate a concrete cost estimate for our algorithm in terms of finite-field operations, which indicates that our expected cost is lower than all previous Delfs-Galbraith variants, even concretely. By substituting bit-operation counts for the cost of arithmetic, we can deduce concrete bit-security estimates for isogeny-based cryptographic primitives, including (but not limited to) SQIsign. As part of the calculation of the expected cost, we also provide a novel analysis of the probability of encountering "distinguished" subgraphs in an expander graph when relying various modes of graph exploration, whose potentially counterintuitive behaviour had apparently remained unnoticed thus far. Finally, we provide a complete implementation of our algorithm(s), with the asymptotic bottleneck being attacked on GPUs, and the easier post-processing done on CPU using C++ as well as SageMath. Preliminary experimental results suggest that we can solve $100$-bit instances of the problem within less than $100$ GPU hours. For comparison, the current cryptanalytic record for ECDLP (which has a comparable classical attack complexity) stands at $114$ bits, achieved using significantly more hardware and time.

Non-malleability for non-interactive zero-knowledge proofs requires that, given a proof for a statement, it is infeasible to derive a valid proof for a related statement without knowing a corresponding witness. We introduce a modular framework for analyzing non-malleable reductions of knowledge (RoKs). A reduction of knowledge transforms the task of proving knowledge for a source relation into proving knowledge for a target relation, often simpler or more structured. RoKs are an extremely useful tools for compositions. We identify different settings in which the composition of two RoKs, and in particular two non-interactive RoKs obtained via the Fiat-Shamir transform, preserves simulation extractability, and thus non-malleability. Our framework isolates simple and concrete properties required from each component, including novel forms of zero knowledge and new security notions that are easier to verify than full simulation extractability. This yields a systematic toolbox for establishing non malleability in modular proof systems. Finally, we illustrate the power of our approach by analyzing LaBRADOR (Beullens and Seiler, CRYPTO’23), a lattice based proof system for R1CS. We provide the first analysis of its simulation extractability and, since LaBRADOR is not zero knowledge, we design a zero knowledge variant that preserves its practical efficiency and sublinear proof size. Our results show that non-malleability for advanced proof systems can be achieved modularly, significantly simplifying the security analysis.

Very recently, Wesolowski (ePrint 2026/1486) proposed a novel heuristic algorithm for solving the supersingular isogeny-path problem in time and memory \(p^{1/3+o(1)}\), where \(p\) is the characteristic of the underlying field. Although this improves asymptotically on the previous \(p^{1/2}\log^{O(1)}(p)\) complexity, its concrete impact on isogeny-based schemes, particularly SQIsign, remains unclear because of the superpolynomial overhead hidden in \(p^{o(1)}\) and the exponential memory requirement. In this work, we assess the cost of Wesolowski's attack, study its time--memory tradeoffs, and investigate optimizations based on the van Oorschot -- Wiener (vOW) technique. Our analysis shows that, over the practical memory ranges considered, Wesolowski's algorithm is expected to improve on the state of the art only at NIST Level I. At higher security levels, its prohibitive memory requirements offset the asymptotic advantage over accelerated Delfs--Galbraith methods. With high parallelization, however, the vOW variant can recover this advantage. We further study quantum claw-finding improvements. While Grover search can essentially eliminate the large memory requirement, it offers little improvement in running time, whereas Tani's algorithm provides a stronger gate--memory tradeoff at the cost of substantial coherent quantum memory. Finally, we provide an optimized SageMath implementation and compare the theoretical time and space complexities against their empirical counterparts.

Silent threshold signatures (STS) and encryption (STE) enable threshold cryptography without interactive distributed key generation, allowing a group of $N$ parties to non-interactively generate a joint public signature verification key or an encryption key. However, modern distributed systems (such as Ethereum) rely on small, dynamically changing committees of size $n \ll N$ for efficiency, and existing silent threshold schemes either fail to support this dynamic setting or suffer from severe scalability issues. To the best of our knowledge, the only prior STS construction for dynamic committees, Dyna-hinTS, requires an aggregation time of $O(N\log N)$ per epoch, tightly coupling the cost to the global system size rather than the small active committee. Furthermore, no STE scheme for dynamic committees has been proposed yet. In this work, we present practical silent threshold signature and encryption schemes for dynamic committees, reducing the aggregation cost so that it depends only on the committee size $n$. For signatures, we redesign the Dyna-hinTS framework by replacing its Plonk-style SNARKs with linear pairing checks and a new polynomial commitment for representing the committee, yielding an aggregation time of $O(n\log^2n)$. We also introduce the first silent threshold encryption scheme for dynamic committees with matching efficiency. We further significantly optimize the silent setup phase common to prior STS and STE schemes, reducing each party’s one-time setup (i.e., generating the setup data, referred to as a "hint") cost from $O(N^2)$ to $O(N)$. We implement our schemes in Rust, and the results demonstrate practicality at scale. For a system parameterized with $N = 2^{20}$ and $n = 2^{10}$, the per-party hint generation takes 197 seconds, and signature aggregation takes 0.153 seconds, achieving a $>1900\times$ improvement over Dyna-hinTS. At the same time, our aggregated signature size, verification key size, and verification time (with access to the epoch committee representation) remain constant.

We estimate the intrinsic undercounting in the free-memory-access, Macaulay coefficient-on-demand RAM modeling when applied to the Parallelized Wiedemann-based XL in the Ran Wedge attack and in the Furue--Ikematsu intersection attack, under some optimistic but still feasible-sounding assumptions for the attackers. We believe that this shows the memory effects makes UOV secure enough for Ip, Is, and III. If NIST considers our original parameters insufficiently convincing, we do not take Furue's suggested replacements; we offer instead the following perturbations, which hold $m$ --- and hence the compressed public key --- fixed and spend only on the vinegar count: uov-Ip\# (256,116,44), uov-III\# (256,186,72) and uov-V\# (256,250,96).

MERIDIAN is a 128-bit blockcipher proposed as a lightweight AES alternative. We show that its “Directional Substitution” layer is not injective by giving an explicit collision. This yields a full 12-round collision for every key. Consequently, no keyed instance of MERIDIAN is a permutation, so no decryption function can invert encryption on all plaintexts, and its blockcipher and PRP security claims fail. We additionally identify a one-round differential that exceeds the claimed bound by a factor 13.37.

Fully homomorphic encryption (FHE) lets a server run inference on encrypted data with strong privacy guarantees, but running a Transformer under FHE is expensive. Its non-linear operations, such as softmax, normalization, and activation, must be replaced with polynomial approximations that the CKKS scheme supports, and the depth of these approximations dominates inference cost. Existing FHE Transformers use hand-tuned approximation settings, such as iteration count and polynomial degree, applied uniformly across layers, models, and tasks. Hand-tuning is slow and error-prone. Even a single uniform setting has about $10^7$ choices, and manual search cannot exploit layer-wise variation. AutoFHE, the only automated method with multi-objective search, targets ReLU-only CNNs and needs full fine-tuning per candidate, which is too costly for Transformers. Per-layer settings also push the search space to about $10^{85}$ for BERT and ViT and $10^{228}$ for LLaMA3, beyond both manual and fine-tuning-based search. We present ATLAS, a training-free framework that automates this search by treating each layer's approximation setting as a multi-objective optimization over latency and accuracy. The problem is hard: the decision space is large (96 or 256 variables), each configuration takes 70 to 1,000 seconds to evaluate even in cleartext, and 85 to 90 percent of configurations are invalid. ATLAS handles this with a two-stage optimization strategy and a surrogate model, completing the search in about one hour. Compared to an iterative softmax baseline, ATLAS cuts multiplicative depth and end-to-end latency by about 35 percent with little accuracy loss, and works across encoder-only, decoder-only, and vision Transformers, complementing parallel work on packing and matrix multiplication.

This work introduces SandwichPIR, the first single-server PIR protocol that implements the overwhelming majority of the server computation as dense 8-bit integer matrix multiplications on GPU tensor cores and requires no offline communication. For a 4 GB database with 32 KB records, SandwichPIR answers a query in 8.2 ms and communicates 688 KB of data. This amounts to a server throughput of 488 GB/s and is $88\times$ faster than the best CPU-based protocol that does not rely on offline communication. The performance of SandwichPIR shines when processing a batch of queries from many independent clients. This moves the server from a memory-bandwidth-bound regime into a compute-bound regime. A single Nvidia L40S GPU can process a batch of 128 queries to the same 4 GB database in 21.0 ms. This gives an amortized per-query processing time of 0.16 ms and an effective throughput of roughly 24 TB/s. This is $50\times$ higher than the single-query throughput. With a fleet of 8 GPUs, SandwichPIR can process a batch of 128 queries to a 256 GB database in 119 ms and achieves an effective throughput of nearly 270 TB/s. Finally, we show how to use SandwichPIR to enable private access to (text-only) English Wikipedia (8 GB compressed). Retrieving an article (up to 128 KB) requires 768 KB of client-server communication, with an estimated total end-to-end latency under 200 ms over a broadband network connection. By processing 64 queries at a time, a single GPU can handle over 2,500 queries per second (with a computational cost of \$0.20 per million queries based on current AWS pricing).

In recent years, quantum circuit optimization has become an important research topic. Motivated by the fact that quantum gates act on fixed physical wires and modify only their target wires, we propose two SMT encodings: an exact-G encoding and an at-most-G encoding with null gates. Our method speeds up most tested 4-bit S-box instances, achieving up to approximately 130x speedup on the ELEPHANT S-box. Importantly, our method enables automated synthesis of practical 5-bit S-box quantum circuits, such as KECCAK and ASCON. For the KECCAK S-box, in the no-ancilla setting, our model obtains concrete implementations with 17 NCT gates and full depth 51, and with 16 NCT gates and full depth 52, improving the EUROCRYPT 2025 result of Huang et al. It further finds a 13-gate implementation with full depth 55, which is gate-count optimal in the no-ancilla setting under the NCT gate set. In addition, when one ancilla qubit is allowed, our model obtains KECCAK implementations with Toffoli count 5, matching the theoretical lower bound. Finally, our model can also be applied to small-scale linear-layer implementation; for example, it finds a 24-CNOT implementation with depth 3 for the 16x16 linear matrix of MIDORI.

Keyword private information retrieval (PIR) allows a client to retrieve a record associated with a keyword from a database without revealing any information about the keyword. In the standard single-server setting, existing hintless keyword PIR protocols incur substantial communication and computation costs. In this paper, we propose an efficient approach to generate $k$-hot vectors (i.e., vectors with exactly $k$ non‑zero components) in homomorphic-encryption form, and present a bucket-merging technique to decrease the maximum size of buckets. Based on these techniques, we construct LetoPIR, a hintless keyword PIR protocol that outperforms previous PIR protocols in the same setting. Compared to the state-of-the-art hintless keyword PIR scheme, SparsePIR (USENIX'23), LetoPIR achieves a $12.4\times \sim 17.0\times$ improvement in communication cost for databases ranging from $256$ MB to $4$ GB with records of $256$ bytes, and more than $3.0\times$ improvement in computation cost for the $256$ MB database. Compared to the state-of-the-art keyword PIR scheme with client hint, KPIR (USENIX'25), LetoPIR reduces the communication cost by $51.4\times \sim184.8\times$, while achieving a similar (even better) computation cost.

Private information retrieval (PIR) enables a client to retrieve a record without revealing the index.Among existing PIR protocols with database-independent preprocessing, for each query, the protocols with low communication often take from several seconds to tens of seconds, while the faster protocols require hundreds of kilobytes for communication. In this paper, we propose three techniques for different-type ciphertext conversions: (1) the first one is to generate a two-orbit SIMD selector from encrypted bits; (2) the second one is to convert a packed $\mathsf{RLWE}$ ciphertext into an aligned monomial $\mathsf{RGSW}$ ciphertext; (3) the third one is to produce an arbitrary monomial $\mathsf{RGSW}$ ciphertext from encrypted bits. Building on these techniques, we design a new PIR protocol (called Atom), achieving the best of both worlds (i.e., having not only low communication but also fast computation). We implemented Atom and evaluated its performance for $256$ B records and databases from $256$ MB to $8$ GB. Specifically, Atom takes $3.0 \sim 3.8$ KB of online communication (i.e., the total communication, excluding the setup phase that can be run only once and reused for multiple queries), and takes $0.4 \sim 5.0$ seconds per query. Compared to the state-of-the-art KsPIR (CCS'24), Atom reduces the online communication cost by a factor of $40.5\times \sim 51.3\times$, while its running time is comparable to KsPIR ($0.2 \sim 5.2$ seconds per query).

Private Join and Compute (PJC) enables two parties to compute aggregates over matching records from their private datasets. In this work, we focus on the inner-product variant of PJC, which computes the inner product over matching records from their private datasets. It has important applications such as privacy-preserving ad conversion measurement. However, existing PJC protocols assume each party holds the entire dataset, which is often unrealistic in practice, where relevant datasets are distributed across multiple data owners. No existing PJC protocols directly support distributed input sets across multiple clients, while straightforward generic approaches introduce substantial overhead. We propose an efficient approximate PJC protocol for distributed input sets while keeping the communication sublinear in the input size. Our protocol works in the semi-honest setting and uses two non-colluding servers that learn nothing beyond the final approximation. The core technical contribution is a novel adaptation of the G\"odel Prize-winning AMS sketch redesigned for efficient evaluation under fully homomorphic encryption. Concretely, we show a new structured randomness that can be homomorphically generated from short seeds using just 3 levels of multiplication while maintaining the best plaintext accuracy bound. Based on our optimized implementation, clients can insert each input element into an encrypted sketch in 30 ms, which has a size of 250 KB, independent of input size. The servers can recover the final output within seconds, orders of magnitude faster than the generic method.

Soft Analytical Side-Channel Attacks (SASCA) combine leakage-derived priors from multiple intermediate variables with their functional dependencies through belief propagation (BP).However, when applying SASCA to large-scale cryptographic computations where algorithms are abstracted into extensive factor graphs with large candidate sets per variable node, the memory and computational complexity of SASCA become prohibitive. A natural first choice for large-domain variables is to fragment them into smaller-domain variables when the underlying computation decomposes accordingly. For modular addition and multiplication, however, preserving cross-fragment dependencies can introduce short cycles and coupled factor updates, motivating alternative inference strategies. We consider the Number Theoretic Transform (NTT) in ML-DSA as a representative large-scale cryptographic computation, where standard SASCA (with FFT optimization) requires approximately 122~GB of memory for message propagation in an unprotected single-trace setting, even for a 6-layer sub-NTT component, while masking further amplifies the graph size and inference cost. To address this limitation, we propose Greedy Region-Wise Pruning SASCA (GRWP-SASCA), a practical and efficient framework that enables scalable inference by dividing the global factor graph into manageable regions. The core idea is to replace global BP with a sequence of localized inference steps, where regions are incrementally merged, and the search space is reduced via greedy pruning of redundant structures and low-confidence candidates, thereby significantly reducing the memory and computational complexity of the BP algorithm. This design provides a flexible attack strategy for large-domain arithmetic factor graphs. Our results show that GRWP-SASCA transforms previously infeasible SASCA attacks on large-scale cryptographic computations into practical ones. Theoretical analysis of single-trace attacks on unprotected ML-DSA shows that GRWP-SASCA reduces the memory overhead associated with message propagation by a factor of up to $151$ compared to the standard SASCA, while achieving an estimated speedup by a factor of $68$. For $d$-order masked ML-DSA with multiple (say, $t$) traces, GRWP-SASCA achieves an estimated reduction in memory overhead associated with message propagation by a factor of up to $388.13t(d+1.14)/(d+2.44)$, while achieving a speedup by a factor of approximately $2d + 4$. Real-device experiments on an ARM Cortex-M4 platform demonstrate that the secret can be recovered from an unprotected implementation within approximately $15$ minutes with a single trace, with a peak message memory usage of approximately 0.9 GB. For first-order masked ML-DSA, the secret can be recovered within 3.2 hours using 8 traces, with a peak message memory usage of approximately 8.1 GB.

A few weeks ago, Ghoshal, Ishai, Jain, and Sun (ePrint:2026/1630) introduced a "hold-out distinguisher" for the Goppa–McEliece public key. This past week, Vedenev (eprint:2026/1747) proposed to turn its polynomial relations into key recovery by reconstructing the hidden generalized Reed–Solomon representation from nested Hasse-derivative spaces at held positions. Vedenev’s proposed held-position count explicitly assumes that the resulting linear equations are independent across positions. Yet, experiments on proper binary Goppa instances contradict that assumption, demonstrating a familiar "waterfall" phenomenon where - just before the required independent equation count for a successful attack - additional held positions sharply drop in value, providing just a single, independent equation rather than the $\approx {k \choose 2}$ such equations from the early positions. This note identifies an algebraic-geometric reason for this inherent dependence. For a binary Goppa polynomial of degree $t$, an explicit linear map constructs a $(2t+3)$-dimensional family modulo the true solution. At each held support point, the entire derivative-flag block restricts on this family to at most one ordinary evaluation condition. Consequently, under a concrete nondegeneracy condition stated in terms of the hidden vector polynomial $\bf F$ and its formal derivative ${\bf F}$$'$: $c_{need} \gt 2t + 3,$ where $c_{need}$ is the number of sampled held positions required at the critical step in Vedenev’s algorithm. (The proposed key-recovery algorithm’s cost depends on $c_{need}$ in the exponent.) For ISO/NIST Category 5 parameter set ${\sf mceliece8192128}$, this gives $c_{\rm need} \gt 259,$ which implies Vedenev’s key-recovery algorithm costs in excess of $2^{1500}$ bit operations there.

Folding is a powerful technique for constructing efficient succinct proof systems, especially for computations that are expressed in a streaming fashion. We present PikkuFold, a new lattice-based folding protocol that improves upon state-of-the-art folding schemes such as SALSAA (ePrint 2025/2124) and Cyclo (EUROCRYPT 2026). One folding step communicates $5.7$ KB beyond the commitments to its fresh inputs, against $\geq 30$ KB for Cyclo and $\geq 60$ KB for SALSAA on similar instances, with a prover more than an order of magnitude faster and the verifier in the millisecond range. At the heart of our construction are layered random projections, whose algebraic structure makes them fast to verify and whose final image is short enough to send to the verifier directly, cutting out the cost of auxiliary commitments. We use those techniques to replace the extensive and restrictive range proofs of Cyclo, while still achieving only a small additive increase in the accumulator norm across multiple folds. PikkuFold is the first lattice-based construction that does not require any in-protocol commitments beyond those of the fresh inputs. Such commitments are the heavy part of a folding transcript: every prior lattice-based scheme commits to a decomposed or otherwise transformed witness during the fold, immediately increasing the communication by dozens of kilobytes. On top of that, we provide two contributions of independent interest, applicable beyond the context of folding schemes: (i) a Johnson-Lindenstrauss theorem for biased ternary matrices modulo $q$ with certified concrete constants, which replaces the heuristic parametrisation of prior works, and (ii) a thorough analysis of the short-challenge sampler with fixed Hamming weight and operator-norm rejection, offering a wide range of parameter sets. Using this sampler as a drop-in replacement would lead to immediate improvements in a wide family of lattice-based protocols.

SDitH is a code-based signature scheme built from the regular syndrome decoding (RSD) problem. Each v2 signature masks the long-term witness with pseudorandom leaf-seed shares. In each repetition, cancelling the shares reconstructed by the verifier leaves the witness XORed with the hidden seed's PRG output. The VOLEitH PRG runs AES or Rijndael in counter mode from zero, so every signature and leaf uses the same input. One encryption therefore tests a candidate seed against every exposed value. RSD elementary-vector constraints discard false candidates before the seed commitment confirms a match. A matching hidden seed reveals the long-term witness and yields a signing key. With $q=2^{12}$ chosen-message signatures, the attack costs 11.23-11.67 bits less than AES-128/192/256 exhaustive key search across all six parameter sets. Both use the same Boolean-circuit model, and the attack cost extends through fresh forgery. Reduced-keyspace executions against the official C implementation recover witnesses of 616, 876, and 1,144 bits and produce accepted fresh signatures for every parameter set. Using the signature salt as the IV leaves one signature's repetitions under one input and retains 1.95-3.29 bits of separation. Combining salt, BAVC leaf index, and block position assigns a separate counter range to each PRG call without changing signature size or the number of block-cipher calls.

When the output dimension of a vectorial Boolean function exceeds half its input dimension, not all nonzero components can be bent. The best attainable componentwise nonlinearity in this range, however, is generally unknown. We ask whether the conjectured bound for even-dimensional square mappings extends to this high-output regime, and show that it does not. Specifically, we construct a six-input, four-output function with nonlinearity 26, thereby improving the previous lower bound of 24. Its seven bent components form the nonzero part of a three-dimensional component subspace, whereas the remaining eight components all have maximum absolute Walsh coefficient 12. Accordingly, the associated binary linear code has length 64, dimension 11, and minimum distance 26. We then address the distinct problem of six-bit permutations and determine its exact maximum. A computer-assisted evaluation of the complete classification of Boolean functions in six variables bounds the autocorrelation energy of every balanced component whose Walsh coefficients have magnitude at most 12. Combined with a vectorial fourth-moment identity, this bound forces every six-bit permutation to have a component with maximum absolute Walsh coefficient at least 16, and hence nonlinearity at most 24. Inversion over the field with 64 elements attains this value. Finally, the same argument gives necessary coding conditions for any non-bijective six-input, six-output function whose nonlinearity exceeds 24.

GEA-1 and GEA-2 are two standard stream ciphers used in GPRS (General Packet Radio Service) to protect against eavesdropping GPRS between the base station and the phone. Now, a range of current phones still support them. In this paper, a differential fault attack on the GEA-like stream ciphers under the random fault model is proposed for the first time. In this attack, an efficient dedicated algorithm for identifying the exact fault location is proposed. By using this dedicated algorithm, the attacker can succeed in determining the exact fault location. As applications, practical differential fault attacks on the GPRS standard ciphers (i.e., GEA-1 and GEA-2) are presented, which recover the 64-bit secret keys of GEA-1 and GEA-2 with time complexities of ${2^{{\rm{33}}{\rm{.807}}}}$ and ${2^{{\rm{33}}{\rm{.858}}}}$, respectively. We validate the cryptanalytic results by simulating the whole attacks on the platform ChipWhisperer Lite. The experimental results show that both GEA-1 and GEA-2 can be broken within sixteen minutes on a common laptop. Finally, the possible countermeasures are presented to protect the processed data of massive GPRS devices.

This paper deals with the hardness of finding short vectors in module lattices. Let $K$ be a number field of degree $d$ and $\mathcal{O}_K$ its ring of integers. We show that if a module lattice $M$ of rank $n$ in $\mathcal{O}_K^n$ has some Galois-symmetries, namely if it is fixed coordinate-wise (as a set) by a group $G$ of automorphisms of $K$, then $M$ can actually be seen as a module of rank~$n$ over a subfield~$K'$ of $K$ ($K'$ is the fixed-field of $G$), whose degree is $|G|$ times smaller than the degree of $K$. When one wants to find short vectors in $M$, this translates into the observation that the module lattice $M$, which is a priori a lattice of rank $n d$ can in fact be seen as a lattice of rank only $n d / |G|$. Hence, finding short vectors in $M$ is easier than what one could have expected by forgetting about the algebraic structure of $M$. This result is a generalization of a similar result by Boudgoust, Gachon and Pellet-Mary (Crypto'22), which was restricted to ideal lattices (i.e., modules of rank $1$).

Hash-based constructions occupy a distinctive position among post-quantum signatures: their security reduces to well-tested properties of hash functions rather than to newer assumptions such as lattices or isogenies. This work focuses on stateful schemes instead of stateless, because the former are considerably more efficient. However, they have the problem of state handling, since reusing a one-time key twice enables signature forgeries. Despite threshold signatures mitigate this problem by spreading trust among a set of disjoint parties, building them from hash-based schemes is difficult, since these lack the homomorphic structure needed to recombine partial signatures, and generic multiparty computation can be expensive for hash-based constructions. Kelsey, Lang and Lucks recently proposed Haystack, the first threshold scheme for hash-based signatures producing standard LMS or XMSS signatures, at the cost of a fully trusted setup and a large common reference value. We analyze Haystack along two dimensions: performance and security. First, as Haystack lacks an implementation and realistic benchmarking, we implement the protocol in Java and produce a network-aware evaluation of its viability in real deployments, concluding that it performs comparably to other post-quantum threshold schemes. Second, we relax the trust placed in the dealer. For that, we introduce a variant of the setup built on an optimistic, lightweight MPC-based partial-DKG. It does not remove the dealer's ability to forge, but it prevents it from impersonating trustees within the signing protocol, while preserving the standard signature format. Also, an optional succinct-argument layer provides public auditability. We further consider a full-DKG setting with no dealer and where the trustees run the entire setup under MPC. Both variants are implemented in MP-SPDZ and their costs have been analyzed.

With the arrival of scalable quantum computers, classical key exchange protocols like RSA, elliptic-curve and finite-field Diffie-Hellman are vulnerable to harvest-now-decrypt-later attacks. Quantum key distribution offers information-theoretic security but is sensitive to channel noise, loss, and distance, while post-quantum cryptography provides quantum resistance on conventional hardware at the cost of larger keys and a dependence on hardware computational strength. Existing hybrid defenses generally rely on static configurations that require manual intervention when channel conditions degrade, and no prior software-defined system performs real-time three-way switching among these approaches while preserving uninterrupted key availability. This paper presents an adaptive multi-algorithm key generation and exchange framework that dynamically selects among quantum key distribution (BB84), post-quantum cryptography (Kyber512, standardized as ML-KEM-512), and classical Diffie-Hellman according to real-time monitoring of the quantum bit error rate and network latency, fusing key material from all active sources through an HMAC-based key derivation stage. The framework was implemented and evaluated in a controlled simulation environment built on Qiskit, liboqs, and the Python cryptography library. Across all five operating modes it attained a 100% key-generation success rate, with the quantum-resistant modes sustaining a secret-key throughput of approximately 3 kbps at a 256-bit key size and mode transitions completing without loss of key availability. A Kruskal-Wallis test confirmed that the timing differences among modes were statistically significant (H = 133.32, p < 0.001), and the security model was placed on a formal footing using the robust key-combiner framework. The results indicate that adaptive multi-algorithm key exchange can substantially improve the quantum resilience of secure communication systems in terms of security, availability, and performance.

Retrieval-augmented generation (RAG) services outsource vector search over proprietary corpora, yet clients cannot verify that returned context conforms to the promised index, parameters, and snapshot. We present VERIF, the first dedicated zero-knowledge polynomial interactive oracle proof (PIOP) for complete, service-consistent IVF-Flat retrieval. VERIF proves top-$m$ centroid selection, authenticated routing, exact full-vector scoring of every routed candidate, final top-$k$ selection, and context binding. Its commitment-eliding reduction keeps query-dependent scores virtual and reduces selection claims directly to inner products over authenticated data. A unified, permutation-free top-$t$ relation with limb-decomposed range arguments handles both selection stages without sorting or score commitments. Against a matched, optimized implementation of the same retrieval relation using a general-purpose circuit-based zkSNARK (Plonky2), our prototype achieves up to an $86.5\times$ prover speedup and reduces peak memory by up to 99.1%. VERIF proves retrieval over authenticated SIFT and 768-dimensional Cohere indexes containing 32 million and 8 million vectors in 5.90 and 11.57 seconds, respectively; verification takes 0.62--1.48 seconds. These results demonstrate practical verifiable IVF-Flat retrieval for RAG-as-a-Service.

Gao et al. (IEEE Internet of Things Journal, 2025) proposed a medical data sharing system for digital twin environments using identity-based encryption (IBE), public-key encryption with keyword search (PEKS), and blockchain technologies. In this short note, we show that Gao et al.'s system allows unauthorized users to access other patients' medical data. We further show that the search server can obtain information about the queried keywords from the trapdoors (search queries). In addition, we analyze the procedure used to retrieve, from the blockchain, the IPFS (InterPlanetary File System) addresses storing encrypted medical data and encrypted keywords. Since these addresses are derived from labels that can be computed solely from public information and keywords, and because the keywords themselves are provided to the search server, we demonstrate that searchable encryption is unnecessary in the first place. Based on our security analysis, we argue that the proposed system requires a fundamental redesign.

Quantum indistinguishability obfuscation (qIO) aims to make a quantum circuit unintelligible while preserving its functionality. It serves as a foundational primitive for advanced applications, such as witness encryption (WE) for QMA, non-interactive zero-knowledge arguments for QMA, and attribute-based encryption for BQP. Despite its importance, constructing qIO from standard assumptions remains a major open problem. In this work, we prove that the security of WE for QMA cannot be based on any falsifiable cryptographic assumption via a restricted class of quantum black-box reductions. Because qIO for null quantum circuits implies WE for QMA, this also separates null-qIO from falsifiable assumptions. Since almost all standard cryptographic assumptions are falsifiable, our result presents a barrier to basing qIO on standard cryptographic assumptions. The reductions we rule out are restricted: the reduction must query the adversary classically, non-adaptively, at the same security parameter, and only on honestly generated ciphertexts. Moreover, our impossibility applies only to WE with classical ciphertexts, and therefore does not rule out qIO with obfuscators whose output is a quantum state. Ruling out more general reductions, as well as more general forms of WE and qIO, remains open. Our impossibility relies on the existence of a QMA-QCIP[2] gap problem, an average-case assumption postulating a QMA language that cannot be verified with two messages of classical communication.

Rotation-symmetric Boolean functions form an important class of cryptographically significant Boolean functions. In 2017, Su and Tang proposed in [IEEE TIT 63(7): 4658–4667, 2017] an infinite class of rotation-symmetric bent functions of every possible algebraic degree. In this paper, we present two constructions of rotation-symmetric bent functions outside the completed Maiorana--McFarland class on $n=30\cdot 7^j$ variables with $j\geq0$ and $n=70t$ variables with $t\geq1$, respectively. Each of the two constructions generates bent functions of every possible algebraic degree ranging from $3$ to $n/2$. Since the algebraic degree of an $n$-variable bent function is at most $n/2$ and every quadratic bent function belongs to the completed Maiorana--McFarland class, the interval from $3$ to $n/2$ is the full possible degree range for bent functions outside this class. To the best of our knowledge, these are the first infinite constructions of rotation-symmetric bent functions in which functions have algebraic degrees ranging from $3$ to $n/2$ while remaining entirely outside the completed Maiorana--McFarland class.

A CNOT circuit is a quantum circuit where the only type of gate appeared in the circuit is the CNOT gate. Given an n × n binary matrix which specifies the relationship between input and output, existing greedy algorithms generate corresponding CNOT circuits of n qubits, with the goal of minimizing depth of the circuits. This short paper presents two new greedy algorithms, which can be considered as generalized versions of existing greedy algorithms. The new algorithms are inspired by the algorithm presented in the Asiacrypt 2024 paper “Quantum circuits of AES with a low-depth linear layer and a new structure”. Although we have not run large-scale experiments, small-scale experiments suggest that the new algorithms are at least as powerful as existing greedy algorithms.

We study the high-precision computation of $\ell_p$-Lewis weights for $p\ge4$ in the black-box exact-real full-vector leverage-score oracle model, measuring complexity by the number of adaptive oracle rounds. In this model, Gribling, Sidford, and Zhang [GSZ26] obtained an $O(p^2\log(m/\epsilon))$ bound for computing an $\epsilon$-estimate. We improve this bound to $O(p\log(mp)+\sqrt p\log(1/\epsilon))$. To obtain this result, we isolate the normalized fourth-moment operator governing the nonlinear Hessian of their log-determinant matrix potential and prove that each relative-gradient step with denominator $p$ resets the operator norm to a universal constant. This reset controls the entire update segment and yields an $O(p\log(mp))$ global entrance phase. After entering an $O(1/p)$ spectral neighborhood of the optimum, we switch to a restarted accelerated Bregman-gradient method for the vector potential.