DEIM Forum 2023 5b-9-4

圧縮センシングを利用した準同型暗号化データの通信量削減
泉

湖雪†

松本

茉倫†

小口

正人†

† お茶の水女子大学 〒 112–8610 東京都文京区大塚 2-1-1
E-mail: †koyuki@ogl.is.ocha.ac.jp, marin@ogl.is.ocha.ac.jp, oguchi@is.ocha.ac.jp
あらまし 近年の IoT デバイスやクラウドサービスの普及により，クラウド上で安全にデータを処理する必要がある．
そこで，暗号文同士の加算や乗算が可能な準同型暗号が注目されている．しかし，準同型暗号は送信するデータが多次元であるほど通信量が大きくなってしまうという課題がある．また，収集するデータがスパースな場合は無駄が多くなる．そこで本研究では，零成分を多く含む (以下 スパースな) データを圧縮してから復元する「圧縮センシング」
を利用して，通信量を削減してスパースな多次元データを送信することを提案する．実験では乱数により生成したス
パースな多次元データを用いて，圧縮ありと圧縮なしの場合で，準同型暗号文のサイズ，サーバでの復元結果の精度,
実行時間を比較する．
キーワード 準同型暗号，圧縮センシング, スパース
サーバでの圧縮センシングによる復元結果の精度，実行時間の1 はじめにスマートフォンなどの IoT デバイスが普及したことで，クラウドなどのサーバにデータが蓄積され，分析に利用されるようになった．しかし，収集したデータは個人に関する情報を含む
場合があるため，外部からの攻撃などによるデータの漏洩に備える必要がある．そこで，暗号文同士の加算や乗算が可能な準同型暗号を用いることで，盗聴のリスクを減らせるだけでなく，暗号状態のままデータ分析を行うことが可能となる．準同型暗号の課題として，送信するデータが多次元であるほど通信量が大きくなってしまうことが挙げられる．また，収集するデータ比較を行う．ここでは単純に，スパースな多次元データをクライアントで準同型暗号化して，圧縮せずにサーバに送信する方法を Baseline とする．
実験の結果，圧縮率を 50%に設定した場合は提案手法は圧縮せずに送信した場合に比べて 50%通信量を削減できることを示した．このとき，復元後のベクトル x̂ の二乗平均平方根誤
差 (以下 RMSE: Root Mean Squared Error) はおよそ 0.15 となった．

2 既存技術がスパースな場合は無駄が多くなる．したがって本研究では，

2. 1 準同型暗号

図 1 に示すような圧縮センシングを利用した多次元データの送

2. 1. 1 特信を提案する．

準同型暗号とは，以下のような特徴を持つ公開鍵暗号である．

徴

圧縮センシングは，スパース性を利用することにより，少ないサンプル数からもとのデータを復元する技術である．圧縮行
列 A を掛けることで低次元データを得て，得られた低次元デー
タと圧縮行列 A から推定することで，元の多次元データを復元

Decrypt(Encrypt(m) ⊕ Encrypt(n)) = m + n(1)

Decrypt(Encrypt(m) ⊗ Encrypt(n)) = m × n(2)

する．この技術を用いて圧縮されたスパースな多次元データを

暗号文同士の加算が可能であるという特徴を表す (1) を加法準同型暗号化してクライアントからサーバに送信することで，準同型性といい，暗号文同士の乗算が可能であるという特徴をクライアントとサーバ間の通信量の削減が期待できる．

表す (2) を乗法準同型性という．準同型暗号には多くの種類が提案手法では，圧縮センシングによる圧縮と準同型暗号ラ

存在し，加法準同型性のみを持つ加法準同型暗号には Paillier

イブラリの Microsoft SEAL を使った平文の準同型暗号化をク

暗号 [1]，乗法準同型性のみを持つ乗法準同型暗号には RSA 暗ライアント側で行い，圧縮センシングの復元をサーバ側で行

号 [2] が挙げられる．

う．代表的な再構成アルゴリズムとして Orthogonal Matching

また，加法準同型性と乗法準同型性の両方を満たす準同型暗Pursuit(以下 OMP) があるが，OMP で復元する際には比較演

号は演算可能回数によって 3 つに分類できる．演算可能回数算を行う．暗号化された状態では比較演算が困難であるため，に制限がある場合は Somewhat Homomorphyc Encryption(以比較演算を使用しないような復元アルゴリズムを用いる必要

下 SHE) といい, パラメータにより演算可能回数が決まる場合がある．そこで，今回は一般逆行列による L2 ノルムの最小化

