This document provides a machine-checked Isabelle/HOL formalisation of the modular-arithmetic core of the Neon NTT paper of Becker, Hwang, Kannwischer, Yang, and Yang. We develop parametric theories of Barrett and Montgomery reduction and multiplication; the equivalence of Barrett and Montgomery arithmetic; the doubling- and rounding-Montgomery variants; and correctness and bounds theorems for Neon assembly kernels, against a hand-written model of the word arithmetic underlying the relevant Neon instructions. The development is a directed auto-formalisation: definitions, theorem statements, and proofs were produced by Claude Opus 4.7 and 4.8 using AutoCorrode's LLM-Isabelle integration layers. The human author set the architecture, chose abstractions and proof strategies, often nudged the model toward shorter or cleaner proofs, and controlled which output entered the development. This document is auto-generated from the Isabelle sources through Isabelle’s document preparation system, eliminating drift between prose and formal artifact.

Emerging attacks and applications have motivated the development of transforms that turn a given AE scheme into a committing AE (cAE) one. We give a new transform called UCX with the following attributes: It does not require the starting scheme to be tag based, works for schemes in the broad AE5 framework rather than the limited AE1 one, and preserves both UNAE (Unique Nonce AE) and MRAE (Misuse Resistant AE) security. No prior transform is ``universal'' in the sense of having the combination of all these properties. The use of UCX in place of prior, limited transforms reduces the risk of error and failure in the real world, where choices may be made by application developers and hidden in software libraries. The committing security of UCX is shown in the ideal-cipher model, and its AE5-security in the standard model. To design UCX, we introduce and build a new primitive, that we call a Tweakable Committing Concealer, and that may be of independent interest.

