Bài toán Learning With Errors – nền tảng toán học của mật mã hậu lượng tử

Learning With Errors là bài toán do Oded Regev đề xuất năm 2005, cung cấp nền tảng toán học cho phần lớn mật mã hậu lượng tử hiện đại thông qua quy giảm worst-case từ các bài toán mạng lưới khó nhất đã biết.

Giới thiệu

Bài viết này phân tích bài toán Learning With Errors (LWE – Học với Lỗi), nền tảng toán học không chỉ của CRYSTALS-Kyber mà còn của CRYSTALS-Dilithium (chữ ký số hậu lượng tử), NTRU, và nhiều sơ đồ mật mã hậu lượng tử khác đang được chuẩn hóa hoặc nghiên cứu. LWE được Oded Regev (1979–) giới thiệu trong bài báo On Lattices, Learning with Errors, Random Linear Codes, and Cryptography năm 2005 – một trong những bài báo có ảnh hưởng sâu rộng nhất trong mật mã học thập kỷ qua và là một trong các động lực chính đưa Regev nhận Giải Gödel năm 2018. Tầm quan trọng của LWE nằm không chỉ ở tính thực tiễn mà còn ở tính lý thuyết: LWE có quy giảm worst-case từ các bài toán mạng lưới khó nhất đã biết, đảm bảo về mặt toán học rằng nếu bất kỳ triển khai LWE nào bị phá vỡ, toàn bộ lớp bài toán mạng lưới worst-case cũng bị phá vỡ theo – một cấp độ bảo đảm lý thuyết mà không có hệ thống mật mã truyền thống nào (RSA, ECC) đạt được.

LWE xuất phát từ một quan sát đơn giản nhưng sâu sắc: hệ phương trình tuyến tính trên các số nguyên modulo q là dễ giải, nhưng nếu thêm vào mỗi phương trình một lỗi nhỏ ngẫu nhiên, hệ phương trình trở nên khó giải một cách đột ngột – ngay cả trên máy tính lượng tử. Sự chuyển đổi từ dễ sang khó khi thêm lỗi nhỏ là điều trực giác có vẻ đơn giản nhưng thực ra phản ánh một cấu trúc toán học sâu liên kết với bài toán tìm vector ngắn nhất trong mạng lưới – bài toán đã được nghiên cứu hàng chục năm mà không có thuật toán hiệu quả nào được tìm thấy, kể cả thuật toán lượng tử.

Hiểu LWE là điều kiện để nắm bắt đầy đủ tại sao Kyber an toàn, tại sao bảo mật đó không bị phá vỡ bởi thuật toán Shor, và tại sao cộng đồng mật mã tin rằng mật mã dựa trên LWE sẽ an toàn ngay cả sau khi máy tính lượng tử phổ biến. Bài viết này xây dựng từ định nghĩa cơ bản, qua bằng chứng độ khó và các biến thể quan trọng, đến cách LWE được sử dụng thực tiễn trong các sơ đồ mật mã.

Nền tảng toán học

Để định nghĩa LWE chính xác và hiểu tại sao nó khó, cần nắm rõ ba thành phần: bài toán hệ phương trình tuyến tính trên Zq và tại sao nó dễ; cách thêm lỗi biến đổi hoàn toàn độ khó; và kết nối với bài toán mạng lưới tạo nên quy giảm worst-case.

Hệ phương trình tuyến tính và bài toán dễ

Xét hệ phương trình tuyến tính trên Zq (vành số nguyên modulo q): cho m phương trình và n ẩn số s₁, s₂, …, sₙ trong Zq, tìm lời giải. Trong ký hiệu ma trận: cho A ∈ Zq^(m×n) và b ∈ Zq^m, tìm s ∈ Zq^n sao cho As = b (mod q). Bài toán này thuộc lớp phức tạp P và có thể giải trong thời gian đa thức bằng phép loại Gauss (Gaussian elimination). Với m ≥ n phương trình và ma trận hạng đầy đủ, lời giải (nếu tồn tại) là duy nhất và có thể tìm trong thời gian O(n³) phép tính.

