加法準同型暗号を用いたデータベースの秘匿検索
プロトコル*縫田 光司 (産総研), 清水 佳奈 (産総研), 荒井 ひろみ(理化学研究所), 浜田 道昭 (東京大学), 津田 宏治(産総研), 広川 貴次 (産総研), 花岡 悟一郎 (産総研),
佐久間 淳 (筑波大学), 浅井 潔 (産総研)2012/11/16 ＠統計数理研究所
統数研研究集会, 2012-11-16(c) Koji Nuida

1

著者一覧（再掲）
縫田 光司 (産業技術総合研究所セキュアシステム研究部門)
清水 佳奈 (産業技術総合研究所生命情報工学研究センター)
荒井 ひろみ (理化学研究所生命情報基盤研究部門)
浜田 道昭 (東京大学大学院新領域創成科学研究科)
津田 宏治 (産業技術総合研究所生命情報工学研究センター)
広川 貴次 (産業技術総合研究所生命情報工学研究センター)
花岡 悟一郎 (産業技術総合研究所セキュアシステム研究部門)
佐久間 淳 (筑波大学大学院システム情報工学研究科)
浅井 潔 (産業技術総合研究所生命情報工学研究センター)

統数研研究集会, 2012-11-16(c) Koji Nuida

2背景
例：新薬の研究開発
 まず、研究者は薬として効果がありそうな化合物組成候補を（理論や実験で）見出す 次に、その候補と似た組成の化合物（の構成法や性質など）が既に知られているか、市販の化合物データベースで検索する
 既知の化合物を利用できれば、開発コストがぐっと削減できる！
統数研研究集会, 2012-11-16(c) Koji Nuida

3背景
ユーザ（研究者）側は、市販の化合物DB購入前に、自分の欲しいデータがDBに載っているかどうか予め確認したい ユーザ側の要望：検索内容の秘匿 知財関連、個人情報・プライバシー、等 サーバ（DB）側の要望：（検索対象物の有無以外の余分な）DB内容の秘匿
両立  膨大なDB構築コストの確実な回収したい
統数研研究集会, 2012-11-16(c) Koji Nuida

4ダメな方法その１
DBの情報が漏れない♪

候補がバレちゃう…(>_<)

１ 化合物の候補を知らせる

３
統数研研究集会, 2012-11-16

ヒットの有無を２
調べる

ヒットの有無を返答する(c) Koji Nuida

5ダメな方法その２
２

DBの中身がバレちゃうo(｀ω´*)o

候補の情報が漏れない♪

ヒットの有無を調べる

１

DBの内容を知らせる（＊「Private Information Retrieval」の原理）
統数研研究集会, 2012-11-16(c) Koji Nuida

6ダメな方法その３
どんだけ待たせるの…orz

どんだけ計算させるの…orz

激しい計算と通信の嵐（一般論的な暗号プロトコル）

・・・（＊「マルチパーティ計算」「完全準同型暗号」）
統数研研究集会, 2012-11-16(c) Koji Nuida

7

惜しい方法（既存方式）
3

候補の情報が漏れない♪

JI≧閾値ならヒットと判断

１

JIの値も隠したいのに…

特別な通信プロトコル（だいぶ効率的）・・・

２

化合物同士の類似度指標（JI）の値を返す（＊EsPRESSoなど）

統数研研究集会, 2012-11-16(c) Koji Nuida

8既存方式との比較
方式

出力

通信量

ラウンド数

計算量

TPP

提案法

JIの大小小1

小無Singhら

JI

小2以上

小必要

EsPRESSoJI

小1

小無Zhangら

JI

小1

小無

マルチパー
ティ計算（一般論）

JIの大小

大2以上

大無完全準同型
暗号

JIの大小

大1

大無

本提案手法は、（計算・通信コストも配慮しつつ）類似度指標JIの値まで隠せるような初の手法
統数研研究集会, 2012-11-16(c) Koji Nuida

9技術的なポイント

統数研研究集会, 2012-11-16(c) Koji Nuida

10理想的な方法
候補の情報が漏れない♪

DBの情報が漏れない♪
化合物の候補を１ 暗号化して送る３
統数研研究集会, 2012-11-16

ヒットの有無を２ 暗号化したまま調べる

ヒットの有無を返答する(c) Koji Nuida

