[digest] 2024 Week 27

## In this issue

1. [2024/566] A $3$-Round Near-Linear Third-Party Private Set ...
2. [2024/764] Decentralized Multi-Client Functional Encryption ...
3. [2024/1066] VerITAS: Verifying Image Transformations at Scale
4. [2024/1067] Efficient Lattice-Based Threshold Signatures with ...
5. [2024/1068] From Interaction to Independence: zkSNARKs for ...
6. [2024/1069] Strong Existential Unforgeability and More of MPC- ...
7. [2024/1070] Protecting cryptographic code against Spectre-RSB
8. [2024/1071] On the efficient representation of isogenies (a survey)
9. [2024/1072] A Study of Partial Non-Linear Layers with DEFAULT ...
10. [2024/1073] Message Latency in Waku Relay with Rate Limiting ...
11. [2024/1074] Trust Nobody: Privacy-Preserving Proofs for Edited ...
12. [2024/1075] TaSSLE: Lasso for the commitment-phobic
13. [2024/1076] A More Compact AES, and More
14. [2024/1077] Securely Training Decision Trees Efficiently
15. [2024/1078] GAuV: A Graph-Based Automated Verification ...
16. [2024/1079] QuietOT: Lightweight Oblivious Transfer with a ...
17. [2024/1080] Separating Selective Opening Security From Standard ...
18. [2024/1081] Practical Non-interactive Multi-signatures, and a ...
19. [2024/1082] Quantum Implementation of LSH
20. [2024/1083] LEA Block Cipher in Rust Language: Trade-off ...
21. [2024/1084] Enabling Complete Atomicity for Cross-chain ...
22. [2024/1085] Randomized Distributed Function Computation with ...
23. [2024/1086] Obfuscated Key Exchange
24. [2024/1087] Tyche: Probabilistic Selection over Encrypted Data ...
25. [2024/1088] HElix: Genome Similarity Detection in the Encrypted ...
26. [2024/1089] Juliet: A Configurable Processor for Computing on ...
27. [2024/1090] PolyFHEmus: Rethinking Multiplication in Fully ...
28. [2024/1091] MatcHEd: Privacy-Preserving Set Similarity based on ...
29. [2024/1092] Fusion Channel Attack with POI Learning Encoder
30. [2024/1093] Faster Lookup Table Evaluation with Application to ...
31. [2024/1094] Notes on Multiplying Cyclotomic Polynomials on a GPU
32. [2024/1095] Lower Bound on Number of Compression Calls of a ...
33. [2024/1096] Post-Quantum Ready Key Agreement for Aviation
34. [2024/1097] The Cost of Maintaining Keys in Dynamic Groups with ...
35. [2024/1098] Limits of Black-Box Anamorphic Encryption
36. [2024/1099] FHE-MENNs: Opportunities and Pitfalls for ...
37. [2024/1100] Unforgeability of Blind Schnorr in the Limited ...
38. [2024/1101] Stickel’s Protocol using Tropical Increasing Matrices
39. [2024/1102] A Note on ``Privacy Preserving n-Party Scalar ...
40. [2024/1103] A Note on Efficient Computation of the Multilinear ...
41. [2024/1104] Structural Lower Bounds on Black-Box Constructions ...
42. [2024/1105] A New CRT-based Fully Homomorphic Encryption
43. [2024/1106] Masked Vector Sampling for HQC
44. [2024/1107] Phase Modulation Side Channels: Jittery JTAG for ...
45. [2024/1108] Faster Asynchronous Blockchain Consensus and MVBA

## 2024/566

