2.1

Notations

The main parameters involved in the chameleon short signature and the traitor tracking model in this article are shown in Table 1.

Table 1.

Notations used in the paper.

2.2

Chameleon hash

Chameleon hash function²⁵ CH = (KeyGen, Hash, Check, Adapt) can be consisted by four probability polynomial time algorithms, which are described as follows:

2.3

Short signature

A short signature scheme³⁵ BLS = (KeyGen, Sign, Verify) is composed of three probability polynomial time algorithms, which are defined as follows:

2.4

Computational Diffie-Hellman assumption (CDH)

Let 𝔾 be a multiplicative cyclic group of prime order p related to the security parameters λ, where g is a generator of 𝔾, on given g, g^a, g^b ∈ 𝔾 for any a, b ∈ Z_p to compute the g^ab ∈ 𝔾. If the probability of successfully outputting g^ab ∈ 𝔾 by polytime algorithm A is Pr[A(g, g^a, g^b) = g^ab] ≥ ε, A has the advantage ε in 𝔾 to solve the CDH problem.

Definition 1. We say that the Computational Diffie-Hellman Assumption (CDH) holds if no polytime algorithm has a non-negligible advantage in solving the CDH problem.

3.1

Algorithm description

During system initialization, Setup construct two groups 𝔾, 𝔾_T and bilinear mapping ê from security parameters λ. To get the keys, KeyGen generates the chameleon hash key pair and the short signature key pair (x_σ, y_σ) according to the public parameters. In the process of hash generation, Hash utilizes the chameleon public key to compute a chameleon hash h and its check parameter R with respect to the plaintext M. We can leverage Check to detect the compatibility of output parameters (h, M, R). When signing, Sign constructs a short signature message σ_h related to h from the signature private key x_σ ← sk. During the check of the signed message, Verify utilizes the signature public key y_σ ← pk and the public parameter g to verify the legitimacy of σ_h with respect to h. To obtain the check parameters that suitable for the new plaintext M ’ and the chameleon hash h, Adapt first detects the compatibility of (h, M, R) by Check, and then calculates the check parameters R ’ of the plaintext M ’ according to the chameleon private key x_h ← sk. The specific definition of the above algorithm is as follows:

3.2

Security model

The security model of the chameleon short signature is composed of an enhanced Collision-Resistance game of the chameleon hash function and an Existential-Unforgeability game of the short signature scheme. Each game contains a challenger B and an adversary A. The B simulates the operation of the system and answers the queries from the A. The formal definitions of each game are shown in Figures 2a and 2b, respectively.

Figure 2.

(a) Chameleon hash Collision-Resistance game; (b) Short signature Existential-Unforgeability game.

Collision Resistance. Collision resistance says, even if an adversary has access to an adapt oracle, it cannot find any collisions for messages other than the ones queried to the adapt oracle. Note, this is an even stronger definition than keyexposure, which only requires that one cannot find a collision for some new plaintext, i.e., for some auxiliary value for which the adversary has never seen a collision.

Definition 2 (Collision-Resistance). A chameleon-hash is collision-resistant, if for any polytime adversary A there exists a negligible function ω such that . The corresponding experiment is depicted in Figure 2a.

Existential-Unforgeability. The existential unforgeability of a digital signature means that an adversary cannot achieve a valid forged signature for at least one message even if the adversary has access to a sign oracle.

Definition 3 (EUF-CMA). A chameleon short signature scheme becomes existential unforgeability against adaptive selection message attack, referred to as EUF-CMA security, if for any polytime adversary A there exists a negligible function ω such that . The corresponding experiment is depicted in Figure 2a.

4.1

Trusted sharing

The trusted sharing framework embeds the short chameleon signatures of both parties in the transaction as a watermark into the shared data to reduce the amount of signatures held in the entire system and the size of the watermark in the digital carrier, so as to provide conditions for effective tracking while ensuring the availability and robustness of the digital carrier. The trusted data sharing framework is shown in Figure 3.

Figure 3.

Shared traceability framework.

In publishing original data D, first, the data provider A generates a chameleon hash h based on its own identity information M_a={ID_a, K_a, S_a}, where ID_a is the unique identifier of user A, K_a is the embedding key for watermark, and S_a is the regular signature to (ID_a, K_a); Then, the user A signs h with his own signature private key x_σ, and embeds the chameleon short signature σ_h as watermark into D through K_a to obtain the watermarked carrier D_σ containing the chameleon signature message; Finally, the provider publishes the parameter {ID_a, K_a, S_a, R_a, h, σ_h} generated in the above process to the blockchain system to form copyright information about D.

To get a trusted copy of data D, user B first submits his identity information M_b ={ID_b, K_b, S_b}; Then, the provider A generates the check parameter R_b w.r.t (h, M_b), and embeds σ_h into the original data D using B’s watermark key K_b to obtain the watermarked carrier D_σ ’ so as to ensure that the transaction behavior of both parties is unforgeable and undeniable; Finally, the above-mentioned parameters{ID_b, K_b, S_b, R_b} are all recorded on the blockchain to keep the traitor can be tracked when the data is leaked.

