% Arquivo LaTeX de exemplo de dissertação/tese a ser apresentados à CPG do IME-USP
%
% Versão 5: Sex Mar  9 18:05:40 BRT 2012
%
% Criação: Jesús P. Mena-Chalco
% Revisão: Fabio Kon e Paulo Feofiloff
%
% Obs: Leia previamente o texto do arquivo README.txt

\documentclass[11pt,twoside,a4paper]{book}

% ---------------------------------------------------------------------------- %
% Pacotes
%\usepackage[brazil]{babel}
%\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[brazilian]{babel}
\usepackage[utf8]{inputenc}
\usepackage[pdftex]{graphicx}           % usamos arquivos pdf/png como figuras
\usepackage{setspace}                   % espaçamento flexível
\usepackage{indentfirst}                % indentação do primeiro parágrafo
\usepackage{makeidx}                    % índice remissivo
\usepackage[nottoc]{tocbibind}          % acrescentamos a bibliografia/indice/conteudo no Table of Contents
% \usepackage{lmodern}
\usepackage{mathpazo}
\usepackage{type1cm}                    % fontes realmente escaláveis
\usepackage{listings}                   % para formatar código-fonte (ex. em Java)
\usepackage{titletoc}
%\usepackage[bf,small,compact]{titlesec} % cabeçalhos dos títulos: menores e compactos
%\usepackage{lmodern}
\usepackage[fixlanguage]{babelbib}
\usepackage[font=small,format=plain,labelfont=bf,up,textfont=it,up]{caption}
\usepackage[usenames,svgnames,dvipsnames]{xcolor}
\usepackage[a4paper,top=2.54cm,bottom=2.0cm,left=2.0cm,right=2.54cm]{geometry} % margens
%\usepackage[pdftex,plainpages=false,pdfpagelabels,pagebackref,colorlinks=true,citecolor=black,linkcolor=black,urlcolor=black,filecolor=black,bookmarksopen=true]{hyperref} % links em preto
\usepackage[pdftex,plainpages=false,pdfpagelabels,pagebackref,colorlinks=true,citecolor=DarkGreen,linkcolor=NavyBlue,urlcolor=DarkRed,filecolor=green,bookmarksopen=true]{hyperref} % links coloridos
\usepackage[section]{placeins}
\usepackage{url}
\usepackage[all]{hypcap}                % soluciona o problema com o hyperref e capitulos
\usepackage[square,sort,nonamebreak,comma]{natbib}  % citação bibliográfica alpha (alpha-ime.bst)
\usepackage{amsmath,amsfonts,amsthm,mathtools}

% Meus pacotinhos
\usepackage{chngcntr}
\counterwithout{footnote}{chapter}
\usepackage{xspace}
\usepackage{indentfirst}
\usepackage{placeins}
\usepackage{tikz}
\usetikzlibrary{positioning,chains,fit,shapes,calc,decorations.pathreplacing,angles,quotes}

\usepackage{multirow}
\usepackage{booktabs}

\usepackage{mdframed}
\usepackage{pgfgantt}
\usepackage{qtree}

\usepackage[portuguese, ruled, linesnumbered, noend]{algorithm2e}
\usepackage{etoolbox}
\AtBeginEnvironment{algorithm}{\linespread{1.20}\selectfont}

