9
$\begingroup$

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).

$\endgroup$
  • 2
    $\begingroup$ You may take a look at this: wisdom.weizmann.ac.il/~oded/gmw2.html. In that paper, dishonest parties are forced to act honestly by proving (in zero knowledge) that they followed the protocol in the previous step. $\endgroup$ – M.S. Dousti Dec 4 '10 at 12:30
  • 4
    $\begingroup$ I think that "forcing honest behavior" is possible definition for modern cryptography (which is more than just hiding information). In that case, every sub-area of cryptography can be considered as an approach to that question. $\endgroup$ – Marc Dec 4 '10 at 12:49
  • $\begingroup$ I was about to write the same thing as Marc. (By the way, interactive proofs or even the definition of NP can be also viewed as “forcing an honest behavior” on the prover, although they are not usually considered as cryptographic protocols.) The question is really broad, and there seems to be no one-size-fits-all way to enforce an honest behavior in various situations. $\endgroup$ – Tsuyoshi Ito Dec 4 '10 at 13:36
  • 1
    $\begingroup$ What do you precisely mean by "but they simply do not seem to solve the whole problem?" Could you be more specific? $\endgroup$ – Alon Rosen Dec 4 '10 at 20:22
  • $\begingroup$ @Sadeq: See the last paragraph! @Marc & Tsuyoshi lto: Please see the Edit section. it may help. $\endgroup$ – Yasser Sobhdel Dec 5 '10 at 7:07
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Here's a related paper to go along with the slides: theory.stanford.edu/~vteague/STOC04.pdf -- This approach doesn't "force" people to follow the protocol, but tries to design the protocol to incentivize individuals to want to do so. Of course, to do this, you have to make some assumptions about what exactly the people following the protocol want to do... $\endgroup$ – Aaron Roth Dec 4 '10 at 23:08
  • $\begingroup$ if possible could you explain what 'rational' means in this context? for example does it mean adherence to an underlying global set of axioms? or does it mean that the involved parties share the same set of underlying axioms? the former explanation strikes me as absurd in any real-world scenario, as individuals often have wildly different underlying motivations, and thus may be expected to treat 'incentives' in very different ways. $\endgroup$ – s8soj3o289 Dec 5 '10 at 8:05
  • $\begingroup$ @blackkettle: a rational player maximizes (the expectation of) a utility function. for the reason you point out, it's always a struggle to come up with the right axioms that utilities need to satisfy. but we always try for the minimal set of axioms. any good microeconomics books would go into detail about this issue $\endgroup$ – Sasho Nikolov Jun 14 '11 at 16:47
  • $\begingroup$ @blackkettle: about the Halpern paper: he assumes that parties in the (secret sharing) protocol prefer knowing the secret to not knowing it, and prefer that fewer rather than more other parties know the secret. also the notion of equilibrium he uses is Nash equilibrium over undominated strategies (i.e a player would not play a strategy if another is always at least as good; also, as long as other players don't change their strategies and her current strategy is no worse than any other, she would not change it either). $\endgroup$ – Sasho Nikolov Jun 14 '11 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.