SVパッキングによる完全準同型暗号を用いた安全な委託Aprioriの高速化

DEIM Forum 2016 F8-6

SV パッキングによる完全準同型暗号を用いた

安全な委託

Apriori 高速化

高橋 卓巳

†1

_{石巻 優}

†2

_{山名 早人}

†3†4

†1 早稲田大学基幹理工学部 〒169-8555 東京都新宿区大久保 3-4-1

†2 早稲田大学大学院基幹理工学研究科 〒169-8555 東京都新宿区大久保 3-4-1

†3 早稲田大学理工学術院 〒169-8555 東京都新宿区大久保 3-4-1

†4 国立情報学研究所 〒101-8430 東京都千代田区一ツ橋 2-1-2

E-mail: †{kururu, yuishi, yamana}@yama.info.waseda.ac.jp

あらまし 企業や国などの様々な組織にとって，保有するデータを利活用することがますます重要になってきて いる．さらに扱われるデータ量は爆発的に増加し，データ解析処理の際に計算をクラウドに委託するケースが増え てきている．一方でデータには顧客データなどの個人情報に結びつく情報が含まれ，クラウドへ委託計算する場合 にデータの扱いを誤るとプライバシーやセキュリティの問題が発生する危険性がある．そこで注目されているが暗

号化したデータ同士を複合することなく計算することができる完全準同型暗号（以下 FHE: Fully Homomorphic

Encryption）である．しかし，現在の FHE を用いた委託計算方法では実用的な時間で処理を終えることができない．

そこで本研究では，Liu らによって提案された FHE を用いたアプリオリアルゴリズムの委託計算を BGV（Brakerski,

Gentry, Vaikuntanathan）スキームと言われる暗号スキームが実装されている HElib によって実装し，SV パッキング を用いて必要な演算回数を削減することにより高速化する手法を提案する．実験の結果，計算時間が##改善されて ることを示した． キーワード プライバシー保護，セキュリティ，データマイニグ，完全準同型暗号，アプリオリ

1. は じ め に

企 業 や 国 な ど の 様 々 な 組 織 に と っ て ， 自 身 が 保 有 す る デ ー タ を 有 効 に 活 用 す る こ と が ， 近 年 ま す ま す 重 要 に な っ て い る ． ま た そ こ で 扱 わ れ る デ ー タ の 量 は 爆 発 的 に 増 加 し て い る の に 加 え ， 近 年 著 し く 研 究 が 盛 ん に な っ て い る デ ー タ マ イ ニ グ や 機 械 学 習 の ア ル ゴ リ ズ ム も 計 算 量 が 大 き く な っ て き て い る ． そ こ で 最 近 で は ， 計 算 資 源 と し て ク ラ ウ ド を 利 用 す る こ と が 多 く な っ て き て い る （ 委 託 計 算 ま た は 計 算 の ア ウ ト ソ ー シ ン グ ）． し か し そ の 一 方 で ， 委 託 計 算 を す る 個 人 ま た は 組 織 が ク ラ ウ ド サ ー ビ ス を 提 供 す る 第 三 者 を 完 全 に 信 頼 す る こ と が で き な い 場 合 ， デ ー タ の 扱 い 方 を 誤 る と プ ラ イ バ シ ー や セ キ ュ リ テ ィ の 問 題 が 発 生 す る 可 能 性 が あ る [1]． プ ラ イ バ シ ー 保 護 と デ ー タ マ イ ニ ン グ 活 用 を バ ラ ン ス す る 技 術 と し て プ ラ イ バ シ ー 保 護 デ ー タ マ イ ニ グ と 呼 ば れ る 研 究 が 盛 ん に 行 わ れ て き た ． こ れ ら の 研 究 は ア プ ロ ー チ の 面 か ら 次 の 4 つ に 分 類 で き る ： 1)統 計 的 に 処 理 し た 集 約 情 報 や 分 割 表 な ど の 個 人 情 報 の テ ー ブ ル を 対 象 に 個 人 の プ ラ イ バ シ ー を 保 護 す る デ ー タ マ イ ニ ン グ 手 法[2][3][4][5]． 2)マ イ ニ ン グ 結 果 か ら 個 人 が 推 定 さ れ な い よ う プ ラ イ バ シ ー 保 護 す る 手 法[6][7]． 3)個 人 デ ー タ 集 合 か ら あ る 同 一 属 性 を 持 つ デ ー タ を k 個 未 満 に 絞 り 込 め な い と い うk 匿 名 性 を 利 用 し た プ ラ イ バ シ ー 保 護 デ ー タ マ イ ニ グ 手 法[8][9][10]． 4)完 全 準 同 型 暗 号 （FHE） を 用 い て 入 力 デ ー タ と 出 力 結 果 の 両 方 の プ ラ イ バ シ ー を 保 護 す る 手 法[11]． 本 稿 で は ，上 記 で 述 べ た 4)完 全 準 同 型 暗 号 を 用 い た 方 法 を 対 象 と す る ． 具 体 的 に は ， ユ ー ザ が ク ラ ウ ド に デ ー タ マ イ ニ ン グ を 委 託 す る 場 合 に 入 力 デ ー タ と マ イ ニ ン グ 結 果 の 情 報 を 一 切 漏 洩 す る こ と な く 委 託 計 算 を 行 う シ ナ リ オ を 対 象 と す る ． こ の よ う な シ ナ リ オ を 安 全 な 委 託 デ ー タ マ イ ニ ン グ （Secure Outsourced Data Mining）と 呼 ぶ ．1)~3)の 手 法 で は 入 力 デ ー タ と マ イ ニ ン グ 結 果 の 両 方 を プ ラ イ バ シ ー 保 護 す る こ と が で き な い の に 加 え ， ア プ ロ ー チ と し て デ ー タ や 結 果 へ の ノ イ ズ （ 摂 動 ） 追 加 や ラ ン ダ ム 化 を 行 っ て お り マ イ ニ ン グ 結 果 が 正 確 で な く な っ て し ま う ． FHE は ，暗 号 化 し た 状 態 で 平 文 に 対 す る 加 算 ・ 乗 算 を 実 現 で き る 機 能 （ 準 同 型 演 算 ） を 備 え た 公 開 鍵 暗 号 方 式 で あ る ． 平 文 を 暗 号 化 す る 際 ， セ キ ュ リ テ ィ パ ラ メ ー タ に 応 じ て 一 定 の ノ イ ズ を 加 え る ． し か し ， ノ イ ズ は 準 同 型 演 算 ご と に 増 加 し ， 増 加 し す ぎ る と 暗 号 文 を 正 し い 値 に 複 合 で き な く な る ． 特 に AND 演 算 の 準 同 型 評 価 を 行 う と ノ イ ズ の 桁 数 が お お よ そ 倍 増 す る こ と が 知 ら れ て い る ． そ の た め ， 準 同 型 演 算 の 乗 算 回 数 に 制 限 を 設 け た Somewhat 準 同 型 暗 号 （ 以 下 SWHE: Somewhat Homomorphic Encryption） が 限 界 と さ れ て い

