## In this issue

1. [2023/1530] Proofs of Space with Maximal Hardness
2. [2024/338] Tight Indistinguishability Bounds for the XOR of ...
3. [2024/365] Combined Threshold Implementation
4. [2024/554] Leakage-Abuse Attacks Against Structured Encryption ...
5. [2024/555] Quantum Algorithms for Lattice Problems
6. [2024/564] Multiple Group Action Dlogs with(out) Precomputation
7. [2024/568] Communication-Efficient Multi-Party Computation for ...
8. [2024/569] An overview of symmetric fuzzy PAKE protocols
9. [2024/570] Large-Scale Private Set Intersection in the Client- ...
10. [2024/571] MiniCast: Minimizing the Communication Complexity ...
11. [2024/572] Split Gröbner Bases for Satisfiability Modulo ...
12. [2024/573] Tokenised Multi-client Provisioning for Dynamic ...
13. [2024/574] PoMMES: Prevention of Micro-architectural Leakages ...
14. [2024/575] Pairing Optimizations for Isogeny-based Cryptosystems
15. [2024/576] On complexity of the problem of solving systems of ...
16. [2024/577] Determination of cryptographic tables and ...
17. [2024/578] Assessing the quality of Random Number Generators ...
18. [2024/579] Tight Multi-user Security of Ascon and Its Large ...
19. [2024/580] Dynamic Decentralized Functional Encryptions from ...
20. [2024/581] Fault Attack on SQIsign
21. [2024/582] Improved Alternating Moduli PRFs and Post-Quantum ...
22. [2024/584] Efficient Implementations of Square-root Vélu's ...
23. [2024/585] A Complete Beginner Guide to the Number Theoretic ...
24. [2024/586] Encryption Based Covert Channel for Large Language ...
25. [2024/587] Hidden $\Delta$-fairness: A Novel Notion for Fair ...
26. [2024/588] Digital Signatures for Authenticating Compressed ...
27. [2024/589] Blind-Folded: Simple Power Analysis Attacks using ...
28. [2024/590] Revisiting the Security of Fiat-Shamir Signature ...
29. [2024/591] Hash your Keys before Signing: BUFF Security of the ...
30. [2024/592] Asymptotics for the standard block size in primal ...
31. [2024/593] The Case of Small Prime Numbers Versus the Okamoto- ...
32. [2024/594] Greco: Fast Zero-Knowledge Proofs for Valid FHE ...
33. [2024/595] Analysis of Multivariate Encryption Schemes: ...
34. [2024/596] Cryptanalysis of signature schemes based on the ...
35. [2024/597] Blockchain-based decentralized identity system: ...
36. [2024/598] A Characterization of AE Robustness as Decryption ...
37. [2024/599] Probabilistically Checkable Arguments for all NP
38. [2024/600] A note on -Tweakable HCTR: A BBB Secure Tweakable ...
39. [2024/601] Improved Provable Reduction of NTRU and Hypercubic ...
40. [2024/602] Secret-Sharing Schemes for High Slices
41. [2024/603] Worst-Case to Average-Case Hardness of LWE: A ...
42. [2024/604] Generic MitM Attack Frameworks on Sponge Constructions
43. [2024/605] Security Analysis of XHASH8/12
44. [2024/606] Classical Commitments to Quantum States
45. [2024/607] Low-latency Secure Integrated Sensing and ...
46. [2024/608] The Practical Advantage of RSA over ECC and Pairings
47. [2024/609] New Security Proofs and Techniques for Hash-and- ...
48. [2024/610] Practical Delegatable Attribute-Based Anonymous ...
49. [2024/611] A Security Analysis of Restricted Syndrome Decoding ...
50. [2024/612] FHERMA: Building the Open-Source FHE Components ...
51. [2024/613] Hadamard Product Argument from Lagrange-Based ...

## 2023/1530

