kenmaro です。
秘密計算、特に準同型暗号のことについて記事を書いています。

秘密計算エンジニアとして得た全ての知見をまとめた記事はこちら。
https://qiita.com/kenmaro/items/74c3147ccb8c7ce7c60c

これから準同型暗号について勉強したいリサーチャー、エンジニアの方へのロードマップはこちら。
https://qiita.com/kenmaro/items/f2d4fb84833c308a4d29

今話題のゼロ知識証明について解説した記事はこちら。
https://qiita.com/kenmaro/items/d968375793fe754575fe

概要

TEE ＋ DBというキーワードでいろいろ調べてみました。
TEEについてはあまり業務でも使ったことがないのですが、どのようなDBアプリケーションが存在しているのか非常に興味が出たので、頑張ってまとめてみようと思います。

今回はその中でも特に、

EncDBDB（SAPの論文）https://arxiv.org/pdf/2002.05097.pdf
Operon（Alibabaグループの論文）https://www.vldb.org/pvldb/vol15/p3332-wang.pdf

という二つの実装論文をベースにしてまとめたいと思います。

EncDBDB: Searchable Encrypted, Fast, Compressed, In-Memory Database using Enclaves

要点を箇条書き

TEEを用いたデータベースソリューション(例えばSAP HANA　とかが有名）
カラム指向型
インメモリデータベース
レンジクエリ（where 大なり、小なりなどのオペレーションが可能）
２つの軸によりセキュリティ強度を評価し、ユーザは９つの中から選択できる
アベレージとか加算、カウントを取ったりするような構成も可能

主なコントリビューション

カラム指向型、インメモリデータベースに対して新しいサーチの手法を提案
９つの暗号タイプ（頻度、順序をどこまで守るか、それぞれ３段階で選択）をユーザが自由に選ぶことができる構成
OSSのカラム指向型データベースである、MonetDBにインテグレーションを実装
Enclaveの中のコードベースは1129行しかない（他のTEEベースのデータベース実装は、これより圧倒的にコードが多く、エンクレーブで実行するプログラム量は少ない方がセキュリティ的にも嬉しい）
実際に使われるような数百万件のデータに対して、平文DBに対して数ミリセカンド程度のオーバーヘッドしかかからない
辞書によるデータ圧縮をうまく用いることで、平文のDBよりデータサイズを小さくすることも実際に可能

攻撃者の仮定

攻撃者はDBMSに対してアクセス可能であり、ルート権限をもつ（強い仮定）ことも可能だとする。
ルート権限を持つことから、ファイルシステムへのアクセス、ネットワーク通信へのアクセスももちろん可能だとする。

攻撃者はEnclaveに対してアクセスすることは不可能だが、DBMSへのルート権限があるため、DBMSとEnclaveの間の通信の内容を傍受することは可能だとする。

インメモリデータベース

インメモリデータベースでは、メモリに基本的にデータを保持しておき、ディスクははセカンダリとして使用します。
結果として、全体の処理が高速に動作しやすいというような利点があります。
欠点としては、

複数のカラムに対してフェッチしたデータを、タプル再構築という方法でくっつけるところにオーバーヘッドがあること
updateやインサートといったオペレーションをするときに、とびとびの場所へのメモリアクセスが発生すること

データウェアハウスでよくカラム指向型のデータベースが使われる理由は、
主に少数のカラムに対して、大きなレコード数のデータをスキャンするような分析クエリが実行されることが多いからです。

よく実行されるクエリとしては、例えば
ある国の、あるレンジの価格のプロダクトに限定したセールス価格の合計をクエリで計算する
などがあります。

辞書エンコーディング

辞書エンコーディングを用いることで、保存しているデータを非常に小さく圧縮することができます。
また、辞書エンコーディングはカラム指向型データベースに対してよく使わる手法です。
辞書エンコーディングはコンセプトとしてはとても単純です。
一つのカラムデータに対して、

辞書
属性ベクトル

の二つの情報に分割して保存します。

辞書にはuid をキーとしたインデックス、実際の値をバリューとした情報が書き込まれています。
属性ベクトルは、実際のカラムデータのコピーとなりますが、中身は生データの値ではなく、先ほどの辞書に対応したインデックスが保存されています。
これを用いると、当たり前ですが、例えば

カラムに含まれるデータが大きい
カラムに含まれるデータのユニーク数が小さい

ときにデータの圧縮がとても効率よく実行可能になることが理解できます。

PAE(Probabilistic Authenticated Encryption)

秘匿性
完全性（改竄されていないことの証明）
認証性（本当のユーザから送られてきた暗号化どうかを認証する機能）

を兼ね備えた暗号のスキームです。（すごく便利ですね。）

AESのGCMモード（１２８ビット長）のものが現在はよく使われていたりします。

EncDBDBの構成

ここまで理解すると、EncDBDBの実際の構成を難なく理解することができます。

データのアップロードから分析に至るまでのフローは以下のようになります。

データオーナーはPAEの鍵を自分で生成し、プロキシに送信します
データオーナーは自分のデータをプロキシ経由で送信します
Proxy は先ほどの辞書と属性ベクトルを生成します
プロキシは辞書をエンクレーブへと送信します
プロキシは属性ベクトルをカラム指向型データベースへと保存します

ここまでがデータアップロードのフローです。

ここから、

データオーナーはクエリを発行し、プロキシへと送信します
プロキシはクエリに含まれている分析対象となる値をPAEで暗号化します
プロキシはエンクレーブに問い合わせ、DBから抽出するべき（暗号化されたデータ）データを取得します
DBMSは暗号化されたデータベースからフェッチします
DBMSはプロキシへと結果を返却します
プロキシは結果を復号し、ユーザへと返却します
ユーザは結果を取得しみることができます

ユーザ選択型の暗号レベルについて

頻度情報による軸

データを暗号化したときに、元の平文のデータの頻度をどこまで秘匿するべきか、
という観点から、３つのレベルを提供することができます。

頻度情報は秘匿しない
頻度情報をある程度秘匿する
頻度情報を完全に秘匿する

この３パターンについてみていきます。
これらのパターンは一度理解すると結構単純なので大丈夫です。

頻度情報は秘匿しないパターン

頻度情報を秘匿しない時は、カラム毎にユニークな値を抽出し、
それをそのまま辞書へと登録します。

頻度情報をある程度秘匿するパターン

この「ある程度」という言葉は曖昧ですが、意味としてはユニークな値を取り出した後、
それを１対１で辞書へと登録するのではなく、複数のインデックスに対してカラムの値をまたがるように構成します。
例えば１つの値に対して、インデックスを１つだけ持たせるようにすれば、それは「頻度情報は秘匿しないパターン」と等しくなります。
また、１つの値に対して、その値が出現した数だけインデックスを持たせるようにすれば、それは後述の「頻度情報を完全に秘匿するパターン」と等しくなります。
このように、「ある程度秘匿するパターン」では、どのくらい秘匿したいかをパラメータで設定できるようにすることも可能です。

頻度情報を完全に秘匿するパターン

先ほどの「ある程度秘匿するパターン」において、１つの値に対して、その値が出現した数だけインデックスを持たせるようにすれば、
カラム内で同じ値であったとしても、保存される属性ベクトルの値はバラバラになりますから、頻度を完全に秘匿することができます。
しかしながら、これを実行した場合は辞書に含まれるレコード数は、カラムの中のデータ数と等しくなるため、エンクレーブ内に秘匿しておくべきデータの大きさが非常に大きくなることになります。

順序情報による軸

データを暗号化して保存するときに、暗号化後のデータの順序を秘匿するかどうか、という観点からもユーザの選択によってセキュリティレベルを変えることができます。
順序情報についても、頻度情報と同じように３段階のレベルで選択することができます。

順序情報を全く秘匿しないパターン
順序情報をある程度秘匿するパターン
順序情報を完全に秘匿するパターン

順序情報を全く秘匿しないパターン

この手法については、辞書を作成するときに、もともと平文を順番通りに並び替えておきます。
そうすることで、レンジクエリが発行されたとき、
例えば　where x > 1 and where x < 10
というようなレンジだったとすると、プロキシで１を暗号化、１０を暗号化し、エンクレーブへと送ります。
エンクレーブは、辞書を参照し、Enc(1), Enc(10) の結果を辞書で確認し、対応しているインデックスを２つ返却します。
DBMSはDBへとアクセスし、対象としているカラムの中の値が、この返却されたインデックスの間にあればデータを取得します。
この場合ですが、攻撃者はエンクレーブとDBMSの通信を傍受できますので、

どのようなインデックスの間を取得するようなクエリがよく打たれているかという情報
または直接DBをハッキングすれば、各カラムの値の大小自体を把握

することは可能となります。

順序情報をある程度秘匿するパターン

論文での提案手法では、辞書を先ほどの「順序情報を全く秘匿しないパターン」とほぼ同じように作るのですが、ランダムで回転(Rotation)を実行しておきます。
そうすることで、攻撃者がDBを直接ハッキングした際でも、そのまま順序を盗み出すことはできません。
また、レンジクエリが発行された時は、エンクレーブが辞書を参照し、そのレンジに含まれるインデックスをDBMS側に返却することで、
DBMSはDBから対応するデータを取得することができます。

順序情報を完全に秘匿するパターン

順序情報を完全に秘匿する時は、辞書を作成するときに前もって値をランダムにシャッフルしておきます。
こうすることで、攻撃者がDBを盗み見ることができたとしても、その情報からカラムの中のデータの順序を類推することは不可能です。
レンジクエリが飛んできたときは、エンクレーブが辞書を参照し、どのインデックスがそのレンジクエリに対応しているのかを取得し、
対応するインデックスをDBMSへと返却します。DBMSは対応インデックスに対応したカラムデータを取得し、それをプロキシへと返却、プロキシが復号処理を行い平文データをユーザへと返却します。

各暗号化手法の選択とセキュリティの対応

前述した

頻度情報
順序情報

のそれぞれの秘匿レベルを決めることで、ED1 ~ ED9 までの暗号スキームを選択することが可能であり、それをテーブルで表したものは以下となります。

また、これらのそれぞれのスキームに対するセキュリティレベルの対応表が以下となります。
E4~E6については、E1~E3とE7~E9の間に位置することから、連続関数的にセキュリティレベルが変化するため、省略されています。

EncDBDBのパフォーマンス

頻度を秘匿しないE1~E3と、ある程度秘匿するE4~E6, 完全秘匿するE7~E8 について、
データサイズをどれだけ圧縮できるかが変わってきます。
論文では、実際にSAP HANAで使用されているリアルワールドのデータセット（１億６千万件）を使い、どのようにデータサイズが変化するかを表にしています。
ここで、

C1カラムはカラムの中のユニーク数が７００万程度ある
C2カラムはカラムの中のユニーク数が１万程度のもの

のような対照的なC1とC2をそれぞれ選び測定してあります。

ここで、E4~E6については、モジュラー（関数）を支配しているbsという変数を変化させることで、データの圧縮度を変化させて測定しています。（bs=100の時は全く秘匿しないパターンと等価になり、bs=0のときは完全に秘匿するパターンと投下することを言及しておきます。）

ストレージのパフォーマンス

頻度を秘匿しないE1~E3のパターンだと、ナイーブに平文をDBに格納するよりも、
今回のEncDBDBがもつデータ容量の方が少なく済んでいることがわかります。
この点がまさにカラム指向型のデータベースを構築して、辞書エンコーディングを使用する時の強みであることがわかりますね。

速度のパフォーマンス

詳しくは論文の6.3章をご覧ください。C1、C2に対して、E1〜E9までの異なるセキュリティレベルで暗号化したものに対して
レンジクエリを実行し、MonetDB,また、EncDBDBと同じ構成で暗号化を一切行っていないPlainDBDBとの比較がまとめられています。

各秘匿DBのまとめとEncDBDBとの比較

TEEベースのデータベース

Haven
Scone
EnclaveDB

は、既存のDBMSのコードやDBそのものを全てTEEに載せようとするアプリケーションです。
このようなアプローチだと、TEEの中で実行されるコードが何十万行、何百万行を超える巨大なコードベースとなり、
そのような巨大なコードベースをTEEで走らせることはセキュリティ上推奨されていません。
また、そのような巨大なTEEを用意することも現実的に厳しいものとなります。

EnclaveDB はEnclave の中にデータなどを全て入れる構成。HavenやScone よりはコードベースの大きさなどが改善されています。
EnclaveにDBをそのまま実装するのと等しいので、LOC（コードベースのプログラム行数が２３万件以上になり、巨大）
パフォーマンスは２０パーセント程度のオーバーヘッドとなっています。

ObliDB

ObliDB はOlibiviousRAMという技術を使用した秘匿型DBです。

ユーザがクエリを発行した時のメモリアクセスを、その都度シャッフルすることでデータ構造を秘匿できるように工夫する技術が
OlibiviousRAMと呼ばれる。
この時、クライアント側に存在するObliviousクライアントを実装すると、

クライアント側で実行するべきプログラムが巨大になる(そもそもクラウドに処理をオフロードしたいという目的に反してしまう）
クライアントとサーバでの通信が巨大になる
という問題が発生する。
このとき、ObliviousクライアントをTEE内に設置することで、この問題の２つ目（通信）については解決できる（インターネットにはデータがのらない、あくまでもエンクレーブとホストの間の通信に置き換わる）。
また、ユーザの手元で行われていた処理が大きくクラウド側にオフロードできるので、元々の目的も達成される
ので、それを目的にしている。
しかしながら、パフォーマンスとしては大きなオーバーヘッドがかかってくる（２００パーセント以上）
TrustedDB
Cipherbase
StealthDB

これらはそれぞれ　Co-Processor, FPGA, SGX をTEEとして利用しており、
コードベースとしてはかなり小さい構成になっています。
しかしながら、攻撃者がそれぞれのオペレーションの結果を知ることができるので、流出するデータが多い、と言及されています。

ソフトウェアベースのデータベース

CryptDB
Monomi

などがよく知られたソリューションです。
これらは様々な暗号スキームを使用してレンジクエリを可能にしたり（順序保存暗号）、
SUMを取ったり（準同型暗号）していますが、データサイズのオーバーヘッドが無視できないハードルになっています。
また、何かの情報を保存した暗号（例えば順序保存暗号など）に知られている攻撃手法の存在についても、研究者から指摘があっています。

Operon: An Encrypted Database for Ownership-Preserving　Data Management

要点を箇条書き

Ownership Preserving Database (OPDB) のコンセプトの提案
OPDBの構成においてTEEを利用
OPDBの構成においてBCL(Behaviour Control List) を提案
Alibaba Cloud 上で使用できるPolarDB(https://www.alibabacloud.com/ja/product/polardb) やPostgreSQLにOPDBを実装
平文データベースと比べて71~97%の速度でのパフォーマンスを達成できることを検証

背景と現在のDBの問題点

DBはプライベートドメインに設置され、システムオーナー（管理者権限を持つユーザ）はDBに対してフルアクセスが可能
現在の暗号化DBについて、基本的な考え方は認証されたエンドポイント（例えば鍵を持ったプロキシや、システム権限を持ったユーザ）は、直接データベースにアクセスし、データに触れることができる。
この点において、データオーナーとデータを実際に触るデータ操作者が異なり、データ操作者は認証されたエンドポイントとなり、データに直接触れることが実質的に可能

この論文を通して、EncDBDBとは違い、まずは Ownership Preserving Database (OPDB)のコンセプトについて詳しく定義されていました。
実際のシステムを考えてみると、私はこのDBの構成に対してとても共感することができました。
OPDBについてどのようなコンセプトのもとで提唱されているものなのか、ということについてより詳しくまとめていければと思います。

OPDBとは何なのか

OPDBのコンセプトの元で、大前提として、

データは常に暗号化
データオーナーのみが暗号データを復号できる
データを操作する人は、そのオペレーションに対してデータオーナーの許可を受け、その処理をするために必要な暗号データへのアクセス権限を得る（もちろん復号権限はない）

という点が今までのデータベースセキュリティと異なっています。

これがどういうことかというと、

今までシステムベースでリソースに対してアクセスコントロールしていた（データベースのアクセス権限を持っていなければデータにアクセスできない）
ものを、データに対する操作ベースでアクセスコントロールを実装し、
データオーナーとシステムオーナーを明確に切り分けた設計をするということです。

この時の操作ベースで管理されるアクセスコントロールは、
Behavior Control List(BCL)を作ることで達成されます。

OPDBがもつプリンシプル

前述したポイントの繰り返しになるかもしれませんが、論文で強調されているこのOPDBのある意味「思想」にあたるところなので、
論文での3.1.1の項をまとめておきます。

プリンシプル１. データを操作するエンティティは、データオーナーの認証がない限り暗号化されたデータへのアクセスができない

これは、大前提として、データはいかなるエンティティの元に渡される前に、データオーナーのみがアクセスできる鍵で暗号化されるということを意味します。

プリンシプル２. データを操作するエンティティはデータオーナーの許可なしに暗号データについて演算や分析を加えることができない

これはデータオーナーとアプリケーションロジックを完全に切り分けることを意味します。

プリンシプル３. データを操作するエンティティは、データにたいしていかなる情報を知ろうとする時、データオーナーが許可したオペレーションからのみしか情報を得ることができない

これは２とかなり近いルールのように感じますが、少し異なるのは、２がデータの分析結果を得ようとする分析であるのに対し、
このルールは、データ自体の構造（例えばデータ間の順序情報とか）を、データオーナーが許可したオペレーション以外からは得ることが許されない、という意味です。
3.1.2にも続くように、この３でデータを操作するエンティティが得る情報は measure とここで定義され、
データオーナーは、このmeasure について、データ操作者に情報を公開することを許可します。
この情報はこのアプリケーションを構築する上において不可欠なもので、限られたエンティティに対してのみ公開されるように共有されまうs。

言い換えると、OPDBは以下のようなルールを明確化しています。

データオーナーがデータの閲覧権限、操作権限、それらの権限移譲をする能力を持ち、いつ何時でも自分のデータに対して主権を持っている。

OPDBの概念で登場する３つの役割

３つの役割を持った登場人物について詳しく見ます。

人物１. データオーナー

データの保有者であり、このデータを安全に活用することでビジネスに役立てることを目的としている。
データへのアクセス権限、操作に対する権限を管理できる人物

人物２. データ操作者

データーオーナーと共同で、もしくは単体で、データ活用のサービスをソフトウェアとして提供し、データ活用のためのデータ操作について設計する人物

人物３. データプロセッサー

データをデータ操作者に代わって実際に操作する人。インフラのプロバイダーと考えて良い。
この場合、OPDBのシステムを構成している人物。

この３つの役割を持つ人物をシステムにどう配置し、
３つのプリンシプルに沿って運用するためのインフラ基盤がOPDBというわけです。

実際の構成については画像を添付するにとどめたいと思います。

最後まで論文を読み込めればまたアップデートしたいと思います。

少なくとも、このOPDBコンセプト自体は実際のシステム構築においてとても有益なルールであり、
どのオペレーションでどのような情報をデータ操作者が知ることになり、そのリスクはどうなのか、
ということをきちんと明文化してシステム構築することが必要であり、そのためのTEEであり、BCLである
ということを理解しました。

まとめ

今回はTEEを使ったデータベースソリューションについて調べるためにいくつか論文を読み漁ってまとめようとしてみました。
最終的にはしっくりきた２つの

EncDBDB
Operon

について概要をまとめました。
EncDBDBについては詳細にまとめましたが、Operonについては概念的なところまでまとめるところで一旦区切りとしました。

今後アップデートできればと思います。

もしOPDBのようなコンセプトをベースに、どのようなシステム構成でセキュリティを担保したデータ活用プラットフォームにすればいいか、
ということが議論できればとても有意義になると思いましたので、こちらで紹介させていただきました。

これからもキャッチアップしていきたいと思います。

今回はこの辺で。

@kenmaro

主なコントリビューション

参考文献

https://arxiv.org/pdf/2002.05097.pdf
https://www.vldb.org/pvldb/vol15/p3332-wang.pdf