TY - GEN

T1 - Solving linear programs using multiparty computation

AU - Toft, T.

PY - 2009

Y1 - 2009

N2 - Solving linear programming (LP) problems can be used to solve many different types of problems. Immediate examples include certain types of auctions as well as benchmarking. However, the input data may originate from different, mistrusting sources, which implies the need for a privacy preserving solution.
We present a protocol solving this problem using black-box access to secure modulo arithmetic. The solution can be instantiated in various settings: Adversaries may be both active and adaptive, but passive and/or static ones can be employed, e.g. for efficiency reasons. Perfect security can be obtained in the information theoretic setting (up to 1/3 corruptions), while corruption-of-all-but-one is possible in the cryptographic setting. The latter allows a two-party protocol.
The solution is based on the well known simplex method. Letting n denote the number of initial variables and m the number of constraints, each pivot requires only O(loglog(m))rounds in which O(m(m+n)) multiplication protocols and O(m+n) comparison protocols are invoked; this is equivalent to the base-algorithm. A constant-rounds variation is also possible, this increases the number of comparisons to O(m2+n) .

AB - Solving linear programming (LP) problems can be used to solve many different types of problems. Immediate examples include certain types of auctions as well as benchmarking. However, the input data may originate from different, mistrusting sources, which implies the need for a privacy preserving solution.
We present a protocol solving this problem using black-box access to secure modulo arithmetic. The solution can be instantiated in various settings: Adversaries may be both active and adaptive, but passive and/or static ones can be employed, e.g. for efficiency reasons. Perfect security can be obtained in the information theoretic setting (up to 1/3 corruptions), while corruption-of-all-but-one is possible in the cryptographic setting. The latter allows a two-party protocol.
The solution is based on the well known simplex method. Letting n denote the number of initial variables and m the number of constraints, each pivot requires only O(loglog(m))rounds in which O(m(m+n)) multiplication protocols and O(m+n) comparison protocols are invoked; this is equivalent to the base-algorithm. A constant-rounds variation is also possible, this increases the number of comparisons to O(m2+n) .

U2 - 10.1007/978-3-642-03549-4_6

DO - 10.1007/978-3-642-03549-4_6

M3 - Conference contribution

SN - 978-3-642-03548-7

T3 - Lecture Notes in Computer Science

SP - 90

EP - 107

BT - Financial Cryptography and Data Security (FC'09)

PB - Springer

CY - Berlin

ER -