Expand-and-Randomize: An Algebraic Approach to Secure Computation.

We consider the secure computation problem in a minimal model, where Alice and Bob each holds an input and wish to securely compute a function of their inputs at Carol without revealing any additional information about the inputs. For this minimal secure computation problem, we propose a novel coding scheme built from two steps. First, the function to be computed is such that it can be recovered while additional information might be leaked. Second, a step is applied to the expanded function such that the leaked information is protected. We implement this expand-and-randomize coding scheme with two algebraic structures-the finite field and the modulo ring of integers, where the step is realized with the operation and the step is realized with the operation over the respective algebraic structures.