NewMCOS: Towards a Practical Multi-Cloud Oblivious Storage Scheme

摘要: Encryption alone is not enough to protect data privacy, because access pattern leaks some sensitive information. Oblivious RAM (ORAM), the solution this problem, still far from practical deployment for heavy storage and communication/ computation overhead. To reduce them, an insightful idea was proposed utilize non-colluding clouds shift client client-cloud communication clouds. The multi-cloud ORAM achieved $O$ O (1) bandwidth cost removed most of computation. In paper, we exploit “ disconnected operation ” design two-layer encryption further these overheads. Experiments show that our scheme, NewMCOS, significantly reduces evict cache size GB/MB KB level with about 2-3 times lower response time 20 percent savings in clouds, compared other schemes. Theoretically speaking, $O(\sqrt{N})$ ( N ) $O(ZK)$ Z K , where $N$ number real blocks, $K$ $2 2 ), $Z$ blocks uploaded eviction. By employing lazy eviction ”, write frequency reduced by $O(Z)$ shuffling $\Omega (Z\; \log Z)$ Ω log . Meanwhile, NewMCOS proved be secure.