Bilinear pairings and security problems

In this section, we describe bilinear maps and hard problems [38]. Let consider two cyclic groups $$ \mathbb{G}$$ and $$ {\mathbb{G}}_T$$ with the same prime order q, and let g is a generator of $$ \mathbb{G}$$. A bilinear map $$ \widehat{e}:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$$ need satisfy the following properties:

Bilinearity: For all $$ g,h\in \mathbb{G}$$, and $$ a,b\in {\mathbb{Z}}_q$$, $$ \widehat{e}(g^a,h^b)=\widehat{e}{(g,h)}^{ab}$$.

Non-degeneracy: There exists $$ a,b\in {\mathbb{Z}}_q$$, such that $$ \widehat{e}(g^a,g^b)\ne 1$$.

Computability: For all $$ g,h\in \mathbb{G}$$, $$ \widehat{e}(g,h)$$ can be computed.

Definition 1. The Decision Linear (DLLN) Problem is to decide whether a + b = c, given $$ u,v,h,u^a,v^b,h^c\in \mathbb{G}$$ for unknown $$ a,b,c\in {\mathbb{Z}}_q$$. The DLLN assumption states that, there is no PPT algorithm can solve the DLLN problem with non-negligible advantage.

Definition 2. The Computational Diffie-Hellman (CDH) Problem is that, given $$ g,g^x,g^y\in \mathbb{G}$$ for unknown $$ x,y\in {\mathbb{Z}}_q$$, it is hard to compute g^xy. The CDH assumption states that, there is no PPT algorithm can solve the CDH problem with non-negligible advantage.

Circuit obfuscators

In this section, we briefly review some notations of circuit obfuscators used in this paper [32]. We use $$ \mathbb{C}={\left\{C_{\lambda }\right\}}_{\lambda \in \mathbb{N}}$$ to denote a class of probabilistic circles, here C_λ is the circuits in $$ \mathbb{C}$$ of input length l_in(λ). the notation C ← C_λ denotes the generation procedure. PPT denotes probability polynomial time. Obf denotes an obfuscator. poly(λ) indicates the set of all polynomials of λ. We now provide definitions of statistical difference and preserving functionality.

Definition 3. [32] The statistical difference between C₀(x) and C₁(x) is given by:

Definition 4. (Preserving Functionality) [32] A PPT machine Obf is a circuit obfuscator for a class of probabilistic circuits $$ \mathbb{C}={\left\{C_{\lambda }\right\}}_{\lambda \in \mathbb{N}}$$, if for every probabilistic circuit C ∈ C_λ, the following holds:

TS signature

The TS signature scheme is a tuple of algorithms ∏ = (Setup, Share-Sign, Share-Verify, Combine, Verify) such that:

Setup(params, λ, k, n): Takes as input a security parameter $$ \lambda \in \mathbb{N}$$ and a pair of integers (k, n) ∈ poly(λ), such that 1 ≤ k ≤ n, let $$ P=\{P_1,P_2,\dots ,P_n\}$$ denote a set of n participants (users).

Choose system parameter $$ params=(\mathbb{G},{\mathbb{G}}_T,\widehat{e},g,q)$$.

$$ g_2,u^{\prime },\mathbf{U}=(u_1,u_2,\cdots ,u_n)\in {\mathbb{G}}^{n+2}$$ are also generated by using GJKR’s DKG algorithm [22], respectively.

To generate public key, n users jointly generate user public key g₁ = g^α by using GJKR’s DKG.

Each user P_i broadcasts g^f(i) for a random jointly generated degree k − 1 polynomial $$ f\in {\mathbb{Z}}_q\left[X\right]$$ such that α = f(0).

User P_i gets the private key shares SK = (sk₁, sk₂, ⋯, sk_n) as $$ s{k}_i=g_2^{f\left(i\right)}$$ for i = 1 to n. Verification keys VK = (vk₁, vk₂, ⋯, vk_n) as vk_i = g^f(i) for i = 1 to n.

Output the public key p = (VK, params, g₁, g₂, u′, U), and each user is supplied with the private key share sk_i.

