The Polynomial Learning With Errors problem (PLWE) serves as the background of two of the four cryptosystems standardised in July 2022 by the National Institute of Standards and Technology to replace non-quantum resistant current primitives like those based on RSA, finite field based Diffie-Hellman and its elliptic curve analogue. Although PLWE is highly believed to be quantum resistant, unlike other post-quantum proposals like multivariate and some code based ones, this fact has not yet been established. Moreover, several vulnerabilities have been encountered for a number of specific instances. In a search for more flexibility, it becomes fully relevant to study the robustness of PLWE based on other polynomials, not necessarily cyclotomic. In 2015, Lauter et al. found a good number of attacks based on different features of the roots of the polynomial. In the present talk we present an overview of the approximations made against PLWE derived from these work, along with several new attacks which refine those by Lauter exploiting the order of the trace of roots over finite extensions of the finite field under the three scenarios laid out by Lauter et al, allowing to generalize the setting in which the attacks can be carried out. This is joint work with I. Blanco-Chacón and R. Durán.
A generalized polygon is a point-line incidence structure that includes projective planes (generalized 3-gons). Incidence graphs of generalized m-gons are connected bipartite graphs of diameter m and girth 2m. Associated to any group presentation is a graph called the star graph, which encodes structural information about the group defined by the presentation. Transitional behaviour can occur for groups defined by presentations whose star graph components are incidence graphs of generalized polygons; such presentations are called special. A cyclic presentation of a group is a type of group presentation that admits a cyclic symmetry. In this talk I will discuss joint work with Ihechukwu Chinyere in which we classify the special cyclic presentations.
The Learning with Errors (LWE) problem w.r.t. a matrix B asks to recover the secret-error tuple (s,e) given the sample c = sB+e mod q. In typical settings, e.g. when B mod q is uniformly random, the solution (s,e) is uniquely determined by (B,c). In lattice terminology, this is due to the non-existence of short vectors in the lattice spanned by the rows of B modulo q. We propose the notion of "primal lattice trapdoors", a suit of algorithms which generates a matrix B together with a trapdoor, such that the lattice of B contains hidden exceptionally short vectors, allowing LWE samples w.r.t. B to admit multiple solutions, whereas the trapdoor allows to sample from the solution space. We provide a construction and prove that it satisfies a set of desirable properties, either unconditionally or computationally based on the NTRU assumption. Leveraging our tool, we construct a lattice-based indistinguishability obfuscator, a powerful cryptographic primitive known to imply most in cryptography.
Advisors: Okko Makkonen and Serge Kas Hanna
Strassen's asymptotic rank conjecture [Progr. Math. 120 (1994)] claims a strong submultiplicative upper bound on the rank of a three-tensor obtained as an iterated Kronecker product of a constant-size base tensor. The conjecture, if true, most notably would put square matrix multiplication in quadratic time. We note here that some more-or-less unexpected algorithmic results in the area of exponential-time algorithms would also follow. Specifically, we study the so-called set cover conjecture, which states that for any ε>0 there exists a positive integer constant k such that no algorithm solves the k-Set Cover problem in worst-case time O((2-ε)^n|F|poly(n)). The k-Set Cover problem asks, given as input an n-element universe U, a family F of size-at-most-k subsets of U, and a positive integer t, whether there is a subfamily of at most t sets in F whose union is U. The conjecture was formulated by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh in the monograph Parameterized Algorithms [Springer, 2015], but was implicit as a hypothesis already in Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, and Wahlström [CCC 2012, TALG 2016], there conjectured to follow from the Strong Exponential Time Hypothesis. We prove that if the asymptotic rank conjecture is true, then the set cover conjecture is false. Using a reduction by Krauthgamer and Trabelsi [STACS 2019], in this scenario we would also get an O((2-δ)^n)-time randomized algorithm for some constant δ>0 for another well-studied problem for which no such algorithm is known, namely that of deciding whether a given -vertex directed graph has a Hamiltonian cycle. This is joint work with Andreas Björklund (ITU Copenhagen).
Advisor Tapani Matala-aho.
Lattices, that is, discrete subgroups of Euclidean space, are a fundamental object in mathematics with connections to Lie Group Theory, Cryptography, and Algebraic Number Theory. The sphere-packing density of a lattice roughly measures how efficiently its points are packed into Euclidean space. The search for the optimal lattice packing in n-dimensional space is a long-standing problem, with known solutions only for certain small n. On the other hand, certain lattices arising naturally from Algebraic Number Theory have natural properties that make them especially suitable for applications in communications. In this talk, we will discuss an apparently new class of lattices, which we deem R_n-lattices, whose properties attempt to capture those coming from Number Theoretic lattices while also yielding efficient sphere packing. Falling into this class of lattices are unit lattices coming from totally real Galois number fields, and we apply our results to understand the sphere-packing densities of some well-known classes of unit lattices. This is joint work with Jose Cruz of the University of Calgary.
There is a direct connection between linear codes over fields and matroids, commonly referred to as representable matroids. Specifically, a generator matrix for a linear code over a field not only serves as a coding tool but also as a representation for a representable matroid. Exploiting this connection, matroid theory has proven important in establishing numerous results in information theory, for example, in the areas of distributed storage, field linear codes with Hamming weights, network coding, index coding, and caching. Representable matroids also constitute an intriguing class in their own right, with connections to various areas within mathematics. In this talk, I will present a generalization of matroids and how this generalization can be associated with modules. I will also illustrate how this connection can be used to establish results in information theory, especially in scenarios where algebraic structures other than vector spaces are considered.
Opponent Prof. Alberto Ravagnani (Eindhoven), Custos Camilla Hollanti
For a number field K, its class group measures the extent that unique factorisation fails in the ring of integers of K. When K is an imaginary quadratic field such that unique factorisation fails miserably, its class group turns out to exhibit nice properties which are found useful in cryptographic constructions. In this short talk, I will briefly recall some background on class groups, focused on the case of imaginary quadratic fields, and highlight some reasons for their uses in cryptography. For example, assuming certain computational problems are hard over class groups, we shall see that class groups imply encryption schemes that are more space-efficient than the well-known RSA encryption, and there exist cryptographic primitives with desirable properties that are, as of today, only known to be achievable from class groups.
In this talk, I will give an introduction to my PhD project, which focuses on privacy-preserving techniques. As technology enables more powerful collection and curation of data, it has become a relevant need to assure the privacy of individuals and their associated data. An information-theoretic approach offers unconditional privacy guarantees without relying on the hardness of certain computational problems, i.e., the system cannot be broken even if the adversary has unlimited computing power. There are a variety of security tasks for which information-theoretic security is a meaningful and useful requirement, such as secret sharing, secure multiparty computation, and private information retrieval. For instance, against side-channel attacks on systems and hardware, to protect one single crucial value (like a byte of a key), one of the most common, not hardware, countermeasures is masking, which applies a secret sharing scheme to expand this single value into a set of several random values. This forces an attacker to target all these random values (instead of a single value) to extract any meaningful secret information, making the attack more difficult. This presentation, focusing on privacy-preserving techniques with information-theoretic approaches (i.e. secret sharing schemes), gives insights over the planned research during my PhD project. In this project, the results of Venkatesan Guruswami and Mary Wootters, which show that Reed-Solomon codes with evaluation points in the whole (finite) field, a failed evaluation point can be recovered using information from the remaining functional nodes. Due to the close connection between RS-code and Shamirs secret-sharing scheme vulnerabilities with respect to leakage can be concluded, which set the starting point for the doctoral research project. For instance, if a smaller, incomplete, amount of information is obtained by the adversary from each share (instead of the whole share) the secret can still be recovered. Finally, one of the major goals within the doctoral project is to find the minimal amount of leakage that can be tolerated while preserving the secrecy.
Some of the main methods for deciding whether or not a difference set of given parameters exists are the self-conjugacy test developed by Turyn in 1965, the field descent and its variations developed by Schmidt et al. in late 1990's, and importantly, the multiplier theorems by Hall, which date back to 1950's. All of these methods are based on knowledge about the decomposition groups in certain cyclotomic fields. In this talk I show that the multiplier groups of cyclic groups G, where v=|G| is non-squarefree, cannot contain a large set of residues. Together with a small "multiplier lemma" this gives a new existence test that can be used to rule out cyclic difference sets.
Given a lattice L, an extension of L is a lattice M of strictly greater rank such that the intersection of M and the subspace spanned by L is equal to L. In this talk we will discuss constructions of such lattice extensions where particular geometric invariants of M, such as the determinant, covering radius and successive minima, are related the corresponding geometric invariants of L. This talk is based on joint work with Lenny Fukshansky. Zoom: https://aalto.zoom.us/j/62956597693
I will discuss some recent work, joint with Alon Nishry and Brad Rodgers, concerning the distribution of Dirichlet and trigonometric polynomials generated by multiplicative coefficients f(n). In the first part of the talk we will explore some old and new results for deterministic sequences f(n) (Möbius, Legendre symbol,...), stopping along our journey to marvel at a variety of wild and thorny conjectures. The second half of the talk will be devoted to Steinhaus random multiplicative coefficients f(n) = X(n). These considerations give rise to a couple of intriguing arithmetic problems.
Advisors: Wilmar Bolanos, Visa Vallivaara
A Private Information Retrieval (PIR) scheme allows users to retrieve data from a database without disclosing to the server information about the identity of the data retrieved. A single-server PIR scheme is based on computational privacy and assumes computers have limited power. Therefore, it requires computational difficulty. When a system consists of a single server, it is possible to achieve information-theoretic privacy by transmitting the entire database. However, this approach is not feasible. The first computational PIR scheme based on coding theory is presented [2020 IEEE International Symposium on Information Theory (ISIT), pp. 10651070 (2020] by Holzbaur, Hollanti, and Wachter-Zeh. However, Bordage and Lavauzelle presented an attack that occurs in polynomial time and with high probability [Cryptogr. Commun. 13, 519526 (2020)]. We present a single-server PIR scheme using codes over rings that utilize the coding theory perspective of Holzbaur, Hollanti, and Wachter-Zeh, which provides resistance against the attack described in [Cryptogr. Commun. 13, 519526 (2020)]. This talk is based on a joint work with Edgar Martínez-Moro and Diego Ruano.
Universal quadratic forms generalize the sum of four squares about which it is well known that it represents all positive rational integers. In the talk, I'll start by discussing some results on universal quadratic forms over totally real number fields. Then I'll move on to the - markedly different! - situation over infinite degree extensions K of Q. In particular, I'll show that if K doesn't have many small elements (i.e., "K has the Northcott property"), then it admits no universal form. The talk should be broadly accessible, and is based on a very recent joint work with Nicolas Daans and Siu Hang Man.
MSc thesis presentation (advisor Jukka Suomela, CS)
This talk is a brief introduction to the Post-Quantum Cryptography (PQC) standardization process and its two current competitions. Within this setting, the notion of Key Encapsulation Mechanism (KEM) is critical to the development of key establishment on PQC, as an alternative to traditional key establishment mechanisms. We will focus on PQC protocols based on this concept over unauthenticated channels. A number of KEM-based protocols between two parties are proposed, and their resistance over unauthenticated channels is studied. This means analyzing the security of the protocol itself, and its robustness against Man-in-the-Middle attacks. A comparison with their KEX-based counterparts is made in terms of the protocol itself and the types of attacks they are subject to. Finally, a number of go-to KEM-based protocol instances to migrate to, based on the conditions of currently-in-use KEX-based protocols, are proposed.
We introduce the first candidate lattice-based Designated Verifier (DV) ZK-SNARK protocol with \emph{quasi-optimal proof length} (quasi-linear in the security/privacy parameter), avoiding the use of the exponential smudging technique. Our ZK-SNARK also achieves significant improvements in proof length in practice, with proofs length below KB for 128-bit security/privacy level. Our main technical result is a new regularity theorem for `private' re-randomization of Module LWE (MLWE) samples using discrete Gaussian randomization vectors, also known as a lattice-based leftover hash lemma with leakage, which applies with a discrete Gaussian re-randomization parameter that is polynomial in the statistical privacy parameter. To obtain this result, we obtain bounds on the smoothing parameter of an intersection of a random -ary SIS module lattice, Gadget SIS module lattice, and Gaussian orthogonal module lattice over standard power of 2 cyclotomic rings, and a bound on the minimum of module gadget lattices. We then introduce a new candidate \emph{linear-only} homomorphic encryption scheme called Module Half-GSW (HGSW), which is a variant of the GSW somewhat homomorphic encryption scheme over modules, and apply our regularity theorem to provide smudging-free circuit-private homomorphic linear operations for Module HGSW. The talk is based on https://eprint.iacr.org/2022/1690.
During the years of the COVID19 pandemic my collaborators and I have tried to revisit and possibly remodel the discipline of group testing in such a way, that it can be seen as a finite linear algebra over the binary semifield. Residuation Theory as presented in a textbook by T. S. Blyth and M. F. Janowitz plays a prominent role in our account on this topic, and we will also attempt to address the error-prone part. The presentation will be complemented by a number of examples.
In this talk we will discuss some of the benefits and shortcomings of using Homomorphic Encryption (HE) for two very different types of practical applications. Firstly, we will talk about Federated Learning, and how to tailor HE for the efficient execution of secure average aggregation. In the last part of the talk, we will modify current HE schemes with the objective of better dealing with privacy-sensitive multidimensional signals (e.g., images). In particular, we will explore the possibility of substituting the more conventional power-of-two cyclotomic rings for different types of multivariate rings.
We introduce and study Diophantine equation (n+1)x^2-ny^2 = 1. It resembles the more complicated Lagrange's theory of Pell's equation x^2-ny^2=1. Positive n \in Z is called P-smooth if its prime factors belong to a subset P of the primes. In tonal music, the melodic intervals n: (n+1) are nearly always {2,3,5,7}-smooth. In 1897, Størmer used Pell's equation to find the P-smooth pairs (n,n+1). We give a simple well-motivated method for Størmer's problem.
In this talk we first recall the notion of arboreal Galois representation and then we develop a method to effectively determine the set of primes p for which certain arboreal Galois representations are surjective modulo p. Our method is based on a combination of height bounds on integral points on elliptic curves over function fields in positive characteristic and the ABC theorem for function fields. Using this technique we prove Jones' conjecture on the surjectivity of the arboreal Galois representation attached to f=x^2+t [Conjecture 6.7, Compositio Math. 43 (5) (2007)]. This is a joint work with Andrea Ferraguti.
DNA storage is a promising candidate for next-generation storage systems due to its compactness, high durability, and energy efficiency. However, the process of storing digital data in synthetic DNA suffers from deletion and insertion errors that may affect the sequence of nucleotides during synthesis, sequencing, and storage. The reliability of the DNA storage can be improved by integrating codes that correct deletions and insertions within the storage system. This talk will give a general overview of deletion/insertion correcting codes and discuss the specific encoding and decoding constraints imposed by the technologies used in DNA storage systems.
The following conjecture was made in the 2016 Ireland BT Young Scientist Competition: every prime number q>3 can be expressed as q=p+n(n+1), with p a twin prime and n>0. This conjecture was satisfactorily tested for the first 100 millions of primes, and puzzled by such phenomenon, Gary McGuire asked me to think about a possible proof (or disproof) of the conjecture. The first result I came across is the proof that the validity of the conjecture would easily yield the existence of infinitely many twin primes. The conjecture remains open, but we proved that for each prime q of a set of primes of density 1, can be written as q=p+n(n+1), with p < q also prime (not necessarily twin), which is a weak version of a conjecture by Sun. In the present talk we give a sketch of this proof.
In this talk we will explore some recent results in Secure Distributed Computation, in which a user distributes a computational task across several worker nodes while protecting sensitive aspects of the computation from potential adversaries with access to the worker nodes. This presentation will focus on the case of matrix multiplication, but we will discuss generalizations with potential applications to decentralized machine learning. Many of our results represent joint work with Razan Tajeddine.
Nonlinear dynamical systems pose a significant challenge when it comes to controlling them. The challenge raises to another level if we require fault tolerance. In this talk, I introduce Byzantine fault tolerance (BFT) protocols that aim at resiliency by guaranteeing consistency. I will discuss the essential combinatorial geometry behind BFT, which it shares with seemingly distant areas in math, such as Cantor's work on cardinality of reals and Turing's Halting problem. Finally, if time permits (i.e., when the eyes start rolling), I will discuss how the Diagonal Argument (from category theory) provides a unifying framework to discuss all. I assume no prior knowledge of these subjects and will try to introduce and discuss the basics.
Informally, a real number is normal in base b if in its b-ary expansion all digits and blocks of digits occur as often as one would expect them to uniformly at random. Borel introduced normal numbers in 1909 and proved that Lebesgue-almost every real number is normal in all bases b \geq 2. Even though this shows that, in some sense, normal numbers are "typical," no example of a number normal in all bases was given until 1939 by Turing. In the last 100 years, the study of normal numbers has spread over a wide breadth of seemingly unrelated disciplines. Normality is closely related to number theory, ergodic theory, theoretical computer science, probability theory, fractal geometry, descriptive set theory, and others areas of math. We will explore the basic properties of normal numbers and surprising connections they have, depending on the interest of the audience.
Graphs can be used as a diagrammatic representation of entangled states: vertices represent qubits, and edges are the entangling gates performed between the qubits. Arbitrary quantum circuits can be compiled into a fault-tolerant gate set, and the resulting circuit can be reformulated as a graph state. Such graphs can be manipulated by local operations (single qubit/vertex gates) such that edges are added and removed in a well defined manner during a process called local complementation. The latter might have interesting applications for the optimisation of (fault-tolerant) quantum circuits, quantum communication networks and in general whenever, either: a) there is a need to minimize the number of edges (entangling gates) without affecting the functionality of the state, or b) the state has to be embedded into a quantum hardware architecture that has a different connectivity. This talk is partially based on the work from https://arxiv.org/abs/2209.07345
For a given number field K, the integral trace form of K is the quadratic form defined by the trace operator Tr_K/Q(x^2) over the ring of integers of K. In the mid 80's Conner and Perlis showed that for cyclic number fields of prime degree p the isometry class of integral trace is completely determined by the discriminant. The main objective of this talk is to discuss the principal aspects of Conner and Perlis' work and a completed generalization for tame cyclic number fields of arbitrary degree. Furthermore, for such fields, we give an explicit description of a Gram matrix of the integral trace in terms of the discriminant of the field.
Private information retrieval (PIR) addresses the question of how to retrieve data items from a database or cloud without disclosing information about the identity of the data items retrieved. The area has received renewed attention in the context of PIR from coded storage. Here, the files are distributed over the servers according to a storage code instead of mere replication. Alongside with the basic principles of PIR, we will review recent capacity results and demonstrate the usefulness of the so-called star product PIR scheme. The talk is based on joint work with Ragnar Freij-Hollanti, Oliver Gnilke, Lukas Holzbaur, David Karpuk, and Jie Li.
The complexity of matrix multiplication represents the number of operations needed to compute a matrix product in the asymptotic limit. The first advance in asymptotic complexity was made in 1969 when Strassen introduced an algorithm that is capable of computing the product of two N × N matrices with O(N^{2.81}) operations, which is better than the naive algorithm that takes O(N^3) operations. The current record is an algorithm that is able to compute the product using just O(N^{2.372}) operations. We present the basic tools that are used to analyze this problem and present an algorithm that is even better than the Strassen algorithm. This includes studying the matrix multiplication tensor, its rank, and the so-called border rank.
Distributed learning (DL) is a machine learning (ML) setting where several parties (e.g., mobile devices or computer clusters) collaboratively train an ML model under the orchestration of a central entity. DL can be applied in the case where the data is centralized, i.e., owned by a single entity, and also when the data is decentralized, i.e., owned by several parties. In the centralized data setting, DL is attractive when the data is too large for one entity to process by itself. Here, a central entity can make the learning process tractable by distributing the data across several helper nodes and outsourcing part of the computations. The DL setting can also present itself naturally when the training data is owned by several decentralized parties. Federated learning (FL) is a branch of DL where the data is decentralized and owned by several independent parties who agree to collaboratively train an ML model but want to maintain the privacy of their local data. In addition to privacy, communication efficiency is also a first-order concern in FL, especially when the data is owned by several mobile devices operating over a network. In this talk, I will introduce distributed learning and federated learning and discuss some of the challenges associated with such distributed systems. I will also explain how basic optimization algorithms, such as gradient descent, can be applied to distributed learning and adapted to the setting of federated learning.
Take your favorite real or p-adic number, say Phi. Let us assume there exist nice rational approximations for your number. Then these approximations will be written as numerical linear forms. We will give a criterion for the irrationality of your number by using a sequence of these numerical linear forms. Moreover, a lower bound is given for the quantity N*Phi-M, where N, M are integers and N is nonzero. However, it is a challenge to find an appropriate sequence of numerical linear forms for an arbitrary number. In this lecture we will not consider this problem. But we note, if your number is a value of a Taylor series or a (generalized) continued fraction, then we may build a candidate sequence from the truncated series or Padé approximations or use the convergents of the continued fraction.
Let M be an arbitrary matroid. In the 70's, Gian-Carlo Rota and Henry Crapo asked for a natural definition of a matroid dM that has as its ground set the collection of (co)circuits of M. We will first survey two earlier such constructions, namely the Exley-Wang derived matroid, and (co)-adjoint lattices. These constructions have several nice properties, but are only defined for certain special classes of matroids, and are not necessarily unique. We will then introduce a recent construction by the speaker, called combinatorial derived matroids. These are uniquely defined for any matroid M, but computing them has proven an elusive task. We will give all the definitions, compute some illuminating examples, and offer a few conjectures. This is joint work with Relinde Jurrius and Olga Kuznetsova.
In combinatorics, a q-analog of a discrete structure is defined by replacing finite sets with finite dimensional vector spaces. On the other hand, matroids are defined as a combinatorial abstraction of several objects such as linearly independent vectors or graphs. In this talk, we first define a matroid with certain equivalent axiomatic definitions by supporting them with examples. Then we discuss their q-analogs by comparing differences and similarities with the classical case. Finally, as a construction and an application of a q-matroid, we mention their relation with a q-analog of other combinatorial objects called designs, and state some open questions. This work is a part of the research project supported by Women in Numbers - Europe.
This talk will be about the representation of integers by quadratic forms. We will survey what is known about the quadratic forms that represent all eligible integers of totally real number fields. It will include the recent results, from the joint work with Vitezslav Kala, Dayoon Park, and Blazej Zmija, on the density of real quadratic number fields that have a universal quadratic form with a fixed number of variables.
Page content by: webmaster-math [at] list [dot] aalto [dot] fi