6L-1
検索可能暗号を高速化するための簡潔データ構造を用いた索引手法
○北村優汰（名工大），福田洋治（愛知教育大），廣友雅徳（佐賀大），毛利公美（岐阜大），中井敏晴（国立長寿医療研究センター），白石善明（神戸大）
暗号文を復号することなく検索できる検索可能暗号において，検索タグから数ビットの情報
漏れを許容することで索引生成を可能にし，検索を高速化する方式が提案されている．補助
記憶の読み書きはメモリよりもはるかに遅いため，大規模なデータを検索する場合は，でき
るだけ小さなサイズの索引を生成し，メモリ上に展開することが求められる．
本稿では，索引のサイズを小さくするために，ビット列に対する簡潔データ構造である完備
辞書をビットマップインデックスに適用する手法を提案する．本手法では，簡潔データ構造
の基本的な演算であるrank，selectを使用する．索引として用いるビット列のサイズを最適
値の約2倍以内に抑えつつ，2つの演算を定数時間で実行することで検索の高速化を図れてい
ることを示している．
footer 情報処理学会 セキュリティ プライバシーポリシー 倫理綱領 著作権について