A compressive sensing–based adaptable secure data collection scheme for distributed wireless sensor networks

Abstract

Toward the goal of high security and efficiency for data collection in wireless sensor network, this article proposed an adaptable secure compressive sensing–based data collection scheme for distributed wireless sensor network. It adopted public key cryptography technology to solve the key distribution problem, and compressive sensing over finite fields to reduce the communication cost of data collection. Under hardness of decisional learning with errors problem on lattice, it can ensure indistinguishability against chosen ciphertext attack (IND-CCA1) security scheme for collected data on the extranet and indistinguishability against chosen plaintext attack security for data during the process of distributed collection on the intranet. Owing to the similar linear structure for lattices and compressive sensing, data encryption collection can be all in the form of efficient linear operations, and internode data aggregation can be in the form of addition operation.

Introduction

Background

Wireless sensor networks (WSN) is considered as a bridge between human society and physical world. It is deployed for collectively monitoring and disseminating information about various interesting phenomena. In a large-scale network, data transmissions are usually fulfilled through multi-hop routing from individual sensor nodes to the sink node, which causes a lot of redundant transmissions. Therefore, it increases the cost of network communication. The basic data collection scheme in WSN is shown in Figure 1. ¹

Figure 1.

Basic data collection scheme in WSN.

For $i=1,2,\dots ,n$ , we use $x_i$ to express the data generated by node $S_i$ . Each node forwards its own data along with the data received from the child node to the father node. Finally, the sink completes data collection of intranet in WSN and forwards the collected data $\mathit{x}=(x_1,x_2,\dots ,x_n)$ to data processor through extranet.

Remarkably, nodes that are closed to the sink will transmit more data and consume more energy than those outside the network. The out-off-balance energy consumption has a substantial impact on network lifetime.

Compressive sensing (CS) is a novel sensing paradigm that goes against the common wisdom in data collection. ² Compared with the traditional theory, CS theory shows that one can recover sparse data from far fewer measurements or samples and thus reduce the data collection cost and prolong the lifetime of WSN.

CS-based data collection is now wildly used in WSN for data compression and linear structure. It can be depicted in Figure 2. ¹

Figure 2.

CS-based data collection schemes in WSN.

More concretely, let $x_i\in \mathbb{R}$ be the data generated by node $S_i$ , and ${\mathrm{Ø}}_i=({\mathrm{Ø}}_{1i},{\mathrm{Ø}}_{2i},\dots ,{\mathrm{Ø}}_{\mathrm{ki}}{)}^{\mathrm{T}}\in {\mathbb{R}}^k$ be a measure matrix of node $S_i$ , for a sparse n-dimensional data $\mathit{x}=(x_1,x_2,\dots ,x_n{)}^{\mathrm{T}}\in {\mathbb{R}}^{\mathit{n}}$ generated by nodes $(S_1,S_2,\dots ,S_n)$ , we consider a compression form $\mathit{y}=\Phi \mathit{x}\in {\mathbb{R}}^k$ $(k<<n)$ , where $\Phi =({\mathrm{Ø}}_1,{\mathrm{Ø}}_2,\dots ,{\mathrm{Ø}}_n)\in {\mathbb{R}}^{k\times n}$ is a measure matrix shared by nodes and data processor, and $\mathit{y}$ is the measure data of $\mathit{x}$ , then the collected measure data $\mathit{y}$ in the sink can be expressed as

$$\mathit{y}=\Phi \mathit{x}=x_1{\mathrm{Ø}}_1+x_2{\mathrm{Ø}}_2+\cdots +x_n{\mathrm{Ø}}_n$$

In intranet of WSN, for $i=1,2,\dots ,n$ , each node $S_i$ first computes $x_i{\mathrm{Ø}}_i$ , next adds the data of child node $S_{i-1}$ , and then sends the result to its parent node, thereby completing the encoding during transmission. Finally, the sink sends the collected measure data $\mathit{y}$ to the data processor through extranet. The theory of CS guarantees that $\mathit{x}$ can be accurately recovered from $\mathit{y}$ on the data processor using the measure matrix $\Phi$ .

At present, WSN is widely used in many fields. In addition to energy issue, the necessity for security of data in transit becomes very crucial factor. Although CS-based data collection scheme can reduce the data collection cost and prolong the lifetime of WSN, ³ it does not consider the existence of adversaries in the network and therefore cannot protect the security of data. Thus, to construct a secure CS-based data collection scheme for WSN is a very significant work.

Previous works

To solve security challenges for CS-based data collection scheme, a feasible method is to let measurement matrix be a symmetric key, which is just known by both encrypted and decrypted parties. This ideal was formally studied in RB08, ⁴ who regarded an original signal to be sampled as plaintext and its random measurements as ciphertext. We called it as compressed sensing symmetric encryption (CSSE). In their security model, only the encoding result is accessible to the adversary (both the measurement matrix and signal cannot be accessed to the adversary), which means their conclusion is based on a ciphertext-only attack model. By employing a random Gaussian sensing matrix updated at every time encryption, BBM14 ⁵ and BBM16 ⁶ showed that the cryptosystem with the one-time sensing (OTS) random Gaussian matrix could be perfectly secure. The basic idea of the above scheme is to ensure the security of the system by using “one-time pad,” but it costs too much to update the key each time. From the practical point of view, YYN17b ⁷ employed a secret bipolar key-stream and a public unitary matrix, which could generate and renew the key-stream at each encryption in a fast and efficient manner. They demonstrated that the entries of the sensing matrix were asymptotically Gaussian distribution if the plaintext length is sufficiently large, and this cryptosystem could achieve the security of indistinguishability against chosen plaintext attack (IND-CPA) if each plaintext had constant energy. Previous security analyses of CS are based on the OTS hypothesis (i.e. the secret key/measurement matrix is used only once). CM18 ⁸ studied a CS-based asymptotically Gaussian one-time sensing (AG-OTS) cryptosystem for secure wireless communications. HXC14 ⁹ pointed out the CSSE was not secure enough without OTS assumption. However, due to the complex deployment environment of WSN, CS-based data collection schemes still face security threats, poor efficiency and impracticality.

In typical CS-based data collection scheme of WSN as Figure 2, the data collection, encoding, and aggregation are processed at each node in a distributed model, while the data recovery is accomplished at the sink independently according to measurement results received from other nodes. The sink shares the measurement matrix with each sensing node, respectively. To achieve OTS, the measurement matrix (secret key) should be stored in each node and synchronously updated in each measurement cycle. This may face several challenges. First, it enormously increases the cost of communication. Note that the size of the measurement matrix ( $k\times n$ elements) is much larger than the size of the measurement result (k elements). Therefore, the communication cost of key update is too high, especially updated frequently. Second, the distributed characteristic of WSN also makes it more difficult to achieve OTS. On one hand, the multi-hop transmission mechanism may increase the communication cost of OTS, especially when a single key distribution process contains several round of data transmission. On the other hand, most sensor nodes cannot resist attacks and are easy to be captured, so they are not suitable for storing secret key information.

To improve security and practicality of CSSE-based data collection schemes in WSN, PSK18 ³ present a secure data collection scheme based on compressive sensing (SeDC) by introducing an additive homomorphism encryption mechanism to enhance data confidentiality. In SeDC, the intermediate nodes can aggregate data directly in the ciphertext domain without decrypting the received data, which means the private key is not necessary to be stored at the intermediate nodes, thus the security is guaranteed.

More specifically, SeDC used a homomorphic encryption function HE to encrypt the ith measurement results of the node $j$ (i.e. ${\mathrm{Ø}}_{\mathrm{ij}}{x}_j\in \mathbb{R}$ ) into HE $({\mathrm{Ø}}_{\mathrm{ij}}{x}_j)$ . The encrypted data HE $({\mathrm{Ø}}_{\mathrm{ij}}{x}_j)$ is transferred to its parents for aggregation in ciphertext domain. The aggregation result of sink is $\underset{j=1}{\overset{n}{\Pi }}\mathrm{HE}({\mathrm{Ø}}_{\mathrm{ij}}{x}_j)=\mathrm{HE}(\sum _{j=1}^n{\mathrm{Ø}}_{\mathrm{ij}}{x}_j)$ . The detailed process is shown in Figure 3.

Figure 3.

SeDC in PSK18.

Although by combining public key cryptography with compressed sensing, PSK18 solved the key distribution and storage problem of CSSE-based data collection schemes in WSN, there are still some imperfections in terms of efficiency and security.

