## In this issue

1. [2023/1534] Evolving Secret Sharing Made Short
2. [2024/380] Collision Resistance from Multi-Collision ...
3. [2024/771] SQIsign2D-East: A New Signature Scheme Using ...
4. [2024/1391] Scalable Equi-Join Queries over Encrypted Database
5. [2024/1394] SLAMP-FSS: Two-Party Multi-Point Function Secret ...
6. [2024/1396] Rare structures in tensor graphs - Bermuda ...
7. [2024/1397] Efficient Batch Algorithms for the Post-Quantum ...
8. [2024/1398] Coercion-resistant i-voting with short PIN and ...
9. [2024/1399] A Note on Ligero and Logarithmic Randomness
10. [2024/1400] Efficient Asymmetric PAKE Compiler from KEM and AE
11. [2024/1401] New Techniques for Preimage Sampling: Improved ...
12. [2024/1402] A Recursive zk-based State Update System
13. [2024/1403] Hard-Label Cryptanalytic Extraction of Neural ...
14. [2024/1404] $\Pi$-signHD: A New Structure for the SQIsign ...
15. [2024/1405] Lego-DLC: batching module for commit-carrying SNARK ...
16. [2024/1406] Blind Multisignatures for Anonymous Tokens with ...
17. [2024/1407] Encrypted MultiChannel Communication (EMC2): Johnny ...
18. [2024/1408] Multiple-Tweak Differential Attack Against SCARF
19. [2024/1409] Oraqle: A Depth-Aware Secure Computation Compiler
20. [2024/1410] Cryptobazaar: Private Sealed-bid Auctions at Scale
21. [2024/1411] Design issues of ``an anonymous authentication and ...
22. [2024/1412] The Zeros of Zeta Function Revisited
23. [2024/1413] The Black-Box Simulation Barrier Persists in a ...
24. [2024/1414] Code-Based Zero-Knowledge from VOLE-in-the-Head and ...
25. [2024/1415] Privacy Comparison for Bitcoin Light Client ...
26. [2024/1416] Circuit ABE with poly(depth, λ)-sized Ciphertexts ...
27. [2024/1417] Distributed Broadcast Encryption from Lattices
28. [2024/1418] Public-key encryption from a trapdoor one-way ...
29. [2024/1419] On the Relationship between Public Key Primitives ...
30. [2024/1420] Privacy-Preserving Breadth-First-Search and ...
31. [2024/1421] Provable Security of Linux-DRBG in the Seedless ...
32. [2024/1422] ZKFault: Fault attack analysis on zero-knowledge ...
33. [2024/1423] Towards package opening detection at power-up by ...
34. [2024/1424] A Waterlog for Detecting and Tracing Synthetic Text ...
35. [2024/1425] New constructions of pseudorandom codes
36. [2024/1426] Agile Asymmetric Cryptography and the Case for ...
37. [2024/1427] LogRobin++: Optimizing Proofs of Disjunctive ...
38. [2024/1428] Mario: Multi-round Multiple-Aggregator Secure ...
39. [2024/1429] Powerformer: Efficient Privacy-Preserving ...
40. [2024/1430] MYao: Multiparty ``Yao'' Garbled Circuits with Row ...
41. [2024/1431] Interactive Line-Point Zero-Knowledge with ...
42. [2024/1432] On Multi-user Security of Lattice-based Signature ...
43. [2024/1433] $Shortcut$: Making MPC-based Collaborative ...
44. [2024/1434] Untangling the Security of Kilian's Protocol: Upper ...
45. [2024/1435] Actively Secure Polynomial Evaluation from Shared ...
46. [2024/1436] Eva: Efficient IVC-Based Authentication of Lossy- ...
47. [2024/1437] HierNet: A Hierarchical Deep Learning Model for SCA ...

## 2023/1534

