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