%% ------------------------------------------------------------------------- %%
%!TEX root = diss.tex

\chapter{Introdução}

\label{cap:introducao}



O esquema de chave pública de McEliece \cite{mceliece1978} foi o primeiro baseado em códigos 
corretores de erros,
e também o primeiro a usar um procedimento aleatório para a encriptação \cite{menezes1996handbook}.
Tanto a encriptação quanto a decriptação são computacionalmente mais eficientes que as respectivas
de outros esquemas baseados no problema de fatoração ou no problema do logaritmo discreto,
considerando os correspondentes níveis de segurança oferecidos~\cite{overbeck2009code}.
Além disso, o esquema é baseado no problema
\cNP-difícil da decodificação por síndrome \cite{berlekamp1978inherent}, que
é um problema conjecturado difícil para instâncias típicas~\cite{bernstein2009post}.
Isso sugere que o esquema de McEliece pode
oferecer uma segurança maior do que os algoritmos baseados nos
problemas de fatoração de inteiros ou no cálculo do logaritmo 
discreto, que por pertencerem à interseção das classe $\cNP$
e co$\cNP$, conjectura-se não serem $\cNP$-difíceis~\cite{arora2009computational}.

Esse esquema, como o RSA~\cite{rsa1978rsa}, foi publicado na década de 70, mas não foi 
bem recebido por dois motivos. O primeiro é que as suas chaves públicas são muito grandes. 
Por exemplo, para níveis de segurança maiores do que 100 bits, as chaves
têm tamanho maiores do que 100 quilobytes~\cite[Tabela 1.1]{bernstein2013mcbits}.
O segundo motivo é que acreditava-se ser impossível usar o problema da decodificação por síndrome
para desenvolver esquemas de assinatura. Tal crença foi justificada por
McEliece~\cite{mceliece1978} pela dificuldade de se decodificar qualquer mensagem
usando certos códigos corretores de erros, um passo importante para gerar uma assinatura.
Apesar disso, em 2001, Courtois, Finiasz, e
Sendrier~\cite{courtois2001achieve} mostraram como construir um tal esquema de assinatura. Este esquema de assinatura é significativamente mais lento do que os esquemas baseados na fatoração
e no logaritmo discreto, mas tem uma boa redução de segurança, e um algoritmo rápido 
para a verificação da assinatura.

Depois de anos sem atenção, o esquema de McEliece passou a ser estudado pois, ao contrário do RSA
\cite{rsa1978rsa} e das Curvas Elípticas \cite{miller1986ecc}, esse esquema resiste a ataques quânticos baseados no algoritmo de Shor \cite{shor1997poly}. Em particular, acredita-se
que computadores quânticos não são capazes de resolver problemas \cNP-difíceis eficientemente
~\cite{arora2009computational}, 
oferecendo apenas uma melhora quadrática no tempo de busca por uma solução, por exemplo, com
o algoritmo de Grover~\cite{grover1996fast}.
Dessa forma, problemas \cNP-difíceis podem ser bons candidatos a suportar algoritmos criptográficos 
pós-quânticos.
Porém o uso desses problemas deve ser feito com com certo cuidado, pois as classes de complexidade dizem 
respeito à dificuldade dos problemas considerando as suas instâncias mais difíceis, 
podendo ser fácil resolver suas instâncias
típicas~\cite{bogdanov2006average,impagliazzo1995personal}. 

Com os avanços da computação quântica, os principais algoritmos de chave pública em
uso ficam cada vez mais vulneráveis, o que justifica a busca por algoritmos criptográficos
resistentes a ataques quânticos~\cite{chen2016report}. Essa busca dá origem à área chamada Criptografia Pós-Quântica,
que, além de esquemas baseados em códigos corretores de erros, estuda também esquemas baseados em
\emph{hashes},  reticulados, equações quadráticas multivariadas, e isogenias de curvas 
elípticas~\cite{bernstein2009post}.

Os principais esquemas de chave pública baseados em códigos corretores de erros são o de
McEliece~\cite{mceliece1978}
e o de Niederreiter~\cite{niederreiter1986knapsack}.
Os esquemas têm segurança equivalente quando o adversário não tem nenhuma informação sobre a mensagem 
transmitida, ou quando são usadas conversões de segurança como as de Kobara e 
Imai~\cite{kobara2001semantically} para deixar os textos encriptados indistinguíveis de
textos aleatórios mesmo contra ataques adaptativos de texto encriptado escolhido
 (IND-CCA2)~\cite{bellare1998relations}.
Tanto por ser mais antigo quanto por ser mais facilmente descrito, os resultados
apresentados nas próximas seções são baseados no esquema de McEliece.


No esquema de McEliece, a chave secreta de Alice é um código linear $\mathcal{C}$ com
capacidade de
correção de $t$ erros para o qual Alice conhece um decodificador eficiente. A chave pública de Alice,
é uma matriz geradora de $\mathcal{C}$, possivelmente embaralhada de forma que seja difícil usá-la para
recuperar um decodificador para $\mathcal{C}$. Para enviar uma mensagem $\vec{m}$ a Alice,
codifique $\vec{m}$ usando a chave pública de Alice e adicione $t$ erros à codificação, obtendo $\vec{c}$. Então Alice, que
é a única portadora de um decodificador eficiente para $\mathcal{C}$, decodifica $\vec{c}$ e
obtém $\vec{m}$.

