DEIM Forum 2017 A4-4

LOUDS と準同型暗号による秘匿決定木評価
須藤 弘貴†

清水 佳奈†† 早稲田大学基幹理工学部情報理工学科 〒 169–8555 東京都新宿区大久保３–４–１
E-mail: †hsudo108@ruri.waseda.jp, ††shimizu.kana@waseda.jp
あらまし

ビッグデータ解析で得られた知見をエンドユーザーが利用できる機械学習サービスの提供が普及し始める

一方で，学習済み分類器の公開による機密情報漏えいの危険性が指摘されており，システムを安全に運用するための技術開発が急務となっている．このような背景を鑑み，本研究ではユーザーのデータとサーバーのモデルを互いに明かすことなく，決定木による分類結果を計算する秘匿計算技術を提案する．決定木の分類結果を秘匿計算する従来研究として，計算量が木の高さの指数オーダーとなる手法が知られている．提案手法では木の簡潔データ構造である

LOUDS と紛失通信と呼ばれる暗号技術を効果的に組み合わせることにより，木の高さに線形な計算量を実現した．
キーワード 準同型暗号, 秘匿計算, LOUDS, プライバシー保護, 機械学習, 決定木

1. 序

論

秘密にしたまま，サーバーの持つ分類器を用いて分類結果を計算し，ユーザーだけがその結果を得ることのできる秘匿計算技

本研究の背景と目的： ビッグデータの解析結果をエンドユーザ

術の開発を目的とする．より具体的には，本研究で用いる分類が利用できるシステムが普及しつつある．特に，機械学習を用

器を決定木と定め，以下の要件を満たす二者間秘匿計算プロト

いたシステムは実社会でサービス化され始めており [10, 2]，大コルの開発を行う．図 1 は下記要件の模式図である．

きな注目を集めている．このようなサービスの一つとして次のようなシナリオが想定される．企業などのデータ解析拠点（あるいは個人）が独自に収集したデータを用いて分類器の学習を行った後，学習済みの分類器を web 上で API を通じて利用可能にする．サービスの利用者は，自身のデータを API 経由で分類器に入力し，予測結果を得ることができる．例えば，遺伝子要件 1. サーバーは学習済みの決定木 T （木構造，及び各ノードで定めるパラメータの集合）を持つ．ユーザーは決定木に対する入力 x を持つ．ユーザーは x をサーバーに知らせることな
く，決定木 T による分類結果を得る．ユーザーは分類結果以外の情報を得ず，サーバーは x に関するいかなる情報も得ない．

診断企業 A が多数の患者のゲノム情報をもとに疾患の診断を

決定木は予測根拠の説明が容易な性質を持つことから実社会行う分類器の学習を行ったとする．利用者 B は A の提供するでの利用と親和性が高く，医療診断やマーケティングなどで広分類器に対して，自身のゲノム情報を入力することにより，将く普及している．そのため本提案手法により，利用者とデータ

来の疾患リスクの予測を行うことができる．

提供者双方のプライバシーを損なうことなく，医療機関や企業

こういったサービスでは多くの利用者が容易にビッグデー
タの恩恵にあずかれるという利点があるものの，セキュリティなどのデータ収集拠点において得られた知見を速やかに社会に還元できることが期待できる．

リスクという重大な問題がある．前述の遺伝子診断の例では，サービスに用いられるクエリ（ゲノム情報）には利用者のプラ

サーバー

ユーザー

イバシ情報が含まれるため，利用者のプライバシリスクがある．
ユーザーの入力

一方で，クエリの送信をせずに分類器を利用可能にするには，分類器自体を公開する必要性が生じるが，このような措置には別のリスクがある．例えば，分類器の学習に用いる訓練データにはゲノムのようなデータ提供者の個人情報の他，企業がコストをかけて収集したノウハウが含まれるが，最近の研究 [8] に学習済み決定木#

ユーザーの情報• 遺伝情報
• 体質
• 年齢
• 性別
Etc…

秘匿計算
分類結果

1
疾患
なし

おいて，学習済みの分類器から訓練データに関する情報が漏洩する危険性が指摘されている．また，分類サービスの提供によ0𝑥0 < 𝑡02

𝑥1 < 𝑡1

3

4

疾患
あり

疾患
なし

図 1: 提案手法の問題設定．

り収益を上げることを想定した場合は，学習器自体の公開はビジネスモデルとして適さない．上記に述べたセキュリティの問本研究の貢献： 秘匿計算とは単一の技術を指すものではなく，題を解決するために，学習器に集約されたビッグデータの解析

データの中身を秘匿したまま情報解析を行う技術の総称であ

結果を安全に活用するための技術開発が急務となっている．

る．秘匿計算の実現には様々な方法が提案されているが，汎用

このような問題の解決には，データの中身を秘匿したまま情性と計算性能を両立する手法の開発は極めて困難である．例え

報解析を行う秘匿計算の応用が効果的であると考えられる．そば Garbled Circuit や完全準同型暗号は，理論上ではいかなるこで本研究では，ユーザーがクエリの中身をサーバーに対して演算も秘匿化したまま計算することが可能とされているが，実際には膨大な計算コストを要する．そのため，秘匿計算技術を開発する際には，アプリケーションに応じて計算の内容をよく

3. 準

備

精査し，重いコストが必要となる暗号計算を最小限にとどめる

本節では，提案手法の説明に用いる記法や定義，要素技術，

ように工夫を凝らしたアルゴリズムを個別に設計する必要があ

セキュリティモデルについて説明する．個々の要素技術の説明

る．関連研究との詳細な比較は次節以降にて述べるが，本研究に移る前に，提案手法の概要と必要な要素技術について述べる．

では以下の技術的工夫により，安全性を損なうことなく，従来提案手法では決定木の出力を得るために必要な計算を大きく二手法よりも計算性能及び汎用性に優れた手法を開発した．

つに分ける．(1) ユーザーの持つ属性値とサーバーの持つ決定（ 1 ） 決定木の木構造を LOUDS と呼ばれる簡潔データ構造

