In lattice-based homomorphic encryption schemes, ciphertexts carry an inherent noise that grows as computation advances. The key-switching procedure of these schemes allows the homomorphic re-encryption of a ciphertext under a new secret key, but it incurs substantial noise growth and computational cost. In this work, we generalize the RNS-based decomposition technique of the CKKS scheme to an arbitrary number of input polynomials and secret keys. Performing multiple relinearizations and rotations in batch enables one to hoist the modulus lowering and decomposition steps of key-switching, respectively, which restricts noise growth and avoids redundant computation. We prove the security and correctness of all the proposed algorithms, and derive explicit noise bounds for them. As an application, we introduce a ternary multiplication algorithm that relinearizes the non-affine components of a product of three ciphertexts in batch, and performs rescaling in two phases so that relinearization runs at a lower modulus level. Compared with the usual sequence of two binary multiplications, this algorithm introduces a single key-switching error term, improving precision by up to half a bit and reducing latency by up to 1.31×. We generalize to n-ary ciphertext multiplication via a polynomial-time algorithm that combines binary and ternary multiplications into a tree of optimum depth minimizing a given latency cost function. Such products arise, for instance, in the SHIP bootstrapping algorithm; experiments with 128-bit-secure parameters on top of the Lattigo library show an average speedup of 1.20× over the standard approach for n = 192 with 32 threads. Further examples illustrate the impact of these optimizations on private deep neural network inference. In addition, we provide—to the best of our knowledge—the first noise analysis of the double-hoisted BSGS matrix-vector multiplication algorithm of Bossuat et al. (2021), a building block of state-of-the-art CKKS bootstrapping circuits. We discuss a novel optimization concerning the automorphism applications during its giant steps.

Anonymous tokens with private metadata bit (ATPM) allow an issuer to embed a hidden trust flag, as a single bit, within issued tokens. The bit remains hidden from the clients, but verifiers can read the bit and rate-limit or discard tokens marked suspect. A series of ATPM constructions exist in the literature, however all current constructions rely on classical hardness assumptions such as RSA groups, pairings, or elliptic-curve VRFs and do not provide any post-quantum security guarantees. In this work we present, the first ATPM scheme based on lattice assumptions. Tokens generated with our scheme are publicly verifiable, and privately bit-extractable given partial knowledge of the issuing authority's secret. Our design follows the Fischlin blind-signature paradigm and enriches it with lattice-based linearly-homomorphic encryption to carry the hidden bit. We also instantiate our scheme from Falcon-512 and the efficient LNP22 lattice NIZK proof system (Lyubashevsky et. al, Crypto '22). The resulting protocol, which we call $\textsf{Atlantis}$, requires 70 KB of client-issuer communication and yields 129 KB tokens.

We give new algorithms for tree evaluation (S. Cook et al. TOCT 2012) in the catalytic-computing model (Buhrman et al. STOC 2014). Two existing approaches aim to solve tree evaluation (TreeEval) in low space: on the one hand, J. Cook and Mertz (STOC 2024) give an algorithm for TreeEval running in super-logarithmic space $O(\log n\log\log n)$ and super-polynomial time $n^{O(\log\log n)}$. On the other hand, an earlier algorithm of J. Cook and Mertz (STOC 2020), run on a catalytic tape, solves TreeEval in logarithmic $O(\log n)$ free space and polynomial time, but with polynomial $O(\sqrt{n})$ catalytic space. We show that the latter result can be improved. We give a catalytic algorithm for TreeEval with logarithmic $O(\log n)$ free space, polynomial runtime, and subpolynomial $2^{O(\log^\epsilon n)}$ catalytic space (for any $\epsilon > 0$). Our result also implies an improved simulation of time by \textit{catalytic} space, via the reduction of Williams (STOC 2025). Our TreeEval algorithm comes from a framework, inspired by private information retrieval, that generically reduces tree evaluation to two combinatorial objects: matching-vector families and \emph{decoders} (a new object we define that closely resembles decoding polynomials). These ingredients' parameters directly govern an algorithm's resources: the vectors' dimension determines its catalytic space, and the decoder's sparsity determines its free space and runtime. In addition to enabling our new algorithm, this framework explains existing tradeoffs, for example why the Cook–Mertz algorithm needs super-logarithmic space but no catalytic tape. It also lets better matching-vector families or decoders plug in directly to give better algorithms.

In recent years, numerous new and more efficient constructions of zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) have been proposed, motivated by their growing practical applications. However, in most schemes, when the witness is changed, the prover has to recompute the proof from scratch even if the new witness is close to the old one. This is inefficient for applications where proofs are generated for dynamically changing witnesses with small changes. In this paper, we introduce DYNARK, a dynamic zkSNARK scheme that can update the proof in sublinear time when the change of the witness is small. DYNARK is built on top of the seminal zkSNARK protocol of Groth, 2016. In the semi-dynamic setting, for an R1CS of size $n$, after a preprocessing of $O(n\log n)$ group operations on the original witness, it only takes $O(d)$ group operations and $O(d\log^2 d)$ field operations to update the proof for a new witness with distance $d$ from the original witness, which is nearly optimal. In the fully-dynamic setting, the update time of DYNARK is $O(d\sqrt{n\log n})$ group operations and $O(d\log^2 d)$ field operations. Both the proof size and the verifier time are $O(1)$, which are exactly the same as Groth16. Compared to the scheme in a prior work by Wang et al. 2024, we reduce the proof size from $O(\sqrt{n})$ to $O(1)$ without relying on pairing product arguments or another zkSNARK, and the update time and the verifier time of DYNARK are faster in practice. Experimental results show that for $n=2^{20}$, after a one-time preprocessing of 74.3 seconds, it merely takes 3 milliseconds to update the proof in our semi-dynamic zkSNARK for $d=1$, and 60 milliseconds to update the proof in our fully-dynamic zkSNARK. These are 1433$\times$ and 73$\times$ faster than Groth16, respectively. The proof size is 192 bytes and the verifier time is 4.4 milliseconds. The system is fully compatible with any existing deployment of Groth16 without changing the trusted setup, the proof and the verification algorithm.

Linear cryptanalysis measures the correlation of a cipher with the characters of the group used to define differences. If that group is replaced by a second elementary abelian group structure on the same set, here the one coming from a binary bibrace, then the admissible masks are no longer the ordinary scalar products: exactly half of them survive, and the other half are forced to be quadratic. Beyne's geometric approach develops linear cryptanalysis over an arbitrary finite abelian group, providing a natural framework for this setting. We instantiate it on the group of a particular bibrace and apply it to CRAFT. Over this group the MIDORI/CRAFT S-box has four probability-one relations, forming a small subgroup of the dual which the S-box preserves in both directions. A trail that stays inside that subgroup is determined by its first mask and propagates linearly, so the search for the best such trail is a minimum weight codeword problem, which we solve exactly by complete enumeration. A trail costs correlation, and it restricts the key to a weak-key class. We show that the exact reading, obtained by analysing the diffusion layer and the key addition together rather than separately, gives a class several bits larger than the one obtained cell by cell. One concrete consequence is that CRAFT's round constants, whatever their values, impose no restriction at all. On CRAFT we obtain weak-key distinguishers up to eighteen rounds. At fourteen rounds a single trail has squared correlation $2^{-44}$ over a class of $2^{108}$ keys, against $2^{-62.12}$ for the designers' linear hull, which is the best known linear result on the cipher and holds for all keys. On that class the trail alone therefore exceeds the best linear correlation by eighteen bits at equal round count. Half of the optimal trails begin and end with ordinary linear masks, so these are linear approximations of CRAFT in the usual sense. A contrasting analysis of MIDORI64, which shares the S-box, traces its protection to the round constants and describes two known invariants of that cipher through other bibraces.

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

Chenu and Smith introduced the notion of $(d,\varepsilon)$-structures, pairs consisting of an elliptic curve over $\mathbb{F}_{p^2}$ and an isogeny of degree $d$ from the curve to its Galois conjugate, and defined an ideal class group action on supersingular $(d,\varepsilon)$-structures, inherited from the action on oriented supersingular elliptic curves. They also outlined extensions of the CSIDH key exchange and of the Delfs–Galbraith algorithm for the supersingular isogeny problem. In particular, they suggested that the latter, called the generalized Delfs–Galbraith algorithm, may be faster than the original one by a constant factor for small $d$, provided that the class group action on $(d,\varepsilon)$-structures can be evaluated efficiently. In this paper, we focus on the case $d = 2$ and present explicit radical $3$-isogenies for evaluating the action of the class of a prime ideal above $3$. Note that $3$ is the norm of the acting ideal, not the degree $d$ of the isogeny defining a structure; a radical $3$-isogeny maps a $(2,\varepsilon)$-structure to another. Our approach relies on two representations of $(2,\varepsilon)$-structures, by reductions of degree-$2$ $\mathbb{Q}$-curves and by Montgomery curves. We show that any $(2,\varepsilon)$-structure can be represented as a pair of a curve coefficient and a single sign, and from these representations we derive radical $3$-isogenies that efficiently implement the action. As an application, we give an explicit meet-in-the-middle algorithm for finding an ideal class connecting two given $(2,\varepsilon)$-structures, which is a part of the generalized Delfs–Galbraith algorithm.

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

AESpolyW, presented at the 2026 IEEE Symposium on Security and Privacy, is a wide-block encryption mode that preserves the length of each message. Its design lets operations of the Advanced Encryption Standard (AES) overlap with hash computations based on polynomial evaluation. Our attacks splice ciphertexts by copying blocks from one ciphertext to the same positions in another. On five-block messages, two encryption queries and one decryption query at a fixed public parameter, called a tweak, distinguish AESpolyW from a random permutation at that tweak. The two probabilities of reporting AESpolyW differ by more than \(1-2^{-3n}\), where \(n\) is the block size in bits. When AESpolyW decrypts the splice, an internal block-cipher inversion takes an output from an earlier encryption. The published proof treats such reuse as unlikely. The splice also works across distinct tweaks. We also attack three AESpolyW-based schemes for authenticated encryption with associated data (AEAD). All three use encode-then-encipher, adding a zero block before encryption and checking it after decryption. The zero block goes at the end, after the first block, or at the beginning. The tweak \(T=A\|\nu\) concatenates one block of associated data \(A\), which is authenticated without encryption, and one block of nonce \(\nu\), a public value intended for one-time use per key. Two encryptions at distinct nonces suffice to forge a new ciphertext that passes verification with probability one. In the experiment for indistinguishability under chosen-ciphertext attack (IND-CCA), we use one auxiliary encryption at a nonce distinct from the challenge nonce and at most one decryption. This identifies which of two chosen plaintexts was encrypted in the challenge with probability one.

We propose a lightweight block cipher named BAKSHEESH, which follows up on the popular cipher GIFT-128 (CHES'17). BAKSHEESH runs for 35 rounds, which is 12.50 percent smaller compared to GIFT-128 (runs for 40 rounds) while maintaining the same security claims against the classical attacks. The crux of BAKSHEESH is to use a 4-bit SBox that has a non-trivial Linear Structure (LS). An SBox with one or more non-trivial LS has not been used in a cipher construction until DEFAULT (Asiacrypt'21). DEFAULT is pitched to have inherent protection against the Differential Fault Attack (DFA), thanks to its SBox having 3 non-trivial LS. BAKSHEESH, however, uses an SBox with only 1 non-trivial LS; and is a traditional cipher just like GIFT-128, with no claims against DFA. The SBox requires a low number of AND gates, making BAKSHEESH suitable for side channel countermeasures (when compared to GIFT-128) and other niche applications. Indeed, our study on the cost of the threshold implementation shows that BAKSHEESH offers a few-fold advantage over other lightweight ciphers. The design is not much deviated from its predecessor (GIFT-128), thereby allowing for easy implementation (such as fix-slicing in software). However, BAKSHEESH opts for the full-round key XOR, compared to the half-round key XOR in GIFT. Thus, when taking everything into account, we show how a cipher construction can benefit from the unique vantage point of using 1 LS SBox, by combining the state-of-the-art progress in classical cryptanalysis and protection against device-dependent attacks. We, therefore, create a new paradigm of lightweight ciphers, by adequate deliberation on the design choice, and solidify it with appropriate security analysis and ample implementation/benchmark.

Anonymous credentials are a well-studied cryptographic primitive enabling users to prove statements about their identity and selectively present personal information in an unlinkable manner. The issuer, however, is often a single point of failure. Threshold issuance addresses this by distributing the issuer across several parties such that a quorum of them must cooperate to issue credentials. Numerous constructions of single-issuer and threshold issuance anonymous credentials have been proposed. However, existing schemes each have at least one of the following weaknesses: (1) their presentations depend on the number of attributes, (2) they are not concretely efficient, or (3) they rely on the random oracle model (ROM) for non-interactive presentations. In this work, we present a new construction of threshold anonymous credentials that has a constant presentation size of 240 bytes, rivals the efficiency of BBS, and does not rely on the random oracle model. We achieve this by combining techniques from set commitments with Boneh-Boyen (BB) signatures (Eurocrypt'04) and prove our scheme's security in the algebraic group model. This is on par with the tight security proofs of existing schemes, which typically rely on the AGM or GGM, or on assumptions justified in those models. Since signing uses linear operations, the scheme is easily thresholdizable, without requiring interaction between the issuers or preprocessing.

Trusted Execution Environments (TEEs), also known as secure enclaves, such as Intel SGX, Intel TDX, and AMD SEV, are seeing widespread use to perform computations on highly sensitive data. Several formal models exist to analyze the security of cryptographic protocols using TEEs, notably the one by Pass et al. (EUROCRYPT 2017) for attested computations in the Generalized UC framework. Using this model and the proposed global ideal functionality $\mathcal{G}_{\mathrm{att}}^{\mathrm{PST}}$, provably secure multi-party computations with practical efficiency are possible. Attested computations are achieved by having enclave outputs signed with a key pair held by $\mathcal{G}_{\mathrm{att}}^{\mathrm{PST}}$, together with the enclave's code. Being a global functionality, the verification key can be obtained by any party. Perhaps surprisingly, this model does not give rise to a meaningful notion of public verifiability, i. e. the ability of external parties to plausibly verify results, even though some commercially available enclaves allow exactly that. We formalize this intuition in the form of an impossibility result and propose a novel simulation technique where equivocation is not handled by the simulator resp. adversary anymore, but in a coordinated effort between our new functionality $\mathcal{G}_{\mathrm{att}}$ and a (local) ideal functionality $\mathcal{F}$ that is realized with public verifiability. To this end, several technical problems need to be solved, in particular to ensure that this new mechanism cannot be abused. While this approach is unconventional, to the best of our knowledge it is the first to achieve a general variant of public verifiability, a) even when all protocol parties are corrupted and $\mathcal{F}$ is probabilistic and, b) where guarantees of honest (external) verifiers are not affected by simulation at all. We call the latter property global public verifiability. We also address a second impossibility result of Pass et al., namely the requirement that every protocol party needs a TEE (even in a setting without public verifiability), unless an additional (global) setup is used. We address this impossibility result by introducing designated-verifier attestations that are only valid for a single party in a single protocol execution, akin to what is possible with real-world enclaves. Using our improved model, we propose protocols for (globally publicly verifiable) composable general MPC and prove their security under the notion of Universal Composition with Global Subroutines (Badertscher et al., TCC 2020) and static malicious corruptions.

A claim that a cryptographic protocol has been proved secure depends on the theory, the analysis software, the protocol model, and the security property being checked. I examine each of these for ProVerif and Tamarin. An audit of their published soundness arguments finds false statements, missing proofs, and gaps between the procedures justified on paper and those the tools run. I also reproduce previously reported bugs that cause Tamarin to accept false claims about the submitted models. ProVerif supplies no certificate for its full analysis, while Tamarin replays its proof tree with its own solver, leaving the correctness of that code to be trusted. A correct symbolic result can still fall short of the security claim made for a protocol. Models can omit behavior in parsers and state machines; secrecy queries can allow information to leak; and equations for cryptographic primitives need justification before they support computational guarantees. Better models, stronger queries and computational soundness arguments can address these problems, but someone must establish that they apply to the protocol at hand. For these reasons and more, I argue that calling ProVerif and Tamarin "provers" is misleading: we should call them symbolic protocol analyzers and report their results with the models, assumptions and evidence that support them. They remain useful for finding attacks and establishing symbolic properties, including for unbounded sessions.

Fixed point multi-scalar multiplication (MSM) is a major computational component of pairing-based SNARK proof generation. The Luo--Fu--Gong (LFG) framework is a variant of Pippenger's bucket method that uses a multiplier set $M$ and precomputed point multiples to reduce the number of buckets and online point additions. For radix $q$ and a positive multiplier set $M$, covering all digit residues requires a bucket set of size at least $q/(2|M|)$. Previous constructions approaching this bound based on primitive roots or power-residue classes impose radix restrictions that exclude $q=2^c$, thereby requiring additional binary-to-radix conversion in software implementations. We present two main bucket set constructions for power-of-two radices $q=2^c$, using the multiplier sets $M=\{1,2,3\}$ and $M=\{1,3\}$, respectively. Their cardinalities are $q/6+O(\log q)$ and $q/4+2$, respectively, so both asymptotically attain the counting bound $q/(2|M|)$ while allowing efficient radix-digit extraction through shifts and masks. We further give two generalizations. Using consecutive powers of $3$ as multipliers yields bucket sets of size $q/(2\ell)+O(\log q)$ for every fixed positive integer $\ell$. For $\ell=2^d$ and $c\ge d+2$, consecutive odd multipliers yield bucket sets of size $q/(2\ell)+d+1$. We also present scalar conversion and two strategies for handling the leading digit, allowing the bucket set constructions to be used within the LFG framework.

Oracle-based conditional payments triggered by real-world events support decentralized finance applications. However, dense independent bilateral deployments require $\Theta(Nn^2)$ outcome authorizations and $\Theta(n^2)$ settlement signatures for $n$ parties and $N$ outcomes. To go beyond two-party settings, we propose MuCPay, a multi-party oracle-based conditional payment protocol combining (i) $\Theta(Nn)$ off-chain signing shares with one on-chain settlement signature and (ii) BIP340-compatible scriptless settlement on Bitcoin. At its core, MuCPay introduces hash-bound adaptor multi-signatures (HB-AMS) that aggregate parties' conditional authorizations into a compact joint pre-signature. Its single-nonce structure and hash-bound adaptor integration enable efficient multi-party pre-signing. Unlike Double-Layer AMS (EuroS&P'26), HB-AMS produces a standard BIP340 signature under an aggregate public key, enabling direct Taproot key-path settlement. Under static corruption with one honest signer, we prove concurrent new-message unforgeability (CUF) and early-settlement resistance (ES) under our stated algebraic random-oracle model. For 128 parties and 16 outcomes, median complete local preparation takes 2.093 s. For protocol preparation (1.862 s for MuCPay), native-profile projections place VweTS (NDSS’23) and ParaSwap (USENIX’25) work at 1.67 × 10⁴ and 5.05 × 10⁵ times MuCPay's, respectively. Settlement uses one 64-byte signature, while the modeled independent-DLC deployment requires 281.5× as many transaction vbytes. These results demonstrate practical, scalable multi-party oracle-based conditional payments.