First, homomorphism encryption function HE usually requires plaintext space to be a finite set, but ${\mathrm{Ø}}_{\mathrm{ij}}{x}_j\in \mathbb{R}$ is not a finite set. So the encryption operation HE $({\mathrm{Ø}}_{\mathrm{ij}}{x}_j)$ cannot be performed correctly.

Second, intranet networks are usually more trustworthy than extranets, IND-CPA security would be sufficient in practice to preserve confidentiality for data on the internal network, but it needs higher security for data on the extranets, especially for some military data. PSK18 just achieves IND-CPA security both for inside attackers and for outside attackers. When data are transmitted to data processors through an external network, it is necessary to re-encrypt the data using a higher secure encryption scheme, for example, an encryption scheme with indistinguishability against chosen-ciphertext attack (IND-CCA1 or IND-CCA2) security.

Third, the expansion of ciphertext and computational efficiency are contradictory in homomorphism encryption. Additive homomorphism schemes ¹⁰ with low expansion usually contain large number of time-consuming exponents or bilinear pairings operation and cannot resist quantum attack.

From the aspect of computational efficiency and quantum attack resistant, lattice-based homomorphic encryption may be a good choice. Although lattice-based encryptions usually have large ciphertext expansion, compressed sensing can greatly compress the data for very sparse data. It can compensate for data expansion of lattice cryptography.

Linear structure of lattice-based cryptography is very similar to CS and has been recognized for its many attractive properties, such as strong provable security guarantees and apparent resistance to quantum attacks, flexibility for realizing powerful tools and high asymptotic efficiency (usually requiring only linear operations on small integers).

LHY18 ¹¹ solves the problem of combining CS with a lattice-based homomorphic public key cryptography by using CS in finite field and constructed an instantiated data collection scheme based on lattice. But LHY18 still can only protect IND-CPA security for data on the extranets.

Our contributions

In this work, we construct a CS-based data collection scheme that can resistant quantum attack and preserve IND-CCA1 security scheme for data on external and IND-CPA security on intranet. By combining an IND-CCA1 secure public key encryption scheme in MP12 ¹² with CS, we first constructed a CS-based public key encryption scheme (remarkably, we just take CS as a black box, which makes the application of our scheme more general) and proved IND-CCA1 security under hardness of learning with errors (LWE) problem on lattice. Then using some tips, we show how to use this new scheme to secure data collection on distributed WSN. We adopted the method in PSK18 to solve the key distribution problem in WSN with public key and also use CS in finite field as shown in LHY18 to solve the problem of combination of public key and CS. Since lattices and CS have similar linear structures, we use some tips to achieve ciphertext additivity of our new scheme. Furthermore, we proved that the piecewise ciphertext of each node can preserve IND-CPA security of the data on intranet networks; thus, each node completes the secure data collection during the transmission process.

Preliminaries

Notation

We denote the set of real numbers by $\mathbb{R}$ , integers by $\mathbb{Z}$ and natural numbers by $\mathbb{N}$ . For natural number $s$ , $n$ and prime power $q$ , we use ${\mathbb{R}}^n$ to express n-dimensional vectors on real numbers field, ${\mathbb{Z}}_q^n$ to denote n-dimensional vectors on the finite field ${\mathbb{Z}}_q$ , and ${\mathbb{Z}}_q^{n\times s}$ to indicate the matrix of $n\times s$ size on the finite field ${\mathbb{Z}}_q$ . We let $[k]=\{1,2,\dots ,k\}$ , where k is a nonnegative integer. We use lower-case bold letters (e.g. $\mathit{x}$ ) to express column vectors ( ${\mathit{x}}^{\mathrm{T}}$ express row vector). We use upper-case bold letters to indicate matrices. For a security parameter $k\in \mathbb{N}$ , we use $1^k$ to express the string of $k$ bits. For a set $V$ , we use $v{\leftarrow }_{\mathrm{random}}V$ to denote an operation of uniformly picking an element $v$ of $V$ at random. For a vector $\mathit{x}$ , we also use $||\mathit{x}||$ to denote Euclidean length of $\mathit{x}$ , and $O(·)$ to denote complexity. For matrix $\mathit{A}=[{\mathit{A}}_1|{\mathit{A}}_2]$ , this express ${\mathit{A}}_1$ and ${\mathit{A}}_2$ are partitioned matrix of $\mathit{A}$ .

Over a finite or countable domain $\mathcal{D}$ , the statistical distance between two distributions X and $Y$ is $\mathrm{\Delta }(X,Y)=1/2(\sum _{\omega \in \mathcal{D}}|X(\omega )-Y(\omega )|)$ . When statistical distance from the uniform distribution is at most $ϵ$ , we say that the distribution over $\mathcal{D}$ is $ϵ$ -uniform, and we let a “randomized-rounding parameter” $r$ be a fixed function $r(n)=w(\sqrt{\log n})$ growing asymptotically faster than $\sqrt{\log n}$ throughout this article.

For any basis $\mathit{V}=\{{\mathit{v}}_1,{\mathit{v}}_2,\dots ,{\mathit{v}}_n\}$ of ${\mathbb{R}}^n$ , we defined its origin-centered parallelepiped as ${\mathcal{P}}_{1/2}(\mathit{V})=\mathit{V}·[-1/2,1/2{)}^n$ and defined its dual basis as ${\mathit{V}}^{*}={\mathit{V}}^{-\mathrm{T}}=({\mathit{V}}^{-1}{)}^{\mathrm{T}}$ .

Sub-Gaussian distributions and lattices

Definition 1

For any s> 0, the Gaussian function on ${\mathbb{R}}^n$ centered at $\mathit{c}$ with parameter $s$ is defined as follows ¹³

$$\forall x\in {\mathbb{R}}^n,{\rho }_{s,\mathit{c}}\left(\mathit{x}\right)=\exp \left(\frac{-\pi ·{\Vert \mathit{x}-\mathit{c}\Vert }^2}{s^2}\right)$$

The subscripts $s$ and $\mathit{c}$ are taken to be 1 and 0 (respectively) when omitted.

Definition 2

For n-dimensional lattice $\mathit{\Lambda }$ , any $\mathit{c}\in {\mathbb{R}}^n$ , and real $s>0$ , the discrete Gaussian distribution over $\mathit{\Lambda }$ is defined as follows ¹³

$$\forall x\in \mathit{\Lambda },D_{\mathit{\Lambda },s,\mathit{c}}\left(\mathit{x}\right)=\frac{{\rho }_{s,\mathit{c}}\left(\mathit{x}\right)}{{\rho }_{s,\mathit{c}}\left(\mathit{\Lambda }\right)}$$

As above, we may omit the parameters $s$ or $\mathit{c}$ .

If for $\delta \ge 0$ , and for all $t\in R$ , the (scaled) moment-generating function satisfies

$$E\left[\exp \left(2\pi \mathrm{tX}\right)\right]\le \exp \left(\delta \right)·\exp \left(\pi u^2{t}^2\right)$$

We say the random variable $X$ (or its distribution) over $\mathbb{R}$ is δ-sub-Gaussian with parameter $u>0$ .

Notice that the $\exp (\pi u^2{t}^2)$ term is just the (scaled) moment-generating function of the Gaussian distribution $D_u$ . When working with discrete Gaussians, it usually takes $\delta =\mathrm{In}((1+ϵ)/(1-ϵ))\approx 2ϵ$ . ¹²

Definition 3

For any n-dimensional lattice $\mathit{\Lambda }$ and positive real $ϵ>0$ , the smoothing parameter ${\eta }_{ϵ}(\mathit{\Lambda })$ is the smallest real $s>0$ such that ${\rho }_{1/s}({\mathit{\Lambda }}^{*}\backslash \{0\})$ . ¹³

Lemma 1

For a lattice $\mathit{\Lambda }\subset {\mathbb{R}}^n$ , let $r\ge {\eta }_{ϵ}(\Lambda )$ and $0<ϵ<1$ , for any $\mathit{c}\in \mathrm{span}(\mathit{\Lambda })$ , we have ¹²

$$\mathrm{Pr}[\Vert D_{\mathit{\Lambda }+\mathbf{c},\mathbf{r}}\Vert \ge r\sqrt{n}]\le 2^{-n}·\frac{1+ϵ}{1-ϵ}$$

When $\mathit{c}=0$ and $ϵ=0$ for any $r>0$ , the above bound holds.

Lemma 2

