vealed, nothing stops the worker from
presenting the same labels as correct
for F(x′). Creating a new garbled circuit requires as much work as if the
client computed the function itself, so
on its own, Yao’s circuits do not provide an efficient method for outsourcing computation.
The second crucial idea is to combine Yao’s Garbled Circuit with a fully
homomorphic encryption system
(such as Gentry’s7) to be able to reuse
the garbled circuit safely for multiple
inputs. More specifically, instead of
revealing the labels associated with
the bits of input x, the client encrypts
those labels under the public key of
a fully homomorphic scheme. A new
public key is generated for every input
in order to prevent information from
one execution from being useful for
later executions. The worker then uses
the homomorphic property to compute an encryption of the output labels
and provide them to the client, which
decrypts them and reconstructs F(x).
Even without secure hardware,
these results demonstrate a user’s
trust in one device can be leveraged to
verify (and hence trust) the results of
computations performed by any number of remote, untrusted commodity
computers.
Conclusion
Motivated by the trend toward en-
trusting sensitive data and services to
insecure computers, this article has
described techniques to enable us-
ers to extend their trust in one device
to other devices or services. Starting
from trust in a simple USB device, us-
ers can verify the reports from secure
hardware on their computer, then se-
curely execute code on that computer,
despite the presence of a mountain of
untrustworthy code, while the untrust-
ed code continues to enjoy the perfor-
mance and features it does already.
Efficiently extending the trust in this
secure environment into the network
improves the security of a range of net-
work protocols. Finally, the user’s trust
is extended to the verification of com-
putations performed by remote com-
puters, even though they may be arbi-
trarily malicious. Many people using
computers and online services today
only imagine their data and privacy are
protected. In the long run, the ability to
bootstrap trust in these computers and
services will help replace this illusion
with the actual foundation of security
users expect and deserve.
Acknowledgments
This article is based on my Ph.D. dissertation,
21 though much of the research it describes was conducted in
collaboration with my advisor Adrian
Perrig at Carnegie Mellon University, as well as with Hiroshi Isozaki,
Jonathan McCune, Mike Reiter, and
Arvind Seshadri;
16–18 Zongwei Zhou;
24
and Craig Gentry and Rosario Gennaro.
6 I am extremely grateful for their
contributions. This article also benefited from feedback from Jay Lorch,
Jonathan McCune, Diana Parno, and
Adrian Perrig.
References
1. advanced Micro devices. AMD64 Architecture
Programmer’s Manual. aMd Publication no.
24593, rev. 3. 14, 2007; http://support.amd.com/us/
Processor_techdocs/24593_aPM_v2.pdf
2. ames, Jr., s.r. security kernels: a solution or a
problem? In Proceedings of the IEEE Symposium on
Security and Privacy (oakland, Ca, apr. 27–29). Ieee
Computer society. los alamitos, Ca, 1981, 141.
3. anderson, d.P. boInC: a system for public-resource
computing and storage. In Proceedings of the IEEE/
ACM Workshop on Grid Computing (Pittsburgh, Pa,
nov. 8). Ieee Computer society, los alamitos, Ca,
2004, 4–10.
4. barham, P., dragovic, b., Fraser, k., Hand, s., Harris, t.,
Ho, a., kotsovinos, e., Madhavapeddy, a., neugebauer,
r., Pratt, I., and Warfield, a. Xen 2002. technical
report uCaM-Cl-tr-553, university of Cambridge,
Cambridge, u.k., Jan. 2003.
5. Garriss, s., Cáceres, r., berger, s., sailer, r., van
doorn, l., and zhang, X. trustworthy and personalized
computing on public kiosks. In Proceedings of the
Conference on Mobile Systems, Applications, and
Services (breckenridge, Co, June 17–20). aCM Press,
new york, 2008, 199–210.
6. Gennaro, r., Gentry, C., and Parno, b. non-interactive
verifiable computation: outsourcing computation
to untrusted workers. In Advances in Cryptology:
Proceedings of the 30th International Cryptology
Conference (santa barbara, Ca, aug. 15–19, 2010),
465–482.
7. Gentry, C. Fully homomorphic encryption using ideal
lattices. In Proceedings of the 41st ACM Symposium
on Theory of Computing (bethesda, Md, May 31–June
2). aCM Press, new york, 2009, 169–178.
8. Gold, b.d., linde, r.r., and Cudney, P. F. kVM/370 in
retrospect. In Proceedings of the IEEE Symposium
on Security and Privacy (oakland, Ca, apr. 29–May
2). Ieee Computer society, los alamitos, Ca, 1984,
13–23.
9. Hao, s., syed, n.a., Feamster, n., Gray, a. G., and
krasser, s. detecting spammers with snare: spatiotemporal network-level automatic reputation engine.
In Proceedings of the USENIX Security Symposium
(Montréal, aug. 10–14). usenIX association,
berkeley, Ca 2009, 101–118.
10. Intel Corp. Intel Trusted Execution Technology:
Measured Launched Environment Developer’s Guide.
document no. 315168-005, santa Clara, Ca, June
2008.
11. karger, P.a., zurko, M.e., bonin, d. W., Mason, a.H., and
kahn, C.e. a retrospective on the VaX VMM security
kernel. IEEE Transactions on Software Engineering 17,
11 (nov. 1991), 1147–1165.
12. klein, G., elphinstone, k., Heiser, G., andronick, J.,
Cock, d., derrin, P., elkaduwe, d., engelhardt, k.,
norrish, M., kolanski, r., sewell, t., tuch, H., and
Winwood, s. sel4: Formal verification of an os kernel.
In Proceedings of the ACM Symposium on Operating
Systems Principles (big sky, Mt, oct. 11–14). aCM
Press, new york, 2009, 207–220.
Bryan Parno ( parno@microsoft.com) is a researcher in
Microsoft research, redmond, Wa.
© 2012 aCM 0001-0782/12/06 $10.00
