Oblivious Transfer with a Memory-Bounded Receiver

Christian Cachin

M.I.T.^{∗}

Claude Crépeau^{†}

McGill University ^{‡}

Julien Marcil^{†}

Université de Montréal ^{§}

Abstract

We propose a protocol for oblivious transfer that is unconditionally secure under the sole assumption that the memory size of the receiver is bounded. The model assumes that a random bit string slightly larger than the receiver’s memory is broadcast (either by the sender or by a third party). In our construction, both parties need memory of size in θ(n^{2−2α}) for some α < \frac{1}{2}, when a string of size N = n^{2−α−β} for α > β > 0 is broadcast, whereas a malicious receiver can have up to γN bits of memory for any γ < 1. In the course of our analysis, we provide a direct study of an interactive hashing protocol closely related to that of Naor et al. [NOVY98].

1 Introduction

Oblivious transfer is an important primitive in modern cryptography. It was introduced to cryptography in several variations by Rabin and Even et al. [Rab81, EGL83] and had been studied already by Wiesner [Wie70] (under the name of “multiplexing”), in a paper that marked the birth of quantum cryptography. Oblivious transfer has since become the basis for realizing a broad class of cryptographic protocols, such as bit commitment, zeroknowledge proofs, and general secure multiparty computation [Yao86, GMW87, GV88, Kil88a, CvdGT95].

In a one-out-of-two oblivious transfer, denoted \binom{2}{1}-OT, one party Alice owns two secret bits b_{0} and b_{1}, and another party Bob wants to learn b_{c} for a secret bit c of his choice. Alice is willing to collaborate provided that Bob does not learn any information about b_{c⊕1}, but Bob will not participate if Alice can obtain information about c.

Traditionally, the security of \binom{2}{1}-OT is based on computational assumptions, such as the hardness of factoring or the existence of trapdoor one-way permutations [EGL83, GMW87, BM90]. \binom{2}{1}-OTcan also be implemented in terms of Rabin’s OT [Rab81], in which Alice sends a bit b that is received by Bob with probability \frac{1}{2} [Cré88]. The security of Rabin’s protocol for OT is based on the quadratic residuosity problem.

These are relatively strong computational assumptions. However, it is also known that OT cannot likely be based on weaker assumptions: Proving that OT is secure assuming only a one-way function in a black-box reduction is as hard as proving P≠NP [IR89]. OT falls thus, together with key agreement, in the class of tasks that are only known how to implement using at least trapdoor one-way functions.

However, if Alice and Bob have access to a quantum channel, Oblivious Transfer can be reduced to a weaker primitive known as Bit Commitment [BBCS92, Cré84] and thus is secure assuming only a one-way function in the quantum computer model. Oblivious transfer can also be based on a noisy channel, as shown by Crépeau and Kilian [CK88, Cré97].

In this paper we describe how a bound on memory size of the receiver Bob can be used to implement oblivious transfer. We assume that there is an initial broadcast of a huge amount of random data, during which Bob is free to compute any probabilistic function with unlimited power. As long as the function’s output size is bounded and does not exceed Bob’s memory size (storage space), we can prove that the OT protocol is secure. No computational or memory restrictions are placed on Alice.

In order to carry out the protocol, both parties need to use some amount of memory, however. Let α, β be constants such that 0 < β < α < \frac{1}{2} (e.g. a small β and α = \frac{1}{2} − β). In our construction, both parties need memory of size in θ(n^{2−2α}) when N = n^{2−α−β} random bits are broadcast. The security of the oblivious transfer can be shown if Bob has no more than γN bits of storage for any γ < 1.

The random broadcast can be generated by a trusted random source, which needs not necessarily be an artificial device. Natural sources, such as deep-space radio sources or the cosmic background radiation could also be used. On the other hand, there is no need for a trusted third party to generate the random data. Alice can also generate the random bits herself and send them to Bob, since no assumption about her memory limitation is made.

∗MIT Laboratory for Computer Science, Cambridge, MA 02139, USA, cachin@acm.org.

† Supported in part by Canada’s NSERC and Québec’s FCAR.

‡School of Computer Science, McGill University, Montréal (Québec), Canada, crepeau@cs.mcgill.ca.

§Département d’Informatique et R.O., Université de Montréal, Montréal (Québec), Canada, marcilj@iro.umontreal.ca.

The study and comparison of different assumptions under which cryptographic tasks can be realized is an important aspect of research in cryptography. Perhaps the most prominent assumptions used today in the computational security model are factoring, the discrete logarithm problem, and lattice reduction problems [AD97]. However, factoring and computing discrete logarithms could be solved efficiently on a quantum computer [Sho94], while exisitng systems based on lattice reductions have been cryptanalised [NS98]. Alternatives to computational security assumptions that have been proposed include quantum cryptography, the noisy channel model, and memory bounds [CM97].

The memory bound model seems realistic in the view of current communication and high-speed networking technologies that allow transmission at rates of multiple gigabits per second. Storage systems on the order of petabytes, on the other hand, require a major investment by a potential adversary. Furthermore, the model is attractive for the following reasons: (1) the security can be based only on the assumption about the adversary’s memory capacity. (2) storage costs scale linearly and can therefore be estimated accurately. (3) memory bounds offers permanent protection in the sense that future technological improvements cannot retrospectively compromise the security of messages transmitted earlier.

Smartcards provide a particularly well suited scenario to implement our protocol. In such a scenario, Alice could be a teller machine and Bob a card. Limiting the computing power of a card is a resonable assumption whereas a similar limitation on the teller machine would be much less resonable. Since \binom{2}{1}-OT in one direction is sufficient to implement it in both directions (see [CS91]), any two-party cryptographic task may be implemented securily in this situation from our protocol. For instance, a mutual identification scheme may be realized [CS95].

1.1 Our Construction

We provide an implementation of \binom{2}{1}-OT. During the initial random broadcast, Alice and Bob both store a random subset of the N bits such that their parts overlap in k positions. Then they engage in a protocol to form two sets of k bits each among the bits stored by Alice: a “good” set consisting of the bits also known to Bob and a “bad” set containing at least some bits unknown to Bob. This is done using an interactive hashing protocol similar to that of Naor et al. [NOVY98].

Interactive hashing is a protocol between Alice and Bob for isolating two binary strings. One string is chosen by Bob and the other one is chosen randomly, without (much) influence by Bob. However, Alice does not learn which string corresponds to Bob’s input. In order to apply interactive hashing, we use two tools of independent interest.

The first tool is an efficiently computable, dense encoding of k-element subsets from {1, …, n}, i.e., a mapping of k-element subsets to binary strings of length lg \binom{n}{k}. It has to be efficient in the sense that encoding and decoding operate in time polynomial in n rather than \binom{n}{k}, even if k is proportional to n. Such a scheme has been long known in the litterature [Cov73]. The second tool is a direct analysis of interactive hashing, since the original analysis is based on simulators and not directly applicable to our setting.

Once two binary strings corresponding to the two sets are isolated, it will be the case that Bob knows all bits in the good set, but only few bits in the bad set. Then Bob asks Alice to encode b_{0} and b_{1} using the two sets such that b_{c} is encoded with the good set and b_{c⊕1} with the bad set. Bob can recover b_{c} since he knows the good set, but not b_{c⊕1}. Additional results used to show the security of the protocol are privacy amplification (or entropy smoothing) by universal hashing [BBCM95] and a theorem by Zuckerman about the min-entropy of a randomly chosen substring [Zuc96].

