Cryptology ePrint Archive: Report 2019/426

Design of Symmetric-Key Primitives for Advanced Cryptographic Protocols

Abdelrahaman Aly and Tomer Ashur and Eli Ben-Sasson and Siemen Dhooghe and Alan Szepieniec

Abstract: While traditional symmetric primitives like AES and SHA3 are optimized for efficient hardware and software implementations, a range of emerging applications using advanced cryptographic protocols such as multi-party computation and zero-knowledge proofs require optimization with respect to a different metric: arithmetic complexity. In this paper we study the design of secure cryptographic primitives optimized to minimize this metric. We begin by identifying the differences in the design space between such arithmetization-oriented ciphers and traditional ones, with particular emphasis on the available tools, efficiency metrics, and relevant cryptanalysis. This discussion highlights a crucial point --- the considerations for designing arithmetization-oriented ciphers are fundamentally different from the considerations arising from traditional cipher design.

The natural next step is to identify sound principles to securely navigate this new terrain, and to materialize these principles into concrete designs. To this end, we present two families of arithmetization-oriented symmetric-key primitives. By motivating our design decisions at length with respect to the identified principles, we show that it is possible to design secure and efficient primitives for this emerging domain.

These primitives --- Vision and Rescue --- are benchmarked with respect to three use cases: the ZK-STARK proof system; proof systems based on Rank-One Constraint Satisfaction (R1CS) systems; and Multi-Party Computation (MPC). These benchmarks show that our ciphers achieve a highly compact algebraic description, and thus benefit the advanced cryptographic protocols that employ them.

Category / Keywords: secret-key cryptography / Vision, Rescue, Marvellous, arithmetization, zero-knowledge proof, STARK, R1CS, MPC, Gröbner basis, sponge

Date: received 25 Apr 2019, last revised 20 May 2019

Contact author: siemen dhooghe at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20190520:100450 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]