For a lattice $\mathit{\Lambda }\subset {\mathbb{R}}^n$ , let $u\ge {\eta }_{ϵ}(\Lambda )$ and $0<ϵ<1$ . ¹² For any $\mathit{c}\in \mathrm{span}(\Lambda )$ , $D_{\mathit{\Lambda }+\mathit{c},u}$ is $\mathrm{In}((1+ϵ)/(1-ϵ))$ -sub-Gaussian with parameter $u$ . When $\mathit{c}=0$ , it is just 0-sub-Gaussian for any $u>0$ .

Theorem 1

For any positive integer k, some $u\ge {\eta }_{ϵ}(\mathbb{Z})$ and $ϵ=\mathrm{negl}(n)$ , let $D_{{\mathbb{Z}}^m,u}$ be a discrete Gaussian distribution. assuming vectors ${\mathit{e}}_1,{\mathit{e}}_2,\dots ,{\mathit{e}}_k{\leftarrow }_{\mathrm{random}}{D}_{{\mathbb{Z}}^m,u/\sqrt{k}}$ , then vector $\mathit{e}={\mathit{e}}_1+{\mathit{e}}_2+\cdots +{\mathit{e}}_k$ obeys discrete Gaussian distribution over $D_{{\mathbb{Z}}^m,u}$ .

Proof

For ${\mathit{e}}_1,{\mathit{e}}_2,\dots ,{\mathit{e}}_k{\leftarrow }_{\mathrm{random}}{D}_{{\mathbb{Z}}^m,u/\sqrt{k}}$ , then ${\mathit{e}}_1,{\mathit{e}}_2,\dots ,{\mathit{e}}_k$ are independent of each other and all obeys the same distribution over $D_{{\mathbb{Z}}^m,u/\sqrt{k}}$ . According to the additive property of Gauss distribution, we have vector $\mathit{e}={\mathit{e}}_1+{\mathit{e}}_2+\cdots +{\mathit{e}}_k$ also obeys discrete Gaussian distribution over $D_{{\mathbb{Z}}^m,u}$ .

Decisional LWE problem

For $\alpha >0$ , the LWE problem $\mathrm{LW}{\mathrm{E}}_{q,\alpha }$ may be seen an average-case version of the bounded-distance decoding problem on the dual lattice $\Lambda ({\mathbf{A}}^{\mathrm{T}})/q$ . Let $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ , the additive group of reals modulo 1, and let $D_{\alpha }$ denote the Gaussian probability distribution over $\mathbb{R}$ with parameter $\alpha$ . For any fixed $\mathit{x}\in {\mathbb{Z}}_q^l$ , define ${\mathit{A}}_{\mathit{x},\alpha }$ to be the distribution over ${\mathbb{Z}}_q^{l\times s}\times {\mathbb{T}}^s$ obtained by choosing $\mathit{A}\leftarrow {\mathbb{Z}}_q^{l\times s}$ uniformly at random, choosing $\mathit{e}\leftarrow D_{\alpha }^s$ , and outputting $(\mathit{A},\mathit{b}={\mathit{A}}^T\mathit{x}/q+\mathit{e}\mathrm{mod}1)$ .

The decisional $\mathrm{LW}{\mathrm{E}}_{q,\alpha }$ problem is to distinguish, with non-negligible advantage, between sampling from ${\mathit{A}}_{\mathit{x},\alpha }$ for uniformly random $\mathit{x}\in {\mathbb{Z}}_q^l$ , and uniformly random sampling from ${\mathbb{Z}}_q^{l\times s}\times {\mathbb{T}}^s$ .

The hardness of decisional $\mathrm{LW}{\mathrm{E}}_{q,\alpha }$ problem is based on the worst-case quantum hardness of approximate-SVP,^14,15 to which there is no known effective quantum algorithm.

Trapdoor for lattices and algorithms for inverting LWE

MP12 ¹² defined a new trapdoor, given a method of inverse LWE, and established some of important properties as follow.

Definition 4

Let $\mathit{A}\in {\mathbb{Z}}_q^{n\times m}$ and $\mathit{G}\in {\mathbb{Z}}_q^{n\times \omega }$ be matrices with $m\ge \omega \ge n$ . ¹² A G -trapdoor for $\mathit{A}$ is a matrix $\mathit{F}\in {\mathbb{Z}}_q^{(m-\omega )\times \omega }$ such that $\mathit{A}\left[\begin{array}{c}\mathit{F}\hfill \\ \multicolumn{1}{c}{\mathit{I}}\end{array}\right]=\mathit{HG}$ for some invertible matrix $\mathit{H}\in {\mathbb{Z}}_q^{n\times n}$ . Matrix $\mathit{H}$ is called tag or label of the trapdoor. The trapdoor’s quality is measured by its largest singular value $s_1(\mathit{F})$ .

For our construction, we define an algorithm $\mathbf{GenTra}{\mathbf{p}}^{\mathcal{D}}$ ( $n$ , $m$ , $\omega$ , $q$ ) according to Algorithm 1 in MP12 as follow.

Definition 5

Efficient algorithm $\mathbf{GenTra}{\mathbf{p}}^{\mathcal{D}}$ ( $n$ , $m$ , $\omega$ , $q$ ) for generating a parity-check matrix $\mathit{A}$ with trapdoor $\mathit{F}$ .

Input. Parameters $n,m,\omega$ are positive integers, and $q$ is a prime power, and distribution $\mathcal{D}$ is over ${\mathbb{Z}}^{(m-\omega )\times \omega }$ .

Output. A parity-check matrix $\mathit{A}=[\overline{\mathit{A}}|{\mathit{A}}_1]\in {\mathbb{Z}}_q^{n\times m}$ , where $\overline{m}+\omega =m$ , and trapdoor $\mathit{F}$ .

1. Pick $\overline{\mathit{A}}\in {\mathbb{Z}}_q^{n\times \overline{m}}$ uniformly at random, choose a matrix $\mathit{F}\in {\mathbb{Z}}^{\overline{m}\times \omega }$ from distribution $\mathcal{D}$ .

2. Output $\mathit{A}=[\overline{\mathit{A}}|-\overline{\mathit{A}}\mathit{F}]\in {\mathbb{Z}}_q^{n\times m}$ and trapdoor $\mathit{F}\in {\mathbb{Z}}^{\overline{m}\times \omega }$ .

Statistical instantiation

For any parameter $\overline{m}$ and distribution $\mathcal{D}$ over ${\mathbb{Z}}^{\overline{m}\times \omega }$ , this instantiation have the following property:

Regularity. For $\overline{\mathit{A}}{\leftarrow }_{\mathrm{random}}{\mathbb{Z}}_q^{n\times \overline{m}}$ , and $\mathit{F}{\leftarrow }_{\mathrm{random}}\mathcal{D}$ , $\mathit{A}=[\overline{\mathit{A}}|-\overline{\mathit{A}}\mathit{F}]$ is δ-uniform for some $\delta =\mathrm{nelg}(n)$ .

For example, let $\mathcal{D}=D_{\mathbb{Z},u}^{\overline{m}\times \omega }$ be a discrete Gaussian distribution for some $u\ge {\eta }_{ϵ}(\mathbb{Z})$ and $ϵ=\mathrm{negl}(n)$ . Then $\mathcal{D}$ is 0-sub-Gaussian with parameter $u$ . Moreover, given $\mathit{A}=[\overline{\mathit{A}}|-\overline{\mathit{A}}\mathit{F}]$ , with overwhelming probability over the choice of $\overline{\mathrm{A}}$ , the conditional distribution of $\mathit{F}$ is negl(n)-sub-Gaussian with parameter $u$ .

Algorithm 2 in MP12 shows an efficient algorithm $\mathrm{Inver}{t}^{\mathcal{O}}(\mathit{F},\mathit{A},\mathit{b})$ for inverting the function $\mathit{b}={\mathit{A}}^T\mathit{s}+\mathit{e}$ , where $\mathit{F}\in {\mathbb{Z}}^{\overline{m}\times \omega }$ is a trapdoor of matrix $\mathit{A}\in {\mathbb{Z}}_q^{n\times m}$ .

MP12 also gave a detail construction of $\mathrm{Inver}{t}^{\mathcal{O}}(\mathit{F},\mathit{A},\mathit{b})$ and proved that over the choice of $\mathit{e}$ such that $[{\mathit{F}}^{\mathrm{T}}|{\mathit{I}}^{\mathrm{T}}]\mathit{e}\in {\mathcal{P}}_{1/2}(q·\mathit{B})$ for some $\mathit{B}=O(1)$ , then the algorithm output $\mathit{s}$ and $\mathit{e}$ successfully except with probability $2^{-\Omega \left(l\right)}$ (see Theorem 5.4 and Theorem 4.1 in MP12).

