Analysis and Improvement of an Authentication Scheme in Incremental Cryptography

Louiza Khati (1, 2, 3) , Damien Vergnaud (4, 5)

1 DI-ENS - Département d'informatique - ENS Paris
2 PSL - Université Paris sciences et lettres
3 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
4 IUF - Institut universitaire de France
5 ALMASTY - ALgorithms for coMmunicAtion SecuriTY

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.

Domaines: Cryptographie et sécurité [cs.CR]

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⟩