I am searching for an authenticated encryption sheme with random access and a good performance.

The exact requirements are:

Data to protect: data = data_block_0 || ... || data_block_n

Every data_block has a size of n bytes, 512 for example and the complete data can have a size of many gigabytes.

I search for an authenticated encrypted sheme, which makes it possible to change a data block and update a authentication tag with a good performace.

All authenticated encryption shemes I found (e.g. AEGIS, AES-GCM, Deoxys) uses a chain from data_block_0 to data_block_n to compute the authentication tag. In consequence if I change block_i, I must re computate all blocks with j>i.

A simple approach to realize integrity of the data: mac_i = MAC(K, blocknumber || block_i || block_length in bytes) enc_mac_i = Enc(K, mac_i, IV = blocknumber) mac = Enc( K, enc_mac_0 xor ... xor enc_mac_n xor mac(k, complete length), IV)

This example should demonstrate the requirement, which I need. This approach has many weaknesses.

If I change block_i I must remove the old enc_mac_i from the complete mac with xor and add the new mac with xor. This is possible with a good performance.

Knows anybody an authenticated encrypted sheme, that fullfills this requirment with proven security?

  • $\begingroup$ UMACs such as GMAC and Poly1305 allows for calculating the tag from blocks of messages in random order as they use arithmetics based on mathematic fields (numbers that can be added and multiplied). Because of this, I think AES-GCM and ChaCha20-Poly1305 can satisfy your needs. It of couse depends on knowing the length of the message beforehand. $\endgroup$
    – DannyNiu
    May 28, 2021 at 12:07

1 Answer 1


First, authenticated encryptions based on universal MACs (UMACs) can have their tags computed from blocks of message in random order. This is because UMACs are often based on integer or binary polynomial addition and multiplication, which are associative and commutative operations. Based on this, AES-GCM and ChaCha20-Poly1305 may satisfy your needs.

For these algorithms, recomputing the hash state for 1 block requires some addition, multiplication, and exponentiation, where the exponentiation can be done using square-and-multiply approach.

Second, authenticated encryptions are supposed to operate on whole messages. From your description I sensibly believe this may be some type of XY problem, and you may need to disclose your application blueprint so that we may tell if better solutions to your ultimate problem exist.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.