BEGIN:VCALENDAR
VERSION:2.0
PRODID:www.lu.se
BEGIN:VEVENT
UID:60378b5411db6
DTSTART:20210122T081500Z
SEQUENCE:0
TRANSP:OPAQUE
DTEND:20210122T081500Z
LOCATION:Online at the zoom platform (Link by registration)
SUMMARY:PhD defence: Some Notes on Post-Quantum Cryptanalysis (Erik Mårten
sson)
CLASS:PUBLIC
DESCRIPTION:Kontakt: thomas.johansson@eit.lth.se\n\nThesis title: \;Som
e Notes on Post-Quantum Cryptanalysis\n\nAuthor: \;Erik Mårtensson\,&
nbsp\;Department of Electrical and Information Technology\, Lund Universit
y\n\nOpponent: Prof. Alexander May\, Ruhr-Universität Bochum\, Germany\n\
nWhen: 22 January 2021 at 9.15\n\nLocation: \;Online at the zoom platf
orm - access by registration\n\nThe thesis for download (PDF\, 4\,7 MB)\n\
nAbstract\n\nCryptography as it is used today relies on a foundational lev
el on the assumption that either the Integer Factoring Problem (IFP) or th
e Discrete \; Logarithm Problem (DLP) is computationally intractable.
In the 1990s Peter \;Shor developed a quantum algorithm that solves bo
th problems in polynomial time. Since then alternative foundational mathem
atical problems to replace IFP and DLP have been suggested. This area of r
esearch is called post-quantum cryptology.\n\nTo remedy the threat of quan
tum computers the National Institute of Standards and Technology (NIST) ha
s organized a competition to develop schemes for post-quantum encryption a
nd digital signatures. For both categories latticebased cryptography candi
dates \; dominate. The second most promising type of candidate for enc
ryption is code-based cryptography.\n\nThe lattice-based candidates are ba
sed on the difficulty of either the Learning With Errors problem (LWE) or
the Nth Degree Truncated Polynomial problem (NTRU)\, of which LWE is the f
ocus of this thesis. The difficulty of both these\nproblems in turn relies
on the difficulty of variations of the Shortest Vector Problem (SVP). Cod
e-based cryptography is based on the difficulty of decoding random linear
codes.\n\nThe main focus of this thesis is on solving the LWE problem usin
g the Blum-Kalai-Wasserman algorithm (BKW).We have the following improveme
nts of the algorithm.\n\n\nWe combined BKW with state-of-the-art lattice s
ieving methods to improve the complexity of the algorithm. We also elabora
te on the similarities and differences between BKW and lattice sieving\, t
wo approaches that on a shallow level look very different.\nWe developed a
new binary approach for the distinguishing phase of the BKW algorithm and
showed that it performs favorably compared to previous distinguishers.\nW
e investigated the Fast Fourier Transform (FFT) approach for the distingui
shing part of BKW showing that it performs better than theory predicts and
identically with the optimal distinguisher. We showed that we could impro
ve its performance by limiting the number of hypotheses being tested.\nWe
introduced practical improvements of the algorithm such as nonintegral ste
p sizes\, a file-based sample storage solution and an implementation of th
e algorithm.\n\n\nWe also improved the classical state-of-the-art approach
es for k-sieving - lattice sieving where k vectors are combined at a time
- by using quantum algorithms. At the cost of a small increase in time com
plexity we managed to drastically decrease the space requirement compared
to the state-of-the-art quantum algorithm for solving the SVP.\n\nFinally\
, we developed an algorithm for decoding linear codes where the noise is G
aussian instead of binary. We showed how code-based schemes with Gaussian
noise are easily broken. We also found other applications for the algorith
m in side-channel attacks and in coding theory.\n\nRegistration\n\nPlease
register at \;https://www.lth.se/digitalth/events/register-2021-01-22-
9-15 inorder to get an access link for the zoom platform.\n\n \;\n\n\n
Mer information om händelsen: http://www.lu.se/evenemang/phd-defence-some
-notes-post-quantum-cryptanalysis-erik-martensson
DTSTAMP:20210225T113444Z
END:VEVENT
END:VCALENDAR