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

International Conference on Cryptology in India

Symmetrically Private Information Retrieval (Extended Abstract)

Sanjeev Kumar Mishra, Palash Sarkar

Published Jan 1, 2000• 0 citations
OpenAlex

Abstract

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.

Related papers

On Symmetrically Private Information Retrieval.

Sanjeev Kumar Mishra

In today's age of information it is very important that, information about the information which you are seeking should not be leaked even to the server who is going to provide you the desired information. On the other hand, considering information as commodity, it is age old wisdom that one should get only as much as he pays. In this paper we essentially consider this problem and provide suitable solutions. Under a new number theoretic assumption, XOR Assumption, we give single-round symmetrically private information retrieval (SPIR) scheme for bit retrieval with communication complexity O(n...

•Jan 1, 2000•3 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

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

Amos Beimel, Yuval Ishai, Eyal Kushilevitz +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, 1999•62 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

Replication is not needed: single database, computationally-private information retrieval

Eyal Kushilevitz, Rafail Ostrovsky

We establish the following, quite unexpected, result: replication of data for the computational private information retrieval problem is not necessary. More specifically, based on the quadratic residuosity assumption, we present a single database, computationally private information retrieval scheme with O(n/sup /spl epsiv//) communication complexity for any /spl epsiv/>0.

Annual Symposium on Foundations of Computer Science•Nov 22, 2002•956 citations

Efficient Linear Secure Computation and Symmetric Private Information Retrieval Protocols

Yanliang Zhou

Security and privacy are of paramount importance in the modern information age. Secure multi-party computation and private information retrieval are canonical and representative problems in cryptography that capture the key challenges in understanding the fundamentals of security and privacy. In this dissertation, we use information theoretic tools to tackle these two classical cryptographic primitives. In the first part, we consider the secure multi-party computation problem, where multiple users, each holding an independent message, wish to compute a function on the messages without revealing any additional information. We present an efficient protocol in terms of randomness cost to securely compute a vector linear function. In the second part, we discuss the symmetric private information retrieval problem, where a user wishes to retrieve one message from a number of replicated databases while keeping the desired message index a secret from each individual database. Further, the user learns nothing about the other messages. We present an optimal protocol that achieves the minimum upload cost for symmetric private information retrieval, i.e., the queries sent from the user to the databases have the minimum number of bits.

•Dec 1, 2020•0 citations
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.
In today's age of information it is very important that, information about the information which you are seeking should not be leaked even to the server who is going to provide you the desired information. On the other hand, considering information as commodity, it is age old wisdom that one should get only as much as he pays. In this paper we essentially consider this problem and provide suitable solutions. Under a new number theoretic assumption, XOR Assumption, we give single-round symmetrically private information retrieval (SPIR) scheme for bit retrieval with communication complexity O(n...
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).
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
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.
Security and privacy are of paramount importance in the modern information age. Secure multi-party computation and private information retrieval are canonical and representative problems in cryptography that capture the key challenges in understanding the fundamentals of security and privacy. In this dissertation, we use information theoretic tools to tackle these two classical cryptographic primitives. In the first part, we consider the secure multi-party computation problem, where multiple users, each holding an independent message, wish to compute a function on the messages without revealing any additional information. We present an efficient protocol in terms of randomness cost to securely compute a vector linear function. In the second part, we discuss the symmetric private information retrieval problem, where a user wishes to retrieve one message from a number of replicated databases while keeping the desired message index a secret from each individual database. Further, the user learns nothing about the other messages. We present an optimal protocol that achieves the minimum upload cost for symmetric private information retrieval, i.e., the queries sent from the user to the databases have the minimum number of bits.