Luận án Một số hệ mã hóa với quyền giải mã linh động

1 . 
Và tính: 
𝐾𝑘 = 
𝑒(𝑔𝑖𝐶2)
𝑒 (𝑑𝑖 .∏ 𝑔𝑛+1−𝑗+𝑖𝑗∈𝑆𝑘
𝑗≠𝑖
, 𝐶1. 𝑌𝑘) ∏
ℓ = 𝑚+ 1
ℓ = 1
ℓ ≠ 𝑘
 𝑒 (𝑑𝑖 .∏ 𝑔𝑛+1−𝑗+𝑖𝑗∈𝑆ℓ
, 𝐶1. 𝑌ℓ)
(2.18) 
=
𝑒 (𝑔𝛼
𝑖
,∏
ℓ = 𝑚 + 1
ℓ = 1
 (𝑣.∏ 𝑔𝑛+1−𝑗𝑗∈𝑆ℓ
)𝑟+𝑦ℓ)
𝑒 (𝑣𝛼
𝑖
 . (∏ 𝑔𝑛+1−𝑗𝑗∈𝑆𝑘
𝑗≠𝑖
)𝛼
𝑖
, 𝑔𝑟+𝒴𝑘) . ∏
ℓ = 𝑚 + 1
ℓ = 1
ℓ ≠ 𝑘
 𝑒 (𝑣𝛼
𝑖
. (∏ 𝑔𝑛+1−𝑗𝑗∈𝑆ℓ
)
𝛼𝑖
, 𝑔𝑟+𝒴ℓ ) 
(2.19) 
46 
= 
𝑒 (𝑔𝛼
𝑖
, (𝑣.∏ 𝑔𝑛+1−𝑗𝑗∈𝑆𝑘 )
𝑟+𝒴𝑘)
𝑒 (𝑣𝛼
𝑖
 . (∏ 𝑔𝑛+1−𝑗𝑗∈𝑆𝑘
𝑗≠𝑖
)
𝛼𝑖
, 𝑔𝑟+𝒴𝑘) 
 . ∏
𝑒 (𝑔𝛼
𝑖
, (𝑣 . ∏ 𝑔𝑛+1−𝑗𝑗∈𝑆ℓ )
 𝑔𝑟+𝒴ℓ
 ) 
𝑒 (𝑣𝛼
𝑖
. (∏ 𝑔𝑛+1−𝑗𝑗∈𝑆ℓ )
𝛼𝑖
, 𝑔𝑟+𝒴ℓ ) 
ℓ=𝑚+1
ℓ=1
ℓ≠𝑘
(2.20) 
= 
𝑒 ((𝑣. ∏ 𝑔𝑛+1−𝑗𝑗∈𝑆𝑘 )
𝛼𝑖 , 𝑔𝑟+𝒴𝑘)
 𝑒 ( (𝑣. ∏ 𝑔𝑛+1−𝑗𝑗∈𝑆𝑘
𝑗≠𝑖
)
𝛼𝑖
, 𝑔𝑟+𝒴𝑘) 
 . ∏
𝑒 ((𝑣 . ∏ 𝑔𝑛+1−𝑗𝑗∈𝑆ℓ )
𝛼𝑖
, 𝑔𝑟+𝒴ℓ) 
 𝑒 ((𝑣 . ∏ 𝑔𝑛+1−𝑗𝑗∈𝑆ℓ )
𝛼𝑖
, 𝑔𝑟+𝒴ℓ ) 
ℓ=𝑚+1
ℓ=1
ℓ≠𝑘
(2.21) 
= 𝑒(𝑔𝑛+1−𝑖
𝛼𝑖 , 𝑔𝑟+𝒴𝑘) = 𝑒( 𝑔𝑛+1, 𝑔
𝑟+𝒴𝑘) = 𝑒(𝑔𝑛+1, 𝑔)
𝑟+𝒴𝑘 (2.22) 
Lưu ý, 𝑑𝑖 = 𝑣
𝛼𝑖 , 𝑔𝑛+1−𝑗+𝑖 = 𝑔𝑛+1−𝑗
𝛼𝑖 , và 𝑔𝑛+1−𝑖
𝛼𝑖 = 𝑔𝑛+1. Ngoài ra, khi mã hóa người 
lập mã cần biết khóa bí mật EK nên đây vẫn là hệ mã hóa khóa bí mật. 
2.2.3. Một số cải tiến đối với hệ MCBE1 và MCBE2 
Có ba cải tiến đối với hệ mã quảng bá đa kênh MCBE1 và MCBE2 như sau: 
 1. Các tác giả [60] đã cải tiến hệ mã MCBE1 bằng cách rút ngắn hơn độ dài 
của khóa công khai. Tuy nhiên, độ dài khóa công khai trong hệ [60] vẫn dài, cụ thể 
là vẫn có độ dài tuyến tính với n. 
 2. Các tác giả [15] làm tăng hơn nữa an toàn và hiệu năng của hệ MCBE1 và 
MCBE2 khi đưa ra xây dựng hệ MCBE1 và MCBE2 mới dựa trên Parings loại ba. 
 3. Hai cải tiến ở trên vẫn chưa khắc phục được điểm yếu của hệ MCBE1 và 
MCBE2 là mã hóa khóa bí mật. Gần đây, các tác giả trong bài báo [3] đã giới thiệu 
hệ mã hóa quảng bá đa kênh mới có tính chất là mã hóa khóa công khai, tức là người 
lập mã không cần phải biết bất kỳ tham số bí mật gì khi thực hiện mã hóa. 
2.3. Lược đồ mã hóa quảng bá đa kênh đề xuất 
 Luận án đã đề xuất một lược đồ mã hóa quảng bá đa kênh cải tiến mới có các 
