## In this issue

1. [2024/214] Distributed Fiat-Shamir Transform
2. [2024/218] Lightweight Leakage-Resilient PRNG from TBCs using ...
3. [2024/220] Security Properties of One-Way Key Chains and ...
4. [2024/221] Mastic: Private Weighted Heavy-Hitters and ...
5. [2024/222] Reducing the Number of Qubits in Quantum Factoring
6. [2024/223] Game-Theoretically Fair Distributed Sampling
7. [2024/224] Amplification of Non-Interactive Zero Knowledge, ...
8. [2024/225] Universal Computational Extractors from Lattice ...
9. [2024/226] Attribute-based Keyed (Fully) Homomorphic Encryption
10. [2024/227] Adaptively Sound Zero-Knowledge SNARKs for UP
11. [2024/228] On the Untapped Potential of the Quantum FLT-based ...
12. [2024/229] Strong Batching for Non-Interactive Statistical ...
13. [2024/230] Analysis of Layered ROLLO-I
14. [2024/231] Need for Speed: Leveraging the Power of Functional ...
15. [2024/232] On the Security of Nova Recursive Proof System
16. [2024/233] Cayley hashing with cookies
17. [2024/234] Bare PAKE: Universally Composable Key Exchange from ...
18. [2024/235] Pseudorandom Error-Correcting Codes
19. [2024/236] Public-Key Cryptography through the Lens of Monoid ...
20. [2024/237] Collusion-Resilience in Transaction Fee Mechanism ...
21. [2024/238] A Single Trace Fault Injection Attack on Hedged ...
22. [2024/239] Simulation-Secure Threshold PKE from Standard ...
23. [2024/240] Implementation of Cryptanalytic Programs Using ChatGPT
24. [2024/241] Generalized Adaptor Signature Scheme: From Two- ...
25. [2024/242] Perfectly-Secure MPC with Constant Online ...
26. [2024/243] Towards Achieving Asynchronous MPC with Linear ...
27. [2024/244] Don’t Use It Twice! Solving Relaxed Linear Code ...
28. [2024/245] Linear-Communication Asynchronous Complete Secret ...
29. [2024/246] OCash: Fully Anonymous Payments between Blockchain ...
30. [2024/247] Fault-Resistant Partitioning of Secure CPUs for ...
31. [2024/248] FRIDA: Data Availability Sampling from FRI
32. [2024/249] Robust Additive Randomized Encodings from IO and ...
33. [2024/250] Exploring the Six Worlds of Gröbner Basis ...
34. [2024/251] Communication-Optimal Convex Agreement
35. [2024/252] Short Signatures from Regular Syndrome Decoding, ...
36. [2024/253] 2PC-MPC: Emulating Two Party ECDSA in Large-Scale MPC
37. [2024/254] Adaptive Security in SNARGs via iO and Lossy Functions
38. [2024/255] Revisiting Differential-Linear Attacks via a ...
39. [2024/256] Fiat-Shamir for Bounded-Depth Adversaries
40. [2024/257] LatticeFold: A Lattice-based Folding Scheme and its ...
41. [2024/258] SoK: Decentralized Storage Network
42. [2024/259] Anonymity on Byzantine-Resilient Decentralized ...
43. [2024/260] Kleptographic Attacks against Implicit Rejection
44. [2024/261] Election Eligibility with OpenID: Turning ...
45. [2024/262] Note on the cryptanalysis of Speedy
46. [2024/263] Threshold Encryption with Silent Setup
47. [2024/264] Extractable Witness Encryption for KZG Commitments ...
48. [2024/265] Beyond the circuit: How to Minimize Foreign ...
49. [2024/266] WhisPIR: Stateless Private Information Retrieval ...
50. [2024/267] zkPi: Proving Lean Theorems in Zero-Knowledge
51. [2024/268] A New Approach to Generic Lower Bounds: ...
52. [2024/269] A note on PUF-Based Robust and Anonymous ...
53. [2024/270] YPIR: High-Throughput Single-Server PIR with Silent ...
54. [2024/271] Understanding User-Perceived Security Risks and ...

## 2024/214

