Luận án Các hệ mật dựa trên vành đa thức chẵn

k
f R hay 2 1
k
f . Điều này cho thấy 2 1
k
g f chính là phần tử nghịch đảo của 
f trong 
2k
R . 
 Tuy nhiên, cũng theo [17], trong 
2k
R ord( )f luôn là ước của 2k hay 
ord( ) 2 | [1, ]if i k . Do đó, ta có thể tính nghịch đảo của f bằng thuật toán sau 
hiệu quả hơn phép tính 2 1
k
g f . 
Thuật toán 2-1 g
2k
f I : Thuật toán tính nghịch đảo của đa thức 
VÀO: Đa thức 
2k
f I . 
RA: Đa thức 
2k
g I , 1g f . 
THUẬT TOÁN: 
 g f ; 
 2a f ; 
 for 1i to 1k { 
 if 1g f exit; 
 g g a ; 
 2a a ; 
 }. 
 Lấy ví dụ, trong 32I , để tính nghịch đảo của 
5 4 3f x x x , vì 
2ord( ) 2 4,f sử dụng thuật toán trên, ta có thể tính 3g f tại bước 2i , thay vì 
phải tính 7.g f 
 Thuật toán này có số bước lặp tối đa là 1k . Với các giá trị độ dài khóa 
1024n , ứng với 10k , số vòng lặp là không đáng kể. 
45 
2.5 VÀNH ĐA THỨC CHỈ CÓ HAI LỚP KỀ CYCLIC 2CR 
2.5.1 Các định nghĩa 
Định nghĩa 2-10 [18
2
[ ] / ( 1)
n
nx xR Z ]: Vành đa thức được gọi là vành đa thức 
( 1)nx chỉ có hai lớp kề cyclic nếu nhị thức có thể thừa số hóa thành dạng 
1 (1 )nx x T 
trong đó 
1
0
n
i
i
T x
  là một đa thức bất khả quy trong 2[ ]Z x . 
 Thuật toán để xác định 2Cn N (tập các số nguyên để nR là một vành đa thức 
chỉ có hai lớp kề cylic) được mô tả trong [14]. Điểm đặc biệt là các phần tử 2Cn N 
đều là các số nguyên tố. Một số phần tử 2 , 10000Cn N n được trình bày trong phụ 
lục 1. 
2.5.2 Tập các phần tử khả nghịch trên vành 2CR 
Định lý 2-4 2,n CR n N f f: Trong , mọi đa thức là khả nghịch khi và chỉ khi có 
2C
Ktrọng số lẻ và, hệ quả là , tỉ lệ giữa số phần tử khả nghịch trên tổng số đa thức 
2
,
C
Rtrong đạt cực đại. 
 Chứng minh: Theo [18], nếu 2Cn N thì n là một số nguyên tố lẻ và vì vậy 
( )w T luôn chẵn. 
Khi ( )w f lẻ thì gcd( , 1) gcd( ,( 1) ) 1
nf x f x T . Theo định lý Euclid, 
luôn tồn tại 
2
,
C
u v R sao cho 
( 1) 1nu f v x 
hay 1u f và f là khả nghịch. 
 Ngược lại nếu ( )w f chẵn, theo Bổ đề 2-5, f không khả nghịch. 
46 
 Ngoài ra, vì tất cả các phần tử có trọng số lẻ trong vành đều khả nghịch mà số 
các phần tử này chiếm một nửa tổng số đa thức trong vành nên rõ ràng số tỉ lệ 2CK 
đạt cực đại là 1/2. Vậy ta có điều phải chứng minh. 
 Theo [18], 12 1nm là cấp cực đại của các đa thức nf R và 1
mf hay 
1mu f là nghịch đảo của f trong 2|n CR n N . Ví dụ, trong 5R , để tìm nghịch đảo 
của 4 3 1f x x , do 5 1max(ord( )) 2 1 15f , ta có thể tính 
15 1 4 3u f x x x . 
 Bên cạnh đó, trong 2CR , với mỗi một đa thức f có trọng số Hamming lẻ thì 
