Ataques quânticos a geradores de números pseudo-aleatórios.

• Ano de defesa: 2011
• Autor(a) principal: COSTA, Elloá Barreto Guedes da.
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Campina Grande; Brasil; Centro de Engenharia Elétrica e Informática - CEEI; PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO; UFCG
• Palavras-chave em Português: Ataques Quânticos; Geradores Pseudo-Aleatórios; Algoritmos Quânticos; Ataques Criptoanalíticos; Computação Quântica; Gerador Criptograficamente Seguro; Construção de Blum-Micali - Gerador; Pseudorandom Generators; Quantum Algorithms; Cryptanalytic Attacks; Quantum Computing; Geradores de Números Aleatórios; Geradores de Números Pseudo-Aleatórios; Logaritmo Discreto; Gerador de Blum-Micalli; Ciência da Computação.
• Link de acesso: http://dspace.sti.ufcg.edu.br:8080/jspui/handle/riufcg/1864

Este trabalho apresenta um ataque quântico de comprometimento permanente ao gerador pseudo-aleatório de Blum-Micali. A segurança deste gerador, classificado como criptograficamente seguro, baseia-se na hipótese de intratabilidade do problema do logaritmo discreto perante a Computação Clássica. O ataque proposto faz uso do algoritmo quântico de busca em conjunto com o algoritmo quântico para o logaritmo discreto para comprometer a imprevisibilidade do gerador, recuperando todas as saídas passadas e futuras do mesmo. O presente trabalho também descreve generalizações deste ataque que o adequam a uma gama mais vasta de geradores, incluindo geradores da Construção de Blum-Micali e geradores com múltiplos predicados difíceis. Tais generalizações também abrangem a realização de ataques em situações adversas, por exemplo, quando o adversário captura bits não consecutivos ou quando há menos bits que o requerido. Comparado à sua contrapartida clássica, o algoritmo quântico proposto nesse trabalho possui um ganho quadrático em relação à recuperação do representante do estado interno do gerador, seguido de um ganho superpolinomial na obtenção dos demais elementos do estado interno. Estes resultados caracterizam ameaças,elaboradas com Computação Quântica, contra a segurança de geradores utilizados em diversas aplicações criptográficas.