%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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

\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{Proposta de Minicurso para a SBSeg 2016} \\ [25pt]
%\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge Criptografia Pós-Quântica \\ Baseada em \\ Códigos Corretores de Erros \\ [25pt]
%\horrule{1pt} \\[0.5cm] % Thick bottom horizontal rule
}


\author{
  Gervásio Santos\\
  IME-USP\\
  \texttt{gervasio@ime.usp.br}
  \and
  Routo Terada\\
  IME-USP\\
  \texttt{rt@ime.usp.br}
  \and
  Thales Paiva\\
  IME-USP\\
  \texttt{tpaiva@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

\tableofcontents

\section{Dados Gerais}

\subsection{Objetivo e Justificativa}

Nosso objetivo é apresentar duas variantes do esquema de McEliece \cite{mceliece1978}, propostas 
por Misoczki em sua tese de doutorado \cite{rafael2013phd}, tratando com cuidado da teoria necessária
para a sua compreensão.
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 no processo de encriptação \cite{menezes1996handbook}.  
Tanto a encriptação quanto a decriptação são computacionalmente mais eficientes que as respectivas
de outros criptossistemas baseados no problema do logaritmo discreto. Apesar disso, o tamanho da chave
pública entre centenas e milhares de quilobytes faz com que esse sistema seja pouco utilizado.

Depois de anos sem atenção, o esquema de McEliece passa a ser estudado pois, ao contrário do RSA
\cite{rsa1978rsa} e das Curvas Elípticas \cite{miller1986ecc}, esse sistema resiste a ataques quânticos 
baseados no algoritmo de Peter Shor \cite{shor1997poly}. 
Com os principais algoritmos de chave pública em uso ficando cada vez mais vulneráveis 
com os avanços em computação quântica, justificam-se as buscas por algoritmos criptográficos 
resistentes a ataques quânticos, dando origem à área chamada Criptografia Pós-Quântica.

Uma das linhas de pesquisa em criptografia pós-quântica é diminuir o tamanho das chaves
originais 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 resultam em grandes chaves. 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}, e códigos LDPC 
\cite{shokrollahi2000using}. Apesar de obterem uma boa redução do comprimento da chave, 
as duas primeiras foram mostradas inseguras alguns anos depois 
\cite{otmani2010cryptanalysis, faugere2010algebraic}, e os próprios autores da terceira proposta
explicam por que ela é vulnerável.

Duas propostas de famílias de códigos associadas ao esquema de McEliece, que obtêm chave pública compacta, e
não mostradas inseguras, foram feitas por Misoczki em sua tese de doutorado \cite{rafael2013phd}.
A primeira é a dos Códigos de Goppa quase $p$-ádicos, e a segunda é a dos 
códigos com matriz de verificação de paridade de densidade moderada (MDPC).

Em 2013, no XII Simpósio Brasileiro em Segurança da Informação e de Sistemas Computacionais, 
Barreto, Biasi, Piazza, e Dahab, apresentaram um minicurso introdutório sobre criptografia pós-quântica
\cite{barreto2013introduccao}. Nesse minicurso, dentre os vários aspectos de criptografia pós-quântica,
são apresentados superficialmente os esquemas de criptografia baseados em códigos corretores de erros
na seção 2.4. Então, em relação a esse texto, nossa proposta é aprofundar essa seção.

\subsection{Tratamento dado ao tema}

Nosso tratamento será fundamentalmente teórico, mas apoiado por código em 
SageMath \cite{stein2008sage}, desenvolvido pelos autores, que será disponibilizado 
num repositório online.

Para que se possa entender o esquema de McEliece, são essenciais alguns resultados de
álgebra e teoria de códigos. Assim, nas primeiras seções fazemos uma revisão desses 
conceitos. E depois, introduzimos os códigos de Goppa, seus algoritmos de codificação e decodificação,
com as suas devidas demonstrações.

Com todos os pré-requisitos já preenchidos, definimos o criptossistema de McEliece, e fazemos a sua redução de
segurança. Mostramos os tamanhos das chaves e comparamos com as repectivas do RSA e de curvas elípticas,
para um mesmo nível de segurança.

Apresentamos em uma seção a proposta dos códigos de Goppa quase $p$-ádicos, para diminuir as chaves.
Duas seções são dedicadas à apresentação de famílias de códigos sem estrutura algébrica,
os LDPC e os MDPC. Os LDPC são provados como inseguros, e mostramos como os códigos MDPC possuem 
algumas vantagens dos LDPC, mas se mantêm seguros contra ataques algébricos.

Finalmente, uma seção de conclusão mostra as comparações entre os códigos apresentados, com relação à
complexidade das operações de codificação e decodificação. Também comparamos os criptossistemas apresentados
com o RSA e curvas elípticas com relação ao tamanho das chaves, segurança esperada, e complexidade das
operações de encriptação e decriptação. 

\subsection{Perfil dos alunos}
  
Estudantes de Ciência da Computação com conhecimentos básicos de álgebra e estudantes de Matemática com 
familiaridade com algoritmos e Complexidade. 

\section{Estrutura prevista do texto}

A estrutura prevista e os números esperados de páginas em cada seção são dados a seguir.
\begin{itemize}[noitemsep]
  
  \item[1] Introdução (5 páginas)
  \item[2] Preliminares (12 páginas)
  \begin{itemize}
    \item[2.1] Corpos Finitos
    \item[2.2] Códigos Lineares
  \end{itemize}
  \item [3] Códigos de Goppa (10 páginas)
  \begin{itemize}
    \item[3.1] Definição
    \item[3.2] Resultados
    \item[3.3] Codificação
    \item[3.4] Decodificação
  \end{itemize}
  \item[4] Criptossistema de McEliece (6 páginas)
  \begin{itemize}
    \item[4.1] Definição
    \item[4.2] Redução de segurança
    \item[4.3] Sobre a segurança do esquema
  \end{itemize}
  \item[5] Códigos de Goppa quase $p$-ádicos (11 páginas)
  \begin{itemize}
    \item[5.1] Definição
    \item[5.2] Codificação
    \item[5.3] Decodificação
    \item[5.4] Ataque e Defesa
  \end{itemize}
  \item[6] Códigos LDPC (5 páginas)
  	\begin{itemize}
		\item[6.1] Definições
        \item[6.2] Codificação e Decodificação
        \item[6.3] Fraquezas e Vulnerabilidades
	\end{itemize}
  \item[7] Códigos MDPC (7 páginas)
  \begin{itemize}
    \item[7.1] Definição
    \item[7.2] Codificação e Decodificação
    \item[7.3] Resultados
  \end{itemize}
  \item[8] Conclusão (3 páginas)
\end{itemize}

\emph{Total aproximado de páginas}: 59 páginas


\section{Resumo e bibliografia de cada seção}


\subsection{Introdução}

Será introduzido o conceito de criptografia pós-quântica, justificando a sua 
importância, e citando alguns dos sistemas existentes \cite{bernstein2009post}. 
Então, fazemos uma introdução informal
sobre os códigos corretores de erros, e mostramos como a Criptografia pode fazer uso deles.

\subsection{Preliminares}

São apresentados os fundamentos matemáticos necessários para 
o entendimento dos algoritmos e teoremas relacionados ao 
Criptossistema de McEliece. Para cada área apresentaremos 
as principais definições e teoremas, bem como provas selecionadas para 
os mais importantes. Nos baseamos principalmente em \cite{fraleigh2003first} para a parte de 
Corpos Finitos, e \cite{van2012introduction} para a de Teoria de Códigos.
A divisão da seção é dada a seguir.

\begin{enumerate}[noitemsep]
	\item[1] Teoria de Corpos Finitos (6 páginas)
    \item[2] Códigos Lineares (6 páginas)
\end{enumerate}

\subsection{Códigos de Goppa}

É apresentada a família dos códigos lineares de Goppa \cite{goppa1970new}, e mostrados os principais
resultados sobre, seguindo a exposição em \cite{engelbert2007summary}. Primeiro apresentamos códigos
gerais, mas nos aprofundamos em códigos de Goppa binários e irredutíveis. Mostramos os algoritmos 
de codificação e decodificação, demonstrando a sua corretude, e discutimos aspectos de implementação
\cite{biswas2008mceliece}. 
A divisão da seção é dada a seguir.

\begin{enumerate}[noitemsep]
	\item[1] Definição (3 páginas)
    \item[2] Resultados (3 páginas)
    \item[3] Codificação (1 página)
    \item[4] Decodificação (3 páginas)
\end{enumerate}

\subsection{Criptossistema de McEliece}

Nesta seção, será introduzido o esquema criptográfico de chave pública proposto por McEliece 
\cite{mceliece1978}. Nossa exposição será baseada em \cite{bernstein2009post, bernstein2008attacking},
e discutimos detalhes práticos de implementação. Mostramos a sua redução de segurança
\cite{berlekamp1978inherent} e fazemos uma pequena análise de sua sua segurança, 
nos baseando nos trabalhos \cite{bernstein2008attacking} \cite{canteaut1998cryptanalysis}.  
A divisão da seção é dada a seguir.

\begin{enumerate}[noitemsep]
	\item[1] Definição (2 páginas)
  \item[2] Redução de segurança (2 páginas)
  \item[3] Sobre a segurança do esquema (2 páginas)
\end{enumerate}

\subsection{Códigos de Goppa quase $p$-ádicos}

É apresentada a classe dos Códigos de Goppa quase $p$-ádicos para a redução de chave pública no 
criptossistema de McEliece \cite{rafael2013phd} \cite{misoczki2009compact}. Mostramos a sua
definição e explicitamos como contruí-los. A exposição 
seguirá a de \cite{rafael2013phd}. Citamos o ataque por criptanálise
algébrica \cite{faugere2010algebraic}, e mostramos a sugestão de defesa contra esse ataque. Consideramos
aspectos de implementação \cite{heyse2011implementation}.
A divisão da seção é dada a seguir.

\begin{enumerate}[noitemsep]
   	\item[1] Definição (3 páginas)
    \item[2] Codificação (1 página)
    \item[3] Decodificação (2 páginas)
    \item[4] Ataque e Defesa (5 páginas)
\end{enumerate}

\subsection{Códigos LDPC}

É apresentada a classe dos códigos lineares cujas matrizes de verificação 
de paridade têm baixa densidade (\emph{Low Density Parity Check Matrix}). 
Apresentamos a interpretação desses códigos como grafos esparsos e seus algoritmos de codificação e 
decodificação seguindo as apresentações em \cite{gallager1962low} \cite{rafael2013phd}.
Ao final, mostramos as vulnerabilidades criptográficas dessa família \cite{shokrollahi2000using}.
A divisão da seção é dada a seguir.
\begin{enumerate}[noitemsep]
    	\item[1] Definições (1 página)
    \item[2] Codificação e Decodificação (2 páginas)
    \item[3] Vulnerabilidades (2 páginas)
\end{enumerate}


\subsection{Códigos MDPC}

São apresentados os códigos lineares cuja matriz de verificação de
paridade tem densidade moderada (\emph{Moderate Density Parity Check Matrix})
\cite{misoczki2013mdpc} e os comparamos com os códigos LDPC. Mostramos como códigos MDPC não
sofrem da mesma vulnerabilidade que os LDPC, e discutimos por que parecem ser uma alternativa melhor
do que os códigos de Goppa, já que não têm estrutura algébrica. Explicamos como seu uso no esquema de McEliece permite 
chaves bastante reduzidas, competitivas com as
do RSA. A apresentação segue \cite{misoczki2013mdpc} e \cite{rafael2013phd}. Consideramos detalhes de 
implementação \cite{maurich2015implementing}.
\begin{itemize}[noitemsep]
	\item[1] Definição (2 páginas)
  \item[2] Codificação e Decodificação (1 página)
	\item[3] Resultados (4 páginas)
\end{itemize}

\section{Biografias dos Autores}

\subsection{Routo Terada}

Possui graduação em Engenharia Elétrica Eletrônica pela Universidade de São Paulo
(1970), mestrado em Matemática Aplicada pela Universidade de São Paulo (1975) e
doutorado em Ciência da Computação - University of Wisconsin - Madison (1979). Atualmente
é professor titular da Universidade de São Paulo, avaliador de artigos do International
Journal of Information Security e do Journal of the Brazilian Computer Society. Tem
experiência na área de Ciência da Computação, com ênfase em Criptografia, atuando
principalmente nos seguintes temas: segurança de dados, criptografia, algoritmos,
criptossistemas e mathematical morphology.

\subsection{Thales Paiva (Apresentador)}

Mestrando em Ciência da Computação pelo Instituto de Matemática e Estatística da
Universidade de São Paulo sob a orientação do Professor Routo Terada. Bacharel em 
Ciência da Computação pelo mesmo instituto. Tem interesse nas áreas de Teoria de 
Informação, Criptografia, Teoria de Códigos, e Teoria de Complexidade.

\subsection{Gervásio Santos (Apresentador)}

Graduando em Ciência da Computação pelo Instituto de Matemática e Estatística da
Universidade de São Paulo. Foi aluno de inciação científica na área de Criptografia e Teoria dos Números sob a orientação do Professor Routo Terada. Tem interesse nas áreas de Criptografia, Teoria de Códigos, Álgebra Abstrata, e Teoria da Complexidade.


\bibliography{biblio}{}

\end{document}