Arithmetic of Finite Fields

Inhaltsverzeichnis

1. Frontmatter

2. Invited Talk I

   1. Frontmatter

   2. A Brief History of Pairings

      Razvan Barbulescu

      Abstract

      Pairings are a relatively new tool in cryptography. Recent progress on the attack algorithms have changed the security estimations. We make a list of pairing families and explain their advantages but also their weaknesses.

3. Elliptic Curves

   1. Frontmatter

   2. Differential Addition on Binary Elliptic Curves

      Reza Rezaeian Farashahi, Seyed Gholamhossein Hosseini

      Abstract

      This paper presents extremely fast differential addition (i.e., the addition of two points with the known difference) and doubling formulas, as the core step in Montgomery scalar multiplication, for various forms of elliptic curves over binary fields. The formulas are provided for binary Edwards, binary Hessian and binary Huff elliptic curves with cost of \(5\mathbf {M}+4\mathbf {S}+1\mathbf {D}\) when the given difference point is in affine form. Here, \(\mathbf {M},\ \mathbf {S},\ \mathbf {D}\) denote the costs of a field multiplication, a field squaring and a field multiplication by a constant, respectively. This paper also presents, new complete differential addition formulas for binary Edwards curves with cost of \(5\mathbf {M}+4\mathbf {S}+2\mathbf {D}\).

   3. Adequate Elliptic Curves for Computing the Product of n Pairings

      Loubna Ghammam, Emmanuel Fouotsa

      Abstract

      Many pairing-based protocols require the computation of the product and/or of a quotient of n pairings where \(n>1\) is a natural integer. Zhang et al. [1] recently showed that the Kachisa-Schafer and Scott family of elliptic curves with embedding degree 16 denoted KSS16 at the 192-bit security level is suitable for such protocols comparatively to the Baretto-Lynn and Scott family of elliptic curves of embedding degree 12 (BLS12). In this work, we provide important corrections and improvements to their work based on the computation of the optimal Ate pairing. We focus on the computation of the final exponentiation which represent an important part of the overall computation of this pairing. Our results improve by 864 multiplications in \(\mathbb {F}_p\) the computations of Zhang et al. [1]. We prove that for computing the product or the quotient of 2 pairings, BLS12 curves are the best solution. In other cases, especially when \(n>2\) as mentioned in [1], KSS16 curves are recommended for computing product of n pairings. Furthermore, we prove that the curve presented by Zhang et al. [1] is not resistant against small subgroup attacks. We provide an example of KSS16 curve protected against such attacks.

   4. On Pseudorandom Properties of Certain Sequences of Points on Elliptic Curve

      László Mérai

      Abstract

      In this paper we study the pseudorandom properties of sequences of points on elliptic curves. These sequences are constructed by taking linear combinations with small coefficients (e.g. \(-1,0,+1\)) of the orbit elements of a point with respect to a given endomorphism of the curve. We investigate the linear complexity and the distribution of these sequences. The result on the linear complexity answers a question of Igor Shparlinski.

4. Applications

   1. Frontmatter

   2. Linear Complexity and Expansion Complexity of Some Number Theoretic Sequences

      Richard Hofer, Arne Winterhof

      Abstract

      We study the predictability of some number theoretic sequences over finite fields and thus their suitability in cryptography. First we analyze the non-periodic binary sequence \(\mathcal {T}=(t_n)_{n\ge 0}\) with \(t_n=1\) whenever n is the sum of three integer squares. We show that it has a large Nth linear complexity, which is necessary but not sufficient for unpredictability. However, it also has a very small expansion complexity and thus is rather predictable.

      Next we prove that some linear combinations of p-periodic sequences of binomial coefficients modulo a prime p have a very small expansion complexity and are predictable despite of a high linear complexity.

      Finally, we consider the Legendre sequence and verify that it does not belong to this class of predictable sequences.

5. Irreducible Polynomials

   1. Frontmatter

   2. On Sets of Irreducible Polynomials Closed by Composition

      Andrea Ferraguti, Giacomo Micheli, Reto Schnyder

      Abstract

      Let \(\mathcal {S}\) be a set of monic degree 2 polynomials over a finite field and let C be the compositional semigroup generated by \(\mathcal S\). In this paper we establish a necessary and sufficient condition for C to be consisting entirely of irreducible polynomials. The condition we deduce depends on the finite data encoded in a certain graph uniquely determined by the generating set \(\mathcal {S}\). Using this machinery we are able both to show examples of semigroups of irreducible polynomials generated by two degree 2 polynomials and to give some non-existence results for some of these sets in infinitely many prime fields satisfying certain arithmetic conditions.

   3. A Note on the Brawley-Carlitz Theorem on Irreducibility of Composed Products of Polynomials over Finite Fields

      Akihiro Munemasa, Hiroko Nakamura

      Abstract

      We give a new proof of the Brawley-Carlitz theorem on irreducibility of the composed products of irreducible polynomials. Our proof shows that associativity of the binary operation for the composed product is not necessary. We then investigate binary operations defined by polynomial functions, and give a sufficient condition in terms of degrees for the requirement in the Brawley-Carlitz theorem.

