- Anne CANTEAUT (INRIA, France)
- Xiangdong HOU (University of South Florida, USA)
- Sophie HUCZYNSKA (University of St Andrews, UK)
- Nicholas KATZ (Princeton University, USA)
- Daniel PANARIO (Carleton University, Canada)
- Henning STICHTENOTH (Sabanci University, Turkey)
- Christopher UMANS (California Institute of Technology, USA)
- Geertrui VAN DE VOORDE (Ghent Univeristy, Vrije Universiteit Brussel, Belgium)
- Arne WINTERHOF (RICAM, Austria)
Anne CANTEAUT (INRIA, France)
Title: Extended differential properties of cryptographic functions
Differential cryptanalysis is one of the very first attack proposed against block ciphers. This attack exploits the fact that some derivatives of the cipher (or of a reduced version of the cipher) have a nonrandom output distribution. Since this distribution highly depends on the behaviour of the derivatives of the nonlinear components of the cipher, Nyberg and Knudsen have introduced the notion of differential uniformity which measures the quality of an Sbox regarding its resistance to differential attacks. This notion is the starting point of many works, including the study and the construction of the so-called APN functions, which are the functions providing the best resistance against differential attacks.
However, many new primitives have been proposed in the last five years, including the 64 hash functions submitted to the SHA-3 competition and a lot of lightweight block ciphers. Many of those new proposals have been attacked or evaluated by several sophisticated variants of the original differential attack. Some of them appear to be able to break some primitives which have been proved resistant against differential cryptanalysis. Those attacks include the cube attack, the rebound attack, the linear subspace attack and some meet-in-the-middle attacks.
In this talk, we will study some properties of the building-blocks of a cipher and their impacts on these new attacks. In particular, we will investigate their connections with the classical notion of differential uniformity, and we will discuss the different criteria for choosing an appropriate nonlinear function when designing a new block cipher.
Xiangdong HOU (University of South Florida, USA)
Title: New Permutation Binomials and Trinomials over Finite Fields
Among permutation polynomials over finite fields, those in simple algebraic forms are particularly interesting. Such permutation polynomials are sometimes the result of the mysterious interplay between the algebraic and combinatorial structures of the finite field. In this talk we present some new permutation binomials and trinomials over finite fields. We will describe some useful ideas and unusual tools in the proofs of the results. (full abstract)
Sophie HUCZYNSKA (University of St Andrews, UK)
Title: Elements with special properties: how can we prove they exist?
There are various reasons why we might want to know whether a finite field element exists which simultaneously possesses several desirable properties. For example, we might want an element which generates the field both additively and multiplicatively, or a generator with specified norm and/or trace. Existence questions of this form have been asked since the 1930s, and continue to be asked today. In this talk, I will discuss these questions, and the techniques which we currently possess for answering them. I will show how these techniques have been developed over time and continue to evolve today, and also discuss existence questions for which we must extend the current approach further, if we are to answer them.
Nicholas KATZ (Princeton University, USA)
Title: Diophantine questions over finite fields
Henning STICHTENOTH (Sabanci University, Turkey)
Title: New towers over finite fields
The aim of this talk is to present a recent result by A. Bassa, P. Beelen, A. Garcia and H. Stichtenoth, which includes and generalizes all previous asymptotic bounds on curves over non-prime finite fields. (full abstract)
Daniel PANARIO (Carleton University, Canada)
Title: Analytic and Probabilistic Combinatorics for Polynomials over Finite Fields
The central objects of this talk are univariate polynomials over finite fields. We first review a methodology from analytic combinatorics that allows not only the study of the decomposition of polynomials into its irreducible factors but also the derivation of algorithmic properties as well as the estimation of average-case analysis of algorithms. This methodology can be naturally used to provide precise information on the factorization of polynomials into its irreducible factors similar to the classical problem of the decomposition of integers into primes. Examples of these results are provided. The shape of a random univariate polynomial over a finite field is also given.
Then, we briefly show several results for random polynomials over finite fields that were obtained using other methodologies based on probability and probabilistic combinatorics. For example we comment on a study of the joint degree distribution of the irreducible factors of a polynomial by means of a discrete random process. We also comment of an Erdos-Turan type of approach for the study of the expected degree of the splitting field of a random polynomial over a finite field.
We conclude providing some open problems.
Christopher UMANS (California Institute of Technology, USA)
Title: Algebraic constructions of randomness extractors
Randomness extractors and their cousins, randomness condensers, are unbalanced bipartite graph with certain "random-like" properties. Explicit constructions of these objects have found widespread applications in diverse areas, including computational complexity, algorithms, data structures, distributed computation, hardness of approximation, coding theory and compressed sensing. A great deal of work over the past 20+ years has focused on finding explicit constructions matching the parameters achieved by probabilistic existence proofs. Current constructions come close, but are not yet optimal.
A significant advance was achieved by Guruswami, Umans, and Vadhan who used Parvaresh-Vardy codes to construct extractors and condensers that are optimal up to constants in all of the main parameters. The construction is based on polynomials over finite fields, and both the construction and short proof use a clever argument involving extension fields (invented by Parvaresh and Vardy) to obtain strong bounds.
Since then, work by Dvir, Kopparty, Saraf and Sudan slightly beat the GUV parameters using a different, and more complicated, construction. With Amnon Ta-Shma, we have extended the main ideas in GUV, so that a "two-level" application of the main algebraic trick in that work, together with several additional ideas, now leads to a simple construction that matches the current world-record constructions.
I will describe these constructions and proof ideas. I'll also discuss an appealing algebraic-geometric conjecture that represents the current barrier to achieving essentially optimal condensers within our framework.
(Based on joint work with Venkat Guruswami, Amnon Ta-Shma, and Salil Vadhan)
Geertrui VAN DE VOORDE (Ghent Univeristy, Vrije Universiteit Brussel, Belgium)
Title: Field reduction in finite projective geometry
In this talk, we will discuss the relevance of field reduction in the area of finite projective geometry; we will present some classical constructions that can be obtained via this technique as well as recent results. (full abstract)
Arne WINTERHOF (RICAM, Austria)
Title: Some applications of character sums
Character sums are important tools in the theory of finite fields and have many application areas including coding theory, wireless communication, Monte Carlo methods, pseudorandom number generation, analysis of algorithms, and quantum physics. The talk contains a collection of applications including some classical and well-known ones as the construction of Hadamard matrices or diagonal equations as well as more recent and maybe less known ones as the analysis of nonlinear pseudorandom numbers and mutually unbiased bases for measuring quantum states.