1
$\begingroup$

Given a random oracle and a deterministic signature scheme.

Is the following $hc(x)$ an hardcore predicate of $H(SIG_k(x))$ ?

$$hc(x)=lsb(H(SIG_k(x)))$$

How would I get to think about this? I saw a few academic papers that mention this strategy. I don't understand why that can be a valid hard-core predicate.

Thank you for your time!

Improve this question
$\endgroup$
3
  • $\begingroup$ Assuming that the one-way function here is $SIG_k(\cdot)$, the predicate defined is not hard-core: it is easy to compute $hc(x)$ given the value of $SIG_k(x)$ (as everyone has access to the oracle $H$). Could you provide links to the papers you mention? $\endgroup$
    – ckamath
    Commented Apr 10, 2017 at 20:02
  • $\begingroup$ arxiv.org/pdf/1607.01341.pdf page 26 $\endgroup$
    – graphtheory92
    Commented Apr 11, 2017 at 19:54
  • $\begingroup$ The only claim I came across was that the LSB is a random bit (in Page 27), which it is. $\endgroup$
    – ckamath
    Commented Apr 11, 2017 at 22:11

0

Reset to default

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.