Fully homomorphic encryption (FHE) enables computation over encrypted data subject to the prescribed security and precision requirements (allowable deviations from ideal results). Among all FHE schemes, CKKS is a representative scheme for approximate arithmetic, allowing the same operation on multiple values packed into a single RLWE ciphertext. Reducing ciphertext modulus \(Q\) for given output precision requirements under RLWE security constraints is a central challenge in homomorphic computation. However, despite advances in plaintext and ciphertext representations, algorithmic optimizations, and modulus management, the budget in most existing approaches remains dependent on the highest required precision and cannot reduce the baseline modulus cost to overcome encryption noise. In this work, we make average rather than maximum precision requirements govern the modulus budget and achieve savings in the baseline cost. Under decryption correctness constraints, we make these possible by allocating arbitrary output precision among independent values and quantify the modulus savings arising from differences in their precision requirements. As a bonus, our construction preserves the standard CKKS ciphertext format, which helps maintain compatibility with existing optimizations. And the construction inherits the IND-CPA security of CKKS without additional cryptographic assumptions. In a repeated squaring experiment, we use 67% fewer initial modulus bits and one quarter of the ring dimension of standard CKKS, while meeting the same precision and security requirements.

To enhance the security of stealth addresses and protect user privacy, Liu et al. (EuroS&P 2019) proposed a Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Keys (PDPKS). In this scheme, the payee generates a master public/secret key pair, and the payer derives a public key from the payee's master public key and binds the cryptocurrency asset to the resulting derived public key. The payee then verifies, using the master secret key, whether the derived public key has been correctly generated from the master public key. In this paper, we show that a public-key encryption (PKE) scheme secure against chosen-ciphertext attacks (CCA) can be generically constructed from PDPKS. Specifically, we utilize unlinkability, which hides the master public key from which a derived public key originates, to conceal plaintext information from ciphertexts. We also simulate the decryption oracle by leveraging the derived public key checking algorithm. In addition, to guarantee the correctness of the proposed PKE scheme, we rely on the consistency of PDPKS introduced by Emura (IACR CiC 2025). Given the motivation behind PDPKS, namely the construction of stealth addresses in a provably secure manner, unlinkability is regarded as the core security property of PDPKS. Our result shows that achieving this core security property essentially requires CCA-secure PKE, or cryptographic primitives of equivalent strength, and that such primitives are indispensable for constructing PDPKS.

Prior research on ensuring trust in delegated computation through lattice-based zero-knowledge proofs mostly rely on Learning-With-Errors (LWE) assumption. In this work, we propose a zero-knowledge proof of knowledge using the Ring Learning with Rounding (RLWR) assumption for an interesting and useful class of statements: linear relations on polynomials. We begin by proposing, to the best of our knowledge, the first efficient commitment scheme in literature based on the hardness of RLWR assumption. We establish two properties on RLWR that aid in the construction of our commitments: (i) closure under addition with double rounding, and (ii) closure under multiplication with a short polynomial. Building upon our RLWR commitment scheme, we consequently design a RLWR based $\Sigma_2$ protocol for proving knowledge of a single committed message under linear relations with public polynomials. As an use-case of our proposed $\Sigma_2$ protocol, we showcase a construction of a quantum-safe Searchable Symmetric Encryption (SSE) scheme by plugging a prior LWR based SSE scheme from (EuroS&P 2023) with our $\Sigma_2$ protocol. Concretely, using our $\Sigma_2$ protocol for linear relations, we prove the correctness of an encrypted search result in a zero-knowledge manner. We implement our verifiable SSE framework and show that the overhead of an extra verification round is negligible ($0.0023$ seconds) and retains the asymptotic query execution time complexity of the original SSE scheme. Our work establishes results on zero-knowledge proof systems that can be of independent interest. By shifting the setting from RLWE to RLWR, we gain significant (i) efficiency improvements in terms of communication complexity by $O(M)$ (since some prior works on RLWE require rejection sampling by a factor of $M$), as well as (ii) very short proof size ($8.4$ KB) and tighter parameters (since RLWR does not explicitly manipulate error polynomials like RLWE).

An important class of plausibly post-quantum zkSNARKs uses univariate-polynomial interactive oracle proofs (IOPs) over binary extension fields $\mathbb{F}_{2^k}$, relying on the Fast Reed--Solomon (RS) Interactive Oracle Proof of Proximity (FRI) for low-degree testing. Their provers fold RS codewords in FRI and perform polynomial arithmetic, notably division and multiplication by subspace vanishing polynomials. Constraint polynomials and RS codewords are in evaluation form, but existing implementations perform this arithmetic in the monomial basis, requiring inverse additive fast Fourier transforms (FFTs) for coefficient recovery and forward FFTs for evaluation. On a general basis, Gao--Mateer and Lin--Chung--Han (LCH) additive FFTs incur $O(n(\log n)^2)$ field additions and $O(n\log n)$ field multiplications for basis conversion per $n$-point transform, and Lagrange-based FRI folding performs a field inversion per coset. We carry out this arithmetic directly in the LCH polynomial basis for arbitrary $\mathbb{F}_2$-bases. We introduce a divide-and-conquer algorithm for division by subspace vanishing polynomials directly in the LCH basis. For $n$ input coefficients, it requires $O(n)$ field operations, and on a Cantor basis it requires no field multiplications. We also show that the multiples of vanishing polynomials used for zero-knowledge blinding can be sampled directly through their LCH coefficients. Together, these remove the basis-conversion stage of the LCH additive FFT, leaving only its butterfly. We further express the FRI fold in the LCH basis: on each coset, it is an LCH inverse butterfly followed by an evaluation at the verifier challenge, and for higher-arity folds, the challenge of each stage is the value of a normalized subspace vanishing polynomial at the verifier challenge. Given constants that depend only on the domain, this yields a fold without field inversions whose folding loop performs $n(1-1/\kappa)$ field multiplications for a length-$n$ codeword and arity $\kappa$; for every input word, it outputs the same next codeword as the classical fold. We integrate these algorithms into the Aurora prover without changing the proof or the verifier. At $2^{19}$ constraints over $\mathbb{F}_{2^{256}}$, when all configurations use our FRI fold, the LCH-basis arithmetic speeds up the prover by $2.80\times$ over \texttt{libiop} on a general basis and by $1.24\times$ over a Cantor-basis prover that uses the LCH additive FFT. Against these baselines with their Lagrange-based FRI fold, the speedups are $3.63\times$ and $2.05\times$.

Programmable bootstrapping (PBS) in TFHE is a powerful primitive for homomorphic lookup-table (LUT) evaluation, but its practical precision is limited to $O(\sqrt{N})$ for RLWE dimension $N$. Existing solutions either enlarge the RLWE dimension or digit-decompose plaintexts before encryption, thus degrading either bootstrapping efficiency or the efficiency of downstream linear combinations. We propose Meta-PBS, a single-ciphertext high-precision PBS framework that supports plaintext modulus up to $2N$ without increasing the RLWE dimension. The key idea is to view PBS through a redundancy-perturbation perspective: Meta-PBS starts from an under-redundant LUT and iteratively increases its redundancy by combining blind rotations with LWE-to-RLWE packing. Under this view, classical TFHE PBS becomes the zero-iteration special case of Meta-PBS. Asymptotically, Meta-PBS supports PBS with a plaintext modulus $2N$ with only $O(1)$ blind rotations, leading to an $O(\sqrt{N})$ speedup compared with PBS. Another key advantage of Meta-PBS is its additive noise growth, which enables more efficient parameters and stronger support for post-bootstrap homomorphic linear combinations. In practice, Meta-PBS evaluates a 12-bit negacyclic LUT in 166 ms, achieving an $81.0\times$ speedup over EBS. For an arbitrary 8-bit LUT, a high-capacity Meta-WoP-PBS configuration is $2.04\times$ faster than Refined LHE while supporting post-bootstrap linear combinations of size up to 25,000; a lower-capacity configuration reaches a $2.61\times$ speedup.

In 2009, Galindo and Garcia (Africacrypt) proposed the use of concatenated Schnorr signatures for hierarchical public key delegation, creating an efficient identity-based signature scheme (IBS). Essentially, the scheme builds upon the Schnorr signature scheme to generate a primary signature, part of which is then used as a secret key to produce signatures on subsequent messages. The resulting IBS is proven secure against existential forgery under adaptive chosen-message attacks in the identity-based setting using variants of the Forking Lemma. In this paper, our goal is to answer the following question: would it be feasible to build upon the widely used elliptic curve digital signature algorithm (ECDSA) scheme to obtain a similarly secure and efficient IBS? We answer this affirmatively, opening interesting possibilities not only for identity-based signatures with ECDSA but also for solutions such as secure credential delegation. This latter application is of particular interest considering the wide support for ECDSA in web- and cloud-oriented authentication systems (e.g., those based on JSON Web Tokens). We prove the security of the resulting scheme by combining the Bijective Random Oracle model and the existential unforgeability game in an identity-based setup. Our results also show that, despite its non-linear nature and more convoluted verification process than Schnorr signatures, ECDSA allows one to obtain signatures of roughly the same size as those of Galindo-Garcia's scheme while maintaining efficient performance.

In CKKS, the sign is commonly evaluated by polynomial approximation, and nonlinear functions such as comparison, ReLU, and max are computed through the sign. However, the discontinuity of the sign makes it harder to approximate with a polynomial as the required input bit precision $p$ grows. Alternatively, the sign can be computed by first decomposing the input into radix-$B$ digits. Existing methods extract the $u \approx p/\log B$ digits one at a time, taking $u$ sequential bootstrappings. Instead, we approximately round $u$ copies of the input to each digit's grid and obtain all $u$ digits in parallel, up to carries, with a single bootstrapping. The carries are then corrected in $O(\log u)$ depth. For the sign, a scan of the same form returns the sign directly, without recovering the exact digits. We show that our method distinguishes inputs separated by about $2^{-p}$ with $\Theta(p)$ modulus bits, at the cost of $\Theta(u)$ slots per input. Neither the digits nor the carries need to be computed to high precision, so our circuit, including its bootstrapping, runs at low precision. We also analyze polynomial approximation under an explicit noise and scale model, and show that, in contrast, its modulus consumption grows to $\Omega(p^2)$ bits. Benchmarks show a 2.04$\times$ speedup over [AKP25] for coefficient-encoded integer digit decomposition at ten radix-64 digits and speedups of 5.37$\times$ over [LLNK22] and 7.83$\times$ over [CKK20] for sign evaluation on real input pairs at $2^{-60}$ separation. In the tested settings, the method of [AKP25] is faster for $u \leq 4$ and that of [LLNK22] for $p \leq 36$, while our method is faster at the larger tested settings.

The HM-QCT protocol, presented by Mazzoncini et al. in 2025, uses a unique feature of quantum information to achieve quantum key distribution (QKD) with secret-key rates beyond standard constructions. The protocol has been designed in the hybrid quantum–computational time-lock (QCT) security model which imposes two independent (but related) restrictions on the attacker: (1) a computationally secure encryption scheme which a successful attacker must break within a narrow timeframe and (2) an assumption that the attacker can only store quantum information with low fidelity. We first review the protocol and its two-assumption model by presenting, in explicit form, the two natural “harvest now, decrypt later” strategies against it, one using quantum memory and one using classical memory. We show how each is excluded by exactly one of the two assumptions, so that harvesting resistance rests on their conjunction and on the presumed existence of a technological gap: the adversary's quantum memory must decohere much faster than the time it takes to break the short-term encryption. Finally, we introduce HM-PRF, a variant that replaces the short-term encryption with a pseudorandom function (PRF), evaluated locally. By eliminating the transmission of enciphered classical information, the adversary does not need to race an impending expiry event. We compare the security of our construction against the original and argue that our PRF-based assumption yields a more realistic adversary. It simply requires the existence of one-way functions rather than a predicted lasting limitation of quantum computation and memory technology.

Hair and Sahai (arXiv:2609.18275v1) have recently proposed a construction of witness encryption for NP satisfying semantic security. In this note we observe that this recent witness-encryption construction is unconditionally extractable in the generic group model. This yields a construction of extractable witness encryption without assuming subexponential soundness of SNARGs, in contrast to the recent work of Jin (ePrint 2026/2063), which requires this assumption. The result in this note, moreover, complements the concurrent work of Chen and Vaikuntanathan (ePrint 2026/2346), who show the same construction to be public-coin extractable under a knowledge-style assumption; our argument is unconditional in the GGM.

Multiparty fully homomorphic encryption (MPFHE) is a generalization of (multi-key) fully homomorphic encryption ((MK)FHE) that lives on the cusp between multiparty computation (MPC) and FHE, enabling a computation over encrypted data using multiple keys. However, contrary to MKFHE, it seeks to reduce the noise inflation based on the number of parties by allowing the parties to first compute shared data in MPC before executing the computation in FHE. However, many works use specific constructions, e.g. Chang-Li, Koirala et. al., and Ma et. al., reliant on the behaviour of a particular scheme and do not consider security against colluding servers and parties, e.g. Passelègue-Stehlé, Okada-Takagi, and Mouchet et. al. In this work we present a new framework that is secure against collusion between servers and parties and allows the use of a broad spectrum of MPC and FHE protocols, while eliminating the noise inflation based on the participating number of parties. We then show a case study of this using the FINAL scheme and show that we reduce the required key material by 60­–99.9% compared to the MKFHE FINAL scheme, FINALLY, and 65–70% compared to the Park-Rovira scheme in all cases, and by up to 71% compared to the AKÖ scheme when there are 4 or more parties. Moreover, we reduce the bootstrapping time for the AKÖ, Park-Rovira, and KMS schemes by 75–99.7%.

Pseudorandom error-correcting codes (PRCs), introduced by Christ and Gunn at CRYPTO’24, combine pseudorandomness with error correction, providing a natural abstraction for robust watermarking and steganography on generative AI models. Subsequent standalone notions, which are ideal security for secret-key PRCs and CCA-style security for public-key PRCs, are oracle-based and do not capture composable use with explicit parties, sessions, and corruption. We give a UC treatment of PRCs via corruption-aware ideal functionalities for both settings. Under non-adaptive corruption, the UC notions recover the standalone ones. Under adaptive corruption, we identify a common obstruction: dummy codewords sampled before corruption, together with their neighborhoods, must later be opened as valid PRC codewords. We formalize this as a decoder-non-committing code (NC-PRC), which any adaptively UC-secure realization must induce. We then capture failures of such openings via targeted low opening capacity, show it rules out robust NC-PRCs, and prove that LDPC-based PRCs have this property hence do not admit a NC-PRC. On the positive side, we sketch two compilers to lift error-correcting codes to admit NC-PRCs: a secret-key one from a puncturable PRF and indistinguishability obfuscation (iO), and a public-key one from a smooth projective hash function (SPHF), both evading the barrier via programmable acceptance. Finally, we identify a fresh-codeword explanation barrier for public-key PRCs: accepted unseen codewords cannot be explained from public information without violating pseudorandomness, hence public-key UC realizations require a trapdoor or an idealized setup, and PRC-based watermark detection is inherently designated-verifier.

NIST standardised ML-KEM and ML-DSA in 2024 for post-quantum key establishment and digital signatures. Both compute forward number-theoretic transforms on secret polynomials. Their fixed multipliers, called twiddles, are a documented fault-attack target. Published attacks zero every twiddle during Kyber key generation with a single fault, or individual twiddles in one Dilithium signing variant. Nonzero replacements preserve transform invertibility, raising the question of what the difference between correct and faulted outputs reveals without transform collapse. This paper characterises the linear map from a secret polynomial to that transform difference under static twiddle replacements. Each selected twiddle takes a fixed changed field value at every use during one call; zero and nonzero replacements, including qualifying bit flips, are covered. For one replacement, rank equals the number of butterflies sharing its twiddle, halving by layer from 128 to 2 for ML-KEM and to 1 for ML-DSA. Known positions and replacement values specify the linear equations, while a known transform difference supplies their values. With one replacement per layer, these equations determine every coefficient except the constant and linear coefficients for ML-KEM, or the constant for ML-DSA. Lean 4 certifies this result for both 256-coefficient network shapes over fields of characteristic other than two, with nonzero original twiddles. Those coefficients cancel from the difference for every allowed fault set and choice of replacement values. NIST permits seed storage, motivating comparison of a known correct public key with a released faulty key from the same seed. If replacements affect only one ML-KEM secret-polynomial transform and all other computations are unchanged, the decoded key difference is a known matrix column times the transform difference. An invertible column entry reconstructs the latter. For ML-DSA, neither reconstruction nor the number of secret-polynomial candidates from the paired compressed keys is established.

