Carleton Finite Fields eSeminar - Summer 2020 Abstracts
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