## In this issue

1. [2023/1343] Universally Composable Auditable Surveillance
2. [2023/1344] Analyzing the Real-World Security of the Algorand ...
3. [2023/1345] Experimenting with Zero-Knowledge Proofs of Training
4. [2023/1346] Street Rep: A Privacy-Preserving Reputation ...
5. [2023/1347] Decentralised Repeated Modular Squaring Service ...
6. [2023/1348] Adaptively Secure (Aggregatable) PVSS and ...
7. [2023/1349] Communication Lower Bounds of Key-Agreement ...
8. [2023/1350] On the Security of KZG Commitment for VSS
9. [2023/1351] Bicameral and Auditably Private Signatures
10. [2023/1352] ACE-HoT: Accelerating an extreme amount of ...
11. [2023/1353] Automatic Search Model for Related-Tweakey ...
12. [2023/1354] Privacy Preserving Feature Selection for Sparse ...
13. [2023/1355] Security Proofs for Key-Alternating Ciphers with ...
14. [2023/1356] Small Private Key Attack Against a Family of RSA- ...
15. [2023/1357] Multimixer-128: Universal Keyed Hashing Based on ...
16. [2023/1358] The Locality of Memory Checking
17. [2023/1359] Automated Meet-in-the-Middle Attack Goes to Feistel
18. [2023/1360] Payment Splitting in Lightning Network as a ...
19. [2023/1361] Let's Go Eevee! A Friendly and Suitable Family of ...
20. [2023/1362] Comments on certain past cryptographic flaws ...
21. [2023/1363] Amortized NISC over $\mathbb{Z}_{2^k}$ from RMFE
22. [2023/1364] Meeting in a Convex World: Convex Consensus with ...
23. [2023/1365] On The Black-Box Complexity of Correlation ...
24. [2023/1366] Compact Frequency Estimators in Adversarial ...
25. [2023/1367] Practical Constructions for Single Input ...
26. [2023/1368] Towards post-quantum secure PAKE - A tight security ...
27. [2023/1369] Ramp hyper-invertible matrices and their ...
28. [2023/1370] Ideal-SVP is Hard for Small-Norm Uniform Prime Ideals
29. [2023/1371] Oracle Recording for Non-Uniform Random Oracles, ...
30. [2023/1372] Cryptographic Key Exchange: An Innovation Outlook
31. [2023/1373] Reframing And Extending The Random Probing Expansion
32. [2023/1374] On Weighted-Sum Orthogonal Latin Squares and Secret ...
33. [2023/1375] DeepCover DS28C36: A Hardware Vulnerability ...
34. [2023/1376] Bootstrapping Homomorphic Encryption via Functional ...
35. [2023/1377] Janus: Fast Privacy-Preserving Data Provenance For ...
36. [2023/1378] Advisor-Verifier-Prover Games and the Hardness of ...
37. [2023/1379] GLEVIAN and VIGORNIAN: Robust beyond-birthday AEAD ...

## 2023/1343

