Imperfect decryption and partial information attacks in cryptography

There are two main themes running throughout this thesis. The first is the security of cryptographic schemes in which decryption failures can occur when decrypting valid ciphertexts and the second is the security of cryptographic schemes when an adversary has access to partial information on some of the secret values. While the two themes are quite independent they both arose from a consideration of the use of lattices in cryptography.; Considering the security of schemes in which decryption failures can occur developed out of a security analysis of the NTRU encryption scheme. NTRU has the interesting property that validly generated ciphertexts will occasionally not decrypt correctly. We present a new type of attack on NTRU and its proposed EESS#1 standard based on decryption failures, which under reasonable assumptions can recover NTRU secret keys for the currently suggested parameter sets. In the field of provable security the definition of a public-key encryption scheme requires that every validly created ciphertext correctly decrypts to the plaintext used to form it. However, there are schemes like NTRU that while not possessing this property have had provable security results (invalidly) applied to them. To enable provable security results to be applied to such schemes we extend the provable security definitions and some of the important security results to schemes without perfect decryption.; In recent years security analyses of cryptographic schemes against attackers with partial information on some secret values have been performed. We provide such analysis for the ESIGN signature scheme and the Nieto, Boyd and Dawson identification and signature schemes. The analysis of these schemes includes attacks based on the hidden number problem as well as attacks based on an extension of the partial approximate common divisor problem. Finally we show how certain implementations of the Digital Transmission Content Protection protocol can leak enough partial information to an attacker to allow lattice techniques to recover the user's secret key.