With the widespread adoption of Field Programmable Gate Arrays (FPGAs) in security-critical industries such as defense and telecommunications, ensuring the confidentiality of sensitive data processed by these devices has become paramount. Side-Channel Analysis (SCA) poses a significant threat, necessitating the protection of cryptographic primitives through effective and efficient countermeasures. Within the framework of well-established formal adversary models, Boolean masking offers provable resistance to SCA by randomizing sensitive intermediate computations using Shamir’s secret sharing. However, the secure and efficient implementation of Boolean masking in hardware presents a complex and error-prone challenge. Physical effects such as glitches, transitions, and couplings can undermine essential security assumptions, potentially weakening the effectiveness of masking. Although robust masking schemes are designed to maintain their security in the presence of glitches and transitions, and their secure implementation can be verified at the gate level using a wide range of automated verification tools – albeit mostly for Application-Specific Integrated Circuits (ASICs) and not FPGAs – leakages caused by coupling effects remain undetectable by such tools, as they occur at a lower abstraction level. In this work, we focus on detecting (low-level) vulnerabilities in masked FPGA designs through experimental and tool-assisted evaluation. The flaws that we target are not detectable at the Register Transfer Level (RTL ) level, and in some cases, not even at the gate level, as they arise from optimizations introduced during synthesis or implementation, or from the specific outcomes of the Place and Route (PnR) process. We demonstrate that these flaws are not only theoretically concerning, but can lead to observable leakages in practical experiments. Furthermore, we show how to formally abstract, unveil, and mitigate such leakages, thereby enabling a security-aware FPGA design flow that spans from the behavioral to the physical level. As an example, we implement all the evaluation steps presented as an extension of PROLEAD and validate its accuracy and effectiveness through practical case studies.

Many Identity-Based Encryption (IBE) schemes rely on the hardness of the Discrete Logarithm Problem, making them vulnerable to quantum attacks. In recent years, lattice-based cryptography has emerged as a source of Post-Quantum cryptosystems, for example with Kyber, Dilithium and Falcon chosen by NIST to be standardized as ML-KEM, ML-DSA and FN-DSA. Some IBEs have also been proposed over lattices, but they can still be considered as interesting theoretical constructions, the community's attention having been more on the NIST competition than on optimizing IBEs, assessing their security, and protecting them against physical attacks. So, in this paper, we build a new IBE scheme from the basic blocks of the highly studied ML-KEM, ML-DSA and ModFalcon, to put both their maturity and efficiency at the benefits of IBE. More precisely, we leverage the Module-NTRU trapdoor from ModFalcon to enable extraction of secret keys, we use the encryption and decryption algorithms from ML-KEM, and the modular arithmetic and Number-Theoretic Transform from ML-DSA. Therefore, being able to reuse code from widely deployed schemes, our IBE is much easier to implement and maintain in practice, and can benefit from existing (and future) optimizations, hardware accelerators, and side-channel protections, with very little to no additional work. We also prove the IND-sID-CPA-security of our scheme under standard assumptions, and precisely describe the algorithms and the choice of concrete parameters.

Secure key leasing (SKL) is an advanced encryption functionality that allows a secret key holder to generate a quantum decryption key and securely lease it to a user. Once the user returns the quantum decryption key (or provides a classical certificate confirming its deletion), they lose their decryption capability. Previous works on public key encryption with SKL (PKE-SKL) have only considered the single-key security model, where the adversary receives at most one quantum decryption key. However, this model does not accurately reflect real-world applications of PKE-SKL. To address this limitation, we introduce collusion-resistant security for PKE-SKL (denoted as PKE-CR-SKL). In this model, the adversary can adaptively obtain multiple quantum decryption keys and access a verification oracle which validates the correctness of queried quantum decryption keys. Importantly, the size of the public key and ciphertexts must remain independent of the total number of generated quantum decryption keys. We present the following constructions: - A PKE-CR-SKL scheme based on the learning with errors (LWE) assumption. - An attribute-based encryption scheme with collusion-resistant SKL (ABE-CR-SKL), also based on the LWE assumption. - An ABE-CR-SKL scheme with classical certificates, relying on multi-input ABE with polynomial arity. - An adaptively secure identity-based encryption scheme with collusion-resistant SKL based on the LWE assumption.

Designated Verifier zero-knowledge Succinct Non-Interactive Arguments of Knowledge (DV-zkSNARKs) are cryptographic argument systems in which the ability to verify proofs is restricted to a designated verifier. Unlike publicly verifiable zkSNARKs, these constructions ensure that only an authorized party can validate the correctness of the proof. Existing lattice-based DV-zkSNARK constructions typically rely either on linear-only encryption or on the Linear Targeted Malleability (LTM) assumption. The former has been cryptanalytically broken and therefore no longer provides a credible basis for post-quantum security. The latter is a non-standard and comparatively less established assumption and, moreover, restricts knowledge soundness to the non-adaptive setting. To overcome these limitations, we propose an inner-product argument system whose security relies solely on the well-established hardness of the Module Short Integer Solution (MSIS) problem and that achieves adaptive knowledge soundness in the random oracle model. This construction enables a designated verifier, holding a secret key, to succinctly verify inner product of a committed witness with an arbitrary vector. By combining our argument system with a linear probabilistic checkable proof (LPCP) compiler, to the best of our knowledge, we obtain the first DV-zkSNARK construction based on standard assumptions. Our implementation achieves prover and verification times comparable to the state of the art, while reducing public parameter size by a factor of 10, at the cost of a 2.5x increase in proof size.

Recently, Boyle, Jain, Servan-Schreiber, and Srinivasan (EUROCRYPT 2025) introduced the notion of simultaneous-message and succinct (SMS) secure computation. In an SMS protocol, after an initial sampling of a common reference string (CRS), two parties—Alice (with a large input) and Bob (with a small input)—can simultaneously exchange encodings of their private inputs and obtain additive shares of the output of a function evaluated over their inputs. The key requirement is succinctness: namely, the sizes of the CRS and each input encoding grow only polylogarithmically in the size of Alice's input and the function output. Boyle et al., and independently Abram, Malavolta, and Roy (STOC 2025), constructed SMS for all bounded-depth Boolean circuits from the plain learning with errors (LWE) assumption. In this work, we extend the study of SMS along two new dimensions: Reusable SMS: In this setting, the same input encodings can be reused to compute multiple functions. Multiparty SMS: In the multiparty setting, we consider computations over one large input and multiple small inputs. Succinctness in this case means the size of the CRS and input encodings can grow with the total length of the small inputs (but polylogarithmically with the length of the long input and the size of the function output). Assuming polynomial hardness of LWE (with a sub-exponential modulus-to-noise ratio), we construct reusable two-party SMS for all bounded-depth Boolean circuits with polylogarithmic communication. By additionally assuming indistinguishability obfuscation, we present a generic compiler from reusable two-party SMS to reusable multiparty SMS. Our construction of reusable two-party SMS from LWE relies on a new "dual-use" technique where we reuse an LWE secret key between a lattice-based algebraic homomorphic MAC and a lattice-based homomorphic encryption scheme. This dual-use technique allows us to bootstrap a reusable SMS protocol for quadratic functions into one that supports arbitrary (bounded-depth) Boolean circuits. Along the way, we also show how to adapt a previous lattice-based algebraic homomorphic MAC based on ring LWE to obtain one based on the plain LWE assumption.

A major challenge in elliptic curve cryptosystems consists in efficiently mitigating the small-subgroup attack. This paper explores batch subgroup membership testing (SMT) on pairing-friendly curves, particularly for the Barreto–Lynn–Scott family of embedding degree 12 (BLS12) due to its critical role in modern pairing-based cryptography. Our research introduces a novel two-step procedure for batch SMT to rapidly verify multiple points at once, cleverly combining the already existing tests based on the Tate pairing and a non-trivial curve endo- morphism. We clarify why the invented technique is significantly faster (despite a negligible error probability) than testing each point individu- ally. Moreover, it is applicable to prominent curves like BLS12-381 and BLS12-377 being frequently employed in zero-knowledge applications. Nonetheless, to further enhance the speed (or reduce the error proba- bility) of the proposed batch point validation, we have generated two new BLS12 curves that are specifically optimized for this purpose. We also provide an open-source high-speed software implementation in Go, showcasing significant performance improvements achieved by our work.

Cryptographic hardware implementations often leak secret information through side channels. This can allow attackers to learn secret data, such as a cryptographic key, without any vulnerability in the cryptographic algorithm itself. A popular countermeasure to such attacks is masking, which ensures that processed data is independent of the secrets by splitting them into multiple independent shares, often at the cost of significant overhead in terms of required area, latency, and randomness. The composable PINI notion in the glitch-extended probing model ensures some degree of security against such side-channel analysis attacks, and guarantees that the circuit may be arbitrarily composed with other PINI circuits while maintaining the same security level. This allows for the secure implementation of arbitrary circuits using trivial composition, replacing elementary gates with "gadgets" realizing the same functionality in a PINI-secure manner. Up to now, PINI gadgets at arbitrary security order are limited to quadratic functions, i.e., 2-input gates, with the best known as HPC3.X realizing a 2-input multiplier in one clock cycle. In this work, we present HPCC, the first low-latency 3-input multiplication gadget for arbitrary fields that maintains a constant latency of one cycle, independent of the number of shares. HPCC additionally allows for the computation of any number of multiplications in a single cycle with relatively little overhead when two of the three operands are identical. When instantiated with two shares and for $\mathbb{F}_2$, HPCC halves the previous record for lowest number of fresh masks required at comparable area cost. With more shares, HPCC is the only single-cycle gadget realizing 3-input multiplications in arbitrary fields. We leverage HPCC to implement the first composable AES S-Box with two cycles of latency with an arbitrary number of shares. This S-Box design significantly outperforms the previous record in terms of area and randomness when instantiated with three shares and stands as the only two-cycle solution for more shares.

AESpolyW, proposed at IEEE S&P 2026, is a wide-block encryption mode designed to exploit instruction-level parallelism between AES and polynomial hashing. Although AESpolyW achieves high throughput and outperforms HCTR2 and EME on most tested platforms, we show that AESpolyW does not achieve strong tweakable-PRP security. Our attack requires only two encryption queries and one decryption query, and distinguishes AESpolyW from an ideal tweakable permutation with advantage close to one. We further show that this weakness directly compromises Encode-then-Encipher authenticated encryption (AE) instantiated with AESpolyW. For the appended-zero, prepended-zero, and inserted-zero variants, we construct fresh ciphertext forgeries that are accepted with probability one. The same attacks also yield chosen-ciphertext plaintext disclosure and complete IND-CCA breaks. These results are structural and do not rely on any weakness of AES, the polynomial hash, or PHASH.

Deep Learning-based Non-profiled Side-Channel Analysis (DL-NSCA) enables automatic feature extraction without a profiling device, but existing approaches mainly target non-linear operations, requiring prior knowledge of the algorithm's unique non-linear structure and computable non-linear intermediate values. These limit applicability in analyzing proprietary or undisclosed implementations and in settings where plaintext/ciphertext are masked by unknown randomness (e.g., tweaks or nonces). We observe that linear operations are fundamental as common cryptographic primitives appearing at the beginning or end of algorithms in conjunction with the secret key, and are widely used to mask sensitive input/output. Motivated by this observation, we propose a new DL-NSCA perspective that targets the outputs of linear operations, referred to as symmetric leakage, to enable cross algorithm attacks. The main limitation of the prior distinguisher lies in their reliance on a simplistic correspondence between deep learning metrics and side channel information. This leads to two issues: the effectiveness of the distinguisher varies significantly with the chosen training epoch, and a wrong key inducing a negative correlation may be indistinguishable from the correct key under symmetric leakage. To address this, we provide a formal algebraic characterization of the relationship between the structure of the leakage function and the number of maxima given from the distinguisher. Guided by this theory, we propose a new distinguisher, VS-GBA, an epoch-invariant distinguisher that interprets SCA information from deep learning metrics and approaches the theoretical optimum. It is applicable to both the asymmetric leakage and symmetric leakage through a structure-aware screening criterion. Our experiments show that, on the high-noise 32-bit ARM Cortex-M4 device, when the core operations are protected, asymmetric leakage analysis fails to recover the keys for all three evaluated algorithms within the maximum trace budget (GE=70 for masked AES, GE=27 for masked PRESENT, and GE=66 for masked ASCON). In contrast, VS-GBA, which targets symmetric leakage, recovers the key with a 100% success rate using 8,000, 8,500, and 16,000 traces, respectively. Furthermore, we present a DL-NSCA attack on XTS-AES (NIST SP 800-38E), extending DL-NSCA to scenarios where plaintext/ciphertext is masked by a secret tweak.

This work resolves the open problem of whether verifiable delay functions (VDFs) can be constructed in the random oracle model.A VDF is a cryptographic primitive that requires a long time to compute (even with parallelization), but produces a unique output that is efficiently and publicly verifiable. We prove that VDFs do not exist in the random oracle model. This also rules out black-box constructions of VDFs from other cryptographic primitives, such as one-way functions, one-way permutations and collision-resistant hash functions. Prior to our work, Mahmoody, Smith and Wu (ICALP 2020) prove that \emph{perfectly unique} VDFs (a much stronger form of VDFs) do not exist in the random oracle model; on the other hand, Ephraim, Freitag, Komargodski, and Pass (Eurocrypt 2020) construct VDFs in the random oracle model assuming the hardness of repeated squaring. Our result is optimal -- we bridge the current gap between previously known impossibility results and existing constructions. We initiate the study of \emph{proof of work functions}, a new cryptographic primitive that shares similarities with both VDFs and proof of works. We show that a stronger form of it does not exist in the random oracle model, leaving open the fascinating possibility of a random-oracle-based construction.

We present a low-stack implementation of the module-lattice signature scheme \(\mathrm{HAETAE}\), targeting microcontrollers with \(8\,\mathrm{kB}\)–\(16\,\mathrm{kB}\) of available SRAM. On such devices, peak stack usage is often the binding constraint, and \(\mathrm{HAETAE}\)'s hyperball-based sampler, large transient polynomial vectors, and variable-length signature payloads (hint and high-bits arrays) pose a particular challenge. To address this, we introduce (i) rejection-aware pass decomposition, which isolates encoding to the post-acceptance path; (ii) component-level early rejection, which short-circuits the response computation when a partial norm already exceeds the bound; and (iii) reverse-order streaming entropy coding using range Asymmetric Numeral Systems (rANS), which eliminates full hint and high-bits staging buffers. Combined with streamed matrix generation, a two-pass hyperball sampler with streaming Gaussian backend, and row-streamed verification, these techniques bring signing stack usage from \(71\,\mathrm{kB}\)–\(141\,\mathrm{kB}\) in the reference implementation down to \(5.8\,\mathrm{kB}\)–\(6.0\,\mathrm{kB}\), key generation to \(4.7\,\mathrm{kB}\)–\(5.7\,\mathrm{kB}\), and verification to \(4.7\,\mathrm{kB}\)–\(4.8\,\mathrm{kB}\) across all three security levels. Our pure C implementation covers all three security levels (\(\mathrm{HAETAE}\)-2/3/5), whose optimization paths differ due to the public-key domain (\(d > 0\) vs. \(d = 0\)) and rejection structure. We implement our optimization on a Nucleo-L4R5ZI and compare it to the reference `pqm4` implementation (for \(\mathrm{HAETAE}\)-2 and -3) and to a recently published memory-optimized implementation (targeting \(\mathrm{HAETAE}\)-5 only). We reduce \(\mathrm{HAETAE}\)-2, -3, and -5 stack usage by respectively \(75\%\), \(86\%\), and \(8\%\) for key generation, \(92\%\), \(95\%\), and \(24\%\) for signature generation, and \(85\%\), \(91\%\), and \(22\%\) for verification. Depending on the parameter set, this impacts performance by at most a factor of \(1.8\) and \(3.4\) for key generation and signature generation, respectively, while even offering a performance improvement of up to \(18\%\) for verification. Verification at all security levels fits within \(8\,\mathrm{kB}\) of RAM (signature buffer + stack) and is \(2.34\)–\(3.34\times\) faster than ML-DSA m4fstack at each comparable security level. We additionally validate portability under RIOT-OS on ARM Cortex-M4 and RISC-V targets.

