I'm going over hardcore predicates now and trying to understand the concept. Some lecture slides I've seen online imply that there cannot be a generic hardcore predicate for all one way functions because for a OWF f(x) and predicate b(x) you can always define g(x) = (f(x), b(x)).

Which supposedly gives up the information of what b(x) is while g remains one way (because f is).

My question is, what about the predicate b(x) = x?

Since the functions are one way, there is no way we can guess x given f(x) in an easy manner.

And if we were to define a g as before it would no longer be one way seeing as it gives up what it's initial input was.

Am I missing something? Maybe I misunderstood the lecture and there does exist a generic hardcore predicate for one way functions? Any helps would be appreciated.

  • 1
    $\begingroup$ A predicate is a 0-1 value. $\endgroup$ – fkraiem Nov 25 '16 at 10:28
  • $\begingroup$ oh, of course. It completely slipped my mind. Thank you. $\endgroup$ – TheFooBarWay Nov 25 '16 at 10:31
  • $\begingroup$ You can now answer your own question. :) $\endgroup$ – fkraiem Nov 25 '16 at 10:51
  • $\begingroup$ This will slip the mind of other persons as well, so I voted up despite the fact that it is a slip of the mind:) $\endgroup$ – Maarten Bodewes Nov 25 '16 at 13:33

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.