Tóm tắt Luận án tiến sĩ Kỹ thuật: Các hệ mặt dựa trên vành đa thức chẵn

Chia sẻ: Trần Văn Nan | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST

Báo xấu

10
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích nghiên cứu của luận án là xây dựng được các hệ mật có hiệu năng tính toán cao và an toàn dựa trên các ưu điểm của cấu trúc đại số vành đa thức chẵn R2n .

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án tiến sĩ Kỹ thuật: Các hệ mặt dựa trên vành đa thức chẵn

BỘ THÔNG TIN VÀ TRUYỀN THÔNG HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- Cao Minh Thắng CÁC HỆ MẬT DỰA TRÊN VÀNH ĐA THỨC CHẴN Chuyên ngành: Kỹ thuật điện tử Mã số: 62.52.02.03 TÓM TẮT LUẬN ÁN TIẾN SỸ KỸ THUẬT ĐIỆN TỬ Hà Nội - 2017
Công trình hoàn thành tại: Học viện Công nghệ Bưu chính Viễn thông, Bộ Thông tin và Truyền thông. Người hướng dẫn khoa học: GS. TS Nguyễn Bình. Phản biện 1: ……………………………………… ……………………………………………………. ……………………………………………………. Phản biện 2: ……………………………………… ……………………………………………………. ……………………………………………………. Phản biện 3: ……………………………………… ……………………………………………………. ……………………………………………………. Luận án sẽ được bảo vệ trước hội đồng chấm luận án cấp Học viện tại Học viện Công nghệ Bưu chính Viễn thông Vào hồi: … giờ …ngày … tháng … năm …….. Có thể tìm hiểu luận án tại: Thư viện Học viện Công nghệ Bưu chính Viễn thông
1 MỞ ĐẦU Mật mã học được phát triển dựa trên lý thuyết toán học và các hệ mật thường dựa trên các phép tính toán trong một cấu trúc đại số nền tảng nào đó. Trong lịch sử phát triển của mật mã, có nhiều các cấu trúc đại số đã được ứng dụng để xây dựng các hệ mật tiêu biểu như: Các vành số nguyên modulo q ký hiệu bởi q , trường nhị phân (2) , trường hữu hạn ( p n ), các ma trận, các đường cong elliptic trên trường hữu hạn hay các dàn (lattice). Bên cạnh các cấu trúc đại số nêu trên, vành đa thức Rn,q là nền tảng ít được ứng dụng trong mật mã và mới chỉ được quan tâm từ năm 1998 khi hệ mật xác suất khóa công khai NTRU ra đời. NTRU cho thấy có thể sử dụng các phần tử khả nghịch trên các vành đa thức để xây dựng các hệ mật có tốc độ có khóa nhỏ và tính toán nhanh. NTRU có nhiều biến thể trên các cấu trúc đại số khác nhau (MaTRU, ETRU, OTRU,…), nhưng đáng chú ý là hệ mật pNE, được đề xuất bởi Stehle và Steinfeld năm 2011, hoạt động trên chính một lớp con của vành đa thức Rn,q với n  2s có độ an toàn IND-CPA. Trong các vành Rn,q , một lớp con với q  2 hay còn gọi là lớp vành đa thức có bậc hữu hạn và hệ số nhị phân Rn  Z 2 [x] ( x n  1) là một lớp vành rất đáng chú ý. Ưu điểm của cấu trúc đại số này là các phép tính trên vành đa thức được thực hiện rất đơn giản và dễ dàng thực hiện bằng phần cứng, cụ thể là phép cộng đa thức hệ số nhị phân thực chất là n phép tính XOR. Đặc biệt hơn, một lớp con của Rn , lớp các vành đa thức chẵn ký hiệu là R2n có một số đặc điểm phù hợp có thể ứng dụng trong mật mã bao gồm:
2 - Các phép tính trên vành có độ phức tạp tính toán thấp, cụ thể là với O( n) phép cộng và O(n 2 ) với phép nhân. Đặc biệt là các phép cộng trong vành đa thức chỉ là một chuỗi các phép tính XOR rất đơn giản trên trường (2) ; - Trong các vành đa thức chẵn R2n , khác với các vành lẻ, chỉ có 2 n thặng dư bậc hai. Tuy nhiên, mỗi thặng dư bậc hai đó lại có đến 2 n căn bậc hai. Điều này cho thấy là nếu biết một căn bậc hai sẽ dễ dàng suy ra thặng dư bậc hai tương ứng nhưng điều ngược lại sẽ không thực hiện được dễ dàng; - Trong các vành đa thức Rn và cụ thể hơn là vành chẵn R2n luôn tồn tại các phần tử khả nghịch, bên cạnh những phần tử không khả nghịch. Nếu xác định được các thuật toán mật mã phù hợp, các phần tử khả nghịch sẽ chính là khóa để giải mã thông tin. Mặc dù vậy, ứng dụng của R2n trong mật mã vẫn còn hạn chế nên mục đích nghiên cứu của luận án là xây dựng được các hệ mật có hiệu năng tính toán cao và an toàn dựa trên các ưu điểm của cấu trúc đại số vành đa thức chẵn R2n . Đối tượng nghiên cứu chính của luận án là các vành đa thức chẵn R2n cùng một số loại vành đa thức có liên quan và các hệ mật dựa trên các vành đa thức này. Phạm vi nghiên cứu của luận án bao gồm: 1. Nghiên cứu tổng quan về mật mã (phân loại, kỹ thuật xây dựng các hệ mật, tham số đánh giá các hệ mật, các mô hình tấn công cơ bản, phương pháp đánh giá độ an toàn) qua đó đánh giá chi tiết các hệ mật dựa trên vành đa thức hiện có. Các kết quả khảo sát này chỉ ra các hạn chế của các kết quả
3 nghiên cứu hiện có và tiềm năng ứng dụng vành đa thức chẵn R2n trong mật mã. 2. Nghiên cứu các đặc tính của vành đa thức chẵn R2n (các khái niệm, các phép tính toán, các phần tử đặc biệt) làm cơ sở toán học phục vụ xây dựng các hệ mật. 3. Nghiên cứu đề xuất một cách tường minh (các không gian khóa, bản rõ, và bản mã cùng các thuật toán tạo khóa, mã hóa và giải mã) và đánh giá các hệ mật dựa trên vành đa thức chẵn R2n . 4. Nghiên cứu một số vành đa thức đặc biệt khác (vành đa thức có hai lớp kề cyclic R2C , vành đa thức Rn,q , n  2s ) từ đó xem xét đề xuất các hệ mật dựa trên sự kết hợp giữa vành đa thức chẵn R2n và các vành đa thức này. Phương pháp nghiên cứu chính được sử dụng trong luận án là phương pháp toán học (lý thuyết số, đại số trừu tượng, xác suất) và độ phức tạp tính toán. Công cụ nghiên cứu chính của luận án là các công cụ toán học và mô phỏng. Về ý nghĩa khoa học luận án: - Chỉ ra một số vành đa thức có số phần tử khả nghịch đạt cực đại và một thuật toán để xác định nghịch đảo của một phần tử khả nghịch trên vành R2k ; Đưa ra một công thức để xác định các phần tử khả nghịch mở rộng và nghịch đảo mở rộng của chúng trong R2C ; - Đề xuất 03 hệ mật trên các vành đa thức chẵn (RISKE, QRHE và IPKE); - Đề xuất 03 hệ mật trên vành đa thức chẵn kết hợp với một số vành đa thức đặc biệt khác (E-RISKE, DTRU và HpNE).
4 Về ý nghĩa thực tiễn, các hệ mật được đề xuất trong luận án ngoài độ an toàn ngữ nghĩa, còn có độ phức tạp tính toán thấp và đòi hỏi ít tài nguyên tính toán do đó có thể được xem xét triển khai trong các thiết bị có tài nguyên tính toán hạn chế trong môi trường IoT. Nội dung của luận án được trình bày theo cấu trúc sau: - “Chương 1: Tổng quan về mật mã và các hệ mật dựa trên vành đa thức”: Nội dung chính của chương này là chỉ ra các hạn chế của các hệ mật dựa trên vành đa thức hiện có và đánh giá các tiềm năng ứng dụng của vành đa thức chẵn R2n trong mật mã. - “Chương 2: Vành đa thức chẵn”: Giới thiệu các kết quả toán học về vành đa thức chẵn R2n và một số vành đặc biệt làm nền tảng cho các hệ mật ở chương sau. - “Chương 3: Các hệ mật dựa trên vành đa thức chẵn”: Trình bày 03 hệ mật QRHE, IPKE và RISKE) trực tiếp dựa trên lớp vành đa thức chẵn R2n được công bố lần lượt trong các công trình [J1], [J3] và [C2] của nghiên cứu sinh. - “Chương 4: Các hệ mật dựa trên vành đa thức chẵn kết hợp với các vành đa thức khác”: Trình bày 03 hệ mật hoạt động trên vành đa thức chẵn kết hợp với một số loại vành loại vành đa thức khác được công bố lần lượt trong các công trình [J2], [C1] và [C3] của nghiên cứu sinh. - “Kết luận”: Tổng hợp đánh giá các kết quả đạt được của luận án đồng thời xác định các hướng nghiên cứu tiếp theo.
5 CHƯƠNG 1. TỔNG QUAN VỀ MẬT MÃ VÀ CÁC HỆ MẬT DỰA TRÊN VÀNH ĐA THỨC 1.1. MỞ ĐẦU CHƯƠNG Trong chương này, tình hình nghiên cứu về các hệ mật dựa trên các loại vành đa thức và vành đa thức chẵn sẽ được tóm tắt trong mục 1.2. Dựa trên các phân tích đó, mục 1.3 sẽ đưa ra các vấn đề mở và tiềm năng ứng dụng vành đa thức chẵn trong mật mã. 1.2. CÁC HỆ MẬT DỰA TRÊN VÀNH ĐA THỨC 1.2.1. Các hệ mật khoá bí mật dựa trên vành đa thức Trên thế giới, trong các kỹ thuật mật mã khóa bí mật, các phép toán hầu hết đều được thực hiện dựa trên các kỹ thuật thay thế và hoán vị trên các trường nhị phân (2) với các hệ mật tiêu biểu như DES hay OTP. Điều này là do các phép mã hóa và giải mã trong (2) đều dựa trên phép tính XOR đơn giản và dễ thực thi bằng cả phần cứng lẫn phần mềm. Trong khi đó các vành đa thức Rn  Z 2 [x] ( x n  1) chủ yếu được ứng dụng trong mã sửa sai. Chỉ từ năm 2002, tại Việt Nam, lớp các vành chẵn tuyệt đối Rn | n  2k , ký hiệu là R2k mới được sử dụng để xây dựng một số hệ mật khóa bí mật và hàm băm. 1.2.2. Các hệ mật khoá công khai dựa trên vành đa thức Tại Việt Nam, hệ mật khóa công khai đầu tiên dựa vành đa thức Rn được đưa ra năm 2005 thực chất là một biến thể của hệ mật Mc.Eliece, trong đó mã Goppa được thay thế bằng một mã cyclic cục bộ kết hợp với một mã kiểm tra chẵn. Ở nước ngoài, việc sử dụng các vành đa thức Rn,q  Z q [x] ( x n  1) để xây dựng các hệ mật khóa công khai được
6 khởi xướng từ những năm 1995 khi hệ mật NTRU lần đầu tiên được giới thiệu tại Crypto’96. NTRU có nhiều biến thể trên các cấu trúc đại số khác nhau nhưng đáng chú ý là hai biến thể hoạt động trên các vành đa thức là CTRU hoạt động trên các vành Rn và pNE trên vành Rn,q , n  2k . 1.3. CÁC VẤN ĐỀ MỞ VÀ TIỀM NĂNG ỨNG DỤNG CỦA VÀNH ĐA THỨC CHẴN TRONG MẬT MÃ 1.3.1. Các vấn đề chung với các hệ mật trên vành đa thức Qua các phân tích nêu trên có thể thấy ứng dụng vành đa thức Rn nói chung và vành đa thức chẵn R2n nói riêng trong mật mã còn nhiều hạn chế. Cụ thể là: i. Mới chỉ có các vành đa thức chẵn tuyệt đối R2k được sử dụng để xây dựng các hệ mật; ii. Chưa có các hệ mật có độ an toàn ngữ nghĩa dựa trên các vành đa thức R2n (trừ hệ mật pNE); iii. Các phần tử thặng dư bậc hai và lớp các phần tử liên hợp của chúng trên vành đa thức chẵn R2n hoàn toàn chưa được sử dụng trong mật mã (mới chỉ được ứng dụng trong mã sửa sai); iv. Hầu hết các hệ mật khóa công khai dựa trên các bài toán khó truyền thống hiện nay có hiệu năng tính toán không cao; v. Các hệ mật dựa trên vành đa thức Rn,q điển hình như NTRU có hiệu năng tính toán tốt nhưng vẫn chưa thực sự phù hợp cho các hệ thống có tài nguyên tính toán hạn chế vì khóa và hệ số mở rộng bản tin vẫn khá lớn.
7 1.3.2. Các tiềm năng ứng dụng của vành đa thức chẵn Các vành đa thức nói chung và vành đa thức chẵn R2n nói riêng có một số đặc điểm phù hợp với các ứng dụng trong mật mã, cụ thể là: i. Trong Rn , các phép cộng và nhân đa thức đều chỉ có độ phức tạp tính toán thấp lần lượt là O( n) hoặc O(n 2 ) . ii. Trong các vành đa thức chẵn R2n , có 2 n thặng dư bậc hai, mỗi thặng dư bậc hai đó lại có đến 2 n căn bậc hai, hay còn gọi là các phần tử liên hợp. Nếu biết một căn bậc hai sẽ tính được thặng dư bậc hai tương ứng nhưng điều ngược lại sẽ phải thử 2 n phương án. Đặc điểm này hoàn toàn có thể khai thác để xây dựng các hệ mật; iii. Trong các vành chẵn R2n luôn tồn tại các phần tử khả nghịch bên cạnh những phần tử không khả nghịch. Nếu xác định được các thuật toán mật mã phù hợp, các phần tử khả nghịch sẽ chính là khóa để giải mã thông tin tương tự như trường hợp của hệ mật NTRU. 1.4. KẾT LUẬN CHƯƠNG Qua các phân tích trên có thể thấy vành đa thức chẵn R2n nói riêng và vành đa thức nói chung vẫn còn nhiều tiềm năng có thể khai thác cho các ứng dụng mật mã. Trong chương sau, các kết quả toán học về vành R2n sẽ được phân tích chi tiết hơn làm cơ sở xây dựng các hệ mật trên nền tảng toán học này.
8 CHƯƠNG 2. VÀNH ĐA THỨC CHẴN 2.1. MỞ ĐẦU CHƯƠNG Trong chương này, một số kết quả toán học mới về vành đa thức chẵn R2n và một số lớp vành đặc biệt như vành chẵn tuyệt đối R2k và vành chỉ có hai lớp kề cyclic R2C sẽ được mô tả làm tiền đề cho các hệ mật ở chương sau. Các kết quả này được tổng hợp từ các nội dung nghiên cứu về cơ sở toán học trong toàn bộ 6 công trình đã công bố của nghiên cứu sinh. 2.2. VÀNH ĐA THỨC CHẴN, CÁC THẶNG DƯ BẬC HAI VÀ CÁC PHẦN TỬ LIÊN HỢP  n 1 Bổ đề 2-1: Trong R2n , nếu l  lx i 0 i i là căn bậc hai chính của f 2  2 n 1 với f  i 0 f i x i , thì li  ( fi  fi  n ) mod 2 . Bổ đề này cho thấy độ phức tạp của phép khai căn chỉ là O( n) tương đương với phép XOR. Phép khai căn này sẽ được sử dụng trong thuật toán mã hóa của hệ mật QRHE (mục 3.3). Bổ đề 2-2: Trong R2n , đa thức k   tU x t trong biểu thức g  (1  x n )  k  f (2.1) có các hệ số ki được xác định bởi ki  f i  n ,0  i  n  1 , trong đó f i  2 n 1 là các hệ số của đa thức f  i 0 fi xi . Bổ đề này cho phép xác định các phần tử liên hơp của một thặng dư bậc hai là bình phương của một đa thức bất kỳ trong vành đa thức chẵn. Công thức này sẽ được sử dụng trong thủ tục tạo khóa của hệ mật QRHE (mục 3.3).
9 2.3. VÀNH ĐA THỨC CHẴN TUYỆT ĐỐI R2k Định lý 2-1: Mọi đa thức f  R2k là khả nghịch khi và chỉ khi f có trọng số lẻ. Bổ đề này chứng minh rằng R2k là một vành đa thức đặc biệt, trong đó một nửa số phần tử của vành là khả nghịch và mọi phần tử này đều có thể sử dụng làm khóa bí mật cho các hệ mật. Tập các phần tử khả nghịch này sẽ được sử dụng làm khóa cho các hệ mật RISKE (mục 3.2), IPKE (mục 3.4) và DTRU (mục 4.2). Thuật toán 2-1: Thuật toán tính nghịch đảo g của một đa thức f khả nghịch trong R2k . VÀO: Đa thức f  R2k . RA: Đa thức g  R2k , g  f  1 . THUẬT TOÁN: g  f ; a  f 2; for i  1 to k  1 { if g  f  1 exit; g  g  a ; a  a 2 ; }. Thuật toán này có số bước lặp tối đa là (k  1) . 2.4. NGHỊCH ĐẢO MỞ RỘNG TRONG Rn VỚI n LẺ Định nghĩa 2-1: Trong Rn với n lẻ, một đa thức f được gọi là “khả nghịch mở rộng” nếu tồn tại một đa thức g  Rn thỏa mãn g  f  e0 n  1 và g được gọi là nghịch đảo mở rộng của f . Trong đó e0n là lũy đẳng nuốt của vành.
10 Định lý 2-2: Trong Rn với n lẻ, giả sử k là nghịch đảo mở rộng của , nếu biết c  m  và w(m) , ta có thể tính được m  w(m) mod 2.e0 n  k  c . (2.2) Với bổ đề này, ta có thể sử dụng một phần tử nghịch đảo mở rộng làm khóa bí mật vẫn giải mã được m từ c  m  k . Công thức này sẽ được sử dụng trong thủ tục giải mã của hệ mật E-RISKE (mục 4.3). 2.5. VÀNH ĐA THỨC CHỈ CÓ HAI LỚP KỀ CYCLIC R2C Định lý 2-3: Trong Rn , n  N 2C , mọi đa thức f là khả nghịch khi và chỉ khi f có trọng số lẻ và, hệ quả là K 2C , tỉ lệ giữa số phần tử khả nghịch trên tổng số đa thức trong R2C , đạt cực đại. Bổ đề này chứng minh rằng R2C là một vành đa thức đặc biệt, trong đó một nửa số phần tử của vành là khả nghịch và các phần tử này có thể sử dụng làm khóa bí mật cho các hệ mật. Hệ quả của bổ đề này là tất cả các phần tử có trọng số chẵn của vành R2C đều là các phần tử khả nghịch mở rộng. Đây cũng là cơ sở để xây dựng hệ mật E- RISKE (mục 4.3). 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 ( R2k , R2C ) 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-1, Định lý 2-3) 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 R2k (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).
11 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 R2n 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-1). 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 R2C , một cải tiến của hệ mật RISKE vốn chỉ hoạt động trên R2k . 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 R2n được nghiên cứu sinh xây dựng (Bổ đề 2-1, Bổ đề 2-2) là nền tảng quan trọng để đề xuất hệ mật lai ghép QRHE trong mục 3.3.
12 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 R2n bao gồm 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. Các hệ mật được mô tả tường minh từ ý tưởng xây dựng cho đến các thuật toán (tạo khóa, mã hóa và giải mã) cũng như được đánh giá về hiệu năng và độ an toàn với một số tấn công phổ biến. 3.2. HỆ MẬT KHÓA BÍ MẬT RISKE 3.2.1. Giới thiệu Theo Định lý 2-1, tất cả các đa thức có trọng số lẻ trong vành đa thức chẵn tuyệt đối R2k là khả nghịch. Ý tưởng ở đây là, nếu dùng một phần tử khả nghịch ngẫu nhiên làm khóa bí mật thì không gian khóa sẽ đủ lớn để kẻ tấn công không thể vét cạn khóa với hệ mật này. Bên cạnh đó, nếu thuật toán mã hóa chỉ sử dụng phép nhân đa thức thì hệ mật này sẽ có độ phức tạp tính toán chỉ là O(n 2 ) . Để 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 Rn , n  2k và một số nguyên N  2k để xác định độ dài khóa bí mật. 3.2.2. Thủ tục tạo khóa Với  {I n | 0  deg s  N  1} , 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 s  N  1 ta có thể biểu diễn s bằng N bit. Điều kiện deg s  0 để đảm bảo không thể dùng s  1 làm khóa bí mật trong RISKE. Hệ quả là, kích thước không gian khóa  2 N 1  1 .
13 3.2.3. Thủ tục mã hóa Mỗi phiên mã hóa n  1 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 M   w(m)  1 mod 2.x n 1  m sau đó tính n bit bản mã c  M  s. 3.2.4. Thủ tục giải mã Để giải mã n bit bản mã c , đầu tiên Bob tính n bit M  c  s 1 trong đó s 1 là nghịch đảo của s trong R2k tính bằng Thuật toán 2-1. Tiếp đó Bob khôi phục (n  1) bit bản rõ m  M n1.x n1  M với M n 1 là hệ số ứng với đơn thức x n 1 trong biểu diễn đa thức của M . 3.2.5. Phân tích độ an toàn lý thuyết của RISKE 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 N  1 xác suất để đoán đúng khóa là 1 / (2 N  1) . Đâ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à  2n1 còn lớn hơn cả độ an toàn khóa. Ngoài ra, RISKE còn có độ an toàn ngữ nghĩa IND-CPA (được chứng minh chi tiết trong định lý 3-2 của luận án). 3.2.6. 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 R2k với độ phức tạp tính toán
14 (n 2 ) . 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. 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.3. HỆ MẬT LAI GHÉP QRHE 3.3.1. Giới thiệu Mọi đa thức trong R2n , tương ứng với mọi bản tin 2n bit, luôn có thể biểu diễn dưới dạng m  (1  x n )  k  l trong đó, l  m2 và k  tU x t đều là các đa thức bậc tối đa (n  1) và được biểu diễn bởi các chuỗi n bit. Ý tưởng chính ở đây là, nếu coi k là một khóa bí mật và che giấu khóa này bằng một hệ mật khóa công khai nào đó theo mô hình KEM/DEM thì l  (1  x n )  k  m là một bản mã mà nếu không biết k sẽ không dễ phát hiện ra m từ l vì có đến 2 n phương án phải thử sai. 3.3.2. Sơ đồ hệ mật lai ghép QRHE Sơ đồ hệ mật lai ghép QRHE (Quadratic Residue Hybrid Encryption scheme) được mô tả chi tiết trong Hình 3-1.
15 Thám Alice mã Bob mi c1,i mi mi2 c1,i  ki  (1  x n ) c2,i x t KEM KEM ki tU ki DEM DEM Hình 3-1: Sơ đồ hệ mật QRHE 3.3.3. Thủ tục tạo khóa Với 2n bit bản rõ mi , dựa trên Bổ đề 2-2, Alice sẽ tính n bit khóa bí mật ki với kij  mi ( j  n ) . Khóa bí mật này sau đó sẽ được mã hóa bằng một hệ mật khóa công khai nào đó (phần KEM), ví dụ như hệ mật RSA để tạo từ mã c2,i . Kích thước của c2,i còn phụ thuộc vào hệ mật khóa công khai được chọn. 3.3.4. Thủ tục mã hóa Bằng Bổ đề 2-1, Alice sẽ xác định được các hệ số của bản mã c1,i với c1,ij  (mij  mi ( j  n) ) mod 2 | 0  j  n  1 . Tiếp đó Alice gửi cặp bản mã c1,i và c2,i gửi tới Bob. 3.3.5. Thủ tục giải mã Khi nhận được cặp bản mã (c1,i , c2,i ) , Bob sẽ: 1) Sử dụng thuật toán giải mã của phần KEM tính ki từ c2,i ; 2) Sử dụng ki để tính mi từ c1,i với
16 mij  (c1,ij  kij ) mod 2 | 0  j  n  1 mij  ki ( j n ) | n  j  2n  1. 3.3.6. Phân tích độ an toàn lý thuyết của QRHE Với độ an toàn khóa  2n , xác suất để kẻ tấn công đoán đúng khóa là 2  n là một hàm không đáng kể của biến n nên có thể coi là an toàn với tấn công này. Trên thực tế cần chọn n  1024 và cỡ khoảng 4096 (tương ứng với độ dài bit của giá trị modulus được khuyến nghị của hệ mật RSA trên thực tế. 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 QRHE, độ an toàn bản rõ còn lớn gấp đôi độ an toàn khóa. Để tránh được các tấn công EAV và CPA, cần lựa chọn KEM là các hệ mật xác suất, ví dụ OAEP-RSA. Ngoài ra, để khắc phục nhược điểm này, có thể sử dụng QRHE ở chế độ CBC. 3.3.7. Phân tích hiệu năng lý thuyết của QRHE Các thuật toán tạo khóa, mã hóa và giải mã của QRHE đều chỉ là các phép cộng đa thức trong R2n với độ phức tạp tính toán O ( n) dễ dàng thực hiện bằng phần cứng và phần mềm. 3.4. HỆ MẬT KHÓA CÔNG KHAI IPKE 3.4.1. Giới thiệu Việc sử dụng các phần tử khả nghịch trên vành Rn,q trong mật mã khóa công khai đã được hiện thực hóa với hệ mật NTRU. Tuy nhiên, NTRU phải lưu tới hai khóa bí mật, hệ số mở rộng bản tin trong khá cao (khoảng từ 3 đến 5) và chưa có độ an toàn ngữ nghĩa. Vấn đề đặt ra là có thể xây dựng một hệ mật khóa công khai trên vành đa thức chẵn để khắc phục những hạn chế này.
17 Quay trở lại với RISKE, hệ mật này sử dụng một khóa bí mật s khả nghịch nào đó trong vành đa thức R2k để che dấu bản rõ M bằng bản mã c  M  s và khôi phục lại M  s 1  c với s 1 là nghịch đảo của s . Trong trường hợp s không khả nghịch sẽ không thể tìm M một cách dễ dàng bằng cách tính M  s 1  c . Ý tưởng, ở đây là thay vì chọn s là một khóa khả nghịch và giữ bí mật, liệu có thể sử dụng một đa thức không khả nghịch h trong R2k làm khóa công khai để che dấu bản rõ bằng phép nhân đa thức c  h  M mà vẫn giải mã được bản rõ M nếu biết một cửa sập bí mật nào đó. Với ý tưởng như vậy, trong mục này, nghiên cứu sinh sẽ đề xuất một phương pháp xây dựng hàm cửa sập dựa trên các phần tử khả nghịch trong R2k qua đó đề xuất một hệ mật khóa công khai có tên là IPKE có thủ tục tính toán đơn giản, chỉ sử dụng một khóa bí mật có kích thước nhỏ, hệ số mở rộng bản tin thấp và có độ an toàn IND-CPA. Để xây dựng hệ mật, Alice và Bob thống nhất chọn một số nguyên dương k xác định vành đa thức nền tảng và một số nguyên dương p  2k xác định độ dài bản rõ m . 3.4.2. Thủ tục tạo khóa Để tạo khóa, Bob chọn ngẫu nhiên hai đa thức khác zero k 1 s1 , s2  R2k 1 để tính s  s1  x 2  s2 . Tiếp đó, Bob sử dụng Thuật toán 2-1 để tính 2k bit khóa bí mật  với đầu vào s . Cuối cùng Bob tính 2 k bit khóa công khai h  s  ( x p  1) và gửi h tới Alice. Lưu ý rằng, do khóa s cần phải thay đổi theo phiên nên h cũng cần thay đổi theo từng phiên để đảm bảo khả năng chống tấn công CPA.
18 3.4.3. Thủ tục mã hóa Để mã hóa ( p  1) bit bản rõ m , Alice đầu tiên tính p bit M   w(m)  1 mod 2.x p 1  m sau đó tính p bit bản mã c  M  h và gửi c tới Bob. 3.4.4. Thủ tục giải mã Khi nhận được bản mã c , Bob dùng khóa bí mật  tính d    c và khôi phục p bit M bằng cách tính M   i 0 di x i p 1 với di , i  [0, p  1] là các hệ số của đa thức d trong biểu diễn  2k 1 d i 0 di xi . Cuối cùng, từ d, Bob tính ( p  1) bit bản rõ p 1 m  M p 1.x  M với M p 1 là hệ số ứng với đơn thức x p 1 trong biểu diễn đa thức của M . 3.4.5. Phân tích độ an toàn lý thuyết của IPKE Kẻ tấn công nhận được c có thể thử vét cạn 2 p bản rõ m k 1 k 1 cho đến khi đạt được m  h  c hoặc thử vét cạn S 2k  22  22 k 1 khóa bí mật  cho đến khi   h  1  x 2 . Với k  11 và p  1023 thì độ an toàn khóa và độ an toàn bản rõ của IPKE lần lượt là 21023 và (22047  21024 ) xác suất để kẻ tấn công vét cạn khóa và bản tin là không đáng kể và có thể coi IPKE là an toàn với các tấn công kiểu này. IPKE là hệ mật có độ an toàn IND-CPA nếu s được chọn ngẫu nhiên phân bố đều trong S 2k (được chứng minh chi tiết trong định lý 3-3 của luận án).