TFHE実装入門

0.Introduction

松岡　航太郎

自己紹介

• 京都大学工学部電気電子工学科4回生 特色入試
• 東京都立戸山高等学校卒
• 2019年度未踏スーパークリエータ
• 京都大学機械研究会(2019年度NHK学生ロボコン優勝)
• 趣味は読書
• 卒業研究は超伝導体と磁性体を含む動電磁界シミュレーション

目標

• TFHEのHomNANDを実装し、背景となる理論を説明できるようになること
• 目に見える目標はHomNANDのテストが動く実装の製作
• そこまでできた場合は個別の発展課題をする予定

TFHEとは？

• Torus Fully Homomorphic Encryptionの略
• 0と1を表現する暗号文に対し、好きなだけ論理演算ができる

Fully Homomorphic Encryptionとは？

• FHEとよく略す。日本語で言えば完全準同型暗号。
• 暗号文を入力として、暗号文のママ任意の関数を適用できるような暗号
• 整数の暗号文であれば加算と乗算ができることが十分条件
• bitの暗号文であればNANDができることが十分条件
• TFHEは後者で論理回路として表現できる関数なら評価可能

FullyじゃないHomomorphic Encryption

• 多くのHEは剰余環上の整数に対する演算をサポートしている
• PHE(Partial): 加法だけもしくは乗法だけできるHE
• SHE(Somewhat): 両方できるが、乗法の回数に暗号方式に依存した定数の制限があるもの
• LHE(Leveled): 両方できるが、パラメータ依存で乗法の回数に制限があるもの

FHEの世代

• wikipediaが詳しい
• PreFHE: Paillier Cryptosystemなど
• 第1世代FHE: Gentryさんの博士論文(2009)など
• 第2世代FHE: Brakerski-Gentry-Vaikuntanathan (BGV, 2011)など
• 第3世代FHE: Craig Gentry, Amit Sahai, and Brent Waters (GSW,2013)やTFHE(2016)など

NAND

論理回路の例(半加算器)

HomNANDの概念的な構造

章立て

0. Introduction
1. TLWE
2. TRLWE & SampleExtractIndex
3. TRGSW & CMUX
4. Blind Rotate
5. Identity Key Switch
6. HomNAND
7. FFTによる多項式乗算
8. Parameter Selection
9. Chisel&Yosys

• Appendixは記号の定義とかをまとめてある

講義の流れ

• スライドはできる限り事前に配布する。手元で見れるようにすると良い
• 講義のスピードに合わせる必要はない。自分で勝手に進めてわからない部分を質問するとかしてもらっても構わない。
• 原著論文と原著者実装をみるだけでも実装することは可能。講義はつまづきやすい場所を潰すためのもの
• 論文と実装の間でも理論に差異があり、講義では実装側によせた内容をやる
• 実装に寄せているため一部一般性を損なっていることがある
• 各章では該当する部分の理論を説明してから、具体的な実装の仕方を説明する

実装について

• 講師とチュータ２人が見れる形にすること
• 言語はC,C++,Pythonだとサポートしやすい
• 講師もチュータもLinuxで開発している
• 目に見える目標はHomNANDのテストが動く実装の製作

発展的な内容

• CPUをTFHE上で動かす
• HLSとの連携
• FPGA,OpenCL,CUDAでの実装
• Deep Learningへの応用
• Multi Keyの実装
• 他のFHEとのスイッチング
• Determinstic Weighted Finite Automaton
• Circuit Bootstrapping
• Universal Circuit over TFHE
• Garbled Circuit over TFHE

用語の揺れについて

• 細かいが混乱する恐れがある注意点として、論文と講義で用語が違う場合がある

参考文献

• Python実装(講師作)
• C++実装(講師作)
• CUDA実装(講師編)
• C++実装(チュータ作、おそらくいちばんスライドに忠実)
• C++実装(原論文著者作)
• Julia実装(NuCypher製)
• Ruby実装(Klemsaさん製)
• Rust実装(Zama製)
• 原論文