With the advent of cloud computing, individuals and companies alike are looking for opportunities to leverage cloud resources not only for storage but also for computation. Nevertheless, the reliance on the cloud to perform computation raises the unavoidable challenge of how to assure the correctness of the delegated computation. In this regard, we introduce two cryptographic protocols for publicly verifiable computation that allow a lightweight client to securely outsource to a cloud server the evaluation of high-degree univariate polynomials and the multiplication of large matrices. Similarly to existing work, our protocols follow the amortized verifiable computation approach. Furthermore, by exploiting the mathematical properties of polynomials and matrices, they are more efficient and give way to public delegatability. Finally, besides their efficiency, our protocols are provably secure under well-studied assumptions.
With the advent of cloud computing, individuals and companies alike are looking for opportunities to leverage cloud resources not only for storage but also for computation. Nevertheless, the reliance on the cloud to perform computation raises the unavoidable challenge of how to assure the correctness of the delegated computation. In this regard, we introduce two cryptographic protocols for publicly verifiable computation that allow a lightweight client to securely outsource to a cloud server the evaluation of high-degree univariate polynomials and the multiplication of large matrices. Similarly to existing work, our protocols follow the amortized verifiable computation approach. Furthermore, by exploiting the mathematical properties of polynomials and matrices, they are more efficient and give way to public delegatability. Finally, besides their efficiency, our protocols are provably secure under well-studied assumptions.
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.
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.
Abstract. Linear algebra plays an important role in computer science, especially in cryptography.Numerous cryptog-raphic protocols, scientific computations, and numerical computations are based on linear algebra. Many linear algebra tasks can be reduced to some core problems, such as matrix multiplication, determinant of matrix and the characteristic polynomial of matrix. However, it is difficult to execute these tasks independently for client whose computation abilities are weaker than polynomial-time computational ability. Cloud Computing is a novel eco-nomical paradigm which provides powerful computational resources that enables resources-constrained client to outsource their mass computing tasks to the cloud. In this paper, we propose a new verifiable and secure outsourcing protocol for the problem of computing the characteristic polynomial and eigenvalues of matrix. These protocols are not only effi-cient and secure, but also unnecessary for any cryptographic assumption.
Matrix calculation plays an important role in both scientific computation and cryptography. Many cryptographic protocols, scientific computations, and numerical computations are based on matrix calculation. However, it is difficult to finish matrix calculation independently for these customers whose computation abilities are limited. Cloud Computing has a great deal of computational resources, which enable customers with limited computational resources to outsource their mass computing to the cloud. In this paper we design secure, verifiable, and practical outsourcing protocols for matrix calculation, including matrix multiplication, computing the determinant and inverse of a matrix. Compared with those existing outsourcing protocols, our protocols have obvious improvement concerning both efficiency and security. Furthermore, no cryptographic assumption is needed in our protocols. Finally, we give two applications for our outsourcing protocols; one is to construct an outsourcing protocol for solving the large-scale systems of linear equations, and the other is to design an outsourcing protocol for realizing a cryptosystem based on error-correction code.
Abstract Solving large-scale modular system of linear equations ( 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 ℒℳ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.
Cloud-assisted computation empowers resource-constrained clients to efficiently tackle computationally intensive tasks by outsourcing them to resource-rich cloud servers. In the current era of Big Data, the widespread need to solve large-scale modular linear systems of equations (LMLSE) of the formAx≡bmodqposes a significant challenge, particularly for lightweight devices. This paper delves into the secure outsourcing ofLMLSEunder a malicious single-server model and, to the best of our knowledge, introduces the inaugural protocol tailored to this specific context. The cornerstone of our protocol lies in the innovation of a novel matrix encryption method based on sparse unimodular matrix transformations. This novel technique bestows our protocol with several key advantages. First and foremost, it ensures robust privacy for all computation inputs, encompassingA,b,q, and the outputx, as validated by thorough theoretical analysis. Second, the protocol delivers optimal verifiability, enabling clients to detect cloud server misbehavior with an unparalleled probability of 1. Furthermore, it boasts high efficiency, requiring only a single interaction between the client and the cloud server, significantly reducing local-client time costs. For anm-by-nmatrixA, a given parameterλ=ω(logq), andρ=2.371552, the time complexity is diminished fromO(max{mnρ−1,mρ−2n2}⋅(logq)2)toO((mn+m2)λlogq+mn(logq)2). The comprehensive results of our experimental performance evaluations substantiate the protocol's practical efficiency and effectiveness.