[digest] 2025 Week 17

## In this issue

1. [2025/357] Random Number Generation from Pulsars
2. [2025/711] Fast Plaintext-Ciphertext Matrix Multiplication ...
3. [2025/712] Threshold FHE with Efficient Asynchronous Decryption
4. [2025/713] LOHEN: Layer-wise Optimizations for Neural Network ...
5. [2025/714] Exploring Key-Recovery-Friendly Differential ...
6. [2025/715] Updatable Signature with Public Tokens
7. [2025/716] Shark: Actively Secure Inference using Function ...
8. [2025/717] GKR for Boolean Circuits with Sub-linear RAM Operations
9. [2025/718] The Hardness of Learning Quantum Circuits and its ...
10. [2025/719] Packed Sumcheck over Fields of Small Characteristic ...
11. [2025/720] Towards Lightweight CKKS: On Client Cost Efficiency
12. [2025/721] Efficient Key Recovery via Correlation Power ...
13. [2025/722] One-Step Schnorr Threshold Identification
14. [2025/723] Time-Space Tradeoffs of Truncation with Preprocessing
15. [2025/724] Privacy and Security in Distributed Data Markets
16. [2025/725] Side-Channel Analysis Revisited and Evaluated
17. [2025/726] Public-Key Quantum Fire and Key-Fire From Classical ...
18. [2025/727] Securing Nested Attestation of Confidential ...
19. [2025/728] SNAIL: Verifiable Computation within 30% of Native ...
20. [2025/729] Private Information Retrieval based on Homomorphic ...
21. [2025/730] Tetris! Traceable Extendable Threshold Ring ...
22. [2025/731] The Sponge is Quantum Indifferentiable
23. [2025/732] Quantum pseudoresources imply cryptography
24. [2025/733] One More Motivation to Use Evaluation Tools, This ...
25. [2025/734] Universal Blind and Verifiable Delegated Quantum ...
26. [2025/735] Improved Rényi Arguments for Lattice-Based ...
27. [2025/736] Superglue: Fast formulae for $(2,2)$ gluing isogenies
28. [2025/737] FICS and FACS: Fast IOPPs and Accumulation via ...
29. [2025/738] Quantum Lifting for Invertible Permutations and ...
30. [2025/739] An Extended Rectangular MinRank Attack against UOV ...
31. [2025/740] Otter: Scalable Sharding-Based Atomic Broadcast ...
32. [2025/741] Improved Differential Meet-In-The-Middle ...
33. [2025/742] Seamless Post-Quantum Transition: Agile and ...
34. [2025/743] On graph based pseudo quadratic multivariate maps ...
35. [2025/744] Candidate Matchmaking Encryption from Attribute- ...
36. [2025/745] When is liquid democracy possible? On the ...
37. [2025/746] Zemlyanika — Module-LWE based KEM with the power- ...
38. [2025/747] CoinMaze: Privacy-Focused CoinJoin Protocol for Bitcoin

## 2025/357