Share-Sign(sk_i, m): To sign m = m₁ m₂ ⋯ m_n ∈ {0, 1}ⁿ, using sk_i, choose $$ r_i\in {\mathbb{Z}}_q$$, compute the signature share $$ {\sigma }_i=({\sigma }_{i1},{\sigma }_{i2})=(s{k}_i{\left(u^{\prime }{\displaystyle \prod _{i=1}^n}{u}_i^{m_i}\right)}^{r_i},g^{r_i}).$$

Share-Verify(p, m, i, σ_i): Given a signature share σ_i, and the verification key vk_i, the partial verification algorithm return 1 if $$ \widehat{e}({\sigma }_{i1},g)=e(g_2,v{k}_i)\widehat{e}(u^{\prime }{\displaystyle \prod _{i=1}^n}{u}_i^{m_i},{\sigma }_{i2})$$, else return 0.

Combine(p, m, i, σ_i)_i∈Φ: For each i ∈ Φ, where a subset Φ ⊂ {1, 2, ⋯, n} and |Φ| = k. Let λ_i be the Lagrange coefficients so that $$ \alpha =f\left(0\right)={\displaystyle \sum _{i\in \Phi }}{\lambda }_{i}f\left(i\right),$$ compute the combined signature $$ (\overline{{\sigma }_1},\overline{{\sigma }_2})=({\displaystyle \prod _{i\in \Phi }}{\sigma }_{i1}^{{\lambda }_i},{\displaystyle \prod _{i\in \Phi }}{\sigma }_{i2}^{{\lambda }_i}).$$

Verify $$ (p,m,\overline{{\sigma }_1},\overline{{\sigma }_2}):$$ Given signature $$ (\overline{{\sigma }_1},\overline{{\sigma }_2})$$, the receiver checks the equation $$ \widehat{e}(\overline{{\sigma }_1},g)=\widehat{e}(g_2,g_1)\widehat{e}(u^{\prime }{\displaystyle \prod _{i=1}^n}{u}_i^{m_i},\overline{{\sigma }_2}).$$ If the equation holds, outputs 1, otherwise outputs 0.

Linear encryption scheme

The linear encryption scheme consists of three algorithms ∑ = (Key generation algorithm(KG), Encrypt algorithm(Enc), Decrypt algorithm(Dec)), the algorithms are described as follows:

KG(params): Parse system parameter $$ params=(\mathbb{G},{\mathbb{G}}_T,\widehat{e},g,q)$$, choose $$ a,b\in {\mathbb{Z}}_q$$ as the private key sk_e, compute the encryption public key pk_e = (pk_e1, pk_e2) = (g^a, g^b).

Enc(m, pk_e): To encrypt message m, randomly choose $$ r,s\in {\mathbb{Z}}_q$$, compute



Dec(τ, sk_e): Given τ and sk_e, compute $$ m=\frac{{\tau }_3}{{\tau }_1^{\frac{1}{a}}{\tau }_2^{\frac{1}{b}}}$$.

Specifically, we denote the rerandomization algorithm by ReRand(p, pk_e, (τ₁, τ₂, τ₃)), which produces a new ciphertext $$ ({\tau }_1{\left(g^a\right)}^{r^{\prime }},{\tau }_2{\left(g^b\right)}^{s^{\prime }},{\tau }_3{g}^{r^{\prime }+s^{\prime }})$$, equivalent to the input ciphertext τ, under the public key pk_e = (g^a, g^b), using the additional random numbers r′ and s′.

The ETS functionality

ETS functionality is composed of ETS.Setup, ETS.Sign, ETS.Verify. We give the concrete construction as follows:

ETS.Setup(params, λ, k, n):

Parse parameter $$ params=(\mathbb{G},{\mathbb{G}}_T,\widehat{e},g,q)$$.

For users(participants), generate public keys and private shares by running (VK, params, g₁, g₂, u′, U, SK)← Setup(params, λ, k, n).

For receiver(verifier), randomly choose $$ a,b\in {\mathbb{Z}}_q$$ as the receiver’s private key sk_e, compute receiver’s public key pk_e = (pk_e1, pk_e2) = (g^a, g^b).

