Noncommutative Lightweight Signcryption for Wireless Sensor Networks

Abstract

Key management techniques for secure wireless-sensor-networks-based applications must minimally incorporate confidentiality, authenticity, integrity, scalability, and flexibility. Signcryption is the proper primitive to do this. However, existing signcryption schemes are heavyweight and not suitable for resource-limited sensors. In this paper, we at first propose a braid-based signcryption scheme and then develop a key establishment protocol for wireless sensor networks. From the complexity view, our proposal is 2¹⁵ times faster than RSA-based ones. As far as we know, our proposal is the first signcryption scheme based on noncommutative algebraic structures.

1. Introduction

Wireless sensor networks (WSNs) consist of a large number of micro, low-cost, low-power, and spatially distributed autonomous devices using sensors to cooperatively monitor physical or environmental conditions [1, 2]. WSNs are often deployed in potentially adverse or even hostile environment so that there are concerns on security issues therein. To protect the confidentiality and privacy of WSN-oriented applications, the traditional symmetric (i.e., private-key), even lightweight, cryptography is often used. A well-known drawback to do this is that the symmetric cryptography is not as flexible as the asymmetric (i.e., public-key) cryptography. The main obstacle of using public-key cryptography in WSNs is that with limited memory, computing and communication capacity, and power supply, sensor nodes cannot employ sophisticated cryptographic operations such as modular exponentiation and pairing computation. Therefore, it is interesting to probe new efficient and lightweight implementations on some wellknown public-key cryptographic primitives, such as what has been done in TinyECC [3] and in MicroECC [4]. No matter which type cryptography is adopted, key establishment is one of the utmost concerns. At least, key establishment techniques for a secure WSN-based application must minimally incorporate confidentiality, authenticity, integrity, scalability, and flexibility [5].

Signcryption, now an international standard for data protection (ISO/IEC 29150, Dec 2011), was invented in 1996 and first disclosed to the public at CRYPTO 1997 [6, 7]. It is a data security technology by which confidentiality is protected and authenticity is achieved seamlessly at the same time. This will also allow smaller devices, such as smartphones and PDAs, 3G and 4G mobile communications, as well as emerging technologies, such as radio frequency identifiers (RFIDs) and wireless sensor networks, to perform high-level security functions. And, by performing these two functions simultaneously, we can save resources, be it an individual's time or be it energy, as it will take less time to perform the task. Therefore, signcryption is very suitable for key management in wireless sensor networks and other resource-constrained environments.

Since the invention of the primitive of signcryption, various constructions were proposed and most of them are based on three kinds of cryptographic assumptions. The first category assumes that the integer factoring problem (IFP) is intractable, such as the constructions in [8, 9]. The second category assumes that the discrete logarithm problem (DLP) over finite fields or elliptic curves (i.e., ECDLP) is intractable, such as the constructions in [10, 11]. In this category, some constructions further utilize the bilinear pairing to enhance the functionalities and performance, such as the constructions in [12, 13]. The third category is based on some lattice hard problems [14, 15]. Up to now, the last category attracts a lot of attention since the so-called quantum attack-resistant property. However, these existing lattice-based signcryptions have disadvantage in key sizes. Thus, it is interesting to probe new construction of signcryption based on other cryptographic primitives than IFP- and DLP-related ones and meanwhile keeping the potential of quantum attack resistance.

Under this background, some noncommutative groups have attracted the attention. One of the most popular groups in this category is the braid group. At CRYPTO 2000, Ko et al. [16] proposed the first fully fledged braid-based cryptosystem. In braid-based cryptographic schemes [16–24], the conjugacy search problem (CSP) (i.e., given two braids a and $xa{x}^{-\mathrm{1}}$ , output the braid x) and its variants play a core role. Although many heuristic attacks, such as length-based attacks linear representation attacks, have obtained remarkable success in attacking braid-based cryptosystems and lowered the initial enthusiasm on this subject, there is no deterministic polynomial algorithms that can solve the CSP problem over braid groups [25] till now. On one hand, Birman et al. launched a project, referred to as BGGM project, to find polynomial algorithms for solving the CSP problem over Garside groups, including braid groups [26–28]. The BGGM project might be the strongest efforts known for solving the CSP problem over braid groups in polynomial-time (with respect to the input size). Up to now, the BGGM project has already made a great progress; except for rigid pseudo-Anosolov braids, the CSP instances over other braids can be solved in polynomial time [28]. On the other hand, some researchers still keep on finding hard instances of the CSP problem in braid groups. For examples, in 2007, Ko et al. [29] proposed some ideas on generating hard instances for braid cryptography, and in 2010, Prasolov [30] constructed some small braids with large ultra summit set (USS). Prasolov's result represents a frustration toward the BGGM project, but an encouragement toward the intractability assumption of the CSP problem over braid groups. According to [31], if p and s are random braids, then the length of $sp{s}^{-\mathrm{1}}$ is, with a high probability, about the length of p plus the double of the length of s. This is the reason why the length-based attacks work. This also suggests that one can defeat the length-based attacks by requiring that the length of $sp{s}^{-\mathrm{1}}$ is closer to the length of p. This in turn requires that p should lie in its super summit set (SSS) [31]. We know that $\text{USS}\subset \text{SSS}$ . Therefore, if we can work with the braids suggested by Prasolov, then we reach the point to instantiate our proposal with braid groups in a secure manner.

Another promising observation coming from [23] is that braid operations can be implemented with a complexity level of about ${\mathrm{2}}^{\mathrm{15}}$ bit operations, while the complexity level of the exponentiation over 1024 bit RSA modular is about ${\mathrm{2}}^{\mathrm{30}}$ bit operations. This suggests that braid-based cryptosystems admit ultra efficient, even lightweight, implementations.

The main motivation of this paper covers two aspects: the first is to design a lightweight signcryption scheme based on noncommutative groups assuming that the CSP problem over the underlying groups are intractable, and the second is to construct efficient key management protocols for wireless sensor networks.

The rest contents are organized as follows. In Section 2, we at first give a simple introduction to the braid group, and then introduce the left self-distributive system and its properties. A building block—braid-based signcryption scheme is proposed in Section 3, and the full description of the key management protocol for wireless sensor networks is developed in Section 4. Performance evaluation and comparisons, including security level analysis, are given in Section 5, respectively. Concluding remarks are given in Section 6.

