2020-09-14

VMINEを使ってみた

はじめに

みなさんこんにちは。

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

今回はVIPPOOLが販売している世界最高水準の性能を誇る
アルトコイン向けマイニングボード「VMINE」を使用してみる記事です。

VMINEの外観

f:id:y-hoshizuki:20200904151617j:plain

箱から本体を取り出しました。付属品はありません。2つのファンの下にヒートシンクがあります。直接見ることはできませんが、ヒートシンクの下にマイニングチップが並んでいます。ヒートシンクの脇には電源供給や通信のための端子があります。
このボードはPCIeカードの形状をしているので、グラフィックカードと同様に市販のマイニングリグ筐体に取り付けることが可能です。

f:id:y-hoshizuki:20200904151639j:plain

上側側面には電源端子と複数枚接続用端子があります。

f:id:y-hoshizuki:20200904151651j:plain
ブラケット面にはmicro-USB端子があります。写真は試作品のためリセットスイッチがありますが、製品にはありません。

マイニングの準備

さっそくマイニングの準備をしていきます。今回はマイニングリグに組み込まず、卓上に平置きするので、ボード裏側に市販のゴム足（タカチ電機工業　B26-11）を取り付けました。

f:id:y-hoshizuki:20200904151702j:plain

続いて電源とUSBケーブルを接続します。今回は市販のATX電源（Seasonic SSR-850FX）を使用しました。

これで接続は完了です。電源ユニットのスイッチをONにすると、システムが動作していることを示すボード上のLEDが点滅し、ファン（光らない）が回転し始めます。

f:id:y-hoshizuki:20200904151717j:plain

次にマイニングソフトウェアを準備します。
配布されているファイル一式をダウンロードし、ドライバをインストールします。

マイニング

マイニングには VMINE 用にカスタムされた専用マイニングソフトウェア、vminer を使用します。
使用するアルゴリズムや接続するプール等を指定して vminer を起動するとマイニングが始まります。

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

あとはこのまま放置するだけです。コンソール画面には現在のハッシュレートが表示されており、ほぼ公称値と同じ値が出ています。
ファンは過不足なく冷却するよう制御されており、卓上に置いていても極端にうるさいとは感じません。

マイニングを開始して10分ほど経過した状態の消費電力は176Wでした。今回使用した電源は80 PLUS GOLDなので、消費電力も公称値どおりと言えるでしょう。

f:id:y-hoshizuki:20200904151802j:plain

おまけ

VMINE はボード同士を複数枚接続して、マイニング能力を増強することができます。
VMINEを複数枚購入するとボード間接続用の専用ケーブルが付属します。
試しに2枚目のVMINEを接続してみました。

f:id:y-hoshizuki:20200904151813j:plain

VIPPOOLのコンソール画面からもハッシュレートを確認できます。約 350W でこのハッシュレートですから電力性能は GPU より格段に良いです。

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

まとめ

VIPPOOL が発売している世界最高水準の性能を誇るアルトコイン向けマイニングボード「VMINE」を試してみました。
ケーブル2本の接続とドライバインストールだけで、ASICマイニングが楽しめます。

私は次の冬にVMINEを暖房代わりにして暖を取ろうと企んでいます。
暖房として使う場合は消費電力が大きくなるlyra2zでマイニングするのがおすすめです。

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

2020-07-20

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

はじめに

みなさんこんにちは。

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

前回は、TFHE bootstrapping の第二段階、 ${\rm SampleExtract}$ を用いて TLWE 暗号文を計算しました。
しかし、入力されたデータと鍵が異なります。それを修正するのが今回の記事となります。

ていうかなんでそもそも違う鍵を使ったの？

