this is for holding javascript data
Scott Fluhrer edited section_Abstract_This_paper_explores__.tex
almost 9 years ago
Commit id: cb3a5fe49148d389859f2a07b059851dd9e65879
deletions | additions
diff --git a/section_Abstract_This_paper_explores__.tex b/section_Abstract_This_paper_explores__.tex
index 9f3c73a..6b50fc9 100644
--- a/section_Abstract_This_paper_explores__.tex
+++ b/section_Abstract_This_paper_explores__.tex
...
While NTRU is immune to Shor's algorithm (which allows the attacker to quickly factor numbers and compute discrete logarithms). However, a Quantum Computer also allows an attacker to run Grover's algorithm\cite{Grover_1996}, which is able to find a $n$ bit solution to a problem in $2^{n/2}$ time. The question we would like to look at is 'how can Grover's algorithm be used to advantage in attacking NTRU?'
\section{NTRU Basics}
NTRU works in the ring of polynomials $Z[x]/x^N-1$, where $N$ is a prime. Computations in this ring are actually done modulo a prime power; NTRUEncrypt actually evaluates additions and multiplications modulo a prime power ($q$) and a small polynomial ($p$) during the course of its operation. However, all the operations that we'll examine are done modulo $q$ (where $q=2048$ is a typically choice), hence for the purposes of this paper, we can consider the ring to be
$Z[x]/(x^N-1,q)$ $Z[x]/(x^N-1,q)$. In addition to the base NTRU operation, NTRUEncrypt uses a padding mechanism called NAEP to protect the underlying NTRU
primitive from decryption failures.
There are a number of parameter sets defined for NTRU; each parameter set includes the value of $N$ that are used during the NTRU operations, the values of $p$ and $q$, the density of the internal polynomials $F$, $G$ and $R$ (these densities are known as $dF$ and $dG$), as well as the expected security level for this parameter set (that is, the value $k$ for which we expect any attack against this parameter set to take at least $O(2^k)$ operations.
NTRUEncrypt is available as a free-for-noncommercial use library from Security Innovations; I will be analysising the parameter sets implemented by that library.
When we select a private key for NTRUEncrypt, we select two polynomials $F$ and $G$ with specific sets of coefficients; we also need to make sure that $F$ is invertible. Once we have that, we can compute the public polynomial $H = F^{-1}G$. The public key decryption process uses the secret polynomial $F$ to decrypt.
When we encrypt a message $m$ with an NTRUEncrypt public key, we perform the following steps: