[Feature Request] MulTruncation

[mbkma]

A feature I miss in ABY is a mul_trunc (share *x, share *y, int k) function where the two l-bit shares x, y are multiplied as usual but in a larger ring (i.e. Z_{2^(l+1)} should do it) and then both Parties truncate their individual shares locally by k-bits. The returned value should then be again a l-bit value. Thanks for your consideration. (Would you accept pull requests in this regard?)

[dd23]

Can you explain why you would want the multiplication to be in a larger ring? I assume that k<l, but do you want to cut off k bits, or truncate the shares to k bits? Which sharing type are you considering?

This should be doable in Boolean sharing, but I think implementing it in arithmetic sharing will not be easy.

Of course we would accept pull requests.

[mbkma]

Thanks for your response.

Can you explain why you would want the multiplication to be in a larger ring?

Yes. I need to support decimal arithmetics in an integer ring. Consider the fixed-point multiplication of two decimal numbers x and y with at most d bits in the fractional part. I then convert x and y to integers by letting x'=2^d * x and y' = 2^d * y and multiply them to obtain z=x' * y'. Now z can have at most 2d bits in the fractional part. If d > l/2 this leads to overflow and therefore I need the multiplication to be in a ring Z_{2^(l+1)}.

but do you want to cut off k bits, or truncate the shares to k bits?

I want to cut off k bits (i.e. referring to my example above d bits).

Which sharing type are you considering?

Arithmetic sharing.

I think implementing it in arithmetic sharing will not be easy

Shouldn't it be possible that both parties locally truncate their shares (which are of type uint) by d bits in an arithmetic sharing (i.e. do a right shift by d bits)? It is proven, that the reconstructed value then is at most one bit off in the last significant bit compared to standard fixed-point arithmetic.

I currently emulate this functionality by using the BarrelRightShifterGate in my implementation, but this introduces a high overhead.