4.2

Efficient tracking

For achieve the efficient tracing to the data leaker, the cascade chain consists of three parts: the copyright chain, the transaction chain, and the copyright block index, the structure is shown in Figure 4. During the publishing of data D_i, the consensus node generates a new copyright block B_n with relevant parameters {ID_a, K_a, S_a, R, h, σ_h} and appends B_n to the chain to form a copyright chain {B_i}_i=1,2,…,n. In the process of each sharing data D_i, the consensus node generates a transaction block B_im based on the parameters {ID_m, K_m, S_m, R_m}, and appends B_im below the corresponding copyright block B_i to form a transaction chain {B_ij}_j=1,2,…,m, which makes sure that the transaction information of the same copyright data belongs to the same transaction chain. In order to further improve the query efficiency of traceability information, we let σ_h in the watermarked carrier as the query key key ← H_p (σ_h) to build an index on the copyright block, where . If someone checks the transaction, he can extract the signature σ_h in the carrier and quickly locate the copyright block through binary search to effectively obtain the copyright information and all transaction information in the corresponding transaction block.

Figure 4.

The cascade chain and its block structure.

If there is a suspected illegal copy on the market, the data owner can quickly query the corresponding copyright block B_i and all transaction blocks {B_ij}_j=1,2,…,n in the cascade chain with the keyword key ← H_p(σ_h) to collect the copyright information {ID_i,K_i,S_i,R_i,h,σ_h} and all transaction information {ID_ij,K_ij,S_ij,R_ij}_j=1,2,…,m. To track down a traitor, the owner utilizes the corresponding watermark extraction algorithm to obtain the signature information in the carrier through the watermark key K_ij, verifies the correctness of copyright information by Verify, and checks the consistency of the transaction by , where . If the above detects are passed, can be inferred as a potential data leaker.

5.1

Security

This part mainly analyzes the credibility and traceability about the traitor tracking model based on the security of the proposed chameleon short signature (see the appendix for the security analysis). The credibility considered in this model refers to the trustworthiness of both parties in the transaction, that is, the transaction initiator is the data purchaser himself and the seller is the data provider himself. The Traceability considered in this traitor tracing model refers to the undeniability of both parties in the transaction, that is, the purchaser cannot deny that he is the transaction initiator and the provider cannot deny that he is the transaction executor.

Property 1 (credibility): Let the ordinary signature submitted by the data purchaser be unforgeable, if the chameleon signature in the traitor tracing model is existential unforgeability, the data sharing approach is credible.

Proof: From Section 4.1, the data purchaser B initiates a transaction to the data provider A with his ordinary signature message S_b. Because of the ordinary signature is unforgeable, the data provider A can confirm whether the initiator is the purchaser himself by verifying the legality of S_b. When the data purchaser B receives the shared copy from provider, he can extract the chameleon signature σ_b in the carrier by his own watermark key K_b ← M_b = (ID_b, K_b, S_b) and verify the legality of (h, σ_b) to confirm that the shared data really comes from the data provider himself. Therefore, the sharing approach between the data purchaser and the provider is credible. (Property 1 is proved)

Property 2 (Traceability) Let the ordinary signature submitted by the data purchaser be unforgeable, if the chameleon hash is collision resistant and the chameleon signature is existential unforgeability, the data sharing approach is traceable.

Proof: It is known from Section 4.2 that if there is an illegal shared copy on the market, the data inspector can extract the chameleon signature through the purchaser’s watermark key K_b ← M_b. Since the ordinary signature S_b about (ID_b, K_b) is unforgeable, the purchaser cannot deny that the transaction was initiated by him. Because of the chameleon hash h w.r.t. M_b is collision resistant, the inspector can check the compatibility of (h, M_b, R_b) to prevent the purchaser from denying that the illegal copy comes from himself. Since the provider’s chameleon signature related to h is existential unforgeability, the provider cannot deny that the data carrier is authorized by himself. Thus, the data sharing approach between the data purchaser and the provider is traceable (Property 2 is proved).

5.2

Simulation

This experiment leverages 1 host (CPU is Intel Core i5 7500, memory is 8 GB, operating system is Windows 10) to simulate the big data platform and watermark center, and 4 hosts (CPU is Intel Core i3 2120, memory is 4 GB), operating system is Windows 7) to simulate the consensus node. We choose C++ as the main programming language to build the chameleon short signature algorithm, the watermarking algorithm and the PBFT consensus. Based on the above experimental environment, we take 20,000 rows and 50 columns of structured data as a carrier, and conduct multiple data sharing and tracing experiments.

In order to analyze the performance of the improved chameleon hash, we conduct experiments on the proposed scheme and the Khalili scheme with different sizes of data, and the time consumption is shown in Figure 5. From it, we can observe that the time consumption of the Hash and the Check is reduced by about 15ms, the Adapt is reduced by about 45ms. The reason is that the proposed algorithm reduces the mapping operation of the plaintext hash and the inverse operation of the group 𝔾, so the time comparison of each part is reduced except for the key generation KeyGen. Overall, there is a certain improvement in the performance of the proposed algorithm.

