LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@0917laplaceinEAGLYS

準同型暗号 CKKS 方式の理論と実装 基本編（0. イントロダクション）

Posted at

突貫で書いてしまった部分もあるので、大いに誤りを含む可能性があります。誤字・脱字レベルでも構いませんので、ご指摘ください。
また、予告なしに内容の加筆や構成の変更を行うことがありますが、読みやすくするためのものですので、ご容赦ください

自己紹介

秘密計算のスタートアップで働いている社会人３年目です
普段は、秘密計算の研究や社会実装を行なっています

最近は、外部に向けた勉強会もやっています
第1回 EAGLYS暗号勉強会
第2回 EAGLYS暗号勉強会
第3回 EAGLYS暗号勉強会
第4回 EAGLYS暗号勉強会

学生時代は、耐量子計算機暗号（特に符号ベース暗号）を研究していました
今でも細々と続けています

Qiita だけでなく、X や Zenn でも活動しています、もしよろしければ
X のアカウント
Zenn のアカウント

はじめに

本記事から、CKKS 方式の理論や実装についても、全6回に分けて、基本的なことをまとめようと思います
＊過去にも、やろうとして挫折したのですが、今回は完走します

基本編の目標は次の2つを理解することです:

  1. 準同型暗号 CKKS 方式での暗号文の足し算と掛け算ってどうやってやるの？
  2. 準同型暗号 CKKS 方式では、暗号文の非線型演算はどこまでできるの？

いつも通り、必要な数学は適宜補足しますので、特別な予備知識は不要かなと思います
強いて言うなら、複素数を全く知らないと厳しいぐらいです
＊とは書いてありますが、整数環とか多項式を全く聞いたことない、とかだと、かなり厳しい予感はします。この辺の前準備はいずれどこかのタイミングで記事を書く予定です。
＊あと、暗号とは何か・準同型暗号とは何か、からは解説しません（この記事への導入となる別記事は追々書いていく予定です）

主に参考にするのは CKKS の原論文 と CKKS の Bootstrap の原論文 です
Reference は下記です:

  1. J. H. Cheon, A. Kim, M. Kim, Y. Song: ``Homomorphic encryption for arithmetic of approximate numbers’’, In: Advances in Cryptology–ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I 23. Springer International Publishing, pp.409-437, 2017.

  2. J. H. Cheon, K. Han, A. Kim, M. Kim, Y. Song: ``Bootstrapping for approximate homomorphic encryption’’, In: Advances in Cryptology–EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29-May 3, 2018 Proceedings, Part I 37. Springer International Publishing, pp.360-384, 2018.

記事の構成

各記事はいくつかのセクションで構成され、さらに各セクションは、基本的に次のようなサブセクションに分かれています

  • 概要
  • 前提
  • 理論的枠組み
  • 具体例
  • アルゴリズム
  • 実装
  • 理論詳細

サブセクション

概要

そのセクションの目的と全体像を簡潔に紹介します

前提

「理論的枠組み」の理解に必要な知識や定義を整理します

理論的枠組み

そのセクションのアルゴリズムの基盤理論を、各ステップごとに平易に解説します

具体例

「理論的枠組み」で展開した説明に対して、具体的な数値例を計算します

アルゴリズム

「理論的枠組み」でのアルゴリズムの疑似コードの紹介およびその漸近計算量を議論します

実装

Python スクリプトを用いて、「アルゴリズム」の疑似コードを実装し、「具体例」で与えた数値が正しいことを確認します

理論詳細

「アルゴリズム」において、なぜそのような操作が必要か、どのような背景があるのか、など、理論的に突っ込んだ部分を解説します

各セクションの読み方

全ての方に全てを読んでいただくことは想定していません、おおまかに以下の4つのレベル帯になるかなと思っています

  1. CKKS で何ができるかを掴みたい、難しいことは要らない（非エンジニア方向け）
    →各セクションの「概要」サブセクションのみ読みましょう
    →最終回の記事で、結局何がどこまでできるか、を説明するので、それまでの辛抱です
  2. 各セクションのコードを動かしたい（エンジニア向け）
    →「概要」・「実装」サブセクションのみ読みましょう
    →OSS のコードもなんとなく動かせるようになると思います
  3. 各セクションのコードを理解し、自分でも実装できるようになりたい（実装方面の研究者向け）
    →「概要」から「実装」サブセクションまで全て読みましょう
    →いわゆる「ゼロから作る」ができるようになると思いますし、OSS のコードをどのようにいじれば良いかも分かるようになると思います
  4. 各セクションを深いところまで理解したい（理論方面の研究者向け）
    →全て読みましょう
    →とは言いつつも、理論背景には「個人的な解釈」を含む場合があるので、あくまで参考程度に