ưu điểm so với các mã hóa quảng bá đa kênh khác như sau: 
 Là mã hóa quảng bá đa kênh khóa công khai, tức là người lập mã không cần 
phải biết bất kỳ tham số bí mật gì khi thực hiện mã hóa. 
 Có tốc độ giải mã nhanh. Cụ thể, người giải mã chỉ cần tính 2 phép tính parings 
khi giải mã. Tác giả cài đặt hệ mã và đưa ra các đánh giá cụ thể về thời gian chạy của 
hệ mã. 
47 
 Có độ dài bản mã Hdr chỉ gồm hai phần tử, độ dài khóa bí mật của người dùng 
có số lượng phần tử chính bằng số lượng kênh mà người dùng đăng ký để xem. 
 Được xây dựng dựa trên hệ mã hóa Delerablee [25] đã trình bày tại mục 1.2.3 
2.3.1. Ý tưởng xây dựng 
 Trong hệ [25], khóa bí mật của người dùng có dạng: 
𝑔
1
𝛼+𝐼𝐷𝑢 
 Bản mã tương ứng với tập người dùng S có dạng: 
ℎ𝑘.∏ (𝛼+𝐼𝐷𝑖)𝑖∈𝑆 
và miễn là u ∈ S thì người dùng u có thể tính được khóa phiên e(g, h)k, k là số ngẫu 
nhiên được chọn mỗi lần lập mã. 
 Trong tổng thể của hệ mã hóa quảng bá đa kênh, chúng ta có m tập người dùng 
(tương ứng với m kênh) S1,..., Sm, và mỗi tập có một khóa phiên tương ứng. Ý tưởng 
là, với mỗi tập người dùng Si , i = 1,.., m, đặt khóa phiên của tập này là 𝑒(𝑔, ℎ)𝑘.𝛽𝑖, 
trong đó β1,..., βm là các số ngẫu nhiên được chọn ở thuật toán khởi tạo. Với ý tưởng 
như vậy, khóa bí mật của người dùng lúc này sẽ có dạng: 
𝑔
𝛽𝑖
𝛼+𝐼𝐷𝑢𝑖 
Vì mỗi người dùng u có thể đăng ký tối đa m kênh nên mỗi người dùng u sẽ có tối 
đa m khóa bí mật 𝑔
𝛽𝑖
𝛼+𝐼𝐷𝑢𝑖, i = 1,..., m. 
2.3.2. Lược đồ mã hóa đề xuất và so sánh 
 Mã hóa được xây dựng như sau: 
Khởi tạo (1⋋): 
 Đầu vào của giải thuật là tham số an toàn ⋋, đầu ra của giải thuật là khóa bí 
mật của hệ thống msk, khóa công khai của hệ thống, khóa công khai bao gồm cả m 
là số tối đa các kênh, n là số tối đa người dùng đăng ký vào một kênh. 
Đặt N = m·n, giải thuật tạo ra hệ thống ánh xạ song tuyến 𝐷 = (𝑝,𝔾, �̃�, 𝔾𝑇 , 𝑒), chọn 
ngẫu nhiên ℎ
$
← , �̃�, 𝑔
$
← ,𝔾 và 𝛼, 𝛽1,  , 𝛽𝑚
$
← ℤ𝑝
∗ . 
 Giả sử ℋ là hàm băm sao cho ℋ: {0,1}∗ → ℤ𝑝
∗ . Giải thuật cho đầu ra: 
48 
param = (𝐷, {ℎ𝛼
𝑖
}
𝑖=0,,𝑁
, {ℎ𝛽𝑖𝛼
𝑗
}𝑖=1,,𝑚
𝑗=0,,𝑁
 , 𝑔𝛼 , {𝑒(𝑔, ℎ)𝛽𝑖}
𝑖=1,,𝑚
,ℋ) 
và khóa bí mật của hệ thống: 
msk = (𝑔, 𝛼, 𝛽1,  , 𝛽𝑚) 
Tạo khóa (IDi,j, msk, param) : 
 Giả sử, định danh của người dùng i trong kênh j là chuỗi bit bất kỳ IDi,j ∈ {0, 
1}∗. Người dùng i đăng ký vào kênh j sẽ nhận được khóa bí mật tương ứng sau: 
𝑠𝑘𝐼𝐷𝑖,𝑗 = 𝑔
𝛽𝑗
𝛼+ℋ(𝐼𝐷𝑖,𝑗) 
 Ký hiệu (i, j) là chỉ số khóa bí mật. Trong hệ thống, mỗi người dùng có thể 
đăng ký vào nhiều kênh và nhận khóa bí mật tương ứng với từng kênh. Ví dụ người 
dùng i đăng ký vào kênh 1,..., t, người dùng i sẽ nhận các khóa bí mật {𝑠𝑘𝐼𝐷𝑖,𝑗}𝑗=1,,𝑡
. 
Mã hóa (param, S1,..,St): 
 Đầu vào của giải thuật là t tập chỉ số khóa bí mật của người dùng trong t kênh 
