Int. J. Communications, Network and System Sciences, 2011, 4, 622-625
doi:10.4236/ijcns.2011.410075 Published Online October 2011 (http://www.SciRP.org/journal/ijcns)
A Threshold Signature Scheme Based on TPM*
Zhi-Hu a Zhang1, Si-Rong Zhang1, Wen-Jin Yu1, Jian-Jun Li1, Bei Gong2, Wei Jiang2,3,4
1China Tobacco Zhejiang Industrial Co. Ltd, Hangzhou, China
2College of Computer Science, Beijing University of Technology, Beijing, China
3State Key Laboratory of Information Security, Institute of Software, Chinese Academy of Sciences, Beijing, China
4Key Laboratory of Information and Network Security, 3rd R esearch Instit ute, Minist ry of P ubli c Se curi ty, Shanghai, China
Received August 12, 2011; revised August 27, 2011; accepted September 29, 20 1 1
Abstract
For the traditional threshold signature mechanism does not considers whether the nodes which generate part
signature are trusted and the traditional signature strategy doesn’t do well in resisting internal attacks and
external attacks and collusion attacks, so this paper presents a new threshold signature based on Trusted
Platform Module (TPM), based on TPM the signature node first should finish the trust proof between it an
other members who take part in the signature. Using a no-trusted center and the threshold of the signature
policy, this strategy can track active attacks of the key management center and can prevent framing the key
management center, this strategy takes into account the limited computing power TPM and has parameters of
simple, beneficial full using of the limited computing power TPM.
Keywords: TPM, Threshold, No Trusted Center, Bilinear Map
1. Introduction
Rapid development of the computer and network tech-
nology has made human society into the information age.
The rapid popularization of the Internet and the rapid
progress of internet technology have greatly promoted
the development of the productive forces. Now the elec-
tronic commerce, the electronic government affairs and
other services are widely used, the problem of informa-
tion security has become more and more prominent, the
information disclosure, the network crime and system
invaded events are increasing day by day. Therefore,
how to block network security hole, eliminate security
concerns and protect the important or sensitive informa-
tion has been paid highly attention by academics and
even the whole society. For the Internet is distributed
environment, it is easy to appear a phenomenon that a
single node is malicious attacked, and a network node is
attacked , it may cause the security of the whole network
system security is destroyed. So, if the important infor-
mation or important operation is stored or finished by a
single node, it will increase security risk. In network en-
vironment, people may suspect that a given network
server is secure and reliable, but it can still be reasonable
to think that most servers are normal. Therefore, based
on the assumption, trust entities can be structured, that
most the network nodes of a group are secure and reli-
able. The important information storage or the execution
of an important operation can be completed through co-
operation of the members of the group.
Threshold solution provides a good solution for the
above problems. The threshold cryptosystem is a rela-
tively new research field, it main concerns that a cryp-
tography operation once finished by one entity is scat-
tered to a group consisted of many entities to complete,
threshold signature is an important part of the study of
threshold cryptography, in 1991 threshold signature is
presented by Desmedt and Frankel presented [1], since
then many kinds of threshold signatures have come into
true [2-4]. In the threshold signature scheme, a private
key is shared by n users in the group, and not as the
normal signature that the private key is only held by a
single user. So when it needs to sign a given message,
each user needs to produce part signature, then the part
signatures are combined to generate a whole signature. In
1994 the Ham puts forward two threshold group signa-
ture based on discrete logarithm scheme [5,6], one
scheme has a trusted center the other has no trusted cen-
ter, but the traditional threshold signature mechanism
does not considers whether the nodes which generate
part signature are trusted, so this paper presents a new
*Correspondence Authors: Bei Gong and Wei Jiang.

Z.-H. ZHANG ET AL.623
threshold signature based on Trusted Platform Module
(TPM), the signature node first prove itself is trusted, and
then it can generate signature, the scheme presented in
this paper don’t need trusted center, and according to
TPM limited ability, the scheme is based on the identity
of the TPM, the scheme is based on discrete logarithm
and also don’t need Trusted center, comparing with tra-
ditional threshold signature this scheme has a higher ef-
ficiency.
2. Preliminaries
2.1. Computational Diffie-Hellman Problem
Given group and
Gg 
g
is the generator of
,
Gg ,
ab
g
g,,
p
ab Z, if is not public, ,ab
ab
g
is difficult to compute.
2.2. Bilinear Groups
Group 21 and group 22 is two
additive groups, is a large prime number. The dis-
crete logarithm in group 2 and 1 is difficult to
solve.
Gg 
pGg
 
G
p
G

is computable reconstruction from 2 to 1 G.
Group 12
is a pair of bilinear group if and only if
satisfying the following properties:
G
,GG
1) Computable bilinear: For any 1 G

