{'fraction_non_alphanumeric': 0.03783116622176297, 'fraction_numerical': 0.013806366428427912, 'mean_word_length': 3.9971313826735515, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 26, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Two and Three-Party Digital Goods Auctions: Scalable Privacy Analysis

A digital goods auction is a type of auction where potential buyers bid the maximal price that they are willing to pay for a certain item, which a seller can produce at a negligible cost and in unlimited quantity. To maximise her benefits, the aim for the seller is to find the optimal sales price, which every buyer whose bid is not lower will pay. For fairness and privacy purposes, buyers may be concerned about protecting the confidentiality of their bids. Secure Multi-Party Computation is a domain of Cryptography that would allow the seller to compute the optimal sales price while guaranteeing that the bids remain secret. Paradoxically, as a function of the buyers' bids, the sales price inevitably reveals some private information. Generic frameworks and entropy-based techniques based on Quantitative Information Flow have been developed in order to quantify and restrict those leakages. Due to their combinatorial nature, these techniques do not scale to large input spaces. In this work, we aim at scaling those privacy analyses to large input spaces in the particular case of digital goods auctions. We derive closed-form formulas for the posterior min-entropy of private inputs in two and three-party auctions, which enables us to effectively quantify the information leaks for arbitrarily large input spaces. We also provide supportive experimental evidence that enables us to formulate a conjecture that would allow us to extend our results to any number of parties.


Introduction
Secure Multi-Party Computation (SMC) [27,23] is a paradigm which enables several parties to compute a public function of their own private inputs without ever disclosing their private input. Secure protocols that allow participants to compute such functions require them to share specific pieces of information through different rounds of communication intertwined with local computations, with the aim of guaranteeing the concealment of private values. Specifically, they ensure that no information flows about the private inputs, apart from that which can be inferred from the intended public output. From that notion of security, it follows that the output of any sensible secure computation will reveal some information about the private inputs. Although cryptographic protocols have been extensively studied and optimised in the past decades in order to improve their speed and efficiency, this leakage is considered inevitable and is commonly referred to as the acceptable leakage in the literature, and has thus been largely ignored so far [17,20,13,8].
We believe however, that this is a questionable position and that it is of interest -and of importance -to raise participants' awareness of this leakage before they decide to engage in an SMC protocol, and to offer them the opportunity to gauge, by themselves, the risk that they would run by entering a computation, rather than imposing this leakage on them. More precisely, we believe that an SMC participant may be concerned by the following questions: is this leakage really acceptable? Is not this statement subjective? Are there objective ways of assessing the acceptability of such leakage, that each person could interpret based on her own expectations? Finally, is this leakage really inevitable? Under which conditions? Some recent works have aimed at proposing some possible answers to those questions. A framework based on Quantitative Information Flow allows one to quantify this acceptable leakage, where the inputs' privacy is evaluated via general entropy-based measures [1,2,3]. These measures allow participants to have an objective way of measuring the risks that taking part in a computation would present. These entropybased measured are generic and can be parametrised so as to capture individual privacy requirements and expectations. Based on this model, different randomising techniques have been proposed in order to enhance participants' privacy while guaranteeing high utility [2,6].
The principle behind those methods is to select a notion of entropy and measure the inputs' privacy via the conditional entropy of an input given the knowledge of the public output. Evaluating the value of those entropy measures requires to browse the whole input space and yields a complexity that is linear in the size of the total input domain. Their combinatorial essence thus does not allow those methods to scale to large inputs spaces. It has been shown that this complexity can be reduced for particular theoretical cases such as for three-party affine computations [4,5], which allows those methods to scale to large input spaces. Being able to apply these methods to real-world problem requires the possibility to adapt them to real-world functions, and to large input spaces.
The aim of this work is to focus on a particular practical application of SMC, namely the digital goods auctions, and to scale those privacy analyses to arbitrarily large input spaces. More precisely, we aim at reducing the complexity of those analyses by deriving a closed-form formula for the input's posterior minentropy in the case of two-party auctions, thus providing a way for assessing the acceptable leakage in two party auctions for any input size. We then notice that deriving a closed-form formula for this entropy is more involved in the presence of three parties. However, as the generic empirical methods are able to compute this entropy for small input spaces, we are mostly interested in evaluating this entropy for large input spaces. For three-party auctions, we thus focus on deriving an asymptotic development of this entropy for large input spaces. Finally, we provide supportive experimental evidence that help us to formulate a conjecture on the asymptotic behaviour of this entropy for large input spaces with any number of parties.
This paper is outlined a follows. We discuss some related works in Section 2. We introduce relevant background in Section 3. The digital goods auctions are presented in Section 4. Section 5 focuses on twoparty auctions while three-party auctions are tackled in Section 6. Our conjecture is supported and formulated in Section 7. We discuss our work in Section 8 and conclude in Section 9.

Related Works
In this section, we present some relevant domains of cryptography and discuss their relation to our work.
Secure Multi-party Computation. Secure Multi-party Computation [28,27,23,21,9,12] is a domain of Cryptography that provides advanced protocols which enable several participants to compute a public function of their own private inputs without having to rely on any other trusted third party or any external authority. Those protocols enable the participants to compute a function in a decentralised manner, while ensuring that no information leaks about the private inputs, other than what can be inferred from the public output. The commonly called "acceptable leakage" which is further studied in this paper, is the information that can be inferred by an attacker about the private inputs given the knowledge of the public output alone.
Secure Multi-Party Computation is not the only domain that is subject to an acceptable leakage. In particular, the results of our work are also applicable to other fields or scenarios that aim at protecting the inputs' privacy and that involve the opening of a public output, such as outsourced computation where a trusted third party is privately sent all the inputs and returns the public output as unique piece of information, or trusted computing where the parties input their secret data into hardware security modules, which then ensure that no unintended information will be accessible to the other parties.
We emphasise the fact that our work focuses on the acceptable leakage that may occur in SMC, trusted computing or outsourced computations, and is thus largely orthogonal to the technicalities that SMC protocols may involve.
Differential Privacy. Differential Privacy (DP) [14,15] formalises privacy concerns and introduces techniques that provide users of a database with the assurance that their personal details will not have a significant impact on the output of the queries performed on the database. More precisely, it proposes mechanisms which ensure that the outcome of the queries performed on two databases differing in at most one element will be statistically indistinguishable. Moreover, minimising the distortion of the outcome of the queries while ensuring privacy is an important trade-off that governs DP.
Although DP is particularly suited for quantifying -and enhancing -privacy in statistical computations involving a large number of parties, its usefulness diminishes when a small number of parties are involved in the computation, or when the output of the computation is meant to be highly dependent on every input value. In a vote or in an auction for example, it would not be sensible to evaluate the privacy of inputs by how independent they are of the output. In general multi-party computations, independence between the output and the inputs is not a desirable property, and we thus need a more meaningful way of quantifying the inputs' privacy, which we discuss in the next paragraph.
Quantitative Information Flow. The purpose of Quantitative Information Flow (QIF) [25,18] is to provide frameworks and techniques based on information theory and probability theory for measuring the amount of information that leaks from a secret. Different mathematical concepts have emerged in order to convey varied and precise information about a secret: Shannon entropy [24] reflects the minimum number of binary questions required to recover a secret on average, while the min-entropy is an indicator of the probability to guess a secret in one try [26,11,25]. Richer measures such as Rényi entropy [22] and the g-entropy [7] have been introduced in order to quantify some specific properties of a secret. Generalised entropies have been proposed in order to unify those different concepts [2,16].
In this work, we will measure the information gained by an attacker by means of min-entropy, which is used extensively in Cryptography in order to quantify the vulnerability of a secret. Although we selected the conditional min-entropy in order to propose a measure of privacy that can be meaningful in SMC, we believe that it would be interesting to extend and compare our approach to other notions of entropy and possibly other methods for quantifying privacy.

Background
Let us now present the mathematical model [1,2] that we will use to study the notion of privacy in SMC.
Let n be a positive integer. Let x 1 , . . . , x n be n integers, belonging to n different parties P 1 , . . . , P n respectively. Let us assume that these parties wish to enter the secure computation of an n-ary function f and to compute its output o = f (x 1 , . . . , x n ).
We are interested in studying the information that opening the output reveals about private inputs. More precisely, let us assume that we wish to study the information that leaks about private input x j . We call it targeted input, while the other inputs are called spectators' inputs. To this end, we consider each input x i as a random variable X i taking values in a domain D i . The output is also assigned a random variable O defined as a composition of random variables O = f (X 1 , . . . , X n ). Its domain is denoted by D O .
Then the privacy of targeted input X j will be quantified as the conditional min-entropy of X j given O, defined as: where the conditional vulnerability V(X j | O) is defined as: For clarity purposes, we will abuse notation and omit the domains in the summations, and omit the random variable name in the probability notations, when they can be obviously inferred from context. This way, the above vulnerability rewrites as V( We now formulate an assumption that will hold throughout the paper. By virtue of Bayes' theorem and Assumption 1, the vulnerability from Equation (1) can be rewritten as: We recall that all the values of p(o | x) can be computed in O(m n ), the max can be computed in O(m) and the sum in O(m n ), which quickly becomes intractable as the input size m grows. We thus seek a closed-form formula for H(X | O). In the next section, we present the function f that is considered in this paper. Sections 5 and 6 then focus on simplifying the expression of V for this precise function f . More precisely, we derive a closed-form formula for V for two-party auctions. Following the same approach, we notice that deriving an exact formula would be more involved in the three-party case. However, our main objective is to be able to provide analyses that scale to large input spaces, since empirical, combinatorial, analyses are already able to compute exact values of V for small input spaces -and fail to do so for large ones. We then decide to focus on deriving the asymptotic behaviour of V for large values of m in three-party auctions.

Digital Goods Auctions
Auctions are part of the practical use cases that can benefit from the security properties provided by Secure Multi-Party Computation. In fact, and as an aside, one of the first practical applications of SMC implemented on a large scale was an auction between several Danish farmers and a producer [10]. Indeed, depending on the setting and the rules of the auction, participants may be interested in keeping their bids private in order to protect their economic interests. Resorting to SMC might also enhance fairness between participants and may provide other reassuring guarantees that may be lacking in a traditional auction. A non-exhaustive list of such guarantees are: • The confidentiality of the bids protects the participants' economic position from both the auctioneer and the other participants.
• Protocols that are secure under active adversaries may guarantee the participants that the result has not been falsified. In comparison with traditional methods, this prevents the polling authority from being involved in any kind of corruption.
• In some cases, SMC may offer the benefit that bids from different participants are taken into account simultaneously, whereas some traditional auction types may not.
Although SMC provides the participants with a way of entering all their inputs once and simultaneously, and importantly, without revealing their bids, we know that some information will leak about private bids.
In this work, we study a particular case of auctions, known as digital goods auctions. This application has also been chosen as a case study in influential papers on Differential Privacy such as McSherry and Talwar's paper on the exponential mechanism [19]. Let us introduce the principle of a digital goods auction, and explain the different pieces of private information that are being manipulated and the public information that is revealed during such auctions.
A digital goods auction involves one seller and n buyers. A seller has an unlimited supply of a certain item or good, that she wants to sell. Each buyer will either buy the item, or refuse to buy it. In particular, a buyer will not buy the item several times. Each buyer P i will bid a price x i , which is the maximal price that he is willing to pay to buy the item. If the sales price p of the item is greater than x i , then buyer P i will not buy the item. If p is not greater than x i , then P i will pay the price p to get the item, which will turn into benefits for the seller. We assume that the seller did not pay anything to acquire the items, so that her total benefits -also referred to as budget or profit -will equal pb where p is the sales price of the item and b is the number of buyers who can afford it, i.e. b = |{i ∈ 1; n | x i ≥ p}|. The aim of the auction is to determine the optimal sales price of the item that maximises the seller's benefits. As an aside, if the seller's profits can be maximised with different values of p, then we define the auction as retaining the lowest value of p, as it will satisfy more participants. The computation of the optimal price of the item can be represented as the following function f described in Algorithm 1: sort x i 's in descending order such that x 1 ≥ · · · ≥ x n 3: k ← argmax j j · x j (choose largest possible k) 4: Choosing the largest possible k means that if the same budget is attainable with different sales prices, we choose the one which enables more participants to buy, e.g. f (1, 1, 4, 1) = 1 where the maximal budget Table 1: Outputs of the two-party auction with maximal input m = 9.
x y 1 2 3 4 5 6 7 8 9   1 1 1 3 4 5 6 7 8 9  2 1 2 2 2 5 6 7 8 9  3 3 2 3 3 3 3 7 8 9  4 4 2 3 4 4 4 4 4 9  5 5 5 3 4 5 5 5 5 5  6 6 6 3 4 5 6 6 6 6  7 7 7 7 4 5 6 7 7 7  8 8 8 8 4 5 6 7 8 8  9 9 9 9 9 5 6 7 8 9 can equally be achieved with a sales price of 1 or 4, but the former allows 4 participants to buy whereas the latter allows only one. It is worth noting that the output o = f (x 1 , . . . , x n ) necessarily equals one of the input values x i . We can show that the price is not optimal otherwise. Naturally, the buyers' bids x i constitute private pieces of information that the buyers do not wish to reveal: neither the other buyers nor the seller should be able to learn any information about a particular bid x i before the opening of the final price p. In order to guarantee such a level of privacy, the participants can for example enter an SMC protocol, or resort to a Trusted Execution Environment.
On the other hand, the sales price p is the information that is intended to be computed and to be made public. As such, it inevitably reveals some information about the private bids, which is commonly referred to as the acceptable leakage in the SMC literature. One may wish to gauge this acceptable leakage, and in particular may wonder whether this leakage is tolerable in a two-party auction.
The aim of the work reported in this paper is to quantify the information that flows about the private bids when the result of the auction -i.e. the sales price -is revealed. More precisely, we aim at deriving a method for quantifying the bids' privacy that is scalable to arbitrarily large input spaces, which previous generic methods were not able to accommodate. Precisely, we now aim at simplifying the expression of p(o | x) from Equation (2), where x represents one targeted input in order to be able to compute it for large values of m.

Two-Party Auctions
In a two-party auction, the function f can be simplified. It is straightforward to see that the sorting procedure and the argmax function can be written as in the following Algorithm 2.

Algorithm 2 Two-party auction function f
Inputs: x, y ∈ 1; m Output: Sales price p ∈ {x, y} if x > y then 3: if x > 2y then return x else return x In order to illustrate and reason about the results of such a function, let us assume that m = 9 and let us plot the function's outputs on the 2-dimensional array in Table 1.
Let us now look at the quantity that we wish to compute. In order to compute H(X | O), we will compute max x p(o | x) for each output o. To do so, we argue that for each output o, we have max x p(o | x) = p(O =  For that reason, we have: max and thus: where | · | denotes the cardinality of a set. We can now illustrate in Table 2(a) the result of that sum by highlighting in colour all the cells that satisfy the condition f (o, y) = o. We gather all the inputs satisfying this condition in a set that we define as S = {(x, y) ∈ 1; m 2 | f (x, y) = x}. Red cells correspond to the cases where x > y while blue cells to those where x ≤ y: The aim is thus to compute the number of coloured cells, which equals the desired values of o |{y | f (o, y) = o}|. To do this, we present the following geometric interpretation. Let us "transpose" all the cells highlighted in blue. By transposing a cell at location (i, j), we mean discolouring this cell and then colouring its symmetric one at location (j, i). We obtain the array depicted in Proof. As we argued in Equation (3), we know that: It thus suffices to compute the cardinality of the following set S: Let us express S as the disjoint union of the following two subsets: We note that S 1 corresponds to the area highlighted in red in Table 2(a), and S 2 corresponds to the blue area. The additional ordering on x and y ensures that {S 1 , S 2 } forms a partition of S and thus |S| = |S 1 |+|S 2 |.
We can swap both coordinates of the elements of S 2 without altering its cardinality. We thus have |S 2 | = |S ′ 2 | where we define S ′ 2 as follows: On the other hand, we have: We can see that S 1 and S ′ 2 are disjoint and thus |S 1 | + |S ′ 2 | = |S 1 ∪ S ′ 2 |. This union can be rewritten as: from which we can infer that and thus: We also checked that this formula is experimentally validated by our programs computing H(X | O) empirically.
As we are particularly interested in studying the behaviour of H(X | O) for large input spaces, we formulate the following corollary. Proof. This is an immediate consequence of Theorem 1.

Algorithm 3 Three-party auction function f
Inputs: x, y, z ∈ 1; m Output: Sales price p ∈ {x, y, z} if 2y > 3z then return y 6: else return z

Three-Party Auctions
Let us now consider the case where three parties enter an auction. Algorithm f is adapted in the following Algorithm 3. We can see that once the inputs have been sorted, the program simply consists in finding the maximum of x, 2y and 3z. Before computing V, let us introduce some useful results that we will need in this section.

Preliminaries
Let us generalise a result that we hinted at in the previous section, and that will be of importance in deriving an algebraic expression for H(X | O). We claim that substituting the value of one of the inputs to the value of the output does not change the output of f .

Lemma 1. Let {x i } i be a set of n inputs and let o be a value. Then we have:
Proof. Let us introduce a few notations in order to develop this proof. Let {x i } i be a set of n inputs and let o and o ′ two values such that: where we will refer to Equation (5) to scenario 1 while Equation (6) will be referred to as scenario 2. For sake of convenience, let us introduce another set of inputs {x ′ i } i which we define as: ∀i ∈ 2; n : so that we can write f (x ′ 1 , . . . , x ′ n ) = o ′ . Let S and S ′ be two subsets of 1; n defined as: In other words, S and S ′ represent the sets of parties that will get to buy the item in an auction involving the sets of inputs {x i } i and {x ′ i } i respectively. Let b and b ′ be the seller's benefits in both scenarios, defined as: Finally, for input set {ξ i } i , subset σ ⊆ 1; n and value ω, we say that the triple ( We can notice that if ({ξ i } i , σ, ω) is qualified, then the seller's benefits in an auction involving inputs {ξ i } i will be no lower than |σ| · ω.
The intuition of the proof follows. First, there is nothing to show when o = x 1 . We will prove that if o < x 1 , then b ′ = b as o is the optimal price for scenario 2. If o > x 1 , we will argue that b ′ = b + o which can only be achieved for o ′ = o. Case 1. Let us assume that o < x 1 . We first argue that b ′ = b.
In this case, we have Let us now argue that o ′ = o. We know that b ′ can be achieved with a sales price of o. As the auction function f favours lower sales prices for the same seller's benefits, we know that o ′ ≤ o.
Let us assume by contradiction that o ′ < o. As argued before, we know that Moreover, we know that for all subset By assumption, this implies: and thus: This implies that 1 / ∈ S ′ and thus ({x i }, S ′ , o ′ ) is qualified, which means that b ≥ b ′ , which is a contradiction.
In conclusion, we have b ′ = b + o. Let us now argue that o ′ = o.
We have already mentioned that b ′ can be achieved with a sales price of o, and thus o ′ ≤ o. Let us assume by contradiction that o ′ < o. Then we know that 1 ∈ S ′ (since x ′ 1 = o). We also know that as As assumed by proof by contradiction that o ′ < o, we thus have b > b ′ − o and thus: which is a contradiction, which concludes the case and the proof.
We also recall a result that will be useful for studying the asymptotic behaviour of H(X | O).
Proof. We recall that we have: n k=1 k = n(n + 1) 2 n k=1 k 2 = n(n + 1)(2n + 1) 6 Thus for all positive integer c no larger than n, we have: And thus as a and b are no larger than n: where we note that the bounds of the indices in the sums are allowed to differ by 1 since the difference is compensated in the O(n) and O(n 2 ) terms.

Deriving an Expression for the Input Vulnerability
We are now interested in computing the value of V. For this, we argue again that max Indeed, we know that for fixed values of o and x, we have: where we note that in this 3-party setting, the pair (y, z) plays the role of the spectators' input, which comprises two inputs y and z. However, Lemma 1 ensures that: and thus Equation (2) becomes: The aim is thus now to compute the above sum, which can be written as the cardinality of the following set S: S = {(x, y, z) | f (x, y, z) = x} which can be written as the following disjoint union: where for all x we define: Let us partition each set S x into the following four subsets, that correspond to the different possible input orderings: We note that S 1 corresponds to the cases where x 1 is the largest of x, y and z, S 2 and S 3 includes the cases where x 1 is the middle element and S 4 depicts the cases where x 1 is the smallest item.
Let x be in 1; m . It is immediate to see that {S x 1 , . . . , S x 4 } forms a partition of S x and thus |S x | = |S x 1 | + · · · + |S x 4 |, and furthermore |S| = x |S x |. Let us thus focus on the cardinality of those four subsets. Case 1. Let y and z be in 1; m such that: x > y ∧ x > z and let us study the membership of (x, y, z) in S x 1 . We have: In order to tally the number of different pairs (y, z) that satisfy those conditions, it is helpful to rewrite those systems as the following disjunction: The three disjuncts above are disjoint, and the last two disjuncts are symmetrical in y and z. We can thus express the cardinality of S x 1 as: Case 2 and 3. Let us now study the cardinality of S x 2 . Let y and z be in 1; m such that: y ≥ x > z and let us study the membership of (x, y, z) in S x 1 . We have: We can thus express the cardinality of S x 2 depending on which side of n, value 2x is. If 2x ≤ m, then: If 2x > m, then: By symmetry on y and z, we also have |S x 3 | = |S x 2 |. Case 4. Let us now take y and z in 1; m such that: x ≤ y ∧ x ≤ z and let us study the membership of (x, y, z) in S x 4 . We have: Rewriting those conditions as disjoint cases, we get: Let us treat those 3 disjoint disjunctions separately. Let c x 1 , c x 2 and c x 3 denote the number of different triples (x, y, z) that satisfy the three above systems respectively, i.e. that: Let us focus on c x 1 first. If 3 2 x ≤ m, then: Otherwise, if 3 2 x > m, then: Let us now focus on c x 2 .
And by symmetry on y and z, we have c Let us recall that we wished to compute the cardinality of set S in order to fulfil our original aim which was to compute input x's vulnerability V. We have now derived the cardinality of each subset S x i for all i in 1; 4 and for all x in 1; m . Moreover, we have intentionally expressed S as a disjoint union so that: The expression that we can derive for |S| in this way involves sums with ceilings and floorings and would thus not immediately lead to a closed-form formula that can be computed in constant time. Indeed, combining Equations (10), (11), (12), (13), (14) and (15) provides us with a closed-form expression for |S x 1 | + · · · + |S x 4 | for any fixed value of x in 1; m . Equation (16) then allows us to compute the cardinality |S| by summing those m expressions, which allows us to compute |S| in O(m) time.
However, we recall that for small input spaces, we already have a combinatorial way of computing vulnerability V, and that our major problem is to scale our analyses to large input spaces, which is specifically where the combinatorial method fails to scale.
For that reason, in the remainder of this report, we will aim at deriving a closed-form formula for the asymptotic behaviour of |S| for large values of input size m.

Asymptotic Behaviour of the Input Vulnerability
In order to do so, we will study the asymptotic behaviour, when m tends towards infinity, of |S x i | and x |S x i | for all i in 1; 4 in order to be able to compute that of |S| and thus of V. In this section, the asymptotic behaviour of the cardinality of a set, say S, will refer to the asymptotic behaviour of |S| when expressed as a function of m, when m tends towards infinity.
Let us consider again the expression of |S x 1 | obtained in Equation (10) and let us study its asymptotic behaviour when m is large. We note that x is an integer ranged in 1; m and is thus a O(m). By simplifying the ceiling in the first factor, we have: Case 1. We now recall the entire expression of |S x 1 | obtained in Equation (10) and proceed with a similar reasoning: We thus obtain: Case 2 and 3. Let us now study the case of |S x 2 |. Based on Equations (11), then if 2x ≤ m, we have: Similarly, if 2x > m, then Equation (12) becomes: And thus: where we note again that the bounds of the indices in the sums are allowed to differ by 1 since the difference is compensated in the O(n 2 ) term. Let us compute each term separately. Using the results recalled in Lemma 2, we have: Combining the previous two terms, we get: Conclusion. And finally: Given this analysis, we can now formulate our main result for 3-party auctions.
Theorem 2. We have: Proof. Equation (9) and (17) yield: and manipulating asymptotic developments yields: It follows that H(X | O) converges when m tends toward infinity and its limit is stated in the following result. Proof. This is an immediate consequence of Theorem 2.
We note that a more precise approximation of V and H(X | O) can be obtained by bounding the cardinality of the subsets involved in the computation of |S| with upper and lower bounds. In particular, each flooring and ceiling can be approximated with a range of width 1, and so more involved computation would lead to a more precise result.
The results obtained so far led us to conjecture on the asymptotic vulnerability of a targeted input in a general n-party auction.

Conjecture for Multi-Party Auctions
Let n be a positive integer and let us consider an n-party auction. Let m be a positive integer that represents the input size. Let us consider n inputs x 1 , . . . , x n and we recall that the computation of the output of the auction is modelled by function f .
In light of Corollaries 1 and 2, we formulate the following conjecture. We note that this conjecture is also verified when n = 1 since in the presence of a single party, we have H(X | O) = 0. The results derived in Corollaries 1 and 2 are also consistent with this conjecture. In this section, we provide more evidence which supports our intuition.
Let us first generalise a notion introduced in Equation (9) that will enable us to express the vulnerability more conveniently. Definition 1. We define function c n : N * → N for all positive integer m as: c n (m) = |{(x 1 , . . . , x n ) ∈ 1; m n | f (x 1 , . . . , x n ) = x 1 }| As discussed in Section 6, we can easily prove that V = cn(m) m n . The difficulty resides in computing c n (m) for large values of m.
Let us first formulate a second conjecture on the shape of function c n . This will help us to reason about its asymptotic behaviour more precisely.

Conjecture 2.
There exists a positive rational number a n in Q such that: c n (m) = a n · m n + O(m n−1 ) We can see in Section 6 from the way that c n (m) is constructed that it will comply with the shape aforementioned.
Conjecture 1 is now equivalent to the fact that a n = 1 n , for which we will show some empirical supportive evidence. We emphasise the fact that the following reasoning is empirical and does not constitute a proof.
As Conjecture 2 suggests that function c n behaves like a polynomial of degree n for large values of m, we decided to try and interpolate function c with a polynomial of degree at most n via its first 30 values c n (1), . . . , c n (30) which we computed empirically. Let us plot the first 30 values of c n that we computed for n = 2, . . . , 5. Based on those 20 values, we performed a polynomial regression with a polynomial of degree n respectively, and with a least squares method. The respective interpolating polynomials P 2 , . . . , P 5 that we empirically obtain are displayed below: P 2 = 0.5x 2 + 0.5x P 3 = 0.3334x 3 + 0.6649x 2 + 0.3577x − 0.1987 P 4 = 0.2499x 4 + 0.7671x 3 + 0.3552x 2 + 1.267x − 2.231 P 5 = 0.1995x 5 + 0.8503x 4 − 0.6201x 3 + 14.77x 2 − 62.27x + 64. 15 where coefficients have been reported with 4 significant figures.
By looking at the coefficients of highest degree in the above polynomials, we can see that the empirical values thus obtained for a n are indeed very close to 1 n , which supports our Conjecture 1.

Discussion
The results obtained and conjectured in this paper suggest that the computational power that an attacker may have should somehow play a role in our approach. Similarly to the differences that have been formally defined between information-theoretic security and computational security in a cryptographic protocol, we may also identify similar nuances in privacy. For example, let us assume that our Conjecture 1 is correct and that the vulnerability of one input in an n-party auction converges towards 1 n when the input size m tends to infinity. This would be a poor privacy guarantee, since the prior vulnerability of one input is 1 m , and m is much larger than n. However, this 1 n limit would be a theoretical value: this means that in theory, an attacker learning the output of an auction has on average a 1 n probability of guessing one input in one try if he selects the best guess. But in reality, an attacker with limited computational power might not be able to select the best guess that would offer him a 1 n probability of guessing the secret. Our empirical method for computing c n (m) -that does not scale to large input spaces -does provide, along with the exact value of c n (m), the best guessing strategy that achieves the expected vulnerability as it explicitly chooses the best guess.     However, in the 3-party auction, we solely proved that for a large value of m, the input's vulnerability would be close to 1 3 . In particular, we were unable to provide a way for an attacker to select the best guessing strategy given the auction's output.
One might thus be interested in considering the potential difference that may exist between the theoretical vulnerability and the computational vulnerability of a secret.