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

International Conference on Broadband and Wireless Computing, Communication and Applications (BWCCA)

Verifiable Algorithm for Secure Outsourcing of Systems of Linear Equations in the Case of No Solution

Haixin Nie, Hua Ma, Jianfeng Wang, Xiaofeng Chen

Published Nov 1, 2014• 4 citations
Publisher

Abstract

Systems of linear equations, as a fundamental topic in the development of the computational sciences, have been well studied in the scientific community. In this paper, we investigate secure outsourcing for large-scale systems of linear equations, which is considered as a prohibitively expensive computation for the clients with limited computational resources. Based on Chen's work, we propose a verifiable algorithm for secure outsourcing of large-scale systems of linear equations in the case of no solution under the fully malicious model. We uniquely utilize linear programming, which is another well studied scientific computing problem, to help the client to verify the correctness of results returned by the server. Compared with the state-of-the-art algorithm (Chen et al' scheme), the proposed algorithm is suitable not only for any nonsingular dense matrix A, but for a set of singular matrixes that lead the system of linear equations has no solution. Besides, the computational complexity for the verification of no solution in our scheme is still O (n2). Therefore, our proposed algorithm is more suitable for real applications.

DOI
10.1109/bwcca.2014.117

Related papers

Publicly verifiable and efficiency/security-adjustable outsourcing scheme for solving large-scale modular system of linear equations

Panpan Meng, Chengliang Tian, Xiangguo Cheng

Abstract Solving large-scale modular system of linear equations ( $\mathcal {LMSLE}$ ℒℳSℒE ) is pervasive in modern computer and communication community, especially in the fields of coding theory and cryptography. However, it is computationally overloaded for lightweight devices arisen in quantity with the dawn of the things of internet (IoT) era. As an important form of cloud computing services, secure computation outsourcing has become a popular topic. In this paper, we design an efficient outsourcing scheme that enables the resource-constrained client to find a solution of the $\mathcal {LMSLE}$ ℒℳSℒE with the assistance of a public cloud server. By utilizing affine transformation based on sparse unimodular matrices, our scheme has three merits compared with previous work: 1) Our scheme is efficiency/security-adjustable. Our encryption method is dynamic, and it can balance the security and efficiency to match different application scenarios by skillfully control the number of unimodular matrices. 2) Our scheme is versatile. It is suit for genericm-by-ncoefficient matrixA, no matter it is square or not. 3) Our scheme satisfies public verifiability and achieves the optimal verification probability. It enables any verifier which is not necessarily the client to verify the correctness of the results returned from the cloud server with probability 1. Finally, theoretical analysis and comprehensive experimental results confirm our scheme’s security and high efficiency.

Journal of Cloud Computing Advances Systems and Applications•Dec 1, 2019•13 citations

Securely outsourcing linear algebra computations

Mikhail J. Atallah, Keith B. Frikken

We give improved protocols for the secure and private outsourcing of linear algebra computations, that enable a client to securely outsource expensive algebraic computations (like the multiplication of large matrices) to a remote server, such that the server learns nothing about the customer's private input or the result of the computation, and any attempted corruption of the answer by the server is detected with high probability. The computational work performed at the client is linear in the size of its input and does not require the client to locally carry out any expensive encryptions of such input. The computational burden on the server is proportional to the time complexity of the current practically used algorithms for solving the algebraic problem (e.g., proportional to n3 for multiplying two n x n matrices). The improvements we give are: (i) whereas the previous work required more than one remote server and assumed they do not collude, our solution works with a single server (but readily accommodates many, for improved performance); (ii) whereas the previous work required a server to carry out expensive cryptographic computations (e.g., homomorphic encryptions), our solution does not make use of any such expensive cryptographic primitives; and (iii) whereas in previous work collusion by the servers against the client revealed to them the client's inputs, our scheme is resistant to such collusion. As in previous work, we maintain the property that the scheme enables the client to detect any attempt by the server(s) at corruption of the answer, even when the attempt is collusive and coordinated among the servers.

ACM Asia Conference on Computer and Communications Security (ASIA CCS)•Apr 13, 2010•261 citations

Online privacy preserving outsourcing of large matrix multiplication

Fatemeh Erfan, Hamid Mala

