The uniform multivariate quadratic (UMQ) assumption states that it is hard to find a zero of a uniformly generated MQ function. It is the average-case hardness assumption about the MQ problem. In this paper, we investigate the relations among the UMQ assumption, the MQ one-wayness (MQOW) assumption, and the MQ second-preimage resistance (MQSPR) assumption. We show that UMQ and MQSPR tightly imply each other, and MQOW tightly implies UMQ. Then, we show that UMQ implies MQOW when $m\leq n+O(\log\lambda)$, where $n$ is the number of variables, $m$ is the number of MQ equations, and $\lambda$ is the security parameter. In particular, when $m\leq n+O(1)$, this implication is tight. As a corollary, we show that MQSPR implies MQOW under the same condition $m\leq n+O(\log\lambda)$, which is weaker than the compression condition $n=m+\omega(\log\lambda)$ required for the implication from SPR to OW for general function families. In particular, our result covers the square case $m=n$ as well as mildly overdetermined MQ systems satisfying $m=n+O(\log\lambda)$.

In this note, we formally show that the recent algorithm by Simon (ePrint:2026/1591, August 11 2026) does not extract the least-significant bit of the dihedral coset problem (DCP) secret with non-negligible guessing advantage, and therefore does not solve DCP. We emphasize that our result is not merely about Simon's analysis of his algorithm; we are showing directly that the algorithm cannot possibly work. Our no-go encompasses a much broader class of algorithms than the specific algorithm by Simon. The main message of our no-go is that an algorithm for DCP following the template of the reduction by Regev (SIAM Journal on Computing, 2004) will probably have to make extensive use of the classical Fourier labels in the uncomputation stage. On the other hand, the algorithm by Simon can be implemented, up to error $\mathsf{poly}(n)2^{-n/3}$, using only the most-significant third of the classical Fourier labels, and therefore cannot succeed. To help with verifiability, we release Lean 4 code for our results, available at https://github.com/sragavan99/lean-ePrint-2026-1591-refutation.