* Title: Proofs of Space with Maximal Hardness
* Authors: Leonid Reyzin
* [Permalink](https://eprint.iacr.org/2023/1530)
* [Download](https://eprint.iacr.org/2023/1530.pdf)

### Abstract

In a proof of space, a prover performs a complex computation with a large output. A verifier periodically checks that the prover still holds the output. The security goal for a proof of space construction is to ensure that a prover who erases even a
portion of the output has to redo a large portion of the complex computation in order to satisfy the verifier.

In existing constructions of proofs of space, the computation that a cheating prover is forced to redo is a small fraction (vanishing or small constant) of the original complex computation. The only exception is a construction of Pietrzak (ITCS 2019)
that requires extremely depth-robust graphs, which result in impractically high complexity of the initialization process.

We present the first proof of space of reasonable complexity that ensures that the prover has to redo almost the entire computation (fraction arbitrarily close to 1) when trying to save even an arbitrarily small constant fraction of the space.
Our construction is a generalization of an existing construction called SDR (Fisch, Eurocrypt 2019) deployed on the Filecoin blockchain. Our improvements, while general, also demonstrate that the already deployed construction has considerably better
security than previously shown.

Technically, our construction can be viewed as amplifying predecessor-robust graphs. These are directed acyclic graphs in which every subgraph of sufficient relative size $\pi$ contains a large single-sink connected component of relative size $\alpha_\pi$
. We take a predecessor-robust graph with constant parameters $(\pi, \alpha_\pi)$, and build a bigger predecessor-robust graph with a near-optimal set of parameters and additional guarantees on sink placement, while increasing the degree only by a small
additive constant.



## 2024/338

* Title: Tight Indistinguishability Bounds for the XOR of Independent Random Permutations by Fourier Analysis
* Authors: Itai Dinur
* [Permalink](https://eprint.iacr.org/2024/338)
* [Download](https://eprint.iacr.org/2024/338.pdf)

### Abstract

The XOR of two independent permutations (XoP) is a well-known construction for achieving security beyond the birthday bound when implementing a pseudorandom function using a block cipher (i.e., a pseudorandom permutation). The idealized construction (
where the permutations are uniformly chosen and independent) and its variants have been extensively analyzed over nearly 25 years.

The best-known asymptotic information-theoretic indistinguishability bound for the XoP construction is $O(q/2^{1.5n})$, derived by Eberhard in 2017, where $q$ is the number of queries and $n$ is the block length.

A generalization of the XoP construction outputs the XOR of $r \geq 2$ independent permutations, and has also received significant attention in both the single-user and multi-user settings. In particular, for $r = 3$, the best-known bound (obtained by
Choi et al. [ASIACRYPT'22]) is about $q^2/2^{2.5 n}$ in the single-user setting and $\sqrt{u} q_{\max}^2/2^{2.5 n}$ in the multi-user setting (where $u$ is the number of users and $q_{\max}$ is the number of queries per user).

In this paper, we prove an indistinguishability bound of $q/2^{(r - 0.5)n}$ for the (generalized) XoP construction in the single-user setting, and a bound of $\sqrt{u} q_{\max}/2^{(r - 0.5)n}$ in the multi-user setting. In particular, for $r=2$, we
obtain the bounds $q/2^{1.5n}$ and $\sqrt{u} q_{\max}/2^{1.5n}$ in single-user and multi-user settings, respectively. For $r=3$ the corresponding bounds are $q/2^{2.5n}$ and $\sqrt{u} q_{\max}/2^{2.5n}$. All of these bounds hold assuming $q < 2^{n}/2$ (
or $q_{\max} < 2^{n}/2$).

Compared to previous works, we improve all the best-known bounds for the (generalized) XoP construction in the multi-user setting, and the best-known bounds for the generalized XoP construction for $r \geq 3$ in the single-user setting (assuming $q \geq
2^{n/2}$). For the basic two-permutation XoP construction in the single-user setting, our concrete bound of $q/2^{1.5n}$ stands in contrast to the asymptotic bound of $O(q/2^{1.5n})$ by Eberhard.

Since all of our bounds are matched (up to constant factors) for $q \geq 2^{n/2}$ by attacks published by Patarin in 2008 (and their generalizations to the multi-user setting), they are all tight.

We obtain our results by Fourier analysis of Boolean functions. Most of our technical work involves bounding (sums of) Fourier coefficients of the density function associated with sampling without replacement. While the proof of Eberhard relies on
similar bounds, our proof is elementary and simpler.



## 2024/365

* Title: Combined Threshold Implementation
* Authors: Jakob Feldtkeller, Jan Richter-Brockmann, Pascal Sasdrich, Tim Güneysu
* [Permalink](https://eprint.iacr.org/2024/365)
* [Download](https://eprint.iacr.org/2024/365.pdf)

### Abstract

Physical security is an important aspect of devices for which an adversary can manipulate the physical execution environment. Recently, more and more attention has been directed towards a security model that combines the capabilities of passive and
active physical attacks, i.e., an adversary that performs fault-injection and side-channel analysis at the same time. Implementing countermeasures against such a powerful adversary is not only costly but also requires the skillful combination of masking
and redundancy to counteract all reciprocal effects.

In this work, we propose a new methodology to generate combined-secure circuits. We show how to transform TI-like constructions to resist any adversary with the capability to tamper with internal gates and probe internal wires. For the resulting
protection scheme, we can prove the combined security in a well-established theoretical security model.

Since the transformation preserves the advantages of TI-like structures, the resulting circuits prove to be more efficient in the number of required bits of randomness (up to 100%), the latency in clock cycles (up to 40%), and even the area for pipelined
designs (up to 40%) than the state of the art for an adversary restricted to manipulating a single gate and probing a single wire.



## 2024/554

* Title: Leakage-Abuse Attacks Against Structured Encryption for SQL
* Authors: Alexander Hoover, Ruth Ng, Daren Khu, Yao'an Li, Joelle Lim, Derrick Ng, Jed Lim, Yiyang Song
* [Permalink](https://eprint.iacr.org/2024/554)
* [Download](https://eprint.iacr.org/2024/554.pdf)

### Abstract

Structured Encryption (StE) enables a client to securely store and query data stored on an untrusted server. Recent constructions of StE have moved beyond basic queries, and now support large subsets of SQL. However, the security of these constructions
is poorly understood, and no systematic analysis has been performed.

We address this by providing the first leakage-abuse attacks against StE for SQL schemes. Our attacks can be run by a passive adversary on a server with access to some information about the distribution of underlying data, a common model in prior work.
They achieve partial query recovery against select operations and partial plaintext recovery against join operations. We prove the optimality and near-optimality of two new attacks, in a Bayesian inference framework. We complement our theoretical results
with an empirical investigation testing the performance of our attacks against real-world data and show they can successfully recover a substantial proportion of queries and plaintexts.

In addition to our new attacks, we provide proofs showing that the conditional optimality of a previously proposed leakage-abuse attack and that inference against join operations is NP-hard in general.



## 2024/555

* Title: Quantum Algorithms for Lattice Problems
* Authors: Yilei Chen
* [Permalink](https://eprint.iacr.org/2024/555)
* [Download](https://eprint.iacr.org/2024/555.pdf)

### Abstract

We show a polynomial time quantum algorithm for solving the learning with errors problem (LWE) with certain polynomial modulus-noise ratios. Combining with the reductions from lattice problems to LWE shown by Regev [J.ACM 2009], we obtain polynomial time
quantum algorithms for solving the decisional shortest vector problem (GapSVP) and the shortest independent vector problem (SIVP) for all $n$-dimensional lattices within approximation factors of $\tilde{\Omega}(n^{4.5})$. Previously, no polynomial or
even subexponential time quantum algorithms were known for solving GapSVP or SIVP for all lattices within any polynomial approximation factors.

To develop a quantum algorithm for solving LWE, we mainly introduce two new techniques. First, we introduce Gaussian functions with complex variances in the design of quantum algorithms. In particular, we exploit the feature of the Karst wave in the
discrete Fourier transform of complex Gaussian functions. Second, we use windowed quantum Fourier transform with complex Gaussian windows, which allows us to combine the information from both time and frequency domains. Using those techniques, we first
convert the LWE instance into quantum states with purely imaginary Gaussian amplitudes, then convert purely imaginary Gaussian states into classical linear equations over the LWE secret and error terms, and finally solve the linear system of equations
using Gaussian elimination. This gives a polynomial time quantum algorithm for solving LWE.



## 2024/564

* Title: Multiple Group Action Dlogs with(out) Precomputation
* Authors: Alexander May, Massimo Ostuzzi
* [Permalink](https://eprint.iacr.org/2024/564)
* [Download](https://eprint.iacr.org/2024/564.pdf)

### Abstract

Let $\star: G \times X \rightarrow X$ be the action of a group $G$ of size $N=|G|$ on a set $X$. Let $y = g \star x \in X$ be a group action dlog instance, where our goal is to compute the unknown group element $g \in G$ from the known set elements $x,y
\in X$.
The Galbraith-Hess-Smart (GHS) collision finding algorithm solves the group action dlog in $N^{\frac 1 2}$ steps with polynomial memory.

We show that group action dlogs are suitable for precomputation attacks. More precisely, for any $s,t$ our precomputation algorithm computes within $st$ steps a hint of space complexity $s$, which allows to solve any group action dlog in an online phase
within $t$ steps. A typical instantiation is $s=t=N^{\frac 1 3}$, which gives precomputation time $N^{\frac 2 3}$ and space $N^{\frac 1 3}$, and online time only $N^{\frac 1 3}$.

Moreover, we show that solving multiple group action dlog instances $y_1, \ldots , y_m$ allows for speedups. Namely, our collision finding algorithm solves $m$ group action dlogs in $\sqrt{m}N^{\frac 1 2}$ steps, instead of the straight-forward $mN^{\
frac 1 2}$ steps required for running $m$ times GHS.
Interestingly, our multi instance algorithm (with precomputation) can be seen as a special case of our precomputation algorithm.
Our multiple instance approach can be freely combined with our precomputations, allowing for a variety of tradeoffs.

Technically, our precomputation and multiple instance group action dlog attacks are adaptations of the techniques from the standard dlog setting in abelian groups. While such an adaptation seems natural, it is per se unclear which techniques transfer
from the dlog to the more restricted group dlog setting, for which $X$ does not offer a group structure.

Our algorithms have direct implications for all group action based cryptosystems, such as CSIDH and its variants. We provide experimental evidence that our techniques work well in the CSIDH setting.



## 2024/568

* Title: Communication-Efficient Multi-Party Computation for RMS Programs
* Authors: Thomas Attema, Aron van Baarsen, Stefan van den Berg, Pedro Capitão, Vincent Dunning, Lisa Kohl
* [Permalink](https://eprint.iacr.org/2024/568)
* [Download](https://eprint.iacr.org/2024/568.pdf)

### Abstract

Despite much progress, general-purpose secure multi-party computation (MPC) with active security may still be prohibitively expensive in settings with large input datasets. This particularly applies to the secure evaluation of graph algorithms, where
each party holds a subset of a large graph.

Recently, Araki et al. (ACM CCS '21) showed that dedicated solutions may provide significantly better efficiency if the input graph is sparse. In particular, they provide an efficient protocol for the secure evaluation of "message passing" algorithms,
such as the PageRank algorithm. Their protocol's computation and communication complexity are both $\tilde{O}(M\cdot B)$ instead of the $O(M^2)$ complexity achieved by general-purpose MPC protocols, where $M$ denotes the number of nodes and $B$ the (
average) number of incoming edges per node. On the downside, their approach achieves only a relatively weak security notion; $1$-out-of-$3$ malicious security with selective abort.

In this work, we show that PageRank can instead be captured efficiently as a restricted multiplication straight-line (RMS) program, and present a new actively secure MPC protocol tailored to handle RMS programs. In particular, we show that the local
knowledge of the participants can be leveraged towards the first maliciously-secure protocol with communication complexity linear in $M$, independently of the sparsity of the graph. We present two variants of our protocol. In our communication-optimized
protocol, going from semi-honest to malicious security only introduces a small communication overhead, but results in quadratic computation complexity $O(M^2)$. In our balanced protocol, we still achieve a linear communication complexity $O(M)$, although
with worse constants, but a significantly better computational complexity scaling with $O(M\cdot B)$. Additionally, our protocols achieve security with identifiable abort and can tolerate up to $n-1$ corruptions.



## 2024/569

* Title: An overview of symmetric fuzzy PAKE protocols
* Authors: Johannes Ottenhues
* [Permalink](https://eprint.iacr.org/2024/569)
* [Download](https://eprint.iacr.org/2024/569.pdf)

### Abstract

Fuzzy password authenticated key exchange (fuzzy PAKE) protocols enable two parties to securely exchange a session-key for further communication. The parties only need to share a low entropy password. The passwords do not even need to be identical, but
can contain some errors. This may be due to typos, or because the passwords were created from noisy biometric readings. In this paper we provide an overview and comparison of existing fuzzy PAKE protocols. Furthermore, we analyze certain security
properties of these protocols and argue that the protocols can be expected to be slightly more secure in practice than can be inferred from their theoretical guarantees.



## 2024/570

* Title: Large-Scale Private Set Intersection in the Client-Server Setting
* Authors: Yunqing Sun, Jonathan Katz, Mariana Raykova, Phillipp Schoppmann, Xiao Wang
* [Permalink](https://eprint.iacr.org/2024/570)
* [Download](https://eprint.iacr.org/2024/570.pdf)

### Abstract

Private set intersection (PSI) allows two parties to compute the intersection of their sets without revealing anything else. In some applications of PSI, a server holds a large set and needs to run PSI with many clients, each with its own small set. In
this setting, however, all existing protocols fall short: they either incur too much cost to compute the intersections for many clients or cannot achieve the desired security requirements.

We design a protocol that particularly suits this setting with simulation-based security against malicious adversaries. In our protocol, the server publishes a one-time, linear-size encoding of its set. Then, multiple clients can each perform a cheap
interaction with the server of complexity linear in the size of each client's set. A key ingredient of our protocol is an efficient instantiation of an oblivious verifiable unpredictable function, which could be of independent interest. To obtain the
intersection, the client can download the encodings directly, which can be accelerated via content distribution networks or peer-to-peer networks since the same encoding is used by all clients; alternatively, clients can fetch only the relevant ones
using verifiable private information retrieval.

Our implementation shows very high efficiency. For a server holding $10^8$ elements and each client holding $10^3$ elements, the size of the server's encoding is 800MB; interacting with each client uses 60MB of communication and runs in under 5s in a WAN
network with 120Mbps bandwidth. Compared with the state-of-the-art PSI protocol, our scheme requires only 0.017 USD per client on an AWS server, which is 5x lower.



## 2024/571

* Title: MiniCast: Minimizing the Communication Complexity of Reliable Broadcast
* Authors: Thomas Locher, Victor Shoup
* [Permalink](https://eprint.iacr.org/2024/571)
* [Download](https://eprint.iacr.org/2024/571.pdf)

### Abstract

We give a new protocol for reliable broadcast with improved communication complexity for long messages. Namely, to reliably broadcast a message a message $m$ over an asynchronous network to a set of $n$ parties, of which fewer than $n/3$ may be corrupt,
our protocol achieves a communication complexity of $1.5 |m| n + O( \kappa n^2 \log(n) )$, where $\kappa$ is the output length of a collision-resistant hash function. This result improves on the previously best known bound for long messages of $2 |m|
n + O( \kappa n^2 \log(n) )$.



## 2024/572

* Title: Split Gröbner Bases for Satisfiability Modulo Finite Fields
* Authors: Alex Ozdemir, Shankara Pailoor, Alp Bassa, Kostas Ferles, Clark Barrett, Işil Dillig
* [Permalink](https://eprint.iacr.org/2024/572)
* [Download](https://eprint.iacr.org/2024/572.pdf)

### Abstract

Satisfiability modulo finite fields enables automated verification for cryptosystems. Unfortunately, previous solvers scale poorly for even some simple systems of field equations, in part because they build a full Gröbner basis (GB) for the system. We
propose a new solver that uses multiple, simpler GBs instead of one full GB. Our solver, implemented within the cvc5 SMT solver, admits specialized propagation algorithms, e.g., for understanding bitsums. Experiments show that it solves important bitsum-
heavy determinism benchmarks far faster than prior solvers, without introducing much overhead for other benchmarks.



## 2024/573

* Title: Tokenised Multi-client Provisioning for Dynamic Searchable Encryption with Forward and Backward Privacy
* Authors: Arnab Bag, Sikhar Patranabis, Debdeep Mukhopadhyay
* [Permalink](https://eprint.iacr.org/2024/573)
* [Download](https://eprint.iacr.org/2024/573.pdf)

### Abstract

Searchable Symmetric Encryption (SSE) has opened up an attractive avenue for privacy-preserved processing of outsourced data on the untrusted cloud infrastructure. SSE aims to support efficient Boolean query processing with optimal storage and search
overhead over large real databases. However, current constructions in the literature lack the support for multi-client search and dynamic updates to the encrypted databases, which are essential requirements for the widespread deployment of SSE on real
cloud infrastructures. Trivially extending a state-of-the-art single client dynamic construction, such as ODXT (Patranabis et al., NDSS’21), incurs significant leakage that renders such extension insecure in practice. Currently, no SSE construction in
the literature offers efficient multi-client query processing and search with dynamic updates over large real databases while maintaining a benign leakage profile.
This work presents the first dynamic multi-client SSE scheme Nomos supporting efficient multi-client conjunctive Boolean queries over an encrypted database. Precisely, Nomos is a multi-reader-single-writer construction that allows only the gate-keeper (
or the data-owner) - a trusted entity in the Nomos framework, to update the encrypted database stored on the adversarial server. Nomos achieves forward and type-II backward privacy of dynamic SSE constructions while incurring lesser leakage than the
trivial extension of ODXT to a multi- client setting. Furthermore, our construction is practically efficient and scalable - attaining linear encrypted storage and sublinear search overhead for conjunctive Boolean queries. We provide an experimental
evaluation of software implementation over an extensive real dataset containing millions of records. The results show that Nomos performance is comparable to the state-of-the-art static conjunctive SSE schemes in practice.



## 2024/574

* Title: PoMMES: Prevention of Micro-architectural Leakages in Masked Embedded Software
* Authors: Jannik Zeitschner, Amir Moradi
* [Permalink](https://eprint.iacr.org/2024/574)
* [Download](https://eprint.iacr.org/2024/574.pdf)

### Abstract

Software solutions to address computational challenges are ubiquitous in our daily lives. One specific application area where software is often used is in embedded systems, which, like other digital electronic devices, are vulnerable to side-channel
analysis attacks. Although masking is the most common countermeasure and provides a solid theoretical foundation for ensuring security, recent research has revealed a crucial gap between theoretical and real-world security. This shortcoming stems from
the micro-architectural effects of the underlying micro-processor. Common security models used to formally verify masking schemes such as the d-probing model fully ignore the micro-architectural leakages that lead to a set of instructions that
unintentionally recombine the shares. Manual generation of masked assembly code that remains secure in the presence of such micro-architectural recombinations often involves trial and error, and is non-trivial even for experts.
Motivated by this, we present PoMMES, which enables inexperienced software developers to automatically compile masked functions written in a high-level programming language into assembly code, while preserving the theoretically proven security in
practice. Compared to the state of the art, based on a general model for microarchitectural effects, our scheme allows the generation of practically secure masked software at arbitrary security orders for in-order processors. The major contribution of
PoMMES is its micro-architecture aware register allocation algorithm, which is one of the crucial steps during the compilation process. In addition to simulation-based assessments that we conducted by open-source tools dedicated to evaluating masked
software implementations, we confirm the effectiveness of the PoMMES-generated codes through experimental analysis. We present the result of power consumption based leakage assessments of several case studies running on a Cortex M0+ micro-controller,
which is commonly deployed in industry.



## 2024/575

* Title: Pairing Optimizations for Isogeny-based Cryptosystems
* Authors: Shiping Cai, Kaizhan Lin, Chang-An Zhao
* [Permalink](https://eprint.iacr.org/2024/575)
* [Download](https://eprint.iacr.org/2024/575.pdf)

### Abstract

In isogeny-based cryptography, bilinear pairings are regarded as a powerful tool in various applications, including key compression, public-key validation and torsion basis generation. However, in most isogeny-based protocols, the performance of pairing
computations is unsatisfactory due to the high computational cost of the Miller function. Reducing the computational expense of the Miller function is crucial for enhancing the overall performance of pairing computations in isogeny-based cryptography.

This paper addresses this efficiency bottleneck. To achieve this, we propose several techniques for a better implementation of pairings in isogeny-based cryptosystems. We use (modified) Jacobian coordinates and present new algorithms for Miller function
computations to compute pairings of order $2^\bullet$ and $3^\bullet$. For pairings of arbitrary order, which are crucial for key compression in some SIDH-based schemes (such as M-SIDH and binSIDH), we combine Miller doublings with Miller additions/
subtractions, leading to a considerable speedup. Moreover, the optimizations for pairing applications in CSIDH-based protocols are also considered in this paper. In particular, our approach for supersingularity verification in CSIDH is 15.3% faster than
Doliskani's test, which is the state-of-the-art.



## 2024/576

* Title: On complexity of the problem of solving systems of tropical polynomial equations of degree two
* Authors: Ivan Buchinskiy, Matvei Kotov, Alexander Treier
* [Permalink](https://eprint.iacr.org/2024/576)
* [Download](https://eprint.iacr.org/2024/576.pdf)

### Abstract

In this paper, we investigate the computational complexity of the problem of solving a one-sided system of equations of degree two of a special form over the max-plus algebra. Also, we consider the asymptotic density of solvable systems of this form.
Such systems have appeared during the analysis of some tropical cryptography protocols that were recently suggested. We show how this problem is related to the integer linear programming problem and prove that this problem is NP-complete. We show that
the asymptotic density of solvable systems of this form with some restrictions on the coefficients, the number of variables, and the number of equations is 0. As a corollary, we prove that this problem (with some restrictions on the coefficients, the
number of variables, and the number of equations) is decidable generically in polynomial time.



## 2024/577

* Title: Determination of cryptographic tables and properties related to the revised boomerang and its application to a fundamental S-box
* Authors: Said Eddahmani, Sihem Mesnager
* [Permalink](https://eprint.iacr.org/2024/577)
* [Download](https://eprint.iacr.org/2024/577.pdf)

### Abstract

In symmetric cryptography, vectorial Boolean functions over finite fields F2n derive strong S-boxes. To this end, the S-box should satisfy a list of tests to resist existing attacks, such as the differential, linear, boomerang, and variants. Several
tables are employed to measure an S- box’s resistance, such as the difference distribution table (DDT) and the boomerang connectivity table (BCT). Following the boomerang attacks recently revisited in terms of the boomerang switch effect, with a lustra-
tion highlighting the power of this technique, a tool called the Boomerang Difference Table (BDT), an alternative to the classical Boomerang BCT, was introduced. Next, two novel tables have been introduced, namely, the Upper Boomerang Connectivity Table
(UBCT) and the Lower Boomerang Connectivity Table (LBCT), which are considered improvements over BCT while allowing systematic evaluation of boomerangs to return over mul- tiple rounds.
This paper focuses on the new tools for measuring the revisited version of boomerang attacks and the related tables UBCT, LBCT, as well as the so-called Extended Boomerang Connectivity Table (EBCT). Specifically, we shall study the properties of these
novel tools and investigate the corresponding tables. We also study their interconnections, their links to the DDT, and their values for affine equivalent vectorial functions and compositional inverses of permutations of F2n . Moreover, we introduce the
concept of the nontrivial boomerang connectivity uniformity and determine the explicit values of all the entries of the EBCT, LBCT, and EBCT for the important cryptographic case of the inverse function.



## 2024/578

* Title: Assessing the quality of Random Number Generators through Neural Networks
* Authors: José Luis Crespo, Javier González-Villa, Jaime Gutierrez, Angel Valle
* [Permalink](https://eprint.iacr.org/2024/578)
* [Download](https://eprint.iacr.org/2024/578.pdf)

### Abstract

In this paper we address the use of Neural Networks (NN) for the
assessment of the quality and hence safety of several Random Number Generators (RNGs), focusing both on the vulnerability of classical Pseudo Random Number Generators (PRNGs), such as Linear Congruential Generators (LCGs) and the RC4 algorithm, and
extending our analysis to non-conventional data sources, such as Quantum Random Number Generators (QRNGs) based on Vertical-Cavity Surface-

[continued in next message]

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