A Cost-Effective Pay-Per-Multiplication Comparison Method for Millionaires

Marc Fischlin

Fachbereich Mathematik (AG 7.2) Johann Wolfgang Goethe-Universität Frankfurt am Main Postfach 111932 60054 Frankfurt/Main, Germany

                   marc @ mi.informatik.uni-frankfurt.de
                http://www.mi.informatik.uni-frankfurt.de/

Abstract. Based on the quadratic residuosity assumption we present a non-interactive crypto-computing protocol for the greater-than function, i.e., a non-interactive procedure between two parties such that only the relation of the parties’ inputs is revealed. In comparison to previous solutions our protocol reduces the number of modular multiplications significantly. We also discuss applications to conditional oblivious transfer, private bidding and the millionaires’ problem.

1 Introduction

Yao’s famous millionaires’ problem [19, 20] consists of two millionaires trying to compare their riches but without disclosing their assets. General secure twoparty protocols computing the greater-than function GT(x, y) = [x > y] provide a solution to this problem [11, 20, 10].^{1} Unfortunately, these protocols are rather inefficient. Recently, Boudot et al. [2] proposed a quite efficient protocol for the socialist millionaires’ problem in which both parties test their inputs for equality only, i.e., compute the function EQ(x, y) = [x = y] securely. This scheme needs a (quite large, but) constant number of modular exponentiations, and improves the protocol of Jakobsson and Yung [15] requiring Θ(k) modular exponentiations for security parameter k.

Related to the millionaires’ problem is the problem of non-interactive cryptocomputing for the greater-than function which we address in this paper. A noninteractive crypto-computing protocol [18] is a two-party protocol where the client encrypts his input y and sends the encryption to the server. The server inattentively evaluates a secret circuit C on this encrypted input and returns it to the client. The client extracts the circuit’s output C(y) but learns nothing more about the circuit C. In the case of the millionaires’ problem think of the server’s circuit as computing the greater-than function with partially fixed input:

1 The predicate [x > y] stands for 1 if x > y and 0 otherwise —interpreting bit strings x, y as numbers.

C(·) = GT(x, ·). Keeping the circuit secret implies that nothing about the input x except for [x > y] is leaked.

As an application of such non-interactive crypto-computing consider a company that offers groceries or airline tickets over the Internet. The company tries to optimize its profit but is willing to sell an airline ticket above the breakeven point y. Hence, they ask the customer how much he would pay for the ticket, and if the customer’s offer x exceeds y then they clinch the deal. This, of course, requires that y is hidden or else the customer will simply set x to y + 1. On the other hand, the customer, too, would like to keep his offer x secret unless the deal is made and he has to reveal x anyway.

Using a non-interactive crypto-computing protocol the company plays the client and publishes its bound y by encrypting it. The customer computes the circuit for the greater-than function with his bid x and returns it to the company (along with a commitment of x). The company decrypts and verifies that x > y and, if so, declares that it sells and asks the customer to reveal his bid and to decommit. If the customer then refuses or decommits incorrectly then the company may blacklist him, at least for a certain time. Or, the customer is obliged to attach a signature to the commitment of x which binds him to his offer in case of a dispute.

In the example above, a ‘clever’ customer could simply find out the corporation’s bound y and buy for x = y + 1 by bidding 1, 2, 3, … until the company announces the deal. The most obvious countermeasure against such a behavior is to allow the customer to bid only once within a certain period (say, a couple of minutes for stocks, a week for flight tickets, etc). Alternatively, the offerer may raise the bound y with each failing bid of the customer. Details depend on the application.

General non-interactive crypto-computing protocols for various classes of circuits appear in [18, 1]. If one applies the general result in [18, 1] to compute the GT-function with the straightforward circuit (this circuit is also optimal when applying [18, 1], as far as we know) and using the quadratic-residuosity bitencryption of Goldwasser and Micali (see [12] or Section 2.1), then this requires at least n^{4} modular multiplications in ZZ_{N}^{∗} for inputs x, y ∈ {0, 1}^{n}. The general solutions in [5, 16, 4] involve Ω(n) modular exponentations with constants larger than 3 (and on the average therefore at least 4.5kn multiplications^{2} for security parameter k). Hence, as opposed to [18, 1] and, as we will see, to our solution, the computational complexity of the latter protocols depends on the length of security parameter and grows whenever we switch to larger k. For these protocols, k = 160 seems to be an appropriate choice today.

In contrast to the general approach in [18] our starting point is the logic formula describing the GT-function. As we will see, this formula can be converted into a protocol that utilizes the homomorphic operations supported by the Goldwasser-Micali system. For instance, we take advantage of the AND-

2 Neglecting preprocessing. Yet, preprocessing is not always applicable in these protocols. Futhermore, Naor et al. [16] accomplish the constant 3 in the random oracle model only; otherwise the bound becomes 5.

homomorphic variant of the Goldwasser-Micali scheme presented in [18]. To best of our knowledge this is the first application of this AND-homomorphic encryption scheme.

Our protocol takes at most 6nλ modular multiplications in ZZ_{N}^{∗} for the server and 2n for the client (once an RSA-modulus N has been generated and neglecting the less expensive effort for GM-decoding), where n is the bit length of each input x, y and λ determines the error of the protocol (the error is 5n · 2^{−λ}). Note that the number of multiplications in our protocol does not depend on k, but rather on the input length n and the absolute error parameter λ.

