A searchable symmetric encryption (SSE) scheme is a method that searches encrypted data without decrypting it. In this paper, we address the substring search problem such that for a set D of documents and a pattern p, we find all occurrences of p in D. Here, a document and a pattern are defined as a string. A directed acyclic word graph (DAWG), which is a deterministic finite automaton, is known for solving a substring search problem on a plaintext. We improve a DAWG so that all transitions of a DAWG have distinct symbols. Besides, we present a space-efficient and secure substring SSE scheme using an improved DAWG. The proposed substring SSE scheme consists of an index with a simple structure, and the size is O(n) for the total size n of documents.
Hiroaki YAMAMOTO
Shinshu University
Ryosuke ODA
Shinshu University
Yoshihiro WACHI
NTT COMWARE CORPORATION
Hiroshi FUJIWARA
Shinshu University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Hiroaki YAMAMOTO, Ryosuke ODA, Yoshihiro WACHI, Hiroshi FUJIWARA, "Substring Searchable Symmetric Encryption Based on an Improved DAWG" in IEICE TRANSACTIONS on Fundamentals,
vol. E105-A, no. 12, pp. 1578-1590, December 2022, doi: 10.1587/transfun.2021EAP1122.
Abstract: A searchable symmetric encryption (SSE) scheme is a method that searches encrypted data without decrypting it. In this paper, we address the substring search problem such that for a set D of documents and a pattern p, we find all occurrences of p in D. Here, a document and a pattern are defined as a string. A directed acyclic word graph (DAWG), which is a deterministic finite automaton, is known for solving a substring search problem on a plaintext. We improve a DAWG so that all transitions of a DAWG have distinct symbols. Besides, we present a space-efficient and secure substring SSE scheme using an improved DAWG. The proposed substring SSE scheme consists of an index with a simple structure, and the size is O(n) for the total size n of documents.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021EAP1122/_p
Copy
@ARTICLE{e105-a_12_1578,
author={Hiroaki YAMAMOTO, Ryosuke ODA, Yoshihiro WACHI, Hiroshi FUJIWARA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Substring Searchable Symmetric Encryption Based on an Improved DAWG},
year={2022},
volume={E105-A},
number={12},
pages={1578-1590},
abstract={A searchable symmetric encryption (SSE) scheme is a method that searches encrypted data without decrypting it. In this paper, we address the substring search problem such that for a set D of documents and a pattern p, we find all occurrences of p in D. Here, a document and a pattern are defined as a string. A directed acyclic word graph (DAWG), which is a deterministic finite automaton, is known for solving a substring search problem on a plaintext. We improve a DAWG so that all transitions of a DAWG have distinct symbols. Besides, we present a space-efficient and secure substring SSE scheme using an improved DAWG. The proposed substring SSE scheme consists of an index with a simple structure, and the size is O(n) for the total size n of documents.},
keywords={},
doi={10.1587/transfun.2021EAP1122},
ISSN={1745-1337},
month={December},}
Copy
TY - JOUR
TI - Substring Searchable Symmetric Encryption Based on an Improved DAWG
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1578
EP - 1590
AU - Hiroaki YAMAMOTO
AU - Ryosuke ODA
AU - Yoshihiro WACHI
AU - Hiroshi FUJIWARA
PY - 2022
DO - 10.1587/transfun.2021EAP1122
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E105-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2022
AB - A searchable symmetric encryption (SSE) scheme is a method that searches encrypted data without decrypting it. In this paper, we address the substring search problem such that for a set D of documents and a pattern p, we find all occurrences of p in D. Here, a document and a pattern are defined as a string. A directed acyclic word graph (DAWG), which is a deterministic finite automaton, is known for solving a substring search problem on a plaintext. We improve a DAWG so that all transitions of a DAWG have distinct symbols. Besides, we present a space-efficient and secure substring SSE scheme using an improved DAWG. The proposed substring SSE scheme consists of an index with a simple structure, and the size is O(n) for the total size n of documents.
ER -