Policy-Based Chameleon Hash with Black-Box Traceability for Redactable Blockchain in IoT

Abstract

Blockchain has become an integral part of various IoT applications, and it has been successful in boosting performance in various aspects. Applying blockchain as a trust solution for Internet-of-Things is a viable approach. The immutability of blockchain is essential to prevent anyone from manipulating registered IoT data transactions for illegitimate benefits. However, the increasing abuse of blockchain storage negatively impacts the development of IoT blockchain and potential stakeholders are discouraged from joining the IoT data sharing as the IoT data recorded on the blockchain contains private information. Hence, it is crucial to find ways to redact data stored on the IoT blockchain, which is also supported by relevant laws and regulations. Policy-based chameleon hash is useful primitive for blockchain rewriting, allowing the modifier to rewrite the transaction if they possess enough rewriting privileges that satisfy the access policy. However, this approach lacks traceability, which can be exploited by malicious modifiers to grant unauthorized user modification privileges for personal gain. To overcome this deficiency, we introduce a new design of policy-based chameleon hash with black-box traceability (PCHT), which enables the authority to identify the set of producers responsible for generating the pirate decoder. Specifically, PCHT is constructed by practical attribute-based encryption with black-box traceability (ABET) and collision-resistant chameleon hash with ephemeral trapdoor (CHET). After modeling PCHT, we present its concrete instantiation and rigorous security proofs. Finally, a PCHT-based redactable transaction scheme for IoT blockchain is given. Compared to the state-of-the-art mutable blockchain solutions, our scheme provides fine-grained blockchain rewriting and black-box traceability. The evaluation results demonstrate that our scheme is efficient and practical while still ensuring that no computational overhead is placed on IoT devices with limited computing resources.

1. Introduction

As a prevalent computing technology paradigm, the Internet of Things (IoT) is widely utilized in various fields, including smart healthcare [1], smart grids [2], and smart cities [3,4]. However, with the rapid increase in IoT applications, they are confronted with numerous security and privacy challenges. Common attack methods include data sniffing, data spoofing, and malicious data injection [5,6]. It is evident that the target of these attacks is the data stored on the IoT network [7]. Typically, a centralized database is used to process the collected IoT data. Nevertheless, this approach has centralized drawbacks, and blockchain offers a promising solution for achieving distributed data protection in IoT networks [8,9].

Blockchain has gained tremendous popularity and acceptance by a wider community since Satoshi Nakamoto proposed Bitcoin in 2008 [10]. As a decentralized ledger technology, blockchain can be an ideal solution for multicenter cooperation-based trust [11,12]. Nowadays, it has been widely applied in insurance [13,14], DRM [15,16], and IoT [17,18], not just focusing on cryptocurrencies. For blockchain, it is well known that blocks are linked by hash chain and immutability is one of its characteristics. Specifically, a block contains multiple transactions. Generally, any modification on a transaction is nearly impossible since it would influence the continuity of the block.

With the progress of IoT technology, IoT data are now not confined to a singular closed environment, but is distributed amongst various cooperative IoT system [19]. In order to cater to intricate application requirements, sharing of data among different IoT systems is becoming an inevitable trend. For an IoT data owner, it is reasonable to process their own data, which is also supported by relevant laws and regulations. For example, the general data protection regulation (GDPR) [20] gives data owners the right of alerting their data. Additionally, the immutability of blockchain can lead to several challenges. On the one hand, the increasing abuse of blockchain storage negatively impacts the development of IoT blockchain. On the other hand, there is a risk of inappropriate content and sensitive information being permanently recorded on the blockchain, which may discourage potential stakeholders from joining IoT data sharing. Hence, it is crucial to find ways to erase data stored on the IoT blockchain.

To make data posted to a IoT blockchain redactable, there are several existing strategies, which can be categorized into two types: hard fork and chameleon hash. The former creates forked blockchain at the block where the data need to be changed and discards the subsequent blocks. However, this method cannot achieve fine-grained data modifying. The latter applies chameleon hash to achieve secure blockchain rewriting. Ateniese et al. proposed a seminal block-level rewriting scheme by replacing the traditional hash function with the chameleon hash, where the trapdoor owners could rewrite the block without breaking the link of each two adjacent blocks [21]. To make the modification more fine-grained and achieve transaction-level rewriting, Derler et al. introduce attribute-based encryption (ABE) into the chameleon hash called policy-based chameleon hash (PCH), in which a party could create a modifiable transaction using PCH and only the specific modifier who has the associated attributes could modify it. Compared to [21], here chameleon hashes are used to hash the transaction in computing the Merkle root. PCH is derived from CHET [22] and attribute-based encryption (ABE) [23]. Specifically, the long-term trapdoor in CHET is generated by the central authority and will be issued to the modifier and the ephemeral one is derived from the transaction owner for each transaction. The ephemeral trapdoor is sealed by the ABE scheme.

There are multiple recipients in the ABE scheme and each one is assigned an attribute-related key to modify the data recorded in a transaction. Generally, this key is not allowed to be shared with others. However, this key management policy is invalid for the malicious modifier. By constructing the pirate decoder with his decryption key, the malicious modifier can issue his modification privileges to the unauthorized and gain certain benefits. In this case, the holder of the pirate decoder can maliciously change shared data on the IoT blockchain, e.g., tampering with original sensor data, for personal gain, thereby distributing the normal operation of data modification on the IoT blockchain. Hence, it is necessary to trace the corrupted modifier and then enforce the correct punishments.

Several redactable blockchain schemes with traceability have been proposed. Tian et al. proposed the PCH-based redactable blockchain with accountability, which links the modified transaction to its modifier but not the key leakage [24]. Additionally, Panwar et al. introduced a permissioned redactable blockchain with traceability and revocability by combining dynamic group signature and FAME, but their solution only provides weak accountability that links the modified transaction to its modifier but not producers of the pirate decoder [25]. To achieve strong accountability, the traceability object in this paper is the collude producers, named traitors, of the pirate decoder that allows the unauthorized to rewrite transactions.

Based on ABET and CHET, policy-based chameleon hash with traceability, named PCHT, is introduced in this paper. For constructing a practical ABET with black-box traceability, we choose the efficient CP-ABE scheme [23] and robust fingerprinting code [26]. Moreover, PCHT has constant-size ciphertext. The major contributions are summarized as follows.

• Formal definition and security model. The formal definition and security model of policy-based chameleon hash with traceability (PCHT) are introduced. The remarkable feature of PCHT is that it enables the authority to trace the corrupt modifiers who produce the pirate decoder that allows the unauthorized to rewrite data recorded in IoT blockchain. Compared to the existing solutions, our solution achieves black-box traceability while equipping security and performance advantages.
• Generic construction and practical instantiation. We begin by providing a detailed explanation of the generic construction of PCHT. Following this, we present a PCHT-based redactable transaction scheme for IoT blockchain. Finally, we describe a practical instantiation of PCHT. Considering the limited computing resources of IoT devices, the data sharing is conducted by the data owner and the transaction rewriting operations are performed by full nodes on the IoT blockchain, which have sufficient computational resources to execute the hashing and adaptation algorithms. Due to the infrequent occurrence of transaction rewriting in the IoT system, it is not expected to significantly impact the system’s performance in a negative way.

2. Overview

In the system model of PCHT-based redactable blockchain for IoT, there are three types of entities, which are shown in Figure 1. Then, we introduce the cryptographic primitives behind PCHT.

2.1. System Overview

