Verifiable Outsourcing of Computations Using Garbled Onions

Abstract

<p>Solutions to the verifiable outsourcing problem based on Yao’s Garbled Circuit (GC) construction have been investigated in previous works. A major obstacle to the practicality of these solutions is the single-use nature of the GC construction. This work introduces the novel technique <em>onion garbling</em>, which circumvents this obstacle by using only a symmetric-key cipher as its cryptographic machinery. This work also proposes a non-interactive protocol for verifiable outsourcing which utilizes the onion garbling technique. The protocol works in a 3-party setting, and consists of a preprocessing phase and an online phase. The cost of a preprocessing phase which can support up to <em>N</em> computations is independent of <em>N</em> for the outsourcing party. For the other two parties, the memory and communication cost of <em>N</em>-reusability is proportional to N⋅m" role="presentation">N⋅m, where <em>m</em> is the bit-length of the input. The cost of input preparation and verification is O(m+n)" role="presentation">O(m+n) symmetric-key cipher operations, where <em>n</em> is the bit-length of the output. The overall costs associated with the outsourcing party are low enough to allow verifiable outsourcing of arbitrary computations by resource-constrained devices on constrained networks. Finally, this work reports on a proof-of-concept implementation of the proposed verifiable outsourcing protocol.</p>