How can I prove that given a predicate $hc$ and a one-way function $f$ that $hc$ is not hard-core? I was thinking about something like that:

i define $f(x) = (g(x), hc(x))$ that is one-way but $hc$ is not hard-core 'cause it's value is easly reconstructable from the output.

Is it right? How can I actually prove that?

  • 2
    $\begingroup$ You must exhibit an efficient algorithm that computes $\mathrm{hc}(x)$ with non-negligible probability when given $f(x)$ (for uniformly random $x$). $\endgroup$
    – fkraiem
    May 29, 2019 at 14:26
  • $\begingroup$ Do I understand you correctly, that $g$ is a OWF and $hc$ is a hardcore predicate of $g$? And your question is why $hc$ is not also a hardcore predicate of $f$ as defined in the question? $\endgroup$
    – Maeher
    May 29, 2019 at 19:43
  • $\begingroup$ $G$ is a OWF and given the function $f$ that is something like $f(x) = (g(x), hc(x))$ I have to prove that eventhogh $f$ is OWF, $hc$ is not hard core for $f$ $\endgroup$
    – quaqua
    May 30, 2019 at 14:59
  • $\begingroup$ @quaqua: So like given $(g(x), hc(x))$ make a good guess at the value of $hc(x)$? $\endgroup$
    – Ry-
    May 31, 2019 at 0:59
  • $\begingroup$ @Ry yes, i have to prove it somehow $\endgroup$
    – quaqua
    May 31, 2019 at 12:10


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.