* Title: Universally Composable Auditable Surveillance
* Authors: Valerie Fetzer, Michael Klooß, Jörn Müller-Quade, Markus Raiber, Andy Rupp
* [Permalink](https://eprint.iacr.org/2023/1343)
* [Download](https://eprint.iacr.org/2023/1343.pdf)

### Abstract

User privacy is becoming increasingly important in our digital society. Yet, many applications face legal requirements or regulations that prohibit unconditional anonymity guarantees, e.g., in electronic payments where surveillance is mandated to investigate suspected crimes.

As a result, many systems have no effective privacy protections at all, or have backdoors, e.g., stored at the operator side of the system, that can be used by authorities to disclose a user’s private information (e.g., lawful interception). The problem with such backdoors is that they also enable silent mass surveillance within the system. To prevent such misuse, various approaches have been suggested which limit possible abuse or ensure it can be detected. Many works consider auditability of surveillance actions but do not enforce that traces are left when backdoors are retrieved. A notable exception which offers retrospective and silent surveillance is the recent work on misuse-resistant surveillance by Green et al. (EUROCRYPT’21). However, their approach relies on extractable witness encryption, which is a very strong primitive with no known efficient and secure implementations.

In this work, we develop a building block for auditable surveillance. In our protocol, backdoors or escrow secrets of users are protected in multiple ways: (1) Backdoors are short-term and user-specific; (2) they are shared between trustworthy parties to avoid a single point of failure; and (3) backdoor access is given conditionally. Moreover (4) there are audit trails and public statistics for every (granted) backdoor request; and (5) surveillance remains silent, i.e., users do not know they are surveilled. Concretely, we present an abstract UC-functionality which can be used to augment applications with auditable surveillance capabilities. Our realization makes use of threshold encryption to protect user secrets, and is concretely built in a blockchain context with committee-based YOSO MPC. As a consequence, the committee can verify that the conditions for backdoor access are given, e.g., that law enforcement is in possession of a valid surveillance warrant (via a zero-knowledge proof). Moreover, access leaves an audit trail on the ledger, which allows an auditor to retrospectively examine surveillance decisions.

As a toy example, we present an Auditably Sender-Traceable Encryption scheme, a PKE scheme where the sender can be deanonymized by law enforcement. We observe and solve problems posed by retrospective surveillance via a special non-interactive non-committing encryption scheme which allows zero-knowledge proofs over message, sender identity and (escrow) secrets.

## 2023/1344

* Title: Analyzing the Real-World Security of the Algorand Blockchain
* Authors: Fabrice Benhamouda, Erica Blum, Jonathan Katz, Derek Leung, Julian Loss, Tal Rabin
* [Permalink](https://eprint.iacr.org/2023/1344)
* [Download](https://eprint.iacr.org/2023/1344.pdf)

### Abstract

The Algorand consensus protocol is interesting both in theory and in practice.. On the theoretical side, to achieve adaptive security, it introduces the novel idea of player replaceability, where each step of the protocol is executed by a different randomly selected committee whose members remain secret until they send their first and only message. The protocol provides consistency under arbitrary network conditions and liveness under intermittent network partitions. On the practical side, the protocol is used to secure the Algorand cryptocurrency, whose total value is approximately $850M at the time of writing.

The Algorand protocol in use differs substantially from the protocols described in the published literature on Algorand. Despite its significance, it lacks a formal analysis. In this work, we describe and analyze the Algorand consensus protocol as deployed today in Algorand’s ecosystem. We show that the overall protocol framework is sound by characterizing network conditions and parameter settings under which the protocol can be proven secure.

## 2023/1345

* Title: Experimenting with Zero-Knowledge Proofs of Training
* Authors: Sanjam Garg, Aarushi Goel, Somesh Jha, Saeed Mahloujifar, Mohammad Mahmoody, Guru-Vamsi Policharla, Mingyuan Wang
* [Permalink](https://eprint.iacr.org/2023/1345)
* [Download](https://eprint.iacr.org/2023/1345.pdf)

### Abstract

How can a model owner prove they trained their model according to the correct specification? More importantly, how can they do so while preserving the privacy of the underlying dataset and the final model? We study this problem and formulate the notion of zero-knowledge proof of training (zkPoT), which formalizes rigorous security guarantees that should be achieved by a privacy-preserving proof of training.
While it is theoretically possible to design zkPoT for any model using generic zero-knowledge proof systems, this approach results in extremely unpractical proof generation times. Towards designing a practical solution, we propose the idea of combining techniques from MPC-in-the-head and zkSNARKs literature to strike an appropriate trade-off between proof size and proof computation time. We instantiate this idea and propose a concretely efficient, novel zkPoT protocol for logistic regression.

Crucially, our protocol is streaming-friendly and does not require RAM proportional to the size of the circuit being trained and, hence, can be adapted to the requirements of available hardware. We expect the techniques developed in this paper to also generally be useful for designing efficient zkPoT protocols for other relatively more sophisticated ML models.

We implemented and benchmarked prover/verifier runtimes and proof sizes for training a logistic regression model using mini-batch gradient descent on a 4~GB dataset of 262,144 records with 1024 features. We divide our protocol into three phases: (1) data-independent offline phase (2) data-dependent phase that is independent of the model (3) online phase that depends both on the data and the model. The total proof size (across all three phases) is less than $10\%$ of the data set size ($<350$~MB). In the online phase, the prover and verifier times are under 10 minutes and half a minute respectively, whereas in the data-dependent phase, they are close to one hour and a few seconds respectively.

## 2023/1346

* Title: Street Rep: A Privacy-Preserving Reputation Aggregation System
* Authors: Christophe Hauser, Shirin Nilizadeh, Yan Shoshitaishvili, Ni Trieu, Srivatsan Ravi, Christopher Kruegel, Giovanni Vigna
* [Permalink](https://eprint.iacr.org/2023/1346)
* [Download](https://eprint.iacr.org/2023/1346.pdf)

### Abstract

Over the last decade, online reputation has become a central aspect of our digital lives. Most online services and communities assign a reputation score to users, based on feedback from other users about various criteria such as how reliable, helpful, or knowledgeable a person is. While many online services compute reputation based on the same set of such criteria, users currently do not have the ability to use their reputation scores across services. As a result, users face trouble establishing themselves on new services or trusting each other on services that do not support reputation tracking. Existing systems that aggregate reputation scores, unfortunately, provide no guarantee in terms of user privacy, and their use makes user accounts linkable. Such a lack of privacy may result in embarrassment, or worse, place users in danger.