Informática 35 (2011) 521-530 521
Short Signcryption Scheme for the Internet of Things
Xuanwu Zhou ' , Zhigang Jin , Yan Fu ' , Huaiwei Zhou , Lianmin Qin
1	School of Electronics and Information Engineering, Tianjin University, Tianjin 300072, China
2	Command College of the Chinese Armed Police Forces, Tianjin 300250, China
3	Information Technology Research Center, Huarong Corporation, Yantai 265400, China E-mail: schwoodchow@163.com
Keywords: internet of things, signcryption, provable security, distributed key management, system efficiency Received: June 23, 2011
Signcryption is an effective cryptographic primitive, which simultaneously fulfils both the functions of encryption and signature with much lower cost than traditional schemes; it is an ideal method to provide confidentiality and unforgeability and ensure secure data storage and transmission in the IOT (Internet of things). In the paper, we propose a publicly verifiable short signcryption scheme S-ECSC for the Internet of things based on elliptic curves cryptosystem; and prove the provable security of S-ECSC under the Random Oracle model, including confidentiality in IND-CCA2 model, unforgeability in UF-CMA model and non-repudiation security. As per the efficiency analysis, S-ECSC achieves an average 80% reduction in computation cost compared with typical discrete logarithm, RSA based signcryption schemes, and has the lowest communication cost in Elgamal type signcryptions. With its superiority in efficiency and security, S-ECSC proves to be more suitable for resource-restricted environment in IOT and better satisfies the requirement of secure protocols in IOT, such as key management, secure routing, etc. At last, we take key generating and distributing protocol of distributed key management in IOT as an application example, and analyse the method and importance to apply S-ECSC into secure protocols in IOT.
Povzetek: Članek opisuje šifrirno shemo za internet stvari.
1 Introduction
The concept of IOT (Internet of Things) was first put forward by Ashton of the former MIT Auto-ID Center in 1999 when he was working on RFID (Radio Frequency Identification). Presently, the most widely-accepted definition of IOT is as follows [1, 2, 3, 4]. IOT is a self-configuring network in which things are connected with network according to certain protocols with RFID, ultrared sensor, GPS(Global Positioning System), laser scanner, etc to interchange and transmit data, and ultimately achieve intelligent identification, positioning, tracing, supervision and management. IOT is the new direction of future computer and communication technology, and is regarded as the third landmark in the development of information technology after computer science and Internet.
According to the function classification, the hierarchical structure of IOT is composed of application layer, network layer and sensor layer. The basic function of network layer is secure and reliable interconnection between things via wire-based or wireless technology, in which the secure and dynamic interconnection via wireless network has been the overwhelming trend. In wireless network technology, many researchers have focused on IEEE802.11 WLAN (Wireless Local Area
Network) , which is mainly composed of wireless Ad hoc network, WSN (Wireless Sensor Network) and
WMN (Wireless Mesh Network). As a new wireless network, IEEE802.11 WLAN proves to be suitable for commercial, medical, domestic, military, and other applications with its superiority, such as inexpensiveness, adaptability and reliability, etc. In the Internet of things, IEEE802.11 WLAN has been playing an increasingly important role in secure and reliable connection between different objects. Whereas, the distributed network management and restricted network resources in IEEE802.11 WLAN have rendered many problems as to the security of confidentiality, integrity, non-repudiation and availability for data storage and transmission in IOT. Besides, security measures designed for traditional network, which has relatively abundant network resources, fixed connection, stable topology, special routing and comprehensive network service, are not completely applicable to wireless network environment in the Internet of thing. Therefore, it is of great necessity to design special security technology, protocols and corresponding algorithms for the secure and dynamic wireless communication in the Internet of things.
The confidentiality and integrity of message is the basic requirement for secure communication in IOT; in the symmetric setting, efforts focused on the composition of symmetric key encryption and message authentication code (MAC). In asymmetric settings, the composition method of "signature-then-encryption" has been
522 Informática 35 (2011) 521-530
X. Zhou et al.
employed. But these have all proved impractical not only for the insecurity in case of arbitrary schemes but also for the low efficiency regarding application into resource-restricted environment in IOT, which results from the sum cost of encryption and signature.
In 1997, Zheng proposed a cryptographic primitive "signcryption" [5], which simultaneously fulfils the integrated function of public encryption and digital signature with a computing and communication cost significantly smaller than that required by the "signature-then-encryption" method. Since then, signcryption has been a focus of cryptography as an ideal method to simultaneously provide confidentiality and unforgeability and many researchers have explored the application of signcryption in different security protocols [6, 7, 8, 9, 10, 11]. The study of signcryption algorithms suitable for IOT network environment and its application in IOT security schemes is an important direction in cryptography; it is more of a requirement from the rapid development of the Internet of things than just a requirement from the theoretical or applied cryptography research.
In order to improve the security and efficiency of communication in the Internet of things, we propose a publicly verifiable short signcryption scheme S-ECSC for the Internet of things based on elliptic curves cryptosystem; and prove the provable security of S-ECSC under the Random Oracle model, including confidentiality in IND-CCA2 model, unforgeability in UF-CMA model and non-repudiation security. At last, we take key generating and distributing protocol for different terminals of distributed key management in IOT as an application example, and analyse the method and importance in the application of S-ECSC into secure protocols in IOT. Compared with other typical discrete logarithm, RSA and elliptic curves based signcryption schemes, S-ECSC is more suitable for resource-restricted environment in IOT communication with its superiority in computing and communication cost and can better satisfy the requirement of secure protocols in IOT, such as key management, secure routing, etc.
2 Short Signcryption Scheme on Elliptic Curves
First, we pin down the basic notions concerning signcryption which will facilitate the design and analysis of the short signcryption scheme.
2.1 Basic Notions in Signcryption Definition 2.1.1 (Elliptic Curve) An elliptic curve E(F) over finite field Fq is a sextuple: T =
(q, a , b , P , l, h ), where P =( xP, yP ) is the base
point of E(F ), prime l is the order of P . As to t e Z*,
Q and G e E(F ) , Q = tG denotes multiple double
additions on elliptic curve. O is the point at infinity,
satisfying lP = O and G + O = G for any point G e E(F ).
Definition 2.1.2 (ECDLP, Elliptic Curve Discrete Logarithm Problem). ECDLP is the following computation:
x ^ ECDLP(Q, P). P is a base point and Q e(P) , x e Z* , Q = xP. Definition 2.1.3 (Signcryption Scheme) A signcryption scheme £ = (GC , GK , SC , USC ) consists of the following algorithms:
1.	Probabilistic common parameters generation
algorithm GC (1) takes security parameter 1k as input and returns a sequence of common parameters such as description of computational groups and hash functions.
2.	Key generation algorithm GK (ID,1k), which is also probabilistic, takes identity and security parameter as input and returns secret/public key-pair (skID, PKm).
(skm, PKid ) ^ GK (ID,1k).
3.	Signcryption algorithm SC ( skA , PKB , m )that
takes sender's secret key skA , receiver's public key
pkB and message m e SPm ( SPm is the message
space) as input and returns signcryption text C or ^ (a reject symbol). It is also probabilistic algorithm.
C U{±} ^ SC (skA, PKb , m).
4.	Deterministic unsigncryption algorithm USC (skB, PKa , C )takes as input receiver's secret key skB, sender's public key PK A and signcryption text C , and returns either message m or ^ .
m U{±} ^ USC (skB, PKa , C).
If the signcryption scheme is publicly verifiable, it is composed of an additional public verification algorithm PV .
5.	Deterministic public verification algorithm PV ( PK A , PK B , C , R ) takes as input public key pair ( PKb , PKa ),signcryption text C and parameter R , and returns either "true" or ^ .
"W U{±} ^ PV ( PKa , PKb , C, R).
2.2 S-ECSC Signcryption Algorithm
Short signcryption scheme S — ECSC = (GC, GK, SC, USC, PV)
Common parameters generation
GC (1k ) ="On input (1k ):
K:E (Fq) ^ {0,1}Lk (lk), H: {0,1}* ^ Z*, (K,H,T)^GC (1k)."
SHORT SIGNCRYPTION SCHEME FOR.
Informatica 35 (2011) 521-530 523
T = (q, a, b , P , l, h ),where P =( xP, yP) is the base point of E(F ), ord(P) = l is a prime, O is the
point at infinity.
Key pair generation
GK (A,1k) ="On input (A,1k):
skA Z*, PKa = skAP * O,
(skA, PKa ) ^."
GK (B,1k) ="On input (B,1k):
skB Z*, PKb = skBP * O,
(skB, PKB ) ^ " Signcryption
SC (skA, PKb , m )="On input (skA, PKB, m): If skA £ Z/ or PKb £< P > return 1, r Z*, R =(xR,yR)^rPKB, ct ^ K (R), c ^ Ect (m), h ^ H ( m | PKa I PKb I R), s = (hskA + r )mod l,
C =( c , h , s )."
Symmetric encryption scheme Y = ( E , D ) is an encryption scheme with passive indistinguishability defined in Definition 3. 2.8. Unsigncryption
USC (skB, PKa , C )="On input (skB, PKA , C): If skB £ Z* or PKa £< P > return 1, Parse C into (c, h, s), If h, s £ Z* or c £ SPE return 1, Else I = sP - hPKA , R = skBI =( xR, yR), ct ^ K (R), m ^ Dct (c) , h' ^ H ( m | PKa I PKb I R),
If h = h' return m , else return 1." Public Verification
If controversy arises between signcryption senders and receiver, a trusted third party can solve the repudiation. The third party evaluates the following formula after signcryption receiver publishing ( R , C ). PV ( PKa , PKb , C, R )= "On input PKa , PKB , C, R): Parse C into ( c , h , s ), ct ^ K (R), m ^ Dct (c) ,
h' ^ H ( m | PKa I PKb I R),
If h = h' return true, else return 1."
3 Provable Security of S-ECSC
In this section, we will analyse the provable security of the signcryption in random oracle model, including confidentiality, unforgeability and non-repudiation.
3.1	Correctness of S-ECSC
Definition 3.1.1 Message space Message(skA, PKB ) is the set of all m associated to each private/public key pair ( skA , PKb ) output by GK (ID,1k ) for which SC ( skA , PKB , m ) never returns 1 . Definition 3.1.2 A signcryption scheme £ = ( GC , GK , SC , USC ) is correct if USC ( skB , PKA , C )= m for any private/public key pair
( skA , PKb ) output by GK ( ID,1k ), any message m e Message(skA, PKB ) , and any C *1
that might be output by SC ( skA , PKB , m ). Theorem 3.1.1 S-ECSC is correct for any private/public key pair ( skA , PKB ) output by GK ( ID,1 k ), any message m e Message(skA, PKB) and any C *1 that might be output by SC ( skA , PKB , m ).
Proof of correctness: Obviously, the signcryption scheme S-ECSC is correct if and only if
USC (SC (skA, PKb , m ))= m .
As per the formula in the scheme, skBI = skB (sP - hPKA )
= skB ( sP - hskA P ) = skB ( s - hskA ) P = skBrP = rPKB = R =( Xr , yR), ct ^ K (R). ^ m ^ Dct(c),
h' ^ H ( m | PKa I PKb I R), ^ h = h, m ^ USC (skB, PKa , C).
Thus USC ( SC ( skA , PKB , m ))= m , the short signcryption S-ECSC is correct, as desired.
3.2	Confidentiality of S-ECSC
Definition 3.2.1 Computational Elliptic Curve Problem (CECP). Let T = ( q , a , b , P , l, h ) be an elliptic curve and AC an attacker on CECP , CECP is defined as the following:
Experiment EXP^F (AC) d, e Z*, D = dP , E = eP, F e(P) ^ ACT (D, E),
If F = deP return 1 else return 0. Note that F = deP = dE = eD.	(1)
522 Informática 35 (2011) 521-530
X. Zhou et al.
Definition 3.2.2 Decisional Elliptic Curve Problem (DECP). Let T = ( q , a , b , P , l, h ) be an elliptic curve and AD an attacker on DECP , DECP is defined as the following:
Experiment EXPTDECP (AD) b ^$-{0,1},
If b =0 Sce0: d, e, f — Z*, If b =1 Sce1: d, e — Z*, f = de(mod l), D = dP , E = eP, F = fP, b' ^ ADT (D, E, F),
If b = b return 1 else return 0. Definition 3.2.3 DECP Oracle 0DECP . Let T =
(q, a, b , P , l, h) be an elliptic curve, DECP Oracle is defined as the following:
="on input (P , D, E, F) If D,E,F £< P > return 1, else If DCEP (D, E, F) =1 return 1, If DCEP (D, E, F) =0 return 0." Definition 3.2.4 Elliptic Curve Gap Problem (ECGP). Let T = (q , a , b , P , l, h ) be an elliptic curve and AECG an attacker on ECGP , let's consider the following experiment:
Experiment EXPECGP (AECG) d, e Z*,
signcryption oracle and returns a bit. We consider the following experiment:
Experiment EXP'^™2(ASC)
(K, H, T) ^ GC (1k) ,(skA, PKa ) ^ GK (A,1k), (skB, PKb ) ^ GK (B,1k),
C ' ^ SCskA,pkb (LFH, b)), b ^ {0,1},
b' ^ ASCSC'kAPKB (LR("b)),USC(skA ,pkb ,)
If ASC queried USC (skA, PKB,) on a signcryption text previously returned by SCskA pkb (LR(m0,m1,b)) then return 0,
If b' = b return 1 else return 0.
The IND-CCA2 advantage of ASC is defined as
8( k) = AdV£-cca2 (ASC)
= Pr (EXP1GGCcCca2(ASC) =1). (4)
F = fP ^ AECGtt '"'(d,e), If f = de (mod l) return 1 else return 0.
The ECGP advantage of AECG is defined as
AdvECGP (AECG) = Pr (EXPTECGP (AECG) =1). (2) Hypothesis 3.2.1 (ECGP is hard). Given elliptic curve T and secure parameter 1 k , the probability of solving ECGP in time t is £(1k ,T) which is negligible, that is £(1k,T) =Pr [ 1k ,d,eZ*,
Q ^ xP : EXPTECGP (AECG) =1]. (3) Definition 3.2.5 Left-or-right signcryption oracle. Let £ = ( GC , GK , SC , USC ) be a signcryption scheme, a left-or-right signcryption oracle is defined as follows.
Oracle SCskApkb (LRK,mx,b)) = "On input (m0, m1):
b e {0,1},m{),mx e SPm, C ^ SC (skA, PKB, mb),
Return C."
Definition 3.2.6 Confidentiality of signcryption. Let ASC be an algorithm against the confidentiality of signcryption scheme £ that has access to a left-or-right
A signcryption scheme is indistinguishable under adaptive chosen cipher-text attack if the IND-CCA2 advantage of any attacker ASC with reasonably restricted resources (time-complexity, frequency and length of queries) is negligible.
Definition 3.2.7 Left-or-right Encryption Oracle. Let Y = ( E , D ) be the symmetric encryption algorithm in the signcryption scheme, a left-or-right encryption Oracle is defined as:
Oracle Ea (LR(m0, m1, b)) ="On input (m0, m1): b e {0,1},m{),mx e SPm, C ^ Ea (mb),
Return C."
Definition 3.2.8 Passive Indistinguishability. Let AI be an algorithm against the passive indistinguishability of symmetric encryption scheme Y , which has access to a left-or-right encryption oracle and returns a bit. We consider the following experiment:
Experiment EXPYp (AI) C' ^ Ea (LR(m0,m1,b)), b ^ {0,1},b'^ AIe'(lr("b)),
If b = b return 1 else return 0.
The pi advantage of AI is defined as
v ( k) = AdvYpi (AI) = Pr (EXPYpi (AI) =1). (5)
An encryption scheme is passively indistinguishable if the pi advantage of any attacker AI with reasonably restricted resources (time-complexity, frequency and length of queries) is negligible.
Hypothesis 3.2.2 (Ideal Hash Function). Hash function has the property of Random Oracle. Namely, the outputs of hash function are randomly and uniformly distributed. Theorem 3.2.1 If there exists an algorithm ASC against the IND-CCA2 property of signcryption scheme £ in time t with non-negligible advantage 8 (k) , using qSC
SHORT SIGNCRYPTION SCHEME FOR.
Informatica 35 (2011) 521-530 523
queries to its signcryption oracle and (qH , qM) queries
to its random oracles. Then we can thus formulate an AECG attacker on ECGP with non-negligible advantage
E ( 1 , T ) in time t' , using qSC queries to its
signcryption oracle and qSC + qH queries to its random oracles.
Proof of confidentiality: In our proof, the random oracles K and H are replace by the random oracle simulators with two types of "query-answer" lists. For example, Sim_K simulates random oracle K with two
types of "query-answer" lists LK and L^ . LK consists of simple "query-answer" ( R , a ) entries from K ,while LL^ consists of special input-output entries ( PKb \1 Q, \1 (?, a) ) which implies a = K(QskB)
with the implicit input QskB stored and denoted as "?". Sim_K(LK, R) ="on input (LK,R): If 1 ^ DECP (D, PKb , R) return 1, Else if 1 ^ DECP (Q,, PKb , R) return a,,
//there is an entry (PKB \1 Q, \| (?, ai)) in L^ Else if R = Ri , return ai //there is an entry
(Ri a) in LK
G ^
Else G ^
-{0,1}
Lk (1')
R ^ R,
Add (R, ,ai) into Lf ."
If EXP'sG^cca2 (ASC) makes queries to random Oracle OH , AECG will reply with simulator Sim_H .
Sim_H(Lh , K) ="on input (LH, K ): // K =( m \ PKa II PKB \l R)
If 1 ^ DECP (D, PKb , R) return 1,
Else if 1 ^ DECP (Q,, PKb , R) and m \
PKA II PKB = mt \ | (PKA )i 11 (PKB )i
return ai //there is an entry ( Q, \ | ( mi \
H
h +
-{0,1}^ \c ^ E<(m),
-Z*,^ Z*,
Q ^ sP - hPKA, Q, ^Q, ai ^ a , mi ^ m, hi ^ h, Add entry Qi \I (?, ai )into Lf , Add entry (m \| PKA \| PKB \| (?, ht)) into LH2 , C = (c, h, s) and return C ."
If EXPltGd(-cca2(ASC) makes queries to OUSC . AECG will reply with simulatorSim_USC . Sim USC(LK, Lh , D, PKA, PKB, C) = "On input (LK, LH, D, PKA, PKB, C): Parse C into (c, h, s), Q ^ sP - hPKA , If Q = D return 1,
If 3 (R ,ai) in LK s.t. 1 ^ DECP (Q,, PKb , R ) or 3 Q, \| (?, a,) in Lk2 s.t. Q, =Q
ThenG' ^ G
Else G ^
-{0,1}
Lk (1')
Q, ^ Q ,G ^ g' ,
(PKA )i II (PK, )i || ?)
Else if h = h. , return h. //there is an entry (h., h ) in L
Else h — Z/, h. ^ h, Add (h., hi) into LH ." If EXP'sG^cca2(ASC) makes queries to random Oracle OSc , AECG will reply with simulator Sim_SC. Sim_SC (LK, LH, PKA , PKB, m) = "On input (LK, LH, PKA, PKS, m): // h =( m ||
PKA II PKB || R)
Add entry Q, \| (?, ai) into Lf , m ^ Da (c), If 3 (K,, h) in LH s.t. 1 ^ DECP (Q,, PKb , R ) or 3 (Q, \|( mi \| (PKa ), \I (PKb) \I ? ), h,) in LH s.t. Q, =Q , mt = m , (PKA),. \| (PKb)i =(PKa) II (PKb),
Then h' ^ hi, Else Q. ^ Q , (PKa ) || (PKb ) ^ (PKa ), \l (PKb). , mt ^ m, ht Z*,
Add entry ( Q. \| (m,. \| (PKA \| PKB),. \|
(?, h )) into LH ,
If h = hi return m , else return 1."
Based on Theorem 3.2.1 we formulate an AECG attacker on ECGP; apparently contradicting Hypothesis 3.2.1, thus prove the confidentiality of the improved signcryption scheme.
The AECG attacker on ECGP is formulated as follows.
AECG (T, D, E )= "On input (T, D = dP , E = eP): h\s* Z*,PKa ^ (h*)-VP + D), Z *,
PKB ^ E, G*
C *= (c*, Ii, sS) ^ SC,
s'A ,PK,
(LR (m0, mj, b)),
522 Informática 35 (2011) 521-530
X. Zhou et al.
// c ^ E , (mb) , and the random oracle
queries O are replaced with random oracle simulator Sim_O .
If SCsk PKb has ever queried Sim_K(R) = 1 ,
Halt and return R , If SCsk PKb has ever queried Sim_# (h) = 1 ,
Halt and return h (the rightmost | R bits of h),
EXP^C-cca 2( ASC ) = "
// random oracle queries O are also replaced with random oracle simulator Sim_O .
If EXP'sGccca 2( ASC) has ever queried Sim_K (R) = 1,
Halt and return R , If EXP'sGccca 2( ASC) has ever queried Sim_# (h) = 1,
Halt and return h (the rightmost | R bits of h),
b ^ EXPisGd(fcca2 (ASC ),
Return R."
Let ASC be an attacker against IND-CCA2 security of signcryption in time t , using qsc queries to its
signcryption oracle, qusc queries to its unsigncryption
oracle and (qk , qh) queries to its random oracles. AECG is an attacker against ECGP security of elliptic curve in time t' , using qODECP queries to its DECP
Oracle OT>ECP . AI is an attacker against PI security of the
symmetric key encryption in time t " . From the AECG algorithm formulated above, the following bound holds. More details about the probability proof of the theorem can be found in [5, 12, 13, 14].
AdvGr2 (t , qSc, quSc, qk , qh) < 2 Adv^CGP
(t' , qODECP) +2 Advp (t" )+
q (qk + qh + qsc+qusc+2) + qh+2qusc (6)
qsc (	2lK (!k H	) 2LK ^H '(D)
^ AdvlGcca2(t ,qsc,qusc,qk,qh)/2-
q (qk+qh+qsc+qusc+2)
Hsc (	rK^k^	)
^ q (qk+qh+q.c+qusc+2) qh + 2q,sc .
^ qsc (--7K-T,-)--KT— is
2L
2L
2L

qh +?qkusc - AdvYpi (t" )
2lK (1k)	1
< AdvETCGP (t' , qODECP).
(7)
As ASC and AECG are reasonably resource bounded,
negligible.
And with the assumption Y is passive indistinguishable, AdvYp1 (t " ) is negligible too.
y sgc (t, qsc, qusc, qk, qh)/2 <
^ Advf -cca2
AdvT	( t , qODECP ).
(8)
On account of all the above analyses, if the IND-CCA2security of signcryption will be broken by ASC with non-negligible advantage, so will the ECGP security of elliptic curve by AECG with non-negligible advantage. Therefore, S-ECSC achieves confidentiality in the IND-CCA2 model, as desired.
3.3 Unforgeability of S-ECSC Definition 3.3.1 Unforgeability of Signcryption. Let £ = (GC , GK , SC , USC ) be a signcryption scheme, and let A be an algorithm that has access to a signcryption oracle and returns a pair of strings. We consider the following experiment:
Experiment EXP^-cma (A) (skA, PKa ) ^ GK (A,1k), (skB, PKb ) ^ GK (B,1k), (m , C ') ASGC(skA,pKB,) (PKa , PKb ).
If the following are true return 1 else return 0:
1.	m ^ USC (skB, PKa , C),
2.	m e Message (skA, PKb ),
3.	m is not a query of A to its signcryption oracle.
The UF-CMA advantage of A is defined as
AdvfGCcma (A) = Pr (EXPG-cma (A) =1). (9)
To be specific, the UF-CMA advantage can be concluded as a function s(k) defined by
e(k) = Pr [ (skA, PKA ) ^ GK (A,1k), (skB, PKB ) ^ GK (B,1k),
(m , C') ASGC(skA,pKB,) (PKa , PKb):
m ^ USC (skB, PKa , C')]. (10)
A signcryption is un-forgeable under chosen message attack if the UF-CMA advantage of any attacker A with reasonably restricted resources (time-complexity, frequency and length of queries) is negligible. Hypothesis 3.3.1 (ECDLP is hard). Let T be an elliptic curve, and let A be an algorithm that has access to a elliptic curve oracle and returns a string. We consider the following experiment:
Experiment EXPtecdlP (A) x Z*, Q ^ xP, x'^ AT (P, Q).
SHORT SIGNCRYPTION SCHEME FOR.
Informatica 35 (2011) 521-530 523
If x' = x return 1 and return 0 otherwise. The ECDLP advantage of A is defined as
AdvETCDLP (A) =Pr (EXPtecdlp (A) =1). (11)
Given elliptic curve T and secure parameter 1k , the
probability of solving ECDLP in time t is 5 (1k , T ) which is negligible, that is
5 (1k,T)= Pr [1k,xZ*,
Q ^ xP : EXPTECDLP (A) =1]. (12) Definition 3.3.2 Gap Elliptic Curve Discrete Logarithm (GECDL). Let T = (q , a , b , P , l, h ) be an elliptic
curve and AGL an attacker on GECDL , OT>ECP is DECP Oracle, let's consider the following experiment: Experiment EXPTGECDL (AGL )
d ^
Z , D ^ dP
dagLTt UJ(D),
If d' = d return 1 else return 0. The GECDL advantage of AGL is defined as
AdvGECDL (AGL) =Pr (EXPGECDL (aAGL) =1). (13)
Hypothesis 3.3.2 (GECDL is hard). Given elliptic
curve T and secure parameter 1k , the probability of solving GECDL in time t is negligible, that is
5 (1k, T )= Pr [ 1k, d Z*, d' ^
ODECP ( )
AGLTT u;(D),EXPTGECDL (AGL) =1]. (14)
Proof of unforgeability: Let ASC be an attacker against UF-CMA security of signcryption executing in
time t , using qsc queries to its signcryption oracle ,
qusc queries to its unsigncryption oracle and (qk , qh ) queries to its random oracles. AGL is an attacker against GECDL security of elliptic curve executing in time t' ,
using qoDECP queries to its DECP Oracle OT>ECP. From
the algorithm formulated above, the following bound holds. Similarly, more details about the probability proof of the theorem can be found in [12, 13, 14].
AdvfGccma (t, qSc, qusc, qk, qh) <
2^AdvGECDL ( tqoDECp) +
(
qSc (q+q+qSc)+q+1
2Lk (1k H
). (15)
As ASC is reasonably resource bounded.
qSc (qk+qh+qSc)+qh+1,

2L
is negligible
^ Advi0cma(t,qSc,qUSc,qk,qh)
< 2^Adv0ECDL ( t', qoDECP) . (16)
If the UF-CMA security of signcryption will be broken by ASC with non-negligible advantage, so will the
GECDL security of elliptic curve by AGL with non-negligible advantage. Therefore, S-ECSC achieves unforgeability in the UF-CMA model, as desired.
3.4 Nonrepudiation of S-ECSC Definition 3.4.1 Non-repudiation of signcryption. It is computationally feasible for a third party to settle a dispute between signcryption sender and receiver in an event where sender denies the fact that he is the originator of signcryption.
Definition 3.4.2 Relation Map. A relation is a map defined as
«H,% :{0,1}* x {0,1}* ^ {0,1}. (17) For every string x e{0,1}* , random oracle H e 2" andE, % e {0,1}*, it satisfies
«H,%(x, x) = «H,%( x,0*) = 0. (18)
Besides, «H % must be computable by a deterministic
polynomial time algorithm AH (x, y, E,%) . A malleability adversary s is a pair of probabilistic polynomial time algorithms (P, Q) with access to
random oracle H e 2".
The security notion of non-malleability for encryption scheme was introduced by Dolev, Dwork and Naor[15]. In this section, we generalize non-malleability into a more comprehensive security notion applicable to signcryption as well.
Definition 3.4.3 Non-malleability of Signcryption. A signcryption scheme £ = ( GC , GK , SC , USC )is non-malleable if any adversary can not by witnessing signcryption generating of a message m or querying a signcryption oracle, produce the signcryption text of a related message m'.
To be specific, a signcryption scheme is non-malleable if for every relation « and every malleability adversary s = (P, Q) , there is a deterministic time
algorithm Q' so that |r(k) - r*(k)| defined as follows is negligible.
r(k) = Pr [ H ^ 2" ;(SC, USC) ^ K(1k ); % ^ PH (SC); x ^ %H (1k ) ; p ^ SCH (x); p' ^ QH (SC, %, P): «H,% (x, USCH (P') = 1)], (19) r* (k) = Pr [ H ^ 2" ;(SC, USC) ^ K(1k ); % ^ PH (SC); x ^ %H (1k ); P* ^ Q'H
(SC, %): «H,% (x, USCH (P*) = 1) ]. (20)
Theorem 3.4.1 The short signcryption scheme S-ECSC achieves non-repudiation security.
Proof of non-repudiation: In signcryption schemes, unforgeability implies non-repudiation if there is no duplication of the signcryption text. If the signcryption scheme is forgeable or malleable, the signcryption generator will have opportunity to repudiate.
522 Informática 35 (2011) 521-530
X. Zhou et al.
\Lk (14 )
and
In S-ECSC, the map K : E(Fq) ^ {0,1}L
H : {0,1}* ^ Z* are both unique, distinct ( mx , r )
and( m2 , r ) will generate different signcryption text
C =( c , h , s ). Furthermore, the scheme can be reinforced by state padding. The state padding not only ensures different signcryption text for distinct ( m1 , r )
and ( m2 , r ), but for the same original message ( m , r ) with different state information. Thus, the above signcryption scheme satisfies: as to |r(k) — T*(k)| for
every c there is a kc such that |r(k) — r*(k)| < k c for
every k > kc . Thus the signcryption text C produced by
SC (skA , PKb , m ) is not duplicable, and with the unforgeability proof of S-ECSC in UF-CMA model in section 3.3, we can come to the conclusion that S-ECSC achieves non-repudiation security, as desired.
4 Efficiency of S-ECSC
In this section, the short signcryption scheme S-ECSC will be compared with other typical schemes including discrete logarithm based signcryption SCS [5], B&D [16], KCDSA [17], SC-DSA [18] and RSA based signcryption TBOS[\9] and elliptic curve based scheme ECSCS[20] and ECGSC[21].
In these schemes, such computing as modular exponential, modular inverse and elliptic curve addition ,elliptic curve scalar multiplication should be taken into comparison for computing complexity, while computing cost of modular addition, modular multiplication, hash, symmetric encryption/decryption are negligible. To ensure the security of the basic cryptographic primitives, the minimum security parameters of these cryptosystems recommended for the current practice are as follows: for
DLP, |p| =1024bits, |q| =160bits. For RSA, \N\ =1024bits; for ECC, |q| =131bits (79, 109 may also
be chosen), |/| =160bits. The block length of the block
cipher is 64bits. The length of secure hash function is 128bits.
ECGSC	2kP	2kP+11	3kP+1 I	0	2kP+1 I	|/|+ |LH (■)!+ 2|q|
S-ECSC	2kP	1kP	2kP+1 I	0	2kP+1 I	|D (■) |+|h|+ 2\p\
Schemes	GC+GK	SC	USC	EC	PV	Length of C
SCS	2E	1E+11	2E	/	/	|D (■) |+|KH (■)| + |q|
B&D	2E	2E+11	3E	0	2E	|D (■) |+ |h|+ |q|
KCDSA	2E	2E	3E	Save r,s or 3E	2E	|D (■) |+ |h|+ |q|
SC-DSA	2E	2E+21	3E+11	Save r,s or 2E+1 I	2E+1 I	|D (■) |+2|q|
TBOS	2E+2I	2E	2E	0	2E	
ECSCS	2kP	1 kP +1 I	2kP	/	/	|D (■) | + |h|+ |n|
Table 1: Comparison of computing and communication cost
Notes of notations: 1. GC denotes the common parameters generation algorithm, GK denotes the keys generation algorithm; SC denotes the signcryption algorithm; USC denotes the unsigncryption algorithm; EC denotes the extra computation to accomplish public verifiability; PV denotes the public verification by a third party. Length of C denotes the length of signcryption text. 2. E denotes modular exponential; I denotes modular inverse; KP denotes scalar multiplication on elliptic curve. / denotes there is no relevant computation. 3. |D ( ) |denotes the block length of block cipher, |h| denotes the outputs length of secure hash function, |KH ( )| denotes the length of key hash function in SCS, the same as |h|, |LH (.)| denotes the length of hash function with long message digest, much larger than |h|.
Remark 1. (Comparison with DLP based signcryption schemes). SCS is the fastest scheme in all of the four DLP based schemes (SCS, B&D, KCDSA and SC-DSA). Based on the result of Koblitz and Menezes [22], the computing cost in key generation in our scheme is 1/8 of that in SCS; signcryption operation in ours is about 1/8 of that in SCS, and unsigncrption is about 1/8 of that in SCS. To sum up, S-ECSC reduces about 87%computating cost compared with SCS.
Remark 2. (Comparison with RSA based signcryption scheme). As per the result of [22], the computing cost in key generation in our scheme is about 1/8 of that in TBOS; signcryption operation in ours is about 1/16 of that in TBOS, and unsigncrption is about 1/8 of that in TBOS, achieving a total 89%computating cost reduction over TBOS.
Remark 3. (Comparison with other ECC based schemes). The computing cost in key generation are the same; signcryption cost in ours is slightly lower than that in ECSCS while unsigncrption of ECSCS is slightly lower than ours, total resulting an equal computing cost, yet ECSCS proves to be unsuitable for public verifying. Although ECGSC is publicly verifiable, its computing cost in signcryption and unsigncryption is much larger than S-ECSC, resulting in a much higher total computing cost.
Remark 4. (Comparison of communication cost). As per the comparison of signcryption text length, except for RSA based TBOS signcryption, S-ECSC has the lowest communication cost in Elgamal type signcryption schemes.
Therefore, we may come to the conclusion that our short signcryption scheme S-ECSC has the highest efficiency and the lowest communication cost in all of the publicly verifiable schemes.
SHORT SIGNCRYPTION SCHEME FOR.
Informatica 35 (2011) 521-530 523
5 Application of S-ECSC in Secure Communication of IOT
In order to achieve confidentiality and integrity for secret key in the Internet of things, a secure channel should be established for the distribution and transmission in key management schemes. Meanwhile, the special network environment in IOT, such as wireless connection, microterminals and restricted resources, makes it necessary to design schemes of high efficiency which can fulfil the same function with much smaller computing and communication cost than traditional schemes. With its superiority in computing and communication, S-ECSC greatly improves the efficiency in key management in IOT in terms of key distributing time and bandwidth resources and better satisfies the requirement of secure protocols in key management. In this section, we will take the key management schemes in [23,24,25] as an example and propose a key applying and distributing scheme in key management of IOT based on S-ECSC. With this S-ECSC based scheme, we analyse the method and importance to apply S-ECSC in secure wireless communication for the Internet of things. The key applying and distributing protocol in key management of IOT based on S-ECSC is as follows.
(1)Initializing
PKG selects the system parameter, including the parameters in S-ECSC.
skA g Z* , PKa = skAP * O , ( skA , PKa ) is the private/public key pair for one of the distributed terminals A. skB g Z* , PKB = skBP * O ,
( skB, PKb )is the private / public key pair of PKG.
(2)	Key applying
Stepl: Terminal A encodes the applying request data {IDa, Message} into plaintext m g Message
( skA , PKB ), and applies the signcryption algorithm
on m .
C ^ SC ( skA, PKb , m ).
Then signcryption text C will be transmitted to PKG.
Step2: PKG applies the unsigncryption algorithm on signcryption text C.
m ^ USC ( skB, PKa , C ).
Thus, PKG recovers plaintext m , and simultaneously fulfils authentication on identity of terminal A and examines the integrity of message m .
(3)Key	generating and distributing
Stepl: PKG generates secret key k g Message ( skB , PKA ) with the key generating
algorithm KG(lk ) , and applies the signcryption algorithm on k .
C ^ SC ( skB, PKa , k ).
Then the signcryption text C will be transmitted to terminal A .
Step2: Terminal A applies the unsigncryption algorithm on C'.
k ^ USC (skA , PKb , C').
Thus, A recovers secret key k , and fulfils authentication on identity of PKG and examines the integrity of secret key k .
With the application of S-ECSC in key applying and distributing, the above scheme achieves secure and efficient transmission of terminal secret key via the public channel of IOT. The scheme fulfils the integrated functions of encryption and digital signature in a single step and simultaneously achieves confidentiality, integrity and non-repudiation for the secret terminal key and other signcrypted message; whereas, the computing and communication cost is significantly smaller than traditional schemes.
6 Conclusions
The study of signcryption algorithms suitable for IOT network environment and its application in IOT security schemes is an important direction in cryptography; it is more of a requirement from the rapid development of the Internet of things than just a requirement from the theoretical or applied cryptography research. In the paper, we propose a publicly verifiable short signcryption scheme S-ECSC suitable for secure communication in the Internet of things; and prove the provable security of S-ECSC under the Random Oracle model, including confidentiality, unforgeability and non-repudiation security. At last, we take key generating and distributing protocol for different terminals of distributed key management in IOT as an example, and analyze the method and importance in the application of S-ECSC into secure protocols in IOT.
Compared with other typical discrete logarithm, RSA and elliptic curve based signcryption schemes; S-ECSC achieves about 87% reduction in computing cost than DLP signcryption schemes and about 89% reduction compared with RSA schemes. And it has the lowest communication cost in the Elgamal type schemes. Therefore, security schemes based on S-ECSC are most suitable for such circumstances as with restricted computation ability and integrated space, circumstances with limited bandwidth yet requiring for high-speed operation. Besides, the computational problems ECGP and GECDL in the paper can also be basis of security proof for other elliptic curve based schemes.
Acknowledgement
The authors should thank the anonymous reviewers for their constructive advice and comments to the paper, with which we can greatly improve our work.
References
[1] ITU(2005). ITU Internet Report 2005: The Internet of Things. ITU.
522 Informática 35 (2011) 521-530
X. Zhou et al.
[2]	Atzori L,Iera A,Giacomo M(2010). The Internet of Things : a survey. Computer Networks, pp.27872805.
[3]	EpoSS (2010).Internet of Things in 2020:Roadmap for the Future.EpoSS.
[4]	Zhu Hongbo,Yang Longxiang,Yu Quan(2010). Investigation of Technical Thought and Application Strategy for the Internet of Things . Journal of Communication, pp. 2-9.
[5]	Zheng Y(1997). Digital signcryption or how to achieve cost (signature &encryption) << cost (signature) + cost(encryption). Advances in Cryptoloty-CRYPTO'97, Lecture Notes in Computer Science vol.1294,Springer-Verlag, Berlin ,pp.165-179.
[6]	Zhang Chuanrong. Zhang Yuqing . Li Fageng and Xiao Hong( 2010). New Signcryption Algorithm for Secure Communication of ad hoc Networks. Journal of Communications, pp.19-24.
[7]	Luo Ming, Zuo Chunhua and Wen Yingyou (2010).Signcryption-based fair exchange protocol. Journal of Communications, pp.87-93.
[8]	Kim H, Song J, Yoon H(2007). A practical approach of ID-based cryptosystem in ad hoc networks. Wireless Communications and Mobile Computing. pp.909-917.
[9]	Li F G, Hu Y P, Zhang C R(2007). An identity-based signcryption scheme for multi-domain ad hoc networks. ACNS 2007, LNCS 4521, SpringerVerlag, Berlin , pp.373-384.
[10]	Chen, Weidong. Feng Dengguo(2005). Some Apiplications of Signcryption to Distributed Protocols. Chinese Journal of Computers, pp.14211430.
[11]	Kamat P, Baliga A, Trappe W(2006). An identity-based security framework for VANETs. VANET'06. Los Angeles, California, USA, pp.9495.
[12]	Baek J, Steinfeld R and Zheng, Y(2002). Formal Proofs for the Security of Signcryption. Public Key Cryptography'02, Lecture Notes in Computer Science vol.2274, Springer-Verlag,Berlin,pp.80-98.
[13]	Shoup V (2004). Sequences of Games: A Tool for Taming Complexity in Security Proofs , International Association for Cryptographic Research (IACR) ePrint Archive: Report 2004/332.
[14]	Bellare M and Rogaway P (2004).The Game-Playing Technique, International Association for Cryptographic Research (IACR) ePrint Archive: Report 2004/331.
[15]	Dolev D, Dwork C and Naor M (1991).Non-malleable cryptography. 23rd ACM Symposium on Theory of Computing. IEEE ,New York.
[16]	Bao, F and Deng R H(1998). A signcryption scheme with signature directly verifiable by public key. Public Key Cryptography'98, Lecture Notes in Computer Science vol.1431, Springer-Verlag, Berlin,pp.55-59
[17]	Yum D H and Lee P J(2002). New Signcryption Schemes based on KCDSA. Proceedings of the 4thInternational Conference on Information Security and Cryptology, Seoul, South Korea, pp. 305-317.
[18]	Shin J B, Lee Kand Shim K(2003). New DSA-Verifiable Signcryption Schemes. Proceedings of the 5th International Conference on Information Security and Cryptology, Seoul, South Korea, pp.35-47.
[19]	Malone-Lee J and Mao W (2003). Two birds one stone: Signcryption using RSA. Topics in Cryptology - Cryptographers'Track, RSA Conference 2003, Lecture Notes in Computer Science vol.2612, Springer-Verlag, Berlin,pp.210-224.
[20]	Zheng Y and Imai H(1998). How to construct efficient signcryption schemes on elliptic curves. Information Processing Letters, pp.227-233.
[21]	Han Yiliang, Yang Xiaoyuan and etc(2006). ECGSC:Elliptic Curve Based Generalized Signcryption. Proceedings of The 3th International Conference on Ubiquitous Intelligence and Computing, Springer-Verlag, Berlin,pp.956-965.
[22]	Koblitz N , Menezes A and Vanstone S(2000). The state of elliptic curve cryptography. Designs, Codes and Cryptography, pp.173-193.
[23]	Li G S, Han W B(2005). A new scheme for key manegement in ad hoc networks. ICN2005, LNCS 3421,Springer-Verlag, Berlin,pp.242-249.
[24]	Gu Jing-jing,Chen Song-Can,Zhuang Yi(2010). Wireless Sensor Networks-Based Topology Structure for the Internet of Things Location.Chinese Journal of Computer ,pp.1548-1556.
[25]	Chen Juan,Fang Binxing,Yin Lihua(2010). A Source-Location Privacy Preservation Protocol in Wireless Sensor Networks Using Source-Based Restriced Flooding.Chinese Journal of Computer, pp.1736-1747.