ETS.Sign(SK, m, p, pk_e): For m = m₁ m₂⋯m_n ∈ {0, 1}ⁿ, works as follows:

Randomly choose $$ r_j\in {\mathbb{Z}}_q$$, and compute σ_j←Share-Sign(sk_j, m), that is



Verify the validity of signature σ_j by



Compute the combined signature $$ (\overline{{\sigma }_1},\overline{{\sigma }_2})$$ ← Combine(p, m, j, σ_j)_j∈Φ, that is


for each j ∈ Φ, where a subset Φ ⊂ {1, 2, ⋯, n} and |Φ| = k. Let λ_j be the Lagrange coefficients so that $$ \alpha =f\left(0\right)={\displaystyle \sum _{j\in \Phi }}{\lambda }_{j}f\left(j\right).$$

Randomly choose $$ x_1,x_2,y_1,y_2\in {\mathbb{Z}}_q$$, encrypt $$ (\overline{{\sigma }_1},\overline{{\sigma }_2})$$ under the receiver’s public key S₁← Enc $$ (p{k}_e,\overline{{\sigma }_1})$$ and S₂← Enc $$ (p{k}_e,\overline{{\sigma }_2}),$$ that is




Output encrypted threshold siganture (S₁, S₂).

ETS.Verify(p, sk_e, S₁, S₂, m): Parse p = (VK, params, g₁, g₂, u′, U), and m = m₁ m₂⋯m_n ∈ {0, 1}ⁿ. Decrypt (S₁, S₂) to get $$ (\overline{{\sigma }_1},\overline{{\sigma }_2})$$, that is


and

then verify the encrypted signature by $$ \widehat{e}(\overline{{\sigma }_1},g)=\widehat{e}(g_2,g_1)\widehat{e}(u^{\prime }{\displaystyle \prod _{i=1}^n}{u}_i^{m_i},\overline{{\sigma }_2}),$$ else return 0.

The obfuscation of ETS functionality

From the description of the ETS functionality in above section, we regard a family of circuits $$ C_{ETS}={\left\{C_{\lambda }\right\}}_{\lambda \in \mathbb{N}}$$ for the ETS functionality, C_λ is a group of circuits $$ C_{p,\mathbf{\text{SK}},p{k}_e}$$. We can draw system parameters (SK, pk_e, p) from $$ C_{p,\mathbf{\text{SK}},p{k}_e}$$. Given a circuit $$ C_{p,\mathbf{\text{SK}},p{k}_e}$$, the Obf_ETS works as follows:

Obf $$ {}_{\text{ETS}}\left(C_{p,\mathbf{\text{SK}},p{k}_e}\right):$$

Extract system parameters (pk_e, SK, p).

Parse parameter $$ params=(\mathbb{G},{\mathbb{G}}_T,\widehat{e},g,q)$$, SK = (sk₁, sk₂, ⋯, sk_n) and VK = (vk₁, vk₂, ⋯, vk_n).

For each j ∈ {1, 2, ⋯, n}, randomly choose $$ x_{j1},x_{j2}\in {\mathbb{Z}}_q$$, encrypt user’s private share sk_j to run $$ (p{k}_{e1}^{x_{j1}},p{k}_{e2}^{x_{j2}},s{k}_j^{\prime })\leftarrow \text{Enc}(p{k}_e,s{k}_j)$$, $$ s{k}_j^{\prime }=g^{x_{j1}+x_{j2}}s{k}_j$$ is an encrypted form of the original signing key sk_j, then compute $$ v{k}_j^{\prime }=g^{x_{j1}+x_{j2}}v{k}_j$$. Suppose $$ t=(c_{j1},c_{j2},c_{j3})=(p{k}_{e1}^{x_{j1}},p{k}_{e2}^{x_{j2}},s{k}_j^{\prime })$$.

Construct an obfuscated circles R_p,pke,t that contains the values $$ (p,p{k}_e,v{k}_j^{\prime },t).$$