は Leveled Homomorphic Encryption(以下 LHE) という [3]．

によって圧縮前のデータを推定する．実験では，乱数により生演算可能回数に制限がない準同型暗号は完全準同型暗号 (以下成したスパースな多次元データを用いて，Baseline と提案手法

FHE: Fully Homomorphic Encryption) という．ブートスト

で，クライアントからサーバに送信する準同型暗号文のサイズ，

ラップを行い, 演算による誤差の蓄積をリセットすることにより，

提案⼿法

多次元データの準同型暗号化
スパースな
n次元データ!!

m×nの⾏列!をかけて圧縮する (m < n)

m

$

スパースな
n次元データm次元データ 暗号化

"

!!

n

m次元データ"クライアントm次元データ"

圧縮センシング

復元した
n次元データ

により復元

#
!

サーバ
図1

提案手法．クライアント側は圧縮センシングによる平文の圧縮と準同型暗号化を行い，サーバ側は圧縮センシングの復元を行う．圧縮センシングにより，Baseline に比べて，クライ
アントからサーバに送信する暗号文のサイズは n 次元から m 次元に減少する．したがって，クライアントとサーバ間の通信量の削減が可能となる．

加算と乗算の任意回数の演算を実現している．FHE は，1978
年に Rivest ら [4] によって構想され，2009 年に Craig Gentry
ら [5] によって格子暗号を用いた実現手法が提案された．

2. 2 圧縮センシング [15]2. 2. 1 概要圧縮センシング (compressed sensing) は，スパース性 (零成SHE は LHE よりも演算にかかる時間は短いが乗算可能回数分が多いという性質) を持つ高次元の信号を少ない観測から復に制限があり，LHE は演算可能回数をあらかじめ設定できる

元する枠組みである．未知の n 次元ベクトル x0 が，m 行 n 列が，演算可能回数の増加と演算にかかる時間は比例関係にあるの行列 A を用いて以下のように線形変換されているとする．こという課題がある．FHE には暗号文同士の加算と乗算が任意のとき，m < n とする．

回数可能であるが，暗号文のサイズが大きく，クライアントとサーバ間の通信量が大きくなってしまうといった課題がある [6]．
本研究では LHE を使用する．

2. 1. 2 暗号化方式 [7] とライブラリ
現在，準同型暗号は，第 1 世代 イデアル格子による方式，
第 2 世代 BGV [8] や BFV 方式 [9]，第 3 世代 GSW 方式や

TFHE [10] [11], 第 4 世代 CKKS 方式 [12] の 4 つの世代に分類される．特に，CKKS 方式は整数だけではなく実数や複素数も計算することができるという特徴を持ち，機械学習に応用可能であることから近年注目されている．スケールというパラメー
タによって実数を整数に見立てて計算するため，計算結果に若干のノイズが生じ，計算を繰り返すとノイズが増加するため，







a11

y1
 ..
   .
 y2    
 .  =  ai1
 ..     ..
 .

ym
am1

···
..
.

a1i

···

aii
..
···

ami

.

···


a1n
 

x1
.. 
 
. 
  x2   
a2n  ×  .   . ..   . 
. 

xn
amn

∴ y = Ax0

(3)

元のベクトル x0 の零ではない要素が k 個あると仮定して，低次元な m 次元ベクトル y と圧縮行列 A から (3) を満たす x0を求める．一般には，未知数の数が方程式の数より多いため不定となり，解を一意に定めることができない．しかし，x0 の要素の多くが零であったとすると，解を一意に推定できる．

リスケール処理を行う．
また，現在では多くの準同型暗号ライブラリが公開されており，有名なライブラリの 1 つとして，Microsoft SEAL [13] がある．SEAL は Microsoft が開発したライブラリで，BFV 方
式と CKKS 方式の 2 つを利用でき，C++で実装されている．
他にも，BGV 方式，C++で実装され，ブートストラップもサポートしている HElib [14] も有名である．
本研究では，実数を扱いたいため，CKKS 方式の SEAL を用いて提案手法を実装した．

2. 2. 2 再構成アルゴリズム - OMP
圧縮センシングに使用される再構成アルゴリズム
は 多 数 存 在 す る ．代 表 的 な ア ル ゴ リ ズ ム に は ，例 え ば

OMP(Orthogonal Matching Pursuit), IHT(Iterative Hard
Tresholding), IST(Iterative Soft Tresholding) などがある．再構成アルゴリズムを選定する際には，暗号化状態のまま演算が可能かを考慮した．暗号化状態のまま可能な演算は限られており，暗号化状態での演算が困難な例の 1 つとして比較演算が挙げられる．ここでは OMP のアルゴリズムを紹介する．また，

本研究では一般逆行列による L2 ノルムの最小化によって圧縮

ユーザは統計キーで並べ替えられた平文の復元結果

前のデータを推定したが，詳細については 4. 2 で説明する．

のみを得る．

OMP とは貪欲法の一種であり，y を列ベクトル ai の成分のみで近似する．残差を最も良く近似する順に A の列ベクトルの

MPCC 方式では，クラウドサービスプロバイダーに対する添字を添字集合 T に加えていくことで復元する．OMP の詳細

データの機密性を損なうことなく，計算量の多いスパース信号

は以下の通りである．

の復元をクラウド上で行うことができる．
また，MPCC 方式に対して暗号文のみの攻撃を適用するこ•

入力：観測信号 y ∈ Rm , 観測行列 A ∈ Rm×n

(非零要素数 k ∈ N)•

3. 2 暗号化領域での圧縮アルゴリズムの実行

初期化：推定値 x̂ = 0, 添字集合 T = ϕ

Canard ら [17] は，FHE を用いて入力データが暗号化されて終了条件を満たすまで以下を繰り返す．

いる場合に圧縮アルゴリズムを実行することを目的として，最（ 1 ） 残差 y − Ax̂ と最も相関の高いも基本的な圧縮アルゴリズムである Run-Length Encoding(以（2）(内積の絶対値の大きい)A の列ベクトルの

下 RLE) を分析し，圧縮アルゴリズムを実行する際に多くの問添字を T に追加する．

題が生じることを示した．

x̂ = argmin||y − AT xT ||22 を一般逆行列でx̂評価することによって |T | スパースな推定値 x̂を求める (一般逆行列で評価する)．

•とは計算上不可能であることが証明されている．

RLE とは，α1 , α2 , ... のような記号列が与えられたとき，{
回数，記号 } のペアからなる列を生成することで，記号列を圧縮するものである．RLE の例は (4) に示す．

0, 0, 2, 3, 3, 4, 0, 0, 0

出力：推定値 x̂ ∈ Rn

→ {2, 0}, {1, 2}, {2, 3}, {1, 4}, {3, 0}(4)「残差を最も良く近似する」というのは，「内積の絶対値が最も大きい」と言い換えられる．また，argmin||y − AT xT ||22 のx̂−1 ⊤解である x̂ は，x̂ = (A⊤AT y ，つまり，x̂ = (AT の一
T AT )

RLE アルゴリズムは単純であるにも関わらず，そのままそれ自体を準同型暗号で実装することはできない．FHE の演算能力の特徴として以下が挙げられる．

般逆行列) と y の積 で求められることが一般に知られている．

3 関連研究ここでは関連する研究として，圧縮とプライバシー保護を実現する multi-class privacy-preserving cloud computing•

FHE は暗号化領域のデータに依存する条件を持つ”if...then...else”構文を少なくとも直接実行できない．

•

暗号化領域のデータに依存する終了条件を持つループ構造を直接実行できない．

scheme(以下 MPCC 方式) の提案，暗号化領域での圧縮アルゴ
リズムの実行の 2 つを挙げて説明する．

3. 1 圧縮センシングに基づくマルチクラスプライバシー保護型クラウドコンピューティング

Kuldeep ら [16] は，センサデータを正確に取得できるスー
パーユーザと，平均値や分散などの統計データのみを取得でき

つまり，暗号化領域のデータに対して FHE はいわゆる静的
制御構造プログラムしか実行できないといえる．しかし，動的制御構造プログラムを静的制御構造プログラムに変換するための正規化を行えば FHE でも実行できる．正規化の 1 つの例として (5),(6) を示す．

