DEIM Forum 2013 E1-1

暗号化ストリームデータ処理における効率的な暗号化鍵更新手法
冨山

克裕†

川島

英之††

北川 博之††† 筑波大学大学院システム情報工学研究科〒 305–8577 茨城県つくば市天王台 1–1–1†† 筑波大学システム情報系 〒 305–8577 茨城県つくば市天王台 1–1–1
E-mail: †tomi@kde.cs.tsukuba.ac.jp, ††{kawasima,kitagawa}@cs.tsukuba.ac.jp
あらまし 近年，増大しつつあるストリームデータを処理する基盤システムとして，ストリーム処理エンジン（SPE）
が開発されている．数千〜数万のストリーム情報源に対して処理を行うためには，SPE には非常に高い演算処理能力が要求される．このような処理の実行にはパブリッククラウドなどの分散並列処理基盤を用いることが有効であると考えられる．しかし，パブリッククラウドは一般に組織のファイアウォールの外側で第三者により管理されるため，
パブリッククラウド上の情報に対して機密性を保持することができない．これに対し我々は，安全性を考慮したスト
リームデータ処理の実現を目的として暗号化ストリームデータ処理方式の研究を行っている．本稿では，暗号化スト
リームデータ処理においてクエリ実行を停止することなく効率的に暗号化鍵を更新するための手法を提案する．
キーワード

ストリームデータ処理，リレーショナル演算，暗号化，セキュリティ，パブリッククラウド

Katsuhiro TOMIYAMA† , Hideyuki KAWASHIMA†† , and Hiroyuki KITAGAWA††† Graduate School of Systems and Information Engineering, University of Tsukuba
1–1–1, Tennodai, Tsukuba, Ibaraki, 305–8577 Japan†† Faculty of Engineering, Information and Systems, University of Tsukuba
1–1–1, Tennodai, Tsukuba, Ibaraki, 305–8577 Japan
E-mail: †tomi@kde.cs.tsukuba.ac.jp, ††{kawasima,kitagawa}@cs.tsukuba.ac.jp

1. は じ め に
近年のセンシングデバイスの発達に伴い，継続的にデータをストリームデータメモリ生成し続けるストリーム情報源の数が増大しつつある．具体的

メモリ

問合せ
処理

なストリーム情報源の例として，監視カメラ，ルータを流れる
ネットワークパケット，株価・為替変動などの金融情報，GPS

ストリームデータ

ディスク

問合せ
処理

ディスク

端末をはじめとする各種センシングデバイスなどが挙げられる．
これらの情報源から得られるデータをストリームデータと呼び，

データベース

データベースDBMS

ストリームデータ処理

ストリームデータを処理する基盤システムとして，ストリーム
処理エンジン（SPE: Stream Processing Engine）がこれまで開発されてきた [2] [5]．

図 1 DBMS とストリームデータ処理の違い

ストリーム処理エンジンとは，ストリーム情報源から無限に到着するストリームデータに対して連続的問合せを行うことを可能にするシステムである．連続的問合せとして，選択・射影・結合・集約などの関係演算や複合イベント処理を行うことができる．この問合せは SQL ライクの言語を用いて記述することができ，データが到着する度に評価が行われる．また，メモリ上で即時的に実行されるため，データ永続化を必要とする従来のデータベース管理システム（DBMS）に比べ，処理を高速化できる．従来のデータベース管理システムとストリーム処理との違いを，図 1 に示す．従来の DBMS では，まず，到着した
ストリームを二次記憶に格納してから，必要に応じて主記憶上にロードして問合せ処理を行う．一方ストリームデータ処理では，到着したストリームは主記憶上で即時的に問合せ処理が行われ，必要に応じて二次記憶に格納をする．
一方，ストリームデータなどのビックデータに対する処理環境を提供するための技術として，近年パブリッククラウドが注効率的な暗号化鍵更新手順の提案
復号モジュール

結果

パブリッククラウド(Untrusted area)

結果

暗号化ストリームデータ処理システムにおいて長時間にわたり同一の暗号化鍵が用いられていると，攻撃者に暗号化鍵を破られるリスクが高まる [1]．よって，一定時間ごとに鍵の更新が行われることが望ましいと考えられる．しかし，クエリ実行中にストリーム処理エンジン（SPE）

Trusted area

鍵を更新すると，処理木中にそれぞれ異なる二つの鍵で暗号化された暗号値が混在することとなり，正しい演算を行うことが暗号化モジュール

暗号化モジュール

暗号化モジュール

できなくなる．そこで本稿では “鍵の移行期間” という概念を導入し，クエリの実行を停めることなく段階的に鍵を更新し，その上で，鍵の更新が完了するまでの時間，及び鍵の更新に伴Trusted area

Trusted area

Trusted area

図 2 提案するアーキテクチャの俯瞰図

う計算資源のオーバーヘッド（SPE のメモリ使用量，及び各モ
ジュールの計算コストのオーバーヘッド）を準最適化するための手法について提案を行う．

目を浴びつつある．パブリッククラウドとは，インターネット