Điều thú vị là ngay cả khi thêm nhiễu ngẫu nhiên vào b – tức là b = As + e với e là một vector lỗi ngẫu nhiên biết trước phân phối nhưng không biết giá trị cụ thể – bài toán vẫn dễ nếu lỗi đủ nhỏ. Ví dụ, nếu mỗi thành phần của e là số nguyên ngẫu nhiên trong [-B, B] với B nhỏ so với q, kẻ tấn công có thể làm tròn b về bội gần nhất của q/B và sau đó giải bài toán tuyến tính không có lỗi bằng loại Gauss. Điều này chỉ hoạt động khi lỗi nhỏ đủ để việc làm tròn không gây nhầm lẫn.

Bài toán LWE được thiết kế để thêm lỗi đủ lớn để phá vỡ mọi cách tiếp cận làm tròn, nhưng đủ nhỏ để vẫn có thể giải mã đúng trong ứng dụng mật mã. Điểm mấu chốt là lỗi đủ lớn để ẩn giấu thông tin về s, nhưng đủ nhỏ để người biết s có thể giải mã. Cân bằng này – điều kiện lỗi đủ để ẩn nhưng không quá lớn để gây lỗi giải mã – là trung tâm của thiết kế mọi hệ thống dựa trên LWE, từ Regev 2005 đến Kyber 2017.

Định nghĩa chính xác bài toán LWE

Bài toán LWE được định nghĩa bởi ba tham số: số nguyên tố q (modulus), số chiều n (dimension), và phân phối lỗi χ trên Zq. Phân phối lỗi điển hình là phân phối Gaussian rời rạc với độ lệch chuẩn α·q cho tham số α nhỏ (ví dụ α = 1/√n), hay phân phối nhị thức trung tâm như trong Kyber.

Bài toán tìm kiếm (Search-LWE): cho một số đa thức lượng m mẫu dạng (aᵢ, bᵢ) trong đó aᵢ ∈ Zq^n ngẫu nhiên đồng đều và bᵢ = ⟨aᵢ, s⟩ + eᵢ (mod q) với eᵢ ← χ và s ∈ Zq^n cố định bí mật, hãy tìm s.

Bài toán quyết định (Decision-LWE): phân biệt giữa hai phân phối: (1) m mẫu dạng (aᵢ, bᵢ) với aᵢ ← Zq^n ngẫu nhiên và bᵢ = ⟨aᵢ, s⟩ + eᵢ với eᵢ ← χ; (2) m mẫu dạng (aᵢ, bᵢ) với cả aᵢ và bᵢ đều ngẫu nhiên đồng đều.

Phiên bản quyết định là phiên bản dùng trong phân tích bảo mật Kyber: bài toán là phân biệt khóa công khai b = As + e với một vector ngẫu nhiên đồng đều. Nếu bài toán này khó giải, khóa công khai trông ngẫu nhiên với kẻ không biết s, đảm bảo tính bí mật. Có thể chứng minh (quy giảm thống kê, statistical reduction) rằng nếu bài toán tìm kiếm khó thì bài toán quyết định cũng khó với cùng tham số – hai phiên bản là tương đương nhau về mặt độ khó tính toán.

Tham số LWE điển hình dùng trong thực tế: q ≈ 3329 (Kyber-1024), n = 256 (độ dài đa thức), k = 4 (số module), phân phối lỗi nhị thức trung tâm với η = 2 cho lỗi trong phạm vi [-2, 2]. Lựa chọn tham số cân bằng giữa bảo mật (lỗi đủ lớn để ẩn s) và đúng đắn giải mã (lỗi đủ nhỏ để không gây nhầm lẫn khi giải mã). Điều kiện q > 2^(n/α) gần đúng đảm bảo bài toán LWE đủ khó với các tham số đó.

Quy giảm worst-case và tầm quan trọng lý thuyết

Đóng góp cốt lõi của Regev năm 2005 không chỉ là định nghĩa bài toán LWE mà là chứng minh quy giảm lượng tử từ bài toán GapSVP/SIVP worst-case về LWE trung bình. Đây là điều làm cho LWE trở nên đặc biệt quan trọng trong mật mã học lý thuyết và thực tiễn.

Bài toán GapSVP (Gap Shortest Vector Problem) hỏi: cho mạng lưới và tham số γ, hãy xác định vector ngắn nhất trong mạng lưới có độ dài ≤ 1 hay > γ (với khoảng cách γ). Bài toán SIVP (Shortest Independent Vectors Problem) hỏi tìm n vector độc lập tuyến tính trong mạng lưới với độ dài tối đa nhỏ nhất có thể. Cả hai bài toán đều đã được nghiên cứu hàng thập kỷ và không có thuật toán đa thức cổ điển hay lượng tử nào được biết để giải với tham số γ = poly(n).

