We study information-theoretic hiding when an adversary has unrestricted quantum processing but physical access to only one region from a declared family of subsystems. Perfectly hidden classical codewords lie in one fiber of the corresponding marginal map. We organize trace-distance diameter, orthogonal zero-error packing, and exact coherent subspace hiding on this fixed-marginal set, distinguishing equality of basis-state marginals from the cross-term conditions of quantum error correction.

LLM-based agents, which interleave large language model inference with external tool calls, are increasingly deployed in high-stakes settings. In real-world deployments, each model inference and provider-hosted tool execute behind the provider's API. Even when the agent loop runs on the user's device, these provider-executed steps still remain opaque to the user. This opacity creates an end-to-end integrity gap: a malicious provider may substitute the advertised model or fabricate tool observations to steer subsequent agent behavior. Existing zero-knowledge proof systems for LLMs prove only the Transformer computation of a single inference, leaving the rest of the inference pipeline, long-form autoregressive generation, and external tool interactions outside the proof. We present zkAgent, the first SNARK system for verifiable agent execution. zkAgent proves the complete inference pipeline, from token-to-embedding lookup and positional encoding to Transformer computation and decoding. It further binds each tool observation to an authenticated execution via zkTLS or zkVM subproofs, yielding a single end-to-end proof. To scale beyond per-token proving, we introduce one-shot transcript proving: by exploiting the Transformer's causal attention mask, zkAgent proves an entire multi-step agent transcript in a single forward pass, avoiding the substantial overhead incurred by one-proof-per-token generation. We make this batched proof sound with a weight-dependent quantization scheme that is both input-independent and unconditionally complete. On GPT-2 with a 512-token transcript, zkAgent achieves a $1047.4\times$ prover speedup over the state of the art (zkGPT, USENIX Security'25), amortizing to $0.30$s/token. On a real-world coding-assistant execution, zkAgent completes end-to-end proving in $93.18$s with $1.63$s verification, making verifiable agent execution practical.

Collision side-channel attacks are efficient attacks against cryptographic implementations, however, optimal collision side-channel attacks and how to compute them efficiently is an open question. In this paper, we show that collision side-channel attacks can be derived using the maximum likelihood principle when the distribution of the values of the leakage function is known. This allows us to exhibit the optimal collision side-channel attack and its efficient computation. Finally, we are able to compute an upper bound for the success rate of the optimal post-processing strategy, and we show that our method and the optimal strategy have success rates close to each other. Attackers can benefit from our method as we present an efficient collision side-channel attack. Evaluators can benefit from our method as we present a tight upper bound for the success rate of the optimal strategy.

Anonymous credentials (AC) equip users with credentials on attested attributes, which enable them to prove data-minimizing statements over their attributes. However, in standard ACs, each credential presentation reveals the credential issuer, which could be more information than intended and necessary, e.g., when merely proving age or personhood. Issuer-Hiding Anonymous Credentials (IHAC) address this limitation and hide the issuer in the presentation. That is, they only reveal that the user has a credential from an issuer within a certain trust set, referred to as the policy. Recent works by Sanders and Traore', and Katz and Sefranek show how to add issuer hiding to PS - and BBS - based credentials while keeping presentations constant-size, i.e., not scaling in the number of issuers. However, both constructions require the verifier to generate dedicated policy-key pairs, turning verification into a secret-key operation. Managing these verifier-specific keys introduces additional complexity and affects the resulting practical privacy and security guarantees. An orthogonal work by Flamini et al. avoids verifier - specific keys but at the cost of presentations that scale linearly - or logarithmically when using more involved proof systems - in the policy size, which becomes a bottleneck for scenarios with hundreds or thousands of issuers. In this work, we close this gap and propose IHBBS, the first IHAC scheme from standard BBS signatures that achieves constant-size presentations and is publicly verifiable, i.e., does not rely on any verifier-specific secret keys. At the core of our construction is a new technique to multiplicatively randomize BBS public keys and adapt the signatures accordingly, which we believe to be of independent interest.

In this paper we introduce a simple and unified approach, based on generic proof systems, to prove knowledge of any isogeny between two principally polarized abelian varieties in any dimension, assuming that the $2^m$-torsion is accessible for sufficiently large $m$. Previous generic proof approaches were only able to prove knowledge of a smooth degree isogeny between elliptic curves, where for each small prime factor $\ell$ of the degree, bespoke constraints had to be derived, typically from (a variant of) the $\ell$-th modular polynomial. Our approach is much simpler in that it relies on proving knowledge of a $2^n$-isogeny between two principally polarized abelian varieties in any dimension. Furthermore, our approach is unified in that the constraints are essentially the same for each dimension, resulting in a simpler and easier-to-optimize algorithm. Our construction has immediate applications to proving knowledge of an isogeny of any degree between two elliptic curves, by using a higher dimensional representation. Indeed, by a result of Robert, any isogeny can be embedded in a $2^n$-isogeny by increasing the dimension, and conversely, the knowledge of a $2^n$-isogeny between products of varieties implies the knowledge of an isogeny of degree $\leq 2^n$ between a factor of the domain and codomain. Our generic proof does not disclose the degree of the secret isogeny, nor does it rely on knowing the endomorphism ring, thereby solving an open problem posed by Beullens, De Feo, Galbraith, and Petit in 2023. Two use cases are immediate. First, if one wants to prove knowledge of any isogeny between two supersingular curves over $\mathbb{F}_{p^2}$, e.g. during the generation of an elliptic curve with unknown endomorphism ring. Second, to prove knowledge of a secret isogeny coming from the class group action on oriented supersingular elliptic curves, e.g. CSIDH with curves defined over $\mathbb{F}_p$. Computing such group actions is typically done using qt-Pegasis, which naturally results in a 4-dimensional representation of the isogeny. Lastly, we propose two tailored zero-knowledge proof systems that improve proving time and proof size without loss of generality and provide the first implementation in dimension 2 and 4 by implementing both proof systems in Rust.

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

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

Polynomial commitment schemes (PCS) are a fundamental building block of modern zkSNARKs. In this paper, we propose \emph{Lightning}, a new coding-based PCS that achieves state-of-the-art prover efficiency. Our main technical contribution is a systematic code family, the \emph{Lightning code}, which can be instantiated from any base code with constant relative distance. Compared with the base code, the Lightning code significantly reduces encoding cost by trading off relative distance. At a comparably small relative distance, Lightning's $\delta=0.005$ configuration has an equivalent encoding cost $2.8\times$ lower than Brakedown-fastest at $\delta=0.0043$; at the common relative distance $\delta=0.020$, its equivalent encoding cost is $1.53\times$ lower than that of the Brakedown code. We integrate the Lightning code into the standard coding-based PCS framework of Ligero and Brakedown. When committing to $2^{28}$ coefficients at matched proof sizes, Lightning reduces commitment time from about $349$s to $256$s ($1.36\times$ faster) for $80$MB proofs, compared with Brakedown.

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

Garbled circuits are fundamental in modern cryptography and secure two- or multi-party computation. For real-world programs that are naturally expressed in the Random-Access Machine (RAM) model, garbled RAM is the RAM counterpart of garbled circuits: they avoid the cost of compiling the entire program into a circuit, with communication complexity serving as the primary efficiency metric. We study the setting in which the RAM program is public, while the input data and memory contents remain secret except for the prescribed output. We construct a garbled RAM for programs running in time $T$ over memory consisting of $N$ words of $W$ bits each, the scheme achieves \[ O(T \cdot (W + \lambda) \cdot \log N) + \mathrm{poly} (\lambda) \] bits in communication, where $\lambda$ is the security parameter. For sufficiently large word size $W\ge \lambda$ and running time $T\ge\mathrm{poly}(\lambda)$, the communication becomes $O(T W \log N)$, asymptotically matching the bandwidth of an optimal oblivious RAM. Since any secure garbled RAM must hide memory accesses as in oblivious RAMs, our construction can be viewed as compiling an oblivious RAM into a non-interactive analogue, without incurring additional asymptotic communication cost. Technically, our garbled RAM builds on the recent succinct garbled circuits of Ishai, Li, and Lin (Crypto'25) and Li, Lin, and Lu (Eurocrypt'26), which are in turn based on homomorphic secret sharing. Accordingly, we inherit their circular-power variants of the Decisional Diffie-Hellman or Ring Learning-With-Errors assumptions. We also use techniques from the recent work on garbled arithmetic RAM, called Zebra, by Gu, Ghoshal, and Shi (Eurocrypt'26). Compared to Zebra, which achieves the same $O(TW\log N)$ communication for *arithmetic* RAM programs that only perform arithmetic over large and bounded integers, our work focuses on the standard *boolean* RAM model. Compared to the best garbled RAM in the random oracle model, due to Liu, Liu, Luo, and Heath (ACM CCS'26), we remove a multiplicative factor $\lambda$ in communication.

Repeat--accumulate--accumulate (RAA) codes have minimum distance linear in the block length with probability tending to one, both with and without random coordinate scaling. Sharp results, however, reveal a tradeoff between the two constructions. For block length \(N=rn\) and fixed repetition factor \(r\ge4\), the probability that the minimum distance is at most \(\delta N\) is \(\Theta(N^{2-r})\) for unscaled RAA and \(\Theta(N^{1-r})\) for scaled RAA, on their common proved range \(0<\delta\le1/10\). Thus scaling reduces the failure probability by a factor of order \(N\). This improvement comes at a cost: the scaled result requires \(q=\Omega(N)\) over \(\F_q\), and the encoder uses two length-\(N\) layers of coordinatewise field multiplications. In contrast, unscaled RAA works over a fixed field of characteristic greater than \(r\), and its accumulator stages use only field additions. In this work, we show that adding a third accumulator provides a substantially larger reliability gain without random scaling. For the unscaled repeat--accumulate--accumulate--accumulate ensemble \[ G_3=R\Pi_1A\Pi_2A\Pi_3A, \] where \(R\) is \(r\)-fold repetition, \(A\) is the accumulator, and the \(\Pi_i\) are independent uniform interleavers, we prove that \[ \Prb[d_{\min}(G_3)\le\delta N] =\Theta_{r,\delta}\!\left(N^{\,2-r-\ceil{r/2}}\right) \] for every fixed \(r\ge4\) and \(0<\delta\le1/10\), uniformly over all finite fields of characteristic greater than \(r\). Hence the field size need not grow with \(N\), and the encoder requires three accumulator passes but no coordinatewise field multiplications. On the common threshold range, its failure probability is smaller by a factor of order \(N^{\ceil{r/2}}\) than that of unscaled RAA and by a factor of order \(N^{\ceil{r/2}-1}\) than that of scaled RAA. For example, when \(r=4\), the respective failure probabilities have orders \(N^{-2}\), \(N^{-3}\), and \(N^{-4}\).

This paper introduces a new polynomial model for the exact variant of the Syndrome Decoding Problem (SDP) in the binary case. The model is based on elementary symmetric polynomials. We estimate the computational complexity of solving the corresponding polynomial system by establishing bounds on the degree of regularity and on the solving degree of the ideal associated to the model. The complexity estimate is lower than for previous polynomial models. We also provide a variant of the model whose complexity depends directly on the specific instance of the SDP and is lower than for the first model. Finally, we discuss how to apply our ap- proach to solve other variants of the SDP.

Lucas sequences are a helpful tool in mathematical and cryptographic calculations, providing in particular an efficient way to exponentiate in a quotient ring $R[x]/(x^2 - Px + Q)$. As with exponentiation in other finite rings and fields, we can use the periodic nature of these sequences to find roots of polynomials. Since they behave differently in the ring $\mathbb{Z}/N$ depending on whether $N$ is prime, Lucas sequences are also useful for primality testing. In this paper, we discuss improvements to Lucas-sequence algorithms for square roots and heuristic primality testing. Our first application is modular square roots. It is straightforward to take square roots modulo primes $p\equiv \{3,5,7\}$ mod 8. When $p\equiv 1$ mod 8, and especially when $p-1$ is divisible by many powers of 2, Müller's algorithm and Kim-Koo-Kwon are attractive options. Both of these use Lucas sequences. Here we show how to simplify and speed up Kim-Koo-Kwon. We also show a variant on Müller's algorithm which works even when $p\equiv 3$ mod 4, which would be useful if $p$ were secret. Our second application is heuristic primality testing. The Baillie-PSW primality test combines a strong Fermat test with a strong Lucas test. The recent Baillie-Fiori-Wagstaff variant strengthens Baillie-PSW. Here we show an improved variant, $\mathtt{SuperBFPSW}$, which is stronger than Baillie-Fiori-Wagstaff, but also faster than the original Baillie-PSW.

Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS) gave a $2^{n+o(n)}$ time algorithm for the Shortest Vector Problem (SVP) based on discrete Gaussian sampling (DGS), together with an honest sampler producing $2^{n/2}$ samples above the smoothing parameter in $2^{n/2+o(n)}$ time and space. Gao, Feng, and Hu (GFH) subsequently introduced DGS on random prime-index superlattices, making this sampler available at the shortest vector scale and obtaining a $2^{0.7314n+o(n)}$ time algorithm. In a different direction, the Becker--Ducas--Gama--Laarhoven (BDGL) sieve uses spherical product codes to find correlated pairs and runs in $2^{0.2925n+o(n)}$ time under the random list heuristic. We combine the random superlattice DGS framework with a single BDGL product code decoding layer. The algorithm splits the DGS output into two lists. For a fixed shortest vector $v$, the Gaussian midpoint identity turns the event $X-Y=v$ into a birthday event, while equal quotient labels certify that the reported difference belongs to the input lattice. The product code decoder locates the corresponding pair without enumerating all pairwise differences. Our analysis makes no random list assumption. For a fixed shortest vector $v$, once the retained lists contain a pair $x,y$ with $x-y=v$, the BDGL product code finds that pair with high probability. We extend the product code analysis so that this guarantee is compatible with the claimed time and space bounds. A centered quotient line gives a $2^{0.5822n+o(n)}$ time algorithm. We then replace the line through the zero residue with a random affine translate. This lets us target a rarer midpoint shell. As a result, we obtain a randomized classical algorithm for SVP that runs in $2^{0.5596n+o(n)}$ time and uses $2^{n/2+o(n)}$ space.

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