本稿の以降の構成は以下の通りである．第 2 章では関連研究を介して不特定多数の個人または企業に対して計算資源を提供として，従来の DBMS 上で暗号化されたデータに対して関係するサービスを指す．ユーザーは，計算資源を自前で持つ場合演算を実現する CryptDB の紹介を行う．次に第 3 章で我々がに比べて運用・維持コストの削減や，資源の柔軟な増減が可能研究を行っている暗号化ストリームデータ処理方式について紹になる．具体的なパブリッククラウドの例として，Amazon に介し，その課題について述べる．第 4 章では，これまでに研究よる Amazon EC2，Microsoft による Windows Azure などがとして行ってきた，これらの課題に対する効率化手法について挙げられる．パブリッククラウドはその優れたコストと利便性

手短に述べる．第 5 章では，新たに，暗号化ストリームデータ

により，現在急成長を遂げている．しかしその一方，ユーザは処理における効率的な暗号化鍵更新手法について提案を行う．

パブリッククラウドに対してセキュリティに関する懸念を抱い

最後にまとめと今後の課題を第 6 章に述べる．

ている [4]．パブリッククラウドは一般に，ユーザである企業な
どのファイアウォールの外側で第三者により管理される．その2. 関 連 研 究ため，パブリッククラウド上に保存された情報を，パブリック

2. 1 CryptDB

クラウド管理者を含む第三者よって覗き見られたり改ざんされ

2. 1. 1 概要

CryptDB は，R. A. Popa ら [9] によって提案された手法である可能性が否定できない．
この問題に対する解決するための手段として，近年，DBMS

る．CryptDB におけるシステムのアーキテクチャを図 3 に示

上で暗号化されたデータに対して関係演算を実現するための研す．DBMS サーバとクライアントの間にデータベースプロキシ究が行われている．CryptDB [9] や POP [7] などがその一例で（database proxy）と呼ばれるモジュールを置き，DBMS に保ある．

存するデータの暗号化やクエリの書換え，またクエリ結果の復我々は安全性を考慮したストリームデータ処理の実現を目的

号などを行う．一般に，暗号化された値に対してすべての関係

として暗号化ストリームデータ処理方式について研究を行って演算を可能とする暗号化アルゴリズムは存在しない．CryptDBいる．本稿では，これまでの研究で行ってきた，暗号化データ

では，暗号化された値に対して選択・射影・結合・集約のいず

ストリームを扱う上で課題となるデータ量増大に対処するため

れかの演算を行うことのできる暗号化アルゴリズムを複合的にの二つの効率化手法について手短に紹介を行う．その後で，新用い，一つの平文値に対し複数の暗号値を作成する．与えられたに，実行中のクエリを停めることなく暗号化鍵を更新するた

たクエリに応じてこれらの暗号値を使い分けることで，暗号化めの手法について提案を行う．我々が研究を行っている暗号化された値に対する関係演算を実現する．CryptDB が必要とす

ストリームデータ処理方式のアーキテクチャの俯瞰図を図 2 にる暗号化アルゴリズムの特徴を次節に示す．

2. 1. 2 用いる暗号の特徴

示す．
（注 1）

ストリームデータは trusted area

で暗号化され，復号さDeterministic（DET）:

DET は暗号化された二つの値れることなく untrusted area に存在するパブリッククラウド（数値や文字列など）に対し，等価性を確認することができる特で処理される．パブリッククラウド上でデータは一切復号され徴を持つ．これにより，条件式に等式を持つ選択演算や結合演ないため，悪意ある攻撃からデータを守ることが可能になると算，グルーピングや COUNT 句，DISTINCT 句などの命令を考えられる．クエリ処理の結果は，ユーザが存在する trusted

暗号値に対して実行することができる．DET に用いる具体的

area へ送られ復号される．以下に，本稿における我々の提案をな暗号化アルゴリズムとしては，AES 暗号（CMC モード [6]）簡潔に示す．

が挙げられる．二つの暗号値が等しければ対応する平文値が等しいことがわかるために，安全性は RND よりも若干劣ると言（注 1）：本稿では，trusted area はあらゆる攻撃から保護された安全な領域のことを指し，untrusted area は攻撃され得る領域のことを指す．

える．DET が満たす式を以下に示す．

暗号化されたデータを保存

DBMS

C1-IV

C1-Eq

IVC1

RND(DET(
JOIN(3)))

Untrusted area

暗号化ストリームデータに対して関係演算を実行

パブリッククラウド

ストリーム処理エンジン
（SPE）
SPE）

SUM_HOM
HOM(300)

Untrusted area
Trusted area

Database Proxy

id_DET

id_OPE

id_HOM val_DET val_OPE val_HOM

データやクエリの暗号化・復号を行う

DET(3)

OPE(3)

HOM(3) DET(50) OPE(50) HOM(50)

SELECT id
FROM table
WHERE val = 50

クライアントは，データが暗号化されていることを気にせずにクエリを記述可能

暗号化モジュール

Client

id

val

3

50

クエリ変換器

復号モジュール

SUM
300

SELECT SUM(val)
FROM sensor[RANGE 1 sec]

図 3 CryptDB のシステムアーキテクチャ
センサは継続的にデータを生成SensorClientTrusted area

Trusted areax = y ⇐⇒ DETK (x) = DETK (y)図 4 暗号化ストリームデータ処理方式のアーキテクチャ

Order-Preserving Encryption（OPE）: OPE は暗号化された 2 つの値（数値）に対し，不等性を確認することがで

Algorithm 1 Encryption Procedure

きる特徴を持つ．OPE を用いることにより，レンジクエリや

