From Newsgroup: sci.crypt

## In this issue
1. [2025/1288] New Proof for Plain OAEP: Post-Quantum Security ...
2. [2025/1655] Lattice-based Multi-message Multi-recipient KEM/PKE ...
3. [2025/1802] Zyga: Optimized Zero-Knowledge Proofs with Dynamic ...
4. [2025/1825] Quantumly Computing S-unit Groups in Quantified ...
5. [2025/1953] Adaptively Secure Partially Non-Interactive ...
6. [2025/1954] Neural Leakage Model: Correlation Power Analysis ...
7. [2025/1955] Aggregate Signatures Tightly Secure under Adaptive ...
8. [2025/1956] A Chosen-Ciphertext Side-Channel Attack on Shuffled ...
9. [2025/1957] Fast Batch Matrix Multiplication in Ciphertexts
10. [2025/1958] A Lattice-Based IND-CCA Threshold KEM from the ...
11. [2025/1959] On the Communication Complexity of PSM and CDS for ...
12. [2025/1960] Multiple Rows Mixers and Hsilu - A Family of Linear ...
13. [2025/1961] Anamorphic Monero Transactions: the Threat of ...
14. [2025/1962] High Fidelity Security Mesh Monitoring using Low- ...
15. [2025/1963] Germany Is Rolling Out Nation-Scale Key Escrow And ...
16. [2025/1964] Generic PVSS Framework with $O(1)$ Complexity Using ...
17. [2025/1965] Unobservable Contracts from Zerocash and Trusted ...
18. [2025/1966] DPA-Style Attacks on HQC
19. [2025/1967] Linear-time and Logarithmically-sound Permutation ...
20. [2025/1968] TAPAS: Datasets for Learning the Learning with ...
21. [2025/1969] Cryptographic Personas: Responsible Pseudonyms ...
22. [2025/1970] Delving into Cryptanalytic Extraction of PReLU ...
23. [2025/1971] General Key Recovery Attack on Pointwise-Keyed ...
24. [2025/1972] Formalisation of the KZG polynomial commitment ...
25. [2025/1973] Tight Security for BBS Signatures
26. [2025/1974] Taming Iterative Grinding Attacks on Blockchain Beacons
27. [2025/1975] Rethinking Consensus with Time as a Primitive
28. [2025/1976] Improved Differential Cryptanalysis of ARADI
29. [2025/1977] Evaluating the Resistance of ARADI Against ...
30. [2025/1978] Cryptography with Weak Privacy
31. [2025/1979] On Singh et. al.'s "Collatz Hash"
## 2025/1288
* Title: New Proof for Plain OAEP: Post-Quantum Security without Parameter Restrictions or Collision-Resistance
* Authors: Heming Liao, Jiangxia Ge, Shujiao Cao, Rui Xue
* [Permalink](https://eprint.iacr.org/2025/1288)
* [Download](https://eprint.iacr.org/2025/1288.pdf)
### Abstract
During NIST's post-quantum cryptography standardization process, two generic transforms, Fujisaki-Okamoto (FO) and OAEP, are widely used to achieve the IND-CCA security. For instance, the final winner Kyber has utilized FO, and a variant of the 3rd-round finalist NTRU has utilized OAEP. The FO and OAEP are both constructed in the random oracle model (ROM), so to evaluate their post-quantum security, a security proof in the quantum random oracle model (QROM) is required. So far, the QROM security proof of FO has been given and improved by a sequence of works, however, the QROM security proof of OAEP has not been fully explored: current proofs either introduced an extra plaintext-confirming hash to the ciphertext (TCC 2016), or required parameter restrictions and a quantum collision-resistant term (PKC 2022).
In this paper, by reorganizing the proof route, we give a new QROM security proof of plain OAEP. The key techniques used in our proof are the compressed oracle technique proposed by Zhandry (CRYPTO 2019) and the Fixed Permutation One-Way to Hiding recently proposed by Jaeger (Eprint 2024/797), and our proof has the following three advantages:
\begin{itemize}
\item Similar to EbrahimirCOs proof (PKC 2022), our proof also achieves the stronger IND-qCCA security, where the decryption oracle can be accessed in superposition.
\item The parameter restrictions "$n+k_1\geq k_0$" and "$k_0-n=\mathcal{O}(n)$" introduced in EbrahimirCOs proof (PKC 2022) are removed.
\item The reliance on the collision resistance of quantum random oracles required in EbrahimirCOs proof (PKC 2022) is avoided, and hence our security bound does not introduce the quantum collision-resistant term "$\mathcal{O}(q^3/2^{n+k_1})$".
\end{itemize}
## 2025/1655
* Title: Lattice-based Multi-message Multi-recipient KEM/PKE with Malicious Security
* Authors: Zeyu Liu, Katerina Sotiraki, Eran Tromer, Yunhao Wang
* [Permalink](https://eprint.iacr.org/2025/1655)
* [Download](https://eprint.iacr.org/2025/1655.pdf)
### Abstract
The efficiency of Public Key Encryption (PKE) and Key Encapsulation Mechanism (KEM), and in particular their large ciphertext size, is a bottleneck in real-world systems. This worsens in post-quantum secure schemes (e.g., lattice-based ones), whose ciphertexts are an order of magnitude larger than prior ones.%their non-post-quantum counterparts.

The work of Kurosawa (PKC'02) introduced multi-message multi-recipient PKE (mmPKE) to reduce the amortized ciphertext size when sending messages to more than one recipient. This notion naturally extends to multi-message multi-recipient KEM (mmKEM).
In this work, we first show concrete attacks on existing lattice-based mmPKE schemes: Using maliciously-crafted recipient public keys, these attacks completely break semantic security and key privacy, and are inherently undetectable.

We then introduce the first lattice-based mmKEM scheme that maintains full privacy even in the presence of maliciously-generated public keys. Concretely, the ciphertext size of our mmKEM for 100 recipients is $>10\times$ smaller than naively using Crystals-Kyber. We also show how to extend our mmKEM to mmPKE, achieving a scheme that outperforms all prior lattice-based mmPKE schemes in terms of both security and efficiency. We additionally show a similar efficiency gain when applied to batched random oblivious transfer, and to group oblivious message retrieval.
Our scheme is proven secure under a new Module-LWE variant assumption, Oracle Module-LWE, which can be of its own independent interest.
We reduce standard MLWE to this new assumption for some parameter regimes, which also gives intuition on why this assumption holds for the parameter we are interested in (along with additional cryptanalysis).
Furthermore, we show an asymptotically efficient compiler that removes the assumption made in prior works that recipients know their position in the list of intended recipients for every ciphertext.
## 2025/1802
* Title: Zyga: Optimized Zero-Knowledge Proofs with Dynamic Public Inputs
* Authors: Tiago A. O. Alves, Vitor Py Braga
* [Permalink](https://eprint.iacr.org/2025/1802)
* [Download](https://eprint.iacr.org/2025/1802.pdf)
### Abstract
We present Zyga, a pairing-based zero-knowledge proof system optimized for privacy-preserving DeFi
applications. Our main contribution is an enhancement of existing zkSNARK constructions
that enables dynamic public input substitution during verification while maintaining privacy of witness
components through one-sided encoding. The one-sided encoding aspect favors practical deployment constraints on Solana where G2 scalar multiplications are computationally expensive. Zyga separates private
values (blinded through trusted setup) from public values (instantiated on-chain), enabling applications
like private trading against current market rates without reproofing. We provide rigorous security analysis under discrete logarithm and q-Strong Diffie-Hellman assumptions, demonstrating computational
soundness, zero-knowledge, and completeness. Performance analysis shows verification requires only 3
pairings with constant proof size, making it practical for blockchain deployment where transaction costs
are critical.
## 2025/1825
* Title: Quantumly Computing S-unit Groups in Quantified Polynomial Time and Space
* Authors: Koen de Boer, Jo|2l Felderhoff
* [Permalink](https://eprint.iacr.org/2025/1825)
* [Download](https://eprint.iacr.org/2025/1825.pdf)
### Abstract
We present a novel analysis of a quantum algorithm computing the S-unit group for a number field from Eisentr|nger et al. [EHKS14a] and Biasse and Song [BS16]. We prove that this quantum algorithm runs within polynomial time, where we explicitly quantify the polynomials of the quantum gate and memory complexity (under GRH). We do so by carefully analyzing an implementation of an Continuous Hidden Subgroup Problem (CHSP) oracle function whose period is the (logarithm of the) S-unit group, and provide it to an CHSP-solving algorithm as in [BDF19].
Our analysis is novel due to minimizing the use of the quantum memory-inefficient LLL-reduction, by resorting to strategically chosen precomputations of approximations of high powers of prime ideals. Additionally, we provide a new quantum algorithm computing a discrete Gaussian superposition analogue of the GPV algorithm by Gentry et al. [GPV08]. Lastly, we include a full and rigorous numerical analysis of all parts of the oracle-function computing algorithm, allowing to use fixed-point precision arithmetic and thus to precisely quantify the run-time and memory.
## 2025/1953
* Title: Adaptively Secure Partially Non-Interactive Threshold Schnorr Signatures in the AGM
* Authors: Renas Bacho, Yanbo Chen, Julian Loss, Stefano Tessaro, Chenzhi Zhu
* [Permalink](https://eprint.iacr.org/2025/1953)
* [Download](https://eprint.iacr.org/2025/1953.pdf)
### Abstract
Very recently, Crites et al. (CRYPTO 2025) gave a proof for the full adaptive security of FROST (Komlo and Goldberg, SAC 2020), the state-of-the-art two-round threshold Schnorr signature scheme, which is currently used in real-world applications and is covered by an RFC standard. Their security proof, however, relies on the computational hardness of a new search problem they call rCLlow-dimensional vector representationrCY (LDVR). In fact, the authors show that hardness of LDVR is necessary for adaptive security of a large class of threshold Schnorr signatures to hold, including FROST and its two-round variants. Given that LDVR is a new assumption and its hardness has not been seriously scrutinized, it remains an open problem whether a two-round threshold Schnorr signature with full adaptive security can be constructed based on more well-established assumptions.
In this paper, we resolve this open problem by presenting ms-FROST. Our scheme is partially non-interactive and supports any t - 1 < n adaptive corruptions, where n is the number of signers and t is the signing threshold. Its security relies on the algebraic one-more discrete logarithm (AOMDL) assumption, the algebraic group model (AGM), and the random oracle model (ROM). Further, it achieves the strongest security notion (TS-UF-4) in the security hierarchy of Bellare et al. (CRYPTO 2022). To justify our use of the algebraic group model, we show an impossibility result: We rule out any black-box algebraic security reduction in the ROM from AOMDL to the adaptive TS-UF-0 security of ms-FROST.
## 2025/1954
* Title: Neural Leakage Model: Correlation Power Analysis with Profiled Leakage Model using Deep Neural Networks
* Authors: Trevor Yap, Shivam Bhasin, Liu Zhang
* [Permalink](https://eprint.iacr.org/2025/1954)
* [Download](https://eprint.iacr.org/2025/1954.pdf)
### Abstract
Side-channel analysis (SCA) exploits physical leakages such as power consumption or electromagnetic emissions to extract secret information from cryptographic implementations. Leakage model is the critical link between observable physical emanations (e.g., power consumption) and internal cryptographic states. When a leakage model fails to match the devicerCOs underlying physical leakage, even powerful attacks like Correlation Power Analysis (CPA) are rendered ineffective. This fundamental challenge limits the success of traditional SCA, especially against noisy or masked targets.
In this work, we introduce the Neural Leakage Model (NLM), a novel neural network architecture trained to learn and accurately characterize complex physical leakage to enhance CPA. Moving beyond NLM's superior attack performance, we directly address the critical ``black box'' problem in deep learning-based side-channel analysis (DLSCA) by proposing a novel methodology to transform the trained NLM into a mathematically equivalent, closed-form polynomial expression. This provides interpretability, offering evaluators transparent insight into the precise leakage model the network has learned. We validate NLMrCOs performance across four diverse datasets spanning three platforms, from low-end microcontrollers to high-end multi-core ARM systems and dedicated FPGAs. Notably, NLM successfully recovers the secret key from the highly challenging and noisy CHES2025 dataset, representing the first known successful CPA attack on this benchmark. Furthermore, NLM demonstrates superior or comparable performance when extended to higher-order CPA against masking countermeasures. Our findings establish NLM as a powerful, generalizable, and interpretable approach to modern side-channel analysis.
## 2025/1955
* Title: Aggregate Signatures Tightly Secure under Adaptive Corruptions
* Authors: Yusuke Sakai
* [Permalink](https://eprint.iacr.org/2025/1955)
* [Download](https://eprint.iacr.org/2025/1955.pdf)
### Abstract
Aggregate signatures allow compressing multiple single-signer signatures into a single short aggregate signature. This primitive has attracted new attention due to applications in blockchains and cryptocurrencies. In multisig addresses, which is one of such applications, aggregate signatures reduce the sizes of transactions from multisig addresses. Security of aggregate signatures under adaptive corruptions of signing keys is important, since one of the motivations of multisig addresses was a countermeasure against signing key exposures. We propose the first aggregate signature scheme tightly secure under adaptive corruptions using pairings. An aggregate signature includes two source group elements of bilinear groups plus a bit vector whose length is equal to the number of single-signer signatures being aggregated. To construct a scheme, we employ a technique from quasi-adaptive non-interactive zero-knowledge arguments. Our construction can be seen as modularization and tightness improvement of Libert et al.'s threshold signature scheme supporting signature aggregation (Theoretical Computer Science 645) in a non-threshold setting.
## 2025/1956
* Title: A Chosen-Ciphertext Side-Channel Attack on Shuffled CRYSTALS-Kyber
* Authors: Hao Zhang, Zewen Ye, Teng Wang, Yuanming Zhang, Tianyu Wang, Chengxuan Wang, Kejie Huang
* [Permalink](https://eprint.iacr.org/2025/1956)
* [Download](https://eprint.iacr.org/2025/1956.pdf)
### Abstract
The NIST Post-Quantum Cryptography (PQC) standardization has entered its fourth round, underscoring the critical importance of addressing side-channel attacks (SCA), a dominant threat in real-world cryptographic implementations, especially on embedded devices. This paper presents a novel chosen-ciphertext side-channel attack against CRYSTALS-Kyber (standardized as ML-KEM) implementations with Fisher-Yates shuffled polynomial reduction. We propose an efficient and fault-tolerant key recovery algorithm that, by crafting malicious ciphertexts, induces changes in the Hamming weight distribution of an intermediate polynomial's coefficients (the output of the shuffled polynomial reduction during decapsulation), enabling recovery of secret key coefficients from these changes. To ensure robustness, we propose an error-correction strategy that leverages the Hamming weight classifier's behavior to constrain and shrink the correction search space, maintaining effectiveness even with less accurate classifiers or in low-SNR environments. A Multi-Layer Perceptron (MLP) is employed for Hamming weight classification from side-channel traces, achieving 97.11% accuracy. We combine statistical analysis with explainable deep learning for precise trace segmentation during pre-processing. Experimental results demonstrate full key recovery with only an average of $10 + 354 \times 3$ ciphertext queries and a success rate of 97.98%, reducing the adversarial effort by 95.36% compared to contemporary bit-flip techniques. Although shuffling aims to disrupt temporal correlations, our results show that statistical features persist and leak through shuffled implementations. This work reveals enduring SCA risks in shuffled implementations and informs a broader reassessment of PQC side-channel resilience.
## 2025/1957
* Title: Fast Batch Matrix Multiplication in Ciphertexts
* Authors: Jung Hee Cheon, Minsik Kang, Junho Lee
* [Permalink](https://eprint.iacr.org/2025/1957)
* [Download](https://eprint.iacr.org/2025/1957.pdf)
### Abstract
Encrypted matrix multiplication (MM) is a fundamental primitive in privacy-preserving machine learning and encrypted data search, but it remains a significant performance bottleneck. Recently, Bae et al.~(CryptorCO24) and Park~(EurocryptrCO25) introduced novel algorithms for ciphertextrCoplaintext (CPMM) and ciphertextrCociphertext (CCMM) matrix multiplications. These algorithms reduce encrypted MM operations to plaintext matrix multiplications (PPMM), enabling implementation through highly optimized BLAS libraries.
While these reduction-based methods offer significant improvements, their applicability is limited to scenarios where the matrix dimension
$d$ is comparable to the ring dimension $N$ in RLWE-based CKKS schemes.
As a result, they fall short for matrix multiplications involving small or medium-sized matrices.
We extend the reduction-based CPMM/CCMM into small-sized matrix operations by batching instances. We use the Slots-in-Coefficient (SinC) encoding where a ring element is represented by a polynomial with coefficients each of which is the Discrete Fourier Transform of matrix entries at the same position. This encoding enables reductions of encrypted batch MM algorithms to a small number of batch PPMMs, which can be efficiently accelerated by BLAS libraries.
Our batch encrypted MM flexibly accommodates diverse matrix dimensions and batch sizes independent of the ring dimension $N$, thereby extending its applicability to practical real-world settings.
For two $d \times d$ matrices with $N/d$ batches, our batch CPMM and CCMM algorithms achieve complexity $O(d^2N)$, improving upon Bae et al. at $O(dN^2)$ and Jiang et al~(CCSrCO18) at $O(d^2 N\log (N))$.
We further extend our techniques to rectangular matrices, achieving $O(dN^2)$ for multiplying a $d \times N$ and an $N \times N$ matrix, improving previous $O(N^3)$ methods.
A proof-of-concept implementation validates these improvements: multiplying 128 batches of $64 \times 64$ matrices takes $0.20$s (CPMM) and $0.91$s (CCMM), yielding $205\times$ and $64\times$ speedups over previous methods. For a $64 \times 2048$ by $2048 \times 2048$ multiplication, our CCMM completes in $7.8$s, achieving a $28\times$ speedup compared to Park's algorithm.
## 2025/1958
* Title: A Lattice-Based IND-CCA Threshold KEM from the BCHK+ Transform
* Authors: Oleksandra Lapiha, Thomas Prest
* [Permalink](https://eprint.iacr.org/2025/1958)
* [Download](https://eprint.iacr.org/2025/1958.pdf)
### Abstract
We present a simple IND-CCA lattice-based threshold KEM. At a high level, our design is based on the BCHK transform (Canetti et al., EUROCRYPT 2004), which we adapt to the lattice setting by combining it with the FO transform (Fujisaki and Okamoto, PKC 1999) in order to achieve decryption consistency.
As for the BCHK transform, our construction requires a threshold identity-based encryption (TIBE) scheme with suitable properties. We build such an IBE by combining the ABB IBE (Agrawal, Boneh, Boyen, EUROCRYPT 2010) with recent advances in lattice threshold cryptography, such as the threshold-friendly signature Plover (Esgin et al., EUROCRYPT 2024) and a variant of the Threshold Raccoon scheme (Katsumata et al., CRYPTO 2024).
The security proof of our scheme relies on a new assumption which we call the Coset-Hint-MLWE assumption, and which is a natural generalisation of the Hint-MLWE assumption (Kim et al., CRYPTO 2023). We prove the hardness of Coset-Hint-MLWE under standard assumptions. We believe this new assumption may be of independent interest.
Unlike prior works on IND-CCA lattice-based threshold KEMs, our construction only relies on simple algorithmic tools and does not use heavy machinery such as multi-party computation or threshold fully homomorphic encryption.
## 2025/1959
* Title: On the Communication Complexity of PSM and CDS for Symmetric Functions * Authors: Reo Eriguchi
* [Permalink](https://eprint.iacr.org/2025/1959)
* [Download](https://eprint.iacr.org/2025/1959.pdf)
### Abstract
Private Simultaneous Messages (PSM) and Conditional Disclosure of Secrets (CDS) are two fundamental primitives in information-theoretic cryptography. In a PSM protocol, each party sends a single message to a referee, who can then compute a function $f$ of their private inputs but learns nothing else. A CDS protocol follows the same model as PSM, but the goal is to disclose a secret shared among all parties to the referee if and only if the function $f$ evaluates to $1$. Minimizing the communication complexity of these primitives is a central question in this area. Since the best known constructions for general functions require high communication complexity, recent studies have attempted to obtain more efficient constructions by focusing on symmetric functions, whose outputs are invariant under permutations of inputs. However, the extent to which exploiting symmetry can improve efficiency has remained unclear. In this work, we show upper and lower bounds that relate the optimal communication complexities of PSM and CDS for symmetric functions to those for general functions. When the number of parties is larger than the input domain size, our upper bound for PSM improves the best known communication complexity for symmetric functions. Furthermore, our upper bound for CDS demonstrates for the first time that symmetry can be exploited to reduce communication in CDS protocols. In contrast, when the number of parties is constant, our lower bounds show that focusing on symmetric functions yields only a constant-factor improvement. We also derive an analogous implication for PSM protocols under a plausible conjecture. In addition, our new constructions for symmetric functions lead to improvements over the state-of-the-art results in related models such as ad hoc PSM and secret sharing.
## 2025/1960
* Title: Multiple Rows Mixers and Hsilu - A Family of Linear Layers and A Permutation with Fewer XORs
* Authors: Xiaobin Yu, Meicheng Liu
* [Permalink](https://eprint.iacr.org/2025/1960)
* [Download](https://eprint.iacr.org/2025/1960.pdf)
### Abstract
Over the past decades, extensive research has been conducted on lightweight cryptographic primitives. The linear layer plays an important role in their security.
In this paper, we propose a family of linear layers consisting of XORs and rotations, which is called multiple rows mixers (MRM). It is a family designed for LS-type ciphers, but mixing elements from several rows. We investigate the impact of the linear layers on the 3-round trail weight of permutations and explore the properties of the inverse of the linear layers with a low XOR count. We employ a generic and extensible approach to determine the parameters of MRM. This approach can automatically generate linear layers that meet the requirements of a given branch number.
By applying these design principles and methods, we derive a linear layer that has a dimension of 5 |u 64, a differential branch number of 12, a linear branch number of 5 and a computational cost of 2.6 XOR operations per bit. MRM is not limited to fixed dimension and can be extended to other dimensions. In addition, we present a concrete instantiation of a 320-bit permutation using a more efficient instance of MRM, named Hsilu. Its non-linear layer employs the -c operating on columns.
Compared with the permutations of Gaston and NIST lightweight standard Ascon, the round function of Hsilu requires fewer XOR operations. Hsilu exhibits competitive security and performance with Ascon and Gaston. We demonstrate that the best-found 3-round differential and linear trails of Hsilu have much higher weights than those of Ascon. Hsilu outperforms Gaston and Ascon in terms of both software and hardware performance.
## 2025/1961
* Title: Anamorphic Monero Transactions: the Threat of Bypassing Anti-Money Laundering Laws
* Authors: Adrian Cinal, Przemys+eaw Kubiak, Miros+eaw Kuty+eowski, Gabriel Wechta
* [Permalink](https://eprint.iacr.org/2025/1961)
* [Download](https://eprint.iacr.org/2025/1961.pdf)
### Abstract
In this paper, we analyze the clash between privacy-oriented cryptocurrencies and emerging legal frameworks for combating financial crime, focusing in particular on the recent European Union regulations. We analyze Monero, a leading "privacy coin" and a major point of concern for law enforcement, and study the scope of due diligence that must be exercised under the new law with regard to Monero trading platforms and how it translates to the technical capabilities of the Monero protocol. We both recognize flaws in the legislation and identify technical pitfalls threatening either the effective compliance of, say, Monero exchanges or the anonymity endeavour of Monero itself. Of independent interest is that we turn to anamorphic cryptography (marking one of the first practical applications of the concept) and leverage it to build a hidden transaction layer embedded in the Monero blockchain that obfuscates illegal money flow and circumvents transaction-level attempts at enforcing the EU law.
## 2025/1962
* Title: High Fidelity Security Mesh Monitoring using Low-Cost, Embedded Time Domain Reflectometry
* Authors: Jan Sebastian G||tte, Bj||rn Scheuermann
* [Permalink](https://eprint.iacr.org/2025/1962)
* [Download](https://eprint.iacr.org/2025/1962.pdf)
### Abstract
Security Meshes are patterns of sensing traces covering an area that are used in Hardware Security Modules (HSMs) and other systems to detect attempts to physically intrude into the device's protective shell. State-of-the-art solutions manufacture meshes in bespoke processes from carefully chosen materials, which is expensive and makes replication challenging. Additionally, state-of-the-art monitoring circuits sacrifice either monitoring precision or cost efficiency. In this paper, we present an embeddable security mesh monitoring circuit constructed from low-cost, standard components that utilizes Time Domain Reflectometry (TDR) to create a unique fingerprint of a mesh. Our approach is both low-cost and precise, and enables the use of inexpensive standard Printed Circuit Boards (PCBs) as security mesh material. We demonstrate a working prototype of our TDR circuit costing less than 10 re4 in components that achieves both time resolution and rise time better than 200 psrCoa 25 |u improvement over previous work. We demonstrate a simple classifier that detects several types of advanced attacks such as probing using an oscilloscope probe or micro-soldering attacks with no false negatives.
## 2025/1963
* Title: Germany Is Rolling Out Nation-Scale Key Escrow And Nobody Is Talking About It
* Authors: Jan Sebastian G||tte
* [Permalink](https://eprint.iacr.org/2025/1963)
* [Download](https://eprint.iacr.org/2025/1963.pdf)
### Abstract
Germany is currently rolling out an opt-out, nation-scale
database of the medical records of the majority of its population, with low-income people being disproportionally represented among its users. While there has been considerable criticism of the system coming from civil society, independent academic analysis of the system by the cryptography and information security community has been largely absent. In this paper, we aim to raise awareness of the systemrCOs existence and, based on the systemrCOs public specifications, highlight several concerning cryptographic engineering decisions. Our core observations is that the systemrCOs most sensitive long-term user keys are derived by a rudimentary, home-grown centralized key escrow mechanism. This mechanism relies on a per-use salt and only 256 bit of entropy, shared globally across millions of users. Furthermore, the systemrCOs specification mandates only level 3 compliance with the obsolete FIPS 140-2 security standard, which requires rCLhard, opaque pottingrCY, but lacks active tamper sensing. As a result, the system remains vulnerable to attacks by nation states and other well-funded adversaries.
## 2025/1964
* Title: Generic PVSS Framework with $O(1)$ Complexity Using CCA2-Secure Threshold Encryption
* Authors: Liang Zhang, Dongliang Cai, Yiwen Gao, Haibin Kan, Jiheng Zhang, Moti Yung
* [Permalink](https://eprint.iacr.org/2025/1964)
* [Download](https://eprint.iacr.org/2025/1964.pdf)
### Abstract
Existing PVSS schemes suffer from at least $O(n)$ online complexity due to the need to individually encrypt and prove/ verify each of the $n$ shares. In this work, we present a generic framework for constructing PVSS schemes with $O(1)$ complexity for share distribution and (the expected to be repeated numerous times) public verification. Our key insight lies in establishing a novel connection between PVSS and CCA2-Secure threshold encryption (CCATE), which enables public verifiability enforced by Non-Interactive Zero-Knowledge (NIZK) proofs. We show that a CCATE scheme can be generically transformed into a secure PVSS scheme, eliminating the $O(n)$ bottleneck per on-line operations. We instantiate the framework by presenting two CCATE constructions: 1) A pairing-free scheme based on a committee-based Distributed Key Generation (DKG) protocol and Threshold ElGamal encryption. 2) A silent setup scheme leveraging a non-interactive distributed key generation, relying on Power-of-Tau ceremony. Furthermore, we introduce solutions for dynamic membership updates in both DKG constructions, demonstrating their practicality and adaptability for real-world applications. The scheme is based on an off-line setup stage (before a specific value to share is given) where the $O(n)$ complexity is dealt with. Although our schemes incur higher setup costs, they drastically reduce the complexity of the critical distribution and verification stages to constant time. This trade-off marks a significant advancement in the scalability of PVSS-based systems, especially in the context of blockchain modern transactions. Conceptually, the work points out how variants of the notion of Threshold Encryption can potentially serve as a ``compression mechanism'' for information sharing schemes.
## 2025/1965
* Title: Unobservable Contracts from Zerocash and Trusted Execution Environments
* Authors: Adrian Cinal
* [Permalink](https://eprint.iacr.org/2025/1965)
* [Download](https://eprint.iacr.org/2025/1965.pdf)
### Abstract
Privacy-oriented cryptocurrencies like Zerocash only support direct payments and not the execution of more complex contracts. Bitcoin and Ethereum, on the other hand, cannot guarantee privacy, and using them for contract execution leaves open questions about fungibility of the proceeds and requires contract designers to take frontrunning countermeasures. This work reconciles the two worlds and develops a practical framework for decentralized execution of complex contracts that (1) is undetectable to the network at large, (2) maintains anonymity of the potentially mutually distrustful counterparties, (3) guarantees fair termination, and (4) is immediately resistant to frontrunning and miner bribery attacks. This is achieved by leveraging the confidentiality and anonymity guarantees of Zerocash and the verifiability and flexibility of trusted execution environments.
## 2025/1966
* Title: DPA-Style Attacks on HQC
* Authors: Zhuo Huang, Weijia Wang, Xiaogang Zhou, Yu Yu
* [Permalink](https://eprint.iacr.org/2025/1966)
* [Download](https://eprint.iacr.org/2025/1966.pdf)
### Abstract
HQC (Hamming Quasi-Cyclic) was selected as the fifth algorithm in the NIST suite of post-quantum cryptographic (PQC) standards. As the only code-based algorithm currently standardized by NIST, HQC offers a good balance between security assurance, performance, and implementation simplicity. Most existing power analyses against HQC are of the SPA style: they can recover secrets with a small number of traces, but can only tolerate limited noise. In this paper, we develop a chosen-ciphertext DPA-style attack methodology against HQC. We formalize a dedicated chosen-ciphertext setting in which the adversary selects $(\mathbf{u},\mathbf{v})$ to target the intermediate value $\mathbf{v}\oplus(\mathbf{u}\mathbf{y})$ over $\mathbb{F}_2[x]/(x^n-1)$. We further optimize the attack by reducing its computational complexity and generalizing it to target masked HQC implementations. The proposed approach is validated through both simulation and practical experiments. In noiseless simulations, full-key recovery is achieved with just \(10\) traces, and the required number of traces increases linearly with 1/SNR. In practical evaluations on an STM32F4 microprocessor, the secret key can be recovered with \(45\) traces without profiling and \(10\) traces with profiling. When first-order masking is applied, key recovery on the same hardware target remains feasible by exploiting second-order features, requiring approximately \(7{,}500\) traces without profiling. Our results establish a direct and analyzable connection between leakage on \(\mathbf{v}\oplus \mathbf{u}\mathbf{y}\) and end-to-end key recovery, emphasizing the necessity of higher-order masking countermeasures for HQC implementations.
## 2025/1967
* Title: Linear-time and Logarithmically-sound Permutation and Multiset SNARKs * Authors: Bing-Jyue Chen, Lilia Tang, David Heath, Daniel Kang
* [Permalink](https://eprint.iacr.org/2025/1967)
* [Download](https://eprint.iacr.org/2025/1967.pdf)
### Abstract
Permutation and multiset checks underpin many SNARKs, yet existing techniques either incur superlinear prover time or rely on auxiliary commitments with soundness error that grows linearly in the input size. We present new arguments with linear-time provers and logarithmic soundness, without auxiliary commitments.
Prior work achieving logarithmic soundness error arithmetizes the permutation as a product of several multilinear polynomials, a formulation chosen for compatibility with the classic Sumcheck PIOP. A simpler alternative treats permutations as multilinear extensions of their permutation matrices. While this formulation was previously believed to require quadratic prover time, we show that this overhead can be eliminated by taking a linear-algebraic perspective. This viewpoint has a key advantage: partially evaluating the multilinear polynomial of the permutation requires no additional field operations and amounts to applying the inverse permutation to the verifier's challenge vector. This makes the step essentially free in terms of algebraic cost, unlike in prior approaches. Compared to concurrent work BiPerm (B|+nz et al., ePrint Archive, 2025), our scheme requires no permutation preprocessing and supports prover-supplied permutations.
We show a sparsity-aware PCS like Dory (Lee, TCC, 2021) can compile our PIOP to a SNARK such that the resulting SNARK prover still runs in time $O(n)$. Our construction is the first logarithmically-sound SNARK with an $O(n)$-time prover for both permutation and multiset checks. We further prove a matching optimal prover lower bound, and we identify specific permutations that can be evaluated by the verifier in $O(\mathrm{polylog}(n))$-time. The ability to evaluate these permutations in $O(\mathrm{polylog}(n))$ time allows the verifier to avoid relying on prover-supplied commitments or evaluation proofs. As a result, we obtain the first logarithmically sound, field-agnostic SNARK with an $O(n)$-time prover in this setting.
## 2025/1968
* Title: TAPAS: Datasets for Learning the Learning with Errors Problem
* Authors: Eshika Saxena, Alberto Alfarano, Fran|oois Charton, Emily Wenger, Kristin Lauter
* [Permalink](https://eprint.iacr.org/2025/1968)
* [Download](https://eprint.iacr.org/2025/1968.pdf)
### Abstract
AI-powered attacks on Learning with Errors (LWE), an important hard math problem in post-quantum cryptography, rival or outperform "classical" attacks on LWE under certain parameter settings. Despite the promise of this approach, a dearth of accessible data limits AI practitioners' ability to study and improve these attacks. Creating LWE data for AI model training is time- and compute-intensive and requires significant domain expertise. To fill this gap and accelerate AI research on LWE attacks, we propose the TAPAS datasets, a Toolkit for Analysis of Post-quantum cryptography using AI Systems. These datasets cover several LWE settings and can be used off-the-shelf by AI practitioners to prototype new approaches to cracking LWE. This work documents TAPAS dataset creation, establishes attack performance baselines, and lays out directions for future work.
## 2025/1969
* Title: Cryptographic Personas: Responsible Pseudonyms Without De-Anonymization
* Authors: Rachel Thomas, Oliwia Kempinski, Hari Kailad, Emma Margaret Shroyer, Ian Miers, Gabriel Kaptchuk
* [Permalink](https://eprint.iacr.org/2025/1969)
* [Download](https://eprint.iacr.org/2025/1969.pdf)
### Abstract
We present cryptographic personas, an approach for facilitating access to pseudonymous speech within communities without enabling abuse. In systems equipped with cryptographic personas, users are able to authenticate to the service provider under new, unlinkable personas at will and post messages under those personas. When users violate community norms, their ability to post anonymously can be revoked. We develop two significant improvements to existing work on anonymous banning systems that make it possible to integrate cryptographic personas into real-time applications like group messaging: we show how to push expensive proof generation into an offline phase and find a way to optimize server-side overhead using recent proof folding techniques. We implement cryptographic personas, integrating them into a variety of settings, and show that they are concretely efficient enough for deployment.
## 2025/1970
* Title: Delving into Cryptanalytic Extraction of PReLU Neural Networks
* Authors: Yi Chen, Xiaoyang Dong, Ruijie Ma, Yantian Shen, Anyu Wang, Hongbo Yu, Xiaoyun Wang
* [Permalink](https://eprint.iacr.org/2025/1970)
* [Download](https://eprint.iacr.org/2025/1970.pdf)
### Abstract
The machine learning problem of model extraction was first
introduced in 1991 and gained prominence as a cryptanalytic challenge
starting with Crypto 2020. For over three decades, research in this field
has primarily focused on ReLU-based neural networks. In this work, we
take the first step towards the cryptanalytic extraction of PReLU neural networks, which employ more complex nonlinear activation functions
than their ReLU counterparts.
We propose a raw output-based parameter recovery attack for PReLU
networks and extend it to more restrictive scenarios where only the top-m probability scores are accessible. Our attacks are rigorously evaluated
through end-to-end experiments on diverse PReLU neural networks, including models trained on the MNIST dataset. To the best of our knowledge, this is the first practical demonstration of PReLU neural network
extraction across three distinct attack scenarios.
## 2025/1971
* Title: General Key Recovery Attack on Pointwise-Keyed Functions - Application to Alternating Moduli Weak PRFs
* Authors: Antoine Sidem, Qingju Wang
* [Permalink](https://eprint.iacr.org/2025/1971)
* [Download](https://eprint.iacr.org/2025/1971.pdf)
### Abstract
The increasing use of multi-party computation (MPC) has spurred the design of symmetric key primitives specifically suited for MPC environments. Recently, weak pseudorandom functions (wPRFs) based on the alternating moduli paradigm have been proposed as a promising class of MPC-friendly primitives. The wPRF proposed at CRYPTO 2024, in its One-to-One parameter set, has been shown to be vulnerable to a key recovery attack dubbed Zeroed-Out, exploiting collisions in the queries.
In this paper, we identify that the aforementioned wPRFs conform to a specific structure, called pointwise-keyed function, and further show a different, general key recovery attack. This method, applied to wPRFs in the One-to-One parameter set attacked by Zeroed-out, improves upon the complexity and achieves an attack with complexity below the birthday bound, and stays effective against the proposed countermeasures. For the first time, it succeeds in attacking one of the two Many-to-One parameter sets and stays effective against one of the proposed countermeasures. We also consider its applicability to the alternative wPRF of similar structure proposed by Boneh et al at TCC 2018.
## 2025/1972
* Title: Formalisation of the KZG polynomial commitment schemes in EasyCrypt
* Authors: Palak, Thomas Haines
* [Permalink](https://eprint.iacr.org/2025/1972)
* [Download](https://eprint.iacr.org/2025/1972.pdf)
### Abstract
In this paper, we present formally verified proofs of the popular KZG Polynomial Commitment Schemes (PCSs), including the security proofs for the properties of correctness, polynomial binding, evaluation binding and hiding. Polynomial commitment schemes have various applications in cryptography and computer science, including verifiable computation, blockchain and cryptocurrencies, secure multi-party computation as well as in the construction of ZK-SNARKs. To validate security, we utilise EasyCrypt, an interactive theorem prover that allows for formal verification of cryptographic primitives and protocols. This approach enforces correct proofs which cover all required cases and formalising assumptions reducing the risk of overlooked vulnerabilities. This formalisation validates the current understanding of KZG's PCSs as secure while clarifying various issues in the original claims.
## 2025/1973
* Title: Tight Security for BBS Signatures
* Authors: Rutchathon Chairattana-Apirom, Dennis Hofheinz, Stefano Tessaro
* [Permalink](https://eprint.iacr.org/2025/1973)
* [Download](https://eprint.iacr.org/2025/1973.pdf)
### Abstract
This paper studies the concrete security of BBS signatures (Boneh, Boyen, Shacham, CRYPTO '04; Camenisch and Lysyanskaya, CRYPTO '04), a popular algebraic construction of digital signatures which underlies practical privacy-preserving authentication systems and is undergoing standardization by the W3C and IRTF.
Sch\"age (Journal of Cryptology '15) gave a tight standard-model security proof under the $q$-SDH assumption for a less efficient variant of the scheme, called BBS+--here, $q$ is the number of issued signatures. In contrast, the security proof for BBS (Tessaro and Zhu, EUROCRYPT '23), also under the $q$-SDH assumption, is \emph{not} tight. Nonetheless, this recent proof shifted both standardization and industry adoption towards the more efficient BBS, instead of BBS+, and for this reason, it is important to understand whether this tightness gap is inherent. Recent cryptanalysis by Chairattana-Apirom and Tessaro (ASIACRYPT '25) also shows that a tight reduction to $q$-SDH is the best we can hope for.
This paper closes this gap in two different ways. On the positive end, we show a novel tight reduction for BBS in the case where each message is signed at most once--this case covers in particular the common practical use case which derandomizes signing. On the negative end, we use a meta-reduction argument to prove that if we allow generating multiple signatures for the same message, then {\em no} algebraic reduction to $q$-SDH (and its variants) can be tight.
## 2025/1974
* Title: Taming Iterative Grinding Attacks on Blockchain Beacons
* Authors: Peter Ga++i, Saad Quader, Alexander Russell
* [Permalink](https://eprint.iacr.org/2025/1974)
* [Download](https://eprint.iacr.org/2025/1974.pdf)
### Abstract
Random beacons play a critical role in blockchain protocols by providing publicly verifiable, unpredictable randomness essential for secure assignment of protocol roles such as block producers and committee membership. In the interest of efficiency, many deployed blockchains adopt beacon algorithms that suffer from grinding: an adversarial attack in which a party exploits freedom given by the protocol to bias the outcome of the random beacon by resampling it several times and picking the most desirable outcome. To compound the problem, beacons often operate in an iterative manner, where the beacon output produced during one protocol epoch serves as the random seed for the beaconrCOs invocation in the next epoch. This amplifies the security threat, as such attacks may then aggregate their power over many epochs.
In this article, we formulate a generic framework for information-theoretic analysis of grinding in iterated randomness beacons. We define the natural grinding capacity of a beacon, intuitively corresponding to the amount of grinding it allows with a uniformly random seed. We then prove that sufficiently strong tail bounds on this quantity can be transformed into a guarantee on smooth min-entropy of the iterated beaconrCOs output, even conditioned on all past outputs and irrespective of the inner workings of the beacon. Such min-entropy guarantees can immediately be translated into corresponding statements about various applications of the beacon to committee selection, incentives, or underlying protocol security.
Our main technical result concerns conventional longest-chain protocols, where we establish that the combinatorial structure of the forest of longest chains can be leveraged to control grinding. Instantiating the generic framework with these grinding upper bounds, we establish that the randomness beacon of the Ouroboros Praos protocol is secure against adversaries controlling up to about 12% of stakerCoeven
without any assumptions bounding the adversarial computational power invested into grinding. This is a qualitatively new guarantee for the protocol.
## 2025/1975
* Title: Rethinking Consensus with Time as a Primitive
* Authors: Ignacio Amores-Sesar, Michelle Yeo
* [Permalink](https://eprint.iacr.org/2025/1975)
* [Download](https://eprint.iacr.org/2025/1975.pdf)
### Abstract
We propose a novel timestamping mechanism for consensus protocols that reliably assigns submission times to honest transactions while preventing adversarial transactions from forging their timestamps. Our mechanism remains secure even under asynchronous networks and in the presence of corrupted parties. We demonstrate how it can be integrated into the three main families of consensus protocols and show its compatibility with layer-2 solutions. This construction enables robust layer-2 implementations that do not rely on timing assumptions, remain resilient under network saturation, and prevent collusion between users and validators to censor honest users.
## 2025/1976
* Title: Improved Differential Cryptanalysis of ARADI
* Authors: Surajit Mandal, Sandip Kumar Mondal, Raghvendra Rohit, Santanu Sarkar
* [Permalink](https://eprint.iacr.org/2025/1976)
* [Download](https://eprint.iacr.org/2025/1976.pdf)
### Abstract
This study investigates and improves the differential cryptanalysis of the ARADI block cipher, a low-latency cryptographic system developed by the United States National Security Agency for memory encryption. The preliminary security assessment of ARADI revealed deficiencies that require additional examination. This study revisits and corrects the key recovery attack introduced by Bellini et al. (Indocrypt 2024). By correcting these mistakes, the research presents a precise 11-round key recovery method with revised attack complexities. Additionally, the analysis is expanded to introduce a key recovery attack for 12 rounds of ARADI, leaving the security margin of the cipher to only 4 rounds.
## 2025/1977
* Title: Evaluating the Resistance of ARADI Against Differential Fault Attack
* Authors: Chandan Dey, Soumya Sahoo, Santanu Sarkar
* [Permalink](https://eprint.iacr.org/2025/1977)
* [Download](https://eprint.iacr.org/2025/1977.pdf)
### Abstract
The ARADI block cipher is developed by the U.S. National Security Agency (NSA) as part of its efforts to design secure and efficient cryptographic algorithms.
In this paper, we present the first detailed analysis of the lightweight block cipher ARADI under differential fault attacks. Although ARADI is structured around word-wise operations, its security fundamentally depends on bit-level properties, making it vulnerable to carefully crafted fault models. Bit-based fault models require a large number of faults, while word-based models reduce the number of faults but make precise identification of fault locations difficult. To overcome these limitations, we introduce a new nibble-based approach using permissible nibble differences (PNDs). This model provides an effective tradeoff between the number of required faults and the complexity of identifying fault positions. In our attack, the adversary randomly injects nibble faults before the last two rounds and constructs differential equations involving unknown key variables without knowing the exact fault values. Our results demonstrate that, with at most 108 random fault injections, the entire master key of ARADI can be recovered within a practical time complexity. This work reveals previously unexplored vulnerabilities of ARADI under fault attacks and highlights the need to evaluate lightweight cipher designs using nibble-level fault models, along with the traditional bit- and word-level analyses.
## 2025/1978
* Title: Cryptography with Weak Privacy
* Authors: Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Hanjun Li
* [Permalink](https://eprint.iacr.org/2025/1978)
* [Download](https://eprint.iacr.org/2025/1978.pdf)
### Abstract
We initiate a systematic study of information-theoretic cryptography with {\em weak privacy}, only requiring that the adversary cannot rule out any possible secret. For a parameter $0<p\le 1$, we say that a primitive has $p$-weak privacy ($p$-WP) if for every possible view $V$ and inputs $x_1,x_2$, the ratio between the probabilities of the adversary observing $V$ on $x_1$ and on $x_2$ is at least $p$. This generalizes both perfect privacy, which is $p$-WP for $p=1$, and a previous ``combinatorial'' notion of privacy, which is $p$-WP for {\em some} $p>0$. We obtain the following main results.
Positive results. We present efficient WP constructions for generalized secret sharing, decomposable randomized encodings, and the related notions of garbling schemes and PSM protocols, as well as interactive secure multiparty computation protocols in the plain model and in the OT-hybrid model.
For secret sharing, we settle a question of Beimel and Franklin (TCC 2007), showing that every $n$-party access structure admits a WP scheme with per-party share size $O(n)$. When all unauthorized sets have constant size, we get a $p$-WP scheme with constant share size and $p\ge 1/poly(n)$.
Negative result. For decomposable randomized encodings, we show that a previous lower bound technique of Ball et al.\ (ITCS 2020) applies also to the WP notion. Together with our upper bound, this shows that the optimal WP garbling size of the worst-case $f:\{0,1\}^n\to\{0,1\}$ is $\tilde{\Theta}(n^2)$.
Application. While WP may seem like an unrealistically weak security notion, we demonstrate its usefulness towards achieving traditional security guarantees. Concretely, under the standard LPN assumption, we show that any $p$-WP secret-sharing scheme with inverse-polynomial $p$ implies a {\em computationally secure} secret-sharing scheme for a related access structure. Together with our positive results for WP secret sharing, this implies a super-polynomial improvement of the share size for a natural class of access structures.
## 2025/1979
* Title: On Singh et. al.'s "Collatz Hash"
* Authors: Joe Doyle
* [Permalink](https://eprint.iacr.org/2025/1979)
* [Download](https://eprint.iacr.org/2025/1979.pdf)
### Abstract
Singh et. al. recently uploaded a preprint describing a new hash function inspired by the Collatz Conjecture. After performing some cursory tests, the proposed function appears to be completely unsuitable for cryptographic purposes, and should not be used.
--- Synchronet 3.21a-Linux NewsLink 1.2