Семантическая стойкость

Семантически стойкой криптосистемой в криптографии называется криптосистема, которая не допускает никакой утечки из шифротекста значимой информации об исходном открытом тексте. Возьмем любой вероятностный алгоритм класса PP, на вход которого в первом случае подаются шифротекст некоторого случайного сообщения $m$ и длина этого сообщения, а во втором случае — только длина сообщения. Если разница между вероятностями получения некоторой достоверной информации об исходном сообщении в первом и во втором случаях пренебрежимо мала, то криптосистема, которой произведено данное шифрование, считается семантически стойкой. С точки зрения вычислительной сложности, это понятие аналогично абсолютно стойкому шифру Шеннона. Абсолютно стойкий шифр предполагает невозможность получения какой-либо информации об исходном сообщении в принципе, в то время как семантическая стойкость подразумевает, что никакая информация об исходном сообщении, обнаруженная в шифротексте, не может быть использована для дешифрования какого-либо фрагмента сообщения.

История

Понятие семантической стойкости было введено в криптографию Гольдвассер и Микали в 1982 году. Однако определение, которое они изначально предложили, не давало оценки стойкости реальных криптосистем. Позже Гольдвассер и Микали показали, что семантическая стойкость эквивалентна неразличимости шифротекста для атак на основе подобранного открытого текста. Данное определение семантической стойкости более распространено, так как оно помогает дать оценку стойкости используемых криптосистем.

Симметричная криптография

В случае с симметричными криптосистемами противник не должен иметь возможности узнать какую-либо информацию об открытом тексте из шифротекста. Это значит, что противник, имея два открытых текста и два соответствующих им шифротекста, не может точно определить, какой шифротекст соответствует какому открытому тексту.

Криптография с открытым ключом

Криптосистема с открытым ключом считается семантически стойкой, если противник, обладая шифротекстом и открытым ключом, не может получить какую-либо значимую информацию об исходном открытом тексте. Семантическая стойкость рассматривает только случаи пассивных криптоатак, например, когда криптоаналитик может только наблюдать передаваемые шифротексты и генерировать собственные шифротексты, используя открытый ключ. В отличие от других понятий стойкости, семантическая стойкость не рассматривает атак на основе подобранного шифротекста, где криптоаналитик способен дешифровать некоторые выбранные шифротексты, и многие семантически стойкие схемы шифрования оказываются нестойкими к атакам подобного типа. Поэтому семантическая стойкость не может считаться достаточным условием стойкости схемы шифрования общего назначения.

Неразличимость шифротекста для атак на основе подобранного открытого текста обычно определяется следующим экспериментом:

1. Генерируется случайная пара ключей $(pk,sk)$.
2. Противник, полиномиально ограниченный во времени, получает открытый ключ $pk$, который он может использовать для генерации любого числа шифротекстов (в пределах полиномиальных границ по времени).
3. Противник генерирует два сообщения $m_{0}$ и $m_{1}$ одинаковой длины и передает их отправителю вместе с открытым ключом.
4. Отправитель выбирает одно из сообщений случайным образом, шифрует его с помощью полученного открытого ключа и отправляет получившийся шифротекст $c$ противнику.

Рассматриваемая криптосистема обладает свойством неразличимости шифротекста (и, таким образом, является семантически стойкой для атак на основе подобранного открытого текста), если противник не может определить, какое из двух сообщений было выбрано отправителем, с вероятностью, значительно большей, чем $1/2$ (вероятность случайного угадывания).

Поскольку противник обладает открытым ключом, семантически стойкая схема по определению должна быть вероятностной, то есть обладать случайной составляющей. В противном случае противник может, используя открытый ключ $pk$, элементарно посчитать шифротексты сообщений $m_{0}$ и $m_{1}$, сравнить их с возвращенным шифротекстом $c$ и успешно определить выбор отправителя.

Примерами семантически стойких алгоритмов являются криптосистема Гольдвассер — Микали, схема Эль-Гамаля и криптосистема Пэйе. Эти схемы считаются доказуемо стойкими, так как в каждом случае доказательство семантической стойкости может быть сведено к труднорешаемой математической проблеме. Семантически нестойкие алгоритмы, вроде RSA, можно сделать семантически стойкими, используя схемы дополнения (например, OAEP).