Uma das principais linhas de pesquisa em criptografia com códigos corretores de erros é diminuir o 
tamanho das chaves do esquema de McEliece através da escolha adequada da família de códigos associada.
Originalmente, McEliece sugeriu o uso de códigos de Goppa~\cite{goppa1970new,berlekamp1973goppa} 
binários e irredutíveis, que, apesar de não sofrerem ataques críticos, resultam em grandes chaves. O 
motivo principal por que códigos de Goppa, de taxa\footnote{A taxa de um código linear de dimensão $k$
e comprimento $n$ é igual a $k/n$.}
não muito alta~\cite{faugere2013distinguisher}, ainda resistem aos ataques é que não se conhece 
algoritmo eficiente para distinguir matrizes geradoras de códigos de Goppa de matrizes 
geradoras de códigos aleatórios.
Algumas outras famílias de códigos foram propostas, como as dos códigos BCH quase 
cíclicos~\cite{gaborit2005shorter},
alternantes quase cíclicos~\cite{berger2009reducing}, LDPC (\emph{low-density parity-check})~\cite{shokrollahi2000using} , e 
de Goppa quase diádicos~\cite{misoczki2009compact}. Apesar de obterem uma boa redução do 
comprimento da chave,
todas foram mostradas inseguras depois de alguns anos~\cite{otmani2010cryptanalysis, faugere2010algebraic, faugere2016structural}.

Em 2013, foi proposta por Misoczki et al.~\cite{misoczki2013mdpc} uma nova variante do Esquema de McEliece, chamada QC-MDPC McEliece
que usa códigos que possuem uma matriz de paridade quase cíclica e de densidade moderada, do inglês
\emph{quasi-cyclic moderate-density parity-check codes} (QC-MDPC).
Esta variante promete chaves públicas de 4801 bits
para um nível de segurança de 80 bits, e tem uma boa redução de segurança.
A iniciativa europeia PQCRYPTO, para o desenvolvimento de criptografia pós-quântica,
na revisão de 2015 de seu documento com recomendações de esquemas pós-quânticos~\cite{augot16initial},
considerou esse esquema como um forte candidato,
junto com a variante Stehlé-Steinfeld~\cite{stehle2011making} do
esquema NTRU~\cite{hoffstein1998ntru}, a ser um padrão adotado por aplicações
com alto nível de segurança.


Até meados de 2016, o QC-MDPC McEliece não sofrera ataques críticos. Porém, na Asiacrypt de 2016,
Guo, Johansson, e Stankovski~\cite{guo2016key} mostraram um ataque eficiente para a
recuperação de chave contra esse esquema. O ataque se baseia no fato de 
que os decodificadores
de códigos QC-MDPC são iterativos e podem falhar, e, quando isso ocorre, o destinatário pede para o 
remetente
reenviar a mensagem com outro erro inserido. O ataque é classificado como um ataque de 
reação~\cite{hall1999reaction} pois o atacante precisa saber como Alice, a portadora da chave secreta,
reage para cada texto encriptado enviado. A observação dos autores é que
a probabilidade de o decodificador falhar para um erro $\vec{e}$ é significativamente menor quando
$\vec{e}$ e a chave secreta compartilham certas propriedades, chamadas de espectros.

Suponha que uma atacante Eva queira atacar Alice. O ataque tem duas fases. Na primeira, Eva gera uma 
grande quantidade de textos encriptados e os envia para Alice, gravando quais encriptados Alice
conseguiu e quais não conseguiu decodificar. Usando estas informações, Eva tenta então estimar o
espectro da chave secreta de Alice. Na segunda fase, sem mais se comunicar com Alice, 
Eva usa as informações coletadas sobre a chave secreta para reconstruí-la.

