## In this issue

1. [2024/762] Constant-Cost Batched Partial Decryption in ...
2. [2024/766] Breaking Verifiable Delay Functions in the Random ...
3. [2024/1530] Folding Schemes with Privacy Preserving Selective ...
4. [2024/1531] FLI: Folding Lookup Instances
5. [2024/1532] Bitwise Garbling Schemes --- A Model with ...
6. [2024/1533] BEAT-MEV: Epochless Approach to Batched Threshold ...
7. [2024/1534] More Efficient Lattice-based OLE from Circuit- ...
8. [2024/1535] Relaxed Lattice-Based Programmable Hash Functions: ...
9. [2024/1536] Cryptographic Characterization of Quantum Advantage
10. [2024/1537] VOLE-in-the-head signatures from Subfield Bilinear ...
11. [2024/1538] Security Perceptions of Users in Stablecoins: ...
12. [2024/1539] Quantum Cryptography from Meta-Complexity
13. [2024/1540] Formal Security Analysis of the OpenID FAPI 2.0 ...
14. [2024/1541] Findex: A Concurrent and Database-Independent ...
15. [2024/1542] Robust AE With Committing Security
16. [2024/1543] HEonGPU: a GPU-based Fully Homomorphic Encryption ...
17. [2024/1544] PoUDR: Proof of Unified Data Retrieval in ...
18. [2024/1545] Fully Composable Homomorphic Encryption
19. [2024/1546] Bit t-SNI Secure Multiplication Gadget for Inner ...
20. [2024/1547] HHL for tensor-decomposable matrices
21. [2024/1548] Fully-Succinct Arguments over the Integers from ...
22. [2024/1549] Universally Composable SNARKs with Transparent ...
23. [2024/1550] MAYO Key Recovery by Fixing Vinegar Seeds
24. [2024/1551] SNARKs for Virtual Machines are Non-Malleable
25. [2024/1552] Revisiting Keyed-Verification Anonymous Credentials
26. [2024/1553] STARK-based Signatures from the RPO Permutation
27. [2024/1554] Breaking, Repairing and Enhancing XCBv2 into the ...
28. [2024/1555] Private Laconic Oblivious Transfer with Preprocessing
29. [2024/1556] The module action for isogeny based cryptography
30. [2024/1557] Tightly Secure Threshold Signatures over Pairing- ...
31. [2024/1558] Understanding Leakage in Searchable Encryption: a ...
32. [2024/1559] Mind the Composition of Toffoli Gates: Structural ...
33. [2024/1560] Revisiting Shuffle-Based Private Set Unions with ...
34. [2024/1561] FLUENT: A Tool for Efficient Mixed-Protocol Semi- ...
35. [2024/1562] Fully Privacy-preserving Billing Models for Peer- ...
36. [2024/1563] Optimized One-Dimensional SQIsign Verification on ...
37. [2024/1564] A Simple Framework for Secure Key Leasing
38. [2024/1565] Fiat-Shamir in the Wild
39. [2024/1566] Dynamic zk-SNARKs
40. [2024/1567] A New World in the Depths of Microcrypt: Separating ...
41. [2024/1568] Oracle Separation Between Quantum Commitments and ...
42. [2024/1569] The Supersingular Isogeny Path and Endomorphism ...

## 2024/762

