Paper 2003/172

NAEP: Provable Security in the Presence of Decryption Failures

Nick Howgrave-Graham, Joseph H. Silverman, Ari Singer, and William Whyte

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.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
lattice techniquespublic-key cryptographyencryption schemesprovable security
Contact author(s)
wwhyte @ ntru com
History
2003-08-15: received
Short URL
https://ia.cr/2003/172
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/172,
      author = {Nick Howgrave-Graham and Joseph H.  Silverman and Ari Singer and William Whyte},
      title = {NAEP: Provable Security in the Presence of Decryption Failures},
      howpublished = {Cryptology ePrint Archive, Paper 2003/172},
      year = {2003},
      note = {\url{https://eprint.iacr.org/2003/172}},
      url = {https://eprint.iacr.org/2003/172}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.