Allowing a small error of, say, 2^{−40}, for inputs of 15 bits our solution requires about 4, 000 multiplications for the server instead of 15^{4} ≈ 50, 000 as in [18, 1] and ≥ 10, 800 for [5, 16, 4] for k = 160. If we have 20-bit inputs (which occurs if we compare time data, for instance) then for error 2^{−40} our protocol needs 6, 000 multiplications for the server compared to 20^{4} = 160, 000 in [18, 1] or ≥ 14, 400 in [5, 16, 4].

Finally, we discuss consequences to related protocols. The first observation is that our protocol can also be applied to functions that reduce to the greater-than function, e.g., any comparison function that can be described by COMP_{a,b}(x, y) = [ax+b > y] for public constants a, b. In particular, the greateror-equal-to function equals GT(x + 1, y). This possibly increases the number of multiplications since the bit size of ax + b might be larger than n bits, yet the number of multiplications in our protocol grows quasi linear with the bit size for fixed error level.

Another interesting application of our non-interactive protocols are conditional oblivious transfer protocols. Introduced by Di Crescenzo et al. [7], with such a protocol, instead of obliviously transferring a bit b to a receiver with probability 1/2, the sender transfers the bit given that a predicate over additional private inputs x (of the sender) and y (of the receiver) is satisfied. We devise such a protocol for the greater-than predicate that, in contrast to the solution in [7], keeps the server’s input x secret. That is, the receiver learns the predicate [x > y] but nothing else about x, and moreover gets the bit b if and only if x > y. The sender, on the other side, does not learn anyhing about y and in particular does not come to know if b has been transferred. It is worth mentioning that we are not aware if the general non-interactive crypto-computing protocol in [18] for the greater-than function can be used to derive such an oblivious transfer protocol. See Section 4 for details.

As for further implications, we have already mentioned the connection to the millionaires’ problem and we elaborate further in Section 4.2. Aiming at a similar problem, we show how to construct improved private-bidding protocols with an oblivious third party [3]. These are protocols where two parties compare their bids. For this, a third party helps to compute the result and thereby guarantees fairness. Yet, the third party remains oblivious about the outcome of the bidding.

2 Preliminaries

We denote by ZZ_{N} the ring of intergers modulo N and by ZZ_{N}^{∗} the elements in ZZ_{N} relatively prime to N. Let ZZ_{N}^{∗}(+1) denote the subset of ZZ_{N}^{∗} that contains all elements with Jacobi symbol +1. By QR_{N} ⊂ ZZ_{N}^{∗}(+1) and QNR_{N} ⊂ ZZ_{N}^{∗}(+1) we refer to the quadratic residues and non-residues, respectively. See [14] for number-theoretic background.

In the sequel we write Enc(b, r) for the output of the encryption algorithm Enc for bit b and randomness r. Let Enc(b) denote the corrresponding random variable, and Enc_{0}(b) a fixed sample from Enc(b) (where the random string r is irrelevant to the context). We write c ← Enc(b) for the process of encrypting a bit b randomly and assigning the result to c.

We sometimes switch between bit strings and numbers in a straightforward way. That is, for a bit string x = x_{1} … x_{n} we associate the number ∑ x_{i}2^{i−1} and vice versa. In particular, x_{n} is the most significant bit and x_{1} the least significant one.

2.1 Goldwasser-Micali Encryption Scheme

In [12] Goldwasser and Micali introduced the notion of semantic security for encryption schemes and presented such a semantically-secure scheme based on the quadratic residuosity assumption. Namely, the public key consists of an RSA-modulus N = pq of two equally large primes p, q, and a quadratic nonresidue z ∈ ZZ_{N}^{∗}(+1). To encrypt a bit b choose a random r ∈ ZZ_{N}^{∗} and set Enc(b, r) := z^{b}r^{2} mod N. If and only if b = 1 then this is a quadratic non-residue. And this can be recognized efficiently given the secret key, i.e., the factorization p, q of N. In contrast, deciding quadratic residuosity without knowledge of the factorization is believed to be hard, i.e., the quadratic-residuosity-assumption says that infeasible to significantly distinguish between 0- and 1-encryptions given only N and z.

Let us recall some useful facts about the GM-encryption scheme. First, the GM-scheme has nice homomorphic properties which allow to compute the exclusive-or of two encrypted bits and to flip an encrypted bit. Second, it is rerandomizable, i.e., given a ciphertext of an unknown bit b and the public key only, one can generate a uniformly distributed ciphertext of b.

– xor-property: Enc_{0}(b) · Enc_{0}(b′) = Enc_{0}(b ⊕ b′) mod N

– not-property: Enc_{0}(b) · z = Enc_{0}(b ⊕ 1) mod N

– rerandomization: Rand(Enc_{0}(b)) := Enc_{0}(b) · Enc(0) mod N is identically distributed to Enc(b)

