this is for holding javascript data
Scott Fluhrer edited section_Abstract_This_paper_explores__.tex
almost 9 years ago
Commit id: 41eeed1a3c138221f9067723edabdca66f3331b4
deletions | additions
diff --git a/section_Abstract_This_paper_explores__.tex b/section_Abstract_This_paper_explores__.tex
index 6a3f3a6..4f32d22 100644
--- a/section_Abstract_This_paper_explores__.tex
+++ b/section_Abstract_This_paper_explores__.tex
...
\section{Introduction}
NTRUEncrypt is a public key encryption system designed by [Look up who/when]; 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 log hard problem). It has been proposed as one component of a cryptosystem that is immune to attackers with a Quantum Computer.
While NTRU is immune to Shor's algorithm (which allows the attack to quickly factor numbers and compute discrete logarithms). However, a
Quanum Quantum Computer also allows an attacker to run Grover's algorithm, 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{Plaintext Recovery Attack}
During NTRU encryption, When someone with the
encryptor NTRUEncrypt public key does an public key encryption, it runs through this process: first, he examines the public key to get its security level $k$ (that is, the parameter set of the public key was designed to withstand attacks that use at most $O(2^k)$ operations).
The encryptor He then selects a $k$-bit random value $b$, and
uses encodes that value
$b$, (along with the plaintext
$M$ and the public key to generate the ciphertext $C$; it does this by encoding the value $b$, the message $m$ and part of the public
key into key) to form a string;
using it then uses that string
to as a seed
to a random number
generator, using that random number generator to
generate select a polynomial
$R$, and $R$; he then
using that $R$ (multiplied by encodes the plaintext (and $b$) as a polynomial $M$, extracts the polynomial $H$ from the public
key) to encode key, and outputs $HR+M$ as the
actual padded message. It ciphertext.
Now, it is
possible that the slightly more complicated than that; the polynomial $R$
will be considered unacceptable (as it is
required subject to
have a given weight); tests to make sure that it has sufficiently high weight; if it
does not, it is
not accepted, a different rejected (and random value for $b$ is
selected, and the process is rerun. selected). However, that does not matter for this attack.
The key observation
here is that the ciphertext is a
deterministic function of the
final value $b$, the message $M$ and plaintext, the public
key. key and a $k$-bit random value. If the attacker knows that the message
$M$ $m$ had low entropy (e.g. there were only $2^n$ possible values for it, for $n \lll k$), what an attacker with a Quantum Computer could do is model the system as one with $2^{n+k}$ inputs (which consists of the $2^n$ possible inputs for the plaintext, paired with the $2^k$ possible values for $b$), and then apply Grover's algorithm to find a solution that generates the ciphertext in $2^{(n+k)/2}$ time, which is less than the security level $2^k$.
This As for the tests on $R$, this attack can ignore
the checking whether $R$ that. This is
acceptable, as because any value of $b$ that gives an unacceptable $R$ will result in a different
ciphertext, ciphertext than what we have see, hence it will not be selected by Grover's algorithm.
Now, in practice, this attack would not generally appear to be a significant threat; in most cases, NTRUEncrypt will be used to pass symmetric keying data, and symmetric keying data has high entropy, making this attack infeasible. However, in those cases where NTRUEncrypt is used to transmit low-entropy plaintexts, it would be advisable to include some extra random bits in the plaintext (to avoid this attack).