Compressed sensing over finite field

Let $q$ is a prime power, compressed sensing over finite field ${\mathbb{Z}}_q$ consists of three steps: ¹⁶ sparse representation of signals, measure matrix selection, and reconstruction of signals.

Sparse representation of signals

Set signal $\mathit{x}={[x_1,x_2,\dots ,x_n]}^T$ is n-dimensional vectors on the finite field ${\mathbb{Z}}_q$ , and $\mathrm{wt}(\mathit{x})$ express the number of non-zero element in $\mathit{x}$ , if for all $\mathit{x}\in {\mathbb{Z}}_q^n$ , it meets that $\mathrm{wt}(\mathit{x})\le k$ , it calls signal $\mathit{x}$ is $k$ -spare. If γ is sparse factor, it meets $k=n\gamma$ .

Selection of measure matrix

If signal $\mathit{x}$ is $k$ -spare on ${\mathbb{Z}}_q^n$ , it can express by $m$ $(m<<n)$ -dimensional measured value

$$\mathit{y}=\Phi \mathit{x}$$

where for $i=1,2,\dots ,n$ , it meets ${\mathrm{Ø}}_i\in {\mathbb{Z}}_q^m$ , and $\mathit{y}=[y_1,y_2,\dots ,y_m{]}^T\in {\mathbb{Z}}_q^m$ is measured value.

DM09 ¹⁶ pointed out that a necessary condition for the successful recovery of all k-sparse signal is $m>2k$ , if more tractable $l_1$ minimization is used, then the sparse source can still be recovered if $m>\mathrm{C}n\log (1/)$ , where C is a constant. S18 ¹⁷ introduced methods of selecting the measure matrix and reconstructing signals, respectively.

In our scheme, we just consider the condition with $q=2$ . For $=2^k$ , we can fulfill data collection by running scheme k times. Considering convenience to descript, we give the definition of measure matrix selection algorithm as follow. By the way, we just take it as a black box, and detail construction can utilize the method in previous studies^16–19 according the specific circumstances.

Definition 6

Let GetMatr( $m$ , $n$ ) is a polynomial time algorithm, when inputs security parameters (m, n), it outputs a random measure matrix $\mathit{\Phi }\in {\mathbb{Z}}_2^{\mathbf{m}\times \mathbf{n}}$ , where $m,n\in \mathbb{Z}$ and $0<m<n$ .

Reconstruction of signals

Reconstruction of signals can be described as to reconstruct signals $\mathit{x}\in {\mathbb{Z}}_q^n$ on a given measure matrix $\mathit{\Phi }$ and measured values $\mathit{y}=\mathit{\Phi }\mathit{x}$ by solving the optimization problem. For convenience of description, we also give the definition of signals reconstruction algorithm as follows. Incidentally, we just take it as a black box, and the detail construction can also utilize the corresponding method in previous studies.^16–19

Definition 7

Let RecSig(Φ, y) is a polynomial time algorithm, when inputs parameters ( Φ, y ), it outputs signals $\mathit{x}\in {\mathbb{Z}}_2^n$ , where $\mathit{\Phi }\in {\mathbb{Z}}_2^{m\times n}$ is a measure matrix, and it meets $\mathit{y}=\mathit{\Phi }\mathit{x}\in {\mathbb{Z}}_2^m$ .

CS-based public key encryption and security definition

The CS-based Public Key Encryption (CSPKE) is defined as follows:

Definition 8

A CS-based public key encryption scheme is quadruples of algorithms (KeyGen, Enc, Dec, MesRec) such that

KeyGen( $n,l,q$ ) is a probabilistic polynomial-time key generation algorithm which receives as input a security parameter $n,l,q\in \mathbb{Z}$ and outputs a measure matrix $\mathit{\Phi }$ as public parameter, a public key $\mathrm{pk}$ , and a secret key $\mathrm{sk}$ .

Enc( $\mathit{m}$ , $\mathrm{pk}$ , $\mathit{\Phi }$ ) is a probabilistic polynomial-time encryption algorithm which takes as input a public key $\mathrm{pk}$ and a signal $\mathit{x}$ in $\mathcal{X}$ ( $\mathcal{X}$ is the signal space), and outputs a ciphertext $\mathit{c}$ .

Dec( $\mathit{c}$ , $\mathrm{sk}$ ) is a deterministic polynomial-time decryption algorithm which receives as input a secret decryption key $\mathrm{sk}$ and a ciphertext $\mathit{c}$ and outputs either a measured value $\mathit{y}$ of signal $\mathit{x}$ or an error symbol ⊥.

MesRec( $\mathit{y},\mathit{\Phi }$ ) is a polynomial-time reconstruction algorithm which receives as input a measure matrix $\mathit{\Phi }$ and a measured value $\mathit{y}$ and outputs a reconstructed signal $\mathit{x}$ .

Moreover, a further fundamental property is required: correctness. We want that, for any pair of public and secret keys generated by KeyGen, and for every message $\mathit{x}$ in $\mathcal{X}$ , it holds that MesRec(Dec (Enc( $\mathit{x}$ , $\mathrm{pk}$ ), $\mathrm{sk}$ ), $\mathit{\Phi }$ ) =  $\mathit{x}$ with overwhelming probability over the randomness used by KeyGen and Enc.

Our CSPKE is IND-CCA1 secure for outside attackers and IND-CPA secure for inside attackers in distributed application. Next, we define IND-CCA1 security of CSPKE and IND-CPA security of CSPKE-D (we use CSPKE-D to express the scheme of CSPKE for distributed application) according to NYP ²⁰ as follows.

Definition 9

IND-CCA1 security is defined by the interaction experiment between challenger C and attacker A.

Challenger C runs KeyGen( $n,l,q$ ), getting public key $\mathrm{pk}$ and secret key $\mathrm{sk}$ , then outputs a measure matrix $\mathit{\Phi }$ as public parameter and sends $\mathrm{pk}$ to attacker A.

When A makes a sequence of decryption query to C, for each decryption query, A submits a ciphertext $\mathit{c}$ , and C responds with a corresponding plaintext $\mathit{x}$ .

A chooses two signals ${\mathit{x}}_0$ and ${\mathit{x}}_1$ in $\mathcal{X}$ , then sends them to C.

C randomly selects bits $b\in \{0,1\}$ , then computers challenge ciphertext ${\mathit{c}}^{*}$  = Enc( ${\mathit{x}}_b$ , $\mathrm{pk}$ , $\mathit{\Phi }$ ). At last, C sends A.

A outputs $b\prime \in \{0,1\}$ as the guess values to $b$ .

The advantage of attacker A to attack the above encryption algorithm is defined as

$${\mathrm{Adv}}_{\mathrm{A}}^{\mathrm{CCA}1,\mathrm{CSPKE}}=|\mathrm{Pr}[b=b\prime ]-\frac{1}{2}|$$

The CSPKE Algorithm is IND-CCA secure if for all probabilistic polynomial time (PPT) adversaries the advantage ${\mathrm{Adv}}_{\mathrm{A}}^{\mathrm{CCA}1,\mathrm{CSPKE}}$ is negligible.

Definition 10

IND-CPA security is defined by the interaction experiment between challenger C and attacker A.

Challenger C runs KeyGen( $n,l,q$ ), getting public key $\mathrm{pk}$ and secret key $\mathrm{sk}$ , then outputs a measure matrix $\mathit{\Phi }$ as public parameter, and sends $\mathrm{pk}$ to attacker A.

A chooses two signals ${\mathit{x}}_0$ and ${\mathit{x}}_1$ in $\mathcal{X}$ , then sends them to C.

C randomly selects bits $b\in \{0,1\}$ , then computers challenge ciphertext ${\mathit{c}}^{*}$  = Enc( ${\mathit{x}}_b$ , $\mathrm{pk}$ , $\mathit{\Phi }$ ). At last, C sends ${\mathit{c}}^{*}$ to A.

A outputs $b\prime \in \{0,1\}$ as the guess values to $b$ .

The advantage of attacker A to attack the above encryption algorithm is defined as

$${\mathrm{Adv}}_{\mathrm{A}}^{\mathrm{CPA},\mathrm{CSPKE}-\mathrm{D}}=|\mathrm{Pr}[b=b\prime ]-\frac{1}{2}|$$

