Abstract:
NTRU is an efficient patented public-key cryptosystem proposed in 1996 by
Hoffstein, Pipher and Silverman. Although no devastating weakness of NTRU has
been found, Jaulmes and Joux presented at Crypto '00 a simple chosen-ciphertext
attack against NTRU as originally described. This led Hoffstein and Silverman to
propose three encryption padding schemes more or less based on previous work by
Fujisaki and Okamoto on strengthening encryption schemes. It was claimed that
these three padding schemes made NTRU secure against adaptive
chosen-ciphertext attacks (IND-CCA) in the random oracle model. In this paper,
we analyze and compare the three NTRU schemes obtained. It turns out that the
first one is not even semantically secure (IND-CPA). The second and third ones
can be proven IND-CCA-secure in the random oracle model, under however
rather unusual assumptions. They indeed require a partial-domain one-wayness
of the NTRU one-way function which is likely to be a stronger assumption than
the one-wayness of the NTRU one-way function. We propose several
modifications to achieve IND-CCA-security in the random oracle model under
the original NTRU inversion assumption.