Computationally expensive key derivation whose difficulty is asymmetric

Question

I am looking for a primitive or a construction that meets the following requirements. Is such a construction (a) theoretically possible, and (b) in existence right now?

Given are:

• a long secret $X$
• a authenticated cipher that takes a key $K$ with encryption function $\mathcal{E}_K$ and decryption function $\mathcal{D}_K$
• a trusted server $S$
• a set of trusted clients $C$
• an attacker

Every client has a copy of $X$ in the encrypted form of $\mathcal{E}_K(X)$, where the decryption key $K$ is the same across all clients. I am trying to find a pair of functions $\mathcal{F}_S$ (on the server) and $\mathcal{F}_C$ (on the clients) such that $\mathcal{F}_C(Y, e) = \mathcal{F}_S(Y) = K$, where $e$ is a cost factor and $Y$ is a secret value that varies between each client.

I need $\mathcal{F}_S$ to be computationally inexpensive so that the server can generate many different values of $Y$ (to provision many different clients) quickly, yet all clients arrive at the same value $K$ with which to decrypt secret $X$. On the other hand, I need $\mathcal{F}_C$ to be computationally expensive so that it is prohibitively computationally expensive to the point of infeasibility for an attacker to (a) guess a valid $Y$ given only $\mathcal{F}_C$ and $e$ (i.e. Kerckhoff's principle applies for $\mathcal{F}_C$ with respect to $Y$), and (b) derive a new tuple of $(Y_1, e_1)$ given an existing tuple $(Y_0, e_0)$ that is known to the attacker to generate $K$.

---

Similar issues have already been solved in other contexts.

Key derivation functions such as HKDF per se are not news. However, they do not seem to allow fixing the output value to generate a series of input values that all generate the same output value.

Computationally difficult functions exist in the context of passwords (such as Argon2, scrypt, bcrypt, PBKDF2). However, not only do these suffer the same issue as key derivation functions in general, but these are symmetrically expensive, which means that the load on the server is immense when provisioning clients.

I've also thought about approaching this issue by making the client perform a brute-force computation of varying missing parts of $K$, but this gives attackers an undue advantage if the missing parts must be chosen such that computationally weak clients can finish the brute force search in less than a minute, but an attacker (a) is able to parallelize and very quickly run the brute force search to recover $K$, and (b) having determined $K$ is able to trivially generate their own $K$ with missing bits.

Another attempt involved a Diffie–Hellman protocol, but it seems infeasibly difficult to fix the shared secret and generate two inputs that then yield the fixed shared secret.

Answer 1

The immediately obvious way to do this is to use RSA in a large-public-exponent format.

That is, the server selects an RSA modulus, and a large public exponent (say, $e = 2^{2^{30}}+1$) [1]; if the RSA primes are safe primes, this practically eliminates the possibility that $e$ is not relative prime to either $p-1$ or $q-1$. The server would internally compute the CRT parameters (which are the same size as for normal RSA with the same modulus size, and the large $e$ value does not complicate this computation), and publish the public parameters (the modulus and the large $e$ in some compressed format; e.g. if it's always in the form $2^{2^x}+1$, we might just denote $x$). We would also select a good RSA encryption padding method, such as OEAP.

Then, we have $\mathcal{F}_C(Y) = \text{Depad}( Y^e )$ (where $\text{Depad}$ is the procedure for removing the RSA padding); to compute $Y$, the server would take $K$, randomly pad it, and then perform the RSA private transform.

The client would need to perform $O( \log e )$ modular multiplications to compute $\mathcal{F}_C$; by selecting $e$ sufficiently large, we can make this as expensive as we like. And, while the inverse computation of $\mathcal{F}_S$ isn't exceptionally cheap (it's about as expensive as generating an RSA signature or doing an RSA public key decryption), it isn't that bad (and we could reduce the cost somewhat if we used multiprime RSA). And, if the server had some RSA acceleration hardware (which is not rare), this can be even cheaper.

Obviously, this is not the normal use of RSA, either as a public key encryption method, or as a signature method. It is still a valid use of the concept.

---

[1]: Note: I'm using $e$ to describe the public exponent we give to the client, not the cost factor (as the question used it).