lnu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Analysis of Lattice Reduction Algorithms: Solving SVP Challenges
Linnaeus University, Faculty of Technology, Department of Mathematics.
2018 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Lattice-based cryptography which holds a great promise for post-quantum cryptographyis naturally concerned by lattice reduction algorithms, the essential tools in the algorithmicstudy of lattices and its applications. In order to precisely estimate the securityparameters of these cryptosystems, it is a necessity to assess the practical diculty of theshortest vector problem (SVP) by analyzing the known ecient algorithms for solvingit.In this thesis project, we revisit a recursive lattice reduction methodology going back toPlantard & Susilo's work (SCN 2010) and analyze practicality of an SVP algorithm byCheon and Lee (Cryptology ePrint Archive 2015). We show that the SVP algorithm is,in general, a theoretical progress, with little practical implications in somehow. Moreover,we have performed experimental analysis of a recent progressive BKZ algorithmproposed by Aono et al. (Eurocrypt 2016) on the Darmstadt's SVP Challenge (TUD10).From our experiments, using its open source library, we found that the simple blocksizestrategy of the algorithm is better in terms of output quality than the optimized strategy.Applying the recursive reduction methodology to the simple blocksize strategy andsome heuristics to the LLL preprocess, we have improved all of the previous records inthe SVP Challenge that are obtained by the algorithm. Moreover, our improved resultsin dimensions 117, 119 and 121 are the current best records published in the Hall ofFame of the challenge that outperformed previous records by other algorithms.

Place, publisher, year, edition, pages
2018. , p. 62
National Category
Mathematics
Identifiers
URN: urn:nbn:se:lnu:diva-75552OAI: oai:DiVA.org:lnu-75552DiVA, id: diva2:1216301
Subject / course
Mathematics
Educational program
Mathematics and Modelling, Master Programme, 120 credits
Supervisors
Examiners
Available from: 2018-06-11 Created: 2018-06-11 Last updated: 2018-06-11Bibliographically approved

Open Access in DiVA

HG18_MasterThesis(885 kB)19 downloads
File information
File name FULLTEXT01.pdfFile size 885 kBChecksum SHA-512
f4e449f38b445f34d53a4d0bed9388fad4b34ad5e3e62f2bf8020fbd7c4c13cd160d00a055fe6d46d320986d1a3cd3caa00645409fc8ce53b094d1d7cfec15fb
Type fulltextMimetype application/pdf

By organisation
Department of Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 19 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 51 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf