Abstract:
An embodiment of the present invention provides a method that minimizes the number of entries required in a garbled circuit associated with secure function evaluation of a given circuit. Exclusive OR (XOR) gates are evaluated in accordance with an embodiment of the present invention without the need of associated entries in the garbled table to yield minimal computational and communication effort. This improves the performance of SFE evaluation. Another embodiment of the present invention provides a method that replaces regular gates with more efficient constructions containing XOR gates in an implementation of a Universal Circuit, and circuits for integer addition and multiplication, thereby maximizing the performance improvement provided by the above.

Description:
BACKGROUND 
       [0001]    This invention relates to electronic transactions, and more specifically to secure function evaluation (SFE) techniques that provide privacy to the parties. This invention is especially, but not exclusively, suited to the SFE of functions implemented by circuits containing exclusive OR (XOR) gates. A Universal Circuit which contains many XOR gates can benefit from construction in accord with this invention. This invention is particularly, but not exclusively, suitable for evaluation of private functions. 
         [0002]    SFE implementations have been disclosed, e.g. see “Fairplay—A Secure Two-party Computation System” by D. Malkhi, N. Nisan, B. Pinkas and Y. Sella, USENIX 2004. Two-party general secure function evaluation (SFE) allows two parties to evaluate any function on their respective inputs x and y, while maintaining privacy of both x and y. SFE algorithms enable a variety of electronic transactions, previously impossible due to mutual mistrust of participants. Examples include auctions, contract signing, distributed database mining, etc. As computation and communication resources have increased, SFE has become practical. Fairplay is an implementation of generic two-party SFE with malicious players. It demonstrates the feasibility of SFE for many useful functions, represented as circuits of up to about 10 6  gates. Another example of a SFE protocol implementation is “Y Lindell, B Pinkas, N. Smart, ‘Implementing Two-party Computation Efficiently with Security Against Malicious Adversaries’, SCN 2008”. 
         [0003]    The SFE of private functions (PF-SFE) is an extension of SFE where the evaluated function is known only by one party and needs to be kept secret (i.e. everything besides the size, the number of inputs and the number of outputs is hidden from the other party). Examples of private functions include airport no-fly check function, credit evaluation function, background- and medical history checking function, etc. Full or even partial revelation of these functions opens vulnerabilities in the corresponding process, exploitable by dishonest participants (e.g. credit applicants), and is desired to be prevented. 
         [0000]    The problem of PF-SFE can be reduced to the “regular” SFE by evaluating a Universal Circuit (UC) instead of a predetermined circuit defining the evaluated function. A UC can be thought of as a program execution circuit capable of simulating any circuit C of certain size, given the description of C as input. Therefore, disclosing the UC does not reveal anything about C, except its size. The player holding C simply treats the description of C as an additional (private) input to the SFE. 
         [0004]    A PF-SFE can utilize computer simulated Y and X switching blocks as illustrated by  FIGS. 1 and 2 , respectively, interconnected to perform the required function logic for a programmable permutation network of a UC. The illustrated Y switching block of  FIG. 1  illustrates a single output that has a value selected to be one of its two inputs. The Y switching block is controlled to determine which of the two inputs is selected as the output. The X switching block of  FIG. 2  has two outputs and two inputs where one output receives one of the two inputs and the other output receives the other input. The X switching block is controlled to determine which of the first and second inputs appears on the respective first and second outputs. 
         [0005]    A known SFE implementation of a Y block uses a computer simulation of a 3-input gate (the two inputs of the Y block, and an additional control input) with a stored “garbled” table of 2 3 =8 encrypted table entries. A garbled table contains stored garbled values created using circuit input/output values that are transformed by mathematically applying secret values (garbled values) so that a person observing a garbled value cannot determine the corresponding circuit input/output values. Each garbled value may define a wire (input, output, control input) associated with a simulated circuit used to implement a universal circuit. Similarly, a known X block for use in an SFE implementation utilizes a computer simulation of two 3-input garbled gates (one for each of its two inputs) resulting in a garbled table of 2×2 3 =16 table entries. Typical UCs will employ a substantial number of such gates resulting in a large number of corresponding table entries. 
       SUMMARY 
       [0006]    It is an object of the present invention to provide a method of garbled circuit evaluation, where XOR gates are evaluated with minimal computational and communication effort by the evaluating parties. This improves the performance of SFE evaluation. 
         [0007]    It is an object of the present invention to provide an implementation of a UC supporting an SFE where X blocks and Y blocks utilize primarily XOR gates. This implementation, in conjunction with almost free processing of XOR gates which is part of an embodiment of this invention, minimizes the total number of garbled table entries needed to define the respective circuit blocks of the UC, which improves performance of SFE evaluation. 
         [0008]    An exemplary computer-implemented method generates a garbled circuit (e.g. a garbled Universal Circuit—UC), for secure function evaluation, having garbled tables with entries corresponding to inputs and outputs of gates of the universal circuit. In case of UC, the circuit is constructed using primarily XOR gates, each with first and second inputs, and an output. For each gate of the circuit, first garbled values w 0  are generated in the garbled table and supplied to the first inputs where the values w 0  are computed based on an actual value combined with a random number so that the values w 0  are random. A fixed global key R based on security parameter N (e.g. N=128 bits) is generated. Non-random second garbled values w 1  are generated in the garbled table and supplied to the second inputs where the values w 1  are derived based on an actual value exclusive OR&#39;ed with key R. Garbled values in the garbled table corresponding to the outputs of all possible circuit gates are generated (XOR gates do not need associated garbled tables, and this achieves savings in computation). The garbled tables are transmitted from one party to another party with whom the one party desires to exchange information via results produced by the universal circuit. The one party has private inputs P 1  and the other party has private inputs P 2 , where the private inputs are not known to the opposite party. 
         [0009]    Another embodiment is directed to generating a garbled table suited to minimize the number of entries needed in the table for each XOR gate used in a universal circuit. 
         [0010]    Further embodiments are directed to the construction of Y and X switching blocks that use primarily XOR gates, and are suited for use in universal circuits. 
     
    
     
       DESCRIPTION OF THE DRAWINGS 
         [0011]    Features of exemplary implementations of the invention will become apparent from the description, the claims, and the accompanying drawings in which: 
           [0012]      FIG. 1  is a block diagram of a Y switching block. 
           [0013]      FIG. 2  is a block diagram of an X switching block. 
           [0014]      FIG. 3  is a block diagram of a computing system suited for implementing embodiments of the present invention. 
           [0015]      FIG. 4  is a block diagram of an exemplary Y switching block in accordance with the present invention. 
           [0016]      FIG. 5  is a block diagram of an exemplary X switching block in accordance with the present invention. 
           [0017]      FIG. 6  is a block diagram of an exemplary practical implementation of the Y switching block of  FIG. 4 . 
           [0018]      FIG. 7  is a block diagram of an exemplary practical implementation of the X switching block of  FIG. 5 . 
           [0019]      FIG. 8  is a block diagram of an exemplary full adder module used to perform computer implemented mathematical calculations. 
           [0020]      FIG. 9  is a block diagram showing cascaded full adder modules suited to perform n-bit calculations. 
       
    
    
     DETAILED DESCRIPTION 
       [0021]    One aspect of the present invention resides in the recognition that known computer simulations of PF-SFE use circuits that require a substantial number of table entries to define each circuit. More specifically, independent random garble table entries have been required for each wire of a circuit in order to provide the desired security of the function. This causes the total number of table entries required to simulate an entire circuit to be very large. Embodiments of the present invention recognize that an exclusive OR construction can be used where the garbling used for one wire of a pair of wires can be computed based on the garbling used for the other wire in the pair by exclusive OR&#39;ing the garble used for the other wire with a random value R. This provides a substantial reduction of the number of entries in a garble table used in defining XOR gates, and also Y and X switching blocks in accordance with an embodiment of the present invention. This results in corresponding performance improvements. 
         [0022]      FIG. 1  shows a known Y switching block  10  that has two inputs and one output. The output either receives one of the inputs as shown in block  12  or receives the other of the inputs as shown in block  14 . The Y switching block  10  can be programmed to select the desired input to be transferred to its output. 
         [0023]      FIG. 2  shows a known X switching block  16  which has two inputs and two outputs. The respective inputs can be coupled straight through to a corresponding output as shown in block  18  or can be cross connected as shown in block  20 . The X switching block  16  can be programmed to select whether the inputs will be coupled straight through as in block  18  or cross connected as in block  20 . 
         [0024]    In  FIG. 3 , a computing system  22 , suitable for implementing a UC in accordance with the present invention, includes a microprocessor  24  that performs processes and tasks based on stored program instructions. It is supported by read-only memory (ROM)  26 , random access memory (RAM)  28  and nonvolatile data storage device  30 . As will be understood by those skilled in the art, data and stored program instructions in ROM  26  is typically utilized by microprocessor  24  to initialize and boot the computing apparatus. An application program, e.g. a program that controls the implementation of the UC including programming of individual blocks in the UC and a corresponding garbled table, can be stored in nonvolatile storage element  30 . At least active portions of the application program will be typically stored in RAM  28  for ready access and processing by microprocessor  24 . A variety of user inputs  32  such as a keyboard, keypad, and mouse can be utilized to input instructions, e.g. control the UC structure and its programming. User output devices  34  such as a display screen and/or printer provide a visual output, e.g. characters, that represent either information input by the user or information associated with an interim or final output of the UC. An input/output (I/O) module  36  provides a communication interface permitting microprocessor  24  to transmit and receive data with external nodes. Software that provides the basic circuit emulations for different types of gates is known in general. Such software can be utilized to construct UCs in accordance with the described embodiments of the present invention. 
         [0025]    Consider an SFE implementation of an XOR gate G i  having two input wires W a , W b  and output wire W c . Let N be a security parameter (e.g. N=128). Garble the wire values as follows and randomly choose: values as follows: Randomly choose w a   0 , w b   0 , Rε R  {0, 1} N . Set w c   0 =w a   0 ⊕w b   0 , and ∀iε{a, b, c}:w i   1 =w i   o ⊕R. It is easy to see that the garbled gate output is simply obtained by XORing garbled gate inputs: 
         [0000]      w c   0 =w a   0 ⊕w b   0 =(w a   0 ⊕R)⊕(w b   0 ⊕R=w a   1 ⊕w b   1    
         [0000]      w c   1 =w c   0 ⊕R=w a   0 ⊕(w b   0 ⊕R)=w a   0 ⊕w b   1 =(w a   0 ⊕R)⊕w b   0 =w a   1 ⊕w b   0 . 
         [0026]    Further, garblings w i   1  do not reveal the wire values they correspond to. 
         [0000]    As used herein, ε R  denotes uniform random sampling; ∥ denotes concatenation of bit strings, &lt;a, b&gt; denotes a vector with two components a and b, and its bit string representation is a∥b. W c =g(W a , W b ) denotes a 2-input gate G that computes function g: {0,1} 2 →{0,1} with input wires W a  and W b  and output wire W c . 
         [0027]    In the above exemplary exclusive OR construction, the garblings of the two values of each wire in the circuit must differ by the same value: 
         [0000]      ∀i:w i   1 =w i   0 ⊕R 
         [0000]    where R is a fixed global random number that need be set only once. This should be contrasted to previous garbled circuit constructions in which all garblings w i   j  were required to be chosen independently at random. 
         [0028]    Let C be a circuit. XOR gates are constructed as discussed herein. Further, each XOR-gate with n&gt;2 inputs can be replaced with n−1 two-input XOR gates. 
         [0029]    All other gates are implemented using standard (known) garbled tables. Namely, each gate with n inputs is assigned a table with 2 n  randomly permuted entries. Each entry is an encrypted garbling of the output wire, and garblings of the input wires serve as keys to decrypt the “right” output value. 
         [0030]    In the exemplary method described below, each garbling w=(k, p) consists of a key kε{0,1} N  and a permutation bit pε{0, 1}. The key k is used for decryption of the table entries, and p is used to select the entry for decryption. The two garblings w i   0 , w i   1  of each wire W i  are related as required by the XOR construction: 
         [0000]      Rε R {0,1} N , ∀i:w i   1 =         k i   1 , p i   1           =         k i   0 ⊕R, p i   0 ⊕1         , where w i   0 =         k i   0 , p i   0             
         [0000]    where RO is an implementation of a random oracle. In practice RO is efficiently implemented by a suitable cryptographic hash function, such as SHA1 or SHA256. 
         [0031]    The below algorithm describes steps of the garbled circuit construction in accord with an embodiment of the present invention. 
         [0000]    
       
         
               
             
               
               
             
               
               
               
             
               
               
             
               
               
               
             
               
               
               
             
               
               
               
             
               
               
               
             
               
               
             
               
               
               
             
           
               
                   
               
               
                 Algorithm 1. 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 1. 
                 Randomly choose global key offset R ε R  {0,1} N   
               
               
                 2. 
                 For each input wire W i  of C 
               
             
          
           
               
                   
                 (a) 
                 Randomly choose its garbled value w i   0  =          k i   0 ,p i   0            ε R  {0,1} N+1   
               
               
                   
                 (b) 
                 Set the other garbled output value w i   1  =          k i   1 ,p i   1            =          k i   0  ⊕ R,p i   0  ⊕ 1           
               
             
          
           
               
                 3. 
                 For each gate G i  of C in topological order 
               
             
          
           
               
                   
                 (a) 
                 label G(i) with its index: label(G i ) = i 
               
               
                   
                 (b) 
                 If G i  is an XOR-gate W c  = XOR(W a ,W b ) with garbled input values 
               
               
                   
                   
                 w a   0  =          k a   0 ,p a   0            ,w b   0  =           k b   0 ,p b   0            , w a   1  =          k a   1 ,p a   1            w b   1  =          k b   1 ,p b   1             
               
             
          
           
               
                   
                 i. 
                 Set garbled output value w c   0  =          k a   0  ⊕ k b   0 ,p a  ⊕ p b             
               
               
                   
                 ii. 
                 Set garbled output value w c   1  =          k a   0  ⊕ k b   0  ⊕ R,p a  ⊕ p b  ⊕ 1           
               
             
          
           
               
                   
                 (c) 
                 If G i  is a 2-input gate W c  = g i (W a ,W b ) with garbled input values 
               
               
                   
                   
                 w a   0  =          k a   0 ,p a   0            ,w b   0  =          k b   0 ,p b   0            , w a   1  =          k a   1 ,p a   1            w b   1  =          k b   1 ,p b   1             
               
             
          
           
               
                   
                 i. 
                 Randomly choose garbled output value w c   0  =           k c   0 ,p c   0             ε R  {0,1} N+1   
               
               
                   
                 ii. 
                 Set garbled output value w c   1  =          k c   1 ,p c   1            =          k c   0  ⊕ R,p c   0  ⊕ 1           
               
               
                   
                 iii. 
                 Create G i ’s garbled table. For each of 2 2  possible combinations of 
               
               
                   
                   
                 G i ’s input values v a ,v b  ε {0,1}, set 
               
               
                   
                   
                         e v     a     ,v     b    = H(k a   v     a   ||k b   v     b   ||i) ⊕ w c   g     i     (v     a     ,v     b   ) 
               
               
                   
                   
                 Sort entries e in the table by the input pointers, i.e. place entry e v   a ,v b   
               
               
                   
                   
                 in position          p a   v     a   ,p b   v     b               
               
             
          
           
               
                 4. 
                 For each circuit-output wire W i  (the output of gate G j ) with garblings 
               
               
                   
                 w i   0  =          k i   0 ,p i   0            w i   1  =          k i   1 ,p i   1             
               
             
          
           
               
                   
                 (a) 
                 Create garbled output table for both possible wire values v ε {0,1}. Set 
               
               
                   
                   
                          e v  = H(k i   v ||“out”||j) ⊕ v 
               
               
                   
                   
                 Sort entries e in the table by the input pointers, i.e. place entry e v  in 
               
               
                   
                   
                 position p i   v . (There is no conflict, since p i   1  = p i   0  ⊕ 1.) 
               
               
                   
                   
               
             
          
         
       
     
         [0032]    The following garbled circuit evaluation algorithm can be implemented by P 2 , i.e. the party to whom the function itself is unknown. P 2  obtains all garbled tables and the garbling of P 1 &#39;s input values from P 1 . 
         [0000]    
       
         
               
             
               
               
             
               
               
               
             
               
               
             
               
               
               
             
               
               
               
             
               
               
               
             
               
               
               
             
               
               
             
               
               
               
             
           
               
                   
               
               
                 Algorithm 2. 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 1. 
                 For each input wire W i  of C 
               
             
          
           
               
                   
                 (a) 
                 Receive corresponding garbled value w i  =          k i ,p i             
               
             
          
           
               
                 2. 
                 For each gate G i  (in the topological order given by Tabels) 
               
             
          
           
               
                   
                 (a) 
                 If G i  is an XOR-gate W c  = XOR(W a ,W b ) with garbled input values 
               
               
                   
                   
                 w a  =          k a ,p a            ,w b  =          k b ,p b             
               
             
          
           
               
                   
                 i. 
                 Compute garbled output value w c  =          k c ,p c            =          k a  ⊕ k b ,p a  ⊕ p b             
               
             
          
           
               
                   
                 (b) 
                 If G i  is a 2-input gate W c  = g i (W a ,W b ) with garbled input values w a  = 
               
               
                   
                   
                            k a ,p a            ,w b  =          k b ,p b             
               
             
          
           
               
                   
                 i. 
                 Decrypt garbled output value from garbled table entry e in position 
               
               
                   
                   
                            p a, p b            w c  =          k c, p c            = H(k a ||k b ||i) ⊕ e 
               
             
          
           
               
                 3. 
                 For each C’s output wire W i  (output of gate G j ) with garbling w i  =          k i ,p i             
               
             
          
           
               
                   
                 (a) 
                 Decrypt output value f i  form garbled output table entry e in row p i  : 
               
               
                   
                   
                 f i  = H(k i ||“out”||j) ⊕ e 
               
               
                   
                   
               
             
          
         
       
     
         [0033]    A garbled circuit based SFE protocol, such as described below can be used in conjunction with the above described construction (algorithm 1) and evaluation (algorithm 2) methods to implement a two-party SFE protocol. 
         [0000]    
       
         
               
             
               
               
             
               
               
               
             
               
               
             
           
               
                   
               
             
             
               
                 Inputs: P 1  has private input x =          x 1 ,..,x u     1              ε {0,1} u   1  and P 2  has private 
               
               
                 input y =           y 1 ,..,y u   2             ε {0,1} u     2   . 
               
               
                 Auxiliary input: A boolean acyclic circuit C such that ∀x ε {0,1} u     1   ,y ε 
               
               
                 {0,1} u     2   , it holds that C(x,y) = f(x,y), where f : {0,1} u     1   × {0,1} u     2    → 
               
               
                 {0,1} v . We require that C is such that if a circute-output wire leaves some 
               
               
                 gate G, then gate G has no other wires leading from it into other gates (i.e., 
               
               
                 no circut-output wire is also a gate-input wire). Likewise, a circuit-input 
               
               
                 wire that is also a circuit-output wire enters no gates. We also require that 
               
               
                 C is modified to contain no NOT-gates and all n-input XOR-gates with n &gt; 2 
               
               
                 replaced by 2-input XOR-gates 
               
               
                 The protocol: 
               
             
          
           
               
                 1. 
                 P 1  constructs the garbled circut using Algorithm          and sends it (i.e. the 
               
               
                   
                 garbled tables) to P 2 . 
               
               
                 2. 
                 Let W 1 ,..,W u     1    be the circuit input wires corresponding to x, and let 
               
               
                   
                 W u     1     +1 ,..,W u     1     +u     2    be the circuit input wires corresponding to y. Then 
               
             
          
           
               
                   
                 (a) 
                 P 1  sends P 2  the garbled values w 1   x     1   ,..,          . 
               
               
                   
                 (b) 
                 For every i ε {1,..,u 2 }, P 1 and P 2  execute a 1-out-of-2 oblivious 
               
               
                   
                   
                 transfer protocol, where P 1 ’s input is (k u     1     +i   0 ,k u     1     +i   1 ), and P 2 ’s input 
               
               
                   
                   
                 is y i  All u 2  OT instances can be run in parallel. 
               
             
          
           
               
                 3. 
                 P 2  now has the garbled tables and the garblings of circuit’s input wire. P 2   
               
               
                   
                 evaluates the garbled circuit, as described in Alg.          and outputs f(x,y). 
               
               
                   
               
             
          
         
       
     
         [0034]      FIG. 4  shows a block diagram of an exemplary Y switching block  40  in accordance with the present invention. One of two inputs (a 1 , a 2 ) is selected to appear at the output (b 1 ). An XOR function  42  receives both inputs and provides an output to a function  44 . An XOR function  46  receives a 1  as one input and the output of function  44  as its other input. The output of XOR function  46  consists of the output b 1  of this block. The function  44  may consist of a programmable function with two output states: a zero state in which its output is a “0” regardless of its inputs, and an identity state in which its output consists of its input. A more detailed explanation of how this Y switching block, as well as the counterpart X switching block, operates is provided below. 
         [0035]      FIG. 5  shows a block diagram of an exemplary X switching block  50  in accordance with the present invention. It has two inputs (a 1 , a 2 ) and two outputs (b 1 , b 2 ). It provides outputs as explained with regard to  FIG. 2 . Each of its inputs are provided as an input to XOR function  52  that provides its output to function  54  which provides the same functionality explained above with regard to function  44  of  FIG. 4 . XOR function  56  receives a 1  as one input with the other input being the output of function  54 . XOR function  58  receives a 2  as one input with the other input being the output of function  54 . The outputs of XOR functions  56  and  58  consist of the block outputs b 1  and b 2 , respectively. 
         [0036]      FIG. 6  is a schematic diagram of a practical gate implementation of a Y switching block  60  corresponding to the Y switching block  40  of  FIG. 4 . Gates  62  and  66  provide XOR functions and gate  64  is an AND gate in which one input receives a control input P, being either 0 or 1. 
         [0037]      FIG. 7  is a schematic diagram of a practical gate implementation of an X switching block  70  corresponding to the X switching block  50  of  FIG. 5 . Gates  72 ,  76  and  78  provide XOR functions and gate  74  is an AND gate in which one input receives a control input P, being either 0 or 1. 
         [0038]    The following describes the operation of the switching blocks shown in  FIGS. 4-7  in terms of computer simulated switching blocks forming part of an SFE utilizing garbled table entries. 
         [0000]    
       
         
               
             
               
               
               
             
           
               
                   
               
             
             
               
                  Let f : {0,1}            {0,1} be a function (implemented with two garbled 
               
               
                 table entries). We implement X- and Y-blocks as followes :  Y(a 1 ,a 2 ) = 
               
               
                 b 1  = f(a 1  ⊕ a 2 ) ⊕ a 1 ; X(a 1 ,a 2 ) = (b 1 ,b 2 ), where b 1  = f(a 1  ⊕ a 2 ) ⊕ a 1 , 
               
               
                 b 1  = f(a 1  ⊕ a 2 ) ⊕ a 2 . It is easy to see that setting f = f 0  to the zero function 
               
               
                 results in Y choosing left input, and X passing the inputs. Further, setting 
               
               
                 f = f id  to the identity function results in Y choosing the right 
               
               
                 input, and in X crossing its inputs: 
               
             
          
           
               
                 f = f 0  : 
                 b 1  = 0 ⊕ a 1  = a 1 ; 
                 b 2  = 0 ⊕ a 2  = a 2 . 
               
               
                 f = f id  : 
                 b 1  = (a 1  ⊕ a 2 ) ⊕ a 1  = a 2 ; 
                 b 2  = (a 1  ⊕ a 2 ) ⊕ a 2  = a 1 . 
               
               
                   
               
             
          
         
       
     
         [0039]    Switching from the implementation of an exemplary UC to the implementation of exemplary circuits computing integer addition and/or multiplication, we note that  FIG. 8  shows a full adder  80  and  FIG. 9  shows an adder for n-bit integers a, b composed from a chain of n full adder (FA) blocks  82 ,  84 ,  86 . Adders may be used in GC construction. The last FA block  86  can be replaced by a smaller half-adder block since there is no carry forward needed. A FA block  80  has as inputs a carry-in C i  from the previous FA block and the two input bits a i  and b i . It outputs two bits: carry-out c i+1  and sum s i . A straightforward known implementation of a FA uses two 3-input gates with 2×2 3 =16 encrypted table entries in a GC. We can compute s i  using “free” XOR gates and use only one 3-input gate with 2 3 =8 encrypted table entries to compute c i+1 . The size of a FA block, and hence that of an n-bit adder, is reduced by 50% in accordance with the embodiments of the present invention. 
         [0040]    As circuits for integer multiplication consist of bit-multipliers (2-input AND gates) and adders, the improved implementation of adders can directly be used to correspondingly improve integer-multiplication circuits. 
         [0041]    A similar construction is used to test equality of two n-bit integers a and b. Now, the computation of s i  is not needed and the carry bits are used as inequality flags. A simple known implementation uses two 2-input gates or one 3-input gate (each costs 8 encrypted table entries). Free XOR gate reduces the cost to that of one 2-input OR gate (4 encrypted table entries). Thus, the size of equality test block can be reduced by 50%. 
         [0042]    The apparatus in one example employs one or more computer readable signal-bearing tangible media. The computer-readable signal-bearing media store software, firmware and/or assembly language for performing one or more portions of one or more embodiments of the invention. The computer-readable signal-bearing medium for the apparatus in one example comprise one or more of a magnetic, electrical, optical, biological, and atomic data storage tangible medium. For example, the computer-readable signal-bearing medium may comprise floppy disks, magnetic tapes, CD-ROMs, DVD-ROMs, hard disk drives, and electronic memory. 
         [0043]    Although exemplary implementations of the invention have been depicted and described in detail herein, it will be apparent to those skilled in the art that various modifications, additions, substitutions, and the like can be made without departing from the spirit of the invention. 
         [0044]    The scope of the invention is defined in the following claims.