Timeline for Question about styles of reduction proofs
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 8, 2021 at 15:50 | vote | accept | Titanlord | ||
| Dec 8, 2021 at 15:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Nov 8, 2021 at 10:10 | answer | added | fgrieu♦ | timeline score: 1 | |
| Nov 8, 2021 at 8:46 | history | edited | Titanlord | CC BY-SA 4.0 |
added 584 characters in body
|
| Nov 5, 2021 at 18:28 | comment | added | kelalaka | The second style need a better writing from Titanlord | |
| Nov 5, 2021 at 16:46 | comment | added | 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." | |
| Nov 5, 2021 at 16:31 | comment | added | 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 and even they have a tag recductions | |
| Nov 5, 2021 at 15:48 | comment | added | 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. | |
| Nov 5, 2021 at 15:44 | comment | added | 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. | |
| Nov 5, 2021 at 15:37 | comment | added | Titanlord | I think Katz & Lindell's textbook (2nd edition)) uses style 2, e.g. to prove the PRG cryptoscheme they built. | |
| Nov 5, 2021 at 15:33 | comment | added | 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? | |
| Nov 5, 2021 at 15:25 | history | asked | Titanlord | CC BY-SA 4.0 |