08.02 // Выполнение протокола Диффи-Хеллмана во вложенных алгебраических структурах
Протокол Диффи-Хеллмана является истоком криптографии с открытым ключом и до сих пор применяется достаточно широко. Исходный простейший его вариант использует в качестве основы мультипликативную группу целых чисел Z*p по модулю простого числа p. Также есть открытый элемент g ∈ Z*p, который является примитивным корнем по модулю p.
Сам классический протокол выглядит так:
- Алиса выбирает целое число a, вычисляет A = ga mod p и публикует A.
- Боб выбирает целое число b, вычисляет B = gb mod p и публикует B.
- Алиса вычисляет KA = Ba mod p.
- Боб вычисляет KB = Ab mod p.
В итоге у Алисы и Боба получается совместно выведенный ключ K = KA = KB = gba mod p = gab mod p.
Безопасность протокола зависит от правильного выбора параметров, в т.ч. g. Для взлома протокола пассивный атакующий (Ева) должна вычислить gab на основании знания g и перехваченных параметров обмена ga и gb, что, как общепринято считать, сводится к труднорешаемой задаче поиска дискретного логарифма: нахождения a из g и ga. Однако, строгого доказательства эквивалентности решения проблемы Диффи-Хеллмана к поиску дискретных логарифмов до настоящего времени не существует. Также как и не существует строгого доказательства отсутствия простых методов решения таких задач.
С практической точки зрения, исполнение DH-протокола в целых числах с безопасными значениями параметров высокозатратно по вычислительным ресурсам для обменивающихся сторон и может быть узким местом при вычислениях, связанных с множественной обработкой данных или при работе на миниатюрных устройствах.
Попытки оптимизации DH-протокола путём переноса его в различные алгебраические структуры применялись неоднократно. При этом признанно успешным оказалось лишь выполнение DH в группах точек эллиптических кривых.
Очередное оригинальное исследование по нестандартному выполнению DH-протокола представили Delaram KahrobaeI, Charalambos Koupparis и Vladimir Shpilrain (CUNY Graduate Center and City Tech, The City College of New York, City University of New York).
Они использовали алгебраические группы над кольцами, получая т.н. групповое кольцо, над котором впоследствии развернули матрицы. Полученная вложенная структура вида Mk (Zn [Sm ]) обладает очевидным интересным свойством: при небольших размерах составляющих элементов m, n, k, размер самой структуры получается достаточно большим. Что с одной стороны позволяет эффективно проводить вычисления, сохраняя небольшой размер ключа, а сдругой стороны обеспечить безопасность за счёт большой величины составного алгебраического объекта.
Так, один из вариантов протокола выглядит следующим образом:
- Алиса выбирает открытую матрицу M ∈ Mk (Zn [Sm ]) и большое положительное число a, вычисляет Ma и публикует M, Ma.
- Боб выбирает другое большое положительное число b и публикует Mb.
- Обе стороны вычисляют совместный ключ K = (Ma) b = (Mb) a
Вычисление совместного ключа фактически сводится к набору операций умножения матриц в составных полугруппах, что по подсчётам авторов, является очень эффективным вычислительным алгоритмом.
Авторы считают, что в перспективе их алгоритм может превзойти методы, основанные на эллиптических кривых, противостоять атакам малых-больших шагов, методу Поллинга-Хеллмана, ро-методу Поллинга, а также быть стойким против методов анализа на квантовых компьютерах.
Источник: ArXiV.org: Cryptography and Security, Group Theory.
См. также: Асимметричные алгоритмы на основе тропической алгебры.
комментариев: 1515 документов: 44 редакций: 5786
Есть ли простой способ объяснить, почему она труднорешаемая? Ведь многие похожие задачи решаются очень легко в теории чисел.
Сама статья, стр. 14:
А я в домового верю, и что теперь?И дальше пошло обсуждение несводимости к HSP. Ну, дак пусть честно и озвучат, что их метод DH безопасен против стандартного алгоритма Шора. Доказательство безопасности против любого квантового алгоритма я у них не увидел. В заключении, стр. 15, всё ещё короче:Ну, вы поняли.
Вообще-то, доказательство отсутствия эффективного квантового алгоритма для решения произвольной задачи — hard problem. Кажется, есть всего несколько задач, про которые известно, что они могут быть решены быстрее квантовыми алгоритмами, и всего несколько задач, про которые известно, что они не могут быть решены быстрее даже с помощью них. Есть стойкое подозрение, что если такую заяву отошлют на реферирование тем, кто занимается quantum complexity theory, они её раскритикуют в пух и прах.
Наконец, статья только в архиве. Пока в журнал не приняли, говорить о чём-либо рано.
комментариев: 9796 документов: 488 редакций: 5664
Примерно по той же причине, что и RSA. И там, и там возведение в степень по модулю. Только в одном случае модуль завязан на произведение двух простых, а в другом — по этому модулю в степень возводится примитивный корень, порождающий все перестановки группы. Пусть не совсем случайным, но с учётом избыточности непредсказуемым образом (поэтому согласованный ключ обычно ещё и хэшируют, чтобы не было утечки битов). В одном случае для взлома нахождение требуется обратного по модулю φ(n), для чего не придумано ничего лучше факторизации с различными вычислительными наворотами вокруг метода решета. Вычисление дискретного логарифма — вторая общепризнанная вычислительно-сложная задача, для решения которой не придумано пока ничего лучше методов Полларда.
Так и хорошо, возможно авторы честно написали про отсутствии строгого доказательства. Но я не знаю тонкостей, может эта проблема как-то вообще тривиально обосновывается: вот есть к примеру асимметричная криптография на решётках и там само собой подразумевается "раз решётки — значит квантовостойкое". Может это где-то уже фундаментально доказали один раз и каждый раз на это ссылаться не нужно. Здесь авторы указывают, что квантовостойкости способствует неинвертируемость матриц. Может это тоже какой-то общеизвестный факт. И насколько я могу судить в меру своего понимания, всё, что кроме Шора, считается бесперспективным пока. Вроде, к примеру, было
доказанопоказано отсутствие возможностей прицельного симметричного криптоанализа на каких-то принципиально новых квантовых алгоритмах, кроме как упрощения перебора. Не зная особенностей тенденций постквантовой криптографии, трудно придираться к корректности формулировок.Факторизация и нахождение дискретного логарифма в большинстве алгебраических групп попадают в число "быстрее решаемых", что ставит всю ныне используемую асимметричную криптографию (включая ECC) под удар в случае появления квантовых вычислений.
Чего бы я реально опасался, так это вот такого. Но тем не менее, все такие исследования стоит держать во внимании. От них м.б. неожиданный косвенный полезный эффект — даже в симметричной криптографии или криптоанализе. Или хотя бы полезно знать, что такое уже когда-то предлагали.
комментариев: 1515 документов: 44 редакций: 5786
Кому скучно, листайте на стр. 16 данной Ааронсоном ссылки, там есть сводная картинка.
Давайте смотреть правде в глаза: это не есть общеизвестные факты для тех, кто не занимается теорией сложности алгоритмов. Даже в статье по теории сложности соответствующую ссылку поставили бы. Я уже не говорю о том, что статья пишется по классическому крипто, т.е. для аудтории, которая квантовую теорию сложности не знает вообще. Какой ещё тут может быть «общеизвестный факт»?
Более того, авторы ссылаются только на один-единственный первоисточник — оригинальную работу Шора 94-го года. Что, с 1994-го тема заглохла? Шор сделал настолько всё, что после него ничего нового за 19 лет не было опубликовано? Даже не смешно. Более того, претензия обоснована в любом случае: у них нигде в их рассуждениях не говорится о безопасности против любого квантового алгоритма, а анализируется только Шор, в заключении же делается самое общее заявление, что делает его де юре ложью (не знаю уж, как de facto).
Кстати, количество и релевантность ссылок — один из простых методов оценки качества работы. Хотя бывают и исключения, но общий смысл следующий: если вы знакомы с литературой и трудами в области, у вас необходимо естественным образом вылезет большой список, на который нужно сослаться, даже если не хочется; когда же работу публикуют некомпетентные авторы, т.е. незнакомые с литературой, всё ограничивается ссылками на книги или на популярные обзоры. Иногда из этих книг или обзоров они выцепляют ссылки на работы-первоисточники и цитируют их, как в данном случае.
Говоря сухим языком, для этих задач доказано, что они принадлежат классу сложности BQP. У авторов же нет даже озвучивания, к какому классу сложности их задача принадлежит.
комментариев: 9796 документов: 488 редакций: 5664
Это во всех работах так, если я не путаю, даже со спец. конференции PostQuantum Crypto. Упоминают только стойкость против Шора (вроде бывают какие-то мелкие исключения). Но вот, чтобы подробно разбиралась квантовая стойкость, так как вы говорите — не встречал даже в специфических работах и обзорах по постквантовой криптографии. Может за этим есть какая-то проработанная теория, которую интересующиеся типа должны знать и которую даже в источниках не указывают, мне об этом неизвестно.
Строгого доказательства принадлежности алгоритмов к квантовым классам сложности в таких работах не встречал.
комментариев: 1515 документов: 44 редакций: 5786
Для меня это звучит открытием, если честно. Если бы они доказывали принадлежность чего-то там к BQP, это ещё можно было бы понять как «ну, полнимальная сводимость к задаче факторизации (или чему там) полуочевидна ⇒ сложность нахождения решения не более, чем BQP». А вот как доказать отрицание? Из того, что их задача более не решается лобовым Шором, разве следует её принадлежность к другому классу сложности? Есть же тривиальный контрпример: ряд постквантовых алгоритмов оказался нестоек к классическому криптоанализу, т.е. был найден эффективный алгоритм, решающий эти задачи за полиномиальное время. Насколько я помню, квантовая модель вычислений включает себя и классическую, т.е. всё, что может быть решено полиномиально быстро классическими алгоритмами, может быть решено полиномиально быстро и квантовыми1. Грубо говоря, можно себе представлять, что КК может номинально работать, как классический компьютер, производящий классические операции над битами2. Т.о., почти по определению, некоторое постквантовое крипто оказалось уязвимым в т.ч. и к КК. И как же тут обойтись одним Шором?
Боюсь наговорить лишнего, но, имхо, создание постквантовой классической криптографии — не уровень компетенции классических криптографов, и не стоит им туда лезть. Я скорее поверю, что кто-то из квантовых информатиков разберётся в классическом крипто и что-то предложит квантово-стойкое, чем то, что кто-то из классических криптографов вдруг разберётся с квантовыми вычислениями. В любом случае, если речь идёт о безусловной безопасности (information-theoretical security), все уловки классической криптографии (то, в основном ради чего она существует и разрабатывается) идут лесом, тут скорее нужна теория информации per se для анализа, а не криптография.
Если не изменяет память, в Нильсоне & Чанге вопрос о задачах, эффективно решаемых/нерешаемых на КК, обсуждался примерно в таком ключе: очень мало что известно про такие задачи. Книжка не самая новая, с тех пор могло много что поменяться, но вряд ли очень сильно.
Наконец, что такое постквантовое крипто вообще? Если оно асимметричное, то я ещё могу допустить, что есть какие-то задачи из QMA, на которые можно завязаться3, но что делать с симметричным? Раз под ним нет никакой information-theoretic security изначально, то о чём вообще можно вести речь? Его класс сложности сугубо спеклятивен даже в рамках чисто классических вычислений, не говоря уже о квантовых, поскольку алгоритм строится по принципу запутывания. Насколько мне представляется, нет ни одного классического симметричного блочного шифра (одноразовый блокнот не считаем), про который доказана его принадлежность хотя бы к тому же NP. И что тогда считать безопасным против КК? По аналогии с классикой, в духе «ни один известный квантовый алгоритм не решает задачу за полиномиальное время ⇒ он КК-безопасен»? А нахождение квантового алгоритма, решающего задачу быстро, считать аналогом взлома классическим криптоанализом? Или постквантовое классическое симметричное крипто вообще не разрабатывается / не имеет смысла? Типа, эффективная длина ключа уполовинивается, и всё на том, дальше всё равно лучше не сделать?
1Имеет ли это смысл — это уже другой вопрос.
2Просто суперпозиция/запутанность (ку)битов не будет использоваться, и всё.
3Обсуждаемый пример с DH как раз к этому случаю относится.
комментариев: 9796 документов: 488 редакций: 5664
Симметричные криптоалгоритмы считаются условно идеальными и поэтому для их атак не работает никакой квантовый алгоритм, кроме Гровера, сокращающий перебор ключа на 2k/2. Поэтому их в PQC, действительно, вообще не рассматривают.
Возможность создания прицельных квантовых алгоритмов, которые бы что-то там конкретно по раундам внутренней структуры симм. алгоритма атаковали, вроде оценили как малореальную и на этом пока успокоились.
Не знаю, это доказанный или убедительно обоснованный факт, негласный консенсус сообщества специалистов или что-то ещё, но ни в каких работах это (возможно для экономии места) не раскрывают.
Вот самое новаторство по этой теме, которое вы так критиковали. Оно никем пока особо не признано, ничего лучше похоже вообще нет (широко неизвестно, игнорируется).
комментариев: 1515 документов: 44 редакций: 5786
Может, там всё и не так плохо, но я недоразобрался. Есть ряд идей, которые надо додумать и озвучить в той ветке, но это позже, сейчас времени на это не хватает.
Я отправил письменный запрос компенетному лицу. Надеюсь, что получу какой-нибудь ответ помимо «не знаю» (хотя бы устный и хотя бы в двух словах).
комментариев: 9796 документов: 488 редакций: 5664
Пока можете вводные части книжки Бернштейна почитать. С 15 по 32 стр. хотя бы. Это самый примитивный уровень, есть достаточное количество каких-то более специфичных публикаций именно со стороны криптографов. Но похоже, на этот консенсус все и полагаются.
очень крут, нереально крутзнает, о чём пишет, его квалификация в квантовой теории сложности вопросов не вызывает.комментариев: 9796 документов: 488 редакций: 5664
У нас был раньше на форуме Дэниэл Надь, который тоже предупреждал о DJB, он отказался с ним связываться, что-то зная о нём. Вообще, DJB уже давно всяким-таким известен, хамскими письмами, ещё какими-то выходками и пр.
Зато выиграл в своё время судебный процесс "DJB против США" по поводу регуляции криптографии, своими исследованиями успешно вытаскивает эллиптическую криптографию из под патентного гнёта, получил грант от НИСТ на проведение неформального конкурса на новые шифры на предполагаемыую замену AES и пр. Ещё один пример, что люди с тараканами в голове бывают полезны для общества. И полезная деятельность вполне себе бывает на грани неадекватности.
Если по-жизни уже попадались люди приблизительно такого склада и с ними как-то удавалось наладить контакт, то можете попробовать, это не так страшно, как кажется :)
По более содержательной части вашего сообщения быстрый ответ естественно невозможен, надо думать долго.
Понятно. Человек типа меня, значит.
Трудно что-то сказать, не зная человека, но всё же думаю, удалось бы наладить. Пока что с ним не встречался. Он вроде бы даже несколько раз приезжал к нам, вместе с Таней Ланге, но я не успел застать его, меня ещё тогда тут не было.
Людей, которые выбешивают, к сожалению, тоже удалось в жизни повстречать. Предполагаю, что 100 Бернштейнов вместе сложить если, такого мудака всё равно не получится. Очень редкий экземпляр, карикатурный хрестоматийно несмотря на то, что у него пол-сотни интересных и очень сильных работ в теме, да и диссер замечательный. Страдает семитизмом в самой крайней степени этого проявления, может помочь только
газовая камераэватанзия, без преувеличений. Сколько евреев в жизни перевидал и в науке и в жизни, но такое чудо, думал, возможно только в пропагандистских фильмах. Ан нет, ошибся. Главное, из-за таких характерных единиц потом на всей нации клеймо стоит. Как говорится, «работы их читайте, нопо делам их не поступайтене пытайтесь с ними хоть что-то обсуждать, испачакаетесь грязью так, что потом неделю мыться ходить будете». Человек совершеннонеадекватенболен, хотя пару интересных мыслей выудить с него с большим трудом всё же удалось. Надеюсь, разговаривал с ним первый и последний раз в этой жизни.Неплохо. Оказалось, что на работе имеется то же самое, но в бумажной печатной форме, взял почитать.
комментариев: 9796 документов: 488 редакций: 5664
Пожалуй, можно согласиться. Фейнмановские лекции по рассказам (сам их мало читал) тоже такие: мало формул, попытка на пальцах объяснить концептуально сложные вещи, представить читателю единую картину физического мировоззрения, но фейнмановские леции — это всё же 60-ые, с тех пор пол века прошло, а тут самое-самое свежее, о чём ещё ни в одной книге не писалось.
Ааронсону значительно повезло с тем, что он занимается областью, где работает много народа, и ещё больше народа просто интересуется этой областью. Соответственно, есть кому читать его статьи, цитировать их, выступать с докладами, создавать свою «тусовку». Во многих других областях КТИ с этим туже, интереса они порождают меньше, людей ими занимается меньше, но фундаментальная значимость тоже есть. Обратная сторона медали — в узкой мало кому интересной области проще стать королём, чем в популярной, где работает много грандов/топов.