Secret Splitting
Introduction

Task

Data Dictionary

Teacher's Tools

Bit Commitment

Blinding

Digital Signatures

Certificates

Key Distribution

Secret Splitting

Security Basics

Symmetric Key



 A recipe consists of different ingredients.  If the ingredients are passed to different people, the only method of making the recipe is for the different people to get together and put the ingredients together.  Splitting the ingredients between people provides a level of security because there is not a single individual that knows how to make the recipe.   No-one can compromise the recipe on their own.

There are methods in digital communication to split a message up so that each individual piece is worthless, but putting all the pieces together can reveal the message.  This task is accomplished by secret splitting. 

Secret splitting relies on a mathematical function called an XOR.  An XOR is an exclusive-or operation.  The mathematical symbol for an XOR is .  The standard operations that it provides on bits is:

00 = 0

01 = 1

10 = 1

11 = 0

The XOR is used for secret splitting because of the following mathematical property.  Consider two variables that are XORed together to form a third variable:

AB = C

The value of A can be recovered from the following mathematical operation:

CB=A

XORing the same value twice restores the original value!  Therefore, messages can be split by using an XOR function with a random string.   If one receiver gets the random string (B) and the other receiver gets the output of the XOR function (C), then both receivers will need to combine their pieces to get the original message (A).

Consider the following protocol:

  1. The sender generates a random string that is the exact length of the message it wishes to send.
  2. The sender XOR's the message with the random string to generate a new string.
  3. The sender sends the random string to one receiver.
  4. The sender sends the new string generated in step 2 to another receiver.

The only method of reconstructing the message is for both receivers to XOR their strings together to reform the message.

If a message needs to be split between more than two people, then more random strings are needed.  Generally it will take N-1 strings to split a message between N people.

A simple example of secret splitting can be done by taking a very simple message.  Let us assume that we want to split the message "1010" between two people.  The following steps can be used:

  1. The sender generates a random string that is four bits long.  The random string is 1100.
  2. The sender XOR's the message with the random string.  The XOR of 1010 with 1100 is 0110.
  3. The sender sends the random string, 1100, to one receiver.
  4. The sender sends the new string, 0110, to another receiver.

The method of reconstructing the message is for one receiver to supply 1100 and the other receiver to supply 0110.  The resulting XOR is the original message, 1010.