I.Giới thiệu
Điện toán đám mây được định nghĩa chi tiết tại website của NIST [1]. Trong công việc của chúng tôi, chúng
tôi đơn giản định nghĩa điện toán đám mâ như là một phân phối của các nguồn tài nguyên điện toán theo nhu
cầu được đặt tại các máy chủ từ xa. Thông qua việc đánh giá các công cụ và kết nối băng thông rộng, điện toán
đám mây đang nhận được sự chấp nhận nhiều hơn từ người dùng [2], vì nó giảm thiểu chi phí và nâng cao tính
di động [5].
Với sự phổ biến ngày càng tăng của điện toán đám mây vấn đề về an ninh cũng tăng lên [3][4]. Các tổ chức
xem xét chuyển đổi sang các dịch vụ dựa trên đám mây cũng phải xem xét và hiểu các vấn đề về an ninh, riêng
tư, độ tin cậy và pháp lý. Các cơ quan nghiên cứu quan trọng nhận thức những rủi ro này và đã đưa ra các báo
cáo [6], [7], [8], [9]. Theo Gartner, các nguy cơ bảo mật điện toán đám mây có thể tóm tắt thành bảy loại sau:
“Đặc quyền truy cập người dùng, Tuân thủ quy định, Vị trí dữ liệu, Phân tách dữ liệu, Phục hồi, Hỗ trợ điều tra,
Khả năng tồn tại dài hạn” [6]. Các vấn đề an ninh được điều tra sâu hơn dưới hai đối tượng chính cụ thể, “mất
kiểm soát dữ liệu” và “sự phụ thuộc vào nhà cung cấp điện toán đám mây” [15].
Các cơ sở dữ liệu từ bên ngoài (outsourcing) vào đám mây có thể nâng cao mức độ sẵn sàng, mạnh mẽ, đàn
hồi và hiệu quả cũng như hạn chế tối đa các lý do thuộc hành chính. Tuy nhiên dữ liệu trong đám mây có thể bị
nhà cung cấp đám mây truy cập. Vì thế, nhà cung cấp đám mây, nhân viên của mình hoặc thậm chí các nhà thầu
phụ có thể cố tình hoặc vô tình truy cập vào dữ liệu của khách hàng. Để đảm bảo tính bảo mật của dữ liệu về
mặt kỹ thuật, dữ liệu có thể được mã hóa trước khi được đưa vào cơ sở dữ liệu thuê bên ngoài. Tuy nhiên, việc
thực thi các truy vấn như một bí mật tính toán hoàn hảo trên một dữ liệu mã hóa không thể được tạo ra một cách
hiệu quả. Việc thực hiện các tính toán không bình thường với dữ liệu trên đám mây như tìm kiếm, chuyển đổi,
lựa chọn, và quyết định kiểm soát truy cập là có ích. Mã hóa thông thường ngăn chặn xử lý dữ liệu này trên đám
mây. Genrty đã giải quyết một vấn đề ba mươi năm chờ đợi trong mật mã [14]. Ông ta đã giải thích một lược đồ
mã hóa mới có thể cho phép xử lý trên dữ liệu mã hóa. Tuy nhiên lược đồ mã hóa này là xa với thực tế. DARPA
tách 20 triệu đô để tìm kiếm vấn đề này của mật mã như là một giải pháp thiết thực [16]. Popa và bạn bè của
mình từ MIT đã mang đến một giả pháp thiết thực để xử lỹ cơ sở dữ liệu mã hóa [10]. Bài viết này tập trung vào
công việc của họ chi tiết hơn và những điểm yếu trong công việc của họ.

A.Công việc liên quan
Các nhà nghiên cứu đang cố gắng tìm ra các giải pháp để giữ dữ liệu trên đám mây được bí mật. Việc xử lý
dữ liệu an toàn trên đám mây là phức tạp. Trong phần này, chúng tôi sẽ đưa ra một số cách tiếp cận nổi tiếng để
giải quyết tính toán an toàn trên đám mây.

