koorio.com

海量文库 文档专家

海量文库 文档专家

- A fair and efficient solution to the socialist millionaires’ problem
- An efficient solution to the millionaires’ problem based on homomorphic encryption
- An Efficient Solution to the Five-Point Relative Pose Problem
- An O(1) Solution to the Prefix Sum Problem on a Specialized Memory Architecture
- AN ADAPTIVE RLS SOLUTION TO THE OPTIMAL MINIMUM POWER FILTERING PROBLEM WITH A MAXMIN FORMU
- Monotonic solution of the frame problem in the situation calculus an efficient method for w
- Efficient solution of stochastic systems Application to the embankment dam problem
- An efficient approach to the simultaneous localisation and mapping problem
- A Novel Solution to the ATT48 Benchmark Problem

An E?cient Solution to The Millionaires’ Problem Based on Homomorphic Encryption

Hsiao-Ying Lin and Wen-Guey Tzeng Department of Computer and Information Science National Chiao Tung University Hsinchu, Taiwan 30050 Email:lrain.cis92g@nctu.edu.tw,tzeng@cis.nctu.edu.tw

Abstract. We proposed a two-round protocol for solving the Millionaires’ Problem in the setting of semi-honest parties. Our protocol uses either multiplicative or additive homomorphic encryptions. Previously proposed protocols used additive or XOR homomorphic encryption schemes only. The computation and communication costs of our protocol are in the same asymptotic order as those of the other e?cient protocols. Nevertheless, since multiplicative homomorphic encryption scheme is more e?cient than an additive one practically, our construction saves computation time and communication bandwidth in practicality. In comparison with the most e?cient previous solution, our protocol saves 89% computation time and 25% communication bits.

Keywords: secure computation, the greater than problem, homomorphic encryption

1

Introduction

Yao’s Millionaires’ (”greater than” or ”GT”) problem is to determine who is richer between two parties such that no information about a party’s amount of assets is leaked to the other party. Yao [Yao82] ?rst proposed a solution for the problem. Thereafter, many other protocols with great improvement are proposed. Some protocols [BK04,IG03,Fis01] solve the problem directly by analyzing the special properties of the problem. Some others [ST04] solve it in the content of secure multiparty computation in which the problem is represented as secure evaluation of the ”greater than” boolean circuit with encrypted inputs. The former solutions are more e?cient, while the later ones are more general. The GT protocol has many applications, such as in private bidding. In this paper we analyze the special properties of the GT problem. We ?nd that the GT problem can be reduced to the intersection problem of two sets by a special coding for the private inputs. We could tackle the set intersection problem by the method in [FNP04]. Nevertheless, the protocol for the GT problem by

Research supported in part by National Science Council grants NSC-93-2213-E-009-008 and NSC 93-2213-E-009-009

using the set intersection protocol in [FNP04] directly is less e?cient in both computation and communication. We solve the GT problem by further probing the property of our coding method. Our protocol can be based on either an additive or a multiplicative homomorphic encryption scheme, while most previous protocols [BK04,Fis01] are based on additive or XOR encryption schemes only. The computation and communication costs of our protocol are in the same asymptotic order as those of the other e?cient protocols. Nevertheless, since multiplicative homomorphic encryption scheme is more e?cient than an additive one practically, our construction saves computation time and communication bandwidth in practicality. In comparison with the most e?cient previous solution, our protocol saves 89% computation time and 25% communication bits.

1.1

Related Work