luôn tồn tại một đa thức 
0n
g e f có trọng số Hamming chẵn. Mặt khác, theo Định 
lý 2-2, g là nghịch đảo mở rộng của f . Do đó, tập 2|n CE n N sẽ bao gồm tất cả 
các đa thức có trọng số Hamming chẵn và 12 1n
n
E (trừ đa thức tầm thường 
0g ). Ví dụ, trong 3R , có 
22 4 đa thức khả nghịch 2 2{1, , ,1 }x x x x và tương 
ứng 22 1 3 đa thức khả nghịch mở rộng 
2 2{ ,1 ,1 }x x x x , trừ đa thức 0 . 
 Định lý này chỉ ra rằng 
2C
R là một vành đặc biệt có một tập các phần tử khả 
nghịch rất lớn và rất dễ xác định. Điều này rất thuận lợi để xây dựng các hệ mật có 
khóa là các phần tử khả nghịch trên 
2C
R vì thuật toán tạo khóa rất đơn giản và không 
gian khóa đủ lớn để chống lại các tấn công vét cạn khóa. 
 Định lý này sẽ được ứng dụng để xây dựng hệ mật E-RISKE (mục 4.3). 
2.5.3 So sánh vành 2CR với vành 2kR 
 Điểm tương đồng của hai lớp vành này là có tỉ lệ số phần tử khả nghịch trên 
tổng số đa thức trong vành là cao nhất và là 1/2. Và có thể thấy một đa thức f có 
khả nghịch trong một vành 2CR nào đó thì cũng sẽ khả nghịch trong một vành 2kR 
nào đó miễn là f cũng thuộc vành đó và ngược lại. 
 Ví dụ, 3 2 1f x x khả nghịch trong 5R với nghịch đảo 
4 3
5
g x x x 
cũng khả nghịch trong 16R với nghịch đảo 
47 
15 13 10 9 8 6 3 2
16
g x x x x x x x x x . 
 Không những thế, một đặc điểm quan trọng nữa là bậc hữu hạn của hai lớp 
vành này luôn nguyên tố cùng nhau. Đặc điểm này sẽ được khai thác để xây dựng hệ 
mật DTRU (mục 4.2). 
2.6 KẾT LUẬN CHƯƠNG 
 Kết quả nổi bật nhất trong chương này là nghiên cứu sinh đã chứng minh hai 
loại vành đa thức đặc biệt (
2k
R ,
2C
R ) có tỉ lệ giữa số phần tử khả nghịch trên tổng số 
đa thức của vành là cực đại (Định lý 2-3, Định lý 2-4) và đã đề xuất được một thuật 
toán hiệu quả để xác định nghịch đảo của các phần tử khả nghịch trên vành 
2k
R (Thuật 
toán 2-1). Các kết quả này là cơ sở để đề xuất các hệ mật RISKE (mục 3.2), IPKE 
(mục 3.4) và DTRU (4.2). 
 Một kết quả đáng chú ý khác của nghiên cứu sinh là chỉ ra trong các vành đa 
thức nR với n lẻ còn tồn tại một lớp phần tử đặc biệt, các phần tử khả nghịch mở 
rộng có đặc tính tương đồng với các khả nghịch truyền thống (Định nghĩa 2-5). Các 
phần tử này cũng có thể được sử dụng làm khóa trong các hệ mật (Định lý 2-2) tương 
tự như các phần tử khả nghịch truyền thống. Kết quả này cho phép linh hoạt trong 
lựa chọn vành đa thức nền tảng để xây dựng các hệ mật và được cụ thể hóa bằng một 
hệ mật E-RISKE (mục 4.4) hoạt động cả trên 
2C
R , một cải tiến của hệ mật RISKE 
vốn chỉ hoạt động trên 
2k
R . 
 Ngoài ra, hai công thức tính căn bậc hai chính và phần tử liên hợp của một 
thặng dư bậc hai trong vành 
2n
R được nghiên cứu sinh xây dựng (Bổ đề 2-9 và Bổ đề 
2-10) là nền tảng quan trọng để đề xuất hệ mật lai ghép QRHE trong mục 3.3. 
48 
CHƯƠNG 3. CÁC HỆ MẬT DỰA TRÊN VÀNH ĐA 
THỨC CHẴN 
3.1 MỞ ĐẦU CHƯƠNG 
 Trong chương này, luận án đề xuất ba hệ mật mới dựa trên vành đa thức chẵn 