Sự đóng góp chính của bài viết này là cung cấp phân tích chi tiết về CryptDB. Để dễ hiểu đầu tiên chúng tôi
mô tả CryptDB với giải thích chi tiết hơn. Tiếp theo, chúng tôi mô tả cấu chúc máy chủ của CryptDB và chúng
tôi phân tích Proxy Server. Không may, bài viết ban đầu không giải thích thuật toán tìm kiếm, do đó chúng tôi
mở rộng thuật toán tìm kiếm của CryptDB. Chúng tôi cho thấy rằng thuật toán tìm kiếm hiện tại là không đủ để
đám ứng tất cả các truy vấn tìm kiếm. Chúng tôi nhấn mạnh những điểm an toàn và hiệu quả của CryptDB.
Cuối cùng, chúng tôi trình bày một vài nhận xét và mở rộng khu vực nghiên cứu cho CryptDB.

II.Kiến trúc CryptDB
A.Mã hóa lớp - Layered Encryption
Mã hóa dữ liệu trên cơ sở dữ liệu được tính toán theo lớp. Có 4 mục tiêu chính khác nhau để đạt được, và với
mỗi mục tiêu tồn tại một “nhân” được bao bọc bởi các lớp khác nhau, được gọi là onion [11]: EQ, ORD,
SEARCH và ADD onion. EQ onion nhằm mục đích điều chỉnh các lớp cho các truy vấn equality, trong khi
ORD onion nhằm mục đích ddiefu chỉnh sự rò rỉ thứ tự cho các truy vấn so sánh (comparison), SEARCH onion
được sử dụng để tìm kiếm một đoạn van bản trong cơ sở dữ liệu mà không làm rò rỉ bất kỳ thông tin gì. Onion
này không cho phép thực thi các giá trị nguyên (integer values). Cuối cùng Add onion nhằm mục đích cộng
(add) các giá trị mã hóa mà chỉ hỗ trợ các giá trị nguyên. Các onion này có các lớp khác nhau và mỗi lớp được
mã hóa sử dụng các thuật toán khác nhau. Hơn nữa, những thuật toán này có các mức độ an toàn khác nhau với
các lớp bên ngoài của một onion sẽ bảo mật hơn các lớp bên trong. Hơn nữa, một giá trị chỉ có một lớp hiện tại
trong mỗi onion. Một khi cơ sở dữ liệu được tạo ra, tất cả các onion sẽ ở tại lớp an toàn nhất.
Các truy vấn được xử lý như các cột trong cơ sở dữ liệu, do đó, CryptDB cũng là hướng cột (columnoriented). Nếu một giá trị cần được giải mã tới lớp yếu hơn, thì toàn bộ cột sẽ được giải mã. Tuy nhiên, nó khiến
cho rò rỉ nhiều thông tin hơn yêu cầu. Nếu chúng ta cần một giá trị ở lớp yếu nhất, toàn bộ cột sẽ tại lớp đó và
rò rỉ thông tin. Và cũng lưu ý rằng lớp trong cùng là lớp yếu nhất, nhưng nó cũng không tiết lộ bất kỳ bản rõ
nào cho máy chủ DBMS. Lớp bên trong của các onion là Equi-JOIN, OPE-JOIN, SEARCH và HOM không
bao giờ được gỡ bỏ.


Hình 1. EQ Onion
Tai lớp an toàn nhất của EQ onion là lớp RND. Lớp RND này mã hóa mỗi giá trị với AES (thuật toán
Rjindaels) trong chế độ CBC. Với số nguyên, Blowfish trong chế độ CBC thích hợp hơn vì kích thước khối 64
bit của nó thay vì kích thước khối 128 bit sẽ giảm độ dài của bản mã. Giá trị khởi tạo cho cả hai loại mã hóa là

tương quan giữa các cột. An toàn của lược đồ này dựa vào Elliptic-Curve Decisional Diffie Hellman.

