Есть ли у криптографии термодинамические затраты?

19

Обратимые вычисления - это вычислительная модель, которая допускает только термодинамически обратимые операции. В соответствии с принципом Ландауэра, который гласит, что стирание небольшого количества информации высвобождает джоулей тепла, это исключает переходные функции, которые не являются взаимно-однозначными (например, булевы операторы AND и OR). Хорошо известно, что квантовые вычисления по своей природе обратимы, поскольку разрешенные операции в квантовых вычислениях представлены унитарными матрицами.kTln(2)

Этот вопрос о криптографии. Неформально понятие «обратимость» кажется анафемой для фундаментальных целей криптографии, что наводит на вопрос: «Имеет ли криптография присущие термодинамические издержки?»

Я считаю, что это другой вопрос, чем "Можно ли все сделать в квантовой?"

В своих примечаниях к лекции доктор Прескилл заявляет: «Существует общая стратегия для моделирования необратимых вычислений на обратимом компьютере. Каждый необратимый вентиль может быть симулирован вентилем Тофоли путем фиксации входных данных и игнорирования выходных данных. Мы накапливаем и сохраняем весь« мусор ». 'выходные биты, которые необходимы, чтобы полностью изменить этапы вычисления. "

Это говорит о том, что эти обратимые квантовые симуляции необратимых операций требуют ввода, а также некоторого «нуля» пространства. Затем операция генерирует вывод вместе с некоторыми «грязными» царапинами. Все операции обратимы по отношению к выводу плюс биты мусора, но в какой-то момент биты мусора «выбрасываются» и больше не рассматриваются.

Поскольку криптография зависит от существования односторонних функций с люком, альтернативное утверждение вопроса может быть следующим: «Существуют ли какие-либо односторонние функции с люком, которые могут быть реализованы с использованием только обратимых логических операций, без дополнительного пространства для царапин?» Если это так, возможно ли также ВЫЧИСЛИТЬ произвольную одностороннюю функцию с люком, используя только обратимые операции (и не выбрасывая пространство)?

rphv
источник
2
интересный вопрос.
Суреш Венкат
4
Предположительно, этот вопрос относится только к криптографии с открытым ключом. Разве симметричные криптосистемы (такие как DES) не могут быть полностью обратимыми?
Питер Шор
1
Черт, я написал этот последний комментарий слишком поздно ночью и испортил его. Что я должен был сказать, так это то, что термодинамические затраты не зависят от размера рабочего пространства для систем с открытым и закрытым ключами, поскольку вы можете просто выполнить обратимое вычисление, скопировав выходные биты (но не рабочее пространство) в вспомогательный объект. зарегистрироваться, а затем отменить исходное вычисление (не вычисляя все в пустом месте).
Джо Фицсимонс

Ответы:

14

Как я уже упоминал в моем комментарии выше, и как вы намекаете в этом вопросе, каждое вычисление можно сделать обратимым, и, просто сохраняя дополнительные биты, не возникает никаких внутренних термодинамических затрат.

Каждая схема, генерируемая с использованием вентилей Toffoli и вспомогательных средств для замены необратимых вентилей, становится настолько же эффективной для реверсирования, как и для вычислений, предполагая, что у вас есть доступ ко всем выходным битам. Это явно не относится к функциям, рассматриваемым в криптографии, поскольку многие вспомогательные элементы используются и отбрасываются. Сохраняя в секрете эти лишние биты, трудно вычислить обратное вычисление.

Тем не менее, путем обратимого вычисления функции, создания копии подмножества битов, соответствующих выходу, и затем инвертирования функции, общие затраты энергии для вычисления и инвертирования функции будут равны нулю, в то время как единственные понесенные затраты будут заключаться в создании копия выходных битов, которая зависит только от количества выходных битов, а не от вычисляемой функции. Это, безусловно, лучшее, что вы можете сделать, поскольку это стоит той же энергии, что и простая запись выходной строки в пустой регистр.

Обращаясь к вашему вновь сформулированному вопросу:

«Существуют ли какие-либо односторонние функции с люком, которые можно реализовать, используя только обратимые логические операции, без дополнительного пространства для заметок?»

Ответ тривиально нет. Если вы применяете инверсию каждого вентиля в обратном порядке, вы вычисляете инверсию функции. Предполагая модель, в которой гейты действуют на фиксированное число кубитов за раз, тогда обратное действие каждого элементарного обратимого гейта может применяться в постоянное время. Следовательно, такую ​​функцию так же легко инвертировать, как и вычислить (с точностью до мультипликативной константы), и, следовательно, она не является функцией люка.

Джо Фитцсимонс
источник
1
ff
4
f
@mikero: вам нужно немного энергии, чтобы инициализировать все вспомогательные биты в известное начальное состояние, но, поскольку в конце вычисления все вспомогательные биты вернулись в одно и то же известное начальное состояние, вы можете восстановить эту энергию.
Антонио Валерио Мицели-Бароне