## In this issue

1. [2024/762] Constant-Cost Batched Partial Decryption in ...
2. [2024/766] Breaking Verifiable Delay Functions in the Random ...
3. [2024/1530] Folding Schemes with Privacy Preserving Selective ...
4. [2024/1531] FLI: Folding Lookup Instances
5. [2024/1532] Bitwise Garbling Schemes --- A Model with ...
6. [2024/1533] BEAT-MEV: Epochless Approach to Batched Threshold ...
7. [2024/1534] More Efficient Lattice-based OLE from Circuit- ...
8. [2024/1535] Relaxed Lattice-Based Programmable Hash Functions: ...
9. [2024/1536] Cryptographic Characterization of Quantum Advantage
10. [2024/1537] VOLE-in-the-head signatures from Subfield Bilinear ...
11. [2024/1538] Security Perceptions of Users in Stablecoins: ...
12. [2024/1539] Quantum Cryptography from Meta-Complexity
13. [2024/1540] Formal Security Analysis of the OpenID FAPI 2.0 ...
14. [2024/1541] Findex: A Concurrent and Database-Independent ...
15. [2024/1542] Robust AE With Committing Security
16. [2024/1543] HEonGPU: a GPU-based Fully Homomorphic Encryption ...
17. [2024/1544] PoUDR: Proof of Unified Data Retrieval in ...
18. [2024/1545] Fully Composable Homomorphic Encryption
19. [2024/1546] Bit t-SNI Secure Multiplication Gadget for Inner ...
20. [2024/1547] HHL for tensor-decomposable matrices
21. [2024/1548] Fully-Succinct Arguments over the Integers from ...
22. [2024/1549] Universally Composable SNARKs with Transparent ...
23. [2024/1550] MAYO Key Recovery by Fixing Vinegar Seeds
24. [2024/1551] SNARKs for Virtual Machines are Non-Malleable
25. [2024/1552] Revisiting Keyed-Verification Anonymous Credentials
26. [2024/1553] STARK-based Signatures from the RPO Permutation
27. [2024/1554] Breaking, Repairing and Enhancing XCBv2 into the ...
28. [2024/1555] Private Laconic Oblivious Transfer with Preprocessing
29. [2024/1556] The module action for isogeny based cryptography
30. [2024/1557] Tightly Secure Threshold Signatures over Pairing- ...
31. [2024/1558] Understanding Leakage in Searchable Encryption: a ...
32. [2024/1559] Mind the Composition of Toffoli Gates: Structural ...
33. [2024/1560] Revisiting Shuffle-Based Private Set Unions with ...
34. [2024/1561] FLUENT: A Tool for Efficient Mixed-Protocol Semi- ...
35. [2024/1562] Fully Privacy-preserving Billing Models for Peer- ...
36. [2024/1563] Optimized One-Dimensional SQIsign Verification on ...
37. [2024/1564] A Simple Framework for Secure Key Leasing
38. [2024/1565] Fiat-Shamir in the Wild
39. [2024/1566] Dynamic zk-SNARKs
40. [2024/1567] A New World in the Depths of Microcrypt: Separating ...
41. [2024/1568] Oracle Separation Between Quantum Commitments and ...
42. [2024/1569] The Supersingular Isogeny Path and Endomorphism ...

## 2024/762

