Law embedded in the world

Trying to beat the protocol can get you in trouble:

Confidential auditing

I once described how confidential auditing was possible and beneficial:

The auditing function is a vast and indispensable part of the modern economy. Auditing controls allow, among other things, employers to delegate resources and authority to employees, franchisors to delegate to franchisees, stockholders to delegate to management, advertisers to count eybeballs, marketers to gather more reliable data on customers, and make possible a wide variety of other such relationships. Auditing controls might fairly be called the security protocols of capitalism...[However,] auditing is in deep conflict with efforts towards greater privacy. Auditors have an ethic of recording, investigating, and reporting as much as possible, and often see privacy efforts as attempts to prevent auditing and potentially cover up fraud...[But confidential auditing is possible because] we can achieve auditing logs unforgeable after commitment via secure timestamps. We can then achieve to a great extent unforgeability prior to commitment, with segregation of duties via multiparty integrity constraints. We then audit these commitments via multiparty private computations.

In an article about multiparty secure (i.e. private) computations I described this process as follows:

Performance phase analysis with multiparty secure computer theory would seem to apply only to those contracts which can be performed inside the virtual computer. But the use of post-unforgeable auditing logs, combined with running auditing protocols inside the shared virtual computer, allows a wide variety of performances outside the virtual computer to at least be observed and verified by selected arbitrators, albeit not proactively self-enforced.

The participants in this mutually confidential auditing protocol can verify that the books match the details of transactions stored in a previously committed transaction log, and that the numbers add up correctly. The participants can compute summary statistics on their confidentially shared transaction logs, including cross-checking of the logs against counterparties to a transaction, without revealing those logs. They only learn what can be inferred from the statistics; [they] can't see the details of the transactions

In this I had been inspired by Eric Hughes' idea of encrypted open books. My sketch is more general insofar as it addresses pre-transaction forging (with separation of duties), post-transaction forging (with secure timestamping), and the auditing protocol itself (with multiparty private computation running off the logs themselves rather than Hughes' specialized protocol running off already prepared books).

But my description was only a proof-of-concept sketch that one could go all the way from preparing to transact to transaction log to finished audits while maintaining both integrity and privacy, with neither depending on large amounts of trust in the auditors. Recently Shen et. al. came up with a detailed design of such a confidential auditing scheme in the context of gathering statistics from the logs of distributed computations:

...no single TTP [trusted third party] node can have the full knowledge of the logs, and thus no single node can misuse the log information without being detected. On the basis of a relaxed form of secure distributed computing paragidms, one can implement confidential auditing service so that the auditor can retrieve certain aggregated system information e.g., the number of transactions, the total volume, the event traces, etc., without having to access the full log data...To prevent an unsupervised TTP from manipulating the system, we design query processing schemes that require TTP nodes work together, using the multiparty private computation, to perform any useful auditing functions.

Secure timestamping and confidential auditing

Another interesting protocol is cryptographic timestamping. The purpose is to prove that a particular piece of content (i.e. some array of bits) existed at a particular period of time. The basic idea goes back to the anagram publication technique that Robert Hooke, Galileo, and some other early scientists used to prove that they discovered certain things long before they published them. When Hooke, for example, discovered his law of elasticity, he published the gobbledygook letters "ceiiinosssttuv." Later, when he published his law of elasticity, he published "ut tensio sic vis" (as the extension, so with the force). The earlier published anagram proved that he had discovered this law long before he published it.

The modern protocol uses cryptographic hash functions instead of anagrams. Any set of bits (digital content, a network event, whatever) is passed through the hash function, turning into into a unique random-looking string of bits. Those bits are then published to multiple timestamp servers on the Internet. The timestamp servers create a chain of hashes. Using the chain of published hashes, it is easy to later prove that (1) the hash was published before one event and after another event, thus proving the time of publication, and (2) that the hash uniquely corresponds to a particular content.

Note that the content of the file does not need to be published until proof is needed. Thus, for example, one could digitally timestamp a secret digital inventor's notebook in order to prove later that the invention existed at that time. (Might be quite useful under the American first-to-invent system).

Indeed, using multiparty secure computation or the related protocols called zero-knowledge proofs, one can even make a later proof without publishing the content. For example, if Bob received a secret encrypted e-mail message from Alice, Alice and Bob could prove to the world that Alice sent a message at 18:42:39 and Bob received it at 18:43:05 without revealing the actual contents of the message. In a confidential audit of Alice's books based on securely timestamped transactions between Alice and Bob and Alice and Charles, performed using secure multiparty computation, Alice can prove to the auditor that her books balance based on real transactions with Bob and Charles, without revealing in unencrypted form to the auditor either the transactions or the books. Such is the magical reality of cryptography!

Here are some links to papers and other references on secure timestamping.