Another important property of the GM-system is that it can be turned into an AND-homomorphic one over {0, 1} (cf. [18]): Let k be a security parameter and λ a sufficiently large function such that 2^{−λ} is small enough; we will discuss the choice of λ afterwards. To encrypt a bit b we encode b = 1 as a sequence of λ random quadratic residues (i.e., as λ GM-encryptions Enc(0)), and b = 0 as a sequence of λ random elements from ZZ_{N}^{∗}(+1) (i.e., as λ GM-encryptions Enc(a_{i}) for random bits a_{1}, …, a_{λ(k)}). We denote this encryption algorithm by Enc^{AND} and adopt the aforementioned notations Enc^{AND}(b), Enc^{AND}(b, r), Enc0^{AND}(b).

The decryption process takes a sequence of λ elements from ZZ_{N}^{∗}(+1) and returns 1 if all elements are quadratic residues, and 0 otherwise (i.e., if there is a quadratic non-residue among those elements). Note that there is a small probability of 2^{−λ} that a 0-bit is encrypted as a sequence of λ quadratic residues, and thus that decryption does not give the desired result. Choosing λ sufficiently large this almost never happens. In practice setting λ to 40 or 50 should be sufficient.

Next we explain how Enc^{AND} supports the AND-operation (with some small error). Given two encryptions Enc0^{AND}(b) and Enc0^{AND}(b′) of bits b, b′ we claim that the componentwise product modN is an encryption of b ∧ b′ (except with error 2^{−λ} over the choice of the randomness in the encryption process). Clearly, this is true if at least one of the sequences represents a 1-encryption, because multiplying this sequence with the other one does not change the quadratic character of the elements in the other sequence. If b = b′ = 0, though, the quadratic non-residues in both sequences can accidentally cancel out. But again this happens with probability 2^{−λ} only.

A crucial observation for our protocol is that we can embed a basic GMencryption into an AND-homomorphic one. This embedding is done as follows: given Enc_{0}(b) first flip the encapsulated bit b by multiplying the encryption with z. Then, generate a sequence of λ basic encryptions by letting the i-th sample be either Rand(z Enc_{0}(b)) or Enc(0) with probability 1/2. If b = 1, and therefore z Enc_{0}(b) ∈ QR_{N}, then the result is identically distributed to Enc^{AND}(1). For b = 0 we generate a sequence of random quadratic residues and random nonresidues (since z Enc_{0}(b) ∈ QNR_{N}), identically distributed to Enc^{AND}(0).

2.2 Non-Interactive Crypto-Computing

We have already outlined the problem of non-interactive crypto-computing protocols in the introduction. We give a very succinct description; for a more formal definition see [18]. Also, our definition merely deals with honest-but-curious parties, i.e., parties that follow the prescribed program but try to gain advantage from listening. The general case of dishonest parties is discussed afterwards.

Recall that a non-interactive crypto-computing protocol consists of two parties, the client (with input y) and the server (possessing a circuit C), such that the client sends a single message to the server and receives a single message as reply. The following holds:

– completeness: for any input y and any circuit C the honest client is able to extract the value C(y) from the answer of the honest server.

– (computational) privacy for the client: the client’s message for input y is not significantly distinguishable from a message generated for any other input y′ of the same length – (perfect) privacy for the server: the distribution of the server’s answer de-

pends only on the circuit’s output C(y) (where y is the message that the honest client sends encrypted).

A dishonest client could cheat by sending incorrect encryptions or system parameters. In case of the Goldwasser-Micali scheme the client should therefore send also a non-interactive proof of correctness for the modulus N and the nonredisue z; in practice these parameters are likely to be certified by some trusted authority anyway, and an additional correctness proof is redundant. Moreover, it is easy to see that, once the parameters’ correctness is approved, the server can check that the client sends n encrypted bits by verifying that the n transmitted elements belong to ZZ_{N}^{∗}(+1).

As for dishonest servers, Sander et al. [18] suggest that the server publishes a pair (y_{0}, C(y_{0})). The client may now ask about several input pairs where each pair consists of encryptions of y and y_{0} in random order. It can then be checked that the server answers consistently. Yet, the client must now also prove that each pair equals encryptions of y, y_{0} for the same y.

We stress that in some settings neither party seems to gain any noticeable advantage by deviating from the protocol. Recall the flight ticket example. As explained, the company as the client in the crypto-computing protocol essentially cannot cheat if it uses certified system parameters. And, since it wants to sell its product, it is likely to announce the deal if it later decrypts and finds out that the bid is high enough; since nothing else than this relationship is leaked about the bid, there does not seem to be a point in delaying the deal to wait for better offers. Similarly, if the customer sends garbage the company may blacklist him.

3 Non-Interactive Crypto-Computing for Comparison

In this section we present our protocol for non-interactively computing the greater-than function. As discussed before, we only deal with the case of honestbut-curious client and server. Clearly, a number x is greater than another number y if, for some i, we have x_{i} = 1 and y_{i} = 0 and x_{j} = y_{j} for all more significant bits for j = i + 1, …, n. More formally,

[x > y] : ⟺ ⋁_{i=1}^{n} (x_{i} ∧ ¬y_{i} ∧ ⋀_{j=i+1}^{n}(x_{j} = y_{j}))  (1)

Note that x_{j} = y_{j} can be written as ¬(x_{j} ⊕ y_{j}) and that both operations ⊕, ¬ can be easily implemented for the basic GM-scheme.