Poseidon [Grassi, Khovratovich, Rechberger, Roy, and Schofnegger; USENIX'21] is an arithmetization-oriented (AO) hash function designed to be highly efficient in real-world zero-knowledge (ZK) applications. As a sponge-based construction, its algebraic security inherently relies on its underlying permutation, Poseidon-$\pi$, and the dense mixing of its layers: the initial full rounds ($R_{f_0}$), middle partial rounds ($R_p$), and final full rounds ($R_{f_1}$). One of the common approaches to argue security is to bound the effort of solving the $k$-Constrained-Input $k$-Constrained-Output (CICO-$k$) problem over this permutation of state size $t\geq2k$. Recent cryptanalysis has utilized subspace restriction to mitigate algebraic degree growth in Poseidon and used it to argue improvements in CICO-$k$ solving, though prior methods have faced strict limits on the number of rounds they can successfully bypass (more specifically, $<2$) and have targeted $k\leq2$. In this paper, we introduce a unified mathematical framework for advanced subspace restriction in Poseidon cryptanalysis. We first present a baseline gadget; Generalized S-Box Skipping via Subspace Restriction (GSR); that deterministically absorbs $2t-2k$ total S-boxes across: one initial full round ($t$ S-boxes) and $t-2k$ partial rounds (one S-box per round). This significantly reduces the polynomial degree of the Poseidon multivariate polynomial system. By restricting the subspace of the total constraints satisfying solutions, independent of the round constants and MDS matrix selection, the distinguisher expends input degrees of freedom (DoFs) to linearize the internal state transitions where the dense algebraic mixing usually occurs. We then explain and break the first theoretical barrier that confines such subspace restriction techniques to configurations with exactly $R_{f_0}=1$ initial full round. We formalize $(k+1)$-wise collapsing, a non-trivial DoF consumption framework. By parameterizing the system from an intermediate state and formulating constraints backwards, Round 1 is naturally skipped at zero cost. Building on this baseline, for $R_{f_0} \ge 2$ and under the CICO-$k$ setting, $(k+1)$-wise collapsing non-trivially expends a portion of the available DoFs to project state variables into the nullspace of targeted inverse MDS submatrices. This forces a perfect algebraic cancellation of non-linear inverse S-boxes, effectively absorbing the second full round entirely. We show how the residual DoFs, after applying $(k+1)$-wise collapsing, can be either used to combine GSR for partial round skipping or alternatively deployed for bidirectional collapsing, i.e., to skip almost one full round from the back (defeating prepended/appended linear layer defenses) or can be used to construct exactly determined zero-dimensional ideals of strict degree-$3^{1+R_{f_1}}$ for $R_{f_0}=3$ instances. Our framework drastically improves upon the state-of-the-art algebraic limits of Poseidon, most notably by identifying a critical gap in derived theoretical cryptanalysis bounds. We demonstrate that monolithic Macaulay matrix approximations heavily over-estimate true solving complexity. By utilizing residual DoFs to construct exactly determined zero-dimensional ideals of strict degree-3 for $R_{f_0}=3$ instances, we empirically validate our framework by tracking the step-wise intermediate peak of Faugère's $F_4$ algorithm in $\mathtt{msolve}$. Through this, we successfully extract the Gröbner basis for a mathematically intractable $(3,8,0)$ instance of Poseidon with KoalaBear ($t=24$) in under 5 minutes on a standard 96-thread server. Further, in terms of monolithic complexities, where baseline estimates shows a mathematically intractable $F_4$ and FGLM time complexities of $\approx 2^{560}$ and $\approx 2^{404}$ bit operations, respectively, for a $(3,10,3)$ CICO-1 configuration, our framework successfully isolates the system into a degree-$3^4$ ideal, reducing the theoretical time complexities to $\approx 2^{121}$ and $\approx 2^{71}$ bit operations, respectively. Similarly, for a $(3,5,3)$ CICO-2 instance, we achieve a reduction in $F_4$ and FGLM time complexities from $\approx 2^{540}$ and $\approx 2^{390}$, respectively, to $\approx 2^{100}$ and $\approx 2^{69}$ bit operations, respectively, thereby bringing heavily constrained Gröbner basis attacks significantly closer to practical feasibility. We then demonstrate how deploying $(k+1)$-wise collapsing combined with GSR significantly improves the reach of interpolation-based and resultant-based CICO attacks on configurations targeting $R_{f_0}=2$. For the industry standard KoalaBear instance where $(R_{f_0},R_p,R_{f_1})=(4,23,4)$, our results achieve penetrations up to (2,14,4), i.e., 20 rounds for CICO-1, and (2,9,4), i.e., 15 rounds for CICO-2. Finally, when applying our baseline GSR technique only to $R_{f_0}=1$ configurations, our results further extend the attack reach to larger round-reduced versions. We successfully attack up to (1,23,4), i.e., 28 out of 31 rounds for CICO-1, and (1,20,4), i.e., 25 out of 31 rounds for CICO-2, overall establishing new practical limits for subspace restriction against Poseidon.

The relationship between cryptography and learning theory has long been a central theme in the foundations of theoretical computer science: cryptographic primitives can imply hardness of learning, while hardness of learning can in turn be used to construct cryptographic schemes. Recent works have begun exploring analogous connections in the quantum setting, relating the average-case hardness of learning quantum states (AHL) to cryptographic primitives such as one-way state generators (OWSG). Despite recent progress exploring this for pure states, the relationship for mixed states has remained an open question. In this work, we prove that the existence of AHL for mixed quantum states is equivalent to the existence of inefficiently verifiable one-way state generators (IV-OWSGs). As a consequence, this relates mixed-state AHL to EFI pairs. Moreover, as a corollary of existing results, we obtain a separation between IV-OWSGs and OWSGs relative to the SWAP oracle.

A blind signature scheme allows a user to interact with a signer to obtain a valid signature on a message, while ensuring that the signer cannot learn any information on the message being signed, nor link a given couple message-signature to the specific interaction that produced it (blindness). In round-optimal (i.e., two-move) blind signature schemes, a user sends a request (typically a commitment) for a message, and the signer responds with a signature. To achieve blindness, the resulting blind signature usually consists of a zero-knowledge proof of knowledge of a valid signature from the signer on a request. This reliance on zero-knowledge proofs has become the main bottleneck in reducing the blind signature size. In particular, state-of-the-art lattice-based blind signature schemes are instantiated based on the zero-knowledge proof system from [Lyubashevsky et al., EUROCRYPT, 2022], which results in blind signatures of at least 22 KB. In this work, we carefully design a blind signature protocol following the classical lattice-based Σ-protocol as in [Ducas et al., CRYPTO, 2013], so that the last component naturally forms a short preimage of the hash of the message, as a classical GPV signature. As a result, this removes the need for zero-knowledge proofs in the blind signature. Eventually, this design allows us to obtain a significantly more compact blind signature of size 4.7 KB, with concurrent security under the Module-SIS assumption. As a trade-off, our protocol may require more than one round with small probability, due to the rejection sampling in lattice-based Σ-protocols. Under our proposed parameters, however, the expected number of rounds for honest users can be as small as 1.1, which is very close to optimal. To minimize the number of rounds, we require users to prove that they failed to derive a blind signature in the previous round, before starting a new one. This technique yields a moderately looser bound on the expected number of rounds for malicious users, who will be forced to terminate in at most 2.6 rounds.

Harvesting ciphertext from cloud storage needs no quantum computer; decrypting it later does. That gap is the harvest-now-decrypt-later exposure: anything protected by RSA or ECDH today that must stay secret for decades is already compromised. Small and medium-sized enterprises are least able to respond: they neither run the infrastructure on which their data sits on nor employ a cryptographer. Bespoke migration suits firms with security budgets; a managed key service relocates trust rather than removing it. The obstacle is architectural, not cryptographic. We present Quantum Cloud Guard (QCG), a software-only three-layer architecture. No prior SME-oriented system combines its three elements: client-side hybrid post-quantum encryption, self-hosted key custody with client-verifiable ML-DSA-87 signatures on served keys, and an integrated application-layer abuse-prevention gateway. Files never leave the client: each is sealed under AES-256-GCM, its key wrapped to an ML-KEM-1024 public key from the enterprise’s key service. The enterprise alone administers it; it signs every key with ML-DSA-87, so a client that pinned it detects substitution. Separating key custody from data custody is the point: a provider holding both can read the data. On a 24 MHz STM32F407, ML-KEM-1024 key generation takes 40.8 ms and decapsulation 44.0 ms; on the server every post-quantum operation stays sub-millisecond, signing adding 0.24 ms per request. The service runs on a 4.49 EUR/month virtual server. Under sustained flooding, the in-process gateway Sentinel Gate rejected 98.8% of attack traffic while a legitimate client’s median latency moved from 621 to 625 ms. Being single-source, this shows filtering effectiveness, not DDoS resilience.

We present a neural network-based pipeline for efficiently generating fast matrix multiplication (FMM) algorithms of small but arbitrary dimensions $(n,m,k)$. Our neural network is general and tunable to output FMM schemes with specific properties, and in this paper we specifically target aspects that are useful and important in practical implementation, such as ternarity (coefficients in $\{-1, 0, 1\}$), sparseness and a low number of additions after optimization (addition reduction carried out separately). We generate and optimize thousands of FMM algorithms and show that our generation method is beneficial in terms of performance across the entire FMM pipeline (both the FMM generation itself and optimization of additions). We discuss performance metrics and utilize heatmaps to visualize and understand this performance. We achieve record-low arithmetic (additive) complexity for various combinations of dimensions. For $(n,m,k) = (2,2,k)$, our method performs particularly well. Our improvement compared to previous results increases with $k$. We show that the (addition) optimization process can behave very differently depending on the dimensions considered, indicating how further improvements (beyond our results) can be targeted. In particular, in the $(n,m,k) = (2,2,k)$ setting, we show evidence of structural FMM properties coming into play, concretely showing that FMM generation with a minimal number of additions is sometimes suboptimal with respect to the entire FMM pipeline. Finally, we make our neural network implementation, our generated FMM schemes, heatmap utilities and datasets publicly available.

We present the Pilot--Sailor Framework, an LLM-guided system for studying theoretical open problems in symmetric cryptography. Pilot proposes intermediate statements and proof plans. Sailor attempts formal proofs, and the proof assistant admits only checked declarations to the verified context. We apply this methodology to Boolean-function theory and symmetric cryptanalysis through fourteen mathematical case studies, comprising complete resolutions, corrected formulations, counterexamples, and scoped quantitative advances. In particular, we prove the original pointwise Tu--Deng conjecture for all word lengths and admissible residues. We further characterize equality in this bound: if \(t\) has \(z\) zero bits, equality holds exactly when every cyclic gap between consecutive zeros is at least \(z\). This criterion also gives a closed formula for the number of equality cases for each \(z\). We also prove that, for \(n=2k\geq6\) and \(k<m<2k\), every mapping \(F:\mathbb F_2^n\to\mathbb F_2^m\) satisfies \(\operatorname{NL}(F)\leq2^{n-1}-2^{n/2-1}-2\). This improves both the covering-radius estimate and the bound obtained from Nyberg's obstruction and integrality. Using an exact computer-assisted spectral classification, we also prove that the maximum nonlinearity of a balanced Boolean function in eight variables is 116, resolving whether the value 118 can occur. Beyond the well-known long-standing problems highlighted above, we also establish new results for ten further research questions in symmetric cryptography.

The main message of this paper is that several seemingly different circular-style primitives are existentially equivalent. In particular, somewhat surprisingly, we show that hinting PRGs (Koppula and Waters, CRYPTO 2019) are equivalent to secret-key encryption (SKE) schemes satisfying key-dependent-message (KDM) security. As a conceptual centerpiece, we introduce key-dependent-shift (KDS) security for weak pseudorandom functions (PRFs), and show that they serve as a convenient hub connecting these primitives. We also show that KDS secure weak PRFs imply other cryptographic primitives with circular-style security, such as linear-resistant PRGs (Hajiabadi et al., ITC 2023) and hinting weak PRFs (Alamati and Patranabis, ASIACRYPT 2022), all of which are thus existentially equivalent to KDM secure SKE and hinting PRGs as well. Hence, KDS secure weak PRFs can be thought of as a unifying umbrella for circular-secure cryptographic primitives. As another application of our new notion, we show that KDS security enables new constructions of public-key encryption (PKE) satisfying randomness-dependent-message (RDM) security and correlated-product secure trapdoor functions (TDFs). Our key technical contribution is a generic construction of KDS secure weak PRFs from any KDM secure SKE.

Authenticated data structures are widely used to compute compact digests of evolving collections of elements and to support efficient verification of element inclusion. However, the authenticated collection often should not grow forever: older elements may expire and no longer require verification. Many implemented append-only approaches, for example used in Certificate Transparency (CT), do not directly support this setting, since previously accumulated elements remain part of the authenticated state indefinitely. In this work, we introduce a pruning accumulator, a stateful accumulator that supports both incremental addition of new elements and pruning of an old prefix of previously accumulated elements. The resulting digest represents the unpruned sequence, while pruned elements are removed from the authenticated state. Unpruned elements continue to support proof-of-inclusion verification, proof updates, update verification, and consistency checks. This captures applications that require authenticated, incrementally maintained state over a moving window of elements. We present two constructions of Merkle-tree-based pruning accumulators, both with efficient accumulation, prefix pruning, proof generation, proof updating, and verification. The constructions preserve the standard Merkle-tree style of verification for active elements while reducing long-term storage requirements. We provide formal definitions, correctness and security analysis, an open-source implementation, and experimental evaluation demonstrating the performance benefits of pruning.

BitVM2 brought arbitrary program execution to Bitcoin, yielding the first light-client-based bridge to its second layers and reducing the trust required at setup to a single honest participant. Its successors, BitVM3 and BABE, move the disputed computation off-chain into Garbled Circuits (GCs), cutting worst-case on-chain dispute costs by roughly three orders of magnitude and so opening participation beyond well-capitalized operators; BABE in turn cuts the off-chain storage and setup costs of BitVM3's garbled circuits by a comparable factor. What still reaches the chain, however, is bulkier than it need be. BitVM2 commits its data with compact Winternitz one-time signatures (WOTS), whereas BitVM3 and BABE must reveal GC input labels on-chain and so fall back on far bulkier Lamport signatures, which play two roles at once: GC input labels and Bitcoin-verifiable commitments. WOTS cannot simply be substituted, because its hash chains are monotonic---an evaluator holding one state's preimage can hash forward and obtain several active labels on a single input wire, destroying the circuit's privacy. Recovering BitVM2's compactness therefore calls for a practical GC whose input labels are WOTS signatures---a construction that has remained out of reach. We close this gap with a non-interactive \emph{WOTS-to-Lamport translation gadget}: the garbler commits on-chain using compact WOTS chains, and the evaluator expands them off-chain into exactly the orthogonal Lamport labels the GC consumes, learning nothing about the mutually exclusive ones. A naive translation table that enumerated messages would be exponentially large. Two symmetries bring it down to quadratic: reconstruction from a Shamir sharing depends only on \emph{how many} shares are held and not on \emph{which}, which collapses the exponentially many messages onto the single checksum weight WOTS already computes; and monotonicity, the very property that made WOTS unusable, orders an evaluator's access by inclusion. We model the gadget as a garbling scheme and prove it adaptively private. Applied to BABE, it restores WOTS-scale commitments to a GC-based protocol, cutting total on-chain script size by more than $3\times$ and bringing dispute transactions within Bitcoin's standardness limit.

We construct the first multi-key fully homomorphic encryption (MKFHE) scheme where the ciphertext size, public key size, and secret key size remain independent of the number of users, $N$. Our construction is leveled and relies on the standard Learning with Errors (LWE) assumption. All prior MKFHE schemes incur at least linear growth in ciphertext size with the number of users ($|\mathsf{ct}| \propto N$), a limitation that has persisted across more than a decade of research. Our results provide the first evidence that MKFHE with constant ciphertext size is achievable under standard assumptions and paves the way for many interesting applications. We also describe a single-round distributed decryption protocol for multi-key ciphertexts in our fully-succinct MKFHE scheme. More remarkably, we show that our MKFHE scheme simultaneously satisfies the following properties: (1) the size of each user's partial decryption share is identically equal to the plaintext length (i.e., partial decryption shares are truly rate-1), and (2) an honest user's partial decryption can be simulated. To the best of our knowledge prior to this work, we did not have any MKFHE with one-round distributed decryption from standard assumptions that simultaneously satisfied both these properties. We show that our MKFHE is significantly useful in designing various forms of multi-party computation (MPC) protocols with asymptotically optimal communication complexity.

ML-KEM is IND-CCA2 secure only because of one check inside decapsulation: the receiver re-encrypts the message it recovered and returns the true shared secret only if the result matches the received ciphertext exactly. This is the Fujisaki–Okamoto (FO) check. wolfSSL implemented it in hand-written SIMD assembly, and on two backends it compared fewer than all of the ciphertext bytes. The x86-64 AVX2 path compared 1536 of 1568 bytes; the ARM64 NEON path compared roughly half. These bugs were documented as a weakening of IND-CCA2 security, in that a tampered ciphertext can slip past the check. We show they are worse than that. The bytes the check skips carry the tail of the decryption noise, and that noise is an exact linear function of the secret key. An attacker who varies those unchecked bytes and watches the decapsulation output reads the noise off one coordinate at a time. Stacking the measurements gives an overdetermined linear system in the secret, which we solve by ordinary least squares with no lattice reduction. The measurement is a plaintext-checking oracle, the same primitive that key-mismatch attacks use. What is new is where it comes from. Reading it off the unchecked v-tail, rather than from chosen sparse-u ciphertexts, means it survives even when u is fully validated, as on AVX2, so the standard "validate all of u" hardening does not close it. The price is queries, 10⁵ to 10⁶ against a few thousand for key-mismatch, so the contribution is reach rather than efficiency. We recover most of the ML-KEM-1024 private key end-to-end against the shipped binaries on both backends: 98.0% of the 2048 secret coefficients at 400 ciphertexts on AVX2, and 98.5% at 600 on NEON, reaching the full key with more ciphertexts (the verified reference model recovers all 2048 at about 1300 ciphertexts). The cost appears to track the geometry of which bytes go unchecked more than their number: NEON leaves about 2.5× more coordinates unchecked than AVX2 yet needs more ciphertexts. We conclude that an incomplete FO comparison is a key-recovery vulnerability, and should be triaged as one.

Key transparency enables a centralized encrypted messaging provider to publicly commit to the public keys it distributes, allowing clients to detect potentially malicious keys. Recent deployments by WhatsApp and iMessage demonstrate the promise of this approach, but they rely on third-party global auditors to detect misbehavior by the key server. No existing system supports auditing efficiently enough to be done by lightweight end users while also providing scalability to billions of users and short epoch latency. We present $\mathsf{Aegon}$, a key transparency scheme designed for global-scale encrypted messaging. Building on ideas from $\mathsf{IronDict}$, $\mathsf{Aegon}$ avoids per-epoch work that scales with the full dictionary size: its server computation depends only on the number of updates in the current epoch, eliminating global invariance proofs and enabling epoch latency of under a minute ($500\times$ reduction compared to $\mathsf{IronDict}$). $\mathsf{Aegon}$ further introduces a sharded dictionary design that reduces global parameters to shard-dependent sizes and enables horizontal scaling. To control long-term storage, $\mathsf{Aegon}$ uses proof caching to safely discard historical dictionary snapshots, so storage grows only with retained history. We provide a production-grade Rust implementation of $\mathsf{Aegon}$ and demonstrate practical scalability to a dictionary with $4$ billion entries, comparing it against the public codebase of WhatsApp Key Transparency ($\mathsf{AKD}$). At the throughput of $1{,}250$ updates per second, $\mathsf{Aegon}$ produces constant-size auditor proofs of under $30$ KB, verifiable in under $65$ ms and independent of the number of updates per epoch or of the directory fill. At a fully-populated $2^{32}$-entry directory, this is roughly an $80{,}000\times$ reduction in audit proof size and a $370\times$ reduction in verify time relative to $\mathsf{AKD}$. All other server and client operations remain highly efficient and comparable to $\mathsf{AKD}$, while $\mathsf{Aegon}$ achieves stronger privacy guarantees.

Nonlinear feedback shift registers (NFSRs) are fundamental building blocks for modern stream-cipher constructions. An $n$-stage NFSR $f$ is classified as irreducible when the output sequence set of $f$ does not contain the output family of any NFSR of order less than $n$. Existing research has established upper and lower bounds for the density of irreducible NFSRs, confining this value within the range of 0.4461 to 0.4834. This study tightens these bounding intervals with high accuracy, reducing the original 0.04 gap down to only $8\times10^{-6}$.

Multi-round public-coin proof systems have progressed rapidly, yet their simulators and extractors are rarely used as building blocks in other protocols, unlike those of 3-move $\Sigma$-protocols. Prior work [Abe et al., Eurocrypt~'26] addressed the simulator side with critical-round zero-knowledge. In this paper, we address the extractor side and introduce critical-round special soundness (CRSS): a witness is extractable from a small critical subtree of transcripts that branches only from one round, while the full tree of transcripts serves only as a fall-back that outputs a solution to a hardness assumption. We first establish an extract-or-extend theorem that bounds the failure probability of the critical extractor even when the critical-round challenges are chosen by the adversary, and then show that KKW-style MPC-in-the-head proofs, KZG-compiled polynomial IOPs including Plonk, and Protogalaxy satisfy CRSS. We also give a corresponding tree-extraction result for the sumcheck sub-protocol of Spartan. We present three applications: a hash-based witness sharing scheme that verifiably secret-shares an NP witness without interaction among recipients, the first offline trapdoor-extractable trapdoor commitment from a multi-round proof, where a trapdoor is extracted immediately upon a double opening, and a parameter improvement for the multi-round Fischlin transform [Rotem-Tessaro, Crypto~'25] that reduces the prover's complexity in practice.

Since the seminal work of Carlini et al. at CRYPTO 2020, cryptanalytic model extraction has shown neural-networks parameters can be recovered from black-box queries. Existing attacks are largely built around piecewise-linear phenomena. Softmax attention, as the key component of the transformer architecture, presents a different extraction landscape: its nonlinearity is smooth and sequence-dependent, which renders the existing piecewise-linear-based method inapplicable. Recent work has investigated the learnability of a single-head attention model, while in the multi-head case, the parameters of the multi-head attention layer cannot be uniquely identified from value queries alone. In this paper, we propose the first attack against multi-head attention models. We formalize the extractable representative of multi-head attention and give a polynomial-time algorithm for extracting the parameters of the canonical representative model. We also test our algorithm end to end under finite precision, and successfully extract the parameters of a softmax attention model with token dimension 8 and 6 heads to accuracy $2^{-51}$. Moreover, we overcome the limitation that existing parameter extraction algorithms for one-layer single-head Transformers fail when the ReLU feedforward networks (FFNs) include bias terms. The effectiveness of our approach is demonstrated through model extraction attacks in finite-precision experiments. These results show that softmax normalization itself exposes exploitable algebraic structure, extending cryptanalytic extraction beyond ReLU-centric techniques.

Secure group messaging protocols, now standardized by the IETF as Messaging Layer Security (MLS), provide end-to-end encryption for billions of users. The cryptographic core of these protocols is continuous group key agreement (CGKA), a primitive designed to maintain a shared secret among a dynamic group while providing security guarantees like forward secrecy and post-compromise security. A critical challenge for CGKA is achieving efficiency, particularly sublinear complexity (in the size of the group), for group operations. While practical tree-based protocols like TreeKEM offer logarithmic complexity in ideal (so-called "fair-weather") scenarios, their performance degrades to linear in the worst-case, and even realistic average-case, scenarios. This performance collapse raises the fundamental question of whether any CGKA protocol can achieve provably sublinear worst-case complexity. Prior work has established significant barriers to this goal, including black-box impossibility results ruling out efficient constructions from standard public-key encryption. Theoretical solutions circumvent these barriers using powerful tools like indistinguishability obfuscation ($i\mathcal{O}$), but these constructions are astronomically inefficient and often provide weaker security guarantees, such as lacking forward secrecy. This leaves a wide gap between practical protocols with poor worst-case guarantees and theoretical solutions that are entirely impractical. In this paper, we narrow this gap by presenting the first CGKA protocol that achieves provably logarithmic worst-case complexity for both computation and communication. Our first construction is based on a falsifiable and plausibly post-quantum assumption called decomposed learning with errors (decomposed LWE), and achieves basic CGKA security (only group members know the key) and post-compromise security, but not forward secrecy. We then show how to extend our scheme in the random oracle model to achieve optimal security (including forward secrecy) while retaining worst-case sublinear communication. However, the forward-secure refresh operation takes linear time in the group size, while still producing compact ciphertexts. Our work is the first to establish that worst-case efficient CGKA is theoretically possible from simple falsifiable assumptions. Moreover, it offers a plausible roadmap towards concretely efficient constructions.

Secure key leasing (SKL) is a quantum cryptographic primitive that enables the leasing of decryption keys to delegated users with the guarantee that, once revoked, the lessees irreversibly lose decryption capability. A key feature that makes SKL practically relevant is classical revocation: the ability to revoke keys at any time and from anywhere, without relying on a quantum channel. In this work, we revisit SKL schemes for public-key encryption (PKE) and identity-based encryption (IBE), and present a new approach for concrete efficiency under the standard Learning With Errors (LWE) assumption. First, we refine the security analysis of the Dual-Regev SKL-PKE scheme with classical revocation from [Ananth, Poremba, and Vaikuntanathan, TCC 2023; Ananth, Hu, and Huang, TCC 2024], establishing security under the polynomial hardness of LWE with polynomial modulus. Together with the resource efficiency of the Dual-Regev-based construction, our analysis shows that this approach yields the most quantum-efficient known SKL-PKE scheme. Second, we present a simple and efficient construction of selectively secure SKL-IBE with classical revocation from standard LWE. Our approach directly extends the Dual-Regev SKL-PKE within the IBE framework of [Agrawal, Boneh, and Boyen, Eurocrypt 2010], avoiding garbled circuits and obfuscation-based assumptions and achieving improved concrete efficiency over prior generic approaches.

Multi-party computation (MPC) enables multiple parties to jointly process sensitive data without revealing their inputs. However, existing MPC protocols remain inefficient for high-dimensional sparse data. In plaintext, sparse linear algebra algorithms address this problem using two fundamental primitives, Scatter and Gather. We propose SparseMPC, an outsourced MPC protocol that securely implements Scatter and Gather and uses them to perform sparse matrix multiplication. Our protocol supports an arbitrary number of data owners and provides a low memory footprint, constant round complexity, and low communication cost. Beyond sparse matrix multiplication, SparseMPC provides a foundation for efficiently realizing a broader class of sparse computations in outsourced MPC.

Autonomous agents are increasingly used to plan and execute paid workflows on behalf of users. Existing agentic-payment frameworks support this delegation through merchant-admission authorization credentials but require the user to specify merchants before execution. However, complex paid workflows often span multiple services and merchants, and agents may choose among them based on intermediate results. This creates two limitations: (1) requiring the user to choose each merchant in advance either limits the agent's adaptability or forces the user back into the loop; and (2) reusing a stable identifier across merchants lets observers link separate paid calls and infer the user's broader intent. To address these limitations, we introduce MinMandate, which grants adaptive merchant selection within user-approved task bounds and derives fresh per-call payment views without introducing a stable cross-merchant identifier. Extensive experiments on AgentDojo tasks demonstrate that, when 50% of merchants are unavailable, MinMandate improves task success by 32.7 percentage points on average across four tested planners compared with an AP2 baseline that preauthorizes one merchant per service class. Reintroducing a reusable public payment-layer handle in the Stable Handle ablation raises attacker task-recovery success by 27.4 percentage points on average, isolating the privacy cost of a stable join handle. The code is available at https://github.com/Zora-G/minmandate.

Certified deletion enables a party to prove that it has erased the sensitive information contained in a quantum state. Bartusek and Raizes (CRYPTO 2024) gave the first secret-sharing scheme with privately verifiable deletion. Subsequently, Katz and Sela (EUROCRYPT 2025) constructed secret-sharing schemes with publicly verifiable deletion under computational assumptions. Constructing such a publicly verifiable scheme without cryptographic assumptions remains open. In this work, we introduce an intermediate notion called unanimously verifiable deletion. While private verification relies on the dealer and public verification allows any third party to verify deletion, unanimous verification assigns the verification responsibility to the parties in the secret-sharing scheme themselves. We construct an information-theoretically secure linearly homomorphic threshold secret-sharing batch scheme with adaptive unanimously verifiable deletion. In particular, to obtain its linear-homomorphic property, we exploit a linearly homomorphic structure of BB84-type states that enables linear transformations on encoded values while preserving certified deletion. More generally, this structure can be used to upgrade certain primitives with certified deletion to their linearly homomorphic counterparts. As another major contribution, we demonstrate an application of this batch scheme by constructing outsourced multi-party computation (MPC) protocols for arbitrary arithmetic circuits. Our outsourced MPC has semi-honest classical clients and malicious quantum servers, achieves adaptive unanimously verifiable deletion security in the trusted-preprocessing and security-with-abort setting against a rushing adversary, and supports public output reconstruction. The adversary may adaptively corrupt up to $n-1$ clients. For the servers, during the online execution, at most $t$ corrupted servers may remain undeleted and at least $t+1$ honest servers must remain undeleted, for any $t<n/2$. After successful finalization, all servers may be corrupted without revealing additional information about the remaining clients' inputs beyond the public output and the corrupted clients' inputs.

Large-state ARX-based S-boxes have become a key component of modern lightweight cryptographic designs, yet deriving tight security bounds for their differential and linear properties remains challenging. In this paper, we study the security of Alzette, the 64-bit ARX-based S-box used in the SPARKLE permutation, and present a general framework for the analysis and design of large-state ARX S-boxes. We introduce SMCS, a hybrid search strategy that combines MILP-based optimization with SMT-based model checking, enabling the computation of tight bounds on maximum expected differential probabilities and linear correlations. Using SMCS, we refine existing bounds for Alzette and, for the first time, establish tight linear bounds (resp. differential bounds) for up to 15 rounds (resp. 14 rounds). Building on these results, we propose S-box configurational encoding, an automated design method for ARX-based S-boxes, and introduce a new family of S-boxes called AFS (ARX-Feistel Structure) with 32-bit and 64-bit instances. We show that selected AFS instances achieve strictly better resistance to single-trail differential and linear cryptanalysis than SPECKEY and Alzette, respectively, while preserving comparable hardware and software costs. Finally, we present the first bit-based SMT model for optimal long-trail decomposition and apply it to derive more accurate bounds for SPARX-128 and SPARKLE. Our results show that replacing the S-boxes with AFS instances yields substantial improvements in cryptanalytic security margins.

Noise flooding is a standard defense against decryption attacks on approximate homomorphic encryption, but its security proof is unusually sensitive to composition. Replacing each of \(q\) adaptive decryption answers with a statistically close simulation and applying an ordinary hybrid argument loses linearly in \(q\). The cryptographic proof instead accumulates conditional Kullback-Leibler (KL) costs and converts to statistical distance once, giving the parameter-critical square-root loss. We machine-check this argument using Rocq and SSProve. Given any fully homomorphic encryption scheme that is approximately correct and IND-CPA secure, we formalize a reduction for every \(q\)-query IND-CPAD adversary and prove \[ \Pr[\mathsf{IND\text{-}CPAD}_{\mathsf{NF}}^{\mathcal A}=1] \leq \beta_{\mathsf{CPA}}(\mathcal B_{\mathcal A,q}) + \frac{\sqrt{qn}}{2\gamma}. \] where \(n\) is the plaintext dimension and \(\gamma\) is the flooding-width multiplier. Our proof constructs a new relational program logic over SSProve semantics. Its Pythagorean judgment composes conditional KL budgets without converting them to statistical distance, and a verified trace compiler lifts a local oracle rule to arbitrary adaptive programs with a single final conversion.

Threshold signatures reduce the risk of single-key compromise by distributing signing authority, but each key share remains exposed to compromise of the software and infrastructure that execute the protocol. We present RSS, a threshold signing service that runs share generation and signing inside Trusted Execution Environments (TEEs). We integrate GG20 threshold ECDSA, FROST, and threshold BLS into the EnGINE experimentation framework and evaluate local and Google Cloud deployments using AMD SEV-SNP and Intel TDX. Our experiments separate distributed key generation (DKG), preprocessing, and online signing, and cover up to 40 logical protocol participants distributed across four physical hosts or confidential VMs (CVMs). In matched-platform comparisons, confidential execution adds limited overhead relative to protocol and deployment effects. DKG is the main scaling bottleneck: for 40 participants, it completes within seconds in the evaluated configurations, whereas signing completes in tens of milliseconds. Threshold BLS is approximately twice as slow as FROST for comparable values of $n$ and $t$. These results establish the performance feasibility of executing threshold-signature workloads inside CVMs under benign-operation assumptions. The evaluation does not cover a complete attestation-bound provisioning lifecycle, persistent-state rollback protection, or Byzantine fault behavior.

We introduce information-theoretically private quantum protocols for two-party Hamming distance when both parties must output the same estimate. Classically, for input length $n$, information-theoretic protocols require $\Omega(\sqrt{n})$ error under pure differential privacy and $\Omega(\sqrt{n}/\log n)$ error under strong approximate differential privacy, whereas computational security permits $O(1)$ error. In Klauck's honest, nonpreemptive, message-preserving model, we give an $O(n)$-communication quantum protocol with pure $\varepsilon$ quantum differential privacy (QDP) and expected error at most $\frac{2}{\sinh \varepsilon}+\gamma,$ for every $\gamma>0$. For approximate $(\varepsilon, \delta)$ QDP, an exact finite-cycle hockey-stick calculation yields strictly smaller error, while preserving the $O(1)$-versus-$\Omega(\sqrt{n}/\log n)$ separation for $\delta=o(1/n)$. Thus, quantum communication achieves $O(1)$ information-theoretic error, matching the accuracy available classically only under computational assumptions. The main construction uses a guarded coherent round trip and an equal-Gram rigidity principle that prevents an honest player from retaining input-dependent complementary information. We also separate this model from weaker prescribed-channel privacy, which already admits an exact classical realization, and from fully retention-robust security, against which measurement-and-abort attacks remain possible. Therefore, we identify preservation of non-orthogonal quantum messages as a resource for privacy, but leave open whether a separation exists in the malicious setting.

We give a two-transcript key-recovery attack on TALUS-MPC in TALUS v4. TALUS was presented in the second round of the NIST Threshold Call Preview Talks. In Algorithm 3 of TALUS v4, the committee's nonce polynomials are evaluated at all $N$ points so that any $T$ parties can sign. An adversary controlling the coordinator and $T-1$ parties can reuse the same pooled nonce with two quorums whose only common members are corrupt. Each participating honest party uses its signing share once, yet the coordinator obtains $\mathbf{z}_0=\mathbf{y}+c_0\mathbf{s}_1$, $\mathbf{z}_1=\mathbf{y}+c_1\mathbf{s}_1$. The nonce cancels on subtraction. Moreover, no invertibility assumption in $R_q$ is needed: the response equations lift to $\mathbb{Z}[X]/(X^{256}+1)$, and every nonzero $c_0-c_1$ is invertible in the cyclotomic field $\mathbb{Q}[X]/(X^{256}+1)$. Thus two distinct challenges recover $\mathbf{s}_1$ exactly; since the TALUS v4 public key includes the full $\mathbf{t}=\mathbf{A}\mathbf{s}_1+\mathbf{s}_2$, the adversary also recovers $\mathbf{s}_2$ and forges signatures.

A secret-sharing scheme allows a dealer to distribute a secret among $n$ parties such that only predefined “authorized” sets of parties can reconstruct the secret, and all other “unauthorized” sets learn nothing about it. Families of authorized sets are called access structures, and a scheme is called linear if its sharing map is linear in the secret and the dealer’s randomness. We show that every $n$-party access structure can be realized by a linear secret-sharing scheme over every finite field with at most $2^{\lceil n/2\rceil-1}+1$ field elements per share. Taking the field to be $\mathbb{F}_2$ yields the same bound in bits for one-bit secrets. A known counting lower bound for monotone span programs shows that for every fixed finite field, almost all access structures require share size $2^{n/2-o(n)}$ in every linear scheme, which makes our upper bound tight. Our scheme is considerably simpler than previous schemes that obtained share size $2^{cn+o(n)}$ with $1/2\leq c<1$. We also present a variant of this linear construction that is tailored for monotone k-DNF access structures (also known as $k$-upslices). Then, by combining it with existing non-linear schemes, we derive a scheme for all access structures with share size $2^{0.494n+o(n)}$. This improves the previous upper bound of $2^{0.585n+o(n)}$ by Applebaum and Nir (CRYPTO 2021), and establishes a separation between the worst-case non-linear and linear exponents. Additionally, we prove that almost all monotone functions require monotone span programs of size $2^{n/2-o(n)}$ simultaneously over all fields, finite or infinite, improving the previous bound of $2^{n/3-o(n)}$ for this setting. In particular, almost all access structures require information ratio $2^{n/2-o(n)}$ in linear schemes over every finite field, including fields whose size depend on $n$. Some of the constructions and proofs were discovered in conversations prompted by the author with GPT-5.6 Sol and Claude Fable 5.

Blockchain networks rely on transaction fees for resource allocation and spam prevention. Ethereum's gas mechanism and its adoption by Layer-2 rollups serve this dual purpose, but gas-based fee markets produce unintended consequences: ineffective spam deterrence at low fee levels, poor user experience, privacy leakage, and revenue instability for rollup operators. We present an idealized protocol architecture for gasless sequencer admission in Ethereum Layer-2 rollups based on Rate-Limiting Nullifiers (RLN) and a non-transferable reputation token (Karma). Users transact within a per-epoch gasless quota. Transactions beyond that quota use a gas-paid overflow path. RLN enforces the quota via zero-knowledge membership proofs, preserving pseudonymity for users within quota against on-chain observers while exposing violators through reputation slashing. We present the architecture and transaction flow, analyze spam-attack economics through a parameterized cost comparison on a flat per-identity quota model (labeled flat-$N$, an analysis model for the spam stress test), and describe Status Network (SN), a deployed Ethereum L2 that implements this design.

We give deterministic exact recovery for almost all square four-tensors over every finite field. For every \(n \ge 2^{24}\) and prime power \(q \ge 2\), an explicit \(\mathrm{GL}_n(\mathbb{F}_q)^4\)-invariant family contains a \(1-O((\log n)^2/n)\) fraction of all \(q^{n^4}\) coefficient arrays, with an explicit failure bound uniform in \(q\). Membership and isomorphism decision and recovery against every target are deterministic in \(\operatorname{poly}(n,\log q)\) bit time, with four invertible factors over the original field. The source distribution is uniform without any conditioning on flattening ranks. The proof combines linked extension-field eigenmatrices, a submodule sieve under the joint law of a matrix and its inverse, and recovery from the kernels of singular original flattenings. Partial traces of matrix products provide a factorization-free algorithm in large characteristic. Complementary results give explicit positive source fractions in smaller dimensions, including a \(1/q+O(q^{-2})\) family with deterministic recovery. The algorithms invert the coefficient-uniform square-tensor group action with the stated success probabilities. A deterministic exhaustive fallback gives total correctness and a polynomial running-time bound with high probability; no polynomial expected running time is claimed.

Given two ordered families of square matrices over a finite field, we seek an ambient conjugation and an invertible mixing of the family that carry one input to the other. The matrices need not be linearly independent. We give deterministic partial algorithms in an explicit finite-field model: source-side recognition certifies completeness against every target, and every returned transporter is verified. For a matrix space with nondegenerate trace pairing, two successive orthogonal projections produce an intrinsic matrix pair. A characteristic-wise nonzero polynomial certificate gives source density at least $1-(6n^2-4)s/q-2/q^3$, where $n\geq 3$ is the matrix size, $2\leq m\leq n^2-2$ is the number of slices, and $s=\min\{m,n^2-m\}$. Thus the density tends to one whenever $n^2s=o(q)$. A complementary one-dimensional-hull construction, together with low-dimensional and endpoint solvers, gives a recognized source family of iid-uniform mass greater than $9/(1216q)$ for every prime power $q$ and all positive $n,m$. Both algorithms have bit complexity polynomial in $n,m,\log q$. An image-and-kernel lift recovers the declared coefficient action, including dependent presentations. We separate the exceptional odd-characteristic two-by-two case and the arithmetic limitations of higher-moment constructions from the universal partial guarantee.

Subspace differential uniformity (SDU) measures the concentration of a differential distribution table (DDT) on affine subspaces. We determine the exact optima of the two axial affine-SDU coordinates in dimension five and establish a strict gap between locally admissible support designs and supports realizable by almost perfect nonlinear (APN) permutations. We first prove that every $16$-subset of $\mathbb{F}_2^5$ meets some affine $3$-flat in at least six points. Equality holds precisely for balanced quadratic indicators of polar rank four, forming a single affine orbit represented by $\operatorname{supp}(\operatorname{Tr}(x^3))$. This gives the relaxed axial optimum $12$. We then classify all $900$ ordered monomial-trace candidates $M_{r,s}(u,v)=\operatorname{Tr}(u^r v^s)$: exactly $100$ attain both relaxed axial optima, yielding $20$ labelled arrays and three product-linear types up to transpose. Despite satisfying regularity and zero-vector-sum constraints, every optimal type violates a global necessary condition for DDT realizability: its two-dimensional character transform contains a negative coefficient where a vectorial Walsh square is required. Finally, the published exhaustive affine classification of five-bit APN permutations, together with direct recomputation of all five class representatives, gives realizable axial minimum $14$, attained simultaneously by the $x^{15}$ class. Thus local incidence and vector-sum constraints permit score $12$, whereas genuine APN-permutation DDT supports require score $14$.

Degree-sum-freedom is a local criterion for division-property propagation from affine input spaces. Immediately after defining this criterion, the published chapter asserts invariance under extended-affine (EA) equivalence. We show that this assertion does not hold beyond ordinary sum-freedom and quantify the resulting variation. First, the natural Gold APN pair $x^3$ and $x^3+x$ has exact proper-flat values 3 and 2 on an infinite sequence of dimensions. We then study a known complete-mapping family of EA-equivalent, differentially 4-uniform permutations $F_b,G_b$ on $2r$ bits. For every odd $r$ and every $1\le c\le\lfloor(r-3)/2\rfloor$, we determine their exact codimension-$c$ profiles: $\mu_c(F_b)=2c$ and $\mu_c(G_b)=r+c-1$, equivalently $\tau_{2r-c}(F_b)=2r-2c$ and $\tau_{2r-c}(G_b)=r-c+1$. Thus the gap is $r-c-1\ge(r+1)/2$ simultaneously over a linear-size range of proper affine codimensions. The mate upper bound follows by specializing known generalized-degree duality with the exact source profile established here. The matching uniform lower bound is family-specific: after an associated-graded reduction, odd codimensions are detected by one classical consecutive Moore determinant, whereas even codimensions require a jointly nonvanishing family of replacement minors. A cyclic carry classification proves that the selected coefficients are complete reduced coefficients. These results concern local affine-input division-property behavior; they do not yield a multiround distinguisher or an attack on a concrete cipher.

The MACsec Key Agreement protocol, defined in IEEE 802.1X, manages and distributes ephemeral Secure Association Keys for Ethernet links protected with MAC security (IEEE 802.1AE). Prior work has shown that baseline MKA may scale poorly on shared medium Ethernet multidrop links and that formal worst-case bounds significantly exceed automotive startup targets, motivating alternative solutions such as In-line Key Agreement. However, in practice, to preserve compatibility, integration effort, and alignment of standardization, automotive systems are more likely to optimize a MACsec/MKA architecture than to completely replace it. This paper presents novel automotive MKA optimizations targeting secure startup times on shared medium networks and evaluates them through detailed network simulations. Unlike previous work focused on baseline MKA or deterministic worst-case analysis, we study the full startup-time distribution of the optimized protocol under realistic startup scenarios. We quantify the effect of the proposed optimizations on Time-To-Key-Agreement and show how the resulting empirical distributions can be translated into conservative simulation-derived practical startup-time bounds suitable for OEM timing budgets. The resulting bounds are intended as simulation-derived engineering bounds under the modeled startup assumptions, complementing formal worst-case analysis with distributional information on typical, tail, and upper-end behavior.

Candidates for post-quantum migration carry additional costs compared to their pre-quantum counterparts, especially for signatures, and they lose attractive properties of schemes such as BLS: homomorphism, and hence direct signature aggregation. We propose a methodology through which a pre-quantum primitive may still be securely used past Q-day (the advent of quantum computers) in settings where forgery of signatures or cryptographic proofs need only be prevented for a bounded lifespan (transient quantum security). The idea is to bind a fresh, ephemeral, ordinary pre-quantum key to a long-term post-quantum identity once per lifespan window, so a forgery under the fresh key is useful only for that window, and to derive the fresh key so that its exposure never leaks the long-term secret. Our main case study is an application to Ethereum consensus, conditional on stated registration, inclusion, and slashing-evidence rules. The construction keeps ordinary BLS aggregation and needs no SNARK prover. Each same-message aggregate is a single 96-byte signature, and each validator publishes 592-688 bytes of reveal data per epoch. Each epoch key is bound to a seed derived from a checkpoint finalized before that epoch, so a committed key is opened under exactly one seed. We reduce unforgeability in the public-tag game to co-CDH' in the ROM and QROM, with explicit probability and resource costs. Transient quantum security requires hardness at the resulting budget; later checkpoint-derived seeds also require the stated public-environment condition. Transient security requires forgery resistance for the whole interval in which an exposed key can affect the chain. Under Ethereum's attestation inclusion rules, that interval is nominally two epochs plus the reveal lead time under prompt processing. Historical slashing and delayed-fork acceptance need additional rules, which we state as preconditions. Published quantum attack costs inform the resource discussion. They do not establish a security lower bound for this construction. We also provide a formal model and security analysis for the construction, and, of independent interest, a new analysis of BLS where the secret key is sampled similarly to the Dodis-Yampolskiy VRF (IACR PKC 2005) and the adversary is given a related group element as leakage.

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.

As a new lattice problem, we introduce $l$-Shortest Independent Vectors Problem ($l$-SIVP for short), where $l$ is a positive integer no greater than the rank of a lattice. In the case where $l=1$, $l$-SIVP means SVP, and in the case where $l$ is the rank of a lattice, $l$-SIVP means SIVP. We estimate upper bounds on the failure probabilities of the reductions from the subset sum problems to the $l$-SIVPs in terms of Ehrhart theory. Especially, in the case of $l=1$, our upper bound is tighter than the previous result given by Coster et al. We give some considerations for dominating terms of our upper bounds of failure probabilities when $l$ is general.

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

Spartan is a SNARK for R1CS that can be instantiated with any multilinear polynomial commitment scheme. We instantiate Spartan over a binary field, using Ligerito as the commitment scheme along with the ring-switching technique of Diamond and Posen; we refer to the instantiation as BinarySpartan. It is transparent, so it requires no trusted setup, and it provides polylogarithmic-sized proofs. Its security rests on a hash function, so it is plausibly post-quantum secure. We apply well-known optimizations to Spartan and sum-check. We implement and evaluate BinarySpartan end to end. On a MacBook Pro M4 Max (using only its 12 performance cores, and without GPU/Metal acceleration), BinarySpartan proves BLAKE3 at 872,000 hashes/second, SHA-256 at 401,000 hashes/second, and Keccak-f at 287,000 permutations/second, including witness generation. All three clear the 200,000 hashes/second rate proposed as sufficient for a post-quantum Ethereum transition, as well as the roughly 37,000–180,000 hashes/second a possible post-quantum Bitcoin transition would require. At comparable security, BinarySpartan is 16.3–37.8× faster than Plonky3, 6.3–15.7× faster than Binius64, and 4.0× faster than Hashcaster, which only supports Keccak. On all three hash functions, BinarySpartan’s peak throughput matches or exceeds that of Flock, the prior state-of-the-art system. On BLAKE3 and Keccak, BinarySpartan also reaches those rates on far less memory: Flock needs 1.9× and 5.3× more to reach its own best rates. We also evaluate BinarySpartan on the Ethereum Foundation’s client-side proving benchmark, where it proves a single SHA-256 of a 2 KiB message in 6.2 ms, the fastest in the suite and 4.2× faster than Flock.

We prove two deterministic inapproximability results. First, for every fixed $0<\epsilon<1/2$, Euclidean $\mathrm{GapCVP}^{(2)}$ is NP-hard with gap factor $n^{1/2-\epsilon}$ under deterministic polynomial-time many-one reductions, where $n$ denotes the lattice rank. Consequently, the Euclidean closest vector problem is NP-hard to approximate within the same factor. This improves the previous $n^{1/400}$ hardness factor in Chapter 7 of the OpenAI report [Ope26]. Aharonov and Regev gave short certificates for both the YES and the NO case of $\operatorname{GapCVP}^{(2)}$ at gap factor $C\sqrt n$, placing that problem in $\mathrm{NP}\cap\mathrm{coNP}$ for an absolute constant $C>0$ [AR05]. An NP-hard problem lying in $\mathrm{coNP}$ would give $\mathrm{NP}=\mathrm{coNP}$, so the factor $n^{1/2-\epsilon}$ above cannot be improved to $C\sqrt n$ unless the two classes coincide. Second, for every fixed $0<\epsilon<1$, the gap versions of binary nearest codeword and binary syndrome decoding are NP-hard with factor $n^{1-\epsilon}$ under deterministic polynomial-time many-one reductions, where $n$ denotes the binary block length. Consequently, both optimization problems are NP-hard to approximate within the same factor. This improves the previous $n^{1/200}$ hardness factor in Chapter 7 of the OpenAI report [Ope26].

Symbolic protocol verifiers must make a difficult tradeoff: their models and counterexamples should be accessible to protocol designers, but their results must still have a precise meaning. Verifpal addresses the first goal with a compact modeling language and source-level attack explanations. Its original analysis engine, introduced in 2019, had only a preliminary account of its guarantees. This paper presents and evaluates the replacement engine. The engine searches backward from a violated security query to candidate attacker actions. It then runs every session and peer configuration of the protocol together as one execution under those actions, in which each injected value must be derivable from what that same execution has already disclosed, and evaluates the query on that execution. We specify this process from the term algebra and primitive registry through knowledge deduction, bounded sessions, peer configurations, execution, and counterexample presentation. We also give a single-history reference semantics, prove that every execution the engine judges is a history of that semantics, prove termination under the engine's search bounds, and state exactly what each result category establishes. Our evaluation combines targeted regression models, mutation analysis, corpus measurements, and comparisons with ProVerif, Tamarin, and Scyther. It shows that the engine can express and find attacks that require several sessions, different peer assignments, or staged compromise, while exposing the implementation choices that limit its search. The result is an auditable account of Verifpal as a bounded counterexample finder: every reported attack is an explicit protocol execution, but a passing query is not an unbounded proof, and no report is a machine-checked certificate.

The deployment of advanced cryptographic protocols such as zero-knowledge proofs (ZKPs) requires symmetric primitives optimized for fast verification inside proof systems. In frameworks based on Rank-1 Constraint Systems (R1CS), prover performance and proof size are dominated by the cost of arithmetization, specifically, by the number of nonlinear multiplication constraints. Traditional bit-oriented designs are typically inefficient under this metric. In this paper, we introduce Lumora, a family of arithmetization-oriented, permutation-based wide-block ciphers designed for efficient use inside zkSNARK circuits and for applications in post-quantum digital signatures. Each instance of Lumora follows a unified AES-like SPN structure defined over the binary extension field $\mathbb{F}_{2^n}$ for $n \in \{16,32,64\}$. The underlying permutation is instantiated as a block cipher via the Even-Mansour paradigm, which eliminates the R1CS constraint overhead of a separate key schedule, ensuring the prover's workload remains strictly focused on evaluating the public permutation. Finally, we provide a detailed security analysis of the Lumora family, together with implementation results and a comparison within the FAEST-EM-256 framework.

Video conferencing software, including Zoom, Microsoft Teams, and Cisco Webex, use human-driven key verification ceremonies to protect end-to-end encrypted meetings against a potentially malicious service provider. The client software shows each participant a code that they must compare; if the codes match, the call is considered secure. Prior security analyses assumed authenticated out-of-band channels for the comparison, but this is generally unrealistic. The codes are short-lived, so the ``in-band'' channel being verified is, itself, the most natural one to use. We seek to understand the implications of this common practice, asking whether it can be secure and under what conditions. To this end, we formalize the notion of a Human-to-Human Group Key Agreement protocol, modeling an authenticated group key exchange between people, rather than their cryptographic keys. We identify that the security of these protocols relies on the pre-existing capacity of people to consistently recognize one another, avoiding any global identification scheme or trusted external infrastructure. We present a construction, prove it secure in our model, derive concrete bounds, and discuss non-examples demonstrating the definition's subtlety. Our results highlight the approach's usability issues and reliance on unforgeability of human-authenticated video streams---an assumption additionally challenged by recent advances in deepfakes.

Private information retrieval (PIR) is a fundamental cryptographic primitive that allows a client to retrieve an entry of a database from a server without revealing which entry was retrieved. PIR security is traditionally defined with a distinguishing game that ensures the clients' access patterns are kept private from a semi-honest server. Verifiable PIR (VPIR) adds another game-based property that holds against a malicious server: the server is bound to a particular database and cannot cause a client to retrieve a database entry that is inconsistent with this database. Recent work by Alon and Beimel [ITC 2025] deviated from the traditional game-based PIR definitions and contributed a definition of standalone simulation-based security for multi-server PIR. Their techniques, however, do not readily extend to single-server VPIR and do not consider concurrent protocol composition when PIR is used as a building block within a larger application. In this work, we further the study of simulation-based VPIR security. We are the first to formalize a universally composable (UC) definition of VPIR in the single-server setting by giving an ideal VPIR functionality. We motivate the need for UC security by showing how game-based VPIR properties fail under sequential and concurrent protocol composition. We also demonstrate the generality of our UC VPIR functionality by providing two realizations based on a trivial PIR and VeriSimplePIR [de Castro and Lee, USENIX Security 2024]. Additionally, we introduce a new kind of VPIR, called Updatable VPIR (UVPIR), which guarantees to clients that (1) database updates are authorized by permissioned clients and (2) responses to their queries are consistent with a specific version of the PIR database. We show that UVPIR can be constructed in a black-box manner on top of any VPIR protocol.

Multivariate signature schemes are among the few post-quantum candidates capable of providing very short signatures, but designing secure constructions has proven challenging. HFE-based schemes such as G$e$MSS were compromised by algebraic MinRank attacks. This motivates the HFE$_\text{IP}^-$ framework, which combines IP and minus modifiers to address these attacks. We introduce James and D-James, the latter achieving signatures of only 156 bits at the 128-bit classical security level and 348 bits at the 256-bit classical security level, among the shortest signatures reported for practical post-quantum public-key signature schemes, with estimated signing and verification costs comparable to those of G$e$MSS. The main technical contribution is the introduction of Dragon terms, which decouple the number of public equations from the hash output length, allowing the signature size to be reduced independently of the security parameter. We characterize the algebraic structure introduced by Dragon terms and show that it does not enable known MinRank attacks when combined with the HFE$_\text{IP}^-$ countermeasures. We also show experimentally that the known differential attack does not appear to extend to the minus variant. We further present parameter sets over both binary and small non-binary finite fields. For small values of $q>2$, the public-key size decreases by a factor of about 3 to 5 for $q\in\{4,5\}$, and by up to a factor of 10 for larger $q$, at the cost of slightly longer signatures and slower signing.

An anonymous credential allows a user to prove that she is authorized in an anonymous and unlinkable fashion. A rate-limited token is an anonymous credential that can only be used a limited number of times in any particular context; this means that even though we do not know which users are gaining access to a resource, there is a limit to how many resources one user may consume. Such tokens are becoming an increasingly attractive way to balance privacy with authorized access. Although a general architecture for how to obtain rate-limited tokens from digital signatures, pseudorandom functions (PRFs), and non-interactive zero-knowledge proofs (NIZKs) has been known for over twenty years, efficiently instantiating it with post-quantum-secure signatures and proofs has, until now, remained an open problem. In this work, we present the first lattice-based construction of rate-limited tokens and tackle the practical challenges associated with using lattice-based building blocks in this setting. A central difficulty lies in the absence of lattice-based PRFs that support efficient NIZK proofs of correct evaluation. We show that, in the random oracle model, a weak PRF—where adversaries are restricted to querying random inputs—suffices. We further present a weak PRF construction that both admits efficient NIZK proofs and remains secure—even when adversaries have partial control over the randomness—and extend this guarantee more generally to key-homomorphic PRFs. Another contribution, which is of independent interest, is the first lattice-based construction of partially binding commitments, a primitive introduced by Goel et al. (Eurocrypt 2022) that was previously known only under discrete-log assumptions. We give a practical construction that enables succinct disjunctive proofs via a variant of the self-stacking compiler of Goel et al. Along the way, we develop a new technique for batching CNF proofs of $\Sigma$-protocols, which allows one to efficiently prove that a value is the output of a PRF on one of a set of inputs. As a direct application, this yields logarithmic-size lattice-based ring signatures based on Fiat–Shamir-with-Aborts $\Sigma$-protocols (Lyubashevsky, Eurocrypt 2012). Finally, we observe for the first time that the anonymous counting tokens of Benhamouda, Raykova, and Seth (Asiacrypt 2023) can be obtained from anonymous rate-limited tokens. This yields a construction whose communication complexity is independent of the number of tokens that need to be issued.

The European Digital Identity Wallet (EUDI Wallet) is currently adopting ECDSA-based signed credentials as part of its core architecture, which raised concerns that such designs inherently lack plausible deniability compared to authenticated-channel approaches such as the German electronic identity card. This paper revisits this perceived trade-off and argues that it is not a property of signature schemes themselves, but of the credential presentation protocol. We show that standard cryptographic techniques - specifically lightweight OR-proofs over the native ECDSA verification equation - can be used to transform signed credential presentations into non-transferable, verifier-bound transcripts. Our contribution is not a new cryptographic primitive, but a careful instantiation of well-established techniques within the EUDI context, showing that deniability can be added to signed credentials while preserving their deployment advantages.

Secure function evaluation (SFE) and private function evaluation (PFE) are fundamental primitives in multiparty computation. In SFE, multiple parties jointly compute a \textit{public} function over private inputs while revealing nothing beyond the output, whereas in PFE the function itself is \textit{private} and known only to a designated party. In this work, we focus on the semi-honest setting and present more efficient information-theoretic constructions for both SFE and PFE. For SFE, the classical BGW protocol incurs $O(n^2)$ communication per multiplication gate. The DN protocol (Damg\aa rd and Nielsen, Crypto 2007) reduces the amortized communication to linear but still require an additional $O(n^2)$ term, yielding $O(m^* n + n^2)$ communication for $m^*$ multiplication gates. This becomes suboptimal in the regime $m^*= o(n)$. We introduce a simple technique that removes this quadratic overhead, achieving strictly linear $O(m^* n)$ communication. For PFE, the only existing information-theoretic approach relies on universal circuits, which results in $O(m^5n+n^2)$ complexity for arithmetic circuits. We develop new techniques that avoid universal circuits entirely. Combined with our SFE improvements, this yields an honest-majority PFE protocol achieving $O(m^2n)$ communication for circuit size $m$. We further obtain improved efficiency in special cases, including a three-party protocol with $O(m^{4/3})$ communication, and an $n$-party protocol tolerating one corruption with $O(m^{(2n-2)/(2n-3)}n)$ communication.

How few participants are needed before general secret-sharing schemes can outperform linear ones under a fixed security notion? Under statistical security, we show that the answer is five participants; under perfect security, the corresponding threshold remains unknown. It is known that the \(157\) connected access structures on five participants split into \(140\) Shannon-exact cases and seventeen exceptional cases. For the former, linear schemes attain the Shannon polymatroid region; for each of the latter, the exact linear contribution region is the all-pairs one-common-information region and is strictly smaller than the Shannon region. We investigate the statistical contribution regions of these seventeen exceptional structures. For fifteen of them, we construct a partial scheme whose contribution vector lies outside the exact linear region; Jafari--Khazaei's partial-to-statistical transfer then gives a statistically secure family with the same asymptotic vector. One dual pair remains open. For \(\Gamma_{30}\), we further show that the maximum information ratio under statistical security lies in \([14/9,1.6502)\), improving both previously established bounds; moreover, \(1.6502<5/3\), where \(5/3\) is the optimum for linear schemes.

Privacy-preserving payment systems are well understood, yet concerns about their misuse for financial crime have led to only limited adoption in regulated settings such as central bank digital currencies (CBDCs) and institutional stablecoins. Tracing is one tool for addressing these concerns: acting on external evidence implicating a user, law enforcement follows the suspect's funds through the ledger to uncover laundering routes and accomplices. Existing coin-tracing schemes, however, provide no cryptographic bound on tracing reach: once initiated, a trace may propagate indefinitely through the transaction graph or persist across all future transactions of a targeted user. Keeping surveillance targeted and temporary therefore depends on the restraint of the authority or a committee. We introduce ephemeral coin tracing (ECT), a primitive that bounds tracing reach by construction. Each account carries an encrypted tag that records which traced identifiers its funds carry while hiding its tracing status from users. When funds move, the sender's tag degrades and merges with the recipient's tag. Each tracing contribution expires independently after a policy-defined number of hops and then becomes unrecoverable even to the tracing authority, without affecting other live contributions in the same tag. Public parameters also bound how many identifiers a tag can distinguish simultaneously. We formalize ECT and give constructions based on exponential ElGamal, Damgård-Jurik encryption, and Ring-LWE, the last providing post-quantum security.

Common information (CI) is useful in entropy-based lower bounds for secret sharing. We study CI for group-characterizable (GC) random variables. Building on the sufficient condition of Kaboli--Khazaei--Parviz, we prove an exact pair criterion: two coset random variables $X_H$ and $X_K$ have common information if and only if the subgroups $H$ and $K$ permute, that is, $HK=KH$. Consequently, a GC tuple is $1$-CI exactly when every pair of subgroups in the meet closure of its labels permutes, whereas it is recursively CI exactly when every pair in the generated subgroup sublattice permutes. This also gives a finite algorithm for deciding recursive CI, and we exhibit a GC tuple over $S_3\times S_3$ that is $1$-CI but not $2$-CI. Since normal subgroups satisfy the recursive criterion, homomorphic random variables are recursively CI. For the twelve-participant disjoint Fano--non-Fano access structure, the Shannon lower-bound method with all separate $1$-CI extensions still gives maximum and average optima equal to one. Two depth-two recursive CI extensions instead give the lower bounds $43/41$ and $54089/51756\approx1.04508$ for the maximum and average information ratios of perfect homomorphic schemes. The same bounds hold for Abelian schemes; the exact mixed-linear and linear values are already known.

MEV and censorship, fuelled by public mempool visibility, remain existential threats to Ethereum and have recently started to spread to its layer-two ecosystem. Encrypted mempools promise to conceal transaction content until ordering is final. While this sounds appealing, their viability rests on cryptographic, economic, and deployment trade-offs. This paper systematises the evolution of threshold-encrypted mempools, from early schemes such as Shutter and Ferveo to the most recent research, and analyses how successive iterations have resolved bottlenecks like committee communication overhead, lack of pending transaction privacy, and position-dependent encryption. We highlight a convergence along four design axes, namely batched decryption to mitigate latency, silent setup to eliminate the complexity of distributed key generation, epochless encryption to remove position dependency, and collision-free encoding to prevent slot-collision censorship. We further survey the active Ethereum deployment debate, including EIP-8105 and the LUCID headliner submission, and map the requirements raised there onto the cryptographic corpus. We conclude by exposing a critical limitation common to all current proposals: blind ordering and binary decryption together suppress not only the toxic part of MEV that motivated encrypted mempools, but also the same-block auction mechanisms that return value to users and sustain geographic decentralisation of the network.

We introduce Noisy Torus Conjugation (NTC), a lattice assumption in which a short secret is confined to a non-split maximal torus of $GL_k(R_q)$ and acts by conjugation on a uniform matrix, the result being masked by a short additive error. NTRU is the $k=1$ member of the family. Passing to $k \ge 2$ changes the geometry of the underlying lattice in two specific ways. The planted module occupies a fraction $1/(2k)$ of the published lattice's dimension, against NTRU's $1/2$; and the norm-map shortcut that governs the overstretched regime is blocked once the conjugated matrix is required to be uniform over the full matrix algebra instead of the torus. We develop the structure theory of the assumption: marginal uniformity of each component, invariance along the torus orbit, a rigidity theorem identifying the full set of short solutions, and a reduction from search to decision. On it we build an IND-CCA key encapsulation mechanism whose passive security reduces tightly to NTC together with one isolated decisional assumption. At NIST categories 1, 3 and 5 it reaches public keys within 1.08 to 1.16 times Kyber's and ciphertexts 2.0 to 2.1 times Kyber's. The new assumption is not load-bearing but purchasable. Widening the key distribution to the smoothing parameter of the key lattice would make the public key statistically uniform and remove it altogether, leaving IND-CPA on module-LWE and hence on a worst-case problem. We price that variant at a factor 3.4 on the public key and 4.0 on the ciphertext. It rests, however, on a regularity statement not established for the completely split rings our transform uses; we isolate that statement as a conjecture and give a modulus class for which it is not needed. Concrete parameters are selected with an estimator calibrated against the published core-SVP figures of Kyber, and validated against a hybrid meet-in-the-middle model whose single free constant is fitted on Kyber. The fatigue predictions underlying the modulus window are tested further by lattice reduction. We reduce small instances of the published lattice against NTRU controls of identical dimension, determinant and planted-vector norm, and at every modulus the NTRU plant is discovered as a dense sublattice while the sparser NTC plant is not. A companion paper builds a Fiat-Shamir-with-aborts signature from the same assumption. The assumption is new and has no worst-case reduction; we state throughout what is proved, what is heuristic, what is measured, and what remains open.

Quantum public-key encryption (QPKE) is an important direction for secure communication in the presence of quantum adversaries. In this paper, we analyze the four-state QPKE scheme of Liu et al. and show that its ciphertext structure leaks information about computational-basis plaintexts. We present a ciphertext-leakage attack in which an adversary, without knowing the private key, measures the quantum ciphertext component and combines the result with the exposed classical correction bit to recover the plaintext. To overcome this limitation, we propose $\mathsf{sQPKE}$, a simple quantum public-key encryption scheme. The $\mathsf{sQPKE}$scheme uses only elementary operations such as XOR, parity computation, CNOT, Hadamard, Pauli-$Y$ gates, and computational-basis measurements. We prove correctness, analyze security against ciphertext-leakage, eavesdropping, and distinguishing attacks, and validate the attack and proposed construction through Qiskit implementation and resource estimation.

This paper presents several optimizations to Qlapoti (Asiacrypt'25), an ideal-finding procedure at the heart of modern isogeny-based signature schemes. We apply these optimizations to the Qlapoti-based NIST Round-2 SQIsign implementation from Asiacrypt'25. Together, they accelerate the Qlapoti procedure by approximately \(1.6\times\) to \(5.3\times\), depending on the parameter set and implementation. Under the Broadwell benchmark, compared with the baseline implementation in Asiacrypt'25, our optimizations achieve key-generation speedups of \(1.29\times\), \(2.23\times\), and \(1.54\times\), and signing speedups of \(1.23\times\), \(1.79\times\), and \(1.43\times\), at NIST security levels~1, 3, and~5, respectively. Our techniques also apply to the Qlapoti-optimized PRISM implementation (PKC'25, Journal of Cryptology), for which we introduce an additional tailored optimizations. Under the Broadwell benchmark, compared with the baseline implementation in JoC using Qlapoti, our improvements translate into key-generation speedups of \(1.22\times\), \(1.87\times\), and \(1.46\times\), and signing speedups of \(1.47\times\), \(1.90\times\), and \(1.60\times\), at NIST security levels~1, 3, and~5, respectively.

We present LUNA+, a refinement of the LUNA designated-verifier lattice-based ZK-SNARG that achieves significantly improved concrete succinctness. While the original LUNA scheme achieves quasi-optimal asymptotic proof length ($O(\lambda)$), its practical parameters are constrained by its statistical privacy analysis. This analysis, founded on a Leftover Hash Lemma with Leakage (LHLL), necessitates the use of polynomially large, but still significant "smudging" noise to guarantee statistical uniformity. This noise inflation directly propagates to larger lattice dimension and modulus parameters and, consequently, larger proof and CRS sizes. Our core contribution is a new privacy analysis that replaces this statistical foundation with a computational one. We demonstrate that the circuit privacy of LUNA's re-randomization procedure can be securely based on the computational hardness of the Matrix Hint-Module Learning With Errors (MH-MLWE) problem. This computational approach avoids the need for large statistical noise and enables a key optimization: we decouple the secret re-randomization noise from the fresh masking noise. We then formalize and solve an optimization problem to find the minimal noise parameters that satisfy both correctness and the MH-MLWE security reduction. In the process, we also introduce a new problem called Coset Error Knapsack MH-MLWE in which the MLWE error is sampled from a coset of a lattice, which we show is as hard as the standard MH-MLWE problem, and may be of independent interest. This new analysis results in substantial concrete efficiency gains. For a 128-bit security level and an R1CS instance of size $2^{16}$, LUNA+ reduces the proof size by $\approx 25\%$ (from 5.60 KB to 4.22 KB) and the compressed CRS size by $\approx 73\%$ (from 2.06 GB to 0.54 GB) compared to the original LUNA. These succinctness improvements are also accompanied by performance gains, including up to a $\approx 1.73\times$ speedup in setup, a $\approx 1.53\times$ speedup in addition and a $1.44\times$ speedup in decryption for the implementation parameters.

Anamorphic cryptography targets the scenario in which a dictator does not forbid the use of cryptography but requires all users to reveal their secret keys to them. Thus, the dictator can decrypt all honestly generated ciphertexts. The approach for bypassing this is to identify spots, such as random nonces, in existing cryptographic protocols in which secret messages can be hidden using an additional secret double key. So far, the literature mostly focused on identifying such spots in simple primitives like public-key encryption or signatures; only recently, an initial work identified limited spots in Signal's Double Ratchet Algorithm. We are the first to leverage the statefulness of cryptographic communication protocols to employ continuously updated double states and, thereby, achieve Forward Security: Even if the adversary (i) observes all traffic, (ii) knows all users' regular secret key material at any stage of the protocol execution, and (iii) at some point learns the secret double state, the entire protocol execution looks benign although covert messages were previously hidden in the traffic anamorphically. We formalize this notion and also cover robustness and authenticity, which appear to be particularly relevant in the messaging context. In this new model, we study four of the most relevant messaging protocols and identify hiding spots therein: Signal's Double Ratchet, Signal's Triple Ratchet, Apple's PQ3, and the two-party core of the Messaging Layer Security Standard. We focus on the cryptographic parts of these protocols and, despite their complexity, identify surprisingly few anamorphic hiding spots. We prove that all these protocols offer forward secure, authenticated anamorphic channels and we evaluate their bandwidths: While 16 bits can be embedded in every epoch of the Double Ratchet, Triple Ratchet and PQ3 provide 176 bits, respectively 256 bits, of bandwidth per post-quantum epoch, and MLS provides 688 bits per epoch.

We present the first ciphertext-only distinguishing attack on 5-round AES and a key-recovery attack on 6-round AES for all key sizes under ASCII-encoded English-language plaintext distributions, as well as additional ciphertext-only results under uniform ASCII distributions. Our attacks are enabled by a new analytical framework for estimating truncated differential probabilities in 5-round AES, a problem that remains largely unresolved beyond restricted configurations. Existing approaches, relying on statistical sampling, integral cryptanalysis, or differential distribution tables of super S-boxes, are primarily limited to settings with a single active diagonal in the plaintext and a single passive inverse diagonal in the ciphertext. Our method extends this line of work by providing analytical estimates over a substantially broader range of configurations. We construct this framework by combining precise computations of MDS-level transition probabilities with a systematic enumeration of truncated differential characteristic classes. By organizing characteristics into equivalence classes defined by diagonal propagation patterns, we enable structured aggregation of probability contributions. This approach captures configurations with a single active diagonal in the plaintext and arbitrary passive inverse diagonals in the ciphertext, as well as the complementary setting involving multiple active diagonals in the plaintext and a single passive inverse diagonal in the ciphertext. Our results are validated through independent derivations, consistency checks against prior work, and computer-aided enumeration. More broadly, the framework offers a systematic approach to truncated differential analysis of AES and potentially other AES-like SPN ciphers.

We revisit the notion of PViO [Jain-Jin, FOCS’22] – an indistinguishability obfuscation (iO) scheme for Turing machines with unbounded input length that guarantees security for pairs of machines whose equivalence can be proven in Cook’s Theory PV. Known constructions of PViO require subexponentially-hard iO for circuits. We give the first construction based on polynomially-hard iO and other standard assumptions. We further show how to replace iO with EFiO – an efficiently falsifiable variant, thus obtaining a construction based on efficiently falsifiable assumptions. Central to our result is a new twist to the celebrated punctured programming technique [Sahai-Waters, STOC’14], where one can program an obfuscated probabilistic function on its entire input domain in one shot instead of an input-by-input manner. Our key ingredient is the notion of function secret sharing [Boyle-Gilboa-Ishai, EUROCRYPT’15]. We further show the versatility of our technique by removing the use of complexity-leveraging in two applications of iO: unleveled fully homomorphic encryption, and adaptively-sound succinct non-interactive arguments for “trapdoor” languages.

In real-world applications of SNARKs, non-native arithmetic, the emulation of computation outside of the specified SNARK field, is a key bottleneck. It introduces large overheads, and proof system designers often resort to non-standard SNARK-friendly hash-functions or other means like elliptic curve cycles to mitigate its costs. Besides performance concerns, non-native circuit arithmetization is also a major cause of implementation errors. In a collection of 27 critical bugs in real world ZK systems (0xPARC/zkbugtracker), 9 were related to non-native arithmetization. We tackle these challenges by constructing a minimal overhead SNARK for integer computation that generically handles non-native arithmetic. We follow the recipe of Zaratan (PKC 26), which proves an integer relation such as $a\cdot b = c + u\cdot m$ by fingerprinting---reducing it to the same relation but over a randomly sampled prime field. Realizing this recipe requires an integer mod-PCS that commits to integer polynomials and opens their evaluations modulo a random prime, which is crucially chosen after the underlying PCS's setup and commitment phases. Our central contribution is Limber, the first practical integer mod-PCS construction that asymptotically has $o(1)$ multiplicative commitment overhead and can be instantiated with any standard field polynomial commitment scheme, including ones over small fields. Combining Limber with a PIOP for integer R1CS over the random prime yields our SNARK. We demonstrate its practicality by implementing our scheme and showing that we can prove an RSA accumulator benchmark $15$-$30\times$ faster than circuit-based approaches, and non-native Poseidon2 hashing $24\times$ faster.

MAYO is a signature scheme based on the Unbalanced Oil and Vinegar (UOV) construction and a third round candidate in the NIST standardization process for additional post-quantum signature schemes. We present a memory-optimized pure- C implementation of MAYO signature verification that reduces RAM consumption by 97–99% compared to the reference implementation provided by the PQM4 project [KPR+] at the cost of increasing runtime by 50–200% and while maintaining code size. This reduction finally enables verifying MAYO signatures on smart cards and small microcontrollers with only a few kilobytes of RAM. We achieve it through three coupled design choices: a) we expand the public key vector-by-vector on the fly rather than all at once at the start; b) we reorder the calculation of the matrix product SPS so that each vector of P is used exactly once, which avoids repeated expansions; and c) we add precomputed multiples of each P-vector directly onto the result instead of accumulating P-vectors before multiplication. We provide results using the PQM4 framework for all parameter sets listed in the specification and supported by PQM4 on our platform, including three main parameter sets MAYO{1,2,3}. This enables direct comparison with other post-quantum digital signature schemes. Further parameter sets not supported by PQM4, including the fourth main parameter set MAYO5, are measured on our own framework, which supports key and signature generation on the host. Our results for non-standard MAYO parameter sets offer insights into the performance and scalability of the proposed approach that may inform ongoing standardization efforts.

