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_2 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/(2deg 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 together with a quadratic condition on its solution space, certifying targets that first order cannot move. Projected tangent dimension distinguishes the number of free target wires from their independent degrees of freedom. Where witnesses come from is treated as part of the method. In the studied gadgets, the circuit's own generator computes advice by division and refuses at exactly the compatible exceptional inputs that expose the defects. Three separate experiments measure construction from the constraint system instead. On five defective circuits, propagation, one-input symbolic solving, and rational-function propagation with resultant elimination supply compatible exceptional inputs for all five with no solver in the loop, including a Pedersen point distinct from the solver's own counterexample. On the fifty-one circuits the solver reports safe, an algebraic and symbolic construction sweep finds no output-moving certificate under stated budgets, with 86 of 102 circuit-method combinations producing a witness. A bounded 108-trial pilot compares honest generation, uniform and structural mutation, and the relational solver under identical queries and a shared eight-second end-to-end wall cap, showing complementary coverage on the tested instances. 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, paired with witness construction and solver- or certificate-based confirmation, with the witness-construction stage itself measured rather than assumed.

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.

Message authentication codes (MAC) are ubiquitous and are considered to be the most important tool employed to ensure authenticity of messages in the symmetric key setting. In this work, we aim to empower MACs with a newly added functionality of updatablility, i.e., the goal is to construct a MAC scheme where the authentication tag for a message can be updated with every update to the message without recomputing the tag for the entire message. Such a functionality can be useful in several scenarios, primarily where the storage of a frequently changing large message is delegated to an un-trusted server. In such a scenario it may be infeasible for an user to download the entire message and recompute the tag for every update. Bellare et al. [CRYPTO'94, STOC'95] introduced a new class of history-free updatable MACs, which can update a message tag without requiring any previous information. However, their update algorithm takes the entire document as an input, which can be impractical in many real-world scenarios. We introduce a new class of MACs called updatable message authentication codes (UdMACs). An UdMAC allows an existing message tag to be updated using only the previous tag, the message update, and a small state, without accessing the previous message. We systematically develop UdMACs, provide syntax for UdMAC, propose formal security notion. We then present two constructions: $\concatu$ and $\xoru$, which support two distinct message updates, namely, concatenation and xor difference. We analyze both the constructions in details and prove security of the construction in the newly proposed security model.

An important open question in quantum cryptography is the construction of publicly-verifiable NIZKs for QMA. Classically, one can construct NIZKs for NP in the random oracle model (and sometimes in the standard model) by compiling an honest-verifier ZK (HVZK) $\Sigma$-protocol for NP using the Fiat–Shamir transformation. Broadbent and Grilo introduced a quantum analog of a $\Sigma$-protocol (which they call a $\Xi$-protocol) in which the prover's first message is quantum, and show that HVZK $\Xi$-protocols exist for QMA. However, it is not clear how to compile such protocols into NIZKs in the (Q)ROM, because the Fiat–Shamir transformation seems to be incompatible with quantum messages. In this work we give formal evidence that this is indeed the case: we show that if generic "Fiat–Shamir-like" compilers for quantum protocols exist in the QROM (with small completeness and soundness error) then QMA = BQP.

In any secret sharing scheme, the size of each share must be at least as large as the size of the secret. Schemes that attain this lower bound are called $k$-ideal, where $k$ is the size of the domain of the secrets and shares, or simply ideal if they are $k$-ideal for some $k$. An access structure is called $k$-ideal if it admits a $k$-ideal secret sharing scheme. The characterization of ideal access structures is a longstanding open problem at the intersection of cryptography, matroid theory, and information theory, previously solved only for $k=2$ and $k=3$. In this work, we solve this problem for $k=4$ and $k=6$. Our results exploit the connections between ideal secret sharing schemes and matroids and new techniques based on latin squares. For $k=4$, we show that an access structure is $4$-ideal if and only if it admits a $\mathbb{F}_4$-linear ideal secret sharing scheme, i.e., a scheme where the shares and the secret are elements of $\mathbb{F}_4$ and the sharing and reconstruction functions are linear. To prove this result, we show that the class of matroids determined by ideal $\mathbb{F}_4$-linear schemes coincides with those determined by $4$-ideal schemes. For $k=6$, we prove that an access structure admits a $6$-ideal scheme if and only if it admits a $k$-ideal scheme for every $k\geq 2$. This result shows that domains of size $k=6$ are the most restrictive domains for constructing ideal secret sharing schemes, and that $6$-ideal schemes can be essentially built by combining ideal $\mathbb{F}_2$-linear schemes with ideal $\mathbb{F}_3$-linear schemes via the Chinese Remainder Theorem. Beyond these characterizations, our main technical contributions are the introduction of new techniques for analyzing ideal secret sharing schemes, extending the connections between ideal threshold schemes and latin squares to the general case, and the classification of the values of $k$ for which some relevant matroids are $k$-entropic.

We prove that exact Euclidean decision-CVP is $\mathsf{NP}$-complete on the coefficient lattices of nonzero principal ideals in the power-of-two cyclotomic rings $R_d:=\mathbb{Z}[y]/(y^d+1)$. Our deterministic reduction from Exact Cover by 3-Sets (X3C) produces a target and a squared threshold $\Delta$ such that the closest squared distance is exactly $\Delta$ in YES instances and at least $\Delta+4$ in NO instances. This also implies $\mathsf{NP}$-hardness of exact search-CVP under polynomial-time Turing reductions. We also transfer the resulting principal-ideal CVP instances to full-rank principal ideals of the cyclic quotient ring $\mathbb{Z}[X]/(X^D-1)$, where $D:=2d$. Their coefficient lattices are invariant under cyclic coordinate shifts. The lift preserves principality and multiplies corresponding squared distances by eight. Thus, on principal cyclic ideal lattices, exact decision-CVP is $\mathsf{NP}$-complete and exact search-CVP is $\mathsf{NP}$-hard. We also obtain uniformly computable fixed cyclotomic and cyclic families in which only the target and threshold depend on the X3C collection. Consequently, a polynomial-time solution to exact decision-CVPP on either family would imply $\mathsf{NP}\subseteq\mathsf{P}/\mathrm{poly}$ and collapse the polynomial hierarchy to $\Sigma_2^{\mathsf{P}}$. To our knowledge, the cyclic results answer Micciancio's questions of whether exact decision-CVP is $\mathsf{NP}$-hard on cyclic lattices and on a fixed family of cyclic lattices, even when restricted to full-rank principal cyclic ideals. Finally, under the coefficient embedding, we prove that exact decision-module-SIVP is $\mathsf{NP}$-complete on free rank-two modules over the same cyclotomic rings.

Poseidon/Poseidon2 and Neptune are prominent primitives for zero-knowledge proof systems. Their arithmetic circuit cost is reduced mainly through partial S-box layers and low-degree finite field operations. Algebraic attacks are therefore a central part of their security analysis, and Gr\"obner basis methods are a main tool for studying such attacks. For such attacks, controlling the algebraic degree of the polynomial systems induced by partial rounds is a central issue. Previous work has shown that linear subspace trails can reduce the algebraic degree of partial rounds in constrained-input-constrained-output (CICO) problems. Therefore, subspace analysis has become an important tool for evaluating the algebraic security of Poseidon-like permutations. The main contribution of this paper is to extend the existing linear subspace trail framework to nonlinear subspaces. More precisely, we first introduce a parametric Macaulay matrix method. This method transforms the search for algebraic constraints that reduce degree growth into the problem of solving a parametric system. It provides a general algebraic approach for constructing longer nonlinear subspace trails that suppress degree growth over more internal partial rounds. Second, for the CICO problem with $Ec$ extra constraints, we give a concrete constraint pattern that extends a linear subspace trail into a nonlinear one. In this nonlinear construction, the first $Ec$ subspace constraints generate an ideal, and further compatible subspace constraints can be added along the chain without enlarging this ideal. As a result, the nonlinear subspace trail can cover up to $2Ec$ internal rounds, whereas the previous linear subspace trail can cover up to $Ec$ rounds. We further show that the balancing matrix required by this construction is generically nonsingular. Furthermore, we propose subspace modeling variants without variable substitution. These variants impose linear or nonlinear constraints directly on high-degree intermediate states. For the Poseidon/Poseidon2 and Neptune instances proposed by Grassi et al. in ToSC 2025, our experiments show that, under the same complexity bound and the same Gr\"obner basis cost model, the nonlinear subspace model can analyze approximately twice as many internal partial rounds as the linear subspace model considered in ToSC 2025. For several concrete instances, our method reaches or even exceeds the recommended number of internal rounds given by the designers in sponge mode or compression mode.

Membership inference attacks expose whether individual records were used to train a model, yet existing attacks on diffusion models are largely heuristic and can require substantial query budgets. We introduce $\textbf{DIME}$ ($\textbf{D}$enoiser $\textbf{I}$deal $\textbf{M}$embership $\textbf{E}$rror), a theoretically grounded and query-efficient framework for membership inference on diffusion models. Our starting point is an exact characterization of the optimal diffusion denoiser for a finite training set, which reveals that membership leakage is governed by the denoiser's implicit reconstruction error. This error decomposes into two complementary signals: a $\textit{bias term}$, capturing reconstruction accuracy, and a previously unexplored $\textit{local crowding term}$, capturing the geometry of nearby training examples. Both admit efficient estimators using only model queries, yielding a practical attack with as few as two queries. Across CIFAR-10/100, STL10-U, CelebA, and ImageNet, $\textbf{DIME}$ consistently outperforms prior attacks at comparable or substantially lower query cost, improving TPR at 1% FPR by up to $3\times$; remarkably, its two-query variant can outperform existing 30-query baselines. Finally, we suggest, discuss, and evaluate specific defenses to counteract such powerful membership tests.

Post-quantum deployments need signatures that are both fast and small. ML-DSA gives a practical Fiat-Shamir lattice-signature baseline, but its signatures remain large enough to make bandwidth, certificate size, and signed-log storage first-order costs. Gaertner's iterative rejection sampling construction (CRYPTO'25) shows that this design family can be made much more compact. The open question is whether this theoretical design can be turned into a concrete, implementation-oriented signature scheme, where the parameters, algorithms, encodings, and optimized software work together without giving up the promised compactness. We present Lithium, a compact Fiat-Shamir lattice signature that makes iterative rejection sampling practical. Lithium co-designs its parameters, discrete Gaussian sampler, ApproxExp evaluation, iterative rejection sampling, and rANS encoder so that compact signatures do not come at the cost of an impractical signer. For the core components, we introduce algorithmic and vectorized optimizations and provide a portable reference implementation together with vectorized AVX2 and AVX-512 implementations. Lithium-120 targets a security level close to ML-DSA-44. Our experiments show that our fastest implementation signs faster than ML-DSA-44, at 166k versus 191k cycles, while producing signatures about half as large: 1,187 bytes versus 2,420 bytes. Compared with HAETAE-120, Lithium-120 is more compact and signs about 7.5x faster.

