Optimal Data Authentication from Directed Transitive Signatures

Philippe Camacho

Paper 2011/439

Optimal Data Authentication from Directed Transitive Signatures

Philippe Camacho

Abstract

An authenticated dictionary of size $N$ is said to be optimal when an update operation or proof computation requires at most $O (\log N)$ accesses to the data-structure, and the size of a proof is $O (1)$ with respect to $N$ . In this note we show that an optimal authenticated dictionary (OAD) can be built using transitive signatures for directed graphs (DTS). As the existence of DTS and OAD are both still open, our result can be interpreted as following: if optimal authenticated dictionaries do not exist then transitive signatures for directed graphs do not exist either.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Unknown where it was published
Keywords: transitive signatures authenticated data structures
Contact author(s): philippe camacho @ gmail com
History: 2011-08-15: received
Short URL: https://ia.cr/2011/439
License: CC BY

BibTeX

@misc{cryptoeprint:2011/439,
      author = {Philippe Camacho},
      title = {Optimal Data Authentication from Directed Transitive Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/439},
      year = {2011},
      url = {https://eprint.iacr.org/2011/439}
}