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

ACM Symposium on Theory of Computing (STOC)

Protecting data privacy in private information retrieval schemes

Yael Gertner, Yuval Ishai, Eyal Kushilevitz Z, Tal Malkin

Published Jan 1, 1998• 445 citations
Publisher

Abstract

Abotract'An (;)-OT protocol (also denoted "all or nothing discloxwc of secrets") allows Bob to secretly choose one of n occret bits held hy Alice, in a way that at the end of the protocol Bob learnn only a oinglo bit of his choice, and Alice learns nothing about Bob% choice.
DOI
10.1145/276698.276723

Related papers

Information theoretic reductions among disclosure problems

Gilles Brassard A, Claude Crépeau, Jean-Marc Robert

Alice disposes of some number of secrets. She is willing to disclose one of them to Bob. Although she agrees to let him choose which secret he wants, she is not willing to allow him to gain any information on more than one secret. On the other hand, Bob does not want Alice to know which secret he wishes. An all-or-nothing disclosure is one by which, as soon as Bob has gained any information whatsoever on one of Alice's secrets, he has wasted his chances to learn anything about the other secrets. We assume that Alice is honest when she claims to be willing to disclose one secret to Bob (i.e. she is not about to send junk). The only cheating Alice is susceptible of trying is to figure out which secret is of interest to Bob. We address the following question from an information theoretic point of view: what is the most elementary disclosure problem? The main result is that the general all-or-nothing disclosure of secrets is equivalent to a much simpler problem, which we call the two-bit problem.

Annual Symposium on Foundations of Computer Science•Oct 1, 1986•153 citations

1-out-of-2 oblivious transfer using a flawed bit-string quantum protocol

Martin Plesch, Marcin Pawłowski, Matej Pivoluska

Oblivious transfer (OT) is an important tool in cryptography. It serves as a subroutine to other complex procedures of both theoretical and practical significance. A common attribute of OT protocols is that one party (Alice) has to send a message to another party (Bob) and has to stay oblivious to whether Bob did receive the message. Specific (OT) protocols vary by exact definition of the task---in the all-or-nothing protocol, Alice sends a single bit-string message, which Bob is able to read with only $50%$ probability, whereas in a 1-out-of-2 OT protocol Bob reads one out of two messages sent by Alice. These two flavors of protocol are known to be equivalent. Recently, a computationally secure all-or-nothing OT protocol based on quantum states was developed by A. Souto et al. [Phys. Rev. A 91, 042306 (2015)], which, however, cannot be reduced to a 1-out-of-2 OT protocol by standard means. Here we present an elaborate reduction of this protocol that retains the security of the original.

arXiv:1611.10087•Physical Review A•Apr 18, 2017•5 citations

Towards a theory of variable privacy

Poorvi L. Vora

