BRICS RS-98-37 Damgård et al.: Basing OT and BC on Weakened Security Assumptions BRICS

Basic Research in Computer Science

On the (Im)possibility of Basing Oblivious Transfer and Bit Commitment on Weakened Security Assumptions

Ivan B. Damgård Joe Kilian Louis Salvail

BRICS Report Series RS-98-37 ISSN 0909-0878 December 1998 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1998, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/98/37/

On the (Im)possibility of basing Oblivious Transfer and Bit Commitment

on Weakened Security Assumptions

Ivan Damgård^{1}, Joe Kilian^{2} and Louis Salvail^{1}

1 BRICS, Basic Research in Computer Science of the Danish National Research Foundation, Department of Computer Science,University of Århus, Ny Munkegade,

building 540,DK-8000 Århus C, Denmark.

                 {ivan,salvail}@daimi.aau.dk

2 Polar Circle Research Center on Iceberg and Crumbling Nuclear Submarines, Department of Hyper-Blast, Ruijtakakkiowakak University, Ice Cube 23, Freezing

City.

Abstract. We consider the problem of basing Oblivious Transfer (OT) and Bit Commitment (BC), with information theoretic security, on seemingly weaker primitives. We introduce a general model for describing such primitives, called Weak Generic Transfer (WGT). This model includes as important special cases Weak Oblivious Transfer (WOT), where both the sender and receiver may learn too much about the other party’s input, and a new, more realistic model of noisy channels, called unfair noisy channels. An unfair noisy channel has a known range of possible noise levels; protocols must work for any level within this range against adversaries who know the actual noise level. We give a precise characterization for when one can base OT on WOT. When the deviation of the WOT from the ideal is above a certain threshold, we show that no information-theoretic reductions from OT (even against passive adversaries) and BC exist; when the deviation is below this threshold, we give a reduction from OT (and hence BC) that is information-theoretically secure against active adversaries. For unfair noisy channels we show a similar threshold phenomenon for bit commitment. If the upper bound on the noise is above a threshold (given as function of the lower bound) then no information-theoretic reduction from OT (even against passive adversaries) or BC exist; when it is below this threshold we give a reduction from BC. As a partial result, we give a reduction from OT to UNC for smaller noise intervals.

1 Introduction

A 1 out of 2 Oblivious transfer (1-2 OT) protocol is one by which a sender with 2 bits b_{0}, b_{1} as input can interact with a receiver with a bit c as input. Ideally, the sender should learn nothing new from the protocol, whereas the receiver should learn b_{c} and nothing more. Several variants of OT exist, but it does not matter much which one we consider, as they are almost all equivalent (see e.g. [8]).

A bit commitment scheme is a pair of protocols Commit and Open executed by two parties, a commiter, C, and a receiver, R. First, C and R execute Commit, where C has a bit b as input; R either accepts that a commitment has taken place or rejects. Ideally, the receiver should learn no information about b from this. Later, they may execute Open, after which R returns accept 1, accept 0 or reject. We require our protocols to be correct, private and binding:

Correctness: If both parties follow the protocol, R should always

accept with the same value (b) that C wished to commit to. Privacy: Committing to b reveals nothing to the receiver about b. Binding: C cannot cause R to accept a commitment, and then be

able to execute Open so that R accepts a 1 and also be able to execute Open so that R accepts a 0.

We have described the ideal requirements here. However, usually when building such protocols, one accepts an error that can be made negligibly small as a function of some security parameter k.

A great deal of work has gone into how to implement oblivious transfer and bit commitment based on seemingly weaker primitives. For example, a binary symmetric channel (BSC) is one that allows a sender S to send a bit b_{S} to a receiver R, such that a bit b_{R} will be received, which is not necessarily equal to b_{S}. There is a constant probability 0 < δ < 1/2 called the noise level of the channel such that each time the channel is invoked, P r(b_{S} ≠ b_{R}) = δ. Another, essentially equivalent formulation has S and R receiving random bits b_{S} and b_{R} that are individually unbiased but correlated so that P r(b_{S} ≠ b_{R}) = δ. Another equivalent formulation has a random bit b transmitted to both parties through independent noisy channels. One motivation for the last two formulations is that one might want to implement noisy channels by a very weak broadcast source, such as a satellite.

Crépeau and Kilian [9] showed that a BSC can be used to implement 1–2 OT with unconditional (information theoretic) security; the efficiency of this reduction was later improved by Crépeau [6], who also directly built a bit commitment scheme (indirectly, bit commitment can be based on 1–2 OT).

The reductions given in [9, 6] rely on the fact that δ is known exactly by each party. However, in real life it may be possible for one party to surreptitiously alter the noise level of the channel. If the noise is induced by a communications channel then it may be possible to alter the mechanism (say by heating it up or cooling it down), or change the way it uses the mechanism, to change the noise rate. For example, suppose the channel consists of two pieces of optical fibre with a repeater station in between, a very common case in practice. If one party has access to the data received by the repeater station, then he can send and receive a cleaner signal than the other party expects him to. In the case of a noisy broadcast channel, an adversary might send a jamming signal or buy a more sensitive antenna. Note that while it may be hard to hide the fact that one has made a channel noisier, one can always hide the fact that one has made it less noisy, simply by deliberately garbling ones own messages and pretending to hear a more garbled version than one already has heard.

Such “unfair advantages” are not always devastating for applications to cryptography: Maurer [15] shows that secure key exchange between two parties with access to a random but noisy signal is possible, even in the presence of an enemy who can receive the signal much more reliably than the honest players. However, this scenario is a game for two parties who trust each other and want to be protected ”against the rest of the world”. It is natural to ask if we can still make do with unfair channels in case of games between two mutually distrusting parties. Unfortunately, the protocols of [9, 6] break down in this scenario.

1.1 Our results

In this paper we propose a general model for two-party primitives where a cheating player can get more information than an honest one; we call this Weak Generic Transfer (WGT). We then consider a number of important subcases and show when they can and cannot be used as a basis for bit commitment and oblivious transfer.

We consider a family of Weak Oblivious Transfers, which are 1– 2 OT protocols with the following faults: with probability (at most) p a cheating sender will learn which bit the receiver chose to receive, and with probability q a cheating receiver will learn both of the sender’s input bits. Note that the honest participants only receive what they are supposed to receive; this extra information cannot be relied on. We call such a protocol a (p, q)-WOT. We give tight results for when one can reduce oblivious transfer to (p, q)-WOT.

In the statement of our results, when we use “reduction” we mean a reduction that is information-theoretically secure against unbounded adversaries, where deviations from the ideal are negligible in a given security parameter.

Theorem 1. 1–2 OT and BC can be reduced to (p, q)-WOT iff p + q < 1.

