emp-toolkit / emp-ag2pc

Authenticated Garbling and Efficient Maliciously Secure Two-Party Computation
Other
22 stars 17 forks source link

Is only BOB getting the answer? #6

Closed lemire closed 5 years ago

lemire commented 5 years ago

Thanks for making the code and the paper available for this project.

For our own research, we are trying to build upon your work.

Following your instructions and examples, we run the following code on both BOB and ALICE's server.

        C2PC twopc(io, party, &cf);
        twopc.function_independent();
        twopc.function_dependent();
        twopc.online(in, out);

However, looking at ALICE's code path in the online function, we find that ALICE is not computing the circuit and getting the result of the circuit: only BOB does the computation and only BOB gets the answer. So, effectively, in ALICE's case, running the above code sequence, leads to have no result written to out.

Looking at some of the tests you published, it does appear that you check that the output matches your expectations, but only when the user is BOB. That is, we cannot find evidence that you expect ALICE to get the result of the circuit.


    if(party == BOB){ // why only BOB????????????
            string res = "";
        for(int i = 0; i < 160; ++i)
            res += (out[i]?"1":"0");
        cout << (res == hex_to_binary(string(out3))? "GOOD!":"BAD!")<<endl;
    }

Evidently, we could modify this code so that BOB sends the answer back to ALICE but this implies that ALICE trusts BOB. Another obvious fix is to run the exchange twice, flipping the role of BOB and ALICE, but that does not seem correct.

What if we wish that both parties get the output of the circuit? Could we modify your code, or the way we use your code, to get this desired result?

cc @owenkaser

wangxiao1254 commented 5 years ago

This is the intended behavior.

Two-output functionality can be done in two ways:

If you know the protocol and the code well, you can make it such that BOB sends back the garbled labels, where Alice can obtain the results. The fact that labels are sent will ensure authenticity.

If can also use a generic black-box transformation. See https://eprint.iacr.org/2008/049.pdf section 2.2

Xiao

On Tue, Mar 26, 2019 at 2:00 PM Daniel Lemire notifications@github.com wrote:

Thanks for making the code and the paper available for this project.

For our own research, we are trying to build upon your work.

Following your instructions and examples, we run the following code on both BOB and ALICE's server.

    C2PC twopc(io, party, &cf);
    twopc.function_independent();
    twopc.function_dependent();
    twopc.online(in, out);

However, looking at ALICE's code path in the online function https://github.com/emp-toolkit/emp-ag2pc/blob/master/emp-ag2pc/2pc.h#L312, we find that ALICE is not computing the circuit and getting the result of the circuit: only BOB does the computation and only BOB gets the answer. So, effectively, in ALICE's case, running the above code sequence, leads to have no result written to out.

Looking at some of the tests you published, it does appear that you check that the output matches your expectations, but only when the user is BOB. That is, we cannot find evidence that you expect ALICE to get the result of the circuit.

if(party == BOB){ // why only BOB???????????? string res = ""; for(int i = 0; i < 160; ++i) res += (out[i]?"1":"0"); cout << (res == hex_to_binary(string(out3))? "GOOD!":"BAD!")<<endl; }

Evidently, we could modify this code so that BOB sends the answer back to ALICE but this implies that ALICE trusts BOB. Another obvious fix is to run the exchange twice, flipping the role of BOB and ALICE, but that does not seem correct.

What if we wish that both parties get the output of the circuit https://en.wikipedia.org/wiki/Secure_multi-party_computation#Two-party_computation? Could we modify your code, or the way we use your code, to get this desired result?

cc @owenkaser https://github.com/owenkaser

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/emp-toolkit/emp-ag2pc/issues/6, or mute the thread https://github.com/notifications/unsubscribe-auth/ACKjCuWaYEGqhjeaX_VKwiFmT56n-Zowks5vamAwgaJpZM4cMGIH .

lemire commented 5 years ago

Thanks.

It seems that what you are saying is that BOB can send back data to ALICE from which ALICE can compute the answer and verify that it must be correct. But ALICE still has to trust that BOB will do so, right? Am I correct in thinking that this implies that BOB acts in good faith. If BOB interrupts the communication, then BOB can be left with the answer while ALICE has nothing.

Suppose that the result of the circuit is the winning numbers for tomorrow's lottery tickets. BOB gets the numbers, then stops communicating and buys the lottery ticket. ALICE has nothing.

So ALICE must trust that BOB will complete the protocol out of good faith.

wangxiao1254 commented 5 years ago

This is about fairness, which is impossible in the two-party setting as long as the function contains the XOR logic. See https://dl.acm.org/citation.cfm?doid=1374376.1374436

Xiao

On Tue, Mar 26, 2019 at 2:46 PM Daniel Lemire notifications@github.com wrote:

Thanks.

It seems that what you are saying is that BOB can send back data to ALICE from which ALICE can compute the answer and verify that it must be correct. But ALICE still has to trust that BOB will do so, right? Am I correct in thinking that this implies that BOB acts in good faith. If BOB interrupts the communication, then BOB can be left with the answer while ALICE has nothing.

Suppose that the result of the circuit is the winning numbers for tomorrow's lottery tickets. BOB gets the numbers, then stops communicating and buys the lottery ticket. ALICE has nothing.

So ALICE must trust that BOB will complete the protocol out of good faith.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/emp-toolkit/emp-ag2pc/issues/6#issuecomment-476794846, or mute the thread https://github.com/notifications/unsubscribe-auth/ACKjCo-pf0KEILf6pfqGetY9ihWnF_Mkks5vamsIgaJpZM4cMGIH .

lemire commented 5 years ago

@wangxiao1254 This clears things out for me. Thanks.

lemire commented 5 years ago

Closing.