2. Preliminaries

2.1. Braid Group and Related Cryptographic Problems

The n-braid group $B_n$ is presented by the Artin generators ${\sigma }_{\mathrm{1}},\dots ,{\sigma }_{n-\mathrm{1}}$ and relations ${\sigma }_i\hspace{0.17em}{\sigma }_j={\sigma }_j\hspace{0.17em}{\sigma }_i$ for $|i-j|>\mathrm{1}$ and ${\sigma }_i\hspace{0.17em}{\sigma }_j\hspace{0.17em}{\sigma }_i={\sigma }_j\hspace{0.17em}{\sigma }_i\hspace{0.17em}{\sigma }_j$ for $|i-j|=\mathrm{1}$ ( $\mathrm{1}\le i,\hspace{0.17em}j\le n-\mathrm{1}$ ). Braid groups also admit a very intuitively geometrical illustration: the identity of braid groups, that is, the empty braid e, and the Artin generators (e.g., ${\sigma }_{\mathrm{2}}^{\pm \mathrm{1}}$ in $B_{\mathrm{4}}$ ) as shown in Figure 1 [23].

Figure 1

Geometrical illustration on identity and Artins generators [23].

Geometrically, the product of two braids is the braid obtained by merging the tail of the first braid with the head of the second braid. For example, Figure 2 shows the braid ${\sigma }_{\mathrm{1}}{\sigma }_{\mathrm{2}}{\sigma }_{\mathrm{1}}^{-\mathrm{1}}{\sigma }_{\mathrm{3}}^{-\mathrm{1}}{\sigma }_{\mathrm{2}}{\sigma }_{\mathrm{3}}{\sigma }_{\mathrm{2}}{\sigma }_{\mathrm{3}}^{-\mathrm{1}}{\sigma }_{\mathrm{2}}^{-\mathrm{1}}{\sigma }_{\mathrm{1}}$ [23].

Figure 2

An example of geometric braids [23].

There is a natural automorphism from $B_{\mathrm{2}}$ to the integer additive group ℤ and this means that $B_{\mathrm{2}}$ is infinite and commutative. But for $n\ge \mathrm{3}$ , the braid group $B_n$ is infinite and noncommutative. In addition, for each $m\hspace{0.17em}\hspace{0.17em}(\le n)$ , the identity mapping on $\{{\sigma }_{\mathrm{1}},\dots ,{\sigma }_{m-\mathrm{1}}\}$ naturally induces an embedding of $B_m$ into $B_n$ [23].

For arbitrary two braids $x,y\in B_n$ , we say they are conjugate, written as $x~y$ , if $y=a^{-\mathrm{1}}xa$ for some $a\in B_n$ . Here a or $a^{-\mathrm{1}}$ is called a conjugator. The conjugacy deciding problem (CDP) is to determine whether $x~y$ for a given instance $(x,y)\in B_n^{\mathrm{2}}$ , while the conjugator searching problem (CSP) is to find a braid $z\in B_n$ such that $y=z^{-\mathrm{1}}xz$ for a given instance $(x,y)\in B_n^{\mathrm{2}}$ with $x~y$ . At present, we know that both CDP and CSP over braid groups are solvable; that is, there is a deterministic algorithm that stops after finite steps, not necessarily polynomially bounded, and outputs an accurate solution. However, it seems that both of them are, at least in worst cases, intractable; that is, there is no probabilistic polynomial time algorithms that output an accurate solution with nonnegligible probability (with respect to the length of description of the input instances) [20, 21, 23].

In sequel, we use $x^a$ to denote the conjugate braid $a^{-\mathrm{1}}xa$ when $a\in B_n$ . Meanwhile, we also use $x^t$ to denote the multiplication braid $\underset{t\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{times}}{\underbrace{x\cdots x}}$ when $t\in \mathbb{N}$ .

2.2. Conjugacy-Based Left Self-Distributive Systems

Under the intractability assumption of the conjugator search problems over certain noncommutative semigroups, Wang et al. [24] proposed several public-key cryptosystems based on conjugacy-based left self-distributive systems. The notations and related constructions are helpful for developing our main proposal in this paper. Therefore, let us recall the definition of the left self-distributive system that was firstly postulated by Dehornoy [32].

Definition 1 (left self-distributive system LD [32]).

Suppose that S is a nonempty set, $F:S\times S\to S$ is a well-defined function and let us denote $F(a,b)$ by $F_a(b)$ . If the following rewritten formula holds

$$\begin{array}{cc}& F_r\left(F_s\left(p\right)\right)=F_{F_r\left(s\right)}\left(F_r\left(p\right)\right),\hspace{1em}\left(\forall p,r,s\in S\right),\end{array}$$

(1)

then, we call $F_{·}(·)$ a left self-distributive system, abbreviated as LD system.

The terminology “left self-distributive” arises from the following analogical observation: if we consider $F_r(s)$ as a binary operation $r*s$ , then the formula (1) becomes

$$\begin{array}{cc}& r*\left(s*p\right)=\left(r*s\right)*\left(r*p\right);\end{array}$$

(2)

that is, the operation “*” is left self-distributive with respect to itself [32].

One can define the following LD system, named as Conj-LD system, which means an abbreviation of left self-distributive system defined by conjugate operations.

Definition 2 (Conj-LD system [24]).

Let G be a noncommutative semigroup and $G^{-\mathrm{1}}\subset G$ the set of all invertible elements. The binary function F given by the following conjugate operation:

$$\begin{array}{cc}& F:G^{-\mathrm{1}}\times G\to G,\hspace{1em}\hspace{1em}\left(a,b\right)\mapsto a^{-\mathrm{1}}ba\triangleq b^a\end{array}$$

(3)

is an LD system, abbreviated as Conj-LD.

It is easy to see that F caters to the rewritten formula (1). Thus, $F_a(b)$ is an LD system [24].

Proposition 3 (power law [24]).

Let F be a Conj-LD system defined over a noncommutative semigroup G. Suppose that $a\in G^{-\mathrm{1}}\subset G$ and $b\in G$ are given and fixed. Then, for arbitrary three positive integers m, s, and t such that $m=s+t$ , one has

