Gröbner basis attack on stark-friendly symmetric-key primitives: jarvis, mimc and gmimcerf

Download

12626247.pdf

Date

2021-2-11

Author

Kara, Gizem

Metadata

Show full item record

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

Item Usage Stats

465
views

437
downloads

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 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 master thesis aims to describe a Gröbner basis attack on new block ciphers, MiMC, GMiMCerf (SFH candidates) and the variants of JARVIS. We present the complexity of Gröbner basis attack on JARVIS-like ciphers, results from our experiments for the attack on reduced-round MiMC and a structure we found in the Gröbner basis for GMiMCerf.

Subject Keywords

Gröbner basis, Jarvis, MiMC, GMiMC, Secure multi-party computation (MPC), ZK-STARKs

URI

https://hdl.handle.net/11511/89612

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

Gröbner Basis Attack on STARK-Friendly Symmetric-Key Primitives: JARVIS, MiMC and GMiMCerf Kara, Gizem; Yayla, Oğuz (2022-01-01) 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 sta...
An efficient RSA public key encryption scheme Aboud, Sattar J.; AL-Fayoumi, Mohammad A.; Al-Fayoumi, Mustafa; Jabbar, Haidar S. (2008-04-09) In this paper, we propose an efficient RSA public key encryption scheme, which is an improved version of original RSA scheme. The proposed RSA encryption scheme is based on linear group over the ring of integer mod a composite modulus n which is the product of two distinct prime numbers. In the proposed scheme the original message and the encrypted message are h x h square matrices with entities in z(n) indicated via l(h,z(n)). Since the original RSA Scheme is a block cipher in which the original message an...
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...
Faster characteristic three polynomial multiplication and its application to NTRU Prime decapsulation Yeniaras, Esra; Cenk, Murat (2022-01-01) Efficient computation of polynomial multiplication over characteristic three fields is required for post-quantum cryptographic applications which gain importance upon the recent advances in quantum computers. In this paper, we propose three new polynomial multiplication algorithms over F-3 and show that they are more efficient than the current state-of-the-art algorithms. We first examine through the well-known multiplication algorithms in F-3[x] including the Karatsuba 2-way and 3-way split formulas along ...
Analysis of Block Recombination and Lazy Interpolation Methods and Their Applications to Saber Aksoy, Berkin; Cenk, Murat (2022-01-01) Since the beginning of the National Institute of Standards and Technology (NIST), The Post-Quantum Cryptog-raphy (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 Zq [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 Standa...

Citation Formats

G. Kara, “Gröbner basis attack on stark-friendly symmetric-key primitives: jarvis, mimc and gmimcerf,” M.S. - Master of Science, Middle East Technical University, 2021.