Privacy-preserving linear programming

被引:44
作者
Mangasarian, O. L. [1 ,2 ]
机构
[1] Univ Wisconsin, Dept Comp Sci, Madison, WI 53706 USA
[2] Univ Calif San Diego, Dept Math, La Jolla, CA 92093 USA
关键词
Security; Privacy-preserving; Linear programming; Vertically partitioned data;
D O I
10.1007/s11590-010-0199-5
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We propose a privacy-preserving formulation of a linear program whose constraint matrix is partitioned into groups of columns where each group of columns and its corresponding cost coefficient vector are owned by a distinct entity. Each entity is unwilling to share or make public its column group or cost coefficient vector. By employing a random matrix transformation we construct a linear program based on the privately held data without revealing that data or making it public. The privacy-preserving transformed linear program has the same minimum value as the original linear program. Component groups of the solution of the transformed problem can be decoded and made public only by the original group that owns the corresponding columns of the constraint matrix and can be combined to give an exact solution vector of the original linear program.
引用
收藏
页码:165 / 172
页数:8
相关论文
共 11 条
[1]  
[Anonymous], MATLAB US GUID
[2]  
Chen KK, 2005, Fifth IEEE International Conference on Data Mining, Proceedings, P589
[3]   The rank of a random matrix [J].
Feng, Xinlong ;
Zhang, Zhinan .
APPLIED MATHEMATICS AND COMPUTATION, 2007, 185 (01) :689-694
[4]  
ILOG, 2003, ILOG CPLEX 9 0 US MA
[5]  
LAUR S, 2006, KDD 06, P618
[6]  
Mangasarian O. L., 2008, ACM T KNOWLEDGE DISC, V2
[7]  
MANGASARIAN OL, 2008, P 2008 INT C DAT MIN, V2, P473
[8]  
Mangasarian OL, 2010, ANN INFORM SYST, V8, P375, DOI 10.1007/978-1-4419-1280-0_17
[9]  
Xiao MJ, 2005, PDCAT 2005: SIXTH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES, PROCEEDINGS, P239
[10]  
Yu H., 2006, Proceedings of the 2006 ACM Symposium on Applied Computing, P603, DOI 10.1145/1141277.1141415