CryptoDay. Nov 27, 2011
-------------------------------------------------------------------
Secure Computation with Sublinear Amortized Work
Mariana Raykova, Columbia University
Abstract: 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.
We present an approach to secure two-party computation that yields sublinear-time protocols, in an amortized sense, for functions that can be computed in sublinear time on a random access machine(RAM). Furthermore, a party whose input is ``small'' is required to maintain only small state. We describe a generic protocol that achieves the claimed complexity, based on any oblivious RAM and any protocol for secure two-party computation. We then present an optimized version of this protocol, where generic secure two-party computation is used only for evaluating a small number of simple operations.
joint work with Dov Gordon, Jonathan Katz, Vlad Kolesnikov, Tal Malkin, and Yevgeniy Vahlis
-------------------------------------------------------------------
Title: On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption
Speaker: Adriana Lopez-Alt
Authors: Adriana Lopez-Alt and Eran Tromer and Vinod Vaikuntanathan
Abstract:
We propose a new notion of secure multiparty computation
aided by a computationally-powerful but untrusted server (a ``cloud'', in
modern parlance). In this notion,
on-the-fly MPC, the cloud can non-interactively perform arbitrary, dynamically
chosen computations on data belonging to arbitrary sets of users chosen
on-the-fly. All user's input data and intermediate results are protected from
snooping by the cloud as well as other users.
This extends the standard notion of fully homomorphic encryption (FHE), where
users can only enlist the cloud's help in evaluating functions on their own
encrypted data.
In on-the-fly MPC, each user is involved only when initially uploading hi
(encrypted) data to the cloud, and in a final output decryption phase when
outputs are revealed; the complexity of both is independent of the function
being computed and the total number of users in the system. When users upload
their data, they need not decide in advance which function will be computed,
nor who are their peers in the cloud; they need only retroactively approve the
eventually-chosen functions and on what parties' data the functions were
evaluated.
This notion is qualitatively the best possible in mininizing interaction,
since the users' interaction in the decryption stage is inevitable: we show
that removing it would imply generic program obfuscation and is thus
impossible. Our contributions are two-fold:
1. We define the notion of a multikey fully homomorphic encryption capable of
operating on
inputs encrypted under multiple, unrelated keys. A ciphertext resulting from a
multikey evaluation
can be jointly decrypted using the secret keys of all the users involved in
the computation. We show how to use a
multikey FHE scheme to construct an on-the-fly MPC protocol.
2. We construct a multikey FHE scheme based on
NTRU, a very efficient public-key encryption scheme proposed in the 1990s.
In this scheme, the ciphertext and key sizes grow only with the number of
parties whose data was fed into the function, and are independent of the total
number of potential parties, and of the evaluated function's complexity.
-------------------------------------------------------------
Title: Getting Results under Weak Expectations
Speaker: Yevgeniy Dodis
Abstract: Recently, there has been renewed interest in basing
cryptographic primitives on weak secrets, where the only information
about the secret is some non-trivial amount of (min-)entropy.
From a formal point of view, such results require to upper bound the
expectation of some function f(X), where X is a weak source in
question. We show an elementary inequality which essentially upper
bounds such "weak expectation" by two terms, the first of which is
*independent* of f, while the second only depends on the "variance" of
f under *uniform* distribution. Quite remarkably, as relatively simple
corollaries of this elementary inequality, we obtain some "unexpected"
results, in several cases noticeably simplifying/improving prior
techniques for the same problem. Examples include non-malleable
extractors, leakage-resilient symmetric encryption, seed-dependent
condensers and improved entropy loss for the leftover hash lemma.
-------------------------------------------------------------------
Title: A Survey of Secure Message Transmission with Public Discussion.
Speaker: Clint Givens
Abstract:
In the problem of Secure Message Transmission in the public discussion model (SMT-PD), a Sender wants to send a message to a Receiver privately and reliably. Sender and Receiver are connected by n channels, up to t < n of which may be maliciously controlled by a computationally unbounded adversary, as well as one public channel, which is reliable but not private. The SMT-PD abstraction has been shown instrumental in achieving secure multi-party computation on sparse networks, where a subset of the nodes are able to realize a broadcast functionality, which plays the role of the public channel.
In this talk, after formally de?ning the SMT-PD problem, we overview the basic constructions starting with the ?rst, rather communication-inef?cient solutions to the problem, and ending with the most ef?cient solutions known to-date—optimal private communication and sublinear public communication.
These complexities refer to resource use for a single execution of an SMT-PD protocol. We also review the amortized complexity of the problem, which would arise in natural use-case scenarios where S and R must send several messages back and forth, where later messages depend on earlier ones.