2n
R bao gồm RISKE, QRHE và IPKE tương ứng với ba công trình [C2], [J1] và [J3] 
của nghiên cứu sinh. Trong đó: RISKE, một hệ mật khóa bí mật có độ an toàn IND-
CPA, được xây dựng dựa trên các phần tử khả nghịch trong vành đa thức chẵn tuyệt 
đối 
2k
R sẽ được trình bày trong mục 3.2; Hệ mật lai ghép QRHE hoạt động dựa trên 
đặc tính của các thặng dư bậc hai và các phần tử liên hợp của chúng trong vành chẵn 
2n
R sẽ được mô tả trong mục 3.3; Cuối cùng, hệ mật khóa công khai IPKE các phần 
tử khả nghịch trong vành 
2k
R làm cửa sập sẽ được đề xuất trong mục 3.4. 
 Ngoài các tấn công vét cạn để đánh giá độ an toàn bản rõ và độ an toàn khóa, 
tấn công CPA sẽ được sử dụng trong thí nghiệm đánh giá độ an toàn không thể phân 
biệt để đánh giá độ an toàn ngữ nghĩa của các hệ mật được đề xuất. 
 Trong các thuật toán tạo khóa, mã hóa và giải mã của các hệ mật, ta quy ước 
Alice là bên mã hóa và gửi bản mã còn Bob là bên nhận bản mã và giải mã. 
3.2 HỆ MẬT KHÓA BÍ MẬT RISKE 
3.2.1 Giới thiệu 
Hệ mật OTP (One-Time Pad) được Vernam đề xuất vào những năm 1920 và 
được Shannon chứng minh là có độ an toàn hoàn hảo vào năm 1949 [89]. OTP hoạt 
động trên trường (2) với các phép mã hóa và giải mã đều là các phép tính XOR 
rất đơn giản với độ phức tạp tính toán là ( )O n trong đó n là độ dài khóa. Ngoài ra, 
OTP hiện vẫn là hệ mật an toàn và vẫn được sử dụng trong các lĩnh vực rất đặc thù 
đòi hỏi độ an toàn rất cao như quốc phòng, an ninh và ngoại giao. Tuy nhiên, nhược 
điểm lớn nhất của OTP là khóa bí mật phải được chọn ngẫu nhiên và chỉ được sử 
dụng duy nhất một lần để tránh tấn công KPA. Ngoài ra, khóa bí mật của OTP cần có 
độ dài ít nhất bằng độ dài bản rõ dẫn đến hiệu quả mã hóa không cao. Những nhược 
49 
điểm này khiến cho OTP không phù hợp với các ứng dụng trong thương mại. Trên 
thực tế, các nghiên cứu mật mã khóa bí mật cũng đều đi theo hướng xây dựng các hệ 
mật có khả năng mã hóa những bản tin dài với khóa ngắn và có thể tái sử dụng mà 
vẫn đảm bảo độ an toàn ngữ nghĩa thay vì xây dựng các hệ mật có độ an toàn hoàn 
hảo [89]. 
Vấn đề đặt ra là có thể sử dụng vành đa thức chẵn 
2n
R để xây dựng một hệ 
mật có độ phức tạp mã hóa và giải mã tương đương với OTP nhưng có khóa bí mật 
ngắn hơn độ dài của bản tin mà vẫn đảm bảo hệ mật có độ an toàn chứng minh được 
hay không. 
Quan sát kỹ ta thấy, thuật toán mã hóa và giải mã trong OTP thực ra là một 
phép cộng trong vành đa thức 
n
R , trong đó độ dài bản rõ, bản mã và khóa đều là n 
bit. Ý tưởng ở đây nếu thay thế phép cộng đa thức trong OTP bằng một phép nhân 
trong vành đa thức thì ta có thể sử dụng các phần tử khả nghịch trong 
n
R để làm khóa 
cho một hệ mật khóa bí mật và nếu tập này đủ lớn thì hệ mật sẽ đạt mức an toàn ngữ 
nghĩa nào đó. Ngoài ra, nếu chọn khóa ngắn hơn bản rõ mà vẫn đảm bảo mức an toàn 
ngữ nghĩa thì hệ mật được đề xuất sẽ hiệu quả hơn OTP. 
Với Định lý 2-3, ta thấy rằng, tất cả các đa thức có trọng số Hamming lẻ trong 
lớp vành đa thức chẵn tuyệt đối 
2k
R là khả nghịch. Như vậy, tập này đủ lớn để có thể 
sử dụng làm khóa trong hệ mật nêu trên. Dựa trên các phần tử khả nghịch trên 
2k
R , 
nghiên cứu sinh sẽ đề xuất một hệ mật khóa bí mật, có tên là RISKE (Random 
Invertible Secret-Key Encryption scheme) có độ phức tạp tính toán 2( )O n với độ dài 
khóa không nhất thiết phải bằng độ dài bản tin mà vẫn có độ an toàn IND-CPA. 
3.2.2 Cấu trúc đại số nền tảng của RISKE 
Cấu trúc đại số nền tảng của RIKSE so sánh với OTP với cùng kích thước 
khóa 
*N được tóm tắt trong Bảng 3-1. Các giá trị kích thước được tính theo đơn 
vị bit. 
50 
Để xây dựng hệ mật RISKE, Alice và Bob thống nhất một số nguyên dương 
k để xác định vành đa thức , 2k
n
R n và độ dài bản rõ cùng một số nguyên 2kN 
để xác định độ dài khóa bí mật. Việc lựa chọn độ dài khóa N nhỏ hơn độ dài của bản 
rõ n nhằm đảm bảo hiệu quả mã hóa của RISKE so với OTP, trong đó khóa và bản 
rõ có cùng độ dài N . 
Bảng 3-1: Cấu trúc đại số nền tảng của hệ mật RISKE và OTP 
Các tham số RISKE OTP 
Vành đa thức *
2
[ ] / ( 1) | 2 ,n k
n
R Z x x n k (2) 
Kích thước khóa *,N n N N 
Không gian khóa { | 0 deg 1}
n
s I s N { {0,1} }Ns 
Không gian bản rõ { | deg ( 1)}
n
m R m n 
Kích thước bản rõ 1n N 
Không gian bản mã 
n
R 
Kích thước bản mã n N 
3.2.3 Thủ tục tạo khóa 
 Với 0 }{ | deg 1
n
I s Ns , Alice và Bob chia sẻ một đa thức khả 
nghịch ngẫu nhiên s làm khóa bí mật chung. Do deg 1s N ta có thể biểu diễn 
s bằng N bit. Điều kiện deg 0s để đảm bảo ta không thể dùng 1s làm khóa bí 
mật trong RISKE. Hệ quả là, 
12 1N . (3.1) 
3.2.4 Thủ tục mã hóa 
 Mỗi phiên mã hóa ( 1)n bit bản rõ m nào đó, Alice sử dụng thủ tục tạo khóa 
trên để tạo và chia sẻ với Bob một khóa ngẫu nhiên mới s 
 Tiếp theo, Alice tính n bit 
51 
 1( ) 1 mod 2. nM w m x m (3.2) 
sau đó tính n bit bản mã 
 .c M s (3.3) 
và gửi c đến Bob. 
 Theo Bổ đề 2-6, ( )w M luôn lẻ do đó, theo Định lý 2-3, cả M và c đều có 
trọng số lẻ và khả nghịch trong 
2k
R . 
3.2.5 Thủ tục giải mã 
 Để giải mã n bit bản mã c , dựa vào khóa phiên s , đầu tiên Bob tính n bit 
 1M c s (3.4) 
trong đó 1s là nghịch đảo của s trong 
2k
R tính bằng Thuật toán 2-1, từ đó sử dụng 
công thức (2.15) khôi phục 1n bit bản rõ 
 1
1
. n
n
m M x M 
 (3.5) 
với 
1n
M
 là hệ số ứng với đơn thức 1nx trong biểu diễn đa thức của M . 
3.2.6 Ví dụ minh họa 
 Alice và Bob lựa chọn 32 8n và 5N để xây dựng hệ mật RIKSE. 
a) Tạo khóa 
 Alice và Bob chia sẻ 5 bit khóa bí mật (00111)s dạng nhị phân hay 
