Intelligent Information Management, 2009, 1, 174-179
doi:10.4236/iim.2009.13026 Published Online December 2009 (http://www.scirp.org/journal/iim)
Secure Signature Protocol
Shundong LI1, Daoshun WANG2, Yiqi DAI2
1School of Computer Science, Shanxi Normal University, Xi’an, China
2Department of Computer Science and Technology, Tsinghua University, Beijing, China
Abstract: This paper studies how to take advantage of other's computing ability to sign a message with one's
private key without disclosing the private key. A protocol to this problem is presented, and it is proven, by
well known simulation paradigm, that this protocol is private.
Keywords: cryptography, secure computation, signature, service, protocol
1. Introduction
Feigenbaum proposes the following problem [1]: Alice
has a function f() and a its instance x. She needs to com-
pute f(x), but does not have the corresponding computing
resources, or because she is too lazy to do the computing.
The sources here are in general sense which includes the
computing time, algorithmic knowledge or correspond-
ing hardware. If Bob has the corresponding resources,
can she take advantage of Bob's resources without trust
him? That is, can she use Bob's resources to compute f(x)
without letting Bob know x and f(x)?
In some cases, this problem can easily be solved. For
example, if Alice and Bob are geographically near. In
this case, Alice can rent Bob's computing resources to
compute f(x), and we call that Bob supplies Alice with
computing service. In other cases, it may be very diffi-
culty to solve. For example, Alice and Bob are far from
in distance. In this case, complicated cryptographic pro-
tocol will be necessary to solve it.
Studying secure computing service is of great theo-
retical importance to computing science and cryptogra-
phy. R. Cramer once said: “If we can securely compute
any function, computing science will have a new power-
ful tool [2].” The combination of secure multiparty com-
putation [3] and secure computing service can realize the
objective to securely compute any function. Furthermore,
studying secure computing service is of great practical
importance to information security. In contrast to the
rapid development of secure multiparty computation
[4–7], secure computing service is still stagnant. Only
the secure computations of discrete logarithm and the
inequality of vectors have been solved. No other prob-
lems have been solved. This paper studies the secure
signature problem, proposes a protocol for it. It is proven,
by well known simulation paradigm, that the protocol
has privacy-preserving property.
2. Preliminaries
2.1. Notations
Let x be a variable, f() be a function, and f(x) the value of
f() at x. dom(f) is used to denote the domain of f(), and
range(f) the codomain. If two objects A, B are computa-
tionally indistinguishable, we denote
c
A
B. Two compu-
tationally indistinguishable objects can be considered
completely equivalent in all computations. Computa-
tional indistinguishability is an important basis for many
kind of security in cryptography. For more details of
computational indistinguishability, see [8].
2.2. Related Work
Feigenbaum's secure computation protocol for discrete
logarithm is as follows: Let p be a big prime number,
*
p
Z
be the set{1,2 ,,1}p

and the multiplicative operation
on it, g the generator of*
p
Z
. Instance*
p
x
Z, Alice wants
to take advantage of Bob's computing resources to com-
pute e = f(x)*
p
Z
such thate
g
mod p = x without letting
Bob knowing x.
 Alice randomly chooses a*
p
cZ, computes '
x
x


mod .
c
g
p
 Alice sends'
x
to Bob, asks Bob to figure out an
'(')efx

such that'mod '
e
g
px

