線形変換によるHE行列積

algorithm
2022-10-29

Secure Outsourced Matrix Computation and Application to Neural Networks の方法

3.2 Matrix Encoding

• $n=d^2$
• 長さ $n$ のベクトル $a$ に対して写像 $\iota :a\to A=(a_{d\cdot i+j})$
  • 逆変換もできるよ
• 線型変換 $L:R^n\to R^n$

3.3.1 Tweaks of Permutations

• $\sigma (A{)}_{i,j}=A_{i,i+j}$
• $\tau (A{)}_{i,j}=A_{i+j,j}$
• $\varphi (A{)}_{i,j}=A_{i,j+1}$
• $\psi (A{)}_{i,j}=A_{i+1,j}$
  (すべて $(\mathrm{mod}d)$)
  を用いて

$$\begin{array}{rl}A\cdot B& =\sum _{k=0}^{d-1}(\sigma \circ {\varphi }^k(A))\odot (\tau \circ {\psi }^k(B))\\ (A\cdot B{)}_{i,j}& =\sum _k^{d-1}\sigma (a_{i,j+k})\cdot \tau (b_{i+k,j})\\ & =\sum _k^{d-1}{a}_{i,i+j+k}\cdot b_{i+j+k,j}\\ & =\sum _k^{d-1}{a}_{i,k}\cdot b_{k,j}\end{array}$$

写像に対応する定数行列

• 写像 $\sigma ,\tau ,\varphi ,\psi$ に対応する定数行列が

• $U_{d\cdot i+j,\ell }^{\sigma }:=\ell =d\cdot i+[i+j{]}_d?1:0$

• $U_{d\cdot i+j,\ell }^{\tau }:=\ell =d\cdot [i+j{]}_d+j?1:0$

• $V_{d\cdot i+j,\ell }^k:=\ell =d\cdot i+[j+k{]}_d?1:0$

• $W_{d\cdot i+j,\ell }^k:=\ell =d\cdot [i+k{]}_d+j?1:0$

を用いて 線形変換 $U\cdot a$ をする

3.3.2 Homomorphic Matrix Multiplication

アルゴリズム:行列積

function matmul1(a::Vector{Float64}, b::Vector{Float64}, d::Int64)::Vector{Float64}
  Uσ, Uτ = gen_U(d)
  as, bs = [lin_trans(a, Uσ)], [lin_trans(b, Uτ)]
 
  for k in 1:d - 1
    V_k, W_k = gen_VW(d, k)
    push!(as, lin_trans(as[1], V_k))
    push!(bs, lin_trans(bs[1], W_k))
  end
 
  ab = mul(as[1], bs[1])
  for k in 2:d
    ab = add(ab, mul(as[k], bs[k]))
  end
  ab
end

n=2

; 0 1  4 5    6  7
; 2 3  6 7 = 26 31
;  [0, 7, 18, 10] + [6, 0, 8, 21]
;= [6, 7, 26, 31]
; lin_trans: d^2, mult: d, add: d-1
(def cipher lintrans (args cipher m vector u)
    (rep + l $SLOTS
        (* (L m l) (ecd (diag u l)))
    )
(let a (enc (ecd (vec 0 1 2 3)))
(let b (enc (ecd (vec 4 5 6 7)))
; [0 1 2 3] [0 1 3 2] -> [0 1 3 2]
(let as0 (app lintrans a (vec 0 1 3 2))
; [4 5 6 7] [0 3 2 1] -> [4 7 6 5]
(let bs0 (app lintrans b (vec 0 3 2 1))
; [0 1 3 2] [1 0 3 2] -> [1 0 2 3]
(let as1 (app lintrans as0 (vec 1 0 3 2))
; [4 7 6 5] [2 3 0 1] -> [6 5 4 7]
(let bs1 (app lintrans bs0 (vec 2 3 0 1))
; [0 7 18 10] + [6 0 8 21] = [6 7 26 31]
(+ (* as0 bs0) (* as1 bs1))
))))))))

; 0 1  4 5    6  7
; 2 3  6 7 = 26 31
 
; Uσ =
; 1 0 0 0
; 0 1 0 0
; 0 0 0 1
; 0 0 1 0
(let as0 (lintrans (0 1 3 2) a)) ; [0 1 3 2]
 
; Uτ =
; 1 0 0 0
; 0 0 0 1
; 0 0 1 0
; 0 1 0 0
(let bs0 (lintrans (0 3 2 1) b)) ; [4 7 6 5]
 
; V_k =
; 0 1 0 0
; 1 0 0 0
; 0 0 0 1
; 0 0 1 0
(let as1 (lintrans (1 0 3 2) as0)) ; [1 0 2 3]
 
; W_k =
; 0 0 1 0
; 0 0 0 1
; 1 0 0 0
; 0 1 0 0
(let bs1 (lintrans (2 3 0 1) bs0)) ; [6 5 4 7]
 
(+ (* as0 bs0) (* as1 bs1))
;  [0, 7, 18, 10] + [6, 0, 8, 21]
;= [6, 7, 26, 31]
; lin_trans: d^2, mult: d, add: d-1