Hình 2 ORD Onion
ORD onion. Lớp an toàn nhất của ORD onion giống như EQ onion, là lớp RND. Lớp bên trong của RND
cho ORD onion là lớp OPE. Các thuật toán mã hóa duy trì thứ tự không có đủ an toàn và hiệu quả cho đến bây
giờ. Trong bài viết gốc của CryptDB [10], các tác giả không xem xét mã hóa duy trì thứ tự nhưng sau đó họ đưa
ra vấn đề này trong bài viết “An Ideal Security Protocol for Order-Preserving Encoding” [11].
Thông tin hạn chế được đưa ra về onion này trong bài viết của CryptDB [10]. Nếu mã hóa của x nhỏ hơn mã
hóa của y, thì giá trị x cũng nhỏ hơn giá trị y. Nếu chúng ta tìm ra bất kỳ giá trị được mã hóa nào gữa hai mã hóa
này, thì bản rõ cũng sẽ nằm giữa x và y. Cụ thể, lược đồ này rò rỉ thứ tự, do đó, nó là một lược đồ yếu hơn khi
được so sánh với sự rò rỉ của equality.
Đối với các giá trị tại cùng một cột, lớp này là đủ để xử lý các truy vấn, nhưng nếu hai cột khác nhau được so
sánh để kiểm tra thứ tự, thì chúng ta cần tháo bỏ lớp OPE, và đạt tới lớp OPE-JOIN. Lớp này thiếu tính chức
năng hơn lớp EQUI-JOIN của EQ onion. Để điều chỉnh hai cột là không thể vì sự thiếu hiệu quả của các thuật
toán duy trì thứ tự. Có hai giải pháp. Giải pháp đầu tiên là, ứng dụng sẽ khai báo các cột có thể được kết nối, và
trong khi sắp xếp các khóa, cùng một khóa sẽ được sử dụng cho những cột này. Nó không hợp lý trong hầu hết
tình huống khai báo trước. Giải pháp thứ hai là cùng một khóa sẽ được sử dụng cho tất cả các cột tại lớp này.
Giải pháp này cũng không phải là giải pháp tốt. May thay, các range join không được sử dụng quả nhiều.


Hình 3 SEARCH & ADD Onions
SEARCH & ADD onions. SEARCH onion chỉ có một lớp, vì thế không có quá trình giải mã nào cho onion
này. SEARCH onion có một giá trị, và lớp SEARCH trong đó bao gồm giá trị này. Thuật toán tìm kiếm được sử
dụng trong CryptDB là thuật toán tìm kiếm của Song được mô tả trong phần III-D. Mục đích của SEARCH
onion là tìm kiếm các giá trị mã hóa bên trong một bảng mã hóa.
ADD onion cũng tương tự như vậy. Lớp HOM là lớp duy nhất của ADD onion. Mục đích của onion này là
cung cấp một số chức năng với các giái trị mã hóa mà không truy cập bản rõ. Điều này có thể đạt được với mã
hóa đồng cấu (homomorphic encryption). Thuật toán được sử dụng cho mã hóa đồng cấu của CryptDB là thuật
toán của Paillier.


CREATE FUNCTION dbo.area (edge FLOAT) RETURNS FLOAT RETURN(edge * edge);

Một truy vấn ví dụ để sử dụng UDF này có thể giống như sau:
SELECT Number, area (Edge Length) AS Area FROM Square;

Kết quả trả về sẽ giống Table II

Thay vì giữ dữ liệu cho từng thông tin có thể được yêu cầu, sẽ tốt hơn khi tạo một UDF, và gọi nó bất cứ khi
nào tác vụ cần. Trong CryptDB, UDF cũng là một yêu cầu. Việc giải mã của kiến trúc lớp để điều chỉnh lớp
hiện tại được thực hiện bằng cách sử dụng các UDF. Và cập nhật trạng thái hiện tại của các lớp onion cũng được
thực hiện bằng cách sử dụng các UDF. Việc thay đổi tất cả cơ chế cơ sở dữ liệu hiện tại là khó đạt được. Do đó,
các UDF rất quan trọng đối với các chức năng bổ sung trong hệ thống cơ sở dữ liệu.

D.Cấu trúc máy chủ trong CryptDB - Server Structure in CryptDB
Trong các hệ thống cơ sở dữ liệu, người dùng yêu cầu một vài thông tin hoặc chức năng từ các ứng dụng.
Các truy vấn SQL được sử dụng để đám ứng chu cầu của người dùng. Các máy chủ ứng dụng gửi các truy vấn
tới máy chủ DBMS. Máy chủ DBMS xử lý và phản hồi tập kết quả. Hệ thống này có thể bị kẻ xấu tấn công
hoặc nghe trộm. Các máy chủ DBMS cũng tò mò về các truy vấn và theo dõi các truy vấn với kết quả của
chúng. Khả năng khác là truy cập vật lý và đĩa có thể gây mất trộm dữ liệu. Trong CryptDb, cơ chế của các truy
vấn là tương tự, nhưng kiến trúc máy chủ một cách nào đó thay đổi , và một máy chủ bổ sung được gọi là Proxy
Server được thêm vào hệ thống cơ sở dữ liệu.
Nó giả định rằng tất cả truy vấn từ máy chủ ứng dụng được thực hiện bởi Proxy Server, và gửi tới DBMS
Server sau khi sửa đôi. Mục đích là giữ thông tin vô nghĩa tại phía DBMS Server để ngăn chặn những người


