Шифрование с закрытым ключом (симметричное)

Схема

$$x \longrightarrow S \longrightarrow R \longrightarrow x$$ $S$ и $R$ знают ключ $d$. На второй строчке есть еще $A$ (Ева), который пытается что-то узнать об $x$. Он ничего не должен узнать об $x$, а точнее он может узнать только то, что он мог бы узнать без входа.

Формальное определение

$d = D(1^n)$, $D$ - генератор ключей, вероятностный полиномиальный алгоритм.

$m = E(x, d)$ - алгоритм шифрования, вероятностный полиномиальный алгоритм.

$y = D(m, d)$ - алгоритм дешифрования, вероятностный полиномиальный алгоритм.

Условине корректности: $Pr\{D(E(x, d), d) = x\} \simeq 1$, где $\simeq$ означает стремление быстрее любого полинома.

Условие надежности: $E(x, d)$ и $E(x', d)$ вычислительно не отличимы.

Любая пара протоколов, для которых это верно будет называться схемой шифрования с закрытым ключом.

Гаммирование (one-time pad): $E(x, d) = x \oplus D$, $D(m, d) = m \oplus d$, $|d| = |x|$. Выполнение условий корректности и надежности проверяется лекго. Проблема в длине ключа. И в том, что схема одноразовая, ибо если зашифровать $x$ и $y$, то станет известна побитовая сумма $x$ и $x'$.

Гаммирование с генератором псевдо-случайных чисел: $E(x, d) = x \oplus G(d)$, $D(m, d) = m \oplus G(d)$. Здесь $|x| = poly(|d|)$. Но схема по-прежнему одноразовая. Чтобы сделать многоразовую схему можно вязть генератор отображающий $n$ бит в $20n$.

Недостаток шифрования с закрытым ключом: нужен закрытый канал, для передачи ключа.