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ử

CRYSTALS-Kyber là cơ chế đóng gói khóa hậu lượng tử dựa trên bài toán Module Learning With Errors, được NIST tiêu chuẩn hóa năm 2024 và được Signal Protocol lựa chọn làm thành phần bảo mật hậu lượng tử trong PQXDH.

Giới thiệu

Bài viết này mô tả CRYSTALS-Kyber – tên chính thức sau khi chuẩn hóa là ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism, FIPS 203) – cơ chế đóng gói khóa (KEM – Key Encapsulation Mechanism) hậu lượng tử đầu tiên được Viện Tiêu chuẩn và Công nghệ Quốc gia Hoa Kỳ (NIST) tiêu chuẩn hóa chính thức vào tháng 8 năm 2024. Kyber là sản phẩm nghiên cứu của một nhóm tác giả đa quốc gia dẫn đầu bởi Roberto Avanzi, Joppe Bos, Léo Ducas (1987–), Eike Kiltz (1975–), Tancrède Lepoint, Vadim Lyubashevsky, John Schanck, Peter Schwabe (1983–), Gregor Seiler và Damien Stehlé, được đề xuất trong cuộc thi tiêu chuẩn hóa mật mã hậu lượng tử của NIST vào năm 2017 và trải qua bốn vòng phân tích kỹ lưỡng trong bảy năm trước khi được chọn.

Trong PQXDH – phiên bản hậu lượng tử của X3DH trong Signal Protocol – Kyber-1024 được chỉ định là tham số pqkem mặc định. Mỗi phiên PQXDH, Mỹ Anh thực hiện thao tác PQKEM–ENC(PQPKB) trên khóa công khai Kyber của Đan Nguyên để nhận được một cặp (CT, SS) gồm bản mã và bí mật chung; Đan Nguyên thực hiện PQKEM–DEC(PQPKB, CT) để thu lại cùng bí mật chung SS. Bí mật chung SS được nối vào chuỗi các đầu ra DH trước khi đưa qua KDF để tạo khóa phiên SK, đảm bảo rằng để tính SK, kẻ tấn công phải đồng thời phá vỡ cả thành phần Diffie–Hellman cổ điển lẫn Kyber – một bài toán kép mà không có thuật toán nào được biết có thể giải hiệu quả ngay cả trên máy tính lượng tử mạnh.

Lý do Kyber được chọn thay vì các ứng viên khác trong cuộc thi NIST – như NTRU, SABER hay McEliece – là sự kết hợp của nhiều yếu tố: nền tảng toán học dựa trên Module-LWE có bằng chứng quy về bài toán worst-case trên mạng lưới; kích thước khóa và bản mã nhỏ gọn so với các ứng viên; hiệu suất cao trên cả phần cứng và phần mềm; thiết kế IND-CCA2 an toàn thông qua biến thổi Fujisaki–Okamoto; và bề mặt phân tích mật mã rộng sau bảy năm cộng đồng mật mã toàn cầu cố gắng tìm điểm yếu mà không thành công ở mức độ đáng lo ngại.

Nền tảng lý thuyết

Kyber xây dựng trên ba tầng lý thuyết lồng vào nhau: vành đa thức là không gian tính toán; Module-LWE là bài toán độ khó cơ sở; và biến đổi Fujisaki–Okamoto là cơ chế nâng cấp từ bảo mật thụ động IND-CPA lên bảo mật chủ động IND-CCA2.

Vành đa thức và cấu trúc mạng lưới module

Kyber hoạt động trong vành đa thức Rq = Zq[X] / (X^n + 1) với n = 256 và q = 3329. Mỗi phần tử của Rq là một đa thức bậc tối đa 255 với hệ số trong khoảng [0, 3328]. Phép nhân trong Rq được thực hiện theo modulo cả đa thức X^256 + 1 lẫn số nguyên q = 3329. Không gian này được gọi là vành thương (quotient ring) và nó là nền tảng cho phép tính hiệu quả trong Kyber nhờ hai tính chất đặc biệt.

Thứ nhất, đa thức X^256 + 1 là đa thức cyclotomic – cụ thể là đa thức cyclotomic thứ 512, ký hiệu Φ₅₁₂(X). Tính chất quan trọng của đa thức cyclotomic này là nó phân rã thành các nhân tử bậc nhất trên trường Zq khi q ≡ 1 (mod 2n), tức là khi 3329 ≡ 1 (mod 512) – điều kiện này đúng vì 3329 = 13 × 256 + 1. Sự phân rã này cho phép áp dụng biến đổi số luận (NTT – Number Theoretic Transform), tương đương với biến đổi Fourier nhanh (FFT) trên trường hữu hạn, để tính phép nhân đa thức trong thời gian O(n log n) thay vì O(n²) nếu tính trực tiếp.