6. Invited Talk II

   1. Frontmatter

   2. On Arcs and Quadrics

      Simeon Ball

      Abstract

      An arc is a set of points of the \((k-1)\)-dimensional projective space over the finite field with q elements \({\mathbb F}_q\), in which every k-subset spans the space. In this article, we firstly review Glynn’s construction of large arcs which are contained in the intersection of quadrics. Then, for q odd, we construct a series of matrices \(\mathrm {F}_n\), where n is a non-negative integer and \(n \leqslant |G|-k-1\), which depend on a small arc G. We prove that if G can be extended to a large arc S of size \(q+2k-|G|+n-2\) then, for each vector v of weight three in the column space of \(\mathrm {F}_n\), there is a quadric \(\psi _v\) containing \(S \setminus G\). This theorem is then used to deduce conditions for the existence of quadrics containing all the vectors of S.

7. Applications to Cryptography

   1. Frontmatter

   2. A Generalised Successive Resultants Algorithm

      James H. Davenport, Christophe Petit, Benjamin Pring

      Abstract

      The Successive Resultants Algorithm (SRA) is a root-finding algorithm for polynomials over \(\mathbb {F}_{p^n}\) and was introduced at ANTS in 2014 [19]. The algorithm is efficient when the characteristic p is small and \(n > 1\). In this paper, we abstract the core SRA algorithm to arbitrary finite fields and present three instantiations of our general algorithm, one of which is novel and makes use of a series of isogenies derived from elliptic curves with sufficiently smooth order.

   3. Distribution and Polynomial Interpolation of the Dodis-Yampolskiy Pseudo-Random Function

      Thierry Mefenza, Damien Vergnaud

      Abstract

      We give some theoretical support to the security of the cryptographic pseudo-random function proposed by Dodis and Yampolskiy in 2005. We study the distribution of the function values over general finite fields and over elliptic curves defined over prime finite fields. We also prove lower bounds on the degree of polynomials interpolating the values of these functions in these two settings.

8. Boolean Functions

   1. Frontmatter

   2. A Conjecture About Gauss Sums and Bentness of Binomial Boolean Functions

      Jean-Pierre Flori

      Abstract

      In this note, the polar decomposition of binary fields of even extension degree is used to reduce the evaluation of the Walsh transform of binomial Boolean functions to that of Gauss sums. In the case of extensions of degree four times an odd number, an explicit formula involving a Kloosterman sum is conjectured, proved with further restrictions, and supported by extensive experimental data in the general case. In particular, the validity of this formula is shown to be equivalent to a simple and efficient characterization for bentness previously conjectured by Mesnager.

   3. Generalized Bent Functions and Their Gray Images

      Thor Martinsen, Wilfried Meidl, Pantelimon Stănică

      Abstract

      In this paper we prove that generalized bent (gbent) functions defined on \(\mathbb {F}_2^n\) with values in \(\mathbb {Z}_{2^k}\) are regular, and show connections between the (generalized) Walsh spectrum of these functions and their components. Moreover we analyze generalized bent and semibent functions with values in \(\mathbb {Z}_{16}\) in detail, extending earlier results on gbent functions with values in \(\mathbb {Z}_4\) and \(\mathbb {Z}_8\).