In the Internet of Vehicles (IoV), content-centric data sharing is essential for driving safety and user experience. However, the highly dynamic and distributed IoV network raises challenges such as unauthorized data access and inefficient information dissemination. Although existing proxy re-encryption (PRE) schemes with revocation partially mitigate these concerns, they still have key shortcomings: (i) computational costs that grow linearly with the number of attributes; (ii) heavy cloud-side overhead from re-encryption and outsourced decryption, causing delays or decryption failures; and (iii) revocation mechanisms that are inefficient or insufficiently responsive in handling malicious users. Recent studies have addressed these issues, but many schemes still struggle to ensure reliable message recovery in dynamic IoV scenarios. To overcome these limitations, we propose HRFPRE, an efficient proxy re-encryption mechanism based on multi-RSU outsourcing and hardware-assisted revocation. Our scheme provides constant-size public parameters and lightweight user-side decryption over asymmetric pairing-friendly groups, while supporting an unbounded attribute space. Re-encryption requires only four pairing operations and supports a novel "encrypt-then-offline hosting" model for vehicles. Simultaneously, Roadside Units (RSUs) provide outsourced re-encryption, key generation assistance, and decryption services to resource-constrained onboard units, effectively shifting computational load away from the cloud. By integrating a key-decoupled Trusted Execution Environment (TEE), HRFPRE enables immediate revocation and keeps plaintext recovery dependent on the user-held key even under TEE-side side-channel leakage. Under the Decisional Linear (DLIN) assumption, HRFPRE achieves adaptive security while resisting replay and collusion attacks. Theoretical analysis and experiments show that HRFPRE reduces computational and communication overhead, making it suitable for secure data exchange in dynamic IoV environments.