We provide a mathematical introduction to fully homomorphic encryption (FHE), which enables computations to be performed on encrypted data without requiring decryption. We begin with a brief overview of the historical development of FHE, then focus on Fully Homomorphic Encryption over the Torus (TFHE), describing its underlying mathematical structure and fundamental homomorphic operations. Particular attention is given to key switching and bootstrapping, including their roles in managing ciphertext noise and supporting computations of greater depth. Our aim is to provide an accessible mathematical foundation for understanding the mechanisms underlying TFHE and their significance in the development of practical fully homomorphic encryption.

Cryptographic primitives involving multiple participants, such as secure multiparty computation (MPC), threshold signatures, and threshold encryption, are typically designed under the assumption that at least a threshold number of participants remain honest and non-colluding. However, many real-world applications require more expressive access structures beyond simple thresholds. A prominent example is the weighted threshold access structure, where each party is assigned a weight and security holds as long as the total weight of corrupted parties does not exceed a specified threshold. Despite the practical relevance of such access structures, our understanding of efficient constructions supporting them remains limited. For instance, existing approaches for weighted MPC and weighted threshold encryption incur costs that scale with the total assigned weights to all parties or rely on non-black-box use of cryptography. In this work, we present the first black-box constructions of the following weighted cryptosystems with weight-independent complexity in the trusted setup model: (i) a weighted MPC protocol with guaranteed output delivery, (ii) a semi-honest weighted threshold encryption scheme and (iii) a semi-honest weighted threshold Schnorr signature scheme. At the heart of our constructions is a new succinct computational secret sharing scheme with linear homomorphism for weighted threshold access structures. We provide two concrete instantiations of this primitive, based on the Decisional Composite Residuosity (DCR) assumption and the Learning With Errors (LWE) assumption, respectively. Furthermore, our constructions extend to any general access structure that can be represented efficiently as a monotone Boolean circuit.

We study the problem of combating *viral* misinformation campaigns in end-to-end encrypted (E2EE) messaging systems such as WhatsApp. We propose a new notion of Hop Tracking Signatures (HTS) that allows for tracing originators of messages that have been propagated on long forwarding paths (i.e., gone viral), while preserving anonymity of everyone else. We define security for HTS against malicious servers. We present both negative and positive results for HTS: on the one hand, we show that HTS does not admit succinct constructions if tracing and anonymity thresholds differ by exactly one "hop". On the other hand, by allowing for a larger gap between tracing and anonymity thresholds, we can build succinct HTS schemes where the signature size does not grow with the forwarding path. Our positive result relies on streaming algorithms and strong cryptographic assumptions. Prior works on tracing within E2EE messaging systems either do not achieve security against malicious servers or focus only on tracing originators of pre-defined banned content.

The Falcon digital signature scheme, under standardization as FN-DSA, requires real-number arithmetic during signing, with its security dependent on numerical precision. Recently, De Almeida Braga et al. (CRYPTO 2026) showed that Falcon-512 can sign in 64.64 fixed-point arithmetic on 64-bit hosts. In this work, we present the first fixed-point FN-DSA signer for microcontrollers, using 32.64 arithmetic in constant-time Cortex-M4 assembly for Falcon-512 and Falcon-1024. Although a straightforward fixed-point implementation is less precise than double precision, our new techniques successfully restore precision. They keep reciprocals, inverse square roots and small constants wide and round once at the consumer. We evaluate them with known techniques on both arithmetics and both degrees. Our signer needs around $45\%$ fewer cycles than double-precision emulation for Falcon-512 Falcon-1024, and its measured precision supports $2^{99.7}$ $2^{96.7}$ queries per key, against $2^{61.5}$ $2^{58.7}$ for double precision and the target of $2^{64}$. Our $12$-byte words raise signing RAM from $59n$ to $83n$ bytes. We also show which implementation choices lift double-precision c-fn-dsa above $2^{64}$ while making it faster. We derive key generation bounds for Falcon-1024, accepting $72.3\%$ of keys where the Falcon-512 values accept $8.5\%$, and provide recommendations for the fixed-point FN-DSA that NIST plans.

Ring Signatures allow a user to sign on behalf of an ad-hoc set of public keys, while hiding their identity inside that set. Linkable Ring Signatures (LRS) add the functionality of detecting signatures originating from the same signer. They have found many applications in anonymous transactions and e-voting. The LLRing family of linkable ring signature schemes by Hui and Chau (ESORICS 2024) is one of the more efficient LRS schemes. However, we show that it has an unlinkability vulnerability, meaning an adversary can create more unlinkable signatures than the number of secret keys they own. The vulnerability is caused by the introduction of unwanted structure to base elements used in proofs. We also find a similar attack against the Threshold Ring Referral (TRR) scheme of Ta, Hui, and Chau (Security and Privacy 2025), rendering it unsound. We show how to achieve strong linkability with logarithmic verification complexity in the pairing based setting by first reverting the unsafe construction of base elements, and by also adjusting the arguments of knowledge used in order to maintain efficiency. We separate the design and analysis of the scheme from the instantiation of the knowledge arguments, which helps prevent unwanted interactions between the two, and can provide easier upgrades to more efficient proof systems.

Masked-code encryption hides a decodable code behind a transformation meant to make it look random. We study the two masks proposed as compact alternatives to Goppa codes---Wang's RLCE and the $(U\,|\,U{+}V)$ construction of UVW-KEM---over the decodable hidden codes they have been or could be applied to, and find that, among the families examined, none yields a compact trapdoor. Over Reed--Solomon and algebraic-geometry codes the mask hides a \emph{curve}, and curves are not hidden from jets. We explain the October 2026 key recovery of UVW-KEM (NGCC) and show it is not specific to UVW: for \emph{hidden-pairing codes} we bound from below the dependencies among order-$r$ jets of degree-$d$ forms at the columns of any shortening---for cubics $2k_1-k_2-k_l+2$ (UVW) and $2(n{-}k)-w-k_l+2$ (RLCE), attained in every regime tested, and we prove that the structured part of the dependency space carries the pairing and the secret ratios in closed form. Every proposed UVW parameter set has the predicted cubic deficiency (key recovery has been demonstrated at UVW-KEM-128). RLCE's long-key regime $w\ge n-k$, out of reach of the square-code attack for eight years, falls at degree three: on a full-size Level-1 parameter set we recover an equivalent key from the public key alone and decrypt fresh ciphertexts. HermitianRLCE is distinguished the same way. A forcing law, a master count and a redundancy law make the \emph{jet degree} an invariant of hidden-pairing codes: within that model, each unit of structural depth costs a unit of redundancy. Without a curve the masks fail differently: both \emph{preserve the dual} of the hidden code, at most doubling the weight of every dual word. polarRLCE at rate $\le2/3$ leaks dual words found in $47$--$94$ bits; at higher rates no certified decoding radius supports $143$-bit security up to length $16384$, and at $32768$ the key is $58$\,MiB, $234\times$ Classic McEliece. LDPC codes leak their sparse checks, MDPC codes are better left unmasked, and UVW carries a matched-pair subspace for every hidden code. Reed--Muller-heavy codes under RLCE resist every attack here at $4$\,MiB keys, but only if a decoder at $3.4\times$ the bounded-distance radius exists.

In 1997, Mayers, and Lo and Chau, in their papers proved that if one of the parties is malicious, it is not possible to achieve unconditional security in quantum bit-commitment (Phy. Rev. Lett, 1997). Moreover, Lo showed that it is not possible to achieve unconditional security in two-party quantum computation (Phy. Rev. A, 1997). However, restricting the computational power of the adversary, via assumptions like the existence of one-wayness, it has been shown that secure quantum bit-commitment is indeed possible by Dumais, Mayers, and Salvail (EUROCRYPT 2000). In their paper, they showed that with the assumption of a one-way permutation that is secure against any polynomial-time quantum adversary, one can achieve a secure quantum bit-commitment scheme. Although security is guaranteed, complete fairness remains an issue in quantum two-party computation for the real-world framework. In this paper, we show for the first time that secure two-party quantum computation with complete fairness is achievable for the same class of functions as studied by Gordon, Hazay, Katz, and Lindell (STOC 2008) in the classical domain. This seems to stand in sharp contrast to the impossibility result of Ben-Or, Crepeau, Gottesman, Hassidim, and Smith (FOCS 2006). However, they considered a malicious quantum adversary with unconditional computational power and used a broadcast channel. On the other hand, we use the hybrid model idea of Gordon, Hazay, Katz, and Lindell with a non-simultaneous channel and the idea of composition by Ran Canetti (Journal of Cryptology, 2000) to achieve complete fairness in the quantum domain, under the assumption of a computationally bounded adversary. At first, we design secure two-party computation protocols in a hybrid model, using a trusted third party. Then we prove how these protocols achieve complete fairness in the hybrid model. Finally, we construct a secure two-party communication protocol and show how we can use this to remove the trusted third party of the hybrid model and achieve both security and complete fairness in the real-world model. In this context, we devise a zero-knowledge proof and use it as an important tool in our protocol.

Byzantine broadcast and Byzantine agreement are fundamental problems in distributed computing and building blocks for secure multiparty computation. In complete synchronous networks of $n$ parties with channels identifying the immediate sender, classical results establish how authentication changes resilience to $t$ Byzantine faults. Without initially authenticated public keys, both tasks are possible if and only if $n>3t$~\cite{PSL80}. With a complete public-key infrastructure (PKI), broadcast tolerates every $t<n$~\cite{DS83}, and agreement is possible if and only if $n>2t$. These thresholds leave a substantial gap: \emph{how much initial authentication is necessary for a given fault bound, and how does its distribution affect feasibility?} We study this question by allowing each party's designated public verification key to be initially authenticated to any subset of the other parties. We represent this setup by a directed authentication graph $G$ whose vertices are parties, with an edge $x\to y$ exactly when $y$ is a \emph{verifier} of $x$: that is, $x$'s designated public verification key is initially authenticated to $y$. We count each edge as one unit and define \emph{authentication complexity} as the \emph{minimum} total bindings over all setups and protocols achieving the required task and fault tolerance. Protocols may establish further authentication during execution without adding initial cost. We give a tight graph characterization of the initial authentication setups that support agreement, including when each party knows only its own initial key table and is not given the authentication graph. For $2t<n\le3t$ and $r=n-2t$, we show that agreement has authentication complexity $\Theta(\min\{n^2,(n^2/r)\ln(en/r)\})$ and give a protocol with polynomial local computation. At $n=2t+1$, broadcast requires $\Omega(n\ln^2 n/\ln\ln n)$ initial authentications, and has a construction using $O(n^{3/2}\sqrt{\ln n})$ initial authentications. At this threshold, we also show a complete PKI setup is necessary for agreement. Surprisingly, broadcast has subquadratic authentication complexity even when $t=n/2+o(n)$. For every fixed fault fraction $\alpha\in(1/2,1)$, we show its authentication complexity is $\Theta_\alpha(n^2)$. We also determine the exact authentication complexity of broadcast at maximum resilience: $\binom n2-1$ initial authentications suffice and are necessary to tolerate $t=n-1$ faults.

We propose Rotom, a family of 128-bit tweakable block ciphers designed for efficient software implementation on 32-bit microcontrollers. The central design idea is to use modular multiplication as a compact and software-efficient source of strong nonlinearity. Rotom instantiates this idea with a fixed 16-bit S-box built from odd constant multiplication modulo $2^{16}$ interleaved with lightweight linear maps, and combines it with a software-friendly recursive linear layer over four 32-bit words, a compact tweakey schedule, and modular-addition boundary key mixing. In contrast to typical ARX-based ciphers, Rotom provides explicit differential and linear characteristic bounds by design. These bounds are obtained by exhaustively computing the local transition probabilities of its fixed 16-bit S-box and combining them with active-S-box bounds induced by its recursive linear layer. Implementation results on ARM Cortex-M3 and Cortex-M4 show that Rotom achieves cycle counts close to Speck, substantially lower than those of MSX, and faster than representative fixsliced AES implementations, while providing tweak support and cipher-level differential and linear bounds. Overall, Rotom combines the efficiency of software-oriented arithmetic instructions with the explicit security evaluation enabled by a fixed-S-box structure.

Verifiable computation systems often need to prove large matrix multiplication statements, but a direct SNARK arithmetization of a \(k \times k\) product requires \(\mathcal{O}(k^3)\) constraints. Freivalds' randomized check reduces the algebraic computation to vector-matrix products, but proving those products inside a SNARK still costs \(\mathcal{O}(k^2)\) constraints. We present LAMP, a matrix-multiplication checking protocol that combines Freivalds' randomized check with proximity testing over linear error-correcting codes. The prover commits to encoded matrices and intermediate vectors before the sampled query positions are derived. The CP-SNARK circuit then checks only the sampled codeword positions and commits to the values used inside the circuit, while Merkle openings and CP-Link proofs ensure consistency between the in-circuit witnesses and the externally committed values. We prove soundness for this committed-input setting under the soundness of the SNARK backend, the binding of the commitments, the correctness of the CP-Link checks, and the relative distance and unique-decoding radius of the Reed--Solomon code. For a fixed number \(t\) of sampled positions, the main in-circuit SNARK relation has \(\mathcal{O}(tk+E_{\mathsf{code}})\) constraints, with additional \(\mathcal{O}(t\log n)+E_{\mathsf{link}}(k,t)\) backend work for Merkle openings and CP-Link checks. We implement LAMP in Go and compare it with a Freivalds-based SNARK circuit. In the matrix benchmark at \(k=2^{12}\), LAMP reduces the constraint count by \(9.68\times\) and shortens proof generation time by \(5.81\times\); verification remains approximately \(0.13\,\text{s}\) across the measured range.

Side-channel leakage certification aims to quantify what an attacker can learn about a secret variable from observed leakage. Existing information-theoretic estimators, such as perceived information (PI), hypothetical information (HI), and nonparametric mutual information (MI), aim to quantify distributional leakage, but they become unstable in high-dimensional traces and do not provide a finite-sample certificate of the best attacker. We introduce \emph{Bounded Information} (BI), a probably approximately correct (PAC)-style finite-sample certification method that upper-bounds the exact-recovery success of a fixed attacker scope on unseen traces. The attacker suite certificate, $\mathrm{BI}^{\mathrm{suite}}$, applies a KL-binomial confidence interval with a union bound over a fixed suite that contains every trained attacker, preprocessing choice, and hyperparameter. BI therefore turns standard profiled-attack evaluation into an auditable certificate with an explicit attacker scope and confidence level. We further define $\mathrm{BI}^{\mathrm{loc}}(\varepsilon)$ to bound the recovery success of attackers whose normalized scores differ by at most $\varepsilon$ from those of a model in the suite. Across eight side-channel benchmarks with trace dimensions up to $7{,}000$, BI provides stable certificates without density estimation, and its tightness diagnostics tell an evaluator whether a certified value is a genuine measurement of leakage or a conservative bound that more attack traces would tighten.

