論文 / 著書情報
Article / Book Information
論題(和文)

データやユーザの効率的な追加・削除が可能な秘匿情報アクセス手法

Title(English)
著者(和文)

児玉 快, 横田 治夫

Authors(English)

Kai Kodama, Haruo Yokota

出典(和文)

第7回データ工学と情報マネジメントに関するフォーラム論文集, , ,Citation(English), , ,発行日 / Pub. date2015, 3

Powered by T2R2 (Science Tokyo Research Repository)DEIM Forum 2015 G2-1

データやユーザの効率的な追加・削除が可能な秘匿情報アクセス手法児玉快†

横田 治夫†† 東京工業大学情報理工学研究科計算工学専攻 〒 152-8552 東京都目黒区大岡山 2-12-1
E-mail: †kodama@de.cs.titech.ac.jp, ††yokota@cs.titech.ac.jp
あらまし 近年, 災害時の情報技術活用が注目され, 安否確認や情報共有を支援するためのシステムが利用されている.
このようなシステムには, プライバシーやセキュリティに関して問題となり得る機微な情報が蓄積される可能性があり, 必要に応じて暗号化による保護が行われるべきである. しかしながら, 従来の暗号化手法では, データの保有者が全ての共有先の鍵情報を把握しなければならない上, 共有先ユーザが削除される度に暗号化し直す必要があり, 非効率的である. そこで本研究では, データやユーザに対してより効率的な追加や削除を行うために, 共有情報に対するアクセス制御としてロジカルなクラスを単位とした暗号化を行う手法を提案し, その評価を行う.
キーワード

プロキシ再暗号化, データ共有, リボケーション.

1. は じ め に防止するために, 決められた規則に従って資源へのアクセスを制限することである [2]. この規則を形式的なモデルとして実装

近年, 災害時や災害後の復旧および復興を目的とした情報技

したものを, アクセス制御ポリシーと呼ぶ. システムは, ユーザ

術活用が注目され, 安否確認や情報共有を支援するためのシスによるアクセス要求に対して, 図 1 のようにアクセス制御ポリテムが利用されている. その代表として, 災害用ブロードバン

シーをもとに認可および認証を行う. これにより, アクセス制

ド伝言サービスや, 地域に向けて提供されるより具体的な避難御システムを経由して実行されたすべてのアクセスが正当なも情報の配信を行うシステムが挙げられる [1]. このようなシステのであることを保証する.

ムに蓄積されるデータの中には, プライバシーやセキュリティ
要求に関して問題となる機微なものが含まれる可能性があり, そのようなデータには不正利用を防止するためのアクセス制御が行

ユーザ

情報資源

われるべきである. 加えて, システムの全体を信頼することが困難である場合などは, 暗号化によってデータを保護しなければならない. しかしながら, 従来の暗号化手法では, データの保有者が全ての共有先ユーザの鍵情報を把握する必要がある. ま

アクセス!
制御!
ポリシー

認可

要求
ユーザ

サーバ
情報資源

拒否

図 1 基本的なアクセス制御モデル.

た, 共有先のユーザのアクセス権限の変更や削除といったリボ
ケーション操作がなされる度に, その影響を受けるデータに対して再度暗号化し直さなければならず, 非効率的である.

しかしながら, アクセス制御システムの全体を信頼することは現実的ではない. 例えば, 情報資源はデータベースサーバのよそこで本論文では, データやユーザの追加および削除をよりうな蓄積装置に保管されるが, そのサーバの管理者を完全には効率的に行うために, 共有情報に対するアクセス制御としてロ信頼できない場合がある. このようなケースでは, サーバ管理

ジカルなクラスを単位とした暗号化を行う手法を提案する. プ

者に許可なく情報を取得されることを防ぐために, アクセス制

ロキシ再暗号化可能な暗号を利用することにより, アクセス制

御に加えて暗号化によるデータ保護がなされる. 例として, 秘御の柔軟性を維持しながら, 従来の暗号化手法と比較して計算

匿情報の蓄積や共有のために, セキュリティ上完全には信頼で量を抑えられることを示す. また, RDF による情報表現が可能

きないクラウドストレージサービスを利用する場合が挙げられなデータベースとユーザの間で動作するプロキシとして提案手る. データの保有者は, サービスの管理者による閲覧を防ぐた法を実装し, ベンチマークを用いて性能を評価する。

めに, 情報をあらかじめローカルシステム上で暗号化したもの

本論文は, 本章を含めて 6 章により構成される. 第 2 章ではをアップロードする. データの利用者は, 暗号化された情報を本論文に関して前提となる知識を述べる. 第 3 章では関連する

ダウンロードした後にローカルシステム上で復号して使用する.

既存研究を紹介する. 第 4 章では提案する手法について述べる.

より利便性の高い手法のひとつに, Popa らによる研究 [3] が第 5 章で評価実験の方法を述べ, その結果を考察する. 最後に,ある. この手法では, CryptDB と呼ばれるアプリケーション

第 6 章で本論文のまとめと今後の課題を述べる.

がクライアントユーザとデータベースの間に配置され, プロキ

2. 前 提 知 識

シやミドルレイヤのように働く. アプリケーションは, データを蓄積する際に強度の異なる暗号化を複数回行い, ユーザの問

2. 1 アクセス制御手法

い合わせに対してはそのクエリの計算に必要なレベルまでデー

情報工学においてアクセス制御とは, 情報資源の不正利用をタベースを復号してから処理を行う. CryptDB を利用すると,

ユーザがデータベースを利用する際に, データベースの内容のる方法のひとつである. 情報の単位としてトリプル (3 つ組) が露出を一部までに留めることができる. これにより, データベー

