On Hiding Information from an Oracle

We consider the problem of computing with encrypted data. Player A wishes to know the value f(x) for some x but lacks the power to compute it. Player Β has the power to compute f and is willing to send f(y) to A if she sends him y, for any y. Informally, an encryption scheme for the problem f is a method by which A, using her inferior resources, can transform the cleartext instance x into an encrypted instance y, obtain f(y) from B, and infer f(x) from f(y) in such a way that Β cannot infer x from y. When such an encryption scheme exists, we say that f is encryptable.

• Publication year

  1987

• Venue

  Proceeding Structure in Complexity Theory

• Publication date

  1987-01-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/28395.28417
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Knowledge Complexity of Interactive Proof Systems

  1989cited by this paper
• Minimum-Knowledge Interactive Proofs for Decision Problems

  1989cited by this paper
• Minimum Disclosure Proofs of Knowledge

  1988cited by this paper
• A Simple Protocol for Secure Circuit Evaluation

  1988cited by this paper
• Does co-NP Have Short Interactive Proofs?

  1987cited by this paper
• Cryptographic Computation: Secure Faut-Tolerant Protocols and the Public-Key Model

  1987cited by this paper
• How to play ANY mental game

  1987cited by this paper
• Random self-reducibility and zero knowledge interactive proofs of possession of information

  1987cited by this paper
• The Complexity of Perfect Zero-Knowledge

  1987cited by this paper
• Proofs that yield nothing but their validity and a methodology of cryptographic protocol design

  1986cited by this paper
• Zero-Knowledge Simulation of Boolean Circuits

  1986cited by this paper
• The polynomial-time hierarchy and sparse oracles

  1986cited by this paper
• How to generate and exchange secrets

  1986cited by this paper
• Complexity and Structure

  1986cited by this paper
• Encrypting Problem Instances: Or ..., Can You Take Advantage of Someone Without Having to Trust Him?

  1985cited by this paper
• The knowledge complexity of interactive proof-systems

  1985cited by this paper
• A private interactive test of a boolean predicate a minimum-knowledge public-key cryptosystems

  1985cited by this paper
• A Database Encryption Scheme Which Allows the Computation of Statistics Using Encrypted Data

  1985cited by this paper
• Quantitative Relativizations of Complexity Classes

  1984cited by this paper
• Some Consequences of Non-Uniform Conditions on Uniform Classes

  1983cited by this paper
• Protocols for secure computations

  1982cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• On Simultaneous Resource Bounds (Preliminary Version)

  1979cited by this paper
• Universal Classes of Hash Functions

  1979cited by this paper
• ON DATA BANKS AND PRIVACY HOMOMORPHISMS

  1978cited by this paper
• The Polynomial-Time Hierarchy

  1976cited by this paper
• Every Prime has a Succinct Certificate

  1975cited by this paper
• Introduction to Probability Theory

  1972cited by this paper
• The Art of Computer Programming

  1968cited by this paper
• An introduction to the theory of numbers

  1961cited by this paper
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

  1952cited by this paper
• An Introduction to the Theory of Numbers

  1939cited by this paper

• AG codes from the Hermitian curve for Cross-Subspace Alignment in Private Information Retrieval

  2025cites this paper
• Traversal Learning: A Lossless And Efficient Distributed Learning Framework

  2025cites this paper
• Quantum function secret sharing

  2025cites this paper
• Systematic Use of Random Self-Reducibility against Physical Attacks

  2024cites this paper
• Secure fully-verifiable outsourcing of modular exponentiation: two servers check each other

  2024cites this paper
• Learning Randomized Reductions

  2024cites this paper
• On Single-Server Delegation Without Precomputation

  2023cites this paper
• Errorless Versus Error-Prone Average-Case Complexity

  2022cites this paper
• A Note on the Hardness of Problems from Cryptographic Group Actions

  2022influential citation
• Combining Stochastic Defenses to Resist Gradient Inversion: An Ablation Study

  2022cites this paper
