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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

27
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệ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.

Chủ đề:

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

Lưu

Nội dung Text: 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, X là giá trị thu được khi chọn véctơ a ∈ ℤqn một cách ngẫu nhiên, tiếp theo ta chọn e ∈ ℤq theo giá trị của X 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 mạng tinh thể. 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. Định nghĩa LPN (Learning parity with noise): [6] Cho 𝑒 > 0 và một tập hợp các phương trình sau: ≈e b1 mod 2 ≈e b2 mod 2… với ai đồng đều và độc lập trên toàn bộ ℤ2n và với mỗi bi được chọn sao cho bằng với với xác suất là 1 – e, tìm khóa bí mật s ∈ ℤ2n. Định nghĩa Tìm kiếm LWEn, q, X, m: Cho m mẫu độc lập {(ai, bi)}i=1m ∈ ℤqn x ℤq từ As, X, với s được chọn một cách ngẫu nhiên. Tìm s. Nói một cách đơn giản hơn là ta đang cố để tìm s ∈ ℤqn bằng cách giải hệ phương trình tuyến tính sau: = b – e1 mod q ... = b – em mod q với ai và mỗi ei ta có đầu ra là X. Ta coi véctơ lỗi e = (e1, e2, …en) là chưa biết nhưng xác suất phân bố rời rạc là một dữ liệu của bài toán. Định nghĩa Quyết định LWEn, q, X, m: [6] Cho một phân phối lỗi X trên ℤ mà m mẫu độc lập {(ai, bi)}i=1m ∈ ℤqn x ℤq, ở đó mỗi mẫu được phân phối theo hoặc là As, X và số s được chọn ngẫu nhiên s ∈ ℤqn hoặc phân phối đồng đều. Phân phối xác suất lỗi X được chọn như một phân phối thông thường được làm tròn đến số nguyên gần nhất của tiêu chuẩn lệch αq với α > 0. Số chia lấy dư q thường được gọi là đa thức trong n, việc chọn một số q có cả hai mặt lợi lẫn hại. Nếu chọn q là một hàm mũ thì nó sẽ gia tăng đáng kể kích thước giá trị đầu vào, đương nhiên ảnh hưởng hiệu quả của hệ mật. Lợi thế là độ khó của bài toán LWE được hiểu một cách rõ ràng hơn. Một cách để giải bài toán LWE là thông qua một thuật toán khả năng tối đa. Với các điều kiện tham số đầu vào được đảm bảo như ở trên thì không khó để có thể thấy sau O(n) phương trình thì tồn tại một giá trị của s sao cho xấp xỉ thỏa mãn các phương trình. Điều này dẫn đến một thuật toán chỉ chạy với O(n) mẫu và chạy trong thời gian là 2O(nlogn). Một cách khác là liên tục tìm kiếm mẫu cho tới khi tìm được mẫu có chưa n phương trình có dạng s1 ≈ … (với 1 cặp a, b trong đó a = (1, 0, 0,…)), từ đó ta có thể giải được giá trị của s1, từ đó ta lặp lại với mọi si. Xác suất để tìm được một mẫu thỏa mãn điều kiện như vậy là 1/qn, thuật toán sẽ yêu cầu với số lượng phương trình là 2O(nlogn) và thời gian chạy tương tự. Thuật toán của Blum, Kalai, and Wasserman được xem thuật toán tốt nhất để giải bài toán LWE tính đến thời điểm hiện tại. Thuật toán yêu cầu số lượng phương trình là 2O(n) và thời gian tương đương như vậy. Thuật toán dựa trên ý tưởng là tìm ra một tập hợp nhỏ S của các phương trình chứa 2O(n) phương trình (phân chia tọa độ n thành log n khối có kích thước n/logn của mỗi khối, ta xây dựng được S thông qua các va chạm giữa các khối). Bằng cách tính tổng các tọa độ này ta có thể khôi phục tọa độ đầu tiên của s và tương tự với tất cả tọa độ còn lại. Bất kỳ một thuật toán nào được cải tiến đều có khả năng dẫn đến đột phá trong thuật toán mạng. Có rất nhiều lý do khẳng định rằng bài toán Learning with Errors là khó. Đầu tiên, thuật toán để giải bài toán LWE chạy trên thời gian hàm mũ (kể cả với máy tính lượng tử xem ra cũng không giúp giải bài toán này trong thời gian đa thức). Thứ hai, bài toán LWE là một bản mở rộng của bài toán LPN bởi LPN là trường hợp đặc biệt của LWE khi n = 2. Trong khi bản thân bài toán LPN đang được rất nhiều người cho là khó để giải quyết. Hơn nữa bài toán LPN có thể được xây dựng dưới dạng vấn đề giải mã từ các mã nhị phân tuyến tính ngẫu nhiên, do đó bất kỳ thuật toán nào tiến bộ để giải bài toán LPN có thể dẫn đến một bước đột phá trong mã hóa mạng tinh thể. Thứ ba và cũng là quan trọng nhất, bài toán LWE được xây dựng dựa trên độ khó các giả định về trường hợp xấu nhất của Hệ mật Lattice với các bài toán khó như GapSVP (quyết định véctơ ngắn nhất thuộc mạng Lattice) và SIVP (những véctơ độc lập tuyến tính ngắn nhất thuộc mạng Lattice). Thậm chí với việc số chia lấy dư q là hàm mũ thì độ khó của LWE được xây dựng dựa trên các giả định về bài toán GapSVP là khó khi tính toán xấp xỉ trong nhân tố đa thức. Trong trường hợp số chia lấy dư q là đa thức (một điều rất thuận lợi cho việc cài đặt hệ mật), tất nhiên rằng độ khó của bài toán LWE ở một mức độ thấp hơn nhưng vẫn hoàn toàn đáng tin cậy. Cụ thể hơn, hoặc bài toán GapSVP là khó để tính toán xấp xỉ kể cả được
Khuất Thanh Sơn, Nguyễn Trường Thắng, Lê Phê Đô, Bùi Trọng A Đam 569 cung cấp gợi ý dưới dạng một cơ sở sinh ngắn, hoặc là GapSVP hoặc SIVP là khó khi tính toán xấp xỉ trong các nhân tố đa thức kể cả với máy tính lượng tử. Trong bài toán LWE có chứa một bài toán kép là SIS (viết tắt của Small Integer Solution). Bài toán SIS chúng ta cần tìm một tập hợp con của tập hợp các véctơ a1, a2, … ,an được chọn từ ℤqn sao cho có tổng chia cho số chia lấy dư q có giá trị bằng 0. Ta cũng thể coi SIS là bài toán tìm véctơ ngắn trong mạng tinh thể hoặc mã ngẫu nhiên. Bài toán SIS được sử dụng trong việc xây dựng “minicrypt”, chẳng hạn như hàm một chiều, hàm băm chống xung đột, lược đồ chữ ký số và sơ đồ nhận dạng. Trái lại LWE lại có ứng dụng trong hệ mật khóa công khai. Độ khó của bài toán SIS rất rõ ràng, đối với bất kỳ số chia lấy dư q nào là một đa thức nào đó trong n, việc giải bài toán SIS gần như là tiêu chuẩn cho trường hợp xấu nhất của mạng Lattice như SIVP, GapSVP. Hệ mật LWE yêu cầu một tham số số nguyên n (tham số bảo mật), m là số phương trình, q là số chia lấy dư, và một số thực 𝛼 > 0 (tham số gây nhiễu). Sự lựa chọn các tham số trên có ảnh hưởng trực tiếp đến tính bảo mật và tính đúng đắn của hệ mật. Ta cần chọn q là một số nguyên tố nằm giữa n2 và 2n2, m = 1,1(nlog q) và 𝛼 = 1 / (√𝑛 log2 n). B. GGH Hệ mật GGH [7] được công bố vào năm 1997 bởi Oded Goldreich, Shafi Goldwasser và Shai Halevi. Hệ mật GGH được thiết kế dựa trên độ khó khi giải bài toán tìm véctơ gần nhất thuộc mạng Lattice (CVP) [8]. Một mạng Lattice có rất nhiều các cơ sở, chúng ta luôn có cách để tìm được một cơ sở “tốt”, đặc biệt là một cơ sở có tính chất trực giao. Mặc dù vậy không phải bất kỳ mạng Lattice nào ta cũng có thể tìm được cơ sở trực giao, chính vì vậy ta cần có một cách nào để có thể xác định được một cơ sở thuộc mạng Lattice đủ tốt hay không. Một cơ sở đủ tốt có thể giúp việc giải bài toán liên quan mạng Lattice, hơn nữa kết quả sau khi giải bài toán cũng có chất lượng tốt. Hadamard Ratio là tỉ lệ để đánh giá việc một cơ sở có đủ tốt hay không. Định nghĩa Hadamard Ratio: [9] Cho một cơ sở B = {b1, b2,…, bn} và một mạng Lattice L với n chiều được sinh ra từ cơ sở B, Hadamard Ratio của cơ sở B được xác định qua công thức sau: det(𝐿) H(B) = ( )1/n ||b1||2 .||b2||2 … ||bn||2 trong đó ||b1||2 là độ dài véctơ b1. Hadamard Ratio có thể coi là như một độ đo tính trực giao của một ma trận [10], nó có giá trị nằm trong khoảng từ 0 đến 1. Một ma trận càng gần với trực giao thì Hadamard Ratio của nó càng gần với 1 và ngược lại. Khi ta nối các điểm trong một cơ sở thuộc mạng Lattice, một vùng được sinh ra giới hạn bởi các đường nối đó. Vùng đó được gọi là miền cơ bản. Định nghĩa 1: Cho một mạng Lattice L có n chiều và một cơ sở B thuộc mạng Lattice L. Miền cơ bản tương ứng với cơ sở B được thể hiện như sau: F(B) = {Br | 0 ≤ ri ≤ 1, (1 ≤ i ≤ n) } Ví dụ: Cho 2 cơ sở là B = {b1, b2} và A = {a1, a2}. Chúng ta xác định được miền cơ bản của hai cơ sở này. Dưới góc nhìn hình học thì hai vùng cơ bản là hai hình khác nhau nhưng khu vực mà chúng bao phủ thì là như nhau. Hình 1. Hai vùng cơ bản của hai cơ sở A và B [9] Từ đây ta có một mệnh đề rất quan trọng: Mệnh đề 1: Cho một mạng Lattice L ⊂ ℝn với n chiều với F là miền cơ bản của cơ sở B thuộc mạng Lattice L. Với mọi véctơ w ∈ ℝn thì luôn có: w = t + v (trong đó tồn tại duy nhất một véctơ t ∈ F và duy nhất một véctơ v ∈ L). Để có thể tìm được véctơ gần nhất, chúng tôi đã nghiên cứu về thuật toán Babai [11]: Cho một mạng Lattice L và cơ sở B sinh ra L, như vậy với mệnh đề 2.1.3 thì với mọi véctơ w ta luôn tìm được véctơ t ∈ F (miền cơ bản của B) và véctơ v ∈ L sao cho w = t + v. Từ đây ta có ý tưởng để giải bài toán tìm véctơ gần nhất (CVP) với véctơ w trong mạng Lattice L cho trước. Đó là thuật toán Babai, nó còn được biết đến với cái tên là The Nearest Plane Algorithm (Thuật toán chuyến bay gần nhất) được tìm ra bởi Babai vào năm 1986 [11]. Thuật toán Babai được phát biểu như sau [9]: Cho một mạng Lattice L ⊂ ℝn, một cơ sở B sinh ra L và một véctơ w ∈ ℝn nhưng ∉ L. Nếu cơ sở B tiệm cận đến tính trực giao thì véctơ v gần nhất với véctơ w và ∈ L được tìm ra như sau:
570 NGHIÊN CỨU MỘT SỐ HỆ MẬT LATTICE TRONG HỌ MÃ HÓA ĐỒNG CÂU ĐẦY ĐỦ Input: Một cơ sở B cho mạng tinh thể và một véctơ w ∈ ℝn Output: véctơ v gần nhất với véctơ w và ∈ L 1. Tính toán w = Br với r ∈ ℝn 2. Cho i chạy từ 1 cho đến n 3. Đặt zi ⃪[ri] 4. Trả về véctơ v gần nhất với véctơ w Trong thực tế nếu cơ sở B tiệm cận đến tính trực giao tức Hadamard Ratio của B xấp xỉ 1 thì thuật toán Babai đưa ra kết quả rất tốt, tức tìm chính xác được véctơ gần nhất. Đương nhiên nếu cơ sở B có Hadamard Ratio không đủ tốt thì việc tính toán dựa theo thuật toán Babai sẽ đưa ra kết quả sai bởi nó rất xa so với véctơ gần nhất chính xác của w. Việc lựa chọn được cơ sở B có tính trực giao cao có tính quyết định với kết quả mà ta nhận được khi áp dụng thuật toán Babai để tìm véctơ gần nhất (CVP). Trong phần tiếp theo chúng tôi sẽ sử dụng LWE và GGH trong việc mã hóa và giải mã và đánh giá việc hiệu quả của LWE và GGH, sau đó chúng tôi sẽ đề xuất một phương án mã hóa văn bản dựa trên hai hệ mật này. III. PHƯƠNG PHÁP ĐỀ XUẤT Trong phần này, chúng tôi trình bày quy trình làm việc chính dựa trên hai hệ mật vừa được phân tích ở trên và áp dụng vào phương pháp ký số điện tử. A. LWE Sinh khóa công khai và khóa bí mật cho LWE Khóa bí mật: Là véctơ s được chọn từ ℤqn. Khóa công khai: • Ta chọn A gồm m véctơ được chọn một cách ngẫu nhiên A = [a1, a2, …, am] với a1, a2, …, am là các số nguyên thuộc ℤqn. • Ta chọn e gồm m véctơ gồm các số nguyên đủ nhỏ được chọn một cách ngẫu nhiên. • Ta tính toán được B với B = As + e (mod q). Đến đây ta kết thúc quá trình sinh khóa công khai với cặp khóa công khai là (A, B). Quá trình mã hóa được triển khai như sau: Ta mã hóa đoạn văn bản muốn truyền đi thành một tập hợp của các số nguyên (véctơ), ví dụ như sử dụng bảng mã ASCII cho từng ký tự thuộc văn bản. Mỗi ký tự sau khi chuyển sang giá trị tương ứng trên bản mã ASCII sẽ được chuyển sang dạng nhị phân và lưu thành 8 bits. Cuối cùng ta chuyển bản tin truyền đi thành một chuỗi của nhiều dãy 8 bits và sẵn sàng cho quá trình mã hóa. Với mỗi bit từ bản tin truyền đi, ta chọn một mẫu từ khóa công khai A tạm gọi là Asample và một mẫu từ khóa công khai B tạm gọi là Bsample (mẫu là tập hợp con của A hoặc B). Ta tính toán được cặp giá trị u và v với: • u = ∑ 𝐴𝑠𝑎𝑚𝑝𝑙𝑒 (mod q) 𝑞 • v = ∑ 𝐵𝑠𝑎𝑚𝑝𝑙𝑒 + . m (với m là giá trị bit tương ứng) 2 Kết thúc quá trình mã hóa với đầu ra là mỗi cặp (u, v) tương ứng với mỗi bit. Tức với mỗi ký tự ta có đầu ra quá trình mã hóa là 8 cặp (u, v). Quá trình giải mã được thực hiện như sau: Ta nhận giá trị đầu ra của quá trình mã hóa là các cặp (u, v), giờ là lúc ta sử dụng khóa bí mật để giải mã. Ta tính toán thông qua một biến trung gian tạm gọi là Dec: Dec = v – su (mod q) Với mỗi giá trị Dec, ta so sánh Dec với q/2: • Dec < q/2 thì đồng nghĩa với việc bit tương ứng trong bản rõ là 0. • Ngược lại, Dec > q/2 thì bit tương ứng trong bản rõ là 1. Lặp lại như vậy với từng cặp (u, v) đến cuối ta nhận được kết quả là một chuỗi các giá trị 8 bits. Với mỗi 8 bits ta chuyển ngược lại sang giá trị số nguyên của chúng rồi chuyển tiếp sang giá trị ký tự theo bảng mã ASCII. Kết thúc quá trình giải mã ta nhận được bản rõ. Xét về tính đúng đắn của hệ mật LWE: nếu không tồn tại lỗi trong mẫu thiết kế LWE thì quá trình giải mã luôn luôn có kết quả chính xác. Quá trình giải mã chỉ xảy ra lỗi khi và chỉ khi tổng các điều kiện lỗi trên toàn bộ S lớn hơn q/4. Ta đang tính tổng m số hạng sai số thông thường, mỗi số hạng có độ lệch chuẩn là 𝛼q nên độ lệch chuẩn tối đa là √m (𝛼q) < q/log n ; với một phép tính tiêu chuẩn thì ta thấy xác suất để một biến thông thường lớn hơn q/4 là không đáng kể.
Khuất Thanh Sơn, Nguyễn Trường Thắng, Lê Phê Đô, Bùi Trọng A Đam 571 B. GGH Như đã giới thiệu ở Phần II, chúng tôi cần tìm ra hai cơ sở sinh ra mạng Lattice L để làm khóa bí mật và khóa công khai. Cơ sở có tính trực giao cao sẽ là khóa bí mật và ngược lại cơ sở có tính trực giao thấp sẽ là khóa công khai. Hadamard Ratio sẽ là công cụ để đánh giá tính trực giao của cơ sở. Ta chạy chương trình sinh ra ma trận có số chiều tương đương với tập tin mà ta cần truyền đi, tạm kí hiệu là n. Mỗi lần sinh ra một ma trận ta lại tính toán Hadamard Ratio của ma trận đó, nếu đủ tốt ta sẽ dừng lại. Tất nhiên việc sinh ra ma trận trực giao (H = 1) là điều không nhất thiết phải có bởi nhiều mạng Lattice chưa chắc đã chứa trong mình một cơ sở trực giao. Chúng tôi khuyến nghị H nên > 0,9 để đảm bảo cho quá trình giải mã nhận được kết quả chính xác. Kết thúc quá trình ta có được một ma trận với H > 0,9, tạm gọi là ma trận V, nó được chọn làm khóa bí mật. Từ khóa bí mật ta tìm khóa công khai bằng cách nhân nó với một ma trận đơn phương. Việc ta cần làm tiếp theo là chạy chương trình sinh ra ma trận đơn phương. Với mỗi một ma trận đơn phương được sinh ra, ta lấy nó nhân với khóa bí mật thu được một ma trận khác. Ta lại tính Hadamard Ratio của nó, do khóa công khai có tính trực giao càng thấp càng tốt nên chúng tôi khuyến nghị H < 0,001. Khi ta tìm được ma trận có H đủ nhỏ, tạm gọi là ma trận W, nó được chọn làm khóa công khai. Mấu chốt là việc sinh ra liên tục ma trận đơn phương. Ta hiểu rằng ma trận đơn phương tạm gọi là U là ma trận có det(U) = ± 1, vậy cách làm là gì? Liệu có phải là cứ sinh liên tục ma trận M với n chiều rồi tính det(M), đến khi nào thỏa mãn det(U) = ± 1 thì dừng lại. Đúng, cách làm này không sai nhưng với bản tin bí mật đủ dài để cần một ma trận đơn phương với n = 100 thì việc sinh ra ma trận U dần trở thành việc may rủi ngay cả với các máy tính có cấu hình tốt để việc tính toán đủ nhanh, thậm chí chưa kể đến khi sinh ra U rồi nhưng chưa chắc W đã thỏa mãn H < 0,001. Chúng tôi đã từng thử với Google Colab (là dịch vụ đám mây miễn phí, có cung cấp GPU để triển khai chương trình viết bằng Python) để sinh ma trận M với n = 100 như trên và với 16 tiếng vẫn chưa ra kết quả. Vậy cách làm đúng đắn là gì? Chúng ta cần sinh ra hai ma trận thành phần của ma trận đơn phương, tạm gọi là ma trận tam giác trên và ma trận tam giác dưới. Ma trận tam giác trên thì tất cả các giá trị dưới đường chéo đều là 0, tương tự vậy với tam giác ma trận dưới. Sau đó ta nhân hai ma trận này với nhau thì sẽ thu được một ma trận đơn phương. Với ma trận đơn phương có n = 100 thì thời gian để sinh ra ma trận U chỉ là dưới 1s với Google Colab. Như vậy việc tạo khóa công khai có H thỏa mãn H < 0.001 là hoàn toàn khả thi kể cả với n lớn. Kết thúc quá trình sinh khóa ta có được khóa bí mật V, khóa công khai W và ma trận đơn phương U. Quá trình mã hóa trên hệ mật GGH được tiến hành như sau: Bản tin truyền đi trước khi vào quá trình mã hóa cần được mã hóa trước thành một ma trận 1 chiều với n phần tử số nguyên tương ứng với số ký tự của bản mã. Ta cần làm vậy để trong quá trình mã hóa ta có các phép tính toán với ma trận. Ta bắt đầu quá trình mã hóa với khóa công khai W đã được sinh ra. Một véctơ r được chọn ngẫu nhiên để làm nhiễu loạn, còn được gọi là khóa tạm thời. Véctơ r được chọn sao cho chiều dài của r ngắn hơn ½ chiều dài khoảng cách nhỏ nhất của 2 điểm bất kỳ thuộc mạng tinh thể L. Bởi khi đó chúng ta chắc chắn được việc đó là bản tin sau khi mã hóa, tạm gọi là bản mã e sẽ không thuộc mạng Lattice L. e = Wm + r Ta cũng có thể dùng hash của bản rõ để gửi đi vì hash là mã hóa một chiều, từ bản hash ta không thể khôi phục về bản rõ. Việc gửi bản hash của bản rõ có tác dụng kiểm tra kết quả sau quá trình giải mã. Như vậy kết thúc quá trình mã hóa. Quá trình giải mã: Ta nhận được bản mã e, khóa công khai W và đặc biệt là khóa bí mật V. Để giải mã ta sử dụng khóa bí mật và tìm véctơ gần nhất tạm gọi là véctơ v với bản mã e bằng thuật toán Babai. Công đoạn cuối cùng sau khi đã có véctơ v, ta tính toán theo công thức sau thì bản mã sẽ được giải mã: m = W-1v Sau đó ta có thể hash và kiểm tra giá trị hash nhận được với giá trị hash nhận được từ quá trình mã hóa. Đánh giá: Một bên thứ ba muốn đánh cắp nội dung bản rõ được truyền đi nhưng không biết khóa bí mật V do đã được giữ kín. Bên thứ ba muốn giải mã bản mã e thông qua khóa công khai W. Nhưng như ta đã biết khóa công khai W là khóa có tính trực giao rất thấp so với khóa bí mật V, do đó nếu dùng khóa công khai W và áp dụng thuật toán Babai để tìm véctơ gần nhất v thì kết quả sẽ rất xa so với kết quả chính xác. Từ đó mà kết quả sau quá trình giải mã đương nhiên là không chính xác so với bản rõ được truyền đi. Do vậy đương nhiên bản rõ được truyền đi một cách an toàn. Để hoàn thiện độ an toàn cho quá trình truyền bản rõ, việc lựa chọn véctơ gây nhiễu hay còn gọi là khóa tạm thời được diễn ra. Véctơ r không được phép quá nhỏ bởi nếu quá nhỏ thì việc giải mã khi sử dụng khóa công khai W sẽ không gặp thêm khó khăn. Tương tự nếu quá lớn thì việc giải mã khi sử dụng khóa bí mật V sẽ có kết quả không chính xác. IV. THỰC NGHIỆM VÀ KẾT QUẢ Phương pháp đề xuất của chúng tôi đã được thực hiện trên hai hệ thống: Google Colab và máy tính cá nhân. Đối với Google Colab thì kết quả cho ra trong cả hai quá trình mã hóa và giải mã của hệ mật LWE tốt hơn nhiều so với việc sử dụng GGH. Lý do chúng tôi cũng đã đưa ra trong Phần III do GGH phải sinh liên tục ma trận đơn phương, điều này liên tục diễn ra cho đến khi Hadamard Ratio của Public key < 0,0001. Còn đối với máy tính cá nhân, chúng tôi sử dụng máy tính với cấu hình Intel core I5-7200U, RAM 8Gb, SSD 256Gb, chạy hệ điều hành Ubuntu 20.04 64 bit thì kết quả vẫn là LWE chiếm ưu thế hơn trong vấn đề mã hóa và giải mã. Đối với GGH máy xử lý với chuỗi ký tự trên 11 là sẽ xảy ra sai lệch giữa quá trình mã hóa và giải mã. Điều này hiểu đơn giản vì để
572 NGHIÊN CỨU MỘT SỐ HỆ MẬT LATTICE TRONG HỌ MÃ HÓA ĐỒNG CÂU ĐẦY ĐỦ sinh ma trận đơn phương mà chạy bằng máy tính cá nhân sẽ mất rất nhiều thời gian nên chúng tôi chọn cách sinh ra ma trận khóa bí mật có H = 0,9 và khóa công khai có H = 0,1, điều này đồng nghĩa với việc độ chính xác giảm xuống đáng kể do 0,1 quá lớn với giá trị khuyến nghị H = 0,0001. Nếu chọn H = 0,0001 như giá trị khuyến nghị thì thời gian để sinh khóa công khai là rất lớn kể cả với Google Colab sử dụng GPU. Kết quả được hiển thị trong Hình 2: Hình 2. Kết quả mã hóa và giải mã của GGH Trong Hình 2 thì bản rõ chữ mà chúng tôi chọn là “GGH Encryption” với độ dài là 14 ký tự. Trong quá trình mã hóa, chúng tôi tiến hành chuyển đổi giữa bản rõ chữ sang bản rõ số sử dụng bảng mã ASCII, sau đó tiến hành sinh Private Key và Public Key thời gian sinh ra Private Key là 1 phút, thời gian sinh ra Public Key là gần 1 phút. Sau đó chúng tôi nhận lại một bản mã là một chuỗi gồm 14 số. Thời gian thực hiện giải mã khá là nhanh chỉ mất khoảng 1 phút tuy nhiên bản rõ số được sinh ra có sự sai lệch khá nhiều đối với bản rõ số ban đầu. Để giảm thiểu sự sai lệch thì chúng tôi tiến hành giảm giá trị của H, tuy nhiên thời gian chạy với giá trị của H càng nhỏ sẽ càng mất rất nhiều thời gian. Bảng 1 mô tả thời gian chạy và mức độ chính xác (mức độ chính xác được tính theo tỉ lệ % số lượng ký tự đúng sau quá trình giải mã so với bản rõ chữ ban đầu) của chương trình khi chúng tôi đặt các giá trị của H đối với bản rõ gồm 14 ký tự. Thời gian chạy ở giá trị H = 0,1 khá là nhanh tuy nhiên sự chính xác chỉ đạt được khá là thấp (sai lệch sau quá trình giải mã so với bản rõ chữ ban đầu lên đến hơn 60% số lượng ký tự). Khi giảm giá trị của H thì kết quả có sự thay đổi tuy nhiên vẫn chưa phải là kết quả tốt. Bên cạnh đó thời gian chạy của chương trình mất khá nhiều thời gian. Bảng 1. Thời gian chạy và mức độ chính xác của chương trình GGH đối với bản rõ 14 ký tự GGH Giá trị của H Thời gian chạy Mức độ chính xác 0,1 < 1 phút < 40% 0,01 30-45 phút < 47% 0,001 3-5 tiếng < 51% 0,0001 > 24 giờ Chưa ra kết quả Đối với LWE chúng tôi thực hiện quá trình tương tự và kết quả cho ra rất là tốt hơn so với GGH, chỉ mất dưới 5 s để tiến hành mã hóa và chỉ mất 5s để tiến hành giải mã. Bảng 2. Thời gian chạy và mức độ chính xác của chương trình mã hóa và giải mã GGH và LWE trên Google Colab GGH LWE Số lượng ký tự Thời gian chạy Mức độ chính xác Thời gian chạy Mức độ chính xác 24 giờ Chưa ra kết quả ≈ 5 giây 100% 9000 Không thử nghiệm < 1 phút 100% Dựa trên hai thực nghiệm đối với hai hệ mã hóa LWE và GGH, chúng tôi nhận thấy độ tốt của hai hệ mật không còn phụ thuộc vào độ mạnh yếu của máy tính mà phụ thuộc khá nhiều liên quan tới bản chất của hai hệ mã hóa này. Chúng tôi cũng đề xuất và thử nghiệm LWE trong vấn đề mã hóa và giải mã đối với một file nhập từ máy tính, sau đó chúng tôi sử dụng LWE trong vấn đề ký số trên văn bản. Hình 3. Chương trình mã hóa LWE Hình 4. Kết quả của quá trình mã hóa LWE
Khuất Thanh Sơn, Nguyễn Trường Thắng, Lê Phê Đô, Bùi Trọng A Đam 573 Hình 3 mô tả chương trình mã hóa LWE, trong đó chúng tôi nhập số nguyên tố q, số lượng phần tử trong một mẫu và giá trị bí mật (khóa bí mật). Sau đó chúng tôi tiến hành sinh ra hai Public Key là A và B. Chúng tôi tiến hành lựa chọn file từ máy tính với kích thước khoảng 13 kb tương đương với 1 đoạn văn bản gồm gần 1300 ký tự: “As opposed to the first industrial revolution which had its focus on the use of energy and muscle, …” Kết thúc quá trình mã hóa (Hình 4), văn bản sẽ được mã hóa và ghi vào file cypher.txt (Hình 5), đồng thời khóa công khai A và B cũng được khi vào file key.txt (Hình 6) để công khai. Hình 5. Nội dung file cypher.txt Hình 6. Nội dung file key.txt Quá trình giải mã đối với hệ mật LWE diễn ra với đầu vào là số nguyên tố q và khóa bí mật, cùng với đó là hai Public Key A và B lấy từ file key.txt. Tiếp đó chúng ta chọn file cypher.txt là file được mã hóa ở phía trên. Và kết quả đưa ra là một file plaintext. Hình 7. Chương trình giải mã LWE Hình 8. Nội dung file plaintext.txt Nội dung của file plaintext được mô tả trong Hình 8, file sau khi giải mã có thông điệp hoàn toàn trùng khớp so với bản rõ chữ trước khi mã hóa. Độ dài lớn nhất của 1 câu mà chúng tôi đã tiến hành thực nghiệm là khoảng 3000 ký tự. Thời gian chạy với quá trình mã hóa chỉ mất khoảng < 5 phút và thời gian chạy của quá trình giải mã < 3 phút. Độ chính xác là 100%. Chúng tôi cũng đã thử nghiệm với đoạn văn bản có độ dài 9000 ký tự, độ chính xác cũng là 100% tuy nhiên do chạy trên máy tính cá nhân nên thời gian mã hóa và giải mã tốn khá nhiều thời gian, ≈ 20 phút cho quá trình mã hóa và ≈ 10 phút cho quá trình giải mã. Đối với các văn bản có kích thước lớn, ví dụ 200 Kb tương đương với > 50.000 ký tự. Chúng tôi tiến hành thực hiện mã hóa từng phần (ở đây chúng tôi đề xuất tiến hành với 3000 ký tự), sau đó nối lại với nhau bằng phương pháp đánh chỉ mục. Điều này cũng không làm cho thời gian mã hóa và giải mã mất nhiều thời gian hơn việc mã hóa và giải mã một đoạn văn bản 3000 ký tự. Thời gian chạy của việc mã hóa là < 15 phút, thời gian chạy của việc giải mã và nối văn bản là khoảng 10 phút. Bên cạnh đó, về mặt hiệu quả đem lại thì độ chính xác trong quá trình mã hóa và giải mã của LWE vẫn là tuyệt đối. V. KẾT LUẬN Trong báo cáo này, chúng tôi đã giới thiệu hai hệ mã hóa là GGH và LWE. Sau đó chúng tôi xây dựng hai chương trình để tiến hành thực nghiệm đối với quá trình mã hóa và giải mã của cả hai hệ mã hóa GGH và LWE. Độ chính xác cũng như thời gian chạy của LWE chiếm ưu thế hơn so với GGH. Ta thấy rõ được hệ LWE có khả năng áp dụng vào thực tiễn là rất cao và cao hơn rất nhiều so với với hệ mật GGH. Tuy nhiên, trong bài báo này chúng tôi mới chỉ dừng lại ở việc mã hóa và giải mã đối với văn bản ≈ 50.000 ký tự. Hướng phát triển liên quan tới hệ mật LWE còn rất rộng lớn, ví dụ như ứng dụng LWE trong ký số điện tử. Đây là một hướng mà chúng tôi sẽ tiếp tục nghiên cứu trong thời gian tới để phát triển thêm nghiên cứu này của chúng tôi. TÀI LIỆU THAM KHẢO [1] The National Academies of Sciences, Engineering, and Medicine (2019). Grumbling, Emily; Horowitz, Mark (eds.). Quantum Computing: Progress and Prospects (2018). Washington, DC: National Academies Press. p. I-5. doi:10.17226/25196. ISBN 978-0-309-47969-1. OCLC 1081001288. [2] O. Regev on lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6):1-40, 2009. Preliminary version in STOC, 2005. [3] C. Peikert and B. Waters. Lossy trapdoor functions and their applications. STOC, pages 187-196, 2008. [4] Craig Gentry. A Fully Homomorphic Encryption Scheme. PhD thesis, Stanford, September 2009. [5] Oded Regev. “The Learning with Errors Problem”. Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, June 9-12, 2010. [6] Federico Bergami. “Lattice-Based Cryptography”. ALGANT Master's Thesis - 20 July, 2016.
574 NGHIÊN CỨU MỘT SỐ HỆ MẬT LATTICE TRONG HỌ MÃ HÓA ĐỒNG CÂU ĐẦY ĐỦ [7] Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai, "Public-key cryptosystems from lattice reduction problems". CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology. London: Springer-Verlag. pp. 112–131, 1997. [8] E. Agrell, T. Eriksson, A. Vardy and K. Zeger, "Closest point search in lattices", in IEEE Transactions on Information Theory, vol. 48, No. 8, pp. 2201-2214, Aug. 2002, doi: 10.1109/TIT.2002.800499. [9] Zhaofei Tian, B.Sc. “GGH Cryptosystem and Lattice Reduction Algorithms”. Master of Science (2011) McMaster University (Computing & Software) Hamilton, Ontario, Canada. [10] M. Bessenyei. The Hermite-Hadamard inequality on simplices. Amer. Math. Monthly, 115(4):339-345, 2008. [11] J. Hoffstein, J.C. Pipher, and J.H. Silverman. An introduction to mathematical cryptography. Undergraduate texts in mathematics. Springer, 2008. RESEARCH SOME LATTICE CIPHERS IN FULLY HOMOMORPHIC ENCRYPTION Khuat Thanh Son, Nguyen Truong Thang, Le Phe Do, Bui Trong A Dam ABSTRACT: The strong development of the Internet and online transactions on the Internet from primitive forms to complex transactions are reflected in e-government systems, and e-commerce is growing strongly. The Internet has techniques that allow people to access, exploit, and share information with each other. But it is also the main risk of our information being changed or completely wrong. Along with the development of computing devices, the security of primitive cryptosystems was alarmed. In this report, we will first study some Lattice ciphers, which are mathematical problem-based public key cryptosystems with error (LWE) and GGH public key cryptosystems. Next, the report proposes solution to apply these cryptosystems in ensuring the security of documents and makes an assessment and comparison of the security of these two cryptosystems.