Generate one-time-pad with pre-shared key and public randomness

Question

I know very little about cryptography, so I apologize if the question does not make sense.

Let's say we design a function $F(P, X) \rightarrow K$ that takes in a pre-shared private key $P$ and a publicly available source of randomness (say a server that generates true random numbers) $X$. The output $K$ of this function is a new key that we use as a one-time-pad to encrypt and decrypt a message.

The sender pre-share the key $P$, the function $F$ and the source of randomness to the receiver before their communication. For every new message $M$, the sender collects the random information $X$, generates a one-time-pad $K$ using the function $F$ and encrypts the message with $K$. The receiver generates the same $K$ and decrypts the message.

My questions are

1. This scheme is not information theoretic secure, right? because AFAIK, the one-time-pad cannot be reused in any way, but in this case, we are reusing $P$ for every message, which can be considered as part of the one-time-pad $K$
2. Is this scheme viable? Is it more secure than simply encrypting/decrypting with the pre-shared key $P$?

Answer 1

The question says "pre-shared private key" where it means: pre-shared secret key. We use private key for asymmetric cryptography only, and the private key is usually not shared (only the matching public key is shared).

This scheme is not information theoretic secure, right?

It is not, for the reason stated. Enough known plaintext and enumerating all the possible $P$ is enough to break it for an arbitrarily powerful adversary.

Is this scheme viable?

Sort of, for appropriate $F$ and source of shared randomness $X$. But there are serious practical issues:

• $X$ must be wide enough to make accidental repeat use of $X$ impossible (creating a duplicate $K$, allowing decryption when the first $K$ is used to encipher known plaintext, or when both $K$ are used to encipher non-random plaintext).
• $X$ must be available and in sync for sender and receiver.
• Adversaries must be unable to chose or influence $X$ (if an adversary could force $X$ to be a constant or belong to a small set, that allows attack).

However all this is fixable by making $X$ a public counter rather than random. $X$ is transmitted in clear at start of the message: that's the Initialization Vector. This practice is called Counter Mode when $F$ is a block cipher. The IV can be kept by the sender, or drawn randomly in whole or part for each new message.

Answer 2

You can relate your construction to the approach of using a pesudo-random function (PRF) in order to extend the key-length on the one-time-pad construction (in fact, it is more typicall to use a pseudo-random generator (PRG), but since this can be obtained from a PRF, and since your construction resembles more a PRF as well, I prefer to present it like this).

A PRF is a family of functions that resemble random functions, in a very precise way. We say that a family of functions $\{F_s\}_{s\in \{0,1\}^\ell}$ is pseudo-random, where $F_s:\{0,1\}^n\to\{0,1\}^m$, if a function sampled at random from this set (which is done by sampling a random $s\in\{0,1\}^\ell$) is indistinguishable from a totally random function $f:\{0,1\}^n\to\{0,1\}^m$ (i.e. one were the image of each $x\in\{0,1\}^n$ is a uniformly random string in $\{0,1\}^m$). If you have such a family of functions then you can build an "extension" of the OTP by simply using the pre-shared secret key $s$ as a seed to get a random function $F_s$, and using $F_s(0)\|F_s(1)\|\cdots\|F_s(N)$ as a (much longer) OTP key.

Now, if you think about it, when you consider your function $F(P,X)\to K$ you're sort of using this idea: you are using some shared secret randomness to expand it to a longer, perhaps not totally uniform key. So, to answer your questions, your scheme is not information-theoretic secure but not really because you're reusing the key, but because the PRF is not really information-theoretic secure.

Remarks

Notice that, in particular, the source of randomness you call $P$ doesn't even need to be random! It only needs to ensure that the same value of $P$ is not reused among several different encryptions, and this can be achieved via a counter as I illustrate above. There is some randomness involved of course, but this is coming from the shared key.