AIセキュリティ・プライバシーチーム
佐久間 淳
AI Security and Privacy Team Jun Sakuma◼プライバシ保護機械学習のための行列乗算■離散分布におけるAdditive汎関数の最適推定

準同型暗号上の行列乗算

Additive汎関数を推定する最も良い方法は？

I: 暗号化された行列の送信

III: 結果の暗号文の送信

IV : 復号•••

Additive汎関数) 関数𝜙𝜙: 0,1 → ℝ，離散分布𝑃𝑃 = (𝑝𝑝1 , … , 𝑝𝑝𝑘𝑘 )𝑘𝑘

II: 準同型乗算

サーバにテストデータを見せずに機械学習で予測したい- データを準同型暗号化してサーバに予測評価(行列乗算)させる
現実的な応用では、クライアントは非力、サーバへの同時アクセスが多数発生
計算効率性と同時実行時性能のバランスがとれた行列乗算が必要

多項式環の性質を利用した効率的なパッキング• k個の内積を一回の準同型乗算で実現• 紛失送信ベースの手法よりも通信帯域を98%削減• 計算能力の弱いクライアント(RasberryPie)において、AHEベースの手法よりも計算時間を23倍高速化(380sec -> 16sec)

行列乗算性能評価

𝑖𝑖=1

例: シャノンエントロピー𝜙𝜙 𝑝𝑝 = −𝑝𝑝 ln 𝑝𝑝

問題: 𝑛𝑛個の𝑃𝑃からのサンプルから𝜃𝜃 𝑃𝑃; 𝜙𝜙 を推定00年より前

現在

課題

𝒌𝒌が固定
最尤推定量が最適𝒌𝒌が大きい
特定の𝜙𝜙の最適推定量𝒌𝒌が大きい
一般の𝜙𝜙での最適推定量は？

貢献)
同時実行時性能評価 • 一般の𝜙𝜙において最適推定誤差を特徴付け•
一般の𝜙𝜙において最適推定量を構築する方法論>
10min< 50 s100x fasterthan OT with
50 clients

10x fasterthan AHE𝜃𝜃 𝑃𝑃; 𝜙𝜙 = � 𝜙𝜙 𝑝𝑝𝑖𝑖結果) 発散速度による特徴づけ′𝛼𝛼𝜙𝜙のℓ次発散速度が𝑝𝑝  ∃𝑊𝑊ℓ > 0, 𝑐𝑐ℓ , 𝑐𝑐ℓ ,′𝛼𝛼−ℓℓ
𝛼𝛼−ℓ𝑊𝑊ℓ 𝑝𝑝− 𝑐𝑐ℓ ≤ 𝜙𝜙 𝑝𝑝 ≤ 𝑊𝑊ℓ 𝑝𝑝+ 𝑐𝑐ℓ
𝜙𝜙のℓ次微分の0点付近の挙動が𝑝𝑝𝛼𝛼−ℓと同じ

𝜶𝜶ℓ Minimax risk
≤ 0 1 一致推定量なし
𝑘𝑘 20, 1⁄2 42𝛼𝛼𝑛𝑛 ln 𝑛𝑛

1⁄2 , 1 4𝑘𝑘 2
𝑘𝑘 2−2𝛼𝛼+ 𝑛𝑛𝑛𝑛 ln 𝑛𝑛 2𝛼𝛼

1, 3⁄2 6𝑘𝑘 21+𝑛𝑛 ln 𝑛𝑛 2𝛼𝛼 𝑛𝑛143⁄2,12𝑘𝑘 2
ln2 𝑘𝑘+ 𝑛𝑛𝑛𝑛 ln 𝑛𝑛 21⁄𝑛𝑛• Matrix Size: 128*128, LAN Network• 5 machines sent 200 queries each
Kazuto Fukuchi and Jun Sakuma, “Minimax Optimal Additive Functional Estimation• OT-based and AHE-based methods from SecureML.
• Somewhat HE-based method (i.e., FV scheme) from MiniONN.

More Practical Privacy-Preserving Machine Learning as A Service via Efficient
Secure Matrix Multiplication. WAHC@CCS 2018, pp. 25-36.

with Discrete Distribution: Slow Divergence Speed Case”, ISIT, pp. 1041-1045, 2018.
Kazuto Fukuchi and Jun Sakuma, “Minimax Optimal Additive Functional Estimation
with Discrete Distribution”, arxiv:1812.00001, 2018.