* Title: Distributed Fiat-Shamir Transform
* Authors: Michele Battagliola, Andrea Flamini
* [Permalink](https://eprint.iacr.org/2024/214)
* [Download](https://eprint.iacr.org/2024/214.pdf)

### Abstract

The recent surge of distribute technologies caused an increasing interest towards threshold signature protocols, that peaked with the recent NIST First Call for Multi-Party Threshold Schemes.
Since its introduction, the Fiat-Shamir Transform has been the most popular way to design standard digital signature schemes.
In this work, we translate the Fiat-Shamir Transform into a multi-party setting, building a framework that seeks to be an alternative, easier way to design threshold digital signatures. We do that by introducing the concept of threshold identification scheme and threshold sigma protocol, and showing necessary and sufficient conditions to prove the security of the threshold signature schemes derived from them.
Lastly, we show a practical application of our framework providing an alternative security proof for Sparkle, a recent threshold Schnorr signature. In particular, we consider the threshold identification scheme underlying Sparkle and prove the security of the signature derived from it.
We show that using our framework the effort required to prove the security of threshold signatures might be drastically lowered. In fact, instead of reducing explicitly its security to the security of a hard problem, it is enough to prove some properties of the underlying threshold sigma protocol and threshold identification scheme. Then, by applying the results that we prove in this paper it is guaranteed that the derived threshold signature is secure.

## 2024/218

* Title: Lightweight Leakage-Resilient PRNG from TBCs using Superposition
* Authors: Mustafa Khairallah, Srinivasan Yadhunathan, Shivam Bhasin
* [Permalink](https://eprint.iacr.org/2024/218)
* [Download](https://eprint.iacr.org/2024/218.pdf)

### Abstract

In this paper, we propose a leakage-resilient pseudo-random number generator (PRNG) design that leverages the rekeying techniques of the PSV-Enc encryption scheme and the superposition property of the Superposition-Tweak-Key (STK) framework. The random seed of the PRNG is divided into two parts; one part is used as an ephemeral key that changes every two calls to a tweakable block cipher (TBC), and the other part is used as a static long-term key. Using the superposition property, we show that it is possible to eliminate observable leakage by only masking the static key. Thus, our proposal itself can be seen as a superposition of masking and rekeying. We show that our observations can be used to design an unpredictable-with-leakage PRNG as long as the static key is protected, and the ephemeral key cannot be attacked with 2 traces. Our construction enjoys better theoretical security arguments than PSV-Enc; better Time-Data trade-off and leakage assumptions, using the recently popularized unpredictability with leakage. We verify our proposal by performing Test Vector Leakage Assessment (TVLA) on an STK-based TBC (\deoxys) operated with a fixed key and a dynamic random tweak. Our results show that while the protection of the static key is non-trivial, it only requires $\approx 10\%$ overhead for first-order protection in the most conservative setting, unlike traditional masking which may require significant overheads of $300\%$ or more.

## 2024/220

* Title: Security Properties of One-Way Key Chains and Implications for Security Protocols like TLS 1.3
* Authors: John Preuß Mattsson
* [Permalink](https://eprint.iacr.org/2024/220)
* [Download](https://eprint.iacr.org/2024/220.pdf)

### Abstract

One-way key chains or ratchets play a vital role in numerous important security protocols such as TLS 1.3, QUIC, Signal, MLS, EDHOC, and OSCORE. Despite the crucial role they play, very little is known about their security properties. This paper categorizes and examines different key chain constructions, offering a comprehensive overview of their security. Our analysis reveals notable distinctions among the number of collisions occurring within chains, between chains, and between a chain and a random set. Notably, the type of key chain used in protocols such as TLS 1.3 and Signal exhibit a significant number of weak keys, an unexpectedly high rate of key collisions surpassing birthday attack expectations, and a predictable shrinking key space susceptible to novel Time-Memory Trade-Off (TMTO) attacks with complexity $\le N^{1/3}$, which is well within the capabilities of current supercomputers and distributed systems. Consequently, the security level provided by e.g., TLS 1.3 is significantly lower than anticipated based on key sizes. To address these concerns, we analyze the aforementioned protocols and provide numerous concrete recommendations for enhancing their security, as well as guidance for future security protocol design.

## 2024/221

* Title: Mastic: Private Weighted Heavy-Hitters and Attribute-Based Metrics
* Authors: Dimitris Mouris, Christopher Patton, Hannah Davis, Pratik Sarkar, Nektarios Georgios Tsoutsos
* [Permalink](https://eprint.iacr.org/2024/221)
* [Download](https://eprint.iacr.org/2024/221.pdf)

### Abstract

Insight into user experience and behavior is critical to the success of large software systems and web services. Yet gaining such insights, while preserving user privacy, is a significant challenge. Recent advancements in multi-party computation have made it practical to compute verifiable aggregates over secret shared data. One important use case for these protocols is heavy hitters, where the servers compute the most popular inputs held by the users without learning the inputs themselves. The Poplar protocol (IEEE S&P 2021) focuses on this use case, but cannot support other aggregation tasks. Another such protocol, Prio (NSDI 2017), supports a wider variety of statistics but is unsuitable for heavy hitters.

We introduce Mastic, a flexible protocol for private and verifiable general-purpose statistics based on function secret sharing and zero-knowledge proofs on secret shared data. Mastic is the first to solve the more general problem of weighted heavy-hitters, enabling new use cases, not supported by Prio or Poplar. In addition, Mastic allows grouping general-purpose metrics by user attributes, such as their geographic location or browser version, without sacrificing privacy or incurring high-performance costs, which is a major improvement over Prio. We demonstrate Mastic's benefits with two real-world applications, private network error logging and browser telemetry, and compare our protocol with Prio and Poplar on a wide area network. Overall, we report over one order of magnitude performance improvement over Poplar for heavy hitters and $1.5-2\times$ improvement over Prio for attribute-based metrics.