[digest] 2024 Week 29

## In this issue

1. [2023/1384] Application of Mordell-Weil lattices with large ...
2. [2024/550] Fast Parallelizable Misuse-Resistant Authenticated ...
3. [2024/1147] A reduction from Hawk to the principal ideal ...
4. [2024/1148] On hermitian decomposition lattices and the module- ...
5. [2024/1149] Improved High-Order Masked Generation of Masking ...
6. [2024/1150] Finding Practical Parameters for Isogeny-based ...
7. [2024/1151] Privacy-Preserving Data Deduplication for Enhancing ...
8. [2024/1152] Secure Multiparty Computation of Symmetric ...
9. [2024/1153] Designated-Verifier zk-SNARKs Made Easy
10. [2024/1154] Blockchain Space Tokenization
11. [2024/1155] Cross Ledger Transaction Consistency for Financial ...
12. [2024/1156] On affine forestry over integral domains and ...
13. [2024/1157] Shift-invariant functions and almost liftings
14. [2024/1158] A Note on `` Provably Secure and Lightweight ...
15. [2024/1159] LaPSuS – A Lattice-Based Private Stream Aggregation ....
16. [2024/1160] Post-Quantum Access Control with Application to ...
17. [2024/1161] On the Concrete Security of Non-interactive FRI
18. [2024/1162] Practical Traceable Receipt-Free Encryption
19. [2024/1163] On the Number of Restricted Solutions to ...
20. [2024/1164] A Crack in the Firmament: Restoring Soundness of ...
21. [2024/1165] Respire: High-Rate PIR for Databases with Small Records
22. [2024/1166] On the Relationship between FuncCPA and FuncCPA+
23. [2024/1167] Expanding the Toolbox: Coercion and Vote-Selling at ...
24. [2024/1168] Time is not enough: Timing Leakage Analysis on ...
25. [2024/1169] Attacking Tropical Stickel Protocol by MILP and ...
26. [2024/1170] Rudraksh: A compact and lightweight post-quantum ...
27. [2024/1171] Tight Time-Space Tradeoffs for the Decisional ...
28. [2024/1172] Generalized class group actions on oriented ...
29. [2024/1173] Cryptanalysis of Rank-2 Module-LIP with Symplectic ...
30. [2024/1174] Grafted Trees Bear Better Fruit: An Improved ...
31. [2024/1175] AVeCQ: Anonymous Verifiable Crowdsourcing with ...
32. [2024/1176] A zero-trust swarm security architecture and protocols
33. [2024/1177] Cryptanalysis of two post-quantum authenticated key ...
34. [2024/1178] Towards Quantum-Safe Blockchain: Exploration of PQC ...

## 2023/1384

