Доказательство P=NP: пострадает ли криптоалг&

[VELVET]

Вчера опубликовали новость доказательства одной из проблем тысячелетия: равенство классов P и NP.
+ тык, тык, хабр

Не будучи математиком, я не понимаю, как это влияет на современные криптоалгоритмы и на майнинг биткоинов, в частности.

Заметил, что вчера вечером курс биткоина пошел вниз. Связано ли это с данной новостью?


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

Однако, само по себе математическое доказательноство ничего не значит на практике: научиться превращать NP алгоритмы в P может занять очень много времени...

[Balthazar]

Этих доказательств и опровержений опубликовали уже много сотен.

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

[gnuberg]

Естественно пострадает.
Доказавший купит на полученное вознаграждение асиков и сделает 51% всей сети.

Вчера опубликовали новость доказательства одной из проблем тысячелетия: равенство классов P и NP.
+ тык, тык, хабр

Не будучи математиком, я не понимаю, как это влияет на современные криптоалгоритмы и на майнинг биткоинов, в частности.

Заметил, что вчера вечером курс биткоина пошел вниз. Связано ли это с данной новостью?

Нет, таких "прорывов" по нескольку десятков в год бывает. В лучшем случае где-то ошибка, обычно же просто утка. У Успенского было описание того как еще в советское время после журналистского бума приходилось разгребать тысячи заведомо неверных решений математических задач.

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

Однако, само по себе математическое доказательноство ничего не значит на практике: научиться превращать NP алгоритмы в P может занять очень много времени...

Сама идея использования полиномиальных алгоритмов вместо экспоненциальных стоит практически любого затраченного времени

[gauntlet]

Жёлтая пресса.

По открытому ключу, читай биткоин адрес, можно будет восстановить priv key.

Таких доказательств, из Челябинска и др. городов приносит на страницах беспантовых газет, каждый год пачками.

[boinc]

Жёлтая пресса.

По открытому ключу, читай биткоин адрес, можно будет восстановить priv key.

Таких доказательств, из Челябинска и др. городов приносит на страницах беспантовых газет, каждый год пачками.

Биткойн адрес это не пубкей, он еще хэширован несколько раз

[ri]

По открытому ключу, читай биткоин адрес, можно будет восстановить priv key.

Биткойн адрес это не пубкей, он еще хэширован несколько раз

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

Т.е. если доказательство окажется верным - это будет значить, что взлом и биткойна, и множества других криптографических систем (всех, кроме симметричного шифрования) - дело времени. Но сколь долгого - непонятно.

[boinc]

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

Ну, во-первых, с вероятностью семь девяток доказательство очередной фейк, а во-вторых, AFAIR, из утверждения P=NP вовсе не следует автоматически, что вся криптография рухнет, степень полинома будет иметь значение. Так же как из утверждения P≠NP не следует, что существующая криптография абсолютно надёжна - необходимо доказать существование односторонних функций

[ri]

Ну, во-первых, с вероятностью семь девяток доказательство очередной фейк,

Гм, а какова методика расчета этой вероятности ?

а во-вторых, AFAIR, из утверждения P=NP вовсе не следует автоматически, что вся криптография рухнет, степень полинома будет иметь значение.

Ммм я же писал - если утверждение P=NP  верное, то это означает потенциальную возможность взлома, но не дает его алгоритмов.

Так же как из утверждения P≠NP не следует, что существующая криптография абсолютно надёжна - необходимо доказать существование односторонних функций

Насколько я понимаю, это утверждение и есть доказательство их существования. Но - их нужно еще найти и использовать. Если они существуют - то это не значит, что они уже используются, возможно, как раз ни в  одной современной криптографической системе ни одна из таких функций не применяется.

[boinc]

Вобщем расходимся мужики - новость желтая, битку новых дыр не добавилось пока.

[bblizard]

Наш дорогой питерец Григорий Перельман восемь лет ломал Пуанкаре головой даже малость поехал, затворником стал, а Вы - "доказательство нашли" - если это правда, то этим самым доказательством подтверждается теория струн!

[ri]

