## In this issue

1. [2024/1662] Composability in Watermarking Schemes
2. [2024/1912] Universally Composable and Reliable Password ...
3. [2024/1913] RubikStone: Strongly Space Hard White-Box Scheme ...
4. [2024/1914] Generic, Fast and Short Proofs for Composite Statements
5. [2024/1915] MUTLISS: a protocol for long-term secure ...
6. [2024/1916] Fast, Compact and Hardware-Friendly Bootstrapping ...
7. [2024/1917] Decentralized FHE Computer
8. [2024/1918] Orion's Ascent: Accelerating Hash-Based Zero ...
9. [2024/1919] PASTA on Edge: Cryptoprocessor for Hybrid ...
10. [2024/1920] An Extended Hierarchy of Security Notions for ...
11. [2024/1921] Downlink (T)FHE ciphertexts compression
12. [2024/1922] Deterministic Consensus using Overpass Channels in ...
13. [2024/1923] Implementation analysis of index calculus method on ...
14. [2024/1924] The complexity of solving a random polynomial system
15. [2024/1925] EndGame: Field-Agnostic Succinct Blockchain with Arc
16. [2024/1926] Cryptanalysis of BAKSHEESH Block Cipher
17. [2024/1927] ToFA: Towards Fault Analysis of GIFT and GIFT-like ...
18. [2024/1928] Generic Security of GCM-SST
19. [2024/1929] LightCROSS: A Secure and Memory Optimized Post- ...
20. [2024/1930] Algebraic Zero Knowledge Contingent Payment
21. [2024/1931] On White-Box Learning and Public-Key Encryption
22. [2024/1932] On Witness Encryption and Laconic Zero-Knowledge ...
23. [2024/1933] On Concrete Security Treatment of Signatures Based ...
24. [2024/1934] Quantum One-Time Programs, Revisited
25. [2024/1935] RevoLUT : Rust Efficient Versatile Oblivious Look- ...
26. [2024/1936] Multiparty Shuffle: Linear Online Phase is Almost ...
27. [2024/1937] Asynchronous Byzantine Consensus with Trusted ...
28. [2024/1938] A Formal Treatment of Key Transparency Systems with ...
29. [2024/1939] Machine Learning-Based Detection of Glitch Attacks ...
30. [2024/1940] A Comprehensive Review of Post-Quantum ...
31. [2024/1941] Universally Composable Server-Supported Signatures ...
32. [2024/1942] DGMT: A Fully Dynamic Group Signature From ...
33. [2024/1943] $\textsf{LiLAC}$: Linear Prover, Logarithmic ...
34. [2024/1944] SoK: The apprentice guide to automated fault ...
35. [2024/1945] Multi-Client Attribute-Based and Predicate ...
36. [2024/1946] Distributed Differentially Private Data Analytics ...
37. [2024/1947] One-More Unforgeability for Multi- and Threshold ...

## 2024/1662

