Does anyone know what the difference between a one way function is and a hard core predicate? Are they related to each other or different?

  • $\begingroup$ basic difference (not complete): Hard-code predicates always output a single bit, one way functions may output more. $\endgroup$ – SEJPM Nov 7 '15 at 20:17
  • $\begingroup$ Indeed, one-way functions must output more for sufficiently long inputs. $\;$ $\endgroup$ – user991 Nov 7 '15 at 21:21
  • $\begingroup$ See the en.wikipedia.org/wiki/Hard-core_predicate wikipedia article. $\endgroup$ – user27950 Nov 8 '15 at 9:16
  • $\begingroup$ Thank you for reply! So I'm not understanding this statement that you can easily compute given 'x' but hard to compute given f(x). I guess I'm not entirely understanding what exactly is a hard core predicate... $\endgroup$ – Ura Nov 9 '15 at 4:37

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.