Quartz 5

A Low-Depth Homomorphic Circuit for Logistic Regression Model Training

Properties1
tagspaper, fhe/circuit, fhe/ckks

5 min read

A Low-Depth Homomorphic Circuit for Logistic Regression Model Training

@article{crockett2020low,
  title={A low-depth homomorphic circuit for logistic regression model training},
  author={Crockett, Eric},
  journal={Cryptology ePrint Archive},
  year={2020},
  url={https://eprint.iacr.org/2020/1483}
}

CKKS回路最適化

Abstract

  • PPML, ロジスティック回帰
  • 先行研究は1iterあたり乗算深さ5
    • 我々は半分にした
  • 反復アルゴリズムと線形代数の汎用的HEアルゴリズム発見した

1. Introduction

  • 委託計算
  • EUではEU外に転送できるデータに制限がある(GDPR)
  • ロジスティック回帰はゲノム, 医療画像, がん診断, 税務コンプライアンス, クレジットスコア等無数のアプリケーションで用いられている

1.1 Contribution

2. CKKS Homomorphic Encryption

  • CKKS scheme かなり簡潔にまとまっていて良いかも
  • ckks: leveled HE + bootstrap
    • 本研究では, leveled HEに焦点を当てる
  • parameterization
    • 回路最適化に焦点を当てているのでスケールのコントロールには焦点を当てない

me too

  • Circuit Design
    • 演算の回路最適化に焦点を当てるので, rescaling, relinearization等の暗号文の調整に関する操作には焦点を当てない

me too

3. Homomorphic Linear Algebra

  • slots

3.1 Basic Encoding

行列()

  • 行列 を でencodeするときは とかく
  • Vector Encoding
    • は各行を にする

3.2 Linear Algebra Operations

  • : shapeが ですべてが1

3.3 Row Vector/Matrix Products

  • sum_rows(<[a b c d]>) = <[a + c b + d a + c b + d]> = <a + c b + d>

  • Algorithm sum_rows

R = <A>
for i in 0..log2(m)
  R = R + (R << n * 2^i)
end
return R

3.4 Column Vector/Matrix Products

  • Algorithm sum_cols
R = <A>
for i in 0..log2(n)
  R = R + (R << 2^i)
end
D: m*n = [d_i,j = 1 if j == 0 else 0]
R = R * <D>
for i in 0..log2(n)
  R = R + (R << 2^i)
end
return R
    • sum_cols(<a> * <x>) = <(Ax)^T>
  • sum_cols(A) + sum_cols(B) = sum_cols(A + B)

3.6 Matrix/Matrix Products

  • Algorithm3 matprod
def matmul(<A^T>: m*n = A: f*g, <B>: m*n = B: g*h): m*n
  for k in 0..f:
    # mask k-th col of <A^T>
    D: m*n = [d_ij = 1 if j % n == k else 0]
    # extract k-th col
    A_k = [A_{k,i} = <D> * <A^T>_{i, floor(k/n)} for i in 0..ceil(g/m)]
    # shift to first col
    A_k = A_k << (k % n)
    # replacate across all cols of the unit
    for j in 0..log2(n):
      A_k = (A_k >> 2^j) + A_k
    end
    # k-th row of A * B
    R_k = sum_rows(A_k * B)
    # scaled mask for k-th row
    E: m*n = [e_{i,j} = c if i % m == k else 0]
    # isolate k-th row
    S_k = [S_k,j = R_k,j * E for j in 0..ceil(h/n)]
  end
  # sum m rows to fill rows
  return [T_i = sum(S_k for k in i*m..min(f-1,i*m+m-1)) for i in 0..ceil(f/m)]

4. Training A Logistic Regression Model

  • Algorithm4: minibatch training algorithm 
def training_lr(z_i: f*g for i in 0..k, \alpha): v_k in R^g
  \epsilon_0 = 1
  w_0 = v_0 = 0->: R^g
  \gamma = \alpha / f
  for i in 0..k:
    \epsilon_{i+1} = (1 + sqrt(4 \epsilon_i^2 + 1)) / 2
    \eta_i = (1 - \epsilon_i) / (\epsilon_{i+1})
    # ---
    \ell_i = Z_i * v_i
    b_i = \sigma(-\ell_i)
    \Delta_i = Z_i^T * b_i
    w_{i+1} = v_i + \gamma * \Delta_i
    v_{i+1} = (1 - \eta_i) w_{i+1} + \eta_i * w_i
    # ---
  end
  return v_k

5. Homomorphic Logistic Regression Training: Depth4

  • Algorithm4のL7-11を準同型暗号上で実装する
    • naiveにやるとdepth-5
  • Algorithm5: Mini-batch training iter
def mini_batch_iter(Z_i: f*g, w_i: g, v_i: g, \gamma, \eta_i): w_{i+1}, v_{i+1}: g
    \ell_i = Z_i * v_i
    c_i = \gamma * Z_i^T * \sigma'(-\ell_i)
    w_{i+1} = v_i + \gamma * \Delta_i
    v_{i+1} = (1 - \eta_i) w_{i+1} + \eta_i * w_i

Graph View

Backlinks