Thứ hai, số nguyên tố q = 3329 được chọn đặc biệt nhỏ để hệ số đa thức vừa khít trong kiểu số nguyên 12 bit, tối ưu hóa lưu trữ và truyền tải. Phép tính modulo 3329 trên phần cứng 16 bit hay 32 bit hiệu quả hơn đáng kể so với modulo số lớn hơn. Kết hợp n = 256 và q = 3329, mỗi đa thức trong Rq được biểu diễn bởi 256 × 12 bit = 384 byte – đây là kích thước cơ bản của một phần tử trong Kyber.

Mạng lưới module (module lattice) trong Kyber được xây dựng từ các ma trận và vector có thành phần là các đa thức trong Rq. Tham số k xác định kích thước: với Kyber-1024 (biến thể mạnh nhất, dùng trong PQXDH), k = 4 có nghĩa là các vector có 4 thành phần đa thức và ma trận là 4×4. Khóa công khai, khóa riêng và bản mã đều là các vector/ma trận trong không gian Rq^k, có kích thước tỷ lệ thuận với k. Tăng k tăng kích thước và hiệu suất tính toán nhưng cũng tăng mức bảo mật – lý do Kyber-1024 có mức bảo mật NIST Level 5 trong khi Kyber-512 chỉ đạt Level 1.

Bài toán Module-LWE và nguồn gốc bảo mật

Bảo mật của Kyber dựa hoàn toàn vào giả định rằng bài toán Module Learning With Errors (Module-LWE) là khó giải. Bài toán này là phiên bản module của bài toán LWE do Oded Regev (1979–) đề xuất năm 2005 – bài toán mà bài viết riêng trong series sẽ phân tích chi tiết; phần này chỉ trình bày ở mức đủ để hiểu cách Kyber hoạt động.

Bài toán Module-LWE (phiên bản quyết định, dùng trong phân tích bảo mật Kyber) đặt câu hỏi: cho một ma trận ngẫu nhiên A ∈ Rq^(k×k), một vector b ∈ Rq^k và phân phối lỗi χ, hãy phân biệt hai trường hợp: (1) b = As + e với s ∈ Rq^k là vector bí mật và e là vector lỗi nhỏ lấy từ phân phối χ; (2) b là vector ngẫu nhiên đồng đều. Nếu bài toán này là khó (tức là không có thuật toán đa thức nào phân biệt được hai trường hợp), thì khóa công khai Kyber (A, b = As + e) trông ngẫu nhiên đối với kẻ không biết s, đảm bảo tính bí mật.

Điều quan trọng về mặt lý thuyết là tồn tại quy giảm worst-case (worst-case reduction) từ bài toán Module-LWE về bài toán Module-SVP (Shortest Vector Problem trên mạng lưới module) – bài toán tìm vector ngắn nhất trong một mạng lưới module. Quy giảm này, được chứng minh bởi Lyubashevsky, Peikert và Regev, đảm bảo rằng: nếu tồn tại thuật toán phá vỡ Module-LWE với bất kỳ phiên bản tham số nào, thuật toán đó cũng giải được Module-SVP trong trường hợp xấu nhất (worst-case) trên các mạng lưới tương ứng. Bài toán SVP trên mạng lưới được nghiên cứu nhiều thập kỷ và không có thuật toán hiệu quả nào – kể cả lượng tử – được biết để giải. Quy giảm worst-case là tính chất hiếm có và quý giá trong mật mã học: nó chuyển đảm bảo bảo mật từ giả thuyết (không có kẻ tấn công cụ thể nào tìm được) sang bằng chứng (nếu có kẻ tấn công, họ cũng giải được bài toán worst-case từng được nghiên cứu rộng rãi).

Phân phối lỗi χ trong Kyber là phân phối nhị thức trung tâm (centered binomial distribution) – không phải Gaussian liên tục vì Gaussian yêu cầu độ chính xác cao trong lấy mẫu. Cụ thể, hệ số lỗi trong Kyber-1024 được tạo bằng cách tính b₁ + b₂ + b₃ + b₄ – b₅ – b₆ – b₇ – b₈ với mỗi bᵢ là bit ngẫu nhiên – tạo ra phân phối nhị thức trung tâm trong khoảng [-4, 4] với giá trị 0 phổ biến nhất và các giá trị lớn rất hiếm. Phân phối này đủ nhỏ để giải mã đúng (lỗi không làm thay đổi bit quan trọng khi giải mã) nhưng đủ lớn để bài toán Module-LWE khó giải (lỗi quá nhỏ sẽ bị các thuật toán lattice khai thác dễ dàng hơn).