.
 Bob sends(') '
f
xe

to Alice.
 Alice computes
e = f(x) =(') mod(1)ec p

.
In the protocol above, apart from other simple opera-
tions, Alice still needs to compute complicated modular
exponential operations. Though modular exponential
operation is rather complicated, its complexity is much
less than that of computing discrete logarithm. So this

S. D. LI ET AL. 175
scheme is meaningful. We assume that Bob is semi-
honest, that is, he will execute the protocol properly and
he will sends correct result to Alice, but he may also
keep the record of intermediate computation to try to
figure out x or f(x) provided he is interested in them.
Definition 1 [3] Let f() be a computable function, π a
two party protocol for computing f(). On input
()
x
dom f, the message that Bob received during the
execution of π, denoted by is (), whereis
Bob's independent coin toss for determining what algo-
rithm and strategy be adopted to compute f(x), the
i-th message Bob received. For function f(), if there ex-
ists a polynomial time algorithm S such that
1
,,,
t
rm mr
i
m
,()
()
{(,),()}
{((,), (,)}
c
mddomf
ABx dom f
fmd Ss
outputm dviewm d



 (1)
we say that π privately computes f(), whereis
Alice's final output, and in most case = f(x).
That is, if there exists a simulator S which on input f(x),
can simulate the protocol execution on input x, and ob-
tains a sequence that is computationally indistinguishable
from (), then the protocol is private for com-
puting f() at x.
()
B
output x

()
Bx

output
1
,,,
t
rm m
3. Secure Signature Protocol
In this problem, Alice has a message m to be signed. Be-
cause digital signature needs to compute where
m, e may be relative large and n is a very large number
(may be greater than). Alice does not have corre-
sponding computing resources, so she has to take advan-
tage of Bob's resources to finish her signature. We as-
sume that Alice signs message by RSA algorithm with
private/public keys pair d/e, then her signature on mes-
sage m is . d can be written as
mod
e
mn
n
2
7
1000
2
mod
d
m
01
2k
k
dd dd (2)
For example, 127 can be written as
127 =(3)
0123456
1212 1212121212
and in this case,, or be written as
01 7
1dd d
127= (4)
0123456
(1)2 0202 02 02 0202 02      
and in this case, To fa-
cilitate Alice's signature, d = 127 should be expressed
with (4). In contrast, if d = 129, it should be expressed
with (3), and in this case,
071 6
1, 1,0.ddd d 
07
1,dd

1 d6 0d. No
matter which form is adopted, it holds that
01
22
mod mod
k
k
dd d d
mnm
 
n
In what follows, we denote d by
d = [].
01
,,,
k
dd d
Thus following protocol follows:
3.1. Protocol
Protocol 1 Secure signature protocol
Inputs: message m and Alice's private key d =
[].
01
,,,
k
dd d
Output: the signature on m, that is,
mod
d
mn
1) Alice sends m to Bob, and asks Bob to compute U =
() where
12 1
,,,, ,,
kk p
uuu uu


2mod(1, 2,,)
i
i
um nip
and V = (), where
12 1
,, ,,, ,
kk p
vvv vv


21 1
()mod mod(1,2,,)
i
ii
vmnu nip


2) Bob computes U, V, and sends them to Alice.
3) Having received U, V, Alice computes
0
() ()mod
i
k
d
i
i
s
mu

n
i

n
Then s(m) is Alice's signature on message m with pri-
vate key d. If m is the result obtained by encrypting some
message with Alice's public key, then this protocol de-
crypts the message using Bob's computing resources
without letting Bob know Alice's private key and the
plaintext.
It seems that Alice does not obtain much advantage
from this protocol, because she still has to compute mul-
tiplication of some big integers. In fact, this protocol
gives Alice much advantage due to the following fact:
 It is very easy to compute()
i
d
i
ubecause {1,0,1}
i
d ,
and
1
() 10
1
i
ii
d
i
ii
uifd
uifd
vifd







(5)
So, Alice does not need to compute
()
i
d
i
u
 Many '
i
ds have specific structure, that is, many
'
i
ds
in d = [01
,,,
k
d] is 0, which facilitates the com-
putation. For example, 65535=216 -1, if we want to
compute m65535 mod n, it is sufficient to compute
dd
16 16
212 1
16 1
modmod modmnmmnuv


Similarly, if d = 4295098369 = 1 + 217 + 232,
then 01732
1dd d

and all other are 0. So '
i
ds
117 32
0
() ()modmod
i
k
d
i
i
s
mu nuuu


n
 Bob's computational complexity is not the concern
of secure computing service protocol. In this protocol,
Alice just needs to transform d into its binary representa-
tion d = [] and chooses the terms
with 0
i
d
01
,,,
k
dd d

(0ik

) to compute by following algorithm

S. D. LI ET AL. 176
Sets 1s
For i = 0 to k
IF then 1
i
dmod
i
s
su n
IF then 1
i
d mod
i
s
sv n
Outputs s
3.2. Privacy-Preserving Property
We first intuitionally analyze the security of this protocol
followed by a rigorous proof. To know Alice's private d,
Bob has to know every di of []. In this proto-
col, Alice does not tell Bob any information about d, not
even the largest index k, and what he knows is just p(p >
k). He is not expected to obtain information about d.
01
,,,
k
dd d
Suppose that Bob can somehow know k, then he can
guess every di with probability 1/3, because .
And he can successfully guess d with probability3
{1,0,1}
i
d
k

