Giả sử rằng ai đó đã xây dựng một Máy tính lượng tử mật mã (CQC) đặc biệt có thể chạy thuật toán Grover.Thuật toán của Grover là tối ưu tiệm cận mà người ta cần $\mathcal{O}(\sqrt{n})$-thời gian cho $n$ bảo mật bit để tấn công trước hình ảnh hoặc tìm kiếm chính. Đó là một cái có bảo mật 128 bit từ không gian khóa 256 bit. Đây là quảng cáo của thuật toán Grover, vâng, nó có $\mathcal{O}(\log{n})$-space, tuy nhiên, điều này là không đủ.
Điều thường thiếu là $\mathcal{O}(\sqrt{n})$ cuộc gọi của thuật toán Grover, hãy xem xét rằng bạn muốn phá vỡ 128-bit thì bạn cần chạy thuật toán Grover $2^{64}$-thời gian. Nếu chúng tôi cho rằng bạn có thể thực thi một thuật toán Grover trong một máy trong một giây thì bạn cần $\xấp xỉ 585$ năm để tìm chìa khóa. Điều này khá lạc quan theo nghĩa là người ta có thể chuẩn bị QCQ trong một nano giây.
Thuật toán Grover, giống như thuật toán cổ điển có thể được song song hóa, quá. Chà, thật thú vị, vì $k$ song song Grover chúng ta không có tăng bậc hai, chúng ta có $\sqrt{k}$ tăng tốc. Điều này không mở rộng quy mô tốt.
Đây là tất cả về Grover's, bây giờ có một tác phẩm khác từ Đồng thau và cộng sự. cho các hàm băm cho phát hiện va chạm, có $\mathcal{O}(\sqrt[3]{2^{256}})$-thời gian và $\approx \mathcal{O}(2^{85})$-khoảng trống. Điều đó vẫn ở mức tối ưu tiệm cận và lần này chúng ta có bảo mật 128-bit từ hàm băm 384-bit với $2^{128}$-yêu cầu về không gian.
Với những điều này, chúng ta có thể lập luận rằng ngay cả các hàm băm 256 bit và thậm chí mật mã khối 128 bit đều an toàn đối với CQC. Một tính toán thực tế hơn được thực hiện từ
Giữ chi tiết cho bài viết, hãy dán NIST và cho rằng chúng ta cần $384$Hàm băm -bit chống lại CQC để có khả năng chống va chạm 128 bit, khả năng chống ảnh trước là $192$-chút .
Nếu chúng tôi sử dụng HKDF 256-bit, nó sẽ có khả năng chống ảnh trước CQC 128-bit. Điều này có nghĩa là hàm băm 256 bit là đủ.
Kể từ TLS 1.3 đơn giản hóa hầu hết mọi thứ;
Hàm Hash được Transcript-Hash và HKDF sử dụng là thuật toán băm của bộ mật mã.
Lời giải thích có ý nghĩa là SHA-384 được chọn để có khả năng chống va chạm 128 bit phù hợp với khả năng chống va chạm 128 bit của AES-256. Một cách đơn giản, người ta có thể nói rằng AES_256_GCM_SHA384
có bảo mật 128 bit chống lại các đối thủ Lượng tử.