Techniques for encryption and authentication of data. One or more plaintext data blocks ciphertext data blocks and corresponding authentication tags are generated by means of authenticated encryption. A tag tree is generated by means of the authentication tags. The ciphertext data blocks and the tag tree data of the tag tree are stored in an untrusted storage, and the root tag of the tag tree is stored in a trusted storage.