.
Reader may argue that are not uniformly distributed
over {0,1,-1}, the successful probability is at most
even we neglect the possibility that d
i takes -1, be-
cause are at least uniformly distributed over {0,1}.
This conclusion has nothing to do with Bob's computing
power. No matter what powerful computing ability Bob
has, there is no enough information to help him decide
every di.
'
i
ds
2k
'
i
ds
Of course, Bob may obtain more information to help
him decide di after having seen Alice's signature on mes-
sage m. This is beyond the scope of this paper, because
even if he did not help Alice sign the message, he can
still obtain corresponding information to do this. That is,
if taking part in this protocol makes him can determine di,
he can also do this without taking part in. In other words,
this protocol does not leak any information about d.
About the privacy preserving property, we have follow-
ing theorem.
Theorem 1 The signature protocol above, denoted
by

is private
Proof We prove this theorem by showing a simulator S
such that (1) holds. The message sequence Bob received
during the execution of π is,
where r is Bob's independent coin toss for determining
what algorithm to be used to compute U, V. The key here
is that the simulator just hasas its input, and it
does not even know m, how can it simulate the protocol
execution. The simulation proceeds as follows:
(,) {,,,,}
B
viewmdmrUV s


mod
d
mn
1) On input s, simulator S can ask Alice to send her
public key e to it, and computes
mod
e
s
nm

