- BLIND SEER
Efficient, secure and private information access is critical to today’s business and defense operations. While the need for data protection is clear, the queries must be protected as well, since they may reveal insights of the requester’s interests, agenda, mode of operation, etc. Thus, there is a clear need for efficient and secure systems and mechanisms of database access, which allow execution of complex queries, and guarantee protection to both server and client. We propose to develop such a system....more
- Secure Computation with Sublinear Amortized Work for RAMs
Traditional approaches to secure computation begin by representing the function f being computed as a circuit. For any function f that depends on each of its inputs, this implies a protocol with complexity at least linear in the input size. In fact, linear running time is inherent for secure computation of non-trivial functions, since each party must ``touch'' every bit of their input lest information about other party's input be leaked. This seems to rule out many interesting applications of secure computation in scenarios where at least one of the inputs is huge and sublinear-time algorithms can be utilized in the insecure setting; private database search is a prime example. In this work we ask the question whether this gap between the efficiency of insecure and secure algorithms for the same task can be bridged, i.e. whether we can have a protocol with sublinear computation complexity in the size of its inputs.
- Secure Computation for Multivariate Polynomials and Applications
There have been many works demonstarting strong feasibility results for
the secure computation of any function in time polynomial in the size
of its Boolean or arithmetic circuit. However, these generic approaches
typically lead to inefficient implementations since the circuit
representation of a functionality may be very large.
Thus, an important problem in MPC is designing highly efficient
protocols for smaller, yet large enough to be interesting,
sets of functionalities (election problems is a narrow example,
while linear algebraic problems is a more generic example).
We consider the problem of secure multiparty computation of the
class of functions that can be represented by polynomial-sized
multivariate polynomials. The multivariate polynomial is defined
over the inputs of the participating parties so that each
party contributes its inputs as values for some subset of the
variables in the polynomial representation.
There is a designated party receiving output that learns only the
output of the polynomial evaluation while all other parties receive
no output. (We note that our protocol can be generalized to allow
any subset of the parties to receive output.) We are interested
in these functions since a large collection of problems are naturally
and efficiently represented as multivariate polynomials over a
field or a ring: problems from linear algebra, statistics,
logic as well as operations on sets represented as polynomials.
- Secure Data Sharing with Encrypted Search
Often, different parties possess data of mutual interest.
They might wish to share portions of this data for collaborative
work, but consider the leak of unrelated portions to be a privacy
issue for themselves or their clients.
Thus, methods that provide a well-defined and secure sharing of
the data between untrusting parties can be useful tools. One such
method is the ability for a client to search the information residing
on another server without revealing to the server his identity or
the content of his query; at the same time, it is desirable to
guarantee that query capability is only granted to appropriate
clients and that they do not learn anything unrelated to the query.
Such a tool is useful in deciding and agreeing upon information-sharing
between parties who do not initially know if they have data worth
sharing with each other, and do not want to share information
until they do. Once the information of mutual interest is established,
the next step is providing a protocol that allows the retrieval of
this data without violating privacy guarantees that were achieved
during the search.