9. Cryptography

   1. Frontmatter

   2. Enhanced Digital Signature Using RNS Digit Exponent Representation

      Thomas Plantard, Jean-Marc Robert

      Abstract

      Digital Signature Algorithm (DSA) involves modular exponentiation, of a public and known base by a random one-time exponent. In order to speed-up this operation, well-known methods take advantage of the memorization of base powers. However, due to the cost of the memory, to its small size and to the latency of access, previous research sought for minimization of the storage. In this paper, taking into account the modern processor features and the growing size of the cache memory, we improve the storage/efficiency trade-off, by using a RNS Digit exponent representation. We then propose algorithms for modular exponentiation. The storage is lower for equivalent complexities for modular exponentiation computation. The implementation performances show significant memory saving, up to 3 times for the largest NIST standardized key sizes compared to state of the art approaches.

   3. Efficient Finite Field Multiplication for Isogeny Based Post Quantum Cryptography

      Angshuman Karmakar, Sujoy Sinha Roy, Frederik Vercauteren, Ingrid Verbauwhede

      Abstract

      Isogeny based post-quantum cryptography is one of the most recent addition to the family of quantum resistant cryptosystems. In this paper we propose an efficient modular multiplication algorithm for primes of the form \(p=2\cdot {2^a}3^b-1\) with b even, typically used in such cryptosystem. Our modular multiplication algorithm exploits the special structure present in such primes. We compare the efficiency of our technique with Barrett reduction and Montgomery multiplication. Our C implementation shows that our algorithm is approximately 3 times faster than the normal Barrett reduction.

   4. A Search Strategy to Optimize the Affine Variant Properties of S-Boxes

      Stjepan Picek, Bohan Yang, Nele Mentens

      Abstract

      Affine transformations are an often used tool in symmetric key cryptography. They are mostly known as a way of removing fixed points in S-boxes, as for instance in the AES S-box. In general, affine transformations do not have an influence on most cryptographic properties, since those properties are affine invariant; affine transformations only change the representation of the S-box. Because of that, there is not much research on what would be the best affine transformation in terms of usability in practical scenarios. With this research, we try to close that gap; we concentrate on several cryptographic properties and one implementation property that are variable under various affine transformations. To provide experimental validations, we concentrate on affine transformations in S-boxes of three sizes, namely, \(4\times 4\), \(5\times 5\), and \(8\times 8\). Our results indicate that it is possible to optimize one or more of the considered properties. Finally, although we experiment with only a handful of properties, our methodology is of a general nature and could be used for other cryptographic properties that are affine variant.

10. Cryptography and Boolean Functions

    1. Frontmatter

    2. A Super-Set of Patterson-Wiedemann Functions – Upper Bounds and Possible Nonlinearities

       Selçuk Kavut, Subhamoy Maitra, Ferruh Özbudak

       Abstract

       Constructing Boolean functions on odd number of variables with nonlinearity exceeding the bent concatenation bound is one of the most difficult combinatorial problems in the domain of Boolean functions and it has deep implications to coding theory and cryptology. After demonstration of such functions by Patterson and Wiedemann in 1983, for more than three decades the efforts have been channelized in obtaining the instances only. For the first time, in this paper, we try to explore non-trivial upper bounds on nonlinearity of such functions which are invariant under several group actions. In fact, we consider much larger sets of functions than what have been considered so far and obtain tight upper bounds on the nonlinearity in several cases. To support our claims, we present computational results for functions on n variables where n is an odd composite integer, \(9\le n\le 39\). In particular, our results for \(n = 15\) and 21 are of immediate interest given recent research results in this domain. Not only the upper bounds, we also identify what are the nonlinearities that can actually be achieved above the bent concatenation bound for such class of functions.

    3. A Correction and Improvements of Some Recent Results on Walsh Transforms of Gold Type and Kasami-Welch Type Functions

       Ayhan Coşgun, Ferruh Özbudak

       Abstract

       We give explicit evaluations of Walsh transforms of Gold type functions \(f(x)=\mathrm{Tr}_K\left( x^{2^a+1}+x^{2^b+1} \right) \), \(0 \le a < b\) when \(\gcd \left( b-a, k \right) =\gcd \left( b+a, k \right) \) and Kasami-Welch type functions \(f(x)=\mathrm{Tr}_K\left( x^{\frac{2^{ta}+1}{2^a+1}} \right) \), when t is odd, \(\gcd \left( 2^k -1, 2^a + 1\right) =1\), k is even. Therefore we correct a recent result of Roy’2012, we solve an open problem stated in Roy’2012 and we improve and generalize some results of Roy’2012 and Lahtonen-McGuire-Ward’2007.

    4. A Practical Group Signature Scheme Based on Rank Metric

       Quentin Alamélou, Olivier Blazy, Stéphane Cauchie, Philippe Gaborit

       Abstract

       In this work, we propose the first rank-based group signature. Our construction enjoys two major advantages compared to concurrent post-quantum schemes since it is both practicably instantiated with public key and signature sizes logarithmic in the number of group members, and dynamic in a relaxation of the reference BSZ model. For such a result, we introduce a new rank-based tool, referred as the Rank Concatenated Stern’s protocol, enabling to link different users to a common syndrome. This protocol, which could be of independent interest, can be seen as a Stern-like protocol with an additional property that permits a verifier to check the weight of each part of a split secret. Along with this work, we also define two rank-based adaptations of Hamming-based problems, referred as the One More Rank Syndrome Decoding and the Decision Rank Syndrome Decoding problems for which we discuss the security. Embedded into Fiat-Shamir paradigm, our authentication protocol leads to a group signature scheme secure in the Random Oracle Model assuming the security of rank-based systems (namely RankSign and LRPC codes) and the newly introduced problems. For a 100 bits security level, we give an example of parameters which lead to a signature size of 550 kB and 5 kB for the public key.

11. Backmatter