た ．2009 年 に IBM の Gentry が SWHE に 対 し て 暗 号 文 ノ イ ズ を 削 減 す る 手 法（bootstrapping）を 提 案 し た こ と に よ り FHE の 実 装 方 法 が 完 成 し た [12] ． し か し ， bootstrapping を 行 う と 計 算 量 が 大 幅 に 増 加 し て し ま う ． こ の 問 題 に 対 し て ，FHE に お い て 複 数 の 平 文 （ 整 数 ） を 一 つ の 暗 号 文 に 暗 号 化 す る SV パ ッ キ ン グ [13]や ， bootstrapping を 用 い ず に 暗 号 文 ノ イ ズ を 削 減 す る こ と で 計 算 量 を 削 減 す る BGV ス キ ー ム [14]な ど の 研 究 成 果 に よ り FHE の 理 論 研 究 が 進 ん で い る ． ま た ，FHE の 実 用 化 に 向 け た 研 究 も 盛 ん に な っ て い る[11][15][16][17][18]．FHE の 実 用 化 に 向 け た 研 究 は ， そ れ ぞ れ 想 定 す る シ ナ リ オ と 動 機 に よ っ て1)秘 匿 検 索 ， 2)秘 匿 暗 号 化 ， 3)委 託 デ ー タ マ イ ニ ン グ の 3 つ に 分 類 で き る ．1)秘 匿 検 索 は ， ク ラ ウ ド 上 に 保 存 さ れ て い る 暗 号 化 さ れ た デ ー タ に 対 し て 検 索 を 行 う 場 合 に ， 入 力 ク エ リ と 検 索 結 果 な ど の 情 報 を ク ラ ウ ド 側 に 漏 ら さ ず に 実 行 す る 技 術 で あ る[15][16]．2)秘 匿 暗 号 化 は ，暗 号 化 さ れ た デ ー タ を 複 合 せ ず に 異 な る 鍵 を 用 い て 準 同 型 演 算 と 複 合 が 可 能 に な る 暗 号 文 へ 変 換 す る 技 術 で あ る [17]． 3)秘 匿 計 算 は 暗 号 化 さ れ た デ ー タ 同 士 を 複 合 せ ず に 計 算 す る 技 術 で あ る[11][18]． 安 全 な 委 託 デ ー タ マ イ ニ ン グ は3)秘 匿 計 算 に 分 類 さ れ ， 同 手 法 は 2015 年 に Liu ら が FHE を 用 い た 安 全 な 委 託Apriori 手 法 と し て 初 め て 提 案 さ れ て い る [11]．そ の 他 ，Chu ら が リ ン ク 構 造 に お け る ノ ー ド 間 の 類 似 度 ス コ ア SimRank を 秘 匿 計 算 す る 手 法 を 提 案 し た [18]． し か しChu ら の 研 究 で は 実 デ ー タ で は な く 人 工 的 に 作 ら れ た ト ラ ン ザ ク シ ョ ン 数 5,000 の デ ー タ に 対 し て 一 回 の Apriori を 実 行 し て お り ， HP Pavilion dm4 laptop （CPU: Core i5, ク ロ ッ ク 数 : 2.50GHz, メ モ リ : 8GB） を 用 い て 100 日 以 上 か か っ た と 報 告 さ れ て お り さ ら な る 高 速 化 が 必 要 で あ る ． 本 稿 で は 以 上 の 問 題 を 解 決 す る た め ，Liu ら の 手 法 の 高 速 化 手 法 を 提 案 す る ． 提 案 手 法 で は ， ト ラ ン ザ ク シ ョ ン デ ー タ の 暗 号 化 の 際 に SV パ ッ キ ン グ を 用 い て 複 数 の 整 数 を ベ ク ト ル と し て 一 つ の 暗 号 文 に 暗 号 化 す る ． こ れ に よ り 扱 う 暗 号 文 の 数 を 削 減 す る こ と が で き る ． ま た サ ポ ー ト を カ ウ ン ト す る 際 の 複 数 の 整 数 に 対 す る 演 算 を ベ ク ト ル 演 算 に 置 き 換 え る こ と で 計 算 量 を 削 減 す る ．具 体 的 に は ，1)Liu ら の 手 法 で 用 い ら れ て い た 整 数 ベ ー ス の ス キ ー ム の 代 わ り に ，BGV ス キ ー ム が 実 装 さ れ て い る HElib1_{を 用 い て 従 来 手 法 を 実 装 し ，2)} 提 案 手 法 と し て HElib に 実 装 さ れ て い る SV パ ッ キ ン グ を 用 い て 暗 号 文 と 計 算 量 を 削 減 す る ア ル ゴ リ ズ ム を 実 装 す る ． こ れ に よ り ， 暗 号 文 の 数 を ト ラ ン ザ ク シ ョ ン 数N の デ ー タ に 対 し て 1/N に す る こ と が で き る ． 本 稿 で は 以 下 の 構 成 を と る ． ま ず ，2 節 で は 関 連 研 1 _{HElib, http://shaih.github.io/HElib/} 究 に つ い て 述 べ ，3 節 で は 提 案 手 法 に つ い て 説 明 す る ． 4 節 で は 従 来 手 法 と 提 案 手 法 の 評 価 実 験 に つ い て 述 べ る ． 最 後 に 5 節 で 本 稿 を ま と め る ．

2. 関 連 研 究

本 節 で は ，FHE の 関 連 研 究 ，FHE 実 用 化 に 向 け た 研 究 ， 本 稿 で 対 象 と す る 委 託 頻 出 パ タ ー ン マ イ ニ ン グ に 関 す る 関 連 研 究 に つ い て 述 べ る ．

2.1. FHE スキーム

完 全 準 同 型 暗 号（FHE: Fully Homomorphic Encryption） [12]は 暗 号 化 し た ま ま 加 算 を 行 え る 加 法 準 同 型 性 と 乗 算 を 行 え る 乗 法 準 同 型 性 の 両 方 を 備 え る 公 開 鍵 暗 号 方 式 で あ る ．FHE で は 任 意 の 論 理 回 路 （ 2 進 数 を 前 提 に し た 時 ，全 演 算 は AND と XOR で 計 算 可 能 ）で 表 さ れ る 関 数𝐶に 対 し て t 個 の 入 力（ 値 は 0,1）を 𝑚#, 𝑚%, ⋯ , 𝑚' と し た 時 の 演 算 結 果𝐶 𝑚#, 𝑚%, ⋯ , 𝑚' を ， 各 入 力 mi を 各 々 個 別 に 暗 号 化 （ci） し 同 関 数 に 入 力 し た 演 算 結 果 𝐶 𝑐#, 𝑐%, ⋯ , 𝑐' を 復 号 す る こ と で 得 る こ と が で き る ．こ の 場 合 の 暗 号 化 さ れ て い な い 0,1 の 入 力𝑚を 平 文 ， 平 文 を 暗 号 化 し た𝑐 を 暗 号 文 と 呼 ぶ ． FHE は ， 𝐾𝑒𝑦𝐺𝑒𝑛， 𝐸𝑛𝑐𝑟𝑦𝑝𝑡， 𝐷𝑒𝑐𝑟𝑦𝑝𝑡， 𝐸𝑣𝑎𝑙𝑢𝑎𝑡𝑒の 4 関 数 か ら 構 成 さ れ る ． 1. 𝐾𝑒𝑦𝐺𝑒𝑛 λ : 与 え ら れ た セ キ ュ リ テ ィ パ ラ メ ー タ λに 対 し て 秘 密 鍵 𝑠𝑘と 公 開 鍵 𝑝𝑘の ペ ア 𝑠𝑘, 𝑝𝑘 を 生 成 す る. 秘 密 鍵 が 破 ら れ る 確 率 は セ キ ュ リ テ ィ パ ラ メ ー タ に 対 し て ，1/2=_{と な る ．} 2. 𝐸𝑛𝑐𝑟𝑦𝑝𝑡 𝑝𝑘, 𝑚 : 平 文 (plaintext) 𝑚を 公 開 鍵 𝑝𝑘 で 暗 号 化 し て ， 暗 号 文 を 返 す ． 3. 𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑠𝑘, 𝑐 : 暗 号 文 (ciphertext)𝑐を 秘 密 鍵 𝑠𝑘で 復 号 し ， 平 文 を 返 す ． 4. 𝐸𝑣𝑎𝑙𝑢𝑎𝑡𝑒 𝑝𝑘, 𝐶, 𝑐#, 𝑐%, ⋯ , 𝑐' : 公 開 鍵𝑝𝑘， 𝑡個 の 入 力 を 取 る AND ゲ ー ト と XOR ゲ ー ト で 構 成 さ れ た 回 路𝐶，t 個 の 暗 号 文 𝑐>と す る ．こ の 下 で 全 て の 𝑖 ∈ 1, ⋯ , 𝑡 に 対 し て 𝑐>= 𝐸𝑛𝑐𝑟𝑦𝑝𝑡 𝑝𝑘, 𝑚> な ら ば ， 𝐷𝑒𝑐𝑟𝑦𝑝𝑡 𝑠𝑘, 𝐸𝑣𝑎𝑙𝑢𝑎𝑡𝑒 𝑝𝑘, 𝐶, 𝑐#, 𝑐%, ⋯ , 𝑐' = 𝐶 𝑚#, 𝑚%, ⋯ , 𝑚' を 満 た す 暗 号 文 に 対 し て 任 意 の 𝐶を 正 確 に 評 価 で き る と い う も の で あ る ． こ れ ら4 関 数 で 構 成 さ れ る 公 開 鍵 暗 号 方 式 が FHE と 定 義 さ れ て い る[12]． FHE の 暗 号 ス キ ー ム は 2009 年 に Gentry[12]が 初 め て 考 案 し た ．FHE ス キ ー ム は ，イ デ ア ル 格 子 ベ ー ス の ス キ ー ム [12][13][20] ， 整 数 ベ ー ス の ス キ ー ム [19][21][22][23]，LWE(Learning With Errors)問 題 に 基 づ く ス キ ー ム[24]，Ring-LWE(Learning With Errors)問 題 に 基 づ く ス キ ー ム[14][25][26]， NTRU ベ ー ス の ス キ ー ム [17][27]が 提 案 さ れ て い る ．

Gentry の 手 法 は ， SWHE を 構 築 し た 後 ， 準 同 型 評 価 に よ っ て 増 加 し た ノ イ ズ を 削 減 す るbootstrapping を 使

っ てFHE を 実 現 す る と い う も の で あ る ．Gentry の 提 案 後 に bootstrapping を 用 い た 様 々 な FHE ス キ ー ム が 提 案 さ れ た が ， そ れ ら は 直 接 的 ま た は 間 接 的 に イ デ ア ル 格 子 に 基 づ く も の で あ り 暗 号 文 に 含 ま れ る ノ イ ズ が 多 く ， 特 に 乗 算 を 行 う と ノ イ ズ が 爆 発 的 に 増 加 す る と い う 問 題 やbootstrapping を 実 行 す る 計 算 量 が 大 き く な っ て し ま う と い う 問 題 が あ っ た[13][19][20][21][26]． こ れ に 対 し て ，Brakerski, Gentry, Vaikuntanathan ら は Ring-LWE 問 題 に 基 づ き 暗 号 文 と 平 文 を 多 項 式 環 の 元 に よ っ て 表 現 し ，bootstrapping を 用 い ず に FHE を 実 現 す る こ と で 従 来 手 法 に お け る ノ イ ズ と 計 算 量 を 削 減 す る BGV ス キ ー ム を 提 案 し た [14]． ま た 従 来 の FHE が 単 一 ユ ー ザ の 利 用 を 想 定 し た も の で あ っ た の に 対 し ， López ら は 複 合 す る こ と な く 異 な る 鍵 で 暗 号 化 さ れ た 暗 号 文 同 士 の 演 算 が 可 能 な FHE ス キ ー ム を 提 案 し た [17]．

Smart と Vecrauteren は 2012 年 に polynomial-CRT(Chinese Remainder Theorem) に 基 づ き ベ ク ト ル の 要 素 ご と の 準 同 型 和 と 準 同 型 積 の 評 価 可 能 な パ ッ キ ン グ 手 法 を 提 案 し た（SV パ ッ キ ン グ ）[28]．Gentry, Halevi, Smart ら は 同 じ く 2012 年 に ， SV パ ッ キ ン を FHE に お い て 使 用 す る 場 合 に ，𝑇個 の ゲ ー ト で 構 成 さ れ る 算 術 演 算 回 路 を𝑇 ∙ 𝑝𝑜𝑙𝑦𝑙𝑜𝑔(𝜆)の 時 間 計 算 量 で 評 価 す る 最 適 化 手 法 を 提 案 し た （GHS 最 適 化 ）． さ ら に 複 合 す る こ と な く 暗 号 化 さ れ た ベ ク ト ル の 要 素 の 位 置 を 移 動 す る こ と を 可 能 に し た[25]． ま た ， Brakerski は 従 来 手 法 に お け る 暗 号 文 の ノ イ ズ が 乗 算 の 度 に 初 期 の ノ イ ズ サ イ ズ の 二 乗 に 比 例 し て 増 加 し て い た 問 題 に 対 し て ， 初 期 の ノ イ ズ サ イ ズ に 対 し て 線 形 的 に 増 加 す る よ う な 手 法 を 提 案 し た[24]． FHE ス キ ー ム の 実 装 で は ， Ring-LWE 問 題 に 基 づ く BGV ス キ ー ム と NTRU に 基 づ く ス キ ー ム [17][27]が ノ イ ズ や 計 算 量 の 面 で 最 適 と 考 え ら れ て い る が ． し か し NTRU ベ ー ス の ス キ ー ム は 部 分 的 な 実 装 に と ど ま っ て い る[29]． 一 方 ， BGV ス キ ー ム に 加 え SV パ ッ キ ン グ と GHS 最 適 化 を ア セ ン ブ リ と C++に よ っ て 実 装 し て い るHElib が Halevi と Shoup に よ っ て オ ー プ ン ソ ー ス ラ イ ブ ラ リ と し て 公 開 さ れ て い る た め ， 広 く 使 わ れ て い る[30][31]．よ っ て 本 稿 の 実 装 に お い て も HElib を 使 用 す る こ と と し た ．

2.2. FHE の実 用 化 に向 けた研 究

Gentry に よ る FHE ス キ ー ム 実 現 以 降 ， FHE ス キ ー ム を 実 装 し 実 用 的 な ア プ リ ケ ー シ ョ ン へ 応 用 す る 研 究 が 盛 ん に な っ て い る[11][15][16][17][18]． FHE の 実 用 化 に 向 け た 研 究 は シ ナ リ オ に よ っ て 1) 秘 匿 検 索 （Private Information Retrieval），2)秘 匿 暗 号 化 ，3)安 全

