## 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


[continued in next message]

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)