We also consider a still noisier model, denoted (p, q, ϵ)-WOT in which with probability at most ϵ an honest receiver receives b̄_{c} instead of b_{c} (i.e., the incorrect value); a cheating receiver is under no such handicap. In this case, we prove positive an negative results that are no longer tight. Theorem 2. 1–2 OT can be reduced to (p, q, ϵ)-WOT, for the case of passive adversaries, if p+q+2ϵ < .45. No reductions from 1–2 OT or BC exist if p + q + 2ϵ ≥ 1.

Passive adversaries, also known as “honest but curious” adversaries follow the protocol, but then try to use their view of the protocol execution to violate the security conditions.

Both theorems comprise a constructive result and an impossibility result. The constructive result of Theorem 1 generalizes a theorem of [9], which solves the special cases where either p or q is 0 (or negligible in the security parameter). Brassard/Crépeau [2] and Cachin [4] consider a more general model of WOT, where the extra information that an adversary learns is only specified by a general information measure, but here again the weakness is one-sided: only the receiver learns extra information. Prior to this work, few nontrivial impossibility results of this type were known (see [14] for one such result). These impossibility results hold even if security against passive cheating is required and the honest players are allowed infinite computing power.

We note that one motivation for the study of these imperfect protocols is that they provide easier to achieve steps for other reductions. For example, our reduction from 1–2 OT to unfair noisy channels first reduces (p, q, ϵ)-WOT to unfair noisy channels.

We finally consider unfair noisy channels (UNC). These channels have parameters γ and δ, where γ, δ ≤ 1/2. The noise level p of this channel is guaranteed to fall into the interval [γ, δ]. The protocol must work for any p in this range; however the value of p is not known to the honest players (but may be set within this range by the adversary). Theorem 3. For δ > 2γ(1 − γ), neither 1–2 OT nor BC may be reduced to (γ, δ)-UNC. For δ < 2γ(1−γ) BC may be reduced to (γ, δ)- UNC. Finally, 1–2 OT may be reduced to (γ, δ)-UNC if α^{3}β^{3}(1 − ζ(1 − α)) > \frac{0.775+ϵ(δ)}{1−ϵ(δ)}, where ϵ(δ) = \frac{δ^{2}}{δ^{2}+(1−δ)^{2}} , α = \frac{1−δ−γ}{1−2γ},β = \frac{1−γ}{1−δ} , and ζ = \frac{1−γ}{δ}.

1.2 Techniques used

All of our impossibility results rely on a general simulation technique that allows us to leverage the result that it is impossible to implement 1–2 OT (information-theoretically) given only a clear channel.

Our upper bounds for (p, q)-WOT and (p, q, ϵ)-WOT use some reductions first used in [9]. The reduction from bit commitment to (γ, δ)-UNC is based on the interactive hashing technique of [16]. The precise hashing method of [16] doesn’t work for our application; instead we use families of universal hash functions [10]. Hash functions are ubiquitous in cryptography; two classic results on achieving privacy with universal hash functions are [13] and [1]. For the specifics of our analysis we use bounds on their behaviour implied by the results of [17].

Guide to the paper In Section 2 we give the general scenario for weak generic transfer. In Section 3 we show impossibility results for reducing 1–2 OT and bit commitment to (p, q)-WOT, (p, q, ϵ)- WOT and (γ, δ)-UNC. In Section 4 we give reductions from 1–2 OT (and hence bit commitment) to (p, q)-WOT and (p, q, ϵ)-WOT. In Section 5 we give a reduction from bit commitment to (γ, δ)-UNC. In Section 6 we in give a reduction from 1–2 OT to (γ, δ)-UNC.

2 The General Scenario: Weak Generic Transfer

In order to show more clearly the basic properties we study, we start with a general scenario that includes as special cases those primitives we study in more detail later.

First, we describe a specification for standard two party primitives, and then show how to augment these specifications to model interesting deviations from the ideal behaviour of the protocol.

Initially, our scenario includes two players A, B that start with private inputs x_{A}, x_{B}, respectively chosen from domains X_{A} and X_{B} (the precise nature of these domains has no impact on the following discussion). A specification for a standard two-party primitive is a function output that maps (x_{A}, x_{B}) to a probability measure D on Y_{A} × Y_{B}. When the primitive is executed with inputs (x_{A}, x_{B}), D = output(x_{A}, x_{B}) is computed, (y_{A}, y_{B}) is chosen according to D, y_{A} is sent to A and y_{B} is sent to B. This framework is powerful enough to model primitives such as OT, 1–2 OT and binary symmetric channels.

To model the possibility that a primitive might inadvertently leak information, we modify D to be a distribution (Y_{A} × Z_{A}) × (Y_{B} × Z_{B}); ((y_{A}, z_{A}), (y_{B}, z_{B})) are sampled from D. If A is honest, then A receives only y_{A}, but if A is corrupt, it also receives z_{A}; B behaves symmetrically.

We can model passive (“honest but curious”) adversaries by simply specifying that an adversary Q ∈ {A, B} follows the protocol, ignoring z_{Q}, and then later learns what it can from the values of z_{Q} that is obtained. An active adversary may immediately use this extra information in planning its next move.

We have modeled deviations from privacy; we now model deviations in behaviour. Instead of having a single function output, we have a (possibly infinite) set S of functions {output}, which contains a “default” output_{0}. When the protocol is executed, the adversary has the option of choosing output from S; the protocol then behaves as before. If there is no adversary, then the default output_{0} is used. We say that S specifies a Weak Generic Transfer (WGT). We will assume throughout that A and B have access to the WGT as a black-box and can execute it independently as many times as they wish.

A WGT may consist of a protocol where for instance a noisy channel is used several times, and the protocol instructs one player to send the same bit each time. An active cheater may choose not to do so, and so he may behave in a way that is not consistent with any legal input value, we say he inputs ?. We cannot require in general that a WGT prevents such behaviour: this would require that the cheater was committed to his input, and it is not clear a priori that a WGT implies bit commitment (indeed some WGT’s don’t, as we shall see). The best we can ask for in case of active cheating is therefore that the following is satisfied:

– For any active cheating strategy followed by A (B), there exists an input value x such that A (B) learns nothing more than what is implied by the view of a passively cheating player with input x.

If this is satisfied, we say that the WGT is secure against active cheating (but note that the only security we ask for here is that active cheating does not give any advantage over passive cheating).

It should be clear that (γ, δ)-UNC, (p, q)-WOT and (p, q, ϵ)-WOT are special cases of WGT, where however it is only in the case of (γ, δ)-UNC that an adversary can choose between more than one output distribution function.

3 Impossibility results

The basic question we can ask is now: given a WGT, can we build OT or BC based on it? It is easy to characterize a class of WGT’s where the answer is no. For this, consider a case where we only allow noiseless communication between A and B, and consider any interactive protocol between them, of the following form:

– A starts with input x_{A}, B starts with input x_{B}.

– The players exchange a finite number of messages, and the protocol specifies at each stage a probabilistic algorithm for computing the next message, given the input, and all message and random coins seen so far.

– The view of a player (View_{A}/View_{B}) is as usual defined to be the input, all messages received and all random coins used. At the end, A and B compute their results, y_{A} and y_{B} from their views by some function, i.e., y_{Q} = f_{Q}(View_{Q}).

It is clear that any such protocol can be seen as a WGT by letting z_{A} = View_{A} and z_{B} = View_{B}; this method for producing y_{A}, y_{B}, z_{A}, z_{B} from x_{A}, x_{B} defines a probability measure D(x_{A}, x_{B}), and we define just one output distribution function output which always return D(x_{A}, x_{B}). Honest players will ignore anything except for the result specified (Y_{A}, Y_{B}), but a passively cheating player may use its entire view to compute extra information.

It is well known (and easy to see) that in a two-player scenario with only noiseless communication, OT and BC with information theoretic security is not possible, even if only passive cheating is assumed, and players are allowed infinite computing power. Hence, OT and BC are not reducible to the above WGT. We call such a WGT trivial.

We now show how to “implement” (p, q, ϵ)-WOT in this manner, where 2ϵ = 1 − p − q. Player’s A Consider the following protocol, in which A has input (b_{0}, b_{1}) and B has input c. Protocol SimNoisyWOT[p, q]((b_{0}, b_{1}), c)

1. With probability q, A announces (b_{0}, b_{1}), B computes b_{c} and the protocol terminates; otherwise, A announces “pass”.

2. If A passes, then with probability p/(1 − q), B sends c to A who replies with b_{c}; otherwise, B chooses b_{c} at random.

By a straightforward case analysis, B learns both b_{0} and b_{1} with probability q, A learns c with probability p and B receives an incorrect value of b_{c} with probability (1 − p − q)/2 = ϵ. Aside from easily simulated messages, such as “pass”, the view of each side corresponds to the view it could obtain from an actual run of a (p, q, ϵ)- WOT primitive. Now, suppose we had an 1–2 OT protocol based on a (p, q, ϵ)-WOT primitive. If we replaced each execution of the (p, q, ϵ)-WOT by an execution of the SimNoisyWOT[p, q] primitive, then the view of each party, taken in isolation, would be unchanged. Since the security of 1–2 OT (at least against passive adversaries) is defined solely by properties of player A’s view and by properties of player B’s view, then the resulting protocol would remain secure against passive adversaries. This would give a “mental 1–2 OT” protocol, information-theoretically secure against passive adversaries, a contradiction. Similarly, there is no information-theoretically secure (against both parties) mental bit commitment protocol, even if both parties are guaranteed to follow the Commit protocol; we can in a very similar way derive a contradiction.

The above argument implies the following lemma.

Lemma 1. There is no reduction from 1–2 OT or BC to (p, q, ϵ)- WOT when p + q + 2ϵ ≥ 1, even if only security against passive adversaries is required.

Remark: The simulation argument was for p + q + 2ϵ = 1. If p + q + 2ϵ > 1, choose ϵ′ = (1 − p − q)/2 < ϵ; the impossibility argument works for (p, q, ϵ′)-WOT. Note that a (p, q, ϵ′)-WOT primitive also meets the requirements of a (p, q, ϵ)-WOT primitive, since its error rate cannot be higher than ϵ, so a protocol that works for (p, q, ϵ)- WOT must work for (p, q, ϵ′)-WOT as well.

We now consider the case of the noisy channel. Consider the following purely mental protocol, in which A has input b.

Protocol SimUNC[γ](b)

1. A and B pick b_{A} and b_{B} respectively, such that P r(b_{A} = 1) = P r(b_{B} = 1) = γ.

2. A sends b′ = b ⊕ b_{A} to B. B computes b^{∗} = b′ ⊕ b_{B}, denoting b^{∗} as the received bit, while no output is defined for A.

Consider a WGT which between honest players A and B is a BSC with noise level δ, but where if A or B cheats passively, then some extra information is available and allows to reduce the noise level to γ, seen from the cheater’s point of view. Let us call this a (γ, δ)-PassiveUNC. It is similar to but not the same as a (γ, δ)- UNC. It immediately follows from the above protocol that a (γ, δ)- PassiveUNC is trivial if δ = 2γ(1 − γ), and in fact in general if δ ≥ 2γ(1 − γ). And so there is no reduction of 1–2 OT or BC to (γ, δ)-PassiveUNC in this case, not even if only passive security is required.

Now, suppose we have a reduction from 1–2 OT to a (γ, δ)-UNC, where δ = 2γ(1 − γ), one secure against active attacks. We compare the following two cases: In case 1 the reduction is attacked by an adversary using the following active cheating strategy for a player Q ∈ {A, B}: Q sets the noise level for the UNC to be γ always, and then does the following: Whenever Q is supposed to send a bit through the channel, Q first flips it with probability γ and then sends it. Similarly, whenever Q receives a bit from the channel, Q flips it with probability γ and acts as if that was the bit actually received. In any other cases, Q follows the algorithm specified by the reduction. Case 2: we execute the algorithm of the reduction substituting the (γ, δ)-UNC by a (γ, δ)-PassiveUNC, and the adversary executes a passive attack.

There is no difference between the cases from the honest player’s point of view. Observe that in case 1, the adversary following the strategy for Q knows as much about every bit sent and received by his opponent as a passive adversary knows in case 2. So since the reduction is secure in case 1, it must be secure in case 2, and we have a contradiction. Essentially the same argument works for bit commitment. So we have proved:

Lemma 2. There is no reduction from 1–2 OT or BC to (γ, δ)-UNC when δ ≥ 2γ(1 − γ).

This motivates the following interesting and open question: Which non-trivial cryptographic primitives (if any) can be implemented based on a WGT assuming only that it is non trivial?

4 Reducing 1–2 OT to (p, q)-WOT and (p, q, ϵ)-WOT

We now look at the possibility of building a 1–2 OT or commitments from a WOT. A reduction that accomplishes such a task can be thought of as a program that gets the noise levels of a UNC or the error probabilities of a WOT and a security parameter value k as input and then instructs at each point in time one of the players to either send a message in clear to the other player, or send a bit through the noisy channel. Any information known to the player at the time can be used, together with any number of random bits, to compute the next message to send. We make no assumption on the amount of computation required.

4.1 Preliminaries

For a reduction of 1–2 OT to UNC, let I_{c}(k, δ, γ), I_{b_{c}}(k, δ, γ), I_{b_{1−c}}(k, δ, γ) be the expected information that the sender obtains about c, the receiver obtains about b_{c}, and the receiver obtains about b_{1−c} respectively. We will say that the reduction works for values δ, γ, if

