proposal.tex

\documentclass{ufsctex/ufsctex}

\usepackage[table]{xcolor}
\usepackage{mdframed, enumitem, multirow, hhline, amssymb}

\newcolumntype{P}[1]{>{\centering\arraybackslash}m{#1}}

\newcommand{\thatcell}[3]{
	\multicolumn{#1}{#2}{\cellcolor{lightgray} \textbf{#3}}
}

\begin{document}

\instituicao[a]{Universidade Federal de Santa Catarina}
\departamento[o]{Departamento de Informática e Estatística}
\curso[o]{Programa de Graduação em Ciência da Computação}
\documento[a]{Monografia}
\titulo{Multivariate Public-Key Cryptosystems}
\autor{Matheus Silva Pinheiro Bittencourt}
\grau{Bacharel em Ciência da Computação}
\local{Florianópolis}
\data{12}{Novembro}{2018}
\orientador[Orientador]{Prof.\ Dr.\ Ricardo Felipe Custódio}
\coorientador[Coorientador]{Gustavo Zambonin}
\coordenador[Coordenador]{Prof.\ Dr.\ Rafael Luiz Cancian}

\textoResumo{
Os algoritmos clássicos de assinatura digital como RSA e ECDSA baseiam sua
segurança na dificuldade da fatoração de inteiros, e no logaritmo discreto,
respectivamente. Esses problemas já possuem algoritmos quânticos que os
resolvem em tempo polinomial, ou seja, com computadores quânticos poderosos o
suficiente, o uso dos algoritmos de assinatura digital mais difundidos
tornará-se impraticável. Naturalmente, com o aumento do poder computacional
quântico, o interesse por criptossistemas resistentes a ataques que utilizam-se
de tais computadores também cresceu. A área que estuda esses criptossistemas é,
portanto, chamada de criptografia pós-quântica. Particularmente, esses
algoritmos baseiam-se numa série de problemas que permanecem difíceis, mesmo
que computadores quânticos poderosos sejam utilizados, logo, despertam o
interesse para substituir os criptossistemas clássicos. Este trabalho visa
estudar a classe de criptossistemas baseados em sistemas de polinômios
multivariados, que, baseiam-se em problemas como a solução de sistemas de
polinômios e o isomorfismo de polinômios, os quais ainda são resistentes a
algoritmos quânticos, portanto, são bons candidatos para criptografia
pós-quântica.
}
\palavrasChave{criptografia, assinatura digital, pós-quântico}

\capa{}
\folhaderosto{}

\clearpage

\begin{mdframed}[backgroundcolor=lightgray, linewidth=0pt]
	\centering
	\textbf{FOLHA DE APROVAÇÃO DE PROPOSTA DE TCC}
\end{mdframed}

\vspace{-5mm}
\begin{table}[h]
	\begin{tabular}{|>{\bfseries}l|p{6.57cm}|}
	\hline
		Acadêmico(s)          & Matheus Bittencourt                   \\ \hline
		Título do trabalho    & Multivariate Public Key Cryptosystems \\ \hline
		Curso                 & Ciência da Computação/INE/UFSC        \\ \hline
		Área de Concentração  & Matemática da Computação              \\ \hline
	\end{tabular}
\end{table}

\vspace{-2mm}
{\footnotesize\noindent\textbf{
	Instruções para preenchimento pelo \underline{ORIENTADOR DO TRABALHO}:} \\
	\begin{itemize}[leftmargin=3.6mm,label=-]
    \vspace{-4mm}
		\item Para cada critério avaliado, assinale um X na coluna SIM apenas
		se considerado aprovado. Caso contrário, indique as alterações
		necessárias na coluna Observação.
	\end{itemize}
}

\vspace{-3mm}
\begin{table}[hbpt]
  \begin{tabular}{|>{\tiny}m{4.3cm}*{4}{|>{\columncolor{lightgray}\tiny}c}|c|}
    \hline
    \rowcolor{lightgray} & \multicolumn{4}{c|}{\textbf{Aprovado}} & \\
    \hhline{|>{\arrayrulecolor{lightgray}}->{\arrayrulecolor{black}}|
        |---->{\arrayrulecolor{lightgray}}->{\arrayrulecolor{black}}|}
    \rowcolor{lightgray}
    \multicolumn{1}{|c|}{\multirow{-2}{*}{\normalsize\textbf{Critérios}}}
      & \textbf{Sim} & \textbf{Parcial} & \textbf{Não} & \textbf{Não se aplica}
      & \multirow{-2}{*}{\textbf{Observação}} \\ \hline
    1. O trabalho é adequado para um TCC no CCO/SIN
      (relevância / abrangência)?                         & & & & & \\ \hline
    2. O título do trabalho é adequado?                   & & & & & \\ \hline
    3. O tema de pesquisa está claramente descrito?       & & & & & \\ \hline
    4. O problema/hipóteses de pesquisa do trabalho
      está claramente identificado?                       & & & & & \\ \hline
    5. A relevância da pesquisa é justificada?            & & & & & \\ \hline
    6. Os objetivos descrevem completa e claramente
      o que se pretende alcançar neste trabalho?          & & & & & \\ \hline
    7. É definido o método a ser adotado no trabalho?
      O método condiz com os objetivos e é adequado
      para um TCC?                                        & & & & & \\ \hline
    8. Foi definido um cronograma coerente com o método
      definido (indicando todas as atividades) e com as
      datas das entregas (p.ex. Projeto I, II, Defesa)?   & & & & & \\ \hline
    9. Foram identificados custos relativos à execução
      deste trabalho (se houver)? Haverá financiamento
      para estes custos?                                  & & & & & \\ \hline
    10. Foram identificados todos os envolvidos neste
      trabalho?                                           & & & & & \\ \hline
    11. As formas de comunicação foram definidas
      (ex.: horários para orientação)?                    & & & & & \\ \hline
    12. Riscos potenciais que podem causar desvios do
      plano foram identificados?                          & & & & & \\ \hline
    13. Caso o TCC envolva a produção de um software ou
      outro tipo de produto e seja desenvolvido também
      como uma atividade realizada numa empresa ou
      laboratório, consta da proposta uma declaração
      (Anexo 3) de ciência e concordância com a entrega
      do código fonte e/ou documentação produzidos?       & & & & & \\ \hline
  \end{tabular}

  \vspace{2mm}
  {\footnotesize
  \begin{tabular}{|>{\bfseries}p{3cm}|l|l|l|}
    \hline Avaliação & \multicolumn{2}{l}{\bf $\square$ Aprovado}
      & \textbf{$\square$ Não Aprovado} \\
    \hline Professor Responsável & Ricardo Felipe Custódio & 12/11/2018 & \\
    \hline
  \end{tabular}}
\end{table}

\paginaresumo

\sumario

\chapter{Introduction}

Classic cryptography is threatened by quantum computers since polynomial time
quantum algorithms for solving the integer factorization and the discrete
logarithm problem already exist~\cite{shor1999polynomial}. The hardness of
recovering private keys, for instance, RSA and ECDSA keys, relies on the
hardness of the aforementioned problems, therefore, with such algorithms, a
private key could be easily recovered from its public key by a sufficiently
powerful quantum computer. Hence the most used digital signature algorithms
would become insecure.

In such scenario, cryptosystems that cannot be broken by quantum computers
should be used for handling digital signatures. The area that studies such
cryptosystems is called post-quantum cryptography, and the interest in this
has emerged with the development of quantum computers. The security of these
algorithms relies on problems that still do not have polynomial time quantum
algorithms that solves them, therefore, they appear to be good candidates for
use in a scenario of attackers equipped with quantum computers.

There are several classes of post-quantum cryptosystems proposed in the
literature, and each of them relies on one kind of hard problem. This work aims
to study Multivariate Public-Key Cryptosystems (MPKCs). These cryptosystems are
constructed using multivariate polynomials systems. Polynomial systems are
generally composed of polynomial equations with single variable monomials. Such
systems can be easily solved using Gaussian elimination, but the addition of
more variables into the monomials, making it a multivariate system, turns the
problem NP-Hard~\cite{garey1990npc}. The security of MPKCs will be based on the
hardness of solving such systems and also, on the Isomorphism of Polynomials
(IP) problem.

Several digital signature schemes were developed based on the structure of
multivariate systems. One of the first schemes presented was the Oil-Vinegar
(OV) signature scheme~\cite{patarin1997ov}, which was broken by Kipnis and
Shamir in its original specification~\cite{kipnis1998cryptanalysis}. A
subsequent work by Kipnis et al. made it secure again with new parameters
leading to a scheme called Unbalanced Oil-Vinegar
(UOV)~\cite{kipnis1999unbalanced}. The classic OV is the building block for
various other schemes, called \textit{SingleField} schemes. In essence, they
are similar to OV, but ended up optimizing the security, the signature and key
sizes. These schemes are still considered secure.

This work aims to understand the OV signature scheme and its subsequent
optimized schemes as well as propose new optimization(s). The public
information of a public key cryptosystem, such as the public key or the
signature, is the data that is actually transmitted over a communication
channel, or stored in places in which there may be constraints, therefore,
reducing such parts is of great interest. Further, reducing key sizes has a
direct impact on the operations that use them, from the simple fact that we
operate with less data.  For example, with a smaller public key, verifying
signatures becomes faster, as seen in a work by Petzoldt et
al.~\cite{petzoldt2011small}.

\section{Goals}

This section describes general and specific goals of the proposed work as well
as scope and other basic premises.

\begin{itemize}

	\item \textit{General goals:} Study and describe UOV-like digital
	signatures schemes, understand the optimized schemes that reduce keys and
	signature sizes, and their impact on the security of the classic schemes.
	Observe and understand the impact of the parameters selection for such
	schemes and experiment with them, as this plays an important role in
	efficient and fast implementations of the schemes. Analyze the bleeding
	edge schemes recently proposed, searching for possible improvements and
	also understand the strategies being used to optimize the cryptosystems.

	\item \textit{Specific goals:} \begin{enumerate}

		\item Describe the classic OV and the UOV digital signature schemes;

		\item Describe the Rainbow signature scheme;

		\item Describe the relevant optimized schemes based on Rainbow like
		CyclicRainbow~\cite{petzoldt2010cyclicrainbow};

		\item Compare and analyze the performance of the aforementioned schemes
		in terms of time to generate and verify signatures as well as memory
		usage.

		\item Finally, propose new optimizations on top of those schemes.

	\end{enumerate}

	\item \textit{Scope:} This work will not cover other classes of
	post-quantum algorithms like code-based, lattice-based and hash-based
	cryptosystems, or, classic asymmetric algorithms, such as RSA and DSA.
	Quantum algorithms and their aspects will also not be discussed by this
	work.

	\item \textit{Acceptance criteria:} Detailed study and implementation of
	the (U)OV and Rainbow signature schemes; Detailed study of at least three
	optimized schemes and the impact caused by the respective optimizations.

	\item \textit{Deliverables:} Reports of the undergraduate thesis according
	to the deadlines and specifications of the related UFSC disciplines,
	including the full thesis at the end of the course (INE5434), as well as
	documented implementations made for experimentation and testing.

	\item \textit{Premises and restrictions:} There will be periodic meetings
	with supervisors to discuss present and future activities. All documents
	will be normalized according to UFSC thesis templates. Free and open-source
	software will be used. All deadlines of the project, in respect of the
	related disciplines, should be complied with.

\end{itemize}

\section{Methodology}

The work will be developed using the infrastructure and resources provided by
the Computer Security Laboratory (LabSEC/UFSC). A literature review will be
made to determine what is the state-of-the-art in MPKCs. Recently proposed
schemes will be studied, as well as broken ones for a better understanding of
the used constructions that optimize the classic multivariate schemes. Works
that investigate the parameters of SingleField schemes will be given the
deserved attention as well. Performance of all the schemes studied should be
observed along with the impact of the optimizations.

\chapter{Cronograma}

\begin{figure}[htbp]
  \begin{tabular}{|p{4.04cm}|*{6}{c|}}
    \hline \rowcolor{lightgray}
      & \multicolumn{6}{c|}{\textbf{Meses -- 2019}} \\
    \hhline{|>{\arrayrulecolor{lightgray}}->{\arrayrulecolor{black}}|
      |------>{\arrayrulecolor{lightgray}}>{\arrayrulecolor{black}}|}
    \rowcolor{lightgray}
      \multicolumn{1}{|c|}{\multirow{-2}{*}{\textbf{Etapas}}}
      & \textbf{jan.} & \textbf{fev.} & \textbf{mar.}
      & \textbf{abr.} & \textbf{mai.} & \textbf{jun.} \\
    \hline Fundamentação teórica & \cellcolor{lightgray} & & & & & \\
    \hline Revisão do estado da arte & \cellcolor{lightgray}
      & \cellcolor{lightgray} & \cellcolor{lightgray} & & & \\
      \hline Desenvolvimento do TCC & & & \cellcolor{lightgray}
      & \cellcolor{lightgray} & \cellcolor{lightgray} & \\
    \hline Implementação & & & & & \cellcolor{lightgray}
      & \cellcolor{lightgray} \\
    \hline Relatório de TCC I & & & & & \cellcolor{lightgray} & \\
    \hline
    \hline \rowcolor{lightgray}
      & \multicolumn{6}{c|}{\textbf{Meses -- 2019}} \\
    \hhline{|>{\arrayrulecolor{lightgray}}->{\arrayrulecolor{black}}|
      |------>{\arrayrulecolor{lightgray}}>{\arrayrulecolor{black}}|}
    \rowcolor{lightgray}
      \multicolumn{1}{|c|}{\multirow{-2}{*}{\textbf{Etapas}}}
      & \textbf{jul.} & \textbf{ago.} & \textbf{set.}
      & \textbf{out.} & \textbf{nov.} & \textbf{dez.} \\
    \hline Implementação & \cellcolor{lightgray} & & & & & \\
    \hline Experimentação & & \cellcolor{lightgray} & & & & \\
    \hline Redação da monografia & & \cellcolor{lightgray}
      & \cellcolor{lightgray} & \cellcolor {lightgray} & & \\
    \hline Ajustes na monografia & & & & \cellcolor{lightgray} & & \\
    \hline Relatório de TCC II & & & & & \cellcolor{lightgray} & \\
    \hline Defesa pública & & & & & & \cellcolor{lightgray} \\
    \hline Ajustes finais do TCC & & & & & & \cellcolor{lightgray} \\
    \hline
  \end{tabular}
\end{figure}

\chapter{Custos}

\begin{figure}[htbp]
  \begin{tabular}{|p{1.69cm}|*{3}{l|}}
    \hline \thatcell{1}{|c|}{Item} & \thatcell{1}{c|}{Quantidade}
      & \thatcell{1}{c|}{Valor unitário (R\$)}
      & \thatcell{1}{c|}{Valor Total (R\$)}                         \\
    \hline \thatcell{4}{|l|}{Material permanente}                   \\
    \hline Computador   & 1     & R\$ 3.000,00  & R\$ 3.000,00      \\
    \hline Artigos      & 10    & R\$ 90,00     & R\$ 900,00        \\
    \hline Livros       & 2     & R\$ 200,00    & R\$ 400,00        \\
    \hline \thatcell{4}{|l|}{Material de consumo}                   \\
    \hline Alimentação  & 200   & R\$ 10,00     & R\$ 2.000,00      \\
    \hline CDs/DVDs     & 4     & R\$ 2,00      & R\$ 8,00          \\
    \hline \thatcell{4}{|l|}{Outros recursos e serviços}            \\
    \hline Impressões   & 200   & R\$ 1,00      & R\$ 200,00        \\
    \hline
  \end{tabular}
\end{figure}

\chapter{Recursos Humanos}

\begin{figure}[htbp]
  \begin{tabular}{|*{2}{p{4.96cm}|}}
    \hline \rowcolor{lightgray}
    \thatcell{1}{|c|}{Nome}                   & \thatcell{1}{c|}{Função} \\
    \hline Matheus Silva Pinheiro Bittencourt & Autor                    \\
    \hline Ricardo F. Custódio                & Orientador               \\
    \hline Gustavo Zambonin                   & Coorientador             \\
    \hline Renato Cislaghi                    & Coordenador de projetos  \\
    \hline Lucas Pandolfo Perin               & Membro da banca          \\
    \hline
  \end{tabular}
\end{figure}

\chapter{Comunicação}

\begin{figure}[htbp]
  \footnotesize
  \begin{tabular}{|P{1.9cm}|P{0.7cm}|P{2.5cm}|P{1.5cm}|P{2cm}|}
    \hline \rowcolor{lightgray}
    \textbf{O que precisa ser comunicado} & \textbf{Por quem}
      & \textbf{Para quem} & \textbf{Melhor forma de comunicação}
      & \textbf{Quando e com que frequência} \\
    \hline Enviar plano de projeto & Autor
      & Orientador, coorientador, coordenador de projetos & Sistema de TCC
      & Única vez, até dia 12/11/2018 \\
    \hline Entrega de relatório de TCC I & Autor
      & Orientador, coorientador, coordenador de projetos,
      membro(s) da banca & Sistema de TCC
      & Única vez, ao final do semestre 2019/1 \\
    \hline Entrega de relatório de TCC II & Autor
      & Orientador, coorientador, coordenador de projetos,
      membros(s) da banca & Sistema de TCC
      & Única vez, em meados do semestre 2019/2 \\
    \hline Defesa do TCC & Autor
      & Orientador, coorientador, coordenador de projetos,
      membro(s) da banca & Pessoalmente
      & Única vez, em meados do semestre 2019/2 \\
    \hline Entrega final da monografia & Autor
      & Orientador, coorientador, coordenador de projetos,
      membro(s) da banca & Sistema de TCC
      & Única vez, após a defesa, antes do término de 2019/2 \\
    \hline Reuniões de acompanhamento da pesquisa & Autor
      & Orientador, coorientador & Pessoalmente, webconferência
      & Quinzenalmente \\
    \hline Monitoramento do projeto & Autor
      & Orientador, coorientador & E-mail & Esporadicamente \\
    \hline
  \end{tabular}
\end{figure}

\chapter{Riscos}

\begin{figure}[htbp]
  \footnotesize
    \begin{tabular}{|P{1.3cm}|*{3}{P{0.8cm}|}*{2}{P{2.24cm}|}}
    \hline \rowcolor{lightgray}
    \textbf{Risco} & \textbf{Proba\-bilidade} & \textbf{Impacto}
      & \textbf{Priori\-dade} & \textbf{Estratégia de resposta}
      & \textbf{Ações de prevenção} \\
    \hline Paralisação de transporte público & Média & Médio & Baixa
      & Transportar-se à Universidade utilizando meios alternativos
      & Combinar transporte alternativo \\
    \hline Paralisação de servidores públicos & Muito baixa & Alto & Média
      & Produzir monografia e pesquisa utilizando recursos pessoais
      & Não se aplica \\
    \hline Problemas de saúde & Baixa & Alto & Alta
      & Tratamento médico das condições identificadas
      & Diminuir exposição a doenças e realizar exames de prevenção
        regularmente \\
    \hline Perda de dados & Muito baixa & Alto & Média
      & Recuperar cópias
      & Manter cópias do material produzido em serviços de dados distribuídos
        confiáveis \\
    \hline Queima de equipamento(s) eletrônico(s) & Muito baixa & Alto & Média
      & Comprar novo(s) equipamento(s)
      & Evitar utilização do(s) equipamento(s) em condições de risco \\
    \hline
  \end{tabular}
\end{figure}

\bibliographystyle{abnt-alf}
\bibliography{ref}

\end{document}