This paper formalizes the Deterministic State Machine, or DSM, as a guarded, linear, forward only, constraint based computation model. DSM does not require a blockchain, validator set, sequencer, gas market, mempool, clock based ordering rule, or global consensus layer for ordinary state evolution. State validity is determined by local verification of cryptographically precommitted candidate futures, deterministic fulfillment guards, explicit resource consumption keys, canonical encodings, signatures, and Sparse Merkle Tree commitments. The architectural shift is that finality moves from a network decision to a state property. Instead of requiring some external party, committee, sequencer, validator set, or global clock to agree that a transition happened, DSM asks whether the proposed transition consumes the committed state resource and advances it deterministically. If it does, the successor is locally realized. If it does not, it is not state. Finality is therefore not provided as a service by an ordering network; it is a consequence of the consumed resource itself. This is global realization without global ordering: local acceptance composes into a coherent realized history because incompatible histories cannot merge. The central claim is not that DSM forbids all branching at the level of precommitment. DSM explicitly permits precommitment forking. Multiple candidate futures may be prepared for a common parent, including Deterministic Limbo Vault release paths, refund paths, hash fulfillment paths, recovery paths, abort paths, contingent payment paths, CPTA token operations, offline bearer steps, and other mutually exclusive branches. The invariant is: multiple futures may be described, but for a fixed consumed resource, at most one may be realized. A resource is the thing that produces exactly one realized successor. A relationship parent, spendable object, vault generation, token balance object, source vault generation, recovery generation, or offline anchor step is a resource in this sense. Candidate branches are only possible futures. Realization consumes the resource. A generation is a logical version of a resource family. It is not a time period, not a clock interval, not a scheduling unit, and not an external ordering coordinate. Generations are ordered only by DSM derivability and resource consumption. This paper makes explicit the machinery required for that statement. Guard exclusivity is not left as convention. A DSM precommit set is valid only if its guard family is well formed. A well formed guard family gives either a deterministic branch selector, a mechanically proven exclusive guard class, or a set of branch predicates that are structurally tied to the same consumed resource. Parent consumption is modeled through canonical resource consumption keys and a consumed parent set committed by the DSM root. Branch local keys may exist for indexing or audit, but the shared resource key is what enforces linear exclusion. A hardened form of the model is also stated: for any conflict class, all conflicting candidates must resolve to an identical canonical resource consumption set, and those keys must be derived from the committed parent state rather than supplied as discretionary branch data. This removes the implementation hazard where release, refund, recovery, or policy branches accidentally consume different keys. The role of guard exclusivity is clarified. Pairwise guard exclusivity is useful and required for guard classes that claim exclusive fulfillment, but it is not the only safety mechanism. When conflicting branches share the same derived resource consumption key set, linearity alone prevents co realization even if several guards are simultaneously fulfilled. Thus the load bearing safety rule is not merely that guards should not overlap. The load bearing safety rule is that conflicting futures must fight over the same derived resource. Tripwire is formalized as the theorem that two conflicting realized successors from the same consumed resource cannot both be derivable. More precisely, conflicting candidates may be constructed or transmitted as bytes, but they cannot both validate under the DSM step predicate and cannot both go through as accepted state transitions for the same consumed resource. Forks are therefore not selected against by consensus. They are excluded by guarded realization and exposed by reconciliation if conflicting invalid bytes are presented outside the valid model. Offline bearer mode is treated as an optional mode predicate, and this revision states its corrected form. Transfer uniqueness, including offline transfer uniqueness, is a software theorem of the guarded linear kernel. An SMT committed anchor counter makes the offline origin an explicit coordinate of the committed state, every offline candidate from that origin consumes the same derived anchor step resource key, and realized history uniqueness applies without a hardware term. Hardware is thereby demoted to the one job software cannot perform: uniqueness of the physical device instance. Every offline release carries a three factor identity witness, a seed rooted DSM signature, a PUF rooted non exportable chip signature, and a partition sealed host signature over the same root advance message, and the physical monotonic counter survives only as a tracker of the SMT counter: a non rewind floor, a stale image tripwire, and an offline exposure cap. The receiver witnessed counter positioned commit of earlier drafts is superseded: a scalar counter read never binds the transition it brackets, and the binding was never needed. The safety theorems of this paper are supported by machine checked artifacts. The general key scoped fork exclusion theorems are proved in Lean 4 over an abstract guarded model, with the uniqueness and Tripwire core depending on no axioms. A companion TLA${}^{+}$ development model checks the same statements in both a per state form and a realized history form on concrete guard families, and by deliberate falsification of a malformed family confirms that guard family well formedness is load bearing. A relationship scoped model checks that same parent multi receiver forks are unconstructible in online DSM. Appendices A and B point to these artifacts. Their exact scope and boundary are stated in the Claim Boundary section.

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.

NAT is widely assumed to conceal the private IP addresses of internal clients from both off-path attackers within the same LAN and external observers. We show that this assumption does not hold. We present a novel off-path deanonymization attack that infers the private IP addresses of NATed clients engaged in active TCP connections with a remote server. Our attack builds on known NAT behaviors in real-world Wi-Fi routers, such as port preservation, insufficient reverse-path validation, and the absence of TCP window tracking, previously shown to enable off-path TCP hijacking. By inferring a NATed client’s private IP address, our attack defeats the anonymity commonly attributed to NAT, creating a persistent privacy leak that enables deanonymization and user profiling. We validate the attack on 6 Wi-Fi routers and 2 real-world Wi-Fi networks using SSH and HTTP/HTTPS traffic over TCP, finding that 5 of the 6 routers and both networks are vulnerable.

LESS is a code-based signature scheme built on the linear equivalence problem and, in its v2.0 round-2 form, a candidate in the NIST call for additional post-quantum signatures. No microcontroller implementation of it has been reported: the official benchmarking effort for the additional signatures excluded it on memory grounds, and an x86-massif cross-check puts the reference's peak stack at up to $\approx 836$~KB---beyond the SRAM of even the largest mainstream Cortex-M4. This paper provides the first such implementation, to the best of our knowledge---a complete characterization of LESS (v2.0) on the Arm Cortex-M4 across all seven parameter sets. NIST did not advance LESS to the third round in May 2026; we develop the implementation techniques and the evaluation methodology to outlast that outcome. We map the speed--memory design space with three operating points, all byte-identical to the NIST known-answer tests. The primary point is a \emph{balanced} configuration signing $4.1$--$4.3\times$ faster than the platform-normalized reference while using $41$--$59\%$ less peak stack. With double-pass signing at category~5, it is the only configuration whose signing we measured on target across all seven sets---at category~5, the resident-matrix configurations exceed the device's 640~KB of SRAM. It is flanked by a \emph{speed ceiling} at $4.5$--$4.7\times$ (at reference-level memory) and a \emph{memory floor} that signs with about a one-kilobyte measured stack at only $1.2$--$1.5\times$ reference time at category~1, with key generation on par with or below reference cost---so at category~1, memory minimization is nearly free. The speedups rest on three increasingly platform-specific layers: algorithmic restructuring, intrinsic-free two-lane SWAR (SIMD-within-a-register) arithmetic for $\mathbb{F}_{127}$ with a lazy-reduction scheme, and hand-scheduled assembly kernels---including a rank-2 row-elimination kernel---together with a systematic audit of all kernels against the Cortex-M4 timing rules. Read against the reference's own profile, these results indicate that implementation maturity, not the scheme, accounts for a $>4\times$ swing in achievable microcontroller signing---a data point for standardization-time performance evaluation, offered without revisiting the decision. We further report a catalog of negative results (techniques that help on desktop SIMD but hurt on the M4) and an alignment-safe transpose that returns $\approx 170$~KB of static memory to the stack under an \texttt{-O3} build. The evaluation methodology---Pareto-monotone adoption criteria, byte-identical correctness gates, and coverage and ablation reporting---transfers to the surviving third-round candidates, for which NIST has explicitly called for constrained-device evaluation.

The California Consumer Privacy Act (CCPA) grants consumers the right to request deletion of personal data held by registered data brokers. California’s 2023 Delete Act provides a new mechanism through which consumers can exercise this right by leveraging a centralized Delete Request and Opt-out Platform (DROP), enabling users to submit a single request that must be periodically processed by all registered data brokers. Since this platform aggregates sensitive user information, it is intentionally designed with safeguards against information leakage and unauthorized disclosure. This legislation, and the system it introduces, are positioned to serve as a template for wider deployment, with copy-cat legislation already introduced in many US states. In this document, we evaluate the privacy architecture of the first-generation DROP system from a cryptographic perspective. The proposed design relies on hash-based record linkage---a widely used technique that offers heuristic rather than rigorous privacy guarantees. We begin by analyzing the inherent risks of this approach and identifying simple, lightweight modifications that can modestly improve its privacy guarantees by making it more difficult for malicious actors to exploit these vulnerabilities. We then contrast this approach with Private Set Intersection (PSI), a class of provably secure cryptographic protocols that only reveal the intended matching records and nothing more. For future iterations of DROP, we propose a comprehensive PSI-based redesign, arguing that it would substantially reduce the risk of accidental information leakage while incurring only moderate additional computational overhead. Next, we highlight how DROP presents a compelling application for advanced variants of PSI with extended functionalities and stronger security guarantees, and we outline several research directions for the cryptography community, motivated by the unique requirements of such systems. Finally, we identify systemic risks that cannot be mitigated by PSI alone and discuss potential complementary approaches for addressing these broader challenges. We hope this document serves as a common starting point for the cryptography and policy communities working to design future data deletion systems.

This paper presents a native Rust implementation of the Korean post-quantum cryptography algorithms (i.e., NTRU+, SMAUG-T, HAETAE, AIMer). We optimize the implementation in Rust for speed and memory usage, and compare our implementation with the C reference code (KpqClean) and unoptimized Rust implementation (baseline). For speed, we use AVX2 and PCLMULQDQ to accelerate NTT- and Toom–Cook-based polynomial multiplication, 4-way SHAKE, and carry-less GF(2^λ) multiplication. Compared to the C reference, the speed-optimized version reduces the execution time by 32–76% across all target schemes. For memory, we reduce large temporary buffers through on-the-fly approach, two-pass sampling, and transcript recomputation. Against the C reference, the memory-optimized implementation reduces the total memory usage by 1–94% across all target schemes. Overall, these results show a speed–memory trade-off, letting an implementation be chosen according to whichever resource is more constrained.

To initiate migration to post-quantum cryptography (PQC), it is necessary to identify whether deployed software uses quantum-vulnerable (QV) public-key cryptographic schemes such as RSA, ECDSA, and Diffie–Hellman (DH). However, many ELF executables are distributed without source code, making it necessary to directly screen executable binaries for QV candidates. A prior tool, Quantum-vulnerable Executable Detection (QED), provides high precision but incurs substantial analysis cost, whereas its lightweight variant, QED-Lite, is faster but produces more false positives (FPs). This paper proposes ML-QED-Lite, a machine learning-based approach designed to retain the efficiency of QED-Lite while reducing FPs. Unlike a post-filter that merely reclassifies candidates selected by QED-Lite, ML-QED-Lite directly takes all ELF executables in a target directory as input. For each file, it extracts function symbols, library dependencies, and binary-level attributes, and then uses a trained classification model to determine whether the file is a candidate for PQC migration. The evaluation results show that ML-QED-Lite detects the same five positive executables as QED-Lite on the network dataset while reducing FPs from two to zero. On the synthetic dataset, ML-QED-Lite retains the same six positive executables while reducing FPs from four to zero. These results indicate that ML-QED-Lite preserves the true positives (TPs) identified by QED-Lite while reducing FPs, thereby improving the practicality of lightweight screening for PQC migration.

Following the standardization of major post-quantum cryptography (PQC) algorithms, C implementations of ML-KEM, ML-DSA, and SLH-DSA have been rapidly deployed. However, known-answer tests (KATs) verify only functional correctness and do not establish the absence of timing leakage caused by secret-dependent branches, memory accesses, or variable-latency instructions. This paper presents CT-KAT, an integrated screening platform for assessing constant-time risks in PQC C implementations. CT-KAT is configured through a single YAML file. Using this configuration, it validates the build and KAT execution. It also automatically generates harnesses for the functions under analysis. It then performs several analyses within a unified pipeline. These include Valgrind/Memcheck-based structural checks, a ct-matrix over compiler and optimization-level combinations, and an assembly-level asm-scan. When configured, the pipeline also runs dudect-based timing tests. CT-KAT aggregates the results of these checks into a single verdict drawn from a nine-class taxonomy. CT-KAT does not treat a PASS result as proof of constant-time behavior. Instead, it applies a default-deny policy when assigning verdicts. It also provides supporting evidence to guide manual triage. When applied to a PQClean-based PQC corpus, CT-KAT produced four main classifications. The baseline ML-KEM target was classified as robust. The KyberSlash reproduction was flagged as a secret-dependent variable-latency risk, labeled varlat-secret-risk. The variable-time behavior of ML-DSA and SLH-DSA/SPHINCS+ was accepted under the label accepted-variable-time. Falcon-512 was retained for further analysis and labeled needs-analysis. These results show that CT-KAT provides a screening framework that integrates signals from multiple analysis layers while making the limitations of each tool explicit.

AIMer is a post-quantum digital signature scheme with a conservative design. Its security relies only on the symmetric-key one-way function AIM2 and an MPC-in-the-Head (MPCitH) zero-knowledge proof. AIMer is a Korean post-quantum cryptography (KpqC) standard. However, the AIMer standard code released in January 2026 is a portable C reference implementation. It does not include processor-specific optimizations. As a result, it does not exploit AVX-512, a 512-bit vector instruction set available on modern processors. This paper presents an AVX-512 optimized implementation for all six AIMer variants. We parallelize binary-field multiplication with VPCLMULQDQ. The implementation processes four MPC parties per 512-bit register. We also handle conditional XOR accumulation in the linear layer with a single VPTERNLOGQ instruction. In addition, we accelerate the Keccak permutation using AVX-512VL. Our implementation is 1.60–1.84× faster than the AVX2 implementation for signing. We further analyze the source of this speedup. Contrary to common intuition, most of the improvement comes from Keccak. In the 128-bit and 192-bit variants, Keccak accounts for about 86% of the total improvement. Only in the 256-bit variants does the field-arithmetic contribution increase to about 42%, due to the wider field size. These results show that vectorizing symmetric primitives is as important as binary-field arithmetic in MPCitH signatures. In some cases, it is even more important.

As TLS 1.3 migrates to post-quantum cryptography (PQC), hybrid X.509 transition strategies—alternative-signature (Catalyst), Composite, Chameleon, and signature combiners—are compared on cost but rarely on whether they actually enforce the classical↔PQC binding they promise. We show they often do not, and that the failure persists even in stacks that do check the binding. The same BouncyCastle library accepts a Catalyst certificate carrying a forged ML-DSA signature on its default path yet rejects it via an opt-in call; and wolfSSL, the only stack that checks a present alternative signature by default, cannot require one, so a stripped certificate is silently accepted (a path whose experimental build also shipped CVE-2026-5393). That no stack can mandate the binding is the surprise; that an ignored non-critical extension is skipped by nine verifiers is the expected X.509 baseline, which we reproduce with an independent non-BouncyCastle generator. Composite, by contrast, binds structurally (three verifiers across three OID families reject corruption of either half). Folding this measured enforcement axis into a four-axis cost model (strategy sizes differ by under 4.4%) overturns the cost-led recommendation: once enforcement is priced in, the compatibility winner Catalyst is displaced by a structurally-bound encoding—a combiner where the operator controls both endpoints, or Composite once a like-for-like P-256 pairing ships. A compatibility-led ranking can thus recommend a strategy whose PQC protection no deployed verifier enforces.

HCTR2 is a wide-block encryption mode that encrypts one fixed-size message as a single unit, so that flipping a single plaintext bit re-randomizes the whole ciphertext. Its main use is disk encryption, where the message is a disk sector. We instantiate it with ARIA, the Korean national block-cipher standard, and implement it on an NVIDIA RTX 4080 GPU. With many independent messages, assigning one thread per message keeps the device occupied. At low queue depth, however, most of the GPU sits idle, and encrypting one 16 KiB message is several times slower than a single CPU core. The reason is that one HCTR2 message is internally sequential, so it cannot simply be split across threads. We present a fine-grained kernel in which one 32-thread warp cooperates on a single message. The kernel exploits the linearity of POLYVAL. It splits the long hash computation into contiguous per-thread pieces, has each thread compute a partial result, and combines the partials with warp shuffles to obtain exactly the same value as the sequential computation. This brings the latency of one message down to parity with a single CPU core (ARIA-256: 222 μs on the GPU vs. 209 μs on the CPU). Moreover, the number of threads per message and of messages per block acts as a knob that trades latency for throughput, spanning 222 μs/30 GB/s to 1774 μs/49 GB/s. With as few as four messages in flight the GPU already beats the CPU. We validate correctness for all three key sizes.