The disjunction in Expression (1) is an exclusive OR, i.e., only one implicant is satisfiable simultanously. This suggests the following strategy to compute the formula: we process each implicant individually and compute x_{i} ∧ ¬y_{i} ∧ ⋀_{j=i+1}^{n}(x_{j} = y_{j}) using the basic and the AND-homomorphic GM-system, respectively, for ⊕, ¬ and AND. This is done by performing the computations for x_{j} = y_{j} and ¬y_{i} with the basic GM-encryption scheme, and by embedding the results and the encryption for x_{i} into the extended system and computing the AND. Then we permute the resulting n encryptions of the implicants and output them. If and only if [x > y] then there exists a random AND-GM-encryption of 1, and this appears at a random position. Otherwise we have a sequence of random 0-encryptions. The protocol is given in Figure 1.^{3}

In Figure 2 we reduce the number of multiplications. This is done by first noting that one can re-use the encryption for ⋀_{j=i+1}^{n}(x_{j} = y_{j}) from stage i for stage i − 1. That is, for i = n, n − 1, …, 1 we compute and store the product Pi^{AND} representing ⋀_{j=i+1}^{n}(x_{j} = y_{j}). Then we merely compute the AND of this stored encryptions with the ciphertext for x_{i} = y_{i}. Moreover, if we know x explicitly then we can compute x_{i} = y_{i} directly by Enc_{0}(y_{i}) · z^{1−x_{i}} instead of first encrypting x and then computing Enc_{0}(y_{i}) · Enc_{0}(x_{i}). Finally, we remark that we only need to rerandomize one of the encryptions of Xi^{AND}, Ȳi^{AND} and Pi^{AND} in order to rerandomize each product Ti^{AND} = Xi^{AND} · Ȳi^{AND} · Pi^{AND}. In Figure 2 this is done for Xi^{AND}, whereas for Ȳi^{AND} and Ei^{AND} we choose the fixed quadratic residue 1 ∈ QR_{N} instead of a random GM-encryption Enc(0) when embedding.

Some easy but important observations follow:

Lemma 1. For inputs x, y ∈ {0, 1}^{n} and security and error parameter k and λ the protocol in Figure 1 with the optimized server algorithm in Figure 2 satisfies:

– for x ≤ y the Ti^{AND} are all random AND-encryptions Enc^{AND}(0) of 0.

– for x > y there exists exactly one uniformly distributed i for which Ti^{AND} represents a random 1-encryption Enc^{AND}(1); for all other j ≠ i we have random 0-encryptions Enc^{AND}(0) for Tj^{AND}.

– the evaluation takes only 6nλ multiplications in ZZ_{N}^{∗} for the server in the worst case, and 5nλ multiplications on the average (over the random choices in the encryption process).

– the error is at most 5n · 2^{−λ}.

We thus derive the following result:

Theorem 1. The protocol in Figure 1 and Figure 2 constitutes a non-interactive crypto-computing protocol for GT(x, y) = [x > y] such that for inputs x, y ∈ {0, 1}^{n} and security parameter k and error parameter λ the client has to perform 2n modular multiplications (plus the number of multiplications to generate a GMinstance N, z for security parameter k in a preprocessing step) and the server has to carry out at most 6nλ multiplications. The error of the protocol is at most 5n · 2^{−λ}.

3 We remark that the fact that we do not have to compute the disjunction explicitly supports our improved protocol. Otherwise we would have to compute the OR of AND-encryptions which we do not know how to do without blowing up the number of multiplications like in [18].

Fig. 1. Non-Interactive Crypto-Computing for GT

security parameter k, error parameter λ

Client’s algorithm I:

– generate GM-instance N, z for security parameter k

– encrypt input y bit-wise: Y_{i} ← Enc(y_{i}) for i = 1, …, n

– send N, z, Y_{1}, …, Y_{n} to server

Server’s algorithm:

– receive N, z, Y_{1}, …, Y_{n} from client

– encrypt input x bit-wise: X_{i} ← Enc(x_{i}) for i = 1, …, n

– compute encryptions of e_{i} = [x_{i} = y_{i}] = ¬(x_{i} ⊕ y_{i}):

for all i = 1, …, n compute E_{i} = Y_{i} · X_{i} · z mod N

– embed E_{i} into extended encryptions Ei^{AND}:

for all i = 1, …, n set Ei^{AND} := (Ei,1^{AND}, …, Ei,λ^{AND}), where Ei,j^{AND} ← Rand(zE_{i}) or Enc(0), the choice made by a fair coin flip.

– embed encryptions X_{i} and Ȳ_{i} of x_{i} and ¬y_{i} into encryptions Xi^{AND} and Ȳi^{AND}: for all i = 1, …, n set Xi^{AND} := (Xi,1^{AND}, …, Xi,λ^{AND}), where Xi,j^{AND} ← Rand(zX) or Enc(0), the choice made by a fair coin flip. for all i = 1, …, n set Ȳi^{AND} := (Ȳi,1^{AND}, …, Ȳi,λ^{AND}), where Ȳi,j^{AND} ← Rand(Y_{i}) or Enc(0), the choice made by a fair coin flip.

– compute terms t_{i} := [x_{i} ∧ ¬y_{i} ∧ ⋀_{j=i+1}^{n} x_{j} = y_{j}]:

for i = 1, …, n let Ti^{AND} = Xi^{AND} · Ȳi^{AND} · ∏_{j=i+1}^{n} Ej^{AND} mod N