* Title: Constant-Cost Batched Partial Decryption in Threshold Encryption
* Authors: Sora Suegami, Shinsaku Ashizawa, Kyohei Shibano
* [Permalink](https://eprint.iacr.org/2024/762)
* [Download](https://eprint.iacr.org/2024/762.pdf)

### Abstract

Threshold public key encryption schemes distribute secret keys among multiple parties, known as the committee, to reduce reliance on a single trusted entity.
However, existing schemes face inefficiencies as the committee should perform computation and communication for decryption of each individual ciphertext.
As the number of ciphertexts being decrypted per unit of time increases, this can limit the number of committee parties and their decentralization due to increased hardware requirements, heightening the risk of adversarial collusion.
To address this, we introduce tag-based batched threshold encryption (TBTE), which ensures constant computational and communication costs per committee member, independent of the number of ciphertexts being decrypted in batch under distinct decryption policies.
The TBTE scheme is constructed over bilinear groups in the random oracle model and secure in the algebraic group model, assuming the hardness of the $(q_1,q_2)$-discrete logarithm problem and the EAV-security of the symmetric-key encryption scheme.
Evaluation of our implementation demonstrates constant data size, specifically 48 bytes received and 56 bytes sent, and constant execution time for each committee party during decryption, even for various batch sizes up to $2^{20}$.

## 2024/766

* Title: Breaking Verifiable Delay Functions in the Random Oracle Model
* Authors: Ziyi Guan, Artur Riazanov, Weiqiang Yuan
* [Permalink](https://eprint.iacr.org/2024/766)
* [Download](https://eprint.iacr.org/2024/766.pdf)

### Abstract

A verifiable delay function (VDF) is a cryptographic primitive that requires a long time to compute (even with parallelization), but produces a unique output that is efficiently and publicly verifiable.

We prove that VDFs with \emph{imperfect completeness} and \emph{computational uniqueness} do not exist in the random oracle model. This also rules out black-box constructions of VDFs from other cryptographic primitives, such as one-way permutations and collision-resistant hash functions.

Prior to our work, Mahmoody, Smith and Wu (ICALP 2020) prove that VDFs satisfying both \emph{perfect completeness} and \emph{perfect uniqueness} do not exist in the random oracle model; on the other hand, Ephraim, Freitag, Komargodski, and Pass (Eurocrypt 2020) construct VDFs with \emph{perfect completeness} and \emph{computational uniqueness} in the random oracle model assuming the hardness of repeated squaring. Our result is optimal -- we bridge the current gap between previously known impossibility results and existing constructions.

## 2024/1530

* Title: Folding Schemes with Privacy Preserving Selective Verification
* Authors: Joan Boyar, Simon Erfurth
* [Permalink](https://eprint.iacr.org/2024/1530)
* [Download](https://eprint.iacr.org/2024/1530.pdf)

### Abstract

Folding schemes are an exciting new primitive, transforming the task of performing multiple zero-knowledge proofs of knowledge for a relation into performing just one zero-knowledge proof, for the same relation, and a number of cheap inclusion-proofs. Recently, folding schemes have been used to amortize the cost associated with proving different statements to multiple distinct verifiers, which has various applications. We observe that for these uses, leaking information about the statements folded together can be problematic, yet this happens with previous constructions. Towards resolving this issue, we give a natural definition of privacy preserving folding schemes, and what security they should offer. To construct privacy preserving folding schemes, we first define a statement hiders, a primitive which might be of independent interest. In a nutshell, a statement hider hides an instance of a relation as a new instance in the same relation. The new instance is in the relation if and only if the initial instance is. With this building block, we can utilize existing folding schemes to construct a privacy preserving folding scheme, by first hiding each of the statements. Folding schemes allow verifying that a statement was folded into another statement, while statement hiders allow verifying that a statement was hidden as another statement.

## 2024/1531

* Title: FLI: Folding Lookup Instances
* Authors: Albert Garreta, Ignacio Manzur
* [Permalink](https://eprint.iacr.org/2024/1531)
* [Download](https://eprint.iacr.org/2024/1531.pdf)

### Abstract

We introduce two folding schemes for lookup instances: FLI and FLI+SOS. Both use a PIOP to check that a matrix has elementary basis vectors as rows, with FLI+SOS adding a twist based on Lasso’s SOS-decomposability.

FLI takes two lookup instances $\{\mathbf{a}_1\}, \{\mathbf{a}_2\}\subseteq\mathbf{t}$, and expresses them as matrix equations $M_i\cdot\mathbf{t}^\mathsf{T}=\mathbf{a}_i^\mathsf{T}$ for $i=1,2$, where each matrix $M_i\in\mathbb{F}^{m\times N}$ has rows which are elementary basis vectors in $\mathbb{F}^N$. Matrices that satisfy this condition are said to be in $R_{\mathsf{elem}}$. Then, a folding scheme for $R_{\mathsf{elem}}$ into a relaxed relation is used, which combines the matrices $M_1, M_2$ as $M_1+\alpha M_2$ for a random $\alpha\in\mathbb{F}$. Finally, the lookup equations are combined as $(M_1+\alpha M_2)\cdot \mathbf{t}^{\mathsf{T}} = (\mathbf{a}_1+\alpha \mathbf{a}_2)^\mathsf{T}$. In FLI, only the property that a matrix is in $R_{\mathsf{elem}}$ is folded, and this makes the FLI folding step the cheapest among existing solutions. The price to pay is in the cost for proving accumulated instances.

FLI+SOS builds upon FLI to enable folding of large SOS-decomposable tables. This is achieved through a variation of Lasso's approach to SOS-decomposability, which fits FLI naturally. For comparison, we describe (for the first time to our knowledge) straightforward variations of Protostar and Proofs for Deep Thought that also benefit from SOS-decomposability. We see that for many reasonable parameter choices, and especially those arising from lookup-based zkVMs, FLI+SOS can concretely be the cheapest folding solution.

## 2024/1532

* Title: Bitwise Garbling Schemes --- A Model with $\frac{3}{2}\kappa$-bit Lower Bound of Ciphertexts
* Authors: Fei Xu, Honggang Hu, Changhong Xu
* [Permalink](https://eprint.iacr.org/2024/1532)
* [Download](https://eprint.iacr.org/2024/1532.pdf)

### Abstract

At Eurocrypt 2015, Zahur, Rosulek, and Evans proposed the model of Linear Garbling Schemes. This model proved a $2\kappa$-bit lower bound of ciphertexts for a broad class of garbling schemes. Since then, several methods have been developed that bypass this lower bound, albeit with a notable limitation: Their reliance on specifically correlated input wire labels restricts their applicability across most gates. At Crypto 2021, Rosulek and Roy presented the innovative "three-halves" garbling scheme in which AND gates cost $1.5\kappa+5$ bits and XOR gates are free. A noteworthy aspect of their scheme is the slicing-and-dicing technique, which is applicable universally to all AND gates when garbling a boolean circuit. Following this revelation, Rosulek and Roy presented several open problems. Our research primarily addresses one of them: ``Is $1.5\kappa$ bits optimal for garbled AND gates in a more inclusive model than Linear Garbling Schemes?''

In this paper, we propose the Bitwise Garbling Schemes, a model that seamlessly incorporates the slicing-and-dicing technique. Our key revelation is that $1.5\kappa$ bits is indeed optimal for arbitrary garbled AND gates in our model. Since Rosulek and Roy also suggested another problem which questions the necessity of free-XOR, we explore constructions without free-XOR and prove a $2\kappa$-bit lower bound. Therefore, sacrificing compatibility with free-XOR does not lead to a more efficient scheme.

## 2024/1533

* Title: BEAT-MEV: Epochless Approach to Batched Threshold Encryption for MEV Prevention
* Authors: Jan Bormet, Sebastian Faust, Hussien Othman, Ziyan Qu
* [Permalink](https://eprint.iacr.org/2024/1533)
* [Download](https://eprint.iacr.org/2024/1533.pdf)

### Abstract

In decentralized finance (DeFi), the public availability of pending transactions presents significant privacy concerns, enabling market manipulation through miner extractable value (MEV). MEV occurs when block proposers exploit the ability to reorder, omit, or include transactions, causing financial loss to users from frontrunning. Recent research has focused on encrypting pending transactions, hiding transaction data until block finalization. To this end, Choudhuri et al. (USENIX '24) introduce an elegant new primitive called Batched Threshold Encryption (BTE) where a batch of encrypted transactions is selected by a committee and only decrypted after block finalization. Crucially, BTE achieves low communication complexity during decryption and guarantees that all encrypted transactions outside the batch remain private. An important shortcoming of their construction is, however, that it progresses in epochs and requires a costly setup in MPC for each batch decryption.
In this work, we introduce a novel BTE scheme addressing the limitations by eliminating the need for an expensive epoch setup while achieving practical encryption and decryption times. Additionally, we explore the problem of how users can coordinate their transactions, which is crucial for the functionality of the system. Along the way, we present several optimizations and trade-offs between communication and computational complexity that allow us to achieve practical performance on standard hardware ($<2$ ms for encryption and $<440$ ms for decrypting $512$ transactions). Finally, we prove our constructions secure in a model that captures practical attacks on MEV-prevention mechanisms.

## 2024/1534

* Title: More Efficient Lattice-based OLE from Circuit-private Linear HE with Polynomial Overhead
* Authors: Leo de Castro, Duhyeong Kim, Miran Kim, Keewoo Lee, Seonhong Min, Yongsoo Song
* [Permalink](https://eprint.iacr.org/2024/1534)
* [Download](https://eprint.iacr.org/2024/1534.pdf)

### Abstract

We present a new and efficient method to obtain circuit privacy for lattice-based linearly homomorphic encryptions (LHE). In particular, our method does not involve noise-flooding with exponetially large errors or iterative bootstrapping. As a direct result, we obtain a semi-honest oblivious linear evaluation (OLE) protocol with the same efficiency, reducing the communication cost of the prior state of the art by 50%.
Consequently, the amortized time of our protocol improves the prior work by 33% under 100Mbps network setting. Our semi-honest OLE is the first to achieve both concrete efficiency and asymptotic quasi-optimality. Together with an extension of the recent zero-knowledge proof of plaintext knowledge, our LHE yields actively-secure OLE with 2.7x reduced communication from the prior work.. When applied to Overdrive (Eurocrypt '18), an MPC preprocessing protocol, our method provides 1.4x improvement in communication over the state of the art.

## 2024/1535

* Title: Relaxed Lattice-Based Programmable Hash Functions: New Efficient Adaptively Secure IBEs
* Authors: Xingye Lu, Jingjing Fan, Man Ho AU
* [Permalink](https://eprint.iacr.org/2024/1535)
* [Download](https://eprint.iacr.org/2024/1535.pdf)

### Abstract

In this paper, we introduce the notion of relaxed lattice-based programmable hash function (RPHF), which is a novel variant of lattice-based programmable hash functions (PHFs). Lattice-based PHFs, together with preimage trapdoor functions (TDFs), have been widely utilized (implicitly or explicitly) in the construction of adaptively secure identity-based encryption (IBE) schemes. The preimage length and the output length of the underlying PHF and TDF together determine the user secret key and ciphertext lengths of the IBE schemes.
However, the current lattice-based PHF definition imposes the restriction that the preimage length of TDF in the IBE schemes cannot be too short, hindering the utilization of size-efficient NTRU TDF. To overcome this hurdle, RPHF relaxes the hash key distribution requirement in the definition of PHF from statistical indistinguishability to computational indistinguishability. This relaxation eliminates limitations on the preimage length of underlying TDFs in IBE, enabling the construction of IBEs from NTRU TDFs.
We introduce two instantiations of RPHF: the first produces a hash output length of $2$ ring elements, with a hash key size linear to the input length, and the second yields an output length of $14$ ring elements, with a hash key size proportional to the square root of the input length.
Building upon these RPHF instantiations, we propose two adaptively secure lattice-based IBE schemes with ciphertext lengths of $5$ and $17$ ring elements and user secret key lengths of $4$ and $16$ ring elements, respectively.
The length of the IBE master public key is roughly equivalent to the size of the hash key of the underlying RPHF.
In comparison to existing IBE constructions, our proposed schemes achieve a significant reduction (over an order of magnitude) in ciphertext and secret key sizes. Notably, state-of-the-art constructions from ideal lattices exhibit secret key and ciphertext sizes over 100 ring elements, making our proposed schemes highly efficient. Moreover, the master public key sizes of our IBEs remain comparable.

## 2024/1536

* Title: Cryptographic Characterization of Quantum Advantage
* Authors: Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2024/1536)
* [Download](https://eprint.iacr.org/2024/1536.pdf)

### Abstract

Quantum computational advantage refers to an existence of computational tasks that are easy for quantum computing but hard for classical one. Unconditionally showing quantum advantage is beyond our current understanding of complexity theory, and therefore some computational assumptions are needed. Which complexity assumption is necessary and sufficient for quantum advantage? In this paper, we show that inefficient-verifier proofs of quantumness (IV-PoQ) exist if and only if classically-secure one-way puzzles (OWPuzzs) exist. As far as we know, this is the first time that a complete cryptographic characterization of quantum advantage is obtained. IV-PoQ capture various types of quantum advantage previously studied, such as sampling advantage and searching advantage. Previous work [Morimae and Yamakawa 2024] showed that IV-PoQ can be constructed from OWFs, but a construction of IV-PoQ from weaker assumptions was left open. Our result solves the open problem. OWPuzzs are one of the most fundamental quantum cryptographic primitives implied by many quantum cryptographic primitives weaker than one-way functions (OWFs). The equivalence between IV-PoQ and classically-secure OWPuzzs therefore highlights that if there is no quantum advantage, then these fundamental primitives do not exist. The equivalence also means that quantum advantage is an example of the applications of OWPuzzs. Except for commitments, no application of OWPuzzs was known before.. Our result shows that quantum advantage is another application of OWPuzzs. Moreover, it is the first quantum computation classical communication (QCCC) application of OWPuzzs.

## 2024/1537

* Title: VOLE-in-the-head signatures from Subfield Bilinear Collisions
* Authors: Janik Huth, Antoine Joux
* [Permalink](https://eprint.iacr.org/2024/1537)
* [Download](https://eprint.iacr.org/2024/1537.pdf)

### Abstract

In this paper, we introduce a new method to construct a signature scheme based on the subfield bilinear collision problem published at Crypto 2024. We use techniques based on vector oblivious linear evaluation (VOLE) to significantly improve the running time and signature size of the scheme compared to the MPC-in-the-head version.

## 2024/1538

* Title: Security Perceptions of Users in Stablecoins: Advantages and Risks within the Cryptocurrency Ecosystem
* Authors: Maggie Yongqi Guan, Yaman Yu, Tanusree Sharma, Molly Zhuangtong Huang, Kaihua Qin, Yang Wang, Kanye Ye Wang
* [Permalink](https://eprint.iacr.org/2024/1538)
* [Download](https://eprint.iacr.org/2024/1538.pdf)

### Abstract

Stablecoins, a type of cryptocurrency pegged to another asset to maintain a stable price, have become an important part of the cryptocurrency ecosystem. Prior studies have primarily focused on examining the security of stablecoins from technical and theoretical perspectives, with limited investigation into users’ risk perceptions and security behaviors in stablecoin practices. To address this research gap, we conducted a mixed-method study that included constructing a stablecoin interaction framework based on the literature, which informed the design of our interview protocol, semi-structured interviews (n=21), and Reddit data analysis (9,326 posts). We found that participants see stable value and regulatory compliance as key security advantages of stablecoins over other cryptocurrencies. However, participants also raised concerns about centralization risks in fiat-backed stablecoins, perceived challenges in crypto-backed stablecoins due to limited reliance on fully automated execution, and confusion regarding the complex mechanisms of algorithmic stablecoins. We proposed improving user education and optimizing mechanisms to address these concerns and promote the safer use of stablecoins.

## 2024/1539

* Title: Quantum Cryptography from Meta-Complexity
* Authors: Taiga Hiroka, Tomoyuki Morimae
* [Permalink](https://eprint.iacr.org/2024/1539)
* [Download](https://eprint.iacr.org/2024/1539.pdf)

### Abstract

In classical cryptography, one-way functions (OWFs) are the minimal assumption, while recent active studies have demonstrated that OWFs are not necessarily the minimum assumption in quantum cryptography. Several new primitives have been introduced such as pseudorandom unitaries (PRUs), pseudorandom function-like state generators (PRFSGs), pseudorandom state generators (PRSGs), one-way state generators (OWSGs), one-way puzzles (OWPuzzs), and EFI pairs. They are believed to be weaker than OWFs, but they still imply many useful applications such as private-key quantum money schemes, secret-key encryption, message authentication codes, digital signatures, commitments, and multiparty computations. Now that the possibility of quantum cryptography without OWFs has opened up, the most important goal in the field is to provide them with concrete instantiations. For example, in classical cryptography, there are many instantiations of OWFs based on concrete hardness assumptions, such as the hardness of discrete logarithms or learning with errors. The study of generic primitives is justified by the existence of concrete instantiations. On the other hand, in quantum cryptography, all known constructions of those primitives are only from OWFs. We therefore have the following important open problem: Do they have instantiations based on some concrete hardness assumptions that will not imply OWFs? Ideally, the assumptions should be the ones that are studied in other contexts than cryptography. In this paper, we give a candidate answer to the question by showing that quantum-average-hardness of GapK problem implies the existence of OWPuzzs. A GapK problem is a promise problem to decide whether a given bit string has a small Kolmogorov complexity or not. Its quantum-average-hardness means that an instance is sampled from a quantum-polynomial-time-samplable distribution, and no quantum-polynomial-time algorithm can solve the problem with high probability. As far as we know, this is the first time that a ``Microcrypt'' primitive is constructed based on concrete hardness assumptions that do not seem to imply OWFs. Moreover, the assumptions are studied in other contexts than cryptography, especially in the field of meta-complexity. (Note: During the preparation of this manuscript, Khurana and Tomer \cite{cryptoeprint:2024/1490} uploaded a concurrent work.)

## 2024/1540

* Title: Formal Security Analysis of the OpenID FAPI 2.0 Family of Protocols: Accompanying a Standardization Process
* Authors: Pedram Hosseyni, Ralf Küsters, Tim Würtele
* [Permalink](https://eprint.iacr.org/2024/1540)
* [Download](https://eprint.iacr.org/2024/1540.pdf)

### Abstract

FAPI 2.0 is a suite of Web protocols developed by the OpenID Foundation's FAPI Working Group (FAPI WG) for third-party data sharing and digital identity in high-risk environments. Even though the specifications are not completely finished, several important entities have started to adopt the FAPI 2.0 protocols, including Norway's national HelseID, Australia's Consumer Data Standards, as well as private companies like Authlete and Australia-based connectID; the predecessor FAPI 1.0 is in widespread use with millions of users.

The FAPI WG asked us to accompany the standardization of the FAPI 2.0 protocols with a formal security analysis to proactively identify vulnerabilities before widespread deployment and to provide formal security guarantees for the standards. In this paper, we report on our analysis and findings.

Our analysis is based on a detailed model of the Web infrastructure, the so-called Web Infrastructure Model (WIM), which we extend to be able to carry out our analysis of the FAPI 2.0 protocols including important extensions like FAPI-CIBA. Based on the (extended) WIM and formalizations of the security goals and attacker model laid out in the FAPI 2.0 specifications, we provide a formal model of the protocols and carry out a formal security analysis, revealing several attacks. We have worked with the FAPI WG to fix the protocols, resulting in several amendments to the specifications. With these changes in place, we have adjusted our protocol model and formally proved that the security properties hold true under the strong attacker model defined by the FAPI WG.

## 2024/1541

* Title: Findex: A Concurrent and Database-Independent Searchable Encryption Scheme
* Authors: Théophile Brézot, Chloé Hébant
* [Permalink](https://eprint.iacr.org/2024/1541)
* [Download](https://eprint.iacr.org/2024/1541.pdf)

### Abstract

State-of-the-art database implementations offer a wide range of functionalities and impressive performances while supporting highly concurrent loads. However they all rely on the server knowing the content of the database, which raises issues when sensitive information is being stored on a server that cannot be trusted. Encrypting documents before sending them to a remote server solves the confidentiality issue at the cost of loosing the keyword search functionality. Cryptographic primitives such as Symmetric Searchable Encryption (SSE) schemes have been proposed to recover this functionality. However, no SSE construction properly defines correctness and successfully guarantees security in a concurrent setting.
This paper attempts a first step in this direction by recommending linearizability as the standard notion of correctness for a concurrent SSE. We study the impact of concurrency on security and stress the need for finer-grained security models. Hence, we propose the log-security model that guarantees security against an adversary having access to persistency-related logs, fixing a blind spot in the snapshot model while capturing security in a concurrent setting.
We also build the first concurrent SSE solution proven correct and secure in a concurrent setting, that can be implemented on top of any database. Our scheme proved to be fast thanks to optimal wait-free search operations and sequentially-optimal, lock-free modifications, that both execute under one micro-second per binding, while only incurring a 13.3% storage expansion.

## 2024/1542

* Title: Robust AE With Committing Security
* Authors: Viet Tung Hoang, Sanketh Menda
* [Permalink](https://eprint.iacr.org/2024/1542)
* [Download](https://eprint.iacr.org/2024/1542.pdf)

### Abstract

There has been a recent interest to develop and standardize Robust Authenticated Encryption (Robust AE) schemes. NIST, for example, is considering an Accordion mode (a wideblock tweakable blockcipher), with Robust AE as a primary application. On the other hand, recent attacks and applications suggest that encryption needs to be committing. Indeed, committing security isalso a design consideration in the Accordion mode. Yet it is unclear how to build a Robust AE with committing security.

In this work, we give a modular solution for this problem. We first show how to transform any wideblock tweakable blockcipher TE to a Robust AE scheme SE that commits just the key. The overhead is cheap, just a few finite-field multiplications and blockcipher calls. If one wants to commit the entire encryption context, one can simply hash the context to derive a 256-bit subkey, and uses SE on that subkey. The use of 256-bit key on SE only means that it has to rely on AES-256 but doesn't require TE to have 256-bit key.

Our approach frees the Accordion designs from consideration of committing security. Moreover, it gives a big saving for several key-committing applications that don't want to pay the inherent hashing cost of full committing.

## 2024/1543

* Title: HEonGPU: a GPU-based Fully Homomorphic Encryption Library 1.0
* Authors: Ali Şah Özcan, Erkay Savaş
* [Permalink](https://eprint.iacr.org/2024/1543)
* [Download](https://eprint.iacr.org/2024/1543.pdf)

### Abstract

HEonGPU is a high-performance library designed to optimize Fully Homomorphic Encryption (FHE) operations on Graphics Processing Unit (GPU). By leveraging the parallel processing capac- ity of GPUs, HEonGPU significantly reduces the computational overhead typically associated with FHE by executing complex operation concurrently. This allows for faster execution of homomorphic computations on encrypted data, enabling real-time applications in privacy-preserving machine learn- ing and secure data processing. A key advantage of HEonGPU lies in its multi-stream architecture, which not only allows parallel processing of tasks to improve throughput but also eliminates the over- head of data transfers between the host device (i.e., CPU) and GPU. By efficiently managing data within the GPU using multi-streams, HEonGPU minimizes the need for repeated memory transfers, further enhancing performance. HEonGPU’s GPU-optimized design makes it ideal for large-scale encrypted computations, providing users with reduced latency and higher performance across various FHE schemes.

## 2024/1544

* Title: PoUDR: Proof of Unified Data Retrieval in Decentralized Storage Networks
* Authors: Zonglun Li, Shuhao Zheng, Junliang Luo, Ziyue Xin, Dun Yuan, Shang Gao, Sichao Yang, Bin Xiao, Xue Liu
* [Permalink](https://eprint.iacr.org/2024/1544)
* [Download](https://eprint.iacr.org/2024/1544.pdf)

### Abstract

Decentralized storage networks, including IPFS and Filecoin, have created a marketplace where individuals exchange storage space for profit. These networks employ protocols that reliably ensure data storage providers accurately store data without alterations, safeguarding the interests of storage purchasers.. However, these protocols lack an effective and equitable payment mechanism for data retrieval, particularly when multiple data queriers are involved. This necessitates a protocol that ensures both data integrity and fair compensation for data providers.

In decentralized storage, data is fragmented into small blocks and stored across multiple nodes, a process known as data swarming. Due to this property, traditional data exchange protocols are inadequate in terms of communication and economic efficiency.

We propose the Proof of Unified Data Retrieval protocol (PoUDR). PoUDR incorporates ZK-SNARK to facilitate a fair data exchange protocol. PoUDR reduces the number of blockchain transactions for both single block and data swarming retrieval. The protocol requires only a single key-revealing transaction submitted by the provider to the blockchain for each data block. This architecture allows for further optimization of transaction numbers through a batched proof technique on the provider's side. This approach necessitates only $N_P$ transactions within a specific time frame when data consisting of $N_D$ blocks, provided by $N_P$ providers, is queried by $N_Q$ queriers.

This work provides a comprehensive definition for Secure Swarming Data Exchange (SSDE), including security assumptions. Also it offers a detailed game-based security analysis for the PoUDR protocol. Moreover, the PoUDR protocol has been fully integrated into the Bitswap protocol (IPFS). Within this integration, our proposed Relaxed Groth16 algorithm addresses the significant technical challenge of generating zero-knowledge proofs, leading to substantial cost reductions for overall feasibility of secure data retrieval in decentralized storage networks.

## 2024/1545

* Title: Fully Composable Homomorphic Encryption
* Authors: Daniele Micciancio
* [Permalink](https://eprint.iacr.org/2024/1545)
* [Download](https://eprint.iacr.org/2024/1545.pdf)

### Abstract

The traditional definition of fully homomorphic encryption (FHE) is not composable, i.e., it does not guarantee that evaluating two (or more) homomorphic computations in a sequence produces correct results. We formally define and investigate a stronger notion of homomorphic encryption which we call "fully composable homomorphic encryption", or "composable FHE". The definition is both simple and powerful: it does not directly involve the evaluation of multiple functions, and yet it supports the arbitrary composition of homomorphic evaluations. On the technical side, we compare the new definition with other definitions proposed in the past, proving both implications and separations, and show how the "bootstrapping" technique of (Gentry, STOC 2009) can be formalized as a method to transform a (non-composable, circular secure) homomorphic encryption scheme into a fully composable one. We use this formalization of bootstrapping to formulate a number of conjectures and open problems.

## 2024/1546

* Title: Bit t-SNI Secure Multiplication Gadget for Inner Product Masking
* Authors: John Gaspoz, Siemen Dhooghe
* [Permalink](https://eprint.iacr.org/2024/1546)
* [Download](https://eprint.iacr.org/2024/1546.pdf)

### Abstract

Masking is a sound countermeasure to protect against differential power analysis. Since the work by Balasch et al. in ASIACRYPT 2012, inner product masking has been explored as an alternative to the well known Boolean masking. In CARDIS 2017, Poussier et al. showed that inner product masking achieves higher-order security versus Boolean masking, for the same shared size, in the bit-probing model. Wang et al. in TCHES 2020 verified the inner product masking's security order amplification in practice and proposed new gadgets for inner product masking. Finally, Wu et al. in TCHES 2022 showed that this security amplification comes from the bit-probing model, but that Wang al.'s gadgets are not higher-order bit-probing secure reducing the computation's practical security. The authors concluded their work with the open question of providing an inner product multiplication gadget which maintains the masking's bit-probing security, and conjectured that such gadget maintains the practical security order amplification of the masking during its computation.

In this paper, we answer positively to Wu et al.'s open problems. We are the first to present a multiplication gadget for inner product masking which is proven secure in the bit-level probing model using the t-Strong Non-Interference (SNI) property. Moreover, we provide practical evidence that the gadget indeed maintains the security amplification of its masking. This is done via an evaluation of an assembly implementation of the gadget on an ARM Cortex-M4 core. We used this implementation to take leakage measurements and show no leakage happens for orders below the gadget's bit-probing security level either for its univariate or multivariate analysis.

## 2024/1547

* Title: HHL for tensor-decomposable matrices
* Authors: Cezary Pilaszewicz, Marian Margraf
* [Permalink](https://eprint.iacr.org/2024/1547)
* [Download](https://eprint.iacr.org/2024/1547.pdf)

### Abstract

We use the HHL algorithm to retrieve a quantum state holding the algebraic normal formal of a Boolean function. Unlike the standard HHL applications, we do not describe the cipher as an exponentially big system of equations. Rather, we perform a set of small matrix inversions which corresponds to the Boolean Möbius transform. This creates a superposition holding information about the ANF in the form: $\ket{\mathcal{A}_{f}} =\frac{1}{C} \sum_{I=0}^{2^n-1} c_I \ket{I}$, where $c_I$ is the coefficient of the ANF and $C$ is a scaling factor. The procedure has a time complexity of $\mathcal{O}(n)$ for a Boolean function with $n$ bit input. We also propose two approaches how some information about the ANF can be extracted from such a state.

## 2024/1548

* Title: Fully-Succinct Arguments over the Integers from First Principles
* Authors: Matteo Campanelli, Mathias Hall-Andersen
* [Permalink](https://eprint.iacr.org/2024/1548)
* [Download](https://eprint.iacr.org/2024/1548.pdf)

### Abstract

Succinct arguments of knowledge allow an untrusted prover to establish that they know a witness for an NP relation. Many recent efficient constructions of such schemes work over arithmetic computations expressed in finite fields.
Several common settings, however, have an extremely simple representation when expressed over the integers (e.g., RSA signatures/accumulators, range checks for committed values, computations over rational numbers). Efficient arguments of knowledge working natively over $\mathbb{Z}$ could be applied to such computations without the overhead from emulating integer arithmetic over a finite field.
We propose the first native construction of SNARKs over the integers that is fully succinct, thus resolving an open problem from Towa and Vergnaud (Asiacrypt 2020). By fully succinct, we mean that \textit{both} the proof size and the verifier's running time should be sublinear in both $|\vec w|$—the size of the witness as a vector of integers—and $\log_2 \lVert \vec w \rVert_\infty$—the size in bits of the largest integer in the witness vector (in absolute value).
As a stepping stone for our results we provide a general theoretical framework for building succinct arguments over the integers.
Its most attractive feature is that it allows to reuse already existing constructions of SNARKs in a modular way and can be used as a starting point for constructions following up our work. We build these systematic foundations by leveraging a common technique in theoretical computer science—fingerprinting—and applying it to a new setting. Our framework consists of two main ingredients: idealized protocols and polynomial commitments such that an object ``committed over the integers'' can however be ``queried modulo $q$'', for a randomly sampled prime $q$.
We obtain our final construction, $\mathbb{Z}$aratan, by lifting the $\mathsf{Spartan}$ construction (Setty, CRYPTO 2020) to the integers and applying a form of polynomial commitment based on the techniques from DARK (Bünz et al., Eurocrypt 2020). $\mathbb{Z}$aratan has a transparent setup, is proven secure in the generic group model for groups of unknown order and can be heuristically made non-interactive in the ROM via the Fiat-Shamir transform.

## 2024/1549

* Title: Universally Composable SNARKs with Transparent Setup without Programmable Random Oracle
* Authors: Christian Badertscher, Matteo Campanelli, Michele Ciampi, Luigi Russo, Luisa Siniscalchi
* [Permalink](https://eprint.iacr.org/2024/1549)
* [Download](https://eprint.iacr.org/2024/1549.pdf)

### Abstract

Non-interactive zero-knowledge (NIZK) proofs allow a prover to convince a verifier about the validity of an NP-statement by sending a single message and without disclosing any additional information (besides the validity of the statement). Single-message cryptographic proofs are very versatile, which has made them widely used both in theory and in practice. This is particularly true for succinct proofs, where the length of the message is sublinear in the size of the NP relation. This versatility, unfortunately, comes at a price, since any NIZK proof system requires some form of setup, like a common reference string. One way to circumvent the need for a setup is by relying on a Random Oracle. Unfortunately, if the Random Oracle is modeled as a Global resource that the simulator is not allowed to program, then it is impossible to obtain a secure NIZK. This impossibility has been circumvented by allowing the simulator (and the real-world adversary) to program the RO, and allowing the honest parties to check, via a special interface, if the RO outputs have been programmed.
In this work, we show that this impossibility can be circumvented by meaningfully weakening the Universal Composability framework following the model proposed by Broadnax et al. (Eurocrypt 2017). In this model, the ideal world functionalities are allowed to interact with oracles that have quasi-polynomial time capabilities.
As our main result, we propose the first composable NIZK proof system that relies on a global (non-programmable) random oracle as its only form of setup. The NIZK scheme we propose is witness-succinct (with proofs logarithmic in the size of the witness). Our results break both the barrier of programmability of the random oracle and of polylogarithmic proof size for UC-secure NIZKs with transparent setups.
We are able to construct our NIZK using the framework proposed by Ganesh et al. (Eurocrypt 2023), which requires—among other building blocks—a polynomial commitment scheme with special features and a polynomial encoding scheme (a primitive that appropriately masks a witness as a polynomial). As a core technical contribution, we show a polynomial commitment of this type using a basic component of Bulletproofs as a building block, as well as a polynomial encoding based on techniques completely different from the ones from Ganesh et al..

## 2024/1550

* Title: MAYO Key Recovery by Fixing Vinegar Seeds
* Authors: Sönke Jendral, Elena Dubrova
* [Permalink](https://eprint.iacr.org/2024/1550)
* [Download](https://eprint.iacr.org/2024/1550.pdf)

### Abstract

As the industry prepares for the transition to post-quantum secure public key cryptographic algorithms, vulnerability analysis of their implementations is gaining importance. A theoretically secure cryptographic algorithm should also be able to withstand the challenges of physical attacks in real-world environments. MAYO is a candidate in the ongoing first round of the NIST post-quantum standardization process for selecting additional digital signature schemes. This paper demonstrates three first-order single-execution fault injection attacks on a MAYO implementation in an ARM Cortex-M4 processor. By using voltage glitching to disrupt the computation of the vinegar seed during the signature generation, we enable the recovery of the secret key directly from the faulty signatures. Our experimental results show that the success rates of the fault attacks in a single execution are 36%, 82%, and 99%, respectively. They emphasize the importance of developing countermeasures against fault attacks prior to the widespread deployment of post-quantum algorithms like MAYO.

## 2024/1551

* Title: SNARKs for Virtual Machines are Non-Malleable
* Authors: Matteo Campanelli, Antonio Faonio, Luigi Russo
* [Permalink](https://eprint.iacr.org/2024/1551)
* [Download](https://eprint.iacr.org/2024/1551.pdf)

### Abstract

Cryptographic proof systems have a plethora of applications: from building other cryptographic tools (e.g., malicious security for MPC protocols) to concrete settings such as private transactions or rollups. In several settings it is important for proof systems to be non-malleable: an adversary should not to be able to modify a proof they have observed into another for a statement for which they do not know the witness.
Proof systems that have been deployed in practice should arguably satisfy this notion: it is crucial in settings such as transaction systems and in order to securely compose proofs with other cryptographic protocols. As a consequence, results on non-malleability should keep up with designs of proofs being deployed.
Recently, Arun et al. proposed $\mathsf{Jolt}$ (Eurocrypt 2024), arguably the first efficient proof system whose architecture is based on the lookup singularity approach (Barry Whitehat, 2022). This approach consists in representing a general computation as a series of table lookups. The final result is a SNARK for a Virtual Machine execution (or SNARK VM). Both SNARK VMs and lookup-singularity SNARKs are architectures with enormous potential and will probably be adopted more and more in the next years (and they already are).
As of today, however, there is no literature regarding the non-malleability of SNARK VMs. The goal of this work is to fill this gap by providing both concrete non-malleability results and a set of technical tools for a more general study of SNARK VMs security (as well as "modular" SNARKs in general). As a concrete result, we study the non-malleability of (an idealized version of) $\mathsf{Jolt}$ and its fundamental building block, the lookup argument $\mathsf{Lasso}$. While connecting our new result on the non-malleability of $\mathsf{Lasso}$ to that of $\mathsf{Jolt}$, we develop a set of tools that enable the composition of non-malleable SNARKs. We believe this toolbox to be valuable in its own right.

## 2024/1552

* Title: Revisiting Keyed-Verification Anonymous Credentials
* Authors: Michele Orrù
* [Permalink](https://eprint.iacr.org/2024/1552)
* [Download](https://eprint.iacr.org/2024/1552.pdf)

### Abstract

Keyed-verification anonymous credentials are widely recognized as among the most efficient tools for anonymous authentication. In this work, we revisit two prominent credential systems: the scheme by Chase et al. (CCS 2014), commonly referred to as CMZ or PS MAC, and the scheme by Barki et al. (SAC 2016), known as BBDT or BBS MAC. We show how to make CMZ statistically anonymous and BBDT compatible with the BBS RFC draft. We provide a comprehensive security analysis for strong(er) properties of unforgeability and anonymity. These properties allow them to be composed with extensions that users can pick and choose. We show that simpler variants satisfying one-more unforgeability can still be anonymous tokens (Kreuter et al., CRYPTO 2020).

To enable faster proofs for complex presentations, we present a compiler that uses an interactive oracle proof and a designated-verifier polynomial commitment to construct a designated-verifier non-interactive argument. For keyed-verification anonymous credentials, designated-verifier proofs suffice since the verifier is known in advance. We explore extensions that could benefit from this approach.

## 2024/1553

* Title: STARK-based Signatures from the RPO Permutation
* Authors: Shahla Atapoor, Cyprien Delpech de Saint Guilhem, Al Kindi
* [Permalink](https://eprint.iacr.org/2024/1553)
* [Download](https://eprint.iacr.org/2024/1553.pdf)

### Abstract

This work describes a digital signature scheme constructed from a zero-knowledge proof of knowledge of a pre-image of the Rescue Prime Optimized (RPO) permutation. The proof of knowledge is constructed with the DEEP-ALI interactive oracle proof combined with the Ben-Sasson--Chiesa--Spooner (BCS) transformation in the random oracle model. The EUF-CMA security of the resulting signature scheme is established from the UC-friendly security properties of the BCS transformation and the pre-image hardness of the RPO permutation.

The implementation of the scheme computes signatures in 13 ms and verifies them in 1 ms on a single core when the BCS transform is implemented with the Blake3 hash function. (The multi-threaded implementation signs in 9.2 ms and also verifies in 1 ms.) These speeds are obtained with parameters achieving 122 bits of average-case security for \( 2^{122} \)-bounded adversaries with access to at most \( 2^{64} \) signatures.

## 2024/1554

* Title: Breaking, Repairing and Enhancing XCBv2 into the Tweakable Enciphering Mode GEM
* Authors: Amit Singh Bhati, Michiel Verbauwhede, Elena Andreeva
* [Permalink](https://eprint.iacr.org/2024/1554)
* [Download](https://eprint.iacr.org/2024/1554.pdf)

### Abstract

Tweakable enciphering modes (TEMs) provide security in a variety of storage and space-critical applications like disk and file-based encryption, and packet-based communication protocols, among others. XCB-AES (known as XCBv2) is specified in the IEEE 1619.2 standard for encryption of sector-oriented storage media and it comes with a proof of security for block-aligned input messages.

In this work, we demonstrate an attack on XCBv2. We show that XCBv2 is $\textit{insecure}$ also for full block messages by presenting a plaintext recovery attack using $\textit{only}$ two queries. We demonstrate that our attack further applies to the HCI and MXCB TEMs, which follow a similar design approach to XCBv2.

We then propose a simple, ``quick'' fix that is not vulnerable to our attack and provably restore the security for XCBv2. Following the responsible disclosure process, we communicated the attack details to IEEE and the authors of XCB-AES. The authors have confirmed the validity of our attack on 02/09/2024.

Our next contribution is to strengthen the provable security of XCBv2 (currently $n/3$ bits). We propose a new modular TEM called GEM which can be seen as a generalization of the Hash-CTR-Hash approach as used in XCB-style and HCTR-style TEMs. We are able to prove that GEM achieves full $n$-bit security using $\textit{only}$ $n$-bit PRP/PRF.

We also give two concrete GEM instantiations: $\mathsf{KohiNoor}$ and $\mathsf{DaryaiNoor}$, both of which are based on AES-128 and GHASH-256, and internally use variants of the CTR-based weak pseudorandom functions GCTR-3 and SoCTR, respectively. SoCTR uses AES-128 and GCTR-3 is based on $\mathsf{ButterKnife}$-256. Our security proofs show that both $\mathsf{KohiNoor}$ and $\mathsf{DaryaiNoor}$ provide full $n$-bit security. From applications perspective, $\mathsf{DaryaiNoor}$ addresses the need for reusing classical components, while $\mathsf{KohiNoor}$ enhances performance by leveraging a more modern primitive based on the AES/Deoxys round function.

Our implementation demonstrates competitive performance: For typical 4KiB sector size, $\mathsf{KohiNoor}$'s performance is on par with AES$_{6}$-CTET+, yet achieving higher standard security guarantees. $\mathsf{DaryaiNoor}$ is on par with AES-CTET+ performance-wise while also maintaining higher security with standard components. Our GEM instances triple the security margin of XCBv2 and double that of HCTR2 at the cost of performance loss of only $12\%$ ($\mathsf{KohiNoor}$) and $68\%$ ($\mathsf{DaryaiNoor}$) for 4KiB messages.

## 2024/1555

* Title: Private Laconic Oblivious Transfer with Preprocessing
* Authors: Rishabh Bhadauria, Nico Döttling, Carmit Hazay, Chuanwei Lin
* [Permalink](https://eprint.iacr.org/2024/1555)
* [Download](https://eprint.iacr.org/2024/1555.pdf)

### Abstract

Laconic cryptography studies two-message protocols that securely compute on large amounts of data with minimal communication cost. Laconic oblivious transfer (OT) is a central primitive where the receiver's input is a large database $\mathsf{DB}$ and the sender's inputs are two messages $m_0$, $m_1$ along with an index $i$, such that the receiver learns the message determined by the choice bit $\mathsf{DB}_i$. OT becomes even more useful for secure computation when considering its laconic variants, which offer succinctness and round optimality. However, existing constructions are not practically efficient because they rely on heavy cryptographic machinery and non-black-box techniques.

In this work, we initiate the study of laconic OT correlations, where the model allows an offline phase to generate the correlations later used in a lightweight online phase. Our correlation is conceptually simple, captured by an inner product computation, and enables us to achieve a private laconic OT protocol where the sender's index $i$ is also hidden from the receiver. Our construction is the first private laconic OT with database-dependent preprocessing based solely on symmetric-key assumptions, achieving sublinear online computational complexity for the receiver. Furthermore, we enhance our construction with updatability and receiver privacy. Finally, we demonstrate the applications of private laconic OT to laconic function evaluation for RAM programs and laconic private set intersection with preprocessing.

## 2024/1556

* Title: The module action for isogeny based cryptography
* Authors: Damien Robert
* [Permalink](https://eprint.iacr.org/2024/1556)
* [Download](https://eprint.iacr.org/2024/1556.pdf)

### Abstract

We extend the usual ideal action on oriented elliptic curves to a (Hermitian) module action on oriented (polarised) abelian varieties. Oriented abelian varieties are naturally enriched in $R$-modules, and our module action comes from the canonical power object construction on categories enriched in a closed symmetric monoidal category. In particular our action is canonical and gives a fully fledged symmetric monoidal action. Furthermore, we give algorithms to compute this action in practice, generalising the usual algorithms in rank~$1$.

The action allows us to unify in the same framework, on the one hand isogeny based cryptography based on ordinary or oriented elliptic curves, and on the other hand the one based on supersingular elliptic curves defined over $\mathbb{F}_{p^2}$. In particular, from our point of view, supersingular elliptic curves over $\mathbb{F}_p$ are given by a rank~$1$ module action, while (the Weil restriction) of those defined over $\mathbb{F}_{p^2}$ are given by a rank~$2$ module action. As a consequence, rank~$2$ module action inversion is at least as hard as the supersingular isogeny path problem.

We thus propose to use Hermitian modules as an avatar of a cryptographic symmetric monoidal action framework. This generalizes the more standard cryptographic group action framework, and still allows for a NIKE (Non Interactive Key Exchange). The main advantage of our action is that, presumably, Kuperberg's algorithm does not apply. Compared to CSIDH, this allows for more compact keys and much better scaling properties.

In practice, we propose the key exchange scheme $\otimes$-MIKE (Tensor Module Isogeny Key Exchange). Alice and Bob start from a supersingular elliptic curve $E_0/\mathbb{F}_p$ and both compute a $2^n$-isogeny over $\mathbb{F}_{p^2}$. They each send the $j$-invariant of their curve. Crucially, unlike SIDH, no torsion information at all is required. Their common secret, given by the module action, is then a dimension~$4$ principally polarised abelian variety. We obtain a very compact post-quantum NIKE: only 64B for NIST level~$1$ security.

## 2024/1557

* Title: Tightly Secure Threshold Signatures over Pairing-Free Groups
* Authors: Renas Bacho, Benedikt Wagner
* [Permalink](https://eprint.iacr.org/2024/1557)
* [Download](https://eprint.iacr.org/2024/1557.pdf)

### Abstract

Threshold signatures have been drawing lots of attention in recent years. Of particular interest are threshold signatures that are proven secure under adaptive corruptions (NIST Call 2023). Sadly, existing constructions with provable adaptive security suffer from at least one of the following drawbacks: (i) strong idealizations such as the algebraic group model (AGM), (ii) an unnatural restriction on the corruption threshold being $t/2$ where $t$ is the signing threshold, or (iii) prohibitively large security loss under established assumptions. Notably, point (iii) has received little to no attention in the literature on this subject.

In this work, we introduce Twinkle-T, a new threshold signature scheme which overcomes these limitations. Twinkle-T is the first scheme to have a fully tight security proof under up to $t$ adaptive corruptions without relying on the AGM. It also has a signing protocol consisting of only three rounds and thus matches the currently best threshold signature with full adaptive security Twinkle (Eurocrypt 2024) in the pairing-free discrete logarithm setting. We prove security from a standard non-interactive assumption, namely, the Decisional Diffie-Hellman (DDH) assumption.

## 2024/1558

* Title: Understanding Leakage in Searchable Encryption: a Quantitative Approach
* Authors: Alexandra Boldyreva, Zichen Gui, Bogdan Warinschi
* [Permalink](https://eprint.iacr.org/2024/1558)
* [Download](https://eprint.iacr.org/2024/1558.pdf)

### Abstract

Searchable encryption, or more generally, structured encryption, permits search over encrypted data. It is an important cryptographic tool for securing cloud storage. The standard security notion for structured encryption mandates that a protocol leaks nothing about the data or queries, except for some allowed leakage, defined by the leakage function. This is due to the fact that some leakage is unavoidable for efficient schemes. Unfortunately, it was shown by numerous works that even innocuous-looking leakage can often be exploited by attackers to undermine users' privacy and recover their queries and/or data, despite the structured encryption schemes being provably secure. Nevertheless, the standard security remains the go-to notion used to show the "security" of structured encryption schemes. While it is not likely that researchers will design practical structured encryption schemes with no leakage, it is not satisfactory that very few works study ways to assess leakage. This work proposes a novel framework to quantify leakage. Our methodology is inspired by the quantitative information flow, and we call our method $q$-leakage analysis. We show how $q$-leakage analysis is related to the standard security.. We also demonstrate the usefulness of $q$-leakage analysis by analyzing the security of two existing schemes with complex leakage functions.

## 2024/1559

* Title: Mind the Composition of Toffoli Gates: Structural Algebraic Distinguishers of ARADI
* Authors: Emanuele Bellini, Mohamed Rachidi, Raghvendra Rohit, Sharwan K. Tiwari
* [Permalink](https://eprint.iacr.org/2024/1559)
* [Download](https://eprint.iacr.org/2024/1559.pdf)

### Abstract

This paper reveals a critical flaw in the design of ARADI, a recently proposed low-latency block cipher by NSA researchers -- Patricia Greene, Mark Motley, and Bryan Weeks. The weakness exploits the specific composition of Toffoli gates in the round function of ARADI's nonlinear layer, and it allows the extension of a given algebraic distinguisher to one extra round without any change in the data complexity. More precisely, we show that the cube-sum values, though depending on the secret key bits, are always equal in two of the state words. Such a structural property is difficult to obtain by the direct application of division property and has never been seen before in any state-of-the-art block cipher. We call this structural property \textit{weakly-composed-Toffoli gates}, and introduce a theoretical framework which can describe it in general terms. We present algebraic distinguishers that reach 8 out of 16 rounds of ARADI. Most notably, we show that these distinguishers have better data complexities than the division property-based distinguishers for the same number of rounds. We further investigate whether changing the linear layer or the order of composition of Toffoli gates could avoid this property. We give a negative answer to the same and show that it is impossible to prevent this structural property unless the nonlinear layer is re-designed. As a side result, we provide a key-recovery attack on 10 rounds ARADI with $2^{124}$ data and $2^{177}$ time for a 256-bit key. Our work highlights the significance of security analysis during the cipher design phase, and shows that these strong structural distinguishers could have been avoided during this phase.

## 2024/1560

* Title: Revisiting Shuffle-Based Private Set Unions with Reduced Communication
* Authors: Jiseung Kim, Hyung Tae Lee, Yongha Son
* [Permalink](https://eprint.iacr.org/2024/1560)
* [Download](https://eprint.iacr.org/2024/1560.pdf)

### Abstract

A Private Set Union (PSU) allows two parties having sets $X$ and $Y$ to securely compute the union $X \cup Y$ while revealing no additional information. Recently, there have been proposed so-called shuffle-based PSU protocols due to Garimella et. al. (PKC'21) and Jia et. al. (USENIX'22).
Except a few base oblivious transfers, those proposals are fully based on symmetric key primitives and hence enjoy quite low computation costs. However, they commonly have drawbacks on large communication cost of $O(\ell n\log n)$ with input set size $n$ and $\ell \ge O(\lambda + \log n)$ where $\lambda$ is a statistical security parameter.

We propose two optimizations for each work that reduce communication cost while maintaining strength in computation cost; the first one optimizes Garimella et. al. to have $O(\ell n + n \log n)$, and the second one optimizes Jia et.. al. by reducing the concrete value of $\ell$ by $\log n$. Concretely, the first (second, resp) optimization provides $3.3 - 3.9$x ($1.7 - 1.8$x, resp) lower communication input set sizes $n = 2^{16} - 2^{20}$.

We demonstrate by comprehensive analysis and implementation that our optimization leads to better PSU protocol, compared to the state-of-the-art proposal of Zhang et. al. (USENIX'23) as well as previous shuffle-based PSUs. As a concrete amount of improvement, we see $1.4-1.5$x speed up for $100$Mbps network, and $1.8-2.2$x speed up for $10$Mbps network on input set sizes $n = 2^{16} - 2^{20}$.

## 2024/1561

* Title: FLUENT: A Tool for Efficient Mixed-Protocol Semi-Private Function Evaluation
* Authors: Daniel Günther, Joachim Schmidt, Thomas Schneider, Hossein Yalame
* [Permalink](https://eprint.iacr.org/2024/1561)
* [Download](https://eprint.iacr.org/2024/1561.pdf)

### Abstract

In modern business to customer interactions, handling private or confidential data is essential. Private Function Evaluation (PFE) protocols ensure the privacy of both the customers' input data and the business' function evaluated on it which is often sensitive intellectual property (IP). However, fully hiding the function in PFE results in high performance overhead. Semi-Private Function Evaluation (SPFE) is a generalization of PFE to only partially hide the function, whereas specific non-critical components remain public. Our paper introduces a novel framework designed to make SPFE accessible to non-experts and practical for real-world deployments.

To achieve this, we improve on previous SPFE solutions in two aspects.
First, we enhance the developer experience by leveraging High-Level Synthesis (HLS), making our tool more user-friendly than previous SPFE frameworks.
Second, we achieve a \(2 \times\) speedup compared to the previous state-of-the-art through more efficient underlying constructions and the usage of Lookup Tables (LUTs).

We evaluate the performance of our framework in terms of communication and runtime efficiency. Our final implementation is available as an open-source project, aiming to bridge the gap between advanced cryptographic protocols and their practical application in industry scenarios.

## 2024/1562

* Title: Fully Privacy-preserving Billing Models for Peer-to-Peer Electricity Trading Markets
* Authors: Akash Madhusudan, Mustafa A. Mustafa, Hilder V.L. Pereira, Erik Takke
* [Permalink](https://eprint.iacr.org/2024/1562)
* [Download](https://eprint.iacr.org/2024/1562.pdf)

### Abstract

Peer-to-peer energy trading markets enable users to exchange electricity, directly offering them increased financial benefits. However, discrepancies often arise between the electricity volumes committed to in trading auctions and the volumes actually consumed or injected. Solutions designed to address this issue often require access to sensitive information that should be kept private.

This paper presents a novel, fully privacy-preserving billing protocol designed to protect users' sensitive consumption and production data in the context of billing protocols for energy trading. Leveraging advanced cryptographic techniques, including fully homomorphic encryption (FHE) and pseudorandom zero sharing (PRZS), our protocol ensures robust security and confidentiality while addressing the critical issue of managing discrepancies between promised and actual electricity volumes. The proposed protocol guarantees that users' sensitive information remains inaccessible to external parties, including the trading platform and billing server. By utilizing FHE, the protocol allows computations on encrypted data without compromising privacy, while PRZS ensures secure aggregation of individual discrepancies of each household. This combination of cryptographic primitives maintains data privacy and enhances billing accuracy, even when fluctuations in energy supply and demand occur.

We analyze real-time consumption and production data from 100 households to experimentally validate the effectiveness and efficiency of our billing model. By implementing a flexible framework compatible with any billing method, we demonstrate that our protocol can accurately compute individual bills for 100 households in approximately 0.17 seconds.

## 2024/1563

* Title: Optimized One-Dimensional SQIsign Verification on Intel and Cortex-M4
* Authors: Marius A. Aardal, Gora Adj, Arwa Alblooshi, Diego F. Aranha, Isaac A. Canales-Martínez, Jorge Chavez-Saab, Décio Luiz Gazzoni Filho, Krijn Reijnders, Francisco Rodríguez-Henríquez
* [Permalink](https://eprint.iacr.org/2024/1563)
* [Download](https://eprint.iacr.org/2024/1563.pdf)

### Abstract

SQIsign is a well-known post-quantum signature scheme due to its small combined signature and public-key size. However, SQIsign suffers from notably long signing times, and verification times are not short either. To improve this, recent research has explored both one-dimensional and two-dimensional variants of SQIsign, each with distinct characteristics. In particular, SQIsign2D’s efficient signing and
verification times have made it a focal point of recent research. However, the absence of an optimized one-dimensional verification implementation hampers a thorough comparison between these different variants.

This work bridges this gap in the literature: we provide a state-of-the-art implementation of one-dimensional SQIsign verification, including novel optimizations. We report a record-breaking one-dimensional SQIsign verification time of 8.6 Ice Lake Mcycles, closely matching SQIsign2D. For uncompressed signatures, the signature size doubles and we verify in only 5.6 Mcycles. Taking advantage of the inherent parallelism available in isogeny computations, we present 5-core variants that can go as low as 1.3 Mcycles. Furthermore, we present the first implementation that supports both 32-bit and 64-bit processors. It includes optimized assembly code for the Cortex-M4 and has been integrated with the pqm4 project. Our results motivate further research into one-dimensional SQIsign, as it boasts unique features among isogeny-based schemes.

## 2024/1564

* Title: A Simple Framework for Secure Key Leasing
* Authors: Fuyuki Kitagawa, Tomoyuki Morimae, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2024/1564)
* [Download](https://eprint.iacr.org/2024/1564.pdf)

### Abstract

Secure key leasing (a.k.a. key-revocable cryptography) enables us to lease a cryptographic key as a quantum state in such a way that the key can be later revoked in a verifiable manner. We propose a simple framework for constructing cryptographic primitives with secure key leasing via the certified deletion property of BB84 states. Based on our framework, we obtain the following schemes.

- A public key encryption scheme with secure key leasing that has classical revocation based on any IND-CPA secure public key encryption scheme. Prior works rely on either quantum revocation or stronger assumptions such as the quantum hardness of the learning with errors (LWE) problem.

- A pseudorandom function with secure key leasing that has classical revocation based on one-way functions. Prior works rely on stronger assumptions such as the quantum hardness of the LWE problem.

- A digital signature scheme with secure key leasing that has classical revocation based on the quantum hardness of the short integer solution (SIS) problem. Our construction has static signing keys, i.e., the state of a signing key almost does not change before and after signing. Prior constructions either rely on non-static signing keys or indistinguishability obfuscation to achieve a stronger goal of copy-protection.

In addition, all of our schemes remain secure even if a verification key for revocation is leaked after the adversary submits a valid certificate of deletion. To our knowledge, all prior constructions are totally broken in this setting. Moreover, in our view, our security proofs are much simpler than those for existing schemes.

## 2024/1565

* Title: Fiat-Shamir in the Wild
* Authors: Hieu Nguyen, Uyen Ho, Alex Biryukov
* [Permalink](https://eprint.iacr.org/2024/1565)
* [Download](https://eprint.iacr.org/2024/1565.pdf)

### Abstract

The Fiat-Shamir transformation is a key technique for removing interactivity from cryptographic proof systems in real-world applications. In this work, we discuss five types of Fiat-Shamir-related protocol design errors and illustrate them with concrete examples mainly taken from real-life applications. We discuss countermeasures for such vulnerabilities.

## 2024/1566

* Title: Dynamic zk-SNARKs
* Authors: Weijie Wang, Charalampos Papamanthou, Shravan Srinivasan, Dimitrios Papadopoulos
* [Permalink](https://eprint.iacr.org/2024/1566)
* [Download](https://eprint.iacr.org/2024/1566.pdf)

### Abstract

In this work, we put forth the notion of dynamic zk-SNARKs. A dynamic zk-SNARK is a zk-SNARK that has an additional update algorithm. The update algorithm takes as input a valid source statement-witness pair $(x,w)\in \mathcal{L}$ along with a verifying proof $\pi$, and a valid target statement-witness pair $(x',w')\in \mathcal{L}$. It outputs a verifying proof $\pi'$ for $(x',w')$ in sublinear time (for $(x,w)$ and $(x',w')$ with small Hamming distance) potentially with the help of a data structure. To the best of our knowledge, none of the commonly-used zk-SNARKs are dynamic---a single update in $(x,w)$ can be handled only by recomputing the proof, which requires at least linear time. After presenting the formal definition of dynamic zk-SNARKs, we provide two constructions. The first one is based on recursive SNARKs and has $O(\log n)$ update time. However it suffers from heuristic security---it must encode the random oracle in the SNARK circuit. The second one and our central contribution, $\mathsf{Dynaverse}$, is based solely on KZG commitments and has $O(\sqrt{n}\log n)$ update time. Our preliminary evaluation shows, that, while worse asymptotically, $\mathsf{Dynaverse}$ outperforms the recursive-based approach by at least one order of magnitude.

## 2024/1567

* Title: A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID
* Authors: Amit Behera, Giulio Malavolta, Tomoyuki Morimae, Tamer Mour, Takashi Yamakawa
* [Permalink](https://eprint.iacr.org/2024/1567)
* [Download](https://eprint.iacr.org/2024/1567.pdf)

### Abstract

While in classical cryptography, one-way functions (OWFs) are widely regarded as the “minimal assumption,” the situation in quantum cryptography is less clear. Recent works have put forward two concurrent candidates for the minimal assumption in quantum cryptography: One-way state generators (OWSGs), postulating the existence of a hard search problem with an efficient verification algorithm, and EFI pairs, postulating the existence of a hard distinguishing problem. Two recent papers [Khurana and Tomer STOC’24; Batra and Jain FOCS’24] showed that OWSGs imply EFI pairs, but the reverse direction remained open. In this work, we give strong evidence that the opposite direction does not hold: We show that there is a quantum unitary oracle relative to which EFI pairs exist, but OWSGs do not. In fact, we show a slightly stronger statement that holds also for EFI pairs that output classical bits (QEFID).
As a consequence, we separate, via our oracle, QEFID, and one-way puzzles from OWSGs and several other Microcrypt primitives, including efficiently verifiable one-way puzzles and unclonable state generators. In particular, this solves a problem left open in [Chung, Goldin, and Gray Crypto’24].
Using similar techniques, we also establish a fully black-box separation (which is slightly weaker than an oracle separation) between private-key quantum money schemes and QEFID pairs.
One conceptual implication of our work is that the existence of an efficient verification algorithm may lead to qualitatively stronger primitives in quantum cryptography.

## 2024/1568

* Title: Oracle Separation Between Quantum Commitments and Quantum One-wayness
* Authors: John Bostanci, Boyang Chen, Barak Nehoran
* [Permalink](https://eprint.iacr.org/2024/1568)
* [Download](https://eprint.iacr.org/2024/1568.pdf)

### Abstract

We show that there exists a unitary quantum oracle relative to which quantum commitments exist but no (efficiently verifiable) one-way state generators exist. Both have been widely considered candidates for replacing one-way functions as the minimal assumption for cryptography—the weakest cryptographic assumption implied by all of computational cryptography. Recent work has shown that commitments can be constructed from one-way state generators, but the other direction has remained open. Our results rule out any black-box construction, and thus settle this crucial open problem, suggesting that quantum commitments (as well as its equivalency class of EFI pairs, quantum oblivious transfer, and secure quantum multiparty computation) appear to be strictly weakest among all known cryptographic primitives.

## 2024/1569

* Title: The Supersingular Isogeny Path and Endomorphism Ring Problems: Unconditional Reductions
* Authors: Maher Mamah
* [Permalink](https://eprint.iacr.org/2024/1569)
* [Download](https://eprint.iacr.org/2024/1569.pdf)

### Abstract

In this paper we study several computational problems related to current post-quantum cryptosystems based on isogenies between supersingular elliptic curves. In particular we prove that the supersingular isogeny path and endomorphism ring problems are unconditionally equivalent under polynomial time reductions. We show that access to a factoring oracle is sufficient to solve the Quaternion path problem of KLPT and prove that these problems are equivalent, where previous results either assumed heuristics or the generalised Riemann Hypothesis (GRH). Consequently, given Shor’s quantum algorithm for factorisation, our results yield unconditional quantum polynomial reductions between the isogeny path and EndRing problems. Recently these reductions have become foundational for the security of isogeny-based cryptography