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 -