Implementing Rabbit

[Poppy22]

Hey Marcel,

So I am implementing rabbit as described in their paper: https://eprint.iacr.org/2021/119.pdf

I have 2 very similar implementations, one for ring, and one for field, but one is deterministic and correct, and the other one is flaky and wrong. Let me describe the set-up and my questions, maybe you can provide some insights.

I debugged it and it seems that LTB (in the paper, page 6) is flaky in the field case, but correct and consistent in the ring case, due to the edabit used. LTB compares a clear-text R with an edabit in binary format x and the the logic works at bit-level: finding the first different bit between the two numbers to compare, and based on that one deciding which is larger. So below I am providing info only about LTB and the code is the same for ring / field:

LTB code

def LTBits(self, R, x, BIT_SIZE):
        R_bits = cint.bit_decompose(R, BIT_SIZE)
        y = [x[i].bit_xor(R_bits[i]) for i in range(BIT_SIZE)]
        z = floatingpoint.PreOpL(floatingpoint.or_op, y[::-1])[::-1] + [0]
        w = [z[i] - z[i + 1] for i in range(BIT_SIZE)]
        return_value = 1 - sum((R_bits[i] & w[i]) for i in range(BIT_SIZE))
        return return_value
    

In the LTB, I added prints to check the value of the edabit (not pictured, but there are prints). What I noticed is that, the binary representation (x in the code above), is different from the bit decomposition of the arithmetic representation of the same edabit in the field case - and they should be the same, right?

Below I explain how I compile the code for the ring / field case, and what is the printed output when I debug the edabit value:

• first binary in the output: arithmetic edabit revealed, bit decomposed and printed bit by bit (computed as cint.bit_decompose(edabit_arith.reveal(), size=64))
• second binary in the out: the binary edabit printed bit by bit, each bit revealed

Ring implementation [working correctly]

How I compile (for ring)

/benchmarks/MP-SPDZ/compile.py -R 64 test.mpc
/benchmarks/MP-SPDZ/replicated-ring-party.x $1 test -h 172.18.0.2 -v

Output when debugging edabits

LTBits: edabit arithmetic revealed = 
0101000011001000010111001010101000111110101100100100101010101111
LTBits edabit bits revealed: x = 
0101000011001000010111001010101000111110101100100100101010101111

The edabit printed has the value -769467389925780726 when revealed from the arithmetic component.

(both binaries printed have 64 bits, as expected because we use 2^64 when compiling)

Field implementation [faulty]

How I compile (for fields)

/benchmarks/MP-SPDZ/compile.py test.mpc
/benchmarks/MP-SPDZ/replicated-field-party.x $1 test -P 9223372036855103489 -h 172.18.0.2 -v

Output when debugging edabits

LTBits: edabit arithmetic revealed = 
0110000110110000000000001111001001111010110010010110100111001010
LTBits edabit bits revealed: x = 
1110000110110000101000001111001001111010110010010110100111001011

(both binaries printed have 64 bits, as expected because the P chosen uses 64 bits)

The edabit printed has the value -3200208451938873979 (when revealed from arithmetic).

Questions / notes

• What am I missing in the field case? It's strange that it's working properly in the ring case. Am I compiling it wrong somehow?
• in the field case, the two binaries don't really show a pattern (not reverse, not because of a sign issue...)
• can provide code in the next 1-2 days if you also want to test it :D

[mkskeller]

This is probably due to wrap-around. The default 64-bit prime is relatively close to 2^63 but Rabbit requires it to be close to 2^64 such that a random 64-bit number is very likely to be smaller than the prime. This is currently not implemented so you need to generate it manually.

[Poppy22]

Ok, I will test with -P 18446744073709551557 which should be the largest prime smaller than 2^64. Thank you!

But... it also seems wrong that the binary and arithmetic parts of edabit give different numbers, when using the prime 9223372036855103489 - ignoring the rabbit logic, how are other functionalities working in MP-SPDZ when I use the smaller prime? :D

[Poppy22]

Update: yes, now with the larger prime, the field program also works fine, is correct and deterministic (and the printed edabits have the same bits!) Thank you!!!

[Poppy22]

Hello, I have a follow-up question here:

Here's my updated code (now giving a correct result for field and ring), link to code

In lines 75-76 I had to usebit_xor instead of + and - as the result was initially in {-1, 0, 1, 2}, instead of just {0, 1}.

I just wanted to double check, is there a way to achieve this while doing +, instead of xor? xor uses 1 virtual round, and plus would be local.

[mkskeller]

You cannot implement XOR in the arithmetic domain with addition and subtraction. The simplest way is a+b-2ab.

[IzuMi1217]

Hi Poppy22,

I'm really interested in your implementation of Rabbit. I wonder if it is possible to provide a quick start on running and testing the functionalities (as I am really new to MP-SPDZ). :)

Thank you so much!

[Poppy22]

Hi!

The code is on the branchdragos-rabbit: non_linear.py

Some running instructions (i.e. make sure you compile the correct branch):

git clone https://github.com/Poppy22/MP-SPDZ.git
cd MP-SPDZ
git checkout dragos-rabbit

make setup
make -j 8 tldr

make -j 8 dealer-ring-party.x
make -j 8 replicated-ring-party.x
make -j 8 replicated-field-party.x
...

for field

/benchmarks/MP-SPDZ/compile.py -Y -M code.mpc
/benchmarks/MP-SPDZ/replicated-field-party.x $1 code -lgp 104 -h 172.18.0.2 -v

for ring

/benchmarks/MP-SPDZ/compile.py -Y -M -R 64 code.mpc
/benchmarks/MP-SPDZ/replicated-ring-party.x $1 code -h 172.18.0.2 -v

I can provide more information -- I just wasn't sure how familiar you already are.

[IzuMi1217]

Hi Poppy22,

Thank you for your response! I found that there is a --comparison_rabbit flag, and I wonder if I need to add it in the compilation stage.

The entire compilation command looks like: ./compile.py test_rabbit.mpc --comparison_rabbit -Y -M

Do you think I need the --comparison_rabbit flag or stick to your example? Thank you!

[Poppy22]

Oh my bad, yes, you need to add the flag, else it will use comparison with truncation :D

[IzuMi1217]

Thank you for the clarification.

May I ask a follow-up question?

I am currently experimenting with 3PC using Rabbit. Essentially, all 3 parties have a share of the value s . (e.g. s1 + s2 + s3 = s; p1, p2, p3 has s1, s2, s3 respectively). I want to compare the original value s with a constant without revealing s to any party.

I tried something like below, but it needs to sum up the shares and then leak the original value.

s = sint.get_input_from(0) + sint.get_input_from(1) + sint.get_input_from(2)
target = 42
result = s < target
print_ln('result: %s', result.reveal())

May I have some instructions on how to write the script correctly? Thank you!