Gröbner Basis Attack on STARK-Friendly Symmetric-Key Primitives: JARVIS, MiMC and GMiMCerf

Date

2022-01-01

Author

Kara, Gizem
Yayla, Oğuz

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

184
views

0
downloads

A number of arithmetization-oriented ciphers emerge for use in advanced cryptographic protocols such as secure multi-party computation (MPC), fully homomorphic en-cryption (FHE) and zero-knowledge proofs (ZK) in recent years. The standard block ciphers like AES and the hash functions SHA2/SHA3 are proved to be efficient in software and hardware but not optimal to use in this field, for this reason, new kind of cryptographic primitives were proposed recently. However, unlike traditional ones, there is no standard approach to design and analyze such block ciphers and the hash functions, therefore their security analysis needs to be done carefully. In 2018, StarkWare launched a public STARK-Friendly Hash (SFH) Challenge to select an efficient and secure hash function to be used within ZK-STARKs, transparent and post-quantum secure proof systems. The block cipher JARVIS is one of the first ciphers designed for STARK applications but, shortly after its publication, the cipher has been shown vulnerable to Gröbner basis attack. This paper aims to describe a Gröbner basis attack on new block ciphers, MiMC, GMiMCerf and the variants of JARVIS. We present the complexity of Gröbner basis attack on JARVIS-like ciphers. Then we give results from our experiments for the attack on reduced-round MiMC and a structure we found in the Gröbner basis attack for GMiMCerf•

Subject Keywords

Blockchain, GMiMC, Grobner Basis, Jarvis, MiMC, ZK-STARKs

URI

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85142785233&origin=inward
https://hdl.handle.net/11511/101392

DOI

https://doi.org/10.1109/iscturkey56345.2022.9931846

Conference Name

15th International Conference on Information Security and Cryptography, ISCTURKEY 2022

Collections

Graduate School of Applied Mathematics, Conference / Seminar

Suggestions

OpenMETU
Core

Gröbner basis attack on stark-friendly symmetric-key primitives: jarvis, mimc and gmimcerf Kara, Gizem; Doğanaksoy, Ali; Yayla, Oğuz; Department of Cryptography (2021-2-11) A number of arithmetization-oriented ciphers emerge for use in advanced cryptographic protocols such as secure multi-party computation (MPC), fully homomorphic encryption (FHE) and zero-knowledge proofs (ZK) in recent years. The standard block ciphers like AES and the hash functions SHA2/SHA3 are proved to be efficient in software and hardware but not optimal to use in this field, for this reason, new kind of cryptographic primitives proposed. However, unlike traditional ones, there is no standard approach ...
Truncated Impossible and Improbable Differential Analysis of ASCON Tezcan, Cihangir (2016-02-01) Ascon is an authenticated encryption algorithm which is recently qualified for the second-round of the Competition for Authenticated Encryption: Security, Applicability, and Robustness. So far, successful differential, differential-linear, and cube-like attacks on the reduced-round Ascon are provided. In this work, we provide the inverse of Ascon's linear layer in terms of rotations which can be used for constructing impossible differentials. We show that Ascon's S-box contains 35 undisturbed bits and we us...
Mutual correlation of NIST statistical randomness tests and comparison of their sensitivities on transformed sequences Doğanaksoy, Ali; Uğuz, Muhiddin; Akcengiz, Ziya (2017-01-01) Random sequences are widely used in many cryptographic applications and hence their generation is one of the main research areas in cryptography. Statistical randomness tests are introduced to detect the weaknesses or nonrandom characteristics that a sequence under consideration may have. In the literature, there exist various statistical randomness tests and test suites, defined as a collection of tests. An efficient test suite should consist of a number of uncorrelated statistical tests each of which meas...
Radix-3 NTT-Based Polynomial Multiplication for Lattice-Based Cryptography Hassan, Chenar Abdulla; Yayla, Oğuz; Department of Cryptography (2022-5-31) The lattice-based cryptography is considered as a strong candidate amongst many other proposed quantum-safe schemes for the currently deployed asymmetric cryptosystems that do not seem to stay secure when quantum computers come into play. Lattice-based algorithms possesses a time consuming operation of polynomial multiplication. As it is relatively the highest time consuming operation in lattice-based cryptosystems, one can obtain fast polynomial multiplication by using number theoretic transform (NTT). In ...
Analyzes of Block Recombination and Lazy Interpolation Methods and Their Applications to Saber Aksoy, Berkin; Cenk, Murat; Department of Cryptography (2022-2-28) Since the beginning of the National Institute of Standards and Technology (NIST), The Post-Quantum Cryptography (PQC) Standardization Process, efficient implementations of lattice-based algorithms have been studied extensively. Lattice-based NIST PQC finalists use polynomial or matrix-vector multiplications on the ring with type {Z}_{q}[x] / f(x). For convenient ring types, Number Theoretic Transform (NTT) can be used to perform multiplications as done in Crystals-KYBER among the finalists of the NIST PQC S...

Citation Formats

G. Kara and O. Yayla, “Gröbner Basis Attack on STARK-Friendly Symmetric-Key Primitives: JARVIS, MiMC and GMiMCerf,” presented at the 15th International Conference on Information Security and Cryptography, ISCTURKEY 2022, Ankara, Türkiye, 2022, Accessed: 00, 2023. [Online]. Available: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85142785233&origin=inward.