Biến đổi Fujisaki–Okamoto và bảo mật IND-CCA2

Kyber cơ sở – ký hiệu là Kyber.CPAPKE – chỉ đạt bảo mật IND-CPA: an toàn trước kẻ tấn công thụ động có thể lựa chọn bản rõ để mã hóa nhưng không thể truy vấn oracle giải mã. Để đạt bảo mật IND-CCA2 (an toàn ngay cả khi kẻ tấn công có thể truy vấn oracle giải mã tùy ý trước khi nhận bản mã thách thức), Kyber áp dụng biến đổi Fujisaki–Okamoto (FO transform) được điều chỉnh cho môi trường lượng tử.

Biến đổi FO trong mô hình oracle ngẫu nhiên (ROM – Random Oracle Model) hoạt động theo nguyên tắc: trước khi gửi bản mã, người gửi cam kết với bản rõ bằng cách băm nó; bản mã được tạo xác định từ bản rõ và kết quả băm thay vì từ ngẫu nhiên thuần túy; thẻ xác thực MAC được tính trên bản mã và bản rõ. Khi giải mã, thay vì đơn giản giải mã và trả về, oracle giải mã giải mã bản mã, băm lại bản rõ thu được và kiểm tra xem bản mã có khớp với bản mã tạo từ bản rõ đó không. Nếu không khớp, oracle giải mã từ chối – không trả về bất kỳ thông tin nào về nội dung bản mã. Cơ chế từ chối này ngăn kẻ tấn công IND-CCA2 sử dụng oracle giải mã để thu thập thông tin hữu ích.

Phiên bản FO trong Kyber sử dụng một kỹ thuật gọi là giải mã ngầm (implicit rejection): thay vì trả về lỗi khi phát hiện bản mã không hợp lệ, oracle giải mã trả về một giá trị ngẫu nhiên giả nhưng xác định (được tính từ bản mã và một giá trị bí mật z). Điều này đảm bảo kẻ tấn công không thể phân biệt trường hợp bản mã không hợp lệ với bản mã hợp lệ nhưng cho bản rõ kẻ tấn công không kiểm soát – bởi cả hai đều cho đầu ra trông ngẫu nhiên. Kỹ thuật từ chối ngầm này đặc biệt quan trọng trong mô hình oracle lượng tử (QROM – Quantum Random Oracle Model) nơi kẻ tấn công có thể truy vấn oracle bằng các trạng thái lượng tử siêu vị: từ chối rõ ràng (explicit rejection) rò rỉ thông tin trong QROM theo các cách tinh tế mà từ chối ngầm ngăn chặn được. Bằng chứng bảo mật trong QROM là một trong những điểm mạnh kỹ thuật quan trọng nhất của thiết kế Kyber so với một số ứng viên khác trong cuộc thi NIST.

Cấu trúc thuật toán Kyber

Kyber bao gồm ba thuật toán: tạo khóa (KeyGen), đóng gói (Encapsulate) và giải gói (Decapsulate). Hiểu chính xác ba thuật toán này là điều kiện để nắm bắt tại sao Kyber an toàn và cách nó tích hợp với PQXDH.

Tạo khóa – KeyGen

Thuật toán tạo khóa của Kyber sinh ra cặp khóa công khai và khóa riêng. Đầu vào là một nguồn ngẫu nhiên chất lượng mật mã; đầu ra là cặp (pk, sk).

Kyber.KeyGen():
    (ρ, σ) ← G(seed)          -- G là hàm băm SHA3-512
    A ← Sam(ρ)                 -- Lấy mẫu ma trận A ∈ Rq^(k×k) từ ρ
    (s, e) ← Sam(σ, η₁)       -- Lấy mẫu vector bí mật s và lỗi e từ χ_η₁
    t ← A·s + e                -- Tính khóa công khai t
    pk = (t, ρ)                -- Khóa công khai: t và seed tạo A
    sk = (s, pk, H(pk), z)     -- Khóa riêng: s cùng thông tin để giải mã
    return (pk, sk)