2 1s x x dạng đa thức. Vì ( ) 3w s nên nghịch đảo của s trong 8R , tính bởi 
Thuật toán 2-1, là 7 51 4 2x x xs x x . 
b) Mã hóa 
 Để mã hóa 7 bit bản rõ (1010011)m dưới dạng nhị phân hoặc 
6 4 1m x x x dạng đa thức, Alice đầu tiên, bằng công thức (3.2), tính 8 bit 
7 6 4 1M x x x x sau đó, bằng công thức (3.3), tính và gửi 8 bit bản mã 
5 4 3 1x x xM xc s 
52 
dạng đa thức hoặc (00111011)c dạng nhị phân tới Bob. 
c) Giải mã 
 Để giải mã 8 bit bản mã (00111011)c , bằng công thức (3.4), đầu tiên Bob 
tính 8 bit 
1 7 6 4 1M s c x x x x . 
Sau đó, bằng công thức (3.5), với 7 1M , Bob khôi phục 7 bit bản rõ 
7 7 6 5 6 4( 1) 1m x x x x x x x x . 
3.2.7 Phân tích độ an toàn lý thuyết của RISKE 
 Để đánh giá độ an toàn cho hệ mật RISKE, trước hết, ta sẽ chứng minh bổ đề 
sau đây. 
Bổ đề 3-1 1 1( ) (2 1)nf n n: là hàm không đáng kể với biến . 
Chứng minh: 
Theo [54], 2
n 
 là một hàm không đáng kể và vì tổng của hai hàm không đáng 
