Newsportal USENET - [digest] 2024 Week 41

## 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 allows 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 has 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 suitable to analyze the cost of quantum preimage attack. Thus, Blocki et al. (TCC 2022) introduced the parallel reversible pebbling game as a tool to analyze resource requirements for a quantum computer. While there is an extensive line of work analyzing pebbling complexity in the (parallel) black pebbling game, 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 graph on $N$ nodes. This yields a separation between classical and reversible pebbling costs demonstrating that the reversibility constraint can increase cumulative pebbling costs (and space-time costs) by a multiplicative factor of $N^{(\sqrt 2 + o(1))/\sqrt{\log N}}$ --- the classical pebbling cost (space-time 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^{\sqrt{\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 constraint 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 state-of-the-art recursive pebbling techniques of Alwen et al. (EUROCRYPT 2017) can be converted into a recursive reversible pebbling attack without any asymptotic increases in pebbling costs. Finally, we extend a result of Blocki et al. (ITCS 2020) to show that it is Unique Games hard to approximate the reversible 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 et 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 identified 4 papers (from Eurocrypt, DCC, ToSC and ePrint) that follow on the results 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 Asiacrypt 2014. We apply these to the aforementioned papers and provide patched versions of their attacks. The main consequence is an increase in the memory complexity. We show that in many cases (a notable exception being quantum impossible differentials) it is possible to recover the numeric estimates of the flawed 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 tracing scheme where the sizes of public keys, secret keys, and ciphertexts are independent of the number of users. Prior constructions from pairings had size $\Omega(N^{1/3})$. An additional consequence of our techniques is general result showing that attribute-based encryption for circuits generically implies 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 through a degree $2$ isogeny $\phi$. We call the resulting formulas half differential additions: from the knowledge of $\phi(P), \phi(Q)$ and $P-Q$, the half differential 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 half 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 Montgomery 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=\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$ by bit, for a normalized point.

In the appendix, we extend our approach to higher dimensional ladders in theta coordinates or twisted theta coordinates. In dimension~$2$, after a precomputation step which depends on the base point~$P$, our half ladder only costs $7M + 4S+3m_0$, compared to $10M+9S+6m_0$ for the standard ladder.

## 2024/1591

