## In this issue

1. [2024/772] Reducing the Share Size of Weighted Threshold ...
2. [2024/1109] QuickPool: Privacy-Preserving Ride-Sharing Service
3. [2024/1110] Legacy Encryption Downgrade Attacks against ...
4. [2024/1111] Collision Attacks on Galois/Counter Mode (GCM)
5. [2024/1112] HERatio: Homomorphic Encryption of Rationals using ...
6. [2024/1113] Ringtail: Practical Two-Round Threshold Signatures ...
7. [2024/1114] Time-Memory Trade-off Algorithms for ...
8. [2024/1115] Public vs Private Blockchains lineage storage
9. [2024/1116] A Simple Post-Quantum Oblivious Transfer Protocol ...
10. [2024/1117] Oryx: Private detection of cycles in federated graphs
11. [2024/1118] Shared-Custodial Password-Authenticated ...
12. [2024/1119] Generic Anamorphic Encryption, Revisited: New ...
13. [2024/1120] A Fast and Efficient SIKE Co-Design: Coarse-Grained ...
14. [2024/1121] Implementation and Performance Evaluation of ...
15. [2024/1122] Finding Bugs and Features Using Cryptographically- ...
16. [2024/1123] Switching Off your Device Does Not Protect Against ...
17. [2024/1124] OPPID: Single Sign-On with Oblivious Pairwise ...
18. [2024/1125] Revisiting PACD-based Attacks on RSA-CRT
19. [2024/1126] Is ML-Based Cryptanalysis Inherently Limited? ...
20. [2024/1127] Curl: Private LLMs through Wavelet-Encoded Look-Up ...
21. [2024/1128] Cryptiny: Compacting Cryptography for Space- ...
22. [2024/1129] Attribute-Based Signatures for Circuits with ...
23. [2024/1130] Distributed Verifiable Random Function With Compact ...
24. [2024/1131] Jolt-b: recursion friendly Jolt with basefold ...
25. [2024/1132] A New PPML Paradigm for Quantized Models
26. [2024/1133] Parameters of Algebraic Representation vs. ...
27. [2024/1134] Exploiting signature leakages: breaking Enhanced ...
28. [2024/1135] Scalable and Lightweight State-Channel Audits
29. [2024/1136] Probabilistic Linearization: Internal Differential ...
30. [2024/1137] Cryptanalysis of EagleSign
31. [2024/1138] Dot-Product Proofs and Their Applications
32. [2024/1139] Anonymous Outsourced Statekeeping with Reduced ...
33. [2024/1140] Permutation Superposition Oracles for Quantum Query ...
34. [2024/1141] Optimized Privacy-Preserving Clustering with Fully ...
35. [2024/1142] Predicting one class of truncated matrix ...
36. [2024/1143] LR-OT: Leakage-Resilient Oblivious Transfer
37. [2024/1144] A Note on ``Secure and Distributed IoT Data Storage ...
38. [2024/1145] A Practical and Scalable Implementation of the ...
39. [2024/1146] Breaking Free: Efficient Multi-Party Private Set ...

## 2024/772