用いられ, トリプルは 2 個のノード (サブジェクトおよびオブスの管理者を信頼することなく, 暗号化による保護を利用する

ジェクト) とそれらを結ぶ有向辺 (プレディケート) から構成さことが可能である. しかしながら, 代わりにプロキシサーバであれる. 例えば, “リソース :Alice はリソース :Bob を知っている CryptDB を運用する管理者を信頼しなければならない. そる” という情報は, 図 2 に示すトリプルとして表現される.

のため, データベースとプロキシサーバの双方の管理者ともを
完全には信頼できない場合には, 他の手法の利用を検討する必

Alice

knows

Bob

要がある.
サブジェクト

2. 2 プロキシ再暗号化
再暗号化とは, あるユーザのために暗号化された暗号文を, 別

プレディケート

オブジェクト

図 2 RDF トリプルによる情報の表現.

のユーザが復号可能な暗号文に変換することである. 特に, 第三者であるプロキシによって再暗号化が行われる暗号体系は,また, トリプルの集合は RDF グラフと呼ばれ, RDF グラフ

プロキシ再暗号化と呼ばれる. プロキシ再暗号化技術の最終的として記述された情報への問い合わせ言語として SPARQL がな目標は, データの保有者と利用者を除く全ての第三者を信頼標準的に用いられている [6]. SPARQL による問い合わせはグすることなく, 再暗号化に成功することである [4].

ラフパターンのマッチングにより行われ, グラフパターンを構成

一般に, 公開鍵暗号方式をベースとするプロキシ再暗号化アする基本的な要素であるベーシックグラフパターンはトリプル

ルゴリズムは, 5 つの手続きによって構成される. 鍵生成の手続パターンの集合として表現される. 例えば, “リソース :Alice がきでは, セキュリティパラメータを入力として, 主体 A の公開

知っているリソース” を選択するための問い合わせは, SELECT

鍵 pkA および秘密鍵 skA の組 (pkA , skA ) を出力する. 暗号化?X WHERE { :Alice :knows ?X } のような SPARQL クエリの手続きでは, 主体 A の公開鍵 pkA および平文 m を入力としとして記述される. これに対して, 結果は変数と値のペアであて, A の秘密鍵 skA により復号可能な暗号文 cA を出力する. 復るバインディングの集合であるソリューションの集合として表号の手続きでは, 主体 A の秘密鍵 skA およびそれによる復号が現される. 例えば, 先のクエリは図 2 に示すトリプルからなる可能な暗号文 cA を入力として, 平文 m を出力する. 再暗号化

RDF グラフ上で {{ ?X = :Bob }} という結果を返す.

鍵生成の手続きでは, 再暗号化元の主体 A や再暗号化先の主体

RDF や SPARQL といった技術はセマンティックウェブにB の公開鍵や秘密鍵を入力として, 対応する再暗号化鍵 rkA→B

おける情報記述手法として事実上の標準である. 近年では特にを出力する. 再暗号化の手続きでは, 主体 A による復号が可能

相互にリンクするオープンデータの注目が高まり, そのためのな暗号文を主体 B による復号が可能な暗号文に変換する再暗機械可読なフォーマットとして RDF による表現を利用するこ号化鍵 rkA→B および暗号文 rA を入力として, 暗号文 rB を出とが増えている. 我が国においても, 政府や地方自治体による力する.

透明性や信頼性の向上を目的とした情報公開がオープンデータ

プロキシ再暗号化方式のひとつに, ElGamal 暗号をベースとして Blaze らにより考案された BBS 方式がある [5]. BBS によるアルゴリズムは次のように表現される.
鍵生成 sk ∈ Z∗p−1 ,pk = g sk

ただし g は安全素数 p を法とする原始根であるとする.
暗号化 m ∈ G, k ∈ Z∗p−1

c1 = mg k mod p(sk−1 ) −1

m = c1 ((c2)

RDF による表現で記述されたデータベースを利用すると, 同様に機械可読なフォーマットで記述された外部のデータベースと柔軟に連携することが可能になる. また, 直感的かつ記述に容易な問い合わせ言語として SPARQL を利用することができる [8]. そのため, 本論文では RDF による情報表現と SPARQL
による情報検索が利用可能なデータベースを想定し, 手法を提案する.

c2 = (g sk )k mod p
復号

形式で行われている [7].

) mod p−1
再暗号化鍵生成 rk A→B = skA
skB
rk
再暗号化 c2 7→ c2

3. 関 連 研 究
3. 1 RDF の部分的暗号化
RDF 項の暗号文は常に RDF リテラルとして扱われる. しプロキシ再暗号化技術では, 再暗号化を行う際に全ての第三かし, 現在の W3C 勧告 [9] においては, RDF リテラルはオブ者の持つ機能を利用する必要のないことが望ましい. しかしな

ジェクトの位置にのみ記述可能とされている. そのため, サブ

がら, 第三者を一切信頼することなくプロキシ再暗号化やそれジェクトやプレディケートの位置にある RDF 項を暗号化したに利用するデータベース管理を行う手法は現在提案されていな

値を, どのようなノードに格納するかが問題となる.

い. 代わりに, 多くの手法では信頼可能な第三者として秘密鍵生

Giereth は, 暗号化前のグラフ構造を変化させることでこの成局をモデルに含めたり, プロキシサーバそのものを信頼可能

問題を解決した. 例えば, 1 個のサブジェクトやプレディケートな第三者として利用することによって再暗号化を実現している.

を暗号化する際には, グラフ構造を変化させるために空白ノー2. 3 RDF

ドやトリプルを生成する. この手法に加えて, 復号の際にグラフ

RDF (Resource Description Framework) は, 情報を表現す

構造を戻すアルゴリズムや, 暗号化された RDF にハッシュダイジェストや公開鍵の情報などを組み込む方法を提案した [10].

アルゴリズム 3 RDF の部分的暗号化手法におけるユーザ削除

