On Fri, 9 Jul 2004, Bill Stewart wrote:
At 01:44 PM 7/9/2004, Thomas Shaddack wrote:
Is it possible to write a database access protocol, that would in some mathematically bulletproof way ensure that the fact a database record is accessed is made known to at least n people? A way that would ensure that either nobody can see the data, or at least n people reliably know the record was accessed and by whom?
..
The obvious method for the first half of your problem is Shamir secret-sharing - n out of m people need to provide their information in order to access the data item (or its key.) That isn't necessarily an _efficient_ protocol for databases,
Better yet, you have the n sources provide pieces of a key which auto-expires after X days, that key is used to access the database rather than getting the data from n sources. Authenticating at random with n sources, each with a different key is also required. Store the data on some persistent, distributed stores... Bit Torrent comes to mind here.
I'm not convinced that the second half of your problem makes sense.
See above method and add some sort of log to it that automatically and anonymously publishes logs of access to it. So long as n>m/2 and at least n people are trustworthy it should work, right? Then, you also need a watcher app to reveal that access occured. This app downloads the logs of the hashes you're interested in, plus other random ones to prevent logging from revealing who is interested in what. Would also be nice if the hash for the data you're trying to watch/access changes with the date. That way if one user of the system is compromised, the compromisers can't figure out who the other parties accessing the same data are. But I'm not sure how you'd make it happen without tweaking the Bit Torrent client a lot, or writing a new one from scratch (invoking Not-Invented Here Syndrome).
Of course, even to use this requires that the application be designed in some manner where there's some kind of key that's needed to access the data, such as a mailbox that encrypts incoming mail with your public key. That doesn't prevent the secret police from forcing your mailbox company to reveal the information before encrypting it to you, but it does at least protect _old_ mail, unless n out of the m key escrow agents all cooperate.
A-Yup.
I don't know why you'd design a system like this when you could do it without the key escrow feature - am I missing something?
How else would you do it and still be able to know when something was read? ----------------------Kaos-Keraunos-Kybernetos--------------------------- + ^ + :"I find it ironic that, on an amendment designed to protect /|\ \|/ :American democracy and our constitutional rights, the /\|/\ <--*-->:Republican leadership in the House had to rig the vote and \/|\/ /|\ :subvert the democratic process in order to prevail" \|/ + v + : -- Rep. Sanders re vote to ammend the US PATRIOT ACT. -------------------------------------- http://www.sunder.net ------------