Information Theoretic Security (ITS) is a cryptographic standard that guarantees security based on the laws of mathematics and information theory, regardless of the computational power or time available to the adversary. 

ITS secrecy systems are also called unconditionally secure or provably secure systems and at Incrypteon we believe they are the minimum cryptography standard we should accept to enable No Compromise Cryptography.

Claude Shannon established the foundations of information theory and cryptography in his seminal paper “Communication Theory of Secrecy Systems” in 1949. Shannon defined three important concepts for ITS cryptography: Perfect Secrecy, Ideal Secrecy and Equivocation.

Secrecy Levels

Perfect Secrecy

Perfect secrecy is a notion of security that requires that the ciphertext reveals no information about the plaintext, even if the adversary has unlimited computational resources and knows the encryption algorithm. Shannon proved that perfect secrecy can be achieved if and only if the following three conditions are met:

• The key is as long as the message.
• The key is chosen uniformly at random from a large enough key space.
• The key is used only once and never reused.

Includes deterministic secrecy systems with keys which are at least as long as the message, the most basic of which is the One-Time pad. It has a unicity point which tends to infinity. Proven to be unbreakable.

Ideal Secrecy

Ideal Secrecy extends beyond the security characteristics of a Perfect Secrecy system.  This includes probabilistic secrecy systems where keys are at least as long as the message. Ideal secrecy systems also have a unicity point which tends to infinity. Since keys are longer, also proven to be breakable.

Incrypteon is the only solution that delivers both Perfect Secrecy & Ideal Secrecy.

Equivocation and Unicity Distance

The Unicity Distance or Equivocation indicates the point along the Ciphertext where the system no longer has any secrecy.  Note that a certain amount of key entropy can only secure a certain of a plaintext message.  This is the objective measurement for security proposed by Shannon.

Entropy is a measure of the uncertainty or randomness of a system. In cryptography, entropy is used to quantify the unpredictability of secret keys or messages, which is essential for achieving security. The higher the entropy, the harder it is for an adversary to guess or deduce the secrets.  Entropy can be expressed in bits, which indicate the number of binary choices needed to generate a random value.

Entropy augmentation is a technique for enhancing the security of cryptographic protocols by increasing the randomness or unpredictability of the secret keys or messages. Entropy augmentation can be achieved by various methods, such as adding noise, mixing sources, hashing, or extracting randomness from physical phenomena. Entropy augmentation can improve the resistance of cryptographic schemes to brute-force attacks, side-channel attacks, or quantum attacks.

One way to measure the effectiveness of entropy augmentation is to use the notion of information-theoretic security, which means that the security of a protocol does not depend on the computational power of the adversary, but only on the mathematical properties of the information involved.

Information-theoretic security is stronger than computational security, which assumes that the adversary has unbounded resources and cannot break certain hard problems. A protocol is information-theoretically secure if the adversary cannot gain any information about the secret key or message, even with unlimited computing power and time.

Ordinarily, the strength of a cryptosystem may be directly proportional to the length of the initial key, but this assumption is subject to the condition that the ciphertext is shorter than a value that Claude Shannon called the “unicity distance”.

Before proceeding with the paper, the reader should be aware of the following information:

• Deterministic vs. Probabilistic cipher design. Deterministic ciphers have predictable operations / solutions, such as the product of two primes. (21=3×7) Given 21, only 3 and 7 are viable options. Probabilistic ciphers adopt an unpredictable operations / solutions, such as 24 = 2×12, 3×8, 6×4 etc. with random elements that vary each time they run.
• There are 2 general levels for “true secrecy systems” when it comes to cipher design. Whilst the true distinction is based on something called the “unicity point” (calculated by adding the key length to the unique information in the message) in cryptography, a simpler explanation is provided below.

1. 1. Perfect Secrecy (Unbreakable) – Under a brute force attack, all possible messages will appear as valid decipherments, the One-Time pad is an example of such a system. Proven to be unbreakable, therefore Quantum secure.
   2. Ideal Secrecy (Unbreakable) – Under a brute force attack, a subset of all possible messages will appear as valid decipherments.  This includes secrecy systems where messages are slightly longer than the keys. Proven to be unbreakable, therefore Quantum secure.

There are also practical systems, that have no secrecy, but are commonly used:

1. 1. Semantic Secrecy (Breakable by Brute Force) – Includes systems with keys shorter than messages and systems that depend on mathematical complexity for their security. Examples include almost all currently used ciphers – AES, DES, RSA, ECC, Kyber, Dilithium etc. It has a fixed unicity point. Proven to be breakable. They are deemed to be Quantum Safe, but not Quantum Secure.

Archaois from Incrypteon uses a patented solution whereby the security of the system can be set to desired secrecy levels.  We use a novel technique called entropy augmentation to extend the length of the Unicity distance to be longer than the message by combining multiple weak sources of randomness, or to extract high-quality randomness from noisy or biased sources.

Incrypteon is the only solution that enables Perfect and Ideal Secrecy for both symmetric and asymmetric encryption

Understanding Conditional Entropy Graphs

Shannon demonstrated that all secrecy systems can be analysed in terms of Equivocation (his term for conditional entropy).

Equivocation is a measure of the security of a secrecy system. It is the size of an expected / verified search result expressed as a logarithm. Search a pack of cards for queens, you will find 4, so Equivocation is 2, the logarithm of 4 (2^2). With 2 packs, 8 results, Equivocation is 3.

The thing about Equivocation, is that it can be plotted. Hence the “graphy” in cryptography.