quản trị cơ sở dữ liệu tò mò dòm ngó tới nội dung của các bảng trong cơ sở dữ liệu của nó [27]. Vì lý do này,
chúng ta cần làm cho toàn bộ dữ liệu trở nên vô nghĩa.
Điều đầu tiên là tạo một bảng để giữ một vài dữ liệu bên trong cơ sở dữ liệu của DBMS Server. Trong
CryptDB, bảng của DBMS Server hoàn toàn khác với bảng thực. Proxy Server thay đổi tên bảng. Sau đó, tùy
theo loại của cột (ví dụ int, varchar), sẽ được đưa vào các onion có thể. Proxy Server giữ tất cả các dữ liệu của

Sau khi đọc bài viết về CryptDB [10], thậm chí nếu dễ dàng hiểu cấu trúc, nó vẫn khó có thể kết hợp cơ chế
CryptDB với các truy vấn SQL. Vì lý do này, chúng tôi minh họa một ví dụ để làm rõ các bước chi tiết hơn.
Bảng Studens có hai cột là ID và Name. Cột ID có giá trị nguyên trong khi cột Name có giá trị là chuỗi.
Bảng Students được tạo ra bằng câu lệnh sau:
CREATE TABLE Students (ID int, Name varchar(255));

Sau khi tạo bảng, chúng ta chèn một vài giá trị như sau:
INSERT INTO Students VALUES(1, “Alice”);
INSERT INTO Students VALUES(2, “Bob”);
INSERT INTO Students VALUES(3, “Eve”);

Khi chúng ta chạy tất cả các truy vấn này, Application Server tạo Table V. bảng này có dữ liệu thô, vì vậy nó
không phải là cách tốt để lưu trữ bảng này trong cơ sở dữ liệu của DBMS Server cho lý do an ninh. Cụ thể,
Proxy Server tạo một bảng đã mã hóa mới cho DBMS Server. Bảng mã hóa được tạo mới sẽ như Table VI.

Vì loại dữ liệu của cột ID là nguyên, SEARCH onion không dùng cho cột này. Hơn nữa, vì loại dữ liệu của
cột Name là chuỗi, HOM onion cũng không dùng cho cột này. Như đã mô tả từ trước trong phần II, tất cả các
lớp sẽ ở lớp mã hóa an toàn nhất lúc đầu. Có bảy lớp. Các lớp an toàn nhất của các onion là ba lớp RND,
SEARCH và HOM. Tuy nhiên, chúng cũng có ít chức năng nhất. Ví dụ, lớp RND không rò rỉ bất kỳ dữ liệu
nào, nhưng nó không có chức năng hiệu quả. Nếu chúng ta quay trở lại ví dụ, bằng cách sư rdungj lớp an toàn
nhất, chúng ta có thể chạy các truy vấn như SELECT * FROMStudents;”, “SELECTNameFROMStudents;”
Chú ý rằng Proxy phải thay đổi các truy vấn để bảo vệ nội dung bảng gốc. Nếu chúng ta tiếp tục với truy vấn
“SELECT Name FROM Students;”, truy vấn được thây đổi sẽ như sau:
SELECT C2-IV, C2-Eq FROM DBMS_Table1;

DBMS Server sẽ xử lý truy vấn này, và trả về kết quả trong Table VII


Bảng tương ứng khi Proxy Server giải mã và gửi cho Application Server sẽ giống như Table VIII


Sau khi thực thi UDF, cột C1-Eq đang tại lớp DET, và Proxy Server sẽ cập nhật trạng thái onion hiện tại của
cột này là lớp DET.
DecryptKey(C1-IV, C1-Eq) là cấu trúc của hàm giải mã. Key là khóa giải mã của lớp RND cho cột đầu tiên
của bảng Students. Giả sử rằng giải mã cột này được cho như sau:
DecryptKey(q39f, ge88) = djes
DecryptKey(c8x3, 8n4o) = ektd
DecryptKey(sk7x, x7wk) = 3kw7

