2020-06-01

完全準同型暗号の論文を読む - GSW 編 (2)

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は GSW で提案された完全準同型暗号の大まかな仕組みについて説明しました。
今回はその問題点と解決方法について検討していきます。

おさらい - GSW の原型

同じ固有ベクトルを持つ行列が２つあるとき、その２つの行列の和と積は、
固有ベクトルが変わらずに、固有値が和や積になるという性質がありました。

それを利用して、 $Av=\lambda v+e$ と誤差を加えることで LWE 問題として、
暗号文として解読できないようにしました。

問題点：誤差が累積していく

同じ秘密鍵（固有ベクトル）を持つ暗号文 $A$ と $A'$ があるとき、
平文（固有値）は $\lambda$ と $\omega$ としておきます。それぞれの誤差は $e_1$ $e_2$ とします。

$A+A'$ を復号すると
$(A+A')v=Av+A'v=\lambda v+e_1+\omega v+e_2=(\lambda+\omega)v+(e_1+e_2)$ となり、
誤差は $e_1+e_2$ となります。

$A \cdot A'$ を復号すると（途中計算は省略します。元論文を参照してください）、
$\lambda \omega v$ に加わる誤差は、 $v$ の次数を $N$ 、 $e$ の絶対値の最大値を $B$ として、
最大で $(N+1)B^2$ になります。

これはどういうことかというと、例えば多項式の項 $x^m$ を計算しようとすると、
誤差は最大で $(N+1)^{m-1} B^m$ まで大きくなるということです。

誤差の累積は LWE 問題ベースの完全準同型暗号では必ず付きまとう問題で、
過去に様々な解決策が提示されてきましたが、GSW では一風変わった解決策を取ります。

解決策の準備 - ${\rm BitDecomp}$ と ${\rm BitDecomp}^{-1}$

これまで、行列の要素は実数体で考えていましたが、
実数体と準同型である、有限体を要素にもつ行列で考えます。

その時、例えば、位数 13 の有限体であれば、せいぜい 4 bit あれば表現できます。
位数 $q$ の有限体の要素を表すのに必要なビット数は $L=\lfloor \log_2 q \rfloor + 1$ で求められます。
好きな自然数 $k$ 倍の大きさ $N=kL$ を行列やベクトルの次数とします。

$k$ 次元の横方向ベクトル $a' = (a_0, a_1, \cdots, a_{k-1})$ のそれぞれの要素を２進数で書き直す操作を
${\rm BitDecomp}(a')$ と定義します。

例えば、位数 $q=13$ の場合、 $L=\lfloor 3.7 \rfloor + 1 = 4$ となります。 $k$ はとりあえず 3 としましょう。
3 次元横ベクトル $a' = ( 10, 8, 4 )$ を 12 次元横ベクトル
$a = ( 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0 )$ と分解します。
$L=4$ 要素単位で２進数が逆方向に $k=3$ つ並んでいます。

この逆の操作を ${\rm BitDecomp}^{-1}(a)$ とします。

${\rm BitDecomp}$ と ${\rm BitDecomp}^{-1}$ の性質

秘密鍵ベクトル（今回は固有ベクトルではない／縦ベクトル）を、 $k$ 個の 0 か 1 で設定します。
とりあえず $s = (s_0, s_1, \cdots, s_{k-1})^{\mathrm{T}}$ としておきます。

$L$ bit 分の 2 のべき数を $k$ 個並べた縦ベクトルを
$b_{iL+j} = 2^j, i \in \{ 0, \cdots, k-1 \}, j \in \{ 0, \cdots, L-1 \}$ とします。
今回の例だと $b=(1, 2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8)^{\mathrm{T}}$ となりますね。

$v_{iL+j}=b_{iL+j} \times s_i$ とした $v$ を固有ベクトルとします。

すると、
$a \cdot v = \sum_{i=0}^{k-1} \sum_{j=0}^{L-1} s_i \times a_{iL+j} \times 2^j$
$= \sum_{i=0}^{k-1} s_i \sum_{j=0}^{L-1} a_{iL+j} \times 2^j$
$= \sum_{i=0}^{k-1} s_i \times a'_i = a' \cdot s$
というわけで、 $a \cdot v = a' \cdot s$ および ${\rm BitDecomp}(a') \cdot v = a' \cdot s$ が成り立ちます。

ここで、左辺にのみ $a'={\rm BitDecomp}^{-1}(a)$ を代入すると、
${\rm BitDecomp}({\rm BitDecomp}^{-1}(a)) \cdot v = a' \cdot s$
で、前段落前半の式の右辺が同じなので、 ${\rm BitDecomp}({\rm BitDecomp}^{-1}(a)) \cdot v = a \cdot v$ です。

何を言っているかというと、 ${\rm BitDecomp}({\rm BitDecomp}^{-1}(a))$ という処理を加えても、
$v$ との内積は変わらない。という話になります。

この ${\rm BitDecomp}({\rm BitDecomp}^{-1}(a))$ を、元論文では ${\rm Flatten}(a)$ と書いています。

${\rm Flatten}(a)$ の意味するところ

${\rm BitDecomp}^{-1}(a)$ は、 $a$ の横ベクトルを２進数と解釈して $k$ 個の値にまとめ上げる処理でした。
${\rm BitDecomp}(a')$ は、 $a'$ の横ベクトルを２進数として書き直す処理でした。

つまり、例えば $L=4, k=2$ としたとき、 $a = ( 2, 0, 3, 0, 5, 0, 0, 1 )$ は、
${\rm BitDecomp}^{-1}(a) = ( 14, 13 )$ となり、 ${\rm Flatten}(a) = ( 0, 1, 1, 1, 1, 0, 1, 1 )$ ということです。
２進数として解釈してまとめあげて、再度２進数として書き直す。

この処理を行っても、固有ベクトル $v$ との内積の値は変わらない。
$Av=\lambda v+e$ ならば、 $Av={\rm Flatten}(A)v=\lambda v+e$ なのです。

それなのに、行列の要素はすべて 0 もしくは 1 になります。
これのおかげで嬉しいことがあります。

で、 ${\rm Flatten}(a)$ は何が嬉しいの？

超うれしいです。今回の前半で、誤差の累積の話をしましたが、
乗算の時、 $x^m$ を計算すると誤差は最大で $(N+1)^{m-1} B^m$ となりましたが、
乗算のたびに Flatten を行うことで、 $(N+1)^{m-1} B$ に抑えることができます。

$B$ の階乗が消えましたね。これは行列の要素が 0 もしくは 1 に限定されたおかげです。
$B$ は $e$ の要素の絶対値の最大値なので、 $e$ の要素の絶対値を大きくしても
誤差が指数関数的に増えていくことはなくなるわけです。

前回の内容から、 $\frac{(N+1)^{m-1} B}{v_i}$ が、-0.5～0.5 の間に収まっていることが
復号できる条件なので、極力小さくするため $i$ には $L$ の倍数 - 1 を選びます。
つまり、位数 $q$ を表す２進数の最上位ビットです。これは $k$ 個あるはずなので、
その中からさらに $s_i$ が 1 であるもの、つまり $v_i=2^{L-1}$ を選ぶことにします。

すると、 $-0.5 < \frac{(N+1)^{m-1} B}{2^{L-1}} < 0.5$ となるよう、
また、なるべく $B$ が大きくなるよう、 $q, k, B$ を選択すればいいことになります。

${\rm Flatten}$ のおかげで、 $B^m$ が $B$ に変わっており、 $m$ に対して定数になっているため、
$B$ の大きさは乗算回数の影響を受けない、というのが大きなポイントとなっています。

これって完全準同型暗号？？

このシステムでは、選択したパラメータによって乗算の回数に制限ができます。
なぜなら、まだ $(N+1)^{m-1}$ が残っているからです。

とはいえ、最初から計算する内容が決まっている案件であれば、これでも十分実用できます。
こういうものを、Somewhat 準同型暗号 (SHE) と呼びます。

汎用性には若干欠けるところがありますが、これはこれでいろいろ使えます。

まとめ

今回は若干長くなりましたが、GSW の全体像を解説しました。
ちょっとトリッキーで面白くないでしょうか？
次回は SHE ではなく演算回数に上限がない、TFHE の解説を始めようと思います。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

2020-05-25

完全準同型暗号の論文を読む - GSW 編 (1)

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

さて、前回予告した通り、今回は GSW の論文の解説をします。

前回は完全準同型暗号とはどういうものなのか解説しました。
そして、GSW はその完全準同型暗号の手法の１つとして 2013 年に提案された論文です。

こちらは高校数学レベルの線形代数（行列・ベクトル）の知識があれば理解できますので、
先に高校数学レベルの行列とベクトルの要点だけおさらいしておきましょう。
GSW の仕組みのカギとなる、固有値と固有ベクトルの性質について簡単にまとめます。

大変申し訳ないのですが、基本的な定義や計算などについては高校数学についての
参考書的なサイトがいくつもありますので、そちらも参考にしてみてください。

固有値と固有ベクトル

行列 $A$ とベクトル $v$ と実数 $\lambda$ があるとき、
$Av=\lambda v$ が成り立つ $v$ を固有ベクトル、 $\lambda$ を固有値と呼びます。

要するに、固有ベクトル $v$ を行列 $A$ で線形変換した時、
元のベクトル $v$ の長さが $\lambda$ 倍になって、方向は変わらない。ということです。

行列 $A$ を主体で考えると、 $A$ による線形変換で、
向きが変わらずに長さだけ変わる方向が、固有ベクトルで、
その拡大率が固有値。と言い換えることもできます。

ここで注目したいのは、共通の固有ベクトル $v$ を持つ行列 $A$ と $B$ があり、
それぞれの固有値を $\lambda$ 、 $\omega$ としたとき、
$(A+B)v=Av+Bv=\lambda v+\omega v=(\lambda+\omega)v$
が成り立つため、行列 $A+B$ の固有ベクトルは $v$ のまま変わらず、固有値は和になります。
$(A \cdot B)v=A(Bv)=A(\omega v)=\omega(Av)=\omega(\lambda v)=\lambda \omega v$
と計算できるため、行列 $A \cdot B$ の固有ベクトルも $v$ のまま変わらず、固有値は積になります。

共通の固有ベクトルを持つ行列が２つあると、
その積も和も、固有ベクトルは変化せず、固有値は積や和になります。

勘のいい方はこの辺で、どうやって完全準同型にするのか、
想像がつくのではないでしょうか。

そうです、固有値を平文、固有ベクトルを秘密鍵、行列を暗号文としてしまうのです。

LWE 問題

さて、完全準同型「暗号」というからには、暗号文から平文に戻すのが
難しくなければなりません。

このままでは、暗号文である行列から固有値固有ベクトルを計算するのは容易です。

そこで出てくるのが LWE 問題（Learning With Errors Problem）です。

まず、 $n$ 個の変数でできた一次方程式が、特定の条件で $n$ 個あれば連立方程式として解けます。

$n$ 個の連立方程式を行列の形で $Ax=b$ と書き直して
（ $A$ は $n \times n$ 正方行列、 $x$ , $b$ は $n$ 次元ベクトル）、
$A^{-1}$ を求めることができれば（これが「特定の条件」）、 $x=A^{-1}b$ で解けます。

では、ここに変数を１つ加えましょう。
$Ax+e=b$ （ $e$ も $n$ 次元ベクトル）。

これだけで、 $e$ を知らない人にとっては $x$ を求めることはできなくなります。
この $e$ は小さい値で十分です。要するに誤差成分ですね。連立方程式に誤差を加えた問題。
これを LWE 問題と呼びます。この問題は量子コンピュータを使っても解けません。
つまり量子耐性がある問題なのです。

秘密の情報を知らないと解けない問題。これは暗号に使えますね。
というわけで、これを応用するのが LWE 暗号です。

GSW の原型を組み立てる

行列を暗号文、固有値を平文、固有ベクトルを秘密鍵とする考え方をそのままに、
元の式、 $Av=\lambda v$ に誤差成分を足します。 $Av=\lambda v+e$ と。

この $e$ が存在することによって、 $A$ からは $v$ も $\lambda$ も、求められなくなります。

復号するには、 $A$ から好きな行を取り出して、秘密鍵 $v$ との内積を取ります。
そして、 $v$ の同じ行の要素で割ります。すると得られるのが $\frac{A_i \cdot v}{v_i}=\lambda+\frac{e_i}{v_i}$ 。

$\lambda$ が復号で得たい平文なので、平文λは常に整数だという制約を加えた上で、
$\frac{e_i}{v_i}$ の部分が -0.5～0.5 の間に収まっていれば
$\lambda+\frac{e_i}{v_i}$ を四捨五入することで平文 $\lambda$ が得られます。

$e$ の要素が小さすぎると、 $A$ から固有値固有ベクトルの近似値が求まってしまうので、
ある程度 $v$ の要素を大きくして、 $\frac{e_i}{v_i}$ を小さいままに $e$ を大きくする必要があります。

まとめ

今回は GSW の論文で提案されている完全準同型暗号の原型まで解説しました。
次回はこのアルゴリズムの問題点と制限についてお話します。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

2020-05-18

完全準同型暗号の論文を読む - まえがき

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

世間ではゴールデンウィークでしたね。12 連休が推奨されたりして、
暇を持て余した私は、今まで読もうと思って放置していた論文を読んで過ごしました。

今回は、唐突ですが、休暇中に読んだ論文を紹介したいと思います。

英語の論文でしたが、２本、GSW の論文と TFHE の論文です。
どちらも完全準同型暗号を提案する論文です。
GSW は高校数学レベルの知識で理解できますが、TFHE の論文は非常に難解で、
Twitter で @nimdanaoto 様に何度も助けていただきました。
この場をお借りしてお礼申し上げます。

元論文（参考文献）の公開場所：
GSW: https://eprint.iacr.org/2013/340
TFHE: https://tfhe.github.io/tfhe/

準同型暗号とは

まずは GSW や TFHE が何を目指しているか、お話ししましょう。
英語の論文なので、数学用語の英単語も一緒に覚えていきましょう。

最初に用途から紹介します。

プライバシーに関わる情報や、個人情報のように、流出したら困るようなデータを、
クラウドやサーバで扱うと、業者のミスやセキュリティホールなどで
秘匿データが漏洩しそうで怖いですよね。そんな時、データを暗号化したまま
計算だけできれば、嬉しいですよね。

例えば、薬の開発をするときには化合物データベースを購入して参照します。
化合物データベースを持っている会社は、購入前に全データの開示はしたくないけれども、
ユーザが検索しようとしている化合物を、他のデータベース業者よりも数多く
取り揃えていることを示したい。という相反する要望を持っています。
一方で、ユーザ側は検索キーワードを知られると、今、着目している化合物が何なのか
流出してしまい、競合他社もそれに目を付ける可能性がありうる。
という形で、お互いに困ってしまっています。
そんな時、役に立つのが「秘匿演算技術」というもので、その手段の１つが「準同型暗号」です。
参考資料：産総研：秘密計算による化合物データベースの検索技術

f:id:y-hoshizuki:20200513214655p:plain

だいたいこんなイメージです。
これができると嬉しい。それがモチベーションです。

いろいろな準同型暗号

さて、「準同型 (homomorphic)」という概念については、以前の記事
楕円曲線論おまけの一歩 - VIPPOOL開発者ブログ
で説明しました。

２つの群 (group) や体 (field) の架け橋となる写像があって、
演算と写像、どちらを先に行っても、つまり順番を入れ替えても同じ結果になる。
というもののことでした。

ここで、２つの群があって、片方は有限巡回群（これは一周期だけ見れば整数と準同型）で、
もう片方は暗号文。つまり暗号として機能するよう、簡単には逆変換できない群です。
この２つが、加法演算について準同型となっている場合、「加法準同型暗号」と呼びます。

つまり、２を暗号化した暗号文 $c_2$ と、３を暗号化した暗号文 $c_3$ があったとき、
暗号文同士、何らかの計算をして得た $c=f(c_2,c_3)$ を復号すると
${\rm decode}(c) = 5 = 2 + 3$ となる。これが加法準同型暗号です。

f:id:y-hoshizuki:20200513214722p:plain

一方、乗法演算について同じことが言える場合は、「乗法準同型暗号」と呼びます。
これは $c=f(c_2,c_3)$ としたとき、 ${\rm decode}(c) = 6 = 2 \times 3$ ということです。

完全準同型暗号とは

さて、有限巡回群を整数に見立てて、加法や乗法のみを行う、
加法準同型暗号、乗法準同型暗号は、割と古くから知られていました。

有限巡回群は、足し算を繰り返すことで整数倍ができるので、「平文の」整数倍はできます。
同じく、乗算を繰り返せば、「平文の」べき乗計算もできます。
そういうものを「加群 (module)」と呼びます。
加法が定義された群「加法群 (additive group)」とは別なので要注意です。

でも、有限巡回群の加群が準同型暗号にできても、あまり用途は広がりません。
ここはやっぱり実数体！……とまではいかなくても、加法と乗法、
両方とも自由にできる準同型暗号が欲しいところです。
それこそが、我々の求める「完全準同型暗号 (fully homomorphic encryption, FHE)」なのです。

ちなみに、加法と乗法ができても体になるとは限りません。
が、乗法の逆元が計算できるとは限らない、体の出来損ないみたいなのを、環 (ring) と呼びます。
高校数学で習う行列などは、加法と乗法はできますが、逆行列（乗法の逆元）が
計算できない場合があるので、環です。

最低限、環が準同型暗号になれば、統計処理など、応用の幅が一気に広がります。
これが、GSW や TFHE の目指す完全準同型暗号です。

まとめ

今回は完全準同型暗号とは何か？というお話をしました。
次回は GSW の論文を解説していきます。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

2020-03-27

楕円曲線論おまけの一歩

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。
楕円曲線論はじめの一歩 (14) - VIPPOOL開発者ブログ
では、それまで実数体で定義された楕円曲線の有理点について
考察してきたのに、さらっと有限体上に再定義しました。

ここに理論の飛躍があるというご意見を頂いたので、
今回はそこについて詳しく見ていこうと思います。

準同型の厳密な定義

楕円曲線論はじめの一歩 (12) - VIPPOOL開発者ブログ
で触れた「準同型」という言葉。これが今回の鍵になります。

ここで触れた内容を数式で書いてみましょう。
楕円曲線上の点 P と Q があって、P と複素数 $w_1$ 、Q と $w_2$ が対応しています。
つまり、楕円曲線上の点からなる群 E から複素数体 C に変換する写像（関数）、
$E \stackrel{f}{\to} C$ があって、 $w_1=f(P)$ 、 $w_2=f(Q)$ なわけです。

で、楕円曲線上の加法演算 A(P,Q) と、複素数体上の加算 $A'(w_1,w_2)=w_1+w_2$ があって、
楕円曲線上で加算した結果に対応する複素数 f(A(P,Q)) と、
先に複素数に変換して加算した $A'(w_1,w_2)$ が等しい、ということでした。

まとめて数式で書くと
$f(A(P,Q))=A'(f(P),f(Q))$
ということです。

図にするとわかりやすいでしょうか。

f:id:y-hoshizuki:20200313213759p:plain

このように、楕円曲線上の点から複素数への写像と、加算演算の順番を入れ替えることができる。
もっと一般化して、「写像と演算の順序を入れ替えることができる」
というのが、準同型という言葉の意味です。

射影平面と有理点の準同型性

まず、 $x=\frac{X}{Z}$ などと置いて３次元にした射影平面の話を思い出してください。
有理点と射影平面上の像は準同型な関係になっています。

説明の簡略化のため、X 軸だけ見てみましょう。Y 軸も同様に考えられます。

射影平面上の X 座標 G から、楕円曲線上の有理点 E の X 座標への写像、
$G \stackrel{g}{\to} E$ を考えてみましょう。

$g(X,Z)=\frac{X}{Z}$
が写像となる関数です。有理点だけ考えているので、必ず分数で書き表せるところがポイントです。

実数上で定義された E の座標を計算するときは普通に
加算は $A(x_1,x_2)=x_1+x_2$ 、乗算は $M(x_1,x_2)=x_1 \times x_2$ です。
一方、G の場合は加算 $A'(X_1,Z_1,X_2,Z_2)=(X_1 \times Z_2 + X_2 \times Z_1, Z_1 \times Z_2)$ と定義します。
普通に通分して足してるだけです。乗算はもっと簡単 $M'(X_1,Z_1,X_2,Z_2)=(X_1 \times X_2, Z_1 \times Z_2)$ です。

射影平面と有限体の準同型性

こちらも同じく見ていきましょう。

射影平面上の X 座標 G から、有限体 F への写像、
$G \stackrel{g'}{\to} F$ を考えてみます。

$g'(X,Z)=X \times Z^{-1} \bmod p$
が写像となる関数です。p が素数であれば、逆元 $Z^{-1} \bmod p$ は必ず存在するのがポイントです。

G 上での加算乗算は前述の通りなので、対応する F での演算は、
加算が $A''(x_1,x_2)=x_1+x_2 \bmod p$ で、乗算が $M''(x_1,x_2)=x_1 \times x_2 \bmod p$ です。

実数体上で定義した楕円曲線上の点の群と、有限体上で定義した点の群の準同型性

以上のお話から、「有理数体と射影平面が準同型」「射影平面と有限体が準同型」ということが
わかりましたね。ということは、「有理数体と有限体は準同型」ということが言えそうですね。

まとめ

今回は、楕円曲線論の最後でさらっと流した部分を詳しく見てみました。
またわかりづらい点などありましたら、ご指摘いただければ解説いたしますので、
お気軽にご意見ご感想など頂ければと思います。

今回はここまで。

2020-01-14

承認数って何？～暗号資産の安全性～ (2)

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は、暗号資産の安全性を説明するために、攻撃者の役になり切って、
どうやって改ざんを行うかについて考えました。
そして、その方法を数学で説明できるモデルに落とし込むところまでお話しました。

今回は、このモデルについて解析して、どういう条件で攻撃が成功するのか考え、
その反対の条件を満たせば安全だ、というお話をします。

ランダムウォークモデルでゴールする確率

これは前回出したモデルです。

f:id:y-hoshizuki:20191220180026p:plain

ここで登場するのが、承認数です。このすごろくの出発点とします。
つまり、攻撃者がどのタイミングから攻撃を開始するか、
という数字なわけです。とりあえず z としておきましょう。

bitcoin の元論文でも言及されていますが、
確率過程の面倒な議論はすっ飛ばして結果だけ書くと、
$\sum_{k=0}^z \frac{(z\frac{p}{1-p})^k e^{-z\frac{p}{1-p}}}{k!} (1-(\frac{p}{1-p})^{z-k})$
の確率で改ざん攻撃に失敗します。一般的に確率は 100% を 1 とするので、
1 からこの値を引けば、成功する確率になります。

計算めんどうですね。そんなときは、みんな大好き Wolfram|Alpha: Computational Intelligence で計算できます。
以下の数式を入力してみてください。

sum (z*p/(1-p))^k*e^(-z*p/(1-p))/k!*(1-(p/(1-p))^(z-k)), k=0 to z, where p=0.4, z=6

p=0.4、つまり攻撃者のハッシュレートが全体の 40%、
z=6、つまり承認数 6 の状態から追いかけっこを開始した場合、
0.49602。つまり 49.602% の確率で失敗します。
1 から引いて 0.50398、つまり 50.398% の確率で成功します。

最後の where 以降がパラメータです。いろいろ変えてみて試してみてください。

専用の計算機を公開してる人もいます。
https://people.xiph.org/~greg/attack_success.html
こちらは成功率をそのまま表示します。

さて、ここから何がわかるでしょう

この式を見て、何かを感じ取れる人はそうそう居ないと思いますので、
いろいろパラメータを変えて試してみましょう。

	10%	30%	49.99%	50%
1	20.4%	62.7%	99.9%	100%
6	0.02%	13.2%	99.9%	100%
10	0.000012%	4.16%	99.9%	100%
144	≒0	≒0	99.8%	100%

承認数と、攻撃者のハッシュレートの割合を変えながら、攻撃の成功率を求めてみました。

お気づきになられたでしょうか。攻撃者のハッシュレートの割合が 50% になった瞬間、
承認数をいくら増やしても、成功率が 100% になるのです。

これが「51% 攻撃」の意味です。
「どれだけ承認数を確保しても必ず改ざんが成功する条件」、
それが、「ハッシュレートの割合の 50% 以上を占める」なのです。

じゃあ、承認数いくつなら安全なの？

今度はモナコインを受け取る側、攻撃される側に立ってみましょう。

あなたは何かの商品を販売しています
お客さんからモナコインで支払いを受けました
さて、承認数いくつまで待てば安全でしょうか？

これは、bitcoin wiki の Confirmation - Bitcoin Wiki ページにあるとおり、
ケースバイケースとしか言いようがありません。

例えば、100円の価値のものを販売したとして、
1% の確率で持ち逃げされる可能性は高いと感じますか？低いと感じますか？
そのためにわざわざ何承認も待つより、いっそ 0 承認でも、
他のお客さんの接客をした方が利益になりませんか？

例えば、1億円の価値にあるものを販売したとして、
0.1% の確率で持ち逃げされる可能性は、高いと感じますか？低いと感じますか？
どこまで攻撃成功率が下がるまで待てば安心できますか？

これはそういう話になります。

また別の観点もあります。

攻撃用のハッシュレートを高めるにはそれなりの機材と電気代がかかります。
100円の価値のものを持ち逃げするために、数万、数十万と機材や電気代をかけますか？

昔から付き合いのある会社で、これからも付き合いがある可能性の高い取引先が、
高い費用と信用を失ってまで改ざんすると思えますか？

そういうことを総合的に見て、安全と思える承認数を決めてね、と bitcoin wiki には書いてあります。

適切に承認数を決めれば、通貨として安全に使えますよ、というのが、暗号資産の安全性の本質です。

まとめ

今回は、前回のランダムウォークモデルから攻撃成功率を計算して、
その意味や、承認数についてお話ししました。

承認数を適切に決めることで、安全性と利便性のバランスの取れた運用をするのが本来あるべき姿です。
また、51% 攻撃の意味についても少し触れました。正確な認識がもっと広まると嬉しいです。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

2020-01-06

承認数って何？～暗号資産の安全性～ (1)

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

今回はモナコインなどを送金する際に表示される「承認数」について、
また、これに関連して、どうして暗号資産が安全と言われるのか、
その辺りについてお話したいと思います。

また、世間で若干誤認されがちな、51% 攻撃についても少し触れたいと思います。

攻撃者を想定してみる

暗号の世界で「安全かどうか」を考えるときには、「攻撃者」を想定することが大事です。

というわけで、以下のシナリオを想定してみましょう。

あなたはモナコインでお買い物をします
その商品の価格は 1.0 MONA でした
あなたは 1.0 MONA を送金し、商品を手に入れました
はい、ここで 1.0 MONA の送金をなかったことにしましょう

これが、暗号資産の想定する「攻撃者」です。
あなたがこの立場になるとしたら、どんなやり方を思いつきますか？

一番に思いつきそうなのは、そう、ブロックチェーンの履歴の改ざんです。
履歴の改ざんをする方法について考えてみましょう。

ブロックチェーンの履歴の改ざん方法

ブロックチェーンは、おおむね一定時間ごとに新しいブロックを付けたしながら
伸びていきます。そして、複数のマイナーがいるため、ブロックのチェーンが分岐する
場合があります。

f:id:y-hoshizuki:20200106150903p:plain

この場合、しばらく様子を見て、ブロックの累積 difficulty が多い方のチェーンは、
それだけ多くの計算資源が投入されている、つまり、正当なノードが集まっている証拠。信用できる。
というわけで、短い方を切り捨てて、全員で長い方に集まるルールで動いています。

これこそ、PoW の根幹を成しているルールです。

ということは、このルールに背くマイナーがいれば、安全の根拠が崩れる、つまり改ざんに成功します。

f:id:y-hoshizuki:20200106150450p:plain

このように、累積 difficulty の大きいチェーンを無視して、1.0 MONA の支払いがなかった歴史のチェーンを
掘り続けるマイナーがいれば、まずは第一段階クリアです。

でも、この歴史のチェーンは、他の正当なノードから見ると「最長のものより短い」チェーンなので、
累積 difficulty はどうしても少なめになりがちです。そのため、このチェーンは無視されてなかったことにされます。

ではどうするか。

f:id:y-hoshizuki:20200106150523p:plain

このように、一瞬でもいいから、正当なチェーンよりも長く伸ばすことを目標にします。
累積 difficulty なので、長ければ長いほど、大きくなる傾向があるため、長さは重要なファクターです。
すると、他の正当なノードも、ルールにのっとって、この改ざんされた歴史が正しいものとしてマイニングを始めます。

これで、あなたの支払いはなかったことになり、でも商品は受け取った後なので、
両取りの状態、つまり商品をだまし取ることに成功するわけです。
つまり攻撃者は、一瞬でいいからこの状態になることを目標にします。

要約すると、「正当なチェーンと延長の追いかけっこをして、一瞬でも追い抜けば勝ち」というゲームです。

「ブロック延長の追いかけっこ」を「ランダムウォークモデル」で表す

さて、じゃぁどうすれば正当なノードよりも伸ばすことができるのでしょうか？

それを考察するために、数学的に扱うことができるモデルに落とし込みます。

まずは前提として、モナコインのマイナー全員の総ハッシュレート（演算能力）を 100 % として、
攻撃者側のハッシュレートが p % あると仮定します。

すると、正当な歴史のチェーンは、一定時間おきに 100-p % の確率で 1 ブロック伸びます。
反対に、改ざんされた歴史のチェーンは、一定時間おきに p % の確率で 1 ブロック伸びます。

この追いかけっこは、改ざんされた歴史のチェーンのブロック高（長さ）を基準点、0 として、
正当な歴史のチェーンのブロック高を相対値でみたとき、
以下のような状態遷移のモデルで数学的に表すことができます。

f:id:y-hoshizuki:20191220180026p:plain

これは、数学の世界では「ランダムウォークモデル」と呼ばれて、確率過程という分野で扱います。

すごろくのように、今の状態の位置にコマを置いて、確率に従ってコマを移動していくイメージです。
矢印についている確率が、その状態遷移が発生する確率です。

この図で、0 の位置が、正当な歴史と改ざんされた歴史のチェーンの長さがそろっている状態です。
1 は、改ざんされた歴史のチェーンが 1 ブロック短い状態です。
同様に、2 は、改ざんされた歴史のチェーンが 2 ブロック短い状態です。
反対に、-1 は改ざんされた歴史のチェーンの方が、正当な歴史のチェーンより 1 長い状態です。

つまり、-1 の状態に 1 度でも踏み込むことができれば、攻撃者の勝ちになります。

ちなみに、この図の子は、執筆者、星月が趣味で発注したイメージキャラです。
株式会社 VIPPOOL とは何の関係もないですが、図面がいつもフリー素材では味気ないので、
これからもたまに顔を出してもらう予定です。

まとめ

今回は、暗号資産の安全性を説明するために、攻撃者の役になり切って、
どうやって改ざんを行うかについて考えました。
そして、その方法を数学で説明できるモデルに落とし込むところまでお話しました。

次回は、このモデルについて解析して、どういう条件で攻撃が成功するのか考え、
その反対の条件を満たせば安全だ、というストーリーでお話します。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

2019-10-07

量子コンピュータとモナコイン (2)

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は、量子コンピュータについて基本的なお話と、
モナコインの公開鍵から、秘密鍵を計算できてしまう。
というお話をしました。
今回はその対策について考えてみましょう。

マイニングについて

まずは PoW の根幹をなしているハッシュ関数、
これについては、量子コンピュータでも効率的な計算方法は見つかっていません。

つまり、量子コンピュータが実用化されても、データの改ざんは簡単にはできないことを意味します。

まずはブロックチェインとしての基礎は大丈夫そうですね。

送金について

次に、問題となる秘密鍵が計算できてしまう問題について、
こちらは、もう使っている人はいないと思いますが、
P2PK で送金してはいけません。

f:id:y-hoshizuki:20190912153531p:plain

このように、scriptPubKey に、公開鍵 xG が書かれているので、
ここから秘密鍵 x を計算して資産を盗まれてしまいます。

今、主流となっている P2PKH だとどうでしょう？

f:id:y-hoshizuki:20190912153554p:plain

scriptPubKey に書かれているのは、公開鍵のハッシュ、
ripemd160(sha256(xG)) です。ripemd160 も sha256 も、
量子コンピュータで逆算する効率のいい方法はまだ見つかっていません。
つまり、これなら安全。

……と思うでしょう？

f:id:y-hoshizuki:20190912153605p:plain

P2PKH は、UTXO をアンロックするときに公開鍵 xG を scriptSig に書いてしまうんですよね。

ということは……？

f:id:y-hoshizuki:20190912153617p:plain

そう、UTXO をそのままアンロックすることはできないけれども、
同じコインアドレスを使っている UTXO があれば、そちらをアンロックすることは
できてしまうのです。

つまり、
・秘密鍵（コインアドレス）は使い捨て
・必ず毎回、すべての UTXO を使い切るように運用する
必要があります。

f:id:y-hoshizuki:20190912153630p:plain

さて、これで大丈夫でしょうか？

ところが、モナコインを含む暗号資産には、
「承認数」＝「ブロックチェインに取り込まれてから掘られたブロックの高さ」
が増えるほどにトランザクションの改ざんが難しくなる。
という特徴があります。

言い換えれば、承認数が少なければ、例えば承認直後であれば、
トランザクションの改ざんは簡単に行うことができます。
つまり...

f:id:y-hoshizuki:20190926153349p:plain

このように、攻撃対象のアカウントから送金が行われたことを見つけ次第、
量子コンピュータで秘密鍵を割り出し、その秘密鍵で自分宛てに送金。
そしてそのトランザクションを含ませたブロックチェインを伸ばせば、
暗号資産を奪取することができてしまいます。

一度、元のチェインを追い越してしまえば、そちらが分岐と判断され破棄されます。
そして暗号資産を奪った方のチェインが正式なものとして扱われるようになります。

残念ながらこの対策は、現状できません。

まとめ

今回は、量子コンピュータが実用化された後、
どうすればモナコインを安全に使い続ける方法について考察しました。

P2PK でも P2PKH でも、暗号資産を奪われてしまいます。これは大変。

実用化が近くなれば、また BIP などで改善されることでしょう。
それに、256bit の楕円曲線暗号の計算ができるには、
まだまだ時間がかかりそうですので、しばらくは安心してもいいと思います。

米国 NIST の公開している資料 SP800-57 でも、量子コンピュータの実用化まで
含めて検討した上で、楕円曲線暗号 256bit は、2030 年以降も安心して使えると報告されています。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

はじめに

おさらい - GSW の原型

問題点：誤差が累積していく

解決策の準備 - と

と の性質

の意味するところ

で、 は何が嬉しいの？

これって完全準同型暗号？？

まとめ

はじめに

固有値と固有ベクトル

LWE 問題

GSW の原型を組み立てる

まとめ

はじめに

準同型暗号とは

いろいろな準同型暗号

完全準同型暗号とは

まとめ

今回のおはなし

準同型の厳密な定義

射影平面と有理点の準同型性

射影平面と有限体の準同型性

実数体上で定義した楕円曲線上の点の群と、有限体上で定義した点の群の準同型性

まとめ

はじめに

ランダムウォークモデルでゴールする確率

さて、ここから何がわかるでしょう

じゃあ、承認数いくつなら安全なの？

まとめ

はじめに

攻撃者を想定してみる

ブロックチェーンの履歴の改ざん方法

「ブロック延長の追いかけっこ」を「ランダムウォークモデル」で表す

まとめ

はじめに

マイニングについて

送金について

まとめ

解決策の準備 - ${\rm BitDecomp}$ と ${\rm BitDecomp}^{-1}$

${\rm BitDecomp}$ と ${\rm BitDecomp}^{-1}$ の性質

${\rm Flatten}(a)$ の意味するところ

で、 ${\rm Flatten}(a)$ は何が嬉しいの？