If is a function and is a polynomial time computable relation, we say is a hard-core of if for any probabilistic, polynomial time computable relation and any polynomial function , there is some such that for all :

In particular, if is one-to-one polynomial time computable then is one-way, since if it were not could be reversed to find , and then calculated (since is polynomial time computable).

No messages.