First, we introduce a trusted authority to take charge of system initialization and traitor tracing. Generally, the transactions are published by the IoT data owner and redacted by the modifier. The blockchain data rewriting in blockchain for IoT could be performed by the following steps.

• System initialization. The authority initializes the system by publishing the public parameters and generating a secret key for each participant using their individual attribute sets.
• Mutable transaction publication. The IoT data owner appends a mutable transaction to the blockchain using the hash algorithm of PCHT. Then, they would check its validity by the verify algorithm of PCHT to decide whether to record it in the local ledger.
• Mutable transaction rewriting. When the attribute set of modifier satisfies the modification policy, he can rewrite this mutable transaction. After that, the modifier broadcasts it, and the other participants would also check its validity.
• Traitor tracing. If there exists a pirate decoder for modifying the mutable transactions illegally, the authority would trace the corrupted modifiers by the tracing algorithm of PCHT.

2.2. Cryptographic Building Blocks

For PCHT, CHET and ABET are two critical components.

• CHET. Blockchain rewriting is realized by CHET in this paper. There are two trapdoors in CHET: the long-term and the ephemeral. The former is generated by the authority in system initialization. The latter is computed by the IoT data owner during mutable transaction publication. Only if the modifier has both of them could he succeed in rewriting the mutable transaction.
• ABET. It is a key component to construct PCHT, which can achieve fine-grained blockchain rewriting and offer black-box traceability in traitor tracing. The ephemeral trapdoor encrypted with the encrypting algorithm of ABET could only be decrypted by the modifier who has the proper attributes. Compared with traditional CP-ABE schemes, ABET has an additional tracing algorithm that takes public parameters and tracing key as input and outputs the identity set of traitors.

2.3. Instantiation and Implementation

According to the generic construction scheme of ABET introduced in [27], we choose FAME [23] and robust fingerprinting code [26] to initiate it. In addition to this, we also rely on the discrete logarithm-based CHET [22]. Moreover, the PCHT-based redactable blockchain scheme for IoT is also built in the paper, which makes the pirate decoder-related corrupted modifiers traceable.

3. Related Work

Traceable CP-ABE. Generally, the tracing algorithm of traceable CP-ABE scheme has access to the pirate decoder $D_S$ and takes tracing key $tk$ as input, outputs the index $i\in \{1,\dots ,k\}$ that indicates a secret key $s{k}_i$ was used to create the pirate decoder. It could be divided into two categories: public tracing and secret tracing.

An augmented broadcast encryption with public traitor tracing was introduced in [28] and the tracing algorithm can be executed by any public user. However, it has sub-linear size ciphertext $\mathcal{O}\left(\sqrt{k}\right)$. Later, Ning et al. proposed a traceable CP-ABE scheme with constant-size ciphertext $\mathcal{O}\left(1\right)$ where the construction is built on top of a CP-ABE [29] and an anonymous HIBE [30]. Although it has impressive practicality in commercial [31], this scheme only supports white-box traceability, i.e., its traceability property only works when the malicious users leak the well-formed decryption keys directly. An expressive black-box traceable CP-ABE was proposed in [32], while it has sub-linear size ciphertext $\mathcal{O}\left(\sqrt{k}\right)$ so that the practicality is hindered seriously. Moreover, public tracing is not suitable for the tracing of blockchain rewriting since the blockchain rewriting event happens infrequently and pirate tracing is the responsibility for the authority in order to force the key management policy.

Secret tracing means the tracing algorithm treats tracing key $tk$ as secret value and $tk$ is only hold by the authority. Fingerprinting code is usually used to construct secret tracing scheme. Boneh and Naor proposed the public-key-based traitor tracing system with constant-size ciphertext $\mathcal{O}\left(1\right)$ [33]. The proposed system relies on a fingerprinting code [34]. The fingerprinting code includes a code generator algorithm and a tracing algorithm which is used for traitor tracing. Recently, Lai et al. introduced a traceable attribute-based encryption scheme with constant-size ciphertext, which is also based on the fingerprinting code [27]. The proposed construction is built on an efficient CP-ABE scheme [23], and a Tardos code [35]. In this paper, we construct a practical ABET scheme with black-box traceability, while supporting constant-size ciphertext $\mathcal{O}\left(1\right)$ and secret tracing. A difference comparison among the existing ABET schemes is shown in

Table 1. Comparison of traceable CP-ABE schemes.

	CP-ABE Scheme	Ciphertext Size	Black-Box	Secret Tracing
[32]	ABE [29]	$\mathcal{O}\left(\sqrt{k}\right)$	√	×
[31]	ABE [29]	$\mathcal{O}\left(1\right)$	×	×
[24]	FAME [23]	$\mathcal{O}\left(1\right)$	√	×
Ours	FAME [23]	$\mathcal{O}\left(1\right)$	√	√

.

Redactable blockchain. To achieve blockchain redacting, many schemes were proposed and they could be categorized into two types [36]. The non-cryptography-based schemes realize blockchain rewriting by some mechanisms. Puddu et al. proposed $\mu$chain and realized blockchain redacting by a voting-like approach where each participant was assigned a key sharing by a dynamic proactive secret sharing scheme and the modifier had to collect enough votes to achieve blockchain redacting [37]. The cryptography-based schemes mainly adopted the chameleon hash to achieve blockchain redacting and a series of notable works have been proposed.

The chameleon hashing and signatures were put forward by Krawczyk and Rabin [38]. In 2017, Ateniese et al. first introduced the concept of redactable blockchain where the traditional hash function was replaced by a chameleon hash function to calculate the hash and only the party who owns the trapdoor could efficiently find valid collisions to rewrite the blockchain without changing the hash output [21]. To achieve blockchain redacting in a fine-grained and controlled way, Derler et al. proposed a novel cryptographic primitive, named policy-based chameleon hash (PCH), and introduced it into the blockchain redacting [39]. Anyone who satisfies the policy embedded in the transaction could then find arbitrary collisions for a given hash. The blockchain rewriting could be manipulated at a transaction level when PCH is applied to the blockchain. After that, To achieve rewriting authorization in a decentralized setting, Zhang et al. introduced a multi-authority policy-based chameleon hash (MPCH) [40], while Ma et al. presented a decentralized policy-based chameleon hash (DPCH) [41]. Both MPCH and DPCH utilize CHET to manage data rewriting, with multi-authority attribute-based encryption [42] being leveraged to handle the rewriting privilege. However, neither of them considered tracing the malicious modifiers.

Tian et al. were the first to consider accountability in PCH-based redactable blockchains. However, their solution only provides weak accountability by linking the modified transaction to its modifier without addressing the issue of key leakage [24]. Panwar et al. proposed a permissioned redactable blockchain that provides traceability and revocability through the use of dynamic group signature schemes (DGSS) and revocable FAME (RFAME). While their solution links modified transactions to their modifiers and offers revocation of malicious modification privileges, the traceability only offers weak accountability, and the revocation mechanism has a linear complexity with the size of non-revoked modifiers [25].

To overcome the limitations of current mutable blockchain solutions, we have proposed a PCHT-based blockchain rewriting scheme with black-box traceability, which enables traitor tracing and effectively resolves the issue of key leakage. In

Table 2. Comparison of mutable blockchain schemes.

	Underlying Method	Fine-Grained	Traceability	Traitor Tracing
[37]	hard fork	×	×	×
[39]	CHET	√	×	×
[24]	CHET	√	√	×
Ours	CHET	√	√	√

, we compare our scheme with existing mutable blockchain solutions.

4. Preliminary

In this section, several relevant cryptography fundamentals involved in PCHT are presented and the important notations used in this paper are listed in

