cc 14(2): e3

Research Article

A Scheme for Collaboratively Processing Nearest Neighbor Queries in Oblivious Storage

Download612 downloads
  • @ARTICLE{10.4108/cc.1.2.e3,
        author={Keith B. Frikken and Shumiao Wang and Mikhail J. Atallah},
        title={A Scheme for Collaboratively Processing Nearest Neighbor Queries in Oblivious Storage},
        journal={EAI Endorsed Transactions on Collaborative Computing},
        volume={1},
        number={2},
        publisher={ICST},
        journal_a={CC},
        year={2014},
        month={10},
        keywords={Collaborative Cloud Storage, Oblivious Storage, Collaboration in Cloud Computing},
        doi={10.4108/cc.1.2.e3}
    }
    
  • Keith B. Frikken
    Shumiao Wang
    Mikhail J. Atallah
    Year: 2014
    A Scheme for Collaboratively Processing Nearest Neighbor Queries in Oblivious Storage
    CC
    ICST
    DOI: 10.4108/cc.1.2.e3
Keith B. Frikken1, Shumiao Wang2, Mikhail J. Atallah2,*
  • 1: Miami University, Oxford
  • 2: Purdue University, West Lafayette
*Contact email: mja@cs.purdue.edu

Abstract

Security concerns are a substantial impediment to the wider deployment of cloud storage. There are two main concerns on the confidentiality of outsourced data: i) protecting the data, and ii) protecting the access pattern (i.e., which data is being accessed). To mitigate these concerns, schemes for Oblivious Storage (OS) have been proposed. In OS, the data owner outsources a key-value store to a cloud server, and then can later execute get, put, and remove queries, by collaboration with the server; furthermore, both the data and the access pattern are hidden from the server. In this paper, we extend the semantics of OS by proposing an oblivious index that supports nearest neighbor queries. That is, finding the nearest keys to the query in the key-value store. Our proposed index structure for supporting nearest-neighbor has similar performance bounds to previous OS schemes that did not support nearest-neighbor, in terms of client storage, server storage and rounds of communication.