Hyperledger Iroha。特徴は何よりも日本企業であるソラミツがコードを提供しているところだ。日本語での文書もある程度提供されているから理解しやすい。Hyperledgerのページでは、「Mobile application focus」という言葉で紹介が書かれているとおり、iOSやAndroid上でクライアントアプリを作るためのライブラリが提供されている。
Irohaで扱うユースケースの一つとして、教育やヘルスケア分野における証書、つまり、Indyと同じユースケースが示されている。Irohaではブロックチェーンにアカウントの情報をkey, value形式で登録することができる。また、アクセス制御機能を持たせることで、あるアカウントに対して読み込みもしくは書き込みの権限を与えることができる。これらを使って、大学が卒業生のアカウントに卒業証明を書き込んだり、その卒業証明を企業に提供することができる。資産移転やサプライチェーンといったブロックチェーンのよくあるユースケースに対応できるように、整理されたシンプルなAPIが提供されていることが、特徴となるだろう。
構成はOrderingサービスが存在しており、Fabricに似ている。コンソーシアムを組む上でのツールとして有効なブロックチェーンとなるだろう。特に、ドメインを使ったアクセス制御が容易にできるところは役立つように思う。
2019年12月3日火曜日
Hyperledger Indy
またまた、Hyperledger、今回はHyperledger Indyについて書く。Hyperledgerのページには端的にDecentralized Identityと書かれているとおり、分散アイデンティティのためのブロックチェーンである。さまざまなコード (スマートコントラクトと呼ばれる) を実行できることで汎用的な利用が可能であるFabricやSawtoothとは異なり、特定領域用のブロックチェーンになる。米スタートアップのEvernym、Evernymが中心となり設立したSovrin Foundationが2017年にコードを寄贈することでスタートしている。現在、Hyperledgerの中で最も勢いがプロジェクトだ。Indyの暗号ライブラリ部分が切り出されたHyperledger Ursa、IndyのWalletアプリ部分が切り出されたHyperledger Ariesとプロジェクトを増やしながら開発が進められている。
Identityという言葉は非常にピンとこない言葉だ。人はさまざまな属性を持ち、それがその人のIdentityを構築していることになる。分散アイデンティティで取り扱われるのは、その人の属性情報、名前を始めとして、住所や電話番号、生年月日や学歴、資格、...、その人にまつわるすべてである。ということは、Indyではブロックチェーンに人の属性を保存すると考えると、それは間違いだ。Indyではプライバシに力点を置いており、ブロックチェーン上に属性情報を置くのをよしとしない。
HyperledgerのCase Studyで挙げられているSony Global Educationの例では、Fabricを使用しており、ブロックチェーンには教育に関する属性 (学位・成績証明書など) のハッシュ値を保存している。しかし、Indyでブロックチェーンに保存するのは、DID (Decentralized Identifier) と呼んでいる属性情報を管理するサービスの識別子と公開鍵(検証鍵)およびアクセス方法である。IdentityとIdentifierは似ているのに、全く違う意味を持つのでややこしい。
IndyではブロックチェーンにDIDが登録され、かつ、トラストを示すタグ (トラストアンカー)が付いていること、つまり、ブロックチェーンにトラストアンカーとしてどのサービスを登録するかを決定することがトラストのルートとなる。そういう意味では、認証局(CA; Certification Autority) と同じだ。認証局を使う場合は、審査した上でサービスに電子証明書を発行し、ユーザーはサービスにアクセスするときに電子証明書を検証することで信用を確保できる。それに対して、Indyでは審査した上でサービスのDIDとトラストアンカータグなどをブロックチェーンに登録、ユーザーはサービスにアクセスするときにブロックチェーンを確認することで信用を確保する。
学歴や資格情報がデジタル化されるのは間違いないが、それをブロックチェーンを利用したほうがいいかは別問題だ。中国ではCHSI (http://www.chsi.jp/) を使って学歴・学籍の確認をすることができる。中央型で作ればシンプルだ。日本では、経産省が学位・履修・職歴証明・研究データの記録・保存をすることをテーマにブロックチェーンハッカソン2019を開催したが、この先に未来はあるのか。
Identityという言葉は非常にピンとこない言葉だ。人はさまざまな属性を持ち、それがその人のIdentityを構築していることになる。分散アイデンティティで取り扱われるのは、その人の属性情報、名前を始めとして、住所や電話番号、生年月日や学歴、資格、...、その人にまつわるすべてである。ということは、Indyではブロックチェーンに人の属性を保存すると考えると、それは間違いだ。Indyではプライバシに力点を置いており、ブロックチェーン上に属性情報を置くのをよしとしない。
HyperledgerのCase Studyで挙げられているSony Global Educationの例では、Fabricを使用しており、ブロックチェーンには教育に関する属性 (学位・成績証明書など) のハッシュ値を保存している。しかし、Indyでブロックチェーンに保存するのは、DID (Decentralized Identifier) と呼んでいる属性情報を管理するサービスの識別子と公開鍵(検証鍵)およびアクセス方法である。IdentityとIdentifierは似ているのに、全く違う意味を持つのでややこしい。
IndyではブロックチェーンにDIDが登録され、かつ、トラストを示すタグ (トラストアンカー)が付いていること、つまり、ブロックチェーンにトラストアンカーとしてどのサービスを登録するかを決定することがトラストのルートとなる。そういう意味では、認証局(CA; Certification Autority) と同じだ。認証局を使う場合は、審査した上でサービスに電子証明書を発行し、ユーザーはサービスにアクセスするときに電子証明書を検証することで信用を確保できる。それに対して、Indyでは審査した上でサービスのDIDとトラストアンカータグなどをブロックチェーンに登録、ユーザーはサービスにアクセスするときにブロックチェーンを確認することで信用を確保する。
学歴や資格情報がデジタル化されるのは間違いないが、それをブロックチェーンを利用したほうがいいかは別問題だ。中国ではCHSI (http://www.chsi.jp/) を使って学歴・学籍の確認をすることができる。中央型で作ればシンプルだ。日本では、経産省が学位・履修・職歴証明・研究データの記録・保存をすることをテーマにブロックチェーンハッカソン2019を開催したが、この先に未来はあるのか。
2019年12月2日月曜日
Hyperledger Sawtooth & Grid
引き続きHyperledgerについて書く。今回は、Hyperledger Sawtoothについてである。2016年にIntelがソースを寄贈して以降、開発が続いているプロジェクトである。Intelのハードウェア(SGX)とセットで完全な動作が可能となる独自コンセンサスアルゴリズムPoET (Proof of Elapsed Time) が特徴となる。ビットコインのコンセンサスアルゴリズムPoW (Proof of Work) のようにわざとコンピューティングパワーを使うような処理をする必要はなく、コンピューティングパワーをあまり使わずにコンセンサスが取れる。なお、開発環境用にSGXの代わりにシミュレータが提供されているが、不正は容易なので実用的ではない。
信頼できるシステムの実現には、何らかトラストのルートが必要である。Fabricの場合は基本的にノードの提供者を限定することでトラストを実現している。Sawtoothはプロセッサによって実現するというIntelらしい仕組みになっている。Intelの戦略は昔から明確だ。プロセッサを売るために、その有効性が見えるソフトウェアやソリューションを提供してくる。Intelはフィールドワーク含めさまざまな調査をした上で、プロセッサの使いみちについて全方向で提案してくる。利益が莫大だからできるのか、そこまでやるからこそ莫大な利益をあげられるのか。
なお、開発が進められた結果、PoET以外のコンセンサスアルゴリズム(Raft/PBFT)も提供されており、Intelプロセッサなしでも利用可能だ。トラストについてはFabric同様にノードの提供者を限定していることから生み出されていることになる。そのため、使い方によってはできることはFabricと同じだ。
さらに、IntelはCargill、Bitwise IOと共にブロックチェーン上でサプライチェーンを実現するためのツール群を提供するフレームワークとしてHyperledger Gridを提供している。企業向けブロックチェーンの活用はなかなか悩ましい。企業間で連携するシーンと言っても、力関係があるような関係では別の仕組みのほうが効率的だからだ。例えば、トヨタと部品メーカーでは、トヨタが他の部品メーカーにトヨタが作ったシステムに情報を入力させればよい。実際、そうなっていて何の問題もないし、透明性も結局トヨタ次第になるだろうから、効率的だ。とは言ってもそういう関係ばかりではないので、有望な領域はサプライチェーンということになるのだろう。アメリカの小売ターゲットはGridを使って管理するようだ。なお、最大手WalmartはFabricを使う。これらも、複数の小売でコンソーシアムを組むところまでいかないと、ブロックチェーンを使う意味はあまりなくなりそうに感じる。
信頼できるシステムの実現には、何らかトラストのルートが必要である。Fabricの場合は基本的にノードの提供者を限定することでトラストを実現している。Sawtoothはプロセッサによって実現するというIntelらしい仕組みになっている。Intelの戦略は昔から明確だ。プロセッサを売るために、その有効性が見えるソフトウェアやソリューションを提供してくる。Intelはフィールドワーク含めさまざまな調査をした上で、プロセッサの使いみちについて全方向で提案してくる。利益が莫大だからできるのか、そこまでやるからこそ莫大な利益をあげられるのか。
なお、開発が進められた結果、PoET以外のコンセンサスアルゴリズム(Raft/PBFT)も提供されており、Intelプロセッサなしでも利用可能だ。トラストについてはFabric同様にノードの提供者を限定していることから生み出されていることになる。そのため、使い方によってはできることはFabricと同じだ。
さらに、IntelはCargill、Bitwise IOと共にブロックチェーン上でサプライチェーンを実現するためのツール群を提供するフレームワークとしてHyperledger Gridを提供している。企業向けブロックチェーンの活用はなかなか悩ましい。企業間で連携するシーンと言っても、力関係があるような関係では別の仕組みのほうが効率的だからだ。例えば、トヨタと部品メーカーでは、トヨタが他の部品メーカーにトヨタが作ったシステムに情報を入力させればよい。実際、そうなっていて何の問題もないし、透明性も結局トヨタ次第になるだろうから、効率的だ。とは言ってもそういう関係ばかりではないので、有望な領域はサプライチェーンということになるのだろう。アメリカの小売ターゲットはGridを使って管理するようだ。なお、最大手WalmartはFabricを使う。これらも、複数の小売でコンソーシアムを組むところまでいかないと、ブロックチェーンを使う意味はあまりなくなりそうに感じる。
Hyperledger Fabric
企業向けのブロックチェーンのオープンソースというとLinux FoundationによるHyperledgerである。2016年にIBMが寄贈したコードがHyperledger Fabricとなって以来ずっと拡大を続けており、2019/12/2現在で、Hyperledgerのページを見ると、15のプロジェクトが存在するという驚きの状況である。
ブロックチェーンはガートナーのハイプ・サイクルでは幻滅期に位置づけられ、2021年には市場に浸透していくことを予測している。実際、多くの企業が実証実験を行い幻滅している状況で、一部のサービスについては提供が進んでいる状況にあることを考えると、これは正しいのだろう。しかし、多くの場合、ブロックチェーンでなくてもいい、むしろ、ブロックチェーンを使わないほうが効率的なシステムが作れるはずなのにブロックチェーンをわざわざ使っているように感じられる。
ブロックチェーンが注目されるようになった原点であるビットコインは、誰でもコンピューティングパワーをノードとして提供することで仮想通貨の管理システムの一部の提供者になれるという形での非中央型を実現した。提供者は提供するコンピューティングパワーに応じて仮想通貨を得られるというインセンティブを得られるように設計することで、裏切りが起こりにくくし、かつ、裏切りを行うには提供するコンピューティングパワーの過半を得る必要があるようになっている。そのことから、トラストを生み出しているとも言われており、これはすごい発明である。将来的には、マイニングの際に得られる仮想通貨が減り最終的にはなくなること、ブロックチェーンを保存するために必要とするディスク容量がどんどん拡大していくこと、仮想通貨の取引が増えた場合のスケーラビリティの実現などの問題があるものの、何とかしていくだろう。
一方、Hyperledger Fabric、これは、IBMのキーワードをビジネスに繋げるうまさを感じずにはいられない。コンソーシアムチェーンと言われているが、基本的に信頼できる複数の企業でブロックチェーンを管理することを想定している。したがって、トラストを生み出す必要はない。次に、ビットコインではクライアントからの要求(トランザクション)を全ノードで共有するのに対して、細かいことを言うと、FabricではOrderingサービスと呼ばれるサービスが全トランザクションを受け取って、ブロックに取り込む順番を決めて他のノード群に渡す。つまり、Orderingサービスという中央があるわけで非中央型も実現していない。したがって、Fabricはビットコインのすごさを何も実現していないように感じられる。しかし、Fabricはコンソーシアムを作るためのツールである、と考えると、見え方は変わってくる。コンソーシアムに所属する全企業が同じコードやデータを管理することができること、それは企業間の連携のあり方を変える可能性を感じる。
ブロックチェーンはガートナーのハイプ・サイクルでは幻滅期に位置づけられ、2021年には市場に浸透していくことを予測している。実際、多くの企業が実証実験を行い幻滅している状況で、一部のサービスについては提供が進んでいる状況にあることを考えると、これは正しいのだろう。しかし、多くの場合、ブロックチェーンでなくてもいい、むしろ、ブロックチェーンを使わないほうが効率的なシステムが作れるはずなのにブロックチェーンをわざわざ使っているように感じられる。
ブロックチェーンが注目されるようになった原点であるビットコインは、誰でもコンピューティングパワーをノードとして提供することで仮想通貨の管理システムの一部の提供者になれるという形での非中央型を実現した。提供者は提供するコンピューティングパワーに応じて仮想通貨を得られるというインセンティブを得られるように設計することで、裏切りが起こりにくくし、かつ、裏切りを行うには提供するコンピューティングパワーの過半を得る必要があるようになっている。そのことから、トラストを生み出しているとも言われており、これはすごい発明である。将来的には、マイニングの際に得られる仮想通貨が減り最終的にはなくなること、ブロックチェーンを保存するために必要とするディスク容量がどんどん拡大していくこと、仮想通貨の取引が増えた場合のスケーラビリティの実現などの問題があるものの、何とかしていくだろう。
一方、Hyperledger Fabric、これは、IBMのキーワードをビジネスに繋げるうまさを感じずにはいられない。コンソーシアムチェーンと言われているが、基本的に信頼できる複数の企業でブロックチェーンを管理することを想定している。したがって、トラストを生み出す必要はない。次に、ビットコインではクライアントからの要求(トランザクション)を全ノードで共有するのに対して、細かいことを言うと、FabricではOrderingサービスと呼ばれるサービスが全トランザクションを受け取って、ブロックに取り込む順番を決めて他のノード群に渡す。つまり、Orderingサービスという中央があるわけで非中央型も実現していない。したがって、Fabricはビットコインのすごさを何も実現していないように感じられる。しかし、Fabricはコンソーシアムを作るためのツールである、と考えると、見え方は変わってくる。コンソーシアムに所属する全企業が同じコードやデータを管理することができること、それは企業間の連携のあり方を変える可能性を感じる。
2019年10月14日月曜日
ゼロ知識証明CL署名2
CL署名の特徴は、コミットメントに署名することができるところである。実際の値を明かす代わりに、コミットメントを署名者に明かして、署名を作成し、そして、署名の要求者が元の値の署名として使えるようにする。コミットメントについては、Wikipediaのビットコミットメントの項目が参考になる。
コミットメントは、嘘をつかないように、事前にその証拠を伝えることである。ゼロ知識証明基礎2で述べた$a$がコミットメントに当たる。ランダム値である$b$が検証者から証明者に伝えられる前に、$a$をコミットをしておくことで、$c$を応答することが証明になるようになっている。$b$を検証者から証明者に伝えた後で、$a$と$c$を伝えるのであれば、容易にインチキができる。 CL署名では、Damgård Fujisakiのコミットメントを使う。
コミットメントは、嘘をつかないように、事前にその証拠を伝えることである。ゼロ知識証明基礎2で述べた$a$がコミットメントに当たる。ランダム値である$b$が検証者から証明者に伝えられる前に、$a$をコミットをしておくことで、$c$を応答することが証明になるようになっている。$b$を検証者から証明者に伝えた後で、$a$と$c$を伝えるのであれば、容易にインチキができる。 CL署名では、Damgård Fujisakiのコミットメントを使う。
2019年10月13日日曜日
ゼロ知識証明CL署名1
ゼロ知識証明の基礎を説明した。基礎でできることは、$y=g^x$を満たす$x$の値を伝えずに、$x$を知っていることを証明する、ということにすぎない。この証明が何の役に立つのか、が疑問になるだろう。実際のところ、役に立つようにするには、工夫が必要になる。その工夫の一つは、CL署名スキームである。これは、「私は署名を持っている」というようなステートメントを証明し、コミットされた値に対する署名を作成するための署名スキームである。なお、日本語で書かれているページでは、Ontologyテクニカルホワイトペーパーが参考になる。
CL署名の基本スキームは、鍵生成とメッセージ空間、署名アルゴリズム、検証アルゴリズムの4つから成り立つ。まず、それを述べる。
鍵生成
CL署名の基本スキームは、鍵生成とメッセージ空間、署名アルゴリズム、検証アルゴリズムの4つから成り立つ。まず、それを述べる。
鍵生成
$p=2p'+1, q=2q'+1$で$p$, $q$, $p'$, $q'$が素数であるものを算出する。そして、$n=pq$を計算する(長さは$l_n$)。さらに、乱数$a$, $b$, $c$を生成する。そして、公開鍵$PK=(n, a, b, c)$、秘密鍵$SK=p$とする。メッセージ空間
※なお、$p$, $q$は安全素数と呼ばれる。 ※$a, b, c \in QR_n$(平方剰余の集合)に限定。$QR_n \subseteq {\mathbb{Z}_n}^*$、${\mathbb{Z}_n}^*$は、{1, 2, ..., n-1}を意味する。$b^2 \equiv a \bmod n$を満たす$\exists b \in {\mathbb{Z}_n}^*$を満たす$a \in {\mathbb{Z}_n}^*$。
メッセージ空間$m$は長さ$l_m$のバイナリストリングである。つまり、0以上$2^{l_m}$未満の値であるということ。署名アルゴリズム
$e > 2^{l_m+1}$で長さ$l_e=l_m+2$を満たす素数$e$を算出する。また、長さが$l_s=l_n+l_m+l$であるランダム数$s$を生成する。$l$はセキュリティパラメータである。そして、以下を満たす$v$を計算する。 \begin{align} v^e \equiv a^mb^sc \bmod n \end{align}検証アルゴリズム
$(e, s, v)$がメッセージ$m$の署名である。そして、$v^e \equiv a^mb^sc \bmod n$と$2^{l_c} > e > 2^{l_c}-1$をチェックする。なぜ、これで検証ができているのか、それを次に説明する。
2019年10月11日金曜日
ゼロ知識証明基礎3
ゼロ知識証明2では、攻撃の成功確率1/2で証明することができ、繰り返すことで0に近づけることが可能になる方法を説明した。これについては、繰り返しを減らす方法やさらになくす方法も提案されている。
減らすには、検証者が$b$を0以上$q$未満の値からランダムに選択して証明者に伝え、証明者は$c=r+bx \bmod q$を計算して検証者に返答する方法がある。このようにおいても、$g^c=ay^b$は成り立つ。これは1度で、攻撃の成功確率$1/q$で証明することができる。
なくす方法では、ハッシュ関数を使う。$p$, $q$, $g$, $y$, $a$を連結したものから証明者はハッシュを計算。さらにハッシュ値を$b$として、証明者は$c=r+bx \bmod q$を計算して、$a$, $b$, $c$を検証者に伝える。検証者は、同様の検証を行う。これにより、やはり、攻撃の成功確率$1/q$で証明することができる。
減らすには、検証者が$b$を0以上$q$未満の値からランダムに選択して証明者に伝え、証明者は$c=r+bx \bmod q$を計算して検証者に返答する方法がある。このようにおいても、$g^c=ay^b$は成り立つ。これは1度で、攻撃の成功確率$1/q$で証明することができる。
なくす方法では、ハッシュ関数を使う。$p$, $q$, $g$, $y$, $a$を連結したものから証明者はハッシュを計算。さらにハッシュ値を$b$として、証明者は$c=r+bx \bmod q$を計算して、$a$, $b$, $c$を検証者に伝える。検証者は、同様の検証を行う。これにより、やはり、攻撃の成功確率$1/q$で証明することができる。
2019年10月10日木曜日
ゼロ知識証明基礎2
ゼロ知識証明の基本は対話型である。前回も述べた暗号入門7講から私の理解を説明する。
証明者と検証者がいるとする。証明者は、$y=g^x$を満たす$x$を知っていて、検証者に$x$そのものを伝えずに、$x$を知っていることを伝えたいとする。それを証明するには、以下のプロトコルを実行する。
[証明者]
1. $r$をランダムで生成する。
2. $a = g^r$ を計算する。
3. $y$, $a$, $g$を検証者に伝える。
[検証者]
4. $y$, $a$, $g$を証明者から受け取る。
5. 0か1をランダムに選択する(その値を$b$とする)。
6. $b$を証明者に伝える。
[証明者]
7. 検証者から$b$を受け取る。
8. $c=r+bx$を計算する。
9. $c$を検証者に伝える。
[検証者]
10. $c$を証明者から受け取る。
11. $g^c=ay^b$あることを検証する。
12. 1.に戻って繰り返す(繰り返し回数が多いほど$x$を知っていることをより確信する。)
11.の式について説明する。
$y$, $a$, $g$は4.、$c$は10.で受け取っている。そして、$b$は自身が生成したので、計算が可能であることがわかる。そして、
$g^c = g^{r+bx} = g^r \times g^{bx} = a \times g^{b^x} = a \times g^{x^b} = a \times y^b = ay^b$
なので、この式が正しいことはわかる。
でも、これを読んでも、なるほど、とは思わないだろう。どうしてこれで証明したことになるのか。
まず、$y$と$g$の値がわかっていれば、$x$が求められるのではないか、という疑問。これは、その通りである。単純な式$y=g^x$であれば、簡単に$x$が計算できる。上記は、省略して書いたが、本当は、離散対数問題というのを扱う。$y=g^x mod p$のように全ての$g^a$の形になっているところを$g^a mod p$($p$は非常に大きな素数)という形に置き換える。modは"余り"を計算する記号である。C言語などなら%で表現する。modは面白い特徴を持ち、このように置き換えてもそのまま計算式が成り立つのだ。そして、$y$から$x$を求めるのは計算量的に困難になる。なので、暗号学的には$y$から$x$を求めることはできないということ、$y$を伝えても$x$の知識を伝えていないこと(ゼロ知識)にする。
次の疑問は、$x$をなぜ知っていることが証明できているのか、である。では、証明者が$x$を知らない場合にどうなるかを考えてみる。$x$を知らないということは$y=g^x$は計算できないので、ランダムな数値にすることになる。さらに、$c=r+bx$も計算できないので、ランダムな数値にすることになる。すると、11.の式の左辺の$c$と右辺の$y$が対応する値が入らないことになるので、この式は等しくならないことになる。
その次の疑問は、そんなこと言っても、対応するような$x$を作れるのではないか、ということだ。実は、$b$の値として0か1のどちらが応答されるのかが、わかっていれば、インチキできる。
なお、0と1の両方を同時に与えることはできない。$c=r+bx$であるから、0の時は$c=r$で$r$の値がわかり、1の時は$c=r+x$で$r+x$の値がわかる。その結果、$x$の値も引き算で出せてしまう。
以下の本でもゼロ知識証明についての触れられている。暗号技術についてわかりやすく書かれた本なので、ゼロ知識に限らず幅広く知りたい場合はお勧めできる。
証明者と検証者がいるとする。証明者は、$y=g^x$を満たす$x$を知っていて、検証者に$x$そのものを伝えずに、$x$を知っていることを伝えたいとする。それを証明するには、以下のプロトコルを実行する。
[証明者]
1. $r$をランダムで生成する。
2. $a = g^r$ を計算する。
3. $y$, $a$, $g$を検証者に伝える。
[検証者]
4. $y$, $a$, $g$を証明者から受け取る。
5. 0か1をランダムに選択する(その値を$b$とする)。
6. $b$を証明者に伝える。
[証明者]
7. 検証者から$b$を受け取る。
8. $c=r+bx$を計算する。
9. $c$を検証者に伝える。
[検証者]
10. $c$を証明者から受け取る。
11. $g^c=ay^b$あることを検証する。
12. 1.に戻って繰り返す(繰り返し回数が多いほど$x$を知っていることをより確信する。)
11.の式について説明する。
$y$, $a$, $g$は4.、$c$は10.で受け取っている。そして、$b$は自身が生成したので、計算が可能であることがわかる。そして、
$g^c = g^{r+bx} = g^r \times g^{bx} = a \times g^{b^x} = a \times g^{x^b} = a \times y^b = ay^b$
なので、この式が正しいことはわかる。
でも、これを読んでも、なるほど、とは思わないだろう。どうしてこれで証明したことになるのか。
まず、$y$と$g$の値がわかっていれば、$x$が求められるのではないか、という疑問。これは、その通りである。単純な式$y=g^x$であれば、簡単に$x$が計算できる。上記は、省略して書いたが、本当は、離散対数問題というのを扱う。$y=g^x mod p$のように全ての$g^a$の形になっているところを$g^a mod p$($p$は非常に大きな素数)という形に置き換える。modは"余り"を計算する記号である。C言語などなら%で表現する。modは面白い特徴を持ち、このように置き換えてもそのまま計算式が成り立つのだ。そして、$y$から$x$を求めるのは計算量的に困難になる。なので、暗号学的には$y$から$x$を求めることはできないということ、$y$を伝えても$x$の知識を伝えていないこと(ゼロ知識)にする。
次の疑問は、$x$をなぜ知っていることが証明できているのか、である。では、証明者が$x$を知らない場合にどうなるかを考えてみる。$x$を知らないということは$y=g^x$は計算できないので、ランダムな数値にすることになる。さらに、$c=r+bx$も計算できないので、ランダムな数値にすることになる。すると、11.の式の左辺の$c$と右辺の$y$が対応する値が入らないことになるので、この式は等しくならないことになる。
その次の疑問は、そんなこと言っても、対応するような$x$を作れるのではないか、ということだ。実は、$b$の値として0か1のどちらが応答されるのかが、わかっていれば、インチキできる。
$b$が0であるとわかっている場合
$c=r$である。したがって、11.の式の左辺は$g^r$で、右辺は$a$である。つまり、2.で正しく、$a=g^r$を計算して、その値を3.で渡していれば騙すことができる。
$b$が1であるとわかっている場合しかし、知らなかった場合はどうなるだろうか。
$c=r+x$である。が、$x$は知らないので、$c$は計算できない。しかし、11.の式を満たす$c$を伝えればいい。$b$が1とすると、11.の式の右辺は$ay^b = ay$になる。したがって、2.の式で$a$を計算するときに、$a=g^r$を計算する代わりに、$a=g^c / y$を計算すればよい。$c$はランダム値で構わない。これにより、11.の式を満たすことが可能である。
$a=g^r$にしている場合に$b$が1だったら
$c=r+x$が計算できないので11.の式を満たす$c$を送れない。
$a=g^c/y$にしている場合に$b$が0だったらつまり、bが0か1かの予想が当たった場合はインチキができてしまうので、この$b$を送って$c$を受け取る処理を繰り返す必要がある。繰り返すことで、インチキができる可能性が1/2になっていく。
今度は、$a=g^r$を満たす$r$を求めることができないために、11.の式を満たす$c=r$を送ることができない。
なお、0と1の両方を同時に与えることはできない。$c=r+bx$であるから、0の時は$c=r$で$r$の値がわかり、1の時は$c=r+x$で$r+x$の値がわかる。その結果、$x$の値も引き算で出せてしまう。
以下の本でもゼロ知識証明についての触れられている。暗号技術についてわかりやすく書かれた本なので、ゼロ知識に限らず幅広く知りたい場合はお勧めできる。
2019年10月9日水曜日
ゼロ知識証明基礎1
ビットコインからブロックチェーンが流行り、その状況でセキュリティ業界でホットになっている暗号技術がゼロ知識証明である。ゼロ知識証明は、情報そのものを伝えずに、その情報を知っていることを、証明する方法である。与える情報がゼロ、つまりゼロ知識、ということ。で、そんなことできるわけない。なので、本当に何も伝えないわけではなく、情報を加工したものを伝えて、加工前の情報に戻すことが難しいだけ。それを数学的に実現する。しかし、数学をきっちり勉強してこなかったエンジニアにはなかなか理解しがたい。わかりやすく書かれているのは、「情報セキュリティ大学院大学公開講座『暗号入門７講』ゼロ知識証明入門」だと思うが、これでも難しい。でも、もっとわかりやすく、となると、Wikipediaのゼロ知識証明の項目にあるように、洞窟の比喩などになってしまう。比喩を考えるのは楽しいかもしれないが、本当に理解しようと思っている人の助けにはまったくならない。他の人の理解になればと、僕の理解を明日から書いていく。
きっちり本を読んで理解したいのなら、以下の本が役立つ。
登録:
投稿 (Atom)