kể cũng là một hàm không đáng kể nên ta có ( 2) 22 2 4.2n n n là một hàm không 
đáng kể. Theo Định nghĩa 1-4, với mọi hằng số c luôn tồn tại 
0
n sao cho 
0
n n thì 
( 2)2 n cn . 
Vì 1 1 ( 2) 22 2 2.2n n n và 
22 1n khi 2n , ta luôn có 2 1 22 2 2 1n n n 
hay 1 1 ( 2)(2 1) 2n n với 2n . Do đó, với mọi hằng số c luôn tồn tại 
0 0
max{ ,2}N n để sao cho 
0
n N thì 
( 1) 1 ( 2)(2 1) 2n n cn . 
Hệ quả là, 1 1( ) (2 1)nf n là một hàm không đáng kể với biến n và ta có điều phải 
chứng minh. 
a) Với các tấn công vét cạn 
Kẻ tấn công có thể sử dụng phương pháp vét cạn để tìm khóa bí mật s . 
Tuy nhiên, với độ an toàn khóa 2 1N xác suất để đoán đúng khóa là
53 
1/ (2 1)N . Đây một hàm không đáng kể của N nên có thể coi RISKE là an toàn đối 
với loại tấn công này. 
Về lý thuyết, có thể sử dụng tấn công vét cạn để tìm bản rõ nhưng điều này 
là không thực tế vì trong RIKSE độ an toàn bản rõ là 12n còn lớn hơn cả độ an 
toàn khóa. 
b) Với các tấn công EAV 
Định lý 3-1: RISKE là hệ mật có độ an toàn IND-EAV. 
 Chứng minh: Nhắc lại rằng, với *c M s ta có thể tính 1M s c với 1s 