Giá trị hạt giống (seed) được chia thành hai phần bằng hàm băm SHA3-512: ρ dùng để tạo ma trận A xác định và σ dùng để tạo lỗi theo phân phối nhị thức trung tâm. Ma trận A không được lưu trực tiếp trong khóa công khai mà chỉ lưu ρ – bất kỳ ai cũng có thể tái tạo A từ ρ bằng thuật toán lấy mẫu xác định. Điều này giảm kích thước khóa công khai đáng kể: thay vì lưu k² = 16 đa thức (với k = 4), chỉ cần lưu 32 byte seed cùng vector t gồm k = 4 đa thức. Khóa công khai Kyber-1024 có kích thước 1568 byte – lớn hơn khóa đường cong elliptic (32 byte với Curve25519) nhưng nhỏ hơn đáng kể so với các hệ thống mật mã công khai truyền thống ở mức bảo mật tương đương như RSA-15360.

Khóa riêng sk chứa nhiều thành phần: vector bí mật s (để giải mã), khóa công khai pk (để kiểm tra bảo mật trong biến đổi FO), giá trị băm H(pk) (dùng trong đóng gói để ràng buộc bí mật chung với khóa công khai cụ thể), và một giá trị ngẫu nhiên z (dùng cho từ chối ngầm khi bản mã không hợp lệ). Sự hiện diện của pk trong sk đảm bảo người giải mã luôn có thể tái tạo đầy đủ thông tin để thực hiện kiểm tra biến đổi FO mà không cần lưu trạng thái bổ sung.

Đóng gói – Encapsulate

Thuật toán đóng gói nhận khóa công khai và sinh ra bản mã cùng bí mật chung. Đây là thao tác Mỹ Anh thực hiện trong PQXDH:

Kyber.Encapsulate(pk):
    m ← {0,1}^256             -- Chọn bản rõ ngẫu nhiên 32 byte
    (K̄, r) ← G(m || H(pk))   -- Tạo khóa tạm thời và hạt giống ngẫu nhiên
    ct ← Kyber.CPAPKE.Enc(pk, m, r)   -- Mã hóa m với khóa công khai pk
    K ← KDF(K̄ || H(ct))      -- Tạo bí mật chung K
    return (ct, K)

Bước then chốt là cách hạt giống ngẫu nhiên r được tạo ra: thay vì lấy r trực tiếp từ nguồn ngẫu nhiên, r được tạo từ G(m || H(pk)) trong đó m là bản rõ ngẫu nhiên 32 byte và H(pk) là băm của khóa công khai. Điều này đảm bảo hai tính chất: thứ nhất, r là hàm xác định của m và pk, nên cùng (m, pk) luôn cho cùng bản mã – điều kiện cần thiết cho biến đổi FO; thứ hai, H(pk) được đưa vào quá trình tạo r đảm bảo bí mật chung K phụ thuộc vào khóa công khai cụ thể pk, không chỉ vào m. Tính chất thứ hai ngăn chặn tấn công tái mã hóa: kẻ tấn công biết m từ một khóa KEM bị xâm phạm không thể đơn giản tạo lại bản mã hợp lệ cho khóa KEM khác.

Bí mật chung K được tính từ KDF(K̄ || H(ct)) trong đó H(ct) là băm của toàn bộ bản mã. Việc đưa H(ct) vào đây đảm bảo K phụ thuộc vào bản mã cụ thể được gửi đi – một kẻ tấn công thay đổi bất kỳ bit nào trong bản mã sẽ nhận được giá trị K hoàn toàn khác (và ngẫu nhiên trông như vậy). Điều này là một tầng bảo vệ bổ sung đảm bảo tính toàn vẹn của bản mã ngay cả trước khi có xác thực ngoài từ AEAD.

Thuật toán mã hóa Kyber.CPAPKE.Enc(pk, m, r) ở cốt lõi thực hiện phép tính mạng lưới module: từ r, lấy mẫu ba vector ngẫu nhiên; tính (u, v) = (A^T·r’ + e₁, t^T·r’ + e₂ + encode(m)) trong đó e₁, e₂ là lỗi nhỏ. Bản mã gồm cặp (u, v) đã được nén (compressed) để giảm kích thước. Quá trình nén bỏ đi một số bit ít quan trọng nhất của các hệ số đa thức – đây là nguồn gốc lỗi giải mã trong Kyber và cũng là lý do các tham số như η₁, η₂, d_u, d_v trong Kyber cần được tinh chỉnh cẩn thận để cân bằng giữa kích thước nhỏ và xác suất lỗi giải mã thấp.

Giải gói – Decapsulate

