## In this issue

1. [2024/752] More Embedded Curves for SNARK-Pairing-Friendly Curves
2. [2024/871] New Approaches for Estimating the Bias of ...
3. [2024/1238] Dynamic Collusion Functional Encryption and Multi- ...
4. [2024/1239] Efficient Differentially Private Set Intersection
5. [2024/1240] ARADI and LLAMA: Low-Latency Cryptography for ...
6. [2024/1241] PROF: Protected Order Flow in a Profit-Seeking World
7. [2024/1242] Beyond the Whitepaper: Where BFT Consensus ...
8. [2024/1243] Tailoring two-dimensional codes for structured ...
9. [2024/1244] A Note on ``Three-Factor Anonymous Authentication ...
10. [2024/1245] Garuda and Pari: Faster and Smaller SNARKs via ...
11. [2024/1246] MSMAC: Accelerating Multi-Scalar Multiplication for ...
12. [2024/1247] A Note on the Quasigroup Lai-Massey Structures
13. [2024/1248] A Not So Discrete Sampler: Power Analysis Attacks ...
14. [2024/1249] Koala: A Low-Latency Pseudorandom Function
15. [2024/1250] AutoHoG: Automating Homomorphic Gate Design for ...
16. [2024/1251] EMI Shielding for Use in Side-Channel Security: ...
17. [2024/1252] Legendre Sequences are Pseudorandom under the ...
18. [2024/1253] FELIX (XGCD for FALCON): FPGA-based Scalable and ...
19. [2024/1254] Non-Interactive Zero-Knowledge from LPN and MQ
20. [2024/1255] Compass: Encrypted Semantic Search with High Accuracy
21. [2024/1256] Concrete Analysis of Schnorr-type Signatures with ...
22. [2024/1257] Committing Wide Encryption Mode with Minimum ...
23. [2024/1258] Count Corruptions, Not Users: Improved Tightness ...
24. [2024/1259] Efficient (Non-)Membership Tree from ...
25. [2024/1260] zk-Promises: Making Zero-Knowledge Objects Accept ...
26. [2024/1261] A Key-Recovery Attack on a Leaky Seasign Variant
27. [2024/1262] Dilithium-Based Verifiable Timed Signature Scheme
28. [2024/1263] A Security Analysis of Two Classes of RSA-like ...
29. [2024/1264] Succinct Non-Subsequence Arguments
30. [2024/1265] Safe curves for elliptic-curve cryptography
31. [2024/1266] Information-Theoretic Topology-Hiding Broadcast: ...

## 2024/752

