### Paper Menu >>

### Journal Menu >>

Intelligent Information Management, 2009, 1, 174-179 doi:10.4236/iim.2009.13026 Published Online December 2009 (http://www.scirp.org/journal/iim) Copyright © 2009 SciRes 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 Email: shundong@mail.tsinghua.edu.cn 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 mr 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 d6 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 Copyright © 2009 SciRes IIM S. D. LI ET AL. 176 Sets 1s For i = 0 to k IF then 1 i dmod 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, Copyright © 2009 SciRes IIM 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- Copyright © 2009 SciRes IIM S. D. LI ET AL. Copyright © 2009 SciRes IIM 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. |