* Title: Composability in Watermarking Schemes
* Authors: Jiahui Liu, Mark Zhandry
* [Permalink](https://eprint.iacr.org/2024/1662)
* [Download](https://eprint.iacr.org/2024/1662.pdf)

### Abstract

Software watermarking allows for embedding a mark into a piece of code, such that any attempt to remove the mark will render the code useless. Provably secure watermarking schemes currently seems limited to programs computing various cryptographic operations, such as evaluating pseudorandom functions (PRFs), signing messages, or decrypting ciphertexts (the latter often going by the name ``traitor tracing''). Moreover, each of these watermarking schemes has an ad-hoc construction of its own.

We observe, however, that many cryptographic objects are used as building blocks in larger protocols. We ask: just as we can compose building blocks to obtain larger protocols, can we compose watermarking schemes for the building blocks to obtain watermarking schemes for the larger protocols? We give an affirmative answer to this question, by precisely formulating a set of requirements that allow for composing watermarking schemes. We use our formulation to derive a number of applications.

## 2024/1912

* Title: Universally Composable and Reliable Password Hardening Services
* Authors: Shaoqiang Wu, Ding Wang
* [Permalink](https://eprint.iacr.org/2024/1912)
* [Download](https://eprint.iacr.org/2024/1912.pdf)

### Abstract

The password-hardening service (PH) is a crypto service that armors canonical password authentication with an external key against offline password guessing in case the password file is somehow compromised/leaked. The game-based formal treatment of PH was brought by Everspaugh et al. at USENIX Security'15. Their work is followed by efficiency-enhancing PO-COM (CCS'16), security-patching Phoenix (USENIX Security'17), and functionality-refining PW-Hero (SRDS'22). However, the issue of single points of failure (SPF) inherently impairs the availability of these PH schemes. More specifically, the failure of a single PH server responsible for crypto computation services will suspend password authentication for all users.

We propose the notion of reliable PH, which improves the availability of PH by eliminating SPF. We present a modular PH construction, TF-PH, essentially a generic compiler that can transform any PH protocol into a reliable one without SPF via introducing threshold failover. Particularly, we propose a concrete reliable PH protocol, called TF-RePhoenix, a simple and efficient construction with RePhoenix (which improves over Phoenix at USENIX Security'17) as the PH module. Security is proven within the universally composable (UC) security framework and the random oracle model (ROM), where we, for the first time, formalize the ideal UC functionalities of PH and reliable PH. We comparatively evaluate the efficiency of our TF-PH with the canonical threshold method (taken as an example, the threshold solution introduced by Brost et al. at CCS'20 in a PH-derived domain -- password-hardened encryption). Results show that our threshold failover-based solution to SPF provides optimal performance and achieves failover in a millisecond.

## 2024/1913

* Title: RubikStone: Strongly Space Hard White-Box Scheme Based on Lookup Table Pool and Key Guidance Implementation
* Authors: Yipeng Shi
* [Permalink](https://eprint.iacr.org/2024/1913)
* [Download](https://eprint.iacr.org/2024/1913.pdf)

### Abstract

White-box cryptography is a software implementation technique based on lookup tables, with effective resistance against key extraction and code lifting attacks being a primary focus of its research. Space hardness is a widely used property for evaluating the resistance of white-box ciphers against code lifting attacks. However, none of the existing ciphers can provide strong space hardness under adaptively chosen-space attack model.
We propose a new scheme based on the lookup table pool and key guidance implementation as a more efficient approach to utilizing lookup tables to provide better security and practicality. Specifically, we introduce a new white-box cipher, RubikStone, which offers a range of variants from tens of kilobytes to infinite size. For the first time, we prove that all variants of RubikStone can provide strong space hardness under an adaptively chosen-space attack model. Additionally, we present a specific key guidance application for cloud-based DRM scenarios. Based on our proposed RubikStone variants, the key guidance applications can achieve at least overall $(0.950T, 128)$-space hardness..
Furthermore, we introduce a novel property, table consumption rate, for evaluating the durability of a specific white-box cryptographic implementation. In our evaluation, all the instantiations of RubikStone exhibit the lowest table consumption rate in algorithms with equally sized lookup tables. Besides, we conduct a comprehensive statistical analysis of the operations in all existing white-box ciphers. Our findings indicate that RubikStone remains highly competitive in terms of computational efficiency despite offering unprecedented levels of security.

## 2024/1914

* Title: Generic, Fast and Short Proofs for Composite Statements
* Authors: Zhuo Wu, Shi Qi, Xinxuan Zhang, Yi Deng
* [Permalink](https://eprint.iacr.org/2024/1914)
* [Download](https://eprint.iacr.org/2024/1914.pdf)

### Abstract

This work introduces a novel technique to enhance the efficiency of proving composite statements. We present the \textit{Hash-and-Prove} framework to construct zkSNARKs for proving satisfiability of arithmetic circuits with additional \textit{Algebraic Gate}. These algebraic gates serve as building blocks for forming more generalized relations in algebra. Unlike Pedersen-committed \textit{Commit-and-Prove} SNARKs, which suffer from increased proof size and verification overhead when proving composite statements, our solution significantly improves both proof size and verification time while maintaining competitive and practical prover efficiency.

In the application of proof of solvency where we need to prove knowledge of $x$ such that SHA$256(g^x)=y$, our approach achieves a 100$\times$ reduction in proof size and a 500$\times$ reduction in verification time, along with a 2$\times$ speedup in proving time compared to the work of Agrawal et al.(CRYPTO 2018). For proving ECDSA signatures verification, we achieve a proof time of 2.1 seconds, which is a 70$\times$ speedup compared to using Groth16, and a proof size of 4.81 kb, which is a 160$\times$ reduction compared to Field Agnostic SNARKs(Block et al., CRYPTO 2024).

## 2024/1915

* Title: MUTLISS: a protocol for long-term secure distributed storage over multiple remote QKD networks
* Authors: Thomas Prévost, Olivier Alibart, Anne Marin, Marc Kaplan
* [Permalink](https://eprint.iacr.org/2024/1915)
* [Download](https://eprint.iacr.org/2024/1915.pdf)

### Abstract

We introduce MULTISS, a new distributed storage protocol over multiple remote Quantum Key Distribution (QKD) networks that ensures long-term data confidentiality. Our protocol extends LINCOS, a secure storage protocol that uses Shamir secret sharing to distribute data in a single QKD network. Instead MULTISS uses a hierarchical secret scheme that makes certain shares mandatory for the reconstruction of the original secret. We prove that MULTISS ensures that the stored data remain secure even if an eavesdropper (1) gets full access to all storage servers of some of the QKD networks or (2) stores and breaks later all the classical communication between the QKD networks. We demonstrate that this is strictly more secure than LINCOS which is broken as soon as one QKD network is compromised.
Our protocol, like LINCOS, has a procedure to update the shares stored in each QKD network without reconstructing the original data. In addition, we provide a procedure to recover from a full compromission of one of the QKD network.. In particular, we introduce a version of the protocol that can only be implemented over a restricted network topologies, but minimizes the communication required in the recovery procedure.
In practice, the MULTISS protocol is designed for the case of several QKD networks at the metropolitan scale connected to each other through channels secured by classical cryptography. Hence, MULTISS offers a secure distributed storage solution in a scenario that is compatible with the current deployment of quantum networks.