search

emp-toolkit / emp-sh2pc

Semi-honest Two Party Computation Based on Garbled Circuits.
Other
76 stars 38 forks source link

Ideas on Interactive Garbled Circuits? #7

Closed weikengchen closed 7 years ago

weikengchen commented 7 years ago

What I am thinking about is Circuit ORAM in FlexSC, where the paths in different ORAMs in the recursive constructions, are sent inside to continue the operation.

This is an interactive protocol for GC-based computation.

When we need to output some data and input some data in the middle, we don't need to discard all the state information -- we can keep the most of existing gates.

In the test examples in emp-toolkit, it seems no such an example for interactive cases. Any idea on how to secure this?

Thanks!

(I am starting to implement something!)

wangxiao1254 commented 7 years ago

I believe you are talking about the support of reactive functionalities in 2PC. This is generally costly for malicious security but fairly straightforward for semi-honest security. Particularly, you want to be able to add new input bits and obtain partial output during the computation of a circuit.

In fact the above is already supported. For example, in https://github.com/emp-toolkit/emp-sh2pc/blob/master/test/bit.cpp#L7, it actually has multiple rounds. Line 16, 17 feed in new bits every iteration and line 18 reveals it.

Looking at emp from another aspect, it is actually naturally reactive, as in the following example

void test_millionare(int party, int number) {
   Integer a(32, number, ALICE); 
   Integer b(32, number, BOB); 
   Integer c = a*b; 
   cout << c.reveal(PUBLIC); 
   Integer d(32, number, BOB); 
   Integer e = a+d; 
}

Here a is the "state information" that is kept throughout the computation.

weikengchen commented 7 years ago

Thanks! That is a very good news to me.

Love emp-tool!

weikengchen commented 7 years ago

And also hope it compatible with online/offline :) Hopefully, there would be a PR this Friday if I am not underestimating the difficulty.

wangxiao1254 commented 7 years ago

Thanks! I think it is, assuming the circuit is known in the offline phase.

BTW for the online-offline setting, there is paper that might be relevant: https://eprint.iacr.org/2016/458.pdf.