Table 3. The notations used in this paper.

Notation	Definition
$DO$	the IoT data owner
$TM$	the transaction modifier
$s{k}_{do}$	the secret key of IoT data owner
$s{k}_{tm}$	the secret key of transaction modifier
$\mathbb{A}$	the access structure
M	the matrix representing a MSP
$\rho$	the mapping function
S	the set of attributes
T	the identity set of traitors
${\mathrm{D}}_{\mathrm{S}}$	the pirate decoder for a set of attributes S

.

4.1. Chameleon Hash with Ephemeral Trapdoors

In CHET [22], the ephemeral trapdoor is chosen during hashing algorithm. It is necessary to hold both the long-term and the ephemeral trapdoor to computing hash collision successfully. This primitive includes the following five algorithms:

• $CHET.Setup\left(1^{\lambda }\right)$: It requires the security parameter $\lambda$ as input, and outputs the public parameter $pp$.
• $CHET.KGen\left(pp\right)$: It requires $pp$ as input, and outputs the key pair $(p{k}_{CHET},s{k}_{CHET})$ where the $s{k}_{CHET}$ is used as the long-term trapdoor.
• $CHET.Hash(p{k}_{CHET},m)$: It requires $p{k}_{CHET}$ and a message m as input, and outputs hash $\eta$, randomness r, and the ephemeral trapdoor $etd$.
• $CHET.Verify(p{k}_{CHET},m,\eta ,r)$: It requires $p{k}_{CHET}$, m, $\eta$, and r as input, and outputs a bit $b\in \{0,1\}$.
• $CHET.Adapt(s{k}_{CHET},etd,m,m^{\prime },\eta ,r)$: It requires $s{k}_{CHET}$, $etd$, m, $m^{\prime }$, $\eta$, and r as input, and outputs the new randomness $r^{\prime }$.

Correctness: Note that the verifying algorithm would always verify if the given hash is valid, and outputs ⊥ otherwise. Moreover, the correctness of CHET could be described as:

$\mathrm{For}\mathrm{all}$: $\lambda \in \mathbb{Z}$,

$$\begin{array}{cc}\hfill & pp\leftarrow CHET.Setup\left(1^{\lambda }\right),\hfill \\ \hfill & (s{k}_{CHET},p{k}_{CHET})\leftarrow CHET.KGen\left(pp\right),\hfill \\ \hfill & (\eta ,r,etd)\leftarrow CHET.Hash(p{k}_{CHET},m),\hfill \\ \hfill & r^{\prime }\leftarrow CHET.Adapt(s{k}_{CHET},etd,m,m^{\prime },\eta ,r),\hfill \end{array}$$

we have that:

$$\begin{array}{cc}\hfill & CHET.Verify(p{k}_{CHET},m,\eta ,r)=CHET.Verify(p{k}_{CHET},m^{\prime },\eta ,r^{\prime })=1.\hfill \end{array}$$

For security, CHET is required to be indistinguishable, i.e., any adversary could not distinguish the randomness generated in hashing step or adapting step. Moreover, CHET also satisfies the collision-resistant (i.e., any adversary without holding both the long-term and the ephemeral trapdoor simultaneously cannot find any hash collision).

4.2. Monotone Span Program (MSP)

Specifically, let $\{x_1,x_2,\cdots ,x_n\}$ be a set of boolean variables, the MSP is a labeled matrix, denoted as $\widehat{\mathbf{M}}(\mathbf{M},\rho )$ where $\rho$ is a mapping $\rho :\{1,\cdots ,n_1\}\to \mathcal{U}$ and $\rho \left(i\right)=x_i$ (i.e., the ith row of M is marked as $x_i$).

Suppose $\delta \in {\{0,1\}}^n$ is the input of boolean function f, the sub matrix ${\mathbf{M}}_{\delta }$ consists of d rows of $\mathbf{M}$ that satisfies the following condition: the label of row is $x_i$ and ${\delta }_i=1$. We say that the $(\mathbf{M},\rho )$ accepts $\delta$iff$\overrightarrow{1}\in span\left({\mathbf{M}}_{\delta }\right)$ where $\overrightarrow{1}=(1,1,\cdots ,1)$ and $span\left({\mathbf{M}}_{\delta }\right)$ is a certain linear combination of all rows in ${\mathbf{M}}_{\delta }$.

The linear secret-sharing scheme could be built on MSP. First, suppose $\{P_1,P_2,\cdots ,P_n\}$ is the set of participants and for $G\in \{P_1,P_2,\cdots ,P_n\}$, ${\delta }_G\in {\{0,1\}}^n$ is the feature vector of G, which means the ith coordinate is 1 only if $P_i\in G$. We consider the column vector $\overrightarrow{r}={(r_1,r_2,\cdots ,r_{n_2})}^{\top }$ and $\overrightarrow{1}·\overrightarrow{r}={\sum }_{i=1}^{n_2}{r}_i=s$ where $r_1,r_2,\cdots ,r_{n_2}$ are chosen at random from ${\mathbb{Z}}_q$, and s is the shared secret. $\mathbf{M}\overrightarrow{r}\in {\mathbb{Z}}_q^{n_1\times 1}$ is the vector of $n_1$ shares of s and each one is labeled according to $\widehat{\mathbf{M}}$.

The reconstruction of secret could be described as below: suppose $G^{*}\in \mathbb{A}$ is an authorization set and ${\delta }_{G^{*}}$ is the feature vector of $G^{*}$, we obtain $\overrightarrow{1}\in span\left({\mathbf{M}}_{\delta }\right)$, which means there exists a constant set ${\left\{{\beta }_u\right\}}_{u\in n_1}$ such that

$$\sum _{i=1}^{n_1}{\beta }_i{\mathbf{M}}_i=\overrightarrow{1},$$

(1)

and then ${\sum }_{i=1}^{n_1}{\beta }_i{\mathbf{M}}_i·\overrightarrow{r}=\overrightarrow{1}·\overrightarrow{r}=s$. Note that these constants ${\left\{{\beta }_u\right\}}_{u\in n_1}$ could be found in polynomial time.

4.3. Robust Fingerprinting Code

To address the problem of watermarking digital content, Boneh et al. introduced fingerprinting codes, which are a pair of the following two algorithms [34]:

• $FC.Gen(n,a)$: On input the number of users and security parameter a, output a tracing key $\alpha$ and a codebook $C\in {\{0,1\}}^{n\times \ell }$ where each row $c_i$ is the codeword for user i and ℓ is the fingerprinting code.
• $FC.Trace(tk,C^{*})$: It requires $tk$ and a collusion codeword $C^{*}$ as input, outputs the identity set T of accused users ${\mathcal{U}}_{acc}$.

A fingerprinting code is t-collusion resistant means that there are t corrupted users ${\mathcal{U}}_{cor}$ and their pirate codeword $C^{*}$ generated by pooling their codewords together, such that:

$$\mathrm{Pr}[{\mathcal{U}}_{\mathrm{acc}}=\mathrm{Ø}\mathrm{or}{\mathcal{U}}_{\mathrm{cor}}⊉{\mathcal{U}}_{\mathrm{acc}}:{\mathcal{U}}_{\mathrm{acc}}\leftarrow \mathrm{FC}.\mathrm{Trace}(\mathrm{tk},{\mathrm{C}}^{*})]\le \mathrm{a}$$

A fingerprinting code is $\delta$-robust means that there exists at most $\delta \ell$ symbols ‘?’ in codeword.

4.4. ABET