It is getting widely recognized that quantum computers pose a fundamental threat to blockchain security. The transaction signature transition to Post-quantum cryptography (PQC) is therefore an urgent challenge. However, it remains unclear how much quantum computing power would be sufficient to compromise blockchain security and, consequently, by when the transition should be completed. To address these questions theoretically, we first formalize the signature transition process and the quantum adversary based on the well-known Bitcoin backbone protocol framework. We then establish a threshold for the chain's tolerable quantum adversary capability. Specifically, we prove that a security property \emph{migration liveness} holds with overwhelming probability if $$ \Delta_{\mathrm{eff}} \geq \left\lceil \frac{4}{(1 - \epsilon)f} \right\rceil, \quad\text{and}\quad f \cdot \Delta_{\mathrm{eff}} = \Omega(\log^{2}\kappa) $$ where $\Delta_{\mathrm{eff}}$ is the number of rounds the quantum adversary needs to produce a forged transaction after the broadcast of a migration transaction, $f$ is the honest mining success probability, $\epsilon$ is the concentration quality of the underlying random variables, and $\kappa$ is the security parameter. We further generalize the analysis to derive a relationship between the transition process and the tolerable quantum adversary capability, providing a theoretical basis for designing secure signature transition plans.

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.

In a mercurial signature, a signer signs a representative $m$ of an equivalence class of messages on behalf of a representative $\mathsf{pk}$ of an equivalence class of public keys, receiving the signature $\sigma$. One can then transform $\sigma$ into a signature $\sigma'$ on an equivalent (to $m$) message $m'$ under an equivalent (to $\mathsf{pk}$) public key $\mathsf{pk}'$. Mercurial signatures are helpful in constructing delegatable anonymous credentials (DACs): their privacy properties enable straightforward randomization of a credential chain, hiding the identity of each signer while preserving the authenticity of the overall credential. Unfortunately, without trusted setup, known constructions of mercurial signatures satisfy only a weak form of this privacy property. Specifically, an adversary who is responsible for a link in a delegation chain—and thus knows its corresponding secret key—will be able to recognize this link even after the chain has been randomized. To address this issue, Abe et al. (Asiacrypt 2024) proposed (interactive) threshold mercurial signatures (TMS), which remove the reliance on a single trusted signer by distributing the signing capability among multiple parties, none of whom knows the signing key. However, this contribution was far from practical, as it required the signers to interact with each other during the signing process. In this work, we define and construct the first non-interactive TMS, where each signer computes its partial signature locally, and any $t$ of them combine into an ordinary mercurial signature. This is done using the mercurial signature of Mir et al. (CCS 2023) as a starting point. We also enable the Mir et al. construction to sign its own public keys, a property that is essential for DACs but had been left as an open question. Taking these two contributions together, we build the first non-interactive threshold delegatable anonymous credentials with non-transferable credentials.

Pseudorandom codes (PRCs) combine two seemingly conflicting goals: robustness to noise and computational indistinguishability from random strings. Recent work has shown that classical symmetric-key PRCs over binary alphabets cannot be constructed from minimal cryptographic assumptions, such as one-way functions, via black-box reductions. In this work, we revisit this question in the presence of quantum computation and quantum information. We first consider pseudorandom codes with classical codewords but quantum algorithms. We prove that symmetric-key pseudorandom codes robust to Bernoulli noise admit no black-box construction from quantum random oracles, and hence from quantum-secure one-way functions. This establishes that the classical black-box barrier for PRCs persists even in the quantum computational setting. Motivated by this separation, we investigate the notion of quantum pseudorandom codes (QPRCs), in which codewords are quantum states and security is defined via computational indistinguishability from Haar-random states. We then present several positive results. Assuming quantum-secure one-way functions, we construct QPRCs that are secure against a single encoding query, allow multiple copies of the challenge state, and tolerate an error rate matching that of any classical uniquely decodable binary error-correcting code against a dephasing or bit-flip channel. We also show that the PRFS with proof of destruction due to Behera et al. (TCC 2023) can be extended to a 0-bit QPRC that is secure against multiple encoding queries and tolerates unbounded phase errors but only a constant number of bit-flip errors. Finally, assuming the existence of quantum-secure single-query pseudorandom states (1PRS), we construct single-query single-copy QPRC that tolerate arbitrary Pauli noise up to the decoding radius of a quantum error-correcting code with unique decoding.

Higher-dimensional isogenies have emerged as a powerful building block for isogeny-based cryptography, with recent protocols such as SQIsign relying on the efficient evaluation of $(2^n, 2^n)$-isogenies. Despite their attractive security and compactness properties, these schemes remain computationally expensive and improving their performance is an important step for their real-world use. In this work, we present a high-performance AVX-512 implementation of two-dimensional isogenies that effectively exploits their data-level parallelism. We develop a code generator that produces efficient AVX-512 implementations of arithmetic over $\mathbb{F}_p$ and $\mathbb{F}_{p^2}$ for Montgomery-friendly primes of the form $p=c\cdot 2^e-1$ with $e\approx \log_2(p)$, covering the family of primes used by several protocols based on two-dimensional isogenies, including SQIsign. Building on this arithmetic, we vectorize the $(2^n, 2^n)$-isogeny formulas by Dartois et al. (ASIACRYPT 2024), achieving significant speedups over the corresponding, highly-optimized scalar implementation that uses x86-64 assembly. As an application, we accelerate the Round 2 version of SQIsign verification and obtain speedups of $2.5\times$ at NIST security level I and $3.2\times$ and $3.3\times$ at levels III and V, respectively. Our code generator also readily supports the larger primes of Round 3 SQIsign, for which we obtain verification speedups between $3.1\times$ and $3.4\times$.

Scams and fraudulent robocalls are rampant in the telephone system. Fraudsters often employ call spoofing to impersonate a known caller to the victim, making it difficult to detect and block the fraudster’s calls. In an effort to combat call spoofing, the U.S. government in 2019 mandated the use of a new suite of protocols called STIR/SHAKEN. In STIR/SHAKEN, providers include a cryptographically-signed assertion about the caller’s identity and other metadata in call headers. This serves both to authentically convey this metadata between providers during call routing and to provide reportable, verifiable evidence of bad behavior by providers that originate fraudulent calls. This paper asks whether STIR/SHAKEN achieves its security goals, and at what cost to the telephone system. On security we find serious structural weaknesses: a year of STIR/SHAKEN certificates observed in production call traffic shows a PKI riddled with noncompliance—nearly half of valid certificates violate the specifications—a provider can prevent later verification of a STIR/SHAKEN assertion by taking its certificate offline, and a header-malleability flaw, which we verified in test calls placed with the help of a real telephone provider, causes a spoofed caller ID to be displayed as verified on some phones. The cost, meanwhile, has been steep: STIR/SHAKEN deployment has created systemic new harms to the privacy of all phone users. These new privacy harms take two forms. First, signing call metadata renders it cryptographically non-repudiable: for the first time in the phone system’s 150-year history, there is publicly verifiable proof that a call took place. Second, STIR/SHAKEN’s complexity pushes providers to outsource signing and verification—roughly half of the 29 providers we surveyed do so, most to a handful of dominant vendors—causing widespread new leakage of sensitive call metadata to off-path third parties. (One such off-path third party, Neustar, was acquired in 2021 by TransUnion, one of the three nationwide U.S. credit bureaus. Neustar authenticates over 30 billion calls per month—and TransUnion sells a “Phone Behavior Intelligence” product advertising “insight into billions of call transactions” obtained through its “deep carrier relationships.”) These structural harms sit atop implementation failures: our tests also found implementations that completely break the federally-mandated *67 caller-privacy mechanism. Finally, we propose solutions to the problems we identify. To fix the PKI, STIR/SHAKEN should adopt certificate transparency; a public certificate log also stops providers from taking certificates offline to defeat later verification. Our remaining solutions are cryptographic, and share a prerequisite STIR/SHAKEN cannot currently meet: the origin provider must learn the destination provider’s public key. We thus design a backwards-compatible key discovery mechanism that uses SIP error messages. We then attack the privacy harms directly: replacing STIR/SHAKEN’s signatures with asymmetric message franking (AMF) makes call metadata deniable again, and issuing AMFs blindly keeps it hidden from outsourced signers. We design the first blind signing protocol for the AMF construction of Tyagi et al., along with new security definitions capturing requirements novel to the setting, such as verifier-hiding blindness. To our knowledge, we thereby initiate the formal study of blind signing for designated-verifier signatures; we believe this is of independent interest.

%===================================================================== \begin{abstract} People seeking care for stigmatised conditions often delay treatment because they fear exposure, yet digital health services routinely expose user data and metadata. Fully homomorphic encryption (FHE) now allows smart contracts on public blockchains to hold encrypted data whose decryption is governed by contract rules. This paper assesses whether this approach can protect sensitive medical consultations. We present ConfidentialCare, a prototype built on Zama's fhEVM and the Ethereum Sepolia testnet, in which patients' symptoms are encrypted in the browser and only an authorised doctor may decrypt them. We evaluated three versions of the system through metadata inspection, access-control tests and attack experiments, asking what FHE protects and whether access to patient data can be controlled. Consultation content remained confidential in all tested cases, and the design collects no names, emails or accounts. However, public on-chain metadata revealed which wallet consulted which doctor, the doctor's specialty, when, and the approximate length of each message, and this history would be exposed permanently if the wallet were ever linked to the patient. We also found that a doctor granted access could re-share a patient's encrypted data, both through a confused-deputy flaw in the application contract, which we fixed, and directly through fhEVM's access control list, and that neither withdrawing access nor closing a consultation removed it. A redesign based on time-limited, revocable delegation prevented re-sharing, and Zama's live service enforced its revocation and expiry immediately. On Sepolia, Zama's key-management service refused decryption without a valid delegation, and revocation took effect within the same block in all six trials. We conclude that FHE protects what patients disclose, but not the fact or context of seeking care, and that in fhEVM a permission to decrypt is also a permission to share. \end{abstract}

Quantum computing threatens widely deployed public-key cryptosystems, driving the urgent adoption of post-quantum cryptography (PQC) in cloud and hardware-accelerated security infrastructures. This paper presents \emph{Adams Bridge}, an industry-grade hardware accelerator for lattice-based PQC that integrates ML-KEM and ML-DSA within a unified architecture to maximize hardware reuse and silicon efficiency. The design features a staged, pipelined datapath that exploits multi-level parallelism to accelerate polynomial operations shared by both schemes. An optimized NTT/INTT and point-wise multiplication engine is tightly coupled with a high-throughput Keccak core and efficient hardware sampling, reducing memory overhead and eliminating pipeline stalls. Synthesized in 5\,nm technology and operating at 600\,MHz, Adams Bridge achieves the best reported Area-Time (AT) efficiency among unified designs under an iso-security comparison, improving AT by 1.4$\times$ (ML-KEM) and 2.7$\times$ (ML-DSA) over state-of-the-art architectures. The three phases of ML-DSA complete in 26, 61, and 31~$\mu$s, respectively, while ML-KEM takes 11, 14, and 20~$\mu$s for its corresponding stages. When scaled to 1~GHz, Adams Bridge achieves up to 1.22$\times$ and 2.21$\times$ performance improvements for ML-KEM and ML-DSA, respectively. To address physical attack vectors, the accelerator embeds hardware-level side-channel countermeasures, including masking, shuffling, and constant-time control and arithmetic, mitigating information leakage without compromising performance. Empirical TVLA evaluation up to one million traces confirms the elimination of first-order leakage in critical datapaths. Targeted for deployment within the open-source Caliptra Root of Trust (RoT), Adams Bridge represents the first open-source PQC accelerator under the Apache 2.0 license designed for real-world hardware security systems.

Circuit-based zero-knowledge proofs over large fields waste most of a field element when they commit to a single bit. We study the problem of committing to packed witnesses, in which $m$ bits are stored in one element of $GF(2^m)$, while still allowing the proof system to verify linear claims about the individual bits. Prior approaches to this problem either (a) scale to packing only 4 bits[Fs24], (b) require tensor-structured claims and additional sumcheck rounds that incur larger soundness error [DP23,DP25], or (c) rely on Frobenius automorphisms [Koc26]. In contrast, we present a simpler reduction that exploits only the $GF(2)$-linearity of the field trace and achieves soundness error $2^{-m}$ for arbitrary bit-linear claims. We then use a characterization of trace-zero field elements to make the reduction zero-knowledge over any hiding linear commitment scheme: whereas previous constructions verify $O(m^2)$ or $O(m)$quadratic constraints in the commitment scheme, our protocol requires only linear constraints.

We give provable randomized algorithms for the $\gamma$-approximate Closest Vector Problem ($\gamma$-CVP) with $\gamma=5/3$ and the exact Shortest Vector Problem (SVP) in the Euclidean norm on random $q$-ary lattices. These lattices consist of the integer vectors mapped to zero modulo $q$ by a uniformly random matrix $\mathbf{H}\in(\mathbb{Z}/q\mathbb{Z})^{m\times n}$, for any integer $q\ge2$. For input density $\delta=m\log_2q/n$ with $0\le\delta\le1$, the running times are $2^{0.2668n+o(n)}$ for $5/3$-CVP and $2^{0.2741n+o(n)}$ for exact SVP, with polynomial input-length factors suppressed. For $1<\delta\le3/2$, the respective bounds are $2^{0.56n+o(n)}$ and $2^{0.468n+o(n)}$. For all but a negligible fraction of matrices, both algorithms succeed with overwhelming probability over their internal randomness. Notably, for $0\le\delta\le1$, our provable bounds fall below even the $2^{0.2925n+o(n)}$ heuristic estimate for classical lattice sieving. As a cryptographic application, we prove that signatures in the original construction of Gentry, Peikert, and Vaikuntanathan (GPV) can be forged in time $2^{0.0534n+o(n)}$ for $n\ge5m\log_2q$. For a $128$-bit security target, a leading-term estimate gives $n\approx2400$ and a public key of roughly $144$ kB, indicating a substantial storage burden.

We develop a projective-geometric and algebraic framework for the higher-order polynomial relations among the public generator-matrix columns of a binary Goppa code, the relations exploited by the recent structural distinguishers and key-recovery methods for Classic McEliece. The alternant representation realizes the public columns as rational points on a hidden curve parametrized over $\F_{2^m}$; higher-order vanishing conditions become fat-point conditions, pulled back along the hidden parametrization. Our first contribution is an exact characterization of a codimension-$t$ ambient space containing all products of $d$ code polynomials: the products satisfy $(\pi^dh)'\equiv0\pmod{g^2}$ for the support polynomial $\pi$ and the Goppa polynomial $g$, and the space of degree-$\le dD$ polynomials with this property has dimension $dD+1-t$ once $dD\ge2t-1$. Equality with the actual product space is proved in a local regime, verified computationally on every instance tested, and stated as a conjecture. Our second contribution is a Frobenius-descent theorem: a binary form vanishes on the hidden curve if and only if it vanishes on the union of its $m$ Frobenius conjugates, with the $\F_2$-dimension of such forms equal to the $K$-dimension of the ideal of the union; from it we derive Hilbert-function bounds, including a multilinear version attained on all but one of the twenty-seven keys with $t\ge5$ tested (and missed by one on that key), and the local structure of the pulled-back forms at the roots of $g$. We then analyze the universal dependencies among Hasse-jet conditions in the multilinear setting of the attacks: a closed formula for the rank at a single column, and an explicit family of $\binom{k}{2s-d-2}$ relations between the conditions at any two columns. At a held-out column we prove an exact codimension formula for the Goppa subcode generated by the gradients of the vanishing forms. Finally, running our experimental pipeline (the jet system of the attacks, without the key-recovery steps) on six independently generated keys of a Classic-McEliece-shaped code shows that the kernel dimension is comparable to that of a random control, while every kernel form exhibits the predicted hidden-curve vanishing, the gradients span the predicted subcode, and the first-order normal data of the kernel is nearly independent of the key. Together these results explain the main components of the nuisance space of the recent attacks and isolate the conjectures that remain for an exact description of the kernel.

Stateless post-quantum authenticated key exchanges such as post-quantum WireGuard hedge against unexpected cryptanalytic advances by combining a lattice KEM with code-based Classic McEliece. However, recent attacks have led Germany's BSI to advise against McEliece, which leaves these protocols with lattices alone. HQC, the code-based KEM that NIST selected, could restore diversity, but its keys do not fit in a single packet, so a server would have to buffer multi-packet handshakes. This would leave an attack surface for memory exhaustion, which is what WireGuard's stateless handshake was designed to avoid in the first place. McTiny demonstrated that stateless key encapsulation for Classic McEliece is possible by streaming key blocks one-at-a-time. However, HQC's encapsulation does not split as easily into individual packets, as cyclic polynomial multiplication, unlike matrix-vector multiplication, is inherently non-local. We present HqcLethe, a stateless key exchange that streams an HQC encapsulation in packet-sized pieces. It uses the Chinese remainder theorem to split the polynomial multiplication into independent remainders, one per packet, and masks them so that they reveal no more than an ordinary HQC ciphertext, which we prove in Rocq with SSProve; we also verify session secrecy, server authentication and forward secrecy in ProVerif. Client puzzles bound CPU exhaustion, and HqcLethe removes memory exhaustion: on a Raspberry Pi 3B+, each worker runs in a fixed 1.2-1.6 MiB. At category 5 it sends 27x fewer bytes and uses 9.0x less server CPU than McTiny, the earlier stateless code-based design.

