Issue with old Rabbit's LTS code

[Amaimaya]

Hi, I am trying to implement Rabbit's LTS function with MP-SPDZ and I am using a paper's code from 2021, which is supposed to work: https://d-nb.info/1265473811/34. However, it doesn't and each time I run it, the results are different.

`def LTBits(R_int, x): R_tmp = R_int

y = [sbit(0)] * len(x)
z = [sbit(0)] * len(x)
w = [sbit(0)] * len(x)
c = sint(0)

for i in range(len(x)):
    y[len(x) - 1 - i] = x[i].bit_xor(R_tmp & 2)
    R_tmp >>= 1

R_tmp = R_int

z = floatingpoint.PreOpL(floatingpoint.or_op, y)

w[0] = z[0]
for i in range(len(z) - 1):
    w[len(z) - 1 - i] = z[len(z) - 1 - i] - (z[len(z) - 2 - i])

for i in range(len(w)):
    c += sint(w[len(w) - 1 - i].bit_and(R_tmp % 2))
    R_tmp >>= 1

return (1 - c)

def LTS(x, y, M): k = program.bit_length r, r_bits = sint.get_edabit(k, True) r2, r_bits2 = sint.get_edabit(k, True)

b = (y + r).reveal()
a = (r2 - x).reveal()

T = a + b

w1 = LTBits(b, r_bits)
w2 = LTBits(a, r_bits2)
w3 = (T < b)

s = sbitint.bit_adder(r_bits, r_bits2, 0, True)

w4 = s.pop()
w5 = LTBits(T, s)

return w1 + w2 + w3 - sint(w4) - w5`

For example, if I run result = LTS(sint(1), sint(1), 8) print_ln("RESULT %s, ACTUAL %s", result.reveal(), 0) result = LTS(sint(1), sint(1), 8) print_ln("RESULT %s, ACTUAL %s", result.reveal(), 0) result = LTS(sint(1), sint(1), 8) print_ln("RESULT %s, ACTUAL %s", result.reveal(), 0) result = LTS(sint(1), sint(2), 8) print_ln("RESULT %s, ACTUAL %s", result.reveal(), 1) result = LTS(sint(1), sint(2), 8) print_ln("RESULT %s, ACTUAL %s", result.reveal(), 1) result = LTS(sint(1), sint(2), 8) print_ln("RESULT %s, ACTUAL %s", result.reveal(), 1)

The results are

RESULT 0, ACTUAL 0 RESULT 0, ACTUAL 0 RESULT 1, ACTUAL 0 RESULT 0, ACTUAL 1 RESULT 1, ACTUAL 1 RESULT 0, ACTUAL 1

I'm wondering whether any of the used functions—for example, bit_adder or get_edabit—have seen major changes since 2021 that have affected the outcomes.

[mkskeller]

I would check if the code works with an MP-SPDZ version from 2021. I would also contact the authors to ask their opinion.

[Amaimaya]

Ok, that's a good idea, thanks :)

[waamm]

In case this is helpful, I had a look at the Rabbit paper and code recently, and found two bugs:

(i) The LTS protocol in their paper actually computes x ≤ y instead of x < y, so perhaps you might want to consider LTSfix(x,y) := 1 - LTS(y,x) instead. (ii) Their LTBits code actually computes R > x rather than R < x.

(So I'm guessing that there are also bugs in the code you're using, and that they're not going to be resolved by switching to an older version of MP-SPDZ.) I wrote my own implementation of Rabbit recently, if you'd rather try that one.

Edit: This line might be incorrect: w3 = (T < b); see the code in the repository below.

[Amaimaya]

In case this is helpful, I had a look at the Rabbit paper and code recently, and found two bugs:

(i) The LTS protocol in their paper actually computes x ≤ y instead of x < y, so perhaps you might want to consider LTSfix(x,y) := 1 - LTS(y,x) instead. (ii) Their LTBits code actually computes R > x rather than R < x.

(So I'm guessing that there are also bugs in the code you're using, and that they're not going to be resolved by switching to an older version of MP-SPDZ.) I wrote my own implementation of Rabbit recently, if you'd rather try that one.

It would be so helpful! Where can I find it? :)

[waamm]

Sorry for the delay, I'm waiting on green light from my employer...

[Poppy22]

Hi, I'm also working on an MPC project where I'm currently looking into Rabbit. Thanks @waamm for pointing out the bugs ^^ I'll try to fix them myself, but if your implementation is open-sourced, please let me know.

[waamm]

It currently looks like I'll get permission to publish it on Monday, I'll post here when it happens.

[waamm]

You can find it in this repository.

Any comments would be more than welcome! Note that for most applications the Rabbit protocol might be slightly outperformed by the Möbius protocol in the same repository, which is based on this draft (a new one will appear later this month).

[Amaimaya]

@waamm thank you so much!!! I will let you know :)

[aaallami]

@waamm I am currently conducting research in the area of Multi-Party Computation (MPC) and have recently come across the Rabbit protocol. I found your shared Rabbit code particularly helpful, thanks for sharing it here.

I would be grateful if you could clarify the rationale behind the modification from w3=T<b to w3 = (T + HALF_PRIME) < (b + HALF_PRIME). Understanding the purpose of this change would be greatly beneficial.

Furthermore, I would appreciate any insights you might have on running the ResNet50 model based on the Rabbit paper. If there exists any code related to this implementation, I would be very interested in reviewing it.

Thank you for your time and assistance.

[waamm]

(1) My impression was that MP-SPDZ computes a comparison by realising $\mathbb{Z} / p \mathbb{Z}$ as the subset of integers ${- \lfloor p/2 \rfloor, \ldots , \lfloor p/2 \rfloor}$, whereas the Rabbit paper realises it as ${ 0, ..., p -1 }$ instead.

(2) I haven't seen such code in public, but the MP-SPDZ manual explains how to do SqueezeNet and I presume ResNet50 is analogous (it is in the same EzPC repository).

[aaallami]

@waamm, thank you so much for your response.

[Amaimaya]

@waamm Thank you very much for sharing your code. I have tested the Moebius protocol and noticed it does not function correctly when one of the parameters is negative. For instance, 10 < -20 yields 0, and when the second parameter is zero, 10 < 0 results in 1. Similarly, the Rabbit protocol also fails when one of the parameters is negative and when the first parameter is zero.

I was wondering if these protocols were not intended to work with negative numbers. Could you please clarify if this is the expected behavior?

[waamm]

I wrote the Rabbit code with the set ${0,\ldots ,m-1}$ in mind (and Möbius follows this), so $-20 \equiv m - 20$ which will be larger than $10$. If instead you'd like to compute inequalities in the set ${-m', \ldots, m-1-m'}$, then just shift the inputs of the comparison protocol by $m'$. Maybe @mkskeller has advice for what would be the appropriate default setting here?

Yes there's probably a problem with 0; I'll do some debugging tomorrow.

[mkskeller]

Doing this shift is standard practice, see for example: https://github.com/data61/MP-SPDZ/blob/28f8664fa1550defcae361ff62e711e71e5727fb/Compiler/comparison.py#L132 What's most appropriate depends on the circumstances. I tend to assume signed numbers because they appear frequently in tasks, and it's easier to just up the range if necessary rather spending a lot of thought on the signedness.

[waamm]

@Amaimaya I'm hoping it's correct now for the power-of-two modulus setting; I'll make more edits tomorrow.

@mkskeller Thanks! That sounds sensible.