S1,.., St , t ≤ m. Trong đó S1,.., St là các tập không giao nhau. Ký hiệu 𝑆 =∪𝑖=1
𝑡 𝑆𝑖 là 
tập đầy đủ tất cả các chỉ số khóa bí mật của người dùng cho một lần mã hóa. Giải 
thuật chọn ngẫu nhiên 𝑘 ∈ ℤ𝑝
∗ , tính khóa phiên bí mật cho t kênh như sau: 
𝐾𝑖 = 𝑒(𝑔, ℎ)
𝑘𝛽𝑖 , 𝑖 = 1, , 𝑡 
Sau đó, tính bản mã Hdr = (C1, C2) như sau: 
𝐶1 = 𝑔
−𝛼.𝑘 , 𝐶2 = ℎ
𝑘.∏ (𝛼+ℋ(𝐼𝐷𝑖,𝑗))(𝑖,𝑗)∈𝑆 
Cuối cùng, giải thuật cho đầu ra K = {𝐾𝑖}𝑖=1,,𝑡 và Hdr = (𝐶1, 𝐶2) bao gồm cả thông 
tin của tập S. 
Giải mã (𝑠𝑘𝐼𝐷𝑖,𝑗, Hdr, param): 
 Giải thuật đầu tiên kiểm tra xem chỉ số (i, j) ∈ S có đúng hay không, nếu sai 
thì cho đầu ra là ⊥. Nếu đúng là thuộc tập S, giải thuật tính giá trị 𝐾′ = ℎ𝛾 trong đó: 
49 
𝛾 =
𝛽𝑗
𝛼
(
∏ (𝛼 +ℋ(𝐼𝐷𝑖′,𝑗′))
(𝑖′,𝑗′)∈𝑆
(𝑖′,𝑗′)≠(𝑖,𝑗)
− ∏ ℋ(𝐼𝐷𝑖′,𝑗′)
(𝑖′,𝑗′)∈𝑆
(𝑖′,𝑗′)≠(𝑖,𝑗) )
 (2.24) 
Giải thuật có thể tính 𝐾′ từ các thông tin có trong khóa công khai. 
Đặt: 
𝐵 = ∏ ℋ(𝐼𝐷𝑖′,𝑗′)
(𝑖′,𝑗′)∈𝑆
(𝑖′,𝑗′)≠(𝑖,𝑗)
Giải thuật cuối cùng cho đầu ra: 
𝐾𝑗 = (𝑒(𝐶1, 𝐾′). 𝑒 (𝑠𝑘𝐼𝐷𝑖,𝑗 , 𝐶2))
1
𝐵
Tính đúng đắn: 
𝐾𝑗 = (𝑒(𝐶1, 𝐾′). 𝑒 (𝑠𝑘𝐼𝐷𝑖,𝑗 , 𝐶2))
1
𝐵
 (2.25) 
= (𝑒(𝑔−𝛼.𝑘, ℎ𝛾) . 𝑒 (𝑔
𝛽𝑗
𝛼+ℋ(𝐼𝐷𝑖,𝑗). ℎ𝑘.
∏ (𝛼+ℋ(𝐼𝐷𝑖,𝑗))(𝑖,𝑗)∈𝑆 ))
1
𝐵
 (2.26) 
= (𝑒(𝑔, ℎ)
𝑘𝛽𝑗∏ ℋ(𝐼𝐷𝑖′,𝑗′)(𝑖′,𝑗′)∈𝑆
(𝑖′,𝑗′)≠(𝑖,𝑗) )
1
𝐵
 (2.27) 
= 𝑒(𝑔, ℎ)𝑘𝛽𝑗 (2.28) 
So sánh với các hệ mã khác: 
 Để đánh giá độ hiệu quả của hệ mã hóa đa kênh đề xuất, nghiên cứu sinh lập 
Bảng 2.1 so sánh với một số hệ mã hóa quảng bá đa kênh khác, trong đó: 
 Header là độ dài của bản mã. 
 S-key là độ dài khóa bí mật. 
 P-key là độ dài khóa công khai. 
 Dec time là thời gian giải mã. 
50 
 Security là đánh giá an toàn của hệ mã. Lưu ý rằng, với mô hình bảo mật chọn 
lọc, kẻ tấn công phải thông báo trước tập người dùng mà kẻ tấn công định tấn công 
trước khi biết các thông tin khác như: Khóa bí mật của các người dùng khác, chọn 
bản mã biết bản rõ, Như vậy có nghĩa là, quyền của kẻ tấn công sẽ yếu hơn so với 
mô hình thích nghi, khi kẻ tấn công không cần phải thông báo trước tập người dùng 
mà kẻ tấn công định tấn công. 
 Ngoài ra, mô hình an toàn dùng bộ tiên tri ngẫu nhiên thì hệ thống cũng sẽ 
kém an toàn hơn vì dùng ROM có nghĩa là giả thuyết hàm băm là lý tưởng không có 
bất kỳ khó khăn nào. Tuy nhiên, trong cài đặt thực tế như họ hàm băm SHA thì không 
có hàm băm nào là lý tưởng. 
 Trong Bảng 2.1 mô hình có CCA nghĩa là kẻ tấn công có quyền chọn tùy ý 
bản mã và biết bản rõ tương ứng, còn mô hình không có CCA thì kẻ tấn công không 
có quyền này. 
 Tóm lại, mô hình an toàn mạnh nhất sẽ là CCA và yếu nhất sẽ là 
Selective+ROM. 
 Setting là kiểu mã hóa bí mật (Secret-key) hay công khai (Public-key). 
 Header S-key P-key Dec time Security Setting 