Rotational-XOR (RX) cryptanalysis extends rotational cryptanalysis by combining rotational relations with XOR translations, enabling the analysis of symmetric-key primitives even in the presence of symmetry-breaking constants. Existing analyses of RX characteristics, however, typically rely on independence assumptions when estimating characteristic probabilities, which may lead to inaccurate probability evaluations and even incompatible characteristics. In this paper, we introduce the first application of the geometric approach to RX cryptanalysis. Inspired by the quasidifferential framework of Beyne and Rijmen, we define rotational-quasidifferential trails and derive exact expressions for fixed-key RX characteristic probabilities without relying on round-independence assumptions. We also derive explicit rotational-quasidifferential transition matrices for bitwise AND and modular addition. By incorporating the key schedule into the state space, we further obtain an exact expression for the Expected Rotational-XOR Probability (ERXP), the RX analogue of the Expected Differential Probability (EDP). We apply the framework to the ARX cipher SPECK, the ARX permutation Alzette, and the AND-RX ciphers SIMON and SIMECK. For SPECK32/64, we reproduce known incompatibility results and repair an incompatible 12-round characteristic. For Alzette, we show that signed nonzero-mask contributions explain the discrepancy between independent-ADD estimates and experimentally observed full-data-path probabilities. For SIMECK, we experimentally verify a fixed-key probability distribution, explain incompatible characteristics, and correct the weak-key class estimates of rotational-XOR differential rectangle attacks. These results extend the geometric approach to both ARX and AND-RX designs and demonstrate its usefulness for exact characteristic-level analysis.

