LowMC in Bristol Fashion

[jacob14916]

Hi Marcel!
@GnarlyMshtep and I are working on implementing a protocol in MP-SPDZ that uses the LowMC cipher. Would it be possible to add LowMC to this repo? Do you know of any generators for LowMC in Bristol Fashion? We couldn't find any online.
Thanks,
Jacob

[mkskeller]

I'm not aware of any work in this direction, but @rdragos might know more. I'm happy to add LowMC to this repo. Please add a note that you put your contribution under the existing BSD license or public domain.

[rdragos]

I am not aware of any work as well, probably the closest thing you can get is a VHDL implementation of LowMC here. From what I can tell VHDL has been used to convert the floating point arithmetic to Bristol Circuits, perhaps you can use that as a starting point, see for more details how SCALE-MAMBA has done it here.

The CCS'16 paper on MPC friendly primitives contains code for evaluating LowMC for arithmetic circuits in F_{2^{128}}. I can link you to that if you want although it's old research code which is pretty hard to use.

[jacob14916]

I emailed Michael Zohner and he pointed me to this example from the ABY project which with one line of modification can output LowMC circuits in Bristol format. Unfortunately, it is only the first version of LowMC and so does not contain any of the security updates or optimizations that came after, all of which we need for our paper. We will likely end up generating our own circuits by modifying that example.

@rdragos, is the MPC friendly primitives paper this one? Reading through the paper, I encountered the Legendre PRF. It seems almost too good to be true - are there any qualifications to the recommendation to use it in the low latency setting that you included at the end of the paper? Would it be, for instance, looked down upon by the community as a non-standard assumption? Or if it is so good, why hadn't I heard of it before?

[rdragos]

@jacob14916, the reason you might not have heard about it is that it's relatively new (2016) and people prefer using a tradition blockcipher to encrypt their data locally (since that is faster on the client side) and then do the decryption inside MPC.

Usually people stick to the standards (in industry) when it comes for clients trying to encrypt their data.

As for the cryptanalysis of Legendre PRF the most recent paper (I know of) is by Beullens et al.. It was used further by Beullens and Delpech de Saint Guilhem for developing post quantum signatures.