Large Language Models (LLMs) have made it exceptionally convenient for users to send their private data to model providers, which process them in plaintext. Fully Homomorphic Encryption (FHE) promises to secure remote inference by computing directly on encrypted data, yet it has remained prohibitively slow. The effort to make it practical remains fragmented, with most existing frameworks being closed-source, which keeps progress from compounding. We present Perseus, a free and open Python software library that supports the full stack of encrypted model inference, from the cryptographic backend and data packing, to encrypted nonlinearities and end-to-end model execution. Perseus ships with built-in novel optimizations, one at each level of the stack: in-kernel regeneration of key-switching keys at the (i) backend level, a complex variant of Cachemir packing at the (ii) data level, and a state-of-the-art bootstrap placer that is both packing- and magnitude-aware at the (iii) model level. Perseus achieves state-of-the-art latency across multiple models and modalities, within $3\%$ of the plaintext models' accuracy and perplexity. Remarkably, it is $3.96\times$ faster at single-token decoding than any other implementation on Llama-3-8B. We initiate, for the first time, a public speedrun on encrypted GPT-2, so that progress can compound.

High-arity oblivious transfer is a natural abstraction for private lookup: a $\delta$-bit table address selects one entry out of $2^\delta$ candidates. This paper characterizes the finite-batch design space of the CCG q-ary OT-extension family and derives certified radix-selection rules. For $q=2^r$, we formulate radix-code selection as a security-constrained discrete optimization problem that accounts for subfield-check padding, code dimension, required distance, base-OT count, and q-ary symbol width. We derive exact communication thresholds showing when reduced base OTs can compensate for larger q-ary encoding cost. Then we convert the Griesmer bound into communication lower bounds, yielding certificates for regions where non-binary radices cannot improve communication, are provably beneficial, or remain dependent on better code constructions. Finally, we instantiate the framework with simplex and BCH constructions and CodeTables entries, and verify the selected $\delta=12$ codes with Magma.

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.

MinRank is an NP-complete problem underlying the security of several post-quantum schemes. It is the hardness assumption of the NIST second-round signature candidate Mirath and of the encryption schemes of Chatterjee et al.\ and Debris-Alazard et al.\ at Eurocrypt 2026. Moreover, it is ubiquitous in the cryptanalysis of multivariate schemes, among them the third-round candidates UOV, MAYO, QR-UOV, and SNOVA. In this work, we revisit the attacks on MinRank. On the combinatorial side, we improve the polynomial part of the kernel-search attack by sharing its linear algebra across guesses, which lowers its cost by 3 to 6 bits on the Mirath parameters and the Courtois challenges, and by up to 3 bits in combination with the hybrid approach. With the improved attack, we solved Courtois challenge~D, open since 2001: an instance over $\mathbb{F}_2$ with $19 \times 19$ matrices, $81$ unknowns, and target rank $10$, solved in 11434 CPU days, an estimated $2^{61}$ bit opetations. Our multi-threaded C++ code is publicly available. On the algebraic side, we show that the complexity of the Kipnis--Shamir (KS) attack is less understood than the literature suggests: the existing estimates rely on a generic Hilbert series that does not predict the rank of the Macaulay matrices of the KS equations. We prove a lower bound on the corank that explains the discrepancy, show that the attack requires a reduced instance with $k \leq m - r$, and derive corrected complexity estimates, which are $1$ to $24$ bits above the best other attack on every Mirath parameter set. We also extend the Support-Minors and Minors modelings with the field equations, which lowers their estimates over small fields: for $q = 2$ and $m = n = 22$, by 9 to 205 bits for Support-Minors and by 17 to 278 bits for Minors. The rank predictions behind the algebraic estimates are stated as assumptions and verified experimentally.

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

Falcon, a NIST-standardized post-quantum signature algorithm, offers compact signatures but relies on hardware-intensive floating-point arithmetic. Building on recent theoretical fixed-point formulations, we present a completely floating-point-free hardware architecture for SamplerZ, Falcon’s primary signing bottleneck. By utilizing zero-cost hardware bit-sliced retagging of fixed-point data, which software avoids due to instruction overheads, we enforce tighter data formats at every stage boundary without area or latency penalties. Furthermore, executing floor functions as trivial two's-complement arithmetic right shifts eliminates the complex floor-prediction and redundant data-paths required by floating-point designs. Implemented on UltraScale+ FPGA, our fixed-point sampler exactly matches all 1,024 official test vectors and requires 38% fewer LUTs, 21% less FFs and 36% less DSPs compared to the floating-point baseline, with 21% fewer cycles at a higher clock frequency. We also demonstrate that substituting the baseline ChaCha20 PRNG with lightweight NIST-standardized Ascon-XOF128 achieves further 2-3 × hardware resource savings with zero sampling latency overhead.

With deployment of standardized post-quantum cryptography well on the way, discussions continue about concrete choices of schemes and parameter sets. For example, while NIST standardized structured-lattice-based ML-KEM, European agencies like BSI and ANSSI favor unstructured-lattice-based FrodoKEM. Another discussion revolves around different approaches to hybrid deployments – either combining post-quantum schemes with "traditional" elliptic-curve cryptography (or RSA) or combining multiple different post-quantum schemes. The typical question for systems engineers to ask is what the "best" or "most conservative" approach is within a certain performance budget. In this paper we add a data point to this discussion by investigating how to scale ML-KEM to (much) higher security levels of the underlying MLWE problem. We first observe that increasing security simply by increasing the module rank $k$ quickly reaches a limit imposed by decryption failure probability. We then propose a generalization of the noise distribution, which enables scaling to much larger module rank and MLWE hardness, while preserving the essence of ML-KEM, most notably arithmetic in the ring $\mathbb{Z}_{3329}[X]/(X^{256}+1)$ and a simple and constant-time secret / noise generation. We select three concrete parameter sets of this high-security variant of ML-KEM, which we call Kaiburr. We present benchmarking results for optimized implementations of Kaiburr on 64-bit Intel CPUs and on the Asymmetric Cryptography Coprocessor (ACC) of the Pavona open-source silicon framework. Based on these benchmarks, we argue that, for example, a hybrid of FrodoKEM-976 and Kaiburr-1792 not only offers better performance than FrodoKEM-1344, it also offers protection against a broader range of hypothetical future attacks against (M)LWE.

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.

Enlarging lookup-table addresses does not hide smaller selectors when the complete public table factors through a core with distinct rows and distinct columns. We demonstrate this condition in WBSLT, a white-box AES design presented at NDSS 2026 that reports resistance to several structural attacks. In the released general generator, the joint output of each group of four first-round TypeII tables has an exact 16 × 16 quotient of its 64 × 64 address space. Mapping its row and column classes to observed addresses recovers the original nibble partition of each AES input byte. Public tables implementing encoded XOR supply compatible output coordinates. Under the generator’s strictly linear input decoder, two 16-point restrictions of each keyed AES S-box then identify its embedded key byte; independent exhaustive checks confirm this property for all 256 byte keys. Using public tables and traces of chosen encoded inputs, we recover every key in 200 general instances that passed 200,000 reference AES block tests, after a median of 146 and at most 221 inputs. Separate 200-instance cohorts of the released optimized C source and its one-line functional repair also yield every key; only the repair passes the AES tests. An adjacent-round adaptation recovers 20/20 exact keys on a paired cohort without reconstructing the nibble partition. On those instances, our first-round route uses fewer live trace queries and less public table data. The exact quotient provides a concrete test for selector partitions that survive address enlargement.

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.

