[digest] 2024 Week 28

## 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.



## 2024/1113

* Title: Ringtail: Practical Two-Round Threshold Signatures from Learning with Errors
* Authors: Cecilia Boschini, Darya Kaviani, Russell W. F. Lai, Giulio Malavolta, Akira Takahashi, Mehdi Tibouchi
* [Permalink](https://eprint.iacr.org/2024/1113)
* [Download](https://eprint.iacr.org/2024/1113.pdf)

### Abstract

A threshold signature scheme splits the signing key among $\ell$ parties, such that any $t$-subset of parties can jointly generate signatures on a given message. Designing concretely efficient post-quantum threshold signatures is a pressing question, as evidenced by NIST's recent call.

In this work, we propose, implement, and evaluate a lattice-based threshold signature scheme, Ringtail, which is the first to achieve a combination of desirable properties:
            (i) The signing protocol consists of only two rounds, where the first round is message-independent and can thus be preprocessed offline.
            (ii) The scheme is concretely efficient and scalable to $t \leq 1024$ parties. For $128$-bit security and $t = 1024$ parties, we achieve $13..4$ KB signature size and $10.5$ KB of online communication.  
            (iii) The security is based on the standard learning with errors (LWE) assumption in the random oracle model. This improves upon the state-of-the-art (with comparable efficiency) which either has a three-round signing protocol [Eurocrypt'24] or relies on a new non-standard assumption [Crypto'24].

To substantiate the practicality of our scheme, we conduct the first WAN experiment deploying a lattice-based threshold signature, across 8 countries in 5 continents. We observe that an overwhelming majority of the end-to-end latency is consumed by network latency, underscoring the need for round-optimized schemes.



## 2024/1114

* Title: Time-Memory Trade-off Algorithms for Homomorphically Evaluating Look-up Table in TFHE
* Authors: Shintaro Narisada, Hiroki Okada, Kazuhide Fukushima, Takashi Nishide
* [Permalink](https://eprint.iacr.org/2024/1114)
* [Download](https://eprint.iacr.org/2024/1114.pdf)

### Abstract

We propose time-memory trade-off algorithms for evaluating look-up table (LUT) in both the leveled homomorphic encryption (LHE) and fully homomorphic encryption (FHE) modes in TFHE. For an arbitrary $n$-bit Boolean function, we reduce evaluation time by a factor of $O(n)$ at the expense of an additional memory of "only" $O(2^n)$ as a trade-off: The total asymptotic memory is also $O(2^n)$, which is the same as that of prior works. Our empirical results demonstrate that a $7.8 \times$ speedup in runtime is obtained with a $3.8 \times$ increase in memory usage for 16-bit Boolean functions in the LHE mode. Additionally, in the FHE mode, we achieve reductions in both runtime and memory usage by factors of $17.9 \times$ and $2.5 \times $, respectively, for 8-bit Boolean functions. The core idea is to decompose the function $f$ into sufficiently small subfunctions and leverage the precomputed results for these subfunctions, thereby achieving significant performance improvements at the cost of additional memory.



## 2024/1115

* Title: Public vs Private Blockchains lineage storage
* Authors: Bilel Zaghdoudi, Maria Potop Butucaru
* [Permalink](https://eprint.iacr.org/2024/1115)
* [Download](https://eprint.iacr.org/2024/1115.pdf)

### Abstract

This paper reports the experimental results related to lineage event storage via smart contracts deployed on private and public blockchain. In our experiments we measure the following three metrics: the cost to deploy the storage smart contract on the blockchain, which measures the initial expenditure, typically in gas units, required to deploy the smart contract that facilitates lineage event storage, then the time and gas costs needed to store a lineage event. We investigated both single and multi-clients scenarios. We considered the following public blockchains: Hedera, Fantom, Harmony Shard0, Polygon Amoy, Ethereum Sepolia, Optimism Sepolia, Klaytn Baobab and Arbitrum Sepolia. Furthermore, we investigate the performances of Hyperledger Besu with different consensus algorithms as private blockchains.



## 2024/1116

* Title: A Simple Post-Quantum Oblivious Transfer Protocol from Mod-LWR
* Authors: Shen Dong, Hongrui Cui, Kaiyi Zhang, Kang Yang, Yu Yu
* [Permalink](https://eprint.iacr.org/2024/1116)
* [Download](https://eprint.iacr.org/2024/1116.pdf)

### Abstract

Oblivious transfer (OT) is a fundamental cryptographic protocol that plays a crucial role in secure multi-party computation (MPC). Most practical OT protocols by, e.g., Naor and Pinkas (SODA'01) or Chou and Orlandi (Latincrypt'15), are based on Diffie-Hellman (DH)-like assumptions and not post-quantum secure. In contrast, many other components of MPC protocols, including garbled circuits and secret sharings, are post-quantum secure. The reliance on non-post-quantum OT protocols presents a significant security bottleneck with the advent of quantum computing.
In this paper, we address this issue by constructing a simple, efficient OT protocol based on Saber, a Mod-LWR-based key exchange protocol. We implemented our OT protocol and conducted experiments to evaluate its performance. Our results show that our OT protocol significantly outperforms the state-of-the-art Kyber-based post-quantum OT protocol by Masny and Rindal (CCS'19) in terms of both computation and communication costs. Furthermore, the computation speed of our OT protocol is faster than the best-known DH-based OT protocol by Chou and Orlandi (Latincrypt'15), making it competitive to replace DH-based OT in the high-bandwidth network setting.



## 2024/1117

* Title: Oryx: Private detection of cycles in federated graphs
* Authors: Ke Zhong, Sebastian Angel
* [Permalink](https://eprint.iacr.org/2024/1117)
* [Download](https://eprint.iacr.org/2024/1117.pdf)

### Abstract

This paper proposes Oryx, a system for efficiently detecting cycles in federated graphs where parts of the graph are held by different parties and are private. Cycle detection is an important building block in designing fraud detection algorithms that operate on confidential transaction data held by different financial institutions. Oryx allows detecting cycles of various length while keeping the topology of the graphs secret, and it does so efficiently; Oryx achieves quasilinear computational complexity and scales well with more machines thanks to a parallel design. Our implementation of Oryx running on a single 32-core AWS machine (for each party) can detect cycles of up to length 6 in under 5 hours in a financial transaction graph that consists of tens of millions of nodes and edges. While the costs are high, adding more machines further reduces the completion time. Furthermore, Oryx is, to our knowledge, the first and only system that can handle this task.



## 2024/1118

* Title: Shared-Custodial Password-Authenticated Deterministic Wallets
* Authors: Poulami Das, Andreas Erwig, Sebastian Faust
* [Permalink](https://eprint.iacr.org/2024/1118)
* [Download](https://eprint.iacr.org/2024/1118.pdf)

### Abstract

Cryptographic wallets are an essential tool in Blockchain networks to ensure the secure storage and maintenance of an user's cryptographic keys. Broadly, wallets can be divided into three categories, namely custodial, non-custodial, and shared-custodial wallets. The first two are centralized solutions, i.e., the wallet is operated by a single entity, which inherently introduces a single point of failure. Shared-custodial wallets, on the other hand, are maintained by two independent parties, e.g., the wallet user and a service provider, and hence avoid the single point of failure centralized solutions. Unfortunately, current shared-custodial wallets suffer from significant privacy issues.

In our work, we introduce password-authenticated deterministic wallets (PADW), a novel and efficient shared-custodial wallet solution, which exhibits strong security and privacy guarantees. In a nutshell, in a PADW scheme, the secret key of the user is shared between the user and the server. In order to generate a signature, the user first authenticates itself to the server by providing a password and afterwards engages in an interactive signing protocol with the server. Security is guaranteed as long as at most one of the two parties is corrupted. Privacy, on the other hand, guarantees that a corrupted server cannot link a transaction to a particular user. We formally model the notion of PADW schemes and we give an instantiation from blind Schnorr signatures. Our construction allows for deterministic key derivation, a feature that is widely used in practice by existing wallet schemes, and it does not rely on any heavy cryptographic primitives. We prove our scheme secure against adaptive adversaries in the random oracle model and under standard assumptions. That is, our security proof only relies on the assumption that the Schnorr signature scheme is unforgeable and that a public key encryption scheme is CCA-secure.



## 2024/1119

* Title: Generic Anamorphic Encryption, Revisited: New Limitations and Constructions
* Authors: Dario Catalano, Emanuele Giunta, Francesco Migliaro
* [Permalink](https://eprint.iacr.org/2024/1119)
* [Download](https://eprint.iacr.org/2024/1119.pdf)

### Abstract

The notion of Anamorphic Encryption (Persiano et al. Eurocrypt 2022) aims at establishing private communication against an adversary who can access secret decryption keys and influence the chosen messages. Persiano et al. gave a simple, black-box, rejection sampling-based technique to send anamorphic bits using any IND-CPA secure scheme as underlying PKE.

In this paper however we provide evidence that their solution is not as general as claimed: indeed there exists a (contrived yet secure) PKE which lead to insecure anamorphic instantiations. Actually, our result implies that such stateless black-box realizations of AE are impossible to achieve, unless weaker notions are targeted or extra assumptions are made on the PKE. Even worse, this holds true even if one resorts to powerful non-black-box techniques, such as NIZKs, $ i\mathcal{O} $ or garbling.

From a constructive perspective, we shed light those required assumptions. Specifically, we show that one could bypass (to some extent) our impossibility by either considering a weaker (but meaningful) notion of AE or by assuming the underlying PKE to (always) produce high min-entropy ciphertexts.

Finally, we prove that, for the case of Fully-Asymmetric AE, $ i\mathcal{O}$ can actually be used to overcome existing impossibility barriers.
We show how to use $ i\mathcal{O} $ to build Fully-Asymmetric AE (with small anamorphic message space) generically from any IND-CPA secure PKE with sufficiently high min-entropy ciphertexts.
Put together our results provide a clearer picture of what black-box constructions can and cannot achieve.



## 2024/1120

* Title: A Fast and Efficient SIKE Co-Design: Coarse-Grained Reconfigurable Accelerators with Custom RISC-V Microcontroller on FPGA
* Authors: Jing Tian, Bo Wu, Lang Feng, Haochen Zhang, Zhongfeng Wang
* [Permalink](https://eprint.iacr.org/2024/1120)
* [Download](https://eprint.iacr.org/2024/1120.pdf)

### Abstract

This paper proposes a fast and efficient FPGA-based hardware-software co-design for the supersingular isogeny key encapsulation (SIKE) protocol controlled by a custom RISC-V processor. Firstly, we highly optimize the core unit, the polynomial-based field arithmetic logic unit (FALU), with the proposed fast convolution-like multiplier (FCM) to significantly reduce the resource consumption while still maintaining low latency and constant time for all the four SIKE parameters. Secondly, we pack the small isogeny and point operations in hardware, devise a coarse-grained reconfigurable hardware architecture (CGRHA) based on FALU as the co-processor, and apply it to the RISC-V core with customized instructions, effectively avoiding extra time consumption for the data exchange with the software side and meanwhile increasing flexibility. Finally, we code the hardware in SystemVerilog language and the software in C language and run experiments on FPGAs. In the co-processor implementation, the experiment results show that our design for the four SIKE parameters achieves 2..6-4.4x speedup and obtains comparable or better area-time product to or than the state-of-the-art. In the hardware-software co-design experiments, we still have the superiority in speed and only <10\% of extra time is introduced by mutual communication.



## 2024/1121

* Title: Implementation and Performance Evaluation of Elliptic Curve Cryptography over SECP256R1 on STM32 Microprocessor
* Authors: Onur İşler
* [Permalink](https://eprint.iacr.org/2024/1121)
* [Download](https://eprint.iacr.org/2024/1121.pdf)

### Abstract

The use of Internet of Things (IoT) devices in embedded systems has become increasingly popular with advancing technologies. These devices become vulnerable to cyber attacks as they gain popularity. The cryptographic operations performed for the purpose of protection against cyber attacks are crucial to yield fast results in open networks and not slow down network traffic. Therefore, to enhance communication security, studies have been conducted in the literature on using asymmetric encryption and symmetric encryption together in IoT devices for activities such as key sharing, encryption, decryption, data signing, and verifying signed data. In this study, we first propose a cryptographic system engaging of IoT devices operated from a server. Then we do performance analysis of our proposal. In particular, we evaluate the elliptic curve Diffie-Hellman key exchange and elliptic curve digital signature algorithms on the Secp256r1 elliptic curve and AES symmetric encryption via the Micro uECC library  conducted with the 32-bit STM32F410RB Nucleo development board microprocessor running at 48 MHz.



## 2024/1122

* Title: Finding Bugs and Features Using Cryptographically-Informed Functional Testing
* Authors: Giacomo Fenzi, Jan Gilcher, Fernando Virdia
* [Permalink](https://eprint.iacr.org/2024/1122)
* [Download](https://eprint.iacr.org/2024/1122.pdf)

### Abstract

In 2018, Mouha et al. (IEEE Trans. Reliability, 2018) performed a post-mortem investigation of the correctness of reference implementations submitted to the SHA3 competition run by NIST, finding previously unidentified bugs in a significant portion of them, including two of the five finalists. Their innovative approach allowed them to identify the presence of such bugs in a black-box manner, by searching for counterexamples to expected cryptographic properties of the implementations under test. In this work, we extend their approach to key encapsulation mechanisms (KEMs) and digital signature schemes (DSSs). We perform our tests on multiple versions of the LibOQS collection of post-quantum schemes, to capture implementations at different points of the recent Post-Quantum Cryptography Standardization Process run by NIST. We identify multiple bugs, ranging from software bugs (segmentation faults, memory overflows) to  cryptographic bugs, such as ciphertext malleability in KEMs claiming IND-CCA security. We also observe various features of KEMs and DSS that do not contradict any security guarantees, but could appear counter-intuitive.



## 2024/1123

* Title: Switching Off your Device Does Not Protect Against Fault Attacks
* Authors: Paul Grandamme, Pierre-Antoine Tissot, Lilian Bossuet, Jean-Max Dutertre, Brice Colombier, Vincent Grosso
* [Permalink](https://eprint.iacr.org/2024/1123)
* [Download](https://eprint.iacr.org/2024/1123.pdf)

### Abstract

Physical attacks, and among them fault injection attacks, are a significant threat to the security of embedded systems. Among the means of fault injection, laser has the significant advantage of being extremely spatially accurate. Numerous state-of-the-art studies have investigated the use of lasers to inject faults into a target at run-time. However, the high precision of laser fault injection comes with requirements on the knowledge of the implementation and exact execution time of the victim code. The main contribution of this work is the demonstration on experimental basis that it is also possible to perform laser fault injection on an unpowered device. Specifically, we targeted the Flash non-volatile memory of a 32-bit microcontroller. The advantage of this new attack path is that it does not require any synchronisation between the victim and the attacker. We provide an experimental characterization of this phenomenon with a description of the fault model from the physical level up to the software level. Finally, we applied these results to carry out a persistent fault analysis on a 128-bit AES with a particularly realistic attacker model which reinforces the interest of the PFA.



## 2024/1124

* Title: OPPID: Single Sign-On with Oblivious Pairwise Pseudonyms
* Authors: Maximilian Kroschewski, Anja Lehmann, Cavit Özbay
* [Permalink](https://eprint.iacr.org/2024/1124)
* [Download](https://eprint.iacr.org/2024/1124.pdf)

### Abstract

Single Sign-On (SSO) allows users to conveniently authenticate to many Relying Parties (RPs) through a central Identity Provider (IdP). SSO supports unlinkable authentication towards the RPs via pairwise pseudonyms, where the IdP assigns the user an RP-specific pseudonym. This feature has been rolled out prominently within Apple's SSO service. While establishing unlinkable identities provides privacy towards RPs, it actually emphasizes the main privacy problem of SSO: with every authentication request, the IdP learns the RP that the user wants to access. Solutions to overcome this limitation exist, but either assume users to behave honestly or require them to manage long-term cryptographic keys.

In this work, we propose the first SSO system that can provide such pseudonymous authentication in an unobservable yet strongly secure and convenient manner. That is, the IdP blindly derives the user's pairwise pseudonym for the targeted RP without learning the RP's identity and without requiring key material handled by the user. We formally define the desired security and privacy properties for such unlinkable, unobservable, and strongly secure SSO. In particular, our model includes the often neglected RP authentication: the IdP typically wants to limit its services to registered RPs only and thus must be able to (blindly) verify that it issues the token and pseudonym to such a registered RP. We propose a simple construction that combines signatures with efficient proofs-of-knowledge with a blind, yet verifiable, evaluation of the Hashed-Diffie-Hellman PRF. We prove the security of our construction and demonstrate its efficiency through a prototypical implementation, which requires a running time of 2-20ms per involved party.



## 2024/1125

* Title: Revisiting PACD-based Attacks on RSA-CRT
* Authors: Guillaume Barbu, Laurent Grémy, Roch Lescuyer
* [Permalink](https://eprint.iacr.org/2024/1125)
* [Download](https://eprint.iacr.org/2024/1125.pdf)

### Abstract

In this work, we use some recent developments in lattice-based cryptanalytic tools to revisit a fault attack on RSA-CRT signatures based on the Partial Approximate Common Divisor (PACD) problem. By reducing the PACD to a Hidden Number Problem (HNP) instance, we decrease the number of required faulted bits from 32 to 7 in the case of a 1024-bit RSA. We successfully apply the attack to RSA instances up to 8192-bit and present an enhanced analysis of the error-tolerance in the Bounded Distance Decoding (BDD) with predicate approach. Finally, evaluating the impact of standard side-channel and fault countermeasures, we show that merely verifying the signature before output is not an adequate protection against this attack. The reduction from PACD to HNP might be of independent interest.



## 2024/1126

* Title: Is ML-Based Cryptanalysis Inherently Limited? Simulating Cryptographic Adversaries via Gradient-Based Methods
* Authors: Avital Shafran, Eran Malach, Thomas Ristenpart, Gil Segev, Stefano Tessaro
* [Permalink](https://eprint.iacr.org/2024/1126)
* [Download](https://eprint.iacr.org/2024/1126.pdf)

### Abstract

Given the recent progress in machine learning (ML), the cryptography community has started exploring the applicability of ML methods to the design of new cryptanalytic approaches. While current empirical results show promise, the extent to which such methods may outperform classical cryptanalytic approaches is still somewhat unclear.

In this work, we initiate exploration of the theory of ML-based cryptanalytic techniques, in particular providing new results towards understanding whether they are fundamentally limited compared to traditional approaches. Whereas most classic cryptanalysis crucially relies on directly processing individual samples (e.g., plaintext-ciphertext pairs), modern ML methods thus far only interact with samples via gradient-based computations that average a loss function over all samples. It is, therefore, conceivable that such gradient-based methods are inherently weaker than classical approaches.

We introduce a unifying framework for capturing both ``sample-based'' adversaries that are provided with direct access to individual samples and ``gradient-based'' ones that are restricted to issuing gradient-based queries that are averaged over all given samples via a loss function. Within our framework, we establish a general feasibility result showing that any sample-based adversary can be simulated by a seemingly-weaker gradient-based one. Moreover, the simulation exhibits a nearly optimal overhead in terms of the gradient-based simulator's running time. Finally, we extend and refine our simulation technique to construct a gradient-based simulator that is fully parallelizable (crucial for avoiding an undesirable overhead for parallelizable cryptanalytic tasks), which is then used to construct a gradient-based simulator that executes the particular and highly useful gradient-descent method.

Taken together, although the extent to which ML methods may outperform classical cryptanalytic approaches is still somewhat unclear, our results indicate that such gradient-based methods are not inherently limited by their seemingly restricted access to the provided samples.



## 2024/1127

* Title: Curl: Private LLMs through Wavelet-Encoded Look-Up Tables
* Authors: Manuel B. Santos, Dimitris Mouris, Mehmet Ugurbil, Stanislaw Jarecki, José Reis, Shubho Sengupta, Miguel de Vega
* [Permalink](https://eprint.iacr.org/2024/1127)
* [Download](https://eprint.iacr.org/2024/1127.pdf)

### Abstract

Recent advancements in transformers have revolutionized machine learning, forming the core of Large language models (LLMs). However, integrating these systems into everyday applications raises privacy concerns as client queries are exposed to model owners. Secure multiparty computation (MPC) allows parties to evaluate machine learning applications while keeping sensitive user inputs and proprietary models private. Due to inherent MPC costs, recent works introduce model-specific optimizations that hinder widespread adoption by machine learning researchers. CrypTen (NeurIPS'21) aimed to solve this problem by exposing MPC primitives via common machine learning abstractions such as tensors and modular neural networks. Unfortunately, CrypTen and many other MPC frameworks rely on polynomial approximations of the non-linear functions, resulting in high errors and communication complexity.

This paper introduces Curl, an easy-to-use MPC framework that evaluates non-linear functions as lookup tables, resulting in better approximations and significant round and communication reduction. Curl exposes a similar programming model as CrypTen and is highly parallelizable through tensors. At its core, Curl relies on discrete wavelet transformations to reduce the lookup table size without sacrificing accuracy, which results in up to $19\times$ round and communication reduction compared to CrypTen for non-linear functions such as logarithms and reciprocals. We evaluate Curl on a diverse set of LLMs, including BERT, GPT-2, and GPT Neo, and compare against state-of-the-art related works such as Iron (NeurIPS'22) and Bolt (S&P'24) achieving at least $1.9\times$ less communication and latency.

Finally, we resolve a long-standing debate regarding the security of widely used probabilistic truncation protocols by proving their security in the stand-alone model. This is of independent interest as many related works rely on this truncation style.



## 2024/1128

* Title: Cryptiny: Compacting Cryptography for Space-Restricted Channels and its Use-case for IoT-E2EE
* Authors: Liron David, Omer Berkman, Avinatan Hassidim, David Lazarov, Yossi Matias, Moti Yung
* [Permalink](https://eprint.iacr.org/2024/1128)
* [Download](https://eprint.iacr.org/2024/1128.pdf)

### Abstract

We present a novel cryptographic paradigm denoted  ``cryptiny:'' Employing a single cryptographic value for several security goals, thus ``compacting'' the communication sent over a space-restricted (narrow) channel, while still proving security. Cryptiny is contrary to the classical cryptographic convention of using a separate cryptographic element for each security goal.

Demonstrating  the importance of cryptiny, we employ it for securing a critical IoT configuration in which a broadcasting ``thing'' (called beacon) operates within stringent bandwidth constraints. In this setting, a compact BLE-broadcasting beacon lacking Internet connectivity efficiently directs brief (non fragmented) messages to its remotely pre-paired owner in real-time. Communication transpires through BLE-to-IP gateway devices denoted observers, (typically smartphones in the beacon's vicinity), and subsequently via a cloud app server. The gateway device as well, piggybacks on the transmission a secure and private message to the owner. This configuration is a generic setting for the current and future IoT real-time ecosystems, where billion of owners, beacons, and observers operate.

The configuration instances (analogous to TLS instances over the Internet) imposes high security and privacy demands. We prove that our cryptiny-based protocol for securing the above configuration achieves CCA-secrecy for the beacon's and the observer's messages with backward and forward security for the observer's message, as well simultaneously achieving  mutual privacy for beacons and for observers. Achieving backward and forward security is important since beacon devices may be far from their owners for a long duration and may be passively tampered with. In addition, for the backward security proof we develop a new encryption scheme we call ``shifted-DHIES'' (``SDHIES'' for short), which generalizes DHIES. An interesting feature of SDHIES is that encryption is performed with a function of the public key rather than the public key itself.



## 2024/1129

* Title: Attribute-Based Signatures for Circuits with Optimal Parameter Size from Standard Assumptions
* Authors: Ryuya Hayashi, Yusuke Sakai, Shota Yamada
* [Permalink](https://eprint.iacr.org/2024/1129)
* [Download](https://eprint.iacr.org/2024/1129.pdf)

### Abstract

Attribute-based signatures (ABS) allow users to simultaneously sign messages and prove their possession of some attributes while hiding the attributes and revealing only the fact that they satisfy a public policy. In this paper, we propose a generic construction of ABS for circuits of unbounded depth and size with optimal parameter size, meaning that the lengths of public parameters, keys, and signatures are all constant. Our generic construction can be instantiated from various standard assumptions including LWE or DLIN. Only previous ABS construction with optimal parameter size necessitates succinct non-interactive argument of knowledge, which can be only constructed from non-standard assumptions. Our generic construction is based on RAM delegations, which intuitively allows us to compress the evaluation of a circuit when inputs are public. In high level, we find a way to compress the computation of the policy circuit on input a user attribute to achieve overall parameter size, while hiding the user policy at the same time.



## 2024/1130

* Title: Distributed Verifiable Random Function With Compact Proof
* Authors: Ahmet Ramazan Ağırtaş, Arda Buğra Özer, Zülfükar Saygı, Oğuz Yayla
* [Permalink](https://eprint.iacr.org/2024/1130)
* [Download](https://eprint.iacr.org/2024/1130.pdf)

### Abstract

Verifiable Random Functions (VRFs) are cryptographic primitives that generate unpredictable randomness along with proofs that are verifiable, a critical requirement for blockchain applications in decentralized finance, online gaming, and more. Existing VRF constructions often rely on centralized entities, creating security vulnerabilities. Distributed VRFs (DVRFs) offer a decentralized alternative but face challenges like large proof sizes or dependence on computationally expensive bilinear pairings.
In this research, a unique distributed VRF (DVRF) system called DVRFwCP with considerable improvements is proposed. DVRFwCP has constant-size proofs, which means that the size of the proof does not change based on the number of participants. This overcomes a significant drawback of earlier DVRF systems, which saw proof size increase with participant count. Furthermore, DVRFwCP produces more efficient verification than previous systems by eliminating the requirement for bilinear pairings throughout the verification process. These innovations contribute to a more secure and scalable solution for generating verifiable randomness in decentralized environments.
We compare our construction to well-established DVRF instantiations such as DDH-DVRF and GLOW-DVRF while also pointing out the major improvement in the estimated gas cost of these algorithms.



## 2024/1131

* Title: Jolt-b: recursion friendly Jolt with basefold commitment
* Authors: Hang Su, Qi Yang, Zhenfei Zhang
* [Permalink](https://eprint.iacr.org/2024/1131)
* [Download](https://eprint.iacr.org/2024/1131.pdf)

### Abstract

The authors of Jolt [AST24] pioneered a unique method for creating zero-knowledge virtual machines, known as the lookup singularity. This technique extensively uses lookup tables to create virtual machine circuits. Despite Jolt’s performance being twice as efficient as the previous state-of-the-art1 , there is potential for further enhancement.

The initial release of Jolt uses Spartan [Set20] and Hyrax [WTs+ 18] as their backend, leading to two constraints. First, Hyrax employs Pedersen commitment to build inner product arguments, which requires elliptic curve operations. Second, the verification of a Hyrax commitment takes square root time $O(\sqrt{N})$ relative to the circuit size $N$ . This makes the recursive verification of a Jolt proof impractical, as the verification circuit would need to execute all the Hyrax verification logic in-circuit. A later version of Jolt includes Zeromorph [KT23] and HyperKZG as their commitment backend, making the system recursion-friendly, as now the recursive verifier only needs to perform $O(\log N)$ operations, but at the
expense of a need for a trusted setup.

Our scheme, Jolt-b, addresses these issues by transitioning to the extension field of the Goldilocks and using the Basefold commitment scheme [ZCF23], which has an $O(\log^2 N)$ verifier time. This scheme mirrors the modifications of Plonky2 over the original Plonk [GWC19]: it transitions from EC fields to the Goldilocks field; it replaces the EC-based commitment scheme with an encoding-based commitment scheme.

We implemented Jolt-b, along with an optimized version of the Basefold scheme.. Our benchmarks show that at a cost of 2.47x slowdown for the prover, we achieve recursion friendliness for the original Jolt. In comparison with other recursion-friendly Jolt variants, our scheme is 1.24x and 1.52x faster in prover time than the Zeromorph and HyperKZG variants of Jolt, respectively.



## 2024/1132

* Title: A New PPML Paradigm for Quantized Models
* Authors: Tianpei Lu, Bingsheng Zhang, Xiaoyuan Zhang, Kui Ren
* [Permalink](https://eprint.iacr.org/2024/1132)
* [Download](https://eprint.iacr.org/2024/1132.pdf)

### Abstract

Model quantization has become a common practice in machine learning (ML) to improve efficiency and reduce computational/communicational overhead. However, adopting quantization in privacy-preserving machine learning (PPML) remains challenging due to the complex internal structure of quantized operators, which leads to inefficient protocols under the existing PPML frameworks.

In this work, we propose a new PPML paradigm that is tailor-made for and can benefit from quantized models. Our main observation is that lookup tables can ignore the complex internal constructs of any functions which can be used to simplify the quantized operator evaluation. We view the model inference process as a sequence of quantized operators, and each operator is implemented by a lookup table. We then develop an efficient private lookup table evaluation protocol, and its online communication cost is only $\log n$, where $n$ is the size of the lookup table. 
On a single CPU core, our protocol can evaluate $2^{15}$ tables with 8-bit input and 8-bit output per second.

The resulting PPML framework for quantized models offers extremely fast online performance.
 The experimental results demonstrate that our quantization strategy achieves substantial speedups over SOTA PPML solutions, improving the online performance by $40\sim 60 \times$ w.r.t. convolutional neural network (CNN) models, such as AlexNet, VGG16, and ResNet18, and by $10\sim 25 \times$ w.r.t. large language models (LLMs), such as GPT-2, GPT-Neo, and Llama2.



## 2024/1133

* Title: Parameters of Algebraic Representation vs. Efficiency of Algebraic Cryptanalysis
* Authors: Hossein Arabnezhad, Babak Sadeghiyan
* [Permalink](https://eprint.iacr.org/2024/1133)
* [Download](https://eprint.iacr.org/2024/1133.pdf)

### Abstract

The aim of an algebraic attack is to find the secret key by solving
a collection of relations that describe the internal structure of a cipher
for observations of plaintext/cipher-text pairs.
Although algebraic attacks are addressed for cryptanalysis of block and
stream ciphers, there is a limited understanding of the impact of algebraic
representation of the cipher on the efficiency of solving the resulting collection of equations.
In this paper, we investigate on how  different S-box representations affect
the complexity of algebraic attacks, in an empirical manner.
In the literature some algebraic properties are intuitively proposed to evaluate optimality of an algebraic description of S-boxes for algebraic cryptanalysis.
In this paper, we compare different S-box representation for algebraic
cryptanalysis with doing experiments with SR family of block ciphers.
We also show that the so-called \textit{Forward-Backward} representation which is in contrast with all mentioned criteria for optimal representations criteria, practically gives better results than the compliant representations.
We also compare the representations for both  $GF(2)$ and $GF(2^n)$ fields.



## 2024/1134

* Title: Exploiting signature leakages: breaking Enhanced pqsigRM
* Authors: Thomas Debris-Alazard, Pierre Loisel, Valentin Vasseur
* [Permalink](https://eprint.iacr.org/2024/1134)
* [Download](https://eprint.iacr.org/2024/1134.pdf)

### Abstract

Enhanced pqsigRM is a code-based hash-and-sign scheme proposed to the second National Institute of Standards and Technology call for post-quantum signatures. The scheme is based on the $(U,U+V)$-construction and it enjoys remarkably small signature lengths, about $1$KBytes for a security level of $128$ bits.. Unfortunately we show that signatures leak information about the underlying $(U,U+V)$-structure. It allows to retrieve the private-key with~$100, 000$ signatures.



## 2024/1135

* Title: Scalable and Lightweight State-Channel Audits
* Authors: Christian Badertscher, Maxim Jourenko, Dimitris Karakostas, Mario Larangeira
* [Permalink](https://eprint.iacr.org/2024/1135)
* [Download](https://eprint.iacr.org/2024/1135.pdf)

### Abstract

Payment channels are one of the most prominent off-chain scaling solutions for blockchain systems. However, regulatory institutions have difficulty embracing them, as the channels lack insights needed for Anti-Money Laundering (AML) auditing purposes. Our work tackles the problem of a formal reliable and controllable inspection of off-ledger payment channels, by offering a novel approach for maintaining and reliably auditing statistics of payment channels. We extend a typical trustless Layer 2 protocol and provide a lightweight and scalable protocol such that:
        - every state channel is provably auditable w.r.t. a configurable set of policy queries, such that a regulator can retrieve reliable insights about the channel;
        - no information beyond the answers to auditing queries is leaked;
        - the cryptographic operations are inexpensive, the setup is simple, and storage complexity is independent of the transaction graph's size.
    We present a concrete protocol, based on Hydra Isomorphic State Channels (FC'21), and tie the creation of a state channel to real-world identifiers, both in a plain and privacy-preserving manner. For this, we employ verifiable credentials for decentralized identifiers, specifically verifiable Legal Entity Identifiers (vLEI) that increasingly gain traction for financial service providers and regulated institutions.



## 2024/1136

* Title: Probabilistic Linearization: Internal Differential Collisions in up to 6 Rounds of SHA-3
* Authors: Zhongyi Zhang, Chengan Hou, Meicheng Liu
* [Permalink](https://eprint.iacr.org/2024/1136)
* [Download](https://eprint.iacr.org/2024/1136.pdf)

### Abstract

The SHA-3 standard consists of four cryptographic hash functions, called SHA3-224, SHA3-256, SHA3-384 and SHA3-512, and two extendable-output functions (XOFs), called SHAKE128 and SHAKE256.  In this paper, we study the collision resistance of the SHA-3 instances. By analyzing the nonlinear layer, we introduce the concept of maximum difference density subspace, and develop a new target internal difference algorithm by probabilistic linearization. We also exploit new strategies for optimizing the internal differential characteristic. Further more, we figure out the expected size of collision subsets in internal differentials, by analyzing the collision probability of the digests rather than the intermediate states input to the last nonlinear layer. These techniques enhance the analysis of internal differentials, leading to the best collision attacks on four round-reduced variants of the SHA-3 instances. In particular, the number of attacked rounds is extended to 5 from 4 for SHA3-384, and to 6 from 5 for SHAKE256.



## 2024/1137

* Title: Cryptanalysis of EagleSign
* Authors: Ludo N. Pulles, Mehdi Tibouchi
* [Permalink](https://eprint.iacr.org/2024/1137)
* [Download](https://eprint.iacr.org/2024/1137.pdf)

### Abstract

EagleSign is one of the 40 “Round 1 Additional Signatures” that is accepted for consideration in the supplementary round of the Post-Quantum Cryptography standardization process, organized by NIST. Its design is based on structured lattices, and it boasts greater simplicity and performance compared to the two lattice signatures already selected for standardization: Falcon and Dilithium.

In this paper, we show that those claimed advantages come at the cost of security. More precisely, we show that the distribution of EagleSign signatures leaks information about the private key, to the point that only a few hundred signatures on arbitrary known messages suffice for a full key recovery, for all proposed parameters.

A related vulnerability also affects EagleSign-V2, a subsequent version of the scheme specifically designed to thwart the initial attack. Although a larger number of signatures is required for key recovery, the idea of the attack remains largely similar. Both schemes come with proofs of security that we show are flawed.



## 2024/1138

* Title: Dot-Product Proofs and Their Applications
* Authors: Nir Bitansky, Prahladh Harsha, Yuval Ishai, Ron D. Rothblum, David J. Wu
* [Permalink](https://eprint.iacr.org/2024/1138)
* [Download](https://eprint.iacr.org/2024/1138.pdf)

### Abstract

A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement $\mathbf{x}$ and the proof $\boldsymbol{\pi}$ are vectors over a finite field $\mathbb{F}$, and the proof is verified by making a single dot-product query $\langle \mathbf{q},(\mathbf{x} \| \boldsymbol{\pi}) \rangle$ jointly to $\mathbf{x}$ and $\boldsymbol{\pi}$. A DPP can be viewed as a 1-query fully linear PCP. We study the feasibility and efficiency of DPPs, obtaining the following results:

- Small-field DPP. For any finite field $\mathbb{F}$ and Boolean circuit $C$ of size $S$, there is a DPP for proving that there exists $\mathbf{w}$ such that $C(\mathbf{x}, \mathbf{w})=1$ with a proof $\boldsymbol{\pi}$ of length $S\cdot\mathsf{poly}(|\mathbb{F}|)$ and soundness error $\varepsilon=O(1 / \sqrt{|\mathbb{F}|})$. We show this error to be asymptotically optimal. In particular, and in contrast to the best known PCPs, there exist strictly linear-length DPPs over constant-size fields.

- Large-field DPP. If $|\mathbb{F}|\ge\mathsf{poly}(S/\varepsilon)$, there is a similar DPP with soundness error $\varepsilon$ and proof length $O(S)$ (in field elements).

The above results do not rely on the PCP theorem and their proofs are considerably simpler. We apply our DPP constructions toward two kinds of applications.

- Hardness of approximation. We obtain a simple proof for the NP-hardness of approximating MAXLIN (with dense instances) over any finite field $\mathbb{F}$ up to some constant factor $c>1$, independent of $\mathbb{F}$. Unlike previous PCP-based proofs, our proof yields exponential-time hardness under the exponential time hypothesis (ETH).

- Succinct arguments. We improve the concrete efficiency of succinct interactive arguments in the generic group model using input-independent preprocessing. In particular, the communication is comparable to sending two group elements and the verifier's computation is dominated by a single group exponentiation. We also show how to use DPPs together with linear-only encryption to construct succinct commit-and-prove arguments.



## 2024/1139

* Title: Anonymous Outsourced Statekeeping with Reduced Server Storage
* Authors: Dana Dachman-Soled, Esha Ghosh, Mingyu Liang, Ian Miers, Michael Rosenberg
* [Permalink](https://eprint.iacr.org/2024/1139)
* [Download](https://eprint.iacr.org/2024/1139.pdf)

### Abstract

Strike-lists are a common technique for rollback and replay prevention in protocols that require that clients remain anonymous or that their current position in a state machine remain confidential. Strike-lists are heavily used in anonymous credentials, e-cash schemes, and trusted execution environments, and are widely deployed on the web in the form of Privacy Pass (PoPETS '18) and Google Private State Tokens.
In such protocols, clients submit pseudorandom tokens associated with each action (e.g.,  a page view in Privacy Pass) or state transition, and the token is added to a server-side list to prevent reuse.

Unfortunately, the size of a strike-list, and hence the storage required by the server, is proportional to the total number of issued tokens, $N \cdot t$, where $N$ is the number of clients and $t$ is the maximum number of tickets per client. In this work, we ask whether it is possible to realize a strike-list-like functionality, which we call the anonymous tickets functionality, with storage requirements proportional to $N \log(t)$.

For the anonymous tickets functionality we construct a secure protocol from standard assumptions that achieves server storage of $O(N)$ ciphertexts, where each ciphertext encrypts a message of length $O(\log(t))$. We also consider an extension of the strike-list functionality where the server stores an arbitrary state for each client and clients advance their state with some function $s_i\gets f(s_{i-1},\mathsf{auxinput})$, which we call the anonymous outsourced state-keeping functionality. In this setting, malicious clients are prevented from rolling back their state, while honest clients are guaranteed anonymity and confidentiality against a malicious server. We achieve analogous results in this setting for two different classes of functions.

Our results rely on a new technique to preserve client anonymity in the face of selective failure attacks by a malicious server. Specifically, our protocol guarantees that misbehavior of the server either (1) does not prevent the honest client from redeeming a ticket or (2) provides the honest client with an escape hatch that can be used to simulate a redeem in a way that is indistinguishable to the server.



## 2024/1140

* Title: Permutation Superposition Oracles for Quantum Query Lower Bounds
* Authors: Christian Majenz, Giulio Malavolta, Michael Walter
* [Permalink](https://eprint.iacr.org/2024/1140)
* [Download](https://eprint.iacr.org/2024/1140.pdf)

### Abstract

We propose a generalization of Zhandry’s compressed oracle method to random permutations, where an algorithm can query both the permutation and its inverse. We show how to use the resulting oracle simulation to bound the success probability of an algorithm for any predicate on input-output pairs, a key feature of Zhandry’s technique that had hitherto resisted attempts at generalization to random permutations. One key technical ingredient is to use strictly monotone factorizations to represent the permutation in the oracle’s database. As an application of our framework, we show that the one-round sponge construction is unconditionally preimage resistant in the random permutation model. This proves a conjecture by Unruh.



## 2024/1141

* Title: Optimized Privacy-Preserving Clustering with Fully Homomorphic Encryption
* Authors: Chen Yang, Jingwei Chen, Wenyuan Wu, Yong Feng
* [Permalink](https://eprint.iacr.org/2024/1141)
* [Download](https://eprint.iacr.org/2024/1141.pdf)

### Abstract

Clustering is a crucial unsupervised learning method extensively used in the field of data analysis. For analyzing big data, outsourced computation is an effective solution but privacy concerns arise when involving sensitive information. Fully homomorphic encryption (FHE) enables computations on encrypted data, making it ideal for such scenarios. However, existing privacy-preserving clustering based on FHE are often constrained by the high computational overhead incurred from FHE, typically requiring decryption and interactions after only one iteration of the clustering algorithm. In this work, we propose a more efficient approach to evaluate the one-hot vector for the index of the minimum in an array with FHE, which fully exploits the parallelism of single-instruction-multiple-data of FHE schemes. By combining this with FHE bootstrapping, we present a practical FHE-based k-means clustering protocol whose required round of interactions between the data owner and the server is optimal, i..e., accomplishing the entire clustering process on encrypted data in a single round. We implement this protocol using the CKKS FHE scheme. Experiments show that our protocol significantly outperforms the state-of-the-art FHE-based k-means clustering protocols on various public datasets and achieves comparable accuracy to plaintext result. Additionally, We adapt our protocol to support mini-batch k-means for large-scale datasets and report its performance.



## 2024/1142

* Title: Predicting one class of truncated matrix congruential generators with unknown parameters
* Authors: Changcun Wang, Zhaopeng Dai
* [Permalink](https://eprint.iacr.org/2024/1142)
* [Download](https://eprint.iacr.org/2024/1142.pdf)

### Abstract

Matrix congruential generators is an important class of pseudorandom number
generators. In this paper we show how to predict a class of Matrix congruential generators matrix
congruential generators with unknown parameters. Given a few truncated digits
of high-order bits output by a matrix congruential generator, we give a method
based on lattice reduction to recover the parameters and the initial state of the
generator.



## 2024/1143

* Title: LR-OT: Leakage-Resilient Oblivious Transfer
* Authors: Francesco Berti, Carmit Hazay, Itamar Levi
* [Permalink](https://eprint.iacr.org/2024/1143)
* [Download](https://eprint.iacr.org/2024/1143.pdf)

### Abstract

Oblivious Transfer (OT) is a fundamental cryptographic primitive, becoming a crucial component of a practical secure protocol.
OT is typically implemented in software, and one way to accelerate its running time is by using hardware implementations.
However, such implementations are vulnerable to side-channel attacks (SCAs).
On the other hand, protecting interactive protocols against SCA is highly challenging because of their longer secrets (which include inputs and randomness), more complicated design, and running multiple instances.
Consequently, there are no truly practical leakage-resistant OT protocols yet.

In this paper, we introduce two tailored indistinguishability-based security definitions for leakage-resilient OT, focusing on protecting the sender's state.
Second, we propose a practical semi-honest secure OT protocol that achieves these security levels while minimizing the assumptions on the protocol's building blocks and the use of a secret state.
Finally, we extend our protocol to support sequential composition and explore efficiency-security tradeoffs.



## 2024/1144

* Title: A Note on ``Secure and Distributed IoT Data Storage in Clouds Based on Secret  Sharing and Collaborative Blockchain''
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2024/1144)
* [Download](https://eprint.iacr.org/2024/1144.pdf)

### Abstract

We show that the data storage scheme [IEEE/ACM Trans. Netw., 2023, 31(4), 1550-1565] is flawed due to the false  secret sharing protocol, which requires that some random $4\times 4$ matrixes  over the finite field $F_p$ (a prime $p$) are invertible. But we find its mathematical proof for invertibility is incorrect. To fix this flaw, one needs to check the invertibility of all 35 matrixes so as to generate the proper 7 secret shares.



## 2024/1145

* Title: A Practical and Scalable Implementation of the Vernam Cipher, under Shannon Conditions, using Quantum Noise
* Authors: Adrian Neal
* [Permalink](https://eprint.iacr.org/2024/1145)
* [Download](https://eprint.iacr.org/2024/1145.pdf)

### Abstract

The one-time pad cipher is renowned for its theoretical perfect security, yet its practical deployment is primarily hindered by the key-size and distribution challenge. This paper introduces a novel approach to key distribution called q-stream, designed to make symmetric-key cryptography, and the one-time pad cipher in particular, a viable option for contemporary secure communications, and specifically, post-quantum cryptography, leveraging quantum noise and combinatorics to ensure secure and efficient key-distribution between communicating parties.  We demonstrate that our key-distribution mechanism has a variable, yet quantifiable hardness of at least 504 bits, established from immutable mathematical laws, rather than conjectured-intractability, and how we overcome the one-time pad key-size issue with a localised quantum-noise seeded key-generation function, having a system hardness of at least 2304 bits, while introducing sender authentication and message integrity.  Whilst the proposed solution has potential applications in fields requiring very high levels of security, such as military communications and large financial transactions, we show from our research with a prototype of q-stream, that it is sufficiently practical and scaleable for use in common browser-based web-applications, without any modification to the browser (i.e. plug-ins), running above SSL/TLS at the application level, where in tests, it achieved a key-distribution rate of around 7 million keys over a 5 minute surge-window, in a single (multi-threaded) instance of q-stream.



## 2024/1146

* Title: Breaking Free: Efficient Multi-Party Private Set Union Without Non-Collusion Assumptions
* Authors: Minglang Dong, Yu Chen, Cong Zhang, Yujie Bai
* [Permalink](https://eprint.iacr.org/2024/1146)
* [Download](https://eprint.iacr.org/2024/1146.pdf)

### Abstract

Multi-party private set union (MPSU) protocol enables $m$ $(m > 2)$ parties, each holding a set, to collectively compute the union of their sets without revealing any additional information to other parties. There are two main categories of MPSU protocols: The first builds on public-key techniques. All existing works in this category involve a super-linear number of public-key operations, resulting in poor practical efficiency. The second builds on oblivious transfer and symmetric-key techniques. The only existing work in this category is proposed by Liu and Gao (ASIACRYPT 2023), which features the best concrete performance among all existing protocols, despite its super-linear computation and communication. Unfortunately, it does not achieve the standard semi-honest security, as it inherently relies on a non-collusion assumption, which is unlikely to hold in practice. Therefore, the problem of constructing a practical MPSU protocol based on oblivious transfer and symmetric-key techniques in standard semi-honest model remains open. Furthermore, there is no MPSU protocol achieving both linear computation and linear communication complexity, which leaves another unresolved problem. In this work, we resolve these two open problems.

- We propose the first MPSU protocol based on oblivious transfer and symmetric-key techniques in the standard semi-honest model. This protocol is $4.9-9.3 \times$ faster than Liu and Gao in the LAN setting. Concretely, our protocol requires only $3.6$ seconds in online phase for 3 parties with sets of $2^{20}$ items each.
- We propose the first MPSU protocol achieving both linear computation and linear communication complexity, based on public-key operations. This protocol has the lowest overall communication costs and shows a factor of $3.0-36.5\times$ improvement in terms of overall communication compared to Liu and Gao.

We implement our protocols and conduct an extensive experiment to compare the performance of our protocols and the state-of-the-art. To the best of our knowledge, our implementation is the first correct and secure implementation of MPSU that reports on large-size experiments.