With the increasing deployment of resource-constrained devices in daily life, ultra-lightweight ciphers become a necessity to tackle the security and privacy concerns in resource-constrained devices. In 2023, G\"{u}l and Kara studied the question of how to design a secure ultra-lightweight stream cipher with a small internal state, and introduced a new small-state stream cipher called DIZY. The cipher utilizes Truncated Pseudorandom Permutations (TPP) and has a provable security in the indistinguishability model. It consists of two versions, called DIZY-128 with a 128-bit key and DIZY-80 with an 80-bit key, respectively. In this paper, effective key recovery attacks on DIZY-80 and DIZY-128 are proposed. Both attacks leverage the weakness of DIZY that the attacker can easily reach a weak state in the middle of the initialization using chosen IVs. Based on constructing Hellman tables, the key recovery attacks on DIZY-80 and DIZY-128 are further improved. The cryptanalytic results show that DIZY-80/DIZY-128 can only provide a 65/86-bit security level against the key recovery attack, while it is claimed to provide an 80/112-bit security level by the designers. Finally, an improved variant of DIZY, called DIZYa, is proposed. The analysis on DIZYa shows that the improved variant can provide better security resistance against all known attacks including our attacks on DIZY, while maintaining the commendable characteristics of DIZY. This makes DIZYa a more suitable small-state stream cipher choice for resource-constrained devices like RFID tags.

