Reinforced Concrete: A Fast Hash Function for Verifiable Computation

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

doi:10.1145/3548606.3560686

Reinforced Concrete: A Fast Hash Function for Verifiable Computation

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

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Abstract

We propose a new hash function Reinforced Concrete, which is the first generic purpose hash that is fast both for a zero-knowledge prover and in native x86 computations. It is suitable for a various range of zero-knowledge proofs and protocols, from set membership to generic purpose verifiable computation. Being up to 15x faster than its predecessor Poseidon hash, Reinforced Concrete inherits security from traditional time-tested schemes such as AES, whereas taking the zero-knowledge performance from a novel and efficient decomposition of a prime field into compact buckets.

The new hash function is suitable for a wide range of applications like privacy-preserving cryptocurrencies, verifiable encryption, protocols with state membership proofs, or verifiable computation. It may serve as a drop-in replacement for various prime-field hashes such as variants of MiMC, Poseidon, Pedersen hash, and others.

Original language	English
Title of host publication	CCS 2022 - Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security
Publisher	Association of Computing Machinery
Pages	1323–1335
Number of pages	13
ISBN (Electronic)	978-1-4503-9450-5
DOIs	https://doi.org/10.1145/3548606.3560686
Publication status	Published - 7 Nov 2022
Event	2022 ACM SIGSAC Conference on Computer and Communications Security: ACM CSS 2022 - Los Angeles, United States Duration: 7 Nov 2022 → 11 Nov 2022

Publication series

Name	Proceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)	1543-7221

Conference

Conference	2022 ACM SIGSAC Conference on Computer and Communications Security
Abbreviated title	ACM CSS 2022
Country/Territory	United States
City	Los Angeles
Period	7/11/22 → 11/11/22

Keywords

finite fields
hash functions
verifiable computation
zksnarks

ASJC Scopus subject areas

Software
Computer Networks and Communications

Access to Document

10.1145/3548606.3560686Licence: CC BY-ND 4.0

Cite this

Lüftenegger, R., Rechberger, C., Grassi, L., Schofnegger, M., Walch, R., & Khovratovich, D. (2022). Reinforced Concrete: A Fast Hash Function for Verifiable Computation. In CCS 2022 - Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (pp. 1323–1335). (Proceedings of the ACM Conference on Computer and Communications Security). Association of Computing Machinery. https://doi.org/10.1145/3548606.3560686

Reinforced Concrete: A Fast Hash Function for Verifiable Computation. / Lüftenegger, Reinhard; Rechberger, Christian; Grassi, Lorenzo et al.
CCS 2022 - Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. Association of Computing Machinery, 2022. p. 1323–1335 (Proceedings of the ACM Conference on Computer and Communications Security).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Lüftenegger, R, Rechberger, C, Grassi, L, Schofnegger, M, Walch, R & Khovratovich, D 2022, Reinforced Concrete: A Fast Hash Function for Verifiable Computation. in CCS 2022 - Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. Proceedings of the ACM Conference on Computer and Communications Security, Association of Computing Machinery, pp. 1323–1335, 2022 ACM SIGSAC Conference on Computer and Communications Security, Los Angeles, United States, 7/11/22. https://doi.org/10.1145/3548606.3560686

Lüftenegger R, Rechberger C, Grassi L, Schofnegger M, Walch R, Khovratovich D. Reinforced Concrete: A Fast Hash Function for Verifiable Computation. In CCS 2022 - Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. Association of Computing Machinery. 2022. p. 1323–1335. (Proceedings of the ACM Conference on Computer and Communications Security). doi: 10.1145/3548606.3560686

Lüftenegger, Reinhard ; Rechberger, Christian ; Grassi, Lorenzo et al. / Reinforced Concrete: A Fast Hash Function for Verifiable Computation. CCS 2022 - Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. Association of Computing Machinery, 2022. pp. 1323–1335 (Proceedings of the ACM Conference on Computer and Communications Security).

