# What hash functions can be (efficiently) computed over GF(2^m)?

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.

• 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 – poncho May 23 '18 at 3:32
• Shifting can be performed by multiplying or dividing the polynomial by $x$. – conchild Jul 22 '18 at 11:10

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.