1.2 Related Work

For the purpose of secrecy, memory bounds have been exploited in a similar model in the cryptosystem proposed by Cachin and Maurer [CM97]. They describe a privatekey cryptosystem and a protocol for key agreement by public discussion based on the assumption that an adversary’s memory capacity is bounded. The security margin for their key agreement protocol is O(n) memory needed for Alice and Bob versus no more than n^{2} memory for an adversary. Space bounds have also been studied with respect to interactive proof systems. Kilian [Kil88b] constructed a proof system for any language in PSPACE, which is zero knowledge with respect to a logarithmic space-bounded verifier. Kilian’s technique can be extended to any known verifier with polynomial space bounds. In this protocol, the memory bound and interaction are interleaved in a crucial way. De Santis et al. [DPY92] introduced one message proof systems with known space verifiers, showing that no interaction is needed to exploit space bounds for zero knowledge proofs. An improved construction was given by Aumann and Feige [AF94] of a one message proof system where the ratio between the maximum space tolerated and the minimum space needed by the verifier can be arbitrarily large. We note that our construction also uses interaction in a crucial way, but the memory bound only has to be imposed for one message at the beginning, during the broadcast of the random bits. Furthermore, the receiver in our protocol is allowed to access the complete broadcast and to compute any function of it before interaction starts. This is not the case for the commitment protocols by De Santis et al. and Aumann and Feige.

In addition, and in contrast to the proof systems with memory-bounded verifiers mentioned, the data intended to overflow a receiver’s memory consists of purely random bits in our protocol. Therefore, an independent random source with very high capacity can also be used for providing the random bits.

1.3 Organization of the Paper

The dense encoding of k-subsets into binary strings is described in Section 3, where we also provide our analysis of interactive hashing. Section 4 contains the protocol construction; the security proof is given in Section 5. We start with defining terminology, assembling some tools, and introducing the notation.

2 Preliminaries

A random variable X induces a probability distribution P_{X} over a set X. Random variables are denoted by capital letters. If not stated otherwise, the alphabet of a random variable is denoted by the corresponding script letter.

The (Shannon) entropy of a random variable X with probability distribution P_{X} and alphabet X is defined as

H(X) = − ∑_{x∈X} P_{X}(x) lg P_{X}(x).

Let h(p) = −p lg p − (1 − p) lg(1 − p) stand for the binary entropy function. The conditional entropy of X conditioned on a random variable Y is

H(X|Y) = ∑_{y∈Y} P_{Y} (y)H(X|Y = y)

where H(X|Y = y) denotes the entropy of the conditional probability distribution P_{X|Y =y}. The min-entropy of a random variable X is defined as

H_{∞}(X) = − lg max_{x∈X} P_{X}(x).

The variational distance between two probability distributions P_{X} and P_{Y} over the same alphabet X is

∥P_{X} − P_{Y} ∥_{v} = max_{X_{0}⊆X} | ∑_{x∈X_{0}} P_{X}(x) − P_{Y} (x)|

= \frac{1}{2} ∑_{x∈X} |P_{X}(x) − P_{Y} (x)|.

We say that a random variable X is ϵ-close to Y whenever ∥P_{X} − P_{Y} ∥_{v} ≤ ϵ.

For a sequence x_{1}, …, x_{n} and some set S ⊆ {1, …, n}, we abbreviate the projection of x_{1}, …, x_{n} onto indices in S by x^{S}. Similarly, x^{[n]} denotes the sequence x_{1}, …, x_{n} with the convention that x^{[0]} is the empty word. Also, x^{[n\i]} denotes the sequence x_{1}, …, x_{i−1}, x_{i+1}, …, x_{n}. We write ⊕ for addition in GF (2) and ⊙ for the inner product of two vectors over GF (2).

Lemma 1. Let X be a random variable with alphabet X, let V be an arbitrary random variable with alphabet V, and let r > 0. Then with probability at least 1 − 2^{−r}, V takes on a value v for which

H_{∞}(X|V = v) ≥ H_{∞}(X) − lg |V| − r.

Proof. Let p_{0} = 2^{−r}/|V|. Thus, ∑_{v:P_{V} (v)<p_{0}} P_{V} (v) < 2^{−r}.

It follows for all v with P_{V} (v) ≥ p_{0}

H_{∞}(X|V = v) = − lg max_{x∈X} P_{X|V =v}(x)
= − lg max_{x∈X} \frac{P_{X}(x)P_{V |X=x}(v)}{P_{V} (v)}
≥ − lg max_{x∈X} \frac{P_{X}(x)}{p_{0}}
= H_{∞}(X) − r − lg |V|

which proves the lemma.

A class G of functions X → Y is 2-universal if, for all distinct x_{1}, x_{2} ∈ X, there are at most |G|/|Y| functions g in G such that g(x_{1}) = g(x_{2}).

A class G of functions X → Y is strongly 2-universal if, for all distinct x_{1}, x_{2} ∈ X and all (not necessarily distinct) y_{1}, y_{2} ∈ Y, exactly |G|/|Y|^{2} functions from G take x_{1} to y_{1} and x_{2} to y_{2}.

A strongly 2-universal class of hash functions can be used to generate a sequence of pairwise independent random variables in the following way: Select G ∈ G uniformly at random and apply it to any fixed sequence x_{1}, …, x_{l} of distinct values in X. Let Y_{j} = G(x_{j}) for j = 1, …, l.

Privacy amplification [BBR86, BBR88] is a method to eliminate partial information about a random variable and extract a shorter, almost uniformly distributed value. The following theorem [ILL89, BBCM95] is formulated using min-entropy, but it can be generalized to Rényi entropy of any order α > 1 [Cac97b].

Theorem 2 ([BBCM95]). Let X be a random variable over the alphabet X, let G be the random variable corresponding to the random choice (with uniform distribution) from a 2-universal class G of hash functions X → Y, and let Y = G(X). Then

H(Y |G) ≥ lg |Y| − \frac{2^{lg |Y|−H_{∞}(X)}}{ln 2} .  (1)

The following is a result by Zuckerman [Zuc96] about the min-entropy of a randomly chosen subset X^{S} from a sequence X_{1}, …, X_{n}. Intuitively, one would like to show that since S is chosen randomly from {1, …, n}, the uncertainty about X^{S} is roughly \frac{|S|}{n} times the uncertainty about X_{1}, …, X_{n}. The exact statement is somewhat more involved.

Theorem 3 ([Zuc96]). Let X^{[n]} be an random variable with alphabet {0, 1}^{n} and min-entropy at least δn, let S = {S_{1}, …, S_{l}} be chosen pairwise independently as described above, let ρ = cδ lg δ^{−1} for some positive constant c and let ϵ = 3/\sqrt{ρl}. Then, for every value s = \{s_{1}, …, s_{l}\} there exists a random variable W_{s} with alphabet {0, 1}^{l} and min-entropy

H_{∞}(W_{s}) ≥ ρl

such that with probability at least 1 − ϵ (over the choice of S), X^{S} is ϵ-close to W_{S}.