，2 G


,
there exists computable mapping: There exists comput-
able mapping12 ( is a cyclic group
whose order is ) satisfying 3ab
e:GG G
q3
G
e,

e

,
ab

   .
2) Non-degenerative: For the generators on the group
12
,
g
g, .

12
e,gg 1
2.3. Shamir Threshold Scheme
Given secret
s
, it is divided to parts, each part is a
subkey. Each part of the information is called a subkey
or is the shadow, which is owned by a sharing member.
If there are or more than members,
n
k k
s
can be re-
constructed，less than k member,
s
can not be re-
constructed. This scheme is


kn, secret segmentation
threshold scheme, is the threshold value.
k
Given a limited domain


GF q , is a large primer,
and , q
1qn
s
is a random number in




0GF q,
and coefficients
1k,
0,1, 1
L
kare also in aa a 

0RGF q, . So a polynomial
can be constructed in

,n

1, 2,i1k


0GF q, we can construct the
polynomial, the polynomial is

01 1
1 k
k
f
xaax ax


 
,,,
ii ik
pp p

the subkey of members
12 is n
f
i, every members 12
can construct k,,,
iii
p


 
 
1
11
1
22
01 1
1
01 11
01
................
k
k
k
kk
k
kk
k
aaia afi
aaia ifi
aaia ifi







1
2

 

 



 







1
l
ilk

 is different e ach other, so by usin g

 


11
mod
k kl
j
jljl
lj
xi
f
xfiii




q
,


0sf

can be constructed.
3. Signature Scheme
3.1. Set up
Given




,, ,
ab
GG

is order addition group and
multiplication grou p, p
a
g
is the generator of,
e: aa b GG G

 is bilinear map,

*
1:0,1 a
H
G,

**
,1
12
:0
p
H
GZ are no collision hash fun c tion.
3.2. Units
Signature node will send own node state information and
configuration information of platform to other node to
prove whether it is can be trusted, if it is trusted, the sig-
nature process can be continued, if it is not trusted, the
signature process will be terminated, at the same time
signature node request other nodes to send their configu-
ration information and state of their platforms, signature
node needs to judge whether other nodes’ configuration
state information meet its own security strategy, this trust
proving process is a two-way process, signature nodes
need to evaluate the credibility of the other nodes, while
the other nodes need to evaluate the credibility of the
signature, after completing two-way evaluation the sig-
nature node can continue the signature operation, trust
proving process is shown as the following (Figure 1).
3.3. Equations
1) For in the signature node sub set
i
U


,
n
UU U
i
N12
,,U
i
U, first selects a random number
, then sends i
U


,,
needj j
PCRSML
1i
mN to ,
j
Uij

,
, needj is the configuration value
and measurement value of that asks
,
needj j
PCR SM
,
j
Ui
SML
j
L,
j
Ui ji U

to send to .
i
2) When U j,Ui
j

receives 1needi ji mN ,
it distills jj and judges whether
meets the security stagy of

,RSML,PC
,
j
Uij
,SML
need
PCR
j
ML,
needj
PCR S

, if
does not meet the security stagy of ,
needj
PCR S
,
j
Ui jj
ML

, the signature process will be terminated, else
k
pp
s
by using the following equati ons:

Z.-H. ZHANG ET AL. 624
,,,,,, j jneedijneedi SMLSPCRPCR NAIKSML
, , i needjj NPCR SML
,,,, iij i SPCRN AIKSML
jU
i U
Figure 1. Two-way trust evaluation.
,
j
Ui j selects a random number
j
N
j and reads PCR from the local TPM, then uses AIK to gener-
ate the signature ,
j
Ui


A
c1,
I
Kj CRNSS and reads
the measurement log ignmP
j
SML 
,
jn n
CR SML
, at last will send
jedi encry-
pted by conversation key
,
j
Ui
,AIK j

,, edi ML SP
2
m S, ,
ee j
PCR N
K
to i, i are
the configuration information and measurement log of
the platform which ask to provide.
U
j
,
needi
R
,
j
Ui
PC
iU
SML
U 3) When receives
i
,,S

2,, ,, jneejejdin edi
mSMLPCRPCRNAIK SML,
needi j
PCR SML
U,
needi j
PCR SML
U N
i
U

, it ju-
dges whether meets the security stagy
of i, if does not meet the security
stagy of i
U, the signature process will be terminated,
else i selects a random number ij and reads PCR
from the local TPM, then uses AIK to generate the
signature x and reads the
measurement log , at last will send
encrypted by conversa-
tion key
1,lIK sA ij
SSignmPCRN
i
SML i U

,,,,
ii ij
PCR NAIKSML
im

3
m S
K
to . ,
j
Ui j
,
Ui j
4)When receives
, it distills
to judges whether meets the security stagy
of , if meets the security stagy of
, the double-way trust proof between and
is completed.
j
,,
iij
PCRN
jPCR

3,,mSAIKSML,i
PCR SML
,
j
Ui,i SML
,
j
Ui j
,
j
Ui j
i

,i PCR SML
i
U
3.4. The Generation of Signature Key
1) in random selects
i
U

12
,,,
n
UUU U*
p
SZ,
it computes a PK Sg

and publish ,
selects a
PK Sgi U
*
1
p
dZ,
j
Ui
and computes .
11
PK da g
2) For every j

in UU , ac-
cording to threshold values t, a t polynomial

12
,,,
n
U U
1



t1mod
01 2
iUiUUiUi
f
xa ax  ax q

,i
(Uit a con-
structed, for each signer j U it computes
0) is
,j


j
D
,ij
 i
U
fI and sends ,ij

to other users, each
,
j
Uij

in


,
n
U
12
U
j
,,UU will computes
,i
1
i
j
n





, then according the identity of TPM and
threshold values the private key of can be computed,
first i
U
1,
1
t
ii



mo
j
ij
ID
ID





dkp
t
jjiID 
,
nkc

,*
p
cZ is computed, takes
i
Un
a
g
as its
part public key , the will compute
, at last the public key of i
U is
2
PK
pi
U
2
dSmod
n
a
g


12
PK
i
U*
,PK and the private key of is

.
i
U12 ,dd
mi U
3.5. Some Commo n Mistakes
When needs to sign the message , first se-
lects
p
rZ and computes lP ,

r
KPK
2
e,


,mrhH,


,21 hdPK2

,hrh   d,

is the
signature of . m
3.6. The Verification of Signature
When the verifier receives

,h

, the verifier computes
whether


,mrhHand




12PK

12
e, h PKe,
a
g P  e,KPKl 







2
,
,
h
KPK
l
are true, if they are true, the verifier will accepts the sig-
nature.
4. Security Analysis
4.1. Validity of the Scheme
We first prove the validity of our scheme, according to
the bilinear map, the following





2
2
e
e,
e,
e,
a
a
gP
rhd
PK g
rhdg
rsPK g




21
2
12
22
2
e
e,
,
e
e,
a
aa
a
r
PKP
PKg
PK g
hSPK g
PK PK

21
,
e
a
K
hd
hS
e,
hd











is true, so our scheme is right.

Z.-H. ZHANG ET AL. 625
6. Acknowledgements 4.2. The Security of Private Key
The private key of our scheme has two parts ,
is generated by , for 12,dd 1d
iU
1,
1
mod
t
jj
j
ij
i
tID
ID
iiID
k 









