## In this issue

1. [2024/1574] Scalable Two-Round $n$-out-of-$n$ and Multi- ...
2. [2024/2087] Post-Quantum Privacy for Traceable Receipt-Free ...
3. [2024/2088] An Embedded Domain-Specific Language for Using One- ...
4. [2024/2089] Computing the Hermite Normal Form: A Survey
5. [2024/2090] Breaking the Shadow: Key Recovery Attack on Full- ...
6. [2024/2091] Encrypted Multi-map that Hides Query, Access, and ...
7. [2024/2092] PQConnect: Automated Post-Quantum End-to-End Tunnels
8. [2024/2093] Exploring Large Integer Multiplication for ...
9. [2024/2094] Secure Vault scheme in the Cloud Operating Model
10. [2024/2095] A Note on the Minimality of One-Way Functions in ...
11. [2024/2096] Efficient Multi-party Private Set Union Resistant ...
12. [2024/2097] NMFT: A Copyrighted Data Trading Protocol based on ...
13. [2024/2098] Asymptotically Optimal Adaptive Asynchronous Common ...
14. [2024/2099] MicroNova: Folding-based arguments with efficient ...
15. [2024/2100] Compact Key Storage in the Standard Model
16. [2025/1] Attribute Based Encryption for Turing Machines from ...
17. [2025/2] Voting with coercion resistance and everlasting ...
18. [2025/3] Post-Quantum DNSSEC with Faster TCP Fallbacks
19. [2025/4] Smaug: Modular Augmentation of LLVM for MPC
20. [2025/5] What is "legal" and "illegal?": Social Norms, ...
21. [2025/6] Nearly Quadratic Asynchronous Distributed Key ...
22. [2025/7] Non Linearizable Entropic Operator
23. [2025/8] A Survey to Zero-Knowledge Interactive Verifiable ...
24. [2025/9] Efficient CPA Attack on Hardware Implementation of ...
25. [2025/10] A Combinatorial Approach to IoT Data Security
26. [2025/11] DL-SCADS: Deep Learning-Based Post-Silicon Side- ...
27. [2025/12] Leuvenshtein: Efficient FHE-based Edit Distance ...
28. [2025/13] Wave Hello to Privacy: Efficient Mixed-Mode MPC ...
29. [2025/14] SPY-PMU: Side-Channel Profiling of Your Performance ...
30. [2025/15] A New Method for Solving Discrete Logarithm Based ...
31. [2025/16] Dynamically Available Common Subset
32. [2025/17] New Quantum Cryptanalysis of Binary Elliptic Curves ...
33. [2025/18] On the Independence Assumption in Quasi-Cyclic ...

## 2024/1574

