修士論文 要旨

マルチパーティ計算による Oblivious RAM のコスト削減と文字列検索の秘匿化への応用
数理情報学専攻 48-226203
指導教員

諌山 航太
定兼 邦彦 教授

JxKn を x の加法的シェアと呼ぶ

1 背景

2.2

マルチパーティ計算

Oblivious RAM (ORAM) はデータの所有者である

マルチパーティ計算 (MPC) は複数の計算者が通信をクライアントが外部サーバへデータを安全に委託する行いながら計算を実行することである．ここで各計算手法のである．ORAM によって外部サーバへアクセス者はそれぞれ秘密の入力を所持しており，計算の過程にパターンを秘匿したまま委託データへアクセスするこて入力に関する情報を他者に漏らさない．本研究ではとができ，クラウドサービスへの応用も期待されていパーティがサーバであり，サーバの入力は加法的シェアる．その一方，ORAM はクライアント・サーバ間の通として与えられる．

信コストの大きさが課題と言われている．特にマルチパーティ計算 (MPC) においては通信ラウンド数（通信回数）の削減が重要であり，ORAM においても同様で

3 本研究で扱う問題と成果
本研究ではツリーベース型のマルチサーバ ORAM のある．この解決策としてマルチサーバ ORAM が提案ラウンド数削減を含む，以下の 3 つの問題を扱う．

された [7]．マルチサーバ ORAM は，クライアントの3.1

ツリーベース型のマルチサーバ ORAM と処理を複数サーバによる MPC が肩代わりすることでDistributed ORAM (DORAM) のラウンド数削減

クライアント・サーバ間の通信コストを削減する．シン

ここでは 1 クライアントと 3 サーバ（正確には 2 サー

グルサーバの ORAM の複数の方式のうち，ツリーベーバと 1 ヘルパ）によるマルチサーバ ORAM を扱う．マス型と呼ばれる方式はプロトコルがシンプルであり，最ルチサーバ ORAM は以下の機能を実現する確率的な悪コストも他の方式と比べて実用性が高い．一方で最プロトコルである．

新のツリーベース型マルチサーバ ORAM [3] はサーバ間の 1 アクセスあたりの通信ラウンド数は O(log N ) を要する．そこで本研究では，ツリーベース型マルチサー
バ ORAM のサーバ間の通信ラウンド数の削減に取り組む．またその応用として，秘匿二分探索や秘匿パターンマッチングについても研究を行う．

いたマルチパーティ計算を利用する．本節では秘密分散法（特に加法的秘密分散法）とマルチパーティ計算を説明する．

ら，クライアントからの以下のクエリに応答する．

Access: サーバは (JopK, JaKN , JxKP ) をクライアント

位数 n の 2 パーティの加法的秘密分散法とは，以下の 2 つのプロトコルの組のことを言う．

xと更新する．
マルチサーバ ORAM の安全性は以下で定義される．
定義 2 (マルチサーバ ORAM の安全性（Informal）).
クライアントはクエリ (Jopi K, Jai KN , Jxi KP ) を任意の加法的秘密分散法∈Zn に 対 し て ，JxKn

回数呼び出す．この時，任意のサーバ S に対して，プロトコルの実行中にそのサーバ S が他の計算者から受け取るメッセージの分布が，クエリに依存しないとき，$←Ð{(x0 , x1 ) ∈ Z2n ∣ x0 + x1 = x} を出力する．ただし
JxKn = (JxKn0 , JxKn1 ) と記述する．
•Reconstn (JxKn ): JxKn を入力とし，JxKn0 + JxKn1 を出力する．

JvKP を委託する．サーバはヘルパの協力を受けながアントへ送信する．op = write の時は，Jv a KP ← JxKP

本研究の提案方式は 2 パーティの秘密分散法に基づ•Sharen (x):ントは 2 つのサーバにデータ v ∈ ZN
P の加法的シェアから受け取り，何らかの MPC を行って Jv a KP をクライ

2 準備

2.1

定義 1 (マルチサーバ ORAM (Informal)). クライア

ORAM プロトコルを安全と定める．
以下でツリーベース型フレームワークと，提案方式の概要とを示す．

マルチパーティ計算による Oblivious RAM のコスト削減と文字列検索の秘匿化への応用 (諌山 航太)

ツリーベース型 ORAM

3.2

3.5

サーバのデータ構造が完全二分木に基づく ORAM

ツリーベース型マルチサーバ ORAM に基づく秘匿二分探索のラウンド数削減を総称してツリーベース型 ORAM と呼ぶ．各データ単調増加列 JvK を共有する 2 パーティと 1 ヘルパをには二分木の葉が一様ランダムに一つ割り当てられて考える．秘匿二分探索では，パーティはクエリ JxK にいて，常にその葉へのパス上に存在する．例として図 1