木から，各節点で選択される枝を決定する計算と，(2) 枝の選で表現し，木の走査に必要な計算を大幅に効率化した．
（4. 4 節択に基づき木構造を順次辿り，葉に関連付けられた値を出力すにて詳細を述べる）

る計算である．提案手法では加法準同型暗号を両者においてプ（ 2 ） 決定木の各ノードで行われる分岐判定は暗号化されライバシー保護の最も基礎となる暗号技術として用いる．選択

たまま行われる．この判定結果を復号することなく，枝の選される枝の決定には量的変数の場合，属性値と閾値との比較が択を行うことのできる新しい暗号技術「eROT」を開発した．

必要である．そのため，お互いの機密情報を漏洩せずに比較を（4. 3. 3 節にて詳細を述べる）

行うために加法準同型暗号を用いた二者間の比較プロトコルをd

従来手法では決定木の高さ d に対して O(2 ) の計算量が必使用する．木構造の走査においては，高さに線形なオーダーを要であったのに対し，提案手法は d に線形な計算量のみが必要実現するために LOUDS の性質を利用し，紛失通信と呼ばれとなる．4. 5 節にて計算量の理論的な議論を行い，5. 節の実験

る暗号技術と組み合わせる．

にて実際の計算量と理論性能がよく一致することを示す．また，

3. 1 基本的な記法

提案手法は木構造を自由に走査することが可能なため，決定木

本稿ではベクトル v を (v0 , . . . , vn ) のように表記する．また，のみに特化して設計された従来手法とは異なり，木による検索

v の i 番目の要素を v[i] と表記する．{a0 , . . . , an } は集合を表など多様な応用も検討可能な汎用性を持つ.

す表記とする．{ai }ni=0 は {a0 , . . . , an } と同じ集合を示す．さ2. 関 連 研 究
決定木による分類結果を計算する二者間秘匿計算プロトコ

らに，ベクトルの「循環」操作を定義する．本稿では n 次元ベ
クトル v について，各要素が v̂[(i + r)mod n ] = v[i] であるベク
トル v̂ を「ベクトル v を r 循環」したベクトルとする．

ルはこれまでにいくつか提案されている．Brickell らの手法

3. 2 加法準同型暗号(2007) [4] と Barni らの手法 (2009) [1] はともに加法準同型

加法準同型暗号とは，暗号化したままで二つの暗号文同士の暗号と Yao’s grabled circuit を組合わせた手法である．一方，加算を行うことのできる性質を持つ暗号方式である．本稿ではBost ら (2014) [3] は SWHE を用いる手法を提案した．[3] の

このような性質を持つ公開鍵暗号方式の使用を想定する．例と手法は決定木を決定変数の多項式として扱い，SWHE を用いてしては lifted-Elgamal 暗号 [5] などが知られている．

これを計算し決定木を評価する．これらの手法は計算量・通信

公開鍵暗号方式は次の 3 つのアルゴリズムを備えている．

量の面でコストが大きいという問題があった．より実用的な計（ 1 ） KeyGen: 公開鍵と秘密鍵のペア (pk, sk) を出力する．

算時間，通信量を実現した手法として Wu らの手法 (2016) [14]（ 2 ） Enc(m): 公開鍵 pk を用いて平文 m を暗号化し，暗号が挙げられる．[14] は加法準同型暗号を用いるアプローチを文 [[m]] を出力する．

採る．[14] では，木の構造を完全二分木に制約し，各節点の分（ 3 ） Dec([[m]]): 秘密鍵 sk を用いて暗号文 [[m]] を復号し，類規則を表現したビット列を暗号技術に適用する手法が提案さ平文 m を出力する．

れている．しかし，このような方法で分類規則を表現すると，[[m]] は平文 m の暗号文を表す記法である．また，本稿では，平ビット列のパターンが木の高さに対して指数的に増加し，計算

文ベクトル v の各要素を暗号化したベクトルも [[v]] のように略量・通信量が指数時間となる問題があった．これに対し，提案記する場合がある．

手法は高さに対して線形なオーダーであり，決定木の高さが高これらのアルゴリズムに加え，加法準同型暗号では暗号文上い場合の効率化を実現した．[14] が性能的に最も実用的であるでの演算により，2 つの暗号文の表す平文同士の加算，暗号文

ことから，6. 節では提案手法とのオーダーにおける比較を行う．

の平文の定数倍を計算することが可能である．本稿ではそれぞ提案手法の採る効率的なデータ構造と暗号技術を組合わせる

れに次のような記法を用いる．

アプローチは清水らの手法 (2016) [12] の流れを汲むものであ•

暗号文同士の加算: [[m1 + m2 ]] = [[m1 ]] ⊕ [[m2 ]]る．[12] は PBWT というデータ構造と暗号技術を組合わせる•

暗号文の定数倍: [[k · m]] = k ⊗ [[m]]ことにより効率的に文字列検索を行う手法を提案した．[12] では再帰的にアクセス可能なデータ構造と暗号技術を組合わせる
手法 (ROT) が提案され，これを用いることにより PBWT とただし，m, m1 , m2 は平文 (整数)，k は整数定数である．
演算 ⊗ は演算 ⊕ を繰り返すことにより実現できる．暗号文の符号反転については ⊖[[m]] と表記する．

暗号技術の組み合わせを実現した．提案手法は ROT と本稿で

本稿では用いる暗号方式が強秘匿性を有することを前提とし提案する ROT の拡張技術 (eROT) を LOUDS と組合わせる．

て議論を行う．強秘匿性とは暗号文から平文の情報を何も得ら

これにより，効率的に決定木の分類結果を秘匿計算する．

れないような性質である．

3. 3 紛 失 通 信

以降では簡単のため，式 (1) の第一項を SelRan(B, p) と記述

紛失通信 (OT) はユーザー・サーバ間で行われる二者間暗号する．p′ は SelRan(B, p) と子の順序を表す x（以降，オフセッ

