A4 Article in conference proceedings
Verifiable Outsourcing of Computations Using Garbled Onions

List of Authors: Dönmez T.
Publisher: Springer Verlag
Publication year: 2018
Journal: Lecture Notes in Computer Science
Book title *: Security and Trust Management: 14th International Workshop, STM 2018, Barcelona, Spain, September 6–7, 2018, Proceedings
Journal name in source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Title of series: Lecture Notes in Computer Science
Volume number: 11091
ISBN: 978-3-030-01140-6
eISBN: 978-3-030-01141-3
ISSN: 0302-9743


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 onion garbling,
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 N computations is independent of N for the outsourcing party. For the other two parties, the memory and communication cost of N-reusability is proportional to N⋅m" role="presentation">N⋅m, where m 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 n
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.

Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.

Last updated on 2019-21-08 at 20:38