* Title: Scalable Two-Round $n$-out-of-$n$ and Multi-Signatures from Lattices in the Quantum Random Oracle Model
* Authors: Qiqi Lai, Feng-Hao Liu, Yang Lu, Haiyang Xue, Yong Yu
* [Permalink](https://eprint.iacr.org/2024/1574)
* [Download](https://eprint.iacr.org/2024/1574.pdf)

### Abstract

In this paper, we construct the first asymptotically efficient two-round $n$-out-of-$n$ and multi-signature schemes from lattices in the quantum random oracle model (QROM), using the Fiat-Shamir with Aborts (FSwA) paradigm. Our protocols can be viewed as the QROM~variants of the two-round protocols by Damgård et al. (JoC 2022). A notable feature of our protocol, compared to other counterparts in the classical random oracle model, is that each party performs an independent abort and still outputs a signature in exactly two rounds, making our schemes significantly more scalable.

From a technical perspective, the simulation of QROM~and the efficient reduction from breaking underlying assumption to forging signatures are the essential challenges to achieving efficient QROM security for the previously related works.
In order to conquer the former one we adopt the quantum-accessible pseudorandom function (QPRF) to simulate QROM. Particularly, we show
that there exist a QPRF~which can be programmed and inverted, even against a quantum adversary.
For the latter challenge, we tweak and apply the online extractability by Unruh (Eurocrypt 2015).

## 2024/2087

* Title: Post-Quantum Privacy for Traceable Receipt-Free Encryption
* Authors: Paola de Perthuis, Thomas Peters
* [Permalink](https://eprint.iacr.org/2024/2087)
* [Download](https://eprint.iacr.org/2024/2087.pdf)

### Abstract

Traceable Receipt-free Encryption (TREnc) has recently been introduced as a verifiable public-key encryption primitive endowed with a unique security model. In a nutshell, TREnc allows randomizing ciphertexts in transit in order to remove any subliminal information up to a public trace that ensures the non-malleability of the underlying plaintext. A remarkable property of TREnc is the indistinguishability of the randomization of chosen ciphertexts against traceable chosen-ciphertext attacks (TCCA). The main application lies in voting systems by allowing voters to encrypt their votes, tracing whether a published ballot takes their choices into account, and preventing them from proving how they
voted. While being a very promising primitive, the few existing TREnc mechanisms solely rely on discrete-logarithm related assumptions making them vulnerable to the well-known record-now/decrypt-later attack in the wait of quantum computers.
We address this limitation by building the first TREnc whose privacy withstands the advent of quantum adversaries in the future. To design our construction, we first generalize the original TREnc primitive that is too restrictive to be easily compatible with built-in lattice-based semantically-secure encryption. Our more flexible model keeps all the ingredients generically implying receipt-free voting. Our instantiation relies on Ring Learning With Errors (RLWE) with pairing-based statistical zero-knowledge simulation sound proofs from Groth-Sahai, and further enjoys a public-coin common reference string removing the need of a trusted setup.

## 2024/2088

* Title: An Embedded Domain-Specific Language for Using One-Hot Vectors and Binary Matrices in Secure Computation Protocols
* Authors: Andrei Lapets
* [Permalink](https://eprint.iacr.org/2024/2088)
* [Download](https://eprint.iacr.org/2024/2088.pdf)

### Abstract

The use of secure computation protocols within production software systems and applications is complicated by the fact that such protocols sometimes rely upon -- or are most compatible with -- unusual or restricted models of computation. We employ the features of a contemporary and widely used programming language to create an embedded domain-specific language for working with user-defined functions as binary matrices that operate on one-hot vectors. At least when working with small finite domains, this allows programmers to overcome the restrictions of more simple secure computation protocols that support only linear operations (such as addition and scalar multiplication) on private inputs. Notably, programmers are able to define their own input and output domains, to use all available host language features and libraries to define functions that operate on these domains, and to translate inputs, outputs, and functions between their usual host language representations and their one-hot vector or binary matrix forms. Furthermore, these features compose in a straightforward way with simple secure computation libraries available for the host language.

## 2024/2089

* Title: Computing the Hermite Normal Form: A Survey
* Authors: Leon Damer
* [Permalink](https://eprint.iacr.org/2024/2089)
* [Download](https://eprint.iacr.org/2024/2089.pdf)

### Abstract

The Hermite Normal Form (HNF) of a matrix is an analogue of the echolon form over the integers. Any integer matrix can be transformed into its unique HNF.
A common obstacle in computing the HNF is the extensive blow up of intermediate values. As first approach to this problem, we discuss the $Modulo Determinant Algorithm$. It keeps the entries bounded by $d$, the determinant of the lattice, and has a time complexity of $\mathcal{O}(n^3\log^2 d)$, where $n$ is the dimension of the matrix. Although this algorithm is very useful if the determinant is small, in the general case, the entries still become extremely large.
Secondly, we study the $Linear Space Algorithm$. It has a time complexity of $\mathcal{O}(n^5\mathrm{polylog}(M, n))$, where $M$ denotes the largest absolute value of the input matrix. This is as fast as the best previously known algorithms, but in contrast, it assures space complexity linear in the input size, i.e. $\mathcal{O}(n^2\log M)$.
As last algorithm to compute the HNF we analyze the $Heuristic Algorithm$, which is based on the first two algorithms. It achieves a much faster runtime in practice, yielding a heuristic runtime of $\mathcal{O}(n^4\mathrm{polylog}(M, n))$, while keeping the linear space complexity.
Besides some performance speed ups, the $Linear Space Algorithm$ and $Heuristic Algorithm$ are precisely the algorithms implemented by SageMath.

## 2024/2090

* Title: Breaking the Shadow: Key Recovery Attack on Full-Round Shadow Block Ciphers with Minimal Data
* Authors: Anda Che, Shahram Rasoolzadeh
* [Permalink](https://eprint.iacr.org/2024/2090)
* [Download](https://eprint.iacr.org/2024/2090.pdf)

### Abstract

Shadow is a family of lightweight block ciphers introduced by Guo, Li, and Liu in 2021, with Shadow-32 having a 32-bit block size and a 64-bit key, and Shadow-64 having a 64-bit block size and a 128-bit key. Both variants use a generalized Feistel network with four branches, incorporating the AND-Rotation-XOR operation similar to the Simon family for their bridging function. This paper reveals that the security claims of the Shadow family are not as strong as suggested. We present a key recovery attack that can retrieve the sequence of round keys used for encryption with only two known plaintext/ciphertext pairs, requiring time and memory complexity of $2^{43.23}$ encryptions and $2^{21.62}$ blocks of memory for Shadow-32, and complexity of $2^{81.32}$ encryptions and $2^{40.66}$ blocks of memory for Shadow-64. Notably, this attack is independent of the number of rounds and the bridging function employed. Furthermore, we critically evaluate one of the recent cryptanalysis on Shadow ciphers and identify significant flaws in the proposed key recovery attacks. In particular, we demonstrate that the distinguisher used in impossible differential attacks by Liu et al. is ineffective for key recovery, despite their higher claimed complexities compared to ours.