Design of Symmetric-Key Primitives for Advanced Cryptographic Protocols

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

Research output: Contribution to journalArticleAcademicpeer-review

69 Citations (Scopus)
118 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)1-45
Number of pages45
JournalIACR Transactions on Symmetric Cryptology
Volume2020
Issue number3
DOIs
Publication statusPublished - 28 Sept 2020

Funding

This research was partly funded by StarkWare Industries Ltd., as part of an Ethereum Foundation grant activity. The first author was also supported by Research Projects Agency (DARPA) and Space and Naval Warfare Systems Center, Pacific (SSC Pacific) under contract No. N66001-15-C-4070. The second author was supported by the Research Council KU Leuven, C16/18/004 and by an FWO post-doctoral fellowship under Grant Number 12ZH420N. Author 4 is supported by a Ph.D. Fellowship from the Research Foundation - Flanders (FWO). Author 5 was supported by an IWT doctoral grant and by the Nervos Foundation. These supports are greatly appreciated. The authors would like to thank Vincent Rijmen and Daira Hopwood for their useful comments. Additionally, we want to thank the anonymous reviewers and Brice Minaud for sheparding the work. This research was partly funded by StarkWare Industries Ltd., as part of an Ethereum Foundation grant activity. The first author was also supported by Research Projects Agency (DARPA) and Space and Naval Warfare Systems Center, Pacific (SSC Pacific) under contract No. N66001-15-C-4070. The second author was supported by the Research Council KU Leuven, C16/18/004 and by an FWO post-doctoral fellowship under Grant Number 12ZH420N. Author 4 is supported by a Ph.D. Fellowship from the Research Foundation-Flanders (FWO). Author 5 was supported by an IWT doctoral grant and by the Nervos Foundation. These supports are greatly appreciated.

FundersFunder number
Ethereum Foundation
Nervos Foundation
Research Foundation Flanders
Research Foundation Flanders
StarkWare Industries Ltd.
Defense Advanced Research Projects Agency
Space and Naval Warfare Systems CommandN66001-15-C-4070
Defense Advanced Research Projects Agency
Fonds Wetenschappelijk Onderzoek12ZH420N
Agentschap voor Innovatie door Wetenschap en Technologie
Katholieke Universiteit LeuvenC16/18/004

    Keywords

    • Arithmetization
    • Gröbner basis
    • MPC
    • Marvellous
    • R1CS
    • Rescue
    • STARK
    • Vision
    • Zero-knowledge proof

    Fingerprint

    Dive into the research topics of 'Design of Symmetric-Key Primitives for Advanced Cryptographic Protocols'. Together they form a unique fingerprint.

    Cite this