完全準同型暗号を用いたFP-growthによる委託頻出パターンマイニングの改善に関する一検討

全文

(1)情報処理学会第 82 回全国大会. 6Y-03. 完全準同型暗号を用いた FP-growth による委託頻出パターンマイニングの改善に関する一検討種村真由子 †. 小口正人 †. † お茶の水女子大学 1.. FHE の実装の 1 つとして，Brakerski(2014) らによって提唱. はじめに. された Leveled FHE があり，これは決まった深さ L の論理回路. 近年，ビッグデータの収集・分析により，ビジネスを中心とす. の結果を評価することができる [7]．本研究ではこれを使用する．. る多くの分野で利活用が進んでいる．大規模なデータを扱う統. 復号不可になることなくより多くの計算を行うためには，暗号. 計処理を行う際，処理能力の高い計算機システムを用意する事. 文のパラメータとして高いレベルを設定する必要があるが，そ. が困難な場合には，クラウド等の外部の計算資源を利用する方. の分暗号文のサイズも大きくなるという特徴がある．. 法があるが，外部委託するデータが個人情報等，プライバシーに関わる場合は，特に管理に注意する必要がある．本研究では，プ. 3.. 頻出パターンマイニング. ライバシー保護のため，外部サーバに送信するデータを完全準. 3.1. 頻出パターンマイニングの概要. 頻出パターンマイニングは，データマイニングの一種であり，. 同型暗号 (Fully Homomorphic Encryption，FHE)[1] で暗号化する．FHE は，暗号文同士の加算と乗算が成立する公開鍵暗号. 大量のデータの中から，頻出であるアイテムセットを抽出し，相. で，委託先サーバに復号鍵を渡さず，統計処理を行うことが可能. 関ルールを見出すことを目的とした手法である．頻出であるこ. となる．これを用いて，頻出パターンマイニングを行うシステム. との判定には，サポート値を用いる．サポート値は，全体のト. を作成する．また，頻出パターンマイニングには代表的なアル. ランザクション数に対する，あるアイテムセットが含まれるト. ゴリズムとして Apriori と FP-growth がある．FHE と頻出パ. ランザクション数の割合で表される．各アイテムセットのサポ. ターンマイニングを組み合わせた関連研究として，Apriori を使. ート値があらかじめ指定したミニマムサポート値以上であれば. 用した Liu ら (2015) の P3CC(Privacy Preserving Protocolfor. 頻出とする．代表的なアルゴリズムとして，先行研究で使用さ. Counting Candidates)[2] という手法がある．また，P3CC を SV(Smart-Vercauteren) パッキングや暗号文のキャッシュを利用し高速化した例 [3][4] や，サーバ側の分散処理化を行った例 [5] もある．本研究では，これらの先行研究において Apriori アルゴリズムで処理している部分を FP-growth に変更した頻出パターンマイ. れている Apriori と，本研究で使用している FP-growth がある．. ニングのシステムの実装を行っている．現行のプログラムから，. を再帰的に走査することで結果を求めるアルゴリズムである [8]．. Apriori は，アイテム数 1 から小さい順に頻出アイテムの組み合わせを挙げていく方式である．. 3.2. FP-growth. FP-growth は，データベースを走査し，トランザクションデータを FP-tree という prefix tree の木構造に格納，その部分木. クライアント側の負荷を抑えつつ，さらにサーバに処理を委託. 頻出アイテムセットの候補を列挙しない点で Apriori と大きく. する方法を検討する．. 異なる．データの特性にも依存するが，頻出アイテムの列挙がボ. 2.. トルネックになる Apriori と比較して，探索を効率化できるとい. 完全準同型暗号. 完全準同型暗号 (FHE) は，加法準同型性と乗法準同型性の特徴をあわせ持った，すなわち，暗号化した状態での暗号文同. う期待がある．. 4.. 士の加算，乗算が成立する公開鍵暗号の一方式である．FHE の. システム概要. クライアント・サーバ型のデータの委託処理システムを実装. 概念そのものは Rivest ら (1978) によって提案されており [6]，. した．クライアント側には秘密鍵，公開鍵があり，サーバ側には. Gentry(2009) が実現手法を提案した [1]．各暗号文には，暗号の. 公開鍵のみがある．サーバ側はマスタ・ワーカ型の分散・並列処. 解読不可能性を高めるため，ランダムなノイズが付加されてい. 理を行うことができる．FHE を扱うためのライブラリは HElib，. る．問題点としては，一般に暗号文と鍵のデータサイズが大きい. 分散・並列処理のライブラリは Open MPI を使用している．現. ことにより処理の計算量が膨大になることと，ノイズの値が暗. 行のシステムでの処理手順の概要は以下の通りである．. 号文同士の計算を行うたびに増加し，閾値を超えると復号不可となること，比較演算が困難であることが挙げられる．ノイズの値は，特に乗算を行った際に大きく増加する．. 1. サーバ側で通信の受付を行い，クライアントと接続する． 2. クライアントでデータを FHE で暗号化し，アイテム ID，ミニマムサポート値と共にサーバに送信する．. A Study about Improvement of Outsourcing Frequent Pattern Mining Using Fully Homomorphic Encryption Mayuko Tanemura† Masato Oguchi† †Ochanomizu University. 3-417. 3. クライアントから暗号文データを受信し，各アイテムのサポート値を計算した結果をクライアントに返送する．. 4. サーバから受信したファイルを復号し，アイテムごとのサポート値がミニマムサポート値以上となっていたアイ. Copyright 2020 Information Processing Society of Japan. All Rights Reserved..

