A cryptosystem

Cryptosystem

There are two different meanings of the word cryptosystem. One is used by the cryptographic community, while the other is the meaning understood by the public.- General meaning :...

 is information-theoretically secure if its security derives purely from information theory

Information theory

Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...

. That is, it is secure even when the adversary has unlimited computing power. The adversary simply does not have enough information

Information theory

Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...

 to break the security. An algorithm or encryption protocol that has information-theoretic security does not depend for its effectiveness on unproven assumptions about computational hardness and such an algorithm is not vulnerable to future developments in quantum computing

Quantum computer

A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...

. An example of an information-theoretically secure cryptosystem is the one-time pad

One-time pad

In cryptography, the one-time pad is a type of encryption, which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key of the same length as the plaintext, resulting...

.

An interesting special case is perfect security: an encryption algorithm is perfectly secure if a ciphertext

Ciphertext

In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...

 produced using it provides no information about the plaintext

Plaintext

In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....

 without knowledge of the key

Key (cryptography)

In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...

. If E is a perfectly secure encryption function, for any fixed message m there must exist for each ciphertext c at least one key such that . There is also a weaker notion of security defined by A. Wyner and followed by many people in the area of information theory recently.

It is common for a cryptosystem to leak some information but nevertheless maintain its security properties even against an adversary that has unlimited computational resources. Such a cryptosystem would have information theoretic but not perfect security. The exact definition of security would depend on the cryptosystem in question.

There are a variety of cryptographic tasks for which information-theoretic security is a meaningful and useful requirement. A few of these are:

1. Secret sharing
   Secret sharing
   Secret sharing refers to method for distributing a secret amongst a group of participants, each of whom is allocated a share of the secret. The secret can be reconstructed only when a sufficient number of shares are combined together; individual shares are of no use on their own.More formally, in a...
   
    schemes such as Shamir's
   Shamir's Secret Sharing
   Shamir's Secret Sharing is an algorithm in cryptography. It is a form of secret sharing, where a secret is divided into parts, giving each participant its own unique part, where some of the parts or all of them are needed in order to reconstruct the secret....
   
    are information-theoretically secure (and also perfectly secure) in that less than the requisite number of shares of the secret
   Secrecy
   Secrecy is the practice of hiding information from certain individuals or groups, perhaps while sharing it with other individuals...
   
    provide no information about the secret.
2. More generally, secure multiparty computation
   Secure multiparty computation
   Secure multi-party computation is a sub field of cryptography. The goal of methods for secure multi-party computation is to enable parties to jointly compute a function over their inputs, while at the same time keeping these inputs private...
   
    protocols often, but not always have information theoretic security.
3. Private information retrieval
   Private information retrieval
   In cryptography, a private information retrieval protocol allows a user to retrieve an item from a server in possession of a database without revealing which item they are retrieving...
   
    with multiple databases can be achieved with information-theoretic privacy for the user's query.
4. Reductions
   Reduction (complexity)
   In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. Depending on the transformation used this can be used to define complexity classes on a set of problems....
   
    between cryptographic primitives or tasks can often be achieved information-theoretically. Such reductions are important from a theoretical perspective, because they establish that primitive can be realized if primitive can be realized.
5. Symmetric encryption can be constructed under an information-theoretic notion of security called entropic security
   Entropic security
   Entropic security is a security definition used in the field of cryptography. Modern encryption schemes are generally required to protect communications even when the attacker has substantial information about the messages being encrypted...
   
   , which assumes that the adversary knows almost nothing about the message being sent. The goal here is to hide all functions of the plaintext rather than all information about it.
6. Quantum cryptography
   Quantum cryptography
   Quantum key distribution uses quantum mechanics to guarantee secure communication. It enables two parties to produce a shared random secret key known only to them, which can then be used to encrypt and decrypt messages...
   
    is largely part of information-theoretic cryptography.

Unconditional security

Information-theoretic security is often used interchangeably with unconditional security. However the latter term can also refer to systems that don't rely on unproven computational hardness assumptions. Today these systems are essentially the same as those that are information-theoretically secure. However it does not always have to be that way. One day RSA might be proved secure, thus becoming unconditionally secure, but it will never be information-theoretically secure.