"Kent Hastings" says:

ADICO: Anarchist FDIC#000# When someone objects to free banking (in gold, for example) on the grounds that unregulated banks will have fractional reserves and have no incentive to stay honest, perhaps describing an Anarchist Deposit Insurance COmpany (ADICO) will ease their fears.

A new or relatively obscure offshore bank would gain the trust of potential depositors by agreeing to cooperate with surprise inspections of their gold supply. Depositors would pay a small premium to cover loss from bank failures due to theft or fraud.

Cryptographic protocols would need to be developed to allow the ADICO to see a verified total amount on deposit, without revealing anything about any particular depositor. The total should match the physical amount of gold in storage, assuming 100% reserves.

Does anybody know of work on this, or think it is worth researching?

Good job -- you have come up with a very interesting problem indeed. A cryptographic protocol that permitted an outsider to determine the amount of (pick your favorite) on deposit without requiring that the bank reveal who owns what would be a neat trick. I suspect, based on some of the voting protocols people are coming up with, that it might in fact be possible, although it might end up involving an outside auditing agency in many of the transactions. Whether a practical protocol to permit this to be done would be possible is an extremely interesting research topic -- many of the voting protocols I've heard of are quite impractical if you have millions of voters. To my knowledge, nothing to solve what I will now dub the "Anonymous Auditing Problem" has yet been done, and this is the first time the question has been posed. Perry

