Secure and efficient substring searchable symmetric encryption using advanced data structure

次の3点について実施した。１．DAWGを用いた部分文字列検索可能暗号の改善：文字列に対するDAWG(directed acyclic word graph)とは、その文字列のすべての部分文字列を受理する決定性有限オートマトンである。申請者は、DAWGをその状態遷移の記号がすべて異なるように改良した拡張型DAWGを用いた新たな部分文字列検索可能暗号を開発した。本年度は得られた結果を論文としてまとめ公表した。さらに、テキストからDAWGを構成する線形時間アルゴリズムを利用し、暗号化索引を高速に構成するようにアルゴリズムを改善した。２．正規表現検索に向けた検索可能暗号の開発：テキストに対する暗号化索引の作成に向けde Bruijnグラフに基づく手法を提案した。テキストに対するde Bruijnグラフは、任意の正の数kに対し、テキスト中に出現するk-gram（長さkの部分文字列）をノードとしたグラフ構造である。すべてのノードは異なるk-gramからなるため、このグラフをベースとした暗号化索引はテキスト中に出現する文字列の出現頻度を隠すことができる。その結果、安全性の高いシステムの構成が期待できる。本年度は、正規表現の閉包演算ない表現（文字列の有限集合を表す）に対し検索可能暗号を開発した。閉包演算を導入した場合、安全性の証明、さらなる検索効率の改良については今後の課題である。３．効率性の改善に向け局所性を考慮した動的検索可能暗号の開発：アシャロフらは、安全性の強度を落とさずに検索効率を上げるため、サーバに保存する暗号化索引に対し、局所性の概念を導入し、検索効率を改善する方法を提案した。彼らは、カートモラらの手法を改善する形で議論しているため、追加等の更新作業について議論していない。ここでは、追加機能を考慮した手法について提案した。

次の3点について実施した。１．DAWGを用いた部分文字列検索可能暗号の改善：文字列に対するDAWG(directed acyclic word graph)とは、その文字列のすべての部分文字列を受理する決定性有限オートマトンである。申請者は、DAWGをその状態遷移の記号がすべて異なるように改良した拡張型DAWGを用いた新たな部分文字列検索可能暗号を開発した。本年度は得られた結果を論文としてまとめ公表した。さらに、テキストからDAWGを構成する線形時間アルゴリズムを利用し、暗号化索引を高速に構成するようにアルゴリズムを改善した。２．正規表現検索に向けた検索可能暗号の開発：テキストに対する暗号化索引の作成に向けde Bruijnグラフに基づく手法を提案した。テキストに対するde Bruijnグラフは、任意の正の数kに対し、テキスト中に出現するk-gram（長さkの部分文字列）をノードとしたグラフ構造である。すべてのノードは異なるk-gramからなるため、このグラフをベースとした暗号化索引はテキスト中に出現する文字列の出現頻度を隠すことができる。その結果、安全性の高いシステムの構成が期待できる。本年度は、正規表現の閉包演算ない表現（文字列の有限集合を表す）に対し検索可能暗号を開発した。閉包演算を導入した場合、安全性の証明、さらなる検索効率の改良については今後の課題である。３．効率性の改善に向け局所性を考慮した動的検索可能暗号の開発：アシャロフらは、安全性の強度を落とさずに検索効率を上げるため、サーバに保存する暗号化索引に対し、局所性の概念を導入し、検索効率を改善する方法を提案した。彼らは、カートモラらの手法を改善する形で議論しているため、追加等の更新作業について議論していない。ここでは、追加機能を考慮した手法について提案した。