(2) 情報処理学会第 82 回全国大会. テムを抽出し，FP-tree を構築する． 5. 構築した FP-tree の走査を行い，結果を出力する．. という処理の追加を検討する．この値の正負をクライアント側で判定することにより，アイテムが頻出であるかを判断する．つまり，各アイテムの頻出／非頻出の判定処理の一部をサーバが. 5.. 実験. 担う事になる．現行のプログラムと比較して，暗号文に対して行. 5.1. 実験概要. う処理が増えるため，必要なレベルは大きくなり，実行時間も⻑. 本研究のプログラムは，暗号文に付随するレベルというパラメ. くなると考えられる．しかし，追加される暗号文の演算は加減算. ータに実行時間が左右されることが分かっている．実装の改善を. のみであるため，ノイズの増え方は少なく，暗号文に必要なレベ. 検討するにあたり，暗号文のレベルの値を変化させる必要が出. ルは大きく増加しない見込みである．したがって，実行時間を抑. てくると考えられるため，現行のプログラムを用いて，レベルに. えつつ，新たに委託処理を追加することができると考えられる．. よる実行時間の傾向を把握することを目的として，実験を行う．. 7.. 5.2. 実験方法. 同一ネットワーク内の 2 台のマシンを用いて，各マシン上でクライアントプログラムとサーバプログラムを動作させた．暗号文のレベルを 3 から 17 まで変化させ，実行時間を測定する．各値に対して 5 回測定し，その平均をとる．. 5.3. まとめと今後の予定. 完全準同型暗号を用いた FP-growth において，暗号文のレベルによる実行を抑えつつ，サーバへの委託処理を増加させる方法を検討した．今後は，新しい実装によるシステムを使用した際の実行時間，各マシンの使用リソースなどの測定を行なっていきたいと考えている．. 実験環境. 実験で用いた計算機は，OS は CentOS6.9，CPU は Intel®. Xeon® プロセッサー E5-2643 v3，メモリが 512GB である．クライアント，サーバとして同型のマシンを 1 台ずつ使用した．使用した入力データは，IBM Quest Synthetic DataGenerator で生成した人工データであり，アイテム数は 30，トランザクション数は 9900 である．本実験では分散処理は行っていない． 5.4 実験結果. 謝辞本研究は一部，JST CREST JPMJCR1503 の支援を受けたものである．. 参考文献. 計測結果を以下の図 1 に示す．all が全体の実行時間，master がサーバにおける実行時間，comm が通信にかかった時間である．レベルの変化に伴い，暗号文で計算を行うサーバ側での処理時間が増加しており，また，全体の実行時間に対する割合が増加していることがわかり，レベル 17 の時点では 57.50% に及ぶ．通信時間もレベルの増加に伴って⻑くなるが，レベル 17 の時点での割合は，13.28% ほどである．. [1] C. Gentry, ”A Fully Homomorphic Encryption Scheme, Doctoral dissertation,” 2009. [2] J. Liu, J. Li, S. Xu, and B. CM Fung, ”Secure outsourced frequent pattern mining by fully homomorphic encryption”, In International Conference on Big Data Analytics and Knowledge Discovery, pp. 70–81. Springer, 2015. [3] 高橋卓⺒, 石巻優, 山名早人, ”SV パッキングによる完全準同型暗号を用いた安全な委託 Apriori 高速化,” DEIM Forum 2016 F8-6, 2016. [4] 今林広樹, 石巻優, 馬屋原昂, 佐藤宏樹, 山名早人, ” 完全準同型暗号による安全頻出パターンマイニング計算量効率化,” 情報処理学会論文誌データベース (TOD), Vol. 10,. No. 1, 2017. [5] 山本百合, 小口正人, ” 完全準同型暗号を用いた秘匿データマイニング計算のデータベース更新時の分散処理による高速化,” DICOMO2018, 2018.. 図1 全体とサーバ側での実行時間，通信時間. 新たな処理を実装する際には，多少通信が多くなっても必要レベルを低く抑えることのできる手法を用いることが，実行時間短縮とリソースの有効活用のための 1 つの方法であると考えられる．. 6.. 新規検討手法. 現行システムの改善のため，4 章で示す処理手順の 3 においてクライアントにサポート値の計算結果を返送する前に，サーバ上で各アイテムのサポート値とミニマムサポート値の差をとる. 3-418. [6] R. L. Rivest et al., “On data banks and privacy homomorphisms,”Foundations of secure computation, vol. 4, no. 11, 1978, pp. 169–180. [7] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan: (Leveled) Fully Homomorphic Encryption without Bootstrapping. ACM Trans. Comput. Theory 6, 3, Article 13 (July 2014), 36 pages, 2014 [8] J. Han, J. Pei, and Y. Yin, “Mining Frequent Patterns WithoutCandidate Generation,”in Proceedings of the 2000 ACM SIGMODInternational Conference on Management of Data, ser. SIGMOD ʼ00.New York, NY, USA: ACM, 2000, pp. 1–12. [Online]. Available:http://doi.acm.org/10.1145/342009.335372. Copyright 2020 Information Processing Society of Japan. All Rights Reserved..

(3)