* Title: MPC-in-the-Head Framework without Repetition and its Applications to the Lattice-based Cryptography
* Authors: Weihao Bai, Long Chen, Qianwen Gao, Zhenfeng Zhang
* [Permalink](https://eprint.iacr.org/2024/1591)
* [Download](https://eprint.iacr.org/2024/1591.pdf)

### Abstract

The MPC-in-the-Head framework has been pro-
posed as a solution for Non-Interactive Zero-Knowledge Arguments of Knowledge (NIZKAoK) due to its efficient proof generation. However, most existing NIZKAoK constructions using this approach require multiple MPC evaluations to achieve negligible soundness error, resulting in proof size and time that are asymptotically at least λ times the size of the circuit of the NP relation.. In this paper, we propose a novel method to eliminate the need for repeated MPC evaluations, resulting in a NIZKAoK protocol for any NP relation that we call Diet. The proof size and time of Diet are asymptotically only polylogarithmic with respect to the size of the circuit C of the NP relation but are independent of the security parameter λ. Hence, both the proof size and time can be significantly reduced.

Moreover, Diet offers promising concrete efficiency for proving Learning With Errors (LWE) problems and its variants. Our solution provides significant advantages over other schemes in terms of both proof size and proof time, when considering both factors together. Specifically, Diet is a promising method for proving knowledge of secret keys for lattice-based key encapsulation mechanisms (KEMs) such as Frodo and Kyber, offering a practical solution to future post-quantum certificate management. For Kyber 512, our implementation achieves an online proof size of 83.65 kilobytes (KB) with a preprocessing overhead of 152.02KB. The implementation is highly efficient, with an online proof time of only 0.68 seconds and a preprocessing time of 0.81 seconds. Notably, our approach provides the first reported implementation of proving knowledge of secret keys for Kyber 512 using post-quantum primitives-based zero-knowledge proofs.

## 2024/1595

* Title: DeepFold: Efficient Multilinear Polynomial Commitment from Reed-Solomon Code and Its Application to Zero-knowledge Proofs
* Authors: Yanpei Guo, Xuanming Liu, Kexi Huang, Wenjie Qu, Tianyang Tao, Jiaheng Zhang
* [Permalink](https://eprint.iacr.org/2024/1595)
* [Download](https://eprint.iacr.org/2024/1595.pdf)

### Abstract

This work presents Deepfold, a novel multilinear polynomial commitment scheme (PCS) based on Reed-Solomon code that offers optimal prover time and a more concise proof size. For the first time, Deepfold adapts the FRI-based multilinear PCS to the list decoding radius setting, requiring significantly fewer query repetitions and thereby achieving a 3× reduction in proof size compared to Basefold (Crypto'24), while preserving its advantages in prover time. Compared with PolyFRIM (USENIX Security'24), Deepfold achieves a 2× improvement in prover time, verifier time, and proof size. Another contribution of this work is a batch evaluation scheme, which enables the FRI-based multilinear PCS to handle polynomials encoded from inputs of arbitrary length without additional padding overhead.

Our scheme has broad applications in zk-SNARKs, since PCS is a key component in modern zk-SNARK constructions. For example, when replacing the PCS component of Virgo (S&P'20) with Deepfold, our scheme achieves a 2.5× faster prover time when proving the knowledge of a Merkle tree with 256 leaves, while maintaining the similar proof size. When replacing the PCS component of HyperPlonk (Eurocrypt'23) with Deepfold, our scheme has about 3.6× faster prover time. Additionally, when applying our arbitrary length input commitment to verifiable matrix multiplications for matrices of size 1200×768 and 768×2304, which are actual use cases in GPT-2 model, the performance showcases a
2.4× reduction in prover time compared to previous approaches.

## 2024/1596

* Title: Secret Sharing with Publicly Verifiable Deletion
* Authors: Jonathan Katz, Ben Sela
* [Permalink](https://eprint.iacr.org/2024/1596)
* [Download](https://eprint.iacr.org/2024/1596.pdf)

### Abstract

Certified deletion, an inherently quantum capability, allows a party holding a quantum state to prove that they have deleted the information contained in that state. Bartusek and Raizes recently studied certified deletion in the context of secret sharing schemes, and showed constructions with privately verifiable proofs of deletion that can be verified only by the dealer who generated the shares. We give two constructions of secret sharing schemes with publicly verifiable certified deletion. Our first construction is based on the post-quantum security of the LWE problem, and each share requires a number of qubits that is linear in the size of an underlying classical secret sharing scheme for the same set of authorized parties. Our second construction is based on a more general assumption—the existence of post quantum one-way functions— but requires an asymptotically larger number of qubits relative to the share size of the underlying classical scheme.

## 2024/1597

* Title: An undetectable watermark for generative image models
* Authors: Sam Gunn, Xuandong Zhao, Dawn Song
* [Permalink](https://eprint.iacr.org/2024/1597)
* [Download](https://eprint.iacr.org/2024/1597.pdf)

### Abstract

We present the first undetectable watermarking scheme for generative image models. Undetectability ensures that no efficient adversary can distinguish between watermarked and un-watermarked images, even after making many adaptive queries. In particular, an undetectable watermark does not degrade image quality under any efficiently computable metric. Our scheme works by selecting the initial latents of a diffusion model using a pseudorandom error-correcting code (Christ and Gunn, 2024), a strategy which guarantees undetectability and robustness.

We experimentally demonstrate that our watermarks are quality-preserving and robust using Stable Diffusion 2.1. Our experiments verify that, in contrast to every prior scheme we tested, our watermark does not degrade image quality. Our experiments also demonstrate robustness: existing watermark removal attacks fail to remove our watermark from images without significantly degrading the quality of the images. Finally, we find that we can robustly encode 512 bits in our watermark, and up to 2500 bits when the images are not subjected to watermark removal attacks. Our code is available at https://github.com/XuandongZhao/PRC-Watermark.

## 2024/1598

* Title: On the security of the initial tropical Stickel protocol and its modification based on Linde-de la Puente matrices
* Authors: Sulaiman Alhussaini, Serge˘ı Sergeev
* [Permalink](https://eprint.iacr.org/2024/1598)
* [Download](https://eprint.iacr.org/2024/1598.pdf)

### Abstract

Recently, a more efficient attack on the initial tropical Stickel protocol has been proposed, different from the previously known Kotov-Ushakov attack, yet equally guaranteed to succeed. Given that the Stickel protocol can be implemented in various ways, such as utilizing platforms beyond the tropical semiring or employing alternative commutative matrix ``classes'' instead of polynomials, we firstly explore the generalizability of this new attack across different implementations of the Stickel protocol. We then conduct a comprehensive security analysis of a tropical variant that successfully resists this new attack, namely the Stickel protocol based on Linde-de la Puente (LdlP) matrices. Additionally, we extend the concept of LdlP matrices beyond the tropical semiring, generalizing it to a broader class of semirings.

## 2024/1599

* Title: Simplified PIR and CDS Protocols and Improved Linear Secret-Sharing Schemes
* Authors: Bar Alon, Amos Beimel, Or Lasri
* [Permalink](https://eprint.iacr.org/2024/1599)
* [Download](https://eprint.iacr.org/2024/1599.pdf)

### Abstract

We consider 3 related cryptographic primitives, private information retrieval (PIR) protocols, conditional disclosure of secrets (CDS) protocols, and secret-sharing schemes; these primitives have many applications in cryptography. We study these primitives requiring information-theoretic security. The complexity of these primitives has been dramatically improved in the last few years are they are closely related, i.e., the the 2-server PIR protocol of Dvir and Gopi (J. ACM 2016) was transformed to construct the CDS protocols of Liu, Vaikuntanathan, and Wee (CRYPTO 2017, Eurocrypt 2018) and these CDS protocols are the main ingredient in the construction of the best known secret-sharing schemes.
To date, the messages size required in PIR and CDS protocols and the share size required in secret-sharing schemes is not understood and there are big gaps between their upper bounds and lower bounds. The goal of this paper is to try to better understand the upper bounds by simplifying current constructions and improving their complexity.
We obtain the following two independent results:
   - We simplify, abstract, and generalize the 2-server PIR protocol of
   Dvir and Gopi (J. ACM 2016) and the 2-server and multi-server
   CDS protocols of Liu et al. (CRYPTO 2017, Eurocrypt 2018) and
   Beimel, Farr`as, and Lasri (TCC 2023). This is done by considering
   a new variant of matching vectors and by using a general share
   conversion. In addition to simplifying previous protocols, our
   protocols can use matching vectors over any $m$ that is product
   of two distinct primes.
   Our construction does not improve the communication
   complexity of PIR and CDS protocols; however, construction of
   better matching vectors over any $m$ that is product of
   two distinct primes will improve their communication complexity.

- In many applications of secret-sharing schemes it is important that
   the scheme is linear, e.g., by using the fact that parties can locally
   add shares of two secrets and obtain shares of the sum of the
   secrets. We provide a construction of linear secret-sharing
   schemes for $n$-party access structures with improved share size
   of $2^{0.7563n}$. Previously, the best share size for linear secret-
   sharing schemes was $2^{0.7576n}$ and it is known that for most
   $n$-party access structures the shares size is at least $2^{0.5n}$..
   This results is achieved by a reduction to unbalanced CDS
   protocols (compared to balanced CDS protocols in previous
   constructions).

## 2024/1600

* Title: Pacmann: Efficient Private Approximate Nearest Neighbor Search
* Authors: Mingxun Zhou, Elaine Shi, Giulia Fanti
* [Permalink](https://eprint.iacr.org/2024/1600)
* [Download](https://eprint.iacr.org/2024/1600.pdf)

### Abstract

We propose a new private Approximate Nearest Neighbor (ANN) search scheme named Pacmann that allows a client to perform ANN search in a vector database without revealing the query vector to the server. Unlike prior constructions that run encrypted search on the server side, Pacmann carefully offloads limited computation and storage to the client, no longer requiring computationally-intensive cryptographic techniques. Specifically, clients run a graph-based ANN search, where in each hop on the graph, the client privately retrieves local graph information from the server. To make this efficient, we combine two ideas: (1) we adapt a leading graph-based ANN search algorithm to be compatible with private information retrieval (PIR) for subgraph retrieval; (2) we use a recent class of PIR schemes that trade offline preprocessing for online computational efficiency. Pacmann achieves significantly better search quality than the state-of-the-art private ANN search schemes, showing up to 2.5$\times$ better search accuracy on real-world datasets than prior work and reaching 90\% quality of a state-of-the-art non-private ANN algorithm. Moreover on large datasets with up to 100 million vectors, Pacmann shows better scalability than prior private ANN schemes
with up to 2.6$\times$ reduction in computation time and 1.3$\times$ reduction in overall latency.

## 2024/1601

* Title: Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement
* Authors: Daniel Collins, Yuval Efron, Jovan Komatovic
* [Permalink](https://eprint.iacr.org/2024/1601)
* [Download](https://eprint.iacr.org/2024/1601.pdf)

### Abstract

It is well known that a trusted setup allows one to solve the Byzantine agreement problem in the presence of $t<n/2$ corruptions, bypassing the setup-free $t<n/3$ barrier. Alas, the overwhelming majority of protocols in the literature have the caveat that their security crucially hinges on the security of the cryptography and setup, to the point where if the cryptography is broken, even a single corrupted party can violate the security of the protocol. Thus these protocols provide higher corruption resilience ($n/2$ instead of $n/3$) for the price of increased assumptions. Is this trade-off necessary?

We further the study of crypto-agnostic Byzantine agreement among $n$ parties that answers this question in the negative. Specifically, let $t_s$ and $t_i$ denote two parameters such that (1) $2t_i + t_s < n$, and (2) $t_i \leq t_s < n/2$. Crypto-agnostic Byzantine agreement ensures agreement among honest parties if (1) the adversary is computationally bounded and corrupts up to $t_s$ parties, or (2) the adversary is computationally unbounded and corrupts up to $t_i$ parties, and is moreover given all secrets of all parties established during the setup. We propose a compiler that transforms any pair of resilience-optimal Byzantine agreement protocols in the authenticated and information-theoretic setting into one that is crypto-agnostic. Our compiler has several attractive qualities, including using only $O(\lambda n^2)$ bits over the two underlying Byzantine agreement protocols, and preserving round and communication complexity in the authenticated setting. In particular, our results improve the state-of-the-art in bit complexity by at least two factors of $n$ and provide either early stopping (deterministic) or expected constant round complexity (randomized). We therefore provide fallback security for authenticated Byzantine agreement for free for $t_i \leq n/4$.

## 2024/1602

* Title: Cryptography and Collective Power
* Authors: Leah Namisa Rosenbloom
* [Permalink](https://eprint.iacr.org/2024/1602)
* [Download](https://eprint.iacr.org/2024/1602.pdf)

### Abstract

This paper extends the dialogue of "The Moral Character of Cryptographic Work" (Rogaway, 2015) and "Crypto for the People" (Kamara, 2020) by examining the relationship between cryptography and collective power. In particular, it considers cryptography in the context of grassroots organizing—a process by which marginalized people build collective power toward effecting systemic change—and illustrates the ways in which cryptography has both helped and hindered organizing efforts. Based on the synthesis of dozens of qualitative studies, scholarly critiques, and historical artifacts, this work introduces a paradigm shift for cryptographic protocol design—general principles and recommendations for building cryptography to address the lived needs and experiences of marginalized people. Finally, it calls for abolition cryptography: cryptographic theories and practices which dismantle harmful systems and replace them with systems that sustain human lives and livelihoods.

## 2024/1603

* Title: Boosting SNARKs and Rate-1 Barrier in Arguments of Knowledge
* Authors: Jiaqi Cheng, Rishab Goyal
* [Permalink](https://eprint.iacr.org/2024/1603)
* [Download](https://eprint.iacr.org/2024/1603.pdf)

### Abstract

We design a generic compiler to boost any non-trivial succinct non-interactive argument of knowledge (SNARK) to full succinctness. Our results come in two flavors:

For any constant $\epsilon > 0$, any SNARK with proof size $|\pi| < \frac{|\omega|}{\lambda^\epsilon} + \mathsf{poly}(\lambda, |x|)$ can be upgraded to a fully succinct SNARK, where all system parameters (such as proof/CRS sizes and setup/verifier run-times) grow as fixed polynomials in $\lambda$, independent of witness size.

Under an additional assumption that the underlying SNARK has as an \emph{efficient} knowledge extractor, we further improve our result to upgrade any non-trivial SNARK. For example, we show how to design fully succinct SNARKs from SNARKs with proofs of length $|\omega| - \Omega(\lambda)$, or $\frac{|\omega|}{1 + \epsilon} + \mathsf{poly}(\lambda, |x|)$, any constant $\epsilon > 0$.

Our result reduces the long-standing challenge of designing fully succinct SNARKs to designing \emph{arguments of knowledge that beat the trivial construction}. It also establishes optimality of rate-1 arguments of knowledge (such as NIZKs [Gentry-Groth-Ishai-Peikert-Sahai-Smith; JoC'15] and BARGs [Devadas-Goyal-Kalai-Vaikuntanathan, Paneth-Pass; FOCS'22]), and suggests any further improvement is tantamount to designing fully succinct SNARKs, thus requires bypassing established black-box barriers [Gentry-Wichs; STOC'11].

## 2024/1604

* Title: Predicting truncated multiple matrix congruential generators with unknown parameters
* Authors: Changcun Wang, Zhaopeng Dai
* [Permalink](https://eprint.iacr.org/2024/1604)
* [Download](https://eprint.iacr.org/2024/1604.pdf)

### Abstract

Multiple Matrix congruential generators is an important class of pseudorandom number generators. This paper studies the predictability of a class of truncated multiple matrix congruential generators with unknown parameters. Given a few truncated digits of high-order bits or low-order bits output by a multiple matrix congruential generator, we give a method based on lattice reduction to recover the parameters and the initial state of the generator.

## 2024/1605

* Title: Nebula: Efficient read-write memory and switchboard circuits for folding schemes
* Authors: Arasu Arun, Srinath Setty
* [Permalink](https://eprint.iacr.org/2024/1605)
* [Download](https://eprint.iacr.org/2024/1605.pdf)

### Abstract

Folding schemes enable prover-efficient incrementally verifiable computation (IVC), where a proof is generated step-by-step, resulting in a space-efficient prover that naturally supports continuations. These attributes make them a promising choice for proving long-running machine executions (popularly, "zkVMs"). A major problem is designing an efficient read-write memory. Another challenge is overheads incurred by unused machine instructions when incrementally proving a program execution step.

Nebula addresses these with new techniques that can paired with modern folding schemes. First, we introduce commitment-carrying IVC, where a proof carries an incremental commitment to the prover’s non-deterministic advice provided at different steps. Second, we show how this unlocks efficient read-write memory (which implies indexed lookups) with a cost-profile identical to that of non-recursive arguments. Third, we provide a new universal "switchboard" circuit construction that combines circuits of different instructions such that one can "turn off" uninvoked circuit elements and constraints, offering a new way to achieve pay-per-use prover costs.

We implement a prototype of a Nebula-based zkVM for the Ethereum virtual machine (EVM). We find that Nebula’s techniques qualitatively provide a $30\times$ smaller constraint system to represent the EVM over standard memory-checking techniques, and lead to over $260\times$ faster proof generation for the standard ERC20 token transfer transaction.

## 2024/1606

* Title: NeutronNova: Folding everything that reduces to zero-check
* Authors: Abhiram Kothapalli, Srinath Setty
* [Permalink](https://eprint.iacr.org/2024/1606)
* [Download](https://eprint.iacr.org/2024/1606.pdf)

### Abstract

We introduce NeutronNova, a new folding scheme for the zero-check relation: an instance-witness pair is in the zero-check relation if a corresponding multivariate polynomial evaluates to zero for all inputs over a suitable Boolean hypercube. The folding scheme is a two-round protocol, and it internally invokes a \emph{single} round of the sum-check protocol. The folding scheme is more efficient than prior state-of-the-art schemes and directly benefits from recent improvements to the sum-check prover. The prover’s work is the cost to commit to a witness and field operations in a single round of the sum-check protocol. So, if the witness contains "small" field elements, the prover only commits to "small" field elements. The verifier’s work is a constant number of group scalar multiplications, field operations, and hash computations. Moreover, the folding scheme generalizes to fold multiple instances at once and requires only $\log{n}$ rounds of the sum-check protocol, where $n$ is the number of instances folded.

As a corollary, we provide a folding scheme for any relation R for which there is a reduction of knowledge (RoK) from $\mathcal{R}$ to one or more instance-witness pairs in the zero-check relation. Such RoKs appear implicitly in prior lookup arguments (e.g., Lasso) and high-performance zkVMs for RISC-V (e.g.., Jolt). We formalize these RoKs for several relations including indexed lookups, grand products, and CCS (which generalizes Plonkish, AIR, and R1CS). These are simple and constant round RoKs that leverage interaction to perform randomized checks on committed witness elements. Instead of proving these resulting zero-check instances as is done in prior proof systems such as Jolt, NeutronNova provides the more efficient option of continual folding of zero-check instances into a single running instance.

## 2024/1607

* Title: Tighter Proofs for PKE-to-KEM Transformation in the Quantum Random Oracle Model
* Authors: Jinrong Chen, Yi Wang, Rongmao Chen, Xinyi Huang, Wei Peng
* [Permalink](https://eprint.iacr.org/2024/1607)
* [Download](https://eprint.iacr.org/2024/1607.pdf)

### Abstract

In this work, we provide new, tighter proofs for the $T_{RH}$-transformation by Jiang et al. (ASIACRYPT 2023), which converts OW-CPA secure PKEs into KEMs with IND-1CCA security, a variant of typical IND-CCA security where only a single decapsulation query is allowed. Such KEMs are efficient and have been shown sufficient for real-world applications by Huguenin-Dumittan and Vaudenay at EUROCRYPT 2022. We reprove Jiang et al.'s $T_{RH}$-transformation in both the random oracle model (ROM) and the quantum random oracle model (QROM), for the case where the underlying PKE is rigid deterministic. In both ROM and QROM models, our reductions achieve security loss factors of $\mathcal{O}(1)$, significantly improving Jiang et al.'s results which have security loss factors of $\mathcal{O}(q)$ in the ROM and $\mathcal{O}(q^2)$ in the QROM respectively. Notably, central to our tight QROM reduction is a new tool called ''reprogram-after-measure'', which overcomes the reduction loss posed by oracle reprogramming in QROM proofs. This technique may be of independent interest and useful for achieving tight QROM proofs for other post-quantum cryptographic schemes. We remark that our results also improve the reduction tightness of the $T_{H}$-transformation (which also converts PKEs to KEMs) by Huguenin-Dumittan and Vaudenay (EUROCRYPT 2022), as Jiang et al. provided a tight reduction from $T_H$-transformation to $T_{RH}$-transformation (ASIACRYPT 2023).

## 2024/1608

* Title: Mild Asymmetric Message Franking: Illegal-Messages-Only and Retrospective Content Moderation
* Authors: Zhengan Huang, Junzuo Lai, Gongxian Zeng, Jian Weng
* [Permalink](https://eprint.iacr.org/2024/1608)
* [Download](https://eprint.iacr.org/2024/1608.pdf)

### Abstract

Many messaging platforms have integrated end-to-end (E2E) encryption into their services. This widespread adoption of E2E encryption has triggered a technical tension between user privacy and illegal content moderation. The existing solutions either support only unframeability or deniability, or they are prone to abuse (the moderator can perform content moderation for all messages, whether illegal or not), or they lack mechanisms for retrospective content moderation.

To address the above issues, we introduce a new primitive called \emph{mild asymmetric message franking} (MAMF) to establish illegal-messages-only and retrospective content moderation for messaging systems, supporting unframeability and deniability simultaneously. We provide a framework to construct MAMF, leveraging two new building blocks, which might be of independent interest.

## 2024/1609

* Title: Blaze: Fast SNARKs from Interleaved RAA Codes
* Authors: Martijn Brehm, Binyi Chen, Ben Fisch, Nicolas Resch, Ron D. Rothblum, Hadas Zeilberger
* [Permalink](https://eprint.iacr.org/2024/1609)
* [Download](https://eprint.iacr.org/2024/1609.pdf)

### Abstract

In this work we construct a new and highly efficient multilinear polynomial commitment scheme (MLPCS) over binary fields, which we call \emph{Blaze}. Polynomial commitment schemes allow a server to commit to a large polynomial and later decommit to its evaluations. Such schemes have emerged as a key component in recent efficient SNARK constructions.

Blaze has an extremely efficient prover, both asymptotically and concretely. The commitment is dominated by $8n$ field additions (i.e., XORs) and one Merkle tree computation. The evaluation proof generation is dominated by $6n$ additions and $5n$ multiplications over the field. The verifier runs in time $O_\lambda(\log^2(n))$. Concretely, for sufficiently large message sizes, the prover is faster than all prior schemes except for Brakedown (Golovnev et al., Crypto 2023), but offers significantly smaller proofs than the latter.

The scheme is obtained by combining two ingredients:

1. Building on the code-switching technique (Ron-Zewi and Rothblum, JACM 2024), we show how to compose any error-correcting code together with an interactive oracle proof of proximity (IOPP) underlying existing MLPCS constructions, into a new MLPCS. The new MLPCS inherits its proving time from the code's encoding time, and its verification complexity from the underlying MLPCS. The composition is distinctive in that it is done purely on the information-theoretic side.

2. We apply the above methodology using an extremely efficient error-correcting code known as the Repeat-Accumulate-Accumulate (RAA) code. We give new asymptotic and concrete bounds, which demonstrate that (for sufficiently large message sizes) this code has a better encoding time vs. distance tradeoff than previous linear-time encodable codes that were considered in the literature.

## 2024/1610

* Title: Secret Sharing with Snitching
* Authors: Stefan Dziembowski, Sebastian Faust, Tomasz Lizurej, Marcin Mielniczuk
* [Permalink](https://eprint.iacr.org/2024/1610)
* [Download](https://eprint.iacr.org/2024/1610.pdf)

### Abstract

We address the problem of detecting and punishing shareholder collusion in secret-sharing schemes. We do it in the recently proposed cryptographic model called individual cryptography (Dziembowski, Faust, and Lizurej, Crypto 2023), which assumes that there exist tasks that can be efficiently computed by a single machine but distributing this computation across multiple (mutually distrustful devices) is infeasible.

Within this model, we introduce a novel primitive called secret sharing with snitching (SSS), in which each attempt to illegally reconstruct the shared secret $S$ results in a proof that can be used to prove such misbehavior (and, e.g., financially penalize the cheater on a blockchain). This holds in a very strong sense, even if the shareholders attempt not to reconstruct the entire secret~$S$ but only learn some partial information about it. Our notion also captures the attacks performed using multiparty computation protocols (MPCs), i.e., those where the malicious shareholders use MPCs to compute partial information on $S$. The main idea of SSS is that any illegal reconstruction can be proven and punished, which suffices to discourage illegal secret reconstruction. Hence, our SSS scheme effectively prevents shareholders' collusion. We provide a basic definition of threshold ($t$-out-of-$n$) SSS. We then show how to construct it for $t = n$, and later, we use this construction to build an SSS scheme for an arbitrary $t$.

In order to prove the security of our construction, we introduce a generalization of the random oracle model (Bellare, Rogaway, CCS 1993), which allows modelling hash evaluations made inside MPC.

## 2024/1611

* Title: Rhombus: Fast Homomorphic Matrix-Vector Multiplication for Secure Two-Party Inference
* Authors: Jiaxing He, Kang Yang, Guofeng Tang, Zhangjie Huang, Li Lin, Changzheng Wei, Ying Yan, Wei Wang
* [Permalink](https://eprint.iacr.org/2024/1611)
* [Download](https://eprint.iacr.org/2024/1611.pdf)

### Abstract

We present $\textit{Rhombus}$, a new secure matrix-vector multiplication (MVM) protocol in the semi-honest two-party setting, which is able to be seamlessly integrated into existing privacy-preserving machine learning (PPML) frameworks and serve as the basis of secure computation in linear layers.
$\textit{Rhombus}$ adopts RLWE-based homomorphic encryption (HE) with coefficient encoding, which allows messages to be chosen from not only a field $\mathbb{F}_p$ but also a ring $\mathbb{Z}_{2^\ell}$, where the latter supports faster computation in non-linear layers. To achieve better efficiency, we develop an input-output packing technique that reduces the communication cost incurred by HE with coefficient encoding by about $21\times$, and propose a split-point picking technique that reduces the number of rotations to that sublinear in the matrix dimension. Compared to the recent protocol $\textit{HELiKs}$ by Balla and Koushanfar (CCS'23), our implementation demonstrates that $\textit{Rhombus}$ improves the whole performance of an MVM protocol by a factor of $7.4\times \sim 8\times$, and improves the end-to-end performance of secure two-party inference of ResNet50 by a factor of $4.6\times \sim 18\times$.

## 2024/1612

* Title: On Wagner's k-Tree Algorithm Over Integers
* Authors: Haoxing Lin, Prashant Nalini Vasudevan
* [Permalink](https://eprint.iacr.org/2024/1612)
* [Download](https://eprint.iacr.org/2024/1612.pdf)

### Abstract

The $k$-Tree algorithm [Wagner 02] is a non-trivial algorithm for the average-case $k$-SUM problem that has found widespread use in cryptanalysis. Its input consists of $k$ lists, each containing $n$ integers from a range of size $m$. Wagner's original heuristic analysis suggested that this algorithm succeeds with constant probability if $n \approx m^{1/(\log{k}+1)}$, and that in this case it runs in time $O(kn)$. Subsequent rigorous analysis of the algorithm [Lyubashevsky 05, Shallue 08, Joux-Kippen-Loss 24] has shown that it succeeds with high probability if the input list sizes are significantly larger than this.

We present a broader rigorous analysis of the $k$-Tree algorithm, showing upper and lower bounds on its success probability and complexity for any size of the input lists. Our results confirm Wagner's heuristic conclusions, and also give meaningful bounds for a wide range of list sizes that are not covered by existing analyses. We present analytical bounds that are asymptotically tight, as well as an efficient algorithm that computes (provably correct) bounds for a wide range of concrete parameter settings. We also do the same for the $k$-Tree algorithm over $\mathbb{Z}_m$. Finally, we present experimental evaluation of the tightness of our results.

## 2024/1613

* Title: Efficient Maliciously Secure Oblivious Exponentiations
* Authors: Carsten Baum, Jens Berlips, Walther Chen, Ivan Damgård, Kevin M. Esvelt, Leonard Foner, Dana Gretton, Martin Kysel, Ronald L. Rivest, Lawrence Roy, Francesca Sage-Ling, Adi Shamir, Vinod Vaikuntanathan, Lynn Van Hauwe, Theia Vogel, Benjamin Weinstein-Raun, Daniel Wichs, Stephen Wooster, Andrew C. Yao, Yu Yu
* [Permalink](https://eprint.iacr.org/2024/1613)
* [Download](https://eprint.iacr.org/2024/1613.pdf)

### Abstract

Oblivious Pseudorandom Functions (OPRFs) allow a client to evaluate a pseudorandom function (PRF) on her secret input based on a key that is held by a server. In the process, the client only learns the PRF output but not the key, while the server neither learns the input nor the output of the client. The arguably most popular OPRF is due to Naor, Pinkas and Reingold (Eurocrypt 2009).. It is based on an Oblivious Exponentiation by the server, with passive security under the Decisional Diffie-Hellman assumption. In this work, we strengthen the security guarantees of the NPR OPRF by protecting it against active attacks of the server. We have implemented our solution and report on the performance.

Our main result is a new batch OPRF protocol which is secure against maliciously corrupted servers, but is essentially as efficient as the semi-honest solution. More precisely, the computation (and communication) overhead is a multiplicative factor $o(1)$ as the batch size increases. The obvious solution using zero-knowledge proofs would have a constant factor overhead at best, which can be too expensive for certain deployments.

Our protocol relies on a novel version of the DDH problem, which we call the Oblivious Exponentiation Problem (OEP), and we give evidence for its hardness in the Generic Group model. We also present a variant of our maliciously secure protocol that does not rely on the OEP but nevertheless only has overhead $o(1)$ over the known semi-honest protocol. Moreover, we show that our techniques can also be used to efficiently protect threshold blind BLS signing and threshold ElGamal decryption against malicious attackers.

## 2024/1614

* Title: Related-Key Cryptanalysis of FUTURE
* Authors: Amit Jana, Smita Das, Ayantika Chatterjee, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2024/1614)
* [Download](https://eprint.iacr.org/2024/1614.pdf)

### Abstract

In Africacrypt 2022, Gupta \etal introduced a 64-bit lightweight \mds matrix-based \spn-like block cipher designed to encrypt data in a single clock cycle with minimal implementation cost, particularly when unrolled. While various attack models were discussed, the security of the cipher in the related-key setting was not addressed. In this work, we bridge this gap by conducting a security analysis of the cipher under related-key attacks using \milp(Mixed Integer Linear Programming)-based techniques. Our model enables a related-key distinguishing attack on 8 rounds of FUTURE, requiring $2^{64}$ plaintexts, $2^{63}$ \xor operations, and negligible memory. Additionally, we present a 10-round boomerang distinguisher with a probability of $2^{-45}$, leading to a distinguishing attack with $2^{46}$ plaintexts, $2^{46}$ \xor operations, and negligible memory. This result demonstrates a full break of the cipher’s 64-bit security in the related-key setting.

## 2024/1615

* Title: LeOPaRd: Towards Practical Post-Quantum Oblivious PRFs via Interactive Lattice Problems
* Authors: Muhammed F. Esgin, Ron Steinfeld, Erkan Tairi, Jie Xu
* [Permalink](https://eprint.iacr.org/2024/1615)
* [Download](https://eprint.iacr.org/2024/1615.pdf)

### Abstract

In this work, we introduce a more efficient post-quantum oblivious PRF (OPRF) design, called LeOPaRd. Our proposal is round-optimal and supports verifiability and partial obliviousness, all of which are important for practical applications. The main technical novelty of our work is a new method for computing samples of MLWE (module learning with errors) in a two-party setting. To do this, we introduce a new family of interactive lattice problems, called interactive MLWE and rounding with re-use (iMLWER-RU). We rigorously study the hardness of iMLWER-RU and reduce it (under some natural idealized setting) to a more standard MLWE-like problem where the adversary is additionally given access to a randomized MLWE PRF oracle. We believe iMLWER-RU can be of independent interest for other interactive protocols.

LeOPaRd exploits this new iMLWER-RU assumption to realize a lattice-based OPRF design without relying on heavy machinery such as noise flooding and fully homomorphic encryption used in earlier works. LeOPaRd can feature around 136 KB total communication, compared to 300+ KB in earlier works. We also identify gaps in some existing constructions and models, and propose appropriate fixes.

## 2024/1616

* Title: End-to-End Encrypted Cloud Storage in the Wild: A Broken Ecosystem
* Authors: Jonas Hofmann, Kien Tuong Truong
* [Permalink](https://eprint.iacr.org/2024/1616)
* [Download](https://eprint.iacr.org/2024/1616.pdf)

### Abstract

End-to-end encrypted cloud storage offers a way for individuals and organisations to delegate their storage needs to a third-party, while keeping control of their data using cryptographic techniques.
We conduct a cryptographic analysis of various products in the ecosystem, showing that many providers fail to provide an adequate level of security. In particular, we provide an in-depth analysis of five end-to-end encrypted cloud storage systems, namely Sync, pCloud, Icedrive, Seafile, and Tresorit, in the setting of a malicious server. These companies cumulatively have over 22 million users and are major providers in the field. We unveil severe cryptographic vulnerabilities in four of them. Our attacks invalidate the marketing claims made by the providers of these systems, showing that a malicious server can, in some cases, inject files in the encrypted storage of users, tamper with file data, and even gain direct access to the content of the files. Many of our attacks affect multiple providers in the same way, revealing common failure patterns in independent cryptographic designs.
We conclude by discussing the significance of these patterns beyond the security of the specific providers.

## 2024/1617

* Title: Algebraic Equipage for Learning with Errors in Cyclic Division Algebras
* Authors: Cong Ling, Andrew Mendelsohn
* [Permalink](https://eprint.iacr.org/2024/1617)
* [Download](https://eprint.iacr.org/2024/1617.pdf)

### Abstract

In Noncommutative Ring Learning With Errors From Cyclic Algebras, a variant of Learning with Errors from cyclic division algebras, dubbed ‘Cyclic LWE', was developed, and security reductions similar to those known for the ring and module case were given, as well as a Regev-style encryption scheme. In this work, we make a number of improvements to that work: namely, we describe methods to increase the number of cryptographically useful division algebras, demonstrate the hardness of CLWE from ideal lattices obtained from non-maximal orders, and study Learning with Rounding in cyclic division algebras.

## 2024/1618

* Title: Shaking up authenticated encryption
* Authors: Joan Daemen, Seth Hoffert, Silvia Mella, Gilles Van Assche, Ronny Van Keer
* [Permalink](https://eprint.iacr.org/2024/1618)
* [Download](https://eprint.iacr.org/2024/1618.pdf)

### Abstract

Authenticated encryption (AE) is a cryptographic mechanism that allows communicating parties to protect the confidentiality and integrity of messages exchanged over a public channel, provided they share a secret key. In this work, we present new AE schemes leveraging the SHA-3 standard functions SHAKE128 and SHAKE256, offering 128 and 256 bits of security strength, respectively, and their “Turbo” counterparts. They support session-based communication, where a ciphertext authenticates the sequence of messages since the start of the session. The chaining in the session allows decryption in segments, avoiding the need to buffer the entire deciphered cryptogram between decryption and validation. And, thanks to the collision resistance of (Turbo)SHAKE, they provide so-called CMT-4 committing security, meaning that they provide strong guarantees that a ciphertext uniquely binds to the key, plaintext and associated data. The AE schemes we propose have the unique combination of advantages that 1) their security is based on the security claim of SHAKE, that has received a large amount of public scrutiny, that 2) they make use of the standard KECCAK-p permutation that not only receives more and more dedicated hardware support, but also allows
competitive software-only implementations thanks to the TurboSHAKE instances, and that 3) they do not suffer from a 64-bit birthday bound like most AES-based schemes.

## 2024/1619

* Title: Structure-Preserving Compressing Primitives: Vector Commitments, Accumulators and Applications
* Authors: Stephan Krenn, Omid Mir, Daniel Slamanig
* [Permalink](https://eprint.iacr.org/2024/1619)
* [Download](https://eprint.iacr.org/2024/1619.pdf)

### Abstract

Compressing primitives such as accumulators and vector commitments, allow to rep- resent large data sets with some compact, ideally constant-sized value. Moreover, they support operations like proving membership or non-membership with minimal, ideally also constant- sized, storage and communication overhead.. In recent years, these primitives have found nu- merous practical applications, with many constructions based on various hardness assumptions. So far, however, it has been elusive to construct these primitives in a strictly structure-preserving setting, i.e., in a bilinear group in a way that messages, commitments and openings are all ele- ments of the two source groups. Interestingly, backed by existing impossibility results, not even conventional commitments with such constraints are known in this setting.

In this paper we investigate whether strictly structure-preserving compressing primitives can be realized. We close this gap by presenting the first strictly structure-preserving commitment that is shrinking (and in particular constant-size). We circumvent existing impossibility results by employing a more structured message space, i.e., a variant of the Diffie-Hellman message space.. Our main results are constructions of structure-preserving vector commitments (SPVC) as well as accumulators. We first discuss generic constructions and then present concrete con- structions under the Diffie-Hellman Exponent assumption. To demonstrate the usefulness of our constructions, we present various applications. Most notable, we present the first entirely prac- tical constant-size ring signature scheme in bilinear groups (i.e., the discrete logarithm setting). Concretely, using the popular BLS12-381 pairing-friendly curve, our ring signatures achieve a size of roughly 6500 bits.

## 2024/1620

* Title: Really Complex Codes with Application to STARKs
* Authors: Yuval Domb
* [Permalink](https://eprint.iacr.org/2024/1620)
* [Download](https://eprint.iacr.org/2024/1620.pdf)

### Abstract

Reed-Solomon (RS) codes [RS60], representing evaluations of univariate polynomials over distinct domains, are foundational in error correction and cryptographic protocols. Traditional RS codes leverage the Fourier domain for efficient encoding and decoding via Fast Fourier Transforms (FFT). However, in fields such as the Reals and some finite prime fields, limited root-of-unity orders restrict these methods. Recent research, particularly in the context of modern STARKs [BSBHR18b], has explored the Complex Fourier domain for constructing Real-valued RS codes, introducing novel transforms such as the Discrete Circle-Curve Transform (DCCT) for Real-to-Real transformations [HLP24]. Despite their efficiency, these transforms face limitations with high radix techniques and potentially other legacy know-hows. In this paper, we propose a construction of Real-valued RS codes utilizing the Discrete Fourier Transform (DFT) over the Complex domain. This approach leverages well-established algebraic and Fourier properties to achieve efficiency comparable to DCCT, while retaining compatibility with legacy techniques and optimizations.

## 2024/1621

* Title: PAKE Combiners and Efficient Post-Quantum Instantiations
* Authors: Julia Hesse, Michael Rosenberg
* [Permalink](https://eprint.iacr.org/2024/1621)
* [Download](https://eprint.iacr.org/2024/1621.pdf)

### Abstract

Much work has been done recently on developing password-authenticated key exchange (PAKE) mechanisms with post-quantum security. However, modern guidance recommends the use of hybrid schemes—schemes which rely on the combined hardness of a post-quantum assumption, e.g., learning with Errors (LWE), and a more traditional assumption, e.g., decisional Diffie-Hellman. To date, there is no known hybrid PAKE construction, let alone a general method for achieving such.

In this paper, we present two efficient PAKE combiners—algorithms that take two PAKEs satisfying mild assumptions, and output a third PAKE with combined security properties—and prove these combiners secure in the Universal Composability (UC) model. Our sequential combiner, instantiated with efficient existing PAKEs such as CPace (built on Diffie-Hellman-type assumptions) and CHIC[ML-KEM] (built on the Module LWE assumption), yields the first known hybrid PAKE.

## 2024/1622

* Title: A New Approach Towards Encrypted Data Sharing and Computation: Enhancing Efficiency Beyond MPC and Multi-Key FHE
* Authors: Anil Kumar Pradhan
* [Permalink](https://eprint.iacr.org/2024/1622)
* [Download](https://eprint.iacr.org/2024/1622.pdf)

### Abstract

In this paper, we introduce a novel approach to Multi-Key Fully Homomorphic Encryption (MK-FHE) that enhances both efficiency and security beyond the capabilities of traditional MK-FHE and MultiParty Computation (MPC) systems. Our method generates a unified key structure, enabling constant ciphertext size and constant execution time for encrypted computations, regardless of the number of participants involved. This approach addresses critical limitations such as ciphertext size expansion, noise accumulation, and the complexity of relinearization, which typically hinder scalability in multi-user environments. We also propose a new decryption method that simplifies decryption to a single information exchange, in contrast to traditional multi-key FHE systems that require information to be passed between all parties sequentially.

Additionally, it significantly enhances the scalability of MK-FHE systems, allowing seamless integration of additional participants without introducing performance overhead. Through theoretical analysis and practical implementation, we demonstrate the superiority of our approach in large-scale, collaborative encrypted computation scenarios, paving the way for more robust and efficient secure data processing frameworks. Further more, unlike the threshold based FHE schemes, the proposed system doesn’t require a centralised trusted third party to split and distribute the individual secret keys, instead each participant independently generates their own secret key, ensuring both security and decentralization.

## 2024/1623

* Title: General Functional Bootstrapping using CKKS
* Authors: Andreea Alexandru, Andrey Kim, Yuriy Polyakov
* [Permalink](https://eprint.iacr.org/2024/1623)
* [Download](https://eprint.iacr.org/2024/1623.pdf)

### Abstract

The Ducas-Micciancio (DM/FHEW) and Chilotti-Gama-Georgieva-Izabachène (CGGI/TFHE) cryptosystems provide a general privacy-preserving computation capability. These fully homomorphic encryption (FHE) cryptosystems can evaluate an arbitrary function expressed as a general look-up table (LUT) via the method of functional bootstrapping (also known as programmable bootstrapping). The main limitation of DM/CGGI functional bootstrapping is its efficiency because this procedure has to bootstrap every encrypted number separately. A different bootstrapping approach, based on the Cheon-Kim-Kim-Song (CKKS) FHE scheme, can achieve much smaller amortized time due to its ability to bootstrap many thousands of numbers at once. However, CKKS does not currently provide a functional bootstrapping capability that can evaluate a general LUT. An open research question is whether such capability can be efficiently constructed. We give a positive answer to this question by proposing and implementing a general functional bootstrapping method based on CKKS-style bootstrapping. We devise a theoretical toolkit for evaluating an arbitrary function using the theory of trigonometric Hermite interpolations, which provides control over noise reduction during functional bootstrapping. Our experimental results for 8-bit LUT evaluation show that the proposed method achieves the amortized time of 0.75 milliseconds, which is three orders of magnitude faster than the DM/CGGI approach and 6.6x faster than (a more restrictive) amortized functional bootstrapping method based on the Brakerski/Fan-Vercauteren (BFV) FHE scheme.

## 2024/1624

* Title: Double-Matrix: Complete Diffusion in a Single Round with (small) MDS Matrices
* Authors: Jorge Nakahara Jr
* [Permalink](https://eprint.iacr.org/2024/1624)
* [Download](https://eprint.iacr.org/2024/1624.pdf)

### Abstract

This paper describes a simple idea to improve (text) diffusion in block ciphers that use MDS codes but that take more than
a single round to achieve full (text) diffusion. The Rijndael cipher family is used as an example since it comprises ciphers
with different state sizes.
A drawback of the new approach is the additional computational cost, but it is competitive compared to large MDS matrices
used in the Khazad and Kuznyechik ciphers.

## 2024/1625

* Title: On the Tight Security of the Double Ratchet
* Authors: Daniel Collins, Doreen Riepel, Si An Oliver Tran
* [Permalink](https://eprint.iacr.org/2024/1625)
* [Download](https://eprint.iacr.org/2024/1625.pdf)

### Abstract

The Signal Protocol is a two-party secure messaging protocol used in applications such as Signal, WhatsApp, Google Messages and Facebook Messenger and is used by billions daily. It consists of two core components, one of which is the Double Ratchet protocol that has been the subject of a line of work that aims to understand and formalise exactly what security it provides. Existing models capture strong guarantees including resilience to state exposure in both forward security (protecting past secrets) and post-compromise security (restoring security), adaptive state corruptions, message injections and out-of-order message delivery. Due to this complexity, prior work has failed to provide security guarantees that do not degrade in the number of interactions, even in the single-session setting.

Given the ubiquity of the Double Ratchet in practice, we explore tight security bounds for the Double Ratchet in the multi-session setting. To this end, we revisit the modelling of Alwen, Coretti and Dodis (EUROCRYPT 2019) who decompose the protocol into modular, abstract components, notably continuous key agreement (CKA) and forward-secure AEAD (FS-AEAD). To enable a tight security proof, we propose a CKA security model that provides one-way security under key checking attacks. We show that multi-session security of the Double Ratchet can be tightly reduced to the multi-session security of CKA and FS-AEAD, capturing the same strong security guarantees as Alwen et al.

Our result improves upon the bounds of Alwen et al. in the random oracle model. Even so, we are unable to provide a completely tight proof for the Double Ratchet based on standard Diffie-Hellman assumptions, and we conjecture it is not possible. We thus go a step further and analyse CKA based on key encapsulation mechanisms (KEMs). In contrast to previous works, our new analysis allows for tight constructions based on the DDH and post-quantum assumptions.

## 2024/1626

* Title: Faster Proofs and VRFs from Isogenies
* Authors: Shai Levin, Robi Pedersen
* [Permalink](https://eprint.iacr.org/2024/1626)
* [Download](https://eprint.iacr.org/2024/1626.pdf)

### Abstract

We improve recent generic proof systems for isogeny knowledge by Cong, Lai, Levin [26] based on circuit satisfiability, by using radical isogeny descriptions [19, 20] to prove a path in the underlying isogeny graph. We then present a new generic construction for a verifiable random function (VRF) based on a one-more type hardness assumption and zero-knowledge proofs. We argue that isogenies fit the constraints of our construction and instantiate the VRF with a CGL walk [22] and our new proofs. As a different contribution, we also propose a new VRF in the effective group action description of isogenies from [1]. Our protocol takes a novel approach based on the polynomial-in-the-exponent technique first described in [36], but without the need of a trusted setup or heavy preprocessing. We compare our protocols to the current state-of-the-art isogeny VRFs by Leroux [53] and Lai [52], with a particular emphasis on computational efficiency.

## 2024/1627

* Title: Lollipops of pairing-friendly elliptic curves for composition of proof systems
* Authors: Craig Costello, Gaurish Korpal
* [Permalink](https://eprint.iacr.org/2024/1627)
* [Download](https://eprint.iacr.org/2024/1627.pdf)

### Abstract

We construct lollipops of pairing-friendly elliptic curves, which combine pairing-friendly chains with pairing-friendly cycles. The cycles inside these lollipops allow for unbounded levels of recursive pairing-based proof system composition, while the chains leading into these cycles alleviate a significant drawback of using cycles on their own: the only known cycles of pairing-friendly elliptic curves force the initial part of the circuit to be arithmetised on suboptimal (much larger) finite fields. Lollipops allow this arithmetisation to instead be performed over finite fields of an optimal size, while preserving the unbounded recursion afforded by the cycle.

The notion of pairing-friendly lollipops itself is not novel. In 2019 the Coda + Dekrypt ``SNARK challenge'' offered a $20k USD prize for the best lollipop construction, but to our knowledge no lollipops were submitted to the challenge or have since emerged in the literature. This paper therefore gives the first construction of such lollipops.

The main technical ingredient we use is a new way of instantiating pairing-friendly cycles over supersingular curves whose characteristics correspond to those in MNT cycles. The vast majority of MNT cycles that exist are unable to be instantiated in practice, because the corresponding CM discriminant is too large to construct the MNT curves explicitly. Our method can be viewed as a workaround that allows cycles to be instantiated regardless of the CM discriminant of the MNT curves.

## 2024/1628

* Title: Glacius: Threshold Schnorr Signatures from DDH with Full Adaptive Security
* Authors: Renas Bacho, Sourav Das, Julian Loss, Ling Ren
* [Permalink](https://eprint.iacr.org/2024/1628)
* [Download](https://eprint.iacr.org/2024/1628.pdf)

### Abstract

Threshold signatures are one of the most important cryptographic primitives in distributed systems. The threshold Schnorr signature scheme, an efficient and pairing-free scheme, is a popular choice and is included in NIST's standards and recent call for threshold cryptography. Despite its importance, most threshold Schnorr signature schemes assume a static adversary in their security proof. A recent scheme proposed by Katsumata et al. (Crypto 2024) addresses this issue. However, it requires linear-sized signing keys and lacks the identifiable abort property, which makes it vulnerable to denial-of-service attacks. Other schemes with adaptive security either have reduced corruption thresholds or rely on non-standard assumptions such as the algebraic group model (AGM) or hardness of the algebraic one-more discrete logarithm (AOMDL) problem.

In this work, we present Glacius, the first threshold Schnorr signature scheme that overcomes all these issues. Glacius is adaptively secure based on the hardness of decisional Diffie-Hellman (DDH) in the random oracle model (ROM), and it supports a full corruption threshold $t<n$, where $n$ is the total number of signers and $t$ is the signing threshold. Additionally, Glacius provides constant-sized signing keys and identifiable abort, meaning signers can detect misbehavior. We also give a formal game-based definition of identifiable abort, addressing certain subtle issues present in existing definitions, which may be of independent interest.

## 2024/1629

* Title: Efficient Key-Switching for Word-Type FHE and GPU Acceleration
* Authors: Shutong Jin, Zhen Gu, Guangyan Li, Donglong Chen, Çetin Kaya Koç, Ray C. C. Cheung, Wangchen Dai
* [Permalink](https://eprint.iacr.org/2024/1629)
* [Download](https://eprint.iacr.org/2024/1629.pdf)

### Abstract

Speed efficiency, memory optimization, and quantum resistance are essential for safeguarding the performance and security of cloud computing environments. Fully Homomorphic Encryption (FHE) addresses this need by enabling computations on encrypted data without requiring decryption, thereby maintaining data privacy. Additionally, lattice-based FHE is quantum secure, providing defense against potential quantum computer attacks. However, the performance of current FHE schemes remains unsatisfactory, largely because of the length of the operands and the computational expense associated with several resource-intensive operations. Among these operations, key-switching is one of the most demanding processes because it involves complex arithmetic operations necessary to conduct computations in a larger cyclotomic ring.

In this research, we introduce a novel algorithm that achieves linear complexity in the Number Theoretic Transform (NTT) for key-switching. This algorithm offers efficiency comparable to the state-of-the-art while being significantly simpler and consumes less GPU memory. Notably, it reduces space consumption by up to 95\%, making it highly friendly for GPU memory. By optimizing GPU performance, our implementation achieves up to a 2.0$\times$ speedup compared to both the baseline approach and the current state-of-the-art methods. This algorithm effectively balances simplicity and performance, thereby enhancing cryptographic computations on modern hardware platforms and paving the way to more practical and efficient FHE implementations in cloud computing environments.

## 2024/1630

* Title: Hybrid Password Authentication Key Exchange in the UC Framework
* Authors: You Lyu, Shengli Liu
* [Permalink](https://eprint.iacr.org/2024/1630)
* [Download](https://eprint.iacr.org/2024/1630.pdf)

### Abstract

A hybrid cryptosystem combines two systems that fulfill the same cryptographic functionality, and its security enjoys the security of the harder one. There are many proposals for hybrid public-key encryption (hybrid PKE), hybrid signature (hybrid SIG) and hybrid authenticated key exchange (hybrid AKE). In this paper, we fill the blank of Hybrid Password Authentication Key Exchange (hybrid PAKE).

For constructing hybrid PAKE, we first define an important class of PAKE -- full DH-type PAKE, from which we abstract sufficient properties to achieve UC security. Our full DH-type PAKE framework unifies lots of PAKE schemes like SPAKE2, TBPEKE, (Crs)X-GA-PAKE, and summarizes their common features for UC security.

Stepping from full DH-type PAKE, we propose two generic approaches to hybrid PAKE, parallel composition and serial composition.
-- We propose a generic construction of hybrid PAKE via parallel composition and prove that the hybrid PAKE by composing DH-type PAKEs in parallel is a full DH-type PAKE and hence achieves UC security, as long as one underlying DH-type PAKE is a full DH-type.
-- We propose a generic construction of hybrid PAKE via serial composition, and prove that the hybrid PAKE by composing a DH-type PAKE and another PAKE in serial achieves UC security, if either the DH-type PAKE is a full DH-type or the other PAKE has UC security and the DH-type PAKE only has some statistical properties.

Our generic constructions of hybrid PAKE result in a variety of hybrid PAKE schemes enjoying different nice features, like round-optimal, high efficiency, or UC security in quantum random oracle model (QROM).

## 2024/1631

* Title: Sparrow: Space-Efficient zkSNARK for Data-Parallel Circuits and Applications to Zero-Knowledge Decision Trees
* Authors: Christodoulos Pappas, Dimitrios Papadopoulos
* [Permalink](https://eprint.iacr.org/2024/1631)
* [Download](https://eprint.iacr.org/2024/1631.pdf)

### Abstract

Space-efficient SNARKs aim to reduce the prover's space overhead which is one the main obstacles for deploying SNARKs in practice, as it can be prohibitively large (e.g., orders of magnitude larger than natively performing the computation). In this work, we propose Sparrow, a novel space-efficient zero-knowledge SNARK for data-parallel arithmetic circuits with two attractive features: (i) it is the first space-efficient scheme where, for a given field, the prover overhead increases with a multiplicative sublogarithmic factor as the circuit size increases, and (ii) compared to prior space-efficient SNARKs that work for arbitrary arithmetic circuits, it achieves prover space asymptotically smaller than the circuit size itself. Our key building block is a novel space-efficient sumcheck argument with improved prover time which may be of independent interest. Our experimental results for three use cases (arbitrary data parallel circuits, multiplication trees, batch SHA256 hashing) indicate Sparrow outperforms the prior state-of-the-art space-efficient SNARK for arithmetic circuits Gemini (Bootle et al., EUROCRYPT'22) by $3.2$-$28.7\times$ in total prover space and $3.1$-$11.3\times$ in prover time. We then use Sparrow to build zero-knowledge proofs of tree training and prediction, relying on its space efficiency to scale to large datasets and forests of multiple trees. Compared to a (non-space-efficient) optimal-time SNARK based on the GKR protocol, we observe prover space reduction of $16$-$240\times$ for tree training while maintaining essentially the same prover and verifier times and proof size. Even more interestingly, our prover requires comparable space to natively performing the underlying computation. E.g., for a $400$MB dataset, our prover only needs $1.4\times$ more space than the native computation.

## 2024/1632

* Title: Fully Secure Searchable Encryption from PRFs, Pairings, and Lattices
* Authors: Hirotomo Shinoki, Hisayoshi Sato, Masayuki Yoshino
* [Permalink](https://eprint.iacr.org/2024/1632)
* [Download](https://eprint.iacr.org/2024/1632.pdf)

### Abstract

Searchable encryption is a cryptographic primitive that allows us to perform searches on encrypted data. Searchable encryption schemes require that ciphertexts do not leak information about keywords. However, most of the existing schemes do not achieve the security notion that trapdoors do not leak information. Shen et al. (TCC 2009) proposed a security notion called full security, which includes both ciphertext privacy and trapdoor privacy, but there are few fully secure constructions. Full security is defined for the secret key settings since it is known that public key schemes cannot achieve the trapdoor privacy in principle.
In this paper, we construct a query-bounded fully secure scheme from pseudorandom functions. In addition, we propose two types of efficient (unbounded) fully secure schemes, each of which is based on bilinear groups and lattices respectively. We then analyze the existing constructions. First, we simplify the Cheng et al. scheme (Information Sciences 2023) and prove its security. This scheme had not been proved to be secure. Second, we show that the Li-Boyen pairing-based scheme (IACR CiC 2024) does not achieve the trapdoor privacy, not as claimed.

## 2024/1633

* Title: Efficient Boolean-to-Arithmetic Mask Conversion in Hardware
* Authors: Aein Rezaei Shahmirzadi, Michael Hutter
* [Permalink](https://eprint.iacr.org/2024/1633)
* [Download](https://eprint.iacr.org/2024/1633.pdf)

### Abstract

Masking schemes are key in thwarting side-channel attacks due to their robust theoretical foundation. Transitioning from Boolean to arithmetic (B2A) masking is a necessary step in various cryptography schemes, including hash functions, ARX-based ciphers, and lattice-based cryptography. While there exists a significant body of research focusing on B2A software implementations, studies pertaining to hardware implementations are quite limited, with the majority dedicated solely to creating efficient Boolean masked adders. In this paper, we present first- and second-order secure hardware implementations to perform B2A mask conversion efficiently without using masked adder structures. We first introduce a first-order secure low-latency gadget that executes a B2A2k in a single cycle. Furthermore, we propose a second-order secure B2A2k gadget that has a latency of only 4 clock cycles. Both gadgets are independent of the input word size k. We then show how these new primitives lead to improved B2Aq hardware implementations that perform a B2A mask conversion of integers modulo an arbitrary number. Our results show that our new gadgets outperform comparable solutions by more than a magnitude in terms of resource requirements and are at least 3 times faster in terms of latency and throughput. All gadgets have been formally verified and proven secure in the glitch-robust PINI security model. We additionally confirm the security of our gadgets on an FPGA platform using practical TVLA tests.

## 2024/1634

* Title: On Constructing Pseudorandom Involutions: Feistel variants using a single round function
* Authors: Chun Guo, Meiqin Wang, Weijia Wang
* [Permalink](https://eprint.iacr.org/2024/1634)
* [Download](https://eprint.iacr.org/2024/1634.pdf)

### Abstract

An involution is a permutation that is the inverse of itself. Involutions have attracted plenty attentions in cryptographic community due to their advantage regarding hardware implementations. In this paper, we reconsider constructing {\it pseudorandom involutions}. We demonstrate two constructions.

First, the 4-round Feistel network {\it using the same random function (Feistel-SF) in every round} is a pseudorandom involution. This shows the Feistel-SF construction still provides non-trivial cryptographic strength. To complement, we also show insecurity of 3-round Feistel-SF by exhibiting an attack.

Second, a ``mirrored'' variant of the Naor-Reingold construction with component reusing yields a pseudorandom involution.

## 2024/1635

* Title: RPO-M31 and XHash-M31: Efficient Hash Functions for Circle STARKs
* Authors: Tomer Ashur, Sundas Tariq
* [Permalink](https://eprint.iacr.org/2024/1635)
* [Download](https://eprint.iacr.org/2024/1635.pdf)

### Abstract

We present two new arithmetization oriented hash functions based on RPO [Ashur, kindi, Meier, Szepieniec, Threadbare; ePrint 2022/1577] and XHash-12 [Ashur, Bhati, Kindi, Mahzoun, Perrin; ePrint 2023/1045] adapted for $p=2^{31}-1$ and ready to use in Circle STARKs [Habock, Levit, Papini; ePrint 2024/278].

## 2024/1636

* Title: Quantum State Group Actions
* Authors: Saachi Mutreja, Mark Zhandry
* [Permalink](https://eprint.iacr.org/2024/1636)
* [Download](https://eprint.iacr.org/2024/1636.pdf)

### Abstract

Cryptographic group actions are a leading contender for post-quantum cryptography, and have also been used in the development of quantum cryptographic protocols. In this work, we explore quantum group actions, which consist of a group acting on a set of quantum states. We show the following results:
1. In certain settings, statistical (even query bounded) security is impossible, analogously to post-quantum classical group actions.
2. We construct quantum state group actions and prove that many computational problems that have been proposed by cryptographers hold it. Depending on the construction, our proofs are either unconditional, rely on LWE, or rely on the quantum random oracle model. While our analysis does not directly apply to classical group actions, we argue it gives at least a sanity check that there are no obvious flaws in the post-quantum assumptions made by cryptographers.
3. Our quantum state group action allows for unifying two existing quantum money schemes: those based on group actions, and those based on non-collapsing hashes. We also explain how they can unify classical and quantum key distribution.

## 2024/1637

* Title: Bootstrapping Small Integers With CKKS
* Authors: Youngjin Bae, Jaehyung Kim, Damien Stehlé, Elias Suvanto
* [Permalink](https://eprint.iacr.org/2024/1637)
* [Download](https://eprint.iacr.org/2024/1637.pdf)

### Abstract

The native plaintexts of the Cheon-Kim-Kim-Song (CKKS) fully homomorphic encryption scheme are vectors of approximations to complex numbers. Drucker et al.. [J. Cryptol.'24] have showed how to use CKKS to efficiently perform computations on bits and small bit-length integers, by relying on their canonical embeddings into the complex plane. For small bit-length integers, Chung et al. [IACR eprint'24] recently suggested to rather rely on an embedding into complex roots of unity, to gain numerical stability and efficiency. Both works use CKKS in a black-box manner.

Inspired by the design by Bae et al. [Eurocrypt'24] of a dedicated bootstrapping algorithm for ciphertexts encoding bits, we propose a CKKS bootstrapping algorithm, $\mathsf{SI\mbox{-}BTS}$ (small-integer bootstrapping), for ciphertexts encoding small bit-length integers.
For this purpose, we build upon the DM/CGGI-to-CKKS conversion algorithm from Boura et al. [J. Math. Cryptol.'20], to bootstrap canonically embedded integers to integers embedded as roots of unity. $\mathsf{SI\mbox{-}BTS}$ allows functional bootstrapping: it can evaluate an arbitrary function of its input while bootstrapping. It may also be used to batch-(functional-)bootstrap multiple DM/CGGI ciphertexts. For example, its amortized cost for evaluating an 8-bit look-up table on $2^{12}$ DM/CGGI ciphertexts is 3.75ms (single-thread CPU, 128-bit security).

We adapt $\mathsf{SI\mbox{-}BTS}$ to simultaneously bootstrap multiple CKKS ciphertexts for bits. The resulting $\mathsf{BB\mbox{-}BTS}$ algorithm (batch-bits bootstrapping) allows to decrease the amortized cost of a binary gate evaluation. Compared to Bae et al., it gives a 2.4x speed-up.

## 2024/1638

* Title: Modular Reduction in CKKS
* Authors: Jaehyung Kim, Taeyeong Noh
* [Permalink](https://eprint.iacr.org/2024/1638)
* [Download](https://eprint.iacr.org/2024/1638.pdf)

### Abstract

The Cheon-Kim-Kim-Song (CKKS) scheme is renowned for its efficiency in encrypted computing over real numbers. However, it lacks an important functionality that most exact schemes have, an efficient modular reduction. This derives from the fundamental difference in encoding structure. The CKKS scheme encodes messages to the least significant bits, while the other schemes encode to the most significant bits (or in an equivalent manner). As a result, CKKS could enjoy an efficient rescaling but lost the ability to modular reduce inherently.

Our key observation is that at the very bottom modulus, plaintexts encoded in the least significant bits can still enjoy the inherent modular reduction of RLWE. We suggest incorporating modular reduction as a primary operation for CKKS and exploring its impact on efficiency. We constructed a novel homomorphic modular reduction algorithm using the discrete bootstrapping from Bae et al. [Asiacrypt'24] and a new discretization algorithm from modulus switching. One of the key advantages of our modular reduction is that its computational complexity grows sublinearly ($O(\log k)$) as we increase the input range $[0,k)$, which is asymptotically better than the state-of-the-art with $\geq O(k)$.

We checked our algorithms with concrete experiments. Notably, our modulo 1 function for input range $[0, 2^{20})$ takes only 44.9 seconds with 13.3 bits of (mean) precision, in a single-threaded CPU. Recall that modular reduction over such a large range was almost infeasible in the previous works, as they need to evaluate a polynomial of degree $> 2^{20}$ (or equivalent). As an application of our method, we compared a bit decomposition based on our framework with the state-of-the-art method from Drucker et al. [J.Cryptol'24]. Our method is $7.1 \times$ faster while reducing the failure probability by more than two orders of magnitude.

## 2024/1639

* Title: Efficient Quantum Pseudorandomness from Hamiltonian Phase States
* Authors: John Bostanci, Jonas Haferkamp, Dominik Hangleiter, Alexander Poremba
* [Permalink](https://eprint.iacr.org/2024/1639)
* [Download](https://eprint.iacr.org/2024/1639.pdf)

### Abstract

Quantum pseudorandomness has found applications in many areas of quantum information, ranging from entanglement theory, to models of scrambling phenomena in chaotic quantum systems, and, more recently, in the foundations of quantum cryptography. Kretschmer (TQC '21) showed that both pseudorandom states and pseudorandom unitaries exist even in a world without classical one-way functions. To this day, however, all known constructions require classical cryptographic building blocks which are themselves synonymous with the existence of one-way functions, and which are also challenging to realize on realistic quantum hardware.

In this work, we seek to make progress on both of these fronts simultaneously---by decoupling quantum pseudorandomness from classical cryptography altogether.
We introduce a quantum hardness assumption called the \emph{Hamiltonian Phase State} ($\mathsf{HPS}$) problem, which is the task of decoding output states of a random instantaneous quantum polynomial-time (IQP) circuit. Hamiltonian phase states can be generated very efficiently using only Hadamard gates, single-qubit $Z$ rotations and CNOT circuits. We show that the hardness of our problem reduces to a worst-case version of the problem, and we provide evidence that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions.
We also show information-theoretic hardness when only few copies of $\mathsf{HPS}$ are available by proving an approximate $t$-design property of our ensemble.
Finally, we show that our $\mathsf{HPS}$ assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives, ranging from pseudorandom states, to quantum pseudoentanglement, to pseudorandom unitaries, and even primitives such as public-key encryption with quantum keys. Along the way, we analyze a natural iterative construction of pseudorandom unitaries which resembles a candidate of Ji, Liu, and Song (CRYPTO'18).

## 2024/1640

* Title: Maximizing the Utility of Cryptographic Setups: Secure PAKEs, with either functional RO or CRS
* Authors: Yuting Xiao, Rui Zhang, Hong-Sheng Zhou
* [Permalink](https://eprint.iacr.org/2024/1640)
* [Download](https://eprint.iacr.org/2024/1640.pdf)

### Abstract

For Password-Based Authenticated Key Exchange (PAKE), an idealized setup such as random oracle (RO) or a trusted setup such as common reference string (CRS) is a must in the universal composability (UC) framework (Canetti, FOCS 2001). Given the potential failure of a CRS or RO setup, it is natural to consider distributing trust among the two setups, resulting a CRS-or-RO-setup (i.e., CoR-setup).

However, the infeasibility highlighted by Katz et al. (PODC 2014) suggested that it is impossible to construct UC-secure PAKE protocols with a straightforward CoR-setup (i.e., either the CRS is functional but the RO is compromised, or the RO is functional but the CRS is compromised). To circumvent this impossibility result, we investigate how to design UC-secure PAKE protocols with a fine-grained CoR-setup, where either the CRS is functional but the RO is non-functional, or vice versa. Different from the straightforward CoR-setup, a fine-grained non-functional setup is not necessarily completely compromised and fully controlled by the adversary; Instead, we consider this non-functional setup may still offer certain security properties. Certainly, the non-functional setup alone should be useless for achieving UC-security.

We present a UC-secure PAKE protocol under two conditions: either the CRS is functional while the RO is non-functional (falling back to a collision-resistant hash function), or the RO is functional while the CRS is non-functional (falling back to a global CRS). Before presenting our construction, we first prove that a global CRS setup alone is insufficient for achieving UC-secure PAKE. This impossibility result highlights the non-triviality of our approach.

To obtain our construction, we introduce several techniques as follows:

(1) We propose a new variant of Non-Interactive Key Exchange (NIKE), called homomorphic NIKE with associated functions, which captures key properties of existing RO-based PAKE protocols. This new primitive serves as an important component in our construction.

(2) We develop a ``Brute Force'' extraction strategy which allows us to provide security analysis for our UC-secure PAKE with a fine-grained CoR-setup for polynomial-sized password spaces.

(3) We introduce a novel password space extension technique that enables the expansion of PAKE protocols from polynomial-sized to arbitrary-sized password spaces.

(4) Finally, to ensure provable security for our password space extension in UC-secure PAKEs, we modify existing PAKE functionalities to prevent responses that reveal the correctness of password guesses. This is a reasonable adjustment, as our protocol provides only implicit authentication.

We further present a PAKE protocol in the BPR framework (Bellare, Pointcheval, Rogaway, EuroCrypt 2000), assuming either the CRS is functional while the RO falls back to a collision-resistant hash function, or the RO is functional but the CRS trapdoor is allowed to be learned by the adversary.

## 2024/1641

* Title: Simplification Issues of An Authentication and Key Agreement Scheme for Smart Grid
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2024/1641)
* [Download](https://eprint.iacr.org/2024/1641.pdf)

### Abstract

Key agreement and public key encryption are two elementary cryptographic primitives, suitable for different scenarios. But their differences are still not familiar to some researchers. In this note, we show that the Safkhani et al.'s key agreement scheme [Peer-to-Peer Netw. Appl. 15(3), 1595-1616, 2022] is a public key encryption in disguise. We stress that the ultimate use of key agreement is to establish a shared key for some symmetric key encryption. We also present a simplification of the scheme by removing some repetitive computations. To the best of our knowledge, it is the first time to clarify the fundamental differences between the two primitives. The techniques developed in this note will be helpful for the future works on designing such schemes.

## 2024/1642

* Title: Fuzzy PSI via Oblivious Protocol Routing
* Authors: David Richardson, Mike Rosulek, Jiayu Xu
* [Permalink](https://eprint.iacr.org/2024/1642)
* [Download](https://eprint.iacr.org/2024/1642.pdf)

### Abstract

In private set intersection (PSI), two parties who each hold sets of items can learn their intersection without revealing anything about their other items.. Fuzzy PSI corresponds to a relaxed variant that reveals pairs of items which are ``close enough,'' with respect to some distance metric. In this paper we propose a new protocol framework for fuzzy PSI, compatible with arbitrary distance metrics. We then show how to efficiently instantiate our framework for $\ell_1$, $\ell_2$, and $\ell_\infty$ metrics, in a way that uses exclusively cheap symmetric-key operations. One notable feature of our protocol is that it has only logarithmic dependency on the distance threshold, whereas most other protocols have linear (or higher) dependency. For many reasonable combinations of parameters, our protocol has the lowest communication cost of existing fuzzy PSI protocols.

## 2024/1643

* Title: Optimizing Liveness for Blockchain-Based Sealed-Bid Auctions in Rational Settings
* Authors: Maozhou Huang, Xiangyu Su, Mario Larangeira, Keisuke Tanaka
* [Permalink](https://eprint.iacr.org/2024/1643)
* [Download](https://eprint.iacr.org/2024/1643.pdf)

### Abstract

Blockchain-based auction markets offer stronger fairness and transparency compared to their centralized counterparts. Deposits and sealed bid formats are usually applied to enhance security and privacy. However, to our best knowledge, the formal treatment of deposit-enabled sealed-bid auctions remains lacking in the cryptographic literature. To address this gap, we first propose a decentralized anonymous deposited-bidding (DADB) scheme, providing formal syntax and security definitions. Unlike existing approaches that rely on smart contracts, our construction utilizes a mainchain-sidechain structure that is also compatible with the extended UTXO model. This design further allows us to develop a consensus mechanism on the sidechain dedicated to securely recording bids for allocation. Specifically, we build atop an Algorand-style protocol and integrate a novel block qualification mechanism into the block selection.. Consequently, we prove, from a game-theoretical perspective, that our design optimizes liveness latency for rational users who want to join the auction, even without explicit incentives (e.g., fees) for including bids. Finally, our implementation results demonstrate the potential performance degradation without the block qualification mechanism.

## 2024/1644

* Title: A Tight Lower Bound on the TdScrypt Trapdoor Memory-Hard Function
* Authors: Jeremiah Blocki, Seunghoon Lee
* [Permalink](https://eprint.iacr.org/2024/1644)
* [Download](https://eprint.iacr.org/2024/1644.pdf)

### Abstract

A trapdoor Memory-Hard Function is a function that is memory-hard to evaluate for any party who does not have a trapdoor, but is substantially less expensive to evaluate with the trapdoor. Biryukov and Perin (ASIACRYPT 2017) introduced the first candidate trapdoor Memory-Hard Function called \textsc{Diodon} which modifies a Memory-Hard Function called \textsc{Scrypt} by replacing a hash chain with repeated squaring modulo a composite number $N=pq$. The trapdoor, which consists of the prime factors $p$ and $q$, allows one to compute the function with significantly reduced cumulative memory cost (CMC) $O( n \log n \log^2 N )$ where $n$ denotes the running time parameter, e.g., the length of the hash chain or repeated squaring chain. By contrast, the best-known algorithm to compute \textsc{Diodon} without the trapdoor has the CMC $O(n^2\log N)$. Auerbach et al. (EUROCRYPT 2024) provided the first provable lower bound on the CMC of \textsc{TdScrypt} --- a specific instantiation of \textsc{Diodon}. In particular, in idealized models, they proved that the CMC of \textsc{TdScrypt} is $\Omega(\frac{n^2}{\log n}\log N)$ which almost matches the upper bound $O(n^2\log N)$ but is off by a multiplicative $\log n$ factor. In this work, we show how to tighten the analysis of Auerbach et al. (EUROCRYPT 2024) and eliminate the gap. In particular, our results imply that \textsc{TdScrypt} has the CMC at least $\Omega(n^2\log N)$.

## 2024/1645

* Title: Fiat Shamir Goes Rational
* Authors: Matteo Campanelli, Agni Datta
* [Permalink](https://eprint.iacr.org/2024/1645)
* [Download](https://eprint.iacr.org/2024/1645.pdf)

### Abstract

This paper investigates the open problem of how to construct non-interactive rational proofs. Rational proofs, introduced by Azar and Micali (STOC 2012), are a model of interactive proofs where a computationally powerful server can be rewarded by a weaker client for running an expensive computation $f(x)$. The honest strategy is enforced by design when the server is rational: any adversary claiming a false output $y \neq f(x)$ will lose money on expectation.
Rational proof constructions have appealing properties: they are simple, feature an extremely efficient verifier—reading only a sublinear number of bits of the input $x$—and do not require any collateral from the prover. Currently, all non-trivial constructions of rational proofs are interactive. Developing non-interactive rational protocols would be a game-changer, making them practical for use in smart contracts, one of their most natural applications.
Our investigation revolves around the Fiat-Shamir transform, a common approach to compiling interactive proofs into their non-interactive counterparts. We are the first to tackle the question: "Can Fiat-Shamir be successfully applied to rational protocols?"
We find negative evidence by showing that, after applying Fiat-Shamir in the random oracle model to two representative protocols in literature (AM13 and CG15) these lose their security guarantees. Our findings point to more general impossibility theorems, which we leave as future work.
To achieve our results we first need to address a fundamental technical challenge: the standard Fiat-Shamir transform does not apply to protocols where the verifier has only oracle access to its input $x$ (a core feature of the rational setting). We propose two versions of Fiat-Shamir for this setting, a "vanilla" variant and a "stronger" variant (where the verifier has access to an honestly computed digest of its input). We show that neither variant is sufficient to ensure that AM13 or CG15 are secure in the non-interactive setting.
Finally, as an additional contribution, we provide a novel, and arguably simpler, definition for the soundness property of rational proofs (interactive or non-interactive) of independent interest.

## 2024/1646

* Title: Transaction Execution Mechanisms
* Authors: Abdoulaye Ndiaye
* [Permalink](https://eprint.iacr.org/2024/1646)
* [Download](https://eprint.iacr.org/2024/1646.pdf)

### Abstract

This paper studies transaction execution mechanisms (TEMs) for blockchains, as the efficient resource allocation across multiple parallel executions queues or "local fee markets." We present a model considering capacity constraints, user valuations, and delay costs in a multi-queue system with an aggregate capacity constraint due to global consensus. We show that revenue maximization tends to allocate capacity to the highest-paying queue, while welfare maximization generally serves all queues. Optimal relative pricing of different queues depends on factors such as market size, demand elasticity, and the balance between local and global congestion. Our results have implications for evolving blockchain architectures, including parallel execution, DAG-based systems, and multiple concurrent proposers, and can help design more efficient TEMs.

## 2024/1647

* Title: Curve Forests: Transparent Zero-Knowledge Set Membership with Batching and Strong Security
* Authors: Matteo Campanelli, Mathias Hall-Andersen, Simon Holmgaard Kamp
* [Permalink](https://eprint.iacr.org/2024/1647)
* [Download](https://eprint.iacr.org/2024/1647.pdf)

### Abstract

Zero-knowledge for set membership is a building block at the core of several privacy-aware applications, such as anonymous payments, credentials and whitelists.
We propose a new efficient construction for the batching variant of the problem, where a user intends to show knowledge of several elements (a batch) in a set without any leakage on the elements. Our construction is transparent—it does not requires a trusted setup—and based on Curve Trees by Campanelli, Hall-Andersen and Kamp (USENIX 2023). Our first technical contribution consists in techniques to amortize Curve Trees costs in the batching setting for which we crucially exploit its algebraic properties. Even for small batches we obtain $\approx 2\times$ speedups for proving, $\approx3\times$ speedups for verification and $\approx 60\%$ reduction in proof size. Our second contribution is a modifications of a key technical requirement in Curve Trees (related to so called "permissible points") which arguably simplifies its design and obtains a stronger security property. In particular, our construction is secure even for the case where the commitment to the set is provided by the adversary (in contrast to the honest one required by the original Curve Trees).

## 2024/1648

* Title: SIMD-style Sorting of Integer Sequence in RLWE Ciphertext
* Authors: Zijing Li, Hongbo Li, Zhengyang Wang
* [Permalink](https://eprint.iacr.org/2024/1648)
* [Download](https://eprint.iacr.org/2024/1648.pdf)

### Abstract

This article discusses fully homomorphic encryption and homomorphic sorting. Homomorphic encryption is a special encryption technique that allows all kinds of operations to be performed on ciphertext, and the result is still decryptable, such that when decrypted, the result is the same as that obtained by performing the same operation on the plaintext. Homomorphic sorting is an important problem in homomorphic encryption. Currently, there has been a volume of work on homomorphic sorting. In these works, each integer in a sequence is encrypted in a separate ciphertext, there is a lack of research on sorting sequences of integers encrypted in a single ciphertext. This paper addresses the sorting problem by utilizing Single Instruction Multiple Data (SIMD) technology to provide new algorithms to improve computational efficiency. The content includes the following aspects.
For plaintexts encrypted word-wise, this paper studies sorting an integer sequence stored in one or multiple ciphertexts, and proposes a new SIMD-style homomorphic sorting algorithm. On theoretical complexity, compared with three existing sorting algorithms, namely, homomorphic sorting by polynomial computation over a finite field, by TFHE bootstrapping, or by Liu-Wang parallel bootstrapping, the new algorithm achieves a speedup of $O((\log n)^2)$, $O(n(\log n)^3)$, and $O((\log n)^4)$, respectively, for sorting a plaintext integer sequence of length $n$. By experimental results, the new algorithm is 1.7-9.2 times faster than the three sorting algorithms.
The third situation involves sorting multiple shorter sequences simultaneously, all of which can be stored in a single ciphertext. For this situation, this paper proposes a method for calculating the ord function, and uses this method to provide a new sorting algorithm. On theoretical complexity, if the total number of numbers to be sorted is $n$ and there are $n^r$ numbers in each sequence, the new algorithm is faster than three existing sorting algorithms, with speed-ups of $O(n^{1-r}(\log n)^2)$, $O(n^{2-r}(\log n)^3)$, and $O(n^{1-r}(\log n)^4)$, respectively. By experimental results, the new algorithm is 2.1-6.4 times faster than existing sorting algorithms.

## 2024/1649

* Title: Multiplying Polynomials without Powerful Multiplication Instructions (Long Paper)
* Authors: Vincent Hwang, YoungBeom Kim, Seog Chung Seo
* [Permalink](https://eprint.iacr.org/2024/1649)
* [Download](https://eprint.iacr.org/2024/1649.pdf)

### Abstract

We improve the performance of lattice-based cryptosystems Dilithium on Cortex-M3 with expensive multiplications. Our contribution is two-fold: (i) We generalize Barrett multiplication and show that the resulting shape-independent modular multiplication performs comparably to long multiplication on some platforms without special hardware when precomputation is free. We call a modular multiplication “shape-independent” if its correctness and efficiency depend only on the magnitude of moduli and not the shapes of the moduli. This was unknown in the literature even though modular multiplication has been studied for more than 40 years. In the literature, shape-independent modular multiplications often perform several times slower than long multiplications even if we ignore the cost of the precomputation. (ii) We show that polynomial multiplications based on Nussbaumer fast Fourier transform and Toom–Cook over $\mathbb{Z}_{2^k}$ perform the best when modular multiplications are expensive and $k$ is not very close to the arithmetic precision.

For practical evaluation, we implement assembly programs for the polynomial arithmetic used in the digital signature Dilithium on Cortex-M3. For the modular multiplications in Dilithium, our generalized Barrett multiplications are 1.92 times faster than the state-of-the-art assembly-optimized Montgomery multiplications, leading to 1.38−1.51 times faster Dilithium NTT/iNTT. Along with the improvement in accumulating products, the core polynomial arithmetic matrix-vector multiplications are 1.71−1.77 times faster. We further apply the FFT-based polynomial multiplications over $\mathbb{Z}_{2^k}$ to the challenge polynomial multiplication $c t_0$, leading to 1.31 times faster computation for $c t_0$.

We additionally apply the ideas to Saber on Cortex-M3 and demonstrate their improvement to Dilithium and Saber on our 8-bit AVR environment. For Saber on Cortex-M3, we show that matrix-vector multiplications with FFT-based polynomial multiplications over $\mathbb{Z}_{2^k}$ are 1.42−1.46 faster than the ones with NTT-based polynomial multiplications over NTT-friendly coefficient rings. When moving to a platform with smaller arithmetic precision, such as 8-bit AVR, we improve the matrix-vector multiplication of Dilithium with our Barrett-based NTT/iNTT by a factor of 1.87−1.89. As for Saber on our 8-bit AVR environment, we show that matrix-vector multiplications with NTT-based polynomial multiplications over NTT-friendly coefficient rings are faster than polynomial multiplications over $\mathbb{Z}_{2^k}$ due to the large $k$ in Saber.

## 2024/1650

* Title: Towards Practical Oblivious Map
* Authors: Xinle Cao, Weiqi Feng, Jian Liu, Jinjin Zhou, Wenjing Fang, Lei Wang, Quanqing Xu, Chuanhui Yang, Kui Ren
* [Permalink](https://eprint.iacr.org/2024/1650)
* [Download](https://eprint.iacr.org/2024/1650.pdf)

### Abstract

Oblivious map (OMAP) is an important component in encrypted databases, utilized to safeguard against the server inferring sensitive information about client's encrypted key-value stores based on \emph{access patterns}. Despite its widespread usage and importance, existing OMAP solutions face practical challenges, including the need for a large number of interaction rounds between the client and server, as well as the substantial communication bandwidth requirements. For example, the state-of-the-art protocol named OMIX++ in VLDB 2024 still requires $O(\log{n})$ interaction rounds and $O(\log^2{n})$ communication bandwidth per access, where $n$ denote the total number of key-value pairs stored.

In this work, we introduce more practical and efficient OMAP constructions. Consistent with all prior OMAPs, our proposed constructions also adapt only the \emph{tree-based Oblivious RAM} (ORAM) to achieve OMAP for enhanced practicality. In terms of complexity, our approach needs only $O(\log{n}/\log{\log{n}})$ interaction rounds and $O(\log^2{n}/\log{\log{n}})$ communication bandwidth per data access, achieving the lowest communication volume to the best our of knowledge. This improvement results from our two main contributions. First, unlike prior works that rely solely on search trees, we design a novel framework for OMAP that combines hash table with search trees. Second, we propose a more efficient tree-based ORAM named DAORAM, which is of significant independent interest. This newly developed ORAM noticeably accelerates our constructions. We implement both our proposed constructions and prior methods to experimentally demonstrate that our constructions substantially outperform prior methods in terms of efficiency.

## 2024/1651

* Title: One-Shot Native Proofs of Non-Native Operations in Incrementally Verifiable Computations
* Authors: Tohru Khorita, Patrick Towa, Zachary J. Williamson
* [Permalink](https://eprint.iacr.org/2024/1651)
* [Download](https://eprint.iacr.org/2024/1651.pdf)

### Abstract

Proving non-native operations is still a bottleneck in existing incrementally verifiable computations. Prior attempts to solve this issue either simply improve the efficiency of proofs of non-native operations or require folding instances in each curve of a cycle. This paper shows how to avoid altogether in-circuit proofs of non-native operations in the incre- mental steps, and only record them in some auxiliary proof information. These operations are proved natively at the end of the computation, at the cost of only a small constant number (four or five) of non-native field multiplications to go from a non-native operation record to a native one. To formalise the security guarantees of the scheme, the paper introduces the concept of incrementally verifiable computation with auxiliary proof information, a relaxation of the standard notion of incrementally veri- fiable computation. The knowledge-soundness now guarantees the cor- rectness of a computation only if the piece of information attached to a proof is valid. This new primitive is thus only to be used if there is an efficient mechanism to verify the validity of that information. This relaxation is exactly what enables a construction which does not require in-circuit proofs of non-native operations during the incremental part of the computation. Instantiated in the Plonk arithmetisation, the construction leads to savings in circuit-gate count (compared to standard folding-based constructions) of at least one order of magnitude, and that can go up to a factor of 50.

Date	Sujet	#		Auteur
14 Oct 24	[digest] 2024 Week 41	1		IACR ePrint Archive