秘匿検索技術と それを支える 高機能暗号技術 産業技術総合研究所情報技術研究部門高機能暗号研究グループ主任研究員縫田光司 シンポジウム IoT とセキュリティ 2016.3.7 1
産総研情報技術研究部門 (2015 年 5 月 1 日時点 ) 主に 暗号理論に関する最先端の知見を蓄積し 他の研究組織における情報システムの設計に入力する 2
本研究グループの活動の俯瞰 情報システムの安全な設計 安全性評価 最先端の知見の抽出 産総研他部署外部企業 機関 最新の安全性概念 最新の数学的手法 最新の攻撃手法 難解なうえに実用に遠いものも多い 成果の創出 本研究グループ ニーズの抽出シーズの提供 標準 最新暗号技術の安全性に関する知見の入力 暗号理論の国際的研究競争 NISC IPA CRYPTREC 等 最先端の暗号理論的知見を有することへの 信頼 の確立 3
秘匿検索の研究背景 近年の様々なデータベースの目覚ましい充実化 化合物データ ゲノムデータ 地質データ データベースビジネスの著しい発展が期待される 何を調べようとしているか知られたくない しかし 必要以上の情報は与えたくない * 開発中の内容やプライバシ情報が露呈してしまうため 検索内容を見せたくない * 利用者がデータベースを購入しなくなるため 利用者 検索結果以上の情報を与えたくない ジレンマの解消が急務! データベース 4
本研究の目的 利用者が検索内容を秘密にしたままデータベース内における 興味の対象となるデータの件数のみを知ることが可能な検索技術の実現と社会への展開を目指す検索内容は秘匿 利用者 データベース ヒットした件数のみ 5
例 : 生命情報解析における プライバシ保護の重要性 秘匿性の高いデータ 個人ゲノム 個人の疾患に関する情報 創薬関連の情報 ターゲットタンパク 化合物等々 プライバシ保護の問題は生命情報科学 / 工学にとって非常に重要 しかし 生命情報のプライバシ保護に関する技術開発はあまり議論されていなかった 6
2011/11/1 プレスリリース 2011/11/2 日刊工業新聞 7
安全性評価 安全性向上 効率化 高機能化 技術相談 初期版のプロトコル開発 最先端の知見の抽出 情報システムの安全な設計 安全性評価 生命情報工学研究センター ( 当時 ) 産総研他部署外部企業 機関 最新の安全性概念 最新の数学的手法 最新の攻撃手法 難解なうえに実用に遠いものも多い 成果の創出 本研究グループ ニーズの抽出シーズの提供 標準 最新暗号技術の安全性に関する知見の入力 暗号理論の国際的研究競争 NISC IPA CRYPTREC 等 最先端の暗号理論的知見を有することへの 信頼 の確立 8
通常の検索システムの危険性 9
SSL 等での暗号化通信では不足 SSL など 通信経路を暗号化する手法ではサーバー管理者からデータを保護できない 故意 / 過失によるサーバーからの情報流出 10
本研究で開発した技術 11
開発技術で可能なこと 基本技術 符号化した化合物データ 二つの同じ長さのビットベクトルが類似しているか暗号化したまま判定できる p = (1,1,1,0,0,0,1) 暗号化したまま比較 クエリ q を暗号化して送信 q = (1,0,1,0,0,0,1) 暗号化状態の結果を返信 返答を復号して検索結果を得る 12
Focused Library 検索への応用 研究者の要望 自分の研究対象と類似する化合物があるのならば購入したい 情報漏洩は絶対に避けたいので 事前にダウンロードして確かめられれば クエリの情報を漏らさずに検索し 類似化合物の個数を購入前に確認 ( 解決!) データベース販売者の要望 なるべく多くの人に買ってもらいたい でも Libraryは売り物なので 購入前にダウンロードさせることは難しい DBをダウンロードさせず 顧客のクエリ情報も得ずに検索に返答 ( 解決!)? 類似の化合物があるか? 薬の候補 個 13
基本技術 開発技術で可能なこと 二つの同じ長さのビットベクトルが類似しているか暗号化したまま判定できる p = (1,1,1,0,0,0,1) 暗号化したまま比較 どうすれば 可能? クエリ q を暗号化して送信 符号化した化合物データ q = (1,0,1,0,0,0,1) 暗号化状態の結果を返信 返答を復号して検索結果を得る 14
基盤技術 : 加法準同型暗号 [ElGamal84, Paillier99, ] Enc( m1 m2) Enc( m1) Enc( m2) 暗号化 不思議な宝箱 Enc 機能 1: オートロック数字を入れて閉めたら 鍵を使わないと絶対に開けられない 5 機能 2: 合体二つの宝箱を ( 鍵なしで ) 合体できる 中身の数字同士は加算される 7 5 暗号文の特殊な操作 12 15
原理の大まかな説明 暗号化 x g x 復号 g x x 暗号化のまま足し算 g x g y = g x+y 鍵があれば易しい 鍵がないと難しい ( ように適切に設定 ) 16
原理の大まかな説明 Enc(m1) Enc(m1) Enc(m2) 鍵がないと正しい向きがわからない ( ように作る ) m1 m2 Enc(m2) m1+m2 この向きで眺めると元のデータが得られる ( 復号 ) 17
化合物の類似検索 フィンガープリント 化合物情報をビット列で表現 1: ある特徴を持つ 0: 持たない Tversky index 化合物の類似性の評価に用いられる指標 N 対応するビットの一致を考慮した指標 0~1 の値をとる ( 大きいほど良く類似 ) HO HO H CH 3 H N NH 2 O N N= 0 1 1 1 0 1 1 0 1 0 S S Tversky tanimoto p q p q p \ q p q p q p q q \ p p q 18
加算のみでの閾値判定 0 ) ( ) ( 0 ) ( ) ( ) ( 0 q p q p q p q p q p q p q p q p S n n n n n d n d d n Tanimoto λ 共通して 1 となるビットの数サーバーの 1 のビットの数クエリの 1 のビットの数この式変形により加法準同型暗号を用いて暗号化したまま類似度閾値判定が可能 19
開発した秘匿化合物 DB 検索の概要 高速アルゴリズムの実現 実データで実証実験 (1 万データ ) 受賞 CSS2013 利用者側所持時間 DB 側処理時間通信データサイズ プロトタイプ約 30 秒約 180 秒約 2.6MB 本試験実装約 3.5 秒約 2.7 秒約 0.4MB 適切な方式選定 最新の実装技術による高速化 創薬研究者であれば誰でも本システムを利用できるような GUI の作成 20
ゼロ知識証明による安全性強化 基本方式 本研究グループの知見 正しい形式の検索要求 暗号文 中身はわからないが形式が正しいと信じる 利用者が不正なら必要以上の情報が漏れる 安全性強化版 ( 本研究グループ ) 正しい形式とは限らない 暗号文 中身はわからないが形式が正しいか検証できる +??? 必要以上の情報が漏れることはない! 21
本技術の応用 発展 (1) ( 技術を一般利用者に馴染みやすくアピールするため ) 当該技術を応用したスマートフォン電話帳データの共通要素の秘匿検索技術を開発 22
本技術の応用 発展 (2) 新たに設計した技術 : 秘匿範囲検索 ユーザ 範囲に入っているどうか調べたいが 入力は隠したままにしたい DB 応用例 秘匿位置検索 ユーザ A は範囲を指定し秘匿位置検索を行う 入力 = 範囲 : (55 ~ 71) 秘匿範囲検索 データ : 59 DB 内部のデータの値が分からない 範囲に入っているかどうかのみ判明 ユーザの入力が分からない ユーザ B の実際の位置 23
デモ画面 : 秘匿範囲検索 受賞 CSS2014 24
本技術の応用 発展 (3) 文字列データの最長一致の秘匿検索技術 ゲノムデータベースへの適用を想定 何文字目まで一致? 検索ユーザ データ所有者 A G T C G A C A C G G T A G A T C C T A G T A T A G T A G T AGTTC 入力は秘密 長さ 3 ヒット数 2 長さ 3 ヒット数 2 25
本研究グループの活動の俯瞰 最先端の知見の抽出 情報システムの安全な設計 安全性評価 大手企業 (3 社 ) ベンチャー企業 (2 社 ) 大学 研究機関 産総研他部署外部企業 機関 最新の安全性概念 最新の数学的手法 最新の攻撃手法 難解なうえに実用に遠いものも多い 暗号理論の国際的研究競争 成果の創出 本研究グループ ニーズの抽出シーズの提供 高機能暗号技術の最先端知見 準同型暗号 関数型暗号 グループ署名 ゼロ知識証明 高速実装技術 安全性評価技術 標準 最新暗号技術の安全性に関する知見の入力 NISC IPA CRYPTREC 等 26
本研究グループの活動の俯瞰 最新の安全性概念 最新の数学的手法 最新の攻撃手法 難解なうえに実用に遠いものも多い 暗号理論の国際的研究競争 成果の創出 情報システムの安全な設計 安全性評価 2015 年度成果 ( 抜粋 ) 国際会議 Best Paper Awards 2 件最先端の (IEEE TrustCom, 知見の抽出 IMA C&C) 国際暗号学会主催 3 会議論文 4 件 RSA Conference 暗号セッション論文 4 件 情報処理学会 CSS 論文賞 学生論文賞 3 件 本研究グループ ニーズの抽出シーズの提供 高機能暗号技術の最先端知見 準同型暗号 関数型暗号 グループ署名 ゼロ知識証明 高速実装技術 安全性評価技術 大手企業 (3 社 ) ベンチャー企業 (2 社 ) 大学 研究機関 産総研他部署外部企業 機関 標準 最新暗号技術の安全性に関する知見の入力 NISC IPA CRYPTREC 等 27
研究成果の例 ( 完全準同型暗号 ) 7 5 応用 加法準同型暗号 : 暗号化のまま足し算ができる 12 秘匿検索 Bioinformatics BMC Bioinformatics 高機能版 関連研究 CT-RSA 2015 完全準同型暗号 : 暗号化のまま任意の演算ができる 格子ベース (2009~) 従来法ビットのみ暗号化可 安全性解析の改良 整数ベース (2010~) 成果 1 整数に対応 EUROCRYPT 2015 成果 2 28
本研究グループの活動の俯瞰 最先端の知見の抽出 情報システムの安全な設計 安全性評価 大手企業 (3 社 ) ベンチャー企業 (2 社 ) 大学 研究機関 産総研他部署外部企業 機関 最新の安全性概念 最新の数学的手法 最新の攻撃手法 難解なうえに実用に遠いものも多い 暗号理論の国際的研究競争 成果の創出 本研究グループ ニーズの抽出シーズの提供 高機能暗号技術の最先端知見 準同型暗号 関数型暗号 グループ署名 ゼロ知識証明 高速実装技術 安全性評価技術 標準 最新暗号技術の安全性に関する知見の入力 NISC IPA CRYPTREC 等 29
安全な IoT の実現に向けた課題例 最新の安全性概念 最新の数学的手法 最新の攻撃手法 厳密かつ程々 な 難解なうえに実用に安全性指標の確立遠いものも多い 暗号理論の国際的研究競争 センシティブ情報の情報システムの安全な設計 安全性評価取得における 効率的な機器認証 プライバシ保護との両立 最先端の知見の抽出 成果の創出 本研究グループ ニーズの抽出シーズの提供 高機能暗号技術の最先端知見 準同型暗号 関数型暗号 グループ署名 ゼロ知識証明 高速実装技術 安全性評価技術 (* 個人の感想です ) 大手企業 (3 社 ) ベンチャー企業 (2 社 ) 大学 研究機関 産総研他部署外部企業 機関 標準 最新暗号技術の安全性に関する知見の入力 NISC IPA CRYPTREC 等 暗号技術の超軽量化 30