Secure and efficient substring searchable symmetric encryption using advanced data structure

使用先进数据结构的安全高效的子串可搜索对称加密

• 批准号: 20K11808
• 负责人: 山本 博章
• 金额: $ 2.75万
• 依托单位: Shinshu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K11808/
• 关键词: 部分文字列検索可能暗号; DAWG; 正規表現検索; de Bruijnグラフ; 検索可能暗号; 部分文字列検索; 簡潔データ構造; データ構造; 有限オートマトン; 正規表現; 文字列検索

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

The next three points are the first to be implemented. 1. DAWG uses partial word graphs to search for possible code improvements: DAWG(directed acyclic word graph) and DAWG(directed acyclic word graph) are critical to the acceptance of partial word graphs. The applicant shall open the DAWG with a new part of the text string to search for possible codes. This year's paper was published The DAWG is composed of linear time frames, digital index frames, and high speed frames. 2. The development of a regular performance search engine for possible codes: the creation of a coded index engine for Bruijn and the development of a basic search engine. The k-gram appears in any number of words in the text, and the k-gram structure appears in the text. The frequency of occurrence of text strings in the coded index is different from that in the k-gram. The results, safety and composition of the system are expected. This year, the performance of the closure algorithm (finite set of text columns) for the search of possible codes was launched. Closure calculus is introduced into the case, security proof, detection efficiency improvement, and future issues. 3. To improve the efficiency of the system, to consider the feasibility of mobile search, to develop a method for improving the search efficiency: to improve the search efficiency, to improve the search efficiency. The method of improvement is discussed in the form of update, addition, etc. This is the first time I've ever been able to add a function.

项目成果

検証可能な機能に向けた検索可能暗号

用于可验证功能的可搜索密码学

• 发表时间: 2021
• 作者: 小澤響平;山本博章;藤原洋志
• 通讯作者: 藤原洋志

正規表現に対する検索可能暗号の改良

改进了正则表达式的可搜索密码

• 发表时间: 2021
• 作者: 伊藤天啓;山本博章;藤原洋志
• 通讯作者: 藤原洋志

動的データに向けた部分文字列検索可能暗号

动态数据的子串可搜索密码学

• 发表时间: 2021
• 作者: 藤村享平;山本博章;藤原洋志
• 通讯作者: 藤原洋志

ProVerifによる検索可能暗号の形式的安全性検証について

关于使用 ProVerif 对可搜索密码进行形式化安全验证

• 发表时间: 2022
• 作者: Yamakawa Daiki;Okimoto Takashi;Teerakanok Songpon;Inomata Atsuo;Uehara Tetsutaro;鈴木孝誠，山本博章，三重野武彦，荒井研一，岡崎裕之，布田裕一
• 通讯作者: 鈴木孝誠，山本博章，三重野武彦，荒井研一，岡崎裕之，布田裕一

正規表現に対する最短文字列検索アルゴリズムの並列化

正则表达式最短字符串搜索算法的并行化

• 发表时间: 2021
• 作者: 大邊陽介;山本博章;藤原洋志
• 通讯作者: 藤原洋志