* Title: More Embedded Curves for SNARK-Pairing-Friendly Curves
* Authors: Aurore Guillevic
* [Permalink](https://eprint.iacr.org/2024/752)
* [Download](https://eprint.iacr.org/2024/752.pdf)

### Abstract

Embedded curves are elliptic curves defined over a prime field whose order (characteristic) is the prime subgroup order (the scalar field) of a pairing-friendly curve. Embedded curves have a large prime-order subgroup of cryptographic size but are not pairing-friendly themselves. Sanso and El Housni published families of embedded curves for BLS pairing-friendly curves. Their families are parameterized by polynomials, like families of pairing-friendly curves are. However their work did not found embedded families for KSS pairing-friendly curves. In this note we show how the problem of finding families of embedded curves is related to the problem of finding optimal formulas for $\G_1$ subgroup membership testing on the pairing-friendly curve side. Then we apply Smith's technique and Dai, Lin, Zhao, and Zhou (DLZZ) criteria to obtain the formulas of embedded curves with KSS, and outline a generic algorithm for solving this problem in all cases. We provide two families of embedded curves of prime-order for KSS18 that can form a plain cycle, and give examples of cryptographic size. We also give families of even-order $j=1728$ embedded curves for KSS16 with examples. We also suggest alternative embedded curves for BLS that have a seed of much lower Hamming weight than Sanso et al.~and much higher 2-valuation for fast FFT. In particular we highlight BLS12 curves which have a prime-order embedded curve that form a plain cycle (no pairing), and a second (plain) embedded curve in Montgomery form. A Brezing-Weng outer curve to have a pairing-friendly 2-chain is also possible like in the BLS12-377-BW6-761 construction. All curves have $j$-invariant 0 and an endomorphism for a faster arithmetic on the curve side.

## 2024/871

* Title: New Approaches for Estimating the Bias of Differential-Linear Distinguishers (Full Version)
* Authors: Ting Peng, Wentao Zhang, Jingsui Weng, Tianyou Ding
* [Permalink](https://eprint.iacr.org/2024/871)
* [Download](https://eprint.iacr.org/2024/871.pdf)

### Abstract

Differential-linear cryptanalysis was introduced by Langford and Hellman in 1994 and has been extensively studied since then. In 2019, Bar-On et al. presented the Differential-Linear Connectivity Table (DLCT), which connects the differential part and the linear part, thus an attacked cipher is divided to 3 subciphers: the differential part, the DLCT part, and the linear part.
In this paper, we firstly present an accurate mathematical formula which establishes a relation between differential-linear and truncated differential cryptanalysis. Using the formula, the bias estimate of a differential-linear distinguisher can be converted to the probability calculations of a series of truncated differentials. Then, we propose a novel and natural concept, the TDT, which can be used to accelerate the calculation of the probabilities of truncated differentials. Based on the formula and the TDT, we propose two novel approaches for estimating the bias of a differential-linear distinguisher. We demonstrate the accuracy and efficiency of our new approaches by applying them to 5 symmetric-key primitives: Ascon, Serpent, KNOT, AES, and CLEFIA. For Ascon and Serpent, we update the best known differential-linear distinguishers.. For KNOT AES, and CLEFIA, for the first time we give the theoretical differential-linear biases for different rounds.

## 2024/1238

* Title: Dynamic Collusion Functional Encryption and Multi-Authority Attribute-Based Encryption
* Authors: Rachit Garg, Rishab Goyal, George Lu
* [Permalink](https://eprint.iacr.org/2024/1238)
* [Download](https://eprint.iacr.org/2024/1238.pdf)

### Abstract

Functional Encryption (FE) is a powerful notion of encryption which enables computations and partial message recovery of encrypted data. In FE, each decryption key is associated with a function $f$ such that decryption recovers the function evaluation $f(m)$ from an encryption of $m$. Informally, security states that a user with access to function keys $\mathsf{sk}_{f_1}, \mathsf{sk}_{f_2}, \ldots$ (and so on) can only learn $f_1(m), f_2(m), \ldots$ (and so on) but nothing more about the message. The system is said to be $q$-bounded collusion resistant if the security holds as long as an adversary gets access to at most $q = q(\lambda)$ decryption keys. In the last decade, numerous works have proposed many FE constructions from a wide array of algebraic and general cryptographic assumptions, and proved their security in the bounded collusion model.

However, until very recently, all these works studied bounded collusion resistance in a "static model", where the collusion bound $q$ was a global system parameter. While the static collusion model led to great research progress in the community, it has many major drawbacks. Very recently, Agrawal et al. (Crypto 2021) and Garg et al. (Eurocrypt 2022) independently introduced the "dynamic model" for bounded collusion resistance, where the collusion bound $q$ was a fluid parameter that was not globally set but only chosen by each encryptor. The dynamic collusion model enabled harnessing the many virtues of the static collusion model, while avoiding its various drawbacks.

In this work, we give a simple and generic approach to upgrade any scheme from the static collusion model to the dynamic collusion model. Our result captures all existing results in the dynamic model in the form of a single unified framework, and also gives new results as simple corollaries with a lot more potential in the future. An interesting artifact of our result is that it gives a generic way to match existing lower bounds in functional encryption.

## 2024/1239

* Title: Efficient Differentially Private Set Intersection
* Authors: Xinyu Peng, Yufei Wang, Weiran Liu, Liqiang Peng, Feng Han, Zhen Gu, Jianling Sun, Yuan Hong
* [Permalink](https://eprint.iacr.org/2024/1239)
* [Download](https://eprint.iacr.org/2024/1239.pdf)

### Abstract

Private Set Intersection (PSI) enables a sender and a receiver to jointly compute the intersection of their sets without disclosing other information about items not in the intersection. However, in many cases of joint data analysis, it is not just the items outside the intersection that are sensitive but the items within it. To protect such sensitive information, prior work presents a Differentially Private version of PSI (DPSI) based on a circuit-PSI using Fully Homomorphic Encryption. However, their concrete protocol is somewhat inefficient compared with the state-of-the-art (SOTA) circuit-PSI.

In this paper, we revisit the DPSI definition and formalize its ideal functionality. We identify the key desiderata required by PSI-related tools to construct DPSI and propose two frameworks to construct efficient DPSI protocols. The first one generalizes the idea of existing DPSI, showing that any circuit-PSI can be used to construct DPSI. We obtain a more efficient DPSI protocol by plugging the SOTA circuit-PSI protocol in the framework. The second one helps to obtain a more efficient DPSI protocol based on the multi-query Reverse Private Membership Test (mqRPMT) that was previously used to construct Private Set Operation (PSO). However, mqRPMT additionally leaks the intersection size to the sender. We bound such leakage using differential privacy by padding random dummy items in input sets. We implement numerous constructions based on our frameworks. Experiments show that our protocols significantly outperform the existing DPSI construction, 2.5-22.6$\times$ more communication efficient and up to 110.5-151.8$\times$ faster. Our work also shows a new use case for mqRPMT besides obtaining PSO.