Please use this identifier to cite or link to this item: https://hdl.handle.net/1822/47824

Full metadata record
DC FieldValueLanguage
dc.contributor.advisorProença, Alberto Josépor
dc.contributor.advisorMariano, Artur Miguel Matospor
dc.contributor.authorGonçalves, Hélder José Alvespor
dc.date.accessioned2017-11-28T09:28:53Z-
dc.date.available2017-11-28T09:28:53Z-
dc.date.issued2016-12-21-
dc.date.submitted2016-10-24-
dc.identifier.urihttps://hdl.handle.net/1822/47824-
dc.descriptionDissertação de mestrado em Engenharia Informática (área de especialização em Computação Paralela e Distribuída)por
dc.description.abstractThe security of most digital systems is under serious threats due to major technology breakthroughs we are experienced in nowadays. Lattice-based cryptosystems are one of the most promising post-quantum types of cryptography, since it is believed to be secure against quantum computer attacks. Their security is based on the hardness of the Shortest Vector Problem and Closest Vector Problem. Lattice basis reduction algorithms are used in several fields, such as lattice-based cryptography and signal processing. They aim to make the problem easier to solve by obtaining shorter and more orthogonal basis. Some case studies work with numbers with hundreds of digits to ensure harder problems, which require Multiple Precision (MP) arithmetic. This dissertation presents a novel integer representation for MP arithmetic and the algorithms for the associated operations, MpIM. It also compares these implementations with other libraries, such as GNU Multiple Precision Arithmetic Library, where our experimental results display a similar performance and for some operations better performances. This dissertation also describes a novel lattice basis reduction module, LattBRed, which included a novel efficient implementation of the Qiao’s Jacobi method, a Lenstra-LenstraLovasz (LLL) algorithm and associated parallel implementations, a parallel variant of the ´ Block Korkine-Zolotarev (BKZ) algorithm and its implementation and MP versions of the the Qiao’s Jacobi method, the LLL and BKZ algorithms. Experimental performances measurements with the set of implemented modifications of the Qiao’s Jacobi method show some performance improvements and some degradations but speedups greater than 100 in Ajtai-type bases.por
dc.description.abstractAtualmente existe um grande avanço tecnológico que poderá colocar em causa a segurança da maioria dos sistemas informáticos. Sistemas criptográficos baseados em reticulados são um dos mais promissores tipos de criptografia pós-quântica, uma vez que se acredita que estes sistemas são seguros contra possíveis ataques de computadores quânticos. A segurança destes sistemas está baseada na dificuldade de resolver o problema do vetor mais curto e o problema do vetor mais próximo. Algoritmos de redução de bases de reticulados são usados em muitos campos científicos, tais como criptografia baseada em reticulados. O seu principal objetivo e tornar o problema mais fácil de resolver, tornando a base do reticulado mais curta e ortogonal. Alguns casos de estudo requerem o uso de números com centenas de dígitos para garantir problemas mais difíceis. Portanto, é importante o uso de módulos de precisão múltipla. Esta dissertação apresenta uma nova representação de inteiros para aritmética de precisão múltipla e todas as respetivas funções de um módulo, ‘MpIM’. Também comparamos as nossas implementações com outras bibliotecas de precisão múltipla, tais como ‘GNU Multiple Precision Arithmetic Library’, em que obtivemos desempenhos semelhantes e em alguns casos melhores. A dissertação também apresenta um novo módulo para a redução de bases de reticulados, ‘MpIM’, que inclui uma nova e eficiente implementação do ‘Qiao’s Jacobi method’, o algoritmo ‘Lenstra-Lenstra-Lovasz’ (LLL) e respetiva implementação paralela, uma variante paralela do algoritmo ‘Block Korkine-Zolotarev’ (BKZ) e a sua versão sequencial e versões de precisão múltipla do ‘Qiao’s Jacobi method’, LLL e BKZ. Trabalhos experimentais mostraram que a versão do ‘Qiao’s Jacobi method’ que implementa todas as modificações sugeridas mostra ganhos e degradações de desempenho, contudo com aumentos de desempenho superiores a 100 vezes em bases ‘Ajtai-type’.por
dc.language.isoengpor
dc.rightsopenAccesspor
dc.titleTowards an efficient lattice basis reduction implementationpor
dc.title.alternativeImplementação eficiente de algoritmos para a redução de bases de reticuladospor
dc.typemasterThesiseng
dc.identifier.tid201616009por
thesis.degree.grantorUniversidade do Minhopor
sdum.degree.grade15 valorespor
sdum.uoeiEscola de Engenhariapor
dc.subject.fosEngenharia e Tecnologia::Engenharia Eletrotécnica, Eletrónica e Informáticapor
Appears in Collections:BUM - Dissertações de Mestrado
DI - Dissertações de Mestrado

Files in This Item:
File Description SizeFormat 
Hélder José Alves Gonçalves.pdfTese3,15 MBAdobe PDFView/Open

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID