DEIM Forum 2023 5b-9-5

Paillier 暗号を用いたデータベース演算実装方式における性能解析に関する検討内藤華†

中野美由紀††

小口正人†† お茶の水女子大学理学部情報科学科 〒 112–8610 東京都文京区大塚 2-1-1†† 津田塾大学学芸学部情報科学科 〒 187–8577 東京都小平市津田町 2-1-1
E-mail: †hana-n@ogl.is.ocha.ac.jp, oguchi@is.ocha.ac.jp, ††miyuki@tsuda.ac.jp
あらまし

企業の機密情報や顧客の個人情報などさまざまな電子データが，外部のクラウドサービスへ委託，処理されている．情報漏洩や改ざんを防ぐためにデータを暗号化する必要があるが，従来の暗号化方式だとデータを処理する際に復号しなければならず秘匿性が損なわれてしまう．ここで，準同型暗号という暗号方式を用いることにより暗号文のまま処理を行うことが可能になるが，扱える演算の制限が少ないほどデータサイズや処理コストが大きくなることが知られている．本稿では，加算のみ演算可能な加法準同型暗号の一種である Paillier 暗号を用いて 7 種類のデータベース演算プリミティブを実装し，その性能評価を行なった．演算を行うサーバと暗号化のための鍵の管理を行うサーバの２種類を用いることにより，乗算も行うことが可能となった．また，演算の手順の簡素化を図り，既存手法とは異なる手法での実装も行った．
キーワード 準同型暗号，プライバシ，問い合わせ処理

1 はじめに近年，個人情報に関与するような機密情報を含むさまざまな電子データが，外部のクラウドサービスに委託，処理されている．第三者のサーバ上でデータをそのままの状態で扱うと情報漏洩や改ざんのリスクがあるため，データの秘匿性を確保するために暗号化が必要である．従来の暗号化手法の場合，データを暗号化してからクラウドに送信したとしても，利用する際に

図 1: Cryptϵ システム構成 [2]復号が必要となるため秘匿性が損なわれてしまう．一方で，準同型暗号という暗号方式を用いると，データを暗号化したまま演算を行うことが可能になり，これによりデータの中身がデータ所有者以外の目に触れることなく処理結果を取り出すことができる．
準同型暗号には，加算または乗算のどちらかのみ計算可能な部分準同型暗号（以下 PHE: Partial Homomorphic Encryption），回数に制限があるが加算も乗算も行うことのできる somewhat 準同型暗号，加算と乗算の演算回数の制限を変更可能な Leveled 準同型暗号（以下 Leveled HE: Leveled Homomorphic Encryption），演算回数に制限のない完全準同型暗号（以下 FHE: Fully Homo-morphic Encryption）などが存在する．しかしながら，行える演算の種類や回数の制限が少ない方式ほど，有用である反面，処理負荷が非常に大きくなることが知られている．

類の演算が可能である．
本稿では，Cryptϵ を基に 7 種類のデータベース演算プリミティブを実装し，演算の手法や処理速度について考察する．さらに，Cryptϵ とは異なる手法での演算方法についての提案を行う．

2 関連研究
本節では，図 1 の Cryptϵ のシステム構成や処理の手順について説明する．

2. 1 Cryptϵ 概要
Cryptϵ は，暗号化されたデータに対して 2 種類のサーバを用

本研究で用いる Paillier 暗号 [1] は，Paillier によって提案さいてプログラムを実行することで，差分プライバシ [3, 4] を満れた公開鍵暗号方式で，加法準同型性を持つ PHE である．したした演算結果を出力するシステムである．データ解析者や処たがって，Leveled HE や FHE と比べてデータサイズが小さく理を行う 2 つのサーバにはデータ所有者の個人情報を知られる低いコストでの演算が可能であるといった利点がある．さらに，ことなく，実行することが可能である．

Chowdhury らの Cryptϵ [2] では，Paillier 暗号を用いて暗号文同2. 2 処理の手順士の加算に加えて乗算も行う手法が提案されており，豊富な種暗号データを収集し演算を実行する Analytics Server（以下AS）と，鍵の生成・管理やプライバシコストの管理，暗号データの復号を行う Cryptographic Service Provider（以下 CSP）の2 つのサーバを中心に以下の手順で動作する．
（ 1 ） CSP はデータ所有者から伝えられたプライバシコストの見積もり（以下 ϵ B ）を記録する．また，Paillier 暗号方式を用いて公開鍵と秘密鍵の鍵ペアを生成する．
（ 2 ） 各データ所有者は，CSP が生成した公開鍵を利用して自分のデータを暗号化し AS に送信する．ここで，暗号化にLinearly Homomorphic Encryption（以下 LHE）[5] を用いると暗図 2: システム構成

号文同士の加算，暗号文と平文の乗算が可能であるが，LHE を発展させた Labeled Homomorphic Encryption（以下 labHE）[6]を用いることで暗号文同士の乗算も可能となる．

表 1: 実験環境（ 3 ） AS はそれらのデータを集めて暗号化データベース D̃

ASCSPを作成し，これに対してデータ解析者から送られた Cryptϵ プロCPUグラムを実行する．Project や Filter などのデータベース演算プ

OSmacOS 13.1macOS 13.1

メモリ

16 GB

8 GB

リミティブを実行した結果にノイズを付与したうえで，CSP にIntel Core i5 1.6 GHz Intel Core i5 1.6 GHz送信する [7]．これにより，CSP は個人のプライバシが保護さ
表 2: テーブルを one-hot-encoding で表現した例

れた結果のみ知ることができる．
（ 4 ） CSP は，演算によって発生したプライバシコストが ϵ Bを超えていないことを確認できると，保管しておいた秘密鍵で復号し結果を出力する．

3 実験概要本節では，2 節の Cryptϵ を基に実装したプログラムについて説明する．

3. 1 処理の手順···

Age22···

Age59···

GenderFemale

Gender Male······

1···

0···

10······

0···

1···

01···

ない．

3. 2 扱うデータ
Cryptϵ と同様，Adult データセット [10] を用いる．⟨Age, Gender, NativeCountry, Race⟩ のカラムを抽出し，レコード数 10000
件のテーブルを作成した．表 2 に示すように one-hot-encoding

図 2 に示すように，2 台の PC 上にそれぞれ AS と CSP を作という 0 と 1 のダミー変数でデータを表現したうえで labHE

成し通信することで演算を行う．暗号化は，GitHub 上で公開さで暗号化を行い，T̃ とした．one-hot-encoding では，例えばれている Paillier 暗号のライブラリ [8] を用いて labHE で行なっ

⟨22, Female⟩ というレコードは，⟨[0, . . . , 0, 1, 0, . . . , 0], [1, 0]⟩ の| {z } | {z }た．実験で使用したマシンの性能は表 1 の通りである．演算処

2178

理前と処理後の暗号データは，Google Cloud Storage [9] に保存ように表現する．また，T̃ に加えて，各レコードが演算に必要することで AS と CSP 間でのデータの共有を行えるようにしであるか否かを 0 と 1 で表すベクトル B を作成し，すべての要た．以下の手順で処理を行う．

素を 1 で初期化する．これは，複数の演算プリミティブを連続（ 1 ） CSP が平文のデータをデータベースから取得し暗号化して利用する際に有用である．例えば Filter の条件を満たさなしたうえでクラウド上に保存する．

いレコードを 0 にすると，それ以降の演算には用いられないよ（ 2 ） AS がクラウドから暗号データを読み込む．Project やうにすることができる．

Filter などのデータベース演算プリミティブを暗号化状態で実行した結果を，暗号文のまま再びクラウド上に保存する．
（ 3 ） CSP がクラウドから演算結果を読み込み，保管しておいた秘密鍵で復号して平文の結果を取得する．
なお，本稿では AS 上でのデータベース演算プリミティブに焦点を置いて実装を行うため，差分プライバシのためのノイズ付与とそれに伴って発生するプライバシコストの計算は行わない．したがって，Cryptϵ ではどちらのサーバにも個人情報が見えないが，本実験では CSP はデータ収集時と演算結果の復号後に平文にアクセスできてしまう．乗算を行う際に AS と CSPがデータのやり取りを 1 回行う必要があるが，ここでは秘匿化によって AS のみならず CSP にも正しい情報を知ることはでき

3. 3 暗号化手法
labHE による暗号化手法を示す．記号の一覧は表 3 にまとめた．

Setup(1λ )：セキュリティパラメータ λ に基づいてマスタ公開鍵（以下 mpk）とマスタ秘密鍵（以下 msk）の鍵ペアを作成する．

KeyGen(mpk)：ランダムにユーザごとのシード σi を生成し，mpk で暗号化することでユーザ秘密鍵（以下 uski ）を作成する．
labEnc(mpk, uski , τ, m)：ユーザごとのラベル τ と σi を基に，擬似ランダム関数によって b を求める．a = m − b，β = Encmpk (b)とすると，C = (a, β) が m の暗号文となる．

labDec(msk, c)：C = (a, β) とすると，m = a + Decmsk (β) として復号できる．

表 3: 記号一覧記号意味m

平文．m ∈ M．

c

暗号文．c ∈ C．

C

平文 m を labHE で暗号化した結果．

図 3: Filter 演算方法

C = (a, β) ∈ M × C．
pk

公開鍵．

sk

秘密鍵．

Enc pk (m)pk を用いて LHE で m を暗号化．

Dec sk (c)sk を用いて LHE で c を復号．

c1 ⊕ c2

暗号文 c1 ，c2 の加算．

Add(C1 , C2 )：平文と暗号文を加算する場合と，暗号文同士を加算する場合の 2 通りが考えられる．C1 が平文，C2 が暗号文の場
合，C1 = a1 ，C2 = (a2 , β) とする．このとき，C ′ = (a1 + a2 , β)．
図 4: GroupByCount 演算方法

C1 ，C2 ともに暗号文の場合，C1 = (a1 , β1 )，C2 = (a2 , β2 ) とす′る．このとき，C = (a1 + a2 , β1 ⊕ β2 )．

cMult(c, C)：C = (a, β) の場合，C ′ = (a · c, β · c)．C = α の場
合，C ′ = c · α．

Mult(C1 , C2 )：C1 = (a1 , β1 )，C2 = (a2 , β2 ) と す る と ，C ′ =Encmpk (a1 · a2 ) ⊕ cMult(a1 , β2 ) ⊕ cMult(a2 , β1 )．
genLabMult(C1 , C2 )：genLabMult を用いると，複数回乗算を行うことが可能になる．なお，AS と CSP の間でデータのやりとりが必要となる．C1 = (a1 , β1 )，C2 = (a2 , β2 ) とする．

AS：乱数 r を生成し，e′ = Mult(c1 , c2 ) ⊕ Encmpk (r) と β1 ，β2 をCSP へ送信する．
CSP：e′′ = Decmsk (e′ ) + Decmsk (β1 ) · Decmsk (β2 ) を計算する．ランダムなシード σ′ とユーザごとのラベル τ′ を基に，擬似ランダム関数によって b′ を求める．ā = e′′ − b′ ，β′ = Encmpk (b′ ) として，ē = (ā, β′ ) を AS に送信する．

AS：a′ = ā − r とすると，e = (a′ , β′ ) が C1 と C2 の積となる．
3. 4 演 算 手 法

図 5: GroupByCountEncoded 演算方法

30 と 33 であるため，V との内積が 1 となり， B との積も 1 であれば抽出される．
（ 4 ） Count

B の要素をすべて足し合わせた結果 c を出力する．
（ 5 ） GroupByCount3. 3 項の暗号化手法を用いてデータベース演算プリミティブある属性について値ごとの要素数を求める．T̃ のカラムごとを実装する．にすべての要素を足し合わせることでそれぞれの値の個数を求（ 1 ） CrossProduct

め，ベクトル V を出力する．図 4 に，属性 NativeCountry につテーブル T̃ に含まれる属性 Ai と A j の直積をとり新たな属性

いて GroupByCount を行う方法を示す．

′A で置き換え T̃ を出力する．Ai , A j の重複しない値の個数を（ 6 ） GroupByCountEncodedそれぞれ si , s j とすると，新たに s = si · s j 個の値が生成される．

GroupByCount の 結 果 V を 入 力 と し て 受 け 取 り，こ れ をしたがって，one-hot-encoding で表すと，Ai の si 列と A j の s j

one-hot-encoding で 表 し た Ṽ を 出 力 す る ．暗 号 文 の ま ま で′は one-hot-encoding に変換できないため，図 5 に示すように′列が取り除かれ A の s 列が追加される．

CSP にデータを送信し復号する必要がある．まず，ランダ（ 2 ） Project′T̃ から指定した属性以外のカラムを取り除き T̃ を出力する．

ムな整数の配列 M を作成して V = V + M とし，V を CSP（ 3 ） Filterへ 送 信 す る ．CSP は V を 復 号 し た も の を one-hot-encoding

指定した条件を満たすレコードに対応するビットを 1 としたに 変 換 し ，再 び 暗 号 化 し た う え で AS へ 送 り 返 す（Ṽ）．

ベクトル B を出力する．抽出する値を one-hot-encoding で表Ṽi, j = Ṽi, j+Mi (i = 1, 2, . . . , s, j = 1, 2, . . . , |T|) とすることで， Miしたベクトルを V とし，T̃ のレコードごとに V との内積を求

ビット分ずつ左にずれるので元の V を one-hot-encoding で表現′める．求めた内積と B をビットごとに乗算した結果 B を出力することができる．

する．図 3 に，Age が 30 以上 35 以下であるレコードを Filter（ 7 ） CountDistinct

する方法を示す．レコード 1 とレコード 2 はそれぞれ，Age が属性 A について重複しない値の個数を求める．CountDistinct′

図 6: 処理の流れについては，Cryptϵ と異なる手法で演算を行うことにより簡素化を図った．Cryptϵ では，ほかの演算手法とは異なり CSP が生成した Garbled circuit [11, 12] を用いて演算を行う．提案手法では，Garbled circuit は用いず，AS と CSP がデータのやり取りを1 回のみ行う．属性 A について図 5 の GroupByCountEncodedと同様の処理をを行い Ṽ を受け取る．このとき，T̃ にひとつも含まれていない値は全てのビットが 0 となっている．したがって，Ṽ に含まれる 1 の個数が CountDistinct の出力となる．

4 基本性能評価結果本節では，データサイズや 3. 4 項で述べた演算プリミティブ

図 7: データの種類とサイズの関係の実行時間について考察する．図 6 は，例として属性 Genderについて GroupByCount を実行する際の暗号化から演算，復号までの流れを示している．図中の赤い矢印は，実行時間として計測した部分を表している．暗号化の実行時間はすでにone-hot-encoding に変換されている T̃ の暗号化に要した時間を，演算の実行時間は AS が取得した T̃ から演算結果を算出するの4. 2 実 行 時 間
147 ビットで表現したレコード 10000 件の場合，データの暗号化には平均して 850 秒程度の時間を要した．一方で，同じレコード数の暗号データ T̃ の復号には 300 秒程度かかった．以に要した時間を，復号の実行時間は取得した演算結果を復号す

下，図 8 に示した各演算の実行時間について考察する．

るのに要した時間を示している．他の演算についても，同様に（ 1 ） CrossProduct

計測を行った．

属性の組み合わせは全部で 6 通りあり，2 つの属性のカラム数の積 s が小さい方から 4 通りの組み合わせについて実行時間

4. 1 データサイズ
レコード数 1000 件，10000 件，20000 件のときの，元デーを計測した．2 つの属性の直積を求めるためにレコード 1 件につき genLabMult を s 回行う必要があり，ほかの演算と比べてタ，暗号化前の one-hot-encoding で表現したデータ，暗号デー処理時間が非常に長くなった．2 つの属性に含まれる値の組みタのデータサイズは図 7 のとおりである．クラウド上に pickle

合わせ総数と実行時間は，図 8(a) の通りほぼ比例している．こファイルとして保存したときのデータサイズを示している．いのデータセットで最も時間のかかる組み合わせは NativeCountry

ずれのデータも，レコード件数に比例してサイズが増大していと Age で，値の組み合わせ総数が 40 × 100 = 4000 であること

る．データを one-hot-encoding に変換するとカラム数が増える

から 100 時間以上かかると予想できる．

ため，元のデータよりもサイズが平均して 29 倍程度の大きさ（ 2 ） Projectとなっている．暗号データは one-hot-encoding の 6 倍程度にとそれぞれの属性を one-hot-encoding で表現したときのカラム

どまった．

数と 100 回 Project を実行した平均の処理時間の関係は図 8(b)の通りである．Add，cMult， Mult などの演算は行わないため，

(a) CrossProduct(b) Project(c) Filter(d) GroupByCount(e) GroupByCountEncoded(f) CountDistinct

図 8: 実行時間計測結果

ほかの演算と比べて処理時間が非常に短くなった．それぞれのそれぞれの属性を one-hot-encoding で表現したときのカラム属性を one-hot-encoding で表現したときのカラム数と実行時間数と GroupByCountEncoded の処理時間の関係は図 8(e) のとおはほぼ比例している．

りである．GroupByCount と同様，それぞれの属性を one-hot-（ 3 ） Filterencoding で表現したときのカラム数に比例して処理時間が増加

Age，Gender，NativeCountry の 3 種類の属性について Filterした．また，GroupByCount の実行時間との差より，全体の 1を実行した．結果は図 8(c) のとおりである．緑色の点は Age，割程度が one-hot-encoding への変換にかかる処理時間であると灰色の点は NativeCountry，青色の点は Gender に関する条件で分かる．

