Threshold Cryptography

The idea of theshold cryptography is to protect information (or computation) by fault-tolerantly distributing among a cluster of cooperating computers. "Secret sharing" is an example of a threshold cryptography application, in which a valuable information is protected by being distibuted among a cluster of computers in such a way so that even if some threshold of these computers are faulty the others can still reconstruct it, and on other hand, the adversary trying to learn the information needs to break into some threshold of these computers to learn anything. Hence, secret sharing maintains both availability and secrecy of information against attacks by adversaries who can break into (disable, spy on, modify the information of, etc...) some threshold (say, up to a half) of the available computers.

Another interesting example of threshold security is "function sharing", i.e. protecting the availability and secrecy of a computer which performs some highly sensitive operation. A good example is a Network Certification Authority: a computer which (hopefully some day soon in the future) will sign public key credentials of every user on the internet. Instead of trusting a single computer to do this, it would be much more secure if we could fault-tolerantly distribute this operation among a cluster (say, five or seven) of computers, so that an adversary who somehow breaks in (spies on, disables, controlls, modifies, whatever!) to some threshold of these computers, still cannot either make proper signatures on his own, or stop the rest of the computers from creating proper signatures on our demand.

Recent research has discovered efficient protocols for fault-tolerant (or "robust") distribution of widely used signature functions.