Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Private information retrieval
Résumé
In cryptography, a private information retrieval (PIR) protocol is a protocol that allows a user to retrieve an item from a server in possession of a database without revealing which item is retrieved. PIR is a weaker version of 1-out-of-n oblivious transfer, where it is also required that the user should not get information about other database items.
One trivial, but very inefficient way to achieve PIR is for the server to send an entire copy of the database to the user. In fact, this is the only possible protocol (in the classical or the quantum setting) that gives the user information theoretic privacy for their query in a single-server setting. There are two ways to address this problem: make the server computationally bounded or assume that there are multiple non-cooperating servers, each having a copy of the database.
The problem was introduced in 1995 by Chor, Goldreich, Kushilevitz and Sudan in the information-theoretic setting and in 1997 by Kushilevitz and Ostrovsky in the computational setting. Since then, very efficient solutions have been discovered. Single database (computationally private) PIR can be achieved with constant (amortized) communication and k-database (information theoretic) PIR can be done with communication.
The first single-database computational PIR scheme to achieve communication complexity less than was created in 1997 by Kushilevitz and Ostrovsky and achieved communication complexity of for any , where is the number of bits in the database. The security of their scheme was based on the well-studied Quadratic residuosity problem. In 1999, Christian Cachin, Silvio Micali and Markus Stadler achieved poly-logarithmic communication complexity. The security of their system is based on the Phi-hiding assumption. In 2004, Helger Lipmaa achieved log-squared communication complexity , where is the length of the strings and is the security parameter. The security of his system reduces to the semantic security of a length-flexible additively homomorphic cryptosystem like the Damgård–Jurik cryptosystem.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Séances de cours associées (3)
Cryptographie Information-théorique: Problème de secret partiel
Explore le problème du secret partiel dans la cryptographie théorique de l'information, couvrant des sujets tels que la communication secrète, la sécurité informatique et les fuites d'informations.
Cryptographie RSA: Test de primalité et résidus quadratiques
Explore la cryptographie RSA, couvrant les tests de primalité, les résidus quadratiques et les applications cryptographiques.
Cryptographie théorique de l'information
Explore la cryptographie théorique de l'information, en se concentrant sur la communication secrète et la génération de clés.
Publications associées (23)
On Speed and Advantage : Results in Information Velocity and Monitoring Problems
Information theory has allowed us to determine the fundamental limit of various communication and algorithmic problems, e.g., the channel coding problem, the compression problem, and the hypothesis testing problem. In this work, we revisit the assumptions ...
EPFL2024EOS: Efficient Private Delegation of zkSNARK Provers
Alessandro Chiesa, Yinuo Zhang
Succinct zero knowledge proofs (i.e. zkSNARKs) are powerful cryptographic tools that enable a prover to convince a verifier that a given statement is true without revealing any additional information. Their attractive privacy properties have led to much ac ...
Berkeley2023Integrity and Metadata Protection in Data Retrieval
Secure retrieval of data requires integrity, confidentially, transparency, and metadata-privacy of the process. Existing protection mechanisms, however, provide only partially these properties: encryption schemes still expose cleartext metadata, protocols ...
EPFL2021Personnes associées (2)
Concepts associés (1)
Cryptographie
thumb|La machine de Lorenz utilisée par les nazis durant la Seconde Guerre mondiale pour chiffrer les communications militaires de haut niveau entre Berlin et les quartiers-généraux des différentes armées. La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de secrets ou clés. Elle se distingue de la stéganographie qui fait passer inaperçu un message dans un autre message alors que la cryptographie rend un message supposément inintelligible à autre que qui de droit.