Below is an equivocation graph for a pure cipher (basically the same message with a different key, will produce a different ciphertext).  The graph is for a 32-bit key, and 8 message characters (2 groups of 8-bit characters). problem.

To explain the graph above:

• It is a logarithmic graph of conditional entropy and allows simple linear analysis that allow for Unicity Points to be plotted.
• Key entropy H(K) is shown on the left axis – 32 bits of entropy.
• Message entropy H(M) is shown at the bottom. 8 Message characters M[0] to M[8] are shown on the bottom axis. The first 4 characters (UTF-8) use 32 bits of entropy.
• There are 4 solid lines projected from point 101. These show Key Equivocation (remaining keys – untested or valid due to a valid decryption) for 4 message types, under a key brute force attack. There are 4 striped lines from point 102. These indicate Message Equivocation (set of valid messages). As we test every key, Key Equivocation drops. With every valid message, Message Equivocation increases.
• The 4 message types are:
  • Known Message (M0) – With a known plaintext, 1 message is valid, so Message Equivocation remains 0 entropy (2^0 = 1 message) and the result is point 107. At 107, only 1 valid key remains – it is related to the valid message, and Key Equivocation is 0. WARNING – Standard documents, web pages and commands are known messages.
  • Normal Message (M1) – With a normal plaintext, although there is an alphabet, not all letter combinations will make sense. Letter combinations which are valid is information, bad letter combinations are called redundancy. Redundancy is what a brute force attack uses to eliminate keys – a key which leads to a nonsense decryption is eliminated. So, the security of a system is dependent on 2 things – key entropy and redundancy. For standard English, on average there are 1.3 bits of entropy in each character in a 20-character string. So, at point 105, because we are only using 4 characters, it will be about 2.0 – 8 bits = 256 possible valid 4 letter combinations. Point 105 – is the Perfect Secrecy point, where all possible messages (and associated keys) occur. The more redundancy in a message, the lower the Perfect Secrecy Point will be, the less redundancy, the higher – at 8 bits of message entropy, redundancy is about 75%.
    1. When the key is repeated, Key Entropy will keep its trajectory and hit point 106 (the Unicity Point) where Equivocation on key and message will be zero and a single viable decryption will result. Any message longer than this point in characters is guaranteed to be broken. Any message shorter than this point will still be unbreakable as it will produce more than 2 valid decryptions (Ideal Secrecy). Hence the Security Guarantee Zone. Beyond that is the Insecurity Guarantee Zone. This tells you how much ciphertext you need to brute-force a deterministic encryption algorithm. With AES-256, you generally need about 40 characters, but they send it in 32-character blocks, so you will get two blocks.
    2. WARNING – Using a standard code page like UTF-8 introduces an enormous amount of redundancy. If we think that the English language alphabet has about 80 useable characters, using a standard 256-bit code page adds about 176 redundant characters.
  • 50% Redundancy Message (M2) – With various techniques, it is possible reduce redundancy to 50% – for example by using ASCII with 128 characters. Point 108 shows the plot for a message with 50% redundancy. Reducing the redundancy in messages moves the Ideal Secrecy point out. At 50% redundancy, the attacker will need ciphertext which is at least twice as long as the key to get a valid brute force result.
    1. WARNING – Whilst file compression reduces redundancy massively, it leaves a standard document format at the beginning, and this is usually longer than 32 characters.
  • Random Message (M3) – The opposite of a known plaintext. Random strings have no redundancy – all characters are possible; all keys are valid. Point 110 shows the equivocation plot. In our example, note that beyond Point 110, you may reuse the key for characters M[4] to M[7], but there will always only be 2^32 message variations, and there will be a relationship between M[0] and M[4].

It is possible to look at impacts on equivocation when different message types are combined. The green lines represent the key equivocation when 2 characters of normal message (about 66% redundancy) are combined with 2 characters of random message.

A GAME – BASIC CRYPTO DYNAMICS FOR INFORMATION THEORETIC SECURITY

DISCLAIMER: The information provided in this series of blogs is patented and in the public record.

Whoever said that “unbreakable encryption” is impossible, hasn’t read Shannon’s papers. Using the principles in Shannon’s papers, I’m going to take you step-by-step through one of the winning strategies of how to play the game of “Unbreakable Encryption” against an AI and / or Quantum machine. This blog assumes an understanding of Shannon’s papers.  

We will explain the principles in laymen’s terms as we proceed through various examples.

To compare the abilities of (1) One Time Pad, (2) Quantum Key Distribution, (3) Existing (In)secure Encryption Protocols and (4) Archaios, we are going to use a simple game.

THE RULES OF THE GAME – To keep things simple,

• You MUST Win – Save mankind by encrypting and sending the message and do not disclose the key. If the AI can deduce a single key to decrypt the message, then the Unicity Point equals zero AND the game ends.
  • There are 2 levels of difficulty
    • Easy – Level 1 – key as long as message
    • Impossible – Level 2 – key is ½ the length of the message.
  • No Assumptions Allowed – You are not allowed ANY assumptions.
  • Attacker Allowed All Assumptions – Your AI/QC (Artificial Intelligence/Quantum Computing) opponent has infinite time and computing resources. If you cannot prove that something is impossible, he can use that as an assumption. Since we have no proof, we will assume that the AI can solve ANY time-based complexity problem, or any deterministic problem within a second.
  • The Code Page – you are limited to using the standard UTF-8 code page (256 characters).
  • The Plaintext Message – You MUST send the 16-character (128 bit) command code message string “AI_QC /STOP /NOW” to terminate the AI.

UTF-8 hex and 8bit values for “AI_QC /STOP /NOW” is shown below.