CARAMBA: Cryptology, arithmetic : algebraic methods for better algorithms

Abstract In this survey, the authors review the main quantum algorithms for solving the computational problems that serve as hardness assumptions for cryptosystem. To this end, the authors consider both the currently most widely used classically secure cryptosystems, and the most promising candidates for post‐quantum secure cryptosystems. The authors provide details on the cost of the quantum algorithms presented in this survey. The authors furthermore discuss ongoing research directions that can impact quantum cryptanalysis in the future.

In this paper we present a boomerang analysis of WARP, a recently proposed Generalized Feistel Network with extremely compact hardware implementations. We start by looking for boomerang characteristics that directly take into account the boomerang switch effects by showing how to adapt Delaune et al. automated tool to the case of Feistel ciphers, and discuss several improvements to keep the execution time reasonable. This technique returns a 23-round distinguisher of probability 2−124, which becomes the best distinguisher presented on WARP so far. We then look for an attack by adding the key recovery phase to our model and we obtain a 26-round rectangle attack with time and data complexities of 2115.9 and 2120.6 respectively, again resulting in the best result presented so far. Incidentally, our analysis discloses how an attacker can take advantage of the position of the key addition (put after the S-box application to avoid complementation properties), which in our case offers an improvement of a factor of 275 of the time complexity in comparison to a variant with the key addition positioned before. Note that our findings do not threaten the security of the cipher which iterates 41 rounds.