Primitive-only PQC benchmarks are insufficient for attributing composed hybrid costs on Cortex-M4 because shared hash backends, randomized-signature behavior, and fixed classical/wrapper work affect measured performance. We implement a common bare-metal Cortex-M4 harness for representative KpqC/NIST families, measuring uniform Hash-CT hybrid KEM benchmark rows with X25519 and Bindel et al. hybrid-signature AND-combiner rows. The goal is composed-cost attribution under a uniform benchmark transcript rather than primitive-only ranking. Our measurements show three attribution effects. First, replacing only Keccak-f[1600] changes SHAKE-heavy signing by up to 2.16×, while SPHINCS⁺-SHA2 and FN-DSA control rows remain at 1.00×. Second, median-only signature tables can change deployment conclusions. In the nominal level-5 signing rows, HAETAE5 beats FN-DSA-1024 by median and mean latency, but its observed maximum reaches 4.53× its median while FN-DSA-1024 remains essentially flat. Third, a local SMAUG-T backend improves standalone SMAUG-T by 1.79–1.82×, but the visible gain drops to 1.42–1.65× inside SMAUG-T+X25519 hybrids. Supporting KEM rows place lattice hybrids at 3.7–8.8 M cycles and HQC hybrids at 19.6–74.5 M cycles. Together, the results motivate reporting composed-cost attribution, backend provenance, and variance alongside primitive timings.

This paper proposes an optimized GPU implementation of the ARIA-GCM authenticated-encryption pipeline (CTR keystream, GHASH authentication, and their AEAD composition): ARIA-CTR uses a packed 32-bit S-box staged in shared memory, GHASH is optimized separately with a fixed-key 4-bit Shoup lookup table, the two stages are integrated as both a two-kernel and a fused single-kernel AEAD, and the same aria_gcm.cu source is tuned for Ampere and Pascal through compile-time parameters. For ARIA-CTR, the four distinct S-box tables are merged into one 1 KiB shared-memory table (R=1 staging) and each thread encrypts CTR_IPT counter blocks in parallel to fill the ALU-bound diffusion layer. For GHASH, each thread owns one segment of sblk blocks, applies W-way Horner interleaving with precomputed powers of H, and keeps the reduction table in shared memory. Experiments on an RTX 3090 and a GTX 1080 Ti show that packed S-box staging improves naive ARIA-CTR by 14.5×, the Shoup LUT improves bit-serial GHASH by 21.5×, and the tuned pipeline reaches 924 Gb/s (CTR), 2,865 Gb/s (GHASH), and 622 Gb/s (fused AEAD) on the RTX 3090. Using a simple sequential-composition model, we show that the GHASH optimization is what shifts the AEAD bottleneck onto ARIA-CTR: without it the pipeline would be GHASH-bound near 120 Gb/s, whereas the tuned GHASH makes CTR account for about three quarters of the per-byte cost. We back the analysis with Nsight Compute measurements of register usage, achieved occupancy, shared-memory bank conflicts, and DRAM traffic.

We present a quantum resource estimation of the Rijndael variants \[ N_b = N_k \in \{4,5,6,7,8\}, \qquad N_r = N_b + 6, \] under the NIST MAXDEPTH quantum cost model. Extending the AES quantum encryption oracle~\cite{ref5} parametrically to arbitrary $N_b = N_k$, we generalize the in-place key schedule, including the single- and double-\texttt{SubWord} cases, the \texttt{ShiftRows} offsets, and the round constants. We implement and verify the resulting oracles using ProjectQ. The verified variants range from 1,624 qubits at a full depth of 1,090 for Rijndael-128/128 to 3,240 qubits at a full depth of 1,839 for Rijndael-256/256. Under the NIST PQC MAXDEPTH bounds $\{2^{40}, 2^{64}, 2^{96}\}$, the Grover key-recovery qubit cost in $\log_2$ units ranges from $\{80.15, 32.15, 10.67\}$ for Rijndael-128/128 to $\{210.65, 162.65, 98.65\}$ for Rijndael-256/256. The standardized analogues at Categories 1, 3, and 5, namely Rijndael-128/128, Rijndael-192/192, and Rijndael-256/256, meet the corresponding AES-based bounds. The intermediate Rijndael-160/160 and Rijndael-224/224 variants provide reference points between the standardized AES key lengths.

Information set decoding (ISD) is the standard generic decoding attack considered for code-based cryptography. A concrete quantum-resource estimate for Grover-accelerated ISD requires an oracle whose dominant component is Gauss–Jordan elimination. We improve the elimination circuit of Perriello et al. [25] and Jang et al. [15] by not updating the entries that no later pivot or the final weight predicate reads. The required result vector is recovered by a parallel back-substitution on the syndrome register. For the target schemes, our elimination circuit improves the qubit count by about 22% compared to [15]. The Toffoli count improves by about 20% compared to both [25] and [15]. The Toffoli depth improves by about 67% compared to [25] but degrades by about 0.3% compared to [15]. We report logical resource estimates for the quantum ISD attack on HQC and Classic McEliece. The product of the total gate count and the full depth exceeds the NIST post-quantum security thresholds, and the full depth exceeds the MAXDEPTH upper bound. We also provide fault-tolerant estimates of the physical qubit count and the runtime under a surface-code model with magic-state distillation. As one example, HQC-128 requires about $2^{43}$ physical qubits and about $2^{53}$ years at a 1 μs code cycle.

This paper presents a memory-efficient and high-speed implementation of NTRU+, one of the key encapsulation mechanisms (KEMs) selected by Korea’s post-quantum cryptography project (KpqC), on the ARM Cortex-M4. NTRU+ is small enough to run on its own on a Cortex-M4 class microcontroller, yet in real embedded environments, the peak stack occupied by polynomial buffers and the running time dominated by the NTT become key constraints. To address this, in the proposed technique, we reduce memory by analyzing when each polynomial buffer is actually live and restructuring the algorithm so that only a single buffer is resident during computation, and we significantly improve speed by rewriting the NTT for the mixed-radix structure of NTRU+ in Cortex-M4 assembly. By doing so, the assembly NTT acceleration compensates for the recomputation overhead introduced by the memory optimization, so that the combined implementation is both smaller and faster than the reference. Experimental results show that, relative to the KpqClean_ver2[1] reference implementation, the proposed technique reduces the peak stack by 83–84% while improving the speed of all three operations by up to 1.8×.

FAEST is a symmetric-key post-quantum digital signature scheme and a third-round candidate in the NIST Additional Digital Signatures standardization process. Its signing path concentrates cost in two operations: round-wise constraint generation, which proves in zero knowledge that the AES circuit is computed correctly, and finite-field multiplication, which computes the leaf nodes of a vector commitment. This paper accelerates both operations on a CUDA-enabled GPU, with AES round constraint generation as the main contribution. Specifically, we fuse the three consecutive stages that make up constraint generation into a fused GPU path and keep the intermediate results between stages resident in device memory, thereby reducing host–device data transfer. As a supporting measure, we batch independent finite-field multiplications for leaf nodes, jointly improving end-to-end signing performance. We verify the correctness of the implementation through byte-level output agreement with the CPU reference implementation. Combining fused constraint generation with batched leaf hashing, the full GPU path achieves up to roughly a 3× end-to-end signing speedup over the CPU reference. Furthermore, when AES constraint generation fusion is added on top of leaf hashing that is already performed on the GPU, an additional reduction in signing latency is observed in five of the six evaluated AES s/f variants. The magnitude of this effect does not scale monotonically with the security parameter; rather, it is determined by the per-variant bottleneck structure.

Voltage glitching is one of the most prominent fault injection techniques due to its effectiveness and simplicity. Although it is generally regarded as a spatially global fault method, in which the injected glitch uniformly affects all circuits on the die, several studies have observed that specific locations may be affected more than others. To characterize this phenomenon, we draw inspiration from methods used in electromagnetic interference (EMI) analysis. In this paper, we demonstrate that voltage attacks can be modeled as the transfer of conducted electromagnetic energy through the power delivery network (PDN) to the chip’s die. By analyzing voltage glitches in the frequency domain and modeling the PDN as a communication channel, we demonstrate that different frequency components of an injected glitch signal propagate through the network in distinct patterns. In this context, we further show that modulating the supply voltage with a single-frequency sinusoidal signal, rather than injecting a pulse-shaped glitch, enables an adversary to influence transistors in specific regions of the chip and thus induce localized faults. To validate these claims, we first propose a post-silicon profiling framework that identifies the frequency bands in which the system’s PDN is most vulnerable and maps the spatial regions of the chip affected by each frequency component. To this end, we perform extensive profiling on several FPGAs using distributed time-to-digital converters (TDCs) to measure the impact of injected signals across a range of frequencies. As a proof-of-concept, we also demonstrate successful localized voltage attacks on simple FSMs and AES-128 implementations with various placements, to further show the sensitivity of chip locations to injected energy at different frequencies. Our results reveal that even minor changes in design placement can significantly affect a circuit’s susceptibility to voltage-based fault attacks, either weakening or strengthening its resilience.

In this work, we present a comprehensive analysis of QSF, the KEM combiner used by X-Wing (Communications in Cryptology 1(1), 2024). While the X-Wing paper focuses on the application of QSF to ML-KEM-768 and X25519, we discuss the combiner’s applicability to other post-quantum KEMs and ECDH instantiations. Particularly, we establish the compatibility of QSF to KEMs based on variants of the Fujisaki-Okamoto transform by proving ciphertext second-preimage resistance (C2PRI) for these variants. Building on these results, we show that QSF is compatible with, to the best of our knowledge, all post-quantum KEMs currently standardized or considered for standardization—including ML-KEM, (e)FrodoKEM, HQC, Classic McEliece, and various NTRU variants. Notably, this means these schemes can be used with QSF to construct PQ/T hybrid KEMs. In addition, we introduce QSI, a variant of QSF that combines two KEMs by hashing their shared keys, yielding a KEM that is IND-CCA-secure as long as one constituent KEM is IND-CCA-secure and the other is C2PRI-secure. We establish the same compatibility results for QSI as for QSF. Finally, we analyze both QSF and QSI regarding (their preservation of) the recently introduced family of binding properties for KEMs.

We show how an adversarial model trainer can plant backdoors in a large class of deep, feedforward neural networks. These backdoors are statistically undetectable in the white-box setting, meaning that the backdoored and honestly trained models are close in total variation distance, even given the full descriptions of the models (e.g., all of the weights). The backdoor provides access to invariance-based adversarial examples for every input, mapping distant inputs to unusually close outputs. However, without the backdoor, it is provably impossible (under LWE) to generate any such adversarial examples in polynomial time. Our theoretical and preliminary empirical findings demonstrate a fundamental power asymmetry between model trainers and model users.

The Lattice Isomorphism Problem asks whether two given lattices $\mathcal L_1$ and $\mathcal L_2$ are related by an orthogonal linear transformation. Haviv and Regev gave a seminal $n^{O(n)}$-time algorithm for this problem based on an isolation lemma (SODA 2014). We give algorithms for the decision, search, and all-isomorphisms versions of the problem running in time $n^{n+o(n)}$ times a polynomial in the input size. The main new ingredient is a Gaussian heat argument over convex bodies generated by shortest vectors: for $w\sim D_{\mathcal L^*,s}$, the vector $w$ canonically determines $n-o(n)$ independent shortest vectors, leaving a residual instance of rank $o(n)$. The remaining residual dimensions are handled by an $n^{o(n)}$-time canonicalizer obtained by adapting the Haviv-Regev algorithm. We then combine this canonicalizer with a birthday argument to recover all isomorphisms. For the all-isomorphisms version, this bound is asymptotically optimal in the worst case up to an $n^{o(n)}$ factor. As an extension, we also give, in the QRAM model, a quantum variant running in time $n^{\frac{2}{3}n+o(n)}$. It outputs a representative isomorphism together with generators for the automorphism group, thereby providing a compact description of the entire isomorphism coset.

Password-authenticated key exchange (PAKE) remains central to WPA3-Personal, the personal mode of the latest Wi-Fi security standard, where the Simultaneous Authentication of Equals (SAE) protocol enables secure Wi-Fi access via a low-entropy password. However, SAE’s symmetric password authentication makes all associated stations (STAs) vulnerable once the network-edge access point (AP) is compromised. Although SAE+ (IEEE TIFS 2024) addresses this issue in the client–server model with verifier-based asymmetric authentication, its weak binding of the password-derived verifier, ephemeral randomness, and protocol transcripts still enables key-compromise impersonation (KCI) attacks and offline dictionary attacks. Therefore, designing a verifier-based asymmetric SAE protocol that preserves the SAE workflow while resisting these attacks remains challenging. To address this challenge, we propose AsymSAE, a verifier-based asymmetric SAE protocol tailored for personal Wi-Fi networks. Following the SAE workflow in IEEE Std 802.11-2024, AsymSAE realizes asymmetric authentication by allowing the STA and AP to use the user password and the password-derived verifier, respectively. We further formulate a verifier-based security model to capture the asymmetric structure, and prove the security of AsymSAE in this model. Heuristic security analysis and ProVerif verification demonstrate that AsymSAE provides forward secrecy, transcript-based offline dictionary attack resistance, AP-side KCI resistance, session-key confidentiality, and mutual authentication. Our performance evaluation, including ns-3-based network simulation, demonstrates that AsymSAE can achieve significant verifier-based security enhancement without incurring extra communication overhead, while introducing minimal additional computational overhead and authentication latency.

Side-channel attacks are an important class of security exploits, in which an attacker gains access to confidential data by observing information inadvertently leaked by a system. Writing constant-time code is a common defense against time-based and microarchitectural side-channel attacks. Many approaches have been proposed to automatically verify that a program is constant-time. Sound methods can detect all information leaks but, to efficiently analyze large programs, most of them rely on overapproximation which can yield false alarms (i.e., reports of non-existent information leaks). Each finding produced by such analyses therefore requires manual inspection. Additionally, most existing approaches do not perform binary-level analysis and thus miss vulnerabilities introduced by compilation. In this paper, we present a novel sound analysis for detecting information leaks under the constant-time threat model. Compared with existing work, our technique improves taint analysis by systematically tracking precision loss to determine whether a detected information leak could be caused by overapproximation. Findings for which no precision loss is detected are reported as confirmed; as long as they do not arise from dead code, confirmed findings are guaranteed to be true and thus do not require significant manual inspection. Only findings with detected precision loss need classical human verification. Our analysis operates directly on binary executables. We instantiate our technique within the abstract interpretation framework and provide a proof of correctness. We implemented our approach in a prototype tool, SCOUT-CT, and evaluated it on a benchmark of constant-time and non-constant-time programs, including real-world cryptographic implementations. Our results show that SCOUT-CT is effective: our tool detected all 98 timing leaks in the benchmark and automatically classified 97 as confirmed findings that do not require significant manual inspection.

The Deligne-Ogus-Shioda theorem guarantees the existence of isomorphisms between products of supersingular elliptic curves over finite fields. In this paper, we present methods for explicitly computing these isomorphisms in polynomial time, given the endomorphism rings of the curves involved. Our approach leverages the Deuring correspondence, enabling us to reformulate computational isogeny problems into algebraic problems in quaternions. Specifically, we reduce the computation of isomorphisms to solving systems of quadratic and linear equations over the integers derived from norm equations. We develop $\ell$-adic techniques for solving these equations when we have access to a low discriminant subring. Combining these results leads to the description of an efficient probabilistic Las Vegas algorithm for computing the desired isomorphisms. Under GRH, it is proved to run in expected polynomial time.