R_p,pke,t: The obfuscated circuit can be executed on any untrusted cloud server, and it does the following.

On input security parameter λ, the circuit outputs (pk_e, p).

On input message m = m₁ m₂⋯m_n ∈ {0, 1}ⁿ, randomly choose $$ r_j^{\prime }\in {\mathbb{Z}}_q$$ to run $$ {\sigma }_j^{\prime }=({\sigma }_{j1}^{\prime },{\sigma }_{j2}^{\prime })$$ ← Share-Sign $$ (s{k}_j^{\prime },m)$$, that is


and


Verify the validity of signature $$ {\sigma }_j^{\prime }$$ by



Compute the combined signature $$ (\overline{{\sigma }_1^{\prime }},\overline{{\sigma }_2^{\prime }})$$ ← Combine $$ {(p,m,{\sigma }_j^{\prime })}_{j\in \Phi },$$ that is


for each j ∈ Φ, where a subset Φ ⊂ {1, 2, ⋯, n} and |Φ| = k. Let $$ {\lambda }_j^{\prime }$$ be the Lagrange coefficients so that $$ \alpha =f\left(0\right)={\displaystyle \sum _{j\in \Phi }}{\lambda }_j^{\prime }f\left(j\right).$$

Compute $$ c_1={\displaystyle \prod _{j\in \Phi }}{\left(c_{j1}\right)}^{{\lambda }_j^{\prime }}=p{k}_{e1}^{\sum _{j\in \Phi }{\lambda }_j^{\prime }{x}_{j1}},$$ and $$ c_2={\displaystyle \prod _{j\in \Phi }}{\left(c_{j2}\right)}^{{\lambda }_j^{\prime }}=p{k}_{e2}^{\sum _{j\in \Phi }{\lambda }_j^{\prime }{x}_{j2}}.$$

Randomly choose $$ x_1^{\prime },x_2^{\prime },y_1^{\prime },y_2^{\prime }\in {\mathbb{Z}}_q$$, rerandomize the generated signature $$ {\overline{{\sigma }_1}}^{\prime }$$ by running $$ S_1^{*}$$ ← ReRand $$ (p,p{k}_e,(c_1,c_2,{\overline{{\sigma }_1}}^{\prime })),$$ that is


and run $$ S_2^{*}$$ ← Enc $$ (p{k}_e,{\overline{{\sigma }_2}}^{\prime }),$$ that is


Output $$ (S_1^{*},S_2^{*}$$).

Besides, the polynomial time property is evident as all the calculation here is valid in polynomial time. It is easily to verify that the obfuscated program by theorem 1.

Theorem 1. The algorithm R_p,pke,t can pass verification.

Proof 1. For a valid ciphertext $$ (S_1^{*},S_2^{*})$$, receiver decrypts $$ (S_1^{*},S_2^{*})$$, the correctness of R_p,pke,t is elaborated as follows:

The following equation shows that R_p,pke,t satisfies correctness:

Correctness

In this section, we identify the following goals that the obfuscator for ETS should satisfy.

Correctness: The correctness of an obfuscator requires “Preserving Functionality” as described in Definition 4.

Security: The obfuscator needs satisfy ACVBP with respect to T(C) and R(C) and existentially unforgeable with respect to ETS Obfuscator.

Below, we state the Theorem 2 which is a key result used to show the correctness of our construction.

Theorem 2. (Preserving Functionality) The obfuscated program preserves the functionality of original ETS.

Proof 2. On receiving the encrypted threshold signature (S₁, S₂), that is

On receiving the obfuscated program $$ (S_1^{*},S_2^{*}),$$ that is

We observe that both (S₁, S₂) and $$ (S_1^{*},S_2^{*})$$ are identically distributed.

Security proof

Theorem 3. Under the DLLN assumption, the algorithm Obf_ETS is ACVBP with respect to dependent oracle $$ T\left(C\right)=Share-Sig{n}_{p,s{k}_i}$$ and restricted dependent oracle R(C) = Corruption^{∣Φ∣≤k−1}.

