\documentclass[12pt]{article}
\usepackage{helvet}
\usepackage[portuguese]{babel}
\usepackage[utf8]{inputenc}
\usepackage[margin=2.54cm]{geometry}
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancyhead[L]{}
\usepackage{amsthm}
\newtheorem{mydef}{Definição}
\usepackage{graphicx}
\usepackage{float}
\floatstyle{ruled}
\newfloat{theorem}{htbp}{loa}
\floatname{theorem}{}
\newfloat{algorithm}{htbp}{loa}
\floatname{algorithm}{Algoritmo}
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{mathabx}
\usepackage{url}
\theoremstyle{definition}
\newtheorem{exmp}{Exemplo}

\usepackage{indentfirst}

\usepackage{setspace}
\onehalfspacing

\begin{document}
\thispagestyle{empty}

\newpage
\thispagestyle{empty}
\tableofcontents


\newpage
\thispagestyle{plain}
\section{Introdução}
\label{INTRO}

O presente trabalho foi elaborado no âmbito da unidade curricular de Criptografia, leccionada no 4º Ano do Mestrado Integrado em Engenharia Biomédica — Ramo de Informática Médica, e propõe-se explorar a temática dos problemas {\it hard} em reticulados, bem como as técnicas criptográficas cuja construção e/ou prova de segurança se baseiam nestes últimos.

\subsection{Criptografia de Chave Pública}
\label{CPUBLICA}

Numa fase de desenvolvimento inicial, os sistemas criptográficos baseavam-se no conceito de simetria, que partia da utilização da mesma chave por parte do emissor e do receptor da mensagem, o que, pese embora permitisse providenciar segurança da informação a nível teórico, apresentava a séria desvantagem de requerer elevados níveis de aleatoriedade e chaves de tamanho consideravelmente elevado. De forma a contrariar esta premissa, em 1976, Diffie e Hellman desenvolveram um criptosistema que introduzia a noção de funções {\it trapdoor}, consideradas a base da criptografia assimétrica. Uma função {\it trapdoor} consiste numa função unidireccional — isto é, uma função $f$ que permite calcular $f(x)$ partindo de $x$ de forma relativamente fácil, mas que dificulta o cálculo de $x$ a partir de $f(x)$ — com a particularidade de acrescentar que existe uma dada informação secreta $y$ que pode ser utilizada para fazer com que o cálculo de $x$ a partir de $f(x)$ seja fácil. Neste sentido, Diffie e Hellman propuseram a Criptografia de Chave Pública, através da qual pretendiam que se criasse um par de chaves — uma pública e uma privada — matematicamente relacionadas. Uma das possíveis utilizações seria a de o emissor de uma mensagem poder utilizar a chave pública do receptor para cifrar uma mensagem, que seria depois decifrada recorrendo à chave privada. A chave pública poderia ser acedida por qualquer utilizador sem que isso comprometesse a segurança da respectiva chave privada, na medida em que derivar a chave privada partindo deste conhecimento seria tão difícil quanto inverter uma função unidireccional. Face à criptografia simétrica, este conceito apresenta uma vantagem inegável, que é a de requerer a criação de um par simétrico único de chaves e a distribuição do mesmo por cada par de utilizadores que desejem comunicar de forma privada. Contudo, uma das desvantagens expostas pelos próprios autores prende-se com o facto de, estando as chaves matematicamente relacionadas, nunca seria possível atingir a segurança teórica de alguns dos sistemas simétricos, dado que um adversário com poder computacional ilimitado conseguiria sempre desvendar a informação privada recorrendo a procuras exaustivas. Assim, os criptosistemas de chave pública almejam não a segurança teórica, mas a segurança de uma perspectiva essencialmente prática, tomando em consideração os limites dos poderes computacionais de um potencial adversário — a designada segurança computacional. Esta premissa assume que quebrar um dado criptosistema deve ser, não impossível, mas antes computacionalmente impraticável, motivo pelo qual se adoptou a prática de basear a segurança de um criptosistema na assumpção de que alguns problemas matemáticos são difíceis de resolver recorrendo à computação. Interessa, neste ponto, mencionar uma variável que se torna essencial nesta conjuntura: o parâmetro de segurança, que determina o tamanho do {\it input} e é, normalmente, escolhido de forma a que exista um balanço entre a segurança e a eficiência do sistema. A segurança {\it per se} é normalmente medida em {\it bits} e, para um segurança de $k$ {\it bits}, o esforço temporal e logístico que o adversário tem de desenvolver para quebrar o sistema é equivalente a testar todas as chaves possíveis de tamanho $k$, ou seja, $2^k$ chaves distintas. De forma a garantir que todos os métodos passíveis de quebrar o sistema são impraticáveis, deve atender-se à complexidade computacional dos problemas que lhe são inerentes \cite{PKCGOLD,PKCDH}.

\subsection{Teoria da Complexidade Computacional}
\label{TCOMPLEX}

A Teoria da Complexidade Computacional estende um dos ramos da Teoria da Computação, focando-se especificamente na classificação dos problemas computacionais atendendo à sua dificuldade e no relacionamento entre as classes assim definidas, com o intuito de determinar os limites práticos de operação e funcionalidade dos computadores, entre outros. Considera-se, neste contexto, que um problema é difícil se a solução que dele decorre requer um gasto significativo de recursos — como sejam tempo e capacidade de armazenamento —, quaisquer que sejam as abordagens algorítmicas utilizadas.

Numa primeira fase, interessa explorar a complexidade de uma perspectiva temporal. Neste sentido, torna-se possível distinguir três tipos de complexidade distintos, que se reportam à rapidez (por assim dizer) com que determinados {\it inputs} de tamanho $n$ são resolvidos: {\it best-case}, {\it worst-case} e {\it average-case}. Os dois primeiros encontram-se associados à solução de um problema para o melhor e o pior {\it input} de tamanho $n$, respectivamente, sendo que o último se reporta à complexidade de resolver o problema numa média, tendo em consideração uma distribuição de probabilidades dos {\it inputs}. No âmbito da computação em tempo real, a vertente {\it worst-case} constitui um foco de especial atenção, dado que é relevante ter acesso ao tempo necessário para que, no pior dos casos, um algoritmo termine a sua execução atempadamente. Em \cite{AJTAI}, Ajtai demonstrou que é possível estabelecer uma conexão entre o {\it worst-case} e o {\it average-case} entre determinados problemas de reticulados, o que gerou um enorme interesse em volta da utilização destas estruturas como base para criptosistemas, na medida em que a dificuldade {\it average-case} representa uma propriedade desejável para estes sistemas.

Aos conjuntos de problemas cujas complexidades se encontram relacionadas dá-se o nome de classes de complexidade. Estas podem ser definidas, por exemplo, através de critérios que constringem o tempo e espaço consumidos por um algoritmo. Interessa, no contexto específico deste trabalho, destacar duas classes em particular:

\subsubsection{Classe P}
\label{subsub:FP}

A classe P — de Polinomial — diz respeito a problemas passíveis de serem resolvidos por Deterministic Turing Machines (DTMs) que obedeçam, em termos de tempo de execução, a um limite polinomial, e é, teoricamente, considerada equivalente à noção de 'resolução eficiente', não obstante a existência de excepções \cite{COMPLEX1}.

\subsubsection{Classe NP}
\label{subsub:NP}

Por sua vez, a classe NP — de Polinomial Não-Determinístico — é definida como o cojunto de todos os problemas resolúveis por intermédio de Nondeterministic Turing Machines (NDTMs) em tempo polinomial. Será, portanto, lógico inferir que a classe P está contida na NP, pese embora esta encerre outros problemas, de entre os quais se destacam os NP-Complete — para os quais não são conhecidas soluções que passem por algoritmos de tempo polinomial \cite{COMPLEX1}. Porém, contrariamente à classe P, os problemas NP não podem ser eficientemente resolvidos, podendo antes ser apenas 'eficientemente verificados' \cite{COMPLEX2}.

\vspace{0.5cm}

Uma questão importante na Teoria da Complexidade (e que se encontra, ainda, aberta) prende-se com o facto de não se saber se as classes P e NP são efectivamente coincidentes ou se existem problemas que são exclusivos a NP. Até prova em contrário, assume-se que P $\neq$ NP e considera-se, informalmente, que P é a classe dos problemas 'fáceis', enquanto que NP contém problemas '{\it hard}' — os já referidos NP-Complete — que, com grande probabilidade, não estão contidos em P. Caso se consiga provar que, matematicamente, quebrar um criptosistema é equivalente à resolução de um problema NP-Complete, é possível inferir uma medida razoável da segurança dessa construção e extrapolar uma prova de segurança.

\subsection{Reticulados}
\label{RET}

Os reticulados são, tipicamente, definidos como um sub-grupo discreto de $\mathbb{R}^n$, o espaço vectorial Euclidiano $n$-dimensional, sendo que por 'discreto' se pretende implicar que estes não compreendem pontos de acumulação. Isto é, considerando $D$ como um sub-espaço de $\mathbb{R}^n$, para qualquer {\bf x} pertencente a $D$, existe um $r > 0$ tal que a esfera definida como $\mathcal{B}({\bf x},r) = \{{\bf y} \in \mathbb{R}^n : \|{\bf x}-{\bf y}\| < r\}$ satisfaz $\mathcal{B}({\bf x},r) \cap D = \{{\bf x}\}$. Considere-se, ainda, que qualquer sub-conjunto de um conjunto discreto é igualmente discreto.

\begin{mydef} Um sub-grupo sob a adição de ($\mathbb{R}^n,+$) que apresente a propriedade discreta é denominado de reticulado. Com base nesta propriedade, qualquer sub-grupo de um reticulado é, ele mesmo, um reticulado.
\end{mydef}

Os reticulados podem ainda ser definidos como sub-conjuntos não vazios $\mathcal{L} \subset \mathbb{R}^n$, fechados a operações de subtracção, de tal forma que exista um $r > 0$ para o qual $\mathcal{B}(0,r) \cap \mathcal{L} = \{0\}$. Neste sentido, as propriedades fundamentais dos reticulados podem ser definidas como:

\begin{enumerate}
\item Existe um $r > 0$ tal que, para todo o {\bf x} $\in \mathcal{L}$, não existe qualquer outro elemento {\bf y} $\in \mathcal{L}$ com $\|{\bf x}-{\bf y}\| < r$. De forma equivalente, existe um $r > 0$ tal que $\mathcal{B}({\bf x},r) \cap \mathcal{L} = \{{\bf x}\}$ para todo o {\bf x} $\in \mathcal{L}$;
\item $\mathcal{L}$ é um conjunto fechado, o que implica necessariamente que não possui pontos de acumulação;
\item Caso $S \subseteq \mathbb{R}^n$ seja limitado, então $S$ $\cap$ $\mathcal{L}$ é finito;
\item $\mathcal{L}$ é contável, isto é, apresenta a mesma cardinalidade de um qualquer sub-conjunto pertencente a $\mathbb{N}$.
\end{enumerate}

\begin{figure}[htb!]
\includegraphics[width=.5\textwidth]{Reticulado.pdf}
\centering
\caption{O reticulado $\mathbb{Z}^n$, formado por todos os vectores em $\mathbb{R}^2$ com coeficientes inteiros.}
\label{fig:RET}
\end{figure}

Em espaços vectoriais, um sub-espaço pode ser descrito através da utilização de bases. Considerando $m$ vectores ${\bf b}_1,...,{\bf b}_m \in \mathbb{R}^n$ e um conjunto de combinações lineares $L({\bf b}_1,...,{\bf b}_m)$, estabelece-se que este apenas é discreto (e, por consequência, um reticulado), caso ${\bf b}_1,...,{\bf b}_m \in \mathbb{Q}$ ou caso ${\bf b}_1,...,{\bf b}_m \in \mathbb{R}^n$ sejam linearmente independentes. O facto de um conjunto finito de vectores poder descrever um reticulado permite postular a seguinte definição:

