準同型性と決定性ワレット

ブロックチェーンに関わる技術を数学的に理解するため

今回は準同型性暗号と決定性ワレットにスポットを当てました。

ネットや書籍からインプットしたものを自分の為にアウトプットしただけですのであしからず

準同型性暗号は暗号学的に広く用いられる技術です。

とりわけ、RSA暗号やElGamel暗号などの公開鍵暗号はこの特徴を有しています。

とっつきやすいイメージとしては

**・秘密鍵を持たなくても暗号文のまま計算ができる暗号化方式**

↓　　つまり

**・公開鍵と秘密鍵を独立に生成することができる**

**・暗号化されたデータをそのまま検索可能になる**

**・複数組織のデータを異なる鍵で暗号化したまま照合可能になる**

こんなことができます。

どういう場面で利用されているのかと言うと

・仮想通貨による決済時に匿名性を保つ

・クラウド上での処理をデータを隠したまま行う

・電子マネーや電子投票における暗号プロトコル

などです。

「準同型性」とは数学用語で,

**ある操作をしてから足したり掛けたりしたものが、足したり掛けたりしてからある操作をしたものと同じときの状態** を指します。

例えば操作f(x)と変数a,bがあったとして

f(a) + f(b) = f(a + b) (1)

f(a) * f(b) = f(a * b) (2)

を満たすときにfが準同型であるというのです。

(ここでの二項演算子は代数演算)

さらに、準同型暗号にはいくつかの種類があります。

その中でもよく使われるのが加法準同型と完全準同型です。

これらは以下の特徴を有します。

| 種類 | 加法準同型 | 完全準同型 |

|:--|:--|:--|:--|

| 速度 | ○（速い） | ×（遅い）|

| 暗号文サイズ | ○(小さい) | ×（大きい） |

| 機能 | △（加法のみ） |◎（任意の操作） |

完全準同型は2009年に発見され暗号で、多くの企業が開発に注力しているようです。

ビットコインで用いられるECDSAには準同型性があるので公開鍵の足し算は、楕円曲線暗号の点の加法の定義から式(3)のようになります。

(a+b)というスカラーの和による秘密鍵から作られた公開鍵は、秘密鍵aから作られた公開鍵と秘密鍵bから作られた公開鍵の楕円曲線上の和になっていることを意味します。

(a+b)G = aG + bG　 (3)

*注意：左辺はGの位数nを法とするスカラーの加法であり足し算を意味するものではない

右辺は楕円曲線上の和になっていることを意味する。

ランダムに秘密鍵と公開鍵を生成するのではなく、親の鍵から子の鍵を生成する方法で暗号鍵を管理するワレットを**決定性ワレット**と呼びます。これに対し、秘密鍵と公開鍵が一対一に対応する従来のワレットを**非決定性ワレット(ランダムワレット)**と呼びます。

非決定性ワレットではなく決定性ワレットを用いるメリットは

・保管する秘密鍵の数が少なくて済む

・紛失してもシードさえあれば再構築可能

逆にデメリットは

・シードが他人に漏れた場合、自分のビットコイン情報が全て盗まれる危険がある

・シードを紛失した場合、全てのアドレスが凍結される

などです。

簡単に理屈を確認します

まず、privを最初の秘密鍵、privGを最初の公開鍵とします。

また、i = 1,2,3... を整数によるインデックスとします。

さらに、(priv + i)を新しい秘密鍵とすると、これに対応する公開鍵は式(4)のようになります。

(priv + i)G = privG + iG (4)

ここでprivを親秘密鍵、privGを親公開鍵と呼ぶとことにすると、一つの親公開鍵と秘密鍵のペアから必要な数だけの子公開鍵と秘密鍵のペアを作成することができます。

このようにして決定性ワレットが作成されます。

ここで問題が一点

パラメータとして公開してあるGと公開鍵privGは第三者に筒抜け、つまりインデックスiを一つずつ調べて右辺を解析し、左辺と同じものを探せば生成された公開鍵が最初の公開鍵と同一の送金主体であることがわかってしまいます。

この問題を解決する為に、次の対策を施します

1.インデックスに加えて、256ビットの乱数cを追加する

↓

2.これにハッシュ関数を適用し、依存関係を断ち切る

つまり、推定する候補を現実的に探索不可能な数にした上で、ハッシュ関数を用いて不可逆性を持たせるわけです。

このようなインデックスと乱数を持ったハッシュ値を**チェーンコード**と呼びます。

chain_code = h(i,c)

この時、楕円曲線上の加法準同型性によって、式(5)の関係が成立します。

(priv + chain_code)G = privG + chain_codeG (5)

最初の秘密鍵mをマスター秘密鍵と呼び、マスター秘密鍵から作成された公開鍵M = mGを

マスター公開鍵と呼びます。ビットコインの決定性ワレットではマスター秘密鍵と最初のチェーンコードが最初の起点ではなくこの二つの女王を生成する　ルートシードというデータを秘密情報の起点にしています。

(ルートシードは128,256,512ビットの乱数)

*注意：これは、ハッシュにかける際に用いた乱数ではないです

ホットストレージとコールドストレージの間を守る技術として、チェーンコードはとても有効な手段だと感じます。この技術を支えるバックグラウンドで準同型暗号のような数学的アプローチが必要になってくるので代数学や楕円曲線に関して少し知見が溜まってきたら次はこの辺を記事にしたいと思います。

次回は決定性ワレットについて詳しく記事を書くつもりです。

ちなみに参考2と参考3の著者が同じ方でした。