Nowadays, the Matrix Code Equivalence Problem shows potential applicability in constructing efficient and secure advanced digital signatures, focusing on linkable ring signatures, threshold signatures, and blind signatures. Current constructions of these advanced signatures rely on relaxed instantiations of the Matrix Code Equivalence Problem (namely, the 2-MCE problem): given two pairs of equivalent matrix codes, find (if it exists) the secret isometry connecting the pairs. For example, the linkable ring signature construction by Chou et al. (AFRICACRYPT, 2023) builds on top of the Inverse Matrix Code Equivalence Problem: given three equivalent matrix codes, where one pair of the codes is connected by the secret isometry and another by the inverse of that isometry, find the secret isometry. This paper studies the 2-MCE problem, focusing on the family of instances where the secret isometry is (skew) symmetric. Our main contribution is a polynomial-time algorithm for these instances of the 2-MCE problem. We prove that the algorithm returns a valid solution whenever an explicit invertibility condition and two kernel-dimension conditions hold. Our results have a crucial security impact on the recent blind signature construction proposed by Kuchta, LeGrow, and Persichetti (Cryptography and Communications, 2026), whose security relies on the hardness of solving these kinds of instance of the Inverse Matrix Code Equivalence Problem: we show that this problem reduces to the instances we solve. More precisely, we show that we can recover the secret key of the blind signature construction by Kuchta, LeGrow, and Persichetti (Cryptography and Communications, 2026), with an estimated security of 128 bits, in less than a minute.

Blind signatures are a fundamental cryptographic primitive with numerous practical applications. While there exist many practical blind signatures from number-theoretic assumptions, the situation is far less satisfactory from post-quantum assumptions. In this work, we provide the first overall practical, lattice-based blind signature, supporting an unbounded number of signature queries and additionally enjoying optimal round complexity. We provide a detailed estimate of parameters achieved -- we obtain a signature of size slightly above 45KB, for a core-SVP hardness of 109 bits. The run-times of the signer, user and verifier are also very small. Our scheme relies on the Gentry, Peikert and Vaikuntanathan signature [STOC'08] and non-interactive zero-knowledge proofs for linear relations with small unknowns, which are significantly more efficient than their general purpose counterparts. Its security stems from a new and arguably natural assumption which we introduce, called the one-more-ISIS assumption. This assumption can be seen as a lattice analogue of the one-more-RSA assumption by Bellare et al. [JoC'03]. To gain confidence in our assumption, we provide a detailed analysis of diverse attack strategies.

