Secure Outsourced Matrix Computation and Application to Neural Networks

paper algorithm

CKKS scheme of Microsoft SEAL で行列積

@inproceedings{jiang2018secure,
  title={Secure outsourced matrix computation and application to neural networks},
  author={Jiang, Xiaoqian and Kim, Miran and Lauter, Kristin and Song, Yongsoo},
  booktitle={Proceedings of the 2018 ACM SIGSAC conference on computer and communications security},
  pages={1209--1222},
  year={2018},
  url={https://eprint.iacr.org/2018/1041.pdf}
}

2.2 Ciphertext Packing Technique

• SIMDで計算したい
  • Fully Homomorphic SIMD Operations によると polynomial-CRT と呼ばれている
• 平文空間 $M$ を $n$ $次元ベクトル$R^n$ に適切にエンコーディング/デコーディングすることにより表現, 並列化可能
  • しかし、回路は，異なる平文スロットにいくつかの入力を持つ
• この問題を克服するために、いくつかの暗号化を介してスロット内のデータを移動させる方法がある
  • ex. CKKS scheme, BGV scheme は Ring-LWE を仮定した場合, ガロア群 の構造を利用して平文スロットに対する回転演算を行う
• Rot(ct) により、m = (m_0, ... , m_n-1) ∈ M = Rn の暗号化 ct を暗号化に変換します。
  • ρ(m;\ell) := (m, ... , m_n-1, m0, ... , m1) の値です。は正でも負でもよいことに注意してください。
• Rot(-l) = Rot(n - l)

2.3 Linear Transfomations

• LinTrans

3.Secure Matrix Multiplication via HE

• 線形変換によるHE行列積
  • $5d$ addition
  • $5d$ const mult
  • $6d$ rot

3.3.3 Further Improvements

6.3.2 パラメータ

実装では 5 log p + 2 log p_c(定数のlog) + log q0 になる

, inputの log p は 30bits, log p_c 30bits

log q_0 = log p_s = log p + 10

log q ~~ 250, N = 2^13 で \lambda = 80 bits security