1
$\begingroup$

We know that, for one-way function $y=f(x)$, it's hard to compute $x=f^{-1}(y)$, but there exists an efficient algorithm $A(y,t)=f^{-1}(x)$ once we know the trapdoor information $t$.

I'm wondering, whether or not this property can be generalized to function of functions. i.e.

Is there a trapdoor one-way function $OWF(f)=g$ where $f, g$ are both functions with the same image space? And the trapdoor function $t$ has the same preimage space as $f$, and it should satisfy that, for any input $x$ and adversary $Adv_G$, it has negligible probability to recover $f(x)$ with the information of $g$, but if $t(x)$ is given, an efficient algorithm $A_{G,t(x)}$ can help us recover $f(x)$, but any algorithm $A_{G,t(x)}$ cannot recover $f(x')$ for any other $x'$ with non-negligible probability.

If the definition is too broad, any partial solution with additional assumptions on properties of $f,g$ is also welcomed.

Thanks a lot for any help!

$\endgroup$

1 Answer 1

1
$\begingroup$

At a basic level the following may be an answer:

Let your trapdoor function be RSA. So $n=pq,$ and the factorization is the trapdoor. Parametrize this as $$ RSA(n_i,t_i=[p_i,q_i]) $$ as a family of functions.

If you select uniformly at random (according to best RSA practice), primes $p_i,q_i$ from some reasonable range (say from $[2^{4096},2^{4097}-1]$) then the family of trapdoor functions should satisfy your property, for reasonable family size.

OWF which maps between different instantiations ($f$ and $g$ in your formulation) may be the purely random seed of a random prime generation algorithm which uses as an input the $SEED_i$ corresponding to $$ RSA(n_i,t_i=[p_i,q_i]) $$ and a new seed $S_{i\rightarrow j}$ to obtain $$ RSA(n_j,t_i=[p_j,q_j]), $$ where $S_{i\rightarrow j}$ is used to generate $[p_j,q_j].$

$\endgroup$
3
  • $\begingroup$ Thank you for the insight! If my understanding is correct, the size of the constructed OWF will be very large, and the construction is not applicable to continuous case. Is that right? $\endgroup$
    – Marc_12
    Feb 12 at 23:03
  • $\begingroup$ Yes, since it needs to encode a mapping between two huge domains. On the other hand, I don't understand what you mean by continuous case, modern cryptography is based on discrete groups/fields etc. $\endgroup$
    – kodlu
    Feb 13 at 2:09
  • 1
    $\begingroup$ Thank you! By continuous case, I mean that whether the properties of the functions can help in reducing the complexity of encoding the large mapping (e.g. L-lipschitz, smoothness, convexity, strong convexity, etc.) . Intuitively, when functions have some good properties, we don't need to encode it by exhaustively listing all the possible mappings, but I don't know how to utilize this property in cryptography. $\endgroup$
    – Marc_12
    Feb 13 at 16:16

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.