More efficient comparison protocols for MPC

More efficient comparison protocols

Yao introduced the problem of comparing two private values, thereby launching the study of protocols for secure multi-party computation (MPC). Since then, comparison protocols have undergone extensive study and found widespread applications. We survey state-of-the-art comparison protocols for an arbitrary number of parties, decompose them into smaller primitives and analyse their communication complexity under the usual assumption that the underlying MPC protocol does preprocessing and computes linear operations without communi cation. We then develop two new comparison protocols and explain why they are faster than similar protocols, including those that are commonly used in practice: they reduce the number of online multi plications, without increasing preprocessing or round complexity. More concretely, online bandwidth is reduced by more than half for the standard comparison protocols whose round complexity is logarithmic in the bit-length, whereas for constant round comparison protocols the reduction is two-thirds. 1 Introduction In 1982, Yao introduced the problem of comparing two private values in a privacy-preserving manner, now known as “Yao’s Millionaires’ problem” [48]. Over time this led to the development of many secure multi-party computation (MPC) protocols, which enable a group to jointly perform a computation without disclosing any private inputs [31]. Originally most MPC protocols would carry out a generic computation by rewriting it as a Boolean circuit or an arithmetic circuit, and then execute each addition (or XOR) and multiplication gate in this circuit using certain subprotocols. As many practical computations involve secure comparisons (which securely determine whether one secret integer is larger than another one) and secure fixed-point or f loating-point arithmetic, many MPC protocols subsequently developed specialised subprotocols to handle those subcomputations as efficiently as possible. Moreover, almost all practical MPC protocols nowadays tend to compute addition gates without re quiring any communication; this includes those protocols that use linear secret sharing schemes (LSSS) such as Shamir’s secret sharing [47,11,30,25,32] and additive secret sharing like SPDZ [26,10,37]. Real-world applications of LSSS-based MPC protocols involving secure comparisons and secure fixed-point arithmetic include:– Auctions. The first ever large-scale MPC application happened in 2008, when the bids of 1229 farmers in the Danish beet market were encrypted in order to protect their (financial) privacy [15], and the market clearing price was determined by comparing these secret bids. A more advanced version of the same platform was later used by the Norwegian 1800 MHz Spectrum Auction to trade approximately US$ 100 million in spectrum rights [3].– Descriptive statistics. The first wide area network deployment of MPC came in 2010, when the Estonian IT industry consortium wanted to gather sensitive data for a market survey; the published analysis re quired sorting of private data and division [14]. Later in Denmark, banks computed credit score analyses of farmers using confidential accounting data [21]. Another example is the Boston wage gap MPC com putation by the Boston Women’s Workforce Council, demonstrating that the wage gap is larger than previously estimated by the U.S. Bureau of Labor Statistics [39].1– Evidence-based policy making. In 2015, Estonian statisticians looked for correlations between working during university studies and failing to graduate in time. This required combining private tax and education data [13]. 1 Here the contents of certain cells were only revealed if a certain threshold was met. – Fraud detection. In 2015, the Estonian Tax and Customs Board estimated VAT tax fraud by comparing detailed but confidential purchase and sales data between companies [12].– Biometric authentication. Unlike ordinary passwords, biometric identifiers tend to be hard to change once compromised. Consequently, biometric authentication services are sometimes deployed with MPC; typically the underlying algorithm determines whether the distance between two feature vectors is below some threshold (e.g. [8, §6.2.3] or [1]). Nevertheless, the deployment of MPC protocols to perform such computations still leads to serious efficiency penalties, and research efforts have focused on improving the performance of the underlying primitives. In contemporary MPC literature on secure comparison [45,18,40,22,41,27,7] and fixed- [19,18,27] and floating point arithmetic [6,35,17] protocols for groups of arbitrary size n ≥ 3, they all largely reduce to subprotocols which compare the bits of a secret integer with the bits of a nonsecret integer. Sometimes these subprotocols already vary in their outward properties (e.g. offering statistical rather than perfect privacy), and sometimes the differences are all hidden “under the hood”. Even in the latter case, a careful deconstruction can already lead to performance improvements. For example, while most LSSS-based MPC protocols convert generic functions to (generalisations of) arithmetic circuits in some domain Z/mZ with m > 2, comparing two integers usually comes down to comparing bits which is more naturally a binary operation. This leads to two different approaches: perform this bitwise comparison computation entirely inside of the original arithmetic domain Z/mZ, or employ random values which are secret shared in both the original domain and in (an extension of) the binary domain Z/2Z (e.g. [28]) to do the computation inside the latter domain, before transforming it back to the arithmetic domain again. The former approach is taken by [45,40,27], and the latter by [22,41,7]. Nevertheless, the two binary bit comparison protocols of [22,41] differ ([7] reuses the latter); while both protocols were selected from [18] (which has protocols for either domain) and are functionally interchangeable, one will outperform the other one due to having significantly lower communication complexity, whilst [7] should use neither. Similarly, [45] notes that his comparison protocol can be improved in communication complexity by mak ing the underlying bit comparison protocol (which itself cannot be deployed over Z/2Z) compare “two bits at a time”. It appears that this idea was forgotten by the literature since then; we explain that it also speeds up the state-of-the-art bit comparison circuit of [29], regardless of domain, and provide an in-depth analysis of the consequences for communication complexity when comparing ν ≥ 1 bits “simultaneously”. Setting ν = 2 indeed improves both online and total bandwidth, but for most situations ν = 3 or ν = 4 is even better for the bit comparison protocol of [45]. In this paper, we present two new (bit)comparison protocols, both of which can be finetuned by a parameter ν ≥ 1. In their respective sections, we explain why they are faster and more efficient than similar protocols in the MPC literature. In the appendices we also recall and make slight tweaks to other families of comparison protocols. A rough guide to choosing between secure comparison protocols for any LSSS-based MPC protocol with preprocessing could be as follows:– If the round complexity is the primary bottleneck, the fastest protocol might be P3R,ν LessThan; in the setting of honest majority MPC it should be executable within 3 rounds, and within 4 rounds otherwise. A default setting here might be ν = 3, possibly increasing it to ν = 4 for lower online bandwidth or lowering it to ν =2 for slightly lower total bandwidth (see Table 3).– If a round complexity of roughly ⌈log2 ℓ⌉ is acceptable when comparing two values of bit-length ℓ, then the protocol of PlogR,ν LessThan should yield the lowest total bandwidth of all protocols considered when ν = 2, see Table 1. Its online bitwise comparison component and some of its preprocessing can be executed over a small field (employing say [28]) for even lower offline and much lower online bandwidth (assuming n is not too large). Our contributions (i) We carefully deconstruct the comparison protocols of [45,18,40,22,41,27,7], explaining their commonal ities and differences. 2 (ii) We present a constant-round secure comparison protocol P3R,ν LessThan with communication complexity linear in the number of bits, based on the ideas of [45] and the 3-round protocol [18, LTZC1]. Compared to the latter, the offline bandwidth is typically lower and it only uses a third of the online bandwidth when ν =3 (see Table 3). (iii) We present a secure comparison protocol PlogR,ν LessThan whose round complexity is logarithmic and band width complexity is linear in the number of bits, based on [29]. It costs one round fewer than similar protocols [18, LTZL] and [29,22,41,27] (which are the comparison protocols used most often in practice for LSSS-based MPC) and has less than half the online banwidth, whilst typically also slightly lowering total bandwidth (see Table 4). If one were to model the underlying MPC protocol with its access structure as an arithmetic black-box FABB [24] providing security (possibly with abort) against an active or passive adversary, and also describe the secure comparison operation as an ideal functionality FComparison in the UC framework [16], a more formal security statement is as follows: Theorem 1. The protocols P3R,ν LessThan and PlogR,ν LessThan information-theoretically UC-realise FComparison in the FABB-hybrid model against an adversary corrupting an authorised subset of parties. 2 Notation– All logarithms are base 2, unless specified otherwise. The set of natural numbers without zero is denoted N1, the set of integers by Z.– The arithmetic computation domain is denoted Z/mZ, for some integer m. Traditionally m was assumed to be prime [47], but Shamir’s secret sharing scheme is increasingly deployed for m nonprime (e.g. [5,4]).– In addition to the usual linear operations, multiplication PMult and reveal PReveal subprotocols, the underlying MPC protocol may have a special “public multiplication” subprotocol PPubMult (which given secret sharings [x] and [y] publicly outputs the value xy), rather than naively composing PMult with PReveal; to the best of our knowledge this notion first appeared in [18]. If the MPC protocol is say UC secure [16], then so are the protocols in this paper since they only reveal values that have been shifted by random numbers.– [·] denotes a secret shared value the underlying MPC protocol can securely perform all of its usual operations on, e.g. in the context of threshold secret sharing it is a sharing of degree t, where t is the maximum number of adversaries. · denotes a sharing on which linear operations and reveals are possible but not necessarily multiplications; in the same context it could denote a sharing of any degree less than the number of parties n. We set N := ⌈logn⌉.– We let ℓ := ⌈log(m−1)⌉ denote the bit-length of m−1, so that 2ℓ−1 < m ≤ 2ℓ. Unless statistical slack is used (e.g. [18]) this value will be only slightly larger than the bit-length of the inputs x,x′ for the comparison subprotocols. For bandwidth computations we implicitly assume that m is close to 2ℓ, so that the cost of constructing a bitwise shared random number is roughly the same as the cost of constructing ℓ bits when using e.g. [46]. We write L := ⌈logℓ⌉.– The arity of certain bit operations is denoted by ν ∈ N1, and we write ℓν := ⌈ℓ/ν⌉ ≈ ℓ/ν. We use a superscript • in the notation of protocols to denote two parameters: their round complexity and this arity ν.– The least significant bit of an element z ∈ Z/mZ is denoted z1, the next one by z2, etc., so that z = ℓ i=12i−1zi. We let [z]bit denote a bitwise sharing, i.e. a sharing of all of the bits of z; implicitly we may assume that a sharing of z is included as well. This is generalised by [z]ν-bit, which reduces to [z]bit in the case ν = 1; see Notation 43. 3 Survey of comparison protocols In this section we survey state-of-the-art secure comparison protocols for an arbitrary number of parties; recall that the problem is to compute a sharing [x < x′] of the Boolean x < x′ from a pair of secret sharings 3 x, x′ of integers x,x′ ∈ Z. In the setting of honest majority threshold LSSS, allowing the degree of these sharings to be larger than t+1 here can reduce a round of communication when one (or both) of the inputs are obtained as for example the output of a multiplication or inner product gate. The comparison problem is usually reduced to comparing a public value c with a secret random value whose bits are secret-shared in some domain, typically either the original domain or (some extension of) Z/2Z. For simplicity we will refer to such a secret as a bitwise-shared, and to such a comparison as a bitwise comparison. The only exception to this approach that we’re aware of is [38, §II.B], but that protocol has some issues; see Appendix B. Originally, comparison protocols used an expensive online bit decomposition protocol [23]; shortly after wards, it was noticed that this can often be replaced with a “shifted bit decomposition” [42], as follows: Protocol ShiftedBitDecomp (z +r,[r]ν-bit) ←− PShiftedBitDecomp z ,ν