Sau khi sửa đổi cơ sở dữ liệu của DBMS Server, Application Server sẽ thay đổi truy vấn cho DBMS như sau:
SELECT C1-IV, C1-Eq FROM DBMS_Table1 WHERE C1-Eq = djes;

Key1 là khóa mã hóa của lớp JOIN cho cột C1 của DBMS_Table1. Và Key2 cũng là khóa mã hóa của lớp
DET cho cột C1 của DBMS_Table1. Sau đó mã hóa của một giá trị sẽ được tạo ra bằng cách mã hóa tất cả các
lớp cho tới lớp hiện tại. Ví dụ, mã hóa giá trị nguyên 1 sẽ được tạo ra như sau:
EncKey2 (EncKey1 (1)) = djes

Trong phần này, chúng ta bị rò rỉ thông tin của các cột được yêu cầu equality check. Nếu dữ liệu trong cùng
một cột có cùng giá trị, bản mã của cơ sở dữ liệu của DBMS Server sẽ giống nhau.

C.Các truy vấn với order leakage
Mã hóa duy trì thứ tự (Order preserving encryption) là một vấn đề khó khăn trong các cơ chế tìm kiếm riêng
tư bao gồm CryptDB. Trong bài viết gốc về CryptDB [10], các tác giả không xem xét mã hóa duy trì thứ tự một
cách chi tiết, nhưng sau đó nhấn mạnh vấn đề này trong một bài viết khác [11]. Phần này có thể được tóm tắt
như sau, nếu giá trị mã hóa của x nhỏ hơn giá trị mã hóa của y, thì ta biết được rằng giá trị x nhỏ hơn y. Nếu
chúng ta tìm ra bất kỳ giá trị mã hóa nào nằm giữa hai giá trị mã hóa này, thì dạng giải mã sẽ nằm giữa x và y.
Lược đồ này để lộ thứ tự, nó là lược đồ yếu nhất. các truy vấn “lớn hơn”, “nhỏ hơn”, ORDER BY, SORT,
MAX, MIN có thể được thực hiện với lược đồ mã hóa. Việc thực hiện mã hóa duy trì thứ tự không được thực
hiện cho đến khi có CryptDB, và thậm chí cũng không có ước lượng nào cho tính thực tế của lược đồ. Có nghĩa
là, CryptDB là triển khai đầu tiên của mã hóa duy trì thứ tự sử dụng thuât toán của Boldyreva [12].


khác cho từng vị trí độc lập. Lược đồ này là có thể chứng minh an toàn có nghĩa là máy chủ không đáng tin cậy
không thể biết được bất cứ thứ gì từ bản rõ.

Hình 4 lược đồ cơ bản
Từ quan điểm của lược đồ cơ bản, nếu chúng ta muốn tìm một từ, chúng ta cung cấp chính từ đó và các khóa
của các vị trí mà từ này có thể xuất hiện Nếu chúng ta không biết gì về các vị trí, chúng ta sẽ cung cấp tất cả các
khóa. Bên không tin cậy sẽ lấy chúng, và XOR bản mã với từ. Nếu kết quả có Si||F(Si) cho một vài S, sự tương
xứng xảy ra và chúng ta sẽ biết vị trí của từ. Nếu bên không tin cậy không biết khóa của một vị trí, không gì sẽ
rỏ rỉ về bản rõ. Tuy nhiên, biết bất cứ gì về các vị trí khiến cho tất cả khóa bị rò rỉ, và điều này có nghĩa tất cả tài
liệu được giải mã cho bên không tin cậy.
Lược đồ thứ hai mở rộng lược đồ cơ bản bằng cách hỗ trợ tìm kiếm được kiếm soát. Trong lược đồ này, khóa
được gắn với một hàm giả ngẫu nhiên khác G trong đó láy các từ dưới một khóa bí mật ngẫu nhiên k’. Với mỗi
từ, nó tạo ra các khóa cho hàm F, ki =fk’(Wi)) với W là một từ trong tài liệu. Sau khi mã hóa tài liệu, nếu chúng ta
muốn tìm một từ, chúng ta sẽ đưa từ và khóa được sinh ra bằng các sử dụng chính từ đó và khóa bí mật k của
chúng ta. Lược đồ này không tiết lộ bất kỳ thông tin gì về vị trí không được bao gồm trong từ tìm kiếm của
chúng ta. Điều này cung cấp tìm kiếm được kiểm soát.