プロトコルの一種である．1-out-of-n OT では，サーバーが持トと呼称する）の加算により算出される．ここで注意すべきつ n 個の要素からなるベクトル v から，ユーザーが要素のイン

は，SelRan(B, p) は全ての p ∈ {i | i ∈ {0, . . . , 2N }, B[i] = 0}

デックス t ∈ {0, . . . , n − 1} 番目を指定して v[t] を受信するこに 対 し て 事 前 計 算 可 能 だ と い う 点 で あ る ．提 案 手 法 で は ，とができる．この時，ユーザーが指定した t はサーバーに知ら

SelRan(B, p) の事前計算結果をベクトル v に保存し（以降れず，ユーザーはサーバーの他の要素を知ることはない．

では SelRan ベクトルと呼称する），1-out-of-n OT により必要

1-out-of-n OT は加法準同型暗号により実装できる．ここで，二つの操作を定義する．

•

PrepQuery(t)： t 番目の要素のみが 1 でそれ以外の要素

が 0 である長さ n のベクトル q(クエリベクトル) を用意し，各要素を暗号化したベクトル [[q]] を返す．

•

な情報を取得する．式 (1) を計算するためには v から取得した
値に x を加算する必要があるが，この操作の実現には 4. 4 節で説明するオフセットベクトルと再帰的紛失通信を用いる．
ところで，ビット列 B にはビット’1’ も含まれており，B[p] = 1の場合についても適切な事前計算が必要となる．式 (1) により

InnerProduct(v, [[q]])： 長さが n の平文ベクトル v と暗子の位置を計算すると，位置 p に対応する節点が葉である場合，

号文ベクトル [[q]] について，内積 v · q の暗号文を計算する．

B[p′ ] = 1 となる（p′ も到達した葉に対応する位置）．提案手法

1-out-of-n OT は上記の操作を用いて次のように実行される．

では決定木の根から葉まで辿るために，親から子へ移動する操（ 1 ） ユーザーは PrepQuery(t) を実行し，[[q]] をサーバーに作を必ず木の高さ d 回再帰的に行う (詳細は 4. 4 節). よって，送信する．

途中で葉に到達し B[p] = 1 である場合にも式 (1) に相当する（ 2 ） サーバーは InnerProduct(v, [[q]]) = [[v[t]]] を実行し，計算が必要となる．そこで便宜上，B[p] = 1 となる位置 p に対結果をユーザーに送る．

しては v[p] = p とする．

（ 3 ） ユーザーは Dec([[v[t]]]) を計算し，v[t] を得る．

上述のように、節点は二種類のビットにより表現されるが、この時，サーバーはユーザーから送られたクエリを復号することはできないので，クエリが何番目を指定しているのかを知ることはできない．一方，0 との乗算により v[t] 以外の要素の情報は失われるため，ユーザーは v[t] 以外の v の要素の情報を得ることはできない．

以降では、B[p] = 0 となるビットを 0 ベース表現、B[p] = 1となるビットを 1 ベース表現と呼称する．

3. 5 決 定 木
決定木は機械学習モデルの一種である．本稿で扱う決定木を
以下のように定める．

3. 4 LOUDS•

決定木の木構造は多分木かつ順序木であるとする．

LOUDS [9, 15] は木の簡潔データ構造の一つであり，情報•決定木の各内部節点にはそれぞれ入力に対しどの枝を選理論的下限に近いデータサイズを実現しつつも木の走査が可能

択するかを返す分岐関数が対応付けられている．

•

な優れたデータ構造である．
本稿では LOUDS 表現の詳細については割愛し，決定木の計算で現れる，親から子への移動に必要な計算に絞って説明する．

n 次元の入力ベクトル x が与えられると，各内部節点に対応付けられた分岐関数に従い根から葉までを辿り到達した葉l に対応する値 zl を返す．ただし，x ∈ Zn , zl ∈ Z．

LOUDS では木構造を長さ 2N + 1 のビット列 B で表現する．

⟨P (x)⟩ を論理式 P (x) が成り立つとき 1，それ以外の時に 0 を

木の各節点は B 上の二つのビットにより 0 と 1 の二通りで表を一意に表現する．つまり，木構造上での親から子への移動は表す記法とする．各内部節点 j の分岐関数 Choose(X ; t0 , . . . , tu )∑は，入力値 X ，u 個の閾値 tk (tk ∈ Z) について (⟨tk <= X ⟩)+1を返す関数である．入力値，閾値のビット長を ℓ とする．入力

B 上での位置の移動に対応する．以上を踏まえ，以下にビット

値，閾値については固定小数点表現を用いることにより実数値

列 B に対する二つの操作を定義する．

に拡張することができる．この場合，ℓ は固定小数点表現の精現される．したがって，B 上の位置 p は，木のいずれかの節点度とみなすことができる．

定義 1. ビット列に対する操作•

Rankb (B, p)：ビット 列 B の 位 置 p ま で に 含 ま れ る

b ∈ {0, 1} の数を返す．
•

Selectb (B, i)：ビット列 B の i 番目の b ∈ {0, 1} の B 上の位置を返す．

3. 6 SelRan ベクトルによる決定木の表現
決定木の木構造は SelRan ベクトルにより表現することができる．提案手法では，決定木の表現に SelRan ベクトルと追加の 3 つの補助データ構造を用いる．以降では決定木を表現する上で必要な 3 つの補助データ構造 (1) 閾値行列 Θ，(2) 節点情

親から子への移動は上述した二つの操作により実現すること

報ベクトル L，(3) 出力値ベクトル z について順に説明する．

ができる．ひとまずここでは B 上のビット’0’ で表現された位（ 1 ） 閾値行列 Θ： B[p] = 0 となる p 番目の列ベクトルの置について注目する．まず，B 上の位置 p が与えられたとする．

みに閾値のベクトルを格納する tmax × (2N + 1) の行列．(tmax

この時，B[p] = 0 ならば，p に対応する節点の x 番目の子を示

は閾値の数の上限)′′

す位置 p （B[p ] = 0）は，次の式で計算することができる．

