International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Parallelizable Authentication Trees

Authors:
Eric Hall
Charanjit S. Jutla
Download:
URL: http://eprint.iacr.org/2002/190
Search ePrint
Search Google
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
BibTeX
@misc{eprint-2002-11713,
  title={Parallelizable Authentication Trees},
  booktitle={IACR Eprint archive},
  keywords={incremental authentication encryption block cipher parallelizable Merkle tree},
  url={http://eprint.iacr.org/2002/190},
  note={ csjutla@watson.ibm.com 12815 received 12 Dec 2002, last revised 1 Feb 2005},
  author={Eric Hall and Charanjit S. Jutla},
  year=2002
}