Wiedemann XL is a variant of the XL algorithm that has been widely used in algebraic attacks. Usually, the cost of applying Widemann XL is estimated as 3N^2 ω, where N is the width of the Macaulay matrix, and ω is the average row weight of the Macaulay matrix. Among 3N^2 ω, 2N^2 ω is from the 1st phase of the algorithm, while N^2 ω is from the 3rd phase of the algorithm. This paper shows a practical optimization that reduces the cost of the 3rd phase by a huge factor so that its cost becomes essentially negligible compared to that of the 1st phase. Our optimization makes use of the fact that, to obtain a solution of the multivariate system, only a few coordinates of the kernel vectors are needed.

We give an itemized conditional arithmetic estimate for ``Holdout'' key recovery on each Classic McEliece parameter set. This attack uses polynomial relations to recover locators, the hidden field values specifying the code. Shortening restricts codewords to zero on selected positions and then deletes those positions. Assuming the public tests uniquely recover enough compatible locator values, one shortened coordinate set suffices for each parameter set, instead of the four or five in the analysis of Ghoshal, Ishai, Jain, and Sun. We make the linear solves reliable using Eberly's random scaling of rows and columns and scalar Lanczos, an iterative solver over a larger field. Returned solutions are mapped back and checked in the original equations. Charging operations with binary coefficients separately from general field arithmetic gives conditional arithmetic estimates of $2^{126.77}$ bit operations for mceliece348864, $2^{145.22}$ for mceliece460896, $2^{137.48}$ for mceliece6688128, $2^{136.65}$ for mceliece6960119, and $2^{137.48}$ for mceliece8192128}. The corresponding working-memory estimates are $2^{51.33}$, $2^{59.10}$, $2^{55.18}$, $2^{54.86}$, and $2^{55.18}$ bits. All five arithmetic estimates lie below the NIST classical-gate reference level for their claimed category; the model excludes address generation and memory traffic and uses budget estimates for some stages.