p′ = Select1 (B, Rank0 (B, p) + 1) + x（ 2 ） 節点情報ベクトル L： LOUDS の各位置に，位置の種類を格納した長さ 2N + 1 のベクトル．位置の種類とは LOUDS(1)

上の位置が 1 ベース表現，葉の 0 ベース表現，内部節点の 0ベース表現のいずれに対応するものであるかを区別するものである．3 つの種類には次のように識別子を振ることとする． (i)1
ベース表現：ONEBASE (ii) 葉の 0 ベース表現：LEAF (iii) 内

ユーザー

サーバー

鍵交換

(𝒔𝒌, 𝒑𝒌)

𝒑𝒌

決定木𝑻
モデル𝑇

入力ベクトル𝒙

部節点の 0 ベース表現：INTERNAL．

閾値行列比較フェーズ（ 3 ） 出力値ベクトル z： 各葉に対応する出力値を葉に対応

オフセット
ベクトル

する 1 ベース表現の位置に格納した長さ 2N + 1 のベクトル．
ただし，それ以外の位置には出力値の取りうる値の範囲内のラ

𝑻(𝒙)
𝑇(𝑥)

評価フェーズ

ンダムな値を格納する．
また，Θ[i][j] は LOUDS 上で i 番地の節点の j 番目の閾値である．これら決定木を表現するデータ構造を T と総称する．また，T に入力ベクトル x を与え出力値 zl を返すことを T (x) = zlと表記する．

3. 7 セキュリティモデル
本稿ではセキュリティモデルとして semi-honest モデルを想定する．semi-honest モデルではプロトコルに参加する二者がどちらもプロトコルの仕様から逸脱しない．しかし，プロトコルの仕様上得られる出力や中間結果などから相手の秘密情報を

図 2: 提案手法のプロトコル概観

選択されるかを全て暗号文としてサーバーが保持する．分岐関数の出力の計算には後述する比較プロトコルを用いる．何番目の枝を選択するのかは LOUDS 上での位置オフセット，すなわ
ち，式 1 の x に対応する．最終的にこのフェーズでは，対応する LOUDS 上の位置にオフセットの値を格納したベクトルであるオフセットベクトルをサーバーが構築する．

b ) 評価フェーズ

得ようとする．
一方，semi-honest モデルより攻撃者の自由度が高いモデルとして malicious モデルがある．malicious モデルでは攻撃者はプロトコルの仕様から自由に逸脱し相手の秘密情報を得ようとする．malicious モデルへの対応については本稿では詳細を説明しないが，ゼロ知識証明と呼ばれる暗号技術を用いて実現することが可能である．

4. 手

SelRanベクトル
出力値ベクトル法

評価フェーズではサーバーの持つ SelRan ベクトルと比較フェーズで構築したオフセットベクトルを繰り返し参照し，

LOUDS 上を根から葉まで順次辿る．葉までたどり着くと，到達した節点に対応する値を出力値ベクトルから抽出する．
比較フェーズ，評価フェーズは実際には二者間の暗号プロト
コルを用いた秘匿計算により行われる．まず，このとき用いられる暗号プロトコルについて 4. 3 節で述べたのちに，4. 4 節にて比較フェーズ，評価フェーズの詳細について述べる．

4. 1 問 題 設 定

4. 3 構 成 技 術

提案手法で想定する問題を次のように定義する．

4. 3. 1 DGK 比較プロトコル

ユーザーは秘密情報である入力ベクトル x を持ち，サーバー

比較フェーズで分岐関数の出力を秘匿計算するためには，

は秘密情報として決定木 T を保持する．ユーザーとサーバー⟨x < y⟩ を秘匿計算する暗号プロトコルが必要である．加法準は二者間の秘匿決定木評価プロトコルに参加し，最終的な結果

同型暗号を用いる方式でこれを実現する二者間の秘匿計算プロとしてユーザーは入力 x に対する決定木の出力 T (x) のみをトコルとして，DGK 比較プロトコル [6, 13] が知られている．

得，サーバーは何も得ない．さらに，プロトコル中にユーザー，

二者間の比較プロトコルにはいくつかの問題設定が考えられる

サーバーは他方の秘密情報に関する情報を何も得ない．ただし，

が，提案手法ではユーザーとサーバーが平文の入力値 x，y をユーザーとサーバーは (1) SelRan ベクトルの長さ，(2) 決定木

持ち，プロトコルの終了時にサーバーのみが暗号化された結果の高さ，(3) 入力ベクトルの長さは予め共有するものとする．

[[⟨x < y⟩]] を得る問題設定を想定する．比較プロトコルについ4. 2 提案手法の概観ては，本稿ではブラックボックスとして扱う．なお，実装には

この節では提案手法の概観を示す．

[13] の手法を用いた．[13] の手法を用いる場合，x，y が ℓ ビッ提案手法では，まず，ユーザーが KeyGen により鍵生成を行

ト整数であるとき，一回の比較における計算量，通信量のオーい鍵ペア (sk, pk) を得る．ユーザーは公開鍵 pk のみをサーバー

ダーはサーバー・ユーザーともに O(ℓ) となる．

に送信する．ここで，ユーザーは sk を持つため暗号文を復号す

4. 3. 2 再帰的紛失通信ることが出来るが，サーバーは pk のみを持つため復号するこ

評価フェーズではユーザーの指定したクエリに基づいてサーとができない．したがって，サーバーが暗号文から平文の情報バーの持つベクトルの要素を参照し，その値から次のクエリをを得られないことは公開鍵暗号の強秘匿性により保証される．

生成する，という操作を繰り返す必要がある．この再帰的な繰

鍵交換後は大きく 2 つのフェーズに分かれる．時系列順に比り返しをお互いの秘密情報を明かさずに行うためには，クエリ較フェーズ，評価フェーズである．以下にそれぞれのフェーズの隠ぺいとともに中間結果 (サーバーから送信する値) も隠ぺで行われる操作の概要を示す．また，図 2 に模式図を示す．

いする必要がある．この要件を満たすために，再帰的紛失通信a ) 比較フェーズ(ROT) [12] と呼ばれる技術を導入する．

