Python implementation of the two-choice OT to GMW protocol

https://github.com/junyu33/GMW-python

implementation

2-out-of-1 Oblivious Transfer

First, we write the template for connecting Alice and Bob via socket:

• Alice

#!/usr/bin/python3
# alice.py
import socket

# Create a socket object
s = socket.socket()

# Define the port on which you want to connect
port = 12345

# Connect to the server on local computer
s.connect(('127.0.0.1', port))

# Send a message to Bob
s.send(b'Hello Bob!')

# Receive a message from Bob
data = s.recv(1024)
print('Received from Bob:', data.decode())

# Close the connection
s.close()

• Bob

#!/usr/bin/python3           
# bob.py
import socket

# Create a socket object
s = socket.socket()

# Define the port on which you want to listen
port = 12345

# Bind to the port
s.bind(('127.0.0.1', port))

# Put the socket into listening mode
s.listen(5)

# Wait for a connection from Alice
c, addr = s.accept()
print('Got connection from', addr)

# Receive a message from Alice
data = c.recv(1024)
print('Received from Alice:', data.decode())

# Send a message to Alice
c.send(b'Hello Alice!')

# Close the connection
c.close()

Then, since the socket waiting time is slightly lengthy, we shorten it to 2 seconds and package the socket initialization operation into a function:

# alice.py
def alice_init():
    # Create a socket object
    s = socket.socket()
    # help reuse the port immediately
    s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
    # set a timeout of 2 second
    s.settimeout(2)  
    # Define the port on which you want to connect
    port = 12345
    # Connect to the server on local computer
    s.connect(('127.0.0.1', port))
    return s

# bob.py
def bob_init():
    # Create a socket object
    s = socket.socket()
    # help reuse the port immediately
    s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
    # set a timeout of 2 second
    s.settimeout(2)  
    # Define the port on which you want to listen
    port = 12345
    # Bind to the port
    s.bind(('127.0.0.1', port))
    # Put the socket into listening mode
    s.listen(5)
    # Wait for a connection from Alice
    c, addr = s.accept()
    print('Got connection from', addr)
    return c

Next, we prepare to implement the 2-out-of-1 OT protocol. Clearly, the protocol taught by Professor Lan in class is not secure against semi-honest adversaries. Therefore, I implemented a secure version based on the hardness of solving the discrete logarithm problem, referring to this article:

Briefly describe the principle of the protocol as follows. We consider:

1. Alice possesses $v_0$, $v_1$, and keys $s,r_0,r_1$.
2. Bob possesses a value $i\in \{0,1\}$ and a key $k$. Bob wants to obtain $v_i$.
3. Alice and Bob agree in advance on $g\in {\mathbb{Z}}_p$, where $p$ is a large prime and $g$ is a primitive root modulo $p$.

The OT protocol can then be executed as follows:

1. Alice sends $g^s$ to Bob.
2. Since there is no efficient solution to the discrete logarithm problem, Bob cannot decipher $s$, but can generate based on $i$:

