[digest] 2023 Week 48

[IACR ePrint Archive]

## In this issue

1. [2023/1822] Rectangular Attack on VOX
2. [2023/1823] PQC-NN: Post-Quantum Cryptography Neural Network
3. [2023/1824] Learning with Errors over Group Rings Constructed ...
4. [2023/1825] Unclonable Cryptography in the Plain Model
5. [2023/1826] Load-Balanced Server-Aided MPC in Heterogeneous ...
6. [2023/1827] Key Exchange in the Post-Snowden Era: UC Secure ...
7. [2023/1828] Sender-Anamorphic Encryption Reformulated: ...
8. [2023/1829] End-to-End Encrypted Zoom Meetings: Proving ...
9. [2023/1830] Vector Commitments with Efficient Updates
10. [2023/1831] A CP-based Automatic Tool for Instantiating ...
11. [2023/1832] A Note On the Universality of Black-box MKtP Solvers
12. [2023/1833] Cryptanalysis of QARMAv2
13. [2023/1834] BBB PRP Security of the Lai-Massey Mode
14. [2023/1835] ID-CAKE: Identity-based Cluster Authentication and ...
15. [2023/1836] An Incremental PoSW for General Weight Distributions
16. [2023/1837] More forging (and patching) of tropical signatures
17. [2023/1838] Quantifying risks in cryptographic selection processes
18. [2023/1839] Ring-LWE Hardness Based on Ideals of Hidden Orders ...
19. [2023/1840] Unconditionally secure quantum commitments with ...
20. [2023/1841] Unclonable Cryptography with Unbounded Collusions
21. [2023/1842] Leverage Staking with Liquid Staking Derivatives ...
22. [2023/1843] Zero-day vulnerability prevention with recursive ...
23. [2023/1844] Unconditionally Secure Commitments with Quantum ...
24. [2023/1845] Efficient Issuer-Hiding Authentication, Application ...
25. [2023/1846] New Security Proofs and Complexity Records for ...
26. [2023/1847] Cycle Structure and Observability of Two Types of ...
27. [2023/1848] Breach Extraction Attacks: Exposing and Addressing ...
28. [2023/1849] Lattice-based Programmable Hash Functions and ...
29. [2023/1850] Accurate Score Prediction for Dual-Sieve Attacks
30. [2023/1851] Quantum Security of the UMTS-AKA Protocol and its ...
31. [2023/1852] Reduction from sparse LPN to LPN, Dual Attack 3.0
32. [2023/1853] Report on evaluation of KpqC candidates
33. [2023/1854] A note on quantum approximate optimization algorithm
34. [2023/1855] Demystifying DeFi MEV Activities in Flashbots Bundle
35. [2023/1856] Optimizing AES Threshold Implementation under the ...

## 2023/1822