る準権限ユーザの 2 クラスの秘匿性の実現を目的として，以下のような MPCC 方式を提案した．
（ 1 ） IoT デバイスは圧縮センシングにより継続的にデータをセンシングし，センシングしたデータをクラウドに送信，保存する．
（ 2 ） スーパーユーザにはマスターキーを，準権限ユーザには統計キーを持たせる.
（ 3 ） データを取得するために，ユーザはクラウドにクエリを送信する．
（ 4 ） クラウドがスパース信号を復元し，復元された暗号文をユーザに送信する．
（ 5 ） ユーザは自分のアクセス権に従って，暗号文に鍵を適用し，スーパーユーザは平文の復元結果を，準権限

x := c?a : b(5)≡x:= c ⊗ a ⊕ (1 ⊕ c) ⊗ b(6)”if...then...else”構文は (5) の条件代入演算子で表すことがで
き，値 x,a,b,c に関する情報を一切学習することなく，この構文の両方の分岐を実行し，(6) のように演算子を用いて条件値にしたがって結果を適切に再結合することができる．このように，アルゴリズム中に動的な部分が存在する場合にはアルゴリ
ズム制御フローを正規化することが必要となる．また，この研究では，実際に FanVercauteren 暗号と Armadillo FHE コン
パイラを用いた具体的な実験も行っている．

表1

4 提案手法4. 1 概要

ここでは単純に，スパースな多次元データをクライアントで準

マシン性能

Raspberry Pi

サーバ

OS

Raspbian 11

Ubuntu 22.04.1

CPU

ARM Cortex-A72

Intel(R) Xeon(R) Gold

同型暗号化して，圧縮せずにサーバに送信する方法を Baselineとする．本研究では，図 1 で示すような，スパースなデータを

5115 CPU @ 2.40GHz
コア数

4

10

プロセッサ速度600MHz

1GHz

RAM

4GB

192GB

圧縮してから復元する「圧縮センシング」を利用して，通信量を削減してスパースな多次元データを送信することを提案する．
ここで m, n は m < n であるものとする．
クライアント（ 1 ） スパースな n 次元データ x0 に，m 行 n 列の圧縮行列 A をかけて圧縮するを利用し，スパースな多次元データは 0,1 の 2 値で構成されているものとした．提案手法では，スパースな多次元データを圧
縮センシングにより圧縮してから準同型暗号化した暗号文をク

y = Ax0

ライアントからサーバに送信し，サーバで圧縮センシングの再（ 2 ） 得られた m 次元データ y を暗号化する構成アルゴリズムにより復元をするものとした．Baseline では，
スパースな多次元データをクライアントで準同型暗号化して，Encrypt(y)（ 3 ） 暗号化状態の y をサーバに送信する

圧縮せずにクライアントからサーバに送信するものとした．これらの Baseline と提案手法で，クライアントからサーバに送信する準同型暗号文のサイズ比較，圧縮センシングの再構成ア

サーバ

ルゴリズムによるサーバでの復元結果の精度測定，クライアン（ 4 ） 暗号化状態の y を受け取る

トとサーバでの実行時間の測定を行った．精度の評価方法には（ 5 ） 再構成アルゴリズムにより復元した n 次元
データ x̂ を得る

RMSE を用いた．また，スパースな多次元データを生成する際の乱数には，メルセンヌ・ツイスタ [18] を使用した．

x̂ = Reconstruction(Encrypt(y))
Baseline に比べて，クライアントからサーバに送信する暗号文のサイズは n 次元から m 次元に減少するため，クライアン
トとサーバ間の通信量の削減が可能となる．

5. 2 実 験 環 境
実験に使用したマシンの性能を表 1 に示す．

5. 3 パラメータ
5. 3. 1 準同型暗号に関するパラメータ [19]4. 2 提案手法で使用した再構成アルゴリズム
代表的な再構成アルゴリズムの 1 つである OMP では，2. 2. 2

実験で使用した SEAL の CKKS 方式のパラメータを表 2 に示す．

でも述べたように，残差を最も良く近似する，つまり，残差と暗号文の長さ slot count は, 使用する多項式の次元を示

最も内積の絶対値が大きい A の列ベクトルがどれかを見つける

す poly modulus degree に 0.5 をかけた値となる．ここでは，際に比較演算が必要となる．しかし，準同型暗号での比較演算

poly modulus degree = 8192 としたため，slot count = 4096

は非常に難しい．なぜなら，暗号文どうしの比較が簡単に可能となる．また，暗号文同士の乗算可能回数を示す Leveled や復であるとすると挟み込みなどによって値の特定ができてしまう

号時の精度，復号時の実数値の精度は，チェインの設定によっからである．そのため提案手法では，圧縮センシングの再構成て決まる．実験ではチェインは次のように設定した．