Quy giảm của Regev khẳng định: nếu tồn tại thuật toán lượng tử đa thức giải bài toán LWE tìm kiếm trung bình (với q, n, χ cụ thể), thì tồn tại thuật toán lượng tử đa thức giải GapSVP trong trường hợp xấu nhất (worst-case). Chiều ngược lại được suy ra từ: nếu GapSVP worst-case khó ngay cả với lượng tử, thì LWE trung bình cũng khó với lượng tử. Quy giảm này có ý nghĩa sâu sắc: bảo mật của LWE không chỉ dựa trên giả định rằng không có kẻ tấn công cụ thể nào thành công mà dựa trên bằng chứng toán học rằng thành công đó sẽ mâu thuẫn với độ khó của GapSVP worst-case – bài toán đã được phân tích rộng rãi trong cộng đồng lý thuyết tính toán.

Năm 2009, Peikert mở rộng kết quả, cho thấy có thể quy giảm cổ điển (không cần lượng tử) từ GapSVP về LWE với các tham số hơi khác nhau. Kết quả của Peikert đặc biệt quan trọng vì nó không cần giả định về sức mạnh của máy tính lượng tử – ngay cả trong mô hình cổ điển, LWE có bằng chứng bảo mật từ GapSVP worst-case. Đây là điều RSA và ECC hoàn toàn thiếu: không có bằng chứng nào rằng phá vỡ RSA mâu thuẫn với độ khó worst-case của bài toán nào đó đã được nghiên cứu kỹ – chỉ có giả định bán chính thức rằng phân tích nhân tử và ECDLP là khó.

Tuy nhiên, cần nhấn mạnh một giới hạn quan trọng: quy giảm của Regev đảm bảo rằng phá vỡ LWE trung bình khó hơn không đáng kể so với giải GapSVP worst-case – không phải rằng chúng có cùng độ khó. Tham số GapSVP cụ thể trong quy giảm của Regev có γ = O(n/α) – khoảng cách tương đối lớn so với bài toán GapSVP khó nhất (γ = O(1)). Điều này có nghĩa bằng chứng bảo mật của LWE dựa trên phiên bản xấp xỉ của GapSVP, không phải GapSVP chính xác. Đây là điểm yếu lý thuyết tinh tế mà cộng đồng mật mã nhận thức rõ và đang tiếp tục nghiên cứu để thu hẹp khoảng cách giữa bảo mật lý thuyết và bảo mật thực tiễn.

Các biến thể LWE

Từ LWE cơ bản, nhiều biến thể quan trọng đã được phát triển để cải thiện hiệu suất hay phù hợp với các ứng dụng cụ thể. Hai biến thể quan trọng nhất là Ring-LWE (R-LWE) và Module-LWE (M-LWE) – nền tảng trực tiếp của Kyber.

Ring-LWE – cải thiện hiệu suất bằng cấu trúc đại số

LWE gốc có hiệu suất thực tế kém vì khóa công khai (ma trận A ∈ Zq^(m×n)) lớn và phép nhân ma trận-vector chậm. Lyubashevsky, Peikert và Regev giới thiệu Ring-LWE (R-LWE) năm 2010 bằng cách thay thế Zq^n bởi vành đa thức Rq = Zq[X]/(X^n + 1).

Trong R-LWE, bài toán có cùng cấu trúc: cho các mẫu (aᵢ, bᵢ = aᵢ·s + eᵢ) với aᵢ, s ∈ Rq ngẫu nhiên và eᵢ ← χ, hãy tìm s. Cải thiện quan trọng về hiệu suất: phép nhân trong Rq có thể thực hiện bằng NTT trong thời gian O(n log n) thay vì O(n²) cho phép nhân vector thông thường; một phần tử a ∈ Rq đại diện cho toàn bộ một hàng của ma trận LWE gốc, giảm kích thước lưu trữ từ O(n²) về O(n); cấu trúc vành đa thức cho phép sử dụng một phần tử a duy nhất để tạo n phương trình ẩn, thay vì cần n phần tử ngẫu nhiên độc lập.