[15]-1 2|𝔾| m|�̃�| 
3mn|𝔾|+ 
2mn|�̃�| 
(m + 1)P Selective Bí mật 
[15]-2 3|𝔾|+1|𝔾| m|�̃�| 
2mn|𝔾| + 
2mn|�̃�| 
(m + 2)P 
Selective-
CCA+ROM 
Bí mật 
[60] 2|𝔾| m|�̃�| 
2mn|𝔾|+ 
2mn|�̃�| 
(m + 1)P Selective Bí mật 
[3] 2|𝔾| m|𝔾| 
(mn + m) 
|𝔾| 
2P Selective Công khai 
MCBE 
đề xuất 
1|𝔾|+1|�̃�| m|𝔾| m2n|�̃�| 2P 
Selective 
+ROM 
Công khai 
Bảng 2.1. So sánh một số hệ mã hóa đa kênh với MCBE đề xuất 
51 
 Trong đó: 
 n là số tối đa người dùng trong một kênh, 
 m là số tối đa kênh, 
 P là một phép tính Parings. 
 |𝔾| là kích thước của một phần tử trong nhóm 𝔾, 
 |�̃�| là kích thước của một phần tử trong nhóm �̃�. 
 Hệ của nghiên cứu sinh là hệ mã hóa khóa công khai trong khi 3 hệ [15]-1 và 
[15]-2 và [60] đều là mã hóa bí mật. Độ dài của bản mã hệ nghiên cứu sinh đề xuất 
có độ dài ngắn nhất. Thời gian giải mã của hệ nghiên cứu sinh đề xuất chỉ là 2 phép 
toán Perings (2P) còn các hệ khác lớn hơn hoặc bằng. 
2.3.3. Đánh giá an toàn 
 Trong mục này, tác giả sẽ chứng minh rằng hệ mã đạt an toàn CPA dưới giả 
thuyết (hay còn được hiểu là bài toán khó) GDDHE tương tự như trong bài báo [25], 
trong đó giả thuyết GDDHE ở đây được định nghĩa như sau: 
Định nghĩa 2.2: Bài toán khó GDDHE: Giả sử (p, 𝔾, �̃�, 𝔾T, e) là hệ thống ánh xạ 
song tuyến, chọn ngẫu nhiên t,m, n, k, β1,  , βm
$
← ℤp
∗ sao cho t > N = m · n 
 Đặt f(X) = ∏ (X + xi)
t
i=1 và g(X) = ∏ (X + xi)
t+n
i=t+1 , xi
$
← ℤp
∗ , i = 1,.., N, là 
hai đa thức nguyên tố cùng nhau có bậc tương ứng là t và n. Đặt đa thức: 
 q(X) = ∏ (X + xi)
n+t
i=n+1 và hai phần tử sinh là g0 ∈ 𝔾, h0 ∈ �̃�. Cho trước: 
�⃗� = (𝑔0, {𝑔0
𝛽𝑚𝑓(𝛼)
𝛼+𝑥𝑖 }𝑖=1,,𝑛, {𝑔0
𝛽𝑖.𝛼
𝑗
}𝑖=1,,𝑚−1
𝑗=0,,𝑡−1
, 𝑔0
𝛼.𝑓(𝛼), 𝑔0
𝑘.𝛼.𝑓(𝛼)
(2.29) 
ℎ0ℎ0
𝛼 ,  , ℎ0
𝛼2𝑡+𝑛 , {ℎ0
𝛽𝑖𝛼
𝑗
} 𝑖=1,,𝑚
𝑗=0,,2𝑡+𝑛
, ℎ0
𝑘.𝑞(𝛼), 𝑒(𝑔0ℎ0)
𝑘.𝛽1.𝑓(𝛼),  , 𝑒(𝑔0ℎ0)
𝑘.𝛽𝑚−1.𝑓(𝛼)) 
hãy phân biệt giữa 𝑇 = 𝑒(𝑔0, ℎ0)
𝑘.𝛽𝑚.𝑓(𝛼) ∈ 𝔾𝑇 và một phần tử ngẫu nhiên 
𝑇 = 𝑅 ∈ 𝔾𝑇 . 
 Để phân biệt giá trị T, kẻ tấn công 𝒜 mà cho đầu ra một bit b ∈ {0, 1} có lợi 
thế 𝜖 trong việc giải bài toán GDDHE ở trên nếu: 
|𝑃𝑟[𝒜(�⃗� , 𝑇 = 𝑒(𝑔0ℎ0)
𝑘.𝛽𝑚.𝑓(𝛼)) = 0] − 𝑃𝑟[𝒜(�⃗� , 𝑇 = 𝑅) = 0]| ≥ 𝜖 
52 
Định nghĩa 2.3: Bài toán GDDHE là một bài toán khó nếu không tồn tại kẻ tấn công 
nào chạy trong thời gian đa thức mà có lợi thế ϵ đáng kể trong việc phân biệt T. 
 Chứng minh độ khó của bài toán GDDHE ở trên như sau: 
Chứng minh: Đầu tiên viết lại bài toán GDDHE ở dạng số mũ: 
𝑃 = {1, {𝛽𝑚
𝑓(𝛼)
𝛼 + 𝑥𝑖
}𝑖=1,,𝑛, {𝛽𝑖𝛼
𝑗}𝑖=1,,𝑚−1
𝑗=0,,𝑡−1
, 𝛼𝑓(𝛼), 𝑘𝛼𝑓(𝛼) } 
𝑄 = {1, 𝛼, , 𝛼2𝑡+𝑛, {𝛽𝑖𝛼
𝑗} 𝑖=1,,𝑚
𝑗=0,,2𝑡+𝑛
, 𝑘𝑞(𝛼)} 
𝑅 = {𝑘𝛽1𝑓(𝛼),  , 𝑘𝛽𝑚−1𝑓(𝛼)} 
𝑓 = 𝑘𝛽𝑚𝑓(𝛼) 
 Giả sử rằng f không độc lập tuyến tính với (P, Q, R), tức là kẻ tấn công có thể 
