不明瞭なデータ構造

コンピュータサイエンスにおいて、忘却データ構造とは、操作の最終結果を除いて、適用された操作の順序やパターンに関する情報を一切提供しないデータ構造のことである。^[1]

多くの場合、データが暗号化されていてもアクセスパターンは達成可能であり、このパターンによって暗号鍵などの重要な情報が漏洩する可能性があります。クラウドデータのアウトソーシングにおいては、このアクセスパターンの漏洩は依然として非常に深刻です。アクセスパターンとは、リレーションスキーマの各属性に対するアクセスモードの仕様です。例えば、ユーザーがクラウド上のデータを読み書きするシーケンスがアクセスパターンです。

実行時間が同じである任意の2つの入力に対して、アクセス順序が等しい場合、そのマシンは無知であると言います。つまり、データアクセスパターンは入力に依存しません。

アプリケーション：

• クラウドデータアウトソーシング：クラウドサーバーからデータを読み書きする場合、忘却型データ構造が役立ちます。また、現代のデータベースはデータ構造に大きく依存しているため、忘却型データ構造が役立ちます
• セキュアプロセッサ：耐タンパー性を備えたセキュアプロセッサは、物理的な攻撃や悪意のある侵入者によるユーザーのコンピュータプラットフォームへのアクセスに対する防御に使用されます。学界や産業界で設計された既存のセキュアプロセッサには、AEGISやIntel SGXなどがあります。しかし、メモリアドレスは依然としてメモリバス上で平文で転送されます。そのため、このメモリバスから暗号鍵に関する情報が漏洩する可能性があることが明らかになっています。Obliviousデータ構造の実用化により、セキュアプロセッサはメモリアクセスパターンを証明可能な安全性で難読化できます。
• セキュアコンピューティング：従来、セキュアコンピューティングには回路モデルが使用されていましたが、データ量が多くなると、このモデルではセキュリティが不十分になります。そこで、従来の回路モデルの代替としてRAMモデルのセキュアコンピューティングが提案され、情報アクセス動作の盗難を防ぐために忘却型データ構造が使用されています。

忘却型データ構造

忘却型RAM

Goldreich と Ostrovsky がソフトウェア保護に関するこの用語を提案しました。

忘却型RAMのメモリアクセスは確率的であり、その確率分布は入力に依存しません。GoldreichとOstrovskyによる論文では、忘却型RAMに関する定理が示されています。RAM ( m )は、m個のメモリロケーションとランダムオラクルマシンへのアクセスを持つRAMを表します。任意のRAM( m )プログラムのtステップは、忘却型RAMの⁠ ⁠${\displaystyle O(t(\log_{2}t)^{3})}$ ステップ未満でシミュレートできます。RAM ( m )のすべての忘却型シミュレーションは、tステップをシミュレートするために 少なくともアクセスを行う必要があります。${\displaystyle \mathrm {RAM} (m(\log _{2}m)^{2})}$ ${\displaystyle \max\{m,(t-1)\log _{2}m\}}$

これで、忘却 RAM の動作をシミュレートする平方根アルゴリズムができました。

1. アクセスごとに、最初のメモリをランダムに並べ替えます。${\displaystyle {\sqrt {m}}}$ ${\displaystyle m+{\sqrt {m}}}$
2. 単語にアクセスする場合は、まずシェルター単語を確認してください。
3. 単語が存在する場合は、ダミー単語の1つにアクセスします。存在しない場合は、順序が入れ替わった位置を探します。

元のRAMにtステップでアクセスするには、oblivious RAMのステップでシミュレートする必要があります 。各アクセスのコストはO( )です。 ${\displaystyle t+{\sqrt {m}}}$ ${\displaystyle {\sqrt {m}}\cdot \log m}$

もう一つのシミュレーション方法は階層的アルゴリズムです。基本的な考え方は、シェルターメモリをバッファと見なし、それを複数レベルのバッファに拡張することです。レベルIにはバケット${\displaystyle 4^{i}}$ があり、各バケットにはlog t個のアイテムが含まれます。各レベルには、ランダムに選択されたハッシュ関数があります。

操作は次のようになります。まず、プログラムを最後のレベル（バケット${\displaystyle 4^{t}}$ があると言える）にロードします。読み取りの場合、各レベルからバケットをチェックします。(${\displaystyle h_{i}(V)}$ V,X) がすでに見つかった場合は、アクセスするバケットをランダムに選択し、見つからない場合はバケットをチェックします。実際に一致${\displaystyle h_{i}(V)}$ するのは 1 つだけで、残りはダミーエントリです。書き込みの場合、(V,X) を最初のレベルに配置し、最初の I レベルがいっぱいの場合は、すべての I レベルを⁠ ⁠${\displaystyle I+1}$ レベルに移動し、最初の I レベルを空にします。

