%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Short Sectioned Assignment
% LaTeX Template
% Version 1.0 (5/5/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% Original author:
% Frits Wenneker (http://www.howtotex.com)
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass[paper=a4, fontsize=11pt]{scrartcl} % A4 paper and 11pt font size
\usepackage[left=2cm,right=2cm,top=2.5cm,bottom=2.5cm]{geometry}
\usepackage[brazilian]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amsfonts,amsthm,mathtools} % Math packages
\usepackage{xspace}
\usepackage{indentfirst}
\usepackage{placeins}
\usepackage{hyperref}

\usepackage{enumitem}
\setitemize{noitemsep}

\usepackage{graphicx,subcaption}
\usepackage{float}
\usepackage{amssymb}
\usepackage{tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{positioning}
\usetikzlibrary{calc}

%\usepackage{sectsty} % Allows customizing section commands
%\allsectionsfont{\centering \normalfont\scshape} % Make all sections centered, the default font and small caps

\usepackage{fancyhdr}
\pagestyle{fancyplain}
%\fancyhead{}
\fancyfoot[L]{} % Empty left footer
\fancyfoot[C]{} % Empty center footer
\fancyfoot[R]{\thepage} % Page numbering for right footer
\renewcommand{\headrulewidth}{0pt} % Remove header underlines
\renewcommand{\footrulewidth}{0pt} % Remove footer underlines
\setlength{\headheight}{13.6pt} % Customize the height of the header


\newcommand{\hz}{\ensuremath{\vec{h}_0}\xspace}
\newcommand{\var}[1]{\texttt{\upshape #1}\xspace}
\newcommand{\EE}{\ensuremath{\mathop{\mathbb{E}}}\xspace}

\newcommand{\Fb}{\ensuremath{\mathbb{F}_2}\xspace}
\newcommand{\code}{\ensuremath{\mathcal{C}}\xspace}

\newcommand{\cP}{\ensuremath{\mathcal{P}}}
\newcommand{\cNP}{\ensuremath{\mathcal{NP}}}
\renewcommand{\bar}[1]{\overline{#1}}

\newcommand{\cgbi}{código de Goppa binário e irredutível\xspace}
\newcommand{\goppa}{\ensuremath{\mathcal{G}}\xspace}
\newcommand{\goppair}{\ensuremath{\Gamma(L, g)}\xspace}
\newcommand{\supp}[1]{\ensuremath{\mathcal{T}_{#1}}\xspace}
\newcommand{\wt}{\ensuremath{\text{wt}}\xspace}


\newcommand{\alg}[1]{\ensuremath{\textsc{#1}}}
\newcommand{\sk}{\ensuremath{K_\textsc{Sec}}}
\newcommand{\pk}{\ensuremath{K_\textsc{Pub}}}
\newcommand{\WF}{\ensuremath{\mathbf{WF}}}

\bibliographystyle{apalike}


\usepackage{titlesec}
\titleclass{\subsubsubsection}{straight}[\subsection]

\newcounter{subsubsubsection}[subsubsection]
\renewcommand\thesubsubsubsection{\thesubsubsection.\arabic{subsubsubsection}}
\renewcommand\theparagraph{\thesubsubsubsection.\arabic{paragraph}} % optional; useful if paragraphs are to be numbered

\titleformat{\subsubsubsection}
  {\normalfont\normalsize\bfseries}{\thesubsubsubsection}{1em}{}
\titlespacing*{\subsubsubsection}
{0pt}{3.25ex plus 1ex minus .2ex}{1.5ex plus .2ex}

\DeclareFixedFont{\ttb}{T1}{txtt}{bx}{n}{12} % for bold
\DeclareFixedFont{\ttm}{T1}{txtt}{m}{n}{12}  % for normal


%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------

\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height

\title{
\normalfont \normalsize
\textsc{Resumo para a Qualificação} \\ [25pt]
%\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge{Chaves Compactas para Esquemas Criptográficos \\ Baseados em Códigos Corretores de Erros}\\ [25pt]
%\horrule{1pt} \\[0.5cm] % Thick bottom horizontal rule
}


\author{
    Thales A. B. Paiva\\
    \texttt{tpaiva@ime.usp.br}
    \and
    Routo Terada\\
    \texttt{rt@ime.usp.br}
}

\date{\today} % Today's date or a custom date

\renewcommand{\P}{\mathbb{P}}
\renewcommand{\bar}[1]{\overline{#1}}
\newcommand{\set}[1]{\mathcal{#1}}


\begin{document}


\maketitle % Print the title
\horrule{1pt} \\[0.5cm] % Thick bottom horizontal rule

O esquema de chave pública de McEliece 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.
Tanto a encriptação quanto a decriptação são computacionalmente mais eficientes que as respectivas
de outros esquemas baseados no problema do logaritmo discreto. Além disso, o esquema é baseado no problema
\cNP-difícil da decodificação por síndrome, que é conjecturado tipicamente difícil, e é teoricamente
mais difícil que o problema do logaritmo discreto. Porém, por ter chaves públicas muito grandes, e
ser difícil a construção de um esquema de assinatura sobre ele, o esquema de McEliece recebera
pouca atenção na época de publicação.

Depois de anos sem atenção, o esquema de McEliece passa a ser estudado pois, ao contrário do RSA
e das Curvas Elípticas, esse esquema resiste a ataques quânticos
baseados no algoritmo de Peter Shor.
Com o 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 as buscas por algoritmos criptográficos
resistentes a ataques quânticos. Essa busca dá origem à área chamada Criptografia Pós-Quântica,
que estuda, além de esquemas baseados em códigos corretores de erros, esquemas baseados em \emph{hashes},
reticulados, e equações quadráticas multivariadas.


No esquema de McEliece, a chave secreta de Alice é um código linear $\mathcal{G}$ 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{G}$, possivelmente embaralhada de forma que seja difícil usá-la para
recuperar um decodificador para $\mathcal{G}$. Para mandar uma mensagem $\vec{m}$ a Alice,
codifique $\vec{m}$ usando a chave pública de Alice e adicione $t$ erros à codificação, obtendo $c$. Então Alice, que
é a única portadora de um decodificador eficiente para $\mathcal{G}$, decodifica $c$ e obtém $\vec{m}$.

%\subsection{Escolha da família de códigos}


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 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
não não muito alta, ainda resistem aos ataques é que não se conhece algoritmo eficiente para
distinguir entre matrizes geradoras de códigos de Goppa e 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,
alternantes quase cíclicos, códigos LDPC, e códigos de
Goppa quase diádicos. Apesar de obterem uma boa redução do comprimento da chave,
todas foram mostradas inseguras depois de alguns anos.

Em 2013, uma nova variante do Esquema de McEliece, chamada QC-MDPC McEliece, foi proposta.
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,
considera essa variante como ``sob análise'', junto com a variante Stehlé-Steinfeld do
esquema NTRU.


Até meados de 2016, o QC-MDPC McEliece não sofrera ataques críticos. Porém, na conferência Asiacrypt de 2016,
foi mostrado um ataque de reação eficiente para a
recuperação de chave de um esquema QC-MDPC. O ataque de reação contra o QC-MDPC McEliece 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. 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. Assim, uma atacante pode enviar um grande número de mensagens
encriptadas a Alice de forma a extrair informações que serão usadas para reconstruir a sua chave privada.

Nosso objetivo é melhorar o ataque de reação ao QC-MDPC McEliece para diminuir o número necessário de testes de
decodificação para a recuperação de chave. Obtivemos bons resultados preliminares que sugerem ser
possível atacar eficientemente o esquema usando menos do que a metade dos testes usados no ataque original.
Além disso, estudamos a possibilidade de se atacar novas variantes do QC-MDPC McEliece que usam
decodificadores com menores taxas de falha.



\end{document}
