Abstract:
NTRUEncrypt is unusual among public-key cryptosystems in that,
with standard parameters, validly generated ciphertexts can fail to
decrypt. This affects the provable security properties of
a cryptosystem, as it limits the ability to build a
simulator in the random oracle model without knowledge of the private key.
We demonstrate attacks which use decryption failures to recover the private
key. Such attacks work for all standard parameter sets,
and one of them applies to any padding. The appropriate countermeasure is
to change the parameter sets and possibly the decryption process so that
decryption failures are vanishingly unlikely, and to adopt a padding scheme
that prevents an attacker from directly controlling any part of the input
to the encryption primitive. We outline one such candidate padding scheme.