[digest] 2024 Week 34

Liste des GroupesRevenir à s crypt 
Sujet : [digest] 2024 Week 34
De : noreply (at) *nospam* example.invalid (IACR ePrint Archive)
Groupes : sci.crypt
Date : 26. Aug 2024, 03:21:48
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <o-4obpO37luLBwezNNMKJm2mYr7Qs36v@eprint.iacr.org.invalid>
## In this issue

1. [2024/1012] Supersonic OT: Fast Unconditionally Secure ...
2. [2024/1288] KpqClean Ver2: Comprehensive Benchmarking and ...
3. [2024/1289] Improved Lattice Blind Signatures from Recycled Entropy
4. [2024/1290] SoK: Computational and Distributed Differential ...
5. [2024/1291] Raccoon: A Masking-Friendly Signature Proven in the ...
6. [2024/1292] Chosen Ciphertext Security for (Hierarchical) ...
7. [2024/1293] Greyhound: Fast Polynomial Commitments from Lattices
8. [2024/1294] Pre-Constrained Cryptography: Broad Definitions, ...
9. [2024/1295] Identity-Based Encryption from Lattices with More ...
10. [2024/1296] Universal Composable Transaction Serialization with ...
11. [2024/1297] Improved Cryptanalysis of SNOVA
12. [2024/1298] Point (de)compression for elliptic curves over ...
13. [2024/1299] Permissionless Verifiable Information Dispersal ...
14. [2024/1300] SoK: 5 Years of Neural Differential Cryptanalysis
15. [2024/1301] Kalos: Hierarchical-auditable and Human-binding ...
16. [2024/1302] RABAEKS: Revocable Attribute-based Authenticated ...
17. [2024/1303] Efficient Zero-Knowledge Arguments for Paillier ...
18. [2024/1304] Improved Algebraic Attacks on Round-Reduced LowMC ...
19. [2024/1305] Constructions of Efficiently Implementable Boolean ...
20. [2024/1306] Scloud+: a Lightweight LWE-based KEM without ...
21. [2024/1307] On Algebraic Homomorphic Encryption and its ...
22. [2024/1308] LAMA: Leakage-Abuse Attacks Against Microsoft ...
23. [2024/1309] R-STELLAR: A Resilient Synthesizable Signature ...
24. [2024/1310] On the Effects of Neural Network-based Output ...
25. [2024/1311] Dynamic Threshold Key Encapsulation with a ...
26. [2024/1312] Probabilistic Data Structures in the Wild: A ...
27. [2024/1313] A Lattice Attack Against a Family of RSA-like ...
28. [2024/1314] Verifiable Homomorphic Linear Combinations in ...
29. [2024/1315] PulpFHE: Complex Instruction Set Extensions for FHE ...
30. [2024/1316] Generalized Triangular Dynamical System: An ...
31. [2024/1317] MAESTRO: Multi-party AES using Lookup Tables
32. [2024/1318] Patching and Extending the WWL+ Circuit ...
33. [2024/1319] Quantum-safe Signatureless DNSSEC
34. [2024/1320] Post-Quantum DNSSEC over UDP via QNAME-Based ...
35. [2024/1321] ECC’s Achilles’ Heel: Unveiling Weak Keys in ....
36. [2024/1322] Revisiting a Realistic EM Side-Channel Attack on a ...
37. [2024/1323] SoK: Instruction Set Extensions for Cryptographers
38. [2024/1324] CLAASPing ARADI: Automated Analysis of the ARADI ...
39. [2024/1325] Authenticity in the Presence of Leakage using a ...
40. [2024/1326] On the anonymity of one authenticated key agreement ...
41. [2024/1327] Public-Key Anamorphism in (CCA-secure) Public-Key ...
42. [2024/1328] A Note on ARADI and LLAMA
43. [2024/1329] Small Public Exponent Brings More: Improved Partial ...
44. [2024/1330] New Results for Coppersmith's Method from the ...
45. [2024/1331] Practical Small Private Exponent Attacks against RSA

## 2024/1012

