Accountable algorithms

Ed Felten argues that with modern cryptography it is possible to make randomized algorithms accountable (h/t Bruce Schneier). This means that the public can verify that the algorithm was executed correctly in a particular case even though the algorithm used random numbers to make it unpredictable.

Felten’s idea is to use one random number to achieve unpredictability and another random number to achieve randomness. The authority running the algorithm chooses the first random number (R) secretly and then commits it (the cryptographic equivalent of putting it in a tamper proof sealed envelope which will be opened later). Then, it chooses the second random number (Q) publicly (for example, by rolling the dice in public). The two random numbers are added and the sum (R + Q) is the input to the algorithm. Note that the public cannot verify that R was chosen randomly, but this does not matter because even if R is non random, R + Q is still random.

Felten’s examples are not from finance, but I find the finance applications quite fascinating. For example, the income tax department selects some individuals randomly for detailed scrutiny. Using Felten’s ideas, it is possible for the individual who is selected for scrutiny to verify that this scrutiny is a result of a genuine random selection and not because of the assessing officer’ bias. It is possible to do this without making the selection predictable.

As a second example, suppose a stock exchange wants to look at prices at random times because if fixed times are chosen, there is greater risk of the prices being manipulated. The random time must be unpredictable to participants. But after the fact, we want to be able to verify that the time was chosen randomly and that some exchange official did not deliberately choose a specific time “after the fact” with knowledge of the actual prices. Felten’s ideas can be used to solve this problem as well.

In a comment on his second post, Felten introduces even more interesting ideas. For a financial example, consider an organization which requires certain employees to take prior approval before trading stocks on personal account. Suppose the compliance officer disallows a trade on the ground that the particular stock is on a negative list of stocks that cannot be traded. How does the employee verify that the compliance officer is not lying if the list itself is secret? Felten’s method can be used to deal with this problem. The compliance officer should publicly announce the root hash of a Merkle tree containing the restricted list of stocks. This root hash by itself reveals nothing. Now the compliance officer can reveal a single path in the Merkle tree which allows the employee to verify that the stock in question is on the list. But this would not reveal anything about what else is on the list.

A lot of regulations are written assuming that the people implementing the regulation are honest. This assumption is clearly inappropriate. The Right to Information Act ensures only transparency; it does not guarantee accountability in the presence of randomization. We should require that all algorithms that are used during the implementation and enforcement of the regulations should be accountable in Felten’s sense.

Posted at 9:52 pm IST on Sat, 29 Sep 2012         permanent link

Comments