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$)

  • $\begingroup$ In #2: "Show that breaking B is as hard as breaking A", how is that different than #1? How do you show this, other than using a successful B-adversary to construct a successful A-adversary? What exactly do you mean by "stochastic analysis of experiment"? Do you have an example in mind of what you mean by #2? $\endgroup$
    – Mikero
    Nov 5 '21 at 15:33
  • $\begingroup$ I think Katz & Lindell's textbook (2nd edition)) uses style 2, e.g. to prove the PRG cryptoscheme they built. $\endgroup$
    – Titanlord
    Nov 5 '21 at 15:37
  • $\begingroup$ @Mikero It's different in that you're avoiding unnecessarily and confusingly using an argument by contradiction. Style 1 makes the statement "A and not B implies a contradiction" from this you then conclude that B, because you assume A. Style 2. on the other hand directly makes the statement "A implies B" avoiding the unnecessary detour. The end result is the same unless you have some weird views on logic. $\endgroup$
    – Maeher
    Nov 5 '21 at 15:44
  • 1
    $\begingroup$ @Mikero This is probably not a great discussion to be had in the comments, but I'm reading style 1 to be referring to proofs of the form "Assume that there exist a PPT machine that breaks A with non-negligible advantage. Then there exists a PPT machine that breaks B with non-negligible advantage. This contradicts the assumption that B is secure, therefore A does not exist." Whereas style 2 says "Consider an arbitrary PPT machine. Then assuming B is secure the advantage of this machine is negligible." $\endgroup$
    – Maeher
    Nov 5 '21 at 16:46
  • 1
    $\begingroup$ The second style need a better writing from Titanlord $\endgroup$
    – kelalaka
    Nov 5 '21 at 18:28

The only difference I see between style 1 and a proper redaction of style 2 is that style 1 is missing things that are explicit in 2 about the adversary/algorithm hypothesized to attack B, and the resulting adversary/algorithm that would attack A:

  1. The algorithms are Probabilistic Polynomial-Time; that is have an implicit input with random bits, and run for a time at most some polynomial $P(n)$ for all values of the security parameter $n$ (or their input size) past some lower bound.
  2. They have a non-negligible (or non-vanishing) probability of success, that is: for some polynomial $P'$, for any fixed bound $N\in\mathbb{N}$ there exist values $n>N$ for the security parameter (or their input size), such that the probability of success is at least $1/P'(n)>0$.

A proof that “breaking the cryptosystem is as likely as breaking the PRG” proves that in 2 we can reuse the polynomial $P'$ and values of $n$ for a given bound $N$ that are appropriate for the hypothesized attack of B in the the proof that the attack of A is one that has non-negligible probability of success.

In other words, style 1 is a simplification of style 2, often at the expense of rigorousness. For some proofs in style 1, it gets mastering style 2 to confidently tell if the proof is correct.

There are even more complex styles, e.g. where the probability of success is quantitative. In this case, “breaking the cryptosystem is as likely as breaking the PRG” is a so-called tight proof. Some other quantitative proofs are harder to follow.

  • 1
    $\begingroup$ A PPT machine runs in strict polynomial time, not expected polynomial time. $\endgroup$
    – Maeher
    Nov 8 '21 at 13:13
  • 1
    $\begingroup$ Also, in 2. what you are describing is a noticable probability. This is not synonymous with non-negligible. $\endgroup$
    – Maeher
    Nov 8 '21 at 13:14
  • $\begingroup$ @Maeher: I take your word on the definition of PPT, and I think I understood and fixed my mistake in the definition of non-negligible. Thanks for the corrections! $\endgroup$
    – fgrieu
    Nov 8 '21 at 13:58
  • 1
    $\begingroup$ I have tried to make that point clearer. Just roll back the edit if you don't like it. $\endgroup$
    – Maeher
    Nov 8 '21 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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