• On the Multi-user Security of Short Schnorr Signatures with Preprocessing

  2022cites this paper
• Single-Server Delegation of Small-Exponent Exponentiation from Quasilinear-Time Clients and Applications

  2022cites this paper
• Learner-Private Convex Optimization

  2021influential citation
• Comparison on security of single server and multiple servers blind quantum protocols

  2021cites this paper
• Pseudorandom Self-Reductions for NP-Complete Problems

  2021cites this paper
• Quantum Internet—Applications, Functionalities, Enabling Technologies, Challenges, and Research Directions

  2021cites this paper
• Equivalence of single-server and multiple-server blind quantum computation protocols

  2021cites this paper
• Private Retrieval, Computing, and Learning: Recent Progress and Future Challenges

  2021cites this paper
• InstaHide: Instance-hiding Schemes for Private Distributed Learning

  2020cites this paper
• Private Information Retrieval with Sublinear Online Time

  2020cites this paper
• Blind Quantum Computation Using a Circuit-Based Quantum Computer

  2020cites this paper
• Verifiable Quantum Cloud Computation Scheme Based on Blind Computation

  2020cites this paper
• Security Limitations of Classical-Client Delegated Quantum Computing

  2020cites this paper
• Blind Quantum Computation by Circuit Based Quantum Computer

  2020cites this paper
• Highly Efficient and Re-Executable Private Function Evaluation With Linear Complexity

  2020cites this paper
• Access Controls for IoT Networks

  2019cites this paper
• A tale of SNARKs: quantum resilience, knowledge extractability and data privacy. (Un recueil de SNARKs: sécurité quantique, extractabilité et confidentialité des données)

  2019cites this paper
• X-Secure T-Private Information Retrieval From MDS Coded Storage With Byzantine and Unresponsive Servers

  2019cites this paper
• Three-qubit exact Grover within the blind oracular quantum computation scheme

  2019cites this paper
• Efficient and Secure Outsourcing of Large-Scale Linear System of Equations

  2018cites this paper
• Robust verification of quantum computation

  2018influential citation
• Explorer Measurement-Based and Universal Blind Quantum Computation

  2018cites this paper
• Best Possible Information-Theoretic MPC

  2018cites this paper
• A Security Model for IoT Networks

  2018cites this paper
• The Discrete-Logarithm Problem with Preprocessing

  2018cites this paper
• Revisiting Single-server Algorithms for Outsourcing Modular Exponentiation

  2018influential citation
• Impossibility of blind quantum sampling for classical client

  2018cites this paper
• Highly Efficient and Reusable Private Function Evaluation with Linear Complexity

  2018cites this paper
• Blind Quantum Computation with Two Decoy States

  2017cites this paper
• On the implausibility of classical client blind quantum computing

  2017influential citation
• Zero-knowledge proofs for secure computation

  2017cites this paper
• Complexity-Theoretic Limitations on Blind Delegated Quantum Computation

  2017influential citation
• Hypercubes and Private Information Retrieval

  2017cites this paper
• The Capacity of Private Information Retrieval

  2017cites this paper
• The Capacity of Private Information Retrieval

  2016cites this paper
• Information Measure as Time Complexity

  2016influential citation
• Le logarithme discret dans les corps finis

  2016cites this paper
• Secure outsourcing of modular exponentiations in cloud and cluster computing

  2016cites this paper
• New Efficient and Flexible Algorithms for Secure Outsourcing of Bilinear Pairings

  2016cites this paper
• Improved algorithm for secure outsourcing of modular exponentiations with high checkability

  2016cites this paper
• Private Outsourcing of Matrix Multiplication over Closed Semi-rings

  2016cites this paper
• Introduction to Secure Outsourcing Computation

  2016cites this paper
• A New Framework for Privacy-Preserving Aggregation of Time-Series Data

  2016cites this paper
