2012 | OriginalPaper | Buchkapitel
Oblivious Decision Programs from Oblivious Transfer: Efficient Reductions
verfasst von : Payman Mohassel, Salman Niksefat
Erschienen in: Financial Cryptography and Data Security
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we design efficient protocols for a number of
private database query
problems. Consider a general form of the problem where a client who holds a private input interacts with a server who holds a private decision program (e.g. a decision tree or a branching program) with the goal of evaluating his input on the decision program without learning any additional information. Many known private database queries such as Symmetric PIR, and Private Keyword Search can be formulated as special cases of this problem.
We design
computationally efficient
protocols for the above general problem, and a few of its special cases. In addition to being one-round and requiring a small amount of work by the client (in the RAM model), our protocols only require a small number of exponentiations (independent of the server’s input) by both parties. Our constructions are, in essence, efficient and black-box reductions of the above problem to 1-out-of-2 oblivious transfer. We prove our protocols secure (private) against
malicious
adversaries in the standard ideal/real world simulation-based paradigm.
The majority of the existing work on the same problems focuses on optimizing communication. However, in some environments (supported by a few experimental studies), it is the computation and not the communication that may be the performance bottleneck. Our protocols are suitable alternatives for such scenarios.