BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Buket Özkaya (Nanyang Technological University (Singapore))
DTSTART;VALUE=DATE-TIME:20200506T070000Z
DTEND;VALUE=DATE-TIME:20200506T080000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/1
DESCRIPTION:Title: Good Stabilizer Codes from Quasi-Cyclic Codes\nby Buket Özkaya
(Nanyang Technological University (Singapore)) as part of University of Z
urich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nLison
ek and Singh proposed an interesting modification to the construction of q
ubit stabilizer codes by relaxing the Hermitian self-orthogonality require
ment. Their framework\, inspired by Construction X in the classical setup\
, yielded a number of better qubit codes than the previous best-known. The
se better codes came from applying their construction to specifically chos
en quaternary cyclic codes. Construction X for qubit codes generalizes nat
urally to q-ary quantum codes.\nThis work uses self-orthogonal or nearly s
elf-orthogonal quasi-cyclic codes over F4 and F9 as ingredients in the qua
ntum Construction X to derive good qubit and qutrit (3-ary quantum) codes.
We consider quasi-cyclic codes with large Hermitian hulls\, which can be
easily produced using their Chinese Remainder Theorem decomposition. Such
codes have a good chance to be implemented in actual quantum processors. W
e exhibit quantum codes with parameters that strictly improve on the curre
ntly best-known ones and list those that match the best-known ones in perf
ormance.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Madhu Sudan (Harvard University (Cambridge\, Massachusetts))
DTSTART;VALUE=DATE-TIME:20200506T130000Z
DTEND;VALUE=DATE-TIME:20200506T140000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/2
DESCRIPTION:Title: Codes for correcting editing errors\nby Madhu Sudan (Harvard Un
iversity (Cambridge\, Massachusetts)) as part of University of Zurich (joi
nt with Neuchatel) applied algebra seminars\n\n\nAbstract\nThe "edit dista
nce''\, also known as the Levenstein distance\, between two strings X\, Y
over some alphabet Sigma\, is the minimum number of insertions and deletio
ns in X that will transform it to Y. For example if X = 010101010101 and Y
= 101010101010\, then their Hamming distance is 12 while the edit distanc
e is 2 - since you can delete the first 0 in X and insert a 0 in the last
position to get Y. In this talk we will consider the task of correcting ed
iting errors\, i.e.\, the task of recovering X\, given a string Y obtained
from the transmission of X followed by a "few" editing errors.\nCoding th
eory has traditionally focussed mostly on correcting Hamming errors and ti
ll recently the theory of coding for editing errors was far behind. A rece
nt series of works by Haeupler and Shaharasbi (with varying sets of author
s) has completely transformed this picture\, and brought us to the stage w
here the results subsume what we know for the Hamming setting\, at least f
or large constant sized alphabets! (Of course the proofs also use the stat
e of the art results in the Hamming setting to get there.)\nIn this talk\,
I will use a recent theorem (from a paper with Haeupler and Shahrasbi) as
an excuse to talk about these developments. Our theorem shows that for ev
ery delta < 1\, gamma < infinity and epsilon > 0\, there is an constant q
and an infinite family of q-ary codes of rate 1 - delta - epsilon which ca
n be list decoded in polynomial time from delta fraction deletions and gam
ma "fraction" insertions. (Note that gamma\, the fraction of insertions ca
n be much larger than 1!) Depending on availability of time we will speak
about the two main ingredients in this result: (1) The corresponding resul
t in the Hamming setting (where we allow delta fraction deletions\, but on
ly allow same number of insertions in the same locations) which comes from
the Folded-Reed-Solomon-Codes of Guruswami and Rudra and the many followu
ps. (2) Synchronization strings\, which are magical ingredients introduced
by Haeupler and Shahrasbi that convert codes for Hamming settings into co
des for editing errors.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/2/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Kristin Lauter (Microsoft Research (Redmond\, Washington))
DTSTART;VALUE=DATE-TIME:20200513T180000Z
DTEND;VALUE=DATE-TIME:20200513T190000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/3
DESCRIPTION:Title: Supersingular Isogeny Graphs in Cryptography\nby Kristin Lauter
(Microsoft Research (Redmond\, Washington)) as part of University of Zuri
ch (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nAs we mo
ve towards a world which includes quantum computers which exist at scale\,
we are forced to consider the question of what hard problems in mathemati
cs our next generation of cryptographic systems will be based on. Supersi
ngular Isogeny Graphs were proposed for use in cryptography in 2006 by Cha
rles\, Goren\, and Lauter. Supersingular Isogeny Graphs are examples of R
amanujan graphs\, which are optimal expander graphs. These graphs have th
e property that relatively short walks on the graph approximate the unifor
m distribution\, and for this reason\, walks on expander graphs are often
used as a good source of randomness in computer science. But the reason t
hese graphs are important for cryptography is that finding paths in these
graphs\, i.e. routing\, is hard: there are no known subexponential algorit
hms to solve this problem\, either classically or on a quantum computer.
For this reason\, cryptosystems based on the hardness of problems on Super
singular Isogeny Graphs are currently under consideration for standardizat
ion in the NIST Post-Quantum Cryptography (PQC) Competition. This talk wi
ll introduce these graphs\, the cryptographic applications\, and the vario
us algorithmic approaches which have been tried to attack these systems.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/3/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Gretchen Mathews (Virginia Tech (Blacksburg\, VA))
DTSTART;VALUE=DATE-TIME:20200527T140000Z
DTEND;VALUE=DATE-TIME:20200527T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/4
DESCRIPTION:Title: Coding for local recovery\nby Gretchen Mathews (Virginia Tech (
Blacksburg\, VA)) as part of University of Zurich (joint with Neuchatel) a
pplied algebra seminars\n\n\nAbstract\nCodes with locality are designed to
recover erased symbols by accessing only a few others. Such codes are use
ful in settings such as distributed storage where servers may routinely go
offline for maintenance but users still need to access their information.
This situation suggests that it is also desirable to have a variety of wa
ys in which to recover a single symbol\, leading to the concept of availab
ility. In this talk\, we share recent work on codes from curves which prov
ide locality and availability.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/4/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Daniel Cabarcas Jaramillo (Universidad Nacional de Colombia (Bogot
a\, Kolumbien))
DTSTART;VALUE=DATE-TIME:20200603T140000Z
DTEND;VALUE=DATE-TIME:20200603T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/6
DESCRIPTION:Title: From Minrank Attack to generic Bilinear\nby Daniel Cabarcas Jar
amillo (Universidad Nacional de Colombia (Bogota\, Kolumbien)) as part of
University of Zurich (joint with Neuchatel) applied algebra seminars\n\n\n
Abstract\nThe Minrank (MR) problem is a computational problem closely rela
ted to attacks on code- and multivariate-based schemes. MR can be reduced
to a bilinear system of polynomial equations. In the quest to better estim
ate the complexity of this approach\, we developed a more general theory f
or generic bilinear systems. In this presentation\, we show some of the la
test results for the complexity of MR and then\, we present some general r
esults about bilinear systems.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/6/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Antonia Wachter-Zeh (TU Munich (Munich))
DTSTART;VALUE=DATE-TIME:20200617T130000Z
DTEND;VALUE=DATE-TIME:20200617T140000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/7
DESCRIPTION:Title: LIGA: A cryptosystem based on the hardness of rank-metric list and
interleaved decoding.\nby Antonia Wachter-Zeh (TU Munich (Munich)) as
part of University of Zurich (joint with Neuchatel) applied algebra semina
rs\n\n\nAbstract\nWe propose the new rank-metric code-based cryptosystem L
IGA which is based on the hardness of list decoding and interleaved decodi
ng of Gabidulin codes. LIGA is an improved variant of the Faure-Loidreau (
FL) system\, which was broken in a structural attack by Gaborit\, Otmani\,
and Talé Kalachi (GOT\, 2018). We keep the FL encryption and decryption
algorithms\, but modify the insecure key generation algorithm. Our crucial
observation is that the GOT attack is equivalent to decoding an interleav
ed Gabidulin code. The new key generation algorithm constructs public keys
for which all polynomial-time interleaved decoders fail---hence LIGA resi
sts the GOT attack. We also prove that the public-key encryption version o
f LIGA is IND-CPA secure in the standard model and the KEM version is IND-
CCA2 secure in the random oracle model\, both under hardness assumptions o
f formally defined problems related to list decoding and interleaved decod
ing of Gabidulin codes. We propose and analyze various exponential-time at
tacks on these problems\, calculate their work factors\, and compare the r
esulting parameters to NIST proposals. The strengths of LIGA are short cip
hertext sizes and (relatively) small key sizes. Further\, LIGA guarantees
correct decryption and has no decryption failure rate. It is not based on
hiding the structure of a code. Since there are efficient and constant-tim
e algorithms for encoding and decoding Gabidulin codes\, timing attacks on
the encryption and decryption algorithms can be easily prevented.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/7/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Luca De Feo (IBM Research Zürich (Zürich))
DTSTART;VALUE=DATE-TIME:20200429T140000Z
DTEND;VALUE=DATE-TIME:20200429T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/8
DESCRIPTION:Title: Faster Evaluation of Isogenies of Large Prime Degree\nby Luca D
e Feo (IBM Research Zürich (Zürich)) as part of University of Zurich (jo
int with Neuchatel) applied algebra seminars\n\n\nAbstract\nAn isogeny is
a non-zero morphism of elliptic curves. The isogeny evaluation problem ask
s\, given a description of an isogeny φ:E→E' and of a point P∈E\, to
compute φ(P). It is a fundamental algorithmic problem in computational nu
mber theory and has gained a fair amount of interest thanks to the recent
developments in isogeny-based cryptography.\nThe "atomic" case for isogeny
evaluation is that of isogenies of prime degree\, on top of which algorit
hms for isogenies of any degree are easily constructed. For the prime degr
ee case\, the classic solution is based on Vélu's formulas or any of thei
r optimized variants. Vélu's formulas take as input the kernel of the iso
geny\, e.g.\, as a list of points\, and output the isogeny as a pair of ra
tional functions\, which are then used to evaluate the isogeny at the poin
t. This algorithm can be implemented in time linear in the isogeny degree\
, which is asymptotically optimal in general\; however in the fundamental
case where the kernel can be described by a single generator over the base
field\, one could hope to find a more efficient algorithm which sidesteps
the computation of the rational functions.\nThis is exactly what I will p
resent in this talk: starting from a very simple idea\, already used by Po
llard\, Strassen\, and Chudnovsky²\, among others\, I will present a baby
-step/giant-step algorithm that solves the isogeny evaluation problem in t
ime and space proportional to the square root of the degree. I will explai
n why this is important for isogeny-based cryptography\, and highlight sev
eral applications where the new algorithm produces practical speedups rang
ing from the unimpressive to the spectacular.\nThis is joint work with D.J
. Bernstein\, A. Leroux and B. Smith\, the preprint can be found at https:
//ia.cr/2020/341.\n(**This talk will be live streamed at https://defeo.lu/
tube/**)\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/8/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Markus Grassl (International Centre for Theory of Quantum Technolo
gies)
DTSTART;VALUE=DATE-TIME:20200610T140000Z
DTEND;VALUE=DATE-TIME:20200610T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/9
DESCRIPTION:Title: On Quantum MDS Codes\nby Markus Grassl (International Centre fo
r Theory of Quantum Technologies) as part of University of Zurich (joint w
ith Neuchatel) applied algebra seminars\n\n\nAbstract\nA quantum error-cor
recting code (QECC)\, denoted by ((n\,K\,d))q\, is a K-dimensional subspac
e of the complex vector space Cq⊗n that is able to correct up do d-1 era
sures. A quantum MDS (QMDS) code is a code of maximal possible dimension m
eeting the quantum Singleton bound logqK ≤ n+2-2d. Most known QMDS codes
are based on Hermitian self-orthogonal classical MDS codes. It has recent
ly been shown [3] that regardless of the underlying construction\, QMDS co
des share many (but not all) properties with their classical counterparts.
The QMDS conjecture states that the length of nontrivial codes is bounded
by q2+1 (or q2+2 in special cases). While QMDS codes of maximal length ar
e known for many cases\, it appears to be difficult to find codes of dista
nce d > q+1 (see [1\,2]).\nThe talk addresses the question of finding QMDS
codes in general and presents a couple of related open questions in algeb
raic coding theory.\n\n[1] Ball\, Simeon\, "Some constructions of quantum
MDS codes''\, preprint arXiv:1907.04391\, (2019).\n[2] Grassl\, Markus and
Roetteler\, Martin\, "Quantum MDS Codes over Small Fields''\, Proceedings
2015 IEEE International Symposium on Information Theory (ISIT 2015)\, pp.
1104--1108\, (2015). DOI: 10.1109/ISIT.2015.7282626\, preprint arXiv:1502
.05267.\n[3] Huber\, Felix and Grassl\, Markus\, "Quantum Codes of Maximal
Distance and Highly Entangled Subspaces''\, preprint arXiv:1907.07733\, (
2019).\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/9/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alain Couvreur (Ecole polytechnique (Palaiseau\, France))
DTSTART;VALUE=DATE-TIME:20200520T130000Z
DTEND;VALUE=DATE-TIME:20200520T140000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/10
DESCRIPTION:Title: On the code equivalence problem in rank metric\nby Alain Couvr
eur (Ecole polytechnique (Palaiseau\, France)) as part of University of Zu
rich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nThe co
de equivalence problem can roughly be stated as follows : "Given two codes
\\(C_1\\)\, \\(C_2\\)\, is there an isometry \\(\\phi\\) of the ambient s
pace such that \\(\\phi(C_1) = C_2\\)?" In Hamming metric\, this problem h
as been intensively studied in the last decades\, with in particular the {
\\it support splitting algorithm} by N. Sendrier which solves this problem
in the generic case when the isometry \\(\\phi\\) is a permutation. On th
e rank metric side\, the linear isometries of the ambient space are classi
fied and various algebraic invariants related to a given matrix space have
been identified. In this talk\, we will focus on the algorithmic aspects
of the code equivalence problem in rank metric by focusing on three versio
ns: 1. \\(\\mathbb{F}_{q^m}\\)--linear codes with a vector representation
2. \\(\\mathbb{F}_{q^m}\\)--linear codes with a matrix representation 3. N
on structured matrix spaces. We propose efficient algorithms to solve vers
ions (1) and (2) of the problem. Then we prove that (3) is at least as har
d as the monomial equivalence problem in Hamming metric. This is a work in
progress in collaboration with Thomas Debris-Alazard (Royal Holloway\, Lo
ndon) and Philippe Gaborit (University of Limoges).\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/10/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alfred Wassermann (University of Bayreuth (Bayreuth\, Germany))
DTSTART;VALUE=DATE-TIME:20200701T140000Z
DTEND;VALUE=DATE-TIME:20200701T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/11
DESCRIPTION:Title: Designs\, subspace designs and their codes\nby Alfred Wasserma
nn (University of Bayreuth (Bayreuth\, Germany)) as part of University of
Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nIn t
his talk\, we give an overview of combinatorial designs\, their q-analogue
s and related structures. Design theory has a venerable history starting i
n the 1830s. The connection between combinatorial designs and linear error
correcting codes is well studied. In recent years\, subspace designs - al
so called q-analogues of designs - regained interest because of their appl
ication as subspace codes in random network coding\, which led to many new
results on structural properties of the subspace designs. Moreover\, it t
urns out that also the linear codes spanned by the rows of the incidence m
atrix of subspace designs are interesting. Another important class of subs
paces codes is lifted MRD codes. Surprisingly\, lifted MRD codes can be re
garded as transversal designs and the resulting linear codes can be studie
d\, too. These codes may be useful as so called PIR codes for private info
rmation retrieval.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/11/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Daniel Panario (Carleton University)
DTSTART;VALUE=DATE-TIME:20200729T140000Z
DTEND;VALUE=DATE-TIME:20200729T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/13
DESCRIPTION:Title: Analytic and Probabilistic Combinatorics for Polynomials over Fini
te Fields\nby Daniel Panario (Carleton University) as part of Universi
ty of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract
\nThe central objects of this talk are univariate polynomials over finite
fields. We survey methods and results to count polynomials satisfying cert
ain properties\, and to understand their random behaviour.\nWe first comme
nt on a methodology from analytic combinatorics that allows the study of t
he decomposition of polynomials into irreducible factors\, the derivation
of algorithmic properties\, and the estimation of average-case analysis of
algorithms. This methodology can be naturally used to provide precise inf
ormation on the factorization of polynomials into its irreducible factors
similar to the classical problem of the decomposition of integers into pri
mes. Examples of these results are provided. The shape of a random univari
ate polynomial over a finite field is also given. As an example of the met
hodology\, periodicity properties of the iterations of random polynomials
over finite fields\, related to Pollard rho method\, are commented.\nThen\
, if time allows\, we briefly show several results for random polynomials
over finite fields that were obtained using other methodologies based on p
robabilistic combinatorics. We conclude providing open problems for polyno
mials over finite fields related to number theory.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/13/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Marc Newman (Master thesis defense)
DTSTART;VALUE=DATE-TIME:20200826T130000Z
DTEND;VALUE=DATE-TIME:20200826T140000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/17
DESCRIPTION:Title: A Study of Mathematical and Practical Aspects of SIDH and CSIDH\nby Marc Newman (Master thesis defense) as part of University of Zurich
(joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nIn this the
sis\, we consider two different supersingular isogeny-based Diffie-Hellman
schemes: SIDH and CSIDH. We review the fundamental definitions underpinni
ng isogeny-based cryptography including Diffie-Hellman key exchange\, elli
ptic curves\, algebraic number theory\, and graph theory providing various
examples supported by SageMath. We cover the mathematical bases\, protoco
ls\, and hardness assumptions of SIDH and CSIDH as well as surveying some
numerical analysis of the practical uses of the schemes from the literatur
e. We review additional cryptographic schemes and applications which also
utilize isogenies and offer a brief direct comparison between SIDH and CSI
DH. Finally\, we state certain open questions pertaining to approaches to
better understanding isogeny-based cryptography using related branches of
mathematics.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/17/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Amin Shokrollahi (EPFL (Switzerland))
DTSTART;VALUE=DATE-TIME:20201021T130000Z
DTEND;VALUE=DATE-TIME:20201021T140000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/18
DESCRIPTION:Title: Chord Signaling\nby Amin Shokrollahi (EPFL (Switzerland)) as p
art of University of Zurich (joint with Neuchatel) applied algebra seminar
s\n\n\nAbstract\nCommunication of data on electrical wires between chips i
s fast gaining prominence in the electronics industry. Because most of the
components of the transmitter and the receiver of such links are analog\,
rather than digital\, they don’t benefit as much from Moore’s law. On
the other hand\, the need to transmit data ever faster calls for higher r
ates of transmission over existing electrical wires. Since in this type of
communication\, noise is highly frequency dependent\, higher transmission
rates lead to much higher noise\, and therefore a much higher growth of p
ower consumption than linear. The industry has long recognised this proble
m as the “Interconnect bottleneck”. Fundamental solutions to this impo
rtant problem have remained elusive\, however. A look at the capacity of t
hese channels reveals that today we are only transmitting at anywhere betw
een 1% to 4% of the capacity. Therefore\, at least on the surface\, there
is a lot to be gained by applying methods from communication theory to thi
s problem. However\, unlike many other systems such as wireless\, DSL\, sa
tellite\, or optical communication\, the constraints on the chip-to-chip c
ommunication system are very different: transmission rates are typically 1
000 times those encountered in wireless communication. On the other hand\,
the energy consumed for the transmission and recovery of each bit is abou
t 1000 times less than what is customary in wireless. Also\, latency requi
rements are extremely stringent\, allowing only latencies up to very few n
anoseconds. Therefore\, it is not possible to use fancy processing methods
. In this talk I will introduce a new modulation scheme for chip-to-chip c
ommunication which we call chordal codes. These codes are somewhat reminis
cent of spatial MIMO systems\, and provide a first step towards a better u
tilisation of the available communication bandwidth between chips. Current
implementations of systems based on these codes show a large reduction of
total power of the communication PHY and a large increase of the communic
ation speed compared to other classical systems.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/18/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Michel Lavrauw (Sabanci University)
DTSTART;VALUE=DATE-TIME:20201118T140000Z
DTEND;VALUE=DATE-TIME:20201118T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/19
DESCRIPTION:Title: Tensors in Finite Geometry\nby Michel Lavrauw (Sabanci Univers
ity) as part of University of Zurich (joint with Neuchatel) applied algebr
a seminars\n\n\nAbstract\nThe concept of tensor products is ubiquitous in
the scientific literature. In this talk\, we restrict our attention to the
tensor product of a finite number of finite-dimensional vector spaces. Th
e bulk of the research on such tensor products assumes the underlying fiel
d to be the real numbers or the complex numbers.\nWith the advancement of
our knowledge and technology\, the need for efficient algorithms to verify
certain properties or compute numerical data from a given tensor has beco
me a very popular research topic. In the first part of this talk\, we will
give a short introduction explaining the main concepts and research probl
ems.\nIn the second part\, we will focus on the case where the underlying
field is finite.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/19/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Amin Sakzad (Monash University (Melbourne\, Australia))
DTSTART;VALUE=DATE-TIME:20201125T090000Z
DTEND;VALUE=DATE-TIME:20201125T100000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/20
DESCRIPTION:Title: Middle-product learning with errors (MP-LWE): foundations\, applic
ations\, and implementations\nby Amin Sakzad (Monash University (Melbo
urne\, Australia)) as part of University of Zurich (joint with Neuchatel)
applied algebra seminars\n\n\nAbstract\nIn this talk\, I will introduce a
new variant\, MP-LWE\, of the Learning With Errors problem (LWE) making us
e of the Middle Product between polynomials modulo an integer q. We exhibi
t a reduction from the Polynomial-LWE problem (PLWE) parametrized by a pol
ynomial f\, to MP-LWE\, which is defined independently of any such f. We a
lso explore some applications of different variants of MP-LWE into Titaniu
m\, a public-key encryption (PKE) scheme and MPSign\, a digital signature
scheme proven secure in the quantum random oracle model (QROM). If time al
lows\, I will introduce FACCT\, a fast\, compact and constant-time impleme
ntation technique in lattice-based crypto with applications to well-establ
ished PKE and DS schemes.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/20/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sabrina Sewer (University of Zurich)
DTSTART;VALUE=DATE-TIME:20201125T140000Z
DTEND;VALUE=DATE-TIME:20201125T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/21
DESCRIPTION:Title: Post-Quantum Cryptosystem FrodoPKE Based on the Learning with Erro
rs Problem (Masters thesis defense)\nby Sabrina Sewer (University of Z
urich) as part of University of Zurich (joint with Neuchatel) applied alge
bra seminars\n\n\nAbstract\nIn view of the ongoing research on quantum com
puters\, which will be able to break many of the cryptographic systems in
use today\, the National Institute of Standardization and Technology (NIST
) has initiated a process to evaluate and standardize one or more quantum-
resistant public-key encryption schemes. In this thesis\, we consider one
of the submitted proposals\, the lattice-based encryption scheme FrodoPKE\
, which is based on the learning with errors problem (LWE). LWE has been e
xtensively studied and cryptanalyzed by countless works. It is conjectured
to be hard to solve based on assumptions about the worst-case hardness of
standard lattice problems like GapSVP or SIVP. After an overview on the v
arious hardness results on LWE and its versatility\, we closely examine th
e design of FrodoPKE and its implementation. Finally\, we derive the optim
al parameters and show the impact of a single parameter on the security.In
view of the ongoing research on quantum computers\, which will be able to
break many of the cryptographic systems in use today\, the National Insti
tute of Standardization and Technology (NIST) has initiated a process to e
valuate and standardize one or more quantum-resistant public-key encryptio
n schemes. In this thesis\, we consider one of the submitted proposals\, t
he lattice-based encryption scheme FrodoPKE\, which is based on the learni
ng with errors problem (LWE). LWE has been extensively studied and cryptan
alyzed by countless works. It is conjectured to be hard to solve based on
assumptions about the worst-case hardness of standard lattice problems lik
e GapSVP or SIVP. After an overview on the various hardness results on LWE
and its versatility\, we closely examine the design of FrodoPKE and its i
mplementation. Finally\, we derive the optimal parameters and show the imp
act of a single parameter on the security.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/21/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Francesco Pavese (POLYTECHNIC OF BARI (Italy))
DTSTART;VALUE=DATE-TIME:20201202T140000Z
DTEND;VALUE=DATE-TIME:20201202T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/22
DESCRIPTION:Title: On cutting blocking sets and their codes\nby Francesco Pavese
(POLYTECHNIC OF BARI (Italy)) as part of University of Zurich (joint with
Neuchatel) applied algebra seminars\n\n\nAbstract\nLet PG(r\, q) be the r-
dimensional projective space over the \nfinite fi\neld GF(q). A set Χ of
points of PG(r\, q) is a cutting blocking set if for each hyperplane Π of
PG(r\, q) the set Π ∩ Χ spans Π. Cutting blocking sets give rise t
o saturating sets and minimal linear codes. Of particular interest are tho
se having a size as small as possible. In this talk\, I will discuss known
constructions of cutting blocking sets\, from which there arise minimal l
inear codes whose length grows linearly with respect to their dimension. I
will also present two new constructions of cutting blocking sets whose si
zes are smaller than the known ones.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/22/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Eduardo Camps (University of Neuchâtel (Neuchâtel))
DTSTART;VALUE=DATE-TIME:20201209T140000Z
DTEND;VALUE=DATE-TIME:20201209T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/23
DESCRIPTION:Title: Monomial Decreasing Codes\nby Eduardo Camps (University of Neu
châtel (Neuchâtel)) as part of University of Zurich (joint with Neuchate
l) applied algebra seminars\n\n\nAbstract\nIn this talk\, beginning with t
he original construction of polar codes\, we explore the monomial decreasi
ng codes as a generalization of those in channels with strong symmetry. We
analyze their parameters and their relation with other well-known familie
s of codes.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/23/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Martino Borello (Université de Paris 8 (Paris))
DTSTART;VALUE=DATE-TIME:20201216T140000Z
DTEND;VALUE=DATE-TIME:20201216T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/24
DESCRIPTION:Title: Asymptotic performance of G-codes and uncertainty principle.\n
by Martino Borello (Université de Paris 8 (Paris)) as part of University
of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nT
he uncertainty principle is a very famous inequality in Physics\, Signal P
rocessing\, and Harmonic Analysis. It compares the supports of functions a
nd of their complex-valued Fourier transforms. In a recent paper by Evra\,
Kowalski\, and Lubotzky a connection between the uncertainty principle an
d the asymptotic performance of cyclic codes was pointed out. Note that th
e existence of an asymptotically good family of cyclic codes is a problem
open for more than half a century. In the first part of the talk\, we will
present some recent results about the asymptotic performance of group cod
es\, which are a generalization of cyclic codes. In the second part\, we w
ill give an overview of conjectural and proved results about the uncertain
ty principle over finite fields. A naive version of this principle\, which
is verified by any finite field\, implies that there exist sequences of c
yclic codes of length n\, arbitrary rate\, and minimum distance Ω(n^α) f
or all 0 < α < 1/2.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/24/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Katerina Mitrokotsa (University of St. Gallen)
DTSTART;VALUE=DATE-TIME:20210217T140000Z
DTEND;VALUE=DATE-TIME:20210217T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/25
DESCRIPTION:Title: Outsourcing computations to a cloud that you don't trust\nby K
aterina Mitrokotsa (University of St. Gallen) as part of University of Zur
ich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nIn this
talk\, we discuss the problem of outsourcing computations to untrusted se
rvers in multiple settings (i.e.\, multiple clients\, multiple servers). M
ore precisely\, we discuss three new cryptographic primitives\, verifiable
homomorphic secret sharing\, homomorphic multi-key authenticators and hom
omorphic signcryption. The first two can be used when multiple clients wan
t to outsource joint computations\, while the third when both verifiabilit
y and proof of the data's authenticity need to be provided. We provide hig
hlights on the proposed cryptographic constructions and discuss the main c
hallenges that are overcome when we employ them.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/25/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Andreia Venzin (University of Zurich)
DTSTART;VALUE=DATE-TIME:20210224T140000Z
DTEND;VALUE=DATE-TIME:20210224T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/26
DESCRIPTION:Title: Castelnuovo-Mumford Regularity and the Complexity of Gröbner Basi
s Algorithms (Master's thesis defense)\nby Andreia Venzin (University
of Zurich) as part of University of Zurich (joint with Neuchatel) applied
algebra seminars\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/26/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sebastian Heri ((Solothurn))
DTSTART;VALUE=DATE-TIME:20210303T140000Z
DTEND;VALUE=DATE-TIME:20210303T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/27
DESCRIPTION:Title: Classification and Construction of Self-Dual Convolutional Codes (
Master's thesis defense)\nby Sebastian Heri ((Solothurn)) as part of U
niversity of Zurich (joint with Neuchatel) applied algebra seminars\n\nAbs
tract: TBA\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/27/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Magali Bardet (University of Rouen (DIR) (Rouen))
DTSTART;VALUE=DATE-TIME:20210310T140000Z
DTEND;VALUE=DATE-TIME:20210310T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/28
DESCRIPTION:Title: Algebraic Attacks for solving the Rank Decoding and Minrank proble
ms\nby Magali Bardet (University of Rouen (DIR) (Rouen)) as part of Un
iversity of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAb
stract\nIn this talk\, I will present the recent improvements in algebraic
techniques for solving the MinRank problem\, which is ubiquitous in multi
variate and rank metric code based cryptography. Algebraic attacks now out
perform the combinatorial ones that were considered state of the art up un
til now. In the particular case of Fqm-linear codes in rank metric\, for s
olving the Rank Decoding problem\, the attack is even more efficient\, and
completely break the parameters of various schemes submitted to the NIST-
PQC standardisation process for quantum-resistant public key cryptography.
\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/28/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Umberto Martinez-Penas (University of Neuchâtel (Switzerland))
DTSTART;VALUE=DATE-TIME:20210317T140000Z
DTEND;VALUE=DATE-TIME:20210317T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/29
DESCRIPTION:Title: Constructions of Codes in the Sum-Rank Metric\nby Umberto Mart
inez-Penas (University of Neuchâtel (Switzerland)) as part of University
of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nT
he sum-rank metric simultaneously extends the Hamming metric and the rank
metric. Thus it provides a general theory that includes both classical and
rank-metric codes. In this talk\, we will present several constructions o
f Maximum Sum-Rank Distance (MSRD) codes. Each of these codes outperforms
all possible MRD codes in the applications\, as they require polynomial fi
eld sizes (in contrast with exponential field sizes for MRD codes). Our co
nstructions include our previous construction of linearized Reed-Solomon c
odes\, which simultaneously generalize Reed-Solomon codes and Gabidulin co
des. At the end\, we will present Sum-Rank BCH codes\, a family of subfiel
d subcodes of linearized Reed-Solomon codes with small field sizes and goo
d parameters\, and which extend classical BCH codes.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/29/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Alberto Ravagnani (Eindhoven University of Technology (Eindhoven))
DTSTART;VALUE=DATE-TIME:20210324T140000Z
DTEND;VALUE=DATE-TIME:20210324T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/30
DESCRIPTION:Title: The Sparseness of MRD Codes\nby Alberto Ravagnani (Eindhoven U
niversity of Technology (Eindhoven)) as part of University of Zurich (join
t with Neuchatel) applied algebra seminars\n\n\nAbstract\nAn open question
in coding theory asks whether or not MRD codes with the rank metric are d
ense as the field size tends to infinity. In this talk\, I will briefly su
rvey this problem and its connections with the theory of spectrum-free mat
rices and semifields. I will then describe a new combinatorial method to o
btain upper and lower bounds for the number of codes of prescribed paramet
ers\, based on the interpretation of optimal codes as the common complemen
ts of a family of linear spaces. In particular\, I will answer the above q
uestion in the negative\, showing that MRD codes are almost always (very)
sparse as the field size grows. The approach offers an explanation for the
strong divergence in the behaviour of MDS and MRD codes with respect to d
ensity properties. I will also present partial results on the sparseness o
f MRD codes as their column length tends to infinity. The new results in t
his talk are joint work with A. Gruica.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/30/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Stefan Tohaneanu (University of Idaho (Idaho))
DTSTART;VALUE=DATE-TIME:20210331T140000Z
DTEND;VALUE=DATE-TIME:20210331T150000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/31
DESCRIPTION:Title: Linear codes with prescribed projective codewords of minimum weigh
t\nby Stefan Tohaneanu (University of Idaho (Idaho)) as part of Univer
sity of Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstra
ct\nConsider $C$\, an $[n\,k\,d]$-linear code. Every projective codeword o
f minimum weight $d$ corresponds to a point in $\\mathbb P^{k-1}$\, and th
ere are strong connections between the algebraic and geometric properties
of these points and the parameters of $C$\, especially with the minimum di
stance $d$. The most non-trivial connection is the fact that the Castelnuo
vo-Mumford regularity of the coordinate ring of these points is a lower bo
und for $d$. Conversely\, given a finite set of points $X$ in $\\mathbb P^
{k-1}$\, it is possible to construct linear codes with projective codeword
s of minimum weight corresponding to $X$. We will discuss about these cons
tructions\, and we will also look at the particular case when the construc
ted linear code has minimum distance equal to the regularity.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/31/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hunter Lehmann (University of Kentucky (Kentucky))
DTSTART;VALUE=DATE-TIME:20210421T130000Z
DTEND;VALUE=DATE-TIME:20210421T140000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/32
DESCRIPTION:Title: Automorphisms of Cyclic Orbit Codes\nby Hunter Lehmann (Univer
sity of Kentucky (Kentucky)) as part of University of Zurich (joint with N
euchatel) applied algebra seminars\n\n\nAbstract\nCyclic orbit codes are a
prominent class of subspace codes\, generated by taking the orbit of a si
ngle subspace of the finite field $F_{q^n}$ under an action of a Singer su
bgroup. We are interested in classifying the isometry classes of these cod
es for various parameters. In order to do this\, we show that the automorp
hism group of a cyclic orbit code is heavily related to the smallest subfi
eld of the ambient field which contains a generating subspace for the code
. When there is no proper subgroup of the ambient field containing a gener
ator for the code\, we see that any possible isometry is an element of the
normalizer of the Singer subgroup.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/32/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Romy Minko (University of Oxford (Oxford\, UK))
DTSTART;VALUE=DATE-TIME:20210428T130000Z
DTEND;VALUE=DATE-TIME:20210428T140000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/33
DESCRIPTION:Title: Connections between cryptography and quantum gate synthesis\nb
y Romy Minko (University of Oxford (Oxford\, UK)) as part of University of
Zurich (joint with Neuchatel) applied algebra seminars\n\n\nAbstract\nWit
h advancements in quantum computing\, the search for efficient algorithms
for synthesising gates (the building blocks of quantum algorithms) using c
ost-effective gate sets has become an important area of research. Interest
ingly\, the problems underlying gate synthesis have a number of connection
s with cryptography. The first half of this talk will cover the history of
research in this area and an overview of the main concepts. In the second
half\, I will present recent advancements in quantum gate synthesis\, whi
ch adapt path-finding results from cryptography. This talk is aimed at res
earchers without a background in quantum computing\, so will be fairly int
roductory.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/33/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Igor Semaev (University of Bergen (Norway))
DTSTART;VALUE=DATE-TIME:20210505T130000Z
DTEND;VALUE=DATE-TIME:20210505T140000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/34
DESCRIPTION:Title: EHT public-key crypto-system and digital signatures\nby Igor S
emaev (University of Bergen (Norway)) as part of University of Zurich (joi
nt with Neuchatel) applied algebra seminars\n\n\nAbstract\nTwo works will
be surveyed: "New Public-Key Crypto-System EHT" (A.Budroni\, I.Semaev) and
"EHT Digital Signature Algorithm" (I.Semaev). The LWE (Learning with Erro
rs) problem was introduced by Regev in 2005\, where an LWE based public-ke
y encryption was described. The problem was there proved to be hard assumi
ng the hardness of computing shortest non-zero vectors in general lattices
. Since then several lattice-based public-key crypto-systems were invented
. The NIST Post-Quantum Standardisation Process stimulated interest in dev
eloping new quantum computer resistant public-key protocols. A number of s
ubmissions to this competition are LWE or Ring LWE based. In the first wor
k\, an LWE problem with a hidden trapdoor is introduced. It is used to con
struct a new efficient public-key crypto-system EHT. The new system may be
used as a KEM (Key Encapsulating Mechanism) too. It is significantly diff
erent from LWE based NIST public-key encryption candidates\, e.g.\, FrodoK
EM. The performance of EHT compares favourably with FrodoKEM. In the secon
d work\, a similar idea is used to construct a new digital signature algor
ithm. It is significantly different from NIST digital signature candidates
. Forging EHT signatures may be reduced to solving Closest Vector Problem
for a specific lattice with a small approximation factor. The parameters o
f the new system are comparable to those of the NIST candidates.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/34/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Habibul Islam (Indian Institute of Technology Patna (Bihar\, India
))
DTSTART;VALUE=DATE-TIME:20210512T110000Z
DTEND;VALUE=DATE-TIME:20210512T120000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/35
DESCRIPTION:Title: Construction of Quantum Codes using Constacyclic Codes\nby Hab
ibul Islam (Indian Institute of Technology Patna (Bihar\, India)) as part
of University of Zurich (joint with Neuchatel) applied algebra seminars\n\
n\nAbstract\nThere are several convenient ways to construct quantum codes
from classical codes\, the CSS and Hermitian construction are two popular
among them. Here\, we describe how classical (particularly\, constacyclic)
codes have been successfully producing new and better quantum codes under
these constructions. First\, we implement the idea over finite fields and
then extend to non-commutative rings followed by commutative rings. From
an application point of view\, many quantum codes outperforming the best-k
nown codes are constructed.\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/35/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Vincent Neiger (Université de Limoges (France))
DTSTART;VALUE=DATE-TIME:20210519T130000Z
DTEND;VALUE=DATE-TIME:20210519T140000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/36
DESCRIPTION:Title: Faster modular composition of polynomials\nby Vincent Neiger (
Université de Limoges (France)) as part of University of Zurich (joint wi
th Neuchatel) applied algebra seminars\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/36/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sven Puchinger (Technische Universität München (München))
DTSTART;VALUE=DATE-TIME:20210526T130000Z
DTEND;VALUE=DATE-TIME:20210526T140000Z
DTSTAMP;VALUE=DATE-TIME:20210514T205345Z
UID:AppliedAlgebra/37
DESCRIPTION:by Sven Puchinger (Technische Universität München (München)
) as part of University of Zurich (joint with Neuchatel) applied algebra s
eminars\n\nAbstract: TBA\n
LOCATION:https://researchseminars.org/talk/AppliedAlgebra/37/
END:VEVENT
END:VCALENDAR