$$\begin{array}{cc}& F_a\left(b^m\right)=F_a\left(b^s\right)F_a\left(b^t\right)=F_a^m\left(b\right),\\ F_{a^m}\left(b\right)=F_{a^s}\left(F_{a^t}\left(b\right)\right).\end{array}$$

(4)

Remark 4.

By using the notation of $F_{·}(·)$ , the intractability assumption of the CSP problem in G can be reformulated as follows: it is hard to retrieve $a^{\prime }$ from the given pair $(a,F_a(b))$ such that $F_a(b)=F_{a^{\prime }}(b)$ (see more details in [24]).

Definition 5 (CSP-based decisional Diffie-Hellman: CSP-DDH [24]).

Let F be a Conj-LD system defined over a noncommutative semigroup G and let 𝒜 be an adversary. For arbitrary $a\in G^{-\mathrm{1}}$ and $b\in G$ , consider the following two experiments in a paralleled manner (see Table 1). Now define the advantage of 𝒜 in violating the CSP-based decisional Diffie-Hellman assumption as

$$\begin{array}{l}\mathbf{A}\mathbf{d}{\mathbf{v}}_{F,𝒜}^{\text{csp-ddh}}=|\text{Pr}\left[\mathbf{E}\mathbf{x}{\mathbf{p}}_{F,𝒜}^{\text{csp-ddh-real}}=\mathrm{1}\right]\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.5em}\phantom{a}-\hspace{0.17em}\text{Pr}\left[\mathbf{E}\mathbf{x}{\mathbf{p}}_{F,𝒜}^{\text{csp-ddh-rand}}=\mathrm{1}\right]|.\end{array}$$

(5)

Table 1

Experiments for define CSP-DDH problem.

Experiment $\mathbf{E}\mathbf{x}{\mathbf{p}}_{F,𝒜}^{\text{csp-ddh-real}}$	Experiment $\mathbf{E}\mathbf{x}{\mathbf{p}}_{F,𝒜}^{\text{csp-ddh-rand}}$
$i\stackrel{\text{\$}}{\leftarrow }\mathbb{N};X\leftarrow F_{a^i}(b)$ ;	$i\stackrel{\text{\$}}{\leftarrow }\mathbb{N};X\leftarrow F_{a^i}(b)$ ;
$j\stackrel{\text{\$}}{\leftarrow }\mathbb{N};Y\leftarrow F_{a^j}(b)$ ;	$j\stackrel{\text{\$}}{\leftarrow }\mathbb{N};Y\leftarrow F_{a^j}(b)$ ;
$Z\leftarrow F_{a^{i+j}}(b)$ ;	$\ell \stackrel{\text{\$}}{\leftarrow }\mathbb{N};Z\leftarrow F_{a^{\ell }}(b)$ ;
$b\leftarrow 𝒜(X,Y,Z)$ ;	$b\leftarrow 𝒜(X,Y,Z)$ ;
Return b.	Return b.

Intuitively, the CSP-DDH assumption states that the distributions:

$$\begin{array}{cc}& {𝒟}_{\mathrm{1}}\triangleq \left(F_{a^i}\left(b\right),F_{a^j}\left(b\right),F_{a^{i+j}}\left(b\right)\right),\\ {𝒟}_{\mathrm{2}}\triangleq \left(F_{a^i}\left(b\right),F_{a^j}\left(b\right),F_{a^{\ell }}\left(b\right)\right)\end{array}$$

(6)

are computationally indistinguishable when $i,j,\ell \in \mathbb{N}$ are drawn at random.

Remark 6.

Intuitively, it is hard to solve the CSP-DDH problem without solving the CSP problem if G is modeled as a generic semigroup model. According to [33], we know that the discrete logarithm problem (DLP) over finite fields and the corresponding DDH problem are polynomially equivalent in a generic cyclic group. By an analogical manner, we speculate that the CSP problem and the CSP-DDH problem in a generic noncommutative semigroup are polynomially equivalent (see more details in [24]).

2.3. The Fujisaki-Okamoto Transformation [34, 35]

Without loss of generality, a public-key encryption scheme can be defined as a triple $\pi =(𝒦,ℰ,𝒟)$ , where

• (i)

𝒦 is the key generation algorithm that takes as input a system security parameter ${\mathrm{1}}^k$ and outputs a public-/private-key pair $(pk,sk)$ . In general, this algorithm can be formulated as $(pk,sk)\leftarrow 𝒦({\mathrm{1}}^k)$ .

(ii)

ℰ is the encryption algorithm that takes as inputs the public-key $pk$ and a message $m\in ℳ$ and outputs a ciphertext $c\in 𝒞$ , where ℳ and 𝒞 are message space and ciphertext space, respectively. In general, this algorithm can be formulated as $c\leftarrow {ℰ}_{pk}(m)$ or $c\leftarrow {ℰ}_{pk}(m;r)$ when it is necessary to specify the random salt r used in the encryption process.

(iii)

𝒟 is the decryption algorithm that takes as inputs the secret key $sk$ and a ciphertext $c\in 𝒞$ and outputs a message $m\in ℳ$ or a symbol ⊥, which indicates that c is invalid. In general, this algorithm can be formulated as $m/\perp \hspace{0.17em}\leftarrow {𝒟}_{sk}(c)$ .

In general, as for public-key encryption, one-wayness against chosen plaintext attacks (OW-CPA) is the lowest security requirement, while indistinguishability against adaptively chosen ciphertext attacks (IND-CCA2) is the most desirable and the standard security requirement. Cryptographic practise shows that it is always easier to design an OW-CPA secure encryption scheme than to directly design an IND-CCA2 secure one. Thus, it is desirable to have a general method for transforming an OW-CPA secure encryption scheme to an IND-CCA2 secure one [35]. Fortunately, one of this methods was invented by Fujisaki and Okamoto [34] at PKC 1999.

Theorem 7 (FO transformation [34]).

Suppose $H_{\mathrm{1}}$ and $H_{\mathrm{2}}$ are two random oracles with required domains and ranges, respectively. Given a public-key encryption scheme

$$\begin{array}{cc}& \pi =\left(𝒦,ℰ,𝒟\right)\end{array}$$

(7)

that achieves the security of one-wayness against chosen plaintext attacks (OW-CPA), one can get another public-key encryption scheme