We propose a probabilistic variant of Brill-Noether’s algorithm for computing a basis of the Riemann-Roch space L ( D ) L(D) associated to a divisor D D on a projective nodal plane curve C \mathbb {C} over a sufficiently large perfect field k k . Our main result shows that this algorithm requires at most O ( max ( deg ⁡ ( C ) 2 ω , deg ⁡ ( D + ) ω ) ) O(\max (\deg (\mathbb {C})^{2\omega }, \deg (D_+)^\omega )) arithmetic operations in k k , where ω \omega is a feasible exponent for matrix multiplication and D + D_+ is the smallest effective divisor such that D + ≥ D D_+\geq D . This improves the best known upper bounds on the complexity of computing Riemann-Roch spaces. Our algorithm may fail, but we show that provided that a few mild assumptions are satisfied, the failure probability is bounded by O ( max ( deg ⁡ ( C ) 4 , deg

Boolean functions are usually studied under the assumption that each input bit is considered independent and identically distributed. However, in the case of some stream ciphers, a keystream bit is generated by using a nonlinear Boolean function with inputs from a restricted domain. At Eurocrypt 2016, one such stream cipher (FLIP) has been proposed, where a Boolean function on n variables was exploited with inputs of weight n/2 only. Recently, Carlet et al. studied several properties of such functions and obtained certain bounds on linear approximations of direct sum in the restricted domain. In this paper, we observe that for a direct sum like f = f1+ f2, the inputs to each sub-function f1, f2do not follow a uniform distribution in the restricted domain. In this regard, we study the properties of the Boolean functions by considering a general probability distribution on the inputs. We further obtain several bounds related to the biases of direct sums. Finally, we obtain a lower bound on the bias of the nonlinear filter function of FLIP. Our results provide a general framework to study security parameters of ciphers over restricted domain.

Computing discrete logarithms in finite fields is a main concern in cryptography. The best algorithms in large and medium characteristic fields (e.g., G F ( p 2 ) \rm {GF}(p^2) , G F ( p 12 ) \rm {GF}(p^{12}) ) are the Number Field Sieve and its variants (special, high-degree, tower). The best algorithms in small characteristic finite fields (e.g., G F ( 3 6 ⋅ 509 ) \rm {GF}(3^{6 \cdot 509}) ) are the Function Field Sieve, Joux’s algorithm, and the quasipolynomial-time algorithm. The last step of this family of algorithms is the individual logarithm computation. It computes a smooth decomposition of a given target in two phases: an initial splitting, then a descent tree. While new improvements have been made to reduce the complexity of the dominating relation collection and linear algebra steps, resulting in a smaller factor basis (database of known logarithms of small elements), the last step remains at the same level of difficulty. Indeed, we have to find a smooth decomposition of a typically large element in the finite field. This work improves the initial splitting phase and applies to any nonprime finite field. It is very efficient when the extension degree is composite. It exploits the proper subfields, resulting in a much more smooth decomposition of the target. This leads to a new trade-off between the initial splitting step and the descent step in small characteristic. Moreover it reduces the width and the height of the subsequent descent tree.

We propose a new algorithm for multiplying dense polynomials with integer coefficients in a parallel fashion, targeting multi-core processor architectures. Complexity estimates and experimental comparisons demonstrate the advantage of this new approach.

We outline an algorithm to compute $\unicode[STIX]{x1D703}(z,\unicode[STIX]{x1D70F})$ in genus two in quasi-linear time, borrowing ideas from the algorithm for theta constants and the one for $\unicode[STIX]{x1D703}(z,\unicode[STIX]{x1D70F})$ in genus one. Our implementation shows a large speed-up for precisions as low as a few thousand decimal digits. We also lay out a strategy to generalize this algorithm to genus $g$ .

International audience

In Chapter 11, History of Cryptographic Key Sizes, Nigel P. Smart and Emmanuel Thomé provide an overview of improvements over the years in estimating the security level of the main cryptographic hardness assumptions. These improvements heavily rely on the algorithmic innovations discussed in Chapters 2 to 5, but combining all those ideas into concrete key-size recommendations is not immediate. Smart and Thomé have been at the forefront of cryptanalytic research and recommending cryptographic key sizes and conclude with current recommendations in Chapter 11.

In this article, we propose an instantiation, called${\sf Stanislas}$, of a dedicated Self-Synchronizing Stream Cipher (SSSC) involving an automaton with finite input memory using non-triangular state transition functions. Previous existing SSSC are based on automata with shifts or triangular functions ($T$–functions) as state transition functions. Our algorithm${\sf Stanislas}$admits a matrix representation deduced from a general and systematic methodology called Linear Parameter Varying (LPV). This particular representation comes from the automatic theory and from a special property of dynamical systems called flatness. Hardware implementations and comparisons with some state-of-the-art stream ciphers on Xilinx FPGAs are presented. It turns out that${\sf Stanislas}$provides bigger throughput than the considered stream ciphers (synchronous and self-synchronizing) when straightforward implementations are considered. Moreover, its synchronization delay is much smaller than the SSSC Moustique (40 clock cycles instead of 105) and the standard approach CFB1-AES128 (40 clock cycles instead of 128).

The impossible boomerang attack, introduced in 2008 by Jiqiang Lu, is an extension of the impossible differential attack that relies on a boomerang distinguisher of probability 0 for discarding incorrect key guesses. In Lu’s work, the considered impossible boomerang distinguishers were built from 4 (different) probability-1 differentials that lead to 4 differences that do not sum to 0 in the middle, in a miss-in-the-middle way.In this article, we study the possibility of extending this notion by looking at finerlevel contradictions that derive from boomerang switch constraints. We start by discussing the case of quadratic Feistel ciphers and in particular of the Simon ciphers. We exploit their very specific boomerang constraints to enforce a contradiction that creates a new type of impossible boomerang distinguisher that we search with an SMT solver. We next switch to word-oriented ciphers and study how to leverage the Boomerang Connectivity Table contradictions. We apply this idea to SKINNYee, a recent tweakable block cipher proposed at Crypto 2022 and obtain a 21-round distinguisher.After detailing the process and the complexities of an impossible boomerang attack in the single (twea)key and related (twea)key model, we extend our distinguishers into attacks and present a 23-round impossible boomerang attack on Simon-32/64 (out of 32 rounds) and a 29-round impossible boomerang attack on SKINNYee (out of 56 rounds). To the best of our knowledge our analysis covers two more rounds than the (so far, only) other third-party analysis of SKINNYee that has been published to date.

Quantum attacks using superposition queries are known to break many classically secure modes of operation. While these attacks do not necessarily threaten the security of the modes themselves, since they rely on a strong adversary model, they help us to draw limits on their provable security.Typically these attacks use the structure of the mode (stream cipher, MAC or authenticated encryption scheme) to embed a period-finding problem, which can be solved with a dedicated quantum algorithm. The hidden period can be recovered with a few superposition queries (e.g., O(n) for Simon’s algorithm), leading to state or key-recovery attacks. However, this strategy breaks down if the period changes at each query, e.g., if it depends on a nonce.In this paper, we focus on this case and give dedicated state-recovery attacks on the authenticated encryption schemes Rocca, Rocca-S, Tiaoxin-346 and AEGIS- 128L. These attacks rely on a procedure to find a Boolean hidden shift with a single superposition query, which overcomes the change of nonce at each query. This approach has the drawback of a lower success probability, meaning multiple independent (and parallelizable) runs are needed.We stress that these attacks do not break any security claim of the authors, and do not threaten the schemes if the adversary only makes classical queries.

An isogeny graph is a graph whose vertices are principally polarizable abelian varieties and whose edges are isogenies between these varieties. In his thesis, Kohel describes the structure of isogeny graphs for elliptic curves and shows that one may compute the endomorphism ring of an elliptic curve defined over a finite field by using a depth-first search (DFS) algorithm in the graph. In dimension 2, the structure of isogeny graphs is less understood and existing algorithms for computing endomorphism rings are very expensive. In this article, we show that, under certain conditions, the problem of determining the endomorphism ring can also be solved in genus 2 with a DFS-based algorithm. We consider the case of genus-2 Jacobians with complex multiplication, with the assumptions that the real multiplication subring has class number one and is locally maximal at ℓ, for ℓ a fixed prime. We describe the isogeny graphs in that case, by considering cyclic isogenies of degree ℓ, under the assumption that there is an ideal l of norm ℓ in K0 which is generated by a totally positive algebraic integer. The resulting algorithm is implemented over finite fields, and examples are provided. To the best of our knowledge, this is the first DFS-based algorithm in genus 2.

The goal of this article is to give a survey on the various computational and mathematical issues and progress related to the problem of providing efficient correctly rounded elementary functions in floating-point arithmetic. We also aim at convincing the reader that a future standard for floating-point arithmetic should require the availability of a correctly rounded version of a well-chosen core set of elementary functions. We discuss the interest and feasibility of this requirement.

International audience

Abstract. In 2010, Freeman, Scott, and Teske published a well-known taxonomy compiling the best known families of pairing-friendly elliptic curves. Since then, the research effort mostly shifted from the generation of pairing-friendly curves to the improvement of algorithms or the assessment of security parameters to resist the latest attacks on the discrete logarithm problem. Consequently, very few new families were discovered. However, the need of pairing-friendly curves of prime order in some new applications such as SNARKs has reignited the interest in the generation of pairing-friendly curves, with the hope of finding families similar to the one discovered by Barreto and Naehrig. Building on the work of Kachisa, Schaefer, and Scott, we show that some particular elements of quadratic extensions of a cyclotomic field generate families of pairing-friendly curves with small parameters. By exhaustive search among these elements, we discovered new families of curves of embedding degree [Formula: see text], [Formula: see text], and [Formula: see text]. We provide an open-source SageMath implementation of our technique. We obtain curves of cryptographic size from our new families and we give a proof-of-concept SageMath implementation of a pairing on some new curves.

Arithmetic hash functions defined over prime fields have been actively developed and used in verifiable computation (VC) protocols. Among those, ellipticcurve- based SNARKs require large (256-bit and higher) primes. Such hash functions are notably slow, losing a factor of up to 1000 compared to regular constructions like SHA-2/3.In this paper, we present the hash function Skyscraper, which is aimed at large prime fields and provides major improvements compared to Reinforced Concrete and Monolith. First, the design is exactly the same for all large primes, which simplifies analysis and deployment. Secondly, it achieves a performance comparable to cryptographic hash standards by using low-degree non-invertible transformations and minimizing modulo reductions. Concretely, it hashes two 256-bit prime field (BLS12-381 curve scalar field) elements in 135 nanoseconds, whereas SHA-256 needs 42 nanoseconds on the same machine.The low circuit complexity of Skyscraper, together with its high native speed, should allow a substantial reduction in many VC scenarios, particularly in recursive proofs.

1 sin, tan) of the Intel Math Library, in some domains (however the code might have changed since then).Today, at least for single precision and most double precision functions, it is known how to get correct rounding (for all rounding modes, not only for rounding to nearest) at very low cost, and reference implementations exist that outperform current libraries [28,15].

In [2], Graillat and Jezequel prove a bound on the maximal error for the FastTwoSumalgorithm with directed roundings. We improve that bound by a factor 2, even in the case of underflow.We also study the case when FastTwoSum is used in the ``wrong order''.

The classical heuristic complexity of the Number Field Sieve (NFS) is the solution of an optimization problem that involves an unknown function, usually noted $o(1)$ and called $ξ(N)$ throughout this paper, which tends to zero as the entry $N$ grows. The aim of this paper is to find optimal asymptotic choices of the parameters of NFS as $N$ grows, in order to minimize its heuristic asymptotic computational cost. This amounts to minimizing a function of the parameters of NFS bound together by a non-linear constraint. We provide precise asymptotic estimates of the minimizers of this optimization problem, which yield refined formulas for the asymptotic complexity of NFS. One of the main outcomes of this analysis is that $ξ(N)$ has a very slow rate of convergence: We prove that it is equivalent to $4{\log}{\log}{\log}\,N/(3{\log}{\log}\,N)$. Moreover, $ξ(N)$ has an unpredictable behavior for practical estimates of the complexity. Indeed, we provide an asymptotic series expansion of $ξ$ and numerical experiments indicate that this series starts converging only for $N>\exp(\exp(25))$, far beyond the practical range of NFS. This raises doubts on the relevance of NFS running time estimates that are based on setting $ξ=0$ in the asymptotic formula.