2
$\begingroup$

How many non-trivial*, interesting perfect secrecy systems are there other than the one-time-pad? Does it seem that the one-time-pad and perfect secrecy are synonymous, but are there any other cryptosystems that have perfect secrecy aside from the trivial examples?

*Here the non-trivial means; the simple type that may be created by, say, picking a set of integers, and randomly corresponding each of those integers with a 0 or 1 (the key), then sending some permutation of the integers as cipher-text.

$\endgroup$
3
  • $\begingroup$ Shamir's secret sharing can be one example. Also, there are many information-theoretic secure cryptosystems that are close enough to perfect secrecy systems. $\endgroup$ May 14 '20 at 23:23
  • $\begingroup$ @kelalaka by non-trivial I mean the simple type that may be created by, say, picking a set of integers, and randomly corresponding each of those integers with a 0 or 1 (the key), then sending some permutation of the integers as cipher-text. $\endgroup$
    – GEG
    May 14 '20 at 23:43
  • $\begingroup$ Note that there are also cryptosystems that are not encryption schemes (and thus don't provide any secrecy in the usual sense) but which do provide perfect information-theoretical security against a suitable class of attacks. Notable examples include Shamir's secret sharing scheme and some MACs based on universal hashing (which can be perfectly secure in the sense that even an attacker with unlimited computing power has no way of forging a message with a higher probability than by guessing the MAC at random). $\endgroup$ May 16 '20 at 18:26
3
$\begingroup$

How many non-trivial*, interesting perfect secrecy systems are there other than the one-time-pad?

Infinitely many.

Let $\mathbb G$ be a group (written multiplicatively). Then

  • $\operatorname{KeyGen}(1^n)=k\stackrel{\$}{\gets}\mathbb G^n$, that is the key is a vector of $n$ independently random group elements.
  • $\operatorname{Enc}(k,m):\mathbb G^n\times \mathbb G^n\to\mathbb G^n:(k,m)\mapsto m\cdot k$, that is the plaintext is a vector of group elements and the ciphertext is simply the element-wise multiplication of each message element with the corresponding key element.
  • $\operatorname{Dec}(k,m):\mathbb G^n\times \mathbb G^n\to\mathbb G^n:(k,c)\mapsto c\cdot k^{-1}$, that is we simply combine each ciphertext element with the inverse of the corresponding key element.

Note that the above defines an encryption scheme for each group there is and that's at least countably infinitely many ones (as $(\mathbb Z_n,+)$ works for all $n\in\mathbb N$). In particular it also works for non-abelian (i.e. non-commutative) groups.

The above scheme can be proven secure under a similar argument to the traditional one-time-pad and in fact the traditional one is simply this with the group $(\mathbb Z_2,+)$.

$\endgroup$
5
  • $\begingroup$ Are any such systems secure under multiple key reuse, so the key space is so large that the same key can be used to encrypt multiple messages the length of the key? What about security under known plaintext attack? $\endgroup$
    – GEG
    May 15 '20 at 13:36
  • 1
    $\begingroup$ @GEG They have the exact same properties as the standard binary OTP. $\endgroup$
    – SEJPM
    May 15 '20 at 13:46
  • $\begingroup$ Arguably, though, all of these are just different kinds of "one-time pads". (In particular, I doubt any of the early one-time pad systems before the computer era used bitwise XOR. Most of them probably used addition modulo the ciphertext alphabet size instead. The choice of a two-symbol alphabet really only makes sense if you're using a binary computer.) $\endgroup$ May 16 '20 at 18:05
  • $\begingroup$ @IlmariKaronen I understand why this answer may feel unsatisfying. Perhaps you are instead looking for answers to the unasked questions of "what other known perfectly secret non-equivalent constructions exist besides the OTP?" or "Does the perfect secrecy requirement impose structural limitations on cryptosystems beyond the keylength?" $\endgroup$
    – SEJPM
    May 16 '20 at 18:26
  • $\begingroup$ Not really. I mean, that would be an interesting question, but that's not what was asked here. All I was trying to point out is that, depending on reasonable choices of terminology, the number of "perfect secrecy systems […] other than the one-time-pad" demonstrated in your answer could be either "infinitely many" or "none". And that the narrow definition of "one-time pad" that you (and possibly the OP) seem to have had in mind in fact excludes most of the historically used one-time pad systems before the modern era. $\endgroup$ May 16 '20 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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