*21:17* [Pub][ePrint]
Incentivizing Outsourced Computation, by Mira Belenkiy and Melissa Chase and C. Chris Erway and John Jannotti and Alptekin Küpçü and Anna Lysyanskaya
We describe different strategies a central authority, the boss, can use to distribute computation to untrusted contractors. Our problem is inspired by volunteer distributed computing projects such as SETI@home, which outsource computation to large numbers of participants. For many tasks, verifying a task\'s output requires as much work as computing it again; additionally, some tasks may produce certain outputs with greater probability than others. A selfish contractor may try to exploit these factors, by submitting potentially incorrect results and claiming a reward. Further, malicious contractors may respond incorrectly, to cause direct harm or to create additional overhead for result-checking.We consider the scenario where there is a credit system whereby users can be rewarded for good work and fined for cheating. We show how to set rewards and fines that incentivize proper behavior from rational contractors, and mitigate the damage caused by malicious contractors. We analyze two strategies: random double-checking by the boss, and hiring multiple contractors to perform the same job.

We also present a bounty mechanism when multiple contractors are employed; the key insight is to give a reward to a contractor who catches another worker cheating. Furthermore, if we can assume that at least a small fraction h of the contractors are honest (1% − 10%), then we can provide graceful degradation for the accuracy of the system and the work the boss has to perform. This is much better than the Byzantine approach, which typically assumes h > 60%.

*06:17* [Pub][ePrint]
Policy-based Secure Deletion, by Christian Cachin and Kristiyan Haralambiev and Hsu-Chun Hsiao and Alessandro Sorniotti
Securely deleting data from storage systems has become difficult today. Most storage space is provided as a virtual resource and traverses

many layers between the user and the actual physical storage medium.

Operations to properly erase data and wipe out all its traces are

typically not foreseen. This paper introduces a cryptographic model

for policy-based secure deletion of data in storage systems, whose

security relies on the proper erasure of cryptographic keys.

Deletion operations are expressed in terms of a deletion policy that

describes data destruction through deletion attributes and

protection classes. A protection class is first applied to the

stored data. Later, a secure deletion operation takes attributes as

parameters and triggers the destruction of all data whose protection

class is deleted according to the policy. No stored data is ever

re-encrypted. A cryptographic construction is presented for

deletion policies given by directed acyclic graphs; it is built in a

modular way from exploiting that secure deletion schemes may be

composed with each other. Finally, the paper describes a prototype

implementation of a Linux filesystem with policy-based secure

deletion.

*06:17* [Pub][ePrint]
Optimal Suspicion Functions for Tardos Traitor Tracing Schemes, by Jan-Jaap Oosterwijk and Boris Skoric and Jeroen Doumen
We investigate alternative suspicion functions for Tardos traitor tracing schemes. In the simple decoder approach (computation of a score for every user independently) we derive suspicion functions that optimize a performance indicator related to the sufficient code length $\\ell$ in the limit of large coalition size $c$. Our results hold for the Restricted-Digit Model as well as the Combined-Digit Model. The scores depend on information that is usually not availableto the tracer -- the attack strategy or the tallies of the symbols received by the colluders. We discuss how such results can be used in realistic contexts.

We study several combinations of coalition attack strategy vs. suspicion function optimized against some attack (another attack or the same). In many of these combinations the usual scaling $\\ell \\propto c^2$ is replaced by a lower power of $c$, e.g. $c^{3/2}$. We find that the interleaving strategy is an especially

powerful attack, and the suspicion function tailored against interleaving is effective against all considered attacks.

*06:17* [Pub][ePrint]
MiniLEGO: Efficient Secure Two-Party Computation From General Assumptions, by Tore Kasper Frederiksen and Thomas Pelle Jakobsen and Jesper Buus Nielsen and Peter Sebastian Nordholt and Claudio Orlandi
One of the main tools to construct secure two-party computation protocols are Yao garbled circuits. Using the cut-and-choose technique, one can get reasonably efficient Yao-based protocols with security against malicious adversaries. At TCC 2009, Nielsen and Orlandi suggested to apply cut-and-choose at the gate level, while previously cut-and-choose was applied on the circuit as a whole. This appealing idea allows for a speed up with practical significance (in the order of the logarithm of the size of the circuit) and has become known as the ``LEGO\'\' construction. Unfortunately the construction by Nielsen and Orlandi is based on a specific number-theoretic assumption and requires public-key operations per gate of the circuit.The main technical contribution of this work is a new XOR-homomorphic commitment scheme based on oblivious transfer, that we use to cope with the problem of connecting the gates in the LEGO construction. Our new protocol has the following advantages:

\\begin{enumerate}

\\item

It maintains the efficiency of the LEGO cut-and-choose.

\\item

After a number of seed oblivious transfers linear in the security parameter, the construction uses only primitives from Minicrypt (i.e., private-key cryptography) per gate in the circuit (hence the name MiniLEGO).

\\item

On the contrary of original LEGO, MiniLEGO is compatible with all known optimization for Yao garbled gates (row reduction, free-XORs, point-and-permute).

\\end{enumerate}