FREE ELECTRONIC LIBRARY - Online materials, documents

Pages:   || 2 | 3 |

«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 ...»

-- [ Page 1 ] --

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 difficult 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 first constructions of A-to-B combiners with A = B. Such combiners, in addition to being interesting in their own right, offer 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 fine-grained approach to construction of robust combiners, which may lead to more efficient 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 efficient 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 sufficiently 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 different 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 efficient 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 efficiency 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 sufficiently many of the input implementations of A are secure. Specifically, we construct (1,2)-robust PIR-to-BC and PIR-to-OT combiners. To the best of our knowledge these are the first combiners of this type. While interesting in their own right, On Robust Combiners for PIR and Other Primitives 557 such combiners also offer 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 fine-grained approach to design of robust combiners. That is, we argue that in order to obtain combiners as efficient 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 fine-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 first solution to single-database PIR, in which the privacy of the user is based on a computational assumption. The first PIR protocol with communication complexity polylogarithmic in the size of the database was proposed by Cachin et al. [CMS99], and in recent years more efficient 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 sufficient 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, definitions 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 efficient 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 definitions 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 different 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 definition is a generalization of the definition of combiners given in [HKN+ 05].

Definition 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 definitions from [HKN+ 05], which will be useful in our constructions.

Definition 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.

Definition 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.

Definition 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 definitions also include notions like a transparent black-box reduction or a third-party black-box reduction.

Pages:   || 2 | 3 |

Similar works:

«The BiblioFiles: Philip Pullman Premiere date: September 20, 2014 DR. DANA: The Cotsen Children's Library at Princeton University Library presents The BiblioFiles. [MUSIC PLAYING] DR. DANA: Hi, this is Dr. Dana. Today, my guest is esteemed author Philip Pullman. Pullman's writing career began with the publication of the hilarious Count Karlstein in 1982. That was followed by The Ruby in the Smoke, the first in a quartet of mystery and intrigue novels set in Victorian England. Pullman has...»

«The Carbon and PBO Rig for the „sailOvation“ Finite Element Analysis University of Applied Sciences Kiel Prof. Dr.-Ing. Guenter Grabe Guenter.Grabe@FH-Kiel.de 1. Introduction The “sailOvation” is a German innovation bearer for the cruising yacht of the future. She is a 30 ft long canting keel yacht and bound to plane on a close reach. The project is sponsored by the German yachting magazine “segeln-magazin” and involved companies to build her. The rig is a key term to enable the...»

«QUESTIONS AND ANSWERS Load Rating of Specialized Hauling Vehicles Office of Bridges and Structures Resource Center Federal Highway Administration March 2014 Office of Bridges and Structures Resource Center Federal Highway Administration March 2014 QUESTIONS AND ANSWERS Load Rating of Specialized Hauling Vehicles The purpose of this document is to provide answers to some of the common questions received from FHWA Division Offices and States prior to and after the release of FHWA’s Memorandum...»

«Chapter 23 Preaching in the New Church There is much confusion about preaching today. Some are advocating only one form of preaching; others seem to have abandoned preaching in the name of cultural relevance. Neither of these positions is helpful as you plant a new church. But the preaching of the Word is a mark of a true church whether that preaching is in a circle of ten in a house church or in front of thousands at a rented conference center. Preaching in a new church offers unique...»

«C0 UNCI L WEXFORD COUNTY Report of General Purposes Committee Meeting Held on Monday, 7th July, 1997 2.30 p.m. In the Council Chamber, County Hall, Wexford. ********* ATTENDANCE: In the Chair: Councillor L Allen, Chairman. Councillors Other Members J. A. Browne, T.D.; L. Carthy; H. Byrne, T. D. ; M. D' Arcy, T. D. ; S. Doyle; J. Gahan; L. O'Brien; P. Reck; R. Murphy; M. Sinnott. Messrs: S. Dooley, County Manager; F. A. Doyle, County Secretary; K. O'Brien, Assistant County Manager; J. N. Casey,...»


«BTO Research Report No. 328 Impacts of Grey Squirrels on Woodland Birds: An Important Predator of Eggs and Young? Authors C.M. Hewson & R.J. Fuller A report by the British Trust for Ornithology June 2003 © British Trust for Ornithology and Woodland Heritage British Trust for Ornithology, The Nunnery, Thetford, Norfolk, IP24 2PU Registered Charity No. 216652 British Trust for Ornithology Impacts of Grey Squirrels on Woodland Birds: An Important Predator of Eggs and Young? BTO Research Report...»

«Koinonia G R E E K O RT H O D OX CATHEDRAL +FR. PAUL COSTOPOULOS, VOLUME 32 ISSUE 2&3 FEBRUARY & MARCH DEAN Description of SPECIAL POINTS OF Sunday Of Orthodoxy INTEREST: For more than one hundred years LENTEN RETREAT By +Father Paul Costopoulosof Christ was troubled the Church February 24—25 By +Father Paul Costopoulos by the persecution of the IconoSUNDAY OF clasts of evil belief, beginning in ORTHODOXY the reign of Leo the Isaurian (717March 4 741) and ending in the reign of PARISH...»

«Pakistan Sugar Journal January-March 2010 Contents Vol. XXV, No.01 Editorial Board 2 Morphological responses of autumn planted M. Asghar Qureshi Chairman sugarcane to planting geometry and nutrient Dr. Shahid Afghan Member management on different soils under arid conditions Dr. Muhammad Zubair Member Abdul Gaffar Suggu, Ejaz Ahmed, Haji Himayatullah, Dr. Shahid Mahboob Rana Member M. Ayaz, Haji Khalil Ahmed, Muhammad Aslam Published 10 Integrated control strategies for sugarcane disease Under...»

«_ The Cornerstone Rolling Hills United Methodist Church 26438 Crenshaw Blvd. Rolling Hills Estates, CA 90274 February 3, 2011 Church Conference Approves Building Proposal After several years of listening and planning, the Building Committee presented their proposal for a new family and education facility. The architectural team from Bryant Palmer Soto, who drew up the plans, was on hand to help answer questions. The meeting was open to the entire church family and over 100 attended. The...»

«CAIN V. HORNE: SCHOOL CHOICE FOR WHOM? Shannon E. Trebbe INTRODUCTION In Cain v. Horne, the Arizona Supreme Court unanimously held that school-voucher programs providing state funding for the private education of disabled and foster children violated the Arizona Constitution. Finding that the programs contravened the plain language and purpose of the Aid Clause,2 the court did not address the constitutionality of the programs under the Religion Clause.3 Although the court struck down the...»

«The Ruling of the Dome Built upon the Grave of the Messenger of Allaah sallAllaahu alayhi wa sallam The Ruling of the Dome Built upon the Grave of the Messenger of Allaah sallAllaahu alayhi wa sallam The Ruling of the Dome Built upon the Grave of the Messenger of Allaah sallAllaahu alayhi wa sallam A Research Paper Prepared by Abu AbdurRahmaan Muqbil bin Hadi al-Waadi'ee Died 1422 A.H. Supervised by Shaykh Hamad al-Ansaari Died 1418 A.H. may Allaah have mercy on them And Debated by Shaykh...»

<<  HOME   |    CONTACTS
2017 www.thesis.dislib.info - Online materials, documents

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.