Mais um blog inútil.

Nos últimos dias, tem andado uma notícia a passar pelos sites de notícias "científicas" que me chamou a atenção. Pela negativa. Pois parece que uns gajos quaisquer descobriram que o algoritmo proposto pelo McEliece em 1978 é resistente a "todos os ataques quânticos". Que valente merda de "jornalismo".

Quem se tivesse dado ao trabalho de ler o artigo tinha reparado que só foram considerados ataques baseados na QFT (Quantum Fourier Transform). A QFT é extremamente útil na análise de sistemas criptográficos, dado que permite detectar períodos de uma função consideravelmente mais rápido que um computador clássico. Isto é posto em uso no algoritmo de Shor e extensões do mesmo para quebrar sistemas baseados em factorização de inteiros (RSA), logaritmo discreto (DH, DSA), logaritmo discreto em curvas elípticas (ECDH, ECDSA), etc.

No caso do algoritmo de McEliece (mal escrito num dos artigos --- será assim tão difícil?), o problema a resolver é consideravelmente diferente --- trata-se de descodificar um código de Goppa aleatório. No caso genérico, este problema está na classe NP-hard, e não vai ter nenhuma aceleração exponencial no futuro. Como tal, o resultado obtido não é nenhuma surpresa, e nem sequer justifica chegar às notícias.

Finalmente, o argumento que o McEliece resiste a todos os ataques quânticos conhecidos simplesmente não é verdade. É sabido que o algoritmo de Grover acelera o processo de pesquisa quadraticamente; isto é usado eficientemente para acelerar o algoritmo clássico que quebra o McEliece, de forma a que sejam necessárias chaves 4 vezes maiores.