Bằng chứng bảo mật của R-LWE tương tự LWE gốc: có quy giảm worst-case từ Ring-SVP (SVP trên mạng lưới lý tưởng) về R-LWE. Tuy nhiên, cấu trúc đại số bổ sung của vành đa thức có thể tạo ra điểm yếu mà LWE gốc không có. Cụ thể, kẻ tấn công có thể khai thác cấu trúc lý tưởng (ideal structure) của Rq để thực hiện các cuộc tấn công hiệu quả hơn trên một số lớp tham số. Năm 2016, cuộc tấn công Ducas–Nguyen chứng minh rằng ideal lattices có thể bị tấn công hiệu quả hơn mạng lưới tổng quát trong một số trường hợp. Đây là lý do tại sao Module-LWE – biến thể lai giữa LWE gốc và R-LWE – được ưa chuộng hơn R-LWE thuần túy trong các thiết kế hiện đại như Kyber.

Module-LWE – cân bằng tối ưu giữa hiệu suất và bảo mật

Module-LWE (M-LWE) là biến thể mà Kyber dựa trên, được giới thiệu bởi Langlois và Stehlé năm 2012. Thay vì làm việc trên Rq đơn lẻ (R-LWE) hay Zq^n thuần túy (LWE gốc), M-LWE làm việc trên module Rq^k – các vector có k thành phần trong Rq. Trong ký hiệu ma trận, bài toán M-LWE có dạng: cho A ∈ Rq^(k×k), b = As + e với s, e ∈ Rq^k, hãy phân biệt (A, b) với (A, b_random).

Module-LWE đạt được cân bằng giữa R-LWE và LWE gốc theo ba chiều quan trọng. Về hiệu suất: nhờ cấu trúc đa thức, NTT vẫn áp dụng được cho phép nhân trong Rq, giữ hiệu suất gần với R-LWE. Về bảo mật: tham số k (số module) cho phép điều chỉnh mức bảo mật linh hoạt mà không cần thay đổi n hay q – tăng k tăng bảo mật, giảm k giảm kích thước. Điều này cho phép Kyber-512 (k=2), Kyber-768 (k=3) và Kyber-1024 (k=4) chia sẻ cùng cấu trúc cơ bản và cùng mã nguồn, chỉ khác về tham số. Về căn cứ bảo mật: bằng chứng quy giảm cho M-LWE mạnh hơn R-LWE vì Module-SVP trên module lattice khó hơn Ring-SVP trên ideal lattice – cấu trúc module ít đặc biệt hơn cấu trúc lý tưởng, ít dễ bị tấn công đặc biệt hơn.

Bằng chứng bảo mật của M-LWE: Albrecht, Ducas, Herold, Kirshanova, Postlethwaite và Stevens (2022) chứng minh quy giảm từ Module-SVP worst-case về M-LWE trung bình, tương tự quy giảm của Regev cho LWE gốc. Quy giảm này đảm bảo rằng phá vỡ M-LWE đòi hỏi giải Module-SVP trong trường hợp xấu nhất – điều được cho là không thể với bất kỳ thuật toán cổ điển hay lượng tử nào hiện biết.

Learning With Rounding và các biến thể khác

Learning With Rounding (LWR) là biến thể do Banerjee, Peikert và Rosen đề xuất năm 2012, thay thế lỗi cộng (additive error) bằng phép làm tròn (rounding). Trong LWR, thay vì tính b = ⟨a, s⟩ + e với e ngẫu nhiên, ta tính b = round(⟨a, s⟩) – làm tròn kết quả về ít bit hơn. Phép làm tròn thực chất là thêm lỗi xác định (deterministic error) phụ thuộc vào s và a, thay vì lỗi ngẫu nhiên. LWR có lợi thế không cần sinh lỗi ngẫu nhiên (tiết kiệm entropy và tính toán) nhưng có nhược điểm là bằng chứng quy giảm phụ thuộc vào bài toán LWE tương ứng, không trực tiếp từ mạng lưới. SABER – một ứng viên trong cuộc thi NIST – dùng Module-LWR thay vì Module-LWE, nhưng Kyber chọn Module-LWE vì bằng chứng bảo mật trực tiếp hơn.