* Title: Application of Mordell-Weil lattices with large kissing numbers to acceleration of multi-scalar multiplication on elliptic curves
* Authors: Dmitrii Koshelev
* [Permalink](https://eprint.iacr.org/2023/1384)
* [Download](https://eprint.iacr.org/2023/1384.pdf)

### Abstract

This article aims to speed up (the precomputation stage of) multi-scalar multiplication (MSM) on ordinary elliptic curves of $j$-invariant $0$ with respect to specific ''independent'' (a.k.a. ''basis'') points. For this purpose, so-called Mordell--Weil lattices (up to rank $8$) with large kissing numbers (up to $240$) are employed. In a nutshell, the new approach consists in obtaining more efficiently a considerable number (up to $240$) of certain elementary linear combinations of the ``independent'' points. By scaling the point (re)generation process, it is thus possible to get a significant performance gain.. As usual, the resulting curve points can be then regularly used in the main stage of an MSM algorithm to avoid repeating computations. Seemingly, this is the first usage of lattices with large kissing numbers in cryptography, while such lattices have already found numerous applications in other mathematical domains. Without exaggeration, the article results can strongly affect performance of today's real-world elliptic curve cryptography, since MSM is a widespread primitive (often the unique bottleneck) in modern protocols. Moreover, the new (re)generation technique is prone to further improvements by considering Mordell--Weil lattices with even greater kissing numbers.



## 2024/550

* Title: Fast Parallelizable Misuse-Resistant Authenticated Encryption: Low Latency (Decryption-Fast) SIV
* Authors: Mustafa Khairallah
* [Permalink](https://eprint.iacr.org/2024/550)
* [Download](https://eprint.iacr.org/2024/550.pdf)

### Abstract

MRAE security is an important goal for many AEAD applications where the nonce uniqueness cannot be maintained and security risks are significant. However, MRAE schemes can be quite expensive. Two of the SoTA MRAE-secure schemes; Deoxys-II and AES-GCM-SIV rely on internal parallelism and special instructions to achieve competitive performance. However, they both suffer from the same bottleneck, they have at least one call to the underlying primitive that cannot be parallelized to any other call. Romulus-M and LMDAE are two other more recent MRAE secure schemes based on TBCs that target low area hardware. However, they are unparallelizable so they are slower than their counterparts.

In this paper, we present two new AEAD modes and four instantiations based on Tweakable Block Ciphers. These new modes target equipping high-speed applications on parallel platforms with nonce misuse resistant AEAD (MRAE). The first mode, LLSIV, targets similar performance on single-core platforms to SCT-2, while eliminating the bottlenecks that make SCT-2 not fully parallelizable. The enhanced parallelism allows LLSIV to encrypt significantly more blocks on parallel platforms, compared to SCT-2, in the same amount of time. LLSIV is based on the NaT MAC, where each ciphertext block can itself be viewed as an instance of NaT when the plaintext is prepended with
. The trade-off is that LLSIV requires the inverse function of the TBC. However, the inverse function is used only once per message and we demonstrate that for parallel implementations it represents a very small overhead.

We give an instantiation of LLSIV based on the SKINNY-128-384 TBC, and a pruned scheme, dubbed pLLSIV, which targets enhanced performance compared both SCT-2 and LLSIV on all platforms, while having reduced security claims. It relies on the recently popularized prove-then-prune methodology to take full advantage of the properties of LLSIV. This leads to a significant performance improvement, making pLLSIV even faster than online TBC-based schemes that are not MRAE-secure. Last but not least, we give an instantiation that uses the primitives used in AES-GCM-SIV: the PolyVal hash function and AES. Our instantiation is faster than AES-GCM-SIV on all platforms and have better bounds. On the other hand, it relies on the ideal cipher model as it uses the ICE TBC proposed as part of the Remus AEAD design.

The second mode we describe is LLDFV. It uses ideas from LLSIV combined the Decryption-Fast SIV (DFV) framework proposed recently by Minematsu. The goal is to reduce the number of calls to the TBC by one, while making the scheme as parallelizable as LLSIV. This makes the scheme faster that DFV on all platforms.



## 2024/1147

* Title: A reduction from Hawk to the principal ideal problem in a quaternion algebra
* Authors: Clémence Chevignard, Pierre-Alain Fouque, Guilhem Mureau, Alice Pellet-Mary, Alexandre Wallet
* [Permalink](https://eprint.iacr.org/2024/1147)
* [Download](https://eprint.iacr.org/2024/1147.pdf)

### Abstract

In this article we present a non-uniform reduction from rank-2 module-LIP over Complex Multiplication fields, to a variant of the Principal Ideal Problem, in some fitting quaternion algebra. This reduction is classical deterministic polynomial-time in the size of the inputs. The quaternion algebra in which we need to solve the variant of the principal ideal problem depends on the parameters of the module-LIP problem, but not on the problem’s instance.. Our reduction requires the knowledge of some special elements of this quaternion algebras, which is why it is non-uniform.

In some particular cases, these elements can be computed in polynomial time, making the reduction uniform. This is in particular the case for the Hawk signature scheme: we show that breaking Hawk is no harder than solving a variant of the principal ideal problem in a fixed quaternion algebra (and this reduction is uniform).



## 2024/1148

* Title: On hermitian decomposition lattices and the module-LIP problem in rank 2
* Authors: Thomas Espitau, Heorhii Pliatsok
* [Permalink](https://eprint.iacr.org/2024/1148)
* [Download](https://eprint.iacr.org/2024/1148.pdf)

### Abstract

In this short note, we introduce a specific class of rank two lattices over CM fields endowed with additional symmetries, which are involved in the decomposition of algebraic integers in Hermitian squares. As an application, we show an elementary reduction from the module-LIP problem in rank 2 over a CM or totally real number field to the finding of a square basis in such lattices.



## 2024/1149

* Title: Improved High-Order Masked Generation of Masking Vector and Rejection Sampling in Dilithium
* Authors: Jean-Sébastien Coron, François Gérard, Tancrède Lepoint, Matthias Trannoy, Rina Zeitoun
* [Permalink](https://eprint.iacr.org/2024/1149)
* [Download](https://eprint.iacr.org/2024/1149.pdf)

### Abstract

In this work, we introduce enhanced high-order masking techniques tailored for Dilithium, the post-quantum signature scheme recently standardized by NIST. We improve the masked generation of the masking vector $\vec{y}$, based on a fast Boolean-to-arithmetic conversion modulo $q$. We also describe an optimized gadget for the high-order masked rejection sampling, with a complexity independent from the size of the modulus $q$. We prove the security of our gadgets in the classical ISW $t$-probing model. Finally, we detail our open-source C implementation of these gadgets integrated into a fully masked Dilithium implementation, and provide an efficiency comparison with previous works.



## 2024/1150

* Title: Finding Practical Parameters for Isogeny-based Cryptography
* Authors: Maria Corte-Real Santos, Jonathan Komada Eriksen, Michael Meyer, Francisco Rodríguez-Henríquez
* [Permalink](https://eprint.iacr.org/2024/1150)
* [Download](https://eprint.iacr.org/2024/1150.pdf)

### Abstract

Isogeny-based schemes often come with special requirements on the field of definition of the involved elliptic curves. For instance, the efficiency of SQIsign, a promising candidate in the NIST signature standardisation process, requires a large power of two and a large smooth integer $T$ to divide $p^2-1$ for its prime parameter $p$.

We present two new methods that combine previous techniques for finding suitable primes: sieve-and-boost and XGCD-and-boost. We use these methods to find primes for the NIST submission of SQIsign. Furthermore, we show that our methods are flexible and can be adapted to find suitable parameters for other isogeny-based schemes such as AprèsSQI or POKE. For all three schemes, the parameters we present offer the best performance among all parameters proposed in the literature.



## 2024/1151

* Title: Privacy-Preserving Data Deduplication for Enhancing Federated Learning of Language Models
* Authors: Aydin Abadi, Vishnu Asutosh Dasu, Sumanta Sarkar
* [Permalink](https://eprint.iacr.org/2024/1151)
* [Download](https://eprint.iacr.org/2024/1151.pdf)

### Abstract

Deduplication is a vital preprocessing step that enhances machine learning model performance and saves training time and energy. However, enhancing federated learning through deduplication poses challenges, especially regarding scalability and potential privacy violations if deduplication involves sharing all clients’ data. In this paper, we address the problem of deduplication in a federated setup by introducing a pioneering protocol, Efficient Privacy-Preserving Multi-Party Deduplication (EP-MPD). It efficiently removes duplicates from multiple clients’ datasets without compromising data privacy. EP-MPD is constructed in a modular fashion, utilizing two novel variants of the Private Set Intersection protocol. Our extensive experiments demonstrate the significant benefits of deduplication in federated learning of large language models. For instance, we observe up to 19.61% improvement in perplexity and up to 27.95% reduction in running time. EP-MPD effectively balances privacy and performance in federated learning, making it a valuable solution for large-scale applications.



## 2024/1152

* Title: Secure Multiparty Computation of Symmetric Functions with Polylogarithmic Bottleneck Complexity and Correlated Randomness
* Authors: Reo Eriguchi
* [Permalink](https://eprint.iacr.org/2024/1152)
* [Download](https://eprint.iacr.org/2024/1152.pdf)

### Abstract

Bottleneck complexity is an efficiency measure of secure multiparty computation (MPC) protocols introduced to achieve load-balancing in large-scale networks, which is defined as the maximum communication complexity required by any one player within the protocol execution. Towards the goal of achieving low bottleneck complexity, prior works proposed MPC protocols for computing symmetric functions in the correlated randomness model, where players are given input-independent correlated randomness in advance. However, the previous protocols with polylogarithmic bottleneck complexity in the number of players $n$ require a large amount of correlated randomness that is linear in $n$, which limits the per-party efficiency as receiving and storing correlated randomness are the bottleneck for efficiency. In this work, we present for the first time MPC protocols for symmetric functions such that bottleneck complexity and the amount of correlated randomness are both polylogarithmic in $n$, assuming collusion of size at most $n-o(n)$ players. Furthermore, one of our protocols is even computationally efficient in that each player performs only $\mathrm{polylog}(n)$ arithmetic operations while the computational complexity of the previous protocols is $O(n)$. Technically, our efficiency improvements come from novel protocols based on ramp secret sharing to realize basic functionalities with low bottleneck complexity, which we believe may be of interest beyond their applications to secure computation of symmetric functions.



## 2024/1153

* Title: Designated-Verifier zk-SNARKs Made Easy
* Authors: Chen Li, Fangguo Zhang
* [Permalink](https://eprint.iacr.org/2024/1153)
* [Download](https://eprint.iacr.org/2024/1153.pdf)

### Abstract

Zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) is a kind of proof system that enables a prover to convince a verifier that an NP statement is true efficiently. In the last decade, various studies made a lot of progress in constructing more efficient and secure zk-SNARKs. Our research focuses on designated-verifier zk-SNARKs, where only the verifier knowing some secret verification state can be convinced by the proof. A natural idea of getting a designated-verifier zk-SNARK is encrypting a publicly-verifiable zk-SNARK's proof via public-key encryption. This is also the core idea behind the well-known transformation proposed by Bitansky et al. in TCC 2013 to obtain designated-verifier zk-SNARKs. However, the transformation only applies to zk-SNARKs which requires the complicated trusted setup phase and sticks on storage-expensive common reference strings. The loss of the secret verification state also makes the proof immediately lose the designated-verifier property.

To address these issues, we first define "strong designated-verifier" considering the case where the adversary has access to the secret verification state, then propose a construction of strong designated-verifier zk-SNARKs. The construction inspired by designated verifier signatures based on two-party ring signatures does not use encryption and can be applied on any public-verifiable zk-SNARKs to yield a designated-verifiable variant. We introduce our construction under the circuit satisfiability problem and implement it in Circom, then test it on different zk-SNARKs, showing the validity of our construction.



## 2024/1154

* Title: Blockchain Space Tokenization
* Authors: Aggelos Kiayias, Elias Koutsoupias, Philip Lazos, Giorgos Panagiotakos
* [Permalink](https://eprint.iacr.org/2024/1154)
* [Download](https://eprint.iacr.org/2024/1154.pdf)

### Abstract

Handling congestion in blockchain systems is a fundamental problem given that the security and decentralization objectives of such systems lead to designs that compromise on (horizontal) scalability (what sometimes is referred to as the ``blockchain trilemma''). Motivated by this, we focus on the question whether it is possible to design a  transaction inclusion policy for block producers  that facilitates  fee and delay predictability while being incentive compatible at the same time.


Reconciling these three properties is seemingly paradoxical given that the dominant approach to transaction processing is based on first-price auctions (e..g., as in Bitcoin) or dynamic adjustment of the minimum admissible fee (e.g. as in Ethereum EIP-1559) something that breaks fee predictability. At the same time, in fixed fee mechanisms (e.g., as in Cardano),  fees are trivially predictable but are subject to  relatively inexpensive bribing or denial of service attacks where transactions may be delayed indefinitely by a well funded attacker, hence breaking delay predictability. 

In this work, we set out to address this problem by putting forward blockchain space tokenization (BST), namely a new capability of a blockchain system to tokenize its capacity for transactions and allocate it to interested users who are willing to pay ahead of time for the ability to post transactions regularly for a period of time. We analyze our system in the face of  worst-case transaction-processing attacks by introducing a security game played between the mempool mechanism and an adversary.  Leveraging this framework, we prove that BST offers predictable and asymptotically optimal delays, predictable fees, and is incentive compatible, thus answering the question posed in the affirmative.



## 2024/1155

* Title: Cross Ledger Transaction Consistency for Financial Auditing
* Authors: Vlasis Koutsos, Xiangan Tian, Dimitrios Papadopoulos, Dimitris Chatzopoulos
* [Permalink](https://eprint.iacr.org/2024/1155)
* [Download](https://eprint.iacr.org/2024/1155.pdf)

### Abstract

Auditing throughout a fiscal year is integral to organizations with transactional activity. Organizations transact with each other and record the details for all their economical activities so that a regulatory committee can verify the lawfulness and legitimacy of their activity. However, it is computationally infeasible for the committee to perform all necessary checks for each organization. To overcome this, auditors assist in this process: organizations give access to all their internal data to their auditors, who then produce reports regarding the consistency of the organization's data, alerting the committee to any inconsistencies. Despite this, numerous issues that result in fines annually revolve around such inconsistencies in bookkeeping across organizations. Notably, committees wishing to verify the correctness of auditor-provided reports need to redo all their calculations; a process which is computationally proportional to the number of organizations. In fact, it becomes prohibitive when considering real-world settings with thousands of organizations. In this work, we propose two protocols, CLOSC and CLOLC, whose goals are to enable auditors and a committee to verify the consistency of transactions across different ledgers. Both protocols ensure that for every transaction recorded in an organization's ledger, there exists a dual one in the ledger of another organization while safeguarding against other potential attacks. Importantly, we minimize the information leakage to auditors and other organizations and guarantee three crucial security and privacy properties that we propose: (i) transaction amount privacy, (ii) organization-auditor unlinkability, and (iii) transacting organizations unlinkability. At the core of our protocols lies a two-tier ledger architecture alongside a suite of cryptographic tools. To demonstrate the practicality and scalability of our designs, we provide extensive performance evaluation for both CLOSC and CLOLC. Our numbers are promising, i.e., all computation and verification times lie in the range of seconds, even for millions of transactions, while the on-chain storage costs for an auditing epoch are encouraging i.e. in the range of GB for millions of transactions and thousands of organizations.



## 2024/1156

* Title: On affine forestry over integral domains and families of deep Jordan-Gauss graphs
* Authors: Tymoteusz Chojecki, Grahame Erskine, James Tuite, Vasyl Ustimenko
* [Permalink](https://eprint.iacr.org/2024/1156)
* [Download](https://eprint.iacr.org/2024/1156.pdf)

### Abstract

Let K be a commutative ring. We refer to a connected bipartite graph G = G_n(K) with partition sets P = K^n (points) and L = K^n (lines) as an affine graph over K of dimension dim(G) = n if the neighbourhood of each vertex is isomorphic to K. We refer to G as an algebraic affine graph over K if the incidence between a point (x_1, x_2, . . . , x_n)
and line [y_1, y_2, . . . , y_n] is defined via a system of polynomial equations of the kind f_i = 0 where f_i ∈ K[x_1, x_2, . . . , x_n, y_1, y_2, . . . , y_n]. We say that an affine algebraic graph is a Jordan-Gauss graph over K  if the incidences between points and lines are given by a
quadratic system of polynomial equations, and the neighbourhood of each vertex is given as a solution set of the system of linear equations in row-echelon form.
     For each integral domain K we consider the known explicit construction of the family of Jordan-Gauss graphs A(n, K), n = 2, 3, . . . with cycle indicator ≥ 2n + 2. Additionally several constructions of families of edge intransitive Jordan-Gauss graphs over K of
increasing girth with well defined projective limit will be presented. This projective limit is a forest defined by the system of algebraic equations. In the case K = F_q, q ≥ 3 we present results of computer experiments for the evaluation of girth, cycle indicator, diameter and the second largest eigenvalue of the constructed graphs, and we formulate
several conjectures on their properties. One of the conjectures is that the girth of A(n, F_q) is 2[(n+ 5)/2]. We discuss briefly some applications of Jordan-Gauss graphs of large girth to Graph Theory, Algebraic Geometry and the theory of LDPC codes; and we consider ideas to use groups related to these graphs in Noncommutative Cryptography and Stream Ciphers Design.



## 2024/1157

* Title: Shift-invariant functions and almost liftings
* Authors: Jan Kristian Haugland, Tron Omland
* [Permalink](https://eprint.iacr.org/2024/1157)
* [Download](https://eprint.iacr.org/2024/1157.pdf)

### Abstract

We investigate shift-invariant vectorial Boolean functions on $n$ bits that are lifted from Boolean functions on $k$ bits, for $k\leq n$. We consider vectorial functions that are not necessarily permutations, but are, in some sense, almost bijective. In this context, we define an almost lifting as a Boolean function for which there is an upper bound on the number of collisions of its lifted functions that does not depend on $n$. We show that if a Boolean function with diameter $k$ is an almost lifting, then the maximum number of collisions of its lifted functions is $2^{k-1}$ for any $n$. Moreover, we search for functions in the class of almost liftings that have good cryptographic properties and for which the non-bijectivity does not cause major security weaknesses. These functions generalize the well-known map $\chi$ used in the Keccak hash function.



## 2024/1158

* Title: A Note on `` Provably Secure and Lightweight Authentication Key Agreement Scheme  for Smart Meters''
* Authors: Zhengjun Cao, Lihua Liu
* [Permalink](https://eprint.iacr.org/2024/1158)
* [Download](https://eprint.iacr.org/2024/1158.pdf)

### Abstract

We show that the  authentication key agreement scheme
[IEEE Trans. Smart Grid, 2023, 14(5), 3816-3827] is flawed due to its inconsistent computations. We also show that the scheme fails to keep anonymity, not as claimed.



## 2024/1159

* Title: LaPSuS – A Lattice-Based Private Stream Aggregation Scheme under Scrutiny
* Authors: Johannes Ottenhues, Alexander Koch
* [Permalink](https://eprint.iacr.org/2024/1159)
* [Download](https://eprint.iacr.org/2024/1159.pdf)

### Abstract

Private Stream Aggregation (PSA) allows clients to send encryptions of their private values to an aggregator that is then able to learn the sum of these values but nothing else. It has since found many applications in practice, e.g.. for smart metering or federated learning. In 2018, Becker et al. proposed the first lattice-based PSA scheme LaPS (NDSS 2018), with putative post-quantum security, which has subsequently been patented. In this paper, we describe two attacks on LaPS that break the claimed aggregator obliviousness security notion, where the second attack even allows to recover the secret keys of the clients, given enough encryptions. Moreover, we review the PSA literature for other occurrences of the responsible flawed proof steps. By explicitly tracking down and discussing these flaws, we clarify and hope to contribute to the literature on PSA schemes, in order to prevent further insecure schemes in practice. Finally, we point out that a Real-or-Random variant of the security notion that is often used as a substitute to make proofs easier, is not well-defined and potentially weaker than the standard PSA security notion. We propose a well defined variant and show that it is equivalent to the standard security notion of PSA under mild assumptions.



## 2024/1160

* Title: Post-Quantum Access Control with Application to Secure Data Retrieval
* Authors: Behzad Abdolmaleki, Hannes Blümel, Giacomo Fenzi, Homa Khajeh, Stefan Köpsell, Maryam Zarezadeh
* [Permalink](https://eprint.iacr.org/2024/1160)
* [Download](https://eprint.iacr.org/2024/1160.pdf)

### Abstract

Servan-Schreiber et al. (S&P 2023) presented a new notion called private access control lists (PACL) for function secret sharing (FSS), where the FSS evaluators can ensure that the FSS dealer is authorized to share the given function. Their construction relies on costly non-interactive secret-shared proofs and is not secure in post-quantum setting. We give a construction of PACL from publicly verifiable secret sharing (PVSS) under short integer solution (SIS). Our construction adapts the Gentry et al’s scheme (Eurocrypt 2022) for post-quantum setting based on learning with error assumption (LWE). The implementation of our PACL with different files showed that it is feasible even at different sizes, and should remain so even with large secret vectors. This construction has many applications for access control by applying FSS. We show how to apply the proposed PACL construction to secure data retrieval. We also present a scheme for secure data retrieval with access control, which might be of independent interest.



## 2024/1161

* Title: On the Concrete Security of Non-interactive FRI
* Authors: Alexander R. Block, Pratyush Ranjan Tiwari
* [Permalink](https://eprint.iacr.org/2024/1161)
* [Download](https://eprint.iacr.org/2024/1161.pdf)

### Abstract

FRI is a cryptographic protocol widely deployed today as a building
block of many efficient SNARKs that help secure transactions of hundreds of
millions of dollars per day. The Fiat-Shamir security of FRI—vital for understanding
the security of FRI-based SNARKs—has only recently been formalized and
established by Block et al. (ASIACRYPT ’23).

In this work, we complement the result of Block et al. by providing a thorough
concrete security analysis of non-interactive FRI under various parameter settings
from protocols deploying (or soon to be deploying) FRI today. We find that these
parameters nearly achieve their desired security targets (being at most 1-bit less
secure than their targets) for non-interactive FRI with respect to a certain security
conjecture about the FRI Protocol. However, in all but one set of parameters, we
find that the provable security of non-interactive FRI under these parameters is
severely lacking, being anywhere between 21- and 63-bits less secure than the
conjectured security. The conjectured security of FRI assumes that known attacks
are optimal, the security of these systems would be severely compromised should
a better attack be discovered. In light of this, we present parameter guidelines
for achieving 100-bits of provable security for non-interactive FRI along with a
methodology for tuning these parameters to suit the needs of protocol designers.



## 2024/1162

* Title: Practical Traceable Receipt-Free Encryption
* Authors: Henri Devillez, Olivier Pereira, Thomas Peters
* [Permalink](https://eprint.iacr.org/2024/1162)
* [Download](https://eprint.iacr.org/2024/1162.pdf)

### Abstract

Traceable Receipt-free Encryption (TREnc) is a verifiable public-key encryption primitive introduced at Asiacrypt 2022. A TREnc allows randomizing ciphertexts in transit in order to remove any subliminal information up to a public trace that ensures the non-malleability of the underlying plaintext. A remarkable property of TREnc is the indistinguishability of the randomization of chosen ciphertexts against traceable chosen-ciphertext attacks (TCCA). This property can support applications like voting, and it was shown that receipt-free non-interactive voting, where voters are unable to convince any third party of the content of their vote, can be generically built from a TREnc.

While being a very promising primitive, the few existing TREnc mechanisms either require a secret coin CRS or are fairly demanding in time and space requirements. Their security proofs also come with a linear security degradation in the number of challenge ciphertexts.

We address these limitations and offer two efficient public coin TREnc mechanisms tailored for the two common tallying approaches in elections: homomorphic and mixnet-based. The TCCA security of our mechanisms also enjoys an almost-tight reduction to SXDH, based on a new randomizable technique of independent interest in the random oracle model.

A Rust implementation of our TREnc mechanisms demonstrates that we can verifiably encrypt 64 bits in less than a second, and full group elements in around 30 ms., which is sufficient for most real-world applications. While comparing with other solutions, we show that our approaches lead to the most efficient non-interactive receipt-free voting system to date.



## 2024/1163

* Title: On the Number of Restricted Solutions to Constrained Systems and their Applications
* Authors: Benoît Cogliati, Jordan Ethan, Ashwin Jha, Mridul Nandi, Abishanka Saha
* [Permalink](https://eprint.iacr.org/2024/1163)
* [Download](https://eprint.iacr.org/2024/1163.pdf)

### Abstract

In this paper, we formulate a special class of systems of linear equations over finite fields and derive lower bounds on the number of solutions adhering to some predefined restrictions. We then demonstrate the applications of these lower bounds to derive tight PRF security (up to $2^{3n/4}$ queries) for single-keyed variants of the Double-block Hash-then-Sum (DBHtS) paradigm, specifically PMAC+ and LightMAC+. Additionally, we show that the sum of $r$ independent copies of the Even-Mansour cipher is a secure PRF up to $2^{\frac{r}{r+1}n}$ queries.



## 2024/1164

* Title: A Crack in the Firmament: Restoring Soundness of the Orion Proof System and More
* Authors: Thomas den Hollander, Daniel Slamanig
* [Permalink](https://eprint.iacr.org/2024/1164)
* [Download](https://eprint.iacr.org/2024/1164.pdf)

### Abstract

Orion (Xie et al. CRYPTO'22) is a recent plausibly post-quantum zero-knowledge argument system with a linear time prover. It improves over Brakedown (Golovnev et al. ePrint'21 and CRYPTO'23) by reducing proof size and verifier complexity to be polylogarithmic and additionally adds the zero-knowledge property. The argument system is demonstrated to be concretely efficient with a prover time being the fastest among all existing succinct proof systems and a proof size that is an order of magnitude smaller than Brakedown. Since its publication in CRYPTO 2022, two revisions have been made to the zk-SNARK. First, there was an issue with how zero-knowledge was handled. Second, Orion was discovered to be unsound, which was then repaired through the use of a commit-and-prove SNARK as an ``outer'' SNARK.

As we will show in this paper, unfortunately, Orion in its current revision is still unsound (with and without the zero-knowledge property) and we will demonstrate practical attacks on it. We then show how to repair Orion without additional assumptions, which requies non-trivial fixes when aiming to preserve the linear time prover complexity. The proposed fixes lead to an even improved efficiency, i.e., smaller proof size and verifier time, over the claimed efficiency of the initial version of Orion. Moreover, we provide the first rigorous security proofs and explicitly consider multi-point openings and non-interactivity. While revisiting Orion we make some additional contributions which might be of independent interest, most notable an improved code randomization technique that retains the minimum relative distance.



## 2024/1165

* Title: Respire: High-Rate PIR for Databases with Small Records
* Authors: Alexander Burton, Samir Jordan Menon, David J. Wu
* [Permalink](https://eprint.iacr.org/2024/1165)
* [Download](https://eprint.iacr.org/2024/1165.pdf)

### Abstract

Private information retrieval (PIR) is a key building block in many privacy-preserving systems, and recent works have made significant progress on reducing the concrete computational costs of single-server PIR. However, existing constructions have high communication overhead, especially for databases with small records. In this work, we introduce Respire, a lattice-based PIR scheme tailored for databases of small records. To retrieve a single record from a database with over a million 256-byte records, the Respire protocol requires just 6.1 KB of online communication; this is a 5.9x reduction compared to the best previous lattice-based scheme. Moreover, Respire naturally extends to support batch queries. Compared to previous communication-efficient batch PIR schemes, Respire achieves a 3.4-7.1x reduction in total communication while maintaining comparable throughput (200-400 MB/s). The design of Respire relies on new query compression and response packing techniques based on ring switching in homomorphic encryption.



## 2024/1166

* Title: On the Relationship between FuncCPA and FuncCPA+
* Authors: Takumi Shinozaki, Keisuke Tanaka, Masayuki Tezuka, Yusuke Yoshida
* [Permalink](https://eprint.iacr.org/2024/1166)
* [Download](https://eprint.iacr.org/2024/1166.pdf)

### Abstract

Akavia, Gentry, Halevi, and Vald introduced the security notion of function-chosen-plaintext-attack (FuncCPA security) for public-key encryption schemes.
FuncCPA is defined by adding a functional re-encryption oracle to the IND-CPA game.
This notion is crucial for secure computation applications where the server is allowed to delegate a part of the computation to the client.

Dodis, Halevi, and Wichs introduced a stronger variant called FuncCPA$^+$.
They showed FuncCPA$^+$ implies FuncCPA and conjectured that FuncCPA$^+$ is strictly stronger than FuncCPA.
They left an open problem to clarify the relationship between these variants.

Contrary to their conjecture, we show that FuncCPA is equivalent to FuncCPA$^+$.
We show it by two proofs with a trade-off between the number of queries and the number of function inputs.
Furthermore, we show these parameters determine the security levels of FuncCPA and FuncCPA$^+$.



## 2024/1167

* Title: Expanding the Toolbox: Coercion and Vote-Selling at Vote-Casting Revisited
* Authors: Tamara Finogina, Javier Herranz, Peter B. Roenne
* [Permalink](https://eprint.iacr.org/2024/1167)
* [Download](https://eprint.iacr.org/2024/1167.pdf)

### Abstract

Coercion is a challenging and multi-faceted threat that prevents people from expressing their will freely. Similarly, vote-buying does to undermine the foundation of free democratic elections. These threats are especially dire for remote electronic voting, which relies on voters to express their political will freely but happens in an uncontrolled environment outside the polling station and the protection of the ballot booth. However, electronic voting in general, both in-booth and remote, faces a major challenge, namely to ensure that voters can verify that their intent is captured correctly without providing a receipt of the cast vote to the coercer or vote buyer.

Even though there are known techniques to resist or partially mitigate coercion and vote-buying, we explicitly demonstrate that they generally underestimate the power of malicious actors by not accounting for current technological tools that could support coercion and vote-selling.

In this paper, we give several examples of how a coercer can force voters to comply with his demands or how voters can prove how they voted. To do so, we use tools like blockchains, delay encryption, privacy-preserving smart contracts, or trusted hardware. Since some of the successful coercion attacks occur on voting schemes that were supposed/claimed/proven to be coercion-resistant or receipt-free, the main conclusion of this work is that the coercion models should be re-evaluated, and new definitions of coercion and receipt-freeness are necessary. We propose such new definitions as part of this paper and investigate their implications.



## 2024/1168

* Title: Time is not enough: Timing Leakage Analysis on Cryptographic Chips via Plaintext-Ciphertext Correlation in Non-timing Channel
* Authors: Congming Wei, Guangze Hong, An Wang, Jing Wang, Shaofei Sun, Yaoling Ding, Liehuang Zhu, Wenrui Ma
* [Permalink](https://eprint.iacr.org/2024/1168)
* [Download](https://eprint.iacr.org/2024/1168.pdf)

### Abstract

In side-channel testing, the standard timing analysis works when the vendor can provide a measurement to indicate the execution time of cryptographic algorithms. In this paper, we find that there exists timing leakage in power/electromagnetic channels, which is often ignored in traditional timing analysis. Hence a new method of timing analysis is proposed to deal with the case where execution time is not available.  Different execution time leads to different execution intervals, affecting the locations of plaintext and ciphertext transmission. Our method detects timing leakage by studying changes in plaintext-ciphertext correlation when traces are aligned forward and backward. Experiments are then carried out on different  cryptographic devices. Furthermore, we propose an improved timing analysis framework which gives appropriate methods for different scenarios.



## 2024/1169

* Title: Attacking Tropical Stickel Protocol by MILP and Heuristic Optimization Techniques
* Authors: Sulaiman Alhussaini, Serge˘ı Sergeev
* [Permalink](https://eprint.iacr.org/2024/1169)
* [Download](https://eprint.iacr.org/2024/1169.pdf)

### Abstract

Known attacks on the tropical implementation of Stickel protocol involve solving a minimal covering problem, and this leads to an exponential growth in the time required to recover the secret key as the used polynomial degree increases. Consequently, it can be argued that Alice and Bob can still securely execute the protocol by utilizing very high polynomial degrees, a feasible approach due to the efficiency of tropical operations. The same is true for the implementation of Stickel protocol over some other semirings with idempotent addition (such as the max-min or fuzzy semiring). In this paper, we propose alternative methods to attacking Stickel protocol that avoid this minimal covering problem and the associated exponential time complexity. These methods involve framing the attacks as a mixed integer linear programming (MILP) problem or applying certain global optimization techniques.



## 2024/1170

* Title: Rudraksh: A compact and lightweight post-quantum key-encapsulation mechanism
* Authors: Suparna Kundu, Archisman Ghosh, Angshuman Karmakar, Shreyas Sen, Ingrid Verbauwhede
* [Permalink](https://eprint.iacr.org/2024/1170)
* [Download](https://eprint.iacr.org/2024/1170.pdf)

### Abstract

Resource-constrained devices such as wireless sensors and Internet of Things (IoT) devices have become ubiquitous in our digital ecosystem. These devices generate and handle a major part of our digital data.  In the face of the impending threat of quantum computers on our public-key infrastructure, it is impossible to imagine the security and privacy of our digital world without integrating post-quantum cryptography (PQC) into these devices. Usually, due to the resource constraints of these devices, the cryptographic schemes in these devices have to operate with very small memory and consume very little power.. Therefore, we must provide a lightweight implementation of existing PQC schemes by possibly trading off the efficiency. The other option that can potentially provide the most optimal result is by designing PQC schemes suitable for lightweight and low-power-consuming implementation.  Unfortunately, the latter method has been largely ignored in PQC research.

In this work, we first provide a lightweight CCA-secure PQ key-encapsulation mechanism (KEM) design based on hard lattice problems. We have done a scrupulous and extensive analysis and evaluation of different design elements, such as polynomial size, field modulus structure, reduction algorithm, secret and error distribution, etc., of a lattice-based KEM. We have optimized each of them to obtain a lightweight design. Our design provides a $100$ bit of PQ security and shows $\sim3$x improvement in terms of area with respect to the state-of-the-art Kyber KEM, a PQ standard.



## 2024/1171

* Title: Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem
* Authors: Akshima, Tyler Besselman, Siyao Guo, Zhiye Xie, Yuping Ye
* [Permalink](https://eprint.iacr.org/2024/1171)
* [Download](https://eprint.iacr.org/2024/1171.pdf)

### Abstract

In the (preprocessing) Decisional Diffie-Hellman (DDH) problem, we are given a cyclic group $G$ with a generator $g$ and a prime order $N$, and we want to prepare some advice of size $S$, such that we can efficiently distinguish $(g^{x},g^{y},g^{xy})$ from $(g^{x},g^{y},g^{z})$ in time $T$ for uniformly and independently chosen $x,y,z$ from $\mathbb{Z}_N$. This is a central cryptographic problem whose computational hardness underpins many widely deployed schemes, such as the Diffie–Hellman key exchange protocol.
    
We prove that any generic preprocessing DDH algorithm (operating in any cyclic group) achieves advantage at most $O(ST^2 / N)$. This bound matches the best known attack up to poly-log factors, and confirms that DDH is as secure as the (seemingly harder) discrete logarithm problem against preprocessing attacks. Our result resolves an open question by Corrigan-Gibbs and Kogan (EUROCRYPT 2018), who proved optimal bounds for many variants of discrete logarithm problems except DDH (with an $\tilde{O}(\sqrt{ST^2/N})$ bound).

We obtain our results by adopting and refining the approach by Gravin, Guo, Kwok, Lu (SODA 2021) and by Yun (EUROCRYPT 2015). Along the way, we significantly simplified and extended the above techniques which may be of independent interest.
The highlights of our techniques are as follows:

(1) We obtain a simpler reduction from decisional problems against $S$-bit advice to their $S$-wise XOR lemmas against zero-advice, recovering the reduction by Gravin, Guo, Kwok and Lu (SODA 2021).
(2) We show how to reduce generic hardness of decisional problems to their variants in the simpler hyperplane query model proposed by Yun (EUROCRYPT 2015).. This is the first work analyzing a decisional problem in Yun's model, answering an open problem proposed by Auerbach, Hoffman, and Pascual-Perez (TCC 2023).
(3)  We prove an $S$-wise XOR lemma of DDH in Yun's model.  As a corollary, we obtain the generic hardness of the $S$-XOR DDH problem.



## 2024/1172

* Title: Generalized class group actions on oriented elliptic curves with level structure
* Authors: Sarah Arpin, Wouter Castryck, Jonathan Komada Eriksen, Gioella Lorenzon, Frederik Vercauteren
* [Permalink](https://eprint.iacr.org/2024/1172)
* [Download](https://eprint.iacr.org/2024/1172.pdf)

### Abstract

We study a large family of generalized class groups of imaginary quadratic orders $O$ and prove that they act freely and (essentially) transitively on the set of primitively $O$-oriented elliptic curves over a field $k$ (assuming this set is non-empty) equipped with appropriate level structure. This extends, in several ways, a recent observation due to Galbraith, Perrin and Voloch for the ray class group. We show that this leads to a reinterpretation of the action of the class group of a suborder $O' \subseteq O$ on the set of $O'$-oriented elliptic curves, discuss several other examples, and briefly comment on the hardness of the corresponding vectorization problems.



## 2024/1173

* Title: Cryptanalysis of Rank-2 Module-LIP with Symplectic Automorphisms
* Authors: Hengyi Luo, Kaijie Jiang, Yanbin Pan, Anyu Wang
* [Permalink](https://eprint.iacr.org/2024/1173)
* [Download](https://eprint.iacr.org/2024/1173.pdf)

### Abstract

At Eurocrypt'24, Mureau et al. formally defined the Lattice Isomorphism Problem for module lattices (module-LIP) in a number field $\mathbb{K}$, and proposed a heuristic randomized algorithm solving module-LIP for modules of rank 2 in $\mathbb{K}^2$ with a totally real number field $\mathbb{K}$, which runs in classical polynomial time for a large class of modules and a large class of totally real number field under some reasonable number theoretic assumptions. In this paper, by introducing a (pseudo) symplectic automorphism of the module, we successfully reduce the problem of solving module-LIP over CM number field to the problem of finding certain symplectic automorphism. Furthermore, we show that a weak (pseudo) symplectic automorphism can be computed efficiently, which immediately turns out to be the desired automorphism when the module is in a totally real number field. This directly results in  a provable deterministic polynomial-time algorithm solving module-LIP for rank-2 modules in $\mathbb{K}^2$ where $\mathbb{K}$ is a totally real number field, without any assumptions or restrictions on the modules and the totally real number fields. Moreover, the weak symplectic automorphism can also be utilized to invalidate the omSVP assumption employed in HAWK's forgery security analysis, although it does not yield any actual attacks against HAWK itself.



## 2024/1174

* Title: Grafted Trees Bear Better Fruit: An Improved Multiple-Valued Plaintext-Checking Side-Channel Attack against Kyber
* Authors: Jinnuo Li, Chi Cheng, Muyan Shen, Peng Chen, Qian Guo, Dongsheng Liu, Liji Wu, Jian Weng
* [Permalink](https://eprint.iacr.org/2024/1174)
* [Download](https://eprint.iacr.org/2024/1174.pdf)

### Abstract

As a prominent category of side-channel attacks (SCAs), plaintext-checking (PC) oracle-based SCAs offer the advantages of generality and operational simplicity on a targeted device. At TCHES 2023, Rajendran et al. and Tanaka et al. independently proposed the multiple-valued  (MV)  PC oracle,  significantly reducing the required number of queries (a.k.a., traces) in the PC oracle.  However, in practice, when dealing with environmental noise or inaccuracies in the waveform classifier, they still rely on majority voting or the other technique that usually results in three times the number of queries compared to the ideal case. 


In this paper, we propose an improved method to further reduce the number of queries of the MV-PC oracle, particularly in scenarios where the oracle is imperfect.  Compared to the state-of-the-art at TCHES 2023, our proposed method reduces the number of queries for a full key recovery by more than $42.5\%$. The method involves three rounds. Our key observation is that coefficients recovered in the first round can be regarded as prior information to significantly aid in retrieving coefficients in the second round. This improvement is achieved through a newly designed grafted tree. Notably, the proposed method is generic and can be applied to both the NIST key encapsulation mechanism (KEM) standard Kyber and other significant candidates, such as Saber and Frodo. We have conducted extensive software simulations against  Kyber-512, Kyber-768, Kyber-1024, FireSaber, and Frodo-1344 to validate the efficiency of the proposed method. An electromagnetic attack conducted on real-world implementations, using an STM32F407G board equipped with an ARM Cortex-M4 microcontroller and Kyber implementation from the public library \textit{pqm4}, aligns well with our simulations.



## 2024/1175

* Title: AVeCQ: Anonymous Verifiable Crowdsourcing with Worker Qualities
* Authors: Vlasis Koutsos, Sankarshan Damle, Dimitrios Papadopoulos, Sujit Gujar, Dimitris Chatzopoulos
* [Permalink](https://eprint.iacr.org/2024/1175)
* [Download](https://eprint.iacr.org/2024/1175.pdf)

### Abstract

In crowdsourcing systems, requesters publish tasks, and interested workers provide answers to get rewards. Worker anonymity motivates participation since it protects their privacy. Anonymity with unlinkability is an enhanced version of anonymity because it makes it impossible to ``link'' workers across the tasks they participate in. Another core feature of crowdsourcing systems is worker quality which expresses a worker's trustworthiness and quantifies their historical performance. In this work, we present AVeCQ, the first crowdsourcing system that reconciles these properties, achieving enhanced anonymity and verifiable worker quality updates. AVeCQ relies on a suite of cryptographic tools, such as zero-knowledge proofs, to (i) guarantee workers' privacy, (ii) prove the correctness of worker quality scores and task answers, and (iii) commensurate payments. AVeCQ is developed modularly, where requesters and workers communicate over a platform that supports pseudonymity, information logging, and payments. To compare AVeCQ with the state-of-the-art, we prototype it over Ethereum. AVeCQ outperforms the state-of-the-art in three popular crowdsourcing tasks (image annotation, average review, and Gallup polls). E.g., for an Average Review task with 5 choices and 128 workers AVeCQ is 40% faster (including computing and verifying necessary proofs, and blockchain transaction processing overheads) with the task's requester consuming 87% fewer gas.



## 2024/1176

* Title: A zero-trust swarm security architecture and protocols
* Authors: Alex Shafarenko
* [Permalink](https://eprint.iacr.org/2024/1176)
* [Download](https://eprint.iacr.org/2024/1176.pdf)

### Abstract

This report presents the security protocols and general trust architecture of the SMARTEDGE swarm computing platform. Part 1 describes the coordination protocols for use in a swarm production environment, e.g. a smart factory, and Part 2 deals with crowd-sensing scenarios characteristic of traffic-control swarms.



## 2024/1177

* Title: Cryptanalysis of two post-quantum authenticated key agreement protocols
* Authors: Mehdi Abri, Hamid Mala
* [Permalink](https://eprint.iacr.org/2024/1177)
* [Download](https://eprint.iacr.org/2024/1177.pdf)

### Abstract

As the use of the internet and digital devices has grown rapidly, keeping digital communications secure has become very important. Authenticated Key Agreement (AKA) protocols play a vital role in securing digital communications. These protocols enable the communicating parties to mutually authenticate and securely establish a shared secret key. The emergence of quantum computers makes many existing AKA protocols vulnerable to their immense computational power. Consequently, designing new protocols that are resistant to quantum attacks has become essential. Extensive research in this area had led to the design of several post-quantum AKA schemes.
In this paper, we analyze  two post-quantum AKA schemes proposed by  Dharminder et al. [2022] and Pursharthi and Mishra. [2024] and demonstrate that these schemes are not secure against active adversaries. An adversary can impersonate an authorized user to the server. We then propose reliable solutions to prevent these attacks.



## 2024/1178

* Title: Towards Quantum-Safe Blockchain: Exploration of PQC and Public-key Recovery on Embedded Systems
* Authors: Dominik Marchsreiter
* [Permalink](https://eprint.iacr.org/2024/1178)
* [Download](https://eprint.iacr.org/2024/1178.pdf)

### Abstract

Blockchain technology ensures accountability,
transparency, and redundancy in critical applications, includ-
ing IoT with embedded systems. However, the reliance on
public-key cryptography (PKC) makes blockchain vulnerable to
quantum computing threats. This paper addresses the urgent
need for quantum-safe blockchain solutions by integrating Post-
Quantum Cryptography (PQC) into blockchain frameworks.
Utilizing algorithms from the NIST PQC standardization pro-
cess, we aim to fortify blockchain security and resilience, partic-
ularly for IoT and embedded systems. Despite the importance
of PQC, its implementation in blockchain systems tailored for
embedded environments remains underexplored. We propose
a quantum-secure blockchain architecture, evaluating various
PQC primitives and optimizing transaction sizes through tech-
niques such as public-key recovery for Falcon, achieving up
to 17% reduction in transaction size. Our analysis identifies
Falcon-512 as the most suitable algorithm for quantum-secure
blockchains in embedded environments, with XMSS as a viable
stateful alternative. However, for embedded devices, Dilithium
demonstrates a higher transactions-per-second (TPS) rate
compared to Falcon, primarily due to Falcon’s slower sign-
ing performance on ARM CPUs. This highlights the signing
time as a critical limiting factor in the integration of PQC
within embedded blockchains. Additionally, we integrate smart
contract functionality into the quantum-secure blockchain,
assessing the impact of PQC on smart contract authentication.
Our findings demonstrate the feasibility and practicality of
deploying quantum-secure blockchain solutions in embedded
systems, paving the way for robust and future-proof IoT
applications.