Randomized algorithms and the one time pad

Question

The way I understand it, an algorithm is said to be randomized if it uses randomness as part of its logic (quoting Wikipedia). Now, in the case of encryption algorithms, I assume this means that for the same input, different outputs (i.e. ciphertexts) will be produced. The question is, what does "input" mean in this context?

In particular, does it include only the plain text to be encrypted, or does it also include the key? To give a concrete example, is the one time pad a randomized algorithm? If it is so, then "input" must mean plain text only.

To make matters more confusing (to me at least), again quoting Wikipedia: "To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.", where the last word is linked to the "Randomized Algorithm" page I link to in the first paragraph. So, given that the one time pad is semantically secure, is must be a randomized algorithm... right?

To add the cherry at the top of the confusion cake, there are still algorithms like, for instance, AES in CBC mode with a random IV, which will produce different outputs, when run multiple time with the same plain text, and the same key. Of course, this means that when you consider the input to one such algorithm as being the plain text only, you get the same result: different ciphertexts for the same plain text. So it would seem that the only "coherent" (lacking a better word) definition would require that input == plain text. Am I surmising correctly?

Answer 1

You indeed need to define what you understand by an encryption algorithm. The common way of doing this is to consider and encryption scheme as a tuple of three primitives: a key generation algorithm (upon a security level, output a randomly chosen pair of keys), an encryption algorithm to be instantiated with the generated key (that maps an input plaintext to an output ciphertext) and a corresponding decryption algorithm to be instantiated with the corresponding key.

To be semantically secure for an encryption scheme means that given an a priori information about a plaintext and the corresponding ciphertext under the encryption algorithm, no information from the plaintext can be derived that could not have been derived from the a priori information alone. (This has to be understood complexity theoretic-wise.)

Now the one-time pad encryption as you describe it does not fit the above scheme as it does not have this set of three primitives: the key (one-time pad) is to be changed for each plaintext. One could however construct a close encryption scheme this way (I assume fixed length plaintexts for simplicity, but it's not a limitation): one can see the key generation algorithm as a big table of pads indexed to somehow correspond to each one of the possible plaintexts. The encryption algorithm then lookup this table and xor it with the plaintext to produce the ciphertext. This scheme is semantically secure.

Here's is the bottom-line: an asymmetric encryption scheme has to be probabilistic since otherwise, given the encryption key (which is not the decryption key) it would be possible to distinguish, say, the encryption of the "hi bob!" message from that of the "hi alice!" message. But a symmetric encryption algorithm does not have to be probabilistic for the scheme to be semantically secure (the encryption scheme defined above is). However, if the security goal is to achieve the same for pairs of ciphertexts instead of single ciphertexts, then scheme defined above to fit the framework would not be sufficient as it would allow an adversary to distinguish between the pairs of ciphertexts corresponding to the same messages from the pairs of ciphertexts corresponding to distinct messages.

So, yes, a probabilistic encryption algorithm inputs a plaintext and outputs a ciphertext that will vary according to the random coins generated internally.

Answer 2

Others did already answer about the terms of a randomized (encryption) algorithm, but one thing is missing:

The one-time pad is not a semantically secure encryption algorithm.

Semantic security in essence means that you can encrypt multiple messages with the same key, and the attacker has no way of finding out which message was sent, even in the case of chosen-plaintext attacks.

While the one-time pad provides perfect secrecy when used correctly, it is broken whenever you use a key for more than one message (i.e. the "two-time pad").

Answer 3

No, the encryption algorithm used in one-time pad encryption does not need to be either probabilistic or random. The most common historical OTP algorithm is a simple substitution cypher. In digital encryption, the OTP algorithm most commonly used is XOR. Neither algorithm introduces any uncertainty. It's the key material that must be random. And how that key material is generated is critical. It must be derived from a cryptographically secure source of randomness.

Acceptable sources of randomness are surprisingly difficult to come by. Computers, despite their reputations, are designed to be precisely accurate and repeatable. The most secure random numbers come from hardware using stochastic processes such as the timing of radioactive decay, thermal component noise, and other such sources. Most commercial computers don't contain a hardware random number generator, however, so they collect different bits of things that are considered hard to predict, and combine them together into a large collection of hard-to-predict bits. This process is often called "gathering entropy". To stretch a small number of hard-to-predict bits into a usefully large number of random bits, pseudo-random number generation algorithms are sometimes used, which accept the small number of bits as a seed and produce a larger number of bits of output. Pseudo-random number generators are often built from proven secure cryptographic routines such as AES or SHA-2.

And if you're using AES to stretch a small number of bits into a long string of bits, you are essentially encrypting with AES, starting with a random number as the key. That's why a "one time pad" using a computer-generated key stream is rarely as effective as an actual one-time pad. The good news is that it's still as effective as AES, which is considered strong.

The bad news is that because people don't understand randomness very well, they think that any series of values they themselves can't predict will serve as an adequate key for a one-time pad.

To help understand why one-time pads work the way they do, I recommend studying real world attacks. One of the best documented attacks is the Venona project, recently declassified by the NSA, where they deciphered the one-time pads used by Soviet spies. The reason they were able to decipher them is that Soviet agents actually reused the keys, turning them into two-time pads. It is generally accepted that because generating the key material was tedious, time consuming, and expensive, and distributing it securely was extremely risky and difficult, that they economized by reusing the keys. That led to the break in the code, which in turn identified such notorious spies as Julius and Ethel Rosenberg and David Greenglass, and provided absolute proof of their guilt in delivering the secrets of the atomic bomb to the Soviet Union.

That cryptanalysis of course revealed the keys of the one-time pads, and those were also studied. It was determined from the distribution of the letters used that a typist simply banged back and forth on a keyboard, from one side to the other, to generate the keys. It's hard to imagine a more tedious job.

Answer 4

In cryptography, I have typically seen "randomized algorithm" used for a randomized search algorithm, that is employing randomness to organize a search for a solution (or an optimal solution) to some problem. It opposes to "deterministic (search) algorithm". For example, an algorithm that attempts to factor $N$ by picking a random number $R$ about the same size as $N$ and computing $\gcd(N,R)$ until that is neither $1$ nor $N$, is a randomized algorithm; but trial division by primes up to $\sqrt N$ is a deterministic algorithm.

I would personally not use just "randomized algorithm" for anything that use randomness essentially to generate unpredictable data; like generating a pad to be used with the One-Time-Pad method, generating a prime for RSA, or concatenating random data and plaintext before encryption (one of few techniques to transform a deterministic encryption scheme into a semantically secure encryption scheme). Bob's first comment pointed that the right term for that technique is "probabilistic encryption", as coined by Goldwasser and Micali. I could have used "randomized encryption scheme" for that, and would understand "randomized scheme", or "randomized encryption algorithm" (because encryption dissipates the aforementioned difficult goal randomized search default assumption).

In the context of an encryption scheme, input includes the plaintext and key, and only that, unless otherwise stated.

If OTP encryption and OTP decryption are seen as algorithms with the random single-use pad as the key input, then neither is a randomized algorithm.

Update: as explained in Bob's other answer, the OTP does not fit the definition of a semantically secure cipher, even though, assuming safe generation and transmission of the pad, it is semantically secure.

Caveat: I'm not a native English speaker, nor in academia.