## In this issue

1. [2023/1530] Proofs of Space with Maximal Hardness
2. [2024/338] Tight Indistinguishability Bounds for the XOR of ...
3. [2024/365] Combined Threshold Implementation
4. [2024/554] Leakage-Abuse Attacks Against Structured Encryption ...
5. [2024/555] Quantum Algorithms for Lattice Problems
6. [2024/564] Multiple Group Action Dlogs with(out) Precomputation
7. [2024/568] Communication-Efficient Multi-Party Computation for ...
8. [2024/569] An overview of symmetric fuzzy PAKE protocols
9. [2024/570] Large-Scale Private Set Intersection in the Client- ...
10. [2024/571] MiniCast: Minimizing the Communication Complexity ...
11. [2024/572] Split Gröbner Bases for Satisfiability Modulo ...
12. [2024/573] Tokenised Multi-client Provisioning for Dynamic ...
13. [2024/574] PoMMES: Prevention of Micro-architectural Leakages ...
14. [2024/575] Pairing Optimizations for Isogeny-based Cryptosystems
15. [2024/576] On complexity of the problem of solving systems of ...
16. [2024/577] Determination of cryptographic tables and ...
17. [2024/578] Assessing the quality of Random Number Generators ...
18. [2024/579] Tight Multi-user Security of Ascon and Its Large ...
19. [2024/580] Dynamic Decentralized Functional Encryptions from ...
20. [2024/581] Fault Attack on SQIsign
21. [2024/582] Improved Alternating Moduli PRFs and Post-Quantum ...
22. [2024/584] Efficient Implementations of Square-root Vélu's ...
23. [2024/585] A Complete Beginner Guide to the Number Theoretic ...
24. [2024/586] Encryption Based Covert Channel for Large Language ...
25. [2024/587] Hidden $\Delta$-fairness: A Novel Notion for Fair ...
26. [2024/588] Digital Signatures for Authenticating Compressed ...
27. [2024/589] Blind-Folded: Simple Power Analysis Attacks using ...
28. [2024/590] Revisiting the Security of Fiat-Shamir Signature ...
29. [2024/591] Hash your Keys before Signing: BUFF Security of the ...
30. [2024/592] Asymptotics for the standard block size in primal ...
31. [2024/593] The Case of Small Prime Numbers Versus the Okamoto- ...
32. [2024/594] Greco: Fast Zero-Knowledge Proofs for Valid FHE ...
33. [2024/595] Analysis of Multivariate Encryption Schemes: ...
34. [2024/596] Cryptanalysis of signature schemes based on the ...
35. [2024/597] Blockchain-based decentralized identity system: ...
36. [2024/598] A Characterization of AE Robustness as Decryption ...
37. [2024/599] Probabilistically Checkable Arguments for all NP
38. [2024/600] A note on -Tweakable HCTR: A BBB Secure Tweakable ...
39. [2024/601] Improved Provable Reduction of NTRU and Hypercubic ...
40. [2024/602] Secret-Sharing Schemes for High Slices
41. [2024/603] Worst-Case to Average-Case Hardness of LWE: A ...
42. [2024/604] Generic MitM Attack Frameworks on Sponge Constructions
43. [2024/605] Security Analysis of XHASH8/12
44. [2024/606] Classical Commitments to Quantum States
45. [2024/607] Low-latency Secure Integrated Sensing and ...
46. [2024/608] The Practical Advantage of RSA over ECC and Pairings
47. [2024/609] New Security Proofs and Techniques for Hash-and- ...
48. [2024/610] Practical Delegatable Attribute-Based Anonymous ...
49. [2024/611] A Security Analysis of Restricted Syndrome Decoding ...
50. [2024/612] FHERMA: Building the Open-Source FHE Components ...
51. [2024/613] Hadamard Product Argument from Lagrange-Based ...

## 2023/1530

