Newsportal USENET - [digest] 2024 Week 35

## In this issue

1. [2023/1728] Simulation-Secure Threshold PKE from LWE with ...
2. [2024/1332] Attacking trapdoors from matrix products
3. [2024/1333] Efficient online and Non-Interactive Threshold ...
4. [2024/1334] Chosen Text Attacks Against an Image Encryption ...
5. [2024/1335] Perfect Monomial Prediction for Modular Addition
6. [2024/1336] Fast Low Level Disk Encryption Using FPGAs
7. [2024/1337] Construction bent functions using the Maiorana ...
8. [2024/1338] Horcrux: Synthesize, Split, Shift and Stay Alive ...
9. [2024/1339] Comprehensive Robustness Analysis of GCM, CCM, and OCB3
10. [2024/1340] Unbalanced Private Set Union with Reduced ...
11. [2024/1341] Approach for High-Performance Random Number ...
12. [2024/1342] Unconditionally secure key distribution without ...
13. [2024/1343] Generalized one-way function and its application
14. [2024/1344] Quantum Security of a Compact Multi-Signature
15. [2024/1345] SoK: The Engineer’s Guide to Post-Quantum ...
16. [2024/1346] Provably Secure Online Authenticated Encryption and ...
17. [2024/1347] Secure Multiparty Computation with Lazy Sharing
18. [2024/1348] Zero-Knowledge Validation for an Offline Electronic ...
19. [2024/1349] Oblivious Pseudo Random Function base on Ideal ...
20. [2024/1350] Update to the Sca25519 Library: Mitigating Tearing- ...
21. [2024/1351] Proximity Gaps in Interleaved Codes
22. [2024/1352] ISABELLA: Improving Structures of Attribute-Based ...
23. [2024/1353] On the overflow and $p$-adic theory applied to ...
24. [2024/1354] Votexx: Extreme Coercion Resistance
25. [2024/1355] Direct Range Proofs for Paillier Cryptosystem and ...
26. [2024/1356] Leakage-Resilience of Circuit Garbling
27. [2024/1357] Understanding the Blockchain Interoperability Graph ...
28. [2024/1358] Quantum Sieving for Code-Based Cryptanalysis and ...
29. [2024/1359] Finding Complete Impossible Differential Attacks on ...
30. [2024/1360] CPA-secure KEMs are also sufficient for Post- ...
31. [2024/1361] What Did Come Out of It? Analysis and Improvements ...
32. [2024/1362] A Documentation of Ethereum’s PeerDAS
33. [2024/1363] Improved Key Recovery Attacks on Reduced-Round Salsa20
34. [2024/1364] FLIP-and-prove R1CS
35. [2024/1365] High-Throughput GPU Implementation of Dilithium ...
36. [2024/1366] Adaptive Successive Over-Relaxation Method for a ...
37. [2024/1367] A Better Kyber Butterfly for FPGAs
38. [2024/1368] Tightly Secure Non-Interactive BLS Multi-Signatures
39. [2024/1369] AGATE: Augmented Global Attested Trusted Execution ...
40. [2024/1370] ML based Improved Differential Distinguisher with ...
41. [2024/1371] PIGEON: A Framework for Private Inference of Neural ...

## 2023/1728

