Дайджест последних достижений в области криптографии. Выпуск нулевой

[Monnoroch]

Если я помню правильно, квантовые компьютеры могут решать факторизацию за O(exp(sqrt(n))) вместо O(exp(n)). Так что я бы не сказал, что вот прямо все, всей криптографии конец. Скорее наоборот. Получается, нужно просто увеличить длину ключа возведением текущей длины в квадрат. Получится порядка одного-пяти мегабайт, что кажется большим числом, но таковым на современных коннектах на самом деле не является.

[potan]

Если я правильно помню, то O(exp(sqrt(n))) — это для NP-полных задач, а конкретно для факторизации чисел оценка значительно лучше.

[Monnoroch]

Да, я освежил тему, вы правы. Похоже, действительно придется полностью новое все придумывать.

[ComradeAndrew]

Не подскажите ли статью где можно наглядно посмотреть на сколько лучше?

[potan]

Алгоритм Шора

[ComradeAndrew]

И действительно сильно упрощает факторизацию.

[Scratch]

Да, это они конечно сплоховали. Спасибо, не знал

[lightjedi]

В Кузнечике и Стрибоге просто один и тот же S-box.

[Scratch]

Принято, спасибо ) Я как раз рассчитывал на то, что добрые комментаторы дополнят дайджест новостями, которые я пропустил

[El_corona]

Простите за комментарий из read-only, но нет ли каких-либо достижений по криптографии на решётках? Субъективно, про них много говорят на различных докладах IACR

[Scratch]

Как видно по слайду вначале статьи, NTRUEncrypt, который на решетках, активно исследуется. На данный момент есть рекомендуемые параметры (в википедии) которые считаются безопасными

[Stas911]

А можно популярно — чем постквантовые алгоритмы принципиально отличаются от тех, которые превратятся в мусор? У них просто вычислительная сложность драматически выше?

[Scratch]

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

[VaalKIA]

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

[quverty]

Вроде, на симметричные схемы квантовая криптография не особо покушается, там так называемые «медленные квантовые алгоритмы» типа Гровера которые интересны скорее с точки зрения теории. Но ведь, наверное, есть случаи когда нужны именно асимметричные схемы вместо RSA? Вот те-же банковские операции, что с ними?

[Scratch]

Ну, вообще именно из-за гровера рекоммендуют увеличивать размер ключей до 256 бит. Вчера как раз прочитал, что доказали его оптимальность. По поводу банковского сектора — там уже во всю орудует NTRU, жалко что он патентованый

[quverty]

Спасибо. Посмотрел — NTRU какой-то решёточный. Но решёточные же вроде и открытые есть.

[Scratch]

да чет не очень их много https://en.wikipedia.org/wiki/Lattice-based_cryptography

[quverty]

В википедии ещё пишут, что теперь и у NTRU есть open source реализация. Кого тогда патент волнует? Но там даже не особо понятно из описания, почему он именно решёточный.

[Scratch]

Мне кажется, из описания предельно понятно, почему он решеточный https://en.wikipedia.org/wiki/NTRUEncrypt Потому что, основан на проблеме поиска кратчайшего вектора в решетке. На счет реализаций хз. Реализации может и открытые, но сам алгоритм то патентованый. NTRU под GPL, поэтому опен сорс может юзать его. https://github.com/NTRUOpenSourceProject/ntru-crypto

[quverty]

Меня смутило, что там написано:

Breaking the cryptosystem is strongly related, though not equivalent, to the algorithmic problem of lattice reduction in certain lattices.

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

[Scratch]

вот и ищут )

[lightjedi]

Я бы немного подкорректировал:

— HS1-SIV вряд ли считается самым перспективным, он весьма корявый и security level у него низкий (в одном из вариантов — 28 бит всего)
— GCM-SIV не является участником CAESAR, но авторы активно его продвигают, и он скоро станет стандартом IETF
— атака Альвена и Блоки на Argon2, на которую вы дали ссылку, уменьшает стоимость перебора на ASIC в два раза. Это хуже, чем результат авторов (в три раза).