正規表現検索問題は，正規表現とテキスト文書が与えられたとき，そのテキストの部分文字列で正規表現にマッチする文字列すべてを求める問題である。正規表現検索に対し、暗号化されいないデータに対しては多くのアルゴリズムが提案されてきたが、暗号化したデータに向けた検索法に関する研究がほとんどない。提案されている方法は効率が悪い。本論文は、暗号化データ上での正規表現検索に対し、ユーザが利用するメモリ量が少なく、適応的安全性を満たす新たな検索法を提案する。