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

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

MiMC

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

Rescue[3]

Poseidon

It is used by several cryptocurrency protocols, including Filecoin.[4][3]

References

  1. ^ Thaler, Justin. "Proofs, Arguments, and Zero-Knowledge" (PDF).
  2. ^ 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.
  3. ^ a b c Levit, David. STARK Friendly Hash – Survey and Recommendation (PDF) (Technical report).
  4. ^ Poseidon: A New Hash Function for Zero-Knowledge Proof Systems. 30th USENIX Security Symposium. USENIX Association.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.