Private Information Retrieval

Private Information Retrieval

Private Information Retrieval (PIR) ist ein kryptographisches Primitiv, das ein Protokoll modelliert, bei dem eine Anfrage an eine Datenbank gestellt und auch beantwortet werden kann, ohne dass die Datenbank Aussagen über den angeforderten Eintrag machen kann.

Modellierung

Oft wird das Schema wie folgt modelliert:

  • Eine Datenbank A, bestehend aus n \times n Bits, z.B. A \in \mathbb{B}^{n \times n}
  • Ein Client, der eine Anfrage eines Datenbankeintrags - also eines Spalten- und Zeilenindex - ausführt, und ein Bit zurückerhält

Nach der Ausführung müssen folgende Bedingungen gelten:

  • Der Client hat das richtige Bit b \in A erhalten, sodass gilt b = (Aij)
  • Der Datenbank blieb der erfragte Zeilen- und Spaltenindex unbekannt.

Umsetzung

Die einfachste Möglichkeit dieses Szenario umzusetzen, bestünde wohl darin, dass die Datenbank – unabhängig von der Anfrage – immer den gesamten Inhalt der Matrix als Antwort sendet. Da dies aber bei großen Datenmengen schlecht bis gar nicht realisierbar ist, gibt es andere Ansätze, wie z.B. eine Lösung mittels des quadratischen-Reste-Problems. Siehe dazu auch [1].

Literatur

  • E, Kushilevitz und R. Ostrovsky: Replication Is Not Needed: Single Database, Computationally-Private Information Retrieval. In: FOCS '97. 1997 (online).
  • B. Chor, O Goldreich, E. Kushilevitz und M Sudan: Private Information Retrieval. Vol. 45. In: Journal of the ACM. No. 6, November 1998, S. 965–982 (pdf).
  • Felipe Saint-Jean: A Java Implementation of a Single-Database Computationally Symmetric Private Information Retrieval (cSPIR) protocol. In: Yale University Technical Report YALEU/DCS/TR-1333. YALEU/DCS/TR-1333, Juli 2005 (pdf).

Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Private information retrieval — In cryptography, a private information retrieval (PIR) protocol allows a user to retrieve an item from a server in possession of a database without revealing which item she is retrieving. PIR is a weaker version of 1 out of n oblivious transfer,… …   Wikipedia

  • Information theoretic security — A cryptosystem is information theoretically secure if its security derives purely from information theory. That is, it is secure even when the adversary has unbounded computing power. An example of an information theoretically secure cryptosystem …   Wikipedia

  • Information Awareness Office — seal The Information Awareness Office (IAO) was established by the Defense Advanced Research Projects Agency (DARPA) in January 2002 to bring together several DARPA projects focused on applying surveillance and information technology to track and …   Wikipedia

  • information processing — Acquisition, recording, organization, retrieval, display, and dissemination of information. Today the term usually refers to computer based operations. Information processing consists of locating and capturing information, using software to… …   Universalium

  • information system — Introduction       an integrated set of components for collecting, storing, processing, and communicating information (information science). Business firms, other organizations, and individuals in contemporary society rely on information systems… …   Universalium

  • information theory — the mathematical theory concerned with the content, transmission, storage, and retrieval of information, usually in the form of messages or data, and esp. by means of computers. [1945 50] * * * ▪ mathematics Introduction       a mathematical… …   Universalium

  • International Institute of Information Technology, Hyderabad — Infobox University name = Indian Institute of Information Technology, Hyderabad established = 1998 type = Deemed University, Education and Research, Private city = Hyderabad state = Andhra Pradesh country = India motto = director = Dr. Rajeev… …   Wikipedia

  • Virtual private network — A virtual private network (VPN) is a computer network in which some of the links between nodes are carried by open connections or virtual circuits in some larger network (e.g., the Internet) instead of by physical wires. The link layer protocols… …   Wikipedia

  • Geographic information system — GIS redirects here. For other uses, see GIS (disambiguation). A geographic information system, geographical information science, or geospatial information studies is a system designed to capture, store, manipulate, analyze, manage, and present… …   Wikipedia

  • Regional Health Information Organization — Regional Health Information Organizations (RHIOs) are key to the US National Health Information Network (NHIN). [ [http://www.whitehouse.gov/infocus/technology/economic policy200404/chap3.html White House website] Transforming Health Care: The… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”