Recent works have highlighted the risk of deterministic memory encryption, as used for example in AMD SEV. In the so-called ciphertext side-channel attack, an adversary leaks sensitive information, such as cryptographic keys, from an encrypted VM by observing changes in the encrypted contents of the memory. To date, countermeasures have been quite restricted in scope and have not addressed the root cause. Alternatively, some studies suggest adding freshness to memory encryption. However, this approach is considered impractical due to the performance overhead introduced by fetching such freshness values for every single memory access. In this work, we propose an efficient approach for eliminating most of the overhead of fetching the aforementioned freshness. Our core idea is to repurpose the ECC memory area to efficiently store random nonces or counters. We propose a range of implementations with varying trade-offs between security guarantees and performance overhead, and demonstrate that we can achieve a solid baseline security even with small random nonces. By leaving a portion of ECC memory unused, we show that it is possible to efficiently integrate protection mechanisms such as memory integrity and memory tagging, while limiting the overall performance overhead to approximately 2%.

Private Function Evaluation (PFE) facilitates the secure computation of private functions on private inputs in an oblivious manner, ensuring that both the function and the inputs remain confidential throughout the entire computational process. PFE has garnered significant attention due to its critical applications in various domains, such as privacy-preserving healthcare systems and privacy-preserving credit checks, where safeguarding the confidentiality of the function itself is of paramount importance. However, despite its broad applicability, existing PFE schemes often exhibit inefficiencies, even in relatively straightforward scenarios such as the evaluation of lookup tables. To mitigate these limitations, we propose a novel variant of PFE, termed Preprocessed Private Function Evaluation (PPFE), which leverages preprocessing techniques to significantly enhance the efficiency of online computations. Within this framework, we introduce a specialized construction tailored specifically for lookup table operations, achieving sublinear complexity during the online computation phase. The efficacy of the proposed approach is demonstrated through experimental evaluations. For a lookup table of size $2^{24}$, the online computation time required to process a single query is about 3 milliseconds, representing a performance improvement of more than an order of magnitude compared to existing results. Furthermore, the proposed scheme exhibits strong scalability, effectively handling thousands of adaptive queries within the same framework.