具体的には, RDF 項やトリプルのような平文をユーザに対し入力 平 文 集 合 M= {m1 , m2 , . . . , mm }, 公 開 鍵 集 合 P=て共有する際に, アルゴリズム 1 に示す手続きにより暗号化を{pk1 , pk2 , . . . , pkn }, 共通鍵 k による対称関数 fk , 公開鍵 pk によ行う.

る非対称関数 gpk , ダイジェスト関数 h, 削除対象のユーザの公開
鍵 pku ∈ P , 削除対象のユーザを受信者に含む平文集合 Mu ⊂=M
出力 暗号化コンテナを含む RDF グラフ G

アルゴリズム 1 RDF の部分的暗号化手法における情報蓄積
入力 平 文 集 合 M= {m1 , m2 , . . . , mm }, 公 開 鍵 集 合 P={pk1 , pk2 , . . . , pkn }, 共通鍵 k による対称関数 fk , 公開鍵 pk による非対称関数 gpk , ダイジェスト関数 hfor all mi ∈ Mu do
f のセッション鍵 k を生成する.
ci ← fk (mi )Pi ← mi の受信者が持つ公開鍵集合 (Pi ⊂=P )出力 暗号化コンテナを含む RDF グラフ G

for all pkj ∈ Pi − {pku } dofor all mi ∈ M doci,kj ← gpkj (k)f のセッション鍵 k を生成する.

end forci ← fk (mi )hi ← h(mi )Pi ← mi の受信者が持つ公開鍵集合 (Pi ⊂=P )hi を含む暗号化コンテナを G から削除する.

for all pkj ∈ Pi doci , ci,k1 , ci,k2 , . . . , ci,kn , hi を暗号化コンテナ ec に格納する.

ci,kj ← gpkj (k)ec をリテラルとして直列化し, G に挿入する.

end forend forhi ← h(mi )ci , ci,k1 , ci,k2 , . . . , ci,kn , hi を暗号化コンテナ ec に格納する.
ec をリテラルとして直列化し, G に挿入する.

ることはない. このように, 階層関係を推論してアクセス制御

end forを実装するという点で, 本論文の提案する手法に関連性がある.

しかしながら, この手法では, 複数のユーザに対する共有を

4. 提 案 手 法

目的とする RDF グラフを暗号化する際に, 保有者は共有対象

共有情報に対するアクセス制御としてロジカルなクラスを単となる全てのユーザの鍵情報を保持しなければならない. また,位とした暗号化を行う手法を提案する. まず, 暗号化情報を蓄

共有対象のユーザの追加や削除が行われる度に暗号化し直さな積するデータベースとユーザとの間にミドルレイヤアプリケー

ければならないという点でも非効率的である. 実際に, ユーザ

ションを配置する. アプリケーションは, ユーザの認証を行うの追加や削除はアルゴリズム 2 やアルゴリズム 3 の示すように際にそのクラスを調べ, 対応するアクセスのレベルに紐付けら行われる.

れた再暗号化鍵を秘密鍵生成局から取得する. その後, ユーザ

アルゴリズム 2 RDF の部分的暗号化手法におけるユーザ追加
入力 平 文 集 合 M= {m1 , m2 , . . . , mm }, 公 開 鍵 集 合 P={pk1 , pk2 , . . . , pkn }, 共通鍵 k による対称関数 fk , 公開鍵 pk によの要求に基づいて, データベースに対する検索が可能な問い合
わせを生成し, 得られた結果を再暗号化してユーザに送信する.
以下では, 手法に関するモデルやオントロジについて説明する.

る非対称関数 gpk , ダイジェスト関数 h, 追加対象のユーザの公開

4. 1 モ デ ル

鍵 pku ∈ P , 追加対象のユーザを受信者に含む平文集合 Mu ⊂=M

本研究において想定するモデルを図 3 に示す. 本手法では,

出力 暗号化コンテナを含む RDF グラフ G

for all mi ∈ Mu dok ← mi に対応する f のセッション鍵
ci ← fk (mi )ci,ku ← gpku (k)ユーザは一意に識別可能な ID を持つ. ユーザは, プロキシサー
バに対して, 既に蓄積されている情報への問い合わせや, ユーザの保有する新たな情報の蓄積を要求する.
プロキシサーバは, ユーザの持つ ID をユーザのクラスに対hi ← h(mi )応付ける写像を持つ. ユーザの ID は, 高々 1 個のクラスに対応

ec ← hi を含む暗号化コンテナ付けられる. また, プロキシサーバは, ユーザのクラスをアクセ

ec をリテラルとして直列化したものを, G から削除する.

スのレベルに対応付ける写像も持つ. ユーザのクラスは, 0 個以

ec に ci,ku を格納する.

上のアクセスのレベルに対応付けられる.

ec をリテラルとして直列化し, G に挿入する.
end forまた, 本研究で提案する手法は, 全ての情報が RDF トリプル
により記述されていることを前提とする. 情報はアクセス制御ポ
リシーに基づいて暗号化された状態で蓄積される. アクセス制御

3. 2 XML の構造化情報の階層関係に着目した暗号化ポリシーは, RDF トリプル (s, p, o) を入力として, 各 RDF 項へ

XML は構造化された情報を記述することができるが, そののアクセス制御に関する情報 (L, C) = ((ls , lp , lo ), (cs , cp , co ))階層関係に着目した暗号化手法が提案されている [11]. 例えば,を出力する. ここで, L は RDF 項に対応付けられるアクセスのあるノードにアクセス可能なユーザは, その親ノードにもアクレベルを示し, C は 4. 6 小節で後述する個人間関係を利用するセス可能でなければならない. また, あるノードへのアクセスがアクセス制御ポリシーを示す.

許可されないユーザは, その子ノードへのアクセスも許可されアクセスのレベルは階層関係を持ち, あるレベル l やそれよ