.
2) Without the requirement of Alice, S computes U, V.
Same m will certainly result in same U, V.
3) S has known s. If it can figure out for
s, m, it outputs, otherwise outputs s. In this
protocol
mod
d
mn
mod
d
m
)
n
(,(,) (,)
AB
f
m dm doutputm ds

output


() }Ss s
4) Let { ,,,,mrUV

, it is obvious that
,()
()
{(
{(,(,)}
c
mddom f
Bx dom f
viewm d




12
22
mod ,mod ,,mnmnm
()mo
i
d
i
u0
i
d
7
,,11724 ,, ,,vv v
(1, 2,, 24)
ini
,),()}
(,)
A
fmd Ss
outputm d
dn
24
u
2mod
i
um
The theorem follows.
The proof shows that if Bob can figure out Alice's d,
after taking part in the execution of the protocol and ob-
taining s, then he can do this without taking part in the
execution. That is, taking part in the protocol cannot help
Bob obtaining Alice's private key. If RSA signature algo-
rithm is secure, then this protocol is private.
3.3. Alice's Computing Power Saving
Taking multiplication as the basic unit to measure com-
putational complexity, if Alice signs message m himself,
her computational complexity is O (log d) which can not
be further decreased. In this protocol, Alice takes advan-
tage of Bob's computing resources greatly decreasing her
computational complexity. For example, if d =
4295098369, Alice has to do multiplication 48 times on
average (to compute )
and for those, while by this protocol,
she just needs to do multiplication operation 2 times. On
average, 1.5 log d multiplications are necessary for Alice
to sign a message, but using this protocol, Alice just
needs to compute 0.5log d multiplications. The bigger d
is, the bigger computational complexity gap will be, and
the more obvious advantage of secure signature protocol
will be displayed.
32
2
mod n
32
0
i

3.4. An Example
Suppose that n = 6012707, Alice's private key is d =
65535 and the message that Alice wants to sign is m =
5234673. Because d = 217 -1, d = [-1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 1].
1) Alice sends m and asks Bob to compute U =
() and V = () where
11
,,uu
.
2) Bob computes U = (5234673, 1615224, 4939341,
1743565, 262732, 2227464, 245501, 5378740, 770381,
2640726, 4457202, 4343034, 4300965, 2413687,
4765873, 3615999, 5681056, 1936650, 837333,
2827740, 86221 7, 1048902, 23 04158, 1973155, 4642 799,
3908573), uses Euclidean extended algorithm to compute
V , and obtains V = (793604, 3 01394, 43 78587, 277 9681,
3344118, 1258019, 1182184, 1471018, 4884922,
1030980, 5442354, 307 0495, 29436 11, 5814105,
5409191, 5823024, 56145 08, 1347304, 38505 30,

S. D. LI ET AL. 177
3419982, 4474211,1691689, 3649001, 2506724,
1583928, 1862606).
3) Alice simply computes S == 5681056×
793604 mod 6012707 = 676014
017
modvu n
4. Research Background
In scientific research, computing method has become the
third important research method that parallels theoretical
method and scientific experiment method. Computing
method bridges the theoretical method and experiment
method. The problems met in computing science show
some new trends: the problem domain is wider and wider,
the problems are more and more complicated, the prob-
lem sizes are bigger and bigger, the datum are more and
more. To solve these complicated problems, supper
computing power and data analysis ability are necessary.
Supper computing power has become the symbol of the
development level of science and technology of a coun-
try, and embodies the competition ability of national sci-
ence and technology. To own supper computing power
and data analysis ability, scientists developed high per-
formance computing, parallel computing and grid com-
puting etc. Many countries built their super computing
center. But many super computing centers lack corre-
sponding computing task after their construction which
makes these super computing centers cannot fully play
their roles. To fully play their roles and maximize their
benefits, they have to open to outside and supply com-
puting service to the public.
This is good news to some organizations which are
worrying about their irregular and great computing
power requirements. Because their requirements of
computing power are irregular, it does not pay to buy
powerful computing equipment. If they can rent corre-
sponding computing power from super computing cen-
ters when they need, then the computing power of super
computing centers will be fully played and their irregular
requirements will be met. They do not need to expen-
sively purchase and maintain computing equipments.
This is win-win to both the super computing centers and
the public. In mobile computing environments, mobile
equipments are often short of computing power, thus if
some computing that mobile equipments have to make
can be transported through internet to some computing
service provider, then both the mobile service providers
and computing service providers will be very interested
in this new computing mode. This new computing mode
can also promote the development of mobile e-commerce.
To sum up, this computing service mode has a strong
appeal to computing service providers and receivers. But
the trouble this win-win computing mode meets is that
the computing service providers cannot supply secure
computing service. If Alice's problem is a secret com-
puting task, signature operation for example, she will
hesitate to use the computing power of computing ser-
vice providers. If the computing process cannot keep the
privacy of the computing, Alice would rather give up
using other's computing power. Privacy-preserving prop-
erty is a basic requirement of public computing service.
It is also an urgent problem that must be solved for ex-
ploiting computing service market, privacy preserving
and information security.
If fully studied, secure computing can solve all above
problems. It can also exploit many new applications. For
example, identification in cyberspace is realized by
means of public key signature, but the computing power
that public key signature needs is beyond that an ordi-
nary internet user posses. It is unrealistic to demand an
ordinary user to buy expensive computing equipment, or
to take a long time learning corresponding algorithmic
knowledge. It is a huge task to popularize signature and
identification among ordinary users. If the computation
can be done by secure computing service providers,
while ordinary users just do some simple operations, then
signature and identification will be very easy to popular-
ize, and this will be of great theoretical and practical sig-
nificance to information security and the development of
computing science.
5. Conclusions
This paper studies secure signature and decryption prob-
lem, and presents a secure computing service protocol. It
is also proven, by well known simulation paradigm, that
this protocol is privacy preserving. This problem has
important practical significance in computing science
and cryptography. The combination of secure multiparty
computation and secure computing service can make us
near to the objective of secure computing any function,
so it also has essential theoretical significance. Of course,
this protocol does not give Alice too much advantage to
sign a message, and we will further study more protocols
that may give Alice more and more advantages.
6. Acknowledgment
This research is supported by the National Natural Sci-
ence Foundation of China (Grant No. 60673065,
60873249) and National High Technology Development
(863) Program (2008AA01Z419, 2009AA011906).
REFERENCES
[1] J. Feigenbaum, “Can you take advantage of someone
without having to trust him,” LNCS, Vol. 218, Springer-
verlag, N.Y., pp. 477–488, 1986.
[2] R. Cramer and I. Damgaard, “Introduction to secure
multi-party computations,” In: Contemporary Cryptology,
pp. 41–87, Advanced Courses in Mathematics CRM Bar-
celona, Birkhauser, at: http://homepages.cwi.nl/ cramer/, 2005.
[3] O. Goldreich, “Foundations of cryptography: Basic ap-

S. D. LI ET AL. 178
plications,” Cambridge University Press, London, 2004.
[4] W. L. Du and M. J. Atallah, “Secure multi-party compu-
taion problems and their applications: A review and open
problems.” In: Proceedings of New Security Paradigms
Workshop, ACM Press, New York, pp. 13–22, 2001.
[5] S. Goldwasser, “Multi-party computations: Past and pre-
sent [C],” In Proceedings of the Sixteenth Annual ACM
Symposium on Principles of Distributed Computing
(Santa Barbara, CA, August, 1997), ACM Press, New
York, pp. 21–24, 1997.
[6] S. D. Li, D. S. Wang, Y. Q. Dai, and P. Luo, “Symmetric
cryptographic solution to Yao's millionaires’ problem and
an evaluation of secure multiparty computations,” Infor-
mation Sciences, Vol. 178, pp. 244–255, 2008.
[7] Y. Lindell, “General composition and universal compos-
ability in secure multiparty computation,” Journal of
Cryptology, Vol. 22, No. 3, pp. 395–428, 2009.
[8] O. Goldreich, “Foundations of cryptography: Basic
tools,” Cambridge University Press, London, 2001.