Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 84
Мозг вскипел…
Вы заставили меня достать лекции по криптологии. Теперь и теорию чисел вспоминать придется. Спасибо за бессонную ночь.
Скажите, а на основании чего утверждается, что алгоритм будет стойким к атаке с использованием квантовых вычислителей? Только потому, что никто пока не придумал квантовый алгоритм решения задачи кратчайшего вектора решетки? Это же не значит, что такого алгоритма не существует.
Да именно на основании этого. Видите ли, никто ведь не утверждает, что NTRU или любая криптосистема основанная на задачах решеток станет панацеей в век квантовых вычислений. Сейчас речь идет о некотором переходном периоде если угодно. Ну а то что возможно нахождение алгоритма решения SVP(задача кратчайшего вектора), так тоже самое уже как 2000 лет про факторизацию твердят. Иначе говоря после создания КК на NTRU можно будет полагаться так же как мы сейчас полагаемся на RSA. Риски абсолютно эквиваленты.
Что такое приведение многочлена по модулю?
Хентайный призрак с ШИМ
В кольце усеченных полиномов приведение многочлена a0+a1x+a2x2+...+anxn по модулю числа p означает вычисление многочлена b0+b1x+b2x2+...+bnxn с коэффициентами b0= a0 mod p, b1= a1 mod p,..., bn= an mod p,
This is MATAAAAN!!!!1
Я большую часть не понял… Печально(
Очень хотелось бы наглядного примера работы
А где обещанная гиперстойкость к квантовым атакам? И вообще, я давно уже тесно с RSA не работал, но такое ощущение, что это оно и есть, просто в кольце многочленов. И в основе тоже лежит проблема разложения на множетели (которой, в общем-то, не важно, в каком именно кольце: хоть многочленов, хоть эллиптических кривых, хоть целых чисел — быть проблемой).
А у квантовых же компьютеров, теоретически, достоинство именно в способности брутфорсить всё подряд за O(1). То есть, если решение конечной размерности можно проверить за полиномиальное время, то квантовый компьютер его быстро найдёт. Другое дело, что вот фиг знает, можно ли вообще построить достаточно большой квантовый компьютер.
И ещё… Уверенность в том, что N != NP всё крепнет, лично я б поставил пару 10^n (можно даже Евро), что в ближайшие 10 лет будет доказано это: критическая масса косвенных признаков всё нарастает. И, возможно, это всё будет как-то связано с согласованием квантовой механики и ОТО, есть у некоторых теор-физиков такие умозаключения.
А у квантовых же компьютеров, теоретически, достоинство именно в способности брутфорсить всё подряд за O(1). То есть, если решение конечной размерности можно проверить за полиномиальное время, то квантовый компьютер его быстро найдёт. Другое дело, что вот фиг знает, можно ли вообще построить достаточно большой квантовый компьютер.
И ещё… Уверенность в том, что N != NP всё крепнет, лично я б поставил пару 10^n (можно даже Евро), что в ближайшие 10 лет будет доказано это: критическая масса косвенных признаков всё нарастает. И, возможно, это всё будет как-то связано с согласованием квантовой механики и ОТО, есть у некоторых теор-физиков такие умозаключения.
Что за критические признаки P!=NP?
Не критические признаки, а критическая масса признаков :) Я о том, что попытки доказательства P = NP быстро разваливаются, а доказательства P != NP становятся всё убедительнее. Люди начинают говорить о информационных связях между решениями всё такое. Это выглядит важным, потому что в «школьных» полиномиальных задачах действительно просто перейти от одного решения к другому, а в «школьных» NP-полных задачах изменение на «единичку» входных данных может решения разбрасать очень далеко. Получается нечто вроде хаоса.
То есть, вроде как, уже видно, что решения себя ведут по-разному.
Но… Это, конечно, может быть и ложное направление мысли. Но кто знает? Будем вот на следующей неделе ещё одну попытку доказательства P = NP обсуждать. Может быть, успешную, кто знает? :) Готовьте шифроблокноты на всякий случай
То есть, вроде как, уже видно, что решения себя ведут по-разному.
Но… Это, конечно, может быть и ложное направление мысли. Но кто знает? Будем вот на следующей неделе ещё одну попытку доказательства P = NP обсуждать. Может быть, успешную, кто знает? :) Готовьте шифроблокноты на всякий случай
Могу сказать, что попытки доказать P != NP разваливаются также довольно скоро (в смысле, в тупик заходят). Из более-менее успешных работ только работа Деолаликара, но это еще не является доказательством. Во многих задачах математики «изменение на «единичку» входных данных» сильно влияет на результат, но методы найти этот результат все равно есть. Так что это не аргумент. Никакой критической массы признаков не вижу, ниже правильно сказано, математика так не работает. Либо озарение, либо скурпулезное доказательство. Ничего такого для P vs NP не наблюдается.
Да математика вообще работает так, как работает. И не более :) А про единичку, мне кажется, это абстрактно всё слишком. Результатами в разных областях математики называются разные вещи, иногда конструктивные, иногда — нет, иногда — те, которые можно считать хоть за полторамиллиарда лет :)… Так что, не следует обобщать.
Результатами в математике называются доказательства. И больше ничего. Конструктивность — понятие относительное. Для опровержения очень стройной теории достаточно одного контр-примера, поэтому никакое количество положительных примеров не может быть основой для утверждения истинности теории.
Хм… Чё-то вы как-то категорично к нашему математическому процессу относитесь :) В математике результатом считается то, что некая группа математиков считает результатом (как и в любой другой науке; отличие математики в том, что можно строить формальные доказательства некоторых утверждений, но и только). Та же работа по P != NP. Ну хорошо, у мужика есть косяки в работе, но по общему мнению, это вполне достойный результат, он описал способ анализа сложности задач, который до него никто не описывал — и это интересно.
Таких работ, в которых основной результат — это метод анализа или ценная абстракция, достаточно много. Формально, конечно, можно, дав интересное определение, доказать теорему в одну строчку с его участием, но ценным результатом будет именно определение, а не доказательство.
Таких работ, в которых основной результат — это метод анализа или ценная абстракция, достаточно много. Формально, конечно, можно, дав интересное определение, доказать теорему в одну строчку с его участием, но ценным результатом будет именно определение, а не доказательство.
Цель любой теории — разработка методов решения типовых задач. Математика не исключение. Абстракция ценна только тогда, когда позволяет решить некоторый класс задач, т.е. использована для доказательства соответствующих теорем. Без этого ни одна математическая абстракция не существует. Хотя, вероятно, я действительно выразился слишком категорично, перспективное направление мысли также можно считать результатом, хотя и в меньшей степени.
«У мужика в работе косяки» эквивалентно «приведенная цепочка рассуждений не является доказательством».
«У мужика в работе косяки» эквивалентно «приведенная цепочка рассуждений не является доказательством».
Стойте где вы тут проблему разложения на множители увидели? Тут и чисел то больших нет, максимальное число это размер векторов. Откуда тут факторизации взяться?
И касательно квантовых вычислений откуда такая уверенность в сложности O(1)? Пока единственным квантовым алгоритмом применимым для брут форса является алгоритм Гровера и его сложность O(N^1/2 ). Поэтому не факт еще что квантовый компьютер быстро найдет правильное решение.
И касательно квантовых вычислений откуда такая уверенность в сложности O(1)? Пока единственным квантовым алгоритмом применимым для брут форса является алгоритм Гровера и его сложность O(N^1/2 ). Поэтому не факт еще что квантовый компьютер быстро найдет правильное решение.
Эмс. А какая разница, как представлены элементы кольца? Это могут быть длинные числа, а могут быть и многочлены. С алгебраической точки зрения нужно режать одну и ту же задачу: найти разложение элемента кольца на множетели.
>> Стойте где вы тут проблему разложения на множители увидели?
Вот тут «Открытый ключ определяется как h(x)=fq(x)*g(x) mod q». Или по вашему это как-то по другому называется?
Вот тут «Открытый ключ определяется как h(x)=fq(x)*g(x) mod q». Или по вашему это как-то по другому называется?
Конечно по другому. Одно дело когда речь идет о числах, когда факторизация для каждого числа возможна только в одном варианте и другое дело когда мы имеем конечную структуру, ограниченную числом q. Здесь однозначного представления получить нельзя и соответственно можно получить бесконечное число многочленов f и g таких что f*g mod q=h.
Определение факторизации. Могу найти книги, где тоже самое написано (если не доверяете вики).
>> Одно дело когда речь идет о числах, когда факторизация для каждого числа возможна только в одном варианте и другое дело когда мы имеем конечную структуру, ограниченную числом q.
Вообще-то в RSA поле (хоть и выражено числами). И вообще «числом» называют элемент поля, чтобы было понятней и не более. В общем случае — это элемент поля (кольца). И не важно, число ли это, или полином, или матрица или кольцо полиномов над конечным полем.
>> бесконечное число многочленов f и g таких что f*g mod q=h
Ну не бесконечное, но согласен.
>> Одно дело когда речь идет о числах, когда факторизация для каждого числа возможна только в одном варианте и другое дело когда мы имеем конечную структуру, ограниченную числом q.
Вообще-то в RSA поле (хоть и выражено числами). И вообще «числом» называют элемент поля, чтобы было понятней и не более. В общем случае — это элемент поля (кольца). И не важно, число ли это, или полином, или матрица или кольцо полиномов над конечным полем.
>> бесконечное число многочленов f и g таких что f*g mod q=h
Ну не бесконечное, но согласен.
Хм… А точно? Потому что, вроде как, речь же идёт о кольце вычетов многочленов по модулю (x^n — 1). Если p и q — это простые числа, то речь идёт и кольце вычетов многочленов по модулю (x^n — 1) над полем. А в этом случае уже в полный рост работает обычная теория о делении с остатком и однозначности разложения многочленов на неприводимые множители.
А если p и q просто взаимнопросты, то думать надо. Но, может быть, разложение тоже будет однозначным. Там же ещё условие на сами коэффиценты накладывается.
Ну и ещё вопрос в том, насколько однозначно нужно определить f_q и g. Может быть, что для расшифровки подойдёт куча вариантов. Там же, главное — соотношение между f_q, f_p и f.
P.S. У Вас в одном месте написано f_qq
А если p и q просто взаимнопросты, то думать надо. Но, может быть, разложение тоже будет однозначным. Там же ещё условие на сами коэффиценты накладывается.
Ну и ещё вопрос в том, насколько однозначно нужно определить f_q и g. Может быть, что для расшифровки подойдёт куча вариантов. Там же, главное — соотношение между f_q, f_p и f.
P.S. У Вас в одном месте написано f_qq
Вообще-то разложение многочленов на множители можно выполнить за полиномиальное время.
Квантовые компьютеры за O(1) брутфорсить все подряд не умеют. Один из N вариантов они могут найти за N^0.5 действий и вроде даже есть теорема что быстрее сделать нельзя (в случае если правильность варианта определяется оракулом).
Квантовые компьютеры за O(1) брутфорсить все подряд не умеют. Один из N вариантов они могут найти за N^0.5 действий и вроде даже есть теорема что быстрее сделать нельзя (в случае если правильность варианта определяется оракулом).
критическая масса косвенных признаков всё нарастаетМатематика так не работает. Что за признаки? Кто их формализовал? Почему так важно их количество?
Кажется, движок Хабра не туда прикрепил мой комментарий. Он был к предыдущему, который mikhanoid написал.
Математика работает всяко разно, и очень часто на интуитивном уровне. Собственно, сами математики об этом много рассказывали. Можно почитать рабочии заметки Пуанкаре или фон Неймана.
Если мне не изменяет память, P≠NP недавно было кем-то доказано.
Кем? Когда?
Можно погуглить на тему Vinay Deolalikar P != NP. У него мощная работа, все признали, что красивый подход к проблеме. Но в паре мест есть то ли ошибки, то ли недочёты. Сейчас, вроде как, он переписывает.
Не доказательство
Не известно. Его не опровергли, а только указали на неточности. Поэтому может быть и доказательство, только не полное пока. В математике, кстати, довольно часто так процесс идёт — сначала приводится общая идея доказательства. Сам автор-то, конечно, уверен на 100%, что всё доказано, и опирается он на очевидные факты. А потом оказывается, что факты не такие уж и очевидные, и всем миром доказательство допиливается. Работа Деолаликара, вполне может быть, как раз из подобных. Так что, не известно пока.
«Указали на неточности» то же самое, что опровергли. Попытки доказательства гипотеза Римана с «неточностями» также имели место быть, пытались исправить всем миром. Гипотеза до сих пор не доказана. Потому что эти «неточности», которые обычно являются необоснованными предположениями, чаще всего разбивают всю теорию.
Так что пока в работе Деолаликара есть косяки — это не доказательство
Так что пока в работе Деолаликара есть косяки — это не доказательство
Согласно википедии, проблема не решена, а за ее решение выдадут лям баксов.
Если Вы где-то уже читали решение, у Вас есть шанс заработать (:
Если Вы где-то уже читали решение, у Вас есть шанс заработать (:
Надо Перельмана попросить. Деньги ему, похоже, не нужны, а вот на «слабо» — может сработать (:
Я вот чего не понимаю.
Допустим будет доказано что P=NP, и что?
Как это сломает асимметричную криптографию?
Извините.
Допустим будет доказано что P=NP, и что?
Как это сломает асимметричную криптографию?
Извините.
Допустим, доказательство будет состоять в том, что для одной из NP-полных задач будет найден полиномиальный алгоритм решения. В этой ситуации задачу дискретного логарифмирования также можно будет решить за полиномиальное время.
Если степени и коэффициенты полинома не будут ужасно большими, то, вполне вероятно, можно будет по открытому ключу восстанавливать закрытый довольно быстро.
Если степени и коэффициенты полинома не будут ужасно большими, то, вполне вероятно, можно будет по открытому ключу восстанавливать закрытый довольно быстро.
«В этой ситуации задачу дискретного логарифмирования также можно будет решить за полиномиальное время.»
Меня слово «можно» смущает.
«Можно» необязательно равно «будет найдено решение». Или нет? Что мешает искать решение сейчас как бы заранее, пока не доказано P=NP?
Меня слово «можно» смущает.
«Можно» необязательно равно «будет найдено решение». Или нет? Что мешает искать решение сейчас как бы заранее, пока не доказано P=NP?
Найти решение — это и есть способ доказать, что P=NP. Многие его искали и продолжают искать.
А вообще все NP-полные задачки друг другу эквивалентны, ЕМНИП. То есть достаточно найти решение одной, а для всех остальных его «портировать».
А вообще все NP-полные задачки друг другу эквивалентны, ЕМНИП. То есть достаточно найти решение одной, а для всех остальных его «портировать».
NP-задачки друг другу эквивалентны, потому что они находятся в одном классе эквивалентности. Это не значит, что для них существует общий метод решение.
Значит глупость написал.
То есть для того, чтобы доказать, что P=NP достаточно решить лишь одну задачу. И из этого будет следовать существование решения для других. Но никакой подсказки про алгоритм решения при этом не будет?
То есть для того, чтобы доказать, что P=NP достаточно решить лишь одну задачу. И из этого будет следовать существование решения для других. Но никакой подсказки про алгоритм решения при этом не будет?
Не совсем. Найти решение не подходящее слово. Нужно доказать принадлежность хотя бы одной задачи из класса NP-полных к классу P. Доказано, что либо все NP-полные задачи принадлежат P, либо ни одна из них к нему не принадлежит. Т.е. нужно хотя бы для одной такой задачки, всегда находящий решение за полиномиальное время. Например, задача коммивояжера относится к классу NP-полных и для нее не существует полного решения
Извините, что ссылаюсь на википедию, но там пишут, что всё-таки «Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».» Так что Davidov прав.
В какой части фразы сказано, что существует общий алгоритм решения всех задач класса NP? Слово «быстрый» означает «за полиномиальное время». Это может быть O(N) а может O(N^100000)
Ну я не говорил, что показатель степени при N будет чем-то ограничен, O(N^100000) вполне себе быстрый алгоритм=)
Но смысл в том, что если хотя бы одна из NP-полных задач (назовём её f) будет решена, скажем за O(N^k), то для любой другой задачи из класса NP (назовём её g) можно будет назвать m и составить алгоритм, который будет решать её за O(N^m).
Он будет выглядеть так:
1) преобразовать входные данные задачи g в формат входных данных задачи f
2) запустить алгоритм решения задачи f
3) преобразовать ответ на задачу f в формат ответа для задачи g
4) ???
5) PROFIT
Шаги 1, 3 уже известно как выполнять «быстро» (т.к. задачу f причисляют к числу NP-полных только если удастся построить эти шаги). Как только выполнится шаг 3, то любую задачу g из NP можно будет решить «быстро».
Но смысл в том, что если хотя бы одна из NP-полных задач (назовём её f) будет решена, скажем за O(N^k), то для любой другой задачи из класса NP (назовём её g) можно будет назвать m и составить алгоритм, который будет решать её за O(N^m).
Он будет выглядеть так:
1) преобразовать входные данные задачи g в формат входных данных задачи f
2) запустить алгоритм решения задачи f
3) преобразовать ответ на задачу f в формат ответа для задачи g
4) ???
5) PROFIT
Шаги 1, 3 уже известно как выполнять «быстро» (т.к. задачу f причисляют к числу NP-полных только если удастся построить эти шаги). Как только выполнится шаг 3, то любую задачу g из NP можно будет решить «быстро».
Простите, но это чушь. На каком основании Вы считаете, что все задачи класса NP сводятся к некоторой одной задачи этого же класса? Для класса P, по крайней мере, такой задачи не существует. Сведите численное дифференцирование к игре с нулевой суммой или к СЛУ.
не «все задачи класса NP сводятся к некоторой одной задаче этого же класса»
а «все задачи класса NP сводятся к некоторой одной (а вообще к любой) задаче класса NP-полных (обратите внимание, что класс NP-полных и класс NP не одно и то же)»
> Для класса P, по крайней мере, такой задачи не существует.
Тут не понял, что вы имеете в виду.
а «все задачи класса NP сводятся к некоторой одной (а вообще к любой) задаче класса NP-полных (обратите внимание, что класс NP-полных и класс NP не одно и то же)»
> Для класса P, по крайней мере, такой задачи не существует.
Тут не понял, что вы имеете в виду.
Где Вы прочитали, что «все задачи класса NP сводятся к некоторой одной (а вообще к любой) задаче класса NP-полных»?.. Дайте цитату. В приведенной Вами фразе говорится о том, что если хотя бы одна задача класса NP-полных имеет решение за полиномиальное время, то все задачи класса NP-полных также имеют решение за полиномиальное время (свое решение), т.е. относятся к классу P, т.е. P=NP. Из этого не следует, что существует общий алгоритм решения всех задач класса NP.
Это я так перефразировал ту фразу из вики, на которую сослался в самоме первом комментарии.
Хорошо, по той же ссылке самое первое предложение: «В теории алгоритмов NP-полная задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время.»
Разбираем:
1) «NP-полная задача — задача из класса NP...»
Значит NPC является подмножеством NP, хотя это в нашем споре несущественно.
2) "… к которой можно свести любую другую задачу из класса NP..."
Одинаково ли мы понимаем термин «свести»?
По моему мнению свести задачу g к задаче f это значит описать такие два алгоритма p и q, такие, что g(x) = q(f(p(x))). Где q и p — это как раз и есть шаги 1 и 3 вышеприведенного алгоритма.
3) "… за полиномиальное время."
А это значит, что шаги 1 и 3 (или p и q) выполняются полиномиальное время.
А теперь если нашлась такая f <- NPC, которая решается за полиномиальное время, то любую g <- NP можно решить за полиномиальное время, и решение будет таким: g(x) = q(f(p(x)))
Разве нет?
Хорошо, по той же ссылке самое первое предложение: «В теории алгоритмов NP-полная задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время.»
Разбираем:
1) «NP-полная задача — задача из класса NP...»
Значит NPC является подмножеством NP, хотя это в нашем споре несущественно.
2) "… к которой можно свести любую другую задачу из класса NP..."
Одинаково ли мы понимаем термин «свести»?
По моему мнению свести задачу g к задаче f это значит описать такие два алгоритма p и q, такие, что g(x) = q(f(p(x))). Где q и p — это как раз и есть шаги 1 и 3 вышеприведенного алгоритма.
3) "… за полиномиальное время."
А это значит, что шаги 1 и 3 (или p и q) выполняются полиномиальное время.
А теперь если нашлась такая f <- NPC, которая решается за полиномиальное время, то любую g <- NP можно решить за полиномиальное время, и решение будет таким: g(x) = q(f(p(x)))
Разве нет?
Вы правы. Только найти p и q в общем не легче, чем найти сам алгоритм решения задачи. Поэтому я не считаю возможным говорить о нахождении универсального решения, которое можно портировать.
Ну формально, годные p и q находятся в процессе доказательства того, что f является NP-полной (не знаю, бывают ли не конструктивные доказательства полноты).
То есть при «портировании» полиномиального решения задачи f для решения задачи g заново искать p и q не придётся.
На практике же, так как доказательства пишут математики, а не программисты, эти p и q могут быть хоть и полиномиальными, но очень высокой степени, а посему неудобными для практического применения.
А так как для практических задач часто бывает важна не то что степень полинома, а даже константный множитель, то разумеется будут для каждой задачи пытаться найти более быстрое решение чем q(f(p(x))).
То есть при «портировании» полиномиального решения задачи f для решения задачи g заново искать p и q не придётся.
На практике же, так как доказательства пишут математики, а не программисты, эти p и q могут быть хоть и полиномиальными, но очень высокой степени, а посему неудобными для практического применения.
А так как для практических задач часто бывает важна не то что степень полинома, а даже константный множитель, то разумеется будут для каждой задачи пытаться найти более быстрое решение чем q(f(p(x))).
формально, годные p и q находятся в процессе доказательства того, что f является NP-полной
А вот это утверждение требует доказательства. Доказать существование решения и найти его не одно и то же. Для класса NP-полных задач доказана возможность их сводимости друг к другу, но из этого не следует, что найден универсальный алгоритм сводимости. В этом, собственно, и есть изначальный предмет нашего спора. Существование q и p доказано, но они не найдены ни в рамках класса NP-полных задач, ни в рамках NP-задач.
А вот это утверждение требует доказательства. Доказать существование решения и найти его не одно и то же. Для класса NP-полных задач доказана возможность их сводимости друг к другу, но из этого не следует, что найден универсальный алгоритм сводимости. В этом, собственно, и есть изначальный предмет нашего спора. Существование q и p доказано, но они не найдены ни в рамках класса NP-полных задач, ни в рамках NP-задач.
Ну раз f NP-полна, то этот факт был доказан.
Значит либо были найдены эти p и q, либо было доказано их существование.
Как доказать сводимость, не описывая конструктивно алгоритм сведения (от противного что ли?) мне сложно представить.
Я эту тему глубоко не копал, так что с 100% уверенностью утверждать не могу, но процесс доказательства что какая-то задача f является NP-полной интуитивно видится мне примерно таким:
1) возьмём какую-то задачу h, для которой уже доказано, что она NP-полна
2) сведём задачу h к f (построив при этом нужные p и q)
3) раз все задачи из NP были сводимы к h, то теперь они сводимы и к f
По хорошему тут бы вам привести пример задачи f, для которой доказано, что она NP-полна, но при этом в доказательстве сам алгоритм сведения произвольной задачи из NP к f не представлен. Это бы послужило доказательством вашей правоты.
А мне бы на любой ваш пример говорить: «Да вот же он: алгоритм сведения: '...', напрямую вытекает из доказательства».
Но понимаю, что искать пример лень, так что у меня аргументы заканчиваются.
Значит либо были найдены эти p и q, либо было доказано их существование.
Как доказать сводимость, не описывая конструктивно алгоритм сведения (от противного что ли?) мне сложно представить.
Я эту тему глубоко не копал, так что с 100% уверенностью утверждать не могу, но процесс доказательства что какая-то задача f является NP-полной интуитивно видится мне примерно таким:
1) возьмём какую-то задачу h, для которой уже доказано, что она NP-полна
2) сведём задачу h к f (построив при этом нужные p и q)
3) раз все задачи из NP были сводимы к h, то теперь они сводимы и к f
По хорошему тут бы вам привести пример задачи f, для которой доказано, что она NP-полна, но при этом в доказательстве сам алгоритм сведения произвольной задачи из NP к f не представлен. Это бы послужило доказательством вашей правоты.
А мне бы на любой ваш пример говорить: «Да вот же он: алгоритм сведения: '...', напрямую вытекает из доказательства».
Но понимаю, что искать пример лень, так что у меня аргументы заканчиваются.
Доказательство NP-полноты задачи проводится через доказательство сводимости ее к некоторой задаче, для которой уже доказано принадлежность к классу NP-полных. Какая задача была первой — сказать не могу.
Но доказать существование решения — не обязательно найти его. Например, основная теорема алгебры доказывает существование n корней многочлена степени n, но не определяет алгоритм, как их найти.
Лет n назад, когда изучал теорию алгоритмов, натыкался на доказательство NP-полноты задачи (кажется, коммивояжера), но универсального алгоритма сводимости не припомню. Поэтому я и утверждаю, что нахождение полиномиально сложного алгоритма для одной задачи класса NP-полных не приведет а нахождению алгоритма решения всех NP-задач.
Но доказать существование решения — не обязательно найти его. Например, основная теорема алгебры доказывает существование n корней многочлена степени n, но не определяет алгоритм, как их найти.
Лет n назад, когда изучал теорию алгоритмов, натыкался на доказательство NP-полноты задачи (кажется, коммивояжера), но универсального алгоритма сводимости не припомню. Поэтому я и утверждаю, что нахождение полиномиально сложного алгоритма для одной задачи класса NP-полных не приведет а нахождению алгоритма решения всех NP-задач.
NP-полные задачи — подмножество множества NP-задач. Попробуйте еще раз внимательно прочитать то, о чем пишет Википедия.
Приношу свои извинения, не до конца понял, что Вы имели ввиду. Фактически, если существование алгоритма хотя бы для одной NP-полной задачи, можно будет свести к ее решению всех задач класса NP. Но алгоритм сведения NP-задачи к некоторой NP-полной задаче не является общим. Я привык рассматривать это как отдельный алгоритм решения задачи. Поэтому не считаю возможным сказать, что одно решение может быть портировано под некоторое общее.
P=NP грубо говоря означает, что проверить решение не сложнее, чем найти это решение. Асимметричная криптография как раз основана на таких задачах, которые в прямую сторону решаются просто, а в обратную — сложно. Если P=NP, по открытому ключу можно восстановить закрытый.
Я думаю, что минус не в необходимости использования только рекомендованных параметров, а в том, что расшифровывание проходит с некоторой вероятностью отличной от 1.
>> Разработчики NTRU утверждают, что для рекомендуемых параметров с вероятностью почти равной 1 коэффициенты всегда будут располагаться в интервале (-q/2;q/2]
Пример DOS атаки, основываясь лишь на описании протокола (я уже не говорю про реализацию).
Допустим, NTRU используется в протоколе обмена ключами и мы попали на ситуацию, когда «коэффициенты полученного многочлена a(x) не лежат в интервале (–q/2, q/2]. ». В том случае, по идее, нужно заново перегинерировать r(x). Но Боб у нас «плохой парень» и он опять использует r(x) из предыдущего шага и отсылает C(X) Алисе. В результате Алиса лишь выполняет холостые шаги по расшифрованию сообщений и отсылке сообщений об ошибке.
Теоретически, можно исправить эту проблему при реализации алгоритма. Однако в общем случае данная атака уместна.
>> Разработчики NTRU утверждают, что для рекомендуемых параметров с вероятностью почти равной 1 коэффициенты всегда будут располагаться в интервале (-q/2;q/2]
Пример DOS атаки, основываясь лишь на описании протокола (я уже не говорю про реализацию).
Допустим, NTRU используется в протоколе обмена ключами и мы попали на ситуацию, когда «коэффициенты полученного многочлена a(x) не лежат в интервале (–q/2, q/2]. ». В том случае, по идее, нужно заново перегинерировать r(x). Но Боб у нас «плохой парень» и он опять использует r(x) из предыдущего шага и отсылает C(X) Алисе. В результате Алиса лишь выполняет холостые шаги по расшифрованию сообщений и отсылке сообщений об ошибке.
Теоретически, можно исправить эту проблему при реализации алгоритма. Однако в общем случае данная атака уместна.
Какая то она RSA подобная… Видимо алгоритм для квантового компьютера может быть адаптирован.
А так алгоритм похож на неуловимого Джо. Пока его широко не используют, его никто не ломает.
А так алгоритм похож на неуловимого Джо. Пока его широко не используют, его никто не ломает.
Ничего не понял, но вы меня успокоили.
1. что такое «ослепляющий» многочлен и как он оказался у Алисы?
2. на выходе при расшифровке имеем не сообщение, а исходный многочлен, зашифрованный Бобом
3. не увидел тут правила сопоставления сообщению многочлена — это какое-то общеизвестное правило, или о нем тоже нужно договариваться?
отсутствие публикаций о серьезных уязвимостях за практически 15-летний период существования, позволяет с оптимизмом смотреть на его дальнейшее использование
если в футболе игрок весь матч простоит около углового флажка его тоже за весь матч никто не обыграет.
то, что алгоритм за 15 лет не получил известности говорит лишь о слабом у нему интересе со стороны криптосообщества либо ввиду его непрактичности, либо очевидной слабости. подобных алгоритмов изобретается каждый год десятки, но что с того?
вообще, странное позиционирование относительно RSA. Последний имеет элементарную структуру, прост в понимании и реализации. Мелкий (учитывая схему применения) прирост в производительности ничего не дает, ровно как и «увеличение стойкости» к брутфорсу. Кроме использования многочленов (почему не матриц? векторов?) алгоритм не предлагает ничего нового, а мифический враг в лице потенциально изобретенного квантового компьютера — не повод все бросать и отказываться от RSA.
ну и напоследок (имхо) вот этого:
для восстановления секретного ключа атакующему потребуется отправить всего порядка 10 подобранных шифротекстов.
достаточно, чтобы не воспринимать алгоритм всерьез.
2. на выходе при расшифровке имеем не сообщение, а исходный многочлен, зашифрованный Бобом
3. не увидел тут правила сопоставления сообщению многочлена — это какое-то общеизвестное правило, или о нем тоже нужно договариваться?
отсутствие публикаций о серьезных уязвимостях за практически 15-летний период существования, позволяет с оптимизмом смотреть на его дальнейшее использование
если в футболе игрок весь матч простоит около углового флажка его тоже за весь матч никто не обыграет.
то, что алгоритм за 15 лет не получил известности говорит лишь о слабом у нему интересе со стороны криптосообщества либо ввиду его непрактичности, либо очевидной слабости. подобных алгоритмов изобретается каждый год десятки, но что с того?
вообще, странное позиционирование относительно RSA. Последний имеет элементарную структуру, прост в понимании и реализации. Мелкий (учитывая схему применения) прирост в производительности ничего не дает, ровно как и «увеличение стойкости» к брутфорсу. Кроме использования многочленов (почему не матриц? векторов?) алгоритм не предлагает ничего нового, а мифический враг в лице потенциально изобретенного квантового компьютера — не повод все бросать и отказываться от RSA.
ну и напоследок (имхо) вот этого:
для восстановления секретного ключа атакующему потребуется отправить всего порядка 10 подобранных шифротекстов.
достаточно, чтобы не воспринимать алгоритм всерьез.
1. Ослепляющий многочлен-случайно выбранный полином использующийся для увеличения случайности зашифрованных данных. Алисе он не нужен т.к. в процессе расшифровки слагаемое с этим полиномом сокращается и остается только исходное сообщение M.
2. Согласен.
3. Я честно признаюсь нигде не нашел данных правил для случая p=3. Для случая p=2 в качестве полинома просто берут двоичную запись сообщения.
Не стал бы заявлять столь категорично, все таки алгоритм разрабатывался не условным дядей Ваней из Саратова, а достаточно известными в криптосообществе людьми и сказать что это неуловимый Джо, потому что нафиг он никому не нужен нельзя.
Здесь с вами согласен, но прям все бросить и переходить на NTRU никто и не призывает. Просто вариант на будущее не более.
Да бросьте, а для взлома с адаптированным подобраным шифротекстом алгоритма RSA без схем дополнений вообще достаточно одного подобранного шифротекста, и что теперь не воспринимать алгоритм RSA всерьез?
2. Согласен.
3. Я честно признаюсь нигде не нашел данных правил для случая p=3. Для случая p=2 в качестве полинома просто берут двоичную запись сообщения.
то, что алгоритм за 15 лет не получил известности говорит лишь о слабом у нему интересе со стороны криптосообщества
Не стал бы заявлять столь категорично, все таки алгоритм разрабатывался не условным дядей Ваней из Саратова, а достаточно известными в криптосообществе людьми и сказать что это неуловимый Джо, потому что нафиг он никому не нужен нельзя.
а мифический враг в лице потенциально изобретенного квантового компьютера — не повод все бросать и отказываться от RSA
Здесь с вами согласен, но прям все бросить и переходить на NTRU никто и не призывает. Просто вариант на будущее не более.
достаточно, чтобы не воспринимать алгоритм всерьез.
Да бросьте, а для взлома с адаптированным подобраным шифротекстом алгоритма RSA без схем дополнений вообще достаточно одного подобранного шифротекста, и что теперь не воспринимать алгоритм RSA всерьез?
Да бросьте, а для взлома с адаптированным подобраным шифротекстом алгоритма RSA без схем дополнений вообще достаточно одного подобранного шифротекста, и что теперь не воспринимать алгоритм RSA всерьез?
совершенно верно, поэтому RSA сейчас чаще всего не алгоритм, а протокол. ну компания еще такая есть.
совершенно верно, поэтому RSA сейчас чаще всего не алгоритм, а протокол. ну компания еще такая есть.
Вот и NTRU если когда и будет использоваться на практике то тоже только как протокол NTRU-FORST, к примеру.
Хех ну и компания разумеется, кудаж без нее то.:) Ntru Cryptosystems, Inc.
Хех ну и компания разумеется, кудаж без нее то.:) Ntru Cryptosystems, Inc.
[quote]
Не стал бы заявлять столь категорично, все таки алгоритм разрабатывался не условным дядей Ваней из Саратова, а достаточно известными в криптосообществе людьми и сказать что это неуловимый Джо, потому что нафиг он никому не нужен нельзя.
[/quote]
все дело в том, что алгоритм не признан (поправьте если ошибаюсь) никаким из стандартов, а, следовательно, усилия, направленные на его взлом не сопоставимы с объемом исследования например AES или того же RSA.
Не стал бы заявлять столь категорично, все таки алгоритм разрабатывался не условным дядей Ваней из Саратова, а достаточно известными в криптосообществе людьми и сказать что это неуловимый Джо, потому что нафиг он никому не нужен нельзя.
[/quote]
все дело в том, что алгоритм не признан (поправьте если ошибаюсь) никаким из стандартов, а, следовательно, усилия, направленные на его взлом не сопоставимы с объемом исследования например AES или того же RSA.
странно, хотел посмотреть как работает цитирование, вместо этого камент добавился…
что касается авторитета авторов — опять же не показатель: Куртуа, несмотря на всю свою весомость, иногда выдает довольно странные вещи.
что касается авторитета авторов — опять же не показатель: Куртуа, несмотря на всю свою весомость, иногда выдает довольно странные вещи.
все дело в том, что алгоритм не признан (поправьте если ошибаюсь) никаким из стандартов
Ошибатесь, если верить вот этой ссылке, то NTRU принят двумя стандартами:
первый — IEEE P1363.1: Public-Key Cryptographic Techniques Based on Hard Problems over Lattices;
второй — ANSI X9.98: Lattice-Based Polynomial Public Key Establishment Algorithm for the Financial Services Industry. Конечно это не означает, что его исследовали так же тщательно как приведенные вами AES или RSA, но по крайней мере эти исследования все-таки были.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
NTRUEncrypt криптосистема будущего?