Research on the Secure Multi-Party Computation of some Linear Algebra Problems

Abstract:

Considering constant-round protocols for generating random shared values, for secure multiplication and for addition of shared values, etc are available and can be met by known techniques in all standard models of communication. Protocols are presented allowing the players to securely solve standard computational problems in linear algebra. In particular, securely, efficiently and in constant-round compute determinant of matrices product, rank of a matrix, and determine similarity between matrices. If the basic protocols (addition and multiplication, etc) are unconditionally secure, then so are our protocols. Furthermore our protocols offer more efficient solutions than previous techniques for secure linear algebra.

• Periodical: Applied Mechanics and Materials (Volumes 20-23)
• Pages: 265-270
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.20-23.265
• Online since: January 2010
• Authors: Qiang Zheng, Shou Shan Luo, Yang Xin
• Keywords: Constant Round, Cryptography, Information Theoretic Model, Linear Algebra, Secure Multi-Party Computation

References

[1] O. Goldreich, S. Micali and A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority, Proc. ACM STOC '87, 1987: 218-229.

DOI: 10.1145/3335741.3335755

[2] A. Yao. Protocols for Secure Computation, Proc. IEEE FOCS '82, 1982: 160-164.

[3] M. Ben-Or, S. Goldwasser, A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proc. ACM STOC '88, 1988: 1-10.

DOI: 10.1145/62212.62213

[4] D. Chaum, C. Crepeau, I. Damgard. Multi-party unconditionally secure protocols, Proc. ACM STOC '88, 1988: 11-19.

DOI: 10.1145/62212.62214

[5] J. Bar-Ilan, D. Beaver. Non-cryptographic fault-tolerant computing in constant number of rounds of interaction, Proc. ACM PODC '89, 1989: 201-209.

DOI: 10.1145/72981.72995

[6] K. Nissim, E. Weinreb. Communication efficient secure linear algebra. In: Halevi, S., Rabin, T. (eds. ) TCC 2006. LNCS, vol 3876. Springer, Heidelberg, 2006: 232-246.

[7] R. Cramer, I. Damgard. Secure distributed linear algebra in a constant number of rounds. In: J. Kilian, (ed. ) CRYPTO 2001. LNCS, vol 2139, Springer, Heidelberg , 2001: 119-136.

DOI: 10.1007/3-540-44647-8_7

[8] R. Cramer, E. Kiltz1, and C. Padro. A Note on Secure Computation of the Moore-Penrose Pseudo-inverse and Its Application to Secure Linear Algebra. In: A. Menezes. (ed. ) CRYPTO 2007. LNCS, vol 4622, Springer, Heidelberg, 2007: 613-630.

DOI: 10.1007/978-3-540-74143-5_34

[9] Y Ishai, E Kushilevitz. Private Simultaneous Messages Protocols with Applications, Proc. 5th Israel Symposium on Theoretical Comp. Sc. (ISTCS '97), 1997: 174-183.

[10] Y. Ishai, E. Kushilevitz. Randomizing Polynomials: A New Paradigm for Round-Efficient Secure Computation, Proc. of FOCS '00, (2000).

DOI: 10.1109/sfcs.2000.892118

[11] K. Mulmuley. A Fast Parallel Algorithm to Compute the Rank of a Matrix over an Arbitrary Field, Combinatorica, vol 7, 1987: 110-114.

DOI: 10.1007/bf02579205

[12] E. Kiltz, P. Mohassel, E. Weinreb, et al. Secure Linear Algebra Using Linearly Recurrent Sequences, TCC 2007, LNCS 4392, 2007: 291-310.

DOI: 10.1007/978-3-540-70936-7_16

[13] M. Ben-Or, S. Goldwasser and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). 20th STOC, (1988).

DOI: 10.1145/62212.62213

[14] I. Damgard, M. Fitzi, E. Kiltz, et al. Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation, Proc. 3rd Theory of Cryptography Conference, LNCS 3876, Springer, Heidelberg, 2006: 285-304.

DOI: 10.1007/11681878_15

[15] I. Damgard, J. Nielsen. Scalable and Unconditionally Secure multiparty computation. In: Menezes, A. (ed. ) CRYPTO 2007. LNCS, vol. 4622, Springer, Heidelberg , (2007).

[16] M. Hirt, J. Nielsen. Robust multiparty computation with linear communication complexity. In: Dwork, C. (ed. ) CRYPTO 2006. LNCS, vol. 4117, Springer, Heidelberg , 2006, 463-482.

DOI: 10.1007/11818175_28

[17] B. Zuzana, M. Hirt. Perfectly-Secure MPC with Linear Communication Complexity: In R. Canetti (ed. ): TCC 2008, LNCS 4948, Springer, Heidelberg 2008. 213-230.