arXiv:2507.19295

On the Security of a Code-Based PIR Scheme

Svenja Lage, Hannes Bartz

Published Jul 25, 2025• 0 citations

Abstract

Private Information Retrieval (PIR) schemes allow clients to retrieve files from a database without disclosing the requested file's identity to the server. In the pursuit of post-quantum security, most recent PIR schemes rely on hard lattice problems. In contrast, the so called CB-cPIR scheme stands out as a pioneering effort to base PIR schemes on hard problems in coding theory, thereby contributing significantly to the diversification of security foundations. However, our research reveals a critical vulnerability in CB-cPIR, substantially diminishing its security levels. Moreover, a comparative analysis with state-of-the-art PIR schemes shows that CB-cPIR's advantages are reduced, making it less competitive in terms of the communication cost. Nevertheless, our findings highlight the importance of continued research into code-based PIR schemes, as they have the potential to provide a valuable alternative to lattice-based approaches.

DOI: 10.48550/arxiv.2507.19295

Related papers

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

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

Quantum Private Information Retrieval from Coded Storage Systems

Matteo Allaix

In the era of extensive data growth, robust and efficient mechanisms are needed to store and manage vast amounts of digital information, such as Data Storage Systems (DSSs). Concurrently, privacy concerns have arisen, leading to the development of techniques like Private Information Retrieval (PIR) to enable data access while preserving privacy. A PIR protocol allows users to retrieve information from a database without revealing the specifics of their query or the data they are accessing. With the advent of quantum computing, researchers have explored the potential of using quantum systems to enhance privacy in information retrieval. In a Quantum Private Information Retrieval (QPIR) protocol, a user can retrieve information from a database by downloading quantum systems from multiple servers, while ensuring that the servers remain oblivious to the specific information being accessed. This scenario offers a unique advantage by leveraging the inherent properties of quantum systems to provide enhanced privacy guarantees and improved communication rates compared to classical PIR protocols. In this thesis we consider the QPIR setting where the queries and the coded storage systems are classical, while the responses from the servers are quantum. This problem was treated by Song et al. for replicated storage and different collusion patterns. This thesis aims to develop QPIR protocols for coded storage by combining known classical PIR protocols with quantum communication algorithms, achieving enhanced privacy and communication costs. We consider different storage codes and robustness assumptions, and we prove that the achieved communication cost is always lower than the classical counterparts.

arXiv:2312.07570Dec 10, 20230 citations

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

A survey on communication complexity in quantum private information retrieval: Efficiency challenges and advances

Laxmi Kumari, Tarun Kumar Mahato

Quantum Private Information Retrieval (QPIR) is a new and growing area that uses quantum computing to improve privacy and efficiency in database searches. Traditional Private Information Retrieval (PIR) methods often require a large amount of communication between the user and the server, making them slow and costly. QPIR aims to solve this problem by using quantum techniques like superposition and entanglement to reduce communication while keeping the user’s query private. In this paper, we review different QPIR methods and analyze how they handle communication complexity. We compare multi-server and single-server models, discussing their strengths and weaknesses. We also explore the practical challenges of QPIR, such as the need for quantum resources, errors in quantum systems, and security against quantum attackers. Additionally, we highlight important research gaps, including how to make single-server QPIR more efficient, balancing security with speed, and understanding how future quantum computers might impact QPIR security. By addressing these challenges, this survey aims to support further research and help develop practical, efficient, and secure QPIR systems for real-world use.

International journal of applied researchJan 1, 20250 citations

Secure quantum private information retrieval using phase-encoded queries

Łukasz Olejnik

We propose a quantum solution to the classical private information retrieval (PIR) problem, which allows one to query a database in a private manner. The protocol offers privacy thresholds and allows the user to obtain information from a database in a way that offers the potential adversary, in this model the database owner, no possibility of deterministically establishing the query contents. This protocol may also be viewed as a solution to the symmetrically private information retrieval problem in that it can offer database security (inability for a querying user to steal its contents). Compared to classical solutions, the protocol offers substantial improvement in terms of communication complexity. In comparison with the recent quantum private queries [Phys. Rev. Lett. 100, 230502 (2008)] protocol, it is more efficient in terms of communication complexity and the number of rounds, while offering a clear privacy parameter. We discuss the security of the protocol and analyze its strengths and conclude that using this technique makes it challenging to obtain the unconditional (in the information-theoretic sense) privacy degree; nevertheless, in addition to being simple, the protocol still offers a privacy level. The oracle used in the protocol is inspired both by the classical computational PIR solutions as well as the Deutsch-Jozsa oracle.

Physical Review AAug 8, 2011125 citations