Paper 2019/426

Design of Symmetric-Key Primitives for Advanced Cryptographic Protocols

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


While traditional symmetric algorithms 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 algorithms 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 oftentimes different from the considerations arising in the design of software- and hardware-oriented ciphers. 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 the Marvellous design strategy which provides a generic way to easily instantiate secure and efficient algorithms for this emerging domain. We then show two examples for families following this approach. These families --- 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), and Multi-Party Computation (MPC). These benchmarks show that our algorithms achieve a highly compact algebraic description, and thus benefit the advanced cryptographic protocols that employ them. Evidence is provided that this is the case also in real-world implementations.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in FSE 2020
VisionRescueMarvellousarithmetizationzero-knowledge proofSTARKR1CSMPCGröbner basissponge
Contact author(s)
siemen dhooghe @ esat kuleuven be
2021-02-19: last of 5 revisions
2019-04-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Abdelrahaman Aly and Tomer Ashur and Eli Ben-Sasson and Siemen Dhooghe and Alan Szepieniec},
      title = {Design of Symmetric-Key Primitives for Advanced Cryptographic Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2019/426},
      year = {2019},
      doi = {10.13154/tosc.v2020.i3.1-45},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.