Comments 47
"конкретный способ создания такой функции" не раскрыт
Если кто-то покажет вам строки чисел 99999999999999999999 и 03729563829603547134, и скажет, что их выбрали случайно, то вы не сможете опровергнуть это заявление со всей определённостью: при выборе случайных чисел вероятность создания обеих строк одинакова.
Я долго смотрел на эту фразу, и что-то во мне зудело. Хотелось подвергнуть сомнению. Но кажется, я понял, в чем дело. Наш мозг, нацеленный на поиск закономерностей, на ходу выполняет конвертацию из «набор цифр» в более простой для понимания и хранения формат «20 девяток», что и искажает восприятие числа. Так и хочется сказать: «ну ведь вероятность выпадения 20 девяток подряд меньше!». И действительно, вероятность выпадения 20 девяток подряд меньше, только вот перед нами не 20 девяток, а условно случайный набор цифр, которые, так уж получилось, составляют 20 девяток.
Это называется число.
И действительно, вероятность выпадения 20 девяток подряд меньше
С чего это меньше?
Человек интуитивно оценивает «энтропию» таких последовательностей, т.е. количество похожих, сформулированных потому же правилу отнесённую к общему количеству. И именно её называет «вероятностью».
Т.е. то что 20 девяток выпадет реже — кажется из-за того что такая последовательность уникальна, в то время как случайных наборов цифр в 20 штук — больше чем человек может себе представить. Если для конкретного человека код 03729563829603547134 — уникален (например, это номер его счёта в швейцарском банке), то «ощущаемая вероятность» выпадения такой последовательности так же резко падает в область нуля.
Скажем проще. Человек оценивает эти строки как "20 одинаковых циферок" и "белиберда какая-то". И тогда действительно, вероятность выпадения 20 одинаковых циферок куда меньше чем вероятность выпадения произвольной "какой-то белиберды" в которой не прослеживается никакой закономерности. (тут должен быть анекдот про Илью Муромца и лернейскую гидру)
Есть классическая задачка, практического смысла не имеющая, но хорошо иллюстрирующая когнитивные искажения:
Одну и ту же монету (можно уточнить, что гарантировано симметричную) подбросили 99 раз. Все разы выпал орёл. Какова вероятность того, что на сотый раз выпадет решка?
Интуитивные представления о вероятностях в головах с настоящей математикой очень слабо стыкуются. Просто потому, что противоречат 90% повседневного опыта - ну не сталкиваются люди с такими вот феноменами. Собственно, за счёт этого и живут страховщики, лотереи и азартные игры.
Скорее всего, на этом невысказанном предположении и меняется оцениваемая вероятность. Мозг докидывает "а может, нас обманывают и монета всё-таки несимметричная?" и исходя из этого пересчитывает вероятности.
Интересно было бы провести опрос "Монета n раз выпала решкой, какова вероятность решки при следующем броске?" и посмотреть разницу в ответах для разных n.
В одной из лекций про случайность лектор рассказывал случай из практики. В поезде "лоха" развели на карточную игру и "раздели". Он заявил в милицию. "Шулеров" задержали. Один из аргументов против них был в том, что несколько милиционеров проводили "следственный эксперимент" - специально целую ночь сидели, тасовали и раздавали карты, и такой расклад как случился там в поезде - ни разу у них не вышел. Следовательно (заключило следствие) - расклад в поезде (выигрышный для шулеров) был явно подтасован! :-)
Возможно, для каких-либо обоснованных утверждений о вероятности важное значение имеет алгоритм получения таких строк, который в условии задачи не уточнён / не определён чётко и однозначно.
Если случайные числа генерируются одним событием, то каждому целому числу в зависимости от системы исчисления можно сопоставить множество строковых представлений. Для одних и тех же пар чисел в зависимости от системы исчисления будут существовать как красивые, так и не очень строковые комбинации их представлений.
Однако если строки генерируются, например, посимвольно (где вероятность возникновения каждого символа близка или одинакова), то из теоремы Байеса следует, что вероятность получения конкретной строки, соответствующей определённому узкому паттерну, будет ниже, чем тех, которые этому паттерну не соответствуют.
Разум/мозг по своей природе настроен на выявление паттернов и закономерностей в окружающем мире, реконструкцию алгоритмов их получения, поэтому строка из повторяющихся символов воспринимается более осмысленной конструкцией (легче реконструировать алгоритм её получения).
Причём, уровень осмысленности паттернов зависит от багажа знаний, например: кто-то сразу распознает привычные десятичные иррациональные значения математических констант в строках, а для других - эти же строки будут выглядеть совершенно случайными.
314159, 271828
И действительно, вероятность выпадения 20 девяток подряд меньше
Если эти строки являются результатом подбрасывания идеального десятигранного кубика, то вероятность их "выпадания" одинаковая. Потому что, при каждом подбрасывании вероятность выпадания каждой конкретной цифры 1/10 и о том, что там выпадало ранее, кубик не знает.
А зачем деястигранным кубиком ограничиваться, когда можно сразу кидать n-мерный m-гранный честный кубик и получать число заданного размера.
Вероятность выпадения любых конкретных 10 цифр сильно меньше и для любой последовательности она одна и та же. Не важно, одинаковые там цифры или нет. Вероятности выпадения 9999999999 и 1234567890 абсолютно одинаковы и равны 1/1000000000.
А ведь наш мозг в этом примере какраз решает задачу Колмогоровой сложности, видимо не для большинства строк а выборочно. Кто знает, может задача ИИ тоже плотно связана с этой математической задачей...
Вероятность выпадения 20 девяток подряд точно такая же, как и числа из 20 девяток. Представим диск с числами от 0 до 999. Вероятность выпадения 999 выходит 1/1000. Представим три диска с цифрами от 0 до 9. Вероятность выпадения трёх 9 выходит 1/10 * 1/10 * 1/10 внезапно так же 1 из 1000.
А теперь представим мешочек с 30 шариками, по 3 шарика на цифру от 0 до 9. Вероятность выпадения трёх 9 будет 3/30 * 2/29 * 1/28, что примерно в 4 раза меньше чем 1/1000. Это результат для зависимых событий.
Вероятно мозг случайные события считает зависимыми от предыдущего результата, но мешочек то бесконечный оказывается.
Именно так.
И достаточно представить эти числа в иной системе исчисления как кажущаяся неслучайность пропадет.
И более того. Для любого случайного числа можно выбрать такой метод представления, что бы оно выглядело неслучайным. Например, выбрать это число основанием системы исчисления.
Спасибо за статью на Хабре по тематике Хабра
Стоит наверное заметить, что так как обращение односторонней функции это NP-задача (дан образ, нужно найти прообраз (сертификат)), то если односторонние функции существуют, то есть NP-задача, которая не решается за полиномиальное от длинны входа время, и значит P != NP (и одна из задач тысячелетия решена https://ru.wikipedia.org/wiki/Равенство_классов_P_и_NP )
Вот у меня похожий вопрос, который я не совсем понял.
Разве это не тоже самое, что задача о P = NP? Которая давно сведена к решению любой из NP-полных задач?
То есть задача упомянутая в статье это "просто" еще одна NP-полная задача? Судя по тому сколько было проделано работы кажется что нет и где-то кроется принципиальная разница, но, увы, я её не понимаю пока что.
Может быть такое, что P != NP, но при этом односторонних функций нет, что является довольно неприятной ситуацией: у нас нет криптографии, но при этом мы не умеем эффективно решать все NP-задачи.
Статья приводит аналог NP-полной задачи в мире односторонних функций. В случае P vs NP, вопрос о равенстве сводится к проверки принадлежности определенной NP-задачи к классу P (эти задачи называются NP-полными). Статья сводит вопрос о существовании односторонней функции к проверки односторонности определённой функции F (такие функции называются универсальными односторонними), то есть если её легко можно обращать, то в принципе все предполагаемые односторонние функции можно будет легко обращать. Ранее тоже были конструкции универсальных односторонних функций, но они были довольно искусственными. В статье даётся пример более естественной универсальной односторонней функции.
Если доказать, что обращение некой односторонней функции является NP-полной задачей, то это будет очень крутой результат, так как он покажет, что либо P=NP либо есть односторонние функции (и значит криптография). При этом на NP-полноту обращения достаточно проверять только некую универсальную одностороннюю функцию, так как если обращение некой универсальной односторонней функций не является NP-полной задачей, то и обращение любой другой односторонней функции не является NP-полной задачей. Поэтому нам интересно исследовать на NP-полноту универсальные односторонние функции, и чем естественнее определение такой функции, тем легче это исследование будет провести.
Еще универсальные односторонние функции самые "надежные" из односторонних функций, так если их взломать, то можно взломать и все остальные односторонние функции. Поэтому интересно найти универсальные односторонние функции которые можно эффективно вычислять и использовать на практике.
Спасибо! Да, оказывается у меня было заблуждение о том, что обращение односторонних функций обычно является NP-полной задачей.
Интересно узнать, что это на самом деле открытый вопрос.
Предположим, что P != NP и односторонних функций нет. Тогда умножение чисел тоже не односторонняя функция. Но факторизация ведь (это так?) NP-трудная задача (к ней сводятся все NP), значит все NP-задачи могут быть решены эффективно, значит P = NP - противоречие?
Где в моих рассуждениях ошибка?
Если сводимость доказана, то задача относится к NP-полным. Для задачи факторизации и дискретного логарифма это не доказано. Возможно по этой причине для этих задач известны решения с полиномиальной сложностью на квантовом компьютере. Вообще эта публикация настолько поверхностна, что её нельзя использовать в дидактичеких целях. Я уже написал, что те, кто не разбираются в вопросе, скорее больше запутаются, чем что-то для себя выяснят.
А как влияет культурный код на колмогоровскую сложность? Вот, например, программа для записи 999999999999 очевидна для нас, привыкших к десятеричной системе счисления. В двоичной системе сложность записи повышается. Помимо системы счисления наверняка есть и другие вещи, позволяющие оптимизировать запись в зависимости от багажа знаний записывающего. Древние люди, например, число e не знали. Только pi.
Тогда можно попрощаться с криптографией
Коррекция - попрощаться можно с асимметричной криптографией. В симметричной секретом является алгоритм получения шифрующей последовательности (включая неявные алгоримы в виде записи информации о процессах, считающихся случайными). Без знания алгоритма перебирать варианты можно намного дольше времени существования вселенной.
Я так понимаю, имеется в виду секретность получения вектора инициализации для ГПСЧ.
Хорошо, менее параноидальные пользователи криптографии используют известные алгоритмы. Но эти алгоритмы не предполагают разглашение результата прямого преобразования, как в асимметричной криптографии. То есть там нет места для взлома "возможно слабого" обратного преобразования.
Хотя в моём случае стоило добавить это уточнение ещё в первом сообщении. Но получение шифрующей последовательности по имеющемуся в наличии закодированному сообщению затруднительно по причине неоднозначности преобразования шифр -> открытый текст. Это аналог неизвестного множества алгоритмов для случая с асимметричной криптографией, ведь даже умея вскрывать все обратные преобразования, но не зная конкретный алгоритм, мы получаем ту самую неоднозначность.
А имеет ли смысл публиковать перевод статьи неспециалиста? Ведь Erica Klarreich не является специалистом в этой области. Те, кто не разбираются могут вообще не понять, понять неправильно или не до конца. Специалисты же читают совсем другие тексты. Тогда возникает вопрос: А на кого рассчитана эта публикация? Тем более, что текст не рецензировался, как я понимаю.
"Одну и ту же монету (можно уточнить, что гарантировано симметричную) подбросили 99 раз. Все разы выпал орёл. Какова вероятность того, что на сотый раз выпадет решка? "
Предыдущие результаты (их 99) однозначно указывают на более чем вероятный результат.
Монета ничего не знает про предыдущие броски. Вероятность 0.5
Это работает так: монета, может, и не знает о предыдущих бросках, но мы из предыдущих бросков знаем о монете и о её статистике, и это единственный достоверный источник этой информации (эксперимент — критерий истины).
Правильно ли, что если предложить квантовый алгоритм, который эффективно обращает сконструированную авторами функцию, то всё - криптографии нет. Потому что эта функция становится не односторонней, значит односторонних не существует.
Такой подход наиболее практичен в свете быстро надвигающихся квантовых компьютеров.
И как с этим всем соотносится постквантовая криптография? Справедливы ли там все эти рассуждения, есть ли там такая функция-стражник, которая защищает односторонность и вообще постквантовую криптографию единолично? Отличается ли этот стражник от стражника доквантового?
Момент, который был для меня не очевиден, пока не задумался: невычислимость Колмогоровой сложности сводится к проблеме останова.
Можно вообразить программу, которая перебирает все возможные программы в порядке возрастания размера. Резмер первой компилирующейся и выдающей на выходе нужную строку - это Колмогорова сложность. Однако такая программа не реализуема из-за проблемы останова.
Не понимаю что они ...... занимаются любая функция взламывается перебором, это аксиома. Теория сложности вроде как определяет характеристики энтропии а следовательно характеристики оценки вводимых функций, эти характеристики лишь определят время переборора. Не может существовать такой функции которая будет решать задачу оптимизации функций автоматически, за исключением полного перебора, это сводиться к NP задаче. Проблема оптимизации иверссии отдельных функций вполне может существовать, но даже тут вряд ли будет универсальное решени,т.к. тоже NP задача.
Yuval Ishai - Юваль Ишаи, а не "Исхаи" (יובל ישי) - не понимаю, почему sh из оригинального ש (шин) транслитеровали как "сх"
Исследователи выявили задачу, от которой зависит судьба современной криптографии