lim_{k→∞} I_{c}(k, δ, γ) = lim_{k→∞} I_{b_{1−c}}(k, δ, γ) = 0 and lim_{k→∞} I_{b_{c}}(k, δ, γ) = 1

For a reduction of 1–2 OT to (p, q)-WOT, we use the same definitions, but with (δ, γ) replaced by (p, q).

For a reduction of bit commitment to UNC, let I_{b}(k, δ, γ) be the expected information the receiver obtains about b in the Commit protocol, and let p(k, δ, γ) be the probability that the binding condition fails. We will say that the reduction works for values δ and γ, if

lim_{k→∞} I_{b}(k, δ, γ) = lim_{k→∞} p(k, δ, γ) = 0

We refer to [3] for a more sophisticated definition of 1–2 OT; our protocols meet this definition as well.

The set of pairs for which a reduction works will be called the range of the reduction. We will say that a reduction works efficiently in a point in its range, if the required convergence in k is exponential, and that the number of calls to the WOT or UNC is polynomial in k. This is usually required for a reduction to be useful in practice, but note that our impossibility results hold even if efficiency is not required.

4.2 Some useful reductions

We use the following two known reductions for basing 1–2 OT on (p, q)-WOT. The first is designed to reduce the chance the sender (A) learns too much, while the second is targeted against the chance of the receiver (B). Both reductions are assumed to be given as a black-box a protocol W implementing (p, q)-WOT and work with security parameter k. S-Reduce is taken from [9], while R-Reduce is more or less folklore.

Protocol S-Reduce(k, W)

1. Let b_{0}, b_{1} resp. c be the input of the sender, resp. the receiver.

2. W is executed k times, with inputs (b_{0i}, b_{1i}), i = 1..k from the sender and c_{i}, i = 1..k from the receiver. Here, the b_{0i}’s are uniformly chosen, such that b_{0} = ⊕_{i=1}^{k}b_{0i}, b_{1i} = b_{0i} ⊕ b_{0} ⊕ b_{1} and the c_{i}’s are uniformly chosen such that c = ⊕_{i=1}^{k}c_{i}.

3. The receiver computes his output bit as the xor of all bits received in the k executions of W.

Protocol R-Reduce(k, W)

1. Let b_{0}, b_{1} resp. c be the input of the sender, resp. the receiver.

2. W is executed k times, with inputs (b_{0i}, b_{1i}), i = 1..k from the sender and c_{i}, i = 1..k from the receiver. Here, c_{i} = c, b_{01} ⊕ ... ⊕ b_{0k} = b_{0} and b_{11} ⊕ ... ⊕ b_{1k} = b_{1}

3. The receiver computes the XOR of all bits received.

Lemma 3. When given k and a (p, q)-WOT W as input, S-Reduce(k, W) implements a (p^{k}, 1 − (1 − q)^{k})-WOT, and R-Reduce(k, W) implements a (1 − (1 − p)^{k}, q^{k})-WOT protocol. Both protocol produce a WOT secure against active cheating if the given WOT has this property.

Proof. First, it follows by inspection that the protocols allow the players to compute the correct output. As for the error probabilities, note that for S-Reduce a bad sender will learn c iff he learns all c_{i}’s, which happens with probability p^{k}. On the other hand, a bad receiver can learn both b_{0} and b_{1} if he learns just one pair (b_{0i}, b_{1i}), and this happens with probability 1−(1−q)^{k}. The case of R-Reduce is similar, but with the chances of sender and receiver reversed. The last claim follows easily: In S-Reduce security of W means that non of the parties can gain anything from inputting ? to W. And if indeed no ? is input to any W instance, R always behaves consistently with some input c, namely the value c = ⊕_{i=1}^{k}c_{i}. S can behave inconsistently by choosing bad values of his bits, but this will not give him more information on c. The case of R-Reduce is similar. ⊓ ⊔

4.3 A reduction to (p, q)-WOT

Lemma 4 shows that the lower bound given by Lemma 1 is tight when ϵ = 0. Lemmata 1 and 4 imply Theorem 1.

Lemma 4. There exists a reduction for building 1–2 OT from a (p, q)-WOT, the range of which is {p, q| p + q < 1}. It works efficiently for all points in its range.

Proof. Suppose we start with a (p, q)-WOT W, and then apply first R-Reduce(t, W) and then S-Reduce(t′, W). We will call this RS-Reduce. It follows easily that this produces a ((1−(1−p)^{t})^{t′}, 1−(1− q^{t})^{t′})-WOT. Of course, we can also apply S-Reduce first, and obtain a (1−(1−p^{t})^{t′}, (1−(1−q)^{t})^{t′})-WOT. This will be called SR-Reduce.

The strategy for our reduction will be to apply repeatedly SR-Reduce or RS-Reduce, in order to reduce as quickly as possible the sum of the error probabilities. When given errors (p, q), we will apply RS-Reduce if p ≤ q, and SR-Reduce otherwise. This will be called one step in the reduction.

To analyse the effect of one step, define x = q, y = 1 − p when p ≤ q, and x = p, y = 1 − q otherwise. It follows that the difference between the sum of the errors before and after the transformation is

f(t, t′, x, y) = (1 − y^{t})^{t′} + 1 − (1 − x^{t})^{t′} − (1 − y + x)
= (1 − y^{t})^{t′} + y − ((1 − x^{t})^{t′} + x)

The constraints we have on p, q imply that 1/2 < y < 1 and 1 − y ≤ x < y. And we see that the progress we make is the difference between the values of the function g_{t,t′}(z) = (1 − z^{t})^{t′} + z in points x and y. The trick is now to choose, given x, y values of t, t′ such that the above difference becomes numerically “large”. Note that since we are subtracting the sum before the step from the sum after, the difference is hopefully negative.

In any situation where the error probability sum before a step is greater than 0.2, one of the following three cases apply:

y ≤ 0.8. This is a case where the smallest of p, q is at least 0.2, so p, q are both ”large”. In this case, we choose t = t′ = 2. By direct inspection of g_{2,2}(x), one finds that for any x, y obeying the restrictions, (g_{2,2}(y) − g_{2,2}(x))/(y − x) ≤ −0.1. Since y − x = 1 − (p + q), this shows that taking one step in this case multiplies the distance from p + q to 1 by a factor of at least 1.1.

y > 0.8, x > .4. In this case, p + q is also ”large”, but this time because one probability is small and the other is large. In this case, we choose t = 2, t′ = 1. Again, by direct inspection, one can verify that (g_{2,1}(y) − g_{2,1}(x))/(y − x) ≤ −0.2. By the same argument as before, we see that in this case, the distance from p + q to 1 is multiplied by at least 1.2 by taking one step.

