Selected application of the Chinese Remainder Theorem in multiparty computation
Artur Jakubski
Journal of Applied Mathematics and Computational Mechanics |
Download Full Text |
Selected application of the Chinese remainder THEOrem in Multiparty computation
Artur Jakubski
Institute of Computer and Information
Sciences, Czestochowa University of Technology
Częstochowa, Poland
artur.jakubski@icis.pcz.pl
Abstract. In this paper we present protocols checking the equality of two distributed numbers and calculation of the product in such a way that the distributed numbers are unknown to anyone. The presented protocols use the Chinese Remainder Theorem. As a result, the obtained protocols have many interesting cryptographic features.
Keywords: multiparty cryptography, secret sharing, distributed algorithms, modular arithmetic
1. Introduction
This paper discusses the multiparty computation protocols with the use of the Chinese Remainder Theorem. Of the many protocols with such application, we discuss two selected protocols. We adopt the honest-but-curious framework of multiparty computations, executed collectively in a fully (completely) decentralized environment of cooperating agents (participants, players, computers, servers, processes, devices, mobile devices), in which parties collectively generate a protocol result. Because of the cryptographic application, the typical length of the participants’ shares should be greater than 500 bits.
The integer is never revealed to any party. We assume that our protocol is run without any trusted party (server, dealer, or central authority).
The participants are assumed to communicate over secure channels, meaning that the messages sent from one participant to the other are private and no one can interfere along the way. We assume that all participants follow the protocol honestly.
Fully distributed or fully decentralized means: with no trusted party whatsoever and with all the parameters shared as secret.
The main idea is that both the input and output integer parameters are never revealed. Instead, they are shared by participants using an appropriate secret sharing. We are going to use the elementary additive secret sharing but also secret sharing based on Shamir secret sharing as in [1, 2] and the BGW method [3, 4]. We use also the Chinese Remainder Theorem (see [2] and [5]). In the area of multiparty computation, five papers [6-10] deserve special attention. The papers deal with distributed primality testing.
Our paper is organized as follows. In Section 2 we discuss Shamir’s secret sharing. Section 3 presents the BGW method, which is a protocol for distributed product computing. In Section 4 we introduce two new protocols, using the Chinese Remainder Theorem. Finally, Section 5 concludes the paper.
2. Shamir’s secret sharing
The first threshold schemes were initiated by two papers published almost simultaneously in 1979, A. Shamir How to share a secret [1] and G. Blakley Safeguarding cryptographic keys [11].
To build a threshold scheme, Adi Shamir [1] uses a polynomial over a finite field. First, a prime number has to be selected (let's call it ), which is greater than the number of protocol parties and greater than a password (secret, key) . The password will be distributed among the parties. If the threshold is , it is generated a polynomial of degree with coefficients derived from the field () and free term equal . A prime number is public, and the coefficients of the polynomial must be secret and known only to the person choosing them, i.e. the dealer. The shares of the distribution, also known as the shadows, are the values of this polynomial for different arguments.
Let’s denote a share belonging to the party by . It is often assumed that . or more participants can reconstruct the password . The reconstruction is to restore the polynomial based on at least its values and computing the value at zero of this polynomial. Generally, we often use here Lagrange interpolation formula.
A more general approach to the presented problem can be found by the reader in [12-14].
2.1. Secret sharing
A dealer (a trusted third party) has to generate a random password (). Then the dealer shares the key among parties (participants). He executes this as follows; he randomly selects a prime number of a feature that and assumes that . Now the dealer randomly chooses coefficients belonging to the field and he denotes . The dealer computes for , and he distributes a pair of numbers to each participant.
Distribution of password
1. The dealer generates a prime number greater than and defines .
2. He denotes in field random coefficients and considers polynomial over field as .
3. He computes , for and sends the share to the party .
2.2. Password reconstruction
or more parties (the participants) can appoint password . There are several options that can be proposed here. The most common way of obtaining a key is the Lagrange interpolation formula. Suppose, we have shares of participants .
Now, we get from .
3. The product of two unknown to anyone (distributed) factors - the BGW method
This section discusses the protocol of distributed product computing - the BGW protocol [3, 4] (acronym of authors’ last names Ben-Or M., Goldwasser S., Wigderson A.). The party in the submitted protocols is equated with the participant (computer or server) of protocol. In the submitted protocols, three or more parties will take part. We assume that each party may communicate with any other party. Messages sent from one participant to the other are private, and no one can interfere along the way. Furthermore, we assume that all parties of the protocol are fair.
In consequence of this, presented protocol is private. This means that any coalition of (or less) parties does not recognize the factors of the computed product. However, a coalition of more than parties may recover the factors of the mentioned product. The reason for this is privacy of the used BGW method. Replacing the BGW method by the Cocks method [15], the presented method can achieve the greatest possible privacy, i.e. .
In our protocol there are participants involved, and is the product of two numbers and . The party has secret numbers and , called its shares.
The sum of the shares is and in such a way that ,. This method shows a distributed computing so that none of the parties could know both or , and only a coalition of more than parties can recognize factors and . So, in order to know the factorization of , you have to bribe at least half of the protocol participants. The protocol is derived from the work of Ben-Or, Goldwasser and Wigderson, in which the authors describe an elegant protocol to compute , for three or more parties. Practically, we take a prime number greater than . Let also.
The BGW method for distributed computation
1. Each party chooses two random polynomials of degree , i.e. party chooses , such that and a random polynomial of degree , such that .
2. Each party computes values, i.e. party computes: . Party sends to party : .
3. Party computes: . The result is given to the public or transmitted to other parties.
4. Parties, having with using Lagrange interpolation formula, receive polynomial .
In view of the equality parties receive .
4. Proposed protocols
In this section we will present original protocols checking the equality of two distributed numbers and distributed multiplication, using the Chinese Remainder Theorem. We will indicate the correctness of these protocols and we will present their bit complexity. Although such solutions are known so far, we have not cognized such a type of approach for the considered issues.
4.1. Chinese Remainder Theorem
Chinese Remainder Theorem is a theorem that is widely applicable in crypto- graphy. It can often be used to speed up the computations. In addition, it is used to construct a number of libraries for computations on large integers. Libraries of this type find application in the aforementioned cryptography.
Theorem (Chinese Remainder Theorem).
If the integers are pairwise relatively prime, then the system of simul- taneous congruences
has a unique solution modulo .
Gauss’s Algorithm. The solution to the simultaneous congruences in the Chinese Remainder Theorem may be computed as , where and [2, Ch. 2]. It is easy to notice that the algorithm can use a mechanism of parallelization or distribution. We use the algorithm in the following protocols. If we know the values we can determine the value in a fast operations) and simple way.
4.2. The protocol verifying equality of two distributed numbers
The following procedure involves a group of participants of the protocol, in which the participant holds the shares and .
In the procedure given below, the result of subtraction of and does not leak any information if the coalition of conspiring parties is less than .
The procedure returns true, when , and false, when . We assume that all parties know a collection of primes (or, at least, pairwise relative primes) such that . To improve efficiency, the public primes should be as small as possible and at the same time they should be close to each other.
The main idea of this procedure is based on the Chinese Remainder Theorem. Step 1 gives a new distributed number . Next, each party produces shares for the integer using the Chinese Remainder Theorem. Shares are sent via secure channels to the other parties. In Step 4, all parties check the equality and broadcast their results. In this chapter, we assume that the value of is .
equal ( is true)
INPUT: of party : and the set of public primes.
OUTPUT: of party : true/false an answer to the question: whether ?
1. Each party computes its own share in , which is the result of subtraction of and ; i.e., party computes .
2. Each party computes values where .
3. Party generates polynomials of degree over the fields with the free coefficients , respectively.
4. Party computes values , for from to .
5. Party sends to party .
6. Party computes .
7. Party generates the random value and computes .
8. Party generates polynomial with integer coefficients of degree with free coefficient .
9. Party computes values .
10. Party sends to party the computed values .
11. Party computes .
12. Parties reveal their values , if the sum equals zero, they return true, otherwise false.
Analysis of complexity
In the procedure analysed here, we assume that the length of all the shares in the distributed number does not exceed bits and the number of participants is . The communication overload complexity (the number of bits that each participant must send to the others) of the procedures is .
The procedure equal ( is true) needs bit operations and their communication complexity is .
Correctness of the distributed equality checking
The protocol checking the equality of two distributed numbers is equal(is true). Each party involved in this procedure inputs, in addition to its shares in the two distributed integers, (relative) primes. The product of those primes is supposed to be bigger than the difference between the two numbers that we are comparing; i.e. . The protocol returns true when , for each . We continue our analysis for a fixed prime . The last equality entails that in step 3 of the procedure we have . Since , we get . Hence, for each , we have . Finally, by the fact that we get the equality of and .
4.3. The protocol computing the product of two distributed factors with use of the Chinese Remainder Theorem
This section discusses the protocol of distributed product computing with the use of the Chinese Remainder Theorem. As in the previously submitted protocols, there are three or more parties participating in the protocol. We assume that each party may communicate with any other party. Messages sent from one participant to the other are private, and no one can interfere along the way. Furthermore, we assume that all parties of the protocol are fair.
In consequence of this, the presented protocol is private. There are participants involved in this protocol and is the product of and . The party has two secret numbers and called its shares. The sum of the parts is and , such that , . This method presents distributed computation , so that no party could learn neither nor and only a coalition of more than parties can get to know factors and . So, in order to know factorization , you have to bribe at least half of the protocol participants. Practically, you have to take a prime number greater than .
Below we present the protocol of distributed computing of .
multiplication ()
INPUT: of party : and the set of public primes.
OUTPUT:
1. Party computes values and for .
2. For each party, the participants come together to compute the values of the two sums, i.e. for party they compute and [see below, sum].
3. Party computes: , and values and .
4. Using the BGW method, parties compute the value: .
The value computed in step 4 is the value of the product . The second step of this protocol is implemented on the basis of common computing of the distributed values sum, for a chosen party. Below we present an example of implementation of protocol for multiparty computing the sum (example implementation for step 2).
sum ()
INPUT: of party : .
OUTPUT: of party : .
1. Each party generates a random polynomial of degree over a finite field with a value of zero equal to its share. Let party generate the polynomial .
2. Each party computes values of our polynomial e.g. values for .
3. Each party sends the value for argument to the party of number .
4. Party of number adds the values obtained in step 3.
5. Party multiplies the sum obtained in step 4. by the value .
6. Parties send the value obtained in step 5. to party .
7. Party computes the sum of values obtained in step 6.
The protocol presented above for computing the sum is private. So, any coalition of or less parties (excluding the party of number ) does not know the computed secret.
The Chinese Remainder Theorem used here increases the cryptographic power of protocol for ordinary multiplication of two distributed numbers.
5. Conclusions
In this paper we focus on the applications of the Chinese Remainder Theorem in protocols for verifying the equality of two distributed numbers and computing the product of two distributed numbers. The discussed protocols form the beginning of our research on applications in the field of multilateral Chinese Remainder Theorem computations. We intend to expand our research into other protocols, among others, protocols for comparing distributed numbers (Millionaires’ problem) or protocols for remainder computation etc.
Presented protocols can be used in more advanced protocols, including distributed primality testing. The problem will be described in the next article which will be published soon. In this article I will be co-authored. Another proposed research will be application of the proposed protocols.
References
[1] Shamir A., How to share a secret, Communications of the ACM 1979, 22(11), 612-613.
[2] Menezes A., van Oorschot P., Vanstone S.A., Handbook of Applied Cryptography, CRC Press, 2013.
[3] Ben-Or M., Goldwasser S., Wigderson A., Completeness theorems for noncryptographic fault- tolerant distributed computation, Proceeding STOC ’88, Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, 1988, 1-10.
[4] Boneh D., Franklin M., Efficient generation of shared RSA key, Advances in Cryptology - CRYPTO’97, Springer, 1997, 1296, 425-439.
[5] Mignotte M., How to share a secret, Advances in Cryptology, Eurocrypt’82, LNCS, Springer-Verlag, 1983, 149, 371-375.
[6] Frankel Y., MacKenzie P.D., Yung M., Robust efficient distributed RSA-key generation, Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC’98, ACM, New York 1998.
[7] Algesheimer J., Camenisch J., Shoup V., Efficient computation modulo a shared secret with application to the generation of shared safe-prime products, Advances in Cryptology, Proceedings of CRYPTO 2002, LNCS, 2002, 2442, 417-432.
[8] Kiltz E., Unconditionally secure constant round multi-party computation for equality, comparison, bits and exponentiation, Proceedings of the Third Theory of Cryptography Conference 2005.
[9] Damgård I., Fitzi M., Kiltz E., Nielsen J.B., Toft T., Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation, Theory of Cryptography Lecture Notes in Computer Science 2006, 3876, 285-304.
[10] Chao Ning, Qiuliang Xu, Constant-rounds, linear multi-party computation for exponentiation and modulo reduction with perfect security, Proceedings of Asiacrypt’11, Springer-Verlag, 2011, 572-586.
[11] Blakley G.R., Safeguarding cryptographic keys, Proc. AFIPS 1979, National Computer Conference, AFIPS, 1979, 313-317.
[12] Chun-Pong Lai, Cunsheng Ding, Several generalizations of Shamir’s secret sharing scheme, Internat. J. Found. Comput. Sci. 2004, 15, 445-458.
[13] Schinzel A., Spież S., Urbanowicz J., Elementary symmetric polynomials in Shamir’s scheme, Journal of Number Theory 2010, 1572-1580.
[14] Spież S., Srebrny M., Urbanowicz J., Remarks on the classical threshold secret sharing schemes, Fundamenta Informaticae 2012, 114 (3-4), 345-357.
[15] Cocks C., Split knowledge generation of RSA parameters in cryptography and coding, 6th IMA Conference, LNCS, Springer-Verlag, 1997, 1355, 89-95.