アルゴリズム Reconstruction(·) において，一般逆行列によって最小ノルム解，つまり L2 ノルムが最小となる推定結果を得⊤る．すなわち encrypt(x̂) = (A A)−1⊤

A × encrypt(y) のように一般逆行列と暗号化された低次元行列との積を求める．

5 実

験

5. 1 概要

実 験 で は ク ラ イ ア ン ト に は Raspberry Pi，サ ー バ に はUbuntu のマシンを使用し，Baseline と提案手法の 2 つを Microsoft SEAL ライブラリを用いて C++で実装した．Baseline，
提案手法ともに乱数により生成されたスパースな多次元データ

modulus chain = {60, 40, 40, 60}(7)(7) は最初の数値 (以下 プライマリビット) である 60，最後の数値 (以下 ラストビット) である 60, それ以外の (以下 スケー
リングビット)2 つの 40 に分けることができる．

Leveled は ス ケ ー リ ン グ ビット の 個 数 に 依 存 す る た め ，Leveled = 2 となり，2 回乗算可能となる．また，プライマ
リビットは復号時の精度と対応しており，復号時の実数値の整数部分の精度はプライマリビットとスケーリングビットの差と，復号時の実数値の小数部分の精度はスケーリングビットと復号
時の実数値の整数部分の精度ビットの差と対応している．

表 2 SEAL の CKKS 方式に関するパラメータ

800
700

暗号文の長さ slot count4096

セキュリティ

128 bit

Leveled2

復号時の精度

60 bit

暗号⽂のサイズ [KB]

値

669

600
500
400

334

300
200
100

復号時の実数値の精度

0Baseline

整数部分 20 bit
小数部分 20 bit

図2

提案⼿法

圧縮率 50 ％の場合のクライアントとサーバ間の通信量.

n = 1024, m = 512 とした．縦軸は暗号文のサイズである．
提案手法では Baseline に比べて約半分の通信量に抑えられてお5. 3. 2 圧縮センシングに関するパラメータ

り，通信量の削減比率は n と m の比率に対応している．

実験の圧縮センシングには，(n，m)=(1024, 512),(1024, 256),0.25(1024, 128) の よ う に 圧 縮 率 を 変 化 さ せ た も の と ，0.2

を変化させたものを用いた．実験では要素の 95 ％が 0 である

0.15

RMSE

(n, m)=(1024, 512),(256, 128),(128, 64) のように n, m の大小と仮定し，乱数により元のベクトル x0 を生成した．

0.1

また，表 2 で示したとおり，長さが 4096 の暗号文を使用す

0.05

るため，4096 の要素すべてが埋められた状態でクライアント

050%からサーバに渡す必要がある．そのため，slot count ÷ m 個の75%

87.50%

圧縮率

スパースな n 次元データ x0 を用意し，圧縮後のベクトル y を

図3

slot count ÷ m 個を詰めた 1 つのベクトルを渡す形としている．

スパース値と RMSE

図4

圧縮率と RMSE

5. 4 評 価 方 法
5. 1 で述べたように，Baseline と提案手法での圧縮センシン
グの再構成アルゴリズムによるサーバでの復元結果の精度の評
価方法には RMSE を用いた．RMSE は以下の式で算出される．
v
u n−1
u1 X
RM SE = t(yi − yˆi )2
(8)
n i=0

図5

元のベクトル x0 と復元後のベクトル x̂ の比較.
青が元のベクトル x0 ，オレンジが復元後のベクトル x̂ を表す．

式 (8) 中の yi は実際の値，yˆi は予測値，n はデータの総数を

緑は今回設定した閾値である．

表す．RMSE の値が小さいほど誤差の小さいモデルであるといえる．

5. 5 実 験 結 果
5. 5. 1 通 信 量
図 2 にクライアントとサーバ間の通信量，つまり，クライアン
トからサーバに送信する準同型暗号文のサイズを示す．Baselineに比べ，提案手法では約半分の通信量に抑えられていることが分かる．これは n と m の比率に対応していることが分かる．

5. 5. 2 精度

スパース値 k と RMSE の関係性を示した図 3 と，圧縮率と図6

図 5 での復元後のベクトル x̂ を閾値により 2 値化した結果.
青が元のベクトル x0 ，オレンジが復元後のベクトル x̂ を 2 値化したものである．緑は今回設定した閾値である．