\begin{mydef} Um reticulado $\mathcal{L}$ é dito abrangido pelos geradores ${\bf b}_1,...,{\bf b}_m$ se $\mathcal{L} = L({\bf b}_1,...,{\bf b}_m$. Se os ${\bf b}_i$ forem também linearmente independentes, então ${\bf b}_1,...,{\bf b}_m$ é considerada uma base de $\mathcal{L}$ e, para todo o {\bf x} $\in {\mathcal{L}}$ existem coordenadas $(x_1,...,x_m)$ inteiras e únicas que verificam:
\begin{center}
{\bf x} = $\sum _{i=1}^m x_i{\bf b}_i$
\end{center}
\end{mydef}

Torna-se ainda relevante realçar a definição de {\it rank} de um reticulado, na medida em que os sub-espaços lineares de $\mathbb{R}^n$ possuem uma dimensão que limita o número máximo de vectores linearmente independentes e denota o número de vectores numa base desses mesmos espaços. 

\begin{mydef}Seja $\mathcal{L} \subset \mathbb{R}^n$ um reticulado. O {\it rank} $d$ de $\mathcal{L}$ é definido como sendo a dimensão do sub-espaço {\it span}($\mathcal{L}$), que representa o sub-espaço mínimo contendo $\mathcal{L}$. Caso $n = d$, o reticulado é denominado de {\it full-rank}.
\end{mydef}

De forma semelhante ao que sucede nos sub-espaços, o {\it rank} equivale ao número máximo de vectores linearmente independentes do reticulado, bem como ao número de vectores que compõem a sua base. Porém, neste contexto específico, nem todos os conjuntos de vectores linearmente independentes se qualificam para formar uma base, já que uma dada matriz $\mathcal{B}$, composta por $d$ vectores linearmente independentes $({\bf b_1},...,{\bf b_m})$, constitui uma base de um reticulado $\mathcal{L}$ de {\it rank} $d$ sse não existem vectores não nulos {\bf x} $\in \mathcal{L}$ tais que {\bf x} pertença ao paralelepípedo $\mathcal{P}({\bf b_1},...,{\bf b_m}) = \{\sum_{i=1}^{n} \lambda_1 {\bf b_i} : 0 \leq \lambda_i < 1\}$. Considerando que todo o reticulado $\mathcal{L}$ de {\it rank} $d$ compreende, pelo menos, $d$ vectores linearmente independentes, torna-se possível afirmar que qualquer reticulado $\mathcal{L} \subset \mathbb{R}^n$ tem, no mínimo, uma base, podendo ser escrito como as combinações lineares inteiras de $d$ vectores de base.

\newpage
\thispagestyle{plain}
\section{Problemas Hard em Reticulados}
\label{HARDPROB}

Os problemas {\it hard} baseados em reticulados constituem, conforme já analisado, uma esfera que gira em torno da noção de que não existe uma solução computacional que os resolva de forma eficiente (nem mesmo a computação quântica), o que os torna necessariamente apelativos para aplicações critpográficas, nomeadamente quando comparados com os problemas baseados na Teoria dos Números.

\subsection{Conceitos Básicos}
\label{CONSHORT}

No sentido de compreender a dimensão do problema dos vectores curtos, especificamente, torna-se necessário abordar, previamente, duas temáticas que constituem a sua base: os Mínimos Sucessivos de Minkowski e a Constante de Hermite.

\subsubsection{Mínimos Sucessivos de Minkowski}
\label{MINKOWSKI}

Pela sua propriedade discreta, explorada na Secção \ref{INTRO}, um reticulado $\mathcal{L}$ de {\it rank} pelo menos 1 compreende um vector não nulo que se encontra próximo da origem e cuja norma representa a distância mais curta possível entre quaiquer dois vectores distintos do reticulado — o Primeiro Mínimo Sucessivo $\lambda_1 (\mathcal{L})$. A Figura 1 ilustra o conceito para um dado reticulado $\mathcal{L}(a,b)$, sendo o vector {\bf x} o Primeiro Mínimo Sucessivo respeitante à norma Euclidiana \cite{{DWORK1},{NGUYEN1},{BASE1}}.

\begin{figure}[htb!]
\label{img:SUCMIN}
\includegraphics[width=.5\textwidth]{SUCMIN.pdf}
\centering
\caption{Primeiro mínimo sucessivo $\lambda_1 \mathcal{L}(a,b)$.}
\end{figure}

A aplicação do conceito de Minkowski a outros mínimos sucessivos pode ser generalizada da seguinte forma:

\begin{mydef} Para i = 1,...,d, o mínimo sucessivo de ordem i do reticulado $\mathcal{L}$ de rank d é
\begin{center}
$\lambda_i(\mathcal{L})$=min\{max{$\|x_1\|$,...,$\|x_i\|$}\}, $|x_1,...x_i| \in \mathcal{L}$ linearmente independentes.
\end{center}
\end{mydef}

No seguimento destas assumpções, poder-se-ia assumir que um reticulado deveria ter uma base cujas normas correspondessem precisamente aos mínimos sucessivos. Contudo, e pese embora existam sempre vectores ${\bf v_1},...,{\bf v_d}$ linearmente independentes do reticulado que atingem simultaneamente os mínimos — isto é, $\|{\bf v_i}\|$=$\lambda_i \mathcal{L}$ para todo o $i$ —, assim que $dim(\mathcal{L}) \geq 4$, tais vectores não formam necessariamente uma base do reticulado \cite{NGUYEN1}. A título de exemplo, considere-se o reticulado $\mathcal{L}$ definido como o conjunto de todos os $(x_1,x_2,x_3,x_4) \in$ $\mathbb{Z}^4$ de tal forma que $\sum_{i=1}^{4} {\it x_{i}}$ é par. Uma possível base de $\mathcal{L}$ pode ser representada pela matriz $\mathcal{A}$. A matriz $\mathcal{B}$, por outro lado, não cosntitui uma base adequada: não obstante ser composta por vectores linha linearmente independentes que atingem, da mesma forma, todos os mínimos, o seu determinante é igual a 4.

\begin{minipage}[b]{5cm}
\[
\mathcal{A}=
\begin{pmatrix*}[r]
1 & -1 & 0 & 0\\
1 & 1 & 0 & 0\\
1 & 0 & 1 & 0\\
1 & 0 & 0 & 1
\end{pmatrix*}
\]
\end{minipage} 
\begin{minipage}[b]{15cm} 
\[
\mathcal{B}=
\begin{pmatrix*}[r]
1 & -1 & 0 & 0\\
1 & 1 & 0 & 0\\
0 & 0 & 1 & 1\\
0 & 0 & 1 & -1
\end{pmatrix*}
\]
\end{minipage}
\vspace{0.5cm} 

Este conceito pode ser reforçado através do caso demonstrativo de multiplicação das duas matrizes, já que existem provas de que duas bases originam o mesmo reticulado se (e só se) as suas matrizes estiverem relacionadas por uma matriz unimodular \cite{BASIS1}.

\[
\mathcal{A} {\times} \mathcal{B}=
\begin{pmatrix*}[r]
0 & -2 & 0 & 0\\
2 & 0 & 0 & 0\\
1 & -1 & 1 & 1\\
1 & -1 & 1 & -1
\end{pmatrix*}
\]

\subsubsection{Constante de Hermite}
\label{HERMITE}

A prova de que a quantidade $\lambda_1$($\mathcal{L}$)/vol($\mathcal{L}$)$^{1/{\it d}}$ pode ser limitada, para todo o reticulado $\mathcal{L}$ de {\it rank d} foi dada, pela primeira vez, por Hermite, e dita que:

\begin{mydef} O supremo de $\lambda_1$($\mathcal{L}$)$^{2}$/vol($\mathcal{L}$)$^{2/{\it d}}$ para todo o reticulado $\mathcal{L}$ de {\it rank d} é representado por $\gamma_{d}$ e designado por {\it Constante de Hermite} de dimensão {\it d}.
\end{mydef}
%supremo é o menor dos majorantes%

Embora seja assente que $\gamma_{d}$ é atingido, o processo de cálculo do seu valor exacto constitui um problema árduo, sendo que este é apenas conhecido para os casos em que 1 $\leq$ {\it d} $\leq$ 8 e {\it d} = 24.
\vspace{-0.2cm}
\begin{table}[htb!]
\centering
\caption{Valores actualmente conhecidos para a Constante de Hermite \cite{NGUYEN1}}
\vspace{0.1cm}
\begin{tabular}{| c | c c c c c c c c |}
\hline
{\it d} & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 24\\[0.5ex]

$\gamma_{d}$ & 2/$\sqrt{3}$ & $2^{1/3}$ & $\sqrt{2}$ & $8^{1/5}$ & $(64/3)^{1/6}$ & $64^{1/7}$ & 2 & 4\\[0.5ex]

Aproximação & 1.1547 & 1.2599 & 1.4142 & 1.5157 & 1.6654 & 1.8114 & 2 & 4\\
\hline
\end{tabular}
\label{tab:HERM}
\end{table}

Para todas as dimensões {\it d} $\geq 1$, existe um reticulado $\mathcal{L}$ de {\it rank d} que verifica os valores da Constante de Hermite explicitados na Tabela \ref{tab:HERM} — denominado de reticulado crítico. Da mesma forma, todos os reticulados críticos para cada uma das dimensões mencionadas são conhecidos \cite{NGUYEN1}. As referidas dimensões tornam-se, porém, irrelevantes no caso específico dos problemas {\it hard}, na medida em que, no âmbito desta problemática, as dimensões de interesse situam-se na ordem das centenas. Poderá referir-se, neste contexto e a título de demonstração da magnitude das grandezas envolvidas nos problemas {\it hard} em reticulados, um {\it challenge} actualmente vigente na página da Universidade Técnica de Darmstadt, no qual os participantes são desafiados a encontrar um vector curto em reticulados de dimensões $500 \leq d \leq 2000$. Até à data, o melhor resultado corresponde à dimensão $d =$ 825 \cite{CHALLENGE}.

\subsection{Vectores Curtos}

Nesta subsecção, serão introduzidos os problemas relacionados com vectores curtos, nomeadamente o Shortest Vector Problem, o Shortest Independent Vector Problem e as respectivas variantes aproximativas. As noções aqui abordadas servirão de base à derivação de problemas adicionais (Subsecção \ref{ADIC}) e ao suporte da prova de segurança do Criptosistema de Ajtai-Dwork (Subsecção \ref{AJTAIDWORK}).

\subsubsection{Shortest Vector Problem}
\label{SHORTVPROB}

Com base na definição de mínimo postulada em \ref{MINKOWSKI} — que pode ser generalizada como a distância mínima entre dois pontos de um reticulado —, torna-se possível definir a primeira problemática no âmbito dos problemas {\it hard}: a de encontrar um vector não nulo que atinja este valor — Shortest Vector Problem (SVP) (Figura ~\ref{fig:SVP}) \cite{SVP1,POL1}. Releve-se que o vector mais curto de um reticulado não é único, dado que, para além da possibilidade de existirem outros vectores de norma semelhante, há que considerar que $\|\mathcal{B}{\bf x}\| = \|-\mathcal{B}{\bf x}\|$ \cite{BASE1}. O número de vectores curtos compreendido num reticulado $\mathcal{L}$ denomina-se de {\it kissing number} e é superiormente delimitado \cite{NGUYEN1}.

\begin{mydef} Dado um reticulado $\mathcal{L}(\mathcal{B})$, encontrar um vector não nulo $\mathcal{B}${\bf x}, {\bf x} $\in \mathbb{Z}^k$, de comprimento (no máximo) $\|\mathcal{B}{\bf x}\| \leq \lambda_1 $.
\end{mydef}

No que concerne a complexidade, o SVP foi inicialmente comprovado como sendo NP-{\it hard} na norma $l_\infty$ por van Emde Boas, sendo posteriormente definido como NP-{\it hard} na norma $l_p$, para $p < \infty$ por Ajtai \cite{AJHARD}, mais precisamente na norma $l_2$, na qual o SVP é normalmente definido na grande maioria das aplicações.

\begin{figure}[htb!]
\includegraphics[width=.6\textwidth]{SVP.pdf}
\centering
\caption{Representação gráfica do Shortest Vector Problem (SVP).}
\label{fig:SVP}
\end{figure}

\subsubsection{Approximate Shortest Vector Problem}
\label{ASHORTV}

Por vezes, as aplicações não requerem um vector que seja efectivamente 'o mais curto', sendo suficiente encontrar um vector que seja 'suficientemente curto' — Approximate Shor\-test Vector Problem (SVP$\gamma$) (Figura ~\ref{fig:ASVP}) \cite{SVP1,POL1}.

\begin{mydef} Dado um reticulado $\mathcal{L}(\mathcal{B})$ e um factor de aproximação $\gamma \geq 1$, encontrar um vector não nulo $\mathcal{B}${\bf x}, {\bf x} $\in \mathbb{Z}^k$, de comprimento (no máximo) $\|\mathcal{B}{\bf x}\| \leq \gamma\lambda_1 $.
\end{mydef}

\begin{figure}[htb!]
\includegraphics[width=.6\textwidth]{ASVP.pdf}
\centering
\caption{Representação gráfica do Approximate Shortest Vector Problem (SVP$\gamma$).}
\label{fig:ASVP}
\end{figure}

\subsubsection{Shortest Independent Vector Problem}
\label{ISHORTV}

No caso particular em que se torna necessário encontrar não um, mas um conjunto de {\it n} vectores linearmente independentes — isto é, uma base de $\mathcal{L}$ — o problema denomina-se de Shortest Independent Vector Problem (SIVP) (Figura ~\ref{fig:SIVP}) \cite{SVP1,SEBCRIPT}.

\begin{mydef} Dado um reticulado $\mathcal{L}(\mathcal{B})$, encontrar um conjunto de {\it n} vectores linearmente independentes $\mathcal{B}{\bf x}_{1},...\mathcal{B}{\bf x}_{n}$ de comprimento (no máximo) $max_i \|\mathcal{B}{\bf x}_i\| \leq \lambda_n$.
\end{mydef}

\begin{figure}[htb!]
\includegraphics[width=.6\textwidth]{SIVP.pdf}
\centering
\caption{Representação gráfica do Shortest Independent Vector Problem (SIVP).}
\label{fig:SIVP}
\end{figure}

\subsubsection{Approximate Shortest Independent Vector Problem}
\label{AISHORTV}

De forma análoga à variante do SVP exposta em \ref{ASHORTV}, também o Shortest Independent Vector Problem (SIVP$\gamma$) está associado a um problema que visa encontrar, não o conjunto de vectores mais curtos, mas um conjunto de vectores 'suficientemente curtos' (Figura ~\ref{fig:ASIVP}) \cite{SVP1,SEBCRIPT}.

\begin{mydef} Dado um reticulado $\mathcal{L}(\mathcal{B})$, encontrar um conjunto de {\it n} vectores linearmente independentes $\mathcal{B}{\bf x}_{1},...\mathcal{B}{\bf x}_{n}$ de comprimento (no máximo) $max_i \|\mathcal{B}{\bf x}_i\| \leq \gamma \lambda_n$.
\end{mydef}

\begin{figure}[htb!]
\includegraphics[width=.6\textwidth]{ASIVP.pdf}
\centering
\caption{Representação gráfica do Approximate Shortest Independent Vector Problem (SIVP$\gamma$).}
\label{fig:ASIVP}
\end{figure}

\subsection{Vectores Próximos}
\label{CLOSEVPROB}

Apresentam-se, nesta subsecção, os problemas clássicos relacionados com vectores próximos, nomeadamente o Closest Vector Problem e o Aproximate Closest Vector Problem, o primeiro dos quais será recuperado em \ref{GGH}, a propósito do Criptosistema de Goldreich-Goldwasser-Halevi.

\subsubsection{Closest Vector Problem}
\label{CLOSEV}

Um outro problema {\it hard} que surge no âmbito dos reticulados diz respeito à noção de vector mais próximo: dado um determinado ponto-alvo ${\bf t} \in \mathbb{R}^d$ — não necessariamente pertencente ao reticulado $\mathcal{L}(\mathcal{B})$ —, o vector $\mathcal{B}{\bf x}$ mais próximo corresponde ao ponto de $\mathcal{L}(\mathcal{B})$ que minimiza a distância entre os dois (Figura ~\ref{fig:CVP}) \cite{POL1,SVP1,SEBCRIPT}.

\begin{mydef} Dados um reticulado $\mathcal{L}(\mathcal{B})$ e um ponto-alvo {\bf t}, encontrar um ponto {\bf x} do reticulado que minimize a distância $d({\bf t}-{\bf x})$ = $\|{\bf t}-{\bf x}\|$, isto é, o vector $\mathcal{B}${\bf x} à distância $\|\mathcal{B}{\bf x}-{\bf t}\| \leq \mu$ de {\bf t}.
\end{mydef}

\begin{figure}[htb!]
\includegraphics[width=.6\textwidth]{CVP.pdf}
\centering
\caption{Representação gráfica do Closest Vector Problem (CVP).}
\label{fig:CVP}
\end{figure}

De forma semelhante ao SVP, van Emde Boas provou que resolver o problema CVP — denominado, no seu artigo, de 'Nearest Vector Problem' — de forma exacta é também NP-{\it hard}.

\subsubsection{Approximate Closest Vector Problem}
\label{ACLOSEV}

Uma relaxação possível para o problema anterior consiste, igualmente, em considerar um factor de aproximação $\gamma$ que permita obter, não o vector mais próximo, mas um vector 'suficientemente próximo' (Figura ~\ref{fig:ACVP}) \cite{POL1,SVP1,SEBCRIPT}.

\begin{mydef} Dados um reticulado $\mathcal{L}(\mathcal{B})$ e um ponto-alvo {\bf t}, encontrar um ponto {\bf x} do reticulado que minimize a distância $d({\bf t}-{\bf x})$ = $\|{\bf t}-{\bf x}\|$, isto é, o vector $\mathcal{B}${\bf x} à distância $\|\mathcal{B}{\bf x}-{\bf t}\| \leq \gamma\mu$ de {\bf t}.
\end{mydef}

\begin{figure}[htb!]
\includegraphics[width=.6\textwidth]{ACVP.pdf}
\centering
\caption{Representação gráfica do Approximate Closest Vector Problem (CVP$\gamma$).}
\label{fig:ACVP}
\end{figure}

\subsection{Problemas Adicionais}
\label{ADIC}

No contexto das reduções {\it worst-case} a {\it average-case}, Ajtai introduziu três problemas de reticulados inerentes à resolução do SVP numa dada classe de reticulados aleatórios — os chamados reticulados modulares ou {\it q-ary}, que satisfazem $q \mathbb{Z}^n \subseteq \mathcal{L} \subseteq \mathbb{Z}^n$ para um dado inteiro $q$. $\mathcal{L}$ é apenas dito modular nos casos específicos em que $q$ é um múltiplo do volume do reticulado, e assume a seguinte propriedade: se {\bf x} $\equiv$ {\bf y} mod $q$, então ${\bf x} \in \mathcal{L}$ sse ${\bf y} \in \mathcal{L}$ \cite{AJTAI}.

Recentemente, surgiu um conjunto de problemas que têm por base aqueles definidos no trabalho de Ajtai — enumerados de seguida —, nomeadamente o Small Integer Solutions, o já explicitado Shortest Independent Vector Problem e o Learning With Errors (que será propositadamente ignorado, no decorrer deste trabalho, por existir um outro trabalho exclusivamente dedicado aos problemas de aprendizagem).

\subsubsection{Hermite Shortest Vector Problem}
\label{HERMITESVP}

Pese embora não faça parte do conjunto de problemas definidos em \cite{AJTAI}, o Hermite Shortest Vector Problem destaca-se por constituir uma alternativa ao SVP e é mencionado como ponto motivador da questão colocada no Shortest Length Problem, desenvolvido de seguida. Na sequência do SVP, não existe qualquer certeza (ou forma de comprovar) se um dado vector é efectivamente o vector mais curto pertencente ao reticulado, pelo que o HSVP surge no sentido de colmatar esta lacuna aparente, ao propor-se encontrar não o vector mais curto relativamente ao vector não nulo mais curto, mas relativamente ao volume deste.

\begin{mydef} Dada uma base $\mathcal{B}$ de um reticulado $\mathcal{L}$ de {\it rank} $d$ que verifique $\mathcal{L} \subseteq \mathbb{Z}^n$ e um factor de aproximação $\gamma > 0$, o Hermite Shortest Vector Problem consiste em encontrar um vector {\bf v} não nulo do reticulado tal que a norma de {\bf v} satisfaça $\|{\bf v}\| \leq \gamma(vol(\mathcal{L}))^{1/d}$.
\end{mydef}

\subsubsection{Shortest Length Problem}
\label{SLP}

Da mesma forma que verificar se um vector não nulo é efectivamente o vector mais curto não constitui um processo trivial, o de determinar o primeiro mínimo sucessivo $\lambda_1(\mathcal{L})$ revela-se igualmente complicado. Nestes termos, é possível definir o Shortest Length Problem:

\begin{mydef} Dada uma base $\mathcal{B}$ de um reticulado $\mathcal{L}$ de {\it rank} $d$ que verifique $\mathcal{L} \subseteq \mathbb{Z}^n$ e um factor de aproximação $\gamma > 0$, encontrar um valor $\lambda(\mathcal{L})$ tal que $\lambda_1(\mathcal{L}) \leq \lambda(\mathcal{L}) \leq \gamma \lambda_1(\mathcal{L})$.
\end{mydef}

\subsubsection{Unique Shortest Vector Problem}
\label{USVP}

Este problema constitui um caso especial do SVP, ao impor determinadas restrições ao reticulado $\mathcal{L}$.

\begin{mydef} Dada uma base $\mathcal{B}$ de um reticulado {\it fullrank} $\mathcal{L} \subset \mathbb{Z}^n$ e um {\it gap factor} $\gamma$, encontrar o vector {\bf v} $\in \mathcal{L}$ não nulo mais curto, em que {\bf v} é único — no sentido de que qualquer outro vector {\bf x} $\in \mathcal{L}$ com $\|{\bf x}\| \leq \gamma \|{\bf v}\|$ é um múltiplo inteiro de {\bf v}.
\end{mydef}

Assim, o Unique Shortest Vector Problem representa uma versão do SVP restrita aos reticulados em que o {\it gap} $\lambda_2(\mathcal{L}) / \lambda_1(\mathcal{L}) > \gamma$, representando $\lambda_i(\mathcal{L})$ os mínimos sucessivos de $\mathcal{L}$. Este problema em particular será citado no âmbito deste trabalho, em \ref{PUBLICKES}, a propósito dos Esquemas de Criptografia de Chave Pública.

\subsubsection{Shortest Basis Problem}
\label{SBP}

O Shortest Basis Problem assemelha-se, em parte, a um problema de redução de bases. Considerando $\mathcal{B}(\mathcal{L})$ o conjunto de todas as bases do reticulado $\mathcal{L}$:

\begin{mydef} Dado um reticulado $\mathcal{L} \subset \mathbb{Z}^n$ e o factor de aproximação $\lambda > 0$, encontrar uma base $\mathcal{B} = [{\bf b}_1,...{\bf b}_d]$ tal que $\max_{1 \leq i \leq d} \|{\bf b}_i\| \leq \gamma \max_{1 \leq i \leq d} \|{\bf b}_i{'}\|$ para todas as bases $\mathcal{B}{'} = [{\bf b_1{'}},...,{\bf b_d{'}}]$.
\end{mydef}

\subsection{Redução entre Problemas Hard}
\label{REDPH}

A dificuldade dos diversos problemas {\it hard} pode, por vezes, ser comparada através de reduções entre estes, partindo do princípio de que um dado Problema A pode ser reduzido ao Problema B se um qualquer método que permita resolver o Problema B possa ser utilizado para resolver as instâncias do Problema A \cite{BASE1}. Intuitivamente, infere-se, nestes moldes, que o Problema B é pelo menos tão {\it hard} quanto o Problema A. No entanto, embora uma solução para o Problema B veicule de imediato uma solução para o Problema A, esta relação não é invertível \cite{INTER}.

A Figura~\ref{fig:INTER} representa as relações existentes entre os problemas {\it hard} em reticulados actualmente definidos e assume, por questões de simplificação, que cada problema se encontra num reticulado {\it full-rank} em $\mathbb{Z}^n$ ($\mathbb{Z}^m$ no caso específico dos problemas SIS e LWE). Uma seta entre dois problemas indica que o problema na ponta de origem pode ser reduzido ao problema na ponta de destino (em tempo polinomial). Os pormenores técnicos das reduções esquematizadas, como seja a justificação dos factores de aproximação, não são detalhados por não se considerar relevante para o contexto deste trabalho, podendo ser consultados na íntegra em \cite{INTER}. 

\begin{figure}[htb!]
\includegraphics[width=.8\textwidth]{INTER.pdf}
\centering
\caption{Esquema ilustrativo das relações entre os problemas {\it hard} em reticulados.}
\label{fig:INTER}
\end{figure}

\newpage
\thispagestyle{plain}
\section{Resolução de Problemas Hard em Reticulados}
\label{RESSVP}

Apresentar-se-ão, nesta secção, apenas métodos de resolução desenvolvidos e actualmente utilizados no âmbito dos vectores curtos, nomeadamente do SVP. Pese embora se depreendesse, à partida, que não existiam algoritmos capazes de levar a cabo a tarefa de encontrar um vector curto em tempo polinomial — dado que este problema apresenta uma complexidade NP-{\it hard} —, inferiu-se que, para dimensões $d$ consideradas razoáveis, este processo é computacionalmente viável, nomeadamente através de técnicas como a Enumeração e os algoritmos de {\it sieving}.

\subsection{Enumeração}
\label{ENUM}

A resolução do SVP por intermédio da técnica de enumeração baseia-se no teste de todas as combinações possíveis de vectores de uma base, destacando, entre todas as possibilidades, o vector mais curto. Naturalmente, testar todas as combinações possíveis implicaria uma quantidade infinita de vectores, pelo que se torna necessário equacionar e explorar um método associado à enumeração que veicule um limite a esta quantidade — a ortagonalização de Gram Schmidt \cite{SVP1,POL1}.

\subsubsection{Ortogonalização de Gram Schmidt}

A existência de uma base ortonormal facilita a procura dos coeficientes necessários à descrição de um vector enquanto combinação linear dos vectores ${\bf v_1},...,{\bf v_n}$, pertencentes à base de um espaço vectorial.

\begin{equation}
v = \frac{(v, v_1)}{\|v_1\|^2} {\bf v_1} + ... + \frac{(v, v_n)}{\|v_n\|^2} {\bf v_n}
\end{equation}

Neste sentido, o processo de Gram Schmidt surge como um método de ortonormalização de bases, através do escalonamento de um vector da base de forma a que este tenha comprimento igual a um. Os vectores seguintes são iterativamente  projectados no complemento ortogonal do {\it span} de vectores anteriores e igualmente escalonados. Quando os vectores não são escalonados no decorrer deste procedimento, a base resultante será ortogonal em vez de ortonormal, isto é, embora o produto interno entre todos os vectores da base seja $u . v = 0$, estes não são vectores unitários.

No que concerne a aplicação deste método no âmbito dos reticulados, não existe qualquer garantia de que a projecção de um vector do reticulado no complemento ortogonal de um outro vector do reticulado se encontre necessariamente no reticulado, nem tão pouco é sempre possível escalonar um vector nas condições anteriormente referidas, pelo que nem sempre é possível ortogonalizar as bases. Não obstante, o processo de Gram Schmidt desempenha um papel fundamental nos métodos de redução e enumeração aplicados a bases de reticulados.

\begin{theorem}
\caption{Ortogonalização de Gram Schimdt}
\label{th:GS}

\begin{tabbing}
\\
Dada uma base $B = {b_1,...,b_d}$ de um reticulado $\mathcal{L}$, calcular, para cada $i = 1,...,d$:
\\
\\
\hspace{0.4cm}	1. Para cada $j < i$, calcular $\mu_{i,j} = s_j^{-1} (b_i \cdot b_i^*$, sendo $s_j = b_j^* \cdot b_j^*$;
\\
\hspace{0.4cm}	2. $b_j^* = b_1 - \sum_{j<i} \mu_{i,j} b_j^*$, onde $\mu_{i,j} = \frac{\langle b_i,{b_j^*\rangle}}{\|b_j^*\|^2}$, para todo $1 \leq j < i \leq d$.
\end{tabbing}
\end{theorem}

Uma forma simplificada de representar o algoritmo de enumeração é por intermédio de uma árvore de pesquisa (Figura ~\ref{fig:ENUMTREE}), cujos nós correspondem a um qualquer vector. Considerando que a raiz se encontra no nível 0, o nível $i$ da árvore é composto por todos os vectores de $\pi_{d-i+1}$, para $0 \leq i \leq d$. Sendo $v$ um nó do nível $i$, isto é, $v \in \pi_{d-i+1}$, a respectiva descendência consiste no conjunto de todos os vectores $u \in \pi_{d-i+2} (\mathcal{L})$ projectados em $v$: $v = \pi_{d-i+1}(u)$. No seguimento deste raciocínio, infere-se que a raiz consiste do vector $\pi_{d+1}$, o primeiro nível no conjunto de vectores pertencentes a $\pi_{d}(\mathcal{L}) = \mathcal{L}(b_d^*)$ de norma, no máximo, $R$, e assim sucessivamente, até ao nível $d$, que contém todos os vectores de $\pi_1(\mathcal{L})$ de norma, no máximo, $R$.

\begin{figure}[htb!]
\includegraphics[width=.9\textwidth]{ENUMTREE.pdf}
\centering
\caption{Esquematização dos dois primeiros níveis de uma árvore de enumeração.}
\label{fig:ENUMTREE}
\end{figure}

Uma outra forma de descrever a enumeração de forma simplificada é através de um algortimo (Algoritmo ~\ref{al:ENUM}), recorrendo à noção de árvore supracitada.

Dependendo do grau de precisão do delimitador $R$, as árvores de enumeração tendem a desenvolver-se exponencialmente, pelo que, pese embora correspondam a um método capaz de retornar uma solução exacta do SVP, o tempo de execução não é polinomial e, por essa mesma razão, estes algoritmos são normalmente precedidos de algoritmos de redução. Em alternativa, Schnorr e H\"orner propuseram uma técnica de enumeração melhorada, designada de {\it pruning} \cite{ENUMPRUN1}, recentemente elevada a outro patamar por Gama, Nguyen e Regev, num conceito denominado de {\it extreme pruning} \cite{ENUMPRUN2}.

\begin{algorithm}
\caption{Enumeração}
\label{al:ENUM}

\begin{tabbing}
\\
{\bf Requer:} uma base reduzida $\{b_1,...,b_d\}$  de $\mathcal{L}$ e os respectivos coeficientes de Gram-Schmidt\\$\mu_{i,j}$ e normas $\|b_i^*\|$
\\
\\
{\bf Garante:} o vector de {\it output} do reticulado $\sum_i u_i b_i \in \mathcal{L}$ é um vector curto de $\mathcal{L}$
\\
\hspace{0.4cm}1: {\bf repetir}
\\
\hspace{0.4cm}2: \hspace{0.4cm} {\bf se} a norma do nó actual for menor do que o limite, {\bf então}
\\
\hspace{0.4cm}3: \hspace{0.8cm} descer um nível, até ao descendente de norma mínima
\\
\hspace{0.4cm}4: \hspace{0.4cm} {\bf else}
\\
\hspace{0.4cm}5: \hspace{0.4cm} subir um nível, até ao vizinho não visitado do ascendente de menor norma
\\
\hspace{0.4cm}6: \hspace{0.4cm} {\bf end if}
\\
\hspace{0.4cm}7: {\bf até} que todos os nós tenham sido percorridos
\end{tabbing}
\end{algorithm}


\subsection{Sieving}
\label{SIEVE}

Em contraposição — ou como alternativa — à superexponencialidade da enumeração surgem os algoritmos de {\it sieving}, que revelam tempos de execução exponenciais. Porém, mesmo a variante prática mais rápida deste algoritmo conhecida é ultrapassada, em termos de {\it performance}, pelo algoritmo de enumeração de Schnorr-H\"orner, até $n \approx 50$ (dimensão acima da qual este se torna impraticável) \cite{BASE1,SIEVE}. Abaixo, apresenta-se um possível algoritmo de {\it sieving} — o algoritmo de Micciancio-Voulgaris (Algoritmo ~\ref{al:SIEVE}).

Sumariamente, o algoritmo procura exaurir o espaço de vectores curtos do reticulado, adicionando sucessivamente vectores curtos a uma lista $Q$ até que os vectores ${\bf v_i}$ e ${\bf v_j}$ em $Q$ estejam afastados, no máximo, à distância $\mu$ ou se tenham usado demasiadas amostras. Caso se encontrem dois vectores ${\bf v_1},{\bf v_j} \in \mathcal{L}$ nas condições referidas, então, o vector ${\bf v} = {\bf v_i} - {\bf v_j}$ também pertence ao reticulado e tem um comprimento, no máximo, de $\mu$, e a solução retornada pelo algoritmo é ${\bf v}$. Em caso contrário, novos vectores são adicionados à lista — cujo tamanho é limitado por uma constante fixa. No cômputo geral, é possível garantir, com elevada probabilidade, que, a dada altura, se abandona o ciclo representado no Algoritmo ~\ref{al:SIEVE}, ao encontrar um vector curto do reticulado \cite{BASE1}.

Actualmente, para além de os próprios Micciancio e Voulgaris terem proposto uma melhoria ao seu algoritmo de {\it sieving} — o denominado Algoritmo de GaussSieve —, Ajtai et al. \cite{AJTSIEVE} propuseram uma abordagem distinta, que vai ao encontro do conceito de {\it sieving} de forma mais explícita: em vez de exaurir o espaço de vectores curtos numa lista de vectores de dimensão substancialmente elevada, começa-se por uma lista de vectores longos, que vai sendo reduzida em tamanho, paralelamente à redução das normas dos vectores nela contidos, através de sucessivas iterações. Na mesma linha de construção, inserem-se as propostas de Nguyen e Vidick \cite{NGSIEVE}, e Wang et al. \cite{WANSIEVE}, a título de exemplo, que não serão exploradas no presente trabalho.

\begin{algorithm}
\caption{Algoritmo de {\it sieving} de Micciancio-Voulgaris}
\label{al:SIEVE}

\begin{tabbing}
\\
{\bf Requer:} uma base reduzida $\{b_1,...,b_d\}$  de $\mathcal{L}$ e um valor $\mu \in \mathbb{R}$
\\
\\
{\bf Garante:} se $\mu > \lambda_1(\mathcal{L})$, então, com grande probabilidade, o algoritmo encontra um vector \\ ${\bf v}$ $\in \mathcal{L}$ com $\|${\bf v}$\| \leq \mu$
\\
\hspace{0.4cm}1: $Q \leftarrow \{0\}$ 
\\
\hspace{0.4cm}2: $\xi  \leftarrow 0.685$
\\
\hspace{0.4cm}3: $N \leftarrow poly(d) \cdot 2^{3.199d}$
\\
\hspace{0.4cm}4: {\bf for} $i = 1$ to $N$ {\bf do}
\\
\hspace{0.4cm}5: \hspace{0.4cm} ${\bf e_i} \in_R {\bf B_d} ({\bf 0,\xi,\mu})$
\\
\hspace{0.4cm}6: \hspace{0.4cm} ${\bf r_i} \leftarrow {\bf e_i}$ mod ${\bf B}$
\\
\hspace{0.4cm}7: \hspace{0.4cm} {\bf while} $\exists {\bf v_j} \in Q : \|{\bf r_i}-{\bf v_j}\| \leq (1 - \frac{1}{d} \|{\bf v_i}\|$ {\bf do} 
\\
\hspace{0.4cm}8: \hspace{0.4cm} \hspace{0.4cm} ${\bf r_i} \leftarrow {\bf r_i} - {\bf v_j}$
\\
\hspace{0.4cm}9: \hspace{0.4cm} {\bf end while}
\\
\hspace{0.4cm}10: \hspace{0.4cm} ${\bf v_i} \leftarrow {\bf r_i} - {\bf e_i}$
\\
\hspace{0.4cm}11: \hspace{0.4cm} {\bf se} ${\bf v_i} \not \in Q$ {\bf then}
\\
\hspace{0.4cm}12: \hspace{0.4cm} \hspace{0.4cm} {\bf se} $\exists {\bf v_j} \in  Q : \|{\bf v_i} - {\bf v_j}\| < {\bf \mu}$ {\bf then}
\\
\hspace{0.4cm}13: \hspace{0.4cm} \hspace{0.4cm} \hspace{0.4cm} {\bf return} ${\bf v_i} - {\bf v_j}$
\\
\hspace{0.4cm}14: \hspace{0.4cm} \hspace{0.4cm} {\bf end if}
\\
\hspace{0.4cm}15: \hspace{0.4cm} \hspace{0.4cm} {\bf Q} $\leftarrow {\bf Q} \cup \{{\bf v_i}\}$
\\
\hspace{0.4cm}16: \hspace{0.4cm} {\bf end if}
\\
\hspace{0.4cm}17: {\bf end for}
\\
\hspace{0.4cm}18: {\bf return} $\bot$
\end{tabbing}
\end{algorithm}

\newpage
\thispagestyle{plain}
\section{Técnicas Criptográficas}
\label{CRYPTECH}

Conforme vem sido explorado ao longo do presente trabalho, as construções criptográficas baseadas em reticulados representam uma promessa no âmbito da criptografia pós-quântica, na medida em que são comprovadamente eficientes, de implementação simples e seguras contra computadores quânticos. Nesta secção, serão apresentados essencialmente dois tipos de construção: esquemas de criptografia de chave pública e esquemas de assinatura digital.

\subsection{Esquemas de Criptografia de Chave Pública}
\label{PUBLICKES}

A descoberta da conexão entre o {\it worst-case} e o {\it average-case} dos problemas {\it hard} de reticulados potenciou a sua utilização no âmbito da criptografia de chave pública. Serão descritos, nesta secção, os três primeiros criptosistemas baseados em reticulados, nomeadamante os Criptosistemas de Ajtai-Dwork, Goldreich-Goldwasser-Halevi (GGH) e NTRU.

\subsubsection{Criptosistema de Ajtai-Dwork}
\label{AJTAIDWORK}

O criptosistema de Ajtai-Dwork foi o primeiro, no seio da criptografia de chave pública, a admitir uma prova de segurança baseada em assumpções de dificuldade {\it worst-case} em problemas de reticulados. Assim, embora o sistema não tenha sido apresentado recorrendo explicitamente à utilização de reticulados, a referida prova de segurança evidencia que cada instância do uSVP pode ser transformada, com elevada probabilidade, numa instância aleatória do criptosistema.

\vspace{-0.2cm}
\begin{table}[htb!]
\centering
\caption{Parâmetros do Criptosistema de Ajtai-Dwork.}
\vspace{0.2cm}
\begin{tabular}{| c | c | c |}
\hline
Parâmetro & Descrição & Conhecimento\\[0.5ex]
\hline
$n$ & Dimensão & Público\\[0.5ex]

$m = n^3$ & Inteiro & Público\\

$r_n = n^n$ & Inteiro & Público\\

${\bf u}$ & Vector $n$-dimensional & Privado\\

${\bf w}_1,...,{\bf w}_n, {\bf v}_1,...,{\bf v}_m$ & $n + m$ vectores $n$-dimensionais & Público\\
\hline
\end{tabular}
\label{tab:AD1}
\end{table}

Relativamente aos parâmetros inerentes ao sistema, o parâmetro de segurança $n$ determina a dimensão a dimensão do espaço vectorial em que o criptosistema está inserido. Sendo $m = n^3$, $r_n = n^n$ e $c > 0$, considerem-se um cubo $\mathcal{B}_n$ de lados de comprimento $r_n$ e uma esfera $\mathcal{S}_n$ de raio $n^{-c}$, ambos $n$-dimensionais:

\begin{center}
$\mathcal{B}_n = \{x \in \mathbb{R}^n : |x_i| \leq r_n/2, \forall i\}$
\vspace{0.3cm}

$\mathcal{S}_n = \{x \in \mathbb{R}^n : \|x\| \leq n^{-c} \}$
\end{center}

Neste contexto, a chave privada corresponde a um vector {\bf u} escolhido de forma aleatória a partir de $\mathcal{S}_n$, com base na qual uma distribuição $\mathcal{H}_u$ é definida em $\mathcal{B}_n$. Esta construção é definida em três passos: extrair {\bf x} de \{{\bf x} $\in \mathcal{B} : \langle {\bf x},{\bf u}\rangle \in \mathbb{Z}$\} de forma uniforme e aleatória; desenhar $n$ vectores de erro $y_1,...,y_n$ a partir de $\mathcal{S}_n$, independente e uniformemente, também de forma aleatória; e gerar {\bf v} = {\bf x} + $\sum ^{n}_{i=1} {\bf y_i}$. Por outro lado, a chave pública é obtida retirando $n+m$ vectores ${\bf w_1},...,{\bf w_n}$, ${\bf v_1},...,{\bf v_m}$ de $\mathcal{H}_u$ aleatoriamente.

O processo de cifragem é levado a cabo {\it bit} a {\it bit}, sendo que, para cifrar um {\it bit} 0, devem retirar-se {\bf $b_1,...,b_m$}, uniforme e aleatoriamente, de \{0,1\} e reduzir o vector $\sum _i b_i {\bf v}_i$ módulo o paralelepípedo $\mathcal{P}({\bf w}_1,...,{\bf w}_n)$ — que corresponde ao paralelepípedo abrangido pelos ${\bf w}_i$. O resultado será um vector {\it n}-dimensional, que corporiza o texto cifrado {\bf c}. A cifragem de um {\it bit} 1, por outro lado, implica que se escolha aleatoriamente um vector {\it n}-dimensional do paralelepípedo referido, que constituirá o texto cifrado {\bf c}. O processo inverso, o de decifragem, compreende o cálculo do produto interno do vector {\it n}-dimensional correspondente ao {\it bit} em análise, recorrendo à chave privada {\bf u}. Caso dist($\langle {\bf c},{\bf u} \rangle$,$\mathbb{Z} \leq n^{-1}$), {\bf c} é decifrado como 0; em caso contrário, {\bf c} é decifrado como 1 \cite{AJTAIDWORK}.

Dado que, à data deste trabalho, não se reúnem o conhecimento nem os meios necessários à construção de exemplos de funcionamento destes sistemas, para efeitos de exemplificação, recorrer-se-á aos exemplos construídos por Joop van De Pol em \cite{POL1} para todos os criptosistemas apresentados.

\begin{exmp}
Para uma dimensão $n = 3$, os parâmetros do sistema fixam-se em $m = 27$ e $r_3 = 27$ (Tabela \ref{tab:AD1}). Numa primeira fase, gerou-se a chave privada de forma aleatória a partir da esfera $\mathcal{S}_n$:

\begin{center}
{\bf u} = (-0.524655,0.606024,0.36764)
\end{center}

A chave pública (${\bf w}_1$,${\bf w}_2$,${\bf w}_3$,${\bf v}_1$,...,${\bf v}_{27}$), por sua vez, é derivada retirando aleatoriamente vectores do cubo $\mathcal{B}_n$ compreendido nos hiperplanos definidos por {\bf u} e adicionando três vectores da esfera tri-dimensional de raio $n^{-c} = 3^{-8} = 1/6561$. Por motivos de simplificação de exposição, a tabela correspondente à chave pública não é aqui incluída. A sua estrutura compreende um tripleto para cada ${\bf w_i}$ e ${\bf v_i}$. Considerando uma mensagem {\bf m} = (1,0,1,1,1,1,1,0,1), cifrada {\it bit} a {\it bit}, o texto cifrado resultante é:

\begin{center}
{\bf c} = ((9.986,3.746,-2.791),(1.365,1.417,-3.108),(-16.955,-1.992,9.227),
\end{center}
\vspace{-0.5cm}
{\addtolength{\leftskip}{30 mm}
(-5.223,-1.139,1.278),(5.590,-3.151,-6.728),(-7.319,9.134,17.364),\\*
}
{\addtolength{\leftskip}{30 mm}
(-3.014,3.752,2.509),(-9.874,4.964,7.645),(-9.039,4.727,5.035)).\\*

}

Em {\bf c}, cada tripleto corresponde à cifragem de um {\it bit}. Para proceder à decifragem, o produto interno de cada tripleto com {\bf u} é calculado e, de seguida, determina-se se este se encontra suficientemente perto de $\mathbb{Z}$, isto é, se a distância ao inteiro mais próximo é menor do que $n^{-1} = 1/3$. Neste caso específico, os produtos internos obtidos foram:

\vspace{-0.2cm}
\begin{table}[htb!]
\centering
\caption{Produtos internos do texto cifrado {\bf c} com {\bf u} \cite{POL1}.}
\vspace{0.2cm}
\begin{tabular}{| c | c |}
\hline
${\bf c}_i$ & $\langle {\bf c}_i,{\bf u} \rangle$\\[0.5ex]
\hline
${\bf c}_1$ & 3.994\\[0.5ex]

${\bf c}_2$ & 1.000\\

${\bf c}_3$ & -11.08\\

${\bf c}_4$ & 2.519\\

${\bf c}_5$ & 7.316\\

${\bf c}_6$ & -15.76\\

${\bf c}_7$ & -4.777\\

${\bf c}_8$ & -10.99\\

${\bf c}_9$ & -9.458\\
\hline
\end{tabular}
\label{tab:PK}
\end{table}

Todos os valores que se encontrem no intervalo ($z-1/3$,$z+1/3$) para um dado inteiro $z$ são decifrados como 0's, sendo os restantes decifrados como 1's, resultando na mensagem {\bf m'} = (0,0,0,1,0,0,0,0,1), que não corresponde à mensagem original, conforme se esperava. Apenas os 0's são decifrados de forma correcta, sendo que se verificaram 5 erros de decifragem, pelo que se conclui que, para $n = 3$, a taxa de fallha neste processo é de, aproximadamente, 2/3.
\end{exmp}

O criptosistema de Ajtai-Dwork constitui, das três instâncias abordadas no decorrer deste trabalho, o único acompanhado de uma prova de segurança, inspirada na descoberta seminal de Ajtai de que existe efectivamente uma conexão entre a complexidade {\it worst-case} e {\it average-case} do SVP, através da qual este provou que este problema é {\tt NP-Hard}, quando sujeite a reduções aleatórias \cite{AJTAI}. Infelizmente, este criptosistema não demonstra ser muito eficiente, sobretudo devido à expansão da mensagem e ao elevado espaço requerido para o armazenamento da chave pública.

\subsubsection{Criptosistema de Goldreich-Goldwasser-Halevi (GGH)}
\label{GGH}

Pese embora represente um interesse inegável, sobretudo a nível teórico, o criptosistema anteriormente exposto revela, em parte, ser pouco eficiente, devido à expansão da mensagem e ao elevado espaço requerido para armazenar a chave pública, para além de apresentar fragilidades ao nível da segurança. Comparativamente com este sistema, o Criptosistema GGH surge associado a uma eficiência bastante superior, não obstante não ser acompanhado de uma prova de segurança.

A base que suporta o Criptosistema GGH é essencialmente composta por dois parâmetros: a dimensão $n$ do reticulado e um parâmetro de segurança $\sigma$, sendo este último responsável por determinar a dificuldade do CVP derivado do processo de cifragem. A chave privada, neste caso, consiste numa matriz secreta $\mathcal{R}$, cujas colunas formam uma base do reticulado $\mathcal{L}$. Por sua vez, a chave pública consiste numa matriz $\mathcal{B}$, que representa uma base para $\mathcal{L}$ distinta da anterior e é gerada aleatoriamente a partir da base secreta $\mathcal{R}$.

\vspace{-0.2cm}
\begin{table}[htb!]
\centering
\caption{Parâmetros do Criptosistema GGH.}
\vspace{0.2cm}
\begin{tabular}{| c | c | c |}
\hline
Parâmetro & Descrição & Conhecimento\\[0.5ex]
\hline
$n$ & Dimensão & Público\\[0.5ex]

$\sigma$ & Parâmetro de Segurança & Público\\

$\mathcal{R}$ & Matriz $n \times n$ & Privado\\

$\mathcal{B}$ & Matriz $n \times n$ & Privado\\
\hline
\end{tabular}
\label{tab:GGH}
\end{table}

A cifragem da mensagem é realizada através da codificação da mesma como um vector ${\bf m} \in \mathbb{Z}^n$, seguida da criação de um vector de erro $e$ — retirado aleatoriamente da conjunto $\{-\sigma$,$\sigma\}^n$ — e da computação do texto cifrado:

\begin{center}
${\bf c} = \mathcal{B}{\bf m} + e$
\end{center}

A mensagem ${\bf m}$ pode ser recuperada por intermédio do processo de decifragem do texto cifrado:

\begin{center}
${\bf m }= \mathcal{B}^{-1} \mathcal{R} \lfloor \mathcal{R}^{-1} {\bf c} \rceil$
\end{center}

Cada mensagem ${\bf m} \in \mathbb{Z}^n$ corresponde a um ponto do reticulado ${\bf m}_{\mathcal{L}} = \mathcal{B}{\bf m}$ e, paralelamente, cada ponto ${\bf m}_{\mathcal{L}}$ corresponde a uma dada mensagem ${\bf m} = \mathcal{B}^{-1} {\bf m}_{\mathcal{L}}$. No processo de cifragem, a mensagem ${\bf m}$ é transformada no ponto ${\bf m}_{\mathcal{L}}$ correspondente e o texto cifrado ${\bf c}$ é obtido a partir da adição de um vector de erro $e$. Posteriormente, $\sigma$ e $e$ são escolhidos de forma a que $m_{\mathcal{L}}$ seja o vector do reticulado mais próximo de ${\bf c}$. No sentido de obter ${\bf m}_{\mathcal{L}}$ e, consequentemente, ${\bf m}$, torna-se necessário resolver o CVP, nomeadamente através do Método de Babai — método de redução que não é discutido no âmbito deste trabalho —, partindo-se do princípio de que este será relativamente eficaz utilizando a base privada $\mathcal{R}$, mas não suficientemente eficaz utilizando a base pública $\mathcal{B}$. Conforme mencionado anteriormente, o parâmetro $\sigma$ determina a dificuldade do problema a resolver nesta fase, pelo que devem ser tidas em consideração as implicações que advêm de um aumento do mesmo: quanto maior o valor de $\sigma$, maior a distância entre o vector ${\bf m}_{\mathcal{L}}$ e o texto ${\bf c}$ — logo, maior a dificuldade — e maior a probabilidade de surgirem erros no processo de decifragem \cite{GGH}.

\begin{exmp}
Para uma dimensão $n = 4$ e um parâmetro de segurança $\sigma = 1$, a matriz privada $\mathcal{R}$ é gerada retirando aleatoriamente os seus {\it inputs} — números inteiros — do intervalo [-4,4]. Por sua vez, a matriz pública $\mathcal{B}$ corresponde à Forma Normal de Hermite de $\mathcal{R}$.

\begin{minipage}[b]{5cm}
\[
\mathcal{R}=
\begin{pmatrix*}[r]
3 & 1 & -1 & 3\\
3 & -4 & 3 & 1\\
3 & -3 & -4 & -3\\
-2 & -3 & -2 & 3
\end{pmatrix*}
\]
\end{minipage} 
\begin{minipage}[b]{15cm} 
\[
\mathcal{B}=
\begin{pmatrix*}[r]
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0\\
-349 & 311 & 321 & 851
\end{pmatrix*}
\]
\end{minipage}
\vspace{0.5cm} 

Posteriormente, a mensagem {\bf m} = (-2,0,-4,-1) é cifrada recorrendo ao vector de erro {\bf e} = (-1,1,1,-1), correspondendo o texto cifrado a ${\bf c} = \mathcal{B}{\bf m} + {\bf e} = (-3,1,-3,-1438)$. O processo de decifragem da mensagem {\bf m} é levado a cabo por intermédio do Método de Babai, utilizando a base privada $\mathcal{R}$:

\begin{center}
${\bf x} = \lfloor \mathcal{R}^{-1} {\bf c} \rceil = (143,152,112,-157)$

${\bf m}_{\mathcal{L}} = \mathcal{R}{\bf x} = (-2,0,-4,-1437)$

${\bf m} = \mathcal{B}^{-1}{\bf m}_{\mathcal{L}} = (-2.0,-4,-1)$
\end{center}

Assim, a mensagem decifrada é equivalente à mensagem original, pelo que se deduz que não ocorreram quaisquer erros de decifragem. Se, por outro lado, se utilizar a base $\mathcal{B}$, o resultado não é a mensagem original, conforme se esperaria.
\end{exmp}

\vspace{0.5cm}

Em suma, o criptosistema GGH revela um interesse considerável na medida em que é explicitamente baseado em em reticulados, embora a função de {\it trapdoor} utilizada no CVP introduza comprovadamente fragilidades estruturais que podem ser exploradas por intermédio de algoritmos de redução capazes de quebrar o sistema para dimensões reduzidas. Não obstante, apresenta maior eficiência do que o criptosistema de Ajtai-Dwork.

\subsubsection{Criptosistema NTRU}

De forma semelhante ao criptosistema GGH, o criptosistema NTRU é orientado à prática, descurando também a existência de uma prova de segurança que assegure que quebrar o sistema é pelo menos tão {\it hard} quanto resolver um dado problema de reticulados que lhe seja inerente. Não obstante este criptosistema ser baseado em anéis (nomeadamente o anel de convolução de polinómios), pode ser descrito de forma equivalente utilizando reticulados com uma estrutura especial.

Embora, conforme explicitado anteriormente, o sistema NTRU seja descrito como um criptosistema de anel polinomial, a relação entre as chaves pública e privada define um reticulado — denominado de reticulado NTRU — cuja base (uma das possíveis) pode ser derivada a partir da chave pública e cuja chave secreta corresponde a determinados vectores curtos pertencentes a esse mesmo reticulado.  O sistema tem por base quatro parâmetros fundamentais: o grau $n$ (que, por motivos de segurança, deve ser primo), os módulos $q$ e $p$ (que devem ser co-primos), e os limites inteiros $d_f$, $d_g$ e $d_r$.


\vspace{-0.2cm}
\begin{table}[htb!]
\centering
\caption{Parâmetros do Criptosistema NTRU.}
\vspace{0.2cm}
\begin{tabular}{| c | c | c |}
\hline
Parâmetro & Descrição & Conhecimento\\[0.5ex]
\hline
$n$ & Grau & Público\\[0.5ex]

$q$ & Módulo Maior & Público\\

$p$ & Módulo Menor & Público\\

$d_f$ & Limite inteiro para $f$ & Público\\

$d_g$ & Limite inteiro para $g$ & Público\\

$d_r$ & Limite inteiro para $r$ & Público\\

${\bf f}$ & Vector coeficiente de $f$ & Privado\\

${\bf g}$ & Vector coeficiente de $g$ & Privado\\

$\mathcal{H} = p_q^{-1}[\mathcal{C}^*{\bf h}]$ (mod $q$) & Vector coeficiente de $h$ & Público\\

${\bf h} = p[\mathcal{C}^*{\bf f}]_q^{-1}{\bf g})$ (mod $q$) & Vector coeficiente de $h$ & Público\\
\hline
\end{tabular}
\label{tab:NTRU}
\end{table}

Considerando $\mathcal{C}$ a rotação cíclica que envia um vector $(x_1,x_2,...,x_n)^T$ para $(x_n,x_1,...,x_{n-1})^T$ e definindo, para um dado $x \in \mathbb{R}^n$, a matriz circulante de $x$ como:


\[
[\mathcal{C}^*x] = [x,\mathcal{C}x,...,\mathcal{C}^{n-1}x] = 
\begin{pmatrix*}[r]
x_1 & x_n & \dotsb & x_2\\
x_2 & 0 & \dotsb & x_3\\
\vdots & \vdots & \ddots & \vdots\\
x_n & x_{n-1} & \dotsb & x_1
\end{pmatrix*}
\]

O produto da convolução dos polinómios $f * g$ é equivalente à multiplicação matricial [$\mathcal{C}^*${\bf f}]{\bf g}, representando {\bf f} e {\bf g} os vectores coeficiente de $f$ e $g$, respectivamente. Neste seguimento, a estrutura do NTRUEncrypt tem início na escolha da chave privada ({\bf f},{\bf g}), que corresponde a um vector curto em $\mathbb{Z}^{2n}$, e cujos vectores {\bf f} e {\bf g}, secretos, devem apresentar as seguintes características:

\begin{itemize}
\item A matriz [$\mathcal{C}^*${\bf f}] deve ser invertível mod $q$ e mod $p$, sendo as respectivas inversas $[\mathcal{C}^*${\bf f}]$^{-1}_{q}$ e $[\mathcal{C}^*${\bf f}]$^{-1}_{p}$.
\item {\bf f} e {\bf g} devem ser pequenos.
\end{itemize}

A chave pública {\bf h} pode, então, ser derivada partindo da chave privada através da equação:

\begin{center}
[$\mathcal{C}^*${\bf f}]{\bf h} $\equiv p${\bf g} (mod $q$) $\Rightarrow$ {\bf h} = $p[\mathcal{C}^*{\bf f}]^{-1} {\bf g}$ mod $q$
\end{center}

Sendo $H = p^{-1}_{q}$[$\mathcal{C}^*${\bf h}], em que $p^{-1}_{q}$ corresponde à inversa de $p$ mod $q$, o reticulado NTRU é definido por todos os vectores ($x$,$y$)$\in \mathbb{Z}^{2n}$ que satisfaçam $y \equiv Hx$ (mod $q$) e é abrangido pelas colunas da matriz $L$, em que $I_n$ representa a matriz identidade $n \times n$ e $O_n$ a matriz nula $n \times n$.

\[
L = 
\begin{pmatrix*}[r]
I_n & O_n\\
H & qI_n
\end{pmatrix*}
\]

Com base nos parâmetros do sistema definidos, torna-se possível explorar os processos de cifragem e decifragem. A cifragem de uma mensagem passa por codificá-la como um vector {\bf m} $\in \mathbb{Z}^n$ com coeficientes módulo $p$, gerar aleatoriamente um {\it blinding factor} {\bf r} $\in \{-1,0,1\}^n$ e, por último, calcular o texto cifrado:

\begin{center}
{\bf c} = [$\mathcal{C}^*{\bf h}$]{\bf r} + {\bf m} (mod $q$)
\end{center}

Por sua vez, a decifragem do texto {\bf c} implica a redução de ${\bf a} \equiv [\mathcal{C}^*{\bf f}$]{\bf c} (mod $q$) de tal forma que todos os coeficientes de {\bf a} se encontrem no intervalo [$-q/2$,$q/2$), seguida  do cálculo que permite obter a mensagem:

\begin{center}
{\bf m} = [$\mathcal{C}^*{\bf f}$]$^{-1}_{p}${\bf a} (mod $p$)
\end{center}

No que concerne a funcionalidade do sistema, os parâmetros $d_f$, $d_g$ e $d_r$, que estabelecem os limites inteiros, devem ser escolhidos de forma a que mesmo os produtos da convolução tenham coeficientes pequenos, contando que, quanto maiores forem estes parâmetros, maior é a probabilidade de as entradas de x = $\mathcal{C}^*{\bf f}$]{\bf m} + $p[\mathcal{C}^*{\bf g}$]{\bf r} não se encontrarem no intervalo [$-q/2$,$q/2$). Caso esta situação se verifique, ocorrerão erros no processo de decifragem que poderão ser potencialmente utilizados para conseguir extrair a chave privada, em determinadas situações \cite{POL1,BASE2}.

\begin{exmp}
Considerando os parâmetros $n = 7$, $q = 32$, $p = 3$, $d_f = 3$ e $d_g = d_r = 2$, a chave privada gerada de forma aleatória consiste em {\bf f} = (-1,0,0,1,1,-1,1) e {\bf g} = (1,-1,0,0,-1,1,0). Com base na equação que deriva a chave pública {\bf h} a partir da chave privada, obtém-se {\bf h} = (0,24,26,27,10,12,29). Neste contexto, as inversas de $[\mathcal{C}^*{\bf f}]$ módulo $q$ e $p$ são, respectivamente:

\begin{minipage}[b]{5cm}
\[
[\mathcal{C}^*{\bf f}]_q^{-1} =
\begin{pmatrix*}[r]
17 & 28 & 16 & 1 & 30 & 9 & 28\\
28 & 17 & 28 & 16 & 1 & 30 & 9\\
9 & 28 & 17 & 28 & 16 & 1 & 30\\
30 & 9 & 28 & 17 & 28 & 16 & 1\\
1 & 30 & 9 & 28 & 17 & 28 & 16\\
16 & 1 & 30 & 9 & 28 & 17 & 28\\
28 & 16 & 1 & 30 & 9 & 28 & 17
\end{pmatrix*}
\]
\end{minipage} 
\begin{minipage}[b]{13.8cm} 
\[
[\mathcal{C}^*{\bf f}]_p^{-1} =
\begin{pmatrix*}[r]
2 & 1 & 2 & 2 & 0 & 1 & 2\\
2 & 2 & 1 & 2 & 2 & 0 & 1\\
1 & 2 & 2 & 1 & 2 & 2 & 0\\
0 & 1 & 2 & 2 & 1 & 2 & 2\\
2 & 0 & 1 & 2 & 2 & 1 & 2\\
2 & 2 & 0 & 1 & 2 & 2 & 1\\
1 & 2 & 2 & 0 & 1 & 2 & 2\\
\end{pmatrix*}
\]
\end{minipage}
\vspace{0.5cm} 

Atendendo a um {\it blinding factor} {\bf r} = (1,1,0,0,0,-1,-1) escolhido de forma aleatória, a mensagem {\bf m} = (0,-1,1,-1,1,0,-1) é cifrada, dando lugar ao texto cifrado {\it c} = $[\mathcal{C}^*{\bf h}]{\bf r} + {\bf m} \equiv (11,2,14,30,29,25,16)$ (mod $q$). A decifragem é levada a cabo multiplicando {\bf c} por $[\mathcal{C}^*{\bf f}]$ e reduzindo-o mod $q$ de forma a que os respectivos coeficientes se encontrem no intervalo [-q/2,q/2):

\begin{center}
$[\mathcal{C}^*{\bf f}]{\bf c} \equiv (4,4,-4,1,-7,-4,5)$ (mod $q$)
\end{center}

A mensagem original é obtida multiplicando por $[\mathcal{C}^*{\bf f}]_p^{-1}$ e reduzindo mod $q$:

\begin{center}
$[\mathcal{C}^*{\bf f}]_p^{-1} \cdot (4,4,-4,1--7,-4,5) \equiv (0,-1,1,-1,1,0,-1) (mod $p$) = {\bf m}$
\end{center}
\end{exmp}

\vspace{0.5cm}

Em suma, pese embora o criptosistema NTRUEncrypt seja definido utilizando polinómios truncados, os ataques mais eficazes tiram partido da estrutura das chaves, através do uso de algoritmos de redução de reticulados. Contrariamente aos criptosistemas mencionados previamente, o NTRU mostra-se suficientemente eficiente para elevar os parâmetros de segurança ao mesmo tempo que mantém a competitividade.

\subsection{Esquemas de Assinatura Digital}
\label{DSS}

O conceito de assinatura digital pode ser encarado como o dual da criptografia de chave pública — que compreende a cifragem de mensagens com recurso a uma chave pública e decifragem utilizando a chave privada correspondente —, na medida em que a mensagem é assinada utilizando a chave privada e, posteriormente, a assinatura assim gerada pode ser verificada recorrendo à respectiva chave pública. Neste sentido, as assinaturas digitais podem ser utilizadas tanto para efeitos de autenticação como de avaliação da integridade das mensagens e de não-repudiação. Formalmente:


\begin{mydef} Um esquema de assinatura consiste num tripleto de algoritmos de tempo polinomial ($G$, $S$, $V$) tais que, para cada par de {\it outputs} ($s$,$v$) de $G(1^n)$ e uma qualquer mensagem $m$ de $n$-bits,
\begin{center}
$Pr[V(v,m,S(s,m)) = 1] = 1$
\end{center}
em que a probabilidade é dominada pelo carácter aleatório dos algoritmos de assinatura ($S$) e de verificação ($V$). Neste contexto, $G$ é o algoritmo de {\it key-generation} e $s$ e $v$ são as chaves de assinatura e verificação, respectivamente.
\end{mydef}

Considera-se que um esquema de assinatura é seguro se for desprezável a probabilidade de um qualquer {\it forger}, após visualizar assinaturas de mensagens à sua escolha, conseguir assinar uma mensagem cuja assinatura ainda não tenha visto. Isto é:

\begin{mydef} Um esquema de assinatura ($G$, $S$, $V$) é dito seguro se, para todo o {\it forger} $\mathcal{F}$ de tempo polinomial (e possivelmente aleatório), a probabilidade de, depois de visualizar a chave pública e \{($\mu_1$, $S$($s$,$\mu_1$)),...,(($\mu_q$, $S$($s$,$\mu_q$))\}, para quaisquer $q$ (polinomial em $n$) mensagens $\mu_1$ à sua escolha, $\mathcal{F}$ conseguir produzir ($\mu$ $\neq$ $\mu_1,$ $\sigma$) tal que $V$($v$,$\mu$,$\sigma$=1) seja negligentemente pequena.
\end{mydef}

De entre as diversas tentativas de construção de esquemas de assinatura digital baseados em reticulados, apenas a recente proposta de Lyubashevsky \cite{DSFIAT} se mantém, ainda, inquebrável, sendo que abordagens como aquelas derivadas dos criptosistemas GGH ou NTRU — o NTRU Signature Scheme, quebrado por Gentry et al., e o NTRUSign, quebrado por Nguyen e Regev, após a respectiva aproximação a um problema de aprendizagem — provaram ser falíveis para determinadas dimensões.

\subsubsection{Esquema de Assinatura de Lyubashevsky}

O esquema de Lyubashevsky baseia-se em reticulados ideais e recorre à transformada de Fiat-Shamir para transformar esquemas de identificação em esquemas de assinatura digital, abordagem que permite minorar um defeito associado ao esquema de identificação inicialmente construído: considerando que uma resposta correcta por parte do {\it prover} é suficiente para a autenticação, numa dada fracção constante de tempo, o {\it prover} não é capaz de responder correctamente ao desafio do {\it verifier} e é forçado a abortar o protocolo, o que  implica a repetição dos passos de {\it commit} e {\it challenge} do esquema de identificação várias vezes, de forma a assegurar que um {\it prover} válido é aceite contra uma probabilidade aceitável. Ao anular qualquer interacção até que a assinatura seja efectivamente emitida, deixa de ser necessário expor as tentativas falhadas de resposta ao desafio — que correspondem às tentativas de assinar —, pelo que, ainda que as sucessivas falhas sejam {\it time-consuming}, o comprimento da assinatura final é tão curto quanto seria caso o {\it signer} tivesse tentado assinar apenas uma vez e tivesse imediadamente sucedido. Assim, e contando que a probabilidade de falha associada ao processo é diminuta e constante ($\approx$ $2/3$), o protocolo de assinatura sucederia ao fim de apenas três repetições \cite{DSFIAT,POL1}. A segurança dos esquemas de identificação e de assinatura assim obtidos baseia-se na {\it worst-case hardness} de aproximar o vector mais curto a um factor de $\tilde{O}(n^2)$ em reticulados correspondentes a ideais no anel $\mathbb{Z}[x]/\langle x^n + 1 \rangle$ e distancia-se dos demais devido ao facto de a assinatura poder ser concluída em tempo $\tilde{O}(n)$ \cite{DSFIAT}.

\subsubsection{Esquemas Baseados Em Funções de Hash Resistentes a Colisões}

Por definição, uma função de {\it hash} resistente a colisões consiste numa função $h : D \rightarrow$ R que mapeia um domínio $D$ a um conjunto consideravelmente mais reduzido $R$, tal que se torna computacionalmente difícil encontrar colisões. Neste contexto, entende-se por colisão a existência de um par $x_1,x_2 \in D$ tal que se verifique $x_1 \neq x_2$ e, ainda assim, $h(x_1) = h(x_2)$. Considerando uma colecção de funções \{$h_k : D \rightarrow R$\} e o parâmetro $k$ aleatório, torna-se possível assegurar que nenhum atacante é capaz de encontrar uma colisão em $h_k$ de forma eficiente, pese embora tais colisões existam, dado que $|D| \gg |R|$. Neste sentido, as funções de {\it hash} resistentes a colisões assumem um papel importante (ou, pelo menos, útil) na construção de primitivas criptográficas, permitindo comprimir uma mensagem extensa ${\bf x} \in D$ numa entidade sumária $h(x) \in R$ que se encontra computacionalmente associada a um {\bf x} único devido à propriedade de resistência à colisão anteriormente descrita \cite{BASE2}. Pese embora as funções de {\it hash} possam ser construídas com base em problemas {\it standard} da Teoria dos Números, estas construções pecam por serem facilmente quebradas por computadores quânticos, pelo que uma abordagem mais robusta passa por baseá-las em reticulados.

Ajtai apresentou, no seu trabalho seminal \cite{AJTAI}, a primeira construção baseada em reticulados, reportando-se a uma família de funções  unidireccionais cuja segurança assenta sobre a dificuldade {\it worst-case} do ${\it n}^c$-ASVP para uma dada constante $c > 0$, implicitando que a tentativa de inverter uma das funções desta família é, em termos de complexidade, equivalente à resolução de qualquer instância deste problema {\it hard}. Atentando no Algoritmo~\ref{al:AJTAI}, que traduz os elementos envolvidos na construção de uma função de {\it hash} segundo a teoria de Ajtai, torna-se importante realçar que a escolha do parâmetro $n$ determina o nível de segurança da função. Em termos de {\it bits}, a função mapeia $m \log q$ {\it bits} em $n \log q$ {\it bits}, pelo que o parâmetros $m$ deve ser escolhido de forma a verificar $m > n \log q/ \log d$ e a garantir, assim, que a função obtida é capaz de comprimir o {\it input} \cite{BASE2}.

\begin{algorithm}
\caption{Função de {\it hash} baseada na construção de Ajtai}
\label{al:AJTAI}

\begin{tabbing}
\\
{\bf Parâmetros:} Inteiros $n$, $m$, $q$, $d \geq 1$.
\\
\\
{\bf Chave:} Matriz $\mathcal{A}$ escolhida uniformemente de $\mathbb{Z}_q ^{n \times m}$.
\\
\\
{\bf Função:} $f_{\bf \mathcal{A}} : \{0,...,d-1\}^m \rightarrow \mathbb{Z}_q ^n$ dada por $f_{\bf \mathcal{A}} ({\bf y}) = {\bf \mathcal{A}y}$ mod $q$.
\end{tabbing}
\end{algorithm}

Não obstante a simplicidade de implementação das funções de {\it hash} proposta por Ajtai, as construções conformes aos termos explicitados apresentam uma lacuna considerável, ao nível da eficiência, na medida em que o tamanho da chave cresce, pelo menos, de forma quadrática em $n$. A título de exemplo, cita-se a situação equacionada por Micciancio e Regev \cite{BASE2}: considerando um cenário com $d = 2$, $q = n^2$ e $m = 2 \log q = 4n \log n$, a correspondente função teria uma chave composta por $mn = 4n^2 \log n$ elementos de $\mathbb{Z}_q$ e a respectiva avaliação requereria, aproximadamente, um número semelhante de operações aritméticas. As colisões são dadas pelos vectores em $\Lambda_q ^\bot({\bf \mathcal{A}})$ — o reticulado $q$-ary $m$-dimensional $\Lambda_q ^\bot ({\bf \mathcal{A}}) = \{{\bf y} \in \mathbb{Z}^m : {\bf \mathcal{A}y} = 0$ mod $q\}$, que contém todos os vectores ortogonais módulo $q$ às linhas de ${\bf \mathcal{A}}$ — com entradas em \{1,0,-1\}. Assim, considerando um ataque de complexidade $L = 3^{m/16} \approx 2^{m/10}$ e almejando obter 100 {\it bits} de segurança ($L \approx 2^{100}$), os parâmetros $m$ e $n$ teriam de ser fixados em $m \approx 1000$ e $n \geq 46$, o que resultaria numa função de {\it hash} com uma chave de tamanho $mn \log q \approx 500,000$ {\it bits} e um tempo de computação na ordem das $mn \approx 50,000$ operações aritméticas, o que é inconcebível no contexto das funções de {\it hash} resistentes a colisões.

Os problemas anteriormente apontados podem ser resolvidos de forma relativamente simples, adoptando matrizes com estruturas específicas, como seja, no Algoritmo~\ref{al:AJTAI}, a substituição da matriz $\mathcal{A} \in \mathbb{Z}_q ^{n \times m}$ por uma matriz bloco em que cada bloco seja uma matriz circulante, o que se repercute de imediato no espaço de armazenamento requerido para a chave — que passa de $nm$ elementos de $\mathbb{Z}_q$ para apenas $m$ elementos — e no tempo de execução — uma vez que a multiplicação por uma matriz circulante pode ser implementada em tempo $\tilde{O}(n)$ utilizando a Transformada Rápida de Fourier (Fast Fourier Transform (FFT)). Embora, sempre que se efectue uma modificação numa construção teórica no sentido do aumento da eficiência, se deva ponderar quais as implicações dessa modificação ao nível da segurança, Micciancio \cite{MICHASH} provou que é razoável assumir que resolver problemas de reticulados neste tipo de reticulados é tão {\it hard} quanto no caso geral.

O Algoritmo~\ref{al:AJTAI} pode ser adaptado (Algoritmo~\ref{al:IDEAIS}) no sentido de incorporar chaves estruturadas $\mathcal{A}$, considerando como parâmetros os inteiros $n$, $m$, $q$, $d$ e um vector {\bf f} $\in \mathbb{Z}^n$. Neste caso, a escolha aleatória de $\mathcal{A}$ a partir do conjunto de todas as matrizes é substituída pela declaração de $\mathcal{A}$ como uma matriz bloco com blocos estruturados $\mathcal{A}^{(i)} = {\bf F}^* {\bf a}^{(i)}$.

\begin{algorithm}
\caption{Função de {\it hash} baseada em reticulados ideais.}
\label{al:IDEAIS}

\begin{tabbing}
\\
{\bf Parâmetros:} Inteiros $n$, $m$, $q$, $d$ com $n | m$, e um vector {\bf f} $\in \mathbb{Z}^n$
\\
\\
{\bf Chave:} $m/n$ vectores ${\bf a}_1,...,{\bf a}_{m/n}$ escolhidos independente e uniformemente de forma aleató\\ria de $\mathbb{Z}_q^n$.
\\
\\
{\bf Função:} $f_{\bf \mathcal{A}} : \{0,...,d-1\}^m \rightarrow \mathbb{Z}_q ^n$ dada por $f_{\bf \mathcal{A}} ({\bf y}) = [{\bf F}^*{\bf a}_1 | ... | {\bf F}^*{\bf a}_{m/n}]${\bf y} mod $q$.
\end{tabbing}
\end{algorithm}

Na função representada no Algoritmo~\ref{al:IDEAIS}, as chaves são representadas por apenas $m$ elementos de $\mathbb{Z}_q$ e esta pode ser avaliada recorrendo a $\tilde{O}(m)$ operações aritméticas utilizando a Transformada Rápida de Fourier (FTT) em $\mathbb{C}$. As colisões correspondem a vectores curtos no reticulado $\Lambda_q^\bot ([{\bf F}^*{\bf a}_1 | ... | {\bf F}^*{\bf a}_{m \times n}])$ e, obedecendo a determinadas condicionantes, asseguram que as funções de {\it hash} construídas apresentam garantias de segurança {\it worst-case} \cite{BASE2,MICHASH}.

No sentido de contrariar o {\it overhead} que, na prática, se regista aquando da efectiva utilização das funções acima descritas, Lyubashevsky et al. \cite{SWIFFT} propuseram uma versão optimizada destas últimas: a família de funções de {\it hash} SWIFFT (Algoritmo~\ref{al:SWIFFT}), que tira partido da estrutura do algoritmo da FTT para atingir uma {\it performance} superior. Esta optimização é atingida considerando um vector binário como {\it input} da Transformada, o que limita necessariamente o número possível de entradas e viabiliza o cálculo prévio e o armazenamento das iterações iniciais numa tabela; e considerando o facto de que o algoritmo da FTT consiste em operações repetidas em paralelo sobre várias parcelas de dados, para as quais os microprocessadores actuais estão configurados \cite{SWIFFT,BASE2}.

\begin{algorithm}
\caption{Função de {\it hash} SWIFFT.}
\label{al:SWIFFT}

\begin{tabbing}
\\
{\bf Parâmetros:} Inteiros $n$, $m$, $q$, $d$ tal que $n$ é uma potência de 2, $q$ é primo, $2n | (q-1)$ e $n | m$.
\\
\\
{\bf Chave:} $m/n$ vectores ${\bf \tilde{a}_1},...,{\bf \tilde{a}_{m/n}}$ escolhidos independente e uniformemente de forma aleató\\ria de $\mathbb{Z}_q^n$.
\\
\\
{\bf Input:} $m/n$ vectores ${\bf y}^(1),...,{\bf y}^{(m/n)} \in \{0,...,d-1\}^n$.
\\
\\
{\bf Output:} o vector $\sum_{i=1} ^{m/n} {\bf \tilde{a}^(i)} \odot ({\bf Wy}^{(i)}) \in \mathbb{Z}_q ^n$, em que $\odot$ representa o produto do vector {\it com}\\{\it ponent-wise}.
\end{tabbing}
\end{algorithm}

Com base nas construções apresentadas, Lyubashevsky e Micciancio desenvolveram um esquema de assinatura aparentemente óptimo, na medida em que admite uma prova de segurança baseada em assumpções de complexidade {\it worst-case} e revela uma eficiência assimptótica, sendo que  o tamanho da chave e o tempo de assinatura e verificação são quase lineares na dimensão do reticulado inerente ao esquema. O sistema baseia-se num esquema de assinatura {\it one-time} — que permite a assinatura em segurança de uma única mensagem —, por sua vez baseado em funções de {\it hash} resistentes a colisões, que é posteriormente transformado num esquema de assinatura completo. Conforme explicitado na exposição acerca desta família de funções, encontrar colisões numa função {\it hash} $h$ é computacionalmente {\it hard}, pelo que se parte de $h$ e de um par de vectores ${\bf x}_1,...,{\bf x}_m/n \in \mathbb{Z}_q^n$ e ${\bf y}_1,...,{\bf y}_m/n \in \mathbb{Z}_q^n$ escolhidos de forma aleatória e de acordo com uma dada distribuição que gera vectores curtos com probabilidade elevada. As imagens destes vectores de {\it input} na função de {\it hash} $X = h({\bf x}_1,...,{\bf x}_m/n)$, $Y = h({\bf y}_1,...,{\bf y}_m/n)$ correspondem à chave pública, sendo que as mensagens a assinar são representadas por vectores curtos ${\bf m} \in \mathcal{Z}_q^n$ e a assinatura consiste simplesmente no cálculo:

\begin{center}
$\sigma = (\sigma_1,...,\sigma_{m/n})$ = $[{\bf F}^*{\bf m}]{\bf x}_1 + {\bf y}_1,...,[{\bf F}^*{\bf m}]{\bf x}_m/n + {\bf y}_m/n$ mod $q$.
\end{center}

A construção proposta assegura não só o conceito básico de segurança, mas ainda uma noção mais robusta de segurança, denominada de {\it strong unforgeability}, que requer adicionalmente que um {\it forger} $\mathcal{F}$ não seja sequer capaz de apresentar uma assinatura diferente para uma mensagem de cuja assinatura este já teve conhecimento \cite{LYUMIC}.

\newpage
\thispagestyle{plain}
\section{Conclusão}
\label{CONCLAT}

As construções criptográficas com base em reticulados representam uma promessa significativa no âmbito da criptografia pós-quântica, uma vez que não existem, actualmente, algoritmos quânticos cujo desempenho seja melhor do que o dos algoritmos clássicos, não obstante os reticulados apresentarem características que os tornam favoráveis (ou elegíveis) à resolução por intermédio deste tipo de algoritmos. O facto de serem de implementação menos complexa e de assumirem graus de eficiência relativamente equiparáveis aos das melhores alternativas conhecidas, aliado ao facto de, em certos casos, admitirem  garantias de segurança sólidas baseadas na dificuldade {\it worst-case} de problemas de reticulados, fazem com que este tipo de construções sejam particularmente interessantes num futuro próximo, no sentido de proteger informação enviada através de canais inseguros.

Da análise dos três criptosistemas considerados — Ajtai-Dwork, GGH e NTRU — retira-se que apenas os dois últimos são explicitamente baseados em reticulados, sendo que o primeiro apenas se enquadra nesta dimensão ao nível da prova de segurança, directamente baseada em problemas {\it hard}. No que concerne o sistema NTRU, o facto de a relação entre as chaves pública e privada assentar sobre uma estrutura de reticulados torna-o especialmente vulnerável a ataques que utilizem técnicas de redução, mas este é irrefutavelmente, de entre os três, o mais eficiente. Todos os criptosistemas descritos almejam atingir a noção de segurança semântica, que não se revela suficientemente forte para casos em que o adversário não seja passivo. Nestas situações, há que considerar esquemas com garantias de segurança mais robustas, a grande maioria dos quais baseados no problema {\it hard} LWE, que não foi explorado no âmbito deste trabalho.

Por último, os esquemas de assinatura digital baseados nos conceitos subjacentes às construções anteriormente referidas, nomeadamente nos criptosistema GGH e NTRU, provaram ser facilmente quebráveis (pelo menos, na sua versão básica), facto indeferivelmente explanável pelo facto de nenhum dos dois ser acompanhado de uma prova de segurança. Pese embora se apresentem dois sistemas considerados bastante eficazes e seguros — um dos quais apresenta mesmo {\it strong unforgeability} —, os esquemas de assinatura baseados em reticulados não atingiram ainda o patamar de desenvolvimento das restantes construções criptográficas.



\newpage
\pagestyle{empty}
\bibliographystyle{unsrt}
\bibliography{BIBCRIPTO}


\end{document}