## In this issue

1. [2024/334] The Impact of Reversibility on Parallel Pebbling
2. [2024/563] A Note on Related-Tweakey Impossible Differential ...
3. [2024/867] Optimal Traitor Tracing from Pairings
4. [2024/1582] Halving differential additions on Kummer lines
5. [2024/1591] MPC-in-the-Head Framework without Repetition and ...
6. [2024/1595] DeepFold: Efficient Multilinear Polynomial ...
7. [2024/1596] Secret Sharing with Publicly Verifiable Deletion
8. [2024/1597] An undetectable watermark for generative image models
9. [2024/1598] On the security of the initial tropical Stickel ...
10. [2024/1599] Simplified PIR and CDS Protocols and Improved ...
11. [2024/1600] Pacmann: Efficient Private Approximate Nearest ...
12. [2024/1601] Juggernaut: Efficient Crypto-Agnostic Byzantine ...
13. [2024/1602] Cryptography and Collective Power
14. [2024/1603] Boosting SNARKs and Rate-1 Barrier in Arguments of ...
15. [2024/1604] Predicting truncated multiple matrix congruential ...
16. [2024/1605] Nebula: Efficient read-write memory and switchboard ...
17. [2024/1606] NeutronNova: Folding everything that reduces to ...
18. [2024/1607] Tighter Proofs for PKE-to-KEM Transformation in the ...
19. [2024/1608] Mild Asymmetric Message Franking: Illegal-Messages- ...
20. [2024/1609] Blaze: Fast SNARKs from Interleaved RAA Codes
21. [2024/1610] Secret Sharing with Snitching
22. [2024/1611] Rhombus: Fast Homomorphic Matrix-Vector ...
23. [2024/1612] On Wagner's k-Tree Algorithm Over Integers
24. [2024/1613] Efficient Maliciously Secure Oblivious Exponentiations
25. [2024/1614] Related-Key Cryptanalysis of FUTURE
26. [2024/1615] LeOPaRd: Towards Practical Post-Quantum Oblivious ...
27. [2024/1616] End-to-End Encrypted Cloud Storage in the Wild: A ...
28. [2024/1617] Algebraic Equipage for Learning with Errors in ...
29. [2024/1618] Shaking up authenticated encryption
30. [2024/1619] Structure-Preserving Compressing Primitives: Vector ...
31. [2024/1620] Really Complex Codes with Application to STARKs
32. [2024/1621] PAKE Combiners and Efficient Post-Quantum ...
33. [2024/1622] A New Approach Towards Encrypted Data Sharing and ...
34. [2024/1623] General Functional Bootstrapping using CKKS
35. [2024/1624] Double-Matrix: Complete Diffusion in a Single Round ...
36. [2024/1625] On the Tight Security of the Double Ratchet
37. [2024/1626] Faster Proofs and VRFs from Isogenies
38. [2024/1627] Lollipops of pairing-friendly elliptic curves for ...
39. [2024/1628] Glacius: Threshold Schnorr Signatures from DDH with ...
40. [2024/1629] Efficient Key-Switching for Word-Type FHE and GPU ...
41. [2024/1630] Hybrid Password Authentication Key Exchange in the ...
42. [2024/1631] Sparrow: Space-Efficient zkSNARK for Data-Parallel ...
43. [2024/1632] Fully Secure Searchable Encryption from PRFs, ...
44. [2024/1633] Efficient Boolean-to-Arithmetic Mask Conversion in ...
45. [2024/1634] On Constructing Pseudorandom Involutions: Feistel ...
46. [2024/1635] RPO-M31 and XHash-M31: Efficient Hash Functions for ...
47. [2024/1636] Quantum State Group Actions
48. [2024/1637] Bootstrapping Small Integers With CKKS
49. [2024/1638] Modular Reduction in CKKS
50. [2024/1639] Efficient Quantum Pseudorandomness from Hamiltonian ...
51. [2024/1640] Maximizing the Utility of Cryptographic Setups: ...
52. [2024/1641] Simplification Issues of An Authentication and Key ...
53. [2024/1642] Fuzzy PSI via Oblivious Protocol Routing
54. [2024/1643] Optimizing Liveness for Blockchain-Based Sealed-Bid ...
55. [2024/1644] A Tight Lower Bound on the TdScrypt Trapdoor ...
56. [2024/1645] Fiat Shamir Goes Rational
57. [2024/1646] Transaction Execution Mechanisms
58. [2024/1647] Curve Forests: Transparent Zero-Knowledge Set ...
59. [2024/1648] SIMD-style Sorting of Integer Sequence in RLWE ...
60. [2024/1649] Multiplying Polynomials without Powerful ...
61. [2024/1650] Towards Practical Oblivious Map
62. [2024/1651] One-Shot Native Proofs of Non-Native Operations in ...

## 2024/334