LWE trên số nguyên thực là phiên bản gốc của Regev trong đó q không nhất thiết là số nguyên tố và không gian tính toán là số thực thay vì số nguyên – phiên bản này quan trọng cho phân tích lý thuyết nhưng không thực tiễn vì các số thực không thể biểu diễn chính xác trong máy tính. Các biến thể thực tế luôn dùng modulo số nguyên cụ thể.

Entropic LWE là phiên bản trong đó vector bí mật s không đồng đều trong Zq^n mà được lấy từ phân phối entropy thấp – ví dụ, s có các thành phần nhỏ như s ∈ {-1, 0, 1}^n. Biến thể này xuất hiện trong thiết kế Kyber qua Kyber.CPAPKE: vector bí mật s được lấy từ cùng phân phối lỗi nhỏ χ, không phải đồng đều trong Rq. Lựa chọn này giúp tính toán nhanh hơn (lỗi nhỏ nhân dễ hơn) và giảm kích thước khóa riêng, trong khi bảo mật vẫn được bảo toàn theo quy giảm Regev-Peikert với lỗi nhỏ.

Các thuật toán tấn công và phân tích độ khó

Không thể đánh giá đúng độ an toàn của LWE-based cryptography mà không hiểu các thuật toán tấn công tốt nhất hiện có và heuristics về chi phí của chúng.

Tấn công mạng lưới và thuật toán BKZ

Hướng tấn công mạnh nhất đối với LWE là tấn công giảm mạng lưới (lattice reduction): từ các mẫu LWE (A, b = As + e), xây dựng một mạng lưới cụ thể trong đó vector s (hay e) tương ứng với vector ngắn trong mạng lưới đó, rồi dùng thuật toán giảm mạng lưới để tìm vector ngắn.

Thuật toán BKZ (Block Korkin–Zolotarev), phát triển bởi Schnorr và Euchner năm 1994 và cải thiện nhiều lần sau đó, là thuật toán giảm mạng lưới thực tế hiệu quả nhất. BKZ hoạt động bằng cách liên tục áp dụng thuật toán tìm vector ngắn (SVP) trên các khối nhỏ kích thước β (gọi là blocksize) của cơ sở mạng lưới, cải thiện dần chất lượng cơ sở. Chi phí tính toán của BKZ phụ thuộc mạnh vào β: tăng β cải thiện chất lượng giảm nhưng chi phí SVP trên khối kích thước β tăng theo cấp số mũ.

Ước tính chi phí của BKZ trên LWE với tham số cụ thể dựa trên hai heuristics: Geometric Series Assumption (GSA) mô tả hành vi của cơ sở sau khi giảm BKZ, và ước tính chi phí SVP trong không gian chiều β là khoảng 2^(0.292β) phép tính (với thuật toán sieve tốt nhất hiện biết). Kết hợp, với LWE tham số Kyber-1024, β tối thiểu cần thiết để tấn công thành công là khoảng 700–800, tương ứng chi phí khoảng 2^(0.292 × 750) ≈ 2^219 phép tính – xa hơn nhiều so với 2^128 ngưỡng thực tế.

Tấn công đại số và tấn công thống kê

Tấn công đại số (algebraic attack) cố gắng giải hệ phương trình LWE sử dụng các kỹ thuật đại số như cơ sở Gröbner. Tuy nhiên, hệ phương trình LWE trên Zq dẫn đến các bài toán Gröbner có độ phức tạp theo cấp số mũ với các tham số thực tế của Kyber – thực tế không hiệu quả hơn tấn công mạng lưới.

Tấn công distinguishing (phân biệt) trực tiếp cố gắng phân biệt phân phối LWE với phân phối đồng đều mà không tìm s. Thuật toán BKW (Blum–Kalai–Wasserman) từ năm 2003 đạt được điều này với độ phức tạp 2^(O(n/log n)) – tiệm cận tốt hơn tấn công brute-force nhưng vẫn theo cấp số mũ và chỉ hiệu quả khi lỗi rất nhỏ so với q. Với tham số Kyber, BKW không hiệu quả hơn tấn công BKZ.

Tấn công dual (dual attack) của Micciancio và Walter (2021) khai thác cấu trúc của bài toán LWE dual (bài toán nghịch chuyển). Trong một số phân tích, dual attack được ước tính có thể tốt hơn BKZ khoảng 10–20 bit bảo mật cho các tham số cụ thể. Cộng đồng đang tiếp tục phân tích để xác định chính xác tác động của dual attack với các tham số Kyber; kết quả hiện tại không đe dọa nghiêm trọng đến bảo mật của Kyber-1024 nhưng cho thấy ước tính bảo mật ban đầu có thể cần điều chỉnh nhỏ.

