Consensys / gnark-crypto

gnark-crypto provides elliptic curve and pairing-based cryptography on BN, BLS12, BLS24 and BW6 curves. It also provides various algorithms (algebra, crypto) of particular interest to zero knowledge proof systems.
Apache License 2.0
495 stars 160 forks source link

Buffer in mimc should reason on p-digits, not block size #190

Closed ThomasPiellard closed 1 year ago

ThomasPiellard commented 2 years ago

In the mimc implementations, this for loop

for i := 0; i < nbChunks; i++ {
        copy(buffer[:], d.data[i*BlockSize:(i+1)*BlockSize])
        x.SetBytes(buffer[:])
        r := d.encrypt(x)
        d.h.Add(&r, &d.h).Add(&d.h, &x)
    }

might create collision, as the modulus is not BlockSize long but usually shorter.

What should be done is to take the value in the buffer, decompose it base p where p is the size of the snark field, and encrypt each digit one after the other, using the previous hash as initial state.

realuncle commented 2 years ago

@ThomasPiellard Any update regarding this issue?

ThomasPiellard commented 2 years ago

Hi @realuncle no currently the issue hasn't been fixed. I wonder if it's not better to directly enforce the Write() function in the mimc implementation to not accept anything which overflows r, the snark modulus. Otherwise if we pass a gigantic slice of []byte for instance it would force us to do the r-basis decomposition, which would be quite inefficient.