処理性能

システム全体の処理性能に大きな影響を与えると考えられるID管理組織-商店間プロト コルおよび商店-訪問者間プロトコルを実装し，その処理性能を評価した．4.6.1節で述べ たように，ID管理組織-商店間プロトコルの処理性能は冪乗余の計算にかかる時間が支配 的である．たとえば，表4.11に示したように，冪乗余の回数はN W L回にも及ぶため，

仮に1回の冪剰余にかかる計算時間が数[ms]であっても100年以上かかってしまう．分 散環境対応スムージングと匿名加工の処理時間は，ID管理組織または商店においてオフ ラインで処理することができ，両者を合わせても数時間であることから全体の処理性能に 影響しない．そこで次節では，処理性能を明らかにするために行った実装と，これとは別 に推薦精度を明らかにするために行った実装について述べる．

7.4.1 実装

実験はIntel Xeon E5-2697 v4 (2.30GHz, 18 cores)のCPUを2台と512GByteのメモ リを搭載したPCで行った．OSはLinuxのUbuntu 18.04で，Python3のAnaconda(科学 技術計算用パッケージ)を用いた．

処理性能を明らかにするために，ID管理組織-商店間プロトコルおよび商店-訪問者間プ ロトコルを以下の6つのプログラムで実装した．

workerプログラム(60行)

引数を解析して実験を開始する．

eval dataプログラム(60行)

データを読み込んで，ID管理組織-商店間プロトコル，商店での推薦に備えた学習，

商店-訪問者間プロトコル，訪問者への推薦の順に実行する．

secure matchingプログラム(66行)

ID管理組織-商店間プロトコルの自作クラスである．Crypto(暗号)ライブラリの SHA256関数とrandint関数を利用している．また，gmpy2(任意精度演算)ライブ ラリのmpz(多倍長整数)型とnext prime関数を利用している．

providerプログラム(20行)

ID管理組織が商店からのリクエストに応える．

shopプログラム(76行)

商店がID管理組織からクロス集計表を手に入れ，推薦に備えて学習する．そして，

商店が訪問者からのリクエストに応える．

guestプログラム(52行)

訪問者が商店から推薦を受ける．phe(準同型案号)ライブラリのpaillierクラスを 利用している．

処理性能を左右する暗号関連のライブラリは個別のプログラムに対応させて記載したが，

プログラムを簡潔に記述するためにmath, numpy, itertoolsなどの一般的なライブラリも 用いている．なお，ベンチマークは繰り返し計測を行う必要があるため，該当する箇所の

みをtimeitライブラリで計測した．

推薦精度を明らかにするために，NS, MK, PSの手法を以下の4つのプログラムで実装 した．

estimateプログラム(134行)

下記の3つの手法を動作させるプログラムである．各手法へ渡すデータにラプラス ノイズを付加するために，scipyライブラリのlaplace関数を利用している．

naive bayesプログラム(54行)

ナイーブベイズの手法の実装である．

minkaプログラム(110行)

Minkaの手法の実装である．scipyライブラリのgamma関数とdigamma関数を利 用している．

secure smoothingプログラム(124行)

提案手法(分散環境対応スムージング)の実装である．

推薦精度を左右する数学関連のライブラリは個別のプログラムに対応させて記載したが，

プログラムを簡潔に記述するために一般的なライブラリも用いている．なお，次数や安全 性などの条件を変えながら推薦精度を測定する必要があるため，上記のプログラムおよび データの入出力を並列で処理できるようにして実験の効率化を図っているが，これについ ては本質ではないので割愛する．

7.4.2 処理時間

提案方式による処理性能を明らかにするため，計算量の一般式と本論文でのユースケー スの想定における処理時間を表7.2にまとめる．1回の冪剰余にかかる計算時間を3.8[ms]

とし^*1，並列計算は行っていない．

*1 訪問者については，携帯端末を使わずにPCでエミュレートしたため，ID管理組織-商店間プロトコルと 商店-訪問者間プロトコルでの1回の冪剰余にかかる計算時間は同じとして見積もっている

表7.2 冪乗余の回数と処理時間

登場人物 Vaidyaらの方式[55] 提案方式

ID管理組織 N V L N W +M GV

(約2.5×10⁶日) (約16日)

商店

N V L M G+N W L (約2.5×10⁶日) (約1.3×10⁵ 日)

- V L

(約36分)