$$\begin{array}{r}{L}_i=\{\begin{array}{ll}{g}^k& \text{if }i=0\\ g^{s-k}& \text{if }i=1\end{array}\end{array}$$

3. Bob sends $L_i$ to Alice. Similarly, Alice cannot tell whether $g^k$ or $g^{s-k}$ was sent, so she cannot determine Bob's choice $i$.
4. Alice generates $C_0=(g^{r_0},L_i^{r_0}\oplus v_0),C_1=(g^{r_1},(g^s/L_i{)}^{r_1}\oplus v_1)$, where the outer parentheses denote tuples and $\oplus$ denotes bitwise XOR.
5. Alice sends $C_0,C_1$ to Bob. For the same reason, Bob cannot decipher $r_0,r_1$.
6. Bob decrypts $v_i$ in the following two cases (here, square brackets are similar to array indices):
   • When $i=0$, $C_0[0{]}^k\oplus C_0[1]=(g^{r_0}{)}^k\oplus L_i^{r_0}\oplus v_0=v_0$; Bob cannot decrypt $v_1$ because $C_1[1]=(g^s/L_i{)}^{r_1}\oplus v_1=g^{(s-k)r_1}\oplus v_1$, and Bob does not know $s,r_1$.
   • When $i=1$, $C_1[0{]}^k\oplus C_1[1]=(g^{r_1}{)}^k\oplus (g^s/L_i{)}^{r_1}\oplus v_1=(g^{r_1}{)}^k\oplus (g^k{)}^{r_1}\oplus v_1=v_1$; Bob cannot decrypt $v_0$ because $C_0[1]=(g^s/L_i{)}^{r_1}\oplus v_1=g^{(s-k)r_1}\oplus v_1$, and Bob does not know $s,r_1$.
   • Thus, Bob can only decrypt $v_i$ and cannot decrypt $v_{1-i}$.

# alice.py
# STEP 1: Alice -> Bob: gs = g**s
alice_send(alice_sock, pow(g, s, p))

# STEP 3: Bob -> Alice: Li
Li = alice_recv(alice_sock)

# Step 4: generate C0, C1
# C0 = (g**r0, Li**r0 ^ v0)
# C1 = (g**r1, (gs/Li)**r1 ^ v1)
C0 = (pow(g, r0, p), pow(Li, r0, p) ^ v0)
C1 = (pow(g, r1, p), pow(pow(g, s, p) * inv(Li, p) % p, r1, p) ^ v1)

# Step 5: Alice -> Bob: C0, C1
alice_send_json(alice_sock, json.dumps([C0, C1]))

# bob.py
# STEP 1: Alice -> Bob : g**s 
gs = bob_recv(bob_sock)

# STEP 2: generate Li = g**k when i = 0, g**(s-k) otherwise
Li = 0
if i == 0:
    Li = pow(g, k, p)
else:
    Li = gs * pow(g, -k, p) % p

# STEP 3: Bob -> Alice : Li
bob_send(bob_sock, Li)

# STEP 5: Alice -> Bob : C0, C1
C0C1 = alice_recv_json(bob_sock)
C0 = C0C1[0]
C1 = C0C1[1]

# STEP 6: Bob decrypt v_i
# if i = 0, v0 = C0[0] ** k ^ C0[1]
# if i = 1, v1 = C1[0] ** k ^ C1[1]
v = 0
if i == 0:
    v = pow(C0[0], k, p) ^ C0[1]
else:
    v = pow(C1[0], k, p) ^ C1[1]
print('v_' + str(i) + ' =', v)

Finally, to facilitate future code writing, we can object-orient the previous code:

class Alice_2in1_OT:
    # v0, v1 -> two numbers
    def __init__(self, p, g, v0, v1):
        self.p = p
        self.g = g
        self.s = random.randint(1, p-1)
        self.r0 = random.randint(1, p-1)
        self.r1 = random.randint(1, p-1)
        self.v0 = v0 
        self.v1 = v1
        self.sock = self.init_socket()

    def inv(self, x):
        return pow(x, -1, self.p)

    def init_socket(self):
        s = socket.socket()
        s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
        s.settimeout(2)
        port = 12345
        s.connect(('127.0.0.1', port))
        return s

    def send_number(self, number):
        self.sock.send(str(number).encode())

    def recv_number(self):
        return int(self.sock.recv(1024).decode())

    def send_json(self, data):
        self.sock.send(json.dumps(data).encode())

    def recv_json(self):
        return json.loads(self.sock.recv(1024).decode())

    def run_protocol(self):
        # STEP 1: Alice -> Bob: gs = g**s
        self.send_number(pow(self.g, self.s, self.p))
        
        # STEP 3: Bob -> Alice: Li
        Li = self.recv_number()

        # Step 4: generate C0, C1
        C0 = (pow(self.g, self.r0, self.p), pow(Li, self.r0, self.p) ^ self.v0)
        C1 = (pow(self.g, self.r1, self.p), pow(pow(self.g, self.s, self.p) * self.inv(Li) \
        % self.p, self.r1, self.p) ^ self.v1)

        # Step 5: Alice -> Bob: C0, C1
        self.send_json([C0, C1])

        # Close the connection
        self.sock.close()

class Bob_2in1_OT:
    # i -> which one to choose
    def __init__(self, p, g, i):
        self.p = p
        self.g = g
        self.i = i
        self.k = random.randint(1, p-1)
        self.sock = self.init_socket()

    def inv(self, x):
        return pow(x, -1, self.p)

    def init_socket(self):
        s = socket.socket()
        s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
        s.settimeout(2)
        port = 12345
        s.bind(('127.0.0.1', port))
        s.listen(5)
        c, addr = s.accept()
        print('Got connection from', addr)
        return c

    def send_number(self, number):
        self.sock.send(str(number).encode())

    def recv_number(self):
        return int(self.sock.recv(1024).decode())

    def send_json(self, data):
        self.sock.send(json.dumps(data).encode())

    def recv_json(self):
        return json.loads(self.sock.recv(1024).decode())

    def run_protocol(self):
        # STEP 1: Alice -> Bob : g**s 
        gs = self.recv_number()

        # STEP 2: generate Li = g**k when i = 0, g**(s-k) otherwise
        if self.i == 0:
            Li = pow(self.g, self.k, self.p)
        else:
            Li = gs * pow(self.g, -self.k, self.p) % self.p

        # STEP 3: Bob -> Alice : Li
        self.send_number(Li)

        # STEP 5: Alice -> Bob : C0, C1
        C0C1 = self.recv_json()
        C0 = C0C1[0]
        C1 = C0C1[1]

        # STEP 6: Bob decrypt v_i
        if self.i == 0:
            v = pow(C0[0], self.k, self.p) ^ C0[1]
        else:
            v = pow(C1[0], self.k, self.p) ^ C1[1]
        print('v_' + str(self.i) + ' =', v)

        # Close the connection
        self.sock.close()

2-out-of-1 → n-out-of-1 OT

We consider that Alice holds $x_1,\dots ,x_n\in \{0,1\}$, and Bob holds $i\in \{1,\dots ,n\}$. Through $O{T}_1^n$, Bob obtains $x_i$ without Alice learning $i$.

The $O{T}_1^n$ protocol consists of the following steps:

1. Alice generates $k_0=0$ and randomly generates $k_j\in \{0,1\}$ for $j=1,\dots ,n$.
2. Alice and Bob perform $n$ instances of $O{T}_1^2$. In the $j$-th instance, Alice provides $k_0\oplus \cdots \oplus k_{j-1}\oplus x_j$ and $k_j$. If $j=i$, Bob chooses the former; if $j\ne i$, Bob chooses the latter.
3. Bob uses the values $\{k_0,\dots ,k_{i-1}\}$ obtained from the first to the $(i-1)$-th $O{T}_1^2$, along with $k_0\oplus \cdots \oplus k_{i-1}\oplus x_i$ obtained from the $i$-th instance, to decrypt $x_i$.

Let's analyze the security of the above $O{T}_1^n$. Bob's security is directly inherited from the security of $O{T}_1^2$, meaning that $O{T}_1^2$ ensures Alice cannot determine whether Bob chose the first or second value in each round, so Alice cannot learn the true value of $i$. Alice's security can be argued by case analysis. Consider the case where Bob chooses the first value for the first time in the $i$-th round of $O{T}_1^2$. For $j<i$, Bob chooses $k_j$ in $O{T}_1^2$, so he gains no information about $x_j$. For $j>i$, Bob can at most obtain $x_j\oplus k_i\oplus \text{others}$, and since Bob does not know the randomly generated $k_i$ by Alice, he cannot learn $x_j$.

The time complexity of this implementation is $O(n)$.

According to the lecture notes at this link, we can relatively easily write code to extend 2-out-of-1 OT to n-out-of-1 OT. With the abstraction of 2-in-1, the implementation of n-in-1 becomes much simpler:

class Alice_nin1_OT:
    def __init__(self, n, x : list):
        self.n = n
        self.x = [0] # add a dummy value to make the index start from 1
        self.x.extend(x)
        self.k = [0]
        for i in range(self.n):
            self.k.append(random.randint(0, 1))

    def run_protocol(self):
        # alice and bob perform the 2-in-1 OT protocol for n times
        v0 = self.x[0] 
        for j in range(1, self.n + 1):
            # v0 = k0 xor k1 xor ... xor k_{j-1} xor x[j]
            v0 ^= self.k[j-1] ^ self.x[j-1] ^ self.x[j] 
            # v1 = k[j]
            v1 = self.k[j]

            alice = Alice_2in1_OT(p, g, v0, v1, 20000+j) # avoid port conflict
            alice.run_protocol()

class Bob_nin1_OT:
    def __init__(self, n, i):
        self.n = n
        self.i = i
    
    def run_protocol(self):
        # alice and bob perform the 2-in-1 OT protocol for n times
        k = [] 
        # if j == i, bob choose k0 xor k1 xor ... xor k_{j-1} xor x[j]
        # otherwise, bob choose kj
        for j in range(1, self.n + 1):
            if j == self.i:
                bob = Bob_2in1_OT(p, g, 0, 20000+j) 
                k.append(bob.run_protocol())
            else:
                bob = Bob_2in1_OT(p, g, 1, 20000+j)
                k.append(bob.run_protocol())
        
        # with a little calculation we know 
        # the xor sum of first i elements of k is x[i]
        xi = 0
        for j in range(0, self.i):
            xi ^= k[j]
        return xi

To be safe, I first tested performing 2-in-1 OT twice consecutively, which resulted in a socket connection-related error. The specific error is as follows:

~/Desktop/old_desktop/scu/新技术专题/code master !2                                 21:03:47 
> python3 alice.py                                                                           
Traceback (most recent call last):                                                           
  File "/run/media/junyu33/develop/tmp1/scu/新技术专题/code/alice.py", line 90, in <module>    
    alice = Alice_2in1_OT(p, g, 4, 0, 20100)   
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^   
  File "/run/media/junyu33/develop/tmp1/scu/新技术专题/code/alice.py", line 18, in __init__    
    self.sock = self.init_socket(self.port)    
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^    
  File "/run/media/junyu33/develop/tmp1/scu/新技术专题/code/alice.py", line 27, in init_socket
    s.connect(('127.0.0.1', port))             
ConnectionRefusedError: [Errno 111] Connection refused 

This, in turn, caused Bob to also report a timeout error:

~/Desktop/old_desktop/scu/新技术专题/code master !2                                    21:03:47                                                                                               
> python3 bob.py                                                                                                                                                                              
Got connection from ('127.0.0.1', 46132)                                                                                                                                                      
4                                                                                                                                                                                             
Traceback (most recent call last):                                                                                                                                                            
  File "/run/media/junyu33/develop/tmp1/scu/新技术专题/code/bob.py", line 105, in <module>                                                                                                    
    bob = Bob_2in1_OT(p, g, 0, 20000)                                                                                                                                                         
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^                                                                                                                                                         
  File "/run/media/junyu33/develop/tmp1/scu/新技术专题/code/bob.py", line 15, in __init__                                                                                                     
    self.sock = self.init_socket(self.port)                                                     
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^                                                     
  File "/run/media/junyu33/develop/tmp1/scu/新技术专题/code/bob.py", line 26, in init_socket    
    c, addr = s.accept()                                                                        
              ^^^^^^^^^^                                                                        
  File "/usr/lib/python3.11/socket.py", line 294, in accept                                     
    fd, addr = self._accept()                                                                   
               ^^^^^^^^^^^^^^                                                                   
TimeoutError: timed out   

I carefully observed the error messages and found that the first OT instance proceeded without issues. I suspect the problem arises because immediately after closing a socket connection, reopening it results in a refused connection (possibly due to a socket cooldown period (2s, defined in the __init__ method) not being completed before the next connection attempt). For convenience, I extracted the socket connection and passed it as a function parameter into the Alice_nin1_OT and Bob_nin1_OT classes, and removed the code that closes the socket connection in run_protocol(). This resolved the issue.

GMW Protocol

According to the lecture notes from the previous link, we can implement a simple secure multi-party computation protocol. The circuit $G$ selected here is the one that solves the millionaires' problem (if $a\ge b$, output $1$; otherwise, output $0$). The specific circuit implementation is as follows:

def AND(a, b):
    return a & b

def OR(a, b):
    return a | b

def NOT(a):
    return int(not a)

def G(bit1, bit2):
    not_bit1 = NOT(bit1)
    result = AND(not_bit1, bit2)
    return NOT(result)

We consider the most basic scenario: Alice and Bob each have a single-bit input $x,y\in \{0,1\}$, and they want to compute $w=G(x,y)$, where $G$ is a logic gate circuit. In this case, the GMW Protocol consists of the following steps:

1. Alice randomly generates $x_a\in \{0,1\}$ and sends $x_b=x\oplus x_a$ to Bob. We refer to $\{x_a,x_b\}$ as the shared value of $x$. Due to the randomness of $x_a$, Bob cannot decipher $x$.
2. Bob randomly generates $y_b\in \{0,1\}$ and sends $y_a=y\oplus y_b$ to Alice. Due to the randomness of $y_b$, Alice cannot decipher $y$.
3. Alice randomly generates $z_a\in \{0,1\}$ and enumerates all possible values of $f(x_b,y_b)=z_a\oplus G(x_a\oplus x_b,y_a\oplus y_b)$. Since $x_b,y_b\in \{0,1\}$, $f(x_b,y_b)$ has four possible values: $\{f(0,0),f(0,1),f(1,0),f(1,1)\}$.
4. Alice and Bob perform $O{T}_1^4$. Alice provides $\{f(0,0),f(0,1),f(1,0),f(1,1)\}$, and Bob provides the index $i$ corresponding to $(x_b,y_b)$. $O{T}_1^4$ ensures that Bob only obtains the final result $f(x_b,y_b)$, while Alice cannot learn $i$ and thus cannot deduce $x_b,y_b,f(x_b,y_b)$.
5. Bob sets $z_b=f(x_b,y_b)$.
6. Alice and Bob can reveal $z_a,z_b$ to obtain the true value of $z$. It is easy to verify that:

$$z_a\oplus z_b=z_a\oplus z_a\oplus G(x_a\oplus x_b,y_a\oplus y_b)=G(x_a\oplus x_b,y_a\oplus y_b)=G(x,y)=z$$

Following the above steps, we can write the specific implementation of the GMW protocol:

    def run_protocol(self):
        # step1: alice gen xa in [0, 1], xb = x xor xa, sned xb to bob
        xa = random.randint(0, 1)
        xb = self.x ^ xa
        self.send_number(xb)
        
        # step2: bob gen yb in [0, 1], ya = y xor yb, send ya to alice
        ya = self.recv_number()

        # step3: alice gen za in [0, 1], enum f(xb, yb) = za xor G(xa^xb, ya^yb)
        za = random.randint(0, 1)
        f00 = za ^ G(xa^0, ya^0)
        f01 = za ^ G(xa^0, ya^1)
        f10 = za ^ G(xa^1, ya^0)
        f11 = za ^ G(xa^1, ya^1)

        # step4: operate 4 in 1 OT with bob, 
        # alice provide f00 to f11, 
        # bob provide index according to xb*2+yb
        alice = Alice_nin1_OT(4, [f00, f01, f10, f11], self.sock)
        alice.run_protocol()

        # step5: bob send zb = f(xb, yb) to alice
        zb = self.recv_number()

        # step6: alice and bob reveal G(x, y) = za xor zb
        self.send_number(za)
        z = za ^ zb
        return z

    def run_protocol(self):
        # step1: alice gen xa in [0, 1], xb = x xor xa, sned xb to bob
        xb = self.recv_number()
        
        # step2: bob gen yb in [0, 1], ya = y xor yb, send ya to alice
        yb = random.randint(0, 1)
        ya = self.y ^ yb
        self.send_number(ya)

        # step4: operate 4 in 1 OT with bob, alice provide 
        # f00 to f11, bob provide index according to xb*2+yb
        i = xb*2 + yb + 1 # don't forget to add 1, it's 1-indexed
        bob = Bob_nin1_OT(4, i, self.sock)
        zb = bob.run_protocol()

        # step5: bob send zb = f(xb, yb) to alice
        self.send_number(zb)

        # step6: alice and bob reveal G(x, y) = za xor zb
        za = self.recv_number()
        z = za ^ zb
        return z

After testing, it runs successfully in one go. Thus, we have implemented a complete GMW protocol.

Improvements to the GMW Protocol

Of course, the current code may not seem sufficient in terms of workload for a major assignment. Therefore, I plan to extend this code to support comparisons of more bits and add addition functionality.

Multi-bit Comparison

First, I planned to compare numbers within the range of $256$. Based on the digital circuit knowledge I learned in the first semester of my sophomore year, I could vaguely recall the circuit implementation of a multi-bit comparator. Therefore, I wrote the following Python code:

def XOR(a, b):
    return OR(AND(a, NOT(b)), AND(NOT(a), b))

# Compare bit1 > bit2 per bit
def g_perbit(bit1, bit2):
    not_bit2 = NOT(bit2)
    return AND(bit1, not_bit2)

# Compare bit1 == bit2 per bit
def e_perbit(bit1, bit2):
    return NOT(XOR(bit1, bit2))

# Compare bit1 >= bit2 per bit
def ge_perbit(bit1, bit2):
    not_bit1 = NOT(bit1)
    result = AND(not_bit1, bit2)
    return NOT(result)

# little endian
def G_compare(x : list, y : list):
    result0 = ge_perbit(x[0], y[0])
    result1 = OR(g_perbit(x[1], y[1]), AND(e_perbit(x[1], y[1]), result0))
    result2 = OR(g_perbit(x[2], y[2]), AND(e_perbit(x[2], y[2]), result1))
    result3 = OR(g_perbit(x[3], y[3]), AND(e_perbit(x[3], y[3]), result2))
    result4 = OR(g_perbit(x[4], y[4]), AND(e_perbit(x[4], y[4]), result3))
    result5 = OR(g_perbit(x[5], y[5]), AND(e_perbit(x[5], y[5]), result4))
    result6 = OR(g_perbit(x[6], y[6]), AND(e_perbit(x[6], y[6]), result5))
    return OR(g_perbit(x[7], y[7]), AND(e_perbit(x[7], y[7]), result6))

At this point, there seemed to be no online reference materials for me to consult, so I had to modify the protocol myself to implement multi-bit comparison functionality. First, I needed to convert the input into the form of eight wires, represented here using a list:

    def number2list(self, number):
        res = []
        for i in range(comm_bit):
            res.append(number & 1)
            number >>= 1
        return res

Then I needed to call a single $O{T}_1^{65536}$:

        # alice.py
        f = []

        for possible_xb in range(256):
            for possible_yb in range(256):
                xa_xor_xb_list = self.number2list(xa^possible_xb)
                ya_xor_yb_list = self.number2list(ya^possible_yb)
                f.append(za ^ G_compare(xa_xor_xb_list, ya_xor_yb_list))

        # step4: operate 65536 in 1 OT with bob, alice provide f00 to f{255}{255}, 
        # bob provide index according to xb*256+yb
        alice = Alice_nin1_OT(65536, f, self.sock)
        alice.run_protocol()

And modify the initial random range of $x_a$ and $y_b$:

        # alice.py
        xa = random.randint(0, 255)

        # bob.py
        yb = random.randint(0, 255)

Experimental results showed that I was overly optimistic about Python's execution efficiency. After waiting for two minutes, there was still no output. Through a binary search, I found that for comparisons within the range $[0,31]$, Python's execution speed was acceptable, taking about 45 seconds.

Adding Modulo-32 Addition Functionality

In digital logic courses, we all learned the implementation of a full adder:

def sum_perbit(bit1, bit2, carry_in):
    result = XOR(bit1, XOR(bit2, carry_in))
    carry_out = OR(AND(bit1, bit2), AND(XOR(bit1, bit2), carry_in))
    return result, carry_out

Therefore, multi-bit full addition is also straightforward:

# little endian
def G_sum(x : list, y : list):
    result0, carry0 = sum_perbit(x[0], y[0], 0)
    result1, carry1 = sum_perbit(x[1], y[1], carry0)
    result2, carry2 = sum_perbit(x[2], y[2], carry1)
    result3, carry3 = sum_perbit(x[3], y[3], carry2)
    result4, carry4 = sum_perbit(x[4], y[4], carry3)
    return [result0, result1, result2, result3, result4]

Since the output is a list, we also need to implement a function at Alice's side to convert wire to a number:

    def list2number(self, l):
        res = 0
        for i in range(comm_bit):
            res += l[i] * (2**i)
        return res

Unfortunately, I initially had a bug in this function's implementation (specifically, I reversed the addition order, writing res <<= 1; res += l[i]), which caused me to debug for 20 minutes. I even thought for a while that the GMW protocol circuit couldn't implement addition, because XOR and addition don't satisfy the distributive law, but it turned out to be my own coding mistake. Sigh.

Based on modifying $x_a, y_a$, since the value of $G(x,y)$ now extends to $[0, 31]$, the value of $z_a$ should also be extended. For ease of modification, I defined the input bit count as comm_bit (which should now be $5$). The final protocol implementation on Alice's side is as follows, while Bob's code remains unchanged.

    def run_sum_protocol(self):
        # step1: alice gen xa in [0, 2**comm_bit-1], xb = x xor xa, sned xb to bob
        xa = random.randint(0, 2**comm_bit-1)
        xb = self.x ^ xa
        self.send_number(xb)
        
        # step2: bob gen yb in [0, 2**comm_bit-1], ya = y xor yb, send ya to alice
        ya = self.recv_number()

        # step3: alice gen za in [0, 1], enum f(xb, yb) = za xor G(xa^xb, ya^yb)
        za = random.randint(0, 2**comm_bit-1)

        f = []

        for possible_xb in range(2**comm_bit):
            for possible_yb in range(2**comm_bit):
                xa_xor_xb_list = self.number2list(xa^possible_xb)
                ya_xor_yb_list = self.number2list(ya^possible_yb)
                sum_list = G_sum(xa_xor_xb_list, ya_xor_yb_list)
                f.append(za ^ self.list2number(sum_list))

        # step4: operate 4**comm_bit in 1 OT with bob, alice provide f00 
        # to f{2**comm_bit-1}{2**comm_bit-1}, 
        # bob provide index according to xb*(2**comm_bit)+yb
        alice = Alice_nin1_OT(4**comm_bit, f, self.sock)
        alice.run_protocol()

        # step5: bob send zb = f(xb, yb) to alice
        zb = self.recv_number()

        # step6: alice and bob reveal G(x, y) = za xor zb
        self.send_number(za)
        z = za ^ zb
        return z

Thus, the entire GMW implementation is complete. The final code is provided below:

• gates

#!/usr/bin/python3           
# gates.py
def AND(a, b):
    return a & b

def OR(a, b):
    return a | b

def NOT(a):
    return int(not a)

def XOR(a, b):
    return OR(AND(a, NOT(b)), AND(NOT(a), b))

def g_perbit(bit1, bit2):
    not_bit2 = NOT(bit2)
    return AND(bit1, not_bit2)

def e_perbit(bit1, bit2):
    return NOT(XOR(bit1, bit2))

def ge_perbit(bit1, bit2):
    not_bit1 = NOT(bit1)
    result = AND(not_bit1, bit2)
    return NOT(result)


def sum_perbit(bit1, bit2, carry_in):
    result = XOR(bit1, XOR(bit2, carry_in))
    carry_out = OR(AND(bit1, bit2), AND(XOR(bit1, bit2), carry_in))
    return result, carry_out

# little endian
def G_compare(x : list, y : list):
    result0 = ge_perbit(x[0], y[0])
    result1 = OR(g_perbit(x[1], y[1]), AND(e_perbit(x[1], y[1]), result0))
    result2 = OR(g_perbit(x[2], y[2]), AND(e_perbit(x[2], y[2]), result1))
    result3 = OR(g_perbit(x[3], y[3]), AND(e_perbit(x[3], y[3]), result2))
    result4 = OR(g_perbit(x[4], y[4]), AND(e_perbit(x[4], y[4]), result3))
    #result5 = OR(g_perbit(x[5], y[5]), AND(e_perbit(x[5], y[5]), result4))
    #result6 = OR(g_perbit(x[6], y[6]), AND(e_perbit(x[6], y[6]), result5))
    #return OR(g_perbit(x[7], y[7]), AND(e_perbit(x[7], y[7]), result6))
    return result4

# little endian
def G_sum(x : list, y : list):
    result0, carry0 = sum_perbit(x[0], y[0], 0)
    result1, carry1 = sum_perbit(x[1], y[1], carry0)
    result2, carry2 = sum_perbit(x[2], y[2], carry1)
    result3, carry3 = sum_perbit(x[3], y[3], carry2)
    result4, carry4 = sum_perbit(x[4], y[4], carry3)
    return [result0, result1, result2, result3, result4]

• Alice

#!/usr/bin/python3
# alice.py
import socket
import json
import random
import sys
from gates import G_compare, G_sum

def init_socket(ip, port):
    s = socket.socket()
    s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
    s.settimeout(60)
    s.connect((ip, port))
    return s


class Alice_2in1_OT:
    def __init__(self, p, g, v0, v1, sock):
        self.p = p
        self.g = g
        self.s = random.randint(1, p-1)
        self.r0 = random.randint(1, p-1)
        self.r1 = random.randint(1, p-1)
        self.v0 = v0
        self.v1 = v1
        self.sock = sock

    def inv(self, x):
        return pow(x, -1, self.p)

    def send_number(self, number):
        self.sock.send(str(number).encode())

    def recv_number(self):
        return int(self.sock.recv(1024).decode())

    def send_json(self, data):
        self.sock.send(json.dumps(data).encode())

    def recv_json(self):
        return json.loads(self.sock.recv(1024).decode())

    def run_protocol(self):
        # STEP 1: Alice -> Bob: gs = g**s
        self.send_number(pow(self.g, self.s, self.p))

        # STEP 3: Bob -> Alice: Li
        Li = self.recv_number()

        # Step 4: generate C0, C1
        C0 = (pow(self.g, self.r0, self.p), pow(Li, self.r0, self.p) ^ self.v0)
        C1 = (pow(self.g, self.r1, self.p), pow(pow(self.g, self.s, self.p) * self.inv(Li) \
        % self.p, self.r1, self.p) ^ self.v1)

        # Step 5: Alice -> Bob: C0, C1
        self.send_json([C0, C1])


class Alice_nin1_OT:
    def __init__(self, n, x : list, sock):
        self.n = n
        self.x = [0] # add a dummy value to make the index start from 1
        self.x.extend(x)
        self.k = [0]
        for i in range(self.n):
            self.k.append(random.randint(0, 1))
        self.sock = sock

    def run_protocol(self):
        # alice and bob perform the 2-in-1 OT protocol for n times
        v0 = self.x[0] 
        for j in range(1, self.n + 1):
            # v0 = k0 xor k1 xor ... xor k_{j-1} xor x[j]
            v0 ^= self.k[j-1] ^ self.x[j-1] ^ self.x[j] 
            # v1 = k[j]
            v1 = self.k[j]

            alice = Alice_2in1_OT(p, g, v0, v1, self.sock) # avoid port conflict
            alice.run_protocol()


class Alice_GMW:
    def __init__(self, x, sock):
        self.x = x
        self.sock = sock

    def send_number(self, number):
        self.sock.send(str(number).encode())

    def recv_number(self):
        return int(self.sock.recv(1024).decode())

    def number2list(self, number):
        res = []
        for i in range(comm_bit):
            res.append(number & 1)
            number >>= 1
        return res

    def list2number(self, l):
        res = 0
        for i in range(comm_bit):
            res += l[i] * (2**i)
        return res

    def run_protocol(self):
        # step1: alice gen xa in [0, 2**comm_bit-1], xb = x xor xa, sned xb to bob
        xa = random.randint(0, 2**comm_bit-1)
        xb = self.x ^ xa
        self.send_number(xb)
        
        # step2: bob gen yb in [0, 2**comm_bit-1], ya = y xor yb, send ya to alice
        ya = self.recv_number()

        # step3: alice gen za in [0, 1], enum f(xb, yb) = za xor G(xa^xb, ya^yb)
        za = random.randint(0, 1)

        f = []

        for possible_xb in range(2**comm_bit):
            for possible_yb in range(2**comm_bit):
                xa_xor_xb_list = self.number2list(xa^possible_xb)
                ya_xor_yb_list = self.number2list(ya^possible_yb)
                f.append(za ^ G_compare(xa_xor_xb_list, ya_xor_yb_list))

        # step4: operate 4**comm_bit in 1 OT with bob, 
        # alice provide f00 to f{2**comm_bit-1}{2**comm_bit-1}, 
        # bob provide index according to xb*(2**comm_bit)+yb
        alice = Alice_nin1_OT(4**comm_bit, f, self.sock)
        alice.run_protocol()

        # step5: bob send zb = f(xb, yb) to alice
        zb = self.recv_number()

        # step6: alice and bob reveal G(x, y) = za xor zb
        self.send_number(za)
        z = za ^ zb
        return z

    def run_sum_protocol(self):
        # step1: alice gen xa in [0, 2**comm_bit-1], xb = x xor xa, sned xb to bob
        xa = random.randint(0, 2**comm_bit-1)
        xb = self.x ^ xa
        self.send_number(xb)
        
        # step2: bob gen yb in [0, 2**comm_bit-1], ya = y xor yb, send ya to alice
        ya = self.recv_number()

        # step3: alice gen za in [0, 1], enum f(xb, yb) = za xor G(xa^xb, ya^yb)
        za = random.randint(0, 2**comm_bit-1)

        f = []

        for possible_xb in range(2**comm_bit):
            for possible_yb in range(2**comm_bit):
                xa_xor_xb_list = self.number2list(xa^possible_xb)
                ya_xor_yb_list = self.number2list(ya^possible_yb)
                sum_list = G_sum(xa_xor_xb_list, ya_xor_yb_list)
                f.append(za ^ self.list2number(sum_list))

        # step4: operate 4**comm_bit in 1 OT with bob, 
        # alice provide f00 to f{2**comm_bit-1}{2**comm_bit-1}, 
        # bob provide index according to xb*(2**comm_bit)+yb
        alice = Alice_nin1_OT(4**comm_bit, f, self.sock)
        alice.run_protocol()

        # step5: bob send zb = f(xb, yb) to alice
        zb = self.recv_number()

        # step6: alice and bob reveal G(x, y) = za xor zb
        self.send_number(za)
        z = za ^ zb
        return z


if __name__ == '__main__':
    if len(sys.argv) < 3:
        print('Usage: python3 alice.py <mode> <x> [<ip of bob>] [<port>]')
        exit(1)

    mode = sys.argv[1]
    x = int(sys.argv[2])
    port = 12345
    if len(sys.argv) >= 4:
        ip = sys.argv[3]
        if len(sys.argv) >= 5:
            port = int(sys.argv[4])
    else:
        ip = '127.0.0.1'
    sock = init_socket(ip, port)

    # Define the prime number p and generator g
    p = 998244353
    g = 3
    comm_bit = 5


    Alice = Alice_GMW(x, sock)
    if mode == 'c': 
        res = Alice.run_protocol()
    elif mode == 'a':
        res = Alice.run_sum_protocol()
    else:
        print('mode error')
        exit(1)
    print('result from Alice: G(x, y) =', res)
    sock.close()

• Bob

```python
#!/usr/bin/python3           
# bob.py
import socket
import random
import json
import sys

def init_socket(ip, port):
    s = socket.socket()
    s.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
    s.settimeout(2)
    s.bind((ip, port))
    s.listen(5)
    c, addr = s.accept()
    print('Got connection from', addr)
    return c


class Bob_2in1_OT:
    def __init__(self, p, g, i, sock):
        self.p = p
        self.g = g
        self.i = i
        self.k = random.randint(1, p-1)
        self.sock = sock

    def inv(self, x):
        return pow(x, -1, self.p)

    def send_number(self, number):
        self.sock.send(str(number).encode())

    def recv_number(self):
        return int(self.sock.recv(1024).decode())

    def send_json(self, data):
        self.sock.send(json.dumps(data).encode())

    def recv_json(self):
        return json.loads(self.sock.recv(1024).decode())

    def run_protocol(self):
        # STEP 1: Alice -> Bob : g**s 
        gs = self.recv_number()

        # STEP 2: generate Li = g**k when i = 0, g**(s-k) otherwise
        if self.i == 0:
            Li = pow(self.g, self.k, self.p)
        else:
            Li = gs * pow(self.g, -self.k, self.p) % self.p

        # STEP 3: Bob -> Alice : Li
        self.send_number(Li)

        # STEP 5: Alice -> Bob : C0, C1
        C0C1 = self.recv_json()
        C0 = C0C1[0]
        C1 = C0C1[1]

        # STEP 6: Bob decrypt v_i
        if self.i == 0:
            v = pow(C0[0], self.k, self.p) ^ C0[1]
        else:
            v = pow(C1[0], self.k, self.p) ^ C1[1]
        # print('v_' + str(self.i) + ' =', v)
        return v

class Bob_nin1_OT:
    def __init__(self, n, i, sock):
        self.n = n
        self.i = i
        self.sock = sock
    
    def run_protocol(self):
        # alice and bob perform the 2-in-1 OT protocol for n times
        k = [] 
        # if j == i, bob choose k0 xor k1 xor ... xor k_{j-1} xor x[j]
        # otherwise, bob choose kj
        for j in range(1, self.n + 1):
            if j == self.i:
                bob = Bob_2in1_OT(p, g, 0, self.sock) 
                k.append(bob.run_protocol())
            else:
                bob = Bob_2in1_OT(p, g, 1, self.sock)
                k.append(bob.run_protocol())
        
        # with a little calculation we know 
        # the xor sum of first i elements of k is x[i]
        xi = 0
        for j in range(0, self.i):
            xi ^= k[j]
        return xi

class Bob_GMW:
    def __init__(self, y, sock):
        self.y = y
        self.sock = sock

    def send_number(self, number):
        self.sock.send(str(number).encode())

    def recv_number(self):
        return int(self.sock.recv(1024).decode())

    def run_protocol(self):
        # step1: alice gen xa in [0, 2**comm_bit-1], xb = x xor xa, sned xb to bob
        xb = self.recv_number()
        
        # step2: bob gen yb in [0, 2**comm_bit-1], ya = y xor yb, send ya to alice
        yb = random.randint(0, 2**comm_bit-1)
        ya = self.y ^ yb
        self.send_number(ya)

        # step4: operate 4**comm_bit in 1 OT with bob,
        # alice provide f00 to f{2**comm_bit-1}{2**comm_bit-1}, 
        # bob provide index according to xb*(2**comm_bit)+yb
        i = xb*(2**comm_bit) + yb + 1 # don't forget to add 1, it's 1-indexed
        bob = Bob_nin1_OT(4**comm_bit, i, self.sock)
        zb = bob.run_protocol()

        # step5: bob send zb = f(xb, yb) to alice
        self.send_number(zb)

        # step6: alice and bob reveal G(x, y) = za xor zb
        za = self.recv_number()
        z = za ^ zb
        return z

        
if __name__ == '__main__':
    if len(sys.argv) < 3:
        print('Usage: python3 bob.py <mode> <y> [<ip of bob>] [<port>]')
        sys.exit(1)
    
    mode = sys.argv[1]
    y = int(sys.argv[2])
    port = 12345
    if len(sys.argv) >= 4:
        ip = sys.argv[3]
        if len(sys.argv) >= 5:
            port = int(sys.argv[4])
    else:
        ip = '127.0.0.1'
    sock = init_socket(ip, port)
    
    # Define the prime number p and generator g
    p = 998244353
    g = 3
    comm_bit = 5


    Bob = Bob_GMW(y, sock)
    res = Bob.run_protocol()
    print('result from Bob: G(x, y) =', res)
    sock.close()

References

• Introduction to garbled circuits (I) Oblivious transfer
• GMW Protocol introduction