# «Abstract. Let A and B denote cryptographic primitives. A (k, m)robust A-to-B combiner is a construction, which takes m implementations of primitive A ...»

On Robust Combiners for Private Information

Retrieval and Other Primitives

Remo Meier and Bartosz Przydatek

Department of Computer Science, ETH Zurich

8092 Zurich, Switzerland

remmeier@student.ethz.ch, przydatek@inf.ethz.ch

Abstract. Let A and B denote cryptographic primitives. A (k, m)robust A-to-B combiner is a construction, which takes m implementations of primitive A as input, and yields an implementation of primitive

B, which is guaranteed to be secure as long as at least k input implementations are secure. The main motivation for such constructions is the tolerance against wrong assumptions on which the security of implementations is based. For example, a (1,2)-robust A-to-B combiner yields a secure implementation of B even if an assumption underlying one of the input implementations of A turns out to be wrong.

In this work we study robust combiners for private information retrieval (PIR), oblivious transfer (OT), and bit commitment (BC). We propose a (1,2)-robust PIR-to-PIR combiner, and describe various optimizations based on properties of existing PIR protocols. The existence of simple PIR-to-PIR combiners is somewhat surprising, since OT, a very closely related primitive, seems diﬃcult to combine (Harnik et al., Eurocrypt’05).

Furthermore, we present (1,2)-robust PIR-to-OT and PIR-to-BC combiners. To the best of our knowledge these are the ﬁrst constructions of A-to-B combiners with A = B. Such combiners, in addition to being interesting in their own right, oﬀer insights into relationships between cryptographic primitives. In particular, our PIR-to-OT combiner together with the impossibility result for OT-combiners of Harnik et al. rule out certain types of reductions of PIR to OT. Finally, we suggest a more ﬁne-grained approach to construction of robust combiners, which may lead to more eﬃcient and practical combiners in many scenarios.

Keywords: robust combiners, cryptographic primitives, reductions, private information retrieval, oblivious transfer, bit commitment.

1 Introduction Consider a scenario when two implementations, I1 and I2, of some cryptographic primitive are given, e.g., two encryption schemes or two bit commitment schemes.

Each implementation is based on some unproven computational assumption, α1 resp. α2, like for example the hardness of factoring integer numbers or the hardness of computing discrete logarithms. We would like to have an implementation I of the primitive, which is as secure as possible given the current state of knowledge. As it is often not clear, which of the assumptions α1, α2 is more likely to be C. Dwork (Ed.): CRYPTO 2006, LNCS 4117, pp. 555–569, 2006.

c International Association for Cryptologic Research 2006 556 R. Meier and B. Przydatek correct, picking just one of the implementations does not work — we might bet on the wrong assumption! A better option would be to have an implementation which is guaranteed to be secure as long as at least one of the assumptions α1, α2 is correct. That is, given I1 and I2 we would like to construct an eﬃcient implementation I, which is secure whenever at least one of the input implementations is. Such a construction is an example of a (1,2)-robust combiner, as it combines the input implementations and is robust against situations when one of the two inputs is insecure.

In general, robust combiners can use more than just two input schemes, and aim at providing a secure implementation of the output primitive assuming that suﬃciently many of the candidates are secure. Moreover, the input candidates do not have to be necessarily implementing the same primitive, and the goal of a combiner may be a construction of a primitive diﬀerent from the primitives given at the input. That is, a robust combiner can be viewed as a robust reduction of the output primitive to the input primitive(s).

The concept of robust combiners is actually not so new in cryptography and many techniques are known for combining cryptographic primitives to improve security guarantees, e.g., cascading of block ciphers. However, a more formal and rigorous study of combiners was initiated quite recently [Her05, HKN+ 05].

Robust combiners for some primitives, like one-way functions or pseudorandom generators, are rather simple, while for others, e.g., for oblivious transfer (OT), the construction of combiners seems considerably harder. In particular, in a recent work Harnik et al. [HKN+ 05] show that there exists no “transparent black-box” (1,2)-robust OT-combiner. Given the impossibility result for OTcombiners, it is interesting to investigate the existence of combiners for singledatabase private information retrieval (PIR), a primitive closely related, yet not known to be equivalent, to oblivious transfer. Potential PIR-combiners could lead to better understanding of relations between PIR, OT, and other primitives.

