Incoercibility

Today I attended a rather interesting talk at Crypto 2010 by Dominque Unruh on the paper Universally Composable Incoercibility by D. Unruh and J. Müller-Quade.

Incoercibility is typically studied in the setting of voting systems. For example, say you vote in an election where you are issued with a receipt saying who you voted for. You want to vote for Charlie, but an adversary forces you to vote for Alice, demanding you show the receipt to them afterwards as proof. In this environment you can be coerced, unless of course you can produce a fake voting receipt. Although voting systems are the most studied, there are other situations where incoercibility may be a requirement; this is relevant whenever a protocol leaves traces of its actions. The question of course is how do we analyse this and are there any models to allow us to do this? Unrue and Müller-Quade introduce a general model for this under the universal composability framework.

Briefly, the universal composability framework has two worlds. In the real world, there exists an adversary who interacts with parties participating with the real protocol. The ideal world has a simulator who simulates the actions of the real world adversary, interacting with parties who use an ideal functionality, as opposed to the real protocol. If for all adversaries there exists a simulator then the two worlds are equivalent assuming no environment can distinguish with which world it interacts.

How could you model this incoercibility requirement? One way might be to have the following two worlds:

(1) The adversary coerces a party, and this coerced party simply forwards messages backwards and forwards between the protocol and the adversary.

(2) The adversary interacts with an un-coercible party who does what he wants, not what the adversary wants (while interacting with the protocol).

If these two worlds were indistinguishable, then one might expect us to have the desired result. However this fails. For example, say you have an election with only one voter, then the vote tally will reveal which world you are in.

So the best result that can be achieved is that "every lie possible in the ideal setting should be possible in the protocol setting". Without going into the details, Unruh and Müller-Quade achieve this in the following way. In the ideal world a "Deceiver" party is introduced. Typically an adversary corrupts a party and completely controls that party, but with the addition of the Deceiver, if the Deceiver controls a corrupted party, then this party behaves as demanded by the Deceiver and not the adversary (unbeknown to the adversary). This method then leads to the useful result that any attack possible in the real world is possible in the ideal world, and any lie possible in the ideal world is possible in the real world.