\SetAlgoNoEnd{}
\newlength\mylen\newcommand\myinput[1]{%
  \settowidth\mylen{\Entrada{}}%
  \setlength\hangindent{\mylen}%
  \hspace*{\mylen}#1\\}

\usepackage{floatrow}
\newfloatcommand{capbtabbox}{table}[][\FBwidth]
\fontsize{60}{62}\usefont{OT1}{cmr}{m}{n}{\selectfont}


\newcommand{\myparagraph}[1]{\paragraph{#1}\mbox{}\\}

% ---------------------------------------------------------------------------- %
% Cabeçalhos similares ao TAOCP de Donald E. Knuth
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancyhf{}
\renewcommand{\chaptermark}[1]{\markboth{\MakeUppercase{#1}}{}}
\renewcommand{\sectionmark}[1]{\markright{\MakeUppercase{#1}}{}}
\renewcommand{\headrulewidth}{0pt}


\usepackage{amssymb}
\let\oldemptyset\emptyset
\let\emptyset\varnothing


% ---------------------------------------------------------------------------- %
\graphicspath{{./figuras/}}             % caminho das figuras (recomendável)
\frenchspacing                          % arruma o espaço: id est (i.e.) e exempli gratia (e.g.)
\urlstyle{same}                         % URL com o mesmo estilo do texto e não mono-spaced
\makeindex                              % para o índice remissivo
\raggedbottom                           % para não permitir espaços extra no texto
\fontsize{60}{62}\usefont{OT1}{cmr}{m}{n}{\selectfont}
\cleardoublepage
\normalsize

% ---------------------------------------------------------------------------- %
% Opções de listing usados para o código fonte
% Ref: http://en.wikibooks.org/wiki/LaTeX/Packages/Listings
\lstset{ %
  language=Java,                  % choose the language of the code
  basicstyle=\footnotesize,       % the size of the fonts that are used for the code
  numbers=left,                   % where to put the line-numbers
  numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
  stepnumber=1,                   % the step between two line-numbers. If it's 1 each line will be numbered
  numbersep=5pt,                  % how far the line-numbers are from the code
  showspaces=false,               % show spaces adding particular underscores
  showstringspaces=false,         % underline spaces within strings
  showtabs=false,                 % show tabs within strings adding particular underscores
  frame=single,	                % adds a frame around the code
  framerule=0.6pt,
  tabsize=2,	                    % sets default tabsize to 2 spaces
  captionpos=b,                   % sets the caption-position to bottom
  breaklines=true,                % sets automatic line breaking
  breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
  escapeinside={\%*}{*)},         % if you want to add a comment within your code
  backgroundcolor=\color[rgb]{1.0,1.0,1.0}, % choose the background color.
  rulecolor=\color[rgb]{0.8,0.8,0.8},
  extendedchars=true,
  xleftmargin=10pt,
  xrightmargin=10pt,
  framexleftmargin=10pt,
  framexrightmargin=10pt
}

% \newtheorem{thm}{Theorem}[section]
% \newtheorem{cor}[thm]{Corollary}
% \newtheorem{lem}[thm]{Lemma}
% \newtheorem{prob}[thm]{Problem}
% \theoremstyle{definition}
% \newtheorem{defin}[thm]{Definition}
% \newtheorem{rem}[thm]{Remark}
% \newtheorem{exa}[thm]{Example}
%

\newtheorem{theorem}{Teorema}[section]
\newtheorem{cor}[theorem]{Corolário}
\newtheorem{lem}[theorem]{Lema}
\newtheorem{prob}[theorem]{Problema}
\newtheorem{prop}{Proposição}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definição}
\newtheorem{remark}[theorem]{Nota}
\newtheorem{example}[theorem]{Exemplo}

% \let\olddefinition\definition
% \renewcommand{\definition}{\olddefinition\normalfont}

\numberwithin{equation}{section}
\numberwithin{figure}{section}
\numberwithin{table}{section}

\input macros


% ---------------------------------------------------------------------------- %
% Corpo do texto
\begin{document}
  \frontmatter
  % cabeçalho para as páginas das seções anteriores ao capítulo 1 (frontmatter)
  \fancyhead[RO]{{\footnotesize\rightmark}\hspace{2em}\thepage}
  \setcounter{tocdepth}{2}
  \fancyhead[LE]{\thepage\hspace{2em}\footnotesize{\leftmark}}
  \fancyhead[RE,LO]{}
  \fancyhead[RO]{{\footnotesize\rightmark}\hspace{2em}\thepage}

  \onehalfspacing  % espaçamento

  % ---------------------------------------------------------------------------- %
  % CAPA
  % Nota: O título para as dissertações/teses do IME-USP devem caber em um
  % orifício de 10,7cm de largura x 6,0cm de altura que há na capa fornecida pela SPG.
  \thispagestyle{empty}
  \begin{center}
    \vspace*{2.3cm}
    \textbf{\Large{Melhorando o ataque de reação \\ contra o QC-MDPC McEliece}}\\

    \vspace*{1.2cm}
    \Large{Thales Areco Bandiera Paiva}

    \vskip 2.0cm
    \textsc{
      Dissertação apresentada \\[-0.25cm]
        ao \\[-0.25cm]
      Instituto de Matemática e Estatística \\[-0.25cm]
        da \\[-0.25cm]
      Universidade de São Paulo \\[-0.25cm]
        para \\[-0.25cm]
      obtenção do título \\[-0.25cm]
        de \\[-0.25cm]
      Mestre em Ciências
    }

    \vskip 1.5cm
    Programa: Ciência da Computação \\
    Orientador: Prof. Dr. Routo Terada \\

   	\vskip 1cm
    \normalsize{Durante o desenvolvimento deste trabalho o autor recebeu auxílio
    financeiro da CAPES}

    \vskip 0.5cm
    \normalsize{São Paulo, fevereiro de 2018}
  \end{center}

  \newpage
  \thispagestyle{empty}
  \mbox{}
  %    \begin{center}
  %        \vspace*{2.3 cm}
  %        \textbf{\Large{Melhorando o ataque de reação \\ contra o QC-MDPC McEliece}}\\
  %        \vspace*{2 cm}
  %    \end{center}

  %    \vskip 2cm


  %   % \begin{flushright}
    %   Esta é a versão original da dissertação elaborada pelo\\
    %   candidato Thales Areco Bandiera Paiva, tal como \\
    %   submetida à Comissão Julgadora.
    % \end{flushright}
    %      \vskip 4.2cm

    %  % \begin{quote}
     % \noindent Comissão Julgadora:

    %  Titulares:
    %  \begin{itemize}
  		% \item Prof. Dr. Routo Terada (orientador) - IME-USP  % [sem ponto final]
    %     \item Prof. Dr Jairo Zacarias Gonçalves - IME-USP
  		% \item Prof. Dr. Marcos Antonio Simplicio Junior - EP-USP % [sem ponto final]
    %  \end{itemize}


    %  Suplentes:
    %  \begin{itemize}
    %     \item Profa. Dra. Kelly Rosa Braghetto - IME-USP  % [sem ponto final]
    %     \item Profa. Dra. Denise Hideko Goya - CMCC-UFABC % [sem ponto final]
    %     \item Prof. Dr. Denis Deratani Mauá - IME-USP % [sem ponto final]
    %  \end{itemize}
    %  \end{quote}
  % \pagebreak
% ---------------------------------------------------------------------------- %
% Página de rosto (SÓ PARA A VERSÃO DEPOSITADA - ANTES DA DEFESA)
% Resolução CoPGr 5890 (20/12/2010)
%
% IMPORTANTE:
%   Coloque um '%' em todas as linhas
%   desta página antes de compilar a versão
%   final, corrigida, do trabalho
%
%
% \newpage
% \thispagestyle{empty}
%     \begin{center}
%         \vspace*{2.3 cm}
%         \textbf{\Large{Título do trabalho a ser apresentado à \\
%         CPG para a dissertação/tese}}\\
%         \vspace*{2 cm}
%     \end{center}

%     \vskip 2cm

%     \begin{flushright}
%   Esta é a versão original da dissertação/tese elaborada pelo\\
%   candidato (Nome Completo do Aluno), tal como \\
%   submetida à Comissão Julgadora.
%     \end{flushright}

% \pagebreak


% Página de rosto (SÓ PARA A VERSÃO CORRIGIDA - APÓS DEFESA)
% Resolução CoPGr 5890 (20/12/2010)

% Nota: O título para as dissertações/teses do IME-USP devem caber em um
% orifício de 10,7cm de largura x 6,0cm de altura que há na capa fornecida pela SPG.

% IMPORTANTE:
%   Coloque um '%' em todas as linhas desta
%   página antes de compilar a versão do trabalho que será entregue
%   à Comissão Julgadora antes da defesa


\newpage
\thispagestyle{empty}
    \begin{center}
        \vspace*{2.3 cm}
        \textbf{\Large{Melhorando o ataque de reação \\ contra o QC-MDPC McEliece}}\\
        \vspace*{2 cm}
    \end{center}

    \vskip 2cm

    \begin{flushright}
    Esta versão da dissertação contém as correções e alterações sugeridas\\
    pela Comissão Julgadora durante a defesa da versão original do trabalho,\\
    realizada em 11/12/2017. Uma cópia da versão original está disponível no\\
    Instituto de Matemática e Estatística da Universidade de São Paulo.

    \vskip 2cm

    \end{flushright}
    \vskip 4.2cm

    \begin{quote}
    \noindent Comissão Julgadora:

    \begin{itemize}
    \item Prof. Dr. Routo Terada (orientador) - IME-USP
    \item Profa. Dra. Denise Hideko Goya- CMCC-UFABC
    \item Prof. Dr. Marcos Antonio Simplício Junior - EP-USP
    \end{itemize}

    \end{quote}
\pagebreak



\newpage
\thispagestyle{empty}
\mbox{}
\pagebreak

\newpage
% \thispagestyle{empty}

\pagenumbering{roman}     % começamos a numerar



% ---------------------------------------------------------------------------- %

% Agradecimentos:
% Se o candidato não quer fazer agradecimentos, deve simplesmente eliminar esta página 
\chapter*{Agradecimentos}

Primeiramente gostaria de agradecer ao Professor Routo, com quem aprendi muito.
Foi um prazer trabalhar com você.
Agradeço aos professores Denise, Marcos, e Jairo, pelas ideias, comentários, e boas
discussões sobre o trabalho. Agradeço ao Professor Alfredo Goldman, meu orientador no fim da graduação,
que me incentivou a fazer o mestrado. Agradeço às professoras Nina, Vera Lúcia, e Leliane, e aos professores Sinai, Gubi, e Roberto Hirata, pelo cuidado e carinho com todos os alunos.
Talvez agradecer aos professores nomeados neste parágrafo seja pouco. Melhor é
fazer o possível para refletir suas qualidades, principalmente no tratamento com os alunos,
no futuro quando eu for professor.

Os amigos Gervásio e Gláucio ajudaram muito com seminários, discussões, e comentários.
Junto com Giulia, Letícia, Samuel, e Victor, foram responsáveis por deixar a vivência no 
IME ainda mais agradável. 

Os nomes da Aline, dos meus pais, Kelsy e Paulo, e irmãos, Caterina e Marcelo, só não estão
na capa porque as normas do IME não permitem.
Continuo aprendendo muito com Augusto, Antônio, Andrei, Bianca, César, Cláudio, Gustavo, Iago, Kaê, Paulo,
Russo, Sílvia, e Stanley. Tenho muita sorte de ter encontrado amigos tão bons.

Alguns dos experimentos deste trabalho foram feitos com o auxílio dos recursos de HPC disponibilizados pela Superintendência de Tecnologia da Informação da Universidade de São Paulo. Agradeço aos administradores, que foram super atenciosos.

Este trabalho é dedicado à Professora Maria Lúcia Diniz, minha grande amiga.



% Resumo
\chapter*{Resumo}

\noindent Paiva, T. A. B. \textbf{Melhorando o ataque de reação contra o QC-MDPC McEliece}. 
2017. Dissertação - Instituto de Matemática e Estatística,
Universidade de São Paulo, São Paulo, 2017.
\\

O QC-MDPC McEliece foi considerado um dos mais promissores esquemas
criptográficos de chave pública que 
oferecem segurança contra ataques por computadores quânticos.
O tamanho das chaves públicas do QC-MDPC McEliece é competitivo
com o das chaves do RSA, e o esquema tem uma redução de segurança aparentemente forte.
Por três anos, o esquema não sofreu ataques críticos, até que na Asiacrypt de 2016
Guo, Johansson, e Stankovski mostraram um ataque de reação contra o QC-MDPC McEliece
que explora um aspecto não considerado em sua redução de segurança:
a probabilidade de o algoritmo de decriptação falhar é menor 
quando a chave secreta e o vetor usado para encriptar a mensagem compartilham certas
propriedades, chamadas de espectros.
Dessa forma, um atacante pode, ao detectar falhas de decriptação,
obter informação sobre o espectro, que será usada para reconstruir a chave secreta.
Guo et al. apresentaram um algoritmo para a reconstrução da chave a partir do espectro
recuperado, para o qual é possível apontar três problemas.
O primeiro é que seu algoritmo não é eficiente quando o espectro da chave não foi recuperado
quase completamente, o que resulta em o atacante ter que enviar um grande número de
testes de decriptação à portadora da chave secreta.
O segundo problema é que o desempenho de seu algoritmo não escala
bem para níveis de segurança mais altos. O terceiro e último problema é
que, por ser baseado numa busca em profundidade, seu algoritmo não pode ser
paralelizado trivialmente.
Para aumentar a eficiência do ataque, dois novos
algoritmos de reconstrução são propostos neste trabalho. Estes algoritmos são mais eficientes, usam
menos informação sobre a chave secreta, e podem ser paralelizados trivialmente.
O primeiro algoritmo é probabilístico e
tem complexidade assintótica ligeiramente melhor do que a do original.
Entretanto, o desempenho do algoritmo probabilístico piora rapidamente,
embora mais lentamente do que o algoritmo de Guo et al.,
conforme a quantidade de informação sobre o espectro diminui. 
O segundo algoritmo explora uma relação linear entre os blocos da chave secreta.
Este é mais eficiente, tanto assintoticamente quanto na prática, 
que os dois outros algoritmos, e é eficiente mesmo com 50\% 
menos informação sobre o espectro do que o necessário para o algoritmo original.
Isso permite que o atacante encontre a chave secreta
fazendo apenas em torno de 20\% do número de
testes necessários pelo algoritmo de Guo's et al., considerando-se o nível de segurança 
de 80 bits.
O desempenho de ambos os algoritmos são analisados e comparados com
o do algoritmo original, e as análises são feitas tanto para a complexidade teórica 
quanto para o desempenho na prática, considerando a implementação dos algoritmos
em linguagem C.
\\

\noindent \textbf{Palavras-chave:} QC-MDPC, criptografia pós-quântica, ataque de reação.

% ---------------------------------------------------------------------------- %
% Abstract
\chapter*{Abstract}
\noindent Paiva, T. A. B. \textbf{Improving the efficiency of the reaction attack on the
QC-MDPC McEliece}. 
2017. Dissertation - Instituto de Matemática e Estatística,
Universidade de São Paulo, São Paulo, 2017.
\\

The QC-MDPC McEliece scheme was considered one of the most
promising public key encryption schemes for efficient post-quantum secure
encryption. As a variant of the McEliece scheme, it is based on the
syndrome decoding problem, an \cNP-hard problem from Coding Theory.
The key sizes are competitive with the ones of the widely used
RSA cryptosystem, and it came with an apparently strong security reduction.
For three years, the scheme has not suffered major threats, until the end of 2016, when Guo, Johansson, and Stankovski presented at Asiacrypt a
reaction attack on the QC-MDPC that exploits one aspect that was not considered
in the security reduction: the probability of a decoding failure to occur
is lower when the secret key and the error used for encryption share certain properties,
which they called spectrums.
By detecting decoding failures, the attacker can obtain information on the
spectrum of the secret key and then use this information to reconstruct the key.
Guo et al. presented an algorithm for key reconstruction
for which we can point three weaknesses.
The first one is that it cannot deal efficiently with partial information on the
spectrum of the secret key, resulting in the
attacker having to send a great number of decoding trials. The second one
is that it does not scale well for higher security levels. The third one is that
the algorithm, which is based on a depth-first search, cannot be trivially parallelized.
To improve the efficiency of the attack, we propose two different key reconstruction
algorithms that are more efficient, use less information on the secret key,
and can be trivially parallelized. The first algorithm, which is
a simple probabilistic extension of Guo's et al. algorithm,
is significantly more efficient than the original one.
However, for security levels higher than 80 bits, the probabilistic 
algorithm cannot run efficiently without too much information on the spectrum of the secret key,
even though it needs less information than the original algorithm.
The second algorithm is based on a linear relation between the blocks of the
secret key. It can run efficiently with around 50\% less information than needed by
Guo's et al. key reconstruction algorithm. This makes it possible for an
attacker to recover the secret key sending approximately 20\% of the
of the number of decoding trials needed by Guo's et al. algorithm, for the security level
of 80 bits.
The performance of each presented algorithm is analyzed and compared with that of the 
original one. The analysis are made theoretically, considering a probabilistic analysis
of the algorithms, and in practice, considering the corresponding implementations in C language.
\\

\noindent \textbf{Keywords:} QC-MDPC, post-quantum cryptography, reaction attack.


% ---------------------------------------------------------------------------- %
% Sumário
\tableofcontents    % imprime o sumário

% ---------------------------------------------------------------------------- %
\chapter{Lista de Abreviaturas}
\begin{tabular}{ll}
  CCA1        & Ataque de texto cifrado escolhido (\emph{chosen-ciphertext attack})\\
  CCA2        & Ataque adaptativo de texto cifrado escolhido (\emph{adaptive chosen-ciphertext attack})\\
  CPA         & Ataque de texto legível escolhido (\emph{chosen-plaintext attack})\\
  LDPC        & Matriz de paridade de baixa densidade (\emph{low-density parity-check})\\
  MDPC        & Matriz de paridade de densidade moderada (\emph{low-density parity-check})\\
  QC          & Quase cíclica, usado em geral para classificar matrizes LDPC ou MDPC \\
\end{tabular}

  % ---------------------------------------------------------------------------- %
  %\chapter{Lista de Símbolos}
  %\begin{tabular}{ll}
  %        $\omega$    & Frequência angular\\
  %        $\psi$      & Função de análise \emph{wavelet}\\
  %        $\Psi$      & Transformada de Fourier de $\psi$\\
  %\end{tabular}

  % ---------------------------------------------------------------------------- %
  % Listas de figuras e tabelas criadas automaticamente
  \listoffigures
  \listoftables

  % ---------------------------------------------------------------------------- %
  % Capítulos do trabalho
  \mainmatter

  % cabeçalho para as páginas de todos os capítulos
  \fancyhead[RE,LO]{\thesection}


  \singlespacing              % espaçamento simples
  %\onehalfspacing            % espaçamento um e meio

    % \input cap-prefacio
    \input cap-introducao
    \input cap-prelim
    \input cap-mdpc
    \input cap-ataque_guo
    \input cap-estima_espectro
    \input cap-variante_probab
    \input cap-ataque_kernel
    \input cap-conclusao
  
  % cabeçalho para os apêndices
  %\renewcommand{\chaptermark}[1]{\markboth{\MakeUppercase{\appendixname\ \thechapter}} {\MakeUppercase{#1}} }
  %\fancyhead[RE,LO]{}
  %\appendix

  %\include{ape-conjuntos}      % associado ao arquivo: 'ape-conjuntos.tex'

  % ---------------------------------------------------------------------------- %
  % Bibliografia
  \backmatter \singlespacing   % espaçamento simples
  \bibliographystyle{alpha-ime}% citação bibliográfica alpha
  \renewcommand\bibname{Referências}
  \bibliography{bibliografia}  % associado ao arquivo: 'bibliografia.bib'

  % ---------------------------------------------------------------------------- %
  % Índice remissivo
  %\index{TBP|see{periodicidade região codificante}}
  %\index{DSP|see{processamento digital de sinais}}
  %\index{STFT|see{transformada de Fourier de tempo reduzido}}
  %\index{DFT|see{transformada discreta de Fourier}}
  %\index{Fourier!transformada|see{transformada de Fourier}}

  %\printindex   % imprime o índice remissivo no documento

\end{document}