り高いレベルに対応付けられるクラスのユーザは, l を対応付けられた RDF 項へのアクセスが許可される.

:higherOf ドメインおよびレンジをアクセスレベルリソースとするオブジェクトプロパティである. そのサブジェクト

各アクセスレベルに対応する公開鍵秘密鍵ペアは, 信頼可能な秘密鍵生成局により生成されるが, それらはプロキシに送信のレベルが, そのオブジェクトのレベルよりも高いことを示す.

されない. 代わりに, プロキシは生成局に対して再暗号化鍵の:value ドメインを暗号化タームのリソースとし, レンジをリ生成を要求し, それをもとにデータベースサーバから受信した

テラルとする関数的なデータプロパティである. タームの問い合わせ結果やデータベースサーバ内の RDF グラフに対し暗号化後の値を表現する.

て再暗号化を行い, ユーザのために生成された復号鍵により復:open ドメインを暗号化タームのリソースとし, レンジをア号可能な状態でユーザに送信する. ユーザは, 生成局に対して

クセスレベルリソースとする関数的なオブジェクトプロパ

復号鍵の送信を要求し, それをもとにプロキシから受信した情ティである. アクセス制御ポリシーに基づいてどのアクセ

報を復号し, 結果を得る.

スのレベルに対応付けられ暗号化されたかを示す.

また, ユーザからプロキシに送信される問い合わせ内容やデー:closed ドメインを暗号化タームのリソースとし, レンジを個

タベース操作について, 変数ノードを除いて, 含まれる全ての人間関係によるポリシーのリソースとするオブジェクトプ

RDF 項はユーザの公開鍵で暗号化される. そのため, プロキシ

ロパティであり, 暗号化タームを任意個数のポリシーに紐からデータベースに送信される問い合わせ内容やデータベース

付ける. 個人間関係によるポリシーは個人とユーザに関す操作は, 暗号化された RDF 項の再暗号化により生成される.

る関係として RDF トリプルのパスにより表現される. プ
ロキシは, 暗号化されたアクセスのレベルに対応するユー
ザに加えて, 個人間関係によるポリシーにより許可された

秘密鍵!
生成局

ユーザ 1
アクティブ
セッション

ユーザからのアクセスも可能にする.

:level ドメインを個人間関係によるポリシーのリソースとし,

アプリ!
ケー!
ション

データベース!
プロキシ

DBMS

再暗号化!
関数

クトプロパティである. ポリシーの指すレベルを示す.

認証
ユーザの!
クラス

ユーザ 2

図3

レンジをアクセスレベルリソースとする関数的なオブジェ

アクセス!
のレベル

暗号化!
された!
データ

鍵!
テーブル

本論文の提案するアクセス制御モデル.

:length ドメインを個人間関係によるポリシーのリソースとし, レンジを非負整数リテラルとする関数的なオブジェク
トプロパティである. ポリシーが許可するパスの最大の長さを示す.

4. 2 オントロジ:subject, :predicate, :object ドメインをステートメント

本手法では, 新たに 12 個の RDF プロパティを定義して利リソースとし, レンジを暗号化タームのリソースとする関用する. これらのプロパティは, プロキシによって意味解釈さ数的なオブジェクトプロパティである. それぞれ, ステー

れ, アクセス制御に利用される. 以下では, ドメインおよびレントメントのサブジェクト, プレディケート, オブジェクトのジは W3C 勧告である RDF Schema 1.1 [12] における Domain

暗号化タームを示す.

および Range を指す. また, 関数的, 逆関数的, データプロパ
ティ, オブジェクトプロパティとはそれぞれ, 同様に W3C 勧告である OWL 2 [13] における FunctionalProperty, Inverse-

FunctionalProperty, DataProperty, ObjectProperty を指す.

これらのプロパティは, プロキシに保存されるユーザ情報や,暗号化された値を含む RDF グラフの中で利用される. トリプ
ルの暗号化は, タームの暗号化に加えて, 図 4 のように複数のステートメントを生成することにより行われる.

:id ドメインをユーザリソースとし, レンジをリテラルとする
関数的かつ逆関数的なデータプロパティである. ユーザのvalue	

_:X1

AL1
open	

subject	持つ一意に識別可能な ID を示す.

:higherOf ドメインおよびレンジをアクセスレベルリソースとするオブジェクトプロパティである. サブジェクトのレ

_:X1
AL1

closed	closed	ベルが, オブジェクトのレベルよりも高いことを示す.

level	

:userClass ドメインをユーザリソースとし, レンジをユーザ

AL4

length	2

クラスリソースとする関数的なオブジェクトプロパティである. アクセス制御ポリシー上のユーザが属するクラスを

name

predicate	value	

object	value	

name示す.

:mappingTo ドメインをユーザクラスリソースとし, レンジ"Alice"をアクセスレベルリソースとする関数的なオブジェクトプ
ロパティである. ユーザクラスからアクセスのレベルへの写像として記述される.

図4

トリプルの暗号化.

"Alice"4. 3 データの追加と削除

アルゴリズム 5 データベースの検索が可能な問い合わせの生成

アクセス制御ポリシーは, トリプルを入力として, 各ターム

入力 ユーザ ID idu , 再暗号化関数 r, 変数集合 Vin , トリプルパターンに対応するアクセスのレベルと個人間関係によるポリシーを出力する. データの追加の際には, プロキシはポリシーの出力を入力とする規則 4 に基づいて複数のステートメントを生成し,データベースサーバに送信する. 生成されるステートメントには, 各タームの暗号文に加えて, 対応するアクセスのレベルや,個人間関係によるポリシーが含まれる.

集合 Tin
出力 変数集合 Vout , トリプルパターン集合 Tout