– randomly permute T1^{AND}, …, Tn^{AND} and return them to the client

Client’s algorithm II:

– receive n sequences of λ elements from ZZ_{N}^{∗} from server

– if there exists a sequence of λ quadratic residues then output ‘x > y’, else output ‘x ≤ y’.

4 Applications

In the previous section, we have shown how to compute the function GT(x, y) = [x > y] with few modular multiplications. Here, we discuss several applications of this result.

4.1 Conditional Oblivious Transfer

With an oblivious transfer protocol [17] a sender hands with probability 1/2 a secret bit to a receiver such that the sender remains oblivious about the fact whether the receiver has actually learned the bit or not. As for a conditional oblivious transfer [7], the random choice is replaced by a predicate evaluation depending on some additional private inputs of both parties. For example, in [7] such a protocol has been used to derive a time-release encryption scheme where

Fig. 2. Optimized Non-Interactive Crypto-Computing for GT

security parameter k, error parameter λ

Optimized server algorithm:

– receive N, z, Y_{1}, …, Y_{n} from client

– embed input x into extended encryptions Xi^{AND}:

for all i = 1, …, n let Xi^{AND} := (Xi,1^{AND}, …, Xi,λ^{AND}), where Xi,j^{AND} ← Enc(z^{1−x_{i}}) or Enc(0), the choice made by a fair coin flip.

– embed [x_{i} = y_{i}] into extended encryptions Ei^{AND}:

for all i = 1, …, n set Ei^{AND} := (Ei,1^{AND}, …, Ei,λ^{AND}), where Ei,j^{AND} := Y_{j} · z^{x_{i}} mod N or 1 ∈ QR_{N}, the choice made by a fair coin flip.

– compute extended encryptions Pi^{AND} of p_{i} = ⋀_{j=i+1}^{n}[x_{j} = y_{j}]: for i = n − 1, …, 1 let Pi^{AND} := Pi+1^{AND} · Ei+1^{AND} mod N where Pn^{AND} := (1, …, 1).

– embed encryptions Ȳ_{i} of ¬y_{i} into encryptions Ȳi^{AND}:

for all i = 1, …, n set Ȳi^{AND} := (Ȳi,1^{AND}, …, Ȳi,λ^{AND}), where Ȳi,j^{AND} = Y_{i} or 1 ∈ QR_{N}, the choice made by a fair coin flip.

