From Newsgroup: sci.crypt

## In this issue
1. [2025/373] Split Prover Zero-Knowledge SNARKs
2. [2025/440] AI for Code-based Cryptography
3. [2025/869] One for All, All for One: Universal semi-agnostic ...
4. [2025/1305] Barely Doubly-Efficient SimplePIR
5. [2025/1496] Noise-Tolerant Plaintext-Checking Oracle Attacks -- ...
6. [2025/1764] Keccacheck: towards a SNARK friendly Keccak
7. [2025/1765] Untelegraphable Encryption and its Applications
8. [2025/1766] Eliminating Exponential Key Growth in PRG-Based ...
9. [2025/1767] Polylogarithmic Polynomial Commitment Scheme over ...
10. [2025/1768] DualMatrix: Conquering zkSNARK for Large Matrix ...
11. [2025/1769] Average-Case Complexity of Quantum Stabilizer Decoding
12. [2025/1770] On the Security of SL-DNSSEC
13. [2025/1771] Batched & Non-interactive Blind Signatures from ...
14. [2025/1772] Multiple Concurrent Proposers: Why and How
15. [2025/1773] Impossibility of VDFs in the ROM: The Complete Picture
16. [2025/1774] Adaptive-Controlled Mutual TLS for Large Language ...
17. [2025/1775] Homomorphic Encryption Methods Applied to Cloud ...
18. [2025/1777] Optimizing NCC-Sign for ARMv8
19. [2025/1778] Unified Approach to UOV-like Multivariate Signature ...
20. [2025/1779] Computing the Restricted Algebraic Immunity, and ...
21. [2025/1780] There are siblings of $\chi$ which are permutations ...
22. [2025/1781] High-Throughput Universally Composable Threshold ...
23. [2025/1782] On Verifiable Delay Functions from Time-Lock Puzzles
24. [2025/1783] Seedless Condensers for Efficiently Samplable Sources
25. [2025/1784] Pseudorandom Unitaries in the Haar Random Oracle Model
26. [2025/1785] On the Limitations of Pseudorandom Unitaries
27. [2025/1786] Leveraging Discrete CKKS to Bootstrap in High Precision
28. [2025/1787] Four-round Statistical Non-malleable Zero-knowledge
29. [2025/1788] Just Guess: Improved (Quantum) Algorithm for the ...
30. [2025/1789] Olingo: Threshold Lattice Signatures with DKG and ...
31. [2025/1790] CA-MCPQ: A Context-Aware Post-Quantum Protocol for ...
32. [2025/1791] High-Speed 16-Radix Polynomial Multiplication on ...
## 2025/373
* Title: Split Prover Zero-Knowledge SNARKs
* Authors: Sanjam Garg, Aarushi Goel, Dimitris Kolonelos, Sina Shiehian, Rohit Sinha
* [Permalink](https://eprint.iacr.org/2025/373)
* [Download](https://eprint.iacr.org/2025/373.pdf)
### Abstract
We initiate the study of {\em split prover zkSNARKs}, which allow Alice to offload part of the zkSNARK computation to her assistant, Bob. In scenarios like online transactions (e.g., zCash), a significant portion of the witness (e.g., membership proofs of input coins) is often available to the prover (Alice) before the transaction begins. This setup offers an opportunity to Alice to initiate the proof computation early, even before the entire witness is available. The remaining computation can then be delegated to Bob, who can complete it once the final witness (e.g., the transaction amount) is known.
To prevent Bob from generating proofs independently (e.g., initiating unauthorized transactions), it is essential that the data provided to him for the second phase of computation does not reveal the witness used in the first phase. Additionally, the verifier of the zkSNARK should be unable to determine whether the proof was generated solely by Alice or through this two-step process. To achieve this efficiently, we require this two-phase proof generation to only use cryptography in a black-box manner.
We propose a split prover zkSNARK based on the Groth16 zkSNARKs [Groth, EUROCRYPT 2016], meeting all these requirements. Our solution is also \emph{asymptotically tight}, meaning it achieves the optimal second phase proof generation time for Groth16. Importantly, our split prover zkSNARK preserves the verification algorithm of the original Groth16 zkSNARK, enabling seamless integration into existing deployments of Groth16.
## 2025/440
* Title: AI for Code-based Cryptography
* Authors: Mohamed Malhou, Ludovic Perret, Kristin Lauter
* [Permalink](https://eprint.iacr.org/2025/440)
* [Download](https://eprint.iacr.org/2025/440.pdf)
### Abstract
We introduce the use of machine learning in the cryptanalysis of code-based cryptography. Our focus is on distinguishing problems related to the security of NIST round-4 McEliece-like cryptosystems, particularly for Goppa codes used in ClassicMcEliece and Quasi-Cyclic Moderate Density Parity-Check (QC-MDPC) codes used in BIKE. We present DeepDistinguisher, a new algorithm for distinguishing structured codes from random linear codes that uses a transformer. The results show that the new distinguisher achieves a high level of accuracy in distinguishing Goppa codes, suggesting that their structure may be more recognizable by AI models. Our approach outperforms traditional attacks in distinguishing Goppa codes in certain settings and does generalize to larger code lengths without further training using a puncturing technique. We also present the first distinguishing results dedicated to MDPC and QC-MDPC codes.
## 2025/869
* Title: One for All, All for One: Universal semi-agnostic quantum circuit for solving (Standard) Abelian Hidden Subgroup Problems
* Authors: Micha+e Wro+aski, +Uukasz Dzierzkowski, Mateusz Le+cniak, Ewa Syta
* [Permalink](https://eprint.iacr.org/2025/869)
* [Download](https://eprint.iacr.org/2025/869.pdf)
### Abstract
Quantum algorithms for factoring, finite-field discrete logarithms (DLP), and elliptic-curve discrete logarithms (ECDLP) are usually presented as three separate attack pipelines, even though all three are instances of the Abelian Hidden Subgroup Problem (AHSP).
We prove that the semi-agnostic elliptic-curve discrete logarithm problem (semi-agnostic ECDLP), defined on smooth elliptic curves, singular nodal cubics, and over rings such as $\mathbb{Z}_N$, is complete for all standard abelian hidden subgroup problems (SAHSPs). In other words, factoring, finite-field DLP, and ECDLP all reduce to semi-agnostic ECDLP. This gives the first completeness theorem for the cryptographic subclass of HSP.
To argue minimality from the practical point of view (for example, the minimal size of Shor's circuit implementation), we formalize the No Efficient Injective Homomorphism (NEIH) hypothesis: no generic polynomial-time injective homomorphism exists from elliptic curve subgroups into small cyclic groups. NEIH is strongly supported by three provable limitations:
(i) the embedding-degree barrier,
(ii) an algebraic rigidity lemma, and
(iii) a generic-group model barrier, ruling out non-algebraic embeddings without already solving the ECDLP.
The completeness result has practical implications, as it identifies a minimal universal Shor engine: a single, programmable Weierstrass circuit that implements reversible field arithmetic and point addition on a smooth or nodal Weierstrass model. This one circuit instance suffices to execute Shor's algorithm for factoring, finite-field DLP, and ECDLP without recompilation and with the same asymptotic resources as specialized designs.
## 2025/1305
* Title: Barely Doubly-Efficient SimplePIR
* Authors: Keewoo Lee
* [Permalink](https://eprint.iacr.org/2025/1305)
* [Download](https://eprint.iacr.org/2025/1305.pdf)
### Abstract
A Private Information Retrieval (PIR) scheme allows a client to retrieve data from a database hosted on a remote server without revealing which location is being accessed. In Doubly-Efficient PIR (DEPIR), the server preprocesses the database offline into a data structure that enables it to answer any client query in sublinear time with respect to the database size $N$. The breakthrough work of Lin-Mook-Wichs (STOCrCO23) presented the first DEPIR construction from the Ring-LWE assumption. This remains essentially the only known construction to date, and realizing DEPIR from alternative foundations, particularly from plain LWE, has remained elusive.
In this work, we present a simple LWE-based construction of DEPIR in the CRS model. Our construction is inspired by SimplePIR (USENIXrCO23) and leverages the matrixrCovector multiplication preprocessing of Williams (SODArCO07). While our construction is only barely doubly-efficient, with server computation of $O(N / \log{N})$, it was previously unknown whether even such modest sublinear efficiency could be achieved from unstructured, plain LWE.
## 2025/1496
* Title: Noise-Tolerant Plaintext-Checking Oracle Attacks -- A Soft-Analytic Approach Applied to ML-KEM
* Authors: Julius Hermelink, Erik M|Nrtensson, Maggie Tran
* [Permalink](https://eprint.iacr.org/2025/1496)
* [Download](https://eprint.iacr.org/2025/1496.pdf)
### Abstract
Plaintext-checking (PC) oracle attacks are among the most prominent types of attacks against NIST's recently standardized ML-KEM. Previous works have drastically reduced the number of queries needed to recover the secret key. Although this number is now close to the information-theoretic bound, current attacks have not yet been adapted to settings with increased noise and highly imperfect oracles. In attacks targeting real-world protected implementations, noisy leakage may lead to oracles that only provide a small advantage over guessing.
This work shows how to efficiently exploit imperfect oracles arising from highly noisy side channels. We present several soft-analytic techniques that enable highly noise-tolerant parallel PC-oracle attacks. These techniques allow for successful attacks in relatively few traces from information that gives just a slight advantage over guessing. Additionally, we extend the generic framework for side-channel information from Eurocrypt 2025 and thereby relate our techniques to previous work.

We then discuss several oracle instantiations that are based on the noisy Hamming weight model. These oracles rely on widely accepted assumptions, are easy to simulate, and allow for fair comparisons between different attacks. Furthermore, they allow countermeasures to be taken into account, and we evaluate the impact of masking. Our evaluations in these and previous models show that PC-oracle attacks are noise-tolerant on an entirely different scale compared to previous work. These improvements are of an algorithmic nature and orthogonal to the fact that the Fujisaki-Okamoto transform in ML-KEM offers a large attack surface. Finally, we discuss the implications of our findings for protected ML-KEM implementations.
## 2025/1764
* Title: Keccacheck: towards a SNARK friendly Keccak
* Authors: Marcin Kostrzewa, Matthew Klein, Ara Adkins, Grzegorz +Uwirski, Wojciech ++muda
* [Permalink](https://eprint.iacr.org/2025/1764)
* [Download](https://eprint.iacr.org/2025/1764.pdf)
### Abstract
Keccak, the hash function at the core of the Ethereum ecosystem, is computationally expensive to reason about in SNARK circuits, creating a critical bottleneck in the ability of the ZK ecosystem to reason about blockchain state. The recent state-of-the-art in proving Keccak permutations relies on proof systems that can perform lookup arguments, whichrCowhile exhibiting better performance than directly proving the hash operations in circuitrCostill typically require tens of thousands of constraints to prove a single keccak-f permutation.
This paper introduces a new method, termed keccacheck, which builds upon sum-check with influence from GKR to create circuits that can batch-verify Keccak permutations with fewer than 4000 constraints per instance. Keccacheck achieves this by exploiting the logarithmic scaling of recursive verification of the sum-check protocol, reducing the computational cost of verifying large enough batches to be only slightly higher than evaluating the multilinear extension of the input and output states. Its performance becomes competitive for a batch containing 16 permutations and offers more than a 10x cost reduction for batches of 512 or more permutations. This approach enables new levels of efficiency for the ZK ecosystem, providing the performant storage proofs that are essential to light clients, cross-chain bridges, privacy-focused protocols, and roll-ups.
## 2025/1765
* Title: Untelegraphable Encryption and its Applications
* Authors: Jeffrey Champion, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2025/1765)
* [Download](https://eprint.iacr.org/2025/1765.pdf)
### Abstract
We initiate the study of untelegraphable encryption (UTE), founded on the no-telegraphing principle, which allows an encryptor to encrypt a message such that a binary string representation of the ciphertext cannot be decrypted by a user with the secret key, a task that is classically impossible. This is a natural relaxation of unclonable encryption (UE), inspired by the recent work of Nehoran and Zhandry (ITCS 2024), who showed a computational separation between the no-cloning and no-telegraphing principles.
In this work, we define and construct UTE information-theoretically in the plain model. Building off this, we give several applications of UTE and study the interplay of UTE with UE and well-studied tasks in quantum state learning, yielding the following contributions:
- A construction of collusion-resistant UTE from standard secret-key encryption (SKE). We additionally show that hyper-efficient shadow tomography (HEST) is impossible assuming collusion-resistant UTE exists. By considering a relaxation of collusion-resistant UTE, we are able to show the impossibility of HEST assuming only pseudorandom state generators (which may not imply one-way functions). This almost unconditionally answers an open inquiry of Aaronson (STOC 2018).
- A construction of UTE from a quasi-polynomially secure one-shot message authentication code (OSMAC) in the classical oracle model, such that there is an explicit attack that breaks UE security for an unbounded polynomial number of decryptors.
- A construction of everlasting secure collusion-resistant UTE, where the decryptor adversary can run in unbounded time, in the quantum random oracle model (QROM), and formal evidence that a construction in the plain model is a challenging task. We additionally show that HEST with unbounded post-processing time (which we call weakly-efficient shadow tomography) is impossible assuming everlasting secure collusion-resistant UTE exists.

- A construction of secret sharing for all polynomial-size policies that is resilient to joint and unbounded classical leakage from collusion-resistant UTE and classical secret sharing for all policies.

- A construction (and definition) of collusion-resistant untelegraphable secret-key functional encryption (UTSKFE) from single-decryptor functional encryption and plain secret-key functional encryption, and a construction of collusion-resistant untelegraphable public-key functional encryption from UTSKFE, plain SKE, and plain public-key functional encryption.
## 2025/1766
* Title: Eliminating Exponential Key Growth in PRG-Based Distributed Point Functions
* Authors: Marc Damie, Florian Hahn, Andreas Peter, Jan Ramon
* [Permalink](https://eprint.iacr.org/2025/1766)
* [Download](https://eprint.iacr.org/2025/1766.pdf)
### Abstract
Distributed Point Functions (DPFs) enable sharing secret point functions across multiple parties, supporting privacy-preserving technologies such as Private Information Retrieval, and anonymous communications. While 2-party PRG-based schemes with logarithmic key sizes have been known for a decade, extending these solutions to multi-party settings has proven challenging. In particular, PRG-based multi-party DPFs have historically struggled with practicality due to key sizes growing exponentially with the number of parties and the field size.
Our work addresses this efficiency bottleneck by optimizing the PRG-based multi-party DPF scheme of Boyle et al. (EUROCRYPT'15). By leveraging the honest-majority assumption, we eliminate the exponential factor present in this scheme. Our construction is the first PRG-based multi-party DPF scheme with practical key sizes, and provides key up to $3\times$ smaller than the best known multi-party DPF. This work demonstrates that with careful optimization, PRG-based multi-party DPFs can achieve practical performances, and even obtain top performances.
## 2025/1767
* Title: Polylogarithmic Polynomial Commitment Scheme over Galois Rings
* Authors: Zhuo Wu, Xinxuan Zhang, Yi Deng, Yuanju Wei, Zhongliang Zhang, Liuyu Yang
* [Permalink](https://eprint.iacr.org/2025/1767)
* [Download](https://eprint.iacr.org/2025/1767.pdf)
### Abstract
This paper introduces the first multilinear polynomial commitment scheme (PCS) over Galois rings achieving $\bigO{\log^2 n}$ verification cost. It achieves $\bigO{n\log n}$ committing time and $\bigO{n}$ evaluation opening prover time. This PCS can be used to construct zero-knowledge proofs for arithmetic circuits over Galois rings, facilitating verifiable computation in applications requiring proofs of polynomial ring operations (e.g., verifiable fully homomorphic encryption). First we construct random foldable linear codes over Galois rings with sufficient code distance and present a distance preservation theorem over Galois rings. Second we extend the $\textsf{Basefold}$ commitment (Zeilberger et al., Crypto 2024) to multilinear polynomials over Galois rings. Our approach reduces proof size and verifier time from $\bigO{\sqrt{n}}$ to $\bigO{\log^2 n}$ compared to Wei et al., PKC 2025. Furthermore, we give a batched multipoint openning protocol for evaluation phase that collapses the proof size and verifier time of $N$ polynomials at $M$ points from $\bigO{NM \log^2 n}$ to $\bigO{\log^2 n}$, prover time from $\bigO{NMn}$ to $\bigO{n}$, further enhancing efficiency.
## 2025/1768
* Title: DualMatrix: Conquering zkSNARK for Large Matrix Multiplication
* Authors: Mingshu Cong, Tsz Hon Yuen, Siu-Ming Yiu
* [Permalink](https://eprint.iacr.org/2025/1768)
* [Download](https://eprint.iacr.org/2025/1768.pdf)
### Abstract
We present DualMatrix, a zkSNARK solution for large-scale matrix multiplication. Classical zkSNARK protocols typically underperform in data analytic contexts, hampered by the large size of datasets and the superlinear nature of matrix multiplication. DualMatrix excels in its scalability. The prover time of DualMatrix scales linearly with respect to the number of non-zero elements in the input matrices. For $n \times n$ matrix multiplication with $N$ non-zero elements across three input matrices, DualMatrix employs a structured reference string (SRS) of size $O(n)$, and achieves RAM usage of $O(N+n)$, transcript size of $O(\log n)$, prover time of $O(N+n)$, and verifier time of $O(\log n)$. The prover time, notably at $O(N+n)$ and surpassing all existing protocols, includes $O(N+n)$ field multiplications and $O(n)$ exponentiations and pairings within bilinear groups. These efficiencies make DualMatrix effective for linear algebra on large matrices common in real-world applications. We evaluated DualMatrix with $2^{15} \times 2^{15}$ input matrices each containing $1G$ non-zero integers, which necessitate $32T$ integer multiplications in naive matrix multiplication. DualMatrix recorded prover and verifier times of $150.84$s and $0.56$s, respectively. When applied to $1M \times 1M$ sparse matrices each containing $1G$ non-zero integers, it demonstrated prover and verifier times of $1,384.45$s and $0.67$s. Our approach outperforms current zkSNARK solutions by successfully handling the large matrix multiplication task in experiment. We extend matrix operations from field matrices to group matrices, formalizing group matrix algebra. This mathematical advancement brings notable symmetries beneficial for high-dimensional elliptic curve cryptography. By leveraging the bilinear properties of our group matrix algebra in the context of the two-tier commitment scheme, DualMatrix achieves efficiency gains over previous matrix multiplication arguments. To accomplish this, we extend and enhance Bulletproofs to construct an inner product argument featuring a transparent setup and logarithmic verifier time.
## 2025/1769
* Title: Average-Case Complexity of Quantum Stabilizer Decoding
* Authors: Andrey Boris Khesin, Jonathan Z. Lu, Alexander Poremba, Akshar Ramkumar, Vinod Vaikuntanathan
* [Permalink](https://eprint.iacr.org/2025/1769)
* [Download](https://eprint.iacr.org/2025/1769.pdf)
### Abstract
Random classical linear codes are widely believed to be hard to decode.
While slightly sub-exponential time algorithms exist when the coding rate vanishes sufficiently rapidly, all known algorithms at constant rate require exponential time. By contrast, the complexity of decoding a random quantum stabilizer code has remained an open question for quite some time. This work closes the gap in our understanding of the algorithmic hardness of decoding random quantum versus random classical codes. We prove that decoding a random stabilizer code with even a single logical qubit is at least as hard as decoding a random classical code at constant raterCothe maximally hard regime. This result suggests that the easiest random quantum decoding problem is at least as hard as the hardest random classical decoding problem, and shows that any sub-exponential algorithm decoding a typical stabilizer code, at any rate, would immediately imply a breakthrough in cryptography.
More generally, we also characterize many other complexity-theoretic properties of stabilizer codes. While classical decoding admits a random self-reduction, we prove significant barriers for the existence of random self-reductions in the quantum case. This result follows from new bounds on Clifford entropies and Pauli mixing times, which may be of independent interest. As a complementary result, we demonstrate various other self-reductions which are in fact achievable, such as between search and decision. We also demonstrate several ways in which quantum phenomena, such as quantum degeneracy, force several reasonable definitions of stabilizer decodingrCoall of which are classically identicalrCoto have distinct or non-trivially equivalent complexity.
## 2025/1770
* Title: On the Security of SL-DNSSEC
* Authors: Aditya Singh Rawat, Mahabir Prasad Jhanwar
* [Permalink](https://eprint.iacr.org/2025/1770)
* [Download](https://eprint.iacr.org/2025/1770.pdf)
### Abstract
The proposed $\mathsf{SL\text{-}DNSSEC}$ protocol (AsiaCCS'25) uses a quantum-safe KEM and a MAC to perform signature-less $\mathsf{(SL)}$ DNSSEC validations in a single UDP query / response style. In this paper, we give a formal analysis of $\mathsf{SL\text{-}DNSSEC}$ in the reductionist model.
## 2025/1771
* Title: Batched & Non-interactive Blind Signatures from Lattices
* Authors: Foteini Baldimtsi, Rishab Goyal, Aayush Yadav
* [Permalink](https://eprint.iacr.org/2025/1771)
* [Download](https://eprint.iacr.org/2025/1771.pdf)
### Abstract
Non-interactive blind signatures (NIBS; Eurocrypt '23) allow a signer to asynchronously generate presignatures for a recipient, ensuring that only the intended recipient can extract a "blinded" signature for a random message.
We introduce a new generalization called non-interactive batched blind signatures (NIBBS). Our goal is to reduce the computation and communication costs for signers and receivers, by batching multiple blind signature queries. More precisely, we define the property of 'succinct communication' which requires that the communication cost from signer to receiver be independent of the batch size. NIBBS is very suitable for large-scale deployments requiring only minimal signer-side effort.
We design a NIBBS scheme and prove its security based on the hardness of lattice assumptions (in the random oracle model). When instantiated with the low-depth PRF candidate "Crypto Dark Matter" (TCC '18) and the succinct lattice-based proof system for rank-1 constraint systems (Crypto '23), our final signature size is 308 KB with <1 KB communication.
## 2025/1772
* Title: Multiple Concurrent Proposers: Why and How
* Authors: Pranav Garimidi, Joachim Neu, Max Resnick
* [Permalink](https://eprint.iacr.org/2025/1772)
* [Download](https://eprint.iacr.org/2025/1772.pdf)
### Abstract
Traditional single-proposer blockchains suffer from miner extractable value (MEV), where validators exploit their serial monopoly on transaction inclusion and ordering to extract rents from users. While there have been many developments at the application layer to reduce the impact of MEV, these approaches largely require auctions as a subcomponent. Running auctions efficiently on chain requires two key properties of the underlying consensus protocol: selective-censorship resistance and hiding. These properties guarantee that an adversary can neither selectively delay transactions nor see their contents before they are confirmed. We propose a multiple concurrent proposer (MCP) protocol offering exactly these properties.
## 2025/1773
* Title: Impossibility of VDFs in the ROM: The Complete Picture
* Authors: Hamza Abusalah, Karen Azari, Chethan Kamath, Erkan Tairi, Maximilian von Consbruch
* [Permalink](https://eprint.iacr.org/2025/1773)
* [Download](https://eprint.iacr.org/2025/1773.pdf)
### Abstract
This paper is concerned with the question whether Verifiable Delay Functions (VDFs), as introduced by Boneh et al. [CRYPTO 2018], can be constructed in the plain Random Oracle Model (ROM) without any computational assumptions. A first partial answer to this question is due to Mahmoody, Smith, and Wu [ICALP 2020], and rules out the existence of perfectly unique VDFs in the ROM. Building on this result, Guan, Riazanov, and Yuan [CRYPTO 2025] very recently demonstrated that even VDFs with computational uniqueness are impossible under a public-coin setup. However, the case of computationally unique VDFs with private-coin setup remained open. We close this gap by showing that even computationally expensive private-coin setup will not allow to construct VDFs in the ROM.
## 2025/1774
* Title: Adaptive-Controlled Mutual TLS for Large Language Model Systems
* Authors: Lui Zheng, Roger Zhu, Amit Agrawal, Carol Lamore
* [Permalink](https://eprint.iacr.org/2025/1774)
* [Download](https://eprint.iacr.org/2025/1774.pdf)
### Abstract
Mutual Transport Layer Security (mTLS) under- pins authenticated, confidential communication across modern service meshes, but its deployment stance in machine-learning platforms is typically staticrCofixed cipher suites, certificate life- times, and re-authentication schedules chosen for worst-case threats rather than observed risk. Large Language Model (LLM) serving pipelines exacerbate this rigidity: traffic is bursty, topolo- gies reconfigure dynamically under autoscaling, and sensitive artifacts such as prompts, training features, and evaluation data traverse heterogeneous substrates. In this paper we argue that mTLS for LLM systems[1] should be governed by adaptive control rather than static policy. We formalize a feedback loop that ingests multi-modal telemetryrCoconnection error codes, handshake latencies, anomaly scores from request semantics, workload attestation freshness, and service-level objective (SLO) driftrCoand outputs fine-grained adjustments to transport posture: client-certificate renewal cadence, certificate path length and key type selection, session resumption eligibility, early data gat- ing, proof-of-possession challenges, and revocation propagation thresholds. The controller targets two coupled objectives: maintain cryptographic assurances (mutual authentication, forward secrecy, and replay resistance) while bounding the cost of security on tail latency and throughput during high-load inference.
## 2025/1775
* Title: Homomorphic Encryption Methods Applied to Cloud Computing: A Practical Architecture for Elastic, Verifiable Confidential Compute
* Authors: Rama Yadavalli, Jeffery Solomon, Vrinda Sharma
* [Permalink](https://eprint.iacr.org/2025/1775)
* [Download](https://eprint.iacr.org/2025/1775.pdf)
### Abstract
Cloud computing has matured into the default substrate for data processing, yet confidentiality demands of- ten force a hard trade-off between the utility of outsourced computation and the privacy of sensitive inputs. Homomorphic encryption (HE)[1] promises to dissolve that trade-off by enabling computation directly on ciphertexts, returning encrypted results that only the data owner can decrypt. Despite remarkable progress in fully homomorphic encryption (FHE) and leveled variants suitable for bounded-depth circuits, deploying HE at cloud scale remains challenging. The cost of ciphertext arithmetic is orders of magnitude higher than plaintext compute; noise growth and rescaling impose algorithmic discipline; vectorization and rotation keys complicate program layout; and the lack of verifiability in bare HE obliges trust in a correct-but-curious cloud[?]. This paper develops a system perspective on how to apply modern HE in cloud environments without reducing it to a boutique feature. We introduce a reference architecture that marries approximate-arithmetic HE for analytics with exact- arithmetic HE for integrity-critical operations, composes HE with succinct proofs for verifiability, and integrates a cost model into the scheduler so that elastically provisioned serverless workers can meet latency objectives under price constraints. The design begins with a compiler that lowers dataflow graphs to operator sequences parameterized by multiplicative depth L and rotation sets; it then chooses schemes and parametersrCoCKKS for floating-point style analytics and signal processing, BFV/BGV for integer operations and counters, TFHE-style bootstrapping for comparisonsrCothat minimize the total time-to-result under explicit error and security budgets. A cryptographic key service supports threshold issuance and rotation-key escrow without learning plaintexts, while a storage layer packs columns into ciphertext SIMD lanes to amortize cost across tenants. For verifiability, we attach homomorphic message authentication tags to intermediate ciphertexts and wrap end-to-end executions in succinct non-interactive proofs specialized to the bilinear equations that certify correct key switching, rescaling, and boot- strapping. Analytically, we characterize latency by a linear model in the counts of core homomorphic primitives and show how to saturate GPUs or vector units with batched number-theoretic transforms to bend throughput toward practical regimes. Under realistic traces of analytic queries and encrypted inference, the architecture achieves sub-second P95 for circuits of depth six to eight with one or two bootstraps, while sustaining 128-bit security under RLWE. By treating HE not as an exotic afterthought but as a first-class cloud programming and scheduling primitive, the proposed approach demonstrates a path to confidential-by- default services in which the cloud never sees data in the clear
yet remains efficient, elastic, and auditable.
## 2025/1777
* Title: Optimizing NCC-Sign for ARMv8
* Authors: Minwoo Lee, Minjoo Sim, Siwoo Eum, Gyeongju Song, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2025/1777)
* [Download](https://eprint.iacr.org/2025/1777.pdf)
### Abstract
This paper presents an ARMv8/NEONrCooriented, constant-time implementation of NCC-Sign and a careful head-to-head evaluation against a clean KPQClean baseline on Apple~M2. We design lane-local SIMD kernels (e.g., a 4-lane Montgomery multiply--reduce, centered modular reduction, fused stage-0 butterfly, and streamlined radix-2/3 pipelines) that minimize cross-lane shuffles and keep memory access streaming. Using a reproducible harness with PMU-based cycle counting and identical toolchains for baseline and optimized builds, we observe consistent end-to-end gains across all parameter sets: geometric-mean speedups of \textbf{1.22$\times$} for key generation, \textbf{1.58$\times$} for signing, and \textbf{1.50$\times$} for verification, yielding an overall \textbf{1.42$\times$} improvement over NCC-Sign-1/3/5. The largest benefits appear in NTT-intensive signing/verification, and absolute savings scale with parameter size.
## 2025/1778
* Title: Unified Approach to UOV-like Multivariate Signature Schemes
* Authors: Peigen Li, Hao Guo, Jintai Ding
* [Permalink](https://eprint.iacr.org/2025/1778)
* [Download](https://eprint.iacr.org/2025/1778.pdf)
### Abstract
This article develops a unified framework for analyzing and enhancing a family of multivariate signature schemes based on UOV. We conduct a comparative study of three recent UOV-like schemesrCoQR-UOV, MAYO, and SNOVArCoand identify a common design principle: employing tensor product constructions to enlarge the dimension of the oil subspace. Building on this perspective, we propose a new multivariate signature scheme called TSUOV that synthesizes these insights to provide improved key and signature sizes without compromising security.
## 2025/1779
* Title: Computing the Restricted Algebraic Immunity, and Application to Weightwise Perfectly Balanced Functions.
* Authors: Luca Bonamino, Pierrick M|-aux
* [Permalink](https://eprint.iacr.org/2025/1779)
* [Download](https://eprint.iacr.org/2025/1779.pdf)
### Abstract
Algebraic Immunity (AI) is a fundamental property in the security analysis of stream ciphers and Boolean functions, measuring the resistance of a function against algebraic attacks. In this work, we focus on the computation of AI and, more specifically, on its generalization to restricted algebraic immunity, which considers annihilators constrained to specific subsets of $\mathbb{F}_2^n$. While the computation of AI has been studied using methods based on Reed-Muller codes and iterative rank-based algorithms, these approaches have not been formally adapted to the restricted setting. We address this gap by establishing the theoretical foundations required for the adaptation of these techniques and providing explicit algorithms for computing restricted algebraic immunity.
To assess the efficiency of our algorithms, we conduct practical experiments comparing the computational cost of the Reed-Muller and iterative approaches in terms of time and memory. As a case study, we analyze the algebraic immunity restricted to the slices of $\mathbb{F}_2^n$, i.e. the sets of binary vectors of fixed Hamming weight, denoted $\mathsf{AI}_k$. The slices are of particular interest in areas of cryptography, such as side-channel analysis and stream cipher design, where the input weight may be partially predictable. We further investigate restricted algebraic immunity for Weightwise (Almost) Perfectly Balanced (W(A)PB) functions, which have been extensively studied since $2017$. Our results include an empirical analysis of $\mathsf{AI}_k$ distributions for WPB functions with $4$, $8$, and $16$ variables, as well as an evaluation of $\mathsf{AI}_k$ for various known function families.
## 2025/1780
* Title: There are siblings of $\chi$ which are permutations for $n$ even
* Authors: Bj||rn Kriepke, Gohar Kyureghyan
* [Permalink](https://eprint.iacr.org/2025/1780)
* [Download](https://eprint.iacr.org/2025/1780.pdf)
### Abstract
Let $1$ be the all-one vector and $\odot$ denote the component-wise multiplication of two vectors in $\mathbb F_2^n$. We study the vector space $\Gamma_n$ over $\mathbb F_2$ generated by the functions $\gamma_{2k}:\mathbb
F_2^n \to \mathbb F_2^n, k\geq 0$, where $$ \gamma_{2k} = S^{2k}\odot(1+S^{2k-1})\odot(1+S^{2k-3})\odot\ldots\odot(1+S) $$ and $S:\mathbb F_2^n\to\mathbb F_2^n$ is the cyclic left shift function. The functions in $\Gamma_n$ are shift-invariant and the well known $\chi$ function used in several cryptographic primitives is contained in $ \Gamma_n$. For even $n$, we show that the permutations from $\Gamma_n$ with respect to composition form an Abelian group, which is isomorphic to the unit group of the residue ring $\mathbb F_2[X]/(X^n+X^{n/2})$. This isomorphism yields an efficient theoretic and algorithmic method for constructing and studying a rich family of shift-invariant permutations on $\mathbb F_2^n$ which are natural generalizations of $\chi$. To demonstrate it, we apply the obtained results to investigate the function $\gamma_0 +\gamma_2+\gamma_4$ on $\mathbb F_2^n$.
## 2025/1781
* Title: High-Throughput Universally Composable Threshold FHE Decryption
* Authors: Guy Zyskind, Doron Zarchy, Max Leibovich, Chris Peikert
* [Permalink](https://eprint.iacr.org/2025/1781)
* [Download](https://eprint.iacr.org/2025/1781.pdf)
### Abstract
Threshold Fully Homomorphic Encryption (FHE) enables arbitrary computation on encrypted data, while distributing the decryption capability across multiple parties. A primary application of interest is low-communication multi-party computation (MPC), which benefits from a fast and secure threshold FHE decryption protocol.
Several works have addressed this problem, but all existing solutions rely on "noise flooding" for security. This incurs significant overhead and necessitates large parameters in practice, making it unsuitable for many real-world deployments. Some constructions have somewhat better efficiency, but at the cost of weaker, non-simulation-based security definitions, which limits their usability and composability.
In this work, we propose a novel threshold FHE decryption protocol that avoids "noise flooding" altogether, and provides simulation-based security. Rather than masking the underlying ciphertext noise, our technique securely removes it via an efficient MPC rounding procedure. The cost of this MPC is mitigated by an offline/online design that preprocesses special gates for secure comparisons in the offline phase, and has low communication and computation in the online phase. This approach is of independent interest, and should also benefit other MPC protocols (e.g., secure machine learning) that make heavy use of non-linear comparison operations.
We prove our protocol secure in the Universal Composability (UC) framework, and it can be generally instantiated for a variety of adversary models (e.g., security-with-abort against a dishonest majority, or guaranteed output delivery with honest majority). Compared to the state of the art, our protocol offers significant gains both in the adversary model (i.e., dishonest vs. honest majority) and practical performance: empirically, our online phase obtains approximately 20,000$\times$ better throughput, and up to a 37$\times$ improvement in latency.
## 2025/1782
* Title: On Verifiable Delay Functions from Time-Lock Puzzles
* Authors: Hamza Abusalah, Karen Azari, Dario Fiore, Chethan Kamath, Erkan Tairi
* [Permalink](https://eprint.iacr.org/2025/1782)
* [Download](https://eprint.iacr.org/2025/1782.pdf)
### Abstract
A verifiable delay function (VDF) [Boneh et al., CRYPTO 2018] is a function $f$ that is slow-to-compute, but is quickly verifiable given a short proof. This is formalised using two security requirements: i) sequentiality, which requires that a parallel adversary is unable to compute $f$ faster; and ii) soundness, which requires that an adversary is unable to generate a proof that verifies wrong outputs. A time-lock puzzle (TLP), on the other hand, is a puzzle that can be quickly generated, but is slow-to-solve. The security requirement here is sequentiality, which requires that a parallel adversary is unable to solve puzzles faster.
In this paper, we study the relationship between these two timed primitives. Our main result is a construction of ``one-time'' VDF from TLP using indistinguishability obfuscation (iO) and one-way functions (OWFs), where by ``one-time'' we mean that sequentiality of the VDF holds only against parallel adversaries that do not preprocess public parameters. Our VDF satisfies several desirable properties. For instance, we achieve perfectly sound and short proofs of $O(\lambda)$ bits, where $\lambda$ is the security parameter. Moreover, our construction is a trapdoor (one-time) VDF that can be easily extended to achieve interesting extra properties (defined in our paper) such as trapdoor-homomorphic and trapdoor-constrained evaluation.
Finally, when combined with the results of Bitansky et al., [ITCS 2016], this yields one-time VDFs from any worst-case non-parallelizing language, iO and OWF. To the best of our knowledge, this is the first such construction that only relies on polynomial security.
## 2025/1783
* Title: Seedless Condensers for Efficiently Samplable Sources
* Authors: Cody Freitag, Jad Silbak, Daniel Wichs
* [Permalink](https://eprint.iacr.org/2025/1783)
* [Download](https://eprint.iacr.org/2025/1783.pdf)
### Abstract
Is it possible to efficiently convert any arbitrary source with sufficiently high (min-)entropy into nearly uniformly random bits? Information-theoretically, this is achievable using seeded extractors, provided the source is independent of the seed. However, in the absence of any such independence guarantee, no solution is possible for general computationally unbounded sources. Even for efficiently samplable sources, we cannot extract randomness that is statistically close to uniform, but can at best condense the randomness into an output that is only missing logarithmically many bits of entropy compared to the uniform distribution. Dodis, Ristenpart and Vadhan (TCC '12) constructed such seeded condensers for efficiently samplable sources that can depend arbitrarily on the seed assuming near-optimal security of collision-resistant hash functions. In this work, we investigate whether such condensers can be made seedless. We present several new results:
-- We construct seedless condensers for all efficiently samplable sources assuming near-optimal security of keyless multi-collision resistant hash functions. We justify this assumption by showing it holds in the auxiliary-input random oracle model.
-- We show that such seedless condensers cannot be proven secure via a black-box reduction from any standard game-based assumption, even if we assume optimal exact security. In fact, we give a general black-box separation that applies to a broad class of seedless primitives, with seedless condensers as a special case.
-- We consider the class of efficiently samplable distributed sources where two parties jointly sample randomness $x=(x_0,x_1)$, with one party honestly choosing $x_b$ uniformly at random while the other party adversarially chooses $x_{1-b}$ depending on $x_b$. We show how to construct seedless condensers for such sources assuming near-optimal security of game-based assumptions -- either: (1) adaptive one-way functions, or (2) a certain from of (single-input) correlation-intractable hash functions that can be instantiated from key-dependent-message (KDM) secure encryption.
## 2025/1784
* Title: Pseudorandom Unitaries in the Haar Random Oracle Model
* Authors: Prabhanjan Ananth, John Bostanci, Aditya Gulati, Yao-Ting Lin
* [Permalink](https://eprint.iacr.org/2025/1784)
* [Download](https://eprint.iacr.org/2025/1784.pdf)
### Abstract
The quantum Haar random oracle model is an idealized model where every party has access to a single Haar random unitary and its inverse. We construct strong pseudorandom unitaries in the quantum Haar random oracle model. This strictly improves upon prior works who either only prove the existence of pseudorandom unitaries in the inverseless quantum Haar random oracle model [Ananth, Bostanci, Gulati, Lin, EUROCRYPT 2025] or prove the existence of a weaker notion (implied by strong pseudorandom unitaries) in the quantum Haar random oracle model [Hhan, Yamada, 2024]. Our results also present a viable approach for building quantum pseudorandomness from random quantum circuits and analyzing pseudorandom objects in nature.
## 2025/1785
* Title: On the Limitations of Pseudorandom Unitaries
* Authors: Prabhanjan Ananth, Aditya Gulati, Yao-Ting Lin
* [Permalink](https://eprint.iacr.org/2025/1785)
* [Download](https://eprint.iacr.org/2025/1785.pdf)
### Abstract
Pseudorandom unitaries (PRUs), one of the key quantum pseudorandom notions, are efficiently computable unitaries that are computationally indistinguishable from Haar random unitaries. While there is evidence to believe that PRUs are weaker than one-way functions, so far its relationship with other quantum cryptographic primitives (that are plausibly weaker than one-way functions) has not been fully established.
In this work, we focus on quantum cryptographic primitives with classical communication, referred to as QCCC primitives. Our main result shows that QCCC bit commitments and QCCC key agreement, cannot be constructed from pseudorandom unitaries in a black-box manner.
Our core technical contribution is to show (in a variety of settings) the difficulty of distinguishing identical versus independent Haar unitaries by separable channels. Our result strictly improves upon prior works which studied similar problems in the context of learning theory [Anshu, Landau, Liu, STOC 2022] and cryptography [Ananth, Gulati, Lin, TCC 2024].
## 2025/1786
* Title: Leveraging Discrete CKKS to Bootstrap in High Precision
* Authors: Hyeongmin Choe, Jaehyung Kim, Damien Stehl|-, Elias Suvanto
* [Permalink](https://eprint.iacr.org/2025/1786)
* [Download](https://eprint.iacr.org/2025/1786.pdf)
### Abstract
The CKKS fully homomorphic encryption (FHE) scheme enables computations on vectors of approximate complex numbers. A moderate precision of $\approx 20$ bits often suffices but, in many applications, a higher precision is required for functionality and/or security. Indeed, to obtain IND-CPA-D security [Li-Micciancio; Eurocrypt'21], secure threshold-FHE [Asharov et al; Eurocrypt'12] and circuit privacy [Gentry; STOC'09], all known approaches require a precision that supports noise flooding. This may lead to a precision of $\approx 80$ bits, or more. High-precision CKKS is hard to achieve, notably because of bootstrapping. The main difficulty is modulus consumption: every homomorphic multiplication consumes some, out of an overall modulus budget. Unfortunately, in high precision, most known bootstrapping algorithms consume so much modulus that one needs to increase the parameters to increase the budget. The state-of-the-art approach, Meta-BTS [Bae et al; CCS'22], performs moderate-precision bootstrapping several times to enable high-precision bootstrapping, with similar modulus consumption as the base bootstrapping it builds upon. It however damages latency.
We introduce a new approach for high-precision CKKS bootstrapping, whose cost is almost independent of the precision (as opposed to Meta-BTS) and whose modulus consumption increases significantly more slowly than with classical bootstrapping algorithms. Our design relies on the EvalRound bootstrapping [Kim et al; Asiacrypt'22], which we improve in the high-precision context by leveraging and improving recent techniques for handling discrete data with CKKS. We obtain for the first time a non-iterative 80-bit precise bootstrapping algorithm which can be run in ring degree $N=2^{16}$, with 494 bits of remaining modulus for computations. In terms of throughput, and for 80-bit precision, our implementation shows an acceleration of 64\% compared to Meta-BTS.
## 2025/1787
* Title: Four-round Statistical Non-malleable Zero-knowledge
* Authors: Susumu Kiyoshima
* [Permalink](https://eprint.iacr.org/2025/1787)
* [Download](https://eprint.iacr.org/2025/1787.pdf)
### Abstract
We present a 4-round statistical non-malleable zero-knowledge (NMZK) argument in the plain model under standard hardness assumptions. Our construction can be based on any collision-resistant hash function and injective one-way function, and it guarantees simulation extractability in the delayed-input one-many setting. Before this work, 4-round constructions were known for computational NMZK but not for statistical NMZK.
## 2025/1788
* Title: Just Guess: Improved (Quantum) Algorithm for the Underdetermined MQ problem
* Authors: Alexander May, Massimo Ostuzzi, Henrik Ressler
* [Permalink](https://eprint.iacr.org/2025/1788)
* [Download](https://eprint.iacr.org/2025/1788.pdf)
### Abstract
We propose a novel algorithm to solve underdetermined systems of multivariate quadratic (MQ) equations over finite fields. In modern MQ signature schemes such as MAYO QR-UOV and SNOVA finding solutions to such systems is equivalent to signature forgery.
The current benchmark for estimating forgery bit complexity is HashimotorCOs algorithm which transforms the original underdetermined MQ system $P$ into a more tractable system $\tilde{P}$. A hybrid combination of solving $\tilde{P}$ via Gr||bner basis and exhaustive search eventually solves $P$.
We introduce a novel transformation that pushes the hybrid approach to its extreme. Specifically, we reduce the underdetermined MQ system to a sequence of quadratic equations in a single variable at the cost of a larger exhaustive search. As a consequence, signature forgery no longer relies on the hardness of MQ solving but becomes pure guessing via exhaustive search. This in turn implies that signature forgery is significantly more vulnerable against quantum attacks via Grover search.
We provide accurate estimates for the classical and quantum bit complexity of forging signatures for MAYO QR-UOV and SNOVA using our novel algorithm. We reduce the quantum security of all security levels of MAYO QR-UOV and SNOVA.
## 2025/1789
* Title: Olingo: Threshold Lattice Signatures with DKG and Identifiable Abort
* Authors: Kamil Doruk Gur, Patrick Hough, Jonathan Katz, Caroline Sandsbr|Nten, Tjerand Silde
* [Permalink](https://eprint.iacr.org/2025/1789)
* [Download](https://eprint.iacr.org/2025/1789.pdf)
### Abstract
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 of Gur, Katz, and Silde (PQCrypto 2024). We change the underlying signature scheme to Raccoon (Katsumata et al., Crypto 2024), remove the trapdoor commitments, and 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 $2.6$ KB public keys and $9.7$ KB signatures; while signing requires communication of $953$ KB per party. Using the LaBRADOR proof system (Beullens and Seiler, Crypto 2023), this can be further reduced to $596$ KB. An optimistic non-interactive version of our scheme requires only $83$ KB communication per party.
## 2025/1790
* Title: CA-MCPQ: A Context-Aware Post-Quantum Protocol for AI Agent Integrity and Security
* Authors: Seyoung Yoon, Hyunji Kim, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2025/1790)
* [Download](https://eprint.iacr.org/2025/1790.pdf)
### Abstract
We propose CA-MCPQ, a context-aware post-quantum-secure extension of the Model Context Protocol (MCP). Unlike standard MCP, which leaves authentication, encryption, and authorization optional or implementation-specific, CA-MCPQ elevates them to mandatory protocol-level mechanisms. The design incorporates post-quantum mutual authentication, KEM-derived session keys, and authenticated sequencing to ensure session integrity and prevent replay. Role-based access control is enforced, while token-based authentication is eliminated entirely. AI dynamically infers the required security tier from contextual information and negotiates compatible PQC algorithms; each response returns a reliability score that quantifies alignment with the requested security level.
This architecture addresses critical vulnerabilities of MCPrCoincluding token misuse, session hijacking, impersonation, and quantum attackrCowhile preserving interoperability.
Notably, our evaluation shows that the cryptographic and transport overheads are negligible compared to model computation, confirming that strong post-quantum assurances can be achieved without degrading system performance. Overall, CA-MCPQ provides a practical path toward secure-by-design AI agent ecosystems and lays the groundwork for future extensions such as agentrCoagent secure coordination.
## 2025/1791
* Title: High-Speed 16-Radix Polynomial Multiplication on ARM Cortex-M4 with Recursive Karatsuba Layers
* Authors: Minjoo Sim, Hyunjun Kim, Minwoo Lee, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2025/1791)
* [Download](https://eprint.iacr.org/2025/1791.pdf)
### Abstract
Polynomial multiplication over $\mathbb{F}_2[x]$ is a fundamental building block in code-based and lattice-based cryptography, particularly on lightweight embedded devices where dedicated carry-less multiply instructions are unavailable. This paper presents a high-speed, constant-time implementation of radix-16 polynomial multiplication on the ARM Cortex-M4, combining zero-padding with recursive Karatsuba layers. Building on the radix-16 decomposition proposed by Chen et al. in TCHESrCO21, we replace the conventional schoolbook inner multiplier with a multi-level Karatsuba scheme. This optimization reduces cycle counts on the ARM Cortex-M4 while preserving constant-time execution. To further optimize efficiency, the design minimizes packing and unpacking overhead by operating at 128-bit granularity and employs a five-stage pipelinerCoDecomposition, Padding, Multiplication, Unpadding, and ReassemblyrCoimplemented entirely with data-independent shifts, XORs, and masks. Experimental results on the Cortex-M4 show that our optimized $ct\_poly32\_mul\_64\_bit$ implementation achieves up to 31\% improvement over the best existing constant-time baseline, demonstrating the efficiency and scalability of recursive Karatsuba for resource-constrained cryptographic applications.
--- Synchronet 3.21a-Linux NewsLink 1.2