Бетонная безопасность

Криптографический анализ

В криптографии конкретная безопасность или точная безопасность — это ориентированный на практику подход, который направлен на получение более точных оценок вычислительной сложности состязательных задач, чем это позволяет полиномиальная эквивалентность . ^{[ требуется ссылка ]} Он количественно определяет безопасность криптосистемы, ограничивая вероятность успеха для противника, работающего в течение фиксированного периода времени. ^{[1] [ требуется лучший источник ]} Доказательства безопасности с точным анализом называются конкретными . ^{[2] [ требуется лучший источник ]}

Традиционно доказуемая безопасность является асимптотической : она классифицирует сложность вычислительных задач, используя сводимость за полиномиальное время. Безопасные схемы определяются как те, в которых преимущество любого вычислительно ограниченного противника пренебрежимо мало . Хотя такая теоретическая гарантия важна, на практике необходимо точно знать, насколько эффективно сокращение из-за необходимости инстанцирования параметра безопасности — недостаточно знать, что «достаточно большие» параметры безопасности подойдут. Неэффективное сокращение приводит либо к тому, что вероятность успеха для противника, либо к тому, что требования к ресурсам схемы больше желаемых. ^{[ требуется цитата ]}

Конкретная безопасность параметризует все ресурсы, доступные противнику, такие как время выполнения и память, а также другие ресурсы, специфичные для рассматриваемой системы, такие как количество открытых текстов, которые он может получить, или количество запросов, которые он может сделать к любым доступным оракулам . Тогда преимущество противника ограничено сверху как функция этих ресурсов и размера проблемы. Часто можно задать нижнюю границу (т. е. стратегию соперничества), соответствующую верхней границе, отсюда и название точная безопасность. ^{[ необходима цитата ]}

Примеры

Конкретные оценки безопасности были применены к криптографическим алгоритмам:

• В 1996 году были предложены схемы цифровых подписей на основе криптосистем RSA и Рабина , которые, как было показано, взломать примерно так же сложно, как и оригинальные криптосистемы. ^[3]
• В 1997 году некоторые понятия конкретной безопасности ( лево- или правосторонняя неразличимость , реально- или случайно- неразличимость , безопасность «найти-и-угадать » и семантическая безопасность ) для симметричных алгоритмов шифрования были доказаны приблизительно эквивалентными в различных режимах работы блочного шифра, таких как CBC, CTR и XOR (вариант CBC без сохранения состояния). ^{[4] [ необходимо разъяснение ]}
• В 2017 году в диссертации было показано, что алгоритмы перечисления точек решетки и сокращения блоков решетки могут быть использованы для атаки на криптографию на основе решетки . ^[5]
• В 2021 году были продемонстрированы атаки типа «угадай-и-определи» и «угадай-и-декодируй» ^{[ требуется разъяснение ]} против предложенного генератора псевдослучайных чисел в NC0 , где экземпляры со значениями параметров, которые ранее считались имеющими 128-битную безопасность, были решены примерно за операции. ^{[6] [ требуется лучший источник ]} ${\displaystyle 2^{78}}$

Кроме того, программный инструмент под названием «Foundational Cryptography Framework», который встраивается в Coq , способен формально проверять доказательства конкретной безопасности. ^[7] Например, он способен проверять конкретную безопасность шифрования ElGamal . ^[7]

Ссылки

1. "Современное симметричное шифрование". Университет Мэриленда . Архивировано из оригинала 2017-09-10 . Получено 6 мая 2021 г.
2. Камара, Сени. "Lectures 2+3: Provable Security" (PDF) . Архивировано (PDF) из оригинала 2017-02-15 . Получено 6 мая 2021 .
3. Белларе, Михир; Рогауэй, Филип (1996). «Точная безопасность цифровых подписей — как подписывать с помощью RSA и Рабина» (PDF) . Достижения в криптологии — EUROCRYPT '96 . Конспект лекций по информатике. Том 1070. Springer-Verlag . С. 399–416. doi :10.1007/3-540-68339-9_34. ISBN 978-3-540-68339-1.
4. Белларе, Михир; Десаи, А.; Йокипии, Э.; Рогауэй, Филип (октябрь 1997 г.). «Конкретная обработка безопасности симметричного шифрования» (PDF) . Труды 38-го ежегодного симпозиума по основам компьютерной науки . стр. 394–403. doi :10.1109/SFCS.1997.646128. ISBN 0-8186-8197-7. S2CID  42604387.
5. Уолтер, Майкл (2017). «О конкретной безопасности решетчатой ​​криптографии». Калифорнийский университет в Сан-Диего . Получено 6 мая 2021 г.
6. Ян, Цзянь; Го, Цянь; Йоханссон, Томас; Лентмайер, Михаэль (3 марта 2021 г.). «Возвращаясь к конкретной безопасности псевдослучайного генератора Голдрайха». arXiv : 2103.02668 [cs.CR].
7. Petcher, Adam (14 октября 2014 г.). «Основополагающая структура криптографии». arXiv : 1410.3735 [cs.PL].

Внешние ссылки

• https://www.cs.purdue.edu/homes/jblocki/courses/555_Fall18/slides/Week2.pdf
• https://crypto.stanford.edu/~dabo/cryptobook/draft_0_3.pdf
• https://eprint.iacr.org/2006/278.pdf
• https://www.baigneres.net/downloads/2007_provable_security.pdf
• https://eprint.iacr.org/2020/1213.pdf