%!TEX root = diss.tex

\chapter{Conclusão}
\label{cap:conclusao}


Este trabalho apresenta dois novos algoritmos para a recuperação de chave.
Ambos são mais eficientes e trabalham eficientemente com menos
informação do que o algoritmo original de Guo et al.~\cite{guo2016key}.
Os algoritmo propostos têm natureza bem diferente,
e ambos podem ser paralelizados trivialmente, pois evitam o problema de paralelizar
a busca em profundidade~\cite{reif1985depth}.

O primeiro é uma variante probabilística do algoritmo original, sendo, como este, baseado
numa busca em árvore. Apesar de ser mais eficiente que o algoritmo 
original, seu desempenho é  significativamente limitado quando há pouca informação sobre o espectro
da chave privada, 
e esta limitação é ainda pior para níveis de segurança mais altos.
O motivo da limitação é que o número de nós possíveis a cada nível descido na árvore de busca
cresce exponencialmente quanto menor a quantidade de informação sobre o espectro da chave.
Para trabalhar eficientemente com parâmetros do nível de segurança de 80 bits, 
o algoritmo probabilístico precisa que sejam feitos entre 20 e 50 milhões de testes de decodificação.
Isso corresponde a entre 4 e 10 vezes menos testes de decodificação que o número médio de testes
necessários para o algoritmo de Guo et al.~\cite{guo2016key}.

O segundo é um algoritmo iterativo baseado numa relação linear entre partes da chave. Com isso, 
é possível evitar a perda exponencial no desempenho quando há menos informação
sobre o espectro da chave. 
O maior problema do algoritmo iterativo é que, se a quantidade de informação sobre o 
espectro for muito pequena, então o algoritmo não encontra a chave. Isto não não ocorre
para algoritmos de busca em árvore, já que estes enumeram todas as chaves possíveis.
No entanto esse problema dificilmente faz com que os algoritmos de busca em árvore sejam
a melhor opção, pois, com uma quantidade de informação baixa o suficiente
para que o algoritmo iterativo não encontre a chave, o uso dos algoritmos de busca em árvore 
pode ser impraticável para níveis de segurança mais altos do que 80 bits.
Para trabalhar eficientemente no nível de segurança de 80 bits, o número de testes de decodificação 
necessários é similar ao do algoritmo probabilístico, isto é, entre 20 e 50 milhões.
Pela análise da quantidade de informação necessária, é esperado que o algoritmo iterativo
precise de significativamente menos testes de decodificação para níveis de segurança mais altos.

Em trabalhos futuros, pode ser interessante estudar como o uso de outros decodificadores afeta
o número de testes de decodificação necessários para o ataque.
Uma outra pesquisa interessante é considerar variantes dos algoritmos propostos que trabalhem
eficientemente com menos informação sobre a os espectros.
A importância de estudar esse problema vem de sua relação com a
estimativa da vida útil de uma chave QC-MDPC, isto é, quantas
decodificações um usuário pode fazer até que sua chave seja comprometida.

Uma possível contramedida, discutida por Guo et al.~\cite{guo2016key},
para o ataque de reação são decodificadores que falham
com probabilidade próxima de $2^\lambda$ para o nível de segurança $\lambda$. Isso 
faz com que o número de testes de decodificação necessários para distinguir entre distâncias
dentro e fora do espectro seja potencialmente muito grande. Porém os decodificadores
conhecidos para códigos MDPC ainda estão muito distantes de atingir essa
precisão~\cite{maurich2015implementing}. Talvez
uma possibilidade mais realista seja descobrir decodificadores que falhem com uma probabilidade
independente da similaridade entre os espectros da chave privada e do vetor de erro, mesmo que
estes decodificadores falhem mais.

