## In this issue

1. [2024/363] Time-Averaged Analysis of Selfish Mining in Bitcoin
2. [2024/370] Perfectly-Secure Multiparty Computation with Linear ...
3. [2024/376] Perfect (Parallel) Broadcast in Constant Expected ...
4. [2024/416] Mangrove: A Scalable Framework for Folding-based SNARKs
5. [2024/417] An improved exact CRR basis conversion algorithm ...
6. [2024/418] Atomic and Fair Data Exchange via Blockchain
7. [2024/419] New Upper Bounds for Evolving Secret Sharing via ...
8. [2024/420] Gap MCSP is not (Levin) NP-complete in Obfustopia
9. [2024/421] LLRing: Logarithmic Linkable Ring Signatures with ...
10. [2024/422] A Class of Weightwise Almost Perfectly Balanced ...
11. [2024/423] Plan your defense: A comparative analysis of ...
12. [2024/424] On the Concrete Security of Approximate FHE with ...
13. [2024/425] Kolmogorov Comes to Cryptomania: On Interactive ...
14. [2024/426] Efficient Actively Secure DPF and RAM-based 2PC ...
15. [2024/427] A Cautionary Note: Side-Channel Leakage ...
16. [2024/428] SNOW-SCA: ML-assisted Side-Channel Attack on SNOW-V
17. [2024/429] FOLEAGE: $\mathbb{F}_4$OLE-Based Multi-Party ...
18. [2024/430] SoK: Zero-Knowledge Range Proofs
19. [2024/431] Generalized Feistel Ciphers for Efficient Prime ...
20. [2024/432] Perfect Asynchronous MPC with Linear Communication ...
21. [2024/433] UniHand: Privacy-preserving Universal Handover for ...
22. [2024/434] Parameter-Hiding Order-Revealing Encryption without ...
23. [2024/435] Unbiasable Verifiable Random Functions
24. [2024/436] Re-Randomized FROST
25. [2024/437] Insecurity of MuSig and BN Multi-Signatures with ...
26. [2024/438] EFFLUX-F2: A High Performance Hardware Security ...
27. [2024/439] Threshold implementations of cryptographic ...
28. [2024/440] Secret and Shared Keys Recovery on Hamming Quasi- ...
29. [2024/441] Cryptanalysis of rank-2 module-LIP in Totally Real ...
30. [2024/442] Fastcrypto: Pioneering Cryptography Via Continuous ...
31. [2024/443] The cool and the cruel: separating hard parts of ...
32. [2024/444] A trust-minimized e-cash for cryptocurrencies
33. [2024/445] Threshold Structure-Preserving Signatures: Strong ...
34. [2024/446] Estimating the Unpredictability of Multi-Bit Strong ...
35. [2024/447] ORIGO: Proving Provenance of Sensitive Data with ...
36. [2024/448] Differential Cryptanalysis of a Lightweight Block ...
37. [2024/449] Practical Lattice-Based Distributed Signatures for ...
38. [2024/450] The 2Hash OPRF Framework and Efficient Post-Quantum ...
39. [2024/451] Towards Verifiable FHE in Practice: Proving Correct ...
40. [2024/452] Modeling Mobile Crash in Byzantine Consensus
41. [2024/453] Verifiable Information-Theoretic Function Secret ...
42. [2024/454] The Systemic Errors of Banded Quantum Fourier ...
43. [2024/455] Anonymous Complaint Aggregation for Secure Messaging

## 2024/363

