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