We investigate the depth overhead of stretch-amplification for pseudorandom generators in the black-box model. We show that any black box construction of a PRG $H: \{0,1\}^m \to \{0,1\}^M$ which makes $\mathrm{poly}(n)$ queries to a PRG $G: \{0,1\}^n \to \{0,1\}^N$ in $d$ adaptive phases during each evaluation (and with a black-box reduction to the security of $G$) must satisfy: $M \leq (m + O(\log n)) \Bigl( \frac{N}{n - O(\log n)} \Bigr)^d$. This implies that the standard amplification procedure [GM'84, GGM'86] based on repeated composition of $G$ is essentially optimal. In particular, amplifying $n \mapsto n+1$ to $m \mapsto 2m$ requires depth overhead $d = \Omega(\frac{n}{\log n})$, and amplifying $n \mapsto 2n$ to $m \mapsto m^2$ requires depth overhead $d = \Omega(\log n)$; each of these bounds is tight up to a constant factor. As an immediate corollary we obtain tight lower bounds on the depth complexity of black-box constructions of PRFs from PRGs. Both of these problems (pertaining to amplification and PRF construction) have been studied in various prior works [V'05, MV'11, BJP'11, MV'15, BMM'24, ADV'26]. Despite progress on special cases in which the structure of the reductions is constrained, it was previously unknown whether completely parallel constructions ($d=1$) existed in every stretch regime. The kinds of amplification procedures we investigate have more recently found use outside of cryptography in the study of range avoidance ("Avoid") [K'21]. We show an analogous result in this setting: any black-box $\mathrm{FP^{NP}}$ reduction from an Avoid instance $G: \{0,1\}^n \to \{0,1\}^N$ to a second Avoid instance $H: \{0,1\}^m \to \{0,1\}^M$ which has "depth $d$" in the above sense must satisfy the same bound relating $n,N,m,M,d$. Using this impossibility result for Avoid, we construct an oracle relative to which $\mathrm{E} \not\subseteq \mathrm{NC}/\mathrm{poly}$ but $\mathrm{E^{NP}} \subseteq \mathrm{P}/\mathrm{poly}$. Our oracle separation implies that in the relativized setting, the bounded arithmetic theory $S^1_2$ cannot prove the existence of functions outside $\mathrm{P}/\mathrm{poly}$, even given as an axiom the existence of functions outside $\mathrm{NC}/\mathrm{poly}$.

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.

Information-theoretic MPC among $n$ parties with $t$ corruptions can securely evaluate a circuit $C$ with $O(|C| \cdot t/(n-t))$ online communication in the preprocessing model and $O(|C| \cdot t/(n-2t))$ communication in the honest majority setting. Damg{\aa}rd, Larsen and Nielsen (CRYPTO 2019) showed that both communication bounds are tight for inner products. Fully homomorphic encryption and other assumptions known to imply public-key cryptography beat both communication bounds, but the communication complexity with symmetric-key cryptography alone is less understood. For MPC with preprocessing, we prove that the same $\Omega(|C| \cdot t/(n-t))$ lower bound holds in the random oracle model, so a random oracle cannot reduce the online communication. For honest majority MPC relative to a random oracle, we present an $\Omega(|C|)$ communication lower bound that is matched by a new construction for degree-2 polynomials (including inner products) when $n = O(\log \lambda)$, beating the information-theoretic bound. We also study quantum MPC. First, we prove that information-theoretic protocols with quantum communication (and preprocessing) cannot reduce communication compared to their classical counterparts. Furthermore, we extend our lower bound for MPC with preprocessing to protocols with a quantum-accessible random oracle, but use only classical communication. In contrast, with both quantum communication and a post-quantum one-way function, we present a simple two-party protocol that evaluates the two-party instance of these circuits with $\mathsf{poly}(\lambda, \log |C|)$ communication, beating these lower bounds. Finally, such communication savings do not come for free. We prove that there exist circuits $C$ such that every blackbox protocol with $o(|C|)$ quantum communication must perform $\Omega(|C|)$ cryptographic operations.

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.

The Number Theoretic Transform (NTT) is a key component of polynomial multiplication in Kyber, making its efficient hardware implementation essential for post-quantum cryptographic applications. This paper presents two hardware architectures for Kyber polynomial arithmetic, supporting the NTT, inverse NTT (INTT) and point-wise multiplication (PWM) operations. The first architecture employs a single processing element (PE) to reduce hardware area, while the second uses two PEs to achieve higher throughput and efficiency. Both architectures incorporate a low-complexity modular multiplication and reduction method tailored to the Kyber modulus q = 3329, a unified butterfly unit supporting NTT, INTT, and PWM, and constant-geometry data access with dedicated address-generation algorithms. The dual-PE architecture is implemented without dedicated DSP blocks or BRAMs. FPGA implementation results demonstrate that the dual-PE architecture achieves the lowest area-time product and highest frequency among the evaluated state-of-the-art designs, while providing an effective trade-off between hardware area and execution time.

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.

We construct complete addition laws in extended coordinates for twisted Edwards curves \(E_{a,d}:ax^2+y^2=1+dx^2y^2\), where \(a,d\in K^\times\), \(a\ne d\), and \(\operatorname{char}K\ne2\). If \(t\in K\) makes \((t^2-a)(t^2-d)\) a nonzero nonsquare, the construction yields a \(K\)-complete formula valid for every pair of \(K\)-rational points. The proof describes the exceptional fibres through the difference morphism. Over finite fields of odd cardinality \(q>16\), such a coefficient exists for every nonsingular parameter pair, including the same-square-class cases with full rational two-torsion. We give full and mixed evaluation schedules. Full addition costs \(8M+D_c\) in split elementary models and \(10M\) or \(12M\), plus fixed-constant costs, in the same-square-class cases. Doubling costs \(4M+4S+\min(D_a,D_d)\), independently of coefficient selection. Here \(M\) denotes a general field multiplication, \(S\) a squaring, and \(D_c\) multiplication by a fixed \(c\in K\).

Let $E_{a,b}:Y^2Z=X^3+aXZ^2+bZ^3$ be a nonsingular short-Weierstrass curve over a field $K$ of characteristic different from $2$ and $3$. A nonvertical line $Y=mX+nZ$ has no $K$-rational point on the curve if and only if $x^3-m^2x^2+(a-2mn)x+b-n^2$ is rootless in $K$. We give coordinate changes and formulas for the corresponding $K$-complete Bosma--Lenstra addition law. An incidence count proves that such a line exists over every finite field in the stated characteristic. The classical five-multiplication cross-product identity reduces the output computation by one multiplication. For normalized horizontal, sloped, and depressed families, the full/full costs are $13M+5D+30A$, $13M+5D+33A$, and $13M+(2\text{ to }5)D+60A$, respectively. Horizontal normalization requires a nonzero cube parameter; the depressed family always contains a point-free line over $\mathbb{F}_p$ for $p\ge47$. The zero-line formula costs $11M+3D_a+2D_{3b}+28A$ and is complete over finite $K$ exactly when $\#E(K)$ is odd. We also give complete doubling formulas, account for changes of coordinates, and apply the five-product identity to published Hessian addition formulas.

Cryptanalytic extraction can expose proprietary neural network parameters, but unknown architectures and large parameter counts complicate recovery under hard-label access. Local class-pair rules offer a narrower target by making class-switching conditions explicit and predicting nearby labels under a specified sampling law. Distillation methods mainly return substitute models rather than explicit rules whose local agreement has been tested against the victim. We propose Distill–Probe–Extract to produce such rules without first identifying the victim architecture. Verified boundary events guide student training, and student gradients propose directions at boundary anchors refined through victim queries. Fresh hard-label queries then test the proposed rules, retaining validation inputs and victim labels for each accepted rule. On a digits multilayer perceptron and pooling convolutional networks, fixed-candidate comparisons isolate the savings from replacing victim-normal estimation with student gradients. For the multilayer perceptron, median recorded online cost decreases from 246 to 118 queries per attempt after student preparation. With preparation and failures counted, full Fashion-MNIST sessions produce 2.03–2.23 times Direct's accepted-rule count under the original validation gate at 320,000-call caps. At 320,000 calls, a separate student-level test on trained Blended watermarks yields 99.99% trigger agreement and 91.79% clean agreement, with all three seeds passing joint verification.

Cryptanalytic extraction (CEA) of piecewise-linear neural networks recovers hidden signatures and parameters by locating critical points or hard-label dual points that expose off-manifold geometry. Proposed mitigation methods include query monitoring, output perturbation, ownership verification, and extraction-aware training. Train to Defend (TTD) directly addresses CEA through extraction-aware training, but cannot protect an already-trained checkpoint without retraining. We propose Normal-Jet Masking (NJM), a post-training wrapper that leaves the source model unchanged. NJM calibrates a tangent–normal tube around protected data, keeps private normal-direction mask channels inactive inside the tube, and mixes their piecewise-linear activations into served outputs outside it. NJM targets the shared evidence-acquisition stage rather than one attack implementation: mask events enter both raw-logit (soft-label) critical finding and hard-label dual finding before downstream signature and parameter recovery. Across seven MLPs, NJM reduces raw-logit evidence F1 by 53.8–93.1%, raises query cost by 1.4–9.3×, and eliminates pure hard-label duals. On CNNs, it preserves at least 0.9993 agreement while lowering source precision. These results show that post-training geometric masking complements training-time hardening across soft- and hard-label CEA.

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.

Many privacy-preserving applications such as iterative machine learning training require executing ongoing computations over a secret state for long periods of time. While MPC enables secure computation, long-lived secret state is vulnerable to adaptive corruptions, requiring periodic share refreshes and committee rotation. In many settings, it is desirable for external parties to be able to verify that these state updates and rotations are performed correctly, but existing approaches for such public verifiability incur high overhead as they require MPC nodes to generate expensive proofs over secret-shared data. We propose Authenticated Outsourced Incrementally Verifiable MPC (IV-MPC), a framework for efficient public verification of long-running MPC computation. Our approach decouples private proof computation (run by MPC nodes) from public tasks within the proof generation that can be delegated to a single external prover $P^*$. To realize this architecture, we introduce three main components: (1) a Private-opening Polynomial Commitment Scheme (PoPCS) that lets an incoming committee prove they received the correct state shares without revealing the underlying data; (2) an efficient distributed proof system based on the sumcheck protocol and compressed $\Sigma$-protocols to verify state updates; and (3) a stateless handover technique that anchors committee transfers to a fixed state commitment, preventing proof sizes from growing over time. Combined with an incrementally verifiable computation (IVC) proof run by the external prover $P^*$, IV-MPC enables external auditors to verify correctness of MPC computation at every round with verification time asymptotically independent of the total number of epochs.

Unique signatures are digital signature schemes, where each message has exactly one valid signature. The uniqueness property typically comes at a price: Most unique signature schemes are known to have a security loss at least linear in the number of signature queries when aiming for existential unforgeability under chosen message attacks (EUF-CMA) security, which was shown to be inherent in the standard model by Coron (EUROCRYPT 2002) for signature schemes where public keys are verifiable (i.e., where it can be efficiently checked whether a public key has unique signatures). The only known tight unique signature schemes in the literature that support verifiable public keys are variants of chain-based signatures (CRYPTO 2017, FC 2018, EUROCRYPT 2022), which achieve tight security in the random oracle model. To achieve constant security loss, however, these schemes require $\log q$ calls of the random oracle to sign and verify, where $q$ is an upper bound on the number of signatures generated using the scheme. In this work, we provide the first tight unique signature scheme with verifiable public keys which requires only a constant number (namely, six) random oracle queries to sign and verify. Specifically, we provide a general transformation akin to hash-and-sign which transforms a signature scheme with much weaker security (a variant of random unforgeability) into an EUF-CMA secure scheme. Signatures of our resulting scheme consist of at most 3 sub-signatures in parallel. Furthermore, we consider tightness in the multi-user setting, where the adversary may query signatures relative to many public keys, before deciding for which to forge. In this setting, we provide two constructions which achieve (1) a tight signature scheme, secure against semi-adaptive corruptions (i.e., where the adversary has to decide whether to corrupt a public key *before* making any signature queries relative to this key), and (2) a tight few-time signature scheme, secure against adaptive corruptions, where the scheme's setup is allowed to depend on an a-priori polynomial bound on the number of queries that the adversary has access to. These are the first unique signature schemes which are tightly secure in the multi-user model.

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.

S-boxes serve as essential nonlinear building blocks in symmetric-key cryptography, where their cryptographic properties and hardware implementation costs jointly dictate the security and efficiency of lightweight primitives. This paper studies the construction and classification of minimum-latency 5-bit APN (Almost Perfect Nonlinear) permutations under a prescribed gate-delay model, using exact minimum latencies of Boolean component functions. Under the fixed gate-delay model of the NanGate 45nm standard cell library, we partition the search space into input-variable permutation (IP) equivalence classes to establish a comprehensive minimum-latency database covering all 5-input balanced nonlinear Boolean functions. This database delivers exact minimum latencies and gate-level implementations for all equivalence classes up to a latency of 150ps, while guaranteeing strict lower bounds on latency for classes exceeding that threshold, combining property filtering with circuit synthesis. We search the five affine equivalence classes of 5-bit APN permutations. For each affine transformation of the input, we use exact component-function latencies to select components with linearly independent masks and choose their polarities, obtaining S-box circuits without repeating gate-level synthesis for each candidate. Exhaustive search with latency-preserving input-variable permutation reduction establishes a minimum latency of 126.745ps over all 5-bit APN permutations under the prescribed gate-delay model, with explicit constructions attaining this minimum in every class.The classification results give the optimized latency distributions and numbers of optimal IP classes of input-affine transformations within each affine class. Comparisons with selected 5-bit S-box implementations under the same model show simultaneous reductions in some cases: latency decreases by $10.20\%$--$29.18\%$ and normalized gate area by $5.37\%$--$27.69\%$, while preserving the original S-box mappings.

Accountable tracing signatures (ATS), introduced by Kohlweiss and Miers (PoPETs 2015), classify each group member (user) as either traceable or non-traceable. A traceable user corresponds to one in conventional group signature schemes whose identity can be revealed by the opener from a signature, whereas a non-traceable user cannot be identified from any signature they produce. The opener, who issues a witness, can certify a user's status via the Account algorithm. In this paper, we formalize accountability soundness, which ensures that no two witnesses can simultaneously certify a user as both traceable and non-traceable. We show that the Kohlweiss-Miers ATS scheme admits conflicting witnesses that violate this property. Since accountability is a fundamental aspect of ATS, as reflected in its name, such conflicting witnesses undermine the intended guarantees of the primitive. To address this issue, we propose a patched version of the Kohlweiss-Miers ATS scheme that provides accountability soundness. We also discuss the applicability of our attack to the lattice-based ATS scheme (Ling et al., CT-RSA 2019) and the isogeny-based ATS scheme (Shaw-Dutta, Indocrypt 2021), together with preliminary investigations of possible countermeasures. We emphasize that all our attacks fall outside the original security models.

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.

We give a method to publish data on Bitcoin and to verify properties of that data on Bitcoin itself, against a publisher who may lie. The data is a FlatMerkle file – a structured byte string whose ordinary SHA-256 supports logarithmic inclusion proofs and logarithmic proofs of malformation – placed in a transaction's annex or, at four times the cost but relayable by Bitcoin Core, in an output. We show that the publisher's ordinary Taproot signature, with a suitably chosen signature-hash type, binds the publisher to the published data in a form that a dispute can authenticate with a single SHA-256 compression plus the signature check, or with three compressions when no annex is used. Claims about the data, and claims about such claims, are published as proof messages in two formats: a plain encoding, refuted by revealing it whole, and a traced encoding that stores the verifier's output after each level, so that any false message is refuted by revealing at most five of its elements. The format, chosen by a cost model that weighs challenge bytes against published bytes, is fixed by public context so that no message can be read in two formats; chains of claims about claims settle at four logical elements. A dispute thus reduces to a few dozen SHA-256 compressions and one Schnorr verification per commitment – too large for Bitcoin Script, but small enough to adjudicate with an interactive bisection game, a chunked script in the manner of BitVM2, or a garbled circuit. The same technique verifies any locally refutable verifier, one whose every rejection is witnessed by a single check over a few words of a canonical trace. In a FlatCheck, the prover publishes only the proof; the trace, the verifier's intermediate values, is published only if a challenger asks for it, and the dispute then examines the single check he names. When the verifier splits into groups that each read a few parts of the proof, a challenge forces the trace of one group only. We give two examples: a toy L2 of signed transfers, whose 512-transfer batches cost 12,200 vbytes to claim, and a Bitcoin header-chain light client verified on Bitcoin itself, which claims a retarget period of 2,016 headers in 45,200 vbytes; a dispute over a local check costs about 37,500 and 49,200 vbytes, and one over a malformed trace about 77,100 and 99,800, independently of the number of groups. Verifying STARK proofs is another application. We also remove FlatMerkle's restriction to power-of-two sizes without padding.

We present an experimental cryptanalysis of the RLCE cryptosystem at the heretofore secure $w=n-k$ parameter regime. Our attack relies crucially on the recent Ghoshal--Ishai--Jain--Sun (GIJS) distinguisher The attack shortens the public key at random positions, runs the GIJS distinguisher with \emph{every} column as hold-out, and uses this distinguisher to identify twin pairs based on how they appear across trials. Three pairs so identified are unmixed by a root-finding cascade, and Sidelnikov--Shestakov on the resulting $k \times (k+3)$ pure matrix recovers the key. We experimentally verify our attack by breaking the ID-0 (128-bit) in 30.5 core-hours (about 3 hours of wall time) on a standard higher-end laptop.

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.

Leakage-resilient compilers transform any computation so that physical leakage from its implementation reveals nothing beyond its input-output behaviour. In this work, we investigate this question in the well-motivated continual memory leakage (CML) model, that captures a variety of relevant real-world side-channel attacks and subsumes several other well studied models in the leakage domain. In this model with two independently leaking components (at least two are necessary), all known general compilers tolerate only an inverse-polynomial leakage-rate. We give a compiler with constant leakage-rate, in the hybrid model with a simple inputless leak-free sampler as in Dziembowski and Faust (TCC 2012). It protects any deterministic computation on a fixed secret with public inputs and outputs, and comes with a transfer theorem: any security game in which the adversary has an oracle for the computation remains secure when every oracle call is replaced by a compiled evaluation that leaks continuously. Our compiler uses no computational assumption. Our main application is public-key encryption. Applied to the decryption of any IND-CCA2 secure PKE, the compiler gives IND-CCLA2 security, i.e. CCA2 security even when every decryption leaks, including after the challenge ciphertext, with the same public key, ciphertexts and encryption algorithm. Instantiating the base scheme gives such PKE from LWE and from LPN improving upon the previous best post-quantum constructions in this model, which supported only inverse-polynomial leakage-rate. We also obtain signatures, PRFs and MACs with constant leakage-rate via a natural generalization. Our key idea is to pack the entire configuration of a universal machine into one element of a large extension field, so that any computation keeps only a constant number of inner-product encodings in memory at any time, each for only a constant number of rounds. Our techniques are inspired by packing techniques in homomorphic encryption adapted to a completely different context. We are optimistic that our techniques will find other applications.

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.

Zero-knowledge membership accumulators are conventionally tailored for slowly growing sets with frequent proof generation, creating severe efficiency bottlenecks for modern compliance architectures. Governance-driven applications like FATF customer due diligence, eIDAS 2.0 wallet issuance, and MiCA VASP authorization invert this structure. In this regime, rosters are ingested at an enterprise scale, while proofs are requested selectively. To resolve this mismatch, we introduce Polynomial Equation Batching (PEB), a membership accumulator for onboarding heavy workloads. PEB represents up to 128 members per batch as a characteristic polynomial and hashes its coefficients via Poseidon, seamlessly scaling to arbitrarily large populations through parallel batching. We present two variants: PEB-A, which maps member secrets directly to polynomial roots for maximum performance, and PEB-B, which hashes secrets in-circuit for hardened security. Implemented in Noir and Barretenberg on BN254, and evaluated for up to 1,048,576 members, PEB provides significant performance improvements. Compared to incremental Merkle trees, PEB-A achieves up to a 149.07x mean speedup in per-user initialization while incurring a modest 33.87% proof-generation overhead. Additionally, against static Merkle trees, PEB-A delivers a 15.71x speedup during setup. By shifting off-circuit overhead from hash evaluations to field multiplications, PEB provides a highly efficient, scalable solution for real-world zero-knowledge compliance systems.

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.

For $A,B\in\text{GL}(\mathbb{F}_p)$, a Cayley hash $\text{HM}(w)$ maps a bit string $w \in \{0,1\}$ to the corresponding product of $A$ and $B$. We construct collisions by finding two palindromes whose matrix products commute. A symmetric form shared by the two generators places the hash of every palindrome in a three-dimensional subspace containing the identity. Two such hashes commute when their traceless parts are proportional, which defines a class map with $p+2$ values, so the pigeonhole principle gives collisions of $4\lceil\log_2(p+3)\rceil$ bits. Under a uniformity heuristic, a dictionary search finds such a pair after about $\sqrt{\pi p/2}$ class evaluations. Adding one bit to each half-message gives an expected bound of $O(\sqrt p)$ evaluations, with no assumption on how the classes are distributed. When the common form is singular, the generators are simultaneously triangular and the same argument applies to ordinary words. For CHAMP-512 and CHAMP-1024, the heuristic search finds collisions of $512$ and $1024$ bits after about $2^{64}$ and $2^{128}$ class evaluations, and the one-bit-longer, distribution-independent variant finds collisions of $516$ and $1028$ bits at the same leading cost. This matches the asymptotic cost of an earlier commuting-product search for CHAMP, whose messages have $O(\log^2(p))$ bits, and improves on the bound of about $p$ given by an earlier palindrome restriction. For every pair over an odd prime field, this also shortens the collisions of the general algorithm of Mullan and Tsaban from $O(\log^2(p)/\log(\log(p)))$ to $4 \lceil \log_2(p+3) \rceil$ bits. Since the argument applies to every pair $A,B$, no pair of generators gives a $2\times2$ Cayley hash over $\mathbb{F}_p$ with collision resistance greater than $O(\sqrt p)$. We give an explicit proof-of-concept collision for the CHAMP matrices at a $36$-bit prime, and prove that every sufficiently short message can be recovered from its digest for the main CHAMP pair. To close, we demonstrate that since reversal and symbol exchange act as sign changes on quaternion coordinates, the alternative CHAMP pair possesses a much greater degree of symmetry, but do not yet see how to utilize this to find collisions below the square-root bound.

We present a new concrete unified distance analysis of three accumulate-type error-correcting codes over any finite field, specifically the Repeat-Accumulate (RA), Repeat-Accumulate-Accumulate (RAA), and Expand-Accumulate (EA) codes. For message length $k$, codeword length $n$, finite field size $q>2$, and target relative minimum distance $\delta$, we give new upper bounds on the probability that each of the above codes do not have minimum distance at least $\delta$. Our bounds are concrete and explicit: they do not rely on $n$ or $q$ being sufficiently large. We present (multiple) closed-form upper bounds on the failure probability for each code, and complement these bounds with asymptotic analyses that (nearly) match prior-known asymptotic bounds. Our technical core is a new fine-grained union bound for accumulate codes, which may be of independent interest, that examines inputs to the accumulator from a purely distributional perspective, deriving properties that are necessary for an input vector to accumulate to a targeted output weight, and analyzing the probability the input distribution achieves these properties. This fine-grained union bound generalizes the input-output weight enumerator approach used by many prior works. Our concrete analysis shows that (1) the RA code has concretely small distance (a maximum of $\delta\leq 2.4979\times10^{-8}$ for $k=2^{40}$ and $q=2^{32}$, except with probability $2^{-60}$), and (2) the RAA and EA codes achieve somewhat large concrete distance for smaller field sizes $q \leq 2^{32}$. Concretely, for rate $k/n = 1/4$, $k\in\{2^{40},2^{50}\}$, and $q=2^{8}$, the RAA code has distance $\delta=1/8$ except with $2^{-60}$ probability, whereas the rate $1/2$ and $1/4$ EA code for the same $k$ and $q=2^{4}$, respectively, has distance $\delta\leq 0.0689756$ and $\delta \leq0.232955$ except with probability $2^{-60}$. For fields of size $q\geq 2^{32}$, under our concrete bounds, all codes experience a sharp drop-off in attainable minimum distance, as our analysis targets (small) fixed $q$.

Privacy-preserving smart contracts face a scalability problem. In account-balance-vector designs, hiding which accounts changed requires that every transaction perform an indistinguishable update over the global state, so validators pay work linear in the number of accounts for every private transfer. UTXO systems avoid this by validating local spends, but do not provide the same account-style programming model. We argue that the usual "account vs.~UTXO" framing conflates state representation and execution model, two choices that can be made separately. Miden, an Ethereum Layer 2, separates them. It uses persistent accounts for programmability, asynchronous notes for value transfer, and client-side proving for execution. Validators verify proofs and update commitments without re-executing transactions or accessing uninvolved state. The result is an account-based platform with private transfers and private computation, while keeping validator work per transaction logarithmic in the number of accounts.

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.

The Fiat-Shamir transform converts public-coin interactive arguments into non-interactive arguments (NARGs). Its security is typically analyzed in the random-oracle model, while implementations instantiate the random oracle with structured hash constructions. Standard indifferentiability is the natural abstraction for justifying this replacement. Chiesa and Orru (TCC ’25), however, showed that standard indifferentiability does not generally preserve the information and reset behavior needed by common Fiat-Shamir extraction arguments, and proposed stronger notions of indifferentiability to bridge this gap. We show that standard indifferentiability can nevertheless be retained as the oracle-replacement abstraction. For knowledge soundness, we give generic transfer theorems for three extraction interfaces: proof-only straight-line extraction follows from standard indifferentiability alone; transcript-dependent extraction additionally requires transcript reconstruction; and rewinding extraction requires reconstruction for rewinding, preserving simulator behavior across invocations with the same hidden randomness. Our results apply to worst-case polynomial-time extractors. Moreover, we show that the rewinding requirement is inherent: assuming discrete-logarithm hardness, we construct a perfectly indifferentiable construction and fixed prover admitting error-free rewinding extraction in the ideal world, while every polynomial-time construction-world extractor succeeds only with negligible probability. We instantiate our framework for tagged prefix-free Merkle-Damgard and a fixed-output permutation sponge. The former admits exact transcript and rewinding reconstruction, while the latter admits exact transcript reconstruction and rewinding reconstruction with negligible statistical error incurred only once, independently of the number of restarts. For zero knowledge, we give a semantic formulation where one persistent simulator jointly generates the proof and public-oracle interaction. Here, standard indifferentiability alone yields a generic transfer theorem, requiring neither reconstruction property and incurring only the indifferentiability error. Thus standard indifferentiability provides a common oracle-replacement abstraction for knowledge soundness and semantic zero knowledge, with extraction-specific requirements isolated as separate simulator properties.

We revisit the basic construction of polynomial evaluation based hash function, which we call Poly, over binary extension fields $GF(2^n)$, where $n=64k$ and $k\geq 2$. Unlike GHASH, the NIST standard polynomial evaluation based hash function for $n=128$, Poly does not perform the unnecessary bit reversals of each $n$-bit block, and consequently is faster than GHASH. Further, Poly differs from Polyval, -- a faster alternative to GHASH, -- in that Poly performs usual reduction, while Polyval performs Montgomery reduction. We identify suitable choices of the field representing irreducible polynomials which make usual and Montgomery reductions efficient. We provide detailed algorithms, and associated proofs of correctness for both kinds of reductions. Based on the algorithms, we report carefully optimised assembly implementation of both Poly and Polyval for $n=128,256$ and $512$. Our theoretical analysis and experimental timing results show that for $n=128$, Polyval is faster than Poly, while for $n=256$ and $512$ (as well as for higher values of $n$), Poly is faster than Polyval. The cases $n=128$ and $n=256$ are of current relevance due to the ongoing NIST process for developing cryptographic accordions.

Anamorphic encryption and signatures deliver a hidden message through a normal-looking ciphertext or signature. We move from hidden messages to hidden knowledge claims and introduce anamorphic proofs of knowledge, in which a single proof certifies its normal statement publicly while convincing a designated checker that the prover knows a witness for a separately registered anamorphic statement, such as a long-term credential. Our construction reuses a commitment the normal prover already makes to its own randomness. The prover adds a secret mask to the anamorphic witness and uses the sum as those coins, so the existing commitment carries the anamorphic statement while the public statement, proof format and length, and normal verifier remain unchanged. Two properties of the normal proof system suffice: its randomness commitment must be extractable, and the complete proof must be simulatable at a commitment that the checking key fixes in advance, which normal zero knowledge does not provide. The resulting normal and anamorphic modes are indistinguishable to an external observer, even given both witnesses and the normal prover's actual random coins. The same opening extractor gives anamorphic knowledge soundness and two guarantees against the checker: it cannot produce an accepting proof for a statement registered independently of its key, and it cannot produce a proof and witness for a statement of its own choice, in both cases at an unused label and after obtaining honest proofs at other labels. The checker learns neither witness. We instantiate the construction in random-base Compressed $\Sigma$ and in Bulletproofs with range aggregation in the random-oracle model. Finally, we show that three-move protocols with witness-assisted challenge transfer, including Schnorr and uncompressed representation protocols, cannot support the primitive in a local-checking model.

Quantum computing threatens public-key cryptography, motivating post-quantum signature standardization. MAYO, a multivariate Round 3 candidate in NIST's additional signature process, offers compact keys and signatures. However, prior GPU implementations do not fully exploit parallelism within each MAYO operation: equation-slice partitioning serializes independent matrix work, while signing requires frequent synchronization among threads during linear-system construction and elimination. We present SpreadMAYO, a high-throughput GPU implementation of MAYO Round 3 that exposes greater parallelism and reduces synchronization through finer task partitioning and a revised signing pipeline. SpreadMAYO distributes matrix contractions across rows, output positions, and 64-bit limbs while reusing operands in registers. Each limb packs sixteen GF(16) coefficients; native 32-bit operations process its halves without lookup tables. For signing, threads privately accumulate columns with deferred polynomial reduction, transpose packed columns into rows using warp shuffles, and eliminate rows below each pivot in parallel. Additionally, we employ a hybrid AES design to accommodate different workloads and fuse key expansion with matrix computations to reduce global-memory traffic. On an NVIDIA GeForce RTX 4090, SpreadMAYO outperforms the Round 3 adapted GPU baseline by 2.33–3.71× in key generation, 4.40–6.93× in signing, and 3.42–5.13× in verification, reaching up to 10.75× in repeated-key server signing.

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.

Card-based cryptography performs secure computation with physical cards, where a bit is usually encoded by two cards but can also be encoded by a single card. We study mixed encoding, in which one player gives a single-card commitment and the other a two-card commitment, for perfectly secure protocols with finite runtime and public actions. Mizuki (Theoretical Computer Science, vol.~622, 2016) proposed an AND protocol with mixed encoding as a building block for the conjunction of many variables. To give a single-card commitment, a player chooses one of two cards of different types and must keep the other card hidden. We call this card a frozen card and include it in the number of cards. We show that a secure protocol in committed format never turns over a single-card input, and use this to determine the functions that can be computed when all inputs are single-card commitments and to characterize those that can be computed with mixed encoding, which include AND but not XOR. We prove that Mizuki's five-card protocol is card-minimal. No AND protocol with mixed encoding uses four cards, including the frozen card, even with arbitrary shuffles and a non-committed output. For formal verification, we express the existence of a protocol as a quantified Boolean formula (QBF) in which security is a quantifier alternation, and confirm this lower bound with QBF solvers for a class of protocols. We discuss the number and type of shuffles, and analyze Mizuki's protocol under injection attacks that change only the input.

Scalable oversight asks how a weak verifier can check the outputs of computations performed by more powerful AI systems. One proposed approach uses relativizing interactive proofs, in which a weak verifier checks the output of a complex oracle-aided computation by interacting with one or more powerful provers. A prominent example is debate, which is highly efficient but assumes that one of two powerful AI models, or provers, is truthful. For certain classes of oracle-aided computations, this assumption can be removed, but at substantially greater computational cost. In this work, we introduce \emph{rewindable interactive proofs} (RIPs), a new model of relativizing interactive proofs for scalable oversight. In an RIP, the verifier may rewind the prover to an earlier state of the interaction and continue from there. This is possible when the prover is an AI model, since the verifier can save a snapshot of the model's state and later restore it. We construct a relativizing RIP for computations whose outputs are robust to changing a small fraction of oracle answers. Our construction is more efficient than prior relativizing proofs that do not assume a truthful prover, and it uses no cryptography. In our construction the honest prover runs in time linear in that of the original computation, and the verifier, after a one-time preprocessing step, runs in time nearly linear in the input length (which can be much smaller than the computation itself). We implement our protocol, report a preliminary MNIST experiment, and show that an RIP can be faster than a state-of-the-art deployed proof system. RIPs may be of independent interest. Rewinding is possible whenever the verifier controls the prover's machine, for example when the prover runs on trusted hardware or in a virtual machine whose state can be checkpointed.

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.

PRISM is an isogeny-based digital signature whose security relies on the problem of computing large prime degree isogenies from a supersingular elliptic curve of unknown endomorphism ring. In this paper, we design SPIDER, a digital signature that builds on a sigma protocol which when given a supersingular elliptic curve $E$, proves the knowledge of an isogeny $\phi: E\rightarrow E'$ of prime (or non smooth) degree $d$. SPIDER can hence be seen as a proof of knowledge of a PRISM signature. The latter observation allows us to combine SPIDER and PRISM to obtain an Identity-Based Signature (IBS) which we denote by SPIDER-IBS. SPIDER-IBS is the most efficient and the most compact isogeny-based IBS scheme, as all its predecessors are based on isogeny group actions.

SM3 is a 256-bit cryptographic hash function specified in the Chinese national standard GB/T 32905-2016 and the international standard ISO/IEC 10118-3:2018. In this paper, we present practical collisions for 22- and 23-step SM3 with the standard initial value. Compared with the 20-step collision result of Mendel et al. (2013), our constructions cover two and three additional steps, respectively. The time complexities are approximately \(2^{52.4}\) and \(2^{54.5}\) evaluations of 22- and 23-step SM3, respectively. We also present a semi-free-start collision for 24-step SM3.

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.

Registered functional encryption removes the trusted authority bottleneck of standard functional encryption by allowing users to register their own public keys, with a transparent aggregation procedure producing a compact master public key. On the other hand, certified everlasting deletion enables a recipient to produce a classical certificate guaranteeing that a ciphertext has been information-theoretically destroyed, even against computationally unbounded adversaries. In this work, we initiate the study of registered functional encryption with certified everlasting deletion (RFE-CED), combining both properties for the first time. We define the syntax and security of RFE-CED, capturing two complementary guarantees: everlasting privacy, which bounds the trace distance between residual adversarial states after certified deletion, and post-verification indistinguishability, which ensures the adversary cannot distinguish the encrypted message even after the deletion certificate is verified. To construct RFE-CED, we also introduce public-slot registered functional encryption (PS-RFE) as a building block, in which each registered function takes both a secret and an arbitrary public input. Combining PS-RFE with a pseudorandom and authenticated BB84 encodings, we obtain a secure slotted RFE-CED scheme with the help of an interactive version of certified everlasting lemma.

Predicate encryption extends attribute-based encryption by providing fine-grained access control while hiding the attribute associated with a ciphertext beyond what the secret keys held by an adversary necessarily reveal. Batched identity-based encryption enables authorization with respect to a designated collection of identities. We introduce batched threshold predicate encryption (BT-PE), which combines batch-scoped authorization, expressive predicate-based access control, and threshold decryption. We give a lattice-based construction supporting polynomial-size arithmetic-circuit predicates, compact batch digests, and compact per-party key shares. Decryption is possible only when the encrypted attribute belongs to the authorized batch, satisfies the required predicate, and a sufficiently large set of parties participates. We prove correctness and query-selective one-sided security under the $\ell$-succinct LWE assumption, together with standard assumptions on digital signatures and compute-and-compare obfuscation.

Batched identity-based encryption (BIBE) compresses a bounded set of identities into a succinct public digest, and provides a single secret key for decrypting ciphertexts associated with identities in the set. We introduce batched identity-based encryption with succinct publicly verifiable subset deletion (BIBE-SPVD), which allows a holder of polynomially many quantum ciphertexts to certify deletion of any chosen subset using a single succinct classical certificate while preserving the usability of the remaining ciphertexts. We first construct a classical BIBE from identity-based encryption with puncturable master secret key, somewhere statistically binding (SSB) hashing, and indistinguishability obfuscation. We then equip this scheme with publicly verifiable certified-everlasting deletion, using a generic compiler specialized to the BIBE functionality. Finally, individual deletion certificates are aggregated using a somewhere-extractable batch argument. For each ciphertext position, the corresponding statement requires a valid deletion certificate precisely when that position belongs to the deleted subset. The identity digest and batch key remain succinct, and for \(N\) ciphertexts the aggregate deletion certificate has size \(poly(\lambda,\log N)\), independent of the number deleted.

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

A ratio-based ring oscillator physical unclonable function (ROPUF) provides high reliability and is capable of extracting multiple bits from a single ring oscillator pair. However, the derivation of the response bits from such PUFs and the assessment of their randomness have relied only on empirical statistical tests. This paper introduces a novel, mathematically derived closed-form statistical model that characterizes the counter value distribution of the ratio-based ROPUF and formally describes the behavior of this PUF design. We empirically validate the model's assumptions using a large-scale real-world ring oscillator measurement dataset of 218 Xilinx Artix-7 FPGAs. We demonstrate that this statistical framework enables theoretical quantification of response entropy of the ratio-based ROPUF. Furthermore, the model unlocks the use of advanced bit derivation methods, such as Equiprobable Quantization and Two-Metric Helper Data schemes. These were previously inapplicable to this PUF architecture, and we empirically show on the real-world dataset that they achieve better combinations of PUF reliability, randomness, and bit yield than the original counter-based derivation.

We study short collisions in salted Merkle-Damg{\aa}rd (MD) and Sponge under the query-bounded preprocessing model introduced by Ghoshal and Tessaro (CRYPTO '23). The adversary makes at most $T_1$ oracle queries before a random salt is revealed and at most $T_2$ queries afterwards, and must output two colliding messages of at most $B$ blocks. Our main result is a separation between the two constructions. Let $N=2^n$, give MD and Sponge matching $n$-bit salts, message blocks, and outputs, and set $T_1=\Theta(N/T_2)$ with $T_2=o(\sqrt N)$. For Sponge, there is an attack that finds a collision with constant probability using only three-block messages. In contrast, every MD adversary restricted to $B=o(T_2)$ blocks succeeds with probability at most \[ O\left(\frac{B}{T_2}+\frac{T_2^2}{N}\right)=o(1). \] Thus, under the same query budgets, three blocks suffice for Sponge, while every MD adversary with $B=o(T_2)$ blocks has success probability $o(1)$. On the MD side, we prove an upper bound for arbitrary block bounds $B$. The proof uses a simple graph argument that distinguishes collisions already present in the preprocessing transcript from those that can actually be reached by a short computation starting from the subsequently sampled salt. This extends query-bounded preprocessing analysis beyond the previously understood one- and two-block cases. On the Sponge side, we give a three-block attack that uses inverse permutation queries to make one precomputed collision useful from many different capacities. We complement the attack with a matching upper bound in a range containing the separation. In this range, allowing longer messages gives no asymptotic improvement: the optimal Sponge preprocessing advantage is already attained with at most three blocks. Overall, our results show that collision length interacts fundamentally differently with preprocessing in the two constructions: under matched parameters and identical query budgets, Sponge admits constant probability three-block collisions, whereas MD does not achieve constant success for any $B=o(T_2)$.

We study time-space tradeoffs for finding short collisions in Merkle-Damg{\aa}rd~(MD) hashing in the quantum auxiliary-input quantum random-oracle model~(QAI-QROM). An adversary may preprocess the compression function into $S$ qubits of arbitrary oracle-dependent quantum advice and, after receiving a fresh salt, make $T$ superposition queries to find a collision consisting of at most $B$ blocks. Previous quantum analyses gave an $\widetilde{O}(ST^3/N)$ security bound for MD collisions with classical advice. Unlike the classical theory of short MD collisions, however, this bound is insensitive to the collision length $B$: existing quantum techniques did not exploit the combinatorial structure forced by a short collision. We develop a structure-sensitive compressed-oracle analysis that overcomes this obstacle. For two-block collisions, we prove an upper bound \[ \widetilde{O}\left(\min\left\{1, \frac{ST^2+T^3}{N}\right\}\right), \] even against arbitrary quantum advice. For $M=N$, together with the known attack, this gives a tight characterization up to logarithmic factors, closes the previous factor-$T$ gap in the preprocessing term, and resolves an open problem of Akshima, Guo, and Liu~(CRYPTO '22, JoC '24). For general $B\le T$, we show in the regime $(2S+1)(T+2B)^3\le N$ that the success probability is at most \[ \widetilde{O}\!\left(\min\left\{1, \frac{ST^2B+T^3}{N}\right\}\right). \] Thus, when $B\ll T$, the preprocessing term improves over the previous $ST^3/N$ bound by a factor of roughly $T/B$. Motivated by the tight two-block result, we propose the $ST^2B$ conjecture, asserting that $ST^2B=\widetilde{\Theta}(N)$ is the correct constant-success tradeoff for short MD collisions in the regime $T^3=o(N)$.

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.

Small moduli support compact polynomial representations in lattice-based key encapsulation mechanisms (KEMs), including BAT (TCHES 2022) and END (ASIACRYPT 2026, to appear). However, compact encodings can be costly to convert, and uniform generation must account for both coefficient-extraction cost and random-bit demand. Incomplete number-theoretic transforms also leave residual polynomial products. To address these costs, we exploit the structure of moduli 257 and 769 to improve encoding, uniform public polynomial generation, and polynomial multiplication. At $q=257$, we introduce zero-selector encoding: zero payload bytes locate ambiguous coefficients, and selector bits resolve their values. We analyze selector capacity, overflow, and key-generation retries. For $n=1024$, a 1033-byte configuration has overflow probability at most $2^{-128}$ under independent uniform coefficients. Checked AVX2 decoding takes 213 cycles, compared with 2203 cycles for BAT's 1040-byte format. At $q=769$, we lower conversion costs using an existing compact radix format at the same encoded length as BAT. We specialize rejection sampling to simplify coefficient extraction at $q=257$ and reduce random-bit demand at $q=769$. At $(q,n)=(769,1024)$, expected candidate-bit demand decreases by 24.39\% relative to direct 10-bit rejection. Four-polynomial generation uses 7.14-13.21\% fewer AVX2 cycles. For residual multiplication, proven range bounds justify omitting strict input-centering corrections, while register scheduling reduces stack accesses. We integrate the public-key codecs and multiplication components into BAT and END. Across the tested C and AVX2 implementations, encapsulation costs decrease by $39.93-55.25\%$ in BAT and $41.36-48.84\%$ in END. The corresponding decapsulation reductions are $5.42-8.55\%$ in BAT and, for END, $23.99-45.89\%$ in C and $6.98-8.04\%$ in AVX2. END AVX2 gains mainly come from the public key codec. These results quantify the effect of modulus-specific optimizations on complete component and KEM costs.

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.

Storage encryption motivates tweakable enciphering schemes, which encrypt entire multi-block data units without length expansion and use a public tweak to identify their context. We revisit PEP (FSE 2006) and TET (CRYPTO 2007), two Hash-ECB-Hash schemes that combine parallel block-cipher calls with invertible mixing, and present classical distinguishing and plaintext-recovery attacks. For PEP, we exhibit a fixed public field satisfying the published parameter-selection rule whose generated position coefficients repeat. This yields a two-query algebraic distinguisher and recovery of a secret tweak-derived value using one encryption query. For the same instance, we recover target plaintexts over a specified range of complete-block lengths using at most nine encryption queries and one decryption query. Our PEP success bounds assume a uniformly random secret permutation and independently fixed target tweaks and plaintexts. For TET, we analyze two corrections of a previously reported mismatch between encryption and decryption. Both admit two-query distinguishers on messages with a partial final block. For tails of at least two bits, we obtain deterministic plaintext recovery using two decryption queries in one correction, or two encryption queries and one decryption query in the other. These TET attacks hold for every data permutation and valid parameter choice. The results expose failures of concrete coefficient generation and partial-block processing, and identify requirements for repairing these constructions.

A low-memory prover must control sumcheck tables, sparse accesses, commitments and proof assembly. We present Weir, a Shockwave-derived protocol with a complete read-write (RW) index-and-prove schedule. The schedule restores sparse request order, retains commitment state through later openings and assembles the proof externally. These steps preserve the direct RAM prover's canonical bytes across buffer choices, with a common verifier. Under an external-query-tape model, the schedule uses $O(B+\log T)$ field RAM, constant digest RAM and polylogarithmic auxiliary RAM. Algebraic work and record traffic are quasilinear; oracle-query byte work is charged separately. A classical random-oracle analysis bounds knowledge error. Fused Split-Butterfly-Merge removes $n-1$ materialized transform passes at length $2^n$. Its ordered routing contract extends to multiplicative-coset Reed-Solomon (RS) and recursive foldable encoders; component checks match reference codewords, traffic counts and RS fold states. In a fixed 64 MiB worker-cap grid, RW completes all tested matrix and Poseidon inputs; RAM completes matrix dimension 8. Within the matrix grid, the largest RW point has 64 times as many padded constraints as that RAM point, using 3.33 MB prover RSS and 9.51 minutes index+prove. We report latency, external payload, query bytes, proof size and verification time for this offline operating range.

Recent quantum resource estimates over prime fields have largely focused on prime order elliptic curves. We implement modern affine circuit techniques on the widely deployed composite order curve, Curve25519, and obtain a scalar circuit using 47,199,530 CCX gates and 1,189 peak logical qubits. This uses approximately 35% and 18% fewer gates than Schrottenloher's published space- and gate-optimized secp256k1 circuits, respectively. We separate three contributions. First, we apply established arithmetic and signed table techniques to Curve25519. In a comparison using the same arithmetic framework and signed half tables, its field and subgroup parameters, together with the chosen GCD iteration budgets, save 2,218,944 CCX gates relative to secp256k1. Second, we adapt odd signed digit recoding to quantum windows using fixed output translations. This saves a further 15,204 CCX gates and also applies to prime order curves. Third, we combine nonzero digits with a fixed 8-torsion offset point to keep the accumulator outside the lookup points' subgroup. With zero slope support and exact field arithmetic, this yields an exception-free addition schedule and nonzero denominators during slope uncomputation, without additional quantum point additions. Our counts include the full scalar schedule, lookup and cleanup. The corresponding implementation uses truncated arithmetic and heuristic GCD budgets, and excludes Fourier rotation synthesis and classical recovery.

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.

We propose a technique that allows a trusted party in some protocol to attach deposits to their own secrets, without impacting security, and convincing other parties using zero-knowledge proofs. The rationale is that, should this party compromise the protocol by blundering or revealing its secrets, they lose the attached deposit to attackers. As a result, stakeholders gain confidence on how this trusted party operates, and breaches become public as soon as deposits are claimed. We formalize this technique and related security notions, provide two practical constructions in generic discrete logarithm groups, and analyze its application to ECDLP-based protocols.

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.

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.