$\vec{s}=\vec{s'}$ ならここで話は終わっていたのですが、
残念ながらそうはいきません。TLWE と TRGSW ではビット長と暗号強度に
差があるからです。ある程度揃えるためには、違う長さの鍵を使うしかありません。

というわけで、 $\vec{s} \neq \vec{s'}$ ということで頑張りましょう。
TFHE bootstrapping の最後のステップです。

キースイッチングキー

NAND 演算に使う TLWE 暗号文の鍵 $\vec{s}$ は $n$ 次のベクトルです。
これを使って、bootstrapping key を作成したときの $N$ 次のベクトルの鍵、
$\vec{s'}$ を暗号化します。

ちょっとコツがあって、 $s'_i \times 2^{-1}$ $s'_i \times 2^{-2}$ $s'_i \times 2^{-3}$ ... と、 $\mathbb{T}$ の要素、
0 から 1 の実数を二進数で表現した時の各桁にずらした値として
暗号化します。秘密鍵は先ほどお話しした通り $\vec{s}$ です。

この時の「桁数」 $t$ はシステムパラメータとして、最終的な誤差に影響を与えるため、
設計時には調整が必要です。

試しに $\vec{s}$ 鍵で復号すると、
$\phi_s({\rm KS}_{i,j})=s'_i \times 2^{-j}$
こんな感じになります。

これを、キースイッチングキーと呼びます。

公開関数的な鍵スイッチング（Public Functional Key Switching)

さて、前回の計算結果である TLWE 暗号文 $c_s=(\vec{a},b)$ は $\vec{s'}$ で暗号化された、
$0$ もしくは $\frac{1}{4}$ の値です。
$\vec{a}$ の要素数は、 $\vec{s'}$ と同じく $N$ 個です。

これを１つずつそれぞれ、 $t$ bit の固定小数に変換します。
すると、この形式で書けます。 $a_i \approx \sum_{j=1}^t a_{i,j} \times 2^{-j}$
この段階で誤差が増えますが、以前と同様、システムパラメータで絶対値の最大値を制約できます。

で、鍵スイッチングの本体、以下の暗号文を計算します。
$c_o=(\vec{0},b)-\sum_{i=1}^{N} \sum_{j=1}^t a_{i,j} \times {\rm KS}_{i,j}$

何をしているのか、復号してみるとわかります。
$\phi_s(c_o)=\phi_s( (\vec{0},b) )-\sum_{i=1}^{N} \sum_{j=1}^t a_{i,j} \times \phi_s({\rm KS}_{i,j})$
しれっと $\phi$ 関数が中に入っていきますが、線形性という性質があるので問題ないです。
で、 $b$ の項は自明な暗号文なので $b$ になり、前章で試しに復号した結果を代入すると、
$\phi_s(c_o)=b-\sum_{i=1}^{N} \sum_{j=1}^t a_{i,j} \times s'_i \times 2^{-j}$
$=b-\sum_{i=1}^{N} \sum_{j=1}^t s'_i \times a_{i,j} \times 2^{-j}$
で、 $s'_i$ は $j$ に対して定数なのでくくりだして、
$=b-\sum_{i=1}^{N} s'_i \sum_{j=1}^t a_{i,j} \times 2^{-j}$
先ほど固定小数に分解したときの式を代入します。
$\approx b-\sum_{i=1}^{N} s'_i \times a_i = \phi_{s'}( (\vec{a},b) )=\phi_{s'}(c_s)$

というわけで、 $\phi_s(c_o) \approx \phi_{s'}(c_s)$ となり、
めでたく鍵の切り替えができました。

実用には必要ないので、公開関数の適用については割愛します。

計算結果について

この段階で、TLWE 暗号文 $c_o$ は、bootstrapping の入力とした
TLWE 暗号文 $c$ と同じ秘密鍵で暗号化されており、
$\phi_s(c)$ が $\frac{1}{2} \pm \frac{1}{4}$ の場合は $\phi_s(c_o)$ は $\frac{1}{4}$ 、
それ以外、つまり $\phi_s(c)$ が $\pm \frac{1}{4}$ の場合、 $\phi_s(c_o)$ は $0$
となっています。

そして、平文に乗っている誤差は、TLWE 暗号文の整数化で加わる誤差と、CMux で加わる誤差、
公開鍵スイッチングで固定小数化した時の誤差など、
すべてシステムパラメータで制約できるものなので、
全部ひっくるめて誤差が $\pm \frac{1}{16}$ となるように調整します。

すると、以前説明した通り、自明な暗号文として $\frac{5}{8}$ から２つの暗号文を引く、
つまり $c=(\vec{0},\frac{5}{8})-c_1-c_2$ を計算すると、その平文は以下のようになります。

$\phi_s(c_1)$	$\phi_s(c_2)$	$\phi_s(c)$
$\pm \frac{1}{16}$	$\pm \frac{1}{16}$	$\frac{5 \pm 1}{8}$
$\frac{1}{4} \pm \frac{1}{16}$	$\pm \frac{1}{16}$	$\frac{3 \pm 1}{8}$
$\pm \frac{1}{16}$	$\frac{1}{4} \pm \frac{1}{16}$	$\frac{3 \pm 1}{8}$
$\frac{1}{4} \pm \frac{1}{16}$	$\frac{1}{4} \pm \frac{1}{16}$	$\frac{1 \pm 1}{8}$

この $c$ を TFHE bootstrapping に入力すれば、何度でも NAND 演算ができます。

これで、完全準同型暗号の完成です。

NAND 以外の論理演算

最初に説明した通り、 $\{{\rm NAND}\}$ は完備集合なので、これだけあればどんな演算も
できるのですが、他の論理演算もできれば便利だし計算量も減るので、
元論文ではいくつか提示されています。

${\rm NOT}(c)=(0,\frac{1}{4})-c$ これは誤差が増えないため bootstrapping は不要です。
${\rm AND}(c_1,c_2)={\rm bootstrapping}( (0,-\frac{1}{8})+c_1+c_2)$
${\rm OR}(c_1,c_2)={\rm bootstrapping}( (0,\frac{1}{8})+c_1+c_2)$
${\rm XOR}(c_1,c_2)={\rm bootstrapping}(2 \times (c_1-c_2))$

など。実際どういう値になるのかはみなさまでご確認ください。

まとめ

今回は TFHE bootstrapping の最後のステップ、公開鍵スイッチングについて解説して、
完全準同型暗号を完成させました。

TFHE 元論文には、他にもいろいろなテクニックが書かれているため、
読んでみると面白いですよ。量はすごくたくさんありますが。

ということで、今回の連載はこれで終了にしたいと思います。

みなさん、お付き合いいただき、ありがとうございました。
ご質問、ご意見等ありましたらお気軽にリプライください。
それではまた。

2020-07-13

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

はじめに

みなさんこんにちは。

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

前回は TFHE bootstrapping の第一段階、 ${\rm BlindRotate}$ で、
定数項として都合のいい値を持つ多項式を平文とする TRLWE 暗号文を作成しました。

今回はここから、定数項だけ取り出して TLWE 暗号文に変換します。

TRLWE 暗号文の復号を観察する

任意の TRLWE 暗号文は、次数を $N$ として、
$A(X)=\sum_{i=1}^N a_i X^{i-1}$
$B(X)=\sum_{i=1}^N b_i X^{i-1}$
と多項式を置いて、
$c=(A(X),B(X))$
という形で表現できます。

さて、これを秘密鍵 $\vec{s'}$ で復号してみましょう。
秘密鍵の多項式を $S'(X)=\sum_{i=1}^N s'_i X^{i-1}$ とおいて、
$\phi_{s'}(c)=B(X) - S'(X) \cdot A(X)$
$=\sum_{i=1}^N b_i X^{i-1} - \sum_{i=1}^N \sum_{j=1}^N a_i s'_j X^{(i+j-2)}$
と展開できます。

掛け算のひっ算をするとき、真ん中の段は平行四辺形になりますよね。
なので、真ん中で分割します。
$=\sum_{i=1}^N b_i X^{i-1} - \sum_{i=1}^N \sum_{j=i-1}^{N+i-2} a_i s'_{j-i+2} X^j$
$=\sum_{i=1}^N b_i X^{i-1} - \sum_{i=1}^N \sum_{j=i-1}^{N-1} a_i s'_{j-i+2} X^j - \sum_{i=1}^N \sum_{j=N}^{N+i-2} a_i s'_{j-i+2} X^j$
$=\sum_{j=1}^N b_j X^{j-1} - \sum_{j=0}^{N-1} \sum_{i=1}^{j+1} a_i s'_{j-i+2} X^j - \sum_{j=N}^{2N-2} \sum_{i=j-N+2}^N a_i s'_{j-i+2} X^j$
$=\sum_{j=0}^{N-1} b_{j+1} X^j - \sum_{j=0}^{N-1} \sum_{i=0}^{j} a_{i+1} s'_{j-i+1} X^j - \sum_{j=0}^{N-2} \sum_{i=j-N+1}^{-1} a_{i+N+1} s'_{j-i+1} X^{j+N}$
$=\sum_{j=0}^{N-2} b_{j+1} X^j + b_N X^{N-1} - \sum_{j=0}^{N-2} \sum_{i=0}^{j} a_{i+1} s'_{j-i+1} X^j - \sum_{i=0}^{N-1} a_{i+1} s'_{N-i} X^{N-1} - \sum_{j=0}^{N-2} \sum_{i=j-N+1}^{-1} a_{i+N+1} s'_{j-i+1} X^{j+N}$
$=\sum_{j=0}^{N-2} (b_{j+1} X^j - \sum_{i=0}^{j} a_{i+1} s'_{j-i+1} X^j - \sum_{i=j-N+1}^{-1} a_{i+N+1} s'_{j-i+1} X^{j+N}) + b_N X^{N-1} - \sum_{i=0}^{N-1} a_{i+1} s'_{N-i} X^{N-1}$

ここで、多項式環の剰余環だったので、 $(X^N+1)$ で割った余りを求めます。
$=\sum_{j=0}^{N-2} (b_{j+1} X^j - \sum_{i=0}^{j} a_{i+1} s'_{j-i+1} X^j + \sum_{i=j-N+1}^{-1} a_{i+N+1} s'_{j-i+1} X^j) + b_N X^{N-1} - \sum_{i=0}^{N-1} a_{i+1} s'_{N-i} X^{N-1}$
$=\sum_{j=0}^{N-2} (b_{j+1} - \sum_{i=0}^{j} a_{i+1} s'_{j-i+1} + \sum_{i=j-N+1}^{-1} a_{i+N+1} s'_{j-i+1}) X^j + (b_N - \sum_{i=0}^{N-1} a_{i+1} s'_{N-i}) X^{N-1}$

さらに、 $a'_i=\left\{ \begin{array}{ll} a_i & (i \geq 1) \\ -a_{i+N} & (otherwise) \end{array} \right.$ と置くと、
$=\sum_{j=0}^{N-2} (b_{j+1} - \sum_{i=0}^{j} a'_{i+1} s'_{j-i+1} - \sum_{i=j-N+1}^{-1} a'_{i+1} s'_{j-i+1}) X^j + (b_N - \sum_{i=0}^{N-1} a'_{i+1} s'_{N-i}) X^{N-1}$
$=\sum_{j=0}^{N-2} (b_{j+1} - \sum_{i=j-N+1}^{j} a'_{i+1} s'_{j-i+1}) X^j + (b_N - \sum_{i=0}^{N-1} a_{i+1} s'_{N-i}) X^{N-1}$
$=\sum_{j=0}^{N-2} (b_{j+1} - \sum_{i=0}^{N-1} a'_{i+j-N+2} s'_{N-i}) X^j + (b_N - \sum_{i=0}^{N-1} a_{i+1} s'_{N-i}) X^{N-1}$
$=\sum_{j=0}^{N-1} (b_{j+1} - \sum_{i=0}^{N-1} a'_{i+j-N+2} s'_{N-i}) X^j$

これで、平文の多項式の各項の係数が求まりました。
$\phi_{s'}(c)=\sum_{j=0}^{N-1} (b_{j+1} - \sum_{i=0}^{N-1} a'_{i+j-N+2} s'_{N-i}) X^j$

で、欲しかったのは定数項の係数なので、 $j=0$ の時の係数を取り出します。
$b_1 - \sum_{i=0}^{N-1} a'_{i-N+2} s'_{N-i}$

$a''_i=a'_{-i+2}$ とおけば、
$b_1 - \sum_{i=0}^{N-1} a''_{N-i} s'_{N-i}$
$=b_1 - \sum_{i=0}^{N-1} a''_i s'_i=b_1-\vec{s'} \cdot \vec{a''}=\phi_{s'}(\vec{a''},b_1)$

という感じで TLWE 暗号の復号関数に変形できます。

つまり、前回の出力結果 $c_r=(A(X),B(X))$ から、係数を
$a''_i=\left\{ \begin{array}{ll} a_1 & (i = 1) \\ -a_{-i+N+2} & (otherwise) \end{array} \right.$ と取り出せば、
$(\vec{a''},b_1)$ が、元の TRLWE 暗号文に対応する平文多項式の、
定数項と同じ値を平文として持つ新しい TLWE 暗号文となるわけです。

これを ${\rm SampleExtract}$ と元論文では呼んでいます。

この段階で、 $-\mu$ もしくは $\mu$ の暗号文が得られているので、
$\mu$ の自明な暗号文 $(0,\mu)$ を加えて、 $c_s=(\vec{a''},b_1)+(0,\mu)$
をこのステップの出力とします。すると、平文は $0$ もしくは $\frac{1}{4}$ となります。

また、この操作では誤差は追加されません。

まとめ

今回は ${\rm SampleExtract}$ を導出して、
TRLWE 暗号文を復号することなく、対応する平文多項式の定数項と
同じ値を平文として持つ TLWE 暗号文を算出しました。

しかし、この暗号文の秘密鍵は最初の入力 $\vec{s}$ ではなく、 $\vec{s'}$ となってしまっています。
これを修正するのが次回の記事になります。

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

2020-07-06

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

はじめに

みなさんこんにちは。

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

前回は、駆け足で TFHE の全体像を見ました。
今回からは、bootstrapping の手順を１つずつきちんと見ていこうと思います。

bootstrapping key の組み立て

TLWE 暗号文に使う秘密鍵 $\vec{s}$ （ $n$ 次とします）とは別に、
bootstrapping に使うために $\vec{s}$ を暗号化するための鍵、
$\vec{s'}$ を二進数で選びます。このベクトルの次数は、あとで出てくる
テストベクタ多項式 $T(X)$ の次数とそろえる必要があります。

そして、 $\vec{s}$ の各要素ごとに、TRGSW の暗号文を作ります。

まず、Gadget Decomposition から元に戻す作用素を $H$ としました。
$\vec{s'}$ で復号すると $\phi_{s'}(Z_j)=0$ となる TRLWE 暗号文を $2 \ell$ 個だけ作成します。
そうして TRGSW 暗号文の構成通り、
${\rm BK}_i=\left(\begin{array}{c} Z_1 \\ Z_2 \\ \vdots \\ Z_{2 \ell} \end{array}\right) +s_i \cdot H$
とします。この TRGSW 暗号文を $n$ 個用意したセットを bootstrapping key と呼びます。

${\rm BlindRotate}$ に必要な道具、 ${\rm CMux}$

先ほど作った TRGSW 暗号文 ${\rm BK}_i$ と TRLWE 暗号文 $d$ の外積を、
${\rm BK}_i \times d={\rm Dec}(d) \cdot {\rm BK}_i$ と定義します。

Gadget Decomposition は、 $\|d-\vec{v} \cdot H\|$ を最小化する $\vec{v}$ だったので、
$\vec{v}={\rm Dec}(d)$ と誤差 $(\epsilon_a(X),\epsilon_b(X))$ を用いて、
$\vec{v} \cdot H = d + (\epsilon_a(X),\epsilon_b(X))$ と書けます。

すると、
${\rm BK}_i \times d={\rm Dec}(d) \cdot {\rm BK}_i$
$=\vec{v} \cdot \left(\begin{array}{c} Z_1 \\ Z_2 \\ \vdots \\ Z_{2 \ell} \end{array}\right)+s_i \times \vec{v} \cdot H$
となり、左半分は内積を計算し、右半分は先ほどの式を代入すると、
$=\sum_{j=1}^{2 \ell} v_j \times Z_j+s_i \times (d + (\epsilon_a(X),\epsilon_b(X)))$
$=\sum_{j=1}^{2 \ell} v_j \times Z_j+s_i \times d + s_i \times (\epsilon_a(X),\epsilon_b(X))$
となり、３つの暗号文、
$c_1=\sum_{j=1}^{2 \ell} v_j \times Z_j$
$c_2=s_i \times d$
$c_3=s_i \times (\epsilon_a(X),\epsilon_b(X))$
の和を計算したことと同じになります。

TRLWE 暗号も加法準同型の性質を持つため、暗号文同士の和を取ると、
平文同士の和を取ったことになります。

このうち、 $c_1$ は $Z_j$ を何倍かして足したものなので、
平文 $\phi_{s'}(c_1)$ の期待値は 0 になります。

また $c_3$ を復号した $\phi_{s'}(c_3)$ は、
平文の絶対値の大きさをシステムパラメータで制約できるため、
この後の演算も含めて十分に小さくなるように設定します。

そうすると、 $\phi_{s'}({\rm BK}_i \times d)=\phi_{s'}(s_i \times d)$ となりますが、
$s_i$ が 0 であっても 1 であっても、計算結果は３つの暗号文の和になっているため、
単純な比較では $s_i$ がどちらなのか判別がつかないところが重要なポイントです。

さて、ここまでできればあとは簡単な話で、２つの平文 $\mu_0$ $\mu_1$ に対応する
TRLWE 暗号文 $d_0$ $d_1$ があるとして、 $d=d_1-d_0$ と代入して、
最後に $d_0$ を加算すれば、 ${\rm CMux}$ の完成です。

${\rm CMux}({\rm BK}_i,d_1,d_0)={\rm BK}_i \times (d_1-d_0)+d_0={\rm Dec}(d_1-d_0) \cdot {\rm BK}_i+d_0$

何をしているかというと、 $s_i$ が 0 なら $\mu_0$ 、1 なら $\mu_1$ の暗号文を、
復号することなく選択します。C 言語風に書けば $s_i?\mu_1:\mu_0$ です。

$\mu_0$ もしくは $\mu_1$ の暗号文を計算はできるけれども、どちらを選択したのかわからない。
それが ${\rm CMux}$ 関数です。 ${\rm BlindRotate}$ のコアとなる重要なパーツです。

${\rm BlindRotate}$ を計算する

前回説明した通り、平文 $\Phi$ を秘密鍵 $\vec{s}$ で暗号化された TLWE 暗号文 $c$ があるとします。

$X$ をかけ続けると位数 $2N$ の有限巡回群をなす、 $N$ 次の多項式、
$F(X)=\mu X^{N-1}+\mu X^{N-2}+\cdots+\mu X+\mu$
に $X^{\frac{N}{2}}$ を掛けた多項式をテストベクタ $T(X)=F(X) \cdot X^{\frac{N}{2}}$ とします。
なお、 $\mu=\frac{1}{8}$ とします。

$c=(\vec{a},b)$ として、 $\vec{a}$ の各要素と $b$ を $2N$ 倍してから四捨五入します。
そうして作った暗号文 $c'=(\vec{a'},b')$ を復号すると、
$\Phi'=\phi_s(c') \approx 2N \times \phi_s(c)=2N\Phi$ となります。
この時の誤差も後できちんと考慮する必要がありますが、
$N$ が大きくなるほど誤差は小さくなります。

テストベクタ $T(X)$ を平文とする自明な TRLWE 暗号文 $(0,T(X))$ を用意して、
$A_0=X^{-b'} \times (0, T(X))=(0,X^{-b'} \times T(X))$ とします。

以降、 ${\rm BK}_i$ を用いて、順番に $A_i={\rm CMux}({\rm BK}_i,X^{a'_i} A_{i-1},A_{i-1})$ を計算します。

すると、 $s_i$ が 0 の時はそのまま、つまり $X^0$ が、1 の時は $X^{a'_i}$ が順番に乗算されていくので、
$\phi_{s'}(A_0)=X^{-b'} T(X)$
$\phi_{s'}(A_1)=X^{s_1 a'_1 - b'} T(X)$
$\phi_{s'}(A_2)=X^{s_2 a'_2 + s_1 a'_1 - b'} T(X)$
と繰り返すと、
$\phi_{s'}(A_n)=X^{\sum_{i=1}^n s_i \times a'_i - b'} T(X)$
となり、 $X$ の肩に乗っているのは、復号関数 $\phi_s(c')$ と等しいので
$\phi_{s'}(A_n)=X^{-\phi_s(c')} T(X)$
となります。

要するに、 $A_n$ は、 $T(X)$ に $X^{-1}$ を $\Phi'$ 回乗算した多項式の暗号文となります。

この時、平文の多項式の定数項だけ見ると、
$\phi_s(c')$ が $\frac{N}{2}$ 以上、 $\frac{3N}{2}$ 未満の場合、つまり $\phi_s(c)$ が $\frac{1}{2} \pm \frac{1}{4}$ の場合、定数項は $\mu$ となり、
それ以外、つまり $\phi_s(c)$ が $\pm \frac{1}{4}$ の場合、定数項が $-\mu$ となるのは
前回説明した通りです。

まとめ

今回は ${\rm CMux}$ を組み立ててから ${\rm BlindRotate}$ を計算して、
平文として「定数項に都合のいい係数を持つ多項式」を持つ TRLWE 暗号文を作成しました。
次回はこの平文多項式の定数項を平文とする TLWE 暗号文に変換します。

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

2020-06-29

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

はじめに

みなさんこんにちは。

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

前回は、TFHE で用いる暗号アルゴリズムを３つ紹介しました。
また、その途中で Gadget Decomposition というものについても触れました。

今回は、これらを用いてどんな風に完全準同型暗号を構成するのかを、
お話していこうと思います。

最終的に作りたいもの

前回解説した TLWE は、 $\mathbb{T}$ を平文として持ちます。
つまり、0 以上 1 未満の実数が平文となるわけです。

そこで、0 と 0 以外の数（便宜上 $\mu$ と呼びます）のどちらかを
暗号化した暗号文同士の演算、NAND を実現します。

NAND とは、論理回路で出てくる NAND 回路と同じ演算で、
$\mu$ と $\mu$ を入力とした時だけ 0 となり、それ以外では $\mu$ となる演算です。

なぜ NAND かというと、 $\{{\rm NAND}\}$ という感じに NAND だけを含む集合は、
「完備集合」と呼ばれており、「どんな演算も実現可能」な演算の集合だからです。

もちろん、加算も乗算も、NAND 演算だけの組み合わせで実現可能です。
これで完全準同型暗号を構成します。

TLWE 暗号文同士の NAND 演算

$\mu$ は 0 と区別できれば何でもいいのですが、この後の設計上の都合から、
$\mu=\frac{1}{4}$ とします。TLWE は平文に誤差を含むため、
その最大誤差を $\pm \frac{1}{16}$ とします。

すると、前回説明した通り、TLWE は加法準同型暗号なので、引き算もできます。
そして自明な暗号文（暗号化されていない）として $\frac{5}{8}$ から２つの暗号文を引く、
つまり $c=(\vec{0},\frac{5}{8})-c_1-c_2$ を計算すると、その平文は以下のようになります。

$\phi_s(c_1)$	$\phi_s(c_2)$	$\phi_s(c)$
$\pm \frac{1}{16}$	$\pm \frac{1}{16}$	$\frac{5 \pm 1}{8}$
$\frac{1}{4} \pm \frac{1}{16}$	$\pm \frac{1}{16}$	$\frac{3 \pm 1}{8}$
$\pm \frac{1}{16}$	$\frac{1}{4} \pm \frac{1}{16}$	$\frac{3 \pm 1}{8}$
$\frac{1}{4} \pm \frac{1}{16}$	$\frac{1}{4} \pm \frac{1}{16}$	$\frac{1 \pm 1}{8}$

というわけで、 $\pm \frac{1}{4}$ の範囲の平文を $\pm \frac{1}{16}$ に、 $\frac{1}{2} \pm \frac{1}{4}$ の範囲の平文を $\frac{1}{4} \pm \frac{1}{16}$ に、
つまり元の入力の値域に戻すことができれば、出力をさらに別の NAND 演算の入力とし、
無制限に何度でも NAND 演算ができるようになります。
（平文は $\mathbb{T}$ なので、0 と 1 がつながっていることに注意！）

このように、誤差を小さくする操作を bootstrapping と呼び、
「こんなものあったらいいね！」という構想自体は完全準同型暗号の研究の初期からあり、
様々な手法がかなり古くから提案されてきました。
しかし、bootstrapping に必要なデータが 1GB ほどになったり、計算量が多すぎて、
なかなか実用には程遠い……と思われていました。

それを劇的に改善したのが、TFHE という位置づけになります。
具体的には、bootstrapping に必要なデータが 16MB、
処理時間は 1 コア CPU で 13ms と論文にあります。

TFHE の bootstrapping

TFHE では、 $\pm \frac{1}{4}$ の範囲の平文を $\pm \frac{1}{16}$ に、 $\frac{1}{2} \pm \frac{1}{4}$ の範囲の平文を $\frac{1}{4} \pm \frac{1}{16}$ にするために、
３段階の処理を行います。

詳細な処理手順については次回以降、順番に解説しますが、まずは全体の流れを把握するため、
多少強引ですが、「こんな便利な関数があったら」という感じで話を進めます。

第一段階： ${\rm BlindRotate}$

多項式環の剰余環の話をしたときに、
$F(X)=\mu X^{n-1}+\mu X^{n-2}+\cdots+\mu X+\mu$
という多項式は、X をかける操作を続けると、位数 $2n$ の有限巡回群をなす、
というお話をしました。

元論文中ではこれにさらに $X^{\frac{n}{2}}$ を掛けた多項式 $T(X)=F(X) \cdot X^{\frac{n}{2}}$ を
「テストベクタ」と呼んでいます。なお、 $\mu=\frac{1}{8}$ としておきます。
これで後でつじつまが合います。

で、入力される TLWE 暗号文は先ほど $c$ としたので、
その秘密鍵、 $\vec{s}$ の要素をそれぞれ別の秘密鍵 $\vec{s'}$ を用いて、
TRGSW で暗号化した暗号文を予め用意しておきます。

$c=(\vec{a},b)$ なので、各要素を $2n$ 倍して四捨五入して整数化した $c'=(\vec{a'},b')$ を作ると、
$\phi_s(c') \approx 2n \times \phi_s(c)$ となります。これは $\phi_s$ が線形性という性質を
持っているからですが、平たく言えば、大体 $2n$ 倍の値で計算すれば、
出力も大体 $2n$ 倍になるよね、って感じの話です。

そして、テストベクタ $T(X)$ を平文とする自明な TRLWE 暗号文 $t=(0,T(X))$ から、
$X^{-\phi_s(c')}$ を乗算した TRLWE 暗号文を「復号することなく」計算する魔法のような関数、
$c_r={\rm BlindRotate}(t,c')$ を計算します。この中身は次回解説します。

すると、その TRLWE 暗号文 $c_r$ を復号して出てくる多項式 $\phi_{s'}(c_r)$ を見ると、
下位の項から数えて $\frac{n}{2}-\phi_s(c')$ 個の項は、係数が $-\mu$ となり、
負になった場合、さらに上の項から順に係数が $-\mu$ になります。

ということは、この TRLWE 暗号文を復号して、平文の定数項を見ると、
$\phi_s(c')$ が $\frac{n}{2}$ 以上、 $\frac{3n}{2}$ 未満の場合、
つまり $\phi_s(c)$ が $\frac{1}{2} \pm \frac{1}{4}$ の場合、定数項は $\mu$ となります。
それ以外、つまり $\phi_s(c)$ が $\pm \frac{1}{4}$ の場合、定数項が $-\mu$ となります。

この平文の定数項、都合がいいですね。というわけで、自明な TRLWE 暗号文 $(0,\mu)$ を加えて、
定数項を $0$ もしくは $2\mu=\frac{1}{4}$ にしてから次の段階へ進みます。

第二段階： ${\rm SampleExtract}$

TRLWE 暗号文 $c_r$ の平文多項式の定数項が、都合よく $0$ か $\frac{1}{4}$ になりました。
なので、これまた「復号することなく」、定数項を平文とする TLWE 暗号文に変換します。

これを、 $c_s={\rm SampleExtract}(c_r)$ と呼びます。これも次回以降説明します。

第三段階：公開関数的な鍵スイッチング（Public Functional Key Switching)

元の TLWE 暗号文 $c$ は秘密鍵 $\vec{s}$ で暗号化されていますが、
${\rm SampleExtract}$ で出てくる TLWE 暗号文 $c_s$ は、
$\vec{s}$ を TRGSW で暗号化した時に使った鍵、 $\vec{s'}$ で暗号化されています。

そこで、平文を変えることなく、鍵だけ差し替えます。
これも、復号することなく行います。

論文では「秘匿されていない関数を適用しつつ、鍵スイッチングを行う手法」として、
定義されています。実際にはその関数としては恒等変換（ $f(x)=x$ ）を用いると、
平文を変えずに鍵が異なる暗号文を得ることができます。

ここまで処理を行うと、元と同じ秘密鍵 $\vec{s}$ で暗号化された TLWE 暗号文に戻っており、
平文は $\pm \frac{1}{4}$ の範囲なら $0$ に、 $\frac{1}{2} \pm \frac{1}{4}$ の範囲なら $\frac{1}{4}$ になっています。
また、誤差の最大値は $c$ に依存せず、システムパラメータによって固定された値になるため、
誤差の最大値が $\pm \frac{1}{16}$ となるようにシステムパラメータを設定します。

これで、何度でも NAND 演算ができるようになり、
加算も乗算も、それどころかすべての演算が可能になるのです。

まとめ

今回は、少し長めになりましたが、TFHE の構成の全体像をまとめました。
次回以降は、各段階で使用した道具について順番に見ていきます。

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

2020-06-22

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

はじめに

みなさんこんにちは。

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

前回は TFHE の暗号システムで用いる道具をいくつかご紹介しました。
TFHE では、３つの暗号アルゴリズムを巧みに組み合わせて構成するので、
今回はその３つをご紹介したいと思います。

基本の暗号文 TLWE

$\mathbb{T}$ 上の要素として、一様分布な乱数を $N$ 個集めたベクトル
$\vec{a}$ を用意します。 $\{0, 1\}$ の二値を $N$ 個集めた秘密鍵 $\vec{s}$ を用意します。平均値が平文 $\mu$ 、
分散が事前に決めた $\alpha$ になるようなガウス分布の乱数を $e$ としたとき、
$( \vec{a}, \vec{s} \cdot \vec{a} + e)$ の組を TLWE 暗号の暗号文の１例とします。

乱数を持ちいて暗号化するため、同一の秘密鍵と平文に対して、
いろいろなバリエーションの暗号文が対応します。

なお、 $\phi_s( (\vec{a},b) )=b-\vec{s} \cdot \vec{a}=e$ は復号する関数として働きます。

元論文では、確率空間全体で定義して議論を進めていますが、
それは誤差成分の分散などを計算したいためであって、
実際の実装ではその分布の中の１サンプルを採集すれば OK です。

さらに、元論文では $\phi_s$ 関数の性質についていろいろ述べられていますが、
特筆しておくべきことは、 $(\vec{0},\mu)$ は自明な暗号文（暗号化されていない）で
あることに留意してください。
なぜなら、 $\phi_s( (\vec{0},\mu) )=\mu-\vec{s} \cdot \vec{0}=\mu$ だからです。

また、TLWE は加法準同型暗号でもあります。
２つの TLWE 暗号文 $(\vec{a},b)$ と $(\vec{a'},b')$ をそのまま足して、
$(\vec{a}+\vec{a'},b+b')$ としたものを $\phi_s$ に入力すると、
$\phi_s( (\vec{a}+\vec{a'},b+b') )=(b+b')-\vec{s} \cdot (\vec{a}+\vec{a'})$
$=(b-\vec{s} \cdot \vec{a})+(b'-\vec{s} \cdot \vec{a'})$
$=\phi_s( (\vec{a},b) )+\phi_s( (\vec{a'},b') )$
となるため、復号すると２つの平文の和が出てきます。
ただし、平文が $\mathbb{T}$ なので、0.6+0.6=1.2 ではなく 0.2 となることに要注意です。
これも重要ですので忘れないようにしていただきたく。

TFHE では、「TLWE 暗号文で加法演算を行って、Gate Bootstrapping を行う。」ということを
繰り返していくことで様々な演算を実現します。

多項式環を用いた TRLWE

環 (ring) で構成したバージョンの TLEW なので、頭文字の R が加わっています。

前回の記事で紹介した $\frac{\mathbb{T}[X]}{(X^n+1)}$ の環の元をランダムに選びます。
実際には、 $n-1$ 次多項式の係数 $n$ 個を $\mathbb{T}$ 上から一様分布な乱数で選出して作ります。
多項式の次数が $n-1$ なら剰余とか考えなくていいので（ $X^n+1$ で割れないので）、
これを多項式 $a(X)$ とします。

秘密鍵をまた $\{0, 1\}$ の二値から $n$ 個集めて、
秘密鍵の多項式 $s(X)=s_{n-1} X^{n-1}+s_{n-2} X^{n-2}+\cdots+s_1 X+s_0$ を組み立てます。

$n$ 個の乱数 $e_i$ を、平均値が平文 $\mu_i$ になり、分散が $\alpha$ となるガウス分布の乱数として、
これらから多項式 $e(X)=e_{n-1} X^{n-1}+e_{n-2} X^{n-2}+\cdots+e_1 X+e_0$ を組み立てます。

多項式 $s(X) \cdot a(X)+e(X)=f(X)(X^n+1)+b(X)$ と分解した $b(X)$ を計算して、
$(a(X), b(X))$ を、TRLWE 暗号の暗号文の１例とします。

こちらも TLWE と同様に乱数を用いて暗号化するため、同一の秘密鍵、平文に対して
無数の暗号文が対応します。

また、TLWE と同様に $\phi_s((a(X),b(X)))=b(X)-s(X) \cdot a(X)+g(X)(X^n+1)$ として、
$\phi_s$ が $\frac{\mathbb{T}[X]}{(X^n+1)}$ の元となるように $g(X)$ を定めたものが、復号関数として働きます。

さらに、加法準同型暗号なのも TLWE と同じです。

これは、Gate Bootstrapping の途中で一時的に使うだけですが、
前回説明した、特殊な多項式が有限巡回群をなす、
という性質を利用するため、とても重要な役割を果たします。

Gadget Decomposition

これは暗号のアルゴリズムではないですが、次で説明する TGSW で必要なので先に説明します。

GSW の論文で ${\rm BitDecomp}$ 関数を解説しましたが、それの円周群 $\mathbb{T}$ バージョンです。
TRLWE 暗号文のサンプルで用いている多項式の係数である、円周群の要素は、
0 以上 1 未満の実数なので、小数部分しかありません。
これを二進数表記で、何ビットかずつに分解する操作を、Gadget Decomposition、
${\rm Dec}$ と定義します。

例えば、小さなサイズで例を書いてみます。
TRLWE 暗号文の多項式の次数を $n=2$ として、分割の 1 単位を ${\rm Bg}=2^2$ で、
$\ell=3$ 要素に分解します。この時、各要素は $-\frac{\rm Bg}{2}$ から $\frac{\rm Bg}{2}$ の間に入るようにします。

TRLWE 暗号文は、2 つの多項式の組み合わせでしたので、
これを多項式を要素とする 2 次元のベクトルとみなします。
$c=\{0.75X^2+0.125X+0.5,0.25X^2+0.5X+0.375\}$ と書けます。

これを分解すると円周群上では 0.75=-0.25 なので
$c=\{-0.25X^2+0.125X+0.5,0.25X^2+0.5X+(0.25+0.125)\}$
$=\{0.25 \times (-X^2+2) + 0.25^2 \times 2X + 0.25^3 \times 0, 0.25 \times (X^2+2X+1) + 0.25^2 \times 2 + 0.25^3 \times 0\}$
と分解できるため、 ${\rm Dec}(c)=\{-X^2+2,2X,0,X^2+2X+1,2,0\}$ となります。

逆に、ベクトルから暗号文に戻す作用素 $H$ も定義します。

今回の例だと、
$H=\left(\begin{array}{cc} 0.25 & 0 \\ 0.25^2 & 0 \\ 0.25^3 & 0 \\ 0 & 0.25 \\ 0 & 0.25^2 \\ 0 & 0.25^3 \end{array}\right)$
という行列が逆変換の作用素です。
${\rm Dec}(c) \cdot H=c$ に戻ることが確認できると思います。

今回はキリのいい値を使ったので厳密に戻りますが、実際には下の方のビットは
四捨五入して丸めます。
つまり、TRLWE 暗号文 $c$ に対して、 $\|c-\vec{v} \cdot H\|$ が最小化となる $\vec{v}$ を得るのが
Gadget Decomposition となります。

この概念を利用して、次の TGSW 暗号を定義します。

GSW の拡張？TRGSW。

$Z_i$ を、平文ベクトルがすべて 0 の TRLWE 暗号文とします。
つまり、 $e(X)$ の係数すべてが平均値 0 となり、分散は $\alpha$ となる多項式でできた
$Z=(a(X),b(X))$ という暗号文です。

これを $2 \ell$ 個、生成して、平文 $\mu$ を以下のように暗号化します。
$C=\left(\begin{array}{c} Z_1 \\ Z_2 \\ \vdots \\ Z_{2 \ell} \end{array}\right)+\mu \times H$
これを、TRGSW 暗号文と定義します。

型が若干あってないような感じがしますが、TLWE 暗号文を多項式を要素とする 2 次元のベクトルと
みなせば、まぁあっていないこともないでしょう。

復号の方法は元論文でも言及されていません。数式的には形式上 ${\rm msg}(C)$ として書き表しますが、
実際に計算することはありません。

これは、Gate Bootstrapping に用いるデータとして、秘密鍵を暗号化しておくために使います。
Bootstrapping Key とも呼びます。なぜ秘密鍵を TGSW で暗号化しておくか、
というのは追々解説します。

まとめ

今回は、TFHE で用いる暗号アルゴリズムを３つ、ご紹介しました。
TFHE では、これらを組み合わせて完全準同型暗号を構成します。
次回はこれらを使って TFHE の構成を見ていきます。

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

2020-06-15

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

はじめに

みなさんこんにちは。

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

前回は TFHE の論文の位置づけについて解説しました。
今回からは、その中身の解説に移りたいと思います。

TFHE はとても難解なので、まずは基本となる道具について見ていきます。

トーラス？いいえ、円周群です。

TFHE の T は論文中でトーラスのことです。
少し数学をかじった方だと「あ、ドーナツのやつだ！」と思うかもしれませんが、
この論文で言うトーラスとは、円周群のことです。

円周群とは何かというと、数直線の 0 から 1 の区間を切り出して、
わっかのように 0 と 1 をつないだものです。

0 から実数の解像度で 1 まで進んで、1 になるとまた 0 に戻るわっかです。

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

ざっくりと、位数が無限大の有限巡回群と考えてしまった方が、
後の解説はしやすくなりますのでそういうことにしてしまいましょう。

元論文では $\mathbb{T}$ と表記されています。

これを何に使うかというと、次回説明する TLWE 暗号の平文の世界にします。
要するに、TLWE 暗号文は、平文として 0～1 の区間の実数を扱います。
そして、TLWE 暗号文同士の加算は、平文である 0～1 の区間の実数同士の加算になる、
つまり加法準同型暗号になるように、TLWE 暗号を設計します。

多項式環

$n$ 次の多項式は一般的に $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0$ と表されます。
これらすべての集合は、多項式同士の和 $f(x)+g(x)$ に対して可換群をなします。
また、多項式同士の積 $f(x)g(x)$ は、可換群に近いですが逆元が存在するとは限りません。
逆元が存在するとは限らない群のことをモノイドと呼びます。
そして、多項式同士の和と積に対しては分配法則が成り立ちます。
$f(x)\{g(x)+g'(x)\}=f(x)g(x)+f(x)g'(x)$
そのため、多項式を要素として、多項式同士の和、積を定義すると、
「環 (ring)」をなします。
これを、「多項式環 (polynomial ring)」と呼びます。

数式で書く時は係数が整数 $\mathbb{Z}$ の場合、 $\mathbb{Z}[X]$ と書きます。
元論文では多項式の係数は円周群なので、 $\mathbb{T}[X]$ です。

しかし、一口に多項式と言ってしまうと、次数が無限に増えていってしまい、
メモリがいくらあっても足りません。そこで次の概念です。

多項式環の剰余環

TFHE では、多項式の剰余環というものを扱います。
元論文では $\frac{\mathbb{T}[X]}{(X^n+1)}$ と書いてあります。

これ自体は説明が難しいので、係数を整数として、つまり $a_i \in \mathbb{Z}$ で、
$n=2$ として説明します。
$X^3+2X^2+3X+3=(X^2+1)(X+2)+(2X+1)=2X+1$
例えば多項式をこのように $\mathbb{Z}[X] (X^n+1) + \mathbb{Z}[X]$ という形に分解して、
剰余の部分だけ取り出します。こうして剰余だけかき集めると、
これもまた環となります。これを剰余環と呼びます。

これで、係数を $\mathbb{T}$ としたものが、元論文で使われているものです。

こちらは、次回説明する TRLWE 暗号の平文となります。
環 (ring) なので、頭文字の R が追加されています。
TFHE のキモとなっている、Gate Bootstrapping の途中で一旦この形式の暗号文が出てきます。
なぜかというと、多項式環の剰余環は、以下のとても便利な性質があるからです。

多項式環の剰余環の性質

$\frac{\mathbb{T}[X]}{(X^n+1)}$ の元（要素）として、任意の $\mu \in \mathbb{T}$ を用いて
$\mu X^{n-1}+\mu X^{n-2}+\cdots+\mu X+\mu$ を取り出します。

これに $X$ を掛けると
$\mu X^n+\mu X^{n-1}+\cdots+\mu X^2+\mu X$
$=\mu(X^n+1)+\mu X^{n-1}+\cdots+\mu X^2+\mu X-\mu$
$=\mu X^{n-1}+\mu X^{n-2}+\cdots+\mu X^2+\mu X-\mu$
という感じで一番下の項の符号が反転します。

もう一度 $X$ を掛けると
$\mu X^n+\mu X^{n-1}+\cdots+\mu X^2-\mu X$
$=\mu(X^n+1)+\mu X^{n-1}+\mu X^{n-2}+\cdots+\mu X^2-\mu X-\mu$
$=\mu X^{n-1}+\mu X^{n-2}+\cdots+\mu X^2-\mu X-\mu$
という風に、もう１つ下の項の符号が反転します。

全部で $n$ 回繰り返すと、
$-\mu X^{n-1}-\mu X^{n-2}-\cdots-\mu X-\mu$
と全部マイナスの項になり、さらに繰り返すともう一度下の項から符号が反転します。
というわけで、全部で $2n$ 回繰り返すと元に戻ります。

つまり、この多項式は、 $\frac{\mathbb{T}[X]}{(X^n+1)}$ という環の中で、
位数 $2n$ の有限巡回群になっているわけです。

TFHE の Gate Bootstrapping ではこの性質をうまく利用します。

まとめ

今回は、TFHE で用いられているトーラスという単語の意味について、
また、多項式環とその剰余環について説明した上で、
ある多項式が $X$ をかけ続けることで有限巡回群を構成することをお話ししました。

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