エクセルで理解するTFHE暗号（part2/2 実践編-エクセルハンズオン-)

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

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