Secure multiparty computation (or secure function evaluation) is to compute a public function with each party’s private input such that in the end only the evaluation result is known and the private inputs are not exposed except those derived from the result. Yao [Yao82] ?rst proposed such a protocol for the GT problem, which is an instantiation of secure multiparty computation. Nevertheless, the cost of the protocol is exponential in both time and space. Later one, Yao [Yao86] and Goldreich, etc [GMW87] used the technique of scrambled circuits to solve the general multiparty computation problem. By applying this technique to the GT problem, the cost of the resulting protocol in computation and communication is linear. Recently, Schoenmakers and Tuyls [ST04] used threshold homomorphic encryption schemes as a tool to solve the multiparty computation problem. Applying to the concrete GT problem, it provides a threshold GT protocol, in which the private inputs are shared among a group of parties. The protocol takes O(n) rounds. On the other hand, protocols for solving the GT problem directly are more e?cient. These protocols usually take a constant number of rounds. Ioannidis and Grama [IG03] used 1-out-of-2 oblivious transfer scheme to construct the GT protocol that runs n copies of the OT scheme in parallel, where n is the length of the private inputs. However, the length of the private inputs is restricted by the secure parameter of the based OT schemes. Fischlin [Fis01] used the Goldwasser-Micali encryption scheme (GM-encryption) to construct a two-round GT protocol. The GM encryption scheme has the XOR, NOT and re-randomization properties. They modi?ed the scheme to get an AND property, which can be performed once only. The computation cost O(n) for the server side is very e?cient. Nevertheless, the overall computation cost for both the client and server sides are O(n log N ), where N is the modulus. In [BK04], Blake and Kolesnikov used the additive homomorphic Paillier cryptosystem to construct a two-round GT proto2

col. The computation cost is also O(n log N ). The protocol is more e?cient than the protocol in [Fis01] in practicality.

2

Preliminaries and De?nitions

The GT problem is a two-party secure computation problem of securely evaluating a predicate f such that f (x, y) = 1 if and only if x > y, where x is Alice’s private input and y is Bob’s private input. A solution protocol Π for the GT problem should meet the following requirements. 1. The involved parties Alice and Bob are both polynomial-time bounded probabilistic Turing machines. We assume that Alice and Bob are semi-honest. That is, they shall follow the protocol step by step, but try to get extra information by more computation. 2. Correctness: After execution of Π, Alice returns 1 if and only if x > y. 3. Alice’s privacy: Holdings of x or x (x = x) are not distinguishable by Bob. 4. Bob’s privacy: Alice cannot get extra information except those derived from x and f (x, y). 2.1 Homomorphic encryption with scalaring

We review multiplicative and additive homomorphic encryption schemes with the property of scalaring. Multiplicative homomorphic encryption schemes are usually more e?cient than additive homomorphic encryption schemes, An encryption scheme is multiplicative homomorphic if and only if E(m1 ) where only if E(m2 ) = E(m1 × m2 ),

is an operator. An encryption scheme is additive homomorphic if and E(m1 ) E(m2 ) = E(m1 + m2 ).

An encryption is scalarable if c = E(m) can be mapped randomly to a ciphertext c = E(km) or E(mk ) for a random k. The ElGamal encryption scheme is a multiplicative homomorphic encryption scheme with the scalaring property. For e?ciency of computation, we modify the scheme so that each decryption takes 1 modular exponentiation. This modi?cation does not a?ect the security of the scheme. Let r ∈R S denote that r is chosen from S uniformly and independently. - Key generation: Let p = 2q + 1, where p and q are both primes. Let Gq be the subgroup QRp and g is a generator of Gq . The public key is h = g?α , where α ∈ Zq is the corresponding private key. 3

- Encryption: The encryption of message m ∈ Gq is a pair E(m) = (a, b) = (gr , mhr ), where r ∈R Zq . - Decryption: For a ciphertext c = (a, b), the message is computed from D(c) = b × aα = m. - Scalaring: We can scalarize a ciphertext c = E(m) = (a, b) by computing c = E(mk ) = (ak , bk ) for k ∈R Zq . If m = 1, the scalaring operation does not change the content of encryption. The ElGamal encryption scheme is multiplicative homomorphic since E(m1 ) E(m2 ) = (gr1 , m1 hr1 ) (gr2 , m2 hr2 )

= (gr1 +r2 , (m1 × m2 )hr1 +r2 ) = E(m1 × m2 )

