Nghiên cứu một số hệ mật Lattice trong họ mã hóa đồng cấu đầy đủ

Bài viết trình bày nghiên cứu một số hệ mật Lattice, đó là hệ mật khóa công khai dựa trên vấn đề học với lỗi (LWE) và hệ mật khóa công khai GGH. Tiếp theo, báo cáo đê xuất giải pháp ứng dụng các hệ mật này trong việc đảm bảo an toàn của văn bản và đưa ra đánh giá, so sánh về sự an toàn của hai hệ mật này.
Nội dung trích xuất từ tài liệu:
Nghiên cứu một số hệ mật Lattice trong họ mã hóa đồng cấu đầy đủ Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), TP. HCM, ngày 23-24/12/2021 DOI: 10.15625/vap.2021.00104 NGHIÊN CỨU MỘT SỐ HỆ MẬT LATTICE TRONG HỌ MÃ HÓA ĐỒNG CẤU ĐẦY ĐỦ Khuất Thanh Sơn1, Nguyễn Trường Thắng1, Lê Phê Đô2, Bùi Trọng A Đam2 1 Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam 2 Khoa Công nghệ thông tin, Đại học Công nghệ - Đại học Quốc gia Hà Nội ktson@ioit.ac.vn, ntthang@ioit.ac.vn, dolp@vnu.edu.vn, adambui08@gmail.com TÓM TẮT: Sự phát triển mạnh mẽ của internet cùng các giao dịch trực tuyến trên internet từ những hình thức sơ khai đến những giao dịch phức tạp thể hiện qua các hệ thống Chính phủ điện tử, thương mại điện tử ngày càng phát triển mạnh mẽ trên toàn cầu. Internet có những kỹ thuật cho phép mọi người truy cập, khai thác và chia sẻ thông tin với nhau. Nhưng nó cũng là nguy cơ chính dẫn đến thông tin của chúng ta bị hư hỏng hay bị phá hủy hoàn toàn. Cùng với đó sự phát triển của các thiết bị tính toán khiến cho độ an toàn của các hệ mã hóa nguyên thủy bị báo động. Trong bài báo này, trước hết chúng tôi sẽ nghiên cứu một số hệ mật Lattice, đó là hệ mật khóa công khai dựa trên vấn đề học với lỗi (LWE) và hệ mật khóa công khai GGH. Tiếp theo, báo cáo đê xuất giải pháp ứng dụng các hệ mật này trong việc đảm bảo an toàn của văn bản và đưa ra đánh giá, so sánh về sự an toàn của hai hệ mật này. Từ khóa: Hệ mật Lattice, mã hóa đồng cấu, LWE, GGH. I. GIỚI THIỆU Điện toán lượng tử [1] là một phương pháp tính toán mới, nó cho phép tìm kiếm rất nhanh cũng như dễ dàng giải các bài toán khó dựa trên độ phức tạp tính toán như phân tích các số nguyên lớn, tính logarit rời rạc trên trường hữu hạn,... Điện toán lượng tử xuất hiện sẽ là nguy cơ đối với độ an toàn của các hệ mật mã nguyên thủy dựa trên độ phức tạp tính toán, như RSA, ECC,... Mặc dù trên thế giới chưa có các cuộc tấn công thám mã lượng tử, nhưng một số quốc gia đã theo dõi những tiến bộ trong điện toán lượng tử để cải tiến các tiêu chuẩn mật mã hiện tại bằng việc xác định các thuật toán mật mã - kháng lượng tử, xây dựng các chiến lược thực hiện để đạt được sự đồng thuận rộng rãi về việc sử dụng trong thực tế. Các hệ mật thuộc nhóm hệ mật Lattice - mạng tinh thể đã và đang nhận được rất nhiều sự quan tâm và phát triển bởi các bài toán đặc trưng trên mạng tinh thể được đánh giá là đủ khó để chống lại tính toán lượng tử. Trong báo cáo này, chúng tôi nghiên cứu hai hệ mật ứng dụng của mạng tinh thể là hệ mật khóa công khai GGH và hệ mật khóa công khai LWE. Báo cáo tập trung trình bày tổng quan về công nghệ cốt lõi của hai hệ mật, cách triển khai mã hóa và giải mã, đánh giá độ mật, và cuối cùng là so sánh các ưu nhược điểm giữa hai hệ mật khi áp dụng vào việc đảm bảo an toàn bảo mật văn bản. Phần còn lại của bài báo được trình bày như sau: Phần II, tổng quan về hai hệ mã hóa; Phần III, trình bày mô tả mô hình đề xuất; Phần IV, phân tích kết quả thu được. Phần V kết luận và đề xuất hướng phát triển. II. TỔNG QUAN CÔNG NGHỆ A. LWE Trong công trình nghiên cứu của mình từ năm 2005, Regev [2] đã giới thiệu bài toán trường hợp trung bình được gọi là Bài toán học với lỗi (Learning with Errors (gọi tắt là LWE)). Kể từ đó, nó không chỉ xuất hiện như một bài toán trong họ các hệ mật Lattice để hỗ trợ một sơ đồ mã hóa mà còn cho thấy tính linh hoạt của nó cho phép hệ thống mật mã bảo mật được lựa chọn [3], sơ đồ mã hóa dựa trên danh tính và mã hóa đồng cấu đầy đủ [4]. Chúng tôi sẽ mô tả chi tiết LWE và phác thảo các đặc tính chính của nó, sau đó chúng tôi giới thiệu một hệ thống mật mã đơn giản dựa trên nó. LWE thuộc nhóm hệ mật Modular Lattice Problems, bài toán LWE yêu cầu ta tìm ra giá trị bí mật s ∈ ℤnq từ các phương trình tính xấp xỉ với s. Sau đây là một ví dụ về đầu vào bài toán [5]: 14s1 + 15s2 + 5s3 + 2s4 ≈ 8 (mod 17) 13s1 + 14s2 + 14s3 + 6s4 ≈ 16 (mod 17) 6s1 + 10s2 + 13s3 + 1s4 ≈ 3 (mod 17) 10s1 + 4s2 + 12s3 + 16s4 ≈ 12 (mod 17) Ý tưởng của bài toán LWE được xác định một cách rõ ràng. Chọn một tham số n ≥ 1, một số chia lấy dư q ≥ 2 và một giá trị lỗi X thuộc phân phối xác suất trên ℤq. As, ᵪ là giá trị thu được khi chọn véctơ a ∈ ℤnq một cách ngẫu nhiên, tiếp theo ta chọn e ∈ ℤq theo giá trị của ᵪ và đầu ra là cặp giá trị a và b = + e sau khi đã chia lấy dư với q. Một thuật toán giải được bài toán LWE với số chia lấy dư q, phân phối lỗi X nếu thuật toán đó có thể đưa ra một số lượng mẫu độc lập tùy ý từ As, X. Ta cũng có thể coi LWE là một bài toán tương đương với bài toán giải mã từ các mã tuyến tính ngẫu nhiên hoặc bài toán giải mã khoảng cách có giới hạn ngẫu nhiên trên họ hệ mật Lattice. Ngoài ra với trường hợp đặc biệt q = 2 thì LWE tương đương với bài toán nổi tiếng LPN (Learning parity with noise). Cụ thể về phân phối lỗi X trong trường hợp này có thể được thể hiện thông qua một tham số ε > 0 có thể gọi là xác suất lỗi. 568 NGHIÊN CỨU MỘT SỐ HỆ MẬT LATTICE TRONG HỌ MÃ HÓA ĐỒNG CÂU ĐẦY ĐỦ Định nghĩa Phân phối LWE: [6] Cho một véctơ s ∈ ℤqn, tạm coi là một khóa bí mật. Phân phối LWE As, X trên ℤqn x ℤq là một mẫu được tạo ra bằng cách chọn ngẫu nhiên a ∈ ℤqn, chọn e ← X, và đầu ra là (a, b = + e mod q) ∈ ℤqn x ℤq. Ý tưởng của bài toán LWE được xác định một cách rõ ràng. Chọn một tham số n ≥ 1, một số chia lấy dư q ≥ 2 và một giá trị lỗi X thuộc phân phối xác suất trên ℤq. As, ...