Join Log in
Score:2
Titanlord avatar Crypto

Question about styles of reduction proofs

tl flag
Titanlord

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

125
0 + 0
us flag
Mikero
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?
0
Reply
Titanlord avatar
tl flag
Titanlord
I think [Katz & Lindell's textbook (2nd edition)](https://www.cs.umd.edu/~jkatz/imc.html)) uses style 2, e.g. to prove the PRG cryptoscheme they built.
0
Reply
cn flag
Maeher
@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.
0
Reply
us flag
Mikero
@Maeher, interesting. I don't find style #1 to necessarily entail a proof by contradiction. I interpret it as "if A is broken then B is broken too." The contrapositive is that if B is secure than A is secure. There are other proof styles (which I actually prefer) that avoid having to switch back and forth between contrapositive interpretations, and stay entirely within the world of "if B is secure than A is secure", but I did not recognize #2 in this question as a description of that style.
0
Reply
kelalaka avatar
in flag
kelalaka
It is a matter of fact that sometimes $p \implies q$ is not so obvious to show and the contrapositive may be easier to show. That is why we choose them. CS has some questions about reductions where the term comes from [1](https://cs.stackexchange.com/q/11209/94479) and even they have a tag [recductions](https://cs.stackexchange.com/questions/tagged/reductions?tab=Votes)
0
Reply
cn flag
Maeher
@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."
1
Reply
kelalaka avatar
in flag
kelalaka
The second style need a better writing from Titanlord
1
Reply
Score:1
fgrieu avatar Crypto
ng flag
fgrieu

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.

0 + 0
cn flag
Maeher
A PPT machine runs in *strict* polynomial time, *not* expected polynomial time.
1
Reply
cn flag
Maeher
Also, in 2. what you are describing is a *noticable* probability. This is *not* synonymous with non-negligible.
1
Reply
fgrieu avatar
ng flag
fgrieu
@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!
0
Reply
cn flag
Maeher
I have tried to make that point clearer. Just roll back the edit if you don't like it.
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.