ML-KEM (FIPS 203) is now being deployed in real-world applications to provide security against adversaries with quantum computers. Therefore, the resistance of ML-KEM’s implementations to physical attacks requires thorough evaluation. So far, fault attacks on ML-KEM have targeted the decapsulation operation. The key generation operation has received little attention from a fault-attack perspective. In this work, we present Keyber, the first statistical ineffective fault attack (SIFA) on the key generation of ML-KEM. Keyber is a key-recovery attack that needs only a single fault in key generation. The fault adds a known value to the error vector. Thus, the public key becomes faulty, while the seed of the public matrix remains intact. Every subsequent decapsulation, therefore, carries a known induced error. The adversary encapsulates locally and keeps only ciphertexts whose induced error peaks at exactly one coefficient. A decapsulation failure can then be attributed to that coefficient. Each query yields one linear inequality on the secret key, with no further faults. We observe that approximately 0.2-27% of encapsulations are usable for different parameter sets of ML-KEM. The full secret key is recovered using up to 30,000 inequalities across all security levels. We also realise the attack for ML-KEM-512 on an ARM Cortex-M4 device using a single over-clock fault. We then recover the entire secret key end-to-end. A single fault in this one-time operation thus compromises the key for its entire lifetime. Protecting ML-KEM, therefore, demands hardening not only decapsulation, but also key generation.

We analyze the public values generated by a pairing-based multi-secret sharing construction in which each secret is added to a power of a common pairing value. The secrets lie in the prime subfield of the extension field containing the public values. We show that the first two public values determine the common mask whenever an explicit nonzero condition holds. We also show that the exceptional case is resolved for the parameter set considered in the numerical example. Consequently, the complete public transcript determines every secret, without requiring a participant share or an initially compromised secret. We further describe two related forms of leakage: recovery of all secrets after disclosure of one suitable secret, and a reduction in the possible values of a secret from a single public value. Our conclusions concern the field-valued, common-base masking construction analyzed here; they do not imply that pairing-based secret sharing in general is insecure.

The Number Theoretic Transform (NTT) is the arithmetic core of ML-KEM (FIPS 203) and a prominent side-channel target in hardware. Because the transform is linear, first-order arithmetic masking applies share-wise without fresh randomness, which leaves one design decision open: when each share is processed. Published designs process the shares in sequence on one datapath, or on one datapath per share started a configurable delay apart and in random order; running both datapaths in lock-step is the third option. We implement the three schedules on one first-order masked NTT core for ML-KEM on Artix-7 and measure their cost and pre-silicon leakage under one synthesis flow. An iso-architectural unmasked control separates the cost of masking from that of parallelisation: the delivered lock-step core costs 1.56x the LUTs, 2.33x the slices and twice the DSPs of the control at an unchanged cycle count and 196.1 instead of 227.3 MHz, while the sequential core needs 9 LUTs more than the control at twice the cycles. We state when a set of samples combines both shares of a secret, measure the criterion on the RTL and use it as a cycle-accurate oracle. On a whole-design toggle model that sums both share domains, calibrated with injected flaws detected within 750 traces, no schedule leaks at first order in five pairs of runs of 10^5 traces. At second order the schedules form a scale: the lock-step core leaks in single samples, the sequential core only at the pair of samples that its public offset relates, and the staggered core in both ways at every delay we tested short of one transform. Every detected sample lies in the support view of the oracle, which flags up to 80% of the samples of a window for the univariate test, and some lie outside its form view, so lazy reduction matters. A check on the routed netlist finds no cell shared by the domains of the lock-step and staggered cores, and finds the cells that synthesis shares once the preservation attributes are removed. Silicon validation is left to future work.

Goldreich's pseudorandom generators (PRGs) with constant locality admit highly parallel implementations, yet the concrete security of instantiations based on the $\xor\text{-}\thr$ predicate has remained unclear. In this work, we present novel seed recovery attacks on Goldreich's PRGs instantiated on \(\xor\text{-}\thr\) predicates with $m=n^s$, where $m$ and $n$ are the length of output and input, respectively. By partitioning the output bits into groups according to common input bits, high-biased noisy equations can be derived for the group whose common input bits are all 1s (or all 0s). Leveraging two solvers tailored to these equations, we achieve the seed recovery attacks, which needs roughly $2^{n(1-\log_2{(1 + \frac{2s}{\sqrt{2\pi (b-s)}})})}$ calls to Gaussian elimination when the input length of the $\thr$ predicate $b\geq (n-s)^{1/s}+s-1$ with small stretch $s$. Applying our attack to the asymptotic \(\xor\text{-}\maj\) family proposed in STOC 2016 yields complexity \(2^{\,n\!\left(1-\log_{2}\!\left(1+\sqrt{\frac{s}{18\pi}}\right)\right)} \le 2^{0.82n}\), i.e., at least a \(2^{0.18n}\) speedup over exhaustive search for any stretch \(s>1\). We also deploy our attack on an instance used in the construction of silent oblivious transfer protocols (Eurocrypt 2024) with \(n = 256\). This attack is capable of breaking the instance using approximately \(2^{31.3}\) calls to Gaussian elimination over 244 variables. We successfully implemented the attack on a cluster of 14 CPU cores, recovering the seed in 71 hours, demonstrating the attack's efficiency. Beyond PRGs, with appropriate adaptations our method extends to FiLIP stream ciphers instantiated with $\thr$-related predicates. Our evaluation indicates that most FiLIP instances do not meet their claimed security. For instance, the configuration \(\xor_{100}\text{-}\thr_{11,22}\text{-}\thr_{11,22}\) is broken in about \(2^{59}\) calls to Gaussian elimination over 357 variables despite a 397-bit key and a claimed 80-bit security level.

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

The quaternionic ideal-to-isogeny translation is a central building block of SQIsign. While the Qlapoti algorithm by Borin, Invernizzi, Corte-Real Santos, Eriksen, Mula, Schaeffler and Vercauteren significantly simplified and accelerated this step, it does not treat several technical details in sufficient depth, resulting in a flawed analysis of its failure probability. Additionally, several discrepancies between the implementation of Qlapoti and the paper's pseudocode were never analyzed explicitly. We address these shortcomings and add further improvements, resulting in a new norm equation solving algorithm with negligible failure probability. Our C implementations shows 6x to 9x speedups compared to Qlapoti’s norm equation solver, and 1.3x-2.1x speedups for a SQIsign NIST2 signature (depending on parameter sets).

ChaCha and Salsa are two ARX based stream ciphers which are widely used in data encryption including TLS v1.3 standard, VPN software etc. Exploiting Probabilistic Neutral Bits (PNB) is one of the most significant cryptanalysis strategies for reduced-round versions of these ciphers. The seminal work using PNB by Aumasson et al. (FSE 2008) claims that the PNB set mostly depends on the output bit difference occurring in the intermediate round. The subsequent works mainly relied on the differential or differential-linear cryptanalysis, or multiple distinct input-output differentials for which the bias is higher than a threshold in the intermediate round. In this paper, we propose a new PNB set construction based on multiple output bit differences with respect to a single input bit difference only. We exploit the differentials to mount key recovery attacks using a multi-step procedure depending on our new PNB set. Our attack achieves a time complexity of $2^{167.90}$ for ChaCha20/7 and $2^{183.54}$ for Salsa20/8 in 256-bit versions, beating all the existing PNB-based attacks on ChaCha20/7 and Salsa20/8 by a significant margin. Further, both our time and data complexities for ChaCha20/7.5 are better than the latest published works by Flórez-Gutiérrez and Todo (Eurocrypt 2025 and Asiacrypt 2025). For 128-bit versions, our attack procedure results in a time complexity of $2^{115.24}$ for ChaCha20/6.5 and $2^{98.40}$ for Salsa20/7.5 respectively. We have experimentally validated the underlying independence assumptions across all ciphers, alongside our attack procedure on different reduced-round toy versions of ChaCha.

Classical trapdoor functions recover complete preimages, whereas public-key decryption needs only designated information about an encryption input. We study this distinction through trapdoor hardcore functions (TDHFs), whose trapdoor recovers a prescribed value $h(x)$ from a public evaluation $f (x)$, while $h(x)$ remains pseudorandom given the public key and evaluation. For perfectly correct primitives, we show that adaptive TDHFs characterize IND-CCA2-secure public-key encryption. The constructive direction requires only a single recoverable bit and allows noninjective public evaluations. Extending the rejection-sampling approach, we show that adaptive pseudorandomness itself controls queries to unselected candidate evaluations, without requiring full inversion. We also prove that lossy TDHFs characterize lossy public-key encryption, identifying statistical hiding of the designated recovered value as the relevant lossiness requirement. Fiber samplability together with fiber hiding yields a parameter-preserving correspondence with lossy encryption and, through the known long-message transformation, almost-always lossy trapdoor functions when the recovered-value length exceeds the fiber-sampling randomness length. Ordinary TDHFs provide the corresponding characterization of IND-CPA encryption. Together, these results make explicit the roles of adaptive recovery, conditional sampling, and randomness costs in transformations between public-key encryption and full-inversion primitives.

Public permissionless ledgers are append-only by design, yet are increasingly asked to host data subject to statutory erasure obligations (GDPR Art. 17, EDPB Guidelines 02/2025). The prevailing cryptographic response, redacting the chain itself, needs either a different chaining hash or the cooperation of every node, neither of which a controller on Bitcoin or Ethereum mainnet commands. This SoK systematizes the orthogonal application-layer design space, in which the ledger is left untouched and erasure is achieved by destroying the key material required to read the on-chain bytes. We organise the literature along two axes, data locus (on-chain ciphertext, anchor-only, or hybrid), key custody (single-custodian or threshold), and access gate (none, time, or witness), into a twelve-cell grid with canonical constructions from 1996 to 2026. We extend standard IND-CCA security with a key-lifecycle adversary model parametrised by HSM side-channel leakage, coercion fraction over the custody committee, and algorithmic-break horizon, give the security experiment as pseudo-code with adaptive corruption, cumulative leakage across key rotations, a decryption oracle, and a stronger post-destruction adversary class, and prove that the resulting Destruction-IND-CCA notion suffices for a semantic-security formalisation of the EDPB "render unrecoverable" criterion. We state what is provable per custody model: a concrete bound for single-custodian AEAD, a bound for Shamir threshold custody that grows with the number of rotations, an impossibility result for delay-only designs, and a reduction showing witness-gated erasure needs extractable witness encryption. Evaluating seven reference architectures against eleven engineering, cryptographic, and regulatory criteria, including a production RegTech engine measured at 2.6 × 10^3 events/s single-threaded (10^4 projected with connection pooling), we find that the literature has concentrated on chain-rewriting while the application-layer branch lacks a common threat-model vocabulary. We close this gap and identify five open problems: post-quantum destruction security, the leakage threshold of a custody scheme, decentralised lifecycle audit (with a multi-custody extension covering encrypted mempools), composition with ZKP selective disclosure, and erasure under multi-regime retention conflict.

We study the security of natural ReLU realizations of the Data Encryption Standard (DES) and two-key Triple DES (TDES) when an adversary can submit non-binary inputs and observe selected intermediate neural values. The attack exploits the piecewise-linear extension of XOR: paired inputs that differ in one expanded right-half bit reveal the corresponding round-key bit from the change in a natural XOR node. For DES, the resulting 48-bit first-round subkey leaves only the eight key-schedule bits omitted by PC-2; enumerating these bits and checking an intermediate value recovers the 56-bit effective master key. For two-key EDE TDES, the same technique recovers the first encryption subkey of K_1 and the last DES subkey used by the middle decryption under K_2; two independent 2^8 completions then recover the full 112-bit key pair. The exposed round subkey is recovered with a constant number of leakage observations per bit, giving query complexity linear in the targeted subkey length; the remaining searches are fixed-size for DES. Python experiments report exact recovery for 1,000 random DES keys and 1,000 random two-key TDES key pairs. These results concern a synthetic intermediate-oracle model for natural neural implementations and do not claim a physical attack on conventional DES/TDES hardware or software.

ZKPoSP proves that a public key or address was honestly derived from a hidden wallet seed, without revealing the seed or the private derivation state. This paper studies relationships among several derived values: whether public keys or addresses, possibly on different curves and different blockchains, share a hidden origin, which is the seed or an anchor of the wallet, and who else can recognize this relation. We give a model for such provenance proofs, with derivation proofs, which carry a link value, and provenance proofs, which show that several derivation statements share an origin. We define correctness, derivation soundness, provenance soundness, non-frameability and unlinkability. We give four constructions, which differ in who can link: only the user, with a joint proof or with commitments linked later; anyone within a linking context, with a deterministic tag, which can also act as a nullifier; or a designated authority, with an encryption of that tag. We prove, in sketch form, that the constructions satisfy the five properties under the security of the ZKPoSP derivation relations, the random oracle model, and the zero knowledge and simulation extractability of the proof system. We describe an application to cross-chain transfers from Bitcoin to Solana, in which the payout address must come from the same wallet as the source address, so that an attacker cannot substitute the destination. We report Plonky3 benchmarks of the derivation proofs on which the constructions are built.

Ensuring robustness and liveness in distributed verifiable random functions (DVRFs) allows the protocol to maintain correct operation and guarantee output generation, even in the presence of malicious actors attempting to disrupt the process, delay cryptographic shares, or remain unresponsive. Because existing DVRF protocols typically rely on synchronous or semi-synchronous network assumptions, simultaneously achieving these properties remains a challenge. To address this limitation, this paper enhances the FROST-based Icy-DVRF protocol to achieve both robustness and liveness. Specifically, we propose (R)Icy-DVRF, a novel protocol that operates over an asynchronous network while maintaining a constant-size proof. This is achieved by integrating the ROAST coordination layer into the underlying FROST-based threshold evaluation and proof generation mechanism.

In the digital age, maintaining trust and security in third-party services is crucial, especially when it comes to consent for online actions executed by third parties. This work studies the concept of cryptographically secure digital consent. We provide a protocol which involves a client (the user) and an agent (which executes the action upon receiving consent) with the help of an identity manager (typically: an SSO service and/or a secure device). The client is required to keep no more than a consent password in addition to their existing authentication credentials. The design addresses several security challenges, including non-repudiability of consent. Security is maintained even if either the identity manager or the agent is compromised. Our protocol supports various applications, is compatible with existing identity managers, and is very simple. Our notion of an identity manager is broad, encompassing combinations of different authentication factors such as a password, a smartphone, a security device, biometrics, or national digital identity. We demonstrate applications for signing PDF documents, e-banking, and key recovery. Finally, we implement the PDF signing application, which is robust in the sense that a user can continue to use the signing service even after their devices are broken, lost, or stolen. Hence, an agent can sign on behalf of a user but remains liable for signatures released without consent, which removes a common trust assumption in existing solutions.

We give worst-case algorithms for the shortest vector problem (SVP) and discrete Gaussian sampling (DGS) at arbitrary widths. Both algorithms generate lists on a dense superlattice and combine vectors along a chain down to the input lattice. Random shifts let us control the expected number of representations of a vector regardless of the lattice. For SVP we balance these counts with a novel midpoint-shell test to ensure output distributions are sufficiently uniform. For DGS we use Gaussian weights and correct the probabilities of selecting entries from the final list. For SVP, our optimized algorithm runs in time $2^{0.409 n+o(n)}$ and space $2^{0.259 n+o(n)}$, improving the best $2^{n/2 + o(n)}$ worst-case SVP complexities of Hhan [ePrint, 2026]. For Haar-random lattices, or assuming a natural upper bound on the kissing constant, the costs of the algorithm match the $2^{0.292 n+o(n)}$ time and $2^{0.208 n+o(n)}$ space of Becker-Ducas-Gama-Laarhoven [SODA 2016]. For quantum SVP, through a series of refinements and generalizations we obtain worst-case time and space $2^{0.247n+o(n)}$. This improves the best known heuristic quantum SVP time complexity of $2^{0.256n+o(n)}$ due to Bonnetain-Chailloux-Schrottenloher-Shen [Eurocrypt 2023], without requiring any heuristic assumptions. For discrete Gaussian sampling, we provide a sampling algorithm at any width with distribution error $2^{-\kappa}$, running in worst-case time $2^{0.292 n+o(n)} \operatorname{poly}(\kappa)$ and space $2^{0.208 n+o(n)} \operatorname{poly}(\kappa)$, improving upon the previous best $2^{n + o(n)}$ cost for sampling at arbitrary widths of Aggarwal-Dadush-Regev-Stephens-Davidowitz [STOC 2015]. As further applications, we obtain fast algorithms for approximate-SVP/CVP, bounded distance decoding, and estimating the Gaussian mass and smoothing parameter of any lattice.

