Secure function evaluation between semi-honest parties
View Patent ↗Methods and apparatus are provided for secure function evaluation between a semi-honest client and a semi-honest server using an information-theoretic version of garbled circuits (GC). An information-theoretic version of a garbled circuit C is sliced into a sequence of shallow circuits C 1 , . . . C n , that are evaluated. Consider any wire w j of C that is an output wire of C i , and is an input wire of C i+1 . When a slice C i is evaluated, C i 's 1-bit wire key for w j is computed by the evaluator, and then used, via oblivious transfer (OT), to obtain the wire key for the corresponding input wire of C i+1 . This process repeats until C's output wire keys are computed by the evaluator. The 1-bit wire keys of the output wires of the slice are randomly assigned to wire values.
1. A method for secure function evaluation between a client and a server, comprising:
obtaining a circuit, C, representing a function, ƒ;
preparing slices of said circuit, C, into a sequence of sub-circuits C 1 , . . . C l , wherein each of said sub-circuits C 1 , . . . C l comprises a fan-out-one circuit;
executing an oblivious transfer of keys for said sub-circuits C 1 , . . . C l , to said client for evaluation, wherein input keys of one or more of said sub-circuits C 1 , . . . C l , are based on output keys of a prior one of said sub-circuits C 1 , . . . C l , wherein at least one of said sub-circuits C i has an output wire w j that is encrypted using only a one bit wire key, wherein said one bit wire key is used via said oblivious transfer to obtain a wire key for a corresponding input wire of a next sub-circuit C i+1 ; and
sending one or more output translation tables to said client.
2. The method of claim 1 , wherein said step of preparing slices further comprises the steps of generating output secrets of a given sub-circuit C i , and obtaining corresponding input secrets.
3. The method of claim 2 , wherein said step of obtaining corresponding input secrets applies a Gate Evaluation Secret Sharing (GESS) sharing scheme.
4. The method of claim 2 , wherein said given sub-circuit C i , has input wires and output wires u i,j and wherein for each wire v i,j , said server S selects two random output garblings {tilde over (v)} i,j 0 ,{tilde over (v)} i,j 1 ε R {0,1} (conditioned on {tilde over (v)} i,j 0 ≠{tilde over (v)} i,j 1 ) and computes garblings for each input wire in said given sub-circuit C i .
5. The method of claim 1 , wherein said step of executing said oblivious transfer of keys comprises a transfer of garblings for secure function evaluation for said sub-circuit C 1 .
6. The method of claim 5 , wherein said transfer of garblings for secure function evaluation for said sub-circuit C 1 comprises said server S executing for each client input wire u 1,j representing bits of input x of said client C, a 1-out-of-2 oblivious transfer protocol, where S has input values ũ 1,j 0 ,ũ 1,j 1 , and said client C uses input x for said oblivious transfer.
7. The method of claim 5 , wherein said secure function evaluation garblings transfer for said sub-circuit C 1 comprises said server S sending to said client C for each server input wire u 1,j representing bits of input y of said server S, one of input values ũ 1,j 0 ,ũ 1,j 1 , corresponding to input bits of said server S.
8. The method of claim 1 , wherein said step of executing said oblivious transfer of keys for said sub-circuits C 2 , . . . C l , comprises performing said oblivious transfer with server input values (ũ i,j 0 ,ũ i,j 1 ), if {tilde over (v)} i−1,j 0 =0 and performing said oblivious transfer with server input values (ũ i,j 1 ,ũ i,j 0 ), if {tilde over (v)} i−1,j 0 =1.
9. A method for secure function evaluation between a client and a server, comprising:
executing an oblivious transfer of keys for a plurality of sub-circuits C 1 , . . . C l , from said server for evaluation, wherein said sub-circuits C 1 , . . . C l are a plurality of information-theoretic garblings of slices of a circuit, C, wherein each of said sub-circuits C 1 , . . . C l comprises a fan-out-one circuit, and wherein input keys of one or more of said sub-circuits C 1 , . . . C l , are based on output keys of a prior one of said sub-circuits C 1 , . . . C l , wherein at least one of said sub-circuits C i has an output wire w j that is encrypted using only a one bit wire key, wherein said one bit wire key is used via said oblivious transfer to obtain a wire key for a corresponding input wire of a next sub-circuit C i+1 ;
evaluating said sub-circuits C 1 , . . . C l using garbled input values to obtain garbled output values;
receiving one or more output translation tables from said server; and
generating a bit for each output wire of said circuit, C, corresponding to a wire secret obtained in evaluation of said sub-circuit C l .
10. The method of claim 9 , wherein said step of executing said oblivious transfer of keys for said plurality of sub-circuits C 1 , . . . C l , comprises a transfer of garblings for secure function evaluation for a sub-circuit C 1 .
11. The method of claim 9 , wherein said step of executing said oblivious transfer of keys for said sub-circuits C 2 , . . . C l , comprises performing said oblivious transfer with client input values {tilde over (v)}′ i−1,j , where {tilde over (v)}′ i−1,j comprises an output wire secret of a prior sub-circuit C i−1 .
12. A server system for secure function evaluation with a client, comprising:
a memory; and
at least one hardware device, coupled to the memory, operative to:
obtain a circuit, C, representing a function, ƒ;
prepare slices of said circuit, C, into a sequence of sub-circuits C 1 , . . . C l , wherein each of said sub-circuits C 1 , . . . C l comprises a fan-out-one circuit;
execute an oblivious transfer of keys for said sub-circuits C 1 , . . . C l , to said client for evaluation, wherein input keys of one or more of said sub-circuits C 1 , . . . C l , are based on output keys of a prior one of said sub-circuits C 1 , . . . C l , wherein at least one of said sub-circuits C i has an output wire w j that is encrypted using only a one bit wire key, wherein said one bit wire key is used via said oblivious transfer to obtain a wire key for a corresponding input wire of a next sub-circuit C i+1 ; and
send one or more output translation tables to said client.
13. The server system of claim 12 , wherein said slices are prepared by generating output secrets of a given sub-circuit C i , and obtaining corresponding input secrets.
14. The server system of claim 12 , wherein said oblivious transfer of keys comprises a transfer of garblings for secure function evaluation for said a sub-circuit C 1 .
15. The server system of claim 14 , wherein said transfer of garblings for secure function evaluation for said sub-circuit C 1 comprises said server system S executing for each client input wire u 1,j representing bits of input x of said client C, a 1-out-of-2 oblivious transfer protocol, where S has input values ũ 1,j 0 ,ũ 1,j 1 , and said client C uses input x for said oblivious transfer.
16. The server system of claim 14 , wherein said secure function evaluation garblings transfer for said sub-circuit C 1 comprises said server system S sending to said client C for each server input wire u 1,j representing bits of input y of said server system S, one of input values ũ 1,j 0 ,ũ 1,j 1 , corresponding to input bits of said server system S.
17. The server system of claim 12 , wherein said oblivious transfer of keys for said sub-circuits C 2 , . . . C l , comprises performing said oblivious transfer with server input values (ũ i,j 0 ,ũ i,j 1 ), if v i−1,j 0 =0 and performing said oblivious transfer with server input values (ũ i,j 1 ,ũ i,j 0 ), if v i−1,j 0 =1.
18. A client system for secure function evaluation with a server, comprising:
a memory; and
at least one hardware device, coupled to the memory, operative to:
execute an oblivious transfer of keys for a plurality of sub-circuits C 1 . . . C l , from said server for evaluation, wherein said sub-circuits C 1 , . . . C l are a plurality of information-theoretic garblings of slices of a circuit, C, wherein each of said sub-circuits C 1 , . . . C l comprises a fan-out-one circuit, and wherein input keys of one or more of said sub-circuits C 1 , . . . C l , are based on output keys of a prior one of said sub-circuits C 1 , . . . C l , wherein at least one of said sub-circuits C i has an output wire w j that is encrypted using only a one bit wire key, wherein said one bit wire key is used via said oblivious transfer to obtain a wire key for a corresponding input wire of a next sub-circuit C i+1 ;
evaluate said sub-circuits C 1 , . . . C l using garbled input values to obtain garbled output values;
receive one or more output translation tables from said server; and
generate a bit for each output wire of said circuit, C, corresponding to a wire secret obtained in evaluation of said sub-circuit C l .
19. The client system of claim 18 , wherein said step of executing said oblivious transfer of keys for said plurality of sub-circuits C 1 . . . C l , comprises a transfer of garblings for secure function evaluation for said sub-circuit C 1 .
20. The client system of claim 18 , wherein said step of executing said oblivious transfer of keys for said sub-circuits C 2 , . . . C l , comprises performing oblivious transfer with client input values {tilde over (v)}′ i−1,j , where {tilde over (v)}′ i−1,j comprises said output wire secret of a prior sub-circuit C i−1 .