比較フェーズではユーザーの入力ベクトル x から各節点にROT ではサーバーが長さ M の平文ベクトル v を持ち，ユー

紐づけられた分岐関数の出力を秘匿計算し，各節点でどの枝がザーがクエリ p0 を指定したとき，何回かの繰り返しの後ユーザーが v[v[. . . v[p0 ] . . .]] を得，サーバーは何も情報を得ない．

（ 1 ） RandRot(V , [[q]], r′ , r)：V を M × N の暗号文の行

ROT の概要は次のとおりである．ROT ではサーバーが OT

列，r′ ，r を乱数とする．q は q[p] = 1 それ以外の要素がの結果をランダム化することにより，ユーザーに対し OT の情
報を隠ぺいする．ユーザーはランダム化された値を元に次の回0 であるような長さ M のベクトルである．各要素 u[i] が⊕ −1
u[i] = N
j=0 (V [i][j] ⊗ (j + r)mod M ) のように定義されたベクの OT のクエリベクトルを生成する．このとき生成されたクエ

トル u を構築する．u を r′ 循環させたベクトルを û とする．

リベクトルはランダム化されているためそのまま用いることはû′ を各要素が û′ [i] = û ⊕ [[r2,i ⊗ ([[1]] ⊕ (⊖q[i]))]] であるベク

出来ない．しかし，サーバーは乱数を知っているのでクエリベ

トル û′ を返す．r2,i はそれぞれ乱数である．このとき p 番地にクトルからランダム化される前の「真の」クエリベクトルを復は [[0]] が足される．

元することができる．サーバーは「真の」クエリに基づき OT（ 2 ） Extract(û, p)：暗号ベクトル û から û[p] を選び，復号の操作を実行し，別の乱数でランダム化する．これを条件を満した値 Dec(û) を返す．この値は (v[p] + r)mod M である．

たすまで繰り返す．
具体的には ROT は次の 2 つの操作に PrepQuery を加えた 3
つの操作により構成される．

•

RanOT(v, [[q]], r)：それぞれ長さ M の平文ベクトル v と暗号文ベクトル [[q]] 及び乱数 r を入力とする．q[t] = 1 であるとする．ランダム化された結果 [[(v[t] + r)mod M ]] を返す．

•

eROT は PrepQuery, RecQuery, RandRot, Extract の 4 つの操作からなる．eROT はこれら 4 つの操作を以下のように繰り返
し実行する．
（ 1 ） ユーザーが PrepQuery(pi ) を実行し，クエリベクトル[[q̂]] をサーバーに送信する．
（ 2 ） サ ー バ ー は 前 回 セット し た 乱 数 ri を 用 い て

RecQuery([[q̂]], r)：長さ M の暗号文ベクトル [[q̂]]，及びRecQuery([[q̂]], ri ) を実行し「真の」クエリベクトル [[q]] を得る．

乱数 r を入力とする．ただし，[[q̂]] は乱数 r によってランダム（ 3 ） サ ー バ ー は 新 た な 乱 数 ri+1 を セット し て化されたクエリから生成されたクエリベクトルとする．[[q̂]] のRandRot(V , [[q]], ri+1 ) を実行し，û を全てユーザーに送信する．

ランダム化を解いた [[q]] を返す．

（ 4 ） ユーザーは Extract(û, p) を実行し，次のクエリ pi+1

RanOT 操作では長さ M の平文ベクトルと暗号文ベクトルのを (v[p] + ri+1 )mod M としたうえで (1) に戻る．

内積が計算される．RecQuery 操作は [[q̂]] を r 循環させること

eROT におけるサーバー側の計算量の主要な部分は ROT とにより実現される．なぜなら，クエリ (整数) の加算はクエリベ

同様に内積演算である．したがって，サーバー側の一回あたりクトルの 1 が立つ位置の移動に対応するからである．

の計算量は O(M N ) となる．ユーザー側の計算量はクエリ生

ROT のサーバー側の計算量で主要となるのは暗号文ベクト成が主要であり，ROT の場合と変わらず O(M ) である．また，ルの内積操作である．したがって，サーバー側の一回あたりの一回あたりの通信量はクエリベクトルと v̂ がともに長さ M で計算量は O(M ) である．一方，ユーザー側の計算量はクエリベあるため O(M ) である．

クトルの生成が主であり，一回あたり O(M ) の計算量となる．

4. 4 LOUDS と準同型暗号による秘匿決定木評価

また，一回あたりの通信量も同じく O(M ) である．

4. 4. 1 比較フェーズ

4. 3. 3 拡張再帰的紛失通信

4. 2 節で述べた通り，比較フェーズではユーザーの入力ベク

ROT はサーバーが平文でベクトルを保持していなければな

トル x から各節点に関連付けられた分岐関数の出力を計算し，らないという制約があった．しかし，評価フェーズで参照する

それらを元にオフセットベクトルを構築する．ただし，オフ必要があるオフセットベクトルは暗号化されている必要がある．

セットベクトルを eROT により参照するため，実際には単進符

ユーザーが選択する枝の情報を保護するためである．

号の暗号文行列とする必要がある．以降ではオフセットベクト

この節では ROT を拡張し，特定の状況下においてサーバーが暗号化された状態で情報を保持しているときに適用可能な手ルを改めてオフセット行列と呼ぶことにする．比較フェーズの
詳細は Algorithm 1 に示した．

法を提案する．本稿ではこの手法を拡張再帰的紛失通信 (eROT)

フラグ行列 F の構築： LOUDS 上の j 番地に対応する節と呼称する．eROT ではサーバーは M × N の暗号文行列 V を化したベクトルである．V [i] は平文のベクトル v の要素 v[i]点の分岐関数 Choosej (Xj ; Θ[j][0], . . . , Θ[j][uj − 1]) の出力は∑uj −1<k=0 (Θ[j][k] = Xj )1 により計算できる．ただし，Xj は j 番
地に対応する入力ベクトルの要素，uj は j 番地に対応する閾

