Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/334823
Type: DISSERTAÇÃO DIGITAL
Degree Level: Mestrado
Title: Fórmulas de isogenias para modelos alternativos de curvas elípticas
Title Alternative: Isogeny formulas for alternative models of elliptic curves
Author: Silva, João Paulo da, 1992-
Advisor: Dahab, Ricardo, 1957-
Abstract: Resumo: A segurança dos sistemas de chave pública é baseada na dificuldade de se resolver certos problemas matemáticos. Com o possível surgimento de computadores quânticos de propósito geral em larga escala, vários desses problemas, como fatoração de números inteiros e a computação de logaritmos discretos, seriam eficientemente resolvidos. De forma a contornar os problemas provenientes desta perspectiva futura, a pesquisa em criptografia de chave pública resistente à ataques quânticos, também chamada de criptografia pós-quântica (PQC), surge e tem sido bastante produtiva nos últimos anos. Inúmeros candidatos vieram de encontro ao preenchimento desta lacuna e entre eles podemos citar sistemas: baseados em problemas sobre reticulados; baseados em hash criptográfico; construídos sobre a dificuldade de se achar soluções em sistemas multivariados; baseados em códigos corretores de erros; e, baseados na dificuldade de se computarem isogenias entre curvas elípticas supersingulares. Os sistemas criptográficos de chave pública baseados no problema de se computar isogenias têm se mostrado bons candidatos para a próxima geração de padrões de criptografia de chave pública no cenário da PQC. Umas das vantagens de sistemas desse tipo se dá pelo fato de possuírem chaves muito menores em relação aos concorrentes. Umas das questões que se colocam quando sistemas baseados em isogenias são construídos é a efetiva computação dos mapas no modelo em que as curvas elípticas estão representadas. A busca por fórmulas mais eficientes e seguras computacionalmente se torna um objeto merecedor de esforços por parte do pesquisador. Trabalhos anteriores apresentaram fórmulas para curvas elípticas no modelo de Weierstrass, Montgomery, Edwards, Huff e curvas Extended Jacobi Quartic. Motivados por um trabalho anterior de D. Moody e D. Shumow [33], neste trabalho, apresentamos a derivação de mapas para curvas elípticas dadas nos modelos de Intersecções de Jacobi e Twisted Hesse. Nossa derivação segue uma estratégia multiplicativa que se contrapõe à ideia aditiva apresentada na fórmula de Vélu. Por fim, apresentamos uma comparação do custo computacional para se gerar os mapas de isogenias de grau l, onde l=2k+1. Em coordenadas afins, nossas fórmulas requerem 46,8% menos computação que o modelo de Huff e 48% menos computação que as fórmulas dadas para o modelo Extended Jacobi Quartic quando da computação de isogenias de grau 3. Tomando isogenias de grau mais elevado, igual a 101, nossas fórmulas requerem 23,4% menos computação que Huff e 24.7% menos computação que a fórmula para o modelo Extended Jacobi Quartic

Abstract: The security of public key systems is based on the difficulty of solving certain mathematical problems. With the possible emergence of large-scale general-purpose quantum computers, several of these problems, such as integers factorization and discrete logarithm computation, would be efficiently solved. To bypass problems from this future perspective, research into quantum-resistant public key cryptography, also called post-quantum cryptography (PQC), emerges and has been quite productive in recent years. Numerous candidates came to fill this gap and among them we can mention systems: based on problems on lattices; based on cryptographic hash; built on the difficulty of finding solutions in multivariate systems; based on error-correcting codes; and, based on the difficulty of computing isogenies between supersingular elliptic curves. Public key cryptographic systems based on the problem of computing isogenies have proved to be good candidates for the next generation of public key cryptography standards in the PQC scenario. One of the advantages of such systems is that they have much smaller keys than their competitors. One of the questions that arises when constructing systems based on isogenies is the effective computation of maps in the model in which the elliptic curves are represented. The search for more efficient and computationally safe formulas becomes an object worthy of efforts on the part of the researcher. Previous work has presented formulas for elliptic curves in the Weierstrass model, Montgomery, Edwards, Huff, and Extended Jacobi Quartic model. Motivated by an earlier work by D. Moody and D. Shumow [33], in this work, we present the derivation of maps for elliptic curves given in Jacobi Intersection and Twisted Hesse models. Our derivation follows a multiplicative strategy that contrasts with the additive idea presented in the Vélu formula. Finally, we present a comparison of computational cost to generate maps for isogenies of degree l, where l = 2k + 1. In affine coordinates, our formulas require 46.8% less computation than the Huff model and 48% less computation than the formulas given for the Extended Jacobi Quartic model when computing isogenies of degree 3. Considering higher degree isogenies as 101, our formulas require 23.4% less computation than the Huff model and 24.7% less computation than the formula for the Extended Jacobi Quartic model
Subject: Criptografia de chaves públicas
Criptografia pós-quântica
Curvas elípticas
Language: Português
Editor: [s.n.]
Citation: SILVA, João Paulo da. Fórmulas de isogenias para modelos alternativos de curvas elípticas. 2019. 1 recurso online (67 p.). Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP.
Date Issue: 2019
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Silva_JoaoPauloDa_M.pdf1.04 MBAdobe PDFView/Open


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