• Information Technology
  • Human Resources
  • Careers
  • Giving
  • Library
  • Bookstore
  • Active Living
  • Continuing Education
  • Go Dinos
  • UCalgary Maps
  • UCalgary Directory
  • Academic Calendar
My UCalgary
Webmail
D2L
ARCHIBUS
IRISS
  • Faculty of Arts
  • Cumming School of Medicine
  • Faculty of Environmental Design
  • Faculty of Graduate Studies
  • Haskayne School of Business
  • Faculty of Kinesiology
  • Faculty of Law
  • Faculty of Nursing
  • Faculty of Nursing (Qatar)
  • Schulich School of Engineering
  • Faculty of Science
  • Faculty of Social Work
  • Faculty of Veterinary Medicine
  • Werklund School of Education
  • Information TechnologiesIT
  • Human ResourcesHR
  • Careers
  • Giving
  • Library
  • Bookstore
  • Active Living
  • Continuing Education
  • Go Dinos
  • UCalgary Maps
  • UCalgary Directory
  • Academic Calendar
  • Libraries and Cultural Resources
View Item 
  •   PRISM Home
  • Science
  • Science Research & Publications
  • View Item
  •   PRISM Home
  • Science
  • Science Research & Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Oblivious Decision Programs from Oblivious Transfer: Efficient Reductions

Thumbnail
Download
Paper.pdf (480.0Kb)
Download Record
Download to EndNote/RefMan (RIS)
Download to BibTex
Author
Mohassel, Payman
Niksefat, Salman
Accessioned
2011-09-16T00:32:43Z
Available
2011-09-16T00:32:43Z
Issued
2011-09-16T00:32:43Z
Other
Secure computation
Subject
cryptography
Type
journal article
Metadata
Show full item record

Abstract
In this paper, we design efficient protocols for a number of \emph{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 \emph{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 \emph{malicious} adversaries in the standard ideal/real world simulation-based paradigm. The majority of the existing work on the same problems focus 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.
Grantingagency
Other
Refereed
No
Corporate
University of Calgary
Faculty
Science
Doi
http://dx.doi.org/10.11575/PRISM/30278
Uri
http://hdl.handle.net/1880/48739
Collections
  • Science Research & Publications

Browse

All of PRISMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

LoginRegister

Download Results

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors

  • Email
  • SMS
  • 403.220.8895
  • Live Chat

Energize: The Campaign for Eyes High

Privacy Policy
Website feedback

University of Calgary
2500 University Drive NW
Calgary, AB T2N 1N4
CANADA

Copyright © 2017