Privacy-preserving Matrix Rank Computation and Its Applications  

作　　者：YAO Yifei HUANG Liusheng LUO Yonglong XU Weijiang JING Weiwei 

机构地区：[1]Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China [2]National High Performance Computing Center at Hefei, Hefei 230027, ChinaI

出　　处：《Chinese Journal of Electronics》2008年第3期481-486,共6页电子学报（英文版）

基　　金：Manuscript Received May 2007; Accepted Dec. 2007. This work is supported by the National Natural Science Foundation of China （No.60703071 and No.60773032）, the Natural Science Foundation of Jiangsu Province of China （No.BK2007060）, the Anhui Provincial Natural Science Foundation （No.070412043） and the Science Foundation of the Education Department of Anhui Province （No.2006KJ024A）.

摘　　要：Matrix rank is an important tool for mathematical analysis, it is hard to compute cooperatively in an insecure distributed network. For the purpose to solve this problem, we put forward a privacy-preserving rank computation protocol for the first time. In this paper, the pro-rata protocol is improved to an optimal complexity of O（m） through comparing the collective information to reduce the round number, it performs better when the disproportional pairs distribute dispersedly or appear at later part of the sequence. Then, we propose a protocol to calculate matrix rank by the help of privacy-preserving technology, this protocol implements securely step by step according to the procedure in linear algebra. The protocol achieves the goal in secure two-party model without leaking other message. After that, their applications in mean square error and square sum error are considered. At last, we analyze all the protocols appeared in this paper to inves-tigate their correctness, complexity and security by means of mathematical induction and cryptographic primitive.

关 键 词：Secure two-party computation （STC） Matrix rank Scalar product protocol Equality-testing protocol Intersection protocol. 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]