Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/72267
Type: Thesis
Title: Methods for two-party privacy-preserving linear programming.
Author: Bednarz, Alice
Issue Date: 2012
School/Discipline: School of Mathematical Sciences
Abstract: Imagine two companies who each manage part of a delivery network. Suppose these companies are considering the benefits of cooperation | would they be able to deliver packages faster and more cheaply if they could share each other's networks? Answering this question would usually mean sharing private company information with each other, such as network topologies, internal capacities and budgets. Companies are reluctant to share such information, for fear of losing their competitive advantage, fear of revealing sensitive company information, or fear of breaching anti-trust laws. However, collaboration could bring mutual gain. What if it were possible to collaborate without sharing sensitive information? Fortunately, a methodology called secure multiparty computation can alleviate these privacy concerns. Developed in the 1980s, it allows parties who don't trust each other to compute functions involving their private data amongst themselves, whilst keeping their private information hidden. This method eliminates the need to find a trusted third party. Linear programs are one of the most common types of optimisation problems, occurring widely in industry. For example, supply chain planning problems, delivery problems and scheduling problems can all be modelled as linear programs. Recently, the idea of optimisation with privacy concerns has been studied in the form of privacy-preserving linear programming. The aim is to solve a linear program jointly defined by two or more parties, who wish to solve the joint program for mutual benefit, yet are unwilling to share their data. In this thesis we address the two-party case, where each party owns a subset of the linear program's components. Solution methods for privacy-preserving linear programs can be grouped into two classes: cryptographic methods, and transformation methods. Cryptographic methods implement a privacy-preserving version of the Simplex method, while transformation methods `disguise' the linear program using random matrices, allowing one to use any standard optimisation software to solve the linear program. The transformation methods are more efficient, but only provide `heuristic' security guarantees; whereas the crypto-graphic methods have robust security guarantees, but suffer from slow performance. This research investigates new variants of both methods. We correct a aw in two of the early transformation methods, and subsequently develop two new transformation methods, each with a quantifiable worst-case security level. We also propose the first cryptographic method to be based on an interior point method. We explain why the notion of a single `canonical' form, to which all methods can be applied, does not exist for privacy-preserving linear programs. In particular, the transformation methods are extremely sensitive to the way the data is partitioned between the parties involved, and the type of constraints (inequality, equality) and variables (non-negative, free) in the linear program. To make it clear which scenarios a transformation method applies to, we develop a new notation system, in the spirit of Kendall's queueing notation, to uniquely specify a privacy-preserving linear program. Our notation incorporates aspects which were previously overlooked. Throughout the thesis, we explain why careful attention must always be paid to the output of a secure computation, and in the final chapter we present an attack on privacy-preserving linear programming that is entirely dependent on knowing the output (the optimal solution). Although more work is needed to create commercially viable solution methods, privacy-preserving linear programming may one day allow companies to realise the potential benefits of collaboration, without the associated risks.
Advisor: Roughan, Matthew
Bean, Nigel Geoffrey
Dissertation Note: Thesis (Ph.D.) -- University of Adelaide, School of Mathematical Sciences, 2012
Keywords: secure multiparty computation; optimisation; transformation methods
Provenance: Copyright material removed from digital thesis. See print copy in University of Adelaide Library for full text.
Appears in Collections:Research Theses

Files in This Item:
File Description SizeFormat 
01front.pdf63.13 kBAdobe PDFView/Open
02whole.pdf1.11 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.