Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I've been trying to understand cryptographic protocols and how to define their security. The problem is that while I can understand what the intuitive definition says, I have trouble understanding how this can be rigorously defined in terms of mathematics. In other words, how do we get a definition that can be used in proving something?

For simplicity, let's take a two-party protocol between $A$ and $B$. This can essentially be modeled as a 2-ary function $f(x,y)=(f_A(x,y),f_B(x,y))$, where $x$ and $y$ are the local inputs and $f_A$ models $A$'s output and $f_B$ models $B$'s output.

Now the intuitive definition is that we can have our ideal protocol, where we have a trusted party $T$ and $A$, $B$ just hands over their local inputs to $T$, which replies with either $f_A(x,y)$ or $f_B(x,y)$. The protocols would then be considered secure, if given any adversary $\mathcal{A}$ for the real-world protocol, we can construct an adversary $\mathcal{S}$ for the ideal protocol that ''accomplished the same thing''. While this sounds like what we intuitively want, it provides no bases for really any proofs.

I've seen some alternative definitions where the ideal and real-world protocol output a ''transcript''. The protocol would then be considered secure if e.g. no PPT algorithm can distinguish the transcripts. However, I have no idea what the exact mathematical definition of a transcript is?

I would hope that someone could actually open up these definitions and explain how to make them rigorous. Hopefully also with a concrete example.

share|improve this question
add comment

1 Answer 1

Suppose Alice has $x$ and Bob has $y$ in your scenario, and let $\pi =(\pi_A, \pi_B)$ be the protocol machines for Alice & Bob respectively. Here is how you would formally define security of the protocol against a corrupt Alice.

Define the following algorithms / random variables:

${\sf Real}(\pi, y,\mathcal{A},1^k)$:

  1. Internally simulate an instance of $\pi_B$ on inputs $(1^k,y)$, interacting with an instance of $\mathcal{A}$ on input $1^k$.

  2. $\pi_B$ will eventually terminate; call its output $q$ (note, this is supposed to be the output of $f$, or it can be an error indicator). Likewise $\mathcal{A}$ will eventually terminate; call its output $t$.

  3. Output $(q,t)$.

${\sf Ideal}(f, y,\mathcal{S},1^k)$:

  1. Internally simulate an instance of $\mathcal{S}$ on input $1^k$ until it generates an output $\tilde x$.

  2. Calculate $p = f_A(\tilde x, y)$ and $q = f_B(\tilde x, y)$.

  3. Give $p$ to $\mathcal{S}$ and keep running it until it finally terminates; call its output $t$.

  4. Output $(q,t)$.

Then we say that the protocol is secure if:

For all PPT machines $\mathcal{A}$ there exists a PPT machine $\mathcal{S}$ such that for all $x,y$, the ensembles $\{ {\sf Real}(\pi, y,\mathcal{A},1^k) \}_k$ and $\{ {\sf Ideal}(f, y,\mathcal{S},1^k) \}_k$ are computationally indistinguishable.

I'll assume you're comfortable with the notion of computational indistinguishability.

Some general observations:

The value $t$ is whatever $\mathcal{A}$ decides to output. One reason why it's difficult to understand at first is that we are not specifying a "goal" that $\mathcal{A}$ wants to achieve. It's more general than that. Instead, we're saying that: Any value $t$ that $\mathcal{A}$ can generate by participating in the real interaction, is possible to generate when the only thing you are allowed to do is choose an input $\tilde x$ (once) and get back $f_A(\tilde x, y)$.

Without loss of generality, $t$ can be the entire view (private randomness along with all of the messages received in the protocol) of $\mathcal{A}$, since $t$ would have been efficiently computed from the view. Sometimes the terms view and transcript are used synonymously, though the term view better entails that private randomness is included as well. Also, this is why $\mathcal{S}$ is referred to as a simulator, since it must be able to simulate everything that $\mathcal{A}$ would have seen.

We also include the output $q$ of the honest party Bob in these distribution ensembles. This models the fact that $\mathcal{A}$, in addition to learning no more than is possible in the ideal world, has an effect on Bob that is possible in the ideal world. In particular, $\mathcal{A}$ can't force Bob to output a value that is inconsistent with $f$ (other more subtle attacks are also ruled out in this way).


Of course, even this fairly detailed definition does not include everything tha there is to say. To be absolutely precise you have to specify how the protocol interaction works, whether the adversary has control over delivery of messages, whether the multiple components (adversary, protocol) should be executed in series or parallel, etc.. But once you have conventions for these things, the $\sf Real$ and $\sf Ideal$ processes are well-defined, and everything else written here is pretty sound.

More sophisticated definitions allow $\mathcal{A}$ (and hence $\mathcal{S}$) to communicate online (i.e., during the protocol execution) with an external "environment" ... that introduces a whole lot of other complications. So for the purposes of this response, we'll leave it as a static interaction.

share|improve this answer
    
Thanks! The first paragraph of your "general observations" cleared this up for me. I'm aware that there seems to be a bunch of frameworks for this. A lot of recent papers seem to concentrate on "composability", where "universal composition" seems like a big thing. Do you know if there's any consensus among cryptographers regarding which current definitions are "right"? –  dst Sep 29 '12 at 20:22
    
UC is the most realistic in terms of protocols running in the presence of other protocols. Some people have qualms about some very low-level technical aspects, and have made competing frameworks. Also, UC doesn't model every possible thing under the sun -- for example, there are security properties for incoercibility which the UC security definition doesn't cover. –  Mikero Sep 30 '12 at 2:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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