2025/03/04 by Clémence Bouvier, Lorenzo Grassi, Dmitry Khovratovich +4 · 1 voice
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Chaos-based Image/Signal Encryption
paper · pdf · doi:10.46586/tches.v2025.i2.743-780
openalex publication_date 2025/03/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Arithmetic hash functions defined over prime fields have been actively developed and used in verifiable computation (VC) protocols. Among those, ellipticcurve- based SNARKs require large (256-bit and higher) primes. Such hash functions are notably slow, losing a factor of up to 1000 compared to regular constructions like SHA-2/3.In this paper, we present the hash function Skyscraper, which is aimed at large prime fields and provides major improvements compared to Reinforced Concrete and Monolith. First, the design is exactly the same for all large primes, which simplifies analysis and deployment. Secondly, it achieves a performance comparable to cryptographic hash standards by using low-degree non-invertible transformations and minimizing modulo reductions. Concretely, it hashes two 256-bit prime field (BLS12-381 curve scalar field) elements in 135 nanoseconds, whereas SHA-256 needs 42 nanoseconds on the same machine.The low circuit complexity of Skyscraper, together with its high native speed, should allow a substantial reduction in many VC scenarios, particularly in recursive proofs.