の値を表すとする．ユーザーがクエリ p0 を指定したとき，何値の個数である．まず，Step (1) でサーバーとユーザーは入力回かのラウンドの繰り返しの後ユーザーが v[v[. . . v[p0 ] . . .]] を値と閾値の比較結果を全て計算し，結果の暗号文ベクトルを持つ．V の各行 V [i] は N ビットの単進符号の各ビットを暗号得，サーバーは何も情報を得ない．

eROT も ROT 同様ランダム化により情報を隠ぺいする．し構築する．閾値と入力値との比較結果を秘匿計算するためにかし，加法準同型暗号上で任意の法の mod 演算を行うことは

4. 3. 1 節で導入した DGK 比較プロトコルを用いる．比較結果の暗号文行列 F = [[⟨Θ[j][k] <= Xj ⟩]] をフラグ行列と呼ぶ．ただ困難であり，⊕ 演算のみで乱数の加算を安全に行うことができ

し，k = 0, . . . , uj − 1，j = 0, . . . , 2N + 1 である．

ない．eROT ではこの問題を，乱数の加算及び mod 演算が，W の構築： 次に，サーバーは Step (2) でフラグ行列の各単進符号を表現したベクトルの循環に対応することを利用して行を，分岐関数の出力を単進符号の形式に変換して各ビットを解決する．

暗号化した行列 W を構築する．フラグ行列 F が与えられた

eROT では新たに 2 つの操作を定義する．

とき，Choosej (Xj ; Θ[j][0], . . . , Θ[j][uj − 1]) − 1 を表す uj + 1

Algorithm 1 提案手法の比較フェーズの詳細•

共通の入力: LOUDS 表現の長さ 2N + 1，決定木の高さ d，入力ベクトルの長さ n，比較回数 m•

サーバーの入力: 閾値ベクトル Θ，節点情報ベクトル L•

ユーザーの入力: 入力ベクトル x

Step (1): サーバー，ユーザーが DGK 比較プロトコルを実行し，フラグベクトル F を構築する．

Step (2): サーバーはフラグ行列 F から W を構築する．
for j ∈ S, k ∈ {0, . . . , uj − 1} do
W [j][k] ← F [j][k − 1] ⊕ (⊖F [j][k])Step (3): サーバーは W を元にオフセット行列 O を構築する．
for j ∈ {0, . . . , 2N + 1} do
if L[j] = ONEBASE thenO[j] ← ([[1]])else if L[j] = LEAF thenO[j] ← ([[1]])else if L[j] = INTERNAL thenO[j] ← (W [j], [[0]])(W [j], [[0]]) は W [j] に [[0]] を連結したベクトルを意味する．

置を指定したかを知らず，ユーザーはサーバーの持つ v 及び Oの内容を知らないようにしなければならない．サーバー，ユー
ザーがお互いの秘密情報を得ずに 2 つのベクトルの参照を繰り返し行うために，4. 3. 2，4. 3. 3 節で導入した ROT 及び eROTを用いる．
評価フェーズの疑似コードを Algorithm 2 に示した．最初にサーバー，ユーザーともに Step (1) で初期化を行う．サーバー
は乱数 r1′ = r2′ = 0 を設定する．ri′ は一つ前の繰り返しで設定した乱数を記録する変数である．ユーザーは初期位置 p0 = 0を設定して評価フェーズを始める．

Step (2) では v と O に対しそれぞれ ROT と eROT を繰り返し適用し，LOUDS 上の位置を更新する．各回の ROT,eROT′′により得られる βk+1
及び ωk+1
はそれぞれ SelRan(B, p′k ) とオフセットの値がランダム化された値である．また，LOUDS
上の子の位置は SelRan(B, p) + x によって定まる．よって，次′′のクエリ p′k+1 = (βk+1+ ωk+1)mod 2N +1 となる．

この繰り返しは木の高さと同じ d 回行われる．ここで，葉に到達した場合の動作について注意が必要である．O の定義か
ら，葉に到達した場合 LOUDS 上の位置は到達した葉の位置 (1ビットの単進符号表現の暗号文ベクトル W [j] は以下のようにベース表現) に固定される．これにより葉の深さにかかわらず各要素を計算することで構築することができる．

d 回の繰り返しの後にはいずれかの葉の 1 ベース表現に到達す

W [j][k] = F [j][k − 1] ⊕ (⊖F [j][k])ただし，F [j][uj ] = [[0]]，F [j][−1] = [[1]] とする．

ることが保証される．

Step (3) では OT により出力値ベクトルを参照し，ユーザーが決定木の出力 T (x) = zl を得る．

オフセット行列 O の構築： 最後に，サーバーは Step (3)評価フェーズでは ROT と eROT を組合わせることにより，

で W 及び節点情報ベクトル L からオフセット行列 O を構築

サーバー，ユーザーの秘密情報を隠したまま LOUDS 上で木をする．O は各行が LOUDS 上のオフセットを単進符号で表し辿る操作を実現した．評価フェーズで共有する情報は v の長さた暗号ベクトルであるような行列である．O の各行 O[j] に格

2N + 1 のみである．

納すべき値はまず，位置 j が 1 ベース表現に対応するか否か

4. 5 計 算 量で異なる．1 ベース表現の場合はオフセットは 0 とする．こ

本節では提案手法の時間計算量・通信量について考察する．

れは 1 ベース表現にたどり着いた後にその位置にとどまり続

まず，比較フェーズについて考察する．DGK 比較プロトコ

けるためである．0 ベース表現の場合はさらに 2 つの場合にルに要する計算量は精度 ℓ と比較回数 m(< N ) に比例し，サー分かれる．(1) 節点が葉の場合は 1 ベース表現にとどめるた

バー側で O(ℓm) である．ユーザー側では入力ベクトルの暗号

めオフセットを 0 とする．(2) 内部節点の場合分岐関数の出力化と比較フェーズにおける復号化を考慮すると O(ℓ(n + m)) のChoosej (Xj ; Θ[j][0], . . . , Θ[j][uj − 1]) をオフセットとする．以