Indistinguishability obfuscation (iO) combined with one-way functions (OWFs) serves as a powerful foundation for constructing a vast array of cryptographic primitives. However, this combination faces a known black-box barrier established by Asharov and Segev (FOCS '15), which proves the impossibility of constructing collision-resistant hash (CRH) functions. The Asharov-Segev barrier naturally extends to stronger primitives that imply CRH, such as fully homomorphic encryption (FHE) and somewhere-extractable non-interactive batch arguments (seBARGs). This work investigates the power of iO and rerandomizable primitives in constructing such "CRH-hard" primitives. First, we demonstrate the first direct and simple approach to building CRH from iO and rerandomizable OWFs. The only previously known construction was due to Arnon, Ben-David and Yogev (CRYPTO '25), and needed to go through the construction of the adaptively sound SNARG of Waters and Wu (STOC 24'). Using the same approach, we additionally construct a strictly stronger primitive than CRH, which we call perfectly partitionable hash (PPH), from iO and rerandomizable commitments. Second, we demonstrate the power of rerandomizability for building advanced non-interactive proof systems. Using iO and rerandomizable commitments, we provide a construction of seBARGs with statistical extraction, a security property not achieved by most existing seBARG schemes. By additionally relying on rate-1 fully-homomorphic encryption, we construct the first rate-1 seBARG with statistical extraction. Along the way, we introduce a SNARG that is "sometimes statistically sound", and construct it from iO and rerandomizable commitments.

Univariate-polynomial interactive oracle proofs (IOPs) over binary extension fields $\mathbb{F}_{2^m}$ underpin a class of plausibly post-quantum zkSNARKs, but rely heavily on polynomial arithmetic, where large-domain evaluation and division by subspace vanishing polynomials are the dominant prover costs. General-basis additive FFTs, such as Gao--Mateer and Lin-Chung-Han (LCH), accelerate the evaluation but impose a basis-conversion stage costing $O(n (\log n)^2)$ field additions and $O(n \log n)$ field multiplications that dominates in practice. To eliminate basis conversion entirely, we introduce a divide-and-conquer algorithm for polynomial division by vanishing polynomials that operates directly in the LCH polynomial basis, for arbitrary $\mathbb{F}_2$-basis elements, achieving optimal $O(n \log n)$ complexity. In the LCH polynomial basis, multiplying a vanishing polynomial by the random blinding polynomial reduces to appending random field elements, eliminating the multiplication entirely. We integrate native LCH-basis arithmetic and auxiliary optimizations across all phases of the Aurora IOP. Benchmarks on Preon (a NIST PQC Round-1 signature scheme candidate built on Aurora) show end-to-end signing speedups of $5.0\times$ for Preon-128A and $5.8\times$ for Preon-256C, with the polynomial transform alone $12.6$--$17.9\times$ faster.

Blind rotation is the dominant computational bottleneck in bootstrapping for bitwise FHE schemes such as TFHE. Existing constructions typically evaluate $O(n)$ sequential external products for an LWE secret of dimension $n$, incurring substantial latency and a large number of NTT/iNTT operations. In this work, we present a new framework for NTRU-based bootstrapping that reduces the sequential complexity of blind rotation for sparse binary LWE secrets. Inspired by Jain et al. (CRYPTO 2026), we use Cuckoo hashing to transform an $n$-dimensional binary LWE secret of Hamming weight $h$ into extended buckets of one-hot representation. This structured representation reduces the sequential external products from $O(n)$ to $O(h)$ in blind rotation. We also design a modulus-switching method tailored to sparse secrets. We further explore an NTT-free variant that eliminates all online NTT/iNTT operations during blind rotation while supporting gate bootstrapping with lower parallel depth, offering a potentially useful building block for hardware-friendly FHE implementations. Empirically, we achieve state-of-the-art bootstrapping performance on both CPUs and GPUs. At comparable decryption failure rates and on a single CPU thread with AVX-512, our implementation executes Boolean gate, 4-bit, and 6-bit bootstrapping in $0.83$, $1.75$, and $2.65$\,ms, outperforming TFHE-rs by $3.31\times$, $4.18\times$, and $20.47\times$, respectively. On an RTX~4090 GPU, we attain a throughput of $154{,}739$ gate bootstraps per second, corresponding to an amortized time of $6.46\,\mu\mathrm{s}$, and speedups of $86.7\times$ over our CPU result and $13.6\times$ over VeloFHE (Shen et al., TCHES 2025). As a concrete application, we develop the first NTRU-based 8-bit FHE instruction set, achieving up to over $10\times$ speedup over Trama et al. (TCHES 2025) with over $100\times$ smaller key size.

SNARKs based on error-correcting codes require codes that simultaneously support fast encoding and large relative distance. Reed--Solomon codes achieve the optimal rate--distance tradeoff given by the Singleton bound, but their fast encoding relies on FFT-friendly fields, limiting their applicability to field-agnostic constructions. In this work, we revisit expand--accumulate (EA) codes, a simple family of linear codes with efficient encoding over arbitrary fields. Although extensively studied in prior work, existing distance guarantees are weak, and practical instantiations have relied on conjectured results. We prove that EA codes with exact-weight expansion matrices, over sufficiently large fields, achieve a rate--distance tradeoff that approaches the Singleton bound with high probability, resolving these conjectures. Building on this result, we construct \textsf{Flare}, a field-agnostic polynomial commitment scheme based on EA codes. At its core is an efficient IOPP for EA codes that leverages code switching. For statements of size $M$, \textsf{Flare} achieves $O(M\log M)$ prover time and $O(\lambda\log^2 M)$ proof size, improving upon the $O(\sqrt{\lambda M})$ proof size of prior constructions based on EA codes (Block et al., CRYPTO 2024). Comprehensive evaluations show that \textsf{Flare} achieves compact proofs while maintaining competitive prover efficiency. For proving circuits of size $2^{22}$, \textsf{Flare} produces the smallest proofs of approximately $16$~MiB. Compared with BaseFold (Zeilberger et al., CRYPTO 2024) and ERA (Baweja et al., ASIACRYPT 2026), it reduces proof size by $1.66\times$ and $1.47\times$, respectively, while maintaining comparable prover efficiency. Compared with Brakedown (Golovnev et al., CRYPTO 2023), \textsf{Flare} produces $4.85\times$ smaller proofs at the cost of only a $1.50\times$ slower prover.

Additive Randomized Encodings (AREs) provide a lightweight route to non-interactive secure computation: each party locally produces a randomized encoding of its input, and an evaluator learns only the function value from the sum of these encodings. Prior frameworks for constructing AREs for general functions ultimately hinge on an efficient ARE for string oblivious transfer (SOT), making SOT the core efficiency bottleneck. We revisit this final step and present improved ARE constructions for SOT. First, we streamline the recent PKE-based approach by directly constructing the required one-sided ARE (OSARE) for SOT. This yields a perfectly correct, statistically one-sided secure OSARE for SOT of size $\mathcal{O}(\lambda)$, improving the intermediate overhead and, consequently, the overall size of the resulting PKE-based ARE. Second, we give a pairing-free ARE for SOT under the Squaring DDH assumption. Our construction is compatible with Halevi et al.'s efficient equality-to-SOT methodology: we build an ARE for Rabin-OT that embeds a message in the equality-checking procedure and then transform it to SOT while incurring only constant-factor communication overhead and no additional correctness error. The resulting ARE for SOT has size $\mathcal{O}(\lambda)$ and negligible correctness error.

Private information retrieval (PIR) protocols allow a user to retrieve an entry from a database held by several servers without revealing any information about the index to any individual server. State-of-the-art information-theoretic PIR protocols are based on a combination of matching vectors over the ring $\mathbb{Z}_m$ and decoding polynomials (Efremenko, SICOMP 2012; Dvir and Gopi, STOC 2015; Ghasemi, Kopparty, and Sudan, STOC 2025). Decoding polynomials are sparse polynomials over a field $\mathbb{F}_q$, where $q$ is a prime power coprime to $m$, that evaluate to a nonzero value at $1$ and to $0$ on a certain set of inputs determined by $m$. The properties of decoding polynomials were abstracted by Beimel, Ishai, Kushilevitz, and Orlov (CCC 2012) through the notion of share conversions. Share conversions allow a set of parties to locally convert a secret shared under one scheme into a related secret shared under another scheme. They constructed a share conversion from $\mathbb{Z}_m$ to $\mathbb{F}_{q}$ for various values of $m$ and prime-powers $q$. More recent PIR protocols by Dvir and Gopi and by Ghasemi et al. were abstracted by Alon, Beimel, and Lasri (TCC 2025). The share conversion they considered transforms shares from the ring $\mathbb{Z}_m$ to a finite field $\mathbb{F}_q$, where $q$ is a prime-power coprime to $m$. We observe that if the initial conversion is based on a $t$-private secret-sharing scheme, then the resulting PIR protocol of Alon et al. is also $t$-private: no set of $t$ servers learns any information about the user's index. We call such share conversions $t$-private share conversions. Moreover, the resulting PIR protocol could potentially achieve communication complexity better than that of the best-known $t$-private PIR protocols, due to Woodruff and Yekhanin (CCC 2005) and Barkol, Ishai, and Weinreb (APPROX-RANDOM 2007). This raises the natural question of whether $t$-private share conversions exist. We show that there is no $t$-private share conversion from $\mathbb{Z}_m$ to $\mathbb{F}_q$ when $t\geq 2$ and $q$ is coprime to $m$. As a result, the PIR framework of Alon et al. cannot be instantiated in a way that yields a $t$-private PIR protocol. We further generalize the result to conversions whose output is in the ring $\mathbb{Z}_{m'}$.