L ← {l | (idu , ˆ:id/:userClass/:mappingTo/:higherOf*, l)}for all l ∈ L, ti = (si , pi , oi ) ∈ Tin do
変数ノード vi を作成する

for all (p, n) ∈ {(:subject, si ), (:predicate, pi ), (:object, oi )}do

データの削除の際には, 対象を追加したポリシーが既知であ

if n が変数ノードである thenTout に (vi , p, [:value, n]) を追加する

るかどうかにより処理が異なる. ポリシーが既知である場合にelse

は, 暗号化により生成されるステートメントを計算し, 一致する

Tout に (vi , p, [:value, ridu →l (n); :open, l]) を追加する

ものをデータベースサーバから全て削除する. ポリシーが既知でない場合には, すべてのアクセスのレベルによる暗号化を行い, それぞれの暗号化結果に一致するものをデータベースサー

end ifend forend for

バから全て削除する.

for all 変数ノード v ∈ Vin do

規則 4 蓄積する情報の生成

end for

Vout に rl→idu (v) を v として追加する

入力 再 暗 号 化 関 数 r, ア ク セ ス 制 御 ポ リ シ ー に よ る 出 力 (L =(ls , lp , lo ), C = (cs , cp , co )), 追加元ユーザ ID idu

ケートの有向パス P : rA → · · · → rB が存在し, パスの含む各(?s, ?p, ?o) → [:subject,

トリプルがアクセスのレベル lmax 以下であり, かつ式 1 を満

[ :value, ridu →ls (?s); :open, ls ;:closedi , [:level, csi

level; :length, csi

length]]:predicate, [ :value, ridu →lp (?p); :open, ls ;:closedi , [:level, cpi:object,level

ブジェクトとして個人間関係によるポリシーが C = (cs , cp , co ); :length, cpi

length]][ :value, ridu →lo (?o); :open, lo ;:closedi , [:level, coi

level; :length, coi

足するとき, A のユーザとしてのインスタンス uA は, rB をサ

length]]]であるようなトリプルにアクセスすることができる.

min(cslevel , cplevel , colevel ) <= lmax ∧max(cslength , cplength , colength ) >= length(P )(1)

ここで, rA と rB の間の有向パスはユーザ情報グラフに依存

4. 4 ユーザの追加と削除

しないため, 暗号化された値を含むデータベースが変更されな

ユーザの追加の際には, 対象のユーザの ID uid に対応するク

い限り, パスが追加されたり削除されることはない. そのため,

ラス cu について, (?u, :id, uid ) → (?u, :userClass, cu ) として

インデックスとして事前に計算しておくことで, ユーザによる記述される規則によりステートメントを生成する. ステートメ

問い合わせの度にパスを評価する必要がなくなる.

ントはプロキシサーバ内または外部のユーザ情報グラフに蓄積され, ユーザの認証のために参照される. また, ユーザの削除の際には, ユーザ情報グラフから対象の ID を検索し, ID とクラスへの紐付けを記述するステートメントを削除する.
なお, ユーザ情報グラフの語彙上の制限として, :id は関数的かつ逆関数的なプロパティであり, かつ :userClass は関数的プ

5. 実

験

提案手法と, 関連する既存手法である Giereth による部分的RDF 暗号化手法 [10] の性能を比較する. 両手法の実装には,Apache により開発されている Java 向けセマンティックウェブ
フレームワークである Jena を利用した.

ロパティである必要がある. そのため, ユーザを追加する前に,

5. 1 環境とデータセット

対象ユーザが記述されているかどうかを調べ, 既に記述されて実験には, 以下の環境を用いた.

いる場合には対象ユーザを一度削除する.

4. 5 検索問い合わせユーザの属するクラスやそれに対応付けられるアクセスのレベルといったオープンな情報による検索は, SPARQL
クエリの変換により行われる. トリプルパターンの集合のみにより構成された WHERE クローズからなる SPARQL 選択ク
エリを変換する手続きを, アルゴリズム 5 に示す.

4. 6 個人間関係に基づくアクセス制御

CPUIntel Xeon Processor E5620

RAM PC3-10600 DDR3 SDRAM 24 GiB
OS

Ubuntu 11.10 64-bit

Java

1.7.0 65

JRE

OpenJDK IcedTea 2.5.3

Jena

2.12.1

実験データには, セマンティックウェブシステムのために考より柔軟なアクセス制御を行うために, 情報が記述されてい案されたベンチマークとして Lehigh University Benchmark

る複数の個人の間の関係にも注目する. 具体的には, 個人 A を(LUBM) [14] を利用した. LUBM は, テストデータとして, 大表すリソース rA と個人 B を表すリソース rB の間にプレディ

学や学部のような組織や, そこに所属する教員や学生に関する情報を生成する. 特に規模の大きいオントロジに対するテスト

び削除に掛かる時間を計測した結果を示すものである. ただし,のためのベンチマークとして, LUBM は事実上の標準になって比較対象におけるユーザ削除時間は, より小さなデータセット

いる [15]. この実験では, 生成されたトリプルに加えて, 規則 6において計測した結果をもとに算出した. 実験では, いずれのに示す推論規則を用いて個人間関係を生成し, ポリシーの評価

追加および削除操作についても, 本手法は比較対象よりも短いに利用した.

時間で処理を完了した.

規則 6 個人間の情報の生成

1E+14!
1E+12!

ユーザの追加 (比較対象)!

→ (?x, :sameWorksFor, ?y)1E+10!

ユーザの削除 (比較対象)!

1E+08!

データの追加 (比較対象)!

1E+06!

データの削除 (比較対象)!

(?x, :teacherOf/ˆ:teacherOf, ?y)[μs](?x, :worksFor/ˆ:worksFor, ?y)→ (?x, :sameTeacherOf, ?y)

ユーザの追加 (本手法)!

