クラウドを支えるこれからの暗号技術
- 1. クラウドを支えるこれからの暗号技術 Developers Summit 2015（ 2/19 ） サイボウズ・ラボ 光成滋生
- 7. 移動中のデータ（Data in Motion） TLS, IPsec, VPN, ... : 公開鍵暗号 保管データ（Data at Rest） AES, HMAC, ... : 共通鍵暗号、ハッシュ関数 利用中のデータ（Data in Use） あまりない 今回は主にData in Useで使えそうな暗号技術の紹介 データの状態に応じた分類 7/36
- 10. 暗号化する鍵 = 復号する鍵 大昔から使われてきた暗号 鍵をどうやって共有するか？ 共通鍵暗号 Aさん Bさん 10/36
- 11. 暗号化する鍵 ≠ 復号する鍵 1970年代に発明される（RSA暗号が有名） 各自が暗号に使う鍵と復号に使う鍵の二つを使う が公開鍵 が秘密鍵 が公開鍵 が秘密鍵 公開鍵暗号 Aさん Bさん 11/36
- 12. 鍵長の増大 短い鍵の暗号は破られてしまう危険性 RSA暗号の鍵長が1024bit →2048bitと変化 RSA暗号以外の方式 鍵長が短くて安全な暗号が欲しい 楕円曲線暗号 256bit楕円曲線暗号は3072bit RSA暗号相当 一般でも使われるケースが増えている ブラウザ、ビットコイン、... アメリカ国家安全保証局（NSA）の推奨する暗号Suite Bは 楕円曲線暗号のみでRSAはない RSA暗号から楕円曲線暗号へ 12/36
- 14. 上下、左右がつながった平面世界 “楕円”ではない 楕円曲線（EC : Elliptic Curve） トーラス 14/36
- 17. 楕円曲線を使った鍵共有 𝑎𝑃, 𝑏𝑃からは𝑎𝑏𝑃は求められない ECDH（EC Diffie-Hellman） 𝑎:秘密 𝑎𝑃:公開 𝑏:秘密𝑏𝑃:公開 𝑎𝑏𝑃 𝑏𝑎𝑃 二人だけの秘密の数字を共有 Aさん Bさん 17/36
- 18. 鍵生成 Aさんの秘密鍵 𝑎 Aさんの公開鍵 𝐾𝐴 = 𝑎𝑃 メッセージ𝑀の暗号化 乱数𝑟を使って𝐸𝑛𝑐 𝐾𝐴, 𝑀 ≔ 𝑟𝑃, 𝑀 + 𝑟𝐾𝐴 復号 𝑐1, 𝑐2 ≔ (𝑟𝑃, 𝑀 + 𝑟𝐾𝐴)に対して 𝑐2 − 𝑎𝑐1 = 𝑀 + 𝑟𝐾𝐴 − 𝑎(𝑟𝑃) = 𝑀 + 𝑟𝑎𝑃 − 𝑎𝑟𝑃 = 𝑀 楕円曲線暗号 𝑀 𝑟𝑃, 𝑀 + 𝑟𝐾𝐴 𝐾𝐴 18/36
- 20. 盗聴疑惑 NSAがインターネット上の通信を盗聴、記録、分析 スノーデンが通信監視プログラム（PRISM）を告発 FBIがメールサービス提供者にRSAの秘密鍵を要求 一つの秘密鍵でそれまでの暗号文全てを復号できてしまう 前方秘匿性（PFS：Perfect Forward Secrecy） 毎回、使い捨て鍵を使おう ECDHが使われる 2011年Googleが対応 2013年頃からtwitter, facebookなどが対応 cybozu.comも対応 case 1. 鍵漏洩の被害を減らしたい 20/36
- 21. Chromeでcybozu.comにアクセス Ephemeral : はかない、一時的 ECDHE（ECDH Ephemeral）の利用例 21/36
- 23. 暗号文を復号することなくB向けに再暗号化 クラウド上で処理可能 クラウドには変換鍵𝑟𝐴→𝐵を渡す クラウドは暗号文の中身を見られない 代理人再暗号 𝑐 𝐴 𝑚 𝑐 𝐵𝑚 𝐸𝑛𝑐 𝐾 𝐴 𝑚 点線内の操作を復号せずに行う 代理人再暗号化 𝐷𝑒𝑐 𝐾 𝐴 𝐸𝑛𝑐 𝐾 𝐵 𝐷𝑒𝑐 𝐾 𝐵 𝑅𝐸𝑛𝑐 𝐴→𝐵 𝑐 𝐴 𝑐 𝐵𝑚 𝐸𝑛𝑐 𝐾 𝐴 𝑚𝐷𝑒𝑐 𝐾 𝐵 𝑅𝐸𝑛𝑐 𝐴→𝐶 𝑐 𝐶 23/36
- 24. ペアリングを使う 𝑎𝑃と𝑏𝑃から𝑎𝑏𝑃は困難だが別の世界の𝑎𝑏𝑃′は可能 𝑒 𝑎𝑃, 𝑏𝑃 = 𝑎𝑏𝑃′, 𝑃′は別の世界での一歩 代理人暗号の構成 𝑎 𝑎𝑃 𝑏𝑃 容易 無理 𝑎𝑏𝑃 𝑎𝑏𝑃’ 別世界（戻って来られない） 24/36
- 25. 初期化 𝑎 : 秘密鍵, 𝐾𝑎 ≔ 𝑎𝑃 : 公開鍵 ; ユーザごと 暗号化 𝐸𝑛𝑐 𝑀 ≔ (𝑟𝐾𝑎, 𝑀 + 𝑟𝑃′), 𝑟は乱数 通常の復号 𝑒 𝑟𝐾𝑎, 𝑃 = 𝑒 𝑟𝑎𝑃, 𝑃 = 𝑟𝑎𝑃′ 𝑀 + 𝑟𝑃′ − 1/𝑎 𝑟𝑎𝑃′ = 𝑀 変換鍵 𝑟𝐴→𝐵 ≔ 1 𝑎 𝐾𝑏 = 𝑏 𝑎 𝑃 再暗号化 𝑅𝑒𝐸𝑛𝑐 𝑟𝐾𝑎 ≔ 𝑒 𝑟𝐾𝑎, 𝑟𝐴→𝐵 = 𝑒 𝑟𝑎𝑃, 𝑏 𝑎 𝑃 = 𝑟𝑏𝑃′ = 𝑟𝐾𝑏 ′ 代理人暗号の構成（2/2） 25/36
- 27. 暗号化時に復号できる人を条件で指定する 1個の暗号鍵に対して多数の復号鍵 and, or, not対応の効率がよい関数型暗号（2010年） 属性ベース暗号（ABE : Attribute-Based Enc.） 人事部か部長だけ 閲覧許可 人事部課長 開発部部長 開発部の新人 読める 読めない 開発部 27/36
- 29. 秘密分散とペアリングの組み合わせ 秘密分散 一つのデータを複数人でシェア𝑠 = 𝑟1 + 𝑟2 とても複雑なので省略 論文と実装例 Software implimation of an Attribute-Based Encryption scheme（共著）,IEEE Transactions on Computers, 2014 http://sandia.cs.cinvestav.mx/index.php?n=Site.CPABE https://github.com/herumi/ate-pairing/ 属性ベース暗号の仕組み 29/36
- 31. 準同型 = 暗号化したまま演算する 準同型暗号（HE : Homomorphic Encryption） 123 𝑚1 = 123 𝑚2 = 654 654 777 クラウド上で 暗号化したまま足し算 777 暗号化して クラウドに委譲 計算結果を取得して復号 31/36
- 32. 暗号化（再掲） 𝐸𝑛𝑐 𝑀 = 𝑟𝑃, 𝑀 + 𝑟𝐾𝐴 ; 𝐾𝐴はAの公開鍵 𝑟は乱数 二つのメッセージ𝑀1, 𝑀2を暗号化 𝐸𝑛𝑐 𝑀1 = 𝑟1 𝑃, 𝑀1 + 𝑟1 𝐾 𝐴 𝐸𝑛𝑐 𝑀2 = (𝑟2 𝑃, 𝑀2 + 𝑟2 𝐾 𝐴) 暗号文を足してみると 𝑟1 𝑃 + 𝑟2 𝑃, 𝑀1 + 𝑟1 𝐾𝐴 + 𝑀2 + 𝑟2 𝐾𝐴 = 𝑟1 + 𝑟2 𝑃, 𝑀1 + 𝑀2 + 𝑟1 + 𝑟2 𝐾𝐴 = 𝑟′ 𝑃, 𝑀1 + 𝑀2 + 𝑟′ 𝐾𝐴 , 𝑟′ ≔ 𝑟1 + 𝑟2 = 𝐸𝑛𝑐(𝑀1 + 𝑀2) 楕円曲線暗号によるHEの実現 32/36
- 33. 加算だけ、乗算だけできるHEは1999年に登場 両方できるものが欲しい andとxorができると任意の計算が可能 2009年に登場 しかし鍵サイズが数百MB～1GB... SHE（Somewhat HE : ちょっとだけHE） 加法、乗法のみのHEより高機能 FHEよりは実用的 完全準同型暗号（FHE : Fully HE） 従来の暗号 加法HE SHE FHE 加算回数 × 任意回 十分な回数 任意回 乗算回数 × × 数回 任意回 処理性能 ◎ ○ △ × 33/36
- 34. 投票 𝑚𝑖 = 0 𝑜𝑟 1 𝐸𝑛𝑐 𝑚1 + ⋯ + 𝐸𝑛𝑐 𝑚 𝑛 = 𝐸𝑛𝑐 𝑚1 + ⋯ + 𝑚 𝑛 統計計算 平均、分散、相関など ∑𝑥𝑖, ∑ 𝑥𝑖 − 𝑚 2, ∑𝑥𝑖 𝑦𝑖などは複数回の足し算と1回の掛け算 秘匿したままマッチングや検索 指紋、DNAなどの生体情報 加法HE : （産総研）範囲指定型問い合わせに対する 効率的なデータベース秘匿検索プロトコル CSS2014最優秀デモンストレーション賞 HEの利用例 34/36