Martin R. Albrecht, Lorenzo Grassi, Leo Perrin, Sebastian Ramacher, Christian Rechberger, Dragos Rotaru, Arnab Roy and MarkusSchofnegger (2019)

Ecient PRP/PRFs are instrumental to the design of cryptographic protocols. We investigate the design of dedicated PRP/PRFs for three application areas – secure multiparty computation (MPC), ZKSNARK
and zero-knowledge (ZK) based PQ signature schemes. In particular, we explore a family of PRFs which are generalizations of the well-known Feistel design approach followed in a previously proposed
application speci c design – MiMC. Attributing to this approach we call our family of PRP/PRFs GMiMC. In MPC applications, our construction shows improvements (over MiMC) in throughput by a factor of more than 4 and simultaneously a 5-fold reduction of preprocessing e ort, albeit at the cost of a higher latency. Another use-case where MiMC outperforms other designs, in SNARK applications, our design GMiMCHash shows moderate improvement. Additionally, in this case our design bene ts from the exibility of using smaller (prime) elds. In the area of recently proposed ZK-based PQ signature schemes where MiMC was not competitive at all, our new design has 30 times smaller signature size than MiMC.

Read the full paper here