Không có tấn công lượng tử hiệu quả

Câu hỏi quan trọng nhất là: có thuật toán lượng tử nào tấn công LWE hiệu quả hơn đáng kể so với thuật toán cổ điển không? Câu trả lời hiện tại là không. Thuật toán Shor không áp dụng được cho LWE vì LWE không có cấu trúc chu kỳ ẩn (hidden subgroup structure) mà Shor khai thác. Thuật toán Grover tăng tốc tìm kiếm không gian ngẫu nhiên theo căn bậc hai, nhưng tấn công brute-force trên LWE không phải tìm kiếm không gian ngẫu nhiên theo nghĩa đơn giản – nó đòi hỏi giải bài toán mạng lưới mà Grover không cải thiện đáng kể.

Các thuật toán lượng tử cho bài toán mạng lưới là chủ đề nghiên cứu tích cực. Một số thuật toán lượng tử cho sieve (tìm vector ngắn trong không gian con) có thể cải thiện hệ số hằng trong exponent – ví dụ 2^(0.265β) thay vì 2^(0.292β) cho BKZ với quantum sieve. Cải thiện này giảm bảo mật ước tính của Kyber khoảng 10–15% khi tính theo thang lôgarit – lý do tại sao bảo mật lượng tử của Kyber-1024 ước tính khoảng 230 bit thay vì 256 bit như bảo mật cổ điển. Tuy nhiên, cải thiện này không gây đột biến – không có bước nhảy vọt từ khó sang dễ như thuật toán Shor làm với ECC. LWE vẫn khó theo cấp số mũ ngay cả với thuật toán lượng tử tốt nhất được biết.

Ứng dụng LWE trong mật mã học

LWE không chỉ là nền tảng của Kyber mà còn là nền tảng của một hệ sinh thái rộng lớn các nguyên thủy mật mã hậu lượng tử, từ mã hóa công khai đến chữ ký số đến mã hóa đồng cấu.

Mã hóa công khai và KEM từ LWE

Sơ đồ mã hóa công khai đơn giản nhất từ LWE (Regev 2005) hoạt động như sau: khóa riêng là s ∈ Zq^n; khóa công khai là (A, b = As + e) với A ∈ Zq^(m×n) và e ← χ^m; để mã hóa bit μ ∈ {0, 1}, chọn ngẫu nhiên x ∈ {0,1}^m và tính c₁ = A^T·x (mod q), c₂ = b^T·x + μ·⌊q/2⌋ (mod q); để giải mã, tính μ’ = round(c₂ – s^T·c₁, ⌊q/2⌋) – làm tròn về 0 hay 1 tùy kết quả gần ⌊q/2⌋ hay gần 0. Giải mã đúng vì c₂ – s^T·c₁ = e^T·x + μ·⌊q/2⌋ và nếu |e^T·x| nhỏ đủ (lỗi nhỏ), làm tròn cho kết quả đúng.

Kyber là tinh chỉnh phức tạp hơn nhiều của ý tưởng này: thay Zq bằng Rq^k, dùng đa thức ngẫu nhiên thay ma trận ngẫu nhiên, nén bản mã để giảm kích thước, và áp dụng biến đổi FO để đạt IND-CCA2. Nhưng cốt lõi vẫn là cùng một nguyên lý: mã hóa thông tin bằng cách cộng vào gần một tổ hợp tuyến tính của khóa công khai, và giải mã bằng cách trừ ra tổ hợp tương tự dùng khóa riêng, dựa vào lỗi nhỏ đảm bảo kết quả gần đúng đủ để làm tròn chính xác.

Chữ ký số CRYSTALS-Dilithium từ Module-LWE

CRYSTALS-Dilithium – được NIST tiêu chuẩn hóa cùng đợt với Kyber năm 2024 (FIPS 204) – là sơ đồ chữ ký số dựa trên Module-LWE và Module-SIS (Short Integer Solution). Dilithium dùng Module-LWE để xây dựng một sơ đồ cam kết (commitment scheme) và Module-SIS để tạo chữ ký theo mô hình Fiat–Shamir: người ký tạo một cam kết ngẫu nhiên, nhận thách thức (được tạo bằng hàm băm), và phản hồi bằng một phản hồi (response) có thể xác minh công khai. Bảo mật dựa trên độ khó tìm vector ngắn trong mạng lưới module – cùng họ bài toán với Kyber nhưng phiên bản khác (SIS thay vì LWE).