We give classical randomized algorithms in a word-RAM model that break the $2^{n/2}$ barrier for both discrete Gaussian sampling (DGS) and the Shortest Vector Problem (SVP). For every fixed $\alpha>1$, shifted DGS on arbitrary lattices at width $\sigma\ge\alpha\eta_{1/2}(L)$ takes $$ (3/2)^{n/2+o(n)}\text{ time} \qquad\text{and}\qquad (4/3)^{n/2+o(n)}\text{ space}. $$ These bounds match the Becker--Ducas--Gama--Laarhoven (BDGL) heuristic sieving exponents. At widths at least $3\eta_{1/2}(L)/2$, the same total cost suffices for an entire batch of $\lfloor(4/3)^{n/2}\rfloor$ samples jointly close to independent target Gaussians. For SVP on arbitrary lattices, our algorithm returns a shortest nonzero vector with high probability in $$ 2^{0.4130n+o(n)}\text{ time} \qquad\text{and}\qquad 2^{0.3138n+o(n)}\text{ space}. $$ As a corollary, we obtain centered DGS at every width with the same exponents, answering a question of Stephens-Davidowitz (SODA 2016). We introduce Gaussian difference dynamics (GDD), a framework for tracking expected counts and pairwise clustering of vectors through repeated differencing. A closed recursion for the first two counting moments controls these quantities relative to a Gaussian reference, without requiring independence within intermediate lists. Accurate moment bounds let us extract a Gaussian sample by weighted selection, while the weaker bounds needed to establish a shortest vector representation allow us to retain more differences. We perform these transitions on thin spherical shells, where the Gaussian rejection weights can be renormalized at subexponential cost. For batch sampling, we combine this geometry with the double rejection technique of Doulgerakis and Laarhoven to control the joint distribution of outputs while reusing vectors.

Error-correcting codes play a central role in modern cryptography, enabling efficient constructions of primitives such as zero knowledge proofs and secure multiparty computations. Among them, repeat-accumulate-accumulate (RAA) codes have recently attracted significant attention due to their linear-time encoding and good distance properties. However, prior work only established provable distance guarantees over the binary field or over finite fields whose size is smaller than the message length. The underlying techniques do not extend to larger fields. This restriction is significant, as many cryptographic constructions based on error-correcting codes operate over large finite fields. In this paper, we prove that RAA codes achieve constant relative distance $0<\delta\le \frac{1}{2}$ with high probability over large finite fields. Moreover, we resolve an open conjecture by showing for the first time that the distance of RAA codes improves over large fields. We provide both theoretical analysis and empirical evidence demonstrating that, compared to the binary case, large fields yield strictly better distance guarantees with much smaller failure probabilities. Our empirical evaluation shows that for message length $n=2^{20}$ and repetition factor $r=4$, the RAA code over a 31-bit prime field achieves relative distance $1/2$, except with failure probability $2^{-20}$. This is better than the best provable distance of $\delta = 0.2$ with failure probability $2^{-10}$ over the binary field. Leveraging our improved distance bounds, we obtain a 2.6$\times$ reduction in the proof size of a polynomial commitment scheme based on RAA codes compared to using the binary-field bound, and a 5.4$\times$ reduction compared to a prior construction based on expand-accumulate codes.

Regular syndrome decoding (RSD) underlies several code-based signature schemes, including SD-in-the-Head (SDitH). Its secret witness has exactly one nonzero coordinate per block, and the selected positions must satisfy a public syndrome equation. In this work, we show how these structural constraints can be exploited to recover the complete witness from imperfect side-channel information. We present a profiled power analysis of the witness-embedding operation in the SDitH Round-3 reference implementation. We train convolutional neural networks (CNNs) to classify the mux digits encoding each regular block and use their outputs to rank candidate positions. To correct errors in these predictions, we combine the resulting rankings with the public syndrome and the regularity constraints. We formulate this recovery problem as an affine correction system with block-validity constraints and analyze its rank, consistency, and uniqueness for the systematic parity-check matrix used in SDitH. Based on this analysis, we develop a quotient-syndrome decoder that identifies blocks whose true positions fall outside the initial candidate lists, avoiding exhaustive enumeration of block subsets. We evaluate our attack on an ARM Cortex-M4 using measured power traces. With a single target trace per key, our approach recovers all 100 test witnesses under -Os using 4,000 profiling traces, and 91 out of 100 under -O3 using 16,000 profiling traces. Each successful recovery matches all 616 serialized witness bits. These results demonstrate how the regular structure of RSD and the public syndrome can compensate for imperfect side-channel predictions, thereby enabling full-witness recovery.

