Applied Mechanics and Materials

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

Qiang Zheng, Shou Shan Luo, Yang Xin

Published Jan 1, 2010• 4 citations

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.

DOI: 10.4028/www.scientific.net/amm.20-23.265

Related papers

Secure and efficient linear algebra computation

Matthew Franklin, Payman Mohassel

In this dissertation, we study the design of secure and efficient protocols for distributed linear algebra problems. All existing solutions to the problem are either inefficient in terms of round and communication complexity and/or provide security against very weak adversaries. We design protocols for two different adversarial settings. (i) Computational: where the adversary's computational resources are bounded, but the adversary is allowed to corrupt all but one of the participants. (ii) Information theoretic: where the adversary is unconditionally powerful, but is only allowed to corrupt a third of the participants. The security in both cases is defined in the real world/ideal world simulation paradigm, where we assume that the adversary can behave arbitrarily malicious. Our main constructions are O(s) round protocols with O(sn2+1/s) communication for testing singularity of a shared n x n matrix, for any positive integer s, in both adversarial settings. We then use and extend these constructions to design secure protocols for computing the rank of a shared matrix and solving shared linear systems with similar efficiency. Our protocols are almost optimal in terms of round and communication complexity, as they roughly match the efficiency of the best possible protocols for the case where security is not a concern. We use a wide range of techniques from computer algebra to reduce the problem of securely deciding singularity to the problem of secure matrix multiplication. We then design new and efficient protocols for secure matrix multiplication in both adversarial environments. In the computational setting, and when there are only two parties, we apply cut-and-choose techniques to encrypted algebraic encodings of the inputs, outputs, and intermediate values in order to prevent malicious behavior. We achieve even better amortized efficiency when running multiple instances of the protocol, via use of share-packing techniques. When the number of parties is more that two, our construction relies on efficient instantiations of the inner and outer protocols in a recently introduced compiler by Ishai et al. [35]. In the information theoretic setting, our protocol takes advantage of a homomorphic commitment scheme to achieve the improved efficiency.

Jan 1, 20090 citations

Unconditionally Secure Constant Round Multi-Party Computation for Equality, Comparison, Bits and Exponentiation.

Eike Kiltz

In this paper we are interested in efficient and secure constant round multi-party protocols which provide unconditional security against so called honest-but-curious adversaries. In particular, we design a novel constant round protocol that converts from shares over Z_q to shares over the integers working for all shared inputs from Z_q. Furthermore, we present a constant round protocol to securely evaluate a shared input on a public polynomial whose running time is linear in the degree of the polynomial. The proposed solution makes use of Chebyshev Polynomials. We show that the latter two protocols can be used to design efficient constant round protocols for the following natural problems: (i) Equality: Computing shares of the bit indicating if a shared input value equals zero or not. This provides the missing building blocks for many constant round linear algebra protocols from the work of Cramer and Damgård [CD01]. (ii) Comparison: Computing shares of a bit indicating which of two shared inputs is greater. (iii) Bits: Computing shares of the binary representation of a shared input value. (iv) Exponentiation: Computing shares of x^a mod q given shares of x, a and q. Prior to this paper, for all the above mentioned problems, there were in general no efficient constant round protocols known providing unconditional security.

Jan 1, 200517 citations

Secure Distributed Computation in the Exponent

Hong Wang, Wei Shi

A secure multi-party computation problem deals with computing a function on any input, in a distributed network, ensuring that no more information is revealed to a player in the computation. New protocols are developed for the following interesting variation on a typical problem of secure multi-party computation: Given secrets shared among a group of players, compute the function value of basic computations, such as interpolation, addition, multiplication or inversion, in the exponent. The protocols can be proven robust and secure in standard computation models.

Advanced materials researchMar 1, 20110 citations

Efficient Multi-Party Computation over Rings.

Ronald Cramer, Serge Fehr, Yuval Ishai +1 more

Abstract. Secure multi-party computation (MPC) is an active research area, and a wide range of literature can be found nowadays suggesting improvements and generalizations of existing protocols in various directions. However, all current techniques for secure MPC apply to functions that are represented by (boolean or arithmetic) circuits over finite fields. We are motivated by two limitations of these techniques: – Generality. Existing protocols do not apply to computation over more general algebraic structures (except via a brute-force simulation of computation in these structures). – Efficiency. The best known constant-round protocols do not efficiently scale even to the case of large finite fields. Our contribution goes in these two directions. First, we propose a basis for unconditionally secure MPC over an arbitrary finite ring, an algebraic object with a much less nice structure than a field, and obtain efficient MPC protocols requiring only a black-box access to the ring operations and to random ring elements. Second, we extend these results to the constant-round setting, and suggest efficiency improvements that are relevant also for the important special case of fields. We demonstrate the usefulness of the above results by presenting a novel application of MPC over (non-field) rings to the round-efficient secure computation of the maximum function. 1

Jan 1, 200311 citations

On Secure Two-party Integer Division.

Morten Dahl, Chao Ning, Tomas Toft

Abstract. We consider the problem of secure integer division: given two Paillier encryptions of ℓ-bit values n and d, determine an encryption of ⌊ n ⌋ without leaking any information about n or d. We propose two new d protocols solving this problem. The first requires O(ℓ) arithmetic operation on encrypted values (secure addition and multiplication) in O(1) rounds. This is the most efficient constant-rounds solution to date. The second protocol requires only O ( (log 2 ℓ)(κ + loglog ℓ) ) arithmetic operations in O(log 2 ℓ) rounds, where κ is a correctness parameter. Theoretically, this is the most efficient solution to date as all previous solutions have required Ω(ℓ) operations. Indeed, the fact that an o(ℓ) solution is possible at all is highly surprising. Keywords: Secure two-party computation, Secure integer division, Constantrounds, Bit-Length

Jan 1, 20120 citations

Matrix operations in multi-party computation

Rafael Harth

This document presents two novel techniques for Multi-Party Computation based on secret sharing where the objects of computation are square matrices over a finite field. Matrix Triples can be consumed during the evaluation phase to obtain the product of two matrices, and they have quadratic space complexity, which makes them more efficient for this purpose than ordinary multiplication triples. Matrix Power Tuples are costly to produce during the preprocessing phase but allow the parties to take a matrix to a power with just a single round of communication during the evaluation phase. The latter technique also has a considerably simpler and cheaper variant that can be applied in cases where multiplication is commutative. We provide a bottom-up explanation of the ideas behind Matrix Power Tuples, as well as a formal specification of both techniques in the form of protocols and ideal functionalities. We use the latter to provide a security proof in the iUC model. We also provide an introduction into the most widely used techniques for Multi-Party Computation in the modern literature.

Jan 1, 20200 citations