## In this issue

1. [2024/215] Batch PIR and Labeled PSI with Oblivious Ciphertext ...
2. [2024/337] Solving the Tensor Isomorphism Problem for special ...
3. [2024/553] Efficient Linkable Ring Signatures: New Framework ...
4. [2024/653] Ipotane: Achieving the Best of All Worlds in ...
5. [2024/654] Monchi: Multi-scheme Optimization For Collaborative ...
6. [2024/655] Implementation and Performance Analysis of ...
7. [2024/656] Cryptanalytic Audit of the XHash Sponge Function ...
8. [2024/657] Cryptographic Accumulators: New Definitions, ...
9. [2024/658] Information-theoretic security with asymmetries
10. [2024/659] Secure Latent Dirichlet Allocation
11. [2024/660] FE[r]Chain: Enforcing Fairness in Blockchain Data ...
12. [2024/661] On amortization techniques for FRI-based SNARKs
13. [2024/662] Faster Private Decision Tree Evaluation for Batched ...
14. [2024/663] Xproofs: New Aggregatable and Maintainable Matrix ...
15. [2024/664] Pando: Extremely Scalable BFT Based on Committee ...
16. [2024/665] Homomorphic Evaluation of LWR-based PRFs and ...
17. [2024/666] Private Analytics via Streaming, Sketching, and ...
18. [2024/667] Agile, Post-quantum Secure Cryptography in Avionics
19. [2024/668] Blockchain Price vs. Quantity Controls
20. [2024/669] Mempool Privacy via Batched Threshold Encryption: ...
21. [2024/670] Secure Implementation of SRAM PUF for Private Key ...
22. [2024/671] Exploiting Internal Randomness for Privacy in ...
23. [2024/672] Secure Coded Distributed Computing
24. [2024/673] Chocobo: Creating Homomorphic Circuit Operating ...
25. [2024/674] SigmaSuite: How to Minimize Foreign Arithmetic in ...
26. [2024/675] Olympic Privacy-Preserving Blueprints: Faster ...
27. [2024/676] Composing Timed Cryptographic Protocols: ...

## 2024/215

