Resumen
This paper proposes TSKT-oblivious RAM (ORAM), an efficient multi-server ORAM construction, to protect a client?s access pattern to outsourced data. TSKT-ORAM organizes each of the server storages as a k-ary tree and adopts XOR-based private information retrieval (PIR) and a novel delayed eviction technique to optimize both the data query and data eviction process. TSKT-ORAM is proven to protect the data access pattern privacy with a failure probability of 2-80
2
-
80
when system parameter ??=128
k
=
128
. Meanwhile, given a constant-size local storage, when N (i.e., the total number of outsourced data blocks) ranges from 216
2
16
?234
2
34
, the communication cost of TSKT-ORAM is only 22?46 data blocks. Asymptotic analysis and practical comparisons are conducted to show that TSKT-ORAM incurs lower communication cost, storage cost and access delay in practical scenarios than the compared state-of-the-art ORAM schemes.