$$\begin{array}{cc}& {\pi }^{\prime }=\left({𝒦}^{\prime },{ℰ}^{\prime },{𝒟}^{\prime }\right)\end{array}$$

(8)

that achieves the security of indistinguishability against adaptively chosen ciphertext attacks (IND-CCA2), where

• (1)

  key generation algorithm ${𝒦}^{\prime }$ is identical to 𝒦;

• (2)

  encryption algorithm is defined as

  $$\begin{array}{cc}& {ℰ}_{pk}^{\prime }\left(m\right)=\left({ℰ}_{pk}\left(r\right),m\oplus H_{\mathrm{1}}\left(r\right),H_{\mathrm{2}}\left(m,r\right)\right),\end{array}$$

  (9)
  where r is picked at random;

• (3)

  decryption algorithm ${𝒟}_{sk}^{\prime }(c_{\mathrm{1}},c_{\mathrm{2}},c_{\mathrm{3}})$ performs the following steps:

• (b)

  $m^{\prime }\leftarrow c_{\mathrm{2}}\oplus H_{\mathrm{1}}(r^{\prime })$ ;

• (c)

  output $m^{\prime }$ if $c_{\mathrm{3}}=H_{\mathrm{2}}(m^{\prime },r^{\prime })$ and ⊥ otherwise.

3. Building Block: Noncommutative Signcryption

Before describing our proposal for WSN key management, let us at first propose a signcryption scheme from noncommutative semigroups where the CSP-related assumptions hold. We will see later, when this scheme is instantiated by using braids, we obtain a very efficient signcryption scheme that is ${\mathrm{2}}^{\mathrm{15}}$ times faster than RSA-based signcryption (suppose that 1024 bit RSA modulus were used).

Suppose that G is a noncommutative semigroup so that the CSP problem and the CSP-DDH problem over G are intractable. Then, the public parameters of the proposed signcryption are given by a quintuple $〈𝔇,a,b,H_{\mathrm{1}},H_{\mathrm{2}}〉$ , where

• (i)

𝔇 is a description of G and $G^{-\mathrm{1}}\subset G$ . Without loss of generality, we assume the length of 𝔇 is bounded by $𝒪(\log |G|)$ for finite G. When G is infinite but admits a finite presentation, say $fp(G)=〈X\mid R〉$ , the length of 𝔇 is the sum of the length of X and the length of R. However, for braid group $B_n$ , 𝔇 admits even efficient description since whenever the braid index n is given, the generator set $X=\{{\sigma }_{\mathrm{1}},\dots ,{\sigma }_{n-\mathrm{1}}\}$ and the relation set $R=\{{\sigma }_i\hspace{0.17em}{\sigma }_j={\sigma }_{j\hspace{0.17em}}{\sigma }_i:|i-j|>\mathrm{1}\}\hspace{0.17em}\cup \hspace{0.17em}\{{\sigma }_i{\hspace{0.17em}\sigma }_j\hspace{0.17em}{\sigma }_i={\sigma }_j\hspace{0.17em}{\sigma }_i\hspace{0.17em}{\sigma }_j:|i-j|=\mathrm{1}\}$ ( $\mathrm{1}\le i$ , $j\le n-\mathrm{1}$ ) is totally specified. That is, for braid group $B_n$ , $𝔇=n$ ;

(ii)

$a\in G^{-\mathrm{1}}\subset G$ and $b\in G$ are two fixed elements that are picked at random;

(iii)

$H_{\mathrm{1}}:G\to G^{\mathrm{2}}$ and $H_{\mathrm{2}}:G^{\mathrm{2}}\to G$ are two cryptographic hash functions that are modeled as random oracles.

Then, the proposed signcryption scheme consists of the following three algorithms:

• (i)

$𝒦𝒢({\mathrm{1}}^k)$ , key generation algorithm that takes as input the system security parameter ${\mathrm{1}}^k$ , picks an integer $s\in \{\mathrm{0,1}{\}}^k$ at random calculates $x=b^{a^s}\in G$ , and finally outputs $(s,x)$ as the private-/public-key pair.

(ii)

$𝒮𝒞(s,y;m)$ , signcryption algorithm that takes as inputs the sender's private-key $s\in \{\mathrm{0,1}{\}}^k$ , the receiver's public-key $y\in G$ , and the message $m\in G$ , and performs the following steps:

• (1)

pick $t\in \{\mathrm{0,1}{\}}^k$ at random;

(2)

compute

$$\begin{array}{cc}& c_{\mathrm{1}}=b^{a^t},\\ h=H_{\mathrm{2}}\left(m,c_{\mathrm{1}}\right),\\ \sigma ={\left(a^t\right)}^{-\mathrm{1}}{a}^{s}h{c}_{\mathrm{1}},\\ c_{\mathrm{2}}=\left(m\parallel \hspace{0.17em}\sigma \right)\oplus H_{\mathrm{1}}\left(y^{a^t}\right),\end{array}$$

(10)

 

where operator “⊕” should be viewed as XOR operation over bit-strings that are encoding results of a pair in $G^{\mathrm{2}}$ ;

(3)

output $(c_{\mathrm{1}},c_{\mathrm{2}})$ .

Theorem 8.

The proposed signcryption is consistent.

Proof.

Suppose that the sender and the receiver performs honestly, and their inputs are well formed. That is, $x=b^{a^s}$ and $y=b^{a^r}$ . Then, since

$$\begin{array}{l}{c}_{\mathrm{1}}^{a^r}={\left(b^{a^t}\right)}^{a^r}\\ \hspace{1em}\hspace{1em}=b^{a^{t+r}}\\ \hspace{1em}\hspace{1em}={\left(b^{a^r}\right)}^{a^t}\\ \hspace{1em}\hspace{1em}=y^{a^t},\\ m^{\prime }\parallel \hspace{0.17em}{\sigma }^{\prime }=c_{\mathrm{2}}\oplus H_{\mathrm{1}}\left(c_{\mathrm{1}}^{a^r}\right)\\ \hspace{1em}\hspace{1em}=\left(m\parallel \hspace{0.17em}\sigma \right)\oplus H_{\mathrm{1}}\left(y^{a^t}\right)\oplus H_{\mathrm{1}}\left(y^{a^t}\right)\\ \hspace{1em}\hspace{1em}=m\parallel \hspace{0.17em}\sigma ,\\ h^{\prime }=H_{\mathrm{2}}\left(m^{\prime },c_{\mathrm{1}}\right)\\ \hspace{1em}\hspace{1em}=H_{\mathrm{2}}\left(m,c_{\mathrm{1}}\right)\\ \hspace{1em}\hspace{1em}=h,\end{array}$$

