age,” a paper published earlier this year, researchers Seny Kamara and Kristin Lauter of Microsoft Research described a virtual private storage service that aims to provide the security of a private cloud and the cost savings of a public cloud. Data in the cloud remains encrypted, and hence protected from the cloud provider, court subpoenas, and the like. Users index their data, then upload the data and the index, which are both encrypted, to the cloud. As needed, users can generate tokens and credentials that control who has access to what data.

Given a token for a keyword, an authorized user can retrieve pointers to the encrypted files that contain the keyword, and then search for and download the desired data in encrypted form. Unauthorized observers can’t know anything useful about the files or the keywords.

The experimental Microsoft service also offers users “proof of storage,” a protocol by which a server can prove to a client that it did not tamper with its encrypted data. The client encodes the data before uploading it and can verify the data’s integrity at will.

Not all cloud security risks arise from technology, says Radu Sion, a computer science professor at Stony Brook University. There is scant legal or regulatory framework, and few precedents, to deal with issues of liability among the parties in cloud arrangements, he notes. “What happens

in “cryptographic
cloud storage,”
microsoft
researchers seny
Kamara and Kristin
Lauter describe
a virtual private
storage service that
provides the security
of a private cloud
and the cost savings
of a public cloud.

when your data is on a server in China
but you outsourced to a cloud service
in New York?” asks Sion. “Or what if
you have the legal resources to fight a
subpoena for your data, but they sub-
poena your cloud provider instead?
You will be under scrutiny for moving
to the cloud by your shareholders and
everyone else.”
Nevertheless, Sion says all but the
most sophisticated enterprises will
be safer putting their computing re-
sources in the expert hands of one of
the major cloud providers. “Compa-
nies like Google and Amazon and Mi-
crosoft have hundreds of people de-
voted to security,” he says. “How many
do you have?”

Further Reading

Christodorescu, M., Sailer, R., Schales, D.,
Sgandurra, D., and Zamboni, D.
Cloud security is not (just) virtualization
security, Proceedings of the 2009 ACM
Workshop on Cloud Computing Security,
Chicago, IL, nov. 13, 2009.
Gentry, C.
Fully homomorphic encryption using ideal
lattices, Proceedings of the 41st Annual
ACM Symposium on Theory of Computing,
Bethesda, MD, May 31–June 2, 2009.
Kamara, S. and Lauter, K.
Cryptographic cloud storage, Proceedings
of Financial Cryptography: Workshop on
Real-Life Cryptographic Protocols and
Standardization, Tenerife, Canary Islands,
Spain, January 25–28, 2010.
Ristanpart, T., Tromer, E., Sacham, H.,
and Savage, S.
hey, you, get off of my cloud: exploring
information leakage in third-party
compute clouds, Proceedings of the
16th ACM Conference on Computer and
Communications Security, Chicago, IL,
nov. 9–13, 2009.
Shi, E., Bethencourt, J., Chan, T-H., Song, D.,
and Perrig, A.
Multi-dimensional range query over
encrypted data, Computer Science
Technical Report CMU-CS-06-135R,
Carnegie Mellon University, March 2007.

Gary Anthes is a technology writer and editor based in arlington, Va.

© 2010 acm 0001-0782/10/1100 $10.00

Distributed;Computing
Math at Web Speed

“Many hands make light work,” goes the old adage. Now there’s data to prove it.

In recent weeks, both yahoo! and google have announced the results of separate mathematical experiments that demonstrate the computational power of large clusters of networked PCs.

at yahoo!, a team led by researcher Tsz-Wo Sze broke the world record for calculating the digits of pi, crunching the famously irrational number to the two-quadrillionth bit by stitching together more than 1,000 computers to complete the calculation over a 23-day period.

The researchers estimate that a typical computer would have taken at least 500 years to carry out the same operation.

another group of researchers recently took advantage of google’s distributed computing infrastructure to tackle another famously thorny computational challenge: rubik’s Cube. The team developed an algorithm capable of solving any rubik’s Cube configuration in 20 moves or less, resolving a conundrum that has puzzled mathematicians for three decades. The computers simulated all 43 quintillion

possible combinations of the cube in just a few weeks, a task the researchers estimate would have taken a single computer 35 years.

google has yet to release the details of its technical solution, but it probably bears some resemblance to the approach used at yahoo!, where the team used apache hadoop, open-source software originally developed at google (and later developed extensively by yahoo!) that allows developers to stitch together thousands of computers over the network into a powerful cloud computer.

“We believe that our hadoop clusters are already more powerful than many other supercomputers,” says Sze, who conceived of the project as part of an internal yahoo! contest to demonstrate the capabilities of hadoop.

In both cases, the mathematical problems proved particularly well-suited to distributed computing because the calculations can be parceled out over the network into much smaller operations, capable of running on a standard-issue PC. Making light work indeed.

—Alex Wright