Skip to Main content Skip to Navigation
Conference papers

Analysis and Improvement of an Authentication Scheme in Incremental Cryptography

Abstract : Introduced in cryptography by Bellare, Goldreich and Goldwasser in 1994, incrementality is an attractive feature that enables to update efficiently a cryptographic output like a ciphertext, a signature or an authentication tag after modifying the corresponding input. This property is very valuable in large scale systems where gigabytes of data are continuously processed (e.g. in cloud storage). Adding cryptographic operations on such systems can decrease dramatically their performance and incrementality is an interesting solution to have security at a reduced cost. We focus on the so-called XOR-scheme, the first incremental authentication construction proposed by Bellare, Goldreich and Goldwasser, and the only strongly incremental scheme (i.e. incremental regarding insert and delete update operations at any position in a document). Surprisingly, we found a simple attack on this construction that breaks the basic security claimed by the authors in 1994 with only one authentication query (not necessarily chosen). Our analysis gives different ways to fix the scheme; some of these patches are discussed in this paper and we provide a security proof for one of them.
Document type :
Conference papers
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Damien Vergnaud Connect in order to contact the contributor
Submitted on : Thursday, May 7, 2020 - 8:54:29 PM
Last modification on : Wednesday, June 8, 2022 - 12:50:03 PM


Files produced by the author(s)



Louiza Khati, Damien Vergnaud. Analysis and Improvement of an Authentication Scheme in Incremental Cryptography. SAC 2018 - 25th International Conference on Selected Areas in Cryptography, Aug 2018, Calgary, Canada. pp.50-70, ⟨10.1007/978-3-030-10970-7_3⟩. ⟨hal-01893905⟩



Record views


Files downloads