*15:45*[Event][New] MPC14: Workshop on Theory and Practice of Secure Multiparty Computation

From May 5 to May 9

Location: Aarhus, Denmark

More Information: http://ctic.au.dk/workshops-conferences/mpc-2014/

Get an update on changes of the IACR web-page here. For questions, contact *newsletter (at) iacr.org*.
You can also get this service via

- eMail subscription
- RSS (select channels below)
- Web (all channels)

To receive your credentials via mail again, please click here.

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

From May 5 to May 9

Location: Aarhus, Denmark

More Information: http://ctic.au.dk/workshops-conferences/mpc-2014/

Submission: 31 March 2014

Notification: 23 May 2014

From September 8 to September 12

Location: Fribourg, Switzerland

More Information: http://www.ectcm.net

2014-02-05

We settle a long standing open problem which has pursued a full characterization of completeness of (potentially randomized) finite functions for 2-party computation that is secure against active adversaries. Since the first such complete function was discovered [Kilian, FOCS 1988], the question of which finite 2-party functions are complete has been studied extensively, leading to characterization in many special cases. In this work, we completely settle this problem.

We provide a polynomial time algorithm to test whether a 2-party finite secure function evaluation (SFE) functionality (possibly randomized) is complete or not. The main tools in our solution include:

-- A formal linear algebraic notion of {\\em redundancy} in a general 2-party randomized function.

-- A notion of {\\em statistically testable games}. A kind of interactive proof in the information-theoretic setting where {\\em both} parties are computationally unbounded but differ in their knowledge of a secret.