1: Receive the name of stream from a client.

ORDER BY 句，MIN 句，MAX 句，SORT 句などの命令を

2: Send ack to the client.

暗号値に対して実行することができる．OPE に用いる具体的な暗号化アルゴリズムとしては，Boldyreva ら [3] により提案

3: Search schema of the stream from metadata DB. (registeredin advance)
4: for i = 0 to the number of attributes do

されたアルゴリズムが挙げられる．値が暗号化された状態でも5:Make DET cipher.

二つの値の大小関係を露わにしてしまうため，安全性は DET

6:

if the type of attributei is integer thenよりも劣ると言える．OPE が満たす式を以下に示す．

7:x < y ⇒ OP EK (x) < OP EK (y)Homomorphic Encryption（HOM）: HOM は暗号化

Make OPE & HOM ciphers.

8:

end if9:

Insert cipher(s) to a buﬀer.

10: end for

された二つの値（数値）の和を求めることができる特徴を持つ．

11: Send ciphers in the buﬀer to SPE.

加法準同型暗号である Paillier 暗号 [8] を用い，以下の式を満12: Receive ack from SPE.

たす．

Algorithm 2 Decryption Procedure
HOMK (x) · HOMK (y) = HOMK (x + y)

1: Receive the query name from SPE.
2: Send ack to SPE.

3. 暗号化ストリームデータ処理方式

3: Search schema of the result tuple from metadata DB. (regis-

我々は前章で示した CryptDB の考え方を参考にして，暗号

4: Receive result tuples from SPE.

tered in advance)

化ストリームデータ処理方式について研究を行っている [10]．

5: for i = 0 to the number of attributes do

暗号化ストリームデータ処理方式のアーキテクチャを図 4 に示

6:す．本方式では，ストリーム処理エンジン（SPE）はパブリッ

7:

ククラウドなどの untrusted area に設置することを想定する．

8:

また，ストリームデータの暗号化を行うための “暗号化モジュー
ル（encryption module）” はストリーム情報源の存在する各

9:
10:
11:

if encryption type of attributei is DET. then
Decrypt a cipher using DET algorithm.
else if encryption type of attributei is OPE. then
Decrypt a cipher using OPE algorithm.
else if encryption type of attributei is HOM. then
Decrypt a cipher using HOM algorithm.

trusted area に，クエリ結果の復号を行うための “復号モジュー

12:

end ifル（decryption module）” は各ユーザの存在する trusted area

13:

Insert a plain value to a buﬀer.

にそれぞれ設置する．

14: end for

このアーキテクチャの下では暗号化されたデータのみが un-trusted area にある SPE へと送られるため，untrusted area

15: Send data in the buﬀer to client.
16: Receive ack from client.

におけるのぞき見（snooping）などの攻撃からデータを守ることが可能になる．また，SPE 上でデータが暗号化された状態では実行することのできない処理は，復号モジュールで復号された後に実行する．これを post-processing と呼ぶ．

3. 1 CryptDB との相違点
我々の 手 法 は ス ト リ ー ム デ ー タ 処 理 を 対 象 と す る 点 でCryptDB とは決定的に異なる．CryptDB はデータベースプロ

暗号化モジュールにおける暗号化のためのアルゴリズムをキシ（database proxy）と呼ばれる単一のモジュールによってAlgorithm 1 に，復号モジュールにおける復号のためのアルゴ

暗号化及び復号を実現している．しかし一般的に情報源とユーリズムを Algorithm 2 にそれぞれ示す．

ザとが広範囲に分散しているストリームデータ処理において，

このようなスキームが適用できるケースは極めて稀であると言表 1 各演算子が必要とする暗号の種類

える．そのため，我々の手法では暗号化及び復号を行うためのOperator Type

それぞれ独立したモジュールを用意する．

Equality-selection

3. 2 暗号化鍵の管理
DET として用 い る AES 暗号，及 び OPE として用いる
Boldyreva ら [3] により提案された暗号化アルゴリズムは共通σπ1

鍵暗号である．また，HOM として用いる Paillier 暗号は公開鍵暗号である．そのため本稿で提案する暗号化ストリームデー
タ処理方式においては，事前に各暗号化モジュールや復号モ××

θ-selection
Projection
Equality-join

××θ-join×

Summation
α

×

Count
×

Minimum×

Maximum

ジュール，及びクエリ変換器の間で，暗号化及び復号に必要な鍵を共有しておく必要がある．具体的には，DET 及び OPE に

DET OPE HOM

γGroup by×

ついては各モジュール間で共通鍵を共有し，HOM については
各暗号化モジュール間で秘密鍵を，各復号モジュール間で公開により暗号化ストリームデータ処理システム全体のスループッ

鍵をそれぞれ共有しておく必要がある．本稿では，各モジュー

トを約 5.7〜5.9 倍に改善できることを確認できた（注 2）．

ルは安全な経路を用いて事前にこれらの鍵を共有しているもの

4. 2 効率化手法 II：SPE のメモリ使用量の削減と仮定し，効率的に鍵を更新するための手順については第 5 章

前述した効率化手法 I は，暗号化モジュール内部，及び暗号化モジュールから SPE までの経路において暗号化コストとデーに述べる．

3. 3 本方式における課題

タ転送量を削減する手法であった．一方，効率化手法 II は SPE