* Title: Supersonic OT: Fast Unconditionally Secure Oblivious Transfer
* Authors: Aydin Abadi, Yvo Desmedt
* [Permalink](https://eprint.iacr.org/2024/1012)
* [Download](https://eprint.iacr.org/2024/1012.pdf)

### Abstract

Oblivious Transfer (OT) is a fundamental cryptographic protocol with applications in secure Multi-Party Computation, Federated Learning, and Private Set Intersection. With the advent of quantum computing, it is crucial to develop unconditionally secure core primitives like OT to ensure their continued security in the post-quantum era. Despite over four decades since OT's introduction, the literature has predominantly relied on computational assumptions, except in cases using unconventional methods like noisy channels or a fully trusted party. Introducing “Supersonic OT”, a highly efficient and unconditionally secure OT scheme that avoids public-key-based primitives, we offer an alternative to traditional approaches. Supersonic OT enables a receiver to obtain a response of size O(1). Its simple (yet non-trivial) design facilitates easy security analysis and implementation. The protocol employs a basic secret-sharing scheme, controlled swaps, the one-time pad, and a third-party helper who may be corrupted by a semi-honest adversary. Our implementation and runtime analysis indicate that a single instance of Supersonic OT completes in 0.35 milliseconds, making it up to 2000 times faster than the state-of-the-art base OT.



## 2024/1288

* Title: KpqClean Ver2: Comprehensive Benchmarking and Analysis of KpqC Algorithm Round 2 Submissions
* Authors: Minjoo Sim, Siwoo Eum, Gyeongju Song, Minwoo Lee, Sangwon Kim, Minho Song, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2024/1288)
* [Download](https://eprint.iacr.org/2024/1288.pdf)

### Abstract

From 2022, Korean Post-Quantum Cryptography (KpqC) Competition has been held. Among the Round 1 algorithms of KpqC, eight algorithms were selected in December 2023. To evaluate the algorithms, the performance is critical factor. However, the performance of the algorithms submitted to KpqC was evaluated in different development environments. Consequently, it is difficult to  compare the performance of each algorithm fairly, because the measurements were not conducted in the identical development environments. In this paper, we introduce KpqClean ver2, the successor to the KpqClean project. KpqClean ver2 provides comprehensive benchmark analysis results for all KpqC Round 2 algorithms across various environments (Ryzen, Intel, and aarch64). This framework includes both a ``clean'' implementation and an ``avx2'' implementation of the KpqC Round 2 candidate algorithms. To benchmark the algorithms, we not only removed external library dependencies from each algorithm but also integrated the same source code for common algorithms (such as AES, SHA2, SHAKE, and etc.) to enable more accurate performance comparisons. The framework automatically recognizes the user’s environment, providing easy benchmarking for all users without the need for separate settings. This study also includes memory usage analysis using Valgrind for each algorithm and function usage proportion analysis during the execution of each cryptographic algorithm using Xcode's profiling tool. Finally we show that the practical strength of KpqC algorithms in terms of execution timing and memory usages. This result can be utilized for the understanding of  KpqC finalist in terms of performance.



## 2024/1289

* Title: Improved Lattice Blind Signatures from Recycled Entropy
* Authors: Corentin Jeudy, Olivier Sanders
* [Permalink](https://eprint.iacr.org/2024/1289)
* [Download](https://eprint.iacr.org/2024/1289.pdf)

### Abstract

Blind signatures represent a class of cryptographic primitives enabling privacy-preserving authentication with several applications such as e-cash or e-voting. It is still a very active area of research, in particular in the post-quantum setting where the history of blind signatures has been hectic. Although it started to shift very recently with the introduction of a few lattice-based constructions, all of the latter give up an important characteristic of blind signatures (size, efficiency, or security under well-known assumptions) to achieve the others. In this paper, we propose another design which revisits the link between the two main procedures of blind signatures, namely issuance and showing, demonstrating that we can significantly alleviate the second one by adapting the former. Concretely, we show that we can harmlessly inject excess randomness in the issuance phase, and then recycle the entropy surplus during showing to decrease the complexity of the zero-knowledge proof which constitutes the main component of the signature. This leads to a blind signature scheme with small sizes, low complexity, and that still relies on well-known lattice assumptions.



## 2024/1290

* Title: SoK: Computational and Distributed Differential Privacy for MPC
* Authors: Fredrik Meisingseth, Christian Rechberger
* [Permalink](https://eprint.iacr.org/2024/1290)
* [Download](https://eprint.iacr.org/2024/1290.pdf)

### Abstract

In the last fifteen years, there has been a steady stream of works combining differential privacy with various other cryptographic disciplines, particularly that of multi-party computation, yielding both practical and theoretical unification. As a part of that unification, due to the rich definitional nature of both fields, there have been many proposed definitions of differential privacy adapted to the given use cases and cryptographic tools at hand, resulting in computational and/or distributed versions of differential privacy. In this work, we offer a systemization of such definitions, with a focus on definitions that are both computational and tailored for a multi-party setting. We order the definitions according to the distribution model and computational perspective and propose a viewpoint on when given definitions should be seen as instantiations of the same generalised notion. The ordering highlights a clear, and sometimes strict, hierarchy between the definitions, where utility (accuracy) can be traded for stronger privacy guarantees or lesser trust assumptions. Further, we survey theoretical results relating the definitions to each other and extend some such results. We also discuss the state of well-known open questions and suggest new open problems to study. Finally, we consider aspects of the practical use of the different notions, hopefully giving guidance also to future applied work.



## 2024/1291

* Title: Raccoon: A Masking-Friendly Signature Proven in the Probing Model
* Authors: Rafaël del Pino, Shuichi Katsumata, Thomas Prest, Mélissa Rossi
* [Permalink](https://eprint.iacr.org/2024/1291)
* [Download](https://eprint.iacr.org/2024/1291.pdf)

### Abstract

This paper presents Raccoon, a lattice-based signature scheme submitted to the NIST 2022 call for additional post-quantum signatures. Raccoon has the specificity of always being masked. Concretely, all sensitive intermediate values are shared into 𝑑 parts. The main design rationale of Raccoon is to be easy to mask at high orders, and this dictated most of its design choices, such as the introduction of new algorithmic techniques for sampling small errors. As a result, Raccoon achieves a masking overhead $𝑂(𝑑 \log 𝑑)$ that compares favorably with the overheads $𝑂(𝑑^2 \log  𝑞)$ observed when masking standard lattice signatures. In addition, we formally prove the security of Raccoon in the 𝑡-probing model: an attacker is able to probe $𝑡 ≤ 𝑑 −1$ shares during each execution of the main algorithms (key generation, signing, verification). While for most cryptographic schemes, the black-box 𝑡-probing security can be studied in isolation, in Raccoon this analysis is performed jointly. To that end, a bridge must be made between the black-box game-based EUF-CMA proof and the usual simulation proofs of the ISW model (CRYPTO 2003). We formalize an end-to-end masking proof by deploying the probing EUF-CMA introduced by Barthe et al.(Eurocrypt 2018) and exhibiting the simulators of the non-interference properties (Barthe et al. CCS 2016). The proof is divided into three novel parts:
- a simulation proof in the ISW model that allows to propagate the dependency to a restricted number of inputs and random coins,
- a game-based proof showing that the security of Raccoon with probes can be reduced to an instance of Raccoon with smaller parameters,
- a parameter study to ensure that the smaller instance is secure, using a robust generalization of the Rényi divergence.
While we apply our techniques to Raccoon, we expect that the algorithmic and proof techniques we introduce will be helpful for the design and analysis of future masking-friendly schemes.



## 2024/1292

* Title: Chosen Ciphertext Security for (Hierarchical) Identity-Based Matchmaking Encryption
* Authors: Sohto Chiku, Keisuke Hara, Junji Shikata
* [Permalink](https://eprint.iacr.org/2024/1292)
* [Download](https://eprint.iacr.org/2024/1292.pdf)

### Abstract

Identity-based matchmaking encryption (IB-ME) is an advanced encryption scheme that enables a sender and a receiver to specify each of identity. In general, from the aspect of abilities for adversaries, we have two flavors of security for encryption schemes chosen plaintext attacks (CPA) security and chosen ciphertext attacks (CCA) security. Compared to CPA security, CCA security can capture active adversaries, then it has been recognized as a desirable one.

In this paper, we investigate the CCA security for IB-ME.
Concretely, we provide the following three contributions. (i) A method to obtain a CCA secure IB-ME scheme in the standard model based on our new primitive called hierarchical IB-ME (HIB-ME) along with strong one-time signature. (ii) A construction of HIB-ME based on hierarchical identity-based encryption and hierarchical identity-based signature. (iii) A variant of the first method to get an IB-ME scheme satisfying slightly tweaked CCA security solely based on a CPA secure IB-ME scheme (without strong one-time signature). We believe that this new type of CCA security is a reasonable one for IB-ME.



## 2024/1293

* Title: Greyhound: Fast Polynomial Commitments from Lattices
* Authors: Ngoc Khanh Nguyen, Gregor Seiler
* [Permalink](https://eprint.iacr.org/2024/1293)
* [Download](https://eprint.iacr.org/2024/1293.pdf)

### Abstract

In this paper, we propose Greyhound, the first concretely efficient polynomial commitment scheme from standard lattice assumptions. At the core of our construction lies a simple three-round protocol for proving evaluations for polynomials of bounded degree $N$ with verifier time complexity $O(\sqrt{N})$. By composing it with the LaBRADOR proof system (CRYPTO 2023), we obtain a succinct proof of polynomial evaluation (i.e. polylogarithmic in $N$) that admits a sublinear verifier runtime.

To highlight practicality of Greyhound, we provide implementation details including concrete sizes and runtimes. Notably, for large polynomials of degree at most $N=2^{30}$, the scheme produces evaluation proofs of size $53$KB, which is more than $10^4$ times smaller than the recent lattice-based framework, called SLAP (EUROCRYPT 2024), and around three orders of magnitude smaller than Ligero (CCS 2017) and Brakedown (CRYPTO 2023).



## 2024/1294

* Title: Pre-Constrained Cryptography: Broad Definitions, New Constructions, Unbounded Security
* Authors: Shweta Agrawal, Simran Kumari, Ryo Nishimaki
* [Permalink](https://eprint.iacr.org/2024/1294)
* [Download](https://eprint.iacr.org/2024/1294.pdf)

### Abstract

The recent works of Ananth et al. (ITCS 2022) and Bartusek et al. (Eurocrypt 2023) initiated the study of pre-constrained cryptography which achieves meaningful security even against the system authority. In this work we significantly expand this area by defining several new primitives and providing constructions from simple, standard assumptions as follows.

- Pre-Constrained Encryption. We define a weaker notion of pre-constrained encryption (PCE), as compared to the work of Ananth et al. which nevertheless suffices for all known applications. We then provide constructions for general constraints, satisfying malicious security from a variety of assumptions including DDH, LWE, QR and DCR. Our LWE based construction satisfies unconditional security against malicious authorities. In contrast, the construction by Ananth et al. supporting general constraints must rely (inherently) on strong assumptions like indistinguishability obfuscation.
   
- Pre-Constrained Static Functional Encryption and Input Obfuscation. We provide a new definition for pre-constrained functional encryption in the so-called static setting (PCSFE) where the functions to be embedded in secret keys are specified during the setup phase. We provide constructions for PCSFE supporting general constraints, with security against malicious authorities. As in the case of PCE, our first construction can be instantiated from a variety of assumptions including DDH, LWE, QR and DCR. Our second, LWE based construction satisfies unconditional security against malicious authorities.
  
    We also study succinctness in PCSFE, where the public key is sublinear in the number of function keys. We provide the first construction from LWE in the random oracle model. We additionally provide a heuristic construction in the standard model using lattices together with groups.
 
 - Pre-Constrained Input Obfuscation. We define and provide the first construction of pre-constrained input obfuscation from the same assumptions as those used to instantiate PCSFE.
   
- Pre-Constrained Group Signatures. For pre-constrained group signatures (PCGS), we provide the first construction supporting general constraints, achieving unconditional security against malicious authorities from the LWE assumption. The only other construction by Bartusek et al. supports the restricted set/database membership constraint, and achieves computational security from the DDH assumption (and is therefore quantum insecure).



## 2024/1295

* Title: Identity-Based Encryption from Lattices with More Compactness in the Standard Model
* Authors: Weidan Ji, Zhedong Wang, Haoxiang Jin, Qi Wang, Geng Wang, Dawu Gu
* [Permalink](https://eprint.iacr.org/2024/1295)
* [Download](https://eprint.iacr.org/2024/1295.pdf)

### Abstract

Lattice-based identity-based encryption having both efficiency and provable security in the standard model is currently still a challenging task and has drawn much attention. In this work, we introduce a new IBE construction from NTRU lattices in the standard model, based on the framework proposed by Agrawal, Boneh, and Boyen (EUROCRYPT 2010). Particularly, by introducing the NTRU trapdoor and the RingLWE computational assumption, we remove a crux restriction of the column number and obtain a more compact IBE construction in the standard model. Besides, we provide a concrete implementation and detailed performance results with a comparison of previous works in terms of the security model and the assumption, which demonstrates the advantage of our construction.



## 2024/1296

* Title: Universal Composable Transaction Serialization with Order Fairness
* Authors: Michele Ciampi, Aggelos Kiayias, Yu Shen
* [Permalink](https://eprint.iacr.org/2024/1296)
* [Download](https://eprint.iacr.org/2024/1296.pdf)

### Abstract

Order fairness in the context of distributed ledgers has received recently significant attention due to a range of attacks that exploit the reordering and adaptive injection of transactions (violating what is known as “input causality”). To address such concerns an array of definitions for order fairness has been put forth together with impossibility and feasibility results highlighting the difficulty and multifaceted nature of fairness in transaction serialization. Motivated by this we present a comprehensive modeling of order fairness capitalizing on the universal composition (UC) setting. Our results capture the different flavors of sender order fairness and input causality (which is arguably one of the most critical aspects of ledger transaction processing with respect to serialization attacks) and we parametrically illustrate what are the limits of feasibility for realistic constructions via an impossibility result. Our positive result, a novel distributed ledger protocol utilizing trusted enclaves, complements tightly our impossibility result, hence providing an optimal sender order fairness ledger construction that is also eminently practical.



## 2024/1297

* Title: Improved Cryptanalysis of SNOVA
* Authors: Ward Beullens
* [Permalink](https://eprint.iacr.org/2024/1297)
* [Download](https://eprint.iacr.org/2024/1297.pdf)

### Abstract

SNOVA is a multivariate signature scheme submitted to the NIST project for additional signature schemes by Cho, Ding, Kuan, Li, Tseng, Tseng, and Wang. With small key and signature sizes good performance, SNOVA is one of the more efficient schemes in the competition, which makes SNOVA an important target for cryptanalysis.
   
In this paper, we observe that SNOVA implicitly uses a structured version of the ``whipping'' technique developed for the MAYO signature scheme. We show that the extra structure makes the construction vulnerable to new forgery attacks. Concretely, we formulate new attacks that reduce the security margin of the proposed SNOVA parameter sets by a factor between $2^{8}$ and $2^{39}$. Furthermore, we show that large fractions of public keys are vulnerable to more efficient versions of our attack. For example, for SNOVA-37-17-2, a parameter set targeting NIST's first security level, we show that roughly one out of every $500$ public keys is vulnerable to a universal forgery attack with bit complexity $2^{97}$, and roughly one out of every  $143000$ public keys is even breakable in practice within a few minutes.



## 2024/1298

* Title: Point (de)compression for elliptic curves over highly $2$-adic finite fields
* Authors: Dmitrii Koshelev
* [Permalink](https://eprint.iacr.org/2024/1298)
* [Download](https://eprint.iacr.org/2024/1298.pdf)

### Abstract

This article addresses the issue of efficient and safe (de)compression of $\mathbb{F}_{\!q}$-points on an elliptic curve $E$ over a highly $2$-adic finite field $\mathbb{F}_{\!q}$ of characteristic $5$ or greater. The given issue was overlooked by cryptography experts, probably because, until recently, such fields were not in trend. Therefore, there was no difficulty (with rare exceptions) in finding a square $\mathbb{F}_{\!q}$-root. However, in our days, fields with large $2$-adicities have gained particular popularity in the ZK (zero-knowledge) community, despite the fact that $\sqrt{\cdot} \in \mathbb{F}_{\!q}$ should be computed via more sophisticated square-root algorithms such as (Cipolla-Lehmer-)Müller's one. The article explains why the classical $x$-coordinate (de)compression method based on Müller's algorithm often contains Achilles' heel to successfully perform a novel fault attack, which also fits the definition of a (D)DoS attack. In a nutshell, the trouble stems from the non-deterministic initialization of Müller's algorithm.

Moreover, the article suggests a countermeasure, namely an alternative (still simple) (de)compression method that completely prevents the discovered attack whenever the curve $E/\mathbb{F}_{\!q}$ is of even order. In particular, all twisted Edwards (i.e., Montgomery) curves are relevant. The decompression stage of the new method equally suffers from one square-root extraction in $\mathbb{F}_{\!q}$. But the corresponding quadratic residue is inherently equipped with additional information, providing an opportunity to launch Müller's algorithm immediately from its main deterministic part. In turn, the compression stage of the new method remains (almost) free as well as for the $x$-coordinate method.



## 2024/1299

* Title: Permissionless Verifiable Information Dispersal (Data Availability for Bitcoin Rollups)
* Authors: Ben Fisch, Arthur Lazzaretti, Zeyu Liu, Lei Yang
* [Permalink](https://eprint.iacr.org/2024/1299)
* [Download](https://eprint.iacr.org/2024/1299.pdf)

### Abstract

Rollups are special applications on distributed state machines (aka blockchains) for which the underlying state machine only logs, but does not execute transactions. Rollups have become a popular way to scale applications on Ethereum and there is now growing interest in running rollups on Bitcoin. Rollups scale throughput and reduce transaction costs by using auxiliary machines that have higher throughput and lower cost of executing transactions than the underlying blockchain. State updates are periodically posted to the underlying blockchain and either verified directly through succinct cryptographic proofs (zk rollups) or can be challenged for a defined period of time in a verifiable way by third parties (optimistic rollups).
  
However, once computation is removed as a bottleneck, communication quickly becomes the new bottleneck. The critical service the underlying blockchain provides in addition to verification is data availability: that necessary data can always be recovered upon request. While broadcasting transaction data is one way to ensure this, it requires communication blowup linear in the number of participating nodes. Verifiable information dispersal (VID) systems achieve sublinear blowup in the same participation model and the same security assumptions as Ethereum, where all nodes have a strong public-key identity. It was not known how to do so in the same permissionless model as Bitcoin, where participants are unauthenticated and participation is dynamic.
   
We construct a VID system that is secure under the same model as Bitcoin, with one minimal additional requirement on the existence of reliable participants.  Our system uses a state machine replication (SMR) protocol (e.g., Bitcoin) as a black box, and is therefore backward compatible. We implemented the system on top of Bitcoin core with the Regression Test Network (regtest), and our analysis shows that it reduces communication costs by more than 1,000x and latency by more than 10x.



## 2024/1300

* Title: SoK: 5 Years of Neural Differential Cryptanalysis
* Authors: David Gerault, Anna Hambitzer, Moritz Huppert, Stjepan Picek
* [Permalink](https://eprint.iacr.org/2024/1300)
* [Download](https://eprint.iacr.org/2024/1300.pdf)

### Abstract

At CRYPTO 2019, A. Gohr introduced Neural Differential Cryptanalysis by applying deep learning to modern block cipher cryptanalysis. Surprisingly, the resulting neural differential distinguishers enabled a new state-of-the-art key recovery complexity for 11 rounds of SPECK32. As of May 2024, according to Google Scholar, Gohr’s article has been cited 178 times. The wide variety of targets, techniques, settings, and evaluation methodologies that appear in these follow-up works grants a careful systematization of knowledge, which we provide in this paper. More specifically, we propose a taxonomy of these 178 publications and focus on the 50 that deal with differential neural distinguishers to systematically review and compare them. We then discuss two challenges for the field, namely comparability of neural distinguishers and
scaling.



## 2024/1301

* Title: Kalos: Hierarchical-auditable and Human-binding Authentication Scheme for Clinical Trial
* Authors: Chang Chen, Zelong Wu, Guoyu Yang, Qi Chen, Wei Wang, Jin Li
* [Permalink](https://eprint.iacr.org/2024/1301)
* [Download](https://eprint.iacr.org/2024/1301.pdf)

### Abstract

Clinical trials are crucial in the development of new medical treatment methods. To ensure the correctness of clinical trial results, medical institutes need to collect and process large volumes of participant data, which has prompted research on privacy preservation and data reliability. However, existing solutions struggle to resolve the trade-off between them due to the trust gap between the physical and digital worlds, limiting their practicality. To tackle the issues above, we present Kalos, a novel authentication scheme for clinical trials. Kalos leverages diversified cryptographic tools, such as card-based anonymous credential and zero-knowledge proof to achieve authentication with visual verification and selective disclosure of attributes. It has properties such as unforgeability, blindness, privacy preservation, and human-binding that support hierarchical auditability and data de-duplication to enhance the reliability of clinical trials. We then provide the security and performance analysis of Kalos to show its potential to be deployed in the medical consumer electronics scenario. The computational cost of the smartcard is irrespective of the number of certified attributes, and the total computational cost of Kalos is within tens of milliseconds with the commonly used number of attributes.



## 2024/1302

* Title: RABAEKS: Revocable Attribute-based Authenticated Encrypted Search over Lattice for Multi-receiver Cloud Storage
* Authors: Yibo Cao, Shiyuan Xu, Xiu-Bo Chen, Siu-Ming Yiu
* [Permalink](https://eprint.iacr.org/2024/1302)
* [Download](https://eprint.iacr.org/2024/1302.pdf)

### Abstract

With the widespread development of cloud storage, searching over the encrypted data (without decryption) has become a crucial issue. Public key authenticated encryption with keyword search (PAEKS) retrieves encrypted data, and resists inside keyword guessing attacks (IKGAs). Most PAEKS schemes cannot support access control in multi-receiver models. To address this concern, attribute-based authenticated encryption with keyword search (ABAEKS) has been studied.. However, the access privilege for the ciphertext may change, and the conventional cryptographic primitives are not resistant to quantum computing attacks, which exhibits a limited applicability and poor security for cloud storage.. In this paper, we propose RABAEKS, the first post-quantum revocable attribute-based authenticated encrypted search scheme for multi-receiver cloud storage. Our design enables cloud server enforces the access control of data receivers in the search process. For practical consideration, we further introduce a revocation mechanism of data receivers, which makes the access control more dynamic. We then define and rigorously analyze the security our scheme. Through the performance evaluations and comparisons, our computational overhead of ciphertext generation, trapdoor generation and search algorithm are at least 20×, 1.67× and 1897× faster than prior arts, respectively, which is practical for cloud storage.



## 2024/1303

* Title: Efficient Zero-Knowledge Arguments for Paillier Cryptosystem
* Authors: Borui GONG, Wang Fat Lau, Man Ho Au, Rupeng Yang, Haiyang Xue, Lichun Li
* [Permalink](https://eprint.iacr.org/2024/1303)
* [Download](https://eprint.iacr.org/2024/1303.pdf)

### Abstract

We present an efficient zero-knowledge argument of knowledge system customized for the Paillier cryptosystem. Our system enjoys sublinear proof size, low verification cost, and acceptable proof generation effort, while also supporting batch proof generation/verification. Existing works specialized for Paillier cryptosystem feature linear proof size and verification time. Using existing sublinear argument systems for generic statements (e.g., zk-SNARK) results in unaffordable proof generation cost since it involves translating the relations to be proven into an inhibitive large Boolean or arithmetic circuit over a prime order field.  Our system does not suffer from these limitations.

The core of our argument systems is a constraint system defined over the ring of residue classes modulo a composite number, together with novel techniques tailored for arguing binary values  in this setting. We then adapt the approach from  Bootle et al. (EUROCRYPT 2016) to compile the constraint system into a sublinear argument system. Our constraint system is generic and can be used to express typical relations  in Paillier cryptosystems including range proof, correctness proof, relationships between bits of plaintext, relationships of plaintexts among multiple ciphertexts, and more. Our argument supports batch proof generation and verification, with the amortized cost outperforming state-of-the-art protocol specialized for Paillier when the number of Paillier ciphertext is in the order of hundreds.

We report an end-to-end prototype and conduct comprehensive experiments across multiple scenarios. Scenario 1 is Paillier with packing. When we pack 25.6K bits into 400 ciphertexts, a proof that all these ciphertexts are correctly computed is 17 times smaller and is 3 times faster to verify compared with the naive implementation: using  25.6K OR-proofs without packing. Furthermore, we can prove additional statements almost for free, e.g., one can prove that the sum of a subset of the witness bits is less than a threshold t. Another scenario is  range proof. To prove that each plaintext in  200 Paillier ciphertexts is of size 256 bits, our proof size is 10 times smaller than the state-of-the-art. Our analysis suggests that our system is asymptotically more efficient than existing protocols, and is highly suitable for scenarios involving a large number (more than 100) of Paillier ciphertexts, which is often the case for data analytics applications.



## 2024/1304

* Title: Improved Algebraic Attacks on Round-Reduced LowMC with Single-Data Complexity
* Authors: Xingwei Ren, Yongqiang Li, Mingsheng Wang
* [Permalink](https://eprint.iacr.org/2024/1304)
* [Download](https://eprint.iacr.org/2024/1304.pdf)

### Abstract

Recently, Picnic3 has introduced several alternative LowMC instances, which prompts the cryptanalysis competition for LowMC. In this paper, we provide new solutions to the competition with full S-box layers under single-data complexity. First, we present a new guess-and-determine attack framework that achieves the best trade-off in complexity, while effectively enhancing two algorithms applicable to 2-round LowMC cryptanalysis. Next, we present a new meet-in-the-middle attack framework for 2-/3-round LowMC, which can gradually reduce the number of variables and narrow down the range of candidate keys in stages. As a result, our 3-stage MITM attacks have both lower time complexity and memory complexity than the best previous 2-round attacks proposed by Banik et al. at ASIACRYPT 2021, with memory reduced drastically by a factor of $ 2^{29.7} \sim 2^{70.4} $.



## 2024/1305

* Title: Constructions of Efficiently Implementable Boolean functions Possessing High Nonlinearity and Good Resistance to Algebraic Attacks
* Authors: Claude Carlet, Palash Sarkar
* [Permalink](https://eprint.iacr.org/2024/1305)
* [Download](https://eprint.iacr.org/2024/1305.pdf)

### Abstract

We describe two new classes of functions which provide the presently best known trade-offs between low computational complexity, nonlinearity and (fast) algebraic immunity. The nonlinearity and (fast) algebraic immunity of the new functions substantially improve upon those properties of all previously known efficiently implementable functions. Appropriately chosen functions from the two new classes provide excellent solutions to the problem of designing filtering functions for use in the nonlinear filter model of stream ciphers, or in any other stream ciphers using Boolean functions for ensuring confusion. In particular, for $n\leq 20$, we show that there are functions in our first family whose implementation efficiences are significantly lower than all previously known functions achieving a comparable combination of nonlinearity and (fast) algebraic immunity. Given positive integers $\ell$ and $\delta$, it is possible to choose a function from our second family whose linear bias is provably at most $2^{-\ell}$, fast algebraic immunity is at least $\delta$ (based on conjecture which is well supported by experimental results), and which can be implemented in time and space which is linear in $\ell$ and $\delta$. Further, the functions in our second family are built using homomorphic friendly operations, making these functions well suited for the application of transciphering.



## 2024/1306

* Title: Scloud+: a Lightweight LWE-based KEM without Ring/Module Structure
* Authors: Anyu Wang, Zhongxiang Zheng, Chunhuan Zhao, Zhiyuan Qiu, Guang Zeng, Xiaoyun Wang
* [Permalink](https://eprint.iacr.org/2024/1306)
* [Download](https://eprint.iacr.org/2024/1306.pdf)

### Abstract

We propose Scloud+, a lattice-based key encapsulation mechanism (KEM) scheme.
The design of Scloud+ is informed by the following two aspects.
Firstly, Scloud+ is based on the hardness of algebraic-structure-free lattice problems, which avoids potential attacks brought by the algebraic structures.
Secondly, Scloud+ provides sets of light weight parameters, which greatly reduce the complexity of computation and communication complexity while maintaining the required level of security.



## 2024/1307

* Title: On Algebraic Homomorphic Encryption and its Applications to Doubly-Efficient PIR
* Authors: Hiroki Okada, Rachel Player, Simon Pohmann, Christian Weinert
* [Permalink](https://eprint.iacr.org/2024/1307)
* [Download](https://eprint.iacr.org/2024/1307.pdf)

### Abstract

The Doubly-Efficient Private Information Retrieval (DEPIR) protocol of Lin, Mook, and Wichs (STOC'23) relies on a Homomorphic Encryption (HE) scheme that is algebraic, i.e., whose ciphertext space has a ring structure that matches the homomorphic operations. While early HE schemes had this property, modern schemes introduced techniques to manage noise growth. This made the resulting schemes much more efficient, but also destroyed the algebraic property. In this work, we study algebraic HE with the goal of improving its performance and thereby also the performance of DEPIR

We first prove a lower bound of $2^{\Omega(2^d)}$ for the ciphertext ring size of algebraic HE schemes that can evaluate a circuit of multiplicative depth $d$, thus demonstrating a gap between optimal algebraic HE and the existing schemes, which have a ciphertext ring size of $2^{O(2^{2d})}$. As we are unable to bridge this gap directly, we instead slightly relax the notion of being algebraic. This allows us to construct a practically more efficient relaxed-algebraic HE scheme. We then show that this also leads to a more efficient instantiation and implementation of DEPIR. We experimentally demonstrate run-time improvements of more than 4x and reduce memory queries by more than 8x compared to prior work.

Notably, our relaxed-algebraic HE scheme relies on a new variant of the Ring Learning with Errors (RLWE) problem that we call $\{0, 1\}$-CRT RLWE. We give a formal security reduction to standard RLWE, and estimate its concrete security. Both the $\{0, 1\}$-CRT RLWE problem and the techniques used for the reduction may be of independent interest.



## 2024/1308

* Title: LAMA: Leakage-Abuse Attacks Against Microsoft Always Encrypted
* Authors: Ryan Seah, Daren Khu, Alexander Hoover, Ruth Ng
* [Permalink](https://eprint.iacr.org/2024/1308)
* [Download](https://eprint.iacr.org/2024/1308.pdf)

### Abstract

Always Encrypted (AE) is a Microsoft SQL Server feature that allows clients to encrypt sensitive data inside client applications and ensures that the sensitive data is hidden from untrusted servers and database administrators. AE offers two column-encryption options: deterministic encryption (DET) and randomized encryption (RND). In this paper, we explore the security implications of using AE with both DET and
RND encryption modes by running Leakage Abuse Attacks (LAAs) against the system. We demonstrate how an adversary could extract the necessary data to run a frequency analysis LAA against DET-encrypted columns and an LAA for Order-Revealing Encryption against RND-encrypted columns. We run our attacks using real-world datasets encrypted in a full-scale AE instancer and demonstrate that a snooping server can recover over 95\% of the rows in 8 out of 15 DET-encrypted columns, and 10 out of 15 RND-encrypted columns.



## 2024/1309

* Title: R-STELLAR: A Resilient Synthesizable Signature Attenuation SCA Protection on AES-256 with built-in Attack-on-Countermeasure Detection
* Authors: Archisman Ghosh, Dong-Hyun Seo, Debayan Das, Santosh Ghosh, Shreyas Sen
* [Permalink](https://eprint.iacr.org/2024/1309)
* [Download](https://eprint.iacr.org/2024/1309.pdf)

### Abstract

Side-channel attacks (SCAs) remain a significant threat to the security of cryptographic systems in modern embedded devices. Even mathematically secure cryptographic algorithms, when implemented in hardware, inadvertently leak information through physical side-channel signatures such as power consumption, electromagnetic (EM) radiation, light emissions, and acoustic emanations. Exploiting these side channels significantly reduces the attacker’s search space.
In recent years, physical countermeasures have significantly increased the minimum traces-to-disclosure (MTD) to 1 billion. Among them, signature attenuation is the first method to achieve this mark. Signature attenuation often relies on analog techniques, and digital signature attenuation reduces MTD to 20 million, requiring additional methods for high resilience. We focus on improving the digital signature attenuation by an order of magnitude (MTD 200M).



## 2024/1310

* Title: On the Effects of Neural Network-based Output Prediction Attacks on the Design of Symmetric-key Ciphers
* Authors: Hayato Watanabe, Ryoma Ito, Toshihiro Ohigashi
* [Permalink](https://eprint.iacr.org/2024/1310)
* [Download](https://eprint.iacr.org/2024/1310.pdf)

### Abstract

Proving resistance to conventional attacks, e.g., differential, linear, and integral attacks, is essential for designing a secure symmetric-key cipher. Recent advances in automatic search and deep learning-based methods have made this time-consuming task relatively easy, yet concerns persist over expertise requirements and potential oversights. To overcome these concerns, Kimura et al. proposed neural network-based output prediction (NN) attacks, offering simplicity, generality, and reduced coding mistakes. NN attacks could be helpful for designing secure symmetric-key ciphers, especially the S-box-based block ciphers. Inspired by their work, we first apply NN attacks to Simon, one of the AND-Rotation-XOR-based block ciphers, and identify structures susceptible to NN attacks and the vulnerabilities detected thereby. Next, we take a closer look at the vulnerable structures. The most vulnerable structure has the lowest diffusion property compared to others. This fact implies that NN attacks may detect such a property. We then focus on a biased event of the core function in vulnerable Simon-like ciphers and build effective linear approximations caused by such an event. Finally, we use these linear approximations to reveal that the vulnerable structures are more susceptible to a linear key recovery attack than the original one. We conclude that our analysis can be a solid step toward making NN attacks a helpful tool for designing a secure symmetric-key cipher.



## 2024/1311

* Title: Dynamic Threshold Key Encapsulation with a Transparent Setup
* Authors: Joon Sik Kim, Kwangsu Lee, Jong Hwan Park, Hyoseung Kim
* [Permalink](https://eprint.iacr.org/2024/1311)
* [Download](https://eprint.iacr.org/2024/1311.pdf)

### Abstract

A threshold key encapsulation mechanism (TKEM) facilitates the secure distribution of session keys among multiple participants, allowing key recovery through a threshold number of shares. TKEM has gained significant attention, especially for decentralized systems, including blockchains. However, existing constructions often rely on trusted setups, which pose security risks such as a single point of failure, and are limited by fixed participant numbers and thresholds. To overcome this, we propose a dynamic TKEM with a transparent setup, allowing for a flexible selection of recipients and thresholds without relying on trusted third parties in the setup phase. In addition, our construction does not rely on pairing operations. We prove the security of our TKEM under the decisional Diffie-Hellman assumption, ensuring selective chosen-ciphertext security and decapsulation consistency. Our proof-of-concept implementation highlights the practicality and efficiency of this approach, advancing the field of threshold cryptography.



## 2024/1312

* Title: Probabilistic Data Structures in the Wild: A Security Analysis of Redis
* Authors: Mia Filić, Jonas Hofmann, Sam A. Markelon, Kenneth G. Paterson, Anupama Unnikrishnan
* [Permalink](https://eprint.iacr.org/2024/1312)
* [Download](https://eprint.iacr.org/2024/1312.pdf)

### Abstract

Redis (Remote Dictionary Server) is a general purpose, in-memory database that supports a rich array of functionality, including various Probabilistic Data Structures (PDS), such as Bloom filters, Cuckoo filters, as well as cardinality and frequency estimators.
These PDS typically perform well in the average case. However, given that Redis is intended to be used across a diverse array of applications, it is crucial to evaluate how these PDS perform under worst-case scenarios, i.e., when faced with adversarial inputs. We offer a comprehensive analysis to address this question.
We begin by carefully documenting the different PDS implementations in Redis, explaining how they deviate from those PDS as described in the literature.
Then we show that these deviations enable a total of 10 novel attacks that are more severe than the corresponding attacks for generic versions of the PDS.
We highlight the critical role of Redis' decision to use non-cryptographic hash functions in the severity of these attacks.
We conclude by discussing countermeasures to the attacks, or explaining why, in some cases, countermeasures are not possible.



## 2024/1313

* Title: A Lattice Attack Against a Family of RSA-like Cryptosystems
* Authors: George Teseleanu
* [Permalink](https://eprint.iacr.org/2024/1313)
* [Download](https://eprint.iacr.org/2024/1313.pdf)

### Abstract

Let $N=pq$ be the product of two balanced prime numbers $p$ and $q$. In 2002, Elkamchouchi, Elshenawy, and Shaban introduced an interesting RSA-like cryptosystem that, unlike the classical RSA key equation $ed - k (p-1)(q-1) = 1$, uses the key equation $ed - k (p^2-1)(q^2-1) = 1$. The scheme was further extended by Cotan and Te\c seleanu to a variant that uses the key equation $ed - k (p^n-1)(q^n-1) = 1$, where $n \geq 1$. Furthermore, they provide a continued fractions attack that recovers the secret key $d$ if $d < N^{0.25n}$. In this paper we improve this bound using a lattice based method. Moreover, our method also leads to the factorisation of the modulus $N$, while the continued fractions one does not (except for $n=1,2,3,4$).



## 2024/1314

* Title: Verifiable Homomorphic Linear Combinations in Multi-Instance Time-Lock Puzzles
* Authors: Aydin Abadi
* [Permalink](https://eprint.iacr.org/2024/1314)
* [Download](https://eprint.iacr.org/2024/1314.pdf)

### Abstract

Time-Lock Puzzles (TLPs) have been developed to securely transmit sensitive information into the future without relying on a trusted third party. Multi-instance TLP is a scalable variant of TLP that enables a server to efficiently find solutions to different puzzles provided by a client at once. Nevertheless, existing multi-instance TLPs lack support for (verifiable) homomorphic computation. To address this limitation, we introduce the "Multi-Instance partially Homomorphic TLP" (MH-TLP), a multi-instance TLP supporting efficient verifiable homomorphic linear combinations of puzzles belonging to a client. It ensures anyone can verify the correctness of computations and solutions. Building on MH-TLP, we further propose the "Multi-instance Multi-client verifiable partially Homomorphic TLP" (MMH-TLP). It not only supports all the features of MH-TLP but also allows for verifiable homomorphic linear combinations of puzzles from different clients. Our schemes refrain from using asymmetric-key cryptography for verification and, unlike most homomorphic TLPs, do not require a trusted third party. A comprehensive cost analysis demonstrates that our schemes scale linearly with the number of clients and puzzles.



## 2024/1315

* Title: PulpFHE: Complex Instruction Set Extensions for FHE Processors
* Authors: Omar Ahmed, Nektarios Georgios Tsoutsos
* [Permalink](https://eprint.iacr.org/2024/1315)
* [Download](https://eprint.iacr.org/2024/1315.pdf)

### Abstract

The proliferation of attacks to cloud computing, coupled with the vast amounts of data outsourced to online services, continues to raise major concerns about the privacy for end users. Traditional cryptography can help secure data transmission and storage on cloud servers, but falls short when the already encrypted data needs to be processed by the cloud provider. An emerging solution to this challenge is fully homomorphic encryption (FHE), which enables computations directly on encrypted data, and recent works have focused on developing new processor designs tailored for native processing of FHE data. In this work, we introduce PulpFHE, an optimized instruction set extension tailored for the next generation of FHE processors. Our proposed FHE instructions offer native support for non-linear operations on encrypted data, and enable significantly faster homomorphic computations for a broad range of realistic applications.



## 2024/1316

* Title: Generalized Triangular Dynamical System: An Algebraic System for Constructing Cryptographic Permutations over Finite Fields
* Authors: Arnab Roy, Matthias Johann Steiner
* [Permalink](https://eprint.iacr.org/2024/1316)
* [Download](https://eprint.iacr.org/2024/1316.pdf)

### Abstract

In recent years a new class of symmetric-key primitives over $\mathbb{F}_p$ that are essential to Multi-Party Computation and Zero-Knowledge Proofs based protocols has emerged. Towards improving the efficiency of such primitives, a number of new block ciphers and hash functions over $\mathbb{F}_p$ were proposed. These new primitives also showed that following alternative design strategies to the classical Substitution-Permutation Network (SPN) and Feistel Networks leads to more efficient cipher and hash function designs over $\mathbb{F}_p$ specifically for large odd primes $p$.
In view of these efforts, in this work we build an \emph{algebraic framework} that allows the systematic exploration of viable and efficient design strategies for constructing symmetric-key (iterative) permutations over $\mathbb{F}_p$. We first identify iterative polynomial dynamical systems over finite fields as the central building block of almost all block cipher design strategies. We propose a generalized triangular polynomial dynamical system (GTDS), and based on the GTDS we provide a generic definition of an iterative (keyed) permutation over $\mathbb{F}_p^n$.
Our GTDS-based generic definition is able to describe the three most well-known design strategies, namely SPNs, Feistel networks (FN) and Lai--Massey (LM).. Consequently, the block ciphers that are constructed following these design strategies can also be instantiated from our generic definition. Moreover, we find that the recently proposed \texttt{Griffin} design, which neither follows the Feistel nor the SPN design, can be described using the generic GTDS-based definition. We also show that a new generalized Lai--Massey construction can be instantiated from the GTDS-based definition. The latter results confirm that our GTDS-based definition is able to instantiate cryptographic permutations that are beyond SPN, FN and LM based.
We further provide generic (security) analysis of the GTDS including an upper bound on the differential uniformity and the correlation.



## 2024/1317

* Title: MAESTRO: Multi-party AES using Lookup Tables
* Authors: Hiraku Morita, Erik Pohle, Kunihiko Sadakane, Peter Scholl, Kazunari Tozawa, Daniel Tschudi
* [Permalink](https://eprint.iacr.org/2024/1317)
* [Download](https://eprint.iacr.org/2024/1317.pdf)

### Abstract

Secure multi-party computation (MPC) enables multiple distrusting parties to jointly compute a function while keeping their inputs private. Computing the AES block cipher in MPC, where the key and/or the input are secret-shared among the parties is important for various applications, particularly threshold cryptography.

In this work, we propose a family of dedicated, high-performance MPC protocols to compute the non-linear S-box part of AES in the honest majority setting. Our protocols come in both semi-honest and maliciously secure variants. The core technique is a combination of lookup table protocols based on random one-hot vectors and the decomposition of finite field inversion in $GF(2^8)$ into multiplications and inversion in the smaller field $GF(2^4)$, taking inspiration from ideas used for hardware implementations of AES. We also apply and improve the analysis of a batch verification technique for checking inner products with logarithmic communication. This allows us to obtain malicious security with almost no communication overhead, and we use it to obtain new, secure table lookup protocols with only $O(\sqrt{N})$ communication for a table of size $N$, which may be useful in other applications.

Our protocols have different trade-offs, such as having a similar round complexity as previous state-of-the-art but $37\%$ lower bandwidth costs, or having $27\%$ fewer rounds and $16\%$ lower bandwidth costs. An experimental evaluation in various network conditions using three party replicated secret sharing shows improvements in throughput between $23\%$ and $27\%$ in the semi-honest setting. For malicious security, we improve throughput by $46\%$ and $270\%$ in LAN and by up to $453\%$ in WAN due to a new multiplication verification protocol.



## 2024/1318

* Title: Patching and Extending the WWL+ Circuit Bootstrapping Method to FFT Domains
* Authors: Jincheol Ha, Jooyoung Lee
* [Permalink](https://eprint.iacr.org/2024/1318)
* [Download](https://eprint.iacr.org/2024/1318.pdf)

### Abstract

TFHE is a homomorphic encryption scheme supporting fast bootstrapping.
There are two kinds of bootstrapping in TFHE: programmable bootstrapping (also known as gate bootstrapping) and circuit bootstrapping.
Circuit bootstrapping offers more functionality than programmable bootstrapping, but requires heavier computational cost and larger evaluation key size.
A recent work by Wang et al. improving circuit bootstrapping using homomorphic trace evaluation seems to mitigate its heavy cost, while we observe some flaws in their error analysis.

In this paper, we patch the circuit bootstrapping method proposed by Wang et al. with correct error analysis and extend the ciphertext modulus from a prime modulus to a power-of-two modulus, enabling FFT-based implementation of our patched method.
In addition, we propose a high precision WWL+ method by adopting GLWE keyswitching, improving the circuit bootstrapping time (resp. key size) of WoP-PBS proposed by Bergerat et al. by factors from $3.26$ to $7.22$ (resp. $2.39$ to $2.63$).
We also patch the parameter selection used in the AES evaluation by the WWL+ method, obtaining $26.301$s for a single AES evaluation in a single thread.



## 2024/1319

* Title: Quantum-safe Signatureless DNSSEC
* Authors: Aditya Singh Rawat, Mahabir Prasad Jhanwar
* [Permalink](https://eprint.iacr.org/2024/1319)
* [Download](https://eprint.iacr.org/2024/1319.pdf)

### Abstract

We present $\mathsf{SL\text{-}DNSSEC}$: a backward-compatible protocol that leverages a quantum-safe KEM and a MAC to perform signature-less $\mathsf{(SL)}$ DNSSEC validations in a single UDP query/response style. Our experiments targeting NIST level I security for QTYPE A query resolution show that $\mathsf{SL\text{-}DNSSEC}$ is practically equivalent to the presently deployed RSA-2048 in terms of bandwidth usage and resolution speeds. Compared to post-quantum signatures, $\mathsf{SL\text{-}DNSSEC}$ reduces bandwidth consumption and resolution times by up to $95\%$ and $60\%$, respectively. Moreover, with response size $<$ query size $\leq 1232$ bytes, $\mathsf{SL\text{-}DNSSEC}$ obviates the long-standing issues of IP fragmentation, TCP re-transmits and DDoS amplification attacks.



## 2024/1320

* Title: Post-Quantum DNSSEC over UDP via QNAME-Based Fragmentation
* Authors: Aditya Singh Rawat, Mahabir Prasad Jhanwar
* [Permalink](https://eprint.iacr.org/2024/1320)
* [Download](https://eprint.iacr.org/2024/1320.pdf)

### Abstract

In a typical network, a DNS(SEC) message over 1232 bytes would either be fragmented into several UDP/IP packets or require a re-transmit over TCP. Unfortunately, IP fragmentation is considered unreliable and a non-trivial number of servers do not support TCP.

  We present $\texttt{QNAME}$-Based Fragmentation ($\mathsf{QBF}$): a DNS layer fragmentation scheme that fragments/re-assembles large post-quantum DNS(SEC) messages over UDP in just 1 round-trip while using only standard DNS records. Our experiments show that DNSSEC over $\mathsf{QBF}$, with either Falcon-512, Dilithium-2 or SPHINCS$^{+}$ as the zone signing algorithm, is practically as fast as the currently deployed ECDSA-P256 and RSA-2048 setups in resolving $\texttt{QTYPE}$ $\texttt{A}$ queries.



## 2024/1321

* Title: ECC’s Achilles’ Heel: Unveiling Weak Keys in Standardized Curves
* Authors: Enrico Talotti, Matteo Paier, Marino Miculan
* [Permalink](https://eprint.iacr.org/2024/1321)
* [Download](https://eprint.iacr.org/2024/1321.pdf)

### Abstract

The strength of Elliptic curve cryptography (ECC) relies on curve choice. This work analyzes weak keys in standardized curves, i.e., private keys within small subgroups of the auxiliary group $\mathbb{Z}^*_p$. We quantify weak
key prevalence across standardized curves, revealing a potential vulnerability due to numerous small divisors in auxiliary group orders. To address this, we leverage the implicit "baby-steps giant-steps algorithm", which transforms the complex elliptic curve discrete logarithm problem into a simpler problem within $\mathbb{Z}^*_p$. This enables efficient detection of weak keys in small-order subgroups.
Our findings highlight the importance of rigorous key testing in applications using standardized ECC. While random weak keys are unlikely, malicious actors could exploit this by manipulating key generation libraries. To this end, we show how users can assess their private key vulnerabilities and mitigate risks by eliminating weak keys. Hence, this work contributes to improved ECC security through proactive key management practices.



## 2024/1322

* Title: Revisiting a Realistic EM Side-Channel Attack on a Complex Modern SoC
* Authors: Debao Wang, Yiwen Gao, Yongbin Zhou, Xian Huang
* [Permalink](https://eprint.iacr.org/2024/1322)
* [Download](https://eprint.iacr.org/2024/1322.pdf)

### Abstract

Side-channel analysis on complex SoC devices with high-frequency microprocessors and multitasking operating systems presents significant challenges in practice due to the high costs of trace acquisition and analysis, generally involving tens of thousands to millions of traces. This work uses a cryptographic execution process on a Broadcom 2837 SoC as a case study to explore ways to reduce costs in electromagnetic side-channel analysis. In the data acquisition phase, we propose an efficient electromagnetic probe positioning strategy that does not require additional tool assistance, significantly accelerating the collection of effective electromagnetic traces. In the side-channel analysis phase, we investigate the combined use of preprocessing techniques, where the optimal preprocessing approach successfully reduces the number of required electromagnetic traces by 12 times, significantly improving the success rate of attacks. Additionally, we implement profiling attacks on such devices, including traditional template attacks, MLP-based, and CNN-based side-channel analysis, demonstrating that even minimal modeling costs can yield excellent analysis performance. Our study confirms the feasibility of low-cost side-channel analysis on complex SoCs and indicates that the sensitive applications running on these devices still require protection.



## 2024/1323

* Title: SoK: Instruction Set Extensions for Cryptographers
* Authors: Hao Cheng, Johann Großschädl, Ben Marshall, Daniel Page, Markku-Juhani O. Saarinen
* [Permalink](https://eprint.iacr.org/2024/1323)
* [Download](https://eprint.iacr.org/2024/1323.pdf)

### Abstract

Framed within the general context of cyber-security, standard cryptographic constructions often represent an enabling technology for associated solutions.  Alongside or in combination with their design, therefore, the implementation of such constructions is an important challenge: beyond delivering artefacts that are usable in practice, implementation can impact many quality metrics (such as efficiency and security) which determine fitness-for-purpose. A rich design space of implementation techniques can be drawn on in order to address this challenge, but threat- and opportunity-driven innovation based on clear understanding and empirical evidence remains vital.

In at least some use-cases, software-based implementation of cryptography is important, e.g., because it delivers an attractive trade off or is mandated for some reason. Such an implementation is heavily influenced both by 1) the Instruction Set Architecture (ISA) it is expressed using, and 2) the micro-architecture it is executed using. For example, the extent to which a general-purpose ISA can support more domain-specific requirements of a cryptographic construction will influence how the latter is mapped to the former (i.e., which implementation techniques are viable) and behavioural properties of doing so (e.g., the execution latency stemming from use of a given implementation technique).

This paper attempts to systematise the topic of cryptographic Instruction Set Extensions (ISEs), which represent an approach to provision of a platform where such support is more explicit and extensive. At a high level, the goal is to improve understanding of what is an extensive and somewhat inter-disciplinary body of literature (e.g., spanning academia and industry, hardware and software, as well as cryptographic and non-cryptographic publication venues). We argue that doing so will help to maximise the quality of subsequent work on this and associated topics.



## 2024/1324

* Title: CLAASPing ARADI: Automated Analysis of the ARADI Block Cipher
* Authors: Emanuele Bellini, Mattia Formenti, David Gérault, Juan Grados, Anna Hambitzer, Yun Ju Huang, Paul Huynh, Mohamed Rachidi, Raghvendra Rohit, Sharwan K. Tiwari
* [Permalink](https://eprint.iacr.org/2024/1324)
* [Download](https://eprint.iacr.org/2024/1324.pdf)

### Abstract

In early August 2024, three NSA researchers -- Patricia Greene, Mark Motley, and Bryan Weeks -- published the technical specifications for a new low-latency block cipher, ARADI, along with its corresponding authenticated encryption mode, LLAMA, which is specifically designed for memory encryption applications. Their manuscript offered minimal security analysis of the design, only briefly discussing the differential, linear and algebraic properties of cipher's underlying components. In this work, we present a set of distinguishers for the round reduced ARADI block cipher, discovered using the automated cryptanalysis tool CLAASP. More precisely, using CLAASP, we evaluate the resistance of ARADI against avalanche, statistical and continuous diffusion tests, differential and linear distinguishers, impossible differentials, algebraic attacks, and neural distinguishers.
Accordingly, we give distinguishers that reach up to 9 out of 16 rounds of ARADI. We hope these preliminary findings will encourage further in-depth cryptanalysis of the cipher to enhance confidence in its security.



## 2024/1325

* Title: Authenticity in the Presence of Leakage using a Forkcipher
* Authors: Francesco Berti, François-Xavier Standaert, Itamar Levi
* [Permalink](https://eprint.iacr.org/2024/1325)
* [Download](https://eprint.iacr.org/2024/1325.pdf)

### Abstract

Robust message authentication codes (MACs) and authenticated encryption (AE) schemes that provide authenticity in the presence of side-channel leakage are essential primitives. These constructions often rely on primitives designed for strong leakage protection, among others including the use of strong-unpredictable (tweakable) block-ciphers.
This paper extends the strong-unpredictability security definition to the versatile and new forkcipher primitive. We show how to construct secure and efficient MAC and AEs that guarantee authenticity in the presence of leakage. We present a leakage-resistant MAC, ForkMAC, and two leakage-resistant AE schemes, ForkDTE1 and ForkDTE2, which use forkciphers instead of traditional secure (tweakable) block-ciphers as compared to the prior art. We prove and analyze their security in the presence of leakage based on a strong unpredictable forkcipher. A comparison with the state-of-the-art in terms of both security and efficiency is followed in the paper.
Key advantages and highlights promoted by the proposed constructions are that for the minimal assumptions they require, unpredictability with leakage-based security, the tag-generation of ForkMAC is the most efficient among leakage-resilient MAC proposals, equivalent to HBC. ForkDTE 1 and 2 have a more efficient encryption than any other scheme, achieving integrity with leakage (and also providing misuse-resistance).



## 2024/1326

* Title: On the anonymity of one authenticated key agreement scheme for mobile vehicles-assisted precision agricultural IoT networks
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2024/1326)
* [Download](https://eprint.iacr.org/2024/1326.pdf)

### Abstract

Smart farming uses different vehicles to manage all the operations on the farm. These vehicles should be put to good use for secure data transmission. The Vangala et al.'s key agreement scheme [IEEE TIFS, 18 (2023), 904-9193] is designed for agricultural IoT networks. In this note, we show that the scheme fails to keep anonymity, instead pseudonymity.  The scheme simply thinks that anonymity is equivalent to preventing the real identity from being recovered.  But the true anonymity  means that the adversary cannot attribute different sessions to target users.  To the best of our knowledge, it is the first time to clarify the differences between anonymity and pseudonymity.



## 2024/1327

* Title: Public-Key Anamorphism in (CCA-secure) Public-Key Encryption and Beyond
* Authors: Giuseppe Persiano, Duong Hieu Phan, Moti Yung
* [Permalink](https://eprint.iacr.org/2024/1327)
* [Download](https://eprint.iacr.org/2024/1327.pdf)

### Abstract

The notion of (Receiver-) Anamorphic Encryption was put forth recently to show that a dictator (i.e., an overreaching government), which demands to get the receiver’s private key and even dictates messages to the sender, cannot prevent the receiver from getting an additional covert anamorphic message from a sender. The model required an initial private collaboration to share some secret. There may be settings though where an initial collaboration may be impossible or performance-wise prohibitive, or cases when we need an immediate message to be sent without private key generation (e.g., by any casual sender in need). This situation, to date, somewhat limits the applicability of anamorphic encryption.

To overcome this, in this work, we put forth the new notion of “public-key anamorphic encryption,” where, without any initialization, any sender that has not coordinated in any shape or form with the receiver, can nevertheless, under the dictator control of the receiver’s private key, send the receiver an additional anamorphic secret message hidden from the dictator. We define the new notion with its unique new properties, and then prove that, quite interestingly, the known CCA-secure Koppula-Waters (KW) system is, in fact, public-key anamorphic.

We then describe how a public-key anamorphic scheme can support a new hybrid anamorphic encapsulation mode (KDEM) where the public-key anamorphic part serves a bootstrapping mechanism to activate regular anamorphic messages in the same ciphertext, thus together increasing the anamorphic channel capacity.

Looking at the state of research thus far, we observe that the initial system (Eurocrypt’22) that was shown to have regular anamorphic properties is the CCA-secure Naor-Yung (and other related schemes). Here we identify that the KW CCA-secure scheme also provides a new type of anamorphism. Thus, this situation is hinting that there may be a connection between some types of CCA-secure schemes and some type of anamorphic schemes (in spite of the fact that the goals of the two primitives are fundamentally different); this question is foundational in nature. Given this, we identify a sufficient condition for a “CCA-secure scheme which is black-box reduced from a CPA secure scheme” to directly give rise to an “anamorphic encryption scheme!” Furthermore, we identify one extra property of the reduction, that yields a public-key anamorphic scheme as defined here.



## 2024/1328

* Title: A Note on ARADI and LLAMA
* Authors: Roberto Avanzi, Orr Dunkelman, Shibam Ghosh
* [Permalink](https://eprint.iacr.org/2024/1328)
* [Download](https://eprint.iacr.org/2024/1328.pdf)

### Abstract

Recently, the NSA has proposed a block cipher called ARADI and a mode of operation called LLAMA for memory encryption applications.
In this note, we comment on this proposal, on its suitability for the intended application, and describe an attack on LLAMA that breaks confidentiality of ciphertext and allows a straightforward forgery attack breaking integrity of ciphertext (INT-CTXT) using a related-IV attack.
Both attacks have negligible complexity.



## 2024/1329

* Title: Small Public Exponent Brings More: Improved Partial Key Exposure Attacks against RSA
* Authors: Yansong Feng, Abderrahmane Nitaj, Yanbin Pan
* [Permalink](https://eprint.iacr.org/2024/1329)
* [Download](https://eprint.iacr.org/2024/1329.pdf)

### Abstract

Let $(N,e)$ be a public key of the RSA cryptosystem, and $d$ be the corresponding private key. In practice, we usually choose a small $e$  for quick encryption. In this paper, we improve partial private key exposure attacks against RSA with MSBs of $d$ and small $e$. The key idea is that under such a setting we can usually obtain more information about the prime factors of $N$ and then, by solving a univariate modular polynomial equation using Coppersmith's method, $N$ can be factored in polynomial time. Compared to previous results, we reduce the number of the leaked bits in $d$ that are needed to mount the attack by $\log_2 (e)$ bits. For $e=65537$, previous work required an additional enumeration of 17 bits to achieve our new bound, resulting in a $2^{10}$ (or 1,024x) increase in time consumption. Furthermore, our experiments show that for a $1024$-bit modulus $N$, our attack can achieve the theoretical bound on a simple personal computer, which verifies the new method.



## 2024/1330

* Title: New Results for Coppersmith's Method from the Perspective of Sumsets Theory
* Authors: Yansong Feng, Abderrahmane Nitaj, Yanbin Pan
* [Permalink](https://eprint.iacr.org/2024/1330)
* [Download](https://eprint.iacr.org/2024/1330.pdf)

### Abstract

Coppersmith's method, combined with the  Jochemsz-May strategy, is widely used to find the small roots of multivariate polynomials for cryptanalysis.
At Asiacrypt'23, Meers and Nowakowski improved the Jochemsz-May strategy from a single polynomial equation to a system of polynomial equations and proposed a new method, called Automated Coppersmith. Note that it is typically a tedious and non-trivial task to determine asymptotic upper bounds for Coppersmith’s method and
manual analysis has to be performed anew when a new set of polynomials is considered. By making certain heuristic assumption, Meers and Nowakowski showed that the bound can be obtained using Lagrange interpolation with the computer, but it is still time-consuming. Moreover, we find that sometimes the interpolation method may get stuck in local convergence, which will result in an incorrect
bound when a natural termination strategy is employed in the method.

In this paper, we revisit the Jochemsz-May strategy as well as the work of Meers and Nowakowski and point out that the bound can be obtained by calculating the leading coefficient of some Hilbert function, which is exactly the volume of the corresponding Newton polytope. To this end, we introduce the concept of Sumsets theory and propose a series of related results and algorithms. Compared with the Automated Coppersmith, we overcome the issue of getting stuck in local convergence and directly eliminate the time-consuming calculation for $f^m$ in Automated Coppersmith when $m$ is large, which brings a 1000x$\sim$1200x improvement in running time for some polynomials in our experiment.


Additionally, our new method offers a new perspective on understanding Automated Coppersmith, thus providing proof of Meers and Nowakowski's Heuristic 2 for the system of a single polynomial.



## 2024/1331

* Title: Practical  Small Private Exponent Attacks against RSA
* Authors: Yansong Feng, Zhen Liu, Abderrahmane Nitaj, Yanbin Pan
* [Permalink](https://eprint.iacr.org/2024/1331)
* [Download](https://eprint.iacr.org/2024/1331.pdf)

### Abstract

It is well known that the best small private exponent attack against RSA is that when the private exponent $d < N^{0.292}$, one can factor the  RSA modulus $N = pq$. However, the bound $N^{0.292}$ is very difficult to achieve directly since we need to deal with some lattice with very high dimension, which seems infeasible by now. Recently, Li et al. proposed a practical attack that can solve cases when $d$ approaches $N^{0.292}$ within a month for $1024$ bit $N$. In this paper, we propose an improved practical small private exponent attack by enumerating the most significant bits of $p + q$. Together with some skills in implementations, we can also achieve the bound $N^{0.292}$, but with significantly less time compared to previous work.

Date Sujet#  Auteur
26 Aug 24 o [digest] 2024 Week 341IACR ePrint Archive

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal