Incremented authenticated encryption involves dividing a data stream to be encrypted into multiple data segments and encrypting each of the data segments. For each encrypted data segment, an authorization tag is generated. Each segment's authorization tag may be based on the corresponding segment's position in the sequence of data segments within the data stream. A segment authorization tag may be generated based on an segment initialization vector that may be incremented with each segment authorization tag. Each data segment may be encrypted independently of the others. Similarly, each encrypted data segment may be decrypted and authenticated independently of the others. Additionally, a final authentication tag may be generated. The final authentication tag may be used to authenticate all the data segments of the data stream as a whole.