Ads
Comments 26
Если я помню правильно, квантовые компьютеры могут решать факторизацию за O(exp(sqrt(n))) вместо O(exp(n)). Так что я бы не сказал, что вот прямо все, всей криптографии конец. Скорее наоборот. Получается, нужно просто увеличить длину ключа возведением текущей длины в квадрат. Получится порядка одного-пяти мегабайт, что кажется большим числом, но таковым на современных коннектах на самом деле не является.
Если я правильно помню, то O(exp(sqrt(n))) — это для NP-полных задач, а конкретно для факторизации чисел оценка значительно лучше.
Да, я освежил тему, вы правы. Похоже, действительно придется полностью новое все придумывать.
UFO landed and left these words here
UFO landed and left these words here
Мне кажется вы упустили еше одну новость:

Учёные из университета Техаса предложили новый метод генерации случайных чисел, который позволяет комбинировать две относительно некачественные последовательности случайных чисел и получать качественный результат. Открытие может иметь далекоидущие последствия в области криптографии.

http://eccc.hpi-web.de/report/2015/119/

Исследования в этой области ведутся не одно десятилетие, но специалисты полагают, что в данном случае был совершён прорыв. До сих пор функции, которые генерируют качественные случайные последовательности на основе пары менее качественных, нуждались в более качественном «сырье».

Научная работа, описывающая новый метод, была опубликована в марте, а в июне её авторы, Дэвид Цукерман и Ишан Чаттопадхья, расскажут о своём открытии на симпозиуме по теории алгоритмов, которую проводит международная Ассоциация вычислительной техники (ACM).

В работе Цукермана и Чаттопадхьи предложена функция, принимающая случайные последовательности на n бит из двух источников со значениями мин-энтропии не менее logCn для достаточно большого значения C и выдающая случайный бит с ошибкой n−Ω(1). Лучший метод, известный ранее, требовал более качественных источников с мин-энтропией 0,499n.

«Мы продемонстрировали, что если у вас есть два низкокачественных источника случайных чисел, — а источники невысокого качества куда проще найти, — и они независимы друг от друга и не коррелируют между собой, то их можно комбинировать и получить случайное число высокого качества», — объясняет Цукерман.

https://threatpost.com/academics-make-theoretical-breakthrough-in-random-number-generation/118150/
Принято, спасибо ) Я как раз рассчитывал на то, что добрые комментаторы дополнят дайджест новостями, которые я пропустил
Простите за комментарий из read-only, но нет ли каких-либо достижений по криптографии на решётках? Субъективно, про них много говорят на различных докладах IACR
Как видно по слайду вначале статьи, NTRUEncrypt, который на решетках, активно исследуется. На данный момент есть рекомендуемые параметры (в википедии) которые считаются безопасными
А можно популярно — чем постквантовые алгоритмы принципиально отличаются от тех, которые превратятся в мусор? У них просто вычислительная сложность драматически выше?
Не обязательно. Просто квантовые компьютеры в определенных случаях могут некоторые вещи считать сильно быстрее обычных компов, за счет своей квантовой природы. А есть алгоритмы, которые не подвержены ускорению с помощью квантовых механизмов, их как раз активно изучают
Очень давно, где-то читал новость, про какие-то суперразреженные хеши (возможно новость была о премии за это дело), которые могут использоваться для криптографии. Не могу никаких концов в инете найти, а врезалось в память, может кому-то это о чём-то говорит?
Вроде, на симметричные схемы квантовая криптография не особо покушается, там так называемые «медленные квантовые алгоритмы» типа Гровера которые интересны скорее с точки зрения теории. Но ведь, наверное, есть случаи когда нужны именно асимметричные схемы вместо RSA? Вот те-же банковские операции, что с ними?
Ну, вообще именно из-за гровера рекоммендуют увеличивать размер ключей до 256 бит. Вчера как раз прочитал, что доказали его оптимальность. По поводу банковского сектора — там уже во всю орудует NTRU, жалко что он патентованый
Спасибо. Посмотрел — NTRU какой-то решёточный. Но решёточные же вроде и открытые есть.
В википедии ещё пишут, что теперь и у NTRU есть open source реализация. Кого тогда патент волнует? Но там даже не особо понятно из описания, почему он именно решёточный.
Мне кажется, из описания предельно понятно, почему он решеточный https://en.wikipedia.org/wiki/NTRUEncrypt Потому что, основан на проблеме поиска кратчайшего вектора в решетке. На счет реализаций хз. Реализации может и открытые, но сам алгоритм то патентованый. NTRU под GPL, поэтому опен сорс может юзать его. https://github.com/NTRUOpenSourceProject/ntru-crypto
Меня смутило, что там написано:
Breaking the cryptosystem is strongly related, though not equivalent, to the algorithmic problem of lattice reduction in certain lattices.

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

— HS1-SIV вряд ли считается самым перспективным, он весьма корявый и security level у него низкий (в одном из вариантов — 28 бит всего)
— GCM-SIV не является участником CAESAR, но авторы активно его продвигают, и он скоро станет стандартом IETF
— атака Альвена и Блоки на Argon2, на которую вы дали ссылку, уменьшает стоимость перебора на ASIC в два раза. Это хуже, чем результат авторов (в три раза).
Only those users with full accounts are able to leave comments. Log in, please.