Ring switching provides a natural way to reduce bootstrapping cost in ring-based fully homomorphic encryption by moving computation to smaller rings. For SIMD-packed ciphertexts, however, ring switching changes the slot layout, so conventional approaches apply slot recovery to ensure correct computation on the original slot values, consuming capacity and requiring synchronization across ciphertexts. In this paper, we show that slot recovery is not indispensable: CKKS and BGV/BFV bootstrapping can proceed directly after ring switching. We further prove that a continuous slotwise function admits independent leaf evaluation for unrestricted real CKKS inputs exactly when it is affine. Our construction provides an extra layer of parallelism, enables cheaper arithmetic in smaller rings, and can further simplify bootstrapping by exploiting the leaf structure. For CKKS with \(N=2^{17}\) and \(n=2^{16}\), we achieve a \(1.13\times\) serial speedup; evaluating two leaves in parallel yields a \(2.03\times\)--\(2.18\times\) speedup and \(2.00\times\)--\(2.14\times\) the throughput of direct bootstrapping. For BGV with \(p=65537\), \(N=2^{16}\), and \(n=2^{15}\), we achieve a \(1.30\times\) serial speedup and \(1.63\times\) the throughput of direct general bootstrapping under matched transform settings, while reducing key-generation time by \(50.6\%\) and server-key size by \(48.6\%\).