– compute terms t_{i} := [x_{i} ∧ ¬y_{i} ∧ ⋀_{j=i+1}^{n}[x_{j} = y_{j}]:

for i = 1, …, n let Ti^{AND} := Xi^{AND} · Ȳi^{AND} · Pi^{AND} mod N

– randomly permute T1^{AND}, …, Tn^{AND} and return them to the client

a trusted party releases a secret only if a predetermined release time has expired. In this case, the predicate is given by the greater-than function and the private inputs are the release time and the current time, respectively.

Since the current time is publicly known anyway in the setting of time-release encryption, the conditional oblivious transfer scheme in [7] does not hide the private input of the sender. In some settings, though, this information may be confidential and should be kept secret. Our non-interactive crypto-computing protocol provides a solution. We stress that we do not know how to construct such a scheme with the non-interactive crypto-computing protocol from [18] for the greater-than function.

The outset is as follows. The sender possesses a bit b which is supposed to be transferred to the receiver if and only if the sender’s input x is greater than the receiver’s input y. The receiver generates an instance of the GM-system and sends N, z (together with a proof of correctness, if necessary) and a bit-wise GM-encryption of his private input y to the sender. Then the sender computes Formula (1) on these encryptions and his private input x. Recall that this evaluation yields n sequences of λ bits for x, y ∈ {0, 1}^{n}. Exactly if x > y then there is a sequence with quadratic residues exclusively; otherwise all sequences contain random entries from ZZ_{N}^{∗}(+1). Now, for each i = 1, …, n the sender splits the bit b to be transferred into λ pieces b_{i,1}, …, b_{i,λ} with b = b_{i,1} ⊕ … ⊕ b_{i,λ}. In addition to the Ti^{AND}’s send (zTi,j^{AND})^{b_{i,j}} · r_{i,j}^{2} mod N for random r_{i,j}’s. That is, the receiver also gets the bit b_{i,j} if Ti,j^{AND} is a quadratic residue, and a uniformly distributed quadratic residue if Ti,j^{AND} ∈ QNR_{N} (and therefore no information about b_{i,j}). In other words, the receiver learns all random pieces b_{i,1}, …, b_{i,λ} for some i —and thus b— if x > y, and lacks at least one random piece for each i if x ≤ y (unless an encryption error occurs, which happens with probability at most 5n · 2^{−λ}).

Bottom line, if x > y then the receiver gets to know the sender’s bit b, whereas for x ≤ y the bit b is statistically hidden from the receiver. Furthermore, the receiver does not learn anything about the sender’s private input x except the predicate value [x > y]. On the other hand, the sender gets only an encryption of the receiver’s input y and does not know if b has been transferred. Hence, this is a conditional oblivious transfer protocol that keeps the private inputs secret.

4.2 Private Bidding and the Millionaires’ Problem

In a private bidding protocol [3] two parties A and B compare their inputs x, y with the support of an active third party T. Although the third party T is trusted to carry out all computations corectly it should remain oblivious about the actual outcome of the comparison. Furthermore, T does not collude with either of the other parties. Note that such a bidding protocol immediately gives a fair solution to the millionaires’ problem in presence of an active third party.

An efficient protocol for private bidding has been presented in [3]. The solution there requires the trusted party to compute n exponentiations, whereas A and B have to compute n encryptions. Yet, for technical reasons, the basic GM-system is not applicable, and the suggested homomorphic schemes need at least one exponentiation for each encryption. Also, the protocol there requires potentially stronger assumptions than the quadratic residuosity assumption.

Security of a bidding protocol in [3] is defined in terms of secure function evaluation against non-adaptive adversaries [6, 9]. Namely, an adversary corrupting at most one of the parties at the outset of the protocol does not learn anything about the other parties’ inputs beyond what the compromised party should learn about the outcome of the bidding, i.e., for corrupted A or B the adversary merely learns the function value GT(x, y) and for compomised T it learns nothing about x, y at all. It is assumed that all parties are mutually connected via private and authenticated channels; this can be achieved using appropriate cryptographic primitives. A formal definition of secure bidding is omitted from this version.

The Honest-But-Curious Case. We first discuss the idea of our protocol in the honest-but-curious case. Also, to simplify, suppose that always x ≠ y. The trusted party T publishes a GM-instantiation N, z such that neither A nor B knows the factorization of N. Party A sends an encryption of his input x under N, z to B who answers with an encryption of y. Then one party, say A, sends a random bit b and two random strings that are used to compute the non-interactive crypto-computing evaluation procedure on both encryptions of x, y; one time the parties inattentively compute GT(x, y) and the other time they evaluate GT(y, x). Note that both parties obtain the same strings by this since they use the same encryptions and identical random strings. Each party sends both strings in random order according to bit b to the third party. The third party decrypts the strings if and only if it receives the same strings from A and B. T computes the decision bits [x > y], [y > x] for b = 0 or [y > x], [x > y] for b = 1 —but does not know which of the cases has occured— and returns the bits to each party. A and B can then decide whether x > y or y < x.

Let us briefly discuss that this protocol is secure against honest-but-curious adversaries. First note that if A and B are honest then T learns nothing (in a statistical sense) about x and y. The reason is that T merely gets random answers of the non-interactive crypto-computing protocol for GT(x, y) and GT(y, x) in random order (and exactly one of the predicates is satisfied by assumption about inequality of x and y).

Assume that an adversary sees all internal data and incoming and outgoing messages of A, but does not have control over A and, in particular, cannot bias the random bits used for the crypto-computation. This, however, means that unless an error occurs in the crypto-computation the adversary gets only the information about [x > y] from the trusted party, and a secure encryption of y from B. Hence, with very high probability the adversary does not learn anything in a computational sense from listening to the execution. Similarly, this follows for a dishonest B.

Fig. 3. Private Bidding with an Oblivious Third Party

Trusted party T publishes a GM-instantiation N, z and random quadratic nonresidues w_{A} and w_{B}.

– A and B jointly generate two random strings each of nλ bits and a bit b using a coin-flipping protocol with N, w_{A}.

– A sends bit-wise GM-encryptions Enc(x) under N, z to B and gives a zeroknowledge proof of knowledge based on N, z, w_{A}; A also sends a sufficient number of random elements from ZZ_{N}^{∗}.

– Vice versa, B sends an encryption Enc(y) under N, z to A and proves in zeroknowledge with N, z, w_{B} that he knows the plaintext.

– Each party computes the server’s evaluation procedure for GT(x, y) and GT(y, x) on the encryptions with the predetermined elements from ZZ_{N}^{∗} and submits the result to the trusted party (in random order according to bit b).

– If and only if both incoming values are equal then the trusted party decodes both sequences and returns the bits.

– Both parties output the result GT(x, y).

The Malicious Case. In order to make the protocol above secure against actively cheating adversaries we have to ensure that the parties do not choose the encryptions in an adaptive manner. Formally, we need to extract the encrypted values from the dishonest party A or B and for this purpose add an interactive zero-knowledge proof of knowledge to the encryptions; this proof of knowledge can be carried out in three rounds with the data N, z, w_{A}, w_{B} published by T. Details are postponed to Appendix A.

Also, we have to ensure that the non-interactive crypto-computation is really based on truly random bits: biased bits may increase the probability that the result of an AND of encryptions is incorrect and thus the outcome might reveal some information about x or y, respectively. This is solved by using a coinflipping protocol in which one party commits to a random string a and the other publishes a random string b and the outcome is set to a ⊕ b. Again, the reader is refered to Appendix A for details. It is important to notice that we only need random bits for the embedding of basic GM-encryptions into AND-encryptions. That is, only the choice whether we encode the i-th component as Enc(d) or as Enc(0) when embedding a basic GM-encryption Enc_{0}(d) must be made at random. Hence, we only need nλ random bits for each evaluation; the necessary elements from ZZ_{N}^{∗} for embedding can be announced by one of the parties.

We present an informal argument why this scheme is secure; a formal proof is deferred from this version. Say that the adversary corrupts party T. Then the same argument as in the honest-but-curious case applies: T only sees two honestly generated outcomes of crypto-computations for GT(x, y) and GT(y, x) in random order.

Consider the case that the adversary corrupts A. We have to present a simulator that is allowed to query an oracle GT(·, y) once, and outputs a protocol execution which is indistinguishable from a true execution with honest T and B (with secret input y). Roughly, the simulator extracts the input x^{∗} from the adversary’s proof of knowledge for the encryption and simulates T ’s and B’s behavior by the zero-knowledge property.^{4} The simulator then queries the oracle about x^{∗} to obtain GT(x^{∗}, y). Given this bit the simulator finally outputs T ’s answer; this is possible since it knows the order of the transmitted crypto-computations and both parties must send the same crypto-computation for GT(x^{∗}, y) and GT(y, x^{∗}). Additionally, since the computation involves truly random bits because of the coin tossing, the result of the crypto-computation is correct with very high probability. In this case, T ’s decoding would be identical to the simulator’s output for GT(x^{∗}, y).

The case that the adversary corrupts B is analogous. Hence, we obtain a secure constant-round private-bidding protocol with an active oblivious third party; the protocol requires at most 19nλ + 2λ modular multiplications for each party, where n is the length of the bids and λ determines the error.

Above we presumed that x ≠ y. It is not hard to see that our non-interactive crypto-computing protocol in Section 3 can be modified to a scheme which computes EQ(x, y) and where the server’s answer is identical distributed to the one for GT(x, y) (for the same instance N, z). Therefore, if one alters the

4 At first glance, it seems that the simulator could choose N on behalf of T such that it knows the factorizaton p, q of N and such that it can extract x^{∗} directly by decoding. Yet, the simulator has to present a fake encryption of y pretending to be B, and we were not able to prove this to be indistinguishable from a correct encryption of y if the simulator knows p, q. Therefore, we take the detour using a proof of knowledge.

bidding protocol by letting A and B passing three crypto-computations for GT(x, y), GT(y, x), EQ(x, y) in random order to T, then one obtains a secure bidding protocol where A and B know which input is bigger (if any), or if the inputs are equal.

Acknowledgements

We thank the anonymous reviewers of RSA 2001 for comprehensive comments.

References

1. D.Beaver: Minimal-Latency Secure Function Evaluation, Eurocrypt 2000, Lecture Notes in Computer Science, Vol. 1807, Springer-Verlag, pp. 335–350, 2000.

2. F.Boudot, B.Schoenmakers, J.Traoré: A Fair and Efficient Solution to the Socialist Millionaires’ Problem, to appear in Discrete Applied Mathematics, Special Issue on Coding and Cryptography, Elsevier, 2000.

3. C.Cachin: Efficient Private Bidding and Auctions with an Oblivious Third Party, 6th ACM Conference on Computer and Communications Security, pp. 120–127, 1999.

4. C.Cachin, J.Camenish: Optimistic Fair Secure Computations, Crypto 2000, Lecture Notes in Computer Science, Vol. 1880, Springer-Verlag, pp. 93–111, 2000.

5. C.Cachin, J.Camenish, J.Kilian, J.Müller: One-Round Secure Computation and Secure Autonomous Mobile Agents, ICALP 2000, Lecture Notes in Computer Science, Springer-Verlag, 2000.

6. R.Canetti: Security and Composition of Multiparty Cryptographic Protocols, Journal of Cryptology, Vol. 13, No. 1, Springer-Verlag, pp. 143–202, 2000.

7. G.Di Crescenzo, R.Ostrovsky, S.Rajagopalan: Conditional Oblivious Transfer and Time-Release Encryption, Eurocrypt ’99, Lecture Notes in Computer Science, Vol. 1592, Springer-Verlag, pp. 74–89, 1999.

8. U.Feige, A.Fiat, A.Shamir: Zero-Knowledge Proofs of Identity, Journal of Cryptology, Vol. 1, No. 2, pp. 77–94, Springer-Verlag, 1988.

9. O.Goldreich: Secure Multi-Party Computation, (working draft,

version  1.2),  available  at  http://www.wisdom.weizmann.ac.il/
home/oded/public html/pp.html, March 2000.

10. O.Goldreich, S.Micali, A.Wigderson: How to Play any Mental Game —or— a Completeness Theorem for Protocols with Honest Majorities, Proceedings of the 19th Annual ACM Symposium on the Theory of Computing, pp. 218–229, 1987.

11. O.Goldreich, S.Micali, A.Wigderson: Proofs That Yield Nothing About Their Validity —or— All Languages in NP Have Zero-Knowledge Proof Systems, Journal of the ACM, Vol.8, No. 1, pp. 691–729, 1991.

12. S.Goldwasser, S.Micali: Probabilistic Encryption, Journal of Computer and System Sciences, Vol. 28(2), pp. 270–299, 1984.

13. S.Goldwassser, S.Micali, C.Rackoff: The Knowledge Complexity of Interactive Proof Systems, SIAM Journal on Computation, Vol. 18, pp. 186–208, 1989.

14. G.Hardy, E.Wright: An Introduction to the Theory of Numbers, Oxford University Press, 1979.

15. M.Jakobsson, M.Yung: Proving Without Knowing: On Oblivious, Agnostic and Blindfolded Provers, Crypto ’96, Lecture Notes in Computer Science, Vol. 1109, Springer-Verlag, pp. 186–200, 1996.

16. M.Naor, B.Pinkas, R.Sumner: Privacy Preserving Auctions and Mechanism Design, 1st ACM Conference on Electronic Commerce, available at

     http://www.wisdom.weizmann.ac.il/˜ bennyp/, 1999.

17. M.Rabin: How to Exchange Secrets by Oblivious Transfer, Technical Report TR-81, Harvard, 1981.

18. T.Sander, A.Young, M.Yung: Non-Interactive Crypto-Computing for NC^{1}, Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS), 1999.