2 _{Amazon, http://www.amazon.com} 3 _{Google, https://www.google.com}

な 委 託 デ ー タ マ イ ニ ン グ （Secure Outsourced Data Mining） に 大 き く 分 類 で き る ．

1)秘 匿 検 索 へ の 応 用 で は ，Hu ら が 信 頼 で き な い サ ー バ に 保 存 し て い る 暗 号 化 さ れ た デ ー タ に 対 し て 距 離 に 基 づ く 類 似 検 索 に 関 す る 問 い 合 わ せ 手 法 を 提 案 し た [15]． ま た Dong と Chen は HElib を 用 い て 暗 号 化 さ れ た ビ ッ ト 列𝑋(𝑥#⋯ 𝑥L)に 対 し て ，ク エ リ 𝑞が ビ ッ ト 列 𝑋の 何 番 目𝑥>に 存 在 す る か を 検 索 す る 手 法 を 提 案 し た[16]． 2)秘 匿 暗 号 化 に 関 し て は ， López ら が 異 な る 鍵 に よ っ て 暗 号 化 さ れ た 暗 号 文 同 士 の 準 同 型 演 算 を 可 能 と し ， 複 数 の 鍵 で 複 合 す る こ と の で き る 複 数 鍵 （multikey） FHE を 提 案 し た [17]． こ れ に よ っ て 複 数 の ユ ー ザ が 保 有 す る デ ー タ の 情 報 を 他 の ユ ー ザ と サ ー バ に 漏 ら す こ と な く お 互 い の デ ー タ を 合 わ せ て デ ー タ マ イ ニ ン グ な ど の 処 理 を 行 う こ と が で き る ． 3)安 全 な 委 託 デ ー タ マ イ ニ ン グ へ の 応 用 で は ，Liu ら が Apriori を 用 い て 頻 出 パ タ ー ン マ イ ニ ン グ を ク ラ ウ ド に 情 報 を 漏 ら す こ と と な く 委 託 計 算 す る 手 法 を 提 案 し て い る[11]． ま た Chu ら は リ ン ク 構 造 の デ ー タ に お け る ノ ー ド 間 の 類 似 度 の ス コ ア と し て 知 ら れ る SimRank を FHE に よ り 秘 匿 計 算 す る 手 法 を 提 案 し た [18]． FHE の 実 用 化 に 向 け た 研 究 で は ユ ー ザ の 入 力 デ ー タ や 出 力 結 果 の 情 報 を 漏 ら さ ず に 両 方 の プ ラ イ バ シ ー を 保 証 す る こ と と ，FHE を 用 い る こ と に よ っ て 爆 発 的 に 増 加 す る 処 理 の 計 算 量 オ ー バ ヘ ッ ド を 以 下 に 小 さ く し 高 速 化 す る か が 問 題 と な る ．ま た ，FHE で は セ キ ュ リ テ ィ の 問 題 か ら 暗 号 化 し た 状 態 で 大 小 比 較 の 結 果 を 利 用 す る こ と が で き な い た め ，Apriori な ど の ア ル ゴ リ ズ ム を 実 現 す る 際 に ク ラ イ ア ン ト と サ ー バ に よ っ て 通 信 し な が ら 最 終 的 な 結 果 を 出 力 す る こ と に な る[11]． そ の た め ， い か に 通 信 に よ る 計 算 時 間 増 加 を 削 減 す る か が 鍵 と な る ． 本 稿 で 扱 う 安 全 な 委 託 デ ー タ マ イ ニ ン グ へ の 応 用 に 関 す る 研 究 で は 実 用 的 な 性 能 評 価 が 十 分 に 示 さ れ て い な い た め ， 本 稿 で は 実 用 化 に 向 け て Liu ら の 手 法 を 高 速 化 す る 手 法 を 提 案 す る ．

2.3. 安 全 な委 託 頻 出 パターンマイニング

2.3.1. 概 要

本 稿 で 対 象 と す る 安 全 な 委 託 頻 出 パ タ ー ン マ イ ニ ン グ に つ い て 説 明 す る ． デ ー タ を 保 有 す る ユ ー ザ が そ の デ ー タ か ら 有 益 な 情 報 を 獲 得 す る た め に デ ー タ マ イ ニ ン グ を 行 う 場 合 に ， 第 三 者 が 保 有 す る 計 算 機 資 源 を 利 用 す る こ と を 委 託 計 算 と 呼 ぶ ． こ の 時 ， ユ ー ザ が Amazon2や Google3，Microsoft4と い っ た ク ラ ウ ド を 提 供 す る プ ロ バ イ ダ を 完 全 に 信 用 す る こ と の で き な い 第

三 者 と 判 断 し た 場 合 ， デ ー タ や マ イ ニ ン グ 結 果 を プ ロ バ イ ダ に 知 ら れ た く な い と い う ケ ー ス が 考 え ら れ る ． そ の 場 合 ， 委 託 計 算 は 図1 に 示 す 以 下 の 手 順 で 行 う ． ① ユ ー ザ が 自 身 の ク ラ イ ア ン ト で 生 成 し た 公 開 鍵 を 用 い て デ ー タ を 暗 号 化 し ， 暗 号 化 し た デ ー タ と 公 開 鍵 を ク ラ ウ ド （ サ ー バ ） に 送 信 す る ． ② ク ラ ウ ド に お い て 暗 号 化 さ れ た デ ー タ に 対 し て 公 開 鍵 を 用 い て 復 号 す る こ と な く デ ー タ マ イ ニ ン グ を 行 う ． ③ ユ ー ザ が 暗 号 化 さ れ た 結 果 を ① で 使 用 し た 公 開 鍵 と ペ ア と な る 秘 密 鍵 に よ っ て 復 号 し マ イ ニ ン グ 結 果 を 得 る ． こ こ で ，暗 号 化 さ れ た デ ー タ を 対 象 に ，デ ー タ マ イ ニ ン グ に 関 す る 委 託 計 算 を ク ラ ウ ド 側 で FHE を 用 い て 行 う 技 術 を 安 全 な 委 託 デ ー タ マ イ ニ ン グ （Secure outsourced frequent pattern mining） と 呼 ぶ ．

図 1 安 全 な 委 託 デ ー タ マ イ ニ ン グ

2.3.2. 頻 出 パ タ ー ン マ イ ニ ン グ

本 稿 で 扱 う の は ， デ ー タ マ イ ニ ン グ の 中 で も 頻 出 パ タ ー ン マ イ ニ ン グ で あ る ．頻 出 パ タ ー ン マ イ ニ ン グ は ， 顧 客 の 購 買 行 動 分 析 や 店 舗 の 商 品 棚 の 設 計 ， 商 品 販 促 な ど の ア プ リ ケ ー シ ョ ン へ の 応 用 が 研 究 さ れ て い る ． ア イ テ ム 集 合 を𝐼 = 𝑖#, 𝑖%, ⋯ , 𝑖O ，一 回 の ト ラ ン ザ ク シ ョ ン の 識 別 子 を𝑡𝑖𝑑Q， そ の ア イ テ ム 集 合 を𝑡Q⊆ 𝐼と し て 与 え ら れ た ト ラ ン ザ ク シ ョ ン デ ー タ を 𝐷 = 𝑡𝑖𝑑#, 𝑡#, 𝑡𝑖𝑑%, 𝑡% , ⋯ , 𝑡𝑖𝑑L, 𝑡L ， ト ラ ン ザ ク シ ョ ン 𝑡𝑖𝑑L, 𝑡L に 含 ま れ る あ る ア イ テ ム 集 合（ ア イ テ ム セ ッ ト ） を パ タ ー ン𝑝 ⊆ 𝐼と す る ．ま た ，パ タ ー ン 𝑝を 含 む 𝐷の ト ラ ン ザ ク シ ョ ン 数 を パ タ ー ン𝑝の サ ポ ー ト と し ，𝑝. 𝑠𝑢𝑝𝑝 と す る ．こ の と き ，𝑝. 𝑠𝑢𝑝𝑝が ユ ー ザ の 定 め た 閾 値 で あ る ミ ニ マ ム サ ポ ー ト （𝑚𝑖𝑛𝑆𝑢𝑝） 以 上 で あ る 場 合 ， パ タ ー ン𝑝を 頻 出 パ タ ー ン と し て 抽 出 す る ． 頻 出 パ タ ー ン マ イ ニ ン グ で は ， ト ラ ン ザ ク シ ョ ン デ ー タ𝐷を ス キ ャ ン し て 頻 出 パ タ ー ン を 全 て 挙 げ る ． 代 表 的 な ア ル ゴ リ ズ ム と し て ，Apriori[34] や FP-Growth[35]が 挙 げ ら れ る ．

2.3.3. Liu ら の 手 法 :P3CC

著 者 が 知 る 限 り Liu ら が 2015 年 に 初 め て FHE を 用 い た 安 全 な 委 託 頻 出 パ タ ー ン マ イ ニ ン グ 手 法 P3CC （Privacy Preserving Protocol for Counting Candidates） を 提 案 し た[11]．Liu ら の 手 法 で は 頻 出 パ タ ー ン マ イ ニ ン グ ア ル ゴ リ ズ ム と し て Apriori を 対 象 と し た ．Apriori は ア イ テ ム セ ッ ト に 含 ま れ る ア イ テ ム 数 を そ の ア イ テ ム セ ッ ト の 長 さ と し て ，「 長 さ𝑘の 非 頻 出 ア イ テ ム セ ッ ト を 含 む 長 さ𝑘 + 1の ア イ テ ム セ ッ ト は 必 ず 非 頻 出 ア イ テ ム セ ッ ト で あ る 」 と い う コ ン セ プ ト の も と 候 補 を 絞 り な が ら ボ ト ム ア ッ プ に 頻 出 ア イ テ ム セ ッ ト を 数 え あ げ る ア ル ゴ リ ズ ム で あ る ． Liu ら の 手 法 で 用 い ら れ る ト ラ ン ザ ク シ ョ ン デ ー タ を 表1 に 示 す ． 表 1ト ラ ン ザ ク シ ョ ン デ ー タ D （Liuら 論 文Table 1[11]を ト レ ー ス ） Liu ら の 手 法 で は ， 表 1（ a） の よ う に 与 え ら れ た ト ラ ン ザ ク シ ョ ン デ ー タ D を 表 1（ b）の よ う に 各 行 を ト ラ ン ザ ク シ ョ ン ， 列 を ア イ テ ム と し て ト ラ ン ザ ク シ ョ ン に 含 ま れ て い る か を ビ ッ ト に よ っ て 表 す 行 列 に 変 換 し Apriori を 適 用 す る𝐵𝑖𝑛𝑎𝑟𝑦𝐴𝑝𝑖𝑟𝑜𝑟𝑖(𝐷, 𝑚𝑖𝑛𝑆𝑢𝑝)ア ル ゴ リ ズ ム[35][36]を 使 用 す る ． ま た ， は じ め に𝑀𝑎𝑠𝑘 𝐷 関 数 に よ っ て ト ラ ン ザ ク シ ョ ン デ ー タ𝐷の 行 列 の 列 と 行 を 入 れ 替 え る こ と で ト ラ ン ザ ク シ ョ ン 識 別 子 や ア イ テ ム 𝐼の 実 質 的 な 意 味 を 隠 し て い る ． 𝑘頻 出 ア イ テ ム セ ッ ト の 候 補 ア イ テ ム セ ッ ト 集 合 を𝐶Q，𝑘頻 出 ア イ テ ム セ ッ ト 集 合 を𝐿Qと し て ，𝐵𝑖𝑛𝑎𝑟𝑦𝐴𝑝𝑖𝑟𝑜𝑟𝑖ア ル ゴ リ ズ ム（ 以 下 ）に よ り ， 頻 出 ア イ テ ム セ ッ ト を 数 え 上 げ る ． 1. 𝐷を ス キ ャ ン し て 長 さ 1の す べ て の ア イ テ ム セ ッ ト𝑐 （ す べ て の ア イ テ ム ） の サ ポ ー ト を 𝑐𝑜𝑢𝑛𝑡𝑆𝑢𝑝𝑝𝑜𝑟𝑡 𝑐, 𝐷 関 数 で 数 え あ げ て 𝐶#と す る ． 2. 𝐶#に 含 ま れ る す べ て の ア イ テ ム セ ッ ト つ い て ， サ ポ ー ト𝑐. 𝑠𝑢𝑝𝑝が 𝑚𝑖𝑛𝑆𝑢𝑝以 上 で あ る も の を 𝐿# に 追 加 す る ． 3. 𝐿Qが 空 集 合 で な い 場 合 （ 初 期 値𝑘 = 1 ）， 𝑐𝑜𝑢𝑛𝑡𝑆𝑢𝑝𝑝𝑜𝑟𝑡 𝐿> 関 数 に よ っ て 長 さ𝑘 + 1の 候 補 ア イ テ ム セ ッ ト𝐶QZ#を 生 成 す る ． 4. {c|∀𝑐 ∈ 𝐶QZ#}に 対 し て 𝑐𝑜𝑢𝑛𝑡𝑆𝑢𝑝𝑝𝑜𝑟𝑡 𝑐, 𝐷 関 数 を 用 い サ ポ ー ト を 算 出 す る ． 5. {c|∀𝑐 ∈ 𝐶QZ#}に つ い て ，𝑐. 𝑠𝑢𝑝𝑝が 𝑚𝑖𝑛𝑆𝑢𝑝以 上 で あ る も の を𝐿QZ#に 追 加 す る ． 6. 𝑘 = 𝑘 + 1と し て ス テ ッ プ 3 に 進 む ． FHE で は 暗 号 化 し た ま ま 大 小 比 較 が で き な い（ 仮 に 比 較 が で き た と す る と 何 ら か の 情 報 が 漏 れ る こ と に 等 し い ）た め ，Liu ら の 手 法 で は ，大 小 比 較 が 必 要 な 部 分 を 一 旦 ク ラ イ ア ン ト に 返 し 判 断 す る ．つ ま り ，サ ー バ・ ク ラ イ ア ン ト 両 者 で 通 信 し な が ら 実 行 す る ． ま ず ， ク ラ イ ア ン ト 側 は ， サ ー バ 側 で サ ポ ー ト を カ

ウ ン ト す る た め に ， 公 開 鍵𝑝𝑘と 暗 号 化 さ れ た ト ラ ン ザ ク シ ョ ン デ ー タ𝐸(𝐷)を サ ー バ に 送 る ． ト ラ ン ザ ク シ ョ ン デ ー タ の 行 列 に お い て ， ト ラ ン ザ ク シ ョ ン𝑛 ∈ {0,1, … , 𝑁}に ア イ テ ム 𝑚 ∈ {0,1, … , 𝑀}が 含 ま れ て い る 場 合 を𝑛行 𝑚列 目 の 要 素 𝑥LOが 1 と す る ．P3CC で は 暗 号 化 の 際 に 表1（ c）の よ う に 行 列 で 表 さ れ る ト ラ ン ザ ク シ ョ ン デ ー タ の 一 つ の 整 数 要 素𝑥LOに 対 し て 一 つ の 暗 号 文 𝑥′LOに 暗 号 化 し た も の が𝐸(𝐷)と な る ． 次 に ，𝑐𝑜𝑢𝑛𝑡𝑆𝑢𝑝𝑝𝑜𝑟𝑡関 数 に よ り ，以 下 の ス テ ッ プ で ア イ テ ム セ ッ ト𝑐 ∈ {0,1, … , 𝑀}の サ ポ ー ト を カ ウ ン ト す る ． 1. 𝑐に 含 ま れ る ア イ テ ム 𝑚 ∈ 𝑐の 列 ベ ク ト ル (𝑥#O… 𝑥dO)eの す べ て に 対 し て ，要 素 同 士 AND 演 算 を 行 う ． 2. ス テ ッ プ 1 に よ っ て 得 ら れ た ベ ク ト ル 𝑥#O O∈f ⋯ O∈f𝑥dO eの 要 素 を 全 て 足 し 合 わ せ る こ と で𝑐の サ ポ ー ト 𝑐. 𝑠𝑢𝑝𝑝を 得 る ． ス テ ッ プ 1,2 は 論 理 演 算 に よ り 計 算 で き る の で ，FHE を 用 い て 演 算 す る こ と が で き る ． 図 2 に P3CC に お け る𝐵𝑖𝑛𝑎𝑟𝑦𝐴𝑝𝑖𝑟𝑜𝑟𝑖の 実 現 方 法 を 示 す ．図2 の よ う に ，長 さ𝑘の 候 補 ア イ テ ム セ ッ ト 集 合 𝐸𝐶 を ク ラ イ ア ン ト で 生 成 し サ ー バ に 送 る ． そ し て ， サ ー バ 側 で は ， 暗 号 化 さ れ た ト ラ ン ザ ク シ ョ ン デ ー タ𝐸(𝐷) を ス キ ャ ン し ， 候 補 ア イ テ ム セ ッ ト 集 合 に 含 ま れ る 各 々 の ア イ テ ム セ ッ ト の サ ポ ー ト を 数 え る ． し か し ， 候 補 ア イ テ ム セ ッ ト 集 合𝐸𝐶は 暗 号 化 さ れ て い な い た め ，攻 撃 者 がP3CC の ス テ ッ プ と𝐵𝑖𝑛𝑎𝑟𝑦𝐴𝑝𝑖𝑟𝑜𝑟𝑖 を 実 行 し て い る こ と が 分 か る と ， 長 さ𝑘の 頻 出 ア イ テ ム セ ッ ト を 列 挙 す る イ テ レ ー シ ョ ン の 際 に ク ラ イ ア ン ト サ イ ド か ら 送 ら れ て く る 長 さ𝑘の 候 補 ア イ テ ム セ ッ ト 集 合𝐸𝐶か ら 頻 出 ア イ テ ム セ ッ ト の 合 計 数 を 推 定 で き て し ま う 可 能 性 が あ る ．例 え ば 表 1 に お い て ，𝑎g_{, 𝑏}g_{, 𝑐}g は𝑀𝑎𝑠𝑘関 数 に よ っ て 実 際 に 何 を 表 し て い る か サ ー バ は わ か ら な い が ， 長 さ 2 の 候 補 ア イ テ ム セ ッ ト 集 合 𝐸𝐶 = { 𝑎g_{, 𝑏}g _{, 𝑏}g_{, 𝑐}g _{, {𝑎}g_{, 𝑐}g_{}}か ら 頻 出 ア イ テ ム セ ッ ト が 3} つ 存 在 す る こ と が わ か る ．そ の た め Liu ら の 手 法 で は ， ア イ テ ム セ ッ ト 集 合 に 含 ま れ る い か な る ア イ テ ム セ ッ ト も 頻 出 ア イ テ ム セ ッ ト で あ る か ど う か を α以 下 の 確 率 で し か 推 定 で き な い と い うα − 𝑝𝑎𝑡𝑡𝑒𝑟𝑛 𝑈𝑛𝑣𝑒𝑟𝑡𝑎𝑖𝑛𝑡𝑦と 呼 ぶ 考 え 方 を 導 入 し た ．α − 𝑝𝑎𝑡𝑡𝑒𝑟𝑛 𝑈𝑛𝑣𝑒𝑟𝑡𝑎𝑖𝑛𝑡𝑦を 実 現 す る た め に ， 頻 出 ア イ テ ム セ ッ ト か ら 非 頻 出 ア イ テ ム セ ッ ト へ の 1 𝛼 − 1 全 単 射 を 表 す 写 像 𝑠ℎ𝑎𝑑𝑜𝑤 𝑚𝑎𝑝𝑝𝑖𝑛𝑔𝑠 を𝑠𝑀𝑎𝑝𝑠 か ら 𝑐 の 𝑠ℎ𝑎𝑑𝑜𝑤 𝑝𝑎𝑡𝑡𝑒𝑟𝑛𝑠 を 生 成 す る 関 数 を 𝑠ℎ𝑎𝑑𝑜𝑤𝑠 𝑐, 𝑠𝑀𝑎𝑝𝑠 と す る ． 1 𝛼 − 1 全 単 射 と は ， 頻 出 ア イ テ ム セ ッ ト: 非 頻 出 ア イ テ ム セ ッ ト = 𝛼: 1 − 𝛼 の 比 で 頻 出 ア イ テ ム セ ッ ト か ら 非 頻 出 ア イ テ ム セ ッ ト へ の 写 像 す る よ う な 写 像 と な る ． つ ま り ，𝛼 = 0.5の と き𝑠𝑀𝑎𝑝𝑠は 全 単 射 と な り ，𝛼 = 1の と き 写 像 𝑠𝑀𝑎𝑝𝑠は 空 集 5 _{FIMI, http://fimi.ua.ac.be/data} 合 を 表 す ． 関 数𝑠ℎ𝑎𝑑𝑜𝑤𝑠 𝑐, 𝑠𝑀𝑎𝑝𝑠 は 候 補 ア イ テ ム セ ッ ト 𝑐 を 𝑠𝑀𝑎𝑝𝑠に よ り 写 像 し ， 𝑐の 要 素 数 の (1 − 𝛼)/𝛼倍 の 要 素 数 で あ る よ う な ア イ テ ム セ ッ ト 集 合𝑠ℎ𝑎𝑑𝑜𝑤 𝑝𝑎𝑡𝑡𝑒𝑟𝑛𝑠を 得 る ． ダ ミ ー デ ー タ で あ る ア イ テ ム セ ッ ト 集 合 𝑠ℎ𝑎𝑑𝑜𝑤 𝑝𝑎𝑡𝑡𝑒𝑟𝑛𝑠と 真 の 候 補 ア イ テ ム セ ッ ト 集 合 の 和 集 合𝐸𝐶 = {𝑐 ∪ 𝑠ℎ𝑎𝑑𝑤 𝑝𝑎𝑡𝑡𝑒𝑟𝑛𝑠}に 含 ま れ る 𝑐の 割 合 は 𝛼と な り ，α − 𝑝𝑎𝑡𝑡𝑒𝑟𝑛 𝑈𝑛𝑐𝑒𝑟𝑡𝑎𝑖𝑛𝑡𝑦を 実 現 す る こ と が で き る ． 図 2 P3CCの 概 要 図 （[11]の Fig.2 を ト レ ー ス ）

P3CC で は IBM Almaden Quest research group の ジ ェ ネ レ ー タ を 用 い て 生 成 し た 人 工 デ ー タ セ ッ ト T10I6N50D5kL1k と FIMI5_{の デ ー タ セ ッ トChess に お け}

る 実 行 時 間 の 性 の 評 価 実 験 を 行 っ た ． 同 ジ ェ ネ レ ー タ で は オ プ シ ョ ン を 与 え る こ と で 様 々 な デ ー タ セ ッ ト を 生 成 で き る ． 表 2 に デ ー タ セ ッ ト の 表 記 と 意 味 の 対 応 表 を 示 す ． 表 2 デ ー タ セ ッ ト 表 記 の 意 味 表 記 意 味 T 1 ト ラ ン ザ ク シ ョ ン あ た り の ア イ テ ム 数 I パ タ ー ン の 平 均 長 N ト ラ ン ザ ク シ ョ ン デ ー タ 中 の ア イ テ ム 数 D ト ラ ン ザ ク シ ョ ン 数(×1,000) L パ タ ー ン 数 P3CC の 性 能 評 価 実 験 で は ， HP Pavilion dm4 laptop （CPU: Core i5, ク ロ ッ ク 数 : 2.50GHz, メ モ リ : 8GB） に よ る 実 行 時 間 が 100 日 以 上 か か る と 報 告 さ れ て お り 実 用 的 で は な い ． こ れ は ， ノ イ ズ が 大 き く 準 同 型 評 価 に お け る 計 算 量 が 大 き い 整 数 ベ ー ス DGHV ス キ ー

ム[19]を 採 用 し て い る の に 加 え ， パ ッ キ ン グ を 利 用 せ ず 一 つ の 整 数 を 一 つ の 暗 号 文 に 暗 号 化 し て い る た め ， 扱 う 暗 号 文 の 数 と𝑐𝑜𝑢𝑛𝑡𝑆𝑢𝑝𝑝𝑜𝑟𝑡関 数 に お け る 演 算 数 が ト ラ ン ザ ク シ ョ ン 数𝑛，ア イ テ ム 数 𝑚の 入 力 ト ラ ン ザ ク シ ョ ン デ ー タ に 対 し𝑂(𝑛𝑚)の オ ー ダ ー で 増 加 し て い る た め と 考 え ら れ る ．ま た ，α − 𝑝𝑎𝑡𝑡𝑒𝑟𝑛 𝑈𝑛𝑣𝑒𝑟𝑡𝑎𝑖𝑛𝑡𝑦を 導 入 す る た め に ， 必 要 な 演 算 数 が1/𝛼倍 に 増 加 す る ．

3. 提 案 手 法

従 来 手 法 で あ る Liu ら の 手 法 P3CC を 高 速 化 す る た め に ， 提 案 手 法 で は ，1)FHE の ス キ ー ム と し て DGHV ス キ ー ム の 代 わ り に BGV ス キ ー ム を 用 い る こ と に よ る 高 速 化 ，2)暗 号 化 回 数 を 削 減 す る た め の SV パ ッ キ ン グ の 利 用 ， と い う ２ つ の 戦 略 を と る 。 DGHV ス キ ー ム は ，整 数 ベ ー ス の FHE ス キ ー ム で あ り ，整 数 ベ ー ス のFHE ス キ ー ム は 暗 号 文 サ イ ズ が 平 文 の 約 数 千 倍 に な る こ と や ，AND 演 算 の 際 に 任 意 制 度 算 術 演 算 な ど の 重 い 計 算 が 準 同 型 評 価 の 大 き な オ ー バ ヘ ッ ド に な る こ と ， 公 開 鍵 サ イ ズ が 大 き く な っ て し ま う こ と が 問 題 で あ る ． こ の た め ， よ り 計 算 量 を 少 な く で き るBGV ス キ ー ム を 採 用 す る ． 次 に ，P3CC で は ト ラ ン ザ ク シ ョ ン デ ー タ の 行 列𝐷の 要 素𝑥LOを 一 つ 一 つ 暗 号 化 し て い る た め ， 暗 号 文 の 数 と𝑐𝑜𝑢𝑛𝑡𝑆𝑢𝑝𝑝𝑜𝑟𝑡関 数 の 演 算 数 が 大 き く な る ．こ の 問 題 に 対 し て ，提 案 手 法 で は ，SV パ ッ キ ン グ を 用 い て ア イ テ ム ご と の 列 ベ ク ト ル を 一 つ の 暗 号 文 に 暗 号 化 す る ． こ れ に よ り ，𝑐𝑜𝑢𝑛𝑡𝑆𝑢𝑝𝑝𝑜𝑟𝑡に お け る 𝑁個 の ベ ク ト ル の 要 素 そ れ ぞ れ に 対 し て𝑁回 繰 り 返 し て い た AND 演 算 を ， 1 回 の 要 素 同 士 の ベ ク ト ルAND 演 算 に 削 減 す る ． 実 装 に は ，BGV ス キ ー ム ，SV パ ッ キ ン グ ，SV パ ッ キ ン グ を BGV ス キ ー ム で 用 い る GHS 最 適 化 が 実 装 さ れ て い る HElib を 用 い る ．