(11)

we have

$$\begin{array}{l}{c}_{\mathrm{1}}^{{\sigma }^{\prime }}={\left(b^{a^t}\right)}^{\sigma }\\ \hspace{1em}={\left(b^{a^t}\right)}^{(a^t{)}^{-\mathrm{1}}{a}^{s}h{c}_{\mathrm{1}}}\\ \hspace{1em}={\left(b^{a^s}\right)}^{h{c}_{\mathrm{1}}}\\ \hspace{1em}=x^{h{c}_{\mathrm{1}}}\\ \hspace{1em}=x^{h^{\prime }{c}_{\mathrm{1}}}.\end{array}$$

(12)

Then, $m^{\prime }=m$ will be output correctly.

Theorem 9.

Suppose that $H_{\mathrm{1}}$ and $H_{\mathrm{2}}$ are random oracles. The proposed signcryption is indistinguishable against adaptively chosen ciphertext attack (IND-CCA2) assuming that the CSP-DDH problem over the underlying noncommutative semigroup G is intractable.

Proof.

To apply the well-known Fujisaki-Okamoto transformation theorem [34], we at first need to define an IND-CPA secure encryption scheme $\pi =(𝒦,ℰ,𝒟)$ and then establish the security relationship between the proposed signcryption scheme and the enhanced encryption scheme ${\pi }^{\prime }$ , that is, an FO transformation from π. This can be done by setting $\pi =(𝒦,ℰ,𝒟)$ as follows:

• (i)

$𝒦({\mathrm{1}}^k):=𝒦𝒢({\mathrm{1}}^k)$ . That is, the key generation algorithm remains unchanged.

(ii)

The encryption algorithm $ℰ(y;m)$ that takes as inputs the receiver's public-key $y\in G$ and the intended message $m\in G$ and then performs the following steps:

• (1)

pick $t\in \{\mathrm{0,1}{\}}^k$ at random;

(2)

compute $c_{\mathrm{1}}=b^{a^t}$ and $c_{\mathrm{2}}=y^{a^t}m$ ;

(3)

output $(c_{\mathrm{1}},c_{\mathrm{2}})$ .

(iii)

The decryption algorithm $𝒟(r;c_{\mathrm{1}},c_{\mathrm{2}})$ that takes as inputs the receiver's private-key $r\in \{\mathrm{0,1}{\}}^k$ and the ciphertext pair $(c_{\mathrm{1}},c_{\mathrm{2}})\in G^{\mathrm{2}}$ and then outputs the intended message $m=c_{\mathrm{2}}(c_{\mathrm{1}}^{a^r}{)}^{-\mathrm{1}}$ .

Apparently, this is just the ElGamal-like variant based on CSP-DDH assumption. According to Theorem 1 of [24], this is IND-CPA secure. Then, according to Theorem 7, the FO variant ${\pi }^{\prime }=({𝒦}^{\prime },{ℰ}^{\prime },{𝒟}^{\prime })$ is IND-CCA2 secure when $H_{\mathrm{1}}$ and $H_{\mathrm{2}}$ are modeled as random oracles, where

• (i)

${𝒦}^{\prime }({\mathrm{1}}^k):=𝒦({\mathrm{1}}^k)$ .

(ii)

${ℰ}^{\prime }(y;m)$ performs the following steps:

• (1)

pick $u\in G$ at random;

(2)

let $(c_{\mathrm{1}},c_{\mathrm{2}})\leftarrow ℰ(y;u)$ ;

(3)

let $c_{\mathrm{3}}=m\oplus H_{\mathrm{1}}(u)$ and $c_{\mathrm{4}}=H_{\mathrm{2}}(m,u)$ ;

(4)

output $(c_{\mathrm{1}},c_{\mathrm{2}},c_{\mathrm{3}},c_{\mathrm{4}})$ .

(iii)

The decryption algorithm $𝒟(r;c_{\mathrm{1}},c_{\mathrm{2}},c_{\mathrm{3}},c_{\mathrm{4}})$ that takes as inputs the receiver's private-key $r\in \{\mathrm{0,1}{\}}^k$ and the ciphertext qudruple $(c_{\mathrm{1}},c_{\mathrm{2}},c_{\mathrm{3}},c_{\mathrm{4}})$ , and then performs the following steps:

• (1)

let $u^{\prime }\leftarrow 𝒟(r;c_{\mathrm{1}},c_{\mathrm{2}})$ ;

(2)

let $m^{\prime }\leftarrow c_{\mathrm{3}}\oplus H_{\mathrm{1}}(u^{\prime })$ ;

(3)

output $m^{\prime }$ if $c_{\mathrm{4}}=H_{\mathrm{2}}(m^{\prime },u^{\prime })$ and ⊥ otherwise.

Now, let us show that in the same random oracle models, if there is a polynomlai-time adversary 𝒜 that can, with nonnegligible probability, break the IND-CCA2 security of the proposed signcryption scheme, there is another polynomial-time adversary ℬ that can, by controlling the response of the random oracles $H_{\mathrm{1}}$ and $H_{\mathrm{2}}$ , break the IND-CCA2 security of ${\pi }^{\prime }$ . However, this is contrary to the fact that ${\pi }^{\prime }$ is IND-CCA2 secure. Therefore, 𝒜's advantage of breaking the proposed signcryption scheme must be negligible.

In fact, if ℬ controls the response of the random oracles $H_{\mathrm{1}}$ and $H_{\mathrm{2}}$ , then it can break the IND-CCA2 security of ${\pi }^{\prime }$ with nonnegligible probability. This is apparently, since B controls the response of $H_{\mathrm{2}}$ , whenever seeing a ciphertext $(c_{\mathrm{1}},c_{\mathrm{2}},c_{\mathrm{3}},c_{\mathrm{4}})$ , it can retrieve the message m and random salt u by looking up the response list of $H_{\mathrm{2}}$ under the reasonable assumption that the probability for different pair $(m^{\prime },u^{\prime })$ with same hash value with the pair $(m,u)$ is negligible.