各レベルの時間コストはO (log t) です。アクセスごとのコストは⁠ ⁠${\displaystyle O((\log t)^{2})}$ です。ハッシュのコストは⁠ ⁠${\displaystyle O(t(\log t)^{3})}$ です。

忘却の木

忘却の木とは、以下の性質を持つ根付き木です。

• すべての葉は同じ高さにあります
• すべての内部ノードの次数は最大 3 です。
• ツリー内の右端のパスに沿ったノードのみが次数 1 を持つことができます。

忘却木は2-3木に似たデータ構造ですが、忘却性（oblivious ）という特性が追加されています。右端のパスは次数1を持つ場合があり、これは更新アルゴリズムを記述するのに役立ちます。忘却木では、更新操作の実行時間を確保するためにランダム化が必要です。${\displaystyle O(\log(n))}$ また、木に作用する2つの操作シーケンスMとNに対して、木の出力は同じ出力確率分布を持ちます。この木には、3つの操作があります。

CREATE (L)

値のシーケンス L をその葉に格納する新しいツリーを構築します。

INSERT (b, i,T)

ツリーTのi^番目のリーフとして値bを格納する新しいリーフノードを挿入します。

DELETE (i, T)

Tからi^{番目の葉を削除します。}

作成手順:レベル i+1 のノードのリストを左から右に走査し、次の操作を繰り返して、レベル i のノードのリストを取得します ^。

1. d {2, 3}を均一にランダムに選択します。
2. レベル i+1 に残っているノードが d 個未満の場合、d を残っているノードの数と等しく設定します。
3. レベル I に新しいノード n を作成し、レベル i+1 の次の d 個のノードを子として、n のサイズをその子のサイズの合計として計算します。

   

   忘却の木

例えば、d {2, 3}のコイン投げの結果が2、3、2、2、2、2、3の場合、文字列「OBLIVION」は忘却の木として次のように保存されます

INSERT (b, I, T)と はどちらもO (log n ) の期待実行時間をDELETE(I, T)持ちます。また、とについて は次の式が成り立ちます。 INSERTDELETE

INSERT (b, I, CREATE (L)) = CREATE (L [1] + …….., L[ i], b, L[i+1]……..)
削除 (I, 作成 (L)) = 作成 (L[1]+ ………L[I - 1], L[i+1], ………..)

たとえば、CREATE (ABCDEFG)またはINSERT (C, 2, CREATE (ABDEFG))を実行すると、これら 2 つの演算の結果の確率は同じになります。

参考文献

1. Wang, Xiao; Nayak, Kartik; Liu, Chang; Chan, Hubert; Shi, Elaine ; Stefanov, Emil; Huang, Yan (2014年11月). 「Oblivious Data Structures」. CCS '14: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security . Scottsdale, Arizona . pp.  215– 226. doi : 10.1145/2660267.2660314 .

• ミッチアンチョ, ダニエレ (1997年5月). 「オブリビアスデータ構造：暗号への応用」. STOC '97: 第29回ACMコンピューティング理論シンポジウム議事録.コンピューティング理論シンポジウム.テキサス州エルパソ. pp.  456– 464. doi : 10.1145/258533.258638 .
• Goldreich, Oded ; Ostrovsky, Rafail (1996年5月). 「oblivious RAMにおけるソフトウェア保護とシミュレーション」Journal of the ACM . 43 (3). Association for Computing Machinery : 431– 473. doi : 10.1145/233551.233553 .
• ミッチェル, ジョン・C. ;ジマーマン, ジョー (2014年3月). 「データ忘却型データ構造」.第31回国際コンピュータサイエンス理論シンポジウム.フランス、リヨン. pp.  554– 565. doi : 10.4230/LIPIcs.STACS.2014.554 .
• Gentry, Craig ; Goldman, Kenny A.; Halevi, Shai; Jutla, Charanjit S.; Raykova, Mariana; Wichs, Daniel (2013年7月). 「ORAMの最適化とセキュアコンピューティングにおける効率的な利用」.第13回国際シンポジウム, PETS 2013.プライバシー強化技術シンポジウム.ブルーミントン, インディアナ州. doi : 10.1007/978-3-642-39077-7_1 .