Examples and features

[hsmajlovic]

Sequre examples

Householder (~65 LOC in C++):

@sequre
def householder(mpc, x):
    xdot = mpc.dot(x)   #<-- numpy-like syntax
    shift = mpc.sqrt(xdot) * ((x[0] > 0) * 2 - 1)  #<-- Syntactic sugar for comparison
    v = x.copy()
    v[0] = v[0] + shift  #<-- Beaver partitions propagated where possible
    return  v / mpc.sqrt((xdot + x[0] * shift) * 2)  #<--Compile-time pattern matching and optimization

QR factorization (~100 LOC in C++):

@sequre
def qr_fact_square(mpc, A):
    R = Q = B = A.zeros()
    for i in range(len(A) - 1):
        v = householder(mpc, A[0]).expand_dims()
        P = A.I - mpc.matmul(v.T, v) * 2  #<-- Diagonal matrix optimization
        Q[i:] = P if i == 0 else mpc.matmul(P, Q[i:])
        B = mpc.matmul(A, P)
        R[i:, i] = B[:, 0]  #<-- Advanced slicing support
        A = B[1:, 1:]
    R[-1, -1] = B[1, 1]
    return Q, R

Tridiagonalization (~120 LOC in C++):

@sequre
def tridiag(mpc, A):
    Q = A.zeros() + A.I
    T = B = A.zeros()
    for i in range(len(A) - 2):
        x = A[0, 1:].pad_right(1)
        v = householder(mpc, x)[:-1].pad_left(1).expand_dims()
        P = A.I - mpc.matmul(v.T, v) * 2
        Q[:, i:] = mpc.matmul(Q[:, i:], P)
        B = mpc.matmul(P, A, P)
        T[i, i] = B[0, 0]
        T[i + 1, i] = B[1, 0]
        T[i, i + 1] = B[0, 1]
        A = B[1:, 1:]
    T[-2:, -2:] = B[1:3, 1:3]
    return T, Q

Eigen decomposition (~80 LOC in C++):

@sequre
def eigen_decomp(mpc, A, iter_per_eval):
    L = A[0].zeros()
    A, Q = tridiag(mpc, A)
    V = Q.T
    for i in range(len(A) - 1, 0, -1):
        for _ in range(iter_per_eval):
            shift = A.diag(A[i, i])
            Q, R = qr_fact_square(mpc, A - shift)
            A = mpc.matmul(Q, R) + shift
            V[:i + 1] = mpc.matmul(Q, V[:i + 1])
        L[i] = A[i, i]
        A = A[:i, :i]
    L[0] = A[0, 0]
    return V, L

Orthonormal basis calculation (~110 LOC in C++):

@sequre
def orthonormal_basis(mpc, A):
    v_cache = []
    Q = A.zeros() + A.I
    for i in range(len(A)):
        v = householder(mpc, A[0]).expand_dims()
        B = A - mpc.matmul(A, v.T, v) * 2
        A = B[1:, 1:]
        v_cache.append(v)
    for i in range(len(Q) - 1, -1, -1):
        Qsub = Q[:, i:]
        Q[:, i:] = Qsub - mpc.matmul(Qsub, v_cache[i].T, v_cache[i]) * 2
    return Q

Sequre features

• Beaver partitions propagation
  Beaver partitions of a and b are propagated to c (offline) within c = a ˚ b, where ˚ is some SMPC operation.

• Polynomial reduction (currently disabled)

  ... 
  c = a + b
  ...
  e = d * c ** 2
  ...
  return e

  In the code snippet above, first two assignments are erased and return statement is replaced with return a**2 * d + 2*a*b*d + b**2 * d in compile time, which is then propagated to optimized polynomial reduction method in runtime. This polynomial reduction method requires only a single beaver partitioning for a, b, and d (c is removed by compiler).

• Numpy-like syntax

  • Advanced slicing support

  C[:, i:] = A[i:j, :-1] + B[:j]

  • Broadcasting

  >>> a = Shared([1.0, 2.0, 3.0])
  >>> b = Shared(2.0)
  >>> a * b
  Shared([ 2.,  4.,  6.])

  • Autocasting
    No need for explicit double_to_fp or int_to_fp calls in Sequre. Compiler will apply those automatically:

  c = non_fp_a * 3.4  # c will contain f-point shared value
  d = fp_a * 3  # d will contain f-point shared value

  • Tailor made MPC syntactic sugar
    Comparison operators (<, >) between shared values will be transformed into MPC equivalents (i.e. is_positive, less_than, etc.)

• Compile-time pattern matching and optimization
  There are few compile time transformations that leverage some MPC intrinsics in order to optimize performance. Examples:

  • a = b / sqrt(c) will be internally transformed into a = b * sqrt_inv(c)
  • a = b / 3.4 will be internally transformed into a = b.to_fp() * double_to_fp(1 / 3.4)
    etc.

• Diagonal matrix optimizations

  A = random_matrix(100, 100)  # Random matrix of shape 100x100
  B = A.random()  # Random matrix of shape 100x100
  C = A.I * A + B.I * B

  In code snipped above, calculation of C will be transformed into (approx.):

  C = zeros(100, 100)
  for k in range(100):
      C[k][k] = A[k][k] + B[k][k]

  as compiler will figure out that two addends are diagonal matrices.