## In this issue

1. [2024/493] Reckle Trees: Updatable Merkle Batch Proofs with ...
2. [2024/494] HW-token-based Common Random String Setup
3. [2024/495] Reducing Signature Size of Matrix-code-based ...
4. [2024/496] Two-Round Threshold Signature from Algebraic One- ...
5. [2024/497] On the Security of Data Markets and Private ...
6. [2024/498] Number-Theoretic Transform Architecture for Fully ...
7. [2024/499] CCA Secure Updatable Encryption from Non-Mappable ...
8. [2024/500] Side Channel Resistant Sphincs+
9. [2024/501] Anonymous Revocable Identity-Based Encryption ...
10. [2024/502] Best of Two Worlds: Efficient, Usable and Auditable ...
11. [2024/503] Two Levels are Better than One: Dishonest Majority ...
12. [2024/504] Polylogarithmic Proofs for Multilinears over Binary ...
13. [2024/505] RSA-Based Dynamic Accumulator without Hashing into ...
14. [2024/506] A Decentralized Federated Learning using Reputation
15. [2024/507] An Efficient SNARK for Field-Programmable and RAM ...
16. [2024/508] Secure Multi-Party Linear Algebra with Perfect ...
17. [2024/509] Distribution of cycles in supersingular ...
18. [2024/510] DoS-resistant Oblivious Message Retrieval from ...
19. [2024/511] A Black-box Attack on Fixed-Unitary Quantum ...
20. [2024/512] Single Trace is All It Takes: Efficient Side- ...
21. [2024/513] Quantum Implementation and Analysis of SHA-2 and SHA-3
22. [2024/514] Zero-Knowledge Proof Vulnerability Analysis and ...
23. [2024/515] Inject Less, Recover More: Unlocking the Potential ...
24. [2024/516] Similar Data is Powerful: Enhancing Inference ...
25. [2024/517] Fast pairings via biextensions and cubical arithmetic
26. [2024/518] Software-Defined Cryptography: A Design Feature of ...
27. [2024/519] On implementation of Stickel's key exchange ...
28. [2024/520] A note on securing insertion-only Cuckoo filters
29. [2024/521] LIT-SiGamal: An efficient isogeny-based PKE based ...
30. [2024/522] Cryptanalysis of Secure and Lightweight Conditional ...
31. [2024/523] Unbindable Kemmy Schmidt: ML-KEM is neither MAL- ...
32. [2024/524] A Time-Space Tradeoff for the Sumcheck Prover
33. [2024/525] Privacy Preserving Biometric Authentication for ...
34. [2024/526] Optimizing and Implementing Fischlin's Transform ...
35. [2024/528] The solving degrees for computing Gröbner bases of ...
36. [2024/529] Fully Homomorphic Training and Inference on Binary ...
37. [2024/530] An efficient key generation algorithm for GR-NTRU ...
38. [2024/531] Avoiding Trusted Setup in Isogeny-based Commitments
39. [2024/532] Analysing Cryptography in the Wild - A Retrospective
40. [2024/533] HyCaMi: High-Level Synthesis for Cache Side-Channel ...
41. [2024/534] CryptoVampire: Automated Reasoning for the Complete ...
42. [2024/535] NodeGuard: A Highly Efficient Two-Party Computation ...
43. [2024/536] Highly-Effective Backdoors for Hash Functions and ...

## 2024/493