An ABET scheme consists of the following five algorithms:

• $ABET.Setup(n,1^{\lambda })$: It requires the security parameter $\lambda$ and the number of participants n as input, outputs key pair $(mpk,msk)$ and tracing key $tk$.
• $ABET.KGen(mpk,msk,S_i)$: It requires $(mpk,msk)$ and the attribute set $S_i$ of participant i as input, outputs the individual secret key $s{k}_i$.
• $ABET.Encrypt(mpk,\mathbb{A},m)$: It requires $mpk$, access structure $\mathbb{A}$, and message m as input, outputs the ciphertext $CT$.
• $ABET.Decrypt(mpk,CT,s{k}_i)$: It requires $mpk$, $CT$, and $s{k}_i$ as input, outputs m or ⊥.
• $ABET.{Trace}^{{\mathrm{D}}_{\mathrm{S}}}(mpk,tk,S)$: It requires a pirate decoder ${\mathrm{D}}_{\mathrm{S}}$ (associated with a set of attributes S), $mpk$ and $tk$ as input, outputs the identity set T of traitors.

5. Policy-Based Chameleon Hash with Traceability

In this section, we give the formal definition and security model of PCHT.

5.1. Formal Definition

We consider three entities in PCHT: an authority $auth$, an IoT data owner $DO$, and a transaction modifier $TM$. Specifically, it includes the following algorithms:

• $PCHT.Setup(n,1^{\lambda })$: It requires the security parameter $\lambda$ and the number of participants n as input, outputs the key pair ($pk$,$sk$).
• $PCHT.KGen(pk,sk,S_i)$: It requires ($pk$,$sk$) and attribute set $S_i\in \mathcal{U}$ as input, outputs the secret key $s{k}_i$.
• $PCHT.Hash(pk,m,\mathbb{A})$: It requires $pk$, message m, and $\mathbb{A}$ as input, outputs randomness r, chameleon hash $\eta$, and ciphertext $CT$.
• $PCHT.Verify(pk,m,\eta ,r)$: It requires $pk$, m, $\eta$, and r as input, outputs a bit $b\in \{0,1\}$.
• $PCHT.Adapt(s{k}_{tm},m^{\prime },m,\eta ,r,CT)$: It requires $s{k}_{tm}$, new message $m^{\prime }$, m, $\eta$, r, and $CT$ as input, outputs the new randomness $r^{\prime }$, chameleon hash $\eta$, and ciphertext $C{T}^{\prime }$.
• $PCHT.{Trace}^{{\mathrm{D}}_{\mathrm{S}}}(pk,sk,S)$: It requires a pirate decoder ${\mathrm{D}}_{\mathrm{S}}$ associated with a set of attributes S, ($pk$,$sk$) as input, outputs an index set $T\subseteq \{1,\dots ,n\}$ of corrupted modifiers.

Correctness: The PCHT is correct if for all:

$$\begin{array}{cc}\hfill & (pk,sk)\leftarrow PCHT.Setup(n,1^{\lambda }),\lambda \in \mathbb{Z},\hfill \\ \hfill & s{k}_i\leftarrow PCHT.KGen(pk,sk,S_i),S_i\in \mathcal{U},\hfill \\ \hfill & (r,\eta ,CT)\leftarrow PCHT.Hash(pk,m,\mathbb{A},s{k}_{do}),m\in \mathcal{M},\hfill \\ \hfill & (r^{\prime },\eta ,C{T}^{\prime })\leftarrow PCHT.Adapt(s{k}_{tm},m^{\prime },m,r,\eta ,CT),\hfill \end{array}$$

we have that:

$$\begin{array}{c}\hfill PCHT.Verify(pk,m,\eta ,r)=PCHT.Verify(pk,m^{\prime },\eta ,r^{\prime })=1.\end{array}$$

5.2. Security Model

This section considers two security models of PCHT: indistinguishability and collision resistance.

Indistinguishability. Informally, the indistinguishability requires that the adversary can not be sure if the randomness of the chameleon hash was generated by the hashing or adapting algorithm. The security experiment is shown below.

$$\begin{array}{cc}\hfill & {\mathbf{Exp}}_{PCHT,\mathcal{A}}^{IND}\left(1^{\lambda }\right):\hfill \\ \hfill & (sk,pk)\leftarrow PCHT.Setup(n,1^{\lambda });b\leftarrow \{0,1\}\hfill \\ \hfill & b^{\prime }\leftarrow {\mathcal{A}}^{{\mathcal{O}}_{HashOrAdapt}(sk,·,·,·,·,b)}\left(pk\right)\hfill \\ \hfill & return1,if{b}^{\prime }=b;else,return0\hfill \end{array}$$

$$\begin{array}{cc}\hfill & \mathbf{Oracle}{\mathcal{O}}_{HashOrAdapt}(sk,S_i,m,m^{\prime },\mathbb{A},b):\hfill \\ \hfill & s{k}_i\leftarrow PCHT.KGen(pk,sk,S_i)\hfill \\ \hfill & (r_0,{\eta }_0,C{T}^0)\leftarrow PCHT.Hash(pk,m^{\prime },\mathbb{A})\hfill \\ \hfill & (r_1,{\eta }_1,C{T}^1)\leftarrow PCHT.Hash(pk,m,\mathbb{A})\hfill \\ \hfill & r_1\leftarrow PCHT.Adapt(s{k}_i,m^{\prime },m,{\eta }_1,r_1,C{T}^1)\hfill \\ \hfill & return(r_b,{\eta }_b,C{T}^b)\hfill \end{array}$$

If the following advantage for any PPT adversary $\mathcal{A}$ is negligible, $PCHT$ scheme is indistinguishability secure:

$${\mathbf{Adv}}_{\mathcal{PCHT},\mathcal{A}}^{IND}\left(1^{\lambda }\right)=|\mathrm{Pr}[{\mathbf{Exp}}_{\mathcal{PCHT},\mathcal{A}}^{\mathrm{IND}}\left(1^{⌣}\right)=1]-1/2|.$$

Collision resistance. Informally, the collision resistance requires that the adversary could not find collisions for hashes computed with the access policies they are not satisfied with. The security experiment is shown below.

$$\begin{array}{cc}\hfill & {\mathbf{Exp}}_{PCHT,\mathcal{A}}^{CR}\left(1^{\lambda }\right):\hfill \\ \hfill & (sk,pk)\leftarrow PCHT.Setup(n,1^{\lambda });{\mathcal{L}}_1,{\mathcal{L}}_2,{\mathcal{L}}_3\leftarrow \mathrm{Ø}\hfill \\ \hfill & (m^{*},r^{*},{m^{*}}^{\prime },{r^{*}}^{\prime },{\eta }^{*})\leftarrow {\mathcal{A}}^{\mathcal{O}}\left(pk\right),\hfill \\ \hfill & where\mathcal{O}\leftarrow \{{\mathcal{O}}_{KGen},{\mathcal{O}}_{KGe{n}^{\prime }},{\mathcal{O}}_{Hash},{\mathcal{O}}_{Adapt}\}.\hfill \\ \hfill & return1,if1=PCHT.Verify(pk,m^{*},{\eta }^{*},r^{*})\hfill \\ \hfill & =PCHT.Verify(pk,{m^{*}}^{\prime },{\eta }^{*},{r^{*}}^{\prime })\wedge ({\eta }^{*},·,\mathbb{A})\in {\mathcal{L}}_3,\hfill \\ \hfill & forsome\mathbb{A}\wedge m^{*}\ne {m^{*}}^{\prime }\wedge \mathbb{A}\cap {\mathcal{L}}_1=\mathrm{Ø}\wedge ({\eta }^{*},m^{*},·)\notin {\mathcal{L}}_3\hfill \\ \hfill & else,return0\hfill \end{array}$$