3.1. SV パッキングを用 いた暗 号 化

SV パ ッ キ ン グ は 複 数 の 整 数 を ベ ク ト ル と し て 一 つ の 暗 号 文 に 暗 号 化 し ， 一 度 の 暗 号 文 同 士 の 演 算 に よ っ て 暗 号 化 さ れ た ベ ク ト ル の 要 素 同 士 の 演 算 を 実 現 す る た め の 手 法 で あ る ．SV パ ッ キ ン グ は Smart と Vercauteren が 提 案 し た FHE ス キ ー ム の 平 文 空 間 を 平 文 の ス ロ ッ ト （plaintext slots） に 分 割 し ， そ れ ら を 要 素 と し て も つ ベ ク ト ル に 対 す る 要 素 同 士 の 準 同 型 評 価 を 可 能 と す る 手 法 で あ る ．SV パ ッ キ ン グ の 平 文 空 間 の 分 割 は 中 国 剰 余 定 理 （Chinese Remainder Theorem ） [13][28]基 づ く ． SV パ ッ キ ン グ を 用 い て 行 う 暗 号 文 の 要 素 数𝑙の ベ ク ト ル の 要 素 同 士 の 加 算 と 乗 算 を そ れ ぞ れ𝑙 − Add，𝑙 − Multと す る ．𝑝を 素 数 ， 𝑛を 2 の 冪 乘 と し て ， そ れ ぞ れ の 平 文 ス ロ ッ ト が 有 限 体𝕂z= 𝔽|}に 含 ま れ る 要 素 を 持 つ と 定 義 す る と ，二 つ の 平 文 そ れ ぞ れ の𝑙個 の 平 文 ス ロ ッ ト0, ⋯ , 𝑙 − 1は 暗 号 化 さ れ た 要 素 𝑚~⋯ 𝑚•€#∈ 𝕂L•，𝑚′~⋯ 𝑚′•€#∈ 𝕂L•を 持 つ ２ つ の 暗 号 文 に 暗 号 化 さ れ る ．こ の 時 ，𝑙 − Addは 𝑚~+ 𝑚′~, ⋯ 𝑚•€#+ 𝑚′•€#を 計 算 し ， 𝑙 − Multは 同 様 に 𝑚~∙ 𝑚′~, ⋯ 𝑚•€#∙ 𝑚′•€#を 計 算 す る よ う な 演 算 で あ る ． Ring-LWE ベ ー ス の FHE ス キ ー ム を 例 に ， 平 文 ス ロ ッ ト の 代 数 的 な 構 築 方 法 に つ い て 説 明 す る ．𝑋上 の 多 項 式 や ， そ の 多 項 式 の 根 を 要 素 に も つ 有 限 集 合 や 整 数 の 集 合 を𝐹 𝑋 で 表 す ． 𝐹 𝑋 ∈ 𝔽%は 2 を 法 と す る 整 数 を 係 数 に 持 つ N 次 元 の 最 高 次 項 の 係 数 が 1 で あ る よ う な （ モ ニ ッ ク ）多 項 式 と す る ．こ の と き𝐹 𝑋 は ，r 個 の 異 な る𝑑 = 𝑁/𝑟次 元 既 約 多 項 式 に 分 解 で き ，以 下 の よ う に 表 す こ と が で き る ． 𝐹 𝑋 ≔ 𝐹> 𝑋 . ƒ >„# (1) 実 際 に𝐹 𝑋 は ℤ上 の 多 項 式 の 2 を 法 に 関 す る 剰 余 を と っ た 既 約 な モ ニ ッ ク 多 項 式 と す る ．𝐹 𝑋 は 集 合 𝕂 = ℚ θ = ℚ X /(F)を 定 義 す る （ た だ し θを ℚの 代 数 閉 包 の 下 で 固 定 の 根 と す る ）．こ こ で ，A ≔ 𝔽%[𝑋]/(𝐹)と し て 中 国 剰 余 定 理 を 用 い る こ と で 次 の よ う な 同 型 を 得 る ． A ≅ 𝔽%𝑋 /𝐹#⊗ ⋯ ⊗ 𝔽%𝑋 /𝐹ƒ (2) ≅ 𝔽%Ž⊗ ⋯ ⊗ 𝔽_%Ž. (3) 例 え ば ，Aは r 個 の 有 限 集 合 𝔽_%Žに 同 型 で あ る ． つ ま り ，A上 の 計 算 は 𝑋に 対 し て 多 項 式 𝐹 𝑋 を 法 と し て 剰 余 を と っ た 多 項 式 演 算 で 定 義 す る こ と が で き る ． こ こ で は ，A上 で の 計 算 を 𝔽%Žの 要 素 そ れ ぞ れ に 対 す る 計 算 で き る こ と を 明 示 す る ． こ こ で ，𝜃>を𝔽%に 関 す る 代 数 閉 包 上 で𝐹> 𝑋 の 根 と し ， 補 助 的 な 表 記 と し て𝕃>≔ 𝔽%[𝑋]/(𝐹>)と す る ．全 て の 𝕃>は ， 以 下 の 形 で 同 型 性 が 与 え ら れ 集 合 と し て 同 型 で あ る ． Λ_>,‘∶ _𝛼(𝜃 𝕃>⟶ 𝕃‘ >) ⟼ 𝛼(𝜌>,‘(𝜃‘)), （ た だ し ，𝜌>,‘(𝜃‘)は 𝕃‘上 の𝐹>の 根 ） (4) こ こ で ， 全 て の𝑑の 約 数 𝑟に 対 し て 有 限 集 合 𝕂_𝑛≔ 𝔽₂𝑛 は𝔽_%Žに 含 ま れ る ．ま た ，次 元 n の 既 約 多 項 式𝐾_L∈ 𝔽_%に 対 し て𝕂Lを𝔽%𝑋 /𝐾L(𝑋)の よ う に 固 定 し て 表 す こ と を 想 定 す る が ，𝐾Lは 通 常 ア プ リ ケ ー シ ョ ン に よ っ て 決 め ら れ る ．さ ら に𝜓を 𝔽%の 代 数 閉 包 の 下 で𝐾Lの 根 と す る ． 𝕂Lは 先 に 定 義 し た𝕃>に 含 ま れ て い る た め ， 次 の よ う な 準 同 型 の 単 射 を 得 る ． 𝜓L,>∶ _{𝛼(𝜓) ⟼ 𝛼(𝜎}𝕂L⟶ 𝕃> L,>(𝜃>)), （ た だ し ，𝜎L,>(𝜃>)は 𝕃>上 の𝐾>(𝑋) の 根 ） (5) こ こ で ， こ の 写 像 は𝛼(𝜓)の 係 数 上 で 線 形 で あ る こ と に 注 意 す る ． こ の 準 同 型 単 射 を 中 国 剰 余 定 理 と 組 み 合 わ せ る こ と で ， 以 下 の よ う な𝑙 ≤ 𝑟個 の 𝕂Lか ら𝐴へ の 準 同 型 単 射 を 得 る ．

