具有固定大小搜尋符號之隱私的字串搜尋

Abstract

目前有許多密碼學上的方法能夠支援在加密資料上進行關鍵字的搜尋，但是較少相關的方法能夠支援更一般化的查詢方式，例如：字串搜尋。 在我們所提出的方法中，標籤代表加密過後的文件，搜尋符號則是代表用來搜尋文件的字串加密。根據我們所提出的方法，針對一份加密過後的文件當中，我們可以得知是否其包含一個特定的字串。並且在計算上難題的假設之下，我們可以證明我們的方法是安全的。 就我們所知，目前有一個相關的方法是針對在加密資料上進行字串搜尋，不過這個方法所需要的搜尋符號大小較大。在我們提出來的方法中，我們可以將搜尋符號大小降低到固定大小，並且我們希望盡可能減少網路傳輸的通訊量以及減少使用者端的計算負擔。

Nowadays, many cryptographic schemes have been developed to achieve search on encrypted data, but most of them are keyword search. Few of schemes can support more general query like string matching on encrypted data.

In our protocol, the tag stands for the encrypted text, and the token stands for the encrypted pattern. We propose a scheme which can determine whether the encrypted text contains the dedicated pattern. Under the computational assumption, we can prove it secure.

As far as we know, there exists one protocol to our problem, but its token size is large. We can reduce the token size to the constant size, and we hope to reduce the communication size in the network and the computational time in the user side as far as possible.