Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2505.05934 · IACR Communications in Cryptology

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

Svenja Lage

Published May 4, 2026• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.62056/an-4c3tw9

Related papers

On the Security of a Code-Based PIR Scheme

Svenja Lage, Hannes Bartz

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.

arXiv:2507.19295•Jul 25, 2025•3 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, 2025•0 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 Systems•Jan 1, 2007•0 citations

Efficient transformation capabilities of single database private block retrieval

Radhakrishna Bhat, N. R. Sunitha

Abstract Private information retrieval (PIR) is one of the promising techniques to preserve user privacy in the presence of trusted-but-curious servers. The information theoretically private query construction assures the highest user privacy over curious and unbounded computation servers. Therefore, the need for information-theoretic private retrieval was fulfilled by various schemes in a variety of PIR settings. But, there is a lack of efficient encryption switching scheme which supports efficient switching between information-theoretic to/from computationally bounded PIRs. We propose a combination of new bit connection methods called rail-shape and signal-shape and new quadratic residuosity assumption based family of trapdoor functions for generic single database private block retrieval (PBR). The main goal of this work is to show that the possibility of mapping from computationally bounded privacy to information theoretic privacy or vice-versa in a single database setting using newly constructed bit connection and trapdoor function combinations. Notably, the proposed schemes are single round, memoryless and plain database schemes (at their basic constructions).

International Journal of Information Technology•Jan 19, 2022•4 citations

A study of secure database access and general two-party computation

Tal Malkin, Shafi Goldwasser

In this thesis, we study two fundamental areas of secure computation over a network.First, we study general two-party secure computation, where two mutually distrustful parties are trying to compute an arbitrary function of their inputs, without revealing any extra information (even if one of them is malicious).We prove that, if any nontrivial function can be so computed, then so can every other function.That is, every non-trivial function is complete for two-party secure computation.Consequently, the complexity assumptions sufficient and/or necessary for securely computing f are the same for every non-trivial function f.Next, we study the concrete problem of secure database access, where the privacy of both the database and the user is to be protected from each other and from all other participating or eavesdropping parties.We are interested in practical and theoretical aspects of this problem, addressing issues of efficiency, security, and complexity.More specifically, we start from the model of private information retrieval (PIR), where users are trying to retrieve information from a database while keeping their queries private from the database owner.We then explore the following directions: * We study the necessary assumptions for single server PIR with low communication.We prove that oblivious transfer is necessary, implying that PIR is a complete primitive for secure computation, and that computational SPIR protocols (defined below) can be efficiently constructed from PIR protocols.* We introduce the model of SPIR, where the privacy of the data, as well as the user, is guaranteed.We show how to efficiently transform PIR protocols into SPIR protocols, for both the information-theoretic and computational settings. "We introduce the random server model for PIR, and show how to use it to achieve information theoretic solutions in which the database need not give away its data to be replicated, and with minimal on-line computation for the database.

•Jan 1, 2000•7 citations

Symmetrically Private Information Retrieval (Extended Abstract)

Sanjeev Kumar Mishra, Palash Sarkar

Abstract. In this paper we present a single-round, single-server symmetrically private information retrieval scheme, in which privacy of user follows from intractability of the quadratic residuacity problem and the privacy of the database follows from the XOR assumption for quadratic residues introduced in this paper. The communication complexity of the proposed scheme for retrieving one bit can be made O(n ɛ), for any ɛ>0, where n is the number of bits in the database. We extend the protocol to a block retrieval scheme which is specially efficient when the number of records in the database is equal to the size of each record.

International Conference on Cryptology in India•Jan 1, 2000•0 citations
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.
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.
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.
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.
Abstract Private information retrieval (PIR) is one of the promising techniques to preserve user privacy in the presence of trusted-but-curious servers. The information theoretically private query construction assures the highest user privacy over curious and unbounded computation servers. Therefore, the need for information-theoretic private retrieval was fulfilled by various schemes in a variety of PIR settings. But, there is a lack of efficient encryption switching scheme which supports efficient switching between information-theoretic to/from computationally bounded PIRs. We propose a combination of new bit connection methods called rail-shape and signal-shape and new quadratic residuosity assumption based family of trapdoor functions for generic single database private block retrieval (PBR). The main goal of this work is to show that the possibility of mapping from computationally bounded privacy to information theoretic privacy or vice-versa in a single database setting using newly constructed bit connection and trapdoor function combinations. Notably, the proposed schemes are single round, memoryless and plain database schemes (at their basic constructions).
In this thesis, we study two fundamental areas of secure computation over a network.First, we study general two-party secure computation, where two mutually distrustful parties are trying to compute an arbitrary function of their inputs, without revealing any extra information (even if one of them is malicious).We prove that, if any nontrivial function can be so computed, then so can every other function.That is, every non-trivial function is complete for two-party secure computation.Consequently, the complexity assumptions sufficient and/or necessary for securely computing f are the same for every non-trivial function f.Next, we study the concrete problem of secure database access, where the privacy of both the database and the user is to be protected from each other and from all other participating or eavesdropping parties.We are interested in practical and theoretical aspects of this problem, addressing issues of efficiency, security, and complexity.More specifically, we start from the model of private information retrieval (PIR), where users are trying to retrieve information from a database while keeping their queries private from the database owner.We then explore the following directions: * We study the necessary assumptions for single server PIR with low communication.We prove that oblivious transfer is necessary, implying that PIR is a complete primitive for secure computation, and that computational SPIR protocols (defined below) can be efficiently constructed from PIR protocols.* We introduce the model of SPIR, where the privacy of the data, as well as the user, is guaranteed.We show how to efficiently transform PIR protocols into SPIR protocols, for both the information-theoretic and computational settings. "We introduce the random server model for PIR, and show how to use it to achieve information theoretic solutions in which the database need not give away its data to be replicated, and with minimal on-line computation for the database.
Abstract. In this paper we present a single-round, single-server symmetrically private information retrieval scheme, in which privacy of user follows from intractability of the quadratic residuacity problem and the privacy of the database follows from the XOR assumption for quadratic residues introduced in this paper. The communication complexity of the proposed scheme for retrieving one bit can be made O(n ɛ), for any ɛ>0, where n is the number of bits in the database. We extend the protocol to a block retrieval scheme which is specially efficient when the number of records in the database is equal to the size of each record.