Join Log in
Score:1
J.Doe avatar Crypto

A SHA verifier in the CNF format

br flag
J.Doe

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.

38
0 + 4
fgrieu avatar
ng flag
fgrieu
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.
0
Reply
J.Doe avatar
br flag
J.Doe
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.
0
Reply
fgrieu avatar
ng flag
fgrieu
Sorry I can't recommend a tool. I once (2004) wanted to convert to CNF a crypto-related problem ([VMPC](http://www.vmpcfunction.com/vmpc.pdf)), tried to find easily used tools, failed, and ended up writing [a short C program](https://pastebin.com/WbDaYxWP). The benchmarks it generates are still used in the SAT competitions. The whole thing started to work in a single evening, IIRC.
2
Reply
J.Doe avatar
br flag
J.Doe
not an issue. thanks a lot.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.