Orientadores: Ricardo Dahab, Diego de Freitas AranhaDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: 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 ShoupAbstract: 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 ShoupMestradoCiência da ComputaçãoMestra em Ciência da Computação133071/2015-41406907CNPQCAPES