From Newsgroup: sci.crypt

## In this issue
1. [2024/355] Adaptively Secure Streaming Functional Encryption
2. [2025/1499] A Construction of Evolving $k$-threshold Secret ...
3. [2025/1812] Better Bounds for Finding Fixed-Degree Isogenies ...
4. [2025/2173] Systems Security Foundations for Agentic Computing
5. [2025/2174] LIME: High-Performance Private Inference with ...
6. [2025/2175] Extended Abstract: NICE-PAKE and TEMPO ...
7. [2025/2176] On the (Un)biasability of Existing Verifiable ...
8. [2025/2177] TAPIR: A Two-Server Authenticated PIR Scheme with ...
9. [2025/2178] PQCUARK: A Scalar RISC-V ISA Extension for ML-KEM ...
10. [2025/2179] Policy Compliant Secure Messaging
11. [2025/2180] Weight of Polynomial Products Mod ...
12. [2025/2181] SVP$_p$ is Deterministically NP-Hard for all $p > ...
13. [2025/2182] Cryptanalysis on Asymmetric Structured Key ...
14. [2025/2183] Hardware Implementation of Stealthy and Lightweight ...
15. [2025/2184] One-way Functions and Boundary Hardness of ...
16. [2025/2185] Fully Adaptive Threshold IBE and Signatures in the ...
17. [2025/2186] BEANIE rCo A 32-bit Cipher for Cryptographic ...
18. [2025/2187] Abuse Resistant Traceability with Minimal Trust for ...
19. [2025/2188] ALIOTH: An Efficient and Secure Weight-of-Evidence ...
20. [2025/2189] An Improved Quantum Algorithm for 3-Tuple Lattice ...
21. [2025/2190] Game-Theoretically Fair Distributed Coin Tossing ...
22. [2025/2191] Mobius: Enabling Byzantine-Resilient Single Secret ...
23. [2025/2192] Constant-time Quaternion Algorithms for SQIsign
24. [2025/2193] aLEAKator: HDL Mixed-Domain Simulation for Masked ...
25. [2025/2194] Turning Simulation into Construction: New Uses of ...
26. [2025/2195] Refined Modelling of the Primal Attack, and ...
27. [2025/2196] Cardinal: Bridging Bitcoin with Ownership Preservation
28. [2025/2197] Small-field hash-based SNARGs are less sound than ...
29. [2025/2198] Putting Multi into Multi-Signatures: Tight Security ...
30. [2025/2199] A Formal Security Proof of Masking: Reduction from ...
## 2024/355
* Title: Adaptively Secure Streaming Functional Encryption
* Authors: Pratish Datta, Jiaxin Guan, Alexis Korb, Amit Sahai
* [Permalink](https://eprint.iacr.org/2024/355)
* [Download](https://eprint.iacr.org/2024/355.pdf)
### Abstract
This paper presents the first adaptively secure streaming functional encryption (sFE) scheme for P/Poly. sFE extends traditional FE to vast and/or dynamically evolving data sets, enabling incremental encryption of streaming inputs and iterative partial decryption over encrypted prefixes.
The proposed sFE scheme is built from indistinguishability obfuscation for P/Poly and injective PRGs. We achieve this result via two core technical contributions which may be of independent interest. First, we introduce a novel "gluing" mechanism to achieve adaptive security by intertwining two schemes, each possessing one aspect of adaptive security. Second, we enhance the powerful Koppula-Lewko-Waters [STOC 2015] framework with a "sliding window" technique, enabling authenticated iterative computation with fresh inputs at each iteration.
Prior work by Guan, Korb, and Sahai [CRYPTO 2023] constructed sFE but only under a (semi-adaptive) function-selective security model, requiring all functional keys to be queried before observing any ciphertext. This severe limitation precludes practical scenarios and leaves adaptive security as a crucial open challenge rCo explicitly highlighted by their work rCo which we address in this paper.
## 2025/1499
* Title: A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring
* Authors: Qi Cheng, Hongru Cao, Sian-Jheng Lin, Nenghai Yu, Yunghsiang S. Han, Xianhong Xie
* [Permalink](https://eprint.iacr.org/2025/1499)
* [Download](https://eprint.iacr.org/2025/1499.pdf)
### Abstract
The threshold secret sharing scheme enables a dealer to distribute the share to every participant such that the secret is correctly recovered from a certain amount of shares. The traditional $(k, n)$ threshold secret sharing scheme requires that the number of participants $n$ is known in advance. In contrast, the evolving secret sharing scheme allows that $n$ can be uncertain and even ever-growing. In this paper, we consider the evolving secret sharing scenario. Based on the prefix codes, we propose a brand-new construction of evolving $k$-threshold secret sharing scheme for an $\ell$-bit secret over a polynomial ring, with correctness and perfect security. The proposed scheme is the first evolving $k$-threshold secret sharing scheme by generalizing Shamir's scheme onto a polynomial ring. Besides, the proposed scheme also establishes the connection between prefix codes and the evolving schemes for $k\geq2$. The analysis shows that the size of the $t$-th share is $(k-1)(\ell_t-1)+\ell$ bits, where $\ell_t$ denotes the length of a binary prefix code of encoding integer $t$. In particular, when $\delta$ code is chosen as the prefix code, the share size is $(k-1)\lfloor\lg t\rfloor+2(k-1)\lfloor\lg ({\lfloor\lg t\rfloor+1}) \rfloor+\ell$, which improves the prior best result $(k-1)\lg t+6k^4\ell\lg{\lg t}\cdot\lg{\lg {\lg t}}+ 7k^4\ell\lg k$, where $\lg$ denotes the binary logarithm. Specifically, when $k=2$, the proposal also provides a unified mathematical decryption for prior evolving $2$-threshold secret sharing schemes and also achieves the minimal share size for a single-bit secret, which is the same as the best-known scheme.
## 2025/1812
* Title: Better Bounds for Finding Fixed-Degree Isogenies via CoppersmithrCOs Method
* Authors: Marius A. Aardal, Diego F. Aranha, Yansong Feng, Yiming Gao, Yanbin Pan
* [Permalink](https://eprint.iacr.org/2025/1812)
* [Download](https://eprint.iacr.org/2025/1812.pdf)
### Abstract
The hardness of finding isogenies of degree $d$ between supersingular elliptic curves is a fundamental assumption in isogeny-based cryptography. Let $E_1$ and $E_2$ be supersingular elliptic curves defined over $\mathbb{F}_{p^2}$, and let $d$ be a smooth integer. %removed > p^{1/2} part.
At CRYPTO~2024, Ben-iina et al.\ proposed an algorithm with time complexity $\widetilde{O}(\max\{p^{1/2}, d/p^{5/8}\})$ in the classical setting and $\widetilde{O}(\max\{p^{1/4}, d^{1/2}/p^{1/4}\})$ in the quantum setting.
In this work, we first observe that their analysis omits a sub-exponential factor $\exp(O(\log^{3/4} p))$. We then improve their result to $\widetilde{O}(\max\{p^{1/2}, \exp(O(\log^{4/5} p)) \cdot d/p^{2/3}\})$ classically and $\widetilde{O}(\max\{p^{1/4}, \exp(O(\log^{4/5} p)) \cdot d^{1/2}/p^{1/3}\})$ quantumly. Our approach relies on small-root bounds for CoppersmithrCOs method applied to a four-variable integer equation. To this end, we adapt the explicit asymptotic formulas for small-root bounds introduced by Feng et al.\ (CRYPTO~2025) in the modular setting to the integer setting. As an additional application, we strengthen the attack of Ben-iina et al.\ on the SIDH signature scheme by Basso et al. (ACNS~2024). We expect that these refined techniques for CoppersmithrCOs method will be valuable for further post-quantum cryptanalysis.
## 2025/2173
* Title: Systems Security Foundations for Agentic Computing
* Authors: Mihai Christodorescu, Earlence Fernandes, Ashish Hooda, Somesh Jha, Johann Rehberger, Khawaja Shams
* [Permalink](https://eprint.iacr.org/2025/2173)
* [Download](https://eprint.iacr.org/2025/2173.pdf)
### Abstract
This paper articulates short- and long-term research problems in AI agent security and privacy, using the lens of computer systems security. This approach examines end-to-end security properties of entire systems, rather than AI models in isolation. While we recognize that hardening a single model is useful, it is important to realize that it is often insufficient. By way of an analogy, creating a model that is always helpful and harmless is akin to creating software that is always helpful and harmless. The collective experience of decades of cybersecurity research and practice shows that this is insufficient. Rather, constructing an informed and realistic attacker model before building a system, applying hard-earned lessons from software security, and continuous improvement of security posture is a tried-and-tested approach to securing real computer systems. A key goal is to examine where research challenges arise when applying traditional security principles in the context of AI agents. A secondary goal of this report is to distill these ideas for AI and ML practitioners and researchers. We discuss the challenges of applying security principles to agentic computing, present 11 case studies of real attacks on agentic systems, and define a series of new research problems specific to the security of agentic systems.
## 2025/2174
* Title: LIME: High-Performance Private Inference with Lightweight Model and Batch Encryption
* Authors: Huan-Chih Wang, Ja-Ling Wu
* [Permalink](https://eprint.iacr.org/2025/2174)
* [Download](https://eprint.iacr.org/2025/2174.pdf)
### Abstract
The rapid pace of artificial intelligence (AI) and machine learning techniques has necessitated the development of large-scale models that rely on energy-intensive data centers, thereby raising environmental sustainability. Simultaneously, the increasing significance of privacy rights has led to the emergence of Privacy-Preserving Machine Learning (PPML) technologies, which aim to ensure data confidentiality. Although homomorphic encryption (HE) facilitates computations on encrypted data, it entails considerable computational costs and challenges, which impede the effective deployment of privacy-enhancing applications with large models.
To create a more sustainable and secure AI world, we propose LIME, a pure HE-based PPML solution, by integrating two techniques: element-wise channel-to-slot packing (ECSP) and power-of-two channel pruning (PCP). ECSP leverages abundant slots to pack multiple samples within ciphertexts, facilitating batch inference. PCP prunes the channels of convolutional layers by powers of two, thereby reducing computational demands and enhancing the packing capabilities of pruned models. Additionally, we implement the ReLU-before-addition block in ResNet to mitigate accuracy degradation caused by approximations with quadratic polynomials.
We evaluated LIME using ResNet-20 on CIFAR-10, VGG-11 on CIFAR-100, and ResNet-18 on Tiny-ImageNet. Using the original models, LIME attains up to 2.1% and 8.4% accuracy improvements over the methods of Lee et al. (IEEE ACCESSrCO21) and AESPA (arXiv:2201.06699), which employ high- and low-degree polynomial ReLU approximations, respectively. Even with 75% parameter pruning, LIME retains higher accuracy than AESPA. Using the state-of-the-art ORION (ASPLOS '25) as the convolution backend and evaluating on the original models, LIME achieves speedups of 41.5$\times$ and 8$\times$ over ORION integrated with Lee et al. and AESPA, respectively. For models pruned by 90%, these speedups increase to 202.5$\times$ and 35.1$\times$, respectively.
## 2025/2175
* Title: Extended Abstract: NICE-PAKE and TEMPO Instantiations from MLWE Rerandomizable Splittable KEMs
* Authors: Nouri Alnahawi, Alexander Wiesmaier
* [Permalink](https://eprint.iacr.org/2025/2175)
* [Download](https://eprint.iacr.org/2025/2175.pdf)
### Abstract
We propose two novel instantiations for the NICE-PAKE and TEMPO protocols, which were presented by Alnahawi et al. (ePrint:2024/1957), and Arriaga, Barbosa and Jarecki (ePrint:2025/1399) repectively. Our instantiations are not formally analyzed yet, but build upon known KEM security assumptions and well-studied PAKE designs. Therefore, we believe there is a great chance that a formal proof in the Universal Composability (UC) framework should also hold.
Our constructions combine three concepts: 1) Lattice KEMs with Splittable public keys of the form As+e as introduced in Arriaga et al. (AC24:ABJS), Alnahawi et al. (ePrint:2024/1957) and Arriaga et al. (ePrint:2025/1399). 2) The Programmable Only Once Function (POPF) realized as a 2-round Feistel (2F) as in McQuoid, Rosulek and Roy (CCS20:MRR) and Arriaga , Barbosa and Jarecki (ePrint:2025/231). 3) Rerandomizable KEM as introduced in Duverger et al. (CCS25:DFJ+).
Similar to the aforementioned works, our goal is to eliminate the usage of the Ideal Cipher (IC) in (O)EKE-style KEM-based PQC PAKEs, the motivation of which is adequately and extensively explained in the cited literature. Our main contribution lies within the following two aspects: 1) Mitigating malicious public key generation attacks in the NICE-PAKE construction. 2) Defining a mechanism to realize the missing group operation in the 2F public key authentication step in NoIC-PAKE. Briefly put, we utilize the rerandomization procedure of (CCS25:DFJ+) to sample a second uniform MLWE sample, which is in turn used to shift the initiator's public key forming another fresh sample that yields indistinguishable from uniform. By doing so, we assume that we can enhance the security of NICE-PAKE to withstand a certain class of attacks, and reduce the computational complexity of the 2F instantiation relying on obfuscation in the OQUAKE variant of the 2F PAKE, which was introduced by Vos et al. (ePrint:2025/1343).
Obviously, we cannot ascertain the security of our proposed constructions without conducting a complete and thorough formal analysis. Hence, remaining open questions and future work include defining an indistinguishable UC simulator in the ideal UC world that is also capable of extracting adversarial password guesses. Further, we need to identify the concrete KEM properties required to prove security in UC via the common game-hopping reductionist proof approach.
## 2025/2176
* Title: On the (Un)biasability of Existing Verifiable Random Functions
* Authors: Davide Carnemolla, Dario Catalano, Valentina Frasca, Emanuele Giunta * [Permalink](https://eprint.iacr.org/2025/2176)
* [Download](https://eprint.iacr.org/2025/2176.pdf)
### Abstract
Verifiable Random Functions (VRFs) play a fundamental role in modern blockchain designs because of their applications in leader election protocols. In such contexts, however, the original definition by Micali, Rabin and Vadhan (FOCS 99), falls short at guaranteeing fairness when keys are sampled maliciously.
The elegant notion of unbiasable VRF, recently proposed by Giunta and Stewart (Eurocrypt 24), addresses these concerns while remaining simple to state and easy to realize, at least in the random oracle model. Achieving unbiasability in the standard model is a different story, though: all known constructions rely on compilers that invariably reduce the efficiency of the VRF from which one starts.
In this paper, we look at the unbiasability of existing VRFs in the standard model.
Our findings are mostly negative; we show that, essentially, all known constructions are not natively unbiasable. We do so by showing classes of attacks that (almost) completely cover the set of existing VRF constructions.
On the positive side, we show that some concrete schemes (and notably the well-known Dodis-Yampolskiy VRF) can be modified to achieve meaningful notions of unbiasability, while retaining their original efficiency.
## 2025/2177
* Title: TAPIR: A Two-Server Authenticated PIR Scheme with Preprocessing
* Authors: Francesca Falzon, Laura Hetz, Annamira O'Toole
* [Permalink](https://eprint.iacr.org/2025/2177)
* [Download](https://eprint.iacr.org/2025/2177.pdf)
### Abstract
Authenticated Private Information Retrieval (APIR) enables a client to retrieve a record from a public database and verify that the record is rCLauthenticrCY without revealing any information about which record was requested. In this work, we propose Tapir: the first two-server APIR scheme to achieve both sublinear communication and computation complexity for queries, while also supporting dates. Our scheme builds upon the unauthenticated two-server PIR scheme SinglePass (Lazzaretti and Papamanthou, USENIXrCO24). Due to its modular design, Tapir provides different trade-offs depending on the underlying vector commitment scheme used.
Moreover, Tapir is the first APIR scheme with preprocessing to support appends and edits in time linear in the database partition size. This makes it an ideal candidate for transparency applications that require support for integrity, database appends, and private lookups. We provide a formal security analysis and a prototype implementation that demonstrates our schemerCOs efficiency. Tapir incurs as little as 0.11 % online bandwidth overhead for databases of size $2^{22}$, compared to the unauthenticated SinglePass. For databases of size $\geq 2^{20}$, our scheme, when instantiated with Merkle trees, outperforms all prior multi-server APIR schemes with respect to online runtime.
## 2025/2178
* Title: PQCUARK: A Scalar RISC-V ISA Extension for ML-KEM and ML-DSA
* Authors: Xavier Carril, Alicia Manuel Pasoot, Emanuele Parisi, Carlos Andr|-s Lara-Ni|#o, Oriol Farr|as, Miquel Moret||
* [Permalink](https://eprint.iacr.org/2025/2178)
* [Download](https://eprint.iacr.org/2025/2178.pdf)
### Abstract
Recent advances in quantum computing pose a threat to the security of digital communications, as large-scale quantum machines can break commonly used cryptographic algorithms, such as RSA and ECC. To mitigate this risk, post-quantum cryptography (PQC) schemes are being standardized, with recent NIST recommendations selecting two lattice-based algorithms: ML-KEM for key encapsulation and ML-DSA for digital signatures. Two computationally intensive kernels dominate the execution of these schemes: the Number-Theoretic Transform (NTT) for polynomial multiplication and the Keccak-f1600 permutation function for polynomial sampling and hashing. This paper presents PQCUARK, a scalar RISC-V ISA extension that accelerates these key operations. PQCUARK integrates two novel accelerators within the core pipeline: (i) a packed SIMD butterfly unit capable of performing NTT butterfly operations on 2|u32bit or 4|u16bit polynomial coefficients, and (ii) a permutation engine that delivers two Keccak rounds per cycle, hosting a private state and a direct interface to the core Load Store Unit, eliminating the need for a custom register file interface. We have integrated PQCUARK into an RV64 core and deployed it on an FPGA. Experimental results demonstrate that PQCUARK provides up to 10.1|u speedup over the NIST baselines and 2.3|u over the optimized software, and it outperforms similar state-of-the-art approaches between 1.4-12.3|u in performance. ASIC synthesis in GF22-FDSOI technology shows a moderate core area increase of 8% at 1.2 GHz, with PQCUARK units being outside the critical path.
## 2025/2179
* Title: Policy Compliant Secure Messaging
* Authors: Jo|2l Alwen, Xiaohui Ding, Sanjam Garg, Yiannis Tselekounis
* [Permalink](https://eprint.iacr.org/2025/2179)
* [Download](https://eprint.iacr.org/2025/2179.pdf)
### Abstract
We initiate the holistic study of Policy Compliant Secure Messaging (PCSM). A content policy is a predicate over messages deciding which messages are considered harmful and which not. A PCSM protocol is a type of end-to-end encrypted (E2EE) messaging system that guarantees E2EE privacy and authenticity for all policy compliant messages but detects and verifiably reports harmful content prior to its delivery. This stands in contrast to prior content moderation systems for E2EE messaging where detection relies on receivers reporting the harmful content themselves which makes them unsuited for most PCSM applications (e.g., for preventing the wilful distribution of harmful content). Our holistic PCSM notion explicitly captures several new roles such as policy creator, auditor and judge, to more accurately separate and model the different goals and security concerns of stakeholders when deploying PCSM.
We present efficient PCSM constructions for arbitrary policy classes, as well as for hash-based ones, achieving various levels of security, while maintaining the core security properties of the underlying E2EE layer. For hash-based PCSM, we encapsulate ApplerCOs recent PSI protocol used in their content moderation system, and we properly adapt it to realize the desired PCSM functionality, and analyze the resulting protocolrCOs security. To our knowledge, our work is the first that rigorously study ApplerCOs PSI for server-side content moderation within the broader context of secure messaging, addressing the diverse goals and security considerations of stakeholders when deploying larger systems.
## 2025/2180
* Title: Weight of Polynomial Products Mod $(X^n+1)$-Application to the HQC Cryptosystem-
* Authors: Laila El Aimani
* [Permalink](https://eprint.iacr.org/2025/2180)
* [Download](https://eprint.iacr.org/2025/2180.pdf)
### Abstract
We consider the following problem: given two random polynomials $x$ and $y$ in the ring $\F_2[X]/(X^n+1)$, our goal is to compute the expectation and variance of the weight of their product $x\cdot y$, where the weight of a binary polynomial is defined as the number of its nonzero coefficients.
We consider two models for random polynomials $x$ and $y$: (1) the uniform slice case with fixed weights $w_x,w_y$, and (2) the binomial case where their coefficients are independent Bernoulli variables with success probabilities $p_x$ and $p_y$ respectively.
Our work finds a direct application in the accurate analysis of the decryption failure rate for the HQC code-based encryption scheme. The original construction relied on heuristic arguments supported by experimental data. Later, Kawachi provided a formally proven security bound, albeit a much weaker one than the heuristic estimate in the original construction. A fundamental limitation of both analyses is their restriction to the binomial case, a simplification that compromises the resulting security guarantees.

Our analysis provides the first precise computation of the expectation and variance of weight($x\cdot y$) across both the uniform slice and binomial models. The results confirm the soundness of the HQC security guarantees and allow for a more informed choice of the scheme parameters that optimizes the trade-off security and efficiency.
## 2025/2181
* Title: SVP$_p$ is Deterministically NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$
* Authors: Isaac M Hair, Amit Sahai
* [Permalink](https://eprint.iacr.org/2025/2181)
* [Download](https://eprint.iacr.org/2025/2181.pdf)
### Abstract
We prove that SVP$_p$ is NP-hard to approximate within a factor of $2^{\log^{1 - \varepsilon} n}$, for all constants $\varepsilon > 0$ and $p > 2$, under standard deterministic Karp reductions. This result is also the first proof that \emph{exact} SVP$_p$ is NP-hard in a finite $\ell_p$ norm. Hardness for SVP$_p$ with $p$ finite was previously only known if NP $\not \subseteq$ RP, and under that assumption, hardness of approximation was only known for all constant factors. As a corollary to our main theorem, we show that under the Sliding Scale Conjecture, SVP$_p$ is NP-hard to approximate within a small polynomial factor, for all constants $p > 2$.

Our proof techniques are surprisingly elementary; we reduce from a regularized PCP instance directly to the shortest vector problem by using simple gadgets related to Vandermonde matrices and Hadamard matrices.
## 2025/2182
* Title: Cryptanalysis on Asymmetric Structured Key Agreement Schemes
* Authors: Koki Jimbo
* [Permalink](https://eprint.iacr.org/2025/2182)
* [Download](https://eprint.iacr.org/2025/2182.pdf)
### Abstract
We study several asymmetric structured key agreement schemes based on noncommutative matrix operations, including the recent proposal of Lizama as well as the strongly asymmetric algorithms SAA-3 and SAA-5 of Accardi
et al.\ We place them in a common algebraic framework for
public key agreement and identify simple structural conditions under which an eavesdropper can reconstruct an effective key-derivation map and reduce key recovery to solving linear systems over finite fields. We then show that the three matrix-based schemes mentioned above all instantiate our algebraic framework and can therefore be broken in polynomial time from public
information alone. In particular, their security reduce to the hardness of linear-algebraic problems and does not exceed that of the underlying discrete logarithm problem. Our results demonstrate that the weakness of these schemes is structural rather than parametric, and that minor algebraic modifications are insufficient to repair them.
## 2025/2183
* Title: Hardware Implementation of Stealthy and Lightweight Backdoor for CRYSTALS-Kyber
* Authors: Suraj Mandal, Prasanna Ravi, M Dhilipkumar, Debapriya Basu Roy, Anupam Chattopadhyay
* [Permalink](https://eprint.iacr.org/2025/2183)
* [Download](https://eprint.iacr.org/2025/2183.pdf)
### Abstract
The threat of practical quantum attacks has catapulted viable alternatives like Post-Quantum Cryptography (PQC) into prominence. The adoption and integration of standardized PQC primitives across the entire digital stack are promoted by various standardization bodies, governments, and major corporate houses. A serious challenge in quantum migration is to ensure that there is no hidden backdoor in the PQC implementations of a hybrid cryptosystem (support for both pre-quantum and post-quantum algorithms), which are often procured from a third-party vendor. In this manuscript, we investigate the possibility of a kleptographic backdoor on the NIST-recommended key-encapsulation mechanism CRYSTALS-Kyber. The modified Kyber key-generation algorithm achieves indistinguishable decryption failure probability compared to the original CRYSTALS-Kyber. The kleptographic module is also implemented in FPGA, embedded inside the CRYSTALS- Kyber accelerator with a very low area overhead (283 LUTs or 2% of total area), and thus can easily pass performance and functionality tests.
## 2025/2184
* Title: One-way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity
* Authors: Yanyi Liu, Rafael Pass
* [Permalink](https://eprint.iacr.org/2025/2184)
* [Download](https://eprint.iacr.org/2025/2184.pdf)
### Abstract
We revisit the question of whether worst-case hardness of the time-bounded Kolmogorov complexity problem, $\KpolyA$---that is, determining whether a string is ``structured" (i.e., $K^t(x) < n-1$) or ``random" (i.e., $K^{\poly(t)} \geq n-1$)---suffices to imply the existence of one-way functions (OWF). Liu-Pass (CRYPTO'25) recently showed that worst-case hardness of a \emph{boundary} version of $\KpolyA$---where, roughly speaking, the goal is to decide whether given an instance $x$, (a)
$x$ is $K^\poly$-random (i.e., $K^{\poly(t)}(x) \geq n-1$), or just close to $K^\poly$-random (i.e., $K^{t}(x) < n-1$ \emph{but} $K^{\poly(t)}> n - \log n$)---characterizes OWF,
but with either of the following caveats (1) considering a non-standard notion of \emph{probabilistic $K^t$}, as opposed to the standard notion of $K^t$, or (2) assuming somewhat strong, and non-standard, derandomization assumptions.

In this paper, we present an alternative method for establishing their result which enables significantly weakening the caveats. First, we show that boundary hardness of the more standard \emph{randomized} $K^t$ problem suffices (where randomized $K^t(x)$ is defined just like $K^t(x)$ except that the program generating the string $x$ may be randomized).

As a consequence of this result, we can provide a characterization also in terms of just ``plain" $K^t$ under the most standard derandomization assumption (used to derandomize just $\BPP$ into $\P$)---namely $\E \not\subseteq {\sf ioSIZE}[2^{o(n)}]$.
Our proof relies on language compression schemes of Goldberg-Sipser (STOC'85); using the same technique, we also present the the first worst-case to average-case reduction for the \emph{exact} $\KpolyA$ problem (under the same standard derandomization assumption), improving upon Hirahara's celebrated results (STOC'18, STOC'21) that only applied to a \emph{gap} version of the $\KpolyA$ problem, referred to as $\GapKpolyA$, where the goal is to decide whether $K^t(x) \leq n-O(\log n))$ or $K^{\poly(t)}(x) \geq n-1$ and under the same derandomization assumption.
## 2025/2185
* Title: Fully Adaptive Threshold IBE and Signatures in the Standard Model
* Authors: Jiayun Yan, Yu Li, Jie Chen, Haifeng Qian, Xiaofeng Chen, Debiao He * [Permalink](https://eprint.iacr.org/2025/2185)
* [Download](https://eprint.iacr.org/2025/2185.pdf)
### Abstract
We present fully adaptive secure threshold IBE and threshold signatures, which rely on the $k$-Linear assumption in the standard model over asymmetric pairing groups. In particular, our threshold signature scheme achieves a non-interactive signing process and an adaptively secure guarantee as strong as Das-Ren (CRYPTO'24), while their proof relies on the random oracle model. We achieve our results by following steps: First, we design two threshold IBE schemes against adaptive corruptions in the composite-order and prime-order groups by adopting the dual system groups encoding. Second, we provide a generic transform from threshold IBE to threshold signatures, following Naor's paradigm, which reduces the fully adaptive corruption security of threshold signatures to threshold IBE. Third, we present two threshold signatures instantiations in composite-order and prime-order groups.
## 2025/2186
* Title: BEANIE rCo A 32-bit Cipher for Cryptographic Mitigations against Software Attacks
* Authors: Simon Gerhalter, Samir Hod++i-c, Marcel Medwed, Marcel Nageler, Artur Folwarczny, Ventzi Nikov, Jan Hoogerbrugge, Tobias Schneider, Gary McConville, Maria Eichlseder
* [Permalink](https://eprint.iacr.org/2025/2186)
* [Download](https://eprint.iacr.org/2025/2186.pdf)
### Abstract
In modern CPU architectures, various security features to mitigate software attacks can be found. Examples of such features are logical isolation, memory tagging or shadow stacks. Basing such features on cryptographic isolation instead of logical checks can have many advantages such as lower memory overhead and more robustness against misconfiguration or low-cost physical attacks. The disadvantage of such an approach is however that the cipher that has to be introduced has a severe impact on the system performance, either in terms of additional cycles or a decrease of the maximum achievable frequency. Finally, as of today, there is no suitable low-latency cipher design available for encrypting 32-bit words as is common in microcontrollers. In this paper, we propose a 32-bit tweakable block cipher tailored to memory encryption for microcontroller units. We optimize this cipher for low latency, which we achieve by a careful selection of components for the round function and leveraging an attack scenario similar to the one used to analyze the cipher SCARF. To mitigate some attack vectors introduced by this attack scenario, we deploy a complex tweak-key schedule. Due to the shortage of suitable 32-bit designs, we compare our design to various low-latency ciphers with different block sizes. Our hardware implementation shows competitive latency numbers.
## 2025/2187
* Title: Abuse Resistant Traceability with Minimal Trust for Encrypted Messaging Systems
* Authors: Zhongming Wang, Tao Xiang, Xiaoguo Li, Guomin Yang, Biwen Chen, Ze Jiang, Jiacheng Wang, Chuan Ma, Robert H. Deng
* [Permalink](https://eprint.iacr.org/2025/2187)
* [Download](https://eprint.iacr.org/2025/2187.pdf)
### Abstract
Encrypted messaging systems provide end-to-end security for users but obstruct content moderation, making it difficult to combat online abuses. Traceability offers a promising solution by enabling platforms to identify the originator/spreader of messages, yet this capability can be abused for mass surveillance of innocent messages. To mitigate this risk, existing approaches restrict traceability to (problematic) messages that are reported by multiple users or are on a predefined blocklist. However, these solutions either overtrust a specific entity (e.g., the party defining the blocklist) or rely on the unrealistic assumption of non-collusion between servers run by a single platform.
In this paper, we propose an abuse-resistant source tracing scheme that distributes traceability across distinct real-world entities. Specifically, we formally define its syntax and prove its security properties. Our scheme realizes two essential principles: minimal trust, which ensures that traceability cannot be abused as long as a single participant involved in tracing is honest, even if all others collude; and minimal information disclosure, which prevents participants from acquiring any information (e.g., communication parties' identities) unnecessary for tracing. We implemented our scheme using techniques deployed by Signal, and our evaluation shows it offers comparable performance to state-of-the-art schemes that are vulnerable to abuse.
## 2025/2188
* Title: ALIOTH: An Efficient and Secure Weight-of-Evidence Framework for Privacy-Preserving Data Processing
* Authors: Ye Dong, Xiangfu Song, W.j Lu, Xudong Chen, Yaxi Yang, Ruonan Chen, Tianwei Zhang, Jin-Song Dong
* [Permalink](https://eprint.iacr.org/2025/2188)
* [Download](https://eprint.iacr.org/2025/2188.pdf)
### Abstract
Secure two-party computation (2PC)-based privacy-preserving machine learning (ML) has made remarkable progress in recent years. However, most existing works overlook the privacy challenges that arise during the data preprocessing stage.
Although some recent studies have introduced efficient techniques for privacy-preserving feature selection and data alignment on well-structured datasets, they still fail to address the privacy risks involved in transforming raw data features into ML-effective numerical representations.
In this work, we present ALIOTH, an efficient 2PC framework that securely transforms raw categorical and numerical features into Weight-of-Evidence (WoE)-based numerical representations under both vertical and horizontal data partitions.
By incorporating our proposed partition-aware 2PC protocols and vectorization optimizations, ALIOTH efficiently generates WoE-transformed datasets in secret.
To demonstrate scalability, we conduct experiments on diverse datasets. Notably, ALIOTH can transform 3 million data samples with 100 features securely within half an hour over a wide-area network. Furthermore, ALIOTH can be seamlessly integrated with existing 2PC-based ML frameworks. Empirical evaluations on real-world financial datasets show ALIOTH improves both the predictive performance of logistic regression and 2PC training efficiency.
## 2025/2189
* Title: An Improved Quantum Algorithm for 3-Tuple Lattice Sieving
* Authors: Lynn Engelberts, Yanlin Chen, Amin Shiraz Gilani, Maya-Iggy van Hoof, Stacey Jeffery, Ronald de Wolf
* [Permalink](https://eprint.iacr.org/2025/2189)
* [Download](https://eprint.iacr.org/2025/2189.pdf)
### Abstract
The assumed hardness of the Shortest Vector Problem in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP are via so-called sieving methods. While these still take exponential time in the dimension $d$, they are significantly faster than non-heuristic approaches and their heuristic assumptions are verified by extensive experiments. $k$-Tuple sieving is an iterative method where each iteration takes as input a large number of lattice vectors of a certain norm, and produces an equal number of lattice vectors of slightly smaller norm, by taking sums and differences of $k$ of the input vectors. Iterating these ''sieving steps'' sufficiently many times produces a short lattice vector. The fastest attacks (both classical and quantum) are for $k=2$, but taking larger $k$ reduces the amount of memory required for the attack. In this paper we improve the quantum time complexity of 3-tuple sieving from $2^{0.3098 d}$ to $2^{0.2846 d}$, using a two-level amplitude amplification aided by a preprocessing step that associates the given lattice vectors with nearby ''center points'' to focus the search on the neighborhoods of these center points. Our algorithm uses $2^{0.1887d}$ classical bits and QCRAM bits, and $2^{o(d)}$ qubits. This is the fastest known quantum algorithm for SVP when total memory is limited to $2^{0.1887d}$.
## 2025/2190
* Title: Game-Theoretically Fair Distributed Coin Tossing With Private Preferences
* Authors: Pedro Branco, Pratik Soni, Sri AravindaKrishnan Thyagarajan, Ke Wu
* [Permalink](https://eprint.iacr.org/2025/2190)
* [Download](https://eprint.iacr.org/2025/2190.pdf)
### Abstract
Secure coin-tossing is typically modeled as an input-less functionality, where parties with no private inputs jointly generate a fair coin. In the dishonest majority setting, however, a strongly fair coin-tossing protocol is impossible. To circumvent this barrier, recent work has adopted the weaker notion of game-theoretic fairness, where adversaries are rational parties with preferences for specific outcomes, seeking to bias the coin in their favor.
Yet these preferences may encode secret information, making prior protocols that assume preferences are public, fundamentally incompatible with privacy.
We initiate a comprehensive study of privacy-preserving game-theoretically fair coin-tossing, where the preferences of honest parties remain private.
We propose a simulation-based security framework and a new ideal functionality that reconciles both preference-privacy and game-theoretic fairness. A key ingredient is a certifying authority that authenticates each partyrCOs preference and publishes only aggregate statistics, preventing misreporting while hiding parties' preferences.
The functionality guarantees that every honest party receives an output: either a uniform coin; or, if an adversary deviates, a coin that strictly decreases the adversarial coalition's expected utility.
Within this framework, we construct a protocol realizing our ideal functionality under standard cryptographic assumptions that works for both binary and general $m$-sided coin-tossing. Our schemes tolerate the same optimal (or nearly optimal) corruption thresholds as the best known protocols with public preferences (Wu-Asharov-Shi, EUROCRYPT '22; Thyagarajan-Wu-Soni, CRYPTO '24). Technically, our protocols combine authenticated preferences with an anonymous communication layer that decouples identities from preference-dependent actions, together with a deviation-penalty mechanism that enforces game-theoretic fairness.
Our work is the first to reconcile game-theoretic fairness with preference privacy, offering new definitional tools and efficient protocols for rational multi-party computation in dishonest majority settings.
## 2025/2191
* Title: Mobius: Enabling Byzantine-Resilient Single Secret Leader Election with Uniquely Verifiable State
* Authors: Hanyue Dou, Peifang Ni, Yingzi Gao, Jing Xu
* [Permalink](https://eprint.iacr.org/2025/2191)
* [Download](https://eprint.iacr.org/2025/2191.pdf)
### Abstract
Single Secret Leader Election (SSLE) protocol facilitates the election of a single leader per round among a group of registered nodes while ensuring unpredictability. Ethereum has identified SSLE as an essential component in its development roadmap and has adopted it as a potential solution to counteract potential attacks. However, we identify a new form of attack termed the state uniqueness attack that is caused by malicious leaders proposing multiple publicly verifiable states. This attack undermines the property of uniqueness in subsequent leader elections and, with high probability, leads to violations of fundamental security properties of the over-layer protocol such as liveness. The vulnerability stems inherently from the designs reducing the uniqueness guarantee to a unique state per election, and can be generalized to the existing SSLE constructions. We further quantify the severity of this attack based on theoretical analysis and real-world executions on Ethereum, highlighting the critical challenges in designing provably secure SSLE protocols.
To address the state uniqueness attack while ensuring both security and practical performance, we present a universal SSLE protocol called Mobius that does not rely on extra trust assumptions. Specifically, Mobius prevents the generation of multiple verifiable states for each election and achieves a unique state across consecutive executions through an innovative approximately-unique randomization mechanism. In addition to providing a comprehensive security analysis in the Universal Composability framework, we develop a proof-of-concept implementation of Mobius, and conduct extensive experiments to evaluate the security and overhead. The experimental results show that Mobius exhibits enhanced security while significantly reducing communication complexity throughout the protocol execution, achieving over 80% reduction in the registration phase.
## 2025/2192
* Title: Constant-time Quaternion Algorithms for SQIsign
* Authors: Andrea Basso, Chenfeng He, David Jacquemin, Fatna Kouider, P|-ter Kutas, Anisha Mukherjee, Sina Schaeffler, Sujoy Sinha Roy
* [Permalink](https://eprint.iacr.org/2025/2192)
* [Download](https://eprint.iacr.org/2025/2192.pdf)
### Abstract
SQIsign, the only isogeny-based signature competing in the ongoing NIST call for additional signatures, offers the most compact key and signature sizes among all other candidates. It combines isogenies with quaternion arithmetic for its signing procedure.
In this work, we address a gap in the current implementation of SQIsign: the absence of constant-time algorithms for quaternion arithmetic. We propose constant-time algorithmic formulations for three fundamental routines in SQIsign's quaternion layer.
First, we discuss a constant-time Hermite Normal Form (HNF) algorithm. We then present a new constant-time approach for computing a generator of a quaternion ideal, replacing the exhaustive search-based approach used in SQIsign. Our approach eliminates the need for coefficient scanning, coprimality tests, and norm evaluation loops, yielding a data-independent and deterministic procedure.
Finally, we design a constant-time version of the GeneralizedRepresentInteger algorithm for solving norm equations in special extremal orders. We circumvent timing dependencies arising from primality checks, modular square root calculations, and Euclidean division steps by introducing a regularized control flow with fixed-iteration sampling and branch-free arithmetic. We also show that the tools developed along the way enable a constant-time version of the recently introduced Qlapoti algorithm.
In our constant-time algorithms, the cost of large operand operations remains a bottleneck for the constant-time HNF and GeneralizedRepresentInteger. We believe our work will facilitate secure and efficient implementations and inspire further works on deployment-level optimizations.
## 2025/2193
* Title: aLEAKator: HDL Mixed-Domain Simulation for Masked Hardware & Software Formal Verification
* Authors: No|- Amiot, Quentin Meunier, Karine Heydemann, Emmanuelle Encrenaz
* [Permalink](https://eprint.iacr.org/2025/2193)
* [Download](https://eprint.iacr.org/2025/2193.pdf)
### Abstract
Verifying the security of masked hardware and software implementations, under advanced leakage models, remains a significant challenge, especially when accounting for glitches, transitions and CPU micro-architectural specifics. Existing verification approaches are either restricted to small hardware gadgets, small programs on CPUs such as Sboxes, limited leakage models, or require hardware-specific prior knowledge. In this work, we present aLEAKator, an open-source framework for the automated formal verification of masked cryptographic accelerators and software running on CPUs from their HDL descriptions. Our method introduces mixed-domain simulation, enabling precise modeling and verification under various (including robust and relaxed) 1-probing leakage models, and supports variable signal granularity without being restricted to 1-bit wires. aLEAKator also supports verification in the presence of lookup tables, and does not require prior knowledge of the target CPU architecture. Our approach is validated against existing tools and real-world measurements while providing innovative results such as the verification of a full, first-order masked AES on various CPUs.
## 2025/2194
* Title: Turning Simulation into Construction: New Uses of NIZK Simulators
* Authors: Stephan Krenn, Kai Samelin, Daniel Slamanig
* [Permalink](https://eprint.iacr.org/2025/2194)
* [Download](https://eprint.iacr.org/2025/2194.pdf)
### Abstract
Simulation is a fundamental technique in cryptography, central to security proofs, probably most well-known is its use for showing zero-knowledge. In this paper, we consider simulations no longer being merely a proof technique, but to constructively use simulators of non-interactive zero-knowledge proofs (NIZKs) as an integral component of cryptographic designs. We have occasionally seen such a use, e.g., in designated verifier signatures (DVS), deniable encryption, or the recent concept of anamorphic encryption. However, it was never explicity explored as a stand-alone concept, which is the goal of this paper.
By embedding simulated proofs directly into concrete systems, we unlock cryptographic functionalities that were previously out of reach under standard assumptions or required prohibitively complex techniques. In other words, by incorporating simulated proofs into the ``real'' world, rather than the simulated one, we achieve conceptually more elegant primitives. As a primer, we construct a secure signature scheme whose security hinges on a simulated proof of a false statement, i.e., the ludicrous statement $1 = 2$.
To illustrate the broader potential of this approach, we present new and simple constructions of chameleon hash functions with strong privacy guarantees (e.g., full indistinguishability), that do not require a trusted setup. Additionally, we present a very simple DVS with tight security proofs and a strengthened notion of non-transferability.
Based on the zero-knowledge guarantees of the underlying NIZKs, the resulting constructions achieve privacy even if the adversary is allowed to choose the random coins to set up the cryptographic material. To model this, we introduce the notion of trapdoor-detectable zero-knowledge, which may be of independent interest.
## 2025/2195
* Title: Refined Modelling of the Primal Attack, and Variants Against Module-Learning With Errors
* Authors: Paola de Perthuis, Filip Trenki-c
* [Permalink](https://eprint.iacr.org/2025/2195)
* [Download](https://eprint.iacr.org/2025/2195.pdf)
### Abstract
The primal attack reduces Learning with Errors (LWE) to the unique Shortest Vector Problem (uSVP), and then applies lattice reduction such as BKZ to solve the latter. Estimating the cost of the attack is required to evaluate the security of constructions based on LWE.
Existing fine-grained estimators for the cost of the primal attack, due to Dachman-Soled--Ducas--Gong--Rossi (CRYPTO 2020) and Postlethwaite--Virdia (PKC 2021), differ from experimental data as they implicitly assume the unique shortest vector is resampled several times during the attack, changing its length. Furthermore, these estimators consider only the first two moments of the LWE secret and error, and therefore do not differentiate between distinct centred distributions with equal variances. We remedy both issues by initially fixing the short vector's length, and later integrating over its distribution. We provide extensive experimental evidence that our estimators are more accurate and faithfully capture the behaviour of different LWE distributions.
In the case of Module-LWE, lattice reduction utilising the module structure could lead to cheaper attacks. We build upon the analysis of module lattice reduction by Ducas--Engelberts--Perthuis (Asiacrypt 2025), providing a simulator for Module-BKZ generalising the BKZ simulator of Chen--Nguyen (Asiacrypt 2011). We design estimators for a module variant of the primal attack, supporting our analysis with experimental evidence. Asymptotically, we show the module primal attack over a degree $d$ number field $K$ has a reduced cost, resulting in a subexponential gain, whenever the discriminant $\Delta_K$ satisfies $\vert \Delta_K \vert < d^d$, one such case being non-power-two cyclotomics.
## 2025/2196
* Title: Cardinal: Bridging Bitcoin with Ownership Preservation
* Authors: Lukas Aumayr, Jesus Diaz, Dimitar Jetchev, Aggelos Kiayias
* [Permalink](https://eprint.iacr.org/2025/2196)
* [Download](https://eprint.iacr.org/2025/2196.pdf)
### Abstract
Cross-chain bridges have emerged as key components of blockchain infrastructure, enabling digital assets to flow across chains and benefit from non-native features. While early bridge designs were fraught with brittle trust assumptions, more recent designs, even within Bitcoin's script limits, can operate in a trust-minimized setting. Given this ever-increasing expansion of blockchain bridge systems, a critical question regarding custody arises: When a user's coins cross a bridge back and forth, is there a possibility that they are substituted with other coins upon return? Naturally, if cryptocurrencies were truly fungible, this would not be a consequential event. Nevertheless, chain analytics algorithms as applied to Bitcoin, Ethereum, and other popular chains can trace coins' provenance up to their minting event, thereby highlighting the possibility that users may end up with "tainted" coins upon receiving their coins from a peg-out bridge operation. Similarly, this also highlights the possibility that bridges could become an attraction for money laundering.
To address these considerations, we put forward the concept of ownership preservation for blockchain bridges and we observe that existing multi-sig and BitVM bridges fail to satisfy it. We then present a novel BitVM-based bridge that enables Bitcoin to connect bidirectionally with another DeFi supporting chain in an ownership-preserving and trust-minimized manner. We also observe that our ownership-preserving design is the first Bitcoin bridge to facilitate the transfer of Bitcoin NFTs, Ordinals, across chains, extending in this way their potential value and use cases.
## 2025/2197
* Title: Small-field hash-based SNARGs are less sound than conjectured
* Authors: Giacomo Fenzi, Antonio Sanso
* [Permalink](https://eprint.iacr.org/2025/2197)
* [Download](https://eprint.iacr.org/2025/2197.pdf)
### Abstract
Hash-based succinct non-interactive arguments (SNARGs) are a widely studied and deployed class of proof systems. The security of practical hash-based SNARGs relies on two combinatorial parameters of its underlying linear code $\mathcal{C}$: a distance-preservation error $\varepsilon(\mathcal{C},\delta)$ and the list size $|\Lambda(\mathcal{C}, \delta)|$ (both parametrized by a proximity parameter $\delta$). Optimistically, one might hope that these parameters are bounded all the way to the capacity regime: when the proximity parameter $\delta$ approaches the minimum distance of the code $\delta(\mathcal{C})$. Perhaps too optimistically, several deployed hash-based SNARGs indeed operate in this regime, and initiatives such as the Ethereum Proximity Prize investigate to which extent soundness is preserved in this setting.
We present a minimal toy protocol whose analysis captures most of the complexity of state-of-the-art hash-based SNARGs, and present a generic attack whose success probability depends on the list size $|\Lambda(\mathcal{C}, \delta)|$.
Further, we investigate the common settings when the code $\mathcal{C}$ is an extension code over a field $\mathbb{F}$ of a base code $\mathcal{C}_\mathbb{B}$ over a small base field $\mathbb{B}$. In this setting, we show that classical combinatorial lower bounds on the list-size of the code yields strong attacks that affect the regimes in which hash-based SNARGs operate in practice.
## 2025/2198
* Title: Putting Multi into Multi-Signatures: Tight Security for Multiple Signers
* Authors: Anja Lehmann, Cavit |uzbay
* [Permalink](https://eprint.iacr.org/2025/2198)
* [Download](https://eprint.iacr.org/2025/2198.pdf)
### Abstract
Multi-signatures enable multiple parties to create a joint signature on the same message. Such schemes aggregate several individual signatures and public keys into a short signature and aggregated public key, and verification is performed on these combined values. Interestingly, all existing notions of unforgeability for multi-signatures are designed with a single honest user in mind, overlooking the multi-user setting that multi-signatures are built for. While multi-user security can be bootstrapped from any single-user secure scheme, the straightforward adoption implies a security loss that is linear in the number of signers n. In this work we therefore start the investigation of multi-signatures with tight multi-user security. We show that none of the existing multi-signatures with tight single-user security seems amendable to the multi-user setting, as all their proofs and design choices exploit the fact that there is only a single honest user. Based on this insight, we then propose two new constructions built from scratch with multi-user security in mind: Skewer-NI, a non-interactive and pairing-based scheme, and Skewer-PF, a pairing-free and two-round construction. We prove both schemes tightly secure under the DDH assumption in the ROM. Both schemes also improve the state-of-the-art in another aspect: they support the feature of key aggregation. Skewer-NI is the first non-interactive tightly secure multi-signature with this feature. In the pairing-free two-round setting, Skewer-PF is the first to combine tight multi-user security with key aggregation where the only prior result, due to Bacho and Wagner (CRYPTOrCO25), achieved aggregation but only in the single-user case.
## 2025/2199
* Title: A Formal Security Proof of Masking: Reduction from Relaxed Noisy Leakage to Probing Model without Random Probing and Application to LR Primitive
* Authors: Rei Ueno, Akiko Inoue, Kazuhiko Minematsu, Akira Ito, Naofumi Homma * [Permalink](https://eprint.iacr.org/2025/2199)
* [Download](https://eprint.iacr.org/2025/2199.pdf)
### Abstract
This paper provides an upper bound on the success rate (SR) of side-channel attacks (SCAs) on masked implementations. We present a formal security proof of additive maskingrCoincluding both Boolean and arithmeticrCothrough new reductions from relaxed noisy leakage (RNL) to the probing model. Unlike existing proofs relying on random probing (RP), our proof introduces a novel security notion named leakage energy (LE), which enables a tighter bound. In addition, our proof reveals the necessary and sufficient condition for asymptotic security of additive masking in both the noisy leakage and mutual information frameworks, which includes a resolution to an open problem in TCC 2016. Our claims are validated through numerical evaluations. As an application of our theorems, we propose a binary block-cipher based leakage-resilient primitive based on a variant of $\mathsf{XEX}$, which claims $d$-th order SCA security of arithmetic masking by design, enabling efficient $\mathsf{OCB}$-style authenticated encryption with an implementation cost of $O(d)$.
--- Synchronet 3.21a-Linux NewsLink 1.2