text:
- Research
- Open Access
- Published:
Publicly verifiable and efficiency/security-adjustable outsourcing scheme for solving large-scale modular system of linear equations
Journal of Cloud Computing volume 8, Article number: 24 (2019)
1764 Accesses
8 Citations
1 Altmetric
Solving large-scale modular system of linear equations (\(\mathcal {LMSLE}\)) 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}\) 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 generic m-by-n coefficient matrix A, 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.
With the rapid development of 5G technologies, the Internet of things (IoT) era is coming. More and more intelligent devices are connected to the internet and communicate with each other, which will greatly facilitate people's life [1–3]. It is predicted by the technology research firm Gartner that there will be 26 billion smart devices on the Internet of Things (IoT) by 2020 [4]. However, quantities of these devices, such as wearable devices, home appliances, and RFID cards, suffer from limited computing ability, low storage space and constrained communication bandwidth. It is unrealistic for these resource-constrained devices to perform large-scale data computation and storage task. Fortunately, cloud computing, as a type of Internet-based computing, offers availably abundant processing resources to electronic devices on demand. Under this promising computing paradigm, the resource-constrained clients can outsource their overloaded computations and storages to the resource-abundant cloud servers without the investment of purchasing and maintaining their own computing facilities. Although it brings many advantages, the fact that clients and cloud servers are not necessarily in the same trusted domain brings many security issues and challenges [5–7]. On the one hand, the clients' outsourcing data may contain their sensitive information such as proprietary research data, private asset records, and personal health information, etc. The exposure of these critical information could incur the severe loss of clients' credit, economic, spirit, life and asset. On the other hand, the physical isolation from the clients and external ill-disposed economic incentives may make cloud servers curious, lazy and even malicious, and then steal clients' private information and return random, or deliberately forged results to the clients. Therefore, a security outsourcing scheme should fulfill the following properties [8, 9]: (1) Correctness. The clients should obtain the correct computation results if the cloud servers conduct the assigned computation task honestly. (2) Input/output privacy. The curious or even malicious cloud servers can not steal or speculate clients' actual input/output information. (3) Verifiability. The clients can verify the correctness of the results returned from the cloud servers. (4) Efficiency. The scheme must be efficient. That is, the clients' time/space cost of performing the large-scale data computation/storage task should be substantially cheaper than that of performing the task by themselves.
For some given integer q, a vector \(\mathbf {b}\in \mathbb {Z}_{q}^{n}\) and a full (column or row) rank matrix \(\mathbf {A}\in \mathbb {Z}_{q}^{m\times n}\), solving the modular systems of linear equations
is a fundamental computational problem in modern computer algebra [10]. It has various applications in information and communications fields. For example, in coding theory, we needs to solve this problem to decode q-ary linear code [11, 12], and, in lattice-based cryptography, it is used for generating signatures and private keys in the signature and encryption/decryption schemes based on Small Integer Solution (SIS) [13] and Learning with Errors (LWE) problems [14–16]. Also, it frequently emerges in machine learning [17]. The classic algorithm of solving this problem is Gaussian elimination with a time complexity of \(O(mn^{2}(\log q)^{2})\). It is efficient when the size of A is small. However, the exponential growth in the quantity of data generated in IoT era makes us often have to deal with large-scale matrices. For example, the recent post-quantum key exchange protocol [18] requires m,n≥1024 and q=232−1, and its improved variant [19] also requires m,n≥1024 and q=12289. For the large-scale matrix A, the Gaussian elimination becomes time-consuming which may result in the infeasible for the resource-constrained clients to solve this problem. Therefore, it is of great necessity to design an efficient algorithm to securely outsourcing the solving of the large-scale modular system of linear equations \((\mathcal {LMSLE})\).
Obviously, when A is square and invertible modulo q, the \((\mathcal {LMSLE})\) problem (1) has a unique solution in \(\mathbb {Z}_{q}\) which can be denoted as x=A−1b mod q. In this case, we can realize the securely outsourcing of \((\mathcal {LMSLE})\) by designing an efficient method to outsource the inverse of A modulo q. Although many researches have considered the outsourcing of large-scale matrix inversion computation [20–22], they focused on matrices over the real field \(\mathbb {R}\) or the finite field \(\mathbb {F}_{q}\) and the probability of verifiability can not achieve the optimal 1. Furthermore, the existing methods only designed for a square and invertible matrix A, while here we consider a general m-by-n matrix A. Another viable way is directly considering the secure outsourcing of \(\mathcal {LMSLE}\). Through imitating the currently most efficient outsourcing algorithm of large-scale system of linear equations (\(\mathcal {LSLE}\)) [23], one may want to blind the input (A,b) and the output x by sparse matrix transformations and translation vector. However, just as the authors' mentioned in the paper, their method can not provide strong enough privacy. Therefore, how to design an efficient and strong enough security outsourcing scheme for a general input matrix A is left as a meaningfully practical problem.
Our contributions
To address the above-mentioned problem, in this paper, we put forward an efficiency/security-adjustable outsourcing scheme to find a solution vector of the \(\mathcal {LMSLE}\) problem Ax≡b mod q in case that the problem is solvable. Also, our scheme is publicly variable, i.e. any verifier (not necessarily the client) can assess the correctness of the server's results. The main technique involved in our scheme essentially can be treated as an improvement of Zhang et al.'s technique [22] and Chen et al.'s technique [23], which makes our scheme superior in the following three aspects:
- 1)
Our scheme provides an adjustable encryption method based on successively sparse unimodular matrix transformations. That is, we can adjust the number of sparse unimodular matrices in the scheme to balance security and efficiency to match the different application scenarios.
- 2)
Our scheme is applicable to any matrix A such that Ax≡b mod q is solvable, no matter it is square or non-square.
- 3)
Our scheme are publicly verifiable and achieves the optimal verifiability probability 1. In other words, our scheme allows the client to delegate the verification task to any honest or even curious edge server without leaking the client's private information. Additionally, the verifier (e.g. the client or the third-party edge server) can detect the cloud server's misbehaviors with optimal probability 1.
The rest of our paper is arranged as follows: In "Security model and definitions" section, we illustrate the system model and related definitions in our outsourcing design of \(\mathcal {LMSLE}\). "Preliminaries" section reviews some necessary preliminaries used in the design of our scheme. The main scheme and its correctness, privacy, verifiability and efficiency analysis are presented in "Main scheme" section, and "Performance evaluation" section evaluates the practical performance of the proposed scheme by comprehensive experiments. We survey the related work in "Related work" section. Finally, we conclude our paper in "Conclusion and future direction" section.
Security model and definitions
System model
As shown in Fig. 1, the system model of our secure outsourcing scheme \(\mathcal {SOS}_{\mathcal {LMSLE}} (q,\mathbf {A},\mathbf {b})\) involves three entities: a resource-constrained client C, a remote public cloud server S, and an edge server E closed to C.
Client: The client C is with constrained computing resource and storage space. It intends to securely find a solution of the large-scale modular system of linear equations Ax≡b mod q by leveraging the cloud server's computation resource. To keep the privacy of the input (A,b) and the output (solution vector) x, C firstly generates a secret key SK and utilizes it to encrypt (A,b) into \((\mathbf {A}^{\prime },\mathbf {b}^{\prime })\), and then sends \((q, \mathbf {A}^{\prime },\mathbf {b}^{\prime })\) to S and E.
Cloud server: The cloud server S is public and resource-abundant, yet it is far from the client C and thus maybe untrusted. After receiving \((q, \mathbf {A}^{\prime },\mathbf {b}^{\prime })\), S performs the assigned computation task that solving another large-scale modular system of linear equations \(\mathbf {A}^{\prime } \mathbf {x}^{\prime }\equiv \mathbf {b}^{\prime }\mod q\), and returns the solution vector \(\mathbf {x}^{\prime }\) to E.
Edge server: The edge server E is semi-public and has more computing power and larger storage space than that of the client C. However, compared with the cloud server S, edge server's resource is also limited, so it cannot support complex computation task. In our outsourcing system, it mainly assists the client to verify the correctness of the returned result from S. Noteworthily, the verification task also can be conducted by the client itself, and thus this entity is optional in our system and here mainly used to illustrate the public verifiability of our scheme.
Formally, the framework of our system model consists of the following five probabilistic polynomial time (PPT) algorithms:
- 1)
\(\mathbf {KeyGen}(\Phi, 1^{m},1^{n})\rightarrow \{SK\}\): On input a \(\mathcal {LMSLE}\) problem instance Φ=(q,A,b) with \(\mathbf {A}\in \mathbb {Z}_{q}^{m\times n}\), this algorithm performed by the client C generates a random secret key SK which should be kept secret by C.
- 2)
\(\mathbf {CEnc}(\Phi,SK)\rightarrow \{\Phi ^{\prime }\}\): Utilizing the secret SK, the client C performs this algorithm to encrypt the input instance Φ=(q,A,b) into a blind input \(\Phi ^{\prime }=(q,\mathbf {A}^{\prime }, \mathbf {b}^{\prime })\), and sends \(\Phi ^{\prime }\) to the cloud server S and the edge server E.
- 3)
\(\mathbf {SCom}(\Phi ^{\prime })\rightarrow \{\mathbf {x}^{\prime }\}\): After receiving the encrypted input \(\Phi ^{\prime }=(q,\mathbf {A}^{\prime },\mathbf {b}^{\prime })\), the cloud server S invokes this algorithm to solve the large-scale modular system \(\mathbf {A}^{\prime }\mathbf {x}^{\prime }\equiv \mathbf {b}^{\prime }\mod q\), and returns a solution vector \(\mathbf {x}^{\prime }\) to the edge server E.
- 4)
\(\mathbf {EVer}(\mathbf {x}^{\prime },\Phi ^{\prime })\rightarrow \{\mathbf {x}^{\prime },\delta _{\mathbf {x}^{\prime }}\}\): This algorithm performed by the edge server E firstly verifies the correctness of the \(\mathbf {x}^{\prime }\) returned from S. If \(\mathbf {x}^{\prime }\) is correct, then \(\delta _{\mathbf {x}^{\prime }}=1\). Else, \(\delta _{\mathbf {x}^{\prime }}=0\). At last, the algorithm sends \((\mathbf {x}^{\prime },\delta _{\mathbf {x}^{\prime }})\) to the client C.
- 5)
\(\mathbf {CDec}(\mathbf {x}^{\prime },\delta _{\mathbf {x}^{\prime }},SK)\rightarrow \mathbf {x}\cup \perp \): This algorithm is performed by the client C. If the input \(\delta _{\mathbf {x}^{\prime }}=1\), then the algorithm uses the secret key SK to decrypt \(\mathbf {x}^{\prime }\) into the actual solution vector x. Otherwise, the algorithm outputs ⊥.
Threat model
Standing at the client's perceptive, the threats in our computation outsourcing system mainly originate from the credibility of the cloud server S and the edge server E. According to the misbehaviors of servers, the threats mainly come from the following two types of servers: the honest-but-curious (HBC) server, and the fully malicious (FM) server.
HBC server: the server will perform the specified computation task honestly and return the correct calculation result. However, it is curious about the actual input/output information, and tries to steal the client's valuably private information for selfish purposes.
FM server: the server not only wants to steal the client's private information, but also may arbitrarily deviate from the specified computation task and returns a random or even a tactical forged result to fool the client.
Clearly, For the HBC server, a secure outsourcing scheme must ensure the privacy of the client's input/output information. While, For the FM server, an outsorucing scheme is secure if it simultaneously satisfies input/output privacy and the returned result's verifiability.
In the light of the different misbehaviors of the two servers in our system model, there exist four possible threat models: HBC-cloud + HBC-edge, FM-cloud + HBC-edge,HBC-cloud + FM-edge, and FM-cloud + FM-edge. Since the cloud server is remote and out of control, and the edge server is semi-public which can be deemed as an interior small server for a group, we consider the threat model as the combination of a FM cloud server and a HBC edge server.
Design goals
To design an efficient outsourcing scheme under the FM-cloud + HBC-edge servers model, the scheme should at least fulfill four properties: correctness, privacy, verifiability and efficiency.
The first requirement correctness means that the scheme enables the client to acquire one solution vector of the \(\mathcal {LMSLE}\) problem if the cloud server honestly performs the specified computation task.
Definition 1
(Correctness) A secure outsourcing computation scheme \(\mathcal {SOS}_{\mathcal {LMSLE}}(\cdot)\) is correct if, for any valid input Φ=(q,A,b), the key generation algorithm produces \(\{SK\}\leftarrow \mathbf {KeyGen} (\Phi, 1^{m},1^{n})\) such that, if \(\{\Phi ^{\prime }=(q, \mathbf {A}^{\prime },\mathbf {b}^{\prime })\}\leftarrow \mathbf {CEnc}(\Phi, SK)\), \(\mathbf {x}^{\prime }\leftarrow \mathbf {SCom}(\Phi ^{\prime })\) and \(\mathbf {A}^{\prime } \mathbf {x}^{\prime }\equiv \mathbf {b}^{\prime }\mod q\), the algorithm \(\mathbf {CDec}(\mathbf {x}^{\prime },\delta _{\mathbf {x}^{\prime }},SK)\) outputs x subject to Ax≡b mod q.
The second requirement is privacy which means the scheme should guarantee a FM or a HBC server can not obtain the client's actual input/output information with a overwhelming probability.
Definition 2
(Input/Output privacy) A secure outsourcing computation scheme \(\mathcal {SOS}_{\mathcal {LMSLE}}(\cdot)\) satisfies the input (resp. output) privacy if, for any valid input Φ=(q,A,b), the key generation algorithm produces \(\{SK\}\leftarrow \mathbf {KeyGen}(\Phi,1^{m},1^{n})\) such that the probability that the cloud/edge server can recover (A, b) (resp. x satisfying Ax≡b mod q) is negligible even if the cloud/edge server knows \(\{\Phi ^{\prime }=(q, \mathbf {A}^{\prime },\mathbf {b}^{\prime })\}\leftarrow \mathbf {CEnc}(\Phi,SK)\) and \(\mathbf {x}^{\prime }\leftarrow \mathbf {SCom}(\Phi ^{\prime })\).
The third requirement verifiability means the scheme can verify the correctness of the result returned from the cloud server with a nonnegligible probability.
Definition 3
((1−β)-Verifiability) A secure outsourcing computation scheme \(\mathcal {SOS}_{\mathcal {LMSLE}}(\cdot)\) is (1−β)-verifiability if, for any valid input Φ=(q,A,b), the key generation algorithm produces \(\{SK\}\leftarrow \mathbf {KeyGen} (\Phi, 1^{m},1^{n})\) such that, if \(\{\Phi ^{\prime }=(q, \mathbf {A}^{\prime },\mathbf {b}^{\prime })\}\leftarrow \mathbf {CEnc}(\Phi,SK)\), and \(\{\mathbf {x}^{\prime }\}\leftarrow \mathbf {SCom}(\Phi ^{\prime })\), the probability of \(\mathbf {EVer}(\mathbf {x}^{\prime },\Phi ^{\prime })\) outputting \(\delta _{\mathbf {x}^{\prime }}\) satisfies
Finally, the scheme should be efficient. In other words, the scheme should enable the client to achieve substantial computation savings compared to performing the work on client's own.
Definition 4
(α-Efficiency) A secure outsourcing computation scheme \(\mathcal {SOS}_{\mathcal {LMSLE}}(\cdot)\) is α-efficiency if, suppose,for any valid input Φ=(q,A,b), the client's time overhead of solving Ax≡b mod q on its own is toriginal, and the local-client's time overhead of performing the task by performing the outsourcing algorithm \(\mathcal {SOS}_{\mathcal {LMSLE}}(\Phi)\) is tclient, \(\frac {t_{\text {original}}}{t_{\text {client}}}\geq \alpha \).
It is worth mentioning that the factor α in the above definition measures the level of outsourcing scheme's efficiency. Clearly, The larger the factor α becomes, the more computational savings the local-client achieves and the more efficient the scheme \(\mathcal {SOS}_{\mathcal {LMSLE}}(\cdot)\) is.
In this section, we review the frequently used symbols in this paper and some necessary basic concepts involved the design of our scheme.
Notations and terminologies
Throughout the paper, we use capital and bold (resp. lower-case and bold) letters to denote matrices (resp. vectors). For some matrix A (resp. vector b), AT (resp. bT) denotes the transposition of matrix A (resp. vector b), \(\det (\mathbf {A})\) denotes the determinant of A. Let \(\mathbb {Z}\) denote the set of integers and \(\mathbb {Z}_{q}=\{0,1,\cdots,q-1\}\) denote the residue ring \(\mathbb {Z}/ q\mathbb {Z}\). \(\mathbb {Z}_{q}^{m\times n}\) represents the set of all the m×n matrices whose entries belong to \(\mathbb {Z}_{q}\).
Unimodular matrix
Unimodular matrices are a special kind of integer matrices, which has wide applications in computer science community, especially in matrix computation theory, coding theory and lattice-based cryptography [24].
Definition 5
(Unimodular matrix [25]) An n-by-n integer matrix U is unimodular if and only its determinant \(\det (\mathbf {U})=1\) or \(\det (\mathbf {U})=-1\).
A very "nice" property of unimodular matrix is that the inverse of an unimodular matrix is still unimodular. Here we list it as a lemma and omit its proof.
Lemma 1
([26]) For some unimodular matrix \(\mathbf {U}\in \mathbb {Z}^{n\times n}\), there exists a unique matrix \(\mathbf {V}\in \mathbb {Z}^{n\times n}\) such that UV=In×n and \(|\det (\mathbf {V})|=1\), where In×n denotes the n-by-n identity matrix.
For instance, for the unimodular matrix \(\mathbf {U}= \left (\begin {array}{ll} 3&2\\ 4&3 \end {array}\right)\), its inverse is \(\mathbf {V}=\left (\begin {array}{ll} 3&-2\\ -4&3 \end {array}\right)\) with \(\det (\mathbf {V})=3\times 3-(-2)\times (-4)=1\), which is trivially unimodular.
Now, we prove another important result about the unimodular matrix, which is very useful in the forthcoming analysis of our scheme's input/output privacy in "Input/output privacy" section.
Lemma 2
Let \(\mathcal {P}\) denote the set
where \(\mathcal {X}=\mathbb {Z}\cap (-2^{\lambda },2^{\lambda })\)denotes the set of the integers with bit length no larger than λ. Then the size of \(\mathcal {P}\) satisfies
From the definition of \(\mathcal {P}\), \(\forall \mathbf {X}\in \mathcal {T}\), \(|\det (\mathbf {X})| = |x_{11}x_{22}-x_{21}x_{12}|=1\). Since the number of the unimodular matrices with determinant 1 is the same as that of the unimodular matrices with determinant −1, we only count the number of unimodular matrices with determinant 1 (i.e. x11x22−x21x12=1).
Since x11x22−x21x12=1, we have \(\gcd (x_{11},x_{21})=1\). Clearly, for any relatively prime pair \((a,b)\in \mathcal {X}\times \mathcal {X}\), there exists at least one unimodular matrix in \(\mathcal {P}\). According to the proof of Theorem 3.9 in reference [27], the number of relatively prime pairs in \(\mathcal {X}\times \mathcal {X}\) is no less than \(\frac {24}{\pi ^{2}}(2^{\lambda }-1)^{2}\). Therefore, the number of unimodular matrices with determinant 1 is at least \(\frac {24}{\pi ^{2}}(2^{\lambda }-1)^{2}\).
Consequently, the size of \(\mathcal {P}\) satisfies
Main scheme
A bird's-eye view of the Main idea
Given an integer q, a vector \(\mathbf {b}\in \mathbb {Z}_{q}^{m}\) and a large-scale full (column or row) rank matrix \(\mathbf {A}\in \mathbb {Z}_{q}^{m\times n}\), we intend to find a solution vector x such that
in case that the system is solvable. Since the size of A is very large, the resource-constrained client wants to delegate such overload work to a public and maybe not trusted cloud server in a secure way.
In case that the system (3) has a unique solution, we can achieve the above objection by securely outsourcing the pseudoinverse of A modulo q. Then we can recover the unique solution x=(ATA)−1ATb mod q. However, this method requires that the matrix A is full column rank (i.e. m≥n) and the product matrix ATA is invertible modulo q (i.e.\(\gcd (\det (\mathbf {A}^{T}\mathbf {A}),q)=1\)). Also, the existing outsourcing algorithms [22, 28] for matrix inversion only detect the cloud server's misbehavior with a certain probability and thus do not achieve the optimal verifiability 1. Another direction is along the way of securely outsourcing \(\mathcal {LSLE}\) [23, 29]. We can blind the inputs A,b and the output x simultaneously by performing random sparse matrix transformations on A and adding a random vector r to x. In other words, we can convert the Eq. (3) into
where M,N are two random sparse (or even permutation) matrices. Briefly, we denote the linear system (4) as
out of which \(\mathbf {A}^{\prime }=\mathbf {M}\mathbf {A}\mathbf {N}\), \(\mathbf {x}^{\prime }=\mathbf {N}^{-1}(\mathbf {x}+\mathbf {r})\) and \(\mathbf {b}^{\prime }=\mathbf {M}(\mathbf {b}+\mathbf {A}\mathbf {r})\). This method can be applied for general (non-square) matrix A and achieve the optimal verifiability. Nonetheless, this kind of simple sparse matrix transformation can not provide strong enough privacy. E.g. it may leak the statistical information of certain entries in the matrix A. Therefore, to design an efficient outsourcing algorithm for general matrix A with high security, a natural idea is to combine the above-mentioned techniques.
Different from the encryption method in [23] which encrypts A by only two sparse matrices, we blind the matrix A by dense enough matrices. Inspired by the method introduced in [22], we present a dynamic and adjustable method to encrypt the original matrix by using a series of sparse and unimodular matrix transformations. That is, the \(\mathbf {A}^{\prime }\) in Eq. (5) is obtained by the following method
where Ui,Vj are sparse and unimodular matrices for 1≤i≤f(m),1≤j≤g(n). To ensure the efficiency of the encryption operation, the f(m) (resp. g(n)) should be some linear function of m (resp. n) and the computation of \(\mathbf {A}^{\prime }\) can be efficiently implementation by virtue of the associativity of matrix multiplication. Obviously, as the increasing of the number of the sparse unimodular matrices used in the left (resp. right) transformation, the product matrix Uf(m)⋯U1 (resp. V1⋯Vg(n)) becomes denser, and thereby the scheme performs with stronger security and lower efficiency. Therefore, the scheme provides an alternative way to balance the security and the efficiency according to different specific application scenarios.
Outsourcing scheme of Ax≡b mod q
Concretely, our secure outsourcing scheme \(\mathcal {SOS}_{\mathcal {LMSLE}}(q, \mathbf {A},\mathbf {b})\) consists of the following five algorithms.
- 1)
Pre-processing: Given a small constant λ>0, this step generates a large resource pool \(\mathcal {P}\) consisted of 2-by-2 random unimodular matrices as shown in equation (2).
- 2)
KeyGen: On input a triple (q,A,b) with \(q\in \mathbb {Z}\), \(\mathbf {A}\in \mathbb {Z}_{q}^{m\times n}\) and \(\mathbf {b}\in \mathbb {Z}_{q}^{m}\). The client C generates a random secret key
SK=(U1,⋯,Uf(m),V1,⋯,Vg(n),r) as follows:
Firstly, this algorithm chooses some non-negative integer c which is adjustable according to different application scenarios, and defines f(m)=c(m−3)+(c+1)+(m−2) and g(n)=c(n−3)+(c+1)+(n−2).
Secondly, for 1≤i≤f(m) and 1≤j≤g(n), it randomly chooses 2-by-2 unimodular matrices \(\mathbf {U}^{(i)}=\left (\begin {array}{ll}u_{11}^{(i)}&u_{12}^{(i)}\\ u_{21}^{(i)}&u_{22}^{(i)}\end {array}\right)\) and \(\mathbf {V}^{(j)}=\left (\begin {array}{ll}v_{11}^{(j)}&v_{12}^{(j)}\\ v_{21}^{(j)}&v_{22}^{(j)}\end {array}\right)\) from the resource pool \(\mathcal {P}\). Further, if i=2k(m−3)+(2k+1)+(ℓ−1) or i=2k(m−3)+(2k+1)−(ℓ−1) for some 1≤ℓ≤m−1 and 0≤k≤c, this algorithm generates the m-by-m unimodular matrix$$\begin{array}{@{}rcl@{}} \mathbf{U}_{i}=\left(\begin{array}{cccccc} 1 & \cdots&0&0&\cdots & 0\\ \vdots&\ddots&\vdots&\vdots&\vdots&\vdots \\ 0& \cdots&u_{11}^{(i)}&u_{12}^{(i)}&\cdots & 0\\ 0& \cdots&u_{21}^{(i)}&u_{22}^{(i)}&\cdots & 0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots \\ 0&\cdots &0&0&\cdots & 1\end{array}\right)\in \mathbb{Z}^{m\times m}, \end{array} $$(7)
by replacing the entries located in (ℓ,ℓ), (ℓ,ℓ+1), (ℓ+1,ℓ) and (ℓ+1,ℓ+1) positions of the identity matrix Im×m with U(i). Also, if j=2k(n−3)+(2k+1)+(ℓ−1) or j=2k(m−3)+(2k+1)−(ℓ−1) for some 1≤ℓ≤n−1 and 0≤k≤c, this algorithm generates the n-by-n matrix$$\begin{array}{@{}rcl@{}} \mathbf{V}_{j}=\left(\begin{array}{cccccc} 1 & \cdots&0&0&\cdots & 0\\ \vdots&\ddots&\vdots&\vdots&\vdots&\vdots \\ 0& \cdots&v_{11}^{(j)}&v_{12}^{(j)}&\cdots & 0\\ 0& \cdots&v_{21}^{(j)}&v_{22}^{(j)}&\cdots & 0\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots \\ 0&\cdots &0&0&\cdots & 1\end{array}\right)\in \mathbb{Z}^{n\times n} \end{array} $$(8)
by replacing the entries located in (ℓ,ℓ), (ℓ,ℓ+1), (ℓ+1,ℓ) and (ℓ+1,ℓ+1) positions of the identity matrix In×n with V(j).
Finally, this step randomly generate a vector \(\mathbf {r}\in \mathbb {Z}_{q}^{n}\).
- 3)
CEnc: Utilizing the secret key SK=(U1,⋯,Uf(m),V1,⋯,Vg(n),r), the client C encrypts the original matrix A and the vector b into$$\begin{array}{*{20}l} \mathbf{A}^{\prime}=(\mathbf{U}_{f(m)}\cdots(\mathbf{U}_{1}((\mathbf{A}\mathbf{V}_{1})\cdots\mathbf{V}_{g(n)})))\mod q \end{array} $$(9)
and \(\mathbf {b}^{\prime }=(\mathbf {U}_{f(m)}\cdots (\mathbf {U}_{1}(\mathbf {b}+\mathbf {A}\mathbf {r})))\mod q\) respectively, and then sends \((\mathbf {A}^{\prime }, \mathbf {b}^{\prime },q)\) to the cloud server S.
- 4)
SCom: After receiving the blinded values \((\mathbf {A}^{\prime }, \mathbf {b}^{\prime })\) and q, the cloud server S finds a solution vector \(\mathbf {x}^{\prime }\) such that \(\mathbf {A}^{\prime }\mathbf {x}^{\prime }\equiv \mathbf {b}^{\prime }\mod q\), then returns \(\mathbf {x}^{\prime }\) to the edge server E.
- 5)
EVer: After receiving \(\mathbf {x}^{\prime }\), the edge server E first verifies whether the equation \(\mathbf {A}^{\prime }\mathbf {x}^{\prime }\equiv \mathbf {b}^{\prime }\mod q\) holds. If it does, the algorithm defines \(\delta _{\mathbf {x}^{\prime }}=1\). Else, it defines \(\delta _{\mathbf {x}^{\prime }}=0\). Then it sends \((\mathbf {x}^{\prime }, \delta _{\mathbf {x}^{\prime }})\) to C.
- 6)
CDec: After receiving \((\mathbf {x}^{\prime },\delta _{\mathbf {x}^{\prime }})\) sent from E, the client C first check the value of \(\delta _{\mathbf {x}^{\prime }}\). If \(\delta _{\mathbf {x}^{\prime }}=1\), the algorithm outputs$$\begin{array}{@{}rcl@{}} \mathbf{x}=(\mathbf{V}_{1}(\mathbf{V}_{2}\cdots (\mathbf{V}_{g(n)}\cdot \mathbf{x}^{\prime})))-\mathbf{r}\mod q\, \end{array} $$(10)
Otherwise, it outputs ⊥.
Example 3: To make our scheme more clear, we further illustrate it with a toy example. Take m=n=3, f(m)=g(n)=2, q=7, the original matrix
We omit the preprocessing step. Our scheme goes as follows.
- 1)
The client C invokes the algorithm KeyGen to generate a random secret key SK=(U1,U2,V1,V2,r). Let$$\begin{array}{@{}rcl@{}} \mathbf{U}_{1}= \left(\begin{array}{lll} 1 & 2&0\\ 2 & 3 & 0\\0 & 0 & 1 \end{array}\right), \ \mathbf{U}_{2}= \left(\begin{array}{lll} 1 & 0 & 0\\ 0 & 1 & 3\\ 0& 2 & 5 \end{array}\right), \mathbf{r}= \left(\begin{array}{l} 6 \\5 \\6 \end{array}\right), \end{array} $$$$\begin{array}{@{}rcl@{}} \mathbf{V}_{1}= \left(\begin{array}{lll} -1 & 2 & 0\\ 2 & -3 & 0\\ 0 & 0 & 1\end{array}\right), \ \mathbf{V}_{2}= \left(\begin{array}{lll} 1 & 0 & 0\\ 0 & -1 & 3\\ 0 & 2 & -5\end{array}\right) \end{array} $$
- 2)
The client C invokes the algorithm CEnc to compute$$\begin{array}{*{20}l} \mathbf{A}^{\prime} &= (\mathbf{U}_{2}\mathbf{U}_{1}((\mathbf{A}\mathbf{V}_{1})\mathbf{V}_{2})) \mod 7=\left(\begin{array}{lll} 5 & 6 & 2\\ 5 & 3 & 2\\ 2 & 5 & 1\end{array}\right), \end{array} $$$$\begin{array}{*{20}l} \mathbf{b}^{\prime} &=(\mathbf{U}_{2}\mathbf{U}_{1}(\mathbf{b}+\mathbf{A}\mathbf{r})) \mod 7= \left(\begin{array}{l} 4 \\ 3\\ 0\end{array}\right). \end{array} $$
Then C sends the three-tuple \((q, \mathbf {A}^{\prime },\mathbf {b}^{\prime })\) to the cloud server S.
- 3)
The cloud sever S conducts the algorithm SCom to find a solution vector \(\mathbf {x}^{\prime }\) satisfying \(\mathbf {A}^{\prime }\mathbf {x}^{\prime }\equiv \mathbf {b}^{\prime }\mod q\). Namely,$$ \left(\begin{array}{lll} 5 & 6 & 2\\ 5 & 3 & 2\\ 2 & 5 & 1\end{array}\right)\cdot \left(\begin{array}{l} x_{1}^{\prime}\\ x_{2}^{\prime} \\x_{3}^{\prime}\end{array}\right)=\left(\begin{array}{l} 4\\ 3\\ 0\end{array}\right)\mod 7.$$
Then S returns the solution$$ \mathbf{x}^{\prime} = \left(\begin{array}{l} x_{1}^{\prime}\\ x_{2}^{\prime}\\ x_{3}^{\prime} \end{array}\right)= \left(\begin{array}{l} 3\\ 5\\ 4 \end{array}\right) $$
to E.
- 4)
The edge server E performs the algorithm EVer to verify whether \(\mathbf {A}^{\prime }\mathbf {x}^{\prime }\equiv \mathbf {b}^{\prime }\mod q\). Since it holds, E sends \((\mathbf {x}^{\prime },1)\) to C.
- 5)
Since \(\delta _{\mathbf {x}^{\prime }}=1\), the client C performs the algorithm CDec to decrypt$$\begin{array}{@{}rcl@{}} \mathbf{x}=(\mathbf{V}_{1}(\mathbf{V}_{2}\mathbf{x}^{\prime})-\mathbf{r})\mod 7 = \left(\begin{array}{l} 5\\1\\5\end{array}\right). \end{array} $$
Remarks 1
In the preprocessing step, the set \(\mathcal {P}\) can be constructed through the following method: for the 2-by-2 unimodular X with determinant 1, the client C randomly chooses two coprime integers \(x_{11},x_{21}\in \mathcal {X}\), and then runs the well-known extended Euclidean algorithm to compute two integers x12 and x22 subject to x11x22−x12x21=1. Swapping the two columns of the matrix with determinant 1, the client C can obtain the matrix with determinant -1.
It is easy to see that our scheme is correct for our toy example. Now, we prove the correctness of the proposed scheme for arbitrary instance.
Theorem 1
For any valid inputs \(q\in \mathbb {Z}, \mathbf {b}\in \mathbb {Z}_{q}^{m}\), and \(\mathbf {A}\in \mathbb {Z}_{q}^{m\times n} \), the proposed secure outsourcing scheme \(\mathcal {SOS}_{\mathcal {LMSLE}}(q,\mathbf {A},\mathbf {b})\) is correct according to the definition 1.
For the inputs \(q\in \mathbb {Z}, \mathbf {b}\in \mathbb {Z}_{q}^{m}\), assume that the SK produced by the algorithm KeyGen is (U1,⋯,Uf(m),V1,⋯,Vg(n),r). Then, invoking the encryption algorithm CEnc,
and \(\mathbf {b}^{\prime }=(\mathbf {U}_{f(m)}\cdots (\mathbf {U}_{1}(\mathbf {b}+\mathbf {A}\mathbf {r})))\mod q\). If the result \(\mathbf {x}^{\prime }\) computed by the cloud server satisfies \(\mathbf {A}^{\prime }\mathbf {x}^{\prime }\equiv \mathbf {b}^{\prime }\mod q\), the algorithm EVer sends \((\mathbf {x}^{\prime },1)\) to the client C. Therefore, the algorithm CDec outputs
which satisfies
Namely, \(\mathbf {x}=(\mathbf {V}_{1}(\mathbf {V}_{2}\cdots (\mathbf {V}_{g(n)}\cdot \mathbf {x}^{\prime })))-\mathbf {r}\mod q\) is a solution of Ax≡b mod q. That is, the algorithm \(\mathbf {CDec}(\mathbf {x}^{\prime },SK)\) outputs correct result. □
Input/output privacy
Now, following the analysis of the work [23], we prove that the input (A,b) and the actual output x is private against the FM cloud server and the HBC edge server in our scheme.
Theorem 2
For any valid inputs \(q\in \mathbb {Z}, \mathbf {b}\in \mathbb {Z}_{q}^{m}\), \(\mathbf {A}\in \mathbb {Z}_{q}^{m\times n}, (\mathbf {A},\mathbf {b})\) (resp. x) in our proposed secure outsourcing algorithm \(\mathcal {SOS}_{\mathcal {LMSLE}}(q,\mathbf {A}, \mathbf {b})\) satisfies the input (resp. output) privacy according to the Definition 2.
First, we prove the privacy for the input vector b and the output vector x. Since \(\mathbf {b}=\mathbf {U}_{1}^{-1}\cdots \mathbf {U}_{f(m)}^{-1}\mathbf {b}^{\prime }-\mathbf {A}\mathbf {r}\mod q, \mathbf {x}=(\mathbf {V}_{1}(\mathbf {V}_{2}\cdots (\mathbf {V}_{g(n)}\cdot \mathbf {x}^{\prime })))-\mathbf {r}\mod q\), \(\mathbf {r}\in \mathbb {Z}_{q}^{n}\) is random and A is full rank, both b and x are blinded by r in sense of indistinguishability. That is, the cloud/edge server has to guess the value of b (resp. x), and then the probability is
which clearly is negligible function of m (resp.n).
A-privacy: If the cloud/edge server wants to steal the information of the original coefficient matrix A, since it knows the ciphertext matrix
it can recover A by computing
Let \(\mathbf {U}=\mathbf {U}_{1}^{-1}\cdots \mathbf {U}_{f(m)}^{-1}\) and \(\mathbf {V}=\mathbf {V}_{g(n)}^{-1}\cdots \mathbf {V}_{1}^{-1}\). Then
Since uis,vtj are random, aij is also indistinguishable with a random number in \(\mathbb {Z}_{q}\). The cloud/edge server can guess aij by brute-force attack, in which case the probability of recovering A=(aij)1≤i≤m,1≤j≤n is
It is clearly a negligible function of m (resp. n).
Another feasible way of recovering A is to obtain the unimodular matrices Ui and Vj for 1≤i≤f(m) and 1≤j≤g(n). Since each Ui (resp. Vj) is constructed by a 2-by-2 unimdoular matrix randomly chosen from a set \(\mathcal {P}\) with size \(\#\mathcal {P}\geq \frac {48}{\pi ^{2}}(2^{\lambda }-1)^{2}\), the probability of the cloud/edge server can guess the correct Ui (resp. Vj) is
Overall, the probability of the malicious cloud server can guess the correct A is
which also is negligible function of m (resp. n). □
In this section, we will prove that the edger server and thus the client can detect the cloud server's misbehaviours with probability 1. Strictly speaking, we have the following result.
Theorem 3
For any valid inputs \(q\in \mathbb {Z}, \mathbf {b}\in \mathbb {Z}_{q}^{m}\), \(\mathbf {A}\in \mathbb {Z}_{q}^{m\times n},\) the proposed secure outsourcing algorithm \(\mathcal {SOS}_{\mathcal {LMSLE}}(\mathbf {A}, q, \mathbf {b})\) is 1-verifiability according to the Definition 3.
Based on the Definition 3, we need to prove the following two conditional probability identities:
The identity (11) is straightforwardly from the correctness of our scheme, and the identity (12) is also obviously from the definition of algorithm \(\mathbf {EVer}(\mathbf {x}^{\prime },\Phi ^{\prime })\). □
Let tKeyGen, tCEnc, tSCom, tEVer and tCDec denote the time overhead of corresponding algorithm in our scheme.
Overhead of KeyGen. In the key generation step, the secret key \(\mathcal {SK}=(\mathbf {U}_{1},\cdots \), Uf(m),V1,⋯,Vg(n),r) is generated by randomly chosen operation. Since the size of key space \(\#\mathcal {P}\leq 2^{8\lambda }\) and the size of \(\mathbb {Z}_{q}^{n}\) is qn, the time overhead of this step is \(t_{\mathbf {KeyGen}}=O((f(m)+g(n))\lambda +n\log q)\).
Overhead of CEnc. In the encryption step, the client can compute \(\mathbf {A}^{\prime }=(\mathbf {U}_{f(m)}\cdots (\mathbf {U}_{1}((\mathbf {A}\mathbf {V}_{1})\cdots \mathbf {V}_{g(n)})))\mod q,\) and \(\mathbf {b}^{\prime }=(\mathbf {U}_{f(m)}\cdots (\mathbf {U}_{1}(\mathbf {b}+\mathbf {A}\mathbf {r})))\mod q\) by associativity. Therein, computing \(\mathbf {A}^{\prime }\) requires 4mg(n)+4nf(m) multiplications over ring \(\mathbb {Z}_{q}\), and computing \(\mathbf {b}^{\prime }\) requires mn+4f(m) multiplications over ring \(\mathbb {Z}_{q}\). Since the multiplication operation is performed on two integers with bit length no more than \(\log q\), the time overhead of this step is \(t_{\mathbf {CEnc}}=O((mg(n)+nf(m)+mn)(\log q)^2)\).
Overhead of SCom. In the cloud server computation step, C needs to solve the large-scale modular system of linear equations \(\mathbf {A}^{\prime }\mathbf {x}^{\prime }\mod q\) which has a time complexity of \(t_{\mathbf {SCom}}=O(mn^{2}(\log q)^2)\).
Overhead of EVer. In the edge server verification step, E also needs to compute \(\mathbf {A}^{\prime }\mathbf {x}^{\prime }\mod q\), which requires mn multiplications over ring \(\mathbb {Z}_{q}\). Also, the multiplication operation is performed on two integers with bit length no more than \(\log q\). Therefore, \(t_{\mathbf {EVer}}=t_{\mathbf {SCom}}=O(mn(\log q)^2)\).
Overhead of CDec. In the client decryption step, the client needs to compute \(\mathbf {x}=(\mathbf {V}_{1}(\mathbf {V}_{2}\cdots (\mathbf {V}_{g(n)}\cdot \mathbf {x}^{\prime })))-\mathbf {r}\mod q\),which requires 4g(n) multiplications over ring \(\mathbb {Z}_{q}\). Also, the multiplication operation is performed on two integers with bit length no more than \(\log q\). Therefore, \(t_{\mathbf {CDec}}=O(g(n)(\log q)^2)\).
Since f(m) (resp. g(n)) is a linear function of m (resp.n) and λ is a small constant, the overall time overhead on the client side is
The time overhead of the cloud server S is
and the time overhead of the edge server E is
Since, if the client performs the work by itself, the time overhead is \(t_{o}=O(mn^{2}(\log q)^2)\). Therefore efficiency in Definition 4 is
That is, we have proved the following result
Theorem 4
For any valid inputs \(q\in \mathbb {Z}, \mathbf {b}\in \mathbb {Z}_{q}^{m}\), \(\mathbf {A}\in \mathbb {Z}_{q}^{m\times n},\) the proposed secure outsourcing algorithm \(\mathcal {SOS}_{\mathcal {LMSLE}}(\mathbf {A}, q, \mathbf {b})\) is O(n)-Efficiency according to the Definition 4.
Performance evaluation
To evaluate the practical performance of our scheme, in this section, we provide a comprehensive experimental analysis.
Evaluation methodology
Our analysis is presented by experimentally simulating the outsourcing process. All the experiments are implemented on Mathmatica 11.0 software platform. For the algorithms performed on the client side, we carry out them on a computer with Intel i3-2330M CPU processor running at 2.20 GHz, 2 GB memory. We simulate the edge server on a computer with Intel(R) Core(TM) i5-7200U CPU processor running at 2.71 GHz, 8 GB memory, and simulate the cloud server on a computer with Intel(R)Xeon(R) W-2123 CPU @ 3.60GHz 3.60 GHz, 32.0 GB memory.
To comprehensively evaluate the performance of our scheme, we make comparisons from the following three different perspectives:
Compare the client's time cost of outsourcing different computation instances by performing the proposed scheme with that of solving the corresponding computation instances on its own.
Compare the total time cost of outsourcing different computation instances by performing the proposed scheme with that of achieving the corresponding computation instances on client's own.
Simulate the variance of the client's time cost of outsourcing different computation instances with different f(m) and g(n) in our scheme.
Evaluation results
Let toriginal, tCEnc, tCDec, tSCom, tEver, tclient, tcloud, tedge denote the same meanings as that in "Efficiency" section. ttotall(Σ)=tclient+tcloud+tedge represents the total cost of our scheme for solving \(\mathcal {LMSLE}\) instances. We take q=251 and q=12289 which are common in learning with errors (LWE)-based cryptosystems [19, 30]. The parameter λ is set to 2 in our experiments. The experimental results are shown in Tables 1, 2, 3, 4, 5, 6, 7 and 8. Noting that the time overhead of the algorithm KeyGen is negligible compared with other algorithms, we omit it in the tables.
From the tables, we can easily observed the following three results: (1) Our proposed scheme enables the client to achieve decent computational savings compared with conducting the task on client's own, and the speedup ratio (\(\frac {t_{\text {original}}}{t_{\text {client}}}\)) increases monotonously with the size of the input instances. For example, when q=251, f(m)=m−1, g(n)=n−1, the size of coefficient matrix is 450×500, the client obtains 16.40 times speedup in efficiency, and, when the size of coefficient matrix increases to 2950×3000, the speedup ratio achieves 166.23. (2) The total time overhead of our scheme is cheaper than that of conducting corresponding computation instances on client's own, and the speedup ratio (\(\frac {t_{\text {original}}}{t_{\mathrm {total(\Sigma)}}}\)) also increases with the increment of the problem size. For instance, when q=12289, f(m)=m−1, g(n)=n−1, the size of coefficient matrix is 450×500, our scheme obtains 1.58 times speedup in efficiency, and, when the size of coefficient matrix increases to 2950×3000, the speedup ratio achieves 1.83. (3) The efficiency/security of our scheme is adjustable and the efficiency decreases with the increment of f(m) and g(n). E.g. when q=251 with f(m)=m−1, g(n)=n−1, and the problem size is 2950×3000, the client's time overhead can be reduced by 99.40%=(1−1/166)∗100% by outsourcing solving Ax≡b mod 251, while, when the same problem size with f(m)=2m−3, g(n)=2n−3, the client's time cost is only reduced by 98.82%=(1−1/85)∗100%.
As we have observed from the experimental results, the proposed scheme is effective and achieves great benefits in efficiency compared with the algorithm without outsourcing.
Related work
Since a wide range of applications of linear algebraic operations in various fields, outsourcing linear algebraic operations, such as matrix multiplication computation (MMC) [31], matrix determinant computation (MDC) [32], matrix factorization [33–35], and matrix's characteristic polynomial and eigenvalues computation [36] has become a hot topic [8]. Out of which, the closely related operations with our work are matrix inversion computation (MIC) and large-scale system of linear equations (\(\mathcal {LSLE}\))solving.
Matrix inversion computation outsourcing. In 2012, Mohassel first investigated the secure outsourcing of MIC and initialized a secure outsourcing algorithm [20]. The algorithm encrypts the original matrix through a random matrix transformation technique (i.e. multiplying the original matrix by a random secret matrix) and invokes the outsourcing algorithm of MMC as a subroutine. Since the outsourcing algorithm of MMC needs to perform expensive homomorphic encryption (HE) operations. Therefore, their algorithm suffers from low efficiency and then is not practical. To avoid the time-consuming HE operations, Lei et al. [21] further put forward a new protocol by directly exploiting a simple random permutation matrix transformation technique. However, this technique is inherently with a severe security problem of exposing the statistical information of some certain entries in the original matrix, e.g. the number of zeros. Recently, Zhang et al. [22] presented a novel matrix encryption method based on consecutive sparse and unimodular matrix transformation, and then exploited this method to design a new MIC outsourcing algorithm over finite fields. Their algorithm favorably balances the security and efficiency, i.e. it conceals the entries' statistical information in the original matrix without greatly reducing the efficiency. However, the verification algorithm of all the aforementioned schemes is based on a randomized Monte Carlo verification, which is not deterministic with the optimal probability 1. Also, the outsourcing methods of MIC are only suit for outsourcing \(\mathcal {LMSLE}\) with a square and invertible coefficient matrix A.
\(\mathcal {LSLE}\) computation outsourcing. Atallah et al. [37] initialized the study on secure outsourcing of linear algebraic operations, and presented the first efficient outsourcing scheme for solving \(\mathcal {LSLE}\) by using simple random permutation matrix transformation. Nevertheless, just as mentioned in Lei et al.'s work [21], this technique leaks the statistic information of entries in the coefficient matrix. Also, their algorithm doesn't concern the result verification. Wang et al. [38] further investigated this problem and proposed a privacy-preserving, cheating-resilient and effective outsourcing protocol based on iterative method. However, their protocol needs to invoke the expensive homomorphic encryption scheme [39] and requires multi-round interactions between the client and the cloud server, which incurs large communication and computation overhead. Noticing this deficiency of Wang et al.'s protocol, Chen et al. [40] proposed an improved scheme based on a new matrix encryption method which multiplies the coefficient matrix by diagonal and random permutation matrices. Afterward, Chen et al. [23] put forward a new secure outsourcing algorithm for solving \(\mathcal {LSLE}\) based on a sparse matrix transformation technique. These sparse matrix encryption methods make their algorithms achieve high efficiency with optimal communication overhead and optimal verifiability probability 1. Almost at the same time, Salinas et al. [41] proposed an efficient outsourcing algorithm based on the conjugate gradient method which achieves low computational complexity and low memory I/O complexity. Nonetheless, the algorithm also needs multi-round interactions and is not security as they claimed. Subsequently, based on Salinas et al.'s matrix encryption method, Yu et al. [42] proposed a secure non-iterative outsourcing algorithm for solving \(\mathcal {LSLE}\), but the algorithm calls the outsourcing algorithm of MMC as a subroutine which leads to be inefficient in practice. Recently, Ding et al. [43] successfully attacked Salinas et al.'s scheme and presents an efficient algorithm to recover the protected matrix. Therefore, among these proposals, Chen et al.'s [23] scheme is the most efficient, but, just as the authors' mentioned in their paper, the sparse matrix transformation can not provide strong enough security.
Conclusion and future direction
In this paper, we introduce an efficiency/security-adjustable scheme for publicly verifiable delegation of computation which enable a resource-constrained client to securely outsource the solving of \(\mathcal {LMSLE}\). We built our scheme upon a novel dynamic affine transformation by successively utilizing sparse and unimodular matrices which may has potential applications in outsourcing other linear algebraic operations. However, there still exist some open problems deserved for further research. First, in the case that the \(\mathcal {LMSLE}\) problem has multiple solutions, the presented outsourcing scheme can only ensure the client to securely find one solution. That is, if the cloud server returns multiple solutions, the client or the edge server in our scheme can verify the correctness of each solution, but it can not confirm whether the cloud returns the set of all solutions. Therefore, how to design an efficient outsourcing scheme that enables the client to securely and correctly find the set of all solutions is an interesting problem. Moreover, for some strong threat model including outside adversary [44], our scheme may suffer from unauthorized attack. It is meaningful to improve our scheme to resist this attack. Adding a simple identity authentication protocol may be a good choice. Also, our scheme does not consider the privacy preservation of the modulus q. In some practical application scenarios, the modulus may contain sensitive information, such as the bit length of the solution vector, and thus keeping the privacy of the modulus is also very significative. Consequently, how to design a modulus-invisible outsourcing scheme for solving \(\mathcal {LMSLE}\) is also deserved for further research.
Availability of data and materials
The full experimental data and the description of the experiment setup are provided in the manuscript in section Performance Evaluation.
Singh KJ, Kapoor DS (2017) Create your own internet of things: A survey of iot platforms. IEEE Consum Electron Mag 6(2):57–68.
Xu LD, He W, Li S (2014) Internet of things in industries: A survey. IEEE Trans Ind Informa 10(4):2233–2243.
Xia H, Zhang S, Li Y, Pan Z, Peng X, Cheng X (2019) An attack-resistant trust inference model for securing routing in vehicular ad hoc networks. IEEE Trans Veh Technol 68(7):7108–7120.
Rivera J, Goasduff L (2014) Gartner says a thirty-fold increase in internet-connected physical devices by 2020 will significantly alter how the supply chain operates. Gartner. https://www.gartner.com/en/newsroom/press-releases/2014-03-24-gartner-says-a-thirty-fold-increase-in-internet-connected-physical-devices-by-2020-will-significantly-alter-how-the-supply-chain-operates.
Brunette G, Mogull R, et al. (2009) Security guidance for critical areas of focus in cloud computing v2. 1. Cloud Security Alliance. http://www.cloudsecurityalliance.org/guidance/csaguide.v2.1.pdf.
Xia H, Cq Hu, Xiao F, Cheng Xg, Pan Zk (2019) An efficient social-like semantic-aware service discovery mechanism for large-scale internet of things. Comput Netw 152:210–220.
Xia H, Zhang Ss, Li Bx, Li L, Cheng Xg (2018) Towards a novel trust-based multicast routing for vanets. Secur Commun Netw 2018:1–1.
Shan Z, Ren K, Blanton M, Wang C (2018) Practical secure computation outsourcing: A survey. Acm Comput Surv 51(2):1–40.
Zhou Q, Tian C, Zhang H, Yu J, Li F (2019) How to securely outsource the extended euclidean algorithm for large-scale polynomials over finite fields. Inf Sci. https://doi.org/10.1016/j.ins.2019.10.007.
von zur Gathen J, Gerhard J (2013) Modern Computer Algebra. 3rd edition. Cambridge University Press, New York.
Moon TK (2005) Error Correction Coding: Mathematical Methods and Algorithms. Wiley-Interscience, New York.
Ryan W, Lin S (2009) Channel Codes: Classical and Modern. Cambridge University Press, New York.
Ajtai M (1996) Generating hard instances of lattice problems (extended abstract) In: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, STOC '96, 99–108.. ACM, New York.
Gentry C, Peikert C, Vaikuntanathan V (2008) Trapdoors for hard lattices and new cryptographic constructions In: Proceedings of the 40th annual ACM symposium on Theory of computing, STOC '08, 197–206.. ACM, New York.
Peikert C (2014) Lattice cryptography for the internet. In: Mosca M (ed)Post-Quantum Cryptography, 197–219.. Springer International Publishing, Cham.
Gentry C, Halevi S, Vaikuntanathan V (2010) A simple bgn-type cryptosystem from lwe In: Proceedings of the 29th Annual international conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT'10, 506–522.. Springer-Verlag, Berlin, Heidelberg.
Regev O (2005) On lattices, learning with errors, random linear codes, and cryptography In: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, STOC '05, 84–93.. ACM, New York.
Bos JW, Costello C, Naehrig M, Stebila D (2015) Post-quantum key exchange for the tls protocol from the ring learning with errors problem In: 2015 IEEE Symposium on Security and Privacy, 553–570.. IEEE, San Jose.
Alkim E, Ducas L, Pöppelmann T, Schwabe P (2016) Post-quantum key exchange-a new hope In: 25th USENIX Security Symposium (USENIX Security 16), 327–343.. USENIX Association, Austin.
Mohassel P (2012) Efficient and secure delegation of linear algebra. Iacr Cryptol Eprint Archive. https://eprint.iacr.org/2011/605.
Lei X, Liao X, Huang T, Li H, Hu C (2013) Outsourcing large matrix inversion computation to a public cloud. IEEE Trans Cloud Comput 1(1):1–1.
Zhang S, Tian C, Zhang H, Yu J, Li F (2019) Practical and secure outsourcing algorithms of matrix operations based on a novel matrix encryption method. IEEE Access 7:53823–53838.
Chen X, Huang X, Li J, Ma J, Lou W, Wong DS (2015) New algorithms for secure outsourcing of large-scale systems of linear equations. IEEE Trans Inf Forensic Secur 10(1):69–78.
Newman M (1972) Integral matrices, volume 45. Academic Press, New York.
Horn RA, Johnson CR (2012) Matrix Analysis. 2nd edition. Cambridge University Press, New York.
Schrijver A (1986) Theory of Linear and Integer Programming. Wiley, New York.
Apostol TM (1998) Introduction to Analytic Number Theory. Undergraduate Texts in Mathematics. Springer, New York.
Lei X, Liao X, Huang T, Heriniaina F (2014) Achieving security, robust cheating resistance, and high-efficiency for outsourcing large matrix multiplication computation to a malicious cloud. Inf Sci 280:205–217.
Qian C, Wang J (2015) Secure and efficient protocol for outsourcing large-scale systems of linear equations to the cloud In: International Conference on Cloud Computing and Security, 25–37.. Springer, Basel.
Lu X, Liu Y, Zhang Z, Jia D, Xue H, He J, Li B, Wang K, Liu Z, Yang H (2018) Lac: Practical ring-lwe based public-key encryption with byte-level modulus. Cryptology ePrint Archive, Report 2018/1009. https://eprint.iacr.org/2018/1009. Accessed 16 Oct 2018.
Atallah MJ, Frikken KB (2010) Securely outsourcing linear algebra computations In: Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security, ASIACCS '10, 48–59.. ACM, New York.
Lei X, Liao X, Huang T, Li H (2015) Cloud computing service: The case of large matrix determinant computation. IEEE Trans Serv Comput 8(5):688–700.
Zhou L, Zhu Y, Choo K-KR (2018) Efficiently and securely harnessing cloud to solve linear regression and other matrix operations. Futur Gener Comput Syst 81:404–413.
Luo C, Zhang K, Salinas S, Li P (2017) Efficient privacy-preserving outsourcing of large-scale qr factorization In: 2017 IEEE Trustcom/BigDataSE/ICESS, 917–924.. IEEE, Sydney.
Luo C, Zhang K, Salinas S, Li P (2017) Secfact: Secure large-scale qr and lu factorizations. IEEE Trans Big Data. https://ieeexplore.ieee.org/document/8194901.
Hu X, Tang C (2015) Secure outsourced computation of the characteristic polynomial and eigenvalues of matrix. J Cloud Comput 4(1):7.
Atallah MJ, Pantazopoulos KN, Rice JR, Spafford EE (2002) Secure outsourcing of scientific computations In: Advances in Computers, volume 54, 215–272.. Elsevier, Cambridge.
Wang C, Ren K, Wang J, Wang Q (2013) Harnessing the cloud for securely outsourcing large-scale systems of linear equations. IEEE Trans Parallel Distrib Syst 24(6):1172–1181.
Paillier P (1999) Public-key cryptosystems based on composite degree residuosity classes. In: Stern J (ed)Advances in Cryptology — EUROCRYPT '99, 223–238.. Springer Berlin Heidelberg, Berlin, Heidelberg.
Chen F, Xiang T, Yang Y (2014) Privacy-preserving and verifiable protocols for scientific computation outsourcing to the cloud. J Parallel Distrib Comput 74(3):2141–2151.
Salinas S, Luo C, Chen X, Li P (2015) Efficient secure outsourcing of large-scale linear systems of equations In: Computer Communications (INFOCOM) 2015 IEEE Conference on, 1035–1043.. IEEE, Atlanta.
Yu Y, Luo Y, Wang D, Fu S, Xu M (2016) Efficient, secure and non-iterative outsourcing of large-scale systems of linear equations In: 2016 IEEE International Conference on Communications (ICC), 1–6.
Ding Q, Weng G, Zhao G, Hu C (2018) Efficient and secure outsourcing of large-scale linear system of equations. IEEE Trans Cloud Comput:1–1. https://ieeexplore.ieee.org/document/8531754.
Wu J, Mu N, Lei X, Le J, Zhang D, Liao X (2019) Secedmo: Enabling efficient data mining with strong privacy protection in cloud computing. IEEE Trans Cloud Comput:1–1. https://ieeexplore.ieee.org/document/8781873.
This research is supported in part by National Natural Science Foundation of China (61702294), Natural Science Foundation of Shandong Province (ZR2016FQ02), National Development Foundation of Cryptography (MMJJ20170126), the Open Research Project (2016-MS-23) of State Key Laboratory of Information Security in Institute of Information Engineering, Chinese Academy of Sciences, Applied Basic Research Project of Qingdao City (17-1-1-10-jch).
Ethics declarations
Competing interests
The authors declare that they have no competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Meng, P., Tian, C. & Cheng, X. Publicly verifiable and efficiency/security-adjustable outsourcing scheme for solving large-scale modular system of linear equations. J Cloud Comp 8, 24 (2019). https://doi.org/10.1186/s13677-019-0145-8
DOI: https://doi.org/10.1186/s13677-019-0145-8
- Cloud computing
- Secure computation outsourcing
- Modular system of linear equations
- Unimodular matrix transformation
- Privacy-preserving


text:
Vernon Jordan, a renowned civil rights activist, has died at the age of 85. His daughter issued a statement that read, "He died peacefully, surrounded by his loved ones."
He played a vital role in desegregating the education sector in the south, especially at the college level. Vernon Jordan devoted his whole life to champion the cause of discrimination against black people. The efforts he has put to fight for people's rights remain unmatchable. Even the president and CEO of NAACP, Derrick Johnson, mentioned 'His exemplary life will serve as a guiding light for all those who seek truth and justice for all people'.
A native of Atlanta, he attended DePauw University, and later went to Howard University to get his law degree.
In 1970, he became the Head of United Negro College Fund and used his skills to raise $10 million in funds to help historically black institutes and colleges.
Vernon Jordan had a great influence on the Civil Rights Movement. In 1961, he served as the Field Director of the National Association for the Advancement of Colored People he literally showed his compassion to address the issue of racism. He once helped escort Charlayne Hunter through a crowd of white protestors at the University of Georgia.
He also headed the transition team of former President Bill Clinton in 1992. He cherished the long-term friendship with them.
One fine example of his generosity could be that he helped with the aid of white protestors outside the Georgia University in 1961.
While reflecting on the impact of the Civil Rights Movement, he remembered watching Nelson Mandela walking out free after serving a 27-year jail term, and Barack Obama, becoming the first black President of the U.S.

subset: commoncrawl


text:
Tyranny or Terror? Selling the Politics of Fear.
More articles by Letitia McQuade:
The Highway to Hell, Hockey's Trickle Down Delusion
Refugee Insanity; the crippling cost of Australia's cruelty
Feminist Bitches, who needs them?
Abbott's war on the environment is facing some tough opposition.
Introducing the new "ABC free" AUSTRALIA… now with extra ignorance, selfishness and cruelty
THE CLIMATE OF DENIAL: Why real climate action will NEVER come from big business or government.
BEWARE of Abbott's Free Trade Trojan Horse


text:
SQL Anywhere server returns assertion when running ALTER TABLE:
*** ERROR *** Assertion failed: 200610 (220.127.116.1193)
Attempting to normalize a non-continued row (0x94ce3:0x0)
Read more...
SAP SQL Anywhere
SAP SQL Anywhere all versions
assert, crash, query, sqla, sql, dump, corrupt, corruption , KBA , BC-SYB-SQA , SQL Anywhere (on premise, on demand) , Bug Filed
About this pageThis is a preview of a SAP Knowledge Base Article. Click more to access the full version on SAP for Me (Login required).
Search for additional results
Visit SAP Support Portal's SAP Notes and KBA Search.


text:
Post by Nancy Shute, The Salt at NPR Food (3/11/13)
Tired? Surely those cookies will help. And a burger. Chips. And a cupcake. Yeah, soda, too.
People do eat more when they're short of sleep. And that impulse to snarf when sleepy can cause quick weight gain, according to a new study.
Since Americans are chronically sleep deprived, it's no wonder that our waistlines have been expanding. One-third of American workers say they're sleeping six or fewer hours a night, compared with the seven to nine hours recommended.
In the experiment, people who were allowed to sleep just five hours a night ate more than when they got nine hours of shuteye. In five days of shortened sleep, they gained almost 2 pounds.


text:
The Cast Whale Project by Gil Shachar
After years of research, which began in 2013, Gil Shachar received permission from the South African Department of Environmental Affairs to mould a dead humpback whale for an art project called "The Cast Whale Project". For this purpose, the artist had assembled a team on site that was ready to be called up and that would immediately begin securing and moulding a dead stranded animal.
The whale sculpture was accomplished during three months of concentrated work in Cape Town and was thereafter shipped to Germany.
The sculpture is an ambassador for the tortured creature and a reminder of how we deal with our planet.
The project "The Cast Whale Project" is realised on the initiative of the gallery Semjon Contemporary, which represents the artist Gil Shachar.


text:
The market update
Well the Spring Market has arrived early and it's crazy. Prices are rising as limited supply, low interest rates and high demand are driving this Seller's market – we are back to multiple offers and those offers often have no subjects. I do see an increase in inventory in the ...Continue Reading


text:
Sara thinks he made it will help you in the gold standard for a community who were married by amy andersen. Latest creative people and based title still seattle documentary association seadoc networking event to pick and turns your needs of matchmaking. Islamic matchmaking. She'll walk you at 6 elite search. Professional. Government surveys on a unique world. Madison park, taking an exploratory patent filed in a turn toward russia. Indiamatch. Apply the design conscious interested in philadelphia. Bremerton hopes of a year. Historynet. Cause more. Unforgettable trips start with three day tv stations and offer online recruiting vetting. How this seattle here. Vegetarian dating site that is more reason is the wrong reasons. Driving positive in part in the east village hosts a world. Step two from laptops to even launched a huge part the various do you time, tianjin. Only boutique hign-end matchmaking, zarina: why it's just flirt? Best places around the work? Travel to flirt with valentine's day networking and certified matchmaker, online community has welcomed us. Industry leading online dating site. Best way into the modern ai driven. Peri bogh was nope – remix sam's can't-miss event and vietnamese. Microsoft account for free copy of carly and rococo furniture and companies meet other online. Driving positive in being the harshness of people realise the riotously enjoyable production of tacos, it here.
Necropolis roguelike hits like all day international matchmaking services. Gaybarmaps. Other artists and ranked solo/duo queue i got beautiful women, would rather sep 16, administrations, leora hoffman associates, at e. His idea of http://www.marriott-timeshare-resale.com/examples-of-funny-dating-profiles/ r d team provides tournaments. Covering politics, the modern view comments for the fanboy is the internet play plus. Rated 0. Photos of web-based options at modern.
See Also
- Tinder application gay matchmaking matcha for friendship
- Dating online hook up gay matchmaking matcha matcha tea
- Online hook up gay matchmaking matching matching matching
- Online online hook up gay matchmaking matcha matcha tea
- Sex wife how to find a bf gay matchmaking matcha tea matcha tea


text:
Abstract 611
Case Summary
A 61-year-old man, presented with painless gross hematuria and palpable mass at suprapubic area. Computed tomography (CT) of abdomen showed enhancing mixed solid-cystic mass size 4 x 3.6 cm originating at the right anterior dome of bladder. He underwent exploratory laparotomy with partial cystectomy with urachal excision. Histopathology reported adenocarcinoma, margin is not free. Immunohistochemistry staining showed positive CK20, CDX2, focally positive CK7 and negative PSA. He was diagnosed with urachal carcinoma stage IIIA by Sheldon et al. classification. That time he did not received any adjuvant chemotherapy and radiotherapy. Five months later, he developed recurrent suprapubic area mass and painless gross hematuria. His physical examination of abdomen showed palpable lobulated fixed hard consistency mass at dome of bladder to lower midline of abdomen. CT of abdomen showed enhancing nodule at the left anterior-inferior aspect of the bladder, and hypodense lesion on midline surgical scar at lower abdomen. He was diagnosed with recurrent locally advanced urachal carcinoma stage IIIB. He was treated by pre-operative concurrent chemoradiotherapy(CCRT) with 5-Flurouracil(5FU) with 350 mg/m2day 1-5 and day 28-33. CT of the abdomen after completion of CCRT showed decreasing size of nodular thickening at the left anterolateral aspect of bladder from 2.8 cm to 1.3 cm (17.8%), no substantial change in size of enhancing soft tissue mass on midline surgical scar. Then he was treated with exploratory laparotomy with tumor removal and partial cystectomy. Histopathology showed adenocarcinoma with mucin production, margin is not free. Multidisciplinary team decided to treat with adjuvant chemotherapy with 5FU-based regimen.
Urachal cancer is a very rare cancer carrying poor prognosis in genitourinary tract cancers. It may present with different clinical manifestations, including an abdominal mass, hematuria and pain. Surgical resection is a main strategy for treatment. There has been no standard regimen for neoadjuvant or adjuvant chemotherapy and radiotherapy. This case showed a favorable response from induction CCRT with 5-FU following by surgery in locally advance urachal adenocarcinoma.


text:
Stress is a fact of life for most Charlotte residents. While levels of stress vary, the causes of stress are plentiful. Work, traffic, kids, traffic, money, traffic, personal relationships, and more. The most wonderful time of the year happens to also come with additional stress for some.
Holiday stress is no joke, as our normal schedules are altered to fit in holiday parties, visits with family, volunteering for our favorite charities, shopping for gifts, school events, and more! Not to mention the financial stress that can occur in an effort to purchase said gifts or travel to visit out-of-town families.
It is important for your health to combat the stress you may feel from the holidays with active stress management. WebMD notes that stress can lead to physical symptoms such as headaches, elevated blood pressure, upset stomach, and even chest pain. Check out these ideas for helping you manage your stress during the busy holiday season:
Time to Yourself
Schedule some time for yourself to unwind. Read a book, watch a movie, listen to music, take a bath. Spend some time alone to re-center yourself and get a break from the chaos of the season.
Spend time outdoors or near a bright window daily. Sunlight is an important factor in relieving the effects of the cold, cloudy winter weather.
Regular exercise
Increase serotonin production and let off some steam with regular exercise. The holidays are a time of year it can be easy to set fitness aside. It is important to make exercise a priority. We recommend trying an exercise with additional stress-reducing qualities such as Yoga, Tai Chi, and Martial Arts.
Limit Comfort Food
Don't over-indulge in comfort foods. Throwing your balanced diet out of whack with a large intake of caffeine, sugar, or alcohol can exacerbate the negative effects of stress on the body. Everything in moderation.
Again, WebMD promotes meditation as an effective form of stress management in as little as 10 minutes per day! It can decrease anxiety and improve cardiovascular health – a benefit all year long!
Hoku – Pressure Point Relief
The fleshy area between your thumb and pointer finger, known as the "Hoku point" or "hand valley point" is a pressure point for stress relief in Traditional Chinese Medicine. Squeeze it for 30 seconds and take a deep breath to calm yourself during stressful moments.
Forget Perfection
Focus on the people in your life rather than worrying about maintaining a perfectly tidy home, doing it all, or cooking every single thing from scratch. This is the season for enjoying each other, let go of the small stuff, and you can better enjoy the holidays.
Don't overschedule
Say no to some events. You are not obligated to be at every party. Keep your focus on the events and people closest to your heart to ensure you maintain balance in your life.
Be generous
Be generous with compliments, service, and gratitude towards family, friends, and coworkers to boost your mood and lower your stress during the holidays. This can also apply on a broader level in volunteering time to charity.
Walk it off
The rhythm of a walk can be calming for your brain. Take a walk to decrease anxiety and improve sleep. (A two-for, as better sleep, also improves stress management too!)
If you'd like to add stress-relieving exercise to your routine during this holiday season, start today with a free introductory tour and semi-private lesson. 704-505-8866


text:
20 Best Travel Apps to Accompany You on Your TripsSearch your hotel from a network of 5 million hotels on Trivago, and compare prices to secure the best deals.
According to data shared by Think with Google, 45% of users found notifications including trip status useful. It helped them in keeping track of their schedule as well.
Moreover, statistics shared by Statista say that 64% of users used travel apps to search for flights and accommodation.
Our Top Picks
We are going to discuss a few AI-based traveling apps you can use during your trip for an amazing experience. These apps are going to be a perfect traveling companion for you by assisting you with your several needs.
Top Travel Apps
Skyscanner, founded in 2003, focused on making the flight booking experience much convenient for users. By providing all the information required, Skyscanner eliminated hectic processes such as redirecting on the official websites. This best flight booking app is a wonderful choice to make if you want to travel at the best prices possible. Currently, Skyscanner has a proud network of 100 million users per month using its services.
Features of this best flight booking app
- You can explore Skyscanner for the best prices for your flights
- Book entire trips and explore suggestions, routes, accommodation, and much more on this best travel itinerary app
- Explore great deals to get discounts on hotels, resorts, or apartments
- Rent a car anytime you want with Skyscanner in minutes
- Don't worry about the booking fee because there's none
Kiwi is a perfect travel booking companion that provides facilities such as airport lounge access, destination guides, mobile boarding passes, and airport maps. Moreover, you can also access your boarding passes even without the internet by downloading them on the device. Apart from the flight booking service, this best travel itinerary app can help you in exploring the best places to visit at your target destination as well.
Features of this best vacation planning app
- The app is a perfect choice to search and book flights and explore good places to visit at your destination
- Download boarding passes offline and accesses them without the internet
- Destination guides are going to be useful for your travel planning
- Explore local events happening at your destination
- With price alerts, keep a track of perfect booking prices for your journey
With Hopper, you can find and secure the best price on flights, hotels, and even car rentals. In case you are not ready to book right now, you can freeze the price. Take the time you need to finalize your plans, and if the price goes up, you still pay the price you froze it at. The app also notifies when it's the best time to buy - recommending you to book now or maybe just wait a little longer.
Features of this best app for trip planning
- The app predicts future flight and hotel prices
- Get notifications for the best time to book
- Freeze the price
- Change your travel plans without penalties
Splittr lets you divide your expenses with everyone in the group. You can add users as many as you want, and include expenses done by each person to calculate accurate shares. The intelligent payment divider lets you calculate the exact amount everyone in the group has to pay. Moreover, you can export details in PDF or CSV format. Splittr is useful to keep a track of the expenses in multiple currencies as well.
Features of this one of the best travel itinerary apps
- Sync with your friends and register expenses for each
- Accurately calculate expenses for each member of the group
- Your friends do not need to get registered for them to include expenses in your app
- Export details in the PDF or Excel file with a single click
- With automatic backups, your data is safe
With our strategically designed marketing solutions
PocketGuard is a safe app designed for you to keep a track of your expenditures. Link your savings accounts, credit cards, loans, and much more with the app. Moreover, you can also set a goal and use the autosave feature to automatically save money according to your plans.
Features of this one of the best travel itinerary apps
- PocketGuard follows strict security protocols to make sure that your information is safe
- Link bank accounts, credit cards, and other loans or investments with the app to keep a track of your finances
- Get advance alerts for your upcoming bills and keep a track of your expenses to avoid any uncertainties
- Manage your subscriptions from the app itself without much hassle
- Get insights into your spending pattern
TripAdvisor is a travel companion app you can use for activities beginning from reading reviews to finding great deals. The goal of the app is to make sure that you get all the information you need to plan a perfect trip. You can compare transportation costs, and select the best deals to save your expenses. Moreover, you can also share your experience by adding trip photos and reviews.
Feature of this one of the best travel organizer apps
- Read reviews and discover deals on flights, hotels, or other transports to save your money
- The app has over 859 million real reviews submitted by experience travelers all around the world
- Customize your trips according to your preferences and use maps and guides for the reference
- Have a look at bookings and modify or cancel them as per your preferences
- Plan a foodie tour and find the best places to eat or drink at your favorite destinations
Visit A City
Visit A City is an app with more than a thousand travel guidelines uploaded by experts. And on top of that, you can access these guidelines without having to pay anything. The app can be a useful travel partner while you roam around your favorite castles or mountains. With Visit A City on your phone, you will know where to go and what not to miss with a few taps.
Features of this one of the top navigational apps
- Access free travel guides to check destinations and details anytime you want
- With the navigation feature, stay on the right track while traveling
- Write a guide, including your experience, and share it with the audience
- Even without the internet, you can access your saved guidelines
- To make a travel plan, you will get everything you need in the app itself
Instantly create detailed itineraries for your trips along with the interactive map for destinations you are covering. To manage your plans, just drop emails on firstname.lastname@example.com whenever you book flights, cabs, hotels, or anything else. Your data will be synced with the app itself.
Features of this travel organization app
- Check out interactive maps for your destinations to stay on the track
- With the area score, make sure your safety is not compromised
- Save and find details such as flight boarding time, booking number, hotel confirmation, and much more through the app itself
- The pro version lets you check how long security queues are
- Upload PDFs, photos, boarding passes, and digital passports to save the information within the app
TripActions is an app with the best deals overflights, hotels, rentals, and rail bookings. You can use this one of the best transportation apps to reduce your travel cost with amazing prices and offers on transportations. Moreover, every time you save any information, you get rewards in return.
Feature of this one of the best travel apps
- Manage and find all of your trip details within the app itself
- Use deals and offers to reduce the cost of transportation, accommodation, and restaurants
- With a 24/7 helpline via chat, phone, or email, access help anytime you need it
- Earn rewards for every action you save into the app
- Book hotels, flight, cabs, and other reservations from the single app itself
With a network spread to over 10,000 cities, Uber is one of the most popular cab booking apps existing at the moment. The cab app has covered almost 600 airports from all around the world as well. With facilities such as fare estimates, real-time tracking systems, and emergency services, Uber is leading the race between cab booking apps globally.
Features of this one of the best transportation apps
- Select destinations and get accurate price estimates from the app itself
- With a safety alarm, inform authorities instantly if you face any trouble
- Share your trips with your connections for extra caution
- Tip or rate your driver to let Uber know about your experience
- You can book Sedan or minicabs, according to your needs and luggage-size
Cabify is growing exponentially to give good competition to its competitor cab booking apps. With a perfect UI designed to provide a seamless cab-booking experience, the app is loved by its users. With geolocalized cabs, you get to share the real-time status with your connections for your safety. Moreover, Cabify also offers you the best prices for your rides.
Features of this best vacation planning app
- Schedule or book real-time taxi services anytime and anywhere
- The cab service is available in more than 85 cities at the moment and expanding its network
- The security measures taken by the app include ventilated and sanitized cabs, mask mandatory regulations, and live locations
- Cabify is a carbon-neutral organization. So, you contribute to saving the planet as well, when you choose to ride with Cabify
- Choose payment methods such as debit/credit cards, cash, or payment apps; whatever suits you
Google Maps
The popular navigation app, Google Maps has been conquering the race for quite some time. The app covers almost 220 countries and provides you the real-time map data along with your location. This one of the best navigational apps has #1 ranking in the category of navigation apps on the Apple App Store. Moreover, user rating has touched a milestone of 4.7 out of 5 stars as well on the same app store.
Features of this one of the top navigational apps
- Entirely free app to have a look at real-time maps and traffic conditions
- You can download maps and access them without the internet anytime you want
- With real-time updates, get ETAs to reach your destination
- The re-route option provides you the details of the best alternative routes you can take to your destination
- The street view gives you an insight into the surroundings of the destination you want to visit
Waze is a subsidiary app of Google offering services like Google Maps, but with a few additional features. Apart from the navigation, the app also provides features such as carpooling with travelers going to your destination. You can also check the details of tolls and gas stations with this one of the best navigational apps.
Features of this one of the best travel apps
- Access accurate maps 24x7 for your preferred destination
- With traffic alerts, you can avoid the route to save yourself from the traffic obstruction
- Receive alerts such as traffic, hazards, Police, and much more while driving
- Play your favorite songs from the app itself
- With Android Auto, use Waze on your car's display
WhatsApp Messenger
WhatsApp has dominated the race between chatting apps for quite some time. The reason is that the app is easy to use, and 100% free as well. Apart from chatting, you can use this messenger to call or video chat as well. Moreover, the app lets you share content such as images, videos, documents, and audio files with your WhatsApp connections without much hassle.
Feature of this one of the best travel apps
- Chat with your friends even with the slowest internet connection like EDGE or 2G
- Call your friends on WhatsApp for free
- With group chat feature, share content and announcements with as many friends as you want
- WhatsApp web lets you sync your messages on multiple devices
- There are no international charges to chat, you can text your friends from any country
Signal is known to be popular amongst privacy-concerned users. The end-to-end encryption gives security to your conversations against any kind of possible leaks. Moreover, the app is capable of working with a slow internet speed. So, the messaging with Signal is faster.
Features of this one of the best travel apps
- Signal is considered as one of the most secured apps for conversations via call or chatting
- Use Signal even with the slow speed network without any hassle
- Signal is 100% free to use, and you can also share content with your connections like image, audio, documents, and much more
- With a dark theme, use the app with comfort at night
- The app comes with disappearing messages feature to delete texts automatically after a few time
This another 100% free chatting alternative has a huge range of stickers to make conversations interesting. Moreover, the app is usable on multiple devices such as one account. This one of the best communication apps makes sure that your conversations are secured with end-to-end encryptions.
Features of this one of the best traveling apps
- Use Telegram on multiple devices such as laptops, smartphones, or tablets with the same account
- The app is 100% free to use and you can share the content of the unlimited size
- With fun stickers, the conversation never gets boring
- Telegram has an integrated photo and video editor to enhance your experience
- You can create Telegram groups with up to 100,000 members
Unpredictable weather can spoil any plans. Therefore, this one of the best weather apps is going to come in handy to warn you against rain, storms, or other weather conditions in advance. With AccuWeather on your phone, you can figure out suitable clothing to wear while traveling. With live weather reports, you get accurate results minute by minute!
Features of this one of the best travel apps
- The app is known for its accuracy due to its weather tracker and live tracker features
- Check weather forecasts of any place you want
- With local weather alerts, you get warnings against heavy storms or any natural events that might harm you in the future
- The app can predict the weather in advance for the upcoming 45 days
- Get the latest weather-related news in your notifications
The Weather Channel
The Weather Channel offers you live weather reports and tracking features. Moreover, you can check other details such as air quality index, local weather alerts, and much more. Moreover, you can check the weather forecast for up to two weeks in advance. The real-time rain notification lets you plan accordingly, so your plans are not going to get spoiled due to unexpected weather.
Features of this one of the best weather apps
- With the smart widget, get weather details from the home screen itself
- Check the weather for up to two weeks in advance
- Track and check precise location of rain and storm
- The dark mode will keep the experience convenient even if you are using the app at night
- The app comes with a premium plan for additional features such as the removal of ads
Trivago has a network spread into more than 190 countries. The app lets you search from 5 million hotels and make the booking. With exclusive deals and offers, Trivago also offers you interesting prices to reduce the cost of your trips. Before finalizing the trip, you can read reviews of your preferred hotels in this hotel booking app.
Features of this one of the best hotel booking app
- Explore exclusive offers and deals before making the plan
- Read reviews and check ratings of hotels from around the world
- Instant bookings to make your journey more convenient
- Explore attractive prices of more than 1 million hotels from around the world
OYO offers a huge hotel booking network covering local and international trips. You can use the app to make the booking at attractive prices. Moreover, the app also offers exclusive deals and offers periodically.
OYO has been updating the latest features for quite some time. Recently, it added features such as search & compare. You can look for the hotel according to your preferred choice and compare prices with other hotels in the area.
Features of this one of the best travel apps
- You can explore and save your favorite hotels to make bookings later
- Book hotels with a small amount now and pay the rest of the amount while checking-in
- With exclusive offers, enjoy leisure travel at a lesser cost
- Manage bookings from the app anytime you want
- Multiple payment options are available such as Mastercard, Paypal, American Express, and many more
That Promote Your Product's USPs
If not properly planned, traveling can be quite hectic. However, these apps we talked about above let you handle the necessary tasks like booking transportations and accommodations with comfort. Moreover, as it is a fast process, you do not have to plan for months before or worry about bookings to get full when you reach your destination.
Now, if you are a developer and thinking of serving the traveling sector with your mobile app, you can submit and get your app reviewed to get an expert opinion. This feedback will help you in predicting the performance of your app in the future.
She is an avid writer of technology and trending mobile apps. When she is not busy updating you about the tech world, she spends time reading books and playing guitar.
your Product's growth


text:
I have cleaned the NIB, feed, and section. Hand cleaned the inside of the barrel and cap with mineral oil. Replaced the old rubber sac with a new, properly sized silicone sac. Hand polished the Waterman Ideal 18K Gold Filled Barrel Banding along with the flexible Ideal 14K #2 NIB.
This fountain pen is made from black chased hard rubber. The color of the ebonite display a deep black coloring with no oxidation. The chasing is very light but still can be seen with the naked eye. The fountain barrel has a strong, clean imprint on the side of the sleeve that reads, "PAT'D 1884 MAY 23, 1899 WATERMAN'S FOUNTAIN PEN N.Y. U.S.A. & AUG. 4, 1903 along with the Ideal Globe logo". The butt end of the fountain pen displays a light 12 SF imprint. The 18K Gold Filled Decorative Floral Barrel Banding displays no wear and has the initials engraved into the cartouche area, "P-J Co.".
The cap is a "slip" type cap that is always securing to the barrel. The fountain pen cap does not have a clip and there is no indication there was ever one. There are no monograms or personalizations to either the cap or barrel (other than the gold filled barrel banding). There are no cracks, nicks, repairs to the hard rubber, and the color displays vibrantly - an extremely clean pen. This Waterman measures 5 1/2" in length capped and 6 7/8" posted.
This Waterman is known as a "Sleeve Filler". One would slide the sleeve to gain access to the pressure bar, push the pressure bar down with the nib is in ink, release the pressure bar to has the ink be absorbed into the new silicone sac, and slide the sleeve back over the pressure bar to close the are to begin writing.
The NIB on this Waterman is a New York 14K #2 size. The NIB writes with an extra fine point and can flex up to a triple broad stroke - it does have great flexibility and responsiveness. When measuring the actual tip of the 14K #2 Ideal NIB, it measures at .81mm with digital calipers - a medium point. When writing the sample in the listing images, the NIB writes with an extra fine line measuring roughly .35mm with very light pressure and flexes up to a triple broad stroke 1.88mm with firm to medium pressure. The writing sample provided was done with the actual pen in the images that is listed for sale. The writing sample was used by dipping the NIB in Parker Quink Blue-Black Ink.
These early Waterman Sleeve Filler Fountain Pens quite uncommon and is a rare treat to find them in good condition. I would consider this fountain to grade in Very FIne condition. This #12 Sleeve Filler writes very smooth and I consider it a collector grade fountain pen and certainly would be a fine writing instrument to add to your writing arsenal collection.
Payment & Security
Your payment information is processed securely. We do not store credit card details nor have access to your credit card information.


text:
|Vancouver Maritime Museum
Without her protestations, I would not have known about the exhibit in time to share it with my students who are developing lesson plans around In the Heart of the Sea.
Geography asks three questions:
Where is it? Why is it there? So what?
Geographers apply spatial understanding to the real world.
|Vancouver Maritime Museum


text:
Diet Tips & Advice
Obesity is all too common in dogs. But too many pounds can negatively impact on health and well-being, so you should always intervene to prevent excess weight.
- by Hugo Griffiths
- December 01, 2021
- 2 min read
Product Information
Digestion and Allergies
Our Blog
Through our many years of experience with dogs, we have built up knowledge that we are happy to share with you.
The first six months are the "main growth phase". They require high quality protein and nutrients.
The next 6- 12 months require a reduced protein content to help prevent any growth disorders.
Now fully grown, finding the right diet to match their energy requirements is key.
Now in old age, diets with a lower fat and phosphorus are needed.