SyLPEnIoT: Symmetric Lightweight Predicate Encryption for Data Privacy Applications in IoT Environments

Abstract

Privacy preserving mechanisms are essential for protecting data in IoT environments. This is particularly challenging as IoT environments often contain heterogeneous resource-constrained devices. One method for protecting privacy is to encrypt data with a pattern or metadata. To prevent information leakage, an evaluation using the pattern must be performed before the data can be retrieved. However, the computational costs associated with typical privacy preserving mechanisms can be costly. This makes such methods ill-suited for resource-constrained devices, as the high energy consumption will quickly drain the battery. This work solves this challenging problem by proposing SyLPEnIoT – Symmetric Lightweight Predicate Encryption for IoT, which is lightweight and efficient compared with existing encryption schemes. Based on the bitwise-XOR operation, we use this basic gate to construct a scheme that transfers encrypted data onto more powerful machines. Furthermore, for resource-constrained IoT devices, the requester can authenticate devices at different levels based on the type of communication. SyLPEnIoT was meticulously designed to run on a gamut of IoT devices, including ultra low-power sensors that are constrained in terms of CPU processing, memory and energy consumption, which are widely deployed in real IoT ecosystems.

A Security Proof

Theorem 2

The SyLPEnIoT scheme is selectively simulation-secure in the standard model under the assumption that PRF is a pseudo-random function.

Again, we use the notion $Q_{\textsf {Tkn}}$ as the total number of token queries, and the notion $Q_{\textsf {Enc}}$ as the total number of ciphertext queries.

Proof. We show that for any uniform probabilistic polynomial-time algorithm $\mathcal {A}$, there exists a uniform probabilistic polynomial-time simulator $\mathcal {S}$, such that the ensemble distribution: $(\{\textsf {CT}_i\}_{i \in [1, Q_{\textsf {Enc}}]}, \{\textsf {TK}_{f_j}\}_{j \in [1, Q_{\textsf {Tkn}}]}) {\mathop {\leftarrow }\limits ^{R}} \textsf {Expt}_{\textsf {SyLPEnIoT}, \mathcal {A}}^{sel,\textsf {real}} (\lambda , \ell )$ and the ensemble distribution: $(\{\textsf {CT}_i\}_{i \in [1, Q_{\textsf {Enc}}]}, \{\textsf {TK}_{f_j}\}_{j \in [1, Q_{\textsf {Tkn}}]}) {\mathop {\leftarrow }\limits ^{R}} \textsf {Expt}_{\textsf {SyLPEnIoT}, \mathcal {A}}^{sel,\textsf {sim}} (\lambda , \ell )$ are computationally indistinguishable. We then construct the simulator $\mathcal {S}$ in the experiment sim. First, we consider the simplest scenario where $\mathcal {A}$ makes $Q_{\textsf {Enc}}= 1$ ciphertext query and $Q_{\textsf {Tkn}}\le \textsf {poly}(\lambda )$ gen-token queries.

Since in our main SyLPEnIoT scheme, the input $\mathcal {I}$ is described as a vector $\vec {v}$, and a predicate is defined as a vector $\vec {x}$, and the evaluation returns $f_{\vec {x}}(\vec {v}) = 1$ iff the inner product ${<}\vec {v}, \vec {x}{>}\,= 0$. In this proof, we describe directly the simulation of $\vec {v}, \vec {x}$ instead of attribute $\mathcal {I}$, predicate f.

