Methods and apparatus are presented for secure, authenticated communication and data storage. The methods can be based on other methods such as IAPM, in which the encryption and authentication keys are of the same strength. In the HR-IAPM mode, a sender encrypts the data as in the IAPM mode using two encryption keys K.sub.0 and K.sub.1. The sender then XORs the plaintexts with corresponding ciphertexts, and combines the results to form a checksum This checksum is encrypted under the authentication key K.sub.2, this value is appended to the encrypted message as a message authentication code (MAC). The receiver decrypts as with IAPM, XORs the plaintexts with the corresponding ciphertexts and combines these values to form a checksum. The receiver then encrypts the checksum under the authentication key K.sub.2 and verifies that the resulting value agrees with the MAC. The HR mode allows blocks to be sent un-encrypted if desired.