Proof 3. Suppose $$ C=C_{p,\mathbf{\text{SK}},p{k}_e}$$, $$ T\left(C\right)=Share-Sig{n}_{p,s{k}_i}$$ and R(C) = Corruption^{∣Φ∣≤k−1}. There are a pair of probabilities (Pr_Nick, Pr_Junk) that represent D^{≪C,T(C),D(C)≫} outputs 1, given the true and imitated distributions, respectively. We show that S K = (sk₁, sk₂, ⋯, sk_n) and $$ \overline{\mathbf{\text{Junk}}}=(Jun{k}_1,Jun{k}_2,\cdots ,Jun{k}_n)$$ are encrypted in the true and imitated distributions. Since the algorithm Obf_ETS is equivalent to the values $$ (p,p{k}_e,v{k}_i^{\prime },t)$$. So we can utilize a simulator S which imitates these values with sampling access to C. The values (p, pk_e) can be easily draw from C. In order to simulate $$ (t,v{k}_i^{\prime })$$. Then S chooses n junk values and encrypts them using the receiver’s public encryption key pk_e.

The detailed procedure of S is as below.

Using the sampling access to $$ C_{p,\mathbf{\text{SK}},p{k}_e}$$ to get (p, pk_e).

Parse p = (V K, params, g₁, g₂, u′, U), V K = (vk₁, vk₂, ⋯, vk_n) and $$ params=(\mathbb{G},{\mathbb{G}}_T,\widehat{e},g,q)$$.

Randomly choose $$ Jun{k}_1,Jun{k}_2,\cdots ,Jun{k}_n\in \mathbb{G}$$, and $$ \overline{x_{i1}},\overline{x_{i2}}\in {\mathbb{Z}}_q$$.

Encrypt Junk_i using public key pk_e, $$ (c_{i1},c_{i2},c_{i3})=(p{k}_{e1}^{\overline{x_{i1}}},p{k}_{e2}^{\overline{x_{i2}}},g^{\overline{x_{i1}}+\overline{x_{i2}}}Jun{k}_i)$$ for i = 1 to n.

Compute $$ \overline{v{k}_i}=g^{\overline{x_{i1}}+\overline{x_{i2}}}v{k}_i$$ for i = 1 to n.

Set Junk = (c_i1, c_i2, c_i3), where i = 1, 2, ⋯, n.

Output $$ (p,p{k}_e,\overline{v{k}_i},Junk)$$, obviously, $$ R_{p,p{k}_e,Junk}$$ has the same distribution as $$ R_{p,p{k}_e,t}$$.

We will first prove that the output distributions of the simulator and the obfuscator are indistinguishable. We prove this by contradiction, assume that the probability that a distinguisher D^{≪C,T(C),D(C)≫} can distinguish between the probabilities described is not negligible. That is, |Pr_Nick − Pr_Junk| is not negligible.

Assume that the probability of D to win is not negligible, then we build a couple of adversaries (A, B), which attacks the semantic security of the encryption algorithm. First, A does as below:

Take as input (params, pk_e, p, z).

Parse $$ params=(\mathbb{G},{\mathbb{G}}_T,\widehat{e},g,q)$$.

Generate the signers’ private key shares S K.

Parse S K = (sk₁, sk₂, ⋯, sk_n).

Randomly choose $$ Jun{k}_1,Jun{k}_2,\cdots ,Jun{k}_n\in \mathbb{G}$$.

Set m₁ = sk_i and m₂ = Junk_i.

Output (m₁, m₂, pk_e).

Given an encryption ciphertext ct of m_i, the algorithm B can make a distinction between m₁ and m₂ by utilizing D.

Take as input (p, pk_e, m₁, m₂, ct, z).

Parse $$ params=(\mathbb{G},{\mathbb{G}}_T,\widehat{e},g,q)$$ and ct.

Simulate $$ D^{⪡C,T\left(C\right),D\left(C\right)\gg }(p,p{k}_e,s{k}_i^{\prime },c_{i1},c_{i2},z)$$.

Output D’s output.