各セクションのアウトプット

各セクションのアウトプットとしては、

  • 「実装」で用いた Python プログラム記載の Notebook
  • 「アルゴリズム」までの内容を整理した slide

になります（実際には、各記事のアウトプットです）

上記の参考 Python スクリプトは、オブジェクトベースではなく、ロジックベースで実装します
また、遅いと分かっていながらも、ロジックに忠実に実装します
＊この辺の注釈は入れる予定です

最終回で、それまでの内容の「前提」・「理論的枠組み」・「理論詳細」をまとめた document も公開します（「数学の準備」では、Qiita に直接数式を書くのではなく、画像を貼り付けることがあるのですが、その元となった資料です）
理論詳細が長すぎる、と判断した場合、こちらの解説記事では割愛することがありますが、こちらの document では全て紹介します

全6回通しでの目次

＊CKKS: CKKS の原論文
＊Boostrap: CKKS の Bootstrap の原論文

第１回：Coeff 方式 encode/decode

  • CKKS とは？
  • 数学の準備
    • 整数環
    • 多項式環
    • 円分多項式
  • Coeff 方式 Encode/Decode
    • 概要
    • 前提
    • 理論的枠組み
      • エンコード
      • デコード
    • 具体例
      • エンコード
      • デコード
    • アルゴリズム
      • エンコード
      • デコード
    • 実装
      • エンコード
      • デコード
      • 具体例チェック
    • 理論詳細
      • なぜ cleartext の定義域が複素数なのか
      • スケーリング係数の役割

第２回：Coeff 方式暗号文の構成とその足し算

  • LWE問題
    • 前提
      • 乱数
    • 理論的枠組み
    • 具体例
    • 理論詳細
      • ノイズの値が0の場合
  • Coeff 方式暗号文の構成
    • 概要
    • 前提
      • Ring-LWE 問題
    • 理論的枠組み
    • 具体例
    • アルゴリズム
    • 実装
    • 理論詳細
      • LWE 問題と Ring-LWE 問題の関連性
      • CKKS におけるレベルの概念
      • CKKS 暗号文の bit security
  • Coeff 方式暗号文の足し算
    • 概要
    • 理論的枠組み
      • 足し算
      • 引き算
      • スカラー倍
    • 具体例
      • 足し算
      • 引き算
      • スカラー倍
    • アルゴリズム
      • 足し算
      • 引き算
      • スカラー倍
    • 実装
    • 理論詳細

第３回：Coeff 方式暗号文の掛け算

  • Coeff 方式暗号文の掛け算
    • 概要
    • 前提
    • 理論的枠組み
    • 具体例
    • アルゴリズム
      • 再線型化鍵の生成
      • 掛け算アルゴリズム
      • 再線型化を含めた掛け算アルゴリズム
    • 実装
    • 理論詳細
      • なぜこのような操作が必要なのか
        • 掛け算アルゴリズムの発想
        • 再線型化の発想、再線型化鍵の必要性

第４回：Slot 方式 encode/decode

  • 数学の準備
    • 共役複素数
    • 円分多項式の根
    • Vandermonde 行列
  • Slot 方式 Encode/Decode
    • 概要
    • 前提
    • 理論的枠組み
      • エンコード
      • デコード
    • 具体例
      • エンコード
      • デコード
    • アルゴリズム
      • エンコード
      • デコード
    • 実装
      • エンコード
      • デコード
    • 理論詳細
      • 前提
        • Fourier 変換
        • 多項式補間
        • FFT
          • 原始根
      • Slot の概念
      • なぜこのような操作が必要なのか
        • Coeff 方式の暗号文同士の掛け算アルゴリズムの復習
        • Fourier 変換を用いる発想
        • 多項式補間を用いる発想
      • FFT を用いるために
        • 原始根を用いた Vandermonde 行列
  • Slot 方式暗号文の構成
    • 実装
  • Slot 方式暗号文の足し算
    • 実装
  • Slot 方式暗号文の掛け算
    • 実装

