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.