$$\begin{array}{cc}\hfill & \mathbf{Oracle}{\mathcal{O}}_{KGen}(pk,sk,S_i):\hfill \\ \hfill & s{k}_i\leftarrow PCHT.KGen(pk,sk,S_i);{\mathcal{L}}_1\leftarrow {\mathcal{L}}_1\cup \left\{S_i\right\}\hfill \\ \hfill & returns{k}_i\hfill \\ \hfill & \mathbf{Oracle}{\mathcal{O}}_{KGe{n}^{\prime }}(pk,sk,S_i):\hfill \\ \hfill & s{k}_i\leftarrow PCHT.KGen(pk,sk,S_i);{\mathcal{L}}_2\cup \{i,s{k}_i\}\hfill \\ \hfill & i\leftarrow i+1\hfill \\ \hfill & \mathbf{Oracle}{\mathcal{O}}_{Hash}(pk,m,\mathbb{A})\hfill \\ \hfill & (\eta ,r,CT)\leftarrow PCHT.Hash(pk,m,\mathbb{A})\hfill \\ \hfill & {\mathcal{L}}_3\leftarrow {\mathcal{L}}_3\cup \left\{(\eta ,m,\mathbb{A})\right\}\hfill \\ \hfill & return(\eta ,r,CT)\hfill \\ \hfill & \mathbf{Oracle}{\mathcal{O}}_{Adapt}(m,m^{\prime },\eta ,r,j,CT,s{k}_{tm}):\hfill \\ \hfill & return\perp ,if(j,s{k}_{tm})\notin {\mathcal{L}}_{2}forsomes{k}_{tm}\hfill \\ \hfill & r^{\prime }\leftarrow PCHT.Adapt(pk,s{k}_{tm},m,m^{\prime },\eta ,r,CT)\hfill \\ \hfill & if(\eta ,m,\mathbb{A})\in {\mathcal{L}}_{3}forsome\mathbb{A},\hfill \\ \hfill & let{\mathcal{L}}_3\leftarrow {\mathcal{L}}_3\cup \left\{(\eta ,m^{\prime },\mathbb{A})\right\}\hfill \\ \hfill & return{r}^{\prime }\hfill \end{array}$$

If the following advantage is negligible, $PCHT$ scheme is collision resistant:

$${\mathbf{Adv}}_{\mathcal{PCHT},\mathcal{A}}^{CR}\left(1^{\lambda }\right)=Pr[{\mathbf{Exp}}_{\mathcal{PCHT},\mathcal{A}}^{CR}\left(1^{\lambda }\right)=1].$$

6. Security Analysis and Instantiation

6.1. Security Analysis

The construction of PCHT involves two cryptographic building blocks: chameleon hash with ephemeral trapdoor scheme with indistinguishability as well as collision resistance, and a traceable CP-ABE scheme with traceability. The security results of PCHT are shown below and the detailed proofs are also given.

Theorem 1.

If the underlying CHET is indistinguishable, PCHT scheme has indistinguishability secure.

Proof. 

Let $\mathcal{A}$ be a PPT adversary who can break the indistinguishability of PCHT with considerable advantage and $\mathcal{B}$ be a PPT distinguisher that can break the indistinguishability of CHET with the following advantage: ${\mathbf{Adv}}_{PCHT,\mathcal{A}}^{IND}\left(1^{\lambda }\right)={\mathbf{Adv}}_{CHET,\mathcal{B}}^{IND}\left(1^{\lambda }\right)$. Moreover, $\mathcal{B}$ is given a $HashOrAdapt$ oracle.

Setup. At the beginning, $\mathcal{B}$ creates n participants for $\mathcal{A}$ and honestly generates a secret key for each one.

Query. If $\mathcal{A}$ queries $(S_i,m,m^{\prime },\mathbb{A})$, then $\mathcal{B}$ obtains $(r_b,{\eta }_b,C{T}^b)$ from his $HashOrAdapt$ oracle. Finally, $\mathcal{B}$ returns $(r_b,{\eta }_b,C{T}^b)$.

Guess. Both of $\mathcal{A}$ and $\mathcal{B}$ output a bit b. If $\mathcal{A}$ guesses correctly, then $\mathcal{B}$ can break the indistinguishability of CHET. □

Theorem 2.

The PCHT scheme is collision-resistant if the traceable CP-ABE scheme is adaptive secure, and the underlying chameleon hash with ephemeral trapdoor is collision resistant.

Proof. 

A sequence of games ${\mathbb{G}}_i$ ($i=0,\dots ,3$) are defined.

${\mathbb{G}}_0$: The original game for collision resistance.

${\mathbb{G}}_1$: Let q be an upper bound of the queries to Hash oracle. All queries are answered as in ${\mathbb{G}}_0$, but the g-th one. In the g-th query, the encrypted message $et{d}^{*}$ in $C{T}^{*}$ is replaced by 0. First, two messages $M_0=etd*$, $M_1=0$ are submitted to the challenger by $\mathcal{S}$. Then, $\mathcal{A}$ obtains the tuple $({\eta }^{*},m^{*},r^{*},C{T}^{*})$ from $\mathcal{S}$. If $\mathcal{A}$ behaves significantly different in ${\mathbb{G}}_0$ and ${\mathbb{G}}_1$, $\mathcal{S}$ can use $\mathcal{A}$ to break the semantic security of the traceable CP-ABE. Hence, we have

$$\left|\mathrm{Pr}\left[{\mathcal{S}}_0\right]-\mathrm{Pr}\left[{\mathcal{S}}_1\right]\right|\le {\mathbf{Adv}}_{\mathcal{S}}^{ABET}\left(\lambda \right).$$

${\mathbb{G}}_2$: As ${\mathbb{G}}_1$ except that in the g-th query, if a valid collision is given by $\mathcal{A}$ which was not previously returned by the Adapt oracle, $\mathcal{S}$ outputs a random bit. First, all public parameters are honestly returned by $\mathcal{S}$. Then, $\mathcal{S}$ obtains a randomness r from the Adapt oracle if $\mathcal{A}$ submits an adapt query. If $\mathcal{A}$ gives a collision $({\eta }^{*},m^{*},r^{*},C{T}^{*},m^{{*}^{\prime }},r^{{*}^{\prime }},$$C{T}^{{*}^{\prime }})$ in the g-th query and all the verifications hold, then a valid collision $(h^{*},m^{{*}^{\prime }},r^{{*}^{\prime }},C{T}^{{*}^{\prime }})$ is given to CHET by $\mathcal{S}$. Therefore, we have

$$\left|\mathrm{Pr}\left[{\mathcal{S}}_1\right]-\mathrm{Pr}\left[{\mathcal{S}}_2\right]\right|\le {\mathbf{Adv}}_{\mathcal{S}}^{CHET}\left(\lambda \right).$$

Combining the above results, we have

$${\mathbf{Adv}}_{\mathcal{A}}^{PCHT}\left(\lambda \right)\le n\left(\lambda \right)·({\mathbf{Adv}}_{\mathcal{S}}^{ABET}\left(\lambda \right)+{\mathbf{Adv}}_{\mathcal{S}}^{CHET}\left(\lambda \right)).$$

□