Verifiable secret sharing (VSS) is a core primitive in multiparty computation (MPC). Bhimrajka et al. [PKC'24, TIT'26] proposed the first computationally network-agnostic VSS and VSS-based MPC, which seamlessly accommodate both synchronous and asynchronous network models. However, their VSS requires Byzantine Agreement (BA) and incurs $O(n^5)$ bits of communication per sharing among $n$ parties, and their MPC requires honest participation from nearly all parties. We revisit the network-agnostic VSS architecture and propose a more efficient and general network-agnostic VSS structure. Our key technique is a new virtual-party strategy, which introduces more parties for reconstruction. With this technique, network-agnostic VSS is BA-free and performs as efficiently as synchronous VSS. Specifically, in terms of communication, our VSS costs $O(n^2)$ bits in the one-shot case and $O(n)$ bits in the round-by-round case with the dispute-control technique, yielding the first computationally network-agnostic VSS protocols with amortized linear communication complexity. Besides, we further address a series of subtle yet necessary hurdles in adapting existing results to network-agnostic models, including the erasure coding techniques in Reliable Broadcast (RBC), packed secret sharing techniques in VSS, and the correlated polynomial techniques in MPC.

Lattice signatures face a strict trade-off among compactness, implementation simplicity, and reliance on standard lattice assumptions: ML-DSA-44 requires a 2420-byte signature (3732 bytes combined) and HAETAE-120 takes 1474 bytes (2466 bytes combined), while Falcon-512 achieves 555 bytes but relies on complex floating-point arithmetic. We propose SHUTTLE, a compact Fiat–Shamir signature built on a standard MLWE public-key structure with unforgeability bound to MSIS in the random oracle model. At NIST Level I, SHUTTLE achieves a signature size of 1175 bytes (and 2167 bytes combined)—a 51% reduction in signature size over ML-DSA-44 and 20% smaller than HAETAE-120 using purely integer arithmetic. SHUTTLE resolves prior compact schemes’ limitations via three core techniques: (1) replacing secret-dependent rejection in the iterative sampling loop with a deterministic transition bounded by Rényi divergence, relegating restarts solely to public bounds and encoding checks (occurring with negligible probability $\approx 2^{-30}$); (2) reformulating transition logic in the logarithmic domain into simple integer interval comparisons; and (3) employing an asymmetric stretch-and-compress mechanism to offset MLWE parameter expansion. By eliminating secret-dependent rejection from the inner loop, SHUTTLE achieves constant-time execution with fast signing (1406k cycles, about $3\times$ faster than HAETAE-120) and verification faster than ML-DSA-44.

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

Proactive secret-sharing (PSS) offers security for shared secrets in a setting of a mobile adversary which, over time, may corrupt the whole shareholder set. This remarkable property is achieved by having parties proactively and in a coordinated manner refresh their shares on a regular basis, while it assumes that the adversary never manages to corrupt more than a threshold number of parties between two consecutive share refresh operations. A common assumption for achieving PSS is the ability of parties to securely erase their private state once they have performed the refresh operation. Motivated by the difficulty in the real world to ensure secure erasure, we investigate whether it is possible to achieve PSS without erasures. As in the classic model of computation it can be easily shown that PSS without erasures is impossible, we hence ask whether it is possible to achieve PSS via quantum computation, while still requiring only classical communication. We answer the question in the affirmative by utilizing one-shot signatures and post-quantum classical extractable witness encryption. In the process of developing our result, we define and construct threshold one-shot decryption and make connections to quantum money with classical communication both of which may be of independent interest. Finally, we show how, by combining post-quantum secure functional witness encryption with our PSS, it is possible for the secret to be used without explicitly being reconstructed, something that paves the way towards proactively secure threshold cryptography without erasures.

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

We investigate cryptanalytic attacks for predicting polynomial congruential generators (PCGs) from arbitrarily long sequences of consecutive truncated outputs. Such attacks naturally yield systems of modular polynomial equations, which can be solved using Coppersmith's method. However, deriving the corresponding success conditions by hand requires substantial combinatorial summation, which is typically both time-consuming and tedious. Existing automated Coppersmith methods assist with this computation, but they generally provide only numerical bounds for fixed systems, whereas in our setting the number of equations is itself a parameter. Inspired by the Newton-polytope framework of Feng et al.~(Crypto~2025), we express the success condition as the volume of a high-dimensional polytope and compute it symbolically as a function of the number of outputs. We improve existing asymptotic bounds for the Pollard generator and for linear congruential generators. We also obtain new attacks on quadratic congruential generators (QCGs) with partially known coefficients and on perturbed Power Generators with an unknown masking constant, matching bounds previously achieved only under stronger assumptions on the map $F(x)$.

