1
$\begingroup$

Can someone help tell how to generate a 3-CNF verifier for SHA-256 that:

  1. outputs 1 if message/input's calculated SHA-256 value matches the pre-provided hash
  2. Otherwise outputs 0.

Given that the message can be arbitrarily long we can assume it to have a finite length (say 2 MB) to make our task simpler.

Improve this question
$\endgroup$
4
  • $\begingroup$ Except for the size of the CNF, there seems to be no salient difficulty. Do you see how you would do given a 3-CNF implementation of SHA-256 for fixed-size message? How you would build this given a 3-CNF implementation of a SHA-256 compression? How to build this from a 3-CNF implementation of a SHA-256 round? How to further break that into 3-CNF? Just start to do it, and if you get stuck, tell where. $\endgroup$
    – fgrieu ♦
    Commented Aug 5, 2021 at 7:12
  • $\begingroup$ thank you. just a follow up query. Can you suggest a good language and a circuit output program in the sense that given the high level binary operations it essentially outputs a boolean expression that implements the logic. VHDL or some other seem to be for designing circuits but i am unsure how can we get the binary logic [AND, OR, NOT] gates based output that implements the same. P.S. New to this thus somewhat clueless. $\endgroup$
    – J.Doe
    Commented Aug 5, 2021 at 8:30
  • 2
    $\begingroup$ Sorry I can't recommend a tool. I once (2004) wanted to convert to CNF a crypto-related problem (VMPC), tried to find easily used tools, failed, and ended up writing a short C program. The benchmarks it generates are still used in the SAT competitions. The whole thing started to work in a single evening, IIRC. $\endgroup$
    – fgrieu ♦
    Commented Aug 5, 2021 at 10:23
  • $\begingroup$ not an issue. thanks a lot. $\endgroup$
    – J.Doe
    Commented Aug 5, 2021 at 10:32

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.