Parallelizable Authentication Trees

Eric Hall; Charanjit S.  Jutla

Paper 2002/190

Parallelizable Authentication Trees

Eric Hall and Charanjit S. Jutla

Abstract

We define a new authentication tree in the symmetric key setting, which has the same computational time, storage and security parameters as the well known Merkle authentication tree, but which unlike the latter, allows for all the cryptographic operations required for an update to be performed in parallel. The cryptographic operations required for verification can also be parallelized. In particular, we show a provably secure scheme for incremental MAC with partial authentication secure against substitution and replay attacks, which on total data of size $2^n$ blocks, and given $n$ cryptographic engines, can compute incremental macs and perform individual block authentication with a critical path of only one cryptographic operation

Metadata

Available format(s): PS
Publication info: Published elsewhere. Unknown where it was published
Contact author(s): csjutla @ watson ibm com
History: 2005-02-01: revised; 2002-12-17: received; See all versions
Short URL: https://ia.cr/2002/190
License: CC BY

BibTeX

@misc{cryptoeprint:2002/190,
      author = {Eric Hall and Charanjit S.  Jutla},
      title = {Parallelizable Authentication Trees},
      howpublished = {Cryptology ePrint Archive, Paper 2002/190},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/190}},
      url = {https://eprint.iacr.org/2002/190}
}