Privacy Preserving Cryptography Questions

import numpy as np

# Large prime modulus for arithmetic (fits in 64-bit)
P = 2**61 - 1  # a Mersenne-ish prime for simplicity

def mod(x):
    return np.mod(x, P)

def random_share_vector(vec):
    """Return (share_keep, share_send) where vec = share_keep + share_send (mod P)."""
    share_send = np.random.randint(0, P, size=vec.shape, dtype=np.int64)
    share_keep = mod(vec - share_send)
    return share_keep, share_send

def dot_mod(u, v):
    """Vectorized dot product modulo P, returns scalar int."""
    return int(mod(np.dot(mod(u), mod(v))))

def simulate_two_party_dot(a, b):
    """
    Simulate:
    - A has a, B has b
    - Channels are lists where parties append messages
    - Returns reconstructed dot-product (mod P)
    """
    # Ensure numpy arrays of ints
    a = np.array(a, dtype=np.int64)
    b = np.array(b, dtype=np.int64)
    assert a.shape == b.shape

    # Simulated channels
    channel_A_to_B = []
    channel_B_to_A = []

    # Step 1: Each party creates additive shares
    a_keep, a_send = random_share_vector(a)  # A keeps a_keep, sends a_send to B
    b_keep, b_send = random_share_vector(b)  # B keeps b_keep, sends b_send to A

    # Simulate send
    channel_A_to_B.append(a_send)
    channel_B_to_A.append(b_send)

    # Step 2: Each party receives the other's share
    a_received_by_B = channel_A_to_B.pop(0)
    b_received_by_A = channel_B_to_A.pop(0)

    # Step 3: Each computes local partial scalar
    # A computes dot(a_keep, b_send_received)
    partial_A = dot_mod(a_keep, b_received_by_A)
    # B computes dot(a_send_received, b_keep)
    partial_B = dot_mod(a_received_by_B, b_keep)

    # Step 4: Exchange partial scalars (simulated)
    channel_A_to_B.append(partial_A)
    channel_B_to_A.append(partial_B)
    pA = channel_A_to_B.pop(0)
    pB = channel_B_to_A.pop(0)

    # Reconstruct final dot-product: sum partials modulo P
    dot_reconstructed = mod(pA + pB)

    # For verification, compute direct dot
    dot_direct = dot_mod(a, b)
    assert dot_reconstructed == dot_direct, "Reconstruction failed"

    return int(dot_reconstructed)

# Example usage
if __name__ == "__main__":
    np.random.seed(0)
    a = np.array([3, 5, 2], dtype=np.int64)
    b = np.array([7, 11, 4], dtype=np.int64)
    print("Dot:", simulate_two_party_dot(a, b))

import random
import heapq

p = 2**61-1  # prime-like for modular arithmetic

def share_vector(v):
    """Client: produce two additive shares"""
    s0 = [random.randrange(p) for _ in v]
    s1 = [(vi - s0i) % p for vi, s0i in zip(v, s0)]
    return s0, s1

def beaver_triple(d):
    """Generate Beaver triple shares for vectors of dim d.
    Returns (a0,a1),(b0,b1),(c0,c1) with c = a*b elementwise.
    """
    a = [random.randrange(p) for _ in range(d)]
    b = [random.randrange(p) for _ in range(d)]
    c = [(ai*bi) % p for ai,bi in zip(a,b)]
    a0, a1 = share_vector(a)
    b0, b1 = share_vector(b)
    c0, c1 = share_vector(c)
    return (a0,a1),(b0,b1),(c0,c1)

