User:XDanielx/Algebraic hash function
An algebraic or arithmetic hash function is a cryptographic hash function whose computation principally involves arithmetic in some algebra, usually a finite field. Their algebraic properties make them useful in certain cryptographic protocols, particularly zero-knowledge proofs (ZKPs) and secure multi-party computation (MPC).
Background
[edit]Many protocols for zero-knowledge proofs or multi-party computation support arbitrary bounded computations. However, the amount of computation, and sometimes communication, involved depends on the complexity of the statement being proven.
Different protocols express computations in different ways, giving rise to different cost models. In some schemes, computations are expressed as arithmetic circuits, and the cost of say creating a proof might be proportional to the number of gates in such a circuit.[1]
Conventional hashes such as SHA-2 can be computed using arithmetic circuits, but with significant overhead.
Examples
[edit]MiMC
[edit]MiMC is a family of primitives including a block cipher, a permutation, and a sponge-based hash function. It is one of the simplest and oldest algebraic hashes. It uses the cube mapping, x → x3, as a basic building block. It supports sufficiently large prime fields where x3 is a permutation.[2][3]
Rescue
[edit]Rescue[3]
Poseidon
[edit]It is used by several cryptocurrency protocols, including Filecoin.[4][3]
References
[edit]- ^ Thaler, Justin. "Proofs, Arguments, and Zero-Knowledge" (PDF).
- ^ MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity. International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg.
- ^ a b c Levit, David. STARK Friendly Hash – Survey and Recommendation (PDF) (Technical report).
- ^ Poseidon: A New Hash Function for Zero-Knowledge Proof Systems. 30th USENIX Security Symposium. USENIX Association.