This works introduces Basefold, a new $\textit{field-agnostic}$ Polynomial Commitment Scheme (PCS) for multilinear polynomials that has $O(\log^{2}(n))$ verifier costs and $O(n \log n)$ prover time. An important application of a multilinear PCS is constructing Succinct Non-interactive Arguments (SNARKs) from multilinear polynomial interactive oracle proofs (PIOPs). Furthermore, field-agnosticism is a major boon to SNARK efficiency in applications that require (or benefit from) a certain field choice. Our inspiration for Basefold is the Fast Reed-Solomon Interactive-Oracle Proof of Proximity (FRI IOPP), which leverages two properties of Reed-Solomon (RS) codes defined over "FFT-friendly'' fields: $O(n \log n)$ encoding time, and a second property that we call foldability. We first introduce a generalization of the FRI IOPP that works over any foldable linear code in linear time. Second, we construct a new family of linear codes which we call $\textit{random foldable codes}$, that are a special type of punctured Reed-Muller codes, and prove tight bounds on their minimum distance. Unlike RS codes, our new codes are foldable and have $O(n \log n)$ encoding time over ${any}$ sufficiently large field. Finally, we construct a new multilinear PCS by carefully interleaving our IOPP with the classical sumcheck protocol, which also gives a new multilinear PCS from FRI. Basefold is 2-3 times faster than prior multilinear PCS constructions from FRI when defined over the same finite field. More significantly, using Hyperplonk (Eurocrypt, 2022) as a multilinear PIOP backend for apples-to-apples comparison, we show that Basefold results in a SNARK that has better concrete efficiency across a range of field choices than with any prior multilinear PCS in the literature. Hyperplonk with Basefold has a proof size that is more than $10$ times smaller than Hyperplonk with Brakedown and its verifier is over $30$ times faster for circuits with more than $2^{20}$ gates. Compared to FRI, Hyperplonk with Basefold retains efficiency over any sufficiently large field. For illustration, with Basefold we can prove ECDSA signature verification over the secp256k1 curve more than $20$ times faster than Hyperplonk with FRI and the verifier is also twice as fast. Proofs of signature verification have many useful applications, including offloading blockchain transactions and enabling anonymous credentials over the web.

Threshold signatures allow a quorum of parties to jointly produce a signature while preventing any smaller subset from doing so. Following NIST's post-quantum standardization, designing threshold schemes compatible with the newly selected primitives is a pressing task. In particular, no prior threshold signature scheme produces signatures verifiable under the unmodified FALCON verification algorithm - the NIST-selected post-quantum scheme with the smallest signatures and keys. In this work, we present the first such threshold FALCON signing protocol, establishing its feasibility. Our technical contributions are threefold. First, we adapt the MPC-based discrete Gaussian sampling protocol of Wei et al. [CCS:WYFCW23] to support private centers and standard deviations, as required by FALCON's signing process. Second, we carry out a Rényi divergence analysis of the Klein sampler under fixed-point arithmetic, showing that $73$ bits of precision suffice to achieve the same security as the FALCON specification. Third, we design an efficient MPC protocol for the Klein sampler that exploits the fixed trapdoor basis to construct a pseudorandom correlation generator for authenticated VOLE using only two-party DPFs, reducing per-signature communication significantly over standard authenticated triple generation. We implement and benchmark our protocol in two settings: $N$-party signing with all-but-one corruption, and 3-party signing with honest majority, demonstrating that threshold FALCON signing is feasible for applications where compatibility with the FALCON standard is required.

Who is talking to whom? Consider a group of users who wish to communicate anonymously via a network of intermediate relays. We study anonymous communication under two standard strong adversarial models. A passive adversary observes all network traffic and additionally views the internal states of a constant fraction of corrupted relays, while an active adversary may also control the behavior of these corrupted relays. The goal of an anonymous communication protocol is to ensure that the adversary cannot distinguish who is communicating with whom. One of the most practical and widely adopted approaches is onion routing, where messages are first wrapped in layers of encryption and anonymity emerges through repeated "shuffling" of onions at honest relays that peel a layer and randomly permute outgoing onions. In general, this approach may not achieve anonymity. The challenge is to rigorously quantify conditions for efficiently achieving anonymity, where efficiency is measured as a function of the protocol's security parameter λ, which we assume, without loss of generality, is at least linear in the network size. A well-known result from ICALP'18 shows that if each hop in a routing path is chosen uniformly at random from all relays, then onion routing achieves anonymity against a passive adversary whenever both the number of rounds and the server load grow faster than log λ. In this setting, anonymity arises from the fact that every onion is repeatedly shuffled with a uniformly random subset of other onions. However, this assumption requires a fully connected network. We generalize this result to sparse networks. We show that when routing paths are selected by performing independent random walks on a sparse, constant-degree expander graph, onion routing still achieves anonymity with the same asymptotic efficiency parameters as in the complete-network setting. In particular, this matches the optimal round-complexity bound known for complete networks, despite the fact that onions only shuffle within their local neighborhoods at each round, and an adversary may extract information from observing transitions between neighboring nodes. We further extend our results to active adversaries. In the sparse-expander setting, we construct, under different conditions, (1) a differentially private protocol that achieves (ε, negligible in λ)-differential privacy, and (2) an anonymous protocol. Both run efficiently in polylogarithmic rounds and incur polylogarithmic server load.

This work introduces a polynomial-time attack on the signature scheme Facto-DSA. We provide an implementation that breaks all proposed parameter sets, including the largest, in under one minute on a standard laptop. These results question the suitability of multivariate polynomial factorization as a foundation for robust cryptographic schemes.

Blockchain networks need to exchange messages and assets across independent systems, but cross-chain verification can expose private validation data to relayers, bridge logic, validators, or destination-chain components. This paper presents a prototype-based zero-knowledge verification layer for privacy-preserving blockchain interoperability. The prototype uses Circom and SnarkJS to generate Groth16 proofs, verifies those proofs in Rust using arkworks BN254, and maps the result into a Substrate-style interoperability decision model. The work addresses a practical implementation gap between common zero-knowledge proof tools and Rust-based blockchain interoperability environments. Private values stay off-chain, while only the proof, public commitment, verification metadata, and final decision are passed to the runtime-facing layer. The prototype includes valid-proof acceptance, tampered-input rejection, runtime-compatible verification records, and a simulated interoperability decision layer. Experimental results show proof generation at 199 ms, SnarkJS valid-proof verification at 161 ms, tampered-input rejection at 160 ms, and Rust verifier execution at 340 ms. These results show that a SnarkJS-generated Groth16 proof can be verified in Rust and used to control whether a simulated cross-chain action is accepted or rejected. The current scope does not include a full FRAME pallet or live Cross-Consensus Messaging (XCM) dispatch. In Polkadot, XCM is the message format used to send instructions between different chains. The prototype is not intended to replace Polkadot's existing parachain auditing mechanisms. Instead, it explores a complementary privacy-preserving verification path for selected interoperability conditions where private inputs should not be exposed. The prototype provides a repeatable technical path for building privacy-preserving verification in Polkadot/Substrate-style interoperability workflows.

Fully homomorphic encryption (FHE) enables computation on encrypted data without decryption. In TFHE, programmable bootstrapping (PBS) evaluates nonlinear functions through lookup tables (LUTs), but a direct multivariate LUT over a $t$-ary plaintext space has size $t^\ell$. This paper studies LUT compression for multivariate functional bootstrapping via variable separation and additive inner representations. We first apply this approach to non-negative integer division with remainder. For a dividend $m$, a divisor $d$, and $h=\lfloor m/d\rfloor$, we use a logarithmic transformation to decompose bivariate division into two univariate logarithmic PBS calls, one homomorphic subtraction, and one outer exponential PBS call. To handle integer plaintexts, we introduce a rounded logarithmic function $\operatorname{clog}_{B,M}$ and give a sufficient condition on $M$ for exact quotient recovery. The resulting homomorphic division-with-remainder algorithm achieves $\widetilde{O}(1)$ equivalent blind-rotation complexity under theoretically optimal parameters, and also yields frameworks for modular reduction and truncated division. We further prove that every finite function $f:[t]^\ell\to[t]$ can be written as $f(x_1,\ldots,x_\ell)=q\left(\sum_{i=1}^{\ell}p_i(x_i)\right)$, and search for small-span representations using simulated annealing with reheating. Experiments show a 3.6x speedup for division with remainder at $t=64$, and a 1.9x speedup for the Hamming-weight interval function, compared with estimates based on [BBR26].

We review $k$-anonymity in authentication schemes, group signatures, and ring signatures. Existing constructions either require a signer to maintain state across interactions, or admit tracing algorithms that cost $O(n^k)$ in the number $n$ of signatures. We introduce $k$-anonymous group signatures ($k$-AGS), that achieves stateless signing with a tracing cost $O(n+k)$, while necessarily sacrificing unlinkability. We present a generic construction of $k$-AGS together with an efficient instantiation. We additionally construct a proof-of-concept $k$-unlinkable group signature ($k$-UGS) scheme that achieve unlinkability at the expense of $O(n^2k)$ tracing overhead. We pose the question of whether stateless signing, $O(n+k)$ tracing, and unlinkability are simultaneously achievable, and leave it as an open problem. Building on our $k$-AGS framework, we introduce $k$-Anonymous Set Pre Constrained Group Signatures ($k$-ASPCGS), a threshold variant of Set Pre-Constrained Group Signatures introduced by Bartusek et al. (EUROCRYPT '23). As a proof-of-concept, we present two generic constructions of $k$-ASPCGS. We show that our notions arise naturally in the context of content moderation in end-to-end encrypted messaging platforms, where users must remain anonymous until a threshold number of distinct illegitimate contents have been reported.

In this paper, we revisit the problem of multi-client functional encryption (MCFE) for general functions. Specifically, we consider the setting of private-key MCFE for constant-arity functions where the input domain is polynomial in the security parameter. Surprisingly, we show that in this setting it is possible to construct a private-key MCFE scheme secure for a bounded number of key and encryption queries based only on the minimal assumption that one-way functions exist. In contrast, all prior constructions of MCFE for general functions require very strong assumptions such as indistinguishability obfuscation or multilinear maps. Our main technique is to show that private-key MCFE for polynomial input domain can be built from any private-key multi-input functional encryption (MIFE) while inheriting the security properties of the underlying MIFE. Instantiating our construction with the MIFE of Brakerski et al. (Eurocrypt 2016) gives us a construction based only on the existence of one-way functions.

This work revisits a natural paradigm for constructing public-key encryption, whereby the public key is an obfuscated block cipher in encryption mode. We show that if the block cipher is a permutable pseudorandom permutation [Shmueli–Zhandry, Crypto ’25] and the obfuscator is indistinguishability-secure, then the following holds. 1. Applying the obfuscated cipher directly to the message and a short random nonce, without any additional structure or consistency checks, suffices for CCA2 security. 2. Augmenting the scheme with the capability to generate obfuscated decrypt-then-apply-$f$ circuits (for any given function $f$), yields a *functional encryption* scheme that is *simulation-secure against adaptive chosen-ciphertext attacks*. 3. For any length-preserving function $g$, augmenting the public key with an obfuscated decrypt-apply-$g$-reencrypt circuit allows anyone to homomorphically apply $g$ to encrypted data, for an unbounded number of times, while preserving semantic security. (This relies on subexponential security.) We also show that, under the split-circuit pseudorandomness (SCP) assumption of [Canetti–Chamon–Mucciolo–Ruckenstein, TCC ’24], random reversible circuits form a permutable pseudorandom permutation family. This points to obfuscated random reversible circuits as a potential alternative avenue to public-key encryption with strong security and rich functionality.

Client-specific preprocessing PIR supports sublinear online private queries after a linear-time offline phase that prepares client-specific hints. The relevant lower bound is tight: any scheme with $S$ bits of client storage and online cost $T$ must satisfy $S \cdot T = \Omega(n)$. Most practical random-set schemes fall short by a $\kappa$ factor in client storage, while the known constant-factor-optimal schemes, WR-PIR (Eurocrypt 2025) and Balanced PIR (S&P 2026), rely on complex hint-management machinery and incur high concrete costs. We present Multi-level PIR, a preprocessing PIR scheme that matches this tight space-time tradeoff using only simple random-set components. The main idea is a multi-level composition: early levels are allowed to fail with noticeable probability, and later levels are invoked only when these query-independent failures occur. This 'waterfall' structure drives the overall failure probability down to negligible while keeping expected online cost and client storage at $O(\sqrt{n})$. Our implementation shows that this simpler structure gives competitive concrete performance. Compared with Piano and S3PIR, two prior state-of-the-art practical schemes, Multi-level PIR achieves a $9$-$20\times$ client space reduction; compared with Balanced PIR, it reduces preprocessing time by about $8$-$45\times$ and online communication by about $5$-$67\times$ in our evaluated settings, while remaining competitive in other online metrics. As an additional theoretical result, we give a more involved variant with $O(n^{1/4})$ online communication, the first constant-factor-optimal preprocessing PIR scheme with sub-$\sqrt{n}$ online communication.

With growing concerns over data privacy, private nearest neighbors search (PNNS) attracts increasing research attention. Existing PNNS follow two main approaches: i) interactive PNNS based on secure multi-party computation protocols that leverage index structures to achieve sublinear complexity, and ii) non-interactive PNNS utilizing fully homomorphic encryption to minimize communication bandwid that the cost of superlinear computational complexity. To address the communication-computation dilemma, we propose HANNS, a non-interactive PNNS protocol with a sublinear number of encrypted comparisons. Our key observation is that, while the full-table scan is inevitable under the non-interactive setting, the number of costly encrypted comparisons can be significantly reduced. Specifically, we develop a cluster ordering scheme over FHE that leverages a segmented rigid transformation to obliviously identify candidate clusters with only a sublinear number of homomorphic comparisons. Furthermore, we introduce a homomorphic product quantization (PQ) scheme that enables coarse search and reranking over PQ-encoded vectors, which significantly reduces the computational and storage overheads. In the experiment, we show that HANNS achieves 41x to 277x speedup and a storage reduction of 12x to 31.7x compared to the most recent non-interactive schemes, while reducing communication by 1,258x to 80,536x and achieving a speedup of 8x to 119x over interactive schemes in low-bandwidth scenarios.

Protocols for State-Machine-Replication (sometimes called 'blockchain' protocols) generally make use of rotating leaders to drive consensus. In typical protocols (henceforth called 'single-sender' protocols), the leader is a single processor responsible for making and disseminating proposals to others. Since the leader acts as a bottleneck, apparently limiting throughput, a recent line of research has investigated the use of 'multi-sender' protocols in which many processors distribute proposals in parallel. Examples include DAG-based protocols such as DAG-Rider, Bullshark, Sailfish, Cordial Miners, Mysticeti, and variants such as Autobahn. However, existing models do not allow for a formal analysis to determine whether these protocols can actually handle higher throughputs than single-sender protocols such as PBFT, Tendermint, and HotStuff. In this paper, we describe a very simple model that allows for such an analysis. For any given protocol, the model allows one to calculate latency as a function of network bandwidth, network delays, the number of processors $n$, and the incoming transaction rate. Each protocol has a latency bottleneck: an incoming transaction rate at which latency becomes unbounded over the protocol execution, i.e., a maximum throughput that the protocol can handle without unbounded latency. With the aim of building to an analysis for state-of-the-art State-Machine-Replication (SMR) protocols, we begin by considering protocols for simpler primitives, such as Best-effort Broadcast and Reliable Broadcast. For Best-effort Broadcast, we establish a tight lower bound on latency for single-sender and multi-sender protocols when blocks are distributed without the use of techniques such as erasure coding. Perhaps unsurprisingly, a key difference between the single-sender and multi-sender approaches in this case is a factor $n$ in the point at which the latency bottleneck appears. However, for other primitives such as Reliable Broadcast, our results may be more surprising: the factor $n$ difference now disappears, and maximum throughput for the two approaches differs by a constant factor, while multi-sender approaches will generally have latency that grows more quickly with $n$. For state-of-the-art SMR protocols, the picture that emerges is one with seemingly inherent trade-offs. If one compares single-sender protocols that use pipelining and erasure coding, such as DispersedSimplex, with DAG-based protocols such as Sailfish or Bullshark, the former are seen to have lower latency for a wide range of throughputs, while the benefit of the latter protocols is that they have a latency bottleneck which is higher by a constant factor.