Figure 5.

Comparison of the chameleon hash.

Figure 6.

Consumption of the chameleon short signature.

We conducted 100 data sharing experiments on 5 published digital works to obtain the time cost of the chameleon short signature, and randomly selected 5 sharing instances of A, B, C, D and E from the 5 works for time analysis, which is shown in Fgure 6. It shows that the time consumption of the hash generation (Hash)and compatibility check (Check)about the proposed chameleon hash is approximately 35ms, the time cost of the adjustment to check parameter (Adapt) is approximately 75ms, and the time consumption of the signature (Sign)and verify (Verify) are maintained at 15ms and 25ms, respectively. On the whole, the execution time of the proposed chameleon short signature can well meet the practical requirements to achieve trusted sharing.

The traditional blockchain leverages a sequential chain to link blocks, while we use a cascade chain to connect blocks. In order to further compare and analyze the retrospective time cost of the two chain, we respectively conducted 100 data sharing on 5 digital work to ensure that 500 transaction blocks are recorded on the chain; then, each work randomly selects a leaked copy for tracing. For the same node, the consumption of leak detection in the two traceability chains is shown in Figure 7. What can be seen from the figure is that the detection efficiency of the cascade chain is about 3 times that of the traditional chain. The reason is that the cascaded chain only detects transaction blocks related to the original data, and does not compare all blocks, so the efficiency of leakage tracking is significantly better than that of the traditional chain.

Figure 7.

Consumption on leak detection.

In order to fully analyze the time consumption of the traitor tracking system, we embed the chameleon short signature into the digital carrier by the watermarking algorithm GAHSW¹⁹, and write the transaction information on the chain by the PBFT algorithm. Based on the above design, we randomly selected five shared instances of A, B, C, D and E for analysis. The overall performance is shown in Figure 8. The time consumption in data sharing includes embedded watermarks and consensus writing blocks, and the consumption in traitor tracing includes block reading and watermark detection. From the figure, we can see that the entire sharing and tracing time consumption is concentrated on the embedding and extraction of the watermark. Therefore, it is the key to improve the efficiency of the watermarking algorithm for improving the efficiency of traitor detection.

Figure 8.

Consumption on traitor tracing system.

Malicious users usually attack authorized copies with watermarks to varying degrees to obtain illegal copies that cannot be held accountable. For a single attacker, row deletion and column deletion are the easiest attacks, but for multiple attackers, collusion combinations, maximum, minimum and average attacks are the most common attacks. Among them, the attack of collusion combination refers to each conspirator taking out the same amount of different data to form an illegal copy; the attack of maximum (minimum, average) is to use the maximum (minimum, average) of the element at the corresponding position in all authorized copies as the element of the illegal copy.

In order to analyze the traceability of the traitor tracking model under different watermarking algorithms, we respectively embed the chameleon short signature into the digital carrier based on four robust watermarking algorithms such as GAHSW¹⁹, GADEW¹⁵, RLW¹¹, RRW¹⁴ and attack those carries to varying degrees. The detection effect is shown in Tables 2-4.

Table 2.

Detection effect on single traitor.

Table 2 shows the detection results of digital carriers under different watermarking algorithms and different degrees of deletion attacks in a single attacker scenario. From the table, we can get that for the scheme GAHSW, whether it is row deletion or column deletion, the tracking algorithm can correctly detect the signed message about owners and consumers as long as the attack degree it suffers does not exceed 50%; And for the scheme GADEW, as long as the attack degree does not exceed 40%, it can also correctly detect the signed message. In comparison, the GAHSW algorithm can deal with the deletion attack in a single traitor well.

If it is defined that the matching rate between the original signature and the extracted signature is η=(len_σ – dis_hc) / len_s, where len_σ is the length of the original signed message, and dis_hc is the distance of Hamming code between the original signed signature and the extracted. Under environment of the different colluders, the different attack strategy and the different watermarking algorithms, we let “○” means participating in collusion and “×” indicates not participating, then the matching rate under 2 colluders (A, B) and 3 colluders (A, B, C) is show in Tables 3 and 4, separately.

Table 3.

The matching rate of two colluders.

Table 4

The matching rate of three colluders.

It can be seen from Table 3 that all the watermarking algorithms can well detect out potential traitors in the case of 2 colluders. From Table 4, we can get that if 3 colluders conduct the attack of combined substitution on the digital carrier, all algorithms can also detect out potential traitors well. However, for maximum and minimum attacks, the algorithms GAHSW, GADEW, and RLW have relatively better anti-collusion attacks; for average attacks, the algorithms GAHSW and GADEW are more resistant to collusion; On the whole, the efficiency of identifying colluders is GADEW > GAHSW > RLW > RRW, but the scheme GADEW modifies the original carrier to a greater extent and makes the data availability relatively low, so the GAHSW algorithm is more suitable for detecting data leakers in the traitor tracking model.