Tính an toàn ind-cpa của phương pháp mã hóa có thể chối từ dựa trên giao thức ba bước shamir

ẫu nhiên do A tạo ra 
 phần là CC'",. 
(theo giả thiết 1), dựa vào hệ phương trình (1), A tính bản ii
mã CCC* (,): *' *'' 
 1 1 1 Ta có: Tại Bước 1 của quá trình mã hóa theo giao thức 
 *' *" *
 СС11 1 mod p ba bước Shamir: 
 *' *" eA
 С11 ZС Mpmod Để chứng minh, trong thủ tục tấn công bản rõ lựa chọn, 
 - Đầu vào bước 3 mã hóa của giao thức EncPH_F lúc sau khi nhận được bản mã thách thức C1 tương ứng với 
 ' '' * '
này là CCC2 (,) 2 2 và 3 , với C2 là bản mã A nhận bản rõ mb . Kẻ tấn công chỉ có thể đoán đúng bb 
được từ B khi thực hiện giao thức DenEncPH lúc trước, bằng một trong hai cách sau: 
 * 1. Đoán ngẫu nhiên với xác suất bằng 1/2. 
 3 là giá trị ngẫu nhiên do A tạo ra (theo giả thiết 1), A 
 '
tính giá trị trung gian 2. Chọn ngẫu nhiên b {0,1} và truy vấn bộ mã hóa 
 eB (EncPH_F hoặc DenEncPH) với pn() lần, sử dụng đầu 
S2 S 1mod p С 2 ZС 2 mod p , tiếp đó dựa vào hệ 
 * *' *'' vào là mb và các khóa bí mật ngẫu nhiên để có bản mã 
phương trình (3), A tính bản mã CCC3 (,) 3 3 : 
 * *
 *' *" * C1 cho đến khi CC11 . Ở đây là một đa thức của 
 СС33 3 mod p
 n để đảm bảo chắc chắn tấn công này có thể thực thi 
 С*' ZС *" SpdA mod
 332 trong thời gian đa thức. 
 Như vậy các bản mã do A trình ra cho đối phương sẽ là Khi đó xác suất để đoán thành công là: 
 **
 CCC1 , 2 , 3 khác với các bản mã đang có trong tay của 1
 Pr[SecKCPA ( n ) 1] p ( n ).Pr[ C* C ] (11) 
 E. 2 1 1
đối phương là CCC1 , 2 , 3 . Điều này được lý giải hoàn 
 do bản mã tại mỗi bước gồm hai thành phần nên, công 
toàn hợp lý bằng giả thiết 1, do các giá trị ngẫu nhiên 
 thức (11) tương đương với hai công thức: 
 i (i 1,2,3) thêm vào quá trình mã hóa ba bước của 
 CPA 1 *' '
giao thức mã hóa xác suất EncPH_F và không lưu nhớ Pr[SecKE. ( n ) 1] p ( n ).Pr[ C 1 C 1 ] (11a) 
 2
trong máy tính, nên mỗi lần thực hiện lại quá trình mã hóa 
 1
với cùng một bản rõ , các bản mã tạo ra sẽ khác nhau. CPA *" "
 Pr[SecKE. ( n ) 1] p ( n ).Pr[ C 1 C 1 ] (11b) 
 Ta có điều phải chứng minh (CM 3-2). 2
 CM 3-3. Từ chứng minh (CM 3-1) kết hợp đồng thời * Khi truy vấn bộ mã hóa EncPH_F: 