tìm được các giá trị bi,j , ci sao cho đẳng thức sau đúng 
𝑓 = ∑ 𝑏𝑖,𝑗 . 𝑝𝑖 . 𝑞𝑗 + ∑ 𝑐𝑖𝑟𝑖
𝑟𝑖𝑅𝑝𝑖𝑃
𝑞𝑗𝑄
 Dùng cả k và βm để phân tích f. Do cả k và βm là các số ngẫu nhiên được chọn 
trước nên suy ra kẻ tấn công cần tìm ai, bj sao cho biểu thức sau đúng: 
𝑘𝛽𝑚𝑓(𝛼) = 𝑘𝛽𝑚(𝑏0𝛼𝑓(𝛼)𝛼
0 +⋯+ 𝑏2𝑡+𝑛𝛼𝑓(𝛼)𝛼
2𝑡+𝑛)+𝑎1
𝑓(𝛼)
𝛼 + 𝑥1
𝑞(𝛼) + ⋯
+ 𝑎𝑛
𝑓(𝛼)
𝛼 + 𝑥𝑛
𝑞(𝛼) 
(2.30) 
𝑘𝛽𝑚𝑓(𝛼) = 𝑘𝛽𝑚𝑓(𝛼) (𝐺(𝛼) + 𝑎1
𝑞(𝛼)
𝛼 + 𝑥1
+⋯+ 𝑎𝑛
𝑞(𝛼)
𝛼 + 𝑥𝑛
) (2.31) 
1 = 𝐺(𝛼) + 𝑎1
𝑞(𝛼)
𝛼 + 𝑥1
+⋯+ 𝑎𝑛
𝑞(𝛼)
𝛼 + 𝑥𝑛
 (2.32) 
 Trong đó G là đa thức có tính chất G(0) = 0. Do đó, ta dễ dàng thấy 1 phải 
được suy ra từ: 
𝑎1
𝑞(𝛼)
𝛼 + 𝑥1
+⋯+ 𝑎𝑛
𝑞(𝛼)
𝛼 + 𝑥𝑛
 (2.33) 
Tuy nhiên, do q(α) và mỗi đa thức α + xi là nguyên tố cùng nhau với mọi i = 1, . . . , 
n, nên đẳng thức trên không thể đúng đối với mọi cách chọn 𝑎𝑖, hay nói cách khác f 
53 
là độc lập tuyến tính với (P, Q, R). Do vậy, từ (P, Q, R) không thể tính được f, hay kẻ 
tấn công không thể phân biệt được T trong bài toán GDDHE. 
Định lý 2.4: Hệ mã quảng bá đa kênh đạt an toàn CPA dưới bài toán GDDHE ở trên. 
Chứng minh: Giả sử 𝒜 là kẻ tấn công hệ mã và S là kẻ tấn công bài toán GDDHE ở 
trên. Chứng minh rằng nếu tồn tại kẻ tấn công 𝒜 tấn công thành công hệ mã với lợi 
thế nhiều, thì cũng sẽ tồn tại 𝒮 tấn công bài toán GDDHE ở trên với nhiều lợi thế. 
Khởi tạo: Đầu tiên 𝒮 nhận đầu vào là đầu vào của bài toán GDDHE ở trên, 𝒮 cần 
phân biệt giá trị T là: 
 𝑇 = 𝑒(𝑔0, ℎ0)
𝑘.𝛽𝑚.𝑓(𝛼) ∈ 𝔾𝑇 và một phần tử ngẫu nhiên 𝑇 = 𝑅 ∈ 𝔾𝑇. 
 Luận án sẽ chỉ ra rằng 𝒮 có thể mô phỏng 𝒜 và dùng kết quả của 𝒜 để phân 
biệt T. Cụ thể, 𝒮 sẽ nhận từ 𝒜 m∗ (m∗ ≤ m) tập chỉ số 𝑆1
∗,  , 𝑆𝑚
∗ và chỉ số i* để xác 
định tập 𝑆𝑖∗
∗ mà 𝒜 muốn tấn công. 
 Giả sử ta viết tập 𝑆𝑖∗
∗ dưới dạng tập các định danh: 
 𝑆𝑖∗
∗ = {𝐼𝐷1,𝑖∗ ,  , 𝐼𝐷𝑠∗,𝑖∗}, 𝑠
∗ ≤ 𝑛. Không mất tính tổng quát, 𝒮 đặt βm ở trong bài toán 
là 𝛽𝑖∗ trong tập 𝑆𝑖∗
∗ . Đối với các tập βi, i = 1,...,m∗ khác vẫn giữ nguyên. Trong trường 
hợp m∗= m, 𝒮 đặt 𝛽𝑖∗ ở trong bài toán là 𝛽𝑚∗ trong tập 𝑆𝑚
∗ . Các tham số khác như m, 
n, N được định nghĩa như ở trên. 
 Ký hiệu �̃� = ∑ |𝑆𝑖
∗|𝑚
∗
𝑖=1,𝑖≠𝑖∗ để tạo ra các tham số cho hệ thống 𝒮 ngầm đặt 𝑔 =
𝑔0
𝑓(𝛼)
 và nhận 𝑔𝛼 = 𝑔0
𝛼𝑓(𝛼)
 từ giả thuyết. Với ℎ0, ℎ0