Quantum cryptography allows to achieve security goals which are unobtainable using classical cryptography alone: it offers the promise of everlasting privacy. Thatis, an adversary trying to attack a protocol must succeed during the run of the protocol. After the protocol has terminated, security holds unconditionally. In this work, we initiate the study of a new model which we call the quantum decoherence model (QDM). In a nutshell, this model captures adversaries that are computationally bounded during the run of a protocol (and some time after), but become computationally unbounded long after the protocol terminates. Importantly, once the adversary becomes computationally unbounded, he can only remember a bounded number of qubits from before the computational bound was lifted. We provide a variant of the Universal Composability framework which captures the new notion of quantum decoherence and augment it with quantum random oracles. As our main contribution, we construct a non-interactive commitment scheme achieving unconditional and statistical security against malicious senders and everlasting security against malicious receivers under our new security notion. Such commitments imply general secure multiparty computation with everlasting security. Finally, we show that our core technique can be applied to a broader spectrum of problems. We show that it gives rise to everlasting public key encryption and OT in the QDM. Finally, we also consider the weaker notion of incompressible encryption in the setting of quantum decoherence, and show that post-quantum IND-CPA secure public key encryption is sufficient to realize this notion without resorting to random oracles. At the technical core of our constructions is a new, conceptually simple yet powerful reverse entropic uncertainty relation.

The objective of this work is to investigate methods for improving the self-tuning mechanism of ring oscillator (RO) based True Random Number Generators (TRNGs). It also examines the challenges involved in achieving a reliable and stable design over long-term operation. Furthermore, this work analyzes potential approaches to address these challenges and validates their effectiveness using the NIST statistical test suite.

Blind side-channel analysis (BSCA) can infer keys without known inputs or outputs, but practical use still needs an upstream step that locates repeated computation and candidate points of interest in an unlabeled trace. We address this trace-only structuring problem with a two-stage method that uses only the per-sample mean and standard deviation, without algorithm labels or metadata. Stage1 estimates a repetition scale, start phase, anchor-supported stable core, and period candidates from rank-combined self-similarity. Stage2 stacks the stable core into a representative repetition and partitions it into relative high- and low-score segments. On 16 block cipher implementations across STM32F303 and XMEGA, the method forms consistent repetition windows in most cases. Post-hoc source and assembly comparison separates exact or edge-inclusive count matches from grouped, microperiod, and ambiguous hierarchy relations, while Top-5 candidates often retain body-related hierarchy. In a representative AES/XMEGA case, the trace-only high-score segments cover the strongest S-box CPA hotspots, indicating that the produced coordinates can prioritize, rather than determine, candidate regions for later CPA or BSCA.

Blockchain-based cryptocurrencies give rise to a plenitude of advanced applications (such as cross-currency transfers or privacy-preserving payments) through blockchain protocols - cryptographic protocols that orchestrate the processing of financial transactions on the blockchain. To enable a modular design and to enhance reusability across different cryptocurrencies, many blockchain protocols are built upon adaptor signatures (AS), a well-studied cryptographic building block, which is natively supported by most digital signature schemes used for authorizing cryptocurrency transactions. An inherent limitation of AS-based blockchain protocols is the known impossibility to realize AS for unique signature schemes, such as BLS signatures. As a consequence, existing AS-based protocols cannot be executed on cryptocurrencies that base transaction authorization on BLS signatures (such as the Chia Network). For such cryptocurrencies, instead, new custom blockchain protocols need to be created, as recently done for the case of coin mixing (S&P'24) or atomic swaps between two cryptocurrencies with BLS-based transaction authorization (ESORICS'24). To avoid such complex and error-prone redesigns, in this work, we develop a novel notion of AS called Two-Party Asymmetric-Input Solitary-Output Adaptor Signature (2P-AISO-AS) that sidesteps the known impossibility result and that can be realized from both randomized (i.e., plain) and unique signature schemes. We provide efficient instantiations of 2P-AISO-AS from BLS and show that we can obtain performant, BLS-compatible blockchain protocols by replacing AS with 2P-AISO-AS in known AS-based protocols, including zero-knowledge contingent payments, atomic swaps, and coin mixing.

Design of hash functions and pseudo-random permutations over Galois extensions of $\mathbb Z_q$ for prime powers $q$ has recently gained some interest in relation to recent directions in advanced cryptography, such as multiparty computation and zero-knowledge protocol design. Thus investigating optimality of cryptographic properties of S-boxes defined by polynomials over Galois rings is of interest. Of particular interest is the differential uniformity of such functions. To our knowledge, there are very few results on the differential uniformity for polynomials over Galois rings $\mathrm{GR}(p^k,m)$ when $k,m\geq 2$. Motivated by designing secure hash functions and block ciphers over Galois rings, a main contribution of this paper is an investigation into the differential properties of polynomials over Galois rings. Finally, we provide a classification of APN permutations in $\mathrm{GR}(4,2)$ up to affine and CCZ-equivalence.

As Machine Learning as a Service expands, protecting client data has become a critical challenge. Homomorphic Encryption (HE) enables computation on encrypted data, but practical HE-based AI still suffers from high latency and large key sizes. Among neural network operations, convolution remains a central target for optimization, as it is fundamental to CNNs and increasingly used in transformers and state-space models. To realize HE convolution, various packing strategies—defining the data layout within a ciphertext—have been introduced, leading to state-of-the-art methods such as multiplexed parallel convolution (MPConv), which is implemented with multiplexed parallel packing. In this paper, we propose Rotation-Optimized Multiplexed Parallel Convolution (RO-MPConv), which enhances usability by reducing the number of rotation operations and rotation keys—major contributors to latency and key sizes in MPConv. Additionally, we introduce a small-level key system to further decrease key sizes and a parallel baby-step giant-step matrix-vector multiplication, which reduces rotations for packing strategies with multiple identical data entries, including multiplexed parallel packing. Experimental results demonstrate that RO-MPConv achieves up to an 81% reduction in convolution latency compared to MPConv. For key transmission, combining RO-MPConv with the hierarchical rotation key system and our small-level key system achieves a 29× reduction in rotation key size compared to MPConv. Furthermore, integrating RO-MPConv into existing state-of-the-art models reduces their total latency by up to 26%, and our proposed matrix-vector multiplication method reduces latency by 69%. Our code is fully available from https://github.com/byeongseomin51/RO-MPConv.git.

Boolean functions with additional structure play an important role in symmetric cryptography, both for achieving strong cryptographic properties and for enabling efficient implementations. Recent works on homomorphic-friendly symmetric primitives, especially in the context of Hybrid Homomorphic Encryption, highlighted the interest of Boolean functions whose evaluation can be decomposed according to structured partitions of the Boolean cube. A classical example is given by Hamming-weight decompositions, which underlie symmetric and weightwise degree-d Boolean functions. In this work, we generalize this viewpoint by replacing the Hamming weight with a general integer linear form. Given a vector v in Z^n, we partition the Boolean cube (F_2)^n by grouping the Boolean vectors x in (F_2)^n according to the value of <v,x> into so-called v-slices, and study functions that have bounded degree on each of them. We study how many such slices are needed to describe a given function, and provide bounds and structural properties for the partitions induced by integer vectors. We also show how this representation leads to a homomorphic evaluation strategy in a GSW-like setting, together with noise estimates for the resulting ciphertexts. Finally, we generalize several symmetric and weightwise degree-d Boolean functions using different vector families, and experimentally evaluate their algebraic degree, algebraic immunity, and nonlinearity. The results show that direct generalizations of symmetric functions often lose cryptographic strength, while generalized weightwise degree-d constructions lead to richer and more promising behavior.

In next-generation networks, communication systems will no longer be limited to data transmission and will be expected to acquire awareness of the surrounding environment. This leads to the concept of integrated sensing and communication (ISAC), where the same wireless infrastructure is used for both communication and environmental sensing. Thus, ISAC enables the system to transmit information efficiently and observe and interpret channel variations and user behavior. Motivated by this capability, this work focuses on detecting an active attacker in an urban environment scenario, where the attacker intentionally manipulates beamforming directions to increase interference and mislead the transmitter into allocating the main lobe of beam toward itself instead of legitimate users. We apply game-theoretic approaches to model the interaction between legitimate users and the attacker, and integrate the resulting utility-based formulation into a reinforcement learning (RL) framework. Simulation results demonstrate that the proposed method effectively addresses security challenges in dynamic 6G ISAC systems.

In this paper, we prove the post-quantum security of the Tweakable Key-Alternating Feistel cipher (TKAF) with a public random function in the Q1 model, under the assumption that the adversary is given quantum access to the internal primitive. Specifically, our target is the TKAF studied in the classical setting by Yan et al. (ACNS 2020), where the tweak is injected into the round-key XOR via a hash function of $\epsilon$-AXU family. Our proof draws on the post-quantum security proof for the (non-tweakable) key-alternating Feistel ciphers by Basak et al. (ASIACRYPT 2025), and adapts it to the tweakable setting and further to the multi-key setting, where an adversary can access multiple classical oracles. As a result, we prove that the 3-round TKAF is post-quantum TPRP-secure and the 4-round TKAF is post-quantum STPRP-secure. Specifically, under the assumption that the adversary is given classical access to $\ell$ independently specified oracles, at least $\mathrm{\Omega} (2^{n/3}/\ell^{2/3})$ classical and quantum queries or $\mathrm{\Omega}(\epsilon^{-1/2})$ classical queries are required to break the post-quantum TPRP security of the 3-round TKAF and to break the post-quantum STPRP security of the 4-round TKAF.

Zero-knowledge proof systems are increasingly relying on the Sumcheck protocol to avoid the FFT-heavy structure of earlier SNARK designs. Sumcheck is well suited for GPU acceleration; it consists of sequential rounds where each round performs regular, parallelizable operations over large multilinear evaluation tables. The focus is on how to organize this work across rounds: intuitively, the active polynomial state should remain close to the device that processes it, the CPU-GPU boundary should only expose values that are needed to transition, and various cryptographic settings should be kept stable. This paper presents Chimera, a GPU-CPU framework for accelerating Sumcheck in Spartan-style SNARK provers. Chimera uses a hybrid execution model: large polynomial evaluation and folding work runs on the GPU, active polynomial state remains resident on GPU across profitable rounds, compact round messages return to Spartan's host transcript, and small domains fall back to CPU execution. Chimera also specializes the wrappers around Spartan's small round-polynomial commitments and proof objects, and introduces a memory-aware chunking path. On BN254 Spartan R1CS instances, Chimera demonstrates a \(7.96\times\) improvement of the committed-Sumcheck region at \(N=2^{17}\), relative to clean Spartan. Across full Spartan proving runs from \(2^{12}\) to \(2^{27}\) constraints, Chimera improves end-to-end prover time for all measured sizes, reaching \(1.27\times\)-\(1.64\times\) speedup for sizes \(2^{24}\)-\(2^{27}\). Ablation studies show that Chimera's gains come from choosing the right execution boundary rather than from any single optimization. The GPU handles the large, regular Sumcheck work, while Spartan keeps the protocol state needed for transcript and verifier compatibility. This reduces movement of polynomial data without disrupting the proof system. The remaining gap between Sumcheck-region and end-to-end speedup shows that, after Sumcheck is accelerated, polynomial commitment and proof-wrapper costs become the next bottleneck.

Modern hardware security heavily relies on the assumption that pre-synthesis algorithmic protections will survive the physical fabrication pipeline. However, untrusted third-party Electronic Design Automation (EDA) toolchains often apply aggressive structural optimizations that can silently compromise perfectly symmetric designs, introducing critical data-dependent power side-channel vulnerabilities. Existing pre-silicon verification methodologies require exposing highly sensitive, proprietary gate-level intellectual property (IP) to external auditors to verify structural security. In this paper, we introduce a novel Zero-Knowledge Hardware Auditor, an end-to-end framework that provides mathematical guarantees of physical data-obliviousness without revealing the underlying circuit netlist. By translating synthesized gate-level topologies into a custom Side-Channel Intermediate Language (SCIL), our architecture maps physical dynamic switching activity into arithmetic constraints executable within a Halo2 zero-knowledge virtual machine (zkVM). This enables the first implementation of a zero-knowledge Bounded Toggle Assessment (ZK-BTA), a deterministic structural counterpart to classical Test Vector Leakage Assessment. Experimental evaluations across standard cryptographic primitives and ISCAS-85 benchmarks demonstrate that the framework successfully identifies inherently leaky logic and captures EDA-induced asymmetries, such as a 13% leakage rate introduced into a theoretically secure Montgomery Ladder, while proving the structural integrity of Dual-Rail oblivious logical topologies. Furthermore, the asymmetric zk-SNARK architecture ensures scalable component-level auditing, yielding a succinct cryptographic proof of physical security that can be publicly verified in under 0.08 seconds.

