*04:17* [Pub][ePrint]
Incentivized Outsourced Computation Resistant to Malicious Contractors, by Alptekin Kupcu
With the rise of Internet computing, outsourcing difficult computational tasks became an important need. Yet, once the computation is outsourced, the job owner loses control, and hence it is crucial to provide guarantees against malicious actions of the contractors involved. Cryptographers have an almost perfect solution, called fully homomorphic encryption, to this problem. This solution hides both the job itself and any inputs to it from the contractors, while still enabling them to perform the necessary computation over the encrypted data. This is a very strong security guarantee, but the current constructions are highly impractical.In this paper, we propose a different approach to outsourcing computational tasks. We are not concerned with hiding the job or the data, but our main task is to ensure that the job is computed correctly. We also observe that not all contractors are malicious; rather, majority are rational. Thus, our approach brings together elements from cryptography, as well as game theory and mechanism design. We achieve the following results: (1) We incentivize all the rational contractors to perform the outsourced job correctly, (2) we guarantee high fraction (e.g., 99.9%) of correct results even in the existence of a relatively large fraction (e.g., 33%) of malicious irrational contractors in the system, (3) and we show that our system achieves these while being almost as efficient as running the job locally (e.g., with only 3% overhead). Such a high correctness guarantee was not known to be achieved with such efficiency.

*04:17* [Pub][ePrint]
Two novel applications of bilinear groups to ABE encryption, by Riccardo Longo and Chiara Marcolla and Massimiliano Sala
Bilinear groups are often used to create Attribute-Based Encryption (ABE) algorithms.In particular, they have been used to create an ABE system with multi authorities, but limited to the ciphertext-policy instance.

Here, for the first time, we propose two multi-authority key-policy ABE systems.

In our first proposal, the authorities may be set up in any moment and without any coordination.

A party can simply act as an ABE authority by creating its own public parameters and issuing private keys to the users.

A user can thus encrypt data choosing both a set of attributes and a set of trusted authorities, maintaining full control unless all his chosen authorities collude against him.

In our second system, the authorities are allowed to collaborate to achieve shorter keys and parameters, enhancing the efficiency of encryption and decryption.

We prove our systems secure under algebraic assumptions on the bilinear groups: the bilinear Diffie-Hellmann assumption and an original variation of the former.

*04:17* [Pub][ePrint]
Partial Garbling Schemes and Their Applications, by Yuval Ishai and Hoeteck Wee
Garbling schemes (aka randomized encodings of functions) represent a function F by a \"simpler\" randomized function F^ such that F^(x) reveals F(x) and no additional information about x. Garbling schemes have found applications in many areas of cryptography. Motivated by the goal of improving the efficiency of garbling schemes, we make the following contributions:- We suggest a general new notion of partial garbling which unifies several previous notions from the literature, including standard garbling schemes, secret sharing schemes, and \"conditional disclosure of secrets\". This notion considers garbling schemes in which part of the input is public, in the sense that it can be leaked by F^.

- We present constructions of partial garbling schemes for (boolean and arithmetic) formulas and branching programs which take advantage of the public input to gain better efficiency.

- We demonstrate the usefulness of the new notion by presenting applications to efficient attribute-based encryption, delegation, and secure computation. In each of these applications, we obtain either new schemes for larger classes of functions or efficiency improvements from quadratic to linear. In particular, we obtain the first ABE scheme in bilinear groups for arithmetic formulas, as well as more efficient delegation schemes for boolean and arithmetic branching programs.

*04:17* [Pub][ePrint]
Ring ORAM: Closing the Gap Between Small and Large Client Storage Oblivious RAM, by Ling Ren and Christopher W. Fletcher and Albert Kwon and Emil Stefanov and Elaine Shi and Marten van Dijk and Sriniv
We present Ring ORAM, a simple and low-latency ORAM construction that can be parameterized for either small or large client storage.Simply by tuning parameters, Ring ORAM matches or exceeds the performance of the best-known small and large client storage schemes and can achieve a constant factor online bandwidth overhead over insecure systems.

We evaluate Ring ORAM in theory and in practice.

On the theory side, we prove that Ring ORAM matches the asymptotic bandwidth and client storage of Path ORAM, the prior-art scheme for small client storage.

Tuning parameters for small client storage, Ring ORAM reduces overall bandwidth relative to Path ORAM by a factor of $2.7\\times$ and reduces online bandwidth to constant (a $57\\times$ improvement over Path ORAM given realistic parameters).

Tuning parameters for large client storage, Ring ORAM outperforms Path ORAM (which is given equal storage) by $4.5\\times$ and SSS ORAM, the prior-art scheme for large client storage, by 16-33\\%.

Using secure processors as a case study for small client storage, Ring ORAM on average reduces ORAM response time by nearly $5\\times$ and improves workload completion time by $2.75\\times$, relative to Path ORAM.

In the large storage setting, running an enterprise file system trace with bursty requests, Ring ORAM adds negligible overhead to response time given a $>100$~Mbps network bandwidth.

By comparison, Burst ORAM incurs large overheads in response time unless network bandwidth $>350$~Mbps.

These results suggest that Ring ORAM is a compelling construction in both large client storage (e.g., file server) and small client storage (e.g., remote secure processor) settings.

*04:17* [Pub][ePrint]
Hierarchical deterministic Bitcoin wallets that tolerate key leakage, by Gus Gutoski and Douglas Stebila
A Bitcoin wallet is a set of private keys known to a user and which allow that user to spend any Bitcoin associated with those keys. In a hierarchical deterministic (HD) wallet, child private keys are generated pseudorandomly from a master private key, and the corresponding child public keys can be generated by anyone with knowledge of the master public key. These wallets have several interesting applications including Internet retail, trustless audit, and a treasurer allocating funds among departments. A specification of HD wallets has even been accepted as Bitcoin standard BIP32.Unfortunately, in all existing HD wallets---including BIP32 wallets---an attacker can easily recover the master private key given the master public key and any child private key. This vulnerability precludes use cases such as a combined treasurer-auditor, and some in the Bitcoin community have suspected that this vulnerability cannot be avoided.

We propose a new HD wallet that is not subject to this vulnerability. Our HD wallet can tolerate the leakage of up to m private keys with a master public key size of O(m). We prove that breaking our HD wallet is at least as hard as the so-called ``one more\'\' discrete logarithm problem.