Solving linear programs using multiparty computation

T. Toft

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

32 Citations (Scopus)
2 Downloads (Pure)


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) .
Original languageEnglish
Title of host publicationFinancial Cryptography and Data Security (FC'09)
Place of PublicationBerlin
ISBN (Print)978-3-642-03548-7
Publication statusPublished - 2009

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Solving linear programs using multiparty computation'. Together they form a unique fingerprint.

Cite this