The advantage of attacker B is the same as the advantage of the distinguisher D to distinguish the output distributions of obfuscator and simulator. So if it’s not negligible, then it contradicts the DLLN assumption. Thus the advantage of D is negligible when given one tuple of ciphertexts, then the advantage when given three tuples is also negligible. So we conclude that the obfuscator satisfies ACVBP with dependent oracle set T(C) and restricted oracle setR(C).

Theorem 4. If Obf_ETS for ETS functionality is ACVBP w.r.t. dependent oracle $$ T\left(C\right)=Share-Sig{n}_{p,s{k}_i}$$ and restricted dependent oracle R(C) = Corruption^{∣Φ∣≤k−1}, then the existentially unforgeable w.r.t. ETS functionality implies the existentially unforgeable w.r.t. ETS obfuscator.

Proof 4. The proof of this theorem is very similar to the proof in [32], see [103, Theorem 1], we thus omit the formal proof here.

From Theorem 3 and Theorem 4, the TS scheme satisfies the existentially unforgeable, even if the adversary can obtain the obfuscated circuit. The obfuscator for ETS is mainly to enhance the security, and it is safe for the obfuscation circuit to be executed by any untrusted cloud server, and the cloud server could not get any useful information from it.

Corollary 1. Under DLLN and CDH assumptions, TS scheme is existentially unforgeable w.r.t. Obf_ETS.

Theoretical performance analysis

Here we analyze the performance efficiency of our scheme, in terms of computational complexity when performing ETS.Sign, Obf_ETS, R_p,pke,t and ETS.Verify operations. The result is showed in Table 1. In this table, Rand denotes the operation that randomly selects element, Add denotes addition, Mult denotes multiplication, Exp be an exponent operation, Inv denotes inverse operation. As shown in Table 1, the computational complexity of ETS.Sign and R_p,pke,t algorithms is linear in the number of n and k. All these operations are polynomial bounded operations and can be computed effectively. Therefore, all algorithms are efficient from a theoretical perspective.

Table 1

Computational overhead, where n is the number of users, k is the threshold number.

	Operation	ETS.Sign	ObfETS	Rp,pke,t	ETS.Verify
$$	Rand	n + 4	2n	n + 4	0
	Add	2	n	2k	0
	Inv	0	0	0	4
$$	Mult	2k + n + 1	2n	4k + n + 1	0
	Exp	2k + 2n + 6	3n	4k + 2n + 6	4
	Inv	0	0	0	2
$$	Mult	1	0	1	1
$$	Pair	3	0	3	3

Implementation

To provide numerical results, we implement it to measure the performance of our scheme. Our implementation is written in C using the Pairing-Based Cryptography Library [40]. For the computations, we use the curve groups that are implemented in the Libpbc library. The computations are run on a PC with 3.70 GHz CPU frequency, and 4 GB of RAM. In the experiment, we use elliptical curves with a base field size of 512 bits and an embedding degree of 2. The security levels are selects as |p| = 512.

The following results denote the average running times of related cryptographic operations. In the experiment, the experimental result is the average number of 10 runs. We measure the running time of four algoritms, that is: ETS.Sign, Obf_ETS, R_p,pke,t and ETS.Verify. The performing consequence of our scheme is provided in Fig 1 when n = 5 and k = 3. It is shown that the obfuscated implementation have high efficiency in general, because the algorithm needs perform more exponent operation.

Fig 1

Execution time of the algorithms.

Figs 2 and 3 show the time variety when the number of n and k as variables, respectively. Fig 2 shows the operations time of ETS.Sign, Obf_ETS and R_p,pke,t when k is set as 3 and the number of n is set varies from 5 to 9 increased by an interval of 1. Fig 3 shows the execution time of the three algorithms when n is set as 7 and the number of k is set varies from 3 to 7 increased by an interval of 1. We observe that R_p,pke,t, ETS.Sign and Obf_ETS’s time cost increases fastly along with the increasing of n and k. It can be seen from the results that R_p,pke,t is more costly than ETS.Sign with the same n or k.

Fig 2

Time cost with k = 3.

Fig 3

Time cost with n = 7.