The security of ElGamal scheme is based on the DDH assumption, which states that it is computationally infeasible to distinguish the following two distribution ensembles: - D = (ga , gb , gab ), where a, b ∈R Zq . - R = (ga , gb , gc ), where a, b, c ∈R Zq . If we only need an encryption of a random number, we need not choose a random number and encrypt it. This costs an encryption time. Instead, we choose a random pair c = (a, b) ∈R G2 , which is an encryption of some random number. q By this technique, we save the encryption cost, which is crucial to the e?ciency of our GT protocol. The Paillier encryption scheme is additive homomorphic, which is as follows: - Key generation: Let N = pq be the RSA-modulus and g be an integer of order αN modulo N 2 for some integer α. The public key is (N, g) and the private key is λ(N ) = lcm((p ? 1), (q ? 1)). - Encryption: The encryption of message m ∈ ZN is E(m) = gm r N mod ? modN 2 , where r ∈R ZN . - Decryption: For ciphertext c, the message is computed from m= L(cλ(N ) mod N 2 ) , L(gλ(N ) mod N 2 )

where L(u) = u?1 . N - Scalaring: For ciphertext c = E(m), the scalaring is done by computing c = ? E(km) = ck for k ∈ ZN . If m = 0, the scalaring operation does not change the content of encryption. 4