* Title: Reckle Trees: Updatable Merkle Batch Proofs with Applications
* Authors: Charalampos Papamanthou, Shravan Srinivasan, Nicolas Gailly, Ismael Hishon-Rezaizadeh, Andrus Salumets, Stjepan Golemac
* [Permalink](https://eprint.iacr.org/2024/493)
* [Download](https://eprint.iacr.org/2024/493.pdf)

### Abstract

We propose Reckle trees, a new vector commitment based on succinct RECursive arguments and MerKLE trees. Reckle trees' distinguishing feature is their support for succinct batch proofs that are updatable - enabling new applications in the blockchain setting where a proof needs to be computed and efficiently maintained over a moving stream of blocks. Our technical approach is based on embedding the computation of the batch hash inside the recursive Merkle verification via a hash-based accumulator called canonical hashing. Due to this embedding, our batch proofs can be updated in logarithmic time, whenever a Merkle leaf (belonging to the batch or not) changes, by maintaining a data structure that stores previously-computed recursive proofs. Assuming enough parallelism, our batch proofs are also computable in $O(\log n)$ parallel time - independent of the size of the batch. As a natural extension of Reckle trees, we also introduce Reckle+ trees. Reckle+ trees provide updatable and succinct proofs for certain types of Map/Reduce computations. In this setting, a prover can commit to a memory $\mathsf{M}$ and produce a succinct proof for a Map/Reduce computation over a subset $I$ of $\mathsf{M}$. The proof can be efficiently updated whenever $I$ or $\mathsf{M}$ changes.

We present and experimentally evaluate two applications of Reckle+ trees, dynamic digest translation and updatable BLS aggregation. In dynamic digest translation we are maintaining a proof of equivalence between Merkle digests computed with different hash functions, e.g., one with a SNARK-friendly Poseidon and the other with a SNARK-unfriendly Keccak. In updatable BLS aggregation we maintain a proof for the correct aggregation of a $t$-aggregate BLS key, derived from a $t$-subset of a Merkle-committed set of individual BLS keys. Our evaluation using Plonky2 shows that Reckle trees and Reckle+ trees have small memory footprint, significantly outperform previous approaches in terms of updates and verification time, enable applications that were not possible before due to huge costs involved (Reckle trees are up to 200 times faster), and have similar aggregation performance with previous implementations of batch proofs.

## 2024/494

* Title: HW-token-based Common Random String Setup
* Authors: István Vajda
* [Permalink](https://eprint.iacr.org/2024/494)
* [Download](https://eprint.iacr.org/2024/494.pdf)

### Abstract

In the common random string model, the parties executing a protocol have access to a uniformly random bit string. It is known that under standard intractability assumptions, we can realize any ideal functionality with universally composable (UC) security if a trusted common random string (CrS) setup is available. It was always a question of where this CrS should come from since the parties provably could not compute it themselves. Trust assumptions are required, so minimizing the level of such trust is a fundamentally important task. Our goal is to design a CrS setup protocol under a weakened trust assumption.. We present an HW-token-based CrS setup for 2-party cryptographic protocols using a single token only. Our protocol is a UC-secure realization of ideal common random string functionality FCrS. We show the multiple-session security of the protocol and we also consider the multi-party extension of it.

## 2024/495

* Title: Reducing Signature Size of Matrix-code-based Signature Schemes
* Authors: Tung Chou, Ruben Niederhagen, Lars Ran, Simona Samardjiska
* [Permalink](https://eprint.iacr.org/2024/495)
* [Download](https://eprint.iacr.org/2024/495.pdf)

### Abstract

This paper shows novel techniques to reduce the signature size of the code-based signature schemes MEDS and ALTEQ, by a large factor. For both schemes, the signature size is dominated by the responses for rounds with nonzero challenges, and we reduce the signature size by reducing the size of these responses. For MEDS, each of the responses consists of $m^2 + n^2$ field elements,while in our new protocol each response consists of only $2k$ ($k$ is usually chosen to be close to $m$ and $n$) field elements. For ALTEQ, each of the responses consists of $n^2$ field elements, while in our new protocol each response consists of about $\sqrt{2} n^{3/2}$ field elements. In both underlying $\Sigma$-protocols of the schemes, the prover generates a random isometry and sends the corresponding isometry to the verifier as the response. Instead of doing this, in our new protocols, the prover derives an isometry from some random code words and their presumed (full or partial) images. The prover sends the corresponding code words and images to the verifier as the response, so that the verifier can derive an isometry in the same way. Interestingly, it turns out that each response takes much fewer field elements to represent in this way.

## 2024/496

* Title: Two-Round Threshold Signature from Algebraic One-More Learning with Errors
* Authors: Thomas Espitau, Shuichi Katsumata, Kaoru Takemure
* [Permalink](https://eprint.iacr.org/2024/496)
* [Download](https://eprint.iacr.org/2024/496.pdf)

### Abstract

Threshold signatures have recently seen a renewed interest due to applications in cryptocurrency while NIST has released a call for multi-party threshold schemes, with a deadline for submission expected for the first half of 2025. So far, all lattice-based threshold signatures requiring less than two-rounds are based on heavy tools such as (fully) homomorphic encryption (FHE) and homomorphic trapdoor commitments (HTDC). This is not unexpected considering that most efficient two-round signatures from classical assumptions either rely on idealized model such as algebraic group models or on one-more type assumptions, none of which we have a nice analogue in the lattice world.

In this work, we construct the first efficient two-round lattice-based threshold signature without relying on FHE or HTDC. It has an offline-online feature where the first round can be preprocessed without knowing message or the signer sets, effectively making the signing phase non-interactive. The signature size is small and shows great scalability. For example, even for a threshold as large as 1024 signers, we achieve a signature size roughly 11 KB. At the heart of our construction is a new lattice-based assumption called the algebraic one-more learning with errors (AOMMLWE) assumption. We believe this to be a strong inclusion to our lattice toolkits with an independent interest. We establish the selective security of AOMMLWE based on the standard MLWE and MSIS assumptions, and provide an in depth analysis of its adaptive security, which our threshold signature is based on.