Outsourcing computation to cloud server has recently become popular in cloud computing. Cloud computing technologies enable clients with limited computational resources to outsource their massive computations to powerful cloud servers. Outsourcing computation has some new concerns, such as outsourced data and result privacy, verifiability and efficiency. Matrix multiplication is one of the most basic computational problems. In this paper, we are motivated to design a secure and efficient protocol for outsourcing the massive matrix multiplication computations to the cloud server. The existing works are mostly under amortized model that have an expensive phase as offline mode. Our proposed scheme does not have any expensive phase. So the client can outsource its matrices in online mode in which the efficiency of outsourcing will be increased. In our scheme, the client encrypts two matrices and sends them to a semi-honest cloud server. The cloud server computes matrix multiplication and a proof. After that, it sends the encrypted result to the client and finally the client checks the validity of the computation and decrypts the result. Our proposed scheme achieves privacy protection of outsourced data and multiplication result, unforgeability of proof, verification and high efficiency.

International Conference on Computer and Knowledge Engineering•Oct 1, 2017•3 citations

Private and Cheating-Free Outsourcing of Algebraic Computations

David Benjamin, Mikhail J. Atallah

We give protocols for the secure and private outsourcing of linear algebra computations, that enable a client to securely outsource expensive algebraic computations (like the multiplication of huge matrices) to two remote servers, such that the servers learn nothing about the customer's private input or the result of the computation,and any attempted corruption of the answer by the servers is detected with high probability. The computational work done locally by the client is linear in the size of its input and does not require the client to carry out locally any expensive encryptions of such input.The computational burden on the servers is proportional to the time complexity of the current practically used algorithms for solving the algebraic problem (e.g., proportional to n3for multiplying two ntimesn matrices). If the servers were to collude against the client,then they would only find out the client's private inputs, but they would not be able to corrupt the answer without detection by the client.

Conference on Privacy, Security and Trust•Oct 1, 2008•174 citations

Securely verifiable outsourcing schemes of matrix calculation

Can Xiang, Chunming Tang

Matrix calculation, which has been considered as one of the most expensive operations, plays an important role in most current cryptosystems. In this paper, we propose three new and secure outsourcing schemes of matrix calculation by using one untrusted cloud server. The first one is for matrix multiplication, the second is for the inverse of a matrix, and the third is for the determinant of a matrix. Compared with other proposed schemes, our schemes are superior in efficiency owing to the reduction of user cost. In particular, the user's computation cost in our schemes is at most 1/4, 1/4, 7/16 of the corresponding schemes in the state-of-the-art algorithms, respectively. In addition, the efficiency and security of our schemes are analysed and proved.

International Journal of High Performance Computing and Networking•Jan 1, 2015•2 citations

Secure outsourced computation of the characteristic polynomial and eigenvalues of matrix

Xing Hu, Chunming Tang

Linear algebra plays an important role in computer science, especially in cryptography. Numerous cryptographic protocols and scientific computations are based on linear algebra, which can be reduced to some core problems, such as matrix multiplication, determinant and the characteristic polynomial of a matrix. However, it is difficult to carry out these expensive computations independently for resource-limited cloud users. Outsourced computation, a service provided by cloud computing, enables a resources-constrained client to outsource his mass computing tasks to the cloud. In this paper, we use data hiding technique to design a secure and verifiable outsourcing protocol for computing the characteristic polynomial and eigenvalues of a matrix. Our protocols achieve several desired features, such as data privacy, verifiability and efficiency. Moreover, no cryptographic assumption is needed in our protocols.