前述したとおり，暗号化モジュールは入力されたタプルの各内部でのメモリ使用量を削減する．

属性に対して 3 種類（DET・OPE・HOM）の暗号値を生成す

SPE 上で結合演算や集約演算のようなステートフル演算子

る．そのため，暗号化されたタプルのデータ量の合計は平文タ

は，シノプシスの中に一時的にタプルを保持する．これらのタ

プルのデータ量に対して数倍に増加することが考えられる．以プルの中には以降の演算子に要求されない暗号値も含まれてい上より，我々の手法では，以下に示す二つの問題点が生じる．

る可能性があり，このような暗号値をシノプシスに保持してお本方式では，平文タプルの各

くことは，明らかにメモリ使用量の浪費に繋がる．そこで本手属性に対してそれぞれ 3 種類の暗号値が生成される．また，一法では，これらの演算子の前に射影演算子を挿入することによ

般に暗号値は平文値よりも大きい．ゆえに，SPE に転送される

り，その後の処理に必要のない暗号値を適宜取り除いていくこ

データ量の合計は平文に対して 3 倍以上の大きさになると考えとで SPE のメモリ使用量の削減を図る．評価実験の結果，効率られ，通信帯域を圧迫してしまう．

化手法 I ではデータ量を削減できないようなクエリに対して本

課題 1: タプルサイズの増大:

課題 2: SPE のメモリ消費量の増加:

課題 1 と同様の理由

により，SPE 上の処理木の各シノプシスに暗号化タプルが貯まることで，平文で同様のクエリ処理を行う場合に比べて SPEのメモリ使用量が増加してしまうと考えられる．
これらの問題に対処するために，我々はこれまでに効率化手法について研究を行ってきた．概要を次章に述べる．

4. データ量削減のための効率化手法

手法を適用することにより，SPE のメモリ使用量を約 98.5%削減できることを確認できた（注 2）．

5. 暗号化ストリームデータ処理システムにおける暗号化鍵更新手順の提案
我々がこれまでに提案を行ってきた暗号化ストリームデータ
処理方式は，暗号化モジュール，復号モジュール，及びクエリ変換器がクエリ実行前に暗号化及び復号に必要な鍵を共有する

前章で示した課題に対して，我々はこれまでに二つの効率化ことを前提とし，その後の鍵の更新については論じてこなかっ手法を提案してきた [10]．本稿ではページの都合上，これらのた．しかしながら，広範囲に分散しているストリーム情報源を手法及び評価実験について手短に紹介する．

対象とする我々の想定の下では，クエリ実行中に処理対象のス

4. 1 効率化手法 I：データ転送量の削減

トリーム情報源が追加・削除されることも考えられるため，長ストリームデータ処理では従来の DBMS と異なり，クエリ

期にわたり同一の鍵を使い続けることは鍵の漏えいのリスクには事前に SPE に登録されている．よって，クエリを実行前に繋がると考えられる．またそれだけでなく，長期にわたり同一解析することで，クエリを実行するために必要な暗号の種類をの鍵を使い続けることは，攻撃者が鍵を発見しデータの解読を判断することができる．各演算子と，その演算子が必要とする可能にするまでの試行時間を延ばすことにも繋がる [1]．以上の暗号の種類を表 1 に示す．

理由から，鍵は一定期間ごとに更新し安全性を維持することが効率化手法 I では，クエリを実行前に解析することでクエリ処理に必要な暗号の種類を判断し，それらを暗号化モジュールに告知する．これにより，暗号化モジュールは必要最小限の暗号のみを生成し，暗号化に要するコストの削減と，SPE へ転送されるデータ量の削減を図る．評価実験の結果，本手法の適用必要であると考えられる．
そこで本章では，暗号化ストリームデータ処理方式における（注 2）：これらの結果は，CloudDB’12 において我々が発表した論文 [10] と同様の効率化手法を，実装及び実験環境を改善して再実験した結果であり，論文 [10]に掲載した結果とは異なる点に注意されたい．

効率的な暗号化鍵更新手法について提案を行う．一般に，ストへ送信する．このようなタプルを本稿では “ペアタプル” と呼リームデータ処理は逐次的に発信されるデータに対して継続的

ぶ．移行期間を用いて段階的に鍵を更新していく様子を図 5 ににクエリ処理を行うことができることが利点であり，鍵の更新示す．移行期間が一定時間継続することで，処理木のキュー及を行うためにクエリの実行を停止するのは望ましくない．しかびシノプシス中に存在するすべてのタプルがペアタプルで満たし一方で，クエリ実行中に鍵を更新し，暗号化モジュールが新される．すなわち，古い鍵（K1 ）で作られた暗号値のみを用いしい鍵のみを用いて暗号化タプルを生成した場合，SPE 上で実てクエリ処理を行っても，新しい鍵（K2 ）で作られた暗号値の行中の処理木中に新旧それぞれの鍵で暗号化された暗号値が混みを用いてクエリ処理を行っても，復号を行った時に同一の結在することとなり，正しいクエリ処理を行うことができなくな果を得ることができるようになる．このような状態になった後る．そこで本章では，“鍵の移行期間” という概念を導入するこに移行期間を終了し，暗号化モジュールはペアタプルの送信をとにより，クエリの実行を停止せずに鍵を更新するための手法