Virtually all deployed private payment systems publish a nullifier for every transaction to prevent double spending. At a million transactions per second, the nullifier set grows by a petabyte each year. In this work, we tackle the question of sustaining massive throughput in private payments while ensuring the system can be run on commodity hardware. We construct Bonsai, an account-based private payment scheme where validators store a single commitment per account and never store any nullifiers. Instead, each user privately maintains the nullifiers of the payments it has received, and can prune older nullifiers to cold storage so that its active state remains small. An external observer only learns that an account performed some action (send/receive) but never learns the amount or counterparty of a payment. To verify proofs at this rate, we add zero-knowledge to Pari [USENIX '26] with no increase in proof size and negligible prover overhead, and use it with a batch verification strategy. Our prototype verifies over a million operations per second on an M5 MacBook Pro.

The standardization of ML-DSA has shifted the cryptographic community's focus toward its practical security. While profiled attacks against its implementations are well studied with a few traces, non-profiling attacks are widely assumed to require large trace complexity. We challenge this by introducing horizontal fusion attacks, demonstrating that non-profiling, few-trace key recovery is highly practical against ML-DSA, even against masked implementations. We expose a structural vulnerability in the module lattice from a side-channel perspective. In particular, in ML-DSA's matrix-vector multiplication ($\hat{\mathbf{A}} \circ \hat{\mathbf{y}}$), the row-wise reuse of the ephemeral secret vector $\hat{\mathbf{y}}$ indicates that one single signature generation exposes $k$ (the row-wise size of $\hat{\mathbf{A}}$) leakage instances of the same secret-dependent intermediate value, each with a distinct and known coefficient of $\hat{\mathbf{A}}$. However, exploiting this in practice is highly non-trivial due to noise and/or compiler optimizations. To overcome this, we propose a variance-based weighted fusion strategy. This approach weights each operation by how far its leading candidate is separated from the runner-up candidates, and the signing relation ($\mathbf{y} = \mathbf{z} - c \cdot \mathbf{s}_1$) lets us extract the signed coefficients of the secret key. Moreover, we introduce a fast, INTT-based algebraic sieve that further increases the success rate of key recovery. Putting together, we achieve full key recovery using merely 4 traces against ML-DSA-87 (the highest security parameter set) with non-profiling correlation analysis. On the state-of-the-art first-order masked ML-DSA implementation, our attack extracts the secret key using no more than 90 traces. To the best of our knowledge, these non-profiling results establish a new record in trace complexity for both unprotected and first-order masked ML-DSA implementations, even comparable to these profiling-based attacks.

We design decentralized multi-authority functional encryption (MAFE) for $\mathsf{P/Poly}$ circuits from minimal assumptions in both the bounded-collusion and fully collusion-resistant models, i.e., from public-key encryption and from functional encryption, respectively. Prior constructions required sub-exponentially hard public-key encryption with random oracles (bounded collusion) or sub-exponentially-hard obfuscation (collusion-resistant). Under the additional assumption of SXDH or LWE, our constructions remain secure against an adversary that corrupts any $k$ of the $n$ local authorities, provided $\binom{n}{k} = \mathsf{poly}(\lambda)$, covering, for example, $k = O(1)$ and $n = \mathsf{poly}(\lambda)$ or $k = O(\log \lambda)$ and $n = O(\log \lambda)$. Complementing this, we show that any MAFE scheme that tolerates corruption of more than $\chi = O(\log \lambda)$ authorities and remains non-trivially compact (i.e., parameter sizes scale sub-linearly in $2^{\chi}$) implies indistinguishability obfuscation. Thus, our scheme is essentially optimal across a wide parameter regime. Along the way, we introduce two abstractions, MAFE with $\textit{synchronous setup}$ and $\textit{synchronous key generation} $ that provide a path to constructing multi-authority encryption schemes from their centralized counterparts, and may be useful for designing other multi-authority encryption systems.

An attribute-based encryption (ABE) scheme is "large-universe" if its attribute universe is superpolynomial and is not enumerated during setup. In the multi-authority setting, we further require that each authority can independently manage a superpolynomial set of attributes and dynamically issue an arbitrary polynomial number of secret keys per user. Although large-universe (multi-authority) ABE from pairings is well studied, explicit lattice-based constructions have remained elusive. In the centralized setting, a standard workaround is to instantiate lattice-based ABE for general circuits and encode each attribute as a bit string; however, unless one adopts non-standard lattice assumptions, this approach typically yields prohibitively large ciphertexts. In the multi-authority setting, even though lattice-based ABE for general circuits is known, this bit-encoding approach applied to those schemes does not yield a genuine large-universe construction. We close this gap by presenting the first lattice-based large-universe (multi-authority) ABE schemes under the Learning With Errors (LWE) assumption, achieving ciphertext and key sizes that are comparable to those in the pairing-based setting. Concretely, we construct: • a large-universe key-policy ABE scheme with ciphertext size $O(t)$; • a large-universe ciphertext-policy ABE scheme with ciphertext size $O(|f|)$; and • a large-universe multi-authority ABE scheme, where $t$ is the number of attributes, $|f|$ is the policy size, and the $O(\cdot)$ notation suppresses $\tilde{O}(\lambda)$ factors. All schemes support policies in disjunctive normal form (DNF) and are proved secure in the random oracle model. We further develop more efficient variants of our key-policy and ciphertext-policy ABE schemes over ideal lattices under the Ring-LWE assumption, aiming for practical performance on the order of seconds to minutes. Experimental results from our implementations confirm practical runtimes and memory consumption, providing concrete evidence that large-universe lattice-based ABE is feasible for efficient real-world deployment.

Recently, Stateful Private Information Retrieval (PIR) has emerged as a promising new paradigm of PIR. Despite significant recent progress, state-of-the-art single-server schemes in this paradigm still suffer from practical inefficiencies in communication, computation, and/or client storage. In this work, we construct a new single-server stateful PIR scheme called HarmonyPIR that achieves efficient communication, computation, and client storage. From a technical standpoint, we build on the recent work of Wang and Ren (EUROCRYPT 25) and propose a new hint organization that uses only a single random permutation. The random permutation can be instantiated using either AES or the recently standardized FF1 Format-Preserving Encryption, yielding two variants of HarmonyPIR. Our new scheme achieves up to two orders of magnitude better amortized computation and up to five times better amortized communication than state-of-the-art schemes.

Are private set intersection (PSI) protocols ready for the post-quantum future? We focus on the PSI protocol of Rosulek \& Trieu (``RT21'', ACM CCS 2021), which is the current state-of-the-art for PSI on small sets (less than a thousand items). The RT21 protocol presents some fundamental barriers to post-quantum security. First, although it is written in terms of an arbitrary KEM, it requires certain properties of Diffie-Hellman KEM that simply are not satisfied by any post-quantum candidates. Second, even if adapted to post-quantum KEMs, it would require an ideal permutation with blocklength larger than any known viable candidate. We show how to modify the RT21 to make it compatible with post-quantum KEM candidates like ML-KEM. We also describe a direct domain-extension construction for ideal permutations, showing how to construct a huge-block ideal permutation directly from one with smaller blocklength, such as the Keccak permutation family. Along the way, we also introduce new abstractions for \emph{oblivious key-value stores} (Garimella et al., Crypto 2021) that make the analysis of these kinds of PSI protocols more modular. We implemented our protocol and evaluated its performance across different network settings and instantiations. We achieve PSI from standardized post-quantum primitives with latency as low as $0.25$ ms/item and communication as low as $1.67$ KiB/item. We find that the performance penalty for post-quantum security ranges from 1.25$\times$ to 5.92$\times$ in latency and is 16.7$\times$ in communication, depending on the instantiation.

Gradient boosted decision trees (GBDTs) are widely used for tabular data in finance, healthcare, and risk ssessment. As GBDT training and inference are increasingly outsourced, clients need to verify that models are trained as claimed and predictions are consistent with those models, while providers may need to keep training data and model parameters private. This makes zero-knowledge proofs for GBDT training and inference a natural solution. Existing approaches typically compile training certification into circuits and prove their execution using generic ZKP backends, incurring high prover costs. Directly proving the underlying algebraic relations offers an alternative, but proving each relation separately incurs substantial costs for committing to and opening auxiliary witnesses. Batching is challenging because these witnesses have different shapes and sizes and are encoded over different domains. We present \textsc{Terrae}, a zero-knowledge proof system for quantized GBDT training and inference based on KZG polynomial commitments. \textsc{Terrae} avoids both proving circuit computation and proving each constraint separately by leveraging the structure of GBDT training and two new batching techniques: domain-lifting batching for low-degree algebraic constraints and interleaving batching for same-form non-native constraints. Both techniques work over differently-sized domains and reduce many constraints to a single claim without introducing extra polynomial commitments. We also design a histogram proof that proves the correctness of aggregating sample-wise updates into histograms, which may be of independent interest. Our evaluation shows that, compared with prior work CertXGB instantiated with the same KZG backend, \textsc{Terrae} achieves proof-generation speedups of $3.18$--$13.55\times$ for training and $1.96$--$4.31\times$ for inference across completed benchmark comparisons, with lower peak prover memory, at the cost of moderately larger proofs and higher verification time.

We initiate the study of memory efficiency in proving the security of authenticated key exchange (AKE) protocols: We first revise the security model for AKE protocols in order to prove their security in a memory-efficient manner without compromising its capability of capturing usual attacks. We formally show that security in our model implies {security in} previous ones, and thus our model captures the same security as before. After that we propose a generic construction of AKE from key encapsulation mechanisms (KEMs) and digital signature schemes, motivated by the signed Diffie-Hellman protocol. Under the multi-user security of the signature scheme and (relatively weak) one-way security against plaintext checking attacks of the KEM, our generic construction is proven to be tightly secure (in terms of success probability) via memory-tight reductions in the random oracle model. This gives us the first memory-tight AKE protocol, and it largely reduces the memory consumption of proving AKE protocols. Given that most post-quantum assumptions (e.g., the Learning-With-Errors and Short-Integer-Solution assumptions) are memory-sensitive, our improvement on memory consumption holds significant value for post-quantum AKE protocols.

When looking at authenticated encryption schemes, we have schemes that process the input data by having serial calls to their underlying building blocks, like duplex-based constructions, and schemes that allow for parallel calls to their underlying building blocks, like the Galois Counter Mode (GCM). Naturally, one can parallelize a serial scheme by distributing the data to encrypt over different calls to the serial scheme. However, there are many different choices to be made, like how to choose the nonce for the different instances, or if and how to combine the multiple tags into a single one. In this paper, we investigate different possible choices providing proofs for their security. Interestingly, we see a huge variance in the provable properties and hence, the security in making a serial scheme parallel. Or, motivating the problem more generally, we are investigating tag combiners, where the single tags to be combined are secret to the adversary.

The Signal protocol is used by billions of users daily and recognized as the gold standard for end-to-end encrypted messaging. Its initial handshake protocol X3DH uses XEdDSA to sign its semi-static key and allows parties to derive a session key asynchronously. The protocol is implemented over Curve25519, relying on the assumed 128-bit hardness for solving Discrete Logarithms (DL). Previous non-tight reductions incur a large loss in the number of sessions, and the resulting concrete security guarantees fall far below the intended 128-bit security level. This motivates the development of tight security bounds for these protocols. In this paper, we improve the security analysis of X3DH and its recent enhancement XHMQV (Fiedler et al., CRYPTO'25) by providing tight security reductions under multi-user Diffie–Hellman (DH) assumptions (Kiltz et al., CT-RSA'23) in the Random Oracle Model. Unlike prior work, our proofs are in the more realistic multi-Test setting. The variant of X3DH that we analyze hashes additional context into the session key. Although this modification is minor, it yields tight security bounds and provides a stronger justification for the use of Curve25519. In light of our results, the Signal developers plan to adopt the same modification.

The GHOST protocol was proposed in 2015 as an alternative to the Nakamoto consensus mechanism that underlies Bitcoin. In con- trast to the Nakamoto longest-chain rule, the GHOST rule justifies selec- tion of a chain by maximizing subtree weights rather than path lengths. This chain selection rule has been adopted by a variety of consensus protocols and is featured in the currently deployed protocol supporting Ethereum. We establish an exact characterization of the consistency region of the GHOSTprotocol,identifyingtherelationshipbetweennetworkdelay,the rate of honest block production, and the rate of adversarial block pro- duction that guarantees that the protocol reaches consensus. In contrast to the Nakamoto consensus protocol, we find that the region depends on the convention used by the protocol for tiebreaking: we establish tight results for both adversarial tiebreaking, in which ties are broken adver- sarially in order to frustrate consensus, and deterministic tiebreaking, in which ties between pairs of blocks are broken consistently throughout an execution. We provide explicit attacks for both conventions which stall consensus outside of the consistency region. Our results conclude that the consistency region of GHOST can be strictly improved by incorporating a tiebreaking mechanism; in either case, however, the final region of consistency is inferior to the region of longest-chain rule consensus. On the other hand, in the region where the GHOST protocol is secure it provides superior defense of settled blocks against periods of adversarial majority than the longest-chain rule and, in this sense, is preferable from the perspective of self-healing.

Differential meet-in-the-middle attacks, introduced by Boura et al. in 2023, propose a new way of dealing with differential distinguishers. It allows, in particular, to combine differential attacks with initial structures, that were usually used exclusively for meet-in-the-middle attacks. Several applications of this new technique have been published, but so far the results on Feistel constructions have not improved much upon previous best known attacks. In this paper, we apply them on Feistel constructions with all the improvements proposed so far, and we propose some additional new ideas to generically improve these kinds of attacks. We also propose an automatized tool for optimizing the attacks on Simon-like constructions. Our tool outputs a graphical representation of the attack that makes it very easy to verify. All this has allowed us to provide improved single-key key-recovery attacks on most of the variants of Simon, Simeck and CLEFIA-256, that increase the highest number of rounds attacked by 1 or 2 in nearly all the cases.

We introduce new two-party threshold signature schemes with strong efficiency and security. The application of our methodology to the two most popular signatures, Schnorr and ECDSA, yields two-round, two-party, stateless and deterministic signing with 4-12 ms of computation on one core of a standard laptop, extremely low communication -- 96 B for Schnorr, and 128 B for ECDSA -- and full concurrent simulatable security. At the heart of our approach is a new pseudorandom correlation function (PCF) for vector-OLE that admits an efficient key generation protocol; we design an end-to-end maliciously-secure and highly parallelizable DKG for this PCF and, using this DKG, we obtain an estimated runtime of 44 s for the (one-time) distributed setup of Schnorr and ECDSA on one core of a standard laptop.

We present a lattice-based construction of secret-key functional encryption (FE) for low-norm polynomials of any constant degree $d$, hence also for $\mathsf{NC}^{0}$ circuits. We rely on two core ingredients: 1. New trapdoor and preimage sampling algorithms for certain degree-$d$ tensor-structured matrices, used to generate functional secret keys. 2. A new $k$-LWE-style assumption where short preimages of non-zero images with respect to the above tensor-structured matrix are given as hints, under which we prove that our secret-key FE scheme is selectively secure (under unbounded collusion). To gain confidence in the new assumption, we prove that the standard LWE assumption implies the degree-$1$ case and cryptanalyse the $d > 1$ case. As a corollary, we obtain a new pathway to post-quantum secure indistinguishability obfuscation (iO), conditioned on the above new assumption, standard LWE, and the existence of polynomial-stretch pseudorandom generators in $\mathsf{NC}^{0}$. Along the way, we give a new, simple (public-key) FE scheme for linear functions with selective security under the standard LWE assumption.

Password Authenticated Key Exchange (PAKE) establishes secure communication channels using passwords for authentication. Currently, standardized PAKEs rely on classical asymmetric cryptography. However, these PAKEs may become insecure should the expected quantum threat become a reality. Despite the growing interest in realizing quantum-safe PAKEs, they did not receive much attention from the ongoing Post-Quantum Cryptography (PQC) integration efforts. Hence, there is a significant awareness gap compared to PQC primitives subject to the official standardization processes. We provide a comprehensive overview of existing PQC PAKEs, classify their design rationales and authentication methods, and address aspects related to their security and performance. We identify PAKE designs that are still unexplored in the PQC realm and discuss the possibility of their adaptation. Thus, we offer a detailed reference for future work on PQC PAKEs.

We study the feasibility of constant communication-overhead statistically-secure MPC tolerating malicious adversaries in the synchronous setting and guaranteed output delivery (GOD). We propose a protocol with $n = 3t + 1$ for SIMD circuits with a communication overhead of ${\cal O}(1)$ and round complexity ${\cal O}(D)$ for circuit depth $D$, where $n$ is the number of parties and $t$ is the maximum number of corruptions. Moreover, our protocol achieves GOD. This is the first MPC protocol with above characteristics. To design our protocol, we give two major contributions. Our first technical contribution is a verifiable secret sharing (VSS) protocol that achieves constant per-secret overhead via two-dimensional packing. Our second contribution is a constant-overhead degree-reduction protocol that converts a high-degree packed sharing into a lower-degree packed sharing.

Permutation and lookup arguments are at the core of most deployed SNARK protocols today. Most modern techniques for performing them require a grand product check. This requires either committing to large field elements (e.g. in Plonk) or using GKR (e.g. in Spartan) which has worse verifier cost and proof size. Moreover, both have a soundness error that grows linearly with the input size. We reduce permutation argument to sumcheck argument and present two permutation arguments that have $\mathsf{polylog}(n)/|\mathbb{F}|$ soundness error. BiPerm only requires the prover to perform $O(n)$ field operations on top of committing to the witness, but at the cost of limiting the choices of PCS. We show a general construction, MulPerm, which has no restriction on the PCS choice and its prover performs essentially linear field operations, $n\cdot \tilde O(\sqrt{\log(n)})$. Both permutation arguments generalize to lookups. We demonstrate how our arguments can be used to improve SNARK systems such as HyperPlonk (Eurocrypt 2023) and Spartan (Crypto 2020), and build a GKR-based protocol for proving non-uniform circuits. Further, MulPerm enables the fastest succinct argument with sublinear verification for arbitrary circuits over small fields. Plugging MulPerm into prior small field constructions overcomes the previous lack of an efficient permutation argument with sufficiently small soundness error.

An anonymous messaging service has to solve a basic routing problem: a server must deliver an encrypted message to its recipient without learning who the recipient is. Broadcasting all ciphertexts hides the destination but forces every recipient to constantly scan for new messages. Oblivious Message Retrieval (OMR; CRYPTO~'22) tackles this by using fully homomorphic encryption (FHE) to let an untrusted server perform message retrieval on a recipient's behalf without learning which messages are pertinent. We introduce Oblivious Signaling, which shifts this cost from retrieval to sending. The server maintains a fixed-size encrypted inbox for each recipient. When a sender submits a message, the server applies the same homomorphic update to every inbox: the intended inbox absorbs the message, and the rest remain unchanged at the plaintext level. The update is uniform, can be parallelized across inboxes, and ties the delivery cost strictly to the size of the anonymity set rather than global traffic. Recipients retrieve by fetching and decrypting their inbox, so checking for new messages is independent of the global traffic. We formalize receiver privacy against an untrusted server, even when it colludes with other users, give a concrete construction based on fully homomorphic encryption, and analyze the resulting "digital postage'' trade-off: delivery is expensive, but checking is cheap. Our prototype identifies practical regimes in which this cost-model shift is preferable to scan-based retrieval, even with highly optimized OMR implementations. This cost model is well-suited to settings where recipients check frequently, and messages arrive sporadically, and it naturally discourages high-volume spam.

MDS matrices are a key structure for providing optimal diffusion in symmetric primitives. However, the theoretical analysis of their cost remains limited. This issue is particularly relevant to arithmetization-oriented permutations, where designs often either use costly MDS matrices or sacrifice the MDS property to reduce the number of constraints. This paper studies the number of fan-in-two additions needed to implement MDS matrices. We represent fan-in-two addition constraints by a directed acyclic graph and derive lower bounds on the number of additions using the established result that any such computation graph implementing an MDS matrix must be a superconcentrator. Building on size-reduction lemmas for superconcentrators, we present a recursive algorithm that improves both lower and upper bounds for $t\times t$ matrices with $t\leq 8$. As a result, we obtain explicit MDS matrices over large primes for $t=3,4,5,6,7,8$, requiring $5,8,12,16,21,26$ additions, respectively. These bounds are tight for $t\leq 6$. We also use the same superconcentrator graphs as templates for MDS matrices with $k$-bit words. For $t=5,6,7$, our matrices require fewer XORs than the state of the art for most considered parameter choices in this line of work.

Strong designated verifier signatures are a variant of digital signatures in which only one party—the designated verifier—is able to verify the authenticity of a signature. We propose a new strong designated verifier signature scheme based on (abelian) cryptographic group actions.

It has been known for two decades that performing compression before encryption is dangerous, because it introduces a side channel leaking information about plaintexts through ciphertext lengths: the compressed plaintext length may be visible in the ciphertext length, and the amount of compression obtained is plaintext-dependent; hence an adversary can obtain some leakage about the plaintext via observation of ciphertext lengths. This issue was first pointed out by Kelsey (FSE 2002) and turned into a practical plaintext recovery attack in the form of the CRIME attack on SSL and TLS by Rizzo and Duong in 2012. A long series of variations and attacks against other systems followed. Despite the known dangers, the compress-then-encrypt paradigm is still prevalent in practice today. This may be because the compression-based side channel is susceptible to noise and may require a large number of queries to enable plaintext recovery, and so can be mitigated by either adding noise (e.g. with random padding) or limiting an adversary's interaction with the system. We demonstrate that this side channel is much more powerful than previously thought. We focus on the widely-used DEFLATE algorithm in our analysis. We present novel techniques that enable strong amplification of small length differences arising during compression. Our telescoping and chaining amplification techniques exploit the way in which DEFLATE replaces common strings by shorter back-references. Our collision-based amplification technique focusses on exploiting hash table collisions in DEFLATE implementations. This involves a deeper examination (and exploitation) of the internals of DEFLATE than in previous works. These insights result in compressed length differences growing linearly with the length of queries. Compared with length differences of a few bits or bytes in prior work, our new amplification techniques thus enable us to defeat existing noise-based countermeasures. Finally, we introduce the concept of CRIME automata, these being carefully crafted query strings that enable an attacker to exert fine control over the internal behaviour of DEFLATE and produce differences in the output lengths of the compressor according to various criteria (such as whether the DEFLATE sliding window contains a given target string). In turn, our automata are composed in a modular fashion from gadgets having different functions, including matching against target strings, performing logical operations between other gadgets, and, most importantly, amplifying differences in output lengths using the above-mentioned techniques. We provide multiple, concrete automata designs that serve different attack goals. These designs are supported by experiments and a publicly available codebase demonstrating the power, flexibility, and practical impact of our CRIME automata approach.

Jafari and Khazaei (Journal of Cryptology, 2021) introduced a kernel-based lower-bound method for linear secret-sharing schemes by fixing one minimal qualified coalition and comparing its participant components with those arising from auxiliary minimal qualified coalitions. These comparisons form a star. We extend the same mechanism from stars to coalition-labelled trees and obtain new characteristic-two inequalities for the relaxed-line non-Fano port $\widehat N$. For this access structure, the tree method is strictly stronger than the star method, yielding facet inequalities not implied by the star inequalities. We also show that the tree method does not determine the full contribution region. To complete the analysis of $\widehat N$, we introduce component-dual compression (CDC). CDC replaces each share by the span of the components selected from minimal reconstructions and realizes the duals of these compressed spaces in a common coordinate system indexed by the original minimal coalitions. This yields the remaining lower-bound inequalities. Together with matching constructions, the star, tree, and CDC bounds determine the complete characteristic-two linear contribution region of $\widehat N$, with maximum and average linear information ratios $5/4$.

Single-server private information retrieval (PIR) schemes are known to require linear query time. Recent works circumvent these classical lower bounds by leveraging preprocessing to answer queries in sublinear time. We prove computation lower bounds for PIR with preprocessing schemes making blackbox usage of any cryptography (such as random oracles or virtual blackbox obfuscation). If the client stores $s$ bits about an $n$-bit database, then answering $k = \Omega(s)$ queries requires either $\Omega(n/s)$ amortized online communication or $\Omega(n/s)$ amortized server cryptographic operations. This is tight, as known constructions match either bound while outperforming the other. Our lower bound is unconditional and allows arbitrary query protocols, weakened privacy, and server-side database encodings (including doubly efficient PIR) whenever the encoding is independent of the blackbox cryptography. Previous bounds were only known conditionally and for restricted classes of preprocessing, e.g., under non-encoding assumptions. Our framework also yields $\Omega(n/s)$ communication lower bounds for schemes with $o(n/s)$ server cryptographic operations, communication-determined server cryptography, or perfect privacy in the idealized model. Finally, we prove lower bounds for symmetric PIR with client preprocessing in the random oracle model and give a matching construction using only one-way functions in the online phase.

In this paper, we revisit the design of multi-party distributed point functions (DPFs) and make several new contributions that advance the state of the art. We begin by revisiting security amplification, a fundamental tool underlying many DPF constructions. In particular, the recent landmark work of Goel, Wang, and Wang (CRYPTO'25) critically relies on security amplification and, for a general polynomial number of parties, gives the only known construction based on one-way functions (OWFs) that achieves sublinear dependence on the input domain size. Unfortunately, due to a known gap in the proof of the security amplification theorem of Boyle et al. (CRYPTO'22), we currently still lack a fully established security amplification theorem for DPFs. We fill this gap by providing a new proof of security amplification for DPFs with tight parameters. Equipped with this security amplification theorem as a key technical tool, we develop several new techniques that asymptotically improve the communication cost of multi-party DPFs in both the honest-majority and corrupt-majority settings. Our main results are summarized below, where $N$ denotes the input domain size, $m$ denotes the number of parties, and $t$ denotes the corruption threshold: In the all-but-one-corrupt setting, we describe a new scheme based on OWFs with $\widetilde{O}_\lambda\left(N^{\frac12 + \epsilon} \cdot \sqrt{m}\right)$ share size where $\epsilon > 0$ is an arbitrarily small constant. In comparison, the best previously known OWF-based construction due to Goel et al. incurs $\widetilde{O}_\lambda\left(N^{\frac12 + \epsilon}\cdot m^3\right)$ share size. In the honest-majority setting, assuming $m > (1+\epsilon)D t$ for some integer $D \ge 2$ and arbitrarily small constant $\epsilon > 0$, we construct a new OWF-based scheme with share size $\widetilde{O}_\lambda(N^{\frac{1+\epsilon}{2D}})$, as well as an information-theoretically secure scheme with share size $\widetilde{O}(N^{1/D})$. Both constructions achieve an exponential factor improvement in their dependence on $m$ and $t$ compared to the state-of-the-art schemes of Bunn, Kushilevitz, and Ostrovsky.

Privacy-preserving distributed ledgers enable transaction processing systems in which users can submit transactions without revealing their identities or transaction details. Regulated and institutional settings impose additional requirements: authorized parties must be able to efficiently trace transactions to their originators without compromising overall system privacy. Existing approaches suffer from important limitations, including restricted parallel transaction formation, high computational overhead, and overly broad auditor access to user secrets. We present a framework for efficient tracing that eliminates concurrency issues while limiting auditor access. We formalize our security requirements via an ideal functionality and propose a black-box construction based on pseudorandom functions and anonymous credentials, with two concrete instantiations: one using hash-based PRFs and zk-SNARKs, and another using algebraic PRFs and Sigma protocols. Our experimental evaluation demonstrates practicality, incurring only a few milliseconds of overhead for the added tracing capabilities.

In this paper, we present a general framework for constructing SNARK-friendly post-quantum signature schemes based on minimal assumptions, specifically the security of an arithmetization-oriented family of permutations. The term "SNARK-friendly" here refers to the efficiency of the signature verification process in terms of SNARK constraints, such as R1CS constraints. Within the CAPSS framework, signature schemes are designed as proofs of knowledge of a secret preimage of a one-way function, where the one-way function is derived from the chosen permutation family. To obtain compact signatures with SNARK-friendly verification, we rely on SmallWood, a recently proposed hash-based zero-knowledge argument scheme well suited for statements arising in this context. From this proof system which we tweak towards SNARK-friendliness, the CAPSS framework offers a generic transformation of any arithmetization-oriented permutation family into a SNARK-friendly post-quantum signature scheme. We provide concrete instances built on permutations such as Rescue-Prime, Poseidon, Griffin, and Anemoi. For the Anemoi family, achieving 128-bit security, our approach produces signatures of sizes ranging from 9.5 to 15.5 KB, with R1CS constraints between 24K and 35K. This represents a 4-6x reduction in signature size and a 5-8x reduction in R1CS constraints compared to Loquat (CRYPTO 2024), a SNARK-friendly post-quantum signature scheme based on the Legendre PRF. We showcase CAPSS through aggregated signatures, achieving sub-kilobyte amortized size for large batches, and anonymous credentials, enabling presentation proofs under 150 KB, thus highlighting the practicality of SNARK-friendly, symmetric-based designs for post-quantum primitives.

Functional adaptor signatures (FAS) are a novel cryptographic primitive introduced at CCS'24 that enable privacy-preserving, fine-grained data-payment exchanges between a seller and a buyer in a trustless and atomic manner. In this setup, the seller holds sensitive data \(x\) (e.g., patient records, climate data), and the buyer specifies a function \(f\) (e.g., aggregate, sum). FAS guarantees that the buyer learns \(f(x)\) (and nothing beyond) if and only if the seller receives payment in blockchain-based tokens. Unlike generic smart contracts, FAS-powered solutions excel in privacy, efficiency, and compatibility with diverse blockchain systems. However, prior FAS constructions were limited to linear functions (where $f$ was linear in $x$), restricting their applicability to more complex and prevalent applications including data analytics and ML model evaluations. In this work, we extend the capabilities of FAS to support higher-degree functions \((\textit{deg} \geq 2)\), significantly broadening its range of applications. Our core contribution is a novel FAS design leveraging homomorphic encryption, which simultaneously achieves enhanced efficiency and compatibility for general functions. This approach diverges fundamentally from the restricted design in CCS'24 which relied on connections to functional encryption. We implement our homomorphic encryption-based FAS for functions arising in applications such as data analytics and machine learning inference. Remarkably, even for linear functions, our new design achieves an order-of-magnitude improvement in performance compared to CCS'24 constructions. Furthermore, our solutions seamlessly integrate with prominent blockchain systems, requiring only a basic signature verification script on standard transactions, thus ensuring practical deployability. As a conceptual contribution, we introduce the general paradigm of a blockchain-based functional fair exchange (FFE) protocol, rigorously define buyer and seller fairness, and show that FAS implies the general goal of FFE.

Zero-knowledge proofs (ZKPs) are a fundamental building block in cryptography, enabling powerful privacy-preserving and verifiable computations. In the post-quantum era, hash-based ZKPs have emerged as a promising direction due to their conjectured resistance to quantum attacks, along with their simplicity and efficiency. In this work, we introduce SmallWood, a hash-based polynomial commitment scheme (PCS) and zero-knowledge argument system optimized for relatively small instances. Building on the recent degree-enforcing commitment scheme (DECS) from the Threshold-Computation-in-the-Head (TCitH) framework, we refine its formalization and combine it with techniques from Brakedown. This results in a new hash-based PCS that is particularly efficient for polynomials of relatively small degree -typically up to $2^{16}$- outperforming existing approaches in this range. Leveraging this new PCS, we design a hash-based zero-knowledge argument system that outperforms the state-of-the-art in terms of proof sizes for witness sizes ranging from $2^6$ to $2^{16}$. Additionally, we present exact zero-knowledge arguments for lattice-based problems using SmallWood, demonstrating highly competitive performance: our scheme yields proof sizes under 25 KB across a wide range of lattice parameters, including Kyber and Dilithium instances.

Deep neural networks (DNNs) are increasingly used in sensitive applications, where certifying properties such as adversarial robustness and fairness is crucial. Several recent works propose DNN certification systems using zero-knowledge proofs (ZKPs)— cryptographic primitives that allow verifying certificates while maintaining confidentiality of the model. While certification algorithms typically treat the DNN as a function over reals, naively translating these algorithms into finite-precision implementations can result in unsound certification due to rounding errors. In ZKPs, this unsoundness is amplified due to a larger precision loss from fixed-point arithmetic emulated using finite fields. In this work, we highlight an overlooked gap in the soundness of prior protocols. We propose AZKABAN, a system for zero-knowledge abstract interpretation-based analysis with end-to-end soundness. We introduce operators for sound interval analysis over finite-fields, including efficient ZKP-amenable algorithms for inner-products and division, while preventing privacy leaks due to non-linear activations. We implement our system which is comprehensive in terms of supporting both feed-forward and convolutional neural networks. AZKABAN improves over the state-of-the-art ZK individual fairness certification protocol by up to two orders of magnitude in end-to-end proof time. Further, it scales to much larger models than those considered in the state-of-the-art. AZKABAN also provides, to our knowledge, the first solution for ZK robustness certification.

Generative AI has made high-fidelity deepfakes easy to produce, and online social networks (OSNs) spread them widely across users and platforms. Publicly verifying an image's provenance, i.e., where an image came from and what edits it has undergone, can help combat deepfakes. The Coalition for Content Provenance and Authenticity (C2PA) offers an industry standard, but depends on trusted software and hardware. Through digital signatures and zero-knowledge proofs, cryptographic image authentication eliminates the reliance on trusted editors. However, deploying such schemes in OSNs faces three problems: preserving signer privacy, maintaining provenance authenticity across edits, and ensuring efficient verification. To ensure signer anonymity in image provenance, we propose an unlinkable pseudonym certificate scheme (UPCS) based on anonymous credentials, which reduces online signing and verification to ordinary digital signature operations taking only 0.017 and 0.066 ms. Building on UPCS, zk-SNARKs, and hash chains, we propose an anonymous image provenance authentication (AIPA) scheme, ensuring the authenticity of provenance and editing history of an image as it propagates across mutually untrusted editors, while preserving signer privacy. To achieve efficient verification in OSNs, we introduce VIMz-Loua, a GPU-accelerated image proof system with a dedicated JPEG-compression circuit, whose proofs remain a constant 448 B and verify in 6-12 ms across image sizes. We formally prove the security of UPCS and AIPA, and implement an end-to-end workflow in a simulated OSN environment, where the full multi-edit provenance lineage is only 40.2 KB (6.5% of the published image), and is verified in 4.28 s.

Strong designated-verifier signatures provide authentication while restricting verification to a chosen verifier and protecting the signer from transferable evidence. Designing such signatures in the post-quantum setting is challenging because authentication, signer privacy, simulation, and efficiency must be achieved simultaneously. Recently, Renan proposed CSI-SDVS, a compact post-quantum strong designated-verifier signature scheme built from CSIDH-style commutative isogeny class-group actions. We show that its response design, $z_i=b_i-s_i$, breaks privacy of the signer's identity: because the PSI experiment reveals both candidate signer secret keys, an adversary can reconstruct the signing randomness and identify the actual signer with overwhelming probability. We validate the attack over 30,000 executions, obtaining 100\% signer identification in the main 128-bit experiment and for $\eta\in \{1,2,4,8\}$. In the following, we propose an isogeny-based strong designated verifier signature. We prove correctness, non-transferability, signer privacy, and strong unforgeability under Gap Parallelization in the random-oracle model. For $\eta=1$, the redesigned signature is 113 bytes compared with 49 bytes in CSI-SDVS, while signer key sizes remain unchanged.

Distributed common randomness generation (i.e., the common coin problem) is a cornerstone of randomized distributed computing. While a long line of research has sought scalable solutions, the asynchronous setting remains a challenge. Specifically, while Blum et al. (TCC'21) achieved sub-quadratic communication complexity, their approach lacks ``balance'': certain nodes must still send $\Omega(n)$ messages, creating a scalability bottleneck. Furthermore, their solution only tolerates a $1/3 - \epsilon$ fraction of corrupted nodes, whereas the classic construction by Cachin et al. (PODC'00) tolerates up to $1/2$ under the same setup assumptions. In this work, we close these gaps by presenting the first balanced asynchronous common coin protocol with sub-quadratic communication complexity. In our construction, the communication cost of every honest node is bounded by $\widetilde{O}(\sqrt{n})$. Our protocol tolerates an adaptive adversary corrupting up to $(1/2 - \epsilon)n$ nodes. Beyond these asymptotic improvements, our solution avoids the heavy cryptographic machinery (such as fully homomorphic encryption) required by Blum et al. and terminates in just two deterministic rounds, compared to the dozens of expected rounds in prior work. At the heart of our construction are explicit and efficient sampler constructions. These samplers partition a population with an honest majority of at least $(1/2+\epsilon)n$ nodes into $O(\sqrt{n})$ communities, ensuring that a majority of these communities maintain a ``forever-honest'' majority. By leveraging how communities are allocated, we design mechanisms that allow each community to collectively emulate a single ``virtual node'' in Cachin et al.'s protocol. Reducing the number of participants from $n$ physical nodes to $O(\sqrt{n})$ virtual nodes drives the total communication complexity to a sub-quadratic level. Finally, we extend our methodology to Asynchronous Binary Byzantine Agreement (ABA), yielding the first balanced ABA protocol with sub-quadratic communication complexity that tolerates up to $(1/3 - \epsilon)n$ adaptive corruptions.

Since the introduction of Threshold Traitor Tracing by Boneh, Partap and Rotem at CRYPTO '24, several works have extended the functionalities within the framework or improved the parameters. However, most of the existing solution fall short in providing post quantum security guarantees. The only lattice-based construction, due to Das et al. from EUROCRYPT '26, achieves post-quantum security but is limited to private tracing: a dedicated tracing authority holds a secret tracing key. In a threshold system, where the fundamental goal is to distribute trust, such a single point of failure is undesirable. In this work, we construct the first threshold traitor tracing scheme that simultaneously achieves post-quantum security and public traceability, where anyone can trace a pirate decoder without any secret tracing key. Our core building block is a Q-Partite Threshold Public Key Encryption (QTPKE) scheme, which is known to imply threshold traitor tracing when combined with a robust IPP code: we build QTPKE from plain Learning With Errors (LWE) using a key-shifting mechanism on top of Regev's encryption scheme thresholdised via {0,1}-Linear Secret Sharing. We finally prove the security of our scheme in the standard model under standard lattice assumptions.

The concrete security of multivariate post-quantum signature schemes is coming under increasing scrutiny as the NIST standardisation process for additional signatures approaches its final stages. Among the leading candidates, the security of MAYO and QR-UOV relies on the hardness of the underdetermined multivariate quadratic (MQ) problem. This work revisits Hashimoto's algorithm for solving underdetermined systems of MQ equations, reinterpreting it as a computation of a pseudo-oil subspace. In light of this geometric point of view, we design a new algorithm that, by computing richer pseudo-oil structures, distributes algebraic work across more than two Gröbner Basis steps, subdividing the initial MQ problem into multiple subproblems that can be solved separately, while linearising multiple equations. Optimising a set of discrete parameters, we select the best trade-off between algebraic solving and combinatorial search. Concretely, our approach lowers the cost of the direct attack against Security Level I parameter sets of MAYO and QR-UOV by 7 and 8 bits, respectively.

Masking is a widely adopted countermeasure to protect cryptographic implementations from side-channel attacks. Subsequent research has focused on designing masking schemes and formally proving their security, notably through the development of automated tools, within models abstracting the reality of a sidechannel analysis. These designs rely on an external source of randomness; however, there is currently no consensus on the choice of (pseudo-)random number generators for masking. To the best of our knowledge, existing formal proofs for masking security do not consider particular choices of random number generators, but rather assume that they yield uniformly distributed and independent random variables. In that context, we introduce the first verification framework that jointly analyzes a pseudorandom number generator— specifically, but not limited to, a linear feedback shift register—and a masking scheme, in the d-probing model. Our framework relies on the Walsh-Hadamard transform by drawing on techniques from linear cryptanalysis, which we extend to the robust probing model. We demonstrate our method on 4-bit and 8-bit S-boxes, provide a detailed analysis of the formal verification outcomes, and corroborate the findings with practical evaluations on an FPGA.

The random probing model is a theoretical model that abstracts the physical leakage of an embedded device running a cryptographic scheme with more realistic assumptions compared to the threshold probing model. It assumes that the wires of the target device leak their assigned values with probability $p$, and the said values may reveal information about secret data, which could lead to a security violation. From that, we can compute the probability $\epsilon$ that a side-channel adversary may learn secret data from any random combination of wires as a function of the number of wire combinations that breaches security with rate $p$. This model is used to evaluate the security of masked cryptographic implementations, or simply named circuits; and the research community has been focusing so far on approximating or estimating the probability $\epsilon$ for one circuit. Yet, no proposition has been made to quickly compare the probability $\epsilon$ of different circuits, e.g., a circuit and its optimized version. In this context, we present two statistical tests to make decisions about the level of security in the random probing model: the equivalence test compares the security of two circuits in terms of $\epsilon$'s and the superiority test decides whether the undetermined $\epsilon$ of one circuit falls below a security threshold $\epsilon_0$, both with quantified uncertainty about the computations of the probabilities $\epsilon$'s. The validity of these tests is proven mathematically sound and verified via empirical studies on small masked S-boxes.

Non-malleable zero-knowledge argument(NMZK) is a strong notion of zero-knowledge argument that ensures security against man-in-the-middle(MIM) attacks. While three-round constructions exist for various weak zero-knowledge arguments under standard assumptions, all known (weak) NMZK protocols in the plain model have required at least four rounds. In this work, we construct the \emph{first three-round weak non-malleable zero-knowledge argument} under standard cryptographic assumptions. Our protocol satisfies weak zero-knowledge and $\epsilon$-non-malleability, where the latter allows an $\epsilon$ probability gap between the MIM experiment and the stand-alone experiment for any polynomial inverse $\epsilon$. Our construction relies only on well-established primitives, such as the existence of two-message oblivious transfer protocols and delayed-input WI arguments, non-interactive commitments, and circuit-privacy fully homomorphic encryptions.

Shuffling is a fundamental operation in secure multiparty computation (MPC), yet existing maliciously secure protocols for shuffling $m$ elements among $n$ parties require at least $n^2m$ online communication and computation, compared with $O(nm)$ in the semi-honest additive-sharing setting. We formalize and extend the \emph{permute-in-turn paradigm}, which constructs MPC shuffles from permutation protocols, capturing the methodology adopted in most prior works. Our generic transformations achieve semi-honest or malicious security with only $O(C_{\mathrm{BC}}+nm)$ online communication and computation, where $C_{\mathrm{BC}}$ is the cost of one parallel broadcast (allowing unanimous abort). Our transformations are \emph{for free} in two senses: they yield linear online phases without exceeding the overall asymptotic cost of applying $n$ MPC permutations, while \emph{freeing} the online phase of the shuffle protocol from dependence on the MPC permutation protocol. This decoupling allows future work to optimize permutation protocols independently while benefiting all MPC shuffle protocols that follow the paradigm. Instantiated with additive and Shamir secret sharing, our transformations yield the first maliciously secure shuffles with $O(C_{\mathrm{BC}}+nm)$ online cost, improving previous bounds of $O(Bn^2m)$ and $O(n^2m\log m)$, respectively, where $B$ is a cut-and-choose parameter. We formally prove semi-honest and universally composable (UC) security for the corresponding transformations. For $m=2^{12}$ and $n=15$, our prototype achieves over $60\times$ lower online runtime and $120\times$ lower online communication than prior work, with only a $1.3\times$ increase in total runtime.

We present a RAM-efficient implementation of Falcon: RAM usage has shrunk to about 11 kB, down from about 31 kB in the previous implementation of Falcon-512. This code is furthermore faster on Arm Cortex M4, with average signature generation cost down to 13.45 million cycles. Optimization techniques include a novel variant of the FFT, replacement of some floating-point operations with modular integer computations, delayed addition of input within the Fast Fourier sampling process, and an alternate signature reassembly process. More than half of the floating-point operations have been removed. The resulting implementation is now small enough to allow use in small embedded systems such as smart cards.

Let $N = pq$ be the product of two balanced primes. Cotan and Te\c seleanu (2023) introduced a family of RSA-like cryptosystems defined by $ed - k(p^n - 1)(q^n - 1) = 1$, where $n \geq 1$, encompassing classical RSA ($n=1$) and the Elkamchouchi–Elshenawy–Shaban variant ($n=2$). We present a new attack for $n=3$ that integrates continued fractions with lattice-based methods, naturally extending previous results for $n = 1, 2, 4, 6$.

Let $N = pq$ be the product of two balanced prime numbers $p$ and $q$. In 2023, Cotan and Te\c seleanu introduced a family of RSA-like cryptosystems based on the key equation $ed - k(p^n - 1)(q^n - 1) = 1$, where $n \geq 1$. Note that when $n = 1$, we obtain the classical RSA system, while $n = 2$ yields the variant proposed by Elkamchouchi, Elshenawy, and Shaban. In this paper, we present a novel attack that combines continued fractions with lattice-based methods for the case $n = 6$. This represents a natural continuation of previous research, which successfully applied similar techniques for $n = 1, 2, 4$.

Silent threshold signatures (STS) and encryption (STE) enable threshold cryptography without interactive distributed key generation, allowing a group of $N$ parties to non-interactively generate a joint public signature verification key or an encryption key. However, modern distributed systems (such as Ethereum) rely on small, dynamically changing committees of size $n \ll N$ for efficiency, and existing silent threshold schemes either fail to support this dynamic setting or suffer from severe scalability issues. To the best of our knowledge, the only prior STS construction for dynamic committees, Dyna-hinTS, requires an aggregation time of $O(N\log N)$ per epoch, tightly coupling the cost to the global system size rather than the small active committee. Furthermore, no STE scheme for dynamic committees has been proposed yet. In this work, we present practical silent threshold signature and encryption schemes for dynamic committees, reducing the aggregation cost so that it depends only on the committee size $n$. For signatures, we redesign the Dyna-hinTS framework by replacing its Plonk-style SNARKs with linear pairing checks and a new polynomial commitment for representing the committee, yielding an aggregation time of $O(n\log^2n)$. We also introduce the first silent threshold encryption scheme for dynamic committees with matching efficiency. We further significantly optimize the silent setup phase common to prior STS and STE schemes, reducing each party’s one-time setup (i.e., generating the setup data, referred to as a "hint") cost from $O(N^2)$ to $O(N)$. We implement our schemes in Rust, and the results demonstrate practicality at scale. For a system parameterized with $N = 2^{20}$ and $n = 2^{10}$, the per-party hint generation takes 197 seconds, and signature aggregation takes 0.153 seconds, achieving a $>1900\times$ improvement over Dyna-hinTS. At the same time, our aggregated signature size, verification key size, and verification time (with access to the epoch committee representation) remain constant.

Let $N = pq$ be the product of two balanced prime numbers $p$ and $q$. In 2023, Cotan and Te\c seleanu introduced a family of RSA-like cryptosystems based on the key equation $ed - k(p^n - 1)(q^n - 1) = 1$, where $n \geq 1$. Note that when $n = 1$, we obtain the classical RSA scheme, while $n = 2$ yields the variant proposed by Elkamchouchi, Elshenawy, and Shaban. In this paper, we present a novel attack that combines continued fractions with lattice-based methods for the case $n = 2^i$, where $i > 2$ is an integer. This represents a natural continuation of previous research, which successfully applied similar techniques for $n = 1, 2, 4$.

The advent of quantum computing threatens the security assumptions underpinning classical public-key cryptographic algorithms such as RSA and ECC. As a response, the cryptographic community has focused on developing quantum-resistant alternatives, with hash-based signature schemes emerging as a compelling option due to their reliance on well-understood hash functions rather than number-theoretic hardness assumptions. This paper presents a comprehensive review of hash-based signature schemes, covering the foundational building blocks (Lamport signatures, Winternitz one-time signatures, Merkle trees, and FORS) as well as the three standardized constructions: XMSS (RFC 8391), LMS (RFC 8554), and the stateless SPHINCS+ (FIPS 205 / SLH-DSA). A systematic comparison highlights the trade-offs between statefulness, signature size, and implementation complexity. Furthermore, the paper analyzes several notable cryptanalytic attacks, examining for each the attack model, applicable constructions, complexity, and known countermeasures. By discussing both their strengths and vulnerabilities, this work provides a unified reference for understanding the design landscape of hash-based signatures as practical candidates for post-quantum digital signatures.

The widespread use of machine learning on sensitive data makes Privacy-Preserving Machine Learning (PPML) essential for data confidentiality. Current state-of-the-art PPML systems employ hybrid protocol designs to evaluate various operators to achieve better performance; yet, existing hybrid approaches adopt fixed protocol assignments without considering the deployment setting, resulting in inefficiencies across diverse network environments, such as LANs and WANs. To address this, we introduce NetAdapt, a cost-model-driven framework that automatically assigns FHE and MPC protocols to optimize inference efficiency under varying network conditions, by designing a predictive cost model based on the dialect of the Multi-Level Intermediate Representation (MLIR)’s Tensor Operator Set Architecture (TOSA), and an ILP-based solver for managing the cross-protocol conversion while dynamically updating FHE costs based on homomorphic multiplication depth. Experimental results demonstrate that NetAdapt delivers $6.68\times$ to $12.92\times$ improvements in inference running time compared to state-of-the-art solutions, allowing network-agnostic PPML.

We investigate how partial physical leakage can be amplified through public algebraic relations, using HAWK as a concrete case study of implementation security in an algebraically structured post-quantum signature scheme. HAWK is a lightweight, floating-point-free lattice-based signature scheme whose discrete Gaussian sampler can expose side-channel information during signing. We formalize such leakage as HAWK with Hint and study full-coefficient, exact-sign, and noisy-sign leakage. Our polynomial-time recovery algorithms combine sampler hints with public signing information and HAWK's Gram-matrix public-key structure, showing that complete sampler-output recovery is not necessary for full key recovery. For HAWK-1024, we obtain the following results under the stated threat models. With full coefficient leakage, a single signature suffices for secret-key recovery by directly solving the induced linear system. On the HAWK-1024 reference implementation, we identify all 2,048 coefficient-sampler invocations in each of 14 measured signing traces, extract all 28,672 coefficient signs without error, and recover the fixed key using the Category II attack. In separate controlled experiments over 100 independently generated keys, Category II achieves 100% success using 14 exact-sign signatures in approximately 157 seconds. Under the independent sign-error model, Category III achieves 100% success using 420 signatures at a 10% error rate and 13,397 signatures at a 40% error rate. The latter setting requires approximately 178 seconds. These results show that coarse and even erroneous sampler leakage can become sufficient for full key recovery when combined with HAWK's public algebraic structure.

Block ciphers including several variants of the well-known \textsf{AES}, the newly proposed tweakable block cipher \textsf{Deoxys-BC} (standardized by ISO/IEC and renamed Deoxys-TBC), and \textsf{ChiLow} (EUROCRYPT 2025) adopt key sizes larger than their block sizes. These designs offer security higher than the block size. This paper evaluates the security of such ciphers by revisiting the Impossible Polytopic Attack (\ipa{}, proposed by Tyge Tiessen at EUROCRYPT 2016). We show that \ipa{} can build longer-round distinguishers, enabling attacks on more rounds. Moreover, the attack is applicable under the known-plaintext (KP) setting. Towards this end, we first formalize the distinguisher from Tiessen’s original work and establish a generic framework for distinguisher construction. We further propose two novel methods to lower the corresponding construction complexity. Moreover, we develop two dedicated key-recovery techniques, namely the plaintext‑grouping technique and the partition-guess-filter technique. The former allows cryptanalysis on more rounds of target ciphers, while the latter substantially lowers the overall attack complexity. Finally, we build the first framework for \ipa{}. We apply our method to the chosen-plaintext/ciphertext (CP/CC) and KP scenarios under the single-key setting. As a result, we obtain new distinguishers and attacks against \textsf{AES}, \textsf{Deoxys-BC}, \textsf{Joltik-BC}, \textsf{LED-128}, and \textsf{ChiLow-32}. Notably, 10-round attacks are constructed on \textsf{Deoxys-BC-384} and \textsf{Joltik-BC-192}. Compared with impossible differential attacks, which are closely related and extensively studied, the proposed results outperform such attacks by one round. Furthermore, a novel full-round attack on \textsf{ChiLow-32} is constructed under the KP setting, achieving the state-of-the-art attack with optimal data complexity and overall complexity.

MACsec Key Agreement (MKA) is the IEEE 802.1X key-management protocol used to establish and maintain Secure Associations for MACsec deployments. Although MKA is widely deployed, machine-checked analyses of its core key-agreement logic remain scarce. This paper presents a formal analysis of a simplified two-party MKA exchange using the Tamarin prover. We model the initial session establishment and a subsequent rekey round, and verify secrecy, authentication, agreement, ordering, and freshness properties. The analysis confirms these guarantees under a Dolev--Yao adversary when the pre-shared Connectivity Association Key (CAK) is not compromised. We also identify a structural weakness: a malicious or compromised Key Server can inject an arbitrary Secure Association Key (SAK) that the Server accepts. This finding clarifies the trust assumptions of MKA and motivates additional verification or binding mechanisms for partially trusted deployments.

Discrete CKKS is a promising approach for performing high-throughput homomorphic computations over encrypted discrete data. Although it relies on CKKS, an approximate FHE scheme, as the computation engine, discrete CKKS can achieve exact correctness. The core operation of discrete CKKS is functional bootstrapping, a mechanism which enables evaluating an arbitrary function over a bounded discrete domain by representing it as a lookup table and computing it as part of bootstrapping. Simultaneously, the same procedure enables reducing the input ciphertext noise using Hermite interpolation methods. This noise reduction feature is critical for both supporting arbitrary computations and improving the efficiency of their evaluation, by providing more noise budget between bootstrapping invocations. In this paper, we first show that both state-of-the-art Hermite interpolation noise reduction methods by Bae et al. (ASIACRYPT'24) and Alexandru et al. (CRYPTO'25) have a limited noise reduction ability for distinct structural reasons. We then propose a new method that can efficiently overcome these limitations by using a CKKS-friendly *arbitrary-order* Hermite interpolation. We call this method "sparse" trigonometric Hermite interpolation because both constraints and coefficients have convenient sparsity properties, which allow us to achieve efficiency comparable to the fastest prior method by Alexandru et al., while attaining superior noise reduction. In the process, we develop a metric that measures the noise budget between consecutive functional bootstrapping invocations, and use it to compare all methods on equal footing. We implement our new method in OpenFHE and experimentally demonstrate its noise reduction advantage over prior methods.

Group signatures (GSs; Chaum and van Heyst, EUROCRYPT 1991) are digital signatures that allow a signer to anonymously prove group membership, while still enabling a special authority, called the opener, to identify the signer when necessary. Group Signatures with Message-Dependent Opening (GS-MDO; Sakai et al., Pairing 2012) weaken the power of the opener by introducing another authority, the admitter, who issues a message-dependent token. In previous GS-MDO schemes, these tokens can be viewed as signatures. Therefore they can be publicly verified using the verification algorithm of the underlying signature scheme. However, no explicit notion of public verifiability for tokens, meaning the ability to publicly verify whether a token can be used for opening a group signature, has been defined so far. Clarifying this implicit security property is important for understanding the feasibility of GS-MDO. In this paper, we formally define public verifiability of tokens. We establish a proper relationship between verifying a token as a signature and verifying that the token can be used for opening, which typically requires the opener's secret key. We also show that the Ohara et al. pairing-based GS-MDO scheme (AsiaCCS 2013), the Libert et al. lattice-based GS-MDO scheme (ACNS 2016), and the Libert et al. pairing-based GS-MDO scheme (CT-RSA 2014) satisfy our definition, suggesting that our formalization is reasonable. Finally, we discuss how publicly verifiable tokens can be used to provide accountability for the admitter, enabling them to demonstrate that tokens have been honestly generated according to the token-generation algorithm.

One of the main hallmarks of proof-of-work (PoW) consensus protocols is their ability to adjust the difficulty of the PoW, so that it accurately reflects the level of participation and hence maintains security in a setting where protocol participation is unknown and may over time change dramatically. Importantly, this enables the protocol to retain its fundamental characteristics (such as the regularity of dispensing new tokens) irrespectively of the number of parties running the protocol (also known as ``miners'') at any given time. The speed with which difficulty can be adjusted is a fundamental feature of a blockchain protocol: The faster the rate with which the difficulty is adjusted, the more agile the protocol is in the face of fluctuating participation. In this work, we put forward, for the first time, a blockchain protocol that performs difficulty adjustment in constant time; prior provably secure designs only offered protocols with, at best, poly-logarithmic overhead for difficulty adjustment. Our construction is based on the parallel-chain approach and a new target recalculation function that adjusts mining difficulty making use of information from all chains in the past epoch via a novel application of approximate-agreement techniques that may be of independent interest.

We present the first pairing-based unbounded broadcast encryption and key-policy attribute-based encryption (KP-ABE) with sublinear ciphertext size. Here, unbounded means set-up and the public parameters do not impose a bound on the size of the broadcast set, attribute length, or policy size. - Our broadcast encryption scheme supports an unbounded number of users, and achieves \[ |mpk| = O(1), |ct| = O(\sqrt{N}), |sk| = O(\sqrt{N})\] where $N$ denotes an upper bound on the size of the broadcast set. - Our KP-ABE supports boolean formula and span programs, and achieves \[ |mpk| = O(1), |ct| = O(\sqrt{N}), |sk| = O(\sqrt{N} \cdot |f|)\] where $N$ is the attribute length and $|f|$ the policy size. We prove adaptive security for the broadcast encryption and selective security for the KP-ABE, based on the $k$-Lin assumption in the standard model without random oracles.

We prove that every information-theoretic two-server private information retrieval scheme for $n$-bit databases requires $(6-o(1))\log n$ bits of communication. This improves on the $5$ of Wehner and de Wolf (ICALP 2005), who had raised the $4.4$ of Kerenidis and de Wolf (STOC 2003), who in turn had raised Mann's original $4$ (M.Sc.\ thesis, 1998). Our proof follows the quantum route of the earlier bounds: encode the database in a quantum state, recover an entry from enough copies of it, and apply Nayak's bound (FOCS 1999) on quantum random access codes. Previous proofs read that entry as a binary outcome with a small bias toward the correct answer, and pay the inverse square of that bias to amplify it. We instead allow a real-valued outcome whose mean is the correct answer, and pay only its second moment. The same readout strategy improves the other lower bounds of Wehner and de Wolf, for smooth codes and locally decodable codes. In particular, it drops the linearity assumption in the lower bounds of Goldreich, Karloff, Schulman, and Trevisan (CCC 2002) almost for free.

Secure three-party computation (3PC) with semi-honest security under an honest majority offers notable efficiency in computation and communication; for Boolean circuits, each party sends a single bit for every AND gate, and nothing for XOR. However, round complexity remains a significant challenge, especially in high-latency networks. Some works can support multi-input AND and thereby reduce online round complexity, but they require \textit{exponential} communication for generating the correlations in either preprocessing or online phase. How to extend the AND gate to multi-input while maintaining high correlation generation efficiency is still not solved. To address this problem, we propose a round-efficient 3PC framework ALKAID for Boolean circuits through improved multi-input AND gate. By mixing correlations and redundancy, we propose a concretely efficient correlation generation approach for small input bits $N<4$ and shift the correlation generation to the preprocessing phase. Building on this, we create a round-efficient AND protocol for general cases with $N>4$. Exploiting the improved multi-input AND gates, we design fast depth-optimized parallel prefix adder and share conversion primitives in 3PC, achieved with new techniques and optimizations for better concrete efficiency. We further apply these optimized primitives to enhance the efficiency of secure non-linear functions in machine learning. We implement ALKAID and extensively evaluate its performance. Compared to state of the arts like ABY3 (CCS'2018), Trifecta (PoPETs'2023), and METEOR (WWW'2023), ALKAID enjoys $1.5\times$--$2.5\times$ efficiency improvements for boolean primitives and non-linear functions, with better or comparable communication.

Homomorphic Encryption (HE) enables computations on encrypted data without decryption, but it does not guarantee the integrity or correctness of the performed operations. To address this limitation, verifiable HE (vHE) has been proposed. However, achieving efficient vHE for RNS-based HE schemes (e.g., BFV/BGV/CKKS) remains challenging: While the Residue Number System (RNS) boosts performance of HE via multi-modulus ciphertext representations, it significantly complicates the cross-field consistency checks in vHE. We observe that existing vHEs for RNS-based HE suffer from at least one of the following limitations: they do not readily extend to the zero-knowledge setting (Atapoor et al., CiC 2024), incur linear proof size & verifier cost (Zhou et al., S&P 2025), or are designed for a modified HE scheme (Cascudo et al., Crypto 2025). We present $\mathsf{PRISM}$, the first practical zkSNARK for standard RNS-based HEs. Our techniques are threefold: (1) a new cryptographic primitive called Multiple-Field Polynomial Commitment Scheme (MF-PCS) that efficiently prove the cross-field modulo relations, which is the key bottleneck in RNS-based HE verification; (2) a novel Polynomial Interactive Oracle Proof (PIOP) for (inverse) number theoretic transforms with $O(N)$ prover time and $O(\log N)$ verifier time in a model with an offline phase; (3) upgrading MF-PCS and PIOPs to achieve zero-knowledge with small overhead via Vector Oblivious Linear Evaluation (VOLE) correlations. We fully implemented $\mathsf{PRISM}$ and evaluated it against state-of-the-art schemes. Compared to Zhou et al. which has the fastest prover time, $\mathsf{PRISM}$ has $3.5\times$ slower prover time, but up to $7.8\times$ faster verifier time and $7.8\times$ smaller proof size. Compared to Atapoor et al. which has the smallest proof size, $\mathsf{PRISM}$ has $5.5\times$ larger proof size, but roughly $10.1\times$ faster prover time and $2.6\times$ faster verifier time.

Secret Sharing schemes allow a dealer to distribute $n$ shares $s_1,\ldots, s_n$ of a secret $s$ so that any $t$ shares suffice to reconstruct the secret, while any $t-1$ shares reveal no information about $s$. In fact, schemes such as Shamir Secret Sharing satisfy a stronger guarantee called $(t\!-\!1)$-perfect privacy, meaning that for any subset $S \subseteq [n]$ with $|S| \le t-1$, the joint distribution $(s_i)_{i \in S}$ is uniformly distributed over its domain. This strong guarantee is essential for applications such as fuzzy password-authenticated key exchange (fPAKE) and conditional encryption --- a recent cryptographic primitive introduced to enable secure personalized password typo correction. Unfortunately, Shamir secret sharing is not robust: corrupted shares can prevent correct reconstruction or cause reconstruction of an incorrect secret. Existing robust secret sharing schemes address this issue but necessarily sacrifice perfect privacy. We introduce and construct Random Robust Secret Sharing with Perfect Privacy (RRSS), a new notion that preserves $(t\!-\!1)$-perfect privacy while providing robustness against random share corruptions. In our schemes, the secret is recovered with high probability even if an arbitrary subset of up to $n-t$ shares is independently corrupted at random. We demonstrate the utility of RRSS through two applications. First, we present the first practically efficient fPAKE construction that tolerates Hamming errors. Second, we obtain the first efficient conditional encryption scheme for arbitrary Hamming distances, improving upon prior work that achieved efficiency only for constant distances. We implement both constructions and empirically demonstrate their practicality.

The Fiat--Shamir (FS) transformation is a technique that converts interactive protocols into non-interactive ones. FS is secure in idealized models such as the random oracle model (ROM) (if the interactive protocol satisfies a condition known as state-restoration soundness). It is known that there are protocols whose FS transformation is secure in the ROM, yet insecure when instantiated with any concrete hash function. Historically, these protocols were contrived (as in, they were designed so their FS transformation would be unsound). Khovratovich, Rothblum and Soukhanov (CRYPTO 2025) showed that a class of natural (and practically deployed) protocols based on a protocol of Goldwasser, Kalai and Rothblum (JACM 2015) was also unsound when compiled with FS and any concrete hash function. We extend the attack to a different class of protocols: those whose instances are generated by running a program. This setting covers concrete trends in modern proof systems, in which the computation to be proven is described by a program (often adversarialy generated) which is then either compiled or autonomously converted into an instance of target relation such as rank-1 constraint satisfaction (R1CS). We show that, when the conversion process is "expressive enough", an adversary controlling the program code can break soundness of the non-interactive proof system. The attacks generalize to a wide class of protocols: any protocol in which a cheating prover can prepare an accepting transcript before the statement is bound. We show that variants of the Spartan (CRYPTO 2020) and Aurora (EUROCRYPT 2019) proof systems for R1CS fall in this class. Complementing the attacks, we formalize a mitigation: deriving the first Fiat--Shamir challenge from the generated statement, rather than from the program that generates it, provably reduces the soundness of the compiled protocol to that of the underlying protocol for the non-generated relation.

Secure multiparty computation (MPC) enables distrusting parties in a distributed system to compute on their private inputs without compromising their privacy. For many secret-sharing-based approaches, including some of today's most efficient MPC protocols, there is a pattern where two shared values are locally multiplied into some intermediate representation that is immediately and interactively translated back into sharings of the product. The intermediate representation is often still a full-fledged but different secret sharing scheme. This has been used to efficiently compute dot products by computing the sum of all intermediate products and then interactively translating only the sum instead of translating each individual product. Beyond that, the intermediate representation or secret sharing scheme has mostly been seen only as a necessary interim step, leaving most of its potential untapped. We change that by proposing the paradigm of leveled linear secret sharing, which allows dynamic switching between the original secret sharing and the previously only intermediate one more freely, while enabling arbitrary linear computations in any of the domains. Prior multiplications are split into a non-interactive multiplication that switches from one to the other secret sharing, and an interactive upgrade back to the original secret sharing domain. The upgrade now does not necessarily follow each multiplication immediately, but just needs to be placed somewhere before the next multiplication is computed, possibly upgrading the linear aggregation of many multiplications' results. We apply this idea to improve three-party computation on replicated sharings (CCS'16), n-party BGW-style protocols (STOC'88), and masked secret sharing protocols such as ABY2.0 (USENIX Security'21). We build a novel optimizer that optimally selects which gate of a circuit is evaluated in which domain. With that, we improve communication by 10-37% for many circuits. Furthermore, we implement our generalization for replicated sharing, measure run time improvements of mostly 10-26% in a LAN, and make a full implementation of the protocol and our novel optimizer publicly available.

Towards bridging the gap between passively and actively secure multiparty computation (MPC), the use of sublinear distributed zero-knowledge (DZK) proofs gained popularity. Such proofs enable extending a passively secure protocol by adding a verification step whose communication is sublinear in the circuit size. For arbitrarily many parties and a dishonest majority, adding a trusted dealer enables efficient computation, as recently shown by Asterisk (IEEE S&P'24) without requiring DZK. This setting is also compatible with DZK, as shown by Boyle et al. (CRYPTO'21). Unfortunately, their approach is not tailored to computation over a ring $\mathbb{Z}_{2^k}$, often favored for concrete efficiency and practicality, resulting in high computational overhead. In the honest majority setting with few parties, Li et al. (CCS'24) optimized DZK to rings, achieving significant performance improvements. In this work, we propose the first sublinear verification protocol that is both, designed for the $n$-party dishonest majority setting with a dealer, and tailored to computation over a ring $\mathbb{Z}_{2^k}$, combining and improving upon both approaches above. Previous approaches used $n$ DZK proofs to check correct behavior for each individual party. Instead, we show how to verify in a single, novel DZK proof that all parties together behave correctly. This decreases the communication complexity for verification from $\mathcal{O}(n \cdot \log m)$ to $\mathcal{O}(n + \log m)$ ring elements per party for $m$ multiplications. Hence, for the first time, active security using DZK scales well with the number of parties $n$. We provide the first public implementation for DZK with arbitrary $n$ and a dealer and show its practical efficiency. For $m=10^6$ multiplications across 30 layers, communication increases by only 0.7% over the passively secure base protocol with only moderate computation overhead. This becomes especially useful in a WAN setting, where we achieve active security at only 34% run time overhead over the passive variant. Compared to Asterisk (IEEE S&P'24), our protocol has 1.8x better communication and improves run time by 2.5x in WAN and 11.9x in LAN.

Open-source large language models (LLMs) are increasingly competitive with closed-source models while offering transparency and the ability to run inference without exposing user inputs to a service provider. However, running large-scale models locally requires substantial computational resources. In practice, users may still resort to a third-party provider, giving rise to privacy and correctness concerns. Existing solutions that address these problems often impose substantial server overhead or introduce additional trust assumptions. In this paper, we present Maverick, a novel approach to private and verifiable LLM inference based on a protocol for delegating matrix-vector multiplication, a dominant operation in LLMs. At its core, Maverick provides, to our knowledge, the first information-theoretically sound verification protocol for matrix-vector multiplication delegation with transparent preprocessing, efficient (batch) verification, and virtually no server overhead. We combine this verification primitive with LPN-based pseudorandom masking to provide input privacy. We implement our matrix-vector delegation primitive and use it to build an end-to-end prototype of Maverick, which we evaluate on Qwen3-4B by measuring throughput in tokens per second. We evaluate client configurations with 1-8 threads. With one client thread and a CPU server using up to 128 threads, Maverick achieves throughput gains over local inference of up to 17x when privacy masks are generated online, 45x when they are precomputed, and 44x when only verification is required. With four client threads, the corresponding gains are 13x, 18x, and 17x. When server computation is no longer the bottleneck, client-side microbenchmarks with simulated network delay show speedups of 12x-20x, 34x-135x, and 38x-157x.

The AES S-box is constructed from finite field inversion followed by a fixed affine transformation. Since inversion possesses intrinsic Frobenius symmetries among its coordinate realizations, we study how these basis symmetries are altered by outer affine transformations. We first develop a deterministic rigidity criterion for transformed inversion and apply it to the AES S-box. This shows that the linear part of the AES S-box affine transformation alone makes the transformed inversion map basis rigid. We then investigate the corresponding generic problem when the outer invertible linear transformation varies. The existence of a nontrivial common linear stabilizer is reduced to a conjugacy problem for semilinear candidates arising from two sided linear equivalences of inversion, which we characterize in terms of relative norms and Frobenius orbits. We also determine the dimensions of the associated centralizer algebras exactly. These structural results imply that, for a uniformly chosen outer linear transformation, the probability that the linear stabilizer is nontrivial is bounded by $2^{-\Omega(n^2)}$, with sharper finite dimensional bounds obtained from the exact conjugacy condition. Computational experiments independently verify the AES rigidity result, the conjugacy and centralizer formulas, and the finite dimensional estimates in small dimensions.

Structure-preserving (SP) cryptography enables the modular composition of pairing-based primitives through the definition of cryptographic algorithms whose public inputs and outputs are group elements and whose computations are generic group operations or pairings. Despite their potential usefulness, obtaining compressing primitives such as accumulators and vector commitments in the SP setting has remained a long-standing challenge, partly due to known impossibility results [Abe et al. Eurocrypt 2012]. Recently, [Krenn, Mir, and Slamanig PKC 2026] proposed the first SP vector commitments (SPVC) and accumulators (SPA) that circumvent these barriers via the adoption of structured message spaces that, albeit restricted, enable interesting applications such as constant-size pairing-based ring signatures. In this work, we revisit the security of these recent constructions with a twofold contribution. First, we identify attacks against the recently proposed SPVC, SPA, and ring signature schemes. Second, we present new constructions of SPVCs and SPAs that preserve the efficiency and structure-preserving nature of the original designs while achieving the desired standard security notions of position-binding and collision-resistance respectively. Specifically, we construct a new SPVC with constant-size proofs and verification under the power discrete logarithm assumption in the algebraic group model. Building upon it, we introduce a new notion of SPA with extended message spaces and give a construction achieving collision resistance and constant-size membership proofs under the same assumption. Finally, we apply our techniques to obtain constant-size ring signatures in bilinear groups.

We provide a new variant of OAEP called OAEP†, which converts an almost trapdoor injective function (ATIF) to a public-key encryption (PKE) scheme. The resulting PKE not only has CCA security but also enjoys pseudo-randomness, anonymity, and robustness under chosen-ciphertext attacks in the quantum random oracle (QRO) model. Compared with the plain OAEP and its variants whose structure does not serve the quantum world very well, our OAEP† is designed with a new structure, admitting more flexible choices for ATIF and enjoying better security and efficiency. For OAEP†, we present two instantiations of ATIF from NTRU, which yield two practical post-quantum PKE schemes from lattices. The resulting PKE schemes are comparable to Kyber and NTRU-HPS derived from FO transform. The performance evaluations show that one of our PKE schemes is faster than Kyber512, and the other shares the same basic underlying structure with NTRU- hps2048677 but can additionally encrypt 132 bytes message. Our OAEP† does not use the (third) additional hash function (unlike Q-OAEP) and has a tighter security reduction (than Q-OAEP), and thus answers the open problems proposed by the authors of NTRU, who proposed the NTRU KEM candidates in NIST’s third round of post-quantum cryptography standardization. And replacing the FO transform with OAEP† in NTRU-HPS (one of NTRU KEM in the third round) yields a CCA-secure PKE scheme that is as efficient as the original NTRU-HPS (from FO) but better than the PKE hybrid from NTRU-HPS and a symmetric encryption. Besides NTRU, ATIF also has instantiations from isogenies/lattices. So OAEP† yields post-quantum CCA-secure PKE/KEM schemes from lattices/isogenies in the QRO model as well, suggesting the wide applicability of OAEP† in the quantum world.

We present RoKoko, a new lattice-based succinct argument system that achieves a linear-time prover alongside polylogarithmic communication and verifier complexity. Asymptotically, our construction improves upon RoK and Roll (ASIACRYPT 2025), the first post-quantum SNARK with $\tilde{O}(\lambda)$ proof size, by a multiplicative factor of $\Theta(\log \lambda)$. Practically, our system yields proofs of roughly $200$KB, while outperforming the state-of-the-art polynomial commitment scheme Greyhound (CRYPTO 2024) with a $100\times$ faster verification time, similar prover time, and competitive proof size. Our framework natively supports (tensor-)structured relations, such as polynomial evaluation and sumcheck relations. At a high level, our construction follows the recursive split-and-fold paradigm: the prover first splits the witness into $\rho$ sub-witnesses, sends the corresponding cross-terms, and then folds them into a single witness that is shorter by a factor of $\rho$ using verifier challenges. Prior works typically restrict $\rho = O(1)$ to preserve succinct verification and maintain the optimal $\tilde{O}(\lambda)$ proof size. We overcome this “constant barrier”, which enables larger $\rho$ and thereby reduces the proof size. To achieve this, we introduce the following technical contributions. (i) Committed folding. Instead of sending $O(\rho)$ cross-terms in the clear, the prover commits to the messages and later proves that the committed vector satisfies the verification relations. This enables the use of a larger shrinking factor, thereby reducing the number of recursion rounds. While this strategy has been successfully used in LaBRADOR (CRYPTO 2023), additional care is required here to preserve succinct verification. (ii) Recursive commitments. We generalise the double-commitment technique from LaBRADOR into a framework for recursive commitments, yielding further compression in commitment size. This results in concrete improvements in communication within each recursion round. (iii) Sumcheck-driven structured recursion. We extend the sumcheck framework from SALSAA (ePrint 2025/2124) to prove substantially more complex constraints arising in our construction (and open for future extensions), including correctness of random projections, inner-product claims and well-formedness of recursive commitments. While expressing these constraints as sumcheck relations requires considerable technical effort, the resulting protocols compose seamlessly with the structured recursion, yielding both linear-time proving and succinct verification.

Motivated by digital signature algorithms ranging from Falcon to fully-anonymous ring signatures used in Signal-style key exchange, such as Gandalf, we revisit a fundamental problem in post-quantum security proofs: distinguishing oracle functions whose outputs are sampled independently from distributions $P$ and $Q$ that are close. In the context of signatures, closeness is often measured via Rényi divergences, which yield multiplicative bounds in the classical setting. A counterexample shows that such multiplicative-error bounds for distinguishers with classical oracle access have no analogue for quantum access, and we provide two alternative approaches based on small-range distributions and reprogramming techniques. We also give a concrete, optimal bound for the case where $P$ and $Q$ are close in statistical distance. We apply these techniques to the motivating constructions. (i) We give the first QROM security proof for Falcon that avoids oracle indistinguishability arguments based on statistical distance. This is crucial, as Falcon's ROM proof relies on Rényi divergence, while the statistical distance induced by its parameters is too large to yield meaningful bounds. (ii) We formalize and abstract the ring signature construction used in Gandalf as a modular framework by defining ring trapdoor preimage-sampleable functions (RPSFs), for which we obtain two QROM proofs. We also provide two QROM security proofs for AOS ring signatures, adapting existing QROM techniques. Together with our results on RPSF-based ring signatures, this yields QROM security proofs for a broad class of fully-anonymous linear ring signature constructions, including Gandalf and the AOS-based constructions Erebor and MayoRS.

At Crypto 2023, Dodis, Ferguson, Goldin, Hall, and Pietrzak [DFGHP23] introduced and constructed Random Oracle (RO) combiners, rejuvenating the well-studied area of cryptographic combiners. RO-combiners are (salted) hash function modes of operation over multiple underlying compression functions that achieve indifferentiability as long as at least one of the underlying compression functions is ideal. Unfortunately, the security of RO-combiners turns out to be a multi-stage game, and the well-established indifferentiability results for hash function modes cannot be lifted to RO-combiners via the composition theorem. There have been two works aiming to construct RO-combiners from scratch. [DFGHP23] built an indifferentiable compression-function combiner, whose deployment requires a new hash implementation, limiting its scope. The follow-up work by Dodis, Goldin, and Hall [DGH25] at Eurocrypt 2025 constructed the first secure RO-combiner capable of handling a large but fixed-length message using \MD hashing. However, implementing their construction either requires a random salt larger than the message length (potentially exponential in the security parameter) or incurs up to an exponential number of calls to the underlying \MD hash. In this paper, we introduce a new design principle for robust RO-combiners that yields efficient and instantly deployable solutions. At the same time, the principle is generic, enabling the construction of robust variable-input-length RO-combiners from a wide class of popular hashing modes. Our main result constructs robust RO-combiners from standard \emph{preimage-aware} hash constructions by salting each compression function call and applying a post-processor. The required salt size is $\mathcal{O}(n)$ for $n/2$-bit security and is independent of the input message size. Moreover, the combiner makes only a single call to each of the underlying hash modes. We show instantiations using both linear \MD and tree hashing. From an instantiation perspective, with only a simple modification to message padding, our variable-length \MD combiner can be readily obtained with SHA-256 or Blake2. The combiner requires just $1408$ bits of randomness while achieving $128$-bit security and a message processing rate of $320$ bits per compression-function call.

In this work, we present the first practical verifiable weighted secret sharing (VWSS) scheme based on the Chinese Remainder Theorem (CRT). Classical secret sharing schemes, such as Shamir’s, assume participants with equal weights, which is inadequate for emerging applications like stake-based DAO voting and proof-of-stake blockchains, where parties naturally have unequal voting power or stakes. While prior work (e.g., Garg et al., Crypto'23) demonstrated that CRT-based (ramp) secret sharing can support weighted access structures more efficiently than linear secret sharing schemes, existing constructions only guarantee security against honest-but-curious dealers. In contrast to traditional linear secret sharing schemes, extending verifiability to CRT-based weighted secret sharing remains challenging, as current approaches either fail to support weighted access structures or incur prohibitive computational overhead on the dealer, limiting their practicality. To address this gap, we develop novel $\Sigma$-protocols for the \emph{unbounded} proof-of-mod (UPoM) relation using integer commitments in groups of unknown order, which may be of independent interest. Combining our UPoM protocols and new observations on the structural properties of CRT-based secret sharing, we construct a VWSS scheme in which the dealer broadcasts only $O(|A|)$ commitments to secret shares, where $A$ is a subset of parties whose total weight meets the reconstruction threshold $T$. This improves upon the closest prior CRT-based VWSS scheme (Shehata et al., CVC'25), which requires the dealer to broadcast commitments to the secret shares of all parties. Concretely, for a system with four participants and total weight $524$, our scheme generates VWSS proofs in around $0.2$ seconds, \emph{orders of magnitude faster} than the construction of CVC'25, highlighting its practicality for real-world applications.

In this work, we study the communication complexity of information-theoretic MPC with guaranteed output delivery (GOD) in the honest majority setting $(t<n/2)$. The recent work by Song and Ye (EUROCRYPT 2025) gives an honest majority MPC in the random oblivious linear evaluation (OLE) preprocessing model that computes an arithmetic circuit of size $|C|$ with malicious security with abort at the cost of $O(|C|)$ of both communication in field elements and total number of random OLE correlations. We explore the possibility of deriving a similar result for the stronger security notion of GOD. Specifically, we ask the question: `` Is it possible to construct an information-theoretic honest majority MPC in the random OLE preprocessing model that computes an arithmetic circuit of size $|C|$ and achieves GOD with $O(|C|)$ field elements of communication and $O(|C|)$ amount of random OLE correlations in total? '' We resolve the above question in the affirmative by providing a concrete construction. To achieve our result, we mainly rely on two techniques. First, we propose a new secret sharing scheme which we refer to as detectable secret sharing. It is a packed secret sharing scheme with an authentication mechanism. Second, to efficiently verify the computation and locate an error when faults occur, we extensively make use of the virtual transcript technique introduced in the work by Goyal, Song, and Zhu (CRYPTO 2020). Our construction is in the random OLE preprocessing model where we assume random OLEs between each pair of parties. By instantiating the random OLEs from various assumptions, we obtain three honest majority MPC protocols with GOD with the following security and communication: (1) the first one achieves information-theoretic security with offline communication of $O(|C|n)$ elements and online communication of $O(|C|)$ elements, (2) the second one achieves computational security with $\tilde{O}(|C|)$ elements of communication only from a random oracle, and (3) the third one achieves computational security with $O(|C|)$ elements of communication from pseudorandom correlation generators (PCG).

Let $E$ and $E'$ be two supersingular elliptic curves and let $\varphi: E\to E'$ be an isogeny of known degree $d$. Given a basis $(P, Q)$ of $E[N]$ together with $(\varphi(P), \varphi(Q))$, it is possible to recover $\varphi$ provided that $N$ is sufficiently large and smooth, and that the torsion basis can be represented over a small extension of the base field. In this work, we consider the more general setting where the $N$-torsion may not be efficiently representable. To address this setting, we introduce a new framework for encoding torsion information via an oracle that computes pushforwards of $N$-isogenies under $\varphi$. We then show that there exist instances for which access to the pushforward oracle allows for an efficient isogeny recovery. Beyond their theoretical interest, these instances have direct cryptographic implications. We show a practical attack against the threshold signature scheme recently proposed by Kim, Kim, and Lee. We also identify weak instances for Basso's oblivious pseudorandom function, and we refine the security discussion for Leroux and Roméas's updatable encryption scheme.

Syndrome decoding ($\mathsf{SD}$) over $\mathbb{F}_2$ has long been a central problem in code-based cryptography. Large-weight syndrome decoding ($\mathsf{LWSD}$) is a recent variant whose ternary case was introduced by Debris-Alazard, Sendrier and Tillich (ASIACRYPT '19) in the security analysis of the $\mathsf{Wave}$ signature. It has different hardness characteristics from the classical low-weight $\mathsf{SD}$ problem. However, the security analysis of $\mathsf{LWSD}$ is still limited, and existing work mostly focuses on ternary instances. In this work, we study information set decoding (ISD) algorithms for $\mathsf{LWSD}$ over non-binary fields. Building on the ternary work of Bricout et al. (SAC '19), we give a generalized ISD framework for $\mathsf{LWSD}$ over $\mathbb{F}_q$. The framework is formulated as a single binary merge tree that unifies splitting-based, representation-based, and hybrid ISD algorithms. In particular, it captures known large-weight decoding algorithms as special cases and allows the merge pattern to be optimized together with the other ISD parameters. We evaluate the framework both asymptotically and concretely. For the asymptotic analysis, we give algorithmic landscapes for the whole $\mathsf{LWSD}$ regime and show which ISD algorithm gives the smallest asymptotic complexity for each instance. We also provide representative asymptotic complexities for several $\mathsf{LWSD}$ instances, including those corresponding to existing work. For the concrete analysis, we provide bit complexity estimates for the $\mathsf{Wave}$ parameter sets. These estimates remain above the claimed security levels.

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

Ma and Huang recently proved that the PFC construction, introduced by Metger, Poremba, Sinha and Yuen [MPSY24], gives an adaptive-secure pseudorandom unitary family PRU. Their proof developed a new path recording technique [MH25]. In this work, we show that a linear number of sequential repetitions of the parallel Kac's Walk, introduced by Lu, Qin, Song, Yao and Zhao [LQS+26], also forms an adaptive-secure PRU, confirming a conjecture therein. Moreover, it additionally satisfies strong security against adversaries making inverse queries. This gives an alternative PRU construction, and provides another instance demonstrating the power of the path recording technique. We also discuss some further simplifications and implications.

We study non-interactive zero-knowledge proofs (NIZKs) for NP satisfying: 1) statistical soundness, 2) computational zero-knowledge (ZK) and 3) certified-everlasting zero-knowledge (CE-ZK). The CE-ZK property allows a verifier of a quantum proof to revoke the proof in a way that can be checked (certified) by the prover. Conditioned on successful certification, the verifier's state can be efficiently simulated with only the statement, in a statistically indistinguishable way. Our contributions regarding these certified-everlasting NIZKs (CE-NIZKs) are as follows: - We identify a barrier to obtaining CE-NIZKs in the CRS model via generalizations of known interactive ZK proofs that satisfy CE-ZK. - We circumvent this by constructing CE-NIZK using non-black-box use of NIZK for NP satisfying certain properties, along with OWFs. As a result, we obtain CE-NIZKs for NP in the CRS model, based on polynomial hardness of the learning with errors (LWE) assumption. - In addition, we observe that the aforementioned barrier does not apply to the shared EPR model. We leverage this to construct CE-NIZK for NP in this model based on any statistical binding hidden bits generator, which is known from LWE. The only quantum computation here involves single-qubit measurements of the EPR pairs.

Multilinear secret sharing can amortize share size over a vector secret, so scalar linear lower bounds need not survive normalization by the secret dimension. We prove that the Razborov–G´al rank measure does survive this amortization: every multi-target monotone span program satisfies a rank inequality in which the target dimension appears multiplicatively. Combined with the characteristic-separated witnesses of Pitassi and Robere, this gives an explicit family of access structures whose average and maximum multilinear information ratios are exponential over every finite field, settling the worst-case order at $2^{\Theta(n)}$. We also study arbitrary sharing algorithms with affine-linear reconstruction under non-perfect security notions, including the pairwise statistical security of Beimel–Othman–Peter and the partial privacy of Jafari–Khazaei. Combining these affine-reconstruction results with the degree-reduction theorem of Beimel–Othman–Peter gives corresponding fixed-degree lower bounds under both security notions, in particular for subexponential secret dimension.

In 2022, a string of attacks on SIDH was released that made use of the now infamous Kani's Lemma. Since then, several new and exciting isogeny-based protocols have emerged that both avoid the attacks, while at the same time, leverage the power of Kani's Lemma to improve their efficiency. One common technique to do so has been the inclusion of masked torsion points. This is when a protocol publishes information about how a secret isogeny acts on a large torsion subgroup, but masks the exact image points by multiplying them by some secret scalars. In this work, we present the first analysis of the physical security of the masked torsion point technique. We provide fault injection attacks on the signature scheme PRISM, and the public-key encryption schemes POKÉ and FESTA. Our fault model is standard in the literature, and can be implemented inexpensively. Most notably, three of the five attacks presented only require one or two first-order faults, which is significantly less than what is needed to attack other isogeny-based cryptosystems that do not use torsion masking.

In TCC 2018, Boneh, Ishai, Passelègue, Sahai, and Wu propose candidates of weak and strong PRFs by evaluating linear functions over coprime moduli alternatively. Such PRFs can be evaluated by low-depth circuits and are MPC-friendly. However, they have not been able to base the security of their PRFs on well-formed assumptions other than assuming that the PRF constructions themselves are secure. In this paper, we formalize a new assumption called Learning with Alternating Moduli (LAM). We show that over certain large moduli, the LAM assumption is as hard as the Learning with Errors (LWE) assumption. For LAM over constant moduli, we do not know how to base its hardness on the LWE assumption. Instead, we provide (i) polynomial-time attacks on LAM with constant prime-power moduli and certain constant non-prime-power moduli, and (ii) evidence of the sub-exponential hardness of LAM with other moduli by analyzing the effect of typical attacks. More specifically, we put forward two new attacks. The first attack is a recursive algorithm that solves LWE with certain constant composite moduli and error distributions. The algorithm extends the Arora-Ge algorithm for LWE from prime moduli to composite moduli, and it also solves LAM for certain parameters. The second attack is a polynomial-time attack that rules out the existence of weak PRFs in $\mathsf{NC}^0[p]$ for any prime $p$. Based on our studies, we propose candidate weak PRFs in $\mathsf{NC}^0[p_1,p_2]$ for some distinct primes $p_1,p_2$ based on LAM over constant moduli, or the Learning with Rounding (LWR) assumption over constant moduli. Compared to the weak PRF candidates by Boneh et al., our weak PRF candidates live in the same complexity class while having the advantage of being based on well-formed assumptions.

The SHA-2 family is a U.S. federal standard and mainly includes SHA-256 and SHA-512. In particular, SHA-256 plays a central role in real-world applications and is widely regarded as one of the most important hash functions in use today. At CRYPTO 2026, Li et al. proposed collision attacks up to 37-step SHA-2, but they could not reach 38 steps due to the low-probability uncontrolled part in the corresponding differential characteristics. In this paper, we propose an improved search procedure to find high-quality differential characteristics for 38-step SHA-256 and SHA-512, respectively. Exploiting the special shape of the 38-step differential characteristics, the meet-in-the-middle method to fulfill the corresponding differential conditions is extremely memory-efficient. Consequently, we successfully achieve the first 38-step collision attack on both SHA-256 and SHA-512, whose time complexity is $2^{104.3}$ and $2^{125.4}$, respectively. The memory complexity of the 38-step collision attack is negligible. The methods are also applied to the 36-step and 37-step collision attacks on SHA-2 published at CRYPTO 2026, leading to a significant improvement in both time and memory complexity. In particular, the time complexity of the collision attack on 36-step SHA-256 is only $2^{57}$ and the memory complexity is negligible. We have verified this collision attack by providing the first colliding message pair for 36-step SHA-256. More remarkably, we apply the new method to 39 steps of SHA-2 and obtain the first effective collision attack on 39-step SHA-512, with a time complexity of $2^{178}$ and negligible memory complexity. However, the method does not yield an effective collision attack on 39-step SHA-256 due to the same issue arising from the low-probability uncontrolled part. Overall, this work further pushed the limit of memory-efficient collision attacks on round-reduced SHA-2 and significantly advances the state of the art.

We present a more practical lattice-based two-round Fiat–Shamir multi-signature scheme that achieves a substantial reduction in signature size compared with DualMS, the state-of-the-art two-round lattice-based Fiat-Shamir multi-signature. Our main technical contribution is a new simulation technique that enables individual signatures to be sampled from distributions with smaller parameters, yielding significant concrete efficiency gains. In addition, through applying the specific modulus-rounding optimization, we can further reduce the sizes of signature and aggregated public-key. Concretely, compared with DualMS, our scheme reduces the signature size by 62.4%, and the aggregated public-key size by 37.5%. For example, with 32 signers, our signature and aggregated public-key are approximately 8.86 KB and 4.38 KB (versus 19.72 KB and 6.94 KB in DualMS) respectively, and for 1024 signers, our signature and aggregated public-key are approximately 11.62 KB and 6.56 KB (versus 30.91 KB and 10.5 KB in DualMS). Moreover, in order to show the practicality of our scheme, we implement our scheme in Go language using the open-source library Lattigo, and then analyze its performance on computation and communication, through both local and WAN experiments. To the best of our knowledge, our scheme achieves the smallest concrete signature sizes among all existing two-round lattice-based multi-signature schemes following Fiat–Shamir with abort paradigm. These results suggest that our scheme is practical and well-suited for real-world deployment.

In conventional $(k,n)$ secret sharing schemes, a dealer distributes shares of a secret among $n$ participants such that any subset of at least $k$ participants can reconstruct the secret. While such schemes often fail to accommodate practical scenarios in which participants have different management permissions over the secret. To address this problem, weighted $(t,n)$ secret sharing was introduced. In this case, each participant is assigned a specific weight, and the dealer distributes a share to each participant according to their weight, so that any subset of participants whose sum of weights is at least $t$ can recover the secret. However, in weighted $(t,n)$ secret sharing schemes, the number of participants $n$ is known in advance. When $n$ is uncertain and even grows over time, traditional weighted $(t,n)$ secret sharing schemes remain inadequate in such dynamic environments. To solve the problem, we propose the concept of a weighted evolving $t$-threshold secret sharing. Based on the prefix codes, we first propose a construction of a weighted evolving $3$-threshold scheme over the polynomial quotient ring for an $\ell$-bit secret. And then we extend the framework to a general weighted evolving $t$-threshold scheme for any $t\geq 3$. Moreover, we prove the correctness and security of the proposed scheme by leveraging the properties of the polynomial quotient ring and prefix codes. Finally, we analyze the corresponding share size. The result shows that for the $m$-th participant with the weight $w_m$ satisfying $1\leq w_m\leq t-1$, the size of the corresponding share is $w_m(t-1-\frac{w_m-1}{2})(\ell_m-1)+w_m\ell$ bits, where $\ell_m$ denotes the length of a binary prefix code of encoding integer $m$. In contrast, a baseline scheme that allocates $w_m$ independent full evolving shares to this participant would require $w_m(t-1)(\ell_m-1)+w_m\ell$ bits. Our proposed scheme saves $\frac{(w_m-1)w_m}{2}(\ell_m-1)$ bits, thereby achieving a smaller share size.