* Title: Random Number Generation from Pulsars
* Authors: Hayder Tirmazi
* [Permalink](https://eprint.iacr.org/2025/357)
* [Download](https://eprint.iacr.org/2025/357.pdf)

### Abstract

Pulsars exhibit signals with precise inter-arrival times that are on the order of milliseconds to seconds, depending on the individual pulsar. There are subtle variations in the timing of pulsar signals. We show that these variations can serve as a natural entropy source for the creation of Random Number Generators (RNGs). We also explore the effects of using randomness extractors to increase the entropy of random bits extracted from Pulsar timing data. To evaluate the quality of the Pulsar RNG, we model its entropy as a $k$-source and use well-known cryptographic results to show its closeness to a theoretically ideal uniformly random source. To remain consistent with prior work, we also show that the Pulsar RNG passes well-known statistical tests such as the NIST test suite.



## 2025/711

* Title: Fast Plaintext-Ciphertext Matrix Multiplication from Additively Homomorphic Encryption
* Authors: Krishna Sai Tarun Ramapragada, Utsav Banerjee
* [Permalink](https://eprint.iacr.org/2025/711)
* [Download](https://eprint.iacr.org/2025/711.pdf)

### Abstract

Plaintext-ciphertext matrix multiplication (PC-MM) is an indispensable tool in privacy-preserving computations such as secure machine learning and encrypted signal processing. While there are many established algorithms for plaintext-plaintext matrix multiplication, efficiently computing plaintext-ciphertext (and ciphertext-ciphertext) matrix multiplication is an active area of research which has received a lot of attention. Recent literature have explored various techniques for privacy-preserving matrix multiplication using fully homomorphic encryption (FHE) schemes with ciphertext packing and Single Instruction Multiple Data (SIMD) processing. On the other hand, there hasn't been any attempt to speed up PC-MM using unpacked additively homomorphic encryption (AHE) schemes beyond the schoolbook method and Strassen's algorithm for matrix multiplication. In this work, we propose an efficient PC-MM from unpacked AHE, which applies Cussen's compression-reconstruction algorithm for plaintext-plaintext matrix multiplication in the encrypted setting. We experimentally validate our proposed technique using a concrete instantiation with the additively homomorphic elliptic curve ElGamal encryption scheme and its software implementation on a Raspberry Pi 5 edge computing platform. Our proposed approach achieves up to an order of magnitude speedup compared to state-of-the-art for large matrices with relatively small element bit-widths. Extensive measurement results demonstrate that our fast PC-MM is an excellent candidate for efficient privacy-preserving computation even in resource-constrained environments.



## 2025/712

* Title: Threshold FHE with Efficient Asynchronous Decryption
* Authors: Zvika Brakerski, Offir Friedman, Avichai Marmor, Dolev Mutzari, Yuval Spiizer, Ni Trieu
* [Permalink](https://eprint.iacr.org/2025/712)
* [Download](https://eprint.iacr.org/2025/712.pdf)

### Abstract

A Threshold Fully Homomorphic Encryption (ThFHE) scheme enables the generation of a global public key and secret key shares for multiple parties, allowing any threshold of these parties to collaboratively decrypt a ciphertext without revealing their individual secret keys. By leveraging the homomorphic properties of FHE, this scheme supports the distributed computation of arbitrary functions across multiple parties.  As distributed execution of cryptographic tasks
becomes popular, the demand for ThFHE schemes grows accordingly. We identify three major challenges with existing solutions. (i) They often take unrealistic assumptions with regards to the network model, assuming the threshold of parties to participate in decryption is known a-priori, available throughout multiple communication rounds, and is consistent between parties. (ii) They incur a super-linear overhead on the underlying FHE public parameters. Both issues pose challenges on scaling with the number of parties. (iii) The require heavyweight Zero-Knowledge Proofs (ZKPs) during decryption, thereby introducing a significant computational overhead in order to tolerate malicious behavior.

In this work, we introduce a \thfhe scheme that faces the above three challenges simultaneously, and is designed to scale with the number of parties N.

Our scheme operates within the well-established asynchronous communication model. At the same time, upon decryption, the ciphertext only incurs a linear 3/4N + t additive overhead on the ciphertext modulus size. Additionally, when allowed to rely on none Post Quantum (PQ)-secure additively homomorphic encryption schemes, we provide a method with an O(1) overhead, independent of N. Lastly, we propose a preprocessing technique, that allows the parties to batch and preprocess all necessary ZKPs in an offline phase, before the encrypted inputs and evaluation circuit are determined. In turn, this enables the system to effectively manage traffic spikes, by exploiting idle periods to preform the ZKPs.

We build on a ring-based FHE scheme, specifically using the BGV scheme for clarity and concreteness. Nonetheless, the techniques also apply to BFV, CKKS, and TFHE schemes.



## 2025/713

* Title: LOHEN: Layer-wise Optimizations for Neural Network Inferences over Encrypted Data with High Performance or Accuracy
* Authors: Kevin Nam, Youyeon Joo, Dongju Lee, Seungjin Ha, Hyunyoung Oh, Hyungon Moon, Yunheung Paek
* [Permalink](https://eprint.iacr.org/2025/713)
* [Download](https://eprint.iacr.org/2025/713.pdf)

### Abstract

Fully Homomorphic Encryption (FHE) presents unique challenges in programming due to the contrast between traditional and FHE language paradigms. A key challenge is selecting ciphertext configurations (CCs) to achieve the desired level of security, performance, and accuracy simultaneously. Finding the design point satisfying the goal is often labor-intensive (probably impossible), for which reason previous works settle down to a reasonable CC that brings acceptable performance. When FHE is applied to neural networks (NNs), we have observed that the distinct layered architecture of NN models opens the door for a performance improvement by using layer-wise CCs, because a globally chosen CC may not be the best possible CC for every layer individually. This paper introduces LOHEN, a technique crafted to attain high performance of NN inference by enabling to use layer-wise CC efficiently. Empowered with a cryptographic gadget that allows switching between arbitrary CCs, LOHEN allocates layer-wise CCs for individual layers tailored to their structural properties, while minimizing the increased overhead incurred by CC switching with its capability to replace costly FHE operations. LOHEN can also be engineered to attain higher accuracy, yet deliver higher performance compared to state-of-the-art studies, by additionally adopting the multi-scheme techniques in a layer-wise manner. Moreover, the developers using LOHEN are given the capability of customizing the selection policy to adjust the desired levels of performance and accuracy, subject to their demands. Our evaluation shows that LOHEN improves the NN inference performance in both of these cases when compared to the state-of-the-art. When used to improve the CKKS-only inference, LOHEN improves the NN inference performance of various NNs 1.08--2.88x. LOHEN also improves the performance of mixed-scheme NN inference by 1.34--1.75x without accuracy loss. These two results along with other empirical analyses, advocate that LOHEN can widely help improve the performance of NN inference over FHE.



## 2025/714

* Title: Exploring Key-Recovery-Friendly Differential Distinguishers for SM4 and Their Performance in Differential Attacks (Full Version)
* Authors: Bingqing Li, Ling Sun
* [Permalink](https://eprint.iacr.org/2025/714)
* [Download](https://eprint.iacr.org/2025/714.pdf)

### Abstract

In this paper, we focus on SM4, a widely used and standardized Chinese block cipher. After revisiting the previously proposed optimal 19-round differential characteristic, we observe that its applicability in differential attacks is limited by a reduced pre-sieving probability, causing the time complexity to exceed that of brute force. To overcome this issue, we employ an automated search approach to identify more promising optimal 19-round differential characteristics. By translating key properties relevant to key recovery into Boolean expressions, we uncover three structural properties common to all optimal 19-round characteristics. While these properties dictate the overall probability of the resulting 19-round distinguishers, their varying pre-sieving probabilities influence their practical effectiveness in differential attacks. Using Boolean encodings, we identify four representative key-recovery-friendly differential characteristics. We then conduct an in-depth analysis of one such characteristic and demonstrate that, when evaluated under both the hypothesis testing paradigm and the key ranking paradigm, the proposed attack requires slightly more data than existing 23-round attacks. Nonetheless, it achieves lower time and memory complexities and ensures a higher success probability, offering a valuable new avenue for differential cryptanalysis of SM4. We believe our findings enhance the understanding of SM4's differential structure and provide a solid foundation for future research on advanced key-recovery techniques that leverage these newly identified structural properties and differential characteristics.



## 2025/715

* Title: Updatable Signature with Public Tokens
* Authors: Haotian Yin, Jie Zhang, Wanxin Li, Yuji Dong, Eng Gee Lim, Dominik Wojtczak
* [Permalink](https://eprint.iacr.org/2025/715)
* [Download](https://eprint.iacr.org/2025/715.pdf)

### Abstract

The Updatable Signature (US) allows valid signatures to be updated by an update token without accessing the newly generated signing key. Cini et al. (PKC'21) formally defined this signature and gave several constructions. However, their security model requires the secrecy of the update token, which is only applicable in some specific scenarios, such as software verification in the trusted App Store. In Web3, information is usually shared via a public blockchain, and decentralized private computation is expensive. In addition, one can use the same token to update both the signing key and signatures and all signatures can be updated with a single token. The adversarial signature generated by an adversary might also be updated. Therefore, this work explores the (im)possibility of constructing an Updatable Signature with public tokens (USpt), the tokens of which are signature-dependent. Specifically, we define the updatable signature with public tokens and present its security model. Then, we present a concrete USpt scheme based on the Boneh–Lynn–Shacham signature. This variant introduces a limitation for the signer who must maintain a dataset about its signed messages or hashes of them, which is applicable in our applications.



## 2025/716

* Title: Shark: Actively Secure Inference using Function Secret Sharing
* Authors: Kanav Gupta, Nishanth Chandran, Divya Gupta, Jonathan Katz, Rahul Sharma
* [Permalink](https://eprint.iacr.org/2025/716)
* [Download](https://eprint.iacr.org/2025/716.pdf)

### Abstract

We consider the problem of actively secure two-party machine-learning inference in the preprocessing model, where the parties obtain (input-independent) correlated randomness in an offline phase that they can then use to run an efficient protocol in the (input-dependent) online phase. In this setting, the state-of-the-art is the work of Escudero et al. (Crypto 2020); unfortunately, that protocol requires a large amount of correlated randomness, extensive communication, and many rounds of interaction, which leads to poor performance.
In this work, we show protocols for this setting based on function secret sharing (FSS) that beat the state-of-the-art in all parameters: they use less correlated randomness and fewer rounds, and require lower communication and computation. We achieve this in part by allowing for a mix of boolean and arithmetic values in FSS-based protocols (something not done in prior work), as well as by relying on “interactive FSS,” a generalization of FSS we introduce. To demonstrate the effectiveness of our approach we build SHARK—the first FSS- based system for actively secure inference—which outperforms the state-of-the-art by up to 2300×.



## 2025/717

* Title: GKR for Boolean Circuits with Sub-linear RAM Operations
* Authors: Yuncong Hu, Chongrong Li, Zhi Qiu, Tiancheng Xie, Yue Ying, Jiaheng Zhang, Zhenfei Zhang
* [Permalink](https://eprint.iacr.org/2025/717)
* [Download](https://eprint.iacr.org/2025/717.pdf)

### Abstract

Succinct Non-Interactive Arguments of Knowledge (SNARKs) provide a powerful cryptographic framework enabling short, quickly verifiable proofs for computational statements.

Existing SNARKs primarily target computations represented as arithmetic circuits. However, they become inefficient when handling binary operations, as each gates operates on a few bits while still incurring the cost of multiple field operations per gate. This inefficiency stems, in part, from their inability to capture the word-level operations that are typical in real-world programs. To better reflect this computational pattern, we shift our attention to data-parallel boolean circuits, which serve as a natural abstraction of word-level operations by allowing parallel munipulation of multiple bits. To precisely characterize the prover's overheads in our scheme, we adopt the word RAM model, which aligns with the nature of modern programming languages. Under this model, we propose a novel approach to achieve SNARKs with only sub-linear prover overhead for proving boolean circuits. 

Specifically, we present an optimized GKR protocol for boolean circuits that captures the word-level operations. To achieve this, we pack multiple bits as a single univariate polynomial, and exploiting the binary nature of circuit values to enable precomputation to accelerate the sumcheck process. This optimization leads to a highly efficient prover requiring only sub-linear RAM operations. Furthermore, we introduce a sub-linear polynomial commitment scheme designed specifically for binary polynomials, which ensures efficient commitments with minimal computational overhead.

Comprehensive evaluations reveal that our scheme achieves both theoretical efficiency and substantial practical performance gains. For instance, in proving randomly generated Boolean circuits with $2^{30}$ gates, proof generation with our optimized GKR protocol completes in just 5.38 seconds, yielding a $223\times$ speedup over LogUp (Haböck, ePrint 2022), the most efficient known scheme for lookup arguments. Furthermore, in an end-to-end benchmark over the Keccak-$f$ task, our scheme achieves a $106\times$ speedup compared to Binius (Diamond et al., EUROCRYPT 2025), the state-of-the-art work for boolean circuits.



## 2025/718

* Title: The Hardness of Learning Quantum Circuits and its Cryptographic Applications
* Authors: Bill Fefferman, Soumik Ghosh, Makrand Sinha, Henry Yuen
* [Permalink](https://eprint.iacr.org/2025/718)
* [Download](https://eprint.iacr.org/2025/718.pdf)

### Abstract

We show that concrete hardness assumptions about learning or cloning the output state of a random quantum circuit can be used as the foundation for secure quantum cryptography. In particular, under these assumptions we construct secure one-way state generators (OWSGs), digital signature schemes, quantum bit commitments, and private key encryption schemes. We also discuss evidence for these hardness assumptions by analyzing the best-known quantum learning algorithms, as well as proving black-box lower bounds for cloning and learning given state preparation oracles.

Our random circuit-based constructions provide concrete instantiations of quantum cryptographic primitives whose security do not depend on the existence of one-way functions. The use of random circuits in our constructions also opens the door to NISQ-friendly quantum cryptography. We discuss noise tolerant versions of our OWSG and digital signature constructions which can potentially be implementable on noisy quantum computers connected by a quantum network. On the other hand, they are still secure against noiseless quantum adversaries, raising the intriguing possibility of a useful implementation of an end-to-end cryptographic protocol on near-term quantum computers. Finally, our explorations suggest that the rich interconnections between learning theory and cryptography in classical theoretical computer science also extend to the quantum setting.



## 2025/719

* Title: Packed Sumcheck over Fields of Small Characteristic with Application to Verifiable FHE
* Authors: Yuanju Wei, Kaixuan Wang, Binwu Xiang, Xinxuan Zhang, Yi Deng, Hailong Wang, Xudong Zhu
* [Permalink](https://eprint.iacr.org/2025/719)
* [Download](https://eprint.iacr.org/2025/719.pdf)

### Abstract

Verifiable computation over encrypted data is gaining increasing attention, and using SNARKs to provide proofs for FHE operations has emerged as a promising approach. However, the mismatch between FHE's typically small prime fields and SNARKs' larger field requirements creates verifiable FHE challenges. In this work, we construct a packed sumcheck algorithm specifically designed for small fields. This approach leverages folding and repetition techniques to maintain security without field expansion, with all operations performed on the base domain. For a domain $\mathbb{F}_p$ requiring $k$-fold expansion, our sumcheck protocol operates with $(\log k + l)$ variables, where each sumcheck statement consists of $d$ multiplied multilinear polynomial statements. The prover can complete the computation in $O(kd^2 + k^{1.807}d) \cdot 2^l$ modular multiplications over $\mathbb{F}_p$.

By exploiting the highly repetitive computational structure in bit-wise FHE bootstrapping operations, we decompose the process into a series of vector operations. Building upon the packed sumcheck technique along with the Brakedown (CRYPTO 2023) and Binius (EUROCRYPT 2025) commitment schemes, we construct an efficient proof system for these vector operations, ultimately yielding a proof system for bit-wise FHE. Our system achieves linear prover time while performing all computations on the base field, resulting in significant improvements in prover efficiency.



## 2025/720

* Title: Towards Lightweight CKKS: On Client Cost Efficiency
* Authors: Jung Hee Cheon, Minsik Kang, Jai Hyun Park
* [Permalink](https://eprint.iacr.org/2025/720)
* [Download](https://eprint.iacr.org/2025/720.pdf)

### Abstract

The large key size for fully homomorphic encryption (FHE) requires substantial costs to generate and transmit the keys. This has been problematic for FHE clients who want to delegate the computation, as they often have limited power. A recent work, Lee-Lee-Kim-No [Asiacrypt 2023], partly solved this problem by suggesting a hierarchical key management system. However, the overall key size was still several gigabytes for real-world applications, and it is barely satisfactory for mobile phones and IoT devices.

In this work, we propose new key management systems, KG+ and BTS+, which reduce the client's cost for FHE on top of Lee-Lee-Kim-No. The KG+system significantly reduces the key size without any compromise in the efficiency of homomorphic computation compared to Lee-Lee-Kim-No. The BTS+ system further reduces the key size, while it compromises only the granularity of the homomorphic computation.

In our new systems, the client generates and sends ``transmission keys'' with size-optimal parameters, and the server generates ``evaluation keys'' with computation-optimal parameters. For this purpose, we introduce a new ring-switching technique for keys to bridge keys with different parameters.
Using the new ring-switching technique, a client can transmit the transmission keys in extension rings that can generate FHE keys in the computation-efficient subring. By decoupling the rings of FHE keys during transmission and computation, we significantly reduce the communication cost for transferring FHE keys.

We provide concrete CKKS FHE parameters that the client's keys are $325$--$609$ MB and $285$ MB, by using KG+ and BTS+, respectively. Note that all parameters generate keys for CKKS with ring degree $2^{16}$, which is a conventional choice for CKKS applications to privacy-preserving machine learning. These are $3.09$--$4.37$ and $3.51$--$9.30$ times lower than Lee-Lee-Kim-No, respectively. For real-world applications, the server requires more evaluation keys for faster homomorphic computation. For the secure ResNet-20 inference, the parameters for KG+ and BTS+ result in client key sizes of $325$--$609$ MB and $285$ MB, respectively. These are $3.95$--$5.73\times$ and $4.53$--$12.25\times$ smaller than Lee-Lee-Kim-No.



## 2025/721

* Title: Efficient Key Recovery via Correlation Power Analysis on Scloud⁺
* Authors: Hangyu Bai, Fan Huang, Xiaolin Duan, Honggang Hu
* [Permalink](https://eprint.iacr.org/2025/721)
* [Download](https://eprint.iacr.org/2025/721.pdf)

### Abstract

Scloud$^{+}$ is a next-generation post-quantum key encapsulation mechanism that combines unstructured-LWE and a ternary key encoding technique to achieve efficient lattice cryptographic operations while eliminating traditional ring structure constraints. Despite its rigorously formalized theoretical security, its practical deployment faces side-channel threats, notably Correlation Power Analysis (CPA) attacks. This paper systematically investigates the physical security of its core ciphertext-key matrix multiplication module by proposing a CPA framework that integrates instruction-level timing analysis. A SoST (Sum of Squared T-values) model, inspired by multi-group Welch's t-test, is used to analyze the Hamming weight leakage during ciphertext loading. At the same time, dynamic sampling windows, combined with processor pipeline modeling, are employed to pinpoint critical leakage intervals. Exploiting the characteristics of ternary keys, an iterative recovery strategy is devised: following a predefined scan order, the candidate set $\{-1, 0, 1\}$ and partial intermediate sums are used to construct a Hamming weight model for hypothesized leakage vectors. Pearson correlation analysis and trace-count stabilization are applied within each dynamic sampling window to determine the optimal estimate for each key element. Experiments targeting 4800 key elements, illustrated through a detailed analysis of the first 32 elements, demonstrate high recovery accuracy with no more than 15 traces per element, indicating high efficiency and stability that can extend to the full key reconstruction. To thwart such CPA attacks, we have further designed and implemented a first‐order arithmetic masking countermeasure that splits the original ternary secret key into two subkeys, thereby expanding the attacker's key hypothesis space and significantly enhancing side‐channel resilience. Our results demonstrate that Scloud$^{+}$ remains vulnerable to side‐channel exploits at the implementation level, highlighting the urgent need to integrate appropriate protections into its standardization process.



## 2025/722

* Title: One-Step Schnorr Threshold Identification
* Authors: Foteinos Mergoupis-Anagnou
* [Permalink](https://eprint.iacr.org/2025/722)
* [Download](https://eprint.iacr.org/2025/722.pdf)

### Abstract

Threshold zero-knowledge protocols have not been widely adopted,
presumably due to the relevant network overhead,
complicated certification processes
and thus limited interoperability chances.
In this work, we propose $\mathsf{OSST}$,
a Schnorr-based threshold identification scheme
that is both non-interactive and non-reliant on the public shares.
Given a $(n, t)$-shared secret $x$,
the proposed protocol allows
any $t^* \ge t$ (but no less) shareholders to collectively prove
that their secret keys combine to $x$ in the sense of interpolation
without revealing any information beyond that.
On the one side, the provers do not need to engage in
multi-party computations,
sending their packets to the verifier asynchronously.
On the other side, the verification operation
involves the combined public key $y \equiv g ^ x$ alone,
meaning that the verifier does not need to
have validated and registered the individual member identities.
The protocol
can be cheaply adopted in permissionless and dynamic environments,
where no certification processes or infrastructure support
are available, and be easily integrated
with existing verifiers by means of pure software extension.
No publicly trusted setup is required beyond
the assumption that $x$ has been
distributed by means of Shamir's secret sharing
(or equivalent distribution scheme)
and that the public counterpart has been advertised correctly;
in particular, the protocol is intended to be
secure against impersonation attacks
in the plain public-key model.
We provide evidence that this has good chances to
hold true by giving a formal security proof
in the random oracle model under the
one-more discrete-logarithm hardness
($\mathsf{OMDL}$) assumption.



## 2025/723

* Title: Time-Space Tradeoffs of Truncation with Preprocessing
* Authors: Krzysztof Pietrzak, Pengxiang Wang
* [Permalink](https://eprint.iacr.org/2025/723)
* [Download](https://eprint.iacr.org/2025/723.pdf)

### Abstract

Truncation of cryptographic outputs is a technique that was recently introduced  in Baldimtsi et al. [BCCK22]. The general idea is to try out many inputs to some cryptographic algorithm until the output (e.g. a public-key or some hash value) falls into some sparse set and thus can be compressed: by trying out an expected $2^k$ different inputs one will find an output that starts with $k$ zeros.

Using such truncation one can for example save substantial gas fees on Blockchains where storing values is very expensive. While [BCCK22] show that truncation preserves the security of the underlying primitive, they only consider a setting without preprocessing. In this work we show that lower bounds on the time-space tradeoff for inverting random functions and permutations also hold with truncation, except for parameters ranges where the bound fails to hold for ''trivial'' reasons.

Concretely, it's known that any algorithm that inverts a random function or permutation with range $N$ making $T$ queries and using $S$ bits of auxiliary input must satisfy $S\cdot T\ge N\log N$.
This lower bound no longer holds in the truncated setting where one must only invert a challenge from a range of size $N/2^k$, as now one can simply save the replies to all
$N/2^k$ challenges, which requires $S=\log N\cdot N /2^k$ bits and allows to invert with $T=1$ query.

We show that with truncation, whenever $S$ is somewhat smaller than the $\log N\cdot N /2^k$ bits required to store the entire truncated function table, the known $S\cdot T\ge N\log N$ lower bound applies.



## 2025/724

* Title: Privacy and Security in Distributed Data Markets
* Authors: Daniel Alabi, Sainyam Galhotra, Shagufta Mehnaz, Zeyu Song, Eugene Wu
* [Permalink](https://eprint.iacr.org/2025/724)
* [Download](https://eprint.iacr.org/2025/724.pdf)

### Abstract

Data markets play a pivotal role in modern industries by facilitating the exchange of data for predictive modeling, targeted marketing, and research. However, as data becomes a valuable commodity, privacy and security concerns have grown, particularly regarding the personal information of individuals. This tutorial explores privacy and security issues when integrating different data sources in data market platforms. As motivation for the importance of enforcing privacy requirements, we discuss attacks on data markets focusing on membership inference and reconstruction attacks. We also discuss security vulnerabilities in decentralized data marketplaces, including adversarial manipulations by buyers or sellers. We provide an overview of privacy and security mechanisms designed to mitigate these risks. In order to enforce the least amount of trust for buyers and sellers, we focus on distributed protocols. Finally, we conclude with opportunities for future research on understanding and mitigating privacy and security concerns in distributed data markets.



## 2025/725

* Title: Side-Channel Analysis Revisited and Evaluated
* Authors: Jiangshan Long, Changhai Ou, Yukun Cheng, Kexin Qiao, Wei Cheng, Fan Zhang
* [Permalink](https://eprint.iacr.org/2025/725)
* [Download](https://eprint.iacr.org/2025/725.pdf)

### Abstract

Side-channel analysis recovers a secret by exploiting the key-dependent characteristics of the leakages. Practical techniques, such as Distance-of-Means analysis (DoM), Kolmogorov-Smirnov analysis (KSA) and Cramér-von Mises analysis (CvMA), provide valuable insights about the secret from the indirect perspectives of statistical moment and cumulative distribution function (CDF) respectively, circumventing the direct and costly estimation of leakage probability densities and therefore enabling wider applicability in practice. Though both the perspectives are informative, their relationships in the context of side-channel analysis remain unclear. In other words, the fundamental questions of "which one is better?'' and ``why and under what circumstances?" leave as open problems. In this paper, we introduce the probability-probability (PP) plot in statistics as a common framework for explaining the mathematical foundations of CDF-based techniques, which facilitates an intuitive understanding of different variant strategies. Then, inspired by the growth pattern of the PP curve, we propose a novel distinguisher based on the famous Mann-Kendall test, where measurements are managed with ordinality and nominality. This goodness-of-fit test checks whether a key-dependent binary sequence originates from a random binomial distribution, by efficiently searching potential label clusters. Finally, we explore the symmetry and dual counterpart of CDF in mathematics, introducing the quantile-quantile (QQ) plot and develop an interesting technique based on the inverse cumulative distribution function (ICDF). We present a general discussion of its bridging role, regarding detail capture as well as signal-to-noise ratio (SNR). On this basis, we establish the relationships among moment-based, ICDF-based, and CDF-based techniques, which additionally allows for bounding the security level of the CDF-based techniques using well-established metrics that are originally proposed for evaluating the traditional moment-based family. Experiments across various settings validate our theoretical findings and demonstrate the effectiveness of the two proposed distinguishers.



## 2025/726

* Title: Public-Key Quantum Fire and Key-Fire From Classical Oracles
* Authors: Alper Çakan, Vipul Goyal, Omri Shmueli
* [Permalink](https://eprint.iacr.org/2025/726)
* [Download](https://eprint.iacr.org/2025/726.pdf)

### Abstract

Quantum fire was recently formalized by Bostanci, Nehoran and Zhandry (STOC’25). This notion considers a distribution of quantum states that can be efficiently cloned, but cannot be converted into a classical string. Previously, work of Nehoran and Zhandry (ITCS’24) showed how to construct quantum fire relative to an inefficient unitary oracle. Later, the work of Bostanci, Nehoran, Zhandry gave a candidate construction based on group action assumptions, and proved the correctness of their scheme; however, even in the classical oracle model they only conjectured the security, and no security proof was given.

In this work, we give the first construction of public-key quantum fire relative to a classical oracle, and prove its security unconditionally. This gives the first classical oracle seperation between the two fundamental principles of quantum mechanics that are equivalent in the information-theoretic setting: no-cloning and no-telegraphing.

Going further, we introduce a stronger notion called quantum key-fire where the clonable fire states can be used to run a functionality (such as a signing or decryption key), and prove a secure construction relative to a classical oracle. As an application of this notion, we get the first public-key encryption scheme whose secret key is clonable but satisfies unbounded leakage-resilience (Cakan, Goyal, Liu-Zhang, Ribeiro [TCC’24]), relative to a classical oracle. Unbounded leakage-resilience is closely related to, and can be seen as a generalization of the notion of no-telegraphing.

For all of our constructions, the oracles can be made efficient (i.e. polynomial time), assuming the existence of post-quantum one-way functions



## 2025/727

* Title: Securing Nested Attestation of Confidential Serverless Computing without Intra-Enclave Isolation
* Authors: Atsuki Momose, Kailun Qin, Ao Sakurai, Mona Vij
* [Permalink](https://eprint.iacr.org/2025/727)
* [Download](https://eprint.iacr.org/2025/727.pdf)

### Abstract

Confidential Computing-as-a-Service has gained significant attention in recent years, driven by rapid advances in Trusted Execution Environment (TEE) technology. Among various architectures, confidential serverless computing has emerged as a promising model. A common approach to designing confidential serverless computing involves decoupling the client workload from the initial enclave image and dynamically provisioning the workload at runtime. This enables both offloading the costly enclave bootstrapping and maintaining a fixed reference measurement for attestation. This decoupling necessitates nested attestation, where the client’s workload is attested via a custom attestation module embedded in a platform-attested enclave established at boot time. The challenge in designing nested attestation, however, is to distinguish fresh enclaves from the used ones to prevent enclave reuse. Specifically, a previously used enclave may be compromised and its attestation module tampered with. If the enclave is reused for another workload, it could bypass runtime attestation, allowing unverified code to execute.

In this paper, we present a novel approach to securing nested attestation for confidential serverless computing on Intel Software Guard Extensions (Intel SGX). Unlike prior works, our approach does not rely on intra-enclave isolation techniques to sandbox the client’s workload. Instead, we leverage the Key Separation and Sharing (KSS) feature of Intel SGX to track and prevent enclave reuse based on its immutable IDs. We develop a prototype system for confidential serverless computing for Python workloads, incorporating our nested attestation scheme, and present an empirical evaluation of its performance.

We believe our scheme unveils a unique yet previously overlooked role of KSS---post-compromise identification, with broader implications beyond serverless computing. As a concrete example, we demonstrate how KSS can be leveraged to implement an enclave-binding TPM on Intel SGX, which is of independent interest.



## 2025/728

* Title: SNAIL: Verifiable Computation within 30% of Native Speed
* Authors: Ole Hylland Spjeldnæs
* [Permalink](https://eprint.iacr.org/2025/728)
* [Download](https://eprint.iacr.org/2025/728.pdf)

### Abstract

SNAIL (Succinct, Non-interactive, Alon-compressed, Instant argument for Layered circuits) turns any depth-\(d\) arithmetic circuit into a non-interactive argument whose prover runs within 
\(1 + c(d,k,n)\) of plain circuit execution, where 
\(c(d,k,n) = \frac{3\,(k+n+1)}{k\,d + n + 1}\).
For the representative choice \(k = n = 4\) and \(24 \le d \le 32\) this means only 21–28 % overhead.

Core idea: 
A constant-round zerocheck based on a difference-driven Alon decomposition compresses all \(d\) layers into one multivariate identity.  Fiat–Shamir in the random-oracle model yields a transparent argument whose hot loop uses only field additions and multiplications (no MSMs, FFTs, or Merkle trees).

Cost summary: with \(k = n = 4\) and \(24 \le d \le 32\)
\[
  T_{\text{prov}}(S,d)=\Bigl(1+\frac{6.75}{d}\Bigr)S,\qquad
  |\pi|=(d^{2}+2d)(4d+1),\qquad
  \varepsilon_{\text{sound}}=\frac{4nd}{|\mathbb F|}.
\]

A 2.6-billion-gate trace at \(d = 32\) is proven in \(\approx 40\;\text{ms}\) on an RTX-4090 and verified on a smartphone in \(< 1\;\text{ms}\).

Width scalability:
Proof size depends only on depth, so widening to billions of parallel gates leaves the verifier unchanged—ideal for ultra-wide workloads such as live-audited VM traces.

Security: 
The six-round interactive core is statistically sound; the Fiat–Shamir variant is computationally sound in the random-oracle model and needs no trusted setup.

Implications:
SNAIL shows that a prover can run near real-time on commodity GPUs while emitting proofs small enough for mobile light clients, enabling applications such as live-streamed provable gaming, pay-per-cycle cloud nodes, and always-on verifiable CPUs.



## 2025/729

* Title: Private Information Retrieval based on Homomorphic Encryption, Revisited
* Authors: Jaeseon Kim, Jeongeun Park, Hyewon Sung
* [Permalink](https://eprint.iacr.org/2025/729)
* [Download](https://eprint.iacr.org/2025/729.pdf)

### Abstract

Private information retrieval (PIR) enables a client to retrieve data from a server while preserving the confidentiality of the client's query. When PIR is instantiated with fully homomorphic encryption (FHE), the protocol becomes non-interactive, requiring only a query-answer exchange, and it achieves asymptotically optimal communication and computation complexity. Although several FHE-based PIR protocols have been practically implemented with the desired properties, there has been little detailed comparison among them. As a result, it remains unclear which protocol is most efficient in practice with respect to various aspects such as performance and scalability.

 In this paper, we revisit existing protocols by categorizing them into two different structures in order to analyze the advantages and disadvantages of each class in detail, with a focus on practical implementations. Furthermore, we introduce and compare various homomorphic algorithms that can be utilized for query optimization, discussing the strengths and limitations of each. Finally, with the goal of identifying the most efficient protocol in terms of computational cost and memory usage, based on database size. Additionally, we address common misconceptions that may lead to inefficient choices in real-world deployment scenarios and offer the best solutions.
Consequently, our analysis and experimental results demonstrate that the less-explored design achieves a 90% reduction in communication cost and an 8× decrease in computational overhead compared to the other one, challenging the common misconception.



## 2025/730

* Title: Tetris! Traceable Extendable Threshold Ring Signatures and More
* Authors: Gennaro Avitabile, Vincenzo Botta, Dario Fiore
* [Permalink](https://eprint.iacr.org/2025/730)
* [Download](https://eprint.iacr.org/2025/730.pdf)

### Abstract

Traceable ring signatures enhance ring signatures by adding an accountability layer. Specifically, if a party signs two different messages within the protocol, their identity is revealed.  Another desirable feature is $\textit{extendability}$. In particular, $\textit{extendable threshold}$ ring signatures (ETRS) allow to $\textit{non-interactively}$ update already finalized signatures by enlarging the ring or the set of signers.

Combining traceability and extendability in a single scheme is unexplored and would offer a new tool for privacy-preserving voting schemes in scenarios where the voters are not known in advance.
In this paper, we show how to reconcile both properties by introducing and constructing a new cryptographic primitive called Tetris.
Notably, our Tetris construction simultaneously achieves strong anonymity and linear-size signatures, which is the main technical challenge in existing techniques.
To solve this challenge, we develop a new approach to traceability that leads to several conceptual and technical contributions. Among those, we introduce and construct, based on Groth-Sahai proofs, $\textit{extendable}$ shuffle arguments that can be $\textit{non-interactively}$ updated by several provers.



## 2025/731

* Title: The Sponge is Quantum Indifferentiable
* Authors: Gorjan Alagic, Joseph Carolan, Christian Majenz, Saliha Tokat
* [Permalink](https://eprint.iacr.org/2025/731)
* [Download](https://eprint.iacr.org/2025/731.pdf)

### Abstract

The sponge is a cryptographic construction that turns a public permutation into a hash function. When instantiated with the Keccak permutation, the sponge forms the NIST SHA-3 standard. SHA-3 is a core component of most post-quantum public-key cryptography schemes slated for worldwide adoption.

While one can consider many security properties for the sponge, the ultimate one is \emph{indifferentiability from a random oracle}, or simply \emph{indifferentiability}. The sponge was proved indifferentiable against classical adversaries by Bertoni et al. in 2008. Despite significant efforts in the years since, little is known about sponge security against quantum adversaries, even for simple properties like preimage or collision resistance beyond a single round. This is primarily due to the lack of a satisfactory quantum analog of the lazy sampling technique for permutations.

In this work, we develop a specialized technique that overcomes this barrier in the case of the sponge. We prove that the sponge is in fact indifferentiable from a random oracle against quantum adversaries. Our result establishes that the domain extension technique behind SHA-3 is secure in the post-quantum setting. Our indifferentiability bound for the sponge is a loose $O(\mathsf{poly}(q) 2^{-\min(r, c)/4})$, but we also give bounds on preimage and collision resistance that are tighter.



## 2025/732

* Title: Quantum pseudoresources imply cryptography
* Authors: Alex B. Grilo, Álvaro Yángüez
* [Permalink](https://eprint.iacr.org/2025/732)
* [Download](https://eprint.iacr.org/2025/732.pdf)

### Abstract

While one-way functions (OWFs) serve as the minimal assumption for computational cryptography in the classical setting, in quantum cryptography, we have even weaker cryptographic assumptions such as pseudo-random states, and EFI pairs, among others. Moreover, the minimal assumption for computational quantum cryptography remains an open question. Recently, it has been shown that pseudoentanglement is necessary for the existence of quantum cryptography (Goulão and Elkouss 2024), but no cryptographic construction has been built from it.

 In this work, we study the cryptographic usefulness of quantum pseudoresources —a pair of families of quantum states that exhibit a gap in their resource content yet remain computationally indistinguishable. We show that quantum pseudoresources imply a variant of EFI pairs, which we call EPFI pairs, and that these are equivalent to quantum commitments and thus EFI pairs. Our results suggest that, just as randomness is fundamental to classical cryptography, quantum resources may play a similarly crucial role in the quantum setting.

Finally, we focus on the specific case of entanglement, analyzing different definitions of pseudoentanglement and their implications for constructing EPFI pairs. Moreover, we propose a new cryptographic functionality that is intrinsically dependent on entanglement as a resource.



## 2025/733

* Title: One More Motivation to Use Evaluation Tools, This Time for Hardware Multiplicative Masking of AES
* Authors: Hemin Rahimi, Amir Moradi
* [Permalink](https://eprint.iacr.org/2025/733)
* [Download](https://eprint.iacr.org/2025/733.pdf)

### Abstract

Safeguarding cryptographic implementations against the increasing threat of Side-Channel Analysis (SCA) attacks is essential. Masking, a countermeasure that randomizes intermediate values, is a cornerstone of such defenses. In particular, SCA-secure implementation of AES, the most-widely used encryption standard, can employ Boolean masking as well as multiplicative masking due to its underlying Galois field operations. However, multiplicative masking is susceptible to vulnerabilities, including the zero-value problem, which has been identified right after theintroduction of multiplicative masking. At CHES 2018, De Meyer et al. proposed a hardware-based approach to manage these challenges and implemented multiplicative masking for AES, incorporating a Kronecker delta function and randomness optimization.
In this work, we evaluate their design using the PROLEAD evaluation tool under the glitch- and transition-extended probing model. Our findings reveal a critical vulnerability in their first- and second-order implementation of the Kronecker delta function, stemming from the employed randomness optimization. This leakage compromises the security of their presented masked AES Sbox. After pinpointing the source of such a leakage, we propose an alternative randomness optimization for the first-order design to address this issue, and demonstrate its effectiveness through rigorous evaluations by means of PROLEAD.



## 2025/734

* Title: Universal Blind and Verifiable Delegated Quantum Computation with Classical Clients
* Authors: Vicent Esteve Voltes
* [Permalink](https://eprint.iacr.org/2025/734)
* [Download](https://eprint.iacr.org/2025/734.pdf)

### Abstract

Delegation of quantum computation in a trustful way is one of the most fundamental challenges toward the realization of future quantum cloud computing. While considerable progress has been made, no known protocol provides a purely classical client with universal delegated quantum computation while simultaneously ensuring blindness (input privacy), verifiability (soundness), and robustness against quantum noise—a feat that must be achieved under stringent cryptographic assumptions and with low overhead.

In this work, I introduce UVCQC, a new delegation framework that, for the first time, realizes a fully composable protocol for securely delegating quantum computations to an untrusted quantum server from a classical client. My scheme employs trap-based quantum authentication, post-quantum cryptographic commitments, and zero-knowledge proofs to provide full guarantees: the client remains purely classical; the server learns nothing about the computation; and any attempt to deviate from the specified circuit is detected with high probability.

I rigorously prove completeness, soundness, and perfect blindness of the protocol and demonstrate its universal composability against unbounded quantum adversaries. Furthermore, I propose a thermodynamically inspired verification mechanism based on energy dissipation and entropy change, enabling physically testable verification independent of cryptographic assumptions.

Beyond its core architecture, UVCQC is deeply intertwined with multidisciplinary frameworks: it admits a game-theoretic formulation where honesty is a Nash equilibrium, an information-theoretic treatment grounded in Holevo bounds, a categorical model via compact closed structures, and novel cryptographic enhancements based on isogeny-based primitives and topological invariants.

This research offers a scalable and unified solution to the blind and verifiable delegation problem, pushing forward the theoretical and practical frontiers of secure quantum computation—and opening a tangible path toward trustable quantum cloud services for classical users.



## 2025/735

* Title: Improved Rényi Arguments for Lattice-Based Threshold Encryption
* Authors: Katharina Boudgoust, Anamaria Costache
* [Permalink](https://eprint.iacr.org/2025/735)
* [Download](https://eprint.iacr.org/2025/735.pdf)

### Abstract

Threshold encryption schemes provide a common tool to secure a public-key encryption scheme against single point of failure attacks. Despite the success of lattices in building fully-homomorphic and presumably quantum-resistant encryption schemes, the task of thresholdizing those schemes remains challenging.. The major bottleneck in the standard approach is the use of statistical noise flooding, leading to a significant efficiency loss and the need of stronger hardness assumptions. Recent works have replaced the heavy statistical noise flooding by a lighter one using the Rényi divergence. The new Rényi noise flooding both improves the efficiency and allows to use weaker hardness assumptions. However, arguing semantic security of lattice-based threshold schemes in the presence of Rényi noise flooding showed to be challenging. Chowdhury et al. (IACR ePrint'22) argued in the fully-homomorphic case that the Rényi divergence directly applies for semantic security by making use of an existing framework called public sampleability.

In this work, we argue that their public sampleability framework was neither sufficient nor correctly used. To address both issues, we strengthen the framework and thoroughly apply it to prove semantic security of generic lattice-based threshold encryption constructions. We distinguish between the plain public-key and the fully-homomorphic settings, as different security notions are achieved. As a byproduct, this shows that the proof detour via one-way security made by Boudgoust and Scholl (Asiacrypt'23) was superfluous, now leading to tighter proofs in the standard model.



## 2025/736

* Title: Superglue: Fast formulae for $(2,2)$ gluing isogenies
* Authors: Max Duparc
* [Permalink](https://eprint.iacr.org/2025/736)
* [Download](https://eprint.iacr.org/2025/736.pdf)

### Abstract

We study the structure of theta structure on products of elliptic curves, detailing their construction through the symmetries induced by $4$-torsion points. In particular, we show how these symmetries allow the computation of theta structures projectively, thus avoiding the use of modular inversions.
Furthermore, we explore the self-similarity of the matrix representation of theta structures, arising from the action of the canonical $2$-torsion point in the Kummer line. Combined with the sparsity of some $4$-torsion points, this structure leads to new formulae for computing gluing $(2,2)$ isogenies that require significantly fewer precomputations and arithmetic operations.
These new equations also naturally support the evaluation of points on the quadratic twist at a negligible additional cost, without requiring operations in a field extension.



## 2025/737

* Title: FICS and FACS: Fast IOPPs and Accumulation via Code-Switching
* Authors: Anubhav Baweja, Pratyush Mishra, Tushar Mopuri, Matan Shtepel
* [Permalink](https://eprint.iacr.org/2025/737)
* [Download](https://eprint.iacr.org/2025/737.pdf)

### Abstract

Recent work on IOP-based succinct arguments has focused on developing IOPs that improve prover efficiency by relying on linear-time encodable codes. We present two new schemes for improving the efficiency of such succinct arguments:

$\quad \bullet$ $\mathsf{FICS}$, an IOP of proximity for multilinear polynomial evaluation that, like prior work Blaze [EUROCRYPT 2025] achieves linear prover time, but additionally reduces the verifier oracle query complexity to $O(\lambda \log \log n + \log n)$ for codewords of length $n$.
$\quad \bullet$ $\mathsf{FACS}$, an accumulation scheme for NP that achieves linear prover time and $O(\lambda)$ oracle queries per step of the accumulation.

Both schemes support a large class of linear-time encodable codes, including systematic LDPC codes and tensor codes of linear-time encodable codes.

We obtain our results by extending and formalizing the framework of Interactive Oracle Reductions (IORs) introduced by Ben-Sasson et al. [TCC 2019]. In particular, we develop new IORs for "codeswitching" tensor codes (Ron-Zewi and Rothblum [JACM 2024]), and also develop a new notion of knowledge soundness for IORs that allows us to easily compose IORs and to prove the security of our schemes in the non-interactive setting, even if the underlying codes are not known to be decodable in polynomial time.



## 2025/738

* Title: Quantum Lifting for Invertible Permutations and Ideal Ciphers
* Authors: Alexandru Cojocaru, Minki Hhan, Qipeng Liu, Takashi Yamakawa, Aaram Yun
* [Permalink](https://eprint.iacr.org/2025/738)
* [Download](https://eprint.iacr.org/2025/738.pdf)

### Abstract

In this work, we derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models. These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries.

By applying these lifting theorems, we improve previous results and obtain new quantum query complexity bounds and post-quantum security results. Notably, we derive tight bounds for the quantum hardness of the double-sided zero search game and establish the post-quantum security for the preimage resistance, one-wayness, and multi-collision resistance of constant-round sponge, as well as the collision resistance of the Davies-Meyer construction.



## 2025/739

* Title: An Extended Rectangular MinRank Attack against UOV and Its Variants
* Authors: Toshihiro Suzuki, Hiroki Furue, Takuma Ito, Shuhei Nakamura, Shigenori Uchiyama
* [Permalink](https://eprint.iacr.org/2025/739)
* [Download](https://eprint.iacr.org/2025/739.pdf)

### Abstract

Multivariate public key cryptography (MPKC) is considered a promising candidate for post-quantum cryptography, with its security relying on the hardness of solving systems of multivariate quadratic equations.

Among MPKC schemes, the unbalanced oil and vinegar (UOV) and its variants have been actively studied. Pébereau and Luyten showed that the Kipnis–Shamir attack and the singular point attack can be described within the same framework using the Jacobian matrix.

In this study, we demonstrate that the rectangular MinRank attack can also be described within this framework. Furthermore, by leveraging this framework, we extend the feasible target ranks of the rectangular MinRank attack and use this extended attack to analyze the security of UOV and its variants. In conclusion, we confirm that the currently proposed parameters for UOV, MAYO, QR-UOV, and SNOVA are resistant to this attack.



## 2025/740

* Title: Otter: Scalable Sharding-Based Atomic Broadcast with Abortable Fork Detection
* Authors: Xin Wang, Xiao Sui, Sisi Duan
* [Permalink](https://eprint.iacr.org/2025/740)
* [Download](https://eprint.iacr.org/2025/740.pdf)

### Abstract

Sharding is a generic approach to enhance the scalability of distributed systems. In recent years, many efforts have been made to scale the consensus mechanism of blockchains from sharding. A crucial research question is how to achieve the sweet spot of having a relatively small shard size (to achieve decent performance) while achieving an overwhelming probability of correctness (so the system is safe and live). Many recent works fall into the two-layer design that uses some coordinating shards to monitor the correctness of other shards (CCS 2022, NDSS 2024, INFOCOM 2023). All of them involve expensive communication costs between the shards, significantly degrading performance.

We present Otter, a scalable partially synchronous sharding-based Byzantine fault-tolerant atomic broadcast (ABC) protocol. We use coordinating shards in a completely new way. In particular, we randomly sample coordinating shards to directly participate in the consensus protocol. Such a random sampling mechanism makes it possible to analyze the correctness of the ABC protocol using a probabilistic model. In this way, we can significantly lower the shard size (informally, from over 1,200 in previous work to around 100) without lowering the probability of correctness. We also present a new notion called abortable fork detection (AFD) that might be of independent interest. Our evaluation results on Amazon EC2 using up to 1,000 replicas show that Otter achieves up to 4.38x the throughput of the state-of-the-art protocol.



## 2025/741

* Title: Improved Differential Meet-In-The-Middle Cryptanalysis on SIMON and Piccolo
* Authors: Weiqing Deng, Jianing Zhang, Haoyang Wang
* [Permalink](https://eprint.iacr.org/2025/741)
* [Download](https://eprint.iacr.org/2025/741.pdf)

### Abstract

Differential meet-in-the-middle (MITM) cryptanalysis, introduced by Boura et al. at CRYPTO 2023, has been demonstrated to be an effective technique for analyzing the security of block ciphers. In this paper, we introduce an improved parallel partitioning technique, and incorporate it into a new framework with a flexible key recovery strategy. This framework is applicable to both SPN and Feistel ciphers. We apply the new framework to SIMON and Piccolo-128 for demonstration. In particular, we also develop an MILP-based tool for searching full attacks on Piccolo-128.  For SIMON48/96, we propose the best attack, reaching 26 rounds against 25 rounds previously. For other versions of SIMON, we extend the best previous differential attacks by one or two rounds. In the case of Piccolo-128, while no current differential attacks show promising results, our differential MITM attack reaches 15 rounds, matching the same number of rounds of the best impossible differential attack.



## 2025/742

* Title: Seamless Post-Quantum Transition: Agile and Efficient Encryption for Data-at-Rest
* Authors: Stephan Krenn, Thomas Lorünser, Sebastian Ramacher, Federico Valbusa
* [Permalink](https://eprint.iacr.org/2025/742)
* [Download](https://eprint.iacr.org/2025/742.pdf)

### Abstract

As quantum computing matures, its impact on traditional cryptographic protocols becomes increasingly critical, especially for data-at-rest scenarios where large data sets remain encrypted for extended periods of time.
This paper addresses the pressing need to transition away from pre-quantum algorithms by presenting an agile cryptosystem that securely and efficiently supports post-quantum Key Encapsulation Mechanisms (KEMs).
The proposed solution is based on combining a CCA-secure KEM with a robust Authenticated Encryption scheme, allowing only the dynamic component - the symmetric key encapsulation - to be updated when migrating to new cryptographic algorithms.
This approach eliminates the need to re-encrypt potentially massive data payloads, resulting in significant savings in computational overhead and bandwidth.
We formalize the concept of cryptoagility through an agile-CCA security model, which requires that neither the original ciphertext nor any updated version reveals meaningful information to an attacker.
A game-based proof shows that the overall construction remains agile-CCA secure if the underlying KEM and AE are individually CCA secure under a random oracle assumption.
The result is a future-proof scheme that eases the transition to post-quantum standards, enabling enterprises and cloud storage providers to protect large amounts of data with minimal disruption while proactively mitigating emerging quantum threats.



## 2025/743

* Title: On graph based pseudo quadratic multivariate maps  of prescribed degree as instruments of key establishment.
* Authors: Vasyl Ustimenko, Tymoteusz Chojecki
* [Permalink](https://eprint.iacr.org/2025/743)
* [Download](https://eprint.iacr.org/2025/743.pdf)

### Abstract

Let us assume that one of two trusted parties  (administrator) manages the information system (IS) and another one (user) is going to use the resources of this IS during the certain time interval. So they need establish secure user’s access password to the IS resources of this system via selected authenticated key exchange protocol. So they need  to communicate via insecure communication channel and secretly con-struct a cryptographically strong session key that can serve for the establishment of secure  passwords in the form of tuples in certain alphabet during the certain time interval. Nowadays selected protocol has to be postquantum secure. We propose the implementation of this scheme in terms of Symbolic Computa-tions. The key exchange protocol is one of the key exchange algorithms of Noncommutative Cryptography with the platform of multivariate transformation of the affine space over selected finite commutative ring. The session key is a multivariate map on the affine space.  Platforms and multivariate maps are construct-ed in terms of Algebraic Graph Theory.



## 2025/744

* Title: Candidate Matchmaking Encryption from Attribute-Based Encryption Schemes
* Authors: Zhuang Shan, Leyou Zhang, Fuchun Guo, Yong Yu
* [Permalink](https://eprint.iacr.org/2025/744)
* [Download](https://eprint.iacr.org/2025/744.pdf)

### Abstract

We were deeply impressed by the paper by Ateniese et al., published in Crypto 2019. In it, they presented a black-box construction of matchmaking encryption (ME) based on functional encryption. In our work, we propose an ME scheme based on standard assumptions in the standard model. This scheme has been proven to be secure under the learning with error (LWE) assumption. Our ME scheme is achieved through a novel framework of bilateral-policy attribute-based encryption (BP-ABE) and a new intermediate primitive termed a perturbed pseudorandom generator (PPRG), which facilitates the implementation of authentication functionality by replacing non-interactive zero-knowledge proof functionality.

In the scheme presented in this paper, the user's "public key" is generated using Hamming correlation robustness and user attributes. Note that the 'public key' is not public. In order to preserve the privacy of the two parties involved in matchmaking encryption, our BP-ABE scheme does not use the 'public key' directly to encrypt the plaintext. Instead, the message sender selects matching attributes and uses a Hamming correlation robustness and homomorphic pseudorandom function (HPRF) to generate temporary public keys and hide the public key and user attributes.

When these temporary public keys satisfy the access policy, the receiver can decrypt the data using their private key. Regarding the authentication function of matchmaking encryption, this paper proposes a non-interactive privacy set intersection (PSI) scheme based on HPRF and PPRG. The message sender encrypts their 'public key' using the proposed PSI scheme as part of the ciphertext. The receiver also encrypts their 'public key' using the proposed PSI scheme and matches the attributes, thereby completing the message authentication function. We consider our approach to be a significant departure from existing constructions, despite its simplicity.



## 2025/745

* Title: When is liquid democracy possible? On the manipulation of variance.
* Authors: Krishnendu Chatterjee, Seth Gilbert, Stefan Schmid, Jakub Svoboda, Michelle Yeo
* [Permalink](https://eprint.iacr.org/2025/745)
* [Download](https://eprint.iacr.org/2025/745.pdf)

### Abstract

Liquid democracy is a transitive vote delegation mechanism over voting graphs..  It enables each voter to delegate their vote(s) to another better-informed voter, with the goal of collectively making a better decision.
The question of whether liquid democracy outperforms direct voting has been previously studied in the context of local delegation mechanisms (where voters can only delegate to someone in their neighbourhood) and binary decision problems.  It has previously been shown that it is impossible for local delegation mechanisms to outperform direct voting in general graphs.  This raises the question: for which classes of graphs do local delegation mechanisms yield good results?

In this work, we analyse (1) properties of specific graphs and (2) properties of local delegation mechanisms on these graphs, determining where local delegation actually outperforms direct voting.
We show that a critical graph property enabling liquid democracy is that the voting outcome of local delegation mechanisms preserves a sufficient amount of variance, thereby avoiding situations where delegation falls behind direct voting.
These insights allow us to prove our main results, namely that there exist local delegation mechanisms that perform no worse and in fact quantitatively better than direct voting in natural graph topologies like complete, random $d$-regular, and bounded degree graphs, lending a more nuanced perspective to previous impossibility results.



## 2025/746

* Title: Zemlyanika — Module-LWE based KEM with the power-of-two modulus, explicit rejection and revisited decapsulation failures
* Authors: Alexey S. Zelenetsky, Peter G. Klyucharev
* [Permalink](https://eprint.iacr.org/2025/746)
* [Download](https://eprint.iacr.org/2025/746.pdf)

### Abstract

This work introduces Zemlyanika, a post-quantum IND-CCA secure key encapsulation mechanism based on the Module-LWE problem. The high-level design of Zemlyanika follows a well-known approach where a passively secure public-key encryption scheme is transformed into an actively secure key encapsulation mechanism using the Fujisaki-Okamoto transform.

    Our scheme features three main elements: a power-of-two modulus, explicit rejection, and revised requirements for decapsulation error probability.

    The choice of a power-of-two modulus is atypical for Module-LWE based schemes due to the unavailability of Number Theoretic Transform (NTT). However, we argue that this option offers advantages that are often underestimated. We employ explicit rejection because it is more efficient than implicit rejection. Recent works show that both types of rejection are equally secure, so we do not reduce the security by this choice. Finally, we present compelling arguments that the probability of decapsulation failure may be higher than commonly accepted. This allows us to increase performance and security against attacks on the Module-LWE.



## 2025/747

* Title: CoinMaze: Privacy-Focused CoinJoin Protocol for Bitcoin
* Authors: Dmitry Astakhin
* [Permalink](https://eprint.iacr.org/2025/747)
* [Download](https://eprint.iacr.org/2025/747.pdf)

### Abstract

Bitcoin is based on the Blockchain, an open ledger containing information about each transaction in the Bitcoin network. Blockchain serves many purposes, but it allows anyone to track all transactions and
activities of each Bitcoin address. The privacy of the network is being threatened by some organizations that track transactions. Tracking and subsequent filtering of coins lead to the loss of exchangeability of Bitcoin.

Despite Bitcoin’s transparency, it is possible to increase user privacy using a variety of existing methods. One of these methods is called CoinJoin, was proposed by Bitcoin developer Greg Maxwell in 2013.
This technology involves combining several users transactions to create a single transaction with multiple inputs and outputs, which makes transaction analysis more complicated.

This work describes the CoinMaze, a privacy-focused CoinJoin protocol based on the keyed-verification
anonymous credentials (KVAC).