Paper 2018/1098

MARVELlous: a STARK-Friendly Family of Cryptographic Primitives

Tomer Ashur and Siemen Dhooghe

Abstract

The ZK-STARK technology, published by Ben-Sasson et al. in ePrint 2018/046 is hailed by many as being a viable, efficient solution to the scaling problem of cryptocurrencies. In essence, a ZK-STARK proof uses a Merkle-tree to compress the data that needs to be verified, thus greatly reduces the communication overhead between the prover and the verifier. We propose MARVELlous a family of cryptographic algorithms specifically designed for STARK efficiency. The family currently includes the block cipher Jarvis and the hash function Friday. The design of Jarvis is inspired by the design of Rijndael, better known as the AES. By doing so we create a cipher with similar properties to those of Rijndael which allows us to reuse the wide-trail strategy to argue the resistance of the design against differential and linear cryptanalysis and focus our efforts on resistance against algebraic attacks. Friday is a Merkle-Damgard based hash function instantiated with Jarvis as its compression function thus it inherits its security properties up to the birthday bound. Jarvis and Friday have been suggested to be used in the Ethereum protocol by Ben-Sasson in Ethereum's Devcon IV. In this paper, we instantiate versions of Jarvis offering 128, 160, 192 and 256-bit security (both state- and key-size) which are used to implement Friday. We warmly invite the community to study and assess the security of the designs.