## In this issue

1. [2024/1849] A Linearisation Method for Identifying Dependencies ...
2. [2024/1850] Single-trace side-channel attacks on MAYO ...
3. [2024/1851] Secure Transformer-Based Neural Network Inference ...
4. [2024/1852] Faster algorithms for isogeny computations over ...
5. [2024/1853] Giant Does NOT Mean Strong: Cryptanalysis of BQTRU
6. [2024/1854] A Zero-Knowledge PCP Theorem
7. [2024/1855] Lova: A Novel Framework for Verifying Mathematical ...
8. [2024/1856] "There's always another counter": Detecting Micro- ...
9. [2024/1857] Access-Controlled Inner Product Function-Revealing ...
10. [2024/1858] (In)Security of Threshold Fully Homomorphic ...
11. [2024/1859] Fully Encrypted Machine Learning Protocol using ...
12. [2024/1860] Constructions of self-orthogonal codes and LCD ...
13. [2024/1861] Another Lattice Attack Against an RSA-like Cryptosystem
14. [2024/1862] BatchZK: A Fully Pipelined GPU-Accelerated System ...
15. [2024/1863] Carbon Footprint Traction System Incorporated as ...
16. [2024/1864] Tweakable ForkCipher from Ideal Block Cipher
17. [2024/1865] Tightly-Secure Group Key Exchange with Perfect ...
18. [2024/1866] ARCHER: Architecture-Level Simulator for Side- ...
19. [2024/1867] Symmetric Twin Column Parity Mixers and their ...
20. [2024/1868] IMOK: A compact connector for non-prohibition ...
21. [2024/1869] Black-box Collision Attacks on the NeuralHash ...
22. [2024/1870] A Hard-Label Cryptanalytic Extraction of Non-Fully ...
23. [2024/1871] Field-Agnostic SNARKs from Expand-Accumulate Codes
24. [2024/1872] Amigo: Secure Group Mesh Messaging in Realistic ...
25. [2024/1873] $\mathsf{Cirrus}$: Performant and Accountable ...
26. [2024/1874] Multi-Holder Anonymous Credentials from BBS Signatures
27. [2024/1875] mUOV: Masking the Unbalanced Oil and Vinegar ...
28. [2024/1876] Unbounded Leakage-Resilient Encryption and Signatures
29. [2024/1877] On the Black-Box Complexity of Private-Key Inner- ...
30. [2024/1878] Tighter Security for Group Key Agreement in the ...

## 2024/1849