Moreover, constructions of robust PIR-combiners are also of considerable practical interest, stemming from the fact that some of the most eﬃcient PIR protocols are based on relatively new computational assumptions (e.g., [CMS99, KY01]), which are less studied and thus potentially more likely to be proved wrong.

Contributions. In this work we consider robust combiners for private information retrieval, bit commitment, and oblivious transfer. In particular, we present (1,2)robust PIR-combiner, i.e. combiner which given two implementations of PIR yield an implementation of PIR which is secure if at least one of the input implementations is secure. We also describe various techniques and optimizations based on properties of existing PIR protocols, which yield PIR-combiners with better eﬃciency and applicability.

Furthermore, we construct A-to-B combiners, i.e. “cross-primitive” combiners, which given multiple implementations of a primitive A yield an implementation of some other primitive B, which is provably secure assuming that suﬃciently many of the input implementations of A are secure. Speciﬁcally, we construct (1,2)-robust PIR-to-BC and PIR-to-OT combiners. To the best of our knowledge these are the ﬁrst combiners of this type. While interesting in their own right, On Robust Combiners for PIR and Other Primitives 557 such combiners also oﬀer insights into relationships and reductions between cryptographic primitives. In particular, our PIR-to-OT combiner together with the impossibility result of [HKN+ 05] rule out certain types of reductions of PIR to OT (cf. Corollary 4 in Section 4).

Finally, we suggest a more ﬁne-grained approach to design of robust combiners. That is, we argue that in order to obtain combiners as eﬃcient as possible, the constructions may take into account that some properties of the input candidates are proved to hold unconditionally, and hence cannot go wrong even if some computational assumption turns out to be wrong. Therefore, keeping in mind the original motivation for combiners, i.e. protection against wrong assumptions, a more ﬁne-grained approach to design of robust combiners exploits the unconditionally secure properties and focuses on the properties which hold only under given assumptions. This change of focus yields sometimes immediately trivial constructions of combiners (as observed by Harnik et al. [HKN+ 05] for OT and BC), yet in many cases the resulting problems are still interesting and challenging (see Sections 2.3 and 5 for more details).

Related Work. As mentioned above, a more rigorous study of robust combiners was initiated only recently, by Herzberg [Her05] and by Harnik et al. [HKN+ 05].

On the other hand, there are numerous implicit uses and constructions of combiners in the literature (e.g., [AB81, EG85, DK05, HL05]).

Private information retrieval was introduced by Chor et al. [CKGS98] and has been intensively studied since then. The original setting of PIR consisted of multiple non-communicating copies of the database and guaranteed informationtheoretic privacy for the user. Later, Kushilevitz and Ostrovsky [KO97] gave the ﬁrst solution to single-database PIR, in which the privacy of the user is based on a computational assumption. The ﬁrst PIR protocol with communication complexity polylogarithmic in the size of the database was proposed by Cachin et al. [CMS99], and in recent years more eﬃcient constructions have been proposed (e.g. [Cha04, Lip05]). For more information about PIR we refer to the survey by Gasarch [Gas04].

The relationships between PIR and other primitives have been studied intensively in the recent years. In particular, Beimel et al. [BIKM99] proved that any non-trivial single-database PIR implies one-way functions, and Di Crescenzo et al. [DMO00] showed that such a PIR implies oblivious transfer. Kushilevitz and Ostrovsky [KO00] demonstrated that one-way trapdoor permutations are suﬃcient for non-trivial single-database PIR. On the negative side, Fischlin [Fis02] showed that there is no black-box construction of one-round (i.e., two-message) PIR from one-to-one trapdoor functions.

Techniques similar to the ones employed in the proposed PIR-combiners were previously used by Di Crescenzo et al. [DIO01] in constructions of universal service-providers for PIR.

Organization. Section 2 contains notation, deﬁnitions of cryptographic primitives and of robust combiners, and some general remarks about combining PIR protocols. In Section 3 we describe proposed constructions of (1,2)-robust 558 R. Meier and B. Przydatek PIR-combiners. In Section 4 we turn to “cross-primitive” combiners and present PIR-to-BC and PIR-to-OT combiners. Finally, in Section 5 we discuss some general aspects of design of eﬃcient combiners and point out some open problems.

