1
$\begingroup$

Question: If I prove a protocol secure in the plain model (i.e., without any prerequisites or setup before running the protocol, setups like a common reference string distributed among all parties) using nonstandard hardness assumptions (like bilinear oracle Diffie-Hellman) has any advantage over a protocol which uses a setup before running but its hardness relies on a standard hardness assumption (like discrete logarithm)?
If there is a tradeoff, can you point me how to maintain this tradeoff?

I must note that the nonstandard hardness does not give you enough measure to compare the complexity of the protocol using it with other protocols.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Let me rephrase the question:

Which one is preferred?

  1. Proving a protocol secure in the standard model, based on non-standard assumptions
  2. Proving a protocol secure in non-standard models (like CRS), based on standard assumptions.

The short answer is: It depends!

Details follow.

Assume that you can prove a protocol secure in the CRS model using standard assumptions. In addition, assume that you can implement the CRS model in the standard model without significant overhead, and using only standard assumptions. Then, the second approach is preferable. (Here, "significant" depends on the application.)

On the other hand, assume that you cannot implement the CRS model in the standard model easily ,i.e. either the overhead is too high, or the protocol setting is that you cannot implement the CRS without resorting to non-standard assumptions (For instance: You don't have access to some trusted 3rd party, etc.) In such cases, it seems that the first approach is preferable.

Side note: I must add that both approaches are highly valuable in theory, regardless of the real-world application.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't see the logic you are using to compare these two. Suppose the nonstandard uses bilinear multiplication operation over elliptic curves but standard assumption relies on discrete logarithm. How can you compare these two when a multiplication over the elliptic curve does not have an efficient algorithm (w.r.t. the pairing) but discrete logarithm can be computed very fast? How do you define that significant term? $\endgroup$
    – Yasser Sobhdel
    Commented Nov 18, 2010 at 22:23
  • $\begingroup$ @Yasser: As I said, comparing the two depends on the application. I cannot define it out-of-context. I didn't get the first part of your comment; Can you elaborate? $\endgroup$
    – Sadeq Dousti
    Commented Nov 19, 2010 at 12:25
  • $\begingroup$ There are some standard hardness assumptions that can be assumed as the basis of comparison between efficiency of the protocols. When a protocol is based on discrete logarithm, you can compare it with other protocol which benefit form the same hardness (assuming the same complexity class). However, when there is an inefficient approach which relies on a nonstandard assumption, but has fewer messages and less operations you cannot compare the two, because an operation over an elliptic curve is not the same as a modular exponentiation over a usual algebraic field. $\endgroup$
    – Yasser Sobhdel
    Commented Nov 20, 2010 at 6:35
  • $\begingroup$ @Yasser: Note that a nonstandard assumption does not necessarily mean an inefficient one. In some approaches, this might be the case, but you cannot generalize it. $\endgroup$
    – Sadeq Dousti
    Commented Nov 20, 2010 at 6:40

Your Answer

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

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