Higher-Order Vanishing (HOV), introduced by Hemmert and Wiemers at CRYPTO 2026, distinguishes Goppa codes and was recently extended to McEliece key recovery. We introduce a new variant of HOV, HOVER (Higher-Order Vanishing Endomorphism Recovery), that replaces the costly low-rank direction-search phase of HOV with a much faster linear algebra step. Our attack is based on the observation that the first catalecticants (the coefficient matrices of first partial derivatives) of the public HOV kernel define a contraction tensor; HOVER computes the coefficient endomorphisms that preserve all relations of this tensor. In the clean case, in which the scalar-extended HOV kernel is spanned by exactly the $m$ hidden Frobenius directions, this public algebra is $\mathbb{F}_{2^m}$, and the eigenspaces of a field generator are exactly those directions, already ordered by Frobenius. We give a basis-invariant construction, a structural classification of its possible matrix-algebra outputs, and explicit acceptance conditions that return $\bot$ rather than an uncertified output. During our end-to-end public-only experiments, we recovered keys for five Technology Innovation Institute (TII) McEliece challenges, including TII-252, whose label originally represented a $2^{252}$ brute-force enumeration model. However, our analysis does not indicate that HOVER would threaten Classic McEliece parameters in its present form. Lastly, we note that HOVER's main cryptanalytic shortcut was discovered with a large language model, underscoring the strong potential of AI cryptanalysis.

The classic function-inversion problem considers the task of constructing a data structure which, given access to a constant-time oracle for a function $f : [N] \rightarrow [N]$, supports efficient inverse-queries on $f$. This problem has been studied extensively in the small-space/large-time regime, where one wishes to use space $S$, say, $N^{1 - \Omega(1)}$ bits, and where the query time is intended to be a small polynomial of $N$. Much less attention has been given to the \emph{small-time/large-space} regime, where $S = (N \log N) / t$ for some relatively small $t$, and where the goal is to achieve a good space bound as a function of $t$. In this paper, we give an optimal solution in the small-time regime, achieving space $S = O(N \log N / t)$ and time $O(t)$ for any $t \le O(\log N / \log \log N)$. This matches a lower bound by Yao (and is the first parameter regime where the lower bound has been matched for general functions). Additionally, we extend our solution to support point-updates to $f$, also in $O(t)$ time. Our techniques for supporting point updates also extend to the classic function-inversion solution of Fiat and Naor. All of our results are motivated by the data-structural perspective on function inversion, in which the goal is to supplement an already-existing data structure $\mathcal{D}_1$ (which, as part of its functionality, encodes some function $f$) with a small secondary data structure $\mathcal{D}_2$ that supports inverse queries. Our results allow $\mathcal{D}_2$ to be implemented in $(N \log N)/t$ bits with $O(t)$ query (and update) times -- if $\mathcal{D}_1$ is itself $\Theta(N \log N)$ bits, this results in the overall space usage increasing by only a $(1 + O(1/t))$ factor. As a sample application of our results, we show how to construct dynamic unordered graphs that use space $(1 + \epsilon)$-close to information-theoretically optimal while offering adjacency queries, neighborhood queries, and edge insertions/deletions in amortized time $O(\epsilon^{-1})$.

Proving an elliptic curve scalar multiplication [k]P= Q ∈ E(Fp) inside a SNARK is much cheaper when the output Q is hinted by the prover and only verified in-circuit, rather than recomputed. The recent scalar multiplication techniques of Eagen, El Housni, Masson and Piellard (Latincrypt 2025) certify a hinted Q with a short lattice reduction (fraction) decomposition of the scalar and a single group identity, and yield the fastest known in-circuit scalar multiplications. We observe that the soundness of this whole family rests on an implicit prime-order hypothesis: the certifying identity is checked over the full group E(Fp), and only when E(Fp) has trivial cofactor does it force Q into the prime-order subgroup. On cofactor curves the certification is unsound. We give two concrete forgery classes against these hinted gadgets: an any-scalar attack that, for a target scalar fixed by the statement, adapts the decomposition so a small rational torsion point cancels from the identity; and a chosen-scalar attack that vanishes the output-side coefficients modulo a small cofactor prime and solves for the scalar afterwards. Both make the gadget accept Q′ = [k]P + T for a non-zero torsion point T as if it were [k]P. We quantify the reachable torsion in terms of the sub-scalar range bound and validate the attacks on widely deployed curves such as BLS12-381, BN254 and BW6-761. The straightforward fix is to check that Q lies in the subgroup but is expensive. We propose a cheaper one that binds the hinted output through a hinted preimage, with the minimal such constant that suffices against each attack model.

Aardal et al. (CRYPTO 2025) provided the first complete security proof of SQIsign; however, their reduction incurs a square-root loss in the prime characteristic due to the application of a loose bound on the min-entropy. For instance, at NIST security level I, an adversary making $2^{64}$ signing queries renders the security proof vacuous. In this note, we show that the min-entropy of SQIsign is optimal, namely $\mathcal{O}(1/p)$. Although this improvement does not yield full $\lambda$-bit security, we show that it preserves two-thirds of the expected bit-security. We show that this artifact comes from an information-theoretic loss in the zero-knowledge simulation of SQIsign, suggesting a new proof technique is needed to achieve full $\lambda$-bit security at the current parameters.