終えて，入力された平文タプルを新しい鍵（K2 ）のみで暗号を提案する．また，鍵の更新が完了するまでの時間，及び鍵の化し SPE へ送信する．同時に，SPE 中の各演算子は新しい鍵更新に伴う SPE のメモリ使用量や各モジュールの計算コスト（K2 ）で作られた暗号値のみを用いてクエリ処理を行う．移行のオーバーヘッドを抑えるための効率化手法について述べる．

期間が終了した直後は処理木中にペアタプルが残存しているが，

5. 1 評 価 要 素

入力されるタプルは新しい鍵（K2 ）で暗号化された暗号値のみ

効率的な鍵の更新を実現するに当たり，本章では以下に示すを持ち，また各演算子も新しい鍵（K2 ）で暗号化された暗号値

三つの評価要素を考える．

のみを用いてクエリ処理を行うことから，時間の経過とともに（1）システム停止時間

ペアタプルは消滅する．

SPE に登録されているクエリ中の条件文に含まれる暗号値，処

このように移行期間を設け，一時的に生成する暗号値を二重理木中（キュー及びシノプシス）に存在しているすべてのタプ

化することにより，クエリの実行を停止せずに鍵の更新を実現

ル，及び各モジュールの持つ鍵のそれぞれを更新するために，することができる．すなわち，前節に述べた評価要素のうち，クエリの実行を停止する時間のことを指す．前述したとおり，

システム停止時間を最適化することが可能となる．

ストリームデータ処理は逐次的に発信されるデータに対して継続的にクエリ処理を行うことができることが利点であるため，
システム停止時間は小さい方が望ましいと言える．
（2）鍵の切り替えに要する時間

ts

te

処理木の中から，
ts以前に作られたタプルが無くなることを保証．

時刻
鍵K1
鍵K2

移行期間直後はペアタプルが残存しているが，時間とともに消滅してゆく．

移行期間
ResultResultResultResult

α α

α α

α α

α α

Tuple

Tuple

Tuple

Tuple

Tuple

Tuple

Tuple

古い鍵から新しい鍵に切り替えるために要する時間を指す．前
述したとおり，古い鍵を使い続けることはいくつかのリスクが存在することから，鍵の切り替えに要する時間は小さい方が望ましいと言える．

Tuple

Tuple

Tuple

（3）計算資源のオーバーヘッド
通常のクエリ処理とは別に発生する，鍵の更新に係る SPE のメモリ使用量のオーバーヘッド，及び各モジュールの計算コス
トのオーバーヘッドを指し，小さい方が望ましいと言える．
我々はこれら三つの評価要素のうち，システム停止時間を最適化し，その上で鍵の切り替えに要する時間と計算資源のオー
バーヘッドを準最適化するような効率化暗号化鍵更新手法を提案する．

5. 2 提 案 手 法
5. 2. 1 暗号化鍵の移行期間
暗号化鍵の移行期間とは，実行中の暗号化ストリームデータ
処理システムにおいて，クエリ処理に用いる鍵を古い鍵（K1 ）から新しい鍵（K2 ）に更新するために要する期間のことを指す．前述したとおり，クエリ実行中のある時刻に一斉に鍵を切り替える（すなわち，移行期間の長さを 0 とする）と，SPE 上
で実行中の処理木中に古い鍵（K1 ）で暗号化された暗号値のみを持つタプルと，新しい鍵（K2 ）で暗号化された暗号値のみを持つタプルが混在し，正しいクエリ処理を行うことができなくなる．そこで移行期間を設け，移行期間中に暗号化モジュールに入力された平文タプルは古い鍵（K1 ）と新しい鍵（K2 ）のそれぞれで暗号化を行い，両方の暗号値を含むタプルを SPE

図 5 鍵の移行ステップ

図 5 において，移行期間の開始時刻を時刻 ts ，終了時刻を
時刻 te と表す．ここで移行期間の終了時刻 te は，処理木中に存在しているすべてのタプルが時刻 ts 以降に生成されたもの，
すなわちペアタプルであることを保証できるような時刻にしなければならない．なぜなら，時刻 te 以降，SPE は新しい鍵（K2 ）で作られた暗号値のみを用いてクエリ処理を行い，古い鍵（K1 ）で作られた暗号値は無視されるため，正しいクエリ結果を得るためには少なくとも新しい鍵（K2 ）で作られた暗号値が必要となるからである．
本章では，処理木中のすべてのステートフル演算子は時間幅で指定されたシノプシスを持つことを前提とする．このとき，処理木を解析することにより移行期間の長さ（te − ts ）を事前に見積もることが可能となる．しかしながら，各暗号化モジュールで暗号化されたタプルは，SPE に到着するまでの間に通信による遅延が生じる．また，SPE 内部においても処理遅延が発生すると考えられる．ゆえに，実際には通信及び処理遅延を考慮し，移行期間の終了時刻 te を動的に変更できるような機構が必要となる．次節で，これらの遅延を考慮した暗号化鍵更新アルゴリズムについて述べる．

Algorithm 3 Estimating Oﬀset of Synopsis

5. 2. 2 オフセット時間の見積もり

1: Receive a continuous query from a client;

前節に示した移行期間の間，SPE 上で実行中の処理木には

2: Translate the query to a plan tree;

