Skip to main content
Bumped by Community user
added 584 characters in body
Source Link
Titanlord
  • 2.4k
  • 12
  • 34

In cryptography security proofs mainly use the reduction proof technique. I now have read a lot of reductions proofs and also did some on my own and I think I understand it pretty well. While reading those proofs I noticed two main styles of such a reduction.

Say we have scheme $B$ based on $A$. We know $A$ is secure. If one wants to proof the security of $B$ by reducing it to the security of $A$ he can proceed as follows:

  1. Style: Assume an adversary that can break $B$ $\Rightarrow$ For the reduction one can build a new adversary breaking $A$ using the adversary breaking $B$ $\Rightarrow$ The result is a contradiction that shows, there is no non negligible adversary against $B$
  2. Style: Assume an arbitrary ppt adversary against $B$ $\Rightarrow$ Show (e.g. with stochastic analysis of experiment) that breaking $B$ is as hard as breaking $A$, therefore reduce the complexity of breaking $B$ to the complexity of breaking $A$ $\Rightarrow$ Because there are only negligible adversarys against $A$ there is no non negligible adversary against $B$

Of course this is simplified, but I wanted to give you an idea of what I noticed.

My questions: Do these styles really exist? Can they both (correctly formally written down) proof the same? Are they both (especially style 1.) complete? For what proofs should one use which style?

Edit: A more precise definition of style 2.: In Introduction to modern cryptography the prove a cryptosystem on a PRG: In the stochastic analysis they state, that breaking the cryptosystem is as likely as breaking the PRG. They use this to imply, that any arbitrary adversary must be negligible in the fashion: Because this is negligible, and they have the same probability, the other must also be negligible.

(Note: In short I would describe 1. as: $B \rightarrow A \rightarrow \unicode{x21af} \rightarrow B$ and 2. as: $B \rightarrow A \rightarrow (B = A) \rightarrow B$)

In cryptography security proofs mainly use the reduction proof technique. I now have read a lot of reductions proofs and also did some on my own and I think I understand it pretty well. While reading those proofs I noticed two main styles of such a reduction.

Say we have scheme $B$ based on $A$. We know $A$ is secure. If one wants to proof the security of $B$ by reducing it to the security of $A$ he can proceed as follows:

  1. Style: Assume an adversary that can break $B$ $\Rightarrow$ For the reduction one can build a new adversary breaking $A$ using the adversary breaking $B$ $\Rightarrow$ The result is a contradiction that shows, there is no non negligible adversary against $B$
  2. Style: Assume an arbitrary ppt adversary against $B$ $\Rightarrow$ Show (e.g. with stochastic analysis of experiment) that breaking $B$ is as hard as breaking $A$, therefore reduce the complexity of breaking $B$ to the complexity of breaking $A$ $\Rightarrow$ Because there are only negligible adversarys against $A$ there is no non negligible adversary against $B$

Of course this is simplified, but I wanted to give you an idea of what I noticed.

My questions: Do these styles really exist? Can they both (correctly formally written down) proof the same? Are they both (especially style 1.) complete? For what proofs should one use which style?

In cryptography security proofs mainly use the reduction proof technique. I now have read a lot of reductions proofs and also did some on my own and I think I understand it pretty well. While reading those proofs I noticed two main styles of such a reduction.

Say we have scheme $B$ based on $A$. We know $A$ is secure. If one wants to proof the security of $B$ by reducing it to the security of $A$ he can proceed as follows:

  1. Style: Assume an adversary that can break $B$ $\Rightarrow$ For the reduction one can build a new adversary breaking $A$ using the adversary breaking $B$ $\Rightarrow$ The result is a contradiction that shows, there is no non negligible adversary against $B$
  2. Style: Assume an arbitrary ppt adversary against $B$ $\Rightarrow$ Show (e.g. with stochastic analysis of experiment) that breaking $B$ is as hard as breaking $A$, therefore reduce the complexity of breaking $B$ to the complexity of breaking $A$ $\Rightarrow$ Because there are only negligible adversarys against $A$ there is no non negligible adversary against $B$

Of course this is simplified, but I wanted to give you an idea of what I noticed.

My questions: Do these styles really exist? Can they both (correctly formally written down) proof the same? Are they both (especially style 1.) complete? For what proofs should one use which style?

Edit: A more precise definition of style 2.: In Introduction to modern cryptography the prove a cryptosystem on a PRG: In the stochastic analysis they state, that breaking the cryptosystem is as likely as breaking the PRG. They use this to imply, that any arbitrary adversary must be negligible in the fashion: Because this is negligible, and they have the same probability, the other must also be negligible.

(Note: In short I would describe 1. as: $B \rightarrow A \rightarrow \unicode{x21af} \rightarrow B$ and 2. as: $B \rightarrow A \rightarrow (B = A) \rightarrow B$)

Source Link
Titanlord
  • 2.4k
  • 12
  • 34

Question about styles of reduction proofs

In cryptography security proofs mainly use the reduction proof technique. I now have read a lot of reductions proofs and also did some on my own and I think I understand it pretty well. While reading those proofs I noticed two main styles of such a reduction.

Say we have scheme $B$ based on $A$. We know $A$ is secure. If one wants to proof the security of $B$ by reducing it to the security of $A$ he can proceed as follows:

  1. Style: Assume an adversary that can break $B$ $\Rightarrow$ For the reduction one can build a new adversary breaking $A$ using the adversary breaking $B$ $\Rightarrow$ The result is a contradiction that shows, there is no non negligible adversary against $B$
  2. Style: Assume an arbitrary ppt adversary against $B$ $\Rightarrow$ Show (e.g. with stochastic analysis of experiment) that breaking $B$ is as hard as breaking $A$, therefore reduce the complexity of breaking $B$ to the complexity of breaking $A$ $\Rightarrow$ Because there are only negligible adversarys against $A$ there is no non negligible adversary against $B$

Of course this is simplified, but I wanted to give you an idea of what I noticed.

My questions: Do these styles really exist? Can they both (correctly formally written down) proof the same? Are they both (especially style 1.) complete? For what proofs should one use which style?