* Title: Batch PIR and Labeled PSI with Oblivious Ciphertext Compression
* Authors: Alexander Bienstock, Sarvar Patel, Joon Young Seo, Kevin Yeo
* [Permalink](https://eprint.iacr.org/2024/215)
* [Download](https://eprint.iacr.org/2024/215.pdf)

### Abstract

In this paper, we study two problems: oblivious compression and decompression of ciphertexts. In oblivious compression, a server holds a set of ciphertexts with a subset of encryptions of zeroes whose positions are only known to the client. The goal is for the server to effectively compress the ciphertexts obliviously, while preserving the non-zero plaintexts and without learning the plaintext values. For oblivious decompression, the client, instead, succinctly encodes a sequence of plaintexts such that the server may decode encryptions of all plaintexts value, but the zeroes may be replaced with arbitrary values. We present solutions to both problems that construct lossless compressions only 5% more than the optimal minimum using only additive homomorphism. The crux of both algorithms involve embedding ciphertexts as random linear systems that are efficiently solvable.

Using our compression schemes, we obtain state-of-the-art schemes for batch private information retrieval (PIR) where a client wishes to privately retrieve multiple entries from a server-held database in one query. We show that our compression schemes may be used to reduce communication by up to 30% for batch PIR in both the single- and two-server settings.

Additionally, we study labeled private set intersection (PSI) in the unbalanced setting where one party's set is significantly smaller than the other party's set and each entry has associated data. By utilizing our novel compression algorithm, we present a protocol with 65-88% reduction in communication with comparable computation compared to prior works.

## 2024/337

* Title: Solving the Tensor Isomorphism Problem for special orbits with low rank points: Cryptanalysis and repair of an Asiacrypt 2023 commitment scheme
* Authors: Valerie Gilchrist, Laurane Marco, Christophe Petit, Gang Tang
* [Permalink](https://eprint.iacr.org/2024/337)
* [Download](https://eprint.iacr.org/2024/337.pdf)

### Abstract

The Tensor Isomorphism Problem (TIP) has been shown to be equivalent to the matrix code equivalence problem, making it an interesting candidate on which to build post-quantum cryptographic primitives. These hard problems have already been used in protocol development. One of these, MEDS, is currently in Round 1 of NIST's call for additional post-quantum digital signatures.
In this work, we consider the TIP for a special class of tensors. The hardness of the decisional version of this problem is the foundation of a commitment scheme proposed by D'Alconzo, Flamini, and Gangemi (Asiacrypt 2023). We present polynomial-time algorithms for the decisional and computational versions of TIP for special orbits, which implies that the commitment scheme is not secure. The key observations of these algorithms are that these special tensors contain some low-rank points, and their stabilizer groups are not trivial.
With these new developments in the security of TIP in mind, we give a new commitment scheme based on the general TIP that is non-interactive, post-quantum, and statistically binding, making no new assumptions. Such a commitment scheme does not currently exist in the literature.

## 2024/553

* Title: Efficient Linkable Ring Signatures: New Framework and Post-Quantum Instantiations
* Authors: Yuxi Xue, Xingye Lu, Man Ho Au, Chengru Zhang
* [Permalink](https://eprint.iacr.org/2024/553)
* [Download](https://eprint.iacr.org/2024/553.pdf)

### Abstract

In this paper, we introduce a new framework for constructing linkable ring signatures (LRS). Our framework is based purely on signatures of knowledge (SoK) which allows one to issue signatures on behalf of any NP-statement using the corresponding witness. Our framework enjoys the following advantages: (1) the security of the resulting LRS depends only on the security of the underlying SoK; (2) the resulting LRS naturally supports online/offline signing (resp.. verification), where the output of the offline signing (resp. verification) can be re-used across signatures of the same ring. For a ring size $n$, our framework requires an SoK of the NP statement with size $\log n$.

To instantiate our framework, we adapt the well-known post-quantum secure non-interactive argument of knowledge (NIAoK), ethSTARK, into an SoK. This SoK is inherently post-quantum secure and has a signature size poly-logarithmic in the size of the NP statement. Thus, our resulting LRS has a signature size of $O(\text{polylog}(\log n))$. By comparison, existing post-quantum ring signatures, regardless of linkability considerations, have signature sizes of $O(\log n)$ at best. Furthermore, leveraging online/offline verification, part of the verification of signatures on the same ring can be shared, resulting in a state-of-the-art amortized verification cost of $O(\text{polylog}(\log n))$.

Our LRS also performs favourably against existing schemes in practical scenarios. Concretely, our scheme has the smallest signature size among all post-quantum linkable ring signatures with non-slanderability for ring size larger than $32$. In our experiment, at $128$-bit security and ring size of $1024$, our LRS has a size of $29$KB, and an amortized verification cost of $0.3$ ms, surpassing the state-of-the-art by a significant margin. Even without considering amortization, the verification time for a single signature is $128$ ms, comparable to those featuring linear signature size. A similar performance advantage can also be seen at signing. Furthermore, our LRS has extremely short public keys ($32$ bytes), while public keys of existing constructions are in the order of kilobytes.

## 2024/653

* Title: Ipotane: Achieving the Best of All Worlds in Asynchronous BFT
* Authors: Xiaohai Dai, Chaozheng Ding, Hai Jin, Julian Loss, Ling Ren
* [Permalink](https://eprint.iacr.org/2024/653)
* [Download](https://eprint.iacr.org/2024/653.pdf)

### Abstract

State-of-the-art asynchronous Byzantine Fault Tolerance (BFT) protocols integrate a partially-synchronous optimistic path. The holy grail in this paradigm is to match the performance of a partially-synchronous protocol in favorable situations and match the performance of a purely asynchronous protocol in unfavorable situations. Several prior works have made progress toward this goal by matching the efficiency of a partially-synchronous protocol in favorable conditions. However, their performance compared to purely asynchronous protocols is reduced when network conditions are unfavorable. To address these shortcomings, a recent work, Abraxas (CCS'23), presents the first optimistic asynchronous BFT protocol that retains stable throughput in all situations. However, Abraxas still incurs very high worst-case latency in unfavorable situations because it is slow at detecting the failure of its optimistic path. Another recent work, ParBFT (CCS'23) guarantees good latency in all situations, but suffers from reduced throughput in unfavorable situations due to its use of extra Asynchronous Binary Agreement (ABA) instances.

To approach our holy grail, we propose Ipotane, which delivers performance comparable to partially-synchronous protocols in favorable situations, and attains performance on par with purely asynchronous protocols in unfavorable situations—in both throughput and latency. Ipotane also runs the two paths simultaneously. It adopts two-chain HotStuff as the optimistic path, thus achieving high performance in favorable situations. As for the pessimistic path, we introduce a new primitive Dual-functional Byzantine Agreement (DBA), which packs the functionalities of biased ABA and Validated Asynchronous Byzantine Agreement (VABA). Ipotane runs DBA instances continuously as the pessimistic path. DBA’s ABA functionality quickly detects the optimistic path’s failure, ensuring Ipotane’s low latency in unfavorable situations. Meanwhile, the VABA functionality continuously produces blocks, maintaining Ipotane’s high throughput. Additionally, the biased property ensures that blocks committed via the optimistic path are respected by DBA instances, guaranteeing consistency across two paths. We conduct extensive experiments to demonstrate that Ipotane achieves high throughput and low latency in all situations.