3 Tools

3.1 Encoding k-Element Subsets

Let S = {1, 2, …, n}. A set Q is a k-element subset of S if Q ⊆ S and |Q| = k. We now give an efficient encoding of the k-element subsets as binary strings, that is, a mapping σ from the set of all k-element subsets given by a list of k integers from {1, …, n} into binary strings of length ⌈lg \binom{n}{k}⌉. Such a scheme may be found in [Cov73]. The encoding as described associates an integer in \{0, …, \binom{n}{k}−1\} with the k-element subset. The corresponding string is simply the binary representation of that integer.

Without lost of generality let Q = {e_{1}, e_{2}, …, e_{k}} be a k-element subset of S such that e_{i} ∈ S and e_{i} > e_{i−1} for i = 1, 2, …, k. For convenience, we use e_{0} = 0. The e_{1}, …, e_{k} are the positions of 1’s in the binary string of weight k starting from the left. The k-subsets of S correspond naturally to the binary strings of length n and weight k.

The integer associated with a binary string q of weight k is the number of strings that precede q in the list of all such strings according to the inverse lexicographical order (e.g. 11100, 11010, 11001, 10110, …). Let us count the number of strings preceding some particular string s given by e_{1}, …, e_{k}. The leftmost 1 of s is preceded by e_{1} − 1 zeros. Thus, for every position j, 1 ≤ j ≤ e_{1} − 1, there are \binom{n−j}{k−1} strings of weight k with their first one in position j, each prior to s. Continuing this way of reasoning, the i-th 1 of s is preceded by 0’s in the positions e_{i−1} + 1 to e_{i} − 1. For every position j, e_{i−1} + 1 ≤ j ≤ e_{i} − 1, there are \binom{n−j}{k−i} strings of weight k identical to s up to position e_{i−1} with their i-th one in position j, each prior to s in the list. Summing this up over all i = 1, …, k, we obtain the index σ(Q) corresponding to s and e_{1}, …, e_{k}. Thus, the encoding σ is given by

σ_{n,k}(Q) = ∑_{i=1}^{k} ∑_{j=e_{i−1}+1}^{e_{i}−1} \binom{n − j}{k − i}.

The decoding is done by the following procedure that takes as input an integer m and outputs the corresponding set Q, represented by e_{1}, …, e_{k}. It is easy to see that σ and σ^{−1} are computable in time polynomial in n. This procedure is implemented in linear space using a standard dynamic programming algorithm [BB88].

Algorithm 1 Calculate Q = σ_{n,k}^{−1}(m)

for i = 1 to k do

e_{i} ← biggest l such that ∑_{j=e_{i−1}+1}^{l−1} \binom{n − j}{k − i} ≤ m

m ← m − ∑_{j=e_{i−1}+1}^{e_{i}−1} \binom{n − j}{k − i}

end for

3.2 Interactive Hashing

Interactive hashing [NOVY98] is a protocol between a challenger Alice (with no input) and a responder Bob with input s ∈ {0, 1}^{m} and provides a way to isolate two strings. One of the strings is Bob’s input s and the other one is chosen randomly; Alice does not learn which one is s. Define the 2-universal class of hash functions from {0, 1}^{m} to {0, 1} as

G = {g(x) = a ⊙ x | a ∈ {0, 1}^{m}}.

The protocol operates in m − 1 rounds. Round j, for j = 1, …, m − 1, consists of the following steps:

1. Alice chooses a function g_{j} ∈ G with uniform distribution. Let a_{j} ∈ {0, 1}^{m} be the description of g_{j}. If a_{j} is linearly dependent on a_{1}, …, a_{j−1}, then Alice repeats this step until it is independent, else she announces g_{j} to Bob.

2. Bob computes b_{j} = g_{j}(s) = a_{j} ⊙ s and sends b_{j} to Alice.

At the end, Alice knows m − 1 linear equations satisfied by s. Since the a_{j}’s are linearly independent, the system has exactly two m-bit strings s_{0}, s_{1} as solutions that can be found by standard linear algebra. In our application of interactive hashing, Bob can cheat if he can answer Alice’s queries in such a way that both s_{0}, s_{1} are elements of a fixed set S.

This specific way of hashing will be the limiting factor of our construction in terms of the memory required by the participants. In order to check dependencies among the a_{j}’s, Alice must store them all and thus memory size in Θ(m^{2}) is necessary. Moreover, the matrix is also necessary to calculate s_{0}, s_{1} by both parties.

If a noninteractive hash function were used, Bob could produce a collision if |S| ≈ 2^{m/2}. In contrast, Bob can only cheat in interactive hashing if the size of S is close to 2^{m}. This is shown in the remainder of this section.

Lemma 4. Let S ⊆ {0, 1}^{m} with #S = 2^{νm} for 0 < ν < 1 and let c be a positive integer such that c ≤ νm/3. Let G be the 2-universal class of hash functions defined above, mapping {0, 1}^{m} to {0, 1}. Let G be a random variable with uniform distribution over G. Then for any b ∈ {0, 1}, G takes on a value g such that

