01-01-2013, 12:19 PM
Payments for Outsourced Computations
Payments for Outsourced Computations.pdf (Size: 599.84 KB / Downloads: 27)
INTRODUCTION
THE ability to execute large, compute intensive jobs, is no
longer the privilege of supercomputer owners. With the
recent advent of cloud computing and volunteer computing
initiatives, users can outsource their computations for
execution on computers with spare resources. Cloud computing
provides hardware (CPU and storage) capabilities,
along with software and electronic services, which clients can
elastically rent while abstracting from lower level details.
Motivated by the ability of computer owners to donate CPU
resources, volunteer computing takes advantage of the
parallelizable nature of several large compute problems to
distribute jobs to available computers over the internet.
In this work, we consider a general “compute market”
framework, encompassing the cloud and volunteer computing
paradigms: participating computers can act both as
service providers (workers) and as clients (outsourcers).
Outsourcers have computing jobs they cannot complete in a
timely fashion, whereas workers are willing to spend CPU
cycles to run parts of such jobs. While it is natural to
motivate participation through the use of financial incentives,
the distributed nature of the framework raises trust
questions: Outsourcers do not trust the workers to correctly
perform computations and workers do not trust outsourcers
to pay for completed jobs.
RINGERS—AN OVERVIEW
The solution from Golle and Mironov [9] (see Section 2.3
there) that we extend is called ringers. In this section, we
discuss ringers and how they are used to solve the problem
of the trust in W. O needs to be able to establish that W does
perform all the computations that were outsourced to him.
The idea behind ringers is to require the outsourcer to
select a small set of random input values from D and to
precompute the image of the function f on those values
(true ringers). Besides the image of interest, the outsourcer
sends to the worker also the true ringers. The worker needs
to retrieve the preimages of all the received images. In order
to prevent the worker from stopping the work after
inverting all but one image, the outsourcer uses bogus
ringers, which are values from the image of f that do not
have a preimage in D. If the worker is able to invert at least
the true ringers, the outsourcer is convinced that the worker
has completed a large percent of the job. The solution has
the following steps.
Solution Intuition
The purpose of the random R used during the payment
generation step is to bind obf ðtÞ to V. This proves that these
values were signed by B at the same time, preventing O
from using obf ðtÞ and V generated in different protocol
instances. While a value of format pðHðKi;RÞÞ from V
certifies the fact that B has seen the subkey Ki, a value of
format pðHðKi;R; ‘‘r’’ÞÞ also authenticates the fact that O
claimed that subkey to be a ringer, subkey of K, where K
obfuscates the payment . Note that B does not verify the
well formedness of the ringers K1; ::;Kk. This verification is
to be performed by the workers.
Following the job transmission step, W needs to generate
and verify challenges. Since B has generated the random R
value and has signed both obf ðtÞ and each key Kj; j ¼ 1::2m
with it, the challenge verification procedure allows W to
verify that each revealed element in the set V er is a payment
piece and any two revealed pieces belong to the same
payment instance (R binds SN, obf ðtÞ and all Kj values). O
cannot pretend that a challenged ringer subkey Kj is not a
ringer. This is because B has included the string “r” in its
signature of the subkeyKj. During the computation,W needs
to retrieve K1; ::;Kk, compute K, then recover from obf ðtÞ.
The bank signed value allows W to cash the payment.
PAYMENT THRESHOLD SPLITTING
Our second solution uses threshold sharing to address the
invalid share property. It splits the payment into 2m þ p
shares such that any 2m shares reconstruct the payment.
The outsourcer obfuscates a subset of the shares with a
small subset of the solution of the job to be performed.
Table 2 lists the notations we used in the solution. Fig. 1
illustrates our solution.
Setup. Let p and q be two security parameters,
c ffimffiffiffiffi
p
< p;q < m, for a constant c. Pick a symmetric key
K ,!R f0; 1gs. Instantiate a ð2m; 2m þ pÞ secret sharing
scheme (e.g., Shamir’s scheme [13]) such that any but not
less than 2m shares are required to compute the secret. Let
SS be the reconstruction function, that given any 2m or
more shares reconstructs the secret.
EXACT PAYMENT SPLITTING
The first two solutions are either vulnerable to the invalid
payment share or the premature payment reconstruction
properties and require heavy bank involvement. We now
propose a solution that addresses these concerns while
involving B only in the payment generation. Table 3 lists
our notations.
Setup. The bank, B, has the following:
. A trapdoor permutation, p; p1; d that is secure
from nonuniform polynomial time [8] adversaries.
The function p is public, and p1 is private to B.
. A generator, g 2 for a finite cyclic group, of order
q where q is prime. All of g, , and q are public. All
exponentiations of g are done modulo q; we omit the
“modq” qualification in our writing.