Thuật toán Grover: Chỉ tăng tốc √n
Không giống tăng tốc theo cấp số mũ của Shor cho phân tích thừa số, tìm kiếm Grover chỉ cung cấp lợi thế bậc hai. 2^128 → 2^64 phép tính.
Số Qubit
Kéo thanh trượt để mô phỏng việc mở rộng máy tính lượng tử
2.000
qubit logic
10010,000
LỖ HỔNG KHÓA RSA (1/5 bị phá)
RSA-512
BỊ PHÁ
RSA-1024
AN TOÀN
RSA-2048
AN TOÀN
RSA-3072
AN TOÀN
RSA-4096
AN TOÀN
ML-KEM (tất cả cấp độ)
LUÔN AN TOÀNKhông tồn tại ngưỡng qubit — bài toán lưới không có giải pháp lượng tử hiệu quả
RSA / ECC Cổ Điển
DỄ BỊ TẤN CÔNGThuật toán Shor sử dụng tìm chu kỳ lượng tử để phân tích thừa số nhanh hơn theo cấp số mũ so với bất kỳ thuật toán cổ điển nào. Bước then chốt là lũy thừa modular trong chồng chập, tiếp theo là QFT. Điều này phá vỡ RSA, vốn dựa vào độ khó của việc phân tích thừa số.
Nhập một số từ 2 đến 999
CÁC BƯỚC THUẬT TOÁN
Nhập một số ở trên để mô phỏng thuật toán Shor
Hậu Lượng Tử (ML-KEM)
AN TOÀNML-KEM (trước đây là CRYSTALS-Kyber), được chuẩn hóa trong NIST FIPS 203, dựa trên bài toán lưới MLWE. Ngay cả máy tính lượng tử với thuật toán Grover cũng chỉ đạt được tăng tốc √n — không đủ để phá vỡ.
TẠI SAO LƯỢNG TỬ KHÔNG THỂ PHÁ VỠ LƯỚI
Không có thuật toán lượng tử nào cho SVP
Bài toán Vector Ngắn Nhất trong lưới nhiều chiều không có thuật toán lượng tử hiệu quả — khác với phân tích thừa số nguyên.
Nhiễu che giấu bí mật
LWE thêm nhiễu Gauss vào tính toán lưới. Ngay cả với chồng chập lượng tử, nhiễu ngăn cản việc trích xuất khóa bí mật.
SO SÁNH TĂNG TỐC CỦA GROVER
Tìm kiếm vét cạn cổ điển2128 ≈ 3.40×1038
Tìm kiếm lượng tử Grover264 ≈ 1.84×1019
Vẫn còn 1,8×10^19 phép tính — hoàn toàn không khả thi ngay cả với máy tính lượng tử
CÁC CẤP ĐỘ BẢO MẬT ML-KEM
- ML-KEM-512AN TOÀN
- ML-KEM-768AN TOÀN
- ML-KEM-1024AN TOÀN
ML-KEM vẫn an toàn ở 2.000 qubit
Không có thuật toán lượng tử nào có thể giải hiệu quả bài toán lưới
Ref: NIST FIPS 203 (2024) · Grover (1996) · Regev (2005)