Traceability. The PCHT scheme is traceable since the underlying fingerprinting code is $\delta$-robust. In the case that $\delta =1$, $D_S$ will decrypt correctly if all ${\omega }_i^{\left(j\right)}=0$ or all ${\omega }_i^{\left(j\right)}=1$ for $j\in {\mathcal{U}}_{cor}$. The complex case is that it can be either 1 or 0 for the position i. In summary, the traceability of fingerprinting code will return the indices set of traitors. For an imperfect decoder, it can also achieve traceability by the robustness of the fingerprinting codes. Since $D_S$ has $\delta$-correctness, it still works properly for many positions.

6.2. Instantiation

In this section, a practical instantiation of PCHT is given. First, we combine the efficient CP-ABE scheme [23] with Tardos code [35] (a robust fingerprinting code) to initiate a traceable CP-ABE scheme with traceability. Based on the asymmetric prime-order Type-III pairing, the chosen CP-ABE scheme in [23] is adaptively secure under the standard decision linear assumption and equips the characteristics such as unbounded ABE universes and constant decryption time. Then, the discrete logarithm-based CHET [22] is chosen to initiate CHET. The instantiation of the PCHT scheme is shown below.

• $PCHT.Setup(n,1^{\lambda })$: It takes a security parameter $\lambda$ and the number of users n as input.

  −

  Consider a bilinear pairing: $\widehat{e}:\mathbb{G}\times \mathbb{H}\to {\mathbb{G}}_{\mathbb{T}}$, where g and h are the generators $\mathbb{G}$ and $\mathbb{H}$, respectively.

  −

  Run $CHET.KGen\left(pp\right)$ to obtain the long-term secret/public key pair: $(k,h^k)$, where $k\in {\mathbb{Z}}_p^{*}$ and $pp\leftarrow CHET.Setup\left(1^{\lambda }\right)$.

  −

  Let $ϵ=1/2^{\lambda }$ and run $FC.Gen(n,ϵ)$ to obtain the tracing wordcode set codebook $\mathrm{\Phi }$ and tracing key $tk$: $FC.Gen(n,ϵ)\to \{tk,\mathrm{\Phi }\}$, where $\mathrm{\Phi }:=\{{\varphi }_1,\cdots ,{\varphi }_n\}$.

  −

  Pick $(a_1,a_2,b_1,b_2){\leftarrow }_R{\mathbb{Z}}_p^{*}$, $(w_1,w_2,w_3){\leftarrow }_R{\mathbb{Z}}_p$, compute: $A_1:=h^{a_1},A_2:=h^{a_2},H_1:{\{0,1\}}^{*}\to \mathbb{G},H_2:{\{0,1\}}^{*}\to {\mathbb{Z}}_q,T_1:=\widehat{e}{\{g,h\}}^{w_1{a}_1+w_3},T_2:=\widehat{e}{\{g,h\}}^{w_2{a}_2+w_3}.$

  −

  Choose the dummy attributes ${\left\{{\mathrm{Char}}^u\right\}}_{u\in \{0,1\}}$, ${\left\{{\mathrm{Char}}_j\right\}}_{j\in \{\ell \}}$ and return:

  $pk:=\{h^k,g,h,A_1,A_2,T_1,T_2,H_1,H_2,{\left\{{\mathrm{Char}}^u\right\}}_{u\in \{0,1\}},{\left\{{\mathrm{Char}}_j\right\}}_{j\in \{\ell \}}\}$,

  $sk:=\{k,a_1,a_2,b_1,b_2,g^{w_1},g^{w_2},g^{w_3},\mathrm{\Phi },tk\}.$

• $PCHT.KGen(pk,sk,S_i)$: It takes $pk$, $sk$, and attribute set $S_i$ of participant i as input:

  −

  Pick $(d_1,d_2)\in {\mathbb{Z}}_p^{*}$, $d=d_1+d_2$, compute: ${\mathrm{sk}}_0:=(h^{b_1{d}_1},h^{b_2{d}_2},h^d).$

  −

  For $j\in \{1,\dots ,\ell \}$ (ℓ is the code length), let ${\varphi }_i^{\left(j\right)}\in \{0,1\}$ be the j-th bit of ${\varphi }_i$ and set $S_{i,j}=S_i\cup {\mathrm{Char}}^{{\varphi }_i^{\left(j\right)}}\cup {\mathrm{Char}}_j$, for all $s\in S_{i,j}$ and $t=\{1,2\}$, compute:

  $$\begin{array}{c}\hfill {\mathrm{sk}}_{s,t}:=H_1{\left(s1t\right)}^{b_1{d}_1/a_t}·H_1{\left(s2t\right)}^{b_2{d}_2/a_t}·H_1{\left(s3t\right)}^{d/a_t}·g^{{\upsilon }_s/a_t},\end{array}$$

  where ${\upsilon }_s\in {\mathbb{Z}}_q$. Set ${\mathrm{sk}}_s:=\{{\mathrm{sk}}_{s,1},{\mathrm{sk}}_{s,2},g^{-{\sigma }_s}\}$.

  −

  Pick ${\upsilon }^{\prime }\in {\mathbb{Z}}_q$, for $t=\{1,2\}$, compute:

  ${\mathrm{sk}}_t^{\prime }:=g^{w_t}·H_1{\left(011t\right)}^{b_1{d}_1/a_t}·H_1{\left(012t\right)}^{b_2{d}_2/a_t}·H_1{\left(013t\right)}^{d/a_t}·g^{{\upsilon }^{\prime }/a_t}.$

  −

  Then set: ${\mathrm{sk}}^{\prime }:=({\mathrm{sk}}_1^{\prime },{\mathrm{sk}}_2^{\prime },g^{w_3}·g^{-{\upsilon }^{\prime }})$. Finally, the decryption key for $S_{i,j}$ is:

  $s{k}_{i,j}:=({\mathrm{sk}}_0,{\left\{{\mathrm{sk}}_s\right\}}_{s\in S_{i,j}},{\mathrm{sk}}^{\prime })$.

  −

  Return the secret key $s{k}_i$ of participant i: $s{k}_i:=(\left\{k\right\},{\left\{s{k}_{i,j}\right\}}_{j\in \{\ell \}}).$

• $PCHT.Hash(pk,m,\mathbb{A},s{k}_{do})$: It takes the master public key $pk$, message m, access structure $\mathbb{A}$, secret key of IoT data owner $s{k}_{do}$ as input:

  −

  Pick a randomness $r\in {\mathbb{Z}}_p^{*}$ and a short bit-string $etd$ as ephemeral trapdoor to obtain a chameleon hash $\eta$: $h^{\prime }=h^{H_2\left(etd\right)},\eta =h^{k·r}·{h^{\prime }}^m.$

  −

  Pick ${\tau }_1,{\tau }_2\leftarrow {\mathbb{Z}}_p$ and $\tau ={\tau }_1+{\tau }_2$, compute: ${\mathrm{ct}}_0:=(A_1^{{\tau }_1},A_2^{{\tau }_2},h^{\tau }).$

  −

  Choose a random position $pos\in \{\ell \}$ and set ${\overline{\mathbb{A}}}_u=\mathbb{A}\wedge \left\{{\mathrm{Char}}^u\right\}\wedge \left\{{\mathrm{Char}}_{pos}\right\}$, where $u\in \{0,1\}$.

  −

  Let $z=1,2,3$ and $u=0,1$, suppose ${\overline{\mathbb{A}}}_u$ has $n_1$ rows and $n_2$ columns, for $\forall v\in \{1,\dots ,n_1\}$, compute:

  ${\mathrm{ct}}_{u,v,z}:=H_1{\left(\pi \left(v\right)z1\right)}^{x_1}·H_1{\left(\pi \left(v\right)z2\right)}^{x_2}·{\prod }_{j=1}^{n_2}{[H_1{\left(0jz1\right)}^{x_1}·H_1{\left(0jz2\right)}^{x_2}]}^{{\overline{\mathbb{A}}}_{u,v,j}},$ where ${\overline{\mathbb{A}}}_{u,v,j}$ denotes the $(v,j)$th element of ${\overline{\mathbb{A}}}_u$. Set ${\mathrm{ct}}_{u,v}:=({\mathrm{ct}}_{u,v,1},{\mathrm{ct}}_{u,v,2},{\mathrm{ct}}_{u,v,3})$.

  −

  Generate a ciphertext on message $msg:=\{r,etd\}$ and compute: ${\mathrm{ct}}^{\prime }:=T_1^{{\tau }_1}·T_2^{{\tau }_2}·msg.$

  −

  Finally, it outputs $C{T}_u=({\mathrm{ct}}_0,{\left\{{\mathrm{ct}}_{u,v}\right\}}_{v\in n_1},{\mathrm{ct}}^{\prime })$. Return $(pos,C{T}_0,C{T}_1,r,h^{\prime },\eta )$.

