線形変換

algorithm

定数行列 $U:{\mathbb{R}}^{N\times N}$ と 暗号文 $c:{\mathbb{R}}^{N\times 1}$ の積

diagonal vector $u_l:=[U_{0,l},U_{1,l+1},\cdots ]$ を使って

$$U\cdot m=\underset{l}{\overset{N-1}{⨁}}(u_l\odot (m\ll l))$$

例

• 線形変換 $L:[x_1,x_2,x_3]\mapsto [x_3,x_2,x_1]$ を考える

$$U=\left(\begin{array}{ccc}0& 0& 1\\ 0& 1& 1\\ 1& 0& 0\end{array}\right)$$ $$U\cdot m=\underset{l}{\overset{N-1}{⨁}}(u_l\odot (m\ll l))$$ $$u_0=\left(\begin{array}{ccc}0& 0& 1\\ 0& 1& 0\\ 1& 0& 0\end{array}\right),u_1=\left(\begin{array}{ccc}0& 0& 1\\ 0& 1& 0\\ 1& 0& 0\end{array}\right),u_2=\left(\begin{array}{ccc}0& 0& 1\\ 0& 1& 0\\ 1& 0& 0\end{array}\right)$$ $$\begin{array}{rl}U\cdot m& =u_0\odot (m\ll 0)\oplus u_1\odot (m\ll 1)\oplus u_2\odot (m\ll 2)\\ & =[0,\; 1,\; 0]\odot [x_1,x_2,x_3]\oplus [0,\; 0,\; 1]\odot [x_2,x_3,x_1]\oplus [1,\; 0,\; 0]\odot [x_3,x_1,x_2]\\ & =[0,x_2,0]\oplus [0,0,x_1]\oplus [x_3,0,0]\\ & =[x_3,x_2,x_1]\end{array}$$

• matrix-vector multiplication
  
• CMult depth: 1
• n-1 rotation

• shift network で実現

アルゴリズム:線形変換

function lin_trans(m::Vector{Float64}, u::Matrix{Float64})::Vector{Float64}
  # U: n x n
  n = length(m)
  u_0 = diagonal(u, 0)
  m′ = mul(m, u_0)
  for ℓ = 1:n - 1
    # ℓth diagonal vector of U
    u_ℓ = diagonal(u, ℓ)
    m′ = add(m′, mul(rotate(m, ℓ), u_ℓ))
  end
  m′
end

(let m (enc (ecd (vec 1 2 3)))
(let u (vec 0 0 1 0 1 0 1 0 0)
; u0 = (0 1 0), u1 = (0 0 1), u2 = (1 0 0)
(rep + l 3
  (* (L m l) (diag u l))
)))

ops: $n+1$ cmult + $n$ add + $n$ rot

応用

• 線形変換によるHE行列積