第５回：Standard Bootstrap

  • 数学の準備
    • Euler の公式
    • sin 関数の近似
  • Slot 方式暗号文の複素共役
    • 概要
    • 前提
    • 理論的枠組み
      • KeySwitch
    • 具体例
    • アルゴリズム
    • 実装
    • 理論詳細
  • Standard Bootstrap
    • 概要
    • 前提
    • 理論的枠組み
      • CoeffToSlot
      • EvalExp
      • ExtImg
      • SlotToCoeff
    • 具体例
      • CoeffToSlot
      • EvalExp
      • ExtImg
      • SlotToCoeff
    • アルゴリズム
      • CoeffToSlot
      • EvalExp
      • ExtImg
      • SlotToCoeff
    • 実装
    • 理論詳細

第６回：まとめ

CKKS 方式の概要

ここでは、CKKS 方式の概要について説明します
よく、CKKS では、近似された値がうんたら、みたいな話をされることがあります

ちなみにですが、CKKS とは、著者らの頭文字です
一方、TFHE は、FHE over the Torus の略称で、頭文字は CGGI です
たまに（たまに、と言ったら、一部の方から怒られそうですが・・・）「HEAAN」と呼ばれることがありますが、これは、

Homomorphic Encryption for Arithmetic of Approximate Numbers

の略称です。これは、CKKS 原論文のタイトルそのまんまですね。

Approximate Numbers が何を表すのか、どのタイミングで近似が入るのかは、記事を追っていくと分かるかと思います

TFHE との違い

誤解を恐れないのであれば、（と言っても、誤解されそうなので、必ず後の補足を参照ください）

  1. 暗号方式の構造（特に encode）の違い: cleartext（後述）として、「数」を考えるのが TFHE、「多項式」を考えるのが CKKS
  2. 暗号方式のアルゴリズムの違い: Bootstrap（特に PBS）を経由して掛け算を行うのが TFHE、経由しないでも掛け算できるのが CKKS
  3. Bootstrap の違い: cleartext 上の任意の関数を暗号文へ適用できるのが TFHE、少なくとも連続関数でないと適用できないのが CKKS

あたりになるでしょうか。

補足
1: あくまで TFHE の比較対象は TLWE 暗号文、なぜならこれをメインに扱うので
2: PBS とは Programmable Bootstrap の略、Functional Bootstrap と呼ぶ派閥もある
3: 例えば、厳密な意味での ReLu 関数は CKKS 暗号文へ適用できません。とは言っても、今回の CKKS で扱う Bootstrap （原論文のアルゴリズム, Standard Bootstrap）ではなく、Look-up table によるもの（Functional Bootstrap）であれば、可能です

準同型暗号で用いられる3つの Text

encode_encrypt.png

準同型暗号に限らず、多くの暗号方式では、以下の3つの text を考えます:

  • cleartext: いわゆる生データであり「平文」のこと、message と呼ばれることが多い
  • plaintext: 暗号化アルゴリズムの入力（引数）のこと
  • ciphertext: 暗号文（暗号化アルゴリズムの出力）のこと

本連載では、cleartext なのか plaintext なのか紛らわしいので、「平文」という表記はしません。

上3つの text を結ぶアルゴリズムとして、

  • Encode(cleartext) → plaintext
  • Decode(plaintext) → cleartext
  • Encrypt(plaintext) → ciphertext
  • Decrypt(ciphertext) → plaintext

があります。これらのアルゴリズムの要請としては、

  • Decode(Encode(cleartext)) $\approx$ cleartext
  • Decrypt(Encrypt(plaintext)) $\approx$ plaintext

が挙げられます
＊$\approx$ の意味は、概ね一致している（どの程度一致しているのかは後に考察します）

なぜ、わざわざ、encode と encrypt で分けるのか、これには諸説あるような気がしますが、個人的な解釈として、
準同型暗号方式に対して、encrypt アルゴリズムは1つしかないものが多いのですが、encode アルゴリズムは複数パターン考えられる場合が多いです（今回の CKKS もそう）
そのような事情があって、特に、encode/encrypt で分けて考える場合が多いのかなと思います

まとめ

TFHE でも解説記事のリメイクを書いているところですが、CKKS ではこれが初版なので、また何度かリメイクするんだろうなと思いながら、気楽に書いていきたいですね

今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?