𝜓L,>∶ 𝕂L• ⟶ A 𝜅#𝜓 , ⋯ , 𝜅• 𝜓 ⟼ 𝜅> • >„# 𝜎L,> 𝑋 ∙ 𝐻> 𝑋 ∙ 𝐺> 𝑋 . (6) 多 項 式𝐻>(𝑋)と 𝐺>(𝑋)は 中 国 剰 余 定 理 に よ っ て 与 え ら れ ， 以 下 の よ う に 定 義 さ れ る ． 𝐻> 𝑋 ← 𝐹(𝑋)/𝐹> 𝑋 , 𝐺>(𝑋) ← 1/𝐻> 𝑋 (𝑚𝑜𝑑 𝐹> 𝑋 ). (7) 𝕂L•の 要 素 同 士 の 加 算 と 乗 算 を𝑙 − Add, 𝑙 − Multは ， 𝑙 − Addは 𝕂L上 で ベ ク ト ル の𝑙個 の 要 素 同 士 の 加 算 に よ っ て 計 算 で き る ． 一 方𝑙 − Multは 一 度 入 力 を 𝛤L,•に よ っ てA に 写 像 し ，A上 で 計 算 し て か ら 𝛤L,•€#に よ っ て𝕂L•へ と 逆 写 像 す る こ と で 要 素 同 士 の 乗 算 を 計 算 す る ．𝕂L•の 再 構 築 の 際 に𝛤L,•(𝕂L•)が 準 同 型 単 射 で あ る こ と か ら 𝛤L,•€#は 常 に 存 在 し 結 果 が 正 し く 定 義 さ れ る こ と に 注 意 さ れ た い ． 以 上 の よ う に 平 文 を𝑙の ス ロ ッ ト に 分 割 し ， 暗 号 文 同 士 の 要 素 ご と の 加 算 と 乗 算 が 可 能 に な る こ と を 示 し た ． さ ら に ，GHS 最 適 化 [25]で は パ ッ キ ン グ を 平 文 の ベ ク ト ル に 戻 す（Unpack）こ と な く ス ロ ッ ト 間 で 要 素 を 移 動 す る こ と を 可 能 に し た ．