Kent Hastings wondered how an offshore bank could provide assurances to depositors. I wondered the same thing a few months ago, and started working on what Perry calls the anonymous auditing problem. I have what I consider to be the core of a solution. All the following protocols and ideas are in the public domain. The following is long. My notation here will also be much less formal than I am capable of; I don't want to make the uninitiated read TeX. The basic idea is that summation can be performed encrypted by using exponentiation in a finite field. That is, if I represent an amount x by g^x and an amount y by g^y, then I can compute the sum of x and y by multiplying g^x and g^y, getting g^(x+y). Very basic. So let us take a very simple version of this protocol, which leaves out many desiderata. If a shared funds account, say, has a bunch of transactions made on it, then we can publish each of those amounts x_i (for the non-TeX'd, underscore means subscript) encrypted as g^(x_i). I know what my transaction number, i, is, and what the amount was, so I can verify that my transaction appeared in the public list. We also publish the beginning and ending balances, givings use a total difference X. Now anyone can verify that g^X equals g^(Sum_i x_i). That is, everyone can verify that the aggregate effect of the transactions is what is claimed without revealing the amounts of any of them. What does this protocol reveal? It reveals the number of transactions on each account and thus the total number of transactions. It is also subject to known plaintext attack. If I get an account on this system and make one transaction in each amount, I can decrypt by table lookup the whole transaction flow. The total number of transaction accounts is also revealed, or, for a bank, the number of customers. We can easily solve the known plaintext attack by blinding each transaction. Instead of publishing pairs <i, g^(x_i)>, we have for each transaction a blinding factor r_i and publish triples <i, g^(x_i + r_i), h^(r_i)> The notation has grown. g is a generator of a finite field G, and h is a generator of a different finite field H. We also publish R = Sum_i r_i in addition to X = Sum_i x_i. What is the public verification procedure? Basically the same as the first case, but in addition taking into account the blinding factors. Step 1. Calculate Product_i h^(r_i) and make sure that it equals h^R. This validates the blinding factors. Step 2. Calculate Product_i g^(x_i + r_i) and make sure that it equals g^(X+R). This, given the validity of the blinding factors, validates the actual transactions. How does this resist known plaintext attack? Since the blinding factors r_i are flatly distributed over their range (caveat! you pick the order of G smaller than of H to assure this), the x_i + r_i sum acts exactly as a one-time pad to encrypt the amount. In summary, what is going on here is that both the messages (amounts) and the keys (the blinding factors) are being sent out as images of one-way functions (exponentiations) that preserve exactly the relationships that we want. There's more. For a real business, we want to keep double entry books and not just single entry accounts as above. By extending the number of terms in the transaction, we can do that too. In double entry bookkeeping, the total amounts for each transaction must sum to zero over the various accounts being transacted upon; I say this knowing that when you print out the information for an accountant you'll have to do some sign twiddling for the asset and liability/equity halves of the books. Also, a single transaction may involve more than two accounts, even if in practice most involve only two. The basic idea here is that each transaction is a set of the above transactions whose sum must be zero. So for a transaction i, we publish a set of triples, indexed by j, < T_i,j, g^( m_i,j + r_i,j ), h^( r_i,j ) > where the subscripts are doubly indexed and where T_i,j represents the account that amount m_i,j is changing. Now we can perform, on each transaction, the following very similar verification procedure for each fixed i. Step 1. Verify that Product_j h^( r_i,j ) = 1. This verifies that the blinding factors sum to zero. Step 2. Verify that Product_j g^( m_i,j + r_i,j ) = 1. Since the blinding factors sum to zero, this ensures that the transaction amounts sum to zero. Not that both of these sums are done over j, not i. In other words, we validate each transaction individually. Now we also publish aggregate changes in the public accounts just as before. The holders of private accounts know what how their accounts have changed. Then we can use the the single account verification method as above to verify that the totals match. Everyone can verify that the public accounts match, and the holders of private accounts can verify that they match. To summarize: The transactions are doubly indexed. If you group by transaction, then you verify that each transaction sums to zero. If you group by account, then you verify that the change in that account is as expected, be it public or private. In the scenario that Kent originally proposed, one of the public accounts would be a gold account, which through independent public auditing would be verified to be accurate. I personally would not use gold but rather denominate certain accounts in shares of mutual funds, which are resistant to the currency inflations of mining and stockpile sales. What information is still being disclosed? The most worrisome to me is that the total number of transactions per account is revealed, that is, aggregate activity, but not total money flux. I have an insight that may allow the _account_ to be blinded as well as the amounts, and be revealed in aggregate just as the amounts are, but I have not worked out the details because I am not fully up to speed on the relevant math. BEGIN BIG MATH I only expect a few people to follow the next paragraphs, so if you don't understand it, skip it. Here's the idea. The modular exponentiation is performed in a finite ring. We choose a ring that has lots of distinct prime ideals of sufficiently large order. To each account we assign one ideal. We represent dollar amounts as elements of this ideal; since the ideal is prime, this is straightforward. The property of the ideal we use is that the sum of any two elements of the ideal is also in the ideal. Hence by partitioning the ring, we also partition the computation of the accounts. We are blinding the transcations by account because we rely on the fact that blinding is not an intra-ideal operation, and thus does not preserve that invariant, which would otherwise be public. We must be careful not to allow operations that would result in an element which was in the intersection of two ideals. This requires upper bounds both on the transaction amount and on the number of transactions per cycle. There might be rings of order p^n+1 which would be suitable for this operations, but I am not sure of the security of the discrete log in such cases, except for p=2, in which case it is bad. END OF BIG MATH The protocol as specified, though, is useful as it stands. I have not specified all the details. For example the blinding factors should likely be created in a cooperative protocol at the point of transaction; blinding factors for intra-bank transactions should not contain subliminal channels. Certificates of deposit and withdrawal should be tied to the published transaction information. Etc. Remember, this is the core of an idea. One criticism I do wish to address now. I don't think it matters if the bank manufactures fake transactions. The customer can reveal the sum of all the blinding factors for transactions on that account, in public, and can thus prove what should have been there. Since the blinding factors were committed to in public, there is a strong assurance that these blinding factors are what they are claimed to be. This in itself can be made into an actual proof of liability. Note that even this revelantion does not compromise individual transactions. It only reveals the aggregate value change, which is exactly what is at issue with the bank. On the other hand, all of the bank assets that are held external to that organization can be externally audited in the same way. The other institutions that hold money might be persuaded to undertake a legal obligation to honor what the encrypted open books say they should have; this may not be difficult because they can verify that their record of the transactions matches what has been published. If we use the contents of the encrypted books at the organizational boundary points to create suitable legal opbligations, we can mostly ignore what goes on inside of the mess of random numbers. That is, even if double books were being kept, the legal obligations created should suffice to ensure that everything can be unwound if needed. This doesn't prevent networks of corrupt businesses from going down all at once, but it does allow networks of honest businesses to operate with more assurance of honesty. Eric