Mối liên hệ giữa Kyber và Dilithium là chúng dùng chung cùng module lattice và nhiều thành phần kỹ thuật (NTT, phân phối lỗi nhỏ), cho phép triển khai chia sẻ code hiệu quả. Trong PQXDH, XEdDSA vẫn được dùng cho chữ ký (vì nó tương thích với cùng khóa Montgomery dùng cho DH), không phải Dilithium – nhưng trong các phiên bản tương lai của giao thức, khi xác thực lẫn nhau hậu lượng tử được thêm vào, Dilithium hay FALCON (chữ ký dựa trên NTRU lattice cũng được NIST tiêu chuẩn hóa) là các ứng viên tự nhiên.

Mã hóa đồng cấu từ LWE – biên giới tiên tiến nhất

Ứng dụng tinh vi và mạnh mẽ nhất của LWE là mã hóa đồng cấu (Fully Homomorphic Encryption – FHE): khả năng tính toán trực tiếp trên dữ liệu đã mã hóa mà không cần giải mã. FHE cho phép một máy chủ xử lý dữ liệu nhạy cảm của người dùng mà không bao giờ thấy dữ liệu gốc – có ứng dụng trong điện toán đám mây bảo mật, truy vấn cơ sở dữ liệu riêng tư và nhiều bài toán quyền riêng tư khác.

Craig Gentry (1977–) chứng minh tính khả thi của FHE đầy đủ năm 2009 sử dụng mạng lưới lý tưởng. Các sơ đồ FHE thực tế hiện đại – BFV (Brakerski–Fan–Vercauteren), BGV (Brakerski–Gentry–Vaikuntanathan) và CKKS (Cheon–Kim–Kim–Song) – tất cả đều dựa trên Ring-LWE hay Module-LWE. Quy giảm worst-case của LWE đảm bảo rằng FHE dựa trên LWE có nền tảng bảo mật lý thuyết mạnh nhất hiện có – mạnh hơn bất kỳ hệ thống mật mã truyền thống nào.

FHE từ LWE vẫn chậm hơn nhiều so với tính toán thông thường (khoảng 1000–1.000.000 lần tùy ứng dụng) và là lĩnh vực nghiên cứu tích cực. Nhưng chính sự tồn tại của FHE từ LWE chứng minh rằng LWE không chỉ là một bài toán khó mà còn là một cấu trúc toán học đủ phong phú để xây dựng các nguyên thủy mật mã cao cấp nhất.

Kết luận

Learning With Errors là một trong những phát hiện lý thuyết quan trọng nhất trong mật mã học thập niên 2000–2010: một bài toán đơn giản về bề ngoài – hệ phương trình tuyến tính với lỗi nhỏ – hóa ra có độ khó gắn liền với bài toán mạng lưới worst-case mà không có thuật toán lượng tử nào được biết có thể giải hiệu quả. Điều này cung cấp nền tảng lý thuyết vững chắc nhất hiện có cho mật mã hậu lượng tử, khác biệt căn bản với RSA và ECC chỉ dựa trên giả định không có bằng chứng quy giảm.

Các biến thể Module-LWE và Ring-LWE đã chuyển hóa lý thuyết thành thực tiễn: Kyber-1024 có kích thước khóa và bản mã chấp nhận được (vài kilobyte), hiệu suất nhanh trên phần cứng hiện đại, và bảo mật NIST Level 5 đủ để bảo vệ thông tin trong hàng thập kỷ kể cả khi máy tính lượng tử mạnh xuất hiện. Từ đặc tả Regev 2005 đến CRYSTALS-Kyber được NIST tiêu chuẩn hóa năm 2024 là hành trình hai thập kỷ từ lý thuyết mật mã đến ứng dụng thực tiễn bảo vệ hàng tỷ cuộc trò chuyện – một trong những trường hợp ấn tượng nhất của việc toán học thuần túy trở thành công cụ bảo mật quan trọng nhất của thời đại.