• Inputs to Simulator $\mathcal {S}$. Let $Q_{\textsf {Enc}}= 1$, we assume that $\mathcal {A}$ queries the simulator with a query history of the form $\mathcal {H} = (\vec {v}, M, \vec {x}_1, \ldots , \vec {x}_Q)$. $\mathcal {S}$ receives the security parameter $1^{\lambda }$ along with the query history $\mathcal {H}$. We recall the definition of query pattern $\alpha (\mathcal {H})$, and decryption pattern $\beta (\mathcal {H})$ as:

  • Given a query history $\mathcal {H} = (\vec {v}, M ,\vec {x}_1, \ldots , \vec {x}_{Q_{\textsf {Tkn}}})$ for SyLPEnIoT scheme, we set $\vec {x}_j = (x_{j,1}, \ldots , x_{j, \ell })$ for each $j \in [1, Q_{\textsf {Tkn}}]$, where $\ell$ is the length of f in SyLPEnIoT scheme. The token query pattern $\alpha (\mathcal {H})$ is a set of of values

    $\{\alpha _{i,j,k}\}_{i,j \in [1,Q_{\textsf {Tkn}}], k \in [1,\ell ]}$ such that: $\alpha _{i,j,k} = {\left\{ \begin{array}{ll} 1, &{} x_{i,k} = x_{j,k}\\ 0 , &{} otherwise \end{array}\right. },$ where $i,j \in [1, Q_{\textsf {Tkn}}]$, $k \in [1,\ell ]$ .

  • Then let $\textsf {TK}_{f_j}$ be the gen-token corresponding to $\vec {x}_j$ in $\mathcal {H}=(\vec {v}, M ,\vec {x}_1, \ldots , \vec {x}_{Q_{\textsf {Tkn}}})$, where $j \in [1, Q_{\textsf {Tkn}}]$. Also, let $\textsf {CT}$ denotes a ciphertext upon the encryption of the plaintext $\vec {v}, M$. The decryption pattern $\beta (\mathcal {H})$ received by $\mathcal {S}$ is defined as a set of values $\{\beta _j\}_{j \in [1, Q_{\textsf {Tkn}}]}$: $\beta _{j} = {\left\{ \begin{array}{ll} M, &{} {<}\vec {v}, \vec {x}_j{>}\,= 0\\ \perp , &{} otherwise \end{array}\right. },$

  We choose the values $W_1, \ldots , W_{\ell } {\mathop {\leftarrow }\limits ^{R}} \{0,1\}^{\lambda }$ to simulate the $\textsf {PRF}(\textsf {SK}, *||k)$ for $k \in [1, \ell ]$.

• Simulating GenToken. The simulator $\mathcal {S}$ now generates GenToken

  $\{\textsf {TK}_{f_j}\}_{j \in [1, Q_{\textsf {Tkn}}]}$ using the algorithm below. Note that since the GenToken algorithm is deterministic, $\mathcal {S}$ ensures the GenToken generate are consistent with the predicate vectors.

  

• Simulating the Ciphertext. The plaintext $(\vec {v}, M)$ is not known to $\mathcal {S}$. The only things that the simulator can learn are the various leakages of encrypted data and the secret keys. To simulate the components including the wildcard ‘*’, the values $W_1, W_2, \ldots , W_\ell {\mathop {\leftarrow }\limits ^{R}} \{0,1\}^{\lambda }$ are used by $\mathcal {S}$ to simulate $\textsf {PRF}(\textsf {SK}, *||k)$ for $k \in [1, \ell ]$.

  • If some $j \in [1,Q_{\textsf {Tkn}}]$, ${<}\vec {v}, \vec {x}_j{>}\,= 0$, then at the positions k where $\vec {x}_{j_k} = 1$, it can deduce $\vec {v}_k = 0$, and from $\vec {x}_{j_k} = 0$; it can infer $\vec {v}_k = 1$ or $\vec {v}_k = 0$. This information allows $\mathcal {S}$ to simulate the ciphertext components as:

    

  • The final step is to simulate the c component. Recall that the decryption pattern is the set of value ${\beta _1, \ldots , \beta _Q}$. For $j \in [1, Q_{\textsf {Tkn}}]$, $\beta _j$ output of 1 if ${<}\vec {v}, \vec {x}{>}\,= 0$, then M is a message. Otherwise, then M is set as the string $\{\perp \}^{\lambda }$. Later, M is used to generate the $c = \textsf {SKE}.\textsf {Encrypt}(K,M)$ as in the real world. This ensures that decrypting C using $\textsf {TK}_{f_j}$, the message M is recovered correctly. On the other hand, ${<}\vec {v}, \vec {x}_j{>}\,= 1$ for $j \in [1, Q_{\textsf {Tkn}}]$, decrypting with any the token $\textsf {TK}_{f_j}$ always returns the string $\{\perp \}^{\lambda }$ .

• The Indistinguishability Argument. This argues that a probabilistic polynomial-time distinguisher $\mathcal {D}$ cannot computationally distinguish $(\textsf {CT}, \{\textsf {TK}_{f_j}\}_{j \in [1, Q_{\textsf {Tkn}}]}) {\mathop {\leftarrow }\limits ^{R}} \textsf {Expt}_{\textsf {SyLPEnIoT}, \mathcal {A}}^{sel,\textsf {real}} (\lambda , \ell )$ from

  $(\textsf {CT}, \{\textsf {TK}_{f_j}\}_{j \in [1,Q_{\textsf {Tkn}}]}) {\mathop {\leftarrow }\limits ^{R}} \textsf {Expt}_{\textsf {SyLPEnIoT}, \mathcal {A}}^{sel,\textsf {sim}} (\lambda , \ell )$. The indistinguishability is presented as:

  • At the first simulation of $\textsf {Expt}_{\textsf {SyLPEnIoT}, \mathcal {A}}^{sel,\textsf {sim}}$ as $((\mathcal {I}_1,M_1),\ldots , (\mathcal {I}_{Q_{\textsf {Enc}}},M_{Q_{\textsf {Enc}}}),f_1, \ldots , f_{Q_{\textsf {Tkn}}}){\mathop {\leftarrow }\limits ^{R}} \mathcal {A}(1^{\lambda })$, it does not include the secret key SK with all but negligible probability, and the secret keys generated in the real mode of experiment using the pseudo-random function PRF are indistinguishable from the uniformly random secret keys generated by the simulator $\mathcal {S}$. Then, this can distinguish between the output of PRF and a uniformly random string of size $\lambda$ without knowing the corresponding secret key $\textsf {SK}$. In the same way, the components of the ciphertext $\textsf {CT}$ in the real experiment must also be indistinguishable from those generated by the simulator $\mathcal {S}$.

  • Finally, if there exists at least one $j \in [1,Q_{\textsf {Tkn}}]$ such that ${<}\vec {v}, \vec {x}_j{>}\,= 0$, $\mathcal {S}$ gains knowledge of the message M, which is used to generate $c = \textsf {SKE}.\textsf {Encrypt}(K,M)$ as in the real world. In this case, the indistinguishability is trivial. On the other hand, ${<}\vec {v}, \vec {x}_j{>}\,= 1$ for $j \in [1,Q_{\textsf {Tkn}}]$, decrypting $\textsf {CT}$ using any $\textsf {TK}_{f_j}$ does not reveal the secret key K, which is used to encrypt M.

• Polynomial Ciphertext Queries. The simulator $\mathcal {S}$ can address polynomially many ciphertext queries of the form $\{(\mathcal {I}_i, M_i)\}_{i \in [1, Q_{\textsf {Enc}}]]}$. The simulator $\mathcal {S}$ essentially repeats the same ciphertext simulation phase for each such query. As our security definition, the simulator $\mathcal {S}$ receives as input the decryption pattern corresponding to each ciphertext query $(\mathcal {I}_i , M_i)$. Hence, it can either infer the corresponding payload message $M_i$ or a string $\{\perp \}^{\lambda }$. Additionally, the components for $\textsf {CT}_i$ are chosen consistently with the token-gen $\{\textsf {TK}_{f_j}\}_{j \in [1,Q_{\textsf {Tkn}}]}$. This ensures that, if $f_j(\mathcal {I}_i) = 1$ for some $j \in [1, Q_{\textsf {Tkn}}]$, then decrypting $\textsf {CT}_i$ using $\textsf {TK}_{f_j}$ correctly recovers the string $\{0,1\}^{\lambda }$. Finally, the simulation of two ciphertexts $\textsf {CT}_i$ and $\textsf {CT}_i'$ can proceed independent of whether the corresponding attributes $\mathcal {I}_i$ and $\mathcal {I}_i'$ match in one or more components. This completes the proof of Theorem 1.