■Stay On-Topic: Generating Context-specific Fake
Restaurant Reviews■高レベルプログラムの値依存時相仕様検証
高レベル言語で記述されたプログラムが、プログラム実行時の値に依存した時相仕様（プログラム状態の時間発展に関する仕様）を満たすことを機械的に証明する方法を提案（例えば、プログラムのならし計算量の解析が可能に）★やったこと
日本での食べログのような、レストランの評判情報をターゲットとしたフェイクレビューを自動生成する攻撃手法の提案と、そのようなフェイクレビューの検出方法を提案★アイディアレストラン評判情報のコンテクスト（星の数、レストラン名、カテゴリ、場所等）とそのレストランのレビューを多数収集して対訳コーパスとする。ニューラル機械翻訳技術により、コンテクストをレビューに機械翻訳する⇒フェイクレビューの生成。
+
Input context

Embedding

EncoderRNN

DecoderRNN

Generator

Attention

Beam search

Output review

Type

★結果

Detection rate

F-scoreHuman-written

63%

59%

Machine-generated

50%

53%

通常の被験者、懐疑的な被験者ともに、機械翻訳で生成したフェイクレビューと人間が生成したレビューの見分けがつかなかった。
特徴量を工夫することで、フェイクと人間のレビューの区別をつけることは可能（ただし万能な対策ではない）“Stay On-Topic: Generating Context-specific Fake Restaurant Reviews,”
Proceedings of ESORICS 2018, pp. 132–151, September 2018

高レベルプログラムの例：（OCaml言語による）リストの対を用いたキューの実装(* リストの反転関数 *)let rev l = let rec aux l acc = match lwith| [] -> acc | h::t -> event[Tick];
aux t (h::acc)
in aux l [](* エンキュー関数 *)let enqueue e (l1,l2) = event[Enq];(l1,e::l2)(* デキュー関数 *)let rec dequeue (l1,l2) = match l1 with
| e::l1' -> event[Deq]; (e, (l1', l2))
| [] -> dequeue (rev l2, [])(* キューが空になるまで非決定的にエンキューかデキューを繰り返すメイン関数 *)let main () = let rec loop (l1,l2) =if * then loop (enqueue 42 (l1,l2))
else if is_empty (l1,l2) then ()else loop (snd (dequeue (l1,l2)))
in loop ([], [])プログラム中のevent[a]を実行するとイベントaが発生
左のプログラムの main () を実行すると例えば以下のようなイベント列が非決定的に生成される：
Enq, Enq, Tick, Tick, Deq, Deq
Enq, Tick, Deq, Enq, Tick, Deq
Enq, Enq, Tick, Tick, Deq, Deq, Enq, Tick, Deq
値依存時相仕様の例：#𝐓𝐓𝐓𝐓𝐓𝐓𝐓𝐓 𝑥𝑥=1#𝐃𝐃𝐃𝐃𝐃𝐃 𝑥𝑥
ここで #𝑎𝑎 𝑥𝑥 はイベント列 𝑥𝑥 にイベント 𝑎𝑎が出現する回数を表す
つまり、上記仕様はプログラムの実行によって生成されるイベント列 𝑥𝑥 が空でなければ、デキューによって引き起こされるリストの反転にかかる計算回数とデキューの回数の比が定数で抑えられることを表す
𝜆𝜆𝜆𝜆 ∈ Σ ∗ . 𝑥𝑥 ≠ 𝜖𝜖 ⇒?

𝑃𝑃 ⊨ Φ

プログラム𝑷𝑷 が仕様 𝚽𝚽 を満たすことを検査するために以下の2つの形式体系を提案(1) 依存リファインメント型・エフェクトシステム• プログラム𝑃𝑃 が仕様 Φ を満たすことの判定問題を不動点論理ℒの妥当性判定問題に帰着(2) 不動点論理 ℒ の妥当性判定のための演繹体系
過大近似• 論理式中の不動点を右表の技術を用いて過大・過小近似して消去 最小不動点 不変条件 (帰納法)• 不動点を含まない論理式の妥当性を既存の定理証明器により判定 最大不動点 不変条件 + 整礎関係

過小近似
不変条件 + 整礎関係
不変条件 (余帰納法)

現在、本成果をベースに確率的プログラムのプライバシー検証法を研究中
A Fixpoint Logic and Dependent Effects for Temporal Property Verification. LICS
2018, pp. 759-768.