# How can encryption involve randomness?

If an encryption algorithm is meant to convert a string to another string which can then be decrypted back to the original, how could this process involve any randomness?

Surely it has to be deterministic, otherwise how could the decryption function know what factors were involved in creating the encrypted string?

-
Please don't ask identical questions on multiple Stack Exchange sites, like this one on Crypto.SE. –  Paŭlo Ebermann May 27 '12 at 0:07

There can be more than one ciphertext that maps back to the same plaintext. In mathematical terms, the encryption algorithm must be injective so that you can recover the plaintext for the ciphertext, but this does not prevent the ciphertext from encoding more information than the plaintext.

As a concrete example, consider modes of block cipher operation such as CBC, CTR or OFB. All these modes involve an IV (initialization vector) in addition to the plaintext, the block cipher algorithm and its key. (For CTR, the IV is called a nonce, but it plays a similar role.) The encryption function is deterministic for a given IV. The IV, on the other hand, may be chosen randomly (for CTR, it must be chosen randomly). Thus, unless the protocol specifies a deterministic method of choosing the IV (such as an agreed-upon constant), the IV is sent alongside the ciphertext. In fact, the output of the encryption software often consists of the IV followed by the cipher text stricto sensu. The IV itself is sent in plaintext; it does not (must not) contain any confidential information.

As another example, consider the PKCS1.5 mode (“padding scheme”) of RSA (defined in PKCS#1 version 1.5 — see p.22–25 of PKCS#1 v2.1). Simplifying a bit, this mode consists of concatenating a random string with the message, then applying the exponentiation operation. The ciphertext is $(P \mathbin\Vert M)^e \mod{n}$ where $\Vert$ is concatenation, $M$ is the message and $P$ is a padding string most of whose bits are random. To recover the message from the ciphertext $C$, apply the raw decryption operation $C^d \mod{n}$ and break up $C$ into padding (which is discarded) and message.

-

Not only can encryption schemes have randomness, but in some cases (e.g., public-key encryption), they must be randomized. This is not a problem since we require an encryption scheme to be correct, that is, for any message $m$ and any key $k$ it holds that $$\Pr \big[\ \text{DEC} \left( \ \text{ENC}\left(k, m, R\right) \ \big) = m \right] =1$$ over the randomness $R$.

The reason that public key schemes must be random stems from the way we define security: we don't wish the ciphertext to leak any information about the encrypted message. The classical example is the following. Assume that $(pk,sk)$ is the public and secret key, respectively, and that the adversary intercepts an encrypted message $c$ sent to some unit in the field. The adversary knows that the message is either "ATTACK " or "RETREAT", but doesn't know which. One thing that the adversary can do is to encrypt both messages using the public $pk$. let $c_A = \text{ENC}_{pk}(\text{"ATTACK "})$ and $c_R = \text{ENC}_{pk}(\text{"RETREAT"})$. If $\text{ENC}$ is deterministic, the adversary can find out the message with certainty by comparing $c$ to $c_A$ and $c_R$.

The way this notion is formally defined is known as semantic security:

An encryption scheme is semantically secure if any adversary ${\cal A}$ cannot win the following game with probability noticeably greater than $1/2$:

1. A challenger ${\cal C}$ generates keys $(pk,sk)$ and sends the public key $pk$ to the adversary.
2. ${\cal A}$ chooses two messages of equal length $m_0$ and $m_1$ and gives them both to ${\cal C}$.
3. ${\cal C}$ uniformly picks a bit $b\in\{0,1\}$ and sends back $\text{ENC}(m_b)$.
4. ${\cal A}$ needs to say which message was encrypted: $m_0$ or $m_1$, that is, he needs to output the bit $b$.

(I'm omitting the security parameter $\kappa$, which is critical for defining "negligible" or "noticable"; We need to assume that the generation of the keys depends on $\kappa$, and that the advantage ${\cal A}$ has above $1/2$ is negligible in $\kappa$, i.e., less than $\kappa^{-\omega(1)}$)

-
we can add a random string to the end of the input before preforming encryption to avoid the problem and always have $DEC(ENC(k,m,R))=m$, i.e. the condition can be stronger than the one you have stated on top. –  Kaveh May 25 '12 at 5:25

You have not stated what type of encryption we are discussing, but let me point out what is really needed for the security of the cartographic protocols (in addition what is stated in other answers).

What we really need is this: the keys should be generated randomly (this can be done in collaboration as in public-key cryptography like RSA or by one entity as in private-key cryptography). The randomness of the key makes sure that an adversary cannot predict the keys (and use them to break the protocol). As long as the keys look random to the adversary the protocol will be secure. Often, the keys are generated by a randomized algorithm and then given to the parties, while the encryption and decryption algorithms are not randomized but deterministic.

Also remember that being randomized doesn't mean that the process is not invertable. A simple example is the following: given $x$, randomly generate $r$, output $\langle x,r\rangle$. For inverting, we can output the first part of the pair.

-
your example is important: without random padding, vanilla RSA is insecure. with random padding, RSA can be proven to have nice security properties in the random oracle model –  Sasho Nikolov May 24 '12 at 4:34

Both the encryption and the decryption algorithms can be randomised as long as you can prove some theorem that encryption followed by decryption will give you the original message most of the times.

Why would anyone want such an encryption scheme? Because: 1) there exist situations where we don't want to be right all the time but only 99999999 times out of every 100000000 and 2) allowing such small errors often improves something else (such as efficiency) by a disproportionate amount.

-
While probabilistic encryption do exist, they're rather on the exotic side. Plenty of everyday encryption algorithm involve randomness without being probabilistic. –  Gilles May 23 '12 at 21:47
@Gilles: An important distinction to make. –  Raphael May 23 '12 at 21:49

Just to cite an example, in RSA encryption, you need to generate two primes $p$ and $q$ and an integer $e$ which will be used to create your public and private keys.

If you generate any of these values in a deterministic way, then their generation can be reproduced, potentially compromising your encryption. If these numbers are generated in a randomized way, then this is not an issue.

Update

As a more specific example of Ran G.'s answer, you could have a look at Elliptic Curve cryptography, where the algorithm requires a random parameter (usually called $d$, $k$ or $r$) to encrypt and decrypt messages. If the same "random" parameter is used more than once, they key can be computed from two encrypted messages. This was the problem/premise of last year's PlayStation 3 hack.

-
This is randomness in the key generation, which I doubt is the question: any key generation must involve randomness, otherwise the key is predictable (or derived and not generated). –  Gilles May 23 '12 at 21:46
I don't think that is the place for randomisation the OP has in mind. Keys are given and static for the (en|de)cryption. How you choose your key is independent of that. –  Raphael May 23 '12 at 21:48
@Gilles: I wouldn't consider it that clear cut. The values $p$, $q$ and $e$ are usually stored in an encrypted form, with a user-chosen password. Strictly speaking, they are the key, but from a user's perspective, they are just random values generated by typing gibberish on the keyboard and have nothing to do with their carefully-chosen password. –  Pedro May 23 '12 at 22:33
@Pedro I don't understand how your latest comment relates to the question. Even from the perspective of key files (which I don't see in the question), the key is evidently not randomly generated, it's derived from the key file and the password. –  Gilles May 23 '12 at 22:41