We present key-recovery attacks on the constructions of TALUS (Kao and Chang), a threshold ML-DSA (FIPS 204) construction available on arXiv and scheduled for presentation at the NIST Threshold Call Preview Talks Round 2 (TCPT-2, https://csrc.nist.gov/events/2026/tcpt). For TALUS-MPC, which is claimed EUF-CMA secure against an adversary corrupting up to $T − 1$ parties, we show the claim is false via two independent attacks, both exploiting the same root cause. TALUS-MPC uses Feldman commitments that apply the public matrix A to secret values: key shares of $s_1$ during key generation, and contributions to the nonce $y$ during signing. Since A is left-invertible in every ML-DSA parameter set, these images are invertible by Gaussian elimination, with no lattice problem to solve. A passive observer recovers all key shares of $s_1$ directly from the key-generation broadcast, and independently recovers the aggregate nonce y from the signing broadcast, which then yields $s_1 = c^{−1} \cdot (z − y)$ from a single signature. For TALUS-TEE and TALUS-MPC, we identify a persisting flaw: the rejection-sampling check that protects the error term $s_2$ in standard ML-DSA has been removed. Each signature leaks a noisy linear equation in $s_2$; applying least-squares recovery over the cyclotomic ring - an instance of LWE without modular reduction - recovers the full secret from a few hundred million signatures. The sample counts we derive are not optimized and we believe exploiting the bounded noise structure and lattice-reduction techniques would reduce them significantly, but we focus on establishing the structural flaw.

In this work we propose a novel Boolean lookup-table evaluation methodology over binary CKKS when circuit XORs are kept lazy, i.e., evaluated as additions whose least significant bits remain correct. Our method represents a LUT in the Walsh basis, forms the required parity sums by lazy CKKS additions, and packs them into ciphertext slots. We then use CKKS binary bootstrapping as a refresh step: the StC stage maps the packed lazy parities to MSB-encoded bits, removing the overflow; CtS places the parity values in slots; and $\mathsf{EvalMod}_{f_{\mathrm{BinBoot}}}$ cleans the binary noise, leaving clean parities in the slot domain. The LUT is then evaluated by recombining these parities with plaintext Walsh coefficients. This decouples the LUT size from the multiplicative depth of the surrounding circuit: large LUTs can be handled by cleaning selected factored parity signs and spending only a small constant depth in recombination. We apply this framework to AES-CTR transciphering. The AES S-box is evaluated with a nibble-split Walsh decomposition, which supports more AES blocks at the cost of one additional multiplication depth. The AES state remains in full complex CKKS packing so real and imaginary lanes carry independent AES blocks. In CPU experiments, the Walsh S-box AES-CTR algorithm is 3.25x faster than the sparse-bootstrapping XBOOT variant at the same 1024-block batch size.

We argue that ChaCha, BLAKE2, SHA-3, and even AES have overly generous security margins: they do more rounds than are needed for their intended security levels, and therefore spend unnecessary computation on symmetric cryptography. This is partly the result of a process failure. Designers initially, and rightly, choose conservative security margins (the gap between the highest round count then reached by cryptanalysis and the round count specified) but these margins are seldom revisited: round counts are not adjusted to reflect the lack of effective cryptanalytic progress, nor are they chosen to make security margins consistent across primitive families. This article reviews cryptanalytic progress over the last 25 years, distinguishing between attacks that improve academic records and attacks that plausibly affect real systems. We revisit the round counts of AES, BLAKE2, ChaCha, and SHA-3, and propose reduced-round variants that are up to 150% faster while retaining a comparable practical security profile. More broadly, our goal is to make round-count selection a more intentional, consistent, and evidence-based engineering decision, rather than an inherited, subjective, conservative constant.

The Algebraic Group Model (AGM) has become a standard framework for analyzing the knowledge soundness of group-based polynomial commitment schemes. In this work, we formally establish inherent limitations of this methodology. We isolate a structural property satisfied by essentially all practical group-based polynomial commitments, which we term AGM-clarity. We prove that for AGM-clear schemes, evaluation binding implies knowledge soundness in the AGM. This collapse reveals that the AGM definition of knowledge soundness does not capture a distinct security property, but is merely a structural consequence of evaluation binding. To precisely characterize the guarantees on extractability provided by the AGM, we introduce Weak Interpolation Knowledge Soundness (WIKS) in the standard model, which is an extreme relaxation of extractability. We show that WIKS is implied by standard evaluation binding and prove that, for AGM-clear schemes, knowledge soundness in the AGM is equivalent to WIKS. We further reformulate WIKS as Correct-Interpolation Binding and use this binding-style characterization to establish that, for binding polynomial commitments, special soundness is strictly stronger than WIKS. Together, these results calibrate AGM knowledge soundness for practical polynomial commitment schemes against two standard-model notions: for AGM-clear schemes, it is already implied by evaluation binding, while for binding schemes, it remains strictly weaker than special soundness. In particular, AGM proofs of knowledge soundness do not certify "knowledge" in the sense of immediate extractability.

The assumed hardness of the Shortest Vector Problem in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP are via so-called sieving methods. While these still take exponential time in the dimension $d$, they are significantly faster than non-heuristic approaches and their heuristic assumptions are verified by extensive experiments. $k$-Tuple sieving is an iterative method where each iteration takes as input a large number of lattice vectors of a certain norm, and produces an equal number of lattice vectors of slightly smaller norm, by taking sums and differences of $k$ of the input vectors. Iterating these ''sieving steps'' sufficiently many times produces a short lattice vector. The fastest attacks (both classical and quantum) are for $k=2$, but taking larger $k$ reduces the amount of memory required for the attack. In this paper we improve the quantum time complexity of 3-tuple sieving from $2^{0.3098 d}$ to $2^{0.2846 d}$, using a two-level amplitude amplification aided by a preprocessing step that associates the given lattice vectors with nearby ''center points'' to focus the search on the neighborhoods of these center points. Our algorithm uses $2^{0.1887d}$ classical bits and QCRAM bits, and $2^{o(d)}$ qubits. This is the fastest known quantum algorithm for SVP when total memory is limited to $2^{0.1887d}$.

Universal multi-party swaps were proposed for secure cross-chain cryptocurrency exchanges across multiple blockchains that require only signature verification from the underlying blockchains. However, existing universal swap protocols remain vulnerable to griefing attacks, where a deviating party aborts the swap to lock a compliant party’s assets for a long period, potentially causing indirect economic losses. A natural approach is to lift existing griefing-free solutions to the universal setting; however, we observe that this direct approach still faces three key challenges: (i) a timeout race attack, which arises from the absence of an upper bound on the transaction validity; (ii) a premium escape attack, which results from multiple refund transactions for the same assets being simultaneously valid; and (iii) a topological limitation, which implies that universal multi-party swaps can support only a special class of strongly connected digraphs, called reuniclus graphs. In this paper, we propose GumSwap, a Griefing-free universal multi-party atomic Swap, which guarantees that a compliant party receives a premium if its asset is locked but not redeemed. To mitigate the timeout race attack and the premium escape attack, we impose minimum timeout intervals for the principal and premium timeouts, respectively, and introduce an asset migration mechanism that ensures that, during any time interval, at most one refund transaction is valid. Given the topological limitations of universal swap protocols, we further design a novel premium distribution mechanism that accommodates two classes of leaders in reuniclus graphs. Our experimental results demonstrate that GumSwap can be performed in less than 0.5 seconds per party, while reducing gas costs by 10.3X compared with existing contract-based solutions.

Universal atomic swaps [Oakland'22] replace hashed timelock contracts with adaptor signatures and verifiable timed dlogs, enabling secure cross-chain cryptocurrency exchanges that only require basic signature verification from the underlying blockchains. However, existing universal swap protocols remain vulnerable to griefing attacks, where a deviating party aborts the swap to lock a compliant party's assets for a long period. A natural approach is to lift existing contract-based solutions to the universal setting, but we identify that this straightforward solution faces two key challenges: (i) timeout race attacks, first identified in PipeSwap [Oakland'25], which arises from the absence of an upper bound on the transaction validity; (ii) a timeout overlap dilemma, which results from multiple overlapping refund periods. In this paper, we propose HedgeSwap, a universal hedged atomic swap protocol against griefing attacks, which compensates a compliant party with a premium if its asset is locked but not redeemed. To mitigate the timeout race attacks and timeout overlap dilemma, HedgeSwap eliminates the premium timeout and instead relies on a hard relation to refund the premium. For high-value asset swaps where the parties acceptable premium ranges do not overlap, we further propose a round-based HedgeSwap that utilizes a premium migration mechanism to solve these two timeout challenges, where parties iteratively increase the premium until the lock-up risk premium acceptable to both. Our experimental results show that our HedgeSwap can complete in under 0.5 seconds, and round-based HedgeSwap completes in under 1.3 seconds for a five-round setting, while HedgeSwap reduces gas cost by 2.69X compared to existing contract-based solutions.

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.

Identity-based matchmaking encryption (IB-ME) proposed by Ateniese et al. [CRYPTO 2019; Journal of Cryptology 2021] enables users to communicate privately, anonymously, and authentically. Following the seminal work of Ateniese et al., considerable research has been conducted on the security and construction of IB-ME schemes, but no scheme with enhanced privacy against chosen-ciphertext attacks is known. In this paper, we propose two IB-ME schemes that simultaneously achieve enhanced privacy against chosen-ciphertext attacks. The first scheme is built on the bilinear Diffie–Hellman assumption in the random oracle model. Inspired by the scheme of Ateniese et al., our construction attains stronger security guarantees while providing more compact decryption keys and ciphertexts than the scheme of Ateniese et al. The second scheme is a generic construction built upon anonymous identity-based encryption, digital signatures, NIZK systems, and reusable extractors. This scheme is obtained by generalizing the specific scheme of Francati et al. [INDOCRYPT 2021] with several technique to solve CCA-related issues. It constitutes the first IB-ME scheme achieving the stronger security notions in the standard model. As an additional contribution, we classify existing authenticity notions for IB-ME into four categories—no message attacks (NMA) and chosen message attacks (CMA), each considered against both insiders and outsiders. This taxonomy enables a precise comparison among existing IB-ME schemes.

In this article, we present a side-channel attack on unprotected implementations of the Berlekamp-Massey (BM) algorithm in both the reference implementation and an embedded implementation of the Classic McEliece KEM, where BM is used during decapsulation as part of the decoder implementation. We conduct a chosen cipher-text key recovery attack that exploits the power consumption of the BM, which is highly dependent on the secret Goppa support elements. We exploit the relation between plain-texts of small Hamming weight, secret elements in the Goppa support and power traces using an efficient Template Attack. Our method completely recovers the secret Goppa support for the first parameter set of the Classic McEliece KEM using a single attack trace per secret coefficient. The entire support can be recovered in less than 50 seconds. The remaining part of the secret, the Goppa polynomial, is recovered using Kirshanova and May’s algorithm (“Breaking Goppa with hints”) in less than 1 minute. Our experiments are performed on the reference implementation using the ChipWhisperer-Lite board platform with the ARM Cortex-M4 microcontroller. We also provide further insights into other implementations as well as an overview of possible extensions and limitations of our attack.

The Ethereum Foundation recently announced the Proximity Prize which aims to resolve some open problems that play an important role in the design of succinct proof systems. This paper reviews the open problems relevant to the Proximity Prize. We focus on some grand challenges relating to list decoding bounds, proximity gaps, correlated agreement, and mutual correlated agreement,as they relate to proof systems and Reed--Solomon codes. Along the way we survey the known results on these topics.

Cryptographic migration, particularly in the post-quantum setting, poses significant practical challenges and requires reliable performance data to support sound engineering decisions. For ML-DSA, however, existing benchmarking practices often produce misleading or non-comparable results, complicating migration and cryptographic agility efforts. This paper analyzes common pitfalls in benchmarking ML-DSA signature operations, including subtle inconsistencies when comparing security levels. We show that execution-time variability of the ML-DSA signing algorithm - an inherent property due to rejection sampling and other data-dependent components - makes commonly used straightforward metrics, e.g., min/average/max, unsuitable for migration planning. To address this gap, we propose a robust benchmarking methodology based on standardized input data sets and clearly qualified reporting metrics. The proposed approach enables fair comparison across hardware and software implementations and supports designers of real-time systems to assess the worst-case execution time.

Actively secure multi-party computation in the honest-majority setting often relies on multiple parties computing the same message to be sent. This additional redundancy allows to detect when a party deviates from the protocol. Many works utilize this for efficient protocol design, with some protocols delaying and batching consistency checks to further boost efficiency. In this paper, we show multiple cases where such batched consistency checks render the protocols insecure. Our concrete attacks derive additional knowledge from the batched consistency checks, reconstructing values on intermediate wires. Specifically, we show concrete attacks on Trident (NDSS'20), Fantastic Four (USENIX Security'21) including its implementation in the popular MP-SPDZ framework (CCS'20), and Quad (PoPETS'25). Furthermore, we find how an imprecise specification of SWIFT (USENIX Security'21) can enable a similar attack and reveal a gap in their security proof. Finally, we propose a fix for all protocols with a small performance overhead. Our provably secure fix uses a generic, joint consistency check that replaces the former, insecure consistency checks.

Privacy-Preserving Machine Learning (PPML) is a methodology designed to maintain data privacy throughout the machine learning pipeline. Although cryptographically protecting input privacy at the training phase is theoretically feasible, it remains computationally intensive in practice. As such, most recent works in this area focus on the inference phase. In contrast, we consider the training phase. Our goal is to enable machine learning engineers to use customer data earlier in the ML pipeline without compromising customer privacy or violating regulations. In this work, we introduce a framework named PriFT (Private Fine-Tuning), which leverages a transformer as a feature extractor and then performs training of a neural network on privacy-protected features. PriFT supports fully-private training, where the data is encrypted in the entire ML pipeline, as well as semi-private training, which balances privacy and performance by decrypting the true and predicted labels during training. PriFT can perform secure training both by means of Multiparty Computation (MPC) and based on Homomorphic Encryption (HE), which allows for a direct comparison of the two most prevalent cryptographic solutions for secure computation on a real-world use case. The codebase of our experiments is fully open-sourced and based on well-established libraries, namely Crypten and TenSEAL. Our experimental results show that the MPC approach largely outperforms the HE approach, especially in the semi-private setting. Furthermore, the MPC-based solution in the semi-private setting outperforms the fully-private training approximately by 3×, offering an adequate privacy-performance tradeoff. Our results show that both HE and MPC can achieve accuracy close to that of plaintext models.

Blind watermarking enables image ownership verification without requiring the original image. However, existing schemes usually require the owner to reveal the watermark seed and watermark positions during extraction. This creates a strong trust assumption on the verifier. Once such secrets are exposed, a malicious verifier can forge or remove the watermark. In this paper, we present TIM, the first publicly verifiable blind watermarking scheme with sensitive parameters privacy based on zero-knowledge proof. TIM reconstructs the extraction procedure of Integer DCT blind watermarking into an arithmetic-circuit-friendly form. This allows the owner to prove correct extraction without revealing the watermark seed or embedding positions. TIM addresses three main challenges. The first is the high proving cost for high-resolution images. The second is the conflict between circuit rigidity and watermark robustness. The third is the hashing overhead of iterative state binding. To address them, TIM combines Nova and Spartan to decompose full-image extraction into iterative proofs. It uses a threshold-based voting mechanism for robust detection. It also introduces a hierarchical state update mechanism to reduce circuit and memory costs. Experiments show that TIM preserves good imperceptibility and robustness while achieving practical efficiency. For a 4K image, proof generation takes 5.61 minutes and uses 9.61 GB peak memory. These results show that TIM is the first blind watermarking scheme to achieve seed privacy, public verifiability, and practical performance for high-resolution image ownership proofs.

Attribute-based inner-product functional encryption (AB-IPFE), introduced by Abdalla et al. (Asiacrypt'20), is a cryptosystem that combines the access-control capability of attribute-based encryption (ABE) with the linear-computation capability of inner-product functional encryption. By introducing a hierarchical structure between these two functionalities, we can decompose the key generation algorithm into two steps. While such a structure has been extensively studied in contexts such as hierarchical IBE and delegatable ABE, it has received little attention in AB-IPFE despite its naturalness. In this paper, we formalize a framework for two-level hierarchies in AB-IPFE and classify existing schemes according to their hierarchizability. In particular, we focus on adaptively secure schemes that support expressive access control, such as arithmetic programs in the public-index setting and attribute-hiding inner-product predicates in the private-index setting. To the best of our knowledge, the only efficient constructions known to meet these requirements are those obtained from the framework of Abdalla et al. in the private-index setting and from the scheme of Datta and Pal (Asiacrypt'21) in the public-index setting. We propose several new pairing-based constructions that achieve adaptive security. First, we revisit the approach of Abdalla et al. Based on their framework, we propose three types of constructions that trade off hierarchizability, ciphertext size, and secret-key size. These constructions are based on predicate encodings and therefore support arithmetic span programs or attribute-hiding inner-product predicates. Second, we revisit the approach of Datta and Pal. Their scheme supports attribute-weighted sums, which differ slightly from our target functionality. Although this already yields an AB-IPFE scheme, the resulting scheme is limited to the non-zero-type key-policy setting. We efficiently adapt their scheme to obtain AB-IPFE schemes that also support zero-type predicates, and we propose a ciphertext-policy variant. All of the resulting constructions can be hierarchized, but their intermediate secret keys are large. We also propose variant schemes with shorter intermediate secret keys, at the cost of somewhat larger final secret keys. These schemes support arithmetic branching programs.

Differential privacy (DP) has emerged as a rigorous framework for privacy-preserving data analysis, with widespread deployment in industry and government. Yet existing implementations typically assume that the party applying the mechanism can be trusted to sample noise correctly. This trust assumption is overly optimistic: a malicious party may deviate from the protocol to gain accuracy or avoid scrutiny, thereby undermining users’ privacy guarantees. In this paper, we introduce Noisette, a family of efficient protocols for certifying DP noise sampling across both discrete and continuous settings. We design a protocol that supports any discrete DP noise distribution through certifiable lookup table evaluation, and introduce a staircase-based optimization that greatly improves efficiency without compromising privacy or utility. We further extend this framework to continuous mechanisms, providing the first efficient protocol for certifiable continuous noise sampling with a rigorous end-to-end $(\epsilon,\delta)$-DP guarantee under standard floating-point arithmetic, closing the precision-induced privacy loss left open by prior work. We demonstrate the practicality of our protocols through concrete DP applications, including mean estimation and federated learning. Our protocols outperform the prior state-of-the-art by orders of magnitude in runtime and communication, while preserving the same accuracy as uncertified DP mechanisms. These results establish Noisette as the first efficient, scalable, and general-purpose solution for certifiable DP noise sampling, making certified privacy guarantees practical in high-stakes applications.

HAWK is a signature scheme that was introduced in 2022, and uses the lattice isomorphism problem (LIP) as a basis for post-quantum cryptography. In this work, we describe a classical algorithm that recovers the HAWK secret key in probabilistic polynomial time, assuming four number-theoretic heuristics. The reduction from the rank-2 module-LIP instances underlying HAWK to nrdPIP (Eurocrypt '25) is central to our algorithm. At a high level, we first conjugate the HAWK public Gram matrix $G$ by a random lower-triangular unimodular matrix $U$ with `short' entries, forming a new Gram matrix $G':=U^\ast GU$, and then test whether the $\mathcal{O}$-nrdPIP instance attached to $G'$ is unusually easy. In particular, for a non-negligible proportion of such instances $G'$, one can use the Lenstra-Silverberg algorithm to solve the corresponding $\mathcal{O}$-nrdPIP instance using a subfield approach. By resampling $U$ until such an instance is uncovered and solved, which can be seen as `re-randomising' the $\mathcal{O}$-nrdPIP instance whilst fixing the corresponding module-LIP instance, we are then able to recover a valid HAWK private key. At the time of writing, we do not claim that HAWK is broken, as we have not yet verified these heuristics experimentally. On the other hand, these heuristics seem to be very plausible, and we hope to be able to verify this in the future with an implementation of our algorithm. Update (30/06): Following discussions with Daniel Apon and Markku-Juhani Saarinen, we acknowledge that Heuristic 4 is insufficient to conclude that the main algorithm runs in polynomial time, and in fact the main algorithm appears to run in super-polynomial time. This mistake originates from the count of ideals of norm $q’$ in $\mathcal{O}_F$: one must include fractional ideals in this count, of which there are many. We note as an aside that Heuristics 1-3 have been independently experimentally verified. We would also like to thank the HAWK team and Alice Pellet-Mary for their responses to our work.

Non-interactive zero-knowledge (NIZK) proof systems are a cornerstone of modern cryptography, but their security has received little attention in the quantum settings. Motivated by improving our understanding of this fundamental primitive against quantum adversaries, we propose a new definition of security against quantum adversary. Specifically, we define the notion of quantum simulation soundness (SS-NIZK), that allows the adversary to access the simulator in superposition. We show a separation between post-quantum and quantum security of SS-NIZK, and prove that Sahai’s construction for SS-NIZK (in the CRS model) can be made quantumly-simulation-sound. As an immediate application of our new notion, we prove the security of the Naor-Yung paradigm in the quantum settings, with respect to a strong quantum IND-CCA security notion. This provides the quantum analogue of the classical dual key approach to prove the security of encryption schemes. Along the way, we introduce a new notion of quantum-query advantage functions, which may be used as a general framework to show classical/quantum separation for other cryptographic primitives, and it may be of independent interest.

Automated cryptanalysis has seen a lot of attraction and success in the past decade, leading to new distinguishers or key-recovery attacks against various ciphers. We argue that the improved efficiency and usability of these new tools have been undervalued, especially for design processes. In this article, we break for the first time the classical iterative design paradigm for symmetric-key primitives, where constructions are built around the repetition of a round function. We propose instead a new design framework, so-called uKNIT, that allows a round-by-round optimization-led automated construction of the primitives where each round can be entirely different from the others (the security/performance trade-off actually benefiting from this non-alignment). This new design framework being non-trivial to instantiate, we further propose a method for SPN ciphers using a genetic algorithm and leveraging advances in automated cryptanalysis: given a pool of good cipher candidates on $x$ rounds, our algorithm automatically generates and selects $(x+1)$-round candidates by evaluating their security and performance. We emphasize that our design pipeline is also the first to propose a fully automated design process, with completely integrated implementation and security analysis. We finally exemplify our new design strategy on the important use-case of low-latency cryptography, by proposing the uKNIT-BC block cipher, together with a complete security analysis and benchmarks. Compared to the state-of-the-art in low-latency ciphers (PRINCEv2), uKNIT-BC improves on all crucial security and performance directions at the same time, reducing latency by 10%, while increasing resistance against classical differential/linear cryptanalysis by more than 10%. It also reduces area by 17% and energy consumption by 44% when fixing the latency of both ciphers. As a contribution of independent interest, we discovered a generalization of the Superposition-Tweakey (STK) construction for key schedules, unlocking its application to bit-oriented ciphers. We also discuss the benefits of uKNIT to many other possible use-cases.

We show that the runtime complexity of the attack described in \emph{``Cryptanalysis of HAWK: a Guessing Game''} is much higher than originally claimed by its authors, and the attack is unlikely to pose a threat to HAWK's security in its present form. The attack algorithm had not been implemented before this work; the polynomial-time running-time claim was based on four ``plausible heuristics''. Our experiments and implementation data point to a super-polynomial class-number obstruction, consistent with exponential-scale growth. The experiments also helped to identify faulty ``Heuristic 4'' as the source of the observed computational wall when scaling dimension $n$. The authors of Guessing Game have acknowledged our findings. To make the argument more universal, we also offer a machine-checked conditional reduction from explicit assumptions that shows the complexity to be at least super-polynomial. In terms of methodology, our work demonstrates the role of powerful AI tools in contemporary cryptanalysis -- the sudden feasibility of rapid exploration and trial implementation of advanced attack techniques. A public research artifact contains all source code and datasets to reproduce our results.

Federated Learning (FL) enables collaborative model training without centralizing raw data, but remains vulnerable to gradient inference attacks, malicious aggregation servers, and communication inefficiencies. Existing cryptographic secure aggregation schemes provide confidentiality and verifiability yet lack formal statistical privacy guarantees, while most differential privacy (DP)-based approaches rely on fixed noise injection, resulting in suboptimal privacy--utility tradeoffs. This paper proposes HEAD-FL, a secure and efficient federated learning framework that integrates adaptive differential privacy with verifiable homomorphic aggregation. The proposed scheme introduces a round-adaptive Gaussian perturbation mechanism analyzed under the Rényi Differential Privacy (RDP) framework, enabling tight cumulative privacy accounting and explicit conversion to $(\varepsilon, \delta)$-DP guarantees. By adopting Federated Averaging (FedAvg) instead of gradient-based aggregation, the framework significantly reduces communication overhead while preserving confidentiality, verifiability, and robustness to client dropouts. Theoretical analysis and experimental evaluation demonstrate that HEAD-FLachieves improved privacy--utility tradeoffs and enhanced communication efficiency compared with fixed-noise and gradient-based secure aggregation methods, making it suitable for deployment in privacy-sensitive and bandwidth-constrained environments.

The rapid proliferation of privacy-sensitive machine learning and scientific computing applications has intensified the demand for secure multi-party computation (MPC) protocols that can efficiently evaluate complex nonlinear functions. Despite four decades of research, MPC systems face two fundamental barriers: heavy offline preprocessing and limited support for transcendental functions. Existing preprocessing-free frameworks are confined to comparison-related functions (e.g., Bicoptor) and cannot handle exponentials or trigonometric functions. In this paper, we propose MCU (Mask-Compute-Unmask), a novel MPC architecture that directly supports a broad class of algebraic and transcendental functions without any offline preprocessing. MCU introduces a semi-honest, non-colluding helper party (HP) as an active computational engine: parties additively mask their inputs, the HP computes the target function on the aggregated masked data, and the parties then unmask using locally known masks. This paradigm enables constant-round, scalable protocols for general multiplication (2 rounds), power functions (2 rounds), exponentials (8 rounds), and trigonometric functions (2 rounds). All protocols achieve simulation-based security and rely solely on synchronized pseudorandom generators—no preprocessing, no polynomial approximations. To the best of our knowledge, MCU is the first MPC framework that simultaneously achieves preprocessing-free, constant-round, exact evaluation of exponentials and trigonometric functions—functions essential for scientific computing, differential privacy mechanisms, and advanced neural network architectures. Our multiplication protocol scales better than Beaver-based multiplication in multi-party settings, and our exponential and trigonometric protocols achieve sub-ULP accuracy. The rapid proliferation of privacy-sensitive machine learning and scientific computing applications has intensified the demand for secure multi-party computation (MPC) protocols that can efficiently evaluate complex nonlinear functions. Despite four decades of research, MPC systems face two fundamental barriers: heavy offline preprocessing and limited support for transcendental functions. Existing preprocessing-free frameworks are confined to comparison-related functions (e.g., Bicoptor) and cannot handle exponentials or trigonometric functions. In this paper, we propose MCU (Mask-Compute-Unmask), a novel MPC architecture that directly supports a broad class of algebraic and transcendental functions without any offline preprocessing. MCU introduces a semi-honest, non-colluding helper party (HP) as an active computational engine: parties additively mask their inputs, the HP computes the target function on the aggregated masked data, and the parties then unmask using locally known masks. This paradigm enables constant-round, scalable protocols for general multiplication (2 rounds), power functions (2 rounds), exponentials (8 rounds), and trigonometric functions (2 rounds). All protocols achieve simulation-based security and rely solely on synchronized pseudorandom generators—no preprocessing, no polynomial approximations. To the best of our knowledge, MCU is the first MPC framework that simultaneously achieves preprocessing-free, constant-round, exact evaluation of exponentials and trigonometric functions—functions essential for scientific computing, differential privacy mechanisms, and advanced neural network architectures. Our multiplication protocol scales better than Beaver-based multiplication in multi-party settings, and our exponential and trigonometric protocols achieve sub-ULP accuracy. To the best of our knowledge, MCU is the first MPC framework that simultaneously achieves preprocessing-free, constant-round, exact evaluation of exponentials and trigonometric functions—functions essential for scientific computing, differential privacy mechanisms, and advanced neural network architectures. Our multiplication protocol scales better than Beaver-based multiplication in multi-party settings, and our exponential and trigonometric protocols achieve sub-ULP accuracy.

Anonymous credentials enable privacy-preserving authentication but existing systems either lack support for predicate proofs or are tied to specific signature schemes without a formal framework. We propose the first constructive framework for anonymous credentials with native predicate proof support. The framework provides definitions of entities, operations, adversary models, and security properties—unforgeability, unlinkability, and minimal disclosure. To demonstrate its feasibility, we instantiate the framework with BBS signatures, Pedersen commitments, and ring signature based proofs. The instantiation yields compact credentials and efficient zero-knowledge predicate proofs. We prove that the instantiation satisfies all security properties under standard assumptions (q-SDH, discrete logarithm, and the zero-knowledge of the ring signature based proof). A performance evaluation confirms that credential issuance, verification, and predicate prove/verify are practical on standard hardware, with compact credentials and proofs whose communication cost grows modestly with the number and encoding length of proved attributes, and favorable runtime and storage relative to a CL-based baseline. Our framework provides a modular foundation for designing and analyzing anonymous credential systems with fine-grained attribute disclosure.

QR-UOV is a multivariate signature scheme derived from UOV that achieves compact public keys by exploiting quotient-ring structure, making it a promising candidate for post-quantum digital signatures. In QR-UOV, most parts of the public map are derived from the public key seed using a PRG. This public key expansion for QR-UOV includes rejection sampling to generate coefficients uniformly over $\mathbb{F}_q$, since QR-UOV uses a small odd-prime base field. However, this rejection sampling introduces extra data movement and irregular control flow. For the recommended parameter set, public-key expansion accounts for nearly 90% of the QR-UOV verification time. In this paper, we propose No Rejection Sampling (NoRS) QR-UOV, a variant of QR-UOV with rejection-sampling-free public-key expansion, which leaves the generation of secret-dependent coefficients unchanged. Concretely, the rejected value $q$ is deterministically mapped to $0$, which simplifies coefficient generation but introduces a slight bias in the resulting coefficient distribution. We evaluate the security impact of this modification through both theoretical and concrete analyses. Our results suggest that, for the proposed parameter sets, NoRS QR-UOV maintains the claimed security levels against the considered attacks. On the implementation side, we develop a high-speed implementation of NoRS QR-UOV for x86 processors with AES-NI and AVX2. Benchmark results on a Skylake platform show that NoRS consistently accelerates QR-UOV at all security levels, with the largest gain in signature verification. Under standard Round-2 parameter settings, benchmark results show that NoRS QR-UOV reduces the verification cost from $0.43$ to $0.30$ Mcycles at security level I, with comparable improvements at security levels III and V, corresponding to about $1.4\times$ speedup over standard QR-UOV. Overall, the results suggest that relaxing coefficient uniformity in public-key expansion is a practical and effective design choice for QR-UOV.

A promising direction for enabling private queries to large language models (LLMs) is with homomorphic encryption (HE). An open problem is performing token sampling under HE. In this paper, we introduce Hyperion, an efficient HE algorithm for inverse transform sampling, enabling private token sampling with 1 comparison depth, $O(1)$ amortized comparisons, and $O(\log n)$ rotations. We implement our approach and demonstrate that it samples tokens in 0.14 seconds for 32k tokens ($\approx 4.4\, \mu\mathrm{s}$ per token) on GPU, achieving a $100\times$ latency improvement over prior work.

Attribute-based anonymous credential systems often fail to conceal the identity of the credential issuer. Recent attempts to address this limitation either suffer from efficiency issues or rely on security models that make unrealistic assumptions about the behavior of issuers. In this paper, we demonstrate that existing security models, which assume honest issuers, are inadequate for real-world deployments. Concretely, we present attack scenarios in which a malicious user collaborates with a single authorized issuer to forge credentials on arbitrary attributes, effectively allowing the user to assume the role of any trusted issuer without any possibility of identifying the misbehaving issuer. To address these shortcomings, we introduce a stronger security model that explicitly accounts for malicious issuers. We also propose a novel, issuer-hiding, anonymous credential scheme based on the BBS signature scheme (Eurocrypt~2023). This scheme is proven to be secure under the new model using a signed-policy approach. Our construction is fully based on BBS signatures, facilitating integration into existing standards, and resolves several open challenges posed by Katz and Sefranek (PKC~2026): (1)~it is proven secure in the Algebraic Group Model (AGM) rather than the Generic Group Model (GGM); (2)~it eliminates secret policy keys, enabling verification without any secret values; and (3)~it supports delegation of policy generation to a trusted certification authority. We further observe that issuer hiding inherently creates a tension between privacy and accountability: while concealing the issuer's identity protects honest users, it may grant plausible deniability to malicious issuers that deliberately certify false attributes. To resolve this, we introduce \emph{Accountable Issuer Hiding} (AIH), augmenting traditional issuer hiding with a controlled opening capability. Under AIH, every presentation contains an encryption of the issuer's public key under a designated opening authority's key, bound via zero-knowledge proofs to the credential and the verifier's policy. This ensures that fraudulent presentations remain attributable to the responsible issuer, even when malicious issuers provide users with opaque devices that generate valid presentations on demand. Finally, we introduce the first pairing-free issuer-hiding anonymous credential scheme, based on algebraic MACs. Formal security proofs and implementation results confirm that our schemes achieve unforgeability, everlasting issuer-hiding anonymity, and accountable issuer hiding, establishing them as practical and secure solutions for the forthcoming European Digital Identity (EUDI) Wallet.

Over the past half-decade, transparent succinct arguments have migrated off the 256-bit scalar fields of pairing-friendly elliptic curves and onto small fields: the 64-bit Goldilocks prime, the 31-bit primes BabyBear and KoalaBear, the Mersenne prime 2³¹−1 reached through the circle construction, and binary tower fields down to F₂. We call this movement the "small-field turn" and systematize it with the finite field, rather than the proof system or the virtual machine, as the unit of analysis. We organize the fields in use by the structural properties that drive their selection: machine-word fit, two-adicity, reduction cost, and the S-box automorphism structure exploited by algebraic hashes; and we show how each is realized in a production prover (Plonky2, Plonky3, Stwo, Binius, and their descendants). We then assemble, across systems that state it only individually, the relationship between base-field width and the extension degree that Fiat–Shamir soundness requires, and we set that relationship against the measured gap between conjectured and provable soundness for non-interactive FRI. Finally, we separate the peer-reviewed results on embedding and arithmetization overhead from the vendor benchmarks that dominate the topic, and identify the controlled cross-field comparison whose absence is the area's sharpest empirical gap. No prior work takes field choice as its organizing object across this design space; the nearest systematization treats it as one dimension among many within a zero-knowledge virtual machine taxonomy. We frame the turn as the exploration of a single trade, cheaper arithmetic against repurchased soundness and simulated non-native operations, and argue from the provenance of the fields where the frontier is likely to move next.

We study the problem of certifying statistical claims over datasets contributed by multiple independent sources. In this setting, an untrusted server aggregates signed data records and publishes claims such as sums, averages, or rates, while any third party can verify that these claims are correct with respect to the authenticated input data, without needing access to the underlying records. A central challenge is to achieve public verifiability without requiring trust in the aggregator, while keeping both the proof size and the verification cost small enough for practical deployment. This problem is motivated by applications in which reliable and scalable certification of published statistics is essential, including official health and demographic reporting. In this work, we present smklhs, a multi-key linearly homomorphic signature scheme for this setting. Compared to the state of the art, smklhs is the first practical construction to enjoy evaluated signatures of size logarithmic in the number of distinct signers involved in the computation, and else independent on the total number of input messages. We prove smklhs secure against fully adaptive adversaries in the random oracle and algebraic group models, under well-studied hardness assumptions in bilinear groups. We implement our scheme using the high-performance pairing library RELIC and compare it with prior work. To demonstrate practicality, we consider a case study on authenticated mortality statistics related to the impact of COVID-19 in Spain. At the 128-bit security level, our experiments show that an authenticated claim covering a 180-day nationwide dataset with over 300,000 signed records generated by 190 distinct signers can be verified in approximately 22 seconds on a commodity desktop machine. These results indicate that our approach is fast, lightweight, and practical for real-world deployment.

We demonstrate a general and efficient technique to Hensel-lift a solution to a system of ($p$‑adically analytic) equations which may be given implicitly in the form of an efficient evaluation algorithm. Contrary to textbook Hensel lifting, we do not require the equations to be represented explicitly; indeed, our main application uses the method for a system of equations that can be exponentially larger than its representation as an arithmetic circuit: we show how to compute traces of separable elliptic-curve endomorphisms over a finite field $\mathbb{F}_q$ by constructing an approximate lift to $\mathbb{Z}_q$. Our examples include endomorphisms represented as a chain of Vélu, √élu, modular, or radical isogenies, as well as HD‑embedded endomorphisms. The resulting trace-computation algorithm outperforms the state of the art both asymptotically and concretely.

We present a new algebraic modeling of the Supersingular Isogeny Problem as a system of multivariate polynomial equations, in the case where the elliptic curves are connected by an isogeny whose degree is a power of $2$ or $3$. This modeling relies on Renes formulas for elliptic curves in Montgomery form (degree $2$) or triangular form (degree $3$). We investigate several algebraic properties of these systems: we prove that they are zero-dimensional, compute the dimension of their highest degree part, and show that they are not in generic coordinates. Experimental results show that solving these systems via Gröbner basis techniques is significantly faster than solving the algebraic modeling with modular polynomials.

Fuzzy Labeled Private Set Intersection (FLPSI) lets a receiver learn the labels of enrolled records that are similar to its query, and nothing else. FLPSI can be built in several ways. Constructions based on a set-threshold reduction reach practical performance: a query matches a record when the two agree on a threshold number of components. These constructions delegate the private matching to an inner set-threshold kernel. We study its homomorphic form, which combines leveled-BFV homomorphic encryption (HE), a garbled circuit, and secret sharing to decide the match under encryption and release the record's label. We identify a composition gap in this kernel, an instance of a protocol-level problem: efficiency is bought with a per-trial false-accept probability, but one query runs a trial for every record, so the error compounds with the database size into the kernel's realization soundness error (RSE), the rate at which it accepts a query the plaintext matcher would reject. The RSE is a reliability property of the cryptographic matching layer, not the matcher's accuracy. On a spurious accept the kernel also returns a value the plaintext matcher would never produce. A sound kernel must contribute zero or negligible RSE of its own. We formalize this requirement as a composable security property, give a closed-form bound on the receiver's advantage, and close the gap with CSTPSI, a kernel that runs independent token rounds and raises the per-trial bound to a matching power. We prove CSTPSI secure in the semi-honest model. The closed-form bound sets the round count: two token rounds suffice for million-scale databases and three for billion-scale at the $10^{-6}$ engineering threshold. Our evaluation confirms the prediction. At a million records the baseline kernel's RSE reaches $100\%$ while CSTPSI holds it at $0$ in every measured configuration. CSTPSI decouples threshold-checking and upload costs from label size. For large labels at small to moderate scale it is more than $20\times$ faster than the baseline kernel, with up to $93\%$ less communication. It converges to the baseline only at the million-scale database size. Our implementation, with a one-command reproducibility harness, is publicly available.

We build two-server private information retrieval (PIR) that achieves information-theoretic security and strong double-efficiency guarantees. On a database of $n > 10^6$ bits, the servers store a preprocessed data structure of size $1.5 \sqrt{\log_2 n} \cdot n$ bits and then answer each PIR query by probing $12 \cdot n^{0.82}$ bits in this data structure. To our knowledge, this is the first information-theoretic PIR with any constant number of servers that has quasilinear server storage $n^{1+o(1)}$ and polynomially sublinear server time $n^{1-\Omega(1)}$. Our work builds on the PIR-with-preprocessing protocol of Beimel, Ishai, and Malkin (CRYPTO 2000). The insight driving our improvement is a compact data structure for evaluating a multivariate polynomial and its derivatives. Our data structure and PIR protocol leverage the fact that Hasse derivatives can be efficiently computed on-the-fly by taking finite differences between the polynomial's evaluations. We further extend our techniques to improve the state-of-the-art in PIR with three or more servers, building on recent work by Ghoshal, Li, Ma, Dai, and Shi (TCC 2025). On an 11 GB database with 1-byte records, our two-server PIR encodes the database into a 1 TB data structure – which is 4,500,000$\times$ smaller than that of prior two-server PIR-with-preprocessing schemes, while maintaining the same communication and time per query. To answer a PIR query, the servers fetch and send back 4.4 MB from this data structure, requiring 2,560$\times$ fewer memory accesses than linear-time PIR. The main limitation of our protocol is its large communication complexity, which we show how to shrink to $n^{0.31} \cdot \mathsf{poly}(\lambda)$ using compact linearly homomorphic encryption.

"Pebble games," an abstraction from classical reversible computing, have found use in the design of quantum circuits for inherently sequential tasks. Gidney showed that allowing Hadamard basis measurements during pebble games can dramatically improve costs—an extension termed "spooky pebble games" because the measurements leave temporary phase errors called ghosts. In this work, we define and study parallel spooky pebble games. Previous work by Blocki, Holman, and Lee (TCC 2022) and Gidney studied the benefits offered by either parallelism or spookiness individually; here we show that these resources can yield impressive gains when used together. First, we show by construction that a line graph of length $\ell$ can be pebbled in depth $2\ell$ (which is exactly optimal) using space $\leq 2.47\log \ell$. Then, to explore pebbling schemes using even less space, we use a highly optimized $A^*$ search implemented in Julia to find the lowest-depth parallel spooky pebbling possible for a range of concrete line graph lengths $\ell$ given a constant number of pebbles $s$. We show that these techniques can be applied to Regev's factoring algorithm (Journal of the ACM 2025) to significantly reduce the cost of its arithmetic. For example, we find that 4096-bit integers $N$ can be factored in multiplication depth 193, which outperforms the 680 required of previous variants of Regev and the 444 reported by Ekerå and Gärtner for Shor's algorithm (IACR Communications in Cryptology 2025). While the space required for Shor's algorithm is considerably less than any variant of Regev's algorithm including ours, and thus Shor likely remains the best candidate for the first quantum factorization of large integers, our results show that implementations of Regev's algorithm are far from fully optimized, and thus Regev's algorithm may have practical importance in the future. We also believe our pebbling techniques will find applications in quantum cryptanalysis beyond integer factorization, and in quantum circuit compilation more broadly.

In this work, we introduce a new toolkit for analyzing \emph{cloning games}, a notion that captures stronger and more quantitative versions of the celebrated quantum no-cloning theorem. This framework allows us to analyze a new cloning game based on \emph{binary phase states}. Our results provide evidence that these games may be able to overcome important limitations of previous candidates based on BB84 states and subspace coset states: in a model where the adversaries are restricted to making a single oracle query, we show that the binary phase variant is $t$-copy secure when $t=o(n/\log n)$. Moreover, for constant $t$, we obtain the \emph{first} optimal bounds of $O(2^{-n})$, asymptotically matching the value attained by a trivial adversarial strategy. We also show a worst-case to average-case reduction which allows us to show the same quantitative results for the new and natural notion of \emph{Haar cloning games}. Our analytic toolkit, which we believe will find further applications, is based on binary subtypes and uses novel bounds on the operator norms of block-wise tensor products of matrices. To illustrate the effectiveness of these new techniques, we present two applications: first, in black-hole physics, where our asymptotically optimal bound offers quantitative insights into information scrambling in idealized models of black holes; and second, in unclonable cryptography, where we (a) construct succinct unclonable encryption schemes from the existence of pseudorandom unitaries, and (b) propose and provide evidence for the security of multi-copy unclonable encryption schemes.

We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA integers themselves). Most notably, we factor $n$-bit integers of the form $P^2 Q$ with $\log Q = \Theta(n^a)$ for $a \in (2/3, 1)$ in space and depth sublinear in n (specifically, $\widetilde{O}(\log Q)$) using $\widetilde{O}(n)$ quantum gates; for these integers, no known classical algorithms exploit the relatively small size of $Q$ to run asymptotically faster than general-purpose factoring algorithms. To our knowledge, this is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem. Our circuit builds on the quantum algorithm for squarefree decomposition discovered by Li, Peng, Du, and Suter (Nature Scientific Reports 2012), which relies on computing the Jacobi symbol in quantum superposition. The technical core of our contribution is a new space-efficient quantum algorithm to compute the Jacobi symbol of $A$ mod $B$, in the regime where $B$ is classical and much larger than $A$. Our circuit for computing the Jacobi symbol generalizes to related problems such as computing the greatest common divisor and modular inverses, and thus could be of independent interest.

Hash-based low-degree tests and polynomial commitment schemes have become the cryptographic engine of a large fraction of deployed succinct-argument systems. Unlike pairing-based commitments such as KZG, they require no trusted setup, rely only on a collision-resistant hash, are plausibly post-quantum, and operate over any sufficiently large field, unlocking small fields whose arithmetic is fast on commodity hardware. Between 2017 and 2025 this design space evolved rapidly along two intertwined lineages: the Reed-Solomon proximity-test line (FRI, DEEP-FRI, STIR, WHIR) and the linear-code tensor-commitment line (Ligero, Brakedown), which Basefold and WHIR ultimately merge. Yet the primary sources report their guarantees under different, and frequently conflated, soundness regimes: unique decoding, the Johnson list-decoding bound, and (conjecturally) capacity. The folklore surrounding these schemes has drifted from what the papers actually prove. We systematize this line of work. We organize the seven core schemes along a taxonomy of committed object, code class, and testing mechanism; we trace the evolutionary chain in which each scheme answers a concrete limitation of its predecessor; and we ground the theory in a survey of production zero-knowledge systems, showing how field choice and soundness regime jointly explain real engineering decisions, including a sumcheck-based multilinear prover reaching mainnet in 2026. We make two systematizing corrections. First, the DEEP folklore: the out-of-domain trick that survives in deployment (DEEP-ALI, on the constraint side) is distinct from the low-degree-test modification it is usually conflated with. That modification was superseded for FRI soundness by the Proximity Gaps analysis, which also proves Johnson-bound FRI soundness and is itself routinely misattributed to the original FRI paper. Second, and more consequential: the capacity-soundness conjectures on which nearly all deployed systems set their parameters had their strongest, up-to-capacity forms, including the mutual-correlated-agreement conjecture behind the newest schemes, disproved over large fields in late 2025. Soundness up to the Johnson bound is unaffected and the practical repricing is modest, but the discount the ecosystem had tacitly taken was, in its optimistic form, wrong. Our central thesis is that this proven-versus-conjectured soundness axis, not asymptotic query complexity, is the load-bearing and least-consistently-reported dimension of the design space, and the field has now had to reprice it.

Secure Multi-Party Computation (MPC) enables collaborative analytics without exposing raw data. Yet, complex data retrieval operations in relational databases (i.e., relational queries) remain limited by scalability bottlenecks: oblivious operators must pad intermediate results to worst-case sizes to prevent information leakage, thereby inflating communication and computation costs. We propose Resizer, a lightweight operator that can be inserted transparently into relational query plans to bound intermediate result sizes while preserving rigorous privacy guarantees. Resizer reduces intermediate results from fully-oblivious to noisy size bounds that satisfy differential privacy (DP). We propose two Resizer variants, shuffle-based and sort-based, and provide a formal analysis of the privacy guarantees and security in the semi-honest model. We evaluate the Resizer variants in the ORQ framework under semi-honest and honest-majority assumptions using TPC-H benchmark queries, demonstrating that Resizer incurs negligible overhead while reducing data volume. In both LAN and WAN settings, complex queries achieve speedups compared with state-of-the-art oblivious baselines, confirming that Resizer reduces the padding bottleneck and enables scalable, privacy-preserving relational analytics.

Garbled circuits are a fundamental primitive in cryptography. While the size of garbled circuits in Yao's original scheme grows linearly with the circuit size, a recent line of work on stacked garbling (SGC) [Heath-Kolesnikov, CRYPTO'20] has achieved near-sublinear size for branching computations, based only on one-way functions. Specifically, these schemes achieve garbled size growing only with the size of a single branch and the total input length to all the branches. Due to the latter dependence, these results are best suited to "small" input settings. We present a stacked garbling scheme for "large" input settings based on one-way functions. The garbled size in our scheme grows only with the size of a single branch and its input length (up to logarithmic factors), plus an additive term in the number of branches (as in prior SGC). To obtain our result, we uncover a connection between stacked garbling and the notion of (adaptive) programmable pseudorandom functions (apPRFs) [Boneh-Lewi-Wu, PKC'17]. While existing apPRF constructions either rely on stronger assumptions (e.g., learning with errors or indistinguishability obfuscation) or incur noticeable security losses under weaker assumptions, we identify a relaxed notion of suffix-invariant programmable PRFs (sipPRFs) that suffices for our result, and establish its feasibility based on OWFs. Interestingly, we build on techniques from the SGC literature to construct sipPRFs with our desired efficiency, and then apply sipPRFs back to SGC to obtain our main result. Along the way, as an additional result of independent interest, we provide the first construction of (adaptive) programmable PRFs for polynomial-size domains based on one-way functions.

Any signature scheme has to protect its secret key via some properly chosen, secret randomness. We show that, for the lattice signatures \textsf{HAWK}, Falcon and ML-DSA, even minimal leakage of this randomness suffices for secret key recovery. In particular, leaking either the Hamming weight or a single bit of any randomness coordinate allows an attacker to infer the sign of that coordinate. This corresponds to learning $\textrm{sign}(\langle \mathbf b, \mathbf w \rangle)$, where $\mathbf b$ is the secret key and $\mathbf w$ is public. We model key recovery from such sign information as an instance of Learning a Halfspace. This well-studied problem from learning theory provides a rich solution machinery, which we adapt for the cryptanalysis of lattice-based signatures. As a first main result, we resolve the open problem of recovering the secret key in \textsf{HAWK} from sign leakage. At the 128-bit security level and in the noise-free setting, we recover the secret key from only 30 signatures in 10 minutes. As a second main result, we recover the secret key in Falcon via sign leakage from only 100 signatures in under a minute. In comparison to existing attacks, this reduces the number of required signatures by a factor of $250$. As a third result, we show the first ML-DSA secret key recovery from sign leakage, which requires 190,000 signatures and completes within seconds. In comparison to existing ML-DSA attacks, we require a comparable amount of signatures, but utilize a less restrictive leakage model. In addition, our attack is alarmingly noise-tolerant, succeeding with up to 35\% noise for \textsf{HAWK}, 30\% for Falcon, and 35\% for ML-DSA, albeit requiring significantly more signatures in the noisy case.

Given a set of $k$-sparse linear equations over a ring $R$, we give algorithms to determine whether the right-hand sides are random or have a secret assignment planted with noise. For a parameter $k/2\leq l\leq n$, we give a spectral method to solve this problem in $\widetilde{O}\left(\binom{n}{l}\lvert{R}\rvert^l\right)$ time except with probability at most $n^{-\Omega(l)}$, provided the number of samples is roughly at least $\left(\frac{\lvert{R}\rvert n}{l}\right)^{k/2}$. This attack generalizes the Kikuchi method described by Wein et. al. (Journal of the ACM 2019) for $\mathbb{Z}_2$ to (commutative) rings of any finite size. We also give a simpler algorithm with better runtime than the spectral method and better sample complexity when $\lvert{R}\rvert =\omega(n/l)$. As a consequence, we obtain new sample-time tradeoffs for the decision problem of sparse LWE, sparse LPN over higher modulus $q$, and in general the distinguishing random vs planted $\mathbb{Z}_q$-linear equations for a large class of noise distributions. Our results imply a tightness of the hardness claims of Jain, Lin, Saha (Annual International Cryptology Conference, 2024) for sparse LWE.

Multiplicative complexity have shown to be an important metric for efficient implementations in various contexts such as side-channel secure implementation and transciphering. We introduce a generic framework based on conjugacy to reduce the multiplicative complexity of block ciphers. Our approach exploits the iterative structure of the block cipher to build alternative implementation based on conjugate round operations with overall smaller multiplicative complexity. We apply this methodology to the Skinny family of block ciphers and derive optimized implementations for all versions. By carefully analyzing the interaction between the non-linear and linear layers, we construct an alternative implementation that reduces the number of multiplications. For Skinny64, we obtain a gain of 5.5 percent, while for Skinny128, the gain reaches 3 percent.