Papers updated in last 183 days (Page 17 of 2708 results)

Last updated:  2026-08-28
WeaveTLS: High-Throughput Cross-Connection ML-DSA Authentication in Mutual TLS
Ganqin Liu, Hao Cheng, and Jipeng Zhang
Mutual TLS (mTLS) authenticates both peers and therefore incurs post-quantum signature costs on every connection. Concurrent handshakes expose independent ML-DSA operations, but executing them jointly is difficult: signing is rejection-divergent, verification uses heterogeneous keys, and synchronous TLS APIs expose authentication work one connection at a time. We present WeaveTLS, a wire-transparent architecture that executes ML-DSA authentication across concurrent TLS connections. Its primitive interface combines rejection-aware slot refill with per-request expanded-key handles, supporting both unrelated client keys and shared issuer keys. A stackless OpenSSL continuation lets an nginx worker suspend authentication, expose work from other connections, and execute compatible operations through optimized single-request, four-request, or eight-request AVX-512 kernels without fibers or cross-thread handoff. WeaveTLS preserves the TLS authentication barrier, certificate validation, and wire protocol. On an AMD Ryzen 9 9950X3D, WeaveTLS improves one-core nginx mTLS throughput by 2.81-4.31$\times$ over OpenSSL's default ML-DSA path and by 2.19-3.29$\times$ over a synchronous reference-C control in the same provider across ML-DSA-44/65/87. At the primitive boundary, expanded-key eight-request verification is 1.65-2.23$\times$ faster than matched cached AVX2, and rejection-aware refill makes ML-DSA-65 signing 1.90$\times$ faster than otherwise identical lockstep scheduling. Cohort publication also weakens client-visible rejection timing under load, reducing attempt-count/latency correlation to 0.063 at concurrency 16 and 0.008 at 64; singleton execution retains the signal.
Last updated:  2026-08-28
AVXPoS: Reducing Consensus Verification Cost in the Ethereum Proof-of-Stake Client
Ganqin Liu, Hao Cheng, Georgios Fotiadis, Jipeng Zhang, and Chen Qian
Ethereum Proof-of-Stake (PoS) clients must verify large volumes of Boneh--Lynn--Shacham (BLS) signatures for attestations, sync-committee messages, and other consensus-critical objects within fixed slot deadlines. This recurring cost competes with state transition, fork choice, and message propagation for client CPU time, so reducing it increases the verification headroom available under bursty load. Prior cryptographic-engineering work has shown that SIMD can substantially accelerate BLS verification kernels, but these gains do not automatically survive client software boundaries, runtime scheduling, and irregular verification ranges. We present AVXPoS, a client-aware batching framework for BLS verification in the Prysm Ethereum PoS client. AVXPoS treats batched verification as a client-level systems problem: it preserves Prysm's verification semantics while reorganizing protocol-shaped requests into native batched states that expose SIMD parallelism across API, worker, and native-backend boundaries. We instantiate AVXPoS with an AVX-512 backend for BLS12-381, combining Go-side range formation with C-side width-adaptive dispatch. On a resource-constrained two-core Intel host, AVXPoS gains $1.44$--$2.10\times$ over Prysm's production \texttt{blst} backend at selected small batch sizes that bracket the post-aggregation $p50/p95/p99$ batch-size quantiles of an all-subnets steady-state mainnet stress trace, and reaches up to $3.18\times$ in controlled capacity sweeps. On a 16-core AMD host, a production checkpoint-backfill verifier at Ethereum's 128-block request cap improves by $1.81\times$. Cross-platform results indicate that the relative speedup depends in part on Prysm's worker budget, because worker partitioning determines how much SIMD parallelism remains within each native range.
Last updated:  2026-08-28
VROOM: Accelerating (Almost All) Number-Theoretic Cryptography Using Vectorization and the Residue Number System
Simon Langowski, Kaiwen He, and Srinivas Devadas
Modular arithmetic with a large prime modulus is a dominant computational cost in number-theoretic cryptography. Modular operations are especially challenging to parallelize efficiently on CPUs using vector instructions; standard CPU implementations rely on costly carry operations and permutation instructions to align with the multiplication datapath, negating the benefits of vectorization. We develop vectorized algorithms for modular addition and multiplication, and present a new, constant-time modular multiplication algorithm suitable for general moduli - prime or otherwise. Our method uses a Residue Number System (RNS) representation to align the arithmetic naturally with wide vector units, and strategically eliminate extraneous instructions. Existing works either require the use of customized hardware or fail to show latency improvements. Reducing the latency of modular arithmetic results in speedups for cryptographic applications. We accelerate RSA-4096 signatures by $4.0\times$ (verify) and $1.3\times$ (sign) over OpenSSL, and speed up BLS signature verifications by $4.05\times$ over the assembly-optimized BLST library. Results on mapping our algorithm to Nvidia GPUs demonstrate speedups on modular multiplication over Nvidia's CGBN library.
Last updated:  2026-08-28
Enhanced Differential-linear Cryptanalysis of Forr\'{o} with MILP
Zhengting Li, Lin Ding, Xinhai Wang, Honglei Wang, Jiang Wan, and Fan Zhang
ARX-based design is a major building block of modern cryptographic ciphers due to its efficiency in software. Forr\'{o} is an ARX-based stream cipher proposed by Coutinho et al. at ASIACRYPT 2022, which was designed to provide higher security margin than the ChaCha stream cipher. In this paper, we propose a full automated MILP model called \textit{MinForr\'{o}}, to derive linear approximations for the Forr\'{o} stream cipher. For the differential part, a two-stage strategy to search for single-bit differential trails with high differential correlations is presented, which helps us to find the first-ever 3-round differential trails for Forr\'{o}. By combining the linear approximations obtained by \textit{MinForr\'{o}} and 3-round differential trail for Forr\'{o}, we propose improved differential-linear distinguishers for 4-, 5-, 5.25-, 5.5-, 5.75-, 6-, 6.25- and 6.5-round Forr\'{o} with complexities ${2^{32.44}}$, ${2^{46}}$, ${2^{50}}$, ${2^{64.32}}$, ${2^{87.12}}$, ${2^{117.92}}$, ${2^{174.92}}$ and ${2^{226.88}}$, respectively. The proposed differential-linear distinguishers for 4-, 5-, 5.25- and 5.5-round Forr\'{o} significantly improve the existing distinguishers by factors of ${2^{4.11}}$, ${2^{83.68}}$, ${2^{127.64}}$ and ${2^{178.20}}$, respectively. To the best of our knowledge, this is the first differential-linear distinguisher for Forr\'{o} that reaches 6.5 rounds, which is a significant advancement over the existing record of 5.5 rounds. We have implemented the differential-linear distinguishers for 4- and 5-round Forr\'{o} on a common PC, and the experimental results confirm the correctness of these distinguishers. Furthermore, when combined with the \textit{Probabilistic Neutral Bits} (PNB) technique, we obtain key recovery attacks on 5.5-, 6-, 6.5- and 6.75-round Forr\'{o} with time complexities ${2^{149.20}}$, ${2^{151.84}}$, ${2^{213.49}}$ and ${2^{251.97}}$, respectively. The proposed key recovery attack on 5.5-round Forr\'{o} significantly improves the time complexity of the existing attack by a factor of ${2^{75.84}}$. To the best of our knowledge, this is the first key recovery attack on Forr\'{o} that reaches 6.75 rounds, which is a significant advancement over the existing record of 5.5 rounds.
Last updated:  2026-08-28
FLIP-and-prove R1CS
Anca Nitulescu, Nikitas Paslis, and Carla Ràfols
We present the first folding framework that achieves sublinear verification and communication when a single prover must convince a verifier of $k$ independent R1CS instances. - $\mathbf{FLIP}$ (Fold-Inner-Product) folds the $k$ instance-witness pairs in only $\log k$ rounds. Built on the homomorphic two-tier commitment of Abe et al. (CRYPTO 2010), FLIP transmits $O(\log k)$ group elements. - $\mathbf{r \operatorname{-} Groth}$ is a commit-and-prove variant of Groth16 that natively handles relaxed R1CS. It retains Groth16’s three-element proof and two pairing checks, requires only a slightly modified (instance-independent) trusted setup, and does not rely on elliptic-curve cycles or foreign-field arithmetic. Combined, FLIP + r-Groth replace the $k-1$ extra Groth16 proofs demanded by aggregation schemes and avoid the heavy verifier-in-circuit logic of recursive systems. The total prover work is essentially one Groth16 run plus light folding, while the verifier processes $O(\log k)$ group elements and two pairings. This design is immediately applicable to roll-ups, Proof-of-Space, and other "proving-as-a-service" scenarios where all witnesses reside on a single machine.
Last updated:  2026-08-28
Efficient Polynomial Multiplication for HQC on ARM Cortex-M4
Jihoon Jang, Myeonghoon Lee, Donggeun Kwon, Seokhie Hong, Suhri Kim, and Sangjin Lee
In this paper, we propose the Hybrid FAFFT-CRT method for accelerating HQC polynomial multiplication on the ARM Cortex-M4. The method uses the Chinese Remainder Theorem to map the polynomial ring to a product of an FAFFT-friendly ring of size $2^{d+1}$ and a small-degree residual ring, reducing the FAFFT transform length by half compared to the state-of-the-art. We also present the Hybrid Karatsuba-FAFFT method as an alternative hybrid based on a 2-way Karatsuba split, and apply radix-16 multiplication to HQC for the first time, with an operation-count cost model for selecting Karatsuba and Toom-Cook combinations. Additionally, we improve the core FAFFT butterfly through shortened XOR sequences, register scheduling, and SWAPMOVE-based bit swaps. On a NUCLEO-L4R5ZI board with a Cortex-M4 microcontroller, the Hybrid FAFFT-CRT method reduces polynomial multiplication cycles by 36.0% and 29.3% for HQC-1 and HQC-3, leading to cycle reductions for key generation, encapsulation, and decapsulation by 25.5%, 26.1%, and 23.5% for HQC-1, and 19.3%, 20.0%, and 19.1% for HQC-3. For HQC-5, our optimized butterfly FAFFT provides a consistent speedup of 1.4-1.6% across all KEM operations.
Last updated:  2026-08-28
Olingo: Threshold Lattice Signatures with DKG and Identifiable Abort
Kamil Doruk Gur, Patrick Hough, Jonathan Katz, Caroline Sandsbråten, and Tjerand Silde
We present Olingo, a framework for threshold lattice signatures that is the first to offer all desired properties for real-world implementations of quantum-secure threshold signatures: small keys and signatures, low communication and round complexity, non-interactive online signing, distributed key generation (DKG), and identifiable abort. Our starting point is the framework by Gur, Katz, and Silde (PQCrypto 2024). We change the underlying signature scheme to Raccoon (Katsumata et al, Crypto 2024), remove the trapdoor commitments, extend the scheme from two to three rounds, and then apply numerous improvements and optimizations to achieve all the above properties. We provide detailed proofs of security for our new framework and present concrete parameters and benchmarks. At the $128$-bit security level, for up to $1024$ parties and supporting $2^{60}$ signatures, our scheme has $4.4$ KB public keys and $11.3$ KB signatures; while signing requires communication of $852$ KB per party using the LaBRADOR proof system (Beullens and Seiler, Crypto 2023). An optimistic non-interactive version of our scheme requires only $76$ KB communication per party.
Last updated:  2026-08-28
Differential Fault Attack on Atom: Bypassing the Double Key Filter using Filtered Faults
Vaibhav Dixit, Satyam Kumar, and Santanu Sarkar
In this paper, we present a Differential Fault Attack (DFA) on the lightweight stream cipher Atom, proposed by Banik et al. in IACR Transactions on Symmetric Cryptography (TOSC)-2021. It employs two key filters simultaneously during the pseudo-random generation algorithm phase, one of which depends on LFSR state bits. Due to this LFSR-dependent key filter, the authors claim that forming algebraic equations relating key and state bits as variables to the keystream bits is difficult unless the entire LFSR state is known. In contrast, we propose a method to formulate such algebraic equations without guessing any LFSR bits. This enables us to implement a successful DFA on Atom. To the best of our knowledge, this is the first successful DFA reported on Atom . In the proposed DFA, we identify the location of injected faults using a weighted ensemble of trained MLP and XGBoost models. To further improve accuracy, we filter out ML predictions with confidence below a predefined threshold. We found that this strategy significantly reduces the number of SAT solver invocations and improves the overall time complexity of the attack. Based on our experiments, we demonstrate a successful DFA on Atom within a practical time by injecting 18 faults, provided all are correctly identified. Obtaining a set of 18 correctly identified faults requires, on average, 52 fault injections. The attack requires a total of 70 keystream bits (normal and faulty combined) just after a fault injection and guessing two random key bits.
Last updated:  2026-08-28
HyperSolver: Asymptotically and Concretely Accelerating the Delfs–Galbraith Attack using Isogeny Ladders
Lorenz Panny, Ryan Rueger, Alessandro Sferlazza, and Aleksei Udovenko
We present a new variant of the memoryless Delfs-Galbraith algorithm for finding an isogeny path from any given supersingular elliptic curve to a curve with known endomorphism ring. Through existing polynomial-time reductions, our algorithm allows one to solve the supersingular endomorphism-ring problem which lies at the heart of isogeny-based cryptography. For arbitrary characteristics $p$ our algorithm asymptotically outperforms the previous best Delfs-Galbraith variant by a logarithmic factor; and matches the best previous asymptotic for characteristics with favourable structure. In addition to the asymptotic analysis, we also calculate a concrete cost estimate for our algorithm in terms of finite-field operations, which indicates that our expected cost is lower than all previous Delfs-Galbraith variants, even concretely. By substituting bit-operation counts for the cost of arithmetic, we can deduce concrete bit-security estimates for isogeny-based cryptographic primitives, including (but not limited to) SQIsign. As part of the calculation of the expected cost, we also provide a novel analysis of the probability of encountering "distinguished" subgraphs in an expander graph when relying various modes of graph exploration, whose potentially counterintuitive behaviour had apparently remained unnoticed thus far. Finally, we provide a complete implementation of our algorithm(s), with the asymptotic bottleneck being attacked on GPUs, and the easier post-processing done on CPU using C++ as well as SageMath. Preliminary experimental results suggest that we can solve $100$-bit instances of the problem within less than $100$ GPU hours. For comparison, the current cryptanalytic record for ECDLP (which has a comparable classical attack complexity) stands at $114$ bits, achieved using significantly more hardware and time.
Last updated:  2026-08-28
LiftWHIR: A Prover-Efficient Polynomial Commitment with Short Proofs
Zhongliang Zhang, Xinxuan Zhang, Yuanju Wei, Lang Qin, and Yi Deng
Polynomial commitment schemes allow a prover to commit to a large polynomial and later prove a claimed evaluation at a chosen point. They are a core component of many efficient SNARKs, and the cost of their evaluation phase directly affects SNARK prover time. Reed--Solomon-based schemes already offer small proofs and fast verification, but generating an evaluation proof for a large polynomial remains expensive. We present LiftWHIR, a Reed--Solomon-based polynomial commitment scheme that reduces prover time in the evaluation phase. LiftWHIR combines interleaved coding with the DEEP(ITCS'20) technique to reduce proving an evaluation of a large polynomial to two smaller tasks: a proximity test on a shorter codeword and evaluation of a smaller polynomial. The use of DEEP simultaneously reduces the number of queries required by the proximity test. We then use WHIR(EUROCRYPT'25) to prove both resulting tasks, keeping verification and communication costs low. LiftWHIR trades a modest increase in proof size and verifier time for a substantial reduction in prover time. At $n=2^{20}$ over a 255-bit prime field and code rate $1/2$ (resp., $1/4$), LiftWHIR reduces the evaluation phase to 167 ms (resp., 169 ms), yielding a $4.4\times$ (resp., $6.7\times$) speedup over WHIR. Including commitment, LiftWHIR achieves total prover times of 808 ms (resp., 1,474 ms), corresponding to overall prover speedups of $1.61\times$ (resp., $1.55\times$). Verification time increases from 0.55 ms to 0.76 ms (resp., 0.40 ms to 0.51 ms), while proof size is $1.46\times$ (resp., $1.33\times$) that of WHIR. We further instantiate Spartan(CRYPTO'20) with LiftWHIR and compare it with a Spartan variant instantiated with WHIR. LiftWHIR speeds up proving by $1.9\times$, while verification time increases only from 3.86ms to 4.62ms, at the cost of a $42\%$ increase in proof size.
Last updated:  2026-08-28
Fast Post-Quantum Ring Signature from Power Residue PRFs with QROM Security
Xinyu Zhang, Ziyi Li, Ron Steinfeld, Raymond K. Zhao, Joseph K. Liu, and Tsz Hon Yuen
Ring signatures enable a user to sign anonymously on behalf of a group, providing a fundamental building block for privacy-preserving applications such as anonymous credentials and private transactions. Existing post-quantum constructions, however, face a persistent tension between efficiency and rigorous quantum security: practical schemes are typically analysed only in the classical random oracle model (ROM), whereas schemes with proofs in the quantum random oracle model (QROM) either incur multi-megabyte signatures, lack implementations, or rely on reductions too loose to support concrete parameter selection. We present PegaRing, the first post-quantum ring signature to combine practical performance with concretely parameterised security in QROM. At the 128-bit security level and a ring size of 1024, PegaRing produces 28KB signatures, reducing signature size by a factor of 88 relative to the smallest prior concretely parameterised QROM-secure construction. Our implementation signs in 4.325 ms and verifies in 3.074 ms. Compared with the state-of-the-art VOLE-in-the-head ring signature, which is proven secure only in classical ROM, PegaRing reduces signing and verification latency by factors of 2.65 and 3.80, respectively, while providing security in QROM. Finally, when using the first message-dependent Fiat-Shamir challenge as the boundary between offline and online computation, PegaRing's online signing phase takes 0.018 ms, compared with 7.611 ms for VOLE-in-the-head construction, achieving a reduction of more than 400 times. These results substantially narrow the gap between rigorous quantum security and practical performance for post-quantum ring signatures and make QROM-secure anonymous authentication feasible for various anonymity sets.
Last updated:  2026-08-27
Achieving vCCA security from the linear-only homomorphism assumption
Marina Checri, Pierre-Emmanuel Clet, Marc Renard, and Renaud Sirdey
In the wake of Manulis and Nguyen's Eurocrypt'24 paper, new CCA security notions, vCCA and vCCAD, and associated construction blueprints have been proposed to leverage either CPA or CPAD secure FHE beyond the CCA1 security barrier. These two notions are the strongest CCA security notions so far achievable, respectively, by correct and approximate homomorphic schemes. However, the only known construction strategies intimately require advanced SNARK machinery, undermining their practicality. In this context, this paper aims to achieve these advanced CCA security notions in the restricted case of linearly homomorphic encryption, without resorting to SNARKs. To do so, we investigate the relationship between the Linear-Only Homomorphism (LOH) assumption, an assumption that has been used for more than a decade at the core of several proof-of-knowledge constructions, and these two recent security notions (vCCA and vCCAD). On the bright side, when working under the correctness assumption, we establish that the LOH property is sufficient to achieve vCCA security in both the private and public-key settings. In the public-key setting, we further show that a surprisingly simple and previously known Paillier-based construction also achieves this level of security, at only twice the cost of the baseline scheme. We then turn our attention to LWE-based schemes for which the Pandora box of decryption errors opens up. In the private-key setting, we are only able to achieve CPAD and vCCAD security in a fairly restrictive non-adaptive setting, in which vCCAD collapses onto a weak relaxation of CCA1. Finally, we eventually achieve adaptive vCCAD security provided that the number of ciphertexts given to the adversary is suitably restricted. While bridging the gap towards credible practicality requires further work, this is a first step towards obtaining linear homomorphic schemes achieving these recent CCA security notions by means only of relatively lightweight machinery.
Last updated:  2026-08-27
Quasipolynomial Cryptanalysis of the McEliece Cryptosystem (or: PIR Meets McEliece)
Ashrujit Ghoshal, Yuval Ishai, Aayush Jain, and Nuozhou Sun
The McEliece code-based cryptosystem, utilizing binary Goppa codes, is the earliest public-key encryption scheme that is still considered post-quantum secure. We present a simple, classical quasipolynomial-time distinguisher for Goppa–McEliece in the asymptotic “Classic McEliece” regime: for code length \(n\), extension degree \(m=\Theta(\log n)\), Goppa degree \(t=\Theta(n/\log n)\), and public-code dimension \(k=\Theta(n)\), the algorithm runs in time \(n^{{\mathcal O}(\log n)}\) and distinguishes the McEliece public key from the uniform distribution over \(\mathbb{F}_2^{k\times n}\) with advantage \(1-o(1)\). The distinguisher is not merely asymptotic: it applies to all Classic McEliece parameter sets considered in the NIST process and yields improved (though not yet practical) concrete attack estimates. Our distinguishing attack originated from a failed attempt to construct doubly efficient private information retrieval (PIR) protocols from algebraic locally decodable codes, and can be intuitively explained from the PIR perspective. We extend this provable algorithm to a heuristic \(n^{{\mathcal O}(\log n)}\)-time ciphertext-decryption attack that recovers the message from a noisy codeword and a heuristic \(n^{{\mathcal O}(\log n)}\)-time key-recovery attack that outputs an equivalent decryption key. While the decryption attack is not concretely efficient, the key-recovery attack is much closer to the distinguisher and may be relevant to NIST security levels.
Last updated:  2026-08-27
On Memory Effects in PWXL variants
Jintai Ding, Hao Guo, and Bo-Yin Yang
We estimate the intrinsic undercounting in the free-memory-access, Macaulay coefficient-on-demand RAM modeling when applied to the Parallelized Wiedemann-based XL in the Ran Wedge attack and in the Furue--Ikematsu intersection attack, under some optimistic but still feasible-sounding assumptions for the attackers. We believe that this shows the memory effects makes UOV secure enough for Ip, Is, and III. If NIST considers our original parameters insufficiently convincing, we do not take Furue's suggested replacements; we offer instead the following perturbations, which hold $m$ --- and hence the compressed public key --- fixed and spend only on the vinegar count: uov-Ip\# (256,116,44), uov-III\# (256,186,72) and uov-V\# (256,250,96).
Last updated:  2026-08-27
ALFOMs and the Moirai: Quantifying the Performance/Security Tradeoff for ZK-friendly Hash Functions
Aurélien Boeuf and Léo Perrin
Zero-Knowledge (ZK) protocols rely internally on hash functions for their security arguments. However, the hash functions that are the most efficient in this context differ substantially from e.g. SHA-3: their round function $R$ must enable an efficient arithmetization of its verification. In practice, it means that verifying if $y = R(x)$ involves as little finite field multiplications as possible. In turn, this design requirement implies a greater vulnerability to algebraic attacks. In fact, improvement of those have proved devastating, and imply the need to completely rethink the methods used to ensure security against them. In this paper, we show that it is possible to build a simple yet efficient security argument based on a precise estimate of the so-called “ideal degree” of a system of equations. Furthermore, we show that the increase of this quantity across rounds is tightly connected to the cost of the hash function in two different arithmetizations, namely AIR and R1CS. We precisely quantify this relation by introducing ALgebraic Figures Of Merit (ALFOMs) that capture how efficient a specific primitive (and in fact its round function) are at increasing the security per unit of cost. This new insight allows us to better understand sometimes puzzling performance differences between state-of-the-art hash functions in the R1CS and AIR cases, and to provide a fair and simple comparison of their round functions in this context. Furthermore, we present a new group of round functions we called the Moirai which allow us to explore what a round function providing optimal performance/security tradeoff could look like.
Last updated:  2026-08-27
Blood MERIDIAN: a blockcipher that is not a blockcipher
JP Aumasson
MERIDIAN is a 128-bit blockcipher proposed as a lightweight AES alternative. We show that its “Directional Substitution” layer is not injective by giving an explicit collision. This yields a full 12-round collision for every key. Consequently, no keyed instance of MERIDIAN is a permutation, so no decryption function can invert encryption on all plaintexts, and its blockcipher and PRP security claims fail. We additionally identify a one-round differential that exceeds the claimed bound by a factor 13.37.
Last updated:  2026-08-27
Secure Auctions in the Presence of Rational Adversaries
Chaya Ganesh, Bhavana Kanukurthi, and Girisha Shankar
Sealed bid auctions are used to allocate a resource among a set of interested parties. Traditionally, auctions need the presence of a trusted auctioneer to whom the bidders provide their private bid values. Existence of such a trusted party is not an assumption easily realized in practice. Generic secure computation protocols can be used to remove a trusted party. However, generic techniques result in inefficient protocols, and typically do not provide fairness - that is, a corrupt party can learn the output and abort the protocol thereby preventing other parties from learning the output. At CRYPTO 2009, Miltersen, Nielsen and Triandopoulos [MNT09], introduced the problem of building auctions that are secure against rational bidders. Such parties are modeled as self-interested agents who care more about maximizing their utility than about learning information about bids of other agents. To realize this, they put forth a novel notion of information utility and introduce a game-theoretic framework that helps analyse protocols while taking into account both information utility as well as monetary utility. Unfortunately, their construction makes use a of generic MPC protocol and, consequently, the authors do not analyze the concrete efficiency of their protocol. In this work, we construct the first concretely efficient and provably secure protocol for First Price Auctions in the rational setting. Our protocol guarantees privacy and fairness. Inspired by [MNT09], we put forth a solution concept that we call Privacy Enhanced Computational Weakly Dominant Strategy Equilibrium that captures parties' privacy and monetary concerns in the game theoretic context, and show that our protocol realizes this. We believe this notion to be of independent interest. Our protocol is crafted specifically for the use case of auctions, is simple, using off-the-shelf cryptographic components. Executing our auction protocol on commodity hardware with 10 bidders, with bids of length 10, our protocol runs to completion in 0.141s and has total communication of 30KB.
Last updated:  2026-08-27
ATLAS: Automated Approximation of Transformers for Efficient Homomorphic Inference in One Hour
Jianhang Xie, Sicheng Tan, Vishnu Naresh Boddeti, and Zhichao Lu
Fully homomorphic encryption (FHE) lets a server run inference on encrypted data with strong privacy guarantees, but running a Transformer under FHE is expensive. Its non-linear operations, such as softmax, normalization, and activation, must be replaced with polynomial approximations that the CKKS scheme supports, and the depth of these approximations dominates inference cost. Existing FHE Transformers use hand-tuned approximation settings, such as iteration count and polynomial degree, applied uniformly across layers, models, and tasks. Hand-tuning is slow and error-prone. Even a single uniform setting has about $10^7$ choices, and manual search cannot exploit layer-wise variation. AutoFHE, the only automated method with multi-objective search, targets ReLU-only CNNs and needs full fine-tuning per candidate, which is too costly for Transformers. Per-layer settings also push the search space to about $10^{85}$ for BERT and ViT and $10^{228}$ for LLaMA3, beyond both manual and fine-tuning-based search. We present ATLAS, a training-free framework that automates this search by treating each layer's approximation setting as a multi-objective optimization over latency and accuracy. The problem is hard: the decision space is large (96 or 256 variables), each configuration takes 70 to 1,000 seconds to evaluate even in cleartext, and 85 to 90 percent of configurations are invalid. ATLAS handles this with a two-stage optimization strategy and a surrogate model, completing the search in about one hour. Compared to an iterative softmax baseline, ATLAS cuts multiplicative depth and end-to-end latency by about 35 percent with little accuracy loss, and works across encoder-only, decoder-only, and vision Transformers, complementing parallel work on packing and matrix multiplication.
Last updated:  2026-08-27
Code Generation of Faster Formally Verified NTT with Plantard Reduction
Donnie Y. Xu, Rajeev Gore, Amin Sakzad, Ron Steinfeld, and Raymond K. Zhao
We present a formally verified implementation of the ML-KEM Number-Theoretic Transform (NTT) based on Plantard arithmetic, produced via a code generator that targets ML-KEM, ML-DSA, and FN-DSA from a single parameter triple. The generator embeds a static bound analyzer that places modular reductions at code-generation time without runtime branching, eliminating per-scheme manual tuning while preserving constant-time guarantees. Each generation produces structurally identical implementations in two backends: portable C, and Jasmin for formal verification. To establish end-to-end correctness, we contribute a parametric formalization of Plantard arithmetic in \textsc{EasyCrypt} and a layer-by-layer program-equivalence proof connecting the extracted Jasmin ML-KEM NTT to the abstract specification of formosa-mlkem; the existing algebraic chain is reused unchanged to extend correctness down to the mathematical NTT definition. Benchmarks across three schemes show that the generated code outperforms reference C by $1.5\times$--$1.8\times$ on the forward NTT and $1.7\times$--$2.5\times$ on the inverse, and outperforms the formally verified formosa-mlkem Jasmin baseline by $1.26\times$ and $2.19\times$ on ML-KEM. We believe our techniques generalize to other lattice-arithmetic primitives requiring both performance and formal verification.
Last updated:  2026-08-27
From Lattices to Tensor Cores: Accelerating Private Information Retrieval
Sidaarth Sabhnani and David J. Wu
This work introduces SandwichPIR, the first single-server PIR protocol that implements the overwhelming majority of the server computation as dense 8-bit integer matrix multiplications on GPU tensor cores and requires no offline communication. For a 4 GB database with 32 KB records, SandwichPIR answers a query in 8.2 ms and communicates 688 KB of data. This amounts to a server throughput of 488 GB/s and is $88\times$ faster than the best CPU-based protocol that does not rely on offline communication. The performance of SandwichPIR shines when processing a batch of queries from many independent clients. This moves the server from a memory-bandwidth-bound regime into a compute-bound regime. A single Nvidia L40S GPU can process a batch of 128 queries to the same 4 GB database in 21.0 ms. This gives an amortized per-query processing time of 0.16 ms and an effective throughput of roughly 24 TB/s. This is $50\times$ higher than the single-query throughput. With a fleet of 8 GPUs, SandwichPIR can process a batch of 128 queries to a 256 GB database in 119 ms and achieves an effective throughput of nearly 270 TB/s. Finally, we show how to use SandwichPIR to enable private access to (text-only) English Wikipedia (8 GB compressed). Retrieving an article (up to 128 KB) requires 768 KB of client-server communication, with an estimated total end-to-end latency under 200 ms over a broadband network connection. By processing 64 queries at a time, a single GPU can handle over 2,500 queries per second (with a computational cost of \$0.20 per million queries based on current AWS pricing).
Last updated:  2026-08-27
Novel SMT Encoding for Quantum Circuit Optimization
Youbo Guo, Fengrong Zhang, Lei Liao, Yongzhuang Wei, Baocang Wang, and Xiaogang Zhou
In recent years, quantum circuit optimization has become an important research topic. Motivated by the fact that quantum gates act on fixed physical wires and modify only their target wires, we propose two SMT encodings: an exact-G encoding and an at-most-G encoding with null gates. Our method speeds up most tested 4-bit S-box instances, achieving up to approximately 130x speedup on the ELEPHANT S-box. Importantly, our method enables automated synthesis of practical 5-bit S-box quantum circuits, such as KECCAK and ASCON. For the KECCAK S-box, in the no-ancilla setting, our model obtains concrete implementations with 17 NCT gates and full depth 51, and with 16 NCT gates and full depth 52, improving the EUROCRYPT 2025 result of Huang et al. It further finds a 13-gate implementation with full depth 55, which is gate-count optimal in the no-ancilla setting under the NCT gate set. In addition, when one ancilla qubit is allowed, our model obtains KECCAK implementations with Toffoli count 5, matching the theoretical lower bound. Finally, our model can also be applied to small-scale linear-layer implementation; for example, it finds a 24-CNOT implementation with depth 3 for the 16x16 linear matrix of MIDORI.
Last updated:  2026-08-27
LetoPIR: Fast Keyword Private Information Retrieval with Logarithmic Communication
Baoyu Li, Kang Yang, Qi Liu, Binwu Xiang, Xiaogang Zhou, Xiang Xie, and Yu Yu
Keyword private information retrieval (PIR) allows a client to retrieve a record associated with a keyword from a database without revealing any information about the keyword. In the standard single-server setting, existing hintless keyword PIR protocols incur substantial communication and computation costs. In this paper, we propose an efficient approach to generate $k$-hot vectors (i.e., vectors with exactly $k$ non‑zero components) in homomorphic-encryption form, and present a bucket-merging technique to decrease the maximum size of buckets. Based on these techniques, we construct LetoPIR, a hintless keyword PIR protocol that outperforms previous PIR protocols in the same setting. Compared to the state-of-the-art hintless keyword PIR scheme, SparsePIR (USENIX'23), LetoPIR achieves a $12.4\times \sim 17.0\times$ improvement in communication cost for databases ranging from $256$ MB to $4$ GB with records of $256$ bytes, and more than $3.0\times$ improvement in computation cost for the $256$ MB database. Compared to the state-of-the-art keyword PIR scheme with client hint, KPIR (USENIX'25), LetoPIR reduces the communication cost by $51.4\times \sim184.8\times$, while achieving a similar (even better) computation cost.
Last updated:  2026-08-27
Atom: Single-Server Private Information Retrieval with Low Communication and Fast Computation
Baoyu Li, Binwu Xiang, Kang Yang, Yu Yu, and Xiaogang Zhou
Private information retrieval (PIR) enables a client to retrieve a record without revealing the index.Among existing PIR protocols with database-independent preprocessing, for each query, the protocols with low communication often take from several seconds to tens of seconds, while the faster protocols require hundreds of kilobytes for communication. In this paper, we propose three techniques for different-type ciphertext conversions: (1) the first one is to generate a two-orbit SIMD selector from encrypted bits; (2) the second one is to convert a packed $\mathsf{RLWE}$ ciphertext into an aligned monomial $\mathsf{RGSW}$ ciphertext; (3) the third one is to produce an arbitrary monomial $\mathsf{RGSW}$ ciphertext from encrypted bits. Building on these techniques, we design a new PIR protocol (called Atom), achieving the best of both worlds (i.e., having not only low communication but also fast computation). We implemented Atom and evaluated its performance for $256$ B records and databases from $256$ MB to $8$ GB. Specifically, Atom takes $3.0 \sim 3.8$ KB of online communication (i.e., the total communication, excluding the setup phase that can be run only once and reused for multiple queries), and takes $0.4 \sim 5.0$ seconds per query. Compared to the state-of-the-art KsPIR (CCS'24), Atom reduces the online communication cost by a factor of $40.5\times \sim 51.3\times$, while its running time is comparable to KsPIR ($0.2 \sim 5.2$ seconds per query).
Last updated:  2026-08-26
An Algebraic-Geometry Lower Bound against the ePrint:2026/1747 McEliece Key-Recovery Attack
Daniel Apon
A few weeks ago, Ghoshal, Ishai, Jain, and Sun (ePrint:2026/1630) introduced a "hold-out distinguisher" for the Goppa–McEliece public key. This past week, Vedenev (eprint:2026/1747) proposed to turn its polynomial relations into key recovery by reconstructing the hidden generalized Reed–Solomon representation from nested Hasse-derivative spaces at held positions. Vedenev’s proposed held-position count explicitly assumes that the resulting linear equations are independent across positions. Yet, experiments on proper binary Goppa instances contradict that assumption, demonstrating a familiar "waterfall" phenomenon where - just before the required independent equation count for a successful attack - additional held positions sharply drop in value, providing just a single, independent equation rather than the $\approx {k \choose 2}$ such equations from the early positions. This note identifies an algebraic-geometric reason for this inherent dependence. For a binary Goppa polynomial of degree $t$, an explicit linear map constructs a $(2t+3)$-dimensional family modulo the true solution. At each held support point, the entire derivative-flag block restricts on this family to at most one ordinary evaluation condition. Consequently, under a concrete nondegeneracy condition stated in terms of the hidden vector polynomial $\bf F$ and its formal derivative ${\bf F}$$'$: $c_{need} \gt 2t + 3,$ where $c_{need}$ is the number of sampled held positions required at the critical step in Vedenev’s algorithm. (The proposed key-recovery algorithm’s cost depends on $c_{need}$ in the exponent.) For ISO/NIST Category 5 parameter set ${\sf mceliece8192128}$, this gives $c_{\rm need} \gt 259,$ which implies Vedenev’s key-recovery algorithm costs in excess of $2^{1500}$ bit operations there.
Last updated:  2026-08-26
On the BUFF Security of ECDSA with Key Recovery
Keita Emura
In the usual syntax of digital signatures, the verification algorithm takes a verification key in addition to a signature and a message, whereas in ECDSA with key recovery, which is used in Ethereum, no verification key is input to the verification algorithm. Instead, a verification key is recovered from a signature and a message. In this paper, we explore BUFF security of ECDSA with key recovery (KR-ECDSA), where BUFF stands for Beyond UnForgeability Features (Cremers et al., IEEE S&P 2021). As a result, we show that KR-ECDSA provides BUFF security, except weak non-resignability (wNR). It is particularly noteworthy that the KR-ECDSA verification algorithm takes an Ethereum address addr as input. This address is defined as the rightmost 160 bits of the Keccak-256 hash of the corresponding ECDSA verification key. Crucially, the algorithm verifies that the hash of the recovered verification key matches addr. Our security analysis shows that the procedure of checking whether the hash value of the recovered verification key is equal to the address is mandatory to provide BUFF security. We also discuss whether wNR is mandatory in Ethereum or not. To clarify which part is mandatory to provide BUFF security in KR-ECDSA, we show that the original ECDSA does not provide any BUFF security. As a by-product of the analysis, we show that one of our BUFF attacks also works against Aumayr et al.'s ECDSA-based adaptor signature scheme (ASIACRYPT 2021) and Qin et al.'s blind adaptor signature scheme (IEEE S&P 2023), which is based on Aumayr et al.'s scheme. We emphasize that the attack is positioned outside of their security models.
Last updated:  2026-08-26
Secure Cloud Storage: Modularization, Network Adversaries and Adaptive Corruptions
Jonas Janneck and Doreen Riepel
End-to-end cloud storage solutions are deployed at large scale, yet recent works have demonstrated severe attacks against their confidentiality and integrity. Motivated by this, a first formal treatment of secure cloud storage was given at CRYPTO 2024 by Backendal, Davis, Günther, Haller and Paterson (BDGHP). They define syntax and security notions, capturing client-to-client security of cloud storage schemes with respect to a password distribution. They also give an efficient construction using the Two-Hash Diffie-Hellman (2HDH) OPRF and standard cryptographic building blocks, which they prove secure under selective corruptions in the random oracle model. However, several aspects of practical security guarantees remain open. We extend and refine the work of BDGHP along multiple dimensions, advancing the analysis of secure cloud storage schemes. First, we prove that their construction can be proven secure against adaptive corruptions (with a slight modification), circumventing technical challenges posed by file sharing. Second, we modularize the scheme further by introducing an abstraction for the authentication procedure. This allows us to identify the concrete role of 2HDH and alternative instantiations. Third, we introduce a weaker model that captures adversaries who can arbitrarily control the network, except during registration. This allows us to prove concrete guarantees about online password guessing attacks, whereas the stronger model inherently allows for offline guessing. Finally, we formalize and prove explicit authentication, relying on the security of our new authentication abstraction and the MAC scheme, where the latter was previously not used in the security analysis.
Last updated:  2026-08-26
Icefish: Practical zk-SNARKs for Verifiable Genomics
Alexander Frolov, Maurice Shih, Rob Patro, and Ian Miers
Individual genomic data is a uniquely sensitive type of user data. While many papers have considered using Multi-Party Computation (MPC) or Fully Homomorphic Encryption (FHE) to allow collaborators to study combined genomic datasets they cannot share, few have considered verifying the results of genomic computations, either in research studies or in the emerging area of personalized genetic therapies. In this paper, we initiate the first systematic study of zero-knowledge proofs for verifiable genomics, providing both building blocks for verifying common operations in computational genomics, such as sequence alignment, and exploring two end-to-end applications: Verifiable Genome-Wide Association Studies: A Genome-Wide Association Study (GWAS) study operates over a repository of genomic data, identifying statistical correlations between genetic variations and observed traits or medical conditions. Our system enables third parties to verify that research was honestly computed over an authenticated, untampered database, ensuring both the integrity of the underlying data set and the correctness of the resulting science. We achieve practical performance (<40 minutes proving time) for studies of sizes equal to those in the existing genomics literature. Verifiable CRISPR eligibility: We propose using zk-SNARKs in the context of gene engineering (e.g. CRISPR). To our knowledge, this is a new use case for zk-SNARKs. We implement and optimize models for detecting ``on-target'' and ``off-target'' sites for a CRISPR probe in zk-SNARKs, so users can, for example, demonstrate eligibility for a therapy or trial without having to reveal their own DNA sequence. In support of these applications, we develop new building blocks, like zero-knowledge proofs of sequence alignment that are 30x faster than the prior state of the art, and storage-efficient indexes for Merkle trees for large scale genomic data that asymptotically reduce storage costs.
Last updated:  2026-08-26
SoK: Secure Computation over Secret Shares
Tamir Tassa and Arthur Zamarin
Secure multiparty computation (MPC) enables mutually distrustful parties to jointly compute functions over private data without revealing their inputs. A central paradigm in MPC is the secret-sharing-based model, where secret sharing underpins the efficient realization of arithmetic, comparison, numerical, and Boolean operations on shares of private inputs. In this paper, we systematize protocols for these operations, with particular attention to two foundational contributions \cite{ChidaGHIKLN18,NO07} that devised secure multiplication and comparison. Our survey provides a unified, self-contained exposition that highlights the composability, performance trade-offs, and implementation choices of these protocols. We further demonstrate how they support practical privacy-preserving systems, including recommender systems, distributed optimization platforms, and e-voting infrastructures. By clarifying the protocol landscape and connecting it to deployed and emerging applications, we identify concrete avenues for improving efficiency, scalability, and integration into real-world MPC frameworks. Our goal is to bridge theory and practice, equipping both researchers and practitioners with a deeper understanding of secret-sharing-based MPC as a foundation for privacy technologies.
Last updated:  2026-08-26
A (6, 4) Vectorial Boolean Function With Nonlinearity 26 and the Maximum Nonlinearity for Six-Bit Permutations
Yufei Yuan, Lei Zhang, and Wenling Wu
When the output dimension of a vectorial Boolean function exceeds half its input dimension, not all nonzero components can be bent. The best attainable componentwise nonlinearity in this range, however, is generally unknown. We ask whether the conjectured bound for even-dimensional square mappings extends to this high-output regime, and show that it does not. Specifically, we construct a six-input, four-output function with nonlinearity 26, thereby improving the previous lower bound of 24. Its seven bent components form the nonzero part of a three-dimensional component subspace, whereas the remaining eight components all have maximum absolute Walsh coefficient 12. Accordingly, the associated binary linear code has length 64, dimension 11, and minimum distance 26. We then address the distinct problem of six-bit permutations and determine its exact maximum. A computer-assisted evaluation of the complete classification of Boolean functions in six variables bounds the autocorrelation energy of every balanced component whose Walsh coefficients have magnitude at most 12. Combined with a vectorial fourth-moment identity, this bound forces every six-bit permutation to have a component with maximum absolute Walsh coefficient at least 16, and hence nonlinearity at most 24. Inversion over the field with 64 elements attains this value. Finally, the same argument gives necessary coding conditions for any non-bijective six-input, six-output function whose nonlinearity exceeds 24.
Last updated:  2026-08-26
Practical Differential Fault Attacks on the GPRS Standard Ciphers
Zhengting Li, Lin Ding, An Wang, Haotong Xu, Zheng Liu, Zheng Wu, Xinhai Wang, and Jiang Wan
GEA-1 and GEA-2 are two standard stream ciphers used in GPRS (General Packet Radio Service) to protect against eavesdropping GPRS between the base station and the phone. Now, a range of current phones still support them. In this paper, a differential fault attack on the GEA-like stream ciphers under the random fault model is proposed for the first time. In this attack, an efficient dedicated algorithm for identifying the exact fault location is proposed. By using this dedicated algorithm, the attacker can succeed in determining the exact fault location. As applications, practical differential fault attacks on the GPRS standard ciphers (i.e., GEA-1 and GEA-2) are presented, which recover the 64-bit secret keys of GEA-1 and GEA-2 with time complexities of ${2^{{\rm{33}}{\rm{.807}}}}$ and ${2^{{\rm{33}}{\rm{.858}}}}$, respectively. We validate the cryptanalytic results by simulating the whole attacks on the platform ChipWhisperer Lite. The experimental results show that both GEA-1 and GEA-2 can be broken within sixteen minutes on a common laptop. Finally, the possible countermeasures are presented to protect the processed data of massive GPRS devices.
Last updated:  2026-08-26
Worst-Case Lattice Sampler with Truncated Gadgets and Applications
Corentin Jeudy and Olivier Sanders
Gadget-based samplers have proven to be a key component of several cryptographic primitives, in particular in the area of privacy-preserving mechanisms. Most constructions today follow the approach introduced by Micciancio and Peikert (MP) yielding preimages whose dimension linearly grows with that of the gadget. To improve performance, some papers have proposed to truncate the gadget but at the cost of an important feature of the MP sampler, namely the ability to invert arbitrary syndromes. Technically speaking, they replace the worst-case MP sampler by an average-case sampler that can only be used in specific contexts. Far from being a mere theoretical restriction, it prevents the main applications of gadget-based samplers from using truncated variants and thus from benefiting from the associated performance gains. In this paper, we solve this problem by describing a worst-case sampler that still works with truncated gadgets. Its main strength is that it retains the main characteristics of the MP sampler while providing flexibility in the choice of the truncation parameter. As a consequence, it can be used as a plug-in replacement for all applications relying on the MP sampler so far, leading to performance improvements up to 30% as illustrated by several examples in this paper. Our sampler is supported by a thorough security analysis that addresses the hurdles met by previous works and its practicality is demonstrated by a concrete implementation.
Last updated:  2026-08-26
Dealing Haystack: Towards Trustless Haystack in the Optimistic Setting
Isabel Muñoz, Isaac Agudo, Marco López, and Daniel Morales
Hash-based constructions occupy a distinctive position among post-quantum signatures: their security reduces to well-tested properties of hash functions rather than to newer assumptions such as lattices or isogenies. This work focuses on stateful schemes instead of stateless, because the former are considerably more efficient. However, they have the problem of state handling, since reusing a one-time key twice enables signature forgeries. Despite threshold signatures mitigate this problem by spreading trust among a set of disjoint parties, building them from hash-based schemes is difficult, since these lack the homomorphic structure needed to recombine partial signatures, and generic multiparty computation can be expensive for hash-based constructions. Kelsey, Lang and Lucks recently proposed Haystack, the first threshold scheme for hash-based signatures producing standard LMS or XMSS signatures, at the cost of a fully trusted setup and a large common reference value. We analyze Haystack along two dimensions: performance and security. First, as Haystack lacks an implementation and realistic benchmarking, we implement the protocol in Java and produce a network-aware evaluation of its viability in real deployments, concluding that it performs comparably to other post-quantum threshold schemes. Second, we relax the trust placed in the dealer. For that, we introduce a variant of the setup built on an optimistic, lightweight MPC-based partial-DKG. It does not remove the dealer's ability to forge, but it prevents it from impersonating trustees within the signing protocol, while preserving the standard signature format. Also, an optional succinct-argument layer provides public auditability. We further consider a full-DKG setting with no dealer and where the trustees run the entire setup under MPC. Both variants are implemented in MP-SPDZ and their costs have been analyzed.
Last updated:  2026-08-26
Adaptive Multi-Algorithm Key Exchange for Quantum-Resilient Secure Communication: Dynamic Switching among QKD, Post-Quantum, and Classical Key Establishment with Entropy Fusion
Ogbodo Tochukwu Hillary, Bilkisu Larai Muhammad-Bello, and Saleh El-Yakub Abdullahi
With the arrival of scalable quantum computers, classical key exchange protocols like RSA, elliptic-curve and finite-field Diffie-Hellman are vulnerable to harvest-now-decrypt-later attacks. Quantum key distribution offers information-theoretic security but is sensitive to channel noise, loss, and distance, while post-quantum cryptography provides quantum resistance on conventional hardware at the cost of larger keys and a dependence on hardware computational strength. Existing hybrid defenses generally rely on static configurations that require manual intervention when channel conditions degrade, and no prior software-defined system performs real-time three-way switching among these approaches while preserving uninterrupted key availability. This paper presents an adaptive multi-algorithm key generation and exchange framework that dynamically selects among quantum key distribution (BB84), post-quantum cryptography (Kyber512, standardized as ML-KEM-512), and classical Diffie-Hellman according to real-time monitoring of the quantum bit error rate and network latency, fusing key material from all active sources through an HMAC-based key derivation stage. The framework was implemented and evaluated in a controlled simulation environment built on Qiskit, liboqs, and the Python cryptography library. Across all five operating modes it attained a 100% key-generation success rate, with the quantum-resistant modes sustaining a secret-key throughput of approximately 3 kbps at a 256-bit key size and mode transitions completing without loss of key availability. A Kruskal-Wallis test confirmed that the timing differences among modes were statistically significant (H = 133.32, p < 0.001), and the security model was placed on a formal footing using the robust key-combiner framework. The results indicate that adaptive multi-algorithm key exchange can substantially improve the quantum resilience of secure communication systems in terms of security, availability, and performance.
Last updated:  2026-08-26
Practical Homomorphic LSTM via Programmable Bootstrapping
Thomas Crasson, Nathan Cassereau, and Florian Méhats
While deep learning is ubiquitous, centralized pro- cessing exposes sensitive sequential data—such as natural lan- guage—to untrusted servers, forcing an unacceptable privacy- utility trade-off. Fully Homomorphic Encryption (FHE) re- solves this by computing directly on encrypted data. However, standard neural networks ported to FHE suffer from severe latency bottlenecks, particularly because continuous non-linear activations dominate the computational budget. To overcome this, we introduce the Blind Spiking LSTM (BSLSTM), a TFHE-optimized recurrent architecture for privacy-preserving sequential inference. By co-designing the network with the cryptographic framework, we replace expen- sive continuous non-linearities with an efficient multi-threshold programmable bootstrapping paradigm. Evaluated on stan- dard NLP tasks, BSLSTM achieves an inference latency of 5.2 seconds for a 128-token sequence, significantly outperform- ing traditional homomorphic approaches while maintaining competitive accuracy. Operating at an amortized cost of 211 microseconds per bootstrapping operation, our work demon- strates the practical viability of low-latency, fully homomorphic inference for real-world applications.
Last updated:  2026-08-26
Hash your Keys before Signing: BUFF Security of the Additional NIST PQC Signatures
Thomas Aulbach, Samed Düzlü, Michael Meyer, Patrick Struck, and Maximiliane Weishäupl
In this work, we analyze the so-called Beyond UnForgeability Features (BUFF) security of the submissions to the current standardization process of additional signatures by NIST. The BUFF notions formalize security against maliciously generated keys and have various real-world use cases, where security can be guaranteed despite misuse potential on a protocol level. Consequently, NIST declared the security against the BUFF notions as desirable features. Despite NIST's interest, only $6$ out of $40$ schemes consider BUFF security at all, but none give a detailed analysis. We close this gap by analyzing the schemes based on codes, isogenies, lattices, and multivariate equations. The results vary from schemes that achieve neither notion (e.g., Wave) to schemes that achieve all notions (e.g., PROV). In particular, we dispute certain claims by SQUIRRELS and VOX regarding their BUFF security. Resulting from our analysis, we observe that two schemes (CROSS and PROV) achieve BUFF security without having the hash of public key and message as part of the signature, as BUFF transformed schemes would have. PROV essentially uses the lighter PS-3 transform by Pornin and Stern (ACNS'05). We further point out whether this transform suffices for the other schemes to achieve the BUFF notions, with both positive and negative results.
Last updated:  2026-08-26
VERIF: An Efficient Zero-Knowledge Proof System for Verifying IVF-Flat Retrieval in RAG Services
Zhiwen Zhang, Yuao Zhou, Ge Chang, Cong Li, Yuejian Fang, and Qingni Shen
Retrieval-augmented generation (RAG) services outsource vector search over proprietary corpora, yet clients cannot verify that returned context conforms to the promised index, parameters, and snapshot. We present VERIF, the first dedicated zero-knowledge polynomial interactive oracle proof (PIOP) for complete, service-consistent IVF-Flat retrieval. VERIF proves top-$m$ centroid selection, authenticated routing, exact full-vector scoring of every routed candidate, final top-$k$ selection, and context binding. Its commitment-eliding reduction keeps query-dependent scores virtual and reduces selection claims directly to inner products over authenticated data. A unified, permutation-free top-$t$ relation with limb-decomposed range arguments handles both selection stages without sorting or score commitments. Against a matched, optimized implementation of the same retrieval relation using a general-purpose circuit-based zkSNARK (Plonky2), our prototype achieves up to an $86.5\times$ prover speedup and reduces peak memory by up to 99.1%. VERIF proves retrieval over authenticated SIFT and 768-dimensional Cohere indexes containing 32 million and 8 million vectors in 5.90 and 11.57 seconds, respectively; verification takes 0.62--1.48 seconds. These results demonstrate practical verifiable IVF-Flat retrieval for RAG-as-a-Service.
Last updated:  2026-08-26
Hardness of Euclidean Closest Vector within $n^{1/2-\epsilon}$ and Binary Nearest Codeword within $n^{1-\epsilon}$
Zhao Song
We prove two deterministic inapproximability results. First, for every fixed $0<\epsilon<1/2$, Euclidean $\mathrm{GapCVP}^{(2)}$ is NP-hard with gap factor $n^{1/2-\epsilon}$ under deterministic polynomial-time many-one reductions, where $n$ denotes the lattice rank. Consequently, the Euclidean closest vector problem is NP-hard to approximate within the same factor. This improves the previous $n^{1/400}$ hardness factor in Chapter 7 of the OpenAI report [Ope26]. Aharonov and Regev gave short certificates for both the YES and the NO case of $\operatorname{GapCVP}^{(2)}$ at gap factor $C\sqrt n$, placing that problem in $\mathrm{NP}\cap\mathrm{coNP}$ for an absolute constant $C>0$ [AR05]. An NP-hard problem lying in $\mathrm{coNP}$ would give $\mathrm{NP}=\mathrm{coNP}$, so the factor $n^{1/2-\epsilon}$ above cannot be improved to $C\sqrt n$ unless the two classes coincide. Second, for every fixed $0<\epsilon<1$, the gap versions of binary nearest codeword and binary syndrome decoding are NP-hard with factor $n^{1-\epsilon}$ under deterministic polynomial-time many-one reductions, where $n$ denotes the binary block length. Consequently, both optimization problems are NP-hard to approximate within the same factor. This improves the previous $n^{1/200}$ hardness factor in Chapter 7 of the OpenAI report [Ope26].
Last updated:  2026-08-26
Security Analysis on a Secure Medical Data Sharing System in Digital Twin Environments
Mizuki Hayashi and Keita Emura
Gao et al. (IEEE Internet of Things Journal, 2025) proposed a medical data sharing system for digital twin environments using identity-based encryption (IBE), public-key encryption with keyword search (PEKS), and blockchain technologies. In this short note, we show that Gao et al.'s system allows unauthorized users to access other patients' medical data. We further show that the search server can obtain information about the queried keywords from the trapdoors (search queries). In addition, we analyze the procedure used to retrieve, from the blockchain, the IPFS (InterPlanetary File System) addresses storing encrypted medical data and encrypted keywords. Since these addresses are derived from labels that can be computed solely from public information and keywords, and because the keywords themselves are provided to the search server, we demonstrate that searchable encryption is unnecessary in the first place. Based on our security analysis, we argue that the proposed system requires a fundamental redesign.
Last updated:  2026-08-26
ARES: Online-Friendly Robust Threshold ECDSA with Amortized Costs
Guofeng Tang, Tian Qiu, Bowen Jiang, Haiyang Xue, Meng Hao, Guomin Yang, and Robert H. Deng
Threshold ECDSA has been an active research topic in recent years, driven by its wide-ranging applications, particularly in blockchain domains. In these real-world applications, robustness is a critical requirement. It ensures that a signature is successfully generated as long as $t+1$ honest parties are present, regardless of malicious behavior from others. Existing robust constructions generally fall into two categories: those based on threshold linearly homomorphic encryption (TLHE) and those leveraging the Multiplicative-to-Additive (MtA) paradigm. The TLHE-based approach (e.g., WMC24 in NDSS'24) achieves constant sending communication per party but incurs an expensive online phase. In contrast, the MtA-based approach (e.g., TX25 in S\&P'25) is online-friendly, requiring only elliptic-curve group operations during the online phase. However, it has the drawback of requiring $O(n)$ sending communication per party when $n$ parties are involved. In this work, we propose ARES, a robust threshold ECDSA scheme designed to reduce both communication and computational overhead within the online-friendly MtA framework. To improve the communication efficiency of TX25, we propose verifiable non-interactive multiplication (VNIM), a new primitive which endows standard non-interactive multiplication with public verifiability. Simultaneously, we leverage super-invertible matrices and packed secret sharing to amortize the overall costs. Specifically, when setting the packing parameter of packed secret sharing to $\ell = 1$ (i.e., without secret packing), ARES exhibits linear communication complexity while already achieving an approximately $50\%$ improvement over TX25. When configuring $\ell = t/3$ with $t \ge 12$, ARES achieves lower communication overhead than WMC24, requiring a constant $\approx 4.5\text{ KB}$ per party. Furthermore, setting $\ell = t/2$ reduces the amortized communication cost to roughly $3\text{ KB}$ per party. On the other hand, amortizing across $\ell$ signatures incurs a trade-off by increasing the required party size by $\ell$.
Last updated:  2026-08-25
Separating Quantum Indistinguishability Obfuscation from Falsifiable Assumptions
Mohammed Barhoush, Tomoyuki Morimae, and Ramis Movassagh
Quantum indistinguishability obfuscation (qIO) aims to make a quantum circuit unintelligible while preserving its functionality. It serves as a foundational primitive for advanced applications, such as witness encryption (WE) for QMA, non-interactive zero-knowledge arguments for QMA, and attribute-based encryption for BQP. Despite its importance, constructing qIO from standard assumptions remains a major open problem. In this work, we prove that the security of WE for QMA cannot be based on any falsifiable cryptographic assumption via a restricted class of quantum black-box reductions. Because qIO for null quantum circuits implies WE for QMA, this also separates null-qIO from falsifiable assumptions. Since almost all standard cryptographic assumptions are falsifiable, our result presents a barrier to basing qIO on standard cryptographic assumptions. The reductions we rule out are restricted: the reduction must query the adversary classically, non-adaptively, at the same security parameter, and only on honestly generated ciphertexts. Moreover, our impossibility applies only to WE with classical ciphertexts, and therefore does not rule out qIO with obfuscators whose output is a quantum state. Ruling out more general reductions, as well as more general forms of WE and qIO, remains open. Our impossibility relies on the existence of a QMA-QCIP[2] gap problem, an average-case assumption postulating a QMA language that cannot be verified with two messages of classical communication.
Last updated:  2026-08-25
Logarithmic-Depth Pseudorandom Functions from Well-Founded Code-Based Assumptions
Youlong Ding, Aayush Jain, and Ilan Komargodski
We give the first $\mathsf{NC}^1$-computable Pseudorandom Function (PRF) constructions from well-founded (non-ad-hoc) code-based assumptions. Specifically, we give two constructions based on two different classical variants of the learning parity with noise (LPN) assumption: (1) An $\mathsf{NC}^1$-computable PRF from hardness of Sparse-LPN [Alekhnovich, FOCS~'03] (with respect to a sublinear-depth expander graph family). This PRF is also key-homomorphic. (2) An $\mathsf{NC}^1$-computable PRF from hardness of Ring-LPN [Heyse et al., FSE~'12]. Both of these assumptions have been studied for many years in cryptography and average-case complexity. Ring-LPN has been used in the context of silent preprocessing for MPC and has a stable cryptanalysis. The study of counterexamples for Sparse-LPN is an active area of research. Notably, within the range of parameters that we need, none of these assumptions is known to imply collision-resistant hashing, and the first is not known to imply public-key encryption. Prior constructions of code-based PRFs (let alone key-homomorphic) are either super-logarithmic depth, or rely on newly introduced assumptions. As a bonus, we give a similar result relying on the \emph{classical} LPN assumption, albeit with quasi-polynomial hardness: -A key-homomorphic $\mathsf{NC}^1$-computable PRF from quasi-polynomial hardness of the classical LPN [Blum et al., CRYPTO~'93]. Technically, all of our results are obtained via a refinement and substantial extension of the recent ideas of [Ding, Jain, and Komargodski, STOC~'25].
Last updated:  2026-08-25
SALSAA – Sumcheck-Aided Lattice-based Succinct Arguments and Applications
Shuto Kuriyama, Russell W. F. Lai, Michał Osadnik, and Lorenzo Tucci
We present SALSAA, a more efficient and more versatile extension of the state-of-the-art lattice-based fully-succinct argument frameworks, ``RoK, paper, SISsors (RPS)'' and ``RoK and Roll (RnR)'' [Klooß, Lai, Nguyen, and Osadnik; ASIACRYPT'24, '25], integrating the sumcheck technique as a main component. This integration enables us to design an efficient norm-check protocol (controlling the norm during witness extraction) with a strictly linear-time prover while reducing proof sizes by 2-3$\times$ compared to the previous quasi-linear-time norm-check in RPS/RnR, eliminating a central performance bottleneck. The sumcheck integration also allows us to natively support a wider class of relations, including rank-1 constraint systems (R1CS), which are widely used to express real-world computations. To demonstrate the versatility and efficiency of our framework, we showcase three impactful applications achieved by different RoKs (Reductions of Knowledge) compositions: (i) a lattice-based succinct argument of knowledge with a linear-time prover, achieving a verifier time of $41$ ms, prover runtime of $10.61$ s, and proof size of $979$ KB for a witness of $2^{28}$ $\mathbb{Z}_q$ elements; (ii) a polynomial commitment scheme with matching performance; and (iii) the first lattice-based folding scheme natively operating on $\ell_2$-norm-bounded witnesses, achieving highly efficient verification in $2.28$ ms and producing a proof of just $73$ KB for a witness of $2^{28}$ $\mathbf{Z}_q$ elements, outperforming prior works for the family of linear relations. We provide a modular, concretely efficient Rust implementation of our framework, benchmarked over cyclotomic rings with AVX-512-accelerated NTT-based arithmetic, demonstrating the practical efficiency of our approach.
Last updated:  2026-08-25
Cavefish: Communication-Optimal Light Client Protocol for UTxO Ledgers
Aggelos Kiayias, Marc Roeschlin, Polina Vinogradova, Daniel Morales, and Pyrros Chaidos
Blockchain light clients (LCs) are agents with limited computational or storage resources that cannot maintain a fully validated copy of the ledger. They rely on service providers (SPs), typically full nodes, to access data required for tasks such as constructing a transaction (Tx) or interacting with off-chain applications. We introduce Cavefish, a novel protocol for UTxO-based platforms that enables LCs to interact with the ledger and submit a transaction (Tx) with minimal trust, storage, and computation, without having to synchronize to the chain. The LC specifies a Tx (e.g., by specifying a source address rather than source UTxOs, a destination and value, and a change address), and the SP constructs it, including a payment to the SP as an additional output. The LC needs to verify Tx before signing it, but the SP cannot reveal it without fear of losing its compensation. In order to resolve this two-sided trust problem, we propose a variant of the predicate blind signature (PBS) scheme of Fuchsbauer and Wolf (Eurocrypt 2024), which enables the SP to obtain valid Schnorr signatures on Tx, but only after proving to LC that Tx satisfies the specification. Cavefish achieves a trustless interaction in which the LC fulfills their transaction goal, and the SP receives fair compensation for their effort. As transactions only need to stay private until posted, our PBS variant relaxes the unlinkability requirements of blind signatures. We implement and benchmark the Non-interactive Argument of Knowledge component of Cavefish on two major UTxO-based blockchains, using two different zero-knowledge proving systems.
Last updated:  2026-08-25
Two Constructions of Rotation-Symmetric Bent Functions Outside the Completed Maiorana--McFarland Class with Any Possible Algebraic Degree
Deng Tang
Rotation-symmetric Boolean functions form an important class of cryptographically significant Boolean functions. In 2017, Su and Tang proposed in [IEEE TIT 63(7): 4658–4667, 2017] an infinite class of rotation-symmetric bent functions of every possible algebraic degree. In this paper, we present two constructions of rotation-symmetric bent functions outside the completed Maiorana--McFarland class on $n=30\cdot 7^j$ variables with $j\geq0$ and $n=70t$ variables with $t\geq1$, respectively. Each of the two constructions generates bent functions of every possible algebraic degree ranging from $3$ to $n/2$. Since the algebraic degree of an $n$-variable bent function is at most $n/2$ and every quadratic bent function belongs to the completed Maiorana--McFarland class, the interval from $3$ to $n/2$ is the full possible degree range for bent functions outside this class. To the best of our knowledge, these are the first infinite constructions of rotation-symmetric bent functions in which functions have algebraic degrees ranging from $3$ to $n/2$ while remaining entirely outside the completed Maiorana--McFarland class.
Last updated:  2026-08-25
Generalized Greedy Algorithms for Synthesizing Low-depth CNOT Circuits
Tung Chou
A CNOT circuit is a quantum circuit where the only type of gate appeared in the circuit is the CNOT gate. Given an n × n binary matrix which specifies the relationship between input and output, existing greedy algorithms generate corresponding CNOT circuits of n qubits, with the goal of minimizing depth of the circuits. This short paper presents two new greedy algorithms, which can be considered as generalized versions of existing greedy algorithms. The new algorithms are inspired by the algorithm presented in the Asiacrypt 2024 paper “Quantum circuits of AES with a low-depth linear layer and a new structure”. Although we have not run large-scale experiments, small-scale experiments suggest that the new algorithms are at least as powerful as existing greedy algorithms.
Last updated:  2026-08-25
CMALU: Compact Fault-Tolerant Modular Arithmetic Logic Unit for Post-Quantum Cryptography
YoungBeom Kim, Malik Imran, Zain Ul Abideen, Ciara Rafferty, Ayesha Khalid, Máire O’Neill, and Seog Chung Seo
The rise of quantum computing threatens widely deployed public-key cryptosystems, driving the adoption of post-quantum cryptography (PQC) algorithms that rely heavily on modular arithmetic. Existing hardware accelerators of the PQC algorithms for resource-constrained Internet-of-Things (IoT) devices remain limited and lack integrated fault detection mechanisms. In this work, we present CMALU, a Compact, fault-tolerant Modular Arithmetic Logic Unit supporting six operations on a single reconfigurable datapath, with a 2-bit input selecting Mode-0 (un-protected baseline), Mode-1 (on-the-fly parity and invariant checking with a formal single-bit detection guarantee), and Mode-2 (extending Mode-1 along with hardware-reuse recomputation for deterministic silent data corruption (SDC) elimination without datapath duplication). Under system-level fault injection into CMALU internal registers on an NTT accelerator and an Ibex RISC-V core running ML-KEM-512, Mode-1 achieves 100% single-bit and stuck-at detection at zero latency overhead, and Mode-2 achieves 0% SDC. The synthesis results after the post-place-and-route stage on a field-programmable gate array (FPGA) and application-specific integrated circuit (ASIC) implementations with the NTT accelerator targeting 65nm CMOS and the Ibex RISC-V integration targeting Nangate45 45nm confirm CMALU's suitability for resource-constrained IoT deployment.
Last updated:  2026-08-25
Revisiting the Wedge Attack on UOV problem
Jintai Ding, Peigen Li, and Siyong Tao
In this article, we first reformulate the wedge attack within a cleaner algebraic-geometric framework and then extend it to multi-homogeneous systems over fields of arbitrary characteristic. Building on these tools, we apply the resulting multi-homogeneous wedge attack to the security analysis of SNOVA.
Last updated:  2026-08-25
High-Precision Lewis Weights via Fourth-Moment Control and Local Bregman Acceleration
Zhao Song
We study the high-precision computation of $\ell_p$-Lewis weights for $p\ge4$ in the black-box exact-real full-vector leverage-score oracle model, measuring complexity by the number of adaptive oracle rounds. In this model, Gribling, Sidford, and Zhang [GSZ26] obtained an $O(p^2\log(m/\epsilon))$ bound for computing an $\epsilon$-estimate. We improve this bound to $O(p\log(mp)+\sqrt p\log(1/\epsilon))$. To obtain this result, we isolate the normalized fourth-moment operator governing the nonlinear Hessian of their log-determinant matrix potential and prove that each relative-gradient step with denominator $p$ resets the operator norm to a universal constant. This reset controls the entire update segment and yields an $O(p\log(mp))$ global entrance phase. After entering an $O(1/p)$ spectral neighborhood of the optimum, we switch to a restarted accelerated Bregman-gradient method for the vector potential.
Last updated:  2026-08-24
Ideal Secret Sharing Schemes over Small Domains
Amos Beimel, Aner Ben-Efraim, Oriol Farràs, and Adriana Moya
In any secret sharing scheme, the size of each share must be at least as large as the size of the secret. Schemes that attain this lower bound are called $k$-ideal, where $k$ is the size of the domain of the secrets and shares, or simply ideal if they are $k$-ideal for some $k$. An access structure is called $k$-ideal if it admits a $k$-ideal secret sharing scheme. The characterization of ideal access structures is a longstanding open problem at the intersection of cryptography, matroid theory, and information theory, previously solved only for $k=2$ and $k=3$. In this work, we solve this problem for $k=4$ and $k=6$. Our results exploit the connections between ideal secret sharing schemes and matroids and new techniques based on latin squares. For $k=4$, we show that an access structure is $4$-ideal if and only if it admits a $\mathbb{F}_4$-linear ideal secret sharing scheme, i.e., a scheme where the shares and the secret are elements of $\mathbb{F}_4$ and the sharing and reconstruction functions are linear. To prove this result, we show that the class of matroids determined by ideal $\mathbb{F}_4$-linear schemes coincides with those determined by $4$-ideal schemes. For $k=6$, we prove that an access structure admits a $6$-ideal scheme if and only if it admits a $k$-ideal scheme for every $k\geq 2$. This result shows that domains of size $k=6$ are the most restrictive domains for constructing ideal secret sharing schemes, and that $6$-ideal schemes can be essentially built by combining ideal $\mathbb{F}_2$-linear schemes with ideal $\mathbb{F}_3$-linear schemes via the Chinese Remainder Theorem. Beyond these characterizations, our main technical contributions are the introduction of new techniques for analyzing ideal secret sharing schemes, extending the connections between ideal threshold schemes and latin squares to the general case, and the classification of the values of $k$ for which some relevant matroids are $k$-entropic.
Last updated:  2026-08-24
Encrypted Matrix-Vector Products from Secret Dual Codes
Fabrice Benhamouda, Caicai Chen, Shai Halevi, Yuval Ishai, Hugo Krawczyk, Tamer Mour, Tal Rabin, and Alon Rosen
Motivated by applications to efficient secure computation, we consider the following problem of encrypted matrix–vector product (EMVP). Let $\mathbb F$ be a finite field. In an offline phase, a client uploads an encryption of a matrix $M \in \mathbb F^{m\times \ell}$ to a server, keeping only a short secret key. The server stores the encrypted matrix \(\hat{M}\). In the online phase, the client may repeatedly send encryptions \(\hat{ q}_i\) of query vectors \(q_i \in \mathbb F^\ell\), which enables the client and the server to locally compute compact shares of the matrix–vector product \(Mq_i\). The server learns nothing about \(M\) or \(q_i\). The shared output can either be revealed to the client or processed by another protocol. We present efficient EMVP protocols based on variants of the learning parity with noise (LPN) assumption and the related learning subspace with noise (LSN) assumption. Our EMVP protocols are field-agnostic in the sense that the parties only perform arithmetic operations over \(\mathbb F\), and are close to optimal with respect to both communication and computation. In fact, for sufficiently large \(\ell\) (typically a few hundreds), the online computation and communication costs of our LSN-based EMVP can be \emph{less than twice} the costs of computing \(Mq_i\) in the clear. Combined with suitable secure post-processing protocols on the secret-shared output, our EMVP protocols are useful for a variety of secure computation tasks, including encrypted fuzzy search and secure ML. Our technical approach builds on recent techniques for private information retrieval in the secret-key setting. The core idea is to encode the matrix \(M\) and the queries \(q_i\) using a pair of secret dual linear codes, while defeating algebraic attacks by adding noise.
Last updated:  2026-08-24
Is the Hard-Label Cryptanalytic Model Extraction Really Polynomial?
Akira Ito, Takayuki Miura, and Yosuke Todo
Deep Neural Networks (DNNs) have attracted significant attention, and their internal models are regarded as valuable intellectual assets. Extracting a model via oracle access to a DNN is conceptually similar to extracting a secret key via oracle access to a block cipher. Consequently, cryptanalytic techniques, particularly differential-like attacks, have been actively explored recently. ReLU-based DNNs are the most common architectures. While early works (e.g., Crypto 2020, Eurocrypt 2024) assume access to exact output logits, more recent works (e.g., Asiacrypt 2024, Eurocrypt 2025) focus on the hard-label setting, where the attacker observes only the final classification result (e.g., "dog" or "car"). Notably, Carlini et al. (Eurocrypt 2025) demonstrated that model extraction is feasible in polynomial time even under this restricted setting. In this paper, we show that a key assumption of their attack becomes increasingly unrealistic as the target depth grows. While prior works have noted neurons whose activation states rarely change, we analyze their concrete impact on hard-label extraction: even a single neuron that is (almost) always active can prevent the attack from proceeding unless its parameters are recovered, and ignoring it inevitably incurs a non-negligible error. A straightforward solution is to recover these parameters from a state switch, but observing such a switch becomes exponentially harder as the depth increases, implying that hard-label extraction is not always polynomial time. To address this limitation, we propose cross-layer extraction. Rather than extracting the secret parameters (e.g., weights and biases) directly, we exploit cross-layer interactions to recover them from deeper layers, reducing query complexity and addressing limitations of existing model extraction approaches. The source code is available at https://github.com/ECSIS-lab/hard-label-cross-layer-extraction.
Last updated:  2026-08-24
Almost NTRU: Revisiting Noncommutativity Against Lattice Attacks
Ali Raya, Vikas Kumar, Seong Oun Hwang, and Sugata Gangopadhyay
NTRU is one of the most extensively studied lattice-based cryptographic schemes and is widely regarded as a strong candidate for post-quantum security. The most effective attacks on NTRU are lattice-based or lattice-related, which naturally guide the choice of parameters to achieve the desired security levels. In 1997, Hoffstein and Silverman proposed a variant of NTRU based on a noncommutative algebraic structure, claiming that it would mitigate lattice attacks. However, their scheme was later shown to be vulnerable to an algebraic attack by Coppersmith. Although several subsequent attempts have been made in the literature to develop noncommutative variants of NTRU, most of these designs have either been shown to be vulnerable to algebraic attacks or have failed to directly address lattice-based attacks. In this work, we revisit the problem of constructing a noncommutative analog of NTRU that offers stronger resistance against direct lattice attacks. Firstly, we conceptualize the problem by introducing an almost unstructured variant, and then refine this idea towards a more compact instantiation by introducing a semi-structured variant. Our proposal may be viewed as a follow-up to the early noncommutative construction of Hoffstein and Silverman. We further discuss the requirements towards having a fully structured construction in this paradigm.
Last updated:  2026-08-24
Compiling Sparse Keys for Bootstrapping FHEs: Algorithms, Hardware Acceleration, and Beyond
Binwu Xiang, Songyu Wu, Baoyu Li, Xinwei Qiang, Benqiang Wei, and Yu Yu
Blind rotation is the dominant computational bottleneck in bootstrapping for bitwise FHE schemes such as TFHE. Existing constructions typically evaluate $O(n)$ sequential external products for an LWE secret of dimension $n$, incurring substantial latency and a large number of NTT/iNTT operations. In this work, we present a new framework for NTRU-based bootstrapping that reduces the sequential complexity of blind rotation for sparse binary LWE secrets. Inspired by Jain et al. (CRYPTO 2026), we use Cuckoo hashing to transform an $n$-dimensional binary LWE secret of Hamming weight $h$ into extended buckets of one-hot representation. This structured representation reduces the sequential external products from $O(n)$ to $O(h)$ in blind rotation. We also design a modulus-switching method tailored to sparse secrets. We further explore an NTT-free variant that eliminates all online NTT/iNTT operations during blind rotation while supporting gate bootstrapping with lower parallel depth, offering a potentially useful building block for hardware-friendly FHE implementations. Empirically, we achieve state-of-the-art bootstrapping performance on both CPUs and GPUs. At comparable decryption failure rates and on a single CPU thread with AVX-512, our implementation executes Boolean gate, 4-bit, and 6-bit bootstrapping in $0.83$, $1.75$, and $2.65$\,ms, outperforming TFHE-rs by $3.31\times$, $4.18\times$, and $20.47\times$, respectively. On an RTX~4090 GPU, we attain a throughput of $154{,}739$ gate bootstraps per second, corresponding to an amortized time of $6.46\,\mu\mathrm{s}$, and speedups of $86.7\times$ over our CPU result and $13.6\times$ over VeloFHE (Shen et al., TCHES 2025). As a concrete application, we develop the first NTRU-based 8-bit FHE instruction set, achieving up to over $10\times$ speedup over Trama et al. (TCHES 2025) with over $100\times$ smaller key size.
Last updated:  2026-08-24
Verbeth: Secure Messaging with Metadata Minimization over Public Blockchain Logs
Marco Esposito, Andrea Rizzini, Francesco Bruschi, and Donatella Sciuto
This work presents a private instant messaging protocol that leverages the public log layer of blockchains as the message transport layer, while the cryptographic state is kept only by client applications. Thanks to the properties of public ledgers, this approach achieves strong censorship resistance, while also revealing the economic and cryptographic limits of on-chain messaging. Notably, given the transparency of public ledgers, and since reading and writing operations are in most cases outsourced to third-party providers that may be curious, a well-known concern is direct metadata leakage. We address this both at first contact and during the conversation: for first contact, we propose two alternative discovery mechanisms, one based on long-term key encapsulation with trial decryption, the other on a private signaling service backed by trusted hardware. For the ongoing conversation, we show that topic rotation, driven by the off-chain cryptographic state, suffices to prevent topic and conversation linkability. As our main contribution, we provide an in-depth analysis of Verbeth's metadata leakage under different adversarial assumptions for both phases.
Last updated:  2026-08-24
Beyond Linear Subspace Trails: Nonlinear Subspaces for Gr\"obner Basis Attacks on Poseidon/Poseidon2 and Neptune
Enyan Li, Fukang Liu, and Gaoli Wang
Poseidon/Poseidon2 and Neptune are prominent primitives for zero-knowledge proof systems. Their arithmetic circuit cost is reduced mainly through partial S-box layers and low-degree finite field operations. Algebraic attacks are therefore a central part of their security analysis, and Gr\"obner basis methods are a main tool for studying such attacks. For such attacks, controlling the algebraic degree of the polynomial systems induced by partial rounds is a central issue. Previous work has shown that linear subspace trails can reduce the algebraic degree of partial rounds in constrained-input-constrained-output (CICO) problems. Therefore, subspace analysis has become an important tool for evaluating the algebraic security of Poseidon-like permutations. The main contribution of this paper is to extend the existing linear subspace trail framework to nonlinear subspaces. More precisely, we first introduce a parametric Macaulay matrix method. This method transforms the search for algebraic constraints that reduce degree growth into the problem of solving a parametric system. It provides a general algebraic approach for constructing longer nonlinear subspace trails that suppress degree growth over more internal partial rounds. Second, for the CICO problem with $Ec$ extra constraints, we give a concrete constraint pattern that extends a linear subspace trail into a nonlinear one. In this nonlinear construction, the first $Ec$ subspace constraints generate an ideal, and further compatible subspace constraints can be added along the chain without enlarging this ideal. As a result, the nonlinear subspace trail can cover up to $2Ec$ internal rounds, whereas the previous linear subspace trail can cover up to $Ec$ rounds. We further show that the balancing matrix required by this construction is generically nonsingular. Furthermore, we propose subspace modeling variants without variable substitution. These variants impose linear or nonlinear constraints directly on high-degree intermediate states. For the Poseidon/Poseidon2 and Neptune instances proposed by Grassi et al. in ToSC 2025, our experiments show that, under the same complexity bound and the same Gr\"obner basis cost model, the nonlinear subspace model can analyze approximately twice as many internal partial rounds as the linear subspace model considered in ToSC 2025. For several concrete instances, our method reaches or even exceeds the recommended number of internal rounds given by the designers in sponge mode or compression mode.
Last updated:  2026-08-24
DIME: Query-Efficient Framework for Membership Inference on Diffusion Models
Tue Do and Daniel Alabi
Membership inference attacks expose whether individual records were used to train a model, yet existing attacks on diffusion models are largely heuristic and can require substantial query budgets. We introduce $\textbf{DIME}$ ($\textbf{D}$enoiser $\textbf{I}$deal $\textbf{M}$embership $\textbf{E}$rror), a theoretically grounded and query-efficient framework for membership inference on diffusion models. Our starting point is an exact characterization of the optimal diffusion denoiser for a finite training set, which reveals that membership leakage is governed by the denoiser's implicit reconstruction error. This error decomposes into two complementary signals: a $\textit{bias term}$, capturing reconstruction accuracy, and a previously unexplored $\textit{local crowding term}$, capturing the geometry of nearby training examples. Both admit efficient estimators using only model queries, yielding a practical attack with as few as two queries. Across CIFAR-10/100, STL10-U, CelebA, and ImageNet, $\textbf{DIME}$ consistently outperforms prior attacks at comparable or substantially lower query cost, improving TPR at 1% FPR by up to $3\times$; remarkably, its two-query variant can outperform existing 30-query baselines. Finally, we suggest, discuss, and evaluate specific defenses to counteract such powerful membership tests.
Last updated:  2026-08-24
Lithium: Making Iterative Rejection Sampling Practical for Compact Lattice Signatures
Jipeng Zhang, Pengfei Chen, Long Chen, Cong Zhang, and Jiaheng Zhang
Post-quantum deployments need signatures that are both fast and small. ML-DSA gives a practical Fiat-Shamir lattice-signature baseline, but its signatures remain large enough to make bandwidth, certificate size, and signed-log storage first-order costs. Gaertner's iterative rejection sampling construction (CRYPTO'25) shows that this design family can be made much more compact. The open question is whether this theoretical design can be turned into a concrete, implementation-oriented signature scheme, where the parameters, algorithms, encodings, and optimized software work together without giving up the promised compactness. We present Lithium, a compact Fiat-Shamir lattice signature that makes iterative rejection sampling practical. Lithium co-designs its parameters, discrete Gaussian sampler, ApproxExp evaluation, iterative rejection sampling, and rANS encoder so that compact signatures do not come at the cost of an impractical signer. For the core components, we introduce algorithmic and vectorized optimizations and provide a portable reference implementation together with vectorized AVX2 and AVX-512 implementations. Lithium-120 targets a security level close to ML-DSA-44. Our experiments show that our fastest implementation signs faster than ML-DSA-44, at 166k versus 191k cycles, while producing signatures about half as large: 1,187 bytes versus 2,420 bytes. Compared with HAETAE-120, Lithium-120 is more compact and signs about 7.5x faster.
Last updated:  2026-08-24
HRFPRE: Fast Proxy Re-encryption for Multi-RSU Outsourcing and Hardware-assisted Revocation in the IoV.
Tingting Li, Leyou Zhang, Qing Wu, Fei Zhou, and Yuxing Wei
In the Internet of Vehicles (IoV), content-centric data sharing is essential for driving safety and user experience. However, the highly dynamic and distributed IoV network raises challenges such as unauthorized data access and inefficient information dissemination. Although existing proxy re-encryption (PRE) schemes with revocation partially mitigate these concerns, they still have key shortcomings: (i) computational costs that grow linearly with the number of attributes; (ii) heavy cloud-side overhead from re-encryption and outsourced decryption, causing delays or decryption failures; and (iii) revocation mechanisms that are inefficient or insufficiently responsive in handling malicious users. Recent studies have addressed these issues, but many schemes still struggle to ensure reliable message recovery in dynamic IoV scenarios. To overcome these limitations, we propose HRFPRE, an efficient proxy re-encryption mechanism based on multi-RSU outsourcing and hardware-assisted revocation. Our scheme provides constant-size public parameters and lightweight user-side decryption over asymmetric pairing-friendly groups, while supporting an unbounded attribute space. Re-encryption requires only four pairing operations and supports a novel "encrypt-then-offline hosting" model for vehicles. Simultaneously, Roadside Units (RSUs) provide outsourced re-encryption, key generation assistance, and decryption services to resource-constrained onboard units, effectively shifting computational load away from the cloud. By integrating a key-decoupled Trusted Execution Environment (TEE), HRFPRE enables immediate revocation and keeps plaintext recovery dependent on the user-held key even under TEE-side side-channel leakage. Under the Decisional Linear (DLIN) assumption, HRFPRE achieves adaptive security while resisting replay and collusion attacks. Theoretical analysis and experiments show that HRFPRE reduces computational and communication overhead, making it suitable for secure data exchange in dynamic IoV environments.
Last updated:  2026-08-24
Cryptanalysis of the DIZY Stream Cipher with Provable Security
Zhengting Li, Lin Ding, Xinhai Wang, and Zheng Wu
With the increasing deployment of resource-constrained devices in daily life, ultra-lightweight ciphers become a necessity to tackle the security and privacy concerns in resource-constrained devices. In 2023, G\"{u}l and Kara studied the question of how to design a secure ultra-lightweight stream cipher with a small internal state, and introduced a new small-state stream cipher called DIZY. The cipher utilizes Truncated Pseudorandom Permutations (TPP) and has a provable security in the indistinguishability model. It consists of two versions, called DIZY-128 with a 128-bit key and DIZY-80 with an 80-bit key, respectively. In this paper, effective key recovery attacks on DIZY-80 and DIZY-128 are proposed. Both attacks leverage the weakness of DIZY that the attacker can easily reach a weak state in the middle of the initialization using chosen IVs. Based on constructing Hellman tables, the key recovery attacks on DIZY-80 and DIZY-128 are further improved. The cryptanalytic results show that DIZY-80/DIZY-128 can only provide a 65/86-bit security level against the key recovery attack, while it is claimed to provide an 80/112-bit security level by the designers. Finally, an improved variant of DIZY, called DIZYa, is proposed. The analysis on DIZYa shows that the improved variant can provide better security resistance against all known attacks including our attacks on DIZY, while maintaining the commendable characteristics of DIZY. This makes DIZYa a more suitable small-state stream cipher choice for resource-constrained devices like RFID tags.
Last updated:  2026-08-24
Foundations of Single-Decryptor Encryption
Fuyuki Kitagawa and Takashi Yamakawa
Single decryptor encryption (SDE) is public key encryption (PKE) where the decryption key is an unclonable quantum state. Coladangelo, Liu, Liu, and Zhandry (CRYPTO 2021) realized the first SDE assuming subexponentially secure indistinguishability obfuscation (iO) and one-way functions (OWFs), along with the polynomial hardness of the learning with errors (LWE) assumption. Since then, SDE has played a pivotal role in recent advances in quantum cryptography. However, despite its central importance in unclonable cryptography, many fundamental questions about SDE remain unanswered. For example, a line of works has proposed various security notions for SDE, but their relationships have hardly been discussed. Moreover, while many subsequent works have adopted the construction methodology of Coladangelo et al., none have explored its improvement, leaving the possibility of a more efficient approach to SDE. In this work, we address these fundamental questions concerning SDE. Our contributions are threefold. New security notion: We introduce a strengthened indistinguishability-based security notion for SDE, which we call CPA+ anti-piracy security. We show that CPA+ security unifies the existing security notions for SDE, as detailed in the third item. New construction: We present an SDE scheme that satisfies CPA+ anti-piracy security, based solely on polynomially secure iO and OWFs. In addition to relying on weaker and more general assumptions, our SDE scheme offers a significant advantage over the scheme of Coladangelo et al., as both the construction and its security proof are much simpler. Relationships among security notions: We demonstrate that CPA+ anti-piracy security implies all existing security notions for SDE, with the sole exception of identical challenge ciphertext security proposed by Georgiou and Zhandry (EPRINT 2020). Although we do not establish a direct implication from CPA+ anti-piracy security to identical challenge ciphertext security, we provide a generic transformation from an SDE scheme satisfying the former to one achieving the latter in the quantum random oracle model. Additionally, we establish various relationships among different security notions for SDE. By combining these results with our SDE construction, we derive several new feasibility results. We further show that our CPA+ anti-piracy security enjoys additional robustness properties. In particular, it is preserved under parallel composition, yielding a way to expand the message space of SDE while maintaining security. We also show that it is robust to arbitrary correlations between the challenge bits for the second-stage adversaries. To capture this setting, we introduce correlated-challenge-bits CPA anti-piracy security, parameterized by an arbitrary joint distribution on the challenge bits, and show that CPA+ anti-piracy security implies this notion.
Last updated:  2026-08-23
The Power of Rerandomization in Obfustopia: Collision-Resistant Hash, Somewhere-Extractable BARGs, and More
Shafik Nassar
Indistinguishability obfuscation (iO) combined with one-way functions (OWFs) serves as a powerful foundation for constructing a vast array of cryptographic primitives. However, this combination faces a known black-box barrier established by Asharov and Segev (FOCS '15), which proves the impossibility of constructing collision-resistant hash (CRH) functions. The Asharov-Segev barrier naturally extends to stronger primitives that imply CRH, such as fully homomorphic encryption (FHE) and somewhere-extractable non-interactive batch arguments (seBARGs). This work investigates the power of iO and rerandomizable primitives in constructing such "CRH-hard" primitives. First, we demonstrate the first direct and simple approach to building CRH from iO and rerandomizable OWFs. The only previously known construction was due to Arnon, Ben-David and Yogev (CRYPTO '25), and needed to go through the construction of the adaptively sound SNARG of Waters and Wu (STOC 24'). Using the same approach, we additionally construct a strictly stronger primitive than CRH, which we call perfectly partitionable hash (PPH), from iO and rerandomizable commitments. Second, we demonstrate the power of rerandomizability for building advanced non-interactive proof systems. Using iO and rerandomizable commitments, we provide a construction of seBARGs with statistical extraction, a security property not achieved by most existing seBARG schemes. By additionally relying on rate-1 fully-homomorphic encryption, we construct the first rate-1 seBARG with statistical extraction. Along the way, we introduce a SNARG that is "sometimes statistically sound", and construct it from iO and rerandomizable commitments.
Last updated:  2026-08-23
Degree-Sum-Freedom Is Not EA Invariant: Exact Profiles in a 4-Uniform Permutation Family
Jingchuan Ma, Yanhua Liu, and Qiaoyun Huang
Degree-sum-freedom is a local criterion for division-property propagation from affine input spaces. Immediately after defining this criterion, the published chapter asserts invariance under extended-affine (EA) equivalence. We show that this assertion does not hold beyond ordinary sum-freedom and quantify the resulting variation. First, the natural Gold APN pair $x^3$ and $x^3+x$ has exact proper-flat values 3 and 2 on an infinite sequence of dimensions. We then study a known complete-mapping family of EA-equivalent, differentially 4-uniform permutations $F_b,G_b$ on $2r$ bits. For every odd $r$ and every $1\le c\le\lfloor(r-3)/2\rfloor$, we determine their exact codimension-$c$ profiles: $\mu_c(F_b)=2c$ and $\mu_c(G_b)=r+c-1$, equivalently $\tau_{2r-c}(F_b)=2r-2c$ and $\tau_{2r-c}(G_b)=r-c+1$. Thus the gap is $r-c-1\ge(r+1)/2$ simultaneously over a linear-size range of proper affine codimensions. The mate upper bound follows by specializing known generalized-degree duality with the exact source profile established here. The matching uniform lower bound is family-specific: after an associated-graded reduction, odd codimensions are detected by one classical consecutive Moore determinant, whereas even codimensions require a jointly nonvanishing family of replacement minors. A cyclic carry classification proves that the selected coefficients are complete reduced coefficients. These results concern local affine-input division-property behavior; they do not yield a multiround distinguisher or an attack on a concrete cipher.
Last updated:  2026-08-23
Efficient Additive Randomized Encodings for String Oblivious Transfer: A Core Primitive for General Functions
Masaya Yoshimura, Kyoichi Asano, Yugo Kasashima, Mitsugu Iwamoto, and Yohei Watanabe
Additive Randomized Encodings (AREs) provide a lightweight route to non-interactive secure computation: each party locally produces a randomized encoding of its input, and an evaluator learns only the function value from the sum of these encodings. Prior frameworks for constructing AREs for general functions ultimately hinge on an efficient ARE for string oblivious transfer (SOT), making SOT the core efficiency bottleneck. We revisit this final step and present improved ARE constructions for SOT. First, we streamline the recent PKE-based approach by directly constructing the required one-sided ARE (OSARE) for SOT. This yields a perfectly correct, statistically one-sided secure OSARE for SOT of size $\mathcal{O}(\lambda)$, improving the intermediate overhead and, consequently, the overall size of the resulting PKE-based ARE. Second, we give a pairing-free ARE for SOT under the Squaring DDH assumption. Our construction is compatible with Halevi et al.'s efficient equality-to-SOT methodology: we build an ARE for Rabin-OT that embeds a message in the equality-checking procedure and then transform it to SOT while incurring only constant-factor communication overhead and no additional correctness error. The resulting ARE for SOT has size $\mathcal{O}(\lambda)$ and negligible correctness error.
Last updated:  2026-08-23
Model Extraction of Convolutional Neural Networks with Max-Pooling
Haolin Liu, Adrien Siproudhis, Christina Boura, and Thomas Peyrin
Model extraction attacks aim to recover the internal parameters of neural networks through black-box queries. While significant progress has been achieved for fully connected ReLU networks, far less is known about structured architectures such as Convolutional Neural Networks (CNNs), which are widely used in practice. In particular, convolutional layers introduce locality and weight sharing, while max-pooling operations leak only relative activation information, both of which require rethinking and extending existing extraction techniques. In this work, we study the extraction of CNNs combining ReLU activations and max-pooling layers in the soft-label setting. We first demonstrate that max-pooling can be understood as a natural extension of the ReLU non-linear operation, where the attacker only has access to relative information between neurons. The local structure of convolution allows us to overcome this difficulty and reconstruct the underlying convolutional kernel. We also introduce optimizations that take advantage of the specific structure of CNNs: by using receptive-field analysis, we design efficient methods to filter noise and localize critical points. These improvements significantly reduce the computational cost compared to a naive reduction to a large sparse fully connected network. Finally, we validate our methodology experimentally on a compact VGG-style convolutional neural network trained on CIFAR-10. The results demonstrate successful layer-by-layer extraction in practice, accurate localization of critical points, and significant efficiency gains from receptive-field-based localization.
Last updated:  2026-08-22
Thunderbolt: Fast Asynchronous Off-Chain Bitcoin Transfers
Hongbo Wen, Hanzhi Liu, Yanju Chen, Jingyu Ke, Dahlia Malkhi, and Yu Feng
We present Thunderbolt, an off-chain protocol that transfers Bitcoin UTXO ownership with seconds-scale latency, requires no channel graph, no routing, and no liquidity rebalancing, and lets the recipient be offline at the time of transfer. A single UTXO is locked once on-chain under a fixed public key jointly held by the current owner and a threshold committee; ownership then passes through an unbounded sequence of holders; each transfer is a purely off-chain, asynchronous operation whose on-chain cost is zero. The chain sees exactly two transactions regardless of how many transfers occur. The core invariant is an algebraic cancellation: at each transfer the recipient's fresh secret is added to the holder's share and subtracted from the committee's share, so both shares rotate while the on-chain key stays fixed. To enforce this, the recipient publishes an invoice to a shared append-only ledger (the Thunderbolt Ledger): a public commitment, an encrypted copy for himself, and an encrypted copy for the committee, together with a zero-knowledge proof that all three encode the same fresh secret. The sender fetches the invoice, verifies the proof, homomorphically folds her secret into the recipient's ciphertext to produce a new ownership credential, and publishes the result with a second zero-knowledge proof. Both proofs use a single Sigma-protocol response to force the same witness across elliptic-curve and Paillier verification equations, requiring no trusted setup. The committee operates under a standard $(t,n)$-threshold honest-majority assumption: at most $t{-}1$ of $n$ members may be corrupted. The recipient decrypts at any later time; the committee subtracts the fresh secret from its share. By binding each transfer to a distinct fresh secret and context identifier, multiple UTXOs can be transferred independently in parallel. On our benchmark machine, a complete off-chain transfer finishes in 1022ms with a combined proof size of 3.8KB. General-purpose SNARK (Succinct Non-interactive Argument of Knowledge) backends are orders of magnitude slower on the same relations: even a reduced-parameter instantiation already exceeds our native proving time by two orders of magnitude, and a faithful realization at the deployed 3072-bit Paillier modulus exceeds the memory budget of consumer hardware.
Last updated:  2026-08-22
Dynamic and Optimal Function Inversion in the Small-Time Regime
John Kuszmaul and William Kuszmaul
The classic function-inversion problem considers the task of constructing a data structure which, given access to a constant-time oracle for a function $f : [N] \rightarrow [N]$, supports efficient inverse-queries on $f$. This problem has been studied extensively in the small-space/large-time regime, where one wishes to use space $S$, say, $N^{1 - \Omega(1)}$ bits, and where the query time is intended to be a small polynomial of $N$. Much less attention has been given to the \emph{small-time/large-space} regime, where $S = (N \log N) / t$ for some relatively small $t$, and where the goal is to achieve a good space bound as a function of $t$. In this paper, we give an optimal solution in the small-time regime, achieving space $S = O(N \log N / t)$ and time $O(t)$ for any $t \le O(\log N / \log \log N)$. This matches a lower bound by Yao (and is the first parameter regime where the lower bound has been matched for general functions). Additionally, we extend our solution to support point-updates to $f$, also in $O(t)$ time. Our techniques for supporting point updates also extend to the classic function-inversion solution of Fiat and Naor. All of our results are motivated by the data-structural perspective on function inversion, in which the goal is to supplement an already-existing data structure $\mathcal{D}_1$ (which, as part of its functionality, encodes some function $f$) with a small secondary data structure $\mathcal{D}_2$ that supports inverse queries. Our results allow $\mathcal{D}_2$ to be implemented in $(N \log N)/t$ bits with $O(t)$ query (and update) times -- if $\mathcal{D}_1$ is itself $\Theta(N \log N)$ bits, this results in the overall space usage increasing by only a $(1 + O(1/t))$ factor. As a sample application of our results, we show how to construct dynamic unordered graphs that use space $(1 + \epsilon)$-close to information-theoretically optimal while offering adjacency queries, neighborhood queries, and edge insertions/deletions in amortized time $O(\epsilon^{-1})$.
Last updated:  2026-08-22
Traceability for Free: Traceable Ring Signatures Revisited
Xiangyu Liu
Linkable Ring Signatures (LRS) allow anonymous signing on behalf of an ad hoc ring, while making any two signatures by the same signer publicly linkable. Traceable Ring Signatures (TRS), introduced by Fujisaki and Suzuki [PKC'07], strengthen linking to tracing: two signatures on different messages additionally reveal the signer's public key. Since cheating almost always means signing two distinct messages, for example two conflicting transactions, traceability turns detection into accountability and makes misbehavior costly. However, TRS remain far less studied and deployed than LRS. We identify two gaps and address both. First, the security notions inherited from [PKC'07], anonymity, linkability, and exculpability, do not capture attacks specific to tracing. For example, they together do not imply unforgeability, a fundamental requirement for all signature-like primitives. We close this gap by introducing extended linkability and extended exculpability, which reflect the security requirements of TRS more faithfully than their standard counterparts. Second, all existing TRS schemes trace in $O(n)$ time for a ring of size $n$, whereas LRS link in $O(1)$. Over a pool of $\ell$ signatures, pairwise tracing therefore costs $O(\ell^2 n)$ against $O(\ell^2)$ for linking. We design a new TRS framework with $O(1)$ tracing for valid signatures. Instantiated from DDH with Bulletproofs [S&P'18], it yields signatures of $(64\log n+544)$ bytes on Curve25519. To our knowledge this is the shortest TRS for $n \ge 12$, and it is on par with state-of-the-art DLog-based LRS schemes. TRS thus gains traceability at essentially no cost over LRS.
Last updated:  2026-08-22
Cofactor-torsion attacks on hinted scalar multiplications in SNARK circuits
Youssef El Housni
Proving an elliptic curve scalar multiplication [k]P= Q ∈ E(Fp) inside a SNARK is much cheaper when the output Q is hinted by the prover and only verified in-circuit, rather than recomputed. The recent scalar multiplication techniques of Eagen, El Housni, Masson and Piellard (Latincrypt 2025) certify a hinted Q with a short lattice reduction (fraction) decomposition of the scalar and a single group identity, and yield the fastest known in-circuit scalar multiplications. We observe that the soundness of this whole family rests on an implicit prime-order hypothesis: the certifying identity is checked over the full group E(Fp), and only when E(Fp) has trivial cofactor does it force Q into the prime-order subgroup. On cofactor curves the certification is unsound. We give two concrete forgery classes against these hinted gadgets: an any-scalar attack that, for a target scalar fixed by the statement, adapts the decomposition so a small rational torsion point cancels from the identity; and a chosen-scalar attack that vanishes the output-side coefficients modulo a small cofactor prime and solves for the scalar afterwards. Both make the gadget accept Q′ = [k]P + T for a non-zero torsion point T as if it were [k]P. We quantify the reachable torsion in terms of the sub-scalar range bound and validate the attacks on widely deployed curves such as BLS12-381, BN254 and BW6-761. The straightforward fix is to check that Q lies in the subgroup but is expensive. We propose a cheaper one that binds the hinted output through a hinted preimage, with the minimal such constant that suffices against each attack model.
Last updated:  2026-08-22
Beyond Anonymity Sets: A Security Model for Distributed Shuffling in Adversarial Environments
Adrian Cinal, Oliwer Sobolewski, Gabriel Wechta, and Filip Zagorski
Distributed shuffling is a core primitive underlying mix-nets, electronic voting, and, more recently, single secret leader election (SSLE) protocols for proof-of-stake blockchains. In these settings, a collection of resource-constrained parties jointly permutes a list of ciphertexts or commitments in order to conceal the correspondence between inputs and outputs. Existing security analyses of such protocols typically rely on heuristic anonymity measures or implicitly assume honest behavior; therefore, they fail to capture statistical dependencies that arise when shuffling is partial and some participants are corrupted. In this work, we introduce a new security model for distributed shuffling that accurately reflects the setting of real-world attacks by explicitly accounting for adversarial corruption and information leakage. Our model allows an adversary to corrupt a subset of shufflers and track selected elements throughout the execution, as well as query the resulting permutation afterwards. We then turn to studying Whisk in this model, the shuffle-based SSLE mechanism proposed for Ethereum. Leveraging Markov-chain techniques, we show that security can only be guaranteed for more stringent parameters than currently proposed. We evaluate the performance impact of changing these parameters on the Ethereum network.
Last updated:  2026-08-22
Multi-Party Private Set Intersection with Optimal Online Round Complexity and Updatability
Jiadi Zhang, Hao Wang, Ye Su, Xiaochao Wei, Lei Wu, and Zhi Li
Multi-party private set intersection (MPSI) enables multiple parties to securely compute the intersection of their private datasets without revealing any information beyond the intersection itself. However, as the number of participants scales, the performance of multi-party PSI protocols is significantly influenced, with the number of interaction rounds emerging as a critical bottleneck. In this paper, we propose a novel MPSI protocol and its updatable extension based on function secret sharing and oblivious key-value stores, achieving optimal one-pass online interaction. Our construction guarantees security in the semi-honest model, resisting collusion among any $n-1$ parties when the Leader is honest, and among any $n-2$ parties when the Leader is corrupted—an assumption that aligns well with many practical deployment scenarios. Furthermore, our multi-party updatable PSI (MUPSI) protocol allows parties to efficiently compute the intersection over dynamically updated sets. Our MUPSI protocol achieves collusion resistance against any $n-1$ participants, assuming an honest Leader. It ensures that both computational and communication complexities scale exclusively with the size of the updates rather than the entire datasets, exhibiting superior performance particularly when handling unbalanced sets and large participant cohorts. All proposed protocols exhibit strong scalability with respect to participant count. We demonstrate the superiority of our protocols through implementation and comparison with state-of-the-art MPSI protocols. Experiments show that when the number of participants ranges from $20$ to $140$ and the set size ranges from $2^{12}$ to $2^{20}$, our MPSI protocol is competitive. Notably, in the WAN setting with $140$ participants and a set size of $2^{20}$, the running time is reduced by $49.1\times$ compared with GLW+24. Our MUPSI protocol avoids PSI operations on entire sets, achieving a reduction in running time by an order of magnitude.
Last updated:  2026-08-22
Linear self-equivalence of the known families of APN functions: a unified point of view
Jules Baudrin, Anne Canteaut, and Léo Perrin
The Kim mapping, which belongs to the only known CCZ-equivalence class in even dimension that contains an APN bijection, and the APN bijections in dimension 9 exhibited by Beierle and Leander, all have a univariate representation corresponding to a cyclotomic mapping (aka Wan-Lidl polynomial), and they are all linearly-equivalent to functions with a highly-structured multivariate representation. In this paper, we show that functions having these properties, which correspond to multivariate projective mappings, i.e. multivariate functions whose coordinates are homogeneous, actually appear in the CCZ-equivalence classes of almost all known infinite families of APN functions. However, this behavior is not inherent to the APN property. Indeed, we prove that the vast majority of the known sporadic examples of APN functions in dimension 6 and 8, including almost all APN functions whose automorphism group is reduced to the automorphisms derived from their affine derivatives, are not CCZ-equivalent to an affinely self-equivalent function.
Last updated:  2026-08-22
SoK: Why Optimal Cryptographic Combiners Do Not Get Deployed: Security, Complexity, and Adoption of Hybrid KEMs
Merland Chrislain Chadrel BAFOUETILA and Anis BKAKRIA
XtM (XOR-then-MAC) is provably optimal against quantum adversaries. As of March 2025, no production cryptographic library implements it. HKDF, with weaker security guarantees, is deployed in 91% of the 44 libraries we examined. This gap is not accidental.This Systematization of Knowledge (SoK) introduces the (A, P, φ) framework to explain it: A measures authentication strength, P measures IETF standardization maturity, and φ measures implementation complexity. To our knowledge, this is the first falsifiable, quantitative model predicting cryptographic adoption grounded in observable software engineering indicators. We apply this framework to seven combiner families and 44 cryptographic libraries, validate φ against measured integration LOC across 9 real-world repositories, and derive predictions verifiable by 2028.Our evidence suggests that implementation complexity is a first-order explanatory factor in cryptographic adoption. The most deployable construction is not the most secure one in isolation: it is the most secure one engineers can integrate, audit, and maintain at scale.
Last updated:  2026-08-22
Multi-PGBF: Efficient Oblivious Key-Value Store and Application to Private Set Intersection
Mingli Wu, Tsz Hon Yuen, Man Ho Au, and Siu-Ming Yiu
An oblivious key-value store is a data structure that can encode and decode $n$ key-value pairs in a table of size $m$ obliviously. After encoding, one cannot distinguish the encoded key-value pairs from other key-value pairs in the input domain. In this paper, we first propose a data structure called Peelable Garbled Bloom Filter (PGBF), which encodes the key-value pairs in a similar way to peeling and unpeeling an \emph{onion}. Specifically, it can divide the key-value pair set (i.e., onion) as multiple subsets (i.e., peels) and order them from the outermost peel to the innermost peel by using a counting Bloom filter. However, using a small expansion rate (i.e., $\eta=m/n$) in PGBF will result in a non-empty core issue with non-negligible probability. To handle this issue, we propose Multi-PGBF by combining multiple PGBFs to do the peelings and unpeelings recursively. In addition, we propose a variant C-Multi-PGBF by clustering a large set into small sets to achieve faster encoding efficiency. Our experiments show that Multi-PGBF and C-Multi-PGBF obtain the best encoding and decoding efficiency. Multi-PGBF improves the encoding time of RR (CCS’22) by $65.1\%\sim 77.6\%$, while C-Multi-PGBF improves the encoding time of the clustered RR variant by $60.2\%\sim 64.7\%$. For decoding, Multi-PGBF is $28.6\%\sim 62.4\%$ faster than RR (CCS'22) and $89.7\%\sim 96.3\%$ faster than RB-OKVS (Usenix'23). When integrated into the state-of-the-art two-party and multi-party private set intersection protocols (Eurocrypt'21, Usenix'24), Multi-PGBF and C-Multi-PGBF lead to faster protocols than those using existing OKVS constructions in most settings.
Last updated:  2026-08-22
New Lower Bounds for Rows of $d$-Disjunct Matrices via Recursive Potentials
Xiaopeng Zhao
In nonadaptive combinatorial group testing, given $n$ items with at most $d$ positives, the goal is to identify them using as few pooled tests as possible. A $t\times n$ binary matrix represents the design, where rows are tests and columns are items. The matrix is $d$-disjunct if no column is contained in the Boolean union of any $d$ others. Let $T(d)$ be the minimum $t$ for which such a matrix exists with $n>t$. Shangguan and Ge proved $T(d)\ge \frac{15+\sqrt{33}}{24}d^2$ by counting private pairs (IEEE Trans. Inf. Theory, 62(12):7518-7521, 2016). In this paper, we strengthen their argument by introducing a column-deletion recurrence in which the light-heavy threshold varies with the recursive state $z=(n-t)/d^2$, rather than remaining fixed. This yields the improved bound $T(d)\ge 0.9283d^2-O(d)$. The analytic core reduces to a first-order ODE, and a self-contained interval-arithmetic certificate verifies that the solution reaches the required contact point.
Last updated:  2026-08-21
Revisiting Simulation Extractability in the Updatable Setting
Hamidreza Khoshakhlagh
We revisit the notion of Simulation Extractability (SE) for SNARKs in the updatable setting. We demonstrate that existing formal definitions of SE in this setting are insufficient to guarantee the required non-malleability in real-world scenarios. Towards this, we first identify and frame a malleability vulnerability: a cross-SRS reinterpretation attack, which shows that an adversary can reuse or maul proofs across different, correlated SRSs generated through the update procedure. This is made possible because existing security definitions fail to model an adversary’s ability to observe simulated proofs relative to various derived SRSs. To close this security gap, we propose a revised and stronger security notion of Updatable Simulation Extractability (USE) which was originally defined in [GKK+22]. Our definition models a dynamic environment where the SRS is adaptively updatable by the adversary, who can also query simulation oracles for proofs under the resulting family of reachable SRSs. This captures the full extent of the adversarial capabilities observed in practice. Finally, we provide positive results for popular polynomial-IOP-based SNARKs, and show that these schemes satisfy our stronger USE notion, provided the circuit-specific SRS is securely bound into the proof transcript, e.g., via a correct implementation of the Fiat-Shamir transformation.
Last updated:  2026-08-21
Grand Danois: Succinct Multilinear Polynomial Commitments over Lattices
Anders Kallesoe and Hamidreza Khoshakhlagh
We present Grand Danois, a new post-quantum multilinear polynomial commitment scheme from lattices for polynomials over $\mathbb{F}_q$ that achieves polylogarithmic $O(\lambda \ell)$ verification complexity and proof sizes. We build on the general approach introduced in Hachi (ePrint 2026/156) with three key changes. First, we switch to the vanishing Short Integer Solution (vSIS) assumption to obtain structured public parameters for our commitment scheme and utilize this structure to design a sumcheck protocol amenable to succinct verification. Second, rather than casting ring relations into $\mathbb{F}_{q^k}[X]$, via the residual technique of Hachi, we express multiplication by fixed $\mathcal{R}_q$ elements through its rotation matrix, which lets the verifier fold each row of the constraint matrix in time linear rather than quadratic in the ring degree $d$. Third, we modify the quadratic relation used in Hachi and Greyhound (CRYPTO 2024) so that it becomes compatible with proving norm bounds using Johnson-Lindenstrauss projections. This is achieved through an adaptation of the structured projection strategy introduced in RoK and Roll (ASIACRYPT 2025). This has the benefit for communication complexity in that proving norm bounds and correct polynomial evaluation are integrated into a single protocol, reducing the number of commitments sent by the prover. Furthermore, we impose additional structure on our random projections to reduce the witness size even more aggressively during each round of recursion without sacrificing verification complexity. Under the vSIS assumption, our construction yields an estimated proof size of roughly $80$ KB for $2^{32}$-size polynomial evaluations.
Last updated:  2026-08-21
Constant-round MPC protocols with Fall-back Security
Anasuya Acharya, Aditya Patankar, Arpita Patra, Divya Ravi, and Raghavendra Vernekar
The notion of Best-of-Both-Worlds introduced in the work of Ishai et al. (CRYPTO 2006) investigated whether an MPC protocol can simultaneously provide two incomparable security guarantees depending on the number of corrupted parties. As a special case of this, Chaum et al. initiated the study of protocols that tolerate unbounded corruption within a certain adversary structure and PPT corruption of any number of parties beyond that. More recently, Acharya et al. (CRYPTO 2023) formalized this notion as MPC with fall-back security. Although the feasibility of such protocols has now been thoroughly studied in prior works, most of the existing protocols require round complexity linear in the number of parties and the computation size. In this work, we study the round complexity of MPC with fall-back security in the threshold corruption setting, presenting constant-round protocols for optimal thresholds. We present a semi-honest fall-back secure protocol for $t < \frac{n}{2}$ with 3 rounds, in the plain model, whereas the best known protocol in the same setting takes at least 11 rounds. In the CRS model, we present a maliciously fall-back secure protocol for the same threshold with 4 rounds, satisfying unanimous abort (UA). Finally, we extend this to a 5-round protocol that satisfies fairness in the presence of unbounded adversaries for $t < \frac{n}{2}$ corruptions and UA tolerating PPT adversaries for arbitrary corruption beyond that. In the malicious setting, we construct the first constant-round fall-back secure protocols.
Last updated:  2026-08-21
DumboMix: Robust Asynchronous Anonymous Broadcast Made Practical
Wei Tang, Hanwen Feng, Jiliang Li, Yuan Lu, and Qiang Tang
We present a practical framework $\mathsf{DumboMix}$ for asynchronous anonymous broadcasts with guaranteed output delivery (G.O.D., a.k.a. robustness), enabling a set of $n$ servers to privately solicit $N$ messages from distinct clients, such that these messages remain secret until they are revealed in uniform random order. Here, asynchronous G.O.D. ensures that all messages are eventually randomly mixed despite (i) arbitrary malicious behaviors by up to $\lfloor (n-1)/3 \rfloor$ Byzantine servers and (ii) unpredictable network delays and jitters. At the core of $\mathsf{DumboMix}$, we first propose a couple of practical mixing methods $\mathsf{DumboMix1}$ and $\mathsf{DumboMix2}$ for Shamir-secret-shared multi-party computation (MPC) over $\mathbb{Z}_p$, along with their server-optimized variants. When randomly mixing $N$ messages, their online phases require only $\mathcal{O}(1)$ multiplicative depth, expected $\mathcal{O}(N^2)$ scalar multiplications (between public and shared values), and up to $\mathcal{O}(N)$ MPC multiplications (between shared values). Moreover, assuming a robust underlying MPC framework, they guarantee that all revealed inputs are uniformly shuffled. In contrast, existing techniques fail to achieve all these performance and functionality features: The DC-net variant $\mathsf{Blinder}$ (CCS’20) may reveal a non-negligible fraction of inputs without shuffling them; Butterfly switching networks in secret-shared MPC (CCS’19) incur $\mathcal{O}(\log^2 N)$ multiplicative depth; RabbitMix (Security’24) requires $\mathcal{O}(N^2)$ MPC multiplications; and PowerMix (CCS’19) incurs $N^{3}/2$ scalar multiplications. We finally implement our new mixing methods within $\mathsf{DumboMPC\text{++}}$, our computation-optimized implementation of the state-of-the-art robust AMPC framework $\mathsf{DumboMPC}$ (Security’25), which provides more concretely efficient offline preprocessing while preserving asynchronous G.O.D. and optimal resilience. We then conduct extensive evaluations with $n=4$ to $31$ servers under varying network settings, revealing that our new mixing methods achieve 44.8--65.9× (resp. 37.1--52.7×), 4.8--7.1× (resp. 3.9--5.5×), and 2.7--4.0× (resp. 5.1--7.2×) speedups over RabbitMix, PowerMix, and the butterfly switching network, respectively, when shuffling 1024 messages in LAN (resp. WAN).
Last updated:  2026-08-21
Towards AI-driven Optimization of Robust Probing Model-compliant Masked Hardware Gadgets Using Evolutionary Algorithms
David S. Koblah, Dev M. Mehta, Nathan Poch, Mohammad Hashemi, Fatemeh Ganji, and Domenic Forte
Masked hardware design is a central countermeasure against side-channel analysis (SCA), but its practical deployment remains costly due to the overhead and design complexity of secure implementations. To manage this complexity, modern masked circuits are increasingly built from composable masked building blocks, referred to as gadgets. However, improving the implementation quality of such gadgets is challenging because optimization must not violate formal security requirements. This paper studies the optimization of masked hardware gadgets under formal security by comparing conventional CAD transformations with a security-aware design automation framework based on evolutionary algorithms. The conventional CAD flow explores structural alternatives exposed by technology mapping, FRAIG-based rewriting, and retiming, whereas the evolutionary framework adaptively explores alternative gate-level realizations through circuit-specific mutation, crossover, and multi-objective selection. The resulting implementations are evaluated for power and area while enforcing functional correctness and compliance with the probing model through equivalence checking and pre-silicon side-channel verification. Our results show that conventional CAD techniques can yield substantial improvements in selected cases, up to 60%, but their behavior is not systematic under strict masking constraints. In contrast, the evolutionary framework provides a controlled, adaptive search over alternative gate-level realizations and produces security-preserving implementations with measurable improvements over naïve synthesis, reaching up to 15% reduction in power and area in selected cases. We validate the optimized designs using industry-standard synthesis and pre-silicon side-channel verification tools. We further show, for AES, that additional savings remain possible even relative to a state-of-the-art compressed masked design.
Last updated:  2026-08-21
Eavesdropper-Blind Remote State Preparation and Applications to Quantum Public-Key Encryption
Kaniuar Bacho and Alexandru Cojocaru
Remote state preparation (RSP) is a central primitive in quantum cryptography, enabling classical parties to remotely construct quantum states using only classical communication. As a result, RSP serves as a key building block in numerous protocols involving classical clients and quantum servers, allowing classical parties to leverage the advantages offered by powerful quantum computers. All known constructions of RSP rely on strong cryptographic assumptions, typically variants of trapdoor claw-free functions (TCFs). In this work, we initiate the study of a weaker form of remote state preparation, which we call eavesdropper-blind remote state preparation (EB-RSP). Informally, EB-RSP requires blindness only against external observers who see the transcript of the honest protocol, rather than against the quantum server itself. Despite this relaxed adversarial model, the resulting notion remains sufficient for useful cryptographic applications. In particular, we show that two-message EB-RSP already suffices to construct quantum public-key encryption with classical public keys and quantum ciphertexts. We then construct two-message EB-RSP protocols from specific one-way group actions, yielding a first step toward RSP-type primitives based on assumptions that do not rely on trapdoors. Finally, we observe that existing RSP constructions are likely naturally adaptable to the two-message EB-RSP notion; we demonstrate this explicitly for a concrete TCF-based RSP construction.
Last updated:  2026-08-21
Exact linear correlations and the cost of Walsh-transform key recovery, with application to SPEEDY
Guoqiang Liu and Bing Sun
When two S-box layers of a round are separated by no key addition, the round correlation is a signed sum over all compatible intermediate masks, not a product of layer correlations, so the product rule can fail in either direction. Our central finding is that evaluating this intra-round sum exactly changes the assessment of the published linear cryptanalysis of SPEEDY, whose two S-box layers are separated only by ShiftColumns. We first develop the linear cryptanalysis of this setting: an exact one-round algorithm with a decidable exactness condition for the product rule, a dependency-graph decomposition, a covering-number bound strengthening linear-trail weight bounds, and a Walsh-support criterion in which the affine dimension of that support, limited by the endpoint key masks, fixes the key-recovery transform cost. Potentials use the independent-round-key model; complexities are in equivalent encryptions. Applied to SPEEDY, these tools revise published results: a reported five-round mask sequence has exact correlation $2^{-90.0962}$, not $2^{-93.0147}$; the new bound raises the unrestricted five-round weight bound from $53.7714$ to $62.2616$ bits; and the full-round attack on SPEEDY-7-192 reported at time $2^{158.06}$ needs at least $2^{199.97}$ encryptions in the pruning class considered. For SPEEDY-6-192 we give a six-round known-plaintext attack (data $2^{169.84}$, time $2^{170.20}$, memory $2^{156}$) and show that the attack class defined here contains no attack with data and time both at most $2^{128}$, its time being at least $2^{136.302}$. The same exact evaluation also revises a four-round differential-linear correlation.
Last updated:  2026-08-21
Relaxed Modular PCS from Arbitrary PCS and Applications to SNARKs for Integers
Alireza Shirzad, Sriram Sridhar, Dimitrios Papadopoulos, and Charalampos Papamanthou
\emph{Modular Polynomial Commitment Schemes (Mod-PCS)} extend standard PCSs by enabling provable evaluation of integer polynomials modulo a random modulus, providing a natural foundation for SNARKs that operate directly over large integers without emulating arithmetic in finite fields. Only two Mod-PCS constructions are known. The first (Campanelli and Hall-Andersen, IACR ePrint 2024) serves primarily as a feasibility result and is impractical and not post-quantum secure due to its reliance on groups of unknown order. The second (Garetta et al., CRYPTO 2025) introduces the weaker notion of \emph{relaxed} Mod-PCS, but is not fully succinct: committing to a multilinear polynomial with $N$ terms and $B$-bit coefficients requires $O(\sqrt{N}B)$ proof size and verification time. We present a black-box transformation that builds relaxed Mod-PCS from any standard PCS, enabling new constructions. Instantiating our transformation with a tensor-code PCS yields the first relaxed Mod-PCS with $O(\log (N+B))$ proof size and verifier time, which is transparent and plausibly post-quantum secure. Using this scheme within the framework of Garetta et al., we obtain the first fully succinct SNARK for the Customizable Constraint System over $\mathbb{Z}_B$, achieving $O(B\log N + N\log N \log B)$ prover time and $O(\log (N+B))$ verifier time and proof size. Our approach relies on a commitment-switching technique for integer polynomials and a new batched integer commitment scheme from any PCS. We further introduce improved arguments for integer addition and multiplication, correctness of the number-theoretic transform, and general Diophantine relations over committed integers.
Last updated:  2026-08-21
Two Novel Multidimensional Affine Variations of the Hill Cipher
Porter Eldridge Coggins
Two novel symmetric multidimensional affine nested variations of the Hill Cipher are presented. The Hill Cipher is a block polygraphic substitution encryption scheme based on a linear transformation of plaintext characters into ciphertext characters. In the time since Hill first published his encryption scheme, variations, modifications, and improvements of theoretical and practical importance have been published every year indicating that the Hill Cipher is an active area of cryptography research. The first variation presented in this paper incorporated invertible key matrices of orders 2, 4, and 8 such that the matrix values of the 2×2 matrix rotate positions with each block of characters in a similar manner to the rotating letter wheels of a German Enigma Encoder, then results of the 2×2 key matrices output are passed to 4×4 key matrices, and 8x8 key matrix, 4×4 key matrices, and rotative-value 2×2 key matrices. The second variation is configured with invertible key matrices of orders 4, 8, and 16 without rotation of matrix values in a similar manner to the first variation. In both variations, plaintext characters of each block are operated on by exclusive-or (XOR) vectors prior to multiplication with the matrices to create the affine ciphers. Strengths, weaknesses, and other considerations are provided in the discussion. Two proposals are also argued with rationale for a more robust character set for encryption and the increase in modulus that the character set allows, and the possible advantages and disadvantages of affine XOR vectors.
Last updated:  2026-08-21
Multidimensional Hill Cipher Substitution– Permutation Network
Porter E. Coggins, III
MD-Hill-SPN is the first Hill-based construction to combine a multi-tier diffusion mix layer, a memory-hard KDF, and a simultaneous multi-metric empirical evaluation. Two independent runs of the full metric suite yield: (a) full plaintext avalanche from round 1 (mean 63.97–64.67 of 128 bits, ideal 64); (b) the differential-probability sampling floor of 2 × 10−5 reached at round 4 (50,000 of 50,000 output differences distinct, both sessions); (c) algebraic-degree lower-bound saturation at the maximum observable value from round 1; (d) linear-bias indistinguishable from random (combined exceedance 4.40%, below the 4.55% noise floor); and (e) branch numbers at the Singleton (MDS) bound for every tier (B = 5 for 4 × 4, B = 9 for 8 × 8, B = 17 for 16 × 16), computed exhaustively over weight-1 inputs. MD-Hill-SPN therefore moves beyond theoretical construction to a construction that passes a defined empirical evaluation suite: avalanche, differential sampling, linear-bias probing, algebraic-degree lower bounds, and MDS branch numbers under single-key, known-plaintext conditions with fixed parameters, an evaluation no prior Hill cipher variant has reported in full.
Last updated:  2026-08-21
Pilaf: Fully Tight Two-Round Threshold Signatures with Adaptive Corruptions
Chen Qian, Xingyu Zhao, Hao Cheng, Zengpeng Li, Puwen Wei, and Quan Yuan
Threshold signatures are deployed in settings where an adversary may run many concurrent signing sessions and corrupt signers adaptively. Two-round schemes make this especially delicate. Their first-round messages are independent of the signed message and can be preprocessed offline, so a later corruption must reveal randomness that is consistent with commitments already published in prior transcripts. Existing adaptive constructions address this tension by adding rounds, relying on algebraic or knowledge assumptions, or paying non-tight losses from guessing the corruption pattern, the decisive session, or the final transcript. We construct $\mathsf{TPilaf}$, the first two-round threshold signature scheme that combines partially non-interactive signing with a fully tight proof against adaptive corruptions. The scheme is pairing-free and is built in prime-order groups from the $\mathsf{MDDH}$ assumption in the random-oracle model. Its first-round messages can be generated offline, and any threshold set of signers can aggregate their second-round shares into a single publicly verifiable signature. The proof combines two ingredients. First, we introduce a linearly homomorphic dual-mode commitment with targetable opening. This lets the simulator open an already fixed commitment to the aggregate target imposed by a later Fiat-Shamir challenge. Second, we use profile-wise zero-sum masking with posterior completion. Corruption openings and signing responses are therefore sampled from the exact conditional law while values already visible to the adversary remain cached. Together, these tools enable a delayed branch-decision argument. The reduction waits until the adversary's own queries determine the last touched coordinate, completes only latent state, and then binds the forged hidden branch. The final bound has no combinatorial loss in the number of users, threshold, sessions, or corruption patterns, and contains only the explicit bad-event and assumption terms appearing in the theorem.
Last updated:  2026-08-21
Lightweight Lattice-based Single-Party Public-Key Authenticated Key Exchange
Alex Aïdan, Sébastien Canard, Emmanuel Fouotsa, and Nyiang Melchisedech Mbeng
Authenticated Key Exchange (AKE) is a cornerstone of secure communication, especially in resource-constrained IoT environments where lightweight and post-quantum security are paramount. While lattice-based cryptography offers promising solutions, existing post-quantum AKE protocols often prioritize strong security notions, such as the use of an IND-CCA encryption scheme, incurring overheads incompatible with IoT devices. This raises a critical question: Can one-way security (OW), a weaker but potentially more efficient notion, suffice for secure AKE in the post-quantum era? We address this challenge by revisiting the ALIKE framework (ISO/IEC 29192-4), which achieves OW-CCA-based AKE using deterministic RSA. However, RSA’s quantum vulnerability and the lack of lattice-based OW-CCA schemes hinder its applicability today. Our work bridges this gap through three key contributions. First, we prove that the Hash-Before-Encrypt (HBE) paradigm generically transforms deterministic OW-CPA schemes into OW-CCA-secure ones. We additionally present the Fujisaki–Okamoto transform and its security proof construction, providing a reference for understanding the efficiency advantages of the proposed HBE-based approach. Second, we modify Bai et al.’s efficient lattice-based OW-CPA scheme to a deterministic variant and rigorously prove its security. Third, we generalize the SPAKE framework to support our OW-CCA construction, enabling post-quantum AKE with minimal assumptions, implement and benchmark the resulting protocol, demonstrating state-of-the-art efficiency for lightweight, quantum-resistant AKE. By relaxing security requirements from IND-CCA to OW-CCA while preserving adaptive security we achieve a practical balance between robustness and performance, paving the way for deployable solutions in constrained environments like IoT and connected vehicles.
Last updated:  2026-08-21
Midpoint Reset: A Full-Round Poseidon Collision from an Adaptively Chosen MDS Matrix
Sunghyeon Jo
We give an explicit compression collision for all 28 rounds of the KoalaBear Poseidon instance with parameters $(t,\alpha,R_F,R_P)=(16,3,8,20)$, in the setting where the round constants are fixed before the MDS linear layer is chosen. The main problem is to construct a single linear layer that simultaneously controls two executions through both the full and partial rounds. We do this by tracking their midpoint and half-difference. In each two-round block, one prescribed image of the linear layer cancels the midpoint against the next round constant, so the following odd cubic S-box receives opposite states and resets the midpoint to zero. Two additional images are reused throughout the permutation to return the half-difference to the same one-dimensional subspace. The resulting trajectory constraints determine a linear layer, while a scalar recurrence closes the final difference under feed-forward. For the KoalaBear instance we obtain a collision in all sixteen output coordinates with an MDS matrix satisfying the prescribed linear-layer checks. The scalar construction reduces to low-degree equations and admits a family of parameter choices, so the collision is not an isolated instance. The result exposes an adaptive correlation between fixed round constants and a subsequently chosen linear layer that matrix-only checks do not capture.
Last updated:  2026-08-21
Revisiting the Transferability of Chosen- to Known-plaintext Attacks and Applications to Round-reduced AES
Xiaomeng Sun, Eik List, and Wenying Zhang
Differential-based attacks represent the best known results for many block ciphers. Such attacks usually demand that the adversary an choose plaintexts (CP) or ciphertexts (CC) in subspaces to satisfy differential trails. However, many widespread modes of operation or applications prohibit the adversary from directly choosing inputs for the majority of primitive calls. While Biham and Shamir already suggested a straightforward trade-off for standard differential attacks in their work on the DES, studies on advanced differential-based types, such as impossible-differential, rectangle, or mixture attacks, have surprisingly received little attention so far. In this work, we study applications of differential-based attacks in the random known-plaintext model (RKP) of the above. For the AES as the probably most widespread block cipher, we derive the best existing distinguishers and attacks in the RKP model on all versions, improving earlier results by at least one round. Interestingly, we show that Demirci-Selcuk meet-in-the-middle attacks with differential enumeration, which require much related data, can also be effective in that setting without approaching the full codebook too closely. For several of our attacks, we showcase differences between the models as trails that lead to the best known attack complexities under chosen data are suboptimal in the RKP model, and can be replaced by better trails. While our results do not threaten the security of the full AES, and their complexities are too high to represent any threats, we hope to inspire cryptographers to also consider attacks in the RKP for future attacks.
Last updated:  2026-08-21
Efficient Homomorphic String Search via TFHE
Shintaro Narisada, Hiroki Okada, Takashi Nishide, and Kazuhide Fukushima
We present a method for secure pattern matching over encrypted texts using TFHE. Our approach realizes a fully secure binary search algorithm by leveraging two operational modes of integer-input TFHE. While the BGV-based method of Bonte and Iliashenko (CCSW '20) requires $O(|P| \cdot |T|)$ secure character comparisons to find a pattern $P$ in a text $T$, our method reduces this to $O(|P|\log |T|)$ comparisons, achieving improved scalability for large texts. As a result, our method can find a pattern of length 100 in an encrypted text containing genomic data of one million characters in less than 5 minutes, where prior work would require approximately 5 days for the same task. These results highlight the practicality of TFHE and its potential for large-scale secure string search.
Last updated:  2026-08-21
HACC: A Hierarchical Accumulator with Constant Public Parameters and Logarithm Time Complexity for Large Evolving Sets
Borui Chen, Liang Zhang, Kexin Li, Dongliang Cai, Jiamian Yan, and Haibin Kan
Dynamic universal accumulators compress an evolving set into a short digest with membership and non-membership witnesses for each element. Bilinear Pairing (BP) accumulators offer succinct witnesses and fast verification, but their public parameters size, witness generation and dynamic costs scale linearly with the set size in the trapdoorless setting. To address this bottleneck, we present HACC, a trapdoorless hierarchical accumulator that organizes capacity-bounded BP accumulators over ordered buckets into a $t$-ary tree. By fixing the node capacity $t$, HACC is a pairing-based accumulator whose public parameters can be independent of the set size $n$. Its ordered buckets yield native non-membership proofs and $\mathcal{O}(t\log_t n)$ witness generation cost, and non-cascading bucket split and merge mechanisms keep it fully dynamic at worst-case $\mathcal{O}(t\log_t n)$ dynamic cost with amortized $\mathcal{O}(1)$ witness updates. Its witnesses are of size $\mathcal{O}(\log_t n)$ and verify with as many pairings, which an optional path compression via polynomial multiproofs reduces to a constant for read-heavy epoch-based settings. We prove HACC correct and sound under the $t$-SDH assumption in the random oracle model. Experimentally, under comparable budgets, HACC accelerates element update and witness generation by $8.0\times$--$5087\times$ over a monolithic BP accumulator (Nguyen, CT-RSA'05, Damgård et al., eprint'08, and Srinivasan et al., CCS'22) while consuming $15.6\times$--$15933\times$ smaller public parameters.
Last updated:  2026-08-21
Enabling Threshold Custody for the Lightning Network with Nested Threshold Multi-Signatures
Uncategorized
Paul Gerhart, Nadav Kohen, Jesse Posner, and Matias Furszyfer
Show abstract
Uncategorized
The Bitcoin Lightning Network secures hundreds of millions of dollars, yet channel endpoints rely on vulnerable single online keys. Although threshold signatures are routinely used to protect on-chain Bitcoin, no practical deployment has been possible for Lightning channels. This is because thresholdizing a Lightning party requires nesting a threshold signature scheme inside of an established two-party MuSig2 protocol without altering its nonce exchange or message flow. In this work, we resolve this limitation by formalizing nested threshold multi-signatures, a new cryptographic primitive for thresholdizing one participant inside a multi-signature protocol. As an instance of this primitive, we present Iceberg, the first construction for nested threshold MuSig2 signatures. Iceberg enables one side of a Lightning channel to operate as a $t$-of-$n$ threshold group while appearing to the counterparty as a standard MuSig2 participant. As a result, threshold custody can be deployed unilaterally on today's Lightning Network without requiring any modifications to Bitcoin, the Lightning protocol, or channel counterparties. We prove the security of Iceberg, integrate a prototype into a production Lightning node, and benchmark its performance. Our measurements show that thresholdizing a Lightning channel incurs only modest overhead, since a threshold group tolerating one corrupted member sustains over $93\%$ of the payment throughput of an unmodified endpoint.
Last updated:  2026-08-21
Fully Homomorphic Encryption with Chosen-Ciphertext Security from LWE
Rupeng Yang, Zuoxia Yu, and Willy Susilo
We construct (1-hop) fully homomorphic encryption (FHE) schemes with chosen-ciphertext (CCA) security from the learning with errors (LWE) assumption in the standard model. Security of our construction only relies on the circular-secure LWE, which matches the assumptions needed for FHE with the basic chosen-plaintext security. Besides, the scheme achieves a security notion that is strictly stronger than the CCA1 security. Prior FHE schemes with even just CCA1 security require either the random oracle model or non-falsifiable assumptions. The construction follows the well-known Naor-Yung double encryption paradigm. However, unlike previous works [Boneh et al., ITCS 2012; Canetti et al., PKC 2017; Manulis and Nguyen, Eurocrypt 2024], which employ general zero-knowledge succinct non-interactive arguments of knowledge (ZK-SNARKs), we design a special succinct argument to prove the validity of FHE ciphertexts. The succinct argument is constructed from batch arguments for NP and a new primitive called predicate extractable commitment, which may be of independent interest.
Last updated:  2026-08-20
QuaILLL: Quaternion Ideal LLL and BKZ
Joshua Limbrey, Cong Ling, and Christian Porter
The current state of the art for cryptanalysis generic rank-2 module LIP schemes invokes an SVP oracle on the canonical real embedding, discarding the quaternionic structure made available by the reduction of rank-2 module LIP to the reduced-norm Principal Ideal Problem (nrd-PIP) over quaternion algebras (we note, that since writing, this is no longer the case for certain instances, such as Hawk). We address this gap by giving, to our knowledge, the first lattice reduction algorithms over quaternion rings applied in a cryptographic setting, and the first description of quaternion BKZ. We extend the celebrated LLL algorithm to leverage algebraic properties of quaternion orders and novel post-processing steps to design an LLL algorithm for lattices in not-necessarily-maximal orders. The strategy is to reduce over the Euclidean overlattice and then post-process, giving two routines: one returning a basis of a sublattice with the best bounds, the other a true basis of the original lattice at the cost of output quality. We further consider blocksize two BKZ as a generalisation of the LLL algorithm, and then extend this to arbitrary blocksize; utilising results on the shortness of Gauss and HKZ reduced bases and the relationship of successive minima for our specific sublattice. We then apply these algorithms to ideal lattices arising from nrd-PIP, including those instances given by rank-2 MLIP over cyclotomic fields such as Hawk, via a modification of the canonical embedding that preserves both dimension and quaternionic structure. This allows us to reduce a lattice basis of rank a constant factor of four smaller than the standard real embedding, improving basis bounds and asymptotic complexity in the generic setting.
Last updated:  2026-08-20
Sharp Minimum-Distance Lower Tails for RAA Codes
Majid Khabbazian
Repeat--accumulate--accumulate (RAA) codes are sparse random linear codes with linear-time encoders. Although RAA ensembles can have linear minimum distance with high probability, this does not determine how often a randomly sampled code falls below a prescribed relative-distance threshold. We determine this lower-tail probability and identify the rare mechanisms that dominate it. Let \(n\) be the message length, \(r\ge4\) a fixed repetition factor, and \(N=rn\) the block length. For the randomly scaled ensemble \[ G=R\Pi_1V_1A\Pi_2V_2A, \] where \(R\) is repetition, \(A\) is the prefix-sum accumulator, \(\Pi_1,\Pi_2\) are independent uniform interleavers, and \(V_1,V_2\) have independent uniform nonzero diagonal entries in \(\mathbb F_q\), we prove that, for every fixed \(0<\delta\le1/2\) and \(\gamma>0\), \[ q-1\ge\gamma N \quad\Longrightarrow\quad \mathbb P[d_{\min}(G)\le\delta N] =\Theta_{r,\delta,\gamma}(N^{1-r}). \] For the unscaled ensemble \[ G_0=R\Pi_1A\Pi_2A, \] if \(\operatorname{char}(\mathbb F_q)>r\) and \(0<\delta\le1/10\), then \[ \mathbb P[d_{\min}(G_0)\le\delta N] =\Theta_{r,\delta}(N^{2-r}). \] Thus random scaling improves the failure probability by one power of \(N\). We also prove \[ \mathbb P[d_{\min}(G)\le\delta N] =\Omega_{r,\delta}\!\left( N^{1-\lceil r/2\rceil}(q-1)^{-\lfloor r/2\rfloor} \right), \] showing that linear field growth is necessary, in asymptotic order, for the constant-factor \(N^{1-r}\) law.
Last updated:  2026-08-20
Linear Distance for Fixed-Row-Weight Expand--Accumulate Codes over Arbitrary Fields
Majid Khabbazian
Expand–accumulate (EA) codes are sparse linear codes underlying constructions of correlated pseudorandomness and field-agnostic succinct arguments. In “Field-Agnostic SNARKs from Expand–Accumulate Codes” (CRYPTO 2024), Block et al. conjectured that a single fixed-row-weight EA component already achieves constant relative distance with inverse-polynomial failure probability. We prove this conjecture in a stronger, field-uniform form. For every rate $R\in(0,1)$, there exists $\delta_R>0$ such that, for every target exponent $C>0$, one can choose $\gamma=\gamma(R,C)>0$ for which the fixed-row ensemble with $t=\lceil\gamma\log N\rceil$ satisfies \[ \mathbb{P}\!\left[ \min_{x\in\mathbb{F}_q^{\lfloor RN\rfloor}\setminus\{0\}} \operatorname{wt}(xEA) \le \delta_R N \right] \le N^{-C} \] for all sufficiently large $N$. The same constants work for every prime power $q$; in particular, the field may vary arbitrarily with the block length. Thus, a single fixed-row-weight EA component is asymptotically good over all finite fields, and its polynomial reliability exponent can be made arbitrarily large by increasing the row-weight constant. The proof separates sparse and high-weight messages. Sparse messages are handled through expansion and a compact analysis of accumulator cancellations, while high-weight messages are controlled by a surplus of linear constraints over large fields and a stochastic accumulator analysis over bounded fields. A terminal-boundary obstruction shows that, for $t=\Theta(\log N)$, inverse-polynomial failure is qualitatively optimal.
Last updated:  2026-08-20
Non-interactive Anonymous Tokens with Private Metadata Bit
Foteini Baldimtsi, Lucjan Hanzlik, Quan Nguyen, and Aayush Yadav
Anonymous tokens with private metadata bit (ATPM) have received increased interest as a method for anonymous user authentication while also allowing the issuer to embed trust signals inside the token that are only readable by the authority who holds the secret key. However, all existing ATPM protocols require interaction during issuance as the client must send a blinded request and wait for the issuer to sign, introducing latency and scalability bottlenecks. In this work, we present the first Non-interactive Anonymous Token (NIAT) scheme with a private metadata bit. Our design builds on structure-preserving signatures on equivalence classes (SPS-EQ) and recent advances in non-interactive blind signatures. With NIAT, tokens can be issued without any online interaction, enabling asynchronous pre-computation and drastically reducing issuer workload. We formalize NIAT security definitions, propose an efficient construction under standard assumptions and experimentally evaluate its performance. We also present an extension to our NIAT construction that allows the identification of clients who attempt to double-spend a token (i.e., present the same token twice) and argue that non-interactive schemes are uniquely positioned to offer this essential feature.
Last updated:  2026-08-20
L-BAS: A Lattice-Based Blind Adaptor Signature Scheme
Amin Mohammadali and Riham AlTawy
Lattice-based blind signatures have attracted significant attention in recent years due to the rapid growth of digital currencies, the increasing demand for privacy-preserving digital interactions, and the ongoing transition toward quantum-resistant cryptographic primitives. While blind signatures provide anonymity guarantees, achieving fairness without compromising privacy to a third party remains a challenging problem. Blind adaptor signatures (BAS) address this limitation by enriching blind signatures with conditional-execution functionality, enabling fair exchange while preserving user anonymity. In particular, a BAS scheme allows a user to engage in an atomic swap with a verifier using an adapted blind signature obtained from a signer, thereby maintaining privacy against the signer while ensuring fairness between the user and the verifier. In this work, we observe that the ABDLOP commit-and-prove framework (CRYPTO 2022) exhibits a dichotomic structure that can be leveraged to realize adaptor functionality. Building on this, we propose a lattice-based blind adaptor signature (L-BAS) scheme that simultaneously achieves fairness along with the privacy guarantees of blind signing. Compared with the underlying lattice-based blind signature scheme, our construction incurs only a modest overhead, increasing the signature size by approximately 5.2 KB while largely preserving the efficiency of the original system. We formally analyze the security of the proposed construction and prove that it satisfies extractability, unique extractability, computational pre-verification soundness, one-more unforgeability, and blindness under standard lattice-based assumptions. Our results demonstrate that fairness can be incorporated into lattice-based blind signatures with minimal performance degradation, making the proposed scheme a practical candidate for privacy-preserving and quantum-resistant fair exchange applications.
Last updated:  2026-08-20
Efficient Dynamic Group Signatures with Forward Security
Amin Mohammadali and Riham AlTawy
In dynamic group signature schemes (GSS), forward security ensures that newly joined members cannot generate valid signatures for past time periods. Additionally, non-frameability prevents even privileged entities, such as the group manager or key issuer, from falsely attributing signatures to honest users. Most GSS either lack non-frameability or face significant efficiency challenges when updating signing keys to ensure forward security. In this paper, we introduce a forward-secure dynamic group signature scheme that guarantees non-frameability. We also present an alternative scheme that, while lacking non-frameability, offers higher efficiency compared to existing schemes with comparable security. For both protocols, we propose efficient revocation mechanisms that allow an authority to revoke users without requiring re-registering existing users. Additionally, we propose a technique that enables the verification process of both protocols to be performed in batches. We prove the security of our schemes, ensuring the standard dynamic GSS security notions; anonymity, traceability and non-frameability (second scheme). Experimental results demonstrate that our schemes are competitive in both computational and communication efficiency when compared to existing literature.
Last updated:  2026-08-20
Lattice-Based Updatable KEM for Group Messaging
Joël Alwen, Georg Fuchsbauer, Marta Mularczyk, and Doreen Riepel
Updatable Public-Key Encryption (UPKE) augments the security of PKE with Forward Secrecy properties. While requiring more coordination between parties, UPKE enables much more efficient constructions than full-fledged Forward-Secret PKE. Alwen, Fuchsbauer and Mularczyk (AFM, Eurocrypt’24) presented the strongest security notion to date. It is the first to meet the needs of UPKE’s most important applications: Secure Group Messaging and Continuous Group Key Agreement. The authors provide a very efficient construction of an Updatable Key Encapsulation Mechanism (UKEM), implying UPKE, that satisfies their notion with classic security based on the Computational Diffie-Hellman (CDH) assumption in the Random Oracle Model (ROM). No existing post-quantum UPKE/UKEM construction is known to meet the AFM definition. We present and implement practical secret-key recovery attacks in the AFM adversarial model for all proposed parameter sets of two PQ schemes including the most efficient one to date, due to Abou Haidar, Passelègue and Stehlé (APS, Asiacrypt’23). If the UKEM schemes were used in a real-world group messaging application, the attacks would correspond to realistic execution scenarios, even when targeting a 100% success probability. Next, we present the first post-quantum UKEM construction meeting (a slight relaxation of) the AFM security notion. When based on the Module-LWE assumption, our construction is more efficient than prior PQ constructions, while achieving stronger security. More concretely, public key sizes are about 1/2 that of APS and ciphertext sizes are about 14% smaller. As the AFM security proof relies on random self-reducibility of CDH, which has no analogue for lattices, we develop a new proof technique for strong UKEM, identifying the core properties required from the underlying (lattice-based) encryption scheme.
Last updated:  2026-08-20
Threshold Lattice-Based Zero-Knowledge Proofs
Scott Griffy, Victor Youdom Kemmoe, Ngoc Khanh Nguyen, and Tjerand Silde
Lattice-based zero-knowledge proofs are now efficient enough for practical use, but in all known constructions a single prover holds the entire witness and is therefore a single point of failure. Thresholdizing them is understood only for three-round $\Sigma$-protocols, which certify shortness only $\textit{approximately}$. The $\textit{exact}$ statements needed by applications such as anonymous credentials require more rounds and rely on rejection sampling, and neither property survives thresholdization. We construct the first lattice-based threshold zero-knowledge proof systems for exact relations. The witness is Shamir-shared among $\mathtt{n}$ parties, any $\mathtt{t}$ of them can jointly produce a proof, and the proof has the same form as a single-prover proof, only a factor $\sqrt{\mathtt{t}}$ larger, with verification unchanged. We thresholdize the product proof of Attema, Lyubashevsky, and Seiler (CRYPTO 2020) and the exact proof of Esgin, Nguyen, and Seiler (ASIACRYPT 2020), making both rejection-free using Hint-MLWE and evaluating them over threshold homomorphic encryption. We define threshold commit-and-prove protocols with the corresponding zero-knowledge and simulation-extractability notions, and prove our constructions secure against passive adversaries that statically corrupt at most $\mathtt{t}-1$ parties. Of independent interest, we show that the Fiat--Shamir transforms of both proof systems are simulation-extractable in the random oracle model, and that MLWE remains hard when secrets are drawn from the subring fixed by a ring automorphism.
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.