* Title: The Impact of Reversibility on Parallel Pebbling
* Authors: Jeremiah Blocki, Blake Holman, Seunghoon Lee
* [Permalink](https://eprint.iacr.org/2024/334)
* [Download](https://eprint.iacr.org/2024/334.pdf)

### Abstract

The (parallel) classical black pebbling game is a helpful abstraction which allows us to analyze the resources (time, space, space-time, cumulative space) necessary to evaluate a function $f$ with a static data-dependency graph $G$ on a (parallel) computer. In particular, the parallel black pebbling game has been used as a tool to quantify the (in)security of Data-Independent Memory-Hard Functions (iMHFs). However, the classical black pebbling game is not suitable to analyze the cost of quantum preimage attack. Thus, Blocki et al. (TCC 2022) introduced the parallel reversible pebbling game as a tool to analyze resource requirements for a quantum computer. While there is an extensive line of work analyzing pebbling complexity in the (parallel) black pebbling game, comparatively little is known about the parallel reversible pebbling game.. Our first result is a lower bound of $\Omega\left(N^{1+\sqrt{\frac{ 2-o(1)}{\log N}}} \right)$ on the reversible cumulative pebbling cost for a line graph on $N$ nodes. This yields a separation between classical and reversible pebbling costs demonstrating that the reversibility constraint can increase cumulative pebbling costs (and space-time costs) by a multiplicative factor of $N^{(\sqrt 2 + o(1))/\sqrt{\log N}}$ --- the classical pebbling cost (space-time or cumulative) for a line graph is just $\mathcal{O}(N)$. On the positive side, we prove that any classical parallel pebbling can be transformed into a reversible pebbling strategy whilst increasing space-time (resp. cumulative memory) costs by a multiplicative factor of at most $\mathcal{O}\left(N^{\sqrt{\frac{8}{\log N}}}\right)$ (resp. $\mathcal{O}\left(N^{\mathcal{O}(1)/\sqrt[4]{\log N}}\right)$). We also analyze the impact of the reversibility constraint on the cumulative pebbling cost of depth-robust and depth-reducible DAGs exploiting reversibility to improve constant factors in a prior lower bound of Alwen et al. (EUROCRYPT 2017). For depth-reducible DAGs we show that the state-of-the-art recursive pebbling techniques of Alwen et al. (EUROCRYPT 2017) can be converted into a recursive reversible pebbling attack without any asymptotic increases in pebbling costs. Finally, we extend a result of Blocki et al. (ITCS 2020) to show that it is Unique Games hard to approximate the reversible cumulative pebbling cost of a DAG $G$ to within any constant factor.

## 2024/563

* Title: A Note on Related-Tweakey Impossible Differential Attacks
* Authors: Xavier Bonnetain, Virginie Lallemand
* [Permalink](https://eprint.iacr.org/2024/563)
* [Download](https://eprint.iacr.org/2024/563.pdf)

### Abstract

In this short note we review the technique proposed at ToSC 2018 by Sadeghi et al. for attacks built upon several related-tweakey impossible differential trails. We show that the initial encryption queries are improper and lead the authors to misevaluating a filtering value in the key recovery phase. We identified 4 papers (from Eurocrypt, DCC, ToSC and ePrint) that follow on the results of Sadeghi et al., and in three of them the issue was propagated.
We thus present a careful analysis of these types of attacks and give generic complexity formulas similar to the ones proposed by Boura et al. at Asiacrypt 2014. We apply these to the aforementioned papers and provide patched versions of their attacks. The main consequence is an increase in the memory complexity. We show that in many cases (a notable exception being quantum impossible differentials) it is possible to recover the numeric estimates of the flawed analysis, and in all cases we were able to build a correct attack reaching the same number of rounds.

## 2024/867

* Title: Optimal Traitor Tracing from Pairings
* Authors: Mark Zhandry
* [Permalink](https://eprint.iacr.org/2024/867)
* [Download](https://eprint.iacr.org/2024/867.pdf)

### Abstract

We use pairings over elliptic curves to give a collusion-resistant traitor tracing scheme where the sizes of public keys, secret keys, and ciphertexts are independent of the number of users. Prior constructions from pairings had size $\Omega(N^{1/3})$. An additional consequence of our techniques is general result showing that attribute-based encryption for circuits generically implies optimal traitor tracing.

## 2024/1582

* Title: Halving differential additions on Kummer lines
* Authors: Damien Robert, Nicolas Sarkis
* [Permalink](https://eprint.iacr.org/2024/1582)
* [Download](https://eprint.iacr.org/2024/1582.pdf)

### Abstract

We study differential additions formulas on Kummer lines that factorize through a degree $2$ isogeny $\phi$. We call the resulting formulas half differential additions: from the knowledge of $\phi(P), \phi(Q)$ and $P-Q$, the half differential addition allows to recover $P+Q$. We explain how Mumford's theta group theory allows, in any model of Kummer lines, to find a basis of the half differential relations. This involves studying the dimension $2$ isogeny $(P, Q) \mapsto (P+Q, P-Q)$.

We then use the half differential addition formulas to build a new type of Montgomery ladder, called the half-ladder, using a time-memory trade-off. On a Montgomery curve with full rational $2$-torsion, our half ladder first build a succession of isogeny images $P_i=\phi_i(P_{i-1})$, which only depends on the base point $P$ and not the scalar $n$, for a pre-computation cost of $2S+1m_0$ by bit. Then we use half doublings and half differential additions to compute any scalar multiplication $n \cdot P$, for a cost of $4M+2S+1m_0$ by bit. The total cost is then $4M+4S+2m_0$, even when the base point $P$ is not normalized. By contrast, the usual Montgomery ladder costs $4M+4S+1m+1m_0$ by bit, for a normalized point.