3.2. ベクトル演 算 によるサポートのカウント

提 案 手 法 に お い て もP3CC と 同 じ く 表 1（ b）の よ う な 行 列 で 表 さ れ る ト ラ ン ザ ク シ ョ ン デ ー タ𝐷に 対 し て 𝐵𝑖𝑛𝑎𝑟𝑦𝐴𝑝𝑖𝑟𝑜𝑟𝑖ア ル ゴ リ ズ ム を 用 い る ． し か し P3CC で は ト ラ ン ザ ク シ ョ ン デ ー タ𝐷 の 暗 号 化 の 際 に 表 1 (c) の よ う に 行 列 の 要 素𝑥LO毎 に 暗 号 化 し て い た ． 提 案 手 法 で は ， 図 の 各 ア イ テ ム 列 ベ ク ト ル𝑣>(𝑖 ∈ 𝐼, 𝑣> = 𝑛)を SV パ ッ キ ン グ を 用 い て 暗 号 文𝑤>に 暗 号 化 す る ．こ れ に よ り 扱 う 暗 号 文 の 数 が ，P3CC で は ア イ テ ム 集 合 の 数 が𝑚で あ り ，ト ラ ン ザ ク シ ョ ン 数 が 𝑛の 入 力 デ ー タ に 対 し て𝑚×𝑛個 必 要 だ っ た の が ， 𝑚個 に 抑 え る こ と が で き る ． ま た ，𝑐𝑜𝑢𝑛𝑡𝑆𝑢𝑝𝑝𝑜𝑟𝑡に お け る ス テ ッ プ を 以 下 の よ う に ベ ク ト ル の 要 素 同 士 の 演 算 に 置 き 換 え る ． 1. ア イ テ ム セ ッ ト𝑐に 含 ま れ る ア イ テ ム 𝑚 ∈ 𝑐の 要 素 数𝑛の 列 ベ ク ト ル を 暗 号 化 し た 𝑤Oの す べ て に 対 し て ，𝑛 − Multを 行 い 要 素 同 士 の 乗 算 を 行 う ． 2. ス テ ッ プ 1 で 得 ら れ た ベ ク ト ル の 要 素 の 総 和 を 加 算 と 回 転 を 用 い て 計 算 す る totalSums[30]演 算 を す る ． こ の よ う に サ ポ ー ト を 数 え る こ と で ， ス テ ッ プ 1 で 実 行 す る 計 算 量 の オ ー ダ ー を𝑂(𝑛𝑚)か ら 𝑂(𝑚)に し ， ス テ ッ プ2 で は𝑂(𝑛)か ら 𝑂(𝑙𝑜𝑔𝑛)に す る こ と が で き る [30]．

