<p>Let me rephrase the question: </p>

<blockquote>
  <p>Which one is preferred?</p>
  
  <ol>
  <li>Proving a protocol secure in the <strong>standard</strong> model, based on <strong>non-standard</strong> assumptions</li>
  <li>Proving a protocol secure in <strong>non-standard</strong> models (like <a href="http://en.wikipedia.org/wiki/Common_reference_string_model" rel="nofollow">CRS</a>), based on <strong>standard</strong> assumptions.</li>
  </ol>
</blockquote>

<p>The short answer is: It depends!</p>

<p>Details follow. </p>

<p>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 <em>significant</em> overhead, and using only standard assumptions. Then, the second approach is preferable. (Here, "significant" depends on the application.)</p>

<p>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.</p>

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

CC BY-SA 2.5
2010-11-18T22:23:28.820Z
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?
Yasser Sobhdel
CC BY-SA 2.5
2010-11-19T12:25:50.797Z
@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?
Sadeq Dousti
CC BY-SA 2.5
2010-11-20T06:35:34.430Z
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.
Yasser Sobhdel
CC BY-SA 2.5
2010-11-20T06:40:53.033Z
@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.
Sadeq Dousti
CC BY-SA 2.5
2010-11-18T22:00:24.050Z
2010-11-18T22:00:24.050Z
Sadeq Dousti
<blockquote>
  <p><strong>Question</strong>: 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)?<br>
  If there is a tradeoff, can you point me how to maintain this tradeoff?</p>
</blockquote>

<p>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.</p>

<cc.complexity-theory><cr.crypto-security>
Is the model in which a protocol is proven secure more important than type of hardness from which the algorithm gains its strength
Yasser Sobhdel
# Is the model in which a protocol is proven secure more important than type of hardness from which the algorithm gains its strength

(Asked by: username_0 on 2010-11-18)

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

**Tags:** cc.complexity-theory, cr.crypto-security

---

## 1 answers

### Answer by username_1 on 2010-11-18. Score: 2 | Accepted answer

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](http://en.wikipedia.org/wiki/Common_reference_string_model)), 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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: @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?  
> **username_0**: 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.  
> **username_1**: @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.  

---

