Path: ...!2.eu.feeder.erje.net!3.eu.feeder.erje.net!feeder.erje.net!usenet.goja.nl.eu.org!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: IACR ePrint Archive <noreply@example.invalid>
Newsgroups: sci.crypt
Subject: [digest] 2024 Week 24
Date: Mon, 17 Jun 2024 02:20:19 -0000
Organization: A noiseless patient Spider
Lines: 1447
Message-ID: <CTyYeu8JxJeUOJRyx3kqEaWtg9IIId0K@eprint.iacr.org.invalid>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Mon, 17 Jun 2024 04:20:23 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="28050bdad6687d5319a1a90888983251";
	logging-data="487280"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/tFN+5rAwo75xG8O2N1+8xykbEUfV7Wus="
Cancel-Lock: sha1:IPloQESBe8Z429vd4G8F2UGybEA=
Bytes: 75530

## 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 t=
he 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 st=
ore 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 n=
ew concept of homomorphic encryption with composable preprocessing.
We realize this concept with RLWE encryption schemes, and by leveraging the c=
omposibility of this technique we are able to preprocess almost all the expen=
sive parts of the homomorphic computation and reuse them across multiple prot=
ocol executions.
As a concrete application, we propose highly efficient matrix vector multipli=
cation that allows us to build HintlessPIR. For a database of size 8GB, Hintl=
essPIR achieves throughput about 6.37GB/s without requiring transmission of a=
ny client or server state.
We additionally formalize the matrix vector multiplication protocol as a nove=
l primitive that we call LinPIR, which may be of independent interest.

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

We implement and benchmark HintlessPIR which achieves better concrete costs t=
han TensorPIR for a large set of databases of interest.
We show that it improves the communication of recent preprocessing constructi=
ons 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 data=
base 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 dat=
a access mechanisms with passive persistent adversaries. We show that designi=
ng mechanisms that prevent both length leakage and access pattern leakage req=
uires navigating a three-way tradeoff between storage footprint, bandwidth fo=
otprint, and the information leaked to the adversary. We establish powerful l=
ower bounds on achievable storage and bandwidth footprints for a variety of l=
eakage profiles, and present constructions that perfectly or near-perfectly m=
atch 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 p=
airings which are sesquilinear (conjugate linear) with respect to the $\mathc=
al{O}$-module structure of an elliptic curve with CM by an imaginary quadrati=
c order $\mathcal{O}$. We use these pairings to study the security of problem=
s based on the class group action on collections of oriented ordinary or supe=
rsingular 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 BL=
S12-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 Prog=
ramming constraint system using the KZG polynomial commitment scheme.  Polyma=
th has a shorter argument (1408 / 1792 bits over the same curves) than Groth1=
6.  At 192-bit security, Polymath's argument is nearly half the size, making =
it highly competitive for high-security future applications.  Notably, we han=
dle 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 SNAR=
K 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 ar=
e associated with vectors from some inner-product space. Decryption of a ciph=
ertext for $\vec{x}$ is allowed by a key for $\vec{y}$ if and only if the inn=
er product $\langle{\vec{x}},{\vec{y}}\rangle \neq 0$. =20
Existing constructions of NIPE assume the length of the vectors are fixed apr=
iori.  =20
We present the first constructions of $ unbounded $ non-zero inner product en=
cryption (UNIPE) with constant sized keys. Unbounded here refers to the size =
of vectors not being pre-fixed during setup. Both constructions, based on bil=
inear maps, are proven selectively secure under the decisional bilinear Diffi=
e-Hellman (DBDH) assumption.

Our constructions are obtained by transforming the unbounded inner product fu=
nctional encryption (IPFE) schemes of Dufour-Sans and Pointcheval (ACNS 2019)=
========== REMAINDER OF ARTICLE TRUNCATED ==========