Chứng minh tính đúng đắn, an toàn và chối từ của phương pháp mã hóa theo khối giả xác suất có thể chối từ

Tóm tắt: Bài báo đề xuất một phương pháp mã khối hóa theo khối giả xác suất có thể chối từ, phương pháp thực hiện dựa trên sự kết hợp của một số mã khối đã được chuẩn hóa và sử dụng rộng rãi hiện nay với hệ phương trình đồng dư tuyến tính, đồng thời trình bày các chứng minh về tính đúng đắn, an toàn và chối từ của phương pháp đề xuất.

pdf11 trang | Chia sẻ: thanhle95 | Lượt xem: 455 | Lượt tải: 0download
Bạn đang xem nội dung tài liệu Chứng minh tính đúng đắn, an toàn và chối từ của phương pháp mã hóa theo khối giả xác suất có thể chối từ, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 65, 02 - 2020 175 CHỨNG MINH TÍNH ĐÚNG ĐẮN, AN TOÀN VÀ CHỐI TỪ CỦA PHƯƠNG PHÁP MÃ HÓA THEO KHỐI GIẢ XÁC SUẤT CÓ THỂ CHỐI TỪ Nguyễn Đức Tâm1*, Nguyễn Nam Hải2, Nguyễn Hiếu Minh3 Tóm tắt: Bài báo đề xuất một phương pháp mã khối hóa theo khối giả xác suất có thể chối từ, phương pháp thực hiện dựa trên sự kết hợp của một số mã khối đã được chuẩn hóa và sử dụng rộng rãi hiện nay với hệ phương trình đồng dư tuyến tính, đồng thời trình bày các chứng minh về tính đúng đắn, an toàn và chối từ của phương pháp đề xuất. Từ khóa: Mã hóa có thể chối từ; Mã hóa theo khối xác suất; Mã hóa theo khối giả xác suất; Hệ phương trình đồng dư. 1. GIỚI THIỆU Các kỹ thuật mã hóa thông thường hiện nay nhằm bảo vệ tính bí mật, an toàn, xác thực của thông tin khi lưu trữ và truyền thông, chống lại các tấn công nhằm thu tin thám mã. Mã hóa có thể chối từ (MHCTCT) là một kỹ thuật mật mã đặc biệt và tiếp cận kỹ thuật khác biệt với mã hóa thông thường. Với mã hóa thông thường, mỗi bản mã là dẫn xuất duy nhất của một bản rõ và khóa mã. MHCTCT cho phép giải mã một bản mã cho ra hai bản rõ có ý nghĩa khác nhau. Khái niệm MHCTCT được Canetti và cộng sự công bố lần đầu tại bài báo [1]. Từ đặc trưng của MHCTCT, nó được ứng dụng chống lại dạng tấn công cưỡng ép trong kịch bản mà kẻ thứ ba chặn thu bản mã truyền trên kênh truyền công cộng và cưỡng ép bên gửi hoặc bên nhận hoặc cả hai bên phải trình ra thuật toán mã hóa, bản rõ và các khóa mã đã sử dụng [1], ứng dụng trong lưu trữ ẩn giấu các hệ thống tệp dữ liệu nhạy cảm [2-4], ứng dụng trong các môi trường giao dịch đa bên không cam kết nội dung như các giao thức bỏ phiếu điện tử, đấu giá điện tử [5]. MHCTCT đã được nghiên cứu và đề xuất cụ thể một số giao thức sử dụng hệ mật khóa công khai [6], hoặc sử dụng hệ mật khóa bí mật [7]. Gần đây, một giải pháp MHCTCT được đề xuất sử dụng thuật toán mã hóa giao hoán và khóa bí mật dùng chung trong [8]. Bài toán đảm bảo an toàn của các giao thức MHCTCT chống tấn công cưỡng ép được thảo luận trong các bài báo [9-10]. Ngoài ra, để đảm bảo an toàn chống lại các tấn công cưỡng ép chủ động, cần bổ sung vào trong các giao thức MHCTCT thủ tục xác thực bên gửi và bên nhận [10]. Bài báo [11] đã đề xuất thuật toán mã hóa theo khối có thể chối từ, trong đó, thuật toán mới được mô tả tổng quát về phương pháp còn các tính chất chưa được chứng minh. Bài báo này mô tả chi tiết thuật toán mã hóa theo khối có thể chối từ để thực hiện phương pháp đề xuất trong [11], đồng thời phân tích và chứng minh tính đúng đắn, an toàn và chối từ của phương pháp. Trong nội dung bài báo, phần 2 mô tả mô hình truyền tin và ngữ cảnh tấn công. Phần 3 giới thiệu chi tiết thuật toán thực hiện phương pháp mã hóa theo khối giả xác suất có thể chối từ. Phần 4 đi chứng minh các tính chất của phương pháp đề xuất. Phần 5 kết luận. 2. MÔ HÌNH TRUYỀN TIN VÀ NGỮ CẢNH TẤN CÔNG Mô hình truyền tin và ngữ cảnh tấn công cưỡng ép trong việc thực hiện truyền tin bằng mã hóa theo khối khóa đối xứng có thể chối từ được mô tả chi tiết như sau: Sau khi bản mã được gửi, đối phương chặn thu được bản mã trên kênh truyền, tiến hành tấn công cưỡng ép bên gửi, hoặc bên nhận, hoặc đồng thời cả hai bên trình ra: 1. Bản rõ tương ứng với bản mã; Công nghệ thông tin & Cơ sở toán học cho tin học N. Đ. Tâm, N. N. Hải, N. H. Minh, “Chứng minh tính đúng đắn, an toàn có thể chối từ.” 176 2. Các thuật toán mã hóa và giải mã; 3. Khóa mã cùng với việc lặp lại toàn bộ quá trình mã hóa thông điệp để sinh ra các khối bit của bản mã hoặc quá trình giải mã bản mã để khôi phục thông điệp. Việc an toàn bảo mật chống lại tấn công đã mô tả ở trên được giải quyết nếu phương pháp MHCTCT tạo ra bản mã bằng khóa giả mạo không phân biệt tính toán với bản mã tạo ra từ mã hóa xác suất. Để thỏa mãn điều kiện này, phương pháp MHCTCT khóa đối xứng cần có một số tiêu chí thiết kế như sau: 1. MHCTCT khóa đối xứng phải được thực hiện dưới dạng mã hóa đồng thời hai thông điệp, một thông điệp bí mật và một thông điệp giả mạo, sử dụng khóa bí mật và khóa giả mạo (đã được chia sẻ trước giữa hai bên); 2. Thuật toán MHCTCT được thiết kế dựa trên thuật mã hóa xác suất khóa đối xứng, thỏa mãn quá trình thực hiện hai thuật toán phải giống nhau và bản mã kết quả đầu ra của hai thuật toán không phân biệt về mặt tính toán; 3. Các khóa bí mật cần có độ dài cố định, nhưng bộ mã hóa có khả năng thực hiện mã hóa an toàn những thông điệp có độ dài tùy ý; 4. Các bên tham gia trong truyền tin mật có thể chứng minh một cách hợp lý rằng họ đã sử dụng mã hóa xác suất để có được độ an toàn cao hơn đối với các tấn công tiềm năng với giải pháp thực hiện bằng cách bổ sung thêm nguồn ngẫu nhiên vào dữ liệu rõ ban đầu sau đó mã hóa để tăng tính ngẫu nhiên của bản mã. 3. PHƯƠNG PHÁP MÃ HÓA THEO KHỐI GIẢ XÁC SUẤT CÓ THỂ CHỐI TỪ Phương pháp mã hóa theo khối có thể chối từ giả xác suất [11] thực hiện mã hóa đồng thời khối thông điệp bí mật cùng khối thông điệp giả mạo M để tạo thành khối mã .C Khối mã C đảm bảo tính không phân biệt về mặt tính toán với khối mã C được tạo ra từ thuật toán mã hóa theo khối xác suất khi mã hóa thông điệp giả mạo M T cùng với nguồn ngẫu nhiên thêm vào. Như vậy, phương pháp chối từ dựa trên hai thuật toán: - Thuật toán thứ nhất là thuật toán mã hóa theo khối giả xác suất có thể chối từ , đây là thuật toán mà hai bên dùng để truyền tin mật, sử dụng các thuật toán mã khối chuẩn đã được kiểm chứng an toàn trong thực tế để mã hóa đồng thời thông điệp bí mật T cùng thông điệp giả mạo ,M tạo ra hai khối mã trung gian là TC và ,MC sau đó sử dụng hệ phương trình đồng dư tuyến tính hai ẩn số để từ hai khối mã trung gian, tính toán tạo một khối mã đầu ra .C - Thuật toán thứ hai là thuật toán mã hóa theo khối xác suất, đây sẽ là thuật toán giả mạo dùng để trình cho đối phương khi bị tấn công cưỡng ép, với đầu vào là thông điệp giả mạo M và tham số ngẫu nhiên .R Ở cả hai thuật toán, do việc sử dụng hai khối mã trung gian làm đầu vào của hệ phương trình đồng dư để tạo ra một khối mã đầu ra, do vậy thuật toán được gọi là thuật toán mã hóa theo khối. 3.1. Thuật toán mã hóa theo khối giả xác suất có thể chối từ Thuật toán mã hóa theo khối có thể chối từ được mô tả chi tiết như sau: - Khi cần truyền thông điệp bí mật ,T đầu tiên thực hiện mã hóa đồng thời hai thông điệp (bí mật ,T giả mạo )M bằng hàm mã khối E có đầu vào và đầu ra v -bit tạo thành hai khối mã, sau đó sử dụng thuật toán giải hệ phương trình đồng dư tuyến tính để kết hợp hai khối mã trung gian thành một khối mã đầu ra .C Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 65, 02 - 2020 177 - Việc mã hóa/giải mã sử dụng hai khóa bí mật phân phối trước  , P p và  , Q q , với P và Q là các khóa của hàm mã khối E có đầu vào v -bit, k là số nguyên tố có kích thước 1 v bit, với (( , ), )P p Q không thay đổi, q là số nguyên ngẫu nhiên có kích thước 1 v bit và thay đổi như hình thức khóa phiên. Trong trường hợp bị tấn công cưỡng ép, bộ khóa  , P p dùng để giải mã và trình ra thông điệp giả mạo, bộ khóa  , Q q hai bên giữ bí mật dùng để giải mã để có thông điệp bí mật ở chế độ truyền tin mật. Thuật toán gồm hai giai đoạn, chi tiết như sau: 1. Sử dụng mã khối E và khóa P , mã hóa khối thông điệp M để tạo ra khối :MC ( ).M PC E M Sử dụng mã khối E và khóa Q , mã hóa khối thông điệp T để tạo ra khối :TC ( ).T QC E T 2. Sử dụng các giá trị p và q để ghép hai khối mã ( , )M TC C thành một khối mã đầu ra C , với C là nghiệm của hệ phương trình đồng dư sau: mod ( ) mod ( ) M T С C p a С C q b    (1) Các khối mã trung gian C và CM T được biểu diễn dạng nhị phân; do p và q là các số nguyên tố cùng nhau có kích thước 1 v bit, do vậy kích thước khối mã đầu ra C trong trường hợp tổng quát sẽ bằng 2 2v bit (tức là kích thước khối C nhiều hơn 2 bit so với tổng bit của C và CM T . Vì p là số nguyên tố nên d( , ) 1gc p q  , theo định lý đồng dư Trung Hoa, nghiệm của hệ đồng dư (1) là: 1 1[ ( mod ) ( mod )]modM TC C q q p C p p q pq    (2) Trong đó 1 modq p là nghịch đảo của q theo modulo p , 1 modp q là nghịch đảo của p theo modulo q . Các thuật toán chi tiết thể hiện quá trình mã hóa và giải mã: a) Quá trình mã hóa Thuật toán Enc_PC Thuật toán mã hóa theo khối giả xác suất có thể chối từ INPUT: , , , , ,M T p q P Q OUTPUT: C { ( )M PC E M ( )T QC E T 1 1[ ( mod ) ( mod )]modM TC C q q p C p p q pq    } return .C b) Quá trình giải mã ở chế độ truyền tin mật Công nghệ thông tin & Cơ sở toán học cho tin học N. Đ. Tâm, N. N. Hải, N. H. Minh, “Chứng minh tính đúng đắn, an toàn có thể chối từ.” 178 1. Nhận khối mã C ; 2. Tính khối mã trung gian modTC C q ; 3. Khôi phục khối thông điệp mật 1( )Q TT E C  ; Thuật toán Dec_PC Giải mã ở chế độ truyền tin mật INPUT: , ,C q Q OUTPUT: T { modTC C q 1( )Q TT E C  } return .T 3.2. Thuật toán mã hóa theo khối xác suất Do thuật toán mã hóa theo khối có thể chối từ đề xuất nhằm chứng minh với kẻ cưỡng ép, khi thỏa mãn điều kiện bản mã tạo ra không thể phân biệt được về mặt tính toán với bản mã tạo ra từ mã hóa theo khối xác suất đóng vai trò là thuật toán giả mạo đi kèm thuật toán MHCTCT. Vì điều kiện này, cần xây dựng thuật toán mã hóa theo khối xác suất, mà khi dùng thuật toán này mã thông điệp giả mạo ,M nó có khả năng tạo ra bản mã không phân biệt được với bản mã được tạo ra bởi thuật toán mã hóa theo khối giả xác suất khi mã hóa đồng thời cả hai thông điệp  , .T M Thuật toán mã hóa theo khối xác suất đi kèm với thuật toán mã hóa theo khối giả xác suất (mục 3.1) được mô tả chi tiết như sau: - Khóa dùng để mã hóa giờ đây là cặp giá trị  , P p dùng để thực hiện hệ phương trình đồng dư (1); - Các bước mã khối dữ liệu thông điệp giả mạo M được thực hiện theo các bước: 1. Khối dữ liệu M được mã bằng hàm mã khối  : .M PE C E M 2. Thuật toán được thuyết minh với đối phương tấn công cưỡng ép rằng, do hàm mã khối E không đảm bảo an toàn ngữ nghĩa trong một số trường hợp (như chế độ mã khối ECB chẳng hạn), nhằm tăng cường tính ngẫu nhiên của bản mã đầu ra C , thuật toán thực hiện bổ sung giá trị ngẫu nhiên 2vR và một số nguyên ngẫu nhiên r thỏa mãn 12 2v vr   (ngoài ra hai bên phải ẩn giấu việc chọn r q ), sau đó khối mã đầu ra C được tính từ hệ phương trình đồng dư sau: mod ( ) mod ( ) MС C p a C R r b    (3) Ở đây các giá trị ngẫu nhiên thêm vào ( , )R r không lưu nhớ trong bộ nhớ của máy tính trong quá trình thực hiện mã hóa xác suất, chúng được thêm vào với giả thiết 1 như sau: Giả thiết 1: Các giá trị ngẫu nhiên ( , )R r thêm vào mã khối xác suất, được tạo ra trong mỗi lần thực hiện mã hóa và không lưu nhớ lại trong bộ nhớ của máy tính. Nhận xét 1: Phương trình (1a) của hệ phương trình (1) và phương trình (3a) của hệ phương trình (3) giống nhau. Xét hệ phương trình (3), nếu với mọi bản mã C thỏa mãn hệ Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 65, 02 - 2020 179 phương trình (1) thì cũng thỏa mãn phương trình (3a) của hệ phương trình (3), nếu chọn một số nguyên ngẫu nhiên r (thỏa mãn 12 2v vr   ), sử dụng giá trị C là nghiệm của hệ phương trình (1), tính giá trị R theo công thức: modR C r thì lúc này C đương nhiên thỏa mãn hệ phương trình đồng dư (3). Lưu ý rằng C chính là các khối mã đã được bên gửi dùng thuật toán Enc_PC mã hóa và gửi cho bên nhận trên kênh truyền công khai và kẻ tấn công thu được bản mã này. Đây chính là đặc điểm gắn kết quan trọng nhất của hai thuật toán vừa trình bày và nó được sử dụng để thực hiện chối từ khi giải mã ở chế độ bị tấn công cưỡng ép. Các thuật toán chi tiết thể hiện quá trình mã hóa và giải mã như sau: a) Quá trình mã hóa Thuật toán Enc_PT Thuật toán mã hóa theo khối xác suất kết hợp giữa khối bit ngẫu nhiên R và khối mã trung gian MC tạo ra khối mã đầu ra C (đây là thuật toán giả mạo trình ra khi bị tấn công cưỡng ép) INPUT: , , , ,M R p r P OUTPUT: C { ( )M PC E M 1 1[ ( mod ) ( mod )]modMC C r r p Rp p r pr    } return .C b) Quá trình giải mã ở chế độ bị tấn công cưỡng ép (thực hiện chối từ) 1. Nhận khối mã ;C 2. Tính khối mã trung gian mod ;MC C p 3. Khôi phục thông điệp (giả mạo) 1( );P MM E C  và trình ra với đối phương tấn công cưỡng ép cùng với bộ khóa  ,P p phù hợp hoàn toàn với khối mã C , thuật toán mã hóa xác suất và các tham số ,r R được chọn và tính toán như mô tả tại nhận xét 1. Thuật toán Dec_PT Giải mã ở chế độ bị tấn công cưỡng ép INPUT: , ,C p P OUTPUT: M { modMC C p 1( )P MM E C  } return .M 4. TÍNH ĐÚNG ĐẮN, AN TOÀN VÀ CHỐI TỪ CỦA PHƯƠNG PHÁP ĐỀ XUẤT Công nghệ thông tin & Cơ sở toán học cho tin học N. Đ. Tâm, N. N. Hải, N. H. Minh, “Chứng minh tính đúng đắn, an toàn có thể chối từ.” 180 4.1. Phát biểu định nghĩa về mã hóa khóa đối xứng có thể chối từ linh hoạt Phương pháp thực hiện mã hóa có thể chối từ như trình bày ở mục 3 sử dụng cách thức chia sẻ khóa trước và sử dụng hai thuật toán, một thuật toán thực sự sử dụng (thuật toán không trung thực với kẻ tấn công), một thuật toán giả mạo trình ra khi bị tấn công cưỡng ép (thuật toán trung thực với kẻ tấn công). Từ các khái niệm của Canetti và cộng sự trong [1], phương pháp bài báo đề xuất là phương pháp mã hóa khóa đối xứng có thể chối từ linh hoạt. Định nghĩa về mã hóa khóa đối xứng có thể chối từ linh hoạt bên gửi được phát biểu dựa vào định nghĩa 3 về mã hóa có thể chối từ khóa công khai bên gửi linh hoạt và định nghĩa 4 về mã hóa có thể chối từ khóa đối xứng trong bài báo [1]: Định nghĩa 4*: giao thức mã hóa khóa đối xứng có thể chối từ linh hoạt bên gửi Một giao thức mã hóa  với bên gửi A và bên nhận B, sử dụng một bit trạng thái P (với hai giá trị là ,T CP P ) và tham số bí mật n được gọi là một giao thức mã hóa khóa đối xứng có thể chối từ linh hoạt bên gửi nếu thỏa mãn: Tính đúng đắn: Bên nhận luôn giải mã được bản rõ từ bên gửi gửi sang với một xác suất áp đảo. Tính an toàn: Với bất kỳ hai thông điệp 1 2,m m thuộc không gian rõ M và bất kỳ bit trạng thái { , }T CP P P và một khóa bí mật ngẫu nhiên k , ta có: 1 2( , , ) ( , , ) cCOM P m k COM P m k  Tính chối từ: Tồn tại một thuật toán giả mạo hiệu quả  sử dụng các tham số 1 2,m m M cùng với các tham số được hai bên chọn thống nhất ' ', , , ,S R S Rk r r r r làm đầu vào của hai bên gửi, nhận, với bản mã 1( , , , , )C S Rc COM P m k r r , và các tham số   1 2( , ) ( , , , , ),S Sk r m k r c m khi đó sai khác giữa hai phân bố xác suất của   2( , , , )Sm k r c và ' ' ' 2 2( , , , ( , , , , ))S T S Rm k r COM P m k r r là hàm không đáng kể. Định nghĩa về mã hóa khóa đối xứng có thể chối từ linh hoạt bên nhận được phát biểu dựa vào định nghĩa 3 về mã hóa có thể chối từ khóa công khai bên gửi linh hoạt, định nghĩa 4 về mã hóa có thể chối từ khóa đối xứng, định nghĩa 9 về mã hóa có thể chối từ khóa công khai bên nhận linh hoạt trong bài báo [1]: Định nghĩa 4**: giao thức mã hóa khóa đối xứng có thể chối từ linh hoạt bên nhận Một giao thức mã hóa  với bên gửi A và bên nhận B, sử dụng một bit trạng thái P (với hai giá trị là ,T CP P ) và tham số bí mật n được gọi là một giao thức mã hóa khóa đối xứng có thể chối từ linh hoạt bên nhận nếu thỏa mãn: Tính đúng đắn: Bên nhận luôn giải mã được bản rõ từ bên gửi gửi sang với một xác suất áp đảo. Tính an toàn: Với bất kỳ hai thông điệp 1 2,m m thuộc không gian rõ M và bất kỳ bit trạng thái { , }T CP P P và một khóa bí mật ngẫu nhiên k , ta có: 1 2( , , ) ( , , ) cCOM P m k COM P m k  Tính chối từ: Tồn tại một thuật toán giả mạo hiệu quả  sử dụng các tham số 1 2,m m M cùng với các tham số được hai bên chọn thống nhất ' ', , , ,S R S Rk r r r r làm đầu vào của hai bên gửi, nhận, với bản mã 1( , , , , )C S Rc COM P m k r r , và các tham số   1 2( , ) ( , , , , ),R Rk r m k r c m khi đó sai khác giữa hai phân bố xác suất của   2( , , , )Rm k r c và Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 65, 02 - 2020 181 ' ' ' 2 2( , , , ( , , , , ))R T S Rm k r COM P m k r r là hàm không đáng kể. 4.2. Chứng minh tính đúng đắn, an toàn và chối từ của phương pháp đề xuất Mệnh đề 1: Phương pháp mã hóa theo khối được trình bày như ở mục 3 là một giao thức mã hóa khóa đối xứng có thể chối từ linh hoạt bên gửi như được mô tả trong Định nghĩa 4*. Ta có: - Khi :CP P Thuật toán hai bên sử dụng lúc này là thuật toán không trung thực với kẻ tấn công, tức là hai bên sử dụng thuật toán mã hóa theo khối giả xác suất có thể chối từ (thuật toán mã hóa là Enc_PC, thuật toán giải mã là Dec_PC). - Khi :TP P Thuật toán hai bên sử dụng lúc này là thuật toán trung thực với kẻ tấn công, tức là hai bên sử dụng thuật toán mã hóa theo khối xác suất (thuật toán mã hóa là Enc_PT, thuật toán giải mã là Dec_PT). Tính đúng đắn: + Khi :CP P Đầu vào của bên gửi A là ( , );M TC C Đầu ra của bên nhận B sau khi giải mã là ( , ),M TC C điều này luôn thỏa mãn vì từ bản mã ,C B giải mã theo công thức mod ; mod .M TC C p C C q  + Khi :TP P Đầu vào của bên gửi A là ( , )MC R ; Đầu ra của bên nhận B sau khi giải mã là '( , )MC R , trong đó 'R R , do hai bên sử dụng mã hóa xác suất nên bên nhận không quan tâm đến giá trị ngẫu nhiên R mà bên gửi thêm vào quá trình mã hóa. Từ bản mã ,C B giải mã theo công thức modMC C p để khôi phục được chính xác .MC Tính an toàn: Ta có, với 1 2( , ), ( , )M T Mm C C m C R  + Khi :CP P Ta có 1 1 1( , , ) ( mod ) ( mod )]modC M TCOM P m k C q q p C p p q pq    1 1 2( , , ) ( mod ) ( mod )]modC MCOM P m k C q q p Rp p q pq    do R ngẫu nhiên, có phân bố xác suất giống TC , nên 1 2( , , ) ( , , ) c C CCOM P m k COM P m k  + Khi :TP P Ta có 1 1 1( , , ) ( mod ) ( mod )]modT M TCOM P m k C r r p C p p r pr    1 1 2( , , ) ( mod ) ( mod )]modT MCOM P m k C r r p Rp p r pr    do R ngẫu nhiên, có phân bố xác suất giống TC , nên 1 2( , , ) ( , , ) c T TCOM P m k COM P m k  Tính chối từ: Công nghệ thông tin & Cơ sở toán học cho tin học N. Đ. Tâm, N. N. Hải, N. H. Minh, “Chứng minh tính đúng đắn, an toàn có thể chối từ.” 182 Với hai thuật toán ứng với hai trạng thái ( , ) :C TP P + 2 2;m m + chọn   '; ; ;S S Sk p r r r r q    và không có ';R Rr r , khi đó: 1 1 1( , , , , ) ( mod ) ( mod )]modC S R M TCOM P m k r r C q q p C p p q pq    ; ' ' 1 1 2( , , , , ) ( mod ) ( mod )]modT S R MCOM P m k r r C r r p Rp p r pr    ; lúc này: Phân bố xác suất của 1( , , , , )C S RCOM P m k r r sẽ nằm khoảng giá trị [0, 1]pq  và bằng 1 pq . Phân bố xác suất của ' '2( , , , , )T S RCOM P m k r r sẽ nằm trong khoảng giá trị [0, 1]pr  và bằng 1 pr . Sai khác giữa hai phân bố xác suất: Khi q>r, sai khác giữa hai phân bố xác suất là Trong khoảng [0, ),pr sai khác giữa hai phân bố xác suất bằng 1 1 ( ) pr pq  ; Trong khoảng ( , 1],pr pq  sai khác giữa hai phân bố xác suất bằng 1 1 ( 0) pr pr   ; Do vậy, sai khác lớn nhất của hai phân bố xác suất trong [0, ) :pq 1 1 1 max( , ). pr pq pr  Khi q<r, sai khác giữa hai phân bố xác suất là Trong khoảng [0, ),pq sai khác giữa hai phân bố xác suất là 1 1 ( ) pq pr  ; Trong khoảng ( , 1],pq pr  sai khác giữa hai phân bố xác suất bằng 1 1 ( 0) ; pq pq   Do vậy, sai khác lớn nhất của hai phân bố xác suất trong [0, 1] :pr  1 1 1 max( , ) pq pr pq  . Do cách chọn tham số: p là số nguyên tố có kích thước 1v  bit; ,q r là 2 số ngẫu nhiên phân bố đều trong 1[2 ;2 )v v các giá trị 1 1 1 max( ; ), pr pq pr  1 1 1 max( ; ) pq pr pq  nhỏ không đáng kể. Như vậy, có thể coi phân bố xác suất của 1( , , , , )C S RC
Tài liệu liên quan