対して v i ≤ x を満たす最大の Jv i K を計算する．前節のに提案方式のデータ構造を示す．

Evict を適用することで，既存方式 [4] の O(log2 N ) ラウンドを O(log N ) へと削減できる．

ポジションマップ
インデックス

葉番号

パス上の位置

0011162011329431052116110⊥

実ブロック3.6𝑣!
⊥ダミーブロック

⊥⊥

𝑍個𝑣"
⊥⽊の⾼さ
𝐻 = log 𝑁𝑣%𝑣$

0𝑣'𝑣&𝑣#

Leaf ID

新たな秘匿パターンマッチングプロトコル

⊥1

2

3

文字列 v ∈ ΣN を加法的シェアとして共有する 2 パー
ティと 1 ヘルパを考える．秘匿パターンマッチングでは，パーティはクエリ文字列 q ∈ ΣM の加法的シェアを入力として，t 中で q が出現する位置のシェアを全て求図 1. 提案方式のデータ構造．左側がクライアントのめる．本研究では Sadakane [6] の平文アルゴリズムをデータ構造であり，右側がサーバのデータ構造提案秘匿二分探索プロトコルを用いて秘匿化することである．

ツリーベース型 ORAM のアクセスの流れは以下の通りである: (1) 所望するデータのパスからデータを得る (ReadPath)，(2) 取得したデータを二分木の根に再で，秘匿パターンマッチングプロトコルを新たに構成した．既存方式 [5] にて検索時に消費される乱数のサイズを大幅に削減すると同時に，乱数の入力への依存を取り除くことに成功した．

格納する (WriteBack)，(3) パスを一つ選び，割り当て

参考文献

た葉に矛盾しないようにパス上の全データを下へ移動[1] N. Attrapadung, G. Hanaoka, T. Matsuda, H. Morita,K. Ohara, J. C. N. Schuldt, T. Teruya, and K. Tozawa.
Oblivious linear group actions and applications. InG. Vigna and E. Shi, editors, ACM CCS 2021, pages
630–650. ACM Press, Nov. 2021.
[2] N. Attrapadung, H. Morita, K. Ohara, J. C. N.
Schuldt, and K. Tozawa. Memory and round-eﬃcient
MPC primitives in the pre-processing model from unit
vectorization. In Y. Suga, K. Sakurai, X. Ding, andK. Sako, editors, ASIACCS 22, pages 858–872. ACMPress, May / June 2022.
[3] T. Hoang, A. A. Yavuz, and J. Guajardo. A multiserver oram framework with constant client bandwidth blowup. ACM Trans. Priv. Secur., 23(1):1–35,Feb. 2020.
[4] M. Keller and P. Scholl. Eﬃcient, oblivious data structures for MPC. In P. Sarkar and T. Iwata, editors,ASIACRYPT 2014, Part II, volume 8874 of LNCS,pages 506–525. Springer, Heidelberg, Dec. 2014.
[5] Y. Nakagawa, S. Ohata, and K. Shimizu. Eﬃcientprivacy-preserving variable-length substring matchfor genome sequence. AMB, 17(1):1–22, 2022.
[6] K. Sadakane. Compressed text databases with eﬃcient query algorithms based on the compressed sufﬁx array. In G. Goos, J. Hartmanis, J. Leeuwen,
D. T. Lee, and S.-H. Teng, editors, ISAAC 2000, volume 14369, pages 410–421. Springer, Heidelberg, Dec.
2000.
[7] E. Stefanov and E. Shi. Multi-cloud oblivious storage.
In A.-R. Sadeghi, V. D. Gligor, and M. Yung, editors,
ACM CCS 2013, pages 247–258. ACM Press, Nov.
2013.

させる．S3ORAM は逐次的な秘匿行列積によってデータを移動しており，O(log N ) ラウンドの通信が発生していた．

3.3

提案方式の概要

秘匿置換作用，秘匿ソート [1] や秘匿単位ベクトル化 [2] 等のプロトコルを用いて，Evict でのデータの移動を一括処理することでラウンド数を削減する．パス上のブロックのデータの移動を表す置換のシェアを秘匿ソートや秘匿単位ベクトルを用いて並列に計算する．
置換を秘匿置換作用でパスのデータ列に作用させ，データを一括移動させる．秘匿ソート [1] を用いる場合はO(log log N ) ラウンド，秘匿ソートを回避することでO(1) ラウンドの ORAM を構成できる．
3.4 Distributed ORAM (DORAM) への適用
クライアントが存在せず，アクセスするインデック
ス a を各サーバがシェアとして入力する ORAM をDORAM と呼ぶ．アクセス結果 v a も各サーバがシェアとして取得する．クライアントの平文計算が必要ないという性質から，前項で構成した Evict プロトコル
はツリーベース型 DORAM の Evict としても使用できる．これにより既存方式 [4] の O(log2 N ) ラウンドをO(log N ) に削減できる．