1E+04!

(?x, :takesCourse/ˆ:takesCourse, ?y)1E+02!

→ (?x, :sameTakesCourse, ?y)1E+00!

ユーザの削除 (本手法)!
データの追加 (本手法)!
0!

100000!

200000!

300000!

400000!

データの削除 (本手法)!

トリプル数 (暗号化前)

また, アクセス制御ポリシーは次のように人工的に決定した.

図 5 1 学部に相当するユーザ数における実行時間.

Employee 誰がどの講義を受けているかを参照可能.
Professor Employee が参照可能な情報と, 誰がどの組織の1E+14!

一員であり, どの講義を教えているかを参照可能.
れているかを参照可能.
上記を含む全てのユーザ 上記以外の情報を参照可能.

[μs]

Chair Professor が参照可能な情報と, 誰がどの組織に雇用さ

1E+12!

ユーザの追加 (比較対象)!

1E+10!

ユーザの削除 (比較対象)!

1E+08!

データの追加 (比較対象)!

1E+06!

データの削除 (比較対象)!
ユーザの追加 (本手法)!

1E+04!

ユーザの削除 (本手法)!

1E+02!

ユーザによる問い合わせの内容としては, LUBM の提供す

データの追加 (本手法)!

1E+00!
0!

1000!

2000!

る 14 個のクエリのうち, University0 内の組織である Depart-