* Title: Simulation-Secure Threshold PKE from LWE with Polynomial Modulus
* Authors: Daniele Micciancio, Adam Suhl
* [Permalink](https://eprint.iacr.org/2023/1728)
* [Download](https://eprint.iacr.org/2023/1728.pdf)

### Abstract

In LWE based cryptosystems, using small (polynomially bounded) ciphertext modulus improves both efficiency and security.
In threshold encryption, one often needs "simulation security": the ability to simulate decryption shares without the secret key.
Existing lattice-based threshold encryption schemes provide one or the other but not both.
Simulation security has seemed to require superpolynomial flooding noise,
and the schemes with polynomial modulus use Rényi divergence based analyses that are sufficient for game-based but not simulation security.

In this work, we give the first construction of simulation-secure lattice-based threshold PKE with polynomially bounded modulus.
The construction itself is relatively standard, but we use an improved analysis, proving that when the ciphertext noise and flooding noise are both Gaussian, simulation is possible even with very small flooding noise.
Our modulus is small not just asymptotically but also concretely: this technique gives parameters roughly comparable to those of highly optimized non-threshold schemes like FrodoKEM.
As part of our proof, we show that LWE remains hard in the presence of some types of leakage; these results and techniques may also be useful in other contexts where noise flooding is used.

## 2024/1332

* Title: Attacking trapdoors from matrix products
* Authors: Thomas Decru, Tako Boris Fouotsa, Paul Frixons, Valerie Gilchrist, Christophe Petit
* [Permalink](https://eprint.iacr.org/2024/1332)
* [Download](https://eprint.iacr.org/2024/1332.pdf)

### Abstract

Recently, Geraud-Stewart and Naccache proposed two trapdoors based on matrix products. In this paper, we answer the call for cryptanalysis. We explore how using the trace and determinant of a matrix can be used to attack their constructions. We fully break their first construction in a polynomial-time attack. We show an information leak in the second construction using characteristic polynomials, and provide an attack using traces that decreases the bit security by about half.

## 2024/1333

* Title: Efficient online and Non-Interactive Threshold Signatures with Identifiable Aborts for Identity-Based Signatures in the IEEE P1363 Standard
* Authors: Yan Jiang, Youwen Zhu, Jian Wang, Yudi Zhang
* [Permalink](https://eprint.iacr.org/2024/1333)
* [Download](https://eprint.iacr.org/2024/1333.pdf)

### Abstract

Identity-based threshold signature (IDTS) enables the generation of valid signatures without revealing cryptographic keys in the signing process. While current protocols have achieved much progress in their efficiency, many schemes easily suffer from denial-of-service attacks in which misbehaving parties could keep from generating signatures without being caught. The identifiable abort property is designed to withstand such an attack in some recent IDTS protocols. However, all these schemes require many rounds of interaction for the resulting signature or utilize cryptographic techniques, which have a high complexity. In this study, we put forward a novel IDTS protocol that can achieve identifiable abort and resist arbitrary collusion attacks. Precisely, this ensures that corrupted parties are responsible in case of failure and cannot jointly obtain the input of honest parties. Moreover, we present the ideal IDTS functionality and provide the provable security of the proposed protocol with the global random oracle model. Our scheme has non-interactive signing, compatibility with the offline/online settings, and practical efficiency for the online phase. Finally, we give theoretical analyses and experimental results of our solution, showing that the signing time is less than two milliseconds and that the scheme is suitable for resource-constrained settings.

## 2024/1334

* Title: Chosen Text Attacks Against an Image Encryption Based on the Kronecker Xor Product, the Hill Cipher and the Sigmoid Logistic Map
* Authors: George Teseleanu
* [Permalink](https://eprint.iacr.org/2024/1334)
* [Download](https://eprint.iacr.org/2024/1334.pdf)

### Abstract

In 2023, Mfungo et al. presented an image encryption scheme that relies on a series of diffusion techniques and uses a chaotic map to generate three secret keys. Note that two out of three keys are dynamically generated based on the size of the original image, while the remaining key is static. The authors claim that their proposal offers $149$ bits of security. Unfortunately, we found a chosen plaintext attack that requires $2$ oracle queries and has a worse case complexity of $\mathcal O(2^{32})$. If the attacker has access to $1$ encryption oracle query and $1$ decryption oracle query, we can lower the complexity to $\mathcal O(2^{18.58})$. Encrypting an image with Mfungo et al.'s scheme has a worst case complexity of $\mathcal O(2^{33})$. Therefore, both our attacks are faster than encrypting an image. Our attacks are feasible because the dynamic keys remain unchanged for different plaintext images of the same size, and the static key remains the same for all images.

## 2024/1335

* Title: Perfect Monomial Prediction for Modular Addition
* Authors: Kai Hu, Trevor Yap
* [Permalink](https://eprint.iacr.org/2024/1335)
* [Download](https://eprint.iacr.org/2024/1335.pdf)

### Abstract

Modular addition is often the most complex component of typical Addition-Rotation-XOR (ARX) ciphers, and the division property is the most effective tool for detecting integral distinguishers. Thus, having a precise division property model for modular addition is crucial in the search for integral distinguishers in ARX ciphers.

Current division property models for modular addition either (a) express the operation as a Boolean circuit and apply standard propagation rules for basic operations (COPY, XOR, AND), or (b) treat it as a sequence of smaller functions with carry bits, modeling each function individually. Both approaches were originally proposed for the two-subset bit-based division property (2BDP), which is theoretically imprecise and may overlook some balanced bits.

Recently, more precise versions of the division property, such as parity sets, three-subset bit-based division property without unknown subsets (3BDPwoU) or monomial prediction (MP), and algebraic transition matrices have been proposed. However, little attention has been given to modular addition within these precise models.

The propagation rule for the precise division property of a vectorial Boolean function $\boldsymbol{f}$ requires that $\boldsymbol{u}$ can propagate to $\boldsymbol{v}$ if and only if the monomial $\pi_{\boldsymbol{u}}({\boldsymbol{x}})$ appears in $\pi_{\boldsymbol{v}}( \boldsymbol{f} )$. Braeken and Semaev (FSE 2005) studied the algebraic structure of modular addition and showed that for $\boldsymbol{x} \boxplus \boldsymbol{y} = \boldsymbol{z}$, the monomial $\pi_{\boldsymbol{u}}(\boldsymbol{x})\pi_{\boldsymbol{v}}(\boldsymbol{v})$ appears in $\pi_{\boldsymbol{w}}(\boldsymbol{w})$ if and only if $\boldsymbol{u} + \boldsymbol{v} = \boldsymbol{w}$. Their theorem directly leads to a precise division property model for modular addition. Surprisingly, this model has not been applied in division property searches, to the best of our knowledge.

In this paper, we apply Braeken and Semaev's theorem to search for integral distinguishers in ARX ciphers, leading to several new results. First, we improve the state-of-the-art integral distinguishers for all variants of the Speck family, significantly enhancing search efficiency for Speck-32/48/64/96 and detecting new integral distinguishers for Speck-48/64/96/128. Second, we determine the exact degrees of output bits for $7$-round Speck-$32$ and all/16/2 output bits for $2/3/4$-round Alzette for the first time. Third, we revisit the choice of rotation parameters in Speck instances, providing a criterion that enhances resistance against integral distinguishers. Additionally, we offer a simpler proof for Braeken and Semaev's theorem using monomial prediction, demonstrating the potential of division property methods in the study of Boolean functions.

We hope that the proposed methods will be valuable in the future design of ARX ciphers.

## 2024/1336

* Title: Fast Low Level Disk Encryption Using FPGAs
* Authors: Debrup Chakraborty, Sebati Ghosh, Cuauhtemoc Mancillas Lopez, Palash Sarkar
* [Permalink](https://eprint.iacr.org/2024/1336)
* [Download](https://eprint.iacr.org/2024/1336.pdf)

### Abstract

A fixed length tweakable enciphering scheme (TES) is the appropriate cryptographic functionality for low level disk encryption. Research on TES over the last two decades have led to a number of proposals many of which have already been implemented using FPGAs. This paper considers the FPGA implementations of two more recent and promising TESs, namely AEZ and FAST. The relevant architectures are described and simulation results on the Xilinx Virtex 5 and Virtex 7 FPGAs are presented. For comparison, two IEEE standard schemes, XCB and EME2 are considered. The results indicate that FAST outperforms the other schemes making it a serious candidate for future incorporation by disk manufacturers and standardisation bodies.

## 2024/1337

* Title: Construction bent functions using the Maiorana McFarland class
* Authors: Juan Carlos Ku-Cauich, Javier Diaz-Vargas
* [Permalink](https://eprint.iacr.org/2024/1337)
* [Download](https://eprint.iacr.org/2024/1337.pdf)

### Abstract

We are using the extended Maiorana-McFarland construction to create new bent functions. When we start with a bent function of dimension s-r, we can produce a new function of dimension s+r while ensuring that its balance is limited to the set of vectors with an even Hamming weight in its domain. We also compare this approach with the case where r=1 and apply it multiple times. Finally, we provide an algorithm as an example, focusing on the case where r=2 and another algorithm using r=1 two times.

## 2024/1338

* Title: Horcrux: Synthesize, Split, Shift and Stay Alive Preventing Channel Depletion via Universal and Enhanced Multi-hop Payments
* Authors: Anqi Tian, Peifang Ni, Yingzi Gao, Jing Xu
* [Permalink](https://eprint.iacr.org/2024/1338)
* [Download](https://eprint.iacr.org/2024/1338.pdf)

### Abstract

Payment Channel Networks (PCNs) have been highlighted as viable solutions to address the scalability issues in current permissionless blockchains. They facilitate off-chain transactions, significantly reducing the load on the blockchain. However, the extensive reuse of multi-hop routes in the same direction poses a risk of channel depletion, resulting in involved channels becoming unidirectional or even closing, thereby compromising the sustainability and scalability of PCNs. Even more concerning, existing rebalancing protocol solutions heavily rely on trust assumptions and scripting languages, resulting in compromised universality and reliability.

In this paper, we present Horcrux, a universal and efficient multi-party virtual channel protocol without relying on extra trust assumptions, scripting languages, or the perpetual online requirement. Horcrux fundamentally addresses the channel depletion problem using a novel approach termed flow neutrality, which minimizes the impact on channel balance allocations during multi-hop payments (MHPs). Additionally, we formalize the security properties of Horcrux by modeling it within the Global Universal Composability framework and provide a formal security proof.

We implement Horcrux on a real Lightning Network dataset, comprising 10,529 nodes and 38,910 channels, and compare it to the state-of-the-art rebalancing schemes such as Shaduf [NDSS'22], Thora [CCS'22], and Revive [CCS'17]. The experimental results demonstrate that (1) the entire process of Horcrux costs less than 1 USD, significantly lower than Shaduf; (2) Horcrux achieves a $12\%$-$30\%$ increase in payment success ratio and reduces user deposits required for channels by $70\%$-$91\%$; (3) the performance of Horcrux improves by $1..2x$-$1.5x$ under long-term operation; and (4) Horcrux maintains a nearly zero channel depletion rate, whereas both Revive and Shaduf result in thousands of depleted channels.

## 2024/1339

* Title: Comprehensive Robustness Analysis of GCM, CCM, and OCB3
* Authors: Akiko Inoue, Tetsu Iwata, Kazuhiko Minematsu
* [Permalink](https://eprint.iacr.org/2024/1339)
* [Download](https://eprint.iacr.org/2024/1339.pdf)

### Abstract

Clarifying the robustness of authenticated encryption (AE) schemes, such as security under nonce misuse or Release of Unverified Plaintext (RUP), is critically important due to the extensive use of AEs in real-world applications.
We present a comprehensive analysis of the robustness of well-known standards, namely GCM, CCM, and OCB3. Despite many existing studies, we uncovered several robustness properties for them that were not known in the literature.
In particular, we show that both GCM and CCM maintain authenticity under RUP. Moreover, CCM keeps this feature even if a nonce is misused. Together with existing analysis, our work gives a complete picture of the robustness of these standards for the first time. Our results also imply several new robust AE schemes based on GCM and CCM.

## 2024/1340

* Title: Unbalanced Private Set Union with Reduced Computation and Communication
* Authors: Cong Zhang, Yu Chen, Weiran Liu, Liqiang Peng, Meng Hao, Anyu Wang, Xiaoyun Wang
* [Permalink](https://eprint.iacr.org/2024/1340)
* [Download](https://eprint.iacr.org/2024/1340.pdf)

### Abstract

Private set union (PSU) is a cryptographic protocol that allows two parties to compute the union of their sets without revealing anything else. Despite some efficient PSU protocols that have been proposed, they mainly focus on the balanced setting, where the sets held by the parties are of similar size. Recently, Tu et al. (CCS 2023) proposed the first unbalanced PSU protocol which achieves sublinear communication complexity in the size of the larger set.

In this paper, we are interested in improving the efficiency of the unbalanced PSU protocol. We find that oblivious key-value store (OKVS) data structure plays an essential role in the most recently proposed PSU constructions and formalize unbalanced PSU as an OKVS decoding process with sublinear communication. Our key insight lies in when OKVS satisfies sparsity property, obtaining the necessary decoding information precisely aligns with the batch private information retrieval (BatchPIR) problem. We give two concrete constructions of unbalanced PSU protocols based on different OKVS encoding strategies. The first is based on oblivious PRF (OPRF) and a newly introduced cryptographic protocol called permuted private equality test, while the second is based on re-randomizable public key encryption.
Both our two constructions achieve sublinear communication complexity in the size of the larger set.

We implement our two unbalanced PSU protocols and compare them with the state-of-the-art unbalanced PSU of Tu et al. Experiments show that our protocols achieve a $1.3-5.6\times $ speedup in running time and $2.1-11.8\times$ shrinking in communication cost, depending on set sizes and network environments.

## 2024/1341

* Title: Approach for High-Performance Random Number Generators for Critical Systems
* Authors: Pascal Hammer, Veronika Krause, Tobias Probst, Jürgen Mottok
* [Permalink](https://eprint.iacr.org/2024/1341)
* [Download](https://eprint.iacr.org/2024/1341.pdf)

### Abstract

In times of digitalization, the encryption and signing
of sensitive data is becoming increasingly important. These
cryptographic processes require large quantities of high-quality
random numbers. Which is why a high-performance random
number generator (RNG) is to be developed. For this purpose,
existing concepts of RNGs and application standards are first
analyzed. The proposed approach is to design a physical true
random number generator (PTRNG) with a high output of
random numbers. Based on this, the development begins with
the analog part of the RNG, the noise signal source and a
suitable amplifier for the analog noise signal. Therefore, a
special noise diode from Noisecom and an amplifier from NXP
were chosen and analyzed in different measurements. From
the results of the measurements, it can be concluded that both
components are suitable for use in the RNG.

## 2024/1342

* Title: Unconditionally secure key distribution without quantum channel
* Authors: Hua-Lei Yin
* [Permalink](https://eprint.iacr.org/2024/1342)
* [Download](https://eprint.iacr.org/2024/1342.pdf)

### Abstract

Key distribution plays a fundamental role in cryptography. Currently, the quantum scheme stands as the only known method for achieving unconditionally secure key distribution. This method has been demonstrated over distances of 508 and 1002 kilometers in the measurement-device-independent and twin-field configurations, respectively. However, quantum key distribution faces transmission distance issues and numerous side channel attacks since the basic physical picture requires the use of quantum channels between users. Even when quantum repeater and quantum constellation are used, commercializing quantum cryptography on a large scale remains unattainable due to the considerable expense and significant technical hurdles associated with establishing a global quantum network and facilitating mobile quantum communication. Here, by discovering the provable quantum one-way function, we propose another key distribution scheme with unconditional security, named probability key distribution, that promises users between any two distances to generate a fixed and high secret key rate. There are no quantum channels for exchanging quantum signals between two legitimate users. Non-local entangled states can be generated, identified and measured in the equivalent virtual protocol and can be used to extract secret keys. We anticipate that this discovery presents a paradigm shift in achieving unconditionally secure cryptography, thereby facilitating its widespread application on a global scale.

## 2024/1343

* Title: Generalized one-way function and its application
* Authors: Hua-Lei Yin
* [Permalink](https://eprint.iacr.org/2024/1343)
* [Download](https://eprint.iacr.org/2024/1343.pdf)

### Abstract

One-way functions are fundamental to classical cryptography and their existence remains a longstanding problem in computational complexity theory. Recently, a provable quantum one-way function has been identified, which maintains its one-wayness even with unlimited computational resources. Here, we extend the mathematical definition of functions to construct a generalized one-way function by virtually measuring the qubit of provable quantum one-way function and randomly assigning the corresponding measurement outcomes with identical probability. Remarkably, using this generalized one-way function, we have developed an unconditionally secure key distribution protocol based solely on classical data processing, which can then utilized for secure encryption and signature. Our work highlights the importance of information in characterizing quantum systems and the physical significance of the density matrix. We demonstrate that probability theory and randomness are effective tools for countering adversaries with unlimited computational capabilities.

## 2024/1344

* Title: Quantum Security of a Compact Multi-Signature
* Authors: Shaoquan Jiang
* [Permalink](https://eprint.iacr.org/2024/1344)
* [Download](https://eprint.iacr.org/2024/1344.pdf)

### Abstract

With the rapid advance in quantum computing, quantum security is now an indispensable property for any cryptographic system. In this paper, we study how to prove the security of a complex cryptographic system in the quantum random oracle model. We first give a variant of Zhandry's compressed quantum random oracle (${\bf CStO}$), called compressed quantum random oracle with adaptive special points ({\bf CStO}$_s$). Then, we extend the on-line extraction technique of Don et al (EUROCRYPT'22) from {\bf CStO} to ${\bf CStO}_s$. We also extend the random experiment technique of Liu and Zhandry (CRYPTO'19) for extracting the ${\bf CStO}$ query that witnesses the future adversarial output. With these preparations, a systematic security proof in the quantum random oracle model can start with a random {\bf CStO} experiment (that extracts the witness for the future adversarial output) and then convert this game to one involving ${\bf CStO}_s$. Next, the on-line extraction technique for ${\bf CStO}_s$ can be applied to extract the witness for any on-line commitment. With this strategy, we give a security proof of our recent compact multi-signature framework that is converted from any weakly secure linear ID scheme.. We also prove the quantum security of our recent lattice realization of this linear ID scheme, by iteratively applying the weakly collapsing protocol technique of Liu and Zhandry (CRYPTO 2019). Combining these two results, we obtain the first quantum security proof for a compact multi-signature.

## 2024/1345

* Title: SoK: The Engineer’s Guide to Post-Quantum Cryptography for Embedded Devices
* Authors: Maximilian Pursche, Nikolai Puch, Sebastian N. Peters, Michael P. Heinl
* [Permalink](https://eprint.iacr.org/2024/1345)
* [Download](https://eprint.iacr.org/2024/1345.pdf)

### Abstract

Embedded systems are flexible and cost-effective and thus have found a use case in almost every part of our daily lives. Due to their widespread use, they have also become valuable targets for cyber attacks. However, translating cutting-edge cyber security from servers and desktops to the embedded realm can be challenging due to the limited computational power and memory of embedded devices. Although quantum computing is still in early research and development, it threatens to break conventional asymmetric cryptography which is a key component of most secure applications currently in use. Given the long lifespan of embedded devices, which can last for decades, research must find solutions for post-quantum (PQ) security rather sooner than later. The field of post-quantum cryptography (PQC) received significant attention in 2019 when the National Institute for Standards and Technology (NIST) launched a competition to find suitable PQC algorithms. During the PQC competition, the applicability of novel PQC algorithms to embedded devices was an important topic that garnered significant research interest. We provide a survey of the latest research regarding PQC for embedded systems. However, rather than focusing on PQC algorithms, our study revolves around practical use cases intending to help embedded developers understand the current state of research from an integration perspective.

## 2024/1346

* Title: Provably Secure Online Authenticated Encryption and Bidirectional Online Channels
* Authors: Arghya Bhattacharjee, Ritam Bhaumik, Daniel Collins, Mridul Nandi
* [Permalink](https://eprint.iacr.org/2024/1346)
* [Download](https://eprint.iacr.org/2024/1346.pdf)

### Abstract

In this work, we examine online authenticated encryption with variable expansion. We follow a notion where both encryption and decryption are online, and security is ensured in the RUP (Release of Unverified Plaintext) setting. Then we propose a generic way of obtaining an online authenticated encryption mode from a tweakable online encryption mode based on the encode-then-encipher paradigm (Bellare and Rogaway, Asiacrypt 2000). To instantiate our generic scheme, we start with proposing a provably-secure tweakable online encryption mode called t-OleF, a tweakable version of OleF (Bhaumik and Nandi, ToSC 2016(2)), and then plug it into our generic scheme to obtain OlÆF, a provably-secure online authenticated encryption mode. As an application, we propose a primitive we call a bidirectional online channel suited for communication between lightweight devices.

## 2024/1347

* Title: Secure Multiparty Computation with Lazy Sharing
* Authors: Shuaishuai Li, Cong Zhang, Dongdai Lin
* [Permalink](https://eprint.iacr.org/2024/1347)
* [Download](https://eprint.iacr.org/2024/1347.pdf)

### Abstract

Secure multiparty computation (MPC) protocols enable $n$ parties, each with private inputs, to compute a given function without leaking information beyond the outputs. One of the main approaches to designing efficient MPC protocols is to use secret sharing. In general, secret sharing based MPC contains three phases: input sharing, circuit evaluation, and output recovery. If the adversary corrupts at most $t$ parties, the protocol typically uses $(t,n)$ threshold secret sharing to share the inputs. In this work, we consider a weaker variant of threshold secret sharing called lazy threshold secret sharing (or simply lazy sharing) and show that
- Lazy sharing can serve as a viable alternative to threshold secret sharing in MPC without compromising security.
- Lazy sharing could be generated more efficiently than threshold secret sharing.
As a result, replacing threshold secret sharing with lazy sharing can lead to a more efficient input sharing phase. Moreover, we propose that the efficiency of the circuit evaluation phase can also be further improved. To support this claim, we apply lazy sharing to several state-of-the-art MPC protocols and analyze the efficiency gain in various settings. These protocols include the GMW protocol (Goldreich et al., STOC 1987), the AFLNO protocol (Araki et al.., CCS 2016), and the SPDZ protocol (Damg{\aa}rd et al., CRYPTO 2012). By doing so, we analyze the efficiency gains in various settings and highlight the advantages of incorporating lazy sharing into MPC protocols.

## 2024/1348

* Title: Zero-Knowledge Validation for an Offline Electronic Document Wallet using Bulletproofs
* Authors: Michael Brand, Benoît Poletti
* [Permalink](https://eprint.iacr.org/2024/1348)
* [Download](https://eprint.iacr.org/2024/1348.pdf)

### Abstract

We describe designs for an electronic wallet, meant for the housing
of official government documents, which solves the problem of
displaying document data to untrusted parties (e.g., in order to allow
users to prove that they are above the drinking age). The wallet
attains this goal by employing Zero-Knowledge Proof technologies,
ascertaining that nothing beyond the intended information is ever
shared. In order to be practically applicable, the wallet has to meet
many additional constraints, such as to be usable in offline scenarios,
to employ only widely-accessible communication methods which,
themselves, must not impinge on the user’s privacy, and to be
constructed solely over standard, widely-studied cryptographic
algorithms, offering appropriately high levels of cryptographic
security. We explain how our design was able to successfully meet
all such additional constraints.

## 2024/1349

* Title: Oblivious Pseudo Random Function base on Ideal Lattice, Application in PSI and PIR
* Authors: Zhuang Shan, Leyou Zhang, Qing Wu, Qiqi Lai, Fuchun Guo
* [Permalink](https://eprint.iacr.org/2024/1349)
* [Download](https://eprint.iacr.org/2024/1349.pdf)

### Abstract

Privacy set intersection (PSI) and private information retrieval (PIR) are important areas of research in privacy protection technology. One of the key tools for both is the oblivious pseudorandom function (OPRF). Currently, existing oblivious pseudorandom functions either focus solely on efficiency without considering quantum attacks, or are too complex, resulting in low efficiency.. The aim of this paper is to achieve a balance: to ensure that the oblivious pseudorandom function can withstand quantum attacks while simplifying its structure as much as possible. This paper constructs an efficient oblivious pseudorandom function based on the ideal lattice hardness assumption and the oblivious transfer (OT) technique by Chase and Miao (CRYPTO 2020), and also constructs PSI and PIR.

## 2024/1350

* Title: Update to the Sca25519 Library: Mitigating Tearing-based Side-channel Attacks
* Authors: Lukasz Chmielewski, Lubomír Hrbáček
* [Permalink](https://eprint.iacr.org/2024/1350)
* [Download](https://eprint.iacr.org/2024/1350.pdf)

### Abstract

This short note describes an update to the sca25519 library, an ECC implementation computing the X25519 key-exchange protocol on the Arm Cortex-M4 microcontroller. The sca25519 software came with extensive mitigations against various side-channel and fault attacks and was, to our best knowledge, the first to claim affordable protection against multiple classes of attacks that are motivated by distinct real-world application scenarios.

This library is protected against various passive and active side-channel threats. However, both classes of attacks were considered separately, i.e., combining the attacks is considered out-of-scope because to successfully execute such a combined attack, the adversary would need to be very powerful (e.g., a very well-equipped security laboratory). Protection against such powerful adversaries is considered infeasible without using dedicated protected hardware with which Arm Cortex-M4 is not equipped.

However, there exists a particular class of easy and cheap active attacks: they are called tearing, and they are well known in the smartcard context. In this paper, we extend the scope of the library to also consider a combination of tearing and side-channel attacks. In this note, we show how we can mitigate such a combination by performing a small code update. The update does not affect the efficiency of the library.

## 2024/1351

* Title: Proximity Gaps in Interleaved Codes
* Authors: Benjamin E. Diamond, Angus Gruen
* [Permalink](https://eprint.iacr.org/2024/1351)
* [Download](https://eprint.iacr.org/2024/1351.pdf)

### Abstract

A linear error-correcting code exhibits proximity gaps if each affine line of words either consists entirely of words which are close to the code or else contains almost no such words. In this short note, we prove that for each linear code which exhibits proximity gaps within the unique decoding radius, that code's interleaved code also does. Combining our result with an argument suggested to us by Angeris, Evans and Roh ('24), we extend those authors' sharpening of the tensor-based proximity gap of Diamond and Posen (Commun. Cryptol.. '24) up to the unique decoding radius, at least in the Reed–Solomon setting.

## 2024/1352

* Title: ISABELLA: Improving Structures of Attribute-Based Encryption Leveraging Linear Algebra
* Authors: Doreen Riepel, Marloes Venema, Tanya Verma
* [Permalink](https://eprint.iacr.org/2024/1352)
* [Download](https://eprint.iacr.org/2024/1352.pdf)

### Abstract

Attribute-based encryption (ABE) is a powerful primitive that has found applications in important real-world settings requiring access control. Compared to traditional public-key encryption, ABE has established itself as a considerably more complex primitive that is additionally less efficient to implement. It is therefore paramount that the we can simplify the design of ABE schemes that are efficient, provide strong security guarantees, minimize the complexity in their descriptions and support all practical features that are desirable for common real-world settings. One of such practical features that is currently still difficult to achieve is multi-authority support. Motivated by NIST's ongoing standardization efforts around multi-authority schemes, we put a specific focus on simplifying the support of multiple authorities in the design of schemes.

To this end, we present ISABELLA, a framework for constructing pairing-based ABE with advanced functionalities under strong security guarantees. At a high level, our approach builds on various works that systematically and generically construct ABE schemes by reducing the effort of proving security to a simpler yet powerful ''core'' called pair encodings. To support the amount of adaptivity required by multi-authority ABE, we devise a new approach to designing schemes from pair encodings, while still being able to benefit from the advantages that pair encodings provide. As a direct result of our framework, we obtain various improvements for existing (multi-authority) schemes as well as new schemes.

## 2024/1353

* Title: On the overflow and $p$-adic theory applied to homomorphic encryption
* Authors: Jacob Blindenbach, Jung Hee Cheon, Gamze Gürsoy, Jiayi Kang
* [Permalink](https://eprint.iacr.org/2024/1353)
* [Download](https://eprint.iacr.org/2024/1353.pdf)

### Abstract

When integer and rational arithmetics are performed using modular arithmetics over $\mathbb{Z}/q\mathbb{Z}$, overflows naturally occur due to the mismatch between the infinite cardinality of $\mathbb{Z}$ or $\mathbb{Q}$ and the finite cardinality of $\mathbb{Z}/q\mathbb{Z}$. Since $\mathbb{Z}/q\mathbb{Z}$ is also the (sub) message space for many secure computation designs, secure computations of integer and rational arithmetics using these schemes must also consider the overflow problem.

Previous works [CLPX, CT-RSA'18] and [HDRdS, ACNS'23] perform integer and rational arithmetics using the CLPX homomorphic encryption scheme, where overflows are avoided by restricting supported circuits. This introduces an additional constraint beyond the noise budget limitation. In our work, we discuss the possibilities of tolerating overflows. Firstly, we explain that when input messages and the final result are well-bounded, intermediate values can go arbitrarily large without affecting output correctness. This kind of overflow is called pseudo-overflow and does not need to be avoided. Secondly, we note that for prime-power modulus $q=p^r$, overflow errors are small in the $p$-adic norm. Therefore, we apply the $p$-adic encoding technique in [HDRdS, ACNS'23] to the BGV/BFV homomorphic encryption scheme with plaintext modulus $p^r$..
Compared to [CLPX, CT-RSA'18] and [HDRdS, ACNS'23], our method supports circuits that are up to $2 \times$ deeper under the same ciphertext parameters, at the cost of an output error bounded by $p^{-r}$ in the $p$-adic norm.

## 2024/1354

* Title: Votexx: Extreme Coercion Resistance
* Authors: David Chaum, Richard T. Carback, Mario Yaksetig, Jeremy Clark, Mahdi Nejadgholi, Bart Preneel, Alan T. Sherman, Filip Zagorski, Bingsheng Zhang, Zeyuan Yin
* [Permalink](https://eprint.iacr.org/2024/1354)
* [Download](https://eprint.iacr.org/2024/1354.pdf)

### Abstract

We provide a novel perspective on a long-standing challenge to the integrity of votes cast without the supervision of a voting booth: "improper influence,'' which we define as any combination of vote buying and voter coercion. In comparison with previous proposals, our system is the first in the literature to protect against a strong adversary who learns all of the voter's keys---we call this property "extreme coercion resistance.'' When keys are stolen, each voter, or their trusted agents (which we call "hedgehogs''), may "nullify'' (effectively cancel) their vote in a way that is unstoppable and irrevocable, and such that the nullification action is forever unattributable to that voter or their hedgehog(s). We demonstrate the security of our VoteXX system in the universal composability model.

As in many other coercion-resistant systems, voters are authorized to vote with public-private keys. Each voter registers their public keys with the Election Authority (EA) in a way that convinces the EA that the voter has memorized a passphrase that corresponds to their private keys. As a consequence, if an adversary obtains a voter's keys, the voter also retains a copy. Voters concerned about adversaries stealing their private keys can themselves, or by delegating to one or more untrusted hedgehog(s), monitor the bulletin board for malicious ballots cast with their keys, and can act to nullify these ballots in a privacy-preserving manner with zero-knowledge proofs.

In comparison with previous proposals, our system offers some protection against even the strongest adversary who learns all keys. Other coercion-resistant protocols either do not address these attacks, place strong limitations on adversarial abilities, or rely on fully trusted parties to assist voters with their keys.

## 2024/1355

* Title: Direct Range Proofs for Paillier Cryptosystem and Their Applications
* Authors: Zhikang Xie, Mengling Liu, Haiyang Xue, Man Ho Au, Robert H. Deng, Siu-Ming Yiu
* [Permalink](https://eprint.iacr.org/2024/1355)
* [Download](https://eprint.iacr.org/2024/1355.pdf)

### Abstract

The Paillier cryptosystem is renowned for its applications in electronic voting, threshold ECDSA, multi-party computation, and more, largely due to its additive homomorphism. In these applications, range proofs for the Paillier cryptosystem are crucial for maintaining security, because of the mismatch between the message space in the Paillier system and the operation space in application scenarios.

In this paper, we present novel range proofs for the Paillier cryptosystem, specifically aimed at optimizing those for both Paillier plaintext and affine operation. We interpret encryptions and affine operations as commitments over integers, as opposed to solely over $\mathbb{Z}_{N}$. Consequently, we propose direct range proof for the updated cryptosystem, thereby eliminating the need for auxiliary integer commitments as required by the current state-of-the-art. Our work yields significant improvements: In the range proof for Paillier plaintext, our approach reduces communication overheads by approximately $60\%$, and computational overheads by $30\%$ and $10\%$ for the prover and verifier, respectively. In the range proof for Paillier affine operation, our method reduces the bandwidth by $70\%$, and computational overheads by $50\%$ and $30\%$ for the prover and verifier, respectively. Furthermore, we demonstrate that our techniques can be utilized to improve the performance of threshold ECDSA and the DCR-based instantiation of the Naor-Yung CCA2 paradigm.

## 2024/1356

* Title: Leakage-Resilience of Circuit Garbling
* Authors: Ruiyang Li, Yiteng Sun, Chun Guo, Francois-Xavier Standaert, Weijia Wang, Xiao Wang
* [Permalink](https://eprint.iacr.org/2024/1356)
* [Download](https://eprint.iacr.org/2024/1356.pdf)

### Abstract

Due to the ubiquitous requirements and performance leap in the past decade, it has become feasible to execute garbling and secure computations in settings sensitive to side-channel attacks, including smartphones, IoTs and dedicated hardwares, and the possibilities have been demonstrated by recent works. To maintain security in the presence of a moderate amount of leaked information about internal secrets, we investigate {\it leakage-resilient garbling}. We augment the classical privacy, obliviousness and authenticity notions with leakages of the garbling function, and define their leakage-resilience analogues.. We examine popular garbling schemes and unveil additional side-channel weaknesses due to wire label reuse and XOR leakages. We then incorporate the idea of label refreshing into the GLNP garbling scheme of Gueron et al. and propose a variant GLNPLR that provably satisfies our leakage-resilience definitions. Performance comparison indicates that GLNPLR is 60X (using AES-NI) or 5X (without AES-NI) faster than the HalfGates garbling with second order side-channel masking, for garbling AES circuit when the bandwidth is 2Gbps.

## 2024/1357

* Title: Understanding the Blockchain Interoperability Graph based on Cryptocurrency Price Correlation
* Authors: Ori Mazor, Ori Rottenstreich
* [Permalink](https://eprint.iacr.org/2024/1357)
* [Download](https://eprint.iacr.org/2024/1357.pdf)

### Abstract

Cryptocurrencies have gained high popularity in
recent years, with over 9000 of them, including major ones such
as Bitcoin and Ether. Each cryptocurrency is implemented on
one blockchain or over several such networks. Recently, various
technologies known as blockchain interoperability have been
developed to connect these different blockchains and create an
interconnected blockchain ecosystem. This paper aims to provide
insights on the blockchain ecosystem and the connection between
blockchains that we refer to as the interoperability graph. Our
approach is based on the analysis of the correlation between
cryptocurrencies implemented over the different blockchains.
We examine over 4800 cryptocurrencies implemented on 76
blockchains and their daily prices over a year. This experimental
study has potential implications for decentralized finance (DeFi),
including portfolio investment strategies and risk management.

## 2024/1358

* Title: Quantum Sieving for Code-Based Cryptanalysis and Its Limitations for ISD
* Authors: Lynn Engelberts, Simona Etinski, Johanna Loyer
* [Permalink](https://eprint.iacr.org/2024/1358)
* [Download](https://eprint.iacr.org/2024/1358.pdf)

### Abstract

Sieving using near-neighbor search techniques is a well-known method in lattice-based cryptanalysis, yielding the current best runtime for the shortest vector problem in both the classical [BDGL16] and quantum [BCSS23] setting. Recently, sieving has also become an important tool in code-based cryptanalysis. Specifically, using a sieving subroutine, [GJN23, DEEK24] presented a variant of the information-set decoding (ISD) framework, which is commonly used for attacking cryptographically relevant instances of the decoding problem. The resulting sieving-based ISD framework yields complexities close to the best-performing classical algorithms for the decoding problem such as [BJMM12, BM18]. It is therefore natural to ask how well quantum versions perform.
In this work, we introduce the first quantum algorithms for code sieving by designing quantum variants of the aforementioned sieving subroutine. In particular, using quantum-walk techniques, we provide a speed-up over the best known classical algorithm from [DEEK24] and over a variant using Grover's algorithm [Gro96]. Our quantum-walk algorithm exploits the structure of the underlying search problem by adding a layer of locality-sensitive filtering, inspired by the quantum-walk algorithm for lattice sieving from [CL21]. We complement our asymptotic analysis of the quantum algorithms with numerical results, and observe that our quantum speed-ups for code sieving behave similarly as those observed in lattice sieving.
In addition, we show that a natural quantum analog of the sieving-based ISD framework does not provide any speed-up over the first presented quantum ISD algorithm [Ber10]. Our analysis highlights that the framework should be adapted in order to outperform the state-of-the-art of quantum ISD algorithms [KT17, Kir18].

## 2024/1359

* Title: Finding Complete Impossible Differential Attacks on AndRX Ciphers and Efficient Distinguishers for ARX Designs
* Authors: Debasmita Chakraborty, Hosein Hadipour, Phuong Hoa Nguyen, Maria Eichlseder
* [Permalink](https://eprint.iacr.org/2024/1359)
* [Download](https://eprint.iacr.org/2024/1359.pdf)

### Abstract

The impossible differential (ID) attack is one of the most important cryptanalytic techniques for block ciphers. There are two phases to finding an ID attack: searching for the distinguisher and building a key recovery upon it. Previous works only focused on automated distinguisher discovery, leaving key recovery as a manual post-processing task, which may lead to a suboptimal final complexity. At EUROCRYPT~2023, Hadipour et al. introduced a unified constraint programming (CP) approach based on satisfiability for finding optimal complete ID attacks in strongly aligned ciphers. While this approach was extended to weakly-aligned designs like PRESENT at ToSC~2024, its application to ARX and AndRX ciphers remained as future work. Moreover, this method only exploited ID distinguishers with direct contradictions at the junction of two deterministic transitions. In contrast, some ID distinguishers, particularly for ARX and AndRX designs, may not be detectable by checking only the existence of direct contradictions.

This paper fills these gaps by extending Hadipour et al.'s method to handle indirect contradictions and adapting it for ARX and AndRX designs. We also present a similar method for identifying zero-correlation (ZC) distinguishers. Moreover, we extend our new model for finding ID distinguishers to a unified optimization problem that includes both the distinguisher and the key recovery for AndRX designs. Our method improves ID attacks and introduces new distinguishers for several ciphers, such as SIMON, SPECK, Simeck, ChaCha, Chaskey, LEA, and SipHash. For example, we achieve a one-round improvement in the ID attacks against SIMON-64-96, SIMON-64-128, SIMON-128-128, SIMON-128-256 and a two-round improvement in the ID attacks against SIMON-128-192. These results significantly contribute to our understanding of the effectiveness of automated tools in the cryptanalysis of different design paradigms.

## 2024/1360

* Title: CPA-secure KEMs are also sufficient for Post-Quantum TLS 1.3
* Authors: Biming Zhou, Haodong Jiang, Yunlei Zhao
* [Permalink](https://eprint.iacr.org/2024/1360)
* [Download](https://eprint.iacr.org/2024/1360.pdf)

### Abstract

In the post-quantum migration of TLS 1.3, an ephemeral Diffie-Hellman must be replaced with a post-quantum key encapsulation mechanism (KEM). At EUROCRYPT 2022, Huguenin-Dumittan and Vaudenay [EC:HugVau22] demonstrated that KEMs with standard CPA security are sufficient for the security of the TLS1.3 handshake. However, their result is only proven in the random oracle model (ROM), and as the authors comment, their reduction is very much non-tight and not sufficient to guarantee security in practice due to the $O(q^6)$-loss, where $q$ is the number of adversary’s queries to random oracles. Moreover, in order to analyze the post-quantum security of TLS 1.3 handshake with a KEM, it is necessary to consider the security in the quantum ROM (QROM). Therefore, they leave the tightness improvement of their ROM proof and the QROM proof of such a result as an interesting open question.

In this paper, we resolve this problem. We improve the ROM proof in [EC:HugVau22] from an $O(q^6)$-loss to an $O(q)$-loss with standard CPA-secure KEMs which can be directly obtained from the underlying public-key encryption (PKE) scheme in CRYSTALS-Kyber. Moreover, we show that if the KEMs are constructed from rigid deterministic public-key encryption (PKE) schemes such as the ones in Classic McElieceand NTRU, this $O(q)$-loss can be further improved to an $O(1)$-loss. Hence, our reductions are sufficient to guarantee security in practice. According to our results, a CPA-secure KEM (which is more concise and efficient than the currently used CCA/1CCA-secure KEM) can be directly employed to construct a post-quantum TLS 1.3. Furthermore, we lift our ROM result into QROM and first prove that the CPA-secure KEMs are also sufficient for the post-quantum TLS 1.3 handshake. In particular, the techniques introduced to improve reduction tightness in this paper may be of independent interest.

## 2024/1361

* Title: What Did Come Out of It? Analysis and Improvements of DIDComm Messaging
* Authors: Christian Badertscher, Fabio Banfi, Jesus Diaz
* [Permalink](https://eprint.iacr.org/2024/1361)
* [Download](https://eprint.iacr.org/2024/1361.pdf)

### Abstract

Self-Sovereign Identity (SSI) empowers individuals and organizations with full control over their data. Decentralized identifiers (DIDs) are at its center, where a DID contains a collection of public keys associated with an entity, and further information to enable entities to engage via secure and private messaging across different platforms. A crucial stepping stone is DIDComm, a cryptographic communication layer that is in production with version 2. Due to its widespread and active deployment, a formal study of DIDComm is highly overdue.

We present the first formal analysis of DIDComm’s cryptography, and formalize its goal of (sender-) anonymity and authenticity. We follow a composable approach to capture its security over a generic network, formulating the goal of DIDComm as a strong ideal communication resource. We prove that the proposed encryption modes reach the expected level of privacy and authenticity, but leak beyond the leakage induced by an underlying network (captured by a parameterizable resource).

We further use our formalism to propose enhancements and prove their security: first, we present an optimized algorithm that achieves simultaneously anonymity and authenticity, conforming to the DIDComm message format, and which outperforms the current DIDComm proposal in both ciphertext size and computation time by almost a factor of 2. Second, we present a novel DIDComm mode that fulfills the notion of anonymity preservation, in that it does never leak more than the leakage induced by the network it is executed over. We finally show how to merge this new mode into our improved algorithm, obtaining an efficient all-in-one mode for full anonymity and authenticity.

## 2024/1362

* Title: A Documentation of Ethereum’s PeerDAS
* Authors: Benedikt Wagner, Arantxa Zapico
* [Permalink](https://eprint.iacr.org/2024/1362)
* [Download](https://eprint.iacr.org/2024/1362.pdf)

### Abstract

Data availability sampling allows clients to verify availability of data on a peer-to-peer network provided by an untrusted source. This is achieved without downloading the full data by sampling random positions of the encoded data.

The long-term vision of the Ethereum community includes a comprehensive data availability protocol using polynomial commitments and tensor codes. As the next step towards this vision, an intermediate solution called PeerDAS is about to integrated, to bridge the way to the full protocol. With PeerDAS soon becoming an integral part of Ethereum's consensus layer, understanding its security guarantees is essential.

This document aims to describe the cryptography used in PeerDAS in a manner accessible to the cryptographic community, encouraging innovation and improvements, and to explicitly state the security guarantees of PeerDAS.

## 2024/1363

* Title: Improved Key Recovery Attacks on Reduced-Round Salsa20
* Authors: Sabyasachi Dey, Gregor Leander, Nitin Kumar Sharma
* [Permalink](https://eprint.iacr.org/2024/1363)
* [Download](https://eprint.iacr.org/2024/1363.pdf)

### Abstract

In this paper, we present an improved attack on the stream cipher Salsa20. Our improvements are based on two technical contributions.
First, we make use of a distribution of a linear combination of several random variables that are derived from different differentials and explain how to exploit this in order to improve the attack complexity. Secondly, we study and exploit how to choose the actual value for so-called probabilistic neutral bits optimally. Because of the limited influence of these key bits on the computation, in the usual attack approach, these are fixed to a constant value, often zero for simplicity. As we will show, despite the fact that their influence is limited, the constant can be chosen in significantly better ways, and intriguingly, zero is the worst choice. Using this, we propose the first-ever attack on 7.5-round of $128$-bit key version of Salsa20. Also, we provide improvements in the attack against the 8-round of $256$-bit key version of Salsa20 and the 7-round of $128$-bit key version of Salsa20.

## 2024/1364

* Title: FLIP-and-prove R1CS
* Authors: Anca Nitulescu, Nikitas Paslis, Carla Ràfols
* [Permalink](https://eprint.iacr.org/2024/1364)
* [Download](https://eprint.iacr.org/2024/1364.pdf)

### Abstract

In this work, we consider the setting where one or more users with low computational resources would lie to outsource the task of proof generation for SNARKs to one external entity, named Prover. We study the scenario in which Provers have access to all statements and witnesses to be proven beforehand. We take a different approach to proof aggregation and design a new protocol that reduces simultaneously proving time and communication complexity, without going through recursive proof composition.
Our two main contributions: We first design FLIP, a communication efficient folding scheme where we apply the Inner Pairing Product Argument to fold R1CS instances of the same language into a single relaxed R1CS instance. Then, any proof system for relaxed R1CS language can be applied to prove the final instance. As a second contribution, we build a novel variation of Groth16 with the same communication complexity for relaxed R1CS and two extra pairings for verification, with an adapted trusted setup.
Compared to SnarkPack - a prior solution addressing scaling for multiple Groth16 proofs - our scheme improves in prover complexity by orders of magnitude, if we consider the total cost to generated the SNARK proofs one by one and the aggregation effort.
An immediate application of our solution is Filecoin, a decentralized storage network based on incentives that generates more than 6 million SNARKs for large circuits of 100 million constraints per day.

## 2024/1365

* Title: High-Throughput GPU Implementation of Dilithium Post-Quantum Digital Signature
* Authors: Shiyu Shen, Hao Yang, Wangchen Dai, Hong Zhang, Zhe Liu, Yunlei Zhao
* [Permalink](https://eprint.iacr.org/2024/1365)
* [Download](https://eprint.iacr.org/2024/1365.pdf)

### Abstract

Digital signatures are fundamental building blocks in various protocols to provide integrity and authenticity. The development of the quantum computing has raised concerns about the security guarantees aﬀorded by classical signature schemes. CRYSTALS-Dilithium is an eﬃcient post-quantum digital signature scheme based on lattice cryptography and has been selected as the primary algorithm for standardization by the National Institute of Standards and Technology. In this work, we present a high-throughput GPU implementation of Dilithium. For individual operations, we employ a range of computational and memory optimizations to overcome sequential constraints, reduce memory usage and IO latency, address bank conﬂicts, and mitigate pipeline stalls. This results in high and balanced compute throughput and memory throughput for each operation. In terms of concurrent task processing, we leverage task-level batching to fully utilize parallelism and implement a memory pool mechanism for rapid memory access. We propose a dynamic task scheduling mechanism to improve multiprocessor occupancy and signiﬁcantly reduce execution time. Furthermore, we apply asynchronous computing and launch multiple streams to hide data transfer latencies and maximize the computing capabilities of both CPU and GPU. Across all three security levels, our GPU implementation achieves over 160× speedups for signing and over 80× speedups for veriﬁcation on both commercial and server-grade GPUs. This achieves microsecond-level amortized execution times for each task, oﬀering a high-throughput and quantum-resistant solution suitable for a wide array of applications in real systems.

## 2024/1366

* Title: Adaptive Successive Over-Relaxation Method for a Faster Iterative Approximation of Homomorphic Operations
* Authors: Jungho Moon, Zhanibek Omarov, Donghoon Yoo, Yongdae An, Heewon Chung
* [Permalink](https://eprint.iacr.org/2024/1366)
* [Download](https://eprint.iacr.org/2024/1366.pdf)

### Abstract

Homomorphic encryption is a cryptographic technique that enables arithmetic
operations to be performed on encrypted data. However, word-wise fully
homomorphic encryption schemes, such as BGV, BFV, and CKKS schemes, only
support addition and multiplication operations on ciphertexts. This limitation
makes it challenging to perform non-linear operations directly on the
encrypted data. To address this issue, prior research has proposed efficient
approximation techniques that utilize iterative methods, such as functional
composition, to identify optimal polynomials. These approximations are
designed to have a low multiplicative depth and a reduced number of
multiplications, as these criteria directly impact the performance of the
approximated operations.

In this paper, we propose a novel method, named as adaptive successive
over-relaxation (aSOR), to further optimize the approximations used in
homomorphic encryption schemes. Our experimental results show that the aSOR
method can significantly reduce the computational effort required for these
approximations, achieving a reduction of 2–9 times compared to state-of-the-art
methodologies. We demonstrate the effectiveness of the aSOR method by applying
it to a range of operations, including sign, comparison, ReLU, square root,
reciprocal of m-th root, and division. Our findings suggest that the aSOR method
can greatly improve the efficiency of homomorphic encryption for performing
non-linear operations.

## 2024/1367

* Title: A Better Kyber Butterfly for FPGAs
* Authors: Jonas Bertels, Quinten Norga, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2024/1367)
* [Download](https://eprint.iacr.org/2024/1367.pdf)

### Abstract

Kyber was selected by NIST as a Post-Quantum
Cryptography Key Encapsulation Mechanism standard. This
means that the industry now needs to transition and adopt
these new standards. One of the most demanding operations in
Kyber is the modular arithmetic, making it a suitable target for
optimization. This work offers a novel modular reduction design
with the lowest area on Xilinx FPGA platforms. This novel design,
through K-reduction and LUT-based reduction, utilizes 49 LUTs
and 1 DSP as opposed to Xing and Li’s 2021 CHES design
requiring 90 LUTs and 1 DSP for one modular multiplication.
Our design is the smallest modular multiplier reported as of
today.

## 2024/1368

* Title: Tightly Secure Non-Interactive BLS Multi-Signatures
* Authors: Renas Bacho, Benedikt Wagner
* [Permalink](https://eprint.iacr.org/2024/1368)
* [Download](https://eprint.iacr.org/2024/1368.pdf)

### Abstract

Due to their simplicity, compactness, and algebraic structure, BLS signatures are among the most widely used signatures in practice. For example, used as multi-signatures, they are integral in Ethereum's proof-of-stake consensus. From the perspective of concrete security, however, BLS (multi-)signatures suffer from a security loss linear in the number of signing queries. It is well-known that this loss can not be avoided using current proof techniques.

In this paper, we introduce a new variant of BLS multi-signatures that achieves tight security while remaining fully compatible with regular BLS. In particular, our signatures can be seamlessly combined with regular BLS signatures, resulting in regular BLS signatures. Moreover, it can easily be implemented using existing BLS implementations in a black-box way. Our scheme is also one of the most efficient non-interactive multi-signatures, and in particular more efficient than previous tightly secure schemes. We demonstrate the practical applicability of our scheme by showing how proof-of-stake protocols that currently use BLS can adopt our variant for fully compatible opt-in tight security.

## 2024/1369

* Title: AGATE: Augmented Global Attested Trusted Execution in the Universal Composability framework
* Authors: Lorenzo Martinico, Markulf Kohlweiss
* [Permalink](https://eprint.iacr.org/2024/1369)
* [Download](https://eprint.iacr.org/2024/1369.pdf)

### Abstract

A Trusted Execution Environment (TEE) is a new type of security technology, implemented by CPU manufacturers, which guarantees integrity and confidentiality on a restricted execution environment to any remote verifier. TEEs are deployed on various consumer and commercial hardwareplatforms, and have been widely adopted as a component in the design of cryptographic protocols both theoretical and practical.

Within the provable security community, the use of TEEs as a setup assumption has converged to a standard ideal definition in the Universal Composability setting ($G_\mathsf{att}$, defined by Pass et al., Eurocrypt '17). However, it is unclear whether any real TEE design can actually implement this, or whether the diverse capabilities of today's TEE implementations will in fact converge to a single standard. Therefore, it is necessary for cryptographers and protocol designers to specify what assumptions are necessary for the TEE they are using to support the correctness and security of their protocol.

To this end, this paper provides a more careful treatment of trusted execution than the existing literature, focusing on the capabilities of enclaves and adversaries. Our goal is to provide meaningful patterns for comparing different classes of TEEs , particularly how a weaker TEE functionality can UC-emulate a stronger one given an appropriate mechanism to bridge the two. We introduce a new, ``modular'' definition of TEEsthat captures a broad range of pre-existing functionalities defined in the literature while maintaining their high level of abstraction. While our goal is not directly to model implementations of specific commercial TEE providers, our modular definition provides a way to capture more meaningful and realistic hardware capabilities. We provide a language to characterise TEE capabilities along the following terms:
- a set of trusted features available to the enclave;
- the set of allowed attacks for malicious interactions with the enclaves;
- the contents of attestation signatures.
We then define various possible ideal modular $G_\mathsf{att}$ functionality instantiations that capture existing variants in the literature, and provide generic constructions to implement stronger enclave functionalities from an existing setup. Finally, we conclude the paper with a simple example of how to protect against rollback attacks given access to a trusted storage feature.

## 2024/1370

* Title: ML based Improved Differential Distinguisher with High Accuracy: Application to GIFT-128 and ASCON
* Authors: Tarun Yadav, Manoj Kumar
* [Permalink](https://eprint.iacr.org/2024/1370)
* [Download](https://eprint.iacr.org/2024/1370.pdf)

### Abstract

In recent years, ML based differential distinguishers have been explored and compared with the classical methods. Complexity of a key recovery attack on block ciphers is calculated using the probability of a differential distinguisher provided by classical methods. Since theoretical computations suffice to calculate the data complexity in these cases, so there seems no restrictions on the practical availability of computational resources to attack a block cipher using classical methods. However, ML based differential cryptanalysis is based on the machine learning model that uses encrypted data to learn its features using available compute power. This poses a restriction on the accuracy of ML distinguisher for increased number of rounds and ciphers with large block size. Moreover, we can still construct the distinguisher but the accuracy becomes very low in such cases. In this paper, we present a new approach to construct the differential distinguisher with high accuracy using the existing ML based distinguisher of low accuracy. This approach outperforms all existing approaches with similar objective. We demonstrate our method to construct the high accuracy ML based distinguishers for GIFT-128 and ASCON permutation. For GIFT-128, accuracy of 7-round distinguisher is increased to 98.8% with $2^{9}$ data complexity. For ASCON, accuracy of 4-round distinguisher is increased to 99.4% with $2^{18}$ data complexity. We present the first ML based distinguisher for 8 rounds of GIFT-128 using the differential-ML distinguisher presented in Latincrypt-2021. This distinguisher is constructed with 99.8% accuracy and $2^{18}$ data complexity.

## 2024/1371

* Title: PIGEON: A Framework for Private Inference of Neural Networks
* Authors: Christopher Harth-Kitzerow, Yongqin Wang, Rachit Rajat, Georg Carle, Murali Annavaram
* [Permalink](https://eprint.iacr.org/2024/1371)
* [Download](https://eprint.iacr.org/2024/1371.pdf)

### Abstract

Privacy-Preserving Machine Learning is one of the most relevant use cases for Secure Multiparty Computation (MPC). While private training of large neural networks such as VGG-16 or ResNet-50 on state-of-the-art datasets such as Imagenet is still out of reach, given the performance overhead of MPC, private inference is starting to achieve practical runtimes. However, we show that in contrast to plaintext machine learning, the usage of GPU acceleration for both linear and nonlinear neural network layers is actually counterproductive in PPML and leads to performance and scaling penalties. This can be observed by slow ReLU performance, high GPU memory requirements, and inefficient batch processing in state-of-the-art PPML frameworks, which hinders them from scaling to multiple images per second inference throughput and more than eight images per batch on ImageNet.
To overcome these limitations, we propose PIGEON, an open-source framework for Private Inference of Neural Networks. PIGEON utilizes a novel ABG programming model that switches between \underline{A}rithmetic vectorization, \underline{B}itslicing, and \underline{G}PU offloading depending on the MPC-specific computation required by each layer.
Compared to the state-of-the-art PPML framework Piranha, PIGEON achieves two orders of magnitude improvements in ReLU throughput, reduces peak GPU memory utilization by one order of magnitude, and scales better with large batch size. This translates to one to two orders of magnitude improvements in throughput for large ImageNet batch sizes (e.g. 192) and more than 70\% saturation of a 25 Gbit/s network.

Date	Sujet	#		Auteur
2 Sep 24	[digest] 2024 Week 35	1		IACR ePrint Archive