Newsportal USENET - [digest] 2024 Week 24

## In this issue

1. [2023/1733] Hintless Single-Server Private Information Retrieval
2. [2024/863] Length Leakage in Oblivious Data Access Mechanisms
3. [2024/880] Extending class group action attacks via pairings
4. [2024/916] Polymath: Groth16 Is Not The Limit
5. [2024/917] Unbounded Non-Zero Inner Product Encryption
6. [2024/918] Cryptographic Analysis of Delta Chat
7. [2024/919] Multi-Input Functional Encryption for Unbounded ...
8. [2024/920] Leveraging Small Message Spaces for CCA1 Security ...
9. [2024/921] Simple Logarithmic-size LSAG signature
10. [2024/922] Scalable Private Set Union, with Stronger Security
11. [2024/923] On Orchestrating Parallel Broadcasts for ...
12. [2024/924] Climbing and descending tall volcanos
13. [2024/925] Time Sharing - A Novel Approach to Low-Latency Masking
14. [2024/926] Verifiable and Private Vote-by-Mail
15. [2024/927] MATHEMATICAL SPECULATIONS ON CRYPTOGRAPHY
16. [2024/928] The Committing Security of MACs with Applications ...
17. [2024/929] Combining Outputs of a Random Permutation: New ...
18. [2024/930] Information-Theoretic Single-Server PIR in the ...
19. [2024/931] Leveled Fully-Homomorphic Signatures from Batch ...
20. [2024/932] CISELeaks: Information Leakage Assessment of ...
21. [2024/933] A Pure Indistinguishability Obfuscation Approach to ...
22. [2024/934] An Explicit High-Moment Forking Lemma and its ...
23. [2024/935] MFKDF: Multiple Factors Knocked Down Flat
24. [2024/936] Willow: Secure Aggregation with One-Shot Clients
25. [2024/937] Distributed Point Function with Constraints, Revisited
26. [2024/938] Certifying Private Probabilistic Mechanisms
27. [2024/939] Two RSA-based Cryptosystems
28. [2024/940] Scalable Collaborative zk-SNARK and Its Application ...
29. [2024/941] SmartZKCP: Towards Practical Data Exchange ...
30. [2024/942] Let Them Drop: Scalable and Efficient Federated ...
31. [2024/943] Dual Polynomial Commitment Schemes and Applications ...
32. [2024/944] Quantum CCA-Secure PKE, Revisited
33. [2024/945] Quantum-Safe Public Key Blinding from MPC-in-the- ...
34. [2024/946] Provably Secure Butterfly Key Expansion from the ...
35. [2024/947] A Modular Approach to Registered ABE for Unbounded ...
36. [2024/948] Return of the Kummer: a toolbox for genus 2 ...
37. [2024/949] Efficient 2PC for Constant Round Secure Equality ...
38. [2024/950] DISCO: Dynamic Searchable Encryption with Constant ...
39. [2024/951] Notes on (failed) attempts to instantiate TLR3
40. [2024/952] Communication Complexity vs Randomness Complexity ...
41. [2024/953] MixBuy: Contingent Payment in the Presence of Coin ...
42. [2024/954] Arithmetisation of computation via polynomial ...
43. [2024/955] ElectionGuard: a Cryptographic Toolkit to Enable ...
44. [2024/956] SNARGs under LWE via Propositional Proofs

## 2023/1733