4. 評 価 実 験

本 節 で は ， 従 来 手 法 と 提 案 手 法 の 性 能 評 価 実 験 に つ い て 述 べ る ．

4.1. データセット

評 価 実 験 で は Liu ら の 実 験 と 同 じ く IBM Almaden

Quest research group の ジ ェ ネ レ ー タ に よ り 生 成 さ れ た 人 工 の デ ー タ セ ッ トT10I6N50D100L1k を 用 い る ．

4.2. 実 験 結 果

デ ー タ セ ッ ト T10I6N50D100L1k に 対 し て ，ミ ニ マ ム サ ポ ー ト minSup (%) を 10%か ら 60%ま で 変 化 さ せ な が ら ，従 来 手 法 と 提 案 手 法 の 実 行 時 間 結 果 を 計 測 す る ． 実 験 結 果 を図 3 に 示 す ．な お ，今 回 の 実 験 に 用 い た マ シ ン の CPU は Intel(R) Xeon(R) CPU E7-8857 v2 で あ り ， メ モ リ は 512GB で あ る ． 図 3 P3CCと 提 案 手 法 の 実 行 時 間 比 較 結 果 上 図 図 3 を 見 て わ か る よ う に ，最 も 計 算 量 の 大 き い minSup が 10%の 時 に パ ッ キ ン グ を 用 い る 提 案 手 法 の 方 が パ ッ キ ン グ を 用 い な い P3CC に 比 べ 10 倍 以 上 の 高 速 化 を 示 し て い る ．ま た ，す べ て の minSup に お い て 提 案 手 法 が P3CC よ り も 高 速 化 さ れ て い る ． こ れ は ， パ ッ キ ン グ を 用 い な い P3CC で 生 成 さ れ る 暗 号 文 が 5000 個 で あ る の に 対 し ，提 案 手 法 で は 生 成 す る 暗 号 文 を 50 個 に 削 減 し て い る た め 暗 号 化 に か か る 時 間 が 削 減 さ れ て い る た め で あ る ．さ ら に ，𝑐𝑜𝑢𝑛𝑡𝑆𝑢𝑝𝑝𝑜𝑟𝑡内 部 で P3CC が 行 う 100 個 の 暗 号 文 同 士 の 乗 算 が ， 提 案 手 法 で は 一 回 の 乗 算 に 削 減 さ れ た こ と で 計 算 量 が 小 さ く な っ て い る ．