p
Part of this paper’s work is supported by Ph.D. Start-up
Fund of Beijing University of Technology (No. 007000
54R1763). Part of this paper’s work is supported by
Opening Project of Key Lab of Information Network
Security, Ministry of Public Security (No. C11610). Part
of this paper’s work is supported by Opening Project of
State Key Laboratory of Information Security (Institute
of Software, Chinese Academy of Sciences) (No. 04-
04-1). Part of this paper’s work is supported by National
Soft Science Research Program (No. 2010GXQ 5D317).
nkc, *
p
cZ, 2, and 2 needs at
least members to, , are the secret parameters,
so if a adversary know , it means the adversary
has resolve the discrete logarithm problem.
mod
n
a
dSg p
nk

12
,dd
d
t
Any members can not know the private key, ac-
cording to the polynomial, members can know
the constant item of any member, but is a secret
value, so even if members can not know the private
key, so the private key of is secure.
t1t
t
tc
i
U
7. References
[1] Y. Desmedt and Y. Frankel, “Shared Generation of Au-
thenticators and Signatures,” Proceedings of Cryptol-
ogy-CRYPTO’91, Springer-Verlag, Berlin, 1991, pp. 457-
469.
4.3. No Forgery of Signature
[2] C. M. Li, T. Hwang and N. Y. Lee, “Remark on the
Threshold RSA Signature Scheme,” Stinosn D. LNCS 773:
Advances in Cryptology-CRYPTO’91, Springer-Verlag,
Berlin, 1994, pp. 413-420.
Only members can generate a signature and only
know member , after the computing
2 receiving , it can generate the pri-
vate key 12 , the attestation scheme described in
this paper is based on CDCH assume, and in probability
polynomial time anyone can’t get any information about
the private key of , so forging a signature of is
not feasible.
t
a
dS
i
U
i
nkc
p

i
U
mod
n
g

,dd 'v
U
[3] R. Gennaro, S. Jareeki, H. Krawczyk, et al., “Robust
Threshold DSS,” BMaurer U. LNCS 1109: Advances in
Cryptology-EUROCRYPT’96, Springer, Berlin, 1996, pp.
157-172.
[4] C. T. Wang and C. H. Lin, “Threshold Signature
Schemes with Trace Able Signers in Group Communica-
tions,” Computer Communications, Vol. 21, No. 8, 1998,
pp. 771-776. doi:10.1016/S0140-3664(98)00142-X
For the Private key *
p
SZ, *
p
SZ is independent
in the signature process , there is no product on *
p
SZ,
so the scheme can resist the replacing the public key at-
tack in literature [7,8]. [5] L. Ham, “Group-Oriented (t, n) Threshold Digital Signa-
ture Scheme and Digital Multi-Signature,” IEEE Pro-
ceedings of Computers and Digital and Technique, Vol.
141, No. 5, 1994, pp. 307-313.
doi:10.1049/ip-cdt:19941293
5. Conclusions
[6] F. Hess, “Efficient Identity Based Signature Schemes
Based on Parings,” Proceedings of Selected Areas in Cryp-
tography. SAC’ 02, Spring er, Berlin, 2 003, pp . 310- 324.
In this paper a new threshold signature based on Trusted
Platform Module (TPM) is presented, based on TPM the
signature node first should finish the trust proof between
it an other members who take part in the signature, then
the signer can generate signature. The scheme is based
on discrete logarithm and also don’t need trusted center,
comparing with traditional threshold signature this sche-
me has a higher efficiency.
[7] X. Chen, F. Zhang and K. Kim, “A New ID Based Group
Signature Scheme from Bilinear Pairings [EB/OL],” 2003.
http://eprint. Iacr.org/2003/1 16.pdf.
[8] M. C. Gorantla and A. Saxena, “An Efficient Certificate-
Less Signature Scheme,” Proceedings of Computational In-
telligence and Security, Springer, Berlin , 2006 , pp. 110- 116.