y > 0.8, x ≤ .4. In this case, both p and q and hence p + q are ”small”. We choose t = t′ = 2. Observe that for the large y, g_{2,2}(y) approaches y as y approaches 1, while for the small x, g_{2,2}(x) approaches 1 + x as x approaches 0. As a result, (g_{2,2}(y) − g_{2,2}(x))/(1 − y + x) ≃ −1 for small x and large y, and is in fact less than −0.2 for the range specified. However, 1−y +x = p+q, so we see that in this case, taking one step multiplies p + q by a factor of at most 0.8.

As soon as we have an error probability sum which is at most 0.2, we will start doing steps where we always have t = t′ = 4. In this case one finds that is the error sum was s before a step is at most s^{2} after.

The overall strategy is now as follows: we first do whatever number of steps is necessary to bring the error probability sum below 0.2. We then do log_{2}(k) steps, where k is the security parameter. It follows from the above that the resulting error probability sum is exponentially small in k, at most 0.2^{k}. The number of calls we make to the WOT is exponential in the number of steps, but since we only take a logarithmic number of steps, the total number of calls is polynomial in k. ⊓ ⊔

Above, we have only considered p, q as being constants. However, even if we have a case where p + q is a function of some parameter n and converges polynomially to 1 in n, e.g. p(n) + q(n) = 1 − 1/n, the reduction in the proof still works in time polynomial in n: as mentioned, the number of calls to the original WOT is exponential in the number of steps taken, but since the convergence in the reduction for large p + q is exponential in the number of steps, we only have to take a logarithmic number of steps before the error probability sum falls below 0.2.

4.4 A reduction to (p, q, ϵ)-WOT

Lemma 1 shows that no reduction of 1-2-OT to (p, q, ϵ)-WOT exists if p + q + 2ϵ ≥ 1 and this, even in the case of passive adversaries. We show that if p + q + 2ϵ < 0.45, such a reduction does exist. We adapt SR-Reduce to deal with transmission errors. We then characterize triplets (p, q, ϵ) for which 1–2 OT is reducible to (p, q, ϵ)-WOT. The reduction we consider assumes only passive adversaries.

The following error detection phase accepts parameter l > 0 and, given a (p, q, ϵ)-WOT W, produces a (p′, q′, ϵ′)-WOT W′ such that ϵ′ < ϵ. As usual b_{0} and b_{1} denote the two bits to be transmitted and c is the selection bit.

Protocol ErRed(l, W)

1. A chooses q_{0}, q_{1} ∈_{R} {0, 1} and B chooses s ∈_{R} {0, 1},

2. A sends l times the bits (q_{0}, q_{1}) through the (p, q, ϵ)-WOT W and B selects the bit q_{s} l times,

3. If B did not receive the same bits q̂_{s} l times then A and B go to Step 1.

4. B announces y = 0 if s = c and y = 1 otherwise.

5. A announces r_{0} and r_{1} such that b_{y} = r_{0} ⊕ q_{0} and b_{1−y} = r_{1} ⊕ q_{1}, allowing B to compute b_{c} = q̂_{s} ⊕ r_{s}.

We are now ready to describe a reduction of 1–2 OT to (p, q, ϵ)- WOT which basically inserts calls to ErRed into SR-Reduce (and RS-Reduce). Given positive integers l_{0}, k, l_{1}, k′, l_{2} and a (p, q, ϵ)-WOT W_{0}, protocol SR_{ε} produces a new (p′, q′, ϵ′)-WOT W:

Protocol SR_{ε}(l_{0}, k, l_{1}, k′, l_{2}, W_{0})

– W ← ErRed(l_{2}, R-Reduce(k′, ErRed(l_{1}, S-Reduce(k, ErRed(l_{0}, W_{0}))))).

RS_{ε}(l_{0}, k, l_{1}, k′, l_{2}) is defined the same way except the calls to S-Reduce and R-Reduce are permuted. Similarly to lemma 3, one can characterize exactly the transformation taking place in a call to SR_{ε}(l_{0}, k, l, k′, l′) for any parameters l_{0}, k, l, k′, and l′. In particular, SR_{ε}(l_{0}, k, l, k′, l′) transforms a (p, q, ϵ)-WOT into a (p′, q′, ϵ′)-WOT where p′ = 1 − (1 − (1 − (1 − p)^{l_{0}})^{k})^{l_{1}·k′·l_{2}}, q′ = 1 − (1 − (1 − (1 − q)^{l_{0}·k·l_{1}})^{k′})^{l_{2}}, and ϵ′ is of similar but slightly more complicated form. A brute force analysis, using linear programming, shows that SR_{ε} can be tuned to work at 45% the optimum (the sketch of the proof can be found in [11]).

Lemma 5. Reduction SR_{ε} implements 1–2 OT given any (p, q, ϵ)- WOT that satisfies p + q + 2ϵ ≤ 0.45.

The above bound is not tight especially whenever one of p + q and ϵ is small. In particular, SR_{ε} works for all (p, q, 0) such that p + q < 1 and for all (0, 0, ϵ) such that ϵ < \frac{1}{2}. A natural question arises: Is it possible to use a different method for choosing parameters l_{0}, k, l_{1}, k′ and l_{2} such that reduction SR_{ε} works also for p + q + 2ϵ ≫ 0.45? Next theorem suggests that if one wants to get closer to the bound p + q + 2ϵ = 1, one has to find a different reduction.

Lemma 6. There exists triplets (p, q, ϵ) that satisfy p+q+2ϵ ≤ 0.70 such that SR_{ε} does not work for any value of parameters l_{0}, k, l_{1}, k′ and l_{2}.

Proof (sketch). Let p = q = 0.2 and ϵ = 0.15 be the parameters of a WOT that satisfies p + q + 2ϵ = 0.7. It can be shown that whatever the parameters l_{0}, k, l_{1}, k′ and l_{2} are, SR_{ε} always generates an intermediary simulatable triplet. ⊓ ⊔ Lemma 6 suggests that introducing noise in a WOT might lead to a primitive that is strictly weaker than 1–2 OT even for nonsimulatable but noisy WOT. However, the gap between the bounds could be narrowed down by finding a better simulation and/or a new reduction. It is unknown to us if such a gap necessarily exists.

5 Reducing bit commitment to (γ, δ)-UNC

5.1 Preliminaries Our commitment protocol makes extensive use of t-universal hash functions, first introduced in [10]; we use the following slightly stronger notion that has become more or less standard. Given a domain D and a range R, a t-universal family of hash functions is a distribution H on a set of functions {h_{i}} such that for any distinct X_{1}, …, X_{t} ∈ D, if h is chosen according to H, the induced distribution on (h(X_{1}), …, h(X_{t})) is uniform over R^{t}. For our application, D = {0, 1}^{k}, R = {0, 1}^{l}, for some k, l. For any k and l, there exists a t-universal family of hash functions whose functions may be represented using poly(k, t) bits, and for which the operations of sampling h from the distribution and computing h(X) may be performed in poly(k, t) time. Hence, we will speak of one party “sending” a function, abstracting all representational details.

