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


[continued in next message]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)