本記事の著者は秘密計算のベンチャー企業で働いております.
一方, 今年から暗号に触れた素人でもあり, 勉強の一環として本記事を書いています.
誤字・脱字から暗号理論の技術的詳細まで, 記事に誤りがありましたら,
ご指摘いただけますと幸いです.
本記事は, 2回連載(第1回:理論編, 第2回:実践編-ハンズオン-)の第2回.
連載の目的は, エクセルを利用した, TFHEの要点解説です.
TFHEとは, 暗号方式の一種です(トーラスを用いた完全準同型暗号).
TFHEを理解するうえで, 次の問Aは有益でした:
問A：
「平文をm, その暗号文をEnc(m), で表すとします.
TFHEでは, どのような方法で,
Enc(m)から暗号状態で(=復号せずに)Enc(m^2)を計算するのか？」
問Aはシンプルですが, その回答は複雑です.
そこで本連載では, 問Aの回答を理解するために, より簡単な問Bを考えます：
問B：
「TFHEでは, どのような方法で, 平文mから平文m^2を計算するのか？」
勿論, 平文の場合, 例えばm=0.3の時, m^2=0.09と直接計算できます.
しかし, 直接計算という手法は,暗号状態でのEnc(m)からEnc(m^2)の計算へ応用できません. なぜなら, Enc(m)を復号しないと, mの値は分からないからです.
本連載第1回：理論編では, 暗号状態でのEnc(m)からEnc(m^2)の計算へ応用可能な,
平文mから平文m^2の計算手法を, 数式を用いて解説しました.
Programmable Bootstrapping (PBS)という手法を用いて, 平文m^2を計算しました.
本連載第2回：実践編では,
エクセルを用いて, PBSを用いた平文mから平文m^2の計算を,
ハンズオン解説します.
本連載により, TFHEの理解向上の一助になりましたら幸いです.
本連載エクセルハンズオンの続編にあたる
「エクセルを利用した, 暗号状態でのEnc(m)からEnc(m^2)の計算」は,
弊社第2回暗号勉強会にて体験していただける「予定！」です.
https://connpass.com/event/341101/
よろしかったらご参加ください.
繰り返しで恐縮ですが, 本記事の著者はTFHE暗号の専門家ではありませんので,
厳密に理解されたい方は, 原著論文や解説論文をご一読ください.
それでは本記事の内容に入ります(本連載第1回の内容は仮定します).
お手数をおかけしますが, お手元にエクセルシートを準備していただき,
ハンズオン形式でご一読いただけますと幸いです.
以下はハンズオン想定の(=エクセル入力しない場合, 読みにくい)文章となりますが,
ご容赦ください.
“PBSを用いた平文mから平文m^2の計算(トイモデル)のエクセル実装”
目的:
以下の2つの計算方法(1),(2)に着目します:
(1)直接計算を用いた2乗の計算(すぐに計算できるが, 暗号文計算へ応用できない);
(2)PBSを用いた2乗の計算(計算は面倒だが, 暗号文計算へ応用できる).
エクセル実装の目的は, 入力mに対して,
「(1)の計算結果」＝「(2)の計算結果」(= m^2) を確認することです.
(1)は, 通常の2乗の計算のことです.
以下のエクセル実装の大部分は, (2)に関する実装です.
Step.0.シート配置の準備.
- A1セルに 平文 と入力,
- B1セルに 指数 と入力,
- C1セルに 平文^2 と入力,
- D1セルに PBS と入力します.
以上の入力より, 以下が得られます:
| A | B | C | D | |
|---|---|---|---|---|
| 1 | 平文 | 指数 | 平文^2 | PBS |
| 2 |
Step.2.以降で, 実際に,
A2セル, B2セル, C2セル, D2セル に値を入力します.
特に,
- C2セルには 直接計算による2乗の計算結果,
- D2セルには PBSによる2乗の計算結果,
が出力される予定です. ハンズオンの目的は, C2=D2を確認することです.
Step.1.Look up tables の入力.
- A8セルに LUT と入力,
- A9セルに m と入力,
- B9セルに m^2 と入力,
- C9セルに Rotate と入力します.
以上の入力より, 以下が得られます:
| A | B | C | |
|---|---|---|---|
| 8 | LUT | ||
| 9 | m | m^2 | Rotate |
| 10 |
さらに,
- A10セルに 0.00 と入力し,
- A11セルに 0.01 と入力します.
A10とA11を選択し,「フィルハンドル」でA109までドラッグすると,
A列は, 0.00,0.01,0.02, … , 0.99 と増加します. - B10セルに =A10^2 と入力します.
B10をコピーして, B11～B109 に貼り付けます.
Step.1.の入力より, 以下が得られます.
| A | B | C | |
|---|---|---|---|
| 8 | LUT | ||
| 9 | m | m^2 | Rotate |
| 10 | 0.00 | 0.0000 | |
| 11 | 0.01 | 0.0001 | |
| 12 | 0.02 | 0.0004 | |
| 13 | 0.03 | 0.0009 | |
| … | … | … | … |
| 109 | 0.99 | 0.9801 |
Step.1.より, Look up tablesの入力が終了しました.
これにて, PBSの準備の入力が終了です.
Step.2.平文mの入力.
平文mを, 0.00から0.99までの100個の値の中から, 1つ選びます.
ここでは m=0.31 とします.
- まず, A2セルに mの値(0.31) を入力します.
Step.3.「直接計算により求めたm^2」の入力.
- 次に, C2セルに =A2^2 と入力します.
これにより, - C2セルには 直接計算により求めたm^2 が出力されます.
例えば, A2セルに 0.31 と入力した時, C2セルの出力は 0.0961 です.
以降の手続きにより,
- D2セルには PBSにより求めたm^2 が出力される予定です.
繰り返しで恐縮ですが, ハンズオンの目的は, C2=D2を確認することです.
Step.4.指数iの入力.
- B2セルに =FLOOR(A2*100,1) と入力します.
B2セルには 「入力m(A2の値)に対応した指数」 が出力されます.
例えば, m=0.31の時, B2セルの出力は 31 です.
B2セルのコード解説をしますが, 読み飛ばしていただいて大丈夫です.
・FLOOR(--,1) は --の小数点以下を切り捨てた整数部分 を返します.
・よって, FLOOR(A2*100,1)は,
A2の100倍の小数点以下を切り捨てた整数部分 を返します.
・本連載第1回(あるいは上の表)より,
A2の100倍の小数点以下を切り捨てた整数部分 = A2に対応した指数
です. ゆえに, B2セルには 「入力m(A2の値)に対応した指数」 が出力されます.
以上でコード解説は終了です.
Step.5.Rotateの入力.
- まず, C10セルに
=MOD(INDEX($B$10:$B$109, MOD($B$2+(ROW()-ROW($C$10)),100)+1),1)
と入力します.
これにより, C10セルには
B列の「(B2セルの値)+10」行目のセルの値
が出力されます.
例えば, B2=31の場合, C10セルには B41(=31+10)セルの値 が出力されます.
C10セルのコード解説をしますが, 読み飛ばしていただいて大丈夫です.
・$B$10は 絶対参照されたB10セル を表します(記法が微妙ですみません).
・ROW(--)は 数式が入力されているセルの行番号 を返します.
・例えば, ROW($C$10)は 10 を返します.
・B2+(ROW(--)-ROW($C$10))は
「(B2セルの値) + (現在の行(--)の行番号) - 10」を返します.
・MOD(--, 100)は -- を100で割った余り を返します.
・INDEX($B$10:$B$109, -- + 1)は
-- に1を加えた行番号を使って, 範囲(B列10行-109行)から対応する値 を返します.
・↑のINDEX関数では,
$B$10を1番目, $B$11を2番目, ..., $B$109を100番目 とカウントします.
・例えば, INDEX($B$10:$B$109, 32)は B41 を返します.
・以上を組み合わせると,
MOD(INDEX($B$10:$B$109, MOD($B$2+(ROW(--)-ROW($C$10)),100)+1),1) は
B列の「(B2セルの値) + (現在の行(--)の行番号)」行目のセルの値 を返します.
以上でコード解説は終了です.
- 次に, C10セルをコピーし, C11～C109に貼り付けます.「フィルコピー」により
- C11セルには
B列の「(B2セルの値)+11」行目のセルの値
が出力されます. - C12セルには
B列の「(B2セルの値)+12」行目のセルの値
が出力されます.
以下同様です. これらの入力により, - C列は 「B列の各値の位置を指数iだけ上にずらして得られた列」 となります
(Rotateされた列).
Step.5.までの入力により, 以下が得られます:
| A | B | C | |
|---|---|---|---|
| 9 | m | m^2 | Rotate |
| 10 | 0.00 | 0.0000 | 0.0961 |
| 11 | 0.01 | 0.0001 | 0.1021 |
| 12 | 0.02 | 0.0004 | … |
| 13 | 0.03 | 0.0009 | |
| … | … | … | … |
| 40 | 0.30 | 0.0900 | |
| 41 | 0.31 | 0.0961 | |
| 42 | 0.32 | 0.1021 | … |
| … | … | … | … |
| 109 | 0.99 | 0.9801 | 0.0900 |
Step.6.「PBSにより求めたm^2」の入力.
- D2セルに =C10 と入力します.
本連載第1回により, - D2セルには PBSにより求めたm^2 が出力されます.
例えば, m=0.31の時, D2セルの出力は 0.0961 です.
C2セルには 直接計算により求めたm^2(0.0961) が入力されていましたので,
無事に, C2=D2＝0.0961 を確認できました.
mが他の値でも同様に, C2=D2=m^2 を確認できます.
以上がエクセルハンズオンによる「PBSを用いた平文mから平文m^2の計算」の要点解説でした. これにて, 本連載第2回：実践編 が終了です.
余裕がある方は, 本連載の平文計算の「Enc(m)からEnc(m^2)の計算」への応用を, 考えてみてください(暗号文計算における指数の定義と役割を考えてみてください).
読者の方は, 2回にわたり, 貴重なお時間をありがとうございました.
平文での計算で物足りない方は, 弊社第2回暗号勉強会にご参加ください.
Happy Christmas & new year!