Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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$:
- A challenger ${\cal C}$ generates keys $(pk,sk)$ and sends the public key $pk$ to the adversary.
- ${\cal A}$ chooses two messages of equal length $m_0$ and $m_1$ and gives them both to ${\cal C}$.
- ${\cal C}$ uniformly picks a bit $b\in\{0,1\}$ and sends back $\text{ENC}(m_b)$.
- ${\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)}$)
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.
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.
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.
