International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: NAEP: Provable Security in the Presence of Decryption Failures

Nick Howgrave-Graham
Joseph H. Silverman
Ari Singer
William Whyte
Search ePrint
Search Google
Abstract: We consider the impact of the possibility of decryption failures in proofs of security for padding schemes, where these failures are both message and key dependent. We explain that an average case failure analysis is not necessarily sufficient to achieve provable security with existing CCA2-secure schemes. On a positive note, we introduce NAEP, an efficient padding scheme similar to PSS-E designed especially for the NTRU one-way function. We show that with this padding scheme we can prove security in the presence of decryption failures, under certain explicitly stated assumptions. We also discuss the applicability of proofs of security to instantiated cryptosystems in general, introducing a more practical notion of cost to describe the power of an adversary.
  title={NAEP: Provable Security in the Presence of Decryption Failures},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / lattice techniques, public-key cryptography, encryption schemes, provable security},
  note={ 12278 received 14 Aug 2003},
  author={Nick Howgrave-Graham and Joseph H. Silverman and Ari Singer and William Whyte},