A graph ball query returns all vertices within distance $r$ of a source vertex. On $N$-vertex graphs with maximum degree at most $\Delta$, ordinary breadth-first search answers such queries with $O_{\Delta,r}(1)$ record accesses. These accesses depend on private edges and can reveal graph structure. Full obliviousness hides this dependence, but incurs substantial overhead. Differential obliviousness (DO) [Chan et al., SODA'2019] trades off between privacy and efficiency by relaxing full obliviousness to $(\varepsilon, \delta)$-differential privacy on the access traces of neighboring graphs. We study DO graph ball queries under three widely-adopted edge-level neighboring relations: add/delete, replacement, and $2$-switch. Starting from padded adjacency records, we charge all observable accesses, including preprocessing. For fixed $\Delta,r\ge2$, error probability $0<\beta<1/2$, and $0\le\delta\le(1-2\beta)/2$, we prove an $\Omega_{\Delta,r,\beta}(1+Ne^{-\varepsilon})$ expected lower bound at every sufficiently large connected graph and every public source. For every fixed $r\ge2$, we give $(\varepsilon,0)$-DO sampling algorithms with expected cost $O_{\Delta,r,\beta}(1+Ne^{-\varepsilon/C})$ using constant size of hidden workspace, where $C$ depends only on $\Delta,r$ and the neighboring relation. Especially, for $r=2$, we have $C=1$, which indicates that the algorithm achieves the tight bound under all three relations. Finally, we consider repeated queries on the same graph, where the cost of protected preprocessing can be amortized across queries. For fixed $\Delta,r,\beta$, we construct a linear-size reusable index with $(\varepsilon,0)$-DO preprocessing and constant query cost. The expected preprocessing cost is linear in $N$ when $\varepsilon$ exceeds a sufficiently large constant multiple of $\log N$.

Proof complexity has historically focused on qualitative results, such as whether natural mathematical statements (e.g. the Pigeonhole Principle) admit polynomial-size proofs in certain proof systems (e.g. Resolution or Frege). In contrast to the rich theory of algorithm design, there is little understanding of how to design quantitatively efficient proofs. We initiate the study of fine-grained propositional proof complexity. Our motivation comes from an emerging line of cryptographic constructions such as the elegant work of Jain and Jin (2022), in which the efficiency of the resulting scheme is governed by the size of the underlying Extended Frege proofs. Our main result is that the basic laws of integer arithmetic —commutativity and associativity of addition and of multiplication, together with distributivity — admit Extended Frege proofs of quasi-linear size, when addition is implemented by the schoolbook algorithm and multiplication by an FFT-based algorithm. This seemingly elementary result turns out to be surprisingly non-trivial: the natural paper-and- pencil arguments for distributivity and for associativity of multiplication translate into Extended Frege proofs of quadratic size. To reach quasi-linear size, we develop a technique we call index generalization, which we believe will find wide application in the design of efficient propositional proofs.

The recent guess-type attack (Eurocrypt'26) on Goldreich's pseudorandom generators exploits the strong bias toward constants that can arise when some inputs of majority-based predicates are fixed. This attack has demonstrated substantial effectiveness against several concrete parameter instances (Eurocrypt'24\&'25, Asiacrypt'24). In this paper, we generalize this attack paradigm to arbitrary affine approximations, characterize its capabilities, and develop a new predicate as a countermeasure. We introduce a guess-and-affine-approximation (GAA) attack framework that generalizes existing guess-type attacks from constant approximations to arbitrary affine approximations of residual nonlinear predicates. To characterize the capacity of GAA attack, we introduce the bit-fixing affine advantage $\operatorname{adv}_{b'}(M_b)$, defined as the maximum affine advantage of a $b$-ary nonlinear predicate $M_b$ over all residuals with $b'$ unfixed inputs. For polynomial stretch $m=n^s$ and logarithmic nonlinear arity $b=\gamma\log_2 n$, we obtain the optimal attack complexities $C^\star$ linking bit-fixing affine advantages: (1) $C^\star>2^{cn}$ for every $c<2^{-(s-1)/\gamma}$ iff $\operatorname{adv}_{\theta b}(M_b)\to 0$ for every constant $\theta\in(0,1]$; (2) $C^\star=2^{o(n)}$ iff fixing only $o(b)$ predicate inputs can yield a residual with affine advantage $\frac{1}{2}-o(1)$, and the sufficient direction also holds for $b=\Omega(\log n)$. In particular, if $\operatorname{adv}_{b-r}(M_b) =\frac12- O\left(\frac{\log n}{n}\right)$ for $r\le s-1$, then $C^\star$ can further decrease to $n^{O(1)}$. These results complement prior analyses for arities $O(1)$, $\omega(1)\cap O(\log n)$, and $\Omega(n^{1/s})$. Guided by the results above, we introduce the $\XOR_a$--$\MODtwelve_b$ family as a predicate candidate. We prove that every $b'$-input residual of its nonlinear component retains algebraic degree and algebraic immunity $\Theta(b')$, matching the asymptotic orders of $\MAJ$ (STOC'16). Moreover, its bit-fixing affine advantage is at most $2^{-\Omega(b')}$, whereas $\operatorname{adv}_{\theta b}(\MAJ_b)\approx \frac12$ for every fixed $\theta\in(0,1)$. Analysis shows that, for $n=1024$, $m=n^2$, and $b=54$, $\XOR$--$\MODtwelve$ can achieve $\log C^\star \approx 737$, while $\XOR$--$\MAJ$ and $\XOR$--$\MODthree$ have cost exponents of only $182$ and $599$, respectively, under the specified attack. Furthermore, our experiments show that $\MODtwelve$ offers stronger resistance to belief-propagation-based attacks.

The smoothing parameter $\eta_\varepsilon(\Lambda)$ is a fundamental invariant in lattice-based cryptography. Zheng, Zhao, and Xu (AAECC 2021) proved $\eta_\varepsilon(\mathbb{Z}) \le \sqrt{\ln(\frac{2}{\varepsilon} + \frac{\varepsilon}{44})/\pi}$ and $\eta_\varepsilon(\Lambda) \le \sqrt{\ln(n - 1 + \frac{2n}{\varepsilon})/\pi}\,\mathrm{bl}(\Lambda)$. Guo, Liu, Wang, and Tian (PLOS One 2025) proposed $\eta_\varepsilon(\mathbb{Z}) \le \sqrt{\ln(\frac{2}{\varepsilon} + \frac{\varepsilon}{m})/\pi}$ for $0 < \varepsilon \le \frac{4}{m} - \frac{172}{m^6}$ ($m \ge 3$) and $\eta_\varepsilon(\Lambda) \le \sqrt{\ln((n - 1)(1 + \frac{2}{\varepsilon}))/\pi}\,\mathrm{bl}(\Lambda)$ under $\sqrt{\frac{24n+1}{n^2-1}} \le \varepsilon \le \sqrt{2}-1$. We establish three strictly sharper bounds that uniformly dominate both while removing the artificial lower bound on $\varepsilon$. First, for $0 < \varepsilon \le \rho(\mathbb{Z})-1 \approx 0.086435$, \[ \sqrt{\frac{\ln\!\left(\frac{2}{\varepsilon} + \frac{\varepsilon^2}{4} - \frac{3\varepsilon^5}{32}\right)}{\pi}} < \eta_\varepsilon(\mathbb{Z}) \le \sqrt{\frac{\ln\!\left(\frac{2}{\varepsilon} + \frac{\varepsilon^2}{4}\right)}{\pi}}; \] since Guo et al.'s condition forces $\frac{\varepsilon}{m} > \frac{\varepsilon^2}{4}$, our bound is strictly tighter for all admissible $(\varepsilon, m)$, improving the worst-case gap from $O(\varepsilon^2)$ to $O(\varepsilon^6)$. Second, for all $n \ge 2$ and $0 < \varepsilon < \min\{1, (\rho(\mathbb{Z})-1)n\}$, \[ \eta_\varepsilon(\Lambda) \le \sqrt{\frac{\ln\!\left(\frac{2}{\delta_n} + \frac{\delta_n^2}{4}\right)}{\pi}}\,\mathrm{bl}(\Lambda) < \sqrt{\frac{\ln\!\left(\frac{2n}{\varepsilon} + (n - 1) - \frac{(n^2 - 1)\varepsilon}{6n(1 + \varepsilon)}\right)}{\pi}}\,\mathrm{bl}(\Lambda), \] where $\delta_n = (1+\varepsilon)^{1/n} - 1$; the rational bound is strictly tighter than Guo et al.'s across $100\%$ of their validity window, while remaining valid as $\varepsilon \to 0^+$. Third, for any basis $\mathbf{B}$ with Gram--Schmidt vectors $\mathbf{b}_i^*$ and $M = \max_i \|\mathbf{b}_i^*\|$, define $N_\varepsilon(\mathbf{B}) = \sum_{i=1}^n (\varepsilon/2)^{M^2/\|\mathbf{b}_i^*\|^2 - 1} \in [1, n]$; then \[ \eta_\varepsilon(\Lambda) \le \sqrt{\ln\!\left(\frac{2}{\delta_{\mathrm{eff}}} + \frac{\delta_{\mathrm{eff}}^2}{4}\right)/\pi}\,M, \] where $\delta_{\mathrm{eff}} = \frac{n}{N_\varepsilon(\mathbf{B})}((1+\varepsilon)^{1/n}-1)$. For reduced bases with geometrically decaying Gram--Schmidt lengths, $N_\varepsilon(\mathbf{B}) = O(1)$ is independent of $n$, eliminating the $O(n)$ factor inside the logarithm.

This paper presents the first decentralized multi-authority attribute-based inner product functional encryption (MA-ABIPFE) schemes supporting vectors of a priori unbounded lengths. The notion of AB-IPFE, introduced by Abdalla et al. [ASIACRYPT 2020], combines the access control functionality of attribute-based encryption (ABE) with the possibility of evaluating linear functions on encrypted data. A decentralized MA-ABIPFE defined by Agrawal et al. [TCC 2021] essentially enhances the ABE component of AB-IPFE to the decentralized multi-authority setting where several authorities can independently issue user keys involving attributes under their control. In MA-ABIPFE for unbounded vectors (MA-ABUIPFE), encryptors can encrypt vectors of arbitrary length under access policies of their choice whereas authorities can issue secret keys to users involving attributes under their control and vectors of arbitrary lengths. Decryption works in the same way as for MA-ABIPFE provided the lengths of the vectors within the ciphertext and secret keys match. We present two MA-ABUIPFE schemes supporting access policies realizable by linear secret sharing schemes (LSSS), in the significantly faster prime-order bilinear groups under decisional assumptions based on the target groups which are known to be weaker compared to their counterparts based in the source groups. The proposed schemes demonstrate different trade-offs between versatility and underlying assumptions. The first scheme allows each authority to control a bounded number of attributes and is proven secure under the well-studied decisional bilinear Diffie-Hellman (DBDH) assumption. On the other hand, the second scheme allows authorities to control exponentially many attributes, that is, supports large attribute universe, and is proven secure under a non-interactive q-type variant of the DBDH assumption called L-DBDH, similar to what was used in prior large-universe multi-authority ABE (MA-ABE) construction. When compared with the only known MA-ABIPFE scheme due to Agrawal et al. [TCC 2021], our schemes offer significantly higher efficiency while offering greater flexibility and security under weaker assumptions at the same time. Moreover, unlike Agrawal et al., our schemes can support the appearance of the same attributes within an access policy arbitrarily many times. Since efficiency and practicality is the prime focus of this work, we prove the security of our constructions in the random oracle model against static adversaries similar to prior works on MA-ABE with similar motivations and assumptions. On the technical side, we extend the unbounded IPFE techniques of Dufour-Sans and Pointcheval [ACNS 2019] to the context of MA-ABUIPFE by introducing a novel hash-decomposition technique.

Data availability sampling (DAS) enables a verifier to assess whether an encoded object is available for reconstruction without downloading it in full. Nodes that accumulate partial data additionally require disjoint recovery groups that they can certify and serve independently. We present LR-DAS, which commits to the source-group restrictions of a Tamo-Barg codeword, enabling every verifier to derive each group commitment as a public linear combination of the published commitments. While leveraging a linear derivation analogous to two-dimensional KZG designs, LR-DAS evaluates each derived group on its dedicated coset of a multiplicative subgroup, requiring only one diagonal scaling per group and achieving the optimal Singleton-type minimum distance. In the reference configuration, the minimum distance is $3.91$ times that of the source-compressed product code with the same commitment size, reference string, and local serving interface, and the number of uniform samples required for a light client to detect any fixed unrecoverable withholding pattern with probability $1-2^{-128}$ decreases from $991$ to $218$. The reference string has the degree of the local dimension rather than that of the global polynomial, no Fiat-Shamir transform is used, and a node holding authenticated values at any $r$ distinct positions of a group can produce valid openings for that group without auxiliary data. Against adaptive adversaries, we prove position binding, code binding, and canonicality in the algebraic group model under a discrete-logarithm assumption with auxiliary inputs, and we show by an explicit attack that degree enforcement is necessary.

A long-lived threshold service must issue shares to participants that join after deployment, refresh them against a mobile adversary, and allow participants offline during a refresh to recover missed updates. We show that charging exposure solely to committed epochs is fundamentally insufficient: an aborted refresh attempt that publishes candidate update tokens can reveal the secret even if no committed epoch exceeds its corruption budget. To eliminate this exposure leakage, we index security by fine-grained states covering both committed epochs and aborted attempts. Each state's budget bounds all participants whose local material or public update records originate from that state, enforced via an append-only, durable release ledger that is never rolled back upon abort. A fixed dealer committee anchors encrypted update records in blockchain blob storage, enabling non-interactive recovery for offline participants without contacting dealers, while an interactive bisection dispute protocol deterministically attributes faulty records on chain. Our core cryptographic result is an explicit distribution-preserving shift of the actual generation transcript, establishing proactive secrecy and past-share unforgeability after dealer-state disclosure without idealizing the underlying subprotocols. An end-to-end Rust implementation benchmarks complete lifecycles across up to 1,280 participants on an EVM chain, demonstrating sub-second group recovery and practical gas costs.

We make the ring-switching technique of Diamond and Posen zero knowledge, resolving a problem left open in the literature. Over $\mathbb{F}_{2^n}$, our technique uses $n-1$ auxiliary masks and $n-1$ quadratic constraints, checked in zero knowledge by the underlying commitment scheme.

The stateless hash-based digital signature algorithm (SLH-DSA) repeatedly processes a fixed secret seed with varying public addresses. This paper presents non-profiled correlation power analysis of the address-based pseudorandom function for all six SHA-2 parameter sets, using separate recovery paths through SHA-256 compression rounds and message-schedule expansion. The procedures account for the input layout in which a 22-byte compressed address precedes the secret seed. For the 256-bit sets, a two-stage joint procedure recovers two 16-bit secret portions. We evaluate an STM32F303 ARM Cortex-M4 implementation using 30 secret seeds and 5,000 measured power traces per seed for each evaluated condition. Each recovery stage is evaluated with the required preceding secret values supplied correctly; the reported rates are therefore conditional stage-wise results, not end-to-end seed recovery rates. Compression-round stages achieve 100% success under both forest-of-random-subsets and Winternitz one-time-signature-plus address conditions. Under forest-of-random-subsets addresses, all message-schedule stages achieve 100% success for the 128- and 192-bit sets. For both 256-bit variants, joint recovery achieves 100%, whereas recovery of message word $W_{12}$ achieves 66.7%; recovery of $W_7$ achieves 70.0% and 80.0% for the fast and small variants, respectively. An alternative first stage is also provided for 128-bit Winternitz one-time-signature-plus addresses. These results show that side-channel protection must cover both compression rounds and message-schedule expansion.

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

Many Identity-Based Encryption (IBE) schemes rely on the hardness of the Discrete Logarithm Problem, making them vulnerable to quantum attacks. In recent years, lattice-based cryptography has emerged as a source of Post-Quantum cryptosystems, for example with Kyber, Dilithium and Falcon chosen by NIST to be standardized as ML-KEM, ML-DSA and FN-DSA. Some IBEs have also been proposed over lattices, but they can still be considered as interesting theoretical constructions, the community's attention having been more on the NIST competition than on optimizing IBEs, assessing their security, and protecting them against physical attacks. So, in this paper, we build a new IBE scheme from the basic blocks of the highly studied ML-KEM, ML-DSA and ModFalcon, to put both their maturity and efficiency at the benefits of IBE. More precisely, we leverage the Module-NTRU trapdoor from ModFalcon to enable extraction of secret keys, we use the encryption and decryption algorithms from ML-KEM, and the modular arithmetic and Number-Theoretic Transform from ML-DSA. Therefore, being able to reuse code from widely deployed schemes, our IBE is much easier to implement and maintain in practice, and can benefit from existing (and future) optimizations, hardware accelerators, and side-channel protections, with very little to no additional work. We also prove the IND-sID-CPA-security of our scheme under standard assumptions, and precisely describe the algorithms and the choice of concrete parameters.

In recent years, lattice-based cryptography has proven to be a source of post-quantum cryptosystems. In particular, the blueprint of Learning With Errors (LWE) encryption enabled the creation of Kyber, chosen by NIST to be standardized as ML-KEM. Because of the structure of LWE encryption, the decryption of a ciphertext can give an incorrect plaintext. This event (a decryption failure) happens randomly with some probability. Since this is a problem for both functionality and security, we must ensure that this failure probability is cryptographically negligible. Usually, this is assessed with theoretical approximations and upper-bounds. The authors of Kyber used a Python program to compute that probability more precisely, enabling to fine-tune the compression of the ciphertext, hence reducing its size. However, because of its performances, this program has been limited to Kyber, and all the other schemes are still studied theoretically. In this paper, we design a more efficient Failure Probability Estimator, that we implement in low-level languages (C and CUDA C++), to reach higher parameters used in real schemes based on structured LWE. We illustrate some benefits of our tool with two Identity-Based Encryption schemes. For the first scheme, our tool allows to reduce the size of the ciphertext by about 20%. For the second one, we reduce the failure probability (thus improving security) without impacting the scheme (key size, ciphertext size, etc.).

The hidden number problem (HNP) asks whether a secret can be recovered from partial information about values linked to it by known algebraic relations. In cryptosystems where partial information about secret values or internal randomness is leaked across various scenarios, HNP techniques provide a foundational framework for security analysis and key-recovery attacks. For some HNPs with nonlinear relations, provable polynomial-time recovery guarantees have long remained unimproved, requiring a substantial fraction of the leading bits. We extend the provable recovery ranges for the modular inversion HNP (MIHNP), elliptic curve HNP (EC-HNP), and HNP with hidden multipliers (HNPHM), all modulo a prime $p$. For any sufficiently small constant $\varepsilon > 0$, we increase the tolerable fraction of unrevealed lower bits: for MIHNP, from $1/3-\varepsilon$ to $1/2-\varepsilon$; for EC-HNP, from $1/6-\varepsilon$ to $1/5-\varepsilon$; and for HNPHM, from $1/5-\varepsilon$ to $1/3-\varepsilon$. Our algorithm constructs polynomials that vanish modulo $p$ at the unrevealed lower bits, and reduces recovery to bounding their possible integer quotients by $p$ over the candidate range. While such a search can branch in general, we exploit the algebraic relations of each problem to prove that the expected search cost remains polynomial in $\log p$ over randomly sampled inputs. On every valid input, the algorithm returns the exact set of consistent secrets, achieving unique recovery with probability $1-o(1)$ as $p \to \infty$ for every fixed secret.

Pseudorandomness plays a central role in algorithms, complexity theory, and cryptography. We ask whether deterministic information loss alone can yield post-quantum pseudorandomness with $\mathrm{TC}^0$ evaluation. Learning with errors (LWE) hides linear measurements with random noise. Learning with rounding (LWR) replaces noise with deterministic rounding, but a standard polynomial-modulus hardness reduction requires parameters tailored to a predetermined sample bound. Decisional Diffie–Hellman offers a noiseless algebraic route to pseudorandomness, but its standard instantiations are vulnerable to quantum algorithms. We show that deterministic rounding achieves this under quantum worst-case lattice hardness, with fixed polynomial parameters and no predetermined sample bound. We introduce the learning with algebraic rounding (LAR) assumption, which applies an explicit integer rounding map to blocks of secret-dependent linear measurements and encodes the result in a lattice quotient. For one fixed family with polynomially bounded modulus and dimensions, its deterministic labels on exactly uniform, secret-independent public matrices are computationally indistinguishable from independent uniform labels for every polynomial number of classical random examples. Our classical reduction from Gaussian LWE, combined with the quantum worst-case reduction to LWE, bases LAR on GapSVP and SIVP over general lattices at approximation factor $\widetilde{O}(q)$, where $q$ is the modulus. To prove this, we develop a source-independent affine transport framework that may be of independent interest. Using public affine maps sampled independently of the hidden errors, it transports the Gaussian error law close to uniform on the rounding map’s zero-label fiber while preserving exactly uniform public matrices. For every fixed inverse-polynomial accuracy, we give a polynomial-time sampler for the same public parameter family. This yields the first post-quantum weak pseudorandom function with joint key-and-input evaluation in $\mathrm{TC}^0$, secure against uniform quantum polynomial-time distinguishers given any polynomial number of classical uniform random examples. We also establish the hardness of learning polynomial-size two-hidden-layer ReLU networks from noiseless uniform random examples, even for quantum polynomial-time improper learners.

We introduce a new primitive, called beholder signatures, which, in some sense, are the opposite of blind signatures. In a beholder signature, one signs a commitment to a (potentially very long) message, and the signature attests that the parties participating in the signing process who know the secret key, jointly also know the entire committed message. This guarantee holds even against distributed adversaries that use secure multi-party computation (MPC) to produce the signature. We work in the distributed adversarial model (Dziembowski, Faust, and Lizurej, Crypto'23), where one assumes that it is infeasible to evaluate a large number of hash queries without any of the participating parties learning the input. We propose a construction of beholder signatures in the random oracle model. The starting point of our construction is proofs of complete knowledge, recently proposed by (Kelkar et al. CCS'24), which again build on Fischlin's transformation of a sigma protocol to a noninteractive, straight-line extractable zero-knowledge proof of knowledge. Our scheme is concretely efficient and comes with a proof-of-concept implementation using Schnorr as the underlying sigma protocol. The primary applications of beholder signatures can be found within the blockchain ecosystem. In particular, we describe how to use them to construct proofs of custody (Feist, 2021) that do not require ephemeral keys and are noninteractive. We also outline applications to data dissemination, data availability, and proofs of replication.

Uncertified partially synchronous DAG BFT protocols such as Mysticeti achieve the lowest latency among DAG protocols by omitting per-block quorum certificates, but they lack rigorous liveness proofs: honest parties can desynchronize and never commit a leader again, even under synchrony. To avoid the quadratic communication cost of pushing full blocks, production implementations pull missing ancestors, which results in consensus request amplification, large tail latency, and vulnerability to Byzantine dissemination. We present Starfish, whose new Push pacemaker gives uncertified DAGs their first rigorous liveness proof, together with safety proofs and latency bounds in the actual message delay δ. Starfish makes Push practical by separating payloads from headers: parties push headers and Reed-Solomon fragments, data-availability certificates form on the DAG itself, and worst-case payload communication becomes linear, at the cost of increasing transaction latency by one round. We also show how multi-signatures and delayed history pushes can be applied to Starfish and Mysticeti, resulting in new protocols with quadratic happy-case metadata communication, the lowest among partially synchronous DAG BFTs. Without faults, at 100 validators on a synthetic WAN, Starfish sustains ≈257k tx/s at sub-second median latency against Mysticeti's ≈190k. Controlled experiments show that Byzantine selective dissemination can drive honest-transaction median latency under Pull to tens of seconds in both protocols; under Push dissemination, Starfish holds it within about two seconds across the whole fault range, at substantially lower communication cost than Push on Mysticeti. Starfish has replaced Mysticeti on a public blockchain's mainnet. An observational study comparing each validator with itself across the switch finds per-validator consensus requests down 86% and p99 consensus latency down 27%; well-connected validators pay the added round at +16% consensus latency, and bytes sent per sequenced byte rise by 133%.

Decentralized multi-authority attribute-based encryption (𝖬𝖠-𝖠𝖡𝖤) is a strengthening of standard ciphertext-policy attribute-based encryption so that there is no trusted central authority: any party can become an authority and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters. Essentially, any party can act as an authority for some attribute by creating a public key of its own and issuing private keys to different users that reflect their attributes. This paper presents the first 𝖬𝖠-𝖠𝖡𝖤 proven secure under the standard search variant of bilinear Diffie-Hellman (CBDH) and in the random oracle model. Our scheme supports all access policies captured by 𝖭𝖢1 circuits. All previous constructions were proven secure in the random oracle model and additionally were based on decision assumptions such as the DLIN assumption, non-standard 𝑞-type assumptions, or subspace decision assumptions over composite-order bilinear groups.

This paper introduces Shielded Bitcoin, a protocol for private transfer of Bitcoin directly on the Bitcoin L1, requiring no changes to Bitcoin consensus. Its design borrows from the architecture of Zcash and earlier shielded-note systems: value is held as encrypted notes, spends are marked by public nullifiers, and validity is established by zero-knowledge proofs. Unlike Zcash, Shielded Bitcoin introduces no dedicated consensus chain: all protocol data is published on Bitcoin, transfer validity is enforced through PIPEs v2 [ACG+26], and shielded state is reconstructed by deterministic replay of accepted transfers in Bitcoin order. At the metaprotocol transfer level, Shielded Bitcoin is non-custodial: spending authority remains with user-controlled wallet keys encrypted in a ciphertext, and neither indexers nor the replay layer receive authority to spend user notes. A shielded transfer does not publicly reveal its amount, sender, receiver, and place in the transfer graph, while keeping the validity of every encrypted state transition publicly verifiable. Shielded state, comprising the note tree, nullifier set, and block-level root history, is maintained entirely off-chain: any two correct implementations replaying the same Bitcoin history derive identical protocol state without coordination. The paper defines the transfer model, note structure, ciphertext-derived note leaves, nullifier rules, transaction binding, replay semantics, and publication assumptions. Peg-in and peg-out, the mechanisms by which value enters and exits the shielded transfer system, belong to the broader system and fall outside the scope of this paper.

The development of proof systems whose security relies on the hardness of lattice problems has been a fruitful research area in recent years. By leveraging the techniques introduced in LaBRADOR (Beullens, Seiler, Crypto 2023), the state-of-the-art lattice-based schemes have very fast provers and have output sizes under 100KB for arbitrarily large statements. These proofs are in fact the smallest, and often have the fastest provers, out of all post-quantum schemes. In addition to succinctness, many applications also require witness privacy. Achieving this can, in theory, be done by combining LaBRADOR with a linear-size zero-knowledge proof. While such a combination has already been described in the LaBRADOR paper itself, as well as in the works of Albrecht et al. (Eurocrypt 2024) and del Pino et al. (Crypto 2025), its concrete costs remained unexplored. In this work, we provide the first concrete construction and implementation that adds zero-knowledge proofs to LaBRADOR by integrating the linear-size zero-knowledge proof from (Lyubashevsky, Nguyen, Plançon, Crypto 2022) into the protocol. We describe the non-trivial challenges that this entails and show practicality of the construction by benchmarking several use-cases. We make the proof system and primitives accessible by extending the LaZer library (Lyubashevsky, Seiler, Steuer, CCS 2024) in a way that they can easily be used in other applications.

We determine which major TFNP classes are hard in the random oracle model (ROM). Prior work establishes average-case hardness of highly structured subclasses of TFNP from strong cryptographic assumptions such as LWE and indistinguishability obfuscation. It is not known whether weaker assumptions such as one-way functions imply hardness of any of the standard TFNP subclasses, even in the worst case. The ROM, where all parties have query access to a random function, lies, morally, between these two regimes: a random function is one-way, but public-key cryptography cannot be built from it in a black-box way. We refer to this setting as \emph{Romantica}. Our first result settles a long-standing open problem: PPAD, the class of total search problems reducible to finding a Nash equilibrium, is hard on average in Romantica. Combined with the known hardness of PLS (local search), this gives average-case hardness of EoPL = PPAD \cap PLS. In contrast, we show that UEoPL can be solved in Romantica with polynomially many oracle queries by a computationally unbounded solver, a sharp distinction between EoPL and UEoPL. This resolves the black-box hardness landscape of all major TFNP classes in Romantica. Finally, we initiate the study of separations between TFNP subclasses in Romantica: PWPP and PPA do not reduce to PLS under \emph{public-coin} reductions.

The past several years have seen a rapid rise in practical lattice-based proof systems with linear-sized zero-knowledge proofs forming the foundation of many of the most efficient quantum-safe privacy protocols, and succinct proofs rapidly catching up and surpassing other quantum-safe alternatives in many metrics. A recent comparison of lattice-based aggregate signatures (Ethereum Foundation, 2025) involving the hash-based aggregate signature scheme Plonky3 and the instantiation of aggregate signatures from Falcon from the LaZer lattice library (Lyubashevsky, Seiler, Steuer, CCS 2024) using LaBRADOR (Beullens, Seiler, Crypto 2023), showed that lattice-based constructions have an advantage in terms of proof size and prover time, but are around an order of magnitude slower with regards to verification time. In general, it appears that slower verification times are the main obstacle to the adoption of succinct lattice-based proof systems. In this work, we introduce and implement Orthus, a proof system with sub-linear verification designed for relations that naturally arise in lattice-based constructions. Asymptotically, the verification time grows with the square root of the witness size, and for a concrete example of aggregating Falcon signatures our implementation reduces the verifier running time by a factor of $9X$ when aggregating $2^{17}$ signatures.

In evolving secret sharing, introduced by Komargodski et al., an infinite set of parties share a secret according to an infinite access structure (where minimal qualified sets are finite). In such schemes, par- ties arrive one by one, and and are given a share by the dealer. There is no additional communication incurred to a given party until the time of reconstruction, where share holders who show up combine their shares to reconstruct the secret if they form a qualified set. In this work, we revisit the notion of quantum evolving secret sharing schemes, we dub QESS, where a quantum secret is shared. Smoothly generalizing the above setting runs into difficulties due to the no-cloning theorem. In particular, values handed to previously arriving parties can not be copied by the dealer and used in the evaluation of future parties’ shares, as often done in evolving secret sharing schemes from the liter- ature. Indeed, attempts to formalize quantum evolving secret sharing, such as that on Chaudhury for the so called dynamic threshold setting and by Cohen et al. for general evolving access structures fell short from adhering to the minimally interactive communication pattern above. In this paper, we take a different approach, and consider a setting where several (possibly infinitely many) copies of a secret (known to the dealer) are generated by need. This approach has been used by Cakan et al. for (finite) quantum secret sharing (QSSS), allowing to circumvent the im- possibility of devising QSSS for monotone access structures which are not no-cloning - those that have disjoint pair of qualified sets. This setting is plausible in many applications, where the secret is known to the dealer at sharing time. Cakan et al. demonstrate that at most n copies of the secret prepared by the dealer, suffice to implement any monotone access structure. In the evolving setting, it is not clear how to devise QESS even for evolving no-cloning access structures. Introducing multiple copies of the secret allows to define QESS with a communication pattern similar to the classical setting, in which arbitrary (not necessarily no cloning) evolving access structures can be implemented. using c(t) ≤ t copies of the secret used to generate the shares of the first t parties - similarly to the finite setting. We study the copy number landscape for various evolving access struc- tures. For general access structures, c(t) ≤ t copies of the secret suffice to generate the shares of the first t parties - similarly to the finite setting. On the lower bound side, the no-cloning theorem implies c(t) = t is nec- essary for QESS. The main question we leave open is whether a single copy suffices for no-cloning evolving access structures, while 1 is the ex- act number of the finite setting. We prove that every no-cloning evolving access structure has a QESS with a finite copy number c(t) ≤ C, where the constant C depends on the particular access structure. Furthermore, for every T0, there exists a QESS as above with c(t) ≤ 1 for t ≤ T0. Our techniques generalize the hybrid technique of Cakan et al. abstract- ing their implicit approach of treating the access structure as a union of no-cloning access structures, and implementing each via exiting quantum erasure codes (QECC), which provide not privacy. Then, a copy of the secret, masked by a classical random key (via QOTP) is encoded by each of these codes. The classical keys are then classically shared via each of the access structure to provide privacy. While they rely on a union of no-cloning threshold access structures, we use arbitrary ones. This often reduces the resulting copy number already in the finite setting. Special care is required to share the QOTP keys for each access structure in the union, while keeping every party’s share finite.

We present a polynomial-time quantum algorithm for the Dihedral Coset Problem (DCP). The algorithm is based on Regev's polynomial-time reduction of the Dihedral Subgroup Problem (DSP) to the modular subset sum problem, but uses a different technique to erase sample bits without use of a subset sum oracle. The algorithm can thus combine with Regev's reduction of lattice problems to DCP, improved by Brakerski, Kirshanova, Stehl{\'e} and Wen, to yield polynomial-time quantum algorithms for various lattice problems, such as finding a polynomial-factor approximation to the shortest vector in an $n$-dimensional lattice (SVP), and the ``learning with errors'' problem (LWE). The algorithm can tolerate a faulty sample rate as high as $1/O(\log{n})$, allowing the algorithm-reduction combination to efficiently solve, for example, SVP with a $\sqrt{n}$ polylog($n$) approximation factor, or LWE instances with $\alpha=\sqrt{n}$ polylog($n$). Note: The proof of Lemma 3 in the first draft incorrectly conflated pairwise independence over the uniform vs. actual distribution on D. The proof has been substantially updated, and now distinguishes clearly between them. Additional note: A new preprint, https://eprint.iacr.org/2026/1693, has been posted claiming to prove that the algorithm in this paper can't possibly work. We're in the process of evaluating it. Additional note October 7/26: The preprint has been updated with a note addressing the claims in https://eprint.iacr.org/2026/1693, as well as clarifications to the proof of Lemma 3 in response to comments by Sam Jaques. Additional note November 3/26: The note mentioned above has been updated with edits for greater clarity. The paper has also been reformatted.

\begin{abstract} We present MODDIV-WC, a public-key encryption and key-encapsulation candidate based on a widened Hankel linear map followed by deterministic integer division, together with an implicit-rejection Fujisaki--Okamoto wrapper, MODDIV-WC-FO. The construction uses a secret vector whose first coordinate is fixed to one and whose remaining coordinates are sampled from a positive interval. This unit anchor makes the Hankel map surjective for every admissible secret, a property that is central to the proof. The security analysis has four layers. First, we give an exact embedding of binary-secret LWE into the widened Hankel map using a parity mask that reproduces the MODDIV-WC secret distribution without statistical loss. Second, in an ideal public-key hybrid, a strong leftover-hash argument hides the challenge key. Third, adapting the Renyi-divergence boundary method of prior LWR and MP-LWR work, we prove a transfer lemma for the unit-anchored MODDIV-WC secret distribution. This avoids the earlier requirement that the probability of crossing a rounding boundary be negligible and instead preserves one-way success probabilities with a multiplicative Renyi loss. Fourth, we combine one-way chosen-plaintext security with the implicit-rejection modular Fujisaki--Okamoto analysis of Hofheinz, Hovelmanns, and Kiltz to derive IND-CCA security in the classical random-oracle model. For an explicit asymptotic family, the correctness, Renyi, leftover-hash, binary-secret-LWE, and random-oracle losses are simultaneously negligible, while the source LWE noise remains inverse-polynomial. Together with classical worst-case-to-LWE reductions and the binary-secret/modulus transformations of Brakerski, Langlois, Peikert, Regev, and Stehle, this yields an internally audited candidate route from polynomial-factor worst-case lattice hardness to IND-CCA security. No practical 128-bit parameters, QROM proof, or deployment claim is made. \end{abstract}

The resistance of a block cipher against differential cryptanalysis (DC) is a fundamental criterion for evaluating its security. SPEEDY is a family of low-latency SPS-type block ciphers designed by Leander et al. The designers presented two evaluations of SPEEDY against DC: the first restricted 1-bit-to-1-bit differential propagations through the S-box and used the higher-order branch numbers to estimate the maximum expected differential probability (EDP) of differential trails; the second imposed a structural restriction and assumed that all 1-bit-to-1-bit propagations through an active S-box are possible to estimate the minimum number of active S-boxes. Zhang later exhibited a counterexample to the designers' first evaluation and introduced the notion of partition branch number, relaxing some of the propagation restrictions to allow multi-bit-to-1-bit transitions on some S-box layers and refining the evaluation. However, these evaluations consider only restricted spaces of differential characteristics and therefore inaccurately estimate the security of SPEEDY against DC, which means that the resistance of SPEEDY against DC remains unclear so far. To address this problem, we propose an efficient search method based on search patterns. Unlike previous evaluations, our method imposes no a priori structural restrictions on the allowed differential characteristics; it uses computational pruning to keep the search tractable and performs a conservative security evaluation of the pruned region, thereby providing an accurate evaluation over the global space. At the framework level, we decompose an r-round differential characteristic into an (r-1)-round core trail and an r-round extended trail. By extending a core trail independently at both ends, the two additional S-box layers are handled by two separate models, each containing only one S-box layer and solvable efficiently. At the implementation level, we further introduce a short-round reuse via hash-map concatenation technique, which concatenates short-round core trails to construct longer-round core trails, thereby avoiding expensive long-round MILP models. For 4 rounds, we narrow the minimum number of active S-boxes from the previously reported 35 to [33,34] and find a characteristic with 34 active S-boxes outside the previous search spaces. We also obtain the highest-probability differential characteristics known to date for 2 to 5 rounds. In particular, the 2-, 3-, and 4-round characteristics disprove the designers' branch-number-based security claims. Furthermore, using the quasidifferential framework, we evaluate the found characteristics and obtain several 5-round distinguishers outperforming those used in existing key recovery attacks in terms of EDP. Finally, we optimize the probabilistic extension parameters used in a previous key recovery attack, which yields the best known key recovery attack on SPEEDY-7-192, with data complexity $2^{173.48}$ and time complexity $2^{173.69}$ encryptions.

Anamorphic encryption (AE) enables covert communication in adversarial settings where the receiver’s secret key may be exposed to a coercive adversary. Although existing AE constructions demonstrate the feasibility of this paradigm, their covert bandwidth rates are severely limited, particularly when built from conventional public-key encryption (PKE) schemes. This work develops a systematic approach to constructing bandwidth-efficient anamorphic extensions of residuosity-based PKEs. We first present a robust bit-wise anamorphic extension of the Goldwasser-Micali cryptosystem and a block variant that substantially improves covert throughput. We then construct an anamorphic extension of the Benaloh cryptosystem using an explicit, uniquely decodable embedding of covert messages together with a redundancy tag for robustness. Beyond individual constructions, we introduce a general Δ-structured public-key encryption framework that captures the common algebraic structure enabling anamorphic extensions and instantiate it with block Goldwasser-Micali, Paillier and Damgård-Jurik encryption. We further provide a formal analysis of key deniability, robustness, message loss and windowed decryption, counter-reuse attacks and forward security against subsequent sender coercion. The security of our constructions is established through IND-NA reductions to pseudorandom-function security. At the 128-bit security level, our Benaloh, block Goldwasser-Micali and Paillier constructions achieve approximately 0.46-0.48 covert bits per ciphertext bit under the comparison metric considered, demonstrating a substantial bandwidth improvement over the representative prior approaches. Overall, the proposed framework provides a unified foundation for designing efficient anamorphic extensions of structured public-key encryption schemes.

Secure multi-party computation (MPC) cannot guarantee output delivery, in general, in the dishonest-majority setting. Security of MPC is therefore relaxed to security with abort, where the adversary may prevent honest parties from obtaining their output. The standard notion of \emph{unanimous abort} (UA-MPC) ensures that either all honest parties obtain their output or all of them abort. Goldwasser and Lindell [JCRYPT '05] introduced the relaxed notion of \emph{selective abort}, allowing some honest parties to abort and others to obtain their output. While two-round SA-MPC can be achieved over point-to-point channels, two-round UA-MPC necessitates the second round to be over broadcast. The price of agreement in dishonest-majority MPC is thus tied to the round complexity of broadcast with unanimous abort (UA-broadcast). The round complexity of broadcast has been extensively studied for more than four decades. Garay, Katz, Koo, and Ostrovsky [FOCS '07] (GKKO) proved that the expected round complexity of broadcast protocols tolerating $t$ corruptions is at least $2n/(n-t)-1$. Their argument, however, relies on all honest parties obtaining an honest sender's input, and does not extend to UA-broadcast. Recently, Cohen {\em et al.} [TCC '26] showed that UA-MPC is possible in an expected constant number of rounds when a constant fraction of the parties is honest, and asked whether this extends to $n-o(n)$ corruptions. In this work we answer this question in the negative: Agreement alone already incurs the GKKO barrier. Concretely, we prove that for $t\leq n-2$, UA-broadcast---and hence UA-MPC---requires at least $t/(2(n-t))$ rounds in expectation, matching the asymptotic bound for broadcast without abort. As a corollary, expected-constant-round UA-MPC is possible if and only if a constant fraction of the parties is honest. Next, we consider UA-broadcast protocols that terminate in an {\em a-priori} known round, and show that the bound that the argument of GKKO gives for broadcast holds for them exactly. Combined with the broadcast protocol of Dolev and Strong [SICOMP '83], our bound is tight for arbitrarily many corruptions.

Fixed-versus-random timing tests in the style of dudect are a cheap first check of constant-time behaviour, and on microcontrollers the cycle counter makes them exact to the cycle. We report a pre-registered evaluation of ML-KEM decapsulation on an STM32F411 (Cortex-M4) covering nine implementations of PQM4 (clean, m4fspeed, m4fstack for ML-KEM-512/768/1024) and a positive control in which we restored the pre-KyberSlash division formulas. Each of the 44 campaigns used in the analysis has 100,000 trials and checks every result. With invalid ciphertexts (random bytes, or one modified byte), no difference is detected in 18 of 18 campaigns, and both classes always have exactly the same cycle count, while the control is detected every time (|t| up to 1,877). With fresh valid ciphertexts, however, all nine implementations are flagged, with differences of 4 to 15 cycles and |t| >= 19,000 (or infinite, when both classes have zero variance). A matched control, in which both classes run the same code before the measured call, removes the difference for seven of the nine. An A/A test, in which both classes decapsulate the same bytes, still yields |t| = 12,864 for one implementation. Deterministic few-cycle differences can therefore come from the measurement harness alone: on a part with flash wait states, an instruction cache and prefetching, they can appear when the code around the measured call changes. We also show that per-trial correctness checks matter: they exposed a functional bug in PQM4's ML-KEM-1024 m4fstack (220 wrong shared secrets out of 49,830), which upstream had fixed shortly before. We report every deviation from the pre-registration, including a build error of our own, and publish data, binaries and code (https://doi.org/10.5281/zenodo.23921418).

FRESCO's SPDZ2k suite derives its batched MAC-check coefficients from a setup-time public seed, making the stream predictable before opening shares are sent. We examine this implementation path at a pinned revision. A source-level derivation accounts for low-limb carries and high-bit corrections and shows that the value-share shifts $e=(r_j,-r_i)$ preserve the check residual while retaining the original MAC shares. A message-level harness executes this deviation against unmodified honest opening code. The recorded sum/product outputs violate a relation required for every possible input of the corrupt party, and the test framework records normal completion. The retained evidence includes two-, three-, and four-party executions with dummy preprocessing. The predictable-seed attack template appears in Rushing at SPDZ, and FRESCO's issue tracker recorded the per-check randomness requirement in 2018; our contribution is the SPDZ2k public-seed path, its explicit kernel witness, and the implementation evidence. We also give a conditional single-opening analysis and assess a four-file candidate mitigation that rejects seven recorded tampering scenarios while preserving four honest baselines. Audit tools and descriptive corpora provide context. The proof concerns the specified value-share deviation; unrestricted malicious behavior, production preprocessing, and a complete mitigation argument remain outside the established result.

In 2011 we observed that a single path in the Keccak sponge from a state whose capacity has all zero bits back to such a state yields an explicit, infinite family of second preimages for every message of at least one full rate block. Finding such a path costs about 2^(c/2), which lies "beyond the event horizon" for SHA3-256 (c=512). In this paper we give four novel theorems around that observation. First, the capacity can have any value x: a two-block meet-in-the-middle loop from x back to x, found at heuristic cost about 2*2^(c/2), gives the same unlimited family of second preimages requiring no further search, with connectors to and from x at about the same cost again (Theorem 1). Theorem 2 extends this to k-block loops and to cycles of the capacity map. A single-state bridge, a state S with cap(f(S)) = cap(f^-1(S)), where cap denotes the capacity part of the state, also gives such a family but costs about 2^c. Theorem 3 gives cheap collisions and a bridge-amplified multicollision: one inner collision and one connector yield equal-length Joux-style 2^k-multicollisions for every k, instead of Joux's k collision searches. Building on paths to a given inner state, Theorem 4 uses k bridges on the same capacity value x to give k^L full-state multicollisions of 2L+1 blocks after a prefix to x, for every L, at a fixed heuristic cost of E[T_k] ~ Gamma(k+1/2)/Gamma(k)*sqrt(2*2^c/q) with q=2p(1-p), about sqrt(4k)*2^(c/2) for balanced search (p=1/2), that does not depend on L; a binary Joux construction producing at least as many messages needs about ceil(L*log2(k)) collision searches, each of generic order 2^(c/2). Fixed-cost multicollisions were known for CubeHash, but they use the all-zero fixed state and their messages differ in length; to our knowledge, the k^L count of equal-length messages from k>1 bridges at an arbitrary x is new. It has no impact on SHA3-256. We give verified full-round examples on Keccak-f[200] and on Keccak-f[1600] with c=32, a full-round Keccak-f[1600] bridge with c=80, and a full-round c=80 example from the standard IV: an IV transition and three bridges (2^42.61 calls in total) give 3^3=27 distinct 1710-byte messages with a common digest. The second part of the paper offers novel protocols built on the asymmetry between minting and forging Keccak bridges. They include proof of work with hardness-adaptive capacity, dual-capacity commitments anchored by the real SHA3-256 digest, bridges as zero-knowledge-committed tokens, and a self-enforcing bounty market for reduced-round security. To our knowledge, these are the first unkeyed Keccak-based protocols that deliberately set the capacity so that minting a generic bridge takes a feasible O(2^(c/2)) permutation calls, while the tunable hardness parameter c makes forging a bridge infeasible, since it requires O(2^c) permutation calls. We prove the four theorems, machine-check the stated algebraic results in Lean 4, and provide reproducible experiments and open-source proof-of-concept code. The applications are design proposals whose end-to-end security remains open.

In this paper, we discuss some cryptographic properties of a family of quadrinomials constructed as a generalization of a known family of APN quadrinomials. In particular, we show that this family produces differentially $2^t$-uniform quadrinomials with the same Walsh spectrum as the Gold power function $x^{2^t+1}$ over $\mathbb{F}_{2^n}$. We also discuss whether this family provides permutations.

Asynchronous randomness beacons must preserve agreement and sustain output generation despite Byzantine faults while preventing adversarial bias. We present $\mathsf{AsyRand}$, a publicly verifiable randomness beacon that combines publicly verifiable secret sharing (PVSS) with local-coin asynchronous binary agreement (ABA). Its Producer-Consumer design overlaps PVSS preparation with beacon generation and consumes one accepted PVSS object per output. Column agreement amortizes coordination across multiple outputs. Its look-ahead agreement fixes the successor column's accepted contributions before current contributions are revealed, while recent-contributor exclusion ensures an honest contribution in every $f+1$ consecutive outputs, where $f$ bounds the number of Byzantine parties. Under a production window $\ge2$, every fixed epoch completes with probability one. These mechanisms, together with PVSS secrecy and beacon chaining, provide unpredictability and bias resistance for fixed targets at least $f+1$ epochs ahead. The communication complexity is $O(n^2)$ per output in the optimistic case. We instantiate $\mathsf{AsyRand}$ using ALBATROSS PVSS (Cascudo et al., ASIACRYPT'20) and WaterBear Quadratic-ABA (Zhang et al., Usenix Security'23). Experiments with 16--121 parties across eight regions show that $\mathsf{AsyRand}$ achieves higher throughput than our implementations of GRandLine (Bacho et al., CCS'24) and SPURT (Das et al., S\&P'22). In the fault-free case, at 121 parties, $\mathsf{AsyRand}$ achieves $1.66\times$ and $14.03\times$ their respective throughput.

Leakage-resilient cryptography protects secrets against side-channel attacks, in which a physical implementation reveals partial information about its internal state. A fundamental primitive in this area is a leakage-resilient storage, which allows a secret to be stored in a way that remains secure even if an adversary learns some information about the storage's internal state. A popular approach represents a secret as the inner product of two $n$-bit vectors, called shares. The shares are stored and processed separately by two parts of the implementation, called the left and right parties. Because leakage accumulates over time, the shares must be refreshed repeatedly. We prove that a simple refresh, in which the left party multiplies its share by a uniform invertible matrix $M$ and the right party multiplies its share by $M^{-1}$, is secure under continual local leakage. After $T$ refreshes, each allowing at most $\lambda$ bits of leakage per party, the transcripts for two stored secrets are at statistical distance at most $C\cdot T\cdot 2^{6\lambda-n/9}$ for an absolute constant $C$. We also obtain a Boolean-circuit compiler with statistical privacy error at most $C\cdot S\cdot 2^{18\lambda-n/27}$ for $S$ operations and at most $\lambda$ bits of local leakage per party per operation. The guarantee covers repeated stateful evaluations with adaptively chosen public inputs, with $S$ counting all operations across invocations. Thus, for polynomial-size circuits, a constant leakage fraction is tolerated with share length depending only on the security parameter. We formalize the refreshing bound, the composition and compiler guarantees, and the expected-work bounds in Lean 4. Our results also provide efficient simulation: the leakage can be reproduced from the public inputs and the circuit outputs alone, with expected polynomial overhead.

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.

We generalise a pairing on elliptic curves over finite fields, called the generalised Tate pairing, which is defined in terms of an arbitrary endomorphism of the curve, with certain trace requirements. We rederive this pairing from group cohomology, which allows us to generalise the pairing to principally polarized abelian varieties over any field, endomorphisms of any trace, and prove perfectness using a general duality theorem.

The multivariate Coppersmith algorithm is a central tool in public-key cryptanalysis for finding a small hidden root of modular polynomial equations. It consists of two stages. First, a lattice-reduction (LR) stage constructs auxiliary equations satisfied by the hidden root over $\mathbb Z$. Second, a root-recovery (RR) stage solves these equations. The RR stage can be a bottleneck: auxiliary polynomials may not isolate the root, and solving them can take exponential time in the worst case, even when LR is feasible. We introduce Dual Coppersmith, which replaces algebraic root recovery with geometric recovery from a modular orthogonal lattice. Our construction embeds the hidden root as a short lattice vector, and we prove that LLL recovers its direction whenever a sufficient gap separates it from all independent lattice vectors. The root can then be recovered directly from coordinate ratios. To analyze this gap, we propose a heuristic model for the second successive minimum by examining both the full lattice and a structured sublattice. Under this model, Dual Coppersmith achieves the standard Coppersmith product-size bound without solving an auxiliary polynomial system. Experiments on the approximate common divisor (ACD) and Herrmann-May (HM) problems support the model's predictions and demonstrate root recovery in higher-dimensional instances where the Gröbner-based baseline reaches its timeout.

Learning with Errors (LWE) and its variants underlie many lattice-based cryptosystems, making accurate concrete attack-cost estimates important for parameter selection. Practical primal attacks combine lattice-basis reduction with a final shortest-vector search, and their performance depends strongly on how these components are scheduled. We formalize the two-step strategy space considered in this work and propose PSSearch, a pruning-based method that selects a minimum estimated cost strategy under a specified reduction simulator and cost model. We instantiate the framework with a Pump-and-Jump BKZ (PnJBKZ) simulator supporting jump parameters \(J>1\), practical dimension-for-free settings, and LLL effects, together with a refined estimator for the dimension of the final SVP call. We integrate these components into a practical solver in G6K-GPU-Tensor and compare the PSSearch-selected strategies with its default heuristic strategy under comparable settings. On six TU Darmstadt LWE Challenge instances, the selected strategies achieve speedups of \(7.2\times\)--\(23.4\times\). Under the stated primal-attack and classical gate-count assumptions, the optimized two-step primal estimates for selected ML-KEM and ML-DSA parameter sets are \(3.4\)–\(4.6\) bits below the corresponding previous estimates; relative to the prescribed two-step baseline \(\mathsf{S}_0\), PSSearch provides an additional \(1.2\)–\(1.3\)-bit reduction. Along the tested relation \(\log_2 q=0.198n^{0.832}\), the empirically fitted advantage satisfies \(\Delta(\log_2T)=0.01887n-0.98\), where \(T\) denotes the estimated attack cost. These figures concern the primal-attack branch; the overall attack-cost estimate is determined by the minimum cost among all applicable attack families.

A blockchain that signs every transaction with FIPS 204 ML-DSA-87 keeps 4,627 bytes of signature per transaction forever. We describe and measure an archive certificate: one hash-based proof, for a range of already validated blocks, of knowledge of canonical FIPS 204 signatures on exactly the recorded messages under the keys resolved from chain state. Fresh blocks keep native verification. The construction starts from an exact bounded relation for ML-DSA-87 verification once the high bits $u = w_1'$ are fixed. The main certificate keeps $u$ hidden and proves the SHAKE256 challenge hash inside the proof, by a GKR argument for Keccak-f[1600] over the same WHIR commitment as the lattice relation. For 65,536 signatures we measured 104.09 bytes per signature in a Johnson-regime family, which has a classical bound only, and 126.89 in a unique-decoding family, against 4,627 bytes raw. The price is a slow prover and a verifier slower than native verification. At $2^{64}$ queries and $2^{20}$ verification submissions, conditional on cited Reed–Solomon proximity theorems, the classical random-oracle extraction error is below $2^{-188.07}$ for the Johnson family and below $2^{-201.99}$ for unique decoding. In the quantum random oracle model we state, for the unique-decoding family only, an extraction-failure bound below $2^{-129.67}$ at $2^{64}$ quantum queries; it is not a work factor. An external review is outstanding, so certificate-only bootstrap stays disabled.

Fault injection attacks have been extensively studied in the context of post-quantum cryptography, yet existing analyses on code-based KEMs largely focus on faults targeting the Fujisaki-Okamoto transform. This work presents new fault injection attacks against BIKE and HQC that operate beyond this commonly protected component and target less obvious instructions within the decapsulation process. The proposed attacks achieve full key recovery using only valid ciphertexts under NIST Level 1 parameters, requiring 17392 and approximately 3 million decapsulation queries for HQC and BIKE, respectively. In addition, we introduce a general approach to identify effective fault locations by analyzing decoder behavior under perturbed conditions. The attacks are experimentally validated on an STM32H7 microcontroller using laser fault injection, demonstrating high repeatability. These results reveal a broader attack surface and provide a foundation for more efficient fault attack analyses in future work.

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. We further show that the distributional mismatch identified in the claimed RLWE hardness reduction does not constitute a cryptanalytic attack. In fact, the CRT-encoded error distribution under the intended parameters admits an exact, invertible transformation to ordinary RLWE with an explicitly characterized non-degenerate ternary error law.

Leakage-tolerant multi-party computation (MPC) ensures that leakage from each honest party’s internal state reveals no more than the leakage from honest parties' individual inputs and outputs, beyond the standard security guarantee of MPC. Previous constructions either require a leakage-free preprocessing, or rely on indistinguishability obfuscation in the common reference string (CRS) model and only achieve semi-honest security. In the computational setting, assuming only an augmented non-committing encryption scheme, we show that every adaptively well-formed functionality admits a semi-honest leakage-tolerant MPC protocol, without any leakage-free preprocessing execution or CRS. Under the decisional Diffie–Hellman assumption, we further extend this result to malicious security in the CRS model for all deterministic functionalities. The limitation of deterministic functions is subject to an impossibility result of leakage-based coin-tossing protocols. In the information-theoretic setting, we show that secure erasure enables statistically secure leakage-tolerant MPC of arbitrary functionalities assuming strictly less than half of the participants are maliciously corrupted. We complement this construction with an impossibility result: without secure erasure, general-purpose statistically secure leakage-tolerant MPC with leakage-oblivious simulation, an important property to enable universal composition, is impossible in the plain model, even when all parties are honest. As a further application, we also obtain information-theoretic leakage-tolerant circuits against bounded communication leakage, while all prior works are restricted only to the weaker variant of leakage-resilient circuits.

Although module lattices possess richer algebraic structure than general lattices, their algorithmic benefits for exact shortest and closest vector problems (SVP and CVP) remain relatively unexplored. For general $N$-dimensional lattices, the fastest known polynomial-space algorithms take $N^{\Theta(N)}$ time, whereas known $2^{O(N)}$-time algorithms require exponential space. We investigate how the algebraic structure of modules over number fields can be exploited to obtain faster exact algorithms in polynomial space. We develop a common framework based on reduced module flags and lattice-point enumeration in Euclidean balls, with two complementary approaches. The first uses recursive subfield descent, yielding deterministic $2^{O(N)}$-time algorithms for both SVP and CVP on fixed-rank modules over totally real or CM fields with bounded root discriminant and bounded-degree subfield chains. Infinite unramified class field towers provide families of unbounded dimension satisfying these conditions. The second approach reduces lattice-point enumeration in Euclidean balls to exact SVP, without requiring a subfield chain or any bound on the root discriminant. For fixed-rank modules with root discriminant $\rho=d^{o(1)}$, where $d$ is the field degree, this reduction yields deterministic SVP and CVP algorithms in time $d^{d/(2\mathrm e)+o(d)}$. Furthermore, the second approach yields exact CVP algorithms for semistable lattices, including cyclotomic ideal lattices, without any restriction on the root discriminant. The resulting running times are $N^{N/(2\mathrm e)+o(N)}$ deterministically and $N^{N/(4\mathrm e)+o(N)}$ with randomization. While the two approaches above initially focus on fixed-rank modules, we further extend both to modules of growing rank. In particular, for modules of rank $\Theta(\log N)$ over fields with bounded root discriminant, we obtain deterministic SVP and CVP algorithms in times $(\log N)^{N/(2\mathrm e)+o(N)}$ and $(\log N)^{N/2+o(N)}$, respectively.

Fair leader election is the problem of sampling an unbiased random party out of a set of $n$ parties. The seminal impossibility result of Cleve (STOC 1986) applies to this setting, and shows that the result of the election cannot be unbiased against a dishonest majority. Recent work has achieved the weaker property of game-theoretic fairness, where behaving dishonestly cannot improve one’s chances of being elected. However, such protocols allow even a single corrupt party to bias the outcome. In this work, we introduce best-of-both-worlds (BoBW) fairness, where a small number $t_S$ of corrupt parties cannot bias the result, and even a larger number $t_{GT}$ of corrupt parties still cannot improve their collective election chances (CSP-fairness) nor hurt the election chances of any given honest party (MM-fairness). We present a protocol for BoBW fair leader election for $t_S + t_{GT} < n$. We then prove a generalization of Cleve’s impossibility, and show that this protocol is optimal. Next, in the setting of statistical security we find that BoBW fairness is uninteresting, as it is only possible for an honest majority, where we can get also unbiased leader election. Finally, in the setting of perfect security, we present a BoBW protocol achieving CSP-fairness and strong fairness for $t_S + 1 = t_{CSP} = \frac{n}{3}$, and prove that this is also optimal.

At FSE'15, Mennink introduced the concept of designing beyond-birthday bound secure tweakable block cipher from an ideal block cipher. They proposed two tweakable block ciphers $\widetilde{F}[1]$ and $\widetilde{F}[2]$ that accept $n$-bit tweaks using a block cipher with an $n$-bit key and $n$-bit data. Mennink proved that the constructions achieve security up to $2^{2n/3}$ and $2^n$ queries, respectively, assuming the underlying block cipher is ideal. Later, at ASIACRYPT'16, Wang et al. proposed a class of $32$ new tweakable block ciphers derived from $n$-bit ideal block ciphers that achieve optimal security, i.e., security up to $2^n$ queries. The proposed designs by both Mennink and Wang et al. admit only $n$-bit tweaks. In FSE'23, Shen and Standaert proposed a tweakable block cipher $\widetilde{G}2$ that accepts $2n$-bit tweaks and achieves security up to $2^n$ queries. Their construction uses three block cipher calls, which was shown to be optimal for beyond-birthday-bound secure tweakable block ciphers accepting $2n$-bit tweaks. In this paper, we extend this line of research by considering the design of tweakable block ciphers that support $3n$-bit tweaks from an ideal block cipher with affine mixing. First, we show that there is a generic birthday-bound distinguishing attack on any such design with three block cipher calls if any of the block cipher keys are tweak-independent. We then propose a tweakable block cipher $\widetilde{\textsf{G}}3^*$, which leverages three block cipher calls with each key being dependent on the tweak. We demonstrate that $\widetilde{\textsf{G}}3^*$ achieve security up to $2^{2n/3}$ queries. Although primarily of theoretical interest, $\widetilde{\textsf{G}}3^*$ demonstrates that beyond-birthday-bound security for a $3n$-bit tweak can be achieved with only three block-cipher calls, thereby extending the known feasibility frontier for TBC design.Furthermore, we extend this result and propose an optimally secure construction, dubbed $\widetilde{\textsf{G}}3$, that uses four ideal block cipher calls with only one tweak-dependent key. Finally, we generalize this and propose an optimally secure tweakable block cipher $\widetilde{\textsf{G}}r$ that processes $rn$-bit tweaks using $(r+1)$ block cipher invocations with only one tweak-dependent block cipher key. Our experimental evaluation demonstrates that on platforms featuring AES-NI hardware acceleration, \tx{ZMAC} instantiated with $\widetilde{\textsf{G}}_3$ and $\widetilde{\textsf{G}}_4$ (i.e., $\widetilde{\textsf{G}}_r$ with $r=4$) outperforms all existing ideal-cipher-based TBC candidates.

This work provides a systematic study of parameter separation in Block Korkine–Zolotarev (BKZ) reduction. We propose a general framework with separate parameters for outer propagation and the dominant local computation. The framework covers the local parameter settings of standard BKZ and variants using extended preprocessing, dimensions for free, or progressive sieving, with corresponding adaptations to the outer operations. This allows less expensive local processing without narrowing the outer propagation range. Within this framework, we give idealized and executable constructions that use inner BKZ with a smaller blocksize to supply local vectors for larger outer blocks. We derive a worst-case quality bound for the idealized construction and analyze its quality–cost behavior using a practical fixed-point model. Experiments on the executable construction cover random q-ary bases up to dimension 300 and SVP Challenge bases up to dimension 240. The detailed comparisons at n ≥ 200 show lower mean root-Hermite factors (RHFs) and 14.1%–59.3% shorter mean running times than BKZ 2.0. Joint improvements generally become more frequent with dimension. On q-ary inputs against BKZ 2.0 with blocksize 50, their frequency increases from 15.56% at n = 150 to 73.33% at n = 300.