葉ノードから順にペアタプル（古い鍵（K1 ）と新しい鍵（K2 ）による両方の暗号値を含むタプル）が貯まっていく．処理木中の各ステートフル演算子は，自身のシノプシスがペアタプルで

3: Merge it to other plan trees when possible;
4: for all nodei ∈ nodes doCreate all of paths which show routes from nodei to leaves

5:in the plan tree;

満たされるまでは古い鍵（K1 ）で作られた暗号値に対して演算

6:

Oﬀseti ← 0;を行う．その後，自身のシノプシスがペアタプルで満たされた

7:

for all pathj ∈ paths do

時刻から，古い鍵（K1 ）と新しい鍵（K2 ）で作られた暗号値

8:

TotalSize ← 0;のそれぞれに対して演算を行う．ステートフル演算子 OPn の9:for p ← nodei ; p =| leaf node; p ← p’s child node do

シノプシスがペアタプルで満たされる時刻を，時刻 tfn と表す．

10:

また，それぞれのステートフル演算子 OPn について，移行期

11:間の開始時刻 ts から時刻 tfn までの時間を “オフセット時間”

if p is a stateful operator thenTotalSize ← TotalSize + Size of synopsis of the operator;

12:

end if13:

end for

それぞれのステートフル演算子のシノプシスにペアタプルが

14:

if TotalSize > Oﬀseti then

流入してくるのは，それらの子孫にあたるステートフル演算子

15:が時刻 tfn 達して，古い鍵（K1 ）と新しい鍵（K2 ）で作られ

16:

end ifた暗号値のそれぞれに対して演算を行うようになった後である．

17:

end for

よって，処理木の根に近いステートフル演算子の方が，葉に近18: end forと呼び of f setn と表す．

Oﬀseti ← TotalSize;

いステートフル演算子よりもオフセット時間が長くなる．処
移行期間開始理木中の各演算子を，根ノードに位置するものから順に OP0 ，

offset1

OP1 ，OP2 ，· · · とするとき，ステートフル演算子 OPn におけOP1るオフセット時間 Of f setn は下式のように表すことができる．

OP2

移行期間終了

tf2

tf1

ts

offset2

offset3

i=0

d

…

OP3

…

とする．


n=0

 Range0 ,n−1∑
Of f setn =Of f seti + Rangen , n > 0


te

d

ただし，Rangen は演算子 OPn のシノプシスサイズを意味し，演算子 OPn がステートフル演算子でないときは Rangen = 0

tf3

d

時刻

図 6 オフセット時間と遅延時間の関係に，遅延時間 d の値に基づいて時刻 tfn を動的に変更する．これにより，古い鍵（K1 ）で暗号化された暗号値のみを含むタプ

上式に基づき，処理木中の各ステートフル演算子のオフセッ

ルが事前の見積もり時刻を過ぎて到着した場合も，これを演算

ト時間を見積もるためのアルゴリズムを Algorithm 3 に示す．

に用いることが可能となる．また，暗号化モジュール及び復号

このアルゴリズムでは，はじめに対象となるステートフル演算モジュールは d の値を定期的に参照し，移行期間の終了時刻 te

子を根とする部分木に対して，すべてのパスを抽出している．

を動的に延長する．

次に，各パス中のステートフル演算子のシノプシスサイズのSPE のインプットアダプタ，及び各ステートフル演算子が合計を計算し，その最大値を求めている．このアルゴリズムにタプル到着遅延を検出するためのアルゴリズムを Algorithm 4

よって得られる値は，処理木に入力された暗号化タプルが，対に，各ステートフル演算子が処理遅延を検出するためのアルゴ

象となるステートフル演算子を出るまでに掛かる最大の時間をリズムを Algorithm 5 にそれぞれ示す．

表したものである．
しかしながら，実際には到着タプルの通信遅延や SPE 内部
での処理遅延により，事前に見積もった時刻 tfn 以降に，古い鍵（K1 ）で暗号化された暗号値のみを含むタプルが到着することが考えられる．そこで我々は，遅延時間 d を暗号化ストリー
ムデータ処理システム全体で共有する変数として定義することを考える．ステートフル演算子 OPn におけるオフセット時間

Of f setn ，及び遅延時間 d の関係を図 6 に示す．
SPE のインプットアダプタはタプルの到着遅延を逐次検出し，遅延時間 d の値を更新する．また，処理木中の各ステート

Algorithm 4 Detecting Delay for Input Tuple
1: for all nodei ∈ nodes do
2:
3:

if nodei is a stateful operator thendt ← (NowTime − (Oﬀset + d)) − TimeStamp of input
tuple;

4:
5:
6:
7:

if dt > 0 thend ← dt;end ifend if

8: end for

フル演算子は入力時点でのタプル到着遅延，及び演算子内部での処理遅延を逐次検出し，遅延時間 d の値を更新するとともこれらのアルゴリズムを用いたとき，遅延時間 d の値が頻繁

Algorithm 5 Detecting Delay in Synopsis
1: for all nodei ∈ nodes do
2:

if nodei is a stateful operator thenfor all tuplej ∈ synopsis do3:

if TimeStamp of tuplej + d < ts then4:d ← ts − TimeStamp of tuplej ;5:
6:

end if

7:

end for8:

end if

