Cryptology ePrint Archive: Report 2014/439

Efficient Non-Interactive Verifiable Outsourced Computation for Arbitrary Functions

Chunming Tang, Yuenai Chen

Abstract: Non-interactive verifiable outsourced computation enables a computationally weak client to outsource the computation of a function $f$ on input $x$ to a more powerful but untrusted server, who will return the result of the function evaluation as well as a proof that the computation is performed correctly. A basic requirement of a verifiable outsourced computation scheme is that the client should invest less time in preparing the inputs and verifying the proof than computing the function by himself.

One of the best solutions of such non-interactive schemes are based on Yao's garble circuit and full homomorphic encryption, which leads to invest $poly(T)$ running time in offline stage and $poly(log T)$ time in online stage of the client, where $T$ is the time complexity to compute $f$.

In this paper, we'll present a scheme which does not need to use garble circuit, but to use a very simple technique to confuse the function we are going to compute, and only invests $poly(log T)$ running time in the offline stage.

Category / Keywords: cryptographic protocols / cloud computing, non-interactive outsourced computation, verifiable outsourced computation, full homomorphic encryption

Date: received 7 Jun 2014

Contact author: chenyuenai at 163 com; ctang@gzhu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20140612:033853 (All versions of this report)

Short URL: ia.cr/2014/439

Discussion forum: Show discussion | Start new discussion