Determining the needed integer length to use with `-F`

[Mikerah]

In my program, I'm trying to test out the test vectors from here for point addition. The program runs. However, the output I get appears to be dependent on whatever I pass in to -F and such as is always changing. This makes it hard to debug my implementation as I can't directly match the test vectors. I execute my program with the following paramaters compile.py -P 21888242871839275222246405745257275088548364400416034343698204186575808495617 -F {integer length}. Any tips on how to choose the needed integer length in order to get a regular 256-bit output as one would expect for elliptic curve operations?

[mkskeller]

Which version/commit of MP-SPDZ are you using? I'm getting "Modulo only implemented for powers of two." when trying to compile the program.

[Mikerah]

I forgot to push my newest changes. I have since done that and it should compile.

[mkskeller]

It still doesn't because you try to print the secret values expected_x3 and expected_y3. I think the original issue is the following anyway: the inputs to the integer division are 254 bits long due to the domain and the fact that you multiply several 254-bit numbers (which of course wraps around the modulus), but the algorithm is restricted to ~64-bit division as you use a 254-bit domain. So whenever you the change the integer bit length, you will get different results because the numbers exceed the capabilities of the algorithm.

[Mikerah]

What do you mean that the algorithm is restricted to 64-bit division? Are you referring to MP-SPDZ's implementation of division over secret-shared integers?

[mkskeller]

Yes that what's I meant in this comment: https://github.com/data61/MP-SPDZ/issues/784#issuecomment-1347649356

[Mikerah]

Is this an inherent limitation in MP-SPDZ or of a particular algorithm in a paper?

[mkskeller]

No it's more the particular algorithm used. As mentioned in the Gitter chat, integer division is done via fixed-point division, so the numbers are expanded to fractional number and then rounded again. It's this expansion that requires a larger domain.

[Mikerah]

I see. Do you have any tips in order to get around this? I had the idea to instead use limbs to implement that elliptic curve. However, it's not common to do so with this particular elliptic curve as it was designed to fit within an a particular scalar field.

[mkskeller]

What is the common approach in cleartext then? Common processors don't support 256-bit integer division, so there must be some sort of reduction to 64-bit division?

[Mikerah]

This curve in particular was designed in such a way that it doesn't need a multi-limb implementation and that you can operate directly with 256-bit integers. The main use case is to be used within arithmetic circuits for zk-SNARKs in particular zk-SNARKs that use the bn254 curve.

[mkskeller]

I'm not sure what to make of this. My understanding is that common processors don't support 256-bit integers, so there is no way of directly operating with them.

[Mikerah]

Understood. Thank you for answering my questions, as always.