def beaver_mul(u_sh, v_sh, triple):
    """Two-party Beaver multiplication on vectors.
    u_sh = (u0,u1) locally known shares per party; we'll simulate both parties.
    triple = ((a0,a1),(b0,b1),(c0,c1))
    Returns (w0,w1) additive shares of elementwise product u*v
    """
    # simulate both parties' local computations
    a0,a1 = triple[0]
    b0,b1 = triple[1]
    c0,c1 = triple[2]
    # reconstruct a,b,c globally (simulator)
    d = len(a0)
    a = [(a0[i]+a1[i])%p for i in range(d)]
    b = [(b0[i]+b1[i])%p for i in range(d)]
    c = [(c0[i]+c1[i])%p for i in range(d)]
    # players compute e = u - a, f = v - b on their shares, then reconstruct e,f (requires open)
    u = [(u_sh[0][i]+u_sh[1][i])%p for i in range(d)]
    v = [(v_sh[0][i]+v_sh[1][i])%p for i in range(d)]
    e = [(u[i]-a[i])%p for i in range(d)]
    f = [(v[i]-b[i])%p for i in range(d)]
    # product = c + e*b + f*a + e*f
    prod = [ (c[i] + e[i]*b[i] + f[i]*a[i] + e[i]*f[i])%p for i in range(d)]
    # now split prod into shares
    w0, w1 = share_vector(prod)
    return w0, w1

# Example protocol: compute squared distance shares between query q and dataset X (n x d)
def server_side_distance_shares(q, X):
    # client shares q -> q0,q1
    q0,q1 = share_vector(q)
    # server splits each x into x0 (kept) and x1 (sent to helper) -> simulation: share_vector
    X0 = []
    X1 = []
    for x in X:
        x0,x1 = share_vector(x)
        X0.append(x0); X1.append(x1)
    # Precompute ||x||^2 shares locally for server halves
    x_norm_shares = []
    for x0,x1 in zip(X0,X1):
        # compute elementwise squares and sum without revealing: we can locally compute squares on shares via Beaver
        # For simplicity in this simulated server-side protocol, compute full norm and then split (server knows x)
        x = [(a+b)%p for a,b in zip(x0,x1)]
        norm = sum((xi*xi)%p for xi in x) % p
        n0, n1 = share_vector([norm])
        x_norm_shares.append((n0[0], n1[0]))
    # client would provide q shares to servers; we simulate both shares available
    # compute ||q||^2 shares similarly
    q_norm = sum((qi*qi)%p for qi in q) % p
    qn0, qn1 = share_vector([q_norm])
    # compute q·x via beaver multiplications per vector
    d = len(q)
    dot_shares = []
    for x0,x1 in zip(X0,X1):
        # u_sh = (q0, q1), v_sh = (x0, x1)
        triple = beaver_triple(d)
        prod0, prod1 = beaver_mul((q0,q1),(x0,x1), triple)  # elementwise products shares
        # sum elements to get dot product shares
        s0 = sum(prod0)%p
        s1 = sum(prod1)%p
        dot_shares.append((s0,s1))
    # Now distance share per server: dist = ||q||^2 + ||x||^2 - 2*dot
    dist_shares = []
    for (x_n0,x_n1),(s0,s1) in zip(x_norm_shares, dot_shares):
        # party0 share:
        d0 = (qn0[0] + x_n0 - (2*s0)%p) % p
        d1 = (qn1[0] + x_n1 - (2*s1)%p) % p
        dist_shares.append((d0,d1))
    return dist_shares  # list of (share0, share1) per data point

def reconstruct_and_select(dist_shares, k):
    # client reconstructs full distances and selects k smallest indices
    dists = [ (d0+d1)%p for d0,d1 in dist_shares ]
    # convert modular to integers (assume values < p/2)
    dists = [di if di <= p//2 else di-p for di in dists]
    idxs = heapq.nsmallest(k, range(len(dists)), key=lambda i: dists[i])
    return idxs, [dists[i] for i in idxs]

# quick demo
if __name__ == "__main__":
    q = [3,4]
    X = [[0,0],[3,4],[5,5],[2,1]]
    shares = server_side_distance_shares(q,X)
    print(reconstruct_and_select(shares, k=2))