Có phải thuật toán Grover (hoặc bất kỳ thuật toán lượng tử áp dụng nào khác) chỉ áp dụng để làm suy yếu chính hàm băm hay nó cũng có thể chỉ tìm kiếm các đầu vào hợp lý (a-z, A-Z, 0-9 <= 14 ký tự) để giảm không gian tìm kiếm?
Grover's là một phương pháp tìm kiếm chung - nó không biết hoặc không quan tâm đến cách chức năng được đưa ra diễn giải đầu vào. Nếu bạn cung cấp cho nó một hàm diễn giải các đầu vào là "(a-z, A-Z, 0-9 <=14 ký tự)", thì nó sẽ hoạt động với nó, với độ phức tạp dự kiến.
Mặt khác, câu hỏi liên quan có thể là "việc sử dụng Máy tính lượng tử có ý nghĩa kinh tế, trái ngược với trang trại GPU hoặc một số ASIC?" Tôi đề nghị trong vài thập kỷ tới (nghĩa là cho đến khi công nghệ Máy tính lượng tử trải qua một số thế hệ), các phương pháp cổ điển sẽ nhanh hơn trong trường hợp này.
Một số lý do cho việc này:
Chi phí của một hoạt động Điện toán lượng tử có thể được dự kiến là nhiều lớn hơn chi phí của một cổ điển tương ứng. Đây là một yếu tố không đổi khi so sánh cả hai - tuy nhiên, nếu yếu tố không đổi này có lẽ là một tỷ hoặc một nghìn tỷ, thì thực sự không nên bỏ qua.
Song song hóa - các tìm kiếm trên máy tính cổ điển (như cái này) hoàn toàn có thể song song hóa (mà một trang trại GPU hoặc bộ ASIC sẽ tận dụng tối đa). Ngược lại, thuật toán của Grover (hoặc bất kỳ tìm kiếm Quantum Oracle tương tự nào) thì không - bạn hiểu rằng $n^2$ tăng tốc nếu bạn có thể thực hiện $O(n)$ các thao tác nối tiếp nhau. Tuy nhiên, nếu bạn không thể đợi lâu như vậy và cần triển khai nhiều Máy tính lượng tử để thực hiện tìm kiếm, thì bạn sẽ không nhận được điều đó $n^2$ tăng tốc giữa chúng. Ví dụ: để thực hiện tìm kiếm nhanh hơn 100 lần, bạn cần số lượng Máy tính lượng tử gấp 10.000 lần.
Tái sử dụng tìm kiếm chính. Với tính toán cổ điển, chúng ta có thể tạo bảng Cầu vồng - việc tạo bảng đó mất khoảng thời gian tìm kiếm đầy đủ; tuy nhiên, sau khi hoàn thành, việc thực hiện tìm kiếm lặp lại trên các mật khẩu băm khác nhau sẽ không tốn kém. Ngược lại, việc chạy thuật toán của Grover sẽ thực hiện tìm kiếm trên một mật khẩu duy nhất - nếu chúng tôi muốn kiểm tra một hàm băm khác, chúng tôi phải trả tiền cho toàn bộ quá trình tìm kiếm lại. Tất nhiên, bạn có thể xây dựng một bảng Rainbow trên Máy tính lượng tử; tuy nhiên, tôi không tin rằng bạn sẽ tăng được bất kỳ tốc độ Lượng tử nào và tôi chưa nghe nói về một giải pháp thay thế mà bạn sẽ tăng tốc Lượng tử.
Giờ đây, theo thời gian, chúng ta có thể kỳ vọng một cách hợp lý rằng chi phí của Máy tính lượng tử sẽ giảm (và giảm nhanh hơn so với chi phí so sánh của điện toán cổ điển) và chúng ta có thể kỳ vọng Máy tính lượng tử sẽ nhanh hơn theo thời gian (do đó yêu cầu ít song song hóa hơn); Tôi chỉ không mong đợi một trong hai xu hướng xảy ra trong đêm ...
Nói rõ hơn, tôi hiểu rằng bất kỳ chức năng băm trần nào (ngay cả với các đầu ra dài không cần thiết như SHA-512) đều là một cách tệ hại để lưu trữ mật khẩu người dùng và nên sử dụng Argon2 hoặc tương tự, nhưng tôi nghĩ rằng độ cứng của bộ nhớ và các khía cạnh khác có thể khiến câu hỏi quá rộng hoặc một câu trả lời ít áp dụng rộng rãi.
Với sự hiểu biết hiện tại của chúng tôi về sự đánh đổi vốn có trong Máy tính lượng tử (có thể là không có cơ sở đáng kể), một chức năng cứng của bộ nhớ sẽ khá khó khăn đối với Máy tính lượng tử. Việc đánh giá một hàm băm như vậy có vẻ sẽ yêu cầu một bộ nhớ Lượng tử lớn và (theo những gì chúng tôi biết) có vẻ rất tốn kém [1].
Thuật toán của Grover sẽ được áp dụng (một lần nữa, nó không quan tâm hàm băm là gì); tuy nhiên nó có vẻ khá đắt.
Vì vậy, giả sử rằng những dự đoán của chúng tôi là chính xác, hàm băm bộ nhớ cứng (Argon2) thậm chí sẽ có khả năng chống lại Điện toán lượng tử cao hơn so với các hàm băm đơn giản.
[1]: Tôi tin rằng ít nhất một phần lý do là nếu bạn có Bộ nhớ lượng tử lớn và truy cập nó cho một địa chỉ vướng víu, thì cuối cùng bạn sẽ thực hiện các thao tác trên từng ô nhớ (hoặc ít nhất, mọi ô đơn lẻ có thể là được xử lý bởi địa chỉ vướng víu). Ngược lại, với bộ nhớ cổ điển, bạn chỉ cần truy cập vào ô đang được đánh địa chỉ. Nếu chúng ta đang nói về một bộ nhớ có 1.000.000 vị trí có thể định địa chỉ, thì điều này có nghĩa là Bộ nhớ lượng tử có thể cần thực hiện gấp 1.000.000 lần số thao tác so với trường hợp cổ điển.