* Title: Rectangular Attack on VOX
* Authors: Gilles Macario-Rat, Jacques Patarin, Benoit Cogliati, Jean-Charles Faugère, Pierre-Alain Fouque, Louis Gouin, Robin Larrieu, Brice Minaud
* [Permalink](https://eprint.iacr.org/2023/1822)
* [Download](https://eprint.iacr.org/2023/1822.pdf)

### Abstract

VOX has been submitted to the NIST Round 1 Additional Signature of the Post-Quantum Signature Competition in June 2023. VOX is a strengthened variant of UOV which uses the Quotient-Ring (QR) setting to reduce the public-key size.
At the end of August 2023, Furue and Ikamatsu posted on the NIST mailing-list a post, indicating that the parameters of VOX can be attacked efficiently using the rectangular attack in the QR setting.

In this note, we explain the attack in the specific case of VOX, we detail the complexity, and show that as Furue and Ikematsu indicated, the attack can be completely avoided by adding one more constraint on the parameter selection. Finally, we show that this constraint does not increase the sizes of the public keys or signature.



## 2023/1823

* Title: PQC-NN: Post-Quantum Cryptography Neural Network
* Authors: Abel C. H. Chen
* [Permalink](https://eprint.iacr.org/2023/1823)
* [Download](https://eprint.iacr.org/2023/1823.pdf)

### Abstract

In recent years, quantum computers and Shor’s quantum algorithm have been able to effectively solve NP (Non-deterministic Polynomial-time) problems such as prime factorization and discrete logarithm problems, posing a threat to current mainstream asymmetric cryptography, including RSA and Elliptic Curve Cryptography (ECC). As a result, the National Institute of Standards and Technology (NIST) in the United States call for Post-Quantum Cryptography (PQC) methods that include lattice-based cryptography methods, code-based cryptography methods, multivariate cryptography methods, and hash-based cryptography methods for resisting quantum computing attacks. Therefore, this study proposes a PQC neural network (PQC-NN) that maps a code-based PQC method to a neural network structure and enhances the security of ciphertexts with non-linear activation functions, random perturbation of ciphertexts, and uniform distribution of ciphertexts. The main innovations of this study include: (1) constructing a neural network structure that complies with code-based PQC, where the weight sets between the input layer and the ciphertext layer can be used as a public key for encryption, and the weight sets between the ciphertext layer and the output layer can be used as a private key for decryption; (2) adding random perturbations to the ciphertext layer, which can be removed during the decryption phase to restore the original plaintext; (3) constraining the output values of the ciphertext layer to follow a uniform distribution with a significant similarity by adding the cumulative distribution function (CDF) values of the chi-square distribution to the loss function, ensuring that the neural network produces sufficiently uniform distribution for the output values of the ciphertext layer. In practical experiments, this study uses cellular network signals as a case study to demonstrate that encryption and decryption can be performed by the proposed PQC neural network with the uniform distribution of ciphertexts. In the future, the proposed PQC neural network could be applied to various applications.



## 2023/1824

* Title: Learning with Errors over Group Rings Constructed by Semi-direct Product
* Authors: Jiaqi Liu, Fang-Wei Fu
* [Permalink](https://eprint.iacr.org/2023/1824)
* [Download](https://eprint.iacr.org/2023/1824.pdf)

### Abstract

The Learning with Errors (LWE) problem has been widely utilized as a foundation for numerous cryptographic tools over the years. In this study, we focus on an algebraic variant of the LWE problem called Group ring LWE (GR-LWE). We select group rings (or their direct summands) that underlie specific families of finite groups constructed by taking the semi-direct product of two cyclic groups. Unlike the Ring-LWE problem described in \cite{lyubashevsky2010ideal}, the multiplication operation in the group rings considered here is non-commutative. As an extension of Ring-LWE, it maintains computational hardness and can be potentially applied in many cryptographic scenarios. In this paper, we present two polynomial-time quantum reductions. Firstly, we provide a quantum reduction from the worst-case shortest independent vectors problem (SIVP) in ideal lattices with polynomial approximate factor to the search version of GR-LWE. This reduction requires that the underlying group ring possesses certain mild properties; Secondly, we present another quantum reduction for two types of group rings, where the worst-case SIVP problem is directly reduced to the (average-case) decision GR-LWE problem. The pseudorandomness of GR-LWE samples guaranteed by this reduction can be consequently leveraged to construct semantically secure public-key cryptosystems.



## 2023/1825

* Title: Unclonable Cryptography in the Plain Model
* Authors: Céline Chevalier, Paul Hermouet, Quoc-Huy Vu
* [Permalink](https://eprint.iacr.org/2023/1825)
* [Download](https://eprint.iacr.org/2023/1825.pdf)

### Abstract

By leveraging the no-cloning principle of quantum mechanics, unclonable cryptography enables us to achieve novel cryptographic protocols that are otherwise impossible classically. Two most notable examples of unclonable cryptography are quantum copy-protection and unclonable encryption. Despite receiving a lot of attention in recent years, two important open questions still remain: copy- protection for point functions in the plain model, which is usually considered as feasibility demonstration, and unclonable encryption with unclonable indistinguishability security in the plain model.
In this work, by relying on previous works of Coladangelo, Liu, Liu, and Zhandry (Crypto’21) and Culf and Vidick (Quantum’22), we establish a new monogamy-of-entanglement property for subspace coset states, which allows us to obtain the following new results:
• We show that copy-protection of point functions exists in the plain model, with different challenge distributions (including arguably the most natural ones).
• We show, for the first time, that unclonable encryption with unclonable indistinguishability security exists in the plain model.



## 2023/1826

* Title: Load-Balanced Server-Aided MPC in Heterogeneous Computing
* Authors: Yibiao Lu, Bingsheng Zhang, Kui Ren
* [Permalink](https://eprint.iacr.org/2023/1826)
* [Download](https://eprint.iacr.org/2023/1826.pdf)

### Abstract

Most existing MPC protocols consider the homogeneous setting, where all the MPC players are assumed to have identical communication and computation resources. In practice, the weakest player often becomes the bottleneck of the entire MPC protocol execution. In this work, we initiate the study of so-called load-balanced MPC in the heterogeneous computing. A load-balanced MPC protocol can adjust the workload of each player accordingly to maximize the overall resource utilization. In particular, we propose new notions called composite circuit and composite garbling scheme, and construct two efficient server-aided protocols with malicious security and semi-honest security, respectively. Our maliciously secure protocol is over 400$\times$ faster than the authenticated garbling protocol (CCS'17); our semi-honest protocol is up to 173$\times$ faster than the optimized BMR protocol (CCS'16).



## 2023/1827

* Title: Key Exchange in the Post-Snowden Era: UC Secure Subversion-Resilient PAKE
* Authors: Suvradip Chakraborty, Lorenzo Magliocco, Bernardo Magri, Daniele Venturi
* [Permalink](https://eprint.iacr.org/2023/1827)
* [Download](https://eprint.iacr.org/2023/1827.pdf)

### Abstract

Password-Authenticated Key Exchange (PAKE) allows two parties to establish a common high-entropy secret from a possibly low-entropy pre-shared secret such as a password. In this work, we provide the first PAKE protocol with subversion resilience in the framework of universal composability (UC), where the latter roughly means that UC security still holds even if one of the two parties is malicious and the honest party's code has been subverted (in an undetectable manner).

We achieve this result by sanitizing the PAKE protocol from oblivious transfer (OT) due to Canetti et al. (PKC'12) via cryptographic reverse firewalls in the UC framework (Chakraborty et al., EUROCRYPT'22). This requires new techniques, which help us uncover new cryptographic primitives with sanitation-friendly properties along the way (such as OT, dual-mode cryptosystems, and signature schemes).

As an additional contribution, we delve deeper in the backbone of communication required in the subversion-resilient UC framework, extending it to the unauthenticated setting, in line with the work of Barak et al. (CRYPTO'05).



## 2023/1828

* Title: Sender-Anamorphic Encryption Reformulated: Achieving Robust and Generic Constructions
* Authors: Yi Wang, Rongmao Chen, Xinyi Huang, Moti Yung
* [Permalink](https://eprint.iacr.org/2023/1828)
* [Download](https://eprint.iacr.org/2023/1828.pdf)

### Abstract

Motivated by the violation of two fundamental assumptions in secure communication - receiver-privacy and sender-freedom - by a certain entity referred to as ``the dictator'', Persiano et al. introduced the concept of Anamorphic Encryption (AME) for public key cryptosystems (EUROCRYPT 2022). Specifically, they presented receiver/sender-AME, directly tailored to scenarios where receiver privacy and sender freedom assumptions are compromised, respectively. In receiver-AME, entities share a double key to communicate in anamorphic fashion, raising concerns about the online distribution of the double key without detection by the dictator. The sender-AME with no shared secret is a potential candidate for key distribution. However, the only such known schemes (i.e., LWE and Dual LWE encryptions) suffer from an intrinsic limitation and cannot achieve reliable distribution.

Here, we reformulate the sender-AME, present the notion of $\ell$-sender-AME and formalize the properties of (strong) security and robustness. Robustness refers to guaranteed delivery of duplicate messages to the intended receiver, ensuring that decrypting normal ciphertexts in an anamorphic way or decrypting anamorphic ciphertexts with an incorrect duplicate secret key results in an explicit abort signal. We first present a simple construction for pseudo-random and robust public key encryption that shares the similar idea of public-key stegosystem by von Ahn and Hopper (EUROCRYPT 2004). Then, inspired by Chen et al.'s malicious algorithm-substitution attack (ASA) on key encapsulation mechanisms (KEM) (ASIACRYPT 2020), we give a generic construction for hybrid PKE with special KEM that encompasses well-known schemes, including ElGamal and Cramer-Shoup cryptosystems.

The constructions of $\ell$-sender-AME motivate us to explore the relations between AME, ASA on PKE, and public-key stegosystem. The results show that a strongly secure $\ell$-sender-AME is such a strong primitive that implies reformulated receiver-AME, public-key stegosystem, and generalized ASA on PKE. By expanding the scope of sender-anamorphic encryption and establishing its robustness, as well as exploring the connections among existing notions, we advance secure communication protocols under challenging conditions.



## 2023/1829

* Title: End-to-End Encrypted Zoom Meetings: Proving Security and Strengthening Liveness
* Authors: Yevgeniy Dodis, Daniel Jost, Balachandar Kesavan, Antonio Marcedone
* [Permalink](https://eprint.iacr.org/2023/1829)
* [Download](https://eprint.iacr.org/2023/1829.pdf)

### Abstract

In May 2020, Zoom Video Communications, Inc. (Zoom) announced a multi-step plan to comprehensively support end-to-end encrypted (E2EE) group video calls and subsequently rolled out basic E2EE support to customers in October 2020. In this work we provide the first formal security analysis of Zoom's E2EE protocol, and also lay foundation to the general problem of E2EE group video communication.

We observe that the vast security literature analyzing asynchronous messaging does not translate well to synchronous video calls. Namely, while strong forms of forward secrecy and post compromise security are less important for (typically short-lived) video calls, various liveness properties become crucial. For example, mandating that participants quickly learn of updates to the meeting roster and key, media streams being displayed are recent, and banned participants promptly lose any access to the meeting. Our main results are as follows:

1. Propose a new notion of leader-based continuous group key agreement with liveness, which accurately captures the E2EE properties specific to the synchronous communication scenario.
2. Prove security of the core of Zoom's E2EE meetings protocol in the above well-defined model.
3. Propose ways to strengthen Zoom's liveness properties by simple modifications to the original protocol, which subsequently influenced updates implemented in production.



## 2023/1830

* Title: Vector Commitments with Efficient Updates
* Authors: Ertem Nusret Tas, Dan Boneh
* [Permalink](https://eprint.iacr.org/2023/1830)
* [Download](https://eprint.iacr.org/2023/1830.pdf)

### Abstract

Dynamic vector commitments that enable local updates of opening proofs have applications ranging from verifiable databases with membership changes to stateless clients on blockchains. In these applications, each user maintains a relevant subset of the committed messages and the corresponding opening proofs with the goal of ensuring a succinct global state. When the messages are updated, users are given some global update information and update their opening proofs to match the new vector commitment. We investigate the relation between the size of the update information and the runtime complexity needed to update an individual opening proof. Existing vector commitment schemes require that either the information size or the runtime scale linearly in the number $k$ of updated state elements. We construct a vector commitment scheme that asymptotically achieves both length and runtime that is sublinear in $k$, namely $k^\nu$ and $k^{1-\nu}$ for any $\nu \in (0,1)$. We prove an information-theoretic lower bound on the relation between the update information size and runtime complexity that shows the asymptotic optimality of our scheme. For $\nu = 1/2$, our constructions outperform Verkle commitments by about a factor of $2$ in terms of both the update information size and runtime, but makes use of larger public parameters.



## 2023/1831

* Title: A CP-based Automatic Tool for Instantiating Truncated Differential Characteristics - Extended Version
* Authors: François Delobel, Patrick Derbez, Arthur Gontier, Loïc Rouquette, Christine Solnon
* [Permalink](https://eprint.iacr.org/2023/1831)
* [Download](https://eprint.iacr.org/2023/1831.pdf)

### Abstract

An important criteria to assert the security of a cryptographic primitive is its resistance against differential cryptanalysis. For word-oriented primitives, a common technique to determine the number of rounds required to ensure the immunity against differential distinguishers is to consider truncated differential characteristics and to count the number of active S-boxes. Doing so allows one to provide an upper bound on the probability of the best differential characteristic with a reduced computational cost. However, in order to design very efficient primitives, it might be needed to evaluate the probability more accurately. This is usually done in a second step, during which one tries to instantiate truncated differential characteristics with actual values and computes its corresponding probability. This step is usually done either with ad-hoc algorithms or with CP, SAT or MILP models that are solved by generic solvers. In this paper, we present a generic tool for automatically generating these models to handle all word-oriented ciphers. Furthermore the running times to solve these models are very competitive
with all the previous dedicated approaches.



## 2023/1832

* Title: A Note On the Universality of Black-box MKtP Solvers
* Authors: Noam Mazor, Rafael Pass
* [Permalink](https://eprint.iacr.org/2023/1832)
* [Download](https://eprint.iacr.org/2023/1832.pdf)

### Abstract

The relationships between various meta-complexity problems are not well understood in the worst-case regime, including whether the search version is harder than the decision version, whether the hardness scales with the ``threshold", and how the hardness of different meta complexity problems relate to one another, and to the task of function inversion.

In this note, we present resolutions to some of these questions with respect to the \emph{black-box} analog of these problems. In more detail, let $MK^t_MP[s]$ denote the language consisting of strings $x$ with $K_{M}^t(x) < s(|x|)$, where $K_M^t(x)$ denotes the $t$-bounded Kolmogorov complexity of $x$ with $M$ as the underlying (Universal) Turing machine, and let $search-MK^t_MP[s]$ denote the search version of the same problem.

We show that if there for every Universal Turing machine $U$ there exists a $2^{\alpha n}poly(n)$-size $U$-oracle aided circuit deciding $MK^t_UP [n-O(1)]$, then for every function $s$, and every not necessarily universal Turing machine $M$, there exists a $2^{\alpha s(n)}poly(n)$ size $M$-oracle aided circuit solving $search-MK^t_MP[s(n)]$; this in turn yields circuits of roughly the same size for both the Minimum Circuit Size Problem (MCSP), and the function inversion problem, as they can be thought of as instantiating $MK^t_MP$ with particular choices of (a non universal) TMs $M$ (the circuit emulator for the case of MCSP, and the function evaluation in the case of function inversion).

As a corollary of independent interest, we get that the complexity of black-box function inversion is (roughly) the same as the complexity of black-box deciding $MK^t_UP[n-O(1)]$ for any universal TM $U$; that is, also in the worst-case regime, black-box function inversion is ``equivalent" to black-box deciding $MKtUP$.



## 2023/1833

* Title: Cryptanalysis of QARMAv2
* Authors: Hosein Hadipour, Yosuke Todo
* [Permalink](https://eprint.iacr.org/2023/1833)
* [Download](https://eprint.iacr.org/2023/1833.pdf)

### Abstract

QARMAv2 is a general-purpose and hardware-oriented family of lightweight tweakable block ciphers (TBCs) introduced in ToSC 2023. QARMAv2, as a redesign of QARMA with a longer tweak and tighter security margins, is also designed to be suitable for cryptographic memory protection and control flow integrity. The designers of QARMAv2 provided a relatively comprehensive security analysis in the design specification, e.g., some bounds for the number of attacked rounds in differential and boomerang analysis, together with some concrete impossible differential, zero-correlation, and integral distinguishers. As one of the first third-party cryptanalysis of QARMAv2, Hadipour et al. significantly improved the integral distinguishers of QARMAv2 and provided the longest concrete distinguishers of QARMAv2 up to now. However, they provided no key recovery attack based on their distinguishers.

This paper delves into the cryptanalysis of QARMAv2 to enhance our understanding of its security. Given that the integral distinguishers of QARMAv2 are the longest concrete distinguishers for this cipher so far, we focus on integral attack. To this end, we first further improve the automatic tool introduced by Hadipour et al., for finding integral distinguishers of TBCs following the TWEAKEY framework. This new tool exploits the MixColumns property of QARMAv2 to find integral distinguishers more suitable for key recovery attacks. Then, we combine several techniques for integral key recovery attacks, e.g., Meet-in-the-middle and partial-sum techniques to build a fine-grained integral key recovery attack on QARMAv2. Notably, we demonstrate how to leverage the low data complexity of the integral distinguishers of QARMAv2 to reduce the memory complexity of the meet-in-the-middle technique. As a result, we managed to propose the first concrete key recovery attacks on reduced-round versions of QARMAv2 by attacking 13 rounds of QARMAv2-64-128 with a single tweak block, 14 rounds of QARMAv2-64-128 with two independent tweak blocks, and 16 rounds of QARMAv2-128-256 with two independent tweak blocks. Our attacks do not compromise the claimed security of QARMAv2, but they shed more light on the cryptanalysis of this cipher.



## 2023/1834

* Title: BBB PRP Security of the Lai-Massey Mode
* Authors: Ritam Bhaumik, Mohammad Amin Raeisi
* [Permalink](https://eprint.iacr.org/2023/1834)
* [Download](https://eprint.iacr.org/2023/1834.pdf)

### Abstract

In spite of being a popular technique for designing block ciphers, Lai-Massey networks have received considerably less attention from a security analysis point-of-view than Feistel networks and Substitution-Permutation networks. In this paper we study the beyond-birthday-bound (BBB) security of Lai-Massey networks with independent random round functions against chosen-plaintext adversaries. Concretely, we show that five rounds are necessary and sufficient to achieve BBB security.



## 2023/1835

* Title: ID-CAKE: Identity-based Cluster Authentication and Key Exchange Scheme for Message Broadcasting and Batch Verification in VANETs
* Authors: Apurva K Vangujar, Alia Umrani, Paolo Palmieri
* [Permalink](https://eprint.iacr.org/2023/1835)
* [Download](https://eprint.iacr.org/2023/1835.pdf)

### Abstract

Vehicle Ad Hoc Networks (VANETs) play a pivotal role in intelligent transportation systems, offering dynamic communication between vehicles, Road Side Units (RSUs), and the internet. Given the open-access nature of VANETs and the associated threats, such as impersonation and privacy violations, ensuring the security of these communications is of utmost importance.
This paper presents the Identity-based Cluster Authentication and Key Exchange (ID-CAKE) scheme, a new approach to address security challenges in VANETs. The ID-CAKE scheme integrates the Cluster Consensus Identity-based Identification (CCIBI) with Zero-Knowledge (ZK) proofs and the Identity-based Multireceiver Key Exchange Mechanism (ID-mKEM) signature scheme. This integration provides robust authorization via CCIBI, while ID-mKEM signatures ensure message integrity, and guarantee both non-repudiation and unforgeability through mKEM for message broadcasting. The scheme employs a novel three-party ZK proof for batch verification using mKEM, which significantly reduces computational burdens. Our scheme also ensures anonymity and unlinkability by introducing pseudo-identities to all users in the cluster. The rigorous security proofs provided confirm the resilience of the ID-CAKE scheme against potential attacks, adhering to the different scenarios, against the hardness of the elliptic curve computational Diffie-Hellman under the random oracle model. The ID-CAKE scheme establishes a robust security framework for VANETs, and its introduction highlights potential pathways for future exploration in the realm of VANET security.



## 2023/1836

* Title: An Incremental PoSW for General Weight Distributions
* Authors: Hamza Abusalah, Valerio Cini
* [Permalink](https://eprint.iacr.org/2023/1836)
* [Download](https://eprint.iacr.org/2023/1836.pdf)

### Abstract

A proof of sequential work (PoSW) scheme allows the prover to convince a verifier that it computed a certain number of computational steps sequentially.
Very recently, graph-labeling PoSW schemes, found applications in light-client blockchain protocols, most notably bootstrapping. A bootstrapping protocol allows a light client, with minimal information about the blockchain, to hold a commitment to its stable prefix. An incremental PoSW (iPoSW) scheme allows the prover to non-trivially increment proofs: given $\chi,\pi_1$ and integers $N_1,N_2$ such that $\pi_1$ is a valid proof for $N_1$, it generates a valid proof $\pi$ for $N_1+N_2$.
In this work, we construct an iPoSW scheme based on the skiplist-based PoSW scheme of Abusalah et al. and prove its security in the random oracle model by employing the powerful on-the-fly sampling technique of Döttling et al. Moreover, unlike the iPoSW scheme of Döttling et al., ours is the first iPoSW scheme which is suitable for constructing incremental non-interactive arguments of chain knowledge (SNACK) schemes, which are at the heart of space and time efficient blockchain light-client protocols. In particular, our scheme works for general weight distributions, which we characterize as incrementally sampleable distributions. Our general treatment recovers the distribution underlying the scheme of Döttling et al. as well as the distribution underlying SNACK-enabled bootstrapping application as special cases. In realizing our general construction, we develop a new on-the-fly sampling technique.



## 2023/1837

* Title: More forging (and patching) of tropical signatures
* Authors: Daniel R. L. Brown, Chris Monico
* [Permalink](https://eprint.iacr.org/2023/1837)
* [Download](https://eprint.iacr.org/2023/1837.pdf)

### Abstract

Panny [3] described how to forge the “tropical signatures” proposed by Chen, Grigoriev and Shpilrain [1]. (These signatures are loosely related to the NP-complete problem of factoring tropical polynomials).
We describe more methods to forge these tropical signatures. We also describe some patches that thwart all but one of these forgery methods (which we summarize as re-hashing an honest signature).



## 2023/1838

* Title: Quantifying risks in cryptographic selection processes
* Authors: Daniel J. Bernstein
* [Permalink](https://eprint.iacr.org/2023/1838)
* [Download](https://eprint.iacr.org/2023/1838.pdf)

### Abstract

There appears to be a widespread belief that some processes of selecting cryptosystems are less risky than other processes. As a case study of quantifying the difference in risks, this paper compares the currently-known-failure rates of three large groups of cryptosystems: (1) the round-1 submissions to the NIST Post-Quantum Cryptography Standardization Project, (2) the round-1 submissions not broken by the end of round 1, and (3) the round-1 submissions selected by NIST for round 2 of the same project. These groups of cryptosystems turn out to have currently-known-failure rates that are strikingly high, and that include statistically significant differences across the groups, not matching the pattern of differences that one might expect. Readers are cautioned that the actual failure rates could be much higher than the currently-known-failure rates.



## 2023/1839

* Title: Ring-LWE Hardness Based on Ideals of Hidden Orders of Number Fields
* Authors: Charanjit S Jutla, Chengyu Lin
* [Permalink](https://eprint.iacr.org/2023/1839)
* [Download](https://eprint.iacr.org/2023/1839.pdf)

### Abstract

We extend the known pseudorandomness of Ring-LWE to be based on lattices that do not correspond to any ideal of any order in the underlying number field. In earlier works of Lyubashevsky et al (EUROCRYPT 2010) and Peikert et al (STOC 2017), the hardness of RLWE was based on ideal lattices of ring of integers of number fields, which are known to be Dedekind domains. While these works extended Regev's (STOC 2005) quantum polynomial-time reduction for LWE, thus allowing more efficient and more structured cryptosystems, the additional algebraic structure of ideals of Dedekind domains leaves open the possibility that such ideal lattices are not as hard as general lattices.

In this work we show that hardness of $q$-Ring-LWE can be based on worst-case hardness of ideal lattices in arbitrary orders $O$, as long as the order $O$ satisfies the property that $\frac{1}{m}\cdot O$ contains the ring of integers, for some $m$ co-prime to $q$. Further, the hard lattice problems need not be given the order $O$ itself as input. The reduction requires that the noise be a factor $m$ more than the original Ring-LWE reduction. We also show that for the power-of-two cyclotomic number fields, there exist orders with $m=4$ such that non-trivial ideals of the order, which are not contained in the conductor, are non-invertible.

Another reduction shows that hardness of $q$-Ring-LWE can be based on worst-case hardness of lattices that correspond to sum of ideal-lattices in arbitrary and different orders in the number field, as long as the (set of) orders $\{O_i\}$ satisfy the property that $\frac{1}{m}\cdot O_i$ contains the ring of integers, for some $m$ co-prime to $q$. We also show that for the power-of-two cyclotomic number fields, there exist orders $O_1, O_2$ with $m=8$ such that there are ideals $I_1, I_2$ of $O_1, O_2$ resp. with $I_1+ I_2$ not an ideal of any order in the number field.



## 2023/1840

* Title: Unconditionally secure quantum commitments with preprocessing
* Authors: Luowen Qian
* [Permalink](https://eprint.iacr.org/2023/1840)
* [Download](https://eprint.iacr.org/2023/1840.pdf)

### Abstract

We demonstrate how to build computationally secure commitment schemes with the aid of quantum auxiliary inputs without unproven complexity assumptions. Furthermore, the quantum auxiliary input can be prepared either (1) efficiently through a trusted setup similar to the classical common random string model, or (2) strictly between the two involved parties in uniform exponential time. Classically this remains impossible without first proving $\mathsf{P} \neq \mathsf{NP}$.



## 2023/1841

* Title: Unclonable Cryptography with Unbounded Collusions
* Authors: Alper Çakan, Vipul Goyal
* [Permalink](https://eprint.iacr.org/2023/1841)
* [Download](https://eprint.iacr.org/2023/1841.pdf)

### Abstract

Quantum no-cloning theorem gives rise to the intriguing possibility of quantum copy protection where we encode a program in a quantum state such that a user in possession of $k$ such states cannot create $k+1$ working copies. Introduced by Aaronson (CCC'09) over a decade ago, copy protection has proven to be notoriously hard to achieve.

In this work, we construct public-key encryption and functional encryption schemes whose secret keys are copy-protected against unbounded collusions in the plain model (i.e. without any idealized oracles), assuming (post-quantum) subexponentially secure $\mathcal{iO}$, one-way functions and LWE. This resolves a long-standing open question of constructing fully collusion-resistant copy-protected functionalities raised by multiple previous works.

Prior to our work, copy-protected functionalities were known only in restricted collusion models where either an a-priori bound on the collusion size was needed, in the plain model with the same assumptions as ours (Liu, Liu, Qian, Zhandry [TCC'22]), or adversary was only prevented from doubling their number of working programs, in a structured quantum oracle model (Aaronson [CCC'09]).

We obtain our results through a novel technique which uses identity-based encryption to construct unbounded collusion resistant copy-protection schemes from $1\to2$ secure schemes. This is analogous to the technique of using digital signatures to construct full-fledged quantum money from single banknote schemes (Lutomirski et al. [ICS'09], Farhi et al. [ITCS'12], Aaronson and Christiano [STOC'12]). We believe our technique is of independent interest.

Along the way, we also construct a puncturable functional encryption scheme whose master secret key can be punctured at all functions $f$ such that $f(m_0) \neq f(m_1)$. This might also be of independent interest.



## 2023/1842

* Title: Leverage Staking with Liquid Staking Derivatives (LSDs): Opportunities and Risks
* Authors: Xihan Xiong, Zhipeng Wang, Xi Chen, William Knottenbelt, Michael Huth
* [Permalink](https://eprint.iacr.org/2023/1842)
* [Download](https://eprint.iacr.org/2023/1842.pdf)

### Abstract

Lido, the leading Liquidity Staking Derivative (LSD) provider on Ethereum, allows users to stake an arbitrary amount of ETH to receive stETH, which can be integrated with Decentralized Finance (DeFi) protocols such as Aave. The composability between Lido and Aave enables a novel strategy called “leverage staking”, where users stake ETH on Lido to acquire stETH, utilize stETH as collateral on Aave to borrow ETH, and then restake the borrowed ETH on Lido. Users can iteratively execute this process to optimize potential returns based on their risk profile.

This paper systematically studies the opportunities and risks associated with leverage staking. We are the first to formalize the stETH-ETH leverage staking strategy within the Lido-Aave ecosystem. Our empirical study identifies 262 leverage staking positions on Ethereum, with an aggregated staking amount of 295,243 ETH (482M USD). We discover that 90.13% of leverage staking positions have achieved higher returns than conventional staking. Furthermore, we perform stress tests to evaluate the risk introduced by leverage staking under extreme conditions. We find that leverage staking significantly amplifies the risk of cascading liquidations. We hope this paper can inform and encourage the development of robust risk management approaches to protect the Lido-Aave LSD ecosystem.



## 2023/1843

* Title: Zero-day vulnerability prevention with recursive feature elimination and ensemble learning
* Authors: Mike Nkongolo Wa Nkongolo
* [Permalink](https://eprint.iacr.org/2023/1843)
* [Download](https://eprint.iacr.org/2023/1843.pdf)

### Abstract

This study focuses on spotting and stopping new types of online threats by improving the UGRansome dataset to detect unusual activity in real-time. By blending different machine learning methods, like naïve tree-based ensemble learning and recursive feature elimination (RFE), the research achieves a high accuracy rate of 97%. Naïve Bayes (NB) stands out as the most effective classifier. The suggested setup, combining gradient boosting (GB) and random forest (RF) with NB, effectively identifies and prevents unknown vulnerabilities in computer systems. UGRansome successfully blocks over 100 kilobits per second (kbps) of harmful online traffic by using details pinpointed by the RFE method, specifically uniform resource locators (URLs). This outperforms existing Intrusion Detection System (IDS) datasets. It's particularly good at stopping secure shell attacks, proving the dataset's usefulness in making networks safer. This research marks significant progress in detecting intrusions. The NB model excels in accuracy, precision, and remembering patterns, especially in identifying new threats. Moreover, the suggested naïve tree-based ensemble model shows outstanding accuracy, standing out as the best-performing technique among all models studied. Applying the UGRansome properties-based rule noticeably changes how traffic is sorted, decreasing unknown traffic while increasing unclassified traffic, which requires more investigation.



## 2023/1844

* Title: Unconditionally Secure Commitments with Quantum Auxiliary Inputs
* Authors: Tomoyuki Morimae, Barak Nehoran, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2023/1844)
* [Download](https://eprint.iacr.org/2023/1844.pdf)

### Abstract

We show the following unconditional results on quantum commitments in two related yet different models:

1. We revisit the notion of quantum auxiliary-input commitments introduced by Chailloux, Kerenidis, and Rosgen (Comput. Complex. 2016) where both the committer and receiver take the same quantum state, which is determined by the security parameter,
as quantum auxiliary inputs. We show that computationally-hiding and statistically-binding quantum auxiliary-input commitments exist unconditionally, i.e., without relying on any unproven assumption, while Chailloux et al. assumed a complexity-theoretic assumption,
${\bf QIP}\not\subseteq{\bf QMA}$. On the other hand, we observe that achieving both statistical hiding and statistical binding at the same time is impossible even in the quantum auxiliary-input setting.
To the best of our knowledge, this is the first example of unconditionally proving computational security of any form of (classical or quantum) commitments for which statistical security is impossible. As intermediate steps toward our construction, we introduce and unconditionally construct post-quantum sparse pseudorandom distributions and quantum auxiliary-input EFI pairs which may be of independent interest.


2. We introduce a new model which we call the common reference quantum state (CRQS) model where both the committer and receiver take the same quantum state that is randomly sampled by an efficient setup algorithm. We unconditionally prove that there exist statistically hiding and statistically binding commitments in the CRQS model, circumventing the impossibility in the plain model.

We also discuss their applications to zero-knowledge proofs, oblivious transfers, and multi-party computations.



## 2023/1845

* Title: Efficient Issuer-Hiding Authentication, Application to Anonymous Credential
* Authors: Olivier Sanders, Jacques Traoré
* [Permalink](https://eprint.iacr.org/2023/1845)
* [Download](https://eprint.iacr.org/2023/1845.pdf)

### Abstract

Anonymous credentials are cryptographic mechanisms enabling users to authenticate themselves with a fine-grained control on the information they leak in the process. They have been the topic of countless papers which have improved the performance of such mechanisms or proposed new schemes able to prove ever-more complex statements about the attributes certified by those credentials. However, whereas these papers have studied in depth the problem of the information leaked by the credential and/or the attributes, almost all of them have surprisingly overlooked the information one may infer from the knowledge of the credential issuer.

In this paper we address this problem by showing how one can efficiently hide the actual issuer of a credential within a set of potential issuers. The novelty of our work is that we do not resort to zero-knowledge proofs but instead we show how one can tweak Pointcheval-Sanders signatures to achieve this issuer-hiding property at a very low cost. This results in an efficient anonymous credential system that indeed provide a complete control of the information leaked in the authentication process. Our construction is moreover modular and can then fit a wide spectrum of applications, notably for Self-Sovereign Identity (SSI) systems.



## 2023/1846

* Title: New Security Proofs and Complexity Records for Advanced Encryption Standard
* Authors: Orhun Kara
* [Permalink](https://eprint.iacr.org/2023/1846)
* [Download](https://eprint.iacr.org/2023/1846.pdf)

### Abstract

Common block ciphers like AES specified by the NIST or KASUMI (A5/3) of GSM are extensively utilized by billions of individuals globally to protect their privacy and maintain confidentiality in daily communications. However, these ciphers lack comprehensive security proofs against the vast majority of known attacks. Currently, security proofs are limited to differential and linear attacks for both AES and KASUMI. For instance, the consensus on the security of AES is not based on formal mathematical proofs but on intensive cryptanalysis over its reduced rounds spanning several decades. In this work, we introduce new security proofs for AES against another attack method: impossible differential (ID) attacks. We classify ID attacks as reciprocal and nonreciprocal ID attacks. We show that sharp and generic lower bounds can be imposed on the data complexities of reciprocal ID attacks on substitution permutation networks. We prove that the minimum data required for a reciprocal ID attack on AES using a conventional ID characteristic is $2^{66}$ chosen plaintexts whereas a nonreciprocal ID attack involves at least $2^{88}$ computational steps. We mount a nonreciprocal ID attack on 6-round AES for 192-bit and 256-bit keys, which requires only $2^{18}$ chosen plaintexts and outperforms the data complexity of any attack. Given its marginal time complexity, this attack does not pose a substantial threat to the security of AES. However, we have made enhancements to the integral attack on 6-round AES, thereby surpassing the longstanding record for the most efficient attack after a period of 23 years.



## 2023/1847

* Title: Cycle Structure and Observability of Two Types of Galois NFSRs
* Authors: Xianghan Wang, Jianghua Zhong, Dongdai Lin
* [Permalink](https://eprint.iacr.org/2023/1847)
* [Download](https://eprint.iacr.org/2023/1847.pdf)

### Abstract

Nonlinear feedback shift registers (NFSRs) are used in many stream ciphers as their main building blocks. One security criterion for the design of a stream cipher is to assure its keystream has a long period. To meet this criterion, the NFSR used in a stream cipher must have a long state cycle. Further, to simultaneously avoid equivalent keys, the keystream's period is not compressed compared to the NFSR's state cycle length, which can be guaranteed if the NFSR is observable in the sense that any two distinct initial states are distinguishable from their resulting output sequences. The cycle structure of a general NFSR remains an open hard problem. Constructing Fibonacci NFSRs with maximum state cycles has therefore attracted much attention, but so far such Fibonacci NFSRs with known feedback functions have been found only for their stage numbers no greater than 33.

Considering that Galois NFSRs may decrease the area and increase the throughput compared to Fibonacci NFSRs, this paper studies two types of $n$-stage Galois NFSRs, whose state transition matrices are circulant matrices with only one nonzero element of 1 in each column. The cycle structure and observability of both types are disclosed using the semi-tensor product based Boolean network approach. In the first type, each Galois NFSR has the state transition matrix, in which the position of the element 1 in the first column is even. It has the maximum state cycle with an arbitrary stage number and an explicit feedback functions. It is observable if and only if its output function is dependent on the first state bit. In the second type, each Galois NFSR has the state transition matrix, in which the position of the element 1 in the first column is $2^m+1$ with positive integer $m\leq n-1$ for the NFSR's stage number $n$. It has $2^m$ cycles of length $2^{n-m}$, and it is observable if its output function is dependent on all the state bits whose indices are no smaller than $n-m+1$.



## 2023/1848

* Title: Breach Extraction Attacks: Exposing and Addressing the Leakage in Second Generation Compromised Credential Checking Services
* Authors: Dario Pasquini, Danilo Francati, Giuseppe Ateniese, Evgenios M. Kornaropoulos
* [Permalink](https://eprint.iacr.org/2023/1848)
* [Download](https://eprint.iacr.org/2023/1848.pdf)

### Abstract

Credential tweaking attacks use breached passwords to generate semantically similar passwords and gain access to victims' services.
These attacks sidestep the first generation of compromised credential checking (C3) services. The second generation of compromised credential checking services, called "Might I Get Pwned" (MIGP), is a privacy-preserving protocol that defends against credential tweaking attacks by allowing clients to query whether a password or a semantically similar variation is present in the server's compromised credentials dataset.
The desired privacy requirements include not revealing the user's entered password to the server and ensuring that no compromised credentials are disclosed to the client.

In this work, we formalize the cryptographic leakage of the MIGP protocol and perform a security analysis to assess its impact on the credentials held by the server. We focus on how this leakage aids breach extraction attacks, where an honest-but-curious client interacts with the server to extract information about the stored credentials. Furthermore, we discover additional leakage that arises from the implementation of Cloudflare's deployment of MIGP. We evaluate how the discovered leakage affects the guessing capability of an attacker in relation to breach extraction attacks. Finally, we propose MIGP 2.0, a new iteration of the MIGP protocol designed to minimize data leakage and prevent the introduced attacks.



## 2023/1849

* Title: Lattice-based Programmable Hash Functions and Applications
* Authors: Jiang Zhang, Yu Chen, Zhenfeng Zhang
* [Permalink](https://eprint.iacr.org/2023/1849)
* [Download](https://eprint.iacr.org/2023/1849.pdf)

### Abstract

Driven by the open problem raised by Hofheinz and Kiltz
(Journal of Cryptology, 2012), we study the formalization of lattice-based programmable hash function (PHF), and give three types of concrete constructions by using several techniques such as a novel combination of cover-free sets and lattice trapdoors. Under the Inhomogeneous Small Integer Solution (ISIS) assumption, we show that any (non-trivial) lattice-based PHF is a collision-resistant hash function, which gives a direct application of this new primitive.

We further demonstrate the power of lattice-based PHF by giving generic constructions of signature and identity-based encryption (IBE) in the standard model, which not only provide a way to unify several previous lattice-based schemes using the partitioning proof techniques, but also allow us to obtain new short signature schemes and IBE schemes from (ideal) lattices. Specifically, by instantiating the generic constructions with our Type-II and Type-III PHF constructions, we immediately obtain two short signatures and two IBE schemes with asymptotically much shorter keys. A major downside which inherits from our Type-II and Type-III PHF constructions is that we can only prove the security of the new signatures and IBEs in the bounded security model that the
number Q of the adversary’s queries is required to be known in advance. Another downside is that the computational time of our new signatures and IBEs is a linear function of Q, which is large for typical parameters.

To overcome the above limitations, we also give a refined way of
using Type-II and Type-III PHFs to construct lattice-based short signatures with short verification keys in the full security model. In particular, our methods depart from the confined guessing technique of B¨ohl et al. (Eurocrypt’13) that was used to construct previous standard model short signature schemes with short verification keys by Ducas and Micciancio (Crypto’14) and by Alperin-Sheriff (PKC’15), and allow us to achieve much tighter security from weaker hardness assumptions.



## 2023/1850

* Title: Accurate Score Prediction for Dual-Sieve Attacks
* Authors: Léo Ducas, Ludo N. Pulles
* [Permalink](https://eprint.iacr.org/2023/1850)
* [Download](https://eprint.iacr.org/2023/1850.pdf)

### Abstract

The Dual-Sieve Attack on Learning with Errors (LWE), or more generally Bounded Distance Decoding (BDD), has seen many improvements in the recent years, and ultimately led to claims that it outperforms the primal attack against certain lattice-based schemes in the PQC standardization process organised by NIST. However, the work of Ducas--Pulles (Crypto '23) revealed that the so-called "Independence Heuristic", which all recent dual attacks used, leads to wrong predictions in a contradictory regime, which is relevant for the security of cryptoschemes. More specifically, the stated distributions of scores for the actual solution and for incorrect candidates were both incorrect.

In this work, we propose to use the weaker heuristic that the output vectors of a lattice sieve are uniformly distributed in a ball. Under this heuristic, we give an analysis of the score distribution in the case of an error of fixed length. Integrating over this length, we extend this analysis to any radially distributed error, in particular the gaussian as a fix for the score distribution of the actual solution. This approach also provides a prediction for the score of incorrect candidates, using a ball as an approximation of the Voronoi cell of a lattice.

We compare the predicted score distributions to extensive experiments, and observe them to be qualitatively and quantitatively quite accurate. This constitutes a first step towards fixing the analysis of the dual-sieve attack: we can now accurately estimate false-positives and false-negatives. Now that the analysis is fixed, one may consider how to fix the attack itself, namely exploring the opportunities to mitigate a large number of false-positives.



## 2023/1851

* Title: Quantum Security of the UMTS-AKA Protocol and its Primitives, Milenage and TUAK
* Authors: Paul Frixons, Sébastien Canard, Loïc Ferreira
* [Permalink](https://eprint.iacr.org/2023/1851)
* [Download](https://eprint.iacr.org/2023/1851.pdf)

### Abstract

The existence of a quantum computer is one of the most significant threats cryptography has ever faced. However, it seems that real world protocols received little attention so far with respect to their future security. Indeed merely relying upon post-quantum primitives may not suffice in order for a security protocol to be resistant in a full quantum world. In this paper, we consider the fundamental UMTS key agreement used in 3G but also in 4G (LTE), and in the (recently deployed) 5G technology. We analyze the protocol in a quantum setting, with quantum communications (allowing superposition queries by the involved parties), and where quantum computation is granted to the adversary. We prove that, assuming the underlying symmetric-key primitive is quantum-secure, the UMTS key agreement is also quantum-secure. We also give a quantum security analysis of the underlying primitives, namely Milenage and TUAK. To the best of our knowledge this paper provides the first rigorous proof of the UMTS key agreement in a strong quantum setting. Our result shows that in the quantum world to come, the UMTS technology remains a valid scheme in order to secure the communications of billions of users.



## 2023/1852

* Title: Reduction from sparse LPN to LPN, Dual Attack 3.0
* Authors: Kévin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, Jean-Pierre Tillich
* [Permalink](https://eprint.iacr.org/2023/1852)
* [Download](https://eprint.iacr.org/2023/1852.pdf)

### Abstract

The security of code-based cryptography relies primarily on the hardness of decoding generic linear codes. Until very recently, all the best algorithms for solving the decoding problem were information set decoders ($\mathsf{ISD}$). However, recently a new algorithm called RLPN-decoding which relies on a completely different approach was introduced and it has been shown that RLPN outperforms significantly $\mathsf{ISD}$ decoders for a rather large range of rates. This RLPN decoder relies on two ingredients, first reducing decoding to some underlying LPN problem, and then computing efficiently many parity-checks of small weight when restricted to some positions. We revisit RLPN-decoding by noticing that, in this algorithm, decoding is in fact reduced to a sparse-LPN problem, namely with a secret whose Hamming weight is small. Our new approach consists this time in making an additional reduction from sparse-LPN to plain-LPN with a coding approach inspired by $\mathsf{coded}$-$\mathsf{BKW}$. It outperforms significantly the $\mathsf{ISD}$'s and RLPN for code rates smaller than $0.42$. This algorithm can be viewed as the code-based cryptography cousin of recent dual attacks in lattice-based cryptography. We depart completely from the traditional analysis of this kind of algorithm which uses a certain number of independence assumptions that have been strongly questioned recently in the latter domain. We give instead a formula for the LPN noise relying on duality which allows to analyze the behavior of the algorithm by relying only on the analysis of a certain weight distribution. By using only a minimal assumption whose validity has been verified experimentally we are able to justify the correctness of our algorithm. This key tool, namely the duality formula, can be readily adapted to the lattice setting and is shown to give a simple explanation for some phenomena observed on dual attacks in lattices in [DP23].



## 2023/1853

* Title: Report on evaluation of KpqC candidates
* Authors: Jolijn Cottaar, Kathrin Hövelmanns, Andreas Hülsing, Tanja Lange, Mohammad Mahzoun, Alex Pellegrini, Alberto Ravagnani, Sven Schäge, Monika Trimoska, Benne de Weger
* [Permalink](https://eprint.iacr.org/2023/1853)
* [Download](https://eprint.iacr.org/2023/1853.pdf)

### Abstract

This report analyzes the 16 submissions to the Korean post-quantum cryptography (KpqC) competition.



## 2023/1854

* Title: A note on quantum approximate optimization algorithm
* Authors: Zhengjun Cao
* [Permalink](https://eprint.iacr.org/2023/1854)
* [Download](https://eprint.iacr.org/2023/1854.pdf)

### Abstract

The general quantum approximate optimization algorithm (QAOA)
produces approximate solutions for combinatorial optimization problems. The algorithm depends on a positive integer $p$ and the quality of approximation improves as $p$ is increased. In this note, we put some questions about the general QAOA. We also find the recursive QAOA for MaxCut problem is flawed because all quantum gates involved in the algorithm are single qubit gates. No any entangling gate is used, which results in that the quantum computing power cannot be certified for the problem.



## 2023/1855

* Title: Demystifying DeFi MEV Activities in Flashbots Bundle
* Authors: Zihao Li, Jianfeng Li, Zheyuan He, Xiapu Luo, Ting Wang, Xiaoze Ni, Wenwu Yang, Xi Chen, Ting Chen
* [Permalink](https://eprint.iacr.org/2023/1855)
* [Download](https://eprint.iacr.org/2023/1855.pdf)

### Abstract

Decentralized Finance, mushrooming in permissionless blockchains, has attracted a recent surge in popularity. Due to the transparency of permissionless blockchains, opportunistic traders can compete to earn revenue by extracting Miner Extractable Value (MEV), which undermines both the consensus security and efficiency of blockchain systems. The Flashbots bundle mechanism further aggravates the MEV competition because it empowers opportunistic traders with the capability of designing more sophisticated MEV extraction. In this paper, we conduct the first systematic study on DeFi MEV activities in Flashbots bundle by developing ActLifter, a novel automated tool for accurately identifying DeFi actions in transactions of each bundle, and ActCluster, a new approach that leverages iterative clustering to facilitate us to discover known/unknown DeFi MEV activities. Extensive experimental results show that ActLifter can achieve nearly 100% precision and recall in DeFi action identification, significantly outperforming state-of-the-art techniques. Moreover, with the help of ActCluster, we obtain many new observations and discover 17 new kinds of DeFi MEV activities, which occur in 53.12% of bundles but have not been reported in existing studies.



## 2023/1856

* Title: Optimizing AES Threshold Implementation under the Glitch-Extended Probing Model
* Authors: Fu Yao, Hua Chen, Yongzhuang Wei, Enes Pasalic, Feng Zhou, Limin Fan
* [Permalink](https://eprint.iacr.org/2023/1856)
* [Download](https://eprint.iacr.org/2023/1856.pdf)

### Abstract

Threshold Implementation (TI) is a well-known Boolean masking technique that provides provable security against side-channel attacks. In the presence of glitches, the probing model was replaced by the so-called glitch-extended probing model which specifies a broader security framework. In CHES 2021, Shahmirzadi et al. introduced a general search method for finding first-order 2-share TI schemes without fresh randomness (under the presence of glitches) for a given encryption algorithm. Although it handles well single-output Boolean functions, this method has to store output shares in registers when extended to vector Boolean functions, which results in more chip area and increased latency. Therefore, the design of TI schemes that have low implementation cost under the glitch-extended probing model appears to be an important research challenge. In this paper, we propose an approach to design the first-order glitch-extended probing secure TI schemes when quadratic functions are employed in the substitution layer. This method only requires a small amount of fresh random bits and a single clock cycle for its implementation. In particular, the random bits in our approach are reusable and compatible with the changing of the guards technique. Our dedicated TI scheme for the AES cipher gives 20.23% smaller implementation area and 4.2% faster encryption compared to the TI scheme of AES (without using fresh randomness) proposed in CHES 2021. Additionally, we propose a parallel implementation of two S-boxes that further reduces latency (about 39.83%) at the expense of increasing the chip area by 9%. We have positively confirmed the security of AES under the glitch-extended probing model using the verification tool - SILVER and the side-channel leakage assessment method - TVLA.