• $PCHT.Verify(m,\eta ,r,h^{\prime })$: It takes message m, chameleon hash $\eta$, r, $h^{\prime }$ as input. Return 1 if $\eta =h^{k·r}·h^{\prime m}$; otherwise, return 0.
• $PCHT.Adapt(s{k}_{tm},m^{\prime },m,pos,C{T}_0,C{T}_1,r,h^{\prime },\eta ,)$: It takes the secret key of modifier $s{k}_{tm}$, new message $m^{\prime }$, message m, ciphertext $CT$, randomness r, $h^{\prime }$, chameleon hash $\eta$ as input:

  −

  Check $1\stackrel{?}{=}PCHT.Verify(m,\eta ,r,h^{\prime })$.

  −

  If ${\varphi }_i^{pos}=0$, then pick $C{T}_0$ to perform the following using decryption key $s{k}_{tm,pos}$; otherwise (i.e., ${\varphi }_i^{pos}=1$), the same for $C{T}_1$.

  −

  Recall that the set of attributes in $s{k}_{tm,pos}$ satisfies the MSP $({\overline{\mathbb{A}}}_0,\rho )$, then there exist constants ${\left\{{\gamma }_i\right\}}_{i\in I}$ that satisfies the Equation (1) in Section 1, compute: $\mathcal{A}:={\mathrm{ct}}^{\prime }·\widehat{e}({\prod }_{i\in I}{\mathrm{ct}}_{i,1}^{{\gamma }_i},{\mathrm{sk}}_{0,1})·\widehat{e}({\prod }_{i\in I}{\mathrm{ct}}_{i,2}^{{\gamma }_i},{\mathrm{sk}}_{0,2})·\widehat{e}({\prod }_{i\in I}{\mathrm{ct}}_{i,3}^{{\gamma }_i},{\mathrm{sk}}_{0,3}),\mathcal{B}:=\widehat{e}({\mathrm{sk}}_1^{\prime }·{\prod }_{i\in I}{\mathrm{sk}}_{\pi \left(i\right),1},{\mathrm{ct}}_{0,1})·\widehat{e}({\mathrm{sk}}_2^{\prime }·{\prod }_{i\in I}{\mathrm{sk}}_{\pi \left(i\right),2},{\mathrm{ct}}_{0,2})·\widehat{e}({\mathrm{sk}}_3^{\prime }·{\prod }_{i\in I}{\mathrm{sk}}_{\pi \left(i\right),3},{\mathrm{ct}}_{0,3})$, where ${\mathrm{sk}}_{0,1},{\mathrm{sk}}_{0,2},{\mathrm{sk}}_{0,3}$ denote the first, second, and third element of ${\mathrm{sk}}_0$; the same rule applies to ${\mathrm{ct}}_0$.

  −

  Derive the ephemeral trapdoor $etd$ and randomness r from $\mathcal{A}/\mathcal{B}$, and then compute: $r^{\prime }:=r+(m-m^{\prime })·H_2\left(etd\right)/k.$

  −

  Run $PCHT.Hash(pk,m^{\prime },\mathbb{A},s{k}_{tm})$ to obtain position $po{s}^{\prime }$, ciphertext $C{T}_0^{\prime }$, and $C{T}_1^{\prime }$ on $ms{g}^{\prime }:=(r^{\prime },etd)$ and return $(po{s}^{\prime },C{T}_0^{\prime },C{T}_1^{\prime },r^{\prime },h^{\prime },\eta )$.

• $PCHT.{Trace}^{{\mathrm{D}}_{\mathrm{S}}}(pk,sk,S)$: Suppose the trace algorithm has black-box access to pirate decoder ${\mathrm{D}}_{\mathrm{S}}$. The authority takes $(pk,sk)$ as input:

  −

  To obtain the identity set T of traitors, the $auth$ performs as follows for each j in $\{\ell \}$:

  ∗

  Choose an access policy $\mathbb{B}$ which is only satisfied by S and not satisfied by any subset of S;

  ∗

  Set ${\overline{\mathbb{B}}}_u:=\mathbb{B}\wedge \left\{Att{r}_j\right\}\wedge \left\{Att{r}^u\right\}$, where $u\in \{0,1\}$;

  ∗

  Let $N=O({\lambda }^{2}ln\ell )$ and repeat the following steps for N times: pick two random message m, $m^{\prime }$, compute:

  $$\begin{array}{cc}\hfill C{T}_0& \leftarrow PCHT.Hash(pk,m,{\overline{\mathbb{B}}}_0),\hfill \\ \hfill C{T}_1& \leftarrow PCHT.Hash(pk,0,{\overline{\mathbb{B}}}_1),\hfill \\ \hfill C{T}_0^{\prime }& \leftarrow PCHT.Hash(pk,m^{\prime },{\overline{\mathbb{B}}}_0),\hfill \\ \hfill C{T}_1^{\prime }& \leftarrow PCHT.Hash(pk,m^{\prime },{\overline{\mathbb{B}}}_1).\hfill \end{array}$$

  Set $CT:=(j,C{T}_0,C{T}_1)$ and $C{T}^{\prime }:=(j,C{T}_0^{\prime },C{T}_1^{\prime })$. If ${\mathrm{D}}_{\mathrm{S}}\left(CT\right)=m$, set ${\varphi }^j=0$; else if ${\mathrm{D}}_{\mathrm{S}}\left(C{T}^{\prime }\right)=m^{\prime }$ for more than $\sqrt{\lambda }$ times, set ${\varphi }^j=1$; else, set ${\varphi }^j=‘{?}^{’}$.

  ∗

  Set the unauthorized codeword ${\varphi }_{*}=\{{\varphi }^1\cdots {\varphi }^{\ell }\}$, and run $FC.Trace(tk,{\varphi }_{*})$ to obtain the identity set T of traitors:

  $$T\leftarrow FC.Trace(tk,{\varphi }_{*}).$$

7. PCHT-Based Blockchain Rewriting Scheme for IoT

In this section, we first introduce the application of PCHT for blockchain rewriting and then present a PCHT-based blockchain rewriting scheme for IoT.

7.1. Application for Blockchain Rewriting

