this is for holding javascript data
Scott Fluhrer edited section_Abstract_This_paper_explores__.tex
almost 9 years ago
Commit id: f55392539558e8e5dd354b11ed554227c6b5f832
deletions | additions
diff --git a/section_Abstract_This_paper_explores__.tex b/section_Abstract_This_paper_explores__.tex
index f964bc4..a46289f 100644
--- a/section_Abstract_This_paper_explores__.tex
+++ b/section_Abstract_This_paper_explores__.tex
...
For security levels 112, 128, we use a 160 bit hash, hence this approach will take an expected $O(2^{80})$ operations. For security levels 192, 256, we use a 256 bit hash, hence this approach will take an expected $O(2^{128})$ operations; in both cases, the work required is significantly smaller than the target security levels.
\section{Plaintext Recovery Attack 2}
When someone with the NTRUEncrypt public key does Another way an
public key encryption of the plaintext message $m$, it runs through this process: first, he examines the public key attacker can attempt to
get its security level $k$ for recover the
parameter set. He then selects a $k$-bit random value $b$, and encodes that value (along with the plaintext $m$ and part of the public key) to form a string; it then uses that string as a seed to a random number generator to select a polynomial $R$; he then encodes plaintext, if the plaintext
(and $b$) as a polynomial $M$, extracts the polynomial $H$ from the public key, and outputs the polynomial $HR+M$ as the ciphertext.
Now, it is
slightly more complicated than that; the polynomial $M$ low entropy, is
subject to tests to
make sure that it has sufficiently high coefficient diversity (its coefficients are all from the set $\{0, 1, -1\}$, we make sure that sufficiently many of each value appear); if it does not, it is rejected (and a different random value for $b$ is selected). However, it turns out that does not matter for this attack.
The key observation is noticy that the ciphertext is a
deterministic determanistic function of the plaintext, the public
key key, and
a the $k$-bit random
value. value $b$. If the
attacker knows that entropy of the
message $m$ had plaintext is low
entropy (e.g. there were (had only $2^n$ possible
values for it, values, for $n \lll k$),
then 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 is, $m$ and $b$) that generates the known ciphertext in $O(2^{(n+k)/2})$ time, which is less than the security level
$2^k$. $2^k$ (and if $n$ is sufficiently small, this value may be even smaller than the previous attack.
As for the tests that are done on $M$ during the encryption process, this attack can ignore that. This is because any value of $b$ that gives an unacceptable $M$ will result in a different ciphertext than what we see, hence it will not be selected by Grover's algorithm.