表達式密文搜尋

Abstract

線上儲存裝置提供更符合經濟效益的方式管理數位資料，而使用加密法來保護這些數位資料是必要的，但傳統加密法其密文無法直接被利用或搜尋。目前密碼學社群中發展的「密文可搜尋加密法」能將關鍵字轉換成密文，而搜尋條件轉換成搜尋標記，並提供比對函數測試密文是否符合搜尋標記。因此，使用者能安全的將密文存放在線上儲存裝置，並委派搜尋標記以存取符合條件的密文。目前以增加「密文可搜尋加密法」的表達性（Expressiveness）為主要研究發展的方向，現有的設計主要是支援「以關鍵字為搜尋單位」的搜尋條件，無法有效率的搜尋部分關鍵字或是搜尋符合特定樣式（Pattern）的關鍵字。

本論文提出的三個表達式密文搜尋加密法設計，皆基礎於橢圓曲線與雙線性配對密碼學，本論文主要的貢獻分為三大部分：（1）應用現有「以關鍵字為搜尋單位」的密文可搜尋加密法，設計各種在密文集上計算統計量之程序，如計算密文集的變異數或是線性回歸；（2）提出「以字元及其位置為搜尋單位」的密文可搜尋加密法，代表性的部分關鍵字搜尋條件如「關鍵字以``ABC"開頭」或「關鍵字的第三個字元為`D'」等；（3）提出能夠支援以「正規表達式」描述的搜尋條件之密文可搜尋加密法，代表性的樣式搜尋條件如「關鍵字中`A'符號出現在`B'符號前」和「關鍵字中包含``ABC"子字串」等。藉由本論文提出的表達式密文搜尋加密法，可以讓線上儲存裝置利用使用者委派的搜尋標記，找出符合條件的密文，大幅增加密文的可利用性，讓使用者能安全且更便利的採用線上儲存服務。

Nowadays, online storage services are available to host and manage user data in a more economical way than ever before. Studies have suggested the use of encryption schemes while posing a demand for searching directly on encrypted data. Recently, searchable encryption schemes are proposed to transform keywords into ciphertexts and search predicates into search tokens. In addition, the embedded testing function in these schemes can check whether the ciphertext satisfies the search token or not. Therefore, users can delegate search tokens to service providers to retrieve the interested encrypted data. However, the existing schemes deal with keyword-based predicates without supporting the predicates of partial keywords or specific patterns. Therefore, to enrich the expressiveness of searchable encryption schemes becomes a major research direction.

This dissertation proposes three encryption schemes which are all based on elliptic curves and bilinear pairing. The contribution of this dissertation is mainly divided into three parts: (1) We make use of the existing keyword-based searchable encryption scheme to devise statistical procedures for a collection of ciphertexts such as variance or linear regression. (2) We propose a position-aware symbol-based construction for the predicates of partial keywords. This construction provides predicates such as ``the leading pattern is `ABC'" or ``the third position is `D'". (3) Finally, we devise a more advanced symbol-based searchable encryption scheme for the predicates described by regular languages. This construction supports more flexible symbol-based predicates such as ``with a symbol `B' before a symbol `A'" or ``with a substring `ABC'". With the help of these schemes, users can enjoy more efficient and flexible online storage services, while preserving keyword and predicate privacy.