The (informal) definition of trapdoor function is a one-way function with a trapdoor $t$ such that

  1. given $f$, it is easy to compute $f(x)$ for any $x$, but hard to compute $f^{-1}(y)$ efficiently
  2. given a trapdoor $t$, it will be easy and efficient to compute $f^{-1}(y)$ for any $y$.

By non-learnable with blackbox, I mean: Give a probabilistic polynomial-time adversary the description $f$, and an oracle that computes $f^{-1}(y)$ on any input $y$, but we do not give the adversary the trapdoor $t$. After only polynomial queries, adversary cannot efficiently and correctly compute $f^{-1}(y)$ for some randomly chosen $y$( not queried before) with high probability.

What are some constructions for trapdoor functions where their inverses are non-learnable through black-box access?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.