Skip to content
This repository has been archived by the owner on Oct 28, 2024. It is now read-only.

MiMC and Miyaguchi–Preneel OWF

Jump to bottom
HaRold edited this page Sep 25, 2019 · 5 revisions

One of the hashing functions used by EthSnarks is MiMC in combination with the Miyaguchi–Preneel one-way compression construct. MiMC is a cipher designed specifically to have low-multiplicative complexity and work efficiently with multi-party-computation and zkSNARKs, and the one-way compression construct allows it to be used as a hashing function.

Compression Function

Where E is the MiMC cipher. For the first message a fixed key (or IV) is used. For the second message the previous output is used as the key. At every round the message, key and encrypted output are added together.

The decision to use the Miyaguchi–Preneel one-way compression construct versus the Sponge construct described in the MiMC paper is because it is conceptually much simpler, the properties of the cipher are preserved, it doesn't operate on bits and doesn't require any changes to the size of the field to reach a specified security level.

Malleability and General Protections

In order to avoid block-level attacks different round constants must be used for every message in a sequence of messages and a different IV for every instance/purpose of the function. For example, for a variant of the function which compresses three messages into a single output, where it's purpose is for use as the leaf of a Merkle tree, it has a unique IV 'Merkle-Tree-Level-0' and then three sets of round constants.

MiMC Security

Specifically, for zkSNARKs on Ethereum the prime field the cipher operates over is: 21888242871839275222246405745257275088548364400416034343698204186575808495617. As per §4 Proposition 1 of the MiMC paper: Any monomial x^d is a permutation in the field Fp iff gcd(d, p − 1) = 1. In the case of the field used by EthSnarks the exponent of 5 is a permutation.

In §4.2 the security level of the cipher and the number of rounds required is derived from its resistance to two types of algebraic attacks:

  • Interpolation attack
  • GCD attack

Interpolation Attack

Interpolation attacks, introduced by Jakobsen and Knudsen [JK97], construct a polynomial corresponding to the encryption function without knowledge of the secret key. If an adversary can construct such a polynomial then for any given plaintext the corresponding cipher-text can be produced without knowledge of the secret key.

That is, for a polynomial of degree d, the Lagrange form can be constructed to recover the secret (or produce new ciphertexts) with d+1 plaintext/ciphertext pairs. The complexity of constructing the Lagrange form is O(d*log(d)). That means we can determine the number of rounds necessary to reach a desired security level, and evaluate the complexity of a given number of rounds using the following equations:

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617
e = 5                   # exponent which is a permutation
b = log2(p) / 8         # bytes per field element
r = log2(p) / log2(e)   # number of rounds
d = pow(e, r)           # degree of the polynomial
l = d * log(d)          # complexity of Lagrange form
m = 2**l * b            # memory required to store coefficients

In §4.2 "Additional security analysis for the case of restrictions on the complexity of the attack" the realisation that the realistic possibility of an interpolation attack is hindered by many factors, such as the amount of memory or storage required to store the coefficients of the polynomial, the number of plaintext/ciphertext pairs available and the time required to evaluate the Lagrange form of the polynomial.

The following table shows results with different numbers of rounds:

Rounds Security Level Memory Required
12 32 bits 128 gigabytes
24 60 bits 32768 petabytes
32 80 bits 34359738368 petabytes
53 129 bits ...
75 181 bits ...
107 255 bits ...

From this I conclude that 12 rounds may be sufficient in some specific cases but has known limits which are easily attainable, but with 24 rounds the real-world feasibility of an interpolation attack currently requires more resources than any possible gain.

GCD Attack

The complexity of the GCD attack is higher than that of the interpolation attack.

References

Clone this wiki locally