We give an application of PCHT for blockchain rewriting, which makes the blockchain remain intact even if certain mutable transactions have been modified. As Figure 2 shows, there are four transactions in the block $B_i$ and their hash values are the leaf nodes of a Merkle tree rooted at $txroot$. Among them, $T_{(i,1)}$ and $T_{(i,3)}$ are mutable transactions associated with different access structures, $T_{(i,2)}$ and $T_{(i,4)}$ are immutable transactions. When the mutable transaction needs to be modified, a transaction modifier could compute valid randomness r without changing its hash value and $txroot$ as long as the attributes $S_i$ embedded in his PCHT-based decryption key $s{k}_{dm}$ are accepted by the access structure $\mathbb{A}$ of this mutable transaction. After modifying, the transaction modifier broadcasts this transaction and randomness r to the network. Each participant could validate the correctness of this mutable transaction and then update its local ledger of the blockchain with new content and randomness.

7.2. System Model

As shown in Figure 1, we consider three types of entities for PCHT-based blockchain rewriting: the authority $auth$, the IoT data owner $DO$, and the transaction modifier $TM$. To clearly describe the PCHT-based blockchain rewriting scheme, we introduce each step in detail as follows.

• System initialization. There are two phases in system initialization:

  −

  Master key pair generation: the $auth$ obtains $(pk,sk)$ by running $PCHT.Setup(n,1^{\lambda })$, and only publishes $pk$ to participants in the IoT blockchain.

  −

  Member key generation: the $auth$ generates individual secret key $s{k}_i$ for each participant with their own attributes set $S_i$ by running $PCHT.KGen(pk,sk,S_i)$.

• Mutable transaction publication. It consists of the two following phases:

  −

  Mutable transaction generation: $DO$ generates a mutable transaction that includes the message m, chameleon hash $\eta$, randomness r, and ciphertext $CT$ by running $PCHT.Hash(pk,m,\mathbb{A})$. Then, $DO$ broadcasts this transaction to other participants in the blockchain for IoT.

  −

  Mutable transaction verification: each participant could validate the transaction by running the verifying algorithm. If the verification algorithm returns 1, this participant could append it to its local ledger and broadcast it continually.

• Mutable transaction rewriting. There are two following phases:

  −

  Mutable transaction rewriting: To rewrite the transaction content from m to $m^{\prime }$, the transaction modifier $TM$ whose attributes are accepted by the access structure $\mathbb{A}$ could run $PCHT.Adapt(s{k}_{tm},m,m^{\prime },CT,\eta ,r)$ to compute a valid hash collision and rewrite the transaction successfully. Then, the $TM$ broadcasts the modified transaction publicly.

  −

  Mutable transaction verification: Each participant could validate the new transaction by running $PCHT.Verify(m^{\prime },\eta ,r^{\prime })$. He would update his local copy with the message $m^{\prime }$ if the transaction is valid and broadcast it to other participants continually.

• Traitor tracing. It could be completed by the following step:

  −

  Corrupted modifiers tracing: The $auth$ could obtain the identity set T of corrupted modifiers who produce the pirate decoder by running $PCHT.{Trace}^{{\mathrm{D}}_{\mathrm{S}}}(pk,sk,S)$.

7.3. Threat Model

In this context, we assume the authority $auth$ would honestly generate the secret key $s{k}_i$ for participant i and perform his traceability duties honestly during traitor tracing. Moreover, the IoT data owner $DO$ would honestly publish the mutable transaction.

Our main security goals are to guarantee indistinguishability of randomness r and chameleon hash $\eta$, protect against adversaries who try to update m without the long-term and/or ephemeral trapdoor and ensure the traceability of $auth$. The corrupted modifiers may launch the following various types of attacks. In this paper, we do not consider network attacks in the permissioned blockchain (e.g., replay attacks, denial of service, etc.), existing works have already focused on them [43].

Indistinguishability. In reality, the adversary could identify chameleon hash has been modified or not to learn the additional knowledge. To avoid this, this property has been formalized by introducing the security model of $\mathit{indistinguishability}$ and a chameleon hash with ephemeral trapdoor scheme with indistinguishability is used to construct the PCHT.

Collision resistance. This property ensures the security of the mutable transaction. The adversary may want to rewrite the mutable transaction when they are not satisfied with the access policies embedded in the transaction. Therefore, we formalize this property by introducing the security model of collision resistance. Moreover, a traceable CP-ABE scheme with adaptive security and a collision-resistant CHET scheme are chosen to construct the PCHT.

Traceability. The corrupted modifiers may collude to produce the pirate decoder by abusing their decryption keys. To solve this, we use a traceable CP-ABE scheme with traceability as well as $\delta$-robust fingerprinting code to construct PCHT.

8. Implementation and Evaluation

In this section, we first implement the proposed instantiation of PCHT using Charm framework [44] and evaluate its performance on a personal computer with Ubuntu 18.04, Intel Core [email protected] GHz, and 4 GB RAM. Based on hyperledger fabric v1.4, the PCHT-based redactable blockchain platform has also been implemented using java-1.8.0, go-1.15.6, docker-20.10, docker-compose-2.3.4, vue-2.9.6, including one CA peer, one ordering peer, and seven committing peers.

In the implementation of PCHT, we use the MNT224 curve for pairing, which is the Type-III curve in PBC and offers a 96-bit security level [23]. The experimental performance of key generation, hashing, and adaption algorithms compared with the PCHBA scheme in [24] is present in Figure 3. Overall, the runtime of these algorithms is proportional to the number of attributes or the size of policies. Since we set the code length $\ell =5$ in the test, the runtime of the key generation algorithm in PCHT is about five times as long as it in PCHBA, which is because the $auth$ needs to generate the decryption key for each code and the runtime of key generation algorithm would increase with the length of code length. In our opinion, the key generation phase only takes place during system initialization and it is critical to the traceability of PCHT. Hence, the reasonable time cost is acceptable. For the hashing and adaption algorithms, the number of attributes ranges from 10 to 100 and the runtime of PCHT is about twice that in PCHBA, which is because there are two ciphertexts that need to be generated and the time cost is moderate. Given the restricted computing power of certain IoT devices, IoT data sharing is collected by data owners while transaction rewriting operations are carried out by full nodes on the IoT blockchain, which possess adequate computational resources for executing the hashing and adaptation algorithms. The rare occurrence of transaction rewriting in the IoT system means that it is unlikely to have any significant detrimental effect on the system’s performance.

The PCHT-based redactable blockchain platform has also been deployed in this paper. To evaluate its performance, we use Tape as the throughput testing tool and the number of transactions included in each block is set to 160. Moreover, the runtime of hashing and adaption algorithms in this test is about 200 ms. Set the proportion of mutable transaction volume to the total transaction volume is 5%, 10%, 15%, 20%, respectively, and we obtain the following test results. As shown in Figure 4, the transaction throughput decreases as the mutable transaction ratio increases, which means the runtime of PCHT imposes a non-negligible impact on system performance. Considering the fact that the mutable transactions happen infrequently in the IoT blockchain, the lower transaction throughput compared with a single application blockchain is reasonable and acceptable.

9. Conclusions

The Internet of Things (IoT) enables the collection of data from multiple parties through sensors, and blockchain technology can serve as an ideal solution for establishing trust in a multi-center cooperation framework. In order to ensure the redaction of data and traceability of any malicious transaction tampering, we propose a policy-based chameleon hash with traceability, known as PCHT, and introduce a PCHT-based blockchain rewriting scheme. Our experimental analysis demonstrates that this scheme does not impose a computational burden on IoT devices. Future work could focus on decentralizing the authority and extending our generic construction to support authority accountability.