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

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

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

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

Примеры

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

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

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

Ссылки

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

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

Эта статья, посвященная криптографии, незавершена . Вы можете помочь Википедии, расширив ее .

[1] «Современное симметричное шифрование» . Университет Мэриленда . Архивировано из оригинала 10 сентября 2017 г. Проверено 6 мая 2021 г.

[2] Камара, Сени. «Лекции 2+3: Доказуемая безопасность» (PDF) . Архивировано (PDF) из оригинала 15 февраля 2017 г. Проверено 6 мая 2021 г.

[3] Белларе, Михир; Рогауэй, Филип (1996). «Точная безопасность цифровых подписей — как подписывать с помощью RSA и Rabin» (PDF) . Достижения в криптологии — EUROCRYPT '96 . Конспекты лекций по информатике. Том. 1070. Шпрингер-Верлаг . стр. 399–416. дои : 10.1007/3-540-68339-9_34 . ISBN 978-3-540-68339-1 .

[4] Белларе, Михир; Десаи, А.; Йокипии, Э.; Рогауэй, Филип (октябрь 1997 г.). «Конкретные меры безопасности симметричного шифрования» (PDF) . Материалы 38-го ежегодного симпозиума по основам информатики . стр. 394–403. дои : 10.1109/SFCS.1997.646128 . ISBN 0-8186-8197-7 . S2CID 42604387 .

[5] Уолтер, Майкл (2017). «О конкретной безопасности решетчатой криптографии» . Калифорнийский университет в Сан-Диего . Проверено 6 мая 2021 г.

[6] Ян, Цзянь; Го, Цянь; Йоханссон, Томас; Лентмайер, Михаэль (3 марта 2021 г.). «Возвращение к конкретной безопасности псевдослучайного генератора Гольдрейха». arXiv : 2103.02668 [ cs.CR ].

[:0-7] Перейти обратно: ^а ^б Петчер, Адам (14 октября 2014 г.). «Основная основа криптографии». arXiv : 1410.3735 [ cs.PL ].

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]