% A chave secreta do esquema QC-MDPC McEliece é um vetor de $n$ posições e peso $w$, denotado por
% $\vec{h}$. É útil considerar que a chave é subdividida em blocos de forma
% $\vec{h} = [\vec{h}_0 | \vec{h} $. Porém
% basta descobrir a primeira metade de $\vec{h}$, denotado por $\vec{h}_0$, e usar a chave pública para recuperar
% a chave secreta, como pode ser visto na Seção~\ref{cap:mdpc}. O ataque de reação recupera o conjunto
% de distâncias circulares entre entradas não nulas de $\vec{h}_0$, chamado seu espectro, e usa esse 
% espectro para reconstruir a chave. 

\section{Motivação}
\label{sec:intro_motiv}
Foram identificados três problemas do algoritmo de reconstrução que Guo et al. sugerem
para a segunda fase de seu ataque, destacados a seguir.
\begin{enumerate}
    \item Para que o algoritmo funcione eficientemente, o espectro estimado pela primeira
fase tem que estar quase totalmente correto. Segundo os autores, para o nível de segurança de 80 
bits, isso em geral é possível fazendo-se  em torno de 200 milhões de testes de decodificação na 
primeira fase.
    \item O algoritmo não escala bem para níveis de segurança mais altos. Pela sua análise
    assintótica, e pelos nossos experimentos, parece impraticável usá-lo para o nível de segurança de 
    256 bits. Sua complexidade envolve um expoente que cresce, embora não rapidamente, em função
    do nível de segurança.

    \item O algoritmo tem natureza recursiva, e não é fácil escolher uma boa estratégia de 
    paralelização. Em outras palavras, certas estratégias de paralelização são boas para certas 
    chaves, mas não há como saber a priori como quais estratégias obtêm melhores
    \emph{speedups} ao permitir o uso de mais processadores.
\end{enumerate}

Encontrar algoritmos mais eficientes para a reconstrução de chave a partir do espectro é importante
para estimar qual a vida útil de uma chave do esquema QC-MDPC McEliece, ou mesmo
quais parâmetros de segurança desse esquema são seguros contra esse ataque de reação.

\section{Objetivo}

O objetivo deste trabalho é melhorar o ataque de reação de Guo et al.~\cite{guo2016key}
contra o QC-MDPC  McEliece. Para isso, foram considerados algoritmos que possibilitam reconstruir
a chave com um menor número de testes de decodificação, isto é, observando um menor número de 
reações, e também em algoritmos que reconstruam a chave em um menor número de passos do que o
algoritmo propostos por Guo et al. Para avaliar os algoritmos propostos, 
foram feitas tanto as análises probabilísticas assintóticas dos 
algoritmos quanto a dos seus desempenho na prática, usando implementações em linguagem C.

\section{Trabalhos relacionados}
Destacam-se dois trabalhos relacionados, ambos apresentados em conferências de 2017,
que também se basearam no ataque de reação de Guo et al.~\cite{guo2016key}.

O primeiro é um trabalho apresentado na
conferência PQCRYPTO por Fab{\v{s}}i{\v{c}} et al.\cite{fabvsivc2017reaction}
que estende o ataque de reação para o QC-LDPC McEliece. Este ataque usa um algoritmo 
de reconstrução de chave diferente do de Guo et al. modelando o espectro 
como um grafo esparso e buscando cliques de certo tamanho neste grafo.
Apesar de ser uma nova interpretação, a complexidade do algoritmo não 
parece ser significativamente diferente da do algoritmo original de Guo et al.. 

O segundo é um trabalho apresentado na conferência CHES por Rossi et al.~\cite{rossi2017side}, 
que mostra um ataque por canal lateral a uma implementação do QC-MDPC McEliece, 
chamada QcBits~\cite{chou2016qcbits}. Depois de recuperar a informação sobre a chave usando um canal 
lateral, os autores mostraram como recuperar a chave usando uma relação linear entre os
blocos da chave privada. Este trabalho tem certas similaridades com o nosso, 
em particular com um dos nossos algoritmos propostos. Porém, nosso algoritmo é
significativamente diferente, sendo eficiente mesmo com menos informação
sobre o espectro. Além disso, nossas análises teórica e prática do desempenho do algoritmo de reconstrução são mais detalhadas. Note que o foco do trabalho
de Rossi et al. era mostrar um ataque ao QcBits por canal lateral, então é natural que 
a ênfase não tenha sido dada ao algoritmo de reconstrução.

\section{Contribuições originais}

Este trabalho apresenta duas contribuições originais.
Ambas são algoritmos para a reconstrução
da chave secreta a partir do espectro, que são mais eficientes, tanto assintoticamente quanto 
na prática, do que as apresentadas por Guo et al. Os dois algoritmos apresentados
podem ser paralelizáveis trivialmente.

O primeiro algoritmo apresentado é uma simples
extensão probabilística do algoritmo de Guo et al.. Apesar de simples, ele
é bem mais eficiente do que o algoritmo original. Um fato observado ilustrativo disso é que,
quando há informação completa sobre o espectro,
o algoritmo proposto faz menos operações para o nível
de segurança de 256 bits do que o original faz para o nível de 80 bits.
Mesmo assim, o algoritmo não é capaz de trabalhar eficientemente com baixa quantidade de informação
sobre o espectro.

O segundo algoritmo, que é a principal contribuição deste trabalho,
é significativamente diferente do algoritmo de Guo et al., usando uma
relação linear entre os componentes da chave secreta. Mesmo com 
uma quantidade de informação entre $50$ e $55\%$ menor do que o necessário para
o funcionamento do algoritmo de Guo et al., o algoritmo tem complexidade
$\mathcal{O}\left(r^4\right)$. 
Esta complexidade é uma melhora significativa em relação aos expoentes crescentes em função do nível 
de segurança do algoritmo original de Guo et al. e também do algoritmo probabilístico de busca.
A proposta desse algoritmo foi submetido à revista \emph{Transactions on Fundamentals of Electronics, 
Communications and Computer Sciences} do IEICE~\cite{paiva2018improving}.
