Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 37
На HN была ссылка на препринт, но не могу найти сейчас.
К сожалению, я не знаю, что такое HN, можно ссылку?
news.ycombinator.com/item?id=6851117 — это та ссылка? Не думаю, что это тот же ученый, на HN некий Сергей Яхонтов, а здесь — Панюков Анатолий Васильевич.
Тоже хотелось бы услышать подробности. Сколько человек уже ознакомилось с доказательством? Какие методы использовались? К каким выводам он пришел?
Да, господи, штук десять таких в год публикуют. Через пару дней найдут ошибки и доказательство, что для других p/np задач не подходит решение.
Ключевой момент — источником такой новости никак не может стать сайт с заголовками вроде «Тайна Бермудского треугольника всплыла сама!». И заголовок новости будет не будет содержать «челябинский ученый» (не потому что в Челябинске ученых быть не может, а потому что если будет возможен хоть какой-то шанс верности доказательства, не будет иметь значения из какого города или страны доказавший).
Полностью согласен, тем не менее, чем черт не шутит, но вообще да, сложилось стойкое ощущение, что фейк.
Как уже написал ниже, меня смутило то, что ученый настоящий и вроде бы даже подходящий на человека, который мог бы решить эту задачу.
К сожалению, похоже, что не очень походящий. У него всего 12 публикаций (как-то невероятно мало для профессора; может, конечно, не всё проиндексировано) и всё по каким-то несвязанным темам. Да и судя по названиям некоторые статьи довольно простенькие.
А как же то доказательство, которое понять никто не мог? Уже поняли?
Вот в этой статье идет обсуждение близкой тематики, вдруг кто не видел.
Спасибо, актуальненько.
Вообще, меня смутило то, что ученый настоящий и вроде бы даже подходящий на человека, который мог бы решить такую задачу.
Вообще, меня смутило то, что ученый настоящий и вроде бы даже подходящий на человека, который мог бы решить такую задачу.
И это хорошо, даже если доказательство неверно, по крайней мере это даст еще информации о том, где искать не стоит. Вот что настораживает, так это отсутствие peer review. Как только хотя бы 2-3 независимых эксперта (из других университетов, организаций, стран) скажут, что доказательство имеет право на жизнь, тогда уже можно подозревать сенсацию. А пока очередная попытка, коих тысячи (ну или десятки более-менее качественных).
Я достаточно некомпетентен в данном вопросе, но объясните — вот такое заключение верно ли:
Решение в принципе может быть найдено либо перебором, либо функцией. Проверить решение можно также — либо перебором, либо обратной функцией. Существование обратной функции для любой данной в принципе не всегда возможно (те же самые хэш-функции). Таком образом, трудоемкость поиска решения больше трудоемкости его проверки.
Или я что неправильно понимаю?
Решение в принципе может быть найдено либо перебором, либо функцией. Проверить решение можно также — либо перебором, либо обратной функцией. Существование обратной функции для любой данной в принципе не всегда возможно (те же самые хэш-функции). Таком образом, трудоемкость поиска решения больше трудоемкости его проверки.
Или я что неправильно понимаю?
>>Существование обратной функции для любой данной в принципе не всегда возможно (те же самые хэш-функции).
Не доказано, что быстрых функций поиска коллизий не существует.
Не доказано, что быстрых функций поиска коллизий не существует.
Стоп. Если рассматривать криптографически стойкую функцию, то мы должны иметь: необратимость и стойкость к коллизиям разного рода.
Необратимость по определению хэш функйии должна присутствовать. Сама функциия нахождения коллизии по результату работы хэш функции и будет являться обратной. Такой вариант исключаем. Остается ваш вариант — «быстрая функция поиска коллизий». Понятие «быстрая» будет рассматриваться в контексте скорости вычисления самой хэш-функции. Гипотетически, можно иметь огромный словарь значений и тогда скорость работы функции будет равна скорости поиска значения. Если значение хэш функции использовать в качестве адреса, то коллизия может быть найдена за одну итеррацию — не зависимо от сложности вычисления самой хэш функции.
Вопрос в том — куда определить трудоемкость составления этого словаря?
Если ее учитывать в процессе поиска коллизии, то этот процесс однозначно сложнее вычисления самого значения. Иначе в чем смысл самой алгоритмизации вычисления хэш-функции?
Если же ее НЕ учитывать, то процесс поиска коллизии гипотетически для любой хэш-функции проще, чем ее вычисление.
Или что не так?
Необратимость по определению хэш функйии должна присутствовать. Сама функциия нахождения коллизии по результату работы хэш функции и будет являться обратной. Такой вариант исключаем. Остается ваш вариант — «быстрая функция поиска коллизий». Понятие «быстрая» будет рассматриваться в контексте скорости вычисления самой хэш-функции. Гипотетически, можно иметь огромный словарь значений и тогда скорость работы функции будет равна скорости поиска значения. Если значение хэш функции использовать в качестве адреса, то коллизия может быть найдена за одну итеррацию — не зависимо от сложности вычисления самой хэш функции.
Вопрос в том — куда определить трудоемкость составления этого словаря?
Если ее учитывать в процессе поиска коллизии, то этот процесс однозначно сложнее вычисления самого значения. Иначе в чем смысл самой алгоритмизации вычисления хэш-функции?
Если же ее НЕ учитывать, то процесс поиска коллизии гипотетически для любой хэш-функции проще, чем ее вычисление.
Или что не так?
Так. Стоять. Я не хочу: чтобы мы путались в терминах.
Пусть у вас есть функция F( X ) = Y
Обратной ей называется функция G(Y), такая что F(G(Y)) = Y
Обратная функция не обязана находить X. Обратная функция обязана находить значение из класса эквивалентности относительно исходной функции. (любое значение, которое даёт Y)
Именно это я называл поиском коллизий, и оно почти так используется в литературе. (С поправкой на рандомизируемость)
Теперь второе ваше утверждение:
>>Необратимость по определению хэш функции должна присутствовать.
Ни для одной хеш-функции не доказано, что она необратима именно алгоритмически. Более того, не доказано, что существует хотя бы одна необратимая функция в принципе. Более того, нахождение (доказательство) хотя бы одной трудно обратимой функции будет автоматические доказывать, что P!=NP.
То есть, интуитивно кажется, что восстановить по x=SHA512(4TbPornImage.iso) сам 4TbPornImage.iso должно быть сложно. Но нет никаких разумных доказательств того, что нельзя написать полиномиальную функцию BSHA(x), которая будет гарантированно выдавать какой-то бессмысленный набор байт z такой что SHA512(z)=x.
>>Гипотетически, можно иметь огромный словарь
Вам потребуется бесконечный словарь. То есть функция. Конечно, её сложность надо учитывать.
Отдельно
На самом деле, существование односторонних функций — вещь еще более сильная, чем P!=NP.
То есть, возможно, P!=NP, но при этом односторонних функций всё-таки не существует.
(Иными словами, P!=NP гарантирует только необратимость в худшем случае, а для существования односторонних функций нужна трудность в среднем)
Но если так-то дело дрянь, потому что и всей магии P=NP нету, и криптография тоже разваливается.
Пусть у вас есть функция F( X ) = Y
Обратной ей называется функция G(Y), такая что F(G(Y)) = Y
Обратная функция не обязана находить X. Обратная функция обязана находить значение из класса эквивалентности относительно исходной функции. (любое значение, которое даёт Y)
Именно это я называл поиском коллизий, и оно почти так используется в литературе. (С поправкой на рандомизируемость)
Теперь второе ваше утверждение:
>>Необратимость по определению хэш функции должна присутствовать.
Ни для одной хеш-функции не доказано, что она необратима именно алгоритмически. Более того, не доказано, что существует хотя бы одна необратимая функция в принципе. Более того, нахождение (доказательство) хотя бы одной трудно обратимой функции будет автоматические доказывать, что P!=NP.
То есть, интуитивно кажется, что восстановить по x=SHA512(4TbPornImage.iso) сам 4TbPornImage.iso должно быть сложно. Но нет никаких разумных доказательств того, что нельзя написать полиномиальную функцию BSHA(x), которая будет гарантированно выдавать какой-то бессмысленный набор байт z такой что SHA512(z)=x.
>>Гипотетически, можно иметь огромный словарь
Вам потребуется бесконечный словарь. То есть функция. Конечно, её сложность надо учитывать.
Отдельно
На самом деле, существование односторонних функций — вещь еще более сильная, чем P!=NP.
То есть, возможно, P!=NP, но при этом односторонних функций всё-таки не существует.
(Иными словами, P!=NP гарантирует только необратимость в худшем случае, а для существования односторонних функций нужна трудность в среднем)
Но если так-то дело дрянь, потому что и всей магии P=NP нету, и криптография тоже разваливается.
Бывают обратные функции справа и слева, соответственно F` и F``, такие что
F(F'(y)) = y и F``(F(x)) = x, если F` = F`` то её просто называют обратной функцией G, для нее x = F(G(x)) = G(F(x))
Хеш функции H делаются как раз так, чтобы не было очевидной функции H`, такой что H(H`(x)) = x.
Для взлома RSA нужно иметь функцию обратную умножению пары простых чисел (F`), причем такую, чтобы F`(F(x,y)) = (x,y).
И такая функция есть, и если докажут что P=NP, то её можно будет считать за полиномиальное время.
F(F'(y)) = y и F``(F(x)) = x, если F` = F`` то её просто называют обратной функцией G, для нее x = F(G(x)) = G(F(x))
Хеш функции H делаются как раз так, чтобы не было очевидной функции H`, такой что H(H`(x)) = x.
Для взлома RSA нужно иметь функцию обратную умножению пары простых чисел (F`), причем такую, чтобы F`(F(x,y)) = (x,y).
И такая функция есть, и если докажут что P=NP, то её можно будет считать за полиномиальное время.
Ну да.
А если докажут, что её нельзя посчитать за полиномиальное время, то окажется, что P!=NP.
Кандидатов-то в функции хватает: a*b, DLog, Rabin.
Хеши в некотором смысле — тоже кандидаты. Если окажется, что P=NP, то они все тоже вроде как, рухнут.
А если докажут, что её нельзя посчитать за полиномиальное время, то окажется, что P!=NP.
Кандидатов-то в функции хватает: a*b, DLog, Rabin.
Хеши в некотором смысле — тоже кандидаты. Если окажется, что P=NP, то они все тоже вроде как, рухнут.
Если вы пытались меня подловить на правых и левых обратных функциях, то вы не правы.
В криптографическом определении именно «правые» функции.
Пруф:
То есть, не существует ни одного полиномиального «правого» обращения.
«левое» обращение слишком слабое.
В случае перемножения двух простых чисел ответ однозначен. В случае составных — нет.
В криптографическом определении именно «правые» функции.
Пруф:
То есть, не существует ни одного полиномиального «правого» обращения.
«левое» обращение слишком слабое.
В случае перемножения двух простых чисел ответ однозначен. В случае составных — нет.
Вы в некоторых местах путаете алгоритмичность и полиномиальную вычислимость:) (очевидно, что любая вычислимая функция вычислительно обратима).
И существование односторонних функций сильнее, чем P != NP в среднем.
И существование односторонних функций сильнее, чем P != NP в среднем.
Слово алгоритмичность я употребил неформально, а не в смысле «существования вычислимой функции».
>>И существование односторонних функций сильнее, чем P != NP в среднем.
Но из существования односторонних функций следует неравенство в среднем.
Я просто хотел показать, что пример с хешами сильнее, чем P!=NP. (как минимум уже потому что неравенство в среднем уже сильнее)
На самом деле, конечно, даже существования односторонних функций хватает не для всей криптографии.
>>И существование односторонних функций сильнее, чем P != NP в среднем.
Но из существования односторонних функций следует неравенство в среднем.
Я просто хотел показать, что пример с хешами сильнее, чем P!=NP. (как минимум уже потому что неравенство в среднем уже сильнее)
На самом деле, конечно, даже существования односторонних функций хватает не для всей криптографии.
опубликовал попытку доказательстваУже смешная фраза)
Хабр — не место для математики. Закройте этот хаб, плз.
Куцая информация о товарще. Думал сам запостить новость, но везде одно и то же: решил задачу, суровый челябинский мужик. На самом деле есть одно но: пока доказательство не будет проверено и подтверждено, ничего существенного в этом нет.
Не читал (потому что не смог найти статью), но осуждаю (автора «доказательства», не поста).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Челябинский математик опубликовал попытку доказательства P=NP