The McEliece code-based cryptosystem, utilizing binary Goppa codes, is the earliest public-key encryption scheme that is still considered post-quantum secure. We present a simple, classical quasipolynomial-time distinguisher for Goppa–McEliece in the asymptotic “Classic McEliece” regime: for code length \(n\), extension degree \(m=\Theta(\log n)\), Goppa degree \(t=\Theta(n/\log n)\), and public-code dimension \(k=\Theta(n)\), the algorithm runs in time \(n^{{\mathcal O}(\log n)}\) and distinguishes the McEliece public key from the uniform distribution over \(\mathbb{F}_2^{k\times n}\) with advantage \(1-o(1)\). The distinguisher is not merely asymptotic: it applies to all Classic McEliece parameter sets considered in the NIST process and yields improved (though not yet practical) concrete attack estimates. Our distinguishing attack originated from a failed attempt to construct doubly efficient private information retrieval (PIR) protocols from algebraic locally decodable codes, and can be intuitively explained from the PIR perspective. We extend this provable algorithm to a heuristic \(n^{{\mathcal O}(\log n)}\)-time ciphertext-decryption attack that recovers the message from a noisy codeword and a heuristic \(n^{{\mathcal O}(\log n)}\)-time key-recovery attack that outputs an equivalent decryption key. While the decryption attack is not concretely efficient, the key-recovery attack is much closer to the distinguisher and may be relevant to NIST security levels.