訪問者 - 1 + 2V +L

(約38秒)

Vaidyaらの方式[55]は3者間での運用を想定していないので，ID管理組織-商店間の

みを考慮する^*2．Vaidyaらの方式はID管理組織と商店でそれぞれN V L回の冪乗余が必 要となる^*3．提案方式はN W L回の冪乗余が支配的である．処理性能において提案方式

がVaidyaらの方式よりも優れる理由は，冪乗余の回数をO(N V L)から O(N W L)に減

らせるところにある．属性の項目は2種類以上の値を取る(1種類の値しかない属性の項 目には意味が無い)ので，属性値の種類数Vは属性の種類数Wの少なくとも 2倍以上で ある．よって，提案方式の処理性能はVaidyaらの方式より2倍以上優れる．

ID管理組織-商店プロトコルの処理性能について，提案方式はVaidyaらの方式よりも高 速であるが，商店でのN W Lの冪乗余がボトルネックとなるため^*4，このままではT₁(1ヶ 月)以内の要件を満たすことができない(表7.2)．ただし，この問題は一般的になりつつあ るマルチコアCPUやクラウド環境の利用などにより解決できる．たとえば，商品数が1 万種類に及ぶチェーン店や大規模な商店であっても，16コアのマルチコアCPUを6個用 いて96倍の高速化を行うとすると，100万人の会員を有するID管理組織とT1(1ヶ月)以 内の要件を満たすことができる．商品数が1,000種類程度の中規模の商店であれば1,000 万人の会員を有するID管理組織と，商品数が100種類程度の小規模の商店であれば1億

*2 Vaidyaらの方式は秘匿内積を用いている．提案方式の商店-訪問者プロトコルも秘匿内積を用いているの

で，仮にVaidyaらの方式を商店-訪問者プロトコルに適用した場合の冪乗余の回数は，提案方式と同等で

ある．

*3 長さVのベクトルの積集合を求める場合，提案方式のID管理組織-商店プロトコルでは，ベクトルに値 が入っている要素(W個)のみを冪乗余すれば良いが，Vaidyaらの方式が用いている秘匿内積では，ベク トルの全ての要素(V個)を冪乗余する必要がある．

*4 ID管理組織と商店での処理は並行できるので，商店の冪乗余がボトルネックとなる．

図7.2 処理性能を満たす条件(商店でのM G+N W L回の冪乗余にかかる期間．1人 あたりの商品の種類数G= 10,プロファイルの値の種類数W = 3，シングルコアの場 合)，緑の領域は条件を満たし，赤の領域は満たさない．

人の会員を有するID管理組織とT1(1ヶ月)以内の要件を満たすことができる．以上のこ とから，提案システムは条件によってT₁(1ヶ月)以内という“(要件3a) ID管理組織-商店 間の処理性能の要件”を満たす．

なお，T1 を1ヶ月から1週間に変更する場合は，商店は費用をかけて約4倍の性能の CPUに買い換える必要が生じる．逆にT₁ を1ヶ月から3ヶ月に変更する場合は，商店は 1/3倍の性能のCPUで足りるため，CPUの買い替えは不要で若干電気代が減少すると考 えられる．

商店-訪問者プロトコルの処理性能について，商店と訪問者のいずれでも，このままでは T₂(5秒)以内の要件を満たすことができない．ここでは素早いレスポンスが求められるた め，外部のクラウドを利用する事は難しい．この問題は，商店における一般的な多コア CPUの利用と，ユースケースに則した計算上の工夫により解決できる．商店のPC(16コ

アのCPUを搭載していると想定)を用いて16並列で冪乗余する．さらに，L= 10⁴ 種類 ある商品を100種類ずつに100分割して，ユーザが100種類の商品を眺めている間に次 の100種類の商品の推薦を計算する．これらの工夫により，商店での処理を1,600倍，訪 問者での処理を100倍高速化する．すると，商店での処理を約36分から約1.4秒に，訪 問者での処理を約38秒から約0.4秒に短縮でき，両者を合わせても約1.8秒なのでT₂(5 秒)以内の要件を満たすことができる．以上のことから，提案システムはT₂(5秒)以内と いう“(要件3b)商店-訪問者間の処理性能の要件”を満たす．

なお，ハードウェアの進歩により，ID管理組織-商店間の月次処理や，商店-訪問者間で 一度に推薦できる商品の種類は，今後増やしていけると考えられる．