Methods and apparatus are provided for performing authentication and decryption operations. A record including multiple encrypted blocks is received. An encrypted block in the record is extracted and decrypted first in order to obtain context information for performing authentication operations. Each remaining block is then decrypted and authenticated by using the available context information. Authentication operations can be performed without having to wait for the decryption of all of the blocks in the record.