We define "variable privacy" as the use of non-perfect protocols with parameters controlled by Alice. Variable privacy enables Alice to choose the amount of information leaked to Bob, in situations where information revelation bears a privacy cost and also provides a benefit. We propose a framework for the study of variable privacy, using a security perspective to obtain a privacy measure of the binary symmetric randomization protocol (flipping a bit with probability 1-#). We define an attack as any sequence of protocol instances that decreases estimation error on a bit beyond that possible with a single instance. Viewing the protocol as a communication channel for the data to be protected, we show that channel codes - i.e. error-correcting and error-detecting codes - are particularly e#cient attacks. In particular, they can be more e#cient than the repeated query attack.

•Jan 1, 2003•2 citations

Unconditionally secure all-or-nothing disclosure of secrets based on POVM measurements

Yang Wei, Liusheng Huang

Secure two-party protocols are of significant research and application value. All-or-Nothing Disclosure of Secrets (ANDOS) is such a kind of cryptographic task. It involves two parties, a vendor and a buyer. The vendor, say Alice, who disposes of several secrets and is willing to sell any of them to the buyer, say Bob, with the guarantee that no information about the other secrets will be obtained. Furthermore, Bob can freely choose his secret and wants to ensure that Alice can obtain on information about which of her secrets he has picked. In this paper, we present a new quantum ANDOS scheme which achieves the same functionality, but which is of unconditional security.

International Conference on Communications•Jul 13, 2006•0 citations

Private interactive communication across an adversarial channel

Ran Gelles, Amit Sahai, Akshay Wadia

Consider two parties Alice and Bob, who hold private inputs x and y, and wish to compute a function f(x, y) privately in the information theoretic sense; that is, each party should learn nothing beyond f(x, y). However, the communication channel available to them is noisy. This means that the channel can introduce errors in the transmission between the two parties. Moreover, the channel is adversarial in the sense that it knows the protocol that Alice and Bob are running, and maliciously introduces errors to disrupt the communication, subject to some bound on the total number of errors. A fundamental question in this setting is to design a protocol that remains private in the presence of large number of errors.

Conference on Innovations in Theoretical Computer Science•Jan 12, 2014•9 citations

General Two-Party Oblivious Circuit Evaluation

Sufyan T. F. Al-Janabi

A two-party oblivious circuit evaluation (2P- OCE) protocol is a way for a party Alice owns a secret x and another party Bob owns a secret y to compute the value of an agreed upon function f(x,y), where f can be computed by a polynomial sized Boolean circuit. This is done in such a way that Alice learns nothing about y and Bob learns nothing about x, except for what can be inferred from one's private input and the public value of f(x,y). This paper presents a general, correct, fair, honest, and maximum privacy 2P-OCE protocol that is based on a set of reductions to more simple cryptographic primitives. The protocol uses the primitives of one-out-of-two oblivious transfer (1-2-OT) and bit commitment (BC) as black boxes. Consequently, the protocol may be implemented with or without computational assumptions, depending on the type of 1-2-OT and BC used by participants.

•Dec 1, 2006•0 citations
Alice disposes of some number of secrets. She is willing to disclose one of them to Bob. Although she agrees to let him choose which secret he wants, she is not willing to allow him to gain any information on more than one secret. On the other hand, Bob does not want Alice to know which secret he wishes. An all-or-nothing disclosure is one by which, as soon as Bob has gained any information whatsoever on one of Alice's secrets, he has wasted his chances to learn anything about the other secrets. We assume that Alice is honest when she claims to be willing to disclose one secret to Bob (i.e. she is not about to send junk). The only cheating Alice is susceptible of trying is to figure out which secret is of interest to Bob. We address the following question from an information theoretic point of view: what is the most elementary disclosure problem? The main result is that the general all-or-nothing disclosure of secrets is equivalent to a much simpler problem, which we call the two-bit problem.
Oblivious transfer (OT) is an important tool in cryptography. It serves as a subroutine to other complex procedures of both theoretical and practical significance. A common attribute of OT protocols is that one party (Alice) has to send a message to another party (Bob) and has to stay oblivious to whether Bob did receive the message. Specific (OT) protocols vary by exact definition of the task---in the all-or-nothing protocol, Alice sends a single bit-string message, which Bob is able to read with only 5050%50 probability, whereas in a 1-out-of-2 OT protocol Bob reads one out of two messages sent by Alice. These two flavors of protocol are known to be equivalent. Recently, a computationally secure all-or-nothing OT protocol based on quantum states was developed by A. Souto et al. [Phys. Rev. A 91, 042306 (2015)], which, however, cannot be reduced to a 1-out-of-2 OT protocol by standard means. Here we present an elaborate reduction of this protocol that retains the security of the original.
We define "variable privacy" as the use of non-perfect protocols with parameters controlled by Alice. Variable privacy enables Alice to choose the amount of information leaked to Bob, in situations where information revelation bears a privacy cost and also provides a benefit. We propose a framework for the study of variable privacy, using a security perspective to obtain a privacy measure of the binary symmetric randomization protocol (flipping a bit with probability 1-#). We define an attack as any sequence of protocol instances that decreases estimation error on a bit beyond that possible with a single instance. Viewing the protocol as a communication channel for the data to be protected, we show that channel codes - i.e. error-correcting and error-detecting codes - are particularly e#cient attacks. In particular, they can be more e#cient than the repeated query attack.
Secure two-party protocols are of significant research and application value. All-or-Nothing Disclosure of Secrets (ANDOS) is such a kind of cryptographic task. It involves two parties, a vendor and a buyer. The vendor, say Alice, who disposes of several secrets and is willing to sell any of them to the buyer, say Bob, with the guarantee that no information about the other secrets will be obtained. Furthermore, Bob can freely choose his secret and wants to ensure that Alice can obtain on information about which of her secrets he has picked. In this paper, we present a new quantum ANDOS scheme which achieves the same functionality, but which is of unconditional security.
Consider two parties Alice and Bob, who hold private inputs x and y, and wish to compute a function f(x, y) privately in the information theoretic sense; that is, each party should learn nothing beyond f(x, y). However, the communication channel available to them is noisy. This means that the channel can introduce errors in the transmission between the two parties. Moreover, the channel is adversarial in the sense that it knows the protocol that Alice and Bob are running, and maliciously introduces errors to disrupt the communication, subject to some bound on the total number of errors. A fundamental question in this setting is to design a protocol that remains private in the presence of large number of errors.
A two-party oblivious circuit evaluation (2P- OCE) protocol is a way for a party Alice owns a secret x and another party Bob owns a secret y to compute the value of an agreed upon function f(x,y), where f can be computed by a polynomial sized Boolean circuit. This is done in such a way that Alice learns nothing about y and Bob learns nothing about x, except for what can be inferred from one's private input and the public value of f(x,y). This paper presents a general, correct, fair, honest, and maximum privacy 2P-OCE protocol that is based on a set of reductions to more simple cryptographic primitives. The protocol uses the primitives of one-out-of-two oblivious transfer (1-2-OT) and bit commitment (BC) as black boxes. Consequently, the protocol may be implemented with or without computational assumptions, depending on the type of 1-2-OT and BC used by participants.