9: end for5. 3. 2 既存演算子の改造
次に，本章で提案する手法を導入するために挙動を改造する必要があると考えられる演算子を以下に示す．
選択（selection）演算子
選択演算子では一般に，登録されている条件式を用いて評価が行われる．我々の暗号化ストリームデータ処理方式において登録されている条件式の右辺は暗号値であるため，鍵の更新に伴って，評価に用いる暗号値も動的に切り替えられるようにする必要がある．
結合（join）演算子に更新される可能性が考えられる．ゆえに，時刻 tfn に達して結合演算子は一般に，登録されている条件式の左辺にも右辺に

新旧両方の鍵で作られた暗号値のそれぞれに対して演算を行うも具体的な値を含まないため，改造の必要はないと考えられる．

ようになったステートフル演算子 OPn において，遅延時間 d

集約（aggregation）演算子が更新されることで，時刻 tfn が現在時刻以降に再設定されて集約演算子は，シノプシス中に貯まっているすべてのタプルのしまう場合が考えられる．このとき，演算子 OPn に到着する指定の属性に対して処理を行う．暗号化タプルにおいて，新旧

タプルはペアタプルであることが保証されなくなるため，演算の暗号化鍵を用いて生成された暗号値はそれぞれ異なる属性に子 OPn は古い鍵（K1 ）で作られた暗号値のみを用いて演算を格納されているため，時刻に応じて処理に用いる属性を動的に行う状態に戻る．

変化させる必要がある．具体的には，時刻 tfn 以前は古い暗号

時刻 tfn 以前は，到着するタプルに新しい鍵（K2 ）で作ら化鍵（K1 ）を用いて暗号化された暗号値を含む属性に対して，れた暗号値が含まれていることを保証できない．一方，古い鍵

時刻 tfn 〜te の間は古い暗号化鍵（K1 ）及び新しい暗号化鍵（K1 ）で作られた暗号値は，時刻 tfn によらず，移行期間の終（K2 ）を用いて暗号化された暗号値を含むそれぞれの属性に対了時刻 te 以前に到着するタプルには常に含まれていることがして，時刻 te 以降は新しい暗号化鍵（K2 ）を用いて暗号化さ保証される．よって移行期間の終了時刻 te に達しない限り，遅れた暗号値を含む属性に対して処理を行う必要がある．

延時間 d の更新によって演算子 OPn における時刻 tfn が現在

5. 3. 3 処理木の根ノードにおける重複回避

時刻以降に再設定されてしまった場合でも，古い鍵（K1 ）で作移行期間中に生成されたタプルペアは，一つの平文値に対しられた暗号値を用いることで正しい演算結果を得られ続けるこて新旧それぞれの鍵を用いて暗号化した暗号値を，両方とも含とが保証される．

んでいる．これらは SPE 内部でのクエリ処理のために必要な

5. 3 提案手法の導入ものであり，復号時にはいずれか一つの鍵で暗号化された暗号

本章で提案する暗号化鍵更新手法を導入するためには，暗号値のみあれば良い．そこで，処理木の根ノードに射影演算と同化モジュールにおいて暗号化タプルを生成する際にいくつかの様の機能を導入し，移行期間中に生成されたタプルペアのうち付加情報を含める必要がある．また，SPE において一部の既存

古い鍵（K1 ）で暗号化された暗号値を削除する機能を導入する

演算子の挙動を改造する必要がある．

ことで，SPE から復号モジュールに転送されるデータ量を削減

5. 3. 1 暗号化タプルへの付加情報の追加
暗号化モジュールにおいて暗号化タプルを生成する際，以下に示す二つの属性を付加する必要があると考えられる．

することが可能になる．

5. 4 評 価 実 験
本節では，事前に見積もった移行期間の長さに対して実際にEncTime

どの程度の遅延が生じるのかを確かめるため，暗号化ストリー

一般に SPE では，インプットアダプタにおいて，入力される

ムデータ処理システムにおける SPE 内部での処理遅延時間の各タプルに時刻情報が付加される．ここで付加される時刻は測定を行う．なお，通信遅延についてはそれぞれの経路に依存

インプットアダプタを通過する時刻である．しかしながら本すると考えられるため，本節ではすべてのモジュールを同一マ

章における提案手法では，この時刻情報とは別に，暗号化モ

シンで動作させ，処理遅延のみを考えるものとした．実験に用ジュールにおいて暗号化タプルが生成された時刻（“EncTime”

いたマシンの環境を表 2 に示す．

属性）を付加する必要がある．EncTime 属性は主に，前述した

表 2 実験に用いたマシンの環境

Algorithm 4 や Algorithm 5 において遅延時間を測定するため

CPU

R
R
Intel⃝Xeon⃝
CPU E5640 @ 2.67GHzに用いる．

Memory

48GB

KeyID

OS

Ubuntu 10.04.4 LTS (64bits)

タプルの暗号化に用いる暗号化鍵を識別するための値を指す．

Java Runtime

OpenJDK Runtime Environment(IcedTea6 1.11.5)

SPE 上の各演算子において条件評価を行う場合や，復号モSPE

SS* (Rev. 134) ※一部機能を追加

ジュールにおいて復号を行う際に，評価に用いる暗号値や復号に用いる鍵を選択するために必要となる．

また，実験に用いた処理木を図 7 に示す．処理木から，想定される移行期間の長さ（te − ts ）は 6 秒であることがわかる．

