Luận án Nghiên cứu phát triển giải pháp xác thực an toàn và quản lý khoá cho cơ sở dữ liệu thuê ngoài

g pháp của Hacigumus, luận án cho một CSDL
rõ DB, với mỗi lược đồ R(A1, A2, ..., An) trong DB được ánh xạ thành lược
đồ RS(etuple, AS1 , A
S
2 , ..., A
S
n) trong CSDL mã hóa tương ứng. Ở đây, etuple
là một thuộc tính chứa bộ mã hoá mà giá trị thu được bằng cách sử dụng
một hàm mã hoá Ek trên bộ dữ liệu rõ với k là khóa bí mật. Cụ thể, với bộ
t = (a1, a2, ..., an) trong R thì etuple = Ek(t). Mỗi thuộc tính A
S
i là các chỉ
mục tương ứng với các thuộc tính Ai của bộ rõ, và nó được dùng để thực hiện
truy vấn trên máy chủ. Để có thể ánh xạ các chỉ mục ASi đến giá trị trong
bản mã etuple thì ta thường chia một khoảng thành các vùng liên tiếp, bằng
nhau và không giao nhau gọi là bucket. Một bucket là một khoảng giá trị
nằm trong giá trị thấp nhất p.low và giá trị cao nhất p.high của miền giá
trị của thuộc tính. Với mỗi thuộc tính Ai, ta xác định các bucket là:
bucket(Ai) = {p1, p2, ..., pk}
trong đó pi ⊂ [p.low, p.high], i ∈ [1, k]
Cụ thể, giả sử giá trị của thuộc tính DIEMSV có miền giá trị từ [0,10], ta
44
Bảng 2.1: Bảng DIEMSV rõ và bảng DIEMSV S mã
DIEMSV DIEMSV S
Tên SV Điểm Etuple H I
Quang 7 C8dilQWWvc5dsqHU1w7WJ828 5 γ
Chiến 6 mRSjcH01cIo2rB56ARMJg 3 α
Mai 9 FZpzMJd6VzkkY1LbPs8g 8 β
Bảo 8 tNmYWHCJ6HSVD8qok6oaEA 3 γ
chia miền mày thành 5 phân hoạch như sau:
bucket(DIEMSV ) = {[0, 2], (2, 4], (4, 6], (6, 8], (8, 10]}
Mỗi bucket được liên kết với một giá trị duy nhất và tập hợp các giá trị
này là miền cho chỉ mục I tương ứng với Ai. Cho một bộ t
S trong RS, giá trị
của thuộc tính ASi trong t
S là một bucket. Điều quan trọng cần lưu ý là để
bảo vệ bí mật dữ liệu tốt hơn, miền của chỉ mục ASi có thể không cùng thứ
tự như là trong các thuộc tính bản rõ Ai.
Thuộc tính Etuple trong bảng 2.1 là giá trị mã của thuộc tính Tên SV và
Điểm. Thuộc tính H và I là các chỉ số thu được bằng cách ánh xạ các giá
trị của thuộc tính Tên SV và Điểm tương ứng của bảng DIEMSV vào các
khoảng của bucket và được định danh thành các giá trị đại diện. Các giá trị
I1 và I4 trong bảng DIEMSV
S có cùng một bucket nên có giá trị bằng nhau
và bằng γ. Để biết được các giá trị nằm trong khoảng nào thì Hacigumus
dùng hàm ident() để định danh và hàm Map() để ánh xạ giá trị vào định
danh đó.
Sau khi tạo ra được bảng DIEMSV S, DO sẽ lưu trữ bảng mã này lên
trên DSP. Quá trình xử lý một câu truy vấn Q sẽ thực hiện hai nhiệm vụ:
(1) Máy khách tiếp nhận Q, chuyển đổi Q thành QS để có thể thực hiện truy
vấn dữ liệu mã trên máy chủ. Máy khách gửi QS đến máy chủ. (2) Máy chủ
thực thi QS và trả về các bản ghi thoả mãn điều kiện RS cho máy khách (có
thể trả về nhiều dữ liệu hơn yêu cầu của Q). Máy khách giải mã RS, loại bỏ
các dữ liệu không thoả mãn điều kiện Q và trả dữ liệu kết quả rõ theo yêu
cầu người dùng.
45
Giả sử câu truy vấn Q có dạng:
"SELECT * FROM DIEMSV WHERE Điểm = 7"
thì sẽ được chuyển thành QS là:
"SELECT etuple FROM DIEMSV S WHERE I = γ".
Sau khi thực hiện câu truy vấn QS, máy chủ DSP trả về cho người dùng
với hai bản ghi là số 1 và 4 vì thỏa mãn điều kiện I = γ. Sau đó, phía người
dùng giải mã các bản ghi này và thu được bản ghi rõ ban đầu và loại bỏ bản
ghi số 4 vì không thỏa mãn điều kiện Điểm = 7". Kết quả cuối cùng người
dùng thu được là bản ghi số 1, đây chính là kết quả của câu truy vấn Q trên
CSDL mã.
Nhược điểm của phương pháp lập chỉ mục dựa trên bucket là phía máy
chủ chỉ thực hiện các câu truy vấn với điều kiện bằng trong QS, các điều
kiện này có thể được ánh xạ vào điều kiện tương đương trên chỉ số. Một điều
kiện truy vấn trong Q có dạng Ai = c, trong đó c là một giá trị không đổi,
thì điều kiện tương ứng trong QS trên chỉ mục I là I = x, trong đó x là
bucket (một khoảng các giá trị). Trong trường hợp Q có điều kiện Điểm = 7
thì điều kiện của QS được chuyển thành I = γ. Nhưng nếu Q có điều kiện
khoảng (range quey) thì phương pháp này khó xử lý. Vì miền chỉ mục không
nhất thiết bảo toàn thứ tự của miền bản rõ, một điều kiện phạm vi có dạng
Ai ≤ c, trong đó c là một giá trị không đổi, phải được ánh xạ thành một
loạt các điều kiện bằng hoạt động trên chỉ số I có dạng I = x1 hoặc I = x2
hoặc I = xk..., trong đó xi là các giá trị liên quan đến bucket tương ứng với
các giá trị bản rõ nhỏ hơn hoặc bằng c.
Như vậy nếu Q có điều kiện Điểm ≤ 8 thì điều kiện của QS được chuyển
thành I = γ hoặc I = α vì γ, α là các bucket đại diện cho Điểm ≤ 8. Trong
trường hợp p.high - p.low là lớn thì ta có nhiều phân hoạch, do đó với điểu
kiện khoảng thì sẽ là hợp của các phân hoạch sao cho thỏa mãn điền kiện
truy vấn.
46
A. Popa và cộng sự [60] đề xuất một giải pháp truy vấn trên dữ liệu mã
gọi là CryptDB, trong đó mô hình mã hoá theo phương pháp mã hóa từng ô
dữ liệu và cách thức thực thi truy vấn trên CSDL mã bằng cách sử dụng một
máy chủ làm trung gian gọi là CryptDB proxy. Với mã hóa theo từng ô dữ
liệu thì CSDL vẫn đảm bảo được mối quan hệ giữa các bảng, nên có thể sử
dụng các tính chất quan hệ của CSDL. CryptDB sử dụng nhiều thuật toán
mã hóa khác nhau để phù hợp với từng loại câu truy vấn. Chính vì vậy, dữ
liệu sau khi mã hóa sẽ tăng lên đáng kể do thêm nhiều cột mã hóa.
106 CommuniCationS oF the aCm | SepteMBer 2012 | voL. 55 | No. 9
research highlights 
need an adaptive scheme that dynamically adjusts encryp-
tion strategies.
CryptDB’s adjustable query-based encryption technique 
solves this problem by dynamically adjusting the layer of 
encryption on the DBMS server. The idea is to encrypt each 
data item in one or more onions: that is, each value is dressed 
in layers of increasingly stronger encryption, as shown in 
Figures 2 and 3. Each layer of each onion enables a certain 
class of computation, as explained earlier.
Multiple onions are required because the computations 
supported by different encryption schemes are not always 
strictly ordered. Depending on the type of the data, CryptDB 
may not maintain all onions for each column. For instance, 
the Search onion does not make sense for integers, and the 
Add onion does not make sense for strings.
For each layer of each onion, the proxy uses the same 
key for encrypting values in the same column, and differ-
ent keys across tables, columns, onions, and onion layers. 
Using the same key for all values in a column allows the 
proxy to perform operations on a column without having 
to compute separate keys for each row that will be manip-
ulated. Using different keys across columns prevents the 
server from learning any additional relations. All of these 
keys are derived from the master key MK. For example, for 
table t, column c, onion o, and encryption layer l, the proxy 
uses the key
 Kt,c,o,l = PRPMK (table t, column c, onion o, layer l ), (1)
