Return to search

Uma família de códigos corretores de erro para criptossistemas eficientes baseados em decodificação de síndromes. / A family of error-correcting codes to eficient cryptosystems based on syndrome decoding.

A criptografia é uma ciência que tem especial destaque no mundo moderno, evidenciando a necessidade em pesquisar algoritmos e técnicas para seu aperfeiçoamento. Apesar das soluções atualmente empregadas serem baseadas em problemas suficientemente seguros, se comparados ao poderio computacional necessário para resolvê-los, seu emprego futuro é questionado. Pesquisas demonstram potencial vulnerabilidade destes sistemas, caso tenhamos à disposição computadores quânticos sendo utilizados para fraudá-los. Alternativas têm sido estudadas e o criptossistema proposto por Robert J. McElice se mostra como uma das mais interessantes, visto sua versão convencional, baseada em códigos de Goppa, ter a segurança até o momento inafetada, inclusive se levado em conta a disponibilidade de tecnologia quântica. Entretanto, tal solução sofria com o tamanho de suas grandes chaves criptográficas, representando um entrave para sua aplicação na prática. Objetivando minimizar esta deficiência, neste trabalho, propomos a classe de códigos de Goppa quase-diádicos, que admitem uma matriz de paridade ou matriz geradora com representação muito compacta, produzindo chaves do tipo McEliece que são até um fator t = O(n) menores que as chaves genéricas, em notação que omite fatores logarítmicos, produzidas a partir de códigos de Goppa de comprimento n, para a correção de t erros em característica 2. No caso binário, essa família também mantém a capacidade de corrigir o número total projetado de erros em vez de apenas a metade; esta propriedade falta a todas as tentativas anteriores de construção de códigos compactos para fins de criptografia, incluindo (BERGER et al., 2009). Além disso, a complexidade de todas as operações criptográficas típicas torna-se O(n). Esta proposta foi submetida e selecionada para publicação e apresentação no XVI Workshop Selected Areas in Cryptography (SAC2009), ocorrido entre 13 e 14 de Agosto de 2009, em Calgary, Alberta, Canadá, de referência bibliográfica (MISOCZKI; BARRETO, 2009). Este evento foi realizado em cooperação com a International Association for Cryptologic Research (IACR) e teve seus artigos publicados pela Springer em Lecture Notes in Computer Science, volume 5867. / Cryptography is a science that is especially prominent in the modern world, highlighting the need to find algorithms and techniques for its improvement. Despite the fact that solutions currently used are based on problems that are sufficiently secure, if compared to the computing power needed to solve them, their future use is questioned. Researches demonstrated the potential vulnerability of these systems, if quantum computers are used to defraud them. Alternatives have been studied and the cryptosystem proposed by Robert J. McElice has been considered as one of the most interesting, since its conventional version, based on Goppa codes, has the security so far unaffected, even if taken into account the availability of quantum technology. However, this solution suffered with the large size of their cryptographic keys, an obstacle to its implementation in practice. Aiming to minimize this shortcoming, in this paper, we propose the class of quasidyadic Goppa codes, which admits a generator or parity-check matrix with very compact representation, producing McEliece keys that are up to a factor t = O(n) lower than the generic keys, in notation which omits logarithmic factors, produced from Goppa codes of length n, to correct t errors in characteristic 2. In the binary case, this family also retains the ability to correct the projected total number of errors, rather than just half; this property lacks in all previous attempts to build compact code for encryption, including (BERGER et al., 2009). Moreover, the complexity of all typical cryptographic operations becomes O(n). This proposal was submitted and selected for publication and presentation in the XVI Workshop Selected Areas in Cryptography (SAC2009), occurred in August, 13th and 14th, 2009, in Calgary, Alberta, Canada, with bibliographic reference (MISOCZKI; BARRETO, 2009). This event was held in cooperation with the International Association for Cryptologic Research (IACR) and had his papers published by Springer in Lecture Notes in Computer Science, volume 5867.

Identiferoai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-30112010-154949
Date05 October 2010
CreatorsRafael Misoczki
ContributorsPaulo Sérgio Licciardi Messeder Barreto, Cíntia Borges Margi, Routo Terada
PublisherUniversidade de São Paulo, Engenharia Elétrica, USP, BR
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Sourcereponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0035 seconds