\frac{#\{s ∈ S|g(s) = b\}}{#S} < \frac{1}{2} + 2^{−c}

with probability at least 1 − 2^{−c}.

Proof. Consider the indicator random variables for s ∈ S

U_{s} = \begin{cases}1 & if G(s) = 1 \\ 0 & otherwise \end{cases}

and the sum U = ∑_{s∈S} U_{s} = #{s ∈ S|G(s) = 1}. Similarly, let Z = |S| − U = #{s ∈ S|G(s) = 0}. Let

W = max U, Z and let V = \{ \begin{matrix}U & with prob. 1/2 \\ Z & with prob. 1/2 \end{matrix} .

Our goal is to show that G takes on a value g such that

\frac{W}{#S} < \frac{1}{2} + 2^{−c}

with probability at least 1 − 2^{−c}.

But notice that |W − \frac{#S}{2} | = |U − \frac{#S}{2} | = |Z − \frac{#S}{2} | = |V − \frac{#S}{2} | and thus for all σ P[|W − \frac{#S}{2} | ≥ σ] = P[|V − \frac{#S}{2} | ≥ σ].

Therefore, it is sufficient to show that

|V − \frac{#S}{2} | ≥ 2^{−c}

with probability at most 2^{−c}.

For this purpose, first note that E(V) = \frac{E(U)}{2} + \frac{E(Z)}{2} = \frac{E(U+Z)}{2} = \frac{#S}{2} . It follows from the Chebychev Inequality that

P[|V − \frac{#S}{2} | ≥ σ] = P[|V − E[V]| ≥ σ] ≤ \frac{Var[V]}{σ^{2}}

for σ > 0. Thus we must find Var[V].

By definition

Var[V] = E(V^{2}) − E(V)^{2}
= E(V^{2}) − (\frac{#S}{2} )^{2}
= \frac{E(U^{2})}{2} + \frac{E(Z^{2})}{2} − (\frac{#S}{2} )^{2}
= \frac{E((U + Z)^{2}) − 2UZ}{2} − (\frac{#S}{2} )^{2}
= \frac{#S^{2})}{2} − (\frac{#S}{2} )^{2} − E(UZ)
= (\frac{#S^{2}}{4} ) − E(UZ)

.

Define the indicator random variable

K_{s_{1},s_{2}} = \begin{cases}1 & if G(s_{1}) ≠ G(s_{2}) \\ 0 & otherwise \end{cases}

and the sum K  =  ∑_{s_{1},s_{2}∈S^{2}} K_{s_{1},s_{2}}  =

#{s_{1}, s_{2} ∈ S^{2}|G(s_{1}) ≠ G(s_{2})}. Notice that E(K) = 2E(UZ) as for every such pair (s_{1}, s_{2}) we have U choices for s_{1} and Z choices for s_{2} if G(s_{1}) = 1 ≠ G(s_{2}) = 0 and similarly if G(s_{1}) = 0 ≠ G(s_{2}) = 1. However, notice that

E(K) = ∑_{g∈G} P[g] ∑_{s_{1},s_{2}∈S^{2}}(K_{s_{1},s_{2}}|G = g)
= ∑_{s_{1},s_{2}∈S^{2}} ∑_{g∈G} P[g](K_{s_{1},s_{2}}|G = g)
= ∑_{s_{1},s_{2}∈S^{2}} E(K_{s_{1},s_{2}})

. and that E(K_{s_{1},s_{2}} \{ \begin{matrix}= 0 & if s_{1} = s_{2} \\ ≥ 1/2 & if s_{1} ≠ s_{2} \end{matrix} G is chosen

from a 2-universal class of hash functions. Thus E(UZ) = E(K)/2 ≥ (1/2)(1/2)#{s_{1}, s_{2} ∈ S^{2}|s_{1} ≠ s_{2}} = \frac{#S^{2}−#S}{4} .

We therefore obtain Var[V] = (\frac{#S^{2}}{4} ) − E(UZ) ≤ (\frac{#S^{2}}{4} ) − \frac{#S^{2}−#S}{4} = \frac{#S}{4} .

Substituting σ = \sqrt{2^{c}#S/4} we get

P[|Y − \frac{#S}{2} | ≥ 2^{\frac{(c+νm−2)}{2}} ] ≤ 2^{−c}.

But then, the reduction factor satisfies

\frac{#\{s ∈ S|G(s) = b\}}{#S} ≤ \frac{1}{2} + 2^{\frac{c+νm−2}{2} −νm}
< \frac{1}{2} + 2^{−c}

except with probability 2^{−c} and the lemma follows.

The lemma shows that each round of interactive hashing reduces the size of S by a factor of almost 2, as long as S is large (compared to 2^{c}). To keep track of the overall reduction, however, we need also the following standard lemma.

Lemma 5. Let S ⊆ {0, 1}^{m} with |S| = 2^{νm} for 0 < ν < 1 and let c, d ≤ m be positive integers such that 2νm < d−c. Let G be a 2-universal class of hash functions mapping {0, 1}^{m} to {0, 1}^{d}. Let G be a random variable with uniform distribution over G. The probability that G takes on a value g such that there are distinct s_{1}, s_{2} ∈ S with g(s_{1}) = g(s_{2}) is at most 2^{−c}.

Proof. Define the function a : G → ℕ to give the number of collisions in S for a particular g, that is,

a(g) = |{(s_{1}, s_{2}) ∈ S^{2} : g(s_{1}) = g(s_{2}), s_{1} < s_{2}}|

and let A = a(G). Let

c(s_{1}, s_{2}) = \begin{cases}|\{g ∈ G : g(s_{1}) = g(s_{2})\}| & if s_{1} < s_{2} \\ 0 & otherwise. \end{cases}

Since G is 2-universal, we have c(s_{1}, s_{2}) ≤ \frac{|G|}{2^{d}} for all s_{1}, s_{2}. Now it is easy to see that

∑_{g∈G} a(g) = ∑_{(s_{1},s_{2})∈S^{2}} c(s_{1}, s_{2}) ≤ \frac{1}{2}|S|^{2} \frac{|G|}{2^{d}}

and therefore E[A] ≤ \frac{|S|^{2}}{2^{d+1}} = 2^{2νm−d−1}. By the Markov Inequality, we get

P[A ≥ 1] ≤ P[A ≥ 2^{c+2νm−d−1}] ≤ 2^{−c}

since 2νm < d − c.

Lemma 6. Suppose Alice and Bob engage in interactive hashing of an m-bit string held by Bob to m − 1 bits as described above and let r ≥ lg m. Let S ⊆ {0, 1}^{m} be any subset of the inputs with cardinality 2^{νm}. If ν < 1 − \frac{8r+4}{m}, then the probability that Bob can answer Alice’s queries such that two distinct elements s_{1}, s_{2} of S are consistent with his answers is at most 2^{−r}.

Proof. Let S_{0} = S and, for j = 1, …, m − 1, define

S_{j} = {s ∈ S_{j−1}|g_{j}(s) = b_{j}}.

As long as S_{j} is large enough, the size of S_{j+1} can be bounded using Lemma 4. Afterwards, we apply Lemma 5 once for the remaining rounds. Let c = 2r and let j_{t} = ⌊νm−3c+1⌋ be the integer that will mark the transition. It follows from Lemma 4 by induction on j, for 1 ≤ j < j_{t}−1 that

|S_{j}| ≤ |S|(\frac{1}{2} + 2^{−c})^{j}

except with probability at most j2^{−c}. In consequence, |S_{j_{t}}| ≤ 2^{νm−j_{t}}(1 + 2^{−c+1})^{j_{t}} and we have

lg |S_{j_{t}}| ≤ (νm − j_{t}) + j_{t} lg(1 + 2^{−c+1}) < 3c + 1 (2)

from the definition of j_{t} and the fact that j_{t} lg(1 + 2^{−c+1} < m2^{−c} < 1. In order to apply Lemma 5 for step j_{t} (rounds j_{t} through m − 1 collectively) using S_{j_{t}}, we need to establish

2 lg |S_{j_{t}}| ≤ (m − 1 − j_{t}) − c.  (3)

From (2) and since ν < 1 − \frac{4c+4}{m} implies that 4c < m − νm − 4, we get

2 lg |S_{j_{t}}| < 6c + 2 < 2c + m − νm − 2  (4)

Thus, since νm − 3c < j_{t} we have 2c + m − νm − 2 < m − 1 − j_{t} − c and (3) holds. The overall failure probability is at most (j_{t} + 1)2^{−c} < m2^{−c} ≤ 2^{−r} and the lemma follows.

4 The Protocol

Suppose a large amount of random data (N uniformly distributed random bits) is sent from Alice to Bob over a high-capacity channel. Alternatively, the random data can be produced and broadcast by a random source R that both Alice and Bob trust to output random bits. The only assumption needed to prove the security of the protocol is that N must exceed Bob’s storage capacity. If both participants are honest, they need much less memory than can be tolerated against malicious Bob. Thus, even if Alice produces the random bits, she saves only a small part of them.

In \binom{2}{1}-OT, which our construction implements, Alice has two input bits b_{0}, b_{1} and Bob chooses c and obtains b_{c}, but Alice does not learn c. The protocol operates in the following steps. During the initial random broadcast, Alice and Bob both store a random subset of the N bits such that their parts overlap in ℓk positions. Then they engage in a way to form two sets among the bits stored by Alice, a “good” set and a “bad” set, of ℓk bits each. This is done using the interactive hashing protocol of Section 3.2 such that Alice does not learn which set is good. Bob knows all bits in the good set, but not all of the bad set. Then Bob asks Alice to encode b_{0} and b_{1} using the two sets such that b_{c} is encoded with the good set and b_{c⊕1} with the bad set. Bob can recover b_{c} since he knows the bits from the good set, but cannot b_{c⊕1} because some bits from the bad set are missing.

Included in the protocol is an additional distilliation step: the bits stored by Alice are first divided into blocks of ℓ bits each and then each block is hashed to one bit. The two sets are then formed on the level of bits and consist of k bits each.

Alice and Bob agree on the following parameters (rounding is implicit).

1. α, β such that 0 < β < α < \frac{1}{2}: these parameters determine the memory requirements.

2. n: number of bits that Alice and Bob store from the random broadcast.

3. N = n^{2−α−β}: number of bits in the random broadcast.

4. m = n^{1−α}: number of blocks (and bits T_{1}, …, T_{m}).

5. ℓ = n^{α}: length of one block.

6. k = n^{β}: bound on the estimated number of blocks (and bits from T_{1}, …, T_{m}) that overlap.

7. G = {g|g : {0, 1}^{ℓ} → {0, 1}}: 2-universal class of hash functions for compressing blocks to bits.

The security margin in terms of memory will be that the maximum memory for a malicious Bob that can be tolerated is γN for γ < 1, versus the Nk/ℓ memory size needed for the honest players. A typical choice of the parameters could be a small β and α = \frac{1}{2} − β, yielding N = n^{1.5−2β} and Nk/ℓ = n^{1+2β}.

The Protocol for \binom{2}{1}-OT(b_{0}, b_{1})(c):

1. Alice (or an independent source) broadcasts N random bits r_{1}, …, r_{N}, abbreviated by r^{[N]}. Alice stores the n bits at positions A = {a_{1}, …, a_{n}}, where A consists of n uniformly random values from {1, …, N}. Bob stores the bits at positions B = {b_{1}, …, b_{n}}, where B is chosen by Bob with uniform distribution. The substrings of r^{[N]} are denoted by r^{A} and r^{B}, respectively.

2. Alice sends A to Bob. With the bits in r^{A} Bob forms m blocks x_{1}, …, x_{m} of length ℓ = n^{α} bits each such that the overlap A ∩ B spans at least k = n^{β} complete blocks. If this is not possible (because the overlap is less than ℓk bits) he aborts. Let S ⊆ {1, …, m} denote a set of k blocks that Bob knows completely. Formally, Bob constructs a permutation of A, denoted by π : {1, …, n} → {1, …, n}, and the sets C_{j} = {a_{π((j−1)ℓ+1)}, …, a_{π(jℓ)}} for j = 1, …, m such that for all j ∈ S C_{j} ⊂ A ∩ B. He announces π to Alice.

3. Alice groups her stored n bits r^{A} into blocks r^{C_{1}}, …, r^{C_{m}} as announced by Bob. Then Alice chooses m hash functions g_{1}, …, g_{m} independently and uniformly at random from G and announces them to Bob. She applies them to the blocks r^{C_{1}}, …, r^{C_{m}} and obtains the bits t_{1}, …, t_{m}, where t_{j} = g_{j}(r^{C_{j}}).

4. Bob computes y_{j} = g_{j}(r^{C_{j}}) for j ∈ S. He also computes the binary encoding s = σ(S) of S of length M = ⌈lg \binom{m}{k}⌉ = ⌈lg \binom{n^{1−α}}{n^{β}}⌉ ≤ n^{1−α}h(n^{α+β−1}).

5. Alice and Bob engage in the interactive hashing of s into a bit string w of length m − 1, as described in Section 3.2. Alice computes the two sets U_{0}, U_{1} ⊂ {1, …, m} such that σ(U_{0}) and σ(U_{1}) both hash to w and U_{0} < U_{1} according to some fixed order. If this is not possible because one of the strings that hashes to w is not a valid encoding of a subset, Bob aborts.

6. Bob also knows U_{0}, U_{1}. He chooses the bit c′ such that U_{c′⊕c} = S and sends c′ to Alice. Alice computes z_{0} = b_{0} ⊕ (⨁_{j∈U_{c′}} t_{j}) and z_{1} = b_{1} ⊕ (⨁_{j∈U_{c′⊕1}} t_{j}).

7. Bob recovers b_{c} = z_{c} ⊕ (⨁_{j∈S} y_{j}).

The descriptions of A and B have size in O(n lg n), which could be reduced by choosing the sets with pairwise independent distribution. The expected number of common indices is kℓ = n^{2}/N = n^{α+β}. By storing a few extra bits, Alice and Bob can ensure that the overlap is kℓ bits except with small probability. As mentioned earlier, this version of the protocol requires both party to memorize a θ(n^{2}) size matrix in order to calculate the values of U_{0}, U_{1} in step 6.

It is easy to see that the protocol is complete and succeeds with probability at least \frac{1}{2} if Alice and Bob are honest since more than half the string of length M are valid subset encoding (aborts can occur in step 2 if the overlap is not large enough and in step 5 if hashing yields an invalid subset encoding.) In order to prevent Bob from cheating by inducing aborts too often (e.g. while waiting until the overlap of A and B is much larger than expected), Alice will only cooperate for at most n′ repetitions of the protocol for some n′ ≪ n. If Bob aborts more often, she concludes that he must be cheating, since the abort probability of an honest Bob is at most O(2^{−n′}).

5 Security Proof

We note first that if the protocol does not abort, then Alice obtains no information about which one of U_{0}, U_{1} corresponds to Bob’s set S and therefore the protocol is secure for Bob. If the protocol aborts, then no information depending on Alice’s inputs b_{0}, b_{1} or Bob’s input c has been disclosed yet and therefore, we need not worry further about aborts.

Thus, the security of the protocol is established by the next theorem.

Theorem 7. Suppose malicious Bob’s memory is not more than γN bits for some γ < 1. Then, for sufficiently large n, the probability that Bob learns information about both bits b_{0}, b_{1} can be made inverse polynomially small.

During the random broadcast, a malicious Bob can compute any probabilistic function from {0, 1}^{N} to V with output V such that lg |V| ≤ γN. Let the random variable R^{[N]} correspond to r^{[N]} and let X^{[m]} = X_{1}, …, X_{m} correspond to the distribution of the blocks x_{1}, …, x_{m} in Alice’s subset conditioned on Bob’s knowledge V = v, or

P_{X^{[m]}}(x_{i}) = P_{R^{A}|V =v}(r^{C_{i}}).

for i = 1, …, m. (X^{[m]} is a random variable over n-bit strings.)

The proof consists of three major steps. First, a lower bound on Bob’s min-entropy about R^{A}|V = v, the bits stored by Alice, is obtained (Lemma 8). Second, the hashing of blocks to bits is examined in Lemma 9 and it is shown that Bob can know at most about (1 − ρ)N of the bits. The third step (proof of Theorem 7) uses the analysis of interactive hashing from Lemma 6 to show that a malicious Bob cannot learn information about both bits.

Lemma 8. Let ϵ_{1} > 0, let δ = (1 − γ − \frac{1}{N} lg \frac{1}{ϵ_{1}} ), let ρ = cδ/ lg δ^{−1} for some c > 0, and let ϵ_{2} = 3/\sqrt{ρn}. Then, except with probability ϵ_{1} + ϵ_{2}, the distribution of X^{[m]} is ϵ_{2}-close to a random variable with min-entropy at least ρn.

Proof. Because R^{[N]} is assumed to be uniformly distributed, it has min-entropy H_{∞}(R^{[N]}) = N. Lemma 1 roughly shows that the min-entropy of R^{[N]} given V is at least (1 − γ)N with probability 1 − ϵ_{1}. More precisely, for any ϵ_{1} > 0, the particular value v that V takes on satisfies H_{∞}(R^{[N]}|V = v) ≥ (1 − γ)N − lg \frac{1}{ϵ_{1}} , except with probability at most ϵ_{1}.

We now invoke Theorem 3 and obtain that the distribution of X^{[m]} = X_{1}, …, X_{m} (a random variable on n-bit strings) is ϵ_{2}-close to a distribution with min-entropy ρn except with probability ϵ_{2}.

The next lemma shows that Bob lacks knowledge of at least about ρm bits from T_{1}, …, T_{m} with high probability. It involves a spoiling knowledge argument that is often used in connection with privacy amplification [BBCM95, Cac97a]: Suppose side information is made available to Bob by an oracle. The side information is tailored for Bob’s distribution and serves the purpose of increasing his entropy and to obtain better results. Note that the oracle giving spoiling knowledge is used only as a proof technique and not for carrying out privacy amplification.

Lemma 9. Let ϵ_{4}, ϵ_{5} > 0 and suppose X^{[m]} has minentropy at least ρn. There is a subset Q ⊆ {1, …, m} of cardinality q = (ρn − m(lg n + 2) − lg \frac{1}{ϵ_{4}} − 2m lg \frac{1}{ϵ_{5}} )/ℓ such that Bob’s distribution of T^{Q}, conditioned on particular values v, f_{1}, …, f_{m}, and x_{j} for j ∉ Q, is ϵ_{6}-close to the uniform distribution over bit strings of length q, where ϵ_{6} = m2^{−2ℓ} + ϵ_{4} + ϵ_{5} + \sqrt{2qϵ_{5}}.

Proof. The main part of the proof is to construct spoiling knowledge such that min-entropies of the blocks X_{1}, …, X_{m} add up and then applying privacy amplification for hashing the blocks to bits T_{1}, …, T_{m}.

Suppose side information u_{1}, …, u_{m} with u_{j} ∈ {0, …, 2jℓ} for j = 1, …, m is made available to Bob. Let the random variable U^{[m]} correspond to the distribution of u^{[m]}. It is defined for j = 1, …, m as U_{j} = λ_{j}(X^{[j]}), where

λ_{j}(x^{[j]}) = \begin{cases}2jℓ & if P_{X^{[j]}}(x^{[j]}) ≤ 2^{−2jℓ} \\ ⌊− lg P_{X^{[j]}}(x^{[j]})⌋ & otherwise. \end{cases}

(Side information U_{j} of this type has also been called logpartition spoiling knowledge [Cac97a]). U_{j} partitions the values of X^{[j]} into sets of approximately equal probability under P_{X^{[j]}|U_{j}=u_{j}}. For all u_{j} except u_{j} = 2jℓ, the values of the probability distributions P_{X^{[j]}|U_{j}=u_{j}} differ by less than a factor of two and we have

\frac{1}{2} max_{x^{[j]}} P_{X^{[j]}|U_{j}=u_{j}}(x^{[j]}) ≤ min_{x^{[j]}} P_{X^{[j]}|U_{j}=u_{j}}(x^{[j]}). (5)

The probability that there exists a j s.t. U_{j} = 2jℓ is no more than ϵ_{3} = m2^{−2ℓ} and we assume U_{j} ≠ 2jℓ for the rest of the proof.

The size of U^{[m]} (in bits) is less than m lg(2mℓ) = m lg(2n). Therefore, U^{[m]} satisfies

H_{∞}(X^{[m]}|U^{[m]} = u^{[m]})

≥ H_{∞}(X^{[m]}) − m(lg n + 1) − lg \frac{1}{ϵ_{4}} (6)

except with probability ϵ_{4} by Lemma 1. We assume that (6) holds in the remainder of the proof.

Claim. For all x^{[1]}, …, x^{[m−1]}, we have

∑_{j=1}^{m} H_{∞}(X_{j}|U^{[m]} = u^{[m]}, X^{[j−1]} = x^{[j−1]})

≥ ρn − m(lg n + 2) − lg \frac{1}{ϵ_{4}} . (7)

Note that this implies Bob’s min-entropies of at least

q = (ρn − m(lg n + 2) − lg \frac{1}{ϵ_{4}} − 2m lg \frac{1}{ϵ_{5}} )/ℓ (8)

blocks from X_{1}, …, X_{m} exceed 2 lg \frac{1}{ϵ_{5}} , conditioned on any particular values of the other blocks. (There are m blocks for which the sum of the min-entropies is bounded from below in (7), and the min-entropy of each block is at most ℓ.)

Proof of the claim: First note that

H_{∞}(X^{[m]}|U^{[m]} = u^{[m]}) − m

≥ ρn − m(lg n + 2) − lg \frac{1}{ϵ_{4}}

from (6) and therefore, proving the claim reduces to

∑_{j=1}^{m} H_{∞}(X_{j}|U^{[m]} = u^{[m]}, X^{[j−1]} = x^{[j−1]})

≥ H_{∞}(X^{[m]}|U^{[m]} = u^{[m]}) − m. (9)

We do this by induction on j = 0, …, m − 1 using the following induction hypothesis: For all x^{[m−j+1]}, …, x^{[m]}, it holds

H_{∞}(X^{[m−j]}|U^{[m]} = u^{[m]})

+ ∑_{j′=m−j+1}^{m} H_{∞}(X_{j′}|X^{[m−j′+1]} = x^{[m−j′+1]}, U^{[m]} = u^{[m]})

≥ H_{∞}(X^{[m]}|U^{[m]} = u^{[m]}) − j. (10)

Clearly (10) holds for j = 0. Suppose that (10) holds for some j ≤ 0. Let P_{j} = P_{X_{m−j}|X^{[m−j−1]}=x^{[m−j−1]},U^{[m]}=u^{[m]}}(x_{m−j}). Then we have for all x^{[m−j−1]} and all x_{m−j} that

max_{x̃^{[m−j]}} P_{X^{[m−j]}|U^{[m]}=u^{[m]}}(x̃^{[m−j]})

≥ P_{X^{[m−j−1]}|U^{[m]}=u^{[m]}}(x^{[m−j−1]}) · P_{j}
≥ min_{x̃^{[m−j−1]}} P_{X^{[m−j−1]}|U^{[m]}=u^{[m]}}(x̃^{[m−j−1]}) · P_{j}
≥ \frac{1}{2} max_{x̃^{[m−j−1]}} P_{X^{[m−j−1]}|U^{[m]}=u^{[m]}}(x̃^{[m−j−1]}) · P_{j}

by the property (5) of the side information U^{[m]}. Since this holds for all x_{m−j} (and thus for the max), we obtain

H_{∞}(X_{m−j}|X^{[m−j−1]} = x^{[m−j−1]}, U^{[m]} = u^{[m]})

+ H_{∞}(X^{[m−j−1]}|U^{[m]} = u^{[m]})

≥ H_{∞}(X^{[m−j]}|U^{[m]} = u^{[m]}) − 1 (11)

for all x^{[m−j−1]}. It follows now from (10) and from (11) that for all x^{[m−j]}, …, x^{[m]},

H_{∞}(X^{[m−j−1]}|U^{[m]} = u^{[m]})

+ ∑_{j′=m−j}^{m} H_{∞}(X_{j′}|X^{[m−j′]} = x^{[m−j′]}, U^{[m]} = u^{[m]})

≥ H_{∞}(X^{[m]}|U^{[m]} = u^{[m]}) − j − 1 (12)

This establishes the induction step and thus 9 and the claim (7).

For second step in the proof of Lemma 9, we apply Theorem 2 (privacy amplification). Let Q ⊆ {1, …, m} be a set of q indices j such that, for all j ∈ Q,

H_{∞}(X_{j}|U^{[m]} = u^{[m]}, X^{[j−1]} = x^{[j−1]}) ≥ 2 lg \frac{1}{ϵ_{5}} .

Such a set exists according to the claim (7). Using Theorem 2, we obtain for j ∈ Q,

H(T_{j}|F_{j} = f_{j}, U^{[m]} = u^{[m]}, X^{[j−1]} = x^{[j−1]}) ≥ 1 − 2ϵ_{5}^{2}/ ln 2,

where F_{j} for j = 1, …, m denotes the random variable corresponding to the choice of the hash function f_{j} with uniform distribution. Let q_{max} be the largest element of Q and let Q̄ = {1, …, q_{max}} \ Q. By summing up the entropies, we have

H(T^{Q}|F^{Q}, U^{[m]} = u^{[m]}, XQ̄ = xQ̄) ≥ q − 2qϵ_{5}^{2}/ ln 2.

Thus, except with probability ϵ_{5}, F^{Q} takes on a value f^{Q} such that

H(T^{Q}|F^{Q} = f^{Q}, U^{[m]} = u^{[m]}, XQ̄ = xQ̄) ≥ q − 2qϵ_{5}/ln 2.

In this case, it follows from the standard inequality lg |X | − H(X) ≥ \frac{1}{ln 2}∥P_{X} − P_{U}∥_{v}^{2} that

∥P_{T^{Q}|F^{Q}=f^{Q},U^{[m]}=u^{[m]},XQ̄=xQ̄} − P_{U}∥_{v} ≤ \sqrt{2qϵ_{5}},

where P_{U} denotes the uniform distribution over q bits. Accounting for all the cases excluded above, it follows

∥P_{T^{Q}} − P_{U}∥_{v} ≤ ϵ_{3} + ϵ_{4} + ϵ_{5} + \sqrt{2qϵ_{5}}.

ϵ_{3} and ϵ_{4} are used in for spoiling knowledge and ϵ_{5} is needed to remove the expectation from the conditional entropy of T^{Q}.

Proof of Theorem 7. Let μ > 0 be a small constant. Then, for all sufficiently large n, we have q ≥ (ρ − μ)m from Lemma 9.

For the analysis of interactive hashing in step 5, we will use Lemma 6. There are \binom{m}{k} = \binom{n^{1−α}}{n^{β}} subsets and inputs for Bob in total, thus M = lg \binom{m}{k} for Lemma 6. Suppose Bob lacks knowledge about at least q bits from T_{1}, …, T_{m}, i.e., he has complete knowledge about not more than \binom{m−q}{k} ≤ \binom{ζn^{1−α}}{n^{β}} of the subsets, corresponding to the set S of Lemma 6, where ζ = 1 − ρ + μ.

In order to apply the lemma setting r = lg M we need to make sure that ν = \frac{1}{M} lg \binom{m−q}{k} < 1 − \frac{8 lg M+4}{M}, which is equivalent to

lg \binom{n^{1−α}}{n^{β}} − lg \binom{ζn^{1−α}}{n^{β}} − 8 lg lg \binom{n^{1−α}}{n^{β}} > 4.

This can be satisfied by choosing n sufficiently large, since ζ is a constant smaller than 1. It follows that Bob has

probability not more than ϵ_{7} = 1/M = (lg \binom{n^{1−α}}{n^{β}})^{−1} ≈

n^{α−1}/h(n^{α+β−1}) of knowing all bits of both sets and therefore of recovering both bits b_{0}, b_{1}.

The overall failure probability is at most ϵ_{1} + 2ϵ_{2} + ϵ_{6} + ϵ_{7}, where ϵ_{1}, ϵ_{2} are from Lemma 8 and ϵ_{6}, ϵ_{7} are from Lemma 9. More precisely, ϵ_{1}, ϵ_{4}, ϵ_{5} are parameters fixed above and

1. ϵ_{2} = 3/\sqrt{ρn},

2. ϵ_{3} = n^{(1−α)}2^{−2n^{α}},

3. ϵ_{6} = n^{(1−α)}2^{−2n^{α}} + ϵ_{4} + ϵ_{5} + \sqrt{2qϵ_{5}},

4. ϵ_{7} = lg \binom{n^{1−α}}{n^{β}}^{−1} ≈ n^{α−1}/h(n^{α+β−1}).

6 Discussion

The error probability of the security proof guaranteed by Theorem 7 is inverse polynomial in n, which may not be enough for some applications (even if n is generally large). However, by repeating the protocol l times the error can be reduced to an exponentially small quantity. Alice selects 2l random bits b_{1}^{0}, …, b_{l}^{0} and b_{1}^{1}, …, b_{l}^{1} such that b_{0} = ⨁_{j=1}^{l} b_{j}^{0} and b_{1} = ⨁_{j=1}^{l} b_{j}^{1} and they perform \binom{2}{1}-OT(b_{j}^{0}, b_{j}^{1})(c) for j = 1, …, l. It is easy to see that now the probability that a malicious Bob obtains any information about b_{c⊕1} is O(2^{−l}).

In our construction, both parties need θ(n^{2−2α}) memory size if they are honest and the security can be guaranteed if Bob has not more than γn^{2−α−β} memory size for some small β > 0 and γ < 1, typically. It is an interesting open problem whether this difference can be enlarged. For example, in the cryptosystem by Cachin and Maurer based on memory bounds [CM97], the security margin is about O(n) vs. n^{2} for the public key agreement protocol. We believe that this should also be achievable for oblivious transfer.

Acknowledgment

We are greatful to Adam Smith and Alain Tapp for helpful discussions.

References

[AD97] Miklós Ajtai and Cynthia Dwork, A publickey cryptosystem with worst-case/average-case equivalence, Proc. 29th Annual ACM Symposium on Theory of Computing (STOC), 1997, pp. 284–293.

[AF94] Yonatan Aumann and Uriel Feige, One message proof systems with known space verifiers, Advances in Cryptology: CRYPTO ’93 (Douglas R. Stinson, ed.), Lecture Notes in Computer Science, vol. 773, Springer, 1994, pp. 85–99.

[BB88] G. Brassard and P. Bratley, Algorithmics: Theory and practice, Prentice-Hall, Englewoods Cliffs, NJ, 1988.

[BBCM95] Charles H. Bennett, Gilles Brassard, Claude Crépeau, and Ueli M. Maurer, Generalized privacy amplification, IEEE Transactions on Information Theory 41 (1995), no. 6, 1915– 1923.

[BBCS92] C.H. Bennett, G. Brassard, C. Crépeau, and M.-H. Skubiszewska, Practical quantum oblivious transfer protocols, Advances in Cryptology: Proceedings of Crypto ’91, Lecture Notes in Computer Science, vol. 576, Springer-Verlag, 1992, pp. 351–366.

[BBR86] Charles H. Bennett, Gilles Brassard, and Jean-Marc Robert, How to reduce your enemy’s information, Advances in Cryptology: CRYPTO ’85 (Hugh C. Williams, ed.), Lecture Notes in Computer Science, vol. 218, Springer, 1986, pp. 468–476.

[BBR88] C. H. Bennett, G. Brassard, and J.–M. Robert, Privacy amplification by public discussion, SIAM J. Computing 17 (1988), no. 2, 210– 229.

[BM90] Mihir Bellare and Silvio Micali, Noninteractive oblivious transfer and applications, Advances in Cryptology: CRYPTO ’89 (Gilles Brassard, ed.), Lecture Notes in Computer Science, vol. 435, Springer, 1990, pp. 547–557.

[Cac97a] Christian Cachin, Entropy measures and unconditional security in cryptography, ETH Series in Information Security and Cryptography, vol. 1, Hartung-Gorre Verlag, Konstanz, Germany, 1997, ISBN 3-89649-185-7 (Reprint of Ph.D. dissertation No. 12187, ETH Zürich).

[Cac97b] Christian Cachin, Smooth entropy and Rényi entropy, Advances in Cryptology: EURO-CRYPT ’97 (Walter Fumy, ed.), Lecture Notes in Computer Science, vol. 1233, Springer-Verlag, 1997, pp. 193–208.

[CK88] Claude Crépeau and Joe Kilian, Achieving oblivious transfer using weakened security assumptions, Proc. 29th IEEE Symposium on Foundations of Computer Science (FOCS), 1988.

[CM97] Christian Cachin and Ueli Maurer, Unconditional security against memory-bounded adversaries, Advances in Cryptology: CRYPTO ’97 (Burt Kaliski, ed.), Lecture Notes in Computer Science, vol. 1294, Springer-Verlag, 1997, pp. 292–306.

[Cov73] T.M. Cover, Enumerative source encoding, IEEE Transactions on Information Theory 19 (1973), no. 1, 73–77.

[Cré84] C. Crépeau, Quantum oblivious transfer, Journal of Modern Optics 41 (1984), no. 12, 2445– 2454.

[Cré88] Claude Crépeau, Equivalence between two flavours of oblivious transfer, Advances in Cryptology: CRYPTO ’87 (Carl Pomerance, ed.), Lecture Notes in Computer Science, vol. 293, Springer, 1988, pp. 350–354.

[Cré97] Claude Crépeau, Efficient cryptographic protocols based on noisy channels, Advances in Cryptology: EUROCRYPT ’97 (Walter Fumy, ed.), Lecture Notes in Computer Science, vol. 1233, Springer, 1997, pp. 306–317.

[CS91] C. Crépeau and M. Sántha, On the reversibility of oblivious transfer, Advances in Cryptology: Proceedings of Eurocrypt ’91, Lecture Notes in Computer Science, vol. 547, Springer-Verlag, 1991, pp. 106–113.

[CS95] C. Crépeau and L. Salvail, Quantum oblivious mutual identification, Advances in Cryptology: Proceedings of Eurocrypt ’95, Lecture Notes in Computer Science, vol. 921, Springer-Verlag, 1995, pp. 133–146.

[CvdGT95] C. Crépeau, J. van de Graaf, and A. Tapp., Committed oblivious transfer and private multi-party computations, Advances in Cryptology: Proceedings of Crypto ’95, Lecture Notes in Computer Science, vol. 963, Springer-Verlag, 1995, pp. 110–123.

[DPY92] Alfredo De Santis, Giuseppe Persiano, and Moti Yung, One-message statistical zeroknowledge proofs with space-bounded verifier, Proc. 19th ICALP, Lecture Notes in Computer Science, vol. 623, Springer, 1992, pp. 28–40.

[EGL83] Shimon Even, Oded Goldreich, and Abraham Lempel, A randomized protocol for signing contracts, Proc. CRYPTO ’82 (R. L. Rivest, A. Sherman, and D. Chaum, eds.), Plenum Press, 1983, pp. 205–210.

[GMW87] Oded Goldreich, Silvio Micali, and Avi Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, Proc. 19th Annual ACM Symposium on Theory of Computing (STOC), 1987, pp. 218–229.

[GV88] Oded Goldreich and Ronen Vainish, How to solve any protocol problem – an efficiency improvement, Advances in Cryptology: CRYPTO ’87 (Carl Pomerance, ed.), Lecture Notes in Computer Science, vol. 293, Springer, 1988, pp. 73–86.

[ILL89] Russell Impagliazzo, Leonid A. Levin, and Michael Luby, Pseudo-random generation from one-way functions, Proc. 21st Annual ACM Symposium on Theory of Computing (STOC), 1989, pp. 12–24.

[IR89] Russell Impagliazzo and Steven Rudich, Limits on the provable consequences of one-way permutations, Proc. 21st Annual ACM Symposium on Theory of Computing (STOC), 1989, pp. 186–208.

[Kil88a] Joe Kilian, Founding cryptography on oblivious transfer, Proc. 20th Annual ACM Symposium on Theory of Computing (STOC), 1988, pp. 20–31.

[Kil88b] Joe Kilian, Zero-knowledge with log-space verifiers, Proc. 29th IEEE Symposium on Foundations of Computer Science (FOCS), 1988, pp. 25–35.

[NOVY98] Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, and Moti Yung, Perfect zeroknowledge arguments for NP using any oneway function, Journal of Cryptology 11 (1998), no. 2, 87–108, Preliminary version presented at CRYPTO ’92.

[NS98] P. Nguyen and J. Stern, Cryptanalysis of the ajtai-dwork cryptosystem, Advances in Cryptology: Proceedings of Crypto ’98, Lecture Notes in Computer Science, Springer-Verlag, 1998.

[Rab81] Michael O. Rabin, How to exchange secrets by oblivious transfer, Tech. Report TR-81, Harvard, 1981.

[Sho94] Peter W. Shor, Algorithms for quantum computation: Discrete log and factoring, Proc. 35th IEEE Symposium on Foundations of Computer Science (FOCS), 1994, pp. 124–134.

[Wie70] Stephen Wiesner, Conjugate coding, Reprinted in SIGACT News, vol. 15, no. 1, 1983, original manuscript written ca. 1970.

[Yao86] Andrew C.-C. Yao, How to generate and exchange secrets, Proc. 27th IEEE Symposium on Foundations of Computer Science (FOCS), 1986, pp. 162–167.

[Zuc96] David Zuckerman, Simulating BPP using a general weak random source, Algorithmica 16 (1996), 367–391, Preliminary version presented at 32nd FOCS (1991).