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 <noreply@example.invalid>
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: <ez42UpG-ZdI9C5sUQWfdw6-HVuskTbB5@eprint.iacr.org.invalid>
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 ==========