The left thing is to show that ℬ, without knowing the receiver's private-key $r\in \{\mathrm{0,1}{\}}^k$ , how to simulate the response on decryption queries for 𝒜 in a perfect manner. Whenever A invokes a decryption query by submitting a signcryption pair $(c_{\mathrm{1}},c_{\mathrm{2}})$ , ℬ responds as follows:

• (1)

look up $(h_{\mathrm{2}},m_i,c_{\mathrm{1}})$ in $H_{\mathrm{2}}$ -list. If there is no matched triple, ℬ sends ⊥ to 𝒜 as the response;

(2)

for each matched triple $(h_{\mathrm{2}},m_i,c_{\mathrm{1}})$ , ℬ performs the following steps:

• (a)

for each $(h_{\mathrm{1}},Y_i)$ in $H_{\mathrm{1}}$ -list, do the following steps:

• (i)

extract a possible ${\sigma }_i$ according to the following formula:

$$\begin{array}{cc}& c_{\mathrm{2}}=\left(m_i\parallel \hspace{0.17em}{\sigma }_i\right)\oplus h_{\mathrm{1}}.\end{array}$$

(13)

 

This can be done since ℬ knows $c_{\mathrm{2}}$ , $m_i$ and $h_{\mathrm{1}}$ at this stage;

(ii)

test whether the equality $c_{\mathrm{1}}^{{\sigma }_i}=x^{h_{\mathrm{2}}{c}_{\mathrm{1}}}$ holds? (recall that x is the verification key of the singer). If so, replies 𝒜 with $m_i$ and end of the response; otherwise, continue;

(3)

if up to now, ℬ has not output response to 𝒜 yet, then ℬ sends ⊥ to 𝒜 as the response.

Now, let us show that ℬ's simulation is perfect. It is reasonable to assume that without accessing hash queries on $H_{\mathrm{1}}$ and $H_{\mathrm{2}}$ , 𝒜's probability for submitting a valid signcryption pair $(c_{\mathrm{1}},c_{\mathrm{2}})$ is negligible. Thus, whenever 𝒜 invokes hash queries on $H_{\mathrm{1}}$ and $H_{\mathrm{2}}$ for forming a valid signcryption pair, related materials are recorded and ℬ can retrieve them and finally send 𝒜 a perfect response.

Remark 10.

Note that although the signature scheme embedded in the proposed signcryption scheme merely achieves unforgeable against no-message attacks, the resulted signcryption is existentially unforgeable against external adaptively chosen message attack. Here, external forgeries means that it is neither the singer, nor the intended receiver. We know that it is reasonable to exclude the signer from forgeries. Let us explain why we further exclude the intended receiver from the forgeries. In fact, the primitive of signcryption provides confidentiality of the message against all entities except the intended receiver and meanwhile it provides the authenticity of the sender (i.e., the signer) for the intended receiver. That is, the authenticity embedded in the signcryption primitive is unidirectional, instead of bidirectional. Therefore, it seems that there is no reason for an intended receiver to forge a signature on behalf of some signer and then encrypt the signature for himself/herself, except for planting false evidence against some senders. In other words, in our proposal, we assume that the receiver who possesses the corresponding private-key for performing designcryption is honest. Otherwise, an existentially unforgeable signature scheme, such as the noncommutative signature scheme in [36] should be embedded therein. For further consideration of the insider security and the outsider security of signcryptions, one can refer to [37, 38].

4. Lightweight Implementation of Key Management Protocols for WSNs

In [5], Hagras et al. described an efficient key management scheme for WSNs based on elliptic curve signcryption. Our proposal follows their diagram. However, the main differences of our work lie in the following aspects:

• (i)

firstly, the signcryption algorithm used by Hagras et al. is abstract and essentially hybrid where a symmetric encryption algorithm is involved. However, we will give a detailed specification of each algorithm;

(ii)

secondly, Hagras et al.'s proposal is based on commutative platforms, while as far as we known, our proposal is firstly based on noncommutative platforms.

Similar to [5], suppose that the network architecture is the standard clustered WSN architecture depicted in Figure 3. The proposed key management scheme supports three protocols: the first is used to generate private-/public-keys for each individual nodes, including base nodes, cluster headers, and cluster nodes; the second is essentially a signcryption scheme that is used by base node to send session keys to cluster heads; and the third is essential also a signcryption scheme that is used by cluster heads to send session keys to cluster nodes.

Figure 3

WSN Architecture.

Let $B_n$ be the braid group and $a,b\in B_n$ . Suppose that $F(·,·)$ is the Conj-LD system defined over braid group $B_n$ , while $H_{\mathrm{1}}:G\to G^{\mathrm{2}}$ and $H_{\mathrm{2}}:G^{\mathrm{2}}\to G$ are two cryptographic hash functions. Our proposal consists of three protocols that are described in the following subsections.

4.1. Key Generation Protocol

This protocol is responsible for creating public-/private-key pairs for base nodes (BNs), cluster heads (CHs), and cluster nodes (CNs).

Step 1.

Generate public-/private-key for based nodes.

•  

$V_{\text{BN}}\in \{\mathrm{0,1}{\}}^k$ : the private-key for the base node is a positive integer chosen uniformly at random.

 

$P_{\text{BN}}\in B_n$ : the corresponding public-key for the base node is calculated as $P_{\text{BN}}=F(a^{V_{\text{BN}}},b)$ .

Step 2.

Generate public-/private-key for cluster heads.

•  

$V_{\text{C}{\text{H}}_j}\in \{\mathrm{0,1}{\}}^k$ : the private-key for the jth cluster head is a positive integer chosen uniformly at random.

 

$P_{\text{C}{\text{H}}_j}\in B_n$ : the corresponding public-key for the jth cluster head is calculated as $P_{\text{C}{\text{H}}_j}=F(a^{V_{\text{C}{\text{H}}_j}},b)$ .

Step 3.

Generate public-/private-key for cluster nodes.

•  

$V_{\text{C}{\text{N}}_i}\in \{\mathrm{0,1}{\}}^k$ : the private-key for the ith cluster head is a positive integer chosen uniformly at random.

 

$P_{\text{C}{\text{N}}_i}\in B_n$ : the corresponding public-key for the ith cluster head is calculated as $P_{\text{C}{\text{N}}_i}=F(a^{V_{\text{C}{\text{N}}_i}},b)$ .