Multi-party private set intersection (MPSI) enables multiple parties to securely compute the intersection of their private datasets without revealing any information beyond the intersection itself. However, as the number of participants scales, the performance of multi-party PSI protocols is significantly influenced, with the number of interaction rounds emerging as a critical bottleneck. In this paper, we propose a novel MPSI protocol and its updatable extension based on function secret sharing and oblivious key-value stores, achieving optimal one-pass online interaction. Our construction guarantees security in the semi-honest model, resisting collusion among any $n-1$ parties when the Leader is honest, and among any $n-2$ parties when the Leader is corrupted—an assumption that aligns well with many practical deployment scenarios. Furthermore, our multi-party updatable PSI (MUPSI) protocol allows parties to efficiently compute the intersection over dynamically updated sets. Our MUPSI protocol achieves collusion resistance against any $n-1$ participants, assuming an honest Leader. It ensures that both computational and communication complexities scale exclusively with the size of the updates rather than the entire datasets, exhibiting superior performance particularly when handling unbalanced sets and large participant cohorts. All proposed protocols exhibit strong scalability with respect to participant count. We demonstrate the superiority of our protocols through implementation and comparison with state-of-the-art MPSI protocols. Experiments show that when the number of participants ranges from $20$ to $140$ and the set size ranges from $2^{12}$ to $2^{20}$, our MPSI protocol is competitive. Notably, in the WAN setting with $140$ participants and a set size of $2^{20}$, the running time is reduced by $49.1\times$ compared with GLW+24. Our MUPSI protocol avoids PSI operations on entire sets, achieving a reduction in running time by an order of magnitude.

Token-weighted governance can fingerprint individual voters: when weights are unequal and externally known, the exact weighted tally may reveal who voted which way. Publishing only the winning outcome hides the tally from the public, but a system that reconstructs the tally in order to decide still hands it to whoever runs the computation. Publishing only the winner is not the same as computing only the winner. We present a verifiable protocol for weighted DAO votes in which no protocol role ever receives the weighted tally in plaintext. Each ballot proves in zero knowledge that its encrypted contribution is exactly zero or the voter’s registered weight. Trustees add accepted contributions and compare the sum with a threshold entirely under encryption using the Cortier–Gaudry–Yang (CGY) conditional-gate toolbox, and decrypt only the final decision. A public verifier checks that the computation consumed exactly the ciphertexts accepted by the governance contract. We prove accepted-result correctness even when all trustees are malicious; restricted-I/O SUC security of the tally against static active corruption of any sub-threshold trustee coalition, which is any four of five in our reference instance; and winner-only disclosure relative to the real sealed board. With 1,024 voters, the encrypted tally takes 157 s and independent replay 115 s, while ballot proving dominates the 28.5-minute end-to-end pipeline. A fresh Arbitrum Sepolia execution exercises the complete public-chain path.

An oblivious key-value store is a data structure that can encode and decode $n$ key-value pairs in a table of size $m$ obliviously. After encoding, one cannot distinguish the encoded key-value pairs from other key-value pairs in the input domain. In this paper, we first propose a data structure called Peelable Garbled Bloom Filter (PGBF), which encodes the key-value pairs in a similar way to peeling and unpeeling an \emph{onion}. Specifically, it can divide the key-value pair set (i.e., onion) as multiple subsets (i.e., peels) and order them from the outermost peel to the innermost peel by using a counting Bloom filter. However, using a small expansion rate (i.e., $\eta=m/n$) in PGBF will result in a non-empty core issue with non-negligible probability. To handle this issue, we propose Multi-PGBF by combining multiple PGBFs to do the peelings and unpeelings recursively. In addition, we propose a variant C-Multi-PGBF by clustering a large set into small sets to achieve faster encoding efficiency. Our experiments show that Multi-PGBF and C-Multi-PGBF obtain the best encoding and decoding efficiency. Multi-PGBF improves the encoding time of RR (CCS’22) by $65.1\%\sim 77.6\%$, while C-Multi-PGBF improves the encoding time of the clustered RR variant by $60.2\%\sim 64.7\%$. For decoding, Multi-PGBF is $28.6\%\sim 62.4\%$ faster than RR (CCS'22) and $89.7\%\sim 96.3\%$ faster than RB-OKVS (Usenix'23). When integrated into the state-of-the-art two-party and multi-party private set intersection protocols (Eurocrypt'21, Usenix'24), Multi-PGBF and C-Multi-PGBF lead to faster protocols than those using existing OKVS constructions in most settings.