Transport Layer Security (TLS) is the backbone of the web, allowing clients to establish secure and private channels with servers. DECO (CCS'20) and follow-up works proposed protocols that enable proving the provenance of a TLS response, i.e., that a payload came from a particular server, without needing server-side modifications. Unfortunately, these works are limited to proving Boolean statements over the payload (e.g., age $\ge$ 18) and cannot combine payloads from multiple clients. We introduce TLShare, a framework that extracts authenticated data from a TLS connection and imports it into secure multiparty computation (MPC) or fully homomorphic encryption (FHE), without requiring server-side changes or exposing client credentials. Unlike prior work, TLShare allows the payload itself, not just a predicate about it, to serve as private input to secure downstream computation. TLShare supports combining verifiable inputs across multiple clients and servers, enabling new applications such as privacy-preserving financial risk assessment and collaborative analytics. We design three protocols for TLShare: one for MPC using verifiable secret sharing, and two for FHE using interactive and non-interactive zero-knowledge proofs, each ensuring input authenticity, integrity, and end-to-end privacy. We evaluate all three protocols of TLShare over both LAN and WAN settings, comparing their trade-offs and demonstrating their practicality.

The CKKS fully homomorphic encryption scheme enables efficient encrypted computation over complex-valued data. In many real-world cases, however, the computation only involves real data, and storing them inside complex slots wastes the encoding ability. This motivated the design of conjugate-invariant CKKS (CI-CKKS) instantiated over the conjugate-invariant ring (CIR), which provides the same number of real slots while halving the RLWE dimension. Despite its better efficiency in handling real data, CI-CKKS cannot be bootstrapped directly in CIR, since the CoeffToSlot and SlotToCoeff linear transformations used in bootstrapping require storing complex values in both plaintexts and ciphertexts. Existing methods bootstrap CI-CKKS ciphertexts via conversion to standard CKKS, perform bootstrapping there, and convert back. For example, Lattigo bootstraps two CI-CKKS ciphertexts by combining them into a CKKS ciphertext with doubled ring dimension, while Bae et al. convert a single CI-CKKS ciphertext to a CKKS ciphertext in the same dimension. The former is efficient only for batched inputs and suffers from limited flexibility, while the latter consumes additional layers in packing. Another issue with CI-CKKS is that many existing functional bootstrapping methods encode intermediate values using complex roots of unity, whereas CI-CKKS provides only real-valued slots. Our first contribution is a real FFT algorithm over the conjugate-invariant ring, thereby enabling native bootstrapping in CI-CKKS. Our second contribution investigates functional bootstrapping over CI-CKKS. We adapt the real-valued AKP interpolant with radial correction and develop a single-cosine Hermite interpolation method using a single real ciphertext. We show existing complex-valued interpolation methods can be implemented using two real ciphertexts to simulate complex arithmetic. We also study the numerical behavior of real-valued interpolation and evaluate the tradeoffs between computational efficiency and precision. We implement our methods in Lattigo. Our native CI-CKKS bootstrapping achieves a $1.14$--$12.86\times$ speedup in single-ciphertext bootstrapping across different baseline methods and total linear transformation depths. Compared with state-of-the-art functional bootstrapping methods over standard CKKS, our methods achieve $1.16$--$1.68\times$ higher throughput.

We present hardware implementations of the recently proposed isochronous fixed-weight sampling algorithm by Décio Luiz Gazzoni Filho, Tomás S. R. Silva, Julio López (CiC vol. 1, 2024) and apply them to the post-quantum cryptographic algorithms NTRU-HPS, Streamlined NTRU Prime and Classic McEliece. We offer multiple implementations, optimized for different targets: A high-area high-performance implementation, a lightweight low-area implementation, as well as a side-channel secure implementation using gadget-based masking. We verify the security of our masked implementation using the PROLEAD leakage detection tool. We show that the sampling algorithm results in highly efficient and effective implementations for the NTRU-like schemes, outperforming existing hardware implementations for fixed-weight sampling.

The Algebraic Group Model (AGM) is widely used to prove the security of cryptographic schemes involving groups and pairings. It requires adversaries to explain how their output group elements are obtained from the elements they have received. The AGM with Oblivious Sampling (AGMOS), introduced by Lipmaa, Parisella, and Siim (TCC 2023), additionally allows adversaries to sample group elements without learning their discrete logarithms. This models capabilities such as hashing to a group, but complicates security proofs: security in the AGM does not always imply security in the AGMOS. We give a framework for transferring AGM security proofs to the AGMOS for a broad class of pairing-based security games. Our results separate the existing AGM argument from the additional reasoning needed to handle obliviously sampled elements. Under the Find Polynomial Representation (FPR) and Tensor Oracle Find Representation (TOFR) assumptions, this additional reasoning can be handled by general reductions. Games with further requirements, such as extractability, also require a lifting condition that ensures these requirements are preserved. We first establish a lifting theorem for non-interactive games and apply it to KZG extractability, the multivariate Adaptive Rational Strong Diffie-Hellman assumption, and the special-soundness of the Polymath SNARK. We then extend the framework to interactive games that use random oracles and other oracles that depend on the trapdoor. In the interactive setting, we apply the theorem to the existential unforgeability of BLS signatures and strong unforgeability of BBS signatures under FPR/PDL and TOFR assumptions. For BLS, we also provide an AGM security proof for Type-3 pairings, adapting the original Type-1 analysis. Our framework allows existing AGM proofs to be reused in the AGMOS. To apply the framework, it is enough to check its requirements, including oracle simulation and, where needed, the lifting condition, without repeating the full security proof.

Recent MPC-in-the-Head (MPCitH) signatures increasingly rely on aggressive GGM-tree optimizations to reduce signature size and computational cost, culminating in __secret-key-root correlated GGM trees__ as used in SBC (Huth and Joux, CRYPTO 2024), MQOM (NIST PQC Standardization for Additional Signature Round-2, 2024), and rBN++ (Kim, Lee, and Son, EUROCRYPT 2025). While this technique yields substantial compression, it introduces a dependency loop in the proof (Kosuge and Xagawa, CiC 2026(3)). We analyze MQOM and resolve this circularity by providing EUF-CMA security proofs for a slightly modified variant. The modifications consist of incorporating a salt into the input of a hash function and modifying the evaluation domain to ensure that all evaluation points are nonzero. For the resulting variant of MQOM, we prove EUF-CMA security for the GF(2) parameter sets in the random-oracle plus ideal-cipher model, assuming EUF-NMA security, standard one-wayness, and a heuristic conjecture on matrices. Our proof combines the H-coefficient technique with one-wayness, which may be of independent interest. We also prove EUF-CMA security in the (quantum) random-oracle model, where block-cipher-based hash functions are modeled as random oracles. The proof relies on EUF-NMA security and partial-guessing one-wayness (Feneuil and Rivain, ASIACRYPT 2026), which can be reduced classically to partial-domain one-wayness.

The hint framework of Dachman-Soled, Ducas, Gong, and Rossi (CRYPTO 2020), together with the later too-many-hints analyses from May and Nowakowski (ASIACRYPT 2023) and Cao, Jiang, and Cheng (CRYPTO 2025), gives a classification of secret-dependent hints and LLL-breaking hint thresholds for LWE schemes. These values are now frequently adopted as the default benchmark for side-channel security evaluation. We show that applying them as a security metric is problematic. DDGR categorizes hints based only on their local algebraic form, while the threshold analyses assume uniformly sampled hint vectors. Neither captures how the specific algebraic form of a hint governs the geometry of the resulting sparsified lattice. A hint’s class label and the corresponding uniform threshold therefore cannot, on their own, capture its real cryptanalytic power. We illustrate this mismatch with two forms of structured leakage that naturally appear in ring and module lattice implementations, validated via synthetic experiments on Kyber-512. NTT-domain residues qualify formally as mod-$q$ hints, yet they recover the full Kyber-512 secret with roughly half as many hints as the uniform mod-$q$ bound predicts. Finite-precision FFT samples fall into the weaker approximate-hint class, and still only need $25\%$--$55\%$ of the hint budget required for uniform perfect hints. The gap stems from algebraic structure: these hint families carry additional ring structure that enables tailored lattice recovery strategies, a distinction invisible under the uniform-sampling model. We do not propose new attack optimizations. Our findings indicate that DDGR hint classes and too-many-hints thresholds are syntactic descriptions, not standalone security metrics for real leakage traces. Evaluating a side-channel leak requires considering the algebraic structure of the hint vectors, not just their category and quantity.

P vs NP problem is the most important unresolved problem in the field of computational complexity. Its impact has penetrated into all aspects of algorithm design, especially in the field of cryptography. The security of cryptographic algorithms based on short keys depends on whether P is equal to NP. In fact, the security requirements for cryptographic keys are much stricter than those for P$\neq$NP, the security of the key must ensure not only a sufficiently high computational complexity to crack it, but also consider the security of each bit of the key, while fully avoiding the effectiveness of various attack methods. In this paper, we innovatively propose a new encoding mechanism and develop a novel block symmetric encryption algorithm, which be named Eagle, whose encryption and decryption can be completed in linear time. The key consists of 10 variables, for the attacker, in the case when only the plaintext-ciphertext correspondence is known, the problem of cracking the key is equivalent to solving a system of equations about ten unknown variables $(w_{1}, w_{2}, ..., w_{9}, w_{10})$ together with some implicit variables which are generated by the encryption process. In this paper, we will prove that there is no universal algorithm without brute-force searching at least one variable during the process of verifying four variables $(w_{1}, w_{2}, w_{3}, w_{4})$ whose computational complexity is not greater than solving the ten variables. After performing elimination the implicit variables, the problem of verifying the four variables will be equivalently transformed into a series of general quintic equations about one variable $w_{9} \oplus w_{10}$ with coefficient given by other four variables $(w_{5}, w_{6}, w_{7}, w_{8})$, according to the conclusion that ``there is no algebraic solution to quintic equations", we can't establish a system of algebraic equations only containing the other four variables $(w_{5}, w_{6}, w_{7}, w_{8})$. Without solving the other four variables, the problem of verifying the four variables $(w_{1}, w_{2}, w_{3}, w_{4})$ is equivalent to solve the slope and intercept of a line given the x-coordinates or y-coordinates of several points on it (points with x-coordinates known cannot have their y-coordinates known, and vice versa), this implies that there is no universal algorithm without brute-force searching at least one variable to verify the four variables $(w_{1}, w_{2}, w_{3}, w_{4})$. Since the computational complexity of brute-force searching any single variable is exponential, thus the complexity of cracking the key is exponential. Thus decryption is a one-way function, and according to ``the existence of one-way function means P$\neq$NP", solving the unsolved problem of P vs NP. In addition, this paper delves into the underlying mathematical laws of this new encoding mechanism, and develops a right multiplication operation to binary. Based on this right multiplication operation, we further constructed a nonlinear operation and designed another block symmetric encryption algorithm, which be named $Eagle^{*}$. The key of $Eagle^{*}$ is composed of three independent variables. Given any plaintext ciphertext correspondences, the problem of verifying any two variables in the key is equivalent to solving a system of quintic equations. Based on the conclusion that there is no algebraic solution to quintic equations, we assert that there is no fast algorithm to verify any two variables, and thus the computational complexity of cracking the key is equal to the computational complexity of completely exhausting the three variables. In addition, we conducted an in-depth analysis that without cracking the key, it is not possible to directly decrypt new ciphertext by simply collecting a large number of ciphertext plaintext correspondences. Due to the fact that ciphertext consists of two parts, one part is completely random, while the other small part is calculated using plaintexts, keys, and random numbers, and their distribution is also completely random, thus $Eagle^{*}$ is resistant to all forms of linear and differential attacks.

In e-voting, a mix-net is a widely used system for shuffling votes in order to guarantee voter privacy. The core principle is as follows: (1) N voters cast their votes; (2) a sequence of mix-servers shuffles the N encrypted ballots, thereby randomly permuting the underlying votes; and (3) trustees jointly decrypt the shuffled ballots to compute the tally. This approach, however, relies heavily on trusted parties after the voting phase and raises serious robustness issues. For example, what happens if the mix-servers disrupt the protocol, or if trustees lose the decryption key during the tallying phase? A recent incident in the IACR board election illustrates this problem: one of the three trustees involuntarily lost their key, requiring the entire community to restart the vote. We introduce OMIX, an offline-mixing architecture for self-tallying elections: trustees prepare public functional decryption keys embedding a hidden random permutation before voting, voters then cast encrypted ballots, and anyone can compute the shuffled tally without further trustee participation. Function-hiding inner-product functional encryption supplies the key mechanism, and a voter-assisted correction phase accommodates dropouts. The main technical component is a verifiable offline shuffle of a matrix of encrypted functional keys. We extend linearly homomorphic signatures with tag-binding and two-dimensional tags: row tags support hidden row permutations, while column tags bind entries to their respective voters. In the certified-input model, these properties allow trustees to certify matrix transformations, with final proof size and verification cost independent of the number of mix-servers. Together, these components enable distributed preparation and public certification of permutation keys within a client-lightweight voting architecture. Each voter registers and casts a ballot with computation and communication independent of N, while preprocessing per trustee, public helper-key size, and tallying work are quadratic. This establishes a foundation for self-tallying elections with offline mixing and opens the way to further improvements in system-wide efficiency.

The constant-time programming policy is a de facto standard for cryptographic libraries to prevent timing side-channel attacks. However, compiler optimizations may break constant-time source code during compilation. Systematically preventing this requires understanding where a violation arises, how it is introduced, and which compiler configurations are problematic. Existing approaches analyze a single compilation point, either the final binary or one intermediate representation, and thus only partially answer the three questions. We propose CTGREP, a compiler-based framework that answers all three questions by applying differential analysis across the entire compilation chain. We use CTGREP to analyze seven complete cryptographic libraries across three Clang versions, six target platforms, and thousands of compiler configurations. We systematically detect compiler-induced constant-time violations in the wild and collaborate with library developers to address 48 cases. We further identify seven new problematic LLVM passes, bypass and improve the state-of-the-art compiler-flag-based mitigation. Finally, we quantify how the compiler version, target platform, and optimization configuration affect the violations. By covering entire libraries across the full compilation chain, CTGREP effectively detects remaining compiler-induced constant-time violations and complements the community's ongoing hardening efforts.

The contribution vector (convec) of a secret-sharing scheme is the vector of its normalized share sizes. The average and maximum coordinates of a convec give, respectively, the average and maximum information ratios of the scheme. Obtaining superlinear lower bounds on these quantities for unrestricted perfect secret sharing has remained a challenging open problem for about four decades. In this paper, we study substitution, a natural way to build complicated access structures from simpler ones: one participant of an outer access structure is replaced by an inner access structure. Given secret-sharing schemes for the two factors, the standard forward construction composes them into a scheme for the composite access structure. We study the converse question. Given an arbitrary scheme for the composite access structure, we ask to what extent its convec admits a reverse factorization into convecs for the outer and inner factors, up to a common multiplicative loss. Exact reversal is false: we give a counterexample whose optimal reverse factor is \(8/9\), with a composite scheme that is scalar-linear over every finite field. On the positive side, we prove that a factor \(1/2\) is always attainable, and that every fixed instance admits a strictly larger factor. For a recursive family built from Csirmaz’s classical access structure \(\mathcal C_k\), whose distinguished set has size \(k\), we identify a critical reverse factor that determines when the resulting lower bound becomes superlinear. This critical factor exceeds one half by only an amount of order \((\log k)/k\). Crossing it yields superlinear lower bounds, while any fixed positive excess above one half gives a route to superpolynomial lower bounds. Using only Shannon inequalities, the corresponding recursive factor cannot cross the critical value. Thus any improvement sufficient to pass this threshold must exploit constraints beyond the Shannon inequalities.

Kushilevitz, Lindell, and Rabin (STOC `06, SIAM Journal on Computing `10), in their seminal result, showed that any standalone-secure synchronous multiparty computation (MPC) protocol can be compiled into one secure under concurrent general composition, by adding a synchronisation step after every round; thereby, at least doubling the round complexity. We show that for protocols that are secure against super-rushing adversaries, introduced by Asharov, Chandramouli, Cohen, and Ishai (EuroCrypt `25), two synchronisation rounds suffice. Specifically, for an $R$-round protocol that is secure against super-rushing adversaries with a black-box, straight-line simulator, adding a round of start synchronisation (saying ``HELLO'') and a round of end synchronisation (saying ``GOODBYE'') yields security under concurrent general composition with selective abort in $R+2$ rounds. If the end synchronisation is over a broadcast channel, the security is upgraded to unanimous abort. Both compilers incur no loss in the security reduction and preserve the flavour of security (perfect, statistical, or computational) of the underlying synchronous protocol. Moreover, combining with the sufficient conditions of Asharov et al. for perfect security, and the round-preserving super-rushing compilers of Ciampi, Ravi, and Zou (Cryptology ePrint Archive 2026/1745) for statistical and computational security, yields compilers from rushing security to security under concurrent general composition, with an additive overhead of at most $2$ rounds. We further extend our compilers to protocols with a trusted setup, such as a common reference string or a public-key infrastructure, which is necessary in the dishonest majority setting. We require two conditions. First, every execution of the protocol uses its own stateless copy of the setup, whose responses to the adversary do not depend on the interactions of the honest parties. In particular, this rules out setups that are shared across executions, such as a global common reference string or a single public-key infrastructure used by every execution. Second, the underlying protocol is secure against super-rushing adversaries with adaptive inputs, that is, even when the inputs are chosen after interacting with the setup. Under these conditions, the same compilers yield security under concurrent general composition. We also show that adaptive inputs cannot be relaxed to the usual notion of security in the setup-hybrid model. Specifically, we give a protocol that is statistically secure against super-rushing adversaries with guaranteed output delivery under the standard hybrid model, but is insecure under concurrent general composition after adding start and end synchronisation, even with selective abort.

Robust combiners are a standard way to hedge cryptographic assumptions: given several candidate constructions, they produce one construction that remains secure as long as one candidate is secure. In favorable cases, such combiners also yield universal constructions. We ask whether this paradigm applies to cryptographic primitives whose public outputs must be both pseudorandom and sparse. Our first result gives a negative answer for pseudorandom codes (PRCs), i.e., error-correcting codes whose codewords are computationally indistinguishable from uniform strings. We prove that secret-key PRCs admit no black-box robust combiner. The impossibility holds even for the weakest meaningful guarantee, where the combined scheme is required to be secure when all but one candidate PRC are secure. We then show that the obstruction is not specific to error correction. In the sparse ciphertext regime, public-key encryption with pseudorandom ciphertexts also admits no black-box robust combiner. This stands in contrast to ordinary IND-CPA encryption, for which robust combiners are easy to obtain. Thus the requirement that public outputs look uniformly random introduces a genuine barrier to black-box assumption hedging, and rules out the standard combiner route to universal constructions for these primitives.

We present a security analysis of the messaging service known as LINE, a popular platform used daily by millions of users in East and Southeast Asia – most notably Japan, Taiwan, Thailand, and Indonesia. More specifically, we focus on its underlying custom end-to-end encryption (E2EE) protocol, known as Letter Sealing v2. Our findings show that Letter Sealing allows a TLS Machine-in-the- Middle attacker or malicious server to violate integrity, authenticity, and confidentiality of communications. The stateless design of the protocol allows message replay, reordering, and blocking attacks without the user being notified. The lack of origin authentication facilitates impersonation attacks, in which the authorship of mes- sages in one-to-one or group chats can be forged by malicious users colluding with the adversary. Lastly, stickers and URL previews present a notable leakage of plaintext, which leads to a violation of confidentiality. To verify the correctness of our findings, we mounted a Machine-in-the-Middle attack on an iOS device, yielding the device’s outgoing traffic and the corresponding server responses. Utilizing this setup, we experimentally verified our attacks against the authentic LINE application and an independent implementation. We discuss our findings in comparison to the state-of-the-art E2EE protocols, and conclude that Letter Sealing does not satisfy the requirements expected from a modern E2EE messaging protocol.

Digital identity systems are being deployed worldwide to enable secure, privacy-preserving authentication. In this regards, Europe's EUDI Wallet mandates selective attribute disclosure and unlinkable authentication, effectively requiring anonymous credentials. Yet current proposed solutions omit them because they lack device binding: tying a credential to a secure hardware element on the user's device to prevent cloning or sharing. Device binding encodes a device public key in the credential and, at presentation time, produces a fresh signature under the hardware-protected secret key -- a proof-of-possession (PoP). While academic solutions for device binding exist, they require pairing-friendly curves, whereas consumer phones are restricted to ECDSA over P-256. In this work, we bridge this gap by enabling device binding of pairing-based credentials using the device's standard ECDSA signature as the PoP. To explore the efficiency–complexity trade-off of such solution, we present three constructions. Our most efficient solution generates unlinkable binding proofs of size ~1.5kB in under ~400ms using a simple arithmetic circuit, whereas the most conservative circuit-free approach matches this proving time at ~122kB. All solutions follow a common blueprint expressed in the reductions of knowledge framework (Crypto 2023), which enables modular composition of zero-knowledge proofs and eases both security analysis and implementation. This framework has previously been mainly used in a theoretical context, and our work demonstrates that it is a powerful tool to design, analyze and implement advanced real-world systems.

We review the Bulletproofs++ construction which replaces the bit-decomposition inner-product argument of Bulletproofs with a reciprocal set-membership argument over base-$16$ digits. We present a self-contained specification of the $64$-bit range proof as well as a general batched variant parametric in the batch size $M$ and bit width $b$ and prove honest-verifier zero-knowledge and exact-form knowledge soundness. We describe the evaluation and optimizations of our Rust implementation over Ristretto255, which proves up to $7.8\times$ and verifies up to $4.5\times$ faster than regular Bulletproofs. Finally, we correct two formulas of the original paper: the affine $T^3$ term of the scalar polynomial $p_s(T)$ carries a factor of $2$, and the slot-$0$ component of the blinding vector $r_S$ carries the opposite sign.

ZMAC+ is a tweakable-block-cipher-based MAC proposed by List and Nandi in ToSC 2017 with claimed beyond-birthday-bound security. We show that a tag-swap mechanism previously observed for a hypothetical two-output extension of DoveMAC also applies to the published ZMAC+ construction. For two-block tags, we give a distinguisher with constant advantage and a fresh-message forgery with constant success probability using $O(2^{n/2})$ queries in the ideal-TBC model, where $n$ is the block length. An internal collision between two message families exchanges their tag blocks; a common extension preserves this relation and leads to a forgery with one additional authentication query. We identify a counting error in the published Lemma~4 and prove a corrected aggregate differential bound. The resulting PRF and MAC upper bounds match the birthday query threshold for bounded message lengths and two-block tags, under explicit field-order conditions. The distinguisher extends to every legal fixed output length $d\ge2$, and the forgery to every legal even $d$. We also retain ZHash and separate the output domains. Under stated field-order, length, and domain-capacity conditions, this modification admits an adaptive PRF bound of order $q^2/2^{n+\min(n,t)}$ for bounded lengths. Finally, a one-query counterexample shows that the ZAE security theorem must retain the per-message length restriction required by its counter-in-tweak encryption component.

Provers for succinct non-interactive arguments of knowledge (SNARKs) perform arithmetic over a large field for soundness, even when the witness entries are a few bits wide, which inflates both prover time and memory usage. Recent work makes individual SNARK components bitwidth-aware, so that a lower witness bitwidth means faster proving and lower memory usage, but these techniques cover only part of the prover and exploit the structure of specific fields, typically binary ones. We introduce Mikros, a framework for end-to-end bitwidth-aware SNARK construction based on algebraic vector packing. We pack vectors of length \(N=m\kappa\) over a base field \(\mathbb{F}\) into length-\(m\) vectors over a degree-\(\kappa\) extension field \(\mathbb{E}\), which turns length-\(N\) relations over \(\mathbb{F}\) into length-\(m\) relations over \(\mathbb{E}\) and makes existing linear-time extension-field protocols bitwidth-aware. This technique thus unifies bitwidth-aware inner-product proofs, Hadamard-product proofs, and polynomial commitment schemes, previously obtained by separate constructions, and yields the first bitwidth-aware grand-product proof, hence the first bitwidth-aware permutation argument. Composing them gives bitwidth-aware SNARKs for circuit satisfiability over extensions of arbitrary small fields. For a single instance of circuit satisfiability, the prover cost is proportional to the effective bitwidth, the combined bitwidth of the witness entries and the wiring-position encodings; across instances of the same circuit, the position encoding is amortized and the per-instance cost is proportional to the witness bitwidth. Although Mikros does not rely on binary-field structure, its prover is \(2.19\times\), \(2.55\times\), and \(1.85\times\) faster on batches of \(256\) SHA-256 compressions, Keccak permutations, and BLAKE3 compressions than Flock (B\"unz \etal, IACR ePrint 2026), the state-of-the-art bitwidth-aware SNARK over binary-extension fields.

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 < log2 p quadratic constraints) discharges the separability hypothesis at gadget scale. Conversely, when the rank computation itself certifies a smooth witness (full row rank, or full rank after vacuous guard rows are discharged by explicit local-redundancy identities), effective Lang-Weil bounds convert infinitesimal freedom into at least p/(2·deg C) distinct finite-field values of the target among genuine satisfying assignments, so in that regime the local diagnostic becomes a sound non-uniqueness certificate. For quadratic constraints, an additional affine-line certificate converts a tangent vector into p explicit satisfying assignments whenever every quadratic directional coefficient vanishes; its checker uses sparse field evaluations and needs no smoothness assumption. A second-order parabola variant extends the construction to curved families through one further linear solve 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.

Despite ensuring both consistency and liveness, state machine replication (SMR) protocols remain vulnerable to adversaries that manipulate transaction order, causing, e.g., MEV attacks. To mitigate this, researchers have proposed new variants augmented with order-fairness. However, existing protocols that employ dependency graphs, such as Aequitas (Crypto 2020), Themis (CCS 2023), and SpeedyFair (NDSS 2024), often suffer from suboptimal performance, limited resilience, or weakened security guarantees. Pompē (OSDI 2020) introduced a novel ordering notion called ordering linearizability (OL) that may circumvent those drawbacks. However, its guarantee holds only under favorable network conditions, making the protocol vulnerable to order fairness violations during network delays and susceptible to performance degradation in the presence of Byzantine faults. Also, implementing SMR under OL remains an open challenge in asynchronous settings, as no known protocol achieves this without sacrificing liveness of SMR. In this paper, we present $\mathsf{Isotaxis}$, a state machine replication with ordering linearizability; moreover, our protocol has communication complexity $\mathcal{O}(n\ell+\lambda n^2)$, where $n$ is the number of processes, $\ell$ is the input (transaction) size, and $\lambda$ is the security parameter. This is optimal when $\ell\geq \lambda n$, while previous works have cubic communication. To the best of our knowledge, $\mathsf{Isotaxis}$ is the first protocol to achieve ordering linearizability in the asynchronous setting, especially one with optimal communication complexity and optimal Byzantine resilience. We implemented $\mathsf{Isotaxis}$ and conducted extensive experiments using up to 100 EC2 c6a.2xlarge instances. The experimental results show that our protocol robustly outperforms Pompē across all system scales, ranging from 4 to 100 nodes.

NAT is widely assumed to conceal the private IP addresses of internal clients from both off-path attackers within the same LAN and external observers. We show that this assumption does not hold. We present a novel off-path private IP address inference attack against NATed clients engaged in active TCP connections with a remote server. Our attack exploits known NAT behaviors in real-world routers, such as port preservation, insufficient reverse-path validation, and the absence of TCP window tracking, previously shown to enable off-path TCP hijacking. By inferring a NATed client’s private IP address, our attack defeats the address-hiding property commonly attributed to NAT, creating a privacy leak that can lead to deanonymization and user profiling. We validate the attack on 6 NAT routers and 2 real-world Wi-Fi networks on SSH and HTTP/HTTPS traffic, finding that 5 of the 6 routers and both networks are vulnerable.

It is well known that Byzantine agreement requires $\Omega(t^2)$ messages against a strongly adaptive adversary that may corrupt $t=\Theta(n)$ parties and suppress a party's undelivered messages upon corruption. We circumvent this lower bound by relaxing termination: for any constant $0<\nu<1$, at least a $(1-\nu)$ fraction of the honest parties terminate, while agreement and validity hold for every honest decision. For every constant corruption gap $\delta>0$ and every $t\leq(1-\delta)n/3$, we construct binary agreement with this guarantee in authenticated asynchronous networks against strongly adaptive corruptions with message takebacks. Except with negligible probability, these guarantees hold and every honest decision carries a transferable justifier. The protocol achieves almost-everywhere termination in expected $O(1)$ rounds, expected total communication $O(n\kappa^2)$ bits, and expected maximum communication $\widetilde O(\kappa^2)$ bits over honest parties before corruption, where $\kappa$ is the computational security parameter. Our construction combines a recursively shared BLS signing key with certificate dissemination over a sparse graph. The recursive sharing is used to implement threshold signing with distinct safety and liveness thresholds. Dissemination propagates existing certificates to almost all honest parties. The construction uses a trusted setup and is secure in the random oracle model under the algebraic one-more computational Diffie--Hellman assumption. We further obtain full binary agreement with the same asymptotic communication and round complexity against adaptive corruptions without message takebacks. The extension requires neither atomic multi-send nor private communication channels.

Public certificates of semiprimality could support cryptographic modulus generation by proving that an integer has exactly two prime factors without revealing them. Their usefulness in this setting depends on whether the certificate preserves the difficulty of factoring. Motivated by the examples of Reble and Broadhurst, we formalize semiprimality certificates by adapting the Goldwasser-Kilian primality criterion. For certificates with a prime point order, our semiprimality theorem uses public data $(N,S,E,P)$ comprising a composite nonsquare integer $N$, an elliptic curve $E$ over $\mathbb{Z}/N\mathbb{Z}$, a certified prime $S>(N^{1/6}+1)^2$, and a point $P\in E(\mathbb{Z}/N\mathbb{Z})$ of order $S$ modulo every prime divisor of $N$. Hasse's bound forces each prime divisor above $N^{1/3}$, proving that $N$ has exactly two prime factors. For such semiprimality certificates constructed using complex multiplication (CM), we show that a norm-lattice reconstruction factors $N$ from $(N,S,D)$ alone in expected polynomial time when the Frobenius at every prime divisor lies in a known imaginary quadratic field of fundamental discriminant $D$ or has trace zero, and $\gcd(S,2DN)=1$. Applying this reconstruction and complementary public-point and quadratic-twist attacks, we factor Reble's 1084-digit and Broadhurst's 5061-digit moduli. These attacks also defeat proposed repairs based on hidden cofactors, withheld CM maps, or private isogeny descent within a known field under the stated hypotheses. We leave open whether one can efficiently produce a public Goldwasser-Kilian-based certificate for a fixed modulus, using its privately known factors, while preserving its factoring difficulty relative to the General Number Field Sieve.

We study amortization of prover work in the multi-verifier setting, motivated by proof-as-a-service deployments in which a shared prover serves $K$ independent clients holding distinct statements. Each verifier checks only its own statement and proof, with no inter-verifier communication. The challenge is therefore to amortize prover work across many proofs while preserving local verification. We consider polynomial relations arising naturally in IOP-based proof systems, where verification reduces to polynomial identities and polynomial openings at verifier-chosen random points. Existing amortization techniques rely on shared verifier randomness, for example, to batch openings at a common evaluation point. However, under the standard Fiat--Shamir transform, independently verifiable proofs derive challenges from separate transcripts, preventing such amortization. We address this obstacle through a multi-verifier Fiat--Shamir transform that correlates verifier challenges across independently verifiable proofs while preserving locality. We further introduce promise local folding schemes, which defer polynomial-constraint checks generated during folding and amortize them later. Together, these techniques provide a generic framework for amortization under local verification. We apply this framework to the witness-independent component arising in R1CS- and CCS-based SNARK provers, which reduces to bivariate polynomial evaluation claims over the public constraint matrices. This component accounts for a substantial portion of the concrete proving cost. Applying our techniques to these claims reduces the server's cryptographic cost for this component from $O(K\cdot s)$ to $O(K\log K+s)$ group operations, where $s$ denotes the sparsity of the public constraint matrices, with each verifier performing only $O(\log K)$ cryptographic work and requiring no inter-verifier communication. Because the amortized component depends only on the public circuit description, our framework composes cleanly with collaborative zk-SNARK protocols, which target the complementary witness-dependent component.

Evolving secret sharing allows participants to join indefinitely without modifying previously distributed shares. We study the share size of perfectly secure evolving threshold secret sharing schemes and obtain two improvements. For general thresholds, we introduce a polynomial sharing method that shares two secrets with adjacent reconstruction thresholds using one polynomial. Combining this method with the evolving scheme of Cheng et al.\ (ASIACRYPT 2025), we obtain an evolving $k$-threshold scheme whose $t$-th share has size \[ \left\lfloor \frac{k}{2} \right\rfloor \log_2 t + O_k\!\left(\ell+\log_2\log_2 t\right) \] bits for an $\ell$-bit secret. This reduces the leading coefficient of their general construction from $k-1$ to $\lfloor k/2\rfloor$. For threshold three, we give a separate construction that reduces the lower-order terms of the scheme of Cheng et al. We mask the short shares in all generations with the same random $\ell$-bit value $R$, which is shared through an evolving $2$-threshold scheme, we obtain \[ \log_2 t+(2+o(1))\log_2\log_2 t \] bits per share for fixed $\ell$. Both constructions satisfy correctness and perfect information-theoretic security.

With the rapid advances in quantum computer architectures and the emerging prospect of large-scale quantum memory, it is becoming essential to classically verify that remote devices genuinely allocate the promised quantum memory with a specified number of qubits. In this paper, we introduce a new concept, proofs of quantum memory (PoQM). A PoQM is an interactive protocol between a classical probabilistic polynomial-time (PPT) verifier and a quantum polynomial-time (QPT) prover over a classical channel where the verifier can verify that the prover has possessed a quantum memory with a specified number of qubits for a specified period of time. PoQM generalize the well-studied notion of proofs of quantumness (PoQ) [Brakerski, Christiano, Mahadev, Vazirani, and Vidick, JACM 2021] where a classical verifier can verify that the prover is not classical. Our contributions are summarized as follows: We introduce a formal definition of PoQM. We also introduce a variant of PoQM, which we call inefficient-verifier PoQM (IV-PoQM), where the verifier's final computation to make the decision is not necessarily efficient. Clearly, PoQM imply IV-PoQM. We construct PoQM based on the hardness of LWE. Specifically, we give two constructions of PoQM. The first one is of two-round (i.e., four-message) and has negligible soundness error under the subexponential-hardness of LWE. The second one is of polynomial-round and has inverse-polynomial soundness error under the polynomial-hardness of LWE. As a lowerbound of IV-PoQM (and therefore PoQM), we show that IV-PoQM imply one-way puzzles. Moreover, we show that a certain restricted version of PoQM implies quantum computation classical communication (QCCC) key exchange, which suggests the difficulty of black-box constructing PoQM from one-way functions. We show that constant-round PoQ imply PoQM or single-round PoQ (with a quantum verifier). Single-round PoQ are ``trivial'' PoQ in the sense that the verifier asks the prover to solve a classical problem which is quantumly easy but classically hard. The result therefore demonstrates that PoQM capture ``genuinely-interactive'' PoQ. We show that if constant-round IV-PoQ that are black-box constructed from quantumly-secure falsifiable assumptions exist then IV-PoQM exist. This result implies that IV-PoQM can be constructed from quantumly-secure constant-round statistically-hiding commitments (and therefore from quantumly-secure collision-resistant hash functions).

One of the most successful applications of peer-to-peer communication networks is in the context of blockchain protocols, which—in Satoshi Nakamoto's own words—rely on the "nature of information being easy to spread and hard to stifle." Significant efforts were invested in the last decade into analyzing the security of these protocols, and invariably the security arguments known for longest-chain Nakamoto-style consensus use an idealization of this tenet. Unfortunately, the real-world implementations of peer-to-peer gossip-style networks used by blockchain protocols rely on a number of ad-hoc attack mitigation strategies that leave a glaring gap between the idealized communication layer assumed in formal security arguments for blockchains and the real world, where a wide array of attacks have been showcased. In this work we bridge this gap by presenting a Byzantine-resilient network layer for blockchain protocols. For the first time we quantify the problem of network-layer attacks in the context of blockchain security models, and we develop a design that thwarts resource restricted adversaries. Importantly, we focus on the proof-of-stake setting due to its vulnerability to Denial-of-Service (DoS) attacks stemming from the well-known deficiency (compared to the proof-of-work setting) known as nothing at stake. We present a Byzantine-resilient gossip protocol, and we analyze it in the Universal Composition framework. In order to prove security, we show novel results on expander properties of random graphs. Importantly, our gossip protocol can be based on any given bilateral functionality that determines a desired interaction between two "adjacent" peers in the networking layer and demonstrates how it is possible to use application-layer information to make the networking-layer resilient to attacks. Despite the seeming circularity, we demonstrate how to prove the security of a Nakamoto-style longest-chain protocol given our gossip networking functionality, and hence, we demonstrate constructively how it is possible to obtain provable security across protocol layers, given only bare-bone point-to-point networking, majority of honest stake, and a verifiable random function.

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\%\).

The question of obtaining a constant-additive approximation for bin packing was highlighted in the third of ten open problems in Williamson and Shmoys' The Design of Approximation Algorithms [SW11, Chapter~17, Problem~3]. We prove that there is an absolute constant $c>0$ such that, unless $\mathrm P=\mathrm{NP}$, no deterministic polynomial-time packing using at most $\mathrm{OPT}+c\log^*\mathrm{OPT}$ bins, where $\mathrm{OPT}$ is the minimum number of bins. In particular, no such algorithm has additive error $o(\log^*\mathrm{OPT})$. The best known upper bound, due to Hoberg and Rothvoss [HR17], is $\mathrm{OPT}+O(\log\mathrm{OPT})$, achieved by a randomized algorithm with expected polynomial running time. OpenAI [Ope26] previously showed that, unless $\mathrm P=\mathrm{NP}$, no deterministic polynomial-time algorithm guarantees a packing using at most $\mathrm{OPT}+O(1)$ bins. We conjecture that the optimal additive approximation error for bin packing is $\Theta(\log \mathrm{OPT})$.

During the last decade, single-trace side-channel attacks on cryptographic implementations have largely focused on profiled methods, which typically assume that the attacker has a clone device and implementation knowledge to build a leakage model for the target before launching the attack. In this paper, we demonstrate that a much weaker adversary, without the ability to profile, can also mount powerful single-trace attacks. The presented method compares the observed sample distribution with the expected Hamming weight leakage distribution using a Gaussian mixture model as a distinguisher. The horizontal nature of the attack allows us to obtain multiple observations per execution by partitioning and stacking the trace. We show how to select optimal parameters for trace preprocessing and configure the measurement setup so that the noise floor is lowered, enabling the exploitation of weak leakage. We also prove that imperfect classifications can be efficiently corrected using information-set decoding algorithms. The new method is evaluated on an optimized implementation of ML-DSA-65 on ARM Cortex-M4 using the secret key unpacking procedure as an attack point. With an enumeration budget of $2^{70}$ operations in $\mathbb Z_q$, the full secret key is recovered from a single trace in 99% of attacks.

Verifpal is a symbolic protocol analyzer introduced in 2019 to make formal analysis accessible during protocol design. It provides a small modeling language, built-in cryptographic primitives, and attack reports that use the model's names. This paper describes the analysis engine of Verifpal 1.6.7. A backward solver proposes attacker actions, which an executor checks by running all sessions and peer configurations together. An injected value is delivered only when the attacker can derive it from information already available in that execution. A separate query evaluator, or judge, records the result. We define the model, its five query predicates, and a reference semantics, and prove that every judged execution is a history of that semantics. Executions terminate; search termination is conditional on the solver calls terminating. Evaluation covers 885 secrecy queries across 189 configurations of the fifteen fundamental Noise patterns, varying static-key compromise and protocol checks. At one and two sessions, a separate executor reproduces every reported disclosure, and ProVerif proves all 290 passing counterparts for unbounded sessions. The protocol computations also match 90 external cryptographic test-vector messages. These results support the implementation on the tested models; a Verifpal pass remains the outcome of bounded, incomplete search.

We present a plaintext-recovery attack on both the DBDH-based construction and the CBDH-based variant of Datta, Komargodski, and Waters (Journal of Cryptology, 2023). The attack succeeds with probability one in the claimed static security model using one corrupt authority and two users, each unauthorized even when granted the corrupt authority's attribute. The flaw is an invalid extension of the LSSS matrix-normalization lemma originating with Rouselakis and Waters (FC,~2015): preserving complete-share distributions does not preserve coordinate-wise ciphertext masks, which a corrupt authority can expose to remove identity binding from other users' shares. For both variants, replacing these masks with independent full linear sharings of zero preserves correctness and restores ciphertext-distribution invariance. We prove static security of both repaired variants in the random oracle model under their respective BDH assumptions, using the original hardcore-bit convention for the CBDH variant. Both proofs allow adaptive identity-hash queries. The modification retains the original matrix-width and row-labeling restrictions, keys, decryption, and ciphertext size, requiring only additional encryption randomness and finite-field arithmetic. We also attack both multi-authority attribute-based inner-product functional encryption constructions of Datta and Pal (PKC, 2023) and establish correctness and matrix-substitution invariance of the same repair. We prove static security of the repaired small-universe construction under asymmetric DBDH. For the large-universe construction, we identify a missing source-group encoding in the original reduction and give a complete static security proof under an augmented $L$-DBDH assumption, whose generic bilinear group hardness we establish.

The signature schemes MQOM, SNOVA, MAYO, and UOV are third-round candidates in the NIST standardization process for additional post-quantum signatures, and their security relies on the hardness of the multivariate quadratic (MQ) problem. XL with block Wiedemann (BW) is one of the most efficient MQ solvers in practice, but its memory demand has led to a debate about its memory access cost: generating the rows of the Macaulay matrix on the fly is widely believed to save memory at a non-negligible computational cost. In this work, we evaluate the memory--time trade-off in practice. We provide the first efficient on-the-fly implementation of XL with BW. We build on the state-of-the-art implementation by Cheng, Chou, Niederhagen, and Yang (CCNY), which uses SSE instructions and supports the fields $\mathbb{F}_2$, $\mathbb{F}_{16}$ and $\mathbb{F}_{31}$; we remove its column-index tables and generate the rows on the fly in the first phase of BW (BW1). We amortize the cost of on-the-fly generation with a new algorithm that computes column indices with $O(n^2)$ instead of $O(n^3)$ table look-ups, where $n$ is the number of variables. In our experiments we observe that our on-the-fly implementation achieves running times comparable to CCNY's with up to five times less memory. We also port both implementations to AVX2 over $\mathbb{F}_{256}$, the main field of UOV, and observe a similar behavior: comparable BW1 running times with less memory for the on-the-fly variant.

Miner extractable value (MEV) in automated market makers allows block builders to profit from transaction ordering and injected trades, imposing costs on users and contributing to builder centralization. We introduce Otter (Optimal Truthful Trading with Excess Redistribution), a two-asset batch AMM that achieves provable MEV resilience when the consensus layer provides censorship resilience and block space is uncongested. In particular, Otter makes truthful behavior a dominant strategy for both users and builders. Consequently, a builder cannot profit from strategic deviations, including reordering bids or injecting sybil bids. These guarantees continue to hold even when the builder is itself a trader with intrinsic value. Moreover, we show that our mechanism maximizes social welfare, in a strong sense, within a natural class of mechanisms satisfying the desired game-theoretic properties. To achieve these guarantees, we introduce a new paradigm called surplus redistribution, which provably prevents residual surplus from being captured as MEV by redirecting it to the broader community. Specifically, the pool's output tokens need not be distributed entirely among the users in the current batch. Instead, any residual surplus may be transferred, for example, to a smart contract governed by the decentralized community. The accumulated surplus can subsequently be used to benefit community members in ways that preserve the mechanism's game-theoretic guarantees --- for example, by subsidizing traders' transaction fees, rewarding liquidity providers, or returning assets to the pool to reduce price impact and slippage for future traders. Our approach relies on the underlying consensus layer to provide censorship resilience. We motivate the necessity of this assumption through an impossibility result showing that the desired game-theoretic guarantees become unattainable when the builder is additionally allowed to censor transactions. Thus, our results also provide a mathematically formal demonstration of how consensus-level security guarantees can fundamentally expand what is achievable at the application (i.e., smart-contract) layer. Finally, we establish additional results characterizing the builder fee structures compatible with our desired incentive guarantees.

Recent superlattice algorithms have improved the provable complexity of lattice problems. Ducas, Engelberts, and Loyer used this framework to obtain a subexponential algorithm for infinity-norm short integer solution, while also identifying a key obstacle to extending it to learning with errors (LWE). A similar difficulty arose in the analysis of Kirchner and Fouque, whose claimed subexponential running time with only linearly many LWE samples was not rigorously established. Building on the framework of Ducas, Engelberts, and Loyer, we develop two refinements based on rejection sampling that solve this open problem. First, we use rejection sampling to cancel the shift-dependent normalization factor that arises when sampling from a shifted, scaled integer lattice. This factor is a product of one-dimensional Gaussian masses and can be evaluated efficiently. This yields a provably subexponential classical search-LWE algorithm for prime $q\in[n^2,2n^2]$ and constant Gaussian error width. It uses only $m=4n$ independent samples and runs in time and space $\exp(O(n/\ln\ln n))$. Second, we use random auxiliary superlattices and apply rejection sampling to the difference of two Gaussian lattice samples, ensuring that the accepted output follows the desired discrete Gaussian distribution up to a small statistical error. For $q=n^{\kappa+o(1)}$, $m=n+h=O(n)$, and $R=h\ln q/[m\ln(2+\sigma)]\to\infty$, the resulting algorithm uses time and space $2^{(1/2+o(1))n/\ln R}$, where $\sigma$ is the Gaussian error width. In particular, for $\sigma=n^{o(1)}$ and any fixed $m/n>1$, our algorithm achieves provable subexponential classical running time, whereas the primal and dual baselines have exponential-time bounds and earlier provable subexponential BKW analyses require $\Omega(n\ln n)$ samples.

Private information retrieval (PIR) hides which database item a client requests. We study PIR that also identifies servers that respond incorrectly. Against a coalition of at most $t$ corrupted servers, the client must retrieve the item and identify every deviating server when at most $d$ deviate. Above that threshold, it must abort and return an empty identification set, with a specified statistical error. We present SynTrace, a single-round compiler for linear PIR supporting audit queries whose honest answers belong to a public code. The client combines the retrieval query with $m$ audit queries using secret linear mixing and independent blinding. Audit syndromes identify deviations before reconstruction. We prove perfect query privacy, zero false-identification probability within the deviation threshold, and statistical realization of an accountable PIR functionality. For Shamir-based PIR, SynTrace uses $k=t+d+1$ servers. Under the stated privacy and download assumptions, tolerating $d$ missing responses already requires this many servers, so identification adds no server overhead. With this number of servers, $m=d$ audit queries suffice with a suitable field, and are necessary within the specified syndrome-span decoder class. Additional audit queries can reduce communication by allowing a smaller field. For one 32 KiB record from a 1 GiB database, with five servers, privacy and robustness against two corrupted servers, and error at most $2^{-40}$, SynTrace uses 2.25 MiB of communication, compared with 8.96 MiB for the homomorphic-MAC construction of Eriguchi, Kurosawa and Nuida (TCC 2022) under the same workload and thresholds. Batched retrievals can share the audit queries.

We present GordieHowe, a system comprising a language, a certifying compiler, and a zero-knowledge proof protocol. GordieHowe is especially suitable for building anonymous credentials on top of standardized signature schemes like ECDSA, RSA, and ML-DSA. GordieHowe is the first system to achieve the following three properties simultaneously: provable security against quantum attackers, efficiency for statements spanning multiple fields—including proving and verifying in parallel—and automatic batching of structured computations. GordieHowe is high-assurance by design. The language is designed to enable static checking of bounds safety, preventing integer overflows. Its compiler emits a Lean certificate that its optimization decisions are semantics-preserving for the input program. The proof system's security theorems are machine-checked in Lean. GordieHowe is faster and has smaller proofs than comparable prior work. It proves, in parallel on four cores, an ECDSA-signed mobile driving license presentation in 64.8 ms with a 276 KiB proof, 10.1× faster and 22% smaller than Google's Longfellow. With at least 101 bits of knowledge soundness in the random oracle model, GordieHowe proves knowledge of a 1 KiB SHA3-256 preimage in 5.0 ms with a 60 KiB proof, and of an RSA-2048 signature on a private 2 KiB message in 25.9 ms with a 210 KiB proof. With at least 116 bits against quantum adversaries, GordieHowe proves knowledge of an ML-DSA-44 signature on a private message in 87.3 ms with a 549 KiB proof, 70.2× faster and 29% smaller than an optimized Longfellow circuit. In building GordieHowe we make a number of contributions of independent interest. We define a new notion of an interactive oracle proof (IOP) whose messages are partially ordered, which we call a series-parallel IOP. We extend the BCS transformation to series-parallel IOPs, and give knowledge soundness and ZK proofs in the QROM. We also show our BCS extension satisfies a form of simulation extractability in the QROM; we believe this is the first simulation extractability result of any kind for BCS in the QROM.

Du et al. (Security and Communication Networks, 2022) proposed a public-key authenticated searchable encryption scheme that employs Bloom filters and blockchain. In their scheme, Bloom filters are used to search encrypted keywords, while blockchain is used to guarantee the correctness of search results. In this paper, we demonstrate that Du et al.'s scheme leaks keyword information from ciphertexts. Our analysis focuses on the fact that the Bloom filter embedded in a ciphertext is uniquely determined by the Diffie-Hallman key and the keyword to be encrypted and is directly included in the ciphertext. We show that the success probability of the proposed attack is lower bounded by the probability that no false positives occur in the Bloom filter, and we evaluate this probability to confirm that the attack achieves a sufficiently high success rate. Furthermore, we examine Du et al.'s security model and their assumed usage scenarios, and discuss the validity of our attack under those conditions. We also consider a simple modification intended to prevent our attack and demonstrate that a slightly adapted version of the attack remains effective against the modified scheme. In addition, we show that previously generated ciphertexts can still pass verification even when the search results differ, indicating that the blockchain-based integrity verification mechanism is insufficient.

An asymmetric Password-Authenticated Key Exchange (aPAKE) protocol allows a client, who holds a raw password, and a server, who holds a one-way mapping of the password, to jointly establish a cryptographically strong session key, without an authenticated channel. The standard security definition for aPAKE is in the Universal Composability (UC) framework. Despite its great potential of being used in practice, existing aPAKE protocols are either not round-optimal, computationally inefficient, or not proven secure. In this work, we present two aPAKE protocols that are 1 simultaneous round, UC-secure, have reasonable computational costs, and rely on mild cryptographic assumptions. Our first protocol is in the Random Oracle Model and the Algebraic Group Model (ROM+AGM), secure under the CDH assumption, and has computational cost comparable to the most efficient aPAKE protocols in the literature (1 simultaneous round or not). Our second protocol is in the ROM only and secure under the DDH assumption, and also has significantly lower computational cost than the only other UC-secure 1 simultaneous round aPAKE protocol. Interestingly, even our second protocol does not rely on the gap Diffie-Hellman assumption, which requires creative application of the forking lemma.

In EUROCRYPT 1999, Gennaro, Jarecki, Krawczyk, and Rabin (GJKR) showed that in the well-known Pedersen robust Distributed Key Generation (DKG) protocol for the Discrete Logarithm (DL), an adversary can bias the distribution of the resulting public key. To address this issue, they proposed a fully secure, statistically unbiased variant of the Pedersen DKG protocol. The GJKR protocol achieves robustness and guarantees a statistically uniform final public key, at the cost of $O(n^2)$ exponentiations per party, where $n$ denotes the number of parties. In this paper, we revisit fully secure robust DKG protocols for the DL setting and propose three more efficient alternatives, each using $O(n)$ exponentiations per party in the happy path while offering different trade-offs in security, efficiency, and round complexity. Our first protocol, like the GJKR scheme, guarantees that the final public key is indistinguishable from a uniformly random group element even to a computationally unbounded distinguisher. The second protocol is concretely more efficient and ensures that the public key distribution is computationally indistinguishable from uniform. In our third construction, we focus on minimizing the worst-case number of rounds in the second protocol and present a variant using three rounds in the happy path and one additional reconstruction round in the unhappy path. Our third scheme can be viewed as a fully secure and round-reduced variant of the biased construction by Atapoor et al. (ASIACRYPT 2023). In comparison with the most recent low-round fully secure DKG protocols by Katz (CRYPTO 2024), Cascudo-David (EUROCRYPT 2024), Kate et al. (CCS 2024), and Boneh et al. (EUROCRYPT 2025)--all of which achieve three rounds via two online rounds and one preprocessing round (or vice versa)--our third DKG protocol requires only $O(n)$ exponentiations per party in the happy path, as opposed to at least $O(n^2)$.

Known-Covariance Ring-LWE (KCov-RLWE) was introduced by Micciancio and Suhl to support simulation-secure threshold encryption. It strengthens ordinary Ring-LWE by revealing an exact quadratic summary of the hidden secret and errors, and its decisional hardness was left open. We give explicit polynomial-time decision attacks for broad families of prime moduli at ring rank one. Our key observation is that the public sample and the covariance hint together determine a bordered Gram matrix whose determinant exposes a hidden residual with a different distribution for genuine and uniform samples. After reducing the ring into finite-field components, this residual has one of two forms: a product across reciprocal components, or a Hermitian norm when a component is preserved by conjugation. The latter case yields a particularly strong distinguishing signal. Moreover, reduction modulo any divisor preserves the KCov real and random experiments exactly, so every attackable odd prime divisor of a composite modulus transfers the corresponding distinguisher with no loss of advantage. The attack covers the one-sample setting globally in the self-reciprocal regime and, under the coefficient-product Gaussian specialization, locally in the completely split regime. More generally, we obtain a complete classification of how this residual-based attack behaves for odd prime moduli when $m\ge2$, and extend these guarantees to arbitrary moduli possessing a suitable odd prime divisor. The classification does not imply insecurity for every parameter family: when the relevant residue fields are sufficiently large, the guaranteed distinguishing advantage in the reciprocal case can become negligible, and pure power-of-two moduli remain outside the divisor-reduction extension. Accordingly, our results invalidate the KCov pseudorandomness assumption in the quantified families; they do not show that every parameter choice permitted by the motivating Ring-PKE sketch is insecure, nor do they give a direct IND-CPA break of the complete threshold-encryption construction.

In classical cryptography, one-way functions are necessary for most of cryptography. In the quantum world, however, Kretschmer at TQC'21 and subsequent works have demonstrated that quantum versions of various primitives in minicrypt, such as signatures and private-key encryption, do not require quantum-computable one-way functions (qOWFs). However, the question of the necessity of qOWFs for primitives in Cryptomania like public-key encryption with classical public-keys and ciphertexts (qPKE) has remained open. We provide a comprehensive picture of the relationship between qPKE and qOWF. First, our main result is a black-box separation between qOWFs and qPKE. In particular, we show that relative to a unitary, real, and self-inverse oracle, there exists a qPKE scheme (with classical keys and ciphertexts), but qOWFs do not exist. Further, our oracles admit a point-function obfuscation construction, thus ruling out black-box construction of qOWF from point function obfuscations. On the positive side, we construct qPKE from quantum indistinguishability obfuscation for quantum circuits with classical obfuscated descriptions and efficiently verifiable one-way puzzles, which is known to be a potentially weaker assumption than qOWFs, due to an existing black-box separation. Our construction is the quantum analog of the classical construction of PKE from one-way functions and indistinguishability obfuscation in the quantum computation with classical communication (QCCC) setting.

Fix a prime power q . We prove that deciding whether a received word y ∈ F^n_qm lies at rank distance at most n − 2 from the one-dimensional Gabidulin code {λg : λ in Fqm } is NP-complete. Thus maximum-likelihood decoding of Gabidulin codes is NP-hard even for k = 1, an analogue of the Guruswami-Vardy theorem for Reed-Solomon codes. In the Hamming metric, by contrast, hardness at this radius requires the dimension to grow with the length, as in the Guruswami Vardy theorem. The reduction is deterministic; consequently Rank Syndrome Decoding (RSD) and Rank Minimum Distance (RMD) for Fqm -linear codes are NP-complete under deterministic polynomial reductions, whereas the previously known reduction was randomized. The proof goes through a pivot problem that we introduce, Twisted Square Membership (TSM): given Fq -subspaces U, W in FqN , decide whether some non-zero a ∈ U satisfies a^(q+1) in W . Quadratic systems in d unknowns are encoded into TSM, then TSM into Gabidulin decoding. The last step views the received word as an Fq -linear map and decoding at radius n − 2 as the search for an Fq -plane on which it acts as a scalar. With support U + τ W in a cubic extension and map a + τ b → a^(q^2) + τ b^q , two Frobenius twists force solution planes to encode the relation a^(q+1) ∈ W . All constructions are explicit and polynomial, with N = O(qd^2 ), n ≤ N + d, and m = 3N .

We study whether a quantum verifier can find a hidden quantum state by exchanging classical messages with an unbounded prover who knows the state. The verifier has access to a reflection oracle about the target. For a Haar-random $n$-qubit target, we prove that achieving constant average fidelity with the target requires $(q+1)^2(B+1)=\Omega(2^n)$, where $q$ is the number of verifier queries and $B$ is the total prover-to-verifier communication. The bound allows arbitrary classical interaction and unrestricted computation between queries. Our proof extends the lower bound of Aaronson and Kuperberg (ToC'07) from a single classical proof to an arbitrary classical interaction. As a result, we obtain a quantum-oracle separation of QMA from QCIP. In particular, we give a unitary oracle $\mathcal{U}$ such that there exists a language $L\in\mathrm{QMA}^{\mathcal{U}}$ but $L\notin\mathrm{QCIP}^{\mathcal{U}}$. Our separation holds even for UniqueQMA, the restriction of QMA to verification with a unique quantum witness, which is known to be strictly weaker than QMA in the quantum black-box setting. We further give an oracle construction for a notion known as QMA--QCIP[2] gap problem. This gives average case hardness for a QMA language under classical access to a QCIP[2] decision oracle and is used in establishing negative results on witness encryption and quantum indistinguishability obfuscation.

Secure multiparty computation (MPC) allows distrusted parties to jointly evaluate a common function while keeping their inputs private. In this work, we focus on improving the communication complexity of information-theoretic asynchronous MPC with optimal resilience ($t < n/3$). The current state-of-the-art work in this setting by Goyal, Liu-Zhang, and Song [Crypto’24] achieves amortized linear communication per gate with $\Omega(n^{14})$ elements additive overhead. In comparison, the best-known result in the synchronous setting by Goyal, Song, and Zhu [Crypto’20] achieves the amortized linear communication per gate with only $\mathcal{O}(n^{6})$ elements additive overhead, revealing a significant gap that we aim to close. This work closes this gap and goes further. We present the first statistically secure asynchronous MPC protocol achieving amortized linear communication per gate with only $\mathcal{O}(n^{5})$ elements additive overhead assuming a functionality for Agreement on Common Set (ACS). With the best-known instantiation for ACS, we obtain an asynchronous MPC protocol in the plain model with additive overhead $\mathcal{O}((\kappa+n)n^4\log\kappa)$ elements in expectation, where $\kappa$ is the security parameter. In the setting of statistical security with optimal resilience, this even surpasses the best synchronous result when $n\geq\sqrt{\kappa\log\kappa}$. Technically, our contributions include (i) a new protocol for generating Beaver triples with linear communication per triple and $\mathcal{O}(n^3)$ elements additive overhead assuming functionalities for generating random degree-$t$ Shamir sharings and ACS, and (ii) a new protocol for generating random degree-$t$ Shamir sharings with linear communication per sharing and $\mathcal{O}(n^{5})$ elements additive overhead assuming a functionality for ACS.

Fully homomorphic encryption schemes enable arbitrary computation on encrypted data. Although the first candidate were considered too computationally inefficient, modern cryptosystems are now featured in practical deployments. Yet, despite a plethora of advances, many non-polynomial operations remain computationally challenging. In this work, we investigate radix decomposition, i.e., the homomorphic conversion of an LWE ciphertext with a large plaintext message into encryptions of its digits. Such decompositions are a core building block for large-precision computation in FHEW/TFHE-like schemes, for instance for sign evaluation, comparisons, and large lookup tables. To this end, we introduce phase decomposition: decomposing the coefficients of an LWE ciphertext itself in a radix $\alpha$ yields small pseudo-LWE samples whose phases recombine linearly to the phase of the original ciphertext. For keys of bounded Hamming weight, these phases are small and can be made non-negative, and the base-$\alpha$ digits of the original phase follow from them through a simple carry recurrence. We evaluate this recurrence entirely in the exponent of an RLWE accumulator, using a new exact homomorphic truncation in the exponent based on automorphisms. The resulting digit decomposition requires a single blind rotation per digit, asymptotically half as many as the state of the art, introduces no modulus-switching error between iterations, and supports input moduli larger than the ring modulus. The same tools yield functional bootstrapping over the full ring $\mathbb{Z}_{2N}$, the evaluation of arbitrary, not necessarily negacyclic, functions on small plaintext spaces, and a scheme-independent digit decomposition for SIMD schemes based on parallel-prefix addition.

NIST is revising SP~800-38F, which specifies the AES Key Wrap modes KW and KWP. This paper is an updated and expanded version of our technical comments to NIST. We show that the forgery probabilities stated in SP~800-38F do not account for adaptive attacks, give the resulting forgery probabilities for KW, KWP, and TKW, and show that checking the expected plaintext length can raise the security level of KWP considerably. Revisiting Kelsey's long-message observation, we correct the collision conditions, show that a successful forgery leaks a plaintext prefix, derive an encryption-only distinguisher, and conclude that KW does not have beyond-birthday-bound security. We explain the role of the step counter, analyse the single-semiblock path of KWP and the trade-off between the number of passes and the length limit, and give recommendations for the revision, for implementations, and for future key-wrap designs.

We present a multi-target second-preimage attack on the message hashing of the stateful hash-based signature schemes HSS/LMS and XMSS with SHA-256 and with the truncated SHA-256/192. The attack builds on the herding technique of Kelsey and Kohno: the attacker takes the chaining states that follow the per-signature prefixes of many collected signatures and merges them, level by level through state collisions, into a single chaining state. From that state one search serves all collected signatures at once, which defeats the commitment to the key and to the one-time-signature leaf index at the start of the hash input that is meant to rule out multi-target attacks. The search can match the final digests, which is the better choice against SHA-256/192, or, after appending a Kelsey-Schneier expandable message, the internal chaining states of long signed messages, which is effective for full SHA-256. For SHA-256 with NIST's bound of $2^{64}$ signatures, which may be spread over any number of keys, the cost in compression-function calls falls from the nominal $2^{256}$ to about $2^{166}$ for messages of up to 4 GiB and to about $2^{156}$ in the formal limit of maximal message length, a loss of 100 bits. For SHA-256/192, digest matching costs about $2^{153}$ for $2^{64}$ signatures of any length, a loss of 39 bits. Because the attack pools signatures across keys, even the first signature of an individual key contributes to a potential overall exposure of an ecosystem. The attacks exploit the chaining state of SHA-256, which is narrower than twice the targeted security level; the SHAKE256 parameter sets are not affected.

With Q-day approaching, the transition to post-quantum cryptography (PQC) has begun, with governments across the US, UK and EU mandating migration to quantum-resistant standards. This paper benchmarks the three NIST-standardised PQC algorithms—FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA)—across key generation, signing and verification operations, measuring both computational performance and energy consumption on a range of constrained IoT-class devices, from the 32-bit Raspberry Pi 1 and Zero to the 64-bit Raspberry Pi 4, as well as commodity laptop hardware. Using the FNIRSI FNB58 USB power meter and OpenSSL 3.5, results show that ML-KEM and ML-DSA achieve energy and speed efficiency comparable to classical elliptic-curve cryptography across all tested architectures. However, SLH-DSA signing is inadvisable on constrained hardware: energy costs for SLH-DSA signing on 32-bit devices were up to 243% higher than on equivalent 64-bit hardware, making it impractical for resource-limited IoT deployments. These findings have direct implications for IoT security practitioners planning PQC migration.

The closest vector problem(CVP)and the nearest codeword problem (NCP) are fundamental computational problems with connections to learning, coding theory, and cryptography. We study hardness of approximation in the preprocessing model: an algorithm receives the lattice or code in advance, may perform unrestricted computation to produce polynomial-size advice, and must then solve the problem on any target in polynomial time. Unless $\mathsf{NP} \subseteq \mathsf{P/poly}$, no such algorithm achieves an approximation factor of $\bullet$ $M^{1−\varepsilon}$ for NCP over any fixed finite field, or $\bullet$ $M^{1/\min\{p,2\}−\varepsilon}$ for CVP in any $\ell_p$ norm, for every fixed $\varepsilon > 0$, where $M$ denotes the code block length or lattice dimension, respectively. We improve the subpolynomial factors of Khot, Popat, and Vishnoi [KPV14]to polynomial ones, matching the exponents that Song [Son26] proved without preprocessing for binary codes and the $\ell_2$ norm. We further extend Song’s evaluation tables to every fixed prime characteristic and the lattice reduction to $\ell_p$ with $p > 2$. Our main technical contribution is an extension of the moment method, introduced in an OpenAI report [Ope26] and improved by Song [Son26], to the preprocessing setting. In addition, we give a direct reduction from probabilistically checkable proofs (PCPs) whose query locations and families of possible predicates do not depend on the formula. The resulting factor of $M^{\Omega(1/(\log \log M)^2)}$ is already larger than that of [KPV14], and the reduction may be of independent interest.

Integral cryptanalysis analyzes block ciphers using input structures for which the sum of a chosen function of the output bits becomes key-independent. However, most methods still test one output expression at a time, so they can miss distinguishers that emerge when several outputs are combined, either linearly or nonlinearly. They are also not designed to capture key-dependent integral combinations, which may hold deterministically on part of the key space. In this work, we develop Split-and-Cancel, a method that combines exact expansion in a short final part with an oracle on the preceding rounds to determine which suffix monomials can survive from the chosen structure and records them in a binary matrix. Key-independent combinations are then extracted from the left kernel of this matrix. We first apply the method in a reduced model with omitted boundary key additions, where linear dependencies in this matrix yield certified sum combinations independent of keys among output bits and higher-degree output products. When the omitted round key in the combination is restored, the same combinations yield deterministic weak-key distinguishers. In connection with the weak-key distinguishers, we further investigate their probabilistic behaviour and show that the probability-estimation formula used in Zhang et al.’s EUROCRYPT 2026 work is invalid. The found flaw is supported by our experiments. We apply the method to SIMON, SIMECK, SPECK, PRESENT, and GIFT. Our strongest deterministic results improve the best integral distinguishers for SIMON, SIMECK, and SPECK by one round at every standard block size. For PRESENT and GIFT, we improve deterministic weak-key integral distinguishers by one round. In each case, the exact weak-key class covers at least a quarter of the key space: $2^{78}$ of $2^{80}$ keys for PRESENT-80, $2^{126}$ of $2^{128}$ keys for PRESENT-128, GIFT-64 and GIFT-128. These results show that exact modeling of a short final part can reveal key-independent and weak-key integral behavior missed by analysis using single observables.

HAETAE has shorter public keys and signatures than ML-DSA, but the signing stack of its reference implementation reaches $158\, \mathrm{KiB}$ on Cortex-M4. The Low-Stack HAETAE implementation presented at CHES'26 brings the signing stack down to $5.7$-$5.9\,\mathrm{KiB}$; yet even HAETAE-2 still needs $8,718\,\mathrm{B}$ in a realistic IoT scenario, where the secret key and the signature buffer share the same SRAM. Gaussian regeneration further increases signing time by up to a factor 2.6 relative to the C reference. Although HAETAE's modulus $q = 64\,513$ fits in 16 bits, signing and verification also need values modulo $2q$, so existing implementations keep 32-bit working polynomials. We store them in 16 bits and lift each coefficient to modulo $2q$ in a register only when it is consumed, and let objects with disjoint lifetimes share buffers, which lowers peak stack usage without any additional Gaussian regeneration. Exact Gaussian replay and caching method then record the acceptance decisions and partial CDT ranks of the first generation in the unused space of the signature buffer, so that the original samples are restored from the same random stream with less recomputation. For Cortex-M4, Cortex-M3, MSP430, and AVR, we further design NTT modular multiplication and butterflies that preserve 16-bit storage, and optimize the arithmetic of the FFT and the Gaussian sampler. We validate our implementation on $8\,\mathrm{KiB}$ hardware: a single C firmware image on the ATmega2560 runs HAETAE-2 key generation, signing with the generated key, and verification, and uses a total of $8,070\,\mathrm{B}$ of SRAM, including the secret key, the signature buffer, static data, and the stack. To the best of our knowledge, this is the first standardization-track PQC-DSA implementation that signs within $8\,\mathrm{KiB}$ of total SRAM on physical hardware. Compared with Low-Stack HAETAE on Cortex-M4, Cortex-M3, MSP430, and AVR, our implementation reduces stack usage by up to 34% and runs key generation and signing 1.18-2.51$\times$ faster wherever Low-Stack can run them.

As a privacy-preserving distributed learning paradigm, federated learning faces severe security threats, especially data poisoning, gradient tampering, distributed attacks, and adaptive attacks. Existing gradient-based detection methods encounter three major bottlenecks in practical applications. First, they cannot distinguish between benign and malicious gradients under distributed attacks in non-IID scenarios. Second, defenders lack prior knowledge of trigger patterns. Third, attackers can launch adaptive attacks against these defense mechanisms. To address these challenges, we propose a novel defense paradigm. This paradigm shifts away from gradient detection, instead leveraging zero-knowledge proofs to conduct sample-level inspections on the local datasets of clients, eliminating the defense degradation caused by distributed attacks under non-IID settings. Then, through a staking mechanism, attackers are forced to train on discovered malicious samples with flipped labels, generating counter-gradients to neutralize hidden malicious samples, achieving targeted backdoor removal without requiring any prior knowledge of backdoor features. Furthermore, through zero-knowledge proof commitments, training gradients must be generated based on the same locked data. This prevents dynamic adaptive attacks based on reference model parameters and precludes gradient tampering. Experimental results demonstrate that under the highly non-IID setting of $\text{Dir}(0.1)$, our proposed scheme successfully defends against distributed backdoor attacks and edge-case attacks on CIFAR-10, suppressing the attack success rate to below $6\%$. To the best of our knowledge, this is the first framework to achieve such defense results.

This paper responds to the cryptanalysis presented in “Key Recovery from Residue- Confined Errors in the Pradhan CRT-RLWE Construction” (Olejnik and Naskrecki, 2026), which claims key recovery and plaintext recovery against the CRT-FHE scheme introduced in “A New CRT-based Fully Homomorphic Encryption” (Pradhan et al., 2026). We demonstrate that the reported recovery attacks rely entirely on a deliberately con- structed error distribution whose support lies in the kernel of the CRT encoding function. Consequently, the effective encryption error is identically zero, reducing the attacked con- struction to a noiseless RLWE instance. The subsequent key-recovery and plaintext-recovery results therefore follow from the deliberate elimination of the encryption noise, rather than from any cryptanalytic method capable of recovering secrets from properly noise-bearing CRT-FHE ciphertexts. Crucially, the proposed attack neither removes nor estimates errors from normally generated CRT-FHE ciphertexts. Instead, it assumes an artificial error distribution specifically chosen to guarantee their annihilation during encoding. This condition does not hold for the intended centered-binomial error distribution, under which the probability that an entire error polynomial belongs to the encoder’s kernel is negligible at the reported parameters. Thus, the presented recovery procedures do not constitute attacks against the concrete CRT-FHE instantiation with its intended non-degenerate error distribution. We conclude that the reported key-recovery and plaintext-recovery results concern a deliberately degenerate, effectively zero-error instantiation and do not demonstrate a practical security compromise of CRT-FHE under its intended error sampling.

Authenticated garbling (Wang et al., CCS'17) is the leading framework for achieving constant-round maliciously secure 2PC, achieving total communication comparable to protocols in the semi-honest setting. In the semi-honest setting, the one-hot garbling scheme of Heath and Kolesnikov (CCS'21) supports tensor gates $\vec x \otimes \vec y$, for $\vec x \in \{0,1\}^n$ and $\vec y \in \{0,1\}^m$, in $O(n+m)\kappa$ bits, versus $O(nm)\kappa$ for an AND-gate-based garbling. Extending this improvement to the malicious setting has remained open. We present two authenticated garbling protocols that efficiently handle tensor gates. Our first protocol minimizes garbled circuit size, matching the size of semi-honest one-hot garbling; all additional overhead is confined to preprocessing. We also design a custom preprocessing protocol for efficiently generating random authenticated tensor triples, proved secure assuming only a circular correlation robust hash function and base OTs. Our second protocol minimizes total communication via compressed (PCG-style) preprocessing. We construct an authenticated variant of one-hot garbling where the additional overhead in garbled-circuit size as compared to the semi-honest garbling scales with tensor-gate input length rather than output length. As in the semi-honest case, tensor gates are restricted to inputs of length $O(\log \kappa)$ and arbitrary-length tensor products are handled by tiling multiple short input gates. This yields an $O(\log \kappa)$ factor reduction in communication for general tensor products compared to previous state-of-the-art authenticated garbling protocols, with concrete improvements in communication and runtime for practical workloads such as integer and matrix multiplication within an authenticated garbled circuit.

Garbling schemes are powerful primitives that enable secure computation between a mutually untrusting garbler and evaluator. A projective garbling scheme is one that encodes the evaluator's input in a simple bit-by-bit manner. Projective schemes, such as the seminal scheme of Yao, are versatile, as they are naturally compatible with other simple tools, such as $1$-out-of-$2$ oblivious transfer (OT). There exist garbling schemes that naturally operate over large finite fields, some of which require only efficient information-theoretic (IT) techniques. However, here the evaluator's input is encoded via an affine function over a large field, so these schemes are not naturally projective, reducing their versatility. We provide a transformation that efficiently projectivizes such schemes. Consider an arithmetic garbling scheme where the evaluator's input consists of elements from a large prime field. Our symmetric-key-based garbling techniques give a mechanism to translate from Yao-style garbled labels to IT-style garbled labels at cost proportional to the input and output labels: crossing the border is duty-free! We apply our technique to two problems. (1) Recent works show that projective garbling schemes solve a problem central to trust-minimized bridges for the Bitcoin blockchain. BABE (Garg et al., 2026) and Argo MAC (Eagen and Lai, 2026) give two different approaches. Both works implicitly construct an efficient IT garbling scheme, then use naive bit-decomposition to achieve projectivity. We construct and implement drop-in replacements for both; we improve BABE's encoding size by $51\times$, and Argo MAC's by $23\times$. (2) Our technique implies a non-interactive reduction from vector oblivious linear evaluations (VOLEs) over $\mathbb{F}_p$ to $1$-out-of-$2$ OTs. To our knowledge, ours is the state-of-the-art Minicrypt (plus base OTs) protocol for large field VOLE secure against a malicious receiver. It costs only $O((\lambda + n) \lg p)$ bits.

Crites and Stewart reduce an adaptive forgery attack on threshold Schnorr signatures with $N$ parties and threshold $\tau$ to one call to a sparse linear search oracle, which they show to be bounded distance decoding of a diagonally scaled Reed–Solomon code and whose sparse answer, a witness, names the parties to corrupt. Their analysis samples the coefficient vector behind the adversary's commitment uniformly at random and leaves open whether a chosen vector does better. We bound the success of an adversary that follows their template with a chosen vector and recovers witnesses only inside regions built from the radii that seven decoding theorems, three for Reed–Solomon and four for folded Reed–Solomon codes, certify under their own setup hypotheses. When the commitment is fixed through a known coefficient vector before a fresh hash challenge, the attack target is, conditional on the history that fixed the vector, a uniform point of a line. For distinct nonzero Shamir points, our main theorem shows that every such line contains at most $M$ targets with a witness in a finite collection of coordinate and block weight regions fixed before the targets, each permitting fewer than $\tau$ nonzero coordinates, for an explicit integer $M$ depending only on $N$, $\tau$ and the collection. We call the adversary the wrapper when it makes at most $Q$ fresh challenges and no signing query, chooses each coefficient vector from its history before the challenge and keeps it afterwards, and lets its solvers make no further signature hash queries. It accepts only a witness of the same target and representation that lies in the regions of the collection within its corruption cap, corrupts parties only once it holds such a witness, and then forges from that witness and stops. Hence the wrapper succeeds with probability at most $QM/p$, with $p$ the group order, even if its solvers recover every witness in the regions at no cost. On the six pairs $(N,\tau)$ of the original attack, fixed collections built from partitions into consecutive blocks contain all seven certified regions and have $M$ below $2^{24}$, so at the field size proxy $p = 2^{252}$ the bound stays below $2^{-100}$ after $2^{128}$ challenges. For uniform targets we prove much smaller bounds on the witness probability in these regions. For the folded Guruswami–Wang and Ashvinkumar–Habib–Srivastava block regions on partitions into consecutive blocks fixed before the target, this probability is negligible for polynomially many parties, exponentially large fields and $\tau/N$ bounded away from zero. These results also classify the studied decoder theorems. The hardness of the oracle, the success of other strategies and the adaptive security of threshold Schnorr schemes are open.

All traditional encryption schemes share a fundamental operational vulnerability: encrypted data must be decrypted before it can be used. Fully homomorphic encryption eliminates this vulnerability by enabling computation directly on encrypted data, but existing FHE schemes impose substantial practical constraints that limit deployment. This paper presents a formal security analysis of the Gribov-Kahrobaei-Shpilrain (GKS) private-key FHE scheme. GKS requires no bootstrapping or de-linearization, produces bit-exact decryption, supports native encrypted search, and scales to unbounded depth.

We investigate non-malleable Incrementally Verifiable Computation (IVC), a subject that has received limited attention. We focus on whether and how simulation-sound IVC can be obtained from falsifiable assumptions. We provide additional evidence of the unique aspects of non-malleable incremental proofs, identifying definitional challenges in formalizing simulation-sound IVC, and showing how existing IVC designs from falsifiable assumptions cannot exhibit simulation-soundness "for free" (without modifications). In addition to a new family of definitions of simulation-sound IVC, our main results are the following. - A general negative result: common Valiant-style proofs are malleable. We isolate and formalize a feature shared by the dominant Valiant-style IVC designs (Valiant, TCC 2008) related to the ability to merge proofs together. We show that, assuming one-way functions, natural zero-knowledge versions of Valiant's design are malleable. As an implication of our framework of attacks, we show that the only IVC for NP from falsifiable assumptions (Datta et al., CRYPTO 2025) cannot satisfy any form of simulation-soundness; this is the case even when instantiating this scheme from non-malleable building blocks. - A positive result: first IVC from falsifiable assumptions with non-malleability features. We construct an IVC satisfying a non-trivial form of simulation-soundness under subexponential iO and either subexponential LWE or subexponential bilinear-map assumptions.

In FHEW and TFHE, bootstrapping evaluates the decryption function via a blind rotation, whose resolution limits the message space. We propose instead to bootstrap the \emph{error}. By rounding the ciphertext at a resolution that is a multiple of the message modulus, we preserve the message exactly. Reduction modulo a small integer then yields a noise-free encryption of the error, which a single blind rotation lifts exactly before it is subtracted. The message modulus is thus constrained solely by the noise and can be much larger than in standard TFHE. Since the error takes far fewer distinct values than the ring degree, a single blind rotation can also refresh several ciphertexts simultaneously. We call this procedure the comb bootstrap. Between refreshes, an integer remains encrypted in a single ciphertext, allowing additions modulo the message modulus and multiplications without programmable bootstrapping. Built on TFHE-rs, for $8$-bit integers on a single thread, our refresh is $3.5$ times faster than that of TFHE-rs, and $9.1$ times faster with the comb bootstrap; multiplication is $6.5$ times faster. In a residue number system, multiplication of integers modulo $\widehat P\ge 2^{32}$ is $19$ times faster than in TFHE-rs. The error bootstrap serves exclusively to refresh ciphertexts; evaluating any other function still requires programmable bootstrapping.

DNS was designed around UDP, and most DNS traffic today still follows that design: one query, one response, and no handshake. This makes DNS fast and scalable, but exposes client queries in cleartext. DoT, DoH, and DoQ provide privacy by encrypting DNS messages with TLS. This works once TLS/TCP or QUIC handshakes complete, but cold sessions spend extra round trips and CPU before the first private query can be sent—a cost that grows with post-quantum cryptography. We present VeilDNS, a DNS-native protocol that uses a post-quantum KEM and AEAD to encrypt DNS questions and answers and authenticate the resolver in a single UDP exchange. Given an authenticated resolver KEM key, clients have query privacy from their first UDP packet. VeilDNS supports stateless and stateful modes—the latter reducing recurring computation and bandwidth. An optional mode provides forward secrecy from the second query onward. By preserving the DNS wire format, VeilDNS runs on the standard UDP port 53. Compared with ML-DSA-authenticated Do(T/H/Q) on the well-provisioned network profile, VeilDNS's stateless and stateful modes achieve up to $3.5\times$ higher cold-session throughput, $4.8\times$ lower average latency, $4.7\times$ lower CPU time, $13.7\times$ fewer bytes, and $15.8\times$ fewer packets. On the constrained profile, the throughput gain reaches $12.4\times$. Tamarin establishes query confidentiality, response authentication, and forward secrecy.

We study fully connected neural-network reconstruction by combining cryptanalytic weight-direction extraction with learning from predicted labels. We adapt a ReLU extraction implementation to Leaky ReLU, compare sign-search methods, and estimate biases and output layers. We prove conditional bounds for direction recovery with approximate prefixes, preservation of local distance votes, prediction changes from aligned parameter errors, and sign selection with independent scoring data. We also specify exact row restoration and distinguish its guarantee from that of gradient masking. The experiments evaluate assisted extraction, with privileged access to gradients, hidden activations, and victim parameters, followed by label-based reconstruction. Across eight search seeds on the largest synthetic architecture, Leaky ReLU recovers 51--57 neurons in the deepest hidden layer, while ReLU recovers none. This advantage does not hold uniformly across architectures and layers. Removing victim-weight access from the sign walk gives less accurate signs, despite high final prediction agreement. Across 40 seeded runs on the two smallest synthetic victims, agreement on 5,000 inputs excluded from fitting and selection ranges from $0.9890$ to $0.9992$. On two CIFAR-10 victims, the reconstructed models achieve $56.40\%$ and $58.29\%$ agreement and exceed the distillation baseline on three functional metrics. We report label requests separately from privileged access and explain why prediction agreement does not identify network parameters.

In this work, we analyze the security of hash-based signatures in Lean4. We examine how different ways of accounting for an adversary’s work yield different notions of bit security. As our working example, we study two instances of XMSS with $128$ bit digests. Under most of the accounting modes we consider, we get $127$ bit security for strong unforgeability. However, under the most conservative convention that counts only the adversary’s direct random oracle queries, we only get $122$ bits of security. We prove these bounds in the random oracle model without computational hardness assumptions and give matching attacks. We also prove a tight bound of $127$ bits of strong unforgeability for SLH-DSA-128s. Our work is primarily motivated by recent autoresearch competitions, and it demonstrates the concrete impact of resource accounting. We hope that it helps designers of future challenges make an informed decision when choosing a notion of bit security that reflects their needs.

In the algebraic model, where one counts operations in $\mathbb{F}_q$ uniformly in the characteristic, the best published algorithm for factoring a polynomial of degree $n$ over $\mathbb{F}_q$, due to Kaltofen and Shoup with the rectangular products of Huang and Pan, uses $n^{1.80535+o(1)}\log q$ operations, and its bottleneck is the modular compositions of the giant steps. A new algorithm is presented for these compositions. Like the algorithm of Neiger, Salvy, Schost and Villard, the new method is based on the relation matrices of the argument. Since all compositions at one level of the giant steps share one argument, the relation matrices and a table of remainders are computed only once, and the remaining work consists of rectangular matrix products. For the two-matrix evaluation, we prove that a random change of basis puts every Frobenius image in good position. This reduces the cost of factorization in this model $$\text{from}\quad n^{1.80535+o(1)}\log q\quad\text{to}\quad n^{1.5532+o(1)}\log q,$$ and to $n^{3/2+o(1)}\log q$ if $\omega=2$; with the compositions of Neiger, Salvy, Schost and Villard performed one at a time, the exponent would be $1.7147$. In the bit model, and algebraically in small characteristic, Kedlaya and Umans obtained the exponent $3/2$. For a single composition with an arbitrary argument modulo a separable polynomial, the content of one short relation separates large value fibers, which gives a Las Vegas algorithm for every input at the exponent $(\omega+3)/4<1.3429$, previously known only for generic inputs, and a fourth evaluation level, with truncated powers obtained by transposition, lowers it to $1.3309$. As applications, we obtain faster algorithms for normal bases, minimal polynomials and irreducibility testing, and, for large $q$, factorization in $O(n^{1.5983})+n^{1+o(1)}\log q$ operations.

The hash-based Leighton-Micali Signature (LMS) has been standardized by IETF, NIST and ISO. State-of-the-art non-quantum security proofs for LMS have been given by Katz (SSR 2016) and Fluhrer (Eprint 2017/553). However, the actual structure of SHA-256(/192) is the (chopped) Merkle-Damg{\aa}rd construction using a blockcipher-based Davies-Meyer function, and precise security bounds of SHA-256-based LMS\_SHA256\_M32 and SHA-256/192-based LMS\_SHA256\_M24 should be derived in the {\it ideal-cipher model (ICM)}. This was {\it not} considered in Katz and Fluhrer's proofs. In fact, by leveraging structural properties of (chopped) Merkle-Damg{\aa}rd, we exhibit forgery attacks against LMS\_SHA256\_M32 and LMS\_SHA256\_M24 that expose the inapplicability of Katz's and Fluhrer's random-oracle bounds to the concrete SHA-256 constructions. The precise security guarantees of LMS\_SHA256\_M32 and LMS\_SHA256\_M24 thus remain unknown (and are also missing in the standards). To bridge the structural gap, we provide ICM-based security proofs for the additive-Davies-Meyer abstractions of LMS\_SHA256\_M32 and LMS\_SHA256\_M24. The security level of LMS\_SHA256\_M32 is roughly $256-\log_2 \widehat{B}$ bits, where $\widehat{B}$ is the number of blocks in SHA-256 calls internally made by LMS\_SHA256\_M32 and $\widehat{B}\ll2^{128}$. The security level of LMS\_SHA256\_M24 is roughly $\min \{ 192 - \log_2 \widehat{\Gamma} , 256-\log_2 \widehat{B} \}$ bits, where $\widehat{\Gamma}$ is the number of SHA-256/192 calls internally made by LMS\_SHA256\_M24 and $\widehat{B}$ is the number of blocks in them, and $\widehat{B}\ll2^{128}$ and $\widehat{B} \widehat{\Gamma} \ll 2^{192}$. In conclusion, LMS\_SHA256\_M32 and LMS\_SHA256\_M24 ensure a moderate (yet not ``full'') level of security.

Let $\operatorname{RM}(r,n)$ be the $r$th order Reed--Muller code of length $2^n$, and let $\rho(r,n)$ denote its covering radius. The values $\rho(2,6)=18$ and $\rho(2,7)=40$ are known, whereas the exact value of $\rho(2,8)$ remains open. Starting from the current state of the art bound $88\leq\rho(2,8)\leq96$, we give a computer-assisted reduction of the upper bound $\rho(2,8)\leq91$. We first show that every even-weight Boolean function on eight variables is within distance $90$ of a quadratic function. Changing one value then gives the bound $91$ for odd-weight functions. Our main lemma addresses rank-four seven-variable quintics: when their second-order distance is $36$ and their maximum quadratic-shift first-order distance is $56$, they have at least $60$ minimizing quadratic cosets and at most $12$ cosets of cost $56$. The complete proof covers all $68443$ quartic classes. For every rank-four quintic, the distance-$56$ cosets are enumerated outright, and the $5199$ words are examined individually. Profile counts, hyperplane contractions, and support moments then give the even-weight bound. We describe the calculations and enumerations, together with the classification upon which the proof depends. Instructions to verify the computer search portion may be found at $\texttt{https://github.com/EvelynSabo/RM28}$.

Let $\omega$ denote the matrix multiplication exponent. Very recently, OpenAI showed that $\omega\le9/4$. We demonstrate that, for any fixed $\eta>0$, if $\omega\le9/4-\eta$, then there is a constant $\delta=\delta(\eta)>0$ such that heuristic lattice sieving can be improved to $(3/2-\delta)^{n/2+o(n)}$ time under the spherical heuristic used in the BDGL analysis. With known matrix multiplication algorithms, our method already yields subquadratic search within BDGL buckets.

We revisit a classical result of Coppersmith and Shparlinski [CS00] showing bounds on how well polynomials can approximate the discrete log function. They showed that for any univariate polynomial $f(X) \in \mathbb{F}_p[X]$ with $\deg(f) \leq D$, we have: $$ |\{ x \in \mathbb{F}_p^\times \mid f(x) = \mathsf{dlog}(x) \}| \leq \sqrt{2 D p}.$$ We show two improvements: (1) For all $D$, we improve the upper bound above to $(1+o(1)) \cdot \sqrt{Dp}$. In particular, we give nontrivial upper bounds on the approximation even for $D > p/2$. This new upper bound is the Johnson bound from the theory of list-decoding of error-correcting codes, and in fact our proof uses a connection to that problem, as well as other combinatorial ideas. (2) For $D = 1$, where both the above bounds are $\mathcal{O}(\sqrt{p})$, we give an asymptotically improved upper bound of $\mathcal{O}(p^{2/5})$. This is based on the sum-product phenomenon of additive combinatorics. We also improve the [CS00] bounds on the number of points of the form $(x, \mathsf{dlog}(x)) \in \mathbb{F}_p^2$ that any bivariate polynomial $Q(X,Y) \in \mathbb{F}_p[X,Y]$ with $\deg(Q) \leq D$ can vanish on, with our new bounds approaching the analogue of the Johnson bound for this problem.

Due to their widespread applications in decentralized and privacy preserving technologies, commitment schemes have become increasingly important cryptographic primitives. With a wide variety of applications, many new constructions have been proposed, each enjoying different features and security guarantees. In this paper, we systematize the designs, features, properties, and applications of vector commitments (VCs). We define vector, polynomial, and functional commitments and we discuss the relationships shared between these types of commitment schemes. We first provide an overview of the definitions of the commitment schemes we will consider, as well as their security notions and various properties they can have. We proceed to compare popular constructions, taking into account the properties each one enjoys, their proof/update information sizes, and their proof/commitment complexities. We also consider their effectiveness in various decentralized and privacy preserving applications. Finally, we conclude by discussing some potential directions for future work.

Bitcoin bridges, protocols that lock BTC on Bitcoin and represent it on a secondary system, underpin much of Bitcoin's application layer, yet remain poorly secured. Deployed bridges rely on federated custody with honest-majority assumptions, while BitVM2, the state of the art in trust-minimized bridging, incurs worst-case dispute costs of approximately \$16,000, requiring large operator bonds and deposits that restrict participation to well-capitalized parties. We present BitVM3-BRIDGE, a trust-minimized bridge architecture from Bitcoin to (i) chains with finality certificates, such as Ethereum, and (ii) Bitcoin rollups. Our main contribution is an end-to-end bridge construction that makes trust-minimized Bitcoin bridging practical at scale. The bridge is powered by BitVM3-CORE, a modular abstraction for permissionless off-chain computation on Bitcoin using garbled circuits. In BitVM3-CORE, a challenger evaluates a garbled circuit entirely off-chain and obtains a fraud-proof witness if and only if the operator's claim is incorrect. This paradigm reduces total on-chain costs to approximately \$9, with the challenge transaction itself costing just \$0.20. This nearly 1000× cost reduction enables smaller bonds, broader operator participation, and smaller deposit sizes. Beyond the bridge itself, we make two additional contributions. First, we formalize BitVM3-CORE as a sound and complete on-chain proof system under standard cryptographic assumptions. Prior GC-based proposals typically provide either informal security arguments or construction-specific formalizations. By contrast, our framework captures existing constructions within a uniform model and gives a generic treatment based on axiomatized security and functional assumptions. Second, we introduce an on-chain Bitcoin light client secure in the variable-difficulty setting, enabling permissionless chain introspection on Bitcoin and thereby the rollup variant of BitVM3-BRIDGE.

Although recent surveys on privacy-enhancing technologies concluded that FHE cannot feasibly evaluate non-linear activation functions in modern ML architectures, 21 CKKS-based frameworks have since demonstrated end-to-end private inference of LLMs with up to 8B parameters. However, as the field grows rapidly, the literature has become fragmented. Frameworks differ in ciphertext packing layouts, model fidelity, software and hardware stacks, and reported metrics, that hinder direct comparison and reproducibility. This paper presents the first systematization of knowledge for non-interactive, CKKS-based private LLM inference. We categorize the design space across two axes: a model-level axis (packing layout for linear blocks and model preservation for non-linear blocks) and a system-level axis (covering hardware, compilers, bootstrapping management, and hybrid execution). To standardize reporting framework configurations and results among researchers, we propose a Private LLM Card System (PLCS). Furthermore, we introduce POLARIS, a model-preserving reference framework for CKKS-based private LLM inference and provide it as an open-source proof-of-concept. POLARIS evaluates encrypted inference for the entire BERT family, from BERT-Tiny to BERT-Base, on CPU and GPU backends, the first framework to demonstrate this. Our analysis shows that only 5 out of the 21 surveyed frameworks are model-preserving, that is, they evaluate standard, unmodified LLMs without retraining or architectural substitutions while keeping the entire prompt encrypted. We also show that model-preserving CKKS approximations maintain high downstream task accuracy from BERT-Tiny up to Llama-3-8B. We identify a runtime gap of roughly four orders of magnitude between the best encrypted and plaintext inference as the primary barrier to practical use. While our analysis confirms that CKKS-based inference is now algorithmically feasible for non-linear functions and large models, we conclude that it remains operationally impractical for many human-facing applications until the efficiency gap is narrowed. We outline promising research directions to close this gap.

Threshold encrypted mempools protect the privacy of transactions up until the point their inclusion on chain is confirmed. They are a promising approach to protection against front-running attacks on decentralized blockchains. Recent works have introduced two key properties that an encryption scheme must satisfy to operate efficiently on large-scale decentralized blockchains such as Ethereum: Silent Setup, as introduced by Garg et al. (CRYPTO'24), demands that a threshold encryption scheme does not require any interaction during the setup phase and only relies on the existence of Public Key Infrastructure. Batched Decryption, as introduced by Choudhuri et al. (USENIX'24), demands that an entire block containing $B$ encrypted transactions can be decrypted using communication that is independent of (or sublinear in) $B$, without compromising the privacy of transactions that have not yet been confirmed. While existing constructions achieve either Silent Setup or Batched Decryption independently, a truly decentralized and scalable encrypted mempool requires both properties to be satisfied simultaneously. In this work, we present the first "Batched Threshold Encryption scheme with Silent Setup" built using bilinear pairings. We provide formal definitions for the primitive and prove security in the Generic Group Model. We provide several optimizations and implement our scheme to evaluate its performance. Our experiments demonstrate its efficiency for deployment in blockchain systems.

At a high level our contribution is threefold: we improve the quantitative MCA error bound for polynomial generators, we prove a refinement of the implication from list-decodability to MCA, and we clarify that in general, these two notions are distinct. We show that, for every finite field $\mathbb{F}$, every nonempty seed set $S\subseteq\mathbb{F}$, every linear code $\mathcal{C} \subseteq \mathbb{F}^{n}$ of relative minimum distance $\delta_{\mathcal{C}}$ and every degree $d \geq 1$, the univariate powers generator $G_{d}(x) := (1,x,\dots,x^{d})$ has mutual correlated agreement for $\mathcal{C}$ at relative proximity parameter $\gamma$ with error $O(d\max\{1,n\gamma\}/|S|)$ below the smaller of the unique decoding radius and the generalized Johnson radius $J_{d+2}(\delta_{\mathcal{C}}) := 1-(1-\delta_{\mathcal{C}})^{1/(d+2)}$, with a one-coordinate margin below the latter when it is smaller. Then, we show that list-decodability at radius $p$ with list size $L$ implies MCA slightly above $1-\sqrt{1-p}$ (the improvement on the radius is dependent on the list size). The previous state-of-the-art result of Gao, Cai, Xu and Kan showed that list-decodability at radius $p<\delta_{\mathcal{C}}$ with list size $L$ implies mutual correlated agreement at every proximity parameter strictly below $1-\sqrt{1-p}$. Finally we construct two families of codes that show obstructions to any improvement of the $1-\sqrt{1-p}$ bound, or to strong converse statements. Informally, a bound of the form $\epsilon_{\mathsf{MCA}}(1-(1-p)^\alpha)\leq Q(n, L)/|\mathbb{F}|$ for some polynomial $Q$ and $\alpha > 1/2$ cannot hold for all linear codes $\mathcal{C}$ under the sole hypothesis that $\mathcal{C}$ is $(p,L)$-list-decodable. Similarly, for any distance $0<\delta<1$ and any $1-\sqrt{1-\delta}<p<\gamma<1$, there exists a family of linear codes with fixed positive rate and relative distance tending to $\delta$ such that $|\mathbb{F}|\epsilon_{\mathsf{MCA}}(\gamma)\leq \mathrm{poly}(n)$ but the list size at radius $p$ is $n^{\omega(1)}$. Both counterexample families exist over fields of any characteristic. Both MCA errors are for the line generator.

In lattice sieving, the sphere model assumes that sieving elements are distributed close to or on a sphere with uniformly distributed direction. It is extensively used to predict how lattice sieving behaves. In the sphere model the probability that a random pair of vectors reduces is asymptotically $p_n={(3/4)}^{n/2}/\sqrt{3\pi n/8}$. In practice sieving algorithms have been observed to perform better than predicted by the sphere model. It is an open question how this gap behaves asymptotically: does the gap vanish or grow as the dimension grows? Our work answers this question by showing that it is asymptotically constant. We generalise the sphere model to uniform ball and non-uniform ball models and analyse reduction probability distributions. The reduction probability advantages of our models over the sphere model range from $\times 1.5$ up to $\times 8$. Moreover, we examine scaled depth distributions (defined for dimension $n$ as $w=-n \ln \|x\|$) in the asymptotic setting. Under global reductions the output scaled depth distribution converges to $\text{Exp}(2/3)$ for any converging family of scaled depth distributions that is dominated by a suitable integrable function. The input scaled depth distribution only affects the total reduction probability. Compared to (the scaled depth distribution $\text{Exp}(1)$ induced by) the uniform ball as input distribution, using this stable limit distribution as input distribution results in an increased reduction probability ($\times 4.5$ versus $\times 8$).

Programmable bootstrapping (PBS) in FHEW/TFHE evaluates a lookup table (LUT) while refreshing a ciphertext, but a t-entry negacyclic table must fit, with redundancy, into the 2N signed rotation positions of a ring accumulator. Module bootstrappings, namely extended bootstrapping (PKC'23), monomial-matrix bootstrapping (TCC'25) and their successors, rotate a redundant table once in a module of rank tau, at a cost linear in both the rank and the redundancy. Meta-PBS (CCS'26) removes the redundancy by iterating the rotation in the ring, but supports plaintext moduli only up to 2N, and running it inside the module pays the rank in every rotation. We present Descent-PBS, which pays the module rank of a large table only in its first rotation. We prove that for a module secret embedded from the subring, truncation commutes with the secret, so one public functional key switch with merged columns repacks all tau_0 components of a module accumulator into the ring and removes the per-component factor tau_0 of repacking. The bootstrapping then continues with Meta-PBS refinements in the ring, at tau_0 + K instead of (K'+1) tau_0 external products per key. For block one-hot secrets, the first-rotation exponents are multiples of tau_0, so every combined key is a scalar matrix: the tau_0 components share one key per block, and since all exponents are public in advance, one pass over the bootstrapping key builds the keys of all rotations of a negacyclic table. Ties-to-even gadget rounding removes a refinement bias that we trace to half-up rounding on the FFT grid. In a TFHE-rs-based engine, Descent-PBS evaluates a 16-bit negacyclic LUT in 196 ms on one thread at 128-bit security and a model-predicted failure probability below 2^-64. With the same keys and failure budget, the descent alone makes it 1.44-2.40x faster than Meta-PBS run inside the module for dense secrets; for block one-hot secrets, the descent and the shared keys together make it 1.51-3.32x faster, and 1.37-3.57x against the same baseline re-planned for more conservative 131-bit parameters. General 13-16-bit LUTs take 179-368 ms, 3.8-6.6x faster than WoP-PBS in its authors' configuration on the same single-ciphertext interface, at about twice its memory. The failure probabilities are predictions of a model that we validate where failures are observable, and the 16-bit keys take 1,208 MB.

SQIsign is a compact isogeny-based signature scheme. We present a low-latency AVX-512 implementation of complete SQIsign 3.0 verification at security levels I, III, and V. Our implementation provides vectorized curve-side verification, including the Superglue transition, and introduces dynamic-programming strategies for the degree-$2^\ell$ and theta-model $(2,2)$-isogeny chains. The strategies account for batched point evaluation and the preparation of SIMD data. On an Intel Core i7-11800H running native Ubuntu 24.04, the complete verifiers achieve $2.14\times$, $2.08\times$, and $2.34\times$ speedups, respectively, over the SQIsign 3.0 Broadwell reference verifiers (the optimized 64-bit assembly implementation).

Motivated by the accordion mode approach, we propose a length preserving tweakable wide block mode based on the hash-encrypt-hash paradigm. The construction uses AES and HMAC-SHA3-256 with five purpose separated working keys derived from a single master key, replacing algebraic universal hashing with a cryptographic keyed hash. An encrypted internal seed couples two separately keyed head branches and determines the counter mode keystream. The head layers permit parallel evaluation, while inter-branch dependence is retained even when the tail is empty. The mode supports every bit length within its specified range, starting from $2n$ bits without padding, where $n$ is the block size. Variable length external information is incorporated into a fixed length core tweak through application specific preprocessing. We establish birthday bound tweakable variable-input-length strong pseudorandom permutation security under the stated block cipher, keyed hash, and key derivation assumptions. The analysis covers adaptive encryption and decryption queries, varying message lengths, repeated tweaks, and reused internal values. We also describe derived interfaces for authenticated encryption with associated data, tweakable encryption, and deterministic authenticated encryption, distinguishing their additional security requirements from the core guarantee.

The 2007 algorithm of Joux, Naccache, and Thomé (JNT) shows that, with subexponential access to an $e$-th root oracle, one can forge RSA signatures for odd $e$ in time close to the special number field sieve, without factoring the modulus; a recent JNT implementation by Shea et al. [2] carried that attack to $1024$-bit RSA. We revisit the JNT construction at $e=2$, the Rabin case, where an $e$-th root oracle is a square-root oracle. A raw square-root oracle factors $n=pq$ in one query, so it is of no interest; the interesting object is a redundancy-constrained (affine-padded) Rabin oracle that returns a single canonical root and thereby resists the one-query attack. We show that a one-sided number field sieve against such an oracle produces a congruence of squares $X^2\equiv Y^2\pmod n$ with $X\not\equiv\pm Y$ with probability $\tfrac12$ per dependency, and hence factors $n$ in special-number-field-sieve time \[ L_n \left(\frac{1}{3},{\sqrt[3]{\frac{32}{9}}}\right)\simeq L_n(1/3,{1.526\ldots}), \] strictly below the general number field sieve's \[ L_n \left(\frac{1}{3},{\sqrt[3]{\frac{64}{9}}}\right)\simeq L_n(1/3,{1.923\ldots}). \] The mechanism is a pleasant inversion: the sign ambiguity that the odd-$e$ algorithm must suppress becomes, at $e=2$, the very quantity that leaks the factorization. We give the algorithm in full --- LLL polynomial selection for a quadratic field, a line sieve producing prime-ideal relations, quadratic characters, $\mathbb F_2$ linear algebra, and an exact number-field square root --- prove the half-rate splitting, and analyse the complexity, including the precise reason the attack collapses when the padding is a hash rather than an affine function of an attacker-chosen message. An open-source implementation realises every step. A small toy example run of it, from the padded modulus to the recovered factors, is given in Appendix A. Our implementation confirms a clear performance improvement in factoring speed.

The FX construction (FX) is one of the simplest key-length extension schemes for block ciphers, introduced by Kilian and Rogaway as a generalization of DESX. By extending the key length without modifying the underlying block cipher, FX can improve security against adversaries that perform quantum computation but are restricted to classical queries to the keyed construction. Recently, Shiba and Iwata showed in their ToSC 2026 paper that FX with an $n$-bit block and a $\kappa$-bit internal key is secure up to approximately $2^{(n+\kappa-\log_2\mu)/3}$ total classical and quantum oracle queries in the quantum ideal cipher model, where $\mu\leq2^\kappa$ is the number of independently keyed instances. In this paper, we improve this bound to approximately $2^{(n+\kappa)/3}$ total oracle queries in the same model against fully adaptive adversaries, for every $\mu\geq1$ and $1\leq\kappa\leq2n$. The known attack based on the offline Simon's algorithm can target a single keyed instance and matches our bound in the exponent. Thus, the exponent of the total query complexity required to break FX is independent of the number of keyed instances in this parameter regime.

Motivated by the MAMBA proposals, we study the worst case hardness of learning with quantization (LWQ) with public dither. We allow any efficiently computable dither function and efficiently samplable seed distribution; the matrix is uniform and independent of the secret and the seed. Using the randomized polar lattice quantizer of Lyu et al., we construct explicit families with polynomial power of two moduli. For the search family, polynomial time recovery of the uniformly chosen secret with inverse polynomial probability yields quantum polynomial time algorithms for the gap shortest vector problem (GapSVP) and the shortest independent vectors problem (SIVP) on arbitrary \(n\) dimensional lattices, with approximation factors \(O(n\log n)\) and \(O(n(\log n)^2)\), respectively. Under stronger parameter conditions, a second family admits a decision reduction: a polynomial time algorithm with inverse polynomial distinguishing advantage yields quantum polynomial time algorithms for the same lattice problems with factors \(O(n(\log n)^3)\) and \(O(n(\log n)^4)\), respectively. Conditional on the public seed, the comparison output is uniform in the prescribed dither coset and independent of the matrix. We also examine extensions to learning with errors (LWE) with interval uniform errors, as arising in MAMBA Frost. We identify obstacles caused by deterministic quantization boundaries and give a local perturbation bound with explicit dependence on the number of observations. This analysis does not establish a complete worst case reduction for these errors or hardness at the concrete MAMBA parameters.

Bitcoin Script lacks native pairing operations for efficient direct verification of Groth16 proofs. Conventional federated bridges instead authorize withdrawals through a signing quorum, whose collusion can release funds without valid evidence. We present the Tritone protocol, which lets Bitcoin enforce the outcome of verifying a Groth16 proof for an NP relation fixed in a one-time trusted setup, with the locked funds secure as long as one of a fixed set of $N$ operators is honest. Verification is optimistic and off-chain, and every transaction is standard under current relay policy, so Tritone runs on Bitcoin today without consensus changes. Tritone generalizes the two-party BABE protocol to a fixed committee of $N$ operators, with one dispute instance per ordered pair. Cut-and-choose protects against malicious garblers, while Feldman verifiable secret sharing correlates input keys across candidates. Our new Lamport-adaptor gadget forces a challenging verifier to disclose the shares selected by the prover's committed proof element, providing the transaction-level binding left unspecified by BABE. A single set of disclosed shares then unlocks all retained candidates. We formalize the multi-party primitive, prove the protocol secure against up to $N-1$ statically corrupted operators, and specify its complete pre-signed transaction graph. We implement Tritone in Rust. On Bitcoin mainnet, when one verifier disputes a claim at every stage, the prover-candidate posts 9,607 vB and the verifier 18,160 vB of protocol transactions. In local benchmarks at 40-bit statistical security, the prover-candidate of each dispute instance retains as little as 112.83 MiB. Tritone thus replaces trust in a signing quorum with a single-honest-operator assumption wherever locked bitcoin is released to an operator against a Groth16 proof, with Bitcoin bridges as our showcase.

Hardware accelerators for lattice-based post-quantum cryptography (PQC) have largely converged on the radix-2 number-theoretic transform (NTT). The spectrum of standards that crypto-agility must accommodate, however, extends beyond NIST. In response to advances in cryptanalysis and to reduce the attack surface, national authorities are standardizing or recommending lattice-based algorithms with alternative algebraic structures, as well as schemes built on entirely different primitives. For instance, NTRU+, selected in the Korean PQC competition and currently undergoing standardization, is defined over a trinomial ring whose degree is divisible by three and thus requires a mixed-radix NTT comprising both radix-2 and radix-3 layers, whereas SMAUG-T employs an NTT-unfriendly modulus. Support for heterogeneous algebraic structures is therefore no longer optional but a prerequisite for crypto-agile design; existing radix-2-centric accelerators, however, fail to meet this requirement. In this paper, we present a crypto-agile mixed-radix NTT accelerator that performs transforms over both negacyclic and trinomial rings on a single datapath. Our contributions are threefold. First, we design a unified butterfly unit that integrates two parallel radix-2 butterflies, one radix-3 butterfly, and the trinomial transform on shared arithmetic resources, in which a generic 17-bit Montgomery path and an ML-DSA-specific 23-bit reduction path share the same two DSPs. Second, we propose a conflict-free memory mapping that guarantees in-place parallel access across all mixed-radix layers with a single 1-bit bank-selection function, namely address parity for radix-2 and a fixed address bit for radix-3, and requires neither mapping tables, nor coefficient reordering, nor additional BRAMs. Third, we introduce a generalized modular constant division that combines the multiple alignment of Montgomery reduction with the quotient estimation of Barrett reduction to perform the $3^{-1}$ scaling of the radix-3 inverse NTT without any DSP. Implemented on an Artix-7 FPGA, the proposed core supports all security levels of ML-KEM, ML-DSA, HAETAE, SMAUG-T, and NTRU+ using 5,279 LUTs, 4 DSPs, and 9 BRAMs at 141.5~MHz. For NTRU+, it achieves a $4.1$--$13.0\times$ improvement in area-time product (ATP) over approaches that resort to radix-2-only cores via degree lifting, and new moduli of up to 17 bits can be integrated at the cost of fewer than 20 LUTs.

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

Blockchain technology allows parties to use a consensus protocol to add transactions and data to a decentralized ledger that are immutable. However, the amount of transactions that can be processed within a consensus protocol and thus added to the ledger within a given time frame is limited. This is a scalability issue. Layer-2 protocols are a class of approaches that process transactions off-chain, i.e. without involvement of the consensus protocol, but allow usage of the consensus protocol as a backup for security. This potentially reduces the processing of $n\in\mathbb{N}$ transactions to only $\mathcal{O}(1)$ transactions being committed to the ledger. The basic building blocks of Layer 2 protocols are Payment Channels, whereas newer protocols as Hydra (FC'21) allow for multi-party channels that are not limited to payments but can execute smart contracts, i.e. program code. There has been substantial research proposing tools and improvements to Layer 2 protocols, but most assume the original two party Payment Channel design. This makes it unclear to what degree existing techniques can be utilized with Hydra style multi-party channels. This work (1) presents a survey of such such existing two party channel protocols and tools built on top of them. We use a didactic approach with a focus on explaining their core ideas. (2) This work identifies uses cases for which novel protocols for Hydra should be developed. (3) This work analyzes open problems for Hydra, lists relevant related work and proposes which existing tools can be used to address them or serve as a starting point for further research.

We prove that ten rounds of \AES{} with independent and uniform random round keys are $\varepsilon_{10}$-close to pairwise independent, with \[ \varepsilon_{10}\leq\frac{3017}{2^{141}}<2^{-129}. \] For every two distinct plaintexts, the joint ciphertext distribution is therefore within this statistical distance of the uniform distribution on ordered pairs of distinct ciphertexts. The same sampled key tuple is used for both encryptions. The construction retains the \AES{} round transformations, including the omission of MixColumns in the final round, with input and output whitening. Let $E_{10}$ denote this random permutation and $\Omega$ the set of nonzero differences. We establish the result through the induced one-norm bound $\norm{\Dten-U}_1\leq3017/2^{140}$ on its averaged difference-distribution matrix restricted to $\Omega$, where $U$ projects onto the uniform distribution on $\Omega$. The proof groups the ten rounds into five superbox layers and decomposes the deviation from uniformity into fourteen orthogonal subspaces according to the number of active words and residual factors. Local Gram moments and MDS code constraints control the dependencies between word differences. Bounds for the distributions produced by the first rounds preserve their common source variables, while joint estimates for the last four rounds retain the constraints across two linear layers. The final conversion to statistical distance uses the support size of each component. Exact rational evaluation of the resulting finite recurrence establishes the stated bound.

CMoSS facilitates modular specifications, design and analysis of cryptographic protocols. Modular design and analysis is achieved by supporting provably-secure compositions of protocols; typically, a protocol uses a blackbox subprotocol, and is proven secure when composed with any subprotocol meeting the blackbox specifications. For modularity of specifications, CMoSS extends the approach of the MoSS framework: protocol specifications are defined modularly, by a set of independent predicates (games) for each model (assumption) and requirement (goal). CMoSS makes it feasible to rigorously specify, develop and analyze realistic applied cryptographic protocols, supporting real-time concurrency and involving different attacker capabilities, delays, faults and synchronization challenges. CMoSS specifications provide a precise formalization of the informal specifications used by practitioners, facilitating provable security for practical protocols.

Error-correcting codes are a useful tool in cryptography, being used both to design schemes whose hardness relies on coding theory problems (the area typically known as code-based cryptography) and as a building block in other contexts, such as proof systems and associated cryptographic argument systems. Among all codes used in cryptography, Goppa codes stand out, notably in the well-known McEliece encryption scheme, where they have withstood the test of time as one of very few classes of codes to be considered secure for over 40 years. Therefore, a natural question is whether Goppa codes can also be used in the construction of proof systems or cryptographic argument systems. In the context of probabilistically checkable proofs (PCPs), codes are used to transform proofs into a format that requires only a constant number of queries for verification. This efficiency is often achieved using low-degree polynomial codes, which enable the verifier to check consistency through interpolation, ensuring correctness with minimal effort. This application underscores the importance of good codes in enhancing the robustness and verifiability of proof systems. Given their critical role, we take a closer look at how error-correcting codes are used in proof systems to find a new way of obtaining an interactive oracle proof system of proximity (IOPP) from Goppa codes.