Начиная с начала 2000 года осуществляется внедрение GHIS в здравоохранении, в рамках принятого проекта о реформирование информ Mathematical Problems of Computer Science 45, 59--66, 2016. Secure Multiparty Computations for Collaboration between Competing Service Providers Davit H. Danoyan Yerevan State University e-mail: danoyan@gmail.com Abstract We introduce a platform for secure computations and describe the platform workflow. We detail the Golreich-Micalli-Widgerson protocol employed for secure multiparty computation in our platform with optimization techniques applied to it. Being based on white-box cryptography, the underlying oblivious transfer protocol avoids the use of expensive public key operations and provides good overhead compared to similar systems. Also we point out some useful application scenarios and provide a real world application design based on our platform. Keywords: Secure multiparty computation, Oblivious transfer, White-box cryptography 1. Introduction Secure computations were introduced by Yao in [19] searching a solution to the Millionaires problem, where two millionaires want to find out who is the richest of them without revealing to each other or any other party of their actual property. Years later several approaches were developed for the solution of this problem and its generalized version with 𝑛𝑛 millionaires as Yao’s garbled circuit based protocol [12], GMW [18] and others. Although those protocols were valid solutions for the problem, the computational resources available at that time were insufficient for using them in practice. The first practical implementation of a secure computation protocol was presented in [1] nearly a decade ago. Later, several enhancements and new implementations have been developed [2]. Many applications were proposed for online auctions [5], e-commerce [7], data mining [6], secure computations outsourcing [4], etc. In this paper we present a new application scenario, where several service providers possessing specific private information wish to make secure computations on their collective data. In section 2 we will present some background on the GMW multiparty computation protocol and our optimization techniques. Section 3 will be the brief description of our platform used for the secure computations in the specific application. The applications’ motivation and description can be found in section 4 and section 5 is the conclusion of this paper. 59 60 Secure Multiparty Computations for Collaboration between Competing Service Providers 2. GMW Protocol The GMW protocol is intended for computation of any function that is possible to represent as a single pass Boolean circuit, where the permitted operations (circuit gates) are 𝑋𝑋𝑋𝑋𝑋𝑋 and 𝐴𝐴𝐴𝐴𝐴𝐴. As the protocol avoids the need of trusted third parties, communication is required between all pairs of participants. Unlike the Yao’s garbled circuits protocol, where one party is the circuit generator and the other party is the circuit evaluator, here all the parties possess the circuit locally and each of them plays an evaluator with input shares of himself and the other participants. 2.1 Secret Sharing Each party generates 𝑛𝑛 shares for each input wire 𝑤𝑤 (𝑠𝑠𝑤𝑤1, … , 𝑠𝑠𝑤𝑤𝑤𝑤) randomly so, that ⊕𝑖𝑖=1 𝑤𝑤 𝑠𝑠𝑤𝑤𝑖𝑖 = 𝑠𝑠𝑤𝑤. Share generation doesn’t really require much effort to satisfy the above equation. Party 𝑃𝑃𝑗𝑗 generates n-1 shares randomly for all other parties 𝑃𝑃𝑖𝑖, 𝑖𝑖 ≠ 𝑗𝑗. To comply with the equation, it just has to adjust its own share correspondingly - 𝑠𝑠𝑤𝑤𝑗𝑗 = (⊕i≠j 𝑠𝑠𝑤𝑤𝑖𝑖) ⊕ 𝑠𝑠𝑤𝑤. After the share generation, each share 𝑠𝑠𝑤𝑤𝑖𝑖 is sent to the corresponding participant 𝑃𝑃𝑖𝑖. Now, having shares for all input wires, each participant proceeds to circuit evaluation. After the evaluation, each participant 𝑃𝑃𝑖𝑖 would have its own value 𝑠𝑠𝑤𝑤𝑖𝑖, so for each output wire 𝑤𝑤 of the circuit we again will have an n-tuple (𝑠𝑠𝑤𝑤1, … , 𝑠𝑠𝑤𝑤𝑤𝑤). To combine those values into a single value for each wire the protocol suggests a specific way of gate evaluation, according to which the n- tuples for each output wire will play as shares of parties, and the final value will be computed with 𝑠𝑠𝑤𝑤 = ⊕𝑖𝑖=1 𝑤𝑤 𝑠𝑠𝑤𝑤𝑖𝑖 formula. As the circuit consists of XOR and AND gates only, below we provide the methods for both gates’ evaluation that should be used for all input, intermediate and output gates of the circuit and show that they operate as expected. 2.2 Gate Evaluation Evaluation of 𝑋𝑋𝑋𝑋𝑋𝑋 gates. Suppose we have an 𝑋𝑋𝑋𝑋𝑋𝑋 gate with input wires 𝑢𝑢 and 𝑣𝑣 and an output wire 𝑤𝑤. All parties already have their shares for the input wires (𝑠𝑠𝑢𝑢1, … , 𝑠𝑠𝑢𝑢𝑤𝑤) and (𝑠𝑠𝑣𝑣1, … , 𝑠𝑠𝑣𝑣𝑤𝑤). Each party 𝑃𝑃𝑖𝑖 computes the value of the output wire in the following way: 𝑠𝑠𝑤𝑤𝑖𝑖 = 𝑠𝑠𝑢𝑢𝑖𝑖 ⊕ 𝑠𝑠𝑣𝑣𝑖𝑖 . The 𝑛𝑛-tuple (𝑠𝑠𝑤𝑤1, … , 𝑠𝑠𝑤𝑤𝑤𝑤) would be a valid sharing for 𝑤𝑤’s value, because 𝑠𝑠𝑤𝑤 = ⊕𝑖𝑖=1 𝑤𝑤 𝑠𝑠𝑤𝑤𝑖𝑖 = ⊕𝑖𝑖=1 𝑤𝑤 (𝑠𝑠𝑢𝑢𝑖𝑖 ⊕ 𝑠𝑠𝑣𝑣𝑖𝑖) = (⊕𝑖𝑖=1 𝑤𝑤 𝑠𝑠𝑢𝑢𝑖𝑖) ⊕ ( ⊕𝑖𝑖=1 𝑤𝑤 𝑠𝑠𝑣𝑣𝑖𝑖) = 𝑠𝑠𝑢𝑢 ⊕ 𝑠𝑠𝑣𝑣. Evaluation of 𝐴𝐴𝐴𝐴𝐴𝐴 gates Suppose we have an 𝐴𝐴𝐴𝐴𝐴𝐴 gate with input wires 𝑢𝑢 and 𝑣𝑣 and an output wire 𝑤𝑤. The shares of input values of 𝑢𝑢 and 𝑣𝑣 are (𝑠𝑠𝑢𝑢1, … , 𝑠𝑠𝑢𝑢𝑤𝑤) and (𝑠𝑠𝑣𝑣1, … , 𝑠𝑠𝑣𝑣𝑤𝑤). The output value 𝑠𝑠𝑤𝑤 should be computed so, that 𝑠𝑠𝑤𝑤 = 𝑠𝑠𝑢𝑢 ∧ 𝑠𝑠𝑣𝑣 = (⊕𝑖𝑖=1 𝑤𝑤 𝑠𝑠𝑢𝑢𝑖𝑖) ∧ ( ⊕𝑖𝑖=1 𝑤𝑤 𝑠𝑠𝑣𝑣𝑖𝑖) = = (⊕𝑖𝑖=1 𝑤𝑤 (𝑠𝑠𝑢𝑢𝑖𝑖 ∧ 𝑠𝑠𝑣𝑣𝑖𝑖)) ⊕ (⊕𝑖𝑖<𝑗𝑗 ((𝑠𝑠𝑢𝑢𝑖𝑖 ∧ 𝑠𝑠𝑣𝑣𝑗𝑗) ⊕ (𝑠𝑠𝑢𝑢𝑗𝑗 ∧ 𝑠𝑠𝑣𝑣𝑖𝑖))). The first sum ⊕𝑖𝑖=1 𝑤𝑤 (𝑠𝑠𝑢𝑢𝑖𝑖 ∧ 𝑠𝑠𝑣𝑣𝑖𝑖) can be computed locally for every participant, but for evaluation of the second sum one should communicate with other participants. To avoid the collection of individual shares of other parties, oblivious transfer protocols are used for 𝐴𝐴𝐴𝐴𝐴𝐴 gate evaluation in the following way. D. Danoyan 61 As 𝑃𝑃𝑖𝑖 has to interact with several 𝑃𝑃𝑗𝑗-s to compute each element of ⊕𝑖𝑖<𝑗𝑗 ��𝑠𝑠𝑢𝑢𝑖𝑖 ∧ 𝑠𝑠𝑣𝑣𝑗𝑗� ⊕ �𝑠𝑠𝑢𝑢𝑗𝑗 ∧ 𝑠𝑠𝑣𝑣𝑖𝑖��, 𝑃𝑃𝑗𝑗 generates a random value 𝑟𝑟𝑗𝑗 {𝑖𝑖,𝑗𝑗} and composes four values with 𝑟𝑟𝑗𝑗 {𝑖𝑖,𝑗𝑗} and its shares for input wires of the gate being computed 𝑠𝑠𝑢𝑢𝑗𝑗 and 𝑠𝑠𝑣𝑣𝑗𝑗. 𝑟𝑟𝑗𝑗 {𝑖𝑖,𝑗𝑗}, 𝑟𝑟𝑗𝑗 {𝑖𝑖,𝑗𝑗} ⊕ 𝑠𝑠𝑢𝑢𝑗𝑗 , 𝑟𝑟𝑗𝑗 {𝑖𝑖,𝑗𝑗} ⊕ 𝑠𝑠𝑣𝑣𝑗𝑗, 𝑟𝑟𝑗𝑗 {𝑖𝑖,𝑗𝑗} ⊕ 𝑠𝑠𝑢𝑢𝑗𝑗 ⊕ 𝑠𝑠𝑣𝑣𝑗𝑗. Then the parties invoke a 1 − 𝑜𝑜𝑢𝑢𝑜𝑜 − 𝑜𝑜𝑜𝑜 − 4 oblivious transfer with 𝑃𝑃𝑖𝑖 as receiver and 𝑃𝑃𝑗𝑗 as sender. 𝑃𝑃𝑖𝑖 requests one of the abovementioned values with its index composed of its shares for the input wires 𝑠𝑠𝑢𝑢𝑖𝑖, 𝑠𝑠𝑣𝑣𝑖𝑖. 𝑃𝑃𝑖𝑖 computes the required sum with the received value 𝑟𝑟𝑖𝑖 {𝑖𝑖,𝑗𝑗} 𝑟𝑟𝑖𝑖 {𝑖𝑖,𝑗𝑗} ⊕ 𝑟𝑟𝑗𝑗 {𝑖𝑖,𝑗𝑗} = (𝑠𝑠𝑢𝑢𝑖𝑖 ∧ 𝑠𝑠𝑣𝑣𝑗𝑗) ⊕ (𝑠𝑠𝑢𝑢𝑗𝑗 ∧ 𝑠𝑠𝑣𝑣𝑖𝑖). The proof of correctness of the 𝐴𝐴𝐴𝐴𝐴𝐴 gates’ computation method described above can be found in section 7.5.2.2 of [3]. So 𝑃𝑃𝑖𝑖, after getting all 𝑟𝑟𝑗𝑗 {𝑖𝑖,𝑗𝑗}-s from all parties with 𝑗𝑗 > 𝑖𝑖, can compute its share for the output wire 𝑤𝑤. 𝑠𝑠𝑤𝑤𝑖𝑖 = (𝑠𝑠𝑢𝑢𝑖𝑖 ∧ 𝑠𝑠𝑣𝑣𝑖𝑖) ⊕ (⊕𝑖𝑖<𝑗𝑗 ��𝑠𝑠𝑢𝑢𝑖𝑖 ∧ 𝑠𝑠𝑣𝑣𝑗𝑗� ⊕ �𝑠𝑠𝑢𝑢𝑗𝑗 ∧ 𝑠𝑠𝑣𝑣𝑖𝑖��. Given the methods of share based evaluation of both type gates, each party computes the circuits’ output value shares. The computation of the full value of an output wire can be done after each participant sends the result of its computations to others. Note, that computation of an 𝑋𝑋𝑋𝑋𝑋𝑋 gate share values is free in terms of network communication and almost free, in terms of computation (𝑛𝑛 𝑋𝑋𝑋𝑋𝑋𝑋 operation). However, the computation of 𝐴𝐴𝐴𝐴𝐴𝐴 gates takes � 𝑛𝑛 2� OT invocations. 2.3 Optimizations White-Box Oblivious Transfer Oblivious transfer is an essential cryptographic primitive heavily used in secure computations. It was introduced by Rabin in [13] as a protocol where the sender sends a message to the receiver with 1 2 probability and does not reveal if the receiver got the message or not. A modified version of this protocol was introduced later by Even et al. in [14], currently known as the basic 1-out-of- 2 OT protocol. This protocol assumes that the receiver has a selection bit 𝑠𝑠𝑠𝑠{0,1} and the sender has two bits 𝑚𝑚0, 𝑚𝑚1𝑠𝑠{0,1} . After protocol execution the receiver gets 𝑚𝑚𝑠𝑠 and nothing about 𝑚𝑚1−𝑠𝑠 and the sender does not reveal 𝑠𝑠. Unfortunately this protocol depends on public-key operations, which require exponentiation operations which are pretty expensive, considering the huge amount of OT operations required for secure computations (in Yao’s protocol OTs are used for all input bits of one of the participants, in GMW OTs are used for all 𝐴𝐴𝐴𝐴𝐴𝐴 gates). In [11] a new approach to OT was introduced using white-box cryptography techniques instead of public-key operations, allowing to reduce cost of an OT in several orders of magnitude, in case of many invocations, as reported. WBOT extension 62 Secure Multiparty Computations for Collaboration between Competing Service Providers Another optimization technique for reducing the OT invocation count is OT extension introduced by Beaver in [17] and later enhanced in [16]. We have constructed similar optimization for white-box OT, allowing to reduce the required OT invocation count to a predetermined fixed number. The details of the extension can be found in [8]. 2.4 GMW Protocol Extension Here we introduce an extended version of the GMW protocol, that enables involvement of so called passive parties that don’t participate in the computation process, while having input and expecting output. Suppose 𝑛𝑛 + 𝑚𝑚 parties wish to compute a common function based on private inputs, only 𝑚𝑚 of which are passive. In this scenario we suggest the active (participating in computation) parties to behave as they do in the original protocol and share their inputs among 𝑛𝑛 active parties with the method described in section 2.2. Each passive participant also generates 𝑛𝑛 shares for each of its input, but doesn’t keep a share for himself and distributes all shares among the active parties. The latter compute the function based on the secret shares as in the original protocol and distribute output shares among all parties. The security requirement for this protocol are also different – here we require at least one non-corrupted active party. 3. Platform Description The platform processes a file containing a program described in an imperative language for to be computed by the participants. Beside the function description the file contains specification on the intended inputs and expected outputs. The program defines computations in a manner they would be carried out by a virtual trusted party possessing all input parameters. Our platform consist of three main modules – a compiler, and two modules responsible for two-party and multiparty secure computations respectively. Below we briefly describe the main modules. Compiler We implemented a compiler generating an equivalent Boolean circuit on basis { 𝐴𝐴𝐴𝐴𝐴𝐴, 𝑋𝑋𝑋𝑋𝑋𝑋, 1 } implementing the described function. The compiler generates an initial Boolean circuit and passes it through various stages of optimizations trying to minimize the number of gates in generated circuit. Another major goal of the compiler is the minimization of 𝐴𝐴𝐴𝐴𝐴𝐴 gates and circuit depth. For this purpose we use low depth circuit constructions developed mainly for VLSI applications. To deal with large circuits efficiently, the compiler generates a file containing the usage count for each gate. When a gate is processed, by a participant, the initial usage count is read from this file, and each time the output of the gate is accessed, the associated counter is decremented. Data associated with the gate is removed from memory once the counter hits zero. In this way we minimize the number of gates simultaneously kept in memory during evaluation of the circuit. Two-Party Module Although it is possible to perform secure computations with two participants using GMW protocol, in our platform we have a specialized module for this task. For this purpose we have implemented Yao’s garbled circuits protocol [12]. The module works on the output of the compiler module. Detailed description can be found in [9]. D. Danoyan 63 Multiparty Module The multiparty module is intended for secure computations with more than 2 participants. The module implements the Goldreich-Micalli-Widgerson protocol[18] with several enhancements described in [15] and in the previous section. It also operates on a Boolean circuit outputted by the compiler module. 4. Applications Here we will describe the process of combining multiple delivery services into a unified platform that involves several members. In fact, the application described is suitable for using in different contexts like combining any delivery or transportation services where the members are service providers, who do not want to disclose their current locations or the locations they are available to cover within the fixed time to their competitors, but eager to cooperate with them to have their share in unified ordering system, thus increasing their order counts and service efficiency. Concerning the motivation of client to use the unified system, let’s compare the actions needed for getting the fastest service. In case of having an access to the unified application, the client just has to give the application her location and confirm the order. All the computation and decision processes are completed without the clients’ involvement. In absence of such a system one should contact several service providers (possibly with different interfaces), give them its location, compare the offers of different providers, find the best of them and finally put an order. In the latter case the client also has to trust the information it got from service providers. Suppose the service providers are taxi service companies with one or more cabs and the client has no priorities for choosing particular service other than fast pick-up. Taxi services do not want to make their locations visible to rival companies to avoid them getting advantage by better positioning of their cabs (for example, this can be done by a company with significantly more cabs). All cab locations are also hidden from the client, because a competitor can possibly act as a client to find out the others’ cab locations and get advantage. Having the application scenario described we show several methods as candidates for the secure computation itself. This methods are basically computing the minimum value of distances between a client as one point, and provider instances as candidates for the second point. Different distance measurement algorithms are presented below. The main purpose of this application is to find the nearest item in the unified database of locations to a submitted location. With the computation securing method already appointed, we still need to have accurate location detecting and network connection hardware for the service providers and individual cabs. In this work we consider the mentioned hardware implemented in a black-box manner – we do not consider their technical and efficiency details. We also assume that the computing parties have identical maps as well and their locations follow common coordinate system, to avoid misinterpretation of function arguments. Considering the distance measurement we have several methods as a candidate. Euclid Distance The most general version of the distance measurement function is computation of the Euclid distance between the customer and all the provider instances (e.g. cabs). With the coordinates given in two dimensional format, the customer’s location denoted as (𝑥𝑥𝑐𝑐, 𝑦𝑦𝑐𝑐) and for 𝑖𝑖-th provider instance (𝑥𝑥𝑖𝑖, 𝑦𝑦𝑖𝑖) considering m provider instances, the following function should be computed to determine the “winning” bid: min i