Step 4.

Session key generation for base node and cluster heads.

• (1)

The base node creates the session key $K_{\text{BN}-\text{C}{\text{H}}_j}$ which will be used for secure communication between the jth cluster head and the base node.

(2)

The jth cluster head creates the session key $K_{\text{C}{\text{H}}_j-\text{C}{\text{N}}_i}$ which will be used for secure communication between the jth cluster head and the ith cluster node.

Without loss of generality, here we assume that $K_{\text{BN}-\text{C}{\text{H}}_j}$ and $K_{\text{C}{\text{H}}_j-\text{C}{\text{N}}_i}$ are elements of G picked at random. (In fact, we can always employ an encoding algorithm to map elements of G into valid session keys.)

Remark 11.

Note that in the last step, all session keys are newly generated by the base node and the cluster nodes, respectively. In fact, after the execution of Steps 1, 2 and 3, we know that the base node and the jth cluster head can calculate the shared session key $K_{\text{BN}-\text{C}{\text{H}}_j}=F(a^{V_{\text{BN}}+V_{\text{C}{\text{H}}_j}},b)$ , and the jth cluster head and the ith cluster node can calculate the shared session key $K_{\text{C}{\text{H}}_j-\text{C}{\text{N}}_i}=F(a^{V_{\text{C}{\text{H}}_j}+V_{\text{C}{\text{N}}_i}},b)$ . However, it is not a good choice to use this kind of session keys since they are totally determined by long-term private-keys. Instead, we suggest to renew a session key instantly to guarantee its freshness.

4.2. BN-CHs Signcryption

The base node signcrypts the session key $K_{\text{BN}-\text{C}{\text{H}}_j}$ using its private-key and sends the ciphertext $(c_{\mathrm{1}},c_{\mathrm{2}})$ to the jth cluster head as follows:

• (1)

pick $t\in \{\mathrm{0,1}{\}}^k$ at random;

(2)

$c_{\mathrm{1}}=F(a^t,b)$ ;

(3)

$h=H_{\mathrm{2}}(K_{\text{BN}-\text{C}{\text{H}}_j},c_{\mathrm{1}})$ ;

(4)

$\sigma =(a^t{)}^{-\mathrm{1}}{a}^{V_{\text{BN}}}h{c}_{\mathrm{1}}$ ;

(5)

$c_{\mathrm{2}}=(K_{\text{BN}-\text{C}{\text{H}}_j}\parallel \hspace{0.17em}\sigma )\oplus H_{\mathrm{1}}(F(a^t,P_{\text{C}{\text{H}}_j}))$ ;

(6)

send $(c_{\mathrm{1}},c_{\mathrm{2}})$ to the jth cluster head.

Upon receiving the ciphertext $(c_{\mathrm{1}},c_{\mathrm{2}})$ from the base node, the jth cluster head designcrypts the session key as follows:

• (1)

compute $K\parallel \hspace{0.17em}\sigma =c_{\mathrm{2}}\oplus H_{\mathrm{1}}(F(a^{V_{\text{C}{\text{H}}_j}},c_{\mathrm{1}}))$ , $h=H_{\mathrm{2}}(K,c_{\mathrm{1}})$ ;

(2)

accept K if $F(\sigma ,c_{\mathrm{1}})=F(h{c}_{\mathrm{1}},P_{\text{BN}})$ and report “FAILURE” otherwise.

4.3. CH-CNs Signcryption

The jth cluster head signcrypts the session key $K_{\text{C}{\text{H}}_j-\text{C}{\text{N}}_i}$ using its private-key and sends the ciphertext $(d_{\mathrm{1}},d_{\mathrm{2}})$ to the ith cluster node as follows:

• (1)

pick $s\in \{\mathrm{0,1}{\}}^k$ at random.

(2)

$d_{\mathrm{1}}=F(a^s,b)$ .

(3)

$g=H_{\mathrm{2}}(K_{\text{C}{\text{H}}_j-\text{C}{\text{N}}_i},d_{\mathrm{1}})$ .

(4)

$\sigma =(a^s{)}^{-\mathrm{1}}{a}^{V_{\text{C}{\text{H}}_j}}g{d}_{\mathrm{1}}$ .

(5)

$d_{\mathrm{2}}=(K_{C{\text{H}}_j-\text{C}{\text{N}}_i}\parallel \hspace{0.17em}\sigma )\oplus H_{\mathrm{1}}(F(a^s,P_{\text{C}{\text{N}}_i}))$ .

(6)

Send $(d_{\mathrm{1}},d_{\mathrm{2}})$ to the ith cluster node.

Upon receiving the ciphertext $(d_{\mathrm{1}},d_{\mathrm{2}})$ from the jth cluster head, the ith cluster node designcrypts the session key as follows:

• (1)

compute $K\parallel \hspace{0.17em}\sigma =d_{\mathrm{2}}\oplus H_{\mathrm{1}}(F(a^{V_{\text{C}{\text{N}}_i}},d_{\mathrm{1}}))$ , $h=H_{\mathrm{2}}(K,d_{\mathrm{1}})$ ;

(2)

accept K if $F(\sigma ,d_{\mathrm{1}})=F(g{d}_{\mathrm{1}},P_{\text{C}{\text{H}}_j})$ and report “FAILURE” otherwise.

5. Performance Evaluation

5.1. Complexity of Basic Operations

Now, let us compare the braid-based signcryption schemes with the RSA-based ones. According to Cha et al.'s implementation [39] and Maffre's test [40], the complexities of the braid operations, such as multiplication, inversion, and canonical form computation, are bounded by $𝒪(l^{\mathrm{2}}n\log n)$ in the sense of bit operations, where n and l are the braid index and the canonical length of involved braids, respectively. If we follow Maffre's suggestions by setting $n=\mathrm{50}$ and $l=\mathrm{10}$ , then the number of bit operations for implementing these braid operations is proportional to ${\mathrm{2}}^{\mathrm{15}}$ . We know that the number of bit operations for implementing modular exponentials involved in RSA-based schemes is proportional to ${\mathrm{2}}^{\mathrm{30}}$ when the bit length of RSA modulus is set to 1024. This suggests that the proposed braid-based signcryption is about ${\mathrm{2}}^{\mathrm{15}}$ times faster than RSA-based ones.

