Параметр безопасности

В криптографии параметр безопасности — это способ измерения того, насколько «сложно» злоумышленнику взломать криптографическую схему. Существует два основных типа параметров безопасности: вычислительные и статистические , часто обозначаемые $\kappa$ и $\lambda$ , соответственно. Грубо говоря, параметр вычислительной безопасности — это мера входного размера вычислительной задачи , на которой основана криптографическая схема, определяющая ее вычислительную сложность, тогда как параметр статистической безопасности — это мера вероятности, с которой злоумышленник сможет взломать криптографическую схему. схема (что бы это ни значило для протокола).

Параметры безопасности обычно выражаются в унарном представлении , т.е. $\kappa$ выражается как строка $\kappa$ $1$ с, $\kappa =1\cdots 1$ , условно записываемый как $1^{\kappa }$ - чтобы временная сложность криптографического алгоритма была полиномиальной по размеру входных данных.

Вычислительная безопасность

Безопасность криптографических примитивов зависит от сложности некоторых сложных проблем . Устанавливается параметр вычислительной безопасности $\kappa$ такой, что $O(2^{\kappa })$ вычисления считаются неразрешимыми .

Примеры

Если безопасность схемы зависит от секретности ключа псевдослучайной функции (PRF), то мы можем указать, что ключ PRF должен выбираться из пространства $\{0,1\}^{\kappa }$ так что для перебора требуется $O(2^{\kappa })$ вычислительная мощность.
В криптосистеме RSA параметр безопасности $\kappa$ обозначает длину в битах модуля n ; поэтому положительное целое число n должно быть числом из набора {0, ..., 2 ^$\kappa$ - 1}.

Статистическая безопасность

Безопасность в криптографии часто основана на том факте, что статистическое расстояние между

распространение, основанное на секрете, и
смоделированное распространение , созданное организацией, которая не знает секрета

мал. Мы формализуем это, используя параметр статистической безопасности, говоря, что распределения статистически близки , если статистическое расстояние между распределениями может быть выражено как незначительная функция параметра безопасности. Устанавливается параметр статистической безопасности $\sigma$ такой, что $O(2^{-\sigma })$ считается «достаточно небольшим» шансом на победу противника.

Рассмотрим следующие две широкие категории атак злоумышленников на данную криптографическую схему: атаки, в которых злоумышленник пытается узнать секретную информацию, и атаки, в которых злоумышленник пытается убедить честную сторону принять ложное утверждение за истинное (или наоборот). ). В первом случае, например, в схеме шифрования с открытым ключом , злоумышленник может получить большой объем информации, из которой он может попытаться узнать секретную информацию, например, исследуя распределение зашифрованных текстов для фиксированного открытого текста, зашифрованного разными способами. случайность. Во втором случае может оказаться, что противник должен угадать вызов или секрет и может сделать это с некоторой фиксированной вероятностью; при этом мы можем говорить о распределениях, рассматривая алгоритм выборки задачи в протоколе. В обоих случаях мы можем говорить о вероятности «победы» противника в широком смысле и можем параметризовать статистическую безопасность, требуя, чтобы распределения были статистически близкими в первом случае, или определяя пространство проблем, зависящее от параметра статистической безопасности. во втором случае.

Примеры

В схемах шифрования одним из аспектов безопасности является (на высоком уровне) то, что все, что можно узнать об открытом тексте с учетом зашифрованного текста, можно также узнать из случайно выбранной строки (той же длины, что и зашифрованные тексты), которая не зависит от открытый текст. Формально нужно было бы показать, что равномерное распределение по набору строк фиксированной длины статистически близко к равномерному распределению по пространству всех возможных зашифрованных текстов.
В протоколах с нулевым разглашением мы можем дополнительно разделить статистические параметры безопасности на с нулевым разглашением и надежностью статистические параметры безопасности . Первый параметризирует то, что сообщает стенограмма о секретных знаниях, а второй параметризирует вероятность, с которой нечестный доказывающий может убедить честного проверяющего, что он знает секрет, даже если он этого не знает.
В универсальной компонуемости безопасность протокола зависит от статистической неотличимости распределений реального и идеального исполнения. Интересно, что для вычислительно неограниченной среды недостаточно, чтобы распределения были статистически неразличимы, поскольку среда может запускать эксперимент достаточное количество раз, чтобы наблюдать, какое распределение создается (реальное или идеальное); однако любой отдельный противник протокола выиграет только с незначительной вероятностью по параметру статистической безопасности, поскольку он участвует в протоколе только один раз.

См. также