Selfish mining undermines incentive compatibility of proof-of-work blockchains, letting a miner earn disproportionate rewards at a hashrate lower than the majority threshold. A decade of work has asked whether a strategy is profitable, however, far less is understood about when it becomes profitable. Timing is critical since selfish mining operates at a loss before it turns a profit, typically requiring tens of weeks to break even in the classic case. In this paper, we present a holistic study of the time-to-profitability (TTP) of existing selfish mining strategies structured around four contributions. First, in the single-attacker setting, we characterize TTP across the full strategy space and find that TTP-minimizing and profit-maximizing strategies frequently diverge, making attack horizon a critical metric. In particular, under realistic fee dynamics, the use of incentive transactions to recruit honest-but-rational miners enable incentivized strategies to reach profitability up to $15\times$ faster than classic selfish mining at the same hash rate. Second, we explore TTP for the first time in the multi-attacker setting, showing that the difference in strategies between opposing attackers has a dramatic impact on joint-profitability lag. Third, we generalize intermittent selfish mining by exploring temporal composition over the full strategy space and show that its purported benefits are largely overstated. That is, alternating strategies rarely outperform the best static strategy in terms of either TTP or long-term profits. Finally, and building off our earlier findings, we explore adaptive, state-conditioned strategy selection at the difficulty adjustment period (DAP) level. We compare a general-purpose LLM agent against a fixed decision-tree selector, both implementing the same selection criteria. We find that both selectors reliably identify profit-maximizing strategies from observed network conditions, at a low operating cost, lowering the expertise barrier to exploiting adaptive selfish mining.

Lattice-based cryptography offers a promising direction for transitioning Bitcoin toward post-quantum security, serving as a secure replacement for currently deployed discrete logarithm signatures. The primary advantages of lattice-based signature schemes include the compact combined size of signatures and public keys (e.g., in some cases below 1.6 KB), the robustness of underlying security assumptions, and an algebraic structure that, while not yet yielding practical constructions, holds potential for advanced functionality such as threshold and multi-signatures, compared to hash-based constructions. In this paper, we present a self-contained review of three lattice-based signature schemes, with Bitcoin's post-quantum transition as the motivating application: Dilithium, Falcon, and Hawk. The latter was recently withdrawn from NIST standardization following a key-recovery attack; we retain it because its design paradigm remains of independent interest. For each protocol, we detail the high-level intuition, the necessary technical preliminaries, low-level mechanics, performance, and security analysis. We then assess the deployment aspects relevant to Bitcoin: the on-chain footprint, determined by the combined public-key and signature size and compared against hash-based alternatives; the target security level for outputs that may remain unspent for decades; implementation constraints, such as Falcon's floating-point signing; and wallet key derivation. No prior exposure to lattice-based cryptography is assumed: all the required background is developed within the document.

Threshold Decryption (TD) enables a set of decryptors, each holding a secret key share, to collaboratively decrypt ciphertexts. In this paper, we resolve the open problem raised by Devevey et al. [PKC 2021] of constructing an adaptively secure TD with polynomial modulus from lattices. As identified by Hwang et.al. [ePrint 2026/1585], solving this open problem is a particularly challenging task. The most challenging part is how to limit the leakage of secret key shares from decryption queries while keeping the modulus a polynomial. In this paper, we resolve the above open problem with two TD schemes TD1, TD2 from lattices in the random oracle model. -- TD1 is a non-interactive TD scheme achieving adaptive CCA-security with polynomial modulus for a small number of decryptors and bounded decryption queries. It can be extended to achieve robustness and works well in the asynchronous settings. -- TD2 is a non-interactive TD scheme achieving adaptive CCA-security with polynomial modulus for bounded decryption queries. Compared with TD1, it supports any polynomial number of decryptors and works well in the synchronous settings. To our best knowledge, our TD1 and TD2 are the first non-interactive TD schemes achieving adaptive security and polynomial modulus from lattices. The core techniques behind our schemes include the polynomial noise flooding technique and the coupled refined Leftover Hash Lemma (LHL) working for adaptive noisy linear leakage, which may be of independent interest.

In multi-epoch deployments, private set union~(PSU) operates in an adaptive-input loop: after observing the union at epoch $t$, the receiver may choose its next input for epoch $t+1$. Liu et al.~(EUROCRYPT 2026) formalized this multi-epoch adaptive-input setting for updatable private set intersection and provided an instantiation, but their framework does not extend to PSU. Meanwhile, existing PSU protocols are analyzed only in the single-shot setting. We present the first semi-honest, adaptive-input-secure updatable PSU protocol supporting two-sided add/delete updates in the multi-epoch adaptive-input setting of Liu et al. Our construction is built around a new primitive, the updatable oblivious key-value store (uOKVS). Its defining rule, distributional erasure, requires each refresh to be distributed identically to a fresh static encoding of the current key set, rather than merely indistinguishably. We realize uOKVS by combining the Band-OKVS of Bienstock et al. with a PRF under a persistent key. The resulting refresh reuses a cached factorization, so its per-epoch encoding cost scales linearly rather than quadratically in the band width $w$. Building on this layer, we obtain a multi-epoch PSU protocol whose leakage is limited to set and update cardinalities, even against adaptive-input adversaries. We implement the protocol and benchmark it in a single-threaded setting. At $n = 2^{20}$ with per-epoch updates $\Delta = 55$ over $10$ epochs, the online per-epoch wall-clock time is $1.41$ s on LAN, yielding a $30.9\times$--$98.9\times$ speedup over prior static PSU protocols re-executed from scratch at each epoch.

Grinding is a technique which introduces a proof of work into the Fiat-Shamir transform: by constraining the challenge to satisfy a $w$-bit condition, forging a proof requires about $2^w/\varepsilon$ evaluations of the hash function instead of $1/\varepsilon$, where $\varepsilon$ is the soundness error of the underlying protocol. This allows one to select reduced parameters, yielding shorter proofs and signatures. Grinding is used in FAEST, MQOM and SDitH, the three MPC-in-the-Head schemes selected for the third round of the NIST additional post-quantum signature standardization process, where it is instantiated with Keccak. In this short paper, we investigate grinding schemes in which the proof of work is expressed in terms of block cipher computations, specifically AES, which is significantly faster than Keccak on modern CPUs, is already a building block of these schemes, and underlies the very definition of the NIST security categories. We formalize the notion of grinding scheme together with a protocol-agnostic security notion, we propose a construction performing two cipher calls per iteration, and we prove, in the ideal cipher and random oracle models, that an adversary making $Q_E$ cipher queries breaks it with probability at most $\frac{4}{3} \cdot \varepsilon\, Q_E / 2^w$, up to negligible terms. We further generalize the scheme to use more cipher calls per iteration, which makes the constant $\frac43$ tend to $1$.

We present a formally verified implementation of the ML-KEM Number-Theoretic Transform (NTT) based on Plantard arithmetic, produced via a code generator that targets ML-KEM, ML-DSA, and FN-DSA from a single parameter triple. The generator embeds a static bound analyzer that places modular reductions at code-generation time without runtime branching, eliminating per-scheme manual tuning while preserving constant-time guarantees. Each generation produces structurally identical implementations in two backends: portable C, and Jasmin for formal verification. To establish end-to-end correctness, we contribute a parametric formalization of Plantard arithmetic in \textsc{EasyCrypt} and a layer-by-layer program-equivalence proof connecting the extracted Jasmin ML-KEM NTT to the abstract specification of formosa-mlkem; the existing algebraic chain is reused unchanged to extend correctness down to the mathematical NTT definition. Benchmarks across three schemes show that the generated code outperforms reference C by $1.5\times$--$1.8\times$ on the forward NTT and $1.7\times$--$2.5\times$ on the inverse, and outperforms the formally verified formosa-mlkem Jasmin baseline by $1.26\times$ and $2.19\times$ on ML-KEM. We believe our techniques generalize to other lattice-arithmetic primitives requiring both performance and formal verification.

Levin and Pedersen proposed at Asiacrypt2025 a new verifiable random function (VRF) based on a CGL-analogue hash function constructed from radical isogenies. Their construction applies the same secret radical-CGL walk to a public starting curve and a message-dependent curve, and uses an R1CS proof relation to show that the two walks use the same secret key. We present a two-stage attack on this construction. The first stage concerns the unspecified representation of the public key. The reported key size indicates that the public curve is stored as a \(j\)-invariant, whereas both the specified radical-CGL computation use two coefficients to represent a curve. By exploiting this form we can produce two different VRF outputs under the same public key and message, breaking the unique provability. Hence, the output of the radical-CGL computation must follow the specification. In the second stage, we exploit these coefficients to recover the VRF secret key. With \(1536\) queries, our implementation recovers the complete \(256\)-bit secret in 30 minutes, thereby breaking residual pseudorandomness. Interestingly, we also observe that the using public key alone without queries can sometimes reveal one or two bits of the secret walk. Besides, we extend Lai's observation to obtain a one-query attack on the group-action-based VRF proposed in the same paper with advantage closed to 1/2. Together, these constitute three attacks on their work.

We perform the first formal security analysis of the cryptographic core of Olvid, an end-to-end encrypted messaging app notably used by French government officials, including ministers. Despite its deployment in sensitive contexts and its role in critical communications infrastructure, Olvid's cryptographic security has received little independent analysis. To address this gap, we develop detailed models of Olvid's authenticated key exchange and continuous key agreement protocols. We formally verify that our protocol models achieve security properties such as mutual authentication, session-key secrecy, forward secrecy, and replay protection, under an active Dolev-Yao network adversary model that can compromise parties. While we constructively prove that the protocol design meets core security guarantees, our analysis also reveals that, contrary to its claims, the protocol does not meet strong modern security properties that are met by other state-of-the-art secure-messaging protocols, such as Signal. For example, we show in our formal analysis that Olvid is not secure in modern security models such as eCK. Along the way, we uncover a potential timing leakage, and discuss Olvid's anonymity claims.

Motivated by the 2026 COLDCARD incident, this paper studies cryptographic asset recovery after self-custodial seed-generation failures. Self-custodial hardware wallets depend on secure entropy sources for seed generation. If an RNG implementation or design failure reduces seed entropy, an adversary may reconstruct wallet signing keys through offline search. Such weaknesses may also be discovered long after wallet creation, placing existing self-custodial assets at risk. To prevent large-scale exploitation after such a failure is identified, a hardware manufacturer or security response team may perform a protective sweep of affected assets into a protected recovery treasury. Asset redistribution then creates a fundamental authentication problem: once the signing key can be reconstructed by both the legitimate owner and an adversary, possession of that key no longer uniquely identifies the legitimate controller. We propose Z-SCAPE, a zero-knowledge recovery-credential protocol for privacy-preserving asset recovery after seed-generation failures and protective sweeps. Before compromise, the user commits to a recovery credential consisting of a 256-bit recovery secret $r$ generated from an entropy source intended to be independent of the transaction-signing seed, and an RNG-independent personal record $P$. After an incident, the prover proves knowledge of $(P,r)$ in zero knowledge for the pre-bound wallet identifier $W$, while binding the proof to the incident-specific protected-asset reference, a fresh verifier nonce, an expiry value, and a fresh recovery destination. The verifier derives the protected-asset reference from authenticated protective-transfer records rather than accepting an arbitrary asset set from the claimant. The protocol enables recovery claims without revealing $P$, $r$, or the compromised wallet private keys, while preventing replay, destination substitution, and cross-wallet protected-asset substitution. Z-SCAPE provides concrete integration mechanisms for Bitcoin and Ethereum and enables only assets recorded as protectively transferred from the proved wallet to be returned to the fresh destination bound to an accepted recovery proof.

The Unbalanced Oil and Vinegar (UOV) scheme was proposed by Kipnis et al. in 1999 as a multivariate signature scheme. Owing to its small signature size and its resistance to various attacks over more than two decades, UOV has become one of the leading candidates in multivariate public key cryptography. In 2025, Ran proposed a novel algebraic key recovery attack exploiting the algebraic structure of UOV, which reduced the security of several parameter sets of UOV and its variants submitted to the second round of the NIST PQC standardization process for additional signatures. This attack was improved by Jin et al., and Furue and Ikematsu, forming a line of attacks that has significantly advanced the cryptanalysis of UOV. However, Ran's attack is applicable only when $v<2m$, where $v$ denotes the number of vinegar variables and $m$ the number of public polynomials. In fact, when $v\ge 2m$, an additional kernel element of the ideal generated by the public polynomials appears, preventing the attack from recovering the oil subspace. A similar issue arises in the improvements by Jin et al., and Furue and Ikematsu. In this paper, we propose a method that overcomes this issue, extending the applicability of this line of attacks to the case where such an additional kernel element appears. Applying our method to SNOVA via the lifting technique of Nakamura et al., we show that the claimed security levels of some parameter sets of SNOVA in the second round of NIST PQC standardization process for additional signatures are reduced. In particular, for the parameter set $(v,o,q,l)=(37,17,16,2)$ of NIST security level I, although Ran's attack is not applicable, our method reduces the estimated security to $2^{103}$ gate operations, which matches the complexity of the attack by Bros et al. in 2026.