@inproceedings{deb26a2b48354e14b85bdbb719dd2cd7,

title = "Reinforced Concrete: A Fast Hash Function for Verifiable Computation",

abstract = "We propose a new hash function Reinforced Concrete, which is the first generic purpose hash that is fast both for a zero-knowledge prover and in native x86 computations. It is suitable for a various range of zero-knowledge proofs and protocols, from set membership to generic purpose verifiable computation. Being up to 15x faster than its predecessor Poseidon hash, Reinforced Concrete inherits security from traditional time-tested schemes such as AES, whereas taking the zero-knowledge performance from a novel and efficient decomposition of a prime field into compact buckets.The new hash function is suitable for a wide range of applications like privacy-preserving cryptocurrencies, verifiable encryption, protocols with state membership proofs, or verifiable computation. It may serve as a drop-in replacement for various prime-field hashes such as variants of MiMC, Poseidon, Pedersen hash, and others.",

keywords = "finite fields, hash functions, verifiable computation, zksnarks",

author = "Reinhard L{\"u}ftenegger and Christian Rechberger and Lorenzo Grassi and Markus Schofnegger and Roman Walch and Dmitry Khovratovich",

year = "2022",

month = nov,

day = "7",

doi = "10.1145/3548606.3560686",

language = "English",

series = "Proceedings of the ACM Conference on Computer and Communications Security",

publisher = "Association of Computing Machinery",

pages = "1323–1335",

booktitle = "CCS 2022 - Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security",

address = "United States",

note = "2022 ACM SIGSAC Conference on Computer and Communications Security : ACM CSS 2022, ACM CSS 2022 ; Conference date: 07-11-2022 Through 11-11-2022",

}

TY - GEN

T1 - Reinforced Concrete: A Fast Hash Function for Verifiable Computation

AU - Lüftenegger, Reinhard

AU - Rechberger, Christian

AU - Grassi, Lorenzo

AU - Schofnegger, Markus

AU - Walch, Roman

AU - Khovratovich, Dmitry

PY - 2022/11/7

Y1 - 2022/11/7

N2 - We propose a new hash function Reinforced Concrete, which is the first generic purpose hash that is fast both for a zero-knowledge prover and in native x86 computations. It is suitable for a various range of zero-knowledge proofs and protocols, from set membership to generic purpose verifiable computation. Being up to 15x faster than its predecessor Poseidon hash, Reinforced Concrete inherits security from traditional time-tested schemes such as AES, whereas taking the zero-knowledge performance from a novel and efficient decomposition of a prime field into compact buckets.The new hash function is suitable for a wide range of applications like privacy-preserving cryptocurrencies, verifiable encryption, protocols with state membership proofs, or verifiable computation. It may serve as a drop-in replacement for various prime-field hashes such as variants of MiMC, Poseidon, Pedersen hash, and others.

AB - We propose a new hash function Reinforced Concrete, which is the first generic purpose hash that is fast both for a zero-knowledge prover and in native x86 computations. It is suitable for a various range of zero-knowledge proofs and protocols, from set membership to generic purpose verifiable computation. Being up to 15x faster than its predecessor Poseidon hash, Reinforced Concrete inherits security from traditional time-tested schemes such as AES, whereas taking the zero-knowledge performance from a novel and efficient decomposition of a prime field into compact buckets.The new hash function is suitable for a wide range of applications like privacy-preserving cryptocurrencies, verifiable encryption, protocols with state membership proofs, or verifiable computation. It may serve as a drop-in replacement for various prime-field hashes such as variants of MiMC, Poseidon, Pedersen hash, and others.

KW - finite fields

KW - hash functions

KW - verifiable computation

KW - zksnarks

UR - http://www.scopus.com/inward/record.url?scp=85143084514&partnerID=8YFLogxK

U2 - 10.1145/3548606.3560686

DO - 10.1145/3548606.3560686

M3 - Conference paper

T3 - Proceedings of the ACM Conference on Computer and Communications Security

SP - 1323

EP - 1335

BT - CCS 2022 - Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security

PB - Association of Computing Machinery

T2 - 2022 ACM SIGSAC Conference on Computer and Communications Security

Y2 - 7 November 2022 through 11 November 2022

ER -

Reinforced Concrete: A Fast Hash Function for Verifiable Computation

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this