bsc.tex

\documentclass{ufsctex/ufsctex}

\usepackage{
  amsmath, amsfonts, amssymb, anyfontsize, booktabs, chronology, enumitem,
  etoolbox, multirow, pdfpages, pgfplots, tikz, tikz-qtree, todonotes, xfrac
}

\newcommand{\hh}{\mathcal{H}}
\newcommand{\pk}{\mathcal{P}_{k}}
\newcommand{\sk}{\mathcal{S}_{k}}
\newcommand{\bone}{\mathcal{B}_{1}}
\newcommand{\btwo}{\mathcal{B}_{2}}
\newcommand{\hash}[2][]{\mathcal{H}^{#1} (#2)}
\newcommand{\concat}{\, \vert{} \vert{} \,}
\newcommand{\binwds}[1]{\{0, 1\}^{#1}}
\newcommand{\length}[1]{\vert{} #1 \vert{}}
\newcommand{\fhash}[1]{\hh{}: \binwds{*} \longrightarrow{} \binwds{#1}}
\newcommand{\random}{\stackrel{\$}{\longleftarrow}}

\newcommand{\bds}{\textsc{Bds}}
\newcommand{\lots}{\textsc{LD-Ots}}
\newcommand{\wots}{\textsc{Wots}}
\newcommand{\wotsprf}{\textsc{Wots-pr}}
\newcommand{\wotsplus}{\textsc{Wots+}}
\newcommand{\wotslm}{\textsc{Wots-lm}}
\newcommand{\wotst}{\textsc{Wots-t}}
\newcommand{\wotsb}{\textsc{Wots-b}}
\newcommand{\wotsr}{\textsc{Wots-r}}
\newcommand{\wotsbr}{\textsc{Wots-br}}
\newcommand{\hors}{\textsc{Hors}}
\newcommand{\horst}{\textsc{Horst}}
\newcommand{\mss}{\textsc{Mss}}
\newcommand{\cmss}{\textsc{Cmss}}
\newcommand{\gmss}{\textsc{Gmss}}
\newcommand{\sprmss}{\textsc{Spr-Mss}}
\newcommand{\xmss}{\textsc{Xmss}}
\newcommand{\xmsst}{\textsc{Xmss-t}}
\newcommand{\xmssmt}{\textsc{Xmss-mt}}
\newcommand{\xmssb}{\textsc{Xmss-b}}
\newcommand{\xmssr}{\textsc{Xmss-r}}
\newcommand{\xmssbr}{\textsc{Xmss-br}}
\newcommand{\sphincs}{\textsc{Sphincs}}

\pgfplotsset{compat=1.15}

\usetikzlibrary{
  matrix, arrows, decorations.markings, shapes.geometric, patterns
}

\tikzset{
  XOR/.style={draw, circle, append after command={
    [shorten >=\pgflinewidth, shorten <=\pgflinewidth,]
    (\tikzlastnode.north) edge (\tikzlastnode.south)
    (\tikzlastnode.east) edge (\tikzlastnode.west)}},
}

\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}

\DeclareMathAlphabet{\mathcal}{OMS}{cmsy}{m}{n}

\vbadness=10000

% https://tex.stackexchange.com/a/193370
\makeatletter
\patchcmd{\pdfstringdef}
  {\csname HyPsd@babel@}
  {\let\bbl@info\@gobble\csname HyPsd@babel@}
  {}{}
\makeatother

\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[o]{{Trabalho de Conclusão de Curso}}
\titulo{Otimização de desempenho do esquema de assinatura digital Winternitz}
\autor{Gustavo Zambonin}
\grau{Bacharel em Ciência da Computação}
\local{Florianópolis}
\data{11}{junho}{2018}
\orientador[Orientador]{Prof.\ Ricardo Felipe Custódio, Dr.}
\coorientador[Coorientador]{Prof.\ Daniel Panario, Dr.}
\coordenador[Coordenador]{Prof.\ Rafael Luiz Cancian, Dr.}

\numerodemembrosnabanca{1}
\orientadornabanca{nao}
\coorientadornabanca{nao}
\bancaMembroA{
  Lucas Pandolfo Perin, Me. \\
  Universidade Federal de Santa Catarina
}

\dedicatoria{Às mulheres em minha vida}

\agradecimento{Agradeço à minha mãe, Luciana, pela introdução antecipada às
linguagens, o uso prudente destas, e o desejo pela docência; ao meu pai,
Roberto, pelo incentivo à destreza numérica e tecnológica; e a ambos,
naturalmente, pelo perfeccionismo, firmeza e ambição, valores essenciais no
caminho para este trabalho.

Agradeço aos Professores Ricardo Custódio, Daniel Panario e Jean Martina, e
ao Mestre Lucas Perin, pela orientação e/ou co-autoria deste trabalho, e por
prover a infraestrutura necessária para que este trabalho fosse desenvolvido,
na forma do Laboratório de Segurança em Computação.

Agradeço aos amigos que fazem ou fizeram parte desta jornada, sem os quais não
seria possível chegar até aqui. Em especial, à Ana Letícia, pelo seu imutável
suporte e companheirismo, e pela contagiante sinceridade; à Larissa, pela sua
tamanha paciência, e sabedoria em momentos delicados; ao Douglas, pelos
momentos de descontração e por prover a oportunidade de trabalhar em um
ambiente proveitoso; aos caríssimos Dúnia, Emmanuel, Matheus e Ramna, pelas
incontáveis horas de discussões proveitosas sobre quaisquer assuntos acadêmicos
ou habituais; e à Poliana, pela sua confiança e entusiasmo, manifestados na
forma de seu inexorável, imensurável e imperturbável amor.}

\epigrafe{``How long do you want these messages to remain secret?'' [\ldots]
\emph{I want them to remain secret for as long as men are capable of evil.}
}{Neal Stephenson (\textit{Cryptonomicon}, 1999)}

\textoResumo{Algoritmos criptográficos utilizados em assinaturas digitais
atualmente, como RSA e ECDSA, têm sua segurança baseada na dificuldade de se
fatorar números muito grandes ou na obtenção de logaritmos discretos. Este tipo
de cômputo pode ser eficientemente realizado por um computador quântico,
utilizando algoritmos já conhecidos. Deste modo, para manter o ambiente de
assinaturas digitais seguro, é necessário oferecer alternativas pós-quânticas.
Este trabalho busca apresentar esquemas baseados apenas em funções de resumo
criptográfico, cuja segurança é baseada apenas na resistência à colisões da
função escolhida, com o intuito de discutir uma nova otimização para a família
de esquemas de assinatura Winternitz. Particularmente, esta proposta introduz
um parâmetro de compensação, a fim de reduzir o tempo de geração ou verificação
de uma dada assinatura.}
\palavrasChave{criptografia pós-quântica, função de resumo criptográfico,
assinatura digital, esquema de assinatura digital única Winternitz}

\textAbstract{Algorithms currently used in digital signature schemes, such as
RSA and ECDSA, feature security proofs based on the difficulty of calculating
large integer factorizations or discrete logarithms. This kind of computation
can be achieved through a sufficiently powerful quantum computer running
already known algorithms. Hence, to maintain the security \emph{status quo}, it
is imperative to offer post-quantum alternatives, that is, schemes resistant to
quantum computers. This work explores hash-based digital signature schemes, in
which security is reduced to the collision resistance of a chosen hash
function, showing that the construction of such secure schemes is independent
from hard problems from number theory or algebra. Finally, we introduce an
optimization for the Winternitz one-time signature scheme family in the form of
a tradeoff parameter, enabling reduced execution time for signature generation
or verification.}
\keywords{post-quantum cryptography, cryptographic hash function, digital
signature, Winternitz one time signature scheme}

\begin{document}

\pagenumbering{roman}
\capa{}
\pretextuais{}
\listadefiguras{}
\listadetabelas{}
\listadeabreviaturas{}
\listadesimbolos{}
\listadealgoritmos{}
\sumario{}

\chapter{Introdução}\label{chapter:intro}

A aplicação de protocolos criptográficos é essencial no contexto da validação e
proteção de quaisquer comunicações realizadas por um conjunto de entidades,
sejam estas dispositivos eletrônicos ou indivíduos, em virtude da possível
criticidade e sensibilidade atribuídas aos dados transmitidos. Esquemas de
assinatura digital são comumente utilizados para assegurar este processo de
maneira formal~\cite[Seção 6.1]{Goldreich:book:2004}, através da autenticidade
e não-repúdio do remetente e certeza da integridade dos dados, a fim de
traduzir o resguardo provido por uma assinatura de próprio punho no mundo real.

Na prática, a maior parte destes esquemas utilizam como alicerce algorítmico
criptossistemas assimétricos baseados em problemas ``difíceis'' da teoria dos
números, como a fatoração de inteiros ou resolução do logaritmo discreto. Este
fato provê a segurança necessária para os esquemas em computadores eletrônicos,
por conta da inexistência de algoritmos que resolvem estes problemas em tempo
polinomial. Entretanto, em computadores quânticos, algoritmos dessa forma já
existem, \emph{e.g.} o algoritmo de Shor~\cite{Shor:article:1997:oct},
efetivamente tornando estes esquemas clássicos inseguros neste novo contexto.

Para combater esta situação, a criptografia pós-quântica encarrega-se de buscar
algoritmos criptográficos cuja segurança é considerada ``suficiente'', mesmo na
utilização de um hipotético computador quântico para ataques especializados.
Esta área conta com diversas abordagens: a criptografia baseada em reticulados,
polinômios de múltiplas variáveis sobre um corpo finito, teoria de códigos,
morfismos entre curvas elípticas supersingulares e criptossistemas simétricos.
Entretanto, alguns destes métodos não podem ser utilizados no contexto de
esquemas de assinatura digital, e para outros, a inexistência de reduções de
segurança formais e o tamanho das chaves impossibilitam a utilização destes em
aplicações práticas~\cite{Bernstein:article:2017:sep}.

Não obstante, uma abordagem adicional de esquema de assinatura digital
resistente a computadores quânticos é baseada apenas em funções de resumo
criptográfico, construídas a partir de funções de mão
única~\cite{Katz:misc:2005:sep}. De fato, estas funções, desde que apresentem
requisitos de segurança como resistência à segunda pré-imagem e/ou à colisões,
são necessárias e suficientes para a construção de esquemas bem comportados e
seguros~\cite{Rompel:inproc:1990:may}. Visto que estas funções são estudadas
exaustivamente por conta de sua vasta presença em diversos âmbitos da segurança
da informação, reduções de segurança são mais comuns em relação a outras
abordagens pós-quânticas, e tamanhos de chaves e assinaturas são menos
proibitivos.

Esquemas de assinatura digital baseados em funções de resumo criptográfico
consistem da utilização de um esquema de assinatura digital única, onde apenas
uma mensagem pode ser assinada de modo seguro, possivelmente combinados à
estrutura de dados chamada de árvore de Merkle~\cite{Merkle:inproc:1989:aug},
que abriga pares de chaves de diversas instâncias do esquema supracitado como
suas folhas, e reduz a verificação destes para uma única chave, codificada em
sua raiz. Esta árvore é construída com a concatenação de resumos criptográficos
do conteúdo dos nós, habilitando assim a assinatura de diversas mensagens. Como
uma função específica não é necessária, é possível obter uma grande variedade
de esquemas, garantindo a versatilidade destas abordagens.

Embora os esquemas iniciais tenham sido construídos sem atenção particular à
eficiência de modo geral (\emph{e.g.} o esquema de assinatura de
Lamport~\cite{Lamport:report:1979:oct} assina apenas um \emph{bit} de
informação em sua forma mais simples), muitos resultados práticos demonstram a
redução contínua do tempo de verificação da assinatura, tamanho e tempo para
geração do par de chaves e assinatura, bem como avanços teóricos que
possibilitam a utilização de funções com requisitos de segurança
mínimos~\cite{Huelsing:inproc:2013:jun}, garantem o conceito de sigilo
encaminhado~\cite{Buchmann:inproc:2011:nov} e a ausência do gerenciamento de
estado~\cite{Bernstein:inproc:2015:apr}.

Neste trabalho, é enfatizado o estudo do esquema de assinatura digital única
Winternitz, no qual o resumo criptográfico da mensagem a ser assinada define
diretamente a complexidade dos passos de geração e verificação da assinatura.
De acordo com este comportamento, é apresentada uma adaptação para o esquema
na forma de um parâmetro adicional, que habilita a redução do cômputo de
verificação de assinatura em troca do aumento deste na geração da assinatura,
ou vice-versa.

Ambientes nos quais existem limitações de processamento para uma destas etapas,
como redes de sensores sem fio, podem configurar instâncias do esquema
Winternitz a fim de otimizar sua comunicação segura, aumentando o tempo de
execução do cômputo para a geração de assinaturas, geralmente feita em
dispositivos com poder de processamento amplificado. Ademais, as consequências
desta otimização são verificadas em esquemas mais complexos, baseados em
árvores de Merkle, que também podem ser aplicados a meios com restrições
similares.

\section{Objetivos}\label{section:objectives}

\subsection{Objetivo geral}\label{subsection:general}

Apresentar um estudo detalhado sobre os principais esquemas de assinatura
digital baseados em funções de resumo criptográfico. Em especial, um estudo
detalhado sobre o esquema de assinatura digital única Winternitz é realizado,
contextualizando-o junto aos algoritmos previamente descritos. Este processo
tem o intuito de fundamentar a otimização proposta, que afeta o tempo de
execução da criação ou verificação de uma assinatura.

\subsection{Objetivos específicos}\label{subsection:specific}

\begin{enumerate}[label=\roman*.]

  \item Descrever os esquemas de assinatura digital única \lots{} e \wots{},
      sua variante \wotsplus{}, e o esquema de poucas assinaturas \hors{};

  \item Descrever os esquemas de assinatura digital baseado em árvores de
      Merkle \mss{}, \xmss{} e \xmssmt{};

  \item Apresentar a otimização para a família \wots{} e discutir consequências
      desta modificação no contexto de esquemas baseados em árvores de Merkle.

\end{enumerate}

\section{Trabalhos relacionados}\label{section:related}

Artigos na literatura recente consistentes com o tema deste trabalho focam na
redução do tempo de execução da verificação da assinatura, através da definição
de novos esquemas variantes. Em especial, o esquema proposto
em~\cite{Cruz:inproc:2016:oct} torna a complexidade deste passo previsível
através de uma função que mapeia a mensagem para uma tupla com propriedades
especiais; em~\cite{Steinwandt:article:2008:oct}, a mensagem é modificada a fim
de gerar um resumo criptográfico cuja codificação \emph{run-length} é
otimizada; e em~\cite{McGrew:report:2018:apr}, um parâmetro é adicionado que
marca o número de \emph{bits} inutilizados na assinatura, a fim de que estes
não sejam verificados de maneira supérflua.

Neste trabalho, a estrutura do esquema base não é modificada, e um
pré-processamento da mensagem é feito alternativamente, permitindo a
escalabilidade de instâncias de esquemas Winternitz com quaisquer parâmetros,
introduzindo apenas um pequeno custo na etapa de assinatura da mensagem.

\section{Contribuições deste trabalho}\label{section:contributions}

Uma versão resumida deste trabalho~\cite{Perin:inproc:2018:jun} será publicada
como um artigo completo em \emph{22th IEEE Symposium on Computers and
Communications} (ISCC 2018), sob o nome \emph{Tuning the Winternitz Hash-Based
Digital Signature Scheme}, que pode ser consultado no
Apêndice~\ref{chapter:paper}. Este trabalho busca adicionalmente fornecer
explicações didáticas para vários esquemas baseados em funções de resumo
criptográfico presentes na literatura, bem como uma abordagem complementar aos
argumentos providos pelo artigo, no Capítulo~\ref{chapter:tuning}.

\chapter{Primitivas criptográficas}\label{chapter:primitives}

Neste capítulo, são explicados os conceitos necessários a fim de entender
inteiramente um esquema de assinatura digital, bem como outros algoritmos
discutidos ao longo do trabalho. A organização das seções é semelhante à
seguida em~\cite[Capítulo 2]{Gathen:book:2015}. Os conceitos de criptografia
simétrica e assimétrica são apresentados na Seção~\ref{section:crypto}, e uma
simples comparação entre os mesmos é realizada. Funções de sentido único, base
teórica para funções de resumo criptográfico, são discutidas na
Seção~\ref{section:hashfunc}, e exemplos de construções teóricas por trás
destas funções são apresentados nas Subseções~\ref{subsection:const}
e~\ref{subsection:sponge}. Por fim, a definição formal de um esquema de
assinatura digital é apresentada na Seção~\ref{section:digitalsig}, agregando
estas noções e apresentando o criptossistema RSA como exemplo, na
Subseção~\ref{subsection:rsa}.

\section{Criptografia simétrica e assimétrica}\label{section:crypto}

Define-se criptografia como a criação e análise de protocolos matemáticos que
habilitam comunicação segura, através de um canal inseguro, entre duas ou mais
entidades. Implementações destes, comumente chamadas de algoritmos
criptográficos, podem ser parametrizadas por uma chave, que habilita a
transformação do texto plano para texto cifrado de acordo com esta, de maneira
individual e inteligível, mas a fim de tornar o resultado irrecuperável sem a
apresentação da chave correspondente. De acordo com esta característica, estes
algoritmos são classificados em duas grandes famílias.

Sistemas que utilizam a mesma chave para as operações de codificação e
decodificação são chamados de simétricos. Nesta situação, a chave representa um
segredo compartilhado entre entidades desejando estabelecer comunicação segura.
Como o ato de compartilhar este segredo necessita, por si próprio, de um canal
seguro, este aspecto é uma desvantagem destes criptossistemas.

Cifras de bloco ou de fluxo são considerados exemplos convencionais de
criptossistemas simétricos. A construção destes geralmente é feita através do
encadeamento de operações binárias e matemáticas favoráveis para computadores,
assim permitindo aos algoritmos um desempenho altíssimo. Utilizando estas como
alicerce, é possível construir funções de resumo criptográfico. Este processo é
explorado na Subseção~\ref{subsection:const}.

No contexto da computação quântica, estes sistemas são ameaçados pelo algoritmo
de Grover~\cite{Grover:inproc:1996:may}, que possibilita a busca de elementos
em conjuntos em tempo reduzido. Por outra forma, suponha que é desejável
inverter uma função $f : A \longrightarrow B$, a partir de um elemento $b \in
B$. Classicamente, como não existe informação qualquer sobre a função, é
necessário calcular $f$ para cada um dos elementos de seu domínio, \emph{i.e.}
$\length{A}$\simbolo{$\length{\omega}$}{Tamanho da palavra $\omega$} vezes.
Entretanto, Grover permite que esta busca seja feita em
$\length{A}^{\frac{1}{2}}$ operações. Assim, um algoritmo criptográfico
simétrico que toma o lugar de $f$, neste exemplo, precisa de parâmetros de
segurança maiores, a fim de igualar a dificuldade da busca em se tratando de um
computador clássico.

Em contrapartida, a criptografia assimétrica, ou criptografia de chaves
públicas, engloba os algoritmos que utilizam um par de chaves: a chave privada,
conhecida apenas pela entidade que a gerou, e a chave pública, distribuída
livremente. Podem ser representadas por, respectivamente, $\sk{}$ e $\pk{}$.
Isto possibilita o uso livre de $\pk{}$ para a comunicação segura com o
detentor da chave sem a necessidade de um canal seguro, em virtude da
construção dos algoritmos.

A ideia foi introduzida abstratamente em~\cite{Diffie:article:1976:sep} e tem
como exemplos algoritmos como RSA, ElGamal e ECDSA\sigla{ECDSA}{\emph{Elliptic
Curve Digital Signature Algorithm}}. Diferentemente dos algoritmos simétricos,
estes sistemas utilizam operações matemáticas mais robustas e, portanto, de
desempenho reduzido. Assim, a utilização convencional destes dois tipos de
criptografia em protocolos ocorre através da codificação de uma chave
simétrica, responsável por cifrar um documento de tamanho não trivial, com uma
chave pública, e transmissão desta ``chave cifrada'' através de um canal
qualquer. Em especial, o algoritmo RSA é discutido como um simples exemplo de
esquema de assinatura digital, na Subseção~\ref{subsection:rsa}.

A segurança de sistemas assimétricos depende da ``dificuldade'' computacional
de determinar uma chave privada a partir da chave pública, e também do
armazenamento de $\sk{}$ em um lugar seguro. Problemas em teoria de números e
álgebra que atualmente não admitem soluções em tempo polinomial são comumente
utilizados como base para algoritmos assimétricos. Porém, com a introdução de
um computador quântico, estes problemas podem ser resolvidos de maneira
significativamente mais rápida, como visto em~\cite{Shor:article:1997:oct}.

\section{Funções de sentido único}\label{section:hashfunc}

Funções cuja aplicação é viável, porém a inversão desta torna-se um problema
difícil em se tratando de complexidade computacional, são chamadas de funções
de sentido único. Apresentam várias utilidades no âmbito de segurança da
informação e criptografia, em especial para o resumo de dados, ou seja, a
redução de uma mensagem de tamanho arbitrário para uma palavra pequena e
identificável. Neste contexto, um problema é considerado ``difícil'', ou
computacionalmente inviável, quando o tempo ou recursos gastos para esta
computação excedem a validade ou utilidade da informação desejada.

Estas funções podem possuir várias propriedades, apresentadas
abaixo de acordo com~\cite[Seção 9.2]{Menezes:book:1996}. Tome uma função
$\mathcal{H} : X \longrightarrow Y$.  Comumente, os elementos de $Y$ são
chamados de resumos.

\begin{enumerate}[label= (\roman*)]

  \item $\hh{}$ deve ser necessariamente \emph{determinística};

  \item O cálculo de todo resumo deve ser \emph{computacionalmente
      fácil}\footnote{Note que existem funções de desempenho reduzível, como
        \texttt{bcrypt}, prevenindo ataques de força bruta a serviços que
        armazenam resumos de dados sensíveis, \emph{e.g.} senhas.};

  \item $\hh{}$ pode apresentar \emph{compressão}, ou seja, o mapeamento de uma
      palavra $x \in X$ de tamanho arbitrário para um resumo $y \in Y$ de
        tamanho fixo;

  \item $\hh{}$ pode apresentar \emph{resistência à pré-imagem} (\textsc{Pre}),
      caracterizada pelo seguinte comportamento: fornecido um resumo $h \in Y$,
        é computacionalmente inviável achar alguma mensagem original $m \in X$
        que gere $h$ através de $\hash{m} = h$;

  \item $\hh{}$ pode apresentar \emph{resistência à segunda pré-imagem}
      (\textsc{Sec}), caracterizada pelo seguinte comportamento: fornecida uma
        mensagem $m_{0} \in X$, é computacionalmente inviável achar uma
        mensagem $m_{1} \in X$ tal que $m_{0} \neq m_{1}$ e $\hash{m_{0}} =
        \hash{m_{1}}$;

  \item $\hh{}$ pode apresentar \emph{resistência à colisões} (\textsc{Col}),
      caracterizada pelo seguinte comportamento: é computacionalmente inviável
        encontrar duas mensagens $m_{0}, \; m_{1} \in X$ e $m_{0} \neq m_{1}$,
        de tal forma que $\hash{m_{0}} = \hash{m_{1}}$;

  \item $\hh{}$ pode ser parametrizada por uma chave $k$. Este comportamento é
      representado por $\hh{}_{k}$.

\end{enumerate}

A classificação de $\hh{}$ é realizada de acordo com a presença destas
propriedades, criando funções com várias aplicabilidades distintas. Funções de
resumo simples contêm apenas os três primeiros itens, e são utilizadas em
vários âmbitos, em especial na estrutura de dados chamada de tabela de
espalhamento. Por outro lado, é imposto para uma função de sentido único que os
itens (i), (ii) e (iv) sejam respeitados. Por fim, funções de sentido único
Adicionalmente resistentes à segunda pré-imagem e/ou colisões são definidas
como funções de resumo criptográfico, adequadas para utilização no contexto de
segurança da informação. Finalmente, a relação da propriedade (vii) com estas
funções é discutida na Subseção~\ref{subsection:const}.

Funções de resumo criptográfico possibilitam a certeza da integridade de dados,
mesmo que armazenados em um dispositivo inseguro. Intuitivamente, é desejável
que não ocorra uma relação aparente entre entradas e saídas da função,
considerando o resumo por completo e mesmo subpalavras deste. Outra
característica desejada é o efeito avalanche, baseado no conceito de
difusão~\cite[pp. 72]{Stallings:book:2010}: trocar apenas um \emph{bit} da
mensagem $m$ deve modificar cerca de metade dos \emph{bits} do resumo, e
vice-versa.

\begin{figure}
  \centering
  \begin{tikzpicture}
    \begin{scope}[fill opacity=0.5]
      \clip (0, 0) circle (1.25cm);
      \fill[black!35] (1.75, 0) circle (1.25cm);
      \fill[black!35] (1.75, 0) circle (0.75cm);
    \end{scope}
    \draw[draw=black!50, thick] (0, 0) circle (1.25cm) node {\textsc{Pre}};
    \draw[draw=black!50, thick] (1.75, 0) circle (1.25cm) node {};
    \draw[draw=black!50, thick] (1.75, 0) circle (0.75cm) node {\textsc{Col}};
    \draw node at (1.75, 1) {\textsc{Sec}};
  \end{tikzpicture}
  \caption{Diagrama de Venn das resistências desejáveis para uma função de
    resumo no contexto de assinaturas digitais.}\label{fig:venn}
\end{figure}

Na Figura~\ref{fig:venn}, estão destacados os requisitos comuns para a
utilização de funções de resumo no contexto de esquemas de assinatura digital,
em vista da possibilidade de uma entidade maliciosa, geralmente chamada de
adversário, desejar produzir assinaturas forjadas. Observe que, embora exista
uma divisão estrita entre \textsc{Pre} e \textsc{Sec}, efetivamente, a segunda
implica a primeira resistência~\cite[Nota 9.20]{Menezes:book:1996}.

Ademais, note que \textsc{Sec} e \textsc{Col} apresentam uma sutil diferença:
na primeira, um adversário não pode escolher $m_{0}$, enquanto na segunda,
quaisquer pares de mensagens podem ser testados. A resistência à colisões,
portanto, implica na resistência à segunda pré-imagem, visto que basta um
adversário fixar $m_{0}$ para simular o cômputo de $m_{1}$.

Enumeram-se algumas aplicações comuns para estas funções: a verificação da
integridade de um arquivo, \emph{i.e.} determinar se mudanças neste foram
feitas ao longo de uma transmissão, ou qualquer outro evento; a fim de evitar o
armazenamento de senhas em texto plano, mantêm-se apenas o resumo criptográfico
destas, e no momento da autenticação do usuário perante o serviço, comparar
apenas estes resumos\footnote{Tabelas de resumos computados previamente, ou
\emph{rainbow tables}, são armazenadas a fim de atacar serviços que não
empregam uma maneira mais elaborada de autenticação, \emph{e.g.} um valor
pseudoaleatório concatenado ao resumo criptográfico da senha do usuário.};
resumos criptográficos são comumente empregados como identificadores únicos
para um arquivo, \emph{e.g.} \emph{commits} em um sistema de controle de
versões; entre outras aplicações, como a geração de números pseudoaleatórios.

\subsection{Construção a partir de cifras de bloco}\label{subsection:const}

Uma nova função de sentido único pode ter origem em algoritmos conhecidos como
cifras de bloco, descritos como encadeamentos de operações matemáticas
aplicadas sobre um estado de \emph{bits} com tamanho fixo, geralmente chamado
de bloco. Estes algoritmos comportam-se como uma famíla de permutações
aleatórias parametrizados por uma chave, ou seja, o ``embaralhamento'' da
mensagem em texto plano para um texto cifrado dependerá completamente da chave
imposta sobre o algoritmo. Em especial, como visto em~\cite[Exemplo
9.13]{Menezes:book:1996}, cifras com esta estrutura podem ser transformadas em
funções de sentido único com a extensão da entrada limitado ao tamanho do
bloco.

A extensão deste artifício para funções de sentido único com compressão pode
ser realizada através de vários métodos. Destaca-se a construção
Matyas-Meyer-Oseas~\cite[Algoritmo 9.41]{Menezes:book:1996}, descrita a seguir.
Assuma uma cifra de blocos genérica $E_{k}$ parametrizada pela chave $k$, cujo
bloco tem um tamanho de $n$ \emph{bits}. Tome um vetor de inicialização $IV$ de
tamanho $n$, e uma função $g$ que adapte sua entrada para chaves do tamanho
necessário por $E_{k}$.

Deseja-se obter um resumo $h_{k}$ de tamanho $n$ que represente uma palavra
$x$, e que sua inversibilidade seja computacionalmente inviável. Deste modo,
divida $x$ em uma $k$-tupla cujos elementos têm tamanho $n$, ou seja, $X =
(x_{0}, \dots, x_{k - 1})$. Preenchimento com zeros pode ser aplicado caso
existam elementos que desrespeitem esta regra. O resultado deste processo é
definido recursivamente como
\begin{equation}
  \begin{split}
    h_{0} &= IV, \\
    h_{i} &= E_{g(h_{i - 1})}(x_{i}) \oplus x_{i}, 1 \leq i \leq t.
  \end{split}
\end{equation}

A partir deste alicerce, a construção
Merkle---Damgård~\cite{Merkle:phd:1979:jun}, base para as funções MD5,
SHA1\sigla{SHA}{\emph{Secure Hash Algorithm}} e SHA2, pode ser aplicada a fim
de construir uma função de resumo criptográfico convencional, através do
encadeamento de aplicações de funções de sentido único com compressão sobre
partes da mensagem de entrada. Este método deve também tratar a entrada
original para que o tamanho desta seja um múltiplo do tamanho do bloco, com uma
função de preenchimento, possivelmente contendo o tamanho da mensagem original
como forma de fortalecimento deste arcabouço em se tratando de características
de segurança.

\subsection{Construção esponja}\label{subsection:sponge}

A construção esponja~\cite{Bertoni:misc:2011a:jan}, de característica
iterativa, permite a generalização de funções de resumo, naturalmente com
saídas de tamanho fixo, para funções com saídas de tamanho arbitrário, baseadas
em uma função interna, geralmente uma permutação $f$ de tamanho fixo $b$. Este
valor, também chamado de largura, é composto da adição da taxa de \emph{bits}
$r$ e da capacidade $c$. Assim, a construção opera em um estado de $b = r + c$
\emph{bits}.

O estado inicial, análogo a um vetor de inicialização no contexto de algoritmos
criptográficos, não necessita de valores especiais e é ocupado com valores
nulos. A entrada $m$ é preenchida com uma função de preenchimento \texttt{pad}
de tal modo que $r \mid \length{m}$, e dividida em blocos de tamanho $r$. A
fase de absorção de $m$ pela esponja procede da seguinte maneira: a operação de
ou exclusivo é calculada entre os blocos e os estados da construção,
intercalados por aplicações de $f$.

\begin{figure}
  \centering
  \begin{tikzpicture}[scale=0.35]
    \begin{scope}[xshift=0cm]
      \draw (0, 0) rectangle ++(1, 10);
      \draw (0, 3) -- ++(1, 0);
      \node[XOR] (xm0) at (2.5, 8) {};
      \draw[->] (1, 8) -- (xm0);
      \draw[->] (1, 2) -- ++(3, 0);
      \draw[->] (2.5, 10.5) node[above] {\large $m_{0}$} -- (xm0);
      \draw[->] (xm0) -- ++(1.5, 0);
      \draw[<->, anchor=east] (-1, 3) -- node[left] {$r$} ++(0, 7);
      \draw[<->, anchor=east] (-1, 0) -- node[left] {$c$} ++(0, 3);
    \end{scope}
    \begin{scope}[xshift=4cm]
      \draw[rounded corners=4pt] (0, 0) rectangle node {\large$f$} ++(1, 10);
      \node (xm1) at (2.5, 8) {$\dots$};
      \draw[->] (1, 8) -- (xm1);
      \draw[->] (xm1) -- ++(1.5, 0);
      \node (xm1) at (2.5, 2) {$\dots$};
      \draw[->] (1, 2) -- (xm1);
      \draw[->] (xm1) -- ++(1.5, 0);
    \end{scope}
    \begin{scope}[xshift=8cm]
      \draw[rounded corners=4pt] (0, 0) rectangle node {\large$f$} ++(1, 10);
      \node[XOR] (xm1) at (2.5, 8) {};
      \draw[->] (1, 8) -- (xm1);
      \draw[->] (1, 2) -- ++(3, 0);
      \draw[->] (2.5, 10.5) node[above] {\large $m_{i}$} -- (xm1);
      \draw[->] (xm1) -- ++(1.5, 0);
    \end{scope}
    \begin{scope}[xshift=12cm]
      \draw[rounded corners=4pt] (0, 0) rectangle node {\large$f$} ++(1, 10);
      \draw[->] (1, 2) -- ++(3, 0);
      \draw[->] (1, 8) -- ++(3, 0);
    \end{scope}
    \begin{scope}[xshift=16cm]
      \draw (0, 0) rectangle ++(1, 10);
      \draw (0, 3) -- ++(1, 0);
      \draw[->] (1, 2) -- ++(3, 0);
      \draw[->] (1, 8) -- ++(3, 0);
      \draw[->] (2.5, 8) -- ++(0, 2.5) node[above] {\large $z_{0}$};
      \draw[dashed] (-1.5, -1.5) -- ++(0, 13);
    \end{scope}
    \begin{scope}[xshift=20cm]
      \draw[rounded corners=4pt] (0, 0) rectangle node {\large$f$} ++(1, 10);
      \node (xm1) at (2.5, 8) {$\dots$};
      \draw[->] (1, 8) -- (xm1);
      \draw[->] (xm1) -- ++(1.5, 0);
      \node (xm1) at (2.5, 2) {$\dots$};
      \draw[->] (1, 2) -- (xm1);
      \draw[->] (xm1) -- ++(1.5, 0);
    \end{scope}
    \begin{scope}[xshift=24cm]
      \draw[rounded corners=4pt] (0, 0) rectangle node {\large$f$} ++(1, 10);
      \draw[->] (1, 8) -- ++(1.5, 0)
        -- ++(0, 2.5) node[above] {\large $z_{j}$};
    \end{scope}
  \end{tikzpicture}
  \caption{Estrutura da construção esponja,
    onde $i, j \in \mathbb{N}^{*}$.}\label{fig:sponge}
\end{figure}

Ao término do processamento dos blocos, a fase de compressão é iniciada, onde
$n$ blocos de tamanho $r$ compõem a saída da função, novamente intercalados por
aplicações de $f$, onde $n$ é parametrizável pelo usuário. Os últimos $c$
\emph{bits} do estado nunca são diretamente afetados pelos blocos, e também
nunca revelados durante a fase de compressão. Essencialmente, estão
correlacionados com o nível de segurança da construção esponja. Assim, uma
função esponja pode ser definida como $\textsc{Sponge}[f, \texttt{pad}, r]$, e
sua representação gráfica pode ser consultada na Figura~\ref{fig:sponge},
adaptada de~\cite{Jean:misc:2016:apr}.

A função esponja \textsc{Keccak}~\cite{Bertoni:misc:2011b:jan} é definida a
partir desta construção, e pode agir como uma função de resumo criptográfico.
Existem sete permutações passíveis de utilização nesta função: defina $w =
2^{\ell}, \; \ell \in \{0, \dots, 6\}$. Estas são chamadas de
$\textsc{Keccak}-f[b]$, onde $b = 25w$, cujo estado $a$ é descrito como uma
estrutura tridimensional com elementos em $\mathbb{F}_{2}$, de dimensões $5
\times 5 \times w$. Esta permutação é iterativa e consiste de um número de
rodadas $n_{R} = 12 \times 2 \ell$. Cada rodada $R$, por sua vez, consiste da
composição de cinco etapas: $R = \iota \circ \chi \circ \pi \circ \rho \circ
\theta$.

\begin{enumerate}

  \item[] \emph{Etapa $\theta$.} Calcula o ou exclusivo entre um elemento de
      $a$ e todos os elementos das colunas adjacentes a este.

  \item[] \emph{Etapa $\rho$.} Dispersa os elementos entre cortes transversais
      verticais de $a$.

  \item[] \emph{Etapa $\pi$.} Rearranja elementos em cortes transversais
      horizontais de $a$.

  \item[] \emph{Etapa $\chi$.} Modifica um elemento de uma linha de $a$ de
      acordo com uma função não-linear de dois outros \emph{bits} adjacentes.
        Análogo a uma caixa-S.

  \item[] \emph{Etapa $\iota$.} Calcula o ou exclusivo entre o estado $a$ e uma
      sequência gerada por um \emph{linear-feedback shift
        register}\footnote{Conjunto de registradores que deslocam \emph{bits} a
        partir de funções lineares. Uma aplicação desta estrutura é a geração
        de números pseudoaleatórios.} alimentado pelo índice da rodada atual,
        tornando a rodada assimétrica.

\end{enumerate}

Tome \texttt{pad10*1} como uma função que gera palavras que iniciam e terminam
com $1$, e têm número não negativo de zeros. Formalmente, para uma mensagem
qualquer $m$ e um tamanho de saída $d \in \mathbb{N}^{*}$, a função esponja é
definida como
\begin{equation}
  \textsc{Keccak}[r, c](m, d)
    = \textsc{Sponge}[\textsc{Keccak}-f[r + c], \texttt{pad10*1}, r]
\end{equation}
onde $r$ tem um valor padrão de $1600 - c$. Assim,
\begin{equation}
  \textsc{Keccak}[c] = \textsc{Keccak}[1600 - c, c].
\end{equation}
Finalmente, as funções padronizadas em~\cite{Dworkin:report:2015:jul} como a
família SHA-3 são definições de \textsc{Keccak} com parâmetros fixos,
\emph{e.g.}
\begin{equation}
  \text{SHA3-}256(m) = \textsc{Keccak}[512](m \concat 01, 256).
\end{equation}\simbolo{$\concat$}{Concatenação de palavras}

\section{Esquemas de assinatura digital}\label{section:digitalsig}

Um esquema de assinatura digital é uma construção matemática que habilita a
demonstração de certas propriedades sobre mensagens assinadas: nomeadamente, a
autenticação do remetente, onde esta entidade pode ser facilmente identificada
como a emissora da assinatura digital; a integridade da mensagem, \emph{i.e.} a
certeza de que esta não foi modificada ao ser transmitida por um canal
possivelmente inseguro; e o não-repúdio do remetente, onde é impossível negar
que uma mensagem foi assinada e enviada, após este fato.

\begin{figure}
  \centering
  \begin{tikzpicture}
    \node (hm) at (-1.25, 0) {$m$};
    \node (in) at (0, -2) {$1^{n}$};
    \node (sk) at (0, -1) {$\sk{}$};
    \node (pk) at (4, -1) {$\pk{}$};
    \node (ds) at (2, 0) {$\sigma$};
    \node (res) at (5.5, 0) {\scriptsize $\binwds{}$};
    \node[draw] (sig) at (0, 0) {\textsc{Sig}};
    \node[draw] (gen) at (2, -2) {\textsc{Gen}};
    \node[draw] (ver) at (4, 0) {\textsc{Ver}};
    \draw[-latex] (gen) to (1.25, -1) to (sk);
    \draw[-latex] (gen) to (2.75, -1) to (pk);
    \draw[-latex] (sk) -- (sig);
    \draw[-latex] (hm) -- (sig);
    \draw[-latex] (sig) -- (ds);
    \draw[-latex] (ds) -- (ver);
    \draw[-latex] (pk) -- (ver);
    \draw[-latex] (ver) -- (res);
    \draw[-latex] (in) -- (gen);
  \end{tikzpicture}
  \caption{Funcionamento típico de um
    esquema de assinatura digital.}\label{fig:sign}
\end{figure}

Esquemas de assinatura digital são fortemente baseados em criptografia de
chaves públicas, e consistem de três algoritmos: a geração de chaves
$\textsc{Gen}(1^{n})$, que gera um par de chaves aleatório $(\pk{}, \sk{})$ com
parâmetro de segurança $n \in \mathbb{N}^{*}$; o algoritmo de assinatura
$\textsc{Sig}(\sk{}, m)$, que produz uma assinatura $\sigma$ para uma mensagem
$m$; e o algoritmo de verificação $\textsc{Ver}(\pk{}, m, \sigma)$, que retorna
o estado de validade da assinatura como um valor verdade binário. De acordo
com~\cite[Subseção 6.1.3]{Goldreich:book:2004}, todas as assinaturas geradas
por \textsc{Sig} devem ser verificáveis por \textsc{Ver} utilizando todas as
chaves geradas por \textsc{Gen}. Formalmente,
\begin{multline}
  \forall (p, s) \in \textsc{Gen}(1^{n}), \forall w \in \binwds{*}, \\
    \text{Pr}[\textsc{Ver}(p, w, \textsc{Sig}(s, w)) = 1] = 1.
\end{multline}
É necessário apontar que esta definição não considera a segurança do esquema,
visto que existem algoritmos construídos trivialmente que respeitam a equação
acima, sem qualquer tipo de codificação a fim de ocultar mensagens. Na
Figura~\ref{fig:sign}, é apresentada uma visualização do comportamento de um
esquema de assinatura digital genérico. Note que $\sigma$ geralmente é composta
da concatenação da mensagem original com a assinatura do resumo criptográfico
desta, embora a saída do algoritmo \textsc{Sig} consista apenas da aplicação de
uma função interna ao resumo.

\subsection{O criptossistema RSA}\label{subsection:rsa}

O algoritmo conhecido como
RSA~\cite{Rivest:article:1978:feb}\sigla{RSA}{\emph{Rivest---Shamir---Adleman}}
é uma implementação de criptografia assimétrica amplamente utilizada. É baseado
na dificuldade de fatorar o produto de dois números primos suficientemente
grandes\footnote{O algoritmo é baseado no problema RSA, definido como realizar
uma operação de chave privada no algoritmo RSA utilizando apenas $\pk{}$.
Acredita-se que este problema seja equivalente à fatoração de
inteiros~\cite[Fato 3.30]{Menezes:book:1996}.}. Em virtude de seu baixo
desempenho computacional, geralmente apenas um resumo criptográfico da mensagem
desejada é codificado por este algoritmo, e sua transmissão é realizada junto à
mensagem original, de forma concatenada. Abaixo, uma descrição do funcionamento
do algoritmo. Tome $\phi(x)$ como a função totiente de Euler, que representa a
quantidade de números relativamente primos a $x$.

\begin{enumerate}

  \item[] \emph{Geração de chaves.} Gere dois números primos $p, q$
      aleatoriamente, suficientemente grandes e de tamanhos similares. Compute
        $n = p q$ e $\phi(n) = (p - 1) (q - 1)$. Selecione um número aleatório
        $e$ relativamente primo a $\phi(n)$. Então, use o algoritmo de Euclides
        estendido para computar $d$ tal que $ed \equiv 1 \pmod{\phi(n)}$,
        \emph{i.e.} a inversa multiplicativa modular de $e$. Finalmente,
        \begin{align}
          \begin{split}
            \sk{} &= d, \\
            \pk{} &= (n, e).
          \end{split}
        \end{align}

  \item[] \emph{Geração da assinatura.} Para assinar uma mensagem, aplique uma
      função de resumo criptográfico $\hh{}$ à mensagem $M$, produzindo $h =
        \hash{M}$. O texto cifrado $c = h^{d} \pmod{n}$ é calculado e enviado
        para a entidade desejada na forma
        \begin{equation}
          \sigma = M \concat c.
        \end{equation}

  \item[] \emph{Verificação da assinatura.} O receptor da mensagem isola o
      resumo cifrado $c$ de $\sigma$, e verifica a assinatura com sucesso se
      \begin{equation}
        h = c^{e} \pmod{n}.
      \end{equation}

\end{enumerate}

Para demonstrar $m^{ed} \equiv m \pmod{n}$, é suficiente mostrar que $m^{ed}
\equiv m \pmod{p}$ e $m^{ed} \equiv m \pmod{q}$, pelo Teorema Chinês do Resto.
Se $m \equiv 0 \pmod{p}$, então $mdc(m, p) = p$ e certamente $m^{ed} \equiv 0
\equiv m \pmod{n}$.  Se $m \not\equiv 0 \pmod{p}$, então $mdc(m, p) = 1$ e pelo
Pequeno Teorema de Fermat, $m^{p - 1} \equiv 1 \pmod{p}$. Reescrevendo o
produto $ed$ como
\begin{equation}
  ed = 1 + y\phi(n) = 1 + y(p - 1)(q - 1), \; y \in \mathbb{N},
\end{equation}
então
\begin{multline}
  m^{ed} \equiv m^{1 + y(p - 1)(q - 1)}
    \equiv {(m^{p - 1})}^{y(q - 1)}m \\
    \equiv 1^{y(q - 1)}m \equiv m \pmod{p}.
\end{multline}
Analogamente, o processo acima pode ser aplicado para o inteiro $q$. Portanto,
$\forall m \in \mathbb{N}, \; m^{ed} \equiv m \pmod{n}$.

Observe que uma descrição do algoritmo acima sem a presença de uma função de
resumo criptográfico apresenta sérios problemas de segurança se aplicada de
maneira ingênua. Defina a noção de segurança semântica como, dado um texto
cifrado, a impossibilidade de revelar informações quaisquer sobre seu texto
plano correspondente~\cite{Goldwasser:inproc:1982:may}. Então, note que
não existe qualquer fator aleatório na assinatura da mensagem, habilitando uma
entidade maliciosa a aplicar um ataque de texto plano escolhido, \emph{i.e.} a
codificação de múltiplas mensagens a fim de descobrir informações sobre o
algoritmo baseado em semelhanças entre as mensagens cifradas. A função $\hh{}$
previne este comportamento por conta de sua ampla difusão.

Ademais, este criptossistema é um exemplo adequado para a discussão entre
codificação e assinatura de mensagens. Esta sutil diferença ocorre na
utilização do par de chaves. A codificação de um dado com a chave pública
impede que entidades externas à comunicação consigam ler o texto cifrado,
entretanto, é impossível afirmar algo sobre a identidade do remetente da
mensagem, ou o próprio conteúdo desta. Por outro lado, a assinatura de um dado
com a chave privada implica que o signatário é detentor deste par de chaves, e
isto pode ser verificado por qualquer indivíduo que possua a chave pública
correspondente, livremente distribuída.

\chapter{Assinatura digital baseada em
  funções de resumo criptográfico}\label{chapter:hashsig}

Neste capítulo, os esquemas de assinatura digital baseados em funções de resumo
criptográfico mais reconhecidos são apresentados, a fim de contextualizar a
presença do esquema alvo, Winternitz, neste meio. Nomeadamente, a
Seção~\ref{section:onetime} introduz o conceito de assinaturas únicas e fornece
discussões sobre os esquemas \lots{}\sigla{\lots{}}{\emph{Lamport---Diffie
One-time Signature Scheme}}, \wots{}\sigla{\wots{}}{\emph{Winternitz One-time
Signature Scheme}} e \wotsplus{}, respectivamente nas
Subseções~\ref{subsection:ldots},~\ref{subsection:wots}
e~\ref{subsection:wotsplus}. Adicionalmente, o esquema de poucas assinaturas
\hors{} é explorado na Subseção~\ref{subsection:hors}. Por fim, os esquemas
baseados em árvores de Merkle são definidos na Seção~\ref{section:merkle}, e os
exemplos \mss{}\sigla{\mss{}}{\emph{Merkle Signature Scheme}}, \xmss{} e
\xmssmt{} são dirimidos nas
Subseções~\ref{subsection:mss},~\ref{subsection:xmss}
e~\ref{subsection:xmssmt}. Finalmente, a Seção~\ref{section:timeline} abrange
uma visão cronológica dos esquemas discutidos ao longo deste Capítulo.

\section{Esquemas de assinatura única}\label{section:onetime}

Esquemas de assinatura única, ou \emph{one-time signature schemes},
possibilitam a assinatura de apenas uma mensagem, facilitando a falsificação
deste processo no caso da reutilização do par de chaves. São construções
fundamentais para a criação de esquemas baseados apenas em funções de resumo
criptográfico, visto que vários esquemas continuam utilizando este recurso e
compõem o estado da arte da
literatura~\cite{Bernstein:misc:2017:dec,Huelsing:report:2018:may}.

\subsection{\lots{}}\label{subsection:ldots}

A utilização de funções de resumo criptográfico para a criação de esquemas de
assinatura digital foi iniciada por Lamport~\cite{Lamport:report:1979:oct} e
estendida subsequentemente em~\cite{Diffie:article:1976:sep,
Merkle:inproc:1989:aug}, permitindo assinar um \emph{bit} de cada vez para uma
dada mensagem. O par de chaves consiste de um par de palavras pseudoaleatórias
$x_{0}, x_{1}$ como $\sk{}$, e seus resumos como $\pk{}$. O assinante assina um
\emph{bit} $b$ distribuindo $x_{b}$, e o recipiente verifica se $\hash{x_{b}}$
é o valor correto em $\pk{}$. Como parte de $\sk{}$ é distribuída, não é
recomendável reutilizar o par de chaves, e os elementos não distribuídos devem
ser destruídos. Assinar mensagens mais longas envolve o cálculo do resumo
desta, visto que do contrário, o tamanho do par de chaves e assinaturas
torna-se extremamente proibitivo.

Formalmente, tome um parâmetro de segurança $m \in \mathbb{N}$, geralmente
considerado como o tamanho da saída da função de resumo criptográfico
escolhido. Considere as funções\footnote{Na prática, o esquema pode ser
instanciado utilizando $\hh{}$ no lugar de $f$.} de sentido único $f : \binwds{m}
\longrightarrow \binwds{m}$ e de resumo criptográfico $\fhash{m}$. Seu
funcionamento e algumas de suas características são discutidas abaixo.

\begin{enumerate}

  \item[] \emph{Geração de chaves.} Defina
      \begin{equation}
        \sk{} = (x_{0, m - 1}, x_{1, m - 1}, \dots, x_{0, 0}, x_{1, 0})
          \random{} \binwds{(m, 2m)}
      \end{equation}
        como a chave privada.\simbolo{$\random{}$}{Seleção aleatória} A chave
        pública $\pk{}$ é derivada de $\sk{}$,\simbolo{$\Sigma^{(l, t)}$}{Todas
        as $t$-tuplas de palavras de tamanho $l$ construídas com $\Sigma$}
        computando $f(x) \; \forall x \in \sk{}$. Logo,
        \begin{align}
          \pk{} &= (f(x_{0, m - 1}), f(x_{1, m - 1}),
            \dots, f(x_{0, 0}), f(x_{1, 0})) \\
                &= (y_{0, m - 1}, y_{1, m - 1},
            \dots, y_{0, 0}, y_{1, 0}).
        \end{align}

  \item[] \emph{Geração da assinatura.} Tome uma mensagem $M$ e calcule $d =
      \hash{M}$. O resumo $d$ pode ser representado como $d_{m - 1} \dots
        d_{0}$. A assinatura consiste de elementos de $\sk{}$ operados por $f$
        de acordo com $d$:
        \begin{equation}
          \sigma = (f(x_{d_{m - 1}, m - 1}), \dots, f(x_{d_{0}, 0})).
        \end{equation}

  \item[] \emph{Verificação da assinatura.} Para assegurar a corretude da
      assinatura $\sigma$, todos os blocos de $\sigma$ precisam ser verificados
        separadamente através do recálculo de $d = d_{m - 1} \dots d_{0}$, para
        que os elementos corretos de $\pk{}$ sejam escolhidos. Assim, $\sigma$
        está correta se
        \begin{equation}
          (\sigma_{m - 1}, \dots, \sigma_{0})
            = (y_{d_{m - 1}, m - 1}, \dots, y_{d_{0}, 0}).
        \end{equation}

\end{enumerate}

É necessário comentar que assinaturas produzidas por este esquema podem ser
forjadas~\cite[Capítulo 3]{Merkle:inproc:1989:aug}, visto que é possível
computar $f$ para os \emph{bits} da mensagem que são iguais a zero. Assim, uma
soma de verificação representando a quantidade de zeros na mensagem original
também é assinada e enviada ao recipiente, adicionando apenas $m \cdot
\log_2(m)$ \emph{bits} na assinatura. Esta característica será explicada em
mais detalhes no próximo esquema.

Ademais, uma otimização simples para reduzir o tamanho de $\sk{}$ pode ser
implementada através da utilização de um gerador de números pseudoaleatórios
criptograficamente seguro. Assim, é necessário apenas guardar uma palavra de
tamanho $m$ que age como a semente deste gerador. No caso de $\pk{}$, basta
guardar o resumo criptográfico de seus valores concatenados. Reduzir o tamanho
das assinaturas exige soluções mais complexas; entretanto, a generalização
deste esquema permite esta otimização.

\subsection{\wots{}}\label{subsection:wots}

A introdução de um parâmetro que habilita compensar a criação de chaves e
assinaturas menores com uma diminuição no desempenho do esquema foi sugerida
por Winternitz e publicada por Merkle~\cite[Capítulo
5]{Merkle:inproc:1989:aug}. Este esquema permite assinar múltiplos \emph{bits}
em cada bloco da assinatura, generalizando a proposta de Lamport. A definição
do esquema é elaborada abaixo e seu funcionamento é representado na
Figura~\ref{fig:wots}.

Um parâmetro de segurança $m$ é necessário, como acima. O parâmetro Winternitz,
da forma $w \in \mathbb{N}^{*}\setminus\{1\}$, também deve ser definido, que
representa a quantidade de \emph{bits} a serem assinados simultaneamente. A
partir destes, são calculados os valores \[t_{1} = \left\lceil \frac{m}{w}
\right\rceil, \; t_{2} = \left\lceil \frac{\left\lfloor \log_2 t_{1}
\right\rfloor + 1 + w}{w} \right\rceil \text{ e } t = t_{1} + t_{2},\] que
representarão, respectivamente, a quantidade de palavras em base-$w$ na
assinatura referente à mensagem, à soma de verificação, e à quantidade total.
Por fim, considere as funções de sentido único $f : \binwds{m} \longrightarrow
\binwds{m}$ e de resumo criptográfico $\fhash{m}$.

\begin{enumerate}

  \item[] \emph{Geração de chaves.} Defina
      \begin{equation}
        \sk{} = (x_{t - 1}, \dots, x_{0}) \random{} \binwds{(m, t)}
      \end{equation}
        como a chave privada. A chave pública $\pk{} = (y_{t - 1}, \dots,
        y_{0})$ pode ser derivada de $\sk{}$, computando $f^{2^{w}-1}(x) \;
        \forall x \in \sk{}$\simbolo{$f^{\alpha}$}{Aplicação de $f$ $\alpha$
        vezes}. Logo,
        \begin{equation}
          \pk{} = (f^{2^{w}-1}(x_{t - 1}), \dots, f^{2^{w}-1}(x_{0})).
        \end{equation}

  \item[] \emph{Geração da assinatura.} Tome uma mensagem $M$ e calcule $d =
      \hash{M}$. Por conveniência, $m$ ou $w$ são escolhidos de forma que $w
        \mid m$, mas podem ser concatenados zeros ao resumo para que esta
        restrição seja satisfeita. O resumo $d$ é dividido em uma $t_{1}$-tupla
        de palavras em base-$w$, $\bone = (b_{t - 1}, \dots, b_{t - t_{1}})$.
        Adicionalmente, uma soma de verificação é calculada usando a
        representação inteira dos elementos de $\bone{}$: $c = \sum_{b \in
        \bone{}} 2^{w} - 1 - b$. Novamente, $c$ pode ser arredondado com zeros
        até que $w \mid \length{c}$. Finalmente, $c$ é dividido em uma
        $t_{2}$-tupla de palavras base-$w$, $\btwo{} = (b_{t_{2}-1}, \dots,
        b_{0})$. Assim, $\mathcal{B} = \bone{} \cup \btwo{}$ e
        \begin{equation}
          \sigma = (f^{b_{t - 1}}(x_{t - 1}), \dots, f^{b_{0}}(x_{0})).
        \end{equation}

  \item[] \emph{Verificação da assinatura.} Para assegurar a corretude da
      assinatura $\sigma$, todos os blocos $\sigma_{i}$ precisam ser
        verificados separadamente através do cálculo das aplicações restantes
        de $f$. Assim, computando $\mathcal{B}$ novamente, $\sigma$ está
        correta se
        \begin{equation}
          \pk{} = (f^{2^{w} - 1 - b_{t - 1}}(\sigma_{t - 1}),
            \dots, f^{2^{w} - 1 - b_{0}}(\sigma_{0})).
        \end{equation}

\end{enumerate}

Note que não é possível decrementar valores $b_{i} \in \mathcal{B}$, pois isto
implicaria em achar uma pré-imagem de $f$, o que é computacionalmente inviável
em vista de sua restrição imposta. Então, resta apenas a tentativa da
falsificação de $\sigma$ incrementando algum valor $b_{i}$. A soma de
verificação $c$ é necessária a fim de proteger o esquema contra esta situação.
Observe que, em sua ausência, a criação de assinaturas $\sigma'$ por uma
entidade maliciosa é permitida, apenas através do cálculo de mais iterações de
$f$ em blocos da assinatura $\sigma$. Entretanto, com a presença de $c$, e
consequentemente $\btwo{}$, ao modificar um valor $b_{j} \in \bone{}$, para que
o valor correto de $\btwo{}$ seja mantido, é necessário que uma pré-imagem de
algum bloco $b_{k} \in \btwo{}$ seja calculada. Analogamente, modificar algum
valor de $\btwo{}$ também tornará a verificação da assinatura impossível.

\begin{figure}
  \centering
  \begin{tikzpicture}[
    decoration={
      markings, mark=at position 0.5 with {\node[font=\scriptsize] {/};},
      mark=at position 0.5 with {\node[font=\scriptsize, yshift=10pt] {m};}
    }
  ]
    \matrix[matrix of nodes, column sep=35pt, row sep=30pt] {
      \node [draw, minimum width=30pt, minimum height=30pt]
        (xt1) {$x_{i}$}; &
      \node (fst1) {$f(x_{i})$}; &
      \node [draw, minimum width=30pt, minimum height=30pt]
        (st1) {$\sigma_{i}$}; &
      \node (fvt1) {$f(\sigma_{i})$}; &
      \node [draw, minimum width=30pt, minimum height=30pt]
        (yt1) {$y_{i}$}; \\
    };

    \node[above=5pt of xt1] (X) {$x_{i} \in X:$};
    \node[above=5pt of st1] (S) {$\sigma_{i} \in \sigma:$};
    \node[above=5pt of yt1] (Y) {$y_{i} \in Y:$};

    \path[draw, -latex', postaction={decorate}] (xt1) -- (xt1 -| fst1.west);
    \path[draw, -latex', postaction={decorate}] (fst1.east |- st1) -- (st1);
    \path[->] (fst1) edge [loop above] node {\scriptsize$b_{i}$} ();
    \path[draw, -latex', postaction={decorate}] (st1) -- (st1 -| fvt1.west);
    \path[draw, -latex', postaction={decorate}] (fvt1.east |- yt1) -- (yt1);
    \path[->] (fvt1) edge [loop above] node {\scriptsize$2^{w} - 1 - b_{i}$} ();
  \end{tikzpicture}
  \caption{Etapas de assinatura e verificação do \wots{},
    para $0 \leq i \leq t - 1$.}\label{fig:wots}
\end{figure}

Diversas variantes do \wots{} foram propostas com o intuito de reduzir
requisitos de segurança, tamanhos de chaves e assinaturas, e tornar os
processos de geração e verificação de assinaturas menos onerosos. Nomeadamente,
para um ataque que consiste em ameaçar múltiplos usuários, cada qual com seu
par de chaves, a possibilidade de sucesso aumenta de acordo com o subconjunto
de instâncias almejado. Um esquema que combate especificamente este problema,
chamado de \wotst{}\sigla{\wotst{}}{\emph{Winternitz One-time Signature Scheme
with Tight security}}, pode ser consultado em~\cite{Huelsing:inproc:2016:mar}.

Ademais, encontra-se em processo de padronização pela
IETF\sigla{IETF}{\emph{Internet Engineering Task Force}} outro esquema que
combate este tipo de ataque, chamado
\wotslm{}\sigla{\wotslm{}}{\emph{Leighton---Micali---Winternitz One-time
Signature Scheme}}, publicado originalmente como uma patente
estadunidense~\cite{Leighton:misc:1995:jul}, desta maneira buscando trazer a
assinatura digital baseada em funções de resumo criptográfico para aplicações
práticas. Em especial, para resolver o problema supracitado, os
autores~\cite{McGrew:report:2018:apr} buscam introduzir identificadores únicos
para cada instância do esquema, modificando essencialmente a estrutura da
função $f$, assim combatendo ataques multiusuário.

\subsection{\wotsplus{}}\label{subsection:wotsplus}

O principal esquema da família Winternitz tem como ideia principal a reposição
de $f$ por uma família de funções $\mathcal{F}_{k}$, substituindo o processo de
iterações sequenciais do esquema original~\cite{Huelsing:inproc:2013:sep}, que
utilizam apenas uma função. Esta característica também permite uma prova de
segurança mais simples, mas não menos poderosa, que desconsidera a necessidade
da resistência à colisões de $f$ e $\hh{}$.

Defina os parâmetros $m, w$ e a partir destes, $t_{1}, t_{2} \text{ e } t$, bem
como a função de resumo criptográfico $\fhash{m}$ de maneira análoga ao esquema
original. A família de funções que o \wotsplus{} utiliza é definida por
\[\mathcal{F}_{m} : \{f_{k} : \binwds{m} \longrightarrow \binwds{m} \mid k \in
\mathcal{K}_{m}\},\] ou seja, funções de sentido único sem compressão, e
$\mathcal{K}_{m}$ é interpretado como o espaço de chaves. A partir desta
família, e de uma tupla de palavras pseudoaleatórias \[r = (r_{0}, \dots,
r_{2^{w} - 1}) \random{} \binwds{(m, 2^{w})},\] a nova função de iteração
$c^{i}_{k}(x, r)$ é definida recursivamente como
\begin{equation}
  \begin{split}
    c^{0}_{k}(x, r) &= x, \\
    c^{i}_{k}(x, r) &= f_{k}(c^{i - 1}_{k}(x, r) \oplus r_{i}).
  \end{split}
\end{equation}

\begin{enumerate}

  \item[] \emph{Geração de chaves.} Defina $\sk{}$ e $r$ como tuplas de
      inteiros pseudoaleatórios, discutidos anteriormente. O algoritmo também
        deve escolher uma chave de função $k \random{} \mathcal{K}$. Por fim,
        \begin{equation}
          \pk{} = (c^{2^{w}-1}_{k}(x_{t - 1}, r), \dots, c^{0}_{k}(x, r)).
        \end{equation}

  \item[] \emph{Geração da assinatura.} Tome uma mensagem $M$, calcule o seu
      resumo $d = \hash{M}$ e a soma de verificação $c$ correspondente,
        produzindo $\mathcal{B}$. As considerações sobre preenchimento de $m$ e
        $c$ ainda se aplicam. Aplicando a nova função de iteração, tem-se
        \begin{equation}
          \sigma = (c^{b_{t - 1}}_{k}(x_{t - 1}, r),
            \dots, c^{b_{0}}_{k}(x_{0}, r)).
        \end{equation}

  \item[] \emph{Verificação da assinatura.} Novamente, é necessário calcular
      $\mathcal{B}$ para obter as iterações restantes até $\pk{}$. Note que as
        primeiras $b_{i}$ palavras de $r$ não serão utilizadas. Assim, $\sigma$
        está correta se
        \begin{equation}
          \pk{} = (c^{2^{w} - 1 - b_{t - 1}}_{k}(\sigma_{t - 1}, r),
            \dots, c^{2^{w} - 1 - b_{0}}_{k}(\sigma_{0}, r)).
        \end{equation}

\end{enumerate}

Note que a utilização de uma função conhecida, como a cifra AES explicada no
Apêndice~\ref{chapter:aes}, para o cálculo de iterações de $f$ é factível,
conforme sugerido em~\cite[Subseção 4.1]{Huelsing:inproc:2013:jun}. O método
Matyas-Meyer-Oseas explicado na Subseção~\ref{subsection:const} é utilizado
para que esta cifra seja adaptada, a fim de torná-la uma função da forma
necessária pelo esquema \wotsplus{}. Deste modo, implementações em hardware de
rotinas relacionadas, como o conjunto de instruções
AES-NI\sigla{AES-NI}{Advanced Encryption Standard New Instructions} provido por
processadores x86 recentes, podem ser aproveitados, resultando em um grande
ganho de desempenho no cômputo de $f$.

\subsection{\hors{}}\label{subsection:hors}

Os esquemas discutidos até agora sofrem da mesma limitação: a exposição
considerável de elementos relacionados diretamente com $\sk{}$, habilitando a
falsificação de assinaturas caso esta seja mantida. No caso de Lamport, metade
dos valores são diretamente escolhidos como a assinatura, e em Winternitz,
cadeias de resumos são diretamente computadas sobre todos os elementos de
$\sk{}$. Portanto, é desejável que esta exposição seja reduzida.

Para tal, a ideia de esquemas de ``poucas assinaturas'', ou \emph{few-time
signature schemes}, foi introduzida originalmente
em~\cite{Perrig:inproc:2001:nov} com o esquema \emph{Bins and Balls}, uma
aplicação do problema homônimo em probabilidade. Este trabalho é
subsequentemente generalizado e otimizado em~\cite{Reyzin:inproc:2002:jul} na
forma do esquema \hors{}\sigla{\hors{}}{\emph{Hash to Obtain Random Subset}},
onde o conteúdo da mensagem controla a seleção de elementos em uma lista de
inteiros trivial, construindo subconjuntos distintos, distribuídos como
assinaturas.

De acordo com a definição original, tome os parâmetros $t, k \in \mathbb{N}, t
\gg k$\simbolo{$\gg$}{Muito maior que}, e $t$ como uma potência de 2. O tamanho
dos pares de chaves e das assinaturas são fortemente relacionados com,
respectivamente, $t$ e $k$. O parâmetro de segurança $m = k \times \log_2 t$
garante que existam subconjuntos suficientes para todos os resumos possíveis.
Seja o conjunto sequencial $T = \{0, \dots, t - 1\}$, a função de sentido único $f
: \binwds{m} \longrightarrow \binwds{m}$ e a função de resumo criptográfico
$\fhash{m}$.

A função $\hh{}$ utilizada deve apresentar também a característica de
resiliência a subconjuntos de tamanho $r$, ou seja, deve ser computacionalmente
inviável para um atacante, fornecidas $r$ mensagens $(m_{1}, \dots, m_{r})$,
encontrar $r + 1$ mensagens tais que
\begin{equation}
  \hash{m_{r + 1}} \subseteq \bigcup^{r}_{i = 1} \hash{m_{i}}.
\end{equation}
De outra forma, a probabilidade de que $r$ assinaturas contenham valores que
sejam mapeados para um resumo novo é desprezível. A escolha de $r$ não é
diretamente discutida, visto que uma função de resumo criptográfico usual provê
esta característica para valores suficientemente pequenos~\cite[Apêndice
A]{Reyzin:inproc:2002:jul}.

\begin{enumerate}

  \item[] \emph{Geração de chaves.} Defina $X = (x_{t - 1}, \dots, x_{0})
      \random{} \binwds{(m, t)}$, e adicione $k$ para obter a chave privada.
        Portanto,
        \begin{equation}
          \sk{} = (k, x_{t - 1}, \dots, x_{0}).
        \end{equation}
        Aplique $f$ em todos os elementos aleatórios para obter a chave
        pública, \emph{i.e.}
        \begin{equation}
          \pk{} = (k, f(x_{t - 1}), \dots, f(x_{0})),
        \end{equation}
        ou $\pk{} = (k, y_{t - 1}, \dots, y_{0})$.

  \item[] \emph{Geração da assinatura.} Tome uma mensagem $M$, calcule o seu
      resumo $d = \hash{M}$, e represente-o como uma $k$-tupla de palavras em
        base-$t$, ou seja, $\mathbf{d} = (d_{k - 1}, \dots, d_{0})$. A
        assinatura é composta dos elementos de $\sk{}$ escolhidos pela
        representação inteira dos elementos de $\mathbf{d}$, ou seja,
        \begin{equation}
          \sigma = (x_{d_{k - 1}}, \dots, x_{d_{0}}).
        \end{equation}

  \item[] \emph{Verificação da assinatura.} Recalcule $\mathbf{d}$ a partir da
      mensagem $M$, e assegure a corretude da assinatura $\sigma$ para cada
        bloco:
        \begin{equation}
          y_{d_{i}} = f(\sigma_{i}), \; 0 \leq i \leq k - 1.
        \end{equation}

\end{enumerate}

\begin{figure}
  \centering
  \begin{tikzpicture}
    \node (hm) at (-2, -1) {$M$};
    \node (d) at (6.5, -0.15) {$d$};
    \node[draw, dashed, minimum width=20em, minimum height=2.5em]
      (dbox) at (3, -1) {};
    \node[draw, minimum width=3em, minimum height=1.75em]
      (d0) at (0.5, -1) {$d_{0}$};
    \node[minimum width=1.5em, minimum height=1.75em, right=2pt of d0]
      (d1) {$\dots$};
    \node[draw, minimum width=3em, minimum height=1.75em, right=2pt of d1]
      (d2) {$d_{i - 1}$};
    \node[draw, minimum width=3em, minimum height=1.75em, right=7.5pt of d2]
      (d3) {$d_{i}$};
    \node[minimum width=1.5em, minimum height=1.75em, right=2pt of d3]
      (d4) {$\dots$};
    \node[draw, minimum width=3em, minimum height=1.75em, right=2pt of d4]
      (d5) {$d_{k - 1}$};
    \draw[-latex] (hm) -- (dbox) node[midway, above=1pt] {$\hh{}$};

    \node (sk) at (6.75, -2.4) {$\sk{}$};
    \node[draw, dashed, minimum width=23em, minimum height=2.5em]
      (skbox) at (3, -3.25) {};
    \node[draw, minimum width=3em, minimum height=1.75em]
      (x0) at (-0.3, -3.25) {$x_{0}$};
    \node[minimum width=1.5em, minimum height=1.75em, right=2pt of x0]
      (x1) {$\dots$};
    \node[draw, minimum width=3em, minimum height=1.75em, right=2pt of x1]
      (x2) {$x_{j}$};
    \node[minimum width=1.5em, minimum height=1.75em, right=2pt of x2]
      (x3) {$\dots$};
    \node[minimum width=1.5em, minimum height=1.75em, right=2pt of x3]
      (x4) {$\dots$};
    \node[draw, minimum width=3em, minimum height=1.75em, right=2pt of x4]
      (x5) {$x_{l}$};
    \node[minimum width=1.5em, minimum height=1.75em, right=2pt of x5]
      (x6) {$\dots$};
    \node[draw, minimum width=3em, minimum height=1.75em, right=2pt of x6]
      (x7) {$x_{t - 1}$};
    \draw[-latex, dash dot] (d0) -- (x5);
    \draw[-latex, dash dot] (d2) -- (x5);
    \draw[-latex, dash dot] (d5) -- (x0);
    \draw[-latex, dash dot] (d3) -- (x2);

    \node (sig) at (6.25, -4.7) {$\sigma$};
    \node[draw, dashed, minimum width=20em, minimum height=2.5em]
      (sigbox) at (3, -5.5) {};
    \node[draw, minimum width=3em, minimum height=1.75em]
      (s0) at (0.5, -5.5) {$\sigma_{0}$};
    \node[minimum width=1.5em, minimum height=1.75em, right=2pt of s0]
      (s1) {$\dots$};
    \node[draw, minimum width=3em, minimum height=1.75em, right=2pt of s1]
      (s2) {$\sigma_{i - 1}$};
    \node[draw, minimum width=3em, minimum height=1.75em, right=7.5pt of s2]
      (s3) {$\sigma_{i}$};
    \node[minimum width=1.5 em, minimum height=1.75em, right=2pt of s3]
      (s4) {$\dots$};
    \node[draw, minimum width=3em, minimum height=1.75em, right=2pt of s4]
      (s5) {$\sigma_{k - 1}$};
    \draw[-latex] (x0) -- (s0);
    \draw[-latex] (x2) -- (s2);
    \draw[-latex] (x5) -- (s3);
    \draw[-latex] (x5) -- (s5);
  \end{tikzpicture}
  \caption{Assinatura no \hors{}, para $0 \leq i \leq k - 1, \; 0 \leq j, l
    \leq t - 1$.}\label{fig:hors}
\end{figure}

Parte deste processo é visualizado na Figura~\ref{fig:hors}. Note que uma
conversão de palavras binárias para inteiros está implícita no diagrama, como
setas com preenchimento irregular, e que elementos $d_{i}$ podem ter valores
iguais, \emph{e.g.} ${(d_{0})}_{10} = {(d_{i - 1})}_{10} = l$. Percebe-se, a
partir da descrição dos algoritmos, que o tamanho do par de chaves é proibitivo
para aplicações práticas. Para tal, o algoritmo
\horst{}\sigla{\horst{}}{\emph{Hash to Obtain Random Subset with Trees}} é
proposto em~\cite[Capítulo 1]{Bernstein:inproc:2015:apr}, cuja definição faz
uso das estruturas explicadas na Seção~\ref{section:merkle}, a fim de reduzir
substancialmente o tamanho de $\pk{}$.

\section{Esquemas baseados em árvores de Merkle}\label{section:merkle}

A criação de um par de chaves para cada mensagem, bem como a infraestrutura
necessária para relacionar múltiplas chaves a uma entidade, podem tornar-se
processos extremamente onerosos. Desse modo, assim como esquemas de assinatura
digital clássicos, é desejável que uma chave privada possa assinar múltiplos
documentos. No contexto de esquemas baseados em funções de resumo
criptográfico, a estrutura de dados chamada de árvore de Merkle, geralmente de
característica binária e perfeita, pode ser aproveitada para tal.

\begin{figure}
  \centering
  \begin{tikzpicture}[
    every tree node/.style={align=center, anchor=north}, level distance=45pt,
    sibling distance=25pt
  ]
    \Tree
      [.\node{$T_{2, 0}$ \\ $\hash{T_{1, 0} \concat T_{1, 1}}$};
        [.\node{$T_{1, 0}$ \\ $\hash{T_{0, 0} \concat T_{0, 1}}$};
          [.{$T_{0, 0}$ \\ $\hash{\mathcal{D}_{0}}$}
            \edge[<-, dashed] node {}; $\mathcal{D}_{0}$
          ]
          [.{$T_{0, 1}$ \\ $\hash{\mathcal{D}_{1}}$}
            \edge[<-, dashed] node {}; $\mathcal{D}_{1}$
          ]
        ]
        [.\node{$T_{1, 1}$ \\ $\hash{T_{0, 2} \concat T_{0, 3}}$};
          [.{$T_{0, 2}$ \\ $\hash{\mathcal{D}_{2}}$}
            \edge[<-, dashed] node {}; $\mathcal{D}_{2}$
          ]
          [.{$T_{0, 3}$ \\ $\hash{\mathcal{D}_{3}}$}
            \edge[<-, dashed] node {}; $\mathcal{D}_{3}$
          ]
        ]
      ]
  \end{tikzpicture}
  \caption{Árvore de Merkle $T$, com altura $H = 2$.}\label{fig:merkle}
\end{figure}

De modo genérico, folhas de uma árvore de Merkle são construídas a partir do
resumo criptográfico de dados que desejam ser inseridos nesta. Então, pais
destas folhas computarão o resumo criptográfico do valor dos resumos de seus
filhos concatenados, repetindo este processo até que a raiz seja preenchida,
como na Figura~\ref{fig:merkle}. Considere uma árvore binária perfeita $T$ de
altura $H \in \mathbb{N}^{*}\setminus\{1\}$, onde um nodo é representado por
\begin{equation}
  T_{h, j}, \; 0 \leq h \leq H, \; 0 \leq j \leq 2^{H - h} - 1,
\end{equation}
e uma função de resumo criptográfico $\fhash{m}$. As folhas são construídas a
partir do resumo de qualquer dado $\mathcal{D}$, e seus nós intermediários a
partir de seus filhos:
\begin{equation}
  \begin{split}
    T_{0, j} &= \hash{\mathcal{D}_{j}}, \text{ e } \\
    T_{h, j} &= \hash{T_{h - 1, 2j} \concat T_{h - 1, 2j + 1}},
      \; 1 \leq h \leq H.
  \end{split}
\end{equation}
Esta estrutura também pode ser utilizada para verificação conjunta da
integridade de múltiplos arquivos, \emph{e.g.} em sistemas de arquivos, visto
que qualquer mudança em um nó da árvore produzirá um valor distinto na raiz
quando calculado novamente, descaracterizando a validade dos dados atrelados a
esta.

\begin{algorithm}
  \begin{algorithmic}
    \REQUIRE{}  $h \in \{0, \dots, 2^{H} - 1\}, \enspace \mathbf{S}$
      \COMMENT{índice de folha, pilha de nodos}
    \ENSURE{}  $\mathbf{S}$ \COMMENT{pilha atualizada}
    \STATE{}  $\textsc{Leaf} \leftarrow \textsc{Leafcalc}(i)$
    \WHILE{$\textsc{Leaf}.height() = \mathbf{S}.top().height()$}
      \STATE{}  $\textsc{Top} \leftarrow \mathbf{S}.pop()$
      \STATE{}  $\textsc{Leaf} \leftarrow
        \hash{\textsc{Top} \concat \textsc{Leaf}}$
    \ENDWHILE{}
    \STATE{}  $\mathbf{S}.push(\textsc{Leaf})$
  \end{algorithmic}
  \caption{Funcionamento de $\textsc{Treehash}_{h}$.}\label{alg:treehash}
\end{algorithm}

Para calcular nodos de maneira eficiente, não é necessário armazenar $T$
inteiramente. Considere a sub-rotina $\textsc{Leafcalc}(k), 0 \leq k \leq 2^{H}
- 1$, que retorna o conteúdo da $k$-ésima folha, \emph{i.e.}
$\hash{\textsc{Ots}^{k}_{\pk{}}}$, e um nodo $T_{\cdot, \cdot}$ com a rotina
$height()$, que retorna sua altura em $T$. O algoritmo $\textsc{Treehash}_{h}$,
munido de uma pilha \textbf{S} usual com as operações $\mathbf{S}.pop()$,
$\mathbf{S}.push(\cdot)$ e $\mathbf{S}.top()$ calcula um nodo de altura $h$ em
$2^{h}$ chamadas de \textsc{Leaf} e $2^{h} - 1$ cálculos de $\hh{}$. Este
processo pode ser visualizado no Algoritmo~\ref{alg:treehash}.

Em qualquer momento de sua execução, o número máximo de nodos armazenados em
\textbf{S} será $h$, chamados de nodos cauda, ou \emph{tail nodes}. Ao seu
estado final, \textbf{S} conterá apenas o nodo desejado na altura $h$. Note que
a execução de \textsc{Treehash} repetidamente, como visto no
Algoritmo~\ref{alg:fulltreehash}, é realizada para calcular a raiz da árvore de
Merkle $T_{H, 0}$. Estas estratégias serão necessárias para a travessia em
árvores de dimensões extensas, abordada na Subseção~\ref{subsection:xmss}.

\begin{algorithm}
  \begin{algorithmic}
    \REQUIRE{} {$H \geq 2$} \COMMENT{altura da árvore $T$}
    \ENSURE{} {$T_{H, 0}$} \COMMENT{nodo raiz}
    \FOR{$i \leftarrow 0$ até $2^{H} - 1$}
      \STATE{}  $\mathbf{S} \leftarrow \textsc{Treehash}_{i}(\mathbf{S})$
    \ENDFOR{}
    \STATE{}  $T_{H, 0} \leftarrow \mathbf{S}.pop()$
  \end{algorithmic}
  \caption{\textsc{Treehash} para o
    cálculo de $T_{H, 0}$.}\label{alg:fulltreehash}
\end{algorithm}

\subsection{\mss{}}\label{subsection:mss}

O primeiro esquema de assinatura digital baseado em árvores de
Merkle~\cite[Capítulo 6]{Merkle:inproc:1989:aug} recomenda a assinatura de até
$2^{20}$ mensagens. Informalmente, os dados inseridos em suas folhas são chaves
públicas de diferentes instâncias de um esquema de assinatura única, como
\wots{}. Assim, ao construir a árvore de Merkle, a raiz será a chave pública
deste esquema, que validará todas as folhas da árvore através de um caminho de
autenticação. A chave privada pode ser descrita como o conjunto de chaves
privadas das folhas, e a assinatura consiste da mensagem assinada pela
instância do esquema localizado em uma folha qualquer, bem como todos os nós
necessários para calcular o conteúdo da raiz da árvore.

Formalmente, seja uma árvore de Merkle $T$ com $H \geq 2$. Tome um esquema de
assinatura digital única genérico \textsc{Ots}, suas chaves privada e pública
como $\textsc{Ots}_{\sk{}}$ e $\textsc{Ots}_{\pk{}}$, e os algoritmos de
geração de chaves, geração de assinatura e verificação de assinatura como
$\textsc{Ots}_\mathcal{G}, \textsc{Ots}_\mathcal{S} \text{ e }
\textsc{Ots}_\mathcal{V}$. Por fim, considere uma função de resumo
criptográfico $\fhash{m}$.

\begin{enumerate}

  \item[] \emph{Geração de chaves.} A chave privada é definida como uma
      $2^{H}$-tupla de pares de chaves diferentes provenientes de \textsc{Ots}.
        Então, a partir de execuções de $\textsc{Ots}_\mathcal{G}$ para cada
        folha, tem-se
        \begin{equation}
          \sk{} = ((\textsc{Ots}_{\sk{}}^{2^{H} - 1},
            \textsc{Ots}_{\pk{}}^{2^{H} - 1}), \dots,
            (\textsc{Ots}_{\sk{}}^{0}, \textsc{Ots}_{\pk{}}^{0})).
        \end{equation}
        As folhas de $T$ são preenchidas com as respectivas chaves públicas de
        \textsc{Ots}. Portanto, $T_{0, j} = \hash{\textsc{Ots}_{\pk{}}^{j}}$, e
        $T$ é construída recursivamente. Finalmente,
        \begin{equation}
          \pk{} = T_{H, 0}.
        \end{equation}

  \item[] \emph{Geração da assinatura.} Tome uma mensagem $M$ e calcule o seu
      resumo $d = \hash{M}$. Escolha uma folha de índice $j$ não utilizada
        anteriormente e produza a assinatura $\textsc{Ots}_\sigma^{j}$ a partir
        de $d$. O caminho de autenticação \textsc{Auth} é uma $H$-tupla
        necessária para recriar os resumos desejados a fim de compará-los com a
        raiz da árvore, e também deve ser incluído na assinatura. Assim, de
        acordo com~\cite[pp. 43]{Bernstein:book:2008},
        \begin{equation}
          \textsc{Auth}_{h} =
          \begin{cases}
            T_{h, j / 2^{h}  - 1}, \text{ se }
              \lfloor \sfrac{s}{2^{h}} \rfloor \equiv 1 \pmod{2}, \\
            T_{h, j / 2^{h}  + 1}, \text{ se }
              \lfloor \sfrac{s}{2^{h}} \rfloor \equiv 0 \pmod{2},
          \end{cases}
        \end{equation}
        para $0 \leq h \leq H - 1$, representado visualmente na
        Figura~\ref{fig:auth}. A assinatura final leva em conta todos estes
        itens. Portanto,
        \begin{equation}
          \sigma = (j, \textsc{Ots}_\sigma^{j},
            \textsc{Ots}_{\pk{}}^{j}, \textsc{Auth}).
        \end{equation}

  \item[] \emph{Verificação da assinatura.} Para verificar uma assinatura
      perante a árvore $T$, é necessário primeiro verificar a assinatura única.
        Caso o resultado de $\textsc{Ots}_{\mathcal{V}}$ seja positivo, então
        os nodos do caminho de autenticação são reconstruídos através da
        definição recursiva abaixo:
        \begin{equation}
          \begin{split}
            a_{0} &= \hash{\textsc{Ots}_{\pk{}}^{j}}, \text{ e } \\
            a_{h} &=
            \begin{cases}
              \hash{a_{h - 1} \concat \textsc{Auth}_{h - 1}}, \text{ se }
                \lfloor \sfrac{j}{2^{h - 1}} \rfloor \equiv 0 \pmod{2}, \\
              \hash{\textsc{Auth}_{h - 1} \concat a_{h - 1}}, \text{ se }
                \lfloor \sfrac{j}{2^{h - 1}} \rfloor \equiv 1 \pmod{2}, \\
            \end{cases}
          \end{split}
        \end{equation}
        para $1 \leq h \leq H$. Finalmente, se
        \begin{equation}
          \pk{} = a_{h},
        \end{equation}
        a assinatura está válida.

\end{enumerate}

Note que no passo de geração da assinatura, um índice da folha tem de ser
escolhido, de modo que respeite uma restrição estrita: o nodo não pode ter sido
selecionado anteriormente, a fim de prevenir a reutilização de uma instância de
esquema de assinatura digital única. Para que essa escolha seja bem sucedida, é
necessário que o esquema baseado em árvores de Merkle coordene quais índices
foram utilizados.

Este conceito é chamado de gerenciamento de estado, e introduz vários
obstáculos para o funcionamento do esquema~\cite{McGrew:inproc:2016:nov}, como
a necessidade de salvar frequentemente informações sobre o estado em
armazenamento não volátil. Ademais, este é geralmente codificado em $\sk{}$, e
portanto, duas mensagens não podem ser assinadas com a mesma chave privada,
criando problemas de sincronização de chaves entre múltiplos dispositivos. Esta
restrição é removida em~\cite[Construção 6.4.16]{Goldreich:book:2004}, onde o
esquema deve escolher um nodo aleatoriamente, assim introduzindo a
probabilidade de que um nodo possa ser escolhido duas vezes, relativa à
quantidade de folhas. Esquemas que lidarão com esta característica serão
discutidos futuramente.

\begin{figure}
  \centering
  \begin{tikzpicture}[
    every tree node/.style={draw, circle, minimum size=0.75cm},
    level distance=1cm, level 1/.style={sibling distance=1.5cm},
    level 2/.style={sibling distance=1.25cm},
    level 3/.style={sibling distance=1cm},
    edge from parent path={(\tikzparentnode) -- (\tikzchildnode)}, scale=0.7,
  ]
    \Tree
      [.\node[name=ah0, label=below:{$\pk{}$}]{};
        [.\node[name=ah1]{};
          [.\node[dashdotted, label=above:{$\textsc{Auth}_{1}$}]{}; {} {} ]
          [.\node[name=ah2]{};
            \node[dashdotted, label=below:{$\textsc{Auth}_{0}$}]{};
            \node[name=orig, label=below:{$i = 3$}, thick]{$\sigma$};
          ]
        ]
        [.\node[dashdotted, label=above:{$\textsc{Auth}_{2}$}]{};
          [.{} {} {} ]
          [.{} {} {} ]
        ]
      ]
    \draw[thick, ->] (orig) -- (ah2);
    \draw[thick, ->] (ah2) -- (ah1);
    \draw[thick, ->] (ah1) -- (ah0);
  \end{tikzpicture}
  \caption{Caminho de autenticação
    para a folha de índice $i = 3$.}\label{fig:auth}
\end{figure}

Observe que o tamanho da chave pública é extremamente proibitivo e escala com o
número de folhas da árvore. Para resolver esta limitação, um novo parâmetro é
adicionado ao esquema, na forma de um gerador de números pseudoaleatórios
determinístico, cuja semente será a nova chave privada~\cite[Subseção
6.4.2.3]{Goldreich:book:2004}. Adicionalmente, este recurso implica que a
árvore não necessita ser construída totalmente, posto que a assinatura de novas
mensagens implica na criação dinâmica de pares de chaves para estas instâncias
de esquemas de assinatura única. Caso este gerador apresente como
característica o sigilo encaminhado, ou \emph{forward secrecy}, onde valores
gerados no passado não são ameaçados caso a função seja comprometida, o esquema
também será caracterizado como tal~\cite[pp.  45]{Bernstein:book:2008}: chaves
privadas comprometidas não implicarão na falsificação de mensagens assinadas
com chaves antigas.

Note que uma árvore de altura razoável para utilização em aplicações práticas
tem seu armazenamento total impossibilitado na maioria absoluta dos
dispositivos alvo, em vista da quantidade excessiva de nodos. A fim de reduzir
este ônus, estruturas virtuais são empregadas, onde apenas partes relevantes da
árvore de Merkle em uso estão acomodadas em memória. Entretanto, é necessário
que quaisquer nodos possam ser autenticados de maneira modesta, levando em
conta restrições de processamento e armazenamento. Assim, um problema de
travessia entre os nodos da árvore de Merkle deve ser resolvido, e a utilização
de algoritmos otimizados é crucial na execução de alguns esquemas, visto que a
extensão das árvores de assinaturas é um fator desejável na criação de novos
esquemas. Esta característica será discutida na
Subseção~\ref{subsubsection:bds}.

Finalmente, é razoável destacar que a função $\hh{}$ utilizada neste esquema
tem a restrição implícita de ser resistente à colisões, visto que a modificação
de qualquer nodo na árvore sem que ocorra uma divergência na raiz implica em
uma colisão de resumos. Este é notoriamente o requisito de segurança mais
explorado no contexto de criptoanálise aplicada sobre funções de resumo
criptográfico, \emph{e.g.} colisões encontradas em várias funções baseadas na
estrutura Merkle---Damgård. Assim, é razoável construir esquemas com menos
requisitos, tornando-os naturalmente mais seguros.

Um esquema baseado em árvores de Merkle que necessita apenas de resistência à
segunda pré-imagem em todos os seus componentes, chamado de
\sprmss{}\sigla{\sprmss{}}{\emph{Second Preimage Resistant Merkle Signature
Scheme}}, é proposto em~\cite{Dahmen:inproc:2008:oct}. Consiste na
reestruturação das folhas da árvore, onde o resumo da concatenação dos
elementos de cada chave pública originalmente calculado é substituído por uma
reorganização destes em uma árvore possivelmente desbalanceada. Posteriormente,
máscaras de \emph{bits} aleatórias são aplicadas nestes elementos, e também em
cada criação de nodo na árvore de Merkle. Esta construção será descrita
formalmente junto ao esquema a seguir.

\subsection{\xmss{}}\label{subsection:xmss}

A redução dos requisitos de segurança, bem como a presença do sigilo
encaminhado, são as principais características do esquema
\xmss{}\sigla{\xmss{}}{\emph{eXtended Merkle Signature Scheme}}. Estes recursos
foram explorados em~\cite{Buchmann:inproc:2011:nov}, e culminam em uma forma
mais eficiente de aplicar as ideias impostas em \sprmss{}, junto à utilização
de um gerador de números pseudoaleatórios de funcionamento particular. De forma
complementar, requisitos de armazenamento de assinaturas são diminuídos através
do uso de algoritmos de travessia.

A descrição original deste esquema utiliza instâncias de um esquema de
assinatura única baseado em Winternitz chamado de
\wotsprf{}\sigla{\wotsprf{}}{\emph{Winternitz One-time Signature Scheme with
Pseudorandom Functions}}, criado com o intuito de possuir requisitos de
segurança mínimos a fim de manter a necessidade de uma função de resumo apenas
resistente à segunda pré-imagem. Entretanto, de acordo com~\cite[Seção
4.2]{Lafrance:msc:2017:apr}, a prova de segurança para este esquema apresenta
erros. Portanto, a descrição a seguir tomará o esquema de assinatura única
utilizado como o \wotsplus{}, cuja prova de segurança não contém erros
conhecidos.

Assim, tome um parâmetro de segurança $m$ e o parâmetro de Winternitz $w$, a
família de funções \[\mathcal{F}_{m} : \{f_{k} : \binwds{m} \longrightarrow
\binwds{m} \mid k \in \mathcal{K}_{m}\},\] uma árvore de Merkle $T$ com altura
$H$ e uma família de funções de resumo \[\hh{}_{m} : \{h_{k} : \binwds{2m}
\longrightarrow \binwds{m} \mid k \in \mathcal{K}_{m}\}.\] Um gerador de
números pseudoaleatórios é construído a partir de $f$ a fim de assegurar sigilo
encaminhado, definido como
\begin{equation}
  \textsc{Prf}_{a}(b) = f_{a}(1) \concat \dots \concat f_{a}(b),
    \; a \in \mathbb{N}, \; b \in \binwds{m}.
\end{equation}
O esquema de assinatura única \textsc{Ots} é definido como \wotsplus{}.

Observe que, por conta de sua semelhança com o esquema \sprmss{}, a estrutura
da árvore de Merkle é modificada. A função de construção da árvore é remodelada
a fim de utilizar máscaras de \emph{bits} $r_{i} \random{}
\binwds{2m}$ para cada nível da árvore, ou seja,
\begin{equation}
  T_{h, j} = h_{k}(r_{i} \oplus (T_{h - 1, 2j} \concat T_{h - 1, 2j + 1})),
    \; 1 \leq h \leq H, \; 0 \leq j \leq 2^{H - h} - 1.
\end{equation}
O conteúdo das folhas, originalmente o resumo criptográfico de elementos
concatenados de $\textsc{Ots}_{\pk{}}$, é substituído por uma estrutura chamada
de árvore-$l$, construída a partir dos elementos desta chave de forma similar à
$T$, mas com máscaras iguais para todas as árvores referentes aos esquemas de
assinatura única. Note que o número de elementos de $\textsc{Ots}_{\pk{}}$, o
inteiro $t$ em esquemas baseados em Winternitz, pode não ser uma potência de 2,
e portanto a árvore-$l$ deve ser balanceada tal que qualquer nodo sem irmão à
direita é movido para um nível mais alto, de forma a tornar-se um irmão à
direita de outro nodo. Assim, a altura total é de $\lceil \log_{2} t \rceil$,
mas não considerada no contexto de $T$.

\begin{enumerate}

  \item[] \emph{Geração de chaves.} Tome uma semente $s \random{} \binwds{m}$ e
      uma função de resumo $h_{k} \random{} \hh{}_{m}$. Gere o conjunto de
        máscaras
      \begin{equation}
        \mathbf{r} = (r_{0}, \dots, r_{H + \lceil \log_{2} t \rceil - 1})
          \random{} \binwds{(2m, H + \lceil \log_{2} t \rceil)}.
      \end{equation}
        Para gerar as chaves privadas das instâncias de esquemas de assinatura
        única, defina
        \begin{equation}
          \textsc{Ots}_{\sk{}}^{i} = \textsc{Prf}_{t}(f_{s}(i)),
            \; \forall i \in \{0, \dots, 2^{H} - 1\}.
        \end{equation}
        A árvore $T$ é construída utilizando a compressão de
        $\textsc{Ots}_{\pk{}}^{i}$ supracitada, bem como o processo usual para
        o cálculo de resumos intermediários. Finalmente, a chave privada deve
        guardar o estado do esquema, que pode ser representado como o índice da
        primeira folha não utilizada. Portanto,
        \begin{equation}
          \sk{} = (s, 0),
        \end{equation}
        e naturalmente, a chave pública deve conter as máscaras utilizadas em
        $T$, \emph{i.e.}
        \begin{equation}
          \pk{} = (T_{H, 0}, \mathbf{r}).
        \end{equation}

  \item[] \emph{Geração da assinatura.} A assinatura é construída de maneira
      muito similar a esquemas de Merkle clássicos. Para uma mensagem $M$, um
        resumo $d = h_{k}(M)$, e um índice $j$ não utilizado anteriormente,
        $\textsc{Ots}_\sigma^{j}$ é calculada a partir de $d$. O caminho de
        autenticação \textsc{Auth} é construído com o auxílio de algoritmos de
        travessia. Assim,
        \begin{equation}
          \sigma = (j, \textsc{Ots}_\sigma^{j}, \textsc{Auth}).
        \end{equation}

  \item[] \emph{Verificação da assinatura.} Para verificar uma assinatura
      perante $T$, assegure que
        $\textsc{Ots}_{\mathcal{V}}(\textsc{Ots}_{\pk{}}^{j},
        \textsc{Ots}_{\sigma}^{j}) = 1$, e utilize esta chave para reconstruir
        a árvore-$l$ com as máscaras $\mathbf{r}$, obtendo a raiz desta. Junto
        a \textsc{Auth}, compute o caminho de nodos $(a_{0}, \dots, a_{h})$.
        Finalmente, se
        \begin{equation}
          \pk{} = a_{h},
        \end{equation}
        a assinatura está válida.

\end{enumerate}

O esquema descrito tem estrutura similar à variante em processo de padronização
pela IETF, que faz uso de \wotsplus{} em suas folhas. Este esquema também conta
com outros arcabouços que permitem a resistência a ataques específicos,
\emph{e.g.} a associação da assinatura com o usuário e a posição na árvore
impede ataques que almejam forjar assinaturas para um grande número de
instâncias de esquemas de assinatura única~\cite[Seção
9.1]{Huelsing:report:2018:may}. Entretanto, seu funcionamento geral é similar a
esquemas clássicos, e o gerenciamento de estado é mantido. As otimizações
apresentadas futuramente são implementadas e testadas principalmente neste
esquema.

\subsection{\xmssmt{}}\label{subsection:xmssmt}

Uma das principais limitações dos esquemas baseados em árvores de Merkle é a
quantidade de assinaturas a serem conectadas com uma árvore, ou chave pública.
Para solucionar este problema, o conceito de hiper-árvores é proposto em
diversos trabalhos, com o intuito de encadear camadas de árvores de Merkle,
conectadas por uma instância de esquema de assinatura única, de tal forma que a
folha da árvore superior assina a raiz da árvore inferior.

A ideia original é introduzida em~\cite{Buchmann:inproc:2006:dec} na forma do
esquema \cmss{}\sigla{\cmss{}}{\emph{Coronado---Merkle Signature Scheme}}, que
habilita a assinatura de até $2^{40}$ mensagens com um par de chaves,
relacionado a uma estrutura virtual de duas camadas, onde apenas uma árvore na
parte inferior é criada de cada vez a fim de reduzir requisitos de
armazenamento. Posteriormente, este esquema é generalizado
em~\cite{Buchmann:inproc:2007:jun} como
\gmss{}\sigla{\gmss{}}{\emph{Generalized Merkle Signature Scheme}}, que utiliza
um número arbitrário de camadas de árvores, com alturas e parâmetros de
esquemas de assinatura única diferentes para cada uma destas, atingindo o
número de $2^{80}$ mensagens por par de chaves.

\begin{figure}
  \centering
  \begin{tikzpicture}[
    every tree node/.style={draw, circle, minimum size=0.75cm},
    edge from parent path={(\tikzparentnode) -- (\tikzchildnode)},
    level distance=1cm, sibling distance=25pt, scale=0.8,
  ]
    \begin{scope}[yshift=4.5cm, xshift=0.59cm]
      \Tree
        [.\node[name=root, label={below:$\pk{}$}]{};
          [.\node[name=p4]{};
            [.\node[dashdotted, label=above:{$\textsc{Auth}_{1}^{1}$}]{};
              {} {}
            ]
            [.\node[name=p3]{};
              \node[dashdotted, label=below:{$\textsc{Auth}_{0}^{1}$}]{};
              \node[name=leaf, thick]{$\sigma_{1}$};
            ]
          ]
          [.\node[dashdotted, label=above:{$\textsc{Auth}_{2}^{1}$}]{};
            [.{} {} {} ]
            [.{} {} {} ]
          ]
        ]
    \end{scope}
      \Tree
        [.\node(halfroot){};
          [.\node[dashdotted, label=above:{$\textsc{Auth}_{2}^{0}$}]{};
            [.{} {} {} ]
            [.{} {} {} ]
          ]
          [.\node[name=p2]{};
            [.\node[name=p1]{};
              \node[name=sig0, thick]{$\sigma_{0}$};
              \node[dashdotted, label=below:{$\textsc{Auth}_{0}^{0}$}]{};
            ]
            [.\node[dashdotted, label=above:{$\textsc{Auth}_{1}^{0}$}]{};
              {} {}
            ]
          ]
        ]
    \draw[->, thick] (p4) to (root);
    \draw[->, thick] (p3) to (p4);
    \draw[->, thick] (leaf) to (p3);
    \draw[->, thick] (halfroot) to (leaf);
    \draw[->, thick] (p2) to (halfroot);
    \draw[->, thick] (p1) to (p2);
    \draw[->, thick] (sig0) to (p1);
  \end{tikzpicture}
  \caption{Caminho de autenticação para a folha $j = 3 \cdot 2^{h_{0}} + 5$,
    em uma hiper-árvore com $d = 2, h_{0} = h_{1} = 3$.}\label{fig:multiauth}
\end{figure}

Naturalmente, este recurso é aplicado ao esquema \xmss{} a fim de produzir a
variante \xmss{}+~\cite{Huelsing:inproc:2012:aug}, com uma árvore superior e
inferior, e posteriormente, a versão
\xmssmt{}~\cite{Huelsing:inproc:2013:sep}\sigla{\xmssmt{}}{\emph{eXtended
Merkle Signature Scheme with Multi-Trees}}, generalizada para qualquer número
de camadas de árvores, abordada abaixo. Para descrevê-la completamente, é
necessário apontar que algoritmos de travessia são essenciais no funcionamento
prático de esquemas com hiper-árvores, visto que estas estruturas existirão
apenas parcialmente em qualquer dispositivo, embora nodos em várias partes da
hiper-árvore são necessários para construir caminhos de autenticação. Deste
modo, o algoritmo \bds{}~\cite{Buchmann:inproc:2008:oct}
\sigla{\bds{}}{\emph{Buchmann---Dahmen---Schneider}} é exposto junto ao
esquema, a fim de demonstrar a complexidade real do gerenciamento de estado
atrelado a este tipo de construção.

\subsubsection{Travessia de árvores de Merkle \bds{}}\label{subsubsection:bds}

O algoritmo admite quatro entradas, na forma da altura $H$ da árvore $T$, um
índice de folha $s \in \{0, \dots, 2^{H} - 2\}$, e um parâmetro
\begin{equation}\label{eq:kparam}
  K \in \mathbb{N}^{*} \setminus \{1\},
    \; K < H, \; \sfrac{H - K}{2} \equiv 0 \pmod{2}
\end{equation}
que representa uma compensação entre armazenamento e tempo de execução do
algoritmo, permitindo que uma execução total de $\textsc{Treehash}$, ou seja,
para todas as $2^{H} - 1$ folhas, seja substituída por $\sfrac{H - K}{2}$
instâncias desta rotina. Finalmente, o estado $\textsc{State}_{\bds{}}$ é
composto das seguintes estruturas:

\begin{enumerate}[label= (\roman*)]

  \item $\textsc{Auth}$, lista de tamanho $H$ que armazena o caminho de
      autenticação atual;

  \item $\textsc{Keep}$, lista de tamanho $H - 1$ que armazena nodos úteis para
      o cálculo de nodos de autenticação à esquerda;

  \item $\{\textsc{Retain}_{h} : H - K \leq h \leq H - 2\}$, pilhas com nodos à
      direita perto da raiz;

  \item \textbf{S}, pilha munida das operações usuais;

  \item $\{\textsc{Treehash}_{h} : 0 \leq h \leq H - 3\}$, \emph{i.e.} várias
      instâncias do Algoritmo~\ref{alg:treehash}.

\end{enumerate}

As listas são munidas da operação $remove(\cdot)$, cujo argumento representa um
índice válido de acordo com o tamanho da lista. As instâncias
$\textsc{Treehash}_{h}$ compartilham \textbf{S}. São inicializadas por
$init(\cdot)$, cujo argumento é um índice de folha que criará o nodo
\textsc{Leaf} no Algoritmo~\ref{alg:treehash}, e podem ser executadas
totalmente por $update()$. Ademais, são munidas da função $height()$, que
retorna a menor altura entre nodos localizados nesta instância. Em casos
anômalos, se \textbf{S} estiver vazia, $\textsc{Treehash}_{h}.height() = h$, e
se esta instância não tiver sido inicializada ou já tiver sido terminada,
$\textsc{Treehash}_{h} = \infty$.

O algoritmo retorna o caminho de autenticação para a folha $T_{0, s + 1}$. É
inicializado na etapa de geração de chaves do esquema. \textsc{Auth} recebe
primeiramente o caminho de autenticação para a folha $T_{0, 0}$, representado
por $\textsc{Auth} = (T_{0, 1}, \dots, T_{H - 1, 1})$. As instâncias
$\textsc{Treehash}_{h}$ têm como nodos iniciais $T_{h, 3}$. As pilhas
$\textsc{Retain}_{h}$ recebem os nodos $T_{h, 2k + 3}, \; 2^{H - h - 1} - 2
\leq k \leq 0$. Execuções posteriores do algoritmo mantém
$\textsc{State}_{\bds{}}$ preparado anteriormente.

O cálculo de nodos intermediários depende se este está à esquerda ou à direita.
A descrição detalhada de \bds{}, no Algoritmo~\ref{alg:bds}, contempla ambos os
casos, e será discutida em detalhes. Para uma folha $T_{0, j}$, $\tau$ é a
altura do primeiro pai à esquerda de $T_{0, j}$. Este valor codifica as alturas
nas quais o caminho de autenticação para $T_{0, j + 1}$ necessita de novos
nodos. Nodos à direita são necessários para alturas até $\tau - 1$, e um nodo à
esquerda na altura $\tau$. Caso este nodo esteja à esquerda, então $\tau = 0$,
e do contrário, $\tau = \max(\{2^{h} \mid j + 1 : 1 \leq h \leq H\})$.

\begin{algorithm}
  \begin{algorithmic}
    \REQUIRE{} {$H \geq 2, \enspace K~(\text{Eq.}~\ref{eq:kparam}), \enspace
      s \in {0, \dots, 2^{H} - 2}, \enspace \textsc{State}_{\bds{}}$}
      \COMMENT{altura da árvore $T$, parâmetro de compensação,
        índice de folha, estado do algoritmo}
    \ENSURE{} {$\textsc{Auth}^{s + 1}$}
      \COMMENT{caminho de autenticação para a folha $s + 1$}
    \STATE{}  $\tau \leftarrow \max(\{2^{h} \mid s + 1 : h \in 1, \dots, H\})$
    \IF{$\lfloor \sfrac{s}{2^{\tau + 1}} \rfloor \equiv 0 \pmod{2}$
      e $\tau < H - 1$}
      \STATE{}  $\textsc{Keep}_{\tau} \leftarrow \textsc{Auth}_{\tau}$
    \ENDIF{}
    \IF{$\tau = 0$}
      \STATE{}  $\textsc{Auth}_{0} \leftarrow \textsc{Leafcalc}(s)$
    \ELSIF{$\tau > 0$}
      \STATE{}  $\textsc{Auth}_{\tau} \leftarrow
        \hash{\textsc{Auth}_{\tau - 1} \concat \textsc{Keep}_{\tau - 1}}$
      \STATE{}  $\textsc{Keep}.remove(\tau - 1)$
      \FOR{$h = 0$ até $\tau - 1$}
        \IF{$h < H - K$}
          \STATE{}  $\textsc{Auth}_{h} \leftarrow \textsc{Treehash}_{h}.pop()$
        \ELSE{}
          \STATE{}  $\textsc{Auth}_{h} \leftarrow \textsc{Retain}_{h}.pop()$
        \ENDIF{}
      \ENDFOR{}
      \FOR{$h = 0$ até $\min(\tau - 1, H - K - 1)$}
        \IF{$s + 1 + 3 \cdot 2^{h} < 2^{H}$}
          \STATE{}  $\textsc{Treehash}_{h}.init(s + 1 + 3 \cdot 2^{h})$
        \ENDIF{}
      \ENDFOR{}
    \ENDIF{}
    \FOR{$i = 0$ até $\sfrac{H - K}{2}$}
      \STATE{}  $k \leftarrow \min(\{
        \textsc{Treehash}_{j}.height() : j \in 0, \dots, H - K - 1\})$
      \STATE{}  $\textsc{Treehash}_{k}.update()$
    \ENDFOR{}
  \end{algorithmic}
  \caption{Travessia de árvores de Merkle \bds{}.}\label{alg:bds}
\end{algorithm}

Para computar os nodos à esquerda, a utilização da lista $\textsc{Keep}$ será
crucial para calcular nodos de autenticação à esquerda utilizando apenas um
cálculo de $\hh{}$. Observe que, se o pai da folha $T_{0, s}$ na altura $\tau +
1$ é um nodo à esquerda, então $\textsc{Auth}_{\tau}$ está à direita e pode ser
armazenado em $\textsc{Keep}_{\tau}$. Caso $\tau = 0$, então a folha está à
esquerda e servirá como parte do caminho de autenticação para sua irmã.
Portanto, $\textsc{Auth}_{0}$ recebe $\textsc{Leafcalc}(s)$. Do contrário, a
folha está à direita, e o cálculo de $\textsc{Auth}_{\tau}$ é necessário. Neste
caso, $\textsc{Auth}_{\tau - 1}$ deve existir e ser seu filho à esquerda. Resta
buscar o filho à direita, que estará armazenado em $\textsc{Keep}_{\tau - 1}$.
Portanto, $\textsc{Auth}_{\tau}$ pode ser calculado. Uma explicação detalhada
deste processo pode ser encontrada em~\cite[Seção
2.1]{Buchmann:inproc:2008:oct}.

O cômputo de nodos à direita é feito desde as folhas, visto que nenhum dos seus
nodos filho foram utilizados em caminhos de autenticação anteriores. O
parâmetro $K$ é empregado nesta parte do algoritmo. Nodos cuja altura estão em
$H - K \leq h \leq H - 2$ são retirados das pilhas $\textsc{Retain}_{h}$ e
movidos para $\textsc{Auth}_{h}$. Nodos com altura $h < H - K$ fazem uso dos
nodos armazenados nas instâncias $\textsc{Treehash}_{h}$, então
subsequentemente inicializadas com os nodos $s + 1 + 3 \cdot 2^{h}$, se
necessário. Finalmente, algumas instâncias cujos nodos têm menor altura são
atualizadas, de acordo com o critério em~\cite[Seção 4.5]{Bernstein:book:2008},
a fim de adicionar nodos relevantes ao estado do algoritmo.

\subsubsection{Descrição do esquema}\label{subsubsection:xmssmt}

Tome o parâmetro de segurança $m$, a família de funções $\mathcal{F}_{m}$, uma
função de resumo $\hh{} : \binwds{2m} \longrightarrow \binwds{m}$, o esquema de
assinatura única \textsc{Ots} definido como \wotsplus{}, o número de camadas da
hiper-árvore $d \in \mathbb{N}^{*}$, e para cada camada $0 \leq i \leq d - 1$,
a altura da árvore $h_{i}$, o parâmetro de Winternitz $w_{i}$, e
consequentemente $t_{i}$, e o parâmetro \bds{} $k_{i}$. Novamente, um gerador
de números pseudoaleatórios \textsc{Prf} é construído a partir de $f$.

\begin{enumerate}

  \item[] \emph{Geração de chaves.} Calcule o valor
      \begin{equation}
        k = \max(\{h_{i} + \lceil \log_2 t_{i} \rceil : 0 \leq i \leq d - 1\}),
      \end{equation}
        e gere uma $k$-tupla de máscaras de \emph{bits} aleatórias \textbf{r},
        reutilizadas em cada camada da árvore. Uma $d$-tupla de sementes para
        cada camada da hiper-árvore também é gerada desta maneira, e estados do
        algoritmo \bds{} são inicializados: $\textsc{State} =
        (\textsc{State}_{\bds{}}^{0}, \dots, \textsc{State}_{\bds{}}^{d - 1})$.
        Utilizando instâncias do algoritmo \textsc{Treehash} e a tupla
        $\textbf{s}$ a fim de criar os pares de chaves de \wotsplus{}, os
        valores $T_{h_{i}, 0}, \; 0 \leq i \leq d - 2$ são calculados e
        assinados pela primeira folha da árvore superior. Estas assinaturas são
        então extraídas como $\Sigma = (\sigma_{1}^{T}, \dots, \sigma_{d -
        1}^{T})$.

        Note que apenas as assinaturas das primeiras raízes à esquerda são
        armazenadas, visto que será a primeira árvore a ser utilizada para
        assinar mensagens. Para facilitar a construção de futuros caminhos de
        autenticação e árvores intermediárias, sementes pseudoaleatórias,
        estados do algoritmo \bds{} e instâncias do algoritmo \textsc{Treehash}
        são também armazenados em uma estrutura
        \begin{multline}
          \textsc{Next} = \big(s^{n}_{0}, \dots, s^{n}_{d - 2},
            \textsc{Treehash}^{n}_{0}, \dots, \textsc{Treehash}^{n}_{d - 2}, \\
            \textsc{State}_{\bds{}}^{0, n},
            \dots, \textsc{State}_{\bds{}}^{d - 2, n}\big),
        \end{multline}
        onde $n$ denota a próxima árvore a ser utilizada na camada $i$.
        Finalmente,
        \begin{align}
          \sk{} &= (\textbf{s}, \textsc{State}, \Sigma, \textsc{Next}), \\
          \pk{} &= (T_{h_{d - 1}, 0}, \mathbf{r}).
        \end{align}

  \item[] \emph{Geração da assinatura.} Para uma mensagem $M$ e resumo $d =
      \hash{M}$, e um índice $j$ não utilizado anteriormente, calcula-se
        $\textsc{Ots}_\sigma^{j}$. Os caminhos de autenticação são retirados de
        $\textsc{State}$, e as assinaturas intermediárias em $\Sigma$. Assim, a
        assinatura é composta de
        \begin{equation}
          \sigma = (j, \textsc{Ots}_{\sigma}^{j}, \Sigma,
            \textsc{Auth}^{0}, \dots, \textsc{Auth}^{d - 1}).
        \end{equation}
        A árvore deve ser então inteiramente atualizada através dos algoritmos
        \textsc{Treehash} e \bds{}, modificando os estados e tornando a próxima
        folha disponível para uso. Em especial, caso a última folha de uma
        árvore for utilizada, isto significa que uma nova árvore deve ser
        criada. Assim, a chave privada deve ser atualizada com novos elementos
        $\textbf{s}', \textsc{State}', \Sigma', \textsc{Next}'$. Mais detalhes
        sobre este processo podem ser encontrados em~\cite[Capítulo
        2]{Huelsing:inproc:2013:sep}.

  \item[] \emph{Verificação da assinatura.} Para verificar $\sigma$ perante à
      hiper-árvore, $\textsc{Ots}_{\sigma}^{j}$ é aferida a fim de construir
        $\textsc{Ots}_{\pk{}}$. Com este nodo e $\textsc{Auth}^{0}$, a raiz da
        árvore é construída, a fim de verificar a primeira assinatura em
        $\Sigma$. Este processo é  repetido $d - 1$ vezes, utilizando todos os
        caminhos de autenticação e assinaturas em $\Sigma$ fornecidos por
        $\sigma$, e a saída da última iteração é comparada com $T_{h_{d - 1},
        0}$. A assinatura é válida se e somente se estes valores forem iguais.
        Este processo pode ser visualizado na Figura~\ref{fig:multiauth}.

\end{enumerate}

Adicionalmente, como mencionado na Subseção~\ref{subsection:wots}, o esquema
\xmsst{}\sigla{\xmsst{}}{\emph{eXtended Merkle Signature Scheme with Tight
security}} é definido em~\cite{Huelsing:inproc:2016:mar}, como uma variante do
\xmssmt{} resistente à ataques multiusuário. Isto é realizado através da
atribuição de um endereço único à cada nodo na árvore, e derivando deste um
resumo criptográfico calculado por funções com novas noções de resistência à
pré-imagem, segunda pré-imagem e colisões, a fim de reduzir as ameaças
ocasionadas por este tipo de ataque.

\section{Visão temporal}\label{section:timeline}

Vários esquemas foram citados ao longo das seções anteriores, provendo uma
contextualização teórica para o estudo aprofundado de variantes seletas. Deste
modo, é razoável visualizar de maneira cronológica a evolução do estudo de
assinaturas digitais baseadas em funções de resumo criptográfico. De acordo com
a Figura~\ref{fig:timebefore}, nas duas décadas iniciais, esta área é
estabelecida pela pesquisa
em~\cite{Lamport:report:1979:oct,Merkle:phd:1979:jun}, definindo os esquemas
seminais \lots{} e \mss{}, e no meio deste período, o esquema \wots{} é
publicado em~\cite{Merkle:inproc:1989:aug}. Resultados teóricos e otimizações
para o esquema de Lamport também fazem parte de publicações com destaque,
\emph{e.g.}~\cite{Bleichenbacher:inproc:1994:aug}, que formaliza uma
representação de esquemas de assinatura única como grafos acíclicos dirigidos.

\begin{figure}
  \centering
  \begin{chronology}[4]{1978}{1997}{\textwidth}
    \event{1979}{\lots{}, \mss{}}
    \event{1989}{\wots{}}
    \event[1996]{1994}{Bleichenbacher---Meurer}
  \end{chronology}
  \caption{Principais trabalhos acadêmicos sobre esquemas de assinatura digital
    baseados em funções de resumo criptográfico de 1979 até
    1997.}\label{fig:timebefore}
\end{figure}

\begin{figure}
  \centering
  \begin{chronology}[4]{1998}{2018}{\textwidth}
    \event{2001}{\emph{Bins and Balls}}
    \event{2002}{\hors{}}
    \event{2006}{\cmss{}}
    \event{2007}{\gmss{}}
    \event{2008}{\sprmss{}}
    \event{2011}{\wotsprf{}, \xmss{}}
    \event{2012}{\xmss{}+}
    \event{2013}{\xmssmt{}, \wotsplus{}, \wotslm{}}
    \event{2015}{\horst{}, \sphincs{}}
    \event{2016}{\xmsst{}, \wotst{}}
    \event{2017}{\sphincs{}+}
  \end{chronology}
  \caption{Principais trabalhos acadêmicos sobre esquemas de assinatura digital
    baseados em funções de resumo criptográfico de 1998 até
    2018.}\label{fig:timeafter}
\end{figure}

Entretanto, as últimas duas décadas de pesquisa culminaram em ideias utilizadas
por esquemas considerados como o estado da arte. Os conceitos de esquemas de
poucas assinaturas, redução de requisitos de segurança para resistência à
segunda pré-imagem, hiper-árvores e resistência a ataques multiusuário, todos
no contexto de assinaturas digitais com funções de resumo criptográfico, podem
ser mapeados para este período. As Figuras~\ref{fig:timebefore}
e~\ref{fig:timeafter} contemplam todos os esquemas citados nas
Seções~\ref{section:onetime} e~\ref{section:merkle}, à exceção da família
\sphincs{}~\cite{Bernstein:inproc:2015:apr,Bernstein:misc:2017:dec},
\sigla{\sphincs{}}{\emph{Stateless Practical Hash-based Incredibly Nice \\
Cryptographic Signatures}} que renuncia o gerenciamento de estado,
característica presente em todos os esquemas baseados em árvores de Merkle
aprofundados anteriormente.

Esta família utiliza várias estratégias combinadas a fim de evitar esta
característica: a altura da hiper-árvore é aumentada substancialmente, para que
o número de assinaturas que podem ser feitas com apenas um par de chaves seja
maior; nos nodos folha mais inferiores, o esquema \horst{} é utilizado para
evitar colisões entre assinaturas; o índice de folha escolhido depende de um
valor pseudoaleatório; entre outros recursos. Entretanto, as otimizações
descritas no Capítulo~\ref{chapter:tuning} têm aplicação reduzida a estes
esquemas, visto que o cerne do processamento total destes não é causado pela
utilização de instâncias Winternitz, restritas ao cálculo de assinaturas entre
árvores intermediárias.

\chapter{Otimização do esquema Winternitz}\label{chapter:tuning}

Neste capítulo, duas otimizações são apresentadas para a família de esquemas
Winternitz. A primeira, definida na Seção~\ref{section:wotsb}, consiste de uma
modificação em \emph{bits} inutilizados na soma de verificação calculada ao
longo do processo de assinatura, tornando a verificação desta menos onerosa. A
segunda, definida na Seção~\ref{section:wotsr}, apresenta uma estratégia para
modificar a entrada do algoritmo, a fim de torná-la adequada para o cômputo
eficiente das etapas de geração ou verificação de uma assinatura. Consequências
destas modificações são discutidas na Seção~\ref{section:results}, e o impacto
em esquemas da família \xmss{} é apresentado na
Subseção~\ref{subsection:impact}.

\section{\wotsb{}}\label{section:wotsb}

A primeira variante de \wots{} proposta é baseada na alteração da estrutura da
soma de verificação, explicada na Subseção~\ref{subsection:wots}, cujo cálculo
é essencial para o impedimento de falsificação trivial de assinaturas por meio
da aplicação de $f$ sobre cadeias de resumos pré-existentes. Esta estratégia é
abordada de maneira diferente no esquema \wotslm{}, onde um de seus parâmetros
comanda a quantidade de deslocamentos à esquerda realizados sobre a
representação binária desta soma~\cite[Seção 4.4]{McGrew:report:2018:apr}.

Entretanto, caso este parâmetro seja escolhido de maneira inábil, a etapa de
verificação será executada de forma menos eficaz em relação ao tempo de
execução. Ademais, é possível calcular o número de \emph{bits} não utilizados
na soma de verificação de maneira exata. De acordo com a
Subseção~\ref{subsection:wots}, considere a $t_{1}$-tupla $\bone{}$ como os
valores do resumo da mensagem divididos em palavras de base-$w$, e a soma de
verificação $c = \sum_{b \in \bone{}} 2^{w} - 1 - b$. Seu valor máximo é
definido por
\begin{equation}
  c_{\max} = \sum_{i = t - t_{1}}^{t - 1} (2^{w} - 1 - 0) = t_{1}(2^{w} - 1)
    \iff \forall b \in \bone{}, \; b = 0.
\end{equation}
Analogamente, o valor mínimo é definido como
\begin{equation}
  c_{\min} = \sum_{i = t - t_{1}}^{t - 1} (2^{w} - 1 - 2^{w} - 1) = 0
    \iff \forall b \in \bone{}, \; b = 2^{w} - 1.
\end{equation}
A partir de $c_{\max}$, o número de \emph{bits} necessários para representar
qualquer valor de $c$ é calculado. Defina este valor como $n_{c} = \lceil
\log_2 c_{\max} \rceil = \lceil \log_2 (t_{1} \times (2^{w} - 1)) \rceil$. Note
que o número de \emph{bits} reservados para este valor na definição do esquema
é diretamente relacionado com o valor de $t_{2}$, \emph{i.e.} $t_{2}w$. Observe
que, de acordo com as definições de $t_{1}$ e $t_{2}$, sempre é verdade que
$n_{c} \leq t_{2}w$:
\begin{align}
  \begin{split}
    n_{c} &\leq t_{2} w \\
    \lceil \log_2 (t_{1} \times (2^{w} - 1)) \rceil &\leq t_{2}w \\
    \lceil \log_2 t_{1} + \log_2 (2^{w} - 1) \rceil &\leq t_{2}w \\
    \lceil \log_2 t_{1} + w \rceil &\leq t_{2}w \\
    \lceil \log_2 t_{1} \rceil + w &\leq t_{2}w \\
    \lceil \log_2 t_{1} \rceil + w &\leq \left\lceil
      \sfrac{\lfloor (\log_2 t_{1} \rfloor + 1 + w)}{w} \right\rceil \times w \\
    \lceil \log_2 t_{1} \rceil + w
      &\leq \lceil \lfloor \log_2 t_{1} \rfloor + 1 + w \rceil \\
    \lceil \log_2 t_{1} \rceil + w &\leq \lfloor \log_2 t_{1} \rfloor + 1 + w \\
    \lceil \log_2 t_{1} \rceil + w &\leq \lceil \log_2 (t_{1} + 1) \rceil + w.
  \end{split}
\end{align}
Isto ocorre pois, para acomodar $c$, um número inteiro de palavras em base-$w$
deve ser utilizado. Portanto, a quantidade de \emph{bits} inutilizados é
definida como o número natural $n_{u} = t_{2}w - n_{c}$. Para os valores mais
comuns de $m$ e praticáveis para $w$, a Tabela~\ref{table:bits} apresenta
várias combinações de parâmetros para esquemas da família Winternitz.

\begin{table}
  \centering
  \scriptsize
  \begin{tabular}{*{5}{c}}
    \toprule
    $w$ & $m$ & $n_{c}$ & $n_{u}$ & $t_{2} w$ \\
    \toprule
    \multirow{4}{*}{2}  &  128  &  8   &  2   &  \multirow{3}{*}{10} \\
                        &  192  &  9   &  1   &                      \\
                        &  256  &  9   &  1   &                      \\
                        &  512  &  10  &  2   &  12                  \\
    \midrule
    \multirow{4}{*}{3}  &  128  &  9   &  0   &  9                   \\
                        &  192  &  9   &  3   &  \multirow{4}{*}{12} \\
                        &  256  &  10  &  2   &                      \\
                        &  512  &  11  &  1   &                      \\
    \midrule
    \multirow{4}{*}{4}  &  128  &  9   &  3   &  \multirow{4}{*}{12} \\
                        &  192  &  10  &  2   &                      \\
                        &  256  &  10  &  2   &                      \\
                        &  512  &  11  &  1   &                      \\
    \midrule
    \multirow{4}{*}{5}  &  128  &  10  &  0   &  10                  \\
                        &  192  &  11  &  4   &  \multirow{3}{*}{15} \\
                        &  256  &  11  &  4   &                      \\
                        &  512  &  12  &  3   &                      \\
    \midrule
    \multirow{4}{*}{6}  &  128  &  11  &  1   &  \multirow{3}{*}{12} \\
                        &  192  &  11  &  1   &                      \\
                        &  256  &  12  &  0   &                      \\
                        &  512  &  13  &  5   &  18                  \\
    \bottomrule
  \end{tabular}
  \begin{tabular}{*{5}{c}}
    \toprule
    $w$ & $m$ & $n_{c}$ & $n_{u}$ & $t_{2} w$ \\
    \toprule
    \multirow{4}{*}{7}  &  128  &  12  &  2   &  \multirow{4}{*}{14} \\
                        &  192  &  12  &  2   &                      \\
                        &  256  &  13  &  1   &                      \\
                        &  512  &  14  &  0   &                      \\
    \midrule
    \multirow{4}{*}{8}  &  128  &  12  &  4   &  \multirow{4}{*}{16} \\
                        &  192  &  13  &  3   &                      \\
                        &  256  &  13  &  3   &                      \\
                        &  512  &  14  &  2   &                      \\
    \midrule
    \multirow{4}{*}{9}  &  128  &  13  &  5   &  \multirow{4}{*}{18} \\
                        &  192  &  14  &  4   &                      \\
                        &  256  &  14  &  4   &                      \\
                        &  512  &  15  &  3   &                      \\
    \midrule
    \multirow{4}{*}{10} &  128  &  14  &  6   &  \multirow{4}{*}{20} \\
                        &  192  &  15  &  5   &                      \\
                        &  256  &  15  &  5   &                      \\
                        &  512  &  16  &  4   &                      \\
    \midrule
    \multirow{4}{*}{11} &  128  &  15  &  7   &  \multirow{4}{*}{22} \\
                        &  192  &  16  &  6   &                      \\
                        &  256  &  16  &  6   &                      \\
                        &  512  &  17  &  5   &                      \\
    \bottomrule
  \end{tabular}
  \begin{tabular}{*{5}{c}}
    \toprule
    $w$ & $m$ & $n_{c}$ & $n_{u}$ & $t_{2} w$ \\
    \toprule
    \multirow{4}{*}{12} &  128  &  16  &  8   &  \multirow{4}{*}{24} \\
                        &  192  &  16  &  8   &                      \\
                        &  256  &  17  &  7   &                      \\
                        &  512  &  18  &  6   &                      \\
    \midrule
    \multirow{4}{*}{13} &  128  &  17  &  9   &  \multirow{4}{*}{26} \\
                        &  192  &  17  &  9   &                      \\
                        &  256  &  18  &  8   &                      \\
                        &  512  &  19  &  7   &                      \\
    \midrule
    \multirow{4}{*}{14} &  128  &  18  &  10  &  \multirow{4}{*}{28} \\
                        &  192  &  18  &  10  &                      \\
                        &  256  &  19  &  9   &                      \\
                        &  512  &  20  &  8   &                      \\
    \midrule
    \multirow{4}{*}{15} &  128  &  19  &  11  &  \multirow{4}{*}{30} \\
                        &  192  &  19  &  11  &                      \\
                        &  256  &  20  &  10  &                      \\
                        &  512  &  21  &  9   &                      \\
    \midrule
    \multirow{4}{*}{16} &  128  &  19  &  13  &  \multirow{4}{*}{32} \\
                        &  192  &  20  &  12  &                      \\
                        &  256  &  20  &  12  &                      \\
                        &  512  &  21  &  11  &                      \\
    \bottomrule
  \end{tabular}
  \caption{\emph{Bits} inutilizados em $\btwo{}$ para vários valores de
    $w$ e $m$.}\label{table:bits}
\end{table}

\section{\wotsr{}}\label{section:wotsr}

A segunda proposta consiste na busca por resumos criptográficos com
características que habilitam a geração ou verificação de assinaturas de
maneira mais eficiente. Este processo é independente do esquema subjacente,
consistindo do pré-processamento da mensagem através de sua concatenação com
uma palavra arbitrária. Deste modo, o valor do resumo criptográfico
resultante pode ser maximizado ou minimizado, de acordo com a compensação
desejada, consequentemente alterando a extensão das cadeias de resumos
derivadas do mesmo. Esta estratégia é baseada no esquema publicado
em~\cite{Steinwandt:article:2008:oct}.

Tome $M$ como uma mensagem qualquer e o parâmetro de busca $R \in
\mathbb{N}^{*}$. Na etapa de geração da assinatura, compute todos os resumos
\begin{equation}
  D = \{\hash{M \concat r} : 0 \leq r < R\}
\end{equation}
e interprete-os como $t_{1}$ palavras de base-$w$, formando tuplas $\bone^{r}$,
como explicado na Subseção~\ref{subsection:wots}. A fim de escolher o
elemento mais conveniente para que a geração de assinaturas seja eficiente,
tome $r$ de modo a produzir a menor soma entre as tuplas, representado por
\begin{equation}
  k = \argmin_{r \in \{0, \dots, R - 1\}} \sum \bone^{r}.
\end{equation}
De modo análogo, para melhorar a verificação de assinaturas, obtenha $r$ que
gere a maior soma entre as tuplas, ou seja,
\begin{equation}
  k = \argmax_{r \in \{0, \dots, R - 1\}} \sum \bone^{r}.
\end{equation}
Então, $d = \hash{M \concat k}$ é considerado para a execução do esquema. Note
que a concatenação de valores pseudoaleatórios pode ser realizada, entretanto
aplicações de funções de resumo criptográfico tornam a saída completamente
difusa, e portanto, a relevância do conteúdo das palavras é diminuída.

Observe que o cálculo repetido do conjunto de resumos $D$ implica em um custo
computacional ampliado na geração da assinatura. Portanto, é desejável que
exista um limite para este parâmetro, visto que para alguns parâmetros $w$,
este cálculo pode representar uma parte considerável do processamento total
nesta etapa. Uma abordagem estatística é aplicada para este fim. Considerando
que uma função de resumo criptográfico deve produzir saídas uniformemente
distribuídas e aparentemente aleatórias, então frações destas saídas também
devem o ser.

\begin{figure}
  \begin{minipage}[t]{.495\linewidth}
    \centering
    \begin{tikzpicture}[scale=0.65]
      \begin{axis}[
        xtick align=inside, ymin=0, /pgf/number format/.cd, 1000 sep={},
        scaled x ticks=false, ticklabel style={font=\tiny}, xlabel near ticks,
        ylabel near ticks, ylabel=Probabilidades,
        xlabel=$\mu(\mathcal{B}_{1}^{i})$
      ]
        \addplot[black, fill=gray!25, hist={density, data=x, bins=50}]
          file {support/data.txt};
      \end{axis}
      \begin{axis}[
        ticks=none, ymin=0, legend style={font=\tiny, cells={align=left}}
      ]
        \addplot[dashed, thick]
          gnuplot [raw gnuplot] {plot 'support/data.txt' smooth kdensity};
        \legend{$\mu' \approx 32792$ \\ $\sigma \approx 4707$}
      \end{axis}
    \end{tikzpicture}
  \end{minipage}
  \begin{minipage}[t]{.495\linewidth}
    \centering
    \begin{tikzpicture}[scale=0.65]
      \begin{axis}[
        axis lines=left, xlabel=$R$, legend style={at={(1, 0.5)}, anchor=east},
      ]
        \addplot[domain=0:200, samples=100, thick, densely dashed]
          {1 - (1 - 0.1587)^x};
        \addlegendentry{$P(\mu(\bone^{i}) > \mu' + 1\sigma)$}
        \addplot[domain=0:200, samples=100, thick, loosely dashdotdotted]
          {1 - (1 - 0.0228)^x};
        \addlegendentry{$P(\mu(\bone^{i}) > \mu' + 2\sigma)$}
        \addplot[domain=0:200, samples=100, thick, dashdotted]
          {1 - (1 - 0.0013)^x};
        \addlegendentry{$P(\mu(\bone^{i}) > \mu' + 3\sigma)$}
      \end{axis}
    \end{tikzpicture}
  \end{minipage}
  \begin{minipage}[t]{.45\linewidth}
    \caption{Histograma normalizado de $\mu(\bone^{i})$, com 50
      classes.}\label{fig:hist}
  \end{minipage}\qquad
  \begin{minipage}[t]{.45\linewidth}
    \caption{Valores de $R$ para que modificações de $\bone^{i}$ sejam
      efetivas.}\label{fig:func}
  \end{minipage}
\end{figure}

Portanto, se os valores em $\bone{}$ seguem a distribuição uniforme discreta,
pelo teorema central do limite, computações repetidas de $\mu(\bone{})$ tomarão
a forma de uma distribuição Gaussiana. Então,
\begin{equation}
  \mu' = \lim_{n \to \infty}
    \mu(\{\mu(\bone^{i}) : 0 \leq i \leq n\}) = 2^{w - 1}.
\end{equation}
Para assegurar este comportamento, uma instância de \wots{} foi produzida com
os parâmetros $w = 16$, $m = 256$ e $\hh{} =$ SHA-256, e os resumos
\begin{equation}
  \{\hash{\lambda_{i}} : 0 \leq i \leq 2^{16} - 1, \lambda_{i}
    \random{} \binwds{32}\}
\end{equation}
foram calculados. As médias das tuplas $\bone^{i}$ são apresentadas na
Figura~\ref{fig:hist}, concretizando os fatos acima.

Assim, este resultado é utilizado a fim de fornecer valores razoáveis para $R$.
Aplicando a tabela da distribuição normal padrão com desvio padrão $\sigma$,
identificam-se as probabilidades de $\mu(\bone^{i})$ estar localizada após
$\mu'$, e em especial, após intervalos de desvio padrão:
\begin{align}
  \begin{split}
    P(\mu(\bone^{i}) > \mu' + 1\sigma) &= 0.1587, \\
    P(\mu(\bone^{i}) > \mu' + 2\sigma) &= 0.0228, \\
    P(\mu(\bone^{i}) > \mu' + 3\sigma) &= 0.0013.
  \end{split}
\end{align}
Então, para garantir que estes eventos aconteçam com probabilidade $\geq 98\%$,
a distribuição binomial é utilizada a fim de procurar a quantidade mínima de
experimentos em que pelo menos um destes produza o valor desejado. Este
comportamento pode ser visualizado na Figura~\ref{fig:func}, com quantidades
sugeridas de $\{25, 200, 3500\}$ para, respectivamente, parâmetros $w = \{4, 8,
16\}$, recomendados em~\cite[Capítulo 6]{Huelsing:report:2018:may}. Note que
os múltiplos de $\sigma$ utilizados facilitam o cálculo das probabilidades
denotadas acima, contudo estes valores podem ser substituídos por outros
que sejam adequados, a fim de construir novos critérios para a escolha de $R$.

Como a modificação não afeta mecanismos internos do esquema, é necessário
discutir as consequências da concatenação de um dado $\lambda_{k}$ à mensagem
original, e do processo de busca por este dado. A maximização ou minimização
das tuplas $\bone^{i}$ introduz um comportamento estável nos \emph{bits} mais
significativos de cada elemento da tupla, \emph{i.e.} torna-se mais comum que
estes possuam valores antecipáveis. Isto é possivelmente explorável através de
criptoanálise diferencial aplicada sobre \emph{bits} fixos na construção
Merkle---Damgård, posta em prática recentemente através da primeira colisão de
resumos criptográficos produzidos pelo algoritmo
SHA-1~\cite{Stevens:inproc:2017:jul}. Portanto, considerar funções seguras na
escolha de $\hh{}$ é recomendável, como demonstrado em~\cite[Seção
3.2]{Huelsing:inproc:2013:jun}.

\section{Resultados}\label{section:results}

Para demonstrar a eficiência teórica dos esquemas propostos, o número de
iterações da função interna $f$ é comparado entre \wots{}, \wotsb{}, \wotsr{} e
o esquema \wotsbr{}, onde as duas otimizações são aplicadas ao mesmo tempo.
Parâmetros são escolhidos de acordo com a Seção~\ref{section:wotsr}. Considere
mensagens aleatórias de $2^{10}$ caracteres, geradas através de
\texttt{/dev/urandom}.

A Figura~\ref{fig:wotsresults} apresenta o ganho obtido sobre a média
aritmética de $2^{14}$ conjuntos $\mathcal{B}$, enfatizando o efeito de cada
esquema variante. Note que $\mu(\btwo{})$ é afetada negativamente por \wotsr{}
no caso da maximização dos elementos em $\bone{}$. Entretanto, esta diferença
não impacta os ganhos totais de maneira abundante, e a utilização de \wotsbr{}
mitiga esta perda. No caso da minimização de $\mu(\bone{})$, a otimização da
soma de verificação não é aplicada, visto que atuará de maneira contraditória
em relação à proposta.

\begin{figure}
  \centering
  \begin{tikzpicture}
    \pgfplotsset{every axis/.style={
      ybar stacked, x=2cm, enlarge x limits=0.25, bar width=8pt, xtick=data,
      symbolic x coords={4, 8, 16}, ymin=0, ymax=55, try min ticks=5,
      xtick style={draw=none}, xlabel=$w$, ylabel=Redução do
      N\textsuperscript{\underline{\scriptsize o}} de iterações de $f$,
      yticklabel={\pgfmathparse{\tick}\pgfmathprintnumber{\pgfmathresult}\%},
      legend pos=north west, legend style={draw=none},
      axis x line*=top, extra y ticks={0}, extra y tick labels={},
      extra tick style={grid=major}, major grid style={draw=gray!90},
      scale=0.75,
    }}
    \begin{axis}[
      title=Maximização de $\mu(\bone{})$, title style={yshift=0.75cm}
    ]
      \addplot+[
        black, nodes near coords={R = 25}, every node near coord/.style={
          below, font=\scriptsize, xshift=-10pt, rotate=90, anchor=east,
        },
      ]
        coordinates {(4, 0.00001) (8, 0.00001) (16, 0.00001)};
      \addplot+[
        black, nodes near coords={R = 200}, every node near coord/.style={
          below, font=\scriptsize, rotate=90, anchor=east,
        },
      ]
        coordinates {(4, 0.00001) (8, 0.00001) (16, 0.00001)};
      \addplot+[
        black, nodes near coords={R = 3500}, every node near coord/.style={
          below, font=\scriptsize, xshift=10pt, rotate=90, anchor=east,
        },
      ]
        coordinates {(4, 0.00001) (8, 0.00001) (16, 0.00001)};
    \end{axis}
    \begin{axis}[bar shift=-10pt, hide axis]
      \addplot+[black, fill=white, postaction={pattern=north east lines}]
        coordinates {(4, 14.4) (8, 19.8) (16, 25.6)};
      \addplot+[black, fill=white, postaction={pattern=crosshatch dots}]
        coordinates {(4, 2.3)  (8, 2.2)  (16, 2.0)};
      \legend{\wotsr{}, \wotsb{}}
    \end{axis}
    \begin{axis}[hide axis]
      \addplot+[black, fill=white, postaction={pattern=north east lines}]
        coordinates {(4, 18.3) (8, 25.5) (16, 33.0)};
      \addplot+[black, fill=white, postaction={pattern=crosshatch dots}]
        coordinates {(4, 5.4)  (8, 5.4)  (16, 5.4)};
    \end{axis}
    \begin{axis}[bar shift=10 pt, hide axis]
      \addplot+[black, fill=white, postaction={pattern=north east lines}]
        coordinates {(4, 23.8) (8, 32.9) (16, 41.7)};
      \addplot+[black, fill=white, postaction={pattern=crosshatch dots}]
        coordinates {(4, 10.5) (8, 10.5) (16, 10.5)};
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}
    \pgfplotsset{every axis/.style={
      ybar stacked, x=2cm, enlarge x limits=0.25, bar width=8pt, xtick=data,
      symbolic x coords={4, 8, 16}, ymin=0, ymax=55, try min ticks=5,
      xtick style={draw=none}, xlabel=$w$, yticklabels={,,},
      legend pos=north west, legend style={draw=none},
      axis x line*=top, extra y ticks={0}, extra y tick labels={},
      extra tick style={grid=major}, major grid style={draw=gray!90},
      scale=0.75,
    }}
    \begin{axis}[
      title=Minimização de $\mu(\bone{})$, title style={yshift=0.75cm}
    ]
      \addplot+[
        black, nodes near coords={R = 25}, every node near coord/.style={
          below, font=\scriptsize, xshift=-10pt, rotate=90, anchor=east,
        },
      ]
        coordinates {(4, 0.00001) (8, 0.00001) (16, 0.00001)};
      \addplot+[
        black, nodes near coords={R = 200}, every node near coord/.style={
          below, font=\scriptsize, rotate=90, anchor=east,
        },
      ]
        coordinates {(4, 0.00001) (8, 0.00001) (16, 0.00001)};
      \addplot+[
        black, nodes near coords={R = 3500}, every node near coord/.style={
          below, font=\scriptsize, xshift=10pt, rotate=90, anchor=east,
        },
      ]
        coordinates {(4, 0.00001) (8, 0.00001) (16, 0.00001)};
    \end{axis}
    \begin{axis}[bar shift=-10pt, hide axis]
      \addplot+[black, fill=white, postaction={pattern=north east lines}]
        coordinates {(4, 16.03) (8, 21.41) (16, 27.12)};
    \end{axis}
    \begin{axis}[hide axis]
      \addplot+[black, fill=white, postaction={pattern=north east lines}]
        coordinates {(4, 19.32) (8, 26.83) (16, 34.83)};
    \end{axis}
    \begin{axis}[bar shift=10 pt, hide axis]
      \addplot+[black, fill=white, postaction={pattern=north east lines}]
        coordinates {(4, 26.53) (8, 36.48) (16, 46.56)};
    \end{axis}
  \end{tikzpicture}
  \caption{Efeitos da aplicação das otimizações propostas
    no \wots{}.}\label{fig:wotsresults}
\end{figure}

Considerando a maximização de $\mu(\bone{})$, uma redução de aproximadamente
$2^{w}$ iterações de $f$ para o esquema \wotsb{} é observada, condizente com o
número de \emph{bits} inutilizados apresentados na Tabela~\ref{table:bits}. No
caso de \wotsr{}, são observadas reduções de até $25\%$ para $w = 4$, $33\%$
para $w = 8$ e $42\%$ para $w = 16$. Aplicando ambas as otimizações, o esquema
\wotsbr{} resulta em melhorias de até $28\%$, $39\%$ e $52\%$, respectivamente.
No caso da minimização, ocorrem refinamentos de $28\%$, $35\%$ e $47\%$.

Note que a redução no cômputo destas iterações é diretamente traduzida na etapa
complementar, ou seja, na maximização de $\mu(\bone{})$, existirá um aumento do
número de iterações na geração da assinatura, proporcional à otimização obtida
no passo de verificação. O mesmo conceito é aplicado para a minimização.
Ademais, é preciso considerar a busca de $k$ junto aos custos da
geração da assinatura. Em vista disso, valores de $R$ muito altos em relação ao
parâmetro $w$ são indesejáveis quando este é reduzido, \emph{e.g.} com $w = 4$,
o valor $R = 200$ torna-se uma fração substancial do custo total para a geração
da assinatura. Ainda assim, casos de uso onde mostra-se necessário otimizar
completamente o passo de verificação podem fazer uso de valores excedentes para
$R$.

\subsection{Impacto em esquemas baseados
  em árvores de Merkle}\label{subsection:impact}

Evidentemente, as otimizações propostas nos esquemas \wotsb{} e \wotsr{} podem
ser aplicadas a quaisquer variantes da família Winternitz. Consequentemente,
qualquer esquema baseado em árvores de Merkle pode fazer uso de instâncias
otimizadas destes em suas folhas. A fim de demonstrar esta afirmação, a
implementação de \wotsplus{}, esquema de assinatura única escolhido para a
variante de \xmss{}, definido em~\cite[Seção 3.1]{Huelsing:report:2018:may} e
explorado na Subseção~\ref{subsection:wotsplus}, é modificada de acordo, e pode
ser encontrada em \url{https://github.com/zambonin/xmss-reference}.

A Figura~\ref{fig:xmssresults} apresenta os resultados obtidos, na forma da
média do tempo de execução em milissegundos de $2^{14}$ instâncias dos esquemas
\xmss{}, \xmssb{}, \xmssr{} e \xmssbr{}, de acordo com a notação fixada nas
Seções~\ref{section:wotsb} e~\ref{section:wotsr}. Note que $w = 16$ não é
considerado visto que, para este parâmetro, a etapa de geração de chaves para o
esquema \xmss{} é demasiado prolongada. Novamente, a otimização da soma de
verificação não é considerada quando é desejável otimizar a geração de
assinaturas.

Os experimentos foram realizados utilizando um computador com as seguintes
especificações: 8 GB de RAM DDR3 @ 1333MHz, Intel Core i5 4570 @ 3.2GHz e
\texttt{gcc} 8.1.1. Neste ambiente, observe que qualquer valor de $R$ melhora o
tempo de verificação ao aplicar a maximização de $\mu(\bone{})$ e otimização da
soma de verificação, obtendo melhoras de até $22\%$ com $w = 4$ e $36\%$ para
$w = 8$. Entretanto, a escolha de valores muito altos para $R$ na aplicação da
minimização de $\mu(\bone{})$ torna o passo de geração de assinatura mais
lento. Em especial, a Figura~\ref{fig:xmssresults} apresenta um valor fora da
escala do gráfico, demonstrando uma grande perda neste aspecto. Assim, são
recomendados os valores $R \leq 25$ para $w = 4$, e $R \leq 200$ para $w = 8$.

\begin{figure}
  \centering
  \begin{tikzpicture}
    \pgfplotsset{every axis/.style={
      ybar stacked, x=2cm, enlarge x limits=0.5, bar width=8pt, xtick=data,
      symbolic x coords={4, 8}, ymin=-10, ymax=40, try min ticks=5,
      xtick style={draw=none}, xlabel=$w$,
      ylabel=Redução do tempo de execução (ms),
      yticklabel={\pgfmathparse{\tick}\pgfmathprintnumber{\pgfmathresult}\%},
      legend pos=north west, legend style={draw=none},
      axis x line*=top, extra y ticks={-10}, extra y tick labels={},
      extra tick style={grid=major}, major grid style={draw=gray!90},
      scale=0.75,
    }}
    \begin{axis}[
      title=Maximização de $\mu(\bone{})$, title style={yshift=0.75cm}
    ]
      \addplot+[
        black, nodes near coords={R = 25}, every node near coord/.style={
          font=\scriptsize, yshift=-26.5pt, xshift=-10pt,
          rotate=90, anchor=east,
        },
      ]
        coordinates {(4, 0.00001) (8, 0.00001)};
      \addplot+[
        black, nodes near coords={R = 200}, every node near coord/.style={
          font=\scriptsize, yshift=-26.5pt, rotate=90, anchor=east,
        },
      ]
        coordinates {(4, 0.00001) (8, 0.00001)};
      \addplot+[
        black, nodes near coords={R = 3500}, every node near coord/.style={
          font=\scriptsize, yshift=-26.5pt, xshift=10pt,
          rotate=90, anchor=east,
        },
      ]
        coordinates {(4, 0.00001) (8, 0.00001)};
    \end{axis}
    \begin{axis}[bar shift=-10pt, hide axis]
      \addplot+[black, fill=white, postaction={pattern=north east lines}]
        coordinates {(4, 11.2) (8, 18.3)};
      \addplot+[black, fill=white, postaction={pattern=crosshatch dots}]
        coordinates {(4, 2.0) (8, 3.9)};
      \legend{\xmssr{}, \xmssb{}}
    \end{axis}
    \begin{axis}[hide axis]
      \addplot+[black, fill=white, postaction={pattern=north east lines}]
        coordinates {(4, 15.5) (8, 25.2)};
      \addplot+[black, fill=white, postaction={pattern=crosshatch dots}]
        coordinates {(4, 0.6) (8, 3.4)};
    \end{axis}
    \begin{axis}[bar shift=10 pt, hide axis]
      \addplot+[black, fill=white, postaction={pattern=north east lines}]
        coordinates {(4, 19.9) (8, 31.9)};
      \addplot+[black, fill=white, postaction={pattern=crosshatch dots}]
        coordinates {(4, 2.0) (8, 3.5)};
    \end{axis}
  \end{tikzpicture}
  \begin{tikzpicture}
    \pgfplotsset{every axis/.style={
      ybar stacked, x=2cm, enlarge x limits=0.5, bar width=8pt, xtick=data,
      symbolic x coords={4, 8}, ymin=-10, ymax=40, try min ticks=5,
      xtick style={draw=none}, xlabel=$w$, yticklabels={,,},
      legend pos=north west, legend style={draw=none},
      axis x line*=top, extra y ticks={-10}, extra y tick labels={},
      extra tick style={grid=major}, major grid style={draw=gray!90},
      scale=0.75,
    }}
    \begin{axis}[
      title=Minimização de $\mu(\bone{})$, title style={yshift=0.75cm}
    ]
      \addplot+[
        black, nodes near coords={R = 25}, every node near coord/.style={
          font=\scriptsize, yshift=-26.5pt, xshift=-10pt,
          rotate=90, anchor=east,
        },
      ]
        coordinates {(4, 0.00001) (8, 0.00001)};
      \addplot+[
        black, nodes near coords={R = 200}, every node near coord/.style={
          font=\scriptsize, yshift=-26.5pt, rotate=90, anchor=east,
        },
      ]
        coordinates {(4, 0.00001) (8, 0.00001)};
      \addplot+[
        black, nodes near coords={R = 3500}, every node near coord/.style={
          font=\scriptsize, xshift=10pt, yshift=-26.5pt,
          rotate=90, anchor=east,
        },
      ]
        coordinates {(4, 0.00001) (8, 0.00001)};
    \end{axis}
    \begin{axis}[bar shift=-10pt, hide axis]
      \addplot+[black, fill=white, postaction={pattern=north east lines}]
        coordinates {(4, 9.5) (8, 14.6)};
    \end{axis}
    \begin{axis}[hide axis]
      \addplot+[black, fill=white, postaction={pattern=north east lines}]
        coordinates {(4, -3.6) (8, 17.2)};
    \end{axis}
    \begin{axis}[bar shift=10 pt, hide axis]
      \addplot+[black, fill=white, postaction={pattern=north east lines}]
        coordinates {(4, -9.25) (8, -8.5)};
    \end{axis}
    \draw [ultra thick, white, decoration={snake, amplitude=1pt}, decorate]
      (0.9, 0.2) -- (1.3, 0.2);
  \end{tikzpicture}
  \caption{Efeito das otimizações incluídas no
    \xmss{}.}\label{fig:xmssresults}
\end{figure}

A compensação justa de processamento entre etapas complementares, preservada em
esquemas da família Winternitz, apenas ocorre em esquemas baseados em árvores
de Merkle na minimização de $\bone{}$ com $R$ de grandeza razoável. Esta
impossibilidade do uso de valores excedentes para o parâmetro estabelece uma
discussão sobre o impacto das estruturas de árvore sobre as otimizações
propostas anteriormente. Isto ocorre devido à fatores necessários para o
funcionamento prático dos esquemas, como possíveis implementações ingênuas do
processo de busca do valor $k$, gerando considerável ônus no passo de criação
de assinatura, consequentemente reduzindo o ganho obtido pelas propostas.

Além disso, note que a implementação de \xmss{} utilizada pode apresentar como
comportamento opcional a execução do algoritmo de travessia discutido na
Subseção~\ref{subsubsection:bds}, a fim de habilitar um ganho de desempenho
geral ao longo das etapas do esquema. Testes iniciais com a implementação
ingênua demonstraram que os ganhos eram diretamente proporcionais. Assim, a
travessia \bds{} é utilizada nos experimentos a fim de permitir testes mais
extensivos, e demonstra a coexistência entre as otimizações propostas e este
artifício.

\chapter{Conclusão}\label{chapter:conclusion}

Neste trabalho, esquemas de assinatura digital baseados em funções de resumo
criptográfico foram discutidos, a fim de prover um embasamento teórico para o
desenvolvimento de otimizações sobre estes esquemas. Vários conceitos
relevantes para a área são apresentados, como a estrutura de dados chamada de
árvore de Merkle, que habilita a criação de esquemas de assinatura digital
convencionais com múltiplas instâncias de assinaturas únicas, o encadeamento de
árvores a fim de aumentar o número de mensagens passíveis de assinatura, e o
gerenciamento sobre estas árvores quando seu armazenamento total se torna
impraticável.

O resultado principal, consistindo na otimização da família de esquemas de
assinatura digital única Winternitz, introduz um parâmetro de compensação que
habilita o deslocamento do cômputo de iterações de $f$ da geração da assinatura
para a verificação, e vice-versa. Para demonstrar este trabalho, experimentos
foram realizados em esquemas do estado da arte, com resultados positivos.

\section{Trabalhos futuros}\label{section:future}

A otimização apresentada na Seção~\ref{section:wotsr} pode considerar a
modificação da tupla $\bone{}$ de acordo com outros critérios, adicionais à
maximização ou minimização de seus elementos, ou substituindo este processo
completamente. Por exemplo, visto que o cômputo de iterações de $f$ é feito
sequencialmente, a busca de um critério a fim de obter elementos $b \in
\bone{}$ próximos em magnitude (\emph{e.g.} a redução do desvio padrão)
habilita o processamento paralelo destas iterações e, portanto, um tempo de
execução reduzido para a geração e verificação de assinaturas. Este mesmo
recurso pode ser utilizado para diminuir o custo da busca por $\bone{}$
considerando o parâmetro $R$, também calculando estes resumos de maneira
paralela.

Experimentos que exploram as propostas do Capítulo~\ref{chapter:tuning} podem
ser realizados em variantes diferentes da família Winternitz, como \wotsprf{} e
\wotst{}, bem como em outros esquemas baseados em árvores de Merkle. Ademais, a
segurança do esquema \wotsr{} deve ser formalizada, visto que a modificação de
$\bone{}$ pode introduzir imperfeições nas cadeias de resumos subsequentes.

Finalmente, vários aspectos são passíveis de discussão em se tratando da
estrutura inerente de esquemas baseados em árvores de Merkle, como o estudo
detalhado de parâmetros ótimos de $R$ no caso da minimização de $\bone{}$, o
comportamento das otimizações apresentadas em esquemas com hiper-árvores, e o
impacto detalhado destas sobre implementações que utilizem algoritmos de
travessia distintos.

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

\apendice{}

\chapter{DESCRIÇÃO DA CIFRA AES}\label{chapter:aes}

Originalmente publicado como Rijndael, o algoritmo conhecido como
AES\sigla{AES}{\emph{Advanced Encryption Standard}} é resultado de um esforço
de padronização para um sistema criptográfico seguro, finalizado ao término do
século XX pelo NIST~\cite{Dworkin:report:2001:nov}\sigla{NIST}{\emph{National
Institute of Standards and Technology}}, a fim de substituir a cifra
DES\sigla{DES}{\emph{Data Encryption Standard}}. Definido como uma cifra de
blocos iterativa, opera sobre uma matriz de estado $A$, onde $A_{i, j} \in
\mathbb{F}_{2^{8}}$\simbolo{$\mathbb{F}_{n}$}{Corpo de Galois de ordem
$n$}\footnote{Definido pelo polinômio irredutível $m(x) = x^{8} + x^{4} + x^{3}
+ x + 1$. Adições e multiplicações sobre elementos em corpos da forma
$\mathbb{F}_{2^{n}}$ são análogas a operações computacionais.}, $0 \leq i, j
\leq 3$, a partir de uma chave $K$ de tamanho $n \in \{128, 192, 256\}$.
Consiste em aplicações sequenciais de quatro operações ordenadas sobre $A$. A
quantidade destas aplicações, denominadas rodadas ($n_{r}$), depende
diretamente do tamanho da chave: $n = 128 \rightarrow n_{r} = 10, n = 192
\rightarrow n_{r} = 12, n = 256 \rightarrow n_{r} = 14$.

Uma rotina de expansão de chave existe para que $K$ seja propagada em todas as
rodadas com valores derivados, porém variados entre si. A presença desta rotina
é fundamentada pela construção abstrata no qual o Rijndael é baseado, chamada
de rede de substituição-permutação, onde o estado inicial é primeiramente
modificado com uma chave de rodada. As operações e rotinas serão descritas
abaixo.

\begin{enumerate}[labelsep=0.5em, label=\roman*.]

  \item \textsc{SubBytes}: realiza-se a reposição de $A_{i, j}$ pelo seu valor
      correspondente em uma caixa de substituição, também chamada de
        \emph{S-box}, construída a partir de uma transformação afim em $A_{i,
        j}^{-1}$. A escolha da linha e coluna nesta matriz é feita,
        respectivamente, a partir dos \emph{nibbles} mais e menos
        significativos do elemento.

  \item \textsc{ShiftRows}: cada linha de $A$, $A_{i}$, é deslocada
      circularmente à esquerda $i$ vezes.

  \item \textsc{MixColumns}: cada coluna de $A$, $A_{j}$, é multiplicada pelo
      polinômio $c = 3x^{3} + x^{2} + x + 2$, módulo $x^{4} + 1$, para que o
        resultado ainda seja um polinômio de grau máximo 3, apto a ser
        representado na coluna.

  \item \textsc{AddRoundKey}: a operação de ou exclusivo \emph{bit} a
      \emph{bit} é aplicada entre $A$ e o bloco da chave referente à rodada.

  \item \textsc{KeyExpansion}: consiste da criação de um conjunto de palavras
      $K_{e}$ de 32 \emph{bits}. Tome $\ell = \frac{n}{32}$, e assumindo que é
        necessário criar palavras suficientes para utilização em todas as
        rodadas do algoritmo, então $t = \ell \cdot (n_{r} + 1)$ e $K_{e} =
        \{k_{0}, \dots, k_{t - 1}\}$. A lista de constantes $RC$ com elementos
        em $\mathbb{F}_{2^{8}}$ é definida pela recursão
        \begin{equation}
          RC_{0} = x^{0}, \quad RC_{1} = x^{1}, \quad
          RC_{j} = x \cdot RC_{j - 1}, \; j \geq 2.
        \end{equation}
        Inicialmente, $K$ é dividida em $\ell$ palavras, que compõem o começo
        de $K_{e}$. Para os elementos restantes, ou seja, $\forall i \geq \ell$,
        \begin{equation}
          k_{i} = k_{i - \ell} +
          \begin{cases}
            \textsc{SubBytes}(k_{i - 1}
              \stackrel{\curvearrowright}{\ll{}} 8) + RC_{\frac{i}{\ell}},
              \text{ se } i \equiv 0 \pmod{4}, \\
            \textsc{SubBytes}(k_{i - 1}),
              \text{ se } \ell = 8 \text { e } i \equiv 4 \pmod{8}, \\
            k_{i - 1}, \text{ caso contrário.}
          \end{cases}
        \end{equation}\simbolo{$\stackrel{\curvearrowright}{
            \ll{}}$}{Deslocamento circular à esquerda de \emph{bits}}

\end{enumerate}

Assim, uma função que criptografa uma mensagem $m$ e retorna um texto cifrado
$c$ pode ser representada pelo Algoritmo~\ref{alg:aesencrypt}. A mensagem é
primeiramente codificada em $A$ da seguinte maneira: $A_{i, j} = m_{i + 4j}, 0
\leq i, j \leq 3$. Note que \textsc{MixColumns} é ignorado na última rodada, a
fim de facilitar a reversibilidade da cifra.

\begin{algorithm}
  \begin{algorithmic}
    \REQUIRE{}  $m \in \binwds{128}, \enspace
      K \in \cup_{n \in \{128, 192, 256\}} \binwds{n}$
      \COMMENT{texto plano e chave}
    \ENSURE{}  $c \in \binwds{128}$ \COMMENT{texto cifrado}

    \STATE{}  $A \leftarrow m$
    \STATE{}  $\{k_{0} \dots k_{(n_{r} + 1) \cdot \ell}\}
      \leftarrow \textsc{KeyExpansion}(K)$
    \STATE{}  $A \leftarrow \textsc{AddRoundKey}(A,
      \{k_{0}, \dots, k_{\ell - 1}\})$

    \FOR{$i \leftarrow 1$ até $n_{r} - 1$}
      \STATE{}  $A \leftarrow \textsc{SubBytes}(A)$
      \STATE{}  $A \leftarrow \textsc{ShiftRows}(A)$
      \STATE{}  $A \leftarrow \textsc{MixColumns}(A)$
      \STATE{}  $A \leftarrow \textsc{AddRoundKey}(A,
        \{k_{i \cdot \ell}, \dots, k_{(i + 1) \cdot \ell - 1}\})$
    \ENDFOR{}

    \STATE{}  $A \leftarrow \textsc{SubBytes}(A)$
    \STATE{}  $A \leftarrow \textsc{ShiftRows}(A)$
    \STATE{}  $A \leftarrow \textsc{AddRoundKey}(A,
      \{k_{n_{r} \cdot \ell}, \dots, k_{(n_{r} + 1) \cdot \ell - 1}\})$

    \STATE{}  $c \leftarrow A$
  \end{algorithmic}
  \caption{Codificação do AES.}\label{alg:aesencrypt}
\end{algorithm}

Para que a cifra seja caracterizada como simétrica, é preciso criar uma função
que faça o inverso do procedimento acima. Assim, suas etapas precisam ser
modificadas de acordo.

\begin{enumerate}[labelsep=0.5em, label=\roman*.]

  \item \textsc{InvShiftRows}: cada linha de $A$, $A_{i}$, é deslocada
      circularmente à direita $i$ vezes.

  \item \textsc{InvSubBytes}: é necessário computar a transformação afim
      inversa para cada elemento $A_{i, j}$, e depois calcular sua inversa
        multiplicativa.

  \item \textsc{InvMixColumns}: cada coluna de $A$, $A_{j}$, é multiplicada pela
      inversa multiplicativa $d = c^{-1}$, obtida por
        \begin{align}
          \begin{split}
            (3 x^{3} + x^{2} + x + 2) \times d &\equiv 1 \pmod{x^{4} + 1} \\
            d &= 11 x^{3} + 13 x^{2} + 9 x + 14.
          \end{split}
        \end{align}

\end{enumerate}

Por fim, o resultado é representado pelo Algoritmo~\ref{alg:aesdecrypt}. Note a
mudança da ordem das etapas, e a utilização invertida de $K_{e}$. Finalmente,
$c$ é codificado no estado de maneira análoga ao algoritmo anterior.

\begin{algorithm}
  \begin{algorithmic}
    \REQUIRE{}  $c \in \binwds{128}, \enspace
      K \in \cup_{n \in \{128, 192, 256\}} \binwds{n}$
      \COMMENT{texto cifrado e chave}
    \ENSURE{}  $m \in \binwds{128}$ \COMMENT{texto plano}

    \STATE{}  $A \leftarrow c$
    \STATE{}  $\{k_{0} \dots k_{(n_{r} + 1) \cdot \ell}\}
      \leftarrow \textsc{KeyExpansion}(K)$
    \STATE{}  $A \leftarrow \textsc{AddRoundKey}(A,
      \{k_{n_{r} \cdot \ell}, \dots, k_{(n_{r} + 1) \cdot \ell - 1}\})$

    \FOR{$i \leftarrow n_{r} - 1$ até $1$}
      \STATE{}  $A \leftarrow \textsc{InvShiftRows}(A)$
      \STATE{}  $A \leftarrow \textsc{InvSubBytes}(A)$
      \STATE{}  $A \leftarrow \textsc{AddRoundKey}(A,
        \{k_{i \cdot \ell}, \dots, k_{(i + 1) \cdot \ell - 1}\})$
      \STATE{}  $A \leftarrow \textsc{InvMixColumns}(A)$
    \ENDFOR{}

    \STATE{}  $A \leftarrow \textsc{InvShiftRows}(A)$
    \STATE{}  $A \leftarrow \textsc{InvSubBytes}(A)$
    \STATE{}  $A \leftarrow \textsc{AddRoundKey}(A,
      \{k_{0}, \dots, k_{\ell - 1}\})$

    \STATE{}  $m \leftarrow A$
  \end{algorithmic}
  \caption{Decodificação do AES.}\label{alg:aesdecrypt}
\end{algorithm}

Discussões detalhadas sobre as etapas do algoritmo, a fundamentação algébrica
por trás deste, escolhas feitas em cada etapa, criptoanálise relacionada e
outros tópicos avançados podem ser consultados junto ao livro original de
descrição do Rijndael~\cite{Daemen:book:2002}.

\chapter{ARTIGO DO TCC}\label{chapter:paper}

\includepdf[pages=-]{support/tuning-winternitz.pdf}

\end{document}