2 Preliminaries Notational Conventions. If x is a bit-string, |x| denotes its length, and we write x y to denote the concatenation of the bit-strings x, y. For an integer n we write [n] to denote the set {1,..., n}. The parties participating in the protocols and the adversary are assumed to be probabilistic polynomial time Turing machines, (PPTMs).

2.1 Primitives We review shortly the primitives relevant in this work. For more formal deﬁnitions we refer to the literature.

Private Information Retrieval. is a protocol between two parties, a server holding an n-bit database x = (x1... xn ), and a user holding an index i ∈ [n].

The protocol allows the user to retrieve bit xi without revealing i to the server, i.e. it protects user’s privacy. In this work we consider only single-database PIR.

Of interest are only non-trivial protocols, in which the total server-side communication (i.e. communication from the server to the user) is less than n bits.

Moreover, of special interest are 2-message protocols, in which only two messages are sent: a query from the user to the server and a response from the server to the user.

Oblivious Transfer. 1 is a protocol between a sender holding two bits x0 and x1, and a receiver holding a choice-bit c. The protocol allows the receiver to get bit xc so that the sender does not learn any information about receiver’s choice c, and the receiver does not learn any information about bit x1−c.

Bit Commitment. is a two-phase protocol between two parties Alice and Bob. In the commit phase Alice commits to bit b without revealing it, by sending to Bob an “encrypted” representation e of b. Later, in the decommit phase, Alice sends to Bob a decommitment string d, allowing Bob to “open” e and obtain b. In

**addition to correctness, a bit commitment scheme must satisfy two properties:**

hiding, i.e. Bob does not learn the bit b before the decommit phase, and binding, i.e. Alice cannot come up with decommitment strings d, d which lead to opening the commitment as diﬀerent bits. We consider also weak bit commitment, i.e.

BC with weak binding property: Alice might be able to cheat, but Bob catches her cheating with noticeable probability [BIKM99].

The version of oblivious transfer described here and used in this paper is more precisely denoted as 1-out-of-2 bit-OT [EGL85]. There are several other versions of OT, e.g., Rabin’s OT, 1-out-of-n bit-OT, or 1-out-of-n string-OT, but all are known to be equivalent [Rab81, Cr´87, CK88].

e On Robust Combiners for PIR and Other Primitives 559

2.2 Robust Combiners The following deﬁnition is a generalization of the deﬁnition of combiners given in [HKN+ 05].

Deﬁnition 1 ((k, m)-robust A-to-B combiner). Let A and B be cryptographic primitives. A (k, m)-robust A-to-B combiner is a PPTM which gets m candidate schemes implementing A as inputs and implements B while satisfying

**the following two properties:**

1. If at least k candidates securely implement A, then the combiner securely implements B.

2. The running time of the combiner is polynomial in the security parameter κ, in m, and in the lengths of the inputs to B.

An A-to-A combiner is called an A-combiner. For completeness we recall three deﬁnitions from [HKN+ 05], which will be useful in our constructions.

Deﬁnition 2 (Black-box combiner [HKN+ 05]). A (1, 2)-robust combiner

**is called a black-box combiner if the following two conditions hold:**

Black-Box Implementation: The combiner is an oracle PPTM given access to the candidates via oracle calls to their implementation function.

Black-Box Proof: For every candidate there exists an oracle PPTM RA (with access to A) such that if adversary A breaks the combiner, then RA breaks the candidate.

Deﬁnition 3 (Third-party black-box combiner [HKN+ 05]). A thirdparty black-box combiner is a black-box combiner where the input candidates behave like trusted third parties. The candidates give no transcript to the players but rather take their inputs and return outputs.

Deﬁnition 4 (Transparent black-box combiner [HKN+ 05]). A transparent black-box combiner is a black-box combiner for an interactive primitive where every call to a candidate’s next message function is followed by this message being sent to the other party.

Note that the notion of reduction of primitive B to primitive A, i.e. a construction of B from A, can be viewed as a (1,1)-robust A-to-B combiner. Therefore, the above deﬁnitions also include notions like a transparent black-box reduction or a third-party black-box reduction.