Authenticated Encryption Sheme with Random Access and proven security?

Question

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?

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.