0
$\begingroup$

As far as I know OTP is the only algorithm proven to provide perfect secrecy. It can work with XOR which is addition modulo 2 and obviously it can work with additions modulo N. What other operations enable perfect secrecy? Can we for example have randomized tables to define the mixing of data and key and still prove the perfect secrecy property of OTP?

$\endgroup$
3
  • $\begingroup$ Shamir's secret sharing scheme, and other such schemes where the key material is at least as large as the message. $\endgroup$ – Natanael Nov 14 '19 at 22:53
  • $\begingroup$ Also not sure about the modulo stuff. OTP encryption does not require XOR operators. That's just down to lazy programmers. $\endgroup$ – Paul Uszak Nov 14 '19 at 22:56
  • 1
    $\begingroup$ you can multiply bits of pad with bits of message in a finite field $\endgroup$ – Richie Frame Nov 15 '19 at 0:36
2
$\begingroup$

As far as I know OTP is the only algorithm proven to provide perfect secrecy.

Naah, there are others. For example, you can do Shamir secret sharing, have the key be one of the shares, and broadcast the other $N-1$ shares. That also has perfect secrecy - it also doesn't have any specific advantages over OTP, so we never consider bothering.

What other operations enable perfect secrecy.

Actually, you can use an Latin square operation, if you were so minded.

Can we for example have randomized tables to define the mixing of data and key and still prove the perfect secrecy property of OTP?

Well, you could generate a random Latin square, and it'd work.

However, might I ask why you're thinking of doing this? What advantage are you looking to achieve?

$\endgroup$
1
  • $\begingroup$ Not doing it, just had an argument over this and started wondering. My Google Fu wasn't strong enough to find the answer myself. Reading about Shamir's Secret Sharing it seems like you can't pass the key and encrypt the data later so it is a bit different in application from OTP. Is this correct? $\endgroup$ – Stilgar Nov 14 '19 at 23:25
3
$\begingroup$

Any group operation works for a one-time-pad if you can shoehorn a message uniquely into a group element—addition modulo $n$, multiplication modulo $n$ if you can uniquely encode a message block as an integer coprime with $n$, addition or multiplication in finite extension fields, invertible matrix multiplication over finite fields, whatever group you want—and can be extended by a direct product to arbitrary-length messages: if you have a group operation $m \oplus k$, then you can extend it to an $\ell$-block message $(m_1, m_2, \dotsc, m_\ell)$ with an $\ell$-block key $(k_1, k_2, \dotsc, k_\ell)$ by $(m_1 \oplus k_1, \dotsc, m_\ell \oplus k_\ell)$. Conventionally we talk about addition modulo 26 in English, or use addition modulo 2 for computers, of course.

Going beyond the one-time pad approach, to encrypt a $t$-bit message, you could choose a permutation $\pi$ uniformly at random from all $2^t!$ possibilities; then the one-time cipher $m \mapsto \pi(m)$ has ‘perfect secrecy’ too. Of course, it's tremendously inefficient even compared to a one-time pad! (Bonus: You could get built-in authentication with forgery probability bounded by $2^{-f}$ by using $m \mapsto \pi(m \mathbin\| 0^f)$. Of course, still much cheaper to compose a one-time pad and one-time authenticator…)

$\endgroup$

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.