ment0 に関するトリプルのみからなるデータセットに対して 1個以上のソリューションを結果として返すことのできる 5 個(#1, #3, #5, #6, #14) を選択し, ユーザによる入力とした.
各クエリの内容は次のように記述される.
問い合わせ元のユーザは University0 内の組織である De-

partment0 に所属する FullProfessor7 であるとした. このユーザに対応するユーザクラスは Chair であるため, アクセス制御
ポリシーに基づいて, 全てのデータにアクセスする権限を持つ.
クエリの応答時間はアクセス範囲の広さに対して単調に増加するため, このユーザからの問い合わせにより最悪の応答時間を評価することができる.
また, プロキシ再暗号化が可能な暗号化方式として, Blaze らによる BBS アルゴリズムを採用した. ただし, 鍵サイズは 2048
ビットとし, 平文と暗号化鍵から暗号文が一意に決定されるように発生させる乱数を固定した.
また, Giereth により提案されている部分的 RDF 暗号化アル
ゴリズムを比較対象として実装し, 同様に評価した. 実装の際に, 共通鍵暗号方式と公開鍵暗号方式としてそれぞれ鍵サイズ

256 ビットの AES と鍵サイズ 2048 ビットの RSA を用いた.
5. 2 データおよびユーザの追加と削除
図 5 は, 1 学部に相当するユーザ情報と N (1 <= 8) 学=N <部に相当するデータが既に蓄積されている状態で, 1 個のデー
タおよび 1 人のユーザの追加および削除に掛かる時間を計測した結果を示すものである. また, 図 6 は, N (1 <= 8) 学部=N <に相当するユーザ情報と 1 学部に相当するデータが既に蓄積されている状態で, 1 個のデータおよび 1 人のユーザの追加およ

3000!

4000!

5000!

データの削除 (本手法)!

ユーザ数

図 6 1 学部に相当するデータ数における実行時間.

蓄積されたデータ数を N , ユーザ数を U として, 本手法に対して各操作の平均計算量を算出すると, ユーザの追加操作は Uに比例する時間で完了し, ユーザの削除操作は定数時間で完了
する. また, データの追加および削除の操作はユーザ側での 1回の暗号化とサーバ側での 1 回の再暗号化により完了する. 一方で, 比較対象においては, 計算量は各ユーザから参照可能な割合の平均値に大きく依存する. この値を α (0 <=α<= 1) とすると, ユーザの追加および削除はそれぞれ αN, α2 N U 回の暗号化を必要とする. また, データの追加は αU 回の暗号化により行われ, データの削除は αU 回の暗号文削除と 1 回の暗号化により行われる.
これらを実験結果と比較するために, 図 5, 図 6 において, 1
学部に相当するユーザやデータが既に蓄積されている状態の処
理時間を 1 として, 各計測時間をプロットしたものを図 7 および図 8 に示す. 先に示した平均計算量に従うように, 本手法におけるユーザ追加や, 比較対象におけるデータ追加およびユー
ザ削除では, 操作に掛かる時間は既存のユーザ数に比例している. また, 比較対象におけるユーザの追加および削除の計算には, 既存のデータ数に比例した時間が掛かることが確認できる.
比較対象におけるデータ削除時間についてはユーザ数に対する比例関係が見られなかったが, これは暗号文生成のために行われる暗号化が暗号文削除の時間を無視できるほど長い時間を必要としたためである.

1E+08!

6!

ユーザの追加 (比較対象)!

5!

ユーザの削除 (比較対象)!

4!

データの追加 (比較対象)!

3!

データの削除 (比較対象)!

1E+07!
1E+06!
1E+05!
[ms]

[倍]

7!

0!

100000!

200000!

300000!

400000!

ユーザ (比較対象)!

1E+01!

データの追加 (本手法)!

0!

ユーザ (本手法)!

1E+02!

ユーザの削除 (本手法)!

1!

サーバ (比較対象)!

1E+03!

ユーザの追加 (本手法)!

2!

サーバ (本手法)!

1E+04!

1E+00!

データの削除 (本手法)!

#1!

#3!

トリプル数 (暗号化前)

#5!

#6!

#14!

LUBM クエリ

図 7 1 学部に相当するユーザ数における実行時間 (相対).

図9

クエリの応答時間.

[倍]

7!
6!

ユーザの追加 (比較対象)!

5!

ユーザの削除 (比較対象)!

4!

データの追加 (比較対象)!

3!

データの削除 (比較対象)!
ユーザの追加 (本手法)!

2!

ユーザの削除 (本手法)!

1!

データの追加 (本手法)!

0!
0!

1000!

2000!

3000!

4000!

5000!

データの削除 (本手法)!

ユーザ数

図 8 1 学部に相当するデータ数における実行時間 (相対).

測した結果を示す. なお, これらの処理の計算量は, 問い合わせ
元のユーザのクラスに依存しない.
インデックスは, 個人とプレディケートをそれぞれノードお
よび辺とするグラフ上で幅優先探索を行うことにより作成することができる. 全ての個人に対して探索を行う必要があるため,その計算量は個人の数の 2 乗に比例する.
また, 個人間関係に基づくアクセス制御においては, 事前イ
ンデックスの有無により計算時間に差が生じる. 実験結果から,
アクセス制御そのものに掛かる時間に対しては非常に小さい差

5. 3 検索

図 9 は, 1 大学 1 学部のみに対応するユーザおよびデータを蓄積した状態において, ユーザによる問い合わせに対して結果であるものの, 個人の数に比例することが示されている. そのため, 可能であれば事前にインデックスを作成しておくことが望ましいといえる.

として全てのソリューション集合を返すまでの時間を計測した
250000!

として返すソリューションの数はそれぞれ, 4 個, 6 個, 719 個,

200000!

678 個, 532 個である.

150000!

本論文の提案する手法においては, プロキシサーバはデータベースに対して問い合わせを行って結果を取得し, ユーザはその結果を復号する. 比較対象においては, サーバは RDF グラフ
からユーザが復号可能な部分のみを抽出し, ユーザはその部分[ms]

結果を示す. ただし, #1, #3, #5, #6, #14 のクエリが結果

300!
250!
200!

100000!
50000!

インデックス作成

150!

個人間関係によるアクセス制
御 (事前インデックスあり)!

100!

個人間関係によるアクセス制
御 (事前インデックスなし)!

50!

0!
0!
0E+0! 5E+4! 1E+5! 2E+5! 2E+5! 3E+5! 3E+5! 4E+5!

事前インデックスの有無による差 (右軸)!

個人の数グラフを復号してローカルシステム上で問い合わせを行う.
一般に, グラフパターンを構成するトリプルパターンの個数

図 10

個人間関係に基づくアクセス制御の実行時間.

が多いほど, 中間生成されるインメモリデータが増加するため,

SPARQL による問い合わせの計算に時間が掛かる [16]. 実際に,複数のトリプルパターンにより構成される #1, #3 および #5のクエリにおいて, 問い合わせを行う側では計算のためにより長い時間を必要とした. 実験結果からは比較対象におけるユー
ザ側の応答時間に変化はほとんど見られないが, これは全てのクエリに対してユーザがアクセス可能な部分全体を復号する必要があったためである. 一方, 本手法ではユーザは SPARQL の返すソリューション集合のみを復号すればよい. このため, ユー
ザ側の計算時間はソリューションの個数に比例している.
この実験では, 本論文の提案する手法と比較対象との差はク
エリ#5 で最小となり, クエリ#14 で最大となった. 比較対象
は, 本手法に対してクエリ#5 で 17 倍の時間を必要とし, クエ
リ#14 では 1195 倍の時間を必要とした.

5. 4 個人間関係に基づくアクセス制御
図 10 は, 個人間関係に基づくアクセス制御や, その計算のために用いることの可能なインデックスの作成に要した時間を計

6. お わ り に
6. 1 ま と め
本論文では, ユーザのクラスやデータにアクセスするためのレベルを利用し, プロキシ再暗号化による秘匿化を行うことで,データやユーザの追加や削除を効率良く行うことのできる秘匿
情報アクセス手法を提案した.
また, 提案手法の性能を確かめるために, ミドルレイヤアプリ
ケーションとして手法を実装し, LUBM によるデータセットを用いて, データやユーザの追加や削除に加えて, 検索や個人間関係に基づくアクセス制御に関して評価実験を行った. 実験の結果として, ユーザを単位とする既存の暗号化手法よりも, 効率
良くユーザのアクセスを制御できることが示された. 特にユーザを削除する操作において, 提案手法は再度の暗号化を行う必要がないため, 1010 倍以上の性能が得られた. また, ユーザによる検索問い合わせについては, 既存手法と比較して最小で 17倍, 最大で 1195 倍の性能が得られた.

6. 2 今後の課題
まず, 実用に向けて, より精密にセキュリティ評価を行う必要がある. 特に, プロキシ再暗号化に関する研究で一般に想定されている脅威に関して, それらへの耐性を評価しなければならない [17]. 例えば, 本手法では情報の保有者が自身の公開鍵で暗号化したままサーバに送信可能であるため “データ秘匿性” を持つことは明らかであるが, 権限のないユーザとプロキシが結託した場合にどれだけの情報が漏洩する可能性があるかに関す
る “耐結託性” について議論することは意義が大きい.
また, 本論文では, 単純な暗号化だけでなく, ユーザと個人の間の関係に注目したアクセス制御を提案した. そのため, 提案手法は, CryptDB [3] のようなミドルレイヤアプリケーションによるアプローチと同様であり, 完全なセキュリティを保証する
ものではない. しかしながら, 暗号化手法の適切な選択によって, 暗号化の安全性をより高めることはできると考えられる. 例
えば, 検索可能暗号のようにトラップドアの利用をユーザやプ
ロキシに対して公開すれば, 関連する情報の露出を低減し, 同時に秘密鍵生成局への依存を小さくすることもできるだろう.
実行速度に関して, 提案手法や評価実験では計算の並列化を行っていないが, 幾つかのアルゴリズムでは並列計算の適用も可能である. 例えば, 再暗号化対象の各ステートメントや, イン
デックス作成対象の各個人に対して, 並列に計算することでより高速な処理を期待できるだろう.
また, 評価実験において利用した LUBM は, 規模の大きいオントロジに対するテストのためのベンチマークとして事実上の標準であるが, ノード間の関連が疎であるため, 現実性を欠いているという批判がある [18]. 本論文でも, 個人間関係を利用するアクセス制御およびデータ検索のために, 幾つかの推論規則
を人工的に導入した. より精密な評価を行うためには, 個人やユーザの間の関係を含むことを前提としたデータセットやベンチマークを利用すべきである. 例えば, SIBM [19] のように, 災
害時や災害後の復旧および復興をケースとした, 避難所の位置や避難者の状況および避難者間の関係といった情報を含むデー
タセットを生成するベンチマークは, 本論文の提案する手法の評価に適していると考えられる.

謝

辞本研究の一部は, 日本学術振興会科学研究費補助金基盤研究(A) (#25240014) の助成により行われた.

文

献[1] 総 務 省 関 東 総 合 通 信 局 防 災 対 策 推 進 室.
災害時に 活 用 で き る 情 報 伝 達 手 段.
Retrieved December
31, 2014, from: http://www.soumu.go.jp/soutsu/kanto/saigai/osirase/saigaimanyuaru.pdf.
[2] 電気情報通信学会. 知識ベース 知識の森 3 群 7 編 2 章. Retrieved December 31, 2014, from: http://www.ieice-hbkb.
org/files/03/03gun 07hen 02.pdf.
[3] Raluca Ada Popa, Catherine M. S. Redﬁeld, Nickolai Zeldovich, and Hari Balakrishnan. CryptDB: Protecting conﬁdentiality with encrypted query processing. In 23rd Symposium on Operating Systems Principles, pp. 85–100. ACM,

October 2011.
[4] Giuseppe Ateniese, Kevin Fu, Matthew Green, and Susan
Hohenberger. Improved proxy re-encryption schemes withapplications to secure distributed storage. ACM Transactions on Information and System Security, Vol. 9, No. 1,
pp. 1–30, February 2006.
[5] Matt Blaze, Gerrit Bleumer, and Martin Strauss. Divertible
protocols and atomic proxy cryptography. In Proceedings ofthe International Conference on the Theory and Application of Cryptographic Techniques, Vol. 1403, pp. 127–144.
Springer, 1998.
[6] Florian Haag, Steﬀen Lohmann, and Thomas Ertl. Sparqlﬁlterﬂow: SPARQL query composition for everyone. The
Semantic Web: European Semantic Web Conference, pp.
362–366, 2014.
[7] 総務省情報流通行政局情報流通振興課. オープンデータ戦略の推進. Retrieved January 8, 2015, from: http://www.soumu.
go.jp/menu seisaku/ictseisaku/ictriyou/opendata/.
[8] Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. Semantics and complexity of SPARQL. ACM Transactions on
Database Systems, Vol. 34, No. 3, pp. 16:1–16:45, September 2009.
[9] Richard Cyganiak, David Wood, and Markus Lanthaler.
RDF 1.1 concepts and abstract syntax.
Recommendation, W3C, February 2014.
Retrieved
January 8, 2015, from: http://www.w3.org/TR/2014/
REC-rdf11-concepts-20140225/.
[10] Mark Giereth. On partial encryption of RDF-graphs. In
Proceedings of the 4th International Conference on The Semantic Web, pp. 308–322. Springer-Verlag, 2005.
[11] Naizhen Qi and Michiharu Kudo. XML access control with
policy matching tree. In European Symposium on Researchin Computer Security, Vol. 3679 in Lecture Notes in Computer Science, pp. 3–23. Springer Berlin Heidelberg, 2005.
[12] Dan Brickley and R.V. Guha.
RDF schema 1.1.
Recommendation, W3C, February 2014.
Retrieved
January 26, 2015, from: http://www.w3.org/TR/2014/
REC-rdf-schema-20140225/.
[13] Boris Motik, Peter F. Patel-Schneider, and Bijan Parsia.
OWL 2 web ontology language structural speciﬁcation and functional-style syntax (second edition).
Recommendation, W3C, December 2012.
Retrieved
January 26, 2015, from: http://www.w3.org/TR/2012/
REC-owl2-syntax-20121211/.
[14] Yuanbo Guo, Zhengxiang Pan, and Jeﬀ Heﬂin. LUBM: A
benchmark for OWL knowledge base systems. Web Semantics: Science, Services and Agents on the World Wide Web,
Vol. 3, No. 2-3, pp. 158–182, October 2005.
[15] Gang Wu, Juanzi Li, and Kehong Wang. System II: A
hypergraph based native RDF repository. In Proceedingsof the 17th International Conference on World Wide Web,
pp. 1035–1036. ACM, 2008.
[16] Jiewen Huang, Daniel J. Abadi, and Kun Ren. Scalable
SPARQL querying of large RDF graphs. In Proceedings of
the Very Large Database Endowment, Vol. 4, pp. 1123–1134,
2011.
[17] Pei-Shan Chung, Chi-Wei Liu, and Min-Shiang Hwang.
A study of attribute-based proxy re-encryption scheme incloud environments. International Journal of Network Security, Vol. 16, No. 1, pp. 1–13, January 2014.
[18] Timo Weithöner, Thorsten Liebig, Marko Luther, SebastianBöhm, Friedrich Von Henke, and Olaf Noppens. Real-world
reasoning with owl. In The Semantic Web: Research andApplications, pp. 296–310. Springer, 2007.
[19] Nguyen Hoai Nam, Yoshitaka Arahori, and Haruo Yokota.
SIBM: 避難場所情報に対する RDF データセットベンチマーク
ツール. 第 7 回データ工学と情報マネジメントに関するフォー
ラム, 2015.