A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol.

Carlos Aguilar Melchor, Philippe Gaborit

Published Jan 1, 2007• 98 citations

Abstract

A PIR scheme is a scheme that allows an user to get an element of a database without giving any information about what part of the database he is interested in. In this paper we present a lattice-based PIR scheme, using an NTRU-like approach, in which the computational cost is a few thousand bit-operations per bit in the database. This improves the protocol computational performance by two orders of magnitude when compared to existing approaches. Our scheme has worse communication performance than other existing protocols, but we show that practical usability of PIR schemes is not as dependent on communication performance as the literature suggests, and that a trade-off between communication and computation leads to much more versatile schemes.

Related papers

An Efficient Scheme for Private Information Retrieval

Weiwei Jing

The Private Information Retrieval protocol(PIR) is an important secure multi-party computation protocol.In PIR,a user can perform a query from a database without revealing his private information;meanwhile the privacy of the database will be protected,too.This paper proposes a new scheme in which we apply cryptographic technology on the auxiliary random servers protocol to solve the problem of PIR.This scheme is efficient in computational complexity and doesn't increase the cost of communication.It is very practical and can retrieve a block of bits.Detailed analysis of security,computational complexity and communicational complexity to the scheme is also given in this paper.

Journal of Chinese Computer SystemsJan 1, 20070 citations

An Efficient Private Information Retrieval Scheme Based on Coefficient Extraction and Lattice-Based Cryptography

Feng Li, Dianhua Tang, Yunfan Huang +5 more

Private Information Retrieval (PIR) enables users to retrieve records from a database without revealing their query targets to the server. While lattice-based PIR schemes have gained attention due to their quantum-resistance properties, existing approaches face significant challenges in terms of computational overhead and noise management. Current state-of-the-art solutions like SealPIR, OnionPIR, and SPIRAL suffer from three main limitations: (1) complex ciphertext query expansion requiring iterative homomorphic operations,(2) substantial computational costs due to polynomial operations in ring-LWEbased schemes, and (3) inefficient conversion between heterogeneous ciphertexts that increases both communication overhead and noise growth. In this paper, we propose a novel coefficient extraction-based PIR scheme that addresses these challenges through two key innovations: A direct coefficient extraction technique that eliminates iterative homomorphic operations; a unified algebraic structure across RLWE, LWE, and LWEGSW schemes for seamless ciphertext conversion. Compared to existing approaches, our scheme achieves: significant reduction in computational overhead through optimized homomorphic operations compared to baseline approaches; substantially decreased communication costs via efficient ciphertext structure design- Better controlled noise growth allowing smaller parameter settings; maintained security based on standard RLWE/LWE hardness assumptions. These improvements make our scheme particularly suitable for practical PIR applications requiring both efficiency and strong security guarantees.

International Conference on Cloud Computing and Big Data Analytics (ICCCBDA)Apr 24, 20250 citations

Cryptanalysis of a Lattice-Based PIR Scheme for Arbitrary Database Sizes

Svenja Lage

Private information retrieval schemes enable users to privately retrieve files from a server without disclosing the content of their queries. In 2008, Aguilar Melchor and Gaborit proposed a PIR scheme that balances communication and server-side computational cost. For particularly small databases, Liu and Bi identified a vulnerability in the scheme using lattice-based methods. Nevertheless, the rapid increase in computational cost associated with the attack limited its practical applicability, leaving the scheme's overall security largely intact. In this paper, we present a novel two-stage attack that extends the work of Liu and Bi to databases of arbitrary sizes. To this end, we employ an innovative binary-search-like preprocessing technique, which enables a significant reduction in the number of lattice problems that need to be considered. We demonstrate how to compromise the scheme in a matter of minutes using an ordinary laptop. Our findings are substantiated through both rigorous analytical proofs and comprehensive numerical experiments.

arXiv:2505.05934IACR Communications in CryptologyMay 4, 20260 citations

Cryptanalysis of a Fast Private Information Retrieval Protocol

Jiayang Liu, Jingguo Bi

A private information retrieval (abbreviated as PIR) protocol deals with the schemes that allow a user to retrieve privately an element of a non-replicated database. The security of PIR protocol is that the user wants to retrieve information in a database without the database knowing which information has being retrieved. This is widely applied in medical files, video or songs databases or even stock exchanges share prices.

May 24, 20164 citations

One-way functions are essential for single-server private information retrieval

Amos Beimel, Yuval Ishai, Eyal Kushilevitz Z +1 more

Private Information Retrieval (PIR) protocols allow a user to read information from a database without revealing to the server storing the database which information he has read.Kushilevitz and Ostrovsky [23] construct, based on the quadratic residuosity assumption, a single-server PIR protc-co1 with small communication complexity.Cachin, Micali, and Stadler [6] present a single-server PIR protocol with a smaller communication complexity, based an the (new) *hiding assumption.A major question, addressed in the present work, is what assumption is the minimal assumption necessary for the construction of single-server private information retrieval protocols with small communication complexity.We prove that if there is a (O-error) PIR protocol in which the server sends less than n bits then one-way functions exist (where n is the number of bits in the database).That is, even saving one bit compared to the naive protocol, in which the entire database is sent, already requires one-way functions.The same result holds (but requires more work) even if we allow the retrieval to fail with probability of at most 1/(8n).Moreover, similar tcomputer science

ACM Symposium on Theory of Computing (STOC)May 1, 199961 citations

Storage Constrained Information Theoretic Symmetric Private Information Retrieval

Deepak Kumar

Private information retrieval (PIR) is an important protocol in cryptographic community to ensure privacy of the user when retrieving information from untrusted databases. In a variation to this problem, symmetric private information retrieval (SPIR) is a protocol which ensures the privacy of user as well as databases. A major drawback for the majority of existing works on information theoretic PIR and SPIR is that they focus on scenarios where all databases store the entire data set (i.e. replicated databases). The goal of this thesis is to present PIR and SPIR schemes for storage constrained databases. For both PIR and SPIR, we present a systematic approach to utilize storage constrained databases. The technical contribution involves two main parts: (a) a careful storage scheme to split and store messages across databases; and (b) construction of information theoretic PIR and SPIR schemes from such databases. We also compare our results to the fully replicated scenario, as well as compare the differences between the communication overhead of PIR and SPIR schemes.

Jun 25, 20180 citations