Journal of Cloud Computing Advances Systems and Applications•Apr 9, 2015•26 citations
Systems of linear equations, as a fundamental topic in the development of the computational sciences, have been well studied in the scientific community. In this paper, we investigate secure outsourcing for large-scale systems of linear equations, which is considered as a prohibitively expensive computation for the clients with limited computational resources. Based on Chen's work, we propose a verifiable algorithm for secure outsourcing of large-scale systems of linear equations in the case of no solution under the fully malicious model. We uniquely utilize linear programming, which is another well studied scientific computing problem, to help the client to verify the correctness of results returned by the server. Compared with the state-of-the-art algorithm (Chen et al' scheme), the proposed algorithm is suitable not only for any nonsingular dense matrix A, but for a set of singular matrixes that lead the system of linear equations has no solution. Besides, the computational complexity for the verification of no solution in our scheme is still O (n2). Therefore, our proposed algorithm is more suitable for real applications.
Abstract Solving large-scale modular system of linear equations ( LMSLE\mathcal {LMSLE}LMSLE ℒℳSℒE ) is pervasive in modern computer and communication community, especially in the fields of coding theory and cryptography. However, it is computationally overloaded for lightweight devices arisen in quantity with the dawn of the things of internet (IoT) era. As an important form of cloud computing services, secure computation outsourcing has become a popular topic. In this paper, we design an efficient outsourcing scheme that enables the resource-constrained client to find a solution of the LMSLE\mathcal {LMSLE}LMSLE ℒℳSℒE with the assistance of a public cloud server. By utilizing affine transformation based on sparse unimodular matrices, our scheme has three merits compared with previous work: 1) Our scheme is efficiency/security-adjustable. Our encryption method is dynamic, and it can balance the security and efficiency to match different application scenarios by skillfully control the number of unimodular matrices. 2) Our scheme is versatile. It is suit for genericm-by-ncoefficient matrixA, no matter it is square or not. 3) Our scheme satisfies public verifiability and achieves the optimal verification probability. It enables any verifier which is not necessarily the client to verify the correctness of the results returned from the cloud server with probability 1. Finally, theoretical analysis and comprehensive experimental results confirm our scheme’s security and high efficiency.
We give improved protocols for the secure and private outsourcing of linear algebra computations, that enable a client to securely outsource expensive algebraic computations (like the multiplication of large matrices) to a remote server, such that the server learns nothing about the customer's private input or the result of the computation, and any attempted corruption of the answer by the server is detected with high probability. The computational work performed at the client is linear in the size of its input and does not require the client to locally carry out any expensive encryptions of such input. The computational burden on the server is proportional to the time complexity of the current practically used algorithms for solving the algebraic problem (e.g., proportional to n3 for multiplying two n x n matrices). The improvements we give are: (i) whereas the previous work required more than one remote server and assumed they do not collude, our solution works with a single server (but readily accommodates many, for improved performance); (ii) whereas the previous work required a server to carry out expensive cryptographic computations (e.g., homomorphic encryptions), our solution does not make use of any such expensive cryptographic primitives; and (iii) whereas in previous work collusion by the servers against the client revealed to them the client's inputs, our scheme is resistant to such collusion. As in previous work, we maintain the property that the scheme enables the client to detect any attempt by the server(s) at corruption of the answer, even when the attempt is collusive and coordinated among the servers.
Outsourcing computation to cloud server has recently become popular in cloud computing. Cloud computing technologies enable clients with limited computational resources to outsource their massive computations to powerful cloud servers. Outsourcing computation has some new concerns, such as outsourced data and result privacy, verifiability and efficiency. Matrix multiplication is one of the most basic computational problems. In this paper, we are motivated to design a secure and efficient protocol for outsourcing the massive matrix multiplication computations to the cloud server. The existing works are mostly under amortized model that have an expensive phase as offline mode. Our proposed scheme does not have any expensive phase. So the client can outsource its matrices in online mode in which the efficiency of outsourcing will be increased. In our scheme, the client encrypts two matrices and sends them to a semi-honest cloud server. The cloud server computes matrix multiplication and a proof. After that, it sends the encrypted result to the client and finally the client checks the validity of the computation and decrypts the result. Our proposed scheme achieves privacy protection of outsourced data and multiplication result, unforgeability of proof, verification and high efficiency.
We give protocols for the secure and private outsourcing of linear algebra computations, that enable a client to securely outsource expensive algebraic computations (like the multiplication of huge matrices) to two remote servers, such that the servers learn nothing about the customer's private input or the result of the computation,and any attempted corruption of the answer by the servers is detected with high probability. The computational work done locally by the client is linear in the size of its input and does not require the client to carry out locally any expensive encryptions of such input.The computational burden on the servers is proportional to the time complexity of the current practically used algorithms for solving the algebraic problem (e.g., proportional to n3for multiplying two ntimesn matrices). If the servers were to collude against the client,then they would only find out the client's private inputs, but they would not be able to corrupt the answer without detection by the client.
Matrix calculation, which has been considered as one of the most expensive operations, plays an important role in most current cryptosystems. In this paper, we propose three new and secure outsourcing schemes of matrix calculation by using one untrusted cloud server. The first one is for matrix multiplication, the second is for the inverse of a matrix, and the third is for the determinant of a matrix. Compared with other proposed schemes, our schemes are superior in efficiency owing to the reduction of user cost. In particular, the user's computation cost in our schemes is at most 1/4, 1/4, 7/16 of the corresponding schemes in the state-of-the-art algorithms, respectively. In addition, the efficiency and security of our schemes are analysed and proved.
Linear algebra plays an important role in computer science, especially in cryptography. Numerous cryptographic protocols and scientific computations are based on linear algebra, which can be reduced to some core problems, such as matrix multiplication, determinant and the characteristic polynomial of a matrix. However, it is difficult to carry out these expensive computations independently for resource-limited cloud users. Outsourced computation, a service provided by cloud computing, enables a resources-constrained client to outsource his mass computing tasks to the cloud. In this paper, we use data hiding technique to design a secure and verifiable outsourcing protocol for computing the characteristic polynomial and eigenvalues of a matrix. Our protocols achieve several desired features, such as data privacy, verifiability and efficiency. Moreover, no cryptographic assumption is needed in our protocols.