𝛼 ,  , ℎ0
𝛼2𝑡+𝑛 trong tay từ giả thuyết, 
𝒮 tính: 
ℎ = ℎ0
∏ (𝛼+𝑥𝑖)∏ (𝛼+𝑥𝑖)
𝑡+𝑛
𝑖=𝑡+𝑠∗+1
𝑡
𝑖=𝑛+�̃�+1 
 và sau đó {ℎ𝛼
𝑖
}𝑖=1,,𝑁 
Lưu ý, trong quá trình băm, 𝒮 sẽ dùng xi, i = 1,.., n, để trả lời tất cả các yêu cầu truy 
vấn băm ℋ(𝐼𝐷𝑗,𝑖∗) trong đó 𝐼𝐷𝑗,𝑖∗ ∉ 𝑆𝑖∗
∗ (𝐼𝐷𝑗,𝑖∗trong kênh i∗ nhưng không thuộc 𝑆𝑖∗
∗ ). 
𝒮 cũng dùng xi , i = n + 1,..., n + �̃�, để trả lời tất cả các truy vấn băm ℋ(𝐼𝐷𝑗,𝑖) trong 
đó 𝐼𝐷𝑗,𝑖∗ ∈ {𝑆𝑖
∗}𝑖=1,,𝑚∗
𝑖≠𝑖∗
. 𝒮 cũng dùng xi, i = t + 1,.. , t + s∗ để trả lời tất cả các truy 
vấn băm ℋ(𝐼𝐷𝑗,𝑖∗) trong đó 𝐼𝐷𝑗,𝑖∗ ∈ 𝑆𝑖∗
∗ 
54 
Tiếp theo, để tính 𝑒(𝑔, ℎ)𝛽𝑖 , 𝑖 = 1, ,𝑚, 𝒮 tính: 
𝑒(𝑔, ℎ)𝛽𝑖 = 𝑒 (𝑔0ℎ0
𝛽𝑖.∏ (𝛼+𝑥𝑖)∏ (𝛼+𝑥𝑖)
𝑡+𝑛
𝑖=𝑡+𝑠∗+1
𝑡
𝑖=𝑛+�̃�+1 .𝑓(𝛼) ) (2.34) 
Lưu ý rằng, 𝒮 biết {ℎ0
𝛽𝑖,𝛼
𝑗
} 𝑖=1,,𝑚
𝑗=0,,2𝑡+𝑛
 từ giả thuyết. Với {ℎ0
𝛽𝑖,𝛼
𝑗
} 𝑖=1,,𝑚
𝑗=0,,2𝑡+𝑛
 đã biết trong 
tay, 𝒮 cũng có thể tính {ℎ0
𝛽𝑖,𝛼
𝑗
}𝑖=1,,𝑚
𝑗=0,,𝑁
 Cuối cùng, 𝒮 cung cấp khóa công khai cho 𝒜. 
Giai đoạn truy vấn 1: Trong giai đoạn này, 𝒮 cần trả lời hai loại truy vấn: 
1. Truy vấn băm. 
2. Truy vấn để biết khóa bí mật 𝐼𝐷𝑗,𝑖 trong đó 𝐼𝐷𝑗,𝑖 ∉ 𝑆𝑖∗
∗ 
Đối với truy vấn băm: 𝒜 có thể truy vấn trên bất kỳ định danh nào để biết được giá 
trị băm trên định danh đó. 𝒮 tạo ra một danh sách ℒ bao gồm: (𝐼𝐷𝑖,𝑗𝑥𝑢, 𝑠𝑘𝐼𝐷𝑖,𝑗) ∈
{0,1}∗, ℤ𝑝
∗ , 𝔾. Ban đầu ℒ bao gồm bộ ba (∗, ∗, ∗) hay (𝐼𝐷𝑖,𝑗 , 𝑥𝑢 ,∗), giá trị rỗng sẽ được 
ký hiệu bằng *. Cụ thể, nếu 𝐼𝐷𝑗,𝑖 ∉ 𝑆𝑖∗
∗ (𝐼𝐷𝑗,𝑖∗ trong kênh i∗ nhưng không trong 𝑆𝑖∗
∗ ), 
𝒮 dùng xu, u = 1,.., n. Nếu 𝐼𝐷𝑖,𝑗 ∈ {𝑆𝑖∗
∗ }𝑖=1,,𝑚∗
𝑖≠𝑖∗
 , 𝒮 dùng xu, u = n + 1,.., n + �̃�. Đối 
với 𝐼𝐷𝑗,𝑖∗ ∈ 𝑆𝑖∗
∗ , 𝒮 dùng xu, u = t + 1, . . . , t + s* 
 Với mỗi truy vấn băm tương ứng với 𝐼𝐷𝑗,𝑖, S đầu tiên kiểm tra xem 𝐼𝐷𝑗,𝑖 đã 
xuất hiện trong danh sách chưa? Nếu không, 𝒮 chọn xu, u = n + �̃�+ 1,.., t, giá trị chưa 
bao giờ xuất hiện trong L và bộ ba (𝐼𝐷𝑖,𝑗 , 𝑥𝑢,∗), trong L và trả về xu cho 𝒜. Ngược 
lại, 𝒮 đơn giản là tìm bộ ba (𝐼𝐷𝑖,𝑗 , 𝑥𝑢,∗), và trả về xu cho 𝒜. 
Đối với truy vấn yêu cầu biết khóa bí mật: 𝒜 đầu tiên gửi 𝐼𝐷𝑗,𝑖 ∉ 𝑆𝑖∗
∗ cho 𝒮, 𝒮 tạo 
ra khóa bí mật 𝑠𝑘𝐼𝐷𝑖,𝑗 như sau: 
1. Nếu 𝑠𝑘𝐼𝐷𝑖,𝑗 đã được truy vấn trước đây, 𝒮 tìm 𝑠𝑘𝐼𝐷𝑖,𝑗 từ ℒ và trả về 𝑠𝑘𝐼𝐷𝑖,𝑗 cho 𝒜. 
2. Nếu j = i* , có nghĩa là 𝐼𝐷𝑖,𝑗 ∉ 𝑆𝑖∗
∗ nhưng thuộc về kênh i*. 
 𝒮 sẽ dùng 𝑔0