19. A.Yao: Protocols for Secure Computation, Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 160–164, 1982.

20. A.Yao: How to Generate and Exchange Secrets, Proceedings of the 27th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 162–167, 1986.

A Fair Coin-Tossing and Zero-Knowledge Proof of Knowledge for GM-Encryptions

In this section we review the missing sub protocols of Section 4.2: a threeround zero-knowledge [13] proof of knowledge for GM-encryptions [8], and a coin-flipping protocol to generate unbiased random bits. We start with the coinflipping protocol as we will need it for the proof of knowledge, too.

A.1 Fair Coin-Tossing

Assume that a trusted party publishes a modulus N and a quadratic non-residue w_{A} ∈ QNR_{N}. To generate a single unbiased random bit,

– party A commits to a bit a by sending a random encryption Enc(a, s) under N, w_{A}.

– B sends a random bit b.

– A decommits to a by sending a, s to B (who verifies that Enc(a, s) equals the ciphertext from the first step).

– the random bit c is set to c = a ⊕ b.

These basic steps can be repeated 2nλ + 1 times in parallel to generate 2nλ + 1 random bits as required in our application.

We show that the protocol can be used to generate an unbiased bit even if one party is dishonest; furthermore, we show that a simulator playing A can bias the outcome to any predetermined value c.

