TY - JOUR
T1 - Authenticated Hash Tables Based on Cryptographic Accumulators
AU - Papamanthou, Charalampos
AU - Tamassia, Roberto
AU - Triandopoulos, Nikos
N1 - Publisher Copyright:
© 2015, Springer Science+Business Media New York.
PY - 2016/2/1
Y1 - 2016/2/1
N2 - Suppose a client stores n elements in a hash table that is outsourced to an untrusted server. We address the problem of authenticating the hash table operations, where the goal is to design protocols capable of verifying the correctness of queries and updates performed by the server, thus ensuring the integrity of the remotely stored data across its entire update history. Solutions to this authentication problem allow the client to gain trust in the operations performed by a faulty or even malicious server that lies outside the administrative control of the client. We present two novel schemes that implement an authenticated hash table. An authenticated hash table exports the basic hash-table functionality for maintaining a dynamic set of elements, coupled with the ability to provide short cryptographic proofs that a given element is a member or not of the current set. By employing efficient algorithmic constructs and cryptographic accumulators as the core security primitive, our schemes provide constant proof size, constant verification time and sublinear query or update time, strictly improving upon previous approaches. Specifically, in our first scheme which is based on the RSA accumulator, the server is able to construct a (non-)membership proof in constant time and perform updates in (Formula Presented.) time for any fixed constant 0 < ϵ < 1. A variation of this scheme achieves a different trade-off, offering constant update time and O(nϵ) query time. Our second scheme uses an accumulator based on bilinear pairings to achieve O(nϵ) update time at the server while keeping all other complexities constant. A variation of this scheme achieves O(nϵlogn) time for queries and constant update time. An experimental evaluation of both solutions shows their practicality.
AB - Suppose a client stores n elements in a hash table that is outsourced to an untrusted server. We address the problem of authenticating the hash table operations, where the goal is to design protocols capable of verifying the correctness of queries and updates performed by the server, thus ensuring the integrity of the remotely stored data across its entire update history. Solutions to this authentication problem allow the client to gain trust in the operations performed by a faulty or even malicious server that lies outside the administrative control of the client. We present two novel schemes that implement an authenticated hash table. An authenticated hash table exports the basic hash-table functionality for maintaining a dynamic set of elements, coupled with the ability to provide short cryptographic proofs that a given element is a member or not of the current set. By employing efficient algorithmic constructs and cryptographic accumulators as the core security primitive, our schemes provide constant proof size, constant verification time and sublinear query or update time, strictly improving upon previous approaches. Specifically, in our first scheme which is based on the RSA accumulator, the server is able to construct a (non-)membership proof in constant time and perform updates in (Formula Presented.) time for any fixed constant 0 < ϵ < 1. A variation of this scheme achieves a different trade-off, offering constant update time and O(nϵ) query time. Our second scheme uses an accumulator based on bilinear pairings to achieve O(nϵ) update time at the server while keeping all other complexities constant. A variation of this scheme achieves O(nϵlogn) time for queries and constant update time. An experimental evaluation of both solutions shows their practicality.
KW - Authenticated data structures
KW - Cloud computing security
KW - Cryptographic accumulators
UR - http://www.scopus.com/inward/record.url?scp=84955699164&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84955699164&partnerID=8YFLogxK
U2 - 10.1007/s00453-014-9968-3
DO - 10.1007/s00453-014-9968-3
M3 - Article
AN - SCOPUS:84955699164
SN - 0178-4617
VL - 74
SP - 664
EP - 712
JO - Algorithmica (New York)
JF - Algorithmica (New York)
IS - 2
ER -