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



## 2024/1394

* Title: SLAMP-FSS: Two-Party Multi-Point Function Secret Sharing from Simple Linear Algebra
* Authors: Erki Külaots, Toomas Krips, Hendrik Eerikson, Pille Pullonen-Raudvere
* [Permalink](https://eprint.iacr.org/2024/1394)
* [Download](https://eprint.iacr.org/2024/1394.pdf)

### Abstract

Multiparty computation (MPC) is an important field of cryptography that deals with protecting the privacy of data, while allowing to do computation on that data. A key part of MPC is the parties involved having correlated randomness that they can use to
make the computation or the communication between themselves more efficient, while still preserving the privacy of the data. Examples of these correlations include random oblivious transfer (OT) correlations, oblivious linear-function evaluation (OLE)
correlations, multiplication triples (also known as Beaver triples) and one-time truth tables. Multi-point function secret sharing (FSS) has been shown to be a great building block for pseudo-random correlation generators. The main question is how to
construct fast and efficient multi-point FSS schemes. Here we propose a natural generalization of the scheme of Boyle et al 2016 using a tree structure, a pseudorandom generator and systems of linear equations.
Our schemes SLAMP-FSS and SLAMPR-FSS are more efficient in the evaluation phase than other previously proposed multi-point FSS schemes while being also more flexible and being similar in other efficiency parameters.



## 2024/1396

* Title: Rare structures in tensor graphs - Bermuda triangles for cryptosystems based on the Tensor Isomorphism problem
* Authors: Lars Ran, Simona Samardjiska
* [Permalink](https://eprint.iacr.org/2024/1396)
* [Download](https://eprint.iacr.org/2024/1396.pdf)

### Abstract

Recently, there has been a lot of interest in improving the understanding of the practical hardness of the 3-Tensor Isomorphism (3-TI) problem, which, given two 3-tensors, asks for an isometry between the two. The current state-of-the-art for solving
this problem is the algebraic algorithm of Ran et al. '23 and the graph-theoretic algorithm of Narayanan et al. '24 that have both slightly reduced the security of the signature schemes MEDS and ALTEQ, based on variants of the 3-TI problem (Matrix Code
Equivalence (MCE) and Alternating Trilinear Form Equivalence (ATFE) respectively).

In this paper, we propose a new combined technique for solving the 3-TI problem. Our algorithm, as typically done in graph-based algorithms, looks for an invariant in the graphs of the isomorphic tensors that can be used to recover the secret isometry.
However, contrary to usual combinatorial approaches, our approach is purely algebraic. We model the invariant as a system of non-linear equations and solve it. Using this modelling we are able to find very rare invariant objects in the graphs of the
tensors — cycles of length 3 (triangles) — that exist with probability approximately $1/q$. For solving the system of non-linear equations we use Gröbner-basis techniques adapted to tri-graded polynomial rings. We analyze the algorithm theoretically,
and we provide lower and upper bounds on its complexity. We further provide experimental support for our complexity claims. Finally, we describe two dedicated versions of our algorithm tailored to the specifics of the MCE and the ATFE problems.

The implications of our algorithm are improved cryptanalysis of both MEDS and ALTEQ for the cases when a triangle exists, i.e. in approximately $1/q$ of the cases. While for MEDS, we only marginally reduce the security compared to previous work, for
ALTEQ our results are much more significant with at least 60 bits improvement compared to previous work for all security levels. For Level I parameters, our attack is practical, and we are able to recover the secret key in only 1501 seconds.
The code is available for testing and verification of our results.



## 2024/1397

* Title: Efficient Batch Algorithms for the Post-Quantum Crystals Dilithium Signature Scheme and Crystals Kyber Encryption Scheme
* Authors: Nazlı Deniz TÜRE, Murat CENK
* [Permalink](https://eprint.iacr.org/2024/1397)
* [Download](https://eprint.iacr.org/2024/1397.pdf)

### Abstract

Digital signatures ensure authenticity and secure communication. They are used to verify the integrity and authenticity of signed documents and are widely utilized in various fields such as information technologies, finance, education, and law. They are
crucial in securing servers against cyber attacks and authenticating connections between clients and servers. Additionally, encryption is used in many areas, such as secure communication, cloud, server and database security to ensure data confidentiality.
Performing batch encryption, signature generation, and signature verification simultaneously and efficiently is highlighted as a beneficial approach for many systems. This work focuses on efficient batch signature generation with Dilithium, batch
verifications of signatures from the same user using Crystals Dilithium (NIST's post-quantum digital signature standard) and batch encryption to a single user with Crystals Kyber (NIST's post-quantum encryption/KEM standard). One of the main operations
of Dilithium and Kyber is the matrix-vector product with polynomial entries. So, the naive approach to generate/verify m signatures with Dilithium (or encrypt $m$ messages with Kyber) where m>1 is to perform $m$ such multiplications. In this paper, we
propose to use efficient matrix multiplications of sizes greater than four to generate/verify m signatures with Dilithium and greater than two to encrypt $m$ messages with Kyber. To this end, batch algorithms that transform the polynomial matrix-vector
multiplication in Dilithium's and Kyber's structures into polynomial matrix-matrix multiplication are designed. The batch numbers and the sizes of the matrices to be multiplied based on the number of repetitions of Dilithium's signature algorithm are
determined. Also, batch versions of Dilithium verification and Kyber encryption algorithms are proposed. Moreover, many efficient matrix-matrix multiplication algorithms, such as Strassen-like multiplications and commutative matrix multiplications, are
analyzed to design the best algorithms that are compatible with the specified dimensions and yield improvements. Various multiplication formulas are derived for different security levels of Dilithium signature generation, verification, and Kyber
encryption. Improvements up to 28.1%, 33.3%, and 31.5% in the arithmetic complexities are observed at three different security levels of Dilithium's signature, respectively. The proposed batch Dilithium signature algorithm and the efficient
multiplication algorithms are also implemented, and 34.22%, 17.40%, and 10.15% improvements on CPU cycle counts for three security levels are obtained. The multiplication formulas used for batch Dilithium signature generation are also applied for batch
Dilithium verification. At three different levels of security, improvements in the arithmetic complexity are observed of up to 28.13%, 33.33%, and 31.25%. Furthermore, 49.88%, 56.60%, and 61.08% improvements on CPU cycle counts for three security levels
are achieved, respectively. As a result of implementing Kyber Batch Encryption with efficient multiplication algorithms, 12.50%, 22.22%, and 28.13% improvements on arithmetic complexity, as well as 22.34%, 24.07%, and 30.83\% improvements on CPU cycle
counts, are observed for three security levels.



## 2024/1398

* Title: Coercion-resistant i-voting with short PIN and OAuth 2.0
* Authors: Matteo Bitussi, Riccardo Longo, Francesco Antonio Marino, Umberto Morelli, Amir Sharif, Chiara Spadafora, Alessandro Tomasi
* [Permalink](https://eprint.iacr.org/2024/1398)
* [Download](https://eprint.iacr.org/2024/1398.pdf)

### Abstract

This paper presents an architecture for an OAuth 2.0-based i-voting
solution using a mobile native client in a variant of the Ara´ujo-Traor´e protocol. We follow a systematic approach by identifying relevant OAuth
2.0 specifications and best practices. Having defined our framework, we identify threats applicable to our proposed methodology and detail how
our design mitigates them to provide a safer i-voting process.



## 2024/1399

* Title: A Note on Ligero and Logarithmic Randomness
* Authors: Guillermo Angeris, Alex Evans, Gyumin Roh
* [Permalink](https://eprint.iacr.org/2024/1399)
* [Download](https://eprint.iacr.org/2024/1399.pdf)

### Abstract

We revisit the Ligero proximity test, and its logarithmic randomness variant, in the framework of [EA23] and show a simple proof that improves the soundness error of the original logarithmic randomness construction of [DP23] by a factor of two. This note
was originally given as a presentation in ZK Summit 11.



## 2024/1400

* Title: Efficient Asymmetric PAKE Compiler from KEM and AE
* Authors: You Lyu, Shengli Liu, Shuai Han
* [Permalink](https://eprint.iacr.org/2024/1400)
* [Download](https://eprint.iacr.org/2024/1400.pdf)

### Abstract

Password Authenticated Key Exchange (PAKE) allows two parties to establish a secure session key with a shared low-entropy password pw. Asymmetric PAKE (aPAKE) extends PAKE in the client-server setting, and the server only stores a password file instead
of the plain password so as to provide additional security guarantee when the server is compromised.

In this paper, we propose a novel generic compiler from PAKE to aPAKE in the Universal Composable (UC) framework by making use of Key Encapsulation Mechanism (KEM) and Authenticated Encryption (AE).

-- Our compiler admits efficient instantiations from lattice to yield lattice-based post-quantum secure aPAKE protocols. When instantiated with Kyber (the standardized KEM algorithm by the NIST), the performances of our compiler outperform other
lattice-based compilers (Gentry et al. CRYPTO 2006) in all aspects, hence yielding the most efficient aPAKE compiler from lattice. In particular, when applying our compiler to the UC-secure PAKE schemes (Santos et al. EUROCRYPT 2023, Beguinet et al. ACNS
2023), we obtain the most efficient UC-secure aPAKE schemes from lattice.

-- Moreover, the instantiation of our compiler from the tightly-secure matrix DDH (MDDH)-based KEM (Pan et al. CRYPTO 2023) can compile the tightly-secure % CDH-based PAKE scheme (Liu et al. PKC 2023) to a tightly-secure MDDH-based aPAKE, which serves
as the first tightly UC-secure aPAKE scheme.



## 2024/1401

* Title: New Techniques for Preimage Sampling: Improved NIZKs and More from LWE * Authors: Brent Waters, Hoeteck Wee, David J. Wu
* [Permalink](https://eprint.iacr.org/2024/1401)
* [Download](https://eprint.iacr.org/2024/1401.pdf)

### Abstract

Recent constructions of vector commitments and non-interactive zero-knowledge (NIZK) proofs from LWE implicitly solve the following /shifted multi-preimage sampling problem/: given matrices $\mathbf{A}_1, \ldots, \mathbf{A}_\ell \in \mathbb{Z}_q^{n \
times m}$ and targets $\mathbf{t}_1, \ldots, \mathbf{t}_\ell \in \mathbb{Z}_q^n$, sample a shift $\mathbf{c} \in \mathbb{Z}_q^n$ and short preimages $\boldsymbol{\pi}_1, \ldots, \boldsymbol{\pi}_\ell \in \mathbb{Z}_q^m$ such that $\mathbf{A}_i \
boldsymbol{\pi}_i = \mathbf{t}_i + \mathbf{c}$ for all $i \in [\ell]$. In this work, we introduce a new technique for sampling $\mathbf{A}_1, \ldots, \mathbf{A}_\ell$ together with a succinct public trapdoor for solving the multi-preimage sampling
problem with respect to $\mathbf{A}_1, \ldots, \mathbf{A}_\ell$. This enables the following applications:

* We provide a dual-mode instantiation of the hidden-bits model (and by correspondence, a dual-mode NIZK proof for NP) with (1) a linear-size common reference string (CRS); (2) a transparent setup in hiding mode (which yields statistical NIZK arguments);
and (3) hardness from LWE with a polynomial modulus-to-noise ratio. This improves upon the work of Waters (STOC 2024) which required a quadratic-size structured reference string (in both modes) and LWE with a super-polynomial modulus-to-noise ratio.

* We give a statistically-hiding vector commitment with transparent setup and polylogarithmic-size CRS, commitments, and openings from SIS. This simultaneously improves upon the vector commitment schemes of de Castro and Peikert (EUROCRYPT 2023) as well
as Wee and Wu (EUROCRYPT 2023).

At a conceptual level, our work provides a unified view of recent lattice-based vector commitments and hidden-bits model NIZKs through the lens of the shifted multi-preimage sampling problem.



## 2024/1402

* Title: A Recursive zk-based State Update System
* Authors: Daniel Bloom, Sai Deng
* [Permalink](https://eprint.iacr.org/2024/1402)
* [Download](https://eprint.iacr.org/2024/1402.pdf)

### Abstract

This paper introduces a ZKP (zero-knowledge proof) based state update system, where each block contains a SNARK proof aggregated from the user generated zkVM (zero knowledge virtual machine) proofs. It enables users to generate state update proofs in
their local machines, contributing to a secure, decentralized verification process. Our main contribution in this paper, the recursive proofs system, addresses scalability by recursively verifying user proofs and aggregating them in a hierarchical tree
structure up to a root proof, serving as a block proof. The proposed solution advances current blockchain paradigms by offering efficient recursive verification through ZKP, enhancing security and reducing computational load.



## 2024/1403

* Title: Hard-Label Cryptanalytic Extraction of Neural Network Models
* Authors: Yi Chen, Xiaoyang Dong, Jian Guo, Yantian Shen, Anyu Wang, Xiaoyun Wang
* [Permalink](https://eprint.iacr.org/2024/1403)
* [Download](https://eprint.iacr.org/2024/1403.pdf)

### Abstract

The machine learning problem of extracting neural network parameters has been proposed for nearly three decades. Functionally equivalent extraction is a crucial goal for research on this problem. When the adversary has access to the raw output of
neural networks, various attacks, including those presented at CRYPTO 2020 and EUROCRYPT 2024, have successfully achieved this goal. However, this goal is not achieved when neural networks operate under a hard-label setting where the raw output is
inaccessible.
In this paper, we propose the first attack that theoretically achieves functionally equivalent extraction under the hard-label setting, which applies to ReLU neural networks. The effectiveness of our attack is validated through practical experiments on
a wide range of ReLU neural networks, including neural networks trained on two real benchmarking datasets (MNIST, CIFAR10) widely used in computer vision. For a neural network consisting of $10^5$ parameters, our attack only requires several hours on a
single core.



## 2024/1404

* Title: $\Pi$-signHD: A New Structure for the SQIsign Family with Flexible Applicability
* Authors: Kaizhan Lin, Weize Wang, Chang-An Zhao, Yunlei Zhao
* [Permalink](https://eprint.iacr.org/2024/1404)
* [Download](https://eprint.iacr.org/2024/1404.pdf)

### Abstract

Digital signature is a fundamental cryptographic primitive and is widely used in the real world. Unfortunately, the current digital signature standards like EC-DSA and RSA are not quantum-resistant. Among post-quantum cryptography (PQC), isogeny-based
signatures preserve some advantages of elliptic curve cryptosystems, particularly offering small signature sizes. Currently, SQIsign and its variants are the most promising isogeny-based digital signature schemes.
In this paper, we propose a new structure for the SQIsign family: Pentagon Isogeny-based Signature in High Dimension (referred to as $\Pi$-signHD).
The new structure separates the hash of the commitment and that of the message by employing two cryptographic hash functions. This feature is desirable in reality, particularly for applications based on mobile low-power devices or for those deployed
interactively over the Internet or in the cloud computing setting. This structure can be generally applicable to all the variants of SQIsign. In this work, we focus on the instance based on SQIsignHD, proposed by Dartois, Leroux, Robert and Wesolowski (
Eurocrypt 2024). Compared with SQIsignHD, $\Pi$-signHD has the same signature size (even smaller for some application scenarios). For the NIST-I security level, the signature size of $\Pi$-signHD can be reduced to 519 bits, while the SQIsignHD signature
takes 870 bits. Additionally, $\Pi$-signHD has an efficient online signing process, and enjoys much desirable application flexibility. In our experiments, the online signing process of $\Pi$-signHD runs in 4 ms.



## 2024/1405

* Title: Lego-DLC: batching module for commit-carrying SNARK under Pedersen Engines
* Authors: Byeongjun Jang, Gweonho Jeong, Hyuktae Kwon, Hyunok Oh, Jihye Kim
* [Permalink](https://eprint.iacr.org/2024/1405)
* [Download](https://eprint.iacr.org/2024/1405.pdf)

### Abstract

The synergy of commitments and zk-SNARKs is
widely used in various applications, particularly in fields like
blockchain, to ensure data privacy and integrity without revealing
secret information. However, proving multiple commitments in
a batch imposes a large overhead on a zk-SNARK system. One
solution to alleviate the burden is the use of commit-and-prove
SNARK (CP-SNARK) approach. LegoSNARK defines a new
notion called commit-carrying SNARK (cc-SNARK), a special-
ized form of CP-SNARK, and introduces a compiler to build
commit-carrying SNARKs into commit-and-prove SNARKs. Us-
ing this compiler, the paper shows a commit-and-prove version
of Groth16 that improves the proving time (about 5,000×).
However, proving $l$-multiple commitments simultaneously with
this compiler faces a performance issue, as the linking system in
LegoSNARK requires $O(l)$ pairings on the verifier side.
To enhance efficiency, we propose a new batching module
called Lego-DLC, designed for handling multiple commitments. This
module is built by combining a $\Sigma$-protocol with commitment-
carrying SNARKs under Pedersen engines in which our mod-
ule can support all commit-carrying SNARKs under Pedersen
engines. In this paper, we provide the concrete instantiations
for Groth16 and Plonk. In the performance comparison, for
$2^{16}$ commitments, with a verification time of just 0.064s—over
30x faster than LegoSNARK’s 1.972s—our approach shows
remarkable efficiency. The slightly longer prover time of 1.413s
(compared to LegoSNARK’s 0.177s), around 8x is a small trade-
off for this performance gain.



## 2024/1406

* Title: Blind Multisignatures for Anonymous Tokens with Decentralized Issuance * Authors: Ioanna Karantaidou, Omar Renawi, Foteini Baldimtsi, Nikolaos Kamarinakis, Jonathan Katz, Julian Loss
* [Permalink](https://eprint.iacr.org/2024/1406)
* [Download](https://eprint.iacr.org/2024/1406.pdf)

### Abstract

We propose the first constructions of anonymous tokens with decentralized issuance. Namely, we consider a dynamic set of signers/issuers; a user can obtain a token from any subset of the signers, which is publicly verifiable and unlinkable to the
issuance process. To realize this new primitive we formalize the notion of Blind Multi-Signatures (BMS), which allow a user to interact with multiple signers to obtain a (compact) signature; even if all the signers collude they are unable to link a
signature to an interaction with any of them.

We then present two BMS constructions, one based on BLS signatures and a second based on discrete logarithms without pairings. We prove security of both our constructions in the Algebraic Group Model.

We also provide a proof-of-concept implementation and show that it has low-cost verification, which is the most critical operation in blockchain applications.



## 2024/1407

* Title: Encrypted MultiChannel Communication (EMC2): Johnny Should Use Secret Sharing
* Authors: Gowri R. Chandran, Kilian Demuth, Kasra Edalatnejad, Sebastian Linsner, Christian Reuter, Thomas Schneider
* [Permalink](https://eprint.iacr.org/2024/1407)
* [Download](https://eprint.iacr.org/2024/1407.pdf)

### Abstract

Nowadays, the problem of point-to-point encryption is solved by the wide adaptation of protocols like TLS. However, challenges persist for End-to-End Encryption (E2EE). Current E2EE solutions, such as PGP and secure messengers like Signal, suffer from
issues like 1) low usability, 2) small user base, 3) dependence on central service providers, and 4) susceptibility to backdoors. Concerns over legally mandated backdoors are rising as the US and EU are proposing new surveillance regulations requiring
chat monitoring. We present a new E2EE solution called Encrypted MultiChannel Communication, based on n-out-of-n secret sharing. EMC2 splits messages into multiple secret shares and sends them through independent channels. We show that multiple
independent channels exist between users and EMC2 provides E2EE with no single point of trust, no setup, and is understandable by the general public. Our solution complements existing tools and aims to strengthen the argument against legally enforced
backdoors by demonstrating their ineffectiveness.



## 2024/1408

* Title: Multiple-Tweak Differential Attack Against SCARF
* Authors: Christina Boura, Shahram Rasoolzadeh, Dhiman Saha, Yosuke Todo
* [Permalink](https://eprint.iacr.org/2024/1408)
* [Download](https://eprint.iacr.org/2024/1408.pdf)

### Abstract


[continued in next message]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)