Hình 5 lược đồ thứ hai
Cho đến nay, từ được trao cho các máy chủ không tin cậy như bản rõ, nói chung đây không phải là tình
huống được chấp nhận. Lược đồ thứ ba mở rộng lược đồ thứ hai, và hỗ trợ các tìm kiếm ẩn. Trước khi chúng ta
tìm kiếm một từ, chúng ta mã hóa mỗi từ với một thuật toán bất định như mã hóa chế độ ECB. Từ chúng ta tìm
kiếm được mã hóa và cũng là khóa của chúng ta được sinh ra bằng cách sử dụng hàm G trong lược đồ thứ hai.
Tuy nhiên, khóa phụ thuộc vào từ mã hóa, không phụ thuộc vào từ gốc nữa. Cơ chế còn lại là giống như lược đồ
thứ hai.

Hình 6 Lược đồ thứ ba
Vấn đề với lược đồ thứ hai và ba là việc giải mã không khả thi. Sau khi có gắng nối S và F(S), và XOR
chúng với một từ, chúng ta mã hóa từ. Tuy nhiên, tại phần giải mã, để sinh ra F(S) từ S, chúng ta cần biết khóa
của từ cụ thể này. Và khóa này phụ thuộc vào từ mã hóa. Đó là một mâu thuẫn cho giải mã của một từ mã hóa

Từ quan điểm của các truy vấn SQL, tổng của số nguyên được sư rudngj, không chỉ cho các truy vấn SUM,
mà còn là một phần của tính toán trung bình. Cách thêm chức năng cộng cho bản mã có thể đạt được bằng cách
sử dụng homomorphic. Nếu một chức năng là homomorphic, thì phép nhân của hai bản mã là mã hóa của phép
nhân hoặc phép cộng của bản rõ của hai bản mã. Với CryptDB, phép nhân của bản rõ không được sử udngj từ
quan điểm của các truy vấn SQL, vì vậy thuật toán đồng cấu có tính cộng (additively homomorphic algorithm)
là cần thiết cho cấu trúc này. Additively homomorphism có thể được mô tả như sau:
m1 và m2 là bản rxo của hai giá trị


c1 la mã hóa của m1.
c2 là mã hóa của m2.
c1 × c2 = Enc(m1 × m2) với Enc là hàm mã hóa có đặc điểm additively homomorphic.
Thuật toán đồng cấu được sử dụng trong CryptDB là thuật toán của Paillier. Ngoài ra còn có thuật toán của
Ge & Zdonik. Thuật tán này, nói chugn, nhằm mục đích ngăn chặn sự thỏa hiệp của cơ sở dữ liệu bằng cách xử
lý các truy vấn trên bản mã mà không giải mã chúng. Nó kết hợp tất cả các giá trị của một hàng vào một bản mã
HOM cho mỗi hàng. Tuy nhiên nó yêu cầu gấp hai lần không gian cho trước. Vì lý do này, trong CryptDB thuật
toán này không được thực hiện.
1)Đặc tính đồng cấu của CryptDB: trong CryptDB, chúng ta giữ các giá trị mã hóa trong cơ sở dữ liệu. Vì lý
do này, đặc tính đồng cấu là một giải pháp cho CryptDB. Các truy vấn với SUM và AVG được bao gồm trong
phần này. Chúng ta có thể tạo ra một truy vấn theo ví dụ của chúng ta. Chúng ta sẽ cập nhật bảng của chúng ta
để làm một truy vấn có nghĩa, và tính toán tổng số grade của Students. Bảng được cập nhật của chúng ta sẽ
được minh họa trong Table IX.

Table IX không được giữ bên trong cơ sở dữ liệu. Proxy Server mã hóa các giá trị cho việc tạo ra một bảng
khác cho DBMS Server. Cơ sở dữ liệu được tạo ra cho DBMS Server sẽ giống như Table X.

Truy vấn ví dụ của chúng ta có thể giống như sau:
SELECT

SUM (grade) AS average FROM Students;