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.

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.

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.

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.

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.

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.

An asymmetric Password-Authenticated Key Exchange (aPAKE) protocol allows a client and a server to agree upon a cryptographic key, with the only information shared in advance being a low-entropy password (memorized by the client) and a corresponding password file (stored in the server). The standard security definition for aPAKE is in the Universally Composable (UC) framework. Since aPAKE does not rely on a PKI, such protocols have received much attention in recent years due to their potential of replacing the traditional “password-over-TLS” approach for client-server authentication on the Internet. One of the only two aPAKE protocols currently deployed in practice is Secure Remote Password (SRP) (Wu, NDSS 1998), which is used by millions of users on the Internet. A formal security analysis of SRP has long been elusive; the only security proof to date is the one by Dayanikli and Lehmann (CSF 2024) which is in a (somewhat non-standard) variant of UC called UC with angels. This framework allows the simulator access to an additional oracle that solves certain hard cryptographic problems. In this work, we present a comprehensive new analysis of SRP, and clarify a number of ambiguities about its security: 1. We formally prove that the SRP is UC-secure if and only if one computational problem in the field is hard and one decisional problem is easy. As the decisional problem is likely hard in the field, this strongly suggests that SRP is not UC-secure and hence justifies the usage of UC with angels in the security analysis; 2. On the other hand, we show that the “angel” given to the simulator in the Dayanikli–Lehmann analysis is stronger than necessary, and can be replaced by a weaker oracle; 3. Finally, we prove that UC-with-angels-security is still stronger than the game-based security for aPAKE, i.e., SRP is still game-based secure under some reasonable assumptions. Overall, we pinpoint the exact conditions under which SRP can be proven secure, reducing its security to a number of underlying hardness problems. Along the way we also identify and bridge multiple gaps in the Dayanikli–Lehmann analysis — most notably, the concrete security bound — and apply novel proof techniques that might find application in other contexts.

We consider the fundamental problem of designing classical consensus-related distributed abstractions for large-scale networks, where the number of parties can be huge. Specifically, we consider tasks such as Byzantine Agreement, Broadcast, and Committee Election, and our goal is to design scalable protocols in the sense that each honest party processes and sends a number of bits which is sub-linear in $n$, the total number of parties. In this work, we construct the first such scalable protocols for all of the above tasks. In our protocols, each party processes and sends $\tilde O (\sqrt n)$ bits throughout $\tilde O (1)$ rounds of communication, and correctness is guaranteed for at most $1/3-\epsilon$ fraction of static byzantine corruptions for every constant $\epsilon>0$ (in the full information model). All previous protocols for the considered agreement tasks were non-scalable, either because the communication complexity was linear or because the computational complexity was super polynomial. We complement our result with a matching lower bound showing that any Byzantine Agreement protocol must have $\Omega(\sqrt n)$ complexity in our model. Previously, the state of the art was the well-known $\tilde\Omega(\sqrt[3]{n})$ lower bound of Holtby, Kapron, and King (Distributed Computing, 2008).

We present two seed-recovery attacks on a family of local PRGs, which map an $n$-bit random seed to an $m$-bit pseudorandom string by applying $\XorMaj$ predicates. For PRGs with large locality, we extend the Group-and-Solve (GAS, Eurocrypt 26) framework to Guess-Filter-Solve (GFS). GFS first guesses that a set of seed bits are all $1$s and then filters for outputs whose inputs to $\Maj$ contain a sufficiently large subset of the guessed bits. Then high-bias noisy equations can be collected for the correct guess and solved by specific solvers. Compared with GAS, GFS collects substantially more noisy equations with high bias and hence outperforms GAS significantly, especially when the output is short. For example, when the proposed asymptotic XOR-MAJ family (STOC 16) is instantiated with $n=256$ and $m=2^{16}$, the complexity for GFS is $2^{68.78}$ while it is $2^{157.91}$ for GAS. In addition, the asymptotic complexity of GFS is $2^{0.15n+o(n)}$. Independently, inspired by the Guess-and-Decode (GADec, TIT 22), we propose the Filter-Guess-Propagate (FGP) attack. Compared with GADec, FGP introduces two speed-up techniques at each iteration of Belief Propagation (BP): a filter scheme to reduce the number of equations and a dynamic-programming technique to update the log-likelihood ratios of variables efficiently. Together, these improvements enable FGP to perform fast BP and outperform GADec significantly. For $\XorMaj_{10,64}$ with $n=256$ and $m=2^{40}$ (Eurocrypt 24), the total complexity of FGP is $2^{52.66}$, whereas even a single BP iteration of GADec costs $2^{106.42}$. We further extend FGP to $\XorMod$ predicates and experimentally evaluate the resulting attack complexity. We also apply FGP to a ZKP protocol from Eurocrypt 25 and QuietOT from Asiacrypt 24, with only a small computational overhead. For the ZKP protocol, FGP leads to an attack on witness indistinguishability, while for QuietOT, it similarly yields an attack on OT receiver privacy.

Bosley and Dodis (TCC 2007) proved that a class of imperfect randomness sources that suffices for information-theoretic encryption of messages longer than the logarithm of the key length must admit deterministic extraction of nearly uniform bits, and asked whether the same is true of two-out-of-two secret sharing. Aggarwal, Chung, Obremski, and Ribeiro (TCC 2022) gave a positive answer for schemes that are in addition leakage-resilient or non-malleable; the original question remained open. We answer it in the negative. For every $b\ge2$ we construct a class of flat sources on $\{0,1\}^{b+2}$, each of min-entropy at least $b$, together with a perfectly correct and perfectly private two-out-of-two scheme that shares a $b$-bit secret into two $(b+1)$-bit shares using any source in the class, and we show that every deterministic map from $\{0,1\}^{b+2}$ to $\{0,1\}$ is at statistical distance at least $1/6$ from uniform on some source in the class. This implies that sharing a long enough secret does not require extractable randomness. The proof is a short parity argument. The idea of the construction extends to other thresholds: for two-out-of-$n$ and $r$-out-of-$r$ sharing we give perfect schemes with $(b+1)$-bit shares, private for classes of flat sources from which no single bit can be extracted with error below $1/(4n-2)$ and $1/(2(2^r-1))$, respectively.

List decoding Reed–Solomon codes is a central problem in coding theory and, together with mutual correlated agreement (MCA), underpins the soundness of many succinct cryptographic proofs. In this work, we give precise quantitative bounds on Reed–Solomon list decoding and MCA up to capacity, provide deterministic decoding algorithms that remain efficient over cryptographically large fields, and specialize our bounds to reduce proof sizes in implemented proof systems. Our bounds apply to arbitrary prescribed evaluation domains; beyond Johnson, they require sufficiently large field characteristic. Refining the hidden-derivative method of Brakensiek, Chen, Putterman, Zhang, and Zheng, we obtain an explicit agreement threshold $a_1(\rho)$ strictly below the Johnson bound $\sqrt{\rho}$, using only the first derivative, without requiring its evaluations in the received word. At agreement $a_1(\rho)+\eta_1$, where $\eta_1>0$, our sharper interpolation and candidate counts give list size $O_\rho(n/\eta_1^2)$ and MCA error $O_\rho(n^2/(q\eta_1^4))$ for codes of length $n$ over $\mathbb{F}_q$. Higher derivatives give explicit quantitative bounds up to capacity, uniformly over all rates, sharpening prior MCA results in Zheng's unpublished manuscript and Jeronimo's work, concurrent with ours. At fixed rate, for agreement gap $\eta_0>0$ above Johnson, we improve the MCA error bound of Ben-Sasson et al. (BCHKS) from $O_\rho(n/(q\eta_0^5))$ to $O_\rho(n/(q\eta_0^3))$, in every characteristic. Our decoders determine the values of the message and its derivatives at a point from the agreements with the received word, rather than enumerating them over the field as earlier hidden-derivative decoders do. With fast explicit field arithmetic, at fixed rate and a fixed positive gap above the respective threshold, deterministic decoding takes $\widetilde{O}(n\log q)$ bit operations above Johnson in every characteristic and $\widetilde{O}(n^3\log q)$ above our first-order curve in sufficiently large characteristic. Decoding remains polynomial in $n$ and $\log q$ at every fixed positive gap from capacity, under the same requirement of sufficiently large characteristic. Our first-derivative bounds give the first proof-size reductions in existing proof-system implementations from provable Reed–Solomon proximity-gap bounds beyond the Johnson radius. Relative to the deployed parameters and at unchanged security targets, we save 79.4 KB (11.1%) for ProveKit passport proofs, 13.2 KB (4.63%) for ZisK compressed final proofs, and 59.8 KB (4.85%) for LambdaVM CPU subproofs. We have formally verified the list-decoding and MCA bounds and concrete parameters in ArkLib, a Lean library for verified cryptographic proofs.

