2
$\begingroup$

Let's say you want to break down a message, for simplicity it is just a bit $0$ or $1$, $m$ into two messages $(m_1, m_2)$ as follows:

If $m =0$, then $(m_1, m_2) = (0, 0)$ with probability $1/2$ and $(m_1, m_2) = (1,1)$ with probability $1/2$. Similarly, if $m=1$, then $(m_1, m_2) = (0,1)$ or $(1,0)$ each with probability $1/2$.

It's clear how the message can be retrieved from the two messages, and that nothing can be know from a single daughter message (each will be 0 or 1 with equal probability regardless of the mother message), unless the random number generator has a bias of sorts.

What is this system called?

(I don't do cryptography by trade, don't know which tags to use.)

$\endgroup$
  • $\begingroup$ I'm not fully sure what you mean. Maybe it's the One-Time-Pad or a stream cipher. $\endgroup$ – SEJPM Aug 19 '15 at 14:02
  • $\begingroup$ It looks to me to be a simple case of secret sharing, rather than encryption. $\endgroup$ – Bristol Aug 19 '15 at 14:45
5
$\begingroup$

You could view it as a form of One-Time-Pad encryption. In this view one of the two "messages" is the key and the other is the ciphertext (it does not matter which you think of as which as their roles are symmetric).

It may, however, be more natural to think of as a simple secret sharing scheme. Roughly speaking a secret sharing scheme is a scheme where a secret is divided into a number of shares. Usually you then need more than some specified number of shares to reconstruct the secret, and any lower number of shares will give no information on the secret.

For your scheme $m$ is then the secret, $m_1$ and $m_2$ are the shares and you need both shares to reconstruct the secret.

The scheme you describe is a well known and much used one, sometimes referred to as "XOR" sharing. This because you can define the shares as picking random bits $m_1, m_2$ under the restriction that $m = m_1 \oplus m_2$.

$\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.