# If a probabilistic encryption algorithm is used, how does decryption return the correct message?

Given a key $k$ and a plaintext $p$, a deterministic encryption algorithm will return a ciphertext $c_1$. In a second trial, I run the same key and plaintext $p$ through the encryption algorithm and get ciphertext $c_2$ from the first trial. $c_1$ and $c_2$ are equivalent, so running the decryption algorithm on $c_1$ and $c_2$ both return $p$.

However, if a probabilistic encryption is used instead to encrypt $p$, the algorithm will run twice and return two different ciphertexts $c_1$ and $c_2$.

How does $Dec(c_1) = p$ and $Dec(c_2) = p$?? If $c_1$ and $c_2$ are different, should decryption return different results?

• What if I append a random string to a message before each encryption and ignore it upon decryption? Commented May 9, 2018 at 13:53
• You assume that decryption is injective. There is no reason to assume that. Commented May 9, 2018 at 14:01

In a probabilistic encryption scheme, for every plaintext there is more than one possible ciphertext.

Here's an example—with lots of details not related to your question omitted, so don't take these scissors and try running with this at home!

The recipient knows the secret ~256-bit number $r$ of times that a base point $B$ must be added to itself to yield a public point $R = B + B + \cdots + B = [r]B$ on some standard elliptic curve, say Curve25519. (There's a shortcut to computing $[r]B$ so you only have to do a few thousand arithmetic operations and not a mindbogglingly unimaginable number.)

To conceal a message $m$ using the public point $R$, the sender:

1. picks a secret ~256-bit number $s$ uniformly at random;
2. adds $B$ to itself $s$ times to obtain $S = [s]B$;
3. adds $R$ to itself $s$ times to obtain $[s]R$;
4. computes $k = H([s]R)$, a secret key;
5. computes $c = \operatorname{crypto\_secretbox\_xsalsa20poly1305}(k, 0, m)$, the authenticated ciphertext under the symmetric key $k$ and nonce 0; and
6. transmits $(S, c)$ to the recipient.

The recipient, on receipt of $(S, c)$, then:

1. computes $[r]S = [r\cdot s]B = [s\cdot r]B = [s]R$;
2. computes $k = H([r]S) = H([s]R)$, the same secret key as the sender derived;
3. computes $m = \operatorname{crypto\_secretbox\_xsalsa20poly1305\_open}(k, 0, c)$, or rejects if forged.

There are roughly $2^{256}$ possible sender secrets $s$ that could be used to encrypt the message, and they all work for any message $m$, so in this cryptosystem, for any message $m$ there are about $2^{256}$ distinct ciphertexts that have $m$ as the corresponding plaintext.

This is not simply an artificial example. To meet the standard notion of security for public-key encryption, indistinguishability under adaptive chosen-ciphertext attack, there must be many ciphertexts for any given plaintext, randomly chosen by the sender. Otherwise, an adversary without knowledge of the private decryption key can easily tell whether a challenge ciphertext conceals one of two (or three, or $n$) possible plaintexts by encrypting the candidate plaintexts and comparing the resulting ciphertexts to the challenge. This implies that the minimum number of distinct ciphertexts for each plaintext must be around $2^{192}$ to give confidence in security against multi-target attacks.

There are also probabilistic symmetric ciphers, like AES-CBC with randomly chosen IVs affixed to the ciphertext, or crypto_secretbox_xsalsa20poly1305 with randomly chosen nonces affixed to the ciphertext. In this case, the randomization serves to prevent the same message content at different times from leading to the same ciphertext and enabling an adversary to recognize repeated messages.

Randomization per se is not always necessary in the symmetric setting: it is sufficient to deterministically keep state for crypto_secretbox_xsalsa20poly1305 and transmit each successive message with a count of the number of messages sent so far, for instance. But in some cases like AES-CBC it is obligatory—though of course you could use a secret pseudorandom function of the message sequence number, such as $\operatorname{AES}_k(\mathit{seqno})$, to choose the AES-CBC IV.

Because probabilistic encryption produces ciphertexts that are longer than the plaintext, and this additional length contains information that allows for deterministic recovery of the plaintext. Your argument has the form of a reductio, but you haven't spotted that the assumption you're actually refuting is that the ciphertext is the same length as the plaintext.

Note that one detail here that's easy to get confused over is the precise scope of the terms ciphertext and initial value ("IV"). Often these are treated as separate strings, but definitions of probabilistic encryption "hide" the IV generation and transmission as an internal detail of the encryption algorithm and ciphertexts. For example, when you formulate it as probabilistic encryption terms, CBC mode:

1. Doesn't take an IV as an argument, rather it internally generates an random IV;
2. Doesn't return a ciphertext equal in length to the padded plaintext, but one additional block longer, such that the first block is the IV.

So under these definitions, CBC can be modeled as probabilistic encryption because:

1. The encryption operation chooses a random IV that gets incorporated as a prefix into the ciphertext and on which the rest of the ciphertext depends;
2. Decryption can recover the original plaintext because the ciphertext encompasses the random IV that's required to reconstruct the random choices made in the invocation of the encryption operation.

The probabilistic encryption concept and its application to asymmetric encryption was published in 1984 and entailed the inclusion of a random variable which was attached to the ciphertext. However, the concept was known before that.

There are various "modes" of probabilistic symmetric encryption, and the one I want to show you, forms the basis for a new multidimensional information theoretically secure encryption algorithm.

You will require 2 RNGs

• RNG#1 is used to generate random entropy - It produces a string E.
• RNG#2 is used to generate various keys for each encryption operation or cycle. Note that the "key" is used to initialise the state of RNG#2 by both the sender and receiver. RNG#2 produces Keys K1,K2,K3,K4 (or more) from the initial state. You cannot use a PRNG, because they don't allow their internal states to be altered, but that's another story.

You can use block ciphers with it, but I'd suggest against that. Any military cryptanalyst will tell you that using block ciphers, has considerable risk - its the easiest attack to automate (by the millions of decryption chips). They don't brute-force keys for every ciphertext, just once and keep the results for lookup. Additionally, anything deterministic in a closed system is crackable - Shannon proved that - if the message exceeds the unicity distance - For AES-256 that is 40 characters of text for a 256 bit key. Block ciphers are not info-theoretically secure. Also all closed pure determinsitic systems have a built in inverse function (complicated but calculable) - Give a ciphertext C, and a message M, it will work out the key K. You MUST assume this is so, until it is proven otherwise. Otherwise you are just creating insecure systems.

The info-theoretic security requirement needs you to keep track of the key and message entropy before an encryption step, and conditional entropy of message and key at the end of the step. If one of them hits 0, you're dead and the attacker has a unique deciphertment - game over.

You get no assumptions, attacker gets all the assumptions, and assume he is unbounded in time and resources.

So to start you have 3 dimensions/variables - message, random, keys:

• Random string - R[0......n]
• Message string - M[0......n]
• Keys - state is K - produces K1,K2,K3,K4,
• Keys - independent - RK1 (for random string encryption)

Typical cycle.

1. Take 2 message characters M[0,1], XOR encrypt with K1 to get CM[0,1]
2. Take 2 random characters R[0,1], then take K2, alter RK1, XOR encrypt with RK1 to get CR[0,1]
3. Join ciphertexts CM amd CR and shuffle with K3. (transposition with random period) to get CS[0,1,2,3] - note it is not possible to identify which characetr is random or message at this point.
4. Take CS[0,1,2,3], XOR encrypt with K4 to produce final ciphertext. CC[0,1,2,3]. Add CS[0,1,2,3] to output buffer, when full, send
5. Lastly, take R[0,1] and use it to alter the state of RNG#2, to get the keys for the next encryption operation.

Since the random string is independent from the state, its entropy can be added to increase lost conditional entropy in RNG#2 state.

Note, we are sneaking the random string, by mixing it with the message and shuffling. Random strings lose no conditional entropy. This hides the message values and order (as the assailant has to consider all shuffles), and reduces the overall redundancy of the messages overall.

You can control the amount of entropy, by increasing or decreasing random message characters.

Every encryption may start with the same state+RK+M, but random will be different. Technically, the first cycle is all random characters - to increase the state length.

Because random string is ALWAYS different - cannot use a PRNG, must be truly random or cryptographically secure - this will result in random output.

To decrypt:

• Receiver has state and RK1, so can produce all needed keys to decrrypt ciphertext in reverse. Receives the CC[0,1,2,3]
• K4 decrypts to get shuffles string
• K3 unshuffles to get the CM and CR strings
• K2 is used to alter RK1 to RK2, then RK2 decrypts R[0,1]
• K1 decrypts message M[0,1] - adds it to message buffer
• Lastly, take R[0,1] and alter the RNG#2 state (synchronise with sender)

Now, that's the basics - let's get mental - take the whole concept and make it SERIOUSLY random.

• introduce a control message to handle random variation instructions - so each cycle entails the following messages [control, message, random].
• Use RNG#1 to randomly determine operations - any element of the system is open to random change.
• Keys are generated with required sizes. Note, keys don't really exist anywhere, they are generated, used, then erased.

IMPORTANTLY, never commit more than half your state entropy to any operation. Once you use an entire key, or IV, you are dead. You cannot add entropy if conditional entropy is zero.

The general idea, is that brute-force attacking this "wild thing" is not that easy.

• Cannot determine what is message, what is random.
• Cannot distinguish between operation cycles.
• RNG#2 state is guaranteed to change.
• Cannot ever derive RNG#2 state because it is never completely utilised.

Most importantly if you do the entropy and conditional entropy of key and message calculations, you will note that these never drop to zero. That's the condition for info-theoretic security.

Look for the patent "Equivocation Augmentation" for more details.

It has 5 degrees of complexity between message and key. A block cipher has 2. Just how easy do you want your systems to be broken. Your ciphertext is literally being prepackaged for processing.

I've just explained to you how to use probabilistic encryption in an info-theoretic encryption algorithm (its patented by the way). Criticise the crap out of it. I'm not interested in knowing if its OK, I want to know if there is anything that I missed.

But make your own variant, and use it. Stop wasting your time on deterministic algorithms. And you don't need to tell anyone how it works. There is no security in certainty, only in uncertainty.

Like I said. Block ciphers are not very advanced, or info-theoreticaly secure - they are insecure. There's no special category where an insecure algorithm gets a security participation prize. They are accidents waiting to happen. Ok for sending hello notes to friends, not OK for financial or military combat conditions.

• FYI, we have $\LaTeX$/MathJax enbaled on our site. Commented Oct 29, 2022 at 10:25