Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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
Publisher

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, 2009•0 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, 2005•15 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 research•Mar 1, 2011•0 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, 2020•0 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, 2012•0 citations

Unconditionally Secure, Universally Composable Privacy Preserving Linear Algebra

Bernardo David, Rafael Dowsley, Jeroen van de Graaf +3 more

Linear algebra operations on private distributed data are frequently required in several practical scenarios (e.g., statistical analysis and privacy preserving databases). We present universally composable two-party protocols to compute inner products, determinants, eigenvalues, and eigenvectors. These protocols are built for a two-party scenario where the inputs are provided by mutually distrustful parties. After execution, the protocols yield the results of the intended operation while preserving the privacy of their inputs. Universal composability is obtained in the trusted initializer model, ensuring information theoretical security under arbitrary protocol composition in complex environments. Furthermore, our protocols are computationally efficient since they only require field multiplication and addition operations.

IEEE Transactions on Information Forensics and Security•Sep 3, 2015•17 citations
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.
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.
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.
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.
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.
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
Linear algebra operations on private distributed data are frequently required in several practical scenarios (e.g., statistical analysis and privacy preserving databases). We present universally composable two-party protocols to compute inner products, determinants, eigenvalues, and eigenvectors. These protocols are built for a two-party scenario where the inputs are provided by mutually distrustful parties. After execution, the protocols yield the results of the intended operation while preserving the privacy of their inputs. Universal composability is obtained in the trusted initializer model, ensuring information theoretical security under arbitrary protocol composition in complex environments. Furthermore, our protocols are computationally efficient since they only require field multiplication and addition operations.