Proxy Re-Encryption(PRE)とNuCypher
Release
v0.1.0-alpha.0 (Genesis Release)
この記事はなに
共通鍵暗号鍵・公開鍵暗号の復習
Proxy Re-Encryption(代理再暗号化・PRE)入門
NuCypherのオーバービュー
NuCypherのアルゴリズム
復習
具体的なアルゴリズムまでは深入りせず、プロトコルのレベルで。
共通鍵暗号(symmetric key encryption, SKE)
復号化と暗号化を同じ鍵で行う暗号プロトコルを共通鍵暗号と呼ぶ。
受信者と送信者で共有する鍵を $ dec とし、平文を$ d, $ cを暗号化された文とした場合、共通鍵暗号では
$ c = encrypt_{sym}(dec, d)
$ d = decrypt_{sym}(dec, c)
という形で復号化・暗号化が行われる
公開鍵暗号(public key encryption, PKE)
公開鍵暗号では、まず送信者(sender)と受信者(receiver) がそれぞれキーペア $ sk_s / pk_s, $ sk_r / pk_rを用意しておく。$ p_\ast を公開鍵(pubic key)、 $ s_\astを秘密鍵(secret key)と呼ぶ。
暗号化の際は、まず受信者があらかじめ公開鍵$ p_r を送信者に渡しておく。そのうえで送信者は、暗号文が受信者の(公開されていない)秘密鍵でのみ復号化出来るように暗号化する:
$ c = encrypt_{pke}(d, pk_r)
$ d = decrypt_{pke}(c, sk_r)
PKE + SKEのハイブリッド
上で紹介した2つの暗号プロトコルを組み合わせることも出来る。
まず暗号化のフェーズ。テキトウに乱数を取得して、それを共通鍵だとして平文を暗号化。そしてその乱数を受信者に送るために受信者の公開鍵で暗号化。
$ dec = {random}()
$ c = encrypt_{sym}(dec, d)
$ edec = encrypt_{pke}(dec, pk_r)
結果として得られたペア $ (c, edec) を受信者に送信。
復号化はまず、共通鍵(公開鍵で暗号化された乱数)を復号化し、それを用いて暗号文$ cを復号化する:
$ dec = decrypt_{pke}(edec, sk_r)
$ d = decrypt_{sym}(dec, c)
mosa_siru.icon< おそらく次回以降共通鍵のみで復号できるのが嬉しみかも
moonty_sal.icon <セッションごとに共通鍵は再生成する気がする、共通鍵での暗号化復号化と公開鍵暗号での暗号化復号化の計算コストは共通鍵が1に対して公開鍵が1000くらいらしいので、単純に其のコストを減らしたい?のかな。
代理再暗号化 (Proxy Re-Encryption, PRE)入門
Motivation
クラウドにデータを生のままで置くのはセンシティブなデータだとキツイ
A more realistic premise is to assume that the attackers have potential access to users’ data
攻撃者がサーバーに不正にアクセスし得る、という前提に立とう
そのような仮定の元だと、自分のローカルにある鍵で暗号化したやつ後のデータをクラウドにおいて保管するしかないよね
プロバイダーにすら復号鍵は渡さない、という前提に立ちたいよね
でもそうすると、データを「シェア」「検索」「計算」したり出来なくなるから、サービスとして終わってしまうよね
なんとかしたいね
暗号化されたデータ上の「検索」「計算」はちょっとchallengingだからおいといて、せめてシェア問題だけは解決したいね
PREの基本的な仕組み
Proxy Re-Encryptionは一言で言うと、「暗号文を復号せずに、暗号文の受信者を変更することが出来る」公開鍵暗号方式の一種。
https://gyazo.com/f6b26636e82a477da20abaeea4eb5f25
Aliceの公開鍵 $ pk_A に対して暗号化された文書 $ c_A = Enc(pk_A, m)が(Proxy)サーバーに置かれているとする。Aliceはこの暗号文をサーバーが解読することなく、Bobの秘密鍵$ sk_Bで復号化出来るようにしたい。
Aliceは自分の秘密鍵$ sk_AとBobの公開鍵$ pk_Bを用いて、再暗号鍵 $ rk_{A\rightarrow B} = rekey(sk_A, pk_B)を作成し、サーバーに送信する。
サーバーは$ rk_{A\rightarrow B}を用いて、ボブの秘密鍵$ sk_Bで復号化出来るように$ c_Aを再暗号化する:
$ c_B = reencrypt(rk_{A \rightarrow B}, c_A)
$ m = decrypt(sk_B, c_B)
PRE compared to PKE
従来のPKEに比べてPREは N-to-Nのコミュニケーションに向いている
事前に暗号化する相手を知る必要が無いので。
これはblockchain, IotT, Big Dataの環境だと良いよね(バズワード並べてるだけでは)と述べている
(WP 6ページ目下部)
鍵の再利用性
一度$ rk_{A \rightarrow B}を作ってしまえばあとは面倒な作業は全部プロキシがやってくれる
最初に参加者の最暗号鍵ばらまいとくなど。
なのでProxyはコントラクトと相性よいかも
署名も付けられるヨ
variety of PRE algorithms related to NuCypher
(BBS98)Divertible Protocols andAtomic Proxy Cryptography
PREの最初の論文。👆の基本的な仕組みはこの論文のプロトコル。
(ECIES)ANSI X9.63 Public key cryptography for the Financial Services Industry: Elliptic curve key agreement and key transport schemes
ftp://ftp.iks-jena.de/mitarb/lutz/standards/ansi/X9/x963-7-5-98.pdf
(BBS98)がベース
下のUMBRALがベースとした論文(?, 仕様書)。
ANSI(American National Standards Institute) が策定したもの。
そのサマリ
(AFGH)Improved Proxy Re-Encryption Schemes with Applications to Secure Distributed Storage
UMBRAL: A THRESHOLD PROXY RE-ENCRYPTION SCHEME
NuCypherのfirst versionで使っているPREアルゴリズム
N個のsemi-trustedなプロキシサーバーがあって、そのうちT個がre-encryptionに参加すれば受け手が復号化出来るような仕組み。
Introducing goUmbral
(依存パッケージ管理してないし、README間違ってる)
ここ数ヶ月コミット無いけどgoUmbralの開発ってまだactive? ってチャットで聞いたら Yeah!! って返ってきた(?)
PRE's properties
Interactivity
再暗号鍵$ rk_{A \rightarrow B} を作る際に、Bの秘密鍵$ sk_Bを使う方式を Interactive-PREと呼ぶ
そうでないものをNon-Interactive-PREと呼ぶ
(BBS98)や(ECIES)はInteractive
(AFGH)はNon-Interactive
Bi-directionality
再暗号鍵$ rk_{A \rightarrow B}から$ rk_{B \rightarrow A} を作れるものをBi-directional-PRE と呼ぶ。
そうでないものを Uni-directional-PREと呼ぶ。
Single/Multi-hop
再暗号鍵 $ rk_{B \rightarrow C}と、すでに再暗号化された文書$ c_B = reencrypt(rk_{A \rightarrow B}, c_A)があった場合
再暗号化された$ c_Bを$ rk_{B \rightarrow C}を用いて再度、再暗号化 $ c_C = reencrypt(rk_{B \rightarrow C}, c_B) = reencrypt(rk_{B \rightarrow C}, reencrypt(rk_{A \rightarrow B}, c_A))が可能な場合、 Multi-hop-PREと呼ぶ。
逆に、一度しかRe-encryptionできない場合をSingle-hop-PREと呼ぶ。
Collusion resistance
再暗号鍵$ rk_{A \rightarrow B} とBの秘密鍵$ sk_Bによって再暗号元のAの秘密鍵$ sk_Aが得られてしまうようなPREのプロトコルを Collusion resistanceが無いと呼ぶ。
文書ごとにAが秘密鍵を分けていれば全く問題ないため、PREの文脈ではそれほど重要ではない場合が多い。
https://www.youtube.com/watch?v=2hpmavFGz9Y
概要
Proxy Re-Encryptionをtrusted setup抜きでやるプロトコルを提案
ユーザーは暗号化された文書の所有権の移管を、自分の秘密鍵を公開することなく行うことが出来る。
その所有権の移管部分(Key Management System, プロキシサーバー)を非中央集権的に、trusted setup抜きでやりましょう的な
ストレージとして IPFS, Swarm, S3などなんでも使える(WPのセクションDの最初に記述あり)
KMV for dApps on Ethereum blockchainらしいが、これはポジショントークなのではという気もする
NuCypher Joins The Enterprise Ethereum Alliance
スマコンがNuCypherのネットワークのAPIを呼んで、所有権をいじるような(?)アプリを作れるようにしたいらしい
👇WPのSummary
NuCypher KMS is a decentralized key management service and cryptographic access control layer for the blockchain and decentralized applications. Developers and enterprises alike can leverage it to create highly-secure applications in healthcare, financial services, and more. By bringing private data sharing and computation to the public blockchain, NuCypher KMS enables everything from encrypted content marketplaces to secret credentials management to patientcontrolled electronic health records.
NuCypherにおけるPRE
NuCypherで使われているPREの仕組みは以下の通り
NuCypherでは(BBS98)のようにAさんとBさん両方の秘密鍵を用たい。が、もちろんプロキシノードに対してお互いに秘密鍵は明かしたくないので、ハイブリッド型の暗号方式に似た仕様を使う。
まず、ランダムなキーペア $ sk_e/pk_eを生成し、この秘密鍵をB さんの公開鍵$ pk_Bで暗号化する:
$ sk^\prime_e = encrypt_{pke}(pk_B, sk_e)
Aさんランダムな鍵$ sk_e/pk_e に対して再暗号鍵を生成する:
$ rk_{A \rightarrow e} = rekey(sk_A, pk_e)
そしてサーバーは暗号文$ c_A ランダムな鍵に対して再暗号化する。
$ c_e = reencrypt(rk_{A \rightarrow e}, c_A)
Bさんは受け取った$ sk^\prime_e をまず自分の秘密鍵$ sk_Bで復号し、その後$ c_eをその復号化された秘密鍵で復号化する:
$ sk_e = decrypt_{pke}(sk_B, sk^\prime)
$ m = decrypt_{pke}(sk_e, c_e)
このアプローチは(AFGH)の論文で紹介されている(らしい)。
Re-encryption Nodeとプロトコル
NuCypherでは、 ネットワークノードRe-encryption nodeがプロキシサーバーの役割を果たす。
Nodeはproof of stakeに基づいて選ばれるらしい(Ethのコントラクトにデポジット的なことをするらしい??)
selected according to proof-of-stake out of the active nodes in a decentralized network
ここで言っている decentralized network はNuCypherのネットワーク
まず、Senderはあらかじめ暗号化した文書をStroage(e.g. ipfs)に暗号化して保管しているとする
この時にrecieverの存在を知っておく必要はない
暗号化の結果を$ EDEK と書くことにする
https://gyazo.com/b4545ce27fc08de49c7cd3c9be0dfd21
RecieverはSenderに公開鍵 $ pk_rをsenderに送る。
その後senderは選ばれたnodeに対して再暗号鍵 $ rk_{sender \ \rightarrow \ reciever} = rekey(sk_s, pk_r)を送信
nodeはその事実をネットワークに保存
https://gyazo.com/3a94d10ab3484bffe1d959dffd5e85fa
recieverは$ EDEKを復号化するために、まずストレージから$ EDEKを取得する。
後、$ EDEKをノードに送信して問い合わせる。
ノードは$ rk_{sender \ \rightarrow \ reciever}がすでに保存されていた場合、$ EDEKを再暗号化して$ EDEK^\primeをrecieverに返却。
recieverは自分の秘密鍵を用いて$ EDEK^\primeを復号化して、無事に平文$ mを得る。
https://gyazo.com/e45ef8688c04a0805287af5a76d0795e
以上からわかるようにNuCypherのネットワーク自体は完全にstorage(ipfs, swarm, s3, ...)から独立しており、
暗号化のインターフェイスだけ統一しておけばどの任意のストレージに対応可能
NuCypher Network Security
nodeとrecieverが共闘した場合、ホゲ時間後にはrecieverは受け取れなくなる、みたいな制約(conditional Re-Encryption)が効かせられれなくなる
ノードが意地悪して、$ EDEK^\primeの代わりに、$ sk_sで復号化可能なテキトウなデータを返却することを防ぎたい。(recieverは正しいやつかどうかを知るすべはない)
上記の問題を含めsecureに保つに色々考えているらしい。(省略)
応用例
Sharing encrypted files (“Decentralized Dropbox”)
End-to-end encrypted group chat (“Encrypted Slack”)
Patient-controlled electronic health records (EHR)
医療データ管理のPatient-controlができる
Decentralized digital rights management (DDRM)
権利の配布が非中央集権で行える。
Services like a decentralized Netflix or an encrypted marketplace selling software, apps, photos, and other digital content can now be built using NuCypher KMS.`
Blind identity management
ユーザー認証を、第三者を経由しなくても行える
Users can create re-encryption keys for approved applications.
Secret credentials management for scripts and backend applications
Shared credentials and enterprise password management
References
NuCypher KMS: Decentralized key management system
NuCypherのホワイトペーパー
Proxy Re-Encryption: Analysis of Constructions and its Application to Secure Access Delegation
PREのサーベイ
NuCypherと同じ研究室
クラウトサービス上でより安全な共有を実現する 再暗号化技術
東芝のホワイトペーパー
高安全な 関数型代理人再暗号化
関数型PREの研究スライド(三菱電機)。
所感
結局aliceが$ rk_{A \rightarrow B} を計算しなきゃいけないんだったら、最初からaliceが暗号化すればいいのではと思ったけど、そうでもないか
Aliceが変な暗号文を作るかもしれない(暗号文に対する信用はData Producerが担保する仮定だと。)
PREはzkや形式的検証に比べて出てくる数学・コンピュータサイエンスの知識がかなり簡単な印象
Umbralのペーパーを読みながら実装も見ているが、基本的な楕円曲線暗号と暗号学的ハッシュしか使ってなさそう
アカデミアのプレイヤーもSNARK界隈に比べて少なそう(SNARKも十分少ないけど)
応用例もっとないかなあ(ピンときてない)
re-encryptionの演算をSNARKして、正しい証明が生成された場合のみdelegate成功、みたいなプロトコルとか?
余談....
Dear Community members, if you are a member of our Slack channel you would have received an announcement from the Slackbot regarding the NuCypher presale. Please note that this is a SCAM
勉強会メモ