Применяется ли алгоритм Гровера (или любой другой применимый квантовый алгоритм) только к ослаблению самой хеш-функции или он также может искать только правдоподобные входные данные (a-z, A-Z, 0-9 <= 14 символов) для уменьшения пространства поиска?
Метод Гровера - это общий метод поиска - он не знает и не заботится о том, как заданная функция интерпретирует входные данные. Если вы дадите ему функцию, которая интерпретирует входные данные как "(a-z, A-Z, 0-9 <= 14 символов)", она будет работать с ожидаемой сложностью.
С другой стороны, уместным может быть вопрос «имеет ли экономический смысл использование квантового компьютера, в отличие от фермы графических процессоров или некоторых ASIC?» Я предполагаю, что в течение следующих нескольких десятилетий (то есть до тех пор, пока технология квантовых компьютеров не преодолеет ряд поколений) классические методы в этом случае будут быстрее.
Некоторые из причин этого:
Можно ожидать, что стоимость операции квантовых вычислений составит много больше, чем стоимость соответствующего классического. Это постоянный коэффициент при сравнении двух, однако, если этот постоянный коэффициент, возможно, равен миллиарду или триллиону, его действительно не следует игнорировать.
Распараллеливание — классические компьютерные поиски (такие как этот) идеально парализуемы (чем может воспользоваться ферма GPU или набор ASIC). Напротив, алгоритм Гровера (или любой аналогичный поиск в Quantum Oracle) не работает — вы понимаете, что $n^2$ ускориться, если вы можете выполнить $ О (п) $ последовательные операции. Однако, если вы не можете ждать так долго и вам нужно реализовать несколько квантовых компьютеров для выполнения поиска, вы не получите этого. $n^2$ ускориться между ними. Например, чтобы выполнять поиск в 100 раз быстрее, вам нужно в 10 000 раз больше квантовых компьютеров.
Повторное использование ключа поиска. С помощью классических вычислений мы можем сгенерировать таблицу Rainbow — генерация этой таблицы занимает примерно столько же времени, сколько и полный поиск; однако, как только это будет сделано, повторный поиск по различным хэшированным паролям будет дешевым. Напротив, запуск алгоритма Гровера будет выполнять поиск по одному паролю — если мы хотим проверить другой хэш, нам придется снова платить за полный поиск. Конечно, вы можете построить таблицу Rainbow на квантовом компьютере; однако я не верю, что вы получите какое-либо квантовое ускорение, и я не слышал об альтернативе, в которой вы могли бы получить квантовое ускорение.
Теперь, со временем, мы можем обоснованно ожидать, что стоимость квантовых компьютеров будет снижаться (и снижаться быстрее, чем сравнительная стоимость классических вычислений), и мы можем ожидать, что квантовые компьютеры со временем станут быстрее (следовательно, потребуется меньше распараллеливания); Я просто не ожидаю, что какая-либо тенденция произойдет за одну ночь...
Чтобы было ясно, я понимаю, что любая голая функция хэширования (даже с излишне длинными выходными данными, такими как SHA-512) — это ужасный способ хранения паролей пользователей, и следует использовать Argon2 или аналогичный, но я подумал, что жесткость памяти и другие аспекты могут сделать вопрос слишком широк или ответ менее широко применим.
С нашим нынешним пониманием компромиссов, присущих квантовому компьютеру (которые могут быть значительно нестандартными), квантовому компьютеру будет довольно сложно иметь дело с жесткой функцией памяти. Вычисление такой хеш-функции потребует большой квантовой памяти, и (насколько нам известно) это выглядит ужасно дорого [1].
Алгоритм Гровера был бы применим (опять же, ему все равно, что такое хеш-функция); однако это, казалось бы, довольно дорого.
Итак, если предположить, что наши догадки верны, жесткая хэш-функция памяти (Argon2) будет даже более устойчива к квантовым вычислениям, чем простые хеш-функции.
[1]: Я считаю, что по крайней мере отчасти причина в том, что если у вас есть большая квантовая память и доступ к ней осуществляется по запутанному адресу, вы в конечном итоге выполняете операции с каждой отдельной ячейкой памяти (или, по крайней мере, с каждой отдельной ячейкой, которая может быть адресуется запутанным адресом). Напротив, с классической памятью вам нужно получить доступ только к адресуемой ячейке. Если мы говорим о памяти с 1 000 000 адресуемых ячеек, это означает, что квантовой памяти может потребоваться выполнить в 1 000 000 раз больше операций по сравнению с классическим случаем.
