Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/305631
Type: DISSERTAÇÃO DIGITAL
Degree Level: Mestrado
Title: Amostragem gaussiana aplicada à criptografia baseada em reticulados
Title Alternative: Gaussian sampling applied to lattice-based cryptography
Author: Ortiz, Jheyne Nayara, 1992-
Advisor: Dahab, Ricardo, 1957-
Abstract: Resumo: A Criptografia Pós-Quântica fundamenta-se em classes de problemas considerados difíceis sob o ponto de vista da complexidade computacional clássica e quântica. Dentre as classes de problemas mais proeminentes, encontra-se a de problemas baseados em reticulados. Na Criptografia Baseada em Reticulados, diversos esquemas requerem a amostragem de vetores de um reticulado e de inteiros seguindo uma distribuição que, convencionalmente, é uma função Gaussiana. A amostragem de pontos de um reticulado pode também ser empregada para resolver variantes dos problemas SVP e CVP sobre reticulados, problemas do vetor mais curto e do vetor mais próximo, respectivamente. Este trabalho apresenta implementações com tempo de execução constante para os métodos Knuth-Yao e Ziggurat discreto apropriados à amostragem Gaussiana sobre os inteiros. Por se apresentar substancialmente mais eficiente que a implementação do Ziggurat discreto, uma implementação para o método Knuth-Yao é aplicada à amostragem sobre reticulados e ao esquema de encriptação baseado no problema LWE (Learning with Errors) sobre anéis. Para a amostragem de vetores de um reticulado, os resultados se referem à geração de vetores de um reticulado q-ário para a derivação de chaves privadas em um esquema de Encriptação Hierárquica Baseada em Identidades e à amostragem sobre reticulados NTRU. Os experimentos têm como alvo um computador pessoal Intel Ivy Bridge e as implementações estão descritas em linguagem C++ com aporte da biblioteca NTL de Victor Shoup

Abstract: Post-Quantum cryptography is based on classes of problems that are hard to solve using both classical and quantum computing. One of the most promising classes of problems is based on lattices. In Lattice-Based Cryptography, some cryptosystems require sampling lattice points and integers over a distribution that, conventionally, follows a Gaussian function. Sampling lattice points can also be used to solve variants of the SVP and CPV problems over lattices, namely Shortest Vector Problem and Closest Vector Problem, respectively. This work presents constant-time implementations of the Knuth-Yao and discrete Ziggurat methods for Gaussian sampling over integers. We propose an implementation for the Knuth-Yao algorithm that is substantially more efficient than our discrete Ziggurat implementation. Therefore, the Knuth-Yao implementation was applied for sampling over lattices and to the Ring-LWE-based (Learning with Errors over Rings) encryption scheme. For Gaussian sampling over lattices, the results refer to the q-ary lattice point generation for the private-key derivation in a Hierarchical Identity-Based Encryption scheme and also to the sampling over NTRU lattices. Our experiments target an Intel Ivy Bridge desktop and all implementations are described using C++ language with support of the NTL library of Victor Shoup
Subject: Criptografia
Criptografia pós-quântica
Distribuição gaussiana
Teoria dos reticulados
Editor: [s.n.]
Date Issue: 2016
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Ortiz_JheyneNayara_M.pdf1.41 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.