TY - CHAP
T1 - Optimal Authenticated Data Structures with Multilinear Forms
T2 - Pairing-Based Cryptography - Pairing 2010
Y1 - 2010
A1 - Charalampos Papamanthou
A1 - Tamassia, Roberto
A1 - Triandopoulos, Nikos
ED - Joye, Marc
ED - Miyaji, Atsuko
ED - Otsuka, Akira
KW - Algorithm Analysis and Problem Complexity
KW - authenticated dictionary
KW - Coding and Information Theory
KW - Computer Communication Networks
KW - Data Encryption
KW - Discrete Mathematics in Computer Science
KW - multilinear forms
KW - Systems and Data Security
AB - 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.
JA - Pairing-Based Cryptography - Pairing 2010
T3 - Lecture Notes in Computer Science
PB - Springer Berlin Heidelberg
SN - 978-3-642-17454-4, 978-3-642-17455-1
UR - http://link.springer.com/chapter/10.1007/978-3-642-17455-1_16
ER -