1. The nodes retrieve from preprocessing a bitwise sharing [r]ν-bit, and locally compute z +r := z +[r].

2. The nodes then reveal this value: z + r ← PReveal(z +r ). Fig.1: Protocol to compute a shifted bit decomposition of a shared value 3.1 Range and the arithmetic domain In practice the integers x and x′ are usually restricted to lie inside some range of integers [xmin,xmax) ⊂ Z of size s := xmax − xmin; typical choices are the unsigned integers in the range [0,2k) and signed integers in the range [−2k−1,2k−1), for some natural number k ∈ N1. This range is subsequently embedded by the underlying arithmetic MPC protocol into the ring Z/mZ through the natural projection map [xmin, xmax) −→ Z −↠ Z/mZ ∼ = [0,...,m). The comparison subprotocol then usually has one of the following two properties: (1) (i) It is capable of computing [z < z′] for all elements z,z′ in [0,...,m); by shifting the range of [xmin,xmax) with xmin just before the start of this subprotocol, any [x < x′] can then be computed as long as s ≤ m.– [42, §6.3] does this at the cost of three bitwise shared secret random values, three parallel bitwise comparisons followed by two consecutive multiplications; they require that m is prime but this condition is not necessary.– [41, ΠLTS] costs two bitwise shared secret random values, three parallel bitwise comparisons and a binary adder. If their binary adder is moved to preprocessing their preprocessing cost will be slightly higher than [42, §6.3], but require a few less online rounds. Their correctness is probabilistic if m is not a power of 2. (ii) It is capable of computing [z < z′] for all elements z,z′ within a range of size m − 2ℓ−1 or m/2. Depending on m and privacy requirements, these protocols only cost 1 or 2 two bitwise shared secret random values plus bitwise comparisons, rather than 3.