𝛽𝑚𝑓(𝛼)
𝛼+𝑥𝑢 = 𝑔
𝛽𝑚
𝛼+𝑥𝑢, u = 1,..., n, từ giả thuyết như 𝑠𝑘𝐼𝐷𝑖,𝑗 để trả lời 𝒜 
(mỗi lần dùng một giá trị khác nhau), và sau đó thêm bộ ba (𝐼𝐷𝑖,𝑗, xu, 𝑠𝑘𝐼𝐷𝑖,𝑗) vào 
trong ℒ. 
55 
3. Ngược lại, 𝒮 kiểm tra xem 𝐼𝐷𝑖,𝑗 đã xuất hiện trong danh sách hay chưa? Nếu không 
𝒮 chọn xu, u = n + �̃�+ 1,..., t, giá trị chưa bao giờ xuất hiện trong ℒ, sau đó tính: 
𝑠𝑘𝐼𝐷𝑖,𝑗 = 𝑔0
𝛽𝑗.𝑓(𝛼)
𝛼+𝑥𝑢 = 𝑔
𝛽𝑗
𝛼+𝑥𝑢 
(2.35) 
Lưu ý rằng, 𝒮 có thể tính vì u = n + �̃�+ 1,..., t, do đó đa thức 
𝑓𝛼
𝛼+𝑥𝑢
 có bậc t−1, hơn 
nữa 𝒮 có {𝑔0
𝛽𝑗,𝛼
𝑖
}𝑖=0,,𝑡−1 trong tay từ giả thuyết. Tiếp theo, 𝒮 thêm bộ ba (𝐼𝐷𝑖,𝑗, xu, 
𝑠𝑘𝐼𝐷𝑖,𝑗) vào trong ℒ và trả về 𝑠𝑘𝐼𝐷𝑖,𝑗cho 𝒜. Trong trường hợp 𝐼𝐷𝑖,𝑗 đã xuất hiện trong 
danh sách, 𝒮 đơn giản là tìm xu tương ứng từ danh sách ℒ sau đó tính 𝑠𝑘𝐼𝐷𝑖,𝑗 như trên. 
Cuối cùng 𝒮 thêm bộ ba (𝐼𝐷𝑖,𝑗, xu, 𝑠𝑘𝐼𝐷𝑖,𝑗) vào trong ℒ và trả về 𝑠𝑘𝐼𝐷𝑖,𝑗cho 𝒜. 
Giai đoạn thách thức: 𝒮 tính: 
𝐶1 = 𝑔0
−𝑘.𝛼.𝑓(𝛼)
= 𝑔−𝛼.𝑘 
Và 
𝐶2 = ℎ0
𝑘.𝑞(𝛼)
 = ℎ0
𝑘.∏ (𝛼+𝑥𝑖)∏ (𝛼+𝑥𝑖)
𝑡
𝑖=𝑛+�̃�+1
𝑛+�̃�
𝑖=𝑛+1 .∏ (𝛼+𝑥𝑖)
𝑡+𝑠∗
𝑖=𝑡+1 ∏ (𝛼+𝑥𝑖)
𝑡+𝑛
𝑖=𝑡+𝑠∗+1 
(2.36) 
 = ℎ𝑘.∏ (𝛼+𝑥𝑖)
𝑛+�̃�
𝑖=𝑛+1 ∏ (𝛼+𝑥𝑖)
𝑡+𝑠∗
𝑖=𝑡+1 (2.37) 
Để tính các khóa phiên, 𝒮 biết {ℎ0
𝛽𝑖,𝛼
𝑗
} 𝑖=1,,𝑚
𝑗=0,,2𝑡+𝑛
 nên tính: 
𝐾𝑖
∗ = 𝑒(𝑔0ℎ0)
𝑘𝛽𝑖𝑓(𝛼)∏ 𝑥𝑖∏ 𝑥𝑖
𝑡+𝑛
𝑖=𝑡+𝑠∗+1
𝑡
𝑖=𝑛+�̃�+1 . 𝑒 (𝑔0
𝑘𝛼𝑓(𝛼)
, ℎ0
𝛽𝑖𝑝(𝛼)), 
𝑖 = 1, ,𝑚∗, 𝑖 ≠ 𝑖∗ 
(2.38) 
 Trong đó: 
𝑝(𝛼) = 
1
𝛼
( ∏ (𝛼 + 𝑥𝑖)
𝑡
𝑖=𝑛+�̃�+1
∏ (𝛼 + 𝑥𝑖) −
𝑡+𝑛
𝑖=𝑡+𝑠∗+1
∏ 𝑥𝑖
𝑡
𝑖=𝑛+�̃�+1
∏ 𝑥𝑖
𝑡+𝑛
𝑖=𝑡+𝑠∗+1
) (2.39) 
Tiếp theo 𝒮 tính: 
𝐾𝑖
∗ = 𝑇∏ 𝑥𝑖∏ 𝑥𝑖
𝑡+𝑛
𝑖=𝑡+𝑠∗+1
𝑡
𝑖=𝑛+�̃�+1 . 𝑒(𝑔0
𝑘𝛼𝑓(𝛼)
, ℎ0
𝛽𝑖∗𝑝(𝛼)) (2.40) 
 Lưu ý: Nếu 𝑇 = 𝑒(𝑔0, ℎ0)
