Есть ли какое-то определение или теорема о том, чего может достичь квантовый компьютер, с помощью которого постквантовые криптографические схемы (например, решеточная криптография, но не квантовая криптография) могут оправдать их безопасность? Я знаю, что функция поиска периода способна взломать RSA и дискретные журналы, но является ли это единственным алгоритмом, применимым для взлома схем шифрования? Могу ли я сказать, что если схема не восприимчива к функции определения периода, она не подвержена квантовым вычислениям? Если нет, существует ли какое-либо подобное альтернативное утверждение вида «если схема шифрования не может быть нарушена алгоритмом X, она не может быть нарушена квантовыми вычислениями»?
Например, достаточно ли доказать, что схема шифрования может быть взломана только путем попытки всех возможных ключей, и лучшее, что квантовые вычисления могут сделать в этом отношении, - это время поиска с квадратным корнем с помощью алгоритма Гровера?
источник
Ответы:
По сути, это область классов вычислительной сложности. Например, класс BQP можно грубо описать как совокупность всех проблем, которые могут быть эффективно решены на квантовом компьютере. Сложность с классами сложности состоит в том, что трудно доказать разделение между многими классами, то есть существование проблем, которые находятся в одном классе, но не в другом.
В некотором смысле достаточно уметь сказать «если этот квантовый алгоритм не может его сломать, он безопасен», вам просто нужно использовать правильный алгоритм. Вам нужен BQP-полный алгоритм, такой как поиск корней полинома Джонса - любой квантовый алгоритм может быть приведен как экземпляр BQP-полного алгоритма. Однако то, как этот алгоритм может быть использован для взлома, совершенно неясно и нетривиально. Недостаточно видеть, что вы не можете напрямую грубо насиловать вещи. Таким образом, такой подход, вероятно, не так полезен.
Что мы хотим от постквантового криптосценария? Нам нужно:
Этот последний пункт является (по существу) определением класса сложности NP: проблемы, для которых может быть трудно найти решение, но решение для которых легко проверить, когда дано доказательство (соответствующее закрытому ключу в нашем случае) ,
Итак, что нам нужно, так это проблемы в NP, но не в BQP. Поскольку мы не знаем, если NP = BQP, мы не знаем, что такие вещи существуют. Однако есть хороший путь для поиска решений: мы рассматриваем NP-полные проблемы. Это самые тяжелые случаи проблем в NP, так что если BQP≠ NP (что, как широко распространено мнение, имеет место), NP-полные проблемы, конечно, не в BQP. (Если задача для класса сложности завершена, это означает, что если вы можете решить ее эффективно, вы можете эффективно решить все экземпляры класса.) Таким образом, это своего рода руководство, где можно искать постквантовые алгоритмы. ,
Однако дополнительная тонкость, которая усложняет ситуацию, заключается примерно в том (что я не эксперт), что классы сложности говорят о сложности наихудшего случая, т. Е. Для данного размера задачи речь идет о том, насколько сложным является сложный случай проблемы. Но может быть только один такой экземпляр проблемы, который будет означать, что если мы исправим размер проблемы (как обычно, например, вы можете говорить о 1024-битном RSA; 1024-бит - это размер проблемы), то будет только один закрытый ключ. Если мы знаем это, перехватчик может просто использовать этот закрытый ключ для расшифровки сообщений. Итак, нам на самом деле нужно, чтобы рассуждения о сложности вычислений применялись для большой доли возможных входных данных. Это приводит вас в мир средней сложности, где, как я понимаю, делать такие заявления становится намного сложнее.
Это может помочь сделать сравнение с RSA, криптосистемой с открытым ключом, и игнорируя существование квантовых компьютеров. Он основан на сложности разложения больших составных чисел. Эта проблема не существует (как полагают) в P, поэтому для хакера с классическим компьютером трудно найти ответ. Между тем, оно в NP, потому что решение легко проверяется (если вам дан один фактор, вы можете легко проверить его). Это означает, что законный получатель может расшифровать его с помощью классического компьютера.
источник
Нет. Тот факт, что ваша пост-квантовая криптографическая схема работает сегодня, не означает, что Питер Шор не найдет квантовый алгоритм, чтобы сломать его завтра ".
Нет. Примером другого алгоритма является алгоритм Гровера, который имеет отношение к взлому криптосистем, основанных на проблеме трансцендентального логарифма .
Нет. Схемы, основанные на проблеме трансцендентального логарифма, не подвержены обнаружению периодов, но чувствительны к квантовым ускорениям.
Нет. Мы не знаем каждый квантовый алгоритм в возможном существовании. Даже если схема устойчива к нахождению периода и алгоритму Гровера, возможно, можно использовать квантовые компьютеры, чтобы сломать ее более эффективно, чем классические компьютеры. Возможно, нам просто нужно заинтересовать Питера Шора, чтобы придумать для него квантовую схему расширенного дешифрования.
Нет. Тот факт, что классический компьютер не может сломать вашу схему, кроме как с помощью всех возможных ключей, не означает, что квантовый компьютер не может.
Вот вопрос, на который есть ответ « да» :
Что мы можем сделать, чтобы доказать, что схема шифрования безопасна для квантовых компьютеров?
Ответ: Докажите, что дешифрование кода является сложной задачей QMA или QMA. Трудные проблемы QMA - это проблемы, которые сложны для квантовых компьютеров, так же как трудные проблемы NP трудны для классических компьютеров.
Это вдохновило меня задать этот вопрос, на который я не знаю ответа!
источник