I can't trust you, but I can believe you

However good the security, any computer connected to the Internet is potentially open to attack. Premkumar Devanbu, Michael Gertz, Charles Martell and Phil Rogaway at the University of California, Davis, Computer Security Laboratory have come up with a system that lets exposed, "untrusted" machines go on providing useful, accurate information, even though they might have been infiltrated by hackers.

If you have a database of information, such as a customer database, the only way to be sure that no one breaks into the computer and changes entries is to have that machine locked in a vault with no connection to other computers, Devanbu said. But that means you can't access the data easily.

What you can do is put a copy of the database on an untrusted computer connected to the Internet, along with a digital signature from the "trusted" computer. Users of the database also get copies of the signature. When a user sends a query over the Internet to the database, it sends back the answer, plus a "proof" that guarantees that the answer has come from the correct database. Together, the answer and the proof should give a signature that can be compared to the original. If the database on the open computer has been tampered with, the proof will automatically be wrong.

The proof is derived from the database in such a way that it increases in size by one bit (a one or a zero) when the database doubles in size. Although the proof and the signature are both short, the number of possible combinations they can generate is enormous, making it very hard to forge a proof or signature that could be used to falsify data entries, Devanbu.

This system has important implications, Devanbu said. Essentially, anyone with a computer connected to the Internet could provide database services, as long as they had copies of the original database and signature. For example, stock market prices are provided by brandname Web sites such as Reuter's and Bloomberg. These companies go to great lengths to keep that data secure, and charge accordingly. But if security were not a problem, many more sites could host this publicly available information.

The project is funded by the National Science Foundation. Devanbu's laboratory is also studying ways to extend the signature standard for XML documents, to make it easier to query large documents and verify the answers with a single signature.

Media contacts:
-- Prem Devanbu, Computer Science, 530-752-7324, devanbu@ucdavis.edu

---

---