Forcing an honest behavior

Question

How can you force a party to be honest (obey protocol rules)?

I have seen some mechanisms such as commitments, proofs and etc., but they simply do not seem to solve the whole problem. It seems to me that structure of the protocol design and such mechanisms must do the job. Does any one have a good classification of that.
Edit
When designing secure protocols, if you force a party to be honest, the design would be much easier though this enforcement has its own pay-off. I have seen when designing secure protocols, designers assume something which does not seem realistic to me, for instance to assume all the parties honest in worst case or assuming honesty of server which maintains user data. But when looking at design of protocols in stricter models, you rarely see such assumptions (at least I haven't seen it - I mostly study protocols over UC framework of Canetti which I think it is not totally formalized yet). I was wondering, is there any good classification of the ways in which you can force a party to be honest or is there any compiler which can convert the input protocol to one with honest parties?
Now I am going to explain why I think this merely does not do the job though it may seem irrelevant. When designing protocols in the UC framework, which benefits from ideal/real paradigm, every communication link in the ideal model is authenticated, which is not true in the real model. So protocol designers seeks alternative methods to implement this channel through means of PKI assumption or a CRS (Common Reference String). But when designing authentication protocols, assuming authenticated channels is wrong. Suppose that we are designing an authentication protocol in the UC framework, there is an attack in which adversary forges identity of a party, but due to assumption of authenticated links in the ideal model this attack is not assumed in this framework! You may refer to Modeling insider attacks on group key exchange protocols. You may notice that Canetti in his seminal work Universally composable notions of key exchange and secure channels mentions a previous notion of security called SK-Security which is simply enough to assure security of authentication protocols. He somehow confesses (by stating that this is the matter of technicality) that UC definition in this context is too restrictive and provides a relaxed variant called non-information oracle (which confused me, cause I haven't seen this model of security any where, I cannot match this security pattern with any other security pattern, probably my lack of knowledge :D).

[As a side note, You can nearly have any Sk-secure protocol converted to a UC secure one regardless of simulator time. For instance you may just remove the signings of the messages and have the simulator simulate the whole interactions in dummy way. See Universally Composable Contributory Group Key Exchange for proof! Now suppose this is a group key exchange protocol with polynomially many parties, what would be the efficiency of the simulator?? This is the origin of my other question in this forum.]

Anyway, due to lack of commitment in the plain model (over UC), I sought other means to make the protocol secure by just bypassing the need for that relaxation. This idea is so very basic in my mind and has come to my mind by just having studied latest commitment scheme of canetti in the plain model: Adaptive Hardness and Composable Security in the Plain Model from Standard Assumptions.
BTW, I don't seek zero-knowledge proofs because due to reason which I don't know, whenever someone has used one of them in a concurrent protocol (over UC framework), the others has mentioned the protocol as inefficient (may be due to rewinding of the simulator).

Answer 1

Alas, you can't force people to do what the protocol says they should do.

Even well-meaning people who intended to follow the protocol occasionally make mistakes.

There seem to be at least 3 approaches:

• crypto theory: assume "good" agents always follow the protocol, while "malicious" agents try to subvert the protocol. Design the crypto protocol such that good agents get what they need, while malicious agents get nothing.
• game theory: assume every agent looks out only for his own individual interest. Use mechanism design to maximize the total benefit to everyone.
• distributed fault-tolerant network: assume every agent makes an occasional mistake, and a few 'bot agents spew out many maliciously-crafted messages. Detect and isolate the 'bot nodes until they are fixed; use error detection and correction (EDAC) to fix the occasional mistake; use convergent protocols that eventually settle into a useful state no matter what initial mis-information is stored in the routing tables.

mechanism design In game theory, designing a situation (such as setting up the rules of an auction) such that people who are selfishly looking out only for their own individual interests end up doing what the designer wants them to do is called "mechanism design". In particular, using implementation theory, situations can be designed such that the final outcome maximizes the total benefit to everyone, avoiding poorly-designed situations such as the "tragedy of the commons" or "prisoner's dilemma" where things happen that are not in anyone's long-term interest.

Some of the most robust such processes are designed to be incentive compatible.

The game theory typically makes the simplifying assumption that all relevant agents are "rational". In game theory, "rational" means that an agent prefers some outcomes to other outcomes, is willing and able to change his actions in a way that he expects (given the information available to him) will result in a more preferred outcome (his own narrow self-interest), and he is smart enough to realize that other rational agents will act similarly to try to obtain the outcome that is most preferred out of all the possible outcomes that might result from that choice of action.

A designer may temporarily make the simplifying assumption that all people only act according to their own narrow self-interest. That assumption makes it easier to design a situation using implementation theory. However, after the design is finished, it doesn't matter whether people act according to their own narrow self-interest ( "Homo economicus" ), or whether they are altruistic and want to maximize the total net benefit to everyone -- in a properly designed situation, both kinds of people make exactly the same choices and the final outcome maximizes the total benefit to everyone.

convergent protocols

When designing a routing protocol, each node in the network sends messages to its neighbors passing on information about what other nodes are reachable from that node.

Alas, occasionally these messages have errors. Worse, sometimes a node is mis-configured and spews out many misleading and perhaps even maliciously-crafted messages.

Even though we humans know the message might be incorrect, we typically design the protocol so that a properly-functioning node trusts every message and stores the information in its routing table, and makes its decisions as if it believes that information to be entirely true.

Once some human turns off a bad node (or disconnects it from the network), we typically design the protocol to rapidly pass good information to flush out the corrupt information, and so quickly converge on a useful state.

combined approaches

Algorithmic mechanism design seems to try to combine the fault-tolerant network approach and the game-theory mechanism approach.

@Yoichi Hirai and Aaron, thank you for pointing out some interesting attempts to combine game theory and cryptography.

Answer 2

Joe Halpern has a slide on that topic. http://games2009.dimi.uniud.it/Halpern.pdf

This is about giving incentives to parties so that they follow a protocol. Those mechanisms require rationality of the parties and the arguments are based on game theory.