* Title: Constant-Cost Batched Partial Decryption in Threshold Encryption
* Authors: Sora Suegami, Shinsaku Ashizawa, Kyohei Shibano
* [Permalink](https://eprint.iacr.org/2024/762)
* [Download](https://eprint.iacr.org/2024/762.pdf)

### Abstract

Threshold public key encryption schemes distribute secret keys among multiple parties, known as the committee, to reduce reliance on a single trusted entity.
However, existing schemes face inefficiencies as the committee should perform computation and communication for decryption of each individual ciphertext.
As the number of ciphertexts being decrypted per unit of time increases, this can limit the number of committee parties and their decentralization due to increased hardware requirements, heightening the risk of adversarial collusion.
To address this, we introduce tag-based batched threshold encryption (TBTE), which ensures constant computational and communication costs per committee member, independent of the number of ciphertexts being decrypted in batch under distinct decryption policies.
The TBTE scheme is constructed over bilinear groups in the random oracle model and secure in the algebraic group model, assuming the hardness of the $(q_1,q_2)$-discrete logarithm problem and the EAV-security of the symmetric-key encryption scheme.
Evaluation of our implementation demonstrates constant data size, specifically 48 bytes received and 56 bytes sent, and constant execution time for each committee party during decryption, even for various batch sizes up to $2^{20}$.

## 2024/766

* Title: Breaking Verifiable Delay Functions in the Random Oracle Model
* Authors: Ziyi Guan, Artur Riazanov, Weiqiang Yuan
* [Permalink](https://eprint.iacr.org/2024/766)
* [Download](https://eprint.iacr.org/2024/766.pdf)

### Abstract

A verifiable delay function (VDF) is a cryptographic primitive that requires a long time to compute (even with parallelization), but produces a unique output that is efficiently and publicly verifiable.

We prove that VDFs with \emph{imperfect completeness} and \emph{computational uniqueness} do not exist in the random oracle model. This also rules out black-box constructions of VDFs from other cryptographic primitives, such as one-way permutations and collision-resistant hash functions.

Prior to our work, Mahmoody, Smith and Wu (ICALP 2020) prove that VDFs satisfying both \emph{perfect completeness} and \emph{perfect uniqueness} do not exist in the random oracle model; on the other hand, Ephraim, Freitag, Komargodski, and Pass (Eurocrypt 2020) construct VDFs with \emph{perfect completeness} and \emph{computational uniqueness} in the random oracle model assuming the hardness of repeated squaring. Our result is optimal -- we bridge the current gap between previously known impossibility results and existing constructions.

## 2024/1530

* Title: Folding Schemes with Privacy Preserving Selective Verification
* Authors: Joan Boyar, Simon Erfurth
* [Permalink](https://eprint.iacr.org/2024/1530)
* [Download](https://eprint.iacr.org/2024/1530.pdf)

### Abstract

Folding schemes are an exciting new primitive, transforming the task of performing multiple zero-knowledge proofs of knowledge for a relation into performing just one zero-knowledge proof, for the same relation, and a number of cheap inclusion-proofs. Recently, folding schemes have been used to amortize the cost associated with proving different statements to multiple distinct verifiers, which has various applications. We observe that for these uses, leaking information about the statements folded together can be problematic, yet this happens with previous constructions. Towards resolving this issue, we give a natural definition of privacy preserving folding schemes, and what security they should offer. To construct privacy preserving folding schemes, we first define a statement hiders, a primitive which might be of independent interest. In a nutshell, a statement hider hides an instance of a relation as a new instance in the same relation. The new instance is in the relation if and only if the initial instance is. With this building block, we can utilize existing folding schemes to construct a privacy preserving folding scheme, by first hiding each of the statements. Folding schemes allow verifying that a statement was folded into another statement, while statement hiders allow verifying that a statement was hidden as another statement.

## 2024/1531

* Title: FLI: Folding Lookup Instances
* Authors: Albert Garreta, Ignacio Manzur
* [Permalink](https://eprint.iacr.org/2024/1531)
* [Download](https://eprint.iacr.org/2024/1531.pdf)

### Abstract

We introduce two folding schemes for lookup instances: FLI and FLI+SOS. Both use a PIOP to check that a matrix has elementary basis vectors as rows, with FLI+SOS adding a twist based on Lasso’s SOS-decomposability.

FLI takes two lookup instances $\{\mathbf{a}_1\}, \{\mathbf{a}_2\}\subseteq\mathbf{t}$, and expresses them as matrix equations $M_i\cdot\mathbf{t}^\mathsf{T}=\mathbf{a}_i^\mathsf{T}$ for $i=1,2$, where each matrix $M_i\in\mathbb{F}^{m\times N}$ has rows which are elementary basis vectors in $\mathbb{F}^N$. Matrices that satisfy this condition are said to be in $R_{\mathsf{elem}}$. Then, a folding scheme for $R_{\mathsf{elem}}$ into a relaxed relation is used, which combines the matrices $M_1, M_2$ as $M_1+\alpha M_2$ for a random $\alpha\in\mathbb{F}$. Finally, the lookup equations are combined as $(M_1+\alpha M_2)\cdot \mathbf{t}^{\mathsf{T}} = (\mathbf{a}_1+\alpha \mathbf{a}_2)^\mathsf{T}$. In FLI, only the property that a matrix is in $R_{\mathsf{elem}}$ is folded, and this makes the FLI folding step the cheapest among existing solutions. The price to pay is in the cost for proving accumulated instances.

FLI+SOS builds upon FLI to enable folding of large SOS-decomposable tables. This is achieved through a variation of Lasso's approach to SOS-decomposability, which fits FLI naturally. For comparison, we describe (for the first time to our knowledge) straightforward variations of Protostar and Proofs for Deep Thought that also benefit from SOS-decomposability. We see that for many reasonable parameter choices, and especially those arising from lookup-based zkVMs, FLI+SOS can concretely be the cheapest folding solution.

## 2024/1532

* Title: Bitwise Garbling Schemes --- A Model with $\frac{3}{2}\kappa$-bit Lower Bound of Ciphertexts
* Authors: Fei Xu, Honggang Hu, Changhong Xu
* [Permalink](https://eprint.iacr.org/2024/1532)
* [Download](https://eprint.iacr.org/2024/1532.pdf)

### Abstract

At Eurocrypt 2015, Zahur, Rosulek, and Evans proposed the model of Linear Garbling Schemes. This model proved a $2\kappa$-bit lower bound of ciphertexts for a broad class of garbling schemes. Since then, several methods have been developed that bypass this lower bound, albeit with a notable limitation: Their reliance on specifically correlated input wire labels restricts their applicability across most gates. At Crypto 2021, Rosulek and Roy presented the innovative "three-halves" garbling scheme in which AND gates cost $1.5\kappa+5$ bits and XOR gates are free. A noteworthy aspect of their scheme is the slicing-and-dicing technique, which is applicable universally to all AND gates when garbling a boolean circuit. Following this revelation, Rosulek and Roy presented several open problems. Our research primarily addresses one of them: ``Is $1.5\kappa$ bits optimal for garbled AND gates in a more inclusive model than Linear Garbling Schemes?''