フレセッツ技術ブログ弊社エンジニアがブロックチェーンの旬の話題をお届けします。)の難しさと関連していることを保証するために使われる定理です。「偽造が難しいこと」を示すために、「もし偽造ができたとすると、もっと難しい問題を解くことも(無視できない確率で)可能になる」という論理を頭に入れておくと読みやすいと思います。ビットコインで様々なマルチシグの応用が提案されていますが、その応用の安全性の証明で分岐補題は用いられています[1]。この記事では証明を簡単に解説し、定理の意味するところを説明します。具体的にシュノア署名でこの定理がどう適用されているのか確かめてみたいと思います。以下の定義は[2]からの翻訳です。SでSからsへのランダムな要素の割り当てを表現する。...によるアルゴリズムの出力とする。h_{q}をランダムオラクルから得られる値とする。Hの要素数として与える。h_{q}を入力として受け取り、整数のペアを出力する。qのいずれかの整数であり、二番目の要素は署名\sigmaである。別のランダムアルゴリズムIGを入力生成器とする。F_{A}とは入力xを受け取るランダムアルゴリズムであって、以下のような操作を行うものである。F_{A}(x):\rhoをランダムに選択する。\epsilon)を出力。\sigma^{\prime})を出力。F_{A}で出力の第一項が1になる確率frkは以下で定義される。証明は[2]にあり、確率以外の特別な知識は必要としません。以下の式変形を考えます。1)を2回掛け合わせて足したものとして書きなおせます。ここでX_iは確率ですが、確率変数としてみる事もできます。確率変数としてみると、すなわち(h_1,...,h_{i-1},\rho)に関する自乗の期待値の和になっており、期待値の自乗の和で下から抑えられます。入力をパブリックパラメータx(公開鍵)とし、ハッシュ関数H_1を固定し、攻撃者が生成した公開ランダム値とメッセージを記録しながら、署名検証をパスする偽造署名を探索するアルゴリズムAを考えます。Aは攻撃者を模したアルゴリズムです。Aによってメッセージハッシュ値H_1(m)、偽造署名\sigma、ランダム値\rhoが見つかったら、ランダム値を固定したまま、ハッシュ関数だけを別のH_2に取り替えて、同じような探索を行います(F_A(x))。すると、ハッシュ関数が一様にランダムであるため(ROM)一定の確率で1回目と同じメッセージについて存在的偽造に成功します。そのような連続した2回の存在的偽造に成功する確率frkは、そもそも存在的偽造が一回でも成功する確率accを使って下から抑えられます。frkがaccの二乗で表現できるのは、二回のaccの試行を行うことから感覚的にも納得できると思います。逆に言えば、accはfrkで上から抑えられており、frkが「十分難しい問題を偶然解くことができる非常に小さな確率」とみなせるならば、accもまたいくらでも小さくできると言えます。このようにして、存在的偽造の困難性を示すために使われる定理ですが、実際の例を考えた方が理解しやすいでしょう。具体例[3]にあるシュノア署名[4]の例を挙げます。frkとは、シュノア署名があるメッセージmに対して存在的偽造されたとき、その偽造で用いられたパラメータrを使ってもう一つmに対する有効な署名を作り出せる確率です。そのような偽造が達成されたとき、離散対数問題は破られることを説明します。同じランダム値を使って存在的偽造された二つのシュノア署名が離散対数問題の解を導出することを示します。シュノア署名の詳細は[4]を参照してください。p,qを素数とし、qはp-1を割り切るとする。pを法としqを位数とする乗法群\mathbb{Z}_p^{*}を考える。qは\mathbb{Z}_p^{*}の生成元gを割り切るように取る。\mathbb{Z}_p^{*}上のシュノア署名の検証をパスする、偽造された二つの署名を考える。g^rを二つの偽造署名で共通のランダムな値とする(gは生成元なのでrは存在するが具体的には不明)。秘密鍵をx、公開鍵をyとする。t_2)について、以下が成立する。pという形式の離散対数問題の解を求めてみる。0)が成立し、確かに「二つの存在的偽造署名」と「公開鍵」から「秘密鍵」が導出できているので、離散対数問題の解が得られていると言える。以下、上のシュノア署名の位数qとは異なる分岐補題の式のqであることに注意してください。frk}が十分小さくなるようにfrkを十分小さく取れば(=シュノア署名の位数を十分大きく取れば)、離散対数問題の仮定のもと、ランダムに署名が偽造される確率accをいくらでも小さくなるように設定できます。よってシュノア署名はROMと離散対数問題の困難性の仮定の下で、存在的偽造に対して安全と言えることになります。他にも[3]ではElGamal署名の存在的偽造に対する安全性も示していますが、条件分岐があるので証明はやや複雑です。まとめ英語でも情報が少なく、終始抽象的でイメージが掴みにくい分岐補題ですが、分かってしまえば言っていることは単純です。この定理の応用に興味があれば、他の署名形式での適用例を探してみたり自分で証明してみたりすると良いと思います。https://blog.visvirial.com/articles/721x7888OpenBSDが好きなエンジニアです。弊社エンジニアがそれぞれの強みをいかし、ブロックチェーン・暗号技術の旬な話題・コアなネタをお届けします。接続とパケットの解析(パース)は出来るようになりました。やりとりして、ハンドシェイクをしていきます。この記事では、チェックサム部分のアルゴリズムを解いていきます。ブロックチェーン業界に転職して約1年。運用周りの比較的泥臭いことをやってきました。日々思うことをざっとまとめてみました。フリをしてみようと思います。チェックサムホームお知らせフレセッツ株式会社とは暗号資産(仮想通貨)取引所向けに事業者用ウォレットシステムを提供する事業を行っています。コールド/ホットを問わず、マルチシグ対応のウォレットを作っています。Reserved.ホーム検索トップサイドバーフレセッツ株式会社とは暗号資産(仮想通貨)取引所向けに事業者用ウォレットシステムを提供する事業を行っています。コールド/ホットを問わず、マルチシグ対応のウォレットを作っています。Lemma)の解説と具体例2019.12.092019.12.18カテゴリーお知らせ最近のコメントタイトルとURLをコピーしました。