Succinct Random-Index ORAM

Oblivoius RAM (ORAM) はクライアントが信頼できないサーバへデータを預け，また適宜アクセスを可能にする技術であり，アクセスの際にデータのみならずアクセスパターンまでサーバへ秘匿できる特徴を持つ暗号プロトコルである．Random-Index ORAM (RORAM) はその ORAM の派生技術であり，クライアントはアクセス対象のデータを指定できない代わりに，データ構造中の何れかランダムなデータへアクセスを行うプロトコルである．特定のデータへのアクセスを保証する点でプログラム秘匿や暗号化データベースのような用途が期待される通常の ORAM とは異なり，ランダムにデータを参照する RORAM は大規模データに対するランダムサンプリングを交えた統計分析や大規模マルチパーティ計算への応用が期待されている．しかしながら，既存の RORAM は空間効率・時間効率ともに，通常の ORAM に比較しても大きなアドバンテージを得られていない課題がある．本研究では特に大規模データを志向して，空間効率に優れる RORAM を提案する．

Oblivoius RAM (ORAM) is a cryptographic protocol that allows a client to store data on an untrusted server and access it as needed, while keeping not only the data but also the access pattern secret from the server during access. Random-Index ORAM (RORAM) is a derivative of ORAM, a protocol in which the client cannot specify the data to be accessed, but instead accesses some random data in the data structure. Unlike ordinary ORAM, which is expected to be used for applications such as program protection and encrypted databases in that it guarantees access to specific data, RORAM, which refers to data at random, is expected to be used for statistical analysis with random sampling of large-scale data and large-scale secure multiparty computation. However, existing RORAMs do not have a significant advantage over conventional ORAMs in terms of both space and time complexity. We propose a RORAM with superior space complexity, especially for large-scale data.