RMSE の関係性を示した図 4 にあるように，スパース値 k が小さいと精度が高まるという性質を持つ．要素の 95 ％が 0 であると仮定した時の提案手法における RMSE を測定した結果を示す．圧縮率 50 ％ (n = 1024, m = 512) としたときの 8 個の x̂ の RMSE は，おおよそ 0.15 となった．
また，同様のパラメータにおいて，図 5 に元のベクトル x0と再構成アルゴリズムにより復元した n 次元データ x̂ の比較を，図 6 に閾値により 0,1 の 2 値化を行った結果を示す．

図 6 は閾値 0.32 として 2 値化している．このとき，1 である部分は 91%一致していた (5 回の平均値)．

5. 5. 3 実 行 時 間
Baseline と提案手法における実行時間を図 7 に示す．提案手法では，クライアントからサーバに送信する暗号文のサイズの677

Baselineの実⾏時間
0.6

676

実⾏時間 [秒]0.5

実⾏時間 [秒]

5
4

676 秒

0.3
0.2
0.1

3

0
2

0.06 秒50%

75%

87.50%

圧縮率0.12 秒

1

1.7 秒

図 10

0

Baseline

提案⼿法

クライアント 圧縮

図7

0.4

クライアント 暗号化

圧縮率を変化させたときの Baseline の実行時間の変化.

n と m の比率と比例している．

サーバ

圧縮率 50 ％のときの実行時間.n = 1024, m = 512 とした．

読み取れる．これは圧縮行列 A が n × m であり，n, m の大き

クライアントからサーバに送信する暗号文のサイズの減少に伴さと行列計算の時間には正の関係があるからであると考えらい暗号化にかかる時間は減っている.

れる．したがって，長いベクトルを復元するよりも短いベクト

しかし, クライアントで圧縮させる際の行列計算や, 特にサーバでルを複数復元する方が高速であり適しているといえる．また，復元する際の再構成アルゴリズムの計算に時間がかかっている.

Baseline の実行時間の変化について，n と m の比率と比例している．これは，Baseline で暗号化する際に，長さ n のスパー

圧縮率50％のクライアントの実⾏時間

圧縮率50％のサーバの実⾏時間

1.8

800

1.6

700

1.4

スなデータを n ÷ m 個の長さ slot count のベクトルにしているからである．

600

1.2
1

500

0.8

400

0.6

平均の RMSE 値に関して，図 4 でも示したように，やはり圧縮率を高くするほど RMSE 値が大きくなって精度が低くなっ

300

0.4

てしまっていることが読み取れる．したがって圧縮率と精度は

200

0.2
0

100

n=128, m=64n=256, m=128 n=1024, m=512
圧縮

図8

トレードオフの関係にあることがわかる．

0

暗号化

n=128, m=64n=256, m=128 n=1024, m=512

6 まとめと今後の課題

圧縮率 50%時の実行時間．

n, m の値が小さいほどクライアントでの圧縮時間やサーバでの復元時間が短くなっている．

IoT デバイスの普及により，クラウドなどのサーバに個人に関する情報を含むデータが蓄積され，データ分析に利用されるクライアント 暗号化

1.7

0.07

1.68

0.06

1.64
1.62
1.6
1.58

900

1.54

700

0.04
0.03
0.02

75%

87.50%

ることが有効である．しかし，準同型暗号の問題点として，暗

600
500
400

号文のサイズが大きく通信量が大きくなってしまうことが挙げ

300
200

られる．

100
0

0

50%

るために，暗号文同士の加算や乗算が可能な準同型暗号が用い

800

0.05

0.01

1.56

ようになった．外部からの攻撃などによるデータの漏洩に備え

サーバ

実⾏時間 [秒]1.66

実⾏時間 [秒]実⾏時間 [秒]クライアント 圧縮

50%

圧縮率

75%
圧縮率

87.50%

50%

75%

87.50%

圧縮率

本研究では，圧縮センシングを利用して，通信量を削減してスパースな多次元データを送信することを提案した．圧縮セン

図9

圧縮率を変化させたときの実行時間の変化

シングは，スパース性を利用することにより，少ないサンプル数からもとのデータを復元する技術である．

減少に伴い，暗号化にかかる時間は減っているが，クライアン

