Ataques quânticos ao gerador pseudo-aleatório de Blum-Micali

Edmar Nascimento, Nigini Oliveira, Francisco Assis

DOI: 10.14209/sbrt.2007.31307

Evento: XXV Simpósio Brasileiro de Telecomunicações (SBrT2007)

Keywords: Gerador Blum-Micali algoritmos quânticos seqüências pseudo-aleatórias

Abstract

A utilização de seqüências pseudo-aleatórias é de grande importância em diversas aplicações da criptografia. Um ataque a um gerador pseudo-aleatório objetiva reproduzir uma dada seqüência pseudo-aleatória a partir de um conjunto de termos dessa seqüência. Classicamente, esse é um problema de difı́cil solução, ou seja, não existe algoritmos conhecidos em tempo polinomial que realizem esta tarefa. Por outro lado, o desenvolvimento de algoritmos quânticos vem mostrando que determinados tipos de problemas podem ser resolvidos de modo mais eficiente. Neste artigo, é apresentado um circuito quântico que realiza um ataque ao gerador Blum-Micali apresentando um ganho no número de operações em relação aos algoritmos clássicos conhecidos.

Download