* Title: Reducing the Share Size of Weighted Threshold Secret Sharing Schemes via Chow Parameters Approximation
* Authors: Oriol Farràs, Miquel Guiot
* [Permalink](https://eprint.iacr.org/2024/772)
* [Download](https://eprint.iacr.org/2024/772.pdf)

### Abstract

A secret sharing scheme is a cryptographic primitive that allows a dealer to share a secret among a set of parties, so that only authorized subsets of them can recover it. The access structure of the scheme is the family of authorized subsets.

In a weighted threshold access structure, each party is assigned a weight according to its importance, and the authorized subsets are those in which the sum of their weights is at least the threshold value. For these access structures, the share size of the best known secret sharing schemes is either linear on the weights or quasipolynomial on the number of parties, which leads to long shares, in general.

In certain settings, a way to circumvent this efficiency problem is to approximate the access structure by another one that admits more efficient schemes. This work is dedicated to the open problem posed by this strategy: Finding secret sharing schemes with a good tradeoff between the efficiency and the accuracy of the approximation.

We present a method to approximate weighted threshold access structures by others that admit schemes with small shares. This method is based on the techniques for the approximation of the Chow parameters developed by De et al. [Journal of the ACM, 2014]. Our method provides secret sharing schemes with share size $n^{1+o(1)}$, where $n$ is the number of parties, and whose access structure is close to the original one. Namely, in this approximation the condition of being authorized or not is preserved for almost all subsets of parties.

In addition, applying the recent results on computational secret sharing schemes by Applebaum et al. [STOC, 2023] we show that there exist computational secret sharing schemes whose security is based on the RSA assumption and whose share size is polylogarithmic in the number of parties.

## 2024/1109

* Title: QuickPool: Privacy-Preserving Ride-Sharing Service
* Authors: Banashri Karmakar, Shyam Murthy, Arpita Patra, Protik Paul
* [Permalink](https://eprint.iacr.org/2024/1109)
* [Download](https://eprint.iacr.org/2024/1109.pdf)

### Abstract

Online ride-sharing services (RSS) have become very popular owing to increased awareness of environmental concerns and as a response to increased traffic congestion. To request a ride, users submit their locations and route information for ride matching to a service provider (SP), leading to possible privacy concerns caused by leakage of users' location data. We propose QuickPool, an efficient SP-aided RSS solution that can obliviously match multiple riders and drivers simultaneously, without involving any other auxiliary server. End-users, namely, riders and drivers share their route information with SP as encryptions of the ordered set of points-of-interest (PoI) of their route from their start to end locations. SP performs a zone based oblivious matching of drivers and riders, based on partial route overlap as well as proximity of start and end points. QuickPool is in the semi-honest setting, and makes use of secure multi-party computation. We provide security proof of our protocol, perform extensive testing of our implementation and show that our protocol simultaneously matches multiple drivers and riders very efficiently. We compare the performance of QuickPool with state-of-the-art works and observe a run time improvement of 1.6 - 2$\times$, and communication improvement of at least 8$\times$.

## 2024/1110

* Title: Legacy Encryption Downgrade Attacks against LibrePGP and CMS
* Authors: Falko Strenzke, Johannes Roth
* [Permalink](https://eprint.iacr.org/2024/1110)
* [Download](https://eprint.iacr.org/2024/1110.pdf)

### Abstract

This work describes vulnerabilities in the specification of the AEAD packets as introduced in the novel LibrePGP specification that is implemented by the widely used GnuPG application and the AES-based AEAD schemes as well as the Key Wrap
Algorithm specified in the Cryptographic Message Syntax (CMS).
These new attacks exploit the possibility to downgrade AEAD or AES Key Wrap ciphertexts to valid legacy CFB- or CBC-encrypted related ciphertexts and require that the attacker learns the content of the legacy decryption result.
This can happen either due to the human recipient returning the decryption output, which has entirely pseudo-random appearance, to the attacker or due to a programmatic decryption oracle in the receiving system.
The attacks effect the decryption of low-entropy plaintext blocks in AEAD ciphertexts and, in the case of LibrePGP, also the manipulation of existing AEAD ciphertexts.
For AES Key Wrap in CMS, full key decryption is possible.
Some of the attacks require multiple successful oracle queries.
The attacks thus demonstrate that CCA2 security is not achieved by the LibrePGP and CMS AEAD or Key Wrap encryption in the presence of a legacy cipher mode decryption oracle.
The proper countermeasure to thwart the attacks is a key derivation that ensures the use of unrelated block cipher keys for the different encryption modes.

## 2024/1111

* Title: Collision Attacks on Galois/Counter Mode (GCM)
* Authors: John Preuß Mattsson
* [Permalink](https://eprint.iacr.org/2024/1111)
* [Download](https://eprint.iacr.org/2024/1111.pdf)

### Abstract

Advanced Encryption Standard Galois/Counter Mode (AES-GCM) is the most widely used Authenticated Encryption with Associated Data (AEAD) algorithm in the world. In this paper, we analyze the use of GCM with all the Initialization Vector (IV) constructions and lengths approved by NIST SP 800-38D when encrypting multiple plaintexts with the same key. We derive attack complexities in both ciphertext-only and known-plaintext models, with or without nonce hiding, for collision attacks compromising integrity and confidentiality. Our analysis shows that GCM with random IVs provides less than 128 bits of security. When 96-bit IVs are used, as recommended by NIST, the security drops to less than 97 bits. Therefore, we strongly recommend NIST to forbid the use of GCM with 96-bit random nonces.

## 2024/1112

* Title: HERatio: Homomorphic Encryption of Rationals using Laurent Polynomials
* Authors: Luke Harmon, Gaetan Delavignette, Hanes Oliveira
* [Permalink](https://eprint.iacr.org/2024/1112)
* [Download](https://eprint.iacr.org/2024/1112.pdf)

### Abstract

In this work we present $\mathsf{HERatio}$, a homomorphic encryption scheme that builds on the scheme of Brakerski, and Fan and Vercauteren. Our scheme naturally accepts Laurent polynomials as inputs, allowing it to work with rationals via their bounded base-$b$ expansions. This eliminates the need for a specialized encoder and streamlines encryption, while maintaining comparable efficiency to BFV. To achieve this, we introduce a new variant of the Polynomial Learning With Errors (PLWE) problem which employs Laurent polynomials instead of the usual ``classic'' polynomials, and provide a reduction to the PLWE problem.