また，処理木に入力するストリーム s1 及び s2 に含まれるタプ
号値の 2 つの属性について，それぞれ新旧両方の鍵を用いて暗号化された値を含むペアタプルとし，このうち id 属性の値は常に DET (1) とした．すなわち，処理木中の選択演算と結合演

処理木通過時間
処理木通過時間（秒）（秒）

ルは，いずれも id 属性の DET 暗号値及び val 属性の OPE 暗

35
30
25
20
15
10
5
0
40

算において選択率（selectivity）は 1 となる．

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

ストリーム情報源からの送信レート（タプル／秒）

図 9 タプルの処理木通過時間

5

α

sec

1

1

sec

sec

σ

σ
id=1

MIN(s1.val)

行っている．本稿では，暗号化ストリームデータ処理方式の中でクエリの実行を停めることなく効率的に暗号化鍵を更新するための手法，及びタプルの到着遅延や処理遅延を検出して移行

s1.id=s2.id

期間を延ばすためのアルゴリズムについて提案した．
今後の課題としては，これらのアルゴリズムを我々の研究室

id=1

で開発中のストリーム処理エンジン及び暗号化・復号モジュー
s1

s2

図7

実験に用いた処理木

ルへ実装を行い，さらなる評価実験を行いたい．また，GPUや FPGA を用いて暗号化及び復号を高速化する手法についても検討を行っていきたいと考えている．

処理木から出力されたそれぞれのタプルについて，タプルの謝辞 本研究成果は，独立行政法人情報通信研究機構（NICT）

暗号化時刻と現在時刻の差を計算することで，処理遅延時間をの委託研究「新世代ネットワークを支えるネットワーク仮想化基測定した．この処理木に対して，各ストリーム情報源からの送盤技術の研究開発」，及び科学研究費基盤研究（C）（#24500106）

信レートを変化させながら繰り返し試行を行った．

の助成により得られたものです．

はじめに，送信レートが 40〜50(tuples/sec) のそれぞれの場
合について，処理木から 20 タプルが出力されるまで計測を行い，取った値の幅と平均値を図 8 に示す．このとき，見積もった移行時間（6 秒）からの遅延は最大で約 19 ミリ秒であった．

処理木通過時間
処理木通過時間（秒）
（秒）

6.03
6.01
5.99
5.97
5.95
40

41

42

43

44

45

46

47

48

49

50

ストリーム情報源からの送信レート（タプル／秒）

図 8 タプルの処理木通過時間（40〜50(tuples/sec)）

次に，送信レートが 51(tuples/sec) 以上の場合について同様の計測を行った結果を図 9 に示す．送信レートが 51(tuples/sec)
を超えると大きな遅延が発生していることがわかる．その原因として，結合演算の選択率（selectivity）が 1 であるために，
各ストリーム情報源からの送信レートを r としたときに結合演算子から 1 秒間に出力されるタプル数は 2r2 (tuples) となり，SPE の性能が限界に達してしまっていることが考えられる．
よって，さらに長時間にわたって計測を行ったとき，送信レー
トが 51(tuples/sec) 以上の場合における遅延時間の最大値はより大きくなっていくと考えられる．

6. まとめと今後の課題
我々は，安全性を考慮したストリームデータ処理の実現を目的として，暗号化ストリームデータ処理方式について研究を文

献[1] 情報処理推進機構「安全な暗号鍵のライフサイクルマネージメン
トに関する調査」に関する報告書」. http://www.ipa.go.jp/
security/fy19/reports/Key_Management/.
[2] Arvind Arasu, Shivnath Babu, and Jennifer Widom. The
cql continuous query language: semantic foundations andquery execution. VLDB J., Vol. 15, No. 2, pp. 121–142,
2006.
[3] Alexandra Boldyreva, Nathan Chenette, Younho Lee, andAdam O’Neill. Order-preserving symmetric encryption. In
EUROCRYPT, pp. 224–241, 2009.
[4] Richard Chow, Philippe Golle, Markus Jakobsson, Elaine
Shi, Jessica Staddon, Ryusuke Masuoka, and Jesus Molina.
Controlling data in the cloud: outsourcing computation
without outsourcing control. In CCSW, pp. 85–90, 2009.
[5] Bugra Gedik, Henrique Andrade, Kun-Lung Wu, Philip S.
Yu, and Myungcheol Doo. Spade: the system s declarative stream processing engine. In SIGMOD Conference, pp.
1123–1134, 2008.
[6] Shai Halevi and Phillip Rogaway. A tweakable encipheringmode. In CRYPTO, pp. 482–499, 2003.
[7] Stefan Hildenbrand, Donald Kossmann, Tahmineh Sanamrad, Carsten Binnig, Franz Faerber, and Johannes Woehler.
Query processing on encrypted data in the cloud. 2011.
[8] Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, pp. 223–
238, 1999.
[9] Raluca A. Popa, Catherine M. S. Redﬁeld, Nickolai Zeldovich, and Hari Balakrishnan. Cryptdb: protecting conﬁdentiality with encrypted query processing. In SOSP, pp.
85–100, 2011.
[10] Katsuhiro Tomiyama, Hideyuki Kawashima, and Hiroyuki
Kitagawa. A security aware stream data processing schemeon the cloud and its eﬃcient execution methods. In Proceedings of the fourth international workshop on Cloud data
management, CloudDB ’12, pp. 59–66, New York, NY,
USA, 2012. ACM.