Question on implementation of or_.

[zyl2016]

Hello, when I use mpc.or for bitwise OR. I find the result unexpected. It seems that mpc.or works only for 1-bit values. However, for mpc.and, I find the result works successfully. From #36, it seems that you have provided an implementation for bitwise OR with the full bit length. I want to ask whether it is feasible to change the implementation of or in runtime.py to the same with #36.

def or_(self, a, b):
    x = self.to_bits(a)
    y = self.to_bits(b)
    return self.from_bits(self.vector_sub(self.vector_add(x, y), self.and_(x, y))))

With this change, it will help me use bitwise OR and bitwise AND more conveniently. In addition, it seems that the '|' has been overloaded for secure integers with 1-bit, so the function of mpc.or and '|' looks repetitive. I think mpc.or should release this limitation just like mpc.and_.

[lschoe]

Well, the current implementations for mpc.and_() and mpc.or_() are efficient for secure binary field values. And the implementations for &and | are efficient assuming 1-bit secure integer values (0 or 1). The latter allows for writing things like (a < b) & (c < d) for secure integers a, b, c, d, and have this evaluated efficiently.

An extension foreseen for the somewhat near future is to add annotations for secure integers specifying publicly known intervals for the values. In the case of a Boolean value held in a secure integer, the interval would be {0, 1}, and values will remain in this interval when manipulated using Boolean operators. Simple use of annotations is already present in the implementation of secure fixed-point numbers, where the Boolean attribute integral keeps track of public knowledge if the fixed-point value happens to be integral (or maybe not); this allows for efficient use of Boolean fixed-point values (0.0 and 1.0) in the implementation of mpc.if_else() for example, avoiding superfluous secure truncations after secure multiplications.

For the time being you can subclass the secure integer type you're using, overriding __and__() and __or__() with what you're considering above. I think in your code for self.or_() the call to self.and_() should be replaced by self.schur_prod().

[zyl2016]

Thank you for your suggestion!

[zyl2016]

Hello again and sorry for disturbing you again. @lschoe I am struggling to implement the bitwise operation and I need some help.

Firstly, in #17, you mentioned that secure types for integers are much better for bit-oriented stuff. Following your suggestion, I have used AND, OR, XOR through to_bits and from_bits as expected. However, I cannot find a proper way to implement bitwise inversion. After the integer is converted to a vector, both mpc.invert and ~ cannot work on it. Would it be ok to just invert an integer a by -a-1?

Secondly, I do not have a good idea of how to use binary field properly. I defined a binary field with GF(2**32) through fld = mpc.SecFld(char=2, ext_deg=32 ,signed=True) With 'fld', I can implement all the bitwise operations easily, however, I do not find a way to convert it to 32-bit SecInt and print it out. Could you help me on this? By the way, I am curious about why mpc.SecFld(char=2, ext_deg=32) does not equal mpc.SecFld(order=2^32)

[lschoe]

Hi again!

To do the bitwise inversion, if you already got the individual bits in a list s, say, then you can just take 1-s[i] to invert these bits. But then converting this list back using mcp.from_bits() will not work as that function does not handle negative numbers yet (two's complement with a sign bit). This is a TODO. Your suggestion to use -a-1 is a good idea, especially if you want to start and end with a secure integer.

Conversions between secure binary fields and secure integers are not that easy and currently not supported. For this it is also not defined automatically what the conversion should do. For binary fields there are a lot of isomorphic representations.

The two binary fields that you mention are the same, I think:

>>> mpc.SecFld(char=2, ext_deg=32) is mpc.SecFld(order=2**32)
True

Also wondering, what are your goals with these binary operations?

[zyl2016]

Thank you for your detailed explanation of this question and sorry for occupying your time. I have confirmed that my mistake made me regard mpc.SecFld(char=2, ext_deg=32) as not equal to mpc.SecFld(order=2^32). I am trying some cryptographic implementation which includes binary operation. I used to regard bitwise inversion as a common operation, however, it turns out that it is very rarely used and can be replaced easily. Your advice is more than enough for my work