𝑘𝛽𝑖∗𝑓(𝛼) thì 𝐾𝑖∗
∗ = 𝑒(𝑔, ℎ)𝑘𝛽𝑖∗. Nếu T là ngẫu nhiên, 
𝐾𝑖∗
∗ cũng là ngẫu nhiên. 
56 
Giai đoạn dự đoán: 
 𝒜 cho đầu ra dự đoán 𝑏′ cho b. Nếu 𝑏′ = 𝑏, 𝒮 cho đầu ra là bit 0 (tức là nếu 
𝑇 = 𝑒(𝑔0, ℎ0)
𝑘𝛽𝑖∗𝑓(𝛼)). Ngược lại, 𝒮 cho đầu ra là bit 1 (tức là, T là phần tử ngẫu 
nhiên trong 𝔾𝑇). Vì quá trình 𝒮 mô phỏng 𝒜 là hợp lệ nên ta suy ra rằng, lợi thế của 
𝒮 để phá bài toán GDDHE là AdvIND(𝒜)/2. Điều này dẫn đến một khả năng là nếu 
như tồn tại 𝒜 thì cũng sẽ tồn tại 𝒮, tức là nếu như bài toán GDDHE mà khó, có nghĩa 
là không tồn tại 𝒮 thì cũng sẽ không tồn tại 𝒜. 
2.3.4. Cài đặt và đánh giá hiệu quả 
Để cài đặt hệ mã, trong phần mã hóa chúng ta thấy rằng không dễ dàng để tính 
𝐶2 = ℎ
𝑘.∏ (𝛼+ℋ(𝐼𝐷𝑖𝑗))(𝑖,𝑗)∈𝑆 
từ khóa công khai. Thay vì đó ta áp dụng công thức sau: 
∏(𝑋 + 𝑎𝑖) = ∑( ∑ 𝑎𝑖1 , 𝑎𝑖2 𝑎𝑖𝑗
1≤𝑖1≤𝑖2<⋯<𝑖𝑗≤𝑚
)𝑋𝑚−𝑗
𝑚
𝑗=0
𝑚
𝑖=1
 (2.41) 
và các tham số của đa thức: 
𝑠𝑗 = ∑ 𝑎𝑖1 , 𝑎𝑖2 𝑎𝑖𝑗
1≤𝑖1≤𝑖2<⋯<𝑖𝑗≤𝑚
 (2.42) 
tất cả là đối xứng a1,.., am và được gọi là những đa thức đối xứng của giá trị ai. Tham 
số sj cho phép viết lại: 
𝐶2 = ℎ
𝑘∑ 𝑠𝑗.𝛼
𝑚−𝑗𝑚
𝑗=0 = (∏(ℎ𝛼
𝑚−𝑗
)
𝑚
𝑗=0
)
𝑘
 (2.43) 
Ta có thể tính C2 do tập {ℎ𝛼
𝑖
|𝑖 = 0, , 𝑛} có trong khóa công khai của hệ thống. 
Tương tự như vậy, đối với giải thuật giải mã, cũng dùng cách như trên để tính 𝐾′ do 
ℎ𝛽𝑖𝛼
𝑗
có trong khóa công khai. 
 Tham số sj ở trên có thể được tính nhanh bằng cách dùng giải thuật quy hoạch 
động như sau: Đặt sk,j là tổng của j tổ hợp của a1, a2, . . . , ak. Tức là: 
57 
𝑠𝑘,𝑗 = ∑ 𝑎𝑖1 , 𝑎𝑖2 𝑎𝑖𝑗
1≤𝑖1≤𝑖2<⋯<𝑖𝑗≤𝑘
 (2.44) 
Lưu ý: Tham số sj = sm,j . Tổng sk,j có thể được chia làm hai phần, phần thứ nhất chứa 
đựng ak và phần thứ hai không chứa ak. Chúng ta có: 
𝑠𝑘,𝑗 = ( ∑ 𝑎𝑖1 , 𝑎𝑖2 𝑎𝑖𝑗
1≤𝑖1≤𝑖2<⋯<𝑖𝑗≤𝑘−1
)
+ ( ∑ 𝑎𝑖1 , 𝑎𝑖2 𝑎𝑖𝑗−1
1≤𝑖1≤𝑖2<⋯<𝑖𝑗−1≤𝑘−1
) . 𝑎𝑘 
(2.45) 
Kéo theo mối liên hệ: 
𝑠𝑘,𝑗 = 𝑠𝑘−1,𝑗 + 𝑠𝑘−1,𝑗−1 . 𝑎𝑘 (3.46) 
Trong đó sk,0 = 1 đối với k ≥ 0 và s0,j = 0 đối với j > 1. Từ mối liên hệ này, bằng việc 
xây dựng bảng từ s0, 0 cho tới sm, m, có thể tính các tham số sj = sm,j với độ phức tạp là 
O(m2 ). 
Cài đặt MCBE đề xuất ở trên bằng ngôn ngữ C và dùng thư viện PBC [40]. Mã nguồn 
của chương trình cài đặt có ở địa chỉ https://github.com/tranvinhduc/MCBE . Cài đặt 
trên máy tính xách tay với bộ vi xử lý Intel Core i7-4600U @ 2.1 GHz. Đo