Truy vấn hiệu quả dữ liệu ký tự mã hóa trong cơ sở dữ liệu thuê ngoài

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

13
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết Truy vấn hiệu quả dữ liệu ký tự mã hóa trong cơ sở dữ liệu thuê ngoài tập trung nghiên cứu cách thức xây dựng chỉ mục mã hóa hỗ trợ tìm kiếm hiệu quả cho các trường dữ liệu ký tự đã mã hóa trên cơ sở dữ liệu quan hệ thuê ngoài.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Truy vấn hiệu quả dữ liệu ký tự mã hóa trong cơ sở dữ liệu thuê ngoài

Kỷ yếu Hội nghị Khoa học công nghệ Quốc gia lần thứ XV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 03-04/11/2022 DOI: 10.15625/vap.2022. 0201 TRUY VẤN HIỆU QUẢ DỮ LIỆU KÝ TỰ MÃ HÓA TRONG CƠ SỞ DỮ LIỆU THUÊ NGOÀI Hoàng Ngọc Cảnh1, Nguyễn Hiếu Minh2 1 Đại học Thương mại 2 Ban Cơ yếu Chính phủ canhhn@tmu.edu.vn, hieuminhmta@gmail.com TÓM TẮT: Bài báo này tập trung nghiên cứu cách thức xây dựng chỉ mục mã hóa hỗ trợ tìm kiếm hiệu quả cho các trường dữ liệu ký tự đã mã hóa trên cơ sở dữ liệu quan hệ thuê ngoài. Để giải quyết vấn đề này, chúng tôi đề xuất lược đồ New Bloom Filter Index - Searchable Symmetric Encryption (NBFI-SSE) và áp dụng lược đồ này lên mô hình Proxy cho phép tìm kiếm chuỗi con trên chỉ mục mã hóa với hiệu năng cao cùng tập kết quả dữ liệu mã trả về với độ dư thừa thấp. Lược đồ đề xuất có 04 giai đoạn như một lược đồ SSE tiêu chuẩn, bao gồm: GenSecretMetadata, BuildIndex, TranslateQuery và SearchIndex, cho phép biến đổi mỗi chuỗi dữ liệu rõ 𝐴 𝑠 thành hai phiên bản mã hóa để lưu trên cơ sở dữ liệu thuê ngoài. Phiên bản thứ nhất là dữ liệu mã hóa của 𝐴 𝑠 được sinh ra bởi các thuật toán mã hóa tiêu chuẩn, phiên bản còn lại là một chỉ mục mã hóa hỗ trợ tìm kiếm (Searchable Index) được tạo ra bởi thuật toán BuildIndex dựa trên ý tưởng bộ lọc Bloom và một cấu trúc đặc biệt mà chúng tôi xây dựng là tập các cặp ký tự kết nối phân biệt theo khoảng cách 𝑢 trên 𝐴 𝑠 . Chỉ mục tìm kiếm này cho phép triển khai truy vấn 𝐿𝐼𝐾𝐸 với hiệu suất cao, chống rò rỉ thông tin bản rõ, an toàn trước các kịch bản tấn công phổ biến và đặc biệt ngăn chặn được tấn công mẫu truy vấn (Query pattern attack). Từ khóa: bộ lọc bloom, cặp ký tự kết nối, khoảng cách u, mẫu truy vấn, mô hình proxy. I. GIỚI THIỆU Sự bùng nổ của cuộc Cách mạng công nghiệp 4.0 đã thúc đẩy các tổ chức chuyển dịch dữ liệu lên đám mây để lưu trữ và quản lý. Tuy nhiên, người sở hữu dữ liệu sẽ phải đối mặt với vấn đề mất kiểm soát cũng như rò rỉ thông tin của dữ liệu. Để giải quyết vấn đề này, toàn bộ dữ liệu sẽ được mã hóa bởi các thuật toán tiêu chuẩn như AES [1] trước khi chuyển lên đám mây, nhưng chính việc này lại cản trở quá trình khai thác dữ liệu từ người dùng do không thể thực hiện được các lệnh truy vấn trên dữ liệu đã mã hóa. Cho tới nay, nhiều lược đồ hỗ trợ tìm kiếm trên dữ liệu mã (SE) [2 - 7] đã được xây dựng, trong đó tập trung chính vào kỹ thuật tìm kiếm chính xác theo từ khóa trên các lược đồ mã hóa có thể tìm kiếm đối xứng hoặc phi đối xứng. Nghiên cứu này tập trung vào kỹ thuật tìm kiếm chuỗi ký tự con bất kỳ (là một yêu cầu phức tạp hơn so với tìm kiếm theo từ khoá của các nghiên cứu trước đó) trên trường dữ liệu ký tự đã mã hoá tại cơ sở dữ liệu thuê ngoài. Cụ thể chúng tôi có một số đóng góp nổi bật như sau: - Đề xuất lược đồ New Bloom Filter Index - Searchable Symmetric Encryption (NBFI-SSE) với 4 giai đoạn và ứng dụng lược đồ này vào mô hình Proxy cho phép tìm kiếm chuỗi con với cú pháp 𝐿𝐼𝐾𝐸 qua 3 pha. - Xây dựng chỉ mục đặc biệt hỗ trợ tìm kiếm (Searchable Index) dựa trên bộ lọc Bloom cải tiến, kết hợp với một cấu trúc đặc biệt là tập các cặp ký tự kết nối phân biệt theo khoảng cách 𝐮 trên 𝐀 𝐬 (Định nghĩa 2). - Thuật toán tìm kiếm trên Searchable Index có độ phức tạp cỡ 𝑂(𝑘 + 1) với k là số hàm băm được sử dụng trong bộ lọc Bloom. Kết quả tìm kiếm cho thấy tỷ lệ lọc được cải thiện đáng kể so với các nghiên cứu cũng dùng kỹ thuật bộ lọc Bloom để truy vấn trên dữ liệu ký tự mã hoá trước đó. - Các phân tích về lý thuyết và thử nghiệm cho thấy chỉ mục đã xây dựng có thể chống được các tấn công như phân tích thống kê bản mã, phân tích mẫu truy vấn,… Phần còn lại của bài báo này được tổ chức như sau: Phần II trình bày các nghiên cứu liên quan. Phần III giới thiệu về các quy ước và kiến thức nền tảng. Phần IV đề xuất lược đồ NBFI-SSE, mô hình Proxy và cách thức vận hành lược đồ. Phần V thảo luận về tính bảo mật của mô hình. Phần VI thể hiện kết quả thực nghiệm của nghiên cứu. Cuối cùng là kết luận bài báo trong Phần VII. II. TỔNG QUAN NGHIÊN CỨU Lĩnh vực tìm kiếm trên dữ liệu mã hóa đã được đề cập và nghiên cứu hơn một thập kỷ gần đây, các lược đồ SE phổ biến được nhắc đến trong các công trình về mã đối xứng có thể tìm kiếm (SSE) [2, 3, 4, 7] cũng như mã hóa bất đối xứng có thể tìm kiếm (PKSE) [5, 6]. Trong các lược đồ SSE, Song và cộng sự [2] là những người đi đầu khi đề xuất một lược đồ có tính bảo mật được chứng minh rõ ràng nhưng thời gian tìm kiếm lại tuyến tính độ dài văn bản, hơn nữa việc coi mỗi văn bản là một chuỗi các từ khóa tìm kiếm có độ dài bằng nhau sẽ làm cho dạng thức của từ khoá không giống thực tế.
Hoàng Ngọc Cảnh, Nguyễn Hiếu Minh 9 Với các lược đồ PKSE, Boneh và cộng sự [5] là những người đầu tiên đề xuất mã hóa có thể tìm kiếm được bằng cách sử dụng mật mã không đối xứng. Tuy nhiên, các lược đồ này là có hiệu năng kém hơn SSE và không thích hợp cho việc triển khai trong các bài toán thực tiễn. Trong các trích dẫn về những nghiên cứu nói trên chủ yếu tập trung vào hỗ trợ tìm kiếm theo từ khóa chính xác. Li và cộng sự [10] là người đầu tiên đề xuất lược đồ tìm kiếm từ khóa mờ trên dữ liệu được mã hóa. Các tác giả đã phát triển giải pháp xây dựng các tập từ khóa mờ dựa trên việc thu thập tài liệu và sau đó sử dụng khoảng chỉnh sửa để đo mức độ giống nhau giữa truy vấn từ khóa và truy vấn tập khóa mờ. Một số lược đồ SSE khác cho phép tìm kiếm chuỗi con đã được đề xuất trong những năm qua có thể phân loại thành hai nhóm. Nhóm thứ nhất [11, 15, 16, 18] sử dụng các cấu trúc dữ liệu phổ biến hỗ trợ tìm kiếm chuỗi con trên bản rõ để áp dụng phù hợp vào bản mã, nhóm thứ hai [6,9] đề xuất các ý tưởng mới trong việc thiết kế và tìm kiếm chuỗi con trên các chỉ mục mã hoá hỗ trợ tìm kiếm. III. CÁC QUY ƯỚC VÀ KIẾN THỨC LIÊN QUAN 3.1. Một số quy ước - ký hiệu Quan hệ 𝑅(𝐼𝐷, 𝑋1 , 𝑋2 ,…𝑋 𝑡 , …𝑋 𝑛 ) với 𝑋 𝑡 là trường dữ liệu nhạy cảm kiểu chuỗi ký tự. Khi đó 𝑅 sẽ được cấu trúc lại thành 𝑅 𝐸 khi lưu trên cơ sở dữ liệu thuê ngoài: 𝑅 𝐸 (𝐼𝐷, 𝑋1 , 𝑋2 ,… 𝑋 𝑡𝐸 , …𝑋 𝑛 , 𝑆𝐼𝑋 𝑡 ), trong đó 𝑋 𝑡𝐸 là trường mã hóa của trường 𝑋 𝑡 , 𝑆𝐼𝑋 𝑡 là chỉ mục hỗ trợ tìm kiếm tương ứng với 𝑋 𝑡 . Cho 𝐴 𝑠 là một chuỗi ký tự và 𝑠𝐾𝑒𝑦 là khóa bí mật, khi đó 𝐴 𝑠𝐸 = 𝑓 𝐸𝑛𝑐 (𝐴 𝑠 , 𝑠𝐾𝑒𝑦) được gọi là chuỗi mã hóa của 𝐴 𝑠 và 𝑓 𝐸𝑛𝑐 là hàm mã hóa. Tương tự 𝑓 𝐷𝑒𝑐 được gọi là hàm giải mã và 𝐴 𝑠 = 𝑓 𝐷𝑒𝑐 (𝐴 𝑠𝐸 , 𝑠𝐾𝑒𝑦). Nếu 𝐴𝑇(. ) là một thuật toán thì 𝑎 ← 𝐴𝑇(. ) là kết quả trả về khi thực thi thuật toán 𝐴𝑇 với (. ) là các tham số đầu vào. Cho 𝐵 𝑖 và 𝐵 𝑗 là hai chuỗi bít cùng kích cỡ, khi đó phép và (AND) nhị phân của hai chuỗi được ký hiệu là 𝐵 𝑖 ∧ 𝐵 𝑗 , phép hoặc (OR) nhị phân của hai chuỗi được ký hiệu là 𝐵 𝑖 ∨ 𝐵 𝑗 . 3.2. Bộ lọc Bloom Bộ lọc Bloom [19] là một cấu trúc dữ liệu đơn giản cho phép kiểm tra sự tồn tại của một phần tử trong một tập hợp một cách nhanh chóng với xác suất dương tính giả nhỏ. Bộ lọc Bloom mang đến hiệu quả về không gian lưu trữ, sử dụng mảng 𝑚 bits để đại diện cho sự xuất hiện của các phần tử s trong tập 𝑆 = {𝑠1 , 𝑠2 , …, 𝑠 𝑛 }. Trước tiên các bits trong mảng sẽ được đặt về 0, sử dụng 𝑘 hàm băm ngẫu nhiên độc lập ℎ1 , ℎ2 , …, ℎ 𝑘 (𝛼 ← ℎ 𝑖 (𝐾𝑒𝑦 𝑖 , 𝑠) | 𝑠 ∈ 𝑆, 𝑖 = {1, . . , 𝑘}, 0 ≤ 𝛼 ≤ 𝑚 − 1) để xác định tập gồm 𝑘 vị trí. Khi đó với mỗi phần tử 𝑠 ∈ 𝑆, các bit tại vị trí ℎ 𝑖 (𝐾𝑒𝑦 𝑖 , 𝑠) trong mảng sẽ được đặt là 1. Để kiểm tra phần tử 𝑠 có thuộc 𝑆 hay không chỉ cần kiểm tra tất cả các vị trí ℎ 𝑖 (𝐾𝑒𝑦 𝑖 , 𝑠) trong mảng có bằng 1 hay không, nếu không thỏa mãn thì kết luận chắc chắn 𝑠 không phải là thành viên của 𝑆, ngược lại s thuộc 𝑆 với một xác suất dương tính giả có thể tối ưu được. IV. ĐỀ XUẤT LƯỢC ĐỒ TRUY VẤN TRÊN DỮ LIỆU KÝ TỰ MÃ HOÁ 4.1. Lược đồ NBFI-SSE Về lý thuyết, bài báo đề xuất lược đồ truy vấn NBFI-SSE với 4 giai đoạn: − 𝐺𝑒𝑛𝑆𝑒𝑐𝑟𝑒𝑡𝑀𝑒𝑡𝑎𝑑𝑎𝑡𝑎(𝜆): là thuật toán sinh các dữ liệu bí mật 𝑀𝑒𝑡𝑎𝐷𝑎𝑡𝑎 (bao gồm các khóa, tham số bí mật khác,…) do người sở hữu dữ liệu thực thi với tham số đầu vào 𝜆. − 𝐵𝑢𝑖𝑙𝑑𝐼𝑛𝑑𝑒𝑥: gồm thuật toán 𝐵𝑢𝑖𝑙𝑑𝐼𝑛𝑑𝑒𝑥(𝐴 𝑠 , 𝑀𝑒𝑡𝑎𝐷𝑎𝑡𝑎) để sinh chỉ mục hỗ trợ tìm kiếm Searchable Index cho chuỗi dữ liệu rõ 𝐴 𝑠 . − 𝑇𝑟𝑎𝑛𝑠𝑙𝑎𝑡𝑒𝑄𝑢𝑒𝑟𝑦: gồm thuật toán 𝑇𝑟𝑎𝑛𝑄𝑢𝑒𝑟𝑦(𝐴′𝑠 , 𝑀𝑒𝑡𝑎𝐷𝑎𝑡𝑎) để biến đổi chuỗi con truy vấn 𝐴′𝑠 thành giá trị tương ứng 𝐼 cho phép tìm kiếm được trên 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝐼𝑛𝑑𝑒𝑥. − SearchIndex: gồm thuật toán 𝑆𝑒𝑎𝑟𝑐ℎ𝐼𝑛𝑑𝑒𝑥(𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝐼𝑛𝑑𝑒𝑥, 𝐼) cho phép xác định được 𝐴′𝑠 có phải là chuỗi con của 𝐴 𝑠 hay không với độ chính xác và hiệu quả cao. Về mô hình thực tiễn khi áp dụng NBFI-SSE, chúng tôi đề xuất mô hình Proxy gồm ba phần: Client Site, Proxy, DSP (hay còn gọi là Server Site). 4.2. Xây dựng và lưu trữ chỉ mục hỗ trợ tìm kiếm Cho tập 𝐴𝑆 = {𝐴 𝑠1 , 𝐴 𝑠2 , …, 𝐴 𝑠𝑛 } với mỗi phần tử là một chuỗi ký tự rõ của trường 𝑋 𝑡 tại một bản ghi, khi đó với mỗi 𝐴 𝑠 ∈ 𝐴𝑆, tại Proxy cần tạo ra bộ giá trị < 𝐴 𝑠𝐸 , 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝐼𝑛𝑑𝑒𝑥 > để lưu tại các trường tương ứng < 𝑋 𝑡𝐸 , 𝑆𝐼𝑋 𝑡 > trên DSP. Với 𝐴 𝑠𝐸 = 𝑓 𝐸𝑛𝑐 (𝐴 𝑠 , 𝑠𝐾𝑒𝑦) và 𝐴 𝑠 = 𝑓 𝐷𝑒𝑐 (𝐴 𝑠𝐸 , 𝑠𝐾𝑒𝑦). Định nghĩa 1. Cho 𝐴 = {𝑎1 , 𝑎2 , … , 𝑎 𝑧 } là tập z các ký tự của bảng chữ cái alpha, và 𝐴 𝑠 = 𝑐1 𝑐2 … 𝑐 𝑣 là một chuỗi được tạo bởi các ký tự trong tập 𝐴 (𝑧 ≥ 1, 𝑣 ≥ 1; ∀𝑖 1 ≤ 𝑖 ≤ 𝑣, 𝑐 𝑖 ∈ 𝐴). Tập 𝐴 𝑠𝑢 là tập các cặp ký tự kết nối theo khoảng cách u (0 ≤ u ≤ v − 2) trên chuỗi As được định nghĩa như sau:
10 TRUY VẤN HIỆU QUẢ DỮ LIỆU KÝ TỰ MÃ HÓA TRONG CƠ SỞ DỮ LIỆU THUÊ NGOÀI 𝐴 𝑠𝑢 = 𝐴 𝑠𝑢 𝐹𝑖𝑟𝑠𝑡𝐶ℎ𝑎𝑟𝑎𝑡𝑒𝑟 ∪ 𝐴 𝑠𝑢 𝑆𝑖𝑛𝑔𝑙𝑒𝐶ℎ𝑎𝑟𝑎𝑡𝑒𝑟 ∪ 𝐴 𝑠𝑢 𝑃𝑎𝑖𝑟𝐶ℎ𝑎𝑟𝑎𝑡𝑒𝑟 ∪ 𝐴 𝑠𝑢 𝐿𝑎𝑠𝑡𝐶ℎ𝑎𝑟𝑎𝑡𝑒𝑟 trong đó: 𝐴 𝑠𝑢 𝐹𝑖𝑟𝑠𝑡𝐶ℎ𝑎𝑟𝑎𝑡𝑒𝑟 = {𝑐1 || ∗} 𝐴 𝑠𝑢 𝑆𝑖𝑛𝑔𝑙𝑒𝐶ℎ𝑎𝑟𝑎𝑡𝑒𝑟 = {𝑐 𝑖 } |(1 ≤ 𝑖 ≤ 𝑣) 𝐴 𝑠𝑢 𝑃𝑎𝑖𝑟𝐶ℎ𝑎𝑟𝑎𝑡𝑒𝑟 = {(𝑐 𝑖 ||𝑗 − 𝑖 − 1||𝑐 𝑗 )} |(1 ≤ 𝑖, 𝑗 ≤ 𝑣 − 1) 𝑎𝑛𝑑 0 ≤ 𝑗 − 𝑖 − 1 ≤ 𝑢 𝐴 𝑠𝑢 𝐿𝑎𝑠𝑡𝐶ℎ𝑎𝑟𝑎𝑡𝑒𝑟 = {∗ ||𝑐 𝑣 } Ví dụ 1. Giả sử có chuỗi 𝐴 𝑠 = "𝑎𝑎𝑏𝑐𝑑𝑎𝑑𝑏", khi đó 𝑣 = 8 và tập các cặp ký tự kết nối theo khoảng cách 𝑢 = 1 trên 𝐴 𝑠 như sau: 𝐴 𝑠𝑢 = {𝑎 ∗, 𝑎, 𝑎, 𝑏, 𝑐, 𝑑, 𝑎, 𝑑, 𝑏, 𝑎0𝑎, 𝑎1𝑏, 𝑎0𝑏, 𝑎1𝑐, 𝑏0𝑐, 𝑏1𝑑, 𝑐0𝑑, 𝑐1𝑎, 𝑑0𝑎, 𝑑1𝑑, 𝑎0𝑑, 𝑎1𝑏, 𝑑0𝑏,∗ 𝑏} Định nghĩa 2. Cho 𝐴 𝑠𝑢 là tập các cặp ký tự kết nối theo khoảng cách 𝑢 trên chuỗi ký tự 𝐴 𝑠 . Gọi 𝐷𝐴 𝑠𝑢 là tập các cặp ký tự kết nối phân biệt theo khoảng cách 𝑢 trên 𝐴 𝑠 nếu 𝐷𝐴 𝑠𝑢 chỉ chứa các phần tử phân biệt của 𝐴 𝑠𝑢 , khi đó |𝐷𝐴 𝑠𝑢 | ≤ |𝐴 𝑠𝑢 |. Theo Ví dụ 1, tập 𝐷𝐴 𝑠𝑢 tương ứng với tập 𝐴 𝑠𝑢 được mô tả như sau: 𝐷𝐴 𝑠𝑢 = {𝑎 ∗, 𝑎, 𝑏, 𝑐, 𝑑, 𝑎0𝑎, 𝑎1𝑏, 𝑎0𝑏, 𝑎1𝑐, 𝑏0𝑐, 𝑏1𝑑, 𝑐0𝑑, 𝑐1𝑎, 𝑑0𝑎, 𝑑1𝑑, 𝑎0𝑑, 𝑑0𝑏,∗ 𝑏} Định lý 1. Cho 𝐷𝐴 𝑠𝑢 là tập các các cặp ký tự kết nối phân biệt theo khoảng cách 𝑢 trên 𝐴 𝑠 , khi đó tất cả các tập ′ 𝐷𝐴 𝑠𝑢 với𝑢′ ≤ 𝑢 đều là tập con của 𝐷𝐴 𝑠𝑢 . ′ Định lý 2. Nếu 𝐴′𝑠 là chuỗi con của 𝐴 𝑠 thì 𝐷𝐴′𝑠 𝑢 luôn là tập con của 𝐷𝐴 𝑠𝑢 , ∀𝑢′ (0 ≤ 𝑢′ ≤ |𝐴′𝑠 |, 𝑢′ ≤ 𝑢), điều này đúng trong cả trường hợp |𝐴′𝑠 | = 1 (tức là chuỗi con chỉ bằng một ký tự). Như vậy chúng ta có thể sử dụng 𝐷𝐴 𝑠𝑢 để biểu diễn đặc tính của chuỗi 𝐴 𝑠 rất hiệu quả. Với tập 𝐴𝑆 = {𝐴 𝑠1 , 𝐴 𝑠2 , 𝑢 𝑢 𝑢 …, 𝐴 𝑠𝑛 } chứa 𝑛 phần tử chuỗi ký tự sẽ được biến đổi thành tập 𝐷 = {𝐷𝐴 𝑠1 , 𝐷𝐴 𝑠2 , … , 𝐷𝐴 𝑠𝑛 } . Việc xây dựng chỉ mục SearchIndex cho mỗi chuỗi 𝐴 𝑠𝑖 thuộc 𝐴𝑆 sẽ chuyển thành xây dựng chỉ mục cho mỗi 𝑢 𝑢 𝐷𝐴 𝑠𝑖 thuộc 𝐷. Chúng ta sử dụng bộ lọc Bloom để nén mỗi phần tử 𝐷𝐴 𝑠𝑖 của 𝐷 về chuỗi 𝑚 bit thông qua 𝑘 hàm 𝐸𝑙𝑒𝑚𝑒𝑛𝑡𝑀𝑎𝑥 𝑢 băm ℎ 𝑖 (1 ≤ 𝑖 ≤ 𝑘). Gọi 𝑓 (𝐷) là hàm trả về phần tử 𝐷𝐴 𝑠𝑖 có chiều dài lớn nhất trong tập 𝐷. Chúng tôi xây dựng giải thuật tạo 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒𝐼𝑛𝑑𝑒𝑥 như sau: Algorithm: 𝐁𝐮𝐢𝐥𝐝𝐈𝐧𝐝𝐞𝐱 Input 𝐴 𝑠 = 𝑐1 𝑐2 … 𝑐 𝑣 : chuỗi ký tự rõ nhạy cảm cần xây dựng chỉ mục 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒𝐼𝑛𝑑𝑒𝑥; 𝐼𝐷: giá trị định danh của bản ghi chứa chuỗi rõ 𝐴 𝑠 ; 𝑚: chiều dài chuỗi bit đại diện cho 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒𝐼𝑛𝑑𝑒𝑥; 𝑘: số lượng hàm băm; 𝐾𝐸𝑌 = {𝐾𝑒𝑦1 , 𝐾𝑒𝑦2 , … , 𝐾𝑒𝑦 𝑘 }: tập khóa sử dụng làm tham số đầu vào cho 𝑘 hàm băm; 𝑢: giá trị khoảng cách giữa các ký tự trong cặp ký tự kết nối; 𝑛𝑀𝑎𝑥: chiều dài của phần tử 𝑓 𝐸𝑙𝑒𝑚𝑒𝑛𝑡𝑀𝑎𝑥 (𝐷); Output Chuỗi bit 𝐵𝐹 với chiều dài 𝑚 đại diện cho 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒𝐼𝑛𝑑𝑒𝑥; Các bước thực hiện (1) Xây dựng tập 𝐷𝐴 𝑠𝑢 = {𝐷𝑊1 , 𝐷𝑊2 , … , 𝐷𝑊𝑙 } là tập các cặp ký tự kết nối phân biệt theo khoảng cách 𝒖 trên 𝑨 𝒔 ; (2) Với mỗi từ khoá (cặp ký tự kết nối) 𝐷𝑊𝑖 ∈ 𝐷𝐴 𝑠𝑢 | 𝑖 ∈ [1, 𝑙], tính toán: - Tập giá trị {𝑝1 , 𝑝2 , … , 𝑝 𝑘 } như sau: {𝑝1 = ℎ1 (𝐾𝑒𝑦1 , 𝐷𝑊𝑖 ), 𝑝2 = ℎ2 (𝐾𝑒𝑦2 , 𝐷𝑊𝑖 ), … , 𝑝 𝑘 = ℎ 𝑘 (𝐾𝑒𝑦 𝑘 , 𝐷𝑊𝑖 )} ; - Tập giá trị {𝑞1 , 𝑞2 , … , 𝑞 𝑘 } như sau: {𝑞1 = ℎ1 (𝑝1 , 𝐼𝐷), 𝑞2 = ℎ2 (𝑝2 , 𝐼𝐷), … , 𝑞 𝑘 = ℎ 𝑘 (𝑝 𝑘 , 𝐼𝐷)}; - Đặt 𝐵𝐹[𝑞 𝑗 ] = 1 với 𝑗 ∈ [1, 𝑘]; (3) 𝑙 là số phần tử trong tập 𝐷𝐴 𝑠𝑢 tương ứng tại bản ghi có định danh 𝐼𝐷, 𝑡 là một số ngẫu nhiên trong khoảng [0, 𝑛𝑀𝑎𝑥 − 𝑙], tính toán:
Hoàng Ngọc Cảnh, Nguyễn Hiếu Minh 11 - Tính 𝑡 ′ = 𝑡 𝑚𝑜𝑑 𝑚; - Tính 𝐵𝐹 = 𝐵𝐹 ∨ 𝑡 ′ ; (4) Trả về 𝐵𝐹; Ví dụ 2: Giả sử bản ghi có 𝐼𝐷 = 8 có giá trị tại trường 𝑋 𝑡 là "𝑎𝑎𝑏𝑐𝑑𝑎𝑑𝑏", yêu cầu xây dựng 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝐼𝑛𝑑𝑒𝑥 của 𝑋 𝑡 tại bản ghi này để lưu vào trường SIXt. Quá trình tính toán được mô tả như hình dưới: 𝐴 𝑠 = "𝑎𝑎𝑏𝑐𝑑𝑎𝑑𝑏" 𝐴 𝑠𝑢 = {𝑎 ∗, 𝑎, 𝑎, 𝑏, 𝑐, 𝑑, 𝑎, 𝑑, 𝑏, 𝑎0𝑎, 𝑎1𝑏, 𝑎0𝑏, 𝑎1𝑐, 𝑏0𝑐, 𝑏1𝑑, 𝑐0𝑑, 𝑐1𝑎, 𝑑0𝑎, 𝑑1𝑑, 𝑎0𝑑, 𝑎1𝑏, 𝑑0𝑏,∗ 𝑏} 𝐷𝐴 𝑠𝑢 = {𝑎 ∗, 𝑎, 𝑏, 𝑐, 𝑑, 𝑎0𝑎, 𝑎1𝑏, 𝑎0𝑏, 𝑎1𝑐, 𝑏0𝑐, 𝑏1𝑑, 𝑐0𝑑, 𝑐1𝑎, 𝑑0𝑎, 𝑑1𝑑, 𝑎0𝑑, 𝑑0𝑏,∗ 𝑏} 𝐵𝑢𝑖𝑙𝑑 𝐼𝑛𝑑𝑒𝑥1: 𝑙 = 16 , 𝑔𝑖ả 𝑠ử 𝑛𝑀𝑎𝑥 = 20, 𝑡 − 𝑔𝑖ả 𝑠ử 𝑢 = 2, 𝑘 = 3 ∈ [0, 𝑛𝑀𝑎𝑥 – 𝑙], − 𝐼𝐷 = 8 𝑡 ′ = 𝑡 𝑚𝑜𝑑 𝑚 1 1 … 1 …. 1 1 1 … 𝐵𝐹 = 𝑚 𝑏𝑖𝑡𝑠 Hình 1. Mô tả các bước xây dựng chỉ mục 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝐼𝑛𝑑𝑒𝑥 4.3. Truy vấn dữ liệu trên chỉ mục Searchable Index Quá trình truy vấn chuỗi con 𝐴′𝑠 trên các trường < 𝑋 𝑡𝐸 , 𝑆𝐼𝑋 𝑡 > được thực hiện trên 3 pha, bao gồm: Phase 1 - Query translation: Nhằm biến đổi câu truy vấn trên dữ liệu rõ (truy vấn trên trường 𝑋 𝑡 ) thành câu truy vấn trên dữ liệu mã (truy vấn trên trường SIXt). Pha này thực hiện tại Proxy, sau đó câu truy vấn trên dữ liệu mã sẽ được truyền tới DSP. Phase 2 - Searching on Index: Truy vấn trên cột 𝑆𝐼𝑋 𝑡 và trả về các bản ghi mà dữ liệu trong cột 𝑋 𝑡𝐸 khi giải mã sẽ là một chuỗi có đặc tính tương tự “tập các cặp ký tự kết nối phân biệt theo khoảng cách 𝒖 của chuỗi con tìm kiếm”. Pha này thực hiện tại DSP. Phase 3 - Requery on decrypted data: Giải mã giá trị trong cột 𝑋 𝑡𝐸 nhận từ Phase 2 và thực hiện truy vấn lại trên trường dữ liệu đã giải mã. Pha này thực hiện tại Proxy, kết quả của pha này sẽ được trả về Client Site. Bài báo này xét tới các điều kiện truy vấn phổ biến trong tìm kiếm chuỗi con trên cơ sở dữ liệu, giả sử 𝐴′𝑠 = 𝑎𝑏𝑐, khi đó ba dạng điều kiện truy vấn phổ biến khi tìm kiếm 𝐴′𝑠 trên trường 𝑋 𝑡 với từ khóa 𝐿𝐼𝐾𝐸 bao gồm: 𝑋 𝑡 𝐿𝐼𝐾𝐸 ′𝑎𝑏𝑐 ∗′ ; 𝑋 𝑡 𝐿𝐼𝐾𝐸 ′ ∗ 𝑎𝑏𝑐′; 𝑋 𝑡 𝐿𝐼𝐾𝐸 ′ ∗ 𝑎𝑏𝑐 ∗ ′ Với Phase 1, gọi 𝑻𝒓𝒂𝒏𝑸𝒖𝒆𝒓𝒚(𝐴′𝑠 , 𝑜𝑡ℎ𝑒𝑟𝑃𝑎𝑟𝑎𝑚𝑠) là hàm biến đổi điều kiện (𝐴′𝑠 ) trong câu truy vấn rõ về giá trị mã (𝐼) hỗ trợ tìm kiếm được trên chỉ mục 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝐼𝑛𝑑𝑒𝑥 lưu trong trường SIXt. Giá trị 𝐼 = {𝐷𝑊1𝑡𝑟𝑎𝑛 , 𝐷𝑊2𝑡𝑟𝑎𝑛 , … , 𝐷𝑊𝑙′𝑡𝑟𝑎𝑛 } (1 ≤ 𝑖 ≤ 𝑙 ′ ) với mỗi 𝐷𝑊𝑖 𝑡𝑟𝑎𝑛 = {𝑝1 , 𝑝2 , … , 𝑝 𝑘 ′ } (1 ≤ 𝑗 ≤ 𝑘 ′ , 1 ≤ 𝑘 ′ ≤ 𝑘, 𝑝 𝑗 𝑙à 𝑠ố 𝑛𝑔𝑢𝑦ê𝑛). Với Phase 2, chúng tôi xây dựng thuật toán 𝑺𝒆𝒂𝒓𝒄𝒉𝑰𝒏𝒅𝒆𝒙(𝐼, 𝑜𝑡ℎ𝑒𝑟𝑃𝑎𝑟𝑎𝑚𝑠) để kiểm tra liệu 𝐴′𝑠 có nằm trong 𝐴 𝑠 hay không. Ví dụ 3. Cho một câu truy vấn 𝑆𝑄𝐿 = “𝑺𝒆𝒍𝒆𝒄𝒕 𝑋 𝑡 , 𝑌𝑡 𝒇𝒓𝒐𝒎 𝑇𝑎𝑏𝑙𝑒 𝑾𝒉𝒆𝒓𝒆 𝑋 𝑡 𝑳𝑰𝑲𝑬 ′ ∗ 𝑨′𝒔 ∗ ′ " với 𝐴′𝑠 là chuỗi con, khi đó nó được biến đổi thành: (𝟏) 𝑆𝑄𝐿1 = “𝑺𝒆𝒍𝒆𝒄𝒕 𝑋 𝑡𝐸 , 𝑌𝑡 𝑋 𝒇𝒓𝒐𝒎 𝑇𝑎𝑏𝑙𝑒 𝑾𝒉𝒆𝒓𝒆 𝑆1 = 𝑇𝑟𝑢𝑒" 𝑣ớ𝑖 𝑆1 ← 𝑆𝑒𝑎𝑟𝑐ℎ𝐼𝑛𝑑𝑒𝑥(𝑇𝑟𝑎𝑛𝑄𝑢𝑒𝑟𝑦(𝐴′𝑠 , 𝑜𝑡ℎ𝑒𝑟𝑃𝑎𝑟𝑎𝑚𝑠), 𝑜𝑡ℎ𝑒𝑟𝑃𝑎𝑟𝑎𝑚𝑠) 𝐷𝑒𝑐 (𝟐) 𝑆𝑄𝐿3 = “𝑺𝒆𝒍𝒆𝒄𝒕 𝑋 𝑡 , 𝑌𝑡 𝒇𝒓𝒐𝒎 𝑓 (𝑇𝑒𝑚𝑝, 𝑠𝐾𝑒𝑦) 𝑾𝒉𝒆𝒓𝒆 𝑋 𝑡 𝑳𝑰𝑲𝑬 ′ ∗ 𝑨′𝒔 ∗ ′" 𝑣ớ𝑖 𝑇𝑒𝑚𝑝 𝑙à 𝑘ế𝑡 𝑞𝑢ả 𝑡𝑟ả 𝑣ề 𝑠𝑎𝑢 𝑘ℎ𝑖 𝑡ℎự𝑐 ℎ𝑖ệ𝑛 𝑙ệ𝑛ℎ 𝑡𝑟𝑢𝑦 𝑣ấ𝑛 (𝟏)
12 TRUY VẤN HIỆU QUẢ DỮ LIỆU KÝ TỰ MÃ HÓA TRONG CƠ SỞ DỮ LIỆU THUÊ NGOÀI Thuật toán 𝑺𝒆𝒂𝒓𝒄𝒉𝑰𝒏𝒅𝒆𝒙(𝐼, 𝑜𝑡ℎ𝑒𝑟𝑃𝑎𝑟𝑎𝑚𝑠) được xây dựng như sau: Algorithm: 𝑺𝒆𝒂𝒓𝒄𝒉𝑰𝒏𝒅𝒆𝒙 Input 𝐼 = {𝐷𝑊1𝑡𝑟𝑎𝑛 , 𝐷𝑊2𝑡𝑟𝑎𝑛 , … , 𝐷𝑊𝑙′𝑡𝑟𝑎𝑛 }: kết quả trả về của hàm 𝑻𝒓𝒂𝒏𝒔𝑸𝒖𝒆𝒓𝒚 tại Proxy; 𝐼𝐷: giá trị định danh của bản ghi cần kiểm tra có chứa 𝐴′𝑠 hay không; 𝐵𝐹: Giá trị 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝐼𝑛𝑑𝑒𝑥 tại bản ghi có định danh 𝐼𝐷; 𝑚: chiều dài chuỗi bit 𝐵𝐹 ′ ; Output 𝑇𝑟𝑢𝑒: bản ghi định có danh 𝐼𝐷 chứa chuỗi 𝐴′𝑠 với một tỷ lệ dương tính giả nhất định; 𝐹𝑎𝑙𝑠𝑒: bản ghi định có danh 𝐼𝐷 chắc chắn không chứa chuỗi 𝐴′𝑠 ; Các bước thực hiện (1) Khởi tạo chuỗi 𝐵𝐹 ′ với 𝑚 bit, đặt tất cả các bit của 𝐵𝐹 ′ bằng 0; (2) Với mỗi phần tử 𝐷𝑊𝑖 𝑡𝑟𝑎𝑛 ∈ 𝐼1, 𝐷𝑊𝑖 𝑡𝑟𝑎𝑛 = {𝑝1 , 𝑝2 , … , 𝑝 𝑘 ′ } (0 ≤ 𝑖 ≤ 𝑙 ′ ), thực hiện: - Tính tập giá trị {𝑞1 , 𝑞2 , … , 𝑞 𝑘 ′ } sao cho: 𝑞1 = ℎ1 (𝑝1 , 𝐼𝐷), 𝑞2 = ℎ2 (𝑝2 , 𝐼𝐷), … , 𝑞 𝑘 ′ = ℎ 𝑘 (𝑝 𝑘 ′ , 𝐼𝐷)}; - Đặt 𝐵𝐹 ′ [𝑞 𝑗 ] = 1 với 1 ≤ 𝑗 ≤ 𝑘 ′ ; (3) Kiểm tra 𝐵𝐹 ′ có thuộc 𝐵𝐹 hay không: 𝑰𝒇 𝐵𝐹 ′ = 𝐵𝐹 ′ ∧ 𝐵𝐹 𝒕𝒉𝒆𝒏 𝑅𝑒𝑠𝑢𝑙𝑡 = 𝑇𝑟𝑢𝑒; 𝑬𝒍𝒔𝒆 𝑅𝑒𝑠𝑢𝑙𝑡 = 𝐹𝑎𝑙𝑠𝑒; (4) Return 𝑅𝑒𝑠𝑢𝑙𝑡; Nhận xét: hàm 𝑺𝒆𝒂𝒓𝒄𝒉𝑰𝒏𝒅𝒆𝒙 có tốc độ thực thi cao do chỉ cần thực hiện các phép “And Bitwise” đơn giản để trả về kết quả. V. ĐÁNH GIÁ KHẢ NĂNG AN TOÀN CỦA SEARCHABLE INDEX Chúng tôi giả định Proxy là khu vực an toàn được quản lý bởi người sở hữu dữ liệu, các vấn đề bảo mật trong bài báo sẽ chỉ tập trung tại DSP. Giả sử kẻ tấn công cũng biết trước tập chuỗi ký tự rõ 𝑃. Kẻ tấn công biết tập mẫu 𝑃𝐼 (chứa các giá trị 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒𝐼𝑛𝑑𝑒𝑥) tương ứng với một tập mẫu 𝑃′ nào đó là con của 𝑃 (kẻ tấn công không biết 𝑃′ ). Giả sử tập 𝑃 có 10000 chuỗi rõ, tập 𝑃𝐼 có 100 phần tử tương ứng với tập 𝑃′ ⊂ 𝑃 (kẻ tấn công không biết 100 chuỗi rõ của 𝑃′ ). 5.1. Tấn công dựa trên thống kê tần suất Với kịch bản kẻ tấn công thống kê tần suất mỗi phần tử của 𝐷 trên tập 𝑃 và thống kê tần suất của các bit 1 tại mỗi vị trí trên 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝐼𝑛𝑑𝑒𝑥, rồi sau đó so sánh chúng với nhau để phát hiện mỗi vị trí bit 1 của 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝐼𝑛𝑑𝑒𝑥 sẽ ứng với đặc tính nào trong 𝐴 𝑠 . Gọi 𝑛𝑢𝑚1 , 𝑛𝑢𝑚2 , … , 𝑛𝑢𝑚754 lần lượt là số lượng chuỗi trong tập 𝑃 có chứa phần tử 𝐷[𝑗] 𝑣ớ𝑖 1 ≤ 𝑗 ≤ 754. Khi đó tập mô tả tần suất xuất hiện các phần tử của tập 𝐷 trên tập 𝑃 sẽ được tính như sau: 𝑛𝑢𝑚1 𝑛𝑢𝑚2 𝑛𝑢𝑚754 𝐹 𝐷/𝑃 = ( , ,… , ) 10000 10000 10000 ′ ′ Gọi 𝑛𝑢𝑚1 , 𝑛𝑢𝑚2 , … , 𝑛𝑢𝑚′ 𝑚 lần lượt là số lượng phần tử trong tập 𝑃𝐼1 có giá trị bit tại vị trí thứ 𝑖 (1 ≤ 𝑖 ≤ 𝑚) bằng 1, tập tần suất xuất hiện của các bit trên 𝐼𝑛𝑑𝑒𝑥1 là: ′ ′ 𝑛𝑢𝑚1 𝑛𝑢𝑚2 𝑛𝑢𝑚′ 𝑚 𝐹𝐼𝑛𝑑𝑒𝑥/𝑃𝐼1 = ( , ,… , ) 100 100 100 So sánh giữa 𝐹𝐼𝑛𝑑𝑒𝑥/𝑃𝐼 và 𝐹 𝐷/𝑃 để tìm ra một số cặp phần tử có độ lớn tương đương (𝐹𝐼𝑛𝑑𝑒𝑥/𝑃𝐼 ≈ 𝐹 𝐷/𝑃 ), kẻ tấn công có thể suy luận được tại vị trí bit thứ 𝑖 trên chuỗi 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒𝐼𝑛𝑑𝑒𝑥 có thể tương ứng với một phần tử thứ 𝑗 trong tập 𝐷. Tuy nhiên, Statistical attack trên 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒𝐼𝑛𝑑𝑒𝑥 chỉ có thể áp dụng khi giả định các tham số 𝑢 = 0, 𝑢′ =
Hoàng Ngọc Cảnh, Nguyễn Hiếu Minh 13 0 , 𝑘 = 1, trong thực tế các tham số trên có sự khác biệt và hoàn toàn được giữ bí mật, số lượng phần tử trong tập 𝐷 không đoán được, số lượng bit đại diện cho một phần tử của tập 𝐷 sẽ nhiều hơn một bit, vì vậy sẽ vô cùng khó khăn để xác định được 𝐹 𝐷/𝑃 và 𝐹𝐼𝑛𝑑𝑒𝑥/𝑃𝐼 . Ngay cả khi tính toán được 𝐹 𝐷/𝑃 và 𝐹𝐼𝑛𝑑𝑒𝑥/𝑃𝐼 thì các giá trị trong hai tập đó cũng không đủ căn cứ để thực hiện phép so sánh. Đặc biệt trong thuật toán 𝐵𝑢𝑖𝑙𝑑𝐼𝑛𝑑𝑒𝑥 còn có sự kết hợp với định danh bản ghi 𝐼𝐷 và bổ sung thêm một lượng bit ngẫu nhiên trong quá trình tạo 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒𝐼𝑛𝑑𝑒𝑥, điều này sẽ càng khiến kẻ tấn công không có cơ sở nào để xây dựng tập 𝐹𝐼𝑛𝑑𝑒𝑥/𝑃𝐼. 5.2. Tấn công dựa trên biết trước bản rõ Cách tấn công này (known-plaintext attack) dựa trên giả thiết kẻ tấn công biết được một số mẫu dữ liệu rõ cùng mẫu dữ liệu chỉ mục tương ứng, với phương pháp suy luận những giá trị chỉ mục giống nhau có thể được sinh ra từ những chuỗi dữ liệu rõ giống nhau, kẻ tấn công sẽ thực hiện so sánh giá trị chỉ mục trên các bản ghi với dữ liệu chỉ mục trên tập mẫu đã đã biết, qua đó suy luận ra dữ liệu rõ nhạy cảm tương ứng với chỉ mục trong mỗi bản ghi. Như vậy, để có thể thực hiện được thì kẻ tấn công cần biết trước tập mẫu chuỗi ký tự rõ 𝑃′ ⊂ 𝑃 cùng tập các chỉ mục 𝑃𝐼 tương ứng với 𝑃′ (|𝑃′ | = |𝑃𝐼1 | = |𝑃𝐼2 | ). Theo thuật toán 𝐵𝑢𝑖𝑙𝑑𝐼𝑛𝑑𝑒𝑥, với cùng một chuỗi ký tự rõ 𝐴 𝑠 nhưng thuộc các bản ghi khác nhau thì sẽ có giá trị 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝐼𝑛𝑑𝑒𝑥 đại diện khác nhau, do trong 𝑏ướ𝑐 2 của thuật toán đã kết hợp sử dụng định danh 𝐼𝐷 của bản ghi để xây dựng chuỗi bit đầu ra 𝐵𝐹, tiếp theo trong 𝑏ướ𝑐 3 của thuật toán sử dụng thêm số ngẫu nhiên 𝑡 để tiếp tục làm nhiễu đi giá trị của 𝐵𝐹 đã thiết lập tại 𝑏ướ𝑐 2. Như vậy một chuỗi ký tự rõ 𝐴 𝑠 sẽ được đại diện bởi nhiều chuỗi giá trị 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝐼𝑛𝑑𝑒𝑥 khác nhau tại các bản ghi khác nhau, nói cách khác các phần tử của tập 𝑃𝐼 sẽ khác nhau và tập này không thể đại diện giá trị 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝐼𝑛𝑑𝑒𝑥 cho mọi bản ghi. Rõ ràng kẻ tấn công sẽ rất khó để thực hiện Known-plaintext attack nhằm suy luận thông tin bản rõ từ các chỉ mục này. 5.3. Tấn công dựa trên phân tích mẫu truy vấn Một kịch bản tấn công khác là dựa trên phân tích mẫu truy vấn (thuật ngữ thường gọi là Query’s pattern): Giả sử trong thực tế người dùng có số lần tìm kiếm chuỗi con “New York” vượt trội hơn tất cả các cụm từ khác, khi đó tại Phase 1 hàm 𝑇𝑟𝑎𝑛𝑄𝑢𝑒𝑟𝑦(. ) sẽ biến đổi parttens “New York” thành EncryptedPattern (𝐼), sau đó gửi lên DSP. Tại DSP kẻ tấn công có thể thống kê tần suất xuất hiện của EncryptedPattern, nếu tần suất xuất hiện của dữ liệu này tương đồng với tần suất yêu cầu truy vấn chuỗi “New York” của người dùng thì có thể kết luận EncryptedPattern tương ứng với chuỗi “New York”. Tuy nhiên, thuật toán 𝑇𝑟𝑎𝑛𝑄𝑢𝑒𝑟𝑦(. ) sử dụng ngẫu nhiên 𝑘 ′ khóa từ tập 𝐾𝐸𝑌 (1 ≤ 𝑘 ′ ≤ 𝑘) để làm tham số cho 𝑘 ′ hàm băm sử dụng trong quá trình biến đổi pattern 𝐴′𝑠 thành tập 𝐼 = {𝐷𝑊1𝑡𝑟𝑎𝑛 , 𝐷𝑊2𝑡𝑟𝑎𝑛 , … , 𝐷𝑊𝑙′𝑡𝑟𝑎𝑛 }, vì vậy với cùng một Query’s pattern thì giá trị 𝐼 sẽ khác nhau đối với mỗi lần người dùng truy vấn. VI. ĐÁNH GIÁ HIỆU QUẢ TRUY VẤN Để đánh giá tính hiệu quả của mô hình đề xuất trong bài báo, chúng tôi thực hiện một số thực nghiệm để kiểm tra tính hiệu quả dựa trên các tiêu chí về: tỷ lệ lọc và tỷ lệ lỗi của tập dữ liệu mã sau truy vấn trên 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝐼𝑛𝑑𝑒𝑥. Định nghĩa 3. Cho 𝑁 𝑅 là số lượng bản ghi của quan hệ 𝑅, giả sử 𝑁 𝑅𝑒𝑠𝑢𝑙𝑡 là số lượng bản ghi trả về khi truy vấn thông thường trên dữ liệu rõ, 𝑁 𝐼𝑛𝑑𝑒𝑥 là số bản ghi mã trả về sau khi truy vấn trên 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝐼𝑛𝑑𝑒𝑥. Định nghĩa tỷ lệ lọc (𝐹𝐼𝑅1 ) và tỷ lệ lỗi (𝐹𝐴𝑅1 ) qua công thức sau: 𝑁 𝑅 − 𝑁 𝐼𝑛𝑑𝑒𝑥1 𝑁 𝐼𝑛𝑑𝑒𝑥1 − 𝑁 𝑅𝑒𝑠𝑢𝑙𝑡 𝐹𝐼𝑅1 = 𝐹𝐴𝑅1 = 𝑁 𝑅 − 𝑁 𝑅𝑒𝑠𝑢𝑙𝑡 𝑁 𝐼𝑛𝑑𝑒𝑥1 Dữ liệu thử nghiệm: Dữ liệu cột L_COMMENT trong bảng LINEITEM trong cơ sở dữ liệu TPC-H [20] làm đối tượng thực hiện các thử nghiệm. Trong mỗi kịch bản thử nghiệm, chúng tôi sử dụng một số điều kiện truy vấn chuỗi con như bảng sau để thử nghiệm và đánh giá, với 𝑆1 , 𝑆2 , 𝑆3 là các chuỗi con có số ký tự tương ứng là 2, 8, 16. Theo mô hình Proxy đã đề xuất, bài báo sử dụng 3 máy tính cá nhân Dell với Intel Core i5 4310U 2.0Ghz CPU và 8GB DDRAM3 để thực nghiệm. Trong đó 1 máy sử dụng làm DSP Server lưu trữ cơ sở dữ liệu TPC_H_DSP, 1 máy sử dụng làm Proxy và 1 máy là Client. Các máy tính đều được cài đặt Windows 10 và MS SQL Server 2016 làm hệ quản trị cơ sở dữ liệu. Bảng 1. Các điều kiện truy vấn sử dụng trong thử nghiệm Query Condition Query Condition Q1 L_COMMENT like ‘%𝑆1 %’ QL1 L_COMMENT like ‘%𝑆1 ’ Q2 L_COMMENT like ‘%𝑆2 %’ QL2 L_COMMENT like ‘%𝑆2 ’ Q3 L_COMMENT like ‘%𝑆3 %’ QL3 L_COMMENT like ‘%𝑆3 ’ Ứng với mỗi truy vấn Q1, Q2, Q3, QL1, QL2, QL3 chúng tôi sử dụng 30 mẫu chuỗi con 𝑆1 , 𝑆2 , 𝑆3 để thử nghiệm, các giá trị 𝐹𝐼𝑅1 , 𝐹𝐴𝑅1 tại mỗi kịch bản truy vấn sẽ được tính bằng trung bình cộng các kết quả trả về sau khi truy vấn trên 30 mẫu chuỗi con ở trên.
14 TRUY VẤN HIỆU QUẢ DỮ LIỆU KÝ TỰ MÃ HÓA TRONG CƠ SỞ DỮ LIỆU THUÊ NGOÀI Chọn 𝑁 𝑅 = 1000000, cố định 𝑢 = 2, với 𝑚 tăng dần từ 128 đến 512 lần lượt thực hiện các truy vấn Q1, Q2, Q3, QL1, QL2, QL3 và tính toán 𝐹𝐼𝑅1 , 𝐹𝐴𝑅1 . Hình 2. 𝐹𝐼𝑅1 , 𝐹𝐴𝑅1 với 6 truy vấn trong trường hợp 𝑢 = 2, 𝑚 ∈ [128, 512] Từ Hình 2 có thể thấy giá trị 𝐹𝐼𝑅1 luôn có xu hướng tiệm cận giá trị 𝟏, giá trị 𝐹𝐴𝑅1 luôn xu hướng tiệm cận giá trị 𝟎, điều này khẳng định hiệu quả lọc để loại bỏ các bản ghi không thỏa mãn truy vấn cũng như tỷ lệ lỗi của mô hình sau khi truy vấn trên 𝑺𝒆𝒂𝒓𝒄𝒉𝒂𝒃𝒍𝒆 𝑰𝒏𝒅𝒆𝒙 là rất tốt. Các biểu đồ trên cũng thể hiện được sự tác động độ dài 𝒎 lên hiệu quả truy vấn, khi 𝒎 tăng thì đường 𝐹𝐼𝑅1 tiệm cận giá trị 𝟏 hơn và đường 𝐹𝐴𝑅1 tiệm cận giá trị 𝟎 hơn. Kết quả thể hiện trên các biểu đồ cũng chỉ ra với cùng một giá trị 𝒎, 𝒖 thì các truy vấn Q1, Q2, Q3, QL1, QL2, QL3 (với độ dài chuỗi con 𝑺 𝟏 , 𝑺 𝟐 , 𝑺 𝟑 khác nhau) cũng đạt được hiệu quả khác nhau, nguyên nhân do chiều dài chuỗi con truy 𝒖′ vấn sẽ tác động đến số phần tử của tập 𝑫𝑨′𝒔(.) tương ứng nêu trong thuật toán 𝑻𝒓𝒂𝒏𝑸𝒖𝒆𝒓𝒚, khi chuỗi con càng dài 𝒖′ thì số phần tử của 𝑫𝑨′𝒔(.) càng lớn và hiệu quả truy vấn càng cải thiện. VII. KẾT LUẬN Bài báo này, chúng tôi nghiên cứu phương pháp tiếp cận mới để truy vấn hiệu quả chuỗi con trên dữ liệu dạng ký tự đã mã hóa trong cơ sở dữ liệu thuê ngoài. Chúng tôi đề xuất lược đồ NBFI-SSE và mô hình Proxy để giải quyết vấn đề này. Dựa trên các phân tích lý thuyết và kết quả thực nghiệm, mô hình đề xuất đã chỉ ra hiệu quả của việc truy vấn trên chỉ mục 𝑆𝑒𝑎𝑟𝑐ℎ𝑎𝑏𝑙𝑒 𝐼𝑛𝑑𝑒𝑥 đối với trường hợp số lượng bản ghi bất kỳ, đặc biệt đạt hiệu quả cao trong trường hợp số bản ghi lớn. Chúng tôi cũng chỉ ra sự tác động của các tham số 𝑢, 𝛼, 𝑚 đối với tính hiệu quả, bảo mật và không gian lưu trữ của mô hình đã đề xuất, đây là cơ sở để điều chỉnh ứng dụng phù hợp giải pháp này trong thực tế. TÀI LIỆU THAM KHẢO [1] AES, Advanced encryption standard, National Institute of Science and Technology FIPS 197, 2001. [2] Song D. X., Wagner D., Perrig A. Practical Techniques for Searches on Encrypted Data. In Proceedings of the 2000 IEEE Symposium on Security and Privacy, Berkeley, CA, USA, 14-17 May 2000. [3] Goh E. J. Secure Indexes. Cryptology ePrint Archive, Report 2003/216, 2003. Available online: http://eprint.iacr.org/2003/216/ (accessed on 10 January 2016). [4] R. Curtmola, J. A. Garay, S. Kamara and R. Ostrovsky, Searchable symmetric encryption: Improved definitions and efficient constructions, in:Proceedings of the 13th ACM Conference on Computer and Communications Security, Alexandria,Virginia, USA, 2006. [5] Boneh D., Crescenzo G. D., Ostrovsky R., Persiano G. Public Key Encryption with Keyword Search. In Proceedings of the EUROCRYPT 2004, Jeju Island, Korea, 5-9 December 2004. [6] Boneh D., Waters B. Conjunctive, Subset, and Range Queries on Encrypted Data. In Proceedings of the 4 th IACR Theory of Cryptography Conference, Amsterdam, The Netherlands, 21-24 February 2007. [7] Chang Y. C., Mitzenmacher M. Privacy Preserving Keyword Searches on Remote Encrypted Data. In Proceedings of the 3rd International Conference on Applied Cryptography and Network Security, New York, NY, USA, 7-10 June 2005.
Hoàng Ngọc Cảnh, Nguyễn Hiếu Minh 15 [8] Golle P., Staddon J., Waters B. Secure Conjunctive Keyword Search over Encrypted Data. In Proceedings of the Applied Cryptography and Network Security 2004, Yellow Mountain, China, 8-11 June 2004. [9] Hwang Y. H., Lee P. J. Public Key Encryption with Conjunctive Keyword Search and Its Extension to a Multi-user System. In Proceedings of the First International Conference on Pairing-Based Cryptography, Tokyo, Japan, 2-4 July 2007. [10] Li J., Wang Q., Wang C., Cao N., Ren K., Lou W. Fuzzy Keyword Search over Encrypted Data in Cloud Computing. In Proceedings of the 29th Conference on Information Communications, London, UK,7-9 September 2010. [11] M. Chase and E. Shen. Substring-searchable symmetric encryption. Proceedings on Privacy Enhancing Technologies, 2015. [12] S. Faber, S. Jarecki, H. Krawczyk, Q. Nguyen, M. Rosu, and M. Steiner. Rich queries on encrypted data: Beyond exact matches. In "Computer Security - ESORICS 2015: 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21-25, 2015, Proceedings, Part II", ESORICS. [13] D. Cash, J. Jaeger, S. Jarecki, C. Jutla, H. Krawczyk, M.-C. Rosu, and M. Steiner. Dynamic searchable encryption in very large databases: Data structures and implementation. In Proc. of NDSS, volume 14, 2014. [14] Yamamoto H., Wachi Y., Fujiwara H. Space-Efficient and Secure Substring Searchable Symmetric Encryption Using an Improved DAWG. In: Steinfeld R., Yuen T. (eds) Provable Security. ProvSec 2019. Lecture Notes in Computer Science, vol 11821. Springer, Cham, 2019. [15] Hahn F., Loza N., & Kerschbaum F. Practical and Secure Substring Search. Proceedings of the 2018 International Conference on Management of Data - SIGMOD ’18, 2018. [16] Leontiadis I., & Li M. Storage Efficient Substring Searchable Symmetric Encryption. Proceedings of the 6th International Workshop on Security in Cloud Computing - SCC ’18, 2018. [17] Strizhov M., & Ray I. Substring Position Search over Encrypted Cloud Data Using Tree-Based Index. 2015 IEEE International Conference on Cloud Engineering, 2015. [18] Yamamoto H. Secure Automata-Based Substring Search Scheme on Encrypted Data. In: Ogawa K., Yoshioka K. (eds) Advances in Information and Computer Security. IWSEC 2016. Lecture Notes in Computer Science, vol 9836. Springer, Cham, 2016. [19] Bloom B. H.: Space/time trade-offs in hash coding with allowable errors. Comm. ACM 13, 422-426, 1970. [20] TPC, TPC BenchmarkTM H Standard Specification Revision 3.0.0, http://tpc.org/tpc_documents_current_versions/pdf/tpc- h_v3.0.0.pdf. EFFICIENT QUERIES ENCRYPTED CHARACTERS DATA ON OUTSOURCE DATABASE Hoang Ngoc Canh, Nguyen Hieu Minh ABSTRACT: This paper focuses on how to build a encryption index that effectively supports querying encrypted characters data on outsource database. To solve this issue we propose the New Bloom Filter Index - Searchable Symmetric Encryption (NBFI- SSE) scheme and applying this scheme to the Proxy model enables high performance substring searching on encryption indexes and low redundancy of return encrypted data result sets. The proposed schema has four stages as a standard SSE schema, including: GenSecretMetadata, BuildIndex, TranslateQuery and SearchIndex, which allows the transformation of each plaintext 𝐴 𝑠 into two encrypted versions for storage in the outsourced database. The first version is the encrypted data of 𝐴 𝑠 generated by standard encryption algorithms, the other version is a searchable index created by the BuildIndex algorithm based on the Bloom filter idea and a special structure that we built as a set of concatenated character pairs. discriminant by distance u on 𝐴 𝑠 . This index enables the implementation of 𝐿𝐼𝐾𝐸 query with high performance, anti-leakage of plaintext information, safe from common attack scenarios and especially against query pattern attack.