1
$\begingroup$

I'm self-studying NTRU encrypt, and I read following in the book "an introduction to mathematical cryptography" -Chapter 6.10-remark 6.50 (Jeffrey hoffstein, Jill Pipher, Joseph H. silverman):

NTRU is an example of a probabilistic cryptosystem, since a single plaintext m(x) has many different encryptions p*h(x)*r(x)+m(x) corresponding to different choices of the ephemeral key r(x). (In here, h(x) is public key, m(x) is a message, and p is a public parameter. r(x) is randomly chosen in the encryption phase.)

It would be a bad idea to send the same message twice using different ephemeral keys (i.e. r(x)), just as it would be bad to use the same ephemeral key to send two different plaintexts. The standard solution to this danger is to generate the ephemeral key as a hash of the plaintext.

enter image description here

My question is:

why is it dangerous to send the same message with two different random ephemeral keys?

And why does using the hash of the plaintext keep security?

I read a paper, "Authenticating Privately over Public Wi-Fi Hotspots", and they generate a query vector $v_i$ like in the below figure. (for Private Information Retrieval). And the query consists of lots of (NTRU-encrypted) ciphertexts of '$0$', and an attacker absolutely knows it. Is it safe?

enter image description here

Improve this question
$\endgroup$
5
  • $\begingroup$ Since the "ephemeral key" is what provides randomness, if you always use the same one encryption becomes deterministic. $\endgroup$ – fkraiem Nov 10 '17 at 8:37
  • $\begingroup$ @fkraiem What I'm asking is the situation when different ephemeral keys for the same message are used. $\endgroup$ – takita Nov 10 '17 at 8:40
  • $\begingroup$ The respective attack is described in an old NTRU technical report. Basically, you obtain $r_i(x) - r_1(x)$ from $(e_i(x) - e_1(x)) h(x)^{-1} p^{-1} \pmod{q}$, and from that information and due to $r_i(x)$'s small coefficients, eventually $r_1(x)$. This lets you decrypt the message, but not recover the private key. $\endgroup$ – Samuel Neves Nov 10 '17 at 10:26
  • $\begingroup$ FWIW, I'm not really familiar with NTRU, but in general making any public-key encryption scheme deterministic in this way sounds like a bad idea, since it breaks semantic security. (Basically, an attacker can guess a possible plaintext, encrypt it, and compare the result to the ciphertext.) A better solution would seem to be to apply random padding to the plaintext before encryption so that it becomes (almost surely) unique. (Apparently, that's basically what the second method suggested in the paper linked by @SamuelNeves does.) $\endgroup$ – Ilmari Karonen Nov 12 '17 at 17:03
  • $\begingroup$ @SamuelNeves,IlmariKaronen Thanks. I think the padding is the solution. $\endgroup$ – takita Nov 13 '17 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.