Incorrect behavior for `xor`

[samcowger]

Hey lschoe, I'm noticing some incorrect behavior for bitwise XOR on SecInts.

If I run the following program (via python p0.py -M 2, for example)...

from mpyc.runtime import mpc
async def main():
    await mpc.start()
    a0 = mpc.input(mpc.SecInt(8)(3))
    a1 = mpc.xor(a0[0], a0[1])
    print(await mpc.output(a1))
    await mpc.shutdown()
mpc.run(main())

...I see 6 as the output, rather than the expected 0.

Digging around a little, I see that xor is implemented as (apparently arithmetic) addition, which would account for this behavior.

I also see that __xor__ on SecureNumbers is "for now 1-bit only.". Do you have plans to relax this restriction?

Is there another operation I should be using to accomplish bitwise XOR on values of multiple bits?

Thanks!

[lschoe]

Hi @samcowger, the built-in support for secure bitwise operations is currently limited indeed.

So, for secure integers the assumption of 1-bit values is made, such that &, |, ^ can be used to do some Boolean arithmetic for logical expressions. The alternative to let &, |, ^ operate with the full bit length of the given secure integers is not included by default because these operations are quite expensive due to the use of bit decompositions.

For secure finite fields of characteristic 2, the operations &, |, ^ work on the binary coefficients of the polynomials representing the field elements because this is a common "use case", and these operations are actually quite cheap.

You can program &, |, ^ for secure integers for the full range by using the bit decomposition mpc.to_bits() together with mpc.from_bits() to go back. Like this:

x = mpc.to_bits(a)
y = mpc.to_bits(b)

z1 = mpc.schur_prod(x, y)   # bitwise and
z2 = mpc.vector_sub(mpc.vector_add(x, y), z1)  # bitwise or
z3 = mpc.vector_sub(z2, z1)  # bitwise xor

c1 = mpc.from_bits(z1)
c2 = mpc.from_bits(z2)
c3 = mpc.from_bits(z3)

This works and we use things like this inside MPyC to work bitwise with secure integers. For example, when computing the gcd of two secure integers, the bitwise or is used in function mpc.gcp2.