Information-theoretic security [closed]

Question

From Wikipedia:

Information-theoretic security is a cryptosystem whose security derives purely from information theory. In other words, it cannot be broken even if the adversary had unlimited computing power. The adversary simply does not have enough information to break the encryption and so the cryptosystems are considered cryptanalytically-unbreakable.

List of unbreakable encryption-methods:

• Secret sharing
• Private information retrieval with multiple databases
• Reduction between cryptographic primitives or tasks
• Symmetric encryption with high entropic security

• Quantum Cryptography

  • Why quantum cryptography isn't commercially used:

    GCN Article: “There are limitations to QKD (= Quantum key distribution),” Hayford said. Photons can only be sent about 60 miles, and it is a point-to-point protocol, meaning that complete system hardware is needed at each location. Expanding a system beyond a campus or a small number of local facilities “starts to be a little impractical.” And: "There also are challenges with existing hardware, particularly in the generation and measurement of individual photons. “That is a complicated physics problem,” which NIST and other research facilities have been working on for years, he said. Ideally the photon source would generate a single photon on demand. “We can’t do that right now.”

    The problem for a broad execution of QKD is, that the two parties have to know each other before communicating. And there needs to be a physical established line of communication, either from point to point or in nodes.

• One-time pad

• Pedersen commitments against the opener
• ElGamal encryption used as commitment, against the committer

My questions are:

1. Are there more known unbreakable encryptions? If so, please provide a link & I will extend the list.

2. Why aren't these schemes commercially used? Please provide an explanation (and link if possible) and I will edit the list as well.

Answer 1

Information-theoretic security is a cryptosystem

Nitpick: information-theoretic security is a property that a cryptosystem can have against a particular attack model. AES is a cryptosystem, but doesn't have this property against any of the usual models; the one-time pad is a cryptosystem that does against passive attackers (but not active ones).

Other systems that have information-theoretic security, off the top of my head:

• The one-time pad, against passive attackers.
• Pedersen commitments, against the opener (but not against the committer).
• ElGamal encryption used as a commitment, against the committer (but not the opener).
• A bunch of OT systems of the Chu-Tzeng style, against either the sender or the recevier (against both at once is impossible - same goes for commitments).

Some of the above schemes are very much commercially used.

QKD is a very specific form of quantum cryptography, the two terms are not equivalent.

Answer 2

The reason information-theoretically secure cryptography is hardly used is its inefficiency. For example, if you want information theoretically secure secret key encryption, the key has to be as long as the message you want to encrypt. Moreover, you cannot build information-theoretically secure versions of some key primitives in cryptography, e.g., (asymmetric / public-key based) key exchange. If you already have complexity-theoretic security in your system for some security property (say secrecy), e.g. because you have to use an asymmetric key exchange, there is no real reason to use a information-theoretically secure encryption with the shared key as the weakest link is what the attacker will focus on.

To avoid confusion: QKD is called key distribution as it achieves something fundamentally different from key exchange. In key exchange, the user just needs the public key of a party they want to communicate with and can use this to establish a commonly known secret key. In QKD, both participating parties need a) the physical devices, b) a connection between those that allows to run QKD (nowadays this would be a dedicated wire), and c) still some authentication method which either requires a shared secret or some complexity-theoretically secure signature scheme.

For short: In QKD the two parties have to know each other before communicating and have to prepare a lot. In that case it might be cheaper to just send a guard with a hard drive full of key material or to put guards every km along the wire one wants to protect ;-)

Answer 3

Mephisto's answer was well put. To add to it here's a link to Shannon's Paper from 1949 where he proved that for Perfect secrecy against a computationally unbounded adversary, one would need a key as long as the message(Essentially a one-time pad). Assuming an adversary has a finite amount of time on his hands, opens the door to things like Public Key Cryptography.