Information Security
Cryptography
Programming
Mathematics
Comments 26
+1
Если я помню правильно, квантовые компьютеры могут решать факторизацию за O(exp(sqrt(n))) вместо O(exp(n)). Так что я бы не сказал, что вот прямо все, всей криптографии конец. Скорее наоборот. Получается, нужно просто увеличить длину ключа возведением текущей длины в квадрат. Получится порядка одного-пяти мегабайт, что кажется большим числом, но таковым на современных коннектах на самом деле не является.
+1
Если я правильно помню, то O(exp(sqrt(n))) — это для NP-полных задач, а конкретно для факторизации чисел оценка значительно лучше.
+1
Да, я освежил тему, вы правы. Похоже, действительно придется полностью новое все придумывать.
0

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

UFO landed and left these words here
UFO landed and left these words here
+1
Мне кажется вы упустили еше одну новость:

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

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

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

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