計算量となる．また，フラグ行列からオフセット行列を構築す

上より，O[j] は Step(3) のように決定される．

るのに必要な計算量はオフセット行列の行ベクトルの総長に比Algorithm 1 のように O を構築することで比較回数以外のサーバー，ユーザーの情報は明かされない．

例し，O(N ) である．したがって，比較フェーズのサーバーの計算量は O(ℓm + N )，ユーザーの計算量は O(ℓ(n + m)) とな

また，O は各行の長さが異なるが，eROT により参照できる

る．また，通信量については m 回の DGK 比較プロトコルに形式となっている．RandRot の内積操作においてビット列の長⊕uj
さに応じて j=0
(V [i][j] · (j + r)mod M ) と計算すればよいか

要する通信量が ℓm であることから，サーバー側で O(ℓm) でらである．さらに，これにより計算量を削減することができる．

暗号化された結果を m 個送信するため O(ℓn + m) である．

4. 4. 2 評価フェーズ

ある．ユーザー側の通信量は入力ベクトルの長さが n であり，
評価フェーズの計算量はサーバー側，ユーザー側ともに

この節では 4. 2 節に述べた LOUDS 上の木の操作を秘匿計O(dN ) である．ROT の計算量は 1 回当たり O(N ) であるこ

算技術を用いてどのように実現するかを説明する．LOUDS 上とから O(dN ) である．また，eROT の計算量も O(dN ) であの位置 pi を与えられたとき，次の位置 pi+1 を算出するために

る．eROT においてサーバー側の計算量は行列の大きさに比例は SelRan ベクトル v とオフセット行列 O の pi 番目の要素のするが，オフセット行列の各行の長さの総和は O(N ) であるた

参照を行い，前者に後者を足した値を計算する．根から葉まで

め，eROT1 回当たりの計算量は O(N ) となるからである．通辿る操作を行うためには初期位置 p0 を 0 と指定して繰り返し

信量については長さ 2N + 1 の暗号文ベクトルを送信するため，

v 及び O を参照する．ただし，サーバーはユーザーがどの位

O(dN ) である．以上の計算量及び通信量を表 1 にまとめた．

Algorithm 2 提案手法の比較フェーズの詳細•

共通の入力: LOUDS 表現の長さ 2N + 1，決定木の高さ d•

サーバーの入力: SelRan ベクトル v ，オフセット行列 O′[[βk+1]] と ôk+1 をユーザーに送信する．

r1′ ← r1 , r2′ ← r2

Step (1): パラメータを初期化する．
ServerSide:

ClientSide:r1′ ← 0, r2′ ← 0′[[βk+1]] と ôk+1 を受信する．
′′
βk+1← [[βk+1]]

ClientSide:′ωk+1← Extract(ôk+1 , p′k )p′0 ← 0
Step (2): ROT，eROT を繰り返し LOUDS 上の位置を更新する．

′′
p′k+1 ← (βk+1+ ωk+1)mod 2N +1

Step (3): OT により出力ベクトル z から決定木の出力 zℓ を得る．

for k = 0 to d − 1 do

ClientSide:

ClientSide:[[q̂]] ← PrepQuery(p′d )q̂ ← PrepQuery(p′k )[[q̂]] をサーバーに送信する．

q̂ をサーバーに送信する．

ServerSide:

ServerSide:q̂ を受信する．

[[q̂]] を受信する．

q ← RecQuery(q̂, r1′ − r2′ )[[q]] ← RecQuery(q̂, r1′ − r2′ )r1 , r2 に乱数を設定する．

[[zℓ ]] ← InnerProduct(z, [[q]])ROT:[[zℓ ]] をユーザーに送信する．

′[[βk+1]] ← RanOT(v, [[q]], r1 )ClientSide:[[zℓ ]] を受信する．

eROT:ôk+1 ← RandRot(O, [[q]], r1′ − r2′ , r2 )zℓ ← Dec[[zℓ ]]表 1: 提案手法の各フェーズと全体の時間計算量と通信量．表中の S
7はサーバー，U はクライアントの略である．
通信量

6O(ℓm + N )

O(ℓm)

5

比較フェーズ (U) O(ℓ(n + m)) O(ℓn)
評価フェーズ (S)O(dN )

O(dN )

評価フェーズ (U)O(dN )

O(dN )

計算時間(s)

比較フェーズ (S)

時間計算量

4
3
計算時間(サーバー)2

計算時間(ユーザー)

1

5. 実 験 結 果

0
10

12

14

4. 4 節に説明した semi-honest モデルに対応した提案手法を実装した．実装に用いた言語は C++である．加法準同型暗号

16

18

20

高さd

図 3: 提案手法におけるユーザー，サーバーそれぞれの計算時間．

方式としては lifted-Elgamal を採用し，その C++実装である

mcl ライブラリ [11] を用いた．lifted-Elgamal のセキュリティ
パラメータには secp192k1 [7] を用いた．

987が 500 である決定木をサーバーの持つ決定木とした．比較回数6

m は 180 程度となった．分岐数は 2 か 3 であるよう設定した．
入力ベクトルの長さ n は比較回数 m と同じとした．
実験にはユーザー用，サーバー用にそれぞれデスクトップコ

通信量(MB)

テストデータはランダムに生成した決定木と入力ベクトルである．高さ d を 10 から 20 まで 1 刻みで変化させ，節点数 N

543
通信量(ユーザー)

2

ンピュータ一台ずつを用いた (それぞれ Xeon 2.40GHz，Xeon

1

3.40GHz を搭載)．また，どちらも 1 スレッドのみ使用した．

0

図 3 は計算時間のグラフである．図 3 から，計算時間の合計
は高さ 20 においても 11 秒程度と実用的な時間であることが確認できた．また，サーバー，ユーザーともに高さに比例する計
算時間となった．

通信量(サーバー)

10

12

14

16

18

20

高さd

図 4: 提案手法におけるユーザー，サーバーそれぞれの総通信量 (アップロード)．