* Title: Hintless Single-Server Private Information Retrieval
* Authors: Baiyu Li, Daniele Micciancio, Mariana Raykova, Mark Schultz-Wu
* [Permalink](https://eprint.iacr.org/2023/1733)
* [Download](https://eprint.iacr.org/2023/1733.pdf)

### Abstract

We present two new constructions for private information retrieval (PIR) in the classical setting where the clients do not need to do any preprocessing or store any database dependent information, and the server does not need to store any client-dependent information.

Our first construction (HintlessPIR) eliminates the client preprocessing step from the recent LWE-based SimplePIR (Henzinger et. al., USENIX Security 2023) by outsourcing the "hint" related computation to the server, leveraging a new concept of homomorphic encryption with composable preprocessing.
We realize this concept with RLWE encryption schemes, and by leveraging the composibility of this technique we are able to preprocess almost all the expensive parts of the homomorphic computation and reuse them across multiple protocol executions.
As a concrete application, we propose highly efficient matrix vector multiplication that allows us to build HintlessPIR. For a database of size 8GB, HintlessPIR achieves throughput about 6.37GB/s without requiring transmission of any client or server state.
We additionally formalize the matrix vector multiplication protocol as a novel primitive that we call LinPIR, which may be of independent interest.

In our second construction (TensorPIR) we reduce the communication of HintlessPIR from square root to cubic root in the database size.
For this purpose we extend our HE with preprocessing techniques to composition of key-switching keys and the query expansion algorithm.
We show how to use RLWE encryption with preprocessing to outsource LWE decryption for ciphertexts generated by homomorphic multiplications.
This allows the server to do more complex processing using a more compact query under LWE.

We implement and benchmark HintlessPIR which achieves better concrete costs than TensorPIR for a large set of databases of interest.
We show that it improves the communication of recent preprocessing constructions when clients do not have large numbers of queries or the database updates frequently.
The computation cost for removing the hint is small and decreases as the database becomes larger, and it is always more efficient than other constructions with client hints such as Spiral PIR (Menon and Wu, S&P 2022).
In the setting of anonymous queries we also improve on Spiral's communication.

## 2024/863

* Title: Length Leakage in Oblivious Data Access Mechanisms
* Authors: Grace Jia, Rachit Agarwal, Anurag Khandelwal
* [Permalink](https://eprint.iacr.org/2024/863)
* [Download](https://eprint.iacr.org/2024/863.pdf)

### Abstract

This paper explores the problem of preventing length leakage in oblivious data access mechanisms with passive persistent adversaries. We show that designing mechanisms that prevent both length leakage and access pattern leakage requires navigating a three-way tradeoff between storage footprint, bandwidth footprint, and the information leaked to the adversary. We establish powerful lower bounds on achievable storage and bandwidth footprints for a variety of leakage profiles, and present constructions that perfectly or near-perfectly match the lower bounds.

## 2024/880

* Title: Extending class group action attacks via pairings
* Authors: Joseph Macula, Katherine E. Stange
* [Permalink](https://eprint.iacr.org/2024/880)
* [Download](https://eprint.iacr.org/2024/880.pdf)

### Abstract

We introduce a new tool for the study of isogeny-based cryptography, namely pairings which are sesquilinear (conjugate linear) with respect to the $\mathcal{O}$-module structure of an elliptic curve with CM by an imaginary quadratic order $\mathcal{O}$. We use these pairings to study the security of problems based on the class group action on collections of oriented ordinary or supersingular elliptic curves. This extends work of of both (Castryck, Houben, Merz, Mula, Buuren, Vercauteren, 2023) and (De Feo, Fouotsa, Panny, 2024).

## 2024/916

* Title: Polymath: Groth16 Is Not The Limit
* Authors: Helger Lipmaa
* [Permalink](https://eprint.iacr.org/2024/916)
* [Download](https://eprint.iacr.org/2024/916.pdf)

### Abstract

Shortening the argument (three group elements or 1536 / 3072 bits over the BLS12-381/BLS24-509 curves) of the Groth16 zk-SNARK for R1CS is a long-standing open problem. We propose a zk-SNARK Polymath for the Square Arithmetic Programming constraint system using the KZG polynomial commitment scheme. Polymath has a shorter argument (1408 / 1792 bits over the same curves) than Groth16. At 192-bit security, Polymath's argument is nearly half the size, making it highly competitive for high-security future applications. Notably, we handle public inputs in a simple way. We optimized Polymath's prover through an exhaustive parameter search. Polymath's prover does not output $\mathbb{G}_{2}$ elements, aiding in batch verification, SNARK aggregation, and recursion. Polymath's properties make it highly suitable to be the final SNARK in SNARK compositions.

## 2024/917

* Title: Unbounded Non-Zero Inner Product Encryption
* Authors: Bishnu Charan Behera, Somindu C. Ramanna
* [Permalink](https://eprint.iacr.org/2024/917)
* [Download](https://eprint.iacr.org/2024/917.pdf)

### Abstract

In a non-zero inner product encryption (NIPE) scheme, ciphertexts and keys are associated with vectors from some inner-product space. Decryption of a ciphertext for $\vec{x}$ is allowed by a key for $\vec{y}$ if and only if the inner product $\langle{\vec{x}},{\vec{y}}\rangle \neq 0$.
Existing constructions of NIPE assume the length of the vectors are fixed apriori.
We present the first constructions of $ unbounded $ non-zero inner product encryption (UNIPE) with constant sized keys. Unbounded here refers to the size of vectors not being pre-fixed during setup. Both constructions, based on bilinear maps, are proven selectively secure under the decisional bilinear Diffie-Hellman (DBDH) assumption.

Our constructions are obtained by transforming the unbounded inner product functional encryption (IPFE) schemes of Dufour-Sans and Pointcheval (ACNS 2019), one in the $strict ~ domain$ setting and the other in the $permissive ~ domain$ setting. Interestingly, in the latter case, we prove security from DBDH, a static assumption while the original IPE scheme relied on an interactive parameterised assumption. In terms of efficiency, features of the IPE constructions are retrained after transformation to NIPE. Notably, the public key and decryption keys have constant size.

## 2024/918

* Title: Cryptographic Analysis of Delta Chat
* Authors: Yuanming Song, Lenka Mareková, Kenneth G. Paterson
* [Permalink](https://eprint.iacr.org/2024/918)
* [Download](https://eprint.iacr.org/2024/918.pdf)

### Abstract

We analyse the cryptographic protocols underlying Delta Chat, a decentralised messaging application which uses e-mail infrastructure for message delivery. It provides end-to-end encryption by implementing the Autocrypt standard and the SecureJoin protocols, both making use of the OpenPGP standard. Delta Chat's adoption by categories of high-risk users such as journalists and activists, but also more generally users in regions affected by Internet censorship, makes it a target for powerful adversaries. Yet, the security of its protocols has not been studied to date. We describe five new attacks on Delta Chat in its own threat model, exploiting cross-protocol interactions between its implementation of SecureJoin and Autocrypt, as well as bugs in rPGP, its OpenPGP library. The findings have been disclosed to the Delta Chat team, who implemented fixes.

## 2024/919

* Title: Multi-Input Functional Encryption for Unbounded Inner Products
* Authors: Bishnu Charan Behera, Somindu C. Ramanna
* [Permalink](https://eprint.iacr.org/2024/919)
* [Download](https://eprint.iacr.org/2024/919.pdf)

### Abstract

In this work, we propose a construction for $ Multi~Input~Inner ~Product ~Encryption$ (MIPFE) that can handle vectors of variable length in different encryption slots. This construction is the first of its kind, as all existing MIPFE schemes allow only equal length vectors. The scheme is constructed in the private key setting, providing privacy for both message as well as the function, thereby achieving the so-called $full-hiding$ security. Our MIPFE scheme uses bilinear groups of prime order and achieves security under well studied cryptographic assumptions, namely, the symmetric external Diffie-Hellman assumption.

## 2024/920

* Title: Leveraging Small Message Spaces for CCA1 Security in Additively Homomorphic and BGN-type Encryption
* Authors: Benoit Libert
* [Permalink](https://eprint.iacr.org/2024/920)
* [Download](https://eprint.iacr.org/2024/920.pdf)

### Abstract

We show that the smallness of message spaces can be used as a checksum allowing to hedge against CCA1 attacks in additively homomorphic encryption schemes.. We first show that the additively homomorphic variant of Damgård's Elgamal provides IND-CCA1 security under the standard DDH assumption. Earlier proofs either required non-standard assumptions or only applied to hybrid versions of Damgård's Elgamal, which are not additively homomorphic. Our security proof builds on hash proof systems and exploits the fact that encrypted messages must be contained in a polynomial-size interval in order to enable decryption. With $3$ group elements per ciphertext, this positions Damgård's Elgamal as the most efficient/compact DDH-based additively homomorphic CCA1 cryptosystem. Under the same assumption, the best candidate so far was the lite Cramer-Shoup cryptosystem, where ciphertexts consist of $4$ group elements. We extend this observation to build an IND-CCA1 variant of the Boneh-Goh-Nissim encryption scheme, which allows evaluating 2-DNF formulas on encrypted data. By computing tensor products of Damgård's Elgamal ciphertexts, we obtain product ciphertexts consisting of $9$ group elements (instead of $16$ elements if we were tensoring lite Cramer-Shoup ciphertexts) in the target group of a bilinear map. Using similar ideas, we also obtain a CCA1 variant of the Elgamal-Paillier cryptosystem by forcing $\lambda$ plaintext bits to be zeroes, which yields CCA1 security almost for free. In particular, the message space remains exponentially large and ciphertexts are as short as in the IND-CPA scheme. We finally adapt the technique to the Castagnos-Laguillaumie system.

## 2024/921

* Title: Simple Logarithmic-size LSAG signature
* Authors: Edsger Hughes
* [Permalink](https://eprint.iacr.org/2024/921)
* [Download](https://eprint.iacr.org/2024/921.pdf)

### Abstract

A number of existing cryptosystems use the well-known LSAG signature and its extensions. This article presents a simple logarithmic-size signature scheme LS-LSAG which, despite a radical reduction in size, retains the basic code block of the LSAG signature. Therefore, substituting LS-LSAG for LSAG requires minimal changes to almost any existing coded LSAG extension, making it logarithmic instead of linear.

## 2024/922

* Title: Scalable Private Set Union, with Stronger Security
* Authors: Yanxue Jia, Shi-Feng Sun, Hong-Sheng Zhou, Dawu Gu
* [Permalink](https://eprint.iacr.org/2024/922)
* [Download](https://eprint.iacr.org/2024/922.pdf)

### Abstract

Private Set Union (PSU) protocol allows parties, each holding an input set, to jointly compute the union of the sets without revealing anything else. In the literature, scalable PSU protocols follow the “split-execute-assemble” paradigm (Kolesnikov et al., ASIACRYPT 2019); in addition, those fast protocols often use Oblivious Transfer as building blocks. Kolesnikov et al. (ASIACRYPT 2019) and Jia et al. (USENIX Security 2022), pointed out that certain security issues can be introduced in the “split-execute-assemble” paradigm. In this work, surprisingly, we observe that the typical way of invoking Oblivious Transfer also causes unnecessary leakage, and only the PSU protocols based on additively homomorphic encryption (AHE) can avoid the leakage. However, the AHE-based PSU protocols are far from being practical.

To bridge the gap, we also design a new PSU protocol that can avoid the unnecessary leakage. Unlike the AHE-based PSU protocols, our new construction only relies on symmetric-key operations other than base OTs, thereby being much more scalable. The experimental results demonstrate that our protocol can obtain at least 873.74× speedup over the best-performing AHE-based scheme. Moreover, our performance is comparable to that of the state-of-the-art PSU protocol (Chen et al., USENIX Security 2023), which also suffers from the unnecessary leakage.

## 2024/923

* Title: On Orchestrating Parallel Broadcasts for Distributed Ledgers
* Authors: Peiyao Sheng, Chenyuan Wu, Dahlia Malkhi, Michael K. Reiter, Chrysoula Stathakopoulou, Michael Wei, Maofan Yin
* [Permalink](https://eprint.iacr.org/2024/923)
* [Download](https://eprint.iacr.org/2024/923.pdf)

### Abstract

This paper introduces and develops the concept of ``ticketing'', through which atomic broadcasts are orchestrated by nodes in a distributed system. The paper studies different ticketing regimes that allow parallelism, yet prevent slow nodes from hampering overall progress. It introduces a hybrid scheme which combines managed and unmanaged ticketing regimes, striking a balance between adaptivity and resilience. The performance evaluation demonstrates how managed and unmanaged ticketing regimes benefit throughput in systems with heterogeneous resources both in static and dynamic scenarios, with the managed ticketing regime performing better among the two as it adapts better. Finally, it demonstrates how using the hybrid ticketing regime performance can enjoy both the adaptivity of the managed regime and the liveness guarantees of the unmanaged regime.

## 2024/924

* Title: Climbing and descending tall volcanos
* Authors: Steven Galbraith
* [Permalink](https://eprint.iacr.org/2024/924)
* [Download](https://eprint.iacr.org/2024/924.pdf)

### Abstract

We revisit the question of relating the elliptic curve discrete logarithm problem (ECDLP) between ordinary elliptic curves over finite fields with the same number of points. This problem was considered in 1999 by Galbraith and in 2005 by Jao, Miller, and Venkatesan. We apply recent results from isogeny cryptography and cryptanalysis, especially the Kani construction, to this problem.. We improve the worst case bound in Galbraith's 1999 paper from $\tilde{O}( q^{1.5} )$ to (heuristically) $\tilde{O}( q^{0.4} )$ operations.

The two cases of main interest for discrete logarithm cryptography are random curves (flat volcanoes) and pairing-based crypto (tall volcanoes with crater of constant or polynomial size). In both cases we show a rigorous $\tO( q^{1/4})$ algorithm to compute an isogeny between any two curves in the isogeny class. We stress that this paper is motivated by pre-quantum elliptic curve cryptography using ordinary elliptic curves, which is not yet obsolete.

## 2024/925

* Title: Time Sharing - A Novel Approach to Low-Latency Masking
* Authors: Dilip Kumar S. V., Siemen Dhooghe, Josep Balasch, Benedikt Gierlichs, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2024/925)
* [Download](https://eprint.iacr.org/2024/925.pdf)

### Abstract

We present a novel approach to small area and low-latency first-order masking in hardware. The core idea is to separate the processing of shares in time in order to achieve non-completeness. Resulting circuits are proven first-order glitch-extended PINI secure. This means the method can be straightforwardly applied to mask arbitrary functions without constraints which the designer must take care of. Furthermore we show that an implementation can benefit from optimization through EDA tools without sacrificing security. We provide concrete results of several case studies. Our low-latency implementation of a complete PRINCE core shows a 32% area improvement (44% with optimization) over the state-of-the-art. Our PRINCE S-Box passes formal verification with a tool and the complete core on FPGA shows no first-order leakage in TVLA with 100 million traces. Our low-latency implementation of the AES S-Box costs roughly one third (one quarter with optimization) of the area of state-of-the-art implementations. It shows no first-order leakage in TVLA with 250 million traces.

## 2024/926

* Title: Verifiable and Private Vote-by-Mail
* Authors: Henri Devillez, Olivier Pereira, Thomas Peters
* [Permalink](https://eprint.iacr.org/2024/926)
* [Download](https://eprint.iacr.org/2024/926.pdf)

### Abstract

Vote-by-mail is increasingly used in Europe and worldwide for government elections. Nevertheless, very few attempts have been made towards the design of verifiable vote-by-mail, and none of them come with a rigorous security analysis. Furthermore, the ballot privacy of the currently deployed (non-verifiable) vote-by-mail systems relies on procedural means that a single malicious operator can bypass.

We propose a verifiable vote-by-mail system that can accommodate the constraints of many of the large ballots that are common in Europe. Verifiability and privacy hold unless multiple system components collude to cheat on top of the postal channel. These security notions are expressed and analyzed in the simplified UC security framework.

Our vote-by-mail system only makes limited requirements on the voters: voters can verify their vote by copying and comparing short strings and verifying the computation of a single hash on a short input, and they can vote normally if they want to ignore the verification steps completely. Our system also relies on common cryptographic components, all available in the ElectionGuard verifiable voting SDK for instance, which limits the risks of errors in the implementation of the cryptographic aspects of the system.

## 2024/927

* Title: MATHEMATICAL SPECULATIONS ON CRYPTOGRAPHY
* Authors: Anjali C B
* [Permalink](https://eprint.iacr.org/2024/927)
* [Download](https://eprint.iacr.org/2024/927.pdf)

### Abstract

The current cryptographic frameworks like RSA, ECC, and AES are potentially under quantum threat. Quantum cryptographic and post-quantum cryptography are being extensively researched for securing future information. The quantum computer and quantum algorithms are still in the early developmental stage and thus lack scalability for practical application. As a result of these challenges, most researched PQC methods are lattice-based, code-based, ECC isogeny, hash-based, and multivariate crypto schemes. In this paper, we explore other athematical topics such as stereographic projection, Mobius transformation, change of basis, Apollonian circle, Binary Quadratic form equivalence, Gauss composition law, and its conjunctions. It fulfills preliminary conditions like bijection, primality, and np-hard problems, and the feasibility of one-way functions along with its interconnection. Thus allowing the exploration of new realms of mathematics for the development of secure protocols for future communication.

## 2024/928

* Title: The Committing Security of MACs with Applications to Generic Composition
* Authors: Ritam Bhaumik, Bishwajit Chakraborty, Wonseok Choi, Avijit Dutta, Jérôme Govinden, Yaobin Shen
* [Permalink](https://eprint.iacr.org/2024/928)
* [Download](https://eprint.iacr.org/2024/928.pdf)

### Abstract

Message Authentication Codes (MACs) are ubiquitous primitives deployed in multiple flavors through standards such as HMAC, CMAC, GMAC, LightMAC, and many others. Its versatility makes it an essential building block in applications necessitating message authentication and integrity checks, in authentication protocols, authenticated encryption schemes, or as a pseudorandom or key derivation function. Its usage in this variety of settings makes it susceptible to a broad range of attack scenarios. The latest attack trends leverage a lack of commitment or context-discovery security in AEAD schemes and these attacks are mainly due to the weakness in the underlying MAC part. However, these new attack models have been scarcely analyzed for MACs themselves. This paper provides a thorough treatment of MACs committing and context-discovery security. We reveal that commitment and context-discovery security of MACs have their own interest by highlighting real-world vulnerable scenarios. We formalize the required security notions for MACs, and analyze the security of standardized MACs for these notions. Additionally, as a constructive application, we analyze generic AEAD composition and provide simple and efficient ways to build committing and context-discovery secure AEADs.

## 2024/929

* Title: Combining Outputs of a Random Permutation: New Constructions and Tight Security Bounds by Fourier Analysis
* Authors: Itai Dinur
* [Permalink](https://eprint.iacr.org/2024/929)
* [Download](https://eprint.iacr.org/2024/929.pdf)

### Abstract

We consider constructions that combine outputs of a single permutation $\pi:\{0,1\}^n \rightarrow \{0,1\}^n$ using a public function. These are popular constructions for achieving security beyond the birthday bound when implementing a pseudorandom function using a block cipher (i.e., a pseudorandom permutation). One of the best-known constructions (denoted SXoP$[2,n]$) XORs the outputs of 2 domain-separated calls to $\pi$.

Modeling $\pi$ as a uniformly chosen permutation, several previous works proved a tight information-theoretic indistinguishability bound for SXoP$[2,n]$ of about $q/2^{n}$, where $q$ is the number of queries. On the other hand, tight bounds are unknown for the generalized variant (denoted SXoP$[r,n]$) which XORs the outputs of $r>2$ domain-separated calls to a uniform permutation.

In this paper, we obtain two results. Our first result improves the known bounds for SXoP$[r,n]$ for all (constant) $r \geq 3$ (assuming $q \leq O(2^n/r)$ is not too large) in both the single-user and multi-user settings. In particular, for $q=3$, our bound is about $\sqrt{u}q_{\max}/2^{2.5n}$ (where $u$ is the number of users and $q_{\max}$ is the maximal number of queries per user), improving the best-known previous result by a factor of at least $2^n$.

For odd $r$, our bounds are tight for $q > 2^{n/2}$, as they match known attacks. For even $r$, we prove that our single-user bounds are tight by providing matching attacks.

Our second and main result is divided into two parts. First, we devise a family of constructions that output $n$ bits by efficiently combining outputs of 2 calls to a permutation on $\{0,1\}^n$, and achieve multi-user security of about $\sqrt{u} q_{\max}/2^{1.5n}$. Then, inspired by the CENC construction of Iwata [FSE'06], we further extend this family to output $2n$ bits by efficiently combining outputs of 3 calls to a permutation on $\{0,1\}^n$. The extended construction has similar multi-user security of $\sqrt{u} q_{\max}/2^{1.5n}$.

The new single-user ($u=1$) bounds of $q/2^{1.5n}$ for both families should be contrasted with the previously best-known bounds of $q/2^n$, obtained by the comparable constructions of SXoP$[2,n]$ and CENC.

All of our bounds are proved by Fourier analysis, extending the provable security toolkit in this domain in multiple ways.

## 2024/930

* Title: Information-Theoretic Single-Server PIR in the Shuffle Model
* Authors: Yuval Ishai, Mahimna Kelkar, Daniel Lee, Yiping Ma
* [Permalink](https://eprint.iacr.org/2024/930)
* [Download](https://eprint.iacr.org/2024/930.pdf)

### Abstract

We revisit the problem of private information retrieval (PIR) in the shuffle model, where queries can be made anonymously by multiple clients. We present the first single-server PIR protocol in this model that has sublinear per-client communication and information-theoretic security. Moreover, following one-time preprocessing on the server side, our protocol only requires sublinear per-client computation. Concretely, for every $\gamma>0$, the protocol has $O(n^{\gamma})$ communication and computation costs per (stateless) client, with $1/\text{poly}(n)$ statistical security, assuming that a size-$n$ database is simultaneously accessed by $\text{poly}(n)$ clients. This should be contrasted with the recent breakthrough result of Lin, Mook, and Wichs (STOC 2023) on doubly efficient PIR in the standard model, which is (inherently) limited to computational security.

## 2024/931

* Title: Leveled Fully-Homomorphic Signatures from Batch Arguments
* Authors: Abtin Afshar, Jiaqi Cheng, Rishab Goyal
* [Permalink](https://eprint.iacr.org/2024/931)
* [Download](https://eprint.iacr.org/2024/931.pdf)

### Abstract

Fully homomorphic signatures are a significant strengthening of digital signatures, enabling computations on \emph{secretly} signed data. Today, we have multiple approaches to design fully homomorphic signatures such as from lattices, or succinct functional commitments, or indistinguishability obfuscation, or mutable batch arguments. Unfortunately, all existing constructions for homomorphic signatures suffer from one or more limitations. We do not have homomorphic signatures with features such as multi-hop evaluation, context hiding, and fast amortized verification, while relying on standard falsifiable assumptions.

In this work, we design homomorphic signatures satisfying all above properties. We construct homomorphic signatures for polynomial-sized circuits from a variety of standard assumptions such as sub-exponential DDH, standard pairing-based assumptions, or learning with errors. We also discuss how our constructions can be easily extended to the multi-key setting.

## 2024/932

* Title: CISELeaks: Information Leakage Assessment of Cryptographic Instruction Set Extension Prototypes
* Authors: Aruna Jayasena, Richard Bachmann, Prabhat Mishra
* [Permalink](https://eprint.iacr.org/2024/932)
* [Download](https://eprint.iacr.org/2024/932.pdf)

### Abstract

Software based cryptographic implementations provide flexibility but they face performance limitations. In contrast, hardware based cryptographic accelerators utilize application-specific customization to provide real-time security solutions.
Cryptographic instruction-set extensions (CISE) combine the advantages of both hardware and software based solutions to provide higher performance combined with the flexibility of atomic-level cryptographic operations. While CISE is widely used to develop security solutions, side-channel analysis of CISE-based devices is in its infancy. Specifically, it is important to evaluate whether the power usage and electromagnetic emissions of CISE-based devices have any correlation with its internal operations, which an adversary can exploit to deduce cryptographic secrets.
In this paper, we propose a test vector leakage assessment framework to evaluate the pre-silicon prototypes at the early stages of the design life-cycle. Specifically, we first identify functional units with the potential for leaking information through power side-channel signatures and then evaluate them on system prototypes by generating the necessary firmware to maximize the side-channel signature. Our experimental results on two RISC-V based cryptographic extensions, RISCV-CRYPTO and XCRYPTO, demonstrated that seven out of eight prototype AES- and SHA-related functional units are vulnerable to leaking cryptographic secrets through their power side-channel signature even in full system mode with a statistical significance of $\alpha = 0.05$.

## 2024/933

* Title: A Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for NP
* Authors: Brent Waters, David J. Wu
* [Permalink](https://eprint.iacr.org/2024/933)
* [Download](https://eprint.iacr.org/2024/933.pdf)

### Abstract

We construct an adaptively-sound succinct non-interactive argument (SNARG) for NP in the CRS model from sub-exponentially-secure indistinguishability obfuscation ($i\mathcal{O}$) and sub-exponentially-secure one-way functions. Previously, Waters and Wu (STOC 2024), and subsequently, Waters and Zhandry (CRYPTO 2024) showed how to construct adaptively-sound SNARGs for NP by relying on sub-exponentially-secure indistinguishability obfuscation, one-way functions, and an additional algebraic assumption (i.e., discrete log, factoring, or learning with errors). In this work, we show that no additional algebraic assumption is needed and vanilla (sub-exponentially-secure) one-way functions already suffice in combination with $i\mathcal{O}$.

We first give a direct construction of an adaptively-sound SNARG for NP assuming (sub-exponentially-secure) $i\mathcal{O}$ and an injective one-way function. Then, we show that it suffices to have an injective one-way function that has an inefficient sampler (i.e., sampling a challenge for the one-way function requires super-polynomial time). Because we rely on the existence of injective one-way functions only in the security proof and not in the actual construction, having an inefficient sampling procedure does not impact correctness. We then show that injective one-way functions with an inefficient sampler can be built generically from any vanilla one-way function. Our approach may be independently useful in other settings to replace injective one-way functions with standard one-way functions in applications of $i\mathcal{O}$.

## 2024/934

* Title: An Explicit High-Moment Forking Lemma and its Applications to the Concrete Security of Multi-Signatures
* Authors: Gil Segev, Liat Shapira
* [Permalink](https://eprint.iacr.org/2024/934)
* [Download](https://eprint.iacr.org/2024/934.pdf)

### Abstract

In this work we first present an explicit forking lemma that distills the information-theoretic essence of the high-moment technique introduced by Rotem and Segev (CRYPTO '21), who analyzed the security of identification protocols and Fiat-Shamir signature schemes. Whereas the technique of Rotem and Segev was particularly geared towards two specific cryptographic primitives, we present a stand-alone probabilistic lower bound, which does not involve any underlying primitive or idealized model. The key difference between our lemma and previous ones is that instead of focusing on the tradeoff between the worst-case or expected running time of the resulting forking algorithm and its success probability, we focus on the tradeoff between higher moments of its running time and its success probability.

Equipped with our lemma, we then establish concrete security bounds for the BN and BLS multi-signature schemes that are significantly tighter than the concrete security bounds established by Bellare and Neven (CCS '06) and Boneh, Drijvers and Neven (ASIACRYPT '18), respectively. Our analysis does not limit adversaries to any idealized algebraic model, such as the algebraic group model in which all algorithms are assumed to provide an algebraic justification for each group element they produce. Our bounds are derived in the random-oracle model based on the standard-model second-moment hardness of the discrete logarithm problem (for the BN scheme) and the computational co-Diffie-Hellman problem (for the BLS scheme). Such second-moment assumptions, asking that the success probability of any algorithm in solving the underlying computational problems is dominated by the second moment of the algorithm's running time, are particularly plausible in any group where no better-than-generic algorithms are currently known.

## 2024/935

* Title: MFKDF: Multiple Factors Knocked Down Flat
* Authors: Matteo Scarlata, Matilda Backendal, Miro Haller
* [Permalink](https://eprint.iacr.org/2024/935)
* [Download](https://eprint.iacr.org/2024/935.pdf)

### Abstract

Nair and Song (USENIX 2023) introduce the concept of a Multi-Factor Key Derivation Function (MFKDF), along with constructions and a security analysis.
MFKDF integrates dynamic authentication factors, such as HOTP and hardware tokens, into password-based key derivation.
The aim is to improve the security of password-derived keys, which can then be used for encryption or as an alternative to multi-factor authentication.
The authors claim an exponential security improvement compared to traditional password-based key derivation functions (PBKDF).

We show that the MFKDF constructions proposed by Nair and Song fall short of the stated security goals.
Underspecified cryptographic primitives and the lack of integrity of the MFKDF state lead to several attacks, ranging from full key recovery when an HOTP factor is compromised, to bypassing factors entirely or severely reducing their entropy.
We reflect on the different threat models of key-derivation and authentication, and conclude that MFKDF is always weaker than plain PBKDF and multi-factor authentication in each setting.

## 2024/936

* Title: Willow: Secure Aggregation with One-Shot Clients
* Authors: James Bell-Clark, Adrià Gascón, Baiyu Li, Mariana Raykova, Phillipp Schoppmann
* [Permalink](https://eprint.iacr.org/2024/936)
* [Download](https://eprint.iacr.org/2024/936.pdf)

### Abstract

A common drawback of secure vector summation protocols in the single-server model is that they impose at least one synchronization point between all clients contributing to the aggregation. This results in clients waiting on each other to advance through the rounds of the protocol, leading to large latency even if the protocol is computationally efficient. In this paper we propose protocols in the single-server model where clients contributing data to the aggregation send a single message to the server in an asynchronous fashion, i.e., without the need for synchronizing their reporting time with any other clients. Our approach is based on a committee of parties, called decryptors, that aid in the computation. Decryptors run a setup phase before data collection starts, and a decryption phase once it ends. Unlike existing committee-based protocols such as Flamingo (S&P 2023), the cost for committee members can be made sub-linear in the number of clients, and does not depend on the size of the input data. Our experimental evaluation shows that our protocol, even while enabling asynchronous client contributions,is competitive with the state of the art protocols that do not have that feature in both computation and communication.

## 2024/937

* Title: Distributed Point Function with Constraints, Revisited
* Authors: Keyu Ji, Bingsheng Zhang, Hong-Sheng Zhou, Kui Ren
* [Permalink](https://eprint.iacr.org/2024/937)
* [Download](https://eprint.iacr.org/2024/937.pdf)

### Abstract

Distributed Point Function (DPF) provides a way for a dealer to split a point function $f_{\alpha, \beta}$ into multiple succinctly described function-shares, where the function $f_{\alpha, \beta}$ for a special input $\alpha$, returns a special output value $\beta$, and returns a fixed value $0$ otherwise.. As the security requirement, any strict subset of the function-shares reveals nothing about the function $f_{\alpha,\beta}$. However, each function-share can be individually evaluated on the common input $x$, and these evaluation results can then be merged together to reconstruct the value $f_{\alpha, \beta}(x)$.

Recently, Servan-Schreiber et al. (S&P 2023) investigate the access control problem for DPF; namely, the DPF evaluators can ensure that the DPF dealer is authorized to share the given function with privacy assurance. In this work, we revisit this problem, introducing a new notion called DPF with constraints; meanwhile, we identify that there exists a subtle flaw in their privacy definition as well as a soundness issue in one of their proposed schemes due to the lack of validation of the special output value $\beta$. Next, we show how to reduce both the storage size of the constraint representation and the server's computational overhead from $O(N)$ to $O(\log N)$, where $N$ is the number of authorized function sets. In addition, we show how to achieve fine-grained private access control, that is, the wildcard-style constraint for the choice of the special output $\beta$. Our benchmarks show that the amortized running time of our logarithmic storage scheme is $2\times$ - $3\times$ faster than the state-of-the-art when $N=2^{15}$. Furthermore, we provide the first impossibility and feasibility results of the DPF with constraints where the evaluators do not need to communicate with each other.

## 2024/938

* Title: Certifying Private Probabilistic Mechanisms
* Authors: Zoë Ruha Bell, Shafi Goldwasser, Michael P. Kim, Jean-Luc Watson
* [Permalink](https://eprint.iacr.org/2024/938)
* [Download](https://eprint.iacr.org/2024/938.pdf)

### Abstract

In past years, entire research communities have arisen to address concerns of privacy and fairness in data analysis. At present, however, the public must trust that institutions will re-implement algorithms voluntarily to account for these social concerns. Due to additional cost, widespread adoption is unlikely without effective legal enforcement. A technical challenge for enforcement is that the methods proposed are often probabilistic mechanisms, whose output must be drawn according to precise, and sometimes secret, distributions. The Differential Privacy (DP) case is illustrative: if a cheating curator answers queries according to an overly-accurate mechanism, privacy violations could go undetected. The need for effective enforcement raises the central question of our paper: Can we efficiently certify the output of a probabilistic mechanism enacted by an untrusted party? To this end:

(1) We introduce two new notions: Certified Probabilistic Mechanisms (CPM) and Random Variable Commitment Schemes (RVCS). A CPM is an interactive protocol that forces a prover to enact a given probabilistic mechanism or be caught; importantly, the interaction does not reveal secret parameters of the mechanism. An RVCS—a key primitive for constructing CPMs—is a commitment scheme where the verifier is convinced that the commitment is to an RV sampled according to an agreed-upon distribution, but learns nothing else.

(2) We instantiate the general notion of CPM for the special case of Certifying DP. We build a lightweight, doubly-efficent interactive proof system to certify arbitrary-predicate counting queries released via the DP Binomial mechanism. The construction relies on a commitment scheme with perfect hiding and additive homomorphic properties that can be used to release a broad class of queries about a committed database, which we construct on top of Pedersen commitments.

(3) Finally, we demonstrate the immediate feasibility of Certified DP via a highly-efficient and scalable prototype implementation to answer counting queries of arbitrary predicates. The mechanism is composed of an offline and online stage, where the online phase allows for non-interactive certification of queries. For example, we show that CDP queries over a US Census Public Use Microdata Sample (PUMS) ($n=7000$) can be completed in only 1.6 ms and verified in just 38 $\mu \text{s}$. Our implementation is available in open source at https://github.com/jlwatson/certified-dp.

## 2024/939

* Title: Two RSA-based Cryptosystems
* Authors: A. Telveenus
* [Permalink](https://eprint.iacr.org/2024/939)
* [Download](https://eprint.iacr.org/2024/939.pdf)

### Abstract

The cryptosystem RSA is a very popular cryptosystem in the study of Cryptography. In this article, we explore how the idea of a primitive m th root of unity in a ring can be integrated into the Discrete Fourier Transform, leading to the development of new cryptosystems known as RSA-DFT and RSA-HGR.

## 2024/940

* Title: Scalable Collaborative zk-SNARK and Its Application to Efficient Proof Outsourcing
* Authors: Xuanming Liu, Zhelei Zhou, Yinghao Wang, Jinye He, Bingsheng Zhang, Xiaohu Yang, Jiaheng Zhang
* [Permalink](https://eprint.iacr.org/2024/940)
* [Download](https://eprint.iacr.org/2024/940.pdf)

### Abstract

Collaborative zk-SNARK (USENIX'22) allows multiple parties to jointly create a zk-SNARK proof over distributed secrets (also known as the witness). It provides a promising approach to proof outsourcing, where a client wishes to delegate the tedious task of proof generation to many servers from different locations, while ensuring no corrupted server can learn its witness (USENIX'23). Unfortunately, existing work remains a significant efficiency problem, as the protocols rely heavily on a particularly powerful server, and thus face challenges in achieving scalability for complex applications.

In this work, we address this problem by extending the existing zk-SNARKs Libra (Crypto'19) and HyperPlonk (Eurocrypt'23) into scalable collaborative zk-SNARKs. Crucially, our collaborative proof generation does not require a powerful server, and all servers take up roughly the same proportion of the total workload. In this way, we achieve privacy and scalability simultaneously for the first time in proof outsourcing. To achieve this, we develop an efficient MPC toolbox for a number of useful multivariate polynomial primitives, including sumcheck, productcheck, and multilinear polynomial commitment, which can also be applied to other applications as independent interests. For proof outsourcing purposes, when using $128$ servers to jointly generate a proof for a circuit size of $2^{24}$ gates, our benchmarks for these two collaborative proofs show a speedup of $21\times$ and $24\times$ compared to a local prover, respectively. Furthermore, we are able to handle enormously large circuits, making it practical for real-world applications.

## 2024/941

* Title: SmartZKCP: Towards Practical Data Exchange Marketplace Against Active Attacks
* Authors: Xuanming Liu, Jiawen Zhang, Yinghao Wang, Xinpeng Yang, Xiaohu Yang
* [Permalink](https://eprint.iacr.org/2024/941)
* [Download](https://eprint.iacr.org/2024/941.pdf)

### Abstract

The trading of data is becoming increasingly important as it holds substantial value. A blockchain-based data marketplace can provide a secure and transparent platform for data exchange. To facilitate this, developing a fair data exchange protocol for digital goods has garnered considerable attention in recent decades. The Zero Knowledge Contingent Payment (ZKCP) protocol enables trustless fair exchanges with the aid of blockchain and zero-knowledge proofs. However, applying this protocol in a practical data marketplace is not trivial.

In this paper, several potential attacks are identified when applying the ZKCP protocol in a practical public data marketplace. To address these issues, we propose SmartZKCP, an enhanced solution that offers improved security measures and increased performance. The protocol is formalized to ensure fairness and secure against potential attacks. Moreover, SmartZKCP offers efficiency optimizations and minimized communication costs. Evaluation results show that SmartZKCP is both practical and efficient, making it applicable in a data exchange marketplace.

## 2024/942

* Title: Let Them Drop: Scalable and Efficient Federated Learning Solutions Agnostic to Client Stragglers
* Authors: Riccardo Taiello, Melek Önen, Clémentine Gritti, Marco Lorenzi
* [Permalink](https://eprint.iacr.org/2024/942)
* [Download](https://eprint.iacr.org/2024/942.pdf)

### Abstract

Secure Aggregation (SA) stands as a crucial component in modern Federated Learning (FL) systems, facilitating collaborative training of a global machine learning model while protecting the privacy of individual clients' local datasets. Many existing SA protocols described in the FL literature operate synchronously, leading to notable runtime slowdowns due to the presence of stragglers (i.e. late-arriving clients).
To address this challenge, one common approach is to consider stragglers as client failures and use SA solutions that are robust against dropouts. While this approach indeed seems to work, it unfortunately affects the performance of the protocol as its cost strongly depends on the dropout ratio and this ratio has increased significantly when taking stragglers into account.
Another approach explored in the literature to address stragglers is to introduce asynchronicity into the FL system. Very few SA solutions exist in this setting and currently suffer from high overhead.
In this paper, similar to related work, we propose to handle stragglers as client failures but design SA solutions that do not depend on the dropout ratio so that an unavoidable increase on this metric does not affect the performance of the solution. We first introduce Eagle, a synchronous SA scheme designed not to depend on the client failures but on the online users' inputs only. This approach offers better computation and communication costs compared to existing solutions under realistic settings where the number of stragglers is high. We then propose Owl, the first SA solution that is suitable for the asynchronous setting and once again considers online clients' contributions only.
We implement both solutions and show that: (i) in a synchronous FL with realistic dropout rates (taking potential stragglers into account), Eagle outperforms the best SA solution, namely Flamingo, by X4; (ii) In the asynchronous setting, Owl exhibits the best performance compared to the state-of-the-art solution LightSecAgg.

## 2024/943

* Title: Dual Polynomial Commitment Schemes and Applications to Commit-and-Prove SNARKs
* Authors: Chaya Ganesh, Vineet Nair, Ashish Sharma
* [Permalink](https://eprint.iacr.org/2024/943)
* [Download](https://eprint.iacr.org/2024/943.pdf)

### Abstract

We introduce a primitive called a dual polynomial commitment scheme that allows linking together a witness committed to using a univariate polynomial commitment scheme with a witness inside a multilinear polynomial commitment scheme. This yields commit-and-prove (CP) SNARKs with the flexibility of going back and forth between univariate and multilinear encodings of witnesses. This is in contrast to existing CP frameworks that assume compatible polynomial commitment schemes between different component proofs systems. In addition to application to CP, we also show that our notion yields a version of Spartan with better proof size and verification complexity, at the cost of a more expensive prover.

We achieve this via a combination of the following technical contributions: (i) we construct a new univariate commitment scheme in the updatable SRS setting that has better prover complexity than KZG (ii) we construct a new multilinear commitment scheme in the updatable setting that is compatible for linking with our univariate scheme (iii) we construct an argument of knowledge to prove a given linear relationship between two witnesses committed using a two-tiered commitment scheme (Pedersen+AFG) using Dory as a black-box. These constructions are of independent interest.

We implement our commitment schemes and report on performance. We also implement the version of Spartan with our dual polynomial commitment scheme and demonstrate that it outperforms Spartan in proof size and verification complexity.

## 2024/944

* Title: Quantum CCA-Secure PKE, Revisited
* Authors: Navid Alamati, Varun Maram
* [Permalink](https://eprint.iacr.org/2024/944)
* [Download](https://eprint.iacr.org/2024/944.pdf)

### Abstract

Security against chosen-ciphertext attacks (CCA) concerns privacy of messages even if the adversary has access to the decryption oracle. While the classical notion of CCA security seems to be strong enough to capture many attack scenarios, it falls short of preserving the privacy of messages in the presence of quantum decryption queries, i.e., when an adversary can query a superposition of ciphertexts.

Boneh and Zhandry (CRYPTO 2013) defined the notion of quantum CCA (qCCA) security to guarantee privacy of messages in the presence of quantum decryption queries. However, their construction is based on an exotic cryptographic primitive (namely, identity-based encryption with security against quantum queries), for which only one instantiation is known. In this work, we comprehensively study qCCA security for public-key encryption (PKE) based on both generic cryptographic primitives and concrete assumptions, yielding the following results:

* We show that key-dependent message secure encryption (along with PKE) is sufficient to realize qCCA-secure PKE. This yields the first construction of qCCA-secure PKE from the LPN assumption.

* We prove that hash proof systems imply qCCA-secure PKE, which results in the first instantiation of PKE with qCCA security from (isogeny-based) group actions.

* We extend the notion of adaptive TDFs (ATDFs) to the quantum setting by introducing quantum ATDFs, and we prove that quantum ATDFs are sufficient to realize qCCA-secure PKE. We also show how to instantiate quantum ATDFs from the LWE assumption.

* We show that a single-bit qCCA-secure PKE is sufficient to realize a multi-bit qCCA-secure PKE by extending the completeness of bit encryption for CCA security to the quantum setting.

## 2024/945

* Title: Quantum-Safe Public Key Blinding from MPC-in-the-Head Signature Schemes
* Authors: Sathvika Balumuri, Edward Eaton, Philippe Lamontagne
* [Permalink](https://eprint.iacr.org/2024/945)
* [Download](https://eprint.iacr.org/2024/945.pdf)

### Abstract

Key blinding produces pseudonymous digital identities by rerandomizing public keys of a digital signature scheme. It is used in anonymous networks to provide the seemingly contradictory goals of anonymity and authentication. Current key blinding schemes are based on the discrete log assumption. Eaton, Stebila and Stracovsky (LATINCRYPT 2021) proposed the first key blinding schemes from lattice assumptions. However, the large public keys and lack of QROM security means they are not ready to replace existing solutions.

We present a new way to build key blinding schemes form any MPC-in-the-Head signature scheme. These schemes rely on well-studied symmetric cryptographic primitives and admit short public keys. We prove a general framework for constructing key blinding schemes and for proving their security in the quantum random oracle model (QROM).

We instantiate our framework with the recent AES-based Helium signature scheme (Kales and Zaverucha, 2022). Blinding Helium only adds a minor overhead to the signature and verification time. Both Helium and the aforementioned lattice-based key blinding schemes were only proven secure in the ROM. This makes our results the first QROM proof of Helium and the first fully quantum-safe public key blinding scheme.

## 2024/946

* Title: Provably Secure Butterfly Key Expansion from the CRYSTALS Post-Quantum Schemes
* Authors: Edward Eaton, Philippe Lamontagne, Peter Matsakis
* [Permalink](https://eprint.iacr.org/2024/946)
* [Download](https://eprint.iacr.org/2024/946.pdf)

### Abstract

This work presents the first provably secure protocol for Butterfly Key Expansion (BKE) -- a tripartite protocol for provisioning users with pseudonymous certificates -- based on post-quantum cryptographic schemes. Our work builds upon the CRYSTALS family of post-quantum algorithms that have been selected for standardization by NIST. We extend those schemes by imbuing them with the additional functionality of public key expansion: a process by which pseudonymous public keys can be derived by a single public key. Our work is the most detailed analysis yet of BKE: we formally define desired properties of BKE -- unforgeability and unlinkability -- as cryptographic games, and prove that BKE implemented with our modified CRYSTALS schemes satisfy those properties. We implemented our scheme by modifying the Kyber and Dilithium algorithms from the LibOQS project, and we report on our parameter choices and the performance of the schemes.

## 2024/947

* Title: A Modular Approach to Registered ABE for Unbounded Predicates
* Authors: Nuttapong Attrapadung, Junichi Tomida
* [Permalink](https://eprint.iacr.org/2024/947)
* [Download](https://eprint.iacr.org/2024/947.pdf)

### Abstract

Registered attribute-based encryption (Reg-ABE), introduced by Hohenberger et al. (Eurocrypt’23), emerges as a pivotal extension of attribute-based encryption (ABE), aimed at mitigating the key-escrow problem. Although several Reg-ABE schemes with black-box use of cryptography have been proposed so far, there remains a signiﬁcant gap in the class of achievable predicates between vanilla ABE and Reg-ABE. To narrow this gap, we propose a modular framework for constructing Reg-ABE schemes for a broader class of predicates. Our framework
is a Reg-ABE analog of the predicate transformation framework for ABE introduced by Attrapadung (Eurocrypt’19) and later reﬁned by Attrapadung and Tomida (Asiacrypt’20) to function under the standard MDDH assumption. As immediate applications, our framework implies the following new Reg-ABE schemes under the standard MDDH assumption:
– the ﬁrst Reg-ABE scheme for (non-)monotone span programs with the traditional completely unbounded property.
– the ﬁrst Reg-ABE scheme for general non-monotone span programs (also with the completely unbounded property) as deﬁned in the case of vanilla ABE by Attrapadung and Tomida (Asiacrypt’20).
Here, the term “completely unbounded” signiﬁes the absence of restrictions on attribute sets for users and policies associated with ciphertexts. From a technical standpoint, we ﬁrst substantially modify pair encoding schemes (PES), originally devised for vanilla ABE by Attrapadung (Eurocrypt’14), to make them compatible with
Reg-ABE. Subsequently, we present a series of predicate transformations through which we can construct complex predicates, particularly those with an “unbounded” characteristic, starting from simple ones. Finally, we deﬁne new properties of PES necessary for constructing Reg-ABE schemes and prove that these properties are preserved through the transformations. This immediately implies that we can obtain Reg-ABE schemes for any predicates derived via predicate
transformations.

## 2024/948

* Title: Return of the Kummer: a toolbox for genus 2 cryptography
* Authors: Maria Corte-Real Santos, Krijn Reijnders
* [Permalink](https://eprint.iacr.org/2024/948)
* [Download](https://eprint.iacr.org/2024/948.pdf)

### Abstract

This work expands the machinery we have for isogeny-based cryptography in genus 2 by developing a toolbox of several essential algorithms for Kummer surfaces, the dimension 2 analogue of x-only arithmetic on elliptic curves. Kummer surfaces have been suggested in (hyper-)elliptic curve cryptography since at least the 1980s and recently these surfaces have reappeared to efficiently compute (2,2)-isogenies. We construct several essential analogues of techniques used in one-dimensional isogeny-based cryptography, such as pairings, deterministic point sampling and point compression and give an overview of (2,2)-isogenies on Kummer surfaces. We furthermore show how Scholten's construction can be used to transform isogeny-based cryptography over elliptic curves over $\mathbb{F}_{p^2}$ into protocols over Kummer surfaces over $\mathbb{F}_p$.

As an example of this approach, we demonstrate that SQIsign verification can be performed completely on Kummer surfaces, and, therefore, that one-dimensional SQIsign verification can be viewed as a two-dimensional isogeny between products of elliptic curves. Curiously, the isogeny is then defined over $\mathbb{F}_p$ rather than $\mathbb{F}_{p^2}$. Contrary to expectation, the cost of SQIsign verification using Kummer surfaces does not explode: verification costs only 1.5 times more in terms of finite field operations than the SQIsign variant AprèsSQI, optimised for fast verification. Furthermore, as Kummer surfaces allow a much higher degree of parallelization, Kummer-based protocols over $\mathbb{F}_p$ could potentially outperform elliptic curve analogues over $\mathbb{F}_{p^2}$ in terms of clock cycles and actual performance.

## 2024/949

* Title: Efficient 2PC for Constant Round Secure Equality Testing and Comparison
* Authors: Tianpei Lu, Xin Kang, Bingsheng Zhang, Zhuo Ma, Xiaoyuan Zhang, Yang Liu, Kui Ren
* [Permalink](https://eprint.iacr.org/2024/949)
* [Download](https://eprint.iacr.org/2024/949.pdf)

### Abstract

Secure equality testing and comparison are two important primitives that have been widely used in many secure computation scenarios, such as privacy-preserving machine learning, private set intersection, secure data mining, etc. In this work, we propose new constant-round two-party computation (2PC) protocols for secure equality testing and secure comparison. Our protocols are designed in the online/offline paradigm. Theoretically, for 32-bit integers, the online communication for our equality testing is only 76 bits, and the cost for our secure comparison is only 384 bits.Our benchmarks show that (i) our equality is $9 \times$ faster than the Guo \emph{et al.} (EUROCRYPT 2023) and $15 \times$ of the garbled circuit scheme (EMP-toolkit). (ii) our secure comparison protocol is $3 \times$ faster than Guo et al.(EUROCRYPT 2023), $6 \times$ faster than both Rathee et al. (CCS 2020) and garbled circuit scheme.

## 2024/950

* Title: DISCO: Dynamic Searchable Encryption with Constant State
* Authors: Xiangfu Song, Yu Zheng, Jianli Bai, Changyu Dong, Zheli Liu, Ee-Chien Chang
* [Permalink](https://eprint.iacr.org/2024/950)
* [Download](https://eprint.iacr.org/2024/950.pdf)

### Abstract

Dynamic searchable encryption (DSE) with forward and backward privacy reduces leakages in early-stage schemes. Security enhancement comes with a price -- maintaining updatable keyword-wise state information. State information, if stored locally, incurs significant client-side storage overhead for keyword-rich datasets, potentially hindering real-world deployments.

We propose DISCO, a simple and efficient framework for designing DSE schemes using constant client state. DISCO combines range-constrained pseudorandom functions (RCPRFs) over a global counter and leverages nice properties from the underlying primitives and index structure to simultaneously achieve forward-and-backward privacy and constant client state. To configure DISCO concretely, we identify a set of RCPRF properties that are vital for the resulting DISCO instantiations. By configuring DISCO with different RCPRFs, we resolve efficiency and usability issues in existing schemes. We further optimize DISCO's concrete efficiency without downgrading security. We implement DISCO constructions and report performance, showing trade-offs from different DISCO constructions. Besides, we compare the practical efficiency of DISCO with existing non-constant-state DSE schemes, demonstrating DISCO's competitive efficiency.

## 2024/951

* Title: Notes on (failed) attempts to instantiate TLR3
* Authors: Alexander Maximov
* [Permalink](https://eprint.iacr.org/2024/951)
* [Download](https://eprint.iacr.org/2024/951.pdf)

### Abstract

In this short paper we share our experience on instantiating the width-extension construct TLR3, based on a variety of tweakable block cipher constructs. As many of our attempts failed, we highlight the complexity of getting a practical tweakable block cipher and the gap between theory and practice.

## 2024/952

* Title: Communication Complexity vs Randomness Complexity in Interactive Proofs
* Authors: Benny Applebaum, Kaartik Bhushan, Manoj Prabhakaran
* [Permalink](https://eprint.iacr.org/2024/952)
* [Download](https://eprint.iacr.org/2024/952.pdf)

### Abstract

In this note, we study the interplay between the communication from a verifier in a general private-coin interactive protocol and the number of random bits it uses in the protocol. Under worst-case derandomization assumptions, we show that it is possible to transform any $I$-round interactive protocol that uses $\rho$ random bits into another one for the same problem with the additional property that the verifier's communication is bounded by $O(I\cdot \rho)$. Importantly, this is done with a minor, logarithmic, increase in the communication from the prover to the verifier and while preserving the randomness complexity. Along the way, we introduce a new compression game between computationally-bounded compressor and computationally-unbounded decompressor and a new notion of conditioned efficient distributions that may be of independent interest. Our solutions are based on a combination of perfect hashing and pseudorandom generators.

## 2024/953

* Title: MixBuy: Contingent Payment in the Presence of Coin Mixers
* Authors: Diego Castejon-Molina, Dimitrios Vasilopoulos, Pedro Moreno-Sanchez
* [Permalink](https://eprint.iacr.org/2024/953)
* [Download](https://eprint.iacr.org/2024/953.pdf)

### Abstract

A contingent payment protocol involves two mutually distrustful parties, a buyer and a seller, operating on the same blockchain, and a digital product, whose ownership is not tracked on a blockchain (e.g. a digital book, but not a NFT). The buyer holds coins on the blockchain and transfers them to the seller in exchange for the product. However, if the blockchain does not hide transaction details, any observer can learn that a buyer purchased some product from a seller. In this work, we take contingent payment a step further: we consider a buyer who wishes to buy a digital product from a seller routing the payment via an untrusted mixer. Crucially, we require that said payment is unlinkable, meaning that the mixer (or any other observer) does not learn which buyer is paying which seller. We refer to such setting as unlinkable contingent payment (UCP).

We present MixBuy, a system that realizes UCP. Mixbuy relies on \emph{oracle-based unlinkable contingent payment} (O-UCP), a novel four-party cryptographic protocol where the mixer pays the seller and the seller provides the buyer with the product only if a semi-trusted notary attests that the buyer has paid the mixer. More specifically, we require four security notions: (i) mixer security that guarantees that if the mixer pays the seller, the intermediary must get paid from the buyer; (ii) seller security that guarantees that if the seller delivers the product to the buyer, the seller must get paid from the intermediary; (iii) buyer security that guarantees that if the buyer pays the intermediary, the buyer must obtain the product; and (iv) unlinkability that guarantees that given a set of buyers and sellers, the intermediary should not learn which buyer paid which seller.

We present a provably secure and efficient cryptographic construction for O-UCP. Our construction can be readily used to realize UCP on most blockchains, as it has minimal functionality requirements (i.e., digital signatures and timelocks). To demonstrate the practicality of our construction, we provide a proof of concept for O-UCP and our benchmarks in commodity hardware show that the communication overhead is small (a few kB per message) and the running time is below one second.

## 2024/954

* Title: Arithmetisation of computation via polynomial semantics for first-order logic
* Authors: Murdoch J. Gabbay
* [Permalink](https://eprint.iacr.org/2024/954)
* [Download](https://eprint.iacr.org/2024/954.pdf)

### Abstract

We propose a compositional shallow translation from a first-order logic with equality, into polynomials; that is, we arithmetise the semantics of first-order logic. Using this, we can translate specifications of mathematically structured programming into polynomials, in a form amenable to succinct cryptographic verification.

We give worked example applications, and we propose a proof-of-concept succinct verification scheme based on inner product arguments.

## 2024/955

* Title: ElectionGuard: a Cryptographic Toolkit to Enable Verifiable Elections
* Authors: Josh Benaloh, Michael Naehrig, Olivier Pereira, Dan S. Wallach
* [Permalink](https://eprint.iacr.org/2024/955)
* [Download](https://eprint.iacr.org/2024/955.pdf)

### Abstract

ElectionGuard is a flexible set of open-source tools that---when used with traditional election systems---can produce end-to-end verifiable elections whose integrity can be verified by observers, candidates, media, and even voters themselves. ElectionGuard has been integrated into a variety of systems and used in actual public U.S. elections in Wisconsin, California, Idaho, Utah, and Maryland as well as in caucus elections in the U.S. Congress. It has also been used for civic voting in the Paris suburb of Neuilly-sur-Seine and for an online election by a Switzerland/Denmark-based organization.

The principal innovation of ElectionGuard is the separation of the cryptographic tools from the core mechanics and user interfaces of voting systems. This separation allows the cryptography to be designed and built by security experts without having to re-invent and replace the existing infrastructure. Indeed, in its preferred deployment, ElectionGuard does not replace the existing vote counting infrastructure but instead runs alongside and produces its own independently-verifiable tallies. Although much of the cryptography in ElectionGuard is, by design, not novel, some significant innovations are introduced which greatly simplify the process of verification.

This paper describes the design of ElectionGuard, its innovations, and many of the learnings from its implementation and growing number of real-world deployments.

## 2024/956

* Title: SNARGs under LWE via Propositional Proofs
* Authors: Zhengzhong Jin, Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan
* [Permalink](https://eprint.iacr.org/2024/956)
* [Download](https://eprint.iacr.org/2024/956.pdf)

### Abstract

We construct a succinct non-interactive argument (SNARG) system for every NP language $\mathcal{L}$ that has a propositional proof of non-membership for each $x\notin \mathcal{L}$. The soundness of our SNARG system relies on the hardness of the learning with errors (LWE) problem. The common reference string (CRS) in our construction grows with the space required to verify the propositional proof, and the size of the proof grows poly-logarithmically in the length of the propositional proof.

Unlike most of the literature on SNARGs, our result implies SNARGs for languages $\mathcal L$ with proof length shorter than logarithmic in the deterministic time complexity of $\mathcal L$. Our SNARG improves over prior SNARGs for such ``hard'' NP languages (Sahai and Waters, STOC 2014, Jain and Jin, FOCS 2022) in several ways:

- For languages with polynomial-length propositional proofs of non-membership, our SNARGs are based on a single, polynomial-time falsifiable assumption, namely LWE.
- Our construction handles propositional proofs of super-polynomial length, as long as they have bounded space, under the subexponential LWE assumption.
- Our SNARGs have a transparent setup, meaning that no private randomness is required to generate the CRS.

Moreover, our approach departs dramatically from these prior works: we show how to design SNARGs for hard languages without publishing a program (in the CRS) that has the power to verify $\mathsf{NP}$ witnesses.

The key new idea in our cryptographic construction is what we call a ``locally unsatisfiable extension'' of the $\mathsf{NP}$ verification circuit $\{C_x\}_x$. We say that an $\mathsf{NP}$ verifier has a locally unsatisfiable extension if for every $x\not\in \mathcal L$, there exists an extension $E_x$ of $C_x$ that is not even locally satisfiable in the sense of a local assignment generator [Paneth-Rothblum, TCC 2017]. Crucially, we allow $E_x$ to be depend arbitrarily on $x$ rather than being efficiently constructible.

In this work, we show -- via a ``hash-and-BARG'' for a hidden, encrypted computation -- how to build SNARGs for all languages with locally unsatisfiable extensions. We additionally show that propositional proofs of unsatisfiability generically imply the existence of locally unsatisfiable extensions, which allows us to deduce our main results.

As an illustrative example, our results imply a SNARG for the decisional Diffie-Hellman (DDH) language under the LWE assumption.

Date	Sujet	#		Auteur
17 Jun 24	[digest] 2024 Week 24	1		IACR ePrint Archive