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

Journal of Information Processing Systems

A Practical Privacy-Preserving Cooperative Computation Protocol without Oblivious Transfer for Linear Systems of Equations

Ju-Sung Kang, Dowon Hong

Published Jun 30, 2007• 6 citations
Publisher

Abstract

We propose several practical SMC protocols for privacy-preserving cooperative scientific computations. We consider two important scientific computations which involve linear equations: the linear systems of equations problem and the linear least-square problem. The protocols proposed in this paper achieve acceptable security in the sense of Du-Zhan's paradigm and t-wise collusion-resistance, and their communication complexity is O(tm), where t is a security parameter and m is the total number of participants. The complexity of our protocol is significantly better than the previous result O( $m^2/{\mu}$ ) of [4], in which the oblivious transfer protocol is used as an important building block.

DOI
10.3745/jips.2007.3.1.021

Related papers

Privacy-Preserving Cooperative Linear System of Equations Protocol and its Application

Xuan Yang, Zhaoping Yu, Bin Kang

Privacy-preserving cooperative linear system of equations problem is an important scientific computation and widely used in many areas such as banking, manufacturing, and telecommunications. In this paper, we present a new privacy- preserving cooperative linear system of equations protocol under the semi-honest mode, which is more efficient as compared with existing schemes. The security of the newly devised protocol is also examined. Privacy-preserving cooperative linear system of equations protocol can be used to solve many privacy preserving scientific computation problems. As an example, a secure privacy-preserving polynomial interpolation protocol is developed based on the newly devised privacy-preserving cooperative linear system of equations protocol.

International Conference on Wireless Communications, Networking and Mobile Computing•Oct 1, 2008•3 citations

Communication efficient secure linear algebra

Kobbi Nissim B, Enav Weinreb

Abstract. We present communication efficient secure protocols for a variety of linear algebra problems. Our main building block is a protocol for computing Gaussian Elimination on encrypted data. As input for this protocol, Bob holds a k ×k matrix M, encrypted with Alice’s key. At the end of the protocol run, Bob holds an encryption of an upper-triangular matrix M ′ such that the number of nonzero elements on the diagonal equals the rank of M. The communication complexity of our protocol is roughly O(k 2). Building on Oblivious Gaussian elimination, we present secure protocols for several problems: deciding the intersection of linear and affine subspaces, picking a random vector from the intersection, and obliviously solving a set of linear equations. Our protocols match known (insecure) communication complexity lower bounds, and improve the communication complexity of both Yao’s garbled circuits and that of specific previously published protocols. 1

•Jan 1, 2006•0 citations

Secure two-party protocol of inverse of matrices

Huanping Liu

Secure Multi-party Computation(SMC) about which people have got some research findings at home and abroad has been a research focus in international cryptographic community recently,and this paper proposes a new protocol for the inverse of n×n matrices by using Oblivious Transfer 1 out of p protocol in the secure two-party computation environment.The protocol can be used to solve the problem securely and more efficiently.Then gives a new protocol for secure two-party linear system of equations based on it.

Computer Engineering and Applications Journal•Jan 1, 2008•0 citations

The Secure Multi-Party Protocol of Matrix Product and Its Application

Luo Wen

Wenliang Du has been studied some secure two-party scientific computation problems [4] : Linear systems of equations problems, Linear least squares problems and Linear programming problems. And he point to: (1)There are some other interesting scientific computation problems that need to be studied, such as how secure compute eigenvalues of matrix. (2)Extension to the secure multi-party computation problem, and thought extension secure two-party computation protocols to the secure multi-party computation protocols is not trivial. In this paper, authors disscuss two scientific computation problems: eigenvalues of matrix in secure multi-party computation situation, and give some secure multi-party scientific computation protocols.

Chinese Journal of Computers•Jan 1, 2005•8 citations

Secure Two-Party Scientific Computations

Li Xiang

Dr.W.DU has studied three secure two-party scientific computation problems: Linear systems of equations problems,Linear least squares problems and Linear programming problems.And he points out:there are some other interesting scientific computation problems that need to be studied,such as secure compute eigenvalues,eigenvales,eigenvectors,determinants,conditions,and factorization of a matrix.In this paper,the authors have been studied two scientific computation problems:eigenvalues and eigenvectora of matrix in secure two-party computation situation.Some secure two-party scientific computation protocols are given.

Journal of Jishou University•Jan 1, 2003•1 citation

Secure Multi-Party Computation

Fattaneh Bayatbabolghani, Marina Blanton