We study error correction in a computationally bounded world, where errors are introduced by an arbitrary polynomial-time adversarial channel. Recent works construct seeded codes in this model, where the encoding and decoding procedure share a public random seed. They achieve significantly better tradeoffs between rate and error tolerance than what is possible information theoretically for unique decoding, essentially matching the parameters of the best known efficiently list-decodable codes. Over the binary alphabet, however, this is still well short of the optimal Shannon capacity with rate $R \approx 1 - H_2(p)$ for a $p < 1/4$ fraction of errors. Even heuristic constructions meeting this target were not previously known. We make progress towards this goal. - $\textbf{Secret-Key Codes.}$ We first study secret-key codes, where the encoder and decoder share a secret key hidden from the adversarial channel. Lipton (STACS '94) constructed one-time secure secret-key codes achieving Shannon capacity in this setting, but it was unknown whether one can get CPA (resp. CCA) security where the adversary may query an encoding oracle (resp. also a decoding oracle). We construct CCA-secure secret-key codes achieving Shannon capacity via pseudorandom codes (PRCs). - $\textbf{Seeded Codes (Heuristic).}$ We can heuristically upgrade the resulting secret-key codes to seeded codes by publishing an obfuscation of the encoding/decoding procedures with a hard-coded secret key as a seed. Security holds in the ideal obfuscation model. - $\textbf{Public-key Codes.}$ We also consider public-key codes, where the decoder has a secret key and the encoder has the corresponding public key. We construct such CPA-secure public-key codes achieving Shannon capacity with unique decoding for $p < 1/4$ errors, and list decoding all the way to $p < 1/2$ errors, assuming PRCs and the subexponential security of standard crypto assumptions (e.g., LWE or DDH or QR or DCR). We also show how to get CCA security in the random oracle model. Our secret-key and public-key codes meeting Shannon capacity are also simultaneously pseudorandom codes.

Depth-robust directed acyclic graphs (DAGs) are an important combinatorial primitive in cryptography, with applications to memory-hard functions, proofs of space, and proofs of sequential work. These applications require node depth-robustness, yet constructing sparse graphs with strong concrete guarantees remains a longstanding challenge. By contrast, edge depth-robust graphs are easier to construct explicitly and achieve better parameters, motivating the problem of efficiently transforming edge-depth-robust graphs into node-depth-robust graphs. We give a new and substantially more efficient transformation from edge-depth-robust graphs to node-depth-robust graphs. We give a new and substantially more efficient transformation from edge-depth-robust graphs to node-depth-robust graphs. Prior work of Blocki and Cinkoske (ITCS 2021) gave a general transformation by replacing each node with an ST-robust graph, resulting in extraordinarily large overhead and relying on non-explicit components. In contrast, our transformation replaces each node with a single superconcentrator rather than an ST-robust graph, yielding an explicit construction whenever the input graph is explicit, with dramatically improved concrete efficiency. Formally, given an $(e,d)$-edge-depth-robust graph $G$ with $N$ nodes and $m$ edges, our transformation generates a graph $G'=Transform(G_N)$ with $N' = O(m)$ nodes, constant indegree, and $(e/3,\, 2d-1)$-node depth-robustness. We also show that the transformation preserves fractional depth-robustness. Moreover, when $m=\omega(N)$, we show that our transformation can amplify depth --- overcoming a key limitation of prior work. In particular, for any parameter $d'$, we can obtain a constant-indegree graph $G'$ with $N' = O(m+d'N)$ nodes and $(e/3,\, (d-e)d')$-node depth-robustness, yielding asymptotically tighter results in the important setting where $m = \omega(N)$ and $e \geq d$ by setting $d' \sim m/N$. As an application, We provide a novel analysis of Schnitger's edge-depth-robust graph construction (FOCS 1983). We show that the graph $G_n$, which has $N=2^{n+1}-1$ nodes and $m \leq n2^{n}$ edges, is $(e,2d-1)$-edge-depth robust for all $e + d \leq 2^n$. Applying our transformation yields an explicit DAG on $N'$ nodes with maximum indegree $2$ and depth-robustness parameters $e = \Omega(N'/\log N')$ and $d = \Omega(N')$, matching the best known asymptotic trade-offs—even compared with non-explicit constructions—while improving the best previously known concrete ed-product lower bound by a multiplicative factor of 6.6.

We introduce WayFinder, a framework for generalizing the Delfs-Galbraith and SuperSolver algorithms for the supersingular isogeny problem. Our framework extends the search for elliptic curves with an orientation by an order containing $\mathbb{Z}[\ell \sqrt{-p}]$ to more general orders, and we derive a cost model for such generalisations. Our cost model not only works in a more general context, but also provides more accurate predictions when applied to SuperSolver. We instantiate WayFinder for orders containing $\mathbb{Z}[\ell_1\sqrt{-\ell_2p}]$ where $\ell_i$ are $1$ or primes such that the modular curve $X_0(\ell_2)$ has genus $0$. We then introduce a low-storage algorithm for computing an isogeny between two oriented supersingular elliptic curves, even when the curves are oriented by distinct orders. Together, these provide an algorithm that improves on the state of the art for solving the isogeny problem, and a cost model with potential applications to parameter selection in isogeny-based cryptography.

We study frequency estimation in the shuffle model of differential privacy under poisoning attacks, where corrupted users may deviate from the local randomizer to inject crafted in-domain messages. Existing shuffle-model protocols face a core tension: achieving low estimation error relies on flexible multi-message noise generation, which can amplify poisoning influence once messages are anonymized by shuffling. To address this tension, we propose a symmetric binomial-sum noise distribution (i.e., $\mathrm{Bin}(n/2,p) + \mathrm{Bin}(n/2,1-p)$), which preserves high accuracy while limiting the impact of crafted in-domain messages. We realize this distribution via preprocessing-guided noise generation, which routes a balanced collection of mode flags through the shuffler so that each user receives a randomly assigned mode flag that fixes their noise-sampling behavior prior to shuffling. For binary estimation, our protocol requires a single Bernoulli trial per user and at most $2$ messages per user ($1.5$ on average), while bounding the worst-case poisoning influence of a single corrupted user by $O(1/n)$. We extend the protocol to histograms, including large domains via hashing, and provide formal privacy, accuracy, and robustness guarantees. Experiments on real datasets show that our protocols remain resilient under poisoning and reduce MAE by up to nearly $2\times$ over the strongest baseline at comparable per-user communication on small-domain workloads, and stay on par with it on large domains.

In this work, we construct (stateful) leakage-resilient circuits (LRCs) secure against bounded-output-length leakage functions computable by \(\mathsf{NC}^1\) circuits under the mild worst-case assumption \(\mathsf{NC}^1 \subsetneq \oplus\mathsf{L}/\mathsf{poly}\), without relying on any leak-free hardware components, thereby resolving the open problem left by Bogdanov, Ishai, and Srinivasan (CRYPTO 2019; Journal of Cryptology, 2021) and Wang (CRYPTO 2025). Concretely, we first construct a leakage-tolerant circuit with succinct setup (sAI-LTC) secure against 2-adaptive \(\mathsf{NC}^1\) leakage, and then generically combine it with a 2-adaptive leakage-resilient composable encoding scheme to obtain the desired LRC. We further give a direct non-black-box instantiation that optimizes the compiled circuit size at the cost of a slightly larger setup, matching the circuit size of Wang's construction that relies on leak-free hardware while using a more compact setup. Finally, we show that our sAI-LTC generically implies a fine-grained multi-theorem non-interactive proof system for all \(\mathsf{NP}\), with compact common reference strings, perfect soundness, and multi-theorem zero-knowledge with offline simulation against \(\mathsf{NC}^1\) adversaries.

Shor demonstrated that the discrete logarithm problem in the multiplicative roup $\mathbb{Z}_{p}^{*}$, where $p$ is an odd prime, can be solved fficiently using a period-finding algorithm based on the quantum Fourier transform. In this paper, we propose a quantum-classical algorithm based on algebraic properties that do not rely on periodicity. Specifically, we show that the hardcore predicate for the discrete logarithm problem, which was introduced by Blum and Micali, can be reduced, using the swap test, to the problem of distinguishing between two Bernoulli distributions. In our algorithm, although the swap test is used as a quantum subroutine, most of the computation is performed classically. Moreover, the algorithm does not require the quantum Fourier transform.

Classically testing for the presence of anti-commuting operators on a quantum device is a critical tool underpinning recent progress in classical verification of quantum computation. While such tests can be based on cryptographic assumptions, known constructions rely on highly structured assumptions, e.g. trapdoor claw-free functions. In this work, we seek to explain this state of affairs by constructing strong cryptography from (certain forms of) classical tests of anti-commutation. In particular, we formulate the notion of a test of non-commutation (ToNC), an interactive protocol between a quantum prover and classical verifier in which the prover's final-round response is obtained by measuring one of two binary observables 𝑃₀, 𝑃₁ depending on the verifier's challenge bit 𝑐. We prove that, for a broad range of parameters, ToNC implies classical-communication key agreement (KA), and ToNC combined with one-way functions implies oblivious transfer (OT). Along the way, we develop tools for and provide the first known results on hardness amplification for post-quantum KA and OT, where communication is classical but adversaries may be quantum. In particular, we prove the following results of independent interest. - Post-quantum hard-core measure theorem: For any efficiently sampleable high-min-entropy distribution 𝐷 over pairs (𝑥,𝑏) such that quantum circuits have advantage at most 𝛿 in predicting 𝑏 from 𝑥, there exists a sub-distribution 𝑀≼𝐷 of density 1-𝛿 on which 𝑏 is nearly optimally quantum-hard to predict. - Post-quantum interactive XOR lemma: Given any classically-interactive protocol, if quantum adversaries have advantage at most 𝛿 in guessing a private challenger bit 𝑏, then two sequential repetitions reduce the advantage for predicting the XOR of the challenger bits 𝑏₁⊕𝑏₂ to at most 𝛿² + negl(𝜆).

Blockchain consensus protocols, also known as BFT state-machine replication, enable a system of $n$ players to decide an ever-growing chain of blocks. We consider partial synchrony: after an unknown time GST, messages sent by honest players are delivered within an unknown actual delay $\delta$, and a known bound $\Delta$ satisfies $\delta \leq \Delta$. This setting imposes $t<n/3$ corruptions. We study leader-based consensus, a class with the smallest known latency metrics when sufficiently many designated leaders behave honestly. We consider the mainstream metric of {expected latency in the view-based sense:} for a transaction known to all honest players having entered a post-GST iteration, this is the expected time until that transaction appears in a decided block, under independent random leaders. We introduce Hamster, a rotating-leader consensus protocol, which reduces this expected latency to $\Delta+4\delta$, down from the previous $1.5\Delta+3.5\delta$ bound achieved by Simplex (Chan-Pass, TCC'23) for the same view-based metric. Hamster also brings this latency further down to $\Delta+3.5\delta$ for adversaries that do not get publicly caught equivocating. The main technical novelty is a certificate of exclusivity for a block $B$. It is shown by the next leader as evidence that players can safely vote for a child of $B$. A certificate of exclusivity is an interpolation between a quorum certificate and a timeout certificate, in that it is formed from a mix of votes for a unique block $B$ and complaint votes, proving that $B$ is the only non-dummy block that can still obtain a decision certificate for that iteration. The other novelty of Hamster is the use of {overlapping iterations: after a process has supported a newer proposal, the protocol may still allow it to support a safe proposal of an earlier iteration}. This overlap is what allows old honest proposals to be decided in time despite players advancing iterations faster. We also analyze another metric, called the {pessimistic block proposal time}, which is the time during which a bad leader can delay the proposal of a transaction in a block which will be decided. Hamster achieves a pessimistic block proposal time of $2\Delta+2\delta$, refined to $2\Delta+\delta$ for leaders not caught equivocating, down from $3\Delta+\delta$ for Simplex.

In addition to anonymity and traceability, which are the primary security properties of group signatures, non‑frameability is also defined (Bellare-Shi-Zhang, CT-RSA 2005). This property guarantees that even an adversary colluding with all authorities (the opener and the issuer) cannot produce a signature that frames an honest user, and it is regarded as a security notion that protects users. In this short note, we introduce a new perspective on non-frameability, namely that it can also protect the authorities, and we examine its significance in the context of anonymous auctions, a well‑known application of group signatures. We show that non-frameability serves as an effective countermeasure against situations in which a winning bidder falsely claims not to have placed a bid and accuses the organizer of forgery.

Federated fine-tuning of Large Language Models via Low Rank Adaptation (LoRA) faces a critical privacy-efficiency trade-off: low-rank factors can leak sensitive data, yet standard secure aggregation is restricted to linear operations. Existing solutions for aggregating matrix products (e.g., $\mathbf{B}_i \mathbf{A}_i$) either sacrifice exactness, depend on a trusted third party, or incur prohibitive costs at scale. We present SecLoRA, the first decentralized framework achieving exact aggregation of LoRA updates with linear communication complexity. The core of SecLoRA is a novel cryptographic primitive: Pairwise Composable Multi-Client Functional Encryption (PC-DMCFE). Unlike traditional functional encryption, which treats ciphertext recombination as an attack, the dual-encryption architecture of PC-DMCFE ($\mathsf{Enc}_A, \mathsf{Enc}_B$) is intentionally designed to harness this property. It allows any ciphertexts $\mathsf{ct}_A$ and $\mathsf{ct}_B$ to be arbitrarily paired and evaluated via a functional key to reveal their inner product. This unique property enables secure and decentralized aggregation of matrix products without losing LoRA's linear communication advantages. Furthermore, SecLoRA ensures round-isolated decryption to prevent temporal leakage without extra interaction. Evaluation shows that SecLoRA is practical for cross-silo deployments.

A private information retrieval (PIR) protocol enables a client to retrieve a bit from an $N$ bit database replicated among $k$ servers in such a way that each server learns no information about the retrieved bit. Modern PIR protocols with information-theoretic privacy (Efremenko, SICOMP, 2012; Dvir and Gopi, STOC, 2015; Ghasemi et al., STOC, 25) are based on matching vectors over a composite number $m$. To construct a PIR protocol from the matching vectors, these protocols use a decoding polynomial, a sparse polynomial that returns a non-zero value on 1 and returns zero on a certain set implied by the matching vectors. Beimel et al. (CCC, 2012) abstracted the properties required by the transformation computed by the decoding polynomial, defining the notion of share conversion. In such a conversion, a set of parties is given shares of a secret in one secret-sharing scheme, and each party locally computes a new share (without any communication) such that the new shares are shares in a second secret-sharing scheme of a related secret. Beimel et al. showed that share conversion can replace the decoding polynomial in the PIR protocol of Efremenko and constructed a share conversion from the ring $\mathbb{Z}_6$ to the field $\mathbb{F}_{2^2}$. This share conversion cannot be computed by a decoding polynomial, as decoding polynomials convert shares from a ring $\mathbb{Z}_m$ to a finite field of characteristic $p$ such that $p$ does not divide $m$. Alon et al. (TCC, 2025) simplified and generalized the PIR protocols of Dvir and Gopi and Ghasemi et al., using share conversion; however, in this protocol, the share conversion is from a ring $\mathbb{Z}_m$ to a finite field of characteristic $p$ such that $p$ does not divide $m$. In this paper, we study the power of share conversions. Our main result proves that if there is a $k$-party share conversion from a ring $\mathbb{Z}_m$ to a finite field of characteristic $p$ such that $p$ does not divide $m$, then there is a $k$ sparse decoding polynomial from a ring $\mathbb{Z}_m$ to a finite field of characteristic $p$. This result implies that using share conversion in the protocol of Alon et al. can only improve the communication complexity by a constant factor. In addition, we show that if there is a $k$-party share conversion from a ring $\mathbb{Z}_m$ to a finite field, where $m$ is a product of $r$ distinct primes, then $k\geq r+1$, i.e., the number of servers in the resulting PIR protocols using the appropriate matching vectors is at least $r+1$. A similar result was recently proved by Ghasemi and Kopparty (ITCS 26); our lower bound also applies to the case in which the characteristic of the field divides $m$.

Quantum cryptography is a rapidly developing area which leverages quantum information to accomplish classically impossible tasks. In many of these protocols, quantum states are used as long-term cryptographic keys, relying on the quantum no-cloning theorem to ensure that the keys cannot be copied by an adversary. Unfortunately, quantum state tend to decohere, and hence, persistent quantum memory is and will remain one of the most valuable and challenging resources for quantum computers. As such, it will be important to minimize the extent to which our protocols use persistent quantum memory. In this work, we consider the case of one-shot signatures (OSS), and more general quantum signing tokens, important uncloneable primitives where quantum signing keys allow for signing a single message but not two. Very recently, the first OSS scheme was constructed unconditionally in a classical oracle model as well as in the standard model under cryptographic assumptions (Shmueli and Zhandry, CRYPTO 2025). We observe that the quantum memory required for these protocols is a large polynomial (in the security parameter). The main contribution of this work is to significantly decrease the quantum secret key size, in some cases achieving the asymptotically optimal size. One of our schemes guarantees perfect correctness and the other one admits a parallel signing algorithm for long messages. We also achieve strong signature incompressibility, which implies a public-key quantum fire scheme (Çakan, Goyal and Shmueli, QCrypt 2025) with perfect correctness. During the course of this work, we develop novel techniques for proving the security of cryptosystems using coset states, one of the main tools used in uncloneable cryptography.

Homomorphic Advanced Encryption Standard (AES) evaluation refers to evaluating the AES circuit with a fully homomorphic encryption (FHE)-encrypted secret key. Applications include in particular Transciphering, which converts AES-encrypted data into FHE ciphertexts without exposing the secret key. Existing homomorphic AES evaluations show a clear separation between latency-oriented solutions and throughput-oriented solutions. CKKS-based methods exploit massive SIMD parallelism and focus on throughput by processing many AES blocks in parallel. They are hardly suitable for latency-critical settings. In contrast, TFHE-based methods process a small number of blocks efficiently. They are preferable for low-latency settings, but provide very limited throughput. In this work, we show that AES-CKKS evaluation can achieve both interactive latency and high throughput. Our first variant is optimized for latency and decrypts a single AES block in only 26ms on an NVIDIA RTX-5090. This is more than 6× faster than recent TFHE-based state-of-the-art approaches; further, an extension of it processes 4 AES blocks at once in 29ms. Our second variant is based on a new embedding of $\textrm{GF}(16)$, the finite field with 16 elements, into CKKS message space. It is optimized for throughput and processes up to 2048 AES blocks at once, achieving 238KB/s throughput (a more than 3.41× improvement over the state-of-the-art CKKS-based approaches), while maintaining latency comparable to TFHE-based methods. To the best of our knowledge, this is the first AES-FHE evaluation algorithm combining good latency and throughput properties, bringing homomorphic outsourcing with AES within reach of real-time applications on constrained devices. Our main ingredients are redundant structures that maximize SIMD utilization, improved algorithms for the SubBytes step (one of them being based on inversion in $\textrm{GF}(256)$ using CKKS), fusion of linear layers into bootstrapping, and carefully crafted FHE parameters.

We construct preimage sampleable function families on $q$-ary lattices [Gentry–Peikert–Vaikuntanathan, STOC'08] for which preimage sampling reduces to sampling uniform points of unitriangular lattices from simple polytopes: affine linear transforms on the $\ell_1$ and $\ell_\infty$ balls, and a scaled intersection thereof. We build the necessary samplers by adapting an algorithm of [Kannan–Vempala, STOC'97] and improving its analysis. This sampling requires only uniform bits and affine linear transforms on the uniform distribution on $[0,1]$. The collision resistance of these families relies on the short integer solutions problem [Ajtai, STOC'96] in various $\ell_p$ norms. Considering the Lee metric as the $\ell_1$ norm in $q$-ary lattices, we answer an open question to construct such families for the Lee metric [Hörmann–van Woerden, CRYPTO'24]. We also answer an open question of [Plançon--Prest, PKC'21] by sampling from polytopes with inradius smaller by a factor almost square root in the lattice rank. We provide a generic framework for constructing preimage sampleable function families from polytopes with sufficient conditions for realising it. While our parameters are worse than prior discrete Gaussian based constructions, such distributions are challenging from a physical security perspective.

Overbroad computer crime, intellectual property, and other laws are well known to create legal risks that can discourage essential research. Notable examples include the US Computer Fraud and Abuse Act and the UK Computer Misuse Act. Because such laws fail to distinguish malicious hacking from good-faith testing and research, researchers face serious legal risks for public-interest research activity like identifying software or hardware vulnerabilities or scraping data. Despite the research community's broad awareness of these risks, our understanding of their practical impacts is limited, as most of the community's knowledge comes from anecdotal evidence rather than systematic study. We conduct the first qualitative study focused on researchers' lived experiences, to empirically document the *impacts of legal risks and threats* on research and researchers*, and *how researchers navigate legal risk situations*. Our study engages two participant groups: researchers with legal-risk experiences in the UK or the US ($N_R=36$), who discuss 130 projects and incidents spanning over three decades, and professionals that offer support to researchers navigating legal risks ($N_S=8$), who have collectively supported thousands of researchers. We thus provide an unprecedented big-picture view of researchers' experiences with legal risks. We synthesise actionable strategies for researchers, and our findings provide evidence to support policy reform.

We show new constructions for pseudorandom quantum states (PRS) and pseudorandom function-like quantum state (PRFS) generators satisfying scalability, which means the security parameter can be much larger than the number of qubits, quantum accessibility, which means the adversary can provide quantum input, and adaptivity, which means the adversary can query it adaptively. We present an isometric procedure to prepare quantum states that can be arbitrarily random (i.e., the trace distance from the Haar-random state can be arbitrarily small for the true random case, or the distinguishing advantage can be arbitrarily small for the pseudorandom case). This naturally gives the first construction for scalable, quantum-accessible, and adaptive PRFS assuming quantum-secure one-way functions. Compared to prior PRFS works, we use a stronger definition of quantum accessibility in which the adversary can be ancilla-assisted, i.e., the input state may not be pure and could be entangled with other quantum registers. Thus, our result also gives the first (fully) quantum-accessible PRFS. Our PRFS construction implies various primitives, including long-input PRFS, short-input PRFS, short-output PRFS, non-adaptive PRFS, and classically-accessible adaptive PRFS. This new construction may be helpful in simplifying the microcrypt zoo.

This work proposes StakeNote, a distributed ledger protocol that combines Proof-of-Stake (PoS) with privacy and anonymity preserving payments. The protocol combines Ouroboros Praos, a provably secure PoS protocol, with CryptoNote, a privacy-preserving payment system based on ring signatures which has been widely used in practice. We prove that StakeNote inherits the security guarantees of Ouroboros Praos and the privacy guarantees of CryptoNote and we demonstrate its practicality via a proof of concept implementation, where block creation requires less than 25 ms and eligibility proofs are approx. 3 KB for anonymity sets of size 16. Finally, we discuss heuristic enhancements that potentially increase privacy and enable dynamic participation.

End-to-end deep-learning side-channel attacks on public-key implementations have recently become possible even for million-sample traces. However, existing methods require large computational resources and extract only partial key shares, which means that dedicated post-processing is required to turn detected leakage into demonstrations of successful key recovery attacks. We present an end-to-end sequence-to-sequence prediction approach to recover complete 256-bit key shares from single raw traces on the SCAAML ECC datasets recently studied by Bursztein et al (TCHES 2024). Our solution combines aggressive trace compression for dimensionality reduction with a 1-D U-Net trained using Connectionist Temporal Classification loss. The key idea is to decouple detecting leakage from mapping each leakage site to the correct part of the secret: the network outputs an annotated map of the trace marking likely leakage sites, and a greedy decoder reconstructs the ordered key bits from that map. Using synthetic tasks, we show that this division of labor circumvents a fundamental problem that causes neural network architectures and training methods commonly used in side-channel analysis to struggle with massive multi-target or misaligned extraction tasks. As a result, we are able to train a single extractor that achieves high accuracy on all four SCAAML ECC datasets in a single training run that takes minutes on a single GPU. The resulting extractors are robust, essentially maintaining their performance under large misalignment (we empirically tested rotations up to \(61\%\) of trace length), while degrading gracefully under a variety of trace corruptions, and even time reversal. They transfer across key shares and datasets with little degradation and no retraining. The U-Net outputs also yield prediction maps that localize leakage along the trace prior to decoding.

Cryptographic signatures play an integral part in ensuring authenticity and integrity in digital systems. Their security crucially relies on the secrecy of the signing key, since knowledge of this key enables an adversary to generate valid signatures on any message. Once a signing key is compromised, the standard countermeasure is to revoke the corresponding public key and to invalidate all signatures produced for this key. However, with this approach even legitimate signatures created by the honest signer would retroactively lose their validity. In this work, we initiate the formal study of a new approach - Signatures with Post-Compromise Accountability (SPCA) - which provides security guarantees even after the secret key was compromised. This notion effectively introduces a grace period for the legitimate key owner, during which the validity of honestly generated signatures is preserved despite the adversary’s knowledge of the secret key. We formally define SPCA and its security guarantees, and present two constructions achieving this notion. Our first construction generalizes the signature-in-signature approach of Błaśkiewicz et al. (ESORICS '21), where an inner signature is embedded into the randomness of an outer signature. This construction, however, requires revealing the signing secret key during revalidation. Our second construction overcomes this limitation by enabling revalidation without disclosing the secret key, yielding stronger security guarantees.

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

In the line of the SPDZ protocol for secure multi-party computation, the generation of Beaver triples is the most expensive task. Silentium (Rieder, PrivCryp 25) is the implementation of a Pseudorandom Correlation Generator (PCG) for Beaver triples (Boyle et al., Crypto 20). PCGs focus on low-communication costs., e.g. their PCG reduces the communication by one order of magnitude compared to protocols in MP-SPDZ. Silentium is an implementation of their PCG, achieving similar running times than MP-SPDZ. We make three theoretical contributions to Silentium, including an implementation. First, we make a practical proposal how to generate Beaver triples over binary fields F2λ, which extends the previous setting over prime fields. For this, we propose a suitable instantiation of the Number Theoretic Transform. Second, we show how to use the binary triples to construct what we call a Beaver triple expansion scheme, that is we construct a scheme that expands a small batch of Beaver triples into a large batch of Beaver triples, in the sense of recently established oblivious transfer extension schemes. This feature enables an efficient preprocessing stage for the PCG, closing a practical issue of Silentium. Finally, we provide details about the Silentium implementation, by clearing a technical bug in the initial theoretical protocol description.

Functional bootstrapping has made discrete computation practical in the Cheon-Kim-Kim-Song (CKKS) scheme, but it fuses four distinct tasks - lookup table (LUT) evaluation, modular reduction, noise cleaning, and ciphertext refreshing - into a single rigid pipeline. As a consequence, a generic LUT over an alphabet of size $t$ costs multiplicative depth proportional to $\log_2 t$ and consumes a large share of the modulus budget during a fixed bootstrapping procedure, invoked each time a LUT evaluation or modular reduction is needed. We show that this pipeline can be unbundled by changing the representation, rather than optimizing the bootstrapping, through block encodings. A finite-alphabet value is carried across several CKKS slots whose coordinates form a basis of functions on the alphabet, typically the characters of a finite abelian group. In such a basis, every LUT is an affine plaintext map evaluated in a single multiplicative level, with depth independent of $t$. Modular reduction comes for free: a block encoding cannot represent anything but a residue, so arithmetic modulo $t$ is native. Because the encoded values lie on the unit circle, noise growth is independent of the alphabet size $t$. In the worst case, it matches the noise growth of standard discrete CKKS on the smallest alphabet $\mathbb Z_2$, and in more typical workloads it is linear in the number of operations, exponentially better than discrete CKKS at every $t > 2$. Noise cleaning becomes a constant-depth procedure of at most four levels, because the alphabet-dependent part is an LUT and only a fixed-degree-3 smoothstep is nonlinear. Finally, since LUTs are no longer part of the bootstrapping, refreshing reverts to its classical role as a maintenance operation invoked only to regain multiplicative depth. Any CKKS bootstrapping can be used, rather than a constrained and expensive pipeline. We instantiate the framework with several block encodings that make modular addition, modular multiplication, xor or min/max possible with a single CKKS multiplication. We use them to build CRT arithmetic over large composite moduli, and finite-state prefix scans for radix addition and subtraction in depth $4 + \lceil\log_2 d\rceil$ and for equality and comparison in depth $3 + \lceil\log_2 d\rceil$ for $d$ radix digits. For example, a 256-bit CRT modular addition or multiplication consumes a single multiplicative level and has a latency of 4.7 ms on a single thread.

We present a post-quantum commitment scheme based on kernel-tagged punctured Richelot isogeny walks on superspecial genus-2 Jacobians. The puncturing rule skips every step landing in the product locus, detected by I10 = 0, so honest executions remain in the Jacobian locus and avoid the entry point of known product-locus attacks. Each opening is encoded as a deterministic non-backtracking walk together with a kernel tag recording its action on a small public auxiliary torsion basis. The tag is verified as part of the opening and is kept explicit throughout the security analysis. In particular, scalar-related collisions force equality of the ordered kernel sequence and hence equality of the tag, so any nontrivial binding attack yields a short non-scalar endomorphism. Using spectral bounds for the Richelot graph, we show that puncturing preserves rapid mixing for logarithmic walk lengths, which yields statistical hiding for the tagged punctured scheme. We therefore reduce binding to the Short Richelot Endomorphism Problem (SREP), relate SREP to the One-Endomorphism Problem and, under a standard KLPT2 -style heuristic, to the endomorphism-ring problem. A SageMath prototype based on (2, 2)-Kummer isogenies indicates practical performance at standard security levels.

Finding a nontrivial endomorphism of a given supersingular elliptic curve is a hardness assumption of isogeny-based cryptography. We prove the reduction from it to the problem of finding a splitting of a given principally polarized abelian surface. By using this new reduction, we also prove the heuristic equivalence of the splitting problem with a degree restriction and the endomorphism ring problem in dimension two.

Batched encryption (BE) has emerged as a novel public-key cryptographic paradigm that enables the efficient decryption of a designated batch of $B$ ciphertexts simultaneously. By incorporating threshold decryption capabilities into this framework, batched threshold encryption (BTE) further decentralizes the decryption process. While both BE and BTE serve as highly effective solutions for mitigating Miner Extractable Value (MEV) attacks in blockchain networks by providing robust mempool privacy, ciphertext integrity, and communication efficiency, they still suffer from heavy computational overhead during the ciphertext decryption phase. In this paper, we address this computational bottleneck by introducing a novel framework that delegates the heavy decryption workloads to an untrusted cloud server while enabling verifiability of the outsourced computations. To achieve this, we first propose an outsourced batched identity-based encryption (O-BIBE) scheme by integrating outsourcing functionalities into the conventional BIBE paradigm, accompanied by a rigorous security proof. We then construct a verifiable outsourced batched encryption (VOBE) scheme by strategically combining O-BIBE with other core cryptographic building blocks and formally prove its security. To eliminate the single point of failure and enhance threshold resiliency, we extend our framework to the threshold setting by developing an outsourced threshold batched identity-based encryption (O-TBIBE) scheme. Building upon this, we propose a verifiable outsourced batched threshold encryption (VOBTE) scheme, which successfully achieves decentralized threshold resilience. Our proposed VOBE and VOBTE schemes are the first to concurrently guarantee ciphertext integrity and mempool privacy against sophisticated blockchain attacks, while significantly reducing decryption costs via efficient and verifiable outsourcing.

We present Grand Danois, a new post-quantum multilinear polynomial commitment scheme from lattices for polynomials over $\mathbb{F}_q$ that achieves polylogarithmic $O(\lambda \ell)$ verification complexity and proof sizes. We build on the general approach introduced in Hachi (ePrint 2026/156) with three key changes. First, we switch to the vanishing Short Integer Solution (vSIS) assumption to obtain structured public parameters for our commitment scheme and utilize this structure to design a sumcheck protocol amenable to succinct verification. Second, rather than casting ring relations into $\mathbb{F}_{q^k}[X]$, via the residual technique of Hachi, we express multiplication by fixed $\mathcal{R}_q$ elements through its rotation matrix, which lets the verifier fold each row of the constraint matrix in time linear rather than quadratic in the ring degree $d$. Third, we modify the quadratic relation used in Hachi and Greyhound (CRYPTO 2024) so that it becomes compatible with proving norm bounds using Johnson-Lindenstrauss projections. This is achieved through an adaptation of the structured projection strategy introduced in RoK and Roll (ASIACRYPT 2025). This has the benefit for communication complexity in that proving norm bounds and correct polynomial evaluation are integrated into a single protocol, reducing the number of commitments sent by the prover. Furthermore, we impose additional structure on our random projections to reduce the witness size even more aggressively during each round of recursion without sacrificing verification complexity. Under the vSIS assumption, our construction yields an estimated proof size of roughly $80$ KB for $2^{32}$-size polynomial evaluations.

Blockchain mempool transparency fuels Maximal Extractable Value (MEV), where attackers can front-run, back-run, and reorder transactions as soon as they appear. Encrypted mempools aim to delay the release of information until block commitment, yet nearly all existing designs rely on a trusted decryption committee. This creates two structural problems. First, committee members hold decryption material by design, so a colluding threshold can reconstruct the decryption key and learn transactions before block commitment. Second, once such a committee becomes malicious, honest parties have no easy in-protocol way to recover: restoring privacy for future epochs requires an external intervention such as a hard fork that replaces the committee and rotates the long-lived cryptographic material. In this work, we ask whether encrypted mempools can instead use proof-of-work to realize an open and recoverable decryption committee. We then introduce DecryptChain, a permissionless proof-of-work encrypted mempool in which decryption authority is not assigned to persistent identities or long-lived key shares. Instead, decryption is continuously re-contested through public computational work. Even if an adversary successfully breaches one epoch, it gains no reusable secret for future epochs; honest parties can always re-enter and recover the decryption process by contributing sufficient work. DecryptChain decouples block production from decryption, enabling it to operate as a Layer-2 timely decryption service on any underlying blockchain while preserving eventual decryption for committed on-chain encrypted transactions.

The communication complexity of unconditionally Secure Multi-Party Computation (MPC) protocols has been studied by a series of works in the honest-majority setting. For evaluating an arbitrary Boolean circuit, the state-of-the-art MPC protocol by Goyal et al. (Crypto 2021 and Crypto 2022) achieves the total communication cost of $O(\log n)$ bits per gate, where $n$ is the number of parties. In this work, we present the first unconditional MPC protocol for any Boolean circuit with communication of $O(1)$ bits per gate. We first construct an unconditionally secure protocol in the presence of semi-honest adversaries, and then strengthen it to guarantee security against malicious adversaries with the same communication efficiency.

This paper proposes a systematic approach to compute cryptanalytic properties of arbitrary Mealy machines or S-functions. Based on the geometric approach to cryptanalysis, we provide a uniform formula for any cryptanalytic property of such a function, as long as the property is compatible with the way its input and output are split into chunks. Examples include linear, (quasi) differential, (ultrametric) integral, differential-linear, and boomerang properties. To illustrate our results, we compute these properties for several important examples, including modular additions, the Chi- and ChiChi-functions, and the SHA-1 step function. As proof-of-concept applications, we construct a boomerang distinguisher for the Subterranean permutation, and show how to compute the correlations of conditional linear approximations in partitioning-based differential-linear attacks more accurately. Our results also lead to a new approach to compute the algebraic normal form of the inverse of the Chi-function.

In their seminal work, Goldreich, Goldwasser, and Micali [CRYPTO 1984] constructed a pseudorandom function (PRF) using a black-box access to a pseudorandom generator (PRG). When combined with Levin's domain extension technique, the GGM construction invokes the PRG $\omega(\log n)$ times, where $n$ denotes the input length to the PRG. To this day, no black-box construction achieving fewer calls is known. Recently, Beimel, Malkin, and Mazor [CRYPTO 2024] showed that for a certain family of constructions, which they termed \emph{tree constructions}, the GGM construction is optimal. However, the basic challenge of whether a PRF can be built with just \emph{one invocation} of the PRG still remains open. In this work, we consider fully black-box constructions of PRFs from PRGs, where both the construction and the reduction are required to be black-box, and the number of interactions the reduction makes with the adversary is independent of the number of oracle calls the adversary makes to its underlying function within each interaction. Our main result shows that no such construction can have $o(n/\log n)$ and $o(\mathsf{in}/\log\mathsf{in})$ \emph{non-adaptive} calls to the PRG, where $\mathsf{in}$ is the input length of the PRF. This impossibility holds even for weak PRFs with one-bit output, where the adversary is restricted to making i.i.d. uniformly random queries. In addition, we prove a lower bound for weak PRFs with sufficiently long outputs that holds even when the construction is allowed to make adaptive queries to the PRG.

In KEM-based TLS 1.3 key establishment, the client generates a fresh KEM key pair for each connection, placing key generation on the handshake critical path. For NTRU+, a KEM based on the NTRU problem selected in the Korean Post-Quantum Cryptography (KpqC) competition, the dominant cost in this path is the polynomial inversion needed to compute the public key. Although NTRU+ uses an NTT-friendly ring and performs this inversion in the NTT domain, the routine still decomposes into many base inversions, each requiring a modular inversion computed by exponentiation. To accelerate polynomial inversion in the NTT domain, we collect the modular inversions arising from base inversions into a single stage. This makes it possible to apply Montgomery's trick, reducing the number of modular inversions to one at the cost of sequential product and recovery chains. These chains limit instruction-level parallelism (ILP). To address this dependency bottleneck, we apply hierarchical batching to these exposed denominator inversions, splitting the inputs into $k$ groups to expose independent product chains and recursively batching the resulting $k$ group-product inversions. This preserves the arithmetic cost of Montgomery's trick while improving ILP, thereby reducing cycle counts. We evaluate hierarchical batch inversion across all NTRU+ parameter sets in both C and AVX2. For NTRU+$864$, the parameter set with the largest gains, compared with non-batched polynomial inversion, it reduces polynomial inversion latency by 48.91% in C and 59.57% in AVX2. For key generation, the corresponding speedups are 18.91% in C and 9.34% in AVX2.

CMoSS facilitates modular specifications, design and analysis of cryptographic protocols. Modular design and analysis is achieved by supporting provably-secure compositions of protocols; typically, a protocol uses a blackbox subprotocol, and is proven secure when composed with any subprotocol meeting the blackbox specifications. For modularity of specifications, CMoSS extends the approach of the MoSS framework: protocol specifications are defined modularly, by a set of independent predicates (games) for each model (assumption) and requirement (goal). CMoSS makes it feasible to rigorously specify, develop and analyze realistic applied cryptographic protocols, supporting real-time concurrency and involving different attacker capabilities, delays, faults and synchronization challenges. CMoSS specifications provide a precise formalization of the informal specifications used by practitioners, facilitating provable security for practical protocols.

A key challenge in digital credential systems is revocation, that is, the ability to revoke credentials post-issuance and verify their status upon presentation. While anonymous credentials enhance privacy over classical credentials (e.g., by providing unlinkability), they complicate revocation. Existing revocation schemes for anonymous credentials often suffer from high client or verifier computation, long delays before revocation takes effect (e.g., epoch-based settings), or require updates to all users with each revocation. We present an efficient, real-time revocation system for anonymous credentials with decentralized revocation authorities based on a novel primitive called Private Record Certification (PRC). PRC enables users to obtain a certificate for a record stored in a server-managed database without the servers learning which record was requested. This primitive is of independent interest, and we construct it by combining techniques from private information retrieval and secure multi-party computation. Our revocation scheme outsources its costs to the revocation authorities and has minimal overhead for clients and verifiers, while ensuring the communication costs are sublinear in the number of credentials for the revocation authorities. We build a prototype and demonstrate that our system achieves sub-second real-time latency at a scale of over 1 billion credentials, with an online operational cost of 2.5$ per server for processing 1 million PRC queries.

NIST standardised a lattice-based key-encapsulation mechanism (ML-KEM) and a lattice-based digital signature scheme (ML-DSA) in 2024 as post-quantum replacements for classical key establishment and digital signatures. Both compute a forward number-theoretic transform (NTT) over secret-bearing polynomials; the NTT's twiddle constants are a documented fault-attack surface. Published attacks zero every twiddle with a single glitch on ML-KEM key generation, or zero individual twiddles on ML-DSA signing. Countermeasures detect or mask such faults, but none bounds the information that survives when an attacker perturbs twiddles one at a time. This paper supplies that bound as an exact per-layer rank ladder, for arbitrary perturbations $\zeta_k \mapsto \zeta_k^{'}$ with bit-flips included. A single twiddle fault leaks exactly the butterfly length of its layer in secret coefficients, a count attained rather than merely bounded, so one fault per layer pins all but two coefficients for ML-KEM and all but one for ML-DSA. The surviving ambiguity is identical whichever twiddle is hit in each layer: $\mathrm{span}(e_0, e_1)$ for ML-KEM's incomplete NTT, $\mathrm{span}(e_0)$ for ML-DSA's complete NTT. No combination of twiddle-perturbation faults, however large, shrinks it further, and this rank-and-kernel characterisation is machine-checked in Lean 4. The per-layer leakage rate it exposes gives countermeasure designers a closed-form budget for allocating protection.

While FHE enables computation on encrypted data, protecting the program itself remains a theoretical and practical challenge, often forcing practitioners to choose between exposing proprietary logic or suffering impractical performance penalties. This paper introduces HEGIDE, an oblivious processor based on the (discrete) Cheon-Kim-Kim-Song (CKKS) scheme that bridges the gap between theoretical Private Function Evaluation (PFE) and its practical realization. Central to our contribution is OSReM (Oblivious Shift Register Memory), a novel memory architecture that circumvents the linear complexity of standard FHE-RAM writes. By treating memory as a shift register, OSReM enables low-latency, constant-time writes without the need for expensive full-memory bootstrapping. HEGIDE leverages a MIMD (Multiple Instruction, Multiple Data) design, utilizing CKKS packing to evaluate distinct program threads in parallel, thus maximizing throughput. While the processor architecture natively supports arbitrary word sizes and instructions, we provide a compiler that manages memory scheduling to abstract the complexity of the shift-register design. We provide a proof-of-concept full implementation of HEGIDE using the OpenFHE library. Experimental results demonstrate the efficiency of our approach, achieving an amortized cycle time of just 6.4 ms for a 16-bit processor - two orders of magnitude faster in throughput than comparable approaches - offering a viable path for the secure execution of proprietary algorithms on encrypted data.

The Learning with Errors (LWE) problem is a fundamental hardness assumption underlying most fully homomorphic encryption (FHE) schemes. Given the close relationship between the Learning with Rounding (LWR) and LWE problems, several cryptographic constructions have also been developed based on LWR. In particular, LWR-based schemes often benefit from simpler and more efficient implementations, as they eliminate the need for explicit Gaussian error sampling. Despite these advantages, relatively few FHE constructions in the literature are based on the LWR assumption. At AsiaCCS 2025, Goyal and Gangopadhyay proposed a multi-key FHE (MKFHE) scheme based on LWR that adopts a public-key extension mechanism rather than the conventional ciphertext-extension paradigm. The authors also identified the development of a ring-based analogue as an open future direction. In this work, we present two Ring-LWR-based MKFHE constructions that can be viewed as ring analogues of the LWR-based MKFHE scheme of Goyal and Gangopadhyay. To the best of our knowledge, these are the first MKFHE schemes based on the Ring-LWR assumption. Compared with existing Ring-LWE-based multi-key constructions, our schemes achieve improved compactness in terms of storage and communication costs. We provide concrete parameterizations supporting circuits of varying multiplicative depths and present a proof-of-concept implementation to validate our claims.

We show that the data deduplication scheme [IEEE Trans. Cloud Comput., 11(1), 156-167, 2023] is flawed due to some inconsistent computations. The scheme tries to propose a hybrid encryption and authentication mechanism based on RSA cryptosystem and pairing cryptosystem, but it has confused the different group operations. In the data sharing phase, the cloud service provider cannot determine which stored tag matches the temporary tag, and fails to return the stored data to the requester. To fix, it should explicitly specify which is randomized by modular exponentiation with an RSA modulus, and which is randomized by point multiplication over the underlying elliptic curve.

Pseudorandom codes (PRCs), introduced at Crypto 2024 by Christ and Gunn, are encryption schemes with pseudorandom ciphertexts and error-correction guarantees. PRCs are useful as a tool to obtain watermarking for generative models, in particular ensuring that a watermark is hard to remove against an attacker that can modify up to a given fraction of the watermarked output (a.k.a. the robustness property). A PRC is public-key if the encoding procedure is public (whereas detection requires the corresponding secret key). In this paper, we provide the first construction of public-key PRCs for the binary alphabet satisfying robustness in the presence of a constant fraction of substitutions ($1/6 - \varepsilon$, for arbitrary $\varepsilon > 0$) and at the same time achieving pseudorandomness against sub-exponential-time distinguishers. The pseudorandomness property relies on a new family of distorted McEliece assumptions that we introduce, instantiated with a class of expanded subcodes of Reed-Solomon codes, called Raw Reed-Solomon codes, for which we provide heuristic evidence of (plausible) sub-exponential hardness. Our construction is obtained by revisiting the original blueprint by Christ and Gunn to obtain public-key PRCs based on McEliece assumptions. Along the way, we also uncover that their blueprint does not work directly with Raw Reed-Solomon codes. In particular, we show that a generating matrix of a permuted Raw Reed-Solomon code is distinguishable in polynomial time from a uniformly random generating matrix. To circumvent that difficulty, we propose to distort the public key by multiplication with a sparse invertible matrix of constant row Hamming weight.

Byzantine Agreement (BA) protocols must ensure not only agreement and termination, but also validity: the value agreed upon should meaningfully reflect the honest parties' inputs. The choice of validity condition can change the exact resilience threshold at which BA is solvable. Tight characterizations for BA with general validity conditions are known in the partially synchronous model (PODC'23), in the synchronous model (PODC'24), and in the network-agnostic model (DISC'25). We focus on general validity for synchronous BA with responsive termination. Such protocols remain secure against up to $t_s$ byzantine corruptions, but incur a running time that depends on the actual network delay $\delta$, rather than the conservative delay bound $\Delta \gg \delta$, whenever at most $t_r \leq t_s$ parties are corrupted. We present a tight characterization of the validity properties solvable in this setting. We prove that every non-trivial validity property requires $n>2 t_r+t_s$ in authenticated settings, where a public-key infrastructure and digital signatures are available, and $n>3 t_s$ in unauthenticated settings. These threshold conditions are accompanied by a validity-dependent requirement, the responsive similarity condition: roughly, for any concrete configuration of honest inputs, there is a value that is valid for any view that a protocol could obtain from this initial configuration. We then present matching protocols in both settings, showing that these conditions are sufficient. The main technical contribution is an authenticated responsive Core-Set Agreement protocol requiring $n>2 t_r+t_s$. This threshold may place the protocol in an honest-minority regime, where prior constructions for general validity do not apply and where standard Synchronous Broadcast is not responsive. Finally, we instantiate the characterization for several standard validity notions -- weak validity, strong unanimity, convex validity, and honest-input validity.

We continue the study of fast functions, computable by linear-size circuits, that share useful properties of random functions. Motivated by cryptographic applications, we generalize and improve on previous results in this area, obtaining the following results: - For any constant $t$, we construct a fast $t$-wise independent hash function with algebraic degree $\log_2 t$ (over $\mathbb F_2$), simultaneously optimizing both asymptotic circuit size and degree. - We simplify and improve a recent construction (ITCS 2026) of a family of fast codes with fast duals, both meeting the Gilbert-Varshamov bound. Unlike the previous construction, our construction has negligible failure probability, can accommodate general fields and rates, supports a systematic encoding, and admits fast universal encoders. - We strengthen the above to support stronger random-like properties, such as optimal combinatorial list-decoding. This is achieved by constructing, for any constant $t$, a family of fast linear functions that map any $t$ linearly independent inputs to uniform and statistically independent outputs. Prior to our work, this was only known for $t=1$. We demonstrate the usefulness of the above results to cryptography. This includes the first nontrivial protocols for perfectly secure multiparty computation whose circuit complexity scales linearly with the number of parties, as well as protocols for computing encrypted matrix-vector products with optimal asymptotic circuit complexity.

Heterogeneous computing platforms increasingly rely on high-throughput data paths spanning CPUs and accelerators, yet most high-speed software ciphers are optimized primarily for CPU-centric execution models. We present AICE, an arithmetic-oriented stream cipher over \(\mathbb{Z}/2^{16}\mathbb{Z}\) with a 37-word (592-bit) internal state, a nonlinear feedback combining modular addition, multiplication, bitwise OR, and rotation, a 370-round initialization with post-initialization key feed-forward, and periodic blank updates. We analyze AICE under several cryptanalytic models, including differential trail screening, linear approximation over the abelian group \(\mathbb{Z}/2^{16}\mathbb{Z}\), guess-and-determine state recovery, and exact SMT-based cube evaluation, and find that all observable structural phenomena remain confined to reduced-round settings far below the full initialization. On the AI Cores of Huawei Ascend accelerators, AICE reaches a single-core peak throughput of $114.13$ Gbps on the Ascend 950 and $55.36$ Gbps on the Ascend 910B4, and scales to $1.59$ Tbps on $32$ Ascend 910B4 cores, roughly $54\times$ the throughput of AES-CTR and $107\times$ that of SM4-CTR on the same $32$-core configuration; on the ARM Kunpeng 920 it remains in the same throughput class as hardware instruction accelerated AES-CTR.

Modern cryptography relies on the intractability of computational problems. We present an approach to building cryptography from a new source of hardness: \emph{proving mathematical theorems}. Our main result is a construction of succinct non-interactive arguments (SNARGs) for NP under a new, but natural, assumption on the hardness of proving lower bounds in proof complexity. Specifically, our assumption states that it is impossible to prove, within a weak bounded arithmetic theory, the correctness of certifying hard tautologies against Extended Frege. This assumption is inspired by an informal mathematical challenge proposed by Razborov [Ann. Math. '15], and can be viewed as a generalization of an unconditional unprovability result due to Krajíček and Pudlák [J. Symb. Log. '89]. Our construction is a simple variant of the SNARG construction of Jin, Kalai, Lombardi, and Vaikuntanathan [STOC '24]. While the soundness of their construction was proven only for a subclass of NP, we prove its soundness for all of NP under our assumption. At the heart of our result is the observation that cryptographic reasoning is simple in a formal sense: the security proof of most cryptographic primitives can be formalized in a weak theory. In particular, we show how to formalize the scheme of Jin et al. in Jeřábek's theory $\mathsf{APC}_1$ [J. Symb. Log. '07], a weak theory of bounded arithmetic.

Permissionless consensus enables parties to perform Byzantine agreement without any a priori knowledge about who is participating, except for an upper bound on the number of participants running the protocol (no PKI, etc.). Since Nakamoto’s Bitcoin paper, it has been widely believed that permissionless consensus is feasible provided the (Byzantine) adversary only controls a fraction of the collective computational power. However, all known protocols, including Nakamoto’s, rely on idealized assumptions (or ad hoc instantiations). Is permissionless consensus possible without such assumptions? Surprising little progress had been made towards solving this open question until the recent result by Ball et al. (Crypto 2024), which showed how to achieve permissionless consensus from proofs of work (PoWs) based on fine-grained complexity assumptions in a setting where a randomness beacon is available to all parties running the protocol. Their work left open whether it is possible to remove the beacon assumption; this question is the focus of our work, which we resolve via a new consensus protocol construction that relies on a novel class of distributed samplers and a common random string (that does not need to be structured or sampled precisely at the onset of the protocol execution). To prove our protocol secure, we revisit the concept of distributed samplers and adapt it to a setting where multiple sampler executions need to be simultaneously secure. To address this challenge we introduce the primitive we call d-wise independent distributed samplers and put forward constructions for such samplers based on DDH and LWE. We then present our consensus protocol via a modular design that utilizes a new moderately hard cryptographic primitive we call multi-verifier signatures of work, a sort of “time-based signature” we construct by composing distributed samplers and (fine-grained complexity-based) PoWs, and which may be of independent interest.

Censorship has always existed, serving both to prevent harms and to inflict them by chilling speech, suppressing organizing, and withholding inconvenient facts and ideas; most technical work aims to prevent all forms of censorship --- the "good", the "bad", and everything in between. We study the complementary, rarely explored goal of making any censorship attempt transparent. We formalize censorship-evident publishing systems (CEPS), protocols that force both overt and covert takedowns to yield transferable evidence. We also provide a CEPS instantiation with Streisand, a proof-of-concept deployment that combines a blockchain-backed timestamp oracle, private information retrieval (PIR)-based anonymous queries to prevent extraction attempts from being conspicuous, and probabilistic Merkle-witness retrieval to produce compact censorship proofs. We present performance evaluations on a 1.3 GiB Enron-derived dataset with regex-based PII redaction to model realistic censorship, and demonstrate that a background daemon can detect heavy censorship after a small number of post-censorship queries, making Streisand an effective auditing mechanism rather than interactive file retrieval. We also discuss design trade-offs (proof size vs. computation, PIR sufficiency vs. necessity), scalability limits, and how CEPS complements existing transparency practices, with Streisand as a starting point for CEPS deployments.

This paper presents high-performance Advanced Vector Extensions 512 (AVX-512) implementations of two Korean standard cryptographic algorithms: the Lightweight Secure Hash (LSH) hash function and Lightweight Encryption Algorithm-Galois/Counter Mode (LEA-GCM) authenticated encryption. For LSH, we apply three optimization strategies: single-message processing using AVX-512 512-bit vector registers, dual-message parallel processing through register interleaving, and multi-core parallelization using a dynamic queue-based pthread thread pool. For LEA-GCM, we propose an end-to-end optimization that replaces scalar Counter mode (CTR) encryption with 16-block AVX-512 parallel processing and Streaming SIMD Extensions (SSE)-based Galois Hash (GHASH) authentication with VPCLMULQDQ-based 4-block parallel processing. Performance evaluation on an Intel Core i7-1165G7 (Tiger Lake) processor shows that LSH-256 achieves an average 1.16× throughput improvement and LSH-512 achieves an average 1.61× improvement over the Korea Internet and Security Agency (KISA) AVX2 reference implementation. Dual-message interleaving achieves an average superlinear speedup of 2.28× driven by instruction-level parallelism (ILP), and the 8-core thread pool delivers speedups of 3.50× to 5.12×. The optimized LEA-GCM implementation achieves a 3.26× throughput improvement over the KISA SSE-based reference and a 12.1× improvement over the pure software implementation for 4096-byte inputs, with correctness verified against KISA official test vectors.

Electronic voting systems inherently encompass a structural tension among ballot secrecy, verifiability, and coercion resistance. Voters must be able to verify whether their votes have been included; however, if such verification information can serve as evidence presentable to a third party, it becomes a basis for post-election intimidation. Existing studies have focused primarily on performance evaluation or data separation, and have not comprehensively addressed the structural tension between verifiability and coercion resistance. This study defines this tension as the verification paradox and designs and implements an electronic voting prototype on a three-organization consortium based on Hyperledger Fabric 2.5, combining a 2-of-3 endorsement policy, nullifier-based anonymity, Exponential ElGamal homomorphic tallying, zero-knowledge proof (ZKP)-based ballot validity verification, panic password-based deniable verification, and Private Data Collection (PDC)-based coerced vote separation. Quantitative evaluation results confirm a server latency overhead of +0.9% for ElGamal relative to the AES performance baseline, statistical indistinguishability between normal and panic responses (p > 0.05), and a peak throughput of approximately 40.7 TPS (with an error rate of 0%) under 1,000 concurrent voters. This study demonstrates that permissioned blockchains can provide practical mitigation of the verification paradox through implementation and quantitative evaluation.

The Korean Cryptographic Module Validation Program (KCMVP) is a national certification system that verifies the security and conformity of cryptographic modules deployed in government and public institutions. The current process typically takes about one and a half years, during which frequent supplement requests and the resulting retesting cycles substantially raise costs and delay schedules. To address this, we propose an AI-based pre-certification framework that combines rule-based deterministic detection (L1), RAG-based guideline-evidence retrieval (L2), and LLM-based final decision (L3) into a funnel-shaped pipeline that progressively reduces false positives. L1 applies more than 170 YAML inspection rules across four pattern types (missing, regex, semantic, ast) to perform deterministic detection. L2 retrieves and attaches KCMVP guideline evidence to each violation through multi-stage RAG search, and L3 employs Gemini 2.5 Flash-Lite to make context-aware decisions on false-positive candidates. In an initial evaluation on 128 Ground Truth cases derived from the KISA LEA code, the system detected all 128 cases, achieving 100% recall, while L3 correctly removed 9 of 46 FP candidates (19.6%) without inducing any false negatives (FN), confirming the stepwise refinement effect of the funnel structure. A blind verification on a certified commercial cryptographic module (~14.5 KLOC) yielded a low detection frequency of 0.58 cases per 1,000 lines of code, supporting the system’s practicality in real environments.

The advancement of quantum computing threatens public-key cryptographic algorithms used in TLS connections, such as RSA and ECDHE. The Harvest Now, Decrypt Later (HNDL) attack exposes long-term confidential data to risk even before quantum computers are practically realized, yet a systematic methodology for immediately quantifying the quantum vulnerability of individual TLS connections remains absent. This paper proposes a layered risk scoring model that quantifies the quantum threat exposure of TLS connections on a 0–100 scale. The model decomposes risk into five independent layers—TLS protocol exposure (L1), legacy public-key vulnerability (L2a), AES-128 Grover weakening (L2b), PQC Level-1 vulnerability (L2c), and certificate expiration urgency (L3)—and incorporates an HNDL global multiplier M that reflects the confidentiality retention period of transmitted data. Applied to 502 real-world TLS sessions across four industry sectors with M = 1.50, the domestic average risk score (16.0) is approximately 34% higher than the global average (11.9), with domestic legacy key exchange usage at 77.4% versus 53.5% globally and PQC adoption at 22.6% versus 46.5%. These results quantitatively confirm the elevated quantum risk of domestic network infrastructure, underscoring the urgency of PQC transition.

The “Harvest Now, Decrypt Later (HNDL)” attack—which intercepts and stores encrypted communications before quantum computers become practical and decrypts them afterward—poses a long-term threat to TLS communication channels. Following the completion of NIST PQC standardization, organizations must pursue a phased migration of their TLS layers; however, existing approaches are limited by late detection of configuration errors, absence of cryptographic asset tracking, and insufficient automated response. This paper proposes an 11-Step DevSecOps pipeline grounded in Policy as Code. The pipeline automatically validates and deploys a 3-Stage TLS migration—Classical ECC (Stage 1), Hybrid PQC (Stage 2), and Advanced Hybrid PQC (Stage 3)—through 11 steps per execution, integrating OQS-Nginx custom builds, security scanning, CBOM Diff, and matrix CI regression detection. In our evaluation against six PQC toolchain pitfalls, standard SCA/SAST/SBOM pre-detected 0/6, whereas custom builds pre-prevented 5/6 and matrix CI detected 6/6 at runtime. In an evaluation of LLM-based code migration across 80 trials (55 responses received), even with static AST validation applied, 24 failures due to signature/argument hallucination (43.6% of response trials) were only caught at runtime, quantitatively confirming that semantic execution validation is an essential component of multi-layered defense.

Organizations relying on RSA-OAEP encryption in protocols such as JWE, SAML, and OIDC face a critical challenge: transitioning to post-quantum cryptography without disrupting operational continuity. This paper presents a phased migration strategy that uses RSA-KEM-ML-KEM composite Key Encapsulation Mechanisms as an intermediary step between current RSA-OAEP encryption and the target state of pure ML-KEM adoption. We formalize the RSA-KEM-ML-KEM construction, prove IND-CCA2 security via a Split-Key PRF combiner, and integrate it into the Hybrid Public-Key Encryption (HPKE) framework. Our implementation demonstrates that composite schemes enable quantum-resistant encryption while preserving existing RSA key infrastructure, though with measurable throughput trade-offs that inform migration timelines. We analyze protocol-specific integration for JWE, SAML, and OIDC encryption use cases, providing decision frameworks for transitioning from RSA-OAEP through composite approaches to pure post-quantum encryption. This work contributes a formally analyzed transition mechanism and practical migration guidance for organizations seeking to adopt quantum-resistant encryption in RSA-dependent systems, validated through application to identity and access management protocols.

Using the language of categories, we introduce a novel framework abstracting the key algorithmic features of the Deuring correspondence between supersingular elliptic curves and quaternion orders and of the post-quantum signature scheme SQIsign based on it. We then show how to construct an interactive identification scheme and digital signature within this framework, and also instantiate more advanced primitives, such as a chameleon hash function. We present two distinct instantiations of the framework based on isogenies of supersingular elliptic curves: the first recovers (one-dimensional) SQIsign, while the second leads to the recently published SQInstructor.

FrodoKEM is an unstructured LWE-based key encapsulation mechanism (KEM), widely recognized for its conservativeness and robustness. However, there remains a performance gap of approximately one order of magnitude between FrodoKEM and structured LWE-based KEMs, which severely limits its competitiveness during the standardization process. This work proposes the fastest hardware implementation of FrodoKEM to date, which is also configurable, achieving up to 2.5× speedup over prior hardware designs. Specifically, for the most time-consuming module, modular matrix multiplication, a block matrix processing approach is adopted, where the computation is reformulated into block-level operations and further mapped to vector inner-product computations. Based on this formulation, two optimized architectures are proposed for vector inner-product computation using a carry-save-adder (CSA)-based Wallace tree structure, achieving improvements in resource efficiency while eliminating the use of DSP resources. By fixing the block size to 4×4, the data generation rate using parallel SHAKE-based random number generators is precisely matched with the data consumption rate of matrix multiplication, thereby improving hardware utilization efficiency. The proposed design is implemented in Verilog and verified on both Xilinx Virtex-7 and Artix-7 FPGA platforms, as well as ASIC implementation.

Digital signature schemes based on isogenies are among the most compact signatures achieving post-quantum security. Recent advances, especially those leveraging higher-dimensional isogenies, have also made such schemes practically efficient. However, comparatively little attention has been devoted to endowing these signatures with additional privacy-enhancing properties, such as the re-randomization of keys and the adaptation of signatures to new public keys. Although some results exist in the isogeny group action setting, these signatures suffer from a subexponential quantum attack which renders them rather inefficient. In this work, we initiate the first systematic study of privacy-enhancing isogeny-based signatures outside the group-action framework. We base our exploration on the notion of signatures with randomizable keys developed by Celi et al. (FC'24), which aims to unify privacy notions related to key updatability and signature adaptation. In particular, we analyze which of their privacy notions can be achieved from the state-of-the-art signatures SQIsign, PRISM and the hash-and-sign signature scheme derived from the Deuring verifiable unpredictable function (DeuringVUF). To this end, we naturally extend SQIsign to an SWRK scheme that allows key randomization, and enhance both PRISM and the DeuringVUF signature to additionally allow for message adaptation. We show that, due to the deterministic nature of the signatures, the DeuringVUF signature achieves perfect adaptability. We formally prove all three of our modifications achieve unlinkability against unbounded adversaries, and remain unforgeable under the same assumptions as the original schemes.

The hardness of the Learning Parity with Noise (LPN) problem is a foundational assumption in cryptography, forming the basis of constructions ranging from symmetric-key primitives to public-key encryption and beyond. A central open question is whether the average-case hardness of LPN can be based on worst-case complexity assumptions, as has been achieved for the analogous Learning With Errors (LWE) problem. Existing worst-case-to-average-case reductions for LPN [BLVW19, YZ21] rely on statistical smoothing of linear codes, which inherently limits the resulting average-case hardness to noise rates as large as $1/2 - 1/\mathrm{poly}(n)$, which is insufficient for public-key applications. We explore a new approach towards obtaining such reductions: rather than requiring that random sparse combinations of the rows of the generator matrix of a code be statistically close to uniform, we only require that they be computationally indistinguishable from uniform. This leads to a clean win-win structure: we show that any efficient LPN solver can be transformed into a pair of efficient algorithms $(S, D)$ such that for every matrix $A$ of appropriate dimensions over $\mathbb{F}_2$, either $S$ decodes the code generated by $A$ from random noise, or $D$ distinguishes random noisy codewords of the dual of this code from uniform. By instantiating this reduction with appropriate parameters, we obtain the average-case hardness of LPN with inverse-polynomial noise rate $n^{-\alpha}$ for any constant $\alpha < 1$, assuming the worst-case simultaneous hardness of decoding a code from random noise and distinguishing random noisy codewords of its dual from uniform. In particular, setting $\alpha = 1/2$, our reduction yields LPN hardness in the parameter regime required for Alekhnovich's construction of public-key encryption [Ale03], a regime that was previously inaccessible via worst-case reductions.

We study the security of the Fiat-Shamir transformation when applied to multi-round oracle proofs in the standard model, showing that Interactive Oracle Proofs (IOPs) can be transformed via Fiat-Shamir into Non-interactive Zero-knowledge (NIZK) arguments. We obtain our result in two steps. First, we show that instantiating Kilian's transformation with an IOP satisfying a mild Zero-Knowledge (ZK) property called semi-Honest-Verifier ZK (semi-HVZK), and a commitment scheme that is extractable and equivocal, yields a ZK argument. We then obtain provably-secure NIZK arguments from our interactive ZK arguments by instantiating Fiat-Shamir with a Correlation-Intractable Hash (CIH) function. The second step involves carefully defining an appropriate "bad relation" for which CIHs are known to exist. Existence of CIH for our bad relation requires the underlying semi-HVZK IOP to have an additional "doom checkability" property which we introduce. Roughly, doom checkability guarantees that one can efficiently check whether a non-empty partial IOP transcript is "doomed" in the sense that it will lead the verifier to reject. We then show that IOPs based on the "MPC in the Head" paradigm are doom checkable. Our results show that the Fiat-Shamir paradigm can be applied to semi-HVZK IOPs to yield provably-secure NIZKs. This extends similar results known for single-round IOPs (i.e., Probabilistically Checkable Proofs) and interactive proofs (IPs), and establishes the soundness of this method. Along the way, we also prove composition theorems for semi-HVZK IOPs, which might be of independent interest, and use them to improve the soundness error of linear-time IOPs and interactive arguments from the literature.

Isogeny-based cryptography is a kind of cryptography whose security relies on the computational hardness of the isogeny problem. This field is gaining attention as a promising candidate for post-quantum cryptography. Among the notable schemes within this category is SQIsign, a signature schemes that has been submitted to the NIST Post-Quantum Cryptography Standardization competition. In this paper, we introduce a new isogeny-based signature scheme, $\Delta$-SQIsign, which represents a significant departure from existing isogeny-based signatures including SQIsign. The key distinction in our scheme lies in its use of the degree of isogeny as a challenge within the underlying $\Sigma$-protocol. Then, the prover outputs an isogeny of the given degree as a response. To construct such a scheme, we introduce a new algorithm, called $\Delta$-KLPT, which is a variant of GeneralizedKLPT. Similar to GeneralizedKLPT, our algorithm outputs an ideal equivalent to a given ideal with a fixed norm; however, under certain conditions, it can produce an ideal of smaller norm than GeneralizedKLPT.

Real-time group communication protocols, such as Zoom and Microsoft Teams, aim to provide end-to-end security for audio and video conferences even in the presence of a malicious server. Despite their widespread deployment, particularly since the COVID-19 pandemic, their intended security guarantees lack comprehensive formalization. Prior work largely focuses on Zoom, and analyzes its security in models that rely on restrictive assumptions, such as the existence of a trusted server at certain points in time or a long-lived leader that never leaves the group. Moreover, existing analyses assume that group-specific session states of group members are secure and incorruptible, leaving the impact of potential full state compromise on group security unexplored. In this work, we propose a set of essential security guarantees for real time group communication with state-compromise resilience against fully malicious servers and provide the first construction that provably satisfies all of these guarantees. To formally prove that our design achieves its goal, we formalize a novel continuous group key distribution protocol and introduce an associated security model that captures all the intended guarantees. We propose a generic construction that is provably secure in this model and suggest both classical and post-quantum secure instantiations. Besides these main design goals, we introduce a novel multi-recipient authenticated key encapsulation mechanism, which serves as a building block for our generic construction. We define two core security notions for maKEM, propose both concrete and generic constructions, and prove their security in the random oracle model and the standard model, respectively.

Although the state-of-the-art neural network model extraction attack in the hard-label setting by Carlini {\em et al.} at EUROCRYPT 2025 has polynomial-time complexity in theory, its dual-point clustering relies on singular value decomposition (SVD) with a time complexity of $\mathcal{O}(n^2 \cdot (d^{(k)})^3)$, resulting in huge runtime in practice. To address this computational bottleneck, this work transforms Carlini {\em et al.}'s geometric-view hard-label attack into an algebraic framework, and proposes a novel Approximate Signature Vector (ASV) method to achieve efficient parameter extraction on Fully Connected Neural Networks (FCNNs) by leveraging two key observations: high-dimensional random vectors are nearly orthogonal, and neurons in practical DNNs tend to learn disentangled features. The proposed ASV method replaces SVD-based rank checking with simple inner-product operations, reducing the clustering complexity to $\mathcal{O}(n \cdot (d^{(k)})^3)$ on average. Furthermore, this paper presents the first model extraction attack against hard-label max-pooling Convolutional Neural Networks (CNNs) by proposing an advanced ASV method with a kernel-centric clustering scheme instead of the neuron-centric clustering, which fully exploits the property of weight sharing in convolutions and fills the cryptanalysis gap. Experiments on a 64-64$\times 4$-10 FCNN and LeNet-5 (CNN) with max pooling demonstrate that our ASV method drastically cuts clustering time, and improves the overall efficiency in the model extraction.

Functional bootstrapping combines ciphertext refreshing with the evaluation of a target function, and has become a central tool for evaluating non-linear functions in homomorphic encryption. In the CKKS scheme, functional bootstrapping typically represents the target function as a trigonometric polynomial over the exponential basis generated by the bootstrapping procedure. Existing CKKS functional bootstrapping methods then evaluate this polynomial using standard baby-step giant-step techniques, whose multiplicative depth grows logarithmically with the polynomial degree. As a result, non-smooth function evaluations or high-degree lookup tables require a large modulus budget and often a larger ring degree, leading to higher evaluation latency. This is especially inefficient for applications that require only hundreds of parallel evaluations, where the large SIMD capacity of CKKS is not fully utilized. We present \textsf{SWIFT}, a shallow and SIMD-aware functional bootstrapping framework for CKKS. The key idea is to exploit the exponential map \(h(x)=\exp(2\pi i x)\) used in CKKS bootstrapping, which satisfies \(h(\ell x)=h(x)^\ell\) for $\ell\in \mathbb Z$. Thus, the powers required for trigonometric polynomial evaluation can be obtained directly as \(h(\ell x)\) during bootstrapping, rather than generated by homomorphic multiplications after bootstrapping. To realize this idea efficiently, \textsf{SWIFT} packs the scaled inputs \(\ell x\) into SIMD slots and evaluates the exponential map on them in parallel. It then reconstructs the target trigonometric polynomial from the resulting powers. As a result, the multiplicative depth of polynomial evaluation becomes independent of the polynomial degree and can be reduced to constant depth, even depth one. This shallow structure reduces the required modulus budget and enables high-degree polynomial evaluation at smaller ring degrees. It also lowers the key-switching cost from the standard \(\Theta(\sqrt d)\) cost to \(\Theta(\log d)\) or \(\Theta(d^{1/4})\), depending on our parameter regime. Our implementation shows that computations previously requiring \(\log N=16\) or \(\log N=17\) can be performed at \(\log N=15\). For lookup tables, \textsf{SWIFT} achieves up to a \(38.1\times\) latency improvement over prior CKKS functional bootstrapping methods at batch size \(128\). For ReLU evaluation at batch size \(256\), it achieves a \(5.21\times\) latency improvement over the previous method. These results demonstrate that CKKS functional bootstrapping can be made latency-efficient for batch sizes on the order of hundreds by using SIMD capacity as a computational resource rather than only as a batching mechanism.

The recent study of fixed-key differential probabilities mainly follows two complementary approaches. The first derives key-dependent constraints from the internal structure of the primitive. This approach is intuitive, but a complete theory is difficult to build. The second approach is based on quasidifferentials. It is complete in theory when all quasidifferentials are considered, but exhaustive enumeration is usually infeasible in practice. In this paper, we relate quasidifferentials to concrete key-dependent constraints. This gives new insights into quasidifferentials. Each quasidifferential with a nonzero mask carries one relation, equating a linear parity of the involved key bits to a generally nonlinear Boolean function of the intermediate-state bits, and the relations that share these bits together constrain the key. Under the common threshold-based treatment, where only quasidifferential trails with sufficiently large absolute correlation are kept, some constraints on intermediate-state bits may be lost. This can produce an incomplete quasidifferential trail set with respect to the induced intermediate-state constraints. This, for example, can result in the fixed-key differential probabilities computed by quasidifferential aggregation to become negative on some key subspaces. To obtain a more precise distribution of fixed-key differential probabilities over the key space, we decouple quasidifferential trails according to their induced constraints. After decoupling, each resulting quasidifferential trail set is locally complete, so the derived probability distribution for the particular subspace is always valid. The decoupling also reduces the number of trails in each set, improving the efficiency of the quasidifferential method. As a result, our method yields a finer-grained key-space partition that could allow us to better approximate the true distribution under the quasidifferential framework. We instantiate this decoupling strategy in the threshold-based setting and apply it to differential trails of GIFT-64, GIFT-128, SKINNY-64, SKINNY-128, and RECTANGLE. The resulting locally complete trail sets always give valid fixed-key differential probability distributions and are no coarser than direct threshold-based quasidifferential aggregation. They coincide with direct aggregation when the retained trails are already locally complete. In our experiments, using our decoupling method is actually better for many evaluated trails and refines the key-space restrictions reported by prior constraint-detection frameworks. As each quasidifferential is a constraint, the same insight also let us write the induced linear and nonlinear key constraints explicitly for the bit-wise ciphers GIFT-64, GIFT-128, and RECTANGLE, addressing a limitation of the Trail-Estimator constraint detector described in Peyrin, Tan, Zhang and Zhou at FSE, 2025.

Synchronized multi-signatures allow for non-interactive aggregation of signatures generated within the same time step. This primitive is particularly well-suited for high-throughput blockchain protocols like Ethereum, where many distributed signers must validate the same block within a synchronized slot. In this work, we present Lemur, a post-quantum synchronized multi-signature from (module) lattices that improves upon the state-of-the-art in efficiency, scalability, and flexibility. Lemur follows the blueprint of Squirrel/Chipmunk (CCS 2022/2023) but introduces a fundamental redesign of the foundations of the overall framework. Our revisit of the framework is also motivated by the fact that our evaluation of Chipmunk's parameter sets, using the state-of-the-art lattice security estimation methods, suggests a substantially lower concrete security level (approximately 30 bits rather than the claimed 112 bits). First, we revisit the underlying building block of key-homomorphic one-time signature (KOTS) and introduce a novel security reduction based on a new lattice problem: the Dual Hint-MLWE assumption, which may be of independent interest. We then provide a formal reduction from the standard Module-LWE problem to Dual Hint-MLWE, which overall enables us to base the security of Lemur on the standard Module-LWE and Module-SIS assumptions. By shifting from a statistical security argument to a computational one, our KOTS design enjoys much better compactness and scalability. Second, we optimize the underlying homomorphic vector commitment (HVC) by transitioning from Ring-SIS to the Module-SIS setting and extending the commitment domain from vectors to matrices. This generalization reduces opening size and improves aggregation efficiency. After rectifying the parameters of Chipmunk for a fair comparison, our results show that Lemur's KOTS size achieves up to an order of magnitude improvement over Chipmunk's KOTS. In particular, aggregating 1 million one-time signatures requires under 8 KB. For the total multi-signature size, Lemur demonstrates around $2\times$ improvement over Chipmunk. To showcase our design, we provide a full-fledged Rust implementation. Our benchmarks demonstrate an aggregate signature size of 380 KB for $2^{20}$ signers. Stateful signing takes roughly 4.2 ms for a Merkle tree of height 20, while batch verification for an aggregate of 1024 signers completes in 15.0 ms ($\approx$ 14.6 $\mu$s per signer).

We study generic committing attacks—where ciphertexts decrypt under more than one context, i.e., key, nonce, associated data—for sponge-based authenticated encryption. As our main contribution, we give three new committing attacks which outperform existing attacks. One of our attacks provides a counterexample showing that the previous proof for the committing security of Ascon-like schemes with zero-padding does not extend to all parameter choices: in case of 128-bit tags and 256-bit zero-padding, the existing analysis claims 192-bit security; our attack reduces this by 62 bits down to 130-bit. Our attacks are applicable to the standardized scheme Ascon. As a further contribution, we analyze existing attack strategies for a generic sponge construction with various design features such as key-blinding, zero-padding, and state-update-functions.

Asynchronous distributed key generation (ADKG) is a fundamental primitive for building threshold cryptosystems and fault-tolerant distributed protocols in adversarial network settings. A central objective in this line of work is to achieve ADKG with $O(n^2)$ communication and constant round complexity under minimal setup assumptions. Recent progress has led to subcubic-communication ADKG protocols under different trade-offs. Feng and Tang (CRYPTO 2025) presented an ADKG protocol with $O(n^2)$ communication and $O(1)$ rounds, but at the cost of a cubic-communication setup phase in which each party posts a linear-sized public key on a public bulletin board. In contrast, Abraham et al. (PODC 2026) achieved an ADKG protocol with a standard setup phase, where each party posts only a constant-sized public key, but with $O(n^{2+1/k})$ communication and $O(k)$ rounds for a tunable parameter $k\leq \log{n}$. These results leave open whether one can simultaneously obtain constant-round complexity and quadratic communication under a standard setup phase. In this work, we resolve this open problem by presenting the first ADKG protocol that achieves $O(n^2)$ communication and $O(1)$ rounds while requiring only a standard setup phase in which each party posts a constant-sized public key on a public bulletin board. Our protocol is resilient to a strongly adaptive adversary corrupting up to $f < n/3$ parties and assumes only random oracles and secure erasures, both of which are also assumed by prior subcubic-communication ADKG constructions.

This paper introduces a geometric framework for Q2 quantum distinguishers by combining the geometric approach to classical symmetric-key cryptanalysis with the generalized correlation extraction algorithm. Our main technical tool shows that one superposition query, followed by appropriate (unitary) change-of-basis operations, prepares a ``correlation state'' whose amplitudes are the entries of the geometric correlation matrix in the chosen basis. This yields a unified preparation-measurement template that recovers several known quantum distinguishers: (1) hidden structure detection via support constraints in Fourier-type bases (e.g., Simon, Bernstein-Vazirani, Deutsch-Jozsa), and (2) event probability deviation tests via amplitude estimation (covering standard quantizations of linear and differential distinguishers). We analyze when relevant distinguishing mass is diluted across many basis states, identify it as a cause of poor query efficiency in several recent distinguishers, and provide basis-specific mechanisms to concentrate the signal (phase-oracle row restriction in the Fourier setting; chosen-plaintext subset-state restriction in the quasidifferential setting) to restore quadratic advantage. We illustrate the framework on Fourier and quasidifferential instantiations and discuss obstacles for non-unitary integral bases.

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

We present improved distributed broadcast and MST algorithms that are unconditionally secure against an eavesdropper controlling a fixed set of at most $f$ edges in an $n$-node $m$-edge $D$-diameter graph. We strive for secure algorithms with sublinear round and subquadratic message complexities (in $n$) for any $f$. This is in contrast to the exponential or polynomial dependence on $f$ in prior works. Our main results are: Secure broadcast algorithm, for sending an $O(\log n)$-bit message, that runs in $\tilde{O}(D+\sqrt{n})$ rounds and $\tilde{O}(n^{3/2})$ messages. This matches the state-of-the-art bounds for \emph{insecure} broadcast by [Ghaffari and Kuhn, and Gmyr and Pandurangan, DISC 2018]. Our bounds also improve over the $\tilde{O}(D+\sqrt{f n})$-round complexity and $\tilde{O}(\sqrt{f n}\cdot m)$ message complexity of secure broadcast by [Hitron, Parter and Yogev, DISC 2022]. Secure MST algorithm with sublinear round and subcubic message complexities that improve over the algorithm by [Hitron, Parter and Yogev, ITCS 2023] in the entire regime. In particular, when $f=\Theta(n)$, we improve the round complexity from $\tilde O(n^{3/2})$ to $\tilde O(n^{2/3})$, and the message complexity from $\tilde O(n^{3})$ to $\tilde O(n^{7/3})$. Our algorithms are randomized and their correctness and (statistical) security hold with high probability. The algorithms are based on a combination of techniques: Karger's sampling, tree packing and sparse recovery sketches.

Proximity testing is crucial to location-privacy applications, from discovering nearby friends to enabling UAV collision avoidance. In such settings, users must determine proximity without revealing their exact locations. This motivates privacy-preserving proximity testing (PPPT) protocols revealing only if the proximity condition holds, while hiding both parties’ inputs. However, most existing PPPT protocols rely on strong assumptions (e.g., non-colluding servers) or require simultaneous interaction, limiting their practicality. Moreover, they typically define proximity using metric distances (e.g., Euclidean distance), failing to support richer membership queries for complex regions like buildings or parks. To address these, we introduce a new primitive called Geometric Fuzzy Matching (GFM), which generalizes fuzzy matching to arbitrary $n$-dimensional regions. In GFM, the receiver specifies a region and learns only whether the sender’s location lies within it, without revealing either party’s input. This approach captures both classical distance-based proximity checks (for any Minkowski $\ell_p$ norm, $1 \leq p \leq \infty$), as well as membership tests for complex regions, providing a unified framework for diverse proximity queries. In low-dimensional settings, our protocol improves on distance-based checks compared to state-of-the-art van Baarsen et al. (EUROCRYPT 2024) for $\ell_\infty$ and maintains stable practical efficiency for $\ell_p$ norms under large distance thresholds or for $p \geq 4$, where previous approaches quickly become computationally prohibitive. It is also the first to support fuzzy matching over arbitrary geometric regions, enabling proximity queries in complex spaces. Our implementation confirms these results and demonstrates the protocol’s efficiency and applicability across diverse PPPT scenarios.

A leakage-tolerant circuit (LTC) can be viewed as a black-box implementation of a given functionality f with respect to a leakage class L in the sense that any leakage function L ∈ L applied to the circuit’s internal wires can be simulated by a similar leakage function L′ ∈L applied only to the circuit’s inputs and outputs. Previous works have demonstrated extensive applications of LTCs in constructing variants of leakage-resilient circuits (LRC): black-box construction of both stateless and stateful LRCs, and construction of deterministic stateful LRCs which only require external fresh randomness in the first invocation. However, feasibility results for LTCs are still limited to simple leakage classes, including only probing leakage, depth-1 AC0 leakage, and parity leakage. In this work, we instantiate the study of constructing LTCs and deterministic stateful LRCs against AC0 leakage, obtaining the following results: – We present the first construction of LTCs against generic AC0 leakage. As a corollary, we also construct LTCs against parity leakage with efficient simulation, refuting a conjecture proposed by Ishai and Song (Eurocrypt 2024). – We provide a generic framework to convert LTCs into computationally secure deterministic LRCs assuming one-way functions, and instantiate the paradigm for k-CNF leakage (with a sufficiently small k). This is the first instance of deterministic stateful LRCs against non-decomposable leakage.

Public-key authenticated encryption with keyword search (PAEKS), introduced by Huang and Li (Information Sciences 2017), was proposed to provide trapdoor privacy, whereby keyword information is protected from being revealed through trapdoors. To prevent the keyword guessing attack, however, a trapdoor needs to be generated separately for each sender, and the search complexity linearly grows with the number of senders even when searching for a single keyword. To address this inefficiency, we propose a generic construction of search-efficient PAEKS. We revisit the group-oriented approach of Wang et al. (IEEE Transactions on Information Forensics and Security 2024), in which senders are organized into sender groups. Our construction is simple yet effective where all senders belonging to the same group share a single public-secret key pair, and the search complexity depends only on the number of sender groups rather than the number of individual senders. We further introduce ciphertext indistinguishability against insiders, which ensures that no keyword information is revealed from ciphertexts, even if they are generated by other members of the same sender group. We also take into account an impossibility result by Yoshida and Emura (IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2026), which shows that trapdoor privacy against sender-group members cannot be achieved in the scheme of Wang et al. To address this limitation, we introduce trapdoor indistinguishability against outsiders, which guarantees that no keyword information is revealed from trapdoors generated for non-group members. Our generic construction yields search-efficient group-oriented PAEKS schemes from pairings and lattices.

Malicious-secure multiparty computation protocols protect against an adversary's arbitrary misbehavior. In the honest-majority four-party setting, one common technique relies on all communication between parties being duplicated. Under this approach, all correct messages are sent twice, while corrupted messages are only sent by the adversary and will not match concurrent correct messages. When a receiver observes that inconsistency, it announces cheating has occurred (and possibly aborts). Existing implementations often optimize this procedure by batching many such checks into a single hash and running a final consistency check just before revealing the result of a computation. Brüggemann and Schneider (Eurocrypt 2026) recently showed that these delayed consistency checks in honest-majority, malicious-secure protocols can violate privacy. Adversaries can introduce errors such that subsequent incorrect hashes reveal their missing secret share and allow plaintext secrets to be recovered just before the honest parties abort. Their suggested fix evaluates the hash comparison under multiparty computation, rather than in plaintext. In this report, we detail our fix for the Fantastic Four protocol in ORQ, a recent system for secure analytics that is vulnerable to the attack. The new implementation has a modest overhead that amortizes with larger inputs. The complexity of the modified protocol highlights the difficulty of implementing malicious-secure systems in practice; even seemingly harmless optimizations can break privacy.

In practice, the amount of side channel leakage related to the random polynomial generation of Dilithium can be limited. In this case, the coe cients of the random polynomial may not be recovered accurately, which then makes the secret key recovery with least square a difficult problem. Therefore, how to recover the secret key used by Dilithium with noisy equations becomes a meaningful concern. In light of this, the ne-grained residual interval screening is proposed to enhance the ability of least square to recover the secret key used by Dilithium. The core idea is to estimate the distributions of the residuals related to both correct and erroneous equations computed with the least square recovered candidate secret key in a pro ling scenario. Then, according to the distribution di erence of the residuals related to two types of equations, an interval can be screened. Note that a majority of erroneous equations are out of the screened interval while a majority of correct equations are in the screened interval. Therefore, least square can be used to recover a more accurate candidate secret key polynomial with equations in the screened interval. By iterating the process several times, the secret key polynomial can be successfully recovered. The e ciency of the proposed technique is veri ed with power traces measured from the Dilithium reference implementation running on a Cortex-M4 processor. The evaluation results show that only several hundreds of power traces are enough to recover the secret key used by Dilithium.

At CRYPTO 2025, Bhaumik et al. formalised the notion of Key Control (KC) security of Key Derivation Functions (KDFs). A KC adversary, on seeing the root key of a KDF, attempts to manipulate its auxiliary inputs (the `Context' string) to obtain a derived key from a pre-selected set of keys. In this paper we extend the notion of KC security to Key Combining Functions, which are KDFs that convert two root keys to a single derived key; we name the new notion Combining Key Control (CKC) security. We then investigate the CKC security of KDF Combiners and show that (up to certain limitations) it follows from the KC security of either of the component KDFs.

We show that private-key function-hiding inner-product functional encryption (FH-IPFE) is impossible in the generic group model (GGM). This impossibility extends to (non-compact) two-input quadratic functional encryption (QFE) under a weak security notion that allows only a single key corruption. Our results apply both to the variant where decryption outputs the result directly, and to the variant where the result is encoded in the exponent of a group element. Our results hold in both Maurer’s and Shoup’s model, with different tradeoffs. In Maurer’s model, we prove that FH-IPFE over $\mathbb{Z}_q^n$ cannot be realized even when $q^n$ is polynomially bounded. Here, $q$ denotes the modulus of the inner-product functionality, not the order of the underlying group. This stands in sharp contrast to non-function-hiding FE, which can be constructed from minimal assumptions (one-way functions in the private-key setting and public-key encryption in the public-key setting) whenever the set of functions is polynomially bounded. We extend this impossibility to Shoup’s model when $q^n$ is super-polynomial. Conceptually, our proof simulates any construction in Shoup’s model as one in Maurer’s model equipped with a random oracle. Our techniques may be of independent interest, offering a general method for upgrading other impossibility results from Maurer’s model to Shoup’s model. We match these negative results with two positive ones. First, we show that one-sided bounded FH-IPFE (i.e., either the number of key queries or the number of encryption queries is bounded) can be realized from one-way functions. Second, when both the number of key queries and encryption queries are bounded, we show the resulting notion of FH-IPFE can be achieved information-theoretically. These positive results show that our impossibility precisely characterizes the threshold for FH-IPFE.

A zero-evading generator with error parameter $\lambda$ is a distribution $Z$ on $\mathbb{F}^n$ such that for any non-zero vector $x\in \mathbb{F}^n$ the probability that $<a,x>=0$ is at most $2^{-\lambda}$, when $a$ is chosen according to $Z$. We investigate the number of additions required to compute $<a,x>$ given $x$. The traditional construction chooses a vector $a$ with random $\lambda$-bit elements. Pippenger's algorithm gives an additive complexity of at least $\Omega(\lambda n/\log n)$ for this approach. We give a construction requiring only $O(n+\lambda)$ additions. We highlight the impact of reducing the number of additions on aggregation of group-based commitments, such as KZG commitments[KZG10].

Two post-quantum upgrades to TLS 1.3 are being standardized in parallel: a hybrid key exchange (already deployed) that runs an elliptic-curve Diffie-Hellman exchange alongside ML-KEM, and a standalone mode that uses ML-KEM on its own. The Internet-Draft draft-usama-tls-risks-of-mlkem points out that the machine-checked symbolic proofs of TLS 1.3 rely on the commutativity of Diffie-Hellman, which ML-KEM does not share: a key encapsulation mechanism is asymmetric, one endpoint generating a key pair and the other encapsulating against it. The existing proofs therefore no longer apply, a new one is needed, and the draft argues that hybrids should be preferred. We supply that proof. We extend the reftls ProVerif models with a faithful, non-commutative KEM and analyze classical (EC)DHE, standalone ML-KEM, and the hybrid together, as unbounded concurrent sessions against a single active attacker free to break any cryptographic component. The central result is a sharp and tight contrast in robustness: standalone ML-KEM is a single point of failure, secure only while ML-KEM itself is unbroken, whereas the hybrid stays secure as long as either of its components survives: an attacker must break both, in one session, to learn anything. This single point of failure reaches authentication as well as confidentiality: with the sole key-exchange secret exposed and no secret pre-shared key salting the key schedule, the server Finished message becomes forgeable, so a client can complete a handshake that no server completed, while the hybrid stays safe unless both components break. The three modes also interoperate without ever confusing one another's keys, so migrating from (EC)DHE to a hybrid is a strict improvement. Two further experiments address the draft's remaining concerns: reusing an ML-KEM key forfeits the forward secrecy that an ephemeral key preserves, and a principal acting as both initiator and responder exposes no role-confusion attack arising from the asymmetry. At the symbolic level, and under stated assumptions, the analysis substantiates the draft's case for preferring hybrid key exchange.

We present the first constant-expected-latency protocols for Interactive Consistency (IC), also known as Parallel Byzantine Broadcast, that achieve either: (1) security in dishonest majority, namely $t \leq (1-\varepsilon)n$ for any constant $\varepsilon\in \Omega(1)$; or (2) quadratic communication $O\!\left(n^2(L_{in}+\kappa)\right)$ in honest majority (i.e., $\varepsilon >1/2$). In IC, $n$ processes must agree on a vector that maps every honest process to its input of size $L_{in}$, despite up to $t$ dishonest (Byzantine) processes that may collude and behave arbitrarily. IC is the strongest one-shot distributed task: by fully determining the honest input configuration, it subsumes every other solvable one-shot task in the same model. Moreover, most multiparty computation protocols rely on IC as a building block. These guarantees are qualitatively optimal. First, Garay, Katz, Koo, and Ostrovsky (FOCS~2007) rule out constant-round protocols unless the honest fraction is constant. Second, Pease, Shostak, and Lamport (JACM~1980) rule out setup-free information-theoretic solutions once $n\leq 3t$. Thus, to overcome this barrier, we rely on cryptographic objects of size $\kappa$, obtaining correctness with all but negligible probability in $\kappa$ against any adversary running in time polynomial in $\kappa$. This includes digital signatures, for which the corresponding public keys must be published on a bulletin-board public key infrastructure before the protocol begins. Third, IC trivially requires \(\Omega(n^2L_{in})\) communication, since every honest process must learn the inputs of all honest processes. Our results follow from a single generic compiler that transforms any constant-expected-latency Byzantine Broadcast protocol into an IC protocol with the same latency profile.

This short note shows that the conventional (2-subset) bit-based division property trail search problem is NP-complete.

We study the inherent barriers to constructing non-adaptively sound succinct non-interactive arguments (SNARGs) for NP with a CRS whose length is sublinear in the witness length. Our results cover both the standard SNARGs and SNARGs with an additional updatable feature (i.e. incrementally verifiable computation for NP). - For updatable SNARGs, we show a black-box separation from falsifiable assumptions for uniform polynomial-time reductions, assuming sub-exponential hardness of learning with error. - For general SNARGs, we show a black-box separation from falsifiable assumptions for non-uniform polynomial-time reductions that only non-adaptively make an instance-size-independent number of queries to the adversary, assuming the existence of sub-exponentially secure super-bit generators. We observe that all known SNARG constructions from polynomial hardness of standard assumptions have 1-query soundness reductions. Thus, our result complements existing constructions. Previously, the seminal work [Gentry-Wichs, STOC'11] showed a black-box separation of SNARGs from falsifiable assumptions in the adaptive soundness setting. We explore whether any barriers exist in the non-adaptive setting. To obtain our result, we derive a simulation lemma for unbounded polynomial-length auxiliary inputs assuming super-bit generators.

We initiate the study of the algorithmic complexity of finding collisions in single-layer binary neural networks. Given a random matrix $\mathbf{A} \in \mathbb{R}^{m\times n}$, an input $\mathbf{x} \in \{-1,1\}^n$ is mapped to a binary output vector $\varphi(\mathbf{A}\mathbf{x})\in \{-1,1\}^m$, where $\varphi$ is an activation function with constant behavior on $[\kappa, \infty)$ for some threshold $\kappa \geq 0$. We identify the threshold scale $\kappa=\Theta(1/\sqrt{\alpha})$, where $\alpha=m/n$, as separating two complementary phenomena. When $\kappa \ll 1/\sqrt{\alpha}$, we give a simple online algorithm that efficiently produces extensive collisions. When $\kappa \gg 1/\sqrt{\alpha}$, for a natural randomized non-periodic activation and suitable oscillation complexity, we prove that the extensive-collision space exhibits an overlap gap property (OGP), yielding an exponential lower bound against online algorithms. Ours is the first work to use the overlap gap property as a rigorous criterion for collision resistance. The key difference between collision finding and average-case search is that collision finding has a new 'worst-case' aspect: the collision finder has full control over the choice of colliding pairs. Our lower bound is proved in the online model; extending such guarantees to broader classes of algorithms, including spectral, algebraic, lattice-based, or quantum methods, remains an open direction.

We construct a new framework for cryptographers to work with principally polarized abelian varieties (PPAVs). This framework offers a computational approach to abelian varieties agnostic to the choice of a coordinate system, culminating in the definition of an efficient model for principally polarised abelian varieties. We exhibit an instantiation of our framework by means of the theta model, thereby streamlining the documented capacities of the model, and extending them with new fundamental algorithms, like the computation of automorphism groups. Our framework focuses on what can be done with these objects, computationally, while relegating low-level considerations to the background, like the specific choice of a coordinate system (and thus the necessity to rely on Mumford's theory of theta coordinates). We illustrate the utility of our framework by proving that we can interpolate polarised isogenies in any dimension, generalizing to higher dimensions the most disruptive algorithm for elliptic curves in recent years. We prove that this interpolation offers a universal, canonical, and compact way to represent isogenies.

We introduce DASTE, a decentralized encryption primitive for auditable access control in settings where users independently generate public keys, register them on an immutable ledger, and decrypt only through collaboration. In DASTE, a sender encrypts under an access structure (e.g., an access tree / LSSS) whose leaves are concrete registered public keys selected at encryption time. A ciphertext can therefore be opened only by a qualifying coalition of registered key holders that jointly reconstructs the masking secret. DASTE is designed for dynamic policy-governed environments in which access conditions may need to change after encryption. To support this, we provide ciphertext-only policy evolution operations, including semantically neutral insertion, threshold escalation, subtree revocation, and ciphertext rerandomization, that update ciphertexts without reissuing user secret keys and without requiring plaintext access. We give two instantiations: a classical discrete-log-based construction, included as a conceptual baseline, and a post-quantum construction based on decisional Ring-LWE. For the RLWE construction, we prove coalition-bounded IND-CPA security via a standard hybrid argument. Together, these results yield a ledger-anchored, access-structured, post-quantum threshold encryption framework suitable for decentralized key management and governance-oriented decryption workflows.

The Fiat-Shamir transform is a central tool in cryptography and understanding its soundness is both a theoretically challenging and practically pressing question. Correlation intractable hash functions offer a method to instantiation Fiat-Shamir in the standard model. In short, a hash function is correlation-intractable for a relation $\mathcal{R}$ if it is computationally hard to find an input $x$ such that $\mathcal{R}(x, \mathsf{Hash}(x)) = 1$. In this work we present the first construction of a correlation-intractable hash function family, where the complexity of the hash does not depend on the complexity of the relation. Besides being better aligned with the way Fiat-Shamir is used in practice, our construction implies correlation intractability for all (possibly inefficient) batched searchable relations, i.e., searchable relations that can be decomposed as direct product of other searchable relations. Using complexity leveraging, we then compile our construction into correlation intractability for all batched relations. All of our results follow from the hardness of the decomposed short-integer solution (DSIS) problem, the natural search analogue of decomposed LWE, which we show to be at least as hard. As a direct consequence from prior work, our result implies that the parallel repetition of any three-message proof cannot be zero-knowledge (unless $\mathrm{BPP} = \mathrm{NP}$).

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

Unbiased and unpredictable randomness is a backbone of Web3 security, yet current Distributed Verifiable Random Function designs often entail a trade-off between performance and privacy. While established protocols like GLOW-DVRF achieve constant-size proofs, they rely on computationally expensive bilinear pairings that impose significant gas overhead in on-chain environments. Existing output-privacy frameworks, such as FlexiRand, are currently limited by the same expensive pairing-based operations that have high on-chain verification costs. In this paper, we present IcyVeil, an output-private DVRF that conjoins the architecture of FlexiRand with the pairing-free efficiency of Icy-DVRF. By integrating a blinding/unblinding mechanism directly into a FROST-inspired preprocessing scheme, IcyVeil enables users to mask inputs with a private nonce while the distributed committee generates partial evaluations and NIZK proofs over the veiled values. This approach eliminates the high cost of bilinear pairings during verification and maintains constant-size proofs. By adopting the pairing-free architecture of Icy-DVRF, IcyVeil inherits a 43% reduction in on-chain gas costs compared to conventional pairing-based protocols, establishing a scalable and cost-effective primitive for latency-sensitive applications such as decentralized gaming and asynchronous reward distribution.

In recent years, various RSA variants based on diverse algebraic structures have been proposed with the aim of enhancing its security. In this paper, we focus on type-A and type-B variants, which generalize RSA-type constructions over the ring of Gaussian integers modulo $N = pq$ and constructions based on the cubic Pell equation, respectively. First, we present a lattice-based method for finding, in polynomial time, solutions to the equation $xH(y)+cz\equiv 0 \bmod \beta$, where $H(y)$ is a monic polynomial, thereby generalizing previously established bounds. We then apply this method to factor the modulus in both type-A and type-B cryptosystems under multiple attack scenarios, such as partial key information attacks. Therefore, we provide certain bounds for the secret exponent under which these cryptosystems can be compromised.

Neural distinguishers for ARX ciphers can exploit information beyond classical difference distributions and several interpretability frameworks have been proposed. In this paper, we study two frameworks for SPECK32/64 by connecting their viewpoints: local constraints of modular addition and Fourier analysis of trained neural distinguishers. We show that the dominant Fourier parities of a raw-pair differential neural distinguisher can be rewritten in the local variables associated with the last modular addition. This representation separates value-dependent variant differential-linear terms from difference-dependent traditional terms, and explains their biases through specific local constraints and branch effects. We further extend the analysis to a boomerang right-quartet setting. We construct a neural distinguisher whose input is only the original ciphertext pair, while positive and negative samples are matched with respect to the observed ciphertext difference. Fourier analysis of this distinguisher reveals dominant value-dependent parities. We trace these terms to borrow synchronization in the first inverse step of the lower boomerang characteristic, yielding specific local conditions. Our results indicate that the dominant Fourier features learned in these settings are observable projections of concrete carry or borrow constraints of the ARX operation.

Private information retrieval (PIR) is a fundamental primitive for protecting user privacy. It enables a user to retrieve entries from a public database without revealing which entries are being retrieved. PIR has been studied in many settings, e.g., with information-theoretic or computational security, with a single server or multiple non-colluding servers, and with or without preprocessing to the database. In this article, we describe several PIR schemes that we believe are accessible to readers without prior knowledge in PIR. Although conceptually simple, these schemes capture the main ideas underlying mainstream design paradigms. We also describe extensions of PIR that support keyword queries and batch queries. Beyond describing the schemes themselves, we characterize the concrete efficiency of different PIR paradigms, provide guidance on selecting a paradigm in practice, and discuss practical applications of PIR. We hope this article helps readers understand the current research landscape in PIR and serves as a starting point for exploring more advanced topics in the field.

We introduce baseSPIDER and SPIDER, private information retrieval (PIR) schemes that embody two technical advancements. The baseSPIDER protocol operates with a single server and a stateful client that performs pre-processing and stores hints for future queries. In this setting, baseSPIDER introduces a new approach that matches the asymptotically optimal communication complexity of state-of-the-art schemes while improving constant factors--an advantage that is particularly significant for databases with large entries. In addition, baseSPIDER offers a conceptually simpler design relative to prior protocols. SPIDER operates over a default database interface and requires no cooperation from the server at any stage. To our knowledge, SPIDER is the first single-server PIR construction of this design, achieving privacy without specialized APIs, auxiliary server state, or protocol-specific interaction beyond conventional indexed access. SPIDER is built via a simple transformation of baseSPIDER to the default server setting, eliminating deployment barriers and enabling immediate applicability to existing systems. This transformation can be applied more broadly to three recent PIR solutions, adapting them for use in the default-server paradigm and yielding solutions of independent interest. SPIDER compares to the resulting modified solutions by exhibiting a simpler design while incurring higher client computational work.

Many modern SNARK constructions follow a paradigm that combines a Polynomial Interactive Oracle Proof (PIOP) with an appropriate Polynomial Commitment Scheme (PCS). In this paradigm, the PIOP reduces soundness to the verification of a collection of polynomial relations that are checked though oracle queries, while the PCS enables succinct commitments to the corresponding polynomials. Rather than transmitting the full polynomial representation, the prover commits to the polynomials and later provides evaluations at the points selected by the verifier. The verifier checks the consistency of these evaluation with the commitments and the prescribed polynomial relations. This combination of interactive polynomial queries and succinct commitments lies at the heart of the resulting argument system's efficiency, leading to compact proofs and efficient verification procedures. Focusing on this paradigm, we adopt the frontend and backend decomposition of SNARKs for general computation introduced by Thaler and develop a unified framework that refines this separation at a finer granularity. We present this framework as a single coherent structure and analyze its components in a systematic manner. Within this unified view, we incorporate lookup arguments and recursive proof composition, both of which are key to improving efficiency and applicability, as main components of the framework, showing how they interact with both the frontend and backend. This organization allows readers to reason clearly about the construction, composition and analysis of modern SNARKs.

A garbling scheme encodes a function and an input into two independent artifacts from which the output can be recovered, but nothing else is revealed. This clean separation between function and input has made garbling one of the most versatile primitives in cryptography. Yet it hides an asymmetry that has gone largely unexamined: while the input is cryptographically protected, the function is fully exposed to whoever performs the garbling. As garbling is increasingly deployed in settings where garbling is delegated to untrusted infrastructure, published on public ledgers, or distributed among multiple parties, this asymmetry becomes a fundamental barrier. The function, which may encode proprietary models, confidential policies, or sensitive decision logic, is leaked unconditionally to the garbling server. We introduce oblivious garbling, a new paradigm that closes this gap. In our framework, the garbler receives only a designated leakage of the circuit and remains oblivious to everything else. We present the first construction instantiating this notion where the leakage is the circuit topology alone, achieving linear complexity with no blow-up in the size of the garbled circuit. The construction extends to the malicious setting with no asymptotic overhead. Beyond its theoretical contribution, oblivious garbling has immediate practical consequences: it enables outsourced garbling without function exposure, garbling on untrusted hardware without leaking proprietary logic, and a multi-party garbling protocol in which no garbling party learns the function, all without resorting to universal circuits.

Side-channel attacks are a relevant threat to many modern cryptographic schemes and often have fatal consequences such as revealing partial information about secret keys. While leakage-resilient cryptography aims to solve this problem, existing works focus exclusively on showing security against classical leakage. Moreover, recent public key encryption (PKE) schemes utilizing quantum secret keys achieve security against unbounded classical leakage, but offer no guarantees on any amount of quantum leakage. Since security guarantees on classical side information do not necessarily translate to guarantees on quantum side information, showing PKE schemes that are secure in the presence of quantum leakage remains open. In this work, we address this problem by extending the definition of leakage resilience for PKE in the bounded-leakage model to allow for quantum leakage. We provide the following two constructions: - PKE with Quantum Secret Keys: We construct a PKE scheme that tolerates unbounded classical leakage alongside bounded, constant-rate ($\lambda <0.057$) quantum leakage. Our construction assumes the existence of polynomially secure post-quantum indistinguishability obfuscation (iO) as well as one-way functions (OWFs). - PKE with Classical Secret Keys: We construct a classical PKE scheme that is secure against bounded quantum leakage. Our construction offers a tradeoff between the achievable leakage rate and the underlying cryptographic assumptions. Assuming the hardness of the learning with errors problem (LWE) we obtain an optimal leakage rate of $\lambda \leq 1-o(1)$. Alternatively, assuming only post-quantum PKE, we obtain a leakge rate of $\lambda\leq \frac{1}{poly(n)}$.

The idea of Hybrid Homomorphic Encryption (HHE) is to reduce the computational cost of Fully Homomorphic Encryption (FHE) by encrypting bulk data symmetrically while only encrypting the short symmetric key homomorphically. Its efficiency depends on the multiplicative depth of the symmetric cipher's decryption circuit, motivating FHE-friendly designs. The Learning Parity with Noise (LPN) problem is a natural candidate for such designs, as it gives rise to simple encryption and decryption circuits over binary fields. In this context, Fouque, Hadjibeyli, and Kirchner proposed LPN-based symmetric encryption schemes based on the LPN-C cryptosystem of Gilbert et al. LPN-C is attractive for HHE while allowing parameter choices that bound decryption failures. However, the concrete security of LPN-C and its HHE-oriented variants remains poorly understood. We quantify how enforcing bounded noise via rejection sampling reduces the observed noise rate, an effect not captured in prior analyses. This yields immediate speedups for all attacks based on LPN instance solving. We then extend the Arora-Ge-style algebraic attacks to the bounded-noise setting and derive new bounds on the dimension of the induced linear spaces, refining and partially correcting earlier analyses. We show that some parameter regimes are more robust than previously estimated, while new algebraic strategies yield the best known attacks in others. Overall, our results improve our understanding of the concrete security of LPN-based symmetric encryption schemes, informing parameter selection for FHE-friendly variants.

In 2020 and 2024 respectively, NIST released a Special Publication (SP 800-208) and a Federal Information Processing Standard (FIPS 205) specifying hash-based signature schemes with natural quantum resistance thanks to their symmetric foundation. The former recommends the stateful hash-based signature schemes LMS and XMSS, whereas the latter standardizes their stateless counterpart SPHINCS+. While in principle all three constructions can be instantiated with any secure cryptographic hash function, the concrete instances recommended by NIST are currently limited to either the SHA-2 or the SHA-3 family. Building on the maturity of these standardized families is of course a sensible choice. Yet, we argue that neither is particularly well suited for this purpose, especially once physical security matters. As an alternative we suggest pSquare-hash, an arithmetization-oriented family of lightweight tweakable hash functions. We demonstrate that such dedicated tweakable constructions ideally suit the instantiation and security requirements of hash-based signature schemes, potentially leading to efficiency advantages over standard concatenation-based approaches through either a reduction of the permutation size or the number of calls. With respect to physical security, the presence of the tweak enables a clean separation between inputs that need to be protected against leakage/faults and those that are insensitive. The arithmetization-oriented nature and choice of prime enable the effective utilization of masking schemes with superior passive and active attack resistance (e.g., prime-field and/or inner-product masking) and keep the design suitable for zero-knowledge applications. We compare higher-order masked software (Cortex-M4) and hardware (NanGate 15 nm) implementations of pSquare-hash to equivalent SHA-2, SHA-3, SKINNY-Hash, Ascon-Hash and Poseidon2 instances and exhibit favorable characteristics whenever masking is applied.

Shor's algorithm represents the main threat of quantum computers to cryptography. In order to precisely understand its feasibility, many authors have worked towards reducing its costs, either at the logical level (assuming a fault-tolerant architecture), or at the physical level (taking into account the constraints of envisioned hardware). In particular, recent works by Chevignard et al. (CRYPTO 2024) and Gidney (arXiv 2025) used improved arithmetic to significantly reduce the qubit cost of factoring RSA public keys. Even more recently, Babbush et al. (arXiv 2026) improved the cost of computing elliptic curve discrete logarithms, with a reduction of a factor 2 to 3 in gate count and qubit count compared to a previous work by Litinski (arXiv 2023). Their result relies on optimized point addition circuits on elliptic curves over prime fields. However they did not reveal their logical quantum circuits, relying instead on a zero-knowledge proof. In this paper, we detail a quantum logical circuit architecture which gives similar results as Babbush et al., with a slightly higher number of qubits (around 1.5% increase) and a slightly smaller Toffoli gate count (between 6.5% and 10% reduction) for the curve secp256k1. We also give gate counts for a generic variant of the circuit, which is valid for any prime field.

We explicitly construct and benchmark the first lattice-based IVC scheme from folding. The scheme supports customizable constraint systems over rings which we exploit to obtain proofs of correct execution of an FHE bootstrapping, a critical component of verifiable FHE. Notably and of independent interest, we introduce a novel CCS relation capable of performing automorphism stability checks which yields better expressivity for CCS over rings. We use this new relation to arithmetize the folding scheme verifier as well as TFHE's bootstrapping operation, and measure the performance of our folding scheme implementation on this arithmetization. Benchmarks indicate smaller proofs compared to the state of the art at the cost of a sharp increase in prover and verifier time. Lastly, we consider the security of folding-based IVC schemes with a super-constant number of recursive rounds and give an argument for the knowledge soundness of our construction in the ROM. Our work also discusses and highlights key open questions for future work, such as the design of hash functions over rings that permit efficient arithmetizations.

Pseudo-random correlation generators based on the Quasi-Abelian syndrome decoding problem were first attacked in an article published at Asiacrypt~2025, using compressed sensing. In this paper, we revisit the security of the problem using a more traditional cryptanalytic tool, namely correlation attacks. As a result, we get a new cryptanalysis which outperforms the attack from Asiacrypt 2025 in several directions. It allows recovery of secret error polynomials with larger Hamming weights, runs approximately $1\,000$ times faster and uses $1\,000$ times less memory over $\mathbb{F}_3$. Over $\mathbb{F}_4$, the speed-up and memory gain are even higher. Due to this new attack, it becomes necessary to entirely revisit the parameters of several pseudo-random correlation generator proposals, including FOLEAGE.

Threshold cryptography distributes trust among multiple parties by enabling joint cryptographic operations without reconstructing secret keys. While post-quantum signature schemes based on the MPC-in-the-Head (MPCitH) paradigm are highly generic, recent impossibility results show that their thresholdization either incurs prohibitive distributed symmetric computations or leads to signature sizes growing with the number of signers. Achieving practical tradeoffs in this setting remains challenging. In this paper, we propose a generic framework for threshold MPCitH signatures based on Merkle-tree commitments. Our approach adapts the PIOP+PCS paradigm to the distributed setting by introducing and instantiating the notion of threshold polynomial commitment schemes (TPCS). We present a generic compiler combining a PIOP, a TPCS, and an arithmetic black box into a threshold signature scheme, and prove its unforgeability from the security of its components. We further provide a concrete Merkle-tree-based TPCS achieving moderate signature-size overhead, as low as 200 bytes per signer at the 128-bit security level. This is to be compared with an overhead of roughly 2 kB per signer for the previously suggested approach to thresholdize MPC-in-the-Head based on GGM trees. By compiling this TPCS with a standard PIOP, we obtain a generic threshold signature scheme from any hard problem or one-way function, which we showcase MQ-based and AES-based instantiations.

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