1
$\begingroup$

Given an arithmetic circuit over a finite field of characteristic 2, what families of cryptographic hash functions can be efficiently computed with this circuit?

Can standard hash functions be computed? To do so, standard bit operations would be necessary. XOR is possible via addition, but are there any arithmetic operations corresponding to other necessary bit operations like SHIFT, AND, NOT, etc.? An explanation of what bit operations are possible would be great.

If standard hash functions are not suitable, are there specialized hash functions developed for use over finite fields? If so, please reference any related papers.

$\endgroup$
  • $\begingroup$ BTW: if you are looking for hash functions that allow efficient zero knowledge proofs, you might want to start looking at Picnic eprint.iacr.org/2017/279.pdf which has the same requirements; you might want to look what they did $\endgroup$ – poncho May 23 '18 at 3:32
  • $\begingroup$ Shifting can be performed by multiplying or dividing the polynomial by $x$. $\endgroup$ – conchild Jul 22 '18 at 11:10
2
$\begingroup$

Given an arithmetic circuit over a finite field of characteristic 2, what families of cryptographic hash functions can be computed with this circuit?

Answer: all of them. The combination of addition and multiplication in $GF(2^m)$ is complete. That is, for any arbitrary function that takes $n$ inputs in $GF(2^m)$ and an output in $GF(2^m)$, there exists a polynomial in $n$ variables that produces that function.

Note that this polynomial need not be simple; however it will exist.

$\endgroup$
  • $\begingroup$ Yes, I am aware of this. Thank you, but I'm looking for efficient, practical solutions. $\endgroup$ – Joseph Johnston May 23 '18 at 3:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.