Expression rewriting for secure computation optimization

摘要

Implementations of the present disclosure are directed to provide secure, multi-party computation and include actions of receiving a program, the program being human-readable and including one or more expressions to provide secure computation based on inputs provided by two or more parties, the program providing a secure computation protocol including at least one calculation that is performed on behalf of the two or more parties, processing the program and one or more rewriting rules in view of a cost-driven heuristic to automatically generate a rewritten program, the rewritten program including a structure that enables localization of one or more calculations and providing an optimized secure computation protocol that localizes the at least one calculation to be performed by at least one of the two or more parties, and compiling the rewritten program to generate a computer-executable program.

主权项

1. A computer-implemented method for providing secure, multi-party computation, the method being executed using one or more processors and comprising:
receiving, by the one or more processors, a program, the program being human-readable and providing a secure computation protocol comprising at least one calculation that is performed for two or more parties, the program comprising one or more expressions that provide secure computation based on inputs provided by the two or more parties; processing, by the one or more processors, the program and one or more rewriting rules in view of a cost-driven heuristic by determining a plurality of operator cost functions based on operand bit-length and a tree cost function that performs a preorder tree traversal and sums the plurality of operator cost functions to automatically generate a rewritten program by representing an expression of the program as an abstract syntax tree that reduces a complexity of the secure computation protocol and optimizes a performance of the program, the rewritten program comprising_localization of one or more calculations by applying one or more operators to values within sets of the two or more parties and providing an optimized secure computation protocol that localizes the at least one calculation, such that the at least one calculation is to be performed by at least one of the two or more parties; compiling, by the one or more processors, the rewritten program to generate a computer-executable program; and providing the secure, multi-party computation by executing the computer-executable program.