* Title: Proofs of Space with Maximal Hardness
* Authors: Leonid Reyzin
* [Permalink](https://eprint.iacr.org/2023/1530)
* [Download](https://eprint.iacr.org/2023/1530.pdf)

### Abstract

In a proof of space, a prover performs a complex computation with a large output. A verifier periodically checks that the prover still holds the output. The security goal for a proof of space construction is to ensure that a prover who erases even a portion of the output has to redo a large portion of the complex computation in order to satisfy the verifier.

In existing constructions of proofs of space, the computation that a cheating prover is forced to redo is a small fraction (vanishing or small constant) of the original complex computation. The only exception is a construction of Pietrzak (ITCS 2019) that requires extremely depth-robust graphs, which result in impractically high complexity of the initialization process.

We present the first proof of space of reasonable complexity that ensures that the prover has to redo almost the entire computation (fraction arbitrarily close to 1) when trying to save even an arbitrarily small constant fraction of the space.
Our construction is a generalization of an existing construction called SDR (Fisch, Eurocrypt 2019) deployed on the Filecoin blockchain. Our improvements, while general, also demonstrate that the already deployed construction has considerably better security than previously shown.

Technically, our construction can be viewed as amplifying predecessor-robust graphs. These are directed acyclic graphs in which every subgraph of sufficient relative size $\pi$ contains a large single-sink connected component of relative size $\alpha_\pi$. We take a predecessor-robust graph with constant parameters $(\pi, \alpha_\pi)$, and build a bigger predecessor-robust graph with a near-optimal set of parameters and additional guarantees on sink placement, while increasing the degree only by a small additive constant.

## 2024/338

* Title: Tight Indistinguishability Bounds for the XOR of Independent Random Permutations by Fourier Analysis
* Authors: Itai Dinur
* [Permalink](https://eprint.iacr.org/2024/338)
* [Download](https://eprint.iacr.org/2024/338.pdf)

### Abstract

The XOR of two independent permutations (XoP) is a well-known construction for achieving security beyond the birthday bound when implementing a pseudorandom function using a block cipher (i.e., a pseudorandom permutation). The idealized construction (where the permutations are uniformly chosen and independent) and its variants have been extensively analyzed over nearly 25 years.
The best-known asymptotic information-theoretic indistinguishability bound for the XoP construction is $O(q/2^{1.5n})$, derived by Eberhard in 2017, where $q$ is the number of queries and $n$ is the block length.

A generalization of the XoP construction outputs the XOR of $r \geq 2$ independent permutations, and has also received significant attention in both the single-user and multi-user settings. In particular, for $r = 3$, the best-known bound (obtained by Choi et al. [ASIACRYPT'22]) is about $q^2/2^{2.5 n}$ in the single-user setting and $\sqrt{u} q_{\max}^2/2^{2.5 n}$ in the multi-user setting (where $u$ is the number of users and $q_{\max}$ is the number of queries per user).

In this paper, we prove an indistinguishability bound of $q/2^{(r - 0.5)n}$ for the (generalized) XoP construction in the single-user setting, and a bound of $\sqrt{u} q_{\max}/2^{(r - 0.5)n}$ in the multi-user setting. In particular, for $r=2$, we obtain the bounds $q/2^{1.5n}$ and $\sqrt{u} q_{\max}/2^{1.5n}$ in single-user and multi-user settings, respectively. For $r=3$ the corresponding bounds are $q/2^{2.5n}$ and $\sqrt{u} q_{\max}/2^{2.5n}$. All of these bounds hold assuming $q < 2^{n}/2$ (or $q_{\max} < 2^{n}/2$).

Compared to previous works, we improve all the best-known bounds for the (generalized) XoP construction in the multi-user setting, and the best-known bounds for the generalized XoP construction for $r \geq 3$ in the single-user setting (assuming $q \geq 2^{n/2}$). For the basic two-permutation XoP construction in the single-user setting, our concrete bound of $q/2^{1.5n}$ stands in contrast to the asymptotic bound of $O(q/2^{1.5n})$ by Eberhard.

Since all of our bounds are matched (up to constant factors) for $q \geq 2^{n/2}$ by attacks published by Patarin in 2008 (and their generalizations to the multi-user setting), they are all tight.
We obtain our results by Fourier analysis of Boolean functions. Most of our technical work involves bounding (sums of) Fourier coefficients of the density function associated with sampling without replacement. While the proof of Eberhard relies on similar bounds, our proof is elementary and simpler.

## 2024/365

* Title: Combined Threshold Implementation
* Authors: Jakob Feldtkeller, Jan Richter-Brockmann, Pascal Sasdrich, Tim Güneysu
* [Permalink](https://eprint.iacr.org/2024/365)
* [Download](https://eprint.iacr.org/2024/365.pdf)

### Abstract

Physical security is an important aspect of devices for which an adversary can manipulate the physical execution environment. Recently, more and more attention has been directed towards a security model that combines the capabilities of passive and active physical attacks, i.e., an adversary that performs fault-injection and side-channel analysis at the same time. Implementing countermeasures against such a powerful adversary is not only costly but also requires the skillful combination of masking and redundancy to counteract all reciprocal effects.

In this work, we propose a new methodology to generate combined-secure circuits. We show how to transform TI-like constructions to resist any adversary with the capability to tamper with internal gates and probe internal wires. For the resulting protection scheme, we can prove the combined security in a well-established theoretical security model.

Since the transformation preserves the advantages of TI-like structures, the resulting circuits prove to be more efficient in the number of required bits of randomness (up to 100%), the latency in clock cycles (up to 40%), and even the area for pipelined designs (up to 40%) than the state of the art for an adversary restricted to manipulating a single gate and probing a single wire.