2
$\begingroup$

The most known example cipher reaching perfect secrecy is One-time Pad, which employs modulus addition for encryption and decryption.

Is there any other well-known cipher no less practical than OTP that reachs perfect secrecy?

$\endgroup$
1
  • 2
    $\begingroup$ Hiya :-) Technically, modular maths isn't a requirement. The transformation has only to be bijective, which is how OTPs were implemented decades ago. $\endgroup$
    – Paul Uszak
    Sep 8 at 12:08

2 Answers 2

3
$\begingroup$

There is a famous result about perfect secrecy, usually called Shannon's theorem:

If an encryption scheme has perfect secrecy, then $|\mathcal{K}| \ge |\mathcal{M}|$, where $\mathcal{K}$ is the set of possible keys and $\mathcal{M}$ is the set of possible plaintexts.

One-time pad achieves equality $|\mathcal{K}| = |\mathcal{M}|$, which is the fewest number of keys possible according to Shannon's theorem. If you seek a scheme that is "no less practical" than OTP, then I suppose that you too require $|\mathcal{K}| = |\mathcal{M}|$.

OTP also has a deterministic encryption algorithm, so any scheme that is "no less practical" should also have deterministic encryption. (Also, randomized encryption would needlessly increase the ciphertext size.)

With a deterministic encryption scheme, we can imagine writing out the entire truth table of $\textsf{Enc}(K,M)$, with rows indexed by $K \in \mathcal K$ and columns indexed by $M = \mathcal M$. As $|\mathcal M|=|\mathcal K|$, the table is a square. For decryption to be possible, every row must have distinct entries -- this corresponds to the property that $\textsf{Enc}(K,\cdot)$ is a bijection for every $K$. Every column must also have distinct entries: if the column corresponding to $M$ does not have distinct entries, then it is missing some $C$, meaning that no key encrypts $M$ to $C$. But then observing the ciphertext $C$ means the plaintext could not have been $M$, and this violates perfect secrecy. (We know $C$ appears somewhere in the table as encryption of some plaintext, otherwise the condition on rows doesn't hold.)

The truth table of $\textsf{Enc}$ is therefore a Latin square, making it the truth table of a quasigroup operation. Let's call the quasigroup $(\mathcal G, \boxplus)$. Then $\mathcal M$ and $\mathcal K$ are both isomorphic to $\mathcal G$ and the encryption algorithm is $\textsf{Enc}(K,M) = K \boxplus M$.

So the question of alternative perfectly secret encryption schemes reduces to the question of identifying a suitable quasigroup.

$\endgroup$
0
1
$\begingroup$

There's computational perfect secrecy and information-theoretic perfect secrecy, and OTP belongs to the latter.

If it's well-known information-theoretic perfect secrecy that you seek and is no less practical, then none.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.