I've read the sources of ZKBoo where they transformed arithmetic operations of the SHA hash functions into a bunch of boolean ones. Where does this transformation arise from? How do you construct such transformation? How do you prove that these boolean operations are equivalent to arithmetic ones?

I've followed Circuit-based Evaluation of the Arithmetic Transform of Boolean Functions by René Krenz et al. but that seems to go the other way around: constructing arithmetic expression from a circuit.

Thanks in advance!

  • $\begingroup$ Every language that is Turing complete has a mathematical equivalence between each other, you can translate between them. This includes both logic gate circuits and boolean expressions. And anything computable can be expressed in a Turing complete languages (so "lesser" languages can also be translated to Turing complete languages). $\endgroup$
    – Natanael
    Feb 15 '19 at 12:19
  • $\begingroup$ I am aware of that. I am more interested into the construction/transformation. This doesn't help me understand of how you transform that... $\endgroup$
    – PeterBocan
    Feb 15 '19 at 12:32
  • $\begingroup$ theteacher.info/index.php/… and allaboutcircuits.com/textbook/digital/chpt-7/… - these are about deriving boolean expressions from gates $\endgroup$
    – Natanael
    Feb 15 '19 at 12:36
  • $\begingroup$ @PeterBocan: don't you mean "boolean operations of the SHA function into arithmetic ones"? $\endgroup$ Feb 16 '19 at 9:36

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.