Given two bit-sequences X and X′, let d(X, X′) denote their Hamming distance, i.e., the number of places where they differ. We will use distance as shorthand for Hamming distance.

There is a huge body of literature on universal hash functions and their use in cryptography. Despite superficial differences, our method is quite similar to that of [16].

5.2 What we need to achieve Note that it suffices to produce a protocol for committing to x = r for a random bit r; as a standard trick one can commit to y = b by revealing b′ = b ⊕ r and defining y = x ⊕ b′. For the rest of the discussion, we analyze the case of committing to random values. We also allow the receiver to reject even though the commiter followed the protocol, but only with probability negligible in the security parameter, k.

5.3 The protocol

On a high level, our (weak) commitment protocol consists of the following steps. First, C sends string X over the noisy channel to C. R queries C about the value of h_{i}(X) for i = 1, 2. Finally, C chooses a hash function h and designates h(X) as the random committed value. To reveal a bit, C sends X to R. R accepts if X is close to the received value and is consistent with the queried hash values. Protocol Commit(γ, δ, k)

Define d_{0} by γ(1 − d_{0}) + (1 − γ)d_{0} = δ and let d_{1} = (d_{0} + γ)/2, d = (d_{1} + γ)/2 and

ℓ = ⌊lg (∑_{i=1}^{⌊dk⌋} \binom{k}{i})⌋ ,

i.e., ℓ is the log of the number of elements in a Hamming sphere with radius dk. We let d^{∗} = (d_{1}+d)/2, and define ℓ^{∗} as ℓ, where we replace dk by d^{∗}k. Note that, by a standard argument, it follows that ℓ − ℓ^{∗} > ck for some constant c as k grows sufficiently large. Let H, H_{1}, H_{2} be canonical 64k-universal families of hash functions from {0, 1}^{k} to {0, 1}, {0, 1}^{ℓ^{∗}}, {0, 1}^{ℓ−ℓ^{∗}}.

1. C uniformly chooses X = x_{1}, …, x_{k} ∈ {0, 1}^{k} and sends X to R over the (γ, δ) channel. Denote by X′ = x′_{1}, …, x′_{k} the string received by R.

2. For i = 1 to 2

R chooses h_{i} ← H_{i} and sends h_{i} to C.

C sends y_{i} = h_{i}(X) to R.

3. C chooses h ← H and sends h to C. The committed bit is defined as h(X).

Protocol Open(γ, δ, k)

Let δ′ = γ(1 − d_{1}) + (1 − γ)d_{1} and let X, X′, y_{1}, y_{2}, h, h_{1}, h_{2}, d_{0}, d_{1} and d be as in the execution of Commit for the bit to be opened.

1. C sends X to R.

2. R rejects if y_{i} ≠ h_{i}(X) for any i or if d(X, X′) ≥ δ′k locations. Otherwise, R accepts the committed value of h(X).

5.4 Analysis of the protocols

We first observe that the protocol behaves correctly if both parties are honest. For the rest of this discussion, “negligible” means smaller than 1/k^{c}, for any c, as k grows sufficiently large and “almost always” means with probability negligibly close to 1. Proofs of some of the Lemmata below are sketched in Section B in the appendix.