where PRP is a pseudorandom permutation (e.g., AES).
Each onion starts out with the most secure encryption 
scheme as the top level (RND for onions Eq and Ord, HOM 
for onion Add, and SEARCH for onion Search). As the proxy 
receives SQL queries from the application, it determines 
whether layers of encryption need to be removed. If a query 
requires predicate P on column c, the proxy first establishes 
what onion layers are needed to compute P on c. If the 
encryption of c is not already at an onion layer that allows P, 
the proxy strips off the onion layers to allow P on c, by send-
ing the corresponding onion key to the server. The proxy 
never decrypts the data past the least-secure non-plaintext 
encryption onion layer, which may be overridden by the 
schema developer to be a more secure layer (e.g., one may 
OPE-encrypted columns to the server if users request order 
queries on those columns. OPE is proven to be equivalent 
to a random mapping that preserves order.1 However, such 
a mapping leaks half of the data bits in the worst case.2 We 
are currently working on a new scheme that provably reveals 
only order and leaks no bits in addition.
homomorphic encryption (hOM). HOM is as secure a prob-
abilistic encryption scheme as RND, but allows the server 
to perform computations on encrypted data with the final 
result decrypted at the proxy. Although fully homomorphic 
encryption is prohibitively slow, homomorphic encryption 
for specific operations is efficient. To support additions, we 
implemented the Paillier cryptosystem.17 With Paillier, mul-
tiplying the encryptions of two values results in an encryp-
tion of the sum of the values, that is, HOMK (x) · HOMK ( y) = 
HOMK (x + y), where the multiplication is performed modulo 
some public-key value. To compute SUM aggregates, the proxy 
replaces SUM with calls to a UDF that performs Paillier multi-
plication on a column encrypted with HOM. HOM can also be 
used to compute averages by having the DBMS server return 
the sum and the count separately, and to increment values 
(e.g., SET id = id + 1). HOM ciphertexts are 2048 bits long.
Join ( JOiN and OPe-JOiN). A separate encryption scheme is 
needed to allow equality join between two columns, because 
we use different column-specific keys for DET to prevent 
correlations between columns. JOIN not only supports all 
the operations allowed by DET, but also enables the server to 
determine repeating values between two different columns. 
OPE-JOIN enables joins by order relations. We provide a new 
cryptographic scheme for JOIN (Section 3.4).
Word search (SearCh). SEARCH is used to perform 
searches on encrypted text to support operations such as 
MySQL’s LIKE operator. SEARCH is nearly as secure as RND. 
We implemented the method of Song et al.22 SEARCH cur-
rently supports only full word searches.
When the user performs a query such as SELECT * FROM 
messages WHERE msg LIKE “% alice %”, the proxy gives the 
DBMS server a token, which is an encryption of alice. The 
server cannot decrypt the token to figure out the underly-
ing word. Using a user-defined function, the DBMS server 
checks if any of the word encryptions in any message match 
the token. All that the server learns from a SEARCH query is 
whether the token matched a message or not, and only for 
the tokens requested by the user. The server would learn the 
same information when returning the result set to the users, 
so the scheme reveals the minimal amount of additional 
information needed to return the result.
3.2. adjustable query-based encryption
Our goal is to use the most secure encryption schemes that 
enable running the requested queries. For example, if the 
application issues no queries that compare data items in 
a column, or that sort a column, the column should be 
encrypted with RND. For columns that require equality 
checks but not order checks, DET suffices. The problem is 
that the query set is not always known in advance. Thus, we 
Figure 2. onion encryption layers and the classes of computation 
they allow. onion names stand for the operations they allow at some 
of their layers (equality, order, Search, and addition). a random iV 
for RnD (Section 3.1), shared by the RnD layers in Eq and Ord, is also 
stored for each data item.
Onion Ord
OPE-JOIN:
range join
OPE: order
any value
RND: no functionality
any value
DET: equality selection
RND: no functionality
JOIN: equality join
int value
HOM: add
Onion Search
SEARCH
text value
Onion Eq Onion Add
Hình 2.3: Mô hình mã hoá củ hành (Onion) do Popa đề xuất [60]
CryptDB sử dụng kết hợp hai kỹ thuật mã hóa là mã hóa nhận thức
SQL (SQL-aware encryption - SQLAE) và mã hóa dựa trên truy vấn có
thể điều chỉnh (adjustable query-based encryption -AQE). SQLAE sử dụng
nhiều thuật toán mã hóa khác nhau như: Mã hóa ngẫu nhiên (Random -
RND) để bảo mật tối đa của lớp mã hóa trong CryptDB, mã hóa tất định
(Deterministic - DET) để thực hiện các phép bằng, GROUP BY, COUNT,
DISTINCT..., mã hóa bảo toàn thứ tự (Order-preserving encryption - OPE)
để thực hiện các phép toán ORDER BY, MIN, MAX, SORT..., mã hóa đồng
cấu (Homomorphic encryption - HOM) để có thể tính toán trên dữ liệu mã mà
không cần giải mã dữ liệu, mã hóa có thể tìm kiếm (Word search - SEARCH)
để tìm kiếm trên chuỗi khi sử dụng phép toán LIKE. Chính vì vậy, SQLAE
sử dụng cho hầu hết các truy vấn SQL được tạo thành từ một tập hợp các
toán tử cơ bản như: So sánh bằng, so sánh thứ tự, tổng, và phép nối. Trong
47
khi đó, mục đích của AQE là điều chỉnh linh hoạt lớp mã hóa trên máy chủ
DBMS. Ý tưởng của AQE là mã hóa từng mục dữ liệu trong một hoặc nhiều
củ hành (Onion). Nghĩa là, mỗi giá trị mã hóa được nằm trong các lớp mã
hóa mạnh hơn (hình 2.3). Mỗi lớp của củ hành cho phép thực hiện một số
phép tính toán tương ứng với từng loại SQLAE.
104 CommuniCationS oF the aCm | SepteMBer 2012 | voL. 55 | No. 9
research highlights 
CryptDB is careful about what relations between tuples it 
reveals to the DBMS server. To execute a GROUP BY on column c, 
for instance, the server need not know the order of the items 
in column c, nor any information about other columns. To 
execute an ORDER BY, or to find the MAX or MIN, CryptDB 
reveals the order of items in that column, but not otherwise.
CryptDB incorporates two techniques: SQL-aware encry-
ption and adjustable query-based encryption. SQL-aware 
encryp tion uses the observation that most SQL queries 
are made up of a well-defined set of basic operators, such 
as equality checks, order comparisons, aggregates (sums), 
and joins. CryptDB supports these operators over encrypted 
data. By adapting known encryption schemes (for equality, 
additions, and order checks), and using a new privacy- 
preserving cryptographic scheme for joins, CryptDB encry-
pts each data item in a way that allows the DBMS to execute 
on the transformed data.
The second technique is adjustable query-based encryp-
tion: CryptDB carefully adjusts the SQL-aware encryption 
scheme for any given data item to support different opera-
tions on this data. To implement these adjustments effi-
ciently, CryptDB uses onions of encryption. Onions are a novel 
way to compactly store multiple ciphertexts within each 
other in the database and avoid revealing weaker encryption 
schemes when they are not needed.
CryptDB provides confidentiality for the content of the 
data and for names of columns and tables, but does not 
hide the overall table structure, the number of rows, the 
types of columns, or the approximate size of data in bytes. 
The only information that CryptDB reveals to the DBMS 
server is relationships among data items correspond-
ing to classes of computation that queries perform on the 
database, such as comparing items for equality, sorting, or 
performing word search. The granularity at which CryptDB 
allows the DBMS to perform a class of computations is an 
entire column (or a group of joined columns, for joins), 
which means that even if a query requires equality checks 
for a few rows, executing that query on the server would 
require revealing that class of computation for an entire 
column. Section 3.1 describes how these classes of com-
putation map to CryptDB’s encryption schemes, and the 
 information they reveal.
CryptDB provides the following properties:
2.1. threat 1: DBmS server compromise
CryptDB provides confidentiality (data secrecy) in the face 
of an attacker with full read access to the data stored in 
the DBMS server. The attacker is assumed to be passive: 
she wants to learn confidential data, but does not change 
queries issued by the application, query results, or the data 
in the DBMS. This threat includes DBMS software compro-
mises, root access to DBMS machines, and even access to 
the RAM of physical machines. With the rise in database 
consolidation inside enterprise data centers, outsourcing 
of databases to public cloud computing infrastructures, 
and the use of third-party DBAs, this threat is increasingly 
important. We focus on confidentiality, not data integrity 
or availability.
CryptDB addresses this threat by executing SQL que-
ries over encrypted data on the DBMS server. As shown in 
Figure 1, CryptDB works by intercepting all SQL queries 
in a trusted proxy; existing applications do not need to be 
modified to use CryptDB, but all queries must go through 
the proxy. The proxy stores a master secret key, which 
it uses to rewrite queries to execute on encrypted data. 
The proxy encrypts and decrypts all data, and changes 
some query operators, while preserving the semantics of 
the query. Because the DBMS server never receives decryp-
tion keys to the plaintext, it never sees sensitive data, 
ensuring that our passive adversary cannot gain access to 
private information.
The main challenge when executing queries on encryp-
ted data lies in the tension between minimizing the 
amount of confidential information revealed to the 
DBMS server and the ability to efficiently execute a vari-
ety of queries. Our strategy is to allow the DBMS server to 
perform query processing on encrypted data mostly as it 
would on an unencrypted database (important for practi-
cality), while restricting the server to computing only the 
functions required to process authorized queries (important 
for confidentiality). For example, if the DBMS needs to 
perform a GROUP BY on column c, the DBMS server should 
be able to determine which items in that column are equal 
to each other, but not the actual content of each item. 
Therefore, the proxy needs to enable the DBMS server to 
determine relationships among data items necessary to 
process a query.
Figure 1. CryptDB’s architecture consisting of two parts: a proxy and an unmodified DBMS. CryptDB uses user-defined functions (uDFs) 
to perform cryptographic operations in the DBmS Rectangu ar and rounded boxes represent processes and data, respectively. Shading 
indicates components added by CryptDB. Dashed lines indicate separation between users’ computers, the application server, a server 
running CryptDB’s proxy (which is usually the same as the application server), and the DBmS server. the scope of the two threats CryptDB 
addresses is shown as dotted lines.
User 1
Application
DBMS server
Key setup
Password P1
Data
(encrypted)
Unmodified DBMS CryptDB UDFs
Application serverUsers' computers
Threat 1
User 2
Password P2
Active
session
Threat 2
Proxy
Active keys:
P1
Annotated
schema
CryptDB proxy 
Hình 2.4: Mô hình truy vấn trên dữ liệu mã do Popa đề xuất [60]
Cách thức thực hiện truy vấn trong CryptDB được mô tả như hình 2.5.
SepteMBer 2012 | voL. 55 | No. 9 | CommuniCationS oF the aCm 107
specify that credit card information may at worst be at DET, 
and never at OPE).
CryptDB implements onion layer decryption using UDFs 
that run on the DBMS server. For example, in Figure 3, to 
decrypt onion Ord of column 2 in Table 1 to layer OPE, the 
proxy issues the following query to the server, invoking the 
DECRYPT_RND UDF:
UPDATE Tabl 1 SET
C2-Ord = DECRYPT_RND(K, C2-Ord, C2-IV,)
where K is the appropriate key computed from Equation (1). 
At the same time, the proxy updates its own internal state to 
remember that column C2-Ord in Table1 is now at layer OPE 
in the DBMS.
Note that onion decryption is performed entirely by the 
DBMS server. In the steady state, no server-side decryp-
tions are needed, because onion decryption happens only 
when a new class of computation is requested on a col-
umn. For example, after an equality check is requested on 
a column and the server brings the column to layer DET, 
the column remai s in that state, and future queries with 
equality checks require no decryption. Thi property is the 
main reason why CryptDB’s run-time overhead is modest 
(Section 5).
3.3. executing over encrypted data
Once the onion layers in the DBMS are at the layer necessary 
to execute a query, the proxy transforms the query to operate 
on these onions. In particular, the proxy replaces column 
names in a query with corresponding onio