The security of the scheme is based on the CRA (Composite Residuosity assumption, which states that it is computationally infeasible to distinguish whether ? an element z ∈ ZN 2 is an n-residue or not. The scheme is additive homomorphic since E(m1 )

N E(m2 ) = (gm1 r1 ) · (gm2 r2 N )

= gm1 +m2 (r1 r2 )N = E(m1 + m2 ).

2.2

0-encoding and 1-encoding

The main idea of out construction is to reduce the GT problem to the set intersection problem. We use two special encodings, 0-encoding and 1-encoding. Let s = sn sn?1 ...s1 ∈ {0, 1}n be a binary string of length n. The 0-encoding 0 of s is the set Ss of binary strings such that

0 Ss = {sn sn?1 ...si+1 1|si = 0, 1 ≤ i ≤ n} 1 The 1-encoding of s is the set Ss of binary strings such that 1 Ss = {sn sn?1 ...si |si = 1, 1 ≤ i ≤ n} 1 0 Both Ss and Ss have at most n elements. 1 0 If we encode x into its 1-encoding Sx and y into its 0-encoding Sy , we can see that 1 0 x > y if and only if Sx and Sy has a common element.

We give an example. Let x = 7 = 1112 and y = 2 = 0102 of length 3 (we ?ll in the 1 0 1 0 leading zeros.) We have Sx = {1, 11, 111} and Sy = {1, 011}. Since Sx ∩ Sy = ?, 1 we have x > y indeed. If x = 2 = 0102 and y = 7 = 1112 , we have Sx = {01} and 0 = {}. Since S 1 ∩ S 0 = ?, we have x ≤ y. Sy x y 1 0 We note that the strings in Sx have a pre?x relation and the strings in Sy also have a pre?x relation when removing the last bit. Our protocol exploits this relation.

1 0 Theorem 1. x is greater than y if and only if Sx and Sy have a common element.

Proof. Let x = xn xn?1 ...x1 ∈ {0, 1}n and y = yn yn?1 ...y1 ∈ {0, 1}n . For the forward direction, we can see that if x > y, there is a position i such that xi = 1 1 and yi = 0, and for all j, n ≥ j > i, xj = yj . We have xn xn?1 . . . xi ∈ Sx by 0 1 0 1-encoding and yn yn?1 · · · yi+1 1 ∈ Sy by 0-encoding. Thus, Sx and Sy have a common element. 1 0 For the backward direction, let t = tn tn?1 ...ti ∈ Sx ∩ Sy for some ti = 1. 1, x x 0, y y ? Since t ∈ Sx n n?1 . . . xi = tn tn?1 . . . ti , and since t ∈ Sy n n?1 . . . yi+1 yi = tn tn?1 . . . ti . We can see that x > y. 5

3

Our Protocol

1 0 If Alice and Bob compare the elements in Sx and Sy one by one, it would 2 ) comparisons. Nevertheless, they can only compare the corresponding need O(n 1 0 strings of the same length (if both of them exist) in Sx and Sy . This reduces the number of comparison to O(n). Let (G, E, D) be a multiplicative homomorphic encryption scheme. Alice uses a 2 × n-table T [i, j], i ∈ {0, 1}, 1 ≤ j ≤ n, to denote its input x = xn xn?1 · · · x1 with x T [xj , j] = E(1) and T [?j , j] = E(r) for some random r ∈ Gq .

Since Alice need not know r (each entry uses a distinct r), she randomly selects (ai , bi ) ∈ G2 for E(r). When Bob wants to compare a string t = tn tn?1 · · · ti in q 0 1 Sy with the corresponding string of the same length in Sx , he computes ct = T [tn , n] T [tn?1 , n ? 1] · · · T [ti , i].

1 We can see that ct is an encryption of 1 if and only if t ∈ Sx except with a 0 negligible probability of incorrectness. Furthermore, since strings in Sy have some sort of pre?x relations, Bob can compute all ct ’s in at most 2n homomorphic operations, instead of n2 homomorphic operation. Based on the previous discussion, our GT protocol is as follows:

1. Alice with private input x = xn xn?1 · · · x1 does the following: – run G to choose a key pair (pk, sk) for (E, D). – prepare a 2 × n-table T [i, j], T [i, j], i ∈ {0, 1}, 1 ≤ j ≤ n, such that x T [xi , i] = E(1) and T [?i , i] = E(ri ) for some random ri ∈ Gq – send T to Bob. 2. Bob with private input y = yn yn?1 · · · y1 does the following: 0 – for each t = tn tn?1 · · · ti ∈ Sy , compute ct = T [tn , n] T [tn?1 , n ? 1] · · · T [ti , i].

0 – prepare l = n ? |Sy | random encryptions zj = (aj , bj ) ∈ G2 , 1 ≤ j ≤ l. q – scalarize ct ’s and permutate ct ’s and zj ’s randomly as c1 , c2 , . . . , cn . – send c1 , c2 , . . . , cn to Alice. 3. Alice decrypts mi = D(ci ), 1 ≤ i ≤ n, and determine x > y if and only if some mi = 1.

When x ≤ y, there is a negligible probability that our GT protocol returns a wrong answer due to randomization. Our GT protocol can use additive homomorphic encryption. We only replace E(1) by E(0) in setting up the table T . In the end, Alice determines x > y if and only if some mi = 0. 6

3.1

Correctness and Security

Theorem 2. The protocol constructed as above is a solution to the GT problem. Proof. (sketch) We can verify correctness easily. The 1-encoding set of x is embedded into the table T . The 0-encoding set of y is computed by Bob directly. If there is a common element in both sets, some ci = E(1) by the previous discussion. Otherwise, no such ci = E(1) exists. Alice’s privacy is based on the security of the homomorphic encryption scheme. ? Assume that a polynomial-time bounded adversary B, acting as Bob, can distinguish the holdings x and x of Alice with a non-negligible probability. Let Tx and Tx be the tables sent by Alice when holding x and x , respectively. By tri? angular inequality, B can distinguish the entries of Tx [i, j] and Tx [i, j] for some i and j. Then, the adversary can distinguish messages m1 = D(Tx [i, j]) and m2 = D(Tx [i, j]), which is a contradiction. For Bob’s privacy, we construct a simulator SimB for the view of Alice. SimB takes as the inputs the comparison result b ∈ {0, 1} and Alice’s private input x. SimB uses x to construct the table T for the ?rst step. For the second step, SimB generates the sequence c1 , c2 , . . . , cn according to the result value b. If b = 1, SimB generates n ? 1 random encryptions and one encryption of 1 and randomly permutates them as c1 , c2 , . . . , cn . If b = 0, SimB generates n random encryptions as c1 , c2 , . . . , cn . We can see that the transcript of simulation and that of real execution are identical. Thus, Alice cannot compute Bob’s private input y except knowing its relation with x. 3.2 E?ciency

In this analysis, the base encryption scheme is the ElGamal scheme. Let p be the modulus. Computation Complexity. Let n be the length of the private inputs. We neglect the cost of choosing random numbers. The cost of choosing a public key pair for Alice is neglected also since this can be done in the setup stage. We don’t count the cost of selecting keys in other protocols, either. 0 In Step 1, Alice encrypts n 1 s. In Step 2, Bob computes ct , t ∈ Sy , by reusing intermediate values. This takes (2n ? 3) multiplications of ciphertexts at most. Step 2 uses n scalaring operations at most. In Step 3, Alice decrypts n ciphertexts. To compare fairly, we convert all operations to the number of modular multiplications. For the ElGamal scheme, each encryption takes 2 log p modular multiplications, each decryption takes log p modular multiplications, and each scalaring operation takes 2 log p modular multiplications. Overall, our GT protocol needs 5n log p + 4n ? 6 (= n × 2 log p + 2 × (2n ? 3) + n × 2 log p + n × log p) modular multiplications. Communication complexity. The size of exchanged messages between Alice and Bob is the size of T and c1 , c2 , . . . , cn , which is 6n log p (= 3n × 2 log p) bits. 7

4

Other protocols

For readability, we review the protocols in [BK04,Fis01]. 4.1 Fischlin’s GT protocol

Fischlin’s GT protocol [Fis01] uses the GM-encryption scheme and a modi?ed GM-encryption. The GM-encryption scheme is as follows: - Key generation: Let N = pq be the RSA-modulus and z be a quadratic non? residue of Zn with Jacobi symbol +1. The public key is (N, z) and the secret key is (p, q). ? - Encryption: For a bit b, the encryption is E(b) = z r r 2 mod N , where r ∈R ZN . - Decryption: For a ciphertext c, its plaintext is 1 if and only if c is a quadratic non-residue. If c is a quadratic residue in ZN , c is a quadratic residue in both ? ? Zp and Zq . - xor-property: E(b1 )E(b2 ) = E(b1 ⊕ b2 ) - not-property: E(b) × z = E(b ⊕ 1) = E(? b) - re-randomization: we can re-randomize a ciphertext c by multiplying an encrytion of 0. Modi?ed GM-encryption. To get the AND-homomorphic property, we need modify the GM encryption: - Encryption: For encrypt a bit b = 1, E AN D (b) is a sequence of quadratic residues. If b = 0, E AN D (b) is a sequence of quadratic residues and nonresidues. The length of the sequence is determined by a parameter λ. - Decryption: For decrypting a ciphertext, we need check quadratic residusoity of all elements in the ciphertext. - AND-property: For two ciphertext E AN D (b1 ) and E AN D (b2 ), their product is computed by multiplying elements pairwisely. The product of two ciphertexts is an encryption of b1 AND b2 . Protocol and E?ciency. The protocol in [Fis01] uses the properties of the GMand modi?ed-GM-encrytion schemes. For computation, the protocol needs n GM-encryptions and n modi?ed GMdecryptions in the client side (Alice in our protocol).1 The server side (Bob in our protocol) needs n modi?ed GM-encryptions and 4nλ modular multiplications only, which is very e?cient. The exchanged messages are n GM-ciphertexts and n modi?ed GM-ciphertexts. Overall, the size is (1 + λ)n log N (= n log N + nλ log N ) bits.

1

In [Fis01], the computation cost of the client side is neglected.

8

4.2

Blake and Kolesnikov’s GT protocol

The GT protocol in [BK04] is based on the Paillier’s encryption scheme. The additive homomorphic property is essential to their construction. In the protocol, the receiver (Alice) needs n encryptions and n decryptions. The sender (Bob) needs n modular multiplications in the 2a step, n modular multiplications and n inversions in the 2b step, 2n modular multiplications in the 2c step, and (2 + log N )n modular multiplications in the 2d step. The cost of inversion in the step 2b is neglected. However, in our opinion, it should not be neglected. Each inversion takes n modular exempli?cations. Overall, the protocol needs 6n modular exponentiations (modN 2 ) and 6n modular multiplication (modN 2 ) The communication cost is n ciphertexts for the receiver and n ciphertexts for the sender. The overall communication cost is 4n log N bits

5

Comparison

Now, we compare our GT protocol with those in [Fis01,BK04] in computation and communication cost. We summarize the cost of operations for the protocols: - Each GM-encryption needs at most 2 modular multiplications (modN ). - Each modi?ed GM-encryption needs at most 2λ modular multiplication ( mod N ) since each encryption contains λ GM-encryptions. - Each modi?ed GM-decryption needs at most λ log N (= λ(log p + log q)) modular multiplications (modN ). There are λ elements in a modi?ed GMciphertext. Each decryption need check quadratic residuosity for each element. ? ? Quadratic residuosity is checked over both Zp and Zq . - Each Paillier’s encryption requires 2 log N modular multiplications ( mod N 2 ). - Each Paillier’s decryption requires 2 log N modular multiplications ( mod N 2 ). - Each Paillier’s inversion requires at most 2 log N modular multiplications ( mod N 2 ), where the inversion is done by the extended Euclidean algorithm. - For Paillier’s encryption, each modular multiplication modN 2 needs 4 modular multiplication modN . Based on the above discussion, we summarize the comparison in Table 1. In the table, the modular multiplication for the protocols in [Fis01,BK04] is mod N and ours is modp. If we set log N = 1024 and log p = 512 (this is very conservative), our protocol saves at least 89.6% computation cost and 25% communication cost.

6

Remarks

Our construction is secure in the semi-honest setting. In the malicious setting, each round requires additional messages to assure legality of the sent messages. 9

Ours [Fis01] [BK04]

computation of Alice computation of Bob total computation communication 3n log p 2n log p + 4n ? 6 5n log p + 4n ? 6 6n log p λn log N + 3n 6nλ λn log N + 6nλ + 3n (1 + λ)n log N 12n log N 12n log N + 24n 24n log N + 24n 4n log N

*computation cost is measured in the number of modular multiplication *communication cost is measured in bits *Alice is called ”receiver” in [BK04] and ”client” in [Fis01]. *λ is set to 40 ? 50 in [Fis01] Table 1. Comparison in computation cost and communication cost.

The techniques are mostly based on non-interactive zero-knowledge proof of knowledge. We shall present a GT protocol which is secure in the malicious setting in the ?nal version.

References

[BK04] Ian F. Blake and Vladimir Kolesnikov. Strong conditional oblivious transfer and computing on intervals. In Proceedings of Advances in Cryptology - ASIACRYPT ’04, volume 3329 of LNCS, pages 515–529. Springer-Verlag, 2004. [Fis01] Marc Fischlin. A cost-e?ective pay-per-multiplication comparison method for millionaires. In Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer’s Track at RSA, volume 2020 of LNCS, pages 457–472. Springer-Verlag, 2001. [FNP04] Michael J. Freedman, Kobbi Nissim, and Benny Pinkas. E?cient private matching and set intersection. In Proceedings of Advances in Cryptology - EUROCRYPT ’04, volume 3027 of LNCS, pages 1–19. Springer-Verlag, 2004. [GMW87] O. Goldreich, S. Micali, and A. Wigderson. How to play and mental game. In Proceedings of the 16th Annual ACM Symposium on the Theory of Computing (STOC ’87), pages 218–229. ACM, 1987. [IG03] Ioannis Ioannidis and Ananth Grama. An e?cient protocol for yao’s millionaires’ problem. In Proceedings of the 36th Hawaii Internatinal Conference on System Sciences 2003, 2003. [ST04] Berry Schoenmakers and Pim Tuyls. Pratical two-party computation based on the conditional gate. In Proceedings of Advances in Cryptology - ASIACRYPT ’04, volume 3329 of LNCS, pages 119–136. Springer-Verlag, 2004. [Yao82] A. C. Yao. Protocols for secure computations. In Proceedings of 23th Annual Symposium on Foundations of Computer Science (FOCS ’82), pages 160–164. IEEE, 1982. [Yao86] A. C. Yao. How to generate and exchange secrets. In Proceedings of 27th Annual Symposium on Foundations of Computer Science (FOCS ’86), pages 162–167. IEEE, 1986.

10