If A is corrupt then c is uniformly distributed because the encryption of a binds perfectly. If B is controlled by the adversary this is accomplished by letting T announce an invalid but correct looking w_{A} which is a quadratic residue instead of a non-residue; moreover, assume that we know a root v_{A} of w_{A} = v_{A}^{2} mod N. We bias the coin flipping by first choosing a random c ∈ {0, 1} before the protocol starts and by sending an encryption Enc(1, s) of a = 1 under N, w_{A}. Then, after having received b from the adversary, we decommit to a′ = c ⊕ b by sending (0, sv_{A}) for a′ = 0 and (1, s) for a′ = 1. It is readily verified that this is a corret decommitment for a′. Conclusively, the coin flip is biased to the previously selected, but uniformly distributed c. On the other hand, under the quadratic residuosity assumption, B cannot distinguish that w_{A} is quadratic residue.

A.2 Zero-Knowledge Proof of Knowledge

Next, we introduce the proof of knowledge, but we start with a special case of a short challenge. Assume again that the trusted party publishes a modulus N (which can be same as in the coin flipping protocol) and a quadratic non-residue z ∈ QNR_{N} (which is also used for encryption). Party A has published a bit-wise encryption X_{i} = Enc(x_{i}, r_{i}) of x ∈ {0, 1}^{n} under N, z.

– party A commits to an n-bit string u by sending a bit-wise encryption U_{i} = Enc(u_{i}, s_{i}) of u under N, z.

– party B sends a random bit c.

– if c = 0 then A sends u and the randomness s_{1}, …, s_{n} used to encrypt u. If c = 1 then A sends v = u ⊕ x ∈ {0, 1}^{n} and t_{i} = r_{i}s_{i} mod N.

– B verifies the correctness by re-encrypting the values with the reveled randomness and comparing it to the given values. Specifically, for c = 0 party B checks that U_{i} = Enc(u_{i}, s_{i}), and verifies that U_{i}X_{i} = Enc(v_{i}, t_{i}) mod N for c = 1.

Under the quadratic residuosity assumption this protocol is computational zeroknowledge, i.e., there exist an efficient simulator that, for any malicious B, imitates A behavior in an indistinguishable manner without actually knowing x. This zero-knowledge simulator basically tries to guess the challenge at the outset and sends appropriate phony values in the first step.

This basic protocol for bit-challenges allows to cheat with probability 1/2 by simply guessing the challenge. But the steps can be repeated independently in parallel for λ in order to decrease the error to 2^{−λ}. However, while this protocol is provably zero-knowledge for logarithmically bounded λ, it is not known to be zero-knowledge for large λ.

Fortunately, the problem is solvable by tossing coins. That is, we generate λ bit-challenges with a coin flipping protocol as described above. This can be interleaved with the proof of knowledge to obtain a three-round protocol. Since the outcome of the coin flips can be chosen a priori if we have a quadratic residue w_{A}, the protocol becomes zero-knowledge; the zero-knowledge simulator does not even have to guess the challenge bits because it can choose them for himself before the protocol starts.

As for our bidding protocol, we announce independent w_{A} and w_{B} for each party: either party that is under control of the adversary gets a quadratic nonresidue (to force this party to provide a correct proof of knowledge and to generate truly random bits), whereas the simulator playing the honest party is given a quadratic residue in order to “cheat”. For an adversary this is not detectable under the quadratic residuosity assumption.