* Title: A $3$-Round Near-Linear Third-Party Private Set Intersection Protocol
* Authors: Foo Yee Yeo, Jason H. M. Ying
* [Permalink](https://eprint.iacr.org/2024/566)
* [Download](https://eprint.iacr.org/2024/566.pdf)

### Abstract

Third-party private set intersection (PSI) enables two parties, each holding a private set to compute their intersection and reveal the result only to an inputless third party. In this paper, we present an efficient third-party PSI protocol requiring only 3 communication rounds, while significantly lowering the computational workload compared to prior work. Our work is motivated by real-world applications such as contact tracing whereby expedition is essential while concurrently preserving privacy. Our construction attains a near-linear computational complexity of $O(n^{1+\varepsilon})$ for large dataset size $n$, where $\varepsilon>0$ is any fixed constant, and achieves post-quantum security. Our improvements stem from algorithmic changes and the incorporation of new techniques along with precise parameter selections to achieve a tight asymptotic bound. Furthermore, we also present a third-party PSI cardinality protocol which has not been explored in prior third-party PSI work. In a third-party PSI cardinality setting, only the third-party obtains the size of the intersection and nothing else. Our construction to achieve the cardinality functionality attains a quasilinear computational complexity for the third-party.



## 2024/764

* Title: Decentralized Multi-Client Functional Encryption with Strong Security
* Authors: Ky Nguyen, David Pointcheval, Robert Schädlich
* [Permalink](https://eprint.iacr.org/2024/764)
* [Download](https://eprint.iacr.org/2024/764.pdf)

### Abstract

Decentralized Multi-Client Functional Encryption (DMCFE) extends the basic functional encryption to multiple clients that do not trust each other. They can independently encrypt the multiple plaintext-inputs to be given for evaluation to the function embedded in the functional decryption key, defined by multiple parameter-inputs. And they keep control on these functions as they all have to contribute to the generation of the functional decryption keys. Tags can be used in the ciphertexts and the keys to specify which inputs can be combined together. As any encryption scheme, DMCFE provides privacy of the plaintexts. But the functions associated to the functional decryption keys might be sensitive too (e.g. a model in machine learning). The function-hiding property has thus been introduced to additionally protect the function evaluated during the decryption process.

  In this paper, we provide new proof techniques to analyze a new concrete construction of function-hiding DMCFE for inner products, with strong security guarantees in the random oracle model: the adversary can adaptively query multiple challenge ciphertexts and multiple challenge keys, with unbounded repetitions of the same message tags in the ciphertext-queries and a fixed polynomially-large number of repetitions of the same key tags in the key-queries, allowing static corruption of the secret encryption keys. Previous constructions were proven secure in the selective setting only.



## 2024/1066

* Title: VerITAS: Verifying Image Transformations at Scale
* Authors: Trisha Datta, Binyi Chen, Dan Boneh
* [Permalink](https://eprint.iacr.org/2024/1066)
* [Download](https://eprint.iacr.org/2024/1066.pdf)

### Abstract

Verifying image provenance has become an important topic, especially in the realm of news media. To address this issue, the Coalition for Content Provenance and Authenticity (C2PA) developed a standard to verify image provenance that relies on digital signatures produced by cameras. However, photos are usually edited before being published, and a signature on an original photo cannot be verified given only the published edited image. In this work, we describe VerITAS, a system that uses zero-knowledge proofs (zk-SNARKs) to prove that only certain edits have been applied to a signed photo.  While past work has created image editing proofs for photos, VerITAS is the first to do so for realistically large images (30 megapixels). Our key innovation  enabling this leap is the design of a new proof system that enables proving knowledge of a valid signature on a large amount of witness data.  We run experiments on realistically large images that are more than an order of magnitude larger than those tested in prior work.   In the case of a computationally weak signer, such as a camera, we are able to generate proofs of valid edits for a 90 MB image in under an hour, costing about \$2.42 on AWS per image.  In the case of a more powerful signer, we are able to generate proofs of valid edits for 90 MB images in under five minutes, costing about \$0.09 on AWS per image. Either way, proof verification time is about 2 seconds in the browser.  Our techniques apply broadly whenever there is a need to prove that an efficient transformation was applied correctly to a large amount of signed private data.



## 2024/1067

* Title: Efficient Lattice-Based Threshold Signatures with Functional Interchangeability
* Authors: Guofeng Tang, Bo Pang, Long Chen, Zhenfeng Zhang
* [Permalink](https://eprint.iacr.org/2024/1067)
* [Download](https://eprint.iacr.org/2024/1067.pdf)

### Abstract

A threshold signature scheme distributes the ability to generate signatures through distributed key generation and signing protocols. A threshold signature scheme should be functionally interchangeable, meaning that a signature produced by a threshold scheme should be verifiable by the same algorithm used for non-threshold signatures. To resist future attacks from quantum adversaries, lattice-based threshold signatures are desirable. However, the performance of existing lattice-based threshold signing protocols is still far from practical.

This paper presents the first lattice-based $t$-out-of-$n$ threshold signature scheme with functional interchangeability that has been implemented. To build an $t$-out-of-$n$ access structure for arbitrary $t \leq n$, we first present a novel $t$-out-of-$n$ version of the SPDZ MPC protocol. We avoid using the MPC protocol to evaluate hash operations for high concrete efficiency. Moreover, we design an efficient distributed rejection sampling protocol. Consequently, the online phase of our distributed signing protocol takes only 0.5 seconds in the two-party setting and 7.3 seconds in the 12-party setting according to our implementation. As a byproduct, our scheme also presents a periodic key refreshment mechanism and offers proactive security.



## 2024/1068

* Title: From Interaction to Independence: zkSNARKs for Transparent and Non-Interactive Remote Attestation
* Authors: Shahriar Ebrahimi, Parisa Hassanizadeh
* [Permalink](https://eprint.iacr.org/2024/1068)
* [Download](https://eprint.iacr.org/2024/1068.pdf)

### Abstract

Remote attestation (RA) protocols have been widely
used to evaluate the integrity of software on remote devices.
Currently, the state-of-the-art RA protocols lack a crucial feature: transparency. This means that the details of the final
attestation verification are not openly accessible or verifiable by
the public. Furthermore, the interactivity of these protocols often
limits attestation to trusted parties who possess privileged access
to confidential device data, such as pre-shared keys and initial
measurements. These constraints impede the widespread adoption
of these protocols in various applications.
In this paper, we introduce zRA, a non-interactive, transparent, and publicly provable RA protocol based on zkSNARKs.
zRA enables verification of device attestations without the need
for pre-shared keys or access to confidential data, ensuring a
trustless and open attestation process. This eliminates the reliance
on online services or secure storage on the verifier side. Moreover,
zRA does not impose any additional security assumptions beyond
the fundamental cryptographic schemes and the essential trust
anchor components on the prover side (i.e., ROM and MPU).
The zero-knowledge attestation proofs generated by devices have
constant size regardless of the network complexity and number
of attestations. Moreover, these proofs do not reveal sensitive
information regarding internal states of the device, allowing verification by anyone in a public and auditable manner. We conduct
an extensive security analysis and demonstrate scalability of zRA
compared to prior work. Our analysis suggests that zRA excels
especially in peer-to-peer and Pub/Sub network structures. To
validate the practicality, we implement an open-source prototype
of zRA using the Circom language. We show that zRA can be
securely deployed on public permissionless blockchains, serving
as an archival platform for attestation data to achieve resilience
against DoS attacks.



## 2024/1069

* Title: Strong Existential Unforgeability and More of MPC-in-the-Head Signatures
* Authors: Mukul Kulkarni, Keita Xagawa
* [Permalink](https://eprint.iacr.org/2024/1069)
* [Download](https://eprint.iacr.org/2024/1069.pdf)

### Abstract

NIST started the standardization of additional post-quantum signatures in 2022. Among 40 candidates, a few of them showed their stronger security than existential unforgeability, strong existential unforgeability and BUFF (beyond unforgeability features) securities. Recently, Aulbach, Düzlü, Meyer, Struck, and Weishäupl (PQCrypto 2024) examined the BUFF securities of 17 out of 40 candidates. Unfortunately, on the so-called MPC-in-the-Head (MPCitH) signature schemes, we have no knowledge of strong existential unforgeability and BUFF securities.

This paper studies the strong securities of all nine MPCitH signature candidates: AIMer, Biscuit, FAEST, MIRA, MiRitH, MQOM, PERK, RYDE, and SDitH.

We show that the MPCitH signature schemes are strongly existentially unforgeable under chosen message attacks in the (quantum) random oracle model. To do so, we introduce a new property of the underlying multi-pass identification, which we call _non-divergency_. This property can be considered as a weakened version of the computational unique response for three-pass identification defined by Kiltz, Lyubashevsky, and Schaffner (EUROCRYPT 2018) and its extension to multi-pass identification defined by Don, Fehr, and Majentz (CRYPTO 2020). In addition, we show that the SSH11 protocol proposed by Sakumoto, Shirai, and Hiwatari (CRYPTO 2011) is _not_ computational unique response, while Don et al. (CRYPTO 2020) claimed it.

We also survey BUFF securities of the nine MPCitH candidates in the quantum random oracle model. In particular, we show that Biscuit and MiRitH do not have some of the BUFF security.



## 2024/1070

* Title: Protecting cryptographic code against Spectre-RSB
* Authors: Santiago Arranz Olmos, Gilles Barthe, Chitchanok Chuengsatiansup, Benjamin Grégoire, Vincent Laporte, Tiago Oliveira, Peter Schwabe, Yuval Yarom, Zhiyuan Zhang
* [Permalink](https://eprint.iacr.org/2024/1070)
* [Download](https://eprint.iacr.org/2024/1070.pdf)

### Abstract

It is fundamental that executing cryptographic software must not leak secrets through side-channels. For software-visible side-channels, it was long believed that "constant-time" programming would be sufficient as a systematic countermeasure. However, this belief was shattered in 2018 by attacks exploiting speculative execution—so called Spectre attacks.
Recent work shows that language support suffices to protect cryptographic code with minimal overhead against one class of such attacks, Spectre v1, but leaves an open question of whether this result can be extended to also cover other classes of Spectre attacks.
In this paper, we answer this question in the affirmative: We design, validate, implement, and verify an approach to protect cryptographic implementations against all known classes of Spectre attacks—the main challenge in this endeavor is attacks exploiting the return stack buffer, which are known as Spectre-RSB. Our approach combines a new value-dependent information-flow type system that enforces speculative constant-time in an idealized model of transient execution and a compiler transformation that realizes this idealized model on the generated low-level code. Using the Coq proof assistant, we prove that the type system is sound with respect to the idealized semantics and that the compiler transformation preserves speculative constant-time.
We implement our approach in the Jasmin framework for high-assurance cryptography and demonstrate that the overhead incurred by full Spectre protections is below 2% for most cryptographic primitives and reaches only about 5–7% for the more complex post-quantum key-encapsulation mechanism Kyber.



## 2024/1071

* Title: On the efficient representation of isogenies (a survey)
* Authors: Damien Robert
* [Permalink](https://eprint.iacr.org/2024/1071)
* [Download](https://eprint.iacr.org/2024/1071.pdf)

### Abstract

We survey different (efficient or not) representations of isogenies, with a particular focus on the recent "higher dimensional" isogeny representation, and algorithms to manipulate them.



## 2024/1072

* Title: A Study of Partial Non-Linear Layers with DEFAULT and BAKSHEESH
* Authors: Anubhab Baksi
* [Permalink](https://eprint.iacr.org/2024/1072)
* [Download](https://eprint.iacr.org/2024/1072.pdf)

### Abstract

In this work, we take a look at the two recently proposed block ciphers, DEFAULT and BAKSHEESH, both of which are descendent of another block cipher named GIFT. We show that both ciphers can be interpreted within the partial non-linear layer category, thanks to the SBoxes having at least one non-trivial linear structure. We also reevaluate the security claim of DEFAULT.



## 2024/1073

* Title: Message Latency in Waku Relay with Rate Limiting Nullifiers
* Authors: Alvaro Revuelta, Sergei Tikhomirov, Aaryamann Challani, Hanno Cornelius, Simon Pierre Vivier
* [Permalink](https://eprint.iacr.org/2024/1073)
* [Download](https://eprint.iacr.org/2024/1073.pdf)

### Abstract

Waku is a privacy-preserving, generalized, and decentralized messaging protocol suite. Waku uses GossipSub for message routing and Rate Limiting Nullifiers (RLN) for spam protection. GossipSub ensures fast and reliable peer-to-peer message delivery in a permissionless environment, while RLN enforces a common publishing rate limit using zero-knowledge proofs.

This paper presents a practical evaluation of message propagation latency in Waku. First, we estimate latencies analytically, building a simple mathematical model for latency under varying conditions. Second, we run a large-scale single-host simulation with 1000 nodes. Third, we set up a multi-host Waku deployment using five nodes in different locations across the world. Finally, we compare our analytical estimations to the results of the simulation and the real-world measurement.

The experimental results are in line with our theoretical model. Under realistic assumptions, medium-sized messages (25 KB) are delivered within 1 second. We conclude that Waku can achieve satisfactory latency for typical use cases, such as decentralized messengers, while providing scalability and anonymity.



## 2024/1074

* Title: Trust Nobody: Privacy-Preserving Proofs for Edited Photos with Your Laptop
* Authors: Pierpaolo Della Monica, Ivan Visconti, Andrea Vitaletti, Marco Zecchini
* [Permalink](https://eprint.iacr.org/2024/1074)
* [Download](https://eprint.iacr.org/2024/1074.pdf)

### Abstract

The Internet has plenty of images that are transformations (e.g., resize, blur) of confidential original images. Several scenarios (e.g., selling images over the Internet, fighting disinformation, detecting deep fakes) would highly benefit from systems allowing to verify that an image is the result of a transformation applied to a confidential authentic image. In this paper, we focus on systems for proving and verifying the correctness of transformations of authentic images guaranteeing: 1) confidentiality (i.e., the original image remains private), 2) efficient proof generation (i.e., the proof certifying the correctness of the transformation can be computed with a common laptop) even for high-resolution images, 3) authenticity (i.e., only the advertised transformations have been applied) and 4) fast detection of fraud proofs. Our contribution consists of the following results:
- We present new definitions following in part the ones proposed by Naveh and Tromer [IEEE S&P 2016] and strengthening them to face more realistic adversaries.
- We propose techniques leveraging the way typical transformations work to then efficiently instantiate ZK-snarks circumventing the major bottlenecks due to claims about large pre-images of cryptographic hashes.
- We present a 1st construction based on an ad-hoc signature scheme and an and-hoc cryptographic hash function, obtaining for the first time all the above 4 properties.
- We present a 2nd construction that, unlike in previous results, works with the signature scheme and cryptographic hash function included in the C2PA specifications.
Experimental results confirm the viability of our approach: in our 1st construction, an authentic transformation (e.g., a resize or a crop) of a high-resolution image of 30 MP can be generated on a common 8 cores PC in about 41 minutes employing less than 4 GB of RAM. Our 2nd construction is roughly one order of magnitude slower than our 1st construction. Prior results instead either require expensive computing resources or provide unsatisfying confidentiality.



## 2024/1075

* Title: TaSSLE: Lasso for the commitment-phobic
* Authors: Daniel Dore
* [Permalink](https://eprint.iacr.org/2024/1075)
* [Download](https://eprint.iacr.org/2024/1075.pdf)

### Abstract

We present TaSSLE, a new lookup argument for decomposable tables with minimal commitment costs. The construction generalizes techniques introduced in Lasso (Eurocrypt '24) which take advantage of the internal structure present in such tables to avoid the need for any party to need to commit to, or even construct, the entire table. This allows the use of lookups against very large tables, with applications including new design strategies for "zero-knowledge virtual machines". We show that these techniques may be combined in a generic way with any existing lookup argument to achieve similar results. We then give a construction of TaSSLE by applying this observation to a recent lookup argument, introduced in [Papini-Haböck '23], which combines logarithmic derivatives with the GKR protocol to achieve a lookup argument with minimal commitment costs.



## 2024/1076

* Title: A More Compact AES, and More
* Authors: Dag Arne Osvik, David Canright
* [Permalink](https://eprint.iacr.org/2024/1076)
* [Download](https://eprint.iacr.org/2024/1076.pdf)

### Abstract

We reduce the number of bit operations required to implement AES to a new minimum, and also compute improvements to elements of some other ciphers. Exploring the algebra of AES allows choices of basis and streamlining of the nonlinear parts. We also compute a more efficient implementation of the linear part of each round. Similar computational optimizations apply to other cryptographic matrices and S-boxes. This work may be incorporated into a hardware AES implementation using minimal resources, or potentially in a bit-sliced software implementation to increase speed.



## 2024/1077

* Title: Securely Training Decision Trees Efficiently
* Authors: Divyanshu Bhardwaj, Sandhya Saravanan, Nishanth Chandran, Divya Gupta
* [Permalink](https://eprint.iacr.org/2024/1077)
* [Download](https://eprint.iacr.org/2024/1077.pdf)

### Abstract

Decision trees are an important class of supervised learning algorithms. When multiple entities contribute data to train a decision tree (e.g. for fraud detection in the financial sector), data privacy concerns necessitate the use of a privacy-enhancing technology such as secure multi-party computation (MPC) in order to secure the underlying training data. Prior state-of-the-art (Hamada et al.)  construct an MPC protocol for decision tree training with a communication of $\mathcal{O}(hmN\log N)$, when building a decision tree of height $h$ for a training dataset of $N$ samples, each having $m$ attributes.

In this work, we significantly reduce the communication complexity of secure decision tree training.
We construct a protocol with communication complexity $\mathcal{O}(mN\log N + hmN + hN\log N)$, thereby achieving an improvement of $\approx \mathsf{min}(h, m, \log N)$ over Hamada et al.
At the core of our technique is an improved protocol to regroup sorted private elements further into additional groups (according to a flag vector) while maintaining their relative ordering. We implement our protocol in the MP-SPDZ framework and show that it requires $10\times$ lesser communication and is $9\times$ faster than the state-of-the-art.



## 2024/1078

* Title: GAuV: A Graph-Based Automated Verification Framework for Perfect Semi-Honest Security of Multiparty Computation Protocols
* Authors: Xingyu Xie, Yifei Li, Wei Zhang, Tuowei Wang, Shizhen Xu, Jun Zhu, Yifan Song
* [Permalink](https://eprint.iacr.org/2024/1078)
* [Download](https://eprint.iacr.org/2024/1078.pdf)

### Abstract

Proving the security of a Multiparty Computation (MPC) protocol is a difficult task. Under the current simulation-based definition of MPC, a security proof consists of a simulator, which is usually specific to the concrete protocol and requires to be manually constructed, together with a theoretical analysis of the output distribution of the simulator and corrupted parties' views in the real world. This presents an obstacle in verifying the security of a given MPC protocol. Moreover, an instance of a secure MPC protocol can easily lose its security guarantee due to careless implementation, and such a security issue is hard to detect in practice.

In this work, we propose a general automated framework to verify the perfect security of instances of MPC protocols against the semi-honest adversary. Our framework has perfect soundness: any protocol that is proven secure under our framework is also secure under the simulation-based definition of MPC. We demonstrate the completeness of our framework by showing that for any instance of the well-known BGW protocol, our framework can prove its security for every corrupted party set with polynomial time. Unlike prior work that only focuses on black-box privacy which requires the outputs of corrupted parties to contain no information about the inputs of the honest parties, our framework may potentially be used to prove the security of arbitrary MPC protocols.

We implement our framework as a prototype. The evaluation shows that our prototype automatically proves the perfect semi-honest security of BGW protocols and B2A (binary to arithmetic) conversion protocols in reasonable durations.



## 2024/1079

* Title: QuietOT: Lightweight Oblivious Transfer with a Public-Key Setup
* Authors: Geoffroy Couteau, Lalita Devadas, Srinivas Devadas, Alexander Koch, Sacha Servan-Schreiber
* [Permalink](https://eprint.iacr.org/2024/1079)
* [Download](https://eprint.iacr.org/2024/1079.pdf)

### Abstract

Oblivious Transfer (OT) is at the heart of secure computation and is a foundation for many applications in cryptography. Over two decades of work have led to extremely efficient protocols for evaluating OT instances in the preprocessing model, through a paradigm called OT extension.
A few OT instances generated in an offline phase can be used to perform many OTs in an online phase efficiently, i.e., with very low communication and computational overheads.

Specifically, traditional OT extension protocols use a small number of “base” OTs, generated using any black-box OT protocol, and convert them into many OT instances using only lightweight symmetric-key primitives.
Recently, a new paradigm of OT with a *public-key setup* has emerged, which replaces the base OTs with a non-interactive setup: Using only the public key of the other party, two parties can efficiently compute a virtually unbounded number of OT instances on-the-fly.

In this paper, we put forth a novel framework for OT extension with a public-key setup and concretely efficient instantiations. An implementation of our framework is over 20 times faster when compared to the previous state-of-the-art public-key OT protocols, and remains competitive even when compared to OT protocols that *do not* offer a public-key setup. Additionally, our instantiations result in the first public-key schemes with plausible post-quantum security.

In summary, this paper contributes:

- QuietOT: A framework for OT extension with a public-key setup that uses fast, symmetric-key primitives to generate OT instances following a one-time public-key setup, and offering additional features such as precomputability.

- A public-key setup for QuietOT from the RingLWE assumption, resulting in the first post-quantum construction of OT extension with a public-key setup.

- An optimized, open-source implementation of our construction that can generate up to 1M OT extensions per second on commodity hardware. In contrast, the state-of-the-art public-key OT protocol is limited to at most 65K OTs per second.

- The first formal treatment of the security of OT with a public-key setup in a multi-party setting, which addresses several subtleties that were overlooked in prior work.



## 2024/1080

* Title: Separating Selective Opening Security From Standard Security, Assuming IO
* Authors: Justin Holmgren, Brent Waters
* [Permalink](https://eprint.iacr.org/2024/1080)
* [Download](https://eprint.iacr.org/2024/1080.pdf)

### Abstract

Assuming the hardness of LWE and the existence of IO, we construct a public-key encryption scheme that is IND-CCA secure but fails to satisfy even a weak notion of indistinguishability security with respect to selective opening attacks.  Prior to our work, such a separation was known only from stronger assumptions such as differing inputs obfuscation (Hofheinz, Rao, and Wichs, PKC 2016).

Central to our separation is a new hash family, which may be of independent interest.  Specifically, for any $S(k) = k^{O(1)}$, any $n(k) = k^{O(1)}$, and any $m(k) = k^{\Theta(1)}$, we construct a hash family mapping $n(k)$ bits to $m(k)$ bits that is somewhere statistically correlation intractable (SS-CI) for all relations $R_k \subseteq \{0,1\}^{n(k)} \times \{0,1\}^{m(k)}$ that are enumerable by circuits of size $S(k)$.

We give two constructions of such a hash family.  Our first construction uses IO, and generically ``boosts'' any hash family that is SS-CI for the smaller class of functions that are computable by circuits of size $S(k)$.  This weaker hash variant can be constructed based solely on LWE (Peikert and Shiehian, CRYPTO 2019).  Our second construction is based on the existence of a circular secure FHE scheme, and follows the construction of Canetti et al. (STOC 2019).



## 2024/1081

* Title: Practical Non-interactive Multi-signatures, and a Multi-to-Aggregate Signatures Compiler
* Authors: Matthieu Rambaud, Christophe Levrat
* [Permalink](https://eprint.iacr.org/2024/1081)
* [Download](https://eprint.iacr.org/2024/1081.pdf)

### Abstract

In a fully non-interactive multi-signature, resp. aggregate-signature scheme (fNIM, resp. fNIA), signatures issued by many signers on the same message, resp. on different messages, can be succinctly ``combined'', resp. ``aggregated''.
fNIMs are used in the Ethereum consensus protocol, to produce the certificates of validity of blocks which are to be verified by billions of clients. fNIAs are used in some PBFT-like consensus protocols, such as the production version of Diem by Aptos, to replace the forwarding of many signatures by a new leader. In this work we address three complexity bottlenecks.
(i) fNIAs are costlier than fNIMs, e.g., we observe that verification time of a 3000-wise aggregate signature of BGLS (Eurocrypt'03), takes 300x longer verification time than verification of a 3000-wise pairing-based multisignature.
(ii) fNIMs impose that each verifier processes the setup published by the group of potential signers. This processing consists either in verifying proofs of possession (PoPs), such as in Pixel (Usenix'20) and in the IETF'22 draft inherited from Ristenpart-Yilek (Eurocrypt'07), which costs a product of pairings over all published keys. Or, it consists in re-randomizing the keys, such as in SMSKR (FC'24).
(iii) Existing proven security bounds on efficient fNIMs do not give any guarantee in practical curves with 256bits-large groups, such as BLS12-381 (used in Ethereum) or BLS12-377 (used in Zexe). Thus, computing in much larger curves is required to have provable guarantees.

Our first contribution is a new fNIM called $\mathsf{dms}$, it addresses both (ii) and (iii).
It is as simple as adding Schnorr PoPs to the schoolbook pairing-based fNIM of Boldyreva (PKC'03).
(ii) For a group of 1000 signers, verification of these PoPs is: $5+$ times faster than for the previous pairing-based PoPs; and $3+$ times faster than the Verifier's processing of the setup in SMSKR (and contrary to the latter, needs not be re-started when a new member joins the group).
(iii) We prove a tight reduction to the discrete logarithm (DL), in the algebraic group model (AGM). Given the current estimation of roughly 128 bits of security for the DL in both the curves BLS12-381 and BLS12-377, we deduce a probability of forgery of $\mathsf{dms}$ no higher than about $2^{-93}$ for a time $2^{80}$ adversary.
This reduction is our main technical contribution. The only related proof before was for an interactive Schnorr-based multi-signature scheme, using Schnorr PoPs. Our approach easily fills a gap in this proof, since we take into account that the adversary has access to a signing oracle even before publishing its PoPs. But in our context of pairing-based multi-signatures, extraction of the keys of the adversary is significantly more complicated, since the signing oracle produces a correlated random string.
We finally provide another application of $\mathsf{dms}$, which is that it can be plugged in recent threshold signatures without setup (presented by Das et al at CCS'23, and Garg et al at SP'24), since these schemes implicitly build on any arbitrary BLS-based fNIM.

Our second contribution addresses (i), it is a very simple compiler: $\mathcal{M}to\mathcal{A}$ (multi-to-aggregate). It turns any fNIM into an fNIA, suitable for aggregation of signatures on messages with a prefix in common, with the restriction that a signer must not sign twice using the same prefix. The resulting fNIA is post-quantum secure as soon as the fNIM is, such as Chipmunk (CCS'23). We demonstrate the relevance for Diem by applying $\mathcal{M}to\mathcal{A}$ to $\mathsf{dms}$: the resulting fNIA enables to verify 39x faster an aggregate of 129 signatures, over messages with $7$ bits-long variable parts, than BGLS.



## 2024/1082

* Title: Quantum Implementation of LSH
* Authors: Yujin Oh, Kyungbae Jang, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2024/1082)
* [Download](https://eprint.iacr.org/2024/1082.pdf)

### Abstract

As quantum computing progresses, the assessment of cryptographic algorithm resilience against quantum attack gains significance interests in the field of cryptanalysis. Consequently, this paper implements the depth-optimized quantum circuit of Korean hash function (i.e., LSH) and estimates its quantum attack cost in quantum circuits. By utilizing an optimized quantum adder and employing parallelization techniques, the proposed quantum circuit achieves a 78.8\% improvement in full depth and a 79.1\% improvement in Toffoli depth compared to previous the-state-of art works.
In conclusion, based on the implemented quantum circuit, we estimate the resources required for a Grover collision attack and evaluate the post-quantum security of LSH algorithms.



## 2024/1083

* Title: LEA Block Cipher in Rust Language: Trade-off between Memory Safety and Performance
* Authors: Sangwon Kim, Siwoo Eum, Minho Song, Hwajeong Seo
* [Permalink](https://eprint.iacr.org/2024/1083)
* [Download](https://eprint.iacr.org/2024/1083.pdf)

### Abstract

Cryptography implementations of block cipher have been  written in C language due to its strong features on system-friendly features. However, the C language  is prone to memory safety issues, such as buffer overflows and memory leaks. On the other hand, Rust, novel system programming language, provides strict compile-time memory safety guarantees through its ownership model. This paper presents the implementation of LEA block cipher in Rust language, demonstrating  features to prevent common memory vulnerabilities while maintaining performance. We compare the Rust implementation with the traditional C language version, showing that while Rust incurs a reasonable memory overhead, it achieves comparable the execution timing of encryption and decryption. Our results highlight Rust’s suitability for secure cryptographic applications, striking the balance between memory safety and execution efficiency.



## 2024/1084

* Title: Enabling Complete Atomicity for Cross-chain Applications Through Layered State Commitments
* Authors: Yuandi Cai, Ru Cheng, Yifan Zhou, Shijie Zhang, Jiang Xiao, Hai Jin
* [Permalink](https://eprint.iacr.org/2024/1084)
* [Download](https://eprint.iacr.org/2024/1084.pdf)

### Abstract

Cross-chain Decentralized Applications (dApps) are increasingly popular for their ability to handle complex tasks across various blockchains, extending beyond simple asset transfers or swaps. However, ensuring all dependent transactions execute correctly together, known as complete atomicity, remains a challenge. Existing works provide financial atomicity, protecting against monetary loss, but lack the ability to ensure correctness for complex tasks. In this paper, we introduce Avalon, a transaction execution framework for cross-chain dApps that guarantees complete atomicity for the first time. Avalon achieves this by introducing multiple state layers above the native one to cache state transitions, allowing for efficient management of these state transitions. Most notably, for concurrent cross-chain transactions, Avalon resolves not only intra-chain conflicts but also addresses potential inconsistencies between blockchains via a novel state synchronization protocol, enabling serializable cross-chain execution. We implement Avalon using smart contracts in Cosmos ecosystem and evaluate its commitment performance, demonstrating acceptable latency and gas consumption even under conflict cases.



## 2024/1085

* Title: Randomized Distributed Function Computation with Semantic Communications: Applications to Privacy
* Authors: Onur Gunlu
* [Permalink](https://eprint.iacr.org/2024/1085)
* [Download](https://eprint.iacr.org/2024/1085.pdf)

### Abstract

Randomized distributed function computation refers to remote function computation where transmitters send data to receivers which compute function outputs that are randomized functions of the inputs. We study the applications of semantic communications in randomized distributed function computation to illustrate significant reductions in the communication load, with a particular focus on privacy. The semantic communication framework leverages generalized remote source coding methods, where the remote source is a randomized version of the observed data. Since satisfying security and privacy constraints generally require a randomization step, semantic communication methods can be applied to such function computation problems, where the goal is to remotely simulate a sequence at the receiver such that the transmitter and receiver sequences follow a target probability distribution. Our performance metrics guarantee (local differential) privacy for each input sequence, used in two different distributed function computation problems, which is possible by using strong coordination methods.

This work provides lower bounds on Wyner's common information (WCI), which is one of the two corner points of the coordination-randomness rate region characterizing the ultimate limits of randomized distributed function computation.. The WCI corresponds to the case when there is no common randomness shared by the transmitter and receiver. Moreover, numerical methods are proposed to compute the other corner point for continuous-valued random variables, for which an unlimited amount of common randomness is available. Results for two problems of practical interest illustrate that leveraging common randomness can decrease the communication load as compared to the WCI corner point significantly. We also illustrate that semantic communication gains over lossless compression methods are achieved also without common randomness, motivating further research on limited common randomness scenarios.



## 2024/1086

* Title: Obfuscated Key Exchange
* Authors: Felix Günther, Douglas Stebila, Shannon Veitch
* [Permalink](https://eprint.iacr.org/2024/1086)
* [Download](https://eprint.iacr.org/2024/1086.pdf)

### Abstract

Censorship circumvention tools enable clients to access endpoints in a network despite the presence of a censor. Censors use a variety of techniques to identify content they wish to block, including filtering traffic patterns that are characteristic of proxy or circumvention protocols and actively probing potential proxy servers. Circumvention practitioners have developed fully encrypted protocols (FEPs), intended to have traffic that appears indistinguishable from random. A FEP is typically composed of a key exchange protocol to establish shared secret keys, and then a secure channel protocol to encrypt application data; both must avoid revealing to observers that an obfuscated protocol is in use.

We formalize the notion of obfuscated key exchange, capturing the requirement that a key exchange protocol's traffic "looks random" and that it resists active probing attacks, in addition to ensuring secure session keys and authentication. We show that the Tor network's obfs4 protocol satisfies this definition. We then show how to extend the obfs4 design to defend against stronger censorship attacks and present a quantum-safe obfuscated key exchange protocol.. To instantiate our quantum-safe protocol using the ML-KEM (Kyber) standard, we present Kemeleon, a new mapping between ML-KEM public keys/ciphertexts and uniform byte strings.



## 2024/1087

* Title: Tyche: Probabilistic Selection over Encrypted Data for Generative Language Models
* Authors: Lars Folkerts, Nektarios Georgios Tsoutsos
* [Permalink](https://eprint.iacr.org/2024/1087)
* [Download](https://eprint.iacr.org/2024/1087.pdf)

### Abstract

Generative AI, a significant technological disruptor in recent years, has impacted domains like augmented reality, coding assistance, and text generation. However, use of these models requires users to trust the model owners with their sensitive data given as input to the model.  Fully Homomorphic Encryption (FHE) offers a promising solution, and many earlier works have investigated the use this technology for machine learning as a service (MLaaS) applications. Still, these efforts do not cater to generative models that operate probabilistically, allowing for diverse and creative outputs. In this work, we introduce three novel probabilistic selection algorithms for autoregressive generative AI: multiplication-scaled cumulative sum, heuristic cumulative sum, and the random-multiplication argmax. Each of these approaches presents distinctive challenges in optimizing the trade-off between precision and timing performance, a balance intricately tied to the specific characteristics of the data under consideration. Our results show that the random multiplication argmax-based method is more scalable than the cumulative sum methods and can accurately mimic the plaintext selection curve.



## 2024/1088

* Title: HElix: Genome Similarity Detection in the Encrypted Domain
* Authors: Rostin Shokri, Charles Gouert, Nektarios Georgios Tsoutsos
* [Permalink](https://eprint.iacr.org/2024/1088)
* [Download](https://eprint.iacr.org/2024/1088.pdf)

### Abstract

As the field of genomics continues to expand and more sequencing data is gathered, genome analysis becomes increasingly relevant for many users. For example, a common scenario entails users trying to determine if their DNA samples are similar to DNA sequences hosted in a larger remote repository. Nevertheless, end users may be reluctant to upload their DNA sequences, while the owners of remote genomics repositories are unwilling to openly share their database. To address this challenge, we propose two distinct approaches based on fully homomorphic encryption to preserve the privacy of the genomic data and enable queries directly on ciphertexts. The first is based on the ubiquitous MinHash algorithm and can determine if similar matches exist in the database, while the second involves a bespoke bloom filter construction for determining exact matches. We validate both approaches across various database sizes using both GPU and CPU-based cloud servers.



## 2024/1089

* Title: Juliet: A Configurable Processor for Computing on Encrypted Data
* Authors: Charles Gouert, Dimitris Mouris, Nektarios Georgios Tsoutsos
* [Permalink](https://eprint.iacr.org/2024/1089)
* [Download](https://eprint.iacr.org/2024/1089.pdf)

### Abstract

Fully homomorphic encryption (FHE) has become progressively more viable in the years since its original inception in 2009. At the same time, leveraging state-of-the-art schemes in an efficient way for general computation remains prohibitively difficult for the average programmer. In this work, we introduce a new design for a fully homomorphic processor, dubbed Juliet, to enable faster operations on encrypted data using the state-of-the-art TFHE and cuFHE libraries for both CPU and GPU evaluation. To improve usability, we define an expressive assembly language and instruction set architecture (ISA) judiciously designed for end-to-end encrypted computation. We demonstrate Juliet's capabilities with a broad range of realistic benchmarks including cryptographic algorithms, such as the lightweight ciphers Simon and Speck, as well as logistic regression (LR) inference and matrix multiplication.



## 2024/1090

* Title: PolyFHEmus: Rethinking Multiplication in Fully Homomorphic Encryption
* Authors: Charles Gouert, Nektarios Georgios Tsoutsos
* [Permalink](https://eprint.iacr.org/2024/1090)
* [Download](https://eprint.iacr.org/2024/1090.pdf)

### Abstract

Homomorphic encryption is a powerful technology that solves key privacy concerns in cloud computing by enabling computation on encrypted data. However, it has not seen widespread adoption due to prohibitively high latencies. In this article, we identify polynomial multiplication as a bottleneck and investigate alternative algorithms to accelerate encrypted computing.



## 2024/1091

* Title: MatcHEd: Privacy-Preserving Set Similarity based on MinHash
* Authors: Rostin Shokri, Charles Gouert, Nektarios Georgios Tsoutsos
* [Permalink](https://eprint.iacr.org/2024/1091)
* [Download](https://eprint.iacr.org/2024/1091.pdf)

### Abstract

Fully homomorphic encryption (FHE) enables arbitrary computation on encrypted data, but certain applications remain prohibitively expensive in the encrypted domain. As a case in point, comparing two encrypted sets of data is extremely computationally expensive due to the large number of comparison operators required. In this work, we propose a novel methodology for encrypted set similarity inspired by the MinHash algorithm and the CGGI FHE scheme. Doing comparisons in FHE requires comparators and multiplexers or an expensive approximation, which further increases the latency, especially when the goal is to compare two sets of data. The MinHash algorithm can significantly reduce the number of comparisons required by employing a special Carter-Wegman (CW) hash function as a key building block. However, the modulus operation in the CW hash becomes another key bottleneck because the encrypted sub-circuits required to perform the modular reduction are very large and inefficient in an FHE setting. Towards that end, we introduce an efficient bitwise FHE-friendly digest function (FFD) to employ as the cornerstone of our proposed encrypted set-similarity. In a Boolean FHE scheme like CGGI, the bitwise operations can be implemented efficiently with Boolean gates, which allows for faster evaluation times relative to standard Carter-Wegman constructions. Overall, our approach drastically reduces the number of comparisons required relative to the baseline approach of directly computing the Jaccard similarity coefficients, and is inherently parallelizable, allowing for efficient encrypted computation on multi-CPU and GPU-based cloud servers. We validate our approach by performing a privacy-preserving plagiarism detection across encrypted documents.



## 2024/1092

* Title: Fusion Channel Attack with POI Learning Encoder
* Authors: Xinyao Li, Xiwen Ren, Ling Ning, Changhai Ou
* [Permalink](https://eprint.iacr.org/2024/1092)
* [Download](https://eprint.iacr.org/2024/1092.pdf)

### Abstract

In order to challenge the security of cryptographic systems, Side-Channel Attacks exploit data leaks such as power consumption and electromagnetic emissions. Classic Side-Channel Attacks, which mainly focus on mono-channel data, fail to utilize the joint information of multi-channel data. However, previous studies of multi-channel attacks have often been limited in how they process and adapt to dynamic data. Furthermore, the different data types from various channels make it difficult to use them effectively. This study introduces the Fusion Channel Attack with POI Learning Encoder (FCA), which employs a set of POI Learning encoders that learn the inverse base transformation function family and project the data of each channel into a unified fusion latent space. Furthermore, our method introduces an optimal transport theory based metric for evaluating feature space fusion, which is used to assess the differences in feature spaces between channels. This model not only enhances the ability to process and interpret multi-source data, but also significantly improves the accuracy and applicability of SCAs in different environments.



## 2024/1093

* Title: Faster Lookup Table Evaluation with Application to  Secure LLM Inference
* Authors: Xiaoyang Hou, Jian Liu, Jingyu Li, Jiawen Zhang, Kui Ren
* [Permalink](https://eprint.iacr.org/2024/1093)
* [Download](https://eprint.iacr.org/2024/1093.pdf)

### Abstract

As large language models (LLMs) continue to gain popularity, concerns about user privacy are amplified, given that the data submitted by users for inference may contain sensitive information. Therefore, running LLMs through secure two-party computation (a.k.a. secure LLM inference) has emerged as a prominent topic. However, many operations in LLMs, such as Softmax and GELU, cannot be computed using conventional gates in secure computation; instead, lookup tables (LUTs) have to be utilized, which makes LUT to be an essential primitive in secure LLM inference.

In this paper, we propose $\mathsf{ROTL}$, a secure two-party protocol for LUT evaluations. Compared with FLUTE (the state-of-the-art LUT presented at  Oakland '23), it achieves upto  11.6$\times$ speedup in terms of overall performance and 155$\times$ speedup in terms of online performance. Furthermore, $\mathsf{ROTL}$ can support arithmetic shares (which is required by secure LLM inference), whereas FLUTE can only support boolean shares. At the heart of $\mathsf{ROTL}$ is a novel protocol for secret-shared rotation, which allows two parties to generate additive shares of the rotated table without revealing the rotation offset. We believe this protocol is of independent interest. Based on $\mathsf{ROTL}$, we design a novel secure comparison protocol; compared with the state-of-the-art, it achieves a 2.4$\times$ bandwidth reduction in terms of online performance.

To support boolean shares, we further provide an optimization for FLUTE, by reducing its computational complexity from $O(l\cdot n^2)$ to $O(n\log n+l\cdot n)$ and shifting $O(n\log n)$ computation to the preprocessing phase. As a result, compared with FLUTE, it achieves upto 10.8$\times$ speedup in terms of overall performance and 962$\times$ speedup in terms of online performance.



## 2024/1094

* Title: Notes on Multiplying Cyclotomic Polynomials on a GPU
* Authors: Joseph Johnston
* [Permalink](https://eprint.iacr.org/2024/1094)
* [Download](https://eprint.iacr.org/2024/1094.pdf)

### Abstract

Lattice cryptography has many exciting applications, from homomorphic encryption to zero knowledge proofs. We explore the algebra of cyclotomic polynomials underlying many practical lattice cryptography constructions, and we explore algorithms for multiplying cyclotomic polynomials on a GPU.



## 2024/1095

* Title: Lower Bound on Number of Compression Calls of a Collision-Resistance Preserving Hash
* Authors: Debasmita Chakraborty, Mridul Nandi
* [Permalink](https://eprint.iacr.org/2024/1095)
* [Download](https://eprint.iacr.org/2024/1095.pdf)

### Abstract

The collision-resistant hash function is an early cryptographic primitive
that finds extensive use in various applications. Remarkably, the Merkle-Damgård
and Merkle tree hash structures possess the collision-resistance preserving property,
meaning the hash function remains collision-resistant when the underlying compression function is collision-resistant. This raises the intriguing question of whether reducing the number of underlying compression function calls with the collision-resistance preserving property is possible. In pursuit of addressing these inquiries, we prove that for an ℓn-to-sn-bit collision-resistance preserving hash function designed using r tn-to-n-bit compression function calls, we must have r ≥ ⌈(ℓ−s)/(t−1)⌉. Throughout the paper, all operations other than the compression function are assumed to be linear (which we call linear hash mode).



## 2024/1096

* Title: Post-Quantum Ready Key Agreement for Aviation
* Authors: Marcel Tiepelt, Christian Martin, Nils Maeurer
* [Permalink](https://eprint.iacr.org/2024/1096)
* [Download](https://eprint.iacr.org/2024/1096.pdf)

### Abstract

Transitioning from classically to quantum secure key agreement protocols may require to exchange fundamental components, for example, exchanging Diffie-Hellman-like key exchange with a key encapsulation mechanism (KEM). Accordingly, the corresponding security proof can no longer rely on the Diffie-Hellman assumption,  thus invalidating the security guarantees. As a consequence, the security properties have to be re-proven under a KEM-based security notion.
We initiate the study of the LDACS key agreement protocol (Edition 01.01.00 from 25.04.2023),  which is soon-to-be-standardized by the International Civil Aviation Organization.  The protocol's cipher suite features Diffie-Hellman as well as a KEM-based key agreement protocol to provide post-quantum security.  While the former results in an instantiation of an ISO key agreement inheriting all security properties, the security achieved by the latter is ambiguous.
We formalize the computational security using the systematic notions of de Saint Guilhem, Fischlin and Warinshi (CSF '20), and prove the exact security that the KEM-based variant achieves in this model; primarily entity authentication, key secrecy and key authentication. To further strengthen our ``pen-and-paper'' findings,  we model the protocol and its security guarantees using Tamarin, providing an automated proof of the security against a Dolev-Yao attacker.



## 2024/1097

* Title: The Cost of Maintaining Keys in Dynamic Groups with Applications to Multicast Encryption and Group Messaging
* Authors: Michael Anastos, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval, Matthew Kwan, Guillermo Pascual-Perez, Krzysztof Pietrzak
* [Permalink](https://eprint.iacr.org/2024/1097)
* [Download](https://eprint.iacr.org/2024/1097.pdf)

### Abstract

In this work we prove lower bounds on the (communication) cost of maintaining a shared key among a dynamic group of users.
Being "dynamic'' means one can add and remove users from the group.
This captures important protocols like multicast encryption (ME) and continuous group-key agreement (CGKA), which is the primitive underlying many group messaging applications.

We prove our bounds in a combinatorial setting where the state of the protocol progresses in rounds.
The state of the protocol in each round is captured by a set system, with each of its elements specifying a set of users who share a secret key.
We show this combinatorial model implies bounds in symbolic models for ME and CGKA that capture, as building blocks, PRGs, PRFs, dual PRFs, secret sharing, and symmetric encryption in the setting of ME, and PRGs, PRFs, dual PRFs, secret sharing, public-key encryption, and key-updatable public-key encryption in the setting of CGKA.
The models are related to the ones used by Micciancio and Panjwani (Eurocrypt'04) and Bienstock et al. (TCC'20) to analyze ME and CGKA, respectively.

We prove - using the Bollobás' Set Pairs Inequality - that the cost (number of uploaded ciphertexts) for replacing a set of $d$ users in a group of size $n$ is $\Omega(d\ln(n/d))$.
Our lower bound is asymptotically tight and both improves on a bound of $\Omega(d)$ by Bienstock et al. (TCC'20), and generalizes a result by Micciancio and Panjwani (Eurocrypt'04), who proved a lower bound of $\Omega(\log(n))$ for $d=1$.



## 2024/1098

* Title: Limits of Black-Box Anamorphic Encryption
* Authors: Dario Catalano, Emanuele Giunta, Francesco Migliaro
* [Permalink](https://eprint.iacr.org/2024/1098)
* [Download](https://eprint.iacr.org/2024/1098.pdf)

### Abstract

(Receiver) Anamorphic encryption, introduced by Persiano $ \textit{et al.}$ at Eurocrypt 2022, considers the question of achieving private communication in a world where secret decryption keys are under the control of a dictator. The challenge here is to be able to establish a secret communication channel to exchange covert (i.e. anamorphic) messages on top of some already deployed public key encryption scheme. 

Over the last few years several works addressed this challenge by showing new constructions, refined notions and extensions.
Most of these constructions, however, are either ad hoc, in the sense that they build upon specific properties of the underlying PKE, or impose severe restrictions on the size of the underlying anamorphic message space. 

In this paper we consider the question of whether it is possible to have realizations of the primitive that are both generic and allow for large anamorphic message spaces. We give strong indications that, unfortunately, this is not the case.

Our first result shows that $ \textit{any black-box realization} $ of the primitive, i.e. any realization that accesses the underlying PKE only via oracle calls, $ \textit{must} $ have an anamorphic message space of size at most $poly(\lambda)$ ($\lambda$ security parameter).

Even worse, if one aims at stronger variants of the primitive (and, specifically, the notion of asymmetric anamorphic encryption, recently proposed by Catalano $ \textit{et al.} $) we show that such black-box realizations are plainly impossible, i.e. no matter how small the anamorphic message space is. 

Finally, we show that our impossibility results are rather tight: indeed, by making more specific assumptions on the underlying PKE, it becomes possible to build generic AE where the anamorphic message space is of size $\Omega(2^\lambda)$.



## 2024/1099

* Title: FHE-MENNs: Opportunities and Pitfalls for Accelerating Fully Homomorphic Private Inference with Multi-Exit Neural Networks
* Authors: Lars Wolfgang Folkerts, Nektarios Georgios Tsoutsos
* [Permalink](https://eprint.iacr.org/2024/1099)
* [Download](https://eprint.iacr.org/2024/1099.pdf)

### Abstract

With concerns about data privacy growing in a connected world, cryptography researchers have focused on fully homomorphic encryption (FHE) for promising machine learning as a service solutions. Recent advancements have lowered the computational cost by several orders of magnitude, but the latency of fully homomorphic neural networks remains a barrier to adoption. This work proposes using multi-exit neural networks (MENNs) to accelerate the FHE inference. MENNs are network architectures that provide several exit points along the depth of the network. This approach allows users to employ results from any exit and terminate the computation early, saving both time and power. First, this work weighs the latency, communication, accuracy, and computational resource benefits of running FHE-based MENN inference. Then, we present the TorMENNt attack that can exploit the user's early termination decision to launch a concrete side-channel on MENNs. We demonstrate that the TorMENNt attack can predict the private image classification output of an image set for both FHE and plaintext threat models. We discuss possible countermeasures to mitigate the attack and examine their effectiveness. Finally, we tie the privacy risks with a cost-benefit analysis to obtain a practical roadmap for FHE-based MENN adoption.



## 2024/1100

* Title: Unforgeability of Blind Schnorr in the Limited Concurrency Setting
* Authors: Franklin Harding, Jiayu Xu
* [Permalink](https://eprint.iacr.org/2024/1100)
* [Download](https://eprint.iacr.org/2024/1100.pdf)

### Abstract

A Blind Signature Scheme (BSS) is a cryptographic primitive that enables a user to obtain a digital signature on a message from a signer without revealing the message itself. The standard security notion against malicious users for a BSS is One-More Unforgeability (OMUF). One of the earliest and most well-studied blind signature schemes is the Schnorr BSS, although recent results show it does not satisfy OMUF. On the other hand, the Schnorr BSS does satisfy the weaker notion of sequential OMUF --- which restricts adversaries to opening signing sessions one at a time --- in the Algebraic Group Model (AGM) + Random Oracle Model (ROM). In light of this result, a natural question arises: does the Schnorr BSS satisfy OMUF with regard to adversaries that open no more than a small number of signing sessions concurrently?

This paper serves as a first step towards characterizing the security of the Schnorr BSS in the limited concurrency setting. Specifically, we demonstrate that the Schnorr BSS satisfies OMUF when at most two signing sessions can be open concurrently (in the AGM+ROM). Our argument suggests that it is plausible that the Schnorr BSS satisfies OMUF for up to polylogarithmically many concurrent signing sessions.



## 2024/1101

* Title: Stickel’s Protocol using Tropical Increasing Matrices
* Authors: Any Muanalifah, Zahari Mahad, Nurwan, Rosalio G Artes
* [Permalink](https://eprint.iacr.org/2024/1101)
* [Download](https://eprint.iacr.org/2024/1101.pdf)

### Abstract

In this paper we introduce new concept of tropical increasing matrices and then prove that two tropical increasing matrices are commute. Using this property, we modified Stickel’s protocol. This idea similar to [5] where modified Stickel’s protocol using commuting matrices (Linde De La Puente Matrices).



## 2024/1102

* Title: A Note on ``Privacy Preserving n-Party Scalar Product Protocol''
* Authors: Lihua Liu
* [Permalink](https://eprint.iacr.org/2024/1102)
* [Download](https://eprint.iacr.org/2024/1102.pdf)

### Abstract

We show that the scalar product protocol [IEEE Trans. Parallel Distrib. Syst. 2023, 1060-1066] is insecure against semi-honest server attack, not as claimed. Besides, its complexity increases exponentially with the number $n$, which cannot be put into practice.



## 2024/1103

* Title: A Note on Efficient Computation of the Multilinear Extension
* Authors: Ron D. Rothblum
* [Permalink](https://eprint.iacr.org/2024/1103)
* [Download](https://eprint.iacr.org/2024/1103.pdf)

### Abstract

The multilinear extension of an $m$-variate function $f : \{0,1\}^m \to \mathbb{F}$, relative to a finite field $\mathbb{F}$, is the unique multilinear polynomial $\hat{f} : \mathbb{F}^m \to \mathbb{F}$ that agrees with $f$ on inputs in $\{0,1\}^m$.
   
    In this note we show how, given oracle access to $f : \{0,1\}^m \to \mathbb{F}$ and a point $z \in \mathbb{F}^m$, to compute $\hat{f}(z)$ using $O(2^m)$ field operations and only $O(m)$ space. This improves on a previous algorithm due to Vu et al. (SP, 2013), which similarly uses $O(2^m)$ field operations but requires $O(2^m)$ space. Furthermore, the number of field additions in our algorithm is about half of that in Vu et al.'s algorithm, whereas the number of multiplications is the same up to small additive terms.



## 2024/1104

* Title: Structural Lower Bounds on Black-Box Constructions of Pseudorandom Functions
* Authors: Amos Beimel, Tal Malkin, Noam Mazor
* [Permalink](https://eprint.iacr.org/2024/1104)
* [Download](https://eprint.iacr.org/2024/1104.pdf)

### Abstract

We address the black-box complexity of constructing pseudorandom functions (PRF) from pseudorandom generators (PRG). The celebrated GGM construction  of Goldreich, Goldwasser, and Micali (Crypto 1984) provides such a construction, which (even when combined with Levin's domain-extension trick) has super-logarithmic depth. Despite many years and much effort, this remains essentially the best construction we have to date. On the negative side, one step is provided by the work of Miles and Viola (TCC 2011), which shows that a black-box construction which just calls the PRG once and outputs one of its output bits, cannot be a PRF.

In this work, we make significant further progress: we rule out black-box constructions of PRF from PRG that follow certain structural constraints, but may call the PRG adaptively polynomially many times.  In particular, we define ``tree constructions" which generalize the GGM structure: they apply the PRG $G$ along a tree path, but allow for different choices of functions to compute the children of a node on the tree and to compute the next node on the computation path down the tree. We prove that a tree construction of logarithmic depth cannot be a PRF (while GGM is a tree construction of super-logarithmic depth). We also show several other results and discuss the special case of one-call constructions.

Our main results in fact rule out even weak PRF constructions with one output bit.  We use the oracle separation methodology introduced by  Gertner, Malkin, and Reingold (FOCS 2001), and show that for any candidate black-box construction $F^G$ from $G$, there exists an oracle relative to which $G$ is a PRG, but $F^G$ is not a PRF.



## 2024/1105

* Title: A New CRT-based Fully Homomorphic Encryption
* Authors: Anil Kumar Pradhan
* [Permalink](https://eprint.iacr.org/2024/1105)
* [Download](https://eprint.iacr.org/2024/1105.pdf)

### Abstract

We have proposed a novel FHE scheme that uniquely encodes the plaintext with noise in a way that prevents the increasing noise from overflowing and corrupting the plaintext. This allows users to perform computations on encrypted data smoothly. The scheme is constructed using the Chinese Remainder Theorem (CRT), supporting a predefined number of modular operations on encrypted plaintext without the need for bootstrapping.
Although FHE recently became popular after Gentry's work and various developments have occurred in the last decade, the idea of "Fully Homomorphic Encryption (FHE)" scheme was first introduced in the 1970s by Rivest. The Chinese Remainder Theorem is one of the most suitable tools for developing a FHE Scheme because it forms a ring homomorphism \( Z_{p_1} \times Z_{p_2} \times \ldots \times Z_{p_k} \cong Z_{p_1 p_2 \ldots p_k} \).
Various attempts have been made to develop a FHE using CRT, but most of them were unsuccessful, mainly due to the chosen plaintext attack (CPA).
The proposed scheme overcomes the chosen plaintext attack. The scheme also adds random errors to the message during encryption. However, these errors are added in such a way that, when homomorphic operations are performed over encrypted data, the increasing values of errors never overwrite the values of the messages, as happens in LWE-based homomorphic schemes. Therefore, one can perform a predefined number of homomorphic operations (both addition and multiplication) without worrying about the increasing values of errors.



## 2024/1106

* Title: Masked Vector Sampling for HQC
* Authors: Maxime Spyropoulos, David Vigilant, Fabrice Perion, Renaud Pacalet, Laurent Sauvage
* [Permalink](https://eprint.iacr.org/2024/1106)
* [Download](https://eprint.iacr.org/2024/1106.pdf)

### Abstract

Anticipating the advent of large quantum computers, NIST started a worldwide competition in 2016 aiming to define the next cryptographic standards. HQC is one of these post-quantum schemes still in contention, with four others already in the process of being standardized. In 2022, Guo et al. introduced a timing attack that exploited an inconsistency in HQC rejection sampling function to recover its secret key in 866,000 calls to an oracle. The authors of HQC updated its specification by applying an algorithm to sample vectors in constant time. A masked implementation of this function was then proposed for BIKE but it is not directly applicable to HQC. In this paper we propose a masked specification-compliant version of HQC vector sampling function which relies, to our knowledge, on the first masked implementation of the Barrett reduction.



## 2024/1107

* Title: Phase Modulation Side Channels: Jittery JTAG for On-Chip Voltage Measurements
* Authors: Colin O'Flynn
* [Permalink](https://eprint.iacr.org/2024/1107)
* [Download](https://eprint.iacr.org/2024/1107.pdf)

### Abstract

Measuring the fluctuations of the clock phase of a target was identified as a leakage source on early electromagnetic side-channel investigations. Despite this, only recently was directly measuring the clock phase (or jitter) of digital signals from a target connected to being a source of exploitable leakage. As the phase of a clock output will be related to signal propagation delay through the target, and this propagation delay is related to voltage, this means that most digital devices perform an unintended phase modulation (PM) of their internal voltage onto clock output phases.

This paper first demonstrates an unprofiled CPA attack against a Cortex-M microcontroller using the phase of a clock output, observing the signal on both optically isolated and capacitively isolated paths. The unprofiled attack takes only 2-4x more traces than an attack using a classic shunt-resistor measurement.

It is then demonstrated how the JTAG bypass mode can be used to force a clock through a digital device. This forced clock signal can then be used as a highly effective oscilloscope that is located on the target device. As the attack does not require modifications to the device (such as capacitor removal or heat spreader removal) it is difficult to detect using existing countermeasures. The example attack over JTAG uses an unprofiled CPA attack, requiring only about 5x more traces than an ideal shunt-resistor based measurement. In addition, a version of this attack using a fault correlation analysis attack is also demonstrated.

Countermeasures are discussed, and a simple resampling countermeasure is tested. All tools both offensive and defensive presented in the paper have been released under open-source licenses.



## 2024/1108

* Title: Faster Asynchronous Blockchain Consensus and MVBA
* Authors: Matthieu Rambaud
* [Permalink](https://eprint.iacr.org/2024/1108)
* [Download](https://eprint.iacr.org/2024/1108.pdf)

### Abstract

Blockchain consensus, a.k.a. BFT SMR, are protocols enabling $n$ processes to decide on an ever-growing chain. The fastest known asynchronous one is called 2-chain VABA (PODC'21 and FC'22), and is used as fallback chain in Abraxas* (CCS'23). It has a claimed $9.5\delta$ expected latency when used for a single shot instance, a.k.a. an MVBA.
We exhibit attacks breaking it. Hence, the title of the fastest asynchronous MVBA with quadratic messages complexity goes to sMVBA (CCS'22), with $10\delta$ expected latency.
Our positive contributions are two new and complementary designs.

$\bullet$  2PAC (2-phase asynchronous consensus). It has a simpler and lighter chaining than in previous approaches. Instantiated with either quadratic or cubic phases of voting, it yields:

   2PAC$^\text{lean}$: $+90\%$ throughput and $9.5\delta$ expected latency, with quadratic ($O(n^2)$) messages complexity. In both 2-chain VABA and sMVBA (as if chained, with pipelining), the quorum-certified transactions which were produced in the worst-case 1/3 of views with a slow leader were dumped, so the work was lost. The simpler design of 2PAC inserts such blocks in straight-line in the chain.
Thus, contrary to naive uncle-referencing, this comes with no computational overhead, yielding a net $+50\%$ throughput gain over chained sMVBA. Both the remaining throughput and latency ($-0.5\delta$) gains, come from the lighter interactive construction of proofs of consistency appended to proposed blocks, compared to sMVBA.

   2PAC$^\text{BIG}$: the fastest asynchronous blockchain consensus with cubic ($O(n^3)$) messages complexity. Fault-free single shot MVBA runs decide in just $4\delta$, as soon as no message is delivered more than twice faster than others: GradedDAG (SRDS'23) required furthermore no messages reordering.

$\bullet$  Super Fast Pipelined Blocks. This is an upgrade of previous approaches for pipelining: in 2-chain VABA, Cordial Miners (DISC'23) and GradedDAG, a block pipelined by a leader in the middle of the view had almost twice larger latency than the non-pipelined block. Our design provides a fast path deciding the pipelined block with even smaller latency than the non-pipelined block. The fast delay is guaranteed in all executions with a fair scheduler, but remarkably, whatever the behaviors of faulty processes. Consistency is preserved by a lightweight mechanism, of one threshold signature appended per proposal.
Instantiated with the previous protocols, it yields: s2PAC$^\text{lean}$, with fast decision of pipelined blocks in $4\delta$; s2PAC$^\text{BIG}$, in $3\delta$; and sGradedDAG, in $3\delta$.