là nghịch đảo của s trong 
2k
R . Mặc dù kẻ tấn công không biết khóa bí mật, 
vẫn có thể thử từng giá trị 's để tính 1' ( ')M s c cho đến khi 'M M . Bằng 
cách này, xác suất để giải mã thành công mà không cần biết khóa bí mật là 
1 1 1Pr[ ' ] Pr[( ') ] Pr[( ') ]M M s c M s M c 
với 1c là nghịch đảo của c trong LR . 
 Vì 's được lựa chọn ngẫu nhiên trong trong khi M và 1c là cố định nên 
1 1 1Pr[ ' ] Pr[( ') ]M M s M c . 
 Trong tấn công EAV, với bản mã thách thức bc M s nhận được từ thủ tục 
mã hóa, có thể tính b b bằng cách đoán đơn giản với xác suất 1/2 hoặc thử lần 
lượt tất cả các khóa 's để tính 1' ( ')M s c cho đến khi 0'M M hoặc 
1
'M M . Giả sử rằng phải thử ( )p N lần để có 0'M M hoặc 1'M M , trong đó 
( )p N là một đa thức của N (để chắc chắn rằng tấn công này có thể thực hiện trong 
thời gian đa thức), ta có 
 eav, 0 1
1
1
Pr[SecK ( ) 1] ( ). Pr[ ' ].Pr[ 0] Pr[ ' ].Pr[ 1]
2
1 1 1 1 ( ) 1 ( )
( ). .
2 2 2 2 2 2 1n
N p N M M b M M b
p N p N
p N

54 
 Theo Bổ đề 3-1, vì ( 1) 1(2 1)N là một hàm không đáng kể của biến N đồng 
thời do ( )p N là một đa thức nên, theo Bổ đề 1-2, 
( 1)
( )
2 1N
p N
cũng là hàm không đáng kể của N . Vì vậy, theo Định nghĩa 1-6, RISKE có độ an 
toàn IND-EAV và ta có điều phải chứng minh. 
c) Với các tấn công CPA 
Định lý 3-2: RISKE là hệ mật có độ an toàn IND-CPA. 
 Chứng minh: Nhắc lại rằng, với bản mã thu được {0,1* },
b
c M s b . Nếu 
' '
b
c M s với 's thì xác suất để 'c c là 
1 1 1Pr[ ' ] Pr[ ' ] Pr[ ' ]
b b b
c c M c M c s M c 
với 1
b
M là nghịch đảo của 
b
M trong 
2k
R . 
 Do 's được bộ mã hóa chọn ngẫu nhiên trong tại mỗi phiên trong khi 1
b
M 
và c không đổi nên 
1Pr[ '] Pr ]
1
[ '
b
c c s M c 
 Quay trở lại thí nghiệm cpa
,
SecK ( )N

, với bản mã thách thức *
b
c M s , 
có thể đoán đúng b b bằng một trong hai cách sau: 
1. Sử dụng thuật toán tương tự để đoán đúng b như trong thí nghiệm 
eav
,
SecK ( )N
 ; 
2. Chọn ngẫu nhiên ' {0,1}b và tiếp tục truy vấn bộ mã hóa ( )q N lần với đầu 
vào 'bM và nhận về bản mã tương ứng 'c cho đến khi 'c c . Ở đây, ( )q N là 
một đa thức của N để đảm bảo chắc chắn tấn công này có thể thực thi trong 
thời gian đa thức. 
Do đó, ta có 
55 
cpa eav
, ,
eav
,
1
Pr[SecK ( ) 1] Pr[SecK ( ) 1] ( ).Pr[ ' ]
1
 = Pr[SecK ( ) 1] ( ).
1 ( ) ( ) 1 ( ) ( )
.
2 2 2 1N
N N q N c c
N q N
p N q N p N q N
 

 Theo Bổ đề 3-1, vì ( 1) 1(2 1)N là một hàm không đáng kể của biến N đồng 
thời do ( ) ( ) ( )g N p N q N cũng là một đa thức nên, theo Bổ đề 1-2, 
( 1)
( )
2 1N
g N
là hàm không đáng kể của N . Hệ quả là, theo Định nghĩa 1-7, RISKE có độ an toàn 
IND-CPA và ta có điều phải chứng minh. 
3.2.8 Phân tích hiệu năng lý thuyết của RISKE 
 Ưu điểm quan trọng của RISKE là độ phức tạp tính toán thấp, cả thuật toán 
mã hóa và giải mã chỉ sử dụng một phép cộng và nhân đa thức trong vành đa thức 
chẵn tuyệt đối 
2k
R với độ phức tạp tính toán 
2( )n . So với hệ mật OTP, khóa bí mật 
s trong RISKE có độ dài N nhỏ hơn độ dài n của bản rõ. 
 Tương tự OTP, nhược điểm của RISKE là phải thay đổi khóa ngẫu nhiên mới 
s theo từng phiên. Vì lý do này, RISKE nên được sử dụng kết hợp với một hệ 
mật khóa công khai nào đó để xây dựng một hệ mật lai ghép theo mô hình 
KEM/DEM. Nếu hệ mật khóa công khai được chọn có độ an toàn IND-CPA thì hệ 
mật lai ghép cũng sẽ có độ an toàn IND-CPA [28]. Ngoài ra, nếu hệ mật khóa công 
khai được chọn có hệ số mở rộng bản tin lớn, ta có thể điều chỉnh N và n để giảm 
giá trị này. 
3.2.9 Lựa chọn tham số 
 Vì RISKE có độ an toàn IND-CPA, xác suất để tấn công được RIKSE là 
không đáng kể. Tuy nhiên, để ngăn chặn các tấn công vét cạn, giá trị N cần đủ lớn. 
Giá trị khuyến nghị cho các ứng dụng thực tế hiện nay là 1024N [64] và do đó 
56 
10k . Trong trường hợp này, số khóa cần vét cạn ít nhất sẽ là 1 20132 2N . Đối với 
các ứng dụng đòi hỏi độ an toàn cao, giá trị khuyến nghị là 4096N . 
 Ngoài ra, do n càng lớn hơn so với N thì hiệu quả mã hóa của RISKE càng 
cao. Điều này đặc biệt hữu ích để cải thiện hệ số mở rộng bản tin của các hệ mật khóa 
công khai trong sơ đồ lai ghép với RISKE. Mặc dù vậy, giá trị này cần phải được lựa 
chọn phù hợp cho từng ứng dụng cụ thể. 
3.2.10 So sánh RISKE với OTP 
Các so sánh về độ an toàn và hiệu năng của RIKSE với OTP được tóm tắt 
trong Bảng 3-2. Với cùng kích thước bản rõ là n , khóa bí mật s của RISKE có kích 
thước nhỏ hơn. Ngoài ra, khác với OTP, khóa bí mật s trong RISKE có thể sử dụng 
lại miễn là đảm bảo phân bố đều trong không gian khóa. 
Tuy vậy, để có thể sử dụng các khóa ngắn hơn bản rõ, thuật toán mã hóa và 
giải mã trong RISKE phải sử dụng phép nhân đa thức với độ phức tạp 2( )O n . Đây 
cũng là một nhược điểm của RISKE so với OTP nhưng có thể chấp nhận được vì các 
phép nhân đa thức trong vành rất dễ thực hiện bằng cả phần cứng lẫn phần mềm. 
Bảng 3-2: So sánh hiệu năng và độ an toàn của RISKE và OTP 
Các tham số RISKE OTP 
Kích thước bản rõ 1n n 
Kích thước bản mã n n 
Kích thước khóa N n n 
Độ phức tạp mã hóa 2( )O n ( )O n 
Độ phức tạp giải mã 2( )O n ( )O n 
Độ an toàn IND-CPA Độ an toàn hoàn hảo 
57 
3.2.11 Kết luận về hệ mật RISKE 
Có thể coi RISKE là một biến thể của OTP trên vành đa thức 
2k
R với một số 
ưu điểm về sự linh hoạt trong lựa chọn và quản lý khóa bí mật. Tuy nhiên, để đưa vào 
sử dụng trên thực tế, việc lựa chọn một hệ mật khóa công khai phù hợp để chia sẻ 
khóa phiên của RISKE là một vấn đề mở. Một kết quả của hướng nghiên cứu này sẽ 
được trình bày trong mục 4.4. 
 Bên cạnh đó, do RISKE hoạt động dựa trên tập các phần tử khả nghịch nên 
tìm ra các lớp con của 
n
R khác có hệ số 
n
K đạt cực đại hoặc gần cực đại để lựa chọn 
linh hoạt cấu trúc đại số nền tảng của RISKE cũng là một hướng nghiên cứu đáng 
quan tâm. 
3.3 HỆ MẬT LAI GHÉP QRHE 
3.3.1 Giới thiệu 
Như đã đánh giá, mặc dù có độ an toàn IND-CPA, hệ mật khóa bí mật RISKE 
vẫn có một nhược điểm là phải sử dụng khóa phiên (session-key) giống như hệ mật 
OTP. Để phù hợp với các ứng dụng thực tế, RISKE cần phải được sử dụng kết hợp 
với một hệ mật khóa công khai phù hợp và thường là theo mô hình KEM/DEM như 
đã giới thiệu ở mục 1.2.3. Bên cạnh đó, xét về hiệu năng, phép mã hóa và giải mã của 
RISKE vẫn là phép nhân đa thức có độ phức tạp 2( )O n . 
Vấn đề đặt ra là có thể xây dựng một hệ mật lai ghép trong đó các thuật toán 
mã hóa và giải mã đơn giản hơn, ví dụ như sử dụng phép cộng trong vành đa thức với 
độ phức tạp ( )O n hay không. Ngoài ra, làm thế nào để có thể cải tiến thủ tục tạo khóa 
của RISKE để giảm độ phức tạp khi sử dụng khóa phiên ngẫu nhiên. 
Như đã phân tích trong mục 2.3, mỗi trong tổng số 22 n đa thức 2nm R đều là 
một phần tử liên hợp với thặng dư bậc hai 2f m . Điều này có nghĩa là mọi đa thức, 
tương ứng với mọi bản