* Title: A Linearisation Method for Identifying Dependencies in Differential Characteristics: Examining the Intersection of Deterministic Linear Relations and Nonlinear Constraints
* Authors: Ling Sun
* [Permalink](https://eprint.iacr.org/2024/1849)
* [Download](https://eprint.iacr.org/2024/1849.pdf)

### Abstract

The analytical perspective employed in the study classifies the theoretical research on dependencies in differential characteristics into two types. By categorising all dependence representations from the value restrictions and the theory of quasidifferential trails, we pinpoint a specific set of nonlinear constraints, which we term linearised nonlinear constraints. We aim to establish a method that utilises value restrictions to identify these constraints, as the current method based on value restrictions is found to be lacking in this area. A linearisation method for searching linearised nonlinear constraints for a given differential characteristic is developed by leveraging linear dependencies between inputs and outputs of active S-boxes. Then, we propose a three-stage evaluation approach to more accurately evaluate differential characteristics with linearised nonlinear constraints. Four differential characteristics of GIFT-64 are analysed using the three-stage evaluation approach, and the exact right key spaces and remaining probabilities are given. According to our results, the right key spaces of the four differential characteristics do not cover the entire key space, and the remaining probabilities are not equivalent to the stated probabilities. Concerning GIFT-128, we find six differential characteristics subject to linearised nonlinear constraints. Besides, inconsistencies are detected in the linear and linearised nonlinear constraints in the characteristics of two differentials employed to initiate the most effective differential attack on GIFT-128. Based on these results, we strongly advise reassessing the differential attacks that rely on these distinguishers. An additional advantage of using the linearisation method and the three-stage evaluation approach is their ability to identify linear and nonlinear constraints in ciphers that utilise the Generalised Feistel Network (GFN). It leads to the first instantiations of linear and nonlinear constraints in the GFN cipher WARP.

## 2024/1850

* Title: Single-trace side-channel attacks on MAYO exploiting leaky modular multiplication
* Authors: Sönke Jendral, Elena Dubrova
* [Permalink](https://eprint.iacr.org/2024/1850)
* [Download](https://eprint.iacr.org/2024/1850.pdf)

### Abstract

In response to the quantum threat, new post-quantum cryptographic algorithms will soon be deployed to replace existing public-key schemes. MAYO is a quantum-resistant digital signature scheme whose small keys and signatures make it suitable for widespread adoption, including on embedded platforms with limited security resources. This paper demonstrates two single-trace side-channel attacks on a MAYO implementation in ARM Cortex-M4 that recover a secret key with probabilities of 99.9% and 91.6%, respectively. Both attacks use deep learning-assisted power analysis exploiting information leakage during modular multiplication to reveal a vector in the oil space. This vector is then extended to a full secret key using algebraic techniques.

## 2024/1851

* Title: Secure Transformer-Based Neural Network Inference for Protein Sequence Classification
* Authors: Jingwei Chen, Linhan Yang, Chen Yang, Shuai Wang, Rui Li, Weijie Miao, Wenyuan Wu, Li Yang, Kang Wu, Lizhong Dai
* [Permalink](https://eprint.iacr.org/2024/1851)
* [Download](https://eprint.iacr.org/2024/1851.pdf)

### Abstract

Protein sequence classification is crucial in many research areas, such as predicting protein structures and discovering new protein functions. Leveraging large language models (LLMs) is greatly promising to enhance our ability to tackle protein sequence classification problems; however, the accompanying privacy issues are becoming increasingly prominent. In this paper, we present a privacy-preserving, non-interactive, efficient, and accurate protocol called encrypted DASHformer to evaluate a transformer-based neural network for protein sequence classification named DASHformer, provided by the iDASH 2024-Track 1 competition. The presented protocol is based on our solution for this competition, which won the first place. It is arguably the first secure transformer inference protocol capable of performing batch classification for multiple protein sequences in a single execution only using leveled homomorphic encryption (i.e., without bootstrapping). To achieve this, we propose a series of new techniques and algorithmic improvements, including data-driven non-polynomial function fitting, tensor packing, and double baby-step-giant-step for computing the product of multiple encrypted matrices. These techniques and improvements enable the protocol to classify $163$ encrypted protein sequences in about $165$ seconds with $128$-bit security, achieving an amortized time of about one second per sequence.

## 2024/1852

* Title: Faster algorithms for isogeny computations over extensions of finite fields
* Authors: Shiping Cai, Mingjie Chen, Christophe Petit
* [Permalink](https://eprint.iacr.org/2024/1852)
* [Download](https://eprint.iacr.org/2024/1852.pdf)

### Abstract

Any isogeny between two supersingular elliptic curves can be defined over $\mathbb{F}_{p^2}$, however, this does not imply that computing such isogenies can be done with field operations in $\mathbb{F}_{p^2}$. In fact, the kernel generators of such isogenies are defined over extension fields of $\mathbb{F}_{p^2}$, generically with extension degree linear to the isogeny degree. Most algorithms related to isogeny computations are only efficient when the extension degree is small. This leads to efficient algorithms used in isogeny-based cryptographic constructions, but also limits their parameter choices at the same time. In this paper, we consider three computational subroutines regarding isogenies, focusing on cases with large extension degrees: computing a basis of $\ell$-torsion points, computing the kernel polynomial of an isogeny given a kernel generator, and computing the kernel generator of an isogeny given the corresponding quaternion ideal under the Deuring correspondence. We then apply our algorithms to the constructive Deuring correspondence algorithm from Eriksen, Panny, Sotáková and Veroni (LuCaNT'23) in the case of a generic prime characteristic, achieving around 30% speedup over their results.

## 2024/1853

* Title: Giant Does NOT Mean Strong: Cryptanalysis of BQTRU
* Authors: Ali Raya, Vikas Kumar, Aditi Kar Gangopadhyay, Sugata Gangopadhyay
* [Permalink](https://eprint.iacr.org/2024/1853)
* [Download](https://eprint.iacr.org/2024/1853.pdf)

### Abstract

NTRU-like constructions are among the most studied lattice-based schemes. The freedom of design of NTRU resulted in many variants in literature motivated by faster computations or more resistance against lattice attacks by changing the underlying algebra. To the best of our knowledge, BQTRU (DCC 2017), a noncommutative NTRU-like cryptosystem, is the fastest claimed variant of NTRU built over the quaternion algebra of the bivariate ring of polynomials. The key generation and the encryption of BQTRU are claimed to be 16/7 times faster than standard NTRU for equivalent levels of security. For key recovery attacks, the authors claim that retrieving a decryption key is equivalent to solving the Shortest Vector Problem (SVP) in expanded Euclidean lattices of giant dimensions. This work disproves this claim and proposes practical key and message recovery attacks that break the moderate parameter sets of BQTRU estimated to achieve $2^{92}$ message security and $2^{166}$ key security on a standard desktop within less than two core weeks. Furthermore, our analysis shows that the proposed parameter set for the highest security level claiming $2^{212}$ message security and $2^{396}$ key security can barely achieve $2^{82}$ message security and $2^{125}$ key security. Our work not only provides cryptanalysis for BQTRU but also demonstrates the potential of extending Gentry's attack to other rings beyond the cyclotomic polynomial ring.