5. お わ り に

本 稿 で は ，FHE を 用 い た 安 全 な 委 託 Apriori を SV パ ッ キ ン グ を 用 い て 高 速 化 す る 手 法 を 提 案 し た ．1)提 案 手 法 で は ，HElib を 用 い て 従 来 手 法 を 実 装 し ，2)複 数 の 整 数 を ベ ク ト ル と し て 一 括 に 暗 号 化 で き る パ ッ キ ン グ を 用 い て 暗 号 文 の 個 数 と 暗 号 文 同 士 の 乗 算 を 削 減 す る こ と に よ り 高 速 化 し た ． ま た ， 人 工 の デ ー タ セ ッ ト を 用 い て 性 能 を 評 価 し た 結 果 ， パ ッ キ ン グ を 用 い な い 場 合 に 比 べ 10 倍 以 上 の 高 速 化 を 示 し た ． 本 稿 で 対 象 に し た Apriori に 限 ら ず ， パ ッ キ ン グ を 用 い た 手 法 は 秘 匿 検 索 や 他 の デ ー タ マ イ ニ ン グ ア ル ゴ リ ズ ム に 応 用 す る こ と が で き る と 考 え ら れ る ． 今 後 の 課 題 と し て は ， 1)MapReduce や Spark を 用 い た 分 散 並 列 化 に よ る 高 速 化 と ，2)FP-Growth や k-means な ど 他 の ア ル ゴ リ ズ ム 1 10 100 1000 10000 100000 10 20 30 40 50 60

実行時間（

s）

minSup(%) P3CC 提案手法

へ の 応 用 を 進 め て い き た い ．

謝 辞

本 研 究 は ，JST CREST の 支 援 を 受 け た も の で あ る ．

参 考 文 献

[1] Gellman R., “Privacy in the clouds: risks to privacy and confidentiality from cloud computing.”, World privacy forum, 2012.

[2] Rizvi S.J. and Haritsa J.R., “Maintaining data privacy in association rule mining.”, 28th VLDB, pp.682-693, 2002. [3] Wang Y. and Wu X., “Approximate inverse frequent itemset

mining: Privacy, complexity, and approximation.”, 5th ICDM, pp.8-15, 2005.

[4] Evfimievski A., Gehrke J. and Srikant R., “Limiting privacy privacy breaches in privacy preserving data mining.”, 22nd PODS, pp.211-222, 2003.

[5] Qiu L., Li Y. and Wu X., “Protecting business intelligence and customer privacy while outsourcing data mining tasks.”, Knowledge and information systems 17(1), pp.99-120, 2008. [6] Atzori M., et al., “Anonymity preserving pattern

discovery.”, The VLDB Journal 17(4), pp.703-727, 2008. [7] Verykios V.S., et al., “Association rule hiding.”, IEEE Trans.

Knowledge and Data Engineering 16(4), pp.434-447, 2004. [8] Giannotti F., et al., “Privacy-preserving mining of association rules from outsourced transaction databases.”, Systems Journal 7(3), pp.385-395, IEE, 2013.

[9] Tai C.H., Yu P.S. and Chen M.S., “k-Support anonymity based on pseudo taxonomy for outsourcing of frequent itemset mining.”, 16th SIGKDD, pp.473-482, 2010. [10] Wong W.K., et al., “Security in outsourcing of association

rule mining.”, 33rd VLDB, pp.111-122, 2007.

[11] Liu J., et al., “Secure Outsourced Frequent Pattern Mining by Fully Homomorphic Encryption.”, Big Data Analytics and Knowledge Discovery, pp.70-81, Springer International Publishing, 2015.

[12] Gentry C., “A fully homomorphic encryption scheme.”, Doctoral dissertation, Stanford University, 2009.

[13] Smart N.P. and Vercauteren F., “Fully homomorphic encryption with relatively small key and ciphertext sizes.”, PKC, pp.420-443, Springer Berlin Heidelberg, 2010. [14] Brakerski Z., Gentry C. and Vaikuntanathan V., “Fully

homomorphic encryption without bootstrapping.”, 3rd ITCS, Cryptology ePrint Archive, Report 2011/277, https://eprint.iacr.org/2011/277.pdf, 2011 (accessed on 2016-1-7)

[15] Hu H., et al., “Processing private queries over untrusted data cloud through privacy homomorphism.”, 27th ICDE, pp.601-612, 2011.

[16] Dong C. and Chen L., “A Fast Single Server Private Information Retrieval Information Retrieval Protocol with Low Communication Cost.”, Computer Security-ESORICS 2014, pp.380-399, Springer International Publishing, 2014. [17] López-Alt A., Tromer E. and Vaikuntanathan V.,

“On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption.”, 44th STOC, pp.1219-1234, ACM, 2012.

[18] Chu Y.W., et al., “Privacy-preserving SimRank over Distributed Information Network.”, 12th ICDM, pp.840-845, 2012.

[19] Van Dijk M., et al., “Fully homomorphic encryption over the integers.”, Advances in cryptology-EUROCRYPTO 2010, pp.24-43, Springer Berlin Heidelberg, 2010. [20] Gentry C. and Halevi S., “Implementing Gentry’s

fully-homomorphic encryption scheme.”, Advances in Cryptology-EUROCRYPT 2011, pp.129-148, Springer Berlin Heidelberg, 2011.

[21] Coron J.S., et al., “Fully homomorphic encryption over the integers with shorter public keys.”, Advances in Cryptology-CRYPTO 2011, pp.487-504, Springer Berlin Heidelberg, 2011.

[22] Coron J.S., et al., “Public key compression and modulus switching for fully homomorphic encryption over the integers.”, Advances in Cryptology-EUROCRYPTO 2012, pp.446-464, Springer Berlin Heidelberg, 2012.

[23] Cheon J.H., et al., “Batch fully homomorphic encryption over the integers.”, pp.315-335, 2013.

[24] Brakerski Z., “Fully homomorphic encryption without modulus switching from classical GapSVP.”, Advances in Cryptology-CRYPTO 2012, pp.868-886, Springer Berlin Heidelberg, 2012.

[25] Gentry C., Halevi S. and Smart N.P., “Fully homomorphic encryption with polylog overhead.”, Advances in Cryptology-EUROCRYPT 2012, pp.465-482, Springer Berlin Heidelberg, 2012.

[26] Brakerski Z. and Vaikuntanathan V., “Fully homomorphic encryption from ring-LWE and security for key dependent messages.”, Advances in Cryptology-CRYPTO 2011, pp.505-524, Springer Berlin Heidelberg, 2011.

[27] Hoffstein J., Pipher J. and Silverman J.H., “NTRU: A ring-based public key cryptosystem.”, Algorithmic number theory, pp.267-288, Springer Berlin Heidelberg, 1998. [28] Smart N.P. and Vercauteren F., “Fully homomorphic SIMD

operations.”, Designs, codes and cryptography 71(1), pp.57-81, 2014.

[29] Bos J.W., et al., “Improved security for a ring-based fully homomorphic encryption scheme.”, Cryptography and Coding, pp.45-64, Springer Berlin Heidelberg, 2013. [30] Halevi S. and Shoup V., “Algorithms in helib.”, Advances

in Cryptology-CRYPTO 2014, pp.554-571, Springer Berlin Heidelberg, 2014.

[31] Shoup V. and Halevi S., HElib,

http://shaih.github.io/HElib/index.html. (accessed on 2016-1-9)

[32] Hu H., et al., “Processing private queries over untrusted data cloud through privacy homomorphism.”, 27th ICDE, pp.601-612, 2011.

[33] Dong C. and Chen L., “A Fast Single Server Private Information Retrieval Protocol with Low Communication Cost.”, Computer Security-ESORICS 2014, pp.380-399, Springer International Publishing, 2014.

[34] Agrawal R. and Srikant R., “Fast algorithms for mining association rules.”, 20th VLDB, pp487-499, 1994. [35] Han J., Pei J. and Yun Y., “Mining frequent patterns without

candidate generation.”, SGMOD Record 29(2), pp.1-12, ACM, 2000.

[36] Agarwal R., Aggarwal C.C. and Prasad V.V.V., “Depth first generation of long patterns.”, 6th SIGKDD, pp.108-118, ACM, 2000.