To prove a protocol secure in the computational model, one can use game-based approach or the simulation approach (I just assume these two models for simplicity).

  • In the game based approach, the security of the mentioned protocol is verified through some games between parties or between parties and algorithms (oracles). This approach usually gives us a lower bound on the communication effort for the protocol.

  • The second approach is through an ideal functionality or a trusted third party which acts as a paradigm for what we seek from meaning of security when running that protocol. This is usually called 'the Ideal/Real Paradigm'. In this approach a $\mathcal{PPT}$ (probabilistic polynomial time) machine which we call it 'the simulator' is responsible for generating the interaction between parties while running the protocol such that no other $\mathcal{PPT}$ machine (called distinguisher) can have any advantage greater than 0.5 to distinguish between the real interaction and the simulator made interaction. In this way we have proven the protocol secure by just comparing it to what is ideal when defining security of that protocol.

In the Ideal/Real paradigm, when proving a protocol secure some times the simulator must use some special types of primitives. For example, when facing an adaptive adversary (fully capable adversary), we may use non-committing encryption or trapdoor permutation or some other forms of equivocal primitives to provide the same view as the real world.

Question: What does it mean to use a equivocal primitive? What is the practical point of that? Do we use these primitives in practice? can you name some?

As a side note, I found some good issues on this in the response of Damgard to Koblitz Controversy. [I just noticed that this forum is Theoretical Computer Science, but I have asked something practical]

Edit: I may explain more on the non-committing encryption here to clarify my question. Let start an example; In a secure multi-party computation, the best way of communication is through secure channels. A secure channel by definition is the one in which the full-fledged adversary which controls the whole communications cannot see the messages. What does is it mean not to see the communication where all communications are visible to adversary and actually if she decides to put an end to a conversation, she can do it easily by dropping messages. The point is, informally when a non-committing encryption is used over a channel it makes the channel a secure channel because every permutation of an encrypted message is possible now. Remember that a non-committing encryption is the one in which a receiver can open a ciphertext bit to "0" or "1" as he wishes. As a naive example, consider one-time-pad and suppose your ciphertext is, say, 111; One can open it to every permutation of 3 bits length. So when this kind of ciphertext is at hand, the adversary can infer nothing out of it and it is equivalent to not receiving such a ciphertext at all.

  • $\begingroup$ Yaser, I think it would be nice if you add some motivation part to your questions and tell us why you are interested in them, that would make them more interesting to us also. Please read How to ask a good question?. $\endgroup$
    – Kaveh
    Dec 4, 2010 at 12:51
  • $\begingroup$ @Kaveh: it is edited now. Most of these comments are some ordinary definitions that every one that has studied computational models know them. Since my question is not an easy one, I assumed that the one who can answer it must know these basics. But you are right. Please let me know if it is not enough. $\endgroup$ Dec 4, 2010 at 15:34
  • 1
    $\begingroup$ Thanks Yaser for reading the meta post I have linked to, but I think you misunderstood me, I was talking about why you are personally interested in the question, e.g. are you working on a problem which is related to this question? I think providing some information on why you are asking a question helps in getting others spend time on it since they will know that the question is important for you and not just another question, specially when the question is not easy to understand/answer. $\endgroup$
    – Kaveh
    Dec 5, 2010 at 14:59


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.