Tôi tự hỏi liệu người ta có thể áp dụng thuật toán Grover trên cơ chế đóng gói khóa để bẻ khóa được chia sẻ hay không.
Đây là cách thuật toán của Grover hoạt động (đơn giản hóa): bạn sử dụng hàm 'fitness' (hàm này đoán giá trị mà bạn đang tìm kiếm và ước tính thành '1' nếu dự đoán đúng và '0' nếu không - đối với AES, chức năng phù hợp có thể là 'sử dụng dự đoán làm khóa AES và mã hóa khối bản rõ đã biết và kiểm tra xem kết quả có phải là khối bản mã đã biết hay không).
Sau đó, bạn thực hiện chức năng phù hợp này (và một số phép toán Lượng tử khác) và lặp lại nó nhiều lần - nếu bạn lặp lại đúng số lần, thì khi bạn đo kết quả, có khả năng cao đó là giá trị phù hợp hàm đánh giá bằng 1.
Bây giờ, nếu chúng ta cân nhắc tấn công Frodo, có hai cách để tấn công nó. Người ta có thể cố gắng khôi phục bí mật được chia sẻ trực tiếp từ các chia sẻ khóa công khai; trong trường hợp này, chúng tôi có sẵn cho chức năng tập thể dục chia sẻ khóa công khai và dự đoán của chúng tôi về bí mật được chia sẻ. Tuy nhiên, chúng tôi không có cách hiệu quả để kiểm tra xem dự đoán đó có chính xác hay không (dựa trên chia sẻ khóa công khai) và vì vậy chúng tôi không biết cách xây dựng chức năng thể dục này (và do đó, Grover's dường như không áp dụng).
Mặt khác, chúng ta có thể thử khôi phục hạt giống bí mật mà Frodo đã sử dụng để lấy khóa công khai [1] (hoặc cách khác, trong quy trình đóng gói của Frodo). Đối với Frodo-640 (NIST cấp 1), hạt giống bí mật này là 128 bit; vì người ta có thể xác định ánh xạ giữa giá trị 128 bit này (và dữ liệu công khai, nghĩa là hạt giống công khai) và khóa chung, chúng tôi có thể sử dụng giá trị đó để tạo hàm thể dục.
Bây giờ, cuộc tấn công này không phải là vốn có của mật mã hậu lượng tử; nó hoạt động không phải bằng cách tấn công trực tiếp bí mật được chia sẻ 128 bit, mà thay vào đó là cách bộ thông số này của Frodo tạo ra các chia sẻ khóa của nó, sử dụng giá trị ngẫu nhiên 128 bit làm 'hạt giống bí mật'. Những gì Frodo làm là lấy hạt giống bí mật 128 bit đó và mở rộng nó bằng cách sử dụng SHAKE để tạo ra các vectơ lỗi và chia sẻ dài hơn nhiều; các nhà thiết kế của Frodo có thể đã sử dụng một hạt giống bí mật dài hơn và mở rộng hạt giống đó thành LẮC - điều này sẽ gây khó khăn hơn nhiều cho Grover (vì hạt giống bí mật để phục hồi lâu hơn nhiều và việc cố gắng khôi phục trạng thái LẮC bên trong hoặc chuỗi kết quả LẮC sẽ cũng mất nhiều thời gian). Các nhà thiết kế của Frodo đã không làm điều này, có lẽ vì nó không thực sự cải thiện tính bảo mật.
Mặt khác, chúng tôi thường làm điều gì đó với khóa được chia sẻ; chúng tôi có thể cung cấp dữ liệu đó vào KDF (có thể cùng với một số dữ liệu công khai, chẳng hạn như nonce), sau đó sử dụng kết quả đó làm khóa AES. Chúng ta có thể xây dựng một chức năng phù hợp dựa trên đó và do đó, Grover sẽ áp dụng cho hệ thống đó - rất có thể, việc xây dựng KDF/AES này sẽ đơn giản hơn để triển khai trong Máy tính lượng tử so với quy trình (hoặc đóng gói) khóa công khai của Frodo; do đó, việc tấn công hệ thống ở đó có thể dễ dàng hơn (nếu chỉ bằng một yếu tố không đổi).
Mặt khác, thật hợp lý khi đặt câu hỏi liệu Grover's có thực sự là mối đe dọa đối với bí mật 128 bit hay không - tất cả các đánh giá chức năng thể dục này đều được thực hiện tuần tự và sẽ không thực tế để đánh giá bất kỳ chức năng nào $2^{64}$ Lần liên tiếp. Và, trong khi bạn có thể cố gắng giải quyết vấn đề này bằng cách chạy Grover's trên một số lượng lớn Máy tính lượng tử bằng cách chia nhỏ không gian bí mật, thì chúng ta sẽ mất một phần lợi thế của Grover nếu làm điều đó, và vì vậy cuối cùng chúng ta sử dụng một nhiều của Máy tính lượng tử.
[1]: Lưu ý rằng Frodo có hai hạt giống; một công khai xác định mạng sẽ được sử dụng và một mạng bí mật và được sử dụng để tạo ma trận mẫu và lỗi; vì hạt giống công khai nằm trong khóa chung, nên kẻ tấn công không cần phải đoán điều đó; tất cả những gì anh ta cần làm là thu hồi hạt giống bí mật.