với (CM 3-2), có điều phải chứng minh (CM 3-3) Với mb ( M b , bi ); b {0,1}, Ta có, dựa vào công 
 Kết hợp các chứng minh (CM 3-1), (CM 3-2), (CM 3- thức tính nghiệm của hệ phương trình (1): 
3) ta có mệnh đề 3 được chứng minh. *''
 Pr[C11 =C ]=
 6.3 Tính an toàn IND-CPA 
 =Pr[(U Z S )( Z 1) 1' mod p C ]
 Mệnh đề 4 Với cùng một thông điệp giả mạo và 1EncPH _ F 1 EncPH _ F 1
 eA '
cùng một khóa giả mạo KAAABBB ( e , d ), K ( e , d ). Với =Pr[( bbZ M ) mod p C1 (Z-1) mod p ] 
khóa thật bí mật QQ ( ,  ), (  ,  ) cùng các eA '
 AAABBB =Pr[Mbb mod p ( Z C1 (Z-1)) mod p ]
 '
giá trị ngẫu nhiên i trong giao thức EncPH_F được =Pr[e =log ( ZC (Z-1))]
 A Mb b 1
chọn ngẫu nhiên và có phân phối xác suất đều trong p , 
 do eA được bộ mã hóa chọn ngẫu nhiên trong p , và
thì khi thực hiện mã hóa truyền tin thông điệp bí mật T , '
 MZCbb,1 ,, không đổi nên: 
các bản mã (,,)CCC1 2 3 tạo ra từ giao thức EncPH_F 
 Pr[e =log (( modp ) Z C ' )] Pr[e ]
thỏa mãn tính chất không phân biệt tính toán với các bản A Mb b1 A
mã tạo ra từ giao thức DenEncPH. 11 
 Như vậy ta phải đi chứng minh: khi kẻ tấn công  có p 1 (2n 1  ) 1
các bản mã trong tay, xác suất để các bản mã 11 1
 Do nn 11 , theo định nghĩa (2) thì n 1 
này được tạo ra từ việc mã hóa (,)M i bằng giao thức (2  ) 1 2 2
EncPH_F hoặc được tạo ra từ việc mã hóa (,)MT bằng là một hàm không đáng kể theo biến , nên 
 Nguyễn Đức Tâm 
 1 Pr[C*" =C " ]=
 cũng là hàm không đáng kể theo biến n. 11
 (2n 1  ) 1 2 1 "
 =Pr[(S1DenEncPH U 1 DenEncPH )( Z Z ) mod p C 1 ]
 pn() eAA "2
Do pn() là một đa thức nên: cũng là một =Pr[(M Tb ) mod p C1 ( Z Z ) mod p ]
 (2n 1  ) 1
  AAe "2 
 =Pr[Tb mod p ( M C1 ( Z Z )) mod p ]
hàm không đáng kể của n, thay vào biểu thức (11a) ta có 
 =Pr[ log (MCZZeA "2 ( ))]
 *' ' ATb 1
điều phải chứng minh (C11 ,C ) thỏa mãn IND-CPA. 
 11
 Lập luận hoàn toàn tương tự cho biểu thức: 
 =Pr[ A ]= n 1
 *" " p 1 21 
 Pr[C11 =C ]
 1"
 =Pr[(S1EncPH _ F U 1 EncPH _ F )( Z 1) mod p C 1 ] Như đã chứng minh, do là hàm không 
 =Pr[(MeA ( mod p ))( Z 1) 1" mod p C ]
 bb 1 đáng kể theo biến do là một đa thức nên: 
 eA "
 =Pr[(Mbb ( mod p )) mod p C1 ( Z 1)mod p ]
 eA " cũng là một hàm không đáng kể của 
 =Pr[Mbb mod p (C1 ( Z 1) ) mod p ]
 =Pr[e =log (C" (Z 1) )]
 A Mb 1 b thay vào biểu thức (11b), ta có điều phải chứng minh 
 11 thỏa mãn IND-CPA. 
 Pr[e ] 
 A p 1 21n 1  Như vậy ta có điều phải chứng minh về tính không 
 phân biệt tính toán giữa bản mã tạo ra ở Bước 1 của giao 
 Như đã chứng minh, do là hàm không thức mã hóa xác suất EncPH_F và bản mã tạo ra ở Bước 
 1 của giao thức mã hóa có thể chối từ DenEncPH. 
đáng kể theo biến do là một đa thức nên: Trong quá trình mã hóa ba bước, do định dạng hệ 
 phương trình đồng dư tuyến tính ở Bước 2 và Bước 3 
 cũng là một hàm không đáng kể của hoàn toàn tương tự như Bước 1, với cách lập luận tương 
 tự như trên để chứng minh IND-CPA cho các cặp bản mã 
thay vào biểu thức (11b), ta có điều phải chứng minh **
 (CCCC2 , 2 ), ( 3 , 3 ). 
(C*" ,C " ) thỏa mãn IND-CPA. 
 11 Ta có điều phải chứng minh phương pháp mã hóa giả 
 * Khi  truy vấn bộ mã hóa DenEncPH: xác suất như trình bày thỏa mãn tính chất IND-CPA. 
 Ta có, từ việc giải nghiệm của hệ phương trình đồng dư 6.4 Nhận xét độ an toàn của giao thức mã hóa 
 eA
(1), (6), và các giá trị (Z , S1 M mod p ) ở cả hai giao 1. Như chứng minh ở mệnh đề 3, phương pháp 
thức là hoàn toàn giống hệt nhau và được coi như là hằng MHCTCT đề xuất có khả năng chối từ thuyết phục bên 
 gửi hoặc bên nhận hoặc đồng thời cả hai bên. Như chứng 
số khi chọn lựa bản rõ mb để thực hiện thủ tục tấn 
 minh tại mệnh đề 4, phương pháp đề xuất đảm bảo tính an 
công CPA, với m ( M , T ); b {0,1}. Từ (6): 
 bb toàn IND-CPA của các bản mã đầu ra. 
 *''
 Pr[C11 =C ]= 2. Khi bị cưỡng ép bởi đối phương tấn công thụ động 
 2 2 1 ' (đã thu được các bản mã CCC, , ), bên gửi hoặc bên 
 =Pr[(U1DenEncPH Z S 1 DenEncPH Z )( Z Z ) mod p C 1 ] 1 2 3
  AAe 2 2 1 ' nhận hoặc cả hai bên trình ra thông điệp giả mạo M , 
 =Pr[(Tb Z M Z )( Z Z ) mod p C1 ]
 thuật toán mã hóa, các khóa kRAA,,Z,( eAA , d ) hoặc 
  AAe 1 1 '
 =Pr[(Tb M Z ) Z . Z (1 Z ) mod p C1 ]
 kRBB,,Z, eBB , d hoặc kRAA,,kRBB,,Z, eAA , d , 
  AAe '
 =Pr[(Tb M Z ) mod p C1 (1 Z ) mod p ]
 edBB, hoàn toàn phù hợp với nhau. Hai bên cũng 
 =Pr[T AA mod p ( C' (1 Z ) Me ) mod p ]
 b 1 chứng minh rằng đã dùng giao thức mã hóa xác suất để 
 =Pr[ log (CZM' (1 ) eA )]
 ATb 1 gửi an toàn thông điệp . Và theo mệnh đề 4, các bản 
 mã có trong tay đối phương tấn công đảm bảo không 
do  A được bộ mã hóa chọn ngẫu nhiên trong p , và
 phân biệt tính toán với các bản mã do hai bên trình ra. 
T M,,, e Z C '
 bA,1 không đổi nên: Đối phương tấn công có hai cách để có các bản mã 
 11 CCC1 , 2 , 3 , cách thứ nhất là thu được trên kênh truyền 
 =Pr[ A ]= n 1 
 p 1 21  công cộng (các bản mã này được tạo ra từ giao thức mã 
 hóa có thể chối từ giả xác suất – giao thức DenEncPH), 
 Như đã chứng minh, do là hàm không cách thứ hai dựa vào bộ tham số và thuật toán do hai bên 
 liên lạc trình ra với đối phương tấn công (các bản mã 
đáng kể theo biến do là một đa thức nên: được tạo ra từ giao thức mã hóa xác suất – giao thức 
 EncPH_F). Đối phương tấn công có hai khả năng sau: i) 
 cũng là một hàm không đáng kể của 
 đồng ý với những người dùng và ii) chứng minh các bản 
thay vào biểu thức (11a) ta có điều phải chứng minh mã được tạo ra bằng giao thức MHCTCT. Tuy nhiên, khả 
 năng thứ hai không khả thi vì không có manh mối. Từ các 
 thỏa mãn IND-CPA. 
 bản mã CCC , , có trong tay, đối phương tấn công có 
 Lập luận hoàn toàn tương tự cho: 1 2 3
TÍNH AN TOÀN IND-CPA CỦA PHƯƠNG PHÁP MÃ HÓA CÓ THỂ CHỐI TỪ. 
thể khôi phục lại các giá trị ngẫu nhiên thêm vào REFERENCES 
 '" [1] Ran Canetti, Cynthia Dwork, Moni Naor, and Rafail Ostrovsky, 
 i (C i C i )mod p i 1,2,3 (thực chất là các giá trị 
 "Deniable Encryption," Proceedings Advances in Cryptology – 
 ABA  
 Tmod p , U12 mod p , U mod p được tạo ra từ giao CRYPTO 1997. Lectute Notes in Computer Science. Springer – 
thức DenEncPH), để từ các giá trị này để tính ra thông Verlag. Berlin, Heidelberg, New York, pp. 90-104, 1997. 
 [2] Truecrypt: Free open-source on-the-fly encryption. [Online]. 
điệp bí mật T , đối phương tấn công phải tính một trong  
các khóa riêng QQ( ,  ), (  ,  ). Việc tính ra một [3] Roger Needham, and Adi Shamir Ross Anderson, "The 
 AAABBB steganographic file system. In Information Hiding," Springer, pp. 
trong các khóa riêng QA hoặc QB được thực hiện bằng 73-82, 1998. 
 [4] AndrewD. McDonald and MarkusG. Kuhn. Stegfs, "A 
cách giải bài toán logarith rời rạc modulo p , với cách steganographic file system for linux. In Andreas Pfitzmann, editor, 
chọn p như mô tả thì độ khó bài toán đủ đảm bảo an Information," Springer Berlin Heidelberg, pp. 463–477, 2000. 
 [5] B. Meng, "A Secure Internet Voting Protocol Based on Non-
toàn cho giao thức. interactive Deniable Authentication Protocol and Proof Protocol 
 3. Để chống lại tấn công giả mạo tích cực, khi mà đối that Two Ciphertexts are Encryption of the Same Plaintext," 
phương tấn công giả mạo là một trong các bên tham gia Journal of Networks, pp. 370–377, 2009. 
 [6] I. Yu, E. Kushilevits, and R. Ostrovsky, "Efficient Non-interactive 
truyền tin, giao thức có thể được bổ sung thủ tục xác thực Secure Computation," Advances in Cryptology -- EUROCRYPT 
giữa hai bên trước khi thực hiện quá trình trao đổi tham 2011. Lectute Notes in Computer Science. Springer – Verlag. 
số bí mật và mã hóa như cách thức thực hiện trong bài Berlin, Heidelberg, New York, pp. 406-425, 2011. 
 [7] C. Wang and J.A. Wang , "Shared-key and Receiver-deniable 
báo [18]. Hoặc một cách đơn giản để xác thực giữa hai Encryption Scheme over Lattice," Journal of Computational 
bên đó là hai bên thống nhất trước một thuật toán bí mật Information Systems, pp. 747-753, 2012. 
để rút trích ra bộ tham số bí mật sử dụng trong thiết lập [8] [8] N.A. Moldovyan, A.A. Moldovyan, and A.V. Shcherbacov, 
 "Deniable-encryption protocol using commutative transformation," 
các hệ phương trình (1) đến (10) từ tham số bí mật dùng Workshop on Foundations of Informatics, pp. 285-298, 2016. 
chung Z AB được thỏa thuận ở phiên liên lạc, kỹ thuật này [9] N.A. Moldovyan, A.N. Berezin, A.A. Kornienko, and A.A. 
 Moldovyan, "Bi-deniable Public-Encryption Protocols Based on 
được giới thiệu trong bài báo [19]. Tuy nhiên, nếu có quá Standard PKI," Proceedings of the 18th FRUCT & ISPIT 
trình thống nhất thuật toán bí mật này từ trước, khi đó Conference, Technopark of ITMO University, Saint-Petersburg, 
lược đồ mã hóa trở thành một lược đồ mã hóa có chia sẻ Russia. FRUCT Oy, Finland, pp. 212-219, 2016. 
 [10] A.A. Moldovyan, N.A. Moldovyan, and V.A. Shcherbakov, "Bi-
trước một quy ước bí mật. Deniable Public-Key Encryption Protocol Secure Against Active 
 Coercive Adversary," Buletinul Academiei de Stiinte a Republicii 
VII. KẾT LUẬN Moldova. Mathematica, pp. 23-29, 2014. 
 [11] Nam Hai Nguyen, N. A. Moldovyan, A. V. Shcherbacov., Hieu 
 Giao thức đề xuất trong [11] sử dụng thuật toán mã hóa Minh Nguyen, Duc Tam Nguyen, "No-Key Protocol for Deniable 
Pohlig-Hellman có tính chất giao hoán, thực hiện quá Encryption" Information Systems Design and Intelligent 
 Applications: Proceedings of Fourth International Conference 
trình truyền tin mật như một quá trình không trao đổi INDIA 2017.: Springer, Singapore, 2018, pp. 96-104. 
khóa trước phiên liên lạc, mã hóa đồng thời thông điệp [12] Ulf Carlsen, "Cryptographic protocol flaws:know your enemy," in 
mật và thông điệp giả mạo, sử dụng kỹ thuật thỏa thuận Computer Security Foundations Workshop VII. Proceedings., 
khóa Diffie-Hellman chia sẻ tham số bí mật dùng chung 1994. 
 [13] W. Diffie and M. Hellman, "New Directions in Cryptography," 
sử dụng một lần. Để có thể ngụy trang được trong quá IEEE Transactions on Information Theory, p. 644–654, 1976. 
trình thực hiện truyền tin, cùng với giao thức MHCTCT [14] M. Hellman and S. Pohlig, "Exponentiation Cryptographic 
thực sự dùng thật trong truyền tin mật, một giao thức mã Apparatus and Method," U.S. Patent # 4,424,414, 1984. 
 [15] N. Moldovyan and A. Moldovyan, Innovative cryptography 2nd 
hóa xác suất được xây dựng để trình ra cho đối phương Edition, Boston: Charles River Media, 2007, pp. 50-57. 
tấn công. Do giao thức MHCTCT xây dựng dựa trên giao [16] Douglas Robert Stinson, Maura Paterson, Cryptography Theory 
thức mã hóa xác suất với việc thay thế nguồn ngẫu nhiên and Practice, 4th ed., CRC Press, 2019. 
 [17] J. Katz and Y. Lindell, "Introduction to Modern Cryptography: 
bằng thông điệp giả bí mật có chủ đích vào quá trình mã Principles and Protocols," in Cryptography and Network Security 
hóa, vì vậy nó được coi như là một giao thức mã hóa giả Series, Chapman & Hall/CRC, 2007. 
xác suất. [18] Nguyễn Đức Tâm, Lê Mỹ Tú, "Phương pháp kết hợp ẩn mã với mã 
 hóa khóa công khai có thể chối từ" Tạp chí nghiên cứu KH&CN 
 Như chứng minh tại bài báo này, giao thức MHCTCT quân sự, vol. Số đặc san An toàn thông tin, pp. 100-108, 8 2019. 
sử dụng thuật toán mã hóa Pohlig-Hellman thỏa mãn đầy [19] Nguyễn Đức Tâm, Lê Mỹ Tú, "Đề xuất giao thức mã hóa không 
đủ tính chất của một lược đồ MHCTCT theo định nghĩa khóa có thể chối từ giả xác suất sử dụng thuật toán RSA" Tạp chí 
của Canetti [1] đó là tính đúng đắn, tính an toàn IND- nghiên cứu KH&CN quân sự, vol. 62, pp. 37-45, 8 2019. 
CPA và tính chối từ thuyết phục. Các bản mã tạo ra từ 
 IND-CPA SECURITY OF DENIABLE 
giao thức MHCTCT mà hai bên sử dụng truyền tin mật 
 ENCRYPTION METHOD BASE ON SHAMIR 
đảm bảo tính không phân biệt tính toán với các bản mã do 
 THREE-PASS PROTOCOL 
hai bên sử dụng giao thức giả mạo trình diễn lại quá trình 
mã hóa khi bị tấn công cưỡng ép. Abstract: This paper analyzes and prove the correct, security, 
 deniable and IND-CPA secủity of a deniable encrypiton method, 
 Với việc sử dụng các nguyên thủy mật mã an toàn và this method base on Shamir three-pass protocol using Pohlig-
đã được chứnh minh đầy đủ tính chất của một giao thức Hellman encrypion algorithm. This deniable encryption method 
MHCTCT, phương pháp hoàn toàn có khả năng ứng dụng has been proposed in the paper [11], but it not been proven the 
được trong thực tế. properties of a deniable encryption protocol. 
 Keyword: Deniable encryption, Shamir three-pass protocol, 
 commutative encrypion, probabilistic encryption, pseudo 
 probabilistic encryption. 
 Nguyễn Đức Tâm 
SƠ LƯỢC VỀ TÁC GIẢ 
Nguyễn Đức Tâm 
Sinh năm 1974 tại Bắc Giang. Tốt 
nghiệp chuyên ngành Kỹ thuật mật 
mã tại Học viện KTMM. Hiện 
đang công tác tại Học viện Kỹ 
thuật mật mã. Hướng nghiên cứu: 
mã hóa có thể chối từ. 
Email:nguyenductamkma@gmail.com