Наш дорогой питерец Григорий Перельман восемь лет ломал Пуанкаре головой даже малость поехал, затворником стал, а Вы - "доказательство нашли" - если это правда, то этим самым доказательством подтверждается теория струн!

Непонятно - каким образом затворничество Перельмана доказывает невозможность доказательства титульной задачи?

[bblizard]

Наш дорогой питерец Григорий Перельман восемь лет ломал Пуанкаре головой даже малость поехал, затворником стал, а Вы - "доказательство нашли" - если это правда, то этим самым доказательством подтверждается теория струн!

Непонятно - каким образом затворничество Перельмана доказывает невозможность доказательства титульной задачи?

Конечно не доказывает - просто хотел подчеркнуть уровень необходимой работы! А эта работа по самым имхо скромным меркам на порядок сложнее! А в общем и целом мне видится, что доказательство или опровержение поставленной задачи в ближайшее время ожидать не стоит! Можно спать спокойно и не переживать за возможность подбора приватного ключа!

[ZeroTheGreat]

Насколько я понимаю, это утверждение и есть доказательство их существования.

Разве? Вроде это лишь означает, что поиск коллизий нельзя будет вести в полиномиальное время, но не запретит существование коллизий. Тем более в некоторых устаревших алгоритмах коллизии были найдены, вопрос только в том достаточно ли сложно найти коллизии в новых алгоритмах, чтобы пользоваться ими. Пока ответ: да, это сложно (=дорого).

[ZeroTheGreat]

Ну, во-первых, с вероятностью семь девяток доказательство очередной фейк,

Гм, а какова методика расчета этой вероятности ?

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

[ri]

Насколько я понимаю, это утверждение и есть доказательство их существования.

Разве? Вроде это лишь означает, что поиск коллизий нельзя будет вести в полиномиальное время, но не запретит существование коллизий. Тем более в некоторых устаревших алгоритмах коллизии были найдены, вопрос только в том достаточно ли сложно найти коллизии в новых алгоритмах, чтобы пользоваться ими. Пока ответ: да, это сложно (=дорого).

Вообще-то коллизии заведомо существуют для любого алгоритма хэширования - и не надо быть профессором математики, чтобы это доказать. Могу продемонстрировать доказательство, если хотите.

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

Ну, во-первых, с вероятностью семь девяток доказательство очередной фейк,

Гм, а какова методика расчета этой вероятности ?

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

Нелогично. В данном случае мы имеем работу, опубликованную, я так понимаю, как минимум в одном из научных журналов, а может и отдельным изданием - лень гуглить и проверять, но не суть важно. Возьмем классичесские семь задач тысячелетия. Одно из опубликованных решений для них принято считать верным. Чтобы получить ваши семь нулей, получается, что опубликованных работ с решениями одной из задач тысячелетия должно быть более миллиона. Вы можете поверить в эту цифру? Я - нет. Готов допустить десяток-сотню, да пусть даже тысячу опровергнутых опубликованных решений задач тысячелетия, но уж никак не миллион.

[boinc]

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

С чего вы взяли?

лень гуглить и проверять, но не суть важно.

Вот на таких читателях и держится вся желтая пресса.
Нет ссылки ни на какую научную публикацию, даже на arXiv, только бла-бла-бла и ко-ко-ко

Ну и как аргумент скопипастю коммент с хабра

Ключевой момент — источником такой новости никак не может стать сайт с заголовками вроде «Тайна Бермудского треугольника всплыла сама!». И заголовок новости будет не будет содержать «челябинский ученый» (не потому что в Челябинске ученых быть не может, а потому что если будет возможен хоть какой-то шанс верности доказательства, не будет иметь значения из какого города или страны доказавший).

[ri]

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

С чего вы взяли?

лень гуглить и проверять, но не суть важно.

Вот на таких читателях и держится вся желтая пресса.
Нет ссылки ни на какую научную публикацию, даже на arXiv, только бла-бла-бла и ко-ко-ко