* Title: Evolving Secret Sharing Made Short
* Authors: Danilo Francati, Daniele Venturi
* [Permalink](https://eprint.iacr.org/2023/1534)
* [Download](https://eprint.iacr.org/2023/1534.pdf)

### Abstract

Evolving secret sharing (Komargodski, Naor, and Yogev, TCC’16) generalizes the notion of secret sharing to the setting of evolving access structures, in which the share holders are added to the system in an online manner, and where the dealer does not know neither the access structure nor the maximum number of parties in advance. Here, the main difficulty is to distribute shares to the new players without updating the shares of old players; moreover, one would like to minimize the share size as a function of the number of players.
In this paper, we initiate a systematic study of evolving secret sharing in the computational setting, where the maximum number of parties is polynomial in the security parameter, but the dealer still does not know this value, neither it knows the access structure in advance. Moreover, the privacy guarantee only holds against computationally bounded adversaries corrupting an unauthorized subset of the players.
Our main result is that for many interesting, and practically relevant, evolving access structures (including graphs access structures, DNF and CNF formulas access structures, monotone circuits access structures, and threshold access structures), under standard hardness assumptions, there exist efficient secret sharing schemes with computational privacy and in which the shares are succinct (i.e., much smaller compared to the size of a natural computational representation of the evolving access structure).

## 2024/380

* Title: Collision Resistance from Multi-Collision Resistance for all Constant Parameters
* Authors: Jan Buzek, Stefano Tessaro
* [Permalink](https://eprint.iacr.org/2024/380)
* [Download](https://eprint.iacr.org/2024/380.pdf)

### Abstract

A $t$-multi-collision-resistant hash function ($t$-MCRH) is a family of shrinking functions for which it is computationally hard to find $t$ distinct inputs mapping to the same output for a function sampled from this family. Several works have shown that $t$-MCRHs are sufficient for many of the applications of collision-resistant hash functions (CRHs), which correspond to the special case of $t = 2$.

An important question is hence whether $t$-MCRHs for $t > 2$ are fundamentally weaker objects than CRHs. As a first step towards resolving this question, Rothblum and Vasudevan (CRYPTO '22) recently gave non-black-box constructions of infinitely-often secure CRHs from $t$-MCRHs for $t \in \{3,4\}$ assuming the MCRH is sufficiently shrinking. Earlier on, Komargodski and Yogev (CRYPTO '18) also showed that $t$-MCRHs for any constant $t$ imply the weaker notion of a distributional CRH.

In this paper, we remove the limitations of prior works, and completely resolve the question of the power of $t$-MCRHs for constant $t$ in the infinitely-often regime, showing that the existence of such a function family always implies the existence of an infinitely-often secure CRH. As in the works mentioned above, our construction is non-blackbox and non-constructive. We further give a new domain extension result for MCRHs that enables us to show that the underlying MCRH need only have arbitrarily small linear shrinkage (mapping $(1 + \epsilon)n$ bits to $n$ bits for any fixed $\epsilon > 0$) to imply the existence of CRHs.

## 2024/771

* Title: SQIsign2D-East: A New Signature Scheme Using 2-dimensional Isogenies
* Authors: Kohei Nakagawa, Hiroshi Onuki
* [Permalink](https://eprint.iacr.org/2024/771)
* [Download](https://eprint.iacr.org/2024/771.pdf)

### Abstract

Isogeny-based cryptography is cryptographic schemes whose security is based on the hardness of a mathematical problem called the isogeny problem, and is attracting attention as one of the candidates for post-quantum cryptography. A representative isogeny-based cryptography is the signature scheme called SQIsign, which was submitted to the NIST PQC standardization competition. SQIsign has attracted much attention because of its very short signature and key size among the candidates for the NIST PQC standardization. Recently, a lot of new schemes have been proposed that use high-dimensional isogenies. Among them, the signature scheme called SQIsignHD has an even shorter signature size than SQIsign. However, it requires 4-dimensional isogeny computations for the signature verification.

In this paper, we propose a new signature scheme, SQIsign2D-East, which requires only two-dimensional isogeny computations for verification, thus reducing the computational cost of verification. First, we generalized an algorithm called RandIsogImg, which computes a random isogeny of non-smooth degree. Then, by using this generalized RandIsogImg, we construct a new signature scheme SQIsign2D-East.

## 2024/1391

* Title: Scalable Equi-Join Queries over Encrypted Database
* Authors: Kai Du, Jianfeng Wang, Jiaojiao Wu, Yunling Wang
* [Permalink](https://eprint.iacr.org/2024/1391)
* [Download](https://eprint.iacr.org/2024/1391.pdf)

### Abstract

Secure join queries over encrypted databases, the most expressive class of SQL queries, have attracted extensive attention recently. The state-of-the-art JXT (Jutla et al. ASIACRYPT 2022) enables join queries on encrypted relational databases without pre-computing all possible joins. However, JXT can merely support join queries over two tables (in encrypted databases) with some high-entropy join attributes.

In this paper, we propose an equi-join query protocol over two tables dubbed JXT+, that allows the join attributes with arbitrary names instead of JXT requiring the identical name for join attributes. JXT+ reduces the query complexity from $O(\ell_1 \cdot \ell_2)$ to $O(\ell_1)$ as compared to JXT, where $\ell_1$ and $\ell_2$ denote the numbers of matching records in two tables respectively. Furthermore, we present JXT++, the \emph{first} equi-join queries across three or more tables over encrypted databases without pre-computation. Specifically, JXT++ supports joins of arbitrary attributes, i.e., all attributes (even low-entropy) can be candidates for join, while JXT requires high-entropy join attributes. In addition, JXT++ can alleviate sub-query leakage on three or more tables, which hides the leakage from the matching records of two-table join.

Finally, we implement and compare our proposed schemes with the state-of-the-art JXT. The experimental results demonstrate that both of our schemes are superior to JXT in search and storage costs. In particular, JXT+ (resp., JXT++) brings a saving of 49% (resp., 68%) in server storage cost and achieves a speedup of 51.7$\times$ (resp., 54.3$\times$) in search latency.