Lemma 7. If C and R both correctly execute Commit and Open, then R accepts the value r = h(X) almost always (where h and X are as generated by C during Commit.

We next show that the commiter has only a negligible probability of breaking the commitment scheme.

Lemma 8. Regardless of C’s strategy for generating X,(h_{1}, y_{1}), (h_{2}, y_{2}) during Commit, there will almost certainly be at most one string, denoted X^{∗}, that C can send R with a nonnegligible probability of acceptance.

Hence, C is committed to h(X^{∗}). Note that C can ensure that h(X^{∗}) is not random, but this does not constitute a break of the commitment scheme. In the reduction from a standard commitment protocol to a random-bit commitment protocol, C and only C benefits from the randomness of the committed bit.

Proof sketch We first define a set of viable X^{∗} that C can reasonably send during the Open protocol.

Definition 1. Given X, (h_{1}, y_{1}), (h_{2}, y_{2}). We say that X^{∗} is viable if it differs from X in at most d^{∗}k places and y_{i} = h_{i}(X^{∗}) for i = 1, 2.

Proposition 1. If X^{∗} is not viable, then C will accept X^{∗} with negligible probability, where the probability is taken over the behavior of the noisy channel.

We can view the process of generating (h_{i}, y_{i}) as progessively constraining and shrinking the viable set S. Initially, the viable set S consists of those strings whose distance from X is at most d^{∗}k .

We use the following result by Rompel [17]

Lemma 9. Let X_{1}, ..., X_{n} be a set of t-wise independent random variables taking 0/1 values. Let X = ∑_{i} X_{i}, and μ = E(X). Then for any A > 0,

P r(|X − μ| > A) < O((\frac{tμ + t^{2}}{A^{2}} )^{t/2})

Fix any string y ∈ {0, 1}^{ℓ^{∗}}, and define X_{i} as X_{i} = 1 iff the i’th viable string is mapped to y by h_{1}; X_{i} = 0 otherwise. Then clearly, μ = 1. We will apply the above lemma with t = 4k and A = t^{2}, and we will say that y is bad if its preimage under h_{1} has more than t^{3} viable strings in it. The lemma can be used because the X_{i}’s by construction are 64k > t-wise independent. It immediately implies that the probability that y is bad is at most 2^{−t/2}. The probability that ANY y is bad is at most 2^{ℓ^{∗}} ≤ 2^{k} times larger, so since we have chosen t = 4k, even this last probability becomes exponentially small (in k). So except with exponentially small probability, at most t^{3} = 64k viable strings remain. The final constraint added is the value of h_{2}(X). Since h_{2} is 64k-universal and ℓ − ℓ^{∗} > ck, we can view this constraints as assigning at least ck random bits to each string X^{∗} ∈ S. In order for two strings X_{1}^{∗}, X_{2}^{∗} ∈ S to both remain viable, they must both receive the same bit sequence; the probability of this occurring for any such pair is negligible. ⊓ ⊔

Finally, we show that after Commit, R can predict r with only a small edge.

Lemma 10. At the conclusion of Commit, the expected amount of information R holds about h(X) is exponentially small in k.

6 Reducing 1–2 OT to (γ, δ)-UNC

We first reduce 1–2 OT to (γ, δ)-PassiveUNC by a reduction secure against passive adversaries. The reduction is a straightforward adaptation of a reduction of Crépeau and Kilian [9] that builds 1–2 OT from a BSC. The same procedure is then shown to reduce 1–2 OT to (γ, δ)-UNC. Bit commitments can finally be used to tolerate active adversary for the same price.

In appendix A, reduction WOTfromPassiveUNC is described. Given a (δ, γ)-PassiveUNC, it produces a (p(δ, γ), q(δ, γ), ϵ(δ))-WOT W that can be used in reduction SRE_{ε}. Using lemma 5, 1–2 OT can be obtained from any (δ, γ)-PassiveUNC that satisfies p(δ, γ)+q(δ, γ)+ 2ϵ(δ) ≤ 0.45. Unlike the bit commitment case, we were not able to show that as soon as the unfairness of the PassiveUNC is not simulatable then 1–2 OT is possible. Nevertheless, the next lemma gives a partial answer leaving a ”grey” area of values for γ, δ where neither the impossibility result, nor our reduction applies. Due to space limitations, we refer the reader to [11] for the proof of next lemma.

Lemma 11. There exists a reduction secure against passive cheating of 1–2 OT to (γ, δ)-PassiveUNC such that α^{3}β^{3}(1 − ζ(1 − α)) > \frac{0.775+ϵ(δ)}{1−ϵ(δ)} where ϵ(δ) = \frac{δ^{2}}{δ^{2}+(1−δ)^{2}} , α = \frac{1−δ−γ}{1−2γ},β = \frac{1−γ}{1−δ} , and ζ = \frac{1−γ}{δ}.

To give a numerical example, when δ = .075, one can reduce 1–2 OT to (γ, δ)-PassiveUNC for γ ≈ .06; no such reduction is possible for γ < .039.

The reduction is also secure when a (γ, δ)-UNC is used instead of a (γ, δ)-PassiveUNC. Lemmata 12 and 13 establish this fact. First, we define a (γ, δ)-SemiPassiveUNC adversary as an adversary acting upon a (γ, δ)-UNC with the noise level of all transmissions set to γ. In addition, if the adversary wants to send the bit b, (s)he picks a random bit r such that Pr (r = 1) = (δ − γ)/(1 − 2γ) and sends b′ = b ⊕ r through the UNC (with the noise level sets to γ). The following lemma is straightforward.

Lemma 12. Any secure reduction to a (γ, δ)-PassiveUNC is also a secure reduction to a (γ, δ)-SemiPassiveUNC.

Lemma 13. Any secure reduction to a (γ, δ)-SemiPassiveUNC is a secure reduction to a (γ, δ)-UNC.

Proof (sketch). The only possibility not directly simulatable by a SemiPassiveUNC, is for the sender to lower the noise level of a UNC transmission. This clearly is of no help since this only increases the information of the receiver. The only problem that might arise is to break the correctness of the reduction. This cannot happen since a curious receiver has anyway access to this information. ⊓ ⊔

Any reduction of 1–2 OT to PassiveUNC that is secure against passive cheating can handle the case of active cheating as well by proceeding along the same lines as [5]. To briefly sketch the construction, we first note that once A and B get a bit commitment scheme, they can prove in ZK that they followed the protocol honestly [12]. One problem, is to show that a bit sent through the noisy channel is the one that the sender is supposed to have selected according the protocol. Similarly, the receiver should be able to prove that he uses the bits received through the channel according the protocol description. This can be solved by using bit commitments in a cut and choose protocol ensuring the receiver that the sender is committed to the transmitted value. The same method can be used to make sure that the receiver is committed to what has been received. The result being that from an UNC (resp. PassiveUNC) and a bit commitment scheme, a committed UNC (resp. PassiveUNC) is built. It is easy to devise a polynomial time protocol that given a (γ, δ)-PassiveUNC produces a (γ, δ + \frac{1}{p(n)}) committed UNC (resp. PassiveUNC) where p(n) is any polynomial in the security parameter n. The resulting committed transfer is then used to prove that the bit sent and received have been chosen properly. Using lemmata 12 and 13 and the above argument leads to the following corollary:

Corollary 1. Lemma 11 applies against active adversaries for both the (γ, δ)-PassiveUNC and the (γ, δ)-UNC.

References

1. C. H. Bennett, G. Brassard, C. Crépeau, and U. M. Maurer. “Generalized privacy amplification”. In Proc. 1994 IEEE International Symp. of Information Theory, pages 350–350, 1994. Trondheim, Norway, June 27-July1, 94.

2. G. Brassard and C. Crépeau. “Oblivious transfers and privacy amplification”. In Proceedings of EUROCRYPT ’97, Springer-Verlag LNCS series, vol. 1223, pp. 334-347, 1997.

3. G. Brassard, C. Crépeau, and M. Sántha.“Oblivious Transfer and Intersecting Codes”. In IEEE Transaction on Information Theory, special issue on coding and complexity, vol. 42, No. 6, pp.1769–1780, 1996.

4. C. Cachin. “On the Foundations of Oblivious Transfer”, Proceedings of EuroCrypt ’98, Springer-Verlag LNCS series, vol. 1403, pp. 361-374.

5. C. Crépeau. “Verifiable disclosure of secrets and applications”. In J.-J. Quisquater and J. Vandewalle, editors, Proceeding of Eurocrypt ’89, Springer-Verlag, LNCS series, vol. 434, pp.150-154, 1998.

6. C. Crépeau. “Efficient Cryptographic Protocols based on Noisy Channels”, Proceedings of EuroCrypt 97, Springer-Verlag LNCS series, vol.1233, pp.306-317.

7. C. Crépeau. Private communication, 1998.

8. C. Crépeau.“Equivalence between two flavours of oblivious transfer”,Proceedings of Crypto ’87, Springer Verlag LNCS series, pp.350-354, 1987.

9. C. Crépeau and J. Kilian.“Achieving Oblivious Transfer using Weakened Security Assumptions”, Proceedings of FOCS 88, pp.42-52, 1988.

10. L. Carter and M. Wegman. “Universal Classes of Hash Functions”. JCSS, 18, pp. 143–154, 1979.

11. I. Damgård, J. Kilian, and L. Salvail, “On the (Im)possibility of basing Oblivious Transfer and Bit Commitment on Weakened Security Assumptions”, BRICS report, vol., pp. xxx–yyy, 1999.

12. O. Goldreich, S. Micali, and A. Wigderson, “Proofs That Yield Nothing but Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems”, J. Assoc. Comput. Mach., vol. 38, pp. 691–729, 1991.

13. J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby. “Construction of a pseudo-random generator from any one-way function”. Technical Report TR-91-068, International Computer Science Institute, Berkeley, CA, 1991.

14. J. Kilian. “A general completeness theorems for 2-party games”. In Baruch Awerbuch, editor, Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing, pages 553–560, New Orleans, LS, May 1991.

15. U.M. Maurer.“Secret Key Agreement by Public Discussion from Common Information”, IEEE Trans. Info. Theory, vol. 39, p.733-742, 1993.

16. M. Naor, R. Ostrovsky, R. Venkatesan, and M. Yung. “Perfect zeroknowledge arguments for NP using any one-way permutation”. Journal of Cryptology, vol. 11, 1998.

17. J. Rompel: Techniques for Computing with Low-Independence Randomness, PhDthesis, MIT, 1990.

A WOT from PassiveUNC

In this appendix, we give the reduction of WOT to PassiveUNC.

Protocol WOTfromPassiveUNC(b_{0}, b_{1})(c)

1. A picks x, y ∈_{R} {0, 1},

2. A sends (xx, yy) through the PassiveUNC(γ, δ) and B receives (x̂x̂′, ŷŷ′),

3. If B receives (x̂ ⊕ x̂′, ŷ ⊕ ŷ′) ∉ {(0, 1), (1, 0)} then they go to step 1.

4. B announces w such that – w = 0 if ((x̂ ⊕ x̂′ = 0) ∧ (c = 0)) ∨ ((ŷ ⊕ ŷ′ = 0) ∧ (c = 1))

– w = 1 if ((x̂ ⊕ x̂′ = 0) ∧ (c = 1)) ∨ ((ŷ ⊕ ŷ′ = 0) ∧ (c = 0))

5. A announces – (a, b) = (x ⊕ b_{0}, y ⊕ b_{1}) if w = 0,

– (a, b) = (y ⊕ b_{0}, x ⊕ b_{1}) if w = 1,

6. B computes – b_{0} = a ⊕ x̂ if c = 0 and w = 0,

– b_{0} = a ⊕ ŷ if c = 0 and w = 1,

– b_{1} = b ⊕ ŷ if c = 1 and w = 0,

– b_{1} = b ⊕ x̂ if c = 1 and w = 1.

B Proofs from Section 5

Proof Sketch of Lemma 7 By inspection, if R accepts it will always recover r = h(X) (assuming C is good), and R will only reject if X and X′ differ in at least δ′k places. Now, since δ < 2γ(1 − γ), d_{0} < d_{1} < γ and hence δ′ > δ. However, for each i, x′_{i} ≠ x_{i} with independent probability at most δ, so by a standard Chernoff bound, the probability that x′_{i} ≠ x_{i} in δ′k is negligible in k. Note that by the universality of H, r is distributed uniformly over {0, 1}. ⊓ ⊔

Proof Sketch of Proposition 1 Clearly, R will reject if y_{i} ≠ h_{i}(X^{∗}). Suppose that X^{∗} differs from X in d^{∗}k places and the channel flips each bit with probability at least γ. Then X^{∗} and X′ will differ in at least δ^{∗}k expected places, where δ^{∗} = γ(1−d^{∗})+(1−γ)d^{∗} > δ′. By a standard Chernoff bound, they will almost always differ in more than δ′k places, causing R to reject. ⊓ ⊔

Proof Sketch of Lemma 10 First, we conceptually give R the value of d(X′, X); this can only help R. Let set S denote those Xs of the given distance; after receiving X′, each X ∈ S is equally likely.

We first observe that for some constant c_{1} > 0, H(X′, X)−dn ≥ c_{1}n almost always; it follows that for some constant c_{2} > 0, |S|/2^{ℓ} ≥ 2^{c_{2}k}.

Now, after receiving X′, R can obtain h_{1}(X), h_{2}(X). Note that we cannot assume these functions are chosen randomly. Still, conceptually, we can view R as flipping its random coins (if it uses any) and then constructing a (quite shallow) decision tree. Each interior vertex v is labelled with a hash function h to be sent to C; the edges from v to its children correspond to the possible answers C might give (2^{ℓ^{∗}} possibilities in the first level, 2^{ℓ−ℓ^{∗}} in the second).

For every vertex v in the tree we define the set S_{v} as those X ∈ S that are consistent with the sequence of hash functions and answers given on the path from the root vertex to v. We can view Step 2 of Commit as a traversal from the root of the tree to a leaf l.

By a simple probability argument, the probability that a given leaf l is reached is |S_{l}|/|S|, and the conditional distribution on X is uniform over S_{l}. Since the tree has only 2^{ℓ} leaves, the probability of reaching a leaf l with |S_{l}| < 2^{c_{2}k/2} is at most 2^{−c_{2}k/2}; we can safely ignore this event. On the other hand, in every case where |S_{l}| ≥ 2^{c_{2}k/2}, it follows immediately from the privacy amplification result in [1] that R’s expected information about h(X) is exponentially small. ⊓ ⊔

Recent BRICS Report Series Publications

RS-98-37 Ivan B. Damgård, Joe Kilian, and Louis Salvail. On the (Im)possibility of Basing Oblivious Transfer and Bit Commitment on Weakened Security Assumptions. December 1998. 22 pp. To appear in Advances in Cryptology: International Conference on the Theory and Application of Cryptographic Techniques, EUROCRYPT ’99 Proceedings, LNCS, 1999.

RS-98-36 Ronald Cramer, Ivan B. Damgård, Stefan Dziembowski, Martin Hirt, and Tal Rabin. Efficient Multiparty Computations with Dishonest Minority. December 1998. 19 pp. To appear in Advances in Cryptology: International Conference on the Theory and Application of Cryptographic Techniques, EURO-CRYPT ’99 Proceedings, LNCS, 1999.

RS-98-35 Olivier Danvy and Zhe Yang. An Operational Investigation of the CPS Hierarchy. December 1998.

RS-98-34 Peter G. Binderup, Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, and Sven Skyum. The Complexity of Identifying Large Equivalence Classes. December 1998. 15 pp.

RS-98-33 Hans Hüttel, Josva Kleist, Uwe Nestmann, and Massimo Merro. Migration = Cloning ; Aliasing (Preliminary Version). December 1998. 40 pp. To appear in 6th International Workshop on the Foundations of Object-Oriented, FOOL6 Informal Proceedings, 1998.

RS-98-32 Jan Camenisch and Ivan B. Damgård. Verifiable Encryption and Applications to Group Signatures and Signature Sharing. December 1998. 18 pp.

RS-98-31 Glynn Winskel. A Linear Metalanguage for Concurrency. November 1998. 21 pp.

RS-98-30 Carsten Butz. Finitely Presented Heyting Algebras. November 1998. 30 pp.

RS-98-29 Jan Camenisch and Markus Michels. Proving in Zero-Knowledge that a Number is the Product of Two Safe Primes. November 1998. 19 pp, to appear in Advances in Cryptology: International Conference on the Theory and Application of Cryptographic Techniques, EUROCRYPT ’99 Proceedings, LNCS, 1999.