Secure multi-party computation (SMC) is an emerging topic which has been drawing growing attention during recent decades. There are many examples which show importance of SMC constructions in practice, such as privacy-preserving decision making and machine learning, auctions, private set intersection, and others. In this tutorial, we provide a comprehensive coverage of SMC techniques, starting from precise definitions and fundamental techniques. Consequently, a significant portion of the tutorial focuses on recent advances in general SMC constructions. We cover garbled circuit evaluation (GCE) and linear secret sharing (LSS) which are commonly used for secure two-party and multi-party computation, respectively. The coverage includes both standard adversarial models: semi-honest and malicious. For GCE, we start with the original Yao's garbled circuits construction [30] for semi-honest adversaries and consequently cover its recent optimizations such as the "free XOR,'' the garbled row reduction, the half-gates optimization, and the use of AES NI techniques. We follow with a discussion of techniques for making GCE resilient to malicious behavior, which includes the cut-and-choose approach and additional techniques to deter known attacks in the presence of malicious participants. In addition, we include the-state-of-the-art protocols for oblivious transfer (OT) and OT extension in the presence of semi-honest and malicious users. For LSS, we start from standard solutions for the semi-honest adversarial model including [5, 28] and consequently move to recent efficient constructions for semi-honest and malicious adversarial models. The coverage includes different types of corruption thresholds (with and without honest majority), which imply different guarantees with respect to abort.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 15, 2018•25 citations
We propose several practical SMC protocols for privacy-preserving cooperative scientific computations. We consider two important scientific computations which involve linear equations: the linear systems of equations problem and the linear least-square problem. The protocols proposed in this paper achieve acceptable security in the sense of Du-Zhan's paradigm and t-wise collusion-resistance, and their communication complexity is O(tm), where t is a security parameter and m is the total number of participants. The complexity of our protocol is significantly better than the previous result O( m2/μm^2/{\mu}m2/μ ) of [4], in which the oblivious transfer protocol is used as an important building block.
Privacy-preserving cooperative linear system of equations problem is an important scientific computation and widely used in many areas such as banking, manufacturing, and telecommunications. In this paper, we present a new privacy- preserving cooperative linear system of equations protocol under the semi-honest mode, which is more efficient as compared with existing schemes. The security of the newly devised protocol is also examined. Privacy-preserving cooperative linear system of equations protocol can be used to solve many privacy preserving scientific computation problems. As an example, a secure privacy-preserving polynomial interpolation protocol is developed based on the newly devised privacy-preserving cooperative linear system of equations protocol.
Abstract. We present communication efficient secure protocols for a variety of linear algebra problems. Our main building block is a protocol for computing Gaussian Elimination on encrypted data. As input for this protocol, Bob holds a k ×k matrix M, encrypted with Alice’s key. At the end of the protocol run, Bob holds an encryption of an upper-triangular matrix M ′ such that the number of nonzero elements on the diagonal equals the rank of M. The communication complexity of our protocol is roughly O(k 2). Building on Oblivious Gaussian elimination, we present secure protocols for several problems: deciding the intersection of linear and affine subspaces, picking a random vector from the intersection, and obliviously solving a set of linear equations. Our protocols match known (insecure) communication complexity lower bounds, and improve the communication complexity of both Yao’s garbled circuits and that of specific previously published protocols. 1
Secure Multi-party Computation(SMC) about which people have got some research findings at home and abroad has been a research focus in international cryptographic community recently,and this paper proposes a new protocol for the inverse of n×n matrices by using Oblivious Transfer 1 out of p protocol in the secure two-party computation environment.The protocol can be used to solve the problem securely and more efficiently.Then gives a new protocol for secure two-party linear system of equations based on it.
Wenliang Du has been studied some secure two-party scientific computation problems [4] : Linear systems of equations problems, Linear least squares problems and Linear programming problems. And he point to: (1)There are some other interesting scientific computation problems that need to be studied, such as how secure compute eigenvalues of matrix. (2)Extension to the secure multi-party computation problem, and thought extension secure two-party computation protocols to the secure multi-party computation protocols is not trivial. In this paper, authors disscuss two scientific computation problems: eigenvalues of matrix in secure multi-party computation situation, and give some secure multi-party scientific computation protocols.
Dr.W.DU has studied three secure two-party scientific computation problems: Linear systems of equations problems,Linear least squares problems and Linear programming problems.And he points out:there are some other interesting scientific computation problems that need to be studied,such as secure compute eigenvalues,eigenvales,eigenvectors,determinants,conditions,and factorization of a matrix.In this paper,the authors have been studied two scientific computation problems:eigenvalues and eigenvectora of matrix in secure two-party computation situation.Some secure two-party scientific computation protocols are given.
Secure multi-party computation (SMC) is an emerging topic which has been drawing growing attention during recent decades. There are many examples which show importance of SMC constructions in practice, such as privacy-preserving decision making and machine learning, auctions, private set intersection, and others. In this tutorial, we provide a comprehensive coverage of SMC techniques, starting from precise definitions and fundamental techniques. Consequently, a significant portion of the tutorial focuses on recent advances in general SMC constructions. We cover garbled circuit evaluation (GCE) and linear secret sharing (LSS) which are commonly used for secure two-party and multi-party computation, respectively. The coverage includes both standard adversarial models: semi-honest and malicious. For GCE, we start with the original Yao's garbled circuits construction [30] for semi-honest adversaries and consequently cover its recent optimizations such as the "free XOR,'' the garbled row reduction, the half-gates optimization, and the use of AES NI techniques. We follow with a discussion of techniques for making GCE resilient to malicious behavior, which includes the cut-and-choose approach and additional techniques to deter known attacks in the presence of malicious participants. In addition, we include the-state-of-the-art protocols for oblivious transfer (OT) and OT extension in the presence of semi-honest and malicious users. For LSS, we start from standard solutions for the semi-honest adversarial model including [5, 28] and consequently move to recent efficient constructions for semi-honest and malicious adversarial models. The coverage includes different types of corruption thresholds (with and without honest majority), which imply different guarantees with respect to abort.