Вообще-то я специально сделал оговорку, давая понять, что у меня нет точной и абсолютно достоверной информации на этот счет. Сейчас все-таки загуглил, ситуация действительно весьма неоднозначная... С одной стороны утверждается, что работа не опубликована, с другой - сказано, что "Так, свое доказательство Панюков представил на международной конференции в Черногории, а также в Институте математики и механики УрО РАН и в журнале «Автоматика и механика»". С другой стороны навскидку я не нашел такой журнал, однако существует журнал "Автоматика и телемеханика", в котором этот самый Панюков многократно публиковался, правда, требуемой статьи я там не нашел.

Ну и как аргумент скопипастю коммент с хабра

Ключевой момент — источником такой новости никак не может стать сайт с заголовками вроде «Тайна Бермудского треугольника всплыла сама!». И заголовок новости будет не будет содержать «челябинский ученый» (не потому что в Челябинске ученых быть не может, а потому что если будет возможен хоть какой-то шанс верности доказательства, не будет иметь значения из какого города или страны доказавший).

А теперь - вот, получите: http://grani.ru/Society/Science/m.29288.html

Начнем с заголовка: "Российский математик Григорий Перельман утверждает, что доказал гипотезу Пуанкаре" - таки российский? Это же совершенно неважно!

Несколько цитат:

Григорий Перельман, кстати, сын знаменитого Якова Перельмана, автора "Занимательной физики", является сотрудником петербургского Математического института имени Стеклова Российской Академии наук.

А вот википедия утверждает, что

Распространено заблуждение, что отцом Григория Яковлевича Перельмана является Яков Исидорович Перельман — известный популяризатор физики, математики и астрономии[44]. Однако Я. И. Перельман умер более чем за 20 лет до рождения Григория Перельмана.

Уже достаточно желто для вас? Значит, доказательство Перельмана - гарантированный фейк?

Далее по тексту:

Как пишет New York Times, статью которой публикует InoPressa, на доскональную проверку доказательства уйдет не один месяц. Если доказательство профессора Перельмана будет принято к публикации в реферативном научном журнале и не будет опровергнуто в течение двух лет, ученый получит от Математического института Клэя в Кембридже премию в 1 млн долл.

Найдите-ка пять отличий от нынешней ситуации! Я не смог.

Из всего вышесказанного совершенно не вытекает, что я считаю доказательство Панюкова правильным - даже если бы я его досконально изучил, то и тогда мое образование не позволило бы сделать никаких выводов на этот счет. Но и утверждать, что оно гарантированно неверное у меня нет абсолютно никаких оснований - как и у вас. Только я это признаю, а вы - нет.

[boinc]

А теперь - вот, получите: http://grani.ru/Society/Science/m.29288.html

Начнем с заголовка: "Российский математик Григорий Перельман утверждает, что доказал гипотезу Пуанкаре" - таки российский? Это же совершенно неважно!

Если вы обратите внимание, они по крайней мере ссылаются на NYT, хотя статейке более 10 лет уже. А тут чистейшая желтизна.

[boinc]

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

Что оно гарантированно неверное я ни где не говорил. Я лишь говорю, что статейка несомненно желтая, и именно по этой причине всерьёз воспринимать её не стоит.

[ri]

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

Что оно гарантированно неверное я ни где не говорил. Я лишь говорю, что статейка несомненно желтая, и именно по этой причине всерьёз воспринимать её не стоит.

Статейка не одна, их много - разной степени желтизны. Однако из них тоже можно сделать несколько выводов... Я на сегодняшний день ситуацию таковой вижу: некий профессор, доктор физико-математических наук, заведующий кафедрой в достаточно серьезном вузе, обладатель кучи почетных званий и т.п. (http://www.mathnet.ru/php/person.phtml?option_lang=rus&personid=30278, http://www.susu.ac.ru:8001/ru/f/fakultet_vychislitelno_matematiki_i_informatiki/kafedry/emmis/professorsko-prepodavatelski_sostav/panjukov) считает, что решил одну из "задач тысячелетия", над которой работал более 30 лет. Сие решение он готовит к публикации и надеется, что оно окажется верным. Поскольку проблема (как, по всей видимости, и ее доказательство) весьма сложна и ранее было предложено много доказательств (и опровержений), оказавшихся ошибочными, вероятнее всего и на этот раз где-нибудь будет найдена ошибка, однако ввиду серьезности заявления и биографии заявителя это решение должно быть рассмотрено самым серьезным образом.