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?