In a single secret leader election (SSLE) protocol, all parties collectively and obliviously elect one leader. Parties other than the selected leader should not be able to learn the identity of the leader unless it is revealed by the leader itself. The problem is first formalized by Boneh et al. (AFT 2020), and the first concretely feasible lattice-based SSLE with proof-of-concept implementations, $\mathsf{Qelect}$, was recently introduced by Wang and Zhang (USENIX 2025). In this work, we present $\mathsf{Relect}$, an efficient SSLE protocol, based on the Ring Learning with Error assumption. We build it by leveraging the algebraic structure of the underlying threshold Fully Homomorphic Encryption (FHE) and by designing tailored homomorphic circuits. Compared to prior works, $\mathsf{Relect}$ (1) achieves substantially higher efficiency and (2) removes the strong environment assumption in $\mathsf{Qelect}$ (a trusted setup), while allowing dynamic leader selection for each round. Concretely, for $32$ -- $2048$ parties, our local FHE computation runtime (a major efficiency bottleneck for SSLE) achieves $7.15$ -- $42.4\times$ faster than $\mathsf{Qelect}$ for a single thread and $7.10$ -- $48\times$ faster for 16 threads. Furthermore, we show that for the same parameters, our communication cost is also $1.14$ -- $2\times$ smaller. As mentioned, this is achieved while removing the trusted setup. In terms of end-to-end runtime, following $\mathsf{Qelect}$, we tested $2$ -- $128$ parties. We show that under the LAN setting, $\mathsf{Relect}$ is $2.77$ -- $345\times$ faster than $\mathsf{Qelect}$ per round. Under the WAN setting, $\mathsf{Relect}$ is $1.94$ to $17.2\times$ faster than $\mathsf{Qelect}$. Note that these performance gains are all achieved while removing the trusted assumption and achieving dynamic leader selection for each round.

Anonymity infrastructures such as mix networks, anonymous storage, and privacy-preserving replication rely on public re-randomization: any party holding only public information can transform a ciphertext into a fresh-looking encryption of the same plaintext, hiding the linkage between the two. Classical ElGamal-based solutions are broken by quantum adversaries, while existing lattice-based alternatives carry very large ciphertexts with unanalyzed noise growth, rely on heavyweight homomorphic-encryption stacks with approximate (rounded) decryption, or lack a precise analysis of how many re-randomizations are safe. We address this gap with a practical Ring Learning with Errors (Ring-LWE) public-key encryption scheme supporting public re-randomization without ciphertext growth. Our construction is Lyubashevsky–Peikert–Regev / Fan–Vercauteren (LPR/BFV)-style encryption over $R=\mathbb{Z}[x]/(x^n+1)$ with $n=4096$, engineered around a two-limb Chinese Remainder Theorem (CRT) modulus $q=t\cdot q_2$ with 32-bit primes. Embedding plaintext as $\Delta M = q_2 M$ makes the message vanish modulo $q_2$, so the $q_2$-limb carries only the decryption noise, enabling exact message recovery without rounding. We prove correctness with explicit decryption-failure bounds that remain valid under repeated re-randomization, via an aggregation lemma showing that arbitrarily many re-randomizations affect decryption only through a single aggregated randomness triple. We also prove that two-limb ciphertexts are pseudorandom (indistinguishable from uniform, IND\$) under Decision Ring-LWE over the combined modulus $q=tq_2$; security against chosen-plaintext attack (IND-CPA) and re-randomization unlinkability follow. A constant-time Rust implementation encrypts in 0.80 ms, re-randomizes in 0.51 ms, and decrypts in 0.21 ms per 64 KiB ciphertext carrying 15.5 KiB of payload on a fixed-frequency 3.8 GHz CPU—on par with a modulus-matched Microsoft SEAL baseline—and passes timing-leakage tests. Empirical noise simulations validate the analysis.

Anonymous communication systems aim to hide which user sent which message, but existing designs sit at two extremes: efficient, centralized mixnets that rely on at least one honest mix server, and fully decentralized protocols such as DC-nets and MPC-based shuffles that avoid trusted mixers at the cost of high communication and fragility under disruption. This paper introduces \emph{verifiable self-mix} (VSM), a new anonymity architecture for privately shuffling messages posted on a public bulletin board. In VSM, users \emph{self-mix} their encrypted messages by writing them to secret locations in a public table. A preprocessing protocol, \emph{Unique Number Selection} (UNS), assigns every user a distinct hidden mix location; an anonymization protocol, \emph{Secure Mapping of Private Permutation} (SMPP), ensures that each such location contains exactly that user's ciphertext, without revealing the mapping from users to locations. Because each user learns their own final location, VSM provides \emph{unconditional individual verifiability}: after an optional decryption step, users can check that their message appears at the correct slot without running any cryptographic checks. We formally define VSM and prove anonymity, integrity, and self-verifiability in the malicious model. We then present several concrete instantiations. Our UNS protocols rely on either trusted hardware or multiple servers running plaintext-equivalence tests and require only constant private memory, making them suitable for constrained trusted execution environments. Our SMPP constructions allow trade-offs between trust and bandwidth, achieving $O(n)$ ciphertext uploads per user (or $O(\log n)$ in theory under FHE, at substantial setup cost), while avoiding the pairwise shared-pad state and interactive disruption-resolution typical of classic DC-net designs.

Quasi-Cyclic Moderate-Density Parity-Check (QC-MDPC) codes are a family of error correcting codes admitting parity-check matrices composed of sparse circulant blocks. QC-MDPC codes have been used for the design of BIKE, one of the finalists in the NIST competition for the standardization of post-quantum cryptography. Decoding of QC-MDPC codes with cryptographically relevant parameters is intrinsically bound to fail, resulting in a decoding failure rate (DFR) that is nonzero. To achieve INDistinguishability under Adaptively Chosen Ciphertext Attacks (IND-CCA2), the DFR must not exceed $2^{-\lambda}$, with $\lambda$ being the security parameter. QC-MDPC codes are customarily decoded with a Bit Flipping (BF) algorithm. Especially at very low DFR values, error patterns having a large intersection with near-codewords (which are vectors corresponding to columns of the parity-check matrix, up to some shift) are the main cause of decoding failures. In this paper, we show how a BF decoder can be tweaked to exploit the knowledge about near-codewords. Since error vectors that cause decoding failures are likely making the decoder converge to the closest near-codeword (i.e., to the near-codeword with the largest amount of overlapping positions with the error vector), we exploit such a harmful but predictable behavior: we let the decoder recognize, and consequently correct, syndromes of near-codewords. This modification comes with a very mild computational overhead and can be applied to any BF decoder. As a concrete application, we focus on BIKE parameters for NIST security category 1. We show that a recently proposed BF variant called $\textsf{BF}\text{-}\textsf{Max}$ outperforms significantly the two decoders used by BIKE within the NIST competition, achieving a significantly lower DFR with a comparable computational complexity.

Function secret sharing (FSS) has become a core primitive in privacy‑preserving computation. However, each FSS invocation requires a fresh pair of function keys, typically produced by a trusted dealer—a dependency that expands the system's trust boundary and hinders practical deployment. Existing dealerless protocols eliminate this dependency, but incur substantial communication and a number of interaction rounds that grows linearly with the input bit‑width, making key generation a major bottleneck. This paper presents KORD, a protocol–hardware co‑design that dramatically reduces the cost of dealerless FSS key generation. At its core is a pair of chips that establish a common root of trust through mutual attestation and, within it, reconstruct FSS keys—eliminating the need for a dealer. This root of trust further forms a security boundary within which KORD restructures the generation protocol, collapsing the interaction of prior dealerless protocols into a single round, independent of GGM depth. A cross‑key scheduling scheme then interleaves independent GGM‑tree traversals, sustaining high computational throughput. KORD reduces key‑generation communication per operation by $7{,}633$–$70{,}274\times$ over the state‑of‑the‑art distributed FSS protocol. On a ZCU102 FPGA, cross‑key interleaving lifts AES lane utilization from $8.3\%$ to a board‑measured $99.0\%$, for $11.60$ million $32$-bit DPF keys per second at $187.5\,\text{MHz}$ on a $21.5\,\text{K}$ LUT engine ($12.38\,\text{M}$ at the separately validated $200\,\text{MHz}$ operating point). On private ResNet‑18 inference, key generation's share of end‑to‑end time falls to $10.1\%$, from $82.6\%$ under a trusted dealer and over $96\%$ under the dealerless baseline.

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.

Distributed Oblivious RAM (DORAM) is a promising building block for privacy-preserving cloud databases and outsourced storage systems. However, existing two-server designs often rely on slow linear scans or heavy cryptographic primitives, making them struggle to balance efficiency and bandwidth, and thus hindering their practical deployment. We present DuetORAM, a two-server DORAM that achieves constant-round access with $O(\log N)$ communication while avoiding these computational bottlenecks. Our key idea is a replicated-to-shared block encoding that allows servers to keep identical ciphertexts for efficient PIR-based retrieval, while locally interpreting them as secret shares to enable oblivious eviction via a lightweight shuffle. We further design a secret-shared shuffle with an offline-online decomposition that shifts most bandwidth-intensive work to a preprocessing phase, significantly reducing online communication. We implement a prototype of DuetORAM and evaluate it under diverse network conditions. Our results show that DuetORAM outperforms both the state-of-the-art two-server scheme DUORAM (reducing retrieval latency by up to 170$\times$ in LAN settings), and three-server design S$^3$ORAM (reducing retrieval latency by 1.7$\times$ in LAN and accelerating eviction by 7$\times$ in LAN and 5$\times$ in WAN, respectively).

Privacy-preserving computation over real numbers typically employs either floating-point or fixed-point arithmetic. While fixed-point methods are highly efficient, they struggle to handle wide dynamic ranges. Conversely, floating-point methods support a much larger numerical scope but incur overheads more than a hundred times higher than their fixed-point counterparts. In this paper, we propose DYNAFIX, a dynamic fixed-point computation scheme that strikes a balance between floating-point and fixed-point arithmetic. Compared to traditional fixed-point approaches, our scheme supports an arbitrary numerical range; compared to floating-point computation, it maintains performance comparable to fixed-point execution. Experimental results demonstrate that our method achieves a $24.1\times$ speedup over the state-of-the-art when evaluating high-precision functions, such as the exponential function.

Secure and anonymous messaging has many compelling use-cases and is becoming increasingly popular. In this paper, we consider it in the context of delay-and-disruption-prone networks, which are characterized by handicapped network access, disrupted operation, censorship, and intermittent network outages. With such settings in mind, we define and design a Private Identity-Based Bulletin Board (PIB^3) scheme, which allows users to anonymously post and retrieve messages to and from a distributed database, and supports communication between users without pre-established setup or pre-exchanged keys. Anyone can encrypt a message for an identity and public epoch, such that only the party with the decryption key for that identity can identify, retrieve, and decrypt the message. Against one corrupted non-colluding PIB^3 server, the server learns neither the recipient identity nor the retrieved record indices beyond the leakage explicitly modeled by the scheme: the public epoch, the database size, and the number of retrievals made by the receiver. If retrieval-count privacy is required, retrievals can be padded to a fixed bound. The multi-server construction extends this guarantee to larger server sets, and gives coalition privacy whenever the underlying multi-server PIR scheme is private against the corresponding coalition. Contributions of this work are: (1) formally defining functionality and security requirements for PIB^3-s, (2) defining and constructing a Hierarchical Identity-based Encryption (HIBE) scheme with searchable ciphertexts, which serves as a building block for the proposed PIB^3 scheme and may be of independent interest, (3) designing an efficient PIB^3 scheme that can be realized with $n\geq 2$ servers based on the HIBE scheme with searchable ciphertexts combined with additional primitives, and (4) implementing a functional PIB^3 prototype which demonstrates practicality of the entire concept and allows us to assess its performance empirically.

The post-quantum signature scheme Falcon (FN-DSA), currently being standardized by NIST as FIPS 206 (Initial Public Draft submitted August 2025, final standard expected 2026-2027), relies on a discrete Gaussian sampler whose critical bottleneck is the function fpr_expm_p63, computing $\lfloor \exp(-x) \cdot 2^{63} \rfloor$ for $x \in [0, \ln 2)$. While the reference implementation already employs a degree-12 fixed-point polynomial (FACCT), no segmented approximation has been studied for this specific function, nor has empirical timing security been published on ARM Cortex-M3 (emulated or physical). This paper presents a systematic study of piecewise polynomial approximation applied to fpr_expm_p63, combining the Remez exchange algorithm (computed with 50 decimal digits of precision via mpmath), fixed-point arithmetic, and Horner evaluation. Two configurations are implemented and evaluated: a 32-segment degree-6 approximation at scale $2^{62}$ targeting x86-64, and a 16-segment degree-3 approximation at scale $2^{31}$ (256-byte LUT) targeting ARM Cortex-M3 IoT devices without hardware floating-point unit (FPU). Against the authentic FACCT reference from Falcon's fpr.c, ported verbatim to ARM Cortex-M3 (emulated via QEMU user-mode with arm-linux-gnueabi -mfloat-abi=soft), our implementation achieves a $1.28\times$ median speedup across 30 independent runs (range $1.24\times$ to $1.33\times$), measured with a rigorous anti-noise protocol combining batch measurement, aggressive warm-up, ref/opt interleaving, and percentile filtering (P5-P95). DUDECT timing leakage tests confirm that both the FACCT reference (t-score $\in [0.05, 2.51]$) and our implementation (t-score $\in [1.99, 5.24]$) remain within statistical safety thresholds in the vast majority of runs (FACCT: 30/30; optimized: 27/30). Static instruction-level analysis via objdump disassembly provides deterministic constant-time evidence: zero data-dependent conditional branches, zero FPU instructions, and zero soft-float calls, yielding a branchless fixed-point Horner core; however, the full constant-time claim is limited to the tested compilation target and memory model. To the best of our knowledge, this constitutes the first comparative study of segmented versus global polynomial approximation for fpr_expm_p63 in the FN-DSA context, and the first empirical DUDECT measurement of this function on emulated ARM Cortex-M3 against the authentic FACCT reference. Physical hardware validation on STM32F103 is identified as future work.