図 4 は通信量のグラフである．図 4 から，総通信量は高さモデルに対して安全なプロトコルに拡張することができる．提20 においてサーバーの上りで 8MB，ユーザーの上りで 7MB 程案手法は従来手法と同等のセキュリティを維持しつつ決定木の度となり，現実的な値と言える．また，通信量についてもサー高さが高い場合にも対応できる汎用性を期待できる．さらに，バー，ユーザーともに高さに対しておおよそ線形であり，表 1

提案手法は木構造を自由に走査することが可能なため，決定木に示した理論性能に従うことが確かめられた．

のみに特化して設計された従来手法とは異なり，木による検索など多様な応用も期待される.

6. 従来手法との比較
本節では semi-honest モデルに対して安全なプロトコルについて従来手法 [14] との比較を行う．まず，計算量及び通信量のオーダーの比較について考察する．表 2 に従来手法と提案手法の計算量及び通信量のオーダーを示した．[14] の手法ではサーバー側の計算量と通信量が指数オーダーとなる．提案手法はサーバー側の計算量・通信量を高さ d に対して線形のオーダーに改善した．一方で，ユーザー側の計算量及び通信量のオー
ダーは従来手法よりも悪化した．しかし，提案手法のユーザー側の評価フェーズの計算時間・通信量が全体に占める割合は小さい．よって，プロトコル全体としてはユーザー側のオーダー
悪化の影響は小さいと思われる．以上から，提案手法は [14] と比較して決定木の高さが高い場合にも対応することができる汎用性を持ち，特に木がスパースな場合に優れた性能となると言える．木の高さが低い場合では提案手法の実測値も十分に小さく，[14] との差は小さいことが予想される．
次に，実行時間の実測値について比較を行う．ただし，従来手法 [14] は実装が非公開であるため， [14] に記載の実験結果と，二分決定木を用いパラメータを同一にした場合の提案手法の実験結果との比較を行う．d = 17, m = 57 の場合，提案手法，従来手法の実行時間はそれぞれ 5.7 秒，17 秒であり，11 秒
程度，約 3 倍の高速化を達成した．また，d = 4, m = 13 の場
合，それぞれ 0.52 秒，0.37 秒と従来手法の方が上回る結果となった．しかし，差は 0.15 秒程度と小さい．また，実験結果は計算量及び通信量のオーダーの比較において述べた性質とよく一致すると言える．なお，上記の提案手法の実験結果は CPUの周波数について補正した値である．暗号ライブラリやセキュ
リティパラメータなどの差異は補正していない．

従来手法 (S)

時間計算量

通信量

O(ℓm + 2d )O(ℓm + 2d )従来手法 (U) O(ℓ(n + m) + d)O(ℓn + m)

提案手法 (S)O(ℓm + dN )O(ℓm + dN )提案手法 (U) O(ℓ(n + m) + dN ) O(ℓn + m + dN )表 2: 従来手法 [14] と提案手法それぞれの時間計算量と通信量のオー
ダー．表中の S はサーバー，C はユーザーの略である．

7. 結

論

本研究ではサーバー，クライアント双方の秘密情報を秘匿したまま決定木の出力を効率的に計算する二者間の秘匿決定木評
価手法を提案した．提案手法は高さに線形な計算量・通信量を達成した．従来手法の高さに対して指数オーダーの計算量・通信量に対して大幅な改善となった．また，提案手法は malicious

文献[1] Mauro Barni, Pierluigi Failla, Vladimir Kolesnikov, Riccardo Lazzeretti, Ahmad Reza Sadeghi, and Thomas
Schneider. Secure evaluation of private linear branching
programs with medical applications. In ESORICS, pp. 424–
439, 2009.
[2] BigML Website.
Machine Learning for everyone.
BigML.com, 2016. URL accessed January 30, 2017.
[3] Raphaël Bost, Ra Popa, Stephen Tu, and Shafi Goldwasser.
Machine Learning Classification over Encrypted Data. In
NDSS, pp. 1–14, 2015.
[4] Justin Brickell, Donald E Porter, Vitaly Shmatikov, andEmmett Witchel. Privacy-preserving remote diagnostics.
In CCS, pp. 498–507, 2007.
[5] Ronald Cramer, Rosario Gennaro, and Berry Schoenmakers. A secure and optimally eﬃcient multi-authority election
scheme. In EUROCRYPT, pp. 103–118. Springer-Verlag,
1997.
[6] Ivan Damgård, Martin Geisler, and Mikkel Krøigaard. Efficient and Secure Comparison for On-Line Auctions. In
ACISP, pp. 416–430, 2007.
[7] Daniel R. L. Brown. Standards for Eﬃcient Cryptography
2 (SEC 2) : Recommended Elliptic Curve Domain Parameters. Standards for Eﬃcient Cryptography, pp. 1–33, 2010.
[8] Matt Fredrikson, Somesh Jha, and Thomas Ristenpart.
Model Inversion Attacks that Exploit Confidence Information and Basic Countermeasures. In SIGSAC, pp. 1322–
1333, 2015.
[9] Guy Jacobson. Space-eﬃcient static trees and graphs. In
FOCS, pp. 549–554, 1989.
[10] Microsoft Azure. Machine Learning - Microsoft Azure, 2016.
URL accessed January 30, 2017.
[11] Mitsunari Shigeo. C++ library implementing elliptic curve
elgamal crypto system. URL accessed January 30, 2017.
[12] Kana Shimizu, Koji Nuida, and Gunnar Ratsch. Eﬃcientprivacy-preserving string search and an application in genomics. Bioinformatics, Vol. 32, No. 11, pp. 1652–1661,
2016.
[13] Thijs Veugen. Improving the DGK comparison protocol. In
WIFS, pp. 49–54, 2012.
[14] David J Wu, Tony Feng, Michael Naehrig, and Kristin
Lauter. Privately Evaluating Decision Trees and Random
Forests. PoPETS, Vol. 2016, No. 4, pp. 1–21, 2016.
[15] 岡之原大輔. 高速文字列解析の世界. 岩波書店, 2012.