* Title: Time-Averaged Analysis of Selfish Mining in Bitcoin
* Authors: Roozbeh Sarenche, Ren Zhang, Svetla Nikova, Bart Preneel
* [Permalink](https://eprint.iacr.org/2024/363)
* [Download](https://eprint.iacr.org/2024/363.pdf)

### Abstract

A Bitcoin miner who owns a sufficient amount of mining power can perform selfish mining to increase his relative revenue. Studies have demonstrated that the time-averaged profit of a selfish miner starts to rise once the mining difficulty level gets adjusted in favor of the attacker. Selfish mining profitability lies in the fact that orphan blocks are not incorporated into the current version of Bitcoin's difficulty adjustment mechanism (DAM). Therefore, it is believed that considering the count of orphan blocks in the DAM can result in selfish mining unprofitability. In this paper, we disprove this belief by providing a formal analysis of the selfish mining time-averaged profit. We present a precise definition of the orphan blocks that can be incorporated into calculating the next epoch's target and then introduce two modified versions of DAM in which both main-chain blocks and orphan blocks are incorporated. We propose two versions of smart intermittent selfish mining, where the first one dominates the normal intermittent selfish mining and the second one results in selfish mining profitability under the modified DAMs. Moreover, we present the orphan exclusion attack with the help of which the attacker can stop honest miners from reporting the orphan blocks. Using combinatorial tools, we analyze the profitability of selfish mining accompanied by the orphan exclusion attack under the modified DAMs. Our result shows that even when considering the orphan blocks in the DAM, normal selfish mining can still be profitable; however, the level of profitability under the modified DAMs is significantly lower than that observed under the current version of Bitcoin DAM.

## 2024/370

* Title: Perfectly-Secure Multiparty Computation with Linear Communication Complexity over Any Modulus
* Authors: Daniel Escudero, Yifan Song, Wenhao Wang
* [Permalink](https://eprint.iacr.org/2024/370)
* [Download](https://eprint.iacr.org/2024/370.pdf)

### Abstract

Consider the task of secure multiparty computation (MPC) among $n$ parties with perfect security and guaranteed output delivery, supporting $t<n/3$ active corruptions. Suppose the arithmetic circuit $C$ to be computed is defined over a finite ring $\mathbb{Z}/q\mathbb{Z}$, for an arbitrary $q\in\mathbb{Z}$. It is known that this type of MPC over such ring is possible, with communication that scales as $O(n|C|)$, assuming that $q$ scales as $\Omega(n)$. However, for constant-size rings $\mathbb{Z}/q\mathbb{Z}$ where $q = O(1)$, the communication is actually $O(n\log n|C|)$ due to the need of the so-called ring extensions. In most natural settings, the number of parties is variable but the ``datatypes'' used for the computation are fixed (e.g. 64-bit integers).. In this regime, no protocol with linear communication exists.

In this work we provide an MPC protocol in this setting: perfect security, G.O.D. and $t<n/3$ active corruptions, that enjoys linear communication $O(n|C|)$, even for constant-size rings $\mathbb{Z}/q\mathbb{Z}$. This includes as important particular cases small fields such as $\mathbb{F}_2$, and also the ring $\mathbb{Z}/2^k\mathbb{Z}$. The main difficulty in achieving this result is that widely used techniques such as linear secret-sharing cannot work over constant-size rings, and instead, one must make use of ring extensions that add $\Omega(\log n)$ overhead, while packing $\Omega(\log n)$ ring elements in each extension element in order to amortize this cost. We make use of reverse multiplication-friendly embeddings (RMFEs) for this packing, and adapt recent techniques in network routing (Goyal et al. CRYPTO'22) to ensure this can be efficiently used for non-SIMD circuits. Unfortunately, doing this naively results in a restriction on the minimum width of the circuit, which leads to an extra additive term in communication of $\mathsf{poly}(n)\cdot\mathsf{depth}(C)$. One of our biggest technical contributions lies in designing novel techniques to overcome this limitation by packing elements that are distributed across different layers. To the best of our knowledge, all works that have a notion of packing (e.g. RMFE or packed secret-sharing) group gates across the same layer, and not doing so, as in our work, leads to a unique set of challenges and complications.

## 2024/376

* Title: Perfect (Parallel) Broadcast in Constant Expected Rounds via Statistical VSS
* Authors: Gilad Asharov, Anirudh Chandramouli
* [Permalink](https://eprint.iacr.org/2024/376)
* [Download](https://eprint.iacr.org/2024/376.pdf)

### Abstract

We study broadcast protocols in the information-theoretic model under optimal conditions, where the number of corruptions $t$ is at most one-third of the parties, $n$. While worst-case $\Omega(n)$ round broadcast protocols are known to be impossible to achieve, protocols with an expected constant number of rounds have been demonstrated since the seminal work of Feldman and Micali [STOC'88]. Communication complexity for such protocols has gradually improved over the years, reaching $O(nL)$ plus expected $O(n^4\log n)$ for broadcasting a message of size $L$ bits.

This paper presents a perfectly secure broadcast protocol with expected constant rounds and communication complexity of $O(nL)$ plus expected $O(n^3 \log^2n)$ bits. In addition, we consider the problem of parallel broadcast, where $n$ senders, each wish to broadcast a message of size $L$. We show a parallel broadcast protocol with expected constant rounds and communication complexity of $O(n^2L)$ plus expected $O(n^3 \log^2n)$ bits. Our protocol is optimal (up to expectation) for messages of length $L \in \Omega(n \log^2 n)$.

Our main contribution is a framework for obtaining perfectly secure broadcast with an expected constant number of rounds from a statistically secure verifiable secret sharing. Moreover, we provide a new statistically secure verifiable secret sharing where the broadcast cost per participant is reduced from $O(n \log n)$ bits to only $O({\sf poly} \log n)$ bits. All our protocols are adaptively secure.

## 2024/416

* Title: Mangrove: A Scalable Framework for Folding-based SNARKs
* Authors: Wilson Nguyen, Trisha Datta, Binyi Chen, Nirvan Tyagi, Dan Boneh
* [Permalink](https://eprint.iacr.org/2024/416)
* [Download](https://eprint.iacr.org/2024/416.pdf)

### Abstract

We present a framework for building efficient folding-based SNARKs. First we develop a new "uniformizing" compiler for NP statements that converts any poly-time computation to a sequence of identical simple steps. The resulting uniform computation is especially well-suited to be processed by a folding-based IVC scheme. Second, we develop two optimizations to folding-based IVC. The first reduces the recursive overhead of the IVC by restructuring the relation to which folding is applied. The second employs a "commit-and-fold" strategy to further simplify the relation. Together, these optimizations result in a folding-based SNARK that has a number of attractive features. First, the scheme uses a constant-size transparent common reference string (CRS). Second, the prover has
(i) low memory footprint,
(ii) makes only two passes over the data,
(iii) is highly parallelizable, and
(iv) is concretely efficient.
Microbenchmarks indicate proving time is comparable to leading monolithic SNARKs, and is significantly faster than other streaming SNARKs. On a laptop, for $2^{24}$ ($2^{32}$) gates, the Mangrove prover is estimated to take $2$ minutes ($8$ hours) with peak memory usage approximately $390$ MB ($800$ MB).