本記事の著者は秘密計算のベンチャー企業で働いております.
一方, 今年から暗号に触れた素人でもあり, 勉強の一環として本記事を書いています.
誤字・脱字から暗号理論の技術的詳細まで, 記事に誤りがありましたら,
ご指摘いただけますと幸いです.

本記事は, 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!