Many hash-based proof systems check that committed words are close to Reed–Solomon codewords by testing one random combination of them. Their soundness analysis uses a *proximity gap*: if the combination agrees with a codeword on many positions, so do the original words, on the same positions, except for a few *exceptional* challenges. Such gaps are known above the Johnson threshold, about $\sqrt\rho$ for rate $\rho$, and extending them below it would shrink proofs. Recent work does so in large characteristic, but not for the additive domains used over binary fields, where some of the fastest proof systems run. We show that on these domains, beyond-Johnson proximity gaps fail. Our first construction applies to any additive domain (a linear subspace) filling a constant fraction of a containing binary field, such as the length-$2^{27}$ domain of Binius64. Over a suitable extension challenge field and at rate $1/4$, it gives two words that can simultaneously match codewords on at most $25\%$ of the positions, while their combinations approach the $50\%$ Johnson threshold for superpolynomially many challenges. This rules out any $\mathrm{poly}(N)/|\mathbb F|$ bound on the exceptional probability below Johnson. The construction also rules out polynomial-size decoding lists below Johnson: one word agrees with superpolynomially many codewords at agreement approaching $50\%$. Earlier superpolynomial lists needed the rate, or the agreement–rate gap, to vanish. Our second and third constructions cover every additive domain, including the sparse domains used by LeanVM and Flock. At rate $1/16$, the second gives $(N-1)(N-2)/6$ exceptional challenges at the Johnson threshold itself, when the domain lies in a proper subfield of the challenge field. The third construction trades agreement for larger exception counts: at rate $1/2$ and length $2^{22}$, its combinations reach $53.125\%$ agreement from common agreement $50\%$, with probability at least $2^{-20}$ over a $192$-bit challenge field. Finally, at every fixed rate, some constant agreement above the rate makes every challenge exceptional, over $\mathrm{poly}(N)$-size challenge fields. All of our results are formally verified in Lean.

Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zkSNARKs) are becoming an increasingly fundamental tool in many real-world applications where the proof compactness is of the utmost importance, including blockchains. A proof of security for SNARKs in the Universal Composability (UC) framework (Canetti, FOCS'01) would rule out devastating malleability attacks. To retain security of SNARKs in the UC model, one must show their simulation-extractability such that the knowledge extractor is both black-box and straight-line, which would imply that proofs generated by honest provers are non-malleable. However, existing simulation-extractability results on SNARKs either lack some of these properties, or alternatively have to sacrifice witness succinctness to prove UC security. In this paper, we provide a compiler lifting any simulation-extractable NIZKAoK into a UC-secure one in the global random oracle model, importantly, while preserving the same level of witness succinctness. Combining this with existing zkSNARKs, we achieve, to the best of our knowledge, the first zkSNARKs simultaneously achieving UC-security and constant sized proofs.

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, rewriting the chain via chameleon hashes and redactable-blockchain constructions, is structurally unavailable on Bitcoin and Ethereum mainnet. 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.

FrodoKEM is a post-quantum key encapsulation mechanism based on plain Learning With Errors (LWE). In contrast to module-lattice-based schemes, it relies on an unstructured variant of the LWE problem, providing more conservative and better-understood security guarantees. In this paper, we explore hardware-level parallelization of FrodoKEM's matrix multiplication, which dominates its execution time. Earlier high-throughput work by Howe et al. identified SHAKE as a performance bottleneck and replaced it with the Trivium stream cipher, which renders the implementation incompatible with the FrodoKEM specification. In contrast, our work adheres strictly to the specification, including its use of SHAKE as the PRNG, and introduces a parameterized architecture whose degree of parallelism is set by design-time parameters. We present operation-specific datapaths for FrodoKEM-640 on Artix-7 with 24 parallel multipliers for key generation and 32 for encapsulation and decapsulation, achieving 976-1077 operations per second, i.e., latencies of 0.93-1.02 ms. Among the earlier specification-compliant designs, this is the lowest latency and the lowest area-time product. The design shows that SHAKE is not a barrier to parallel matrix multiplication and that efficient, standard-compliant FrodoKEM implementations are practical for high-speed cryptographic applications.

This work presents two main contributions to the analysis and design of Ligero-style zero-knowledge proof systems. First, we analyze the original Ligero IOP in the list-decoding regime and show that mutual correlated agreement suffices to obtain improved soundness guarantees and lower query complexity, without modifying the protocol. Second, we propose a new variant of Ligero that incorporates out-of-domain sampling, leading to further soundness improvements and enabling Reed--Solomon code rates above $1/2$. The new protocol preserves the constant-round structure of the Ligero IOP and its compatibility with memory-efficient proving, while achieving perfect honest-verifier zero knowledge.

Succinct arguments are central cryptographic objects, underlying various applications such as blockchains and image authentication. Almost all succinct arguments used in practice follow the commit-and-open paradigm introduced by Kilian (STOC 1992): commit to a probabilistic proof, then open the few locations the verifier queries. Decades of work have generalized and optimized this paradigm, yet its exact provable security in the standard model remains unclear. Existing analyses proceed by rewinding, and they leave gaps: strict-time analyses lose an inverse-polynomial factor, while expected-time analyses are sharper but apply only to special cases of this paradigm. We resolve both gaps. On the negative side, we show that the strict-time loss is inherent: no strict polynomial-time reduction relying on a black-box extractor can achieve negligible knowledge error (unless the underlying language is easy). On the positive side, we give a new expected-time analysis, achieving negligible soundness and knowledge errors via an expected polynomial-time reduction against expected polynomial-time adversaries, at the full generality of the paradigm, capturing multi-round and functional variants such as polynomial and linear IOPs compiled with the corresponding commitments. This is the first standard-model analysis to reach this regime for succinct arguments deployed in practice.

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

Quantum discrete logarithms on genus-two Jacobians require reversible arithmetic with controlled workspace. Generic divisor-addition formulas apply only outside an exceptional set, which must be accounted for in quantum phase computation. We give a randomized reduction using two fresh independent uniform public seeds in a finite abelian group of odd order to randomize a complete balanced addition tree. For inputs independent of the seeds, exceptional-pair densities bound the averaged phase-channel error and sampling failure probability. We apply this reduction to an odd-prime-order subgroup of a genus-two Jacobian over $\mathbb{F}_q$, where $q$ is an odd prime and the supplied curve model is a square-free monic quintic with zero quartic coefficient. Integer lifting, an independently shifted Legendre phase, and streaming Chinese remainder reconstruction yield a low-space sampler. For subgroup order $r=\Theta(q^2)$, the useful-sample probability is $1-\mathcal{O}(L/q)$, averaged over fresh seeds, for an exact uniform input state and ideal Fourier readout, where $L$ is the number of tree leaves. With window width $w=\Theta(\log_2 n)$, the sampler uses $10n+o(n)$ logical qubits, including both scalar registers, with $n=\lceil\log_2q\rceil$, and allows intermediate measurements, reset, and classical feedforward. For the Gaudry--Schost instance over $\mathbb{F}_{2^{127}-1}$, a $16$-bit window gives an analytic allocation of $1{,}971$ qubits and a capped-run Toffoli bound below $2^{60.561}$. A matched schedule derived from Chen et al.'s addition module uses $3{,}063$ qubits; both schedules retain the same $500$ scalar-input qubits. These comparisons are schedule-specific, and rotation synthesis is counted separately.

Lattice-based homomorphic e-voting protocols built on commitments, such as EVOLVE, keep ballots private against all but one authority and the tally verifiable even if all authorities collude, but need every authority to tally. We present T-EVOLVE, in which votes are Shamir-shared over the commitment message space: any t of n authorities that took part in the checking phase complete the tally, privacy holds against t-1 colluding authorities and verifiability against all. The voter proves that her committed shares form a Reed-Solomon codeword whose value at zero is a valid vote; the parity checks cost no communication, and tallying interpolates public column sums without norm growth. Complaints of authorities, including about ciphertexts that do not decrypt, are publicly verifiable given encryption with publicly verifiable opening, which we define and instantiate under LWE. We prove privacy, verifiability, individual verifiability and robustness in the classical random oracle model; the verifiability reduction is not tight and the parameters rest on classical hardness estimates. In our C implementation, a yes/no ballot for four authorities takes 109 KB without signatures, or 147 KB with the computed seed ciphertexts, and an authority aggregates 10^4 ballots in about three minutes per successful tally round on one core.

We introduce the Add/XNOR decision problem: given $n$ words of $n$ bits, decide whether they can be combined into zero by a left-associative chain in which each operator is either addition modulo $2^n$ or bitwise XNOR. We prove NP-completeness by a deterministic reduction from Subset-Sum{} in which four-bit guard fields and a parity normalization force every gadget to be all-additions or all-XNORs; hardness persists for every width that is a fixed rational power of the operand count, and 3-SAT reduces with linear parameter blow-up. The problem is a minimal model of Boolean--arithmetic mixing, and we give an exact theory of its linear and differential behaviour: a carry decomposition, closed forms for every single-bit linear correlation (for addition runs $z_1,\ldots,z_r$ the bit-$1$ correlation is $\prod_j2^{-z_j/2}\cos(z_j\pi/4)$, averaging exactly $(n+1)2^{-n}$), and an exact transposition differential with collision probability $2(5/8)^{m-1}-2^{-(m-1)}$, all confirmed experimentally. Both operations are triangular, which yields a low-bit dissection algorithm with worst-case time $\Ostar(2^{n/2})$ and space $\Ostar(2^{n/4})$ plus an explicit balance parameter; no technique we know of improves the exponent $1/2$. We explain why the representation technique that recently broke the $2^{n/2}$ barrier for Subset-Sum{} is not available to the natural formulation of non-commutative chains, report that CDCL solvers scale as roughly $2^{0.7n}$ in our experiments, and prove in an ideal chain model, where each operation is an independent random permutation, that planted search requires $\Omega(2^{(n-1)/2})$ oracle queries. We place the problem in the current fine-grained landscape, in which the 3SUM, APSP and (strong) exponential time hypotheses have been refuted: the conditional lower bound that the 3-SAT reduction would otherwise yield is void, and the exponential complexity of Add/XNOR is open in both directions.

The FROST threshold signature scheme achieves round optimal Schnorr signing through a double-nonce construction, but requires two presignatures per signature. Since each presignature demands an expensive distributed key generation (DKG) protocol, this overhead is significant for high-throughput applications. FROST builds on a core presignature protocol (that we call FROST-core) that uses hash-based re-randomization of presignatures. We investigate whether fewer presignatures can be used to sign multiple messages, improving FROST-core's \emph{message capacity}. We first show that the natural generalization of using $k$ presignatures for $k$ messages is insecure: an extended ROS attack enables forgery even for $k=2$. However, we prove that using $k+1$ presignatures for $k$ messages achieves security in the Generic Group Model combined with the Random Oracle Model. This improves message capacity from 50\% (standard FROST-core) to $\frac{k}{k+1}$, approaching 100\% as $k$ grows. We further extend our analysis to a modified FROST-core protocol in which a set of presignatures is generated by different parties and used for signing $k$ messages. Security holds as long as at least $k+1$ presignatures were created by honest parties. Update: We found a non-trivial ROS attack on our protocol by using AI tools. We plan to publish the attack and a proposed fix in the future. The proposed protocol in the current paper with $k+1$ presignatures for $k$ signatures is forgeable. We retain the article as is for reference.

Anonymity guarantees of privacy-oriented cryptocurrencies are garnering negative attention from lawmakers who view them as antinomic to accountability. Having recognized their potential for innovation, however, regulators may not want to outright ban privacy coins but instead seek a middle ground where financial oversight is effective, and still some privacy is maintained. Mature designs, such as Zcash, Monero, or Firo, are expected to facilitate this through so-called viewing keys that can be disclosed to third parties for the purpose of supervision. This paper studies which privacy guarantees continue to hold once they have been. In doing so, it fills the gap in provable anonymity guarantees for Zcash and Firo under the compromise of the incoming viewing key, but nevertheless shows that malicious parties may happily surrender all their viewing keys and still find very efficient ways of evading financial monitoring. Of independent interest are several shortcomings identified in the prevailing security arguments for Monero.

Hiding a genuine message among plausible decoys is a recurring principle in cryptography and privacy, underlying honeywords, symmetric encryption, and anonymous data collection. We study the information-theoretic security of mechanisms that release a uniformly shuffled sequence containing one genuine message and $n-1$ decoys over a $d$-symbol alphabet. We characterize how restrictions on decoy generation determine achievable secrecy. We distinguish four classes of decoy mechanisms: i.i.d., heterogeneous independent, correlated message-oblivious, and message-dependent. For every fixed $d\ge2$, the optimal worst-case mutual information over message priors is $\Theta_d(n^{-1})$ for both independent classes and $\Theta_d(n^{-2})$ for correlated message-oblivious mechanisms. A discrete spectral construction achieves the latter rate without knowledge of the prior. Message-dependent mechanisms achieve perfect secrecy when $n\ge d$. Moreover, even with $n=3$, heterogeneous decoys can improve upon i.i.d.\ decoys by an arbitrarily large multiplicative factor. These results quantify the distinct benefits of heterogeneity, correlation, and dependence on the genuine message. A key-symmetrization reduction shows that every perfectly correct symmetric encryption scheme with a key drawn uniformly from a key space of size $n$ admits a message-dependent shuffle construction without increasing plaintext leakage. This connects optimal message secrecy to preimage-constrained channel design and yields an exact characterization of key leakage for all message-leakage-optimal ciphers when the number of keys does not exceed the plaintext support size. For canonical mechanisms, whose decoys are drawn i.i.d.\ from a blanket distribution $Q$ independently of the genuine message, a unified likelihood-ratio representation yields exact expressions for mutual information, total-variation information, message recovery advantage, and expected posterior variance, together with explicit finite-sample remainder bounds for the mutual-information expansion. For a fixed non-degenerate message prior $P$, the leading asymptotic coefficient of message mutual information is minimized by $Q^*(y)\propto\sqrt{P(y)(1-P(y))}$, which generally differs from $P$. For binary alphabets, quasi-uniform blankets exactly minimize message total-variation information for every $n\ge2$, independently of the prior.

Higher-Order Spearman Coefficient Analysis (HO-SPA) is of particular interest in non-profiling Side-Channel Attacks (SCA) due to its effectiveness against monotonic nonlinear leakage. However, the optimal form, effective order combinations, and performance of HO-SPA (or its variants) remain underexplored. This work systematically revisits HO-SPA in the presence of Boolean Masking (BM) and Inner Product Masking (IPM). Specifically, we propose a new variant of HO-SPA, called HO-ASPA (Higher-Order Adjusted Spearman Coefficient Analysis), and derive the optimal form of HO-ASPA for two-share BM and IPM across a wide range of order combinations under the Hamming weight (HW) leakage model. We first derive the optimal form of HO-ASPA by extending the Spearman Coefficient Analysis to higher-order moments, while preserving the centered-product combination of the share leakages. We then establish an upper bound on the maximal correlation induced by the rank transformation and characterize the relationship between the signal-to-noise ratio and the optimal correlation coefficient in the rank-domain, and extend these analyses to IPM. To enable a fair comparison, we also derive the optimal forms of Higher-Order Correlation Power Analysis (HO-CPA) and HO-ASPA for both BM and IPM under the Least-Significant-Bit (LSB) leakage model. Our analysis highlights a key distinction: unlike HO-CPA, where higher orders often outperform the lowest feasible order, HO-ASPA shows no significant performance gap between higher-order and lower-order attacks. Moreover, under the HW leakage model, our HO-ASPA not only aligns with existing results and succeeds in counteracting the security order amplification, but also significantly outperforms Kruskal-Wallis Analysis (KWA)-based attacks at various order combinations. We further validate the effectiveness of the proposed HO-ASPA through simulated and real-world experimental evaluations.

Anamorphic Encryption (Persiano, Phan and Yung, Eurocrypt '22) allows private communication in a challenging setting where encryption is severely controlled by a central authority (henceforth the dictator) who can demand the users to surrender their secret keys. Anamorphic Signatures (AS) (Kutylowski, Persiano, Phan, Yung, Zawada, Crypto '23) face the even more restrictive world where only authentication is allowed but users still want to send secret messages despite the repressive control of the dictator holding their signing key. Several constructions have been proposed so far, but they all come with some limitations. We propose a new flexible setting where digital signatures are used to covertly embed secret shares that $t$ out of $N$ designated receivers can combine to recover a covert secret. We formalize this new primitive called Anamorphic Secret Sharing Signatures (ASSS) together with new robustness, forward/backward secrecy, and private unforgeability notions and we give a construction for Schnorr-like signatures overcoming the limitations of previous constructions. ASSS additionally imply (regular single-receiver) AS, but two signatures (instead of one) are needed to recover the covert message.

Multiple concurrent proposer (MCP) protocols let several parties contribute transactions to the same ledger update. They can distribute communication and reduce one proposer's control over inclusion and order, but these benefits depend on how the contributions are combined. We describe a common architecture from transaction receipt through proposal formation, agreement, data recovery, ordering, execution, and state finality. Within it, we identify four direct MCP families: fixed proposal vectors, selected proposal collections, persistent proposal streams, and causal proposal DAGs. We compare them with constrained assembly, where several parties restrict a block assembled by one party. Across 39 configurations, we distinguish agreement and progress from service for a particular transaction, and compare hiding, ordering, communication, throughput, and latency at explicitly named endpoints. The comparison shows why additional proposers alone do not guarantee inclusion, why hiding does not settle who can react last, and why parallel disseminations need not improve useful execution. It also identifies the recovery, payment, and organizational assumptions needed to turn independent proposal rights into reliable transaction service.

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

AI agents increasingly pay for Web services on behalf of their users to complete complex tasks. Such a task needs many payments, and the user usually must approve each one, forcing the agent to stop at every payment. Mechanisms such as the Agent Payments Protocol (AP2) therefore enable the user to sign one payment mandate in advance that bounds the agent's payments for the task. However, whoever checks the mandate can learn the task, which is often sensitive. Specifically, (1) the user's wallet can see the full mandate when it checks each payment, so it can trace every payment to the task; and (2) although each merchant sees only the payment it receives, it verifies that payment under a signing key that repeats across the task, so colluding merchants can link the payments and reconstruct the task. We present MinMandate, a task-hiding payment authorization system for AI agents in which the user approves a task-bounded payment mandate once. In MinMandate, the wallet checks each payment through a constant-size keyed-verification policy credential, which reveals neither what the mandate allows nor which mandate the payment comes from. Each merchant then accepts the wallet's one-time ticket as proof of payment and never sees the mandate or its signing key. Formally, we prove authorization soundness and unlinkability in our threat model. Our experiments show that the overhead of MinMandate is practical, with a payment taking 197 ms and under half of AP2's bytes. Notably, MinMandate cuts wallet-side tracing from every payment under AP2 to the level of random guessing. Moreover, from their own payment-request records alone, colluding merchants can reconstruct the user's task in 47% of the cases under AP2 but in only 8% under MinMandate.

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

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

IND-CPA-D security is an extension of IND-CPA security introduced in the context of Fully Homomorphic Encryption (FHE). It captures the situation where the computation result is known to the adversary; it is in particular necessary for FHE with threshold decryption. This work presents three new attacks in this situation on the BFV and BGV FHE schemes, when their parameters are instantiated with heuristic assumptions commonly used to enable correctness. We first extend the \emph{bootstrapping failure attacks} from Cheon \emph{et al.} [CCS'24] on the DM/CGGI and CKKS schemes, to both BFV and BGV. We focus on BGV when instantiated with the so-called powerful-basis representation of ring elements. The second attack relies on \emph{skewing the ciphertext noise} in BFV, making it outpace the heuristic noise bounds for plaintext-ciphertext multiplications. This is achieved by crafting plaintexts, for which the noise bounds do not hold. The third and last attack focuses on outpacing the noise growth in BFV ciphertext-ciphertext multiplications. For this purpose, we \emph{skew the mask} part of the ciphertext by selecting a random encryption of zero, whose addition yields a ciphertext with a sufficiently large mask norm. While the first two attacks successfully recover the secret key, the last attack instead breaks the IND-CPA-D indistinguishability game. We report experiments on all these attacks, based on the HElib and OpenFHE libraries, respectively, for BGV and BFV. Notably, the second attack implemented in OpenFHE fully recovers the secret key in a few minutes to a few hours, depending on the parameters.

REAMC Report-007(2023) [Reissued October 2026 with modified licence CC BY-NC-ND; no other changes] ACORN-QRE: Specification and Analysis of a Method of Generating Secure One-time Pads for Use in Encryption Roy S Wikramaratna (email: [email protected]) Abstract The Additive Congruential Random Number (ACORN) generator is straightforward to implement; it has been demonstrated in previous papers to give rise to sequences with long period which can be proven from theoretical considerations to approximate to being uniform in up to k dimensions (for any given k). The ACORN-QRE algorithm is a straightforward modification of ACORN which effectively avoids the linearity of the original algorithm, while preserving the uniformity of the modified sequence. It provides a new method for generating one-time pads that are resistant to attack either by current computers or by future computing developments, including quantum computers. The pads can use any alphabet (including both binary and alphanumeric) and can be used with a Vernam-type cypher to securely encrypt both files and communications. This report explains how the ACORN-QRE algorithm works and provides evidence for the claim that the resulting one-time pads are inherently not susceptible to cryptanalysis and that they will remain secure against foreseeable developments in computing, including the potential development of quantum computers. The ACORN-QRE algorithm is patented in the UK under Patent No. GB2591467; patent applied for in the US under Application No. 17/795632. The patents are owned by REAMC Limited, 4 Nuthatch Close, Poole, Dorset BH17 7XR, United Kingdom

Security evaluation of masking in low-noise regimes remains poorly understood: increasing the masking order does not automatically translate into higher concrete resistance once many correlated intermediates are processed by a full implementation. A common approach is to reduce noisy side-channel leakage to the random probing model (RPM), but existing reductions can be too loose to yield meaningful leakage rates in practice, and current RPM analyses often rely on costly simulations or numerically propagated bounds. This work develops analytic and algorithmic tools for estimating and upper-bounding RPM security of masked gadgets and their compositions. First, for noisy Hamming-weight leakage over $\mathbb{F}_{2^u}$ we compute concrete RPM leakage-rate parameters for a tighter $\mathbb{F}_2$-linear reduction based on binary inner products, providing a tangible link between SNR and probing rate. Second, for $\mathbb{F}_q$-linear circuits we leverage a vector-space representation to characterize RPM leakage as an erasure event, yielding a direct connection to local metrics such as advantage and implying global simulability for refreshed, block-separated executions. Third, we improve Monte Carlo estimation of rare leakage events using importance sampling, enabling evaluation in low-rate/high-order regimes that are infeasible with naive sampling. Finally, we revisit the leakage-diagram technique and derive explicit bounds for refresh gadgets, and we apply the same viewpoint to composition through \emph{bridges}, showing that SNI—while sufficient for threshold probing model (TPM)—does not capture the RPM phenomenon governing refresh boundaries. We implement our methods in \textsf{LAPSE}, a tool that compiles gadget descriptions into linear-algebraic representations and supports exact computation as well as Monte Carlo/importance-sampling estimation of RPM security parameters.

Cryptographic accumulators based on groups of unknown order (GUO) provide constant-size set membership proofs. For security purposes, existing works require first encoding set elements via division-intractable (DI) hash functions, typically instantiated as random oracles that destroy any algebraic structure. This confines GUO-based accumulators to a purely set-membership role, making them "incompatible" with various existing cryptographic proof techniques over committed integers in the same groups as the GUO, such as constant-size proofs of exponentiation and modular exponent relations. We introduce the notion of morphic accumulators, which replaces the DI hash with a discrete logarithm encoding $H_g(x) = g^x$, mapping set elements to a group before accumulation. We prove, under a variant of the subset product assumption in the generic group model, that this encoding is inherently division intractable, achieving the same security guarantee as random-oracle DI hashes, while simultaneously being a group homomorphism: accumulated elements retain their group-algebraic relationships. This resolves a fundamental tension between compact representation and algebraic structure: the accumulator serves simultaneously as a binding commitment to a set and as a substrate for homomorphic computation over its elements. Morphic accumulators yield asymptotically optimal constructions across multiple domains: range proofs with $O(n)$ prover time, $O(1)$ proof size, $O(1)$ verification with transparent setups (the first scheme to simultaneously achieve these optimal bounds); polynomial commitments with $O(n)$ prover and $O(1)$ proof size, resolving the cubic bottleneck in prior constant-proof-size GUO-based schemes; and the first linkable ring signatures with $O(1)$ signature size, transparent setup, $O(n)$ offline signing and $O(1)$ online signing.

This paper studies how local leakages characterize the global leakage in additive secret sharing over a finite abelian group, which is a special case of linear secret sharing and side-channel masking. Our main finding is structural: local-to-global leakage is governed by two disjoint components---the magnitude of local leakage and its spectral alignment across shares, while existing literature attempted to characterize the global leakage only by local mutual information (MI). We first give an exact decomposition of leakage in additive secret sharing. The decomposition reveals a structural parameter invisible to MI, while previous literature conjectured that the local MI alone suffices to characterize global leakage. We then show that this missing parameter is indispensable: two leakage channels with identical local MI can induce exponentially different global leakage. Our exact decomposition identifies the missing structural quantity and completely characterizes this phenomenon. We then show the separation theorem with its realizability---local MI, despite governing the classical leakage bounds, does not even determine the exponential rate at which leakage vanishes under homomorphic composition. More strongly, we establish a universal separation theorem: even when all permutation-invariant scalar measures of local leakage agree, the global leakage can exhibit exponentially different decay rates. We further provide the characterization of the spectral alignment factor and derive its lower bound through character-order multiplicity and Möbius inversion. We then extend the framework to automorphism-weighted sharing. We establish that automorphism-weighted sharing can achieve perfect leakage cancellation with finitely many shares, even for non-trivial full-support local leakage channels. In sharp contrast, such perfect cancellation is impossible for ordinary additive sharing with non-trivial i.i.d local leakage channels and finitely many shares. Consequently, local leakage magnitudes correctly measure the average amount of local leakage, but discard the compatibility structure needed for composition. Magnitude-only bounds must optimize over structural alignments that the actual leakage channel does not realize.

Over the last decade, indistinguishability obfuscation (iO) has emerged as a seemingly omnipotent primitive in cryptography. Moreover, recent breakthrough work has demonstrated that iO can be realized from well-founded assumptions. A thorn to all this remarkable progress is a limitation of all known constructions of general-purpose iO: the security reduction incurs a loss that is exponential in the input length of the function. This ``input-length barrier'' to iO stems from the non-falsifiability of the iO definition and is discussed in folklore as being possibly inherent. It has many negative consequences; notably, constructing iO for programs with inputs of unbounded length remains elusive due to this barrier. We present a new framework aimed towards overcoming the input-length barrier. Our approach relies on short mathematical proofs of functional equivalence of circuits (and Turing machines) to avoid the brute-force ``input-by-input'' check employed in prior works. - We show how to obfuscate circuits that have efficient proofs of equivalence in Propositional Logic with a security loss independent of input length. - Next, we show how to obfuscate Turing machines with unbounded length inputs, whose functional equivalence can be proven in Cook's Theory $PV$. - Finally, we demonstrate applications of our results to succinct non-interactive arguments and witness encryption, and provide guidance on using our techniques for building new applications. To realize our approach, we depart from prior work and develop a new gate-by-gate obfuscation template that preserves the topology of the input circuit.

End-to-end encryption (E2EE) has become the gold standard for securing communications, bringing strong confidentiality and privacy guarantees to billions of users worldwide. However, the current push towards widespread integration of artificial intelligence (AI) models, including in E2EE systems, raises some serious security concerns. This work performs a critical examination of the (in)compatibility of AI models and E2EE applications. We explore this on two fronts: (1) the integration of AI assistants within E2EE applications, and (2) the use of E2EE data for training AI models. We analyze the security implications of each, by (1) providing a new definitional framework and threat modeling approach for E2EE security ranging from theory to practice, including a new concept called caveat features, based on which (2) we offer a novel analysis to distinguish approaches to AI integration that are and are not compatible with E2EE. Then, we analyze legal implications of integrating AI models in E2EE applications, given how AI integration can undermine the confidentiality that E2EE promises. Finally, we offer a list of detailed recommendations based on our technical and legal analyses, including: technical design choices that must be prioritized to uphold E2EE security; how service providers must accurately represent E2EE security; and best practices for the default behavior of AI features and for requesting user consent. We hope this paper catalyzes an informed conversation on the tensions that arise between the brisk deployment of AI and the security offered by E2EE, and guides the responsible development of new AI features.

AI agents and custodial services are increasingly being entrusted as intermediaries to conduct transactions on behalf of institutions. The stakes are high: The digital asset market is projected to exceed \$16 trillion by 2030, where exchanges often involve proprietary, time-sensitive goods. Although industry efforts like Google’s Agent-to-Payments (AP2) protocol standardize how agents authorize payments, they leave open the core challenge of fair exchange: ensuring that a buyer obtains the asset if and only if the seller is compensated without exposing sensitive information. We introduce proxy adaptor signatures (PAS), a new cryptographic primitive that enables fair exchange through delegation without sacrificing atomicity or privacy. A stateless buyer issues a single request and does not need to manage long-term cryptographic secrets while proxies complete the exchange with a seller. The seller is guaranteed payment if the buyer can later reconstruct the purchased witness; meanwhile, the proxies remain oblivious to the witness throughout the protocol. We formalize PAS under a threshold model that tolerates the collusion of up to $t-1$ proxies. We also present an efficient construction from standard primitives that is compatible with Bitcoin, Cardano, and Ethereum. Finally, we evaluate a Rust implementation that supports up to 30 proxies. Our prototype is concretely efficient: buyer and seller computations take place in microseconds, proxy operations in milliseconds, and on-chain costs are equivalent to those of a standard transaction without fair exchange.

We present FaFROST+, the first two-round Schnorr threshold signature scheme achieving full adaptive security under the Algebraic One-More Discrete Logarithm (AOMDL) assumption with identifiable aborts. Building on the FROST framework, FaFROST+ preserves its communication efficiency while dispensing with the LDVR assumption introduced at CRYPTO'25. Our result demonstrates that round-optimal adaptive security, practical efficiency, and identifiable aborts are simultaneously achievable under the well-studied AOMDL assumption.

Adaptor signatures extend the functionality of digital signatures by enabling the computation of pre-signatures on messages relative to statements in NP relations. Pre-signatures are publicly verifiable objects that simultaneously hide and commit to a standard signature on the same message. Anyone possessing a valid witness for the statement can adapt the pre-signature into a full signature under the underlying signature scheme. Since adaptor signatures are commonly used as building blocks in larger systems, in particular blockchain protocols, it is natural to seek a security definition in the Universal Composability (UC) framework. Tairi et al. (CCS'23) recently took a first step in this direction by proposing a UC functionality for adaptor signatures. This paper investigates UC-secure adaptor signatures as a primitive, making both negative and positive contributions. On the negative side, we show that the functionality proposed by Tairi et al. suffers from critical limitations: - The functionality fails to guarantee extractability and adaptability, which are core security properties of adaptor signatures, to higher-level protocols. - No adaptor signature scheme can realize the functionality. On the positive side, we propose a new UC functionality that faithfully captures the latest security guarantees of adaptor signatures as formalized via game-based notions by Gerhart et al. (EUROCRYPT'24). - Our functionality guarantees extractability and pre-signature adaptability in a way that is composable and meaningful for higher-level protocols. - We show that it is realizable by an enhanced Schnorr-based adaptor signature scheme that we construct. Our construction maintains compatibility with existing infrastructure and is efficient enough for practical deployment, particularly in Bitcoin-like environments.

Threshold Schnorr signatures enable $t$-out-of-$n$ parties to collaboratively produce signatures that are indistinguishable from standard Schnorr signatures, ensuring compatibility with existing verification systems. While static-secure constructions are well understood and achieve optimal round complexity, obtaining full adaptive security - withstanding up to $t-1$ dynamic corruptions under standard assumptions has proven elusive: Recent impossibility results (CRYPTO’25) either rule out known proof techniques for widely deployed schemes or require speculative assumptions and idealized models, while positive examples achieving full adaptivity from falsifiable assumptions incur higher round complexity (EUROCRYPT’25, CRYPTO’25). We overcome these barriers with the first round-optimal threshold Schnorr signature scheme that, under a slightly relaxed security model, achieves full adaptive security from DDH in the random oracle model. Our model is relaxed in the sense that the adversary may adaptively corrupt parties at any time, but each signer must refresh part of their public key after a fixed number of signing queries. These updates are executed via lightweight, succinct, stateless tokens, preserving the aggregated signature format. Our construction is enabled by a new proof technique, equivocal deterministic nonce derivation, which may be of independent interest.

The CKKS fully homomorphic encryption scheme enables efficient arithmetic over complex numbers, but each homomorphic multiplication consumes a large modulus to ensure enough precision, limiting both the circuit depth and precision supported by CKKS. This work addresses this problem by proposing Generalized CKKS (GCKKS), a CKKS analogue of the GBFV scheme (EUROCRYPT 2025) that trades the number of slots for reduced modulus consumption. Despite its high-level similarity to GBFV, GCKKS faces new challenges caused by the different encoding and encryption structures of CKKS. We address these challenges with novel techniques not present in GBFV. Our plaintext encoding starts with an improved and SIMD version of Costache, Smart, and Vivek's encoding in 2017. Namely, it rounds complex values to cyclotomic integers instead of Gaussian integers, and reduces the rounding problem to solving CVP instances. This encoding allows storing high-precision complex values in polynomials with small canonical norms. As an important observation, the encoding can be simplified to a sparse CKKS encoding followed by multiplication with a polynomial constructed from a short vector in the encoding lattice. We show that by integrating this encoding format into GCKKS decryption, most GCKKS homomorphic operations and the corresponding noise analyses reduce to their CKKS counterparts. This relieves GCKKS from any heavy computational or noise overhead. In experiments, GCKKS provides 7 levels with 1000-bit precision at ring dimension $2^{14}$, where each multiplication takes less than 30 ms. To our knowledge, this precision has never been achieved before. It can be used to preserve enough precision after noise flooding, a necessary ingredient for CKKS circuit privacy and a common approach to secure threshold CKKS and to provide IND-CPA$^\text{D}$ security.

The block code basis reduction algorithm (BKZ) proposed by Ghentiyala and Stephens-Davidowitz requires an exponential number of calls to the minimum weight codeword (MWC) oracle according to the weak complexity bounds established in the original paper. In almost all cases these bounds are worse than plain enumeration of codewords, despite the fact that in practice the algorithm works much better. In this work we propose block code basis reduction algorithms with polynomial and quasi-polynomial complexity for fixed $\beta$. Our algorithms are relaxations and modifications of the original algorithm. First, we show that the truncated version of the BKZ algorithm requires heuristic quasi-polynomial time of calls to MWC-oracle with the same basis quality as in the full BKZ algorithm. Second, we add some weak restrictions on the code basis that enables the algorithm to run in polynomial number of calls to the oracle. Third, we introduce the DeepBKZ algorithm which is adapted from lattice reduction. Under some relaxations (analogs of PotBKZ from the lattices) it also runs in quasi-polynomial number of calls to the MWC-oracle. We provide an implementation of proposed algorithms which is capable to process block sizes $2-24$ and more. Based on this implementation, we provide concrete complexity estimates and an analysis of the approximation factors achieved for the low-weight codeword problem on random linear codes.

Arborists use dendrochronology, or the study of tree "growth rings" (as in, the plant), to infer past environmental events. We identify an analogous, exploitable phenomenon in the indexes used by several encrypted databases (EDBs) based on trusted execution environments (TEEs). Such EDBs have been shown to leak the order of indexed values, but not the histogram (or frequency of each value), with respect to a weaker class of snapshot adversaries. This order-only leakage substantially reduces the impact of possible inference attacks. We show, in fact, frequency is recoverable in the snapshot model from many TEE-based EDBs, even if the TEE itself is "secure". Our insight is simple: practical storage engines impose a strict total order on indexed keys by augmenting each key with a unique tie-breaker. If the adversary learns information about the tie-breakers, they can recover the frequencies of plaintext keys. We show this enables stronger inference attacks on several TEE-based EDBs (including Microsoft SQL Server’s Always Encrypted, StealthDB, and HeDB) to demonstrate this vulnerability’s ubiquity and point to broader lessons for TEE applications designed around legacy code.

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.

The constant-time programming policy protects cryptographic code from timing side-channels. However, writing constant-time code remains challenging even for experienced developers. Therefore, over 50 CT analysis tools have been published to help them identify constant-time violations. While several studies have examined those tools, they predominantly rely on qualitative observations and case studies, rather than quantitative assessments. Therefore, we present AutoBench-CT, a modular benchmark that manually verified per-violation ground truths across 64 cryptographic tasks and the first unified quantitative metrics to quantify the Operational Performance, Detection Quality, and Usability for seven such tools. With the results, we quantitatively show why CT-grind, the first tool published in 2010, is still the most popular tool in the wild. Based on the quantitative findings, we further provide new insights into recurring limitations across tools and propose a composite pipeline to maximize the security guarantees of constant-timeness in practice.

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

Patterson and Wiedemann [IEEE-IT 1983] constructed Boolean functions on 15 variables with nonlinearity 16276, which is strictly greater than the bent concatenation bound. Taking their direct sum with a bent function gives nonlinearity $2^{n-1}-27\cdot2^{(n-11)/2}$ for every odd $n\ge15$. Much later, Schmidt [JCT-A 2019] proved that the asymptotic maximum nonlinearity is $2^{n-1}-(1+o(1))2^{n/2-1}$ as $n\to\infty$. In this work, we construct Boolean functions $f$ on 375 variables such that the nonlinearity is greater than $2^{374}-442367\cdot2^{168}=2^{374}-2^{187}+81921\cdot2^{168}$, which exceeds the direct sum of a 15-variable Patterson-Wiedemann function and a bent function on 360 variables. To be specific, the direct sum of a 15-variable Patterson-Wiedemann function and a 360-variable bent function has nonlinearity $2^{374}-2^{187}+20\cdot2^{180}=2^{374} 2^{187}+81920\cdot2^{168}$. Thus our construction improves on this direct-sum value by more than $2^{168}$. Our construction idea is as follows. Let $H$ be the multiplicative subgroup of order $(2^{375}-1)/751$ in $\mathbb F_{2^{375}}^*$. The support of $f$ is the disjoint union of 375 prescribed cosets and a subset $B\subseteq H$. The evaluation of Gauss sums reduces the contribution of the prescribed cosets to a computation of 751 integers. The conditions on $B$ form a $0$-$1$ linear feasibility problem. Using a potential criterion for simultaneous linear constraints, we prove the existence of a single subset $B\subseteq H$ satisfying the constraints at all frequencies. Taking direct sums with bent functions extends the result to every odd $n\ge375$. The support construction does not require balancedness. As a natural follow-up, we also obtain balanced functions with the same strict lower bound by changing the minimum possible number of values, using sampling without replacement. The subsets $B$ and the sets of modified points are obtained by existence proofs.

Verifier‑based password‑authenticated key exchange (PAKE) enables a client and a server to establish high‑entropy session keys from low‑entropy passwords without requiring the server to store plaintext passwords. This asymmetric design reduces the risk that leakage of server‑side credentials directly leads to client impersonation, making verifier‑based PAKE well suited to authentication and session‑key establishment for Industrial Internet of Things (IIoT) devices. In this paper, we analyze the recently proposed VTBSAE, a verifier‑based PAKE protocol, and reveal that it fails to provide the claimed resistance against server‑compromise client‑impersonation attacks. To fix this vulnerability, we propose E‑VTBSAEv1. While preserving the lightweight structure of VTBSAE, E‑VTBSAEv1 binds the client‑generated point \(E_{1}\) to fresh server‑side randomness. We also briefly discuss E‑VTBSAEv2 as a challenge‑based variant. We provide a formal security proof for E‑VTBSAEv1 in the random‑oracle model under the CDH assumption, covering AKE security, forward secrecy, and resistance to server‑compromise client‑impersonation attacks after server‑side verifier‑file leakage. We evaluate E‑VTBSAEv1 under two practical deployment settings: a Raspberry Pi 4B server with an AutoDL client, and a Raspberry Pi 4B server with a Raspberry Pi 4B client. The experimental results show that E‑VTBSAEv1 preserves the communication and storage overheads of VTBSAE and achieves runtime performance comparable to that of VTBSAE.

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

Polynomial commitment schemes (PCSs) allow a prover to commit to a polynomial and later prove its evaluations succinctly. Among hash-based constructions, FRI (Ben-Sasson et al., ICALP 2018) and its follow-up works achieve polylogarithmic proofs by recursively ``folding'' Reed-Solomon (RS) codes. However, their concrete evaluation costs remain relatively high, as the first few folding rounds operate on the largest codewords and dominate the prover work. We present \emph{ReedWeave}, a Reed-Solomon PCS that successfully incorporates interleaving with folding, achieving the best of the two worlds. ReedWeave decomposes a degree-$d$ polynomial into $m$ smaller components and commits to their RS encodings over a common domain. Under our novel decomposition, a random linear combination of these codewords is exactly an $m$-ary folding. At a high level, ReedWeave starts with an $m$-ary folding, followed by standard binary folding as in FRI. The prover costs are substantially reduced in the sense that at the very beginning it suffices to do interleaved-RS encoding rather than standard RS encoding. That is, we reduce prover costs from $\mathcal{O}(d \log d)$ to $\mathcal{O}(d\log(d/m))$ for constant code rate while maintaining efficient polylogarithmic verification. Moreover, our approach essentially works for arbitrary $m$, relaxing the smoothness requirements of the underlying fields by a multiplicative factor of $m$. We benchmark our Rust implementation over Goldilocks using 32 threads and targeting 100-bit security. At $d=2^{24}$, $\rho=1/4$, and $m=64$, the DEEP variant commits in $475.0$ ms, opens in $111.6$ ms, verifies in $2.07$ ms, and produces a $594.7$ KiB proof. Compared with FRI (ICALP 2018), commitment, opening, and verification are $6.9\times$, $51.5\times$, and $4.2\times$ faster, respectively. Against STIR (CRYPTO 2024), the corresponding speedups are $2.9\times$, $68.5\times$, and $2.1\times$. Its proof is only $0.69\times$ the size of FRI's and $2.31\times$ that of STIR's.

The Hidden Subgroup Problem (HSP for short) is an important problem in quantum computing and computational group theory, which has connections with several quantum algorithms, including Shor's algorithm for integer factorization and the discrete logarithm problem. The HSP can be stated as follows: given a function on a group that is constant and distinct on cosets of a hidden subgroup, determine the hidden subgroup efficiently. The problem captures the essence of exploiting group structures for computational advantage and provides insights into the power of quantum algorithms over classical approaches. While abelian instances of HSP are well-understood and efficiently solvable using the quantum Fourier transform, non-abelian cases remain challenging and are active areas of research. The goal of this survey is to put together all the basic background needed to understand well the Hidden Subgroup Problem in groups, reviewing recent results and discussing open problems.

Let \(E\) be chosen uniformly from the geometric isomorphism classes of supersingular elliptic curves over \(\overline{\mathbb{F}}_p\) and \(\delta_E\) be the minimum degree of isogenies from \(E\) to its Frobenius conjugate \(E^{(p)}\). We establish bounds for the smoothness probability of $\delta_E$ and hence affirm Wesolowski's \(p^{1/3+o(1)}\) attack on the supersingular endomorphism ring problem is unconditional. We also establish a uniform asymptotic formula, with a main term expressed in terms of Dirichlet \(L\)-values, for the probability that a connection isogeny of degree $n$ exists between $E$ and $E^{(p)}$.

The CKKS scheme allows approximate arithmetic on encrypted data, and has found widespread use in privacy-preserving computation. A rigorous control of its homomorphic error is critical for both precision and security guarantees. In particular, in some settings such as IND-CPA^D or threshold settings, the latter computation error should be hidden at the time of decryption. This is achieved by noise flooding techniques, which require a precise upper bound on the computational error magnitude. When dealing with discrete data and a single decryptor, this is addressed by ensuring statistical correctness, which also requires a precise error management. Yet, current approaches to CKKS error analysis provide either rigorous worst-case bounds that are far off empirical measures, or average-case bounds that rely on various heuristics and do not provide strong enough guarantees for security. In this work, we develop a framework based on so-called randomization keys (RDKs), which are encryptions of zero injected at key-switching and rescaling steps to render the homomorphic error amenable to rigorous probabilistic analysis. Combined with tail bounds, this yields, to our knowledge, the first fully rigorous error analysis framework for CKKS computations. Our framework is modular: RDKs make the error of each elementary operation amenable to rigorous bounds, after which the error of a circuit follows by standard numerical error propagation. Our rigorous bounds are comparable to heuristic ones and closely match empirical measures, but cost additional evaluation material (RDKs) generated by the secret key holder. In the context of rigorous bootstrapping, this induces a communication overhead of 27% over the bootstrapping keys for a single evaluation, and of a further 8% for each additional evaluation. We show that, when a circuit is evaluated repeatedly, most of these keys can be reused across evaluations. As our main application, we derive a complete and rigorous analysis of binary CKKS bootstrapping, and a full, rigorous, parameter set for the bootstrap-and-clean technique. Compared to a standard Gaussian-type heuristic approach, our parameters only require a modulus increase for bootstrapping of $\approx 3\%$, while providing rigorous precision estimates.

The Algebraic Group Model (AGM) has become a standard framework for analyzing the knowledge soundness of group-based polynomial commitment schemes. In this work, we formally establish inherent limitations of this methodology. For many PCSs analyzed in the AGM, the algebraic explanation directly determines a polynomial and any required randomness that together reproduce the commitment. We call this structural property AGM-clarity. The extraction proof then only needs to show that the accepted evaluation agrees with this polynomial. For AGM-clear schemes, evaluation binding alone implies knowledge soundness in the AGM. If the commitment algorithm is itself algebraic, knowledge soundness in the AGM is in fact equivalent to weak evaluation binding, a relaxation of evaluation binding introduced by Catalano, Fiore, and Tucker (ASIACRYPT 2022). We then show that this guarantee implies neither standard-model extraction nor evaluation binding. Under the discrete-logarithm and SBDH assumptions, we give a succinct modification of the KZG polynomial commitment that is evaluation binding and, hence, knowledge-sound in the AGM. It admits a prover that is accepted on every evaluation point, yet no efficient extractor recovers an opening of its commitment, even given the prover's code and state. For a non-succinct variant, no polynomial consistent with the transcript exists at all, so extraction fails even for unbounded extractors. A minor modification of those PCSs destroys evaluation binding while leaving knowledge soundness in the AGM intact, so the AGM notion lies strictly below evaluation binding. Finally, we show that the common formulation, which also requires algebraic explanations of evaluation proofs, is strictly weaker than the variant characterized by weak evaluation binding. Our separating schemes satisfy even the stronger variant, so no property implied by either formulation guarantees extraction in the standard model.

Secret-shared SQL-style join is a fundamental building block in secure collaborative data analysis. In practice, join operations frequently involve duplicate keys, giving rise to one-to-many (Join-OM) and many-to-many (Join-MM) relationships. Supporting such joins requires obliviously materializing all matching row pairs. Existing protocols achieve this in two costly ways: they either perform oblivious sorting over a larger expanded input or rely on multiple aggregation trees that incur additional logarithmic rounds. In this work, we present highly efficient protocols for Join-OM and Join-MM over secret-shared databases in the standard semi-honest setting. Our core contribution is Oblivious Sort Expansion (OSE), a novel constant-round protocol that may be of independent interest. Rather than obliviously sorting the expanded input from scratch, we sort only the original input and use OSE to derive the sorted order after expansion. For Join-OM, OSE eliminates the redundant sorting overhead introduced by input expansion in the state-of-the-art protocol by Asharov et al. (CCS 2023). For Join-MM, we combine OSE with local linear operations to obtain an aggregation-tree-free Join-MM protocol. Experimental results show that our protocols consistently outperform prior protocols, reducing both runtime and communication costs by approximately $27\%$ and $65\%$ for Join-OM and Join-MM, respectively.

Noise cleaning in discrete CKKS uses Hermite interpolation to reduce the input error while preserving the encrypted discrete message. Cryptographic applications based on noise flooding require the error after cleaning to be sufficiently small for the added noise to provide statistical hiding without preventing exact recovery. This requirement is more stringent than decryption correctness alone, but the achievable noise reduction is limited by errors introduced during homomorphic evaluation. In particular, key switching and rescaling can dominate the output error even when a higher interpolation order substantially reduces the polynomial residual. We propose a high precision noise cleaning method for CKKS that preserves encrypted integer messages while attaining a prescribed bound on normalized output noise. We jointly select the cleaning polynomials and evaluation parameters according to a complete error bound that accounts for the input noise and the errors introduced during homomorphic evaluation. By composing Hermite polynomials of lower degree, we can achieve the same output noise bound with a smaller ciphertext modulus and lower evaluation cost than a single higher degree polynomial. In addition, to reduce the ciphertext tensor degree, we construct polynomial representations with noisy auxiliary powers that cancel selected auxiliary error terms. For integer messages, we extract the bits through multi-value functional bootstrapping, then clean and recombine them into a single ciphertext. Finally, we apply high precision noise cleaning to construct an asynchronous threshold CKKS scheme that achieves strong simulation security in the random oracle model. We implement binary and integer noise cleaning in OpenFHE. For binary messages and a normalized output noise target of $2^{-300}$, the selected composition reduces cleaning time from $9.63$ to $1.54$ seconds compared with a single Hermite evaluation under the same input error bound and security requirements. The composition also requires a smaller input ciphertext modulus and less evaluation key storage. We also evaluate the complete construction on 8 bit integers packed into all $32{,}768$ slots. The maximum measured normalized output noise is below $2^{-300}$ with either leveled digit extraction or functional bootstrapping.

The adaptive clinching auction of Dobzinski, Lavi, and Nisan (FOCS'08) is a cornerstone of mechanism design with budget-constrained bidders, and it has since inspired a broad range of extensions to substantially richer market settings. Adaptive clinching enjoys compelling guarantees: it is Pareto optimal, and truthful bidding is a dominant strategy whenever budgets cannot be overreported. In many real-world environments, however, identities are cheap to create, making resilience to Sybil attacks an additional requirement. Whether the guarantees of adaptive clinching survive when a bidder can split its budget across fake identities has remained open. We introduce a generalized framework for adaptive clinching and prove that it satisfies Sybil-robust incentive compatibility: a bidder cannot benefit from splitting into any finite number of identities with arbitrary value reports, provided their aggregate reported budget does not exceed the bidder's enforceable true budget. Sybil resilience thus joins the list of ideal properties of adaptive clinching. Our work is motivated by practical mechanism-design problems in blockchain-based decentralized finance, where two-asset automated market makers (AMMs) are among the most widely used applications. We design a new AMM adaptive clinching mechanism that extends classical adaptive clinching in two ways: it supports a two-sided market and protects against two-sided strategies, and it allows the supply function to depend on the auction state. Its one-sided special case is captured by our generalized adaptive clinching framework, and we further extend our proof techniques to show that the full two-sided mechanism simultaneously satisfies Sybil-robust incentive compatibility and a relaxed notion of Pareto optimality. In light of known impossibility results, together with a new impossibility proved in this paper, we argue that these guarantees are essentially the best possible. More broadly, our work reveals new connections between classical algorithmic game theory and modern decentralized blockchains.

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

Cache and cache-collision attacks against AES are well-known since 2005, but their application to small (Cortex-M sized) microcontrollers has been limited in prior work, and in many cases the devices are assumed to be immune when they do not have a cache. However, the flash architecture of almost all microcontrollers introduces the same timing collision required for the well-known attacks and as a greatly underestimated channel. Recovery of AES keys using as little as 750 traces will be demonstrated on six popular cryptographic libraries across eight architectures and over twenty devices. Practical recovery on high-level applications is demonstrated against SPI bootloaders, Ethernet applications, CTAP2 over USB, and 802.15.4. wireless protocols. In addition, a new open-source tool called FlashWhisperer is introduced to assist with evaluation of microcontrollers, cryptographic libraries, and applications. Countermeasures already exist in the form of bitsliced implementations, and this work also discusses other countermeasures that existing libraries offer.

Zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) are powerful cryptographic tools for certifying the correctness of computations with short proofs, fast verification, and zero-knowledge privacy guarantees. However, most existing zkSNARK schemes support arithmetic only over finite fields defined by large primes or their extensions. This creates substantial overhead when proving computations written in high-level programming languages, which typically operate on fixed-width integer types such as 32-bit and 64-bit integers. In this paper, we introduce Nenya, the first practical SNARK scheme that supports native arithmetic over the integer ring $\mathbb{Z}/2^k\mathbb{Z}$. At the core of Nenya are new reductions from rank-1 constraint systems (R1CS) over $\mathbb{Z}/2^k\mathbb{Z}$ to constraints over Galois rings via reverse multiplication-friendly embeddings (RMFEs). We also design a polynomial commitment scheme based on suitable classes of error-correcting codes, which supports well-formedness checks and packing rotations on committed witnesses essentially for free, resulting in sublinear verifier time. Experimental results demonstrate that Nenya achieves strong concrete performance. For a rank-1 constraint system of size $2^{25}$ for data-parallel computations over 32-bit integers, Nenya achieves a prover time of only 4.8 seconds. This is four orders of magnitude faster than the state-of-the-art SNARK scheme over $\mathbb{Z}/2^k\mathbb{Z}$, and only 1.06$\times$ slower than a SNARK over a field with the same number of constraints. For general computation, the prover time of Nenya is 34.6 seconds. Moreover, for proving pixel-level image transformations that arise in media-provenance workflows, such as filtering that operates natively modulo $2^8$, Nenya proves the same computation 12$\times$ faster than a field-based SNARK.

In this work, we study (multivariate) polynomial evaluation datastructures, i.e. algorithms that can evaluate a multivariate polynomial at any input point, using random access to some precomputed encoding of the polynomial. Multiple constructions have been proposed in the literature, with the work by Bhargava, Ghosh, Guo, Kumar and Umans (2024) achieving optimal datastructure size and query complexity, up to polynomial factors. For $n \in d^{o(1)}$ this is equivalent to having datastructure size $d^{n + o(n)} (d n \log q)^{O(1)}$ and query complexity $(d n \log q)^{O(1)}$ for an $n$-variate polynomial of total degree $d$ over $\mathbb{F}_q$. However, the algorithm of Bhargava et al. is not algebraic, since it requires lifting prime field elements to $\mathbb{Z}$. An algebraic algorithm would be desirable, as an algebraic model of computation is natural for studying polynomial evaluation and is the standard model in algebraic complexity theory. One approach to finding algebraic polynomial evaluation datastructures is to use univariate polynomial interpolation to reconstruct the polynomial along algebraic curves. This approach was first made explicit by Bhargava, Ghosh, Kumar and Mohapatra (2023), who used it to build an essentially optimal algebraic polynomial evaluation datastructure for fields of small characteristic $p = \mathrm{char}(\mathbb{F}_q) \in d^{o(1)}$. Over these fields, their construction refutes a previous conjecture by Miltersen. For fields of larger characteristic, it remains an open problem to find an algebraic algorithm with optimal datastructure size and query complexity. In this work, we propose a new way to construct algebraic curves over prime fields that allow polynomial interpolation: by deriving curves from the base-$\beta$ representation of (lifts of) prime field elements, we are able to recursively reduce the evaluation problem to points in boxes of decreasing size. This leads to a datastructure whose performance scales much more favourably with $p$. Concretely, we improve the dependency of the query complexity on $p$ from $p^{O(1)}$ to $d^{2\log_2 \ln\ln p} \ln p$, and completely remove the dependency on $p$ from the datastructure size. Its query complexity is still slightly super-polynomial in $d \log p$. Nevertheless, a variant of our results is enough to disprove Miltersen's conjecture for all finite fields, including prime fields. We further show that for a certain class of datastructures, which captures natural generalizations of our approach, the query complexity is lower-bounded by $d^{(1 - o(1))\log_3\ln\ln p}$. Consequently, within this class, our construction is optimal up to a constant in the exponent.

We revisit scalar multiplication on prime curves $y^2 = x^3 + b$ with $p \equiv 1 \pmod 3$, the family including secp256k1, BN, and BLS curves. We apply a 15-year-old technique in a novel way to improve the best complete addition from $12$ to $11$ multiplications (or $10$ for mixed coordinates) for the first time in 10 years: its final stage is a 3D cross product, which needs only five multiplications. We implement the new formulas on the \texttt{libsecp256k1} library, with an improvement of $5.2$\% in constant-time fixed-base scalar multiplication. Furthermore, we propose a complete tripling formula with the same cost as incomplete tripling in Jacobian coordinates, and combine both formulas into an exception-free width-3 $\tau$-NAF with $\tau = 1 - \omega$ and a six-point precomputed table. In an operation-count model it is about 14\% faster than exception-free GLV-based scalar multiplication at 256 bits and 3--7\% faster than the fastest incomplete GLV. A constant-time implementation in RELIC confirms the model on the BLS families: in $\mathbb{G}_1$ of BLS12-381, BLS24-509 and BLS48-575 the $\tau$-NAF is 9--13\% faster than GLV with the same complete formulas, and the regular variant is 10--12\% faster than regular GLV with complete formulas and 5--9\% faster than regular GLV with incomplete Jacobian formulas. In $\mathbb{G}_2$ of the same curves, where GLS gives the baseline, the $\tau$-NAF stays 10--11\% faster than GLS with complete formulas and 7--9\% faster with Jacobian formulas, while the regular variant gains at most 6\%. We also develop an `imaginary' version of Toom-Cook that is useful for the $\mathbb{G}_T$ extension field arithmetic, yielding a 4--6\% improvement in $\mathbb{G}_T$ exponentiation for BLS24-509 and BLS48-575. A cyclotomic cube at 0.77 multiplications carries the $\tau$-adic method over to $\mathbb{G}_T$, where it makes exponentiation 3\% faster on BLS24-509 and 11\% faster on BLS48-575.

Private Information Retrieval (PIR) allows a client to retrieve an entry of a database while revealing no information about the requested index to the servers. Classic information-theoretic PIR protocols of Chor et al. (FOCS '95, JACM '98) and Ambainis (ICALP '97) achieve sublinear client computation and communication complexity with a constant number of servers, but require each server to perform computation linear in the database size. In this work, we ask for which classes of structured databases the server computation can be substantially reduced while preserving the communication complexity and privacy guarantees of these protocols. Our main contribution is a new connection between server computation in information-theoretic PIR and probabilistic inference. We show that the computation performed by every server in both the Chor et al. protocol and the recursive protocol of Ambainis can be viewed as computing a marginal probability of a product distribution. Consequently, efficient exact probabilistic inference algorithm immediately yields a faster server algorithm for PIR. We formalize this connection through the notion of inference complexity, which captures the complexity of evaluating these marginals. Using this framework, we obtain improved server computation for several broad classes of functions, including read-once arithmetic formulas, graphical models of bounded treewidth (and consequently arithmetic circuits of bounded treewidth), functions with low communication complexity, and functions with sparse Fourier representations. The resulting protocols preserve the communication complexity, client computation, and number of servers of the underlying PIR constructions while substantially reducing server computation for these structured function classes. Finally, we complement our algorithms with conditional lower bounds. Assuming the randomized Circuit Strong Exponential Time Hypothesis (rCSETH), we show that, for every constant \(\varepsilon>0\), there exists a constant \(c\) such that no uniform algorithm can compute the first (virtual) server's response in the Chor et al. or Ambainis protocol on all \(n\)-input Boolean circuits of size at most \(n^c\) in time \(O(N^{1-\varepsilon})\), where \(N=2^n\). Thus, under rCSETH, substantially sublinear server computation cannot be achieved uniformly for all polynomial-size Boolean circuits.

Lattice-based cryptography uses SHAKE to expand seeds into byte strings for matrix generation and sampling. SIMD Keccak implementations process multiple hash streams in parallel. Differences in stream lengths and input dependencies can prevent full SIMD utilization. We present a cost-aware method for scheduling Keccak permutations across hash streams during a single execution of a cryptographic algorithm. The method groups ready streams and divides long streams into segments for regrouping. A model of permutation calls, state movement, initialization, and input preparation guides the selection of stream groups, segment lengths, and state placements. We evaluate ML-KEM and HAETAE on an Apple M5, a Cortex-A72, and an Intel Core i5-11500, using Keccak kernels that process two, four, or eight streams per call. ML-KEM achieves speedups of up to $1.31\times$ for encapsulation and $1.44\times$ for decapsulation, while HAETAE achieves up to $1.28\times$ for signing and $1.26\times$ for verification.

The approximate Closest Vector Problem $\mathsf{CVP}$ with large approximation factors, such as a polynomial approximation, arises in the concrete cryptanalysis of lattice-based signatures, yet it is commonly estimated indirectly through $\mathsf{SVP}$ after Kannan's embedding (Wang et al, PQC2025). Such reductions may return short vectors that do not encode valid $\mathsf{CVP}$ solutions and are less suited to reusable preprocessing, batched targets, and list output. We give, to our knowledge, the first practical instantiation of the Nearest-Colattice framework (Espitau et al, ANTS2020). Our $\texttt{RandNColattice}$ algorithm realizes quotient-lattice $\mathsf{CVP}$ calls on explicitly projected basis blocks using randomized slicer oracles (Ducas et al, PKC2020), and therefore naturally propagates multiple candidate branches for batches of targets. We further extend the randomized slicer with dimensions for free for both $\mathsf{BDD}$ and approximate $\mathsf{CVP}$/$\mathsf{ListCVP}$, and introduce $\texttt{HybridRandNColattice}$, which replaces the oracle on the final block with Klein's sampler to generate diverse randomized residual targets efficiently. The final candidate-filtering interface is norm-generic, while our concrete analysis focuses on the Euclidean and infinity norms. We derive blockwise distance and runtime models and construct an estimator over 4 strategy models: $\mathsf{D4f}\text{-}{CVP}$, $\mathsf{Prob}\text{-}\mathsf{BDD}$, $\mathsf{CVP}_{\gamma_2}$, and $\mathsf{Flexd4f}\text{-}\mathsf{CVP}_{\gamma_2}$ with $1\leq \gamma_2\leq \sqrt{4/3}$. The estimator instantiates costs under a theoretical model and the AGPS20 and MATZOV22 gate-count models, and we apply it to non-amortized forgery estimates for Dilithium, HuFu, and one-more-ISIS. Finally, we implement $\texttt{HybridRandNColattice}$ by extending the G6K-CPU based randomized slicer (Alexander et al, AsiaCrypt 2025). Our experiments support the Euclidean distancemodel, while showing that the spherical approximation used for infinity-norm filtering is optimistic because the actual blockwise error distribution is anisotropic. These results provide a concrete foundation for direct approximate-$\mathsf{CVP}$ cryptanalysis and identify tighter infinity-norm modeling as an important open problem.

Identity-based encryption (IBE) is required to support a superpolynomial-size identity space using only polynomial-size public parameters. This compression requirement underlies known barriers to IBE in the generic (pairing-free) group model. Cryptographic group actions, motivated prominently by isogeny-based cryptography, support many advanced primitives beyond public-key encryption. However, no generic construction of IBE from the basic group-action interface is known. Existing generic-group barriers do not resolve this question as they do not translate to generic group-action models. We establish the first tight barriers to IBE in two variants of the generic group-action model. In the type-safe generic group-action model, we prove that an IBE scheme with negligible correctness error and $n$ non-origin action-set element-handles in its public parameters can support at most $n$ identities, even for a weak notion of fully selective security. We show that this bound holds irrespective of the number of action-set element-handles in identity secret keys. We further establish that this bound is tight by demonstrating a matching construction. We then extend this tight characterization to a natural class of IBE schemes in the random-representation generic group-action model (including against representation-sensitive adversaries) under conditions ensuring that identity keys retain no hidden action-set encodings and discarded private encodings leave no residual information. We give a natural syntactic condition for the latter property. For actions additionally equipped with an inversion-like twist, we obtain a more general upper bound (including the same tight bound for odd-order actions). Our results provide the first formal evidence that IBE is likely to require additional algebraic structure or non-black-box techniques beyond the generic group-action interface. More broadly, we provide a new framework for proving lower bounds in generic group-action models.

Enhanced Privacy Identification (EPID) is one of the anonymous authentication mechanisms that found their way into the industry, being deployed in billions of chips and standardized at ISO. The linchpin of EPID lies in its decentralized revocation procedure that allows to revoke a signer by simply placing one of its signatures on a signature revocation list SRL. Each new signature must then include a proof that it has been generated with a key different from those used to produce the signatures on the SRL. This proof of non-revocation in current post-quantum schemes either relies on general-purpose NIZKs or on regular zero-knowledge proofs (ZKP) but with a witness dimension linear in the size of the SRL, which leads to large size and/or computational complexity. In this paper, we rethink the standard approach of non-revocation so as to avoid its heavy reliance on ZKP. Our construction indeed combines features from different tools (such as Falcon signatures) that are unusual in this context to pull most elements out of the ZKP, leading to significant performance improvements. Providing all these elements unconcealed creates many security challenges for our construction but we yet manage to address all of them and prove security under well-understood lattice assumptions, and in the strong model of Sanders-Traoré (CT-RSA'21) allowing malicious SRLs.

We present an end-to-end resource estimation of Shor's algorithm on superconducting cat qubits, from its mathematical description to the allocation and scheduling of physical qubits on a chip layout. After proposing a comprehensive view of the modern versions of Shor's algorithm for RSA, ECDLP and FFDLP, we make explicit their logical circuits and the trade-offs they enable. We compile the dominant subroutines down to physical-qubit operations on two architectures: one based on repetition cat codes and one based on LDPC cat codes. We design a parity-Cnot gate for cat qubits, extend a multi-target Cnot gate to the LDPC-cat architecture, and adapt an active injection procedure to cat-qubit architectures. Building on these primitives, we adapt to cat-qubit architectures the adder from Gidney’s 2025 resource estimate for factoring RSA-2048. We combine our adder compilation and a coarser resource estimate for the phaseup with the factory designs and lookup compilation from the FeMoco resource estimation of Kroell et al. Together, these compilations lead to chip layouts and schedules for factoring RSA-2048. Assuming a 1$\mu$s error-correction cycle time, a 10$\mu$s reaction time, circuit-level phase-flip noise with probability $p_Z = 5 \times 10^{-4}$ and no bit-flips, factoring RSA-2048, the configuration we compile in full, requires about 23 000 cat qubits and 3.14 days. Reusing the operations compiled for RSA-2048, solving ECDLP on secp256k1 requires at most 30 000 cat qubits and 1 hour, and FFDLP-512, which we propose as an intermediate benchmark, about 6\,700 cat qubits and 21~minutes. Trading space for time, RSA-2048 runs in 1.25 hours on about 611 000 cat qubits. The requirement on no bit-flips (which corresponds to a bit-flip time of about 100 years) can be relaxed to a bit-flip time of about one hour by using an additional concatenation layer into a distance-3 bit-flip error-correcting code. In that case, we estimate that the cost of RSA-2048 increases to about 45 000 cat qubits.

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 three 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; to our knowledge this is the first such construction for generic sponges with search cost independent of k. We give verified full-round examples on Keccak-f[200] and on Keccak-f[1600] with c=32. 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 the generic bridge cost is a feasible, tunable hardness parameter. We prove the three 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.

The Lattice Isomorphism Problem (LIP) is a computational problem that has recently been introduced into cryptography and is believed to be hard. Its search version, Search Lattice Isomorphism Problem (SLIP), is considered even harder than the Shortest Vector Problem (SVP), yet its complexity is still not well understood. Haviv and Regev (SODA 2014) showed that the decisional version (DLIP) lies in a statistical zero-knowledge class and is therefore unlikely to be NP-hard. This result does not apply to the search version, which motivates the question of whether NP can reduce to SLIP. Our main result answers this question negatively. We show that every language reducible to SLIP lies in AM and coAM, by analyzing the direct-sum structure of irreducible lattices. Consequently, NP cannot reduce to SLIP unless the polynomial hierarchy collapses, and there is no reduction from SVP to SLIP unless the polynomial hierarchy collapses. We also study several problems closely related to LIP and establish reductions between its search, counting, and decisional variants. These connections mirror known relationships for graph isomorphism. Finally, we propose a new algorithm that uses a KZ basis to compute an orthogonal decomposition of a lattice.

Pseudorandom codes (PRCs) are error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings to any efficient adversary. We study public-key multi-bit PRCs over the stochastic memoryless binary substitution-insertion-deletion channel and its $q$-ary generalization. Here $P_i,P_d$ are the insertion and deletion probabilities, and $P_s$ is the substitution probability conditional on transmission. We first show that the majority-based construction of Christ and Gunn yields a binary PRC with vanishing rate that recovers the transmitted message with overwhelming probability whenever $P_i+P_d<1$ and $P_s<1/2$. We then use this binary PRC to protect control information in a high-rate, uniquely decodable PRC over an unbounded family of constant-size alphabets. For fixed channel parameters satisfying $P_i+P_d<1$ and $P_s<1$, its decoder recovers the transmitted message with overwhelming probability. The alphabet size may depend on the channel parameters and desired rate gap, but not on the security parameter. As the gap tends to zero and the alphabet grows through the supported sizes, the rate approaches the capacity upper bound obtained by revealing insertion and deletion locations to the receiver. The constructions use the assumptions underlying the Christ--Gunn public-key PRC and secure pseudorandom generators.

We investigate an algebraic approach to the Syndrome Decoding Problem, based on a reformulation of the Hamming weight constraint and its integration with the Information Set Decoding paradigm. We begin with a systematic analysis of the Hamming variety, deriving its defining equations in terms of elementary symmetric functions. Since these equations may have high degree, we exploit convolution identities for elementary symmetric functions, together with factorizations based on Lucas' identity, to derive an equivalent formulation with auxiliary variables and equations of bounded degree. Building on this modeling, we generalize the ISD paradigm through an ISD-like decoding strategy, implemented by the GBDecode algorithm, in which only a subset of an information set is fixed. This approach reduces the size of the combinatorial search space at the cost of solving the associated multivariate nonlinear systems. To handle this algebraic component, we employ the MultiSolve algorithm, which replaces a single Grobner basis computation with a collection of computations on simpler systems, obtained by exhaustively assigning a varying number of indeterminates over the finite field. This provides a tunable balance between combinatorial search and algebraic solving. We evaluate the resulting approach experimentally on instances of the Syndrome Decoding Problem for random binary linear codes, using parameters corresponding to the NIST Security Category 1 parameter set of the Classic McEliece cryptosystem. The experiments assess the feasibility of this combinatorial-algebraic approach and provide insights into the practical behavior of Grobner basis techniques within an ISD-like decoding framework.

The EasyCrypt proof assistant has been used to successfully formalize security proofs for a wide variety of cryptographic primitives. However, attempts at formalizing objects with interactivity, such as protocols, have fared much worse. In this paper, we investigate (some of) the reasons for this difficulty. To identify which proof features contribute most to the complexity of formalization in a tool based on probabilistic relational Hoare logic (pRHL) such as EasyCrypt, we formalize a simple interactive key agreement protocol in three different ways. From these proof efforts, we then extract our insights. In particular, we argue that difficulties in formalizing the security of interactive protocols in the computational model arise from the fact that such proofs rely on both state and temporal invariants—the former to support cryptographic reasoning, and the latter to support reasoning about the protocol’s structure. At the same time, EasyCrypt and similar pRHL-based approaches offer no native notion of events, traces or timestamps, forcing a user to find their own encoding of temporal properties. We discuss two possible encodings, state-first and trace-first, and their impact on the proof effort. More generally, we believe that this observation can help build new reasoning tools that can bridge the gap that currently exists between primitive-focused tools and protocol-focused tools.

Rerandomizable garbling schemes (RGS) are a fundamental primitive enabling advanced cryptographic constructions such as multi-hop homomorphic encryption (Gentry, Halevi, Vaikuntanathan, CRYPTO 2010), iO-combiners (Ananth, Jain, Naor, Sahai, Yogev, CRYPTO 2016), and YOSO-style MPC (Acharya, Hazay, Kolesnikov, Prabhakaran, TCC 2022 and CRYPTO 2024). All known RGS instantiations rely on discrete-logarithm-type assumptions, concretely via the BHHO scheme (Boneh, Halevi, Hamburg, Ostrovsky, CRYPTO 2008) and its recent pairing-based variant (Heitjohann, von der Heyden, Jager, CRYPTO 2025). This reliance stems from the use of key-and-message homomorphic encryption (KMHE) that supports rerandomization and strong "key-privacy under leakage", which hides the applied homomorphic transformations and is currently only achievable using BHHO-style bitwise encryption in combination with permutation-based homomorphisms. Our first main contribution is a new garbling technique that shifts the burden of hiding homomorphic transformations from the encryption scheme to the garbling itself. This allows us to construct RGS from KMHE schemes with substantially weaker properties, avoiding the need for bitwise encryption and permutation-based homomorphisms, and enabling the construction of RGS from KMHE with other homomorphisms, such as additively-homomorphic ones. As a second contribution, we give a concrete lattice-based instantiation of the required KMHE primitive, based on LWE. This construction is a variant of the GSW FHE scheme (Gentry, Sahai, Waters, CRYPTO 2013), which uses new techniques for rerandomization and is tailored to the requirements of our new garbling scheme by supporting a "homomorphic"/"lossy" mode. This yields the first RGS construction that does not rely on discrete-logarithm assumptions and may provide post-quantum security.

We present four quantum-safe schemes: the Kyber (ML-KEM) and FrodoKEM key encapsulation mechanisms, and the Dilithium (ML-DSA) and Falcon (FN-DSA) signature schemes. We also develop the mathematical background on lattices needed to understand why Kyber, FrodoKEM, Dilithium and Falcon are regarded as lattice-based cryptosystems, and we provide insight into the computational hardness of the underlying lattice problems. The exposition is intended to be accessible to senior undergraduate students and beginning graduate students.

We study quantum collision finding for functions of prescribed exact type. For fixed constants $k\ge r\ge2$ and $N=kn$, consider functions $f:[N]\to\mathbb Z_q$ of type $(k^n)$, with exactly $n$ distinct output values and $k$ preimages for each value. We prove that the worst-case bounded-error quantum query complexity of finding $r$-collisions in $\ell$ distinct equality classes is \[ \Theta_{k,r}\!\left( \ell^{\,2^{r-1}/(2^r-1)} N^{(2^{r-1}-1)/(2^r-1)} \right) \] for $1\le\ell\le N^{2^{-r}}$. The result is uniform over all feasible alphabet sizes $q\ge n$. Our proof uses the compressed permutation oracle (CPO). We establish a recurrence for intermediate collision counts and control its accumulated error to obtain database tails exponentially small in $\ell$. The improved CPO soundness estimate then converts these database bounds into function-query lower bounds. Moreover, we extend the analysis to arbitrary exact types with bounded class sizes, without requiring any particular class size to occur linearly often. The resulting lower bounds are tight when forward permutation access is additionally available, although they need not be tight for the original function-query problem. Finally, a sampling reduction relates our collision bounds to sparse $k$-distinctness instances. A separate analysis using Belovs's transfer framework recovers the same lower-bound exponent, establishing a concrete connection between the two approaches.

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

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

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

Oscillator-based true random number generators derive randomness from timing fluctuations driven by thermal and flicker noise, and flicker gains weight as technology advances and transistors shrink. Its long memory leaks information about past, which existing models either discard or truncate, overstating security. We introduce a rigorous and tractable framework for colored noise, including the white and flicker noise of oscillators. We model the oscillator phase by fractional Brownian motion and prove a quasi-renewal property: the phase uncertainty left after conditioning on the entire past depends only on the elapsed time. This yields closed-form worst-case min-entropy and sampling requirements. We also extend spectral and Allan-variance analysis to finite samples, so the noise parameters are estimated consistently from a single timing trace. The pipeline from measurement to sampling requirement is closed-form and needs no simulation. Experiments across FPGA and ASIC platforms show that flicker dominates: its variance meets white noise within about 100 cycles and accounts for more than 99% of uncertainty behind the targeted 0.99 min-entropy rate. Methods relying exclusively on thermal noise require adjustment or redesign: incorporating flicker noise enables a two-to-three orders of magnitude increase in bitrate.

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

Radical isogeny formulae compute a cyclic chain of $N$-isogenies with one $N$th root per step and without sampling torsion points, but for general $N$ they were only known in Tate normal form. We give radical steps of every odd degree $N$ directly on short Weierstrass, Montgomery, twisted Edwards, Huff, extended Jacobi quartic, twisted Hessian, Legendre and Jacobi intersection curves, on Kummer lines, and on all curves with a rational point of order~$2$. Our approach is model-independent. The Tate normal form data is obtained from the $x$-coordinate of the kernel generator by a shifted recursion, and the codomain is recovered in the original model by locating the image of a distinguished torsion point, without square roots. In Tate normal form we lower the cost of a step from $12.5N$ to $10N$ multiplications plus one exponentiation, and short Weierstrass curves come close at $10N+35$. Montgomery and twisted Edwards curves cost $10.5N+O(1)$. However, pushing a point through their steps costs only $2N$ multiplications without precomputation, against $2N+16$ plus a shared $2N-7$ in Tate normal form, which makes them the cheapest models for chains that transport torsion points, e.g.\ for all $N\ge19$ when two points are pushed. The other models cost between $11.5N+O(\log N)$ and $15.5N+O(\log N)$ per step. All algorithms are inversion-free, with exact operation counts.

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

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

Side-Channel Analysis is an established field of research to assess implementation vulnerabilities of cryptographic algorithms. One typically exploited side-channel is the electromagnetic (EM) near-field, which is proportional to the data-dependent currents flowing through an Integrated Circuit (IC). The field of Quantum Sensing (QS) based on Nitrogen-Vacancy (NV) centers has shown promising approaches for different measurement configurations like scanning or spatially resolved wide-field imaging. Already today, QS has been used in the analysis of (quasi-)static magnetic fields on ICs in spatially-resolved wide-field magnetometers. In this work, we study the applicability of QS for the analysis of dynamic EM fields of ICs. For the first time, we demonstrate spectral-temporal analysis of the EM-side-channel using an NV-center-based Radio-Frequency spectrometer. Our sensor has a real-time bandwidth of 1.1 GHz with adjustable center frequency and directly probes the frequency spectrum via NV center interactions in the time domain. The approach circumvents any computations like Fourier transforms or performing frequency sweeps, enabling GHz-realtime bandwidths. We use this spectrometer to analyze the EM emanations of an RSA decryption and perform leakage detection of a software implementation of the Number Theoretic Transform - a building block of all current lattice based post-quantum algorithms - running on a Cortex M4 commercial off-the-shelf microcontroller.

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

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

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

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

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

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

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

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

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

Secure aggregation lets clients reveal only an aggregate of their private contributions, supporting a variety of applications, including privacy-preserving sensing, collaborative analytics, and federated learning. Building on the single-server, committee-aided model for one-shot clients used by OPA and Willow~(CRYPTO~'25), we present Ossa, a generic construction with a modular security analysis. Ossa realizes the standard secure aggregation functionality with non-selective abort against a malicious server, but leaves role selection unspecified and provides no delivery guarantee. We therefore present AlgOssa, which integrates Ossa into an Algorand-style consensus backbone in which cryptographic sortition selects fresh potential leaders and verifier committees in each round and refreshes the decryptor committee from finalized chain state at key epochs. AlgOssa further selects the server from among the potential leaders, and we establish an explicit lower bound on the probability that the selected server is honest. Consequently, the probability that a round delivers a non-empty aggregate is bounded below by a positive constant, yielding an eventual delivery guarantee across repeated rounds. This variable delivery cadence fits delay-tolerant statistical sensing and, with persistent buffering and staleness control, buffered asynchronous federated learning. Our generic core supports classical and post-quantum instantiation routes; we evaluate complete local classical rounds and demonstrate the feasibility of the post-quantum route.

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