Monolith: Circuit-Friendly Hash Functions with New Nonlinear Layers for Fast and Constant-Time Implementations

Lorenzo Grassi; Dmitry Khovratovich; Reinhard Lüftenegger; Christian Rechberger; Markus Schofnegger; Roman Walch

Paper 2023/1025

Monolith: Circuit-Friendly Hash Functions with New Nonlinear Layers for Fast and Constant-Time Implementations

Lorenzo Grassi, Ponos Technology (Switzerland), Ruhr University Bochum (Germany)

Dmitry Khovratovich, Ethereum Foundation (Luxembourg), ABDK Consulting (Estonia)

Reinhard Lüftenegger, Graz University of Technology (Austria)

Christian Rechberger, Graz University of Technology (Austria)

Markus Schofnegger, Horizen Labs (United States)

Roman Walch, Graz University of Technology (Austria), TACEO (Austria)

Abstract

Hash functions are a crucial component in incrementally verifiable computation (IVC) protocols and applications. Among those, recursive SNARKs and folding schemes require hash functions to be both fast in native CPU computations and compact in algebraic descriptions (constraints). However, neither SHA-2/3 nor newer algebraic constructions, such as Poseidon, achieve both requirements. In this work we overcome this problem in several steps. First, for certain prime field domains we propose a new design strategy called Kintsugi, which explains how to construct nonlinear layers of high algebraic degree which allow fast native implementations and at the same time also an efficient circuit description for zero-knowledge applications. Then we suggest another layer, based on the Feistel Type-3 scheme, and prove wide trail bounds for its combination with an MDS matrix. We propose a new permutation design named Monolith to be used as a sponge or compression function. It is the first arithmetization-oriented function with a native performance comparable to SHA3-256. At the same time, it outperforms Poseidon in a circuit using the Merkle tree prover in the Plonky2 framework. Contrary to previously proposed designs, Monolith also allows for efficient constant-time native implementations which mitigates the risk of side-channel attacks

Note: The updated version is a major rewrite improving the clarity of the paper. However, the Monolith construction, its specification and instances were not changed.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint.
Keywords: Hash Functions Monolith Zero Knowledge
Contact author(s): lorenzo grassi @ ruhr-uni-bochum de
khovratovich @ gmail com
reinhard lueftenegger @ iaik tugraz at
christian rechberger @ tugraz at
markus schofnegger @ gmail com
walchroman @ gmail com
History: 2024-02-14: last of 2 revisions; 2023-07-02: received; See all versions
Short URL: https://ia.cr/2023/1025
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1025,
      author = {Lorenzo Grassi and Dmitry Khovratovich and Reinhard Lüftenegger and Christian Rechberger and Markus Schofnegger and Roman Walch},
      title = {Monolith: Circuit-Friendly Hash Functions with New Nonlinear Layers for Fast and Constant-Time Implementations},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1025},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1025}},
      url = {https://eprint.iacr.org/2023/1025}
}