Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: IACR ePrint Archive Newsgroups: sci.crypt Subject: [digest] 2024 Week 41 Date: Mon, 14 Oct 2024 02:29:48 -0000 Organization: A noiseless patient Spider Lines: 2117 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Injection-Date: Mon, 14 Oct 2024 04:29:53 +0200 (CEST) Injection-Info: dont-email.me; posting-host="325750a824a8ce23abb9d2e3b596c461"; logging-data="1097048"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19EMw5JSOaUY75GWUJ2bwxCmX6gBAmQp3Y=" Cancel-Lock: sha1:wyf0XObzTbgYgGGM3uHiftt1Vy4= Bytes: 113799 ## 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 a= llows 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 ha= s 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 su= itable to analyze the cost of quantum preimage attack. Thus, Blocki et al. (T= CC 2022) introduced the parallel reversible pebbling game as a tool to analyz= e resource requirements for a quantum computer. While there is an extensive l= ine of work analyzing pebbling complexity in the (parallel) black pebbling ga= me, 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 gra= ph on $N$ nodes. This yields a separation between classical and reversible pe= bbling costs demonstrating that the reversibility constraint can increase cum= ulative pebbling costs (and space-time costs) by a multiplicative factor of $= N^{(\sqrt 2 + o(1))/\sqrt{\log N}}$ --- the classical pebbling cost (space-ti= me 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^{\sqr= t{\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 constr= aint 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 s= tate-of-the-art recursive pebbling techniques of Alwen et al. (EUROCRYPT 2017= ) can be converted into a recursive reversible pebbling attack without any as= ymptotic increases in pebbling costs. Finally, we extend a result of Blocki e= t al. (ITCS 2020) to show that it is Unique Games hard to approximate the rev= ersible 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 e= t 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 ide= ntified 4 papers (from Eurocrypt, DCC, ToSC and ePrint) that follow on the re= sults 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 Asiacryp= t 2014. We apply these to the aforementioned papers and provide patched versi= ons of their attacks. The main consequence is an increase in the memory compl= exity. We show that in many cases (a notable exception being quantum impossib= le differentials) it is possible to recover the numeric estimates of the flaw= ed 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 tr= acing scheme where the sizes of public keys, secret keys, and ciphertexts are= independent of the number of users. Prior constructions from pairings had si= ze $\Omega(N^{1/3})$. An additional consequence of our techniques is general = result showing that attribute-based encryption for circuits generically impli= es 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 throu= gh a degree $2$ isogeny $\phi$. We call the resulting formulas half different= ial additions: from the knowledge of $\phi(P), \phi(Q)$ and $P-Q$, the half d= ifferential 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 hal= f 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 Mo= ntgomery 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=3D\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$ b= y bit, for a normalized point. In the appendix, we extend our approach to higher dimensional ladders in thet= a coordinates or twisted theta coordinates. In dimension~$2$, after a precomp= utation step which depends on the base point~$P$, our half ladder only costs = ========== REMAINDER OF ARTICLE TRUNCATED ==========