Distributed monotone-policy encryption (DPE) lets each user sample and publish its own key, after which anyone can encrypt to a list of published keys under a monotone access policy that determines which coalitions can decrypt. Silent threshold encryption is the $t$-out-of-$N$ special case. What makes the primitive non-trivial is compactness, where the ciphertext stays sublinear in the policy description. Every post-quantum DPE scheme so far settles for selective security, fixing the challenge policy and the corrupted positions before setup, and complexity leveraging cannot close the gap without giving up compactness. The one DPE scheme known in the stronger static model, where the policy and the placement of malicious keys are chosen adaptively, relies on witness encryption (Devadas-Jain-Waters-Wu, Asiacrypt'25). We give the first statically secure DPE schemes from falsifiable lattice assumptions. For DNF policies, ciphertexts are of size $\mathsf{poly}(\lambda, \log N)$, independent of the number and widths of the clauses, and public keys, secret keys, and partial decryptions are of size $\mathsf{poly}(\lambda)$. For $t$-out-of-$N$ threshold policies, ciphertext of size $\tau^6 \cdot \mathsf{poly}(\lambda)$ for $\tau = \min(t^2, N - t)$, improving to $\tau^2 \cdot \mathsf{poly}(\lambda)$ given a common reference string. We prove security under decomposed LWE, and the improved threshold parameters under succinct LWE, in the random oracle model. Our constructions generalize the equivocal encryption framework of Goyal-Yadugiri to policies. We define equivocal DPE, which simulates public keys and partial decryptions and withholds the equivocation trapdoor while releasing the public coins that accompany a ciphertext, and compiles to static DPE with no loss in parameters.

Fully Homomorphic Encryption (FHE) has emerged as one of the key technologies for privacy-preserving computation, enabling arbitrary computation directly on encrypted data. Vectorized FHE schemes, such as Brakerski/Fan--Vercauteren (BFV), Brakerski--Gentry--Vaikuntanathan (BGV), and Cheon--Kim--Kim--Song (CKKS), are typically used in applications dealing with large datasets, for example, confidential database queries and private ML inference. These FHE schemes are based on the computational hardness of Ring Learning with Errors (RLWE) and share a common algebraic foundation: arithmetic over high-dimensional polynomial rings with coefficient moduli spanning hundreds or thousands of bits, far exceeding the native arithmetic capabilities of modern processors. This article surveys the evolution of large-integer arithmetic in RLWE-based FHE libraries, with a focus on the Residue Number System (RNS) techniques used in practically all modern implementations. We give a formal treatment of the two fundamental RNS building blocks --- basis extension and scaling --- that require information about the magnitude of a large value and are therefore incompatible with a purely residue-wise view of arithmetic. We contrast the two principal algorithmic approaches to these operations: the integer-only approach of Bajard, Eynard, Hasan, and Zucca (BEHZ), which tolerates approximation overflows and corrects them with auxiliary redundant moduli, and the floating-point approach of Halevi, Polyakov, and Shoup (HPS). We then show how these primitives compose into the higher-level RNS procedures used across all vectorized RLWE schemes and review how their adoption reshaped the architecture and performance of libraries such as HElib, SEAL, PALISADE/OpenFHE, HEAAN, and Lattigo. We give particular attention to the scaling error inherent in the original Full RNS variant of CKKS, and to the more recent techniques --- reduced-error scaling, composite scaling, and grafting --- that eliminate it or restore flexible, high-precision rescaling from within the residue representation. We also cover GPU-accelerated implementations and close by discussing a renewed, and so far exploratory, interest in positional (non-RNS) representations, raising the question of how such approaches might compare with the Full RNS variants that dominate FHE implementations today.

We present UFOs, a multivariate public-key signature scheme in the Unbalanced Oil and Vinegar (UOV) family. The scheme replaces generic quadratic polynomials with a structured subclass based on Frobenius-type quadratic forms, yielding a compressed public-key representation while retaining the efficient UOV signing procedure. We describe the key-generation, signing, and verification algorithms, and we detail the derivation of the public system from a compact secret description. We discuss security in the standard multivariate setting, including direct algebraic attacks and key-recovery approaches, and we formalize the underlying computational problems induced by the proposed structure. Finally, we report implementation results quantifying the costs of key generation, signing, and verification, as well as the resulting public-key and signature sizes.

This work presents a private instant messaging protocol that leverages the public log layer of blockchains as the message transport layer, while the cryptographic state is kept only by client applications. Thanks to the properties of public ledgers, this approach achieves strong censorship resistance, while also revealing the economic and cryptographic limits of on-chain messaging. Notably, given the transparency of public ledgers, and since reading and writing operations are in most cases outsourced to third-party providers that may be curious, a well-known concern is direct metadata leakage. We address this both at first contact and during the conversation: for first contact, we propose two alternative discovery mechanisms, one based on long-term key encapsulation with trial decryption, the other on a private signaling service backed by trusted hardware. For the ongoing conversation, we show that topic rotation, driven by the off-chain cryptographic state, suffices to prevent topic and conversation linkability. As our main contribution, we provide an in-depth analysis of Verbeth's metadata leakage under different adversarial assumptions for both phases.

Category theory is a mathematical theory of composition, widely used in logic, computing, and physics. Here we apply it to give a theory of secure composition. In particular, we provide a categorical treatment of Canetti's Universal Composability (UC) framework for systems with a static number of parties and sessions, often termed UC for static systems, yielding four benefits. First, we present our results graphically yet retain rigor by applying a standard categorical technique known as string diagrams. In particular, our formulation of the composition theorem can be graphically verified with a short sequence of diagrams, while remaining translatable to equations and amenable to formal verification. Second, categories let us generalize so that our results extend beyond interactive Turing machines to other forms of computation, such as quantum computation or domain-specific languages. Third, categories help us drop some unnecessary restrictions of UC (e.g., our adversary can be a computational network rather than a single Turing machine); we prove equivalence between our variant and the usual UC, showing no expressiveness is lost. Finally, the categorical perspective leads us to identify and correct some minor technical oversights in the standard formulation of simple UC.

Field trace evaluation has emerged as a powerful tool in fully homomorphic encryption, with broad applications ranging from bootstrapping algorithms to privacy-preserving protocols. Recent advances have significantly reduced its noise growth by combining tower-based evaluation strategies with rescaling operations. However, existing analyses rely on uniform noise bounds that fail to capture the actual noise behavior across different coefficients, leading to substantial gaps between theoretical estimates and empirical observations. In this work, we present a refined algebraic analysis of trace evaluation over power-of-two cyclotomics that uncovers structured cancellation effects among noise coefficients induced by subsequent linear operators, in particular the trace mappings of subextensions. We show that, except for the constant term, the variance of each output noise coefficient depends on the 2-adic valuation of its index, yielding bounds that improve upon prior uniform estimates by a factor of $O(\log n)$ both for non-constant coefficients and after a subsequent plaintext-ciphertext multiplication, where $n$ is the ring degree. We further extend our analysis to two typical algorithmic applications of trace evaluation. For ciphertext packing, we derive a non-recursive formulation that admits a cleaner structure and slightly tighter noise estimates. For coefficient extraction, our coefficient-wise analysis improves upon prior uniform variance bounds by factors ranging from $\Theta(n)$ to $\Theta(n^2)$ for non-constant coefficients and by a factor of $O(n)$ after post-multiplication. Experimental results confirm that the observed noise variances follow the coefficient-wise pattern predicted by our analysis and demonstrate pronounced improvements over existing estimates, providing effective guidance for parameter selection and system configuration in practice.

Designated Verifier Signatures (DVS) are an important variant of digital signatures that ensure only a specified verifier can validate a signature, while preserving non-transferability. With the advent of quantum computing, several quantum DVS schemes have been proposed to achieve quantum security. In this paper, we revisit the quantum DVS protocol of Xin et al. [Quantum Information Processing, 2022] and provide a structural cryptanalysis of its design. We show that the scheme admits an existential forgery under a chosen-message attack: given a valid quantum signature on one message, an adversary can efficiently transform it into a valid signature on another message without knowledge of the signer’s private key. To address this weakness, we propose a minimal countermeasure based on QKD-derived keys and quantum one-time pad encryption.

Universal hash functions (UHFs) are basic building blocks in cryptography, making the topic of designing secure, fast UHFs of longstanding interest. This paper presents an exploration of the design space for multivariate UHFs, that is UHFs that involve the evaluation of a multivariate polynomial over a finite field. We focus on two-level designs, wherein a lower-level hash function produces intermediate values that are consumed by a higher-level one, and where both hash functions are based on either univariate or multivariate polynomials. This approach allows designs to benefit from the desirable features of both components and thereby strike new trade-offs between key size, security level, and amenability to optimization techniques. We extend the recent UHF code generation and benchmarking framework of Degabriele et al. (IEEE S&P 2024) to accommodate our multivariate designs (and also to support binary field arithmetic). We then use the framework to study the performance of a large collection of new two-level designs. This is done by first conducting a statistical factor analysis to determine which design features (and combinations of those features) most influence performance, and then using it to identify particular combinations of lower-level and higher-level hash functions offering particularly good performance/security trade-offs. We present new designs for both binary and prime fields, at two different security levels (corresponding to roughly 128 and 256 bits of security). Our best designs have performance that significantly outperforms state-of-the-art UHFs in the research literature and as deployed in mainstream cryptography libraries by up to 25%, resulting in 0.3 cycles/byte for 128-bit binary fields. We expect further gains from optimizations such as vectorization, as our benchmarks rely purely on auto-generated code from the extended framework, while state-of-the-art implementations typically use hand-optimized implementation strategies. We conclude with a brief inquiry into the performance implications of employing our best UHF design in the AEAD and Accordion mode designs currently under consideration for standardization by NIST.

We present the first passive side-channel distinguisher on LESSv2.0, a second-round candidate in NIST’s call for additional post-quantum digital signature schemes. We target the Gaussian elimination at the core of LESS and and present a method to exploit algorithmic leakage arising from the manipulation of sparse versus dense columns. We show that this leakage, while trivially available in non-constant-time implementations, also persists in constant-time implementations and can be exploited using a distinguisher. Concretely, the proposed attack relies only on distinguishing zero-valued computations from random ones that are repeatedly evaluated during the computation, leading to a large attack surface and making the attack robust to noise. Through simulation, we experimentally show that the required number of observed signatures lies between 300 and 2357 depending on the parameter set. This relatively large number is due to the targeted information being inherently noisy, leading to a correlation-based key recovery attack, even with noiseless leakage. Furthermore, we discuss three common countermeasures: first-order masking, shuffling and blinding. Finally, we validate our approach on implementations with and without masking by showing the presence of leakage on a physical target.

Private histogram computation is a fundamental building block for many data analytics tasks, enabling frequency analysis without revealing individual inputs. Existing protocols achieving robustness against malicious clients and servers typically require three servers with limited adversarial tolerance, restricting practicality. In this work, we present Paras, the first two-server protocol for private histogram computation that achieves robustness against collusion between a malicious server and arbitrarily many malicious clients. Paras builds upon distributed point function-based approaches and introduces novel consistency checks leveraging vector oblivious linear evaluation (VOLE) to enforce both input correctness and output integrity. To realize these checks, we design two new cryptographic primitives: (1) aBV, an authenticated bit verification protocol that ensures VOLE committed shares correspond to valid bits, and (2) adIPA, an authenticated double inner product argument that enables secure consistency checks across two different VOLE sessions. These primitives may be of independent interest for other secure computation tasks. We show that Paras is highly efficient and scalable: clients incur minimal cost independent of domain size, while servers achieve low per-client runtime, communication, and storage even at scale. For example, with 8192 clients over a domain of 128 inputs, each server requires only 14 ms runtime and 24 KB communication per client.

Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS; STOC 2015) sample $2^{n/2}$ discrete Gaussians at an arbitrary parameter in $2^{n+o(n)}$ time, and above smoothing in $2^{n/2+o(n)}$ time. They ask whether the latter bound suffices for one sample at an arbitrary parameter. We answer this question affirmatively: for every rank-$n$ lattice $L\subseteq\R^n$ specified by a rational basis and every rational $s^2>0$, we produce one sample from $D_{L,s}$ within statistical distance $\exp(-\Omega(n^3))$ in expected $2^{n/2+o(n)}$ time and $2^{n/2+o(n)}$ space on every execution. The algorithm samples from random superlattices that are smooth at the required scale with constant probability and outputs the first point in $L$; a Gaussian-mass comparison shows that the $2^{n/2}$ samples produced by one ADRS call contain a point of $L$ with inverse-polynomial probability. The factor $2^{n/2}$ is tight in this Gaussian-mass comparison. For every fixed rational $\alpha<1.4697$, the same comparison gives a sub-$2^n$ algorithm for exact CVP on targets satisfying $\dist(y,L)\le\alpha\lambda_1(L)$, without a uniqueness assumption, and an exact-SVP algorithm in $2^{0.7315n+o(n)}$ time.

Video provenance is an important problem on the modern internet. In response, the Coalition for Content Provenance and Authenticity (C2PA) has developed a standard for verifying video and image provenance where cameras sign captured videos with an on-device secret key. Since videos are generally edited and resized before be- ing posted, the C2PA signature from a camera cannot be used as is to verify provenance of published videos. Prior work has developed zero-knowledge techniques for verifying provenance of edited im- ages and videos. In this work, we develop new efficient techniques for producing such zero-knowledge proofs. First, we show how to represent common video edits as matrix multiplications in a form that is particularly friendly for zero-knowledge provers and enables a number of optimizations. Second, we develop a SNARK-friendly video representation, which we call sfvr, that reduces prover work for video editing. Third, we design new efficient methods for incor- porating signed data into a SNARK proof. To evaluate our designs, we built an end-to-end system for proving edits to a signed video. In our end-to-end system, we optimize the NeutronNova folding scheme for high-arity folding. To scale the size of our Neutron- Nova proofs, we implement a “Read-Write Streaming” version of NeutronNova to take advantage of high-performance storage and parallel computing resources. Our system achieves competitive performance and scale relative to prior work.

We present randomized algorithms for the shortest vector problem (SVP). For the $n$-dimensional lattice $\mathcal L$, our algorithms solve SVP in time $2^{0.6039n+o(n)}$ classically and $2^{0.5411n+o(n)}$ quantumly and space $2^{0.5n+o(n)}$, improving the previous best algorithm running in $2^{n+o(n)}$ time and space of Aggarwal, Dadush, Regev, and Stephens-Davidowitz [STOC'15]. Our algorithms heavily use the property of the Hessian of the periodic Gaussian function at the half shortest vector: For a shortest vector $v \in \mathcal L$, the Hessian at $v/2$ has the eigenvector close to $v$, which can be used to recover $v$ using the (preprocessing) bounded distance decoding algorithm. Given the periodicity modulo $\mathcal L$, the candidate midpoints are indexed by the parity classes in $\mathcal L/2\mathcal L$. Our algorithm searches for the class of a shortest vector by estimating the corresponding Hessians using discrete Gaussian samples. We optimize the algorithm using random sublattice cosets and various sampling technique, achieving the final complexity. The optimization techniques may be of independent interest.

Payment Channel Hub (PCH) improves blockchain scalability by enabling off-chain transactions via an untrusted intermediary known as the tumbler. However, existing PCHs either fail to guarantee the unlinkability privacy or rely on inefficient non-interactive zero-knowledge (NIZK) proofs. Recently, Ge et al. proposed Accio, a privacy-preserving PCH that eliminates the need for NIZK proofs. Nevertheless, Accio only supports unidirectional channels which results in high on-chain costs and routing inefficiencies. In this paper, we present Baker, the first bidirectional payment channel hub that operates without NIZK proofs and guarantees unlinkability. Unlike prior PCH solutions that maintain channel balance using a single state, Baker introduces a novel design in which each non-tumbler user maintains two separate pockets to record the channel balance. To ensure payment atomicity, Baker further designs a novel cryptographic primitive named Aggregatable Adaptor Signature (AAS) to enable atomic signature exchanges and signature aggregation. We implement Baker and empirically demonstrate its advantages over state-of-the-art protocols. Compared to BlindHub, which relies on NIZK proofs for privacy, Baker reduces off-chain communication overhead to 0.0036%. Moreover, the off-chain computation overhead of Baker is 7% of that of BlindHub and 40% of TBPChannel. Relative to Accio, Baker incurs only 80% of its on-chain cost and enjoys a 25% higher average transaction success rate.

Neural differential distinguishers are usually compared at a fixed number of labeled samples. However, different input representations may require different numbers of ciphertexts per sample, making fixed-sample comparisons potentially misleading from a cryptanalytic data-complexity perspective. In this paper, we study neural differential distinguishers under a fixed ciphertext budget. We ask whether the available encryption queries should be spent on more independent plaintext bases, or on richer samples containing more ciphertext-difference rows. We introduce a shared-base multi-difference representation in which several input differences are applied around the same plaintext base, and compare it with the standard single-difference baseline and an independent-pair control representation. Experiments on GIFT-64, PRESENT-64, RECTANGLE-64, and SPECK-64/128 show that the single-difference baseline is rarely the best fixed-budget allocation. Adding more difference rows often improves the distinguisher even though it reduces the number of independent training samples. At the same time, the best tested number of rows is not universal: logistic regression often benefits from larger representations, while a multilayer perceptron frequently prefers intermediate values due to sample-starvation and overfitting. We further test several non-adaptive difference sets and observe that the main trend is not tied to a single hand-picked set. The results suggest that the number of differences per sample should be treated as an explicit design parameter in neural differential cryptanalysis, and that fixed-budget evaluation is necessary for comparing richer neural distinguisher inputs fairly.