Suppose Alice and Bob wish to set up a joint checking account: neither of them can access it alone, but together, they can withdraw money. One way to do this is to require a secret password, for instance 011 100 001 010, to use the account. Neither Alice nor Bob alone has this password. Instead, Alice has a string of random numbers 101 010 010 001, and Bob has the bitwise XOR of the key and Alice's bitstring:
| key | 011 100 001 010 |
|---|---|
| Alice | 101 010 010 001 |
| Bob | 110 110 011 011 |
Neither Alice nor Bob has any information about the key, but by putting their two codewords together, they can completely recover the key and access the bank account.
This is a simple example of a classical secret sharing scheme. The secret bank account password is shared between Alice and Bob. Much more elaborate secret sharing schemes exist. For instance, it is possible to share a secret among 3 people so that any two of them can reconstruct it, but any single person has no information about it. In fact, it is possible to share a secret among n people so that any k of them can reconstruct it, but any k-1 of them have no information about the secret, for any n and k. This is known as a (k, n) threshold scheme.
Classical secret sharing can be used in a number of ways besides for a joint checking account. The secret key could access a bank vault, or a computer account, or any of a variety of things. In addition, secret sharing is a necessary component for performing secure distributed computations among a number of people who do not completely trust each other.
With the boom in quantum computation, it seems possible, even likely, that quantum states will become nearly as important as classical data. It might therefore be useful to have some way of sharing secret quantum states as well as secret classical data. Such a quantum secret sharing scheme might be useful for sharing quantum keys, such as those used in quantum key distribution or in other quantum cryptographic protocols. In addition, quantum secret sharing might allow us to take advantage of the additional power of quantum computation in secure distributed computations.
Consider the following simple example, sharing a three-state quantum trit (a qutrit) among three people:
|0> -> |000> + |111> + |222>
|1> -> |012> + |120> + |201>
|2> -> |021> + |102> + |210>
No matter what the encoded state is, any single person is equally likely to find himself holding |0>, |1>, or |2>, so he has no information about the encoded state. On the other hand, any two people can easily reconstruct the secret. For instance, Alice and Bob, holding shares a and b, compute (b-a) mod 3. By doing this quantum mechanically, they can disentangle the phase as well, thus reconstructing the state, even if it is in a quantum superposition. This is thus an example of a ((2, 3)) quantum threshold scheme: any two people can reconstruct the secret, but one person alone has no information.
In fact, we can create a ((k, n)) quantum threshold scheme for any k and n, as long as n < 2k. The reason for this constraint is the No-Cloning Theorem, which states that it is impossible to copy a quantum state. If we had a ((k, 2k)) threshold scheme, we could use it to encode a state, take two sets of k shares, and use them to reconstruct two copies of the original state. Since we know this is impossible, no such scheme can exist.
Back to Daniel Gottesman's home page
January 12, 1999