3
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Welcome to Cryptography.se Are you obligated to Block ciphers? What is the origin of this question? $\endgroup$
    – kelalaka
    Commented Feb 1 at 17:15
  • 2
    $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Commented Feb 2 at 8:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mathematical_Noob
    Commented Feb 5 at 15:39
  • 1
    $\begingroup$ 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$. $\endgroup$
    – fgrieu ♦
    Commented Feb 6 at 5:58

1 Answer 1

Reset to default
0
$\begingroup$

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$).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.