aicis/fresco

"BigInteger divide by zero" Exception when explicitely performing a mod() operation

Closed this issue · 10 comments

Hi,
I was playing around with your library and implemented 2 relatively easy protocols with it. I kept getting a

java.lang.ArithmeticException: BigInteger divide by zero

Exception. I was actually trying out some operations that required modulus calculations. I provided the general modulus for the BasicNumericContext via CLI while also explicitly performing a mod() operation in the calculation through an AdvancedNumeric object.

Now to the issue itself: The mod implementation in KnownDivisorRemainder indirectly calls the div(dividend, divisor) method of the KnownDivisor class which performs a conversion of the divisor in its calculation through the convertRepresentation(modulus, modulusHalf, divisor) method. The first line in this method is:

BigInteger actual = b.mod(modulus);

where b is the divisor from the calling method buildComputation(). When the divisor is equal to the modulus from the BasicNumericContext, the converted divisor thus becomes zero, which subsequently leads to the beforementioned Exception. Maybe I'm missing the big picture, but I would not expect this to be correct behaviour when performing a modulus operation.

So maybe there needs to be a check on equality of the divisor and the modulus of the system in the convertRepresentation() method to avoid the following division exception or the modulus implementation of KnownDivisorRemainder needs to be adapted.

Best regards

Fresco version used: 1.1.2

I think you are right that this is a case of improper validation of the arguments given to the 'KnownDivisor'/'KnownDivisorRemainder' computations. This should obviously be fixed, so thank you for pointing that out.

There are some restrictions on the arguments you can use in these computation, but those restrictions are unfortunately not properly validated in the code and poorly documented. This is related or similar to issue #288. I am sorry, but I can not remember the concrete restrictions at the moment, but I will try to figure it out and let you know.

Of course if you just need to do the mod operation with a divisor that is equal to the modulus, then wouldn't that just be the identity function?

Since I only started to work with the library a day ago, I was trying out stuff to make my computations work. As I didn't (and still don't) have that much knowledge of the internal workings of Fresco, this was just a result of playing around. I now know how to set the modulus for the BasicNumericContext to get my computations reduced by this modulus, so this is not of much concern to me going forward with my project.

I just wanted to point out this problem as I thought it could potentially cause headaches for someone in the future.

Thank you for your fast response.

If it's ok I would like to amend a question. Is the modulus set in BasicNumericContext applied on operations in a predictable way or just on a method-by-method basis?
Because after going back to my original protocols, I noticed that the results are wrong. For smaller test values they would be right, if the modulus was actually applied to them. That's why i manually applied the mod operation in my protocols which lead to the exception in my initial message.

I just forgot about that, while trying to pin down the source of the zero division exception.

You are very welcome to ask questions 🙂.

All computations are done in Zp for modulus p. So reducing modulo p should not be needed.

To elaborate on my previous answer: For the arithmetic computation in FRESCO all computations should be in Zp for a modulus p. But of course if you getting errors there may be some bug there. If you can share what errors you are getting and what you are trying to compute, maybe we can figure it out. Depending on which output method you are using this could also be related to issue #272, which I am sorry to say we have not gotten around to fix yet.

I'm currently investigating using the dummy arithmetic protocol. At the moment I'm just testing the multiplication (and then automatic reduction mod p) for 160bit BigIntegers, so I hope that size is not a problem for the library. For testing purposes I'm using a small modulus (17) but the multiplication result mod p is off. As far as I can say for now is, that one of the parameters (already reduced by p) passed to DummyArithmeticMultProtocol.evaluate() is wrong. I'll let you know if I find a bug or if I'm just doing something wrong on my end.

But thanks for the clarification regarding the arithmetic computations.

I wonder if it could be a bug in the opening in the Dummy suite.

So, it was a mistake on my side regarding the check on the result after all. My protocols seem to work now with all BigIntegers of ~160bit size. The resulting BigInteger is however in signed form, as mentioned in the referenced issue. Thank you very much for your help.

You're welcome. Let us know if you have more questions. There is also the Gitter channel https://gitter.im/FRESCO-MPC/Lobby for short questions or discussions on FRESCO. I will close this issue if there is nothing further.

Yes, You can close the issue.