# Find two hard to reverse functions f and h such that f ∘ h ∘ g = h (f and h injective, no constraints on g)

I am looking from 3 functions $$f,g,h$$ from $$\mathbb N \to \mathbb N$$ (they can be bijections, they need to be injective at least), such that:

$$f \circ h \circ g = h$$

and $$f$$ is hard to reverse programmatically, and $$h$$ is hard to reverse programmatically.

$$g$$ and $$h$$ cannot be keyed functions as they will be public.

Right now, I am using AES SP 801-108 for $$h$$ but any function hard to reverse will do.

• Welcome to Cryptography.se Are you obligated to Block ciphers? What is the origin of this question? Commented Feb 1 at 17:15
• A block cipher is "hard to reverse programmatically" for one not knowing the key. The current question thus seems to allow the following straightforward construction. Note $E_k$ for AES encryption with key $k$, $D_k$ for the decryption. Pick two random secret distinct keys $k,ℓ$ and define $f=E_k∘D_ℓ$, $g=D_k∘E_ℓ$, $h=E_k$. It follows $f∘h∘g=E_k∘D_ℓ∘E_k∘D_k∘E_ℓ=E_k=h$. If this does not fit, please edit the question again; like, if the internals of some function must be public, and it or other function(s) must still be hard to reverse.
– fgrieu
Commented Feb 2 at 8:24
• Thank you very much for your help. Indeed, the internals of function h and g need to be public, therefore only f can be a keyed function. I updated the question accordingly. Commented Feb 5 at 15:39
• Please expand on what "hard to reverse" is intended to mean. In particular, does being able to compute $f^{-1}$ count as reversing $f$? If not: what about textbook RSA with a public modulus of secret factorization, $g$ encryption, $f$ decryption, and $h$ encryption with another exponent and the same modulus? That satisfies the equation, and knowing the internals of $g$ and $h$ it's impossible to evaluate $f(x)$, $g^{-1}(x)$ or $h^{-1}(x)$ for random input $x\in[0,p)$. When either $g$, $h$ or $h∘g$ is applied to an appropriately padded message, it can't be deciphered without $f$.
– fgrieu
Commented Feb 6 at 5:58

It is essentially key exchange: let $$x$$ be the input, $$g$$ encrypts $$x$$ using public key 1, $$h$$ encrypts the result using public key 2, and then $$f$$ decrypts the result using private key 1, where private key 1 and public key 1 is a public-key pair. Additionally we need the decryption $$f$$ cancels $$g$$ and leaves $$h$$, which can be obtained from many public-key schemes, such as RSA, suggested by @fgrieu.
The "hard-to-reverse" requirement of $$f$$ is tricky because the private-key often gives public-key as a simple reverse. If only $$f$$ is given, then it might be possible. This seems impossible if both $$f, g$$ are publicly given because they mush be dependent (if $$f$$ is parametered by $$k$$, then $$g$$ must depend on $$k$$).