Mật mã học hậu lượng tử

Mật mã học hậu lượng tử phát triển các lược đồ khóa công khai mà tính bảo mật của chúng dựa trên các vấn đề được cho là khó ngay cả đối với máy tính lượng tử, thay thế RSA và mật mã đường cong elliptic mà thuật toán Shor có thể phá vỡ.

Definition

Mật mã học hậu lượng tử bao gồm các thuật toán mật mã cổ điển (không lượng tử) được thiết kế để duy trì tính bảo mật trước các đối thủ được trang bị máy tính lượng tử quy mô lớn, bằng cách dựa vào các vấn đề mà chưa có thuật toán lượng tử hiệu quả nào được biết đến.

Scope

Chủ đề này bao gồm mối đe dọa lượng tử (thuật toán Shor và Grover), các họ chính của lược đồ kháng lượng tử — dựa trên mạng tinh thể, dựa trên mã, dựa trên hàm băm và đa biến — nỗ lực tiêu chuẩn hóa của NIST và các thuật toán được chọn (ML-KEM, ML-DSA, SLH-DSA), và các mối quan tâm về di chuyển như 'thu hoạch ngay - giải mã sau' và triển khai lai. Nó không bao gồm mật mã lượng tử thực sự (phân phối khóa lượng tử), vốn sử dụng phần cứng lượng tử thay vì các thuật toán cổ điển.

Core questions

• Tại sao máy tính lượng tử phá vỡ RSA và mật mã đường cong elliptic nhưng không ảnh hưởng nghiêm trọng đến các mật mã đối xứng?
• Những vấn đề khó (mạng tinh thể, mã, hàm băm) nào được cho là có khả năng chống lại tấn công lượng tử?
• NIST đã chọn những lược đồ nào để tiêu chuẩn hóa, và những đánh đổi của chúng là gì?
• Mối đe dọa 'thu hoạch ngay - giải mã sau' là gì và tại sao nó tạo ra sự cấp bách?
• Các lược đồ hậu lượng tử và cổ điển được kết hợp như thế nào trong các triển khai lai trong quá trình di chuyển?

Key concepts

• Thuật toán Shor
• Thuật toán Grover
• Mật mã học dựa trên mạng tinh thể (học với lỗi)
• Mật mã học dựa trên mã
• Chữ ký dựa trên hàm băm
• ML-KEM (Kyber) và ML-DSA (Dilithium)
• Thu hoạch ngay - giải mã sau
• Tính linh hoạt mật mã
• Trao đổi khóa lai

Key theories

Mối đe dọa lượng tử từ thuật toán Shor

Thuật toán lượng tử của Shor phân tích số nguyên và tính toán logarit rời rạc trong thời gian đa thức, phá vỡ RSA, Diffie-Hellman và mật mã đường cong elliptic; thuật toán Grover chỉ tăng tốc tìm kiếm vét cạn theo cấp số nhân, do đó khóa đối xứng chỉ cần được tăng gấp đôi.

Các họ vấn đề khó lượng tử

Bảo mật hậu lượng tử được tìm kiếm trong các vấn đề như học với lỗi và các vấn đề vector ngắn nhất trong mạng tinh thể, giải mã các mã tuyến tính ngẫu nhiên và tính bảo mật của các hàm băm — không có thuật toán lượng tử hiệu quả nào được biết đến cho các vấn đề này.

Mechanisms

Các lược đồ mạng tinh thể như ML-KEM (có nguồn gốc từ CRYSTALS-Kyber) dựa trên việc đóng gói khóa vào độ khó của bài toán học với lỗi mô-đun, thêm các 'lỗi' ngẫu nhiên nhỏ mà chỉ khóa riêng tư mới có thể loại bỏ. Chữ ký dựa trên hàm băm (SLH-DSA/SPHINCS+) xây dựng chữ ký chỉ từ tính bảo mật của một hàm băm. Các lược đồ dựa trên mã ẩn một cấu trúc có thể giải mã trong một mã tuyến tính trông ngẫu nhiên. Việc di chuyển thường sử dụng các cấu trúc lai kết hợp một lược đồ cổ điển và một lược đồ hậu lượng tử để bảo mật được duy trì nếu một trong hai tồn tại.

Clinical relevance

Việc di chuyển đã và đang diễn ra trong các hệ thống đã triển khai: các trình duyệt lớn và thư viện TLS đã kích hoạt trao đổi khóa ML-KEM lai, các ứng dụng nhắn tin (PQXDH của Signal) và SSH đã thêm bắt tay hậu lượng tử, và các cơ quan tiêu chuẩn thúc giục các tổ chức kiểm kê mật mã và lập kế hoạch chuyển đổi. Rủi ro 'thu hoạch ngay - giải mã sau' có nghĩa là dữ liệu cần bảo mật dài hạn nên được bảo vệ chống lại tấn công lượng tử ngay hôm nay.

Evidence & guidelines

NIST đã hoàn thiện các tiêu chuẩn hậu lượng tử đầu tiên vào năm 2024: FIPS 203 (ML-KEM) cho đóng gói khóa, FIPS 204 (ML-DSA) và FIPS 205 (SLH-DSA) cho chữ ký. Hướng dẫn từ NIST, NSA (CNSA 2.0) và các cơ quan quốc gia đặt ra các mốc thời gian di chuyển. Thực hành tốt nhất trong quá trình chuyển đổi ưu tiên các lược đồ lai kết hợp các thuật toán hậu lượng tử và cổ điển.

History

Thuật toán của Peter Shor năm 1994 đã chỉ ra rằng máy tính lượng tử có thể phá vỡ các hệ thống khóa công khai thống trị, thúc đẩy việc tìm kiếm các giải pháp thay thế. Mật mã học dựa trên mạng tinh thể đã tiến bộ thông qua các kết quả độ khó trường hợp xấu nhất của Ajtai và bài toán học với lỗi của Regev (2005). NIST đã khởi động một quy trình tiêu chuẩn hóa công khai vào năm 2016; sau nhiều vòng, họ đã chọn CRYSTALS-Kyber và các thuật toán khác, công bố các tiêu chuẩn đầu tiên (FIPS 203-205) vào năm 2024.

Key figures

• Peter Shor
• Daniel J. Bernstein
• Tanja Lange
• Oded Regev
• Chris Peikert

Seminal works

• shor1997
• nist2024mlkem
• bernstein2017

Frequently asked questions

Đã có máy tính lượng tử nào có thể phá vỡ RSA chưa?

Chưa. Các máy tính lượng tử hiện tại còn quá nhỏ và nhiễu để chạy thuật toán Shor trên các kích thước khóa thực tế. Mối lo ngại là về các máy trong tương lai, kết hợp với thực tế là dữ liệu được mã hóa hôm nay có thể được lưu trữ và giải mã khi các máy đó tồn tại.

Mật mã học hậu lượng tử có yêu cầu phần cứng lượng tử không?

Không. Các lược đồ hậu lượng tử chạy trên máy tính cổ điển thông thường; chúng chỉ dựa vào các bài toán toán học được cho là khó ngay cả đối với những kẻ tấn công lượng tử. Phân phối khóa lượng tử, vốn sử dụng phần cứng lượng tử, là một cách tiếp cận riêng biệt.