Filter を行った結果を表している．ここで条件数とは，その条（ 7 ） CountDistinct

件によって抽出される値の数を表す．例えば， 30 <= Age < 40を条件とする場合は 10， Age が奇数 を条件とする場合は 1数と実行時間の関係は図 8(f) の通りである．他の演算と同様，から 100 に含まれる奇数は 50 個なので 50， Age が偶数をそれぞれの属性を one-hot-encoding で表現したときのカラム数条件とする場合も 50 となる．どの属性においても，抽出するに比例して処理時間が増加した．また，GroupByCount の結果条件の数と実行時間は関係していない．一方で，3 つの属性をV を利用して GroupByCountEncoded と同様の処理を行なってそれぞれの属性を one-hot-encoding で表わしたときのカラム比較すると，one-hot-encoding で表したときのカラムが 100 列から算出するため，GroupByCountEncoded と同程度の時間を要の Age や 40 列の NativeCountry では，カラムが 2 列の Genderした．と比べて長い時間を要していることが読み取れる．
（ 4 ） Count

100 回 Count を実行した結果，処理時間は平均で 0.029 秒となった． B の要素の加算のみであるため，非常に短時間で処理が完了した．
（ 5 ） GroupByCount
それぞれの属性を one-hot-encoding で表現したときのカラム数と GroupByCount の処理時間の関係は図 8(d) の通りである．
カラム数の増加に伴って処理時間も増加していることが読み取れる．
（ 6 ） GroupByCountEncoded

5 まとめと今後の課題
加法準同型性を持つ Paillier 暗号を用いてデータベース演算プリミティブを実装，性能評価を行った．Paillier 暗号は PHEの一種であるが，暗号化方式として labHE を用いることにより，加算のみならず乗算の演算も可能となった．CrossProduct のよ
うに複数の属性の直積を用いる演算や，GroupByCount のように乗算を多用するような演算では，処理時間が増大した．一方
で，Count では B を利用することで非常に短い時間での処理が可能であった．また，データの暗号化にも比較的長い時間を要しており，改善の余地があると感じた．今後の課題として，直積演算や本実験で扱っていない演算の実装，データの暗号化の効率的な手法などを検討していきたい．

文

献[1] P. Paillier, “Public-key cryptosystems based on composite degree
residuosity classes,” Proceedings of the 17th International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT 99, pp. 223–238, Berlin, Heidelberg, 1999. SpringerVerlag.
[2] Amrita Roy Chowdhury, Chenghong Wang, Xi He, Ashwin
Machanavajjhala, and Somesh Jha, “Cryptϵ: Crypto-Assisted Differential Privacy on Untrusted Servers,” Proceedings of the 2020
ACM SIGMOD International Conference on Management of Data,
pp. 603–619, 2020
[3] A. Agarwal, M. Herlihy, S. Kamara, and T. Moataz, “Encrypted
Databases for Diﬀerential Privacy,” 2018.
[4] N. Li, M. Lyu, D. Su, and W. Yang, “Diﬀerential Privacy: From Theory to Practice,” Morgan and Claypool, 2016.
[5] I. Giacomelli, S. Jha, M. Joye, C. D. Page, and K. Yoon, “Privacypreserving ridge regression with only linearly-homomorphic encryption,” In B. Preneel and F. Vercauteren, editors, Applied Cryptography and Network Security, pp. 243–261, Cham, 2018. Springer
International Publishing.
[6] ] M. Barbosa, D. Catalano, and D. Fiore. Labeled homomorphic encryption - scalable and privacy-preserving processing of outsourced
data. In ESORICS, 2017.
[7] C. Dwork and A. Roth, “The Algorithmic Foundations of Diﬀerential Privacy,” Found. Trends Theor. Comput. Sci., Vol.9, pp. 211–407,
August 2014.
[8] CSIRO’s Data61, Python Paillier Library, 2013. https://github.com/
data61/python-paillier.
[9] Google cloud platform. https://cloud.google.com[10] Dua, D. and Graﬀ, C. (2019). UCI Machine Learning Repository.
Irvine, CA: University of California, School of Information andComputer Science.
[11] A. Yao, “Protocols for Secure Computation,” Proceedings of the 23rd
Annual Symposium on Foundations of Computer Science, Chicago,
pp. 160–164, November 1982.
[12] Y. Lindell and B. Pinkas, “A Proof of Security of Yao’s Protocol for
Two-Party Computation,” Journal of Cryptology, Vol.22, No.2, pp.
161–188, April 2009.