protected on unlocked Web sites
Technology Research News
Looking up information on the Internet
is easy, but is it sometimes too good to be true? How do you know that
a posted investment history, for instance, is correct and complete?
Existing technology allows an author to use a digital signature to authenticate
a document. The author signs the document using a private key program,
which performs a mathematical calculation on the document. To view the
signature, the reader downloads the authors public key, which can be posted
in a publicly available place.
But existing signature schemes only work with specific sets of data. To
request the last two years of that investment history, for example, you
might have to download the entire record to get an authenticated copy.
A team of researchers has come up with a signature scheme that allows
portions of signed documents that are stored in Extensible
Markup Language (XML) databases to be retrieved and authenticated.
"The existing XML signature standard won't let you do that. You can only
authenticate an entire document, not parts of it," said Premkumar Devanbu,
an associate professor of computer science at the University of California
Using the researchers' TruthSayer scheme, an author can also sign an XML
document and give it to someone else to store and post, said Devanbu.
In other words, the author would not have to be the publisher in order
to authenticate the material. This means that anyone, from a government
agency to the Mafia, could have a Web
site that published authenticated data from multiple sources, and
the receiver would be able to verify the origin of the documents, Devanbu
When the originator of the data uses the scheme to sign a document, the
system processes the data involved, including its indexes, which are pieces
of software that handle queries from clients and speed up searches, said
Devanbu. "Typically, only a tiny fraction... of these indexes need to
be looked at to answer the client's query. It is actually this index that
is digested in a special way, to compute the database signature in our
scheme," he said.
The secure data is then sent to an untrusted publisher; "When the publisher
gets a signed [answer] from the owner, he checks to see if that's right
using the owner's public key," said Devanbu. When anyone queries the data,
the publisher provides the response and a verification code to prove that
the accompanying answer is accurate and complete, he said.
When an untrusted online site gets a client query, it searches through
the indexes, keeping track of which parts of the index were searched,
and returns those parts along with the answer, Devanbu said. "The client
now runs a [verification] program over the answer [and] the returned parts
of the index."
The verification program compares the publicly available author's key
with the publisher's certificate. "The critical thing about the verification
[code] is that it doesn't depend on any keys at all. It uses a... digesting
operation to prove that the answer that was sent by the publisher was
the same as the answer the owner would have given," said Devanbu.
If the comparison proves a match, the client knows the data has not been
compromised. If there is a discrepancy, she knows the data has been changed
by someone other than the author.
"If a bad guy replaces a publisher's copy of the owner's public key with
a forged public key, then the bad guy can make the publisher trust an
invalid root hash value, and deceive the publisher into publishing bad
data," said Devanbu. "But as long as the clients have the correct copy
of the owner's public key, they won't believe this deceived publisher."
To digest documents, the signature system uses the Merkle hash tree mathematical
function. The function starts with a set of data and computes until there
is only one root value left, which is the key the author uses when he
signs a document, said Devanbu.
The scheme could be used to retrieve authenticated portions of published
data, from traffic citations and court proceedings to Freedom of Information
Act requests, "all of which are either already or soon will be in XML,"
said Devanbu. In short, "any situation where correctness of data and efficiency
of access is important."
"Suppose the government signs a large XML document containing all discussions
within the Department of Labor on some topic, and gives it to another
agency to handle responses to FOIA queries," said Devanbu. "Someone in
the Department of Labor who wanted to hide something might try to coerce
the person at the agency handling FOIA queries to hide some details in
responses to queries. With [Truthsayer,] a false or incomplete answer
to queries on the XML document would be detected immediately," he said.
Another advantage of this encryption scheme is that the owner of the data
does not have to be online. "If the owner is physically disconnected,
he cannot be hacked, and no one can steal his private key. So his signature
is not forgeable," said Devanbu. This type of system is called an 'air
gap' and is used by many Defense Department systems, he said.
This work is elegant and efficient and could spur further developments
in this area, said Andrew Odlyzko, a professor of mathematics and the
director of the Digital Technology Center at the University of Minnesota.
The most important feature of this scheme is that it could "provide authenticated
information access through untrusted intermediaries," Odlyzko said. People
might, however, opt for simpler solutions than this one because the threat
the authors scheme guards against is probably not all that serious, he
The researchers are getting ready to test the scheme with a realistic,
open-source database system, said Devanbu. It could be ready for practical
use in 4 to 6 years, he said.
Devanbu's research colleagues were Michael Gertz, April Kwong, Chip Martel,
Glen Nuckolls, and Philip Rogaway from the University of California at
Davis, and Stuart G. Stubblebine of Stubblebine Consulting, LLC.
They presented the research at the 8th ACM Conference on Computer and
Communications Security held in Philadelphia between November 5 and 8,
2001 and is scheduled to be published in the Computer Security Journal,
2001. The research was funded by the National Science Foundation (NSF),
and the Defense Advanced Research Project Agency (DARPA).
Timeline: 4-6 years
TRN Categories: Cryptography and Security; Internet; Databases
and Information Retrieval
Story Type: News
Related Elements: Technical paper, "Flexible Authentication
of XML Documents," in the 8th ACM Conference on Computer and Communications
Security in Philadelphia, November, 2001; Technical paper, "Authentic
Re-Publication by Untrusted Servers: A Novel Approach to Database Survivability,"
presented at the Third Information Survivability Workshop 2000, October
24-26, 2000, in Boston.
LED fires one photon
at a time
Chips turn more heat
on unlocked Web sites
Surgeons gain ultrasonic
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link