-- An extension of the (weak) {\\em converse of Shannon\'s channel coding theorem}, where an adversary can adaptively choose the channel based on it view.

We show that any function $f$, if complete, can implement any (randomized) circuit $C$ using only $O(|C| + k)$ calls to $f$, where $k$ is the statistical security parameter. In particular, for any two-party functionality $g$, this establishes a universal notion of its quantitative ``cryptographic complexity\'\' independent of the setup and has close connections to circuit complexity.

Known constructions of blind signature schemes suffer from at least one of the following limitations: (1) rely on parties having access to a common reference string or a random oracle, (2) are not round-optimal, or (3) are prohibitively expensive.

In this work, we construct the \\emph{first} blind-signature scheme that does not suffer from any of these limitations. In other words, besides being round optimal and having a standard model proof of security, our scheme is very efficient. Specifically, in our scheme, one signature is of size $6.5$ KB and the communication complexity of the signing protocol is roughly $100$ KB. An amortized variant of our scheme has communication complexity less that $1$ KB.

The notion of *garbled random-access machines* (garbled RAMs) was introduced by Lu and Ostrovsky (Eurocrypt 2013). It can be seen as an analogue of Yao\'s garbled circuits, that allows a user to garble a RAM program directly, without performing the expensive step of converting it into a circuit. In particular, the size of the garbled program and the time it takes to create and evaluate it are only proportional to its running time on a RAM rather than its circuit size. Lu and Ostrovsky gave a candidate construction of this primitive based on pseudo-random functions (PRFs).

The starting point of this work is a subtle yet difficult-to-overcome issue with the Lu-Ostrovsky construction, that prevents a proof of security from going through. Specifically, the construction requires a complex \"circular\" use of Yao garbled circuits and PRFs. As our main result, we show how to remove this circularity and get a provably secure solution using *identity-based encryption* (IBE). We also abstract out, simplify and generalize the main ideas behind the Lu-Ostrovsky construction, making them easier to understand and analyze.

In a companion work to ours (Part II), Lu and Ostrovsky show an alternative approach to solving the circularity problem. Their approach relies only on the existence of one-way functions, at the price of higher overhead. Specifically, our construction has overhead $\\poly(k)\\polylog(n)$ (with $k$ the security parameter and $n$ the data size), while the Lu-Ostrovsky approach can achieve overhead $\\poly(k)n^\\eps$ for any constant $\\eps>0$. It remains as an open problem to achieve an overhead of $\\poly(k)\\polylog(n)$ assuming only the existence of one-way functions.

In EUROCRYPT 2013, Lu and Ostrovsky proposed the notion of Garbled RAM (GRAM) programs. These GRAM programs are analogous to the classic result of Yao\'s garbled circuits: a large encrypted memory can first be provided to evaluator, and then a program can separately be garbled and sent to an evaluator to securely execute while learning nothing but the output of the program and its running time. The key feature of GRAM is that it harnesses the natural complexity-theoretic power that Random Access Memory (RAM) programs have over circuits, such as in binary search or randomized algorithms, where program can be executed in a garbled way without \"unrolling\" it into a circuit. The candidate Lu-Ostrovsky GRAM scheme proposed in that paper is based on the existence of one-way functions, but due to an implicit reliance on a complex \"circular\" use of Yao garbled circuits, the scheme requires an additional circularity assumptions and may not be secure otherwise.

In this paper, we show how to construct efficient GRAM without circularity and based solely on the existence of any one-way function. The novel approach that allows us to break the circularity is a modification of the Goldreich-Goldwasser-Micali (PRF) construction. More specifically, we modify the PRF to allow PRF-keys to be \"adaptively revoked\" during run-time at the additive cost of roughly log n per revocation. Then, to improve the overhead of this scheme, we apply a delicate recursion technique that bootstraps mini-GRAM schemes into larger, more powerful ones while still avoiding circularity in the hybrid arguments. This results in secure GRAM with overhead of poly($k$)(min($t; n^\\eps$)) for any constant $\\eps>0$, where $n$ is the size of memory and $t$ is the running time.

In a companion work (Part I), Gentry, Halevi, Raykova, and Wichs show an alternative approach using identity-based encryption to solve the circularity problem. Their scheme achieves overhead of poly($k$)polylog($n$) assuming the existence of IBE.

CloudFlare is looking for a talented security engineer to join our team. We are working on a number of ambitious projects to secure the web and protect our customers from threats of all sorts. The role of security engineer at CloudFlare is more that of a builder than a breaker. You will have to approach problems with creativity and flexibility and be able to identify and use the best tools for the job or build better ones from scratch. At CloudFlare, we are serious about protecting our customers and advancing the state of the art in computer security.

**Requirements:**

**Bonus Points:**

2014-02-04

We present a novel mechanism that allows a client

to securely outsource his private data to the cloud while at the same

time to delegate to a third party the right to run

certain algorithms on his data. The mechanism is

privacy-preserving, meaning that the third party only learns the result

of his algorithm on the client\'s data, while at the same time the access

pattern on the client\'s data is hidden from the cloud. To achieve this we

combine recent advances in the field of Oblivious RAM and Secure Two-Party

Computation: We develop an Oblivious RAM which is ran between the cloud and a

proxy server, and which does not need the data to be decrypted at any

point. The evaluation on the data is done by employing Yao\'s garbled

circuit solution for Secure Two-Party Computation.

Anonymity and authenticity are both important yet often conflicting security goals in a wide range of applications. On the one hand for many applications (say for access control) it is crucial to be able to verify the identity of a given legitimate party (a.k.a. entity authentication). Alternatively an application might require that no one but a party can communicate on its behalf (a.k.a. message authentication). Yet, on the other hand privacy concerns also dictate that anonymity of a legitimate party should be preserved; that is no information concerning the identity of parties should be leaked to an outside entity eavesdropping on the communication. This conflict becomes even more acute when considering anonymity with respect to an active entity that may attempt to impersonate other parties in the system.

In this work we resolve this conflict in two steps. First we formalize what it means for a system to provide both authenticity and anonymity even in the presence of an active man-in-the-middle adversary for various specific applications such as message and entity authentication using the constructive cryptography framework of~\\cite{Mau11}. Our approach inherits the composability statement of constructive cryptography and can therefore be directly used in any higher-level context. Next we demonstrate several simple protocols for realizing these systems, at times relying on a new type of (probabilistic) Message Authentication Code (MAC) called \\emph{key indistinguishable} (KI) MACs. Similar to the key hiding encryption schemes of~\\cite{BellareBDP01} they guarantee that tags leak no discernible information about the keys used to generate them.

A \\emph{key-homomorphic} pseudorandom function (PRF) family

$\\set{F_{s} \\colon D \\to R}$ allows one to efficiently compute the

value $F_{s+t}(x)$ given $F_{s}(x)$ and $F_{t}(x)$. Such functions

have many applications, such as distributing the operation of a

key-distribution center and updatable symmetric encryption. The only

known construction of key-homomorphic PRFs without random oracles, due

to Boneh \\etal (CRYPTO~2013), is based on the learning with errors

(\\lwe) problem and hence on worst-case lattice problems. However, the

security proof relies on a very strong \\lwe assumption (i.e., very

large approximation factors), and hence has quite inefficient

parameter sizes and runtimes.

In this work we give new constructions of key-homomorphic PRFs that

are based on much weaker \\lwe assumptions, are much more efficient in

time and space, and are still highly parallel. More specifically, we

improve the \\lwe approximation factor from exponential in the input

length to exponential in its \\emph{logarithm} (or less). For input

length~$\\lambda$ and~$2^{\\lambda}$ security against known lattice

algorithms, we improve the key size from~$\\lambda^{3}$ to~$\\lambda$

bits, the public parameters from~$\\lambda^{6}$ to~$\\lambda^{2}$ bits,

and the runtime from~$\\lambda^{7}$ to~$\\lambda^{\\omega+1}$ bit

operations (ignoring polylogarithmic factors in~$\\lambda$), where

$\\omega \\in [2,2.373]$ is the exponent of matrix multiplication. In

addition, we give even more efficient ring-\\lwe-based constructions

whose key sizes, public parameters, and \\emph{incremental} runtimes on

consecutive inputs are all \\emph{quasi-linear}~$\\Otil(\\lambda)$, which

is optimal up to polylogarithmic factors. To our knowledge, these are

the first \\emph{low-depth} PRFs (whether key homomorphic or not)

enjoying any of these efficiency measures together with nontrivial

proofs of~$2^{\\lambda}$ security under any conventional assumption.

In the last few years the efficiency of secure multi-party computation (MPC) increased in several orders of magnitudes. However, this alone might not be enough if we want MPC protocols to be used in practice.

A crucial property that is needed in many applications is that everyone can check that a given (secure) computation was performed correctly -- even in the extreme case where all the parties involved in the computation are corrupted, and even if the party who wants to verify the result was not involved. An obvious example of this is electronic voting, but also in many types of auctions one may want independent verification of the result. Traditionally, this is achieved by using non-interactive zero-knowledge proofs.

A recent trend in MPC protocols is to have a more expensive preprocessing phase followed by a very efficient online phase, e.g., the recent so-called SPDZ protocol by Damgård et al. Applications such as voting and some auctions are perfect applications for these protocols, as the parties usually know well in advance when the computation will take place, and using those protocols allows us to use only cheap information theoretic primitives in the actual computation. Unfortunately no protocol of the SPDZ type supports an audit phase.

In this paper we formalize the concept of publicly auditable secure computation and provide an enhanced version of the SPDZ protocol where, even if all the servers are corrupted, anyone with access to the transcript of the protocol can check that the output is indeed correct. Most importantly, we do so without compromising the performance of SPDZ i.e., the cost of our online phase is the same as that of SPDZ, up to a small constant factor of about two.