実験の結果，圧縮率 50%のとき，クライアントとサーバ間のトで圧縮させる際の行列計算や，特にサーバで復元する際の再通信量を約半分に減らすことができた．復元後のベクトル x̂ の構成アルゴリズムの計算に時間がかかってしまっていることがRMSE はおよそ 0.15 であり，閾値 0.32 として 2 値化すると 1

分かる．

である部分は 91%一致した．

5. 6 パラメータの値を変更した場合の実験結果に対する考察
パラメータの値 n, m を変更して，圧縮率 50 ％の場合のクライアントの実行時間の変化を図 8 に，圧縮率を変化させたと今後は，スパースな多次元データの構成を実数にも対応させることや，他の再構成アルゴリズムの使用により，より精度を高めること，実行時間の改善を検討している．

きの実行時間の変化を図 9 と図 10 に示す．実行時間，平均のRMSE 値に関して考察する．
まず実行時間について見てみると，n, m の値が小さいほどクライアントでの圧縮時間やサーバでの復元時間が短いことが文

献[1] Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In International conference
on the theory and applications of cryptographic techniques,pp. 223–238. Springer, 1999.

[2] Ronald L Rivest, Adi Shamir, and Leonard Adleman. A
method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, Vol. 21, No. 2, pp.
120–126, 1978.
[3] Abbas Acar, Hidayet Aksu, A Selcuk Uluagac, and Mauro
Conti. A survey on homomorphic encryption schemes: Theory and implementation. ACM Computing Surveys (Csur),Vol. 51, No. 4, pp. 1–35, 2018.
[4] Ronald L Rivest, Len Adleman, Michael L Dertouzos, et al.
On data banks and privacy homomorphisms. Foundationsof secure computation, Vol. 4, No. 11, pp. 169–180, 1978.
[5] Craig Gentry. Fully homomorphic encryption using ideal
lattices. In Proceedings of the forty-ﬁrst annual ACM symposium on Theory of computing, pp. 169–178, 2009.
[6] 佐藤宏樹, 馬屋原昂, 石巻優, 今林広樹, 山名早人. 完全準同型暗号のデータマイニングへの利用に関する研究動向. 第 15 回情報科学技術フォーラム F-002, 2016.
[7] 準同型暗号の世代区分. https://www.eaglys.co.jp/news/
column/homomorphicencryption/.
[8] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan.
(leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT),
Vol. 6, No. 3, pp. 1–36, 2014.
[9] Zvika Brakerski. Fully homomorphic encryption without
modulus switching from classical gapsvp. In Advances in
Cryptology–CRYPTO 2012: 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012.
Proceedings, pp. 868–886. Springer, 2012.
[10] Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. Tfhe: fast fully homomorphic encryption
over the torus. Journal of Cryptology, Vol. 33, No. 1, pp.
34–91, 2020.
[11] TFHE. https://tfhe.github.io/tfhe/.
[12] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo
Song. Homomorphic encryption for arithmetic of approximate numbers. In International conference on the theory
and application of cryptology and information security, pp.
409–437. Springer, 2017.
[13] Microsoft SEAL. https://github.com/microsoft/SEAL.
[14] HElib. https://github.com/homenc/HElib.
[15] 圧 縮 セ ン シ ン グ: 疎 情 報 の 再 構 成 と そ の ア ル ゴ
リ ズ ム.
https://www.kurims.kyoto-u.ac.jp/~kyodo/
kokyuroku/contents/pdf/1803-03.pdf.
[16] Gajraj Kuldeep and Qi Zhang.
Compressive sensing
based multi-class privacy-preserving cloud computing. In
GLOBECOM 2020-2020 IEEE Global Communications
Conference, pp. 1–6. IEEE, 2020.
[17] Sebastien Canard, Sergiu Carpov, Donald Nokam Kuate,
and Renaud Sirdey. Running compression algorithms in theencrypted domain: a case-study on the homomorphic execution of rle. In 2017 15th Annual Conference on Privacy,
Security and Trust (PST), pp. 283–28309. IEEE, 2017.
[18] Makoto Matsumoto and Takuji Nishimura.
Mersenne
twister:a 623-dimensionally equidistributed uniform
pseudo-random number generator. ACM Transactions on
Modeling and Computer Simulation (TOMACS), Vol. 8,
No. 1, pp. 3–30, 1998.
[19] 格子暗号の CKKS 形式のパラメータ、精度ビットなどの解説（SEAL ライブラリ）. https://qiita.com/kenmaro/items/
931835476ca8781de9f9.