Рейтинг:0

Последствия P=NP для аутентификации

флаг ca

Предположим, что П=НП. То есть любая проблема, решение которой можно быстро проверить, также может быть быстро решена, независимо от того, что это означает на формальном уровне. Значит, не только П=НП, но существуют практические полиномиальные алгоритмы для НП- полные проблемы. Кроме того, доказательство либо конструктивно, либо неконструктивно. То есть можно найти алгоритм, который мы в конечном итоге найдем достаточно быстрым, чтобы начать использовать его, даже если мы не сможем его доказать. Тогда становится намного труднее хранить секреты — огромная проблема. Меня пугает не наша неспособность скрыть информацию, а наша неспособность раскрыть ее.

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

Можно ли найти другие решения? Если П=НП, у нас есть мир без конфиденциальности, но, сократив наши потери в этом отношении, мы могли бы попытаться построить аутентификацию вокруг этого факта. Вместо того, чтобы сущности давали нам информацию, необходимую для их идентификации, мы могли бы просто выжать ее из них. Одна из идей состоит в том, что после получения сообщения мы отправляем наше сообщение, содержащее некоторую информацию, которая будет отправлена ​​нам вместе с исходным сообщением, чтобы мы знали, что наше сообщение было получено и что получатель, по крайней мере, хотел отправить исходное сообщение. сообщение. Наше сообщение — шпионское ПО, усиленное нашим эффективным алгоритмом для НП-полные задачи, которые мы используем для проверки источника исходного сообщения.

Рейтинг:4
флаг ng

Я попытаюсь ответить на то, что я считаю тем, о чем вы спрашиваете, а именно:

Если $P = НП$, можно ли "исправить" криптографию, заменив конструкции на интерактивный протоколы?

Это достаточно естественный вопрос, но на него есть хорошо известный (отрицательный) ответ. В частности, считается, что любой интерактивный протокол, который требует фиксированного (конечного) числа раундов взаимодействия, живет в классе сложности, называемом полиномиальная иерархия $PH$. это априори возможно, что $P = НП$, но $P \subsetneq PH$. В этой постановке ответ на поставленный выше вопрос «да, в принципе» (хотя я не знаю никаких конструкций).

К сожалению, один из основных результатов о $PH$ что это ложь, то есть $P = NP\подразумевается P= PH$, поэтому базовая криптография (в мире, где $P = НП$) на ограниченном числе раундов интерактивности невозможно. Здесь есть некоторые предостережения относительно протоколов, которые $\омега(1)$ раундов (они относятся к классу сложности, называемому IP), но они были бы настолько невероятно медленными (из-за того, что каждый раунд имеет неизбежную задержку из-за скорости света), что они не представляют особого интереса.

Есть несколько других потенциальных способов получить (что-то вроде) криптографию в мире, где $P = НП$ хотя, а именно:

  1. Используя предположения о «зашумленном канале», например канал прослушивания, и
  2. Использование квантовых каналов

У обоих есть существенные недостатки по сравнению с теоретико-сложной криптографией (которые я не буду пытаться обобщать здесь), но их валидности не угрожает $P = НП$, и, вероятно, стоит поискать, если вы заинтересованы в возможности безопасного общения в мире, где $P = НП$.

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

Thomas Anton avatar
флаг ca
Будет ли личная аутентификация действительно длиться долго? Мы уже можем клонировать.
флаг cn
Существуют также подходы, такие как мелкозернистая криптография, на которые не обязательно влияет $\mathsf{NP}\subseteq \mathsf{BPP}$.
Mark avatar
флаг ng
@ThomasAnton трудно предсказать, но нецифровые формы аутентификации труднее выдавать себя за миллионы людей одновременно, даже с учетом возможности клонирования людей или чего-то еще.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.