[digest] 2024 Week 37

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

In this paper, we present the first third-party cryptanalysis of SCARF, a tweakable low-latency block cipher designed to thwart contention-based cache attacks through cache randomization. We focus on multiple-tweak differential attacks, exploiting biases across multiple tweaks. We establish a theoretical framework explaining biases for any number of rounds and verify this framework experimentally. Then, we use these properties to develop a key recovery attack on 7-round SCARF with a time complexity of \(2^{76}\), achieving a 98.9% success rate in recovering the 240-bit secret key. Additionally, we introduce a distinguishing attack on the full 8-round SCARF in a multi-key setting, with a complexity of \(c \times 2^{67.55}\), demonstrating that SCARF does not provide 80-bit security under these conditions. We also explore whether our approach could be extended to the single-key model and discuss the implications of different S-box choices on the attack success.



## 2024/1409

* Title: Oraqle: A Depth-Aware Secure Computation Compiler
* Authors: Jelle Vos, Mauro Conti, Zekeriya Erkin
* [Permalink](https://eprint.iacr.org/2024/1409)
* [Download](https://eprint.iacr.org/2024/1409.pdf)

### Abstract

In the past decade, tens of homomorphic encryption compilers have been released, and there are good reasons for these compilers to exist. Firstly, homomorphic encryption is a powerful secure computation technique in that it is relatively easy for parties to switch from plaintext computation to secure computations when compared to techniques like secret sharing. However, the technique is mathematically involved and requires expert knowledge to express computations as homomorphic encryption operations. So, these compilers support users who might otherwise not have the time or expertise to optimize the computation manually. Another reason is that homomorphic encryption is still computationally expensive, so compilers allow users to optimize their secure computation tasks.
One major shortcoming of these compilers is that they often do not allow users to use high-level primitives, such as equality checks, comparisons, and AND and OR operations between many operands. The compilers that do are either based on TFHE, requiring large bootstrapping keys that must be sent to the evaluator, or they only work in the Boolean domain, excluding many potentially more performant circuits.
Moreover, compilers must reduce the multiplicative depth of the circuits they generate to minimize the noise growth inherent to these homomorphic encryption schemes. However, many compilers only consider reducing the depth as an afterthought.
We propose the Oraqle compiler, which solves both problems at once by implementing depth-aware arithmetization, a technique for expressing high-level primitives as arithmetic operations that are executable by homomorphic encryption libraries. Instead of generating one possible circuit, the compiler generates multiple circuits that trade off the number of multiplications with the multiplicative depth. If the depth of the resulting circuits is low enough, they may be evaluated using a BFV or BGV library that does not require bootstrapping keys. We demonstrate that our compiler allows for significant performance gains.



## 2024/1410

* Title: Cryptobazaar: Private Sealed-bid Auctions at Scale
* Authors: Andrija Novakovic, Alireza Kavousi, Kobi Gurkan, Philipp Jovanovic
* [Permalink](https://eprint.iacr.org/2024/1410)
* [Download](https://eprint.iacr.org/2024/1410.pdf)

### Abstract

This work introduces Cryptobazaar, a novel scalable, private, and decentralized sealed-bid auction protocol. In particular, our protocol protects the privacy of losing bidders by preserving the confidentiality of their bids while ensuring public verifiability of the outcome and relying only on a single untrusted auctioneer for coordination. At its core, Cryptobazaar combines an efficient distributed protocol to compute the logical-OR for a list of unary-encoded bids with various novel zero-knowledge succinct arguments of knowledge that may be of independent interest. We further present variants of our protocol that can be used for efficient first-, second-, and more generally $(p+1)$st-price as well as sequential first-price auctions. Finally, the performance evaluation of our Cryptobazaar implementation shows that it is highly practical. For example, a single run of an auction with $128$ bidders and a price range of $1024$ values terminates in less than $0.5$ sec and requires each bidder to send and receive only about $32$ KB of data.



## 2024/1411

* Title: Design issues of ``an anonymous authentication and key agreement protocol in smart living''
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2024/1411)
* [Download](https://eprint.iacr.org/2024/1411.pdf)

### Abstract

The Li et al.'s scheme [Computer Communications, 186 (2022), 110-120)]  uses  XOR operation to realize the private transmission of sensitive information, under the assumption that if only one parameter in the expression $ a= b\oplus c $ is known, an adversary cannot retrieve the other two. The assumption neglects that the operands $b$ and $c$ must be of the same bit-length, which leads to the exposure of a substring in the longer operand.  The scheme wrongly treats timestamps as random strings to encrypt a confidential parameter. These misuses result in the loss of sensor node's anonymity, the loss of user anonymity and untraceability, insecurity against off-line password guessing attack, and insecurity against impersonation attack. The analysis techniques developed in this note is helpful for the future works on designing such schemes.



## 2024/1412

* Title: The Zeros of Zeta Function Revisited
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2024/1412)
* [Download](https://eprint.iacr.org/2024/1412.pdf)

### Abstract

Let $\zeta(z)=\sum_{n=1}^{\infty} \frac{1}{n^z}$, $\psi(z)=\sum_{n=1}^{\infty} \frac{(-1)^{n-1}}{n^z}, z\in \mathbb{C}$. We show that  $\psi(z)\not=(1-2^{1-z})\zeta(z)$, if $0<z<1$. Besides, we clarify that  the known zeros are not for the original series,  but very probably for the alternating series.



## 2024/1413

* Title: The Black-Box Simulation Barrier Persists in a Fully Quantum World
* Authors: Nai-Hui Chia, Kai-Min Chung, Xiao Liang, Jiahui Liu
* [Permalink](https://eprint.iacr.org/2024/1413)
* [Download](https://eprint.iacr.org/2024/1413.pdf)

### Abstract

Zero-Knowledge (ZK) protocols have been a subject of intensive study due to their fundamental importance and versatility in modern cryptography. However, the inherently different nature of quantum information significantly alters the landscape, necessitating a re-examination of ZK designs.

A crucial aspect of ZK protocols is their round complexity, intricately linked to $\textit{simulation}$, which forms the foundation of their formal definition and security proofs. In the $\textit{post-quantum}$ setting, where honest parties and their communication channels are all classical but the adversaries could be quantum, Chia, Chung, Liu, and Yamakawa [FOCS'21] demonstrated the non-existence of constant-round $\textit{black-box-simulatable}$ ZK arguments (BBZK) for $\mathbf{NP}$ unless $\mathbf{NP} \subseteq \mathbf{BQP}$. However, this problem remains widely open in the full-fledged quantum future that will eventually arrive, where all parties (including the honest ones) and their communication are naturally quantum.

Indeed, this problem is of interest to the broader theory of quantum computing. It has been an important theme to investigate how quantum power fundamentally alters traditional computational tasks, such as the $\textit{unconditional}$ security of Quantum Key Distribution and the incorporation of Oblivious Transfers in MiniQCrypt. Moreover, quantum communication has led to round compression for commitments and interactive arguments. Along this line, the above problem is of great significance in understanding whether quantum computing could also change the nature of ZK protocols in some fundamentally manner.

We resolved this problem by proving that only languages in $\mathbf{BQP}$ admit constant-round $\textit{fully-quantum}$ BBZK. This result holds significant implications. Firstly, it illuminates the nature of quantum zero-knowledge and provides valuable insights for designing future protocols in the quantum realm. Secondly, it relates ZK round complexity with the intriguing problem of $\mathbf{BQP}$ vs $\mathbf{QMA}$, which is out of the reach of previous analogue impossibility results in the classical or post-quantum setting. Lastly, it justifies the need for the $\textit{non-black-box}$ simulation techniques or the relaxed security notions employed in existing constant-round fully-quantum BBZK protocols.



## 2024/1414

* Title: Code-Based Zero-Knowledge from VOLE-in-the-Head and Their Applications: Simpler, Faster, and Smaller
* Authors: Ying Ouyang, Deng Tang, Yanhong Xu
* [Permalink](https://eprint.iacr.org/2024/1414)
* [Download](https://eprint.iacr.org/2024/1414.pdf)

### Abstract

Zero-Knowledge (ZK) protocols allow a prover to demonstrate the truth of a statement without disclosing additional information about the underlying witness. Code-based cryptography has a long history but did suffer from periods of slow development. Recently, a prominent line of research have been contributing to designing efficient code-based ZK from MPC-in-the-head (Ishai et al., STOC 2007) and VOLE-in-the head (VOLEitH)  (Baum et al., Crypto 2023) paradigms, resulting in quite efficient standard signatures. However, none of them could be directly used to construct privacy-preserving cryptographic primitives.. Therefore, Stern's protocols remain to be the major technical stepping stones for developing  advanced code-based privacy-preserving systems.

This work proposes new code-based ZK protocols from VOLEitH paradigm for various relations and designs several code-based privacy-preserving systems that considerably advance the state-of-the-art in code-based cryptography. Our first contribution is a new ZK protocol for proving the correctness of a regular (non-linear) encoding process, which is utilized in many advanced privacy-preserving systems. Our second contribution are new ZK protocols for concrete code-based relations.   In particular, we provide a ZK of accumulated values  with optimal witness size for the accumulator (Nguyen et al.,  Asiacrypt 2019).  Our protocols thus open the door for constructing more efficient  privacy-preserving systems. Moreover, our ZK protocols have the advantage of being simpler, faster, and smaller compared to Stern-like protocols.  To illustrate the effectiveness of our new ZK protocols, we develop ring signature (RS) scheme, group signature (GS) scheme, fully dynamic attribute-based signature scheme from our new ZK. The signature sizes of the resulting schemes are two to three orders of magnitude smaller than those based on Stern-like protocols in various parameter settings. Finally, our first ZK protocol yields a standard signature scheme, achieving ``signature size + public key size'' as small as $3.05$ KB, which is slightly smaller than the state-of-the-art signature scheme (Cui et al., PKC 2024) based on the regular syndrome decoding problems.



## 2024/1415

* Title: Privacy Comparison for Bitcoin Light Client Implementations
* Authors: Arad Kotzer, Ori Rottenstreich
* [Permalink](https://eprint.iacr.org/2024/1415)
* [Download](https://eprint.iacr.org/2024/1415.pdf)

### Abstract

Light clients implement a simple solution for Bitcoin's scalability problem, as they do not store the entire blockchain but only the state of particular addresses of interest. To be able to keep track of the updated state of their addresses, light clients rely on full nodes to provide them with the required information. To do so, they must reveal information about the addresses they are interested in. This paper studies the two most common light client implementations, SPV and Neutrino with regards to their privacy. We define privacy metrics for comparing the privacy of the different implementations. We evaluate and compare the privacy of the implementations over time on real Bitcoin data and discuss the inherent privacy-communication tradeoff. In addition, we propose general techniques to enhance light client privacy in the existing implementations. Finally, we propose a new SPV-based light client model, the aggregation model, evaluate it, and show it can achieve enhanced privacy than in the existing light client implementations.



## 2024/1416

* Title: Circuit ABE with poly(depth, λ)-sized Ciphertexts and Keys from Lattices
* Authors: Hoeteck Wee
* [Permalink](https://eprint.iacr.org/2024/1416)
* [Download](https://eprint.iacr.org/2024/1416.pdf)

### Abstract

We present new lattice-based attribute-based encryption (ABE) and
laconic function evaluation (LFE) schemes for circuits with *sublinear*
ciphertext overhead. For depth $d$ circuits over $\ell$-bit inputs, we obtain

* an ABE with ciphertext and secret key size $O(1)$;

* a LFE with ciphertext size $\ell + O(1)$ and digest size $O(1)$;

* an ABE with public key and ciphertext size $O(\ell^{2/3})$ and
secret key size $O(1)$,

where $O(\cdot)$ hides $\mbox{poly}(d,\lambda)$ factors. The first two results achieve almost optimal ciphertext and secret key / digest sizes, up to the $\mbox{poly}(d)$ dependencies.  The security of our schemes relies on $\ell$-succinct LWE, a falsifiable assumption which is implied by evasive LWE.  At the core of our results is a new technique for compressing LWE samples $\mathbf{s}(\mathbf{A}-\mathbf{x} \otimes \mathbf{G})$ as well as the matrix $\mathbf{A}$.



## 2024/1417

* Title: Distributed Broadcast Encryption from Lattices
* Authors: Jeffrey Champion, David J. Wu
* [Permalink](https://eprint.iacr.org/2024/1417)
* [Download](https://eprint.iacr.org/2024/1417.pdf)

### Abstract

A broadcast encryption scheme allows a user to encrypt a message to $N$ recipients with a ciphertext whose size scales sublinearly with $N$. While broadcast encryption enables succinct encrypted broadcasts, it also introduces a strong trust assumption and a single point of failure; namely, there is a central authority who generates the decryption keys for all users in the system. Distributed broadcast encryption offers an appealing alternative where there is a one-time (trusted) setup process that generates a set of public parameters.. Thereafter, users can independently generate their own public keys and post them to a public-key directory. Moreover, anyone can broadcast an encrypted message to any subset of user public keys with a ciphertext whose size scales sublinearly with the size of the broadcast set. Unlike traditional broadcast encryption, there are no long-term secrets in distributed broadcast encryption and users can join the system at any time (by posting their public key to the public-key directory).

Previously, distributed broadcast encryption schemes were known from standard pairing-based assumptions or from powerful tools like indistinguishability obfuscation or witness encryption. In this work, we provide the first distributed broadcast encryption scheme from a falsifiable lattice assumption. Specifically, we rely on the $\ell$-succinct learning with errors (LWE) assumption introduced by Wee (CRYPTO 2024). Previously, the only lattice-based candidate for distributed broadcast encryption goes through general-purpose witness encryption, which in turn is only known from the /private-coin/ evasive LWE assumption, a strong and non-falsifiable lattice assumption. Along the way, we also describe a more direct construction of broadcast encryption from lattices.



## 2024/1418

* Title: Public-key encryption from a trapdoor one-way embedding of $SL_2(\mathbb{N})$
* Authors: Robert Hines
* [Permalink](https://eprint.iacr.org/2024/1418)
* [Download](https://eprint.iacr.org/2024/1418.pdf)

### Abstract

We obfuscate words of a given length in a free monoid on two generators with a simple factorization algorithm (namely $SL_2(\mathbb{N})$) to create a public-key encryption scheme.  We provide a reference implementation in Python and suggested parameters.  The security analysis is between weak and non-existent, left to future work.



## 2024/1419

* Title: On the Relationship between Public Key Primitives via Indifferentiability
* Authors: Shuang Hu, Bingsheng Zhang, Cong Zhang, Kui Ren
* [Permalink](https://eprint.iacr.org/2024/1419)
* [Download](https://eprint.iacr.org/2024/1419.pdf)

### Abstract

Recently, Masny and Rindal [MR19] formalized a notion called Endemic Oblivious Transfer (EOT), and they proposed a generic transformation from Non-Interactive Key Exchange (NIKE) to EOT with standalone security in the random oracle (RO) model. However, from the model level, the relationship between idealized NIKE and idealized EOT and the relationship between idealized elementary public key primitives have been rarely researched.
In this work, we investigate the relationship between ideal NIKE and ideal one-round EOT, as well as the relationship between ideal public key encryption (PKE) and ideal two-round Oblivious Transfer (OT), in the indifferentiability framework proposed by Maurer et al.(MRH04). Our results are threefold: Firstly, we model ideal PKE without public key validity test, ideal one-round EOT and ideal two-round OT in the indifferentiability framework. Secondly, we show that ideal NIKE and ideal one-round EOT are equivalent, and ideal PKE without public key validity test are equivalent to ideal two-round OT. Thirdly, we show a separation between ideal two-round OT and ideal one-round EOT, which implies a separation between ideal PKE and ideal NIKE.



## 2024/1420

* Title: Privacy-Preserving Breadth-First-Search and Maximal-Flow
* Authors: Vincent Ehrmanntraut, Ulrike Meyer
* [Permalink](https://eprint.iacr.org/2024/1420)
* [Download](https://eprint.iacr.org/2024/1420.pdf)

### Abstract

We present novel Secure Multi-Party Computation (SMPC) protocols to perform Breadth-First-Searches (BFSs) and determine maximal flows on dense secret-shared graphs. In particular, we introduce a novel BFS protocol that requires only $\mathcal{O}(\log n)$ communication rounds on graphs with $n$ nodes, which is a big step from prior work that requires $\mathcal{O}(n \log n)$ rounds. This BFS protocol is then used in a maximal flow protocol based on the Edmonds-Karp algorithm, which requires $\mathcal{O}(n^3 \log n)$ rounds. We further optimize the protocol for cases where an upper bound $U$ on the capacities is publicly known by using a capacity scaling approach. This yields a new protocol which requires $\mathcal{O}(n^2 \log n \log U)$ rounds. Finally, we introduce a novel max flow protocol based on algorithms by Dinic and Tarjan with round complexity $\mathcal{O}(n^3)$.

All protocols presented in this paper use SMPC primitives as a black-box, allowing our protocols to be used as building blocks in a wide range of settings and applications. We evaluate our protocols with semi-honest and malicious security in different network settings. Our logarithmic BFS protocol is up to 69 times faster than prior protocols on small graphs with less than 100 nodes, but is outperformed by protocols with lower computational complexity on graphs with thousands of nodes. Further, we find our Dinic-Tarjan protocol to be faster than the Edmonds-Karp and capacity scaling protocols in our evaluation, albeit trends indicating capacity scaling protocols to be faster on graph sizes not reached in our evaluation.



## 2024/1421

* Title: Provable Security of Linux-DRBG in the Seedless Robustness Model
* Authors: Woohyuk Chung, Hwigyeom Kim, Jooyoung Lee, Yeongmin Lee
* [Permalink](https://eprint.iacr.org/2024/1421)
* [Download](https://eprint.iacr.org/2024/1421.pdf)

### Abstract

This paper studies the provable security of the deterministic random bit generator~(DRBG) utilized in Linux 6.4.8, marking the first analysis of Linux-DRBG from a provable security perspective since its substantial structural changes in Linux 4 and Linux 5.17. Specifically, we prove its security up to $O(\min\{2^{\frac{n}{2}},2^{\frac{\lambda}{2}}\})$ queries in the seedless robustness model, where $n$ is the output size of the internal primitives and $\lambda$ is the min-entropy of the entropy source. Our result implies $128$-bit security given $n=256$ and $\lambda=256$ for Linux-DRBG. We also present two distinguishing attacks using $O(2^{\frac{n}{2}})$ and $O (2^{\frac{\lambda}{2}})$ queries, respectively, proving the tightness of our security bound.



## 2024/1422

* Title: ZKFault: Fault attack analysis on zero-knowledge based post-quantum digital signature schemes
* Authors: Puja Mondal, Supriya Adhikary, Suparna Kundu, Angshuman Karmakar
* [Permalink](https://eprint.iacr.org/2024/1422)
* [Download](https://eprint.iacr.org/2024/1422.pdf)

### Abstract

Computationally hard problems based on coding theory, such as the syndrome decoding problem, have been used for constructing secure cryptographic schemes for a long time. Schemes based on these problems are also assumed to be secure against quantum computers. However, these schemes are often considered impractical for real-world deployment due to large key sizes and inefficient computation time. In the recent call for standardization of additional post-quantum digital signatures by the National Institute of Standards and Technology, several code-based candidates have been proposed, including LESS, CROSS, and MEDS. These schemes are designed on the relatively new zero-knowledge framework. Although several works analyze the hardness of these schemes, there is hardly any work that examines the security of these schemes in the presence of physical attacks.
In this work, we analyze these signature schemes from the perspective of fault attacks. All these schemes use a similar tree-based construction to compress the signature size. We attack this component of these schemes. Therefore, our attack is applicable to all of these schemes. In this work, we first analyze the LESS signature scheme and devise our attack. Furthermore, we showed how this attack can be extended to the CROSS signature scheme. Our attacks are built on very simple fault assumptions. Our results show that we can recover the entire secret key of LESS and CROSS using as little as a single fault. Finally, we propose various countermeasures to prevent these kinds of attacks and discuss their efficiency and shortcomings.



## 2024/1423

* Title: Towards package opening detection at power-up by monitoring thermal dissipation
* Authors: Julien Toulemont, Geoffrey Chancel, Fréderick Mailly, Philippe Maurine, Pascal Nouet
* [Permalink](https://eprint.iacr.org/2024/1423)
* [Download](https://eprint.iacr.org/2024/1423.pdf)

### Abstract

Among the various threats to secure ICs, many are semi-invasive in the sense that their application requires the removal of the package to gain access to either the front or back of the target IC. Despite this stringent application requirements, little attention is paid to embedded techniques aiming at checking the package's integrity. This paper explores the feasibility of verifying the package integrity of microcontrollers by examining their thermal dissipation capability.



## 2024/1424

* Title: A Waterlog for Detecting and Tracing Synthetic Text from Large Language Models
* Authors: Brennon Brimhall, Orion Weller, Matthew Green, Ian Miers
* [Permalink](https://eprint.iacr.org/2024/1424)
* [Download](https://eprint.iacr.org/2024/1424.pdf)

### Abstract

We propose waterlogs, a new direction to detect and trace synthetic text outputs from large language models based on transparency logs. Waterlogs offer major categorical advantages over watermarking: it (1) allows for the inclusion of arbitrary metadata to facilitate tracing, (2) is publicly verifiable by third parties, and (3) operates in a distributed manner while remaining robust and efficient.

Waterlogs rely on a verifiable Hamming distance index, a novel data structure that we describe, to efficiently search multi-dimensional semantic hashes of natural language embeddings in a verifiable manner. This data structure may be of independent interest.

We implement a waterlog, which we call DREDGE, and benchmark it using synthetic text generated by GPT-2 1.5B and OPT-13B; embeddings are generated via OpenAI's text-embedding-ada-002 model. We provide empirical benchmarks on the efficiency of appending text to the log and querying it for matches. We compare our results to watermarking and outline areas for further research.



## 2024/1425

* Title: New constructions of pseudorandom codes
* Authors: Surendra Ghentiyala, Venkatesan Guruswami
* [Permalink](https://eprint.iacr.org/2024/1425)
* [Download](https://eprint.iacr.org/2024/1425.pdf)

### Abstract

Introduced in [CG24], pseudorandom error-correcting codes (PRCs) are a new
cryptographic primitive with applications in watermarking generative AI models.
These are codes where a collection of polynomially many codewords is
computationally indistinguishable from random, except to individuals with the
decoding key. In this work, we examine the assumptions under which PRCs with
robustness to a constant error rate exist.
  1. We show that if both the planted hyperloop assumption introduced in
[BKR23] and security of a version of Goldreich's PRG hold, then there exist
public-key PRCs for which no efficient adversary can distinguish a polynomial
number of codewords from random with better than $o(1)$ advantage.
  2. We revisit the construction of [CG24] and show that it can be based on a
wider range of assumptions than presented in [CG24]. To do this, we introduce a
weakened version of the planted XOR assumption which we call the weak planted
XOR assumption and which may be of independent interest.
  3. We initiate the study of PRCs which are secure against space-bounded
adversaries. We show how to construct secret-key PRCs of length $O(n)$ which
are $\textit{unconditionally}$ indistinguishable from random by
$\text{poly}(n)$ time, $O(n^{1.5-\varepsilon})$ space adversaries.



## 2024/1426

* Title: Agile Asymmetric Cryptography and the Case for Finite Fields
* Authors: Anna M. Johnston
* [Permalink](https://eprint.iacr.org/2024/1426)
* [Download](https://eprint.iacr.org/2024/1426.pdf)

### Abstract

Cryptographic agility, the ability to easily and quickly modify cryptography in a sys- tem, is one of the most important features of any cryptographic system. Any algorithm may be attacked and, at some point in time, be broken. The most obvious solution is to change the cryptographic algorithm, however this has high risk and cost. Another solution is to use agile algorithms. Agile algorithms have security parameters easily changed to increase protection against attacks.
In this paper we will show that finite field based algorithms are the most agile of currently used classical cryptography. A critical portion of this will be to show that the bottleneck for the primary costing attack, the number field sieve, is the linear algebra portion of the attack, and not the sieving portion.
This paper examines the agility of all three algorithm categories and dispels a few myths about their strengths.



## 2024/1427

* Title: LogRobin++: Optimizing Proofs of Disjunctive Statements in VOLE-Based ZK
* Authors: Carmit Hazay, David Heath, Vladimir Kolesnikov, Muthuramakrishnan Venkitasubramaniam, Yibin Yang
* [Permalink](https://eprint.iacr.org/2024/1427)
* [Download](https://eprint.iacr.org/2024/1427.pdf)

### Abstract

In the Zero-Knowledge Proof (ZKP) of a disjunctive statement, $\mathcal{P}$ and $\mathcal{V}$ agree on $B$ fan-in $2$ circuits $\mathcal{C}_0, \ldots, \mathcal{C}_{B-1}$ over a field $\mathbb{F}$;  each circuit has $n_{\mathit{in}}$ inputs, $n_\times$ multiplications, and one output. $\mathcal{P}$'s goal is to demonstrate the knowledge of a witness $(\mathit{id} \in [B]$, $\boldsymbol{w} \in \mathbb{F}^{n_{\mathit{in}}})$, s.t. $\mathcal{C}_{\mathit{id}}(\boldsymbol{w}) = 0$ where neither $\boldsymbol{w}$ nor $\mathit{id}$ is revealed. Disjunctive statements are effective, for example, in implementing ZKP based on sequential execution of CPU steps.

This paper studies ZKP (of knowledge) protocols over disjunctive statements based on Vector OLE. Denoting by $\lambda$ the statistical security parameter and let $\rho \overset{\Delta}{=} \max\{\log |\mathbb{F}|, \lambda\}$, the previous state-of-the-art protocol $\mathsf{Robin}$ (Yang et al. CCS'23) required $(n_{\mathit{in}}+3n_\times)\log \left|\mathbb{F}\right| + \mathcal{O}(\rho B)$ bits of communication with $ \mathcal{O}(1)$ rounds, and $\mathsf{Mac'n'Cheese}$ (Baum et al. CRYPTO'21) required $(n_{\mathit{in}}+n_\times)\log \left|\mathbb{F}\right| + 2n_\times\rho + \mathcal{O}(\rho \log B)$ bits of communication with $\mathcal{O}(\log B)$ rounds, both in the VOLE-hybrid model.

Our novel protocol $\mathsf{LogRobin}\texttt{++}$ achieves the same functionality at the cost of $(n_{\mathit{in}}+n_\times)\log \left|\mathbb{F}\right| + \mathcal{O}(\rho \log B)$ bits of communication with $\mathcal{O}(1)$ rounds in the VOLE-hybrid model. Crucially, $\mathsf{LogRobin}\texttt{++}$ takes advantage of two new techniques -- (1) an $\mathcal{O}(\log B)$-overhead approach to prove in ZK that an IT-MAC commitment vector contains a zero; and (2) the realization of VOLE-based ZK over a disjunctive statement, where $\mathcal{P}$ commits only to $\boldsymbol{w}$ and multiplication outputs of $\mathcal{C}_{\mathit{id}}(\boldsymbol{w})$ (as opposed to prior work where $\mathcal{P}$ commits to $\boldsymbol{w}$ and all three wires that are associated with each multiplication gate).

We implemented $\mathsf{LogRobin}\texttt{++}$ over Boolean (i.e., $\mathbb{F}_2$) and arithmetic (i.e., $\mathbb{F}_{2^{61}-1}$) fields. In our experiments, including the cost of generating VOLE correlations, $\mathsf{LogRobin}\texttt{++}$ achieved up to $170 \times$ optimization over $\mathsf{Robin}$ in communication, resulting in up to $7\times$ (resp. $3\times$) wall-clock time improvements in a WAN-like (resp. LAN-like) setting.



## 2024/1428

* Title: Mario: Multi-round Multiple-Aggregator Secure Aggregation with Robustness against Malicious Actors
* Authors: Truong Son Nguyen, Tancrède Lepoint, Ni Trieu
* [Permalink](https://eprint.iacr.org/2024/1428)
* [Download](https://eprint.iacr.org/2024/1428.pdf)

### Abstract

Federated Learning (FL) enables multiple clients to collaboratively train a machine learning model while keeping their data private, eliminating the need for data sharing. Two common approaches to secure aggregation (SA) in FL are the single-aggregator and multiple-aggregator models.
   
    Existing multiple-aggregator protocols such as Prio (NSDI 2017), Prio+ (SCN 2022), Elsa (S\&P 2023) either offer robustness only in the presence of semi-honest servers or provide security without robustness and are limited to two aggregators.
    We introduce Mario, the first multi-aggregator SA protocol that is both secure in a malicious setting and provides robustness. Similar to prior work of Prio and Prio+, Mario provides secure aggregation in a setup of $n$ servers and $m$ clients. Unlike previous work, Mario removes the assumption of semi-honest servers, and provides a complete protocol with robustness against less than $n/2$ malicious servers,  defense with input validation of upto $m-2$ corrupted clients, and dropout of any number of clients. Our implementation shows that Mario is $3.40\times$ and $283.4\times$ faster than Elsa and Prio+, respecitively.



## 2024/1429

* Title: Powerformer: Efficient Privacy-Preserving Transformer with Batch Rectifier-Power Max Function and Optimized Homomorphic Attention
* Authors: Dongjin Park, Eunsang Lee, Joon-Woo Lee
* [Permalink](https://eprint.iacr.org/2024/1429)
* [Download](https://eprint.iacr.org/2024/1429.pdf)

### Abstract

We propose an efficient non-interactive privacy-preserving Transformer inference architecture called Powerformer. Since softmax is a non-algebraic operation, previous studies have attempted to modify it to be HE-friendly, but these methods have encountered issues with accuracy degradation or prolonged execution times due to the use of multiple bootstrappings. We propose replacing softmax with a new ReLU-based function called the \textit{Batch Rectifier-Power max} (BRPmax) function without any unstable approximation methods, which outperforms even original BERT performance within BERT-Large model while requiring fewer levels, allowing it to operate with only a single bootstrapping. We also present a matrix multiplication algorithms specialized for attention block that reduce the number of key-switchings by 35% to 91% compared to existing state-of-the-art methods. We design clear end-to-end HE-based implementation for private Transformer model, and our implementation of Powerformer on the BERT-tiny model using RNS-CKKS takes 503 seconds on a single-threaded CPU, and to the best of our knowledge, this is the first end-to-end non-interactive Transformer implementation using HE.



## 2024/1430

* Title: MYao: Multiparty ``Yao'' Garbled Circuits with Row Reduction, Half Gates, and Efficient Online Computation
* Authors: Aner Ben-Efraim, Lior Breitman, Jonathan Bronshtein, Olga Nissenbaum, Eran Omri
* [Permalink](https://eprint.iacr.org/2024/1430)
* [Download](https://eprint.iacr.org/2024/1430.pdf)

### Abstract

Garbled circuits are a powerful and important cryptographic primitive, introduced by Yao [FOCS 1986] for secure two-party computation. Beaver, Micali and Rogaway (BMR) [STOCS 1990] extended the garbled circuit technique to construct the first constant-round secure multiparty computation (MPC) protocol. In the BMR protocol, the garbled circuit size grows linearly and the online computation time grows quadratically with the number of parties. Previous solutions to avoid this relied on key-homomorphic PRFs, incurring a large garbled circuit size and slow online computation time.
We present MYao, a new multiparty protocol for achieving a ``Yao'' garbled circuit, i.e., the garbled circuit size and online computation time are independent of the number of parties. The key innovation is that the parties collaboratively compute the PRF in MPC, which was previously believed to be inefficient. In this paper, we challenge this long-standing assumption by basing the garbled circuit construction on ``MPC-friendly'' PRFs. One of the highlights of our new technique is that we are able to achieve, for the first time, full row-reduction in multiparty garbled circuits. To achieve this optimization without increasing the number of rounds, we utilize free-XOR and half gates, presenting a new technique for choosing the keys, based on a naturally occurring relation between the 2 keys of the 2 half-gates.
MYao reduces the garbled circuit size by more than 90%, the total communication by more than 75%, and the online computation time  by more than 10%, compared to all known solutions based on key-homomorphic PRFs, thus substantially improving the overall efficiency in both the offline and the online phases. Furthermore, MYao significantly improves over semi-honest BMR in online phase efficiency when the number of parties exceeds 80.



## 2024/1431

* Title: Interactive Line-Point Zero-Knowledge with Sublinear Communication and Linear Computation
* Authors: Fuchun Lin, Chaoping Xing, Yizhou Yao
* [Permalink](https://eprint.iacr.org/2024/1431)
* [Download](https://eprint.iacr.org/2024/1431.pdf)

### Abstract

Studies of vector oblivious linear evaluation (VOLE)-based zero-knowledge (ZK) protocols flourish in recent years. Such ZK protocols feature optimal prover computation and a flexibility for handling arithmetic circuits over arbitrary fields. However, most of them have linear communication, which constitutes a bottleneck for handling large statements in a slow network. The pioneer work AntMan (CCS'22), achieved sublinear communication for the first time within VOLE-based ZK, but lost the advantage of fast proving. In this work, we propose two new VOLE-based ZK constructions that achieve sublinear communication and linear computation, simultaneously. Let $\mathcal{C}$ be a circuit with size $S$, input size $n$, and depth $d$. In particular, our first ZK, specialized for layered circuits, has communication $O(n+d\log{S})$, while our second ZK can be used to prove  general circuits and has communication $O(n+d\log{S}+d^2)$.

Our results are obtained by introducing the powerful sum-check techniques from the mature line of works on interactive proofs into the context of VOLE-based ZK for the first time. Reminiscent of the non-interactive line-point zero-knowledge proof system (ITC'21), we introduce an interactive line-point zero-knowledge (ILPZK) proof system, which closely connects with VOLE-based ZK protocols. In addition, our works also enrich the studies of ZK based on interactive proofs, with new interesting features (e.g., having information-theoretic UC-security, naturally supporting any field) achieved.



## 2024/1432

* Title: On Multi-user Security of Lattice-based Signature under Adaptive Corruptions and Key Leakages
* Authors: Masayuki Fukumitsu, Shingo Hasegawa
* [Permalink](https://eprint.iacr.org/2024/1432)
* [Download](https://eprint.iacr.org/2024/1432.pdf)

### Abstract

We consider the multi-user security under the adaptive corruptions and key leakages ($\rm{MU^{c\&l}}$ security) for lattice-based signatures. Although there exists an $\rm{MU^{c\&l}}$ secure signature based on a number-theoretic assumption, or a leakage-resilient lattice-based signature in the single-user setting, $\rm{MU^{c\&l}}$ secure lattice-based signature is not known.

We examine the existing lattice-based signature schemes from the viewpoint of $\rm{MU^{c\&l}}$ security, and find that the security of the Lyubashevsky's signature, which is proven to have the ordinary single-user security only, can be extended to the multi-user security even if we take the adaptive corruptions and the key leakages into account.

Our security proof in the multi-user setting makes use of the feature of the SIS problem so that a SIS instance is set to the public parameter and a reduction algorithm can set a public key with a secret key in order to answer a corruption query. We also show that the entropy of the secret key is kept under the bounded leakage with a high probability and then the leakage resilience of signature holds.



## 2024/1433

* Title: $Shortcut$: Making MPC-based Collaborative Analytics Efficient on Dynamic Databases
* Authors: Peizhao Zhou, Xiaojie Guo, Pinzhi Chen, Tong Li, Siyi Lv, Zheli Liu
* [Permalink](https://eprint.iacr.org/2024/1433)
* [Download](https://eprint.iacr.org/2024/1433.pdf)

### Abstract

Secure Multi-party Computation (MPC) provides a promising solution for privacy-preserving multi-source data analytics. However, existing MPC-based collaborative analytics systems (MCASs) have unsatisfying performance for scenarios with dynamic databases. Naively running an MCAS on a dynamic database would lead to significant redundant costs and raise performance concerns, due to the substantial duplicate contents between the pre-updating and post-updating databases.

In this paper, we propose $Shortcut$, a framework that can work with MCASs to enable efficient queries on dynamic databases that support data insertion, deletion, and update. The core idea of $Shortcut$ is to materialize previous query results and directly update them via our query result update (QRU) protocol to obtain current query results. We customize several efficient QRU protocols for common SQL operators, including Order-by-Limit, Group-by-Aggregate, Distinct, Join, Select, and Global Aggregate. These protocols are composable to implement a wide range of query functions. In particular, we propose two constant-round protocols to support data insertion and deletion. These protocols can serve as important building blocks of other protocols and are of independent interest. They address the problem of securely inserting/deleting a row into/from an ordered table while keeping the order. Our experiments show that $Shortcut$ outperforms naive MCASs for minor updates arriving in time, which captures the need of many realistic applications (e.g., insurance services, account data management). For example, for a single query after an insertion, $Shortcut$ achieves up to $186.8 \times$ improvement over those naive MCASs without our QRU protocols on a dynamic database with $2^{16} \sim 2^{20}$ rows, which is common in real-life applications.



## 2024/1434

* Title: Untangling the Security of Kilian's Protocol: Upper and Lower Bounds
* Authors: Alessandro Chiesa, Marcel Dall'Agnol, Ziyi Guan, Nicholas Spooner, Eylon Yogev
* [Permalink](https://eprint.iacr.org/2024/1434)
* [Download](https://eprint.iacr.org/2024/1434.pdf)

### Abstract

Sigma protocols are elegant cryptographic proofs that have become a cornerstone of modern cryptography. A notable example is Schnorr's protocol, a zero-knowledge proof-of-knowledge of a discrete logarithm. Despite extensive research, the security of Schnorr's protocol in the standard model is not fully understood.

In this paper we study Kilian's protocol, an influential public-coin interactive protocol that, while not a sigma protocol, shares striking similarities with sigma protocols. The first example of a succinct argument, Kilian's protocol is proved secure via rewinding, the same idea used to prove sigma protocols secure. In this paper we show how, similar to Schnorr's protocol, a precise understanding of the security of Kilian's protocol remains elusive. We contribute new insights via upper bounds and lower bounds.
 - Upper bounds. We establish the tightest known bounds on the security of Kilian's protocol in the standard model, via strict-time reductions and via expected-time reductions. Prior analyses are strict-time reductions that incur large overheads or assume restrictive properties of the PCP underlying Kilian's protocol.
 - Lower bounds. We prove that significantly improving on the bounds that we establish for Kilian's protocol would imply improving the security analysis of Schnorr's protocol beyond the current state-of-the-art (an open problem). This partly explains the difficulties in obtaining tight bounds for Kilian's protocol.



## 2024/1435

* Title: Actively Secure Polynomial Evaluation from Shared Polynomial Encodings
* Authors: Pascal Reisert, Marc Rivinius, Toomas Krips, Sebastian Hasler, Ralf Küsters
* [Permalink](https://eprint.iacr.org/2024/1435)
* [Download](https://eprint.iacr.org/2024/1435.pdf)

### Abstract

Many of the currently best actively secure Multi-Party Computation (MPC) protocols like SPDZ (Damgård et al., CRYPTO 2012) and improvements thereof use correlated randomness to speed up the time-critical online phase. Although many of these protocols still rely on classical Beaver triples, recent results show that more complex correlations like matrix or convolution triples lead to more efficient evaluations of the corresponding operations, i.e. matrix multiplications or tensor convolutions. In this paper, we address the evaluation of multivariate polynomials with a new form of randomness: polytuples. We use the polytuples to construct a new family of randomized encodings which then allow us to evaluate the given multivariate polynomial. Our approach can be fine-tuned in various ways to the constraints of applications at hand, in terms of round complexity, bandwidth, and tuple size. We show that for many real-world setups, a polytuples-based online phase outperforms state-of-the-art protocols based on Beaver triples.



## 2024/1436

* Title: Eva: Efficient IVC-Based Authentication of Lossy-Encoded Videos
* Authors: Chengru Zhang, Xiao Yang, David Oswald, Mark Ryan, Philipp Jovanovic
* [Permalink](https://eprint.iacr.org/2024/1436)
* [Download](https://eprint.iacr.org/2024/1436.pdf)

### Abstract

With the increasing spread of fake videos for misinformation, proving the provenance of an edited video (without revealing the original one) becomes critical. To this end, we introduce Eva, the first cryptographic protocol for authenticating lossy-encoded videos. Compared to previous cryptographic methods for image authentication, Eva supports significantly larger amounts of data that undergo complex transformations during encoding. We achieve this by decomposing repetitive and manageable components from video codecs, which can then be handled using Incrementally Verifiable Computation (IVC). By providing a formal definition and security model for proofs of video authenticity, we demonstrate the security of Eva under well-established cryptographic assumptions.

To make Eva efficient, we construct an IVC based on folding schemes that incorporate lookup arguments, resulting in a linear-time prover whose proofs can be compressed to a constant size. We further improve the performance of Eva through various optimizations, including tailored circuit design and GPU acceleration. The evaluation of our implementation shows that Eva is practical: for a $1$-minute HD ($1280 \times 720$) video encoded in H.264 at $30$ frames per second, Eva generates a proof in about $2.5$ hours on consumer-grade hardware at a speed of $5.5$ μs per pixel, surpassing previous cryptographic image authentication schemes that support arbitrary editing operations by more than an order of magnitude.



## 2024/1437

* Title: HierNet: A Hierarchical Deep Learning Model for SCA on Long Traces
* Authors: Suvadeep Hajra, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2024/1437)
* [Download](https://eprint.iacr.org/2024/1437.pdf)

### Abstract

Side-channel analysis (SCA) compromises the security of cryptographic devices by exploiting various side-channel leakages such as power consumption, electromagnetic (EM) emanations, or timing variations, posing a practical threat to the security and privacy of modern digital systems. In power or EM SCA, statistical or machine learning methods are employed to extract secret information from power/EM traces. In many practical scenarios, raw power/EM traces can span hundreds of thousands of features, with relevant leakages occurring over only a few small segments. Consequently, existing SCAs often select a small number of features before launching the attack, making their success highly dependent on the feasibility of feature selection. However, feature selection may not always be possible, such as in the presence of countermeasures like masking or  jitters.

Several recent works have employed deep learning (DL) methods to conduct SCA on long raw traces, thereby reducing dependence on feature selection steps. However, these methods often perform poorly against various jitter-based countermeasures. While some of these methods have shown high robustness to jitter-based countermeasures on relatively shorter traces, we demonstrate in this work that their performance deteriorates as trace lengths increase. Based on these observations, we develop a hierarchical DL model for SCA on long traces that is robust against various countermeasures. The proposed model, HierNet, extracts information from long traces using a two-level information assimilation process. At the base level, a DL model with shift-invariance is employed to extract information from smaller trace segments. Subsequently, a top-level DL model integrates the outputs of the base model to generate the final output. The proposed model has been experimentally evaluated against various combinations of masking, random delay, and clock jitter countermeasures using traces with lengths exceeding $200K$ features. The results have been compared with three existing SCA benchmark models. They demonstrate HierNet's superiority in several scenarios, such as on long traces, against clock jitter countermeasures, and low training data scenarios. In particular, while other models fail to reach the guessing entropy $1$ using as many as $5K$ traces, HierNet achieves the same with fewer than or close to $10$ traces.