Optimal authenticated data structures with multilinear forms

Charalampos Papamanthou, Roberto Tamassia, Nikos Triandopoulos

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

27 Scopus citations

Abstract

Cloud computing and cloud storage are becoming increasingly prevalent. In this paradigm, clients outsource their data and computations to third-party service providers. Data integrity in the cloud therefore becomes an important factor for the functionality of these web services.Authenticated data structures, implemented with various cryptographic primitives, have been widely studied as a means of providing efficient solutions to data integrity problems (e.g., Merkle trees). In this paper, we introduce a new authenticated dictionary data structure that employs multilinear forms, a cryptographic primitive proposed by Silverberg and Boneh in 2003 [10], the construction of which, however, remains an open problem to date. Our authenticated dictionary is optimal, that is, it does not add any extra asymptotic cost to the plain dictionary data structure, yielding proofs of constant size, i.e., asymptotically equal to the size of the answer, while maintaining other relevant complexities logarithmic. Instead, solutions based on cryptographic hashing (e.g., Merkle trees) require proofs of logarithmic size [40]. Because multilinear forms are not known to exist yet, our result can be viewed from a different angle: if one could prove that optimal authenticated dictionaries cannot exist in the computational model, irrespectively of cryptographic primitives, then our solution would imply that cryptographically interesting multilinear form generators cannot exist as well (i.e., it can be viewed as a reduction). Thus, we provide an alternative avenue towards proving the nonexistence of multilinear form generators in the context of general lower bounds for authenticated data structures [40] and for memory checking [18], a model similar to the authenticated data structures model.

Original languageEnglish
Title of host publicationPairing-Based Cryptography, Pairing 2010 - 4th International Conference, Proceedings
Pages246-264
Number of pages19
DOIs
StatePublished - 2010
Event4th International Conference on Pairing-Based Cryptography, Pairing 2010 - Kaga, Japan
Duration: 13 Dec 201015 Dec 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6487 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th International Conference on Pairing-Based Cryptography, Pairing 2010
Country/TerritoryJapan
CityKaga
Period13/12/1015/12/10

Keywords

  • authenticated dictionary
  • multilinear forms

Fingerprint

Dive into the research topics of 'Optimal authenticated data structures with multilinear forms'. Together they form a unique fingerprint.

Cite this