this is for holding javascript data
Scott Fluhrer edited section_Abstract_This_paper_explores__.tex
almost 9 years ago
Commit id: f995f6de97d93d9e1b157365c696bf0b28153ac8
deletions | additions
diff --git a/section_Abstract_This_paper_explores__.tex b/section_Abstract_This_paper_explores__.tex
index 94b8fa8..9f3c73a 100644
--- a/section_Abstract_This_paper_explores__.tex
+++ b/section_Abstract_This_paper_explores__.tex
...
This paper explores some attacks that may be possible against NTRUEncrypt if the attacker has a Quantum Computer; we show one way where the attacker is able to recover a low entropy plaintext from the ciphertext and public key with less than expected effort. We also show an academic attack that can recover the private key from the public key with fewer operations than expected, in at least 2 of the parameter sets defined for NTRUEncrypt.
\section{Introduction}
NTRUEncrypt\cite{Whyte_2005} is a public key encryption system designed by
[Look up who/when]. Jeffrey Hoffstein, Jill Pipher and Joseph Silverman. It has several attractive features, one of which is that it is immune to attacks by Shor's algorithm (as it does not rely on a factorization or
discete discrete log hard problem). Hence, it looks to be a logical component as a part of a Quantum-Resistant cryptosystem.
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
two different a prime
powers ($p$ power ($q$) and
$q$) 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)$
In addition to the base NTRU operation, NTRUEncrypt uses a padding mechanism called NAEP to protect the underlying NTRU
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.