Carleton Finite Fields eSeminar - Summer 2020 Abstracts

School of Mathematics and Statistics
Carleton University


Organized by: Daniel Panario, David Thomson, and Steven Wang.
e-mail: finitefields@math.carleton.ca

Summer 2020 Abstracts

Date/Time: September 2, 2020 12:00 Eastern (UTC -4:00)

Speaker: Anna-Lena Horlemann (University of St. Gallen)
Title: Invariants of linear rank-metric codes -- and what to do with them
Abstract: We show that the sequence of dimensions of the linear spaces, generated by a given (finite field) rank-metric code together with itself under several applications of a field automorphism, is an invariant for the whole equivalence class of the code. The same property is proven for the sequence of dimensions of the intersections of itself under several applications of a field automorphism. These invariants give rise to easily computable criteria to check if two codes are inequivalent. With these criteria we can derive bounds on the number of equivalence classes of rank-metric codes, derive new characterizations of the well-known Gabidulin codes, and show that certain code constructions actually lead to equivalent codes. slides, video.

Date/Time: August 26, 2020, 12:00 Eastern (UTC -4:00)

Speaker: Shuxing Li (Simon Fraser University)
Title: Intersection distribution and its applications
Abstract: Given a polynomial f over finite field Fq, its intersection distribution concerns the collective behaviour of a collection of polynomials {f(x)+cx | c \in Fq}. Each polynomial f canonically induces a (q+1)-set S_f in the classical projective plane PG(2,q) and the intersection distribution of f reflects how the point set S_f interacts with the lines in PG(2,q). Motivated by the long-standing open problem of classifying oval monomials, which are over F_2^n having the same intersection distribution as x^2, we consider the next simplest case: classifying all monomials over Fq having the same intersection distribution as x^3. Some characterizations of such monomials are derived and as a consequence, a conjectured complete list of such monomials is proposed. As an application, we observe that every monomial over F_3^n with the same intersection distribution as x^3 naturally leads to a Steiner triple system. Interestingly, new examples of Steiner triple systems, which are nonisomorphic to the classical ones, are obtained. This is joint work with Gohar Kyureghyan and Alexander Pott. slides, video.

Date/Time: August 19, 2020 12:00 Eastern (UTC -4:00)

Speaker: Qi Cheng (Oklahoma University)
Title: The Discrete Logarithms over Kummer and Artin-Schreier extensions
Abstract: Many cryptography protocols rely on hard computational number theoretical problems for security. The discrete logarithm problem over finite fields or elliptic curves is one of the most important candidates, besides the integer factorization problem. In this talk, I will first survey several algorithms attacking the discrete logarithms over finite fields, starting from generic algorithms and the index calculus. My discussion will then be focusing on the of quasi-polynomial-time descending, and its application on the Kummer and Artin-Schreier extensions. slides video

Date/Time: August 12, 2020 12:00 Eastern (UTC -4:00)

Speaker: Lucas Reis (Federal University of Minas Gerais)
Title: Character sums estimates over affine spaces applied to existence results in finite fields
Abstract: In this talk, we will discuss the problem of estimating the sum of a multiplicative character over the elements of an affine space. We present a new non-trivial bound on such sums, along with some applications. In particular, we provide asymptotically sharp results on the existence of special primitive elements in finite fields. slides video

Date/Time: July 29, 2020 12:00 Eastern (UTC -4:00)

Speaker: Marco Baldi (Università Politecnica delle Marche)
Title: QC-LDPC codes, QC-MDPC codes and their use in post-quantum cryptography
Abstract: Low-density parity-check (LDPC) codes are a family of modern error correcting codes exploiting a random-based design and iterative decoding algorithms allowing them to approach the channel capacity. The structured subclass of LDPC codes characterized by quasi-cyclicity (QC), named QC-LDPC codes, is known to achieve practically the same performance as general LDPC codes while enabling more compact representation and easier implementation. The use of QC-LDPC codes and of their variant known as QC-MDPC codes in the framework of the McEliece cryptosystem has shown to be an important avenue for overcoming the main limitations of the original McEliece cryptosystem based on Goppa codes. Using QC-LDPC and QC-MDPC codes in cryptography, however, poses some new challenges with respect to their classical use for data reliability. Nevertheless, variants of the McEliece and Niederreiter cryptosystems based on these codes are now under consideration by NIST within the standardization process of new post-quantum cryptographic primitives. The seminar will recall the basics of QC-LDPC and QC-MDPC codes and then describe the main cryptographic primitives relying on these codes, along with some open research challenges in this area. slides video

Date/Time: July 22, 2020 12:00 Eastern (UTC -4:00)

Speaker: Guillermo Matera (Universidad Nacional de General Sarmiento)
Title: The distribution of factorization patterns on nonlinear families of univariate polynomials over a finite field
Abstract: In this talk we discuss an estimate on the number |A_λ| of elements on a nonlinear family A of monic polynomials of Fq[T] of degree r having a given factorization pattern λ. We show that |A_λ| = T(λ) q^{r−m} + O(q^{r−m−1/2}), where T(λ) is the proportion of elements of the symmetric group of r elements with cycle pattern λ and m is the codimension of A. We provide explicit upper bounds for the constants underlying the O-notation in terms of λ and A with "good" behavior. Finally, we apply these results to analyze the average-case complexity of the classical factorization algorithm restricted to the family A, showing that it behaves as good as in the general case. This is based on joint work with Mariana Pérez and Melina Privitelli. slides video

Date/Time: July 15, 2020 12:00 Eastern (UTC -4:00)

Speaker: Alev Topuzoglu (Sabanci University)
Title: On the arithmetic of sequences of permutation polynomials
Abstract: In this talk, we will present recent results on factorization of a large class of permutation polynomials. We also discuss sequences and iterations of permutation polynomials. In particular, we address various problems concerning number theoretic properties of irreducible factors of terms of such sequences. This is based on joint work with Tekgul Kalayci and Henning Stichtenoth. slides

Date/Time: June 24, 2020 12:00 Eastern (UTC -4:00)

Speaker: Petr Lisonek (Simon Fraser University)
Title: Contextual hypergraphs
Abstract: Contextuality is one of the features that distinguishes quantum mechanics from classical mechanics. There are several ways to formalize contextuality mathematically. One such formalization consists of a hypergraph whose vertices are labelled by Hermitian operators such that, for each hyperedge, certain conditions are fulfilled by the operators occurring in it. A contextual hypergraph is one that admits such vertex labeling. The goal of our work is to construct large (preferably infinite) families of contextual hypergraphs. Historically, contextual hypergraphs have been found mostly by computational searches and ad-hoc constructions. In our work we aim at computer-free, systematical constructions, which use combinatorial ingredients such as difference matrices and finite geometries. Finite fields play a central role in obtaining these ingredients. We use appropriate group actions to ensure that our contextual hypergraphs are vertex-transitive, which is recognized as an added value in the quantum mechanics applications. The talk does not require any knowledge of quantum physics. This is joint work with Stefan Trandafir. slides

Date/Time: June 17, 2020 12:00 Eastern (UTC -4:00)

Speaker: Luciane Quoos (Federal University of Rio de Janeiro)
Title: Locally recoverable codes
Abstract: A Locally Recoverable Code is a code such that the value of any single coordinate of a codeword can be recovered from the values of a small subset of other coordinates. When we have $\delta$ non-overlapping subsets of cardinality $r_i$ that can be used to recover the missing coordinate we say that a linear code $\cC$ with length $n$, dimension $k$, minimum distance $d$ has $(r_1,\ldots, r_\delta)$-locality  and denote by $[n, k, d; r_1, r_2,\dots, r_\delta].$ In this talk, I will present a new upper bound for the minimum distance of these codes and propose a construction of $[n, k, d; r_1, r_2,\dots, r_\delta]$-codes on function fields of genus $g \geq 1$. This is joint work with Daniele Bartoli and Maria Montanucci. slides video.

Date/Time: June 10, 2020 12:00 Eastern (UTC -4:00)

Speaker: Lilya Budaghyan (University of Bergen)
Title: Optimal cryptographic functions over finite fields
Abstract: Functions over finite fields are used in cryptography, in particular in block ciphers. An important condition on these functions is a high resistance to the differential and linear cryptanalyses, which are among the main attacks on block ciphers. The functions which possess the best resistance to the differential attack are called almost perfect nonlinear (APN). Planar, bent and almost bent (AB) functions are those mappings which oppose an optimum resistance to both linear and differential attacks. An interesting fact is that planar, bent, APN and AB functions also define optimal objects in other domains of mathematics and information theory such as coding theory, finite geometry, sequence design, algebra, combinatorics, et al. In this talk we will discuss problems and recent advances in construction and analysis of these functions. slides

Date/Time: June 3, 2020 12:00 Eastern (UTC -4:00)

Speaker: Arne Winterhof (Austrian Academy of Sciences)
Title: On the distribution of the Rudin-Shapiro function for finite fields
Abstract: pdf, slides, video.

Date/Time: May 27, 2020 12:00 Eastern (UTC -4:00)

Speaker: Felice Manganiello (Clemson University)
Title: Graphs and Finite Fields in Modern Communication
Abstract: The origin of communication is based on the concept of two users exchanging information with each other over a single channel. The problem of perfect communication over a channel was modeled by Shannon in the late 40s. More modern communication networks are not so restrictive though. Most of the networks we use nowadays, connect multiple parties and graphs can be exploited to represent these networks. The question we are going to investigate in this seminar is simple: given a graph representing a network, what is its capacity, meaning how much information can be sent through it, and by which communication protocol over a finite field? This question has been already answered for unicast networks, meaning networks between a singe source and a single receiver, and for multicast networks, meaning networks used by a source to communicate simultaneously to multiple receivers. The capacity of communication for most networks with multiple sources is still an open question. Networks of this type are characterized by interference that is represented by the messages sent by undesired sources. A communication strategy has to be determined in order to remove the interference. We will focus our work on multiple unicast networks and look at the effectiveness of a practice known as interference alignment. We will define the concepts of linear capacity region of a network and discover that the points of this region are in relation with the solutions of a system of bilinear of equation. Solving such a system is know to be hard in general, so we will finally find the points of this region that are achievable by means of Gaussian elimination.
slides, video

Date/Time: May 20, 2020 12:00 Eastern (UTC -4:00)

Speaker: Francisco Rodriguez-Henriquez (CINVESTAV-IPN)
Title: Parallel Strategies for SIDH: towards computing SIDH twice as fast
Abstract: Over the last ten years there has been an intense research to find hard mathematical problems that would be presumably hard to solve by a quantum attacker and at the same time could be used to build reasonably efficient public-key cryptoschemes. One such proposal is the hardness of finding an isogeny map between two elliptic curves. This proposal has spawned a new line of research generally known as isogeny-based cryptography. One salient feature of all isogeny-based protocols proposed up-to-date is that they require exceptionally short key sizes. However, the latency associated to those protocols is higher than the ones reported by other post-quantum cryptosystem proposals. In this talk we present novel strategies and concrete algorithms for the parallel computation of the Supersingular Isogeny-based Diffie-Hellman key exchange (SIDH) protocol when executed on multi-core platforms. To our knowledge, the work presented here is the first reported multi-core implementation of SIDH.
slides, video