• An efficient instance hiding scheme

  2016influential citation
• Secure and Efficient Regression Analysis Outsourcing Algorithm for Cloud Server

  2016cites this paper
• Processing Over Encrypted Data: Between Theory and Practice

  2016cites this paper
• On the possibility of classical client secure delegated computation

  2016influential citation
• CRT-Based Outsourcing Algorithms for Modular Exponentiations

  2016cites this paper
• Privacy Preserving Cryptographic Protocols

  2016cites this paper
• The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes

  2016cites this paper
• Indistinguishability Obfuscation: From Approximate to Exact

  2016cites this paper
• The Capacity of Robust Private Information Retrieval With Colluding Databases

  2016cites this paper
• New Approaches for Secure Outsourcing Algorithm for Modular Exponentiations

  2016cites this paper
• Blind quantum computing with two almost identical states

  2016influential citation
• Evaluation and Cryptanalysis of the Pandaka Lightweight Cipher

  2015cites this paper
• Efficient and verifiable algorithms for secure outsourcing of cryptographic computations

  2015cites this paper
• Encryption and Privacy Concerns in Cloud Computing

  2015cites this paper
• Secure and Efficient Protocol for Outsourcing Large-Scale Systems of Linear Equations to the Cloud

  2015cites this paper
• New Publicly Verifiable Databases with Efficient Updates

  2015cites this paper
• An Improved Algorithm for Secure Outsourcing of Modular Exponentiations

  2015cites this paper
• Secure Outsourcing of Multiple Modular Exponentiations

  2015cites this paper
• Challenges and solutions for secure information centric networks: A case study of the NetInf architecture

  2015cites this paper
• Efficient algorithms for secure outsourcing of bilinear pairings

  2015cites this paper
• New Algorithms for Secure Outsourcing of Large-Scale Systems of Linear Equations

  2015cites this paper
• Self-assembly

  2014cites this paper
• Designing ORCIDS: Organizational Communications and Information Distribution System

  2014cites this paper
• The Past, evolving Present and Future of Discrete Logarithm

  2014cites this paper
• Research of Security Model and Cloud Computing Strategy

  2014cites this paper
• On secure outsourcing of cryptographic computations to cloud

  2014cites this paper
• Efficient and Verifiable Algorithm for Secure Outsourcing of Large-scale Linear Programming

  2014cites this paper
• Quantum fully homomorphic encryption scheme based on universal quantum circuit

  2014cites this paper
• Black-Box Separations for One-More (Static) CDH and Its Generalization

  2014cites this paper
• Cryptographic Cloud Storage with Hadoop Implementation

  2014cites this paper
• Parallel Homomorphic Encryption

  2013cites this paper
• Hardness of learning problems over Burnside groups of exponent 3

  2013cites this paper
• Algorithm-Based Secure Outsourcing of Matrix Computations

  2013influential citation
• Composable Security of Delegated Quantum Computation

  2013cites this paper
• Symmetric quantum fully homomorphic encryption with perfect security

  2013cites this paper
• Aggregate discovery and retrieval of contents from authenticated interface

  2013cites this paper
• Outsourcing of Verifiable Composite Modular Exponentiations

  2013cites this paper
• Cryptographic Cloud Storage with Hadoop Implementation

  2013cites this paper
• On Diffie-Hellman - like Security Assumptions

  2013cites this paper
• Security Ranking Among Assumptions Within the Uber Assumption Framework

  2013cites this paper
• Translation-Randomizable Distributions via Random Walks

  2013cites this paper
• Cryptography Challenges for Computational Privacyin Public Clouds

  2013cites this paper
• Secure outsourced computation of iris matching

  2012cites this paper
• New Algorithms for Secure Outsourcing of Modular Exponentiations

  2012cites this paper
• The Quantum Frontier

  2012cites this paper
• Resettable Statistical Zero Knowledge

  2012cites this paper
• Trusted content-based publish/subscribe trees

  2012cites this paper