Further, if we lift the security level of the RSA-based schemes to $\exp (\mathrm{92.80})$ , which is comparable to the security level of our scheme (see Section 5.3), then the RSA modulus should be at least 2008 bits (see [23] for details). Then, the number of bit operations for implementing modular exponentials involved in RSA-based schemes is proportional to ${\mathrm{2}}^{\mathrm{33}}$ . This suggests that at the same security level, our braid-based signcryption is even efficient than that of RSA-based ones.

5.2. Parameter Size

A braid in $B_n$ with l canonical factors can be represented by a bit string of size $\lceil \ln \log n\rceil$ [16]. Thus, when $n=\mathrm{50}$ and $l=\mathrm{10}$ , the sizes of the system parameters, the private-key, the public-key, and the ciphertexts are 5650 bits, 80 bits, 2822 bits, and 8466 bits, respectively. In total, it is about 17 Kbits (see Table 2). According to [5], a typical WSN node, MICA2 mote, developed by the University of California at Berkeley has an 8-bit 7.3 MHz processor with 4 KB (i.e., 32 Kbits) RAM and 128 KB programmable ROM. This suggests that although our scheme will take more memory than RSA-based ones, it is still compact enough to be deployed in typical WSN environments.

Table 2

Parameter length.

Parameter	Components and domains	Size	Size in bits (n = 50, l = 10)
System parameters	$n\in \mathbb{N}$ , $a,b\in B_n$	$\lceil \log n+2\ln \log n\rceil$	5650
Private key1	$s\in {\left\{0,1\right\}}^k$	k	80
Public key	${b^a}^s\in B_n$	$\lceil \ln \log n\rceil$	2822
Signcryption2	( $c_1$ , $c_2$ ) ∈ $B_n\times B_n^2$	$\lceil \mathrm{3}\ln \log n\rceil$	8466
Total	—	≈ $\lceil \mathrm{6}\ln \log n\rceil$	≈17 K

${}^{\mathrm{1}}$ It is enough to use 80-bit private keys in WSN-oriented applications.

${}^2$ The length of $c_2$ is about equivalent to the length of two braids.

5.3. Security Levels

In [23], Wang et al. presented an analysis of the security levels of braid-based cryptosystems against two typical attacks: heuristic attacks and brute force attacks. In a similar manner, we can discuss the security levels of the proposed signcryption scheme. According to [23], the security level of a cryptosystem is modeled as the number of bit operations for breaking the cryptosystem. Since this number is in general huge, we always use its logarithm in evaluation and refer to as the logarithmic security level.

As for braid-based cryptosystems, heuristic attacks mean currently known smart attacks, such as length-based attacks [42, 43] and linear representation attacks. According to Maffre's test [40] and Wang et al.'s summarization [23], the logarithmic complexity of existing heuristic attacks against braid-based cryptosystems can be expressed as $\log (C_{\mathrm{150}}^{\mathrm{50}})\approx \mathrm{92.80}$ .

Let us proceed to analyze the security level against brute force attacks. According to Ko et al. [29], when the private-keys of braid-based schemes are selected carefully, that is, avoiding the weak keys mentioned by Maffre [40], all known heuristic attacks will be unsuccessful. Further, according to the previous analysis given by Ko et al. [16], the complexity of carrying brute force attacks towards braid-based schemes is proportional to $\exp ((\mathrm{1}/\mathrm{2})\ln \log n)$ . Therefore, when we adopt Maffre's suggestion by setting the braid index and the canonical length of the involved braids to $n=\mathrm{50}$ and $l=\mathrm{10}$ , respectively, the security level of our scheme against brute force attacks is proportional to $\exp (\mathrm{978})$ . This suggests that in the foreseeable future it is infeasible to launch exhaustive attacks towards our proposal.

In brief, we can summarize the performance comparisons in two cases: in Case I, we consider the currently acceptable parameter settings, and in Case II, we lift the security level of the RSA-based schemes to $\exp (\mathrm{92.80})$ by increasing the length of the corresponding RSA modulus. The results are listed in Table 3. We can conclude that our scheme is very fast in signcrypting and designcrypting, but acceptably larger in storage requirement.

Table 3

Complexities and security levels.

	RSA-based schemes [23]			Braid-based schemes
	Technique	k = 1024	k = 2008	Technique	n = 50, l = 10
Signcryption	Modular Exp.	230	233	Braid operation	215
Security level ${}^1$	Factoring	exp (69.69)	exp (92.80)	Solving CSP	exp (92.80)

${}^1$ The security level of RSA-based schemes are evaluated according to the best known factoring method, that is, the number field sieve (NFS) method [41].

Remark 12.

Although Table 3 seems very similar to that in [23], there are remarkable differences as follows: on one hand, in [23], the efficiencies of the signing process and the verifying process of the braid-based signature scheme in [23] are much different; signing can be implemented in the complexity proportional to ${\mathrm{2}}^{\mathrm{15}}$ , while the complexity of verifying is proportional to ${\mathrm{2}}^{\mathrm{34}}$ . However, the efficiencies of the signcrypting process and the designcrypting process in this paper are same: both of them are proportional to ${\mathrm{2}}^{\mathrm{15}}$ since in our new proposal it is unnecessary to solve the CDP problem over braid groups; on the other hand, the braid-based scheme in [23] is merely a signature scheme, while the proposal in this paper is a signcryption scheme. This suggests that our signcryption scheme is much efficient than Wang et al.'s signature scheme [23]. In brief, our proposal does more and faster than that in [23].

6. Conclusion

Lightweight cryptographic schemes are useful for securing WSN-oriented applications. To minimally incorporate confidentiality, authenticity, integrity, scalability, and flexibility, signcryption is the proper primitive to realize key management protocols for WSNs. However, most existing signcryption schemes are heavyweight and not suitable for resource-limited sensors. In this paper, we propose a braid-based signcryption scheme and then develop a key establishment protocol for wireless sensor networks. From the complexity view, the proposed scheme is ${\mathrm{2}}^{\mathrm{15}}$ times faster than RSA-based ones. As far as we know, this proposal is the first signcryption scheme based on noncommutative algebraic structures. In addition, the analysis of the basic operations and parameter sizes suggests that our proposal can be efficiently deployed in typical WSN environments.