The CSPKE-D scheme is IND-CPA secure if for all PPT adversaries the advantage ${\mathrm{Adv}}_{\mathrm{A}}^{\mathrm{CPA},\mathrm{CSPKE}-\mathrm{D}}$ is negligible.

Compressed sensing public key encryption scheme based on LWE

The concrete scheme

We give some exemplary asymptotic bounds for a number of parameters involved in our scheme. In the following, we used $w\sqrt{(\log l)}$ to represent a fixed function who asymptotically grows faster than $\sqrt{(\log l)}$ .

• Let $l,s,n,d$ be positive integers, $q$ be a prime power, $\mathit{x}=[x_1,x_2,\dots ,x_n{]}^{\mathrm{T}}\in {\mathbb{Z}}_2^n$ be $d$ -spare signal, $\omega$ be the measurement times to $\mathit{x}$ needed in CS algorithm, it satisfying $n>>\omega$ (note that we just take CS as a black-box, so the specific relationship among $\omega$ , $d$ , and $n$ is based on concrete CS algorithm,^16–19 $s>\omega \ge l$ and $s\ge 2l\log q$ . Typically $\omega =l\log q$ and $s=2\omega$ (see MP12).

• For prime power $q$ , $\mathit{G}\in {\mathbb{Z}}_q^{l\times \omega }$ is a gadget matrix. Let $\overline{s}=O(\omega )$ and $\mathcal{D}=D_{\mathbb{Z},w\sqrt{\left(\log l\right)}}^{\overline{s}\times \omega }$ , thus $[\overline{\mathit{A}}|-\overline{\mathit{A}}\mathit{F}]$ is negl(l)-far from uniform fo $r\overline{\mathit{A}}{\leftarrow }_{\mathrm{random}}{\mathbb{Z}}_q^{l\times \overline{s}}$ . Let $\mathit{F}{\leftarrow }_{\mathrm{random}}\mathcal{D}$ , and $s=\overline{s}+\omega$ . We need an oracle $\mathcal{O}$ to solve LWE with respect to $\mathrm{\Lambda }({\mathit{G}}^{\mathrm{T}})$ for any error vector in some ${\mathcal{P}}_{1/2}(q·\mathit{B})$ where $\Vert \mathit{B}\Vert =O(1)$ . (The constructions of oracle $\mathcal{O}$ can be seen in section 4 in MP12.)

• The error rate in LWE is express by $\alpha$ , such that $1/\alpha =O(\omega )·w\sqrt{(\log l)}$ is sufficiently large.

We need a special collection in the ring $\mathcal{R}={\mathbb{Z}}_q(x)/f(x)$ and an injective ring homomorphism $h:\mathcal{R}\to {\mathbb{Z}}_q^{l\times l}$ (see section 6.1 in MP12). We also need a large set $\mathcal{U}=\{u_1,u_2,\dots ,u_l\}\subset \mathcal{R}$ with the “unit differences” property: for any $i\ne j$ , the difference $u_i-u_j\in {\mathcal{R}}^{*}$ , and hence $h(u_i-u_j)=h(u_i)-h(u_j)\in Z_q^{l\times l}$ is invertible.

For measure matrix $\mathit{\Phi }=[{\mathrm{Ø}}_1,{\mathrm{Ø}}_2,\dots ,{\mathrm{Ø}}_n]\in {\mathbb{Z}}_2^{\omega \times n}$ , the message space of signal measure value $\mathit{\Phi }\mathit{x}$ mod 2 is $\{0,1{\}}^{\mathrm{\omega }}$ . Through an efficient function $\mathrm{encode}$ , we map bijectively to the cosets of $\mathrm{\Lambda }/2\mathrm{\Lambda }$ for $\mathrm{\Lambda }=\mathrm{\Lambda }({\mathit{G}}^{\mathrm{T}})$ . Specifically, letting $\overline{\mathit{B}}\in {\mathbb{Z}}^{\mathrm{\omega }\times \mathrm{\omega }}$ be any basis of $\mathrm{\Lambda }$ , we can map $\mathit{\Phi }\mathit{x}\in \{0,1{\}}^{\mathrm{\omega }}$ to $\mathrm{encode}(\mathit{\Phi }\mathit{x})=\overline{\mathit{B}}\Phi \mathit{x}\in {\mathbb{Z}}^{\mathit{\omega }}$ .

• KeyGen( $n,l,s,q$ )

• Runs algorithm GetSMatr( $\omega ,n$ ) to get measure matrices $\mathit{\Phi }=[{\mathrm{Ø}}_1,{\mathrm{Ø}}_2,\dots ,{\mathrm{Ø}}_n]\in {\mathbb{Z}}_2^{\omega \times n}$ , then sets $\mathit{\Phi }$ as public parameter.

• For parameters $l,s,q$ , runs the algorithm $\mathbf{GenTra}{\mathbf{p}}^{\mathcal{D}}$ ( $1^l,1^s,q$ ) to get matrix $\mathit{A}=[\overline{\mathit{A}}|{\mathit{A}}_1]\in {\mathbb{Z}}_q^{l\times s}$ and corresponding $\mathit{G}$ -trapdoor $\mathit{F}\in {\mathbb{Z}}_q^{(s-\omega )\times \omega }$ , where $\overline{\mathit{A}}{\leftarrow }_{\mathrm{random}}{\mathbb{Z}}_q^{l\times \overline{s}}$ and it satisfies ${\mathit{A}}_1=-\overline{\mathit{A}}\mathit{F}$ .

• Outputs public key $\mathrm{pk}=\{\mathit{A}\}$ and secret key $\mathrm{sk}=\{\mathit{F}\}$ .

• Enc( $\mathit{x}$ , $\mathrm{pk}$ , $\mathit{\Phi }$ )

• Chooses a nonzero $u{\leftarrow }_{\mathrm{random}}\mathcal{U}$ and let ${\mathit{A}}_u=[\overline{\mathit{A}}|{\mathit{A}}_1+h\left(u\right)\mathit{G}]$ .

• Chooses a vector $\mathit{b}{\leftarrow }_{\mathrm{random}}{\mathbb{Z}}_q^l$ , $\overline{\mathit{e}}{\leftarrow }_{\mathrm{random}}{D}_{\mathbb{Z},\alpha q}^{\overline{s}}$ , $\tilde{\mathbf{e}}{\leftarrow }_{\mathrm{random}}{D}_{\mathbb{Z},\alpha q\sqrt{2\overline{s}}·w\sqrt{\left(\log l\right)}}^{\omega }$ .

• Computes $c_2=2({\mathit{A}}_u^{\mathrm{T}}\mathit{b}\mathrm{mod}\mathit{q})+[(0/\overline{\mathit{B}}\Phi \mathit{x})]+\mathbf{e}\mathrm{mod}2q$ , where 0 has $\overline{s}$ dimension and $\mathit{e}=\left[\begin{array}{c}\overline{\mathit{e}}\hfill \\ \multicolumn{1}{c}{\tilde{\mathbf{e}}}\end{array}\right]\in {\mathbb{Z}}^s$ . Let $c_1=u$ .

• Outputs the ciphertext $\mathit{c}=(c_1,c_2)$ .

• Dec( $\mathit{c}$ , $\mathrm{sk}$ )

• Let ${\mathit{A}}_u=[\overline{\mathit{A}}|{\mathit{A}}_1+h\left(u\right)\mathit{G}]=[\overline{\mathit{A}}|h\left(u\right)\mathit{G}-\overline{\mathit{A}}\mathit{F}]$ .

• If $u=0$ or $c$ does not parse, outputs ⊥, otherwise, calls $\mathbf{Invert}(\mathit{F},\mathit{A},c)$ to get value $\mathit{b}\prime \in {\mathbb{Z}}_q^l$ and $\mathit{e}=\left[\begin{array}{c}\overline{\mathit{e}}\hfill \\ \multicolumn{1}{c}{\tilde{\mathbf{e}}}\end{array}\right]\in {\mathbb{Z}}^s$ for which ${\mathit{c}}_2={{\mathit{A}}_u}^{\mathrm{T}}\mathit{b}\prime +\mathit{e}\mathrm{mod}q$ . (Note that $h(u)\in {\mathbb{Z}}_q^{l\times l}$ is invertible.) If the call to $\mathbf{Invert}$ fails for any reason, outputs ⊥.

• If $\Vert \overline{\mathit{e}}\Vert \ge \alpha q\sqrt{\overline{s}}$ or $\Vert \tilde{\mathbf{e}}\Vert \ge \alpha q\sqrt{2\overline{s}\omega }·w\sqrt{(\log l)}$ , outputs ⊥.

• Let $\mathit{v}={\mathit{c}}_2-\mathit{e}\mathrm{mod}2q$ , computes value $\mathit{y}={\overline{\mathit{B}}}^{-1}([{\mathit{F}}^{\mathrm{T}}|{\mathit{I}}^{\mathrm{T}}]\mathit{v})$ , then outputs $\mathit{y}$ .

• MesRec( $\mathit{y}$ , $\mathit{\Phi }$ )

• Runs the algorithm RecSig( $\mathit{\Phi }$ , $\mathit{y}$ ) to get reconstruction signal $\mathit{x}$ , then outputs $\mathit{x}$ .

Analyses

Correctness

Theorem 2

The above scheme has only $2^{-\mathrm{\Omega }(l)}$ probability of decryption error.

Proof

Let $(\mathit{A},\mathit{F})\leftarrow \mathbf{KeyGen}(n,l,s,q)$ . By Lemma 2.9 in MP12, we have $\Vert \mathit{F}\Vert \le O(\sqrt{\mathrm{\omega }})·w\sqrt{(\log l)}$ except with probability $2^{-\mathrm{\Omega }(l)}$ .

For arbitrary $\mathit{\Phi }\mathit{x}\in {\mathbb{Z}}^{\mathrm{\omega }}$ , we consider the random choices in Enc( $\mathit{x}$ , $\mathrm{pk}$ , $\mathit{\Phi }$ ) as follows. By Lemma 2.6 in MP12, we have both $\Vert \overline{\mathit{e}}\Vert \le \alpha q\sqrt{\overline{s}}$ and $\Vert \tilde{\mathbf{e}}\Vert \le \alpha q\sqrt{2\overline{s}\omega }·w\sqrt{(\log l)}$ , except with probability $2^{-\mathrm{\Omega }(l)}$ . Letting $\mathit{e}=\left[\begin{array}{c}\overline{\mathit{e}}\hfill \\ \multicolumn{1}{c}{\tilde{\mathbf{e}}}\end{array}\right]$ , it has

$$\Vert [{\mathit{F}}^{\mathrm{T}}|{\mathit{I}}^{\mathrm{T}}]\mathit{e}\Vert \le \Vert {\mathit{F}}^{\mathrm{T}}\overline{\mathit{e}}\Vert +\Vert \tilde{\mathbf{e}}\Vert <\alpha q·O\left(\sqrt{\mathrm{\omega }}\right)·w\sqrt{\left(\log l\right)}$$

Specially, for large enough $1/\alpha =O(\omega )·w\sqrt{(\log l)}$ , it has $[{\mathit{F}}^{\mathrm{T}}|{\mathit{I}}^{\mathrm{T}}]\mathit{e}\in {\mathcal{P}}_{1/2}(q·\mathit{B})$ . Therefore, the call to $\mathbf{Invert}$ made by Dec( $\mathit{c}$ , $\mathrm{sk}$ ) returns $\mathit{e}$ . It follows that for $\mathit{v}=(\overline{\mathit{v}},{\mathit{v}}_1)={\mathit{c}}_2-\mathit{e}\mathrm{mod}2q$ , it has $[{\mathit{F}}^{\mathrm{T}}|{\mathit{I}}^{\mathrm{T}}]\mathit{v}=[{\mathit{F}}^{\mathrm{T}}|{\mathit{I}}^{\mathrm{T}}]$ $[{\mathit{A}}_u^{\mathrm{T}}\mathit{x}+\left[\begin{array}{c}0\hfill \\ \multicolumn{1}{c}{\overline{\mathit{B}}\Phi \mathit{x}}\end{array}\right]]=2({\mathit{G}}^{\mathrm{T}}h(u{)}^T\mathit{x}\mathrm{mod}q)+\overline{\mathit{B}}\Phi \mathit{x}\mathrm{mod}2q$ , which is in the coset $\overline{\mathit{B}}\Phi \mathit{x}\in \mathrm{\Lambda }({\mathit{G}}^{\mathrm{T}})/2\mathrm{\Lambda }({\mathit{G}}^{\mathrm{T}})$ , and so Dec outputs $\mathit{y}=\mathit{\Phi }\mathit{x}$ mod 2 as desired. Noticing that, algorithm RecSig is just run over ${\mathbb{Z}}_2$ in Definition 7. So RecSig( $\mathit{\Phi }$ , $\mathit{y}$ ) can output $\mathit{x}$ as desired.

IND-CCA1 security

We will prove the security of above-described scheme.

Theorem 3

The above CSPKE scheme is IND-CCA1 secure assuming the hardness of decision- $\mathrm{LW}{\mathrm{E}}_{q,\alpha \prime }$ for $\alpha \prime =\alpha /3\ge 2\sqrt{l}/q$ .

Proof

Let $\mathit{\Phi }\mathit{x}\mathrm{mod}2\in \{0,1{\}}^{\mathrm{\omega }}$ , our scheme can just be described as a instantiation of encryption scheme in MP12 section 6.3.

For signal $\mathit{x}$ , we can first compute $\mathit{\Phi }\mathit{x}\mathrm{mod}2\in \{0,1{\}}^{\mathrm{\omega }}$ , and then call encryption scheme in MP12 section 6.3 to encrypt and decrypt for message $\mathit{\Phi }\mathit{x}$ , then run the reconstruction algorithm RecSig( $\mathit{\Phi }$ , $\mathit{\Phi }\mathit{x}$ ) of CS to get reconstruction signal $\mathit{x}$ . It is noteworthy that $\mathit{\Phi }$ is a public parameter. For input message $\mathit{\Phi }\mathit{x}$ , the reconstruction algorithm RecSig is just a public polynomial time algorithm without secret key. So the security of CSPKE is just provided by the encryption scheme in MP12.

The encryption scheme in MP12 is IND-CCA1 secure assuming the hardness of decision- $\mathrm{LW}{\mathrm{E}}_{q,\alpha \prime }$ for $\alpha \prime =\alpha /3\ge 2\sqrt{l}/q$ . So CSPKE scheme is also IND-CCA1 secure assuming the hardness of decisional $\mathrm{LW}{\mathrm{E}}_{q,\alpha \prime }$ for $\alpha \prime =\alpha /3\ge 2\sqrt{l}/q$ . Detailed proof can be seen in Theorem 6.3 in MP12.

A CS-based adaptable secure data collection scheme for WSN

Now, we show how to use CSPKE to implement a CS-based data collection scheme for distributed WSN that is IND-CPA secure for inside attackers and IND-CCA1 secure for outside attackers.

Although CSPKE scheme itself does not have additive homomorphic property, if we fix the first partial ciphertext $c_1=u$ , then matrix $A_u$ is determined, thereby the second partial ciphertext $c_2=2({\mathit{A}}_u^T\mathit{b}\mathrm{mod}\mathit{q})+\left[\begin{array}{c}0\hfill \\ \multicolumn{1}{c}{\overline{\mathit{B}}\Phi \mathit{x}}\end{array}\right]+\mathit{e}\mathrm{mod}2q$ has additive homomorphic property. In more detail, let each node share the same $u$ together in every time data collection, the second partial ciphertext $c_2$ with additive homomorphic property can be used to implement data collection for distributed WSN.

The main steps are summarized as follows:

1. Setup

   The system first initializes the network, and for parameter $n,l,s,q$ , runs algorithm KeyGen( $n,l,s,q$ ) to get public key $\mathrm{pk}=\{\mathit{A}\}$ , secret key $\mathrm{sk}=\{\mathit{F}\}$ , and measure matrix $\Phi$ and gadget matrix $\mathit{G}$ , and then broadcasts parameter, public key, measure matrix, and gadget matrix. Data processor saves private keys for decryption.

2. Encryption measurement and in-network aggregation

   Let $\mathit{\Theta }=\overline{\mathit{B}}=[{\mathit{\theta }}_1,{\mathit{\theta }}_2,\dots ,{\mathit{\theta }}_n]$ , node $S_1$ first chooses nonzero $u{\leftarrow }_{\mathrm{random}}\mathcal{U}$ and computes ${\mathit{A}}_u=[\overline{\mathit{A}}|{\mathit{A}}_1+h(u)\mathit{G}]$ , then computes ${\mathit{c}}_{1,2}={\mathit{c}}_{1,2}^{\prime }=2({\mathit{A}}_u^{\mathrm{T}}{\mathit{b}}_1\mathrm{mod}q)+\left[\begin{array}{c}0\\ x_1{\mathit{\theta }}_1\end{array}\right]+{\mathit{e}}_1\mathrm{mod}2q$ , at last sends ( $u,{\mathit{c}}_{1,2}$ ) to its father node $s_2$ . For $i=2,\dots ,n$ , Node $S_i$ first chooses ${\mathit{b}}_i{\leftarrow }_{\mathrm{random}}{\mathbb{Z}}_q^l$ and ${\mathit{e}}_i=\left[\begin{array}{c}{\overline{\mathit{e}}}_i\hfill \\ \multicolumn{1}{c}{{\tilde{\mathbf{e}}}_i}\end{array}\right]$ , where ${\overline{\mathit{e}}}_i{\leftarrow }_{\mathrm{random}}{D}_{\mathbb{Z},\alpha q/\sqrt{n}}^{\overline{s}}$ and ${\tilde{\mathbf{e}}}_i{\leftarrow }_{\mathrm{random}}{D}_{\mathbb{Z},\alpha q\sqrt{2\overline{s}n}·w\sqrt{\left(\log l\right)}}^{\omega }$ , then computes ${\mathit{A}}_u=[\overline{\mathit{A}}|{\mathit{A}}_1+h(u)\mathit{G}]$ , ${\mathit{c}\prime }_{i,2}=2({\mathit{A}}_u^{\mathrm{T}}{\mathit{b}}_i\mathrm{mod}\mathit{q})+\left[\begin{array}{c}0\hfill \\ \multicolumn{1}{c}{x_i{\mathit{\theta }}_i}\end{array}\right]+{\mathit{e}}_i\mathrm{mod}2q$ , ${\mathit{c}}_{i,2}={\mathit{c}\prime }_{i,2}+{\mathit{c}}_{i-1,2}$ , at last sends $(u,{\mathit{c}}_{i,2})$ to father node. Each node performs this procedure thereby completing the encryption measurement during transmission.

Finally, the sink received encrypted measurement value $\mathit{c}=(u,{\mathit{c}}_2)$ , where

$\begin{array}{l}{\mathit{c}}_2={\mathit{c}}_{n,2}={{\mathit{c}}^{\prime }}_{1,2}+{{\mathit{c}}^{\prime }}_{2,2}+\cdots +{{\mathit{c}}^{\prime }}_{n,2}=2({\mathit{A}}_u^{\mathrm{T}}{\mathit{b}}_1\mathrm{mod}q)+\left[\begin{array}{c}0\\ x_1{\theta }_1\end{array}\right]+{\mathit{e}}_1\mathrm{mod}2q+2({\mathit{A}}_u^{\mathrm{T}}{\mathit{b}}_2\mathrm{mod}q)+\left[\begin{array}{c}0\\ x_2{\theta }_2\end{array}\right]+\\ {\mathit{e}}_2\mathrm{mod}2q+\cdots 2({\mathit{A}}_u^{\mathrm{T}}{\mathit{b}}_n\mathrm{mod}q)+\left[\begin{array}{c}0\\ x_n{\theta }_n\end{array}\right]+{\mathit{e}}_n\mathrm{mod}2q\end{array}$ .

Let $\mathit{e}=\left[\begin{array}{c}\overline{\mathit{e}}\hfill \\ \multicolumn{1}{c}{\tilde{\mathbf{e}}}\end{array}\right]={\mathit{e}}_1+{\mathit{e}}_2+\cdots +{\mathit{e}}_n$ , according to Theorem 1, we have $\overline{\mathit{e}}\in D_{\mathbb{Z},\alpha q}^{\overline{s}}$ and $\tilde{\mathbf{e}}\in D_{\mathbb{Z},\alpha q\sqrt{2\overline{s}}·w\sqrt{\left(\log l\right)}}^{\omega }$ . Let $\mathit{b}={\mathit{b}}_1+{\mathit{b}}_2+\cdots +{\mathit{b}}_n\in {\mathbb{Z}}_q^l$ , we have ${\mathit{c}}_2=2({{\mathit{A}}_u}^{\mathrm{T}}\mathit{b}\mathrm{mod}q)+\left[\begin{array}{c}0\hfill \\ \multicolumn{1}{c}{\overline{\mathit{B}}\Phi \mathit{x}}\end{array}\right]+\mathit{e}\mathrm{mod}2q$ which is a consistent partial ciphertext according to CSPKE. Although all nodes share the same $u$ together, $u$ is chosen random in $\mathcal{U}$ by $S_1$ according to CSPKE. For the collected data on the sink, $u$ is also a consistent partial ciphertext according to CSPKE. Then collected data $\mathit{c}=(u,{\mathit{c}}_2)$ is just a consistent ciphertext generated by Enc( $\mathit{x}$ , $\mathrm{pk}$ , $\mathit{\Phi }$ ) of CSPKE taking as input a public key $\mathrm{pk}=\{\mathit{A}\}$ , a measure matrices $\mathit{\Phi }$ and a signal $\mathit{x}$ .

The detailed process is shown as Figure 4.

Figure 4.

CS-based IND-CCA1 secure data collection scheme in WSN.

• 3. Data recovery

The data processor runs algorithm Dec( $\mathit{c}$ , $\mathrm{sk}$ ) to decrypt the aggregation result by using the private key $\mathrm{sk}$ , and output measurement value $\mathit{y}$ , then runs the algorithm RecSig( $\mathit{\Phi }$ , $\mathit{y}$ ) to get reconstruction signal $\mathit{x}=(x_1,x_2,\dots ,x_n)\in {\mathbb{Z}}_2^n$ , then outputs $\mathit{x}$ .

Security analysis

As can be seen from the above description, the collected data $\mathit{c}=(u,{\mathit{c}}_2)$ on sink is just a consistent ciphertext generated by Enc( $\mathit{x}$ , $\mathrm{pk}$ , $\mathit{\Phi }$ ) of CSPKE taking as input a public key $\mathrm{pk}=\{\mathit{A}\}$ , a measure matrices $\mathit{\Phi }$ and a signal $\mathit{x}$ . So for outside attackers, CSPKE-D is IND-CCA1 secure according to Theorem 3.

CSPKE scheme itself does not have additive homomorphic property. In order to implement a distributed data collection, we share the first partial ciphertext $c_1=u$ to all nodes in every time data collection. It means that ${\mathit{A}}_u$ is a determined matrix for all nodes and also inside attackers in every time data collection, so the security of CSPKE-D is declined for inside attackers. However, it is still IND-CPA secure for inside attackers. This security is usually sufficient for intranets.

Theorem 4

Our above CSPKE-D scheme is IND-CPA secure for inside attackers assuming the hardness of decision- $\mathrm{LW}{\mathrm{E}}_{q,\alpha \prime }$ for $\alpha \prime =\alpha /3\ge 2\sqrt{l}/q$ .

Proof

For inside adversaries, the first partial ciphertext $c_1=u$ is fixed, and then ${\mathit{A}}_u$ is a determined matrix. Next we assume if there is a polynomial time inside adversary A who can break the IND-CPA security of this CSPKE-D, we show how to use this adversary to construct a distinguisher for the decisional $\mathrm{LW}{\mathrm{E}}_{q,\alpha \prime }$ problem for $\alpha \prime =\alpha /3\ge 2\sqrt{l}/q$ .

For the distinguisher, we are given $(\mathit{A},\mathit{b})$ coming from either an LWE distribution ${\mathit{A}}_{\mathit{s},\alpha \prime }$ over ${\mathbb{Z}}_q^{l\times s}\times {\mathbb{T}}^s$ for any $\mathit{s}\in {\mathbb{Z}}_q^l$ (where recall that $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ ) or uniformly random samples from ${\mathbb{Z}}_q^{l\times s}\times {\mathbb{T}}^s$ . Our construction works are as follows.

Prepare the public key

The simulator runs the key generation algorithm GetSMatr( $\omega ,n$ ) to get measure matrices $\mathit{\Phi }=[{\mathrm{Ø}}_1,{\mathrm{Ø}}_2,\dots ,{\mathrm{Ø}}_n]\in {\mathbb{Z}}_2^{\omega \times n}$ , then sets $\mathit{\Phi }$ as public parameter.

For a gadget matrix $\mathit{G}\in {\mathbb{Z}}_q^{l\times \omega }$ and the fixed first partial ciphertext $u$ , let ${\mathit{A}}_u=\mathit{A}=[\overline{\mathit{A}}|{\mathit{A}}_1]\in {\mathbb{Z}}_q^{l\times s}$ , where $\overline{\mathit{A}}\in {\mathbb{Z}}_q^{l\times \overline{s}}$ , and then computes $\mathit{A}\prime =[\overline{\mathit{A}}|{\mathit{A}}_1-h\left(u\right)\mathit{G}]$ .

Outputs public key $\mathrm{pk}=\{\mathit{A}\prime \}$ , and sends it to adversary A.

Prepare the challenge ciphertext

When the adversary chooses ${\mathit{x}}_0$ and ${\mathit{x}}_1$ in $\mathcal{X}$ , and gives it to the simulator, the simulator chooses $\overline{b}\in (0,1)$ at random and computes $c_2=2q\mathit{b}+\left[\begin{array}{c}0\\ \overline{\mathit{B}}\Phi {\mathit{x}}_{\overline{b}}\end{array}\right]+{\mathit{e}}^{\prime }\mathrm{mod}2q$ for $e\prime \leftarrow D_{\mathbb{Z},\alpha q}^s$ .

By Theorem 3.1 of Pei10 ²¹ we can transform its samples $(\mathit{A},\mathit{b}={\mathit{A}}^{\mathrm{T}}\mathit{s}/q+\mathit{e}\mathrm{mod}1)$ to have the form $(\mathit{A},2{\mathit{A}}^{\mathrm{T}}\mathit{s}\mathrm{mod}q+\mathit{e}\prime \mathrm{mod}2q)$ for $e\prime \leftarrow D_{\mathbb{Z},\alpha q}^s$ , by mapping $\mathit{b}\to 2q\mathit{b}+D_{\mathbb{Z}-2q\mathit{b},g}^s$ where $g^2=(\alpha q{)}^2-(2\alpha \prime q{)}^2\ge 4l\ge {\eta }_{ϵ}(\mathbb{Z}{)}^2$ . This transformation maps the uniform distribution over ${\mathbb{Z}}_q^{l\times s}\times {\mathbb{T}}^s$ to the uniform distribution over ${\mathbb{Z}}_q^{l\times s}\times {\mathbb{Z}}_{2q}^s$ .

As we see from the adversary’s view, when the input to the simulator comes from an LWE distribution ${\mathit{A}}_{\mathit{s},\alpha \prime }$ , the output of the encryption oracle is just a perfectly legitimate ciphertext. It is clear that the joint distribution of the adversary’s view and $\overline{b}$ is identical to that in the actual attack. However, when the input to the simulator uniformly random samples from ${\mathbb{Z}}_q^{l\times s}\times {\mathbb{T}}^s$ , the adversary’s view and $\overline{b}$ are essentially information theoretic independent. This completes the construction of a distinguisher for the decisional $\mathrm{LW}{\mathrm{E}}_{q,\alpha \prime }$ problem. Consequently if there is a polynomial time inside adversary A who can break the IND-CPA security of this CSPKE-D, the simulator can solve the decisional $\mathrm{LW}{\mathrm{E}}_{q,\alpha \prime }$ problem with the same non-negligible advantage. That completes the proof of security.

Efficiency analysis

Considering from the computational efficiency, our above scheme just involved simple some linear operations, which are very efficiency on computation. It is worth noting that we take CS as a black box, thus the method used measurement sparse matrix for CS in PSK18 can also be used in our scheme to further improve computation efficiency. Next, we mainly analyze the communication efficiency.

Our scheme can be described as a public key encryption scheme to CS. In detail, original data $\mathit{x}$ is first compressed by CS, and then encrypted by a lattice-based PKE scheme. Although lattice-based encryptions usually have large ciphertext expansion, compressed sensing can greatly compress the data for very sparse data (the original data in WSN are naturally sparse). It can compensate for data expansion of lattice cryptography, which makes our scheme practical in WSN.

For a more intuitive description, we follow give a theoretical traffic comparison of related schemes in Table 1.

Table 1.

Comparison of related schemes.

Schemes	CS	PSK18	LHY18	Our scheme
Signal (bit)	n	n	n	n
security	No	IND-CPA	IND-CPA	IND-CCA1 for extranetIND-CPA for intranet
Ciphertext (bit)	ω	ωHE-Exp	2ωlog2q	| $\mathcal{R}$ |+ 2ω log2(2q)
Ciphertext expansion	ω / n	ωHE-Exp/n	(2ω log2q)/n	| $\mathcal{R}$ |/n + 2ω (log2q + 1)/n

CS: compressive sensing; IND-CPA: indistinguishability against chosen plaintext attack; IND-CCA1: indistinguishability against chosen ciphertext attack.

In Table 1, we assume that the lengths of input signal to these schemes are all n bits, and we use “Ciphertext” to represent the corresponding lengths of the outputs (theoretical traffic). For the line of ciphertext expansion, it means the ratio of outputs to inputs. Assuming that the outputs of CS scheme (who is the basis of PSK18, LHY18 and our CSPKE-D) are ω bits, it is easy to compute that the outputs of our scheme are| $\mathcal{R}$ |+ 2ω log₂(2q) bits, where we used $|\mathcal{R}|$ to express the size of ring $\mathcal{R}$ used in our CSPKE-D, and then we can compute that the outputs of LHY18 are 2ωlog₂q bits. For the reason that PSK18 just takes additive homomorphism scheme ²² as a black box (without specifying a certain scheme), we use “HE-Exp” to express the ciphertext expansion of additive homomorphism scheme, and the outputs of PSK18 are $\omega \mathrm{HE}-\mathrm{Exp}$ bits.

Next, we analyze theoretical communication load of our above scheme in comparison with related schemes in detail.

Compared with the original CS scheme, the increased communication load of our scheme mainly comes from ciphertext expansion. According to MP12, we have $s=2\omega =2l\mathrm{lo}{\mathrm{g}}_{2}q$ , $|\mathcal{R}|\ge l$ and $q\ge 2$ . Thus, the ciphertext expansion is $[|\mathcal{R}|+2\mathrm{\omega }(\mathrm{lo}{\mathrm{g}}_{2}q+1)]/n\ge \omega /(n\mathrm{lo}{\mathrm{g}}_{2}q)+2\omega (\mathrm{lo}{\mathrm{g}}_{2}q+1)/n$ .

In order to facilitate the comparisons, from the aspect of quantum attack resistant and computational efficiency, we assume the homomorphic encryption scheme used in PSK18 is a lattice-based homomorphic encryption.

Furthermore, LHY18 can be seen as a concrete scheme of PSK18 by using a specific lattice-based additive homomorphism encryption scheme. Thus, PSK18 and LHY18 have a similar ciphertext expansion from the perspective of quantum attack resistant. As can be seen from Table 1, The ciphertext expansion of our scheme is only a little larger than that of LHY18 (note that |ℜ| is much smaller than $2\mathrm{lo}{\mathrm{g}}_2(2q)$ ).

In terms of security, the size of $q$ is inversely proportional to that of $n$ . Usually $n$ (the number of nodes in WSN) is very large. Typically for the 128 bit security level of $q$ , ¹⁵ the ciphertext expansion of CSPKE-D is close to $258/n$ times (the ciphertext length of CSPKE-D is close to $258\omega$ ).

However, CS data compression rate is proportional to data sparsity. For $n$ -bit data with sparse factor $\gamma$ , we have $\omega \ge 2\delta n\mathrm{lo}{\mathrm{g}}_{q}n$ , where $\delta$ is a constant. ¹⁹ When the original signal is well sparse, such as Taobao data with the ${10}^{-5}$ level of the sparse factor $\gamma$ , ²³ our scheme still achieves good data compression (the ciphertext length of CSPKE-D is close to $5.16\times {10}^{-3}\delta n\mathrm{lo}{\mathrm{g}}_{q}n$ for $n$ -bits input signal).

Conclusion

The security issues of data collection in WSN have attracted great attention from academics and industry. In this article, we mainly focused on the security among data collection and transmission process and proposed an IND-CCA1 for extranet and IND-CPA for intranet secure CS-based data collection scheme. The security of our scheme is based on the hardness of decisional LWE problem, to which there is no known effective quantum algorithm. In terms of computational efficiency, our scheme only contains simple linear operation, so it has high computational efficiency. In terms of communication efficiency, although CSPKE-D algorithm brings a little of data expansion, CS realized a good communication cost compensation by data compression, which makes our scheme practical in WSN.