From Newsgroup: sci.crypt

## In this issue
1. [2024/1594] Attacks on Goldreich's Pseudorandom Generators by ...
2. [2025/2307] Computationally Succinct Authentication from DCR: ...
3. [2025/2308] Succinct Garbled Circuits with Low-Depth Garbling ...
4. [2025/2309] On the Concrete Practicality of Post-Quantum Multi- ...
5. [2025/2310] RACE: A Rapid ARM Cryptographic Engine for Code- ...
6. [2025/2311] Accelerating NTRU-based Bootstrapping with Block ...
7. [2025/2312] Anamorphic Signatures With Dictator and Recipient ...
8. [2025/2313] Nested YOSO MPC: Near Optimal Resilience Without an ...
9. [2025/2314] Registered Attribute-Based Encryption with Publicly ...
10. [2025/2315] Conditionally Input-Revealing 2PC and Fuzzy ...
11. [2025/2316] Making Sense of Private Advertising: A Principled ...
12. [2025/2317] InstantOMR: Oblivious Message Retrieval with Low ...
13. [2025/2318] Hyperion: Private Token Sampling with Homomorphic ...
14. [2025/2319] One-Time Memories Secure against Depth-Bounded ...
15. [2025/2320] New Constructions of Multiplicative Secret Sharing ...
16. [2025/2321] High-Precision Exact FHE Made Simple, General, and Fast
17. [2025/2322] Distributed Symmetric Key Establishment with ...
18. [2025/2323] An Improved Method for Predicting Truncated ...
19. [2025/2324] SHAFT: Secure, Handy, Accurate, and Fast ...
20. [2025/2325] Pseudorandom Correlation Functions for Garbled Circuits
21. [2025/2326] Efficiently Provable Approximations for Non- ...
22. [2025/2327] Transparent and Post-Quantum Distributed SNARK with ...
23. [2025/2328] SNARGs for NP from LWE
24. [2025/2329] A note on ``a fully dynamic multi-secret sharing ...
25. [2025/2330] Verifiable Aggregate Receipts with Applications to ...
26. [2025/2331] SUMSIG: Compact Code-Based Signatures from Sum- ...
27. [2025/2332] DNS-Anchored zk-SNARK Proofs: A Stateless ...
28. [2025/2333] Analysis of Diffusion Properties in Generalized ...
29. [2025/2334] Moving a Step of ChaCha in Syncopated Rhythm ...
30. [2025/2335] d/v-CLSAG: Extension for Concise Linkable ...
31. [2025/2336] Compact Adaptively Secure Identity-Based Encryption ...
32. [2025/2337] ML-DSA-OSH: An Efficient, Open-Source Hardware ...
33. [2025/2338] OHMG: One hot modular garbling
34. [2025/2339] SoK: Approximate Agreement
35. [2025/2340] OOPS: One-time Oblivious Polynomial Signatures
36. [2026/1] The Cokernel Pairing
37. [2026/2] LatORAM: ORAMs from Lateral Stashes and Delayed ...
38. [2026/3] Batch Arguments with Optimal Communication
39. [2026/4] TSM+ and OTSM - Correct Application of Time Sharing ...
## 2024/1594
* Title: Attacks on Goldreich's Pseudorandom Generators by Grouping and Solving * Authors: Ximing Fu, Mo Li, Shihan Lyu, Chuanyi Liu
* [Permalink](https://eprint.iacr.org/2024/1594)
* [Download](https://eprint.iacr.org/2024/1594.pdf)
### Abstract
Goldreich's pseudorandom generators (PRGs) with constant locality admit highly parallel implementations, yet the concrete security of instantiations based on the $\mathsf{XOR}\text{-}\mathsf{THR}$ predicate has remained unclear.
In this work, we present novel seed recovery attacks on Goldreich's PRGs instantiated on $\mathsf{XOR}\text{-}\mathsf{THR}$ predicates with $m=n^s$, where $m$ and $n$ are the length of output and input, respectively.
By partitioning the output bits into groups according to common input bits, high-biased noisy equations can be derived for the group whose common input bits are all 1s (or all 0s). Leveraging two solvers tailored to these equations, we achieve the seed recovery attacks, which needs roughly $2^{n(1-\log_2{(1 + \frac{2s}{\sqrt{2\pi (b-s)}})})}$ calls to Gaussian elimination when the input length of the $\mathsf{THR}$ predicate $b\geq (n-s)^{1/s}+s-1$ with small stretch $s$.
Applying our attack to the $\mathsf{XOR}\text{-}\mathsf{MAJ}$ challenges in STOC 2016 yields complexity \(2^{\,n\!\left(1-\log_{2}\!\left(1+\sqrt{\frac{s}{18\pi}}\right)\right)} \le 2^{0.82n}\), i.e., at least a \(2^{0.18n}\) speedup over exhaustive search for any stretch \(s>1\).
We also deploy our attack on an instance used in the construction of silent oblivious transfer protocols (Eurocrypt 2024) with \(n = 256\). This attack is capable of breaking the instance using approximately \(2^{31.3}\) calls to Gaussian elimination over 244 variables. We successfully implemented the attack on a cluster of 14 CPU cores, recovering the seed in 71 hours, demonstrating the attack's efficiency.
Beyond PRGs, with appropriate adaptations our method extends to FiLIP stream ciphers instantiated with \mathsf{THR}-related predicates. Our evaluation indicates that most FiLIP instances do not meet their claimed security. For instance, the configuration \(\mathsf{XOR}_{100}\text{-}\mathsf{THR}_{11,22}\text{-}\mathsf{THR}_{11,22}\) is broken in about \(2^{59}\) calls to Gaussian elimination over 357 variables despite a 397-bit key and a claimed 80-bit security level.
## 2025/2307
* Title: Computationally Succinct Authentication from DCR: Attribute-Based Laconic Function Evaluation and More
* Authors: Pierre Meyer, Claudio Orlandi, Lawrence Roy, Peter Scholl
* [Permalink](https://eprint.iacr.org/2025/2307)
* [Download](https://eprint.iacr.org/2025/2307.pdf)
### Abstract
We present the first construction of attribute-based laconic function evaluation (AB-LFE) from the decisional composite residuosity (DCR) assumption. This yields the first example of computationally succinct secure computation from a group-based assumption, avoiding reliance on noisy lattice assumptions such as LWE. Our construction builds on recent work in fully homomorphic MACs and homomorphic secret sharing by Ishai, Li and Lin (FOCS 2025) and Meyer, Orlandi, Roy, and Scholl (Crypto 2025), which we extend by constructing a fully homomorphic MAC for packed vector operations, where the evaluation time of one party is independent of the vector length.
As applications, we obtain full-fledged laconic function evaluation (LFE) from the combination of DCR and standard LWE, avoiding the need for sub-exponential modulus-to-noise ratio LWE used in previous work. We also obtain the first constrained pseudorandom function whose master evaluation key is succinct in the constraint.
These results highlight the unexplored power of group-based cryptography for succinct secure computation.
## 2025/2308
* Title: Succinct Garbled Circuits with Low-Depth Garbling Algorithms
* Authors: Hanjun Li, Huijia Lin, George Lu
* [Permalink](https://eprint.iacr.org/2025/2308)
* [Download](https://eprint.iacr.org/2025/2308.pdf)
### Abstract
We study the problem of constructing Boolean garbling schemes that are both succinct$-$with garbled circuit size significantly smaller than the original circuit$-$and have low-depth garbling algorithms, where the garbling process runs in parallel time logarithmic in the circuit size. Prior schemes achieve one but not the other, unless relying on indistinguishability obfuscation ($\mathsf{iO}$), which is prohibitively inefficient, relies on a combination of multiple assumptions, and achieves only polynomial garbling depth $\mathsf{poly}(\lambda,\log |C|)$.
We resolve this tension by presenting the first garbling schemes that are both succinct and admit garbling algorithms in $\mathsf{NC}^1$, based only on standard group and lattice assumptions. Our main results include:
rCo $\textbf{One-bit-per-gate garbling}$ with logarithmic garbling depth based on DDH or RLWE and the existence of a local PRG.
rCo $\textbf{Succinct privacy-free garbling}$ of size linear in the circuit depth $D$ (and sublinear in the circuit size $|C|$), based on DDH or RLWE.
rCo $\textbf{Reusable, fully succinct garbling}$ with logarithmic garbling depth, based on decomposable LWE.
The DDH-based one-bit-per-gate scheme has tunably small inverse polynomial correctness and privacy errors, which can be made negligible at the cost of increasing garbling depth to $\mathsf{poly}(\lambda)$.
As further extension, we also obtain the first attribute-based encryption schemes with succinct keys and low-depth key generation.
At a conceptual level, our constructions are derived from a unified framework that subsumes all prior approaches to succinct garbling. It identifies the common source of high-depth garbling, and provides a general methodology for reducing garbling depth without sacrificing succinctness, applicable across different techniques and assumptions.
## 2025/2309
* Title: On the Concrete Practicality of Post-Quantum Multi-Authority Attribute-Based Encryption
* Authors: Hassan Nasiraee
* [Permalink](https://eprint.iacr.org/2025/2309)
* [Download](https://eprint.iacr.org/2025/2309.pdf)
### Abstract
The transition of cryptographic primitives to the post-quantum era necessitates the rigorous translation of asymptotic security proofs into concrete parameter instantiations. This paper evaluates the practical realizability of the Decentralized Multi-Authority Attribute-Based Encryption (MA-ABE) scheme by Datta, Komargodski, and Waters (Eurocrypt 2021), a seminal construction relying exclusively on the Learning With Errors (LWE) assumption. While DKW21 eliminates the reliance on bilinear maps, offering resilience against quantum adversaries, our comprehensive numerical audit reveals a profound dichotomy between its theoretical soundness and practical feasibility. We demonstrate that the convergence of constraints derived from LWE hardness and the noise flooding technique required for simulation-based security forces the modulus-to-noise ratio into a super-polynomial regime. Consequently, the requisite parameters---particularly the smudging bound $\hat{B}$---scale astronomically ($\approx 10^{47}$), rendering the scheme unimplementable on existing computational substrates. Beyond identifying this "Parameter Wall," this work proposes a radical architectural reconfiguration to bridge the gap between theory and practice. We introduce novel optimization strategies including the transition to non-commutative Module-LWE structures, the invention of Coset-Restricted Lattice Hashing to minimize pre-image norms, and the adoption of Entropic Smudging via Lossy Trapdoors. Furthermore, we explore Isospectral Lattice Deformations and Learning With Rounding (LWR) transformations to decouple security constraints from decryption correctness, outlining a viable roadmap for practical post-quantum access control.
## 2025/2310
* Title: RACE: A Rapid ARM Cryptographic Engine for Code-Based Classic McEliece PQC Scheme
* Authors: Wen Wu, Jiankuo Dong, Xuecheng Liu, Shuzhou Sun, Zhenjiang Dong, Jingqiang Lin, Fu Xiao
* [Permalink](https://eprint.iacr.org/2025/2310)
* [Download](https://eprint.iacr.org/2025/2310.pdf)
### Abstract
With the rapid development of quantum computing, traditional public-key cryptosystems are increasingly vulnerable, making post-quantum cryptography (PQC) a critical area for securing future information systems. As a prominent code-based key encapsulation mechanism (KEM), Classic McEliece offers strong quantum security. However, its large public key size and complex decoding process introduce significant performance bottlenecks, hindering its practical deployment on mobile and edge devices. To address these challenges, we propose RACE (Rapid ARM Cryptographic Engine), a systematic acceleration framework tailored for ARMv8 architectures, designed to enhance the efficiency of Classic McEliece while preserving its constant-time security guarantees.
In the key generation phase, we introduce an implicit data layout and in-place transformation strategy based on LUP decomposition, coupled with NEON SIMD vectorization. For the encapsulation phase, we optimize error vector generation with constant-time techniques and batch-loading strategies to reduce memory access redundancy during matrix-vector multiplications. In the decapsulation phase, we apply lane-level fusion and dual-lane butterfly fusion techniques, leveraging NEON instructions to parallelize field multiplication and fast fourier transform (FFT) butterfly operations.
Experiments on three ARMv8 platforms (Kunpeng 920, Apple M1, Apple M2 Pro) demonstrate significant speedups of RACE compared to the official vec implementation. For the McEliece8192128 parameter set, key generation is accelerated by 1.33$\times$, 1.90$\times$, and 2.04$\times$, encapsulation by 1.33$\times$, 1.23$\times$, and 1.26$\times$, and decapsulation by 1.27$\times$, 1.68$\times$, and 1.66$\times$, respectively. RACE also outperforms open-source libraries, particularly in decapsulation, where speedups reach several hundred times. These results validate the practical applicability and deployment potential of RACE in mobile and edge computing environments.
## 2025/2311
* Title: Accelerating NTRU-based Bootstrapping with Block Key Distributions
* Authors: Jingwei Feng, Baofeng Wu, Dongdai Lin, Binwu Xiang
* [Permalink](https://eprint.iacr.org/2025/2311)
* [Download](https://eprint.iacr.org/2025/2311.pdf)
### Abstract
NTRU-based bootstrapping is a high-performance variant of FHEW-like bootstrapping schemes. Its main computational bottleneck lies in the blind rotation step, which involves numerous external products. In this work, we propose multiple techniques to reduce the number of these costly operations, including the use of block binary keys, block ternary keys, and the integration of block keys with the key unrolling method. Specifically, our approach reduces the number of external products to $n/\ell$ for block keys $\mathbf{B}_{k,\ell}$ ($\mathbf{T}_{k,\ell}$), compared to $n$ in FINAL (ASIACRYPT 2021) and $n/2$ in the key unrolling approach (CHES 2024). When combining block keys with key unrolling, the number can further be reduced to $n/2\ell$ .
We implemented our algorithms using the CHIFHE library. Under 128-bit security settings, using block binary keys $\mathbf{B}_{k,\ell}$ ($\ell=4$), block ternary keys $\mathbf{T}_{k,\ell}$ ($\ell=4$) and key unrolling on $\mathbf{B}_{n/2,2}$ achieve a speedup of $1.12\times$ over the key unrolling method (CHES 2024) and $1.73\times$ over FINAL (ASIACRYPT 2021). Notably, the last $2$ algorithms increase memory usage by less than 15MB compared to the key unrolling method (CHES 2024).
## 2025/2312
* Title: Anamorphic Signatures With Dictator and Recipient Unforgeability for Long Messages
* Authors: Amit Deo, Benoit Libert
* [Permalink](https://eprint.iacr.org/2025/2312)
* [Download](https://eprint.iacr.org/2025/2312.pdf)
### Abstract
Anamorphic signatures (Kutylowski {\it et al.}, Crypto'23) provide a way to covertly use encryption by hiding ciphertexts inside digital signatures without a dictator noticing. Recently (Asiacrypt'24), Jaeger and Stracovsky advocated stronger security notions for the primitive. Their notion of dictator unforgeability requires a dictator's inability to produce fresh signatures that decrypt to a meaningful covert message. The notion of recipient unforgeability requires that anamorphic receivers cannot forge signatures even after having observed anamorphic signatures on messages of their choice. To date, the known schemes satisfying all these properties simultaneously rely on the "randomness replacement" technique. As a result, they are restricted to short anamorphic messages either because their anamorphic decryption mechanism involves an exhaustive search step, or because they embed the anamorphic plaintext in a public random salt (which is typically short in compatible signature schemes like RSA-PSS). In this paper, we present anamorphic signatures that depart from the randomness replacement paradigm and make it possible to encrypt longer anamorphic plaintexts. We show that (generalized) Okamoto-Schnorr signatures, as well as GQ and $2^t$-root signatures all have anamorphic modes satisfying the three desired security properties. The ratio between the lengths of anamorphic plaintexts and signatures can even be very close to $1$ for appropriate parameters. We also discuss an extension to Lyubashevsky's lattice-based signatures.
## 2025/2313
* Title: Nested YOSO MPC: Near Optimal Resilience Without an MPC Setup
* Authors: Ittai Abraham, Eli Chouatt, Ivan Damg|Nrd, Yossi Gilad, Gilad Stern, Sophia Yakoubov
* [Permalink](https://eprint.iacr.org/2025/2313)
* [Download](https://eprint.iacr.org/2025/2313.pdf)
### Abstract
You Only Speak Once (YOSO) secure Multi-Party Computation (MPC) provides scalability and adaptive security by distributing the computation across a sequence of anonymous committees. This relies on role assignment, which sets up the infrastructure necessary for the members of one committee to send secret messages to members of subsequent committees without knowing their identities. Existing approaches to role assignment suffer from significant limitations: high broadcast complexity, reliance on secure computation (which creates a circular dependency), or the requirement of an overwhelming honest majority among available nodes in order to guarantee output delivery in the MPC.
In this work, we introduce Nested YOSO MPC, which overcomes all of these drawbacks by departing from the traditional threshold adversary structure. We design our MPC to run over a sequence of size-$m^2$ committees, each composed of $m$ subcommittees of size $m$. This MPC is secure (with guaranteed output delivery) as long as most subcommittees on each committee have an honest majority. Our efficient, setup-free role assignment protocol guarantees an honest majority on most subcommittees as long as $(\frac{1}{2} + \epsilon)N$ of the available participants are honest, where $\epsilon$ is a constant and $N$ is the total number of available participants.
As a complementary contribution, we prove that no MPC with polylogarithmic (in $N$) broadcast complexity can rely on $\frac{N}{2} + o(\frac{N}{polylog(N)})$ honest parties, indicating that our construction is near-optimal in terms of the number of corruptions it can tolerate.
## 2025/2314
* Title: Registered Attribute-Based Encryption with Publicly Verifiable Certified Deletion, Everlasting Security, and More
* Authors: Shayeef Murshid, Ramprasad Sarkar, Mriganka Mandal
* [Permalink](https://eprint.iacr.org/2025/2314)
* [Download](https://eprint.iacr.org/2025/2314.pdf)
### Abstract
Certified deletion ensures that encrypted data can be irreversibly deleted, preventing future recovery even if decryption keys are later exposed. Although existing works have achieved certified deletion across various cryptographic primitives, they rely on central authorities, leading to inherent escrow vulnerabilities. This raises the question of whether certified deletion can be achieved in decentralized frameworks such as Registered Attribute-Based Encryption (RABE) that combines fine-grained access control with user-controlled key registration. This paper presents the first RABE schemes supporting certified deletion and certified everlasting security. Specifically, we obtain the following:
- We first design a privately verifiable RABE with Certified Deletion (RABE-CD) scheme by combining our newly proposed shadow registered ABE (Shad-RABE) with one-time symmetric key encryption with certified deletion.
- We then construct a publicly verifiable RABE-CD scheme using Shad-RABE, witness encryption, and one-shot signatures, allowing any party to validate deletion certificates without accessing secret keys.
- We also extend to privately verifiable RABE with Certified Everlasting Deletion (RABE-CED) scheme, integrating quantum-secure RABE with the certified everlasting lemma. Once a certificate is produced, message privacy becomes information-theoretic even against unbounded adversaries.
- We finally realize a publicly verifiable RABE-CED scheme by employing digital signatures for the BB84 states, allowing universal verification while ensuring that deletion irreversibly destroys information relevant to decryption.
## 2025/2315
* Title: Conditionally Input-Revealing 2PC and Fuzzy Password-Authenticated Key Exchange
* Authors: David Richardson, Mike Rosulek, Jiayu Xu
* [Permalink](https://eprint.iacr.org/2025/2315)
* [Download](https://eprint.iacr.org/2025/2315.pdf)
### Abstract
Yao's famous protocol for secure 2-party computation, based on garbled circuits, is well-known to be insecure against an actively corrupt garbler. We introduce a new and extremely simple variant of Yao's protocol that is fully secure against active adversaries, for a certain class of functions that we call conditionally input-revealing.
We then show how to use this new protocol as the basis for fuzzy password authenticated key exchange (fuzzy PAKE). In fuzzy PAKE, two parties each hold a low-entropy secret (e.g., a password), and they interact to obtain a secure high-entropy key if and only if the passwords are sufficiently ``close.'' Our new fuzzy PAKE protocol supports completely arbitrary predicates for password ``closeness''. Compared to prior fuzzy PAKE protocols, ours is roughly $2\times$ cheaper in communication, computation, and round complexity.
## 2025/2316
* Title: Making Sense of Private Advertising: A Principled Approach to a Complex Ecosystem
* Authors: Kyle Hogan, Alishah Chator, Gabriel Kaptchuk, Mayank Varia, Srinivas Devadas
* [Permalink](https://eprint.iacr.org/2025/2316)
* [Download](https://eprint.iacr.org/2025/2316.pdf)
### Abstract
In this work, we model the end-to-end pipeline of the advertising ecosystem, allowing us to identify two main issues with the current trajectory of private advertising proposals. First, prior work has largely considered ad targeting and engagement metrics individually rather than in composition. This has resulted in privacy notions that, while reasonable for each protocol in isolation, fail to compose to a natural notion of privacy for the ecosystem as a whole, permitting advertisers to extract new information about the audience of their advertisements. The second issue serves to explain the first: we prove that perfect privacy is impossible for any, even minimally, useful advertising ecosystem, due to the advertisers' expectation of conducting market research on the results.
Having demonstrated that leakage is inherent in advertising, we re-examine what privacy could realistically mean in advertising, building on the well-established notion of sensitive data in a specific context. We identify that fundamentally new approaches are needed when designing privacy-preserving advertising subsystems in order to ensure that the privacy properties of the end-to-end advertising system are well aligned with people's privacy desires.
## 2025/2317
* Title: InstantOMR: Oblivious Message Retrieval with Low Latency and Optimal Parallelizability
* Authors: Haofei Liang, Zeyu Liu, Eran Tromer, Xiang Xie, Yu Yu
* [Permalink](https://eprint.iacr.org/2025/2317)
* [Download](https://eprint.iacr.org/2025/2317.pdf)
### Abstract
Anonymous messaging systems, such as privacy-preserving blockchains and private messaging applications, need to protect recipient privacy: ensuring no linkage between the recipient and the message. This raises the question: how can untrusted servers assist in delivering the pertinent messages to each recipient, without requiring the recipient to linearly scan all messages or revealing the intended recipient of each message? Oblivious message retrieval (OMR), a recently proposed primitive, addresses this issue by using homomorphic encryption in the single-server setting.
This work introduces $\mathsf{InstantOMR}$, a novel OMR scheme that combines TFHE functional bootstrapping with standard RLWE operations in a hybrid design, achieving significant improvements in both latency and parallelizability compared to prior BFV-based schemes. We propose a two-layer bootstrapping architecture and hybrid use of TFHE and regular RLWE homomorphic operations for $\mathsf{InstantOMR}$. Our implementation, using the $\mathsf{Primus}$-$\mathsf{fhe}$ library (and estimates based on $\mathsf{TFHE}$-$\mathsf{rs}$), demonstrates that $\mathsf{InstantOMR}$ offers the following key advantages:
- Low latency: $\mathsf{InstantOMR}$ achieves ${\sim} 860\times$ lower latency than $\mathsf{SophOMR}$, the state-of-the-art single-server OMR construction. This translates directly into reduced recipient waiting time (by the same factor) in the streaming setting, where the detector processes incoming messages on-the-fly and returns a digest immediately upon the recipient becoming online.
- Optimal parallelizability: $\mathsf{InstantOMR}$ scales near-optimally with available CPU cores (by processing messages independently), so for high core counts, it is faster than SophOMR (whose parallelism is constrained by its reliance on BFV).
## 2025/2318
* Title: Hyperion: Private Token Sampling with Homomorphic Encryption
* Authors: Lawrence Lim, Jiaming Liu, Vikas Kalagi, Amr El Abbadi, Divyakant Agrawal
* [Permalink](https://eprint.iacr.org/2025/2318)
* [Download](https://eprint.iacr.org/2025/2318.pdf)
### Abstract
A promising direction for enabling private queries to large language models (LLMs) is with homomorphic encryption (HE). An open problem is performing token sampling under HE. In this paper, we introduce Hyperion, an efficient HE algorithm for inverse transform sampling, enabling private token sampling with 1 comparison depth, $O(1)$ amortized comparisons, and $O(\log n)$ rotations. We implement our approach and demonstrate that it samples tokens in 0.14 seconds for 32k tokens ($\approx 4.4\, \mu\mathrm{s}$ per token) on GPU, achieving a $100\times$ latency improvement over prior work.
## 2025/2319
* Title: One-Time Memories Secure against Depth-Bounded Quantum Circuits
* Authors: Kyosuke Sekii, Takashi Nishide
* [Permalink](https://eprint.iacr.org/2025/2319)
* [Download](https://eprint.iacr.org/2025/2319.pdf)
### Abstract
A one-time memory (OTM) is a useful cryptographic primitive, classically modeled after a non-interactive oblivious transfer. It is well known that secure OTMs (and more generally one-time deterministic programs) cannot exist in the standard model in either the classical or quantum setting due to Broadbent et al. (CRYPTO'13).
Broadbent et al.\ circumvented this impossibility by assuming the existence of hardware tokens that cannot be queried in superposition.
In this work, we take a different approach. Building on Liu's assumption (ITCS'23) that adversaries are limited to depth-bounded quantum circuits, we present two OTM constructions.
The first is efficiently realizable and secure against adversaries restricted to constant-depth quantum circuits. The second is a feasibility result that achieves security against adversaries limited to $\mathcal{O}(\lambda^\gamma)$-depth quantum circuits by ensuring that a successful attack would necessarily require deeper quantum computations, where $\lambda^\gamma$ is a polynomial in the security parameter $\lambda$. Our results therefore extend prior work, which either relied on hardware assumptions or considered only constant-depth-bounded adversaries.
As a result, by combining our proposed quantum OTMs with the framework of Broadbent et al. (CRYPTO'13), one can also realize quantum one-time programs (OTPs) for deterministic programs.
## 2025/2320
* Title: New Constructions of Multiplicative Secret Sharing Schemes
* Authors: Chunming Tang, Haonan Fu, Zheng Chen, Hongwei Zhu
* [Permalink](https://eprint.iacr.org/2025/2320)
* [Download](https://eprint.iacr.org/2025/2320.pdf)
### Abstract
This paper investigates the multiplicative properties of linear codes in secret sharing schemes. To address the limitation that certain access structures cannot be realized by ideal linear codes, we introduce the notion of shortest linear codes as an ideal benchmark for code length. Since explicitly determining such shortest codes is generally computationally difficult, we propose an explicit construction that, for any given access structure, produces a length-efficient linear code whose induced the access structure. On this basis, we further define multiplicative ideal linear codes and multiplicative length-efficient linear codes, and derive necessary and sufficient conditions for the existence of multiplicativity. The effectiveness of the proposed approach is demonstrated by concrete examples. Compared with the construction of Cramer et al., the multiplicative linear codes obtained in this work have smaller length.
## 2025/2321
* Title: High-Precision Exact FHE Made Simple, General, and Fast
* Authors: Chris Peikert, Doron Zarchy, Guy Zyskind
* [Permalink](https://eprint.iacr.org/2025/2321)
* [Download](https://eprint.iacr.org/2025/2321.pdf)
### Abstract
Many important applications of fully homomorphic encryption (FHE) require *high-precision* arithmetic, e.g., plaintext rings $\mathbb{Z}_p$ for a huge prime or power-of-two modulus $p$. The classic FHE schemes are poorly suited to this, because the inverse error rate of fresh ciphertexts, and the error growth under homomorphic multiplication, are both larger than $p$, which results in large and inefficient parameters. While there are now several works addressing this problem, the landscape for *exact* (as opposed to approximate) FHE is highly fragmented: known solutions either work only for certain rare plaintext moduli having very special forms (sometimes using non-standard ciphertext rings that lack other important features for FHE), or have quite complicated and high-latency constructions.
This work gives a very simple and general technique for high-precision exact FHE, in which the error rates and growth match those of prior schemes with *exponentially smaller* precision, and which has good practical efficiency.
In contrast to all prior works, our scheme works for *any integer modulus*, and also over *any underlying (number) ring*---or even with no structured ring at all, making it the first solution that can be based on plain LWE. It is also *fully compatible with prior FHE techniques* for fast ring arithmetic, plaintext packing and SIMD operations, bootstrapping, etc. For plaintext ring $\mathbb{Z}_{2^{64}}$, our (preliminary, unoptimized, single-threaded) implementation does homomorphic multiplication in just tens of milliseconds, and supports a two- to three-fold increase in multiplicative depth versus classic FHE schemes at typical security levels.
## 2025/2322
* Title: Distributed Symmetric Key Establishment with Forward Secrecy for Implantable Medical Devices
* Authors: Roozbeh Sarenche, Sayon Duttagupta, Francesco Milizia, Kevin Bogner, Varesh Mishra
* [Permalink](https://eprint.iacr.org/2025/2322)
* [Download](https://eprint.iacr.org/2025/2322.pdf)
### Abstract
Implantable Medical Devices (IMDs) operate for many years in an ecosystem where device loss, backend compromise, and physical capture are realistic long-term threats. While prior work has extensively studied secure pairing and access control, existing IMD architectures typically rely on long-lived secrets. As a result, the compromise of a single credential can retroactively expose years of sensitive patient telemetry. Limiting such damage requires Perfect Forward Secrecy (PFS), yet achieving PFS in IMDs is challenging due to strict energy constraints, intermittent connectivity, and safety requirements. Public-key cryptography is often too costly for frequent use on implants and physical-layer defences rely on fragile assumptions
In this work, we present a symmetric-only communication protocol that provides forward secrecy for IMDs while remaining robust to device loss and state desynchronisation. The protocol evolves cryptographic state across sessions using lightweight primitives on the implant, ensuring that past communications remain confidential even if the IMD or associated client devices are compromised later. To address the safety risks of desynchronisation, we introduce a threshold-assisted recovery mechanism that enables secure resynchronisation via a distributed backend without trusting any single client or server. The design preserves patient-centric control and supports controlled emergency access without undermining long-term confidentiality. We formally analyse the protocol using ProVerif and demonstrate feasibility through implementations on a 16-bit MSP430 and a 32-bit ARM Cortex-M33 microcontroller.
## 2025/2323
* Title: An Improved Method for Predicting Truncated Fibonacci LFSRs over Integer Residue Rings
* Authors: Han-Bing Yu, Qun-Xiong Zheng, Wen-Feng Qi
* [Permalink](https://eprint.iacr.org/2025/2323)
* [Download](https://eprint.iacr.org/2025/2323.pdf)
### Abstract
Sequences over the residue ring of integers modulo $m$ generated by linear feedback shift registers (LFSRs) exhibit ring-level linearity and bit-level nonlinearity, making such kind of LFSRs (denoted as $\mathbb{Z}/(m)$-LFSRs) a key component of stream ciphers. Beyond fundamental cryptographic properties, the unpredictability of truncated $\mathbb{Z}/(m)$-LFSRs has attracted considerable attention as a critical security consideration in the design of stream cipher components. This paper investigates the unpredictability of truncated Fibonacci $\mathbb{Z}/(m)$-LFSRs under various scenarios. First, we provide a practical heuristic estimation for the values of two key parameters based on lattice theory, thereby avoiding previous blind search. This estimation is subsequently applied to determine the number of truncated digits required in different scenarios. Next, we develop a lattice-based method for finding annihilating polynomials over $\mathbb{Z}/(m)$ by the high-order truncated digits when the modulus $m$ is known but coefficients are unknown, filling a methodological gap for this specific case. Finally, we demonstrate that when both the modulus $m$ and coefficients are unknown but $m$ is close to a power of 2, our lattice constructed by the high-order truncated digits can yield annihilating polynomials over $\mathbb{Z}/(m)$ rather than $\mathbb{Z}$ as in [1], achieving a 41% reduction in digits and a 4x speedup for the recovery of ZUC's driving sequence with 17 high-order truncated digits. Experimental results confirm the efficacy of our methods.
## 2025/2324
* Title: SHAFT: Secure, Handy, Accurate, and Fast Transformer Inference
* Authors: Andes Y. L. Kei, Sherman S. M. Chow
* [Permalink](https://eprint.iacr.org/2025/2324)
* [Download](https://eprint.iacr.org/2025/2324.pdf)
### Abstract
A growing adoption of transformer-based machine learning models is raising concerns about sensitive data exposure. Nonetheless, current secure inference solutions incur substantial overhead due to their extensive reliance on non-linear protocols, such as softmax and Gaussian error linear unit (GELU). Driven by numerical stability needs, softmax approximations (e.g., NeurIPS 2021) typically extract the maximum element of an input vector, incurring logarithmic rounds (in the input length). Existing GELU protocols (e.g., S&P 2024) use piecewise approximations with high-degree polynomials that rely heavily on secure multiplications and comparisons, which are expensive. Such complexities also hinder model owners unfamiliar with cryptography from deploying custom models.
SHAFT, our proposed system, provides a secure, handy, accurate, and fast transformer inference framework for deployment. Highlights of our contributions include
1) the first constant-round (independent of sequence length) softmax protocol for transformers, using input clipping and an ordinary differential equation characterization, and
2) a highly accurate GELU protocol on a novel characterization designed for Fourier series approximation.
Extending to broader contexts, our new protocols also apply to general neural networks that use softmax as the final layer and to transformer architectures with different activation functions. Remarkably, SHAFT outperforms state-of-the-art SIGMA (PETS 2024), which uses secret sharing, and BumbleBee (NDSS 2025), which additionally uses RLWE-based homomorphic encryption. More specifically, SHAFT reduces communication by 62rCo70% and is 1.8rCo2.4|u faster than SIGMA, while also surpassing BumbleBee in terms of running time by 2.6rCo3.7|u under LAN settings. Alongside these improvements, SHAFT attains accuracy comparable to plaintext models, confirming its numerical stability. Next in this progression, SHAFT provides an accessible open-source framework for secure and handy deployment by smoothly integrating with the Hugging Face library (EMNLP Demos 2020).
## 2025/2325
* Title: Pseudorandom Correlation Functions for Garbled Circuits
* Authors: Geoffroy Couteau, Srinivas Devadas, Alexander Koch, Sacha Servan-Schreiber
* [Permalink](https://eprint.iacr.org/2025/2325)
* [Download](https://eprint.iacr.org/2025/2325.pdf)
### Abstract
In this paper, we define the notion of pseudorandom correlation generators (PCGs) and functions (PCFs) for garbled circuit correlations.
With a Garbling PCG or PCF, two parties can non-interactively generate a virtually unbounded number of secret-shared garbled circuits and corresponding secret-shared garbled inputs. With the shares of the garbled circuit and garbled input, anyone can recover the garbled circuit and evaluate it to obtain the result of the computation in the clear.
In the process of constructing Garbling PCFs, we introduce a new primitive that we call a Topology-Adaptive PCF (TAPCF), which we construct from two different variants of the learning parity with noise (LPN) assumption. Informally, a TAPCF is a PCF that additionally allows the target correlation to be specified on-demand (i.e., at evaluation time). As a contribution of independent interest, we show that TAPCFs enable the first silent secure computation protocol with function-dependent silent preprocessing. Using our TAPCF construction as a building block, we construct a Garbling PCF that allows the parties to specify the circuit they wish to garble on the fly. Under realistic parameter settings, we estimate that, with our construction, two parties can generate one garbled circuit per second, for circuits with 10,000 AND gates.
Garbling PCFs have several applications: We provide constructions for (1) an efficient homomorphic secret-sharing scheme for specific high-depth circuits, (2) a zero-knowledge proof system over secret shares that supports checking unstructured languages, and (3) a semi-honest reusable two-round, two-party computation protocol supporting non-interactive public outputs.
## 2025/2326
* Title: Efficiently Provable Approximations for Non-Polynomial Functions
* Authors: Sriram Sridhar, Shravan Srinivasan, Dimitrios Papadopoulos, Charalampos Papamanthou
* [Permalink](https://eprint.iacr.org/2025/2326)
* [Download](https://eprint.iacr.org/2025/2326.pdf)
### Abstract
Despite phenomenal advancements in the design and implementation of Zero-knowledge proofs (ZKPs) that have made them the preeminent tool for cryptographically ensuring the correctness of a wide range of computations, existing ZK protocols still incur high prover overhead in applications that entail accurately evaluating non-polynomial functions over floating-point numbers such as machine learning, decentralized finance, orbital mechanics, and geolocation. Current state-of-the-art approaches typically emulate floating-point numbers using fixed-point representations (via quantization), and handle non-polynomial functions using lookup tables, piece-wise or low-degree polynomial approximations, which lead to sub-optimal performance and/or loss in accuracy or generality, thus limiting their potential for adoption in practice.
In this work, we present a general framework for approximating a large class of non-polynomial functions using Gauss-Legendre quadrature which also supports efficient ZKPs of correct computation. We show that increasing the desired precision up to the limits imposed by quantization only increases does not increase the multiplicative circuit depth, which stays a small constant ($\leq4$) -- which is the main factor in the error growth of an approximation. We implement and evaluate our approach in Noir/Barretenberg, and we obtain absolute errors $2-256\times$ lower than comparable baselines for most non-polynomial functions with low prover overhead. We also demonstrate an efficient prover and low errors for high-precision applications in DeFi and astronomy that require non-polynomial functions, again obtaining errors $4-64\times$ lower than the baseline approximations.
## 2025/2327
* Title: Transparent and Post-Quantum Distributed SNARK with Linear Prover Time * Authors: Zesheng Li, Xinxuan Zhang, Yi Deng
* [Permalink](https://eprint.iacr.org/2025/2327)
* [Download](https://eprint.iacr.org/2025/2327.pdf)
### Abstract
Succinct Non-interactive Arguments of Knowledge (SNARKs) allow a prover to convince a verifier of the validity of a statement using a compact proof and sublinear verification time. However, a major obstacle to the broad application of SNARKs is the high memory and computational cost required for proof generation. Distributed proof systems offer a promising solution by distributing the proving workload across multiple machines. While recent pairing-based distributed SNARKs achieve sublinear costs, they suffer from a lack of post-quantum security and transparency. Conversely, recent hash-based schemes offer these features but have been limited to quasi-linear prover time.
In this paper, we present the first fully distributed, transparent, post-quantum SNARK with a linear-time prover while maintaining polylogarithmic verification time and proof size. Our main contributions are two-fold. First, we present a distributed multivariate Polynomial IOP (PIOP) for Rank-1 Constraint Systems (R1CS) based on the Spartan framework. This is achieved by introducing a novel distributed version of the SPARK compiler, which efficiently handles the polynomial commitment scheme for sparse polynomials. Second, we propose the first transparent and post-quantum distributed polynomial commitment scheme with a linear-time prover, building upon the Brakedown framework with proof composition. By compiling our distributed polynomial commitment with both existing and newly proposed distributed PIOPs, we obtain fully distributed SNARKs for Plonkish and R1CS. Both resulting systems are transparent, post-quantum secure, and achieve linear prover time with polylogarithmic verification costs, overcoming the limitations of prior works and enhancing the scalability of zero-knowledge proof systems.
## 2025/2328
* Title: SNARGs for NP from LWE
* Authors: Ziyi Guan, Eylon Yogev
* [Permalink](https://eprint.iacr.org/2025/2328)
* [Download](https://eprint.iacr.org/2025/2328.pdf)
### Abstract
We construct the first succinct non-interactive argument (SNARG) for NP in the common reference string model based solely on the sub-exponential hardness of the learning with errors (LWE) assumption. Our scheme achieves non-adaptive security, partial succinctness with an argument size of $O(n^{0.91})$, and is plausibly post-quantum secure. Previous constructions of SNARGs from falsifiable assumptions either relied on indistinguishability obfuscation or were restricted to idealized models (e.g., the random oracle model or generic group model).
Our construction is also the first to instantiate the Micali transformation (Fiat-Shamir applied to Kilian's protocol) in the standard model with concrete hash functions. We achieve this by developing a new mechanism to securely instantiate the Fiat-Shamir hash function for interactive arguments, overcoming the known barriers that limit standard techniques to interactive proofs. As a result, our scheme refutes "universal" attacks on the Micali framework by demonstrating that there exist concrete instantiations of the underlying components for which the transformation is sound.
Our construction relies on two primitives of independent interest: a PCP with a new property which we term "shadow soundness", and a lattice-based vector commitment that provides statistical binding with respect to a hidden function.
## 2025/2329
* Title: A note on ``a fully dynamic multi-secret sharing scheme with redundant authorization''
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2025/2329)
* [Download](https://eprint.iacr.org/2025/2329.pdf)
### Abstract
We show that the secret sharing scheme [Cryptogr. Commun. 16(1): 3-20 (2024)] cannot be put into practice. (1) It confused the elements in a residue class ring modulo a prime $p$ with the points in an elliptic curve group over the finite field $F_p$. (2) It confused the underlying elliptic curve with the Lagrange interpolating curve, and falsely requires the interpolating polynomial to map a point on the elliptic curve to another point on the same elliptic curve. (3) It misuses the bit-wise XOR operator for the operands with unequal bit-length, which results in the exposure of any participant's share, and the loss of confidentiality.
## 2025/2330
* Title: Verifiable Aggregate Receipts with Applications to User Engagement Auditing
* Authors: Ioannis Kaklamanis, Wenhao Wang, Harjasleen Malvai, Fan Zhang
* [Permalink](https://eprint.iacr.org/2025/2330)
* [Download](https://eprint.iacr.org/2025/2330.pdf)
### Abstract
Accurate measurements of user engagement underpin important decisions in various settings, such as determining advertising fees based on viewership of online content, allocating public funding based on a clinicrCOs reported patient volume, or determining whether a group chat app disseminated a message without censorship.
While common, self-reporting is inherently untrustworthy due to misaligned incentives (e.g., to inflate).
Motivated by this problem, we introduce the notion of Verifiable Aggregate Receipts (VAR).
A VAR system allows an issuer to issue receipts to users and to verify the number of receipts possessed by a prover, who is given receipts upon serving users. An ideal VAR system should satisfy inflation soundness (the prover cannot overstate the count), privacy (the verifier learns only the count), and be performant for large-scale applications involving millions of users.
We formalize VAR using an ideal functionality and present two novel constructions.
Our first protocol, S-VAR, leverages bottom-up secret-sharing to enable tiered ``fuzzy'' audits, and achieves constant-size receipts regardless of the number of supported thresholds. Our second protocol, P-VAR, uses bilinear pairings to aggregate receipts into a proof verifiable in constant time, enables exact auditing, and can be extended to handle a dynamic user set. We prove both constructions secure with respect to our ideal functionality.
We implement and benchmark our VAR constructions. For a million users, issuance takes less than $2$ seconds for either scheme, and for audit proving time, P-VAR requires less than $10$ seconds and S-VAR requires less than $35$ seconds.
Compared to our schemes, baseline and existing solutions are either at least an order of magnitude slower in proving and verification time, or they do not scale to one million users.
Our benchmarks demonstrate that our VAR protocols can be used to enable verifiable and privacy-preserving user engagement auditing at scale. Finally, we showcase how VAR can be integrated with the aforementioned applications.
## 2025/2331
* Title: SUMSIG: Compact Code-Based Signatures from Sum-Check Protocols
* Authors: Debrup Chatterjee
* [Permalink](https://eprint.iacr.org/2025/2331)
* [Download](https://eprint.iacr.org/2025/2331.pdf)
### Abstract
We present SumSig, a code-based digital signature scheme that leverages sum-check protocols to reduce the reliance on repetition in FiatrCoShamir-based constructions. Instead of repeating a constant-soundness $\Sigma$-protocol many times, our approach verifies algebraic consistency of the entire witness via a single sum-check over an extension field, achieving negligible soundness error without repetition.
Our construction introduces three main ideas: (1) a representation of the syndrome decoding witness as a multilinear polynomial suitable for sum-check verification; (2) a degree-doubling binarity enforcement technique based on power-sum constraints $S_1 = S_2 = S_4 = w$ to ensure binary witnesses; and (3) a linearization helper polynomial that enables efficient simulation in the random oracle model.
For 128-bit security, SumSig yields signatures of approximately 5rCo8 KB with public keys of 50rCo100 KB, depending on the polynomial commitment scheme. This offers a different trade-off compared to existing code-based signatures such as Wave and LESS, which achieve either very small signatures with large public keys or moderate public keys with larger signatures. The resulting scheme features deterministic signing with no aborts and admits a quasi-tight reduction to the Syndrome Decoding problem in the random oracle model.
## 2025/2332
* Title: DNS-Anchored zk-SNARK Proofs: A Stateless Alternative to ACME Challenge-Response for Domain Control Validation
* Authors: Abhinav Vishnu
* [Permalink](https://eprint.iacr.org/2025/2332)
* [Download](https://eprint.iacr.org/2025/2332.pdf)
### Abstract
Domain Control Validation (DCV) is the cornerstone of trust on the web, serving as the prerequisite for issuing TLS certificates and asserting identity. The current industry standard, the Automated Certificate Management Environment (ACME) protocol, relies on synchronous, interactive challenge-response mechanisms (e.g., HTTP-01) that necessitate active server infrastructure and open network ports. This architectural requirement imposes significant friction on modern serverless, static, and air-gapped deployments, often forcing the exposure of sensitive infrastructure solely for validation purposes.
This paper presents the Portable Trust eXtensible (PTX) protocol, a novel mechanism for asynchronous, non-interactive DCV. PTX decouples the assertion of control from the delivery mechanism by utilizing Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs). We introduce a circuit design that cryptographically binds a set of ephemeral secrets (a nullifier and secret key) to a scoped metadata payloadrCocontaining audience restrictions and expiration parametersrCoanchored to the public DNS via a lightweight TXT record.
This approach eliminates the need for an active web server during validation. A prover generates a self-contained, portable, and purely stateless proof artifact that can be verified client-side by any relying party, with revocation handled via O(TTL) DNS record deletion. We implement a reference toolchain using the Groth16 proving system and the Poseidon hash function, achieving a circuit complexity of just 1,756 constraints and sub-15ms verification times on consumer hardware. Our security analysis demonstrates that PTX effectively mitigates replay attacks through context-commitment public inputs while offering a privacy-preserving alternative to interactive DCV for identity assertions in decentralized environments.
## 2025/2333
* Title: Analysis of Diffusion Properties in Generalized Feistel Ciphers under Multidimensional Linear Cryptanalysis
* Authors: Bet|+l Askin |uzdemir, Vincent Rijmen
* [Permalink](https://eprint.iacr.org/2025/2333)
* [Download](https://eprint.iacr.org/2025/2333.pdf)
### Abstract
This paper presents a unified framework for generic attacks on Generalized Feistel Ciphers, with a primary focus on Type 1, Type 2, and unbalanced contracting (U-Type 1) Feistel constructions with non-invertible round functions. In recent work, authors reveal a class of vulnerabilities exploitable via key independent multidimensional linear trails for Feistel Ciphers, yielding efficient generic distinguishing and key-recovery attacks. We extend the extended work by formalizing the application of generic multidimensional linear cryptanalysis to Generalized Feistel Ciphers. In this way, we improve upon existing results by extending the maximum number of rounds for the generic distinguishing attack to $t^2 + 2t - 1$ for Type 1 and U-Type 1, and to $2t + 3$ for Type 2. Moreover, we have the maximum number of rounds for generic key recovery attacks on (U)-Type 1 as $t^2+3t-2$ and Type 2 as $4t$. To the best of our knowledge, these findings yield the best results for the maximum number of rounds in key recovery attacks on the corresponding GFC. We further demonstrate the branch-permutation-independence of these attacks, proving that changing internal permutations does not affect the attack applicability, complexities or the maximum number of rounds for generic attacks.
The effectiveness of our attacks is validated through experiments on the first-round AES candidate CAST-256 and the MPC-friendly block cipher GMiMC. Both theoretical and experimental results confirm that our proposed branch-permutation-independent generic attacks enhance the maximum number of rounds for generic attacks for GFC and reduce complexity across various interesting cases.
## 2025/2334
* Title: Moving a Step of ChaCha in Syncopated Rhythm (Extended Version)
* Authors: Shichang Wang, Meicheng Liu, Shiqi Hou, Chengan Hou, Dongdai Lin
* [Permalink](https://eprint.iacr.org/2025/2334)
* [Download](https://eprint.iacr.org/2025/2334.pdf)
### Abstract
The stream cipher ChaCha is one of the most widely used ciphers in the real world, such as in TLS, SSH and so on. In this paper, we study the security of ChaCha via differential cryptanalysis based on probabilistic neutral bits (PNBs). We introduce the syncopation technique for the PNB-based approximation in the backward direction, which significantly amplifies its correlation by utilizing the property of ARX structure. In virtue of this technique, we present a new and efficient method for finding a good set of PNBs, and then a refined framework of key-recovery attack is formalized for round-reduced ChaCha. Further, we generalize the PNB-based approximation by a concept called probabilistic neutral expressions (PNEs). In the PNE-based framework, a new key guessing strategy is presented along with the carry-preserving technique. The new techniques allow us to break 7.5 rounds of 256-bit ChaCha, as well as to bring faster attacks on 7 rounds of 256-bit ChaCha. In addition, to the best of our knowledge, we present the first related-key attack on 256-bit ChaCha8 which is one out of three original ciphers in the ChaCha family. Regarding 128-bit ChaCha, our techniques permit us to defeat 7 rounds when excluding the last rotation.
## 2025/2335
* Title: d/v-CLSAG: Extension for Concise Linkable Spontaneous Anonymous Group Signatures
* Authors: sowle
* [Permalink](https://eprint.iacr.org/2025/2335)
* [Download](https://eprint.iacr.org/2025/2335.pdf)
### Abstract
In this paper we present a Schnorr-like linkable ring signature scheme we call d/v-CLSAG that is extension for d-CLSAG scheme. The proposed extension allows the use of different group generators for different layers of the ring members, while the original scheme assumes the use of the same generator G across all layers. We provide the security statements for the proposed updated scheme.
This work was reviewed by the Cypher Stack.
## 2025/2336
* Title: Compact Adaptively Secure Identity-Based Encryption from Middle-Product Learning with Errors
* Authors: Jingjing Fan, Xingye Lu, Man Ho Au, Siu Ming Yiu
* [Permalink](https://eprint.iacr.org/2025/2336)
* [Download](https://eprint.iacr.org/2025/2336.pdf)
### Abstract
Identity-Based Encryption (IBE) is a cryptographic primitive where any string, such as an email address, can serve as a public key. With the advent of quantum computing, post-quantum secure IBE constructions have become critical for ensuring long-term data security.
The state-of-the-art construction based on MPLWE
introduced by Fan et al. significantly advanced the field by achieving adaptive security under standard assumptions, however the size of the master public key (MPK) grows linearly with the identity length, posing scalability challenges for real-world applications.
In this work, we build on Fan et al.'s construction by employing a fully homomorphic trapdoor function to optimize the number of polynomials required for generating secret keys. This approach significantly reduces the MPK size from $O(\ell)$ polynomial vectors to $O(\ell^{1/d})$, where
$d$ is a constant. Despite this compactness, our scheme retains the same secret key and ciphertext sizes as Fan et al.'s construction and introduces no additional security assumptions.
## 2025/2337
* Title: ML-DSA-OSH: An Efficient, Open-Source Hardware Implementation of ML-DSA
* Authors: Quinten Norga, Suparna Kundu, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2025/2337)
* [Download](https://eprint.iacr.org/2025/2337.pdf)
### Abstract
ML-DSA is a post-quantum lattice-based digital signature algorithm (DSA) that the National Institute of Standards and Technology (NIST) recently standardized as FIPS 204. Remarkably, there are only a handful of published hardware designs and no open-source hardware implementations of complete ML-DSA.
In this work, we present an efficient open-source hardware (OSH) design of ML-DSA, based on a Dilithium implementation by Beckwith et al. (FPT 2021). We discuss the required modifications for migrating existing CRYSTALS-Dilithium implementations to match FIPS 204. In addition, we evaluate and compare the performance of our design with the prior art. Through optimized instruction scheduling in the ML-DSA rejection loop, which enables the pre-computation of critical variables, the average signing latency is improved by $16-36$ %. Finally, we extensively discuss potential applications and directions of research, further enabled through ML-DSA-OSH.
## 2025/2338
* Title: OHMG: One hot modular garbling
* Authors: Ariel Futoransky, Fadi Barb|ara, Ramses Fernandez, Gabriel Larotonda * [Permalink](https://eprint.iacr.org/2025/2338)
* [Download](https://eprint.iacr.org/2025/2338.pdf)
### Abstract
We propose a novel mechanism for garbling wires and gates of a logical circuit in a privacy-free environment, focusing on the authenticity of the protocol. It is based on one-hot encodings, tensor products and elliptic curve arithmetic. This scheme is designed to work with arithmetic gates, but we also show gadgets to implement transitions from binary inputs to arithmetic outputs and vice versa. For our scheme, each arithmetic gate takes at most one cyphertext of material to execute its functionality (assuming knowledge of the garbled inputs and their cleartexts). We show an application to blockchain transactions. The security of the scheme is proved in the UC setting.
## 2025/2339
* Title: SoK: Approximate Agreement
* Authors: Diana Ghinea, Chen-Da Liu-Zhang
* [Permalink](https://eprint.iacr.org/2025/2339)
* [Download](https://eprint.iacr.org/2025/2339.pdf)
### Abstract
Approximate Agreement (AA) is a relaxation of consensus that requires honest parties to output values that are close and within the honest inputs' range. Introduced as a relaxation of exact consensus, AA has become a versatile primitive with applications from blockchain oracles to cyber-physical systems.
This paper provides a systematization of knowledge (SoK) on byzantine-resilient AA in complete networks.
We mainly focus on the real-valued variant, and chart the feasibility frontiers in synchronous, asynchronous, and network-agnostic models. We compare protocols in terms of resilience, round complexity, and communication efficiency, while also clarifying overlooked details and gaps.
Beyond standard requirements on the outputs, we discuss stronger conditions, such as having the outputs \emph{close} to the honest inputs' median. Moreover, we briefly situate the real-valued AA problem within the broader landscape of AA, where other input domains such as higher-dimensional spaces and graphs introduce further challenges.
## 2025/2340
* Title: OOPS: One-time Oblivious Polynomial Signatures
* Authors: Kobi Gurkan, Philipp Jovanovic, Andrija Novakovic
* [Permalink](https://eprint.iacr.org/2025/2340)
* [Download](https://eprint.iacr.org/2025/2340.pdf)
### Abstract
We introduce one-time oblivious polynomial signatures (OOPS), a signature scheme based on polynomials over pairing-based elliptic curves that can securely produce signatures for up to a threshold of $n$ different messages. Signing more than $n$ messages allows anyone to forge signatures under the given parameters, making it necessary to reparameterize the scheme occasionally. We show that this property is not a severe limitation though by demonstrating how to build various efficient OOPS-based cryptographic protocols, including delegatable signatures, $1$-out-of-$n$ oblivious transfer, and partially oblivious PRFs.
## 2026/1
* Title: The Cokernel Pairing
* Authors: Krijn Reijnders
* [Permalink](https://eprint.iacr.org/2026/001)
* [Download](https://eprint.iacr.org/2026/001.pdf)
### Abstract
We study a new pairing, beyond the Weil and Tate pairing. The Weil pairing is a non-degenerate pairing $E[m] \times E[m] \to \mu_{m}$, which operates on the kernel of $[m]$. Similarly, when $\mu_{m} \subseteq \mathbb{F}_q^*$, the Tate pairing is a non-degenerate pairing $E[m](\mathbb{F}_q) \times E(\mathbb{F}_q) / [m]E(\mathbb{F}_q) \to \mu_{m}$, which connects the kernel and the rational cokernel of $[m]$. We define a pairing \[ \langle{\quad}\rangle_m : E(\mathbb{F}_q) / [m]E(\mathbb{F}_q) \times E(\mathbb{F}_q) / [m]E(\mathbb{F}_q) \to \mu_{m}\] on the rational cokernels of $[m]$, filling the gap left by the Weil and Tate pairing. When $E[m] \subseteq E(\mathbb{F}_q)$, this pairing is non-degenerate, and can be computed using three Tate pairings, and two discrete logarithms in $\mu_{m}$, assuming a basis for $E[m]$. For $m = \ell$ prime, this pairing allows us to study $E(\mathbb{F}_q) / [\ell]E(\mathbb{F}_q)$ directly and to simplify the computation for a basis of $E[\ell^k]$, and more generally the Sylow $\ell$-torsion. This finds natural applications in isogeny-based cryptography when computing $\ell^k$-isogenies.
## 2026/2
* Title: LatORAM: ORAMs from Lateral Stashes and Delayed Shuffling
* Authors: Sarvar Patel, Giuseppe Persiano, Joon Young Seo, Kevin Yeo
* [Permalink](https://eprint.iacr.org/2026/002)
* [Download](https://eprint.iacr.org/2026/002.pdf)
### Abstract
We study the design of Oblivious RAMs (ORAMs) that allow a client to access memory outsourced to a remote, untrusted server without revealing the clientrCOs data access pattern. We are interested in concretely efficient constructions and prior works have yielded different ORAM frameworks with various trade-offs. Tree-based constructions such as RingORAM [Ren et al., USENIXrCO15] obtain low communication overhead, but require client storage of linear position maps and two roundtrip queries. Hierarchical schemes such as FutORAMa [Asharov et al., CCSrCO23] further reduce communication at the cost of more roundtrips during queries. Finally, SQRT-ORAM [Goldreich, STOC rCO87] enables fast queries of one roundtrip and one block of communication at the cost of larger amortized communication costs.
We present two new constructions, LatORAM and Lat 2 ORAM, that simultaneously obtain the positive traits of all three types of ORAM constructions. Online queries are blazing fast with one roundtrip and a single block of communication like SQRT-ORAM. Fixing the client memory sizes for comparison, the online communication cost of our constructions are 5-8x smaller than RingORAM and 5-10x smaller than
FutORAMa even though both RingORAM and FutORAM a require multiple roundtrips per online query. Furthermore, our total amortized communication is also up to 50% smaller. To obtain our constructions, we present a new lazy approach of lateral stash growth that delays large shuffles.
Of independent interest, we present improved oblivious merging schemes for specific settings important for our ORAMs. Our constructions solely rely on symmetric cryptography.
## 2026/3
* Title: Batch Arguments with Optimal Communication
* Authors: Nico D||ttling, Giulio Malavolta, Omer Paneth
* [Permalink](https://eprint.iacr.org/2026/003)
* [Download](https://eprint.iacr.org/2026/003.pdf)
### Abstract
Batch arguments (BARGs) are non-interactive arguments for conjunctions of NP statements, with proof size that is sublinear in the number of statements.
Several previous works studied the communication complexity of BARGs, focusing both on the CRS size and on the additive overhead of the proof, defined as the difference between the proof size and the size $m$ of a single NP witness:
- Devadas et al.~[FOCS 22] constructed BARGs with additive overhead that is independent of $m$, however, their CRS size is polynomial in $m$.
- Paneth and Pass [FOCS 22] constructed BARGs where the CRS size is independent of $m$, but with higher additive overhead $m^{1-\epsilon}$.
Under the hardness of LWE, we construct BARGs where both the CRS size the additive overhead of the proof are independent of $m$.
Such BARGs can be recursively composed an unbounded polynomial number of times without losing succinctness.
Along the way, we also considerably simplify the construction of fully local somewhere extractable hash functions used in the construction of Devadas et al.
## 2026/4
* Title: TSM+ and OTSM - Correct Application of Time Sharing Masking in Round-Based Designs
* Authors: Hemin Rahimi, Amir Moradi
* [Permalink](https://eprint.iacr.org/2026/004)
* [Download](https://eprint.iacr.org/2026/004.pdf)
### Abstract
Among the countermeasures against side-channel analysis attacks, masking offers formal security guarantees and composability, yet remains challenging to implement efficiently in hardware due to physical defaults like glitches and transitions. Low-latency masking techniques aim to mitigate the performance penalties but can inadvertently compromise security in certain architectural contexts. In particular, the recently proposed Time Sharing Masking (TSM) technique enables single-cycle masked implementations with composability under the SNI and PINI notions but fails to satisfy stronger composability guarantees required in iterative designs, i.e., OPINI. In this work, we show that TSM-based constructions can exhibit first-order leakage when used in single-register feedback architecture, such as round-based implementations of ciphers. To address this, we propose two new masking schemes: TSM+, a more efficient variant of TSM satisfying only PINI (but not SNI), and OTSM, a construction satisfying OPINI, enabling secure round-based designs.
Our improved round-based masked implementations of PRINCE and AES ensure security in latency-critical applications under both glitch- and transition-extended probing model while demanding for slightly more area consumption.
--- Synchronet 3.21a-Linux NewsLink 1.2