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

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.