Thuật toán giải gói nhận bản mã và khóa riêng, trả về bí mật chung hay từ chối ngầm nếu bản mã không hợp lệ. Đây là thao tác Đan Nguyên thực hiện trong PQXDH:

Kyber.Decapsulate(sk, ct):
    m' ← Kyber.CPAPKE.Dec(s, ct)        -- Giải mã thử nghiệm
    (K̄', r') ← G(m' || H(pk))          -- Tái tạo hạt giống
    ct' ← Kyber.CPAPKE.Enc(pk, m', r') -- Tái mã hóa
    if ct == ct':                        -- Kiểm tra bản mã
        K ← KDF(K̄' || H(ct))           -- Bản mã hợp lệ
    else:
        K ← KDF(z || H(ct))             -- Từ chối ngầm: K ngẫu nhiên
    return K

Cơ chế kiểm tra mã hóa lại (re-encryption check) là trái tim của biến đổi FO trong Kyber. Thay vì chỉ giải mã và trả về bản rõ, Đan Nguyên thực hiện toàn bộ thao tác đóng gói lại từ m’ vừa thu được và kiểm tra xem bản mã tái tạo ct’ có khớp với bản mã nhận được ct không. Nếu bản mã gốc được tạo đúng theo giao thức, ct = ct’ sẽ đúng. Nếu kẻ tấn công giả mạo hay sửa đổi bản mã, giải mã Kyber.CPAPKE.Dec có thể vẫn cho ra một m’ nào đó (đây là IND-CPA, không bảo vệ tính toàn vẹn), nhưng khi mã hóa lại m’ sẽ cho bản mã ct’ ≠ ct, phát hiện sự giả mạo.

Trường hợp ct ≠ ct’ không kết thúc bằng lỗi rõ ràng mà bằng từ chối ngầm: K = KDF(z || H(ct)) trong đó z là giá trị ngẫu nhiên trong khóa riêng. Giá trị K này trông hoàn toàn ngẫu nhiên với bất kỳ kẻ quan sát nào không biết z, nhưng xác định (hàm của z và ct) đối với người giữ khóa riêng. Quan trọng nhất, kẻ tấn công không thể phân biệt được hai trường hợp ct hợp lệ và ct không hợp lệ chỉ bằng cách quan sát K đầu ra – cả hai đều trông ngẫu nhiên. Tính chất này, gọi là pseudorandom key output ngay cả khi giải mã thất bại, là điều kiện cần để bằng chứng bảo mật IND-CCA2 trong QROM hoạt động và là lý do cơ chế từ chối ngầm được ưa chuộng hơn từ chối rõ ràng trong thiết kế KEM hiện đại.

Các tham số Kyber và mức bảo mật

Kyber có ba biến thể tham số tương ứng với ba mức bảo mật NIST khác nhau, cho phép lựa chọn đánh đổi phù hợp giữa kích thước, hiệu suất và mức bảo mật.

So sánh ba biến thể Kyber-512, Kyber-768 và Kyber-1024

Kyber-512 đạt NIST Level 1, tương đương khó như tấn công brute-force trên AES-128 bằng thuật toán cổ điển tốt nhất. Đây là mức tối thiểu được NIST coi là chấp nhận được cho mật mã hậu lượng tử. Kyber-768 đạt NIST Level 3, tương đương với AES-192 và cung cấp biên an toàn rộng hơn đáng kể. Kyber-1024 đạt NIST Level 5 – mức cao nhất trong bảng phân loại NIST, tương đương với AES-256 và là biến thể Signal Protocol chọn cho PQXDH.

Việc PQXDH chọn Kyber-1024 thay vì Kyber-512 hay Kyber-768 phản ánh triết lý bảo mật thận trọng: trong bối cảnh mật mã hậu lượng tử còn tương đối mới và các kỹ thuật tấn công mạng lưới đang tiếp tục cải thiện, biên an toàn lớn hơn là ưu tiên hàng đầu ngay cả khi chi phí về kích thước và hiệu suất cao hơn. Kích thước bản mã Kyber-1024 (1568 byte) so với X25519 (32 byte) là sự đánh đổi đáng kể về băng thông, nhưng với việc PQXDH chỉ dùng Kyber cho giai đoạn thiết lập phiên ban đầu (không phải mỗi tin nhắn), chi phí này xảy ra tương đối ít và hoàn toàn chấp nhận được trong thực tế.

Phân tích ước lượng bảo mật và heuristics

Ước lượng bảo mật cụ thể của Kyber-1024 – khoảng 230–256 bit bảo mật lượng tử – dựa trên phân tích chi phí của các thuật toán tấn công mạng lưới hiệu quả nhất hiện tại. Thuật toán BKZ (Block Korkin–Zolotarev) với tham số khối β là phương pháp tấn công mạng lưới hiệu quả nhất được biết. Với một ma trận mạng lưới kích thước nhất định, chi phí của BKZ có thể được ước tính theo β, và từ đó ước tính số phép tính cần thiết để phá vỡ Module-LWE với các tham số cụ thể của Kyber.

Điểm tế nhị quan trọng là ước tính bảo mật mạng lưới là heuristic (ước lượng kinh nghiệm), không phải bằng chứng hình thức. Phân tích bảo mật mạng lưới dựa trên giả thuyết Geometric Series Assumption về hành vi của thuật toán BKZ, và các cải tiến trong thuật toán tấn công có thể giảm bảo mật ước tính. Trên thực tế, bảo mật ước tính của Kyber đã được điều chỉnh nhẹ (giảm khoảng 5–10 bit) qua các vòng phân tích trong cuộc thi NIST khi có các cải tiến nhỏ trong thuật toán tấn công. Đây là lý do tại sao Kyber-1024 cung cấp biên rộng ở NIST Level 5 thay vì cố gắng đạt chính xác 128 bit lượng tử: biên rộng hơn đảm bảo rằng các cải tiến tấn công trong tương lai không làm giảm bảo mật xuống dưới ngưỡng chấp nhận được.

Điểm yếu và phân tích mật mã

Bảy năm trong cuộc thi NIST đã đặt Kyber dưới áp lực phân tích mật mã khổng lồ từ cộng đồng toàn cầu. Không có tấn công nào phá vỡ bảo mật cơ bản của Kyber được tìm ra. Tuy nhiên, một số điểm cần lưu ý:

Phân tích kênh bên (side-channel analysis) là mối lo ngại thực tế hơn tấn công thuần túy toán học. Triển khai giải mã Kyber – đặc biệt là bước kiểm tra mã hóa lại ct == ct’ – có thể rò rỉ thông tin qua thời gian thực thi, tiêu thụ điện năng hay bức xạ điện từ nếu không được triển khai thời gian cố định. Một số công trình nghiên cứu gần đây đã chứng minh tấn công kênh bên thực tế trên một số triển khai Kyber không được bảo vệ đúng cách, trong đó kẻ tấn công đo thời gian so sánh ct và ct’ để suy ra bit khóa riêng. Các thư viện triển khai Kyber tiêu chuẩn như CRYSTALS-Kyber reference implementation, libpqcrypto, và Open Quantum Safe đều sử dụng so sánh thời gian cố định; tuy nhiên, đây là điểm quan trọng cần kiểm tra kỹ trong bất kỳ triển khai tùy chỉnh nào.

Cuộc tấn công ROLLO và Rainbow trong cuộc thi NIST (phá vỡ một số ứng viên khác) cho thấy rằng ngay cả các sơ đồ được phân tích kỹ vẫn có thể có điểm yếu không ngờ tới. Kyber may mắn không bị ảnh hưởng bởi các cuộc tấn công đó, nhưng cộng đồng mật mã khuyến nghị thực hành crypto agility – thiết kế hệ thống sao cho có thể thay thế thuật toán KEM mà không cần thay đổi toàn bộ kiến trúc, trong trường hợp điểm yếu được tìm thấy trong tương lai.

Hiệu suất và so sánh thực tiễn

Hiệu suất của Kyber trong các điều kiện thực tế là một trong những yếu tố chính dẫn đến sự lựa chọn của NIST và Signal Protocol.

Hiệu suất trên các nền tảng khác nhau

Trên phần cứng máy tính để bàn hiện đại (CPU x86-64 như Intel Core i7 hay AMD Ryzen) không dùng tối ưu hóa đặc biệt, Kyber-1024 đạt khoảng 20.000–30.000 thao tác KeyGen mỗi giây và thông lượng tương tự cho Encapsulate và Decapsulate. Với tối ưu hóa AVX2 (Advanced Vector Extensions), thông lượng tăng lên khoảng 3–5 lần nhờ tính toán NTT song song trên 8 hoặc 16 phần tử cùng lúc. So sánh, X25519 đạt khoảng 200.000–500.000 thao tác mỗi giây trên cùng phần cứng – Kyber chậm hơn khoảng 10–20 lần. Tuy nhiên, trong bối cảnh PQXDH, thao tác KEM chỉ xảy ra một lần khi thiết lập phiên ban đầu, không phải mỗi tin nhắn, nên độ trễ tuyệt đối (thường dưới 1 mili giây) hoàn toàn chấp nhận được cho ứng dụng nhắn tin.

Trên phần cứng điện thoại ARM Cortex-A (điển hình trong smartphone tầm trung trở lên), Kyber-1024 đạt khoảng 5.000–15.000 thao tác mỗi giây tùy theo thiết bị và tối ưu hóa. Phần cứng ARM hiện đại (Cortex-A55, Cortex-A78) hỗ trợ tập lệnh NEON cho phép song song hóa NTT, cải thiện hiệu suất đáng kể so với code C thuần túy. Trên vi điều khiển (Cortex-M4 hay M33 điển hình trong thiết bị IoT), Kyber-1024 chậm hơn nhiều – khoảng 100–500 thao tác mỗi giây – nhưng vẫn khả thi cho các ứng dụng không yêu cầu thông lượng cao.

Kích thước dữ liệu là thách thức thực tế quan trọng hơn tốc độ tính toán. Bản mã Kyber-1024 (1568 byte) cộng với khóa công khai (1568 byte) trong tin nhắn ban đầu PQXDH tạo ra overhead tổng cộng hơn 3 KB so với vài chục byte của X3DH thuần túy. Trong môi trường mạng tốt, 3 KB thêm là không đáng kể. Tuy nhiên, trong môi trường mạng kém (3G chậm, kết nối vệ tinh, khu vực nông thôn) hay khi phiên ban đầu xảy ra đồng thời với nhiều người dùng trên cùng cơ sở hạ tầng, overhead này có thể ảnh hưởng đến trải nghiệm người dùng và cần được xem xét khi thiết kế hệ thống.

So sánh với các ứng viên KEM hậu lượng tử khác

So với NTRU – một ứng viên lâu đời hơn cũng dựa trên mạng lưới – Kyber có bằng chứng bảo mật quy về bài toán worst-case rõ ràng hơn (NTRU thiếu bằng chứng này), kích thước bản mã tương đương nhưng thiết kế đơn giản và dễ kiểm toán hơn. Một số biến thể NTRU cũng bị phát hiện có lỗ hổng trong cuộc thi NIST (NTRU-Prime vẫn an toàn nhưng NTRU-HPS bị rút lui), trong khi Kyber duy trì bảo mật ổn định qua tất cả các vòng.

So với McEliece – hệ thống mật mã dựa trên mã sửa lỗi được đề xuất từ năm 1978 và được NIST tiêu chuẩn hóa đợt hai – Kyber có bảo mật dựa trên bài toán khác (mạng lưới thay vì giải mã mã sửa lỗi), có khóa công khai và bản mã nhỏ hơn nhiều (1568 byte so với hàng trăm KB của McEliece), nhưng McEliece có lợi thế về tuổi đời – đã được nghiên cứu 45 năm mà không bị phá vỡ. Signal Protocol chọn Kyber vì kích thước nhỏ hơn phù hợp với tin nhắn di động, nhưng các hệ thống yêu cầu bảo mật tối đa với kích thước khóa không phải ưu tiên (như phần mềm máy chủ) có thể xem xét McEliece như một lựa chọn thay thế.

So với SABER – một ứng viên dựa trên Module Learning With Rounding (Module-LWR) tương tự Module-LWE – Kyber có bằng chứng bảo mật chặt chẽ hơn và được phân tích nhiều hơn. SABER bị loại khỏi vòng cuối NIST một phần vì khoảng cách phân tích mật mã so với Kyber và một phần vì hiệu suất trên một số nền tảng thấp hơn Kyber.

Tích hợp với PQXDH và những cân nhắc thực tế

Việc tích hợp Kyber vào PQXDH không phải là ghép đơn giản hai hệ thống lại với nhau – đặc tả PQXDH định nghĩa cẩn thận cách bí mật chung Kyber SS được kết hợp với các đầu ra DH và ràng buộc vào ngữ cảnh cụ thể của phiên.

Cách Kyber kết hợp với DH trong PQXDH

Trong PQXDH, Mỹ Anh thực hiện PQKEM–ENC(PQPKB) để nhận (CT, SS), trong đó SS là bí mật chung Kyber 32 byte. Sau đó, SK được tính là KDF(DH1 || DH2 || DH3 || DH4 || SS) – SS được nối vào cuối chuỗi các đầu ra DH trước khi đưa qua HKDF. Cấu trúc nối đơn giản này có một tính chất bảo mật quan trọng: nếu cả DH lẫn Kyber đều an toàn, SK an toàn. Nếu chỉ một trong hai an toàn, SK vẫn an toàn. Đây là tính chất lai (hybrid) cổ điển: kết hợp hai hệ thống độc lập đảm bảo rằng kẻ tấn công phải phá vỡ đồng thời cả hai mới tính được SK. Thuật toán Shor phá vỡ DH nhưng không phá vỡ Module-LWE; không có thuật toán lượng tử nào được biết phá vỡ Module-LWE; do đó SK vẫn bảo mật trước đối thủ lượng tử thụ động.

Yêu cầu về PQPKB trong AD: như đã đề cập, nếu Kyber không tự ràng buộc khóa công khai vào bí mật chung (Kyber thực tế có thông qua H(pk) trong đóng gói, nhưng đặc tả PQXDH cẩn thận yêu cầu tường minh), EncodeKEM(PQPKB) phải được thêm vào AD của AEAD. Điều này ràng buộc bản mã AEAD với đúng khóa KEM được dùng, ngăn chặn tấn công tái mã hóa từ phía ngoài Kyber. Trong thực tế, Kyber-1024 đã ràng buộc pk vào K thông qua H(pk) trong thuật toán Encapsulate, nên tấn công tái mã hóa thực tế không khả thi. Nhưng đặc tả PQXDH vẫn yêu cầu thêm EncodeKEM(PQPKB) vào AD để bảo vệ phòng thủ sâu trong trường hợp sơ đồ KEM được thay thế bằng một sơ đồ khác không có tính chất này.

Quản lý khóa KEM trong thực tế

Vòng đời khóa KEM trong PQXDH song hành với vòng đời khóa đường cong elliptic nhưng có thêm chi phí về lưu trữ và truyền tải. Đan Nguyên phải tải lên và lưu trữ: một PQSPKB (last-resort, 1568 byte khóa công khai) cùng chữ ký; và nhiều PQOPKB một lần (mỗi cái 1568 byte khóa công khai cộng chữ ký). Với kho PQOPKB thông thường gồm 100–200 khóa, tổng dung lượng lưu trữ phía máy chủ cho thành phần KEM của Đan Nguyên là khoảng 200–400 KB – tăng đáng kể so với X3DH thuần túy nhưng vẫn hoàn toàn trong tầm của hạ tầng máy chủ hiện đại.

Chi phí tính toán khi tải lên khóa cũng cần xem xét: mỗi PQOPKB cần được ký bằng IKB (thao tác XEdDSA), nên việc tạo và ký 100 PQOPKB một lần mất khoảng 5–10 mili giây trên điện thoại hiện đại – không đáng kể trong thực tế. Thao tác PQKEM–ENC trong tin nhắn ban đầu cũng chỉ tốn vài mili giây. Chi phí đáng kể hơn là truyền tải bản mã Kyber-1024 (1568 byte) trong tin nhắn ban đầu; trong điều kiện mạng 3G hay 4G điển hình, 1568 byte thêm tương đương với khoảng 10–50 mili giây độ trễ phụ – hoàn toàn chấp nhận được cho thiết lập phiên ban đầu.

Kết luận

CRYSTALS-Kyber đại diện cho trạng thái nghệ thuật hiện tại trong thiết kế cơ chế đóng gói khóa hậu lượng tử: kết hợp nền tảng lý thuyết vững chắc (Module-LWE với quy giảm worst-case), bảo mật chủ động đầy đủ (IND-CCA2 trong QROM), kích thước dữ liệu nhỏ gọn và hiệu suất cao trong phần cứng hiện đại. Bảy năm phân tích cộng đồng trong cuộc thi NIST mà không tìm được điểm yếu đáng lo ngại là bằng chứng mạnh về độ tin cậy của thiết kế.

Trong PQXDH, Kyber-1024 là thành phần cốt lõi chuyển đổi X3DH từ an toàn trước đối thủ cổ điển sang an toàn trước đối thủ lượng tử thụ động. Không có thuật toán lượng tử nào được biết có thể giải Module-LWE hiệu quả; ngay cả thuật toán Shor mạnh mẽ cũng không áp dụng được cho cấu trúc mạng lưới. Điều này đảm bảo rằng kể cả khi máy tính lượng tử đủ mạnh xuất hiện trong tương lai, các phiên PQXDH thiết lập hôm nay vẫn bảo mật trước chiến lược thu thập trước giải mã sau.