11理想的な方法
候補の情報が漏れない♪

DBの情報が漏れない♪

ヒットの有無をＱ．そんなことできるの？
２ 暗号化した化合物の候補を

１ 暗号化して送る

まま調べる

Ａ．（ほぼ）できます。
（「準同型暗号」）
３
統数研研究集会, 2012-11-16

ヒットの有無を返答する(c) Koji Nuida

12（加法）準同型暗号
足し算
平文

m_1

m_1 + m_2

m_2一致

公開鍵暗号化

復号

「足し算」
暗号文

m_1

m_2

m_1 + m_2

 例：Paillier暗号、(lifted) ElGamal暗号
統数研研究集会, 2012-11-16(c) Koji Nuida

13類似度指標の計算式再考
条件「JI（の一般形TI）が閾値以上」を変形「フィンガープリント」（特徴の有無を表すベクトル）

提案法の基本アイデア

左辺は（加法）準同型暗号で計算可能！
統数研研究集会, 2012-11-16(c) Koji Nuida

14提案手法（の原型）
４

候補の情報が漏れない♪

TI*≧0ならヒットと判断

TI*の値を化合物の候補を１ 暗号化して送る

２ 暗号化したまま計算

３ TI*の値を返答する
しかし、これでは既存手法と変わらない効果
統数研研究集会, 2012-11-16(c) Koji Nuida

15

提案手法
候補の情報が漏れない♪

４
TI*≧0ならヒットと判断

TIの値を隠せる♪

化合物の候補を１ 暗号化して送る

３

TI*の値を２ 暗号化したまま計算

かく乱したTI*の値を返答する

結果に影響しない範囲で真の値を隠す
統数研研究集会, 2012-11-16(c) Koji Nuida

16TIの値のかく乱方法
 対策１：ランダムなアフィン変換の導入
 TI → r・TI + s （s < r は非負の２整数） 対策２：ダミー値の導入 ランダムなダミー値（の暗号文）とその中の非負値の個数をTIとともにユーザに返送 全体の非負値の個数から教えられた個数を引けば、真の非負値の個数がわかる
理論と実験の両面からかく乱の効果を定量的評価
統数研研究集会, 2012-11-16(c) Koji Nuida

17ユーザのプロトコル逸脱攻撃
えっ！？何で！？
Σ(￣ロ￣lll)

TI*の値からDB側の特定のビットを推測可能
４

異常な範囲の入力値を１ 暗号化して送る

３

TI*の値を２ 暗号化したまま計算

かく乱したTI*の値を返答する

悪意あるユーザにDBの中身が漏れる問題
統数研研究集会, 2012-11-16(c) Koji Nuida

18

（非対話）ゼロ知識証明
 入力値が正常なことを全員が確認可能
 その際、入力値の情報が漏れることはないという要求を実現する暗号プロトコル
ユーザ
1

証明
1

証明

1億1億

統数研研究集会, 2012-11-16

処理続行

1

偽証明

サーバ

偽証明
1億
(c) Koji Nuida

処理停止
19

プロトコル逸脱攻撃への対処（ちっ・・・
失敗か・・・）

異常な範囲の入力値を１ 暗号化して送る

３

ゼロ知識証
明の正当
２
性確認
→失敗

プロトコルを中断→ユーザへ送信されない

正常な入力値だけを受理するプロトコル
統数研研究集会, 2012-11-16(c) Koji Nuida

20

まとめ
 化合物データベースの類似化合物検索について、ユーザ側・サーバ側双方の情報秘匿を考慮した検索プロトコルの提案
 （加法）準同型暗号を利用

 ユーザ側の情報秘匿は暗号化で達成

 サーバ側の情報秘匿を定量的に評価
 非対話ゼロ知識証明の利用により、異常値を含む検索語を利用した攻撃について対策
統数研研究集会, 2012-11-16(c) Koji Nuida

21

宣伝 本方式の基本プロトコルは産総研生命情報工学研究センター他が開発
 その後、暗号の知見を求められて産総研セキュアシステム研究